Introduction to Computer Networking Guy Leduc …

1 1 From Computer Networking , by Kurose&RossDataLink Layer6-1 Introduction to Computer Networking Guy Leduc Chapter 6 Link Layer and LANsComputer Networking : A Top Down Approach, 7th edition. Jim Kurose, Keith Ross Addison-Wesley, April 2016. From Computer Networking , by Kurose&RossDataLink Layer6-2 Chapter 6: The Data Link LayerOur goals: understand principles behind data link layer services: error detection sharing a broadcast channel: multiple access link layer addressing local area networks: Ethernet instantiation and implementation of various link layer technologies2 From Computer Networking , by Kurose&RossDataLink Layer6-3 Link Layer Introduction and services Error detection Multiple access protocols LANs Addressing, ARP Ethernet Switches Data center Networking A day in the life of a web request From Computer Networking , by Kurose&RossDataLink Layer6-4 Link Layer: IntroductionSome terminology.

2 Hosts and routers are nodes= devices with a network layer (L3) communication channels that connect adjacent nodes along communication path are links wired links wireless links LANs layer-2 packet is a frame, encapsulates datagramdata-link layer has responsibility of transferring datagram from one node to physically adjacent node over a linkglobal ISP3 From Computer Networking , by Kurose&RossDataLink Layer6-5 Link layer: context datagram transferred by different link protocols over different links: , Ethernet on first link, MPLS on intermediate links, Wi-Fi on last link each link protocol provides different services , may or may not provide reliable data transfer (rdt) over linktransportation analogy trip from Princeton to Lausanne limo: Princeton to JFK plane: JFK to Geneva train: Geneva to Lausanne tourist = datagram transport segment = communication link transportation mode = link layer protocol travel agent = routing algorithm From Computer Networking , by Kurose&RossDataLink Layer6-6 Link Layer Services framing, link access: encapsulate datagram into frame, adding header, trailer control channel access if shared medium frame addresses used in frame headers to identify sending, receiving node interfaces, over broadcast channels different from IP addresses!

3 (which identify source, dest host interfaces) reliable delivery between adjacent nodes we learned how to do this already (see rdt, chapter 3)! seldom used on low bit-error links (fiber, some twisted pair) wireless links: higher error rates, may need link-level recovery Q: why both link-level and end-end reliability?4 From Computer Networking , by Kurose&RossDataLink Layer6-7 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 From Computer Networking , by Kurose&RossDataLink Layer6-8 Where is the link layer implemented?

4 In each and every host and router interface link layer implemented in adaptor (aka network interface card NIC) or on a chip Ethernet card, Wi-Fi card; Ethernet chipset implements link, physical layer attaches into host s system buses combination of hardware, software, firmwarecontrollerphysicaltransmissioncp umemoryhost bus ( , PCI)network adaptercardapplicationtransportnetworkli nklinkphysical5 From Computer Networking , by Kurose&RossDataLink Layer6-9 Adaptors communicating sending side: encapsulates datagram in frame adds error checking bits (rdt, flow control, etc.) receiving side looks for errors (rdt, flow control, etc) extracts datagram, passes to upper layer at receiving sidecontrollercontrollersending hostreceiving hostdatagramdatagramdatagramframe From Computer Networking , by Kurose&RossDataLink Layer6-10 Link Layer Introduction and services Error detection Multiple access protocols LANs addressing, ARP Ethernet switches Data center Networking A day in the life of a web request6 From Computer Networking , by Kurose&RossDataLink Layer6-11 Error DetectionEDC= Error Detection (and sometimes Correction) bits (= redundancy)D = Data protected by error checking, may include header fields Error detection not 100% reliable!

5 May miss some errors (why?), but rarely larger EDC field yields better detection (and correction)otherwiseEDC = f (D)for some function fIs EDC = f (D )? From Computer Networking , by Kurose&RossDataLink Layer 6-12 Basic example: Parity CheckingSingle Bit Parity:Detect single bit errorsTwo Dimensional Bit Parity:Detect and correct single bit errors007 From Computer Networking , by Kurose&RossDataLink Layer6-13 TCP/UDP checksum (review)Sender: treat segment contents as sequence of 16-bit integers checksum: addition (1 s complement sum) of segment contents sender puts checksum value into UDP/TCP checksum fieldReceiver: compute checksum of received segment check if computed checksum equals checksum field value: NO - error detected YES - no error detected. But maybe errors : detect errors ( , flipped bits) in transmitted packet (note: used at transport layer only) From Computer Networking , by Kurose&RossDataLink Layer6-14 Cyclic Redundancy Check (CRC) more powerful error-detection coding 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 (in base-2 arithmetic) receiver knows G, divides <D,R> by G, if non-zero remainder: error detected!

6 Can detect any single error burst not longer than r bits (see later) widely used in practice (Ethernet, Wi-Fi, ..)<D,R> ==8 From Computer Networking , by Kurose&RossDataLink Layer 6-15 CRC XOR R = (for some n, with R < G) = XOR = + R equivalently: if we divide by G (in base-2 arithmetic), want remainder RR = mod GQuotientDividendIn base-2 arithmetic( , in a Binary Field):no carriesno borrows1 + 1 = 00 1 = 1+, , XOR: all equivalent100110011101010110001010100111 00001100100110101001 011101110D DivisorGr = 3000R = Remainder From Computer Networking , by Kurose&RossDataLink Layer 6-16 CRC Example: the polynomial viewTransmitted frame:T(x) = D(x).xr + R(x)is thus divisible by G(x)(by construction)R(x) = D(x).xr mod G(x)R(x) = x + 1 Polynomials with coefficients in a Binary FieldG(x) = x3 + 1D(x) = x5 + x3 + x2 + xr = 39 DataLink Layer6-17 Why does it work?

7 We have T(x) = D(x).xr + R(x) By construction T(x) is divisible by G(x) T(x) mod G(x) = 0 This is easy to check at the receiver, provided that the sender and the receiver agree on a certain G(x) Suppose some errors occur during transmission Errors are modelled as a particular E(x) where each term ( 0) of E(x) indicates the position of an error bit The erroneous received frame is thus T(x) + E(x) The receiver will then calculate (T(x) + E(x)) mod G(x) But (T(x) + E(x)) mod G(x) = E(x) mod G(x) because T(x) mod G(x) = 0 If the errors are an E(x) that is not divisible by G(x), they will be detected! The choice of G(x) is thus very important! But impossible to detect all errors! Why?DataLink Layer6-18 Example of CRC, with properties (1) Example of Generator: G(x) = x16 + x12 + x5 + 1 Property 1: G(x) detects every error consisting of an odd number of error bitsProof: G(x) is divisible by (x+1), in other words G(x) = (x+1)H(x) indeed, in base-2 arithmetic, G(1) = 1+1+1+1 = 0, therefore (x+1) is a factor An odd number of bit errors is modeled by a polynomial E(x) with an odd number of terms Such E(x) cannot be divisible by (x+1) indeed, in base-2 arithmetic, E(1) = 1 for such E(x) Therefore E(x) is not divisible by G(x) More generally, a G(x) composed of an even number of terms detects every error consisting of an odd number of error bits At least as good as a parity bit!

8 BTW, could a parity bit be seen as a trivial CRC? Any G(x) to suggest? Property 2: G(x) detects every 2-bit error (in any place in the frame)10 DataLink Layer6-19 Example of CRC, with properties (2) G(x) = x16 + x12 + x5 + 1 Property 3: G(x) detects every single error burst of length 16 bits An error burst of length n ( 2) is 1 error bit, followed by n-2 bits (correct or not), followed by 1 error bit Proof: An error burst of length 16 bits can be modelled by E(x) = H(x) . xk, with H(x) of degree 15, and k ( 0) being the number of bits after the last error bit H(x) is not divisible by G(x), because H(x) is of degree 15, and G(x) of degree 16 Using G(0) 0, it is easy to prove by induction that if H(x) . xk is not divisible by G(x), which is true for k=0, then H(x) . xk+1 is not divisible by G(x).

9 This leads to E(x) not being divisible by G(x) More generally, a G(x) of degree r, with G(0) 0, detects every single error burst of length r bits If errors are random, G(x) detects 99,997% of the 17-bit error bursts Any undetectable 17-bit error burst to suggest? 99,998% of the 18-bit error bursts From Computer Networking , by Kurose&RossDataLink Layer6-20 Link Layer Introduction and services Error detection Multiple access protocols LANs Addressing, ARP Ethernet Switches Data center Networking A day in the life of a web request11 From Computer Networking , by Kurose&RossDataLink Layer6-21 Multiple Access Links and ProtocolsTwo types of links : point-to-point serial link connecting two routers no need for multiple access protocol broadcast (shared wire or medium) old-fashioned Ethernet upstream Hybrid Fiber Coax (HFC) Wi-Fi wireless LANshared wire ( , cabled Ethernet)shared RF ( , Wi-Fi)shared RF(satellite) humans at acocktail party (shared air, acoustical) From Computer Networking , by Kurose&RossDataLink Layer 6-22 Multiple Access protocols single shared broadcast channel two or more simultaneous transmissions by nodes interference aka collisionmultiple access protocol: distributed algorithm that determines how nodes share channel, , determine when node can transmit so-called MAC (Medium Access Control) protocols communication about channel sharing must use channel itself!

10 No out-of-band channel for coordination12 From Computer Networking , by Kurose&RossDataLink Layer6-23An Ideal Multiple Access ProtocolGiven: broadcast channel of rate R bpsDesiderata:1. when one node wants to transmit, it can send at rate R2. when M nodes want to transmit, each can send at average rate R/M (fairness)3. fully decentralized: no special node to coordinate transmissions no synchronization of clocks, slots4. simple From Computer Networking , by Kurose&RossDataLink Layer6-24 MAC Protocols: a taxonomyThree broad classes: Channel Partitioning divide channel into smaller pieces (time slots, frequency, ..) allocate piece to node for exclusive use Random Access channel not divided, allow collisions recover from collisions Taking turns nodes take turns, but nodes with more to send can take longer turns13 From Computer Networking , by Kurose&RossDataLink Layer6-25 Channel Partitioning MAC protocols: TDMATDMA: time division multiple access access to channel in "rounds" each station gets fixed length slot (length = packet transmission time) in each round unused slots go idle example: 6-station LAN, 1,3,4 have packet, slots 2,5,6 idle 1341346-slotframe From Computer Networking , by Kurose&RossDataLink Layer6-26 Channel Partitioning MAC protocols: FDMAFDMA.