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 <D,R> exactly divisible by G (modulo 2) 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, HDCL)