大二下复习计算机网络课件chapter

1、5: DataLink Layer5-1Chapter 5Link Layer and LANsComputer Networking: A Top Down Approach 4th edition. Jim Kurose, Keith RossAddison-Wesley, July 2007. 5: DataLink Layer5-2Link Layerr5.1 Introduction and servicesr5.2 Error detection and correction r5.3Multiple access protocolsr5.4 Link-layer Addressi

2、ngr5.5 Ethernetr5.6 Link-layer switchesr5.7 PPP5: DataLink Layer5-3Link Layer: IntroductionSome terminology:rhosts and routers are nodesrcommunication channels that connect adjacent nodes along communication path are linksmwired linksmwireless linksmLANsrlayer-2 packet is a frame, encapsulates datag

3、ramdata-link layer has responsibility of transferring datagram from one node to adjacent node over a link5: DataLink Layer5-4Link Layer Servicesrframing, link access: mencapsulate datagram into frame, adding header, trailermchannel access if shared mediumm“MAC” addresses used in frame headers to ide

4、ntify source, dest different from IP address!rreliable delivery between adjacent nodesmwe learned how to do this already (chapter 3)!mseldom used on low bit-error link (fiber, some twisted pair)mwireless links: high error rates5: DataLink Layer5-5Link Layer Services (more)rflow control: mpacing betw

5、een adjacent sending and receiving nodesrerror detection: merrors caused by signal attenuation, noise. mreceiver detects presence of errors: rerror correction: mreceiver identifies and corrects bit error(s) without resorting to retransmissionrhalf-duplex and full-duplexmwith half duplex, nodes at bo

6、th ends of link can transmit, but not at same time5: DataLink Layer5-6Where is the link layer implemented?rin each router and every hostrlink layer implemented in “adaptor” (aka network interface card NIC)me.g. Ethernet cardmimplements link, physical layerrattaches into hosts system busesrcombinatio

7、n of hardware, software, firmwarecontrollerphysicaltransmissioncpumemoryhost bus (e.g., PCI)network adaptercardhost schematicapplicationtransportnetworklinklinkphysical5: DataLink Layer5-7Adaptors Communicatingrsending side:mencapsulates datagram in framemadds error checking bits, rdt, flow control,

8、 etc.rreceiving sidemlooks for errors, rdt, flow control, etcmextracts datagram, passes to upper layer at receiving sidecontrollercontrollersending hostreceiving hostdatagramdatagramdatagramframe5: DataLink Layer5-8Link Layerr5.1 Introduction and servicesr5.2 Error detection and correction r5.3Multi

9、ple access protocolsr5.4 Link-layer Addressingr5.5 Ethernetr5.6 Link-layer switchesr5.7 PPPr5.8 Link Virtualization: ATM. MPLS5: DataLink Layer5-9Error DetectionEDC= Error Detection and Correction bits (redundancy)D = Data protected by error checking, may include header fields Error detection not 10

10、0% reliable! protocol may miss some errors, but rarely larger EDC field yields better detection and correctionotherwise5: DataLink Layer5-10Checksumming: Cyclic Redundancy Checkrview data bits, D, as a binary numberrchoose r+1 bit pattern (generator), G rgoal: choose r CRC bits, R, such thatm exactl

11、y divisible by G (modulo 2) mreceiver knows G, divides by G. If non-zero remainder: error detected!mcan detect all burst errors less than r+1 bitsrwidely used in practice (802.11 WiFi, ATM)5: DataLink Layer5-11CRC Example5: DataLink Layer5-12Link Layerr5.1 Introduction and servicesr5.2 Error detecti

12、on and correction r5.3Multiple access protocolsr5.4 Link-layer Addressingr5.5 Ethernetr5.6 Link-layer switchesr5.7 PPPr5.8 Link Virtualization: ATM, MPLS5: DataLink Layer5-13Multiple Access Links and ProtocolsTwo types of “links”:rpoint-to-pointmPPP for dial-up accessmpoint-to-point link between Eth

13、ernet switch and hostrbroadcast (shared wire or medium)mold-fashioned Ethernetmupstream HFCm802.11 wireless LANshared wire (e.g., cabled Ethernet)shared RF (e.g., 802.11 WiFi)shared RF(satellite) humans at acocktail party (shared air, acoustical)5: DataLink Layer5-14Multiple Access protocolsrsingle

14、shared broadcast channel rtwo or more simultaneous transmissions by nodes: interference mcollision if node receives two or more signals at the same timemultiple access protocolrdistributed algorithm that determines how nodes share channel, i.e., determine when node can transmit5: DataLink Layer5-15M

15、AC Protocols: a taxonomyThree broad classes:rChannel Partitioningmdivide channel into smaller “pieces” (time slots, frequency, code)mallocate piece to node for exclusive userRandom Accessmchannel not divided, allow collisionsm“recover” from collisionsr“Taking turns”mnodes take turns, but nodes with

16、more to send can take longer turns5: DataLink Layer5-16Channel Partitioning MAC protocols: TDMATDMA: time division multiple access raccess to channel in rounds reach station gets fixed length slot (length = pkt trans time) in each round runused slots go idle rexample: 6-station LAN, 1,3,4 have pkt,

17、slots 2,5,6 idle 1341346-slotframe5: DataLink Layer5-17Channel Partitioning MAC protocols: FDMAFDMA: frequency division multiple access rchannel spectrum divided into frequency bandsreach station assigned fixed frequency bandrunused transmission time in frequency bands go idle rexample: 6-station LA

18、N, 1,3,4 have pkt, frequency bands 2,5,6 idle frequency bandstimeFDM cable5: DataLink Layer5-18Random Access ProtocolsrWhen node has packet to sendmtransmit at full channel data rate R.mno a priori coordination among nodesrtwo or more transmitting nodes “collision”,rrandom access MAC protocol specif

19、ies: mhow to detect collisionsmhow to recover from collisions (e.g., via delayed retransmissions)rExamples of random access MAC protocols:mALOHA and slotted ALOHAmCSMA, CSMA/CD, CSMA/CA5: DataLink Layer5-19collisions can still occur:propagation delay means two nodes may not heareach others transmiss

20、ioncollision:entire packet transmission time wastedspatial layout of nodes note:role of distance & propagation delay in determining collision probabilityCSMA: listen before transmit:rIf channel sensed idle: transmit entire framerIf channel sensed busy, defer transmission CSMA (Carrier Sense Multiple

21、 Access)5: DataLink Layer5-20CSMA/CD (Collision Detection)CSMA/CD: carrier sensing, deferral as in CSMAmcollisions detected within short timemcolliding transmissions aborted, reducing channel wastage rCSMA/CDm先听再讲-载波监听m边讲边听进行检测检测m冲突处理-发送站检测到冲突后立即停止帧的发送，并且发一个简短的堵塞信号(称强化冲突信号，Jamming signal)，通知网上各站已经发生

22、冲突，本站及网上所有站都等待一段随机分布的时间，然后再按CSMA/CD方式重发该帧。5: DataLink Layer5-21LAN technologiesData link layer so far:mservices, error detection/correction, multiple access Next: LAN technologiesmaddressingmEthernetmswitchesmPPP5: DataLink Layer5-22 OSI/RM LANNetwork LayerData Link LayerPhysical LayerLLCMACPhysical

23、mMost of traditional LAN is medium-sharing (using broadcast channel) mNeeds not functions of route selecting,so it only has the functions of the first and second layers of OSImData link layer is divided into two sub-layers: LLC and MAC.OSI/RM & LAN MODEL(1)OSI/RM & LAN MODEL(1)5: DataLink Layer5-23r

24、 MAC( Media Access Control ): respective of transmission mediums and topologies mFraming/disassembling framemAddressingmBit error detectingmRealizing and maintain MAC protocolOSI/RM & LAN MODEL(2) OSI/RM LANNetwork LayerData Link LayerPhysical LayerLLCMACPhysical5: DataLink Layer5-24rLLC(Logical Lin

25、k Control ): irrespective of transmission mediums and topologies mEstablish and release logic connection of data link layermProvide interface to upper layermAdd sequence number to frame, flow control, error controlOSI/RM & LAN MODEL(3) OSI/RM LANNetwork LayerData Link LayerPhysical LayerLLCMACPhysic

26、al5: DataLink Layer5-25Link Layerr5.1 Introduction and servicesr5.2 Error detection and correction r5.3Multiple access protocolsr5.4 Link-Layer Addressingr5.5 Ethernetr5.6 Link-layer switchesr5.7 PPPr5.8 Link Virtualization: ATM, MPLS5: DataLink Layer5-26MAC Addresses and ARPr32-bit IP address: mnet

27、work-layer addressmused to get datagram to destination IP subnet rMAC (or LAN or physical or Ethernet) address: mfunction: get frame from one interface to another physically-connected interface (same network)m48 bit MAC address (for most LANs) burned in NIC ROM, also sometimes software settable5: Da

28、taLink Layer5-27LAN Addresses and ARPEach adapter on LAN has unique LAN addressBroadcast address =FF-FF-FF-FF-FF-FF= adapter1A-2F-BB-76-09-AD58-23-D7-FA-20-B00C-C4-11-6F-E3-9871-65-F7-2B-08-53 LAN(wired orwireless)5: DataLink Layer5-28LAN Address (more)rMAC address allocation administered by IEEErma

29、nufacturer buys portion of MAC address space (to assure uniqueness)rMAC flat address mcan move LAN card from one LAN to anotherrIP hierarchical address NOT portablem address depends on IP subnet to which node is attached5: DataLink Layer5-29ARP: Address Resolution ProtocolrEach IP node (host, router

30、) on LAN has ARP tablerARP table: IP/MAC address mappings for some LAN nodes m TTL (Time To Live): time after which address mapping will be forgotten (typically 20 min)Question: how to determineMAC address of Bknowing Bs IP address?1A-2F-BB-76-09-AD58-23-D7-FA-20-B00C-C4-11-6F-E3-9871-65-F7-2B-08-53

31、 LAN137.196.7.23137.196.7.78137.196.7.14137.196.7.885: DataLink Layer5-30ARP protocol: Same LAN (network)rA wants to send datagram to B, and Bs MAC address not in As ARP table.rA broadcasts ARP query packet, containing Bs IP address mdest MAC address = FF-FF-FF-FF-FF-FFmall machines on LAN receive A

32、RP query rB receives ARP packet, replies to A with its (Bs) MAC addressmframe sent to As MAC address (unicast)rA caches (saves) IP-to-MAC address pair in its ARP table until information becomes old (times out) rARP is “plug-and-play”:mnodes create their ARP tables without intervention from net admin

33、istrator5: DataLink Layer5-31Addressing: routing to another LANR1A-23-F9-CD-06-9B222.222.222.220111.111.111.110E6-E9-00-17-BB-4BCC-49-DE-D0-AB-7D111.111.111.112111.111.111.111A74-29-9C-E8-FF-55222.222.222.22188-B2-2F-54-1A-0FB222.222.222.22249-BD-D2-C7-56-2Awalkthrough: send datagram from A to B via

34、 R assume A knows Bs IP addressrtwo ARP tables in router R, one for each IP network (LAN)5: DataLink Layer5-32rA creates IP datagram with source A, destination B rA uses ARP to get Rs MAC address for 111.111.111.110rA creates link-layer frame with Rs MAC address as dest, frame contains A-to-B IP dat

35、agramrAs NIC sends frame rRs NIC receives frame rR removes IP datagram from Ethernet frame, sees its destined to BrR uses ARP to get Bs MAC address rR creates frame containing A-to-B IP datagram sends to BR1A-23-F9-CD-06-9B222.222.222.220111.111.111.110E6-E9-00-17-BB-4BCC-49-DE-D0-AB-7D111.111.111.1

36、12111.111.111.111A74-29-9C-E8-FF-55222.222.222.22188-B2-2F-54-1A-0FB222.222.222.22249-BD-D2-C7-56-2AThis is a really importantexample make sure youunderstand!5: DataLink Layer5-33Link Layerr5.1 Introduction and servicesr5.2 Error detection and correction r5.3Multiple access protocolsr5.4 Link-Layer

37、Addressingr5.5 Ethernetr5.6 Link-layer switchesr5.7 PPPr5.8 Link Virtualization: ATM and MPLS5: DataLink Layer5-34Star topologyrbus topology popular through mid 90small nodes in same collision domain (can collide with each other)rtoday: star topology prevailsmactive switch in centermeach “spoke” run

38、s a (separate) Ethernet protocol (nodes do not collide with each other)switchbus: coaxial cablestar5: DataLink Layer5-35Ethernet Frame StructureSending adapter encapsulates IP datagram (or other network layer protocol packet) in Ethernet framePreamble: r7 bytes with pattern 10101010 followed by one

39、byte with pattern 10101011r used to synchronize receiver, sender clock rates5: DataLink Layer5-36Ethernet Frame Structure (more)rAddresses: 6 bytesmif adapter receives frame with matching destination address, or with broadcast address (eg ARP packet), it passes data in frame to network layer protoco

40、lmotherwise, adapter discards framerType: indicates higher layer protocol (mostly IP but others possible, e.g., Novell IPX, AppleTalk)rCRC: checked at receiver, if error is detected, frame is droppedrData: 46-1500byte5: DataLink Layer5-37Ethernet: Unreliable, connectionlessrconnectionless: No handsh

41、aking between sending and receiving NICs runreliable: receiving NIC doesnt send acks or nacks to sending NICmstream of datagrams passed to network layer can have gaps (missing datagrams)mgaps will be filled if app is using TCPmotherwise, app will see gapsrEthernets MAC protocol: unslotted CSMA/CD5:

42、DataLink Layer5-38Ethernet CSMA/CD algorithm1. NIC receives datagram from network layer, creates frame2. If NIC senses channel idle, starts frame transmission If NIC senses channel busy, waits until channel idle, then transmits3. If NIC transmits entire frame without detecting another transmission,

43、NIC is done with frame !4. If NIC detects another transmission while transmitting, aborts and sends jam signal5. After aborting, NIC enters exponential backoff5: DataLink Layer5-39Ethernets CSMA/CD (more)Exponential Backoff: rGoal: adapt retransmission attempts to estimated current loadmheavy load:

44、random wait will be longerrafter mth collision, NIC chooses K at random from 0,1,2,2m-1. NIC waits K512 bit times, for example:mfirst collision: choose K from 0,1; delay is K 512 bit transmission timesmafter second collision: choose K from 0,1,2,3mafter ten collisions, choose K from 0,1,2,3,4,1023mA

45、fter sixteen collisions, abandon the transmission.5: DataLink Layer5-40Link Layerr5.1 Introduction and servicesr5.2 Error detection and correction r5.3 Multiple access protocolsr5.4 Link-layer Addressingr5.5 Ethernetr5.6 Link-layer switchesr5.7 PPP5: DataLink Layer5-41Hubs physical-layer (“dumb”) re

46、peaters:mbits coming in one link go out all other links at same ratemall nodes connected to hub can collide with one anothermno frame bufferingmno CSMA/CD at hub: host NICs detect collisionstwisted pairhub5: DataLink Layer5-42Switchrlink-layer device: smarter than hubs, take active rolemstore, forwa

47、rd Ethernet framesmexamine incoming frames MAC address, selectively forward frame to one-or-more outgoing links when frame is to be forwarded on segment, uses CSMA/CD to access segmentrtransparentmhosts are unaware of presence of switchesrplug-and-play, self-learningmswitches do not need to be confi

48、gured5: DataLink Layer5-43Switch: allows multiple simultaneous transmissionsrhosts have dedicated, direct connection to switchrswitches buffer packetsrEthernet protocol used on each incoming link, but no collisions; full duplexmeach link is its own collision domainrswitching: A-to-A and B-to-B simul

49、taneously, without collisions mnot possible with dumb hubAABBCCswitch with six interfaces(1,2,3,4,5,6) 1234565: DataLink Layer5-44Switch TablerQ: how does switch know that A reachable via interface 4, B reachable via interface 5?rA: each switch has a switch table, each entry:m(MAC address of host, i

50、nterface to reach host, time stamp)rlooks like a routing table!rQ: how are entries created, maintained in switch table? msomething like a routing protocol?AABBCCswitch with six interfaces(1,2,3,4,5,6) 1234565: DataLink Layer5-45Switch: self-learningrswitch learns which hosts can be reached through w

51、hich interfacesmwhen frame received, switch “learns” location of sender: incoming LAN segmentmrecords sender/location pair in switch tableAABBCC123456A ASource: ADest: AMAC addr interface TTLSwitch table (initially empty)A1605: DataLink Layer5-46Switch: frame filtering/forwardingWhen frame received:

52、1. record link associated with sending host2. index switch table using MAC dest address3. if entry found for destination then if dest on segment from which frame arrived then drop the frame else forward the frame on interface indicated else flood forward on all but the interface on which the frame a

53、rrived5: DataLink Layer5-47Self-learning, forwarding: exampleAABBCC123456A ASource: ADest: AMAC addr interface TTLSwitch table (initially empty)A160A AA AA AA AA Arframe destination unknown:floodA Ardestination A location known:A460selective send5: DataLink Layer5-48Institutional networkto externaln

54、etworkrouterIP subnetmail serverweb server5: DataLink Layer5-49Switches vs. Routersrboth store-and-forward devicesmrouters: network layer devices (examine network layer headers)mswitches are link layer devicesrrouters maintain routing tables, implement routing algorithmsrswitches maintain switch tab

55、les, implement filtering, learning algorithms 5: DataLink Layer5-50Summary comparison5: DataLink Layer5-51Link Layerr5.1 Introduction and servicesr5.2 Error detection and correction r5.3Multiple access protocolsr5.4 Link-Layer Addressingr5.5 Ethernetr5.6 Hubs and switchesr5.7 PPP5: DataLink Layer5-5

56、2Point to Point Data Link Controlrone sender, one receiver, one link: easier than broadcast link:mno Media Access Controlmno need for explicit MAC addressingme.g., dialup link, ISDN linerpopular point-to-point DLC protocols:mPPP (point-to-point protocol)mHDLC: High level data link control5: DataLink Layer5-53PPP Design Requirements RFC 1557rpacket framing: encapsulation of network-layer datagram in data link frame mcarry network layer data of any network layer protocol (not just IP)mability to demultiplex upwardsrbit transparency: must