Chapter 6

The Link
Layer
and LANs

Computer
Networking: A Top-
Down Approach
8th edition
Jim Kurose, Keith Ross
Pearson, 2020
Link layer and LANs: our goals
 understand principles  instantiation,
behind link layer implementation of
services: various link layer
• error detection, correction technologies
• sharing a broadcast
channel: multiple access
• link layer addressing
• local area networks:
Ethernet, VLANs
 datacenter networks

Link Layer: 6-2

Link layer, LANs: roadmap
 introduction
 error detection, correction
 multiple access protocols
 LANs
• addressing, ARP
• Ethernet
• switches
• VLANs  a day in the life of a web
 link virtualization: MPLS request
 data center networking

Link Layer: 6-3

Link layer: introduction
terminology: mobile network
 hosts and routers: nodes national or global ISP

 communication channels that

connect adjacent nodes along
communication path: links
• wired
• wireless
• LANs
 layer-2 packet: frame, datacenter
network
encapsulates datagram
link layer has responsibility of
transferring datagram from one node enterprise
to physically adjacent node over a link network

Link Layer: 6-4

Link layer: context
 datagram transferred by transportation analogy:
different link protocols  trip from Princeton to
over different links: Lausanne
• limo: Princeton to JFK
• e.g., WiFi on first link, • plane: JFK to Geneva
Ethernet on next link • train: Geneva to Lausanne
 each link protocol  tourist = datagram
provides different  transport segment =
services communication link
• e.g., may or may not  transportation mode = link-
provide reliable data layer protocol
transfer over link  travel agent = routing
algorithm

Link Layer: 6-5

Link layer: services
 framing, link access: …
• encapsulate datagram into frame, …
adding header, trailer
• channel access if shared medium
• “MAC” addresses in frame headers
identify source, destination (different
from IP address!)
 reliable delivery between adjacent
nodes
• we already know how to do this!
• seldom used on low bit-error links
• wireless links: high error rates
• Q: why both link-level and end-end
reliability?
Link Layer: 6-6
Link layer: services (more)
 flow control: …
• pacing between adjacent sending and
receiving nodes
…
 error detection:
• errors caused by signal attenuation,
noise.
• receiver detects errors, signals
retransmission, or drops frame
 error correction:
• receiver identifies and corrects bit
error(s) without retransmission
 half-duplex and full-duplex:
• with half duplex, nodes at both ends of
link can transmit, but not at same time
Link Layer: 6-7
Where is the link layer implemented?

 in each-and-every host
 link layer implemented in
network interface card (NIC)
or on a chip application
transport
cpu memory
network
• Ethernet, WiFi card or chip link

• implements link, physical layer host bus

(e.g., PCI)
 attaches into host’s system link
controller

physical
buses physical

 combination of hardware,
network interface
software, firmware

Link Layer: 6-8

Interfaces communicating
application application
transport transport
cpu memory memory CPU
datagra network network
link link
m

linkh datagra controller controller

link
datagra
link
m physical physical m
physical physical

sending side: receiving side:

 encapsulates datagram in  looks for errors, reliable
frame data transfer, flow control,
 adds error checking bits, etc.
reliable data transfer, flow  extracts datagram, passes
control, etc. to upper layer at receiving
side Link Layer: 6-9
Link layer, LANs: roadmap
 introduction
 error detection, correction
 multiple access protocols
 LANs
• addressing, ARP
• Ethernet
• switches
• VLANs  a day in the life of a
 link virtualization: MPLS web request
 data center networking
Link Layer: 6-10
Error detection
EDC: error detection and correction bits (e.g., redundancy)
D: data protected by error checking, may include header fields

datagram datagram Error detection not

otherwise
100% reliable!
all  protocol may miss
bits in D’ N
OK detected some errors, but
? error
d data bits rarely
D EDC D’ EDC’  larger EDC field
yields better
bit-error prone link detection and
correction
Link Layer: 6-11
Parity checking
single bit parity: two-dimensional bit parity:
 detect single bit errors  detect and correct single bit errors

row parity
0111000110101011 1
d1,1 ... d1,j d1,j+1
d data d2,1 ... d2,j d2,j+1
bits ... ... ... ...
parity
bit di,1 ... di,j di,j+1
column
parity ...
Even parity: set di+1,1 di+1,j di+1,j+1
parity bit so there
is an even number detected 1 0 1 0 1
no errors: 1 0 1 0 1 1 1
of 1’s and 1 0 1 1 0 parity
11110 0 correctable 0 error
01110 1 single-bit 0 1 1 1 0 1
10101 0 error: 1 0 1 0 1 0
parity
error
Link Layer: 6-12
Internet checksum (review)
Goal: detect errors (i.e., flipped bits) in transmitted segment

sender: receiver:
 treat contents of UDP  compute checksum of received
segment (including UDP segment
header fields and IP
addresses) as sequence of  check if computed checksum
16-bit integers equals checksum field value:
 checksum: addition (one’s • not equal - error detected
complement sum) of • equal - no error detected. But
segment content maybe errors nonetheless?
 checksum value put into More later ….
UDP checksum field

Transport Layer: 3-13

Cyclic Redundancy Check (CRC)
 more powerful error-detection coding
 D: data bits (given, think of these as a binary number)
 G: bit pattern (generator), of r+1 bits (given)
r CRC bits
d data bits
D R bit pattern
<D,R> = D* 2r XOR R formula for bit pattern

goal: choose r CRC bits, R, such that <D,R> exactly divisible by G (mod
2)
• receiver knows G, divides <D,R> by G. If non-zero remainder: error detected!
• can detect all burst errors less than r+1 bits
• widely used in practice (Ethernet, 802.11 WiFi)
Link Layer: 6-14
 Cyclic Redundancy Check (CRC): example
We want: G 1 0 10 1 1
D.2r XOR R = nG 1 0 0 1 1 0 1 1 1 00 0 0
or equivalently: 1 0 0 1
D.2r = nG XOR R 1 0 1 D*2r
0 0 0
or equivalently: 1 0 1 0
if we divide D.2r by G, want 1 0 0 1
remainder R to satisfy: 1 1 0
0 0 0
D.2r 1 1 0 0
R = remainder [ ] 1 0 0 1
G 1 0 1 0
1 0 0 1
0 1 1
R
* Check out the online interactive exercises for more examples: h ttp://gaia.cs.umass.edu/kurose_ross/interactive/
Link Layer: 6-15
 Link layer, LANs: roadmap
 introduction
 error detection, correction
 multiple access protocols
 LANs
• addressing, ARP
• Ethernet
• switches
• VLANs
 link virtualization: MPLS  a day in the life of a
 data center networking
web request

Link Layer: 6-16

Multiple access links, protocols
two types of “links”:
 point-to-point
• point-to-point link between Ethernet switch, host
• PPP for dial-up access
 broadcast (shared wire or medium)
• old-fashioned Ethernet
• upstream HFC in cable-based access network
• 802.11 wireless LAN, 4G/4G. satellite

shared wire (e.g., humans at a cocktail party

cabled Ethernet) shared radio: 4G/5G shared radio: WiFi shared radio: satellite
(shared air, acoustical)

Link Layer: 6-17

Multiple access protocols
 single shared broadcast channel
 two or more simultaneous transmissions by nodes: interference
• collision if node receives two or more signals at the same time

multiple access protocol

 distributed algorithm that determines how nodes share channel, i.e.,
determine when node can transmit
 communication about channel sharing must use channel itself!
• no out-of-band channel for coordination

Link Layer: 6-18

An ideal multiple access protocol
given: multiple access channel (MAC) of rate R bps

1. when one node wants to transmit, it can send at rate

R.
2. when M nodes want to transmit, each can send at
average rate R/M
3. fully decentralized:
• no special node to coordinate transmissions
• no synchronization of clocks, slots
4. simple

Link Layer: 6-19

MAC protocols: taxonomy
three broad classes:
 channel partitioning
• divide channel into smaller “pieces” (time slots, frequency,
code)
• 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 turns
Link Layer: 6-20
Channel partitioning MAC protocols: TDMA
TDMA: 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 packets to send,
slots 2,5,6 idle
6-slot 6-slot
frame frame
1 3 4 1 3 4

Link Layer: 6-21

Channel partitioning MAC protocols: FDMA
FDMA: frequency division multiple access
 channel spectrum divided into frequency bands
 each station assigned fixed frequency band
 unused transmission time in frequency bands go idle
 example: 6-station LAN, 1,3,4 have packet to send, frequency
bands 2,5,6 idle
time

frequency bands
FDM cable

Link Layer: 6-22

Random access protocols
 when node has packet to send
• transmit at full channel data rate R.
• no a priori coordination among nodes
 two or more transmitting nodes: “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, CSMA/CA

Link Layer: 6-23

Slotted ALOHA
assumptions: operation:
 all frames same size  when node obtains fresh
 time divided into equal size frame, transmits in next slot
slots (time to transmit 1 • if no collision: node can
frame) send new frame in next
 nodes start to transmit only slot
slot beginning • if collision: node
 nodes are synchronized retransmits frame in each
subsequent slot with
 if 2 or more nodes transmit
probability p until success
in slot, all nodes detect
collision

randomization – why? Link Layer: 6-24

Slotted ALOHA
node 1 1 1 1 1

node 2 2 2 2 C: collision
S: success
node 3 3 3 3
E: empty
C E C S E C E S S

Pros: Cons:
 single active node can  collisions, wasting slots
continuously transmit at full  idle slots
rate of channel  nodes may be able to detect
 highly decentralized: only
collision in less than time to
slots in nodes need to be in transmit packet
sync
 simple  clock synchronization
Link Layer: 6-25
Slotted ALOHA: efficiency
efficiency: long-run fraction of successful slots (many
nodes, all with many frames to send)
 suppose: N nodes with many frames to send, each
transmits in slot with probability p
• prob that given node has success in a slot = p(1-p)N-1
• prob that any node has a success = Np(1-p)N-1
• max efficiency: find p* that maximizes Np(1-p)N-1
• for many nodes, take limit of Np*(1-p*)N-1 as N goes to
infinity, gives:
max efficiency = 1/e = .37
 at best: channel used for useful transmissions 37% of time!
Link Layer: 6-26
Pure ALOHA
 unslotted Aloha: simpler, no synchronization
• when frame first arrives: transmit immediately
 collision probability increases with no synchronization:
• frame sent at t0 collides with other frames sent in [t0-
1,t0+1] will overlap will overlap
with start of with end of
i’s frame i’s frame

t0 - 1 t0 t0 + 1
 pure Aloha efficiency: 18% !

Link Layer: 6-27

CSMA (carrier sense multiple access)
simple CSMA: listen before transmit:
• if channel sensed idle: transmit entire frame
• if channel sensed busy: defer transmission
 human analogy: don’t interrupt others!

CSMA/CD: CSMA with collision detection

• collisions detected within short time
• colliding transmissions aborted, reducing channel
wastage
• collision detection easy in wired, difficult with wireless
 human analogy: the polite conversationalist
Link Layer: 6-28
CSMA: collisions spatial layout of nodes

 collisions can still occur

with carrier sensing:
• propagation delay means two
nodes may not hear each
other’s just-started
transmission
 collision: entire packet
transmission time wasted
• distance & propagation delay
play role in in determining
collision probability

Link Layer: 6-29

CSMA/CD: spatial layout of nodes

 CSMA/CS reduces the

amount of time wasted in
collisions
• transmission aborted on
collision detection

Link Layer: 6-30

Ethernet CSMA/CD algorithm
1.NIC receives datagram from network layer, creates frame
2.If NIC senses channel:
if idle: start frame transmission.
if busy: wait until channel idle, then transmit
3.If NIC transmits entire frame without collision, NIC is done
with frame !
4.If NIC detects another transmission while sending: abort, send
jam signal
5.After aborting, NIC enters binary (exponential) backoff:
• after mth collision, NIC chooses K at random from {0,1,2, …, 2m-
1}. NIC waits K·512 bit times, returns to Step 2
• more collisions: longer backoff interval
Link Layer: 6-31
CSMA/CD efficiency
 Tprop = max prop delay between 2 nodes in LAN
 ttrans = time to transmit max-size frame
1
efficiency 
1  5t prop /ttrans
 efficiency goes to 1
• as tprop goes to 0
• as ttrans goes to infinity
 better performance than ALOHA: and simple, cheap,
decentralized!

Link Layer: 6-32

“Taking turns” MAC protocols
channel partitioning MAC protocols:
 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 MAC protocols
 efficient at low load: single node can fully utilize
channel
 high load: collision overhead
“taking turns” protocols
 look for best of both worlds!

Link Layer: 6-33

“Taking turns” MAC protocols
polling:
 master node “invites” other
nodes to transmit in turn data
poll
 typically used with “dumb”
devices master
 concerns: data

• polling overhead
• latency
• single point of failure slaves
(master)

Link Layer: 6-34

“Taking turns” MAC protocols
T
token passing:
 control token passed
from one node to next
(nothing
sequentially. to send)
 token message T
 concerns:
• token overhead
• latency
• single point of failure
(token)
data

Link Layer: 6-35

Cable access network: FDM, TDM and random access!

Internet frames, TV channels, control transmitted

downstream at different frequencies

cable headend

CMTS
…

splitter cable
cable modem
… modem
ISP termination system

 multiple downstream (broadcast) FDM channels: up to 1.6

Gbps/channel
 single CMTS transmits into channels
 multiple upstream channels (up to 1 Gbps/channel)
 multiple access: all users contend (random access) for certain
upstream channel time slots; others assigned TDM
Link Layer: 6-36
Cable access network:
MAP frame for
Interval [t1, t2]

Downstream channel i
CMTS
Upstream channel j

cable headend
t1 t2 Residences with cable modems

Minislots containing Assigned minislots containing cable modem

minislots request frames
upstream data frames

DOCSIS: data over cable service interface

specificaiton
 FDM over upstream, downstream frequency channels
 TDM upstream: some slots assigned, some have contention
• downstream MAP frame: assigns upstream slots
• request for upstream slots (and data) transmitted random
access (binary backoff) in selected slots Link Layer: 6-37
Summary of MAC protocols
 channel partitioning, by time, frequency or code
• Time Division, Frequency Division
 random access (dynamic),
• ALOHA, S-ALOHA, CSMA, CSMA/CD
• carrier sensing: easy in some technologies (wire), hard
in others (wireless)
• CSMA/CD used in Ethernet
• CSMA/CA used in 802.11
 taking turns
• polling from central site, token passing
• Bluetooth, FDDI, token ring
Link Layer: 6-38