Computer Networks

5. Data Link Layer

Lszl Bszrmnyi

Computer Networks

Link Layer - 1

Nodes and Links

link

Hosts and routers are nodes

Comm. channels connecting
adjacent nodes are links
Wired and wireless links
LANs

A 2-PDU (L-PDU) is a frame,

encapsulates a datagram
Path over different link
protocols over different links
Ethernet WLAN Ethernet

data-link layer has responsibility of

transferring datagram from one node
to an adjacent node over a single link
Lszl Bszrmnyi

Computer Networks

Link Layer - 2

Link Layer Services

Framing, link access
Encapsulate datagram into frame, adding header, trailer
Channel access if shared medium (MAC)
Media Access Control protocols

Physical addresses used in frame headers to identify

source and destination
Different from IP address!

Reliable delivery between adjacent nodes

Transport layer learned a lot from the link layer (frame
numbering and retransmission if necessary)
Seldom used on low bit error link (fiber, some twisted pair)
Wireless links: high error rates
Lszl Bszrmnyi

Computer Networks

Link Layer - 3

Link Layer Services (more)

Flow Control
Sliding window protocols (as in the transport layer)

Error Detection
Errors caused by signal attenuation, noise.
Receiver detects presence of errors:
Signals sender for retransmission or drops frame

Error Correction
Receiver identifies and corrects bit error(s) without
resorting to retransmission

Half-duplex and full-duplex

With half duplex, nodes at both ends of link can
transmit, but not at same time
Lszl Bszrmnyi

Computer Networks

Link Layer - 4

Adapters Communicating
datagram
sending
node

frame

frame

adapter

adapter

Link layer implemented in

adapter (aka NIC)

Receiving side

Ethernet card, PCMCI card,

802.11 card

Sending side:
Encapsulates datagram in a
frame
Adds error checking bits, rdt,
flow control, etc.
Lszl Bszrmnyi

rcving
node

link layer protocol

Looks for errors, rdt, flow

control, etc
Extracts datagram, passes to
the receiving node

Adapter is semi-autonomous
Link & physical layers

Computer Networks

Link Layer - 5

Error Detection

EDC= Error Detection

and Correction bits
(redundancy)
D = Data protected
by error checking, may
include header fields

Error detection not 100% reliable!

Protocol may miss some errors, but rarely
Larger EDC field yields better detection and correction
Lszl Bszrmnyi

Computer Networks

Link Layer - 6

Parity Checking
Single Bit Parity:
Detect single bit errors

Two Dimensional Bit Parity:

Detect and correct single bit errors

Even (odd) parity

scheme
# of 1s in d+1 bits is
always even (odd)
Receiver checks this
Can detect 1 bit error
Insufficient for usual
error-bursts
Lszl Bszrmnyi

Computer Networks

Link Layer - 7

Cyclic Redundancy Check (CRC)

View data bits, D, as a binary number
Choose r+1 bit pattern (generator), G, leftmost bit being 1
Goal: choose r CRC bits, R, such that

<D,R> (d + r) exactly divisible by G (modulo 2, no carries: +,- XOR)

D*2r XOR R = n*G D*2r = n*G XOR R R = remainder(D*2r / G)
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 (ATM, HDLC); 8,12,16,32 bit G-s

Lszl Bszrmnyi

Computer Networks

Link Layer - 8

CRC Example
Want:
D.2r XOR R = nG
equivalently:
D.2r = nG XOR R
equivalently:
if we divide D.2r by G,
want remainder R
R = remainder[

Lszl Bszrmnyi

D.2r
G

Transmitted
d+r (9) bits:
101110 | 011

Computer Networks

Link Layer - 9

Bit Stuffing in general

Special pattern at start and end of frame
Flag: <01111110> (7EH) (contains 6 consecutive 1s)

Data transparency requirement

Data field must be allowed to include flag pattern
If the data contains 7EH, change it in a predefined way

Sender (hardware)
Adds (stuffs) an additional 0 bit after each 5
consecutive 1s

Receiver (hardware)
Sees 5 1 bits, followed by a 0: destuff the 0 bit

If no hardware support: use Byte Stuffing in sw.

Lszl Bszrmnyi

Computer Networks

Link Layer - 10

Bit Stuffing example

7
Lszl Bszrmnyi

10

5
Computer Networks

10
Link Layer - 11

Point to Point Data Link Control

One sender, one receiver, one link

Easier than broadcast link

No Media Access Control
No need for explicit MAC addressing
E.g., dialup link, ISDN line

Popular point-to-point DLC protocols:

PPP (point-to-point protocol)
HDLC: High level data link control
Advanced error detection and retransmission
mechanisms

Lszl Bszrmnyi

Computer Networks

Link Layer - 12

PPP Design Requirements [RFC 1557]

Packet framing
Encapsulation of any NL (not only IP) datagr. in DL frame
Ability to demultiplex upwards

Bit transparency
Must carry any bit pattern in the data field
May use byte-stuffing instead of bit-stuffing

Error detection (no correction)

Multiple types of links
Connection aliveness
Detect, signal link failure to network layer

Network layer address negotiation

Endpoints can learn/set each others network address
Lszl Bszrmnyi

Computer Networks

Link Layer - 13

PPP non-requirements

No error correction/recovery
No flow control
Out of order delivery OK
No need to support multipoint links (e.g., polling)
Error recovery, flow control, data re-ordering
all relegated to higher layers!

Lszl Bszrmnyi

Computer Networks

Link Layer - 14

PPP Data Frame

Flag
Every frame begins and ends with a flag byte (framing)

Address and Control

Currently do nothing and can be omitted

Protocol
Upper layer protocol (e.g, PPP-Link Control Protocol
(LCP), IP, IP Control Protocol (IPCP), AppleTalk, etc)

Default max. length for info: 1500 bytes

Lszl Bszrmnyi

Computer Networks

Link Layer - 15

Multiple Access Links and Protocols

Point-to-point links
E.g. PPP for dial-up access, or point-to-point link
between Ethernet switch and host

Broadcast links (shared wire or medium)

E.g. traditional Ethernet, or 802.11 wireless LAN (WiFi)

Lszl Bszrmnyi

Computer Networks

Link Layer - 16

Multiple Access (MAC) Protocols

Single shared broadcast channel
Access must be regulated

If two or more nodes transmit simultaneously:

interference
Only one node can send successfully at a time

Multiple access protocol

Distributed algorithm that determines how nodes share
channel, i.e., determine when a certain node can transmit
Communication about channel sharing must use the
same channel!

Lszl Bszrmnyi

Computer Networks

Link Layer - 17

Ideal Multiple Access Protocol

Assume a broadcast channel of rate R bps

The ideal requirement is

1. When 1 node transmits, it can send at rate R

2. When M nodes want to transmit, each can send
at an average rate R/M (fairness)
3. Fully decentralized
No special node to coordinate transmissions
No synchronization of clocks, no time-slots

4. Simple
Lszl Bszrmnyi

Computer Networks

Link Layer - 18

General MAC Protocol Classes

1. Channel Partitioning
Divide channel into smaller pieces
(time slots, frequency or code division)
Allocate piece to node for exclusive use

2. Random Access
Channel not divided, allow collisions
Recover from collisions

3. Taking turns
Tightly coordinate shared access to avoid collisions

Lszl Bszrmnyi

Computer Networks

Link Layer - 19

Channel Partitioning MAC protocols: TDMA

TDM (Time Division Multiplexing)
Channel divided into N time slots, one per user;

TDMA (Time Division Multiple Access )

Access to channel in "rounds"
Each station gets fixed length slot
(length = frame transmission time) in each round
Unused slots go idle
Example: 6-station LAN, 1,3,4 have frame, slots 2,5,6 idle

Lszl Bszrmnyi

Computer Networks

Link Layer - 20

Channel Partitioning MAC protocols: FDMA

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 pkt, frequency
bands 2,5,6 idle

Lszl Bszrmnyi

frequency bands

FDMA (Frequency
Division Multiple Access)

Computer Networks

Link Layer - 21

Channel Partitioning MAC protocols: CDMA

CDMA (Code Division Multiple Access)
Senders may send simultaneously, coding helps to
separate different sources
All users share same frequency, but each user has own
chipping sequence (i.e., code) to encode data
Allows code set partitioning (if codes are orthogonal)
Used mostly in wireless broadcast channels (cellular,
satellite, etc)
The code needs high frequency (chipping frequency)
Encoded signal = (original data) X (chipping sequence)
Decoding: inner-product of encoded signal and chipping
sequence
Multiple users can coexist with minimal interference
Lszl Bszrmnyi

Computer Networks

Link Layer - 22

CDMA Encode/Decode
di: ith data bit
cm: mth bit of the
code
Zi,m : mth bit of
the encoded
data bit
Makes no
sense with
one single
sender-receiver
pair
Lszl Bszrmnyi

Computer Networks

Link Layer - 23

CDMA: two-sender interference

Additive signals
E.g if 4 senders
send 1,1,1,-1:
The received
signal is 2
Receiver gets
the sum of all
channels: Z*

Each receiver
can recover its
channel, if the
codes are
chosen
orthogonally
Lszl Bszrmnyi

Computer Networks

Link Layer - 24

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 and slotted ALOHA
CSMA, CSMA/CD (Ethernet), CSMA/CA
Lszl Bszrmnyi

Computer Networks

Link Layer - 25

Slotted ALOHA
Assumptions

Operation

All frames same size (L)

Time is divided into
equal size slots (L/R),
time to transmit 1 frame
Nodes start to transmit
frames only at beginning
of slots
Nodes are synchronized
If 2 or more nodes
transmit in the same slot,
all nodes detect collision
Lszl Bszrmnyi

When node obtains fresh

frame, it transmits in next
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
Toss a coin, probability of
head: p, tails: 1-p
If head: retransmit
If tails: skip the slot

Computer Networks

Link Layer - 26

Slotted ALOHA

Slot evenets

Cons

Pros
Single active node can
continuously transmit
at full rate of channel
Highly decentralized:
only slots in nodes
need to be in sync
Simple
Lszl Bszrmnyi

Collisions and wasting

slots
Empty (idle) slots
Nodes may be able to
detect collision in less
than time to transmit
packet

Computer Networks

Link Layer - 27

Slotted Aloha efficiency

Efficiency is the long-run
fraction of successful slots
when theres many nodes, each
with many frames to send
Suppose N nodes with many
frames to send, each
transmits in a given slot with
probability p
Probability that others do not
transmit: (1-p)N-1
Probability of success of one
node in a slot = p(1-p)N-1
Probability that any node has
a success = Np(1-p)N-1
Lszl Bszrmnyi

For max efficiency with

N nodes, 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: 1/e = .37
(e: natural logarithm)

Computer Networks

At best: channel

used for useful

transmissions 37%
of time!
Link Layer - 28

Pure (unslotted) ALOHA

Unslotted Aloha: simpler, no synchronization
When frame first arrives
Transmit immediately

Collision probability increases

Frame sent at t0 may collide with other frames sent in [t0-1,t0+1]

Efficiency: half of that of slotted ALOHA: 18%

Lszl Bszrmnyi

Computer Networks

Link Layer - 29

CSMA (Carrier Sense Multiple Access)

spatial layout of nodes

CSMA
If channel sensed idle:
transmit entire frame
If channel sensed busy:
defer transmission

Collisions can still

occur
Two nodes may not
hear each others
transmission due to
propagation delay
Entire transmission time
wasted
Lszl Bszrmnyi

Computer Networks

Link Layer - 30

CSMA/CD (CSMA+Collision Detection)

CSMA/CD
Collisions detected fast
Colliding transmissions
aborted
Wasted time shorter

Collision detection:
Easy in wired LANs
Compare transmitted and
received signals

Difficult in wireless
LANs

Lszl Bszrmnyi

Computer Networks

Link Layer - 31

Taking Turns MAC protocols

Channel partitioning MAC protocols:
Share channel efficiently and fairly at high load
Inefficient at low (resp. bursty) load:
Delay in channel access
1/N bandwidth allocated even if only 1 active node!

Random access MAC protocols

Efficient at low (resp. bursty) load
Single node can fully utilize channel

High load
Collision overhead

Taking turns protocols

Look for best of both worlds!
Lszl Bszrmnyi

Computer Networks

Link Layer - 32

Taking Turns MAC protocols

Polling:
Master node
invites slave nodes
to transmit in turn
Concerns:
polling overhead
latency
single point of failure
(master)

Lszl Bszrmnyi

Token passing:
Control token passed from one
node to next sequentially
Token owner may send
(for a limited time)

Token message
Concerns:
token overhead
latency
token may get lost: must be
regenerated, but never duplicated

Computer Networks

Link Layer - 33

Summary of MAC protocols

What do we do with a shared media?
Channel Partitioning, by time, frequency or code
Time Division, Frequency Division, Code Division

Random partitioning (dynamic),

ALOHA, S-ALOHA, CSMA, CSMA/CD
Carrier sensing: easy in some technologies (wire), hard
in others (wireless)
CSMA/CD used in Ethernet

Taking Turns
polling from a central site
token passing
Lszl Bszrmnyi

Computer Networks

Link Layer - 34