Question? Leave a message!




The Data Link Layer

The Data Link Layer 20
Dr.ShivJindal Profile Pic
Dr.ShivJindal,India,Teacher
Published Date:19-07-2017
Website URL
Comment
Computer Communication Networks (CCN) Chapter 5: The Data Link Layer 1Goals 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 Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman & © Biplab Sikdar 2Overview • link layer services • error detection, correction • multiple access protocols and LANs • link layer addressing, ARP • specific link layer technologies: • Ethernet • hibs, bridges, switches • IEEE 802.11 LANs • PPP • ATM Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman & © Biplab Sikdar 3Link Layer: setting the context - 1 Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman & © Biplab Sikdar 4Link Layer: setting the context - 2 • two physically connected devices: • host-router, router-router, host-host • unit of data: frame M application M transport H t data link network network M H H t n protocol link M H H H link l n t M H H H l n t physical physical frame phys. link adapter card Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman & © Biplab Sikdar 5Link Layer Services - 1 • 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 Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman & © Biplab Sikdar 6Link Layer Services - 2 • 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? Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman & © Biplab Sikdar 7Link Layer Services - 3 • 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 Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman & © Biplab Sikdar 8Link Layer: Implementation • Implemented in “adapter” • e.g., PCMCIA card, Ethernet card • typically includes: RAM, DSP chips, host bus interface, and link interface M application M transport H t data link network network M H H n t protocol link M H H H link l n t M H H H l n t physical physical frame phys. link adapter card Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman & © Biplab Sikdar 9Error Detection - 1 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 Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman & © Biplab Sikdar 10Error Detection - 2 Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman & © Biplab Sikdar 11Parity Checking Single Bit Parity: Two Dimensional Bit Parity: Detect single bit Detect and correct single bit errors errors 0 0 Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman & © Biplab Sikdar 12Internet checksum Goal: detect “errors” (e.g., flipped bits) in transmitted segment (note: used at transport layer only) Sender: Receiver: • treat segment contents • compute checksum of received as sequence of 16-bit segment integers • check if computed checksum • checksum: addition (1‟s equals checksum field value: complement sum) of • NO - error detected segment contents • sender puts checksum • YES - no error detected. But value into UDP maybe errors nonetheless? checksum field More later…. Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman & © Biplab Sikdar 13Checksumming: 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) Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman & © Biplab Sikdar 14CRC Example Want: . D 2r XOR R = nG equivalently: . D 2r = nG XOR R equivalently: . if we divide D 2r by G, want reminder R . D 2r R = remainder G Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman & © Biplab Sikdar 15Multiple Access Links and Protocols Three types of “links”: • Point-to-point (single wire, e.g. PPP, SLIP) • Broadcast (shared wire or medium; e.g, Ethernet, Wavelan, etc.) • Switched (e.g., switched Ethernet, ATM etc) Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman & © Biplab Sikdar 16Multiple Access protocols - 1 • single shared communication channel • two or more simultaneous transmissions by nodes: interference • only one node can send successfully at a time • multiple access protocol: • distributed algorithm that determines how stations share channel, i.e., determine when station can transmit Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman & © Biplab Sikdar 17Multiple Access protocols - 2 • multiple access protocol (cont.): • communication about channel sharing must use channel itself • What to look for in multiple access protocols: • synchronous or asynchronous • information needed about other stations • robustness (e.g., to channel errors) • performance Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman & © Biplab Sikdar 18Multiple Access protocols - 3 • claim: humans use multiple access protocols all the time • class can "guess" multiple access protocols • multiaccess protocol 1: • multiaccess protocol 2: • multiaccess protocol 3: • multiaccess protocol 4: Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman & © Biplab Sikdar 19MAC Protocols: a taxonomy Three broad classes: • Channel Partitioning • divide channel into smaller “pieces” (time slots, frequency) • allocate piece to node for exclusive use • Random Access • allow collisions • “recover” from collisions • “Taking turns” • tightly coordinate shared access to avoid collisions Goal: efficient, fair, simple, decentralized Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman & © Biplab Sikdar 20