3rd edition, chapter 5 – the fengs - thefengs.com

5: DataLink Layer,5-1,Chapter 5Link Layer and LANs,A note on the use of these ppt slides:Were making these slides freely available to all (faculty, students, readers). Theyre in PowerPoint form so you can add, modify, and delete slides (including this one) and slide content to suit your needs. They obviously represent a lot of work on our part. In return for use, we only ask the following: If you use these slides (e.g., in a class) in substantially unaltered form, that you mention their source (after all, wed like people to use our book!) If you post any slides in substantially unaltered form on a www site, that you note that they are adapted from (or perhaps identical to) our slides, and note our copyright of this material.Thanks and enjoy! JFK/KWRAll material copyright 1996-2007J.F Kurose and K.W. Ross, All Rights Reserved,Computer Networking: A Top Down Approach 4th edition. Jim Kurose, Keith RossAddison-Wesley, July 2007.,5: DataLink Layer,5-2,Chapter 5: The Data Link Layer,Our goals: understand principles behind data link layer services:error detection, correctionsharing a broadcast channel: multiple accesslink layer addressingreliable data transfer, flow control: done!instantiation and implementation of various link layer technologies,5: DataLink Layer,5-3,Link Layer,5.1 Introduction and services5.2 Error detection and correction 5.3Multiple access protocols5.4 Link-Layer Addressing5.5 Ethernet and other data link layers,5.6 Hubs and switches5.7 PPP5.8 Link Virtualization: ATM and MPLS,5: DataLink Layer,5-4,Link Layer: Introduction,Some terminology:hosts and routers are nodescommunication channels that connect adjacent nodes along communication path are linkswired linkswireless linksLANslayer-2 packet is a frame, encapsulates datagram,data-link layer has responsibility of transferring datagram from one node to adjacent node over a link,5: DataLink Layer,5-5,Adaptors Communicating,link and physical layers implemented in adaptor/NIC (Network Interface Card)RAM, DSP chips, host bus interface, and link interfaceEthernet card, PCMCIA card, 802.11 cardsending side:encapsulates datagram in a frameadds error checking bits, rdt, flow control, etc.,receiving sidelooks for errors, rdt, flow control, etcextracts datagram, passes to upper layer at receiving sidedatagram transferred by different link protocols over different links:e.g., Ethernet on first link, frame relay on intermediate links, 802.11 on last link,sendingnode,rcvingnode,datagram,adapter,adapter,link layer protocol,5: DataLink Layer,5-6,Protocol stack picture,networklinkphysical,frame,phys. link,data linkprotocol,adapter card,5: DataLink Layer,5-7,Host adaptor,5: DataLink Layer,5-8,Link Layer Functions,Flow Controlpacing between adjacent sending and receiving nodesReliable delivery between adjacent nodeswe learned how to do this already (chapter 3)!seldom used on low bit error link (i.e. fiber, twisted pair)wireless links: high error ratesEschew end-to-end principle for performanceSecurityDemux to upper protocolFramingencapsulate datagram into frame, adding header, trailer,5: DataLink Layer,5-9,Link Layer Functions (more),Error Detectionerrors caused by signal attenuation, noise. receiver detects presence of errors: signals sender for retransmission or drops frame Error Correctionreceiver identifies and corrects bit error(s) without resorting to retransmissionMedium access and quality of servicechannel access if shared mediumAddressing“MAC” addresses used in frame headers to identify source, dest (different from IP address),5: DataLink Layer,5-10,Flow control,Pacing between sender and receiverSender prevented from overrunning receiverReady-To-Send, Clear-To-Send signalling,5: DataLink Layer,5-11,Reliable delivery,Reliability at the link layerHandled in a similar manner to transport protocolsARQ, Stop-and-wait, Go-back-N, Selective RepeatWhen and why should this be used? Rarely done over twisted-pair or fiber optic linksUsually done over lossy links for performance improvement (versus correctness),5: DataLink Layer,5-12,Security,Mainly for broadcast data-link layersEncrypt payload of higher layersHide IP source/destination from eavesdroppersImportant for wireless LANs especiallyParking lot attacks with 802.11bWEP, WPAIf time permits, security will be covered at the end of the course.,5: DataLink Layer,5-13,Demux to upper protocol,Protocol type specification interfaces to network layerData-link layer can support any number of network layersType field in data-link header specifies network layer of packetEach data-link layer defines its own protocol type numbering for network layerIP is one of many network layers,5: DataLink Layer,5-14,Demux to upper protocol,/CaveBear/Ethernet/type.htmlSome Ethernet protocol types0800 DOD Internet Protocol (IP) 0806 Address Resolution Protocol (ARP)8037 IPX (Novell Netware) 80D5 IBM SNA Services809B EtherTalk (AppleTalk over Ethernet),5: DataLink Layer,5-15,Framing,Data encapsulation for transmission over physical linkData embedded within a link-layer frame before transmissionData-link header and/or trailer addedPhysical addresses used in frame headers to identify source and destination (not IP),5: DataLink Layer,5-16,Fixed length framing,Length delimitedBeginning of frame has lengthSingle corrupt length can cause problemsMust have start of frame character to resynchronizeResynchronization can fail if start of frame character is inside packets as well,5: DataLink Layer,5-17,Variable length framing,Byte stuffingSpecial start of frame byte (e.g. 0xFF)Special escape byte value (e.g. 0xFE)Values actually in text are replaced (e.g. 0xFF by 0xFEFF and 0xFE by 0xFEFE)Worst case can double the size of frameBit stuffingSpecial bit sequence (0x01111110)0 bit stuffed after any 11111 sequence,5: DataLink Layer,5-18,Clock-Based Framing,Used by SONETFixed size frames (810 bytes)Look for start of frame marker that appears every 810 bytesWill eventually sync up,5: DataLink Layer,5-19,Link Layer,5.1 Introduction and services5.2 Error detection and correction 5.3Multiple access protocols5.4 Link-Layer Addressing5.5 Ethernet and other data link layers,5.6 Hubs and switches5.7 PPP5.8 Link Virtualization: ATM,5: DataLink Layer,5-20,Error detection/correction,Errors caused by signal attenuation, noise. Receiver detects presence of errorsPossible actionsSignal sender for retransmissionDrops frameCorrect bit errors if possible and continue,5: DataLink Layer,5-21,Error Detection,EDC= Error Detection and Correction bits (redundancy)D = Data protected by error checking, may include header fields Error detection not 100% reliable! protocol may miss some errors, but rarely larger EDC field yields better detection and correction,5: DataLink Layer,5-22,Parity Checking,Single Bit Parity:Detect single bit errors,Two Dimensional Bit Parity:Detect and correct single bit errors,0,0,5: DataLink Layer,5-23,Cyclic Redundancy Check (CRC),Polynomial codeTreat data bits as coefficients of n-bit polynomialChoose r+1 bit generator polynomial GG well known chosen in advanceAdd r bits to packet so that message is divisible by GAt receiver, divide payload by generator polynomialIf result not zero, error detectedBetter loss detection properties than checksumsAll single bit errors, all double bit errors, all odd-numbered errors, burst errors less than rWidely used in practice (802.11, WiFi, ATM, SCTP),5: DataLink Layer,5-24,Cyclic Redundancy Check (CRC),Calculate code using modulo 2 division of data by generator polynomialSubtraction equivalent to XORWeak definition of magnitudeX = Y iff position of highest 1 bit of X is the same or greater than the highest 1 bit of YRecord remainder “R” after division and attach “R” after dataResult divisible by generator polynomial,5: DataLink Layer,5-25,Cyclic Redundancy Check (CRC),5: DataLink Layer,5-26,CRC example,Data:101110Generator Polynomial:x3 + 1 (1001) Send: 101110011,5: DataLink Layer,5-27,CRC example,Data:10000Generator Polynomial:x2 + 1 (101) Send:,101 1000000,G,5: DataLink Layer,5-28,CRC example,Data:10000Generator Polynomial:x2 + 1 (101) Send: 1000001,101 1000000 101 010 000 100 101 010 000 100 101 01,101,D,G,R,5: DataLink Layer,5-29,Cyclic Redundancy Check (CRC),CRC-16 implementationShift register and XOR gates,5: DataLink Layer,5-30,CRC polynomials,CRC-16 = x16 + x15 + x2+ 1 (used in HDLC) CRC-CCITT = x16 + x12 + x5 + 1 CRC-32 = x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x + 1 (used in Ethernet),5: DataLink Layer,5-31,Forward error correction,FECUse error correcting codes to repair lossesAdd redundant information which allows receiver to correct bit errorsSee information and coding theory work.,5: DataLink Layer,5-32,Link Layer,5.1 Introduction and services5.2 Error detection and correction 5.3Multiple access protocols5.4 Link-Layer Addressing5.5 Ethernet and other data link layers,5.6 Hubs and switches5.7 PPP5.8 Link Virtualization: ATM,5: DataLink Layer,5-33,Multiple Access Links and Protocols,Two types of “links”:point-to-pointPPP for dial-up accesspoint-to-point link between Ethernet switch and hostbroadcast (shared wire or medium)old-fashioned Ethernetupstream HFC (cable)802.11 wireless LAN,shared wire (e.g., cabled Ethernet),shared RF (e.g., 802.11 WiFi),shared RF(satellite),humans at acocktail party (shared air, acoustical),5: DataLink Layer,5-34,Multiple access problem,Point-to-point link and switched media no problemBroadcast links?Network arbitrationGive everyone a fixed time/freq slot?Ok for fixed bandwidth (e.g., voice)What if traffic is bursty?Centralized arbiterEx: cell phone base stationSingle point of failureDistributed arbitrationAloha/EthernetHumans use multiple access protocols all the time,5: DataLink Layer,5-35,Multiple access protocols,single shared communication channel two or more simultaneous transmissions by nodes: interference only one node can send successfully at a time multiple access protocol:distributed algorithm that determines how stations share channel, i.e., determine when station can transmitcommunication about channel sharing uses channel itself! what to look for in multiple access protocols: synchronous or asynchronous amount of information needed about other stations robustness (e.g., to channel errors) performance,5: DataLink Layer,5-36,Ideal Multiple Access Protocol,Broadcast channel of rate R bps1. Efficient:When one node wants to transmit, it can send at rate R.2. Fair:When M nodes want to transmit, each can send at average rate R/M3. Fully decentralized:no special node to coordinate transmissionsno synchronization of clocks, slots4. Simple,5: DataLink Layer,5-37,MAC Protocols: a taxonomy,Three broad classes:Channel Partitioningdivide channel into smaller “pieces” (time slots, frequency, code)allocate piece to node for exclusive useRandom Accesschannel not divided, allow collisions“recover” from collisions“Taking turns”tightly coordinate shared access to avoid collisionsNodes take turns, but nodes with more to send can take longer turns,5: DataLink Layer,5-38,Channel Partitioning MAC protocols: TDMA,TDMA: time division multiple access channel divided into N time slots, one per useraccess to channel in rounds inefficient with low duty cycle users and at light loadeach station gets fixed length slot (length = pkt trans time) in each round unused slots go idle example: 6-station LAN, 1,3,4 have pkt, slots 2,5,6 idle,1,3,4,1,3,4,6-slotframe,5: DataLink Layer,5-39,Channel Partitioning MAC protocols: FDMA,FDMA: frequency division multiple access channel spectrum divided into frequency bandseach station assigned fixed frequency bandunused transmission time in frequency bands go idle example: 6-station LAN, 1,3,4 have pkt, frequency bands 2,5,6 idle,frequency bands,time,FDM cable,5: DataLink Layer,5-40,Channel Partitioning MAC protocols,CDMA (Code Division Multiple Access) unique “code” assigned to each user; ie, code set partitioningused mostly in wireless broadcast channels (cellular, satellite,etc)each user has own “chipping” sequence (ie, code) to encode dataencoded signal = (original data) X (chipping sequence)decoding: inner-product of encoded signal and chipping sequenceallows multiple users to “coexist” and transmit simultaneously with minimal interference (if codes are “orthogonal”),5: DataLink Layer,5-41,Channel Partitioning MAC protocols,CDMA Encode/Decode,5: DataLink Layer,5-42,Channel Partitioning MAC protocols,CDMA: two sender interference,5: DataLink Layer,5-43,Random Access Protocols,When node has packet to sendtransmit at full channel data rate R.no a priori coordination among nodestwo or more transmitting nodes “collision”,To avoid deterministic collisions: randomize random access MAC protocol specifies: how to detect collisionshow to recover from collisions (e.g., via delayed retransmissions)“Asynchronous” TDMAExamples of random access MAC protocols:slotted ALOHAALOHACSMA, CSMA/CD, CSMA/CA,5: DataLink Layer,5-44,Slotted ALOHA,Assumptionsall frames same sizetime is divided into equal size slots, time to transmit 1 framenodes start to transmit frames only at beginning of slotsnodes are synchronizedif 2 or more nodes transmit in slot, all nodes detect collision,Operationwhen node obtains fresh frame, it transmits in next slotno collision, node can send new frame in next slotif collision, node retransmits frame in each subsequent slot with prob. p until success,5: DataLink Layer,5-45,Slotted ALOHA,Prossingle active node can continuously transmit at full rate of channelhighly decentralized: only slots in nodes need to be in syncsimple,Conscollisions, wasting slotsidle slotsnodes may be able to detect collision in less than time to transmit packetclock synchronization,5: DataLink Layer,5-46,Slotted Aloha efficiency,Suppose N nodes with many frames to send, each transmit in slot with probability pprob that node 1 has success in a slot = p(1-p)N-1prob that any node has a success = Np(1-p)N-1,For max efficiency with N nodes, find p* that maximizes Np(1-p)N-1For many nodes, take limit of Np*(1-p*)N-1 as N goes to infinity, gives 1/e = .37,Efficiency is the long-run fraction of successful slots when there are many nodes, each with many frames to send,At best: channelused for useful transmissions 37%of time!,5: DataLink Layer,5-47,Pure (unslotted) ALOHA,unslotted Aloha: simpler, no synchronizationwhen frame arrivesSend without awaiting for beginning of slotcollision probability increases:frame sent at t0 collides with other frames sent in t0-1,t0+1,5: DataLink Layer,5-48,Pure Aloha efficiency,P(success by given node) = P(node transmits) . P(no other node transmits in p0-1,p0 . P(no other node transmits in p0,p0+1 = p . (1-p)(N-1) . (1-p) (N-1)P(success by any of N nodes) = N p . (1-p) (N-1). (1-p) (N-1) choosing optimum p as n - infty . = 1/(2e) = .18,S = throughput = “goodput” (success rate),5: DataLink Layer,5-49,CSMA (Carrier Sense Multiple Access),Human analogy: dont interrupt others!Listen before transmittingCSMA algorithmIf channel sensed idle: transmit entire frameIf channel sensed busy, defer transmission Persistent CSMA: retry immediately with probability p when channel becomes idleNon-persistent CSMA: retry after random interval,5: DataLink Layer,5-50,CSMA collisions,collisions can still occur:propagation delay means two nodes may not heareach others transmission,collision:entire packet transmission time wasted,spatial layout of nodes,note:role of distance & propagation delay in determining collision probability,5: DataLink Layer,5-51,CSMA/CD (Collision Detection),Human analogy: the polite conversationalist CSMA/CD algorithmCarrier sensing, deferral as in CSMAAttempt to detect collisions while sendingAbort colliding transmissions as soon as possible to reduce channel wastage Collision detection: Easy in wired LANs: measure signal strengths, compare transmitted, received signalsCollisions detected within short time,5: DataLink Layer,5-52,CSMA/CD collision detection,5: DataLink Layer,5-53,CSMA/CD problems,Can CSMA/CD work over wireless LANs?Collision detection difficult in wireless LANs: receiver shut off while transmittingHidden terminal problem,5: DataLink Layer,5-54,Hidden Terminal effect,A, C cannot hear each otherobstacles, signal attenuationNeither A nor C can tell if they collide at B,5: DataLink Layer,5-55,CSMA/CA: CSMA w/ collision avoidance,Use base CSMAAdd acknowledgementsReceiver acknowledges receipt of dataAvoids hidden terminal problemAvoid collisions explicitly via channel reservationSender sends “request-to-send” (RTS) messagesTransmitted without reservation using CSMA with ACKsReceiver sends “clear-to-send” (CTS) messagesTransmitted without reservation using CSMA with ACKsSender sends data packet using reservationExplicitly indicates length of so others know how long to back offUsed in 802.11 wireless LAN networks,5: DataLink Layer,5-56,“Taking Turns” MAC protocols,Recall, channel partitioning MAC protocols:share channel efficiently and fairly at high loadinefficient at low load: delay in channel access, 1/N bandwidth allocated even if only 1 active node! Random access MAC protocolsefficient at low load: single node can fully utilize