Chapter 5: The data link layer Our goals: Overview: o understand principles o link layer services behind data link layer services: g error detection O error detection correction correction D multiple access protocols o sharing a broadcast channel: multiple access and laNs o link layer addressing o link layer addressing, ARP o reliable data traster O specific link layer flow control: done! g instantiation and technologies implementation of various o Ethernet link layer technologies o hibs bridges, switches 5: DataLink Layer 5a-1
5: DataLink Layer 5a-1 Chapter 5: The Data Link Layer Our goals: understand principles behind data link layer services: error detection, correction sharing a broadcast channel: multiple access link layer addressing reliable data transfer, flow control: done! instantiation and implementation of various link layer technologies Overview: link layer services error detection, correction multiple access protocols and LANs link layer addressing, ARP specific link layer technologies: Ethernet hibs, bridges, switches
Link Layer: setting the context error actual PDu flow di dI dI Router r1 application app ication transport network net ork data link data link data link physical dIdI d protocol I di d physica Host H1 ph/ph/Ph 回p回 network Host H2 Router R2 Router r3 Router R4 5: DataLink Layer 5a-2
5: DataLink Layer 5a-2 Link Layer: setting the context
Link Layer: setting the context o two physically connected devices: o host-router router-router host-host unit of data: frame APplication HM‖ fransport n ht M network data link network link proToco link Hi HnH+ N hysical phy hys link physical frame adapter card 5: DataLink Layer 5a-3
5: DataLink Layer 5a-3 Link Layer: setting the context two physically connected devices: host-router, router-router, host-host unit of data: frame application transport network link physical network link physical M M M M Ht HnHt Hl HnHt Hl HnHt M frame phys. link data link protocol adapter card
Link Layer Services 口 Framing, link access: encapsulate datagram into frame, adding header, trailer o implement channel access if shared medium o physical addresses' used in frame headers to identify source. dest different from IP address D Reliable delivery between two physically connected devices o we learned how to do this already (chapter 3 o seldom used on low bit error link(fiber some twisted pair o wireless links: high error rates Q: why both link-level and end-end reliability? 5: DataLink Layer 5a-4
5: DataLink Layer 5a-4 Link Layer Services Framing, link access: encapsulate datagram into frame, adding header, trailer implement channel access if shared medium, ‘physical addresses’ used in frame headers to identify source, dest • different from IP address! Reliable delivery between two physically connected devices: we learned how to do this already (chapter 3)! seldom used on low bit error link (fiber, some twisted pair) wireless links: high error rates • Q: why both link-level and end-end reliability?
Link Layer Services(more 口 Flow Contro|: o pacing between sender and receivers g Error Detection o errors caused by signal attenuation, noise o receiver detects presence of errors: signals Sender for retransmISSion or drops frame g Error Correction o receiver identifies and corrects bit error(s without resorting to retransmission 5: DataLink Layer 5a-5
5: DataLink Layer 5a-5 Link Layer Services (more) Flow Control: pacing between sender and receivers Error Detection: errors caused by signal attenuation, noise. receiver detects presence of errors: • signals sender for retransmission or drops frame Error Correction: receiver identifies and corrects bit error(s) without resorting to retransmission
Link Layer: Implementation O implemented in adapter o e.g., PCMCIA card, Ethernet card o typically includes: RAM, DSP chips, host bus nterface, and link interface [M application H+ M l transport M network data link network proToco M link link Hi HH+ M physical phys. link physical frame ada card 5: DataLink Layer 5a-6
5: DataLink Layer 5a-6 Link Layer: Implementation implemented in “adapter” e.g., PCMCIA card, Ethernet card typically includes: RAM, DSP chips, host bus interface, and link interface application transport network link physical network link physical M M M M Ht HnHt Hl HnHt Hl HnHt M frame phys. link data link protocol adapter card
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 datagram datagram a bits in D N ○K detected ? error ← d data bits D EDC D EDC o bit-error prone link 0 5: DataLink Layer 5a-7
5: DataLink Layer 5a-7 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
Parity checking Single Bit Parity: Two Dimensional Bit Parity: Detect single bit errors Detect and correct single bit errors d data bits -parity d 1,j+1 bit 2,1 d 2j+1 011001010 d olumn 1.1 d 101011 11011 1111oO 王(11)Pa error 011101 01110n 001010 0101o no errors parIty error correctab/e single bit error 5: DataLink Layer 5a-8
5: DataLink Layer 5a-8 Parity Checking Single Bit Parity: Detect single bit errors Two Dimensional Bit Parity: Detect and correct single bit errors 0 0
Internet checksum Goal: detect"errors"(e.g, flipped bits)in transmitted segment(note: used at transport layer only) Sender. Receiver o treat segment contents 口 compute checksum of as sequence of 16-bit received segment Integers o check if computed checksum 口 checksum: addition(1s equals checksum field value complement sum)of o NO-error detected segment contents O yES- no error detected 口 sender puts checksum But maybe errors value into UDP checksum nonethless? More later field 5: DataLink Layer 5a-9
5: DataLink Layer 5a-9 Internet checksum Sender: treat segment contents as sequence of 16-bit integers checksum: addition (1’s complement sum) of segment contents sender puts checksum value into UDP checksum field Receiver: compute checksum of received segment check if computed checksum equals checksum field value: NO - error detected YES - no error detected. But maybe errors nonethless? More later …. Goal: detect “errors” (e.g., flipped bits) in transmitted segment (note: used at transport layer only)
Checksumming Cyclic Redundancy Check o view data bits, d, as a binary number o choose r+1 bit pattern(generator), G o goal: choose r CRC bits, R, such that o D, R> exactly divisible byG(modulo 2) o receiver knows G, divides D, R> by G. If non-zero remainder error detected. o can detect all burst errors less than r+1 bits o widely used in practice (ATM, HDCL) -d bits ← r bits→ bit D: data bits to be sent R: CRC bits pattern mathematical D*2 XOR R formula 5: Datalink layer 5a-10
5: DataLink Layer 5a-10 Checksumming: Cyclic Redundancy Check view data bits, D, as a binary number choose r+1 bit pattern (generator), G goal: choose r CRC bits, R, such that exactly divisible by G (modulo 2) receiver knows G, divides by G. If non-zero remainder: error detected! can detect all burst errors less than r+1 bits widely used in practice (ATM, HDCL)