《计算机网络：Chapter 5 Link Layer and LANs》由会员分享，可在线阅读，更多相关《计算机网络：Chapter 5 Link Layer and LANs（104页珍藏版）》请在金锄头文库上搜索。
1、4-1Chapter 5Link Layer and LANs5: DataLink Layer5-2Reading Assignment: Chapter 55: DataLink Layer5-3Chapter 5: The Data Link LayerOur goals: runderstand principles behind data link layer services:merror detection, correctionmsharing a broadcast channel: multiple accessmlink layer addressingmreliable
2、 data transfer, flow control: done!rinstantiation and implementation of various link layer technologies5: DataLink Layer5-4Link 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 PPPr
3、5.8 Link virtualization: ATM, MPLS5: DataLink Layer5-5Link 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 datagramdata-link
4、layer has responsibility of transferring datagram from one node to adjacent node over a link5: DataLink Layer5-6Link layer: contextrdatagram transferred by different link protocols over different links:me.g., Ethernet on first link, frame relay on intermediate links, 802.11 on last linkreach link pr
5、otocol provides different servicesme.g., may or may not provide rdt over linktransportation analogyrtrip from Guangzhou to Beijingmlimo: Guangzhou to CANmplane: CAN to PEKmTaxi: PEK to Hotelrtourist = datagramrtransport segment = communication linkrtransportation mode = link layer protocolrtravel ag
6、ent = routing algorithm5: DataLink Layer5-7Link Layer Servicesrframing, link access: mencapsulate datagram into frame, adding header, trailermchannel access if shared mediumm“MAC” addresses used in frame headers to identify source, dest different from IP address!rreliable delivery between adjacent n
7、odesmwe learned how to do this already (chapter 3)!mseldom used on low bit-error link (fiber, some twisted pair)mwireless links: high error ratesQ: why both link-level and end-end reliability?5: DataLink Layer5-8Link Layer Services (more)rflow control: mpacing between adjacent sending and receiving
8、nodesrerror detection: merrors caused by signal attenuation, noise. mreceiver detects presence of errors: signals sender for retransmission or drops frame rerror correction: mreceiver identifies and corrects bit error(s) without resorting to retransmissionrhalf-duplex and full-duplexmwith half duple
9、x, nodes at both ends of link can transmit, but not at same time5: DataLink Layer5-9Where is the link layer implemented?rin each and every hostrlink layer implemented in “adaptor” (aka network interface card NIC)mEthernet card, PCMCI card, 802.11 cardmimplements link, physical layerrattaches into ho
10、sts system busesrcombination of hardware, software, firmwarecontrollerphysicaltransmissioncpumemoryhost bus (e.g., PCI)network adaptercardhost schematicapplicationtransportnetworklinklinkphysical5: DataLink Layer5-10Adaptors Communicatingrsending side:mencapsulates datagram in framemadds error check
11、ing bits, rdt, flow control, etc.rreceiving sidemlooks for errors, rdt, flow control, etcmextracts datagram, passes to upper layer at receiving sidecontrollercontrollersending hostreceiving hostdatagramdatagramdatagramframe5: DataLink Layer5-11Link Layerr5.1 Introduction and servicesr5.2 Error detec
12、tion 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-12Error DetectionEDC= Error Detection and Correction bits (redundancy)D = Data protected by error checking, may include header
13、 fields Error detection not 100% reliable! protocol may miss some errors, but rarely larger EDC field yields better detection and correctionotherwise5: DataLink Layer5-13Parity CheckingSingle Bit Parity:Detect single bit errorsTwo Dimensional Bit Parity:Detect and correct single bit errors005: DataL
14、ink Layer5-14Internet checksum (review)Sender:rtreat segment contents as sequence of 16-bit integersrchecksum: addition (1s complement sum) of segment contentsrsender puts checksum value into UDP checksum fieldReceiver:rcompute checksum of received segmentrcheck if computed checksum equals checksum
15、field value:mNO - error detectedmYES - no error detected. But maybe errors nonetheless? Goal: detect “errors” (e.g., flipped bits) in transmitted packet (note: used at transport layer only)5: DataLink Layer5-15Checksumming: Cyclic Redundancy Checkrview data bits, D, as a binary numberrchoose r+1 bit
16、 pattern (generator), G rgoal: choose r CRC bits, R, such thatm exactly 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 (Ethernet, 802.11 WiFi, ATM)5: DataLink Layer5-16CRC Exampl
17、eWant:D.2r XOR R = nGequivalently:D.2r = nG XOR R equivalently: if we divide D.2r by G, want remainder RR = remainder D.2rG5: DataLink Layer5-17Link Layerr5.1 Introduction and servicesr5.2 Error detection and correction r5.3Multiple access protocolsr5.4 Link-layer Addressingr5.5 Ethernetr5.6 Link-la
18、yer switchesr5.7 PPPr5.8 Link Virtualization: ATM, MPLS5: DataLink Layer5-18Multiple Access Links and ProtocolsTwo types of “links”:rpoint-to-pointmPPP for dial-up accessmpoint-to-point link between Ethernet switch and hostrbroadcast (shared wire or medium)mold-fashioned Ethernetmupstream HFCm802.11
19、 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-19Multiple Access protocolsrsingle shared broadcast channel rtwo or more simultaneous transmissions by nodes: interference mcollision
20、 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 transmitrcommunication about channel sharing must use channel itself! mno out-of-band channel for coordination5: DataLink Layer5
21、-20Ideal Multiple Access ProtocolBroadcast channel of rate R bps1. when one node wants to transmit, it can send at rate R.2. when M nodes want to transmit, each can send at average rate R/M3. fully decentralized:mno special node to coordinate transmissionsmno synchronization of clocks, slots4. simpl
22、e5: DataLink Layer5-21MAC 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
23、 turns, but nodes with more to send can take longer turns5: DataLink Layer5-22Channel 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-statio
24、n LAN, 1,3,4 have pkt, slots 2,5,6 idle 1341346-slotframe5: DataLink Layer5-23Channel 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
25、 rexample: 6-station LAN, 1,3,4 have pkt, frequency bands 2,5,6 idle frequency bandstimeFDM cable5: DataLink Layer5-24Random 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 acc
26、ess MAC protocol specifies: mhow to detect collisionsmhow to recover from collisions (e.g., via delayed retransmissions)rExamples of random access MAC protocols:mslotted ALOHAmALOHAmCSMA, CSMA/CD, CSMA/CA5: DataLink Layer5-25Slotted ALOHAAssumptions:rall frames same sizertime divided into equal size
27、 slots (time to transmit 1 frame)rnodes start to transmit only slot beginning rnodes are synchronizedrif 2 or more nodes transmit in slot, all nodes detect collisionOperation:rwhen node obtains fresh frame, transmits in next slotmif no collision: node can send new frame in next slotmif collision: no
28、de retransmits frame in each subsequent slot with prob. p until success5: DataLink Layer5-26Slotted ALOHAProsrsingle active node can continuously transmit at full rate of channelrhighly decentralized: only slots in nodes need to be in syncrsimpleConsrcollisions, wasting slotsridle slotsrnodes may be
29、 able to detect collision in less than time to transmit packetrclock synchronization5: DataLink Layer5-27Slotted Aloha efficiencyrsuppose: N nodes with many frames to send, each transmits in slot with probability prprob that given node has success in a slot = p(1-p)N-1rprob that any node has a succe
30、ss = Np(1-p)N-1 rmax efficiency: find p* that maximizes Np(1-p)N-1rfor many nodes, take limit of Np*(1-p*)N-1 as N goes to infinity, gives:Max efficiency = 1/e = .37Efficiency : long-run fraction of successful slots (many nodes, all with many frames to send)At best: channelused for useful transmissi
31、ons 37%of time!5: DataLink Layer5-28Pure (unslotted) ALOHArunslotted Aloha: simpler, no synchronizationrwhen frame first arrivesm transmit immediately rcollision probability increases:mframe sent at t0 collides with other frames sent in t0-1,t0+15: DataLink Layer5-29Pure Aloha efficiencyP(success by
32、 given node) = P(node transmits) . P(no other node transmits in p0-1,p0 . P(no other node transmits in p0-1,p0 = p . (1-p)N-1 . (1-p)N-1 = p . (1-p)2(N-1) choosing optimum p and then letting n - infty . = 1/(2e) = .18 even worse than slotted Aloha!5: DataLink Layer5-30CSMA (Carrier Sense Multiple Ac
33、cess)CSMA: listen before transmit:If channel sensed idle: transmit entire framerIf channel sensed busy, defer transmission rhuman analogy: dont interrupt others!5: DataLink Layer5-31CSMA collisionscollisions can still occur:propagation delay means two nodes may not heareach others transmissioncollis
34、ion:entire packet transmission time wastedspatial layout of nodes note:role of distance & propagation delay in determining collision probability5: DataLink Layer5-32CSMA/CD (Collision Detection)CSMA/CD: carrier sensing, deferral as in CSMAmcollisions detected within short timemcolliding transmission
35、s aborted, reducing channel wastage rcollision detection: measy in wired LANs: measure signal strengths, compare transmitted, received signalsmdifficult in wireless LANs: received signal strength overwhelmed by local transmission strength rhuman analogy: the polite conversationalist 5: DataLink Laye
36、r5-33CSMA/CD collision detection5: DataLink Layer5-34“Taking Turns” MAC protocolschannel partitioning MAC protocols:mshare channel efficiently and fairly at high loadminefficient at low load: delay in channel access, 1/N bandwidth allocated even if only 1 active node! Random access MAC protocolsmeff
37、icient at low load: single node can fully utilize channelmhigh load: collision overhead“taking turns” protocolslook for best of both worlds!5: DataLink Layer5-35“Taking Turns” MAC protocolsPolling: rmaster node “invites” slave nodes to transmit in turnrtypically used with “dumb” slave devicesrconcer
38、ns:mpolling overhead mlatencymsingle point of failure (master)masterslavespolldatadata5: DataLink Layer5-36“Taking Turns” MAC protocolsToken passing:rcontrol token passed from one node to next sequentially.rtoken messagerconcerns:mtoken overhead mlatencymsingle point of failure (token) Tdata(nothing
39、to send)T5: DataLink Layer5-37 Summary of MAC protocolsrchannel partitioning, by time, frequency or codemTime Division, Frequency Divisionrrandom access (dynamic), mALOHA, S-ALOHA, CSMA, CSMA/CDmcarrier sensing: easy in some technologies (wire), hard in others (wireless)mCSMA/CD used in EthernetmCSM
40、A/CA used in 802.11rtaking turnsmpolling from central site, token passingmBluetooth, FDDI, IBM Token Ring 5: DataLink Layer5-38Link 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
41、PPPr5.8 Link Virtualization: ATM, MPLS5: DataLink Layer5-39MAC Addresses and ARPr32-bit IP address: mnetwork-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 (s
42、ame network)m48 bit MAC address (for most LANs) burned in NIC ROM, also sometimes software settable5: DataLink Layer5-40LAN 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
43、(wired orwireless)5: DataLink Layer5-41LAN Address (more)rMAC address allocation administered by IEEErmanufacturer buys portion of MAC address space (to assure uniqueness)ranalogy: (a) MAC address: like Social Security Number (b) IP address: like postal addressr MAC flat address portability mcan mov
44、e LAN card from one LAN to anotherrIP hierarchical address NOT portablem address depends on IP subnet to which node is attached5: DataLink Layer5-42ARP: Address Resolution ProtocolrEach IP node (host, router) on LAN has ARP tablerARP table: IP/MAC address mappings for some LAN nodes m TTL (Time To L
45、ive): 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 LAN137.196.7.23137.196.7.78137.196.7.14137.196.7.885: DataLink Layer5-43ARP protocol: Same L
46、AN (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 ARP query rB receives ARP packet, replies to A with its (Bs) MAC addressmframe sent to As MAC
47、address (unicast)rA caches (saves) IP-to-MAC address pair in its ARP table until information becomes old (times out) msoft state: information that times out (goes away) unless refreshedrARP is “plug-and-play”:mnodes create their ARP tables without intervention from net administrator5: DataLink Layer
48、5-44Addressing: 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 R assume A knows Bs IP a
49、ddressrtwo ARP tables in router R, one for each IP network (LAN)5: DataLink Layer5-45rA 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 datagramrAs NIC sends frame
50、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.112111.111.111.111A74-29-9
51、C-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-46Link Layerr5.1 Introduction and servicesr5.2 Error detection and correction r5.3Multiple access protocolsr5.4 Link-Layer Addressingr5.5 Ethernetr5
52、.6 Link-layer switchesr5.7 PPPr5.8 Link Virtualization: ATM and MPLS5: DataLink Layer5-47Ethernet“dominant” wired LAN technology: rcheap $20 for NICrfirst widely used LAN technologyrsimpler, cheaper than token LANs and ATMrkept up with speed race: 10 Mbps 10 Gbps Metcalfes Ethernetsketch5: DataLink
53、Layer5-48Star topologyrbus topology popular through mid 90small nodes in same collision domain (can collide with each other)rtoday: star topology prevailsmactive switch in centermeach “spoke” runs a (separate) Ethernet protocol (nodes do not collide with each other)switchbus: coaxial cablestar5: Dat
54、aLink Layer5-49Ethernet Frame StructureSending adapter encapsulates IP datagram (or other network layer protocol packet) in Ethernet framePreamble: r7 bytes with pattern 10101010 followed by one byte with pattern 10101011r used to synchronize receiver, sender clock rates5: DataLink Layer5-50Ethernet
55、 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 protocolmotherwise, adapter discards framerType: indicates higher layer protocol (mostly IP but others possible,
56、 e.g., Novell IPX, AppleTalk)rCRC: checked at receiver, if error is detected, frame is dropped5: DataLink Layer5-51Ethernet: Unreliable, connectionlessrconnectionless: No handshaking between sending and receiving NICs runreliable: receiving NIC doesnt send acks or nacks to sending NICmstream of data
57、grams 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: DataLink Layer5-52Ethernet CSMA/CD algorithm1. NIC receives datagram from network layer, creates frame2. If NIC senses chan
58、nel idle, starts frame transmission If NIC senses channel busy, waits until channel idle, then transmits3. If NIC transmits entire frame without detecting another transmission, NIC is done with frame !4. If NIC detects another transmission while transmitting, aborts and sends jam signal5. After abor
59、ting, NIC enters exponential backoff: after mth collision, NIC chooses K at random from 0,1,2,2m-1. NIC waits K512 bit times, returns to Step 2 5: DataLink Layer5-53Ethernets CSMA/CD (more)Jam Signal: make sure all other transmitters are aware of collision; 48 bitsBit time: .1 microsec for 10 Mbps E
60、thernet ;for K=1023, wait time is about 50 msec Exponential Backoff: rGoal: adapt retransmission attempts to estimated current loadmheavy load: random wait will be longerrfirst collision: choose K from 0,1; delay is K 512 bit transmission timesrafter second collision: choose K from 0,1,2,3rafter ten
61、 collisions, choose K from 0,1,2,3,4,1023See/interact with Javaapplet on AWL Web site:highly recommended !5: DataLink Layer5-54CSMA/CD efficiencyrTprop = max prop delay between 2 nodes in LANrttrans = time to transmit max-size framerefficiency goes to 1 mas tprop goes to 0mas ttrans goes to infinity
62、rbetter performance than ALOHA: and simple, cheap, decentralized!5: DataLink Layer5-55802.3 Ethernet Standards: Link & Physical Layersrmany different Ethernet standardsmcommon MAC protocol and frame formatmdifferent speeds: 2 Mbps, 10 Mbps, 100 Mbps, 1Gbps, 10G bpsmdifferent physical layer media: fi
63、ber, cableapplicationtransportnetworklinkphysicalMAC protocoland frame format100BASE-TX100BASE-T4100BASE-FX100BASE-T2100BASE-SX100BASE-BXfiber physical layercopper (twisterpair) physical layer5: DataLink Layer5-56Manchester encodingrused in 10BaseTreach bit has a transitionrallows clocks in sending
64、and receiving nodes to synchronize to each othermno need for a centralized, global clock among nodes!rHey, this is physical-layer stuff!5: DataLink Layer5-57Link Layerr5.1 Introduction and servicesr5.2 Error detection and correction r5.3 Multiple access protocolsr5.4 Link-layer Addressingr5.5 Ethern
65、etr5.6 Link-layer switchesr5.7 PPPr5.8 Link Virtualization: ATM, MPLS5: DataLink Layer5-58Hubs physical-layer (“dumb”) repeaters: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
66、 collisionstwisted pairhub5: DataLink Layer5-59Switchrlink-layer device: smarter than hubs, take active rolemstore, forward 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 se
67、gmentrtransparentmhosts are unaware of presence of switchesrplug-and-play, self-learningmswitches do not need to be configured5: DataLink Layer5-60Switch: allows multiple simultaneous transmissionsrhosts have dedicated, direct connection to switchrswitches buffer packetsrEthernet protocol used on ea
68、ch incoming link, but no collisions; full duplexmeach link is its own collision domainrswitching: A-to-A and B-to-B simultaneously, without collisions mnot possible with dumb hubAABBCCswitch with six interfaces(1,2,3,4,5,6) 1234565: DataLink Layer5-61Switch TablerQ: how does switch know that A reach
69、able via interface 4, B reachable via interface 5?rA: each switch has a switch table, each entry:m(MAC address of host, interface 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 in
70、terfaces(1,2,3,4,5,6) 1234565: DataLink Layer5-62Switch: self-learningrswitch learns which hosts can be reached through which interfacesmwhen frame received, switch “learns” location of sender: incoming LAN segmentmrecords sender/location pair in switch tableAABBCC123456A ASource: ADest: AMAC addr i
71、nterface TTLSwitch table (initially empty)A1605: DataLink Layer5-63Switch: frame filtering/forwardingWhen frame received: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
72、 the frame else forward the frame on interface indicated else flood forward on all but the interface on which the frame arrived5: DataLink Layer5-64Self-learning, forwarding: exampleAABBCC123456A ASource: ADest: AMAC addr interface TTLSwitch table (initially empty)A160A AA AA AA AA Arframe destinati
73、on unknown:floodA Ardestination A location known:A460selective send5: DataLink Layer5-65Interconnecting switchesrswitches can be connected togetherABrQ: sending from A to G - how does S1 know to forward frame destined to F via S4 and S3?rA: self learning! (works exactly the same as in single-switch
74、case!)S1CDEFS2S4S3HIG5: DataLink Layer5-66Self-learning multi-switch exampleSuppose C sends frame to I, I responds to CrQ: show switch tables and packet forwarding in S1, S2, S3, S4 ABS1CDEFS2S4S3HIG125: DataLink Layer5-67Institutional networkto externalnetworkrouterIP subnetmail serverweb server5:
75、DataLink Layer5-68Switches 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 tables, implement filtering, learning algorithms
76、 5: DataLink Layer5-69Link 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 PPPr5.8 Link Virtualization: ATM5: DataLink Layer5-70Point to Point Data Link Controlrone sender, one recei
77、ver, 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 control (Data link used to be considered “high layer” in protocol stack!5
78、: DataLink Layer5-71PPP 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) at same timemability to demultiplex upwardsrbit transparency: must carry any bit pattern in the data f
79、ieldrerror detection (no correction)rconnection liveness: detect, signal link failure to network layerrnetwork layer address negotiation: endpoint can learn/configure each others network address5: DataLink Layer5-72PPP non-requirementsrno error correction/recoveryrno flow controlrout of order delive
80、ry OK rno need to support multipoint links (e.g., polling)Error recovery, flow control, data re-ordering all relegated to higher layers!5: DataLink Layer5-73PPP Data FramerFlag: delimiter (framing)rAddress: does nothing (only one option)rControl: does nothing; in the future possible multiple control
81、 fieldsrProtocol: upper layer protocol to which frame delivered (eg, PPP-LCP, IP, IPCP, etc) 5: DataLink Layer5-74PPP Data Framerinfo: upper layer data being carriedrcheck: cyclic redundancy check for error detection5: DataLink Layer5-75Byte Stuffingr “data transparency” requirement: data field must
82、 be allowed to include flag pattern mQ: is received data or flag?rSender: adds (“stuffs”) extra byte after each data byterReceiver: mtwo 01111110 bytes in a row: discard first byte, continue data receptionmsingle 01111110: flag byte5: DataLink Layer5-76Byte Stuffingflag bytepatternin datato sendflag
83、 byte pattern plusstuffed byte in transmitted data5: DataLink Layer5-77PPP Data Control ProtocolBefore exchanging network-layer data, data link peers mustrconfigure PPP link (max. frame length, authentication)rlearn/configure network layer informationmfor IP: carry IP Control Protocol (IPCP) msgs (p
84、rotocol field: 8021) to configure/learn IP address5: DataLink Layer5-78Link 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 PPPr5.8 Link Virtualization: ATM and MPLS5: DataLink Layer
85、5-79Virtualization of networksVirtualization of resources: powerful abstraction in systems engineering:rcomputing examples: virtual memory, virtual devicesmVirtual machines: e.g., javamIBM VM os from 1960s/70srlayering of abstractions: dont sweat the details of the lower layer, only deal with lower
86、layers abstractly5: DataLink Layer5-80The Internet: virtualizing networks1974: multiple unconnected nets mARPAnetmdata-over-cable networksmpacket satellite network (Aloha)mpacket radio network differing in:maddressing conventionsmpacket formatsmerror recoverymroutingARPAnetsatellite netA Protocol fo
87、r Packet Network Intercommunication, V. Cerf, R. Kahn, IEEE Transactions on Communications, May, 1974, pp. 637-648.5: DataLink Layer5-81The Internet: virtualizing networksARPAnetsatellite netgatewayInternetwork layer (IP): raddressing: internetwork appears as single, uniform entity, despite underlyi
88、ng local network heterogeneityrnetwork of networksGateway: r“embed internetwork packets in local packet format or extract them”rroute (at internetwork level) to next gateway5: DataLink Layer5-82Cerf & Kahns Internetwork ArchitectureWhat is virtualized?rtwo layers of addressing: internetwork and loca
89、l networkrnew layer (IP) makes everything homogeneous at internetwork layerrunderlying local network technology mcablemsatellitem56K telephone modemmtoday: ATM, MPLS “invisible” at internetwork layer. Looks like a link layer technology to IP!5: DataLink Layer5-83ATM and MPLSrATM, MPLS separate netwo
90、rks in their own rightm different service models, addressing, routing from Internetrviewed by Internet as logical link connecting IP routersmjust like dialup link is really part of separate network (telephone network)rATM, MPLS: of technical interest in their own right5: DataLink Layer5-84Asynchrono
91、us Transfer Mode: ATMr1990s/00 standard for high-speed (155Mbps to 622 Mbps and higher) Broadband Integrated Service Digital Network architecturerGoal: integrated, end-end transport of carry voice, video, datammeeting timing/QoS requirements of voice, video (versus Internet best-effort model)m“next
92、generation” telephony: technical roots in telephone worldmpacket-switching (fixed length packets, called “cells”) using virtual circuits5: DataLink Layer5-85ATM architecture radaptation layer: only at edge of ATM networkmdata segmentation/reassemblymroughly analagous to Internet transport layerrATM
93、layer: “network” layermcell switching, routingrphysical layerphysicalATMAALphysicalATMAALphysicalATMphysicalATMend systemend systemswitchswitch5: DataLink Layer5-86ATM: network or link layer?Vision: end-to-end transport: “ATM from desktop to desktop”mATM is a network technologyReality: used to conne
94、ct IP backbone routers m“IP over ATM”mATM as switched link layer, connecting IP routersATMnetworkIPnetwork5: DataLink Layer5-87ATM Adaptation Layer (AAL)rATM Adaptation Layer (AAL): “adapts” upper layers (IP or native ATM applications) to ATM layer belowrAAL present only in end systems, not in switc
95、hesrAAL layer segment (header/trailer fields, data) fragmented across multiple ATM cells manalogy: TCP segment in many IP packetsphysicalATMAALphysicalATMAALphysicalATMphysicalATMend systemend systemswitchswitch5: DataLink Layer5-88ATM Adaptation Layer (AAL) moreDifferent versions of AAL layers, dep
96、ending on ATM service class:rAAL1: for CBR (Constant Bit Rate) services, e.g. circuit emulationrAAL2: for VBR (Variable Bit Rate) services, e.g., MPEG videorAAL5: for data (eg, IP datagrams)AAL PDUATM cellUser data5: DataLink Layer5-89ATM LayerService: transport cells across ATM networkranalogous to
97、 IP network layerrvery different services than IP network layerNetworkArchitectureInternetATMATMATMATMServiceModelbest effortCBRVBRABRUBRBandwidthnoneconstantrateguaranteedrateguaranteed minimumnoneLossnoyesyesnonoOrdernoyesyesyesyesTimingnoyesyesnonoCongestionfeedbackno (inferredvia loss)nocongesti
98、onnocongestionyesnoGuarantees ?5: DataLink Layer5-90ATM Layer: Virtual CircuitsrVC transport: cells carried on VC from source to destmcall setup, teardown for each call before data can flowmeach packet carries VC identifier (not destination ID)mevery switch on source-dest path maintain “state” for e
99、ach passing connectionmlink,switch resources (bandwidth, buffers) may be allocated to VC: to get circuit-like perf.rPermanent VCs (PVCs)mlong lasting connectionsmtypically: “permanent” route between to IP routersrSwitched VCs (SVC):mdynamically set up on per-call basis5: DataLink Layer5-91ATM VCsrAd
100、vantages of ATM VC approach:mQoS performance guarantee for connection mapped to VC (bandwidth, delay, delay jitter)rDrawbacks of ATM VC approach:mInefficient support of datagram trafficmone PVC between each source/dest pair) does not scale (N*2 connections needed) mSVC introduces call setup latency,
101、 processing overhead for short lived connections5: DataLink Layer5-92ATM Layer: ATM cellr5-byte ATM cell headerr48-byte payloadmWhy?: small payload - short cell-creation delay for digitized voicemhalfway between 32 and 64 (compromise!)Cell headerCell format5: DataLink Layer5-93ATM cell headerrVCI: v
102、irtual channel IDmwill change from link to link thru netrPT: Payload type (e.g. RM cell versus data cell) rCLP: Cell Loss Priority bitmCLP = 1 implies low priority cell, can be discarded if congestionrHEC: Header Error Checksummcyclic redundancy check5: DataLink Layer5-94ATM Physical Layer (more)Two
103、 pieces (sublayers) of physical layer:rTransmission Convergence Sublayer (TCS): adapts ATM layer above to PMD sublayer belowrPhysical Medium Dependent: depends on physical medium being usedTCS Functions:mHeader checksum generation: 8 bits CRC mCell delineationmWith “unstructured” PMD sublayer, trans
104、mission of idle cells when no data cells to send5: DataLink Layer5-95ATM Physical LayerPhysical Medium Dependent (PMD) sublayerrSONET/SDH: transmission frame structure (like a container carrying bits); mbit synchronization; mbandwidth partitions (TDM); mseveral speeds: OC3 = 155.52 Mbps; OC12 = 622.
105、08 Mbps; OC48 = 2.45 Gbps, OC192 = 9.6 GbpsrTI/T3: transmission frame structure (old telephone hierarchy): 1.5 Mbps/ 45 Mbpsrunstructured: just cells (busy/idle)5: DataLink Layer5-96IP-Over-ATMClassic IP only r3 “networks” (e.g., LAN segments)rMAC (802.3) and IP addressesIP over ATM rreplace “networ
106、k” (e.g., LAN segment) with ATM networkrATM addresses, IP addressesATMnetworkEthernetLANsEthernetLANs5: DataLink Layer5-97IP-Over-ATMAALATMphyphyEthIPATMphyATMphyapptransportIPAALATMphyapptransportIPEthphy5: DataLink Layer5-98Datagram Journey in IP-over-ATM Network rat Source Host:mIP layer maps bet
107、ween IP, ATM dest address (using ARP)mpasses datagram to AAL5mAAL5 encapsulates data, segments cells, passes to ATM layer rATM network: moves cell along VC to destinationrat Destination Host:mAAL5 reassembles cells into original datagrammif CRC OK, datagram is passed to IP5: DataLink Layer5-99IP-Ove
108、r-ATMIssues:rIP datagrams into ATM AAL5 PDUsrfrom IP addresses to ATM addressesmjust like IP addresses to 802.3 MAC addresses!ATMnetworkEthernetLANs5: DataLink Layer5-100Multiprotocol label switching (MPLS)rinitial goal: speed up IP forwarding by using fixed length label (instead of IP address) to d
109、o forwarding mborrowing ideas from Virtual Circuit (VC) approachmbut IP datagram still keeps IP address!PPP or Ethernet headerIP headerremainder of link-layer frameMPLS headerlabelExp S TTL203185: DataLink Layer5-101MPLS capable routersra.k.a. label-switched routerrforwards packets to outgoing inter
110、face based only on label value (dont inspect IP address)mMPLS forwarding table distinct from IP forwarding tablesrsignaling protocol needed to set up forwardingmRSVP-TEmforwarding possible along paths that IP alone would not allow (e.g., source-specific routing) !muse MPLS for traffic engineering rm
111、ust co-exist with IP-only routers5: DataLink Layer5-102R1R2DR3R4R50100AR6 in out outlabel label dest interface 6 - A 0 in out outlabel label dest interface10 6 A 112 9 D 0 in out outlabel label dest interface 10 A 0 12 D 01 in out outlabel label dest interface 8 6 A 00 8 A 1MPLS forwarding tables5:
112、DataLink Layer5-103Chapter 5: Summaryr principles behind data link layer services:merror detection, correctionmsharing a broadcast channel: multiple accessmlink layer addressingrinstantiation and implementation of various link layer technologiesmEthernetmswitched LANSmPPPmvirtualized networks as a link layer: ATM, MPLS5: DataLink Layer5-104Chapter 5: lets take a breathrjourney down protocol stack complete (except PHY)rsolid understanding of networking principles, practicer. could stop here . but lots of interesting topics!mwirelessmmultimediamsecurity mnetwork management
