15 –Data link layer15 Data link layer4-1Chapter 5: The Data Link LayerChapter 5 The Data L nk LayerOur goals: understand principles behind data link layer services:error detection, correctionerror detection, correction sharing a broadcast channel: multiple access link layer addressingli bl d t t nsf fl c nt l: dn!reliable data transfer, flow control: done! instantiation and implementation of various link layer technologiesyg4-2Link Layer: IntroductionL nk Layer Introduct onSome terminology: hosts and routers are nodes“link” communication channels that connect adjacent nodes along communication path are linksp wired links wireless links LANs layer-2 packet is a frame,encapsulates datagramdata-link layer has responsibility of transferring datagram from one node Network Layer4-3transferring datagram from one node to adjacent node over a linkLink layer: contextL nk layer context Datagram transferred by different link protocols gfyff pover different links: e.g., Ethernet on first link, frame relay on intermediate links 802 11 on last linklinks, 802.11 on last link Each link protocol provides different services e.g., may or may not provide rdt over linkNetwork Layer4-4Link Layer ServicesL nk Layer Serv ces Framing, link access: encapsulate datagram into frame, adding header, trailer channel access if shared medium “MAC” addresses used in frame headers to identify fm fysource, dest • different from IP address!Reliable delivery between adjacent nodesReliable delivery between adjacent nodes we learned how to do this already (chapter 3)! seldom used on low bit error link (fiber, some twisted i)pair) wireless links: high error rates• Q: why both link-level and end-end reliability?Network Layer4-5Link Layer Services (more)L nk Layer Serv ces (more)Flow Control:Flow Control: pacing between adjacent sending and receiving nodesError Detection: errors caused by signal attenuation, noise.  receiver detects presence of errors: •signals sender for retransmission or drops frame signals sender for retransmission or drops frame  Error Correction: receiver identifies and correctsbit error(s) without ()resorting to retransmissionHalf-duplex and full-duplexwith half duplex nodes at both ends of link can transmit Network Layer4-6with half duplex, nodes at both ends of link can transmit, but not at same timeAdaptors CommunicatingAdaptors Commun cat ngsendingrcvingnodedatagramlink layer protocolgnodeframenodeframeadapteradapter link layer implemented in “adaptor” (aka NIC) receiving side looks for errors, rdt, flow l pp Ethernet card, 802.11 cardsending side:control, etc extracts datagram, passes to rcving nodesending side encapsulates datagram in a frameadds error checking bits Network Layer4-7adds error checking bits, rdt, flow control, etc.Error DetectionError Detect onEDC= Error Detection and Correction bits (redundancy)D = Data protected by error checking, may include header fields py gy• Error detection not 100% reliable!• protocol may miss some errors, but rarelyl EDC f ld ld b d d •larger EDC field yields better detection and correction5: DataLink Layer 5-8Parity CheckingTwo Dimensional Bit ParitySingle Bit Parity:Detect single bit errorsy(Forward error correction):Detect and correctsingle bit errorsDetect double bit errors00Lots of bandwidth!5: DataLink Layer 5-9Internet checksumInternet checksumGoal: detect “errors” (e.g., flipped bits) in transmitted t Sender: Receiver:compute checksum of received segment  treat segment contents as sequence of 16-bit integers checksum: addition (1’s complement sum) of segment nt ntscompute checksum of received segment check if computed checksum equals checksum field value:NO error detectedcontents sender puts checksum value into UDP/TCP/IP checksum fieldNO -error detected YES - no error detected. But maybe errors nonetheless?More later ….Performed in software and hence must be a simple and quick mechanism.5: DataLink Layer 5-10Checksumming: Cyclic Redundancy Checkgy y view data bits, D, as a binary numberchoose r+1 bit pattern (generator) Gchoose r+1 bit pattern (generator), G goal: choose r CRC bits, R, such that <D,R> exactly divisible by G (modulo 2) receiver knows G divides <D R> by G If nonzero remainder: receiver knows G, divides <D,R> by G. If non-zero remainder: error detected!can detect all burst errors less than r+1 bitswidely used in practice (ATM Ethernet)widely used in practice (ATM, Ethernet)5: DataLink Layer 5-11CRC ExampleEmpWant:D2rXOR R GD.2rXOR R = nGequivalently:f d d D2if we divide D.2rby G, yield remainder Rremainder RR = remainder[ ]D.2rG5: DataLink Layer 5-12CRCCRCThree polynomials that are in common are:Three polynomials that are in common are: 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) Ethernet) 5: DataLink Layer 5-13CRC-16 implementation in hardwareG( ) 16 15 2 1G(x) = x16+ x15+ x2+ 1S htt // tt t h /CRC/AN730 df5: DataLink Layer 5-14Source: http://wattmep.tvn.hu/CRC/AN730a.pdfMultiple Access Links and ProtocolsTwo types of “links”:point-to-pointpp PPP for dial-up access broadcast (shared wire or medium) traditional Ethernet upstream HFC802 11 wireless LAN802.11 wireless LAN5: DataLink Layer 5-15Multiple Access protocolsMult ple Access protocols single shared broadcast channel il ii b d  two or more simultaneous transmissions by nodes: interference  collision if node receives two or more signals at the same timegmultiple access protocol distributed algorithm that determines how nodes h h l d h d share channel, i.e., determine when node can transmit communication about channel sharing must use channel itself! itself!  no out-of-band channel for coordination5: DataLink Layer 5-16Ideal Multiple Access ProtocolIdeal Mult ple Access ProtocolBroadcast channel of rate R bpsfp1. 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:3. Fully decentralized: no special node to coordinate transmissions no synchronization of clocks, slots4. Simple5: DataLink Layer 5-17MAC