CS 4700 / 5700 Network Fundamentals Data Link (The Etherknot Notwork)

CS 4700 / 5700 Network Fundamentals Data Link (The Etherknot Notwork) Revised 1/15/24

Data Link Layer 2 Application Presentation Session Transport Network Data Link Physical Function: Send blocks of data (frames) between physical devices Regulate access to the physical media Key challenge: How to delineate frames? How to detect errors? How to perform media access control (MAC)? How to recover from and avoid collisions?

3 Outline Framing Error Checking and Reliability Media Access Control

Framing 4 Physical layer determines how bits are encoded Next step: how to encode blocks of data Packet switched networks Each packet includes routing information Data boundaries must be known so headers can be read Types of framing Byte-oriented protocols Bit-oriented protocols Clock-based protocols

Byte Oriented: Byte Counting 5 132 132 Data Sender: insert length of the data in bytes at the beginning of each frame Receiver: extract the length and read that many bytes Problem: what if the byte count gets corrupted by interference? Receiver will erroneously believe the packet it shorter or longer than it really is, packet is corrupted Subsequent packets are also impacted! Hard to resynchronize

Desynchronization 6 Actual Packets w/ Size in Bytes What the Receiver Gets or Maybe This 10 10 10 Data 10 Data 17 17 2 75 7 7 10 Data 75 Data 2 10 Data 201 201

Byte Oriented: Sentinel Approach 7 START DLE DLE Data DLE END END Add START and END sentinels to the data Problem: what if END appear in the data? Add a special DLE (Data Link Escape) character before END What if DLE appears in the data? Add DLE before it. Similar to escape sequences in C printf(“You must \”escape\” quotes in strings”); printf(“You must \\escape\\ forward slashes as well”); Used by Point-to-Point protocol, e.g. modem, DSL, cellular

Bit Oriented: Bit Stuffing 8 0111111 0 Both sentinels are the same Example: 01111110 in High-level Data Link Protocol (HDLC) Sender: insert a 0 after each 11111 in data Known as “bit stuffing” Receiver: after seeing 11111 in the data 111110 remove the 0 (it was stuffed) 111111 look at one more bit 1111110 end of frame 1111111 error! Discard the frame 0111111 0 Add sentinels to the start and end of data Data Disadvantage: 17% overhead at worst

10 Outline Framing Error Checking and Reliability Error Detection Error Correction and Reliable Delivery Media Access Control

Dealing with Noise 11 The physical world is inherently noisy How to detect bit-errors in transmissions? Interference from electrical cables Cross-talk from radio transmissions, microwave ovens Solar storms Error detection How to recover from errors? Error correction

Naïve Error Detection 12 Idea: send two copies of each frame if (memcmp(frame1, frame2) ! 0) { OH NOES, AN ERROR! } Why is this a bad idea? Extremely high (50% !!!) overhead Poor protection against errors Twice the data means twice the chance for bit errors

Parity Bits 13 Idea: add extra bits to keep the number of 1s even Example: 7-bit ASCII characters 1 parity bit 010100 1 110100 0 101111 1 000111 1 011010 1 1 1 0 0 0 10 Detects 1-bit errors 13% overhead But, not reliable against bursty errors

Two Dimensional Parity 14 Parity bit for each column 0101001 1101001 1011110 0001110 0110100 1011111 1 0 1 1 1 0 Parity bit for each row Parity bit for the parity byte Can detect all 1-, 2-, and 3-bit errors 25% overhead 1111011 0

Two Dimensional Parity Examples 15 0101001 1 1101001 0 1011110 0001110 1 1 0110100 1011111 1 0 1 1 1 0 Odd number of Odd 1s number of 1s 1111011 0 Odd Number of 1s Odd number of 1s

Checksums 16 Idea: Add up the bytes in the data Include the sum in the frame START Checksu END m Use ones-complement arithmetic Lower overhead than parity: 16 bits per frame But, not resilient to multi-bit errors Data Why? 1010100 01101001 10010010 1 Used in UDP, TCP, and IP

Cyclic Redundancy Check (CRC) 17 Uses field theory to compute a semi-unique value for a given message Much better performance than previous approaches Fixed size overhead per frame (usually 32-bits) Quick to implement in hardware Only 1 in 232 chance of missing an error with 32-bit CRC Details are in the book/on Wikipedia Today, cryptographic hashes are more common e.g. MD5, SHA1, SHA256, SHA512 Fixed size overhead (256- or 512-bits) Only 1 in 2256 chance of missing an error, at least

From Detection to Correction 19 Error detection needs to be paired with error correction Algorithm sketch 1. 2. 3. 4. Sender transmits a frame, retains a copy of the frame in memory Are bit errors the Receiver reads the frame, checks for errors only class of error If error is detected, sender retransmits the frame that can occur? If frame never arrives, sender retransmits the frame Problem: how does the sender know if an error occurs? Bit errors, or Frame loss

Acknowledgement 20 Problem: how does the sender know if an error occurs? Sender Receiver Frame Time ACK Acknowledgeme nt

Stop and Wait Protocol 21 Simplest form of reliability Example: Bluetooth Problems? Low utilization: can only have one frame in flight at any time Sender Timeout Timeout Receiver

Aside: Bandwidth Delay Product 24 How many bits can a given layer 2 link hold? Bandwidth Delay Product Multiply the link speed by the delay Essentially, calculate the volume of the link Delay Link Speed Tube full of cats. Bandwidth Delay Product

Aside: Bandwidth Delay Product 25 How many bits can a given layer 2 link hold? Bandwidth Delay Product Multiply the link speed by the delay Essentially, calculate the volume of the link Example: 10 Gigabit per second link with 10 millisecond delay Convert seconds to milliseconds: 10 Gbps * (1s / 1000ms) 0.01 Gbpms Calculate bandwidth delay product: 0.01 Gbpms * 10 ms 0.1 Gb 100 Mb This link can hold 100 Mb of data at any given moment

Stop and Wait Protocol 26 Simplest form of reliability Problems? Example: Bluetooth Low utilization: can only have one frame in flight at any time 10Gbps link and 10ms delay Need 100 Mb to fill the pipe Assume packets are 1500B 1500B * (8b/1B) / 2 6000b 0.006Mb Utilization is 0.006% Sender Timeout Timeout Receiver

Sliding Window 27 Windo w Allow multiple outstanding, un-ACKed frames Number Sender of un-ACKed frames is called the Receiver window Frame s ACKs Made famous by TCP We’ll look at this in more detail later

Should We Error Check in the Data Link? 28 Recall the End-to-End Argument from Architecture lecture Cons: Pros: Error free transmission cannot be guaranteed Not all applications want this functionality Error checking adds CPU and packet size overhead Error recovery requires buffering, i.e., lots of RAM Potentially better performance than app-level error checking Data link error checking in practice Most useful over lossy links Wifi, cellular, satellite

29 Outline Framing Error Checking and Reliability Media Access Control Contention MAC Basics 802.3 Ethernet

What is Media Access? 30 Ethernet and Wifi are both multi-access technologies Broadcast medium, shared by many hosts Simultaneous transmissions cause collisions This destroys the data Media Access Control (MAC) protocols are required Rules on how to share the medium Strategies for detecting, avoiding, and recovering from collisions

Strategies for Media Access 31 Channel partitioning Taking turns Divide the resource into small pieces Allocate each piece to one host Example: Time Division Multi-Access (TDMA) cellular Example: Frequency Division Multi-Access (FDMA) cellular Tightly coordinate shared access to avoid collisions Example: Token ring networks Contention Allow collisions, but use strategies to recover Examples: Ethernet, Wifi

Contention MAC Goals 32 Share the medium 1. Two hosts sending at the same time collide, thus causing interference If no host sends, channel is idle Thus, want exactly one host sending at any given time High utilization 2. TDMA is low utilization Just like a circuit switched network Simple, distributed algorithm 3. Multiple hosts that cannot directly coordinate No fancy (complicated) token-passing schemes

Contention Protocol Evolution 33 ALOHA Slotted ALOHA Start transmissions only at fixed time slots Significantly fewer collisions than ALOHA Carrier Sense Multiple Access / Collision Detection (CSMA/CD) Developed in the 70’s for packet radio networks Start transmission only if the channel is idle Stop ongoing transmission if collision is detected Carrier Sense Multiple Access / Collision Avoidance (CSMA/CA)

ALOHA 34 Topology: radio broadcast with multiple stations Protocol: Stations transmit data immediately Receivers ACK all packets No ACK collision, wait a random time then retransmit Simple, but radical concept Previous attempts all divided the channel TDMA, FDMA, etc. Optimized for the common case: few senders A B C

Tradeoffs vs. TDMA 35 In TDMA, each host must wait for its turn Delay is proportional to number of hosts Throughput In Aloha, each host sends immediately Much lower delay But, much lower utilization Sender A Sender B 2*Frame Width ALOHA Frame ALOHA Frame Time Load Maximum throughput is 18% of channel capacity

Slotted ALOHA 36 Protocol Same as ALOHA, except time is divided into slots Hosts may only transmit at the beginning of a slot Throughput Thus, frames either collide completely, or not at all 37% throughput vs. 18% for ALOHA But, hosts must have synchronized clocks Sender A Sender B ALOHA Frame ALOHA ALOHA Frame Frame ALOHA Frame Load

37 Outline Framing Error Checking and Reliability Media Access Control Contention MAC Basics 802.3 Ethernet

Broadcast Ethernet 38 Originally, Ethernet was a broadcast technology 10Base2 Terminator Repeate r Tee Connector 10BaseT and 100BaseT T stands for Twisted PairHub Hubs and repeaters are layer-1 devices, i.e. physical only

Ethernet CSMA/CD 39 Carrier sense multiple access with collision detection Key insight: wired protocol allows us to sense the medium Algorithm Sense for carrier (signal from another host) If carrier is present, wait for it to end 1. 2. Send a frame and sense for collision If no collision, then frame has been delivered If collision, abort immediately 3. 4. 5. 6. Sending would cause a collision and waste time Why keep sending if the frame is already corrupted? Perform exponential backoff then retransmit

802.3 Ethernet Header 40 Bytes: 1 6 6 2 Preambl e SF Sourc e Dest. Lengt h 0-1500 0-46 Data Pad 4 Checksu m Preamble is 7 bytes of 10101010. Why? Start Frame (SF) is 10101011 Source and destination are MAC addresses 7 E.g. 00:45:A5:F3:25:0C Broadcast: FF:FF:FF:FF:FF:FF Minimum packet length of 64 bytes, hence

CSMA/CD Collisions 41 Collisions can occur Collisions are quickly detected and aborted Note the role of distance, propagation delay, and frame length Spatial Layout of Hosts t0 Time A B C D t1 B notices the collision D notices the collision

Distance 42 Suppose we make the Ethernet cable longer Both senders finish sending before observing the collision Thus, they will both erroneously believe their transmissions were successful Spatial Layout of Hosts t0 A B C D t1 Time Collisio n

Packet Length 43 What if B sends a really short packet? Only one of the senders notices the collision t0 B’s packet may be corrupted, but it has no idea Time Spatial Layout of Hosts A B C D t1 D notices the collision

Minimum Packet Sizes & Cable Length 44 Why is the minimum packet size 64 bytes? 1. 2. 3. To give hosts enough time to detect collisions What is the relationship between packet size and cable length? Time t: Host A starts transmitting Time t d: Host B starts transmitting Time t 2*d: Host A detects the collision A B Propagation Delay (d) A B

Exercise 45 Derive the maximum cable length 1. 2. Min frame size: b Bandwidth: r Cable length: l Propagation delay: d Speed of light (xmit one bit): c Time t 2*d: Host A detects the collision Must transmit bits for b/r 2*d A B Propagation Delay (d) A B

Minimum Packet Sizes & Cable Length 46 Why is the minimum packet size 64 bytes? 1. 2. 3. To give hosts enough time to detect collisions What is the relationship between packet size and cable length? Time t: Host A starts transmitting Time t d: Host B starts transmitting Time t 2*d: Host A detects the collision A 10 Mbps Ethernet Delay (d) Packet Propagation and cable lengths change for faster Ethernet A standards B B [min frame size / (2*bandwidth)] * light speed max cable length (64B*8) / (2*107bps) * (2.5*108mps) 6400 meters

Cable Length Examples 47 min frame size / (2*bandwidth) * light speed max cable length (64B*8) / (2*10Mbps) * (2.5*108mps) 6400 meters What is the max cable length if min frame size were changed to 1024 bytes? What is max cable length if bandwidth were changed to 1 Gbps ? 102.4 kilometers 64 meters What if you changed min packet size to 1024 bytes and bandwidth to 1 Gbps? 1024 meters

Ethernet CSMA/CD 48 Carrier sense multiple access with collision detection Algorithm Sense for carrier (signal from another host) If carrier is present, wait for it to end 1. 2. Send a frame and sense for collision If no collision, then frame has been delivered If collision, abort immediately 3. 4. 5. 6. Sending would cause a collision and waste time Why keep sending if the frame is already corrupted? Perform exponential backoff then retransmit

Exponential Backoff 49 When a sender detects a collision, send “jam signal” Make sure all hosts are aware of collision Jam signal is 32 bits long (plus header overhead) Exponential backoff operates in multiples of 512 bits (64 bytes) Called contention slots Select k [0, 2n – 1], where n number of sequential collisions Wait k * 51.2µs before retransmission n is capped at 10, frame dropped after 16 collisions

Exponential Backoff 50 Why is minimum backoff timer 512 bits? Minimum Ethernet packet size is also 512 bits 64 bytes * 8 512 bits Coincidence? Of course not. If the backoff time was 512 bits, a sender who waits and another who sends immediately can still collide

Maximum Packet Size 51 Maximum Transmission Unit (MTU): 1500 bytes Pros: Cons: Bit errors in long packets incur significant recovery penalty More bytes wasted on header information Higher per packet processing overhead Datacenters shifting towards Jumbo Frames 9000 bytes per packet

Long Live Ethernet 52 Today’s Ethernet is switched CSMA/CD is no longer necessary More on this later 1Gbps and 10Gbps Ethernet now common 100Gbps on the way Uses same old packet header Full duplex (send and receive at the same time) Auto negotiating (backwards compatibility) Can also carry power

53 Outline Framing Error Checking and Reliability Media Access Control Contention MAC Basics 802.3 Ethernet

802.3 Ethernet vs. Wireless 54 Ethernet has one shared collision domain Wireless radios have small range compared to overall system All hosts on a LAN can observe all transmissions Collisions are local Collision are at the receiver, not the sender Carrier sense (CS in CSMA) plays a different role 802.11 uses CSMA/CA not CSMA/CD Collision avoidance, rather than collision detection

Hidden Terminal Problem 55 Radios on the same network cannot always hear each other Collision ! A A cannot hear C B C C cannot hear A Hidden terminals mean that sender-side collision detection is useless

Exposed Terminal Problem 56 Carrier sense Carrier sensing is problematic in wireless detects a busy channel No collision No collision A B C D Carrier sense can erroneously reduce utilization

Reachability in Wireless 57 High level problem: Reachability in wireless is not transitive Just because A can reach B, and B can reach C, doesn’t mean A can reach C A B C D

Potential Protocol: MACA 58 Multiple Access with Collision Avoidance Developed in 1990Sense Host in the Sender’s channel Range Sender RTS Soft- reserve the channel RTS but no Successful CTS transmissio clear to n send The Channel receiver is idle is Host in Receiver’s busy Receiver CTS Data ACK Range

Collisions in MACA 59 What if sender does not receive CTS or ACK? Assume collision Enter exponential backoff mode

802.11 a.k.a. WiFi 60 Uses CSMA/CA, not MACA 802.11b Introduced in 1999 Uses the unlicensed 2.4 Ghz band Same band as cordless phones, microwave ovens 5.5 and 11 Mbps data rates Practical throughput with TCP is only 5.9 Mbps 11 channels (in the US). Only 1, 6, and 11 are orthogonal

Current Wifi Version: Wifi 7 (802.11be) 61 More spectrum: 2.4 Ghz, 5 Ghz, and 6Ghz bands Multiple Input Multiple Output (MIMO) Multiple send and receive antennas per devices (up to 16) Data streams from different devices are multiplexed across antennas Multi Link Operation 5Ghz and 6Ghz bands have many more orthogonal channels than 2.4Ghz band One device can send in parallel across multiple frequencies Advanced signal encoding techniques: 4096-QAM Each “symbol” that is transmitted encodes 12 bits, not 1

802.11 Media Access 65 MACA-style RTS/CTS is optional Default algorithm: Carrier Sense Multiple Access with Collision Avoidance CSMA/CA vs. CSMA/CD for Ethernet Carrier sensing and exponential backoff are (roughly) the same as Ethernet even though we know carrier sense doesn’t work very well in wireless networks Key observation: collisions can only be detected by the receiver So sender-side collision detection isn’t feasible Instead, try to avoid collisions in the first place

802.11 DCF and IFS 66 Distributed Coordination Function (DCF) based on Inter Frame Spacing (IFS) wait times DIFS – low priority, normal data packets, long wait PIFS – medium priority, used with Point Coordination Function (PCF), medium wait time SIFS – high priority, control packets (RTS, CTS, ACK, etc.), low wait time Contention interval: random wait time Sense the channel Sender Channel Busy DIFS PIFS SIFS Time Sense the channel Contention Transmit Data

802.11 DCF Example 67 Sense the channel SenseSense the the channel channel SIFS Transmit Data Sender 1 PIFS Sender 2 Channel Busy DIFS Sender 3 Contentio n Channel Busy Time Sense the

801.11 is Complicated 68 We’ve only scratched the surface of 802.11 Association – how do clients connect to access points? Scanning What Variable sending rates to combat noisy channels Infrastructure vs. ad-hoc vs. point-to-point Mesh networks and mesh routing Power saving optimizations How about roaming? do you sleep and also guarantee no lost messages? Security and encryption (WEP, WAP, 802.11x) This is why there are courses on wireless networking