Question? Leave a message!




The Data Link Layer

The Data Link Layer 20
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: • hostrouter, routerrouter, hosthost • 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 linklevel 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 16bit 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 nonzero 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”: • Pointtopoint (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 20Channel Partitioning MAC protocols: TDMA 1 TDMA: time division multiple access • Access to channel in "rounds" • Each station gets fixed length slot (length = pkt trans time) in each round • Unused slots go idle • Example: 6station LAN, 1,3,4 have pkt, slots 2,5,6 idle Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 21Channel Partitioning MAC protocols: TDMA 2 • TDM (Time Division Multiplexing): channel divided into N time slots, one per user; inefficient with low duty cycle users and at light load. • FDM (Frequency Division Multiplexing): frequency subdivided. Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 22Channel Partitioning MAC protocols: FDMA 1 FDMA: frequency division multiple access • Channel spectrum divided into frequency bands • Each station assigned fixed frequency band • Unused transmission time in frequency bands go idle Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 23Channel Partitioning MAC protocols: FDMA 2 • Example: 6station LAN, 1,3,4 have pkt, frequency bands 2,5,6 idle Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 24 frequency bandsChannel Partitioning MAC protocols: FDMA 3 • TDM (Time Division Multiplexing): channel divided into N time slots, one per user; inefficient with low duty cycle users and at light load. • FDM (Frequency Division Multiplexing): frequency subdivided. Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 25Channel Partitioning (CDMA) 1 CDMA (Code Division Multiple Access) • unique “code” assigned to each user; ie, code set partitioning • used mostly in wireless broadcast channels (cellular, satellite, etc) • all users share same frequency, but each user has own “chipping” sequence (ie, code) to encode data Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 26Channel Partitioning (CDMA) 2 • Encoded signal = (original data) X (chipping sequence) • Decoding: innerproduct of encoded signal and chipping sequence • allows multiple users to “coexist” and transmit simultaneously with minimal interference (if codes are “orthogonal”) Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 27CDMA Encode/Decode Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 28CDMA: twosender interference Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 29Performance of Fixed Assignment Protocols 1 • Fixed assignment protocols are ideal for continuous streams such as video or audio • What about for packet switched data • A “perfect” multiple access scheme would always use the channel when there are packets waiting (statistical multiplexing) • The mean delay for statistical multiplexing is just like for the M / M / 1 queue: where  is the arrival rate and  is the service rate Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 30Performance of Fixed Assignment Protocols 2 • OTOH fixed assignment protocols divide the channel into N separate independent, /N identical subchannels • If each user has arrival rate /N, each user/subchannel pair can be modeled as a separate M / M / 1 queue • And the mean delay for a packet is • So, if we use fixed assignment protocols for packet switched data, mean delay goes up by a factor of N Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 31Performance of Fixed Assignment Protocols 3 • This analysis is only appropriate for TDMA de to the discretetime (slotted) nature of TDMA but the rough factor of N still holds • Fixed assignment protocols are not appropriate for multiple access in a packet switched network with a large number of users • Packet arrivals are fairly random, so there will be many times when packets are waiting at one user while other users are idle • The idle resources (time slots or bandwidth or both are wasted in this case) Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 32Random Access Protocols 1 • When node has packet to send • transmit at full channel data rate R. • no a priori coordination among nodes • Two or more transmitting nodes “collision”, • Random access MAC protocol specifies: • how to detect collisions • how to recover from collisions (e.g., via delayed retransmissions) Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 33Random Access Protocols 2 • Examples of random access MAC protocols: • ALOHA • slotted ALOHA • CSMA and CSMA/CD Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 34Pure (unslotted) ALOHA 1 • Unslotted Aloha: simpler, no synchronization • pkt needs transmission: • send without awaiting for beginning of slot • Collision probability increases: • pkt sent at t collide with other pkts sent 0 in t 1, t +1 0 0 Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 35Pure (unslotted) ALOHA 2 . P(success by given node) = P(node transmits) . P(no other node transmits in p 1,p 0 0 P(no other node transmits in p 1,p 0 0 (N1) (N1) . . = p (1p) (1p) (N1) . . P(success by any of N nodes) = N p (1p) (N1) (1p) … choosing optimum p as n infty ... = 1/(2e) = .18 Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 36Slotted Aloha • time is divided into equal size slots (= pkt trans. time) • node with new arriving pkt: transmit at beginning of next slot • if collision: retransmit pkt in future slots with probability p, until successful. Success (S), Collision (C), Empty (E) slots Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 37Slotted Aloha Efficiency Q: What is max fraction slots successful A: Suppose N stations have packets to send • each transmits in slot with probability p • prob. successful transmission S is: (N1) by single node: S= p (1p) by any of N nodes At best: S = Prob (only one transmits) channel (N1) = N p (1p) use for useful … choosing optimum p as n infty ... transmissions = 1/e = .37 as N infty 37 of time Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 38Performance Comparison 0.4 0.3 Slotted Aloha protocol constrains 0.2 effective channel throughput 0.1 Pure Aloha 1.5 2.0 0.5 1.0 G = offered load = Np Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 39Carrier Sense Multiple Access (CSMA) 1 • In some shorter distance networks, it is possible to listen to the channel before transmitting • In radio networks, this is called “ sensing the carrier” • The CSMA protocol works just like Aloha except: If the channel is sensed busy, then the user waits to transmit its packet, and a collision is avoided • This really improves the performance in short distance networks Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 40Carrier Sense Multiple Access (CSMA) 2 • How long does a blocked user wait before trying again to transmit its packet Three basic variants: • 1persistent: Blocked user continuously senses channel until its idle, then transmits • 0persistent: Blocked user waits a randomly chosen amount of time before sensing channel again Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 41Carrier Sense Multiple Access (CSMA) 3 • Ppersistent: Let T = endtoend propagation delay • If channel is idle then transmit packet • If channel busy then toss coin with P(heads) = P • Heads: Transmit at first idle • Tails: wait until first idle plus T, sense, repeat • Human analogy: Don‟t interrupt others Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 42CSMA collisions spatial layout of nodes along ethernet collisions can occur: propagation delay means two nodes may not year hear each other‟s transmission collision: entire packet transmission time wasted note: role of distance and propagation delay in determining Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 43 collision prob.CSMA/CD (Collision Detection) • CSMA improves performance, but still it wastes the channel during collisions • In some very short distance networks (e.g. coax LANs), it is possible to listen while transmitting (in addition to listening before transmitting) • If we detect a collision while transmitting, we can abort the transmission and free up the channel sooner • This idea was proposed by R. Metcalfe and Boggs at Xerox PARC in the mid 1970s under the name Ethernet. • Human analogy: the polite conversationalist Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 44CSMA/CD collision detection Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 45Historical Aside on CSMA / CD • While Metcalfe and Boggs are generally given credit for inventing Ethernet, some feel that the concept was first described by P. Townshend in 1968 under the name Magic Bus: Everyday I get in the queue, (too much, Magic Bus) To get on the bus that takes me to you (too much, Magic Bus) Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 46“Taking Turns” MAC protocols 1 Channel partitioning MAC protocols: • share channel efficiently at high load • inefficient at low load: delay in channel access, 1/N bandwidth allocated even if only 1 active node Random access MAC protocols • efficient at low load: single node can fully utilize channel • high load: collision overhead “Taking turns” protocols look for best of both worlds Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 47“Taking Turns” MAC protocols 2 Polling: Token passing: • Master node “invites” • Control token passed from slave nodes to one node to next sequentially. transmit in turn • Token message • Request to Send, • Concerns: Clear to Send messages • token overhead • Concerns: • latency • polling overhead • single point of failure • latency (token) • single point of failure (master) Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 48Reservationbased protocols 1 Distributed Polling: • Time divided into slots • Begins with N short reservation slots • reservation slot time equal to channel endend propagation delay • station with message to send posts reservation • reservation seen by all stations Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 49Reservationbased protocols 2 • After reservation slots, message transmissions ordered by known priority Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 50
Website URL
Comment