CPSC 441 Computer Networks - Chapter 6 PDF

Chapter 6: Link layer CPSC 441 our goals: Computer Networks v understand principles behind link layer services:...

Chapter 6: Link layer CPSC 441 our goals: Computer Networks v understand principles behind link layer services: Majid Ghaderi § error detection, correction § sharing a broadcast channel: multiple access Department of Computer Science § link layer addressing University of Calgary § local area networks: Ethernet v instantiation, implementation of various link layer technologies CPSC 441 - Link Layer 2 Outline Introduction terminology: 6.1 introduction, services v hosts and routers: nodes 6.2 error detection, correction v communication channels that global ISP 6.3 multiple access protocols connect adjacent nodes along communication path: links 6.4 LANs § wired links § addressing, ARP § wireless links § Ethernet v layer-2 packet: frame, § switches encapsulates datagram data-link layer has responsibility of transferring datagram from one node to physically adjacent node over a link CPSC 441 - Link Layer 3 CPSC 441 - Link Layer 4 Link layer: context Link layer services v datagram transferred by different link protocols over v framing: different links: § encapsulate datagram into frame, adding header § e.g., Ethernet on one link, 802.11 on another link § channel access if shared medium § “MAC” addresses used in frame headers to identify source, dest v each link protocol provides different services different from IP address! § e.g., may or may not provide rdt over link v reliable delivery between adjacent nodes -xp LCP § we learned how to do this already (chapter 3)! # g § seldom used on low bit-error link (e.g., fiber) § wireless links: high error rates ↓ ↓ ↓ WiFi Fiber Copper Q: why both link-level and end-end reliability? optic link CPSC 441 - Link Layer 5 CPSC 441 - Link Layer 6 Link layer services (more) Link layer services (more) v link access: v error detection: § no problem on point to point links § errors caused by signal attenuation, noise § multiple access control for shared links § receiver detects presence of errors: signals sender for retransmission or drops frame v flow control: v error correction: § receiver identifies and corrects bit error(s) without resorting to § pacing between adjacent sending and receiving nodes retransmission § not to overflow receiver v half-duplex and full-duplex § with half duplex, nodes at both ends of link can transmit, but not at same time CPSC 441 - Link Layer 7 CPSC 441 - Link Layer 8 Where is the link layer implemented? Adapters communicating v in each and every node v link layer implemented in “adapter” (aka network datagram datagram interface card NIC) or on a controller controller chip application § Ethernet card, 802.11 transport network cpu memory sending host receiving host card; Ethernet chipset link datagram § implements link, physical host frame layer controller bus (e.g., PCI) v attaches into system’s bus link physical v sending side: v receiving side physical v combination of hardware, transmission § encapsulates datagram in § looks for errors, rdt, software, firmware frame flow control, etc network adapter card § adds error checking bits, § extracts datagram, passes rdt, flow control, etc. to upper layer at receiving side CPSC 441 - Link Layer 9 CPSC 441 - Link Layer 10 Outline Error detection EDC= Error Detection and Correction bits (redundancy) 6.1 introduction, services D = Data protected by error checking, may include header fields 6.2 error detection, correction Error detection not 100% reliable! 6.3 multiple access protocols protocol may miss some errors, but rarely larger EDC field yields better detection and correction 6.4 LANs § addressing, ARP § Ethernet otherwise § switches CPSC 441 - Link Layer 11 CPSC 441 - Link Layer 12 Parity checking Internet checksum (review) single bit parity: two-dimensional bit parity: goal: detect “errors” (e.g., flipped bits) in transmitted packet v detect single bit v detect and correct single bit errors (note: used at transport layer only) errors sender: receiver: v treat segment contents v compute checksum of 1 as sequence of 16-bit received segment integers v check if computed v checksum: addition (1’s checksum equals checksum complement sum) of field value: segment contents § NO - error detected v sender puts checksum § YES - no error detected. value into UDP But maybe errors 0 0 checksum field nonetheless? CPSC 441 - Link Layer 13 CPSC 441 - Link Layer 14 CRC Example Cyclic redundancy check D = 10/110 G = v more powerful error-detection coding 10013 bits v view data bits, D, as a binary number = v choose r+1 bit pattern (generator), G ite into v goal: choose r CRC bits, R, such that. D 25 = z Dx 101110 § exactly divisible by G (modulo 2) 000 ! XOR r = 3 § receiver knows G, divides by G. If non-zero remainder: error detected! XoR § can detect all burst errors up to r bits - widely used in practice (Ethernet, 802.11 WiFi) 0011 00 v 100/ So , o transmit : 1 DR 00 s Lao(as bits + R CPSC 441 - Link Layer 15 CRC example Outline want: 6.1 introduction, services D.2r XOR R = nG equivalently: 6.2 error detection, correction D.2r = nG XOR R 6.3 multiple access protocols equivalently: 6.4 LANs if we divide D.2r by § addressing, ARP G, want remainder R § Ethernet to satisfy: § switches D.2r R = remainder[ ] G CPSC 441 - Link Layer 16 CPSC 441 - Link Layer 17 Multiple access links, protocols Multiple access protocols two types of “links”: v single shared broadcast channel v point-to-point v two or more simultaneous transmissions by nodes: § PPP for dial-up access interference § point-to-point link between Ethernet switch, host § collision if node receives two or more signals at the same v broadcast (shared wire or medium) time § upstream HFC § 802.11 wireless LAN multiple access protocol v algorithm that determines how nodes share channel, i.e., determines when node can transmit v communication about channel sharing must use channel itself! § no out-of-band channel for coordination shared wire (e.g., shared RF shared RF humans at a cabled Ethernet) (e.g., 802.11 WiFi) (satellite) cocktail party (shared air, acoustical) CPSC 441 - Link Layer 18 CPSC 441 - Link Layer 19  An ideal multiple access protocol MAC protocols: taxonomy three broad classes: given: broadcast channel of rate R bps v channel partitioning desiderata: § divide channel into smaller “pieces” (e.g., time slot, frequency) 1. when M nodes are active, each can transmit at average § allocate piece to node for exclusive use rate R/M. v random access 2. when only one node is active, it can send at rate R § channel not divided, allow collisions 3. fully decentralized: § “recover” from collisions no special node to coordinate transmissions v “taking turns” no synchronization of clocks, slots § nodes take turns, but nodes with more to send can take longer turns 4. simple CPSC 441 - Link Layer 20 CPSC 441 - Link Layer 21 Channel partitioning MAC protocols: TDMA Channel partitioning MAC protocols: FDMA TDMA: time division multiple access FDMA: frequency division multiple access v access to channel in "rounds" v channel spectrum divided into frequency bands v each station gets fixed length slot (length = pkt v each station assigned fixed frequency band trans time) in each round v unused transmission time in frequency bands go idle v unused slots go idle v example: 6-station LAN, 1,3,4 have pkt, frequency bands 2,5,6 v example: 6-station LAN, 1,3,4 have pkt, slots idle 2,5,6 idle not efficient b/c 3 channels are wasted and unused & basty traffic time frequency bands 6-slot 6-slot frame frame 1 3 4 1 3 4 not efficient b/ each slot only gets By of the FDM cable bandwidth but , these are only 3 active spots CPSC 441 - Link Layer 22 CPSC 441 - Link Layer 23 Random access protocols ALOHA v when node has packet to send § transmit at full channel data rate R § no a priori coordination among nodes v two or more transmitting nodes ➜ “collision”, v random access MAC protocol specifies: § how to detect collisions § how to recover from collisions (e.g., via delayed retransmissions) v examples of random access MAC protocols: § slotted ALOHA § ALOHA § CSMA, CSMA/CD, CSMA/CA CPSC 441 - Link Layer 24 CPSC 441 - Link Layer 25 ALOHA Slotted ALOHA v Developed in University of Hawaii in early 1970’s by assumptions: operation: Norman Abramson v all frames same size v when node obtains fresh v time divided into equal size frame, transmits in next slot v It does not get much simpler: slots (time to transmit 1 § if no collision: node can send § A user transmits at will, i.e., random access frame) new frame in next slot § If two or more messages overlap in time, there is a collision nodes start to transmit § Sender waits for roundtrip time plus a fixed delay v § if collision: node retransmits only at slot beginning frame in each subsequent lack of ACK = collision v nodes are synchronized slot with prob. p until § After a collision, colliding stations retransmit the packet, but they stagger their attempts randomly to reduce the chance of repeated v if 2 or more nodes transmit success collisions in slot, all nodes detect collision CPSC 441 - Link Layer 26 CPSC 441 - Link Layer 27  Efficiency of ALOHA Slotted ALOHA Efficiency total ofsuccessful time Zim a s 1 1 1 probability (a = node 1 1 time slot is successful node 2 2 2 2 Throughput = R Efficiency - node 3 3 3 3 ↓ ↓ 0. 5 Channel C E C S E C E S S Rate Pros: Cons: v single active node can v collisions, wasting slots continuously transmit at v idle slots full rate of channel v nodes may be able to v highly decentralized: only detect collision in less slots in nodes need to be in sync than time to transmit packet v simple v clock synchronization CPSC 441 - Link Layer 28 Slotted ALOHA Analysis (a successful Slotted ALOHA: efficiency P Efficiency = Slot is P(node success) = 2 1 is success) + PLode is +... + P(node N is success) P(mode success) 1 is = P(node I transmits) · P(other modes do not transmit) efficiency: long-run v max efficiency: find p* that = P. (1 - p)n - 1 fraction of successful slots maximizes = P(1 p)n - - (many nodes, all with many Np(1-p)N-1 frames to send) for many nodes, take limit 1 p)n - E = NP(1 - v Choose optimal p + p * = t of Np*(1-p*)N-1 as N goes 2 v suppose: N nodes with to infinity, gives: = p)N- p) (1 p) ) - P(n (1 (n 1) + many frames to send, each max efficiency = 1/# =.37 + p() = 0 0 - - = 0 - + - - - transmits in slot with > - px = t probability p ! E = (1 - t )d - 1 v prob that given node has at best: channel success in a slot = p(1- used for useful = sin( v p)N-1 prob that any node has a transmissions 37% of time! (1 success = Np(1-p)N-1 () " Toext Note : Lin + = e x + x CPSC 441 - Link Layer 29  Pure ALOHA Analysis Pure (unslotted) ALOHA Efficiency = NXP(noda 1 is successful) do not PCode transmits) Ploter modes P(node 1 is successful) = A X v unslotted Aloha: simpler, no synchronization tensmit [to , to 13) + x P(other modes do not v when frame first arrives transmit Cto-1 , to]) 1 § transmit immediately p)n (1 b)n - (1 - = p. -. - 1) collision probability increases: P(1 p)2(m - = v - § frame sent at t0 collides with other frames sent in [t0-1,t0+1] - N+ x onarrae outordesare susa CPSC 441 - Link Layer 30 Pure ALOHA efficiency CSMA (carrier sense multiple access) P(success by given node) = P(node transmits). P(no other node transmits in [t0-1,t0]. P(no other node transmits in [t0,t0+1] CSMA: listen before transmit: if channel sensed idle: transmit entire frame = p. (1-p)N-1. (1-p)N-1 v if channel sensed busy, defer transmission = p. (1-p)2(N-1) … choosing optimum p and then letting " → ∞ v human analogy: don’t interrupt others! = 1/(2e) =.18 even worse than slotted Aloha! CPSC 441 - Link Layer 31 CPSC 441 - Link Layer 32 CSMA collisions spatial layout of nodes CSMA/CD (collision detection) v collisions can still occur: CSMA/CD: carrier sensing, deferral as in CSMA propagation delay means § collisions detected within short time two nodes may not hear § colliding transmissions aborted, reducing channel wastage each other’s transmission v collision detection: v collision: entire packet § easy in wired LANs: measure signal strengths, compare transmission time transmitted, received signals wasted § difficult in wireless LANs: received signal strength § distance & propagation overwhelmed by local transmission strength delay play role in in determining collision probability CPSC 441 - Link Layer 33 CPSC 441 - Link Layer 34 CSMA/CD Collision Detection CSMA/CD (collision detection) - t prop T [l I L B spatial layout of nodes / TJ #l is max propagation delay = + prop X total = duration 2t prop for France A 7 detect It prop collision CPSC 441 - Link Layer 35 CSMA/CD Analysis CSMA/CD efficiency slot tim e (2e v tprop = max prop delay between 2 nodes in LAN ↓delPetit 1) k = - Access ttrans = time to transmit max-size frame 4 transmission = 4 v. I ↓ S I I C E " C 2 +prop It prop 2+ prop + )**+,+)$,- = " + !! &"'& (!!"#$% trans ⑫ Alona v efficiency goes to 1 § as tprop goes to 0 =Zippe Efficiency tor. § as ttrans goes to infinity + trans v better performance than ALOHA: and simple, cheap, decentralized! +po - -E- 10 % is CPSC 441 - Link Layer 36 Collision Avoidance: RTS-CTS exchange CSMA/CA (collision avoidance) A B idea: allow sender to “reserve” channel rather than random AP access of data frames: avoid collisions of long data frames RTS(B) RTS(A) v sender first transmits small request-to-send (RTS) packets to receiver using CSMA reservation collision § RTSs may still collide with each other (but they’re short) RTS(A) v receiver broadcasts clear-to-send CTS in response to RTS CTS(A) CTS(A) v CTS heard by all nodes § sender transmits data frame § other nodes defer transmissions DATA (A) defer avoid data frame collisions time using small reservation packets! ACK(A) ACK(A) CPSC 441 - Link Layer 37 CPSC 441 - Link Layer 38  “Taking turns” MAC protocols “Taking turns” MAC protocols Master through polling: goes each checking channel partitioning MAC protocols: , if there is data to be sent § share channel efficiently and fairly at high load v master node “invites” § inefficient at low load: delay in channel access, 1/N slave nodes to transmit data bandwidth allocated even if only 1 active node! in turn E poll typically used with F v random access MAC protocols “dumb” slave devices master § efficient at low load: single node can fully utilize v concerns: data If master channel crashes § polling overhead , entire network § high load: collision overhead § latency functioning will stop “taking turns” protocols § single point of slaves T look for best of both worlds! failure (master) try to be efficient for both high land v used in Bluetooth and low load scenarios networks CPSC 441 - Link Layer 39 CPSC 441 - Link Layer 40 “Taking turns” MAC protocols Summary of MAC protocols token passing: v channel partitioning, by time, frequency or code T v control token passed § Time Division, Frequency Division - from one node to next v random access (dynamic), sequentially. § ALOHA, S-ALOHA, CSMA, CSMA/CD, CSMA/CA v token message (nothing § carrier sensing: easy in some technologies (wire), hard v concerns: to send) in others (wireless) § token overhead T § CSMA/CD used in Ethernet (aka IEEE 802.3) § latency § CSMA/CA used in WiFi (aka IEEE 802.11) Et Jan § single point of failure v taking turns (token) § polling there Say are N nodes when § token passing a mode has the toten , they can access the chanmel with tmax time. data (tmux node tiea Every can transmit after CPSC 441 - Link Layer 41 CPSC 441 - Link Layer 42  Outline MAC addresses and ARP 6.1 introduction, services v 32-bit IP address: 6.2 error detection, correction § network-layer address for interface 6.3 multiple access protocols § used for layer 3 (network layer) forwarding 6.4 LANs v MAC (or LAN or physical or Ethernet) address: § addressing, ARP § function: used ‘locally” to get frame from one interface to another physically-connected interface (same network, in IP- § Ethernet addressing sense) § switches § 48 bit MAC address (for most LANs) burned in NIC ROM, also sometimes software settable § e.g.: 1A-2F-BB-76-09-AD hexadecimal (base 16) notation (each “number” represents 4 bits) CPSC 441 - Link Layer 43 CPSC 441 - Link Layer 44 LAN addresses and ARP LAN addresses (more) each adapter on LAN has unique LAN address v MAC address allocation administered by IEEE v manufacturer buys portion of MAC address space 1A-2F-BB-76-09-AD (to assure uniqueness) v analogy: § MAC address: like Social Insurance Number LAN § IP address: like postal address (wired or adapter wireless) v MAC flat address ➜ portability 71-65-F7-2B-08-53 58-23-D7-FA-20-B0 § can move LAN card from one LAN to another v IP hierarchical address not portable If LAN is wired , switch is needed 0C-C4-11-6F-E3-98 § address depends on IP subnet to which node is attached If LAN is wireless , wireless access point is needed CPSC 441 - Link Layer 45 CPSC 441 - Link Layer 46 ARP LAN ARP: address resolution protocol -Q-1B IP A Switch Ir B Question: how to determine macB interface’s MAC address, MAL A Src dest knowing its IP address? ARP table: each IP node (host, i IP router) on LAN has table 137.196.7.78 § IP/MAC address mappings for some LAN 1A-2F-BB-76-09-AD nodes: 137.196.7.23 137.196.7.14 < IP address; MAC address; TTL> Map IP > MAL § TTL (Time To Live): - LAN time after which address IPB -- MALB 71-65-F7-2B-08-53 mapping will be 58-23-D7-FA-20-B0 this forgotten (typically 20 mapping is called ARP min) 0C-C4-11-6F-E3-98 137.196.7.88 CPSC 441 - Link Layer 47 ARP protocol: same LAN Addressing: routing to another LAN walkthrough: send datagram from A to B via R v A wants to send datagram to B § focus on addressing – at IP (datagram) and MAC layer (frame) § B’s MAC address not in v A caches (saves) IP-to- § assume A knows B’s IP address A’s ARP table. MAC address pair in its § assume A knows IP address of first hop router, R (how?) v A broadcasts ARP query ARP table until § assume A knows R’s MAC address (how?) packet, containing B's IP information becomes old address (times out) LAN 1 LAN 2 § dest MAC address = FF-FF- § soft state: information that - FF-FF-FF-FF times out (goes away) - unless refreshed § all nodes on LAN receive A B ARP query v ARP is “plug-and-play”: R v B receives ARP packet, § nodes create their ARP 111.111.111.111 74-29-9C-E8-FF-55 222.222.222.222 replies to A with its (B's) tables without intervention 49-BD-D2-C7-56-2A from net administrator 222.222.222.220 MAC address 1A-23-F9-CD-06-9B § frame sent to A’s MAC 111.111.111.112 111.111.111.110 222.222.222.221 address (unicast) CC-49-DE-D0-AB-7D E6-E9-00-17-BB-4B 88-B2-2F-54-1A-0F CPSC 441 - Link Layer 48 CPSC 441 - Link Layer 49 Addressing: routing to another LAN Addressing: routing to another LAN v A creates IP datagram with IP source A, destination B v frame sent from A to R v A creates link-layer frame with R's MAC address as dest, frame v frame received at R, datagram removed, passed up to IP contains A-to-B IP datagram MAC src: 74-29-9C-E8-FF-55 MAC src: 74-29-9C-E8-FF-55 MAC dest: E6-E9-00-17-BB-4B MAC dest: E6-E9-00-17-BB-4B IP src: 111.111.111.111 IP src: 111.111.111.111 IP dest: 222.222.222.222 IP src: 111.111.111.111 IP dest: 222.222.222.222 IP dest: 222.222.222.222 IP IP IP Eth Eth Eth Phy Phy Phy A B A B R R 111.111.111.111 111.111.111.111 222.222.222.222 222.222.222.222 74-29-9C-E8-FF-55 74-29-9C-E8-FF-55 49-BD-D2-C7-56-2A 49-BD-D2-C7-56-2A 222.222.222.220 222.222.222.220 1A-23-F9-CD-06-9B 1A-23-F9-CD-06-9B 111.111.111.112 111.111.111.110 222.222.222.221 111.111.111.112 111.111.111.110 222.222.222.221 CC-49-DE-D0-AB-7D E6-E9-00-17-BB-4B 88-B2-2F-54-1A-0F CC-49-DE-D0-AB-7D E6-E9-00-17-BB-4B 88-B2-2F-54-1A-0F CPSC 441 - Link Layer 50 CPSC 441 - Link Layer 51 Addressing: routing to another LAN Addressing: routing to another LAN v R forwards datagram with IP source A, destination B v R forwards datagram with IP source A, destination B v R creates link-layer frame with B's MAC address as dest, frame v R creates link-layer frame with B's MAC address as dest, frame contains A-to-B IP datagram contains A-to-B IP datagram MAC src: 1A-23-F9-CD-06-9B MAC src: 1A-23-F9-CD-06-9B MAC dest: 49-BD-D2-C7-56-2A MAC dest: 49-BD-D2-C7-56-2A IP src: 111.111.111.111 IP src: 111.111.111.111 IP dest: 222.222.222.222 IP dest: 222.222.222.222 IP IP IP Eth IP Eth Eth Phy Eth Phy Phy Phy A B A B R R 111.111.111.111 111.111.111.111 222.222.222.222 222.222.222.222 74-29-9C-E8-FF-55 74-29-9C-E8-FF-55 49-BD-D2-C7-56-2A 49-BD-D2-C7-56-2A 222.222.222.220 222.222.222.220 1A-23-F9-CD-06-9B 1A-23-F9-CD-06-9B 111.111.111.112 111.111.111.110 222.222.222.221 111.111.111.112 111.111.111.110 222.222.222.221 CC-49-DE-D0-AB-7D E6-E9-00-17-BB-4B 88-B2-2F-54-1A-0F CC-49-DE-D0-AB-7D E6-E9-00-17-BB-4B 88-B2-2F-54-1A-0F CPSC 441 - Link Layer 52 CPSC 441 - Link Layer 53 Addressing: routing to another LAN Outline v R forwards datagram with IP source A, destination B v R creates link-layer frame with B's MAC address as dest, frame contains A-to-B IP datagram 6.1 introduction, services MAC src: 1A-23-F9-CD-06-9B MAC dest: 49-BD-D2-C7-56-2A 6.2 error detection, correction 6.3 multiple access protocols IP src: 111.111.111.111 IP dest: 222.222.222.222 IP Eth 6.4 LANs Phy § addressing, ARP § Ethernet A B § switches R 111.111.111.111 222.222.222.222 74-29-9C-E8-FF-55 49-BD-D2-C7-56-2A 222.222.222.220 1A-23-F9-CD-06-9B 111.111.111.112 111.111.111.110 222.222.222.221 CC-49-DE-D0-AB-7D E6-E9-00-17-BB-4B 88-B2-2F-54-1A-0F CPSC 441 - Link Layer 54 CPSC 441 - Link Layer 55 Ethernet Ethernet: physical topology “dominant” wired LAN technology: v active switch in center v low cost NIC v each “spoke” runs a (separate) Ethernet protocol v first widely used LAN technology (nodes do not collide with each other) v kept up with speed race: 10 Mbps – 100 Gbps Ethernet card v CSMA/CD Twisted pair cable switch Metcalfe’s Ethernet sketch Star topology CPSC 441 - Link Layer 56 CPSC 441 - Link Layer 57 Ethernet frame structure Ethernet frame structure (more) v addresses: 6 byte source, destination MAC addresses sending adapter encapsulates IP datagram (or other § if adapter receives frame with matching destination network layer protocol packet) in Ethernet frame address, or with broadcast address (e.g. ARP packet), it type passes data in frame to network layer protocol dest. source preamble address address data (payload) CRC § otherwise, adapter discards frame v type: indicates higher layer protocol (mostly IP but preamble: others possible, e.g., Novell IPX, AppleTalk) v 7 bytes with pattern 10101010 followed by one v CRC: cyclic redundancy check at receiver byte with pattern 10101011 § error detected: frame is dropped v used to synchronize receiver, sender clock rates type dest. preamble address address source data CRC (payload) CPSC 441 - Link Layer 58 CPSC 441 - Link Layer 59 Binary Exponential Backoff Ethernet: unreliable, connectionless B 1 D 11 H MD T t v connectionless: no handshaking between sending and collision # receiving NICs contention window : Co 13 - K unreliable: receiving NIC doesn’t send acks or nacks , v 1 p= (kX unit) to sending NIC wait time 2 ↓ § data in dropped frames recovered only if initial Collision #2 512 bits sender uses higher layer rdt (e.g., TCP), otherwise contention window : [0 , 1 , 2 33+ k dropped data lost , p i = v Ethernet’s MAC protocol: unslotted CSMA/CD with Collision binary backoff #3 contention window : 20 , 1 , 2 , 3 4 5 0 33 + F , , , , : p = - CPSC 441 - Link Layer 60 Collision contention # m windon : Co , 1 ,...., 22 - 13 > No Ethernet CSMA/CD algorithm 802.3 Ethernet standards: link & physical layers 1. NIC receives datagram v many different Ethernet standards 4. If NIC detects another from network layer, transmission while § common MAC protocol and frame format creates frame transmitting, aborts and § different speeds: 2 Mbps, 10 Mbps, 100 Mbps, 1Gbps, 2. If NIC senses