计算机网络（计算机学院）chapter5b

SummaryofMACprotocols

nWhatdoyoudowithasharedmedia?

oChannelPartitioning,bytime,frequencyorcode

•TimeDivision,CodeDivision,FrequencyDivision

oRandompartitioning(dynamic),

•ALOHA,S-ALOHA,CSMA,CSMA/CD

•carriersensing:easyinsometechnoligies(wire),hard

inothers(wireless)

•CSMA/CDusedinEthernet

□TakingTurns

•pollingfromacentralcite,tokenpassing

哈工大计算机学院李全龙ComputerNetworks5:DatalinkLayerandLAN1

LANtechnologies

Datalinklayersofar:

oservices,errordetection/correction,multiple

access

Next:LANtechnologies

oaddressing

oEthernet

ohubs,bridges,switches

0802.11R

O

U

T

E

R

userhosts

哈工大计算机学院李全龙ComputerNetworks5:DatalinkLayerandLAN2

兄黑

LANAddressesandARP

32-bitIPaddress:

□network-layeraddress(discussitlater)

□usedtogetdatagramtodestinationnetwork

LAN(orMACorphysical)address:

□usedtogetdatagramfromoneinterfaceto

anotherphysically-connectedinterface(same

network)

□48bitMACaddress(formostLANs)

burnedintheadapterROM

哈工大计算机学院李全龙ComputerNetworks5:DatalinkLayerandLAN3

LANAddressesandARP

EachadapteronLANhasuniqueLANaddress

node

1A-23-F9-CD-06-9B

49-BD-D2-C7-56-2A

node

哈工大计算机学院李全龙ComputerNetworks5:DatalinkLayerandLAN4

LANAddress(more)

□MACaddressallocationadministeredbyIEEE

□manufacturerbuysportionofMACaddressspace

(toassureuniqueness)

□Analogy:

(a)MACaddress:likeSocialSecurityNumber

(b)IPaddress:likepostaladdress

□MACflataddress=>portability

ocanmoveLANcardfromoneLANtoanother

□IPhierarchicaladdressNOTportable

odependsonnetworktowhichoneattaches

哈工大计算机学院李全龙ComputerNetworks5:DatalinkLayerandLAN5

品

Recallearlierroutingdiscussion

StartingatA,givenIP

>223.1.1.1

datagramaddressedtoB:

223.1.27

alookupnet.addressofB,findB223.1.1.2

onsamenet.asA223.11.2.9

□linklayersenddatagramtoBcr223.1

i.27

insideIink-1ayerframe223.1.1.3223

223.1/1223.1.3.2

framesource,datagramsource,

destaddressdestaddress

B'sMACA'sMACA：/B'*IPpayload

addraddraddraddrr'

datagram

frame

哈工大计算机学院李全龙ComputerNetworks5:DatalinkLayerandLAN6

ARP:AddressResolutionProtocol

Question:howtodetermine□EachIPnode(Host,

MACaddressofBRouter)onLANhas

givenB5sIPaddress?ARPmodule,table

□ARPTable:IRMAC

addressmappingsfor

someLANnodes

<1Paddress;MACaddress;TTL>

<.........................>

oTTL(TimeToLive):time

afterwhichaddress

mappingwi11beforgotten

(typically20min)

哈工大计算机学院李全龙ComputerNetworks5:DatalinkLayerandLAN7

ARPprotocol

□AknowsB'sIPaddress,wantstolearnphysical

addressofB

□AbroadcastsARPquerypkt,contaimingB'sIP

address

oallmachinesonLANreceiveARPquery

□BreceivesARPpacket,repliestoAwithits(B's)

physicallayeraddress

□Acaches(saves)IP-to-physicaladdresspairsuntil

informationbecomesold(timesout)

osoftstate:informationthattimesout(goes

away)unlessrefreshed

哈工大计算机学院李全龙ComputerNetworks5:DatalinkLayerandLAN8

RoutingtoanotherLAN

walkthrough:routingfromAtoBviaR

CC-49-DE-D0-AB-7D

□InroutingtableatsourceHost,findrouter

111.111.111.110

□InARPtableatsource,findMACaddressE6-E9-

00-17-BB-4B,etc

哈工大计算机学院李全龙ComputerNetworks5:DatalinkLayerandLAN9

口AcreatesIPpacketwithsourceA,destinationB匕产

□AusesARPtogetRsphysicallayeraddressfor111.111.111.110

□AcreatesEthernetframewithRsphysicaladdressasdest,

EthernetframecontainsA-to-BIPdatagram

□A5sdatalinklayersendsEthernetframe

口RsdatalinklayerreceivesEthernetframe

□RremovesIPdatagramfromEthernetframe,seesits

destinedtoB

□RusesARPtogetB'sphysicallayeraddress

aRcreatesframecontaimingA-to-BIPdatagramsendstoB

CC-49-DE-D0-AB-7D

哈工大计算机学院李全龙ComputerNetworks5:DatalinkLayerandLAN10

jjj;t;・工・')

,ARPmessageformat(IPtoEthernet)

ARPMESSAGE

FRAMEFRAMEDATAAREA

HEADER

08162431

HARDWARETYPEPROTOCOLTYPE

HLENPLENOPERATION

SENDERHA(octets0-3)

SENDERHA(octets4-5)SENDERIP(octets0-1)

SENDERIP(octets2-3)TARGETHA(octets0-1)

TARGETHA(octets2-5)

TARGETIP(octets0-3)

哈工大计算机学院李全龙ComputerNetworks5:DatalinkLayerandLAN11

ARPmessageformat(IPtoEthernet)

ARPMESSAGE

，I9-Ethernet____।

AMEFRAMEDATAAREA

XDER

0162431

^HARDWARETYPE^>PROTOCOLTYPE

HLEN|PLENOPERATION

SENDERHA(octets0-3)

SENDERHA(octets4-5)SENDERIP(octets0-1)

SENDERIP(octets2-3)TARGETHA(octets0-1)

TARGETHA(octets2-5)

TARGETIP(octets0-3)

哈工大计算机学院李全龙ComputerNetworks5:DatalinkLayerandLAN12

ARPmessageformat(IPtoEthernet)

Upperlayerprotocol

——addresstype,forIP,it's

~~—valueis0806H\

0816一-----------2^_31

HARDWARETYPE^PROTOCOLTYPE^>

HLEN|PLENOPERATION

SENDERHA(octets0-3)

SENDERHA(octets4-5)SENDERIP(octets0-1)

SENDERIP(octets2-3)TARGETHA(octets0-1)

TARGETHA(octets2-5)

TARGETIP(octets0-3)

哈工大计算机学院李全龙ComputerNetworks5:DatalinkLayerandLAN13

,ARPmessageformat(IPtoEthernet)谭

ARPMESSAGE

HardwareAddressLength

1----------1——由哂——I一FRAMEDATAAREA

8162431

A/ARDWARETYPEPROTOCOLTYPE

CHLEN31PLENOPERATION

SENDERHA(octets0-3)

SENDERHA(octets4-5)SENDERIP(octets0-1)

SENDERIP(octets2-3)TARGETHA(octets0-1)

TARGETHA(octets2-5)

TARGETIP(octets0-3)

哈工大计算机学院李全龙ComputerNetworks5:DatalinkLayerandLAN14

ARPmessageformat(IPtoEthernet)

ARPMESSAGE

FRAMEDATAAREA

ProtocolAddressLength

0831

HARDWARETYPEj广PROTOCOLTYPE

HLEN|CPLENJ)OPERATION

SENDERHA(octets0-3)

SENDERHA(octets4-5)SENDERIP(octets0-1)

SENDERIP(octets2-3)TARGETHA(octets0-1)

TARGETHA(octets2-5)

TARGETIP(octets0-3)

哈工大计算机学院李全龙ComputerNetworks5:DatalinkLayerandLAN15

11

,ARPmessageformat(IPtoEthernet)

ARPMESSAGE

FRAMEFRAMEDATAAREA

HEADER

08

HARDWARETYPE^BBDTQCOLTYPE

HLEN|PLENJOPERATIONJ)

SENDERHA(octets0.3)

L___________________________

1

SENDERHA(octets4-5)169

■11-ARPrequest

SENDERIP(octets2-3)'2'-ARPresponse

TARGETHA(octet'3'-RARPrequest

'4'-RARPresponse

TARGETIP(octet；—VVf

哈工大计算机学院李全龙ComputerNetworks5:DatalinkLayerandLAN16

,ARPmessageformat(IPtoEthernet)谭

ARPMESSAGE

|FRAME|

--------------------------FRAMEDATAAREA

0SenderHardware162431

Address\PROTOCOLTYPE

HLtN|PLt£L----OPERATION

CINDERHA(octets豆

SENDERHA(octets4-5)SENDERIP(octets0-1)

SENDERIP(octets2-3)TARGETHA(octets0-1)

TARGETHA(octets2-5)

TARGETIP(octets0-3)

哈工大计算机学院李全龙ComputerNetworks5:DatalinkLayerandLAN17

ARPmessageformat(IPtoEthernet)

0824

HARDWARET、SenderIPAddress；OLTYPE

HLEN\!0N

SENDERHA(octets4-5)SENDERIP

SENDERIP(octets2-3)TARGETHA(octets0-1)

TARGETHA(octets2-5)

TARGETIP(octets0-3)

哈工大计算机学院李全龙ComputerNetworks5:DatalinkLayerandLAN18

ARPmessageformat(IPtoEthernet)

ARPMESSAGE

FRAMEFRAMEDATAAREA

HEADER

0824

HARDWARE「：OLTYPE

HLENTargetHardwareNATION

Addressx____

SENDERHA(octets5)btzNUt-KIP1

SENDERIP(octets2-3)的GETHA(octets0^

TARGETHA(octets2-5)

TARGETIP(octets0-3)

哈工大计算机学院李全龙ComputerNetworks5:DatalinkLayerandLAN19

谭

,ARPmessageformat(IPtoEthernet)

ARPMESSAGE

FRAMEFRAMEDATAAREA

HEADER

08162431

HARDWARETYPEPROTOCOLTYPE

HLENPLENOPERATION

zk(octets0-3)

TargetIPAddressSENDERIP(octets0-1)

X

「TARGETHA.octetsCM：.

L4^Uts^2-5)

TARGETIP(octets

哈工大计算机学院李全龙ComputerNetworks5:DatalinkLayerandLAN20

,Ethernet

“dominant”LANtechnology:

□cheap$20for100Mbs!

□firstwildeyusedLANtechnology

□Simpler,cheaperthantokenLANsandATM

□Keptupwithspeedrace:10,100,1000Mbps

Metcalfe'sEtheret

sketch

哈工大计算机学院李全龙ComputerNetworks5:DatalinkLayerandLAN21

.EthernetFrameStructure

SendingadapterencapsulatesIPdatagram

(orothernetworklayerprotocolpacket)

inEthernetframe

DestSource

PreambleData

AddressAddress

Type

Preamble:

□7byteswithpattern10101010followedbyonebyte

withpattern10101011

□usedtosynchronizereceiver,senderclockrates

哈工大计算机学院李全龙ComputerNetworks5:DatalinkLayerandLAN22

“EthernetFrameStructure

(more)

□Addresses:6bytes,frameisreceivedbyall

adaptersonaLANanddroppedifaddressdoes

notmatch

□Type:indicatesthehigherlayerprotocol,mostly

IPbutothersmaybesupportedsuchasNovelI

IPXandAppleTalk)

□CRC:checkedatreceiver,iferrorisdetected,the

frameissimplydropped

DestSource

PreambleD的

AddressAddressn

Type

哈工大计算机学院李全龙ComputerNetworks5:DatalinkLayerandLAN23

耳

Ethernet:usesCSMA/CD

A:sensechannel,ifidle

then{

transmitandmonitorthechannel;

Ifdetectanothertransmission

then{

abortandsendjamsignal;

update#collisions;

delayasrequiredbyexponentialbackoffalgorithm;

gotoA

)

else{donewiththeframe;setcollisionstozero}

)

else{waituntilongoingtransmissionisoverandgotoA}

哈工大计算机学院李全龙ComputerNetworks5:DatalinkLayerandLAN24

Ethernet'sCSMA/CD(more)

JamSignal:makesureallothertransmittersare

awareofcollision;48bits;

ExponentialBackoff:

□Goal',adaptretransmissionattemtpstoestimated

currentload

oheavyload:randomwaitwillbelonger

□firstcollision:chooseKfrom{0,1};delayisKx512

bittransmissiontimes

□aftersecondcollision:chooseKfrom{0,1,2,3}...

□aftertenormorecollisions,chooseKfrom

{0,1,2,3,4,..,1023}

哈工大计算机学院李全龙ComputerNetworks5:DatalinkLayerandLAN25

EthernetTechnologies:10Base2

□10:10Mbps;2:under200metersmaxcablelength

□thincoaxialcableinabustopology

□repeatersusedtoconnectuptomultiplesegments

□repeaterrepeatsbitsithearsononeinterfaceto

itsotherinterfaces:physicallayerdeviceonly!

哈工大计算机学院李全龙ComputerNetworks5:DatalinkLayerandLAN26

耳

10BaseTand1OOBaseT

□10/100Mbpsrate;lattercalledufastethernet55

□TstandsforTwistedPair

□Hubtowhichnodesareconnectedbytwistedpair,

thus“startopology^^

□CSMA/CDimplementedathub

backbone

哈工大计算机学院李全龙ComputerNetworks5:DatalinkLayerandLAN27

兄

10BaseTand1OOBaseT(more)

□MaxdistancefromnodetoHubis100meters

□Hubcandisconnectujabberingadapter

□Hubcangathermonitoringinformation,statistics

fordisplaytoLANadministrators

哈工大计算机学院李全龙ComputerNetworks5:DatalinkLayerandLAN28

GbitEthernet

□usestandardEthernetframeformat

□alIowsforpoint-to-pointlinksandshared

broadcastchannels

□insharedmode,CSMA/CDisused;shortdistances

betweennodestobeefficient

□useshubs,calIedheret(BufferedDistributors"

□Full-Duplexat1Gbpsforpoint-to-pointlinks

哈工大计算机学院李全龙ComputerNetworks5:DatalinkLayerandLAN29

耳

TokenPassing:IEEE802.5standard

□4Mbps

□maxtokenholdingtime:10ms,limitingframelength

|SD|AC|屈

SD|AG|FC|destaddrsrcadd「|datachucksurn|EDFS

口SD,EDmarkstart,endofpacket

□AC:accesscontrolbyte:

otokenbit:value0meanstokencanbeseized,value1means

datafollowsFC

oprioritybits:priorityofpacket

oreservationbits:stationcanwritethesebitstoprevent

stationswithlowerprioritypacketfromseizingtoken

aftertokenbecomesfree

哈工大计算机学院李全龙ComputerNetworks5:DatalinkLayerandLAN30

TokenPassing:IEEE802.5standard

|SDIACIFE

SD|AG|FC|destaddrsrcaddr|datachecksum|EDFS

□FC:framecontrolusedformonitoringand

maintenance

□source,destinationaddress:48bitphysical

address,asinEthernet

□data:packetfromnetworklayer

□checksum:CRC

□FS:framestatus:setbydestreadbysender

osettoindicatedestinationup,framecopiedOKfromring

oDLC-levelACKing

哈工大计算机学院李全龙ComputerNetworks5:DatalinkLayerandLAN31

InterconnectingLANs

Q:WhynotjustonebigLAN?

□Limitedamountofsupportabletraffic:onsingle

LAN,allstationsmustsharebandwidth

□limitedlength:802.3specifiesmaximumcable

length

□large''collisiondomain,5(cancollidewithmany

stations)

□limitednumberofstations:802.5havetoken

passingdelaysateachstation

哈工大计算机学院李全龙ComputerNetworks5:DatalinkLayerandLAN32

耳

Hubs

aPhysicalLayerdevices:essentiallyrepeaters

operatingatbitlevels:repeatreceivedbitsonone

interfacetoallotherinterfaces

□Hubscanbearrangedinahierarchy(ormulti-tier

design),withbackbonehubatitstop

哈工大计算机学院李全龙ComputerNetworks5:DatalinkLayerandLAN33

Hubs(more)

□EachconnectedLANreferredtoasLANsegment

□Hubsdonotisolatecollisiondomains:nodemaycollide

withanynoderesidingatanysegmentinLAN

□HubAdvantages:

osimple,inexpensivedevice

oMulti-tierprovidesgracefuldegradation:portions

oftheLANcontinuetooperateifonehub

malfunctions

oextendsmaximumdistancebetweennodepairs

(100mperHub)

哈工大计算机学院李全龙ComputerNetworks5:DatalinkLayerandLAN34

Hublimitations

□singlecollisiondomainresultsinnoincreaseinmax

throughput

omulti-tierthroughputsameassinglesegment

throughput

□individualLANrestrictionsposelimitsonnumber

ofnodesinsamecollisiondomainandontotal

alIowedgeographicalcoverage

□cannotconnectdifferentEthernettypes(e.g.,

10BaseTand100baseT)

哈工大计算机学院李全龙ComputerNetworks5:DatalinkLayerandLAN35

Bridges

口LinkLayerdevices:operateonEthernet

frames,examiningframeheaderand

selectivelyforwardingframebasedonits

destination

口Bridgeisolatescollisiondomainssinceit

buffersframes

nWhenframeistobeforwardedon

segment,bridgeusesCSMA/CDtoaccess

segmentandtransmit

哈工大计算机学院李全龙ComputerNetworks5:DatalinkLayerandLAN36

Bridges(more)

口Bridgeadvantages:

oIsolatescollisiondomainsresultinginhigher

totalmaxthroughput,anddoesnotlimitthe

numberofnodesnorgeographicalcoverage

oCanconnectdifferenttypeEthernetsinceitis

astoreandforwarddevice

oTransparent:noneedforanychangetohosts

LANadapters

哈工大计算机学院李全龙ComputerNetworks5:DatalinkLayerandLAN37

耳

Bridges:framefiltering,forwarding

□bridgesfilterpackets

osame-LAN-segmentframesnotforwardedonto

otherLANsegments

□forwarding:

ohowtoknowwhichLANsegmentonwhichto

forwardframe?

olookslikearoutingproblem(moreshortly!)

哈工大计算机学院李全龙ComputerNetworks5:DatalinkLayerandLAN38

品t;・工・')

BackboneBridge

哈工大计算机学院李全龙ComputerNetworks5:DatalinkLayerandLAN39

InterconnectionWithoutBackbone

nNotrecommendedfortworeasons:

-singlepointoffailureatComputerSciencehub

-alltrafficbetweenEEandSEmustpathover

CSsegment

哈工大计算机学院李全龙ComputerNetworks5:DatalinkLayerandLAN40

BridgeFiltering

□bridgeslearnwhichhostscanbereachedthrough

whichinterfaces:maintainfilteringtables

owhenframereceived,bridgeNearns55locationof

sender:incomingLANsegment

orecordssenderlocationinfilteringtable

□filteringtableentry:

o(NodeLANAddress,BridgeInterface,TimeStamp)

ostaleentriesinFilteringTabledropped(TTLcanbe

60minutes)

哈工大计算机学院李全龙ComputerNetworks5:DatalinkLayerandLAN41

耳

BridgeFiltering

□filteringprocedure:

ifdestinationisonLANonwhichframewasreceived

thendroptheframe

else{lookupfilteringtable

ifentryfoundfordestination

thenforwardtheframeoninterfaceindicated;

elseflood;/*forwardonallbuttheinterface

onwhichtheframe

arrived*/

)

哈工大计算机学院李全龙ComputerNetworks5:DatalinkLayerandLAN42

BridgeLearning:example

SupposeCsendsframetoDandDrepliesbackwith

frametoC

0■-Q9

-©addressport

31

•12

♦——bridge-1

2

6-i3

3