Link Layer o5.1 Introduction and o5.6 Hubs and switches services o5.7PPP 5.2 Error detection and correction o 5.mUltiple access protocols o 5.4 Link-Layer Addressing o5.5 Ethernet 5: Dat
Link Layer 5.1 Introduction and services 5.2 Error detection and correction 5.3Multiple access protocols 5.4 Link-Layer Addressing 5.5 Ethernet 5.6 Hubs and switches 5.7 PPP 5: DataLink Layer 5-6
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 all bits in d N OK detected error d data bits- D EDC D EDC bit-error prone link 5: Dat
Error Detection 5: DataLink Layer 5-7 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
Checksumming: Cyclic Redundancy Check View data bits, D, as a binary number Choose r+1 bit pattern( generator , G o Goal: choose r crc bits, R, such that o <D, R> exactly divisible(polynomial division by g(modulo 2 e Receiver knows G, divides <D, R> by G. If non-zero remainder: error detected! e Can detect all burst errors less than r+1 bits o Widely used in practice (ATM, HDLC d bits ← r bits bit D: data bits to be sent R: CRC bits, pattern D* 2 XOR R mathematica formula 5: Dat
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 (polynomial division) 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, HDLC) 5: DataLink Layer 5-8
CRC EXample Want D2r XORR=nG 10101 00 01110000 equivalently. 001 D2r=nG XORR 000 equivalently 1010 001 if we divide d2 by g 110 want remainder r 000 1100 1001 R: remainder 2 1010 001 011 R 5: Dat
CRC Example Want: D.2 r XOR R = nG equivalently: D.2 r = nG XOR R equivalently: if we divide D.2 r by G, want remainder R 5: DataLink Layer 5-9 R = remainder[ ] D.2 r G
Link Layer o5.1 Introduction and o5.6 Hubs and switches services o5.7PPP o 5.2 Error detection and correction ●5.3 Multiple access protocols o 5.4 Link-Layer Addressing o5.5 Ethernet 5: Dat
Link Layer 5.1 Introduction and services 5.2 Error detection and correction 5.3 Multiple access protocols 5.4 Link-Layer Addressing 5.5 Ethernet 5.6 Hubs and switches 5.7 PPP 5: DataLink Layer 5-10