Use LEFT and RIGHT arrow keys to navigate between flashcards;
Use UP and DOWN arrow keys to flip the card;
H to show hint;
A reads text to speech;
26 Cards in this Set
- Front
- Back
|
Functionality of Data-Link layer |
- Send blocks of data (frames) between physical devices - Regulate access to the physical medium (MAC) |
|
|
Example protocols/encodings |
Ethernet (802.3), Wireless (802.11), byte-oriented framing, bit-oriented framing, parity, checksum, Cyclic Redundancy Check (CRC) |
|
|
Framing: Byte oriented "Sentinel Approach" |
- adds START and END to frame - Problem: What if END appears in the data? - Solution: Add two DLE (data link escape) chars before END |
|
|
Framing: Byte oriented "Byte Counting" |
- length of data heads the frame |
|
|
Framing: Bit oriented "Bit Stuffing" |
- Add bit sequence sentinel to start and end of frame. - Sender insert 0 after five consecutive 1s - Receiver reads 11111 and - 111110 -> remove 0 (it was stuffed) - 111111 -> look one bit ahead - 1111110 -> EOF - 1111111 -> ERROR: discard frame |
|
|
Framing: Clock-based "SONET" |
- Synchronous Optical Network - Fixed-size frame with a special start sequence |
|
|
Error Detection/Correction: Parity |
- add extra bits to keep # of 1s even - 1D Parity: detects 1-bit and some 2-bit - 2D Parity: detects all 1-, 2-, and 3-bit errors, some 4-bit - %14 overhead |
|
|
Error Detection/Correction: Checksum |
- adds up the bytes in the data and puts the sum in data |
|
|
Error Detection/Correction: Cyclic Redundancy Check (CRC) |
- uses field theory to compute semi-unique value for message - Much better performance - Fixed overhead (usually 32 bits) - Quick to implement in hardware - 1/232 chance of missing error |
|
|
Reliability: Stop and Wait |
- bluetooth - Problems: underutilization..only 1 frame midair at a time - Example: 10Gbps link & 10ms delay...need 100 Mbit to fill the pipe with packets of size 1500B - Example: 1500B x 8bit/(2 x 10ms) = 600Kbps - Example: Utilization = .006% |
|
|
Reliability: Sliding window |
- multiple, un-ACKed frames midair - Window size = # of un-ACKed frames allowed |
|
|
Reliability: Pros and Cons of Error-checking @ data link layer |
- Cons: can’t guarantee no errors, not all applications want it, adds CPU and packet size overhead, error recovery requires buffer. - Pros: potentially better performance than app-level checking - In Practice: useful over lossy links (wifi, cell, satellite) |
|
|
MAC: Channel Partitioning |
- Divides resource into small pieces - Allocate one to each host - Example: Time Division Multi-Access (TDMA) - Example: Frequency Division Multi-Access (FDMA) |
|
|
MAC: Taking Turns |
- Closely coordinate to avoid collision - Example: Token ring networks |
|
|
MAC: Contention |
- Allow collisions, but use strategy to recover - Example: Wifi, Ethernet |
|
|
MAC: Contention -> Goals |
- Share the medium: - Two hosts sending at same time collide...interference - If no host sends, channel is idle - We want one user sending at any one time - High utilization: - TDMA is too low utilization - Contention = similar to circuit-switched network - Simple, distributed algorithm: - Multiple hosts that can’t directly coordinate - No complicated token-passing schemes |
|
|
MAC -> Ethernet: Carrier Sense Multiple Access with Collision Detection (CSMA/CD) -> Algorithm |
1. Sense for carrier 2. If present, wait for it to end (sending would collide) 3. Send a frame and sense for collision 4. If no collision, frame has been delivered 5. If collision, abort immediately 6. Exponential backoff then retransmit |
|
|
MAC -> Ethernet: Carrier Sense Multiple Access with Collision Detection (CSMA/CD) -> Exponential Backoff |
- When sender detect collision, send jam signal (32bits) - EB works in multiples of 512 bits - Select K from [0, 2n - 1], n = # of collisions - Wait K x 51.2μs before retransmit - n is capped at 10, frame dropped after 16 collisions |
|
|
MAC -> Ethernet: Minimum Packet Size |
- min_frame_size x light_speed/(2 x bandwidth) = max_cable_length - Example: (64B x 8) x (2.5 108mps) / (2 x 10Mbps) = 6400 meters - Don’t forget about unit conversions!! |
|
|
MAC -> Ethernet: Exponential Backoff revisited |
- 512 bit backoff timer - Minimum ethernet packet size: 64 bytes x 8 = 512 bits |
|
|
MAC -> Ethernet: Maximum Transmission Unit (MTU) |
- Maximum Transmission Unit (MTU): 1500 bytes - Pros: - Bit errors in too-long packets would incur big recovery penalty - Cons: - More bytes wasted on headers - Higher per-packet processing overhead - Datacenters use jumbo (9000 byte) MTU |
|
|
MAC -> WiFi: Ethernet vs Wireless |
- Ethernet has one shared collision domain - All hosts on LAN can observe all transmissions - Wireless radios have small range - Collisions are local - Collisions are at receiver, not sender - Carrier sense plays a different role - Wireless (802.11) uses Collision Avoidance (CA) instead of CD |
|
|
MAC -> WiFi: Hidden Terminal Problem |
- Radios on same network can’t always hear each other - Hidden terminals mean sender-side CD |
|
|
MAC -> WiFi: Exposed Terminal Problem |
- Carrier sense can erroneously reduce utilization - Two close radios broadcasting to others might hear one another and falsely detect a collision since the collision-causing signal wouldn’t reach the intended receiver anyway. |
|
|
MAC -> WiFi: Is Wireless Transitive? |
- Wireless is not transitive - A reaches B and B reaches C does NOT mean A reaches C |
|
|
Advantages/Limitations of bridge vs switched networks |
- Bridged Network: - Pros: - More scalable - Cons: - Higher overhead to establish network - Higher overhead for upkeep - Switched Network: - Pros: - High utilization - High reliability - No global control - Cons: - Unscalable |
