Introduction

Data-link layer has responsibility of transferring IP datagram from one node to adjacent node over a single link.

MAC (Media Access Control) layer = data-link layer = layer 2

• Hosts and routers are nodes
• Communication channels that connect adjacent nodes are layer-3 links
• Each link may contain multiple layer-2 devices (e.g., switches)

Services:

• Framing
  • Add header, trailer to IP packet
  • Data-link addresses (completely independent of IP addresses) used in frame headers to identify source, dest
• Link access
  • Channel access if shared medium
• Flow control
  • Pacing between adjacent sending and receiving nodes
• Error detection
  • Errors caused by signal attenuation, noise
  • Receiver detects presence of errors and signals data-link layer of adjacent node for retransmission or drops frame
• Forward Error Correction (FEC)
  • Receiver identifies and corrects bit error(s) without resorting to retransmission
• Reliable delivery (rdt) between adjacent nodes
  • Rdt 3.0 is a common technique
  • Seldom used on low bit error links (fiber, twisted pair), but may be implemented in wireless networks

Terminology:

• In half-duplex mode, nodes at both ends of link can transmit, but not at the same time
• In full-duplex, bidirectional transfer happens concurrently

Multiple access protocols

Two types of links:

• Point-to-point
  • PPP for dial-up and DSL access
  • Dedicated cable between Ethernet switch and host
• Broadcast (shared wire/medium)
  • Traditional Ethernet
  • Upstream HFC
  • 802.11 wireless LAN, satellite

For a single shared broadcast channel,

• Two or more simultaneous transmissions by nodes is called interference or collision
• Link access protocol
  • Distributed algorithm that determines how nodes share channel
  • Communication about channel sharing must use the channel itself!

MAC Protocols, 3 broad classes:

• Channel Partitioning
  • Divide channel into smaller “pieces” (time slots, frequency, wavelengths)
  • Allocate piece to node for exclusive use
  • Share channel efficiently and fairly at high load
  • Inefficient at low load: delay in channel access, 1/N bandwidth allocated even if only 1 active node!
• Random Access
  • Channel not divided, allow collisions
  • Recover from collisions
  • Efficient at low load: single node can fully utilize channel
  • High load: potentially huge collision overhead
• Taking turns
  • Nodes take turns, but nodes with more to send can take longer turns

Channel Partitioning MAC protocols

• TDMA, Time Division Multiple Access
  • Access to channel in “rounds” (time frames)
  • Maximum throughput for a single user is R / N
• FDMA: frequency division multiple access
  • Channel spectrum divided into frequency bands

Random Access Protocols

• When node has packet to send
  • Transmit at full channel data rate R
• Two or more transmitting nodes cause collision
• Random access MAC protocol specifies
  • How to detect collisions
  • How to recover from collisions (e.g., via delayed retransmissions)
• Examples of random access MAC protocols
  • ALOHA, Slotted ALOHA
  • CSMA, CSMA/CD

Slotted ALOHA

Assumption:

• All frames same size
• Time is divided into equal size slots, time to transmit 1 frame
• Nodes start transmission only at beginning of slots
• If 2 or more nodes transmit in slot, all nodes detect collision

Operation:

• When node obtains fresh frame from IP, it transmits in the next time slot
• No collision, node can send new frame in next slot
• If collision, node retransmits frame in each subsequent slot with probability p until success

Pros:

• Single active node can continuously transmit at full rate of channel
• Reasonably decentralized: only slots need to be in sync
• Simple

Cons:

• Collisions
• Idle/empty slots
• Full slot wasted on collision
• Accurate clock synchronization is still a headache

Efficiency is the long-term fraction of successful slots when there are many nodes, each with many frames to send.

• Optimal p is 1 / N with N nodes
• Efficiency is 1 / e = 0.37

CSMA, Carrier Sense Multiple Access

• Remove slots and allow transmission at any time
• If channel sensed idle, transmit entire frame
• If channel sensed busy, defer transmission
• If collision is detected at the end of transfer, wait a random period of time, then retransmit

CSMA/CD, Collision Detection

• carrier sensing, deferral as in CSMA
• But now collisions are detected immediately
• Colliding transmissions aborted, reducing channel waste

Collision detection:

• Easy in wired LANs: measure signal strengths, compare transmitted, received signals
• Difficult in wireless LANs: receiver shut off while transmitting

Taking Turns MAC Protocols

• Polling
  • Master node invites slave nodes to transmit in turn
  • Concerns
    • Polling overhead
    • Latency
    • Single point of failure (master)
• Token passing
  • Control token passed from one node to next sequentially
  • Can send only if holding token
  • Concerns
    • Token overhead
    • Latency
    • Single point of failure (token)

Link-Layer Addressing

Network address:

• Transport layer
  • 16-bit port
  • Find correct application within a host
• Network layer
  • 32-bit IPv4, 128-bit IPv6
  • Find correct subnet and host on the Internet
• MAC (or LAN, physical, Ethernet)
  • 48-bit number in the adapter ROM
  • Find correct interface within a subnet

LAN address

• Each adapter in a LAN must have a unique LAN address
• Broadcast address = FF-FF-FF-FF-FF-FF
• MAC address allocation administered by IEEE
• Manufacturer buys portion of MAC address space
• Flat MAC addresses achieve portability
• Hierarchical IP addresses NOT portable

ARP, Address Resolution Protocol:

• Each IP node (host, router) on LAN has an ARP table
  • Contains IP/MAC address mappings for known LAN nodes
    • <IP address; MAC address; TTL>
    • TTL typically 20 min

For X to send a datagram to Y, X doesn’t know Y’s MAC address

1. X broadcasts ARP query, containing Y’s IP address
2. Y receives ARP packet, replies to X with its MAC address (unicast)
3. X caches IP/MAC mapping in ARP table

For X, in order to send datagram to Y in another LAN. X knows Y’s IP address. The inter router R has two interface, R1 for X, R2 for Y.

1. X broadcasts ARP with IP_R1, receive R1 MAC
2. X sends packet to R
   • MAC_X, MAC_R1, IP_X, IP_Y
3. R changes interface to R2
4. R2 broadcasts ARP, get Y MAC
5. R sends packet to Y
   • MAC_R2, MAC_Y, IP_X, IP_Y

DHCP, Dynamic Host Configuration Protocol

• Assigns IP address, netmask, DNS server, default router, and other parameters to end-hosts
• UDP (ports 67-68), using MAC-layer broadcasts to find available servers
  • Steps: Discovery –> Offer –> Request –> Lease (4 packets exchanged)
  • Client may receive multiple offers, must choose one
  • Leased IPs carry some TTL (expiration time)
  • Routers and switches may implement DHCP
• Routers may be configured to forward broadcast DHCP packets between subnets
  • One DHCP server may cover multiple LANs

Ethernet

• Dominant wired LAN technology
• Ethernet data rates
  • 10 GE [802.3ae]: 10 Gbps (2003 fiber, 2006 twisted pair)
  • 40/100 GE [IEEE 802.3ba]: 2010

Frame structure:

• 8-byte preamble (physical layer)
  • 7 bytes 10101010 followed by one byte 10101011
  • synchronizes receiver-sender clock rates
• 6-byte MAC addresses
  • dest first, then source
• 2-byte protocol type
  • IPv4(0x800), IPv6(0x86DD), ARP(0x806)
• 32-bit CRC checksum
• Minimum payload 46 bytes
• inter-frame gap 12 bytes

Ethernet CSMA/CD

• No slots
• carrier sense (CS)
  • Doesn’t transmit if sensing other is transmitting
• collision detection (CD)
  • Transmitting adapter aborts when sensing other is transmitting
• Before attempting a retransmission, adapter waits a random time, that is, random access
• Connectionless, no handshaking
• Unreliable, NO ACKs

Bit time is 1/ speed.

Exponential Backoff:

• Goal: adapt retransmission attempts to estimated load
  • Heavy load: random wait should be longer
• After m-th collision in a row
  • Choose integer $D \in [0, 2^m - 1]$;
  • then wait $512D$ bit times before retx

Efficiency:

• $d$ is max propagation delay between any two nodes in LAN
• $T$ is time to transmit frame

Ethernet Technology:

• Notation: [speed]Base[medium]
• Examples
  • 10base5 (thick coax 500m), 1000BaseLX (long-range fiber 5km)
• Now: 10GBaseT over CAT6 (55m), CAT6a (100m)
• Coax networks were daisy-chained, while copper and fiber run the star topology

Hubs and switches

Hubs

• Hubs were physical-layer repeaters
  • Bits coming from one link went out all other links
• No frame buffering
  • No CSMA/CD at hub: host adapters must detect collisions
• Backbone hubs interconnected other hubs
  • Increased max distance between nodes
• Additional limitations
  • No management functionality
  • All ports had to be same speed
• Similar to daisy-chaining, but with all connections in one place

Switches

• Link layer device
  • Stores and forwards Ethernet frames
  • Examines frame header and selectively forwards frame based on MAC dest address
  • When frame is to be forwarded on segment, uses CSMA/CD to access segment
• Transparent
  • Hosts are unaware of presence of switches
• Plug-and-play, self-learning
  • Switches do not need to be configured
• Modern switches can perform some IP functionality

Functions:

• A switch has a switch table
  • Entry: (MAC Address, Interface, TTL)
• Switch learns which hosts can be reached through which interfaces
  • When frame received, switch “learns” location of sender: incoming LAN segment
• If the entry is not found for destination, flood all but the source interface

Dedicated Access:

• Dedicated: hosts have direct connection to switch
  • No collisions; full duplex
• Switching: two unrelated transfers can be simultaneous, no collisions
• Buffering: two transfers towards the same destination can be simultaneous, no collisions
• Combinations of shared/dedicated and diverse (10/100/1000 Mbps) interfaces are possible

Reference

This is my class notes while taking CSCE 612 at TAMU. Credit to the instructor Dr. Loguinov.