Chapter 5 Computer Networkin Link Layer and LANs 17lAa学ms A note on the use of these ppt slides James F Kurse. keith w Ross Al material copyright 1996-2007 J F Kurose and K.W. Ross, All Rights reserved Computer Networking A Top Down Approach 4th edition Jim Kurose. Keith ross Addison-Wesley, Jul 2007 5: Dat
5: DataLink Layer 5-1 Chapter 5 Link Layer and LANs A note on the use of these ppt slides: All material copyright 1996-2007 J.F Kurose and K.W. Ross, All Rights Reserved Computer Networking: A Top Down Approach 4th edition. Jim Kurose, Keith Ross Addison-Wesley, July 2007
Link Layer 5. 1 Introduction and o5.6 Hubs and switches services o5.7PPP o 5.2 Error detection and correction 6 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-2
Link Layer: Setting the Context o Two physically connected devices e Host-router, router-router host-host ● Unit of data: frame M lication M l transport TH M network data link network protoco HnH+I M link link Hi HnHtM physical physical hys link frame adapter card 5: Dat
Link Layer: Setting the Context Two physically connected devices: Host-router, router-router, host-host Unit of data: frame 5: DataLink Layer 5-3 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 e Channel access if shared medium MAC addresses used in frame headers to identify source, dest Different from ip address! o Reliable delivery between adjacent nodes 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: Dat
Link Layer Services Framing, link access: Encapsulate datagram into frame, adding header, trailer Channel access if shared medium “MAC” addresses used in frame headers to identify source, dest Different from IP address! Reliable delivery between adjacent nodes 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? 5: DataLink Layer 5-4
Link Layer Services(more) o Flow Control o Pacing between adjacent sending and receiving nodes o Error detection o Errors caused by signal attenuation, noise o Receiver detects presence of errors Signals sender for retransmission or drops frame o Error correction: o Receiver identifies and corrects bit error(s] without resorting to retransmission o Half-duplex and full-duplex e With half duplex, nodes at both ends of link can transmit but not at same time 5: Dat
Link Layer Services (more) 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 Error Correction: Receiver identifies and corrects bit error(s) without resorting to retransmission Half-duplex and full-duplex With half duplex, nodes at both ends of link can transmit, but not at same time 5: DataLink Layer 5-5
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 exactly divisible(polynomial division by g(modulo 2 e Receiver knows G, divides 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 exactly divisible (polynomial division) 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, 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