Content

  1. Overview
  2. Link-Layer Services
    1. Framing
      1. Sentinel-Based - Character-Oriented
      2. Sentinel-Based - Bit-Oriented
    2. Link Access
      1. MAC Address
      2. Address Resolution Protocol (ARP)
      3. Medium Access Control
        1. Channelization
        2. Taking Turns
        3. Random Access
    3. Error Detection
      1. Cyclic Redundancy Check (CRC)

Overview

Transferring link-layer frames from one link-layer node to another.

  • Different link-layer protocols
  • Different frame size -> different MTU
  • Different frame structure
  • Framing
    • Encapsulate IP datagrams
  • Link access
    • Effectively utilize a link shared by multiple nodes
    • Medium access control
    • MAC address to identify source & destination
  • Reliable delivery
    • Used in high bit-error links e.g. WiFi
  • Flow control
    • Pacing between adjacent sending & receiving nodes
    • Seldom used by link-layer technologies
  • Error detection

Framing

Working in sequence of bits. Senders can control bit transmission easily; receivers need to identify the whole frame.

The structure specified by link-layer protocol.

Sentinel-Based - Character-Oriented
  • NIC collects each 8-bits can process it
  • Header + data + trailer are contained between 2 flag bytes
    • Escape bytes are prepended to flag byte to differentiate it from payload byte

Sentinel-Based - Bit-Oriented
  • Not concerned with byte boundaries
  • High-level data link control (HDLC): 01111110 as flag
    • To differentiate from payload, every 11111 is followed by a 0

MAC Address

  • IP: 32-bit

    • Network layer
    • Direction to destination IP subnet, no carrier information

  • MAC: 48-bit

    • Link layer
    • Burned in NIC ROM, sometimes S/W settable
Address Resolution Protocol (ARP)
  • Given IP of host B, determine MAC of host B
    • Different subnets: ARP to find MAC of nexthop router
    • Same subnet: ARP to find MAX of host B
      • Host A broadcasts ARP query packet containing B's IP
        • Destination MAC set to FF-FF-FF-FF-FF-FF
        • Host B unicast to A its MAC address
  • ARP table
    • <IP, MAC, TTL>
      • TTL: after how long will the mapping be forgotten
    • ARP request: source IP, source MAC
      • Cached by target host
    • ARP reply: dest MAC
      • Cached by requesting host
  • Router
    • ARP tables for each IP subnet
    • Receives a frame, extract IP datagram, sees destination IP
Medium Access Control

When 2 frames are transmitted into the same channel simultaneously, collision occurs, the resulting signals are garbled.

  • Collision domain: machines in the same collision domain contends for the network resource via medium access control protocol

  • Control

    • Channelization
      • Divide 1 physical channel into multiple logical channels, each user dedicatedly assigned one
    • Take turns
      • Orderly access, e.g. polling, token padding, ...
      • e.g. WiFi, Bluetooth, FDDI, IBM token ring, ...
    • Random access
      • Station always at full transmission rate
      • Colliding nodes repeatedly retransmit their frames at a random delay
      • e.g. WiFi, Ethernet
Channelization
  • Frequency division multiple access (FDMA)
    • e.g. broadcast radio & TV, analog cell phone
  • Time division multiple access (TDMA)
    • e.g. telephone backbone, GSM digital cell phone
  • Code division multiple access (CDMA)
    • Encoding scheme, different codes for different users
    • e.g. cell phones, 3G cellular
Taking Turns

  • Polling

    • Master polls from stations according to certain order
    • Issues
      • Polling overhead
      • Latency
      • Single point failure (master)

    • e.g. WiFi under PCT mode

  • Token-passing

    • A permit (token) passed from station to station
    • Issues
      • Token overhead
      • Latency
      • Single point failure (token)

    • e.g. FDDI

Random Access
  • How to detect collisions
  • How to recover from collisions (e.g. random delayed retransmission)
  • e.g. ALOHA/slotted ALOHA, CSMA, CSMA/CD, CSMA/CA
  • Pure ALOHA
    • Transmit whenever a station has data; waits for ACK
      • If no ACK, random backoff & retransmit
      • If failed repeatedly, give up
    • Receiver drops frame if interference detected
    • Increase active node -> increase traffic load -> increase collisions -> increase retransmissions -> increase traffic load
  • Carrier sense multiple access (CSMA)
    • Listen for carrier & act accordingly
    • Collisions still exist if propagation delay
  • CSMA + collision detection (CSMA/CD)
    • If no CD, station keeps sending the whole frame even when there's collition
    • Steps
      1. Carrier sensing before transmission
      2. Collision detection during transmission
      3. Aborts transmission if collision detected
    • Easy to detect for wired LANs
      • Measure signal strengths, compare transmitted & received signals
    • Difficult to detect for wireless LANs
      • Received signals overwhelmed by local transmission strength

Error Detection

  • Transport & network layer: internet checksum
    • Less overhead (16 bits)
    • Weaker protection
  • Link layer: cyclic redundancy check (CRC)
    • Stronger protection
    • More complex computation
Cyclic Redundancy Check (CRC)
  • Components
    • Frame D: k bits
    • Generator G: r+1 bits pattern, generates r checking bits
      • Wants r << k
    • r bit CRC generated s.t. T = <D,R> = D * 2^r + R is divisible by G
  • Receiver
    • Knows G
    • Receives T, divide by G
      • T = D * 2^r + R = nG -> D * 2^r = nG + R
      • If remainer != 0, error
    • Can detect burst errors less than r+1 bits
    • T+E, where E is error pattern, can be divisible by G if:
      • E == 0
      • E is divisible by G

References

results matching ""

    No results matching ""