5,DataLink Layer 5a-1
Chapter 5,The Data Link Layer
Our goals:
? understand principles
behind data link layer
services:
? error detection,
correction
? sharing a broadcast
channel,multiple access
? link layer addressing
? reliable data transfer,
flow control,done!
? instantiation and
implementation of various
link layer technologies
Overview:
? link layer services
? error detection,
correction
? multiple access protocols
and LANs
? link layer addressing,ARP
? specific link layer
technologies:
? Ethernet
? hibs,bridges,switches
5,DataLink Layer 5a-2
Link Layer,setting the context
5,DataLink Layer 5a-3
Link Layer,setting the context
? two physically connected devices:
? host-router,router-router,host-host
? unit of data,frame
application
transport
network
link
physical
network
link
physical
M
M
M
M
Ht
HtHn
HtHnHl MHtHnHl
framephys,link
data link
protocol
adapter card
5,DataLink Layer 5a-4
Link Layer Services
? Framing,link access:
? encapsulate datagram into frame,adding header,trailer
? implement channel access if shared medium,
? ?physical addresses? used in frame headers to identify
source,dest
? different from IP address!
? Reliable delivery between two physically connected
devices:
? we learned how to do this already (chapter 3)!
? seldom used on low bit error link (fiber,some twisted
pair)
? wireless links,high error rates
? Q,why both link-level and end-end reliability?
5,DataLink Layer 5a-5
Link Layer Services (more)
? Flow Control:
? pacing between sender and receivers
? 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
5,DataLink Layer 5a-6
Link Layer,Implementation
?implemented in,adapter”
? e.g.,PCMCIA card,Ethernet card
? typically includes,RAM,DSP chips,host bus
interface,and link interface
application
transport
network
link
physical
network
link
physical
M
M
M
M
Ht
HtHn
HtHnHl MHtHnHl
framephys,link
data link
protocol
adapter card
5,DataLink Layer 5a-7
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
5,DataLink Layer 5a-8
Parity Checking
Single Bit Parity:
Detect single bit errors
Two Dimensional Bit Parity:
Detect and correct single bit errors
0 0
5,DataLink Layer 5a-9
Internet checksum
Sender:
? treat segment contents
as sequence of 16-bit
integers
? checksum,addition (1?s
complement sum) of
segment contents
? sender puts checksum
value into UDP checksum
field
Receiver:
? compute checksum of
received segment
? check if computed checksum
equals checksum field value:
? NO - error detected
? YES - no error detected,
But maybe errors
nonethless? More later ….
Goal,detect,errors” (e.g.,flipped bits) in transmitted
segment (note,used at transport layer only)
5,DataLink Layer 5a-10
Checksumming,Cyclic Redundancy Check
? view data bits,D,as a binary number
? choose r+1 bit pattern (generator),G
? goal,choose r CRC bits,R,such that
? <D,R> exactly divisible by G (modulo 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 (ATM,HDCL)
5,DataLink Layer 5a-11
CRC Example
Want:
D.2r XOR R = nG
equivalently:
D.2r = nG XOR R
equivalently:
if we divide D.2r by
G,want reminder R
R = remainder[ ]D
.2r
G
5,DataLink Layer 5a-12
Multiple Access Links and Protocols
Three types of,links”:
? point-to-point (single wire,e.g,PPP,SLIP)
? broadcast (shared wire or medium; e.g,Ethernet,
Wavelan,etc.)
? switched (e.g.,switched Ethernet,ATM etc)
5,DataLink Layer 5a-13
Multiple Access protocols
? single shared communication channel
? two or more simultaneous transmissions by nodes,
interference
? only one node can send successfully at a time
? multiple access protocol:
? distributed algorithm that determines how stations share
channel,i.e.,determine when station can transmit
? communication about channel sharing must use channel itself!
? what to look for in multiple access protocols,
? synchronous or asynchronous
? information needed about other stations
? robustness (e.g.,to channel errors)
? performance
5,DataLink Layer 5a-14
Multiple Access protocols
?claim,humans use multiple access protocols
all the time
?class can "guess" multiple access protocols
? multiaccess protocol 1:
? multiaccess protocol 2:
? multiaccess protocol 3:
? multiaccess protocol 4:
5,DataLink Layer 5a-15
MAC Protocols,a taxonomy
Three broad classes:
? Channel Partitioning
? divide channel into smaller,pieces” (time slots,
frequency)
? allocate piece to node for exclusive use
? Random Access
? allow collisions
?“recover” from collisions
?,Taking turns”
? tightly coordinate shared access to avoid collisions
Goal,efficient,fair,simple,decentralized
5,DataLink Layer 5a-16
Channel Partitioning MAC protocols,TDMA
TDMA,time division multiple access
? access to channel in "rounds"
? each station gets fixed length slot (length = pkt
trans time) in each round
? unused slots go idle
? example,6-station LAN,1,3,4 have pkt,slots 2,5,6
idle
5,DataLink Layer 5a-17
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 pkt,frequency
bands 2,5,6 idle
fr
eq
ue
nc
y b
an
ds
5,DataLink Layer 5a-18
Channel Partitioning (CDMA)
CDMA (Code Division Multiple Access)
? unique,code” assigned to each user; ie,code set partitioning
? used mostly in wireless broadcast channels (cellular,
satellite,etc)
? all users share same frequency,but each user has own
“chipping” sequence (ie,code) to encode data
? encoded signal = (original data) X (chipping sequence)
? decoding,inner-product of encoded signal and chipping
sequence
? allows multiple users to,coexist” and transmit
simultaneously with minimal interference (if codes are
“orthogonal”)
5,DataLink Layer 5a-19
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 trasnmitting 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:
? slotted ALOHA
? ALOHA
? CSMA and CSMA/CD
5,DataLink Layer 5a-20
Slotted Aloha
? time is divided into equal size slots (= pkt trans,time)
? node with new arriving pkt,transmit at beginning of
next slot
? if collision,retransmit pkt in future slots with
probability p,until successful.
Success (S),Collision (C),Empty (E) slots
5,DataLink Layer 5a-21
Slotted Aloha efficiency
Q,what is max fraction slots successful?
A,Suppose N stations have packets to send
? each transmits in slot with probability p
? prob,successful transmission S is:
by single node,S= p (1-p)(N-1)
by any of N nodes
S = Prob (only one transmits)
= N p (1-p)(N-1)
… choosing optimum p as n -> infty,..
= 1/e =,37 as N -> infty
At best,channel
use for useful
transmissions 37%
of time!
5,DataLink Layer 5a-22
Pure (unslotted) ALOHA
? unslotted Aloha,simpler,no synchronization
? pkt needs transmission:
? send without awaiting for beginning of slot
? collision probability increases:
? pkt sent at t0 collide with other pkts sent in [t0-1,t0+1]
5,DataLink Layer 5a-23
Pure Aloha (cont.)
P(success by given node) = P(node transmits),
P(no other node transmits in [p0-1,p0],
P(no other node transmits in [p0-1,p0]
= p, (1-p), (1-p)
P(success by any of N nodes) = N p, (1-p), (1-p)
… choosing optimum p as n -> infty,..
= 1/(2e) =,18
G = offered load = Np
0.5 1.0 1.5 2.0
0.1
0.2
0.3
0.4
Pure Aloha
Slotted Aloha protocol constrainseffective channel
throughput!
5,DataLink Layer 5a-24
CSMA,Carrier Sense Multiple Access)
CSMA,listen before transmit:
? If channel sensed idle,transmit entire pkt
? If channel sensed busy,defer transmission
? Persistent CSMA,retry immediately with
probability p when channel becomes idle (may cause
instability)
? Non-persistent CSMA,retry after random interval
? human analogy,don?t interrupt others!
5,DataLink Layer 5a-25
CSMA collisions
collisions can occur:
propagation delay means
two nodes may not year
hear each other?s
transmission
collision:
entire packet transmission
time wasted
spatial layout of nodes along ethernet
note:
role of distance and
propagation delay in
determining collision prob.
5,DataLink Layer 5a-26
CSMA/CD (Collision Detection)
CSMA/CD,carrier sensing,deferral as in CSMA
? collisions detected within short time
? colliding transmissions aborted,reducing channel
wastage
? persistent or non-persistent retransmission
?collision detection:
? easy in wired LANs,measure signal strengths,
compare transmitted,received signals
? difficult in wireless LANs,receiver shut off while
transmitting
?human analogy,the polite conversationalist
5,DataLink Layer 5a-27
CSMA/CD collision detection
5,DataLink Layer 5a-28
,Taking Turns” MAC protocols
channel partitioning MAC protocols:
? share channel efficiently 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!
5,DataLink Layer 5a-29
,Taking Turns” MAC protocols
Polling:
? master node
“invites” slave nodes
to transmit in turn
? Request to Send,
Clear to Send msgs
? concerns:
? polling overhead
? latency
? single point of
failure (master)
Token passing:
? control token passed from
one node to next
sequentially.
? token message
? concerns:
? token overhead
? latency
? single point of failure (token)
5,DataLink Layer 5a-30
Reservation-based protocols
Distributed Polling:
? time divided into slots
? begins with N short reservation slots
? reservation slot time equal to channel end-end propagation
delay
? station with message to send posts reservation
? reservation seen by all stations
? after reservation slots,message transmissions ordered by
known priority
Chapter 5,The Data Link Layer
Our goals:
? understand principles
behind data link layer
services:
? error detection,
correction
? sharing a broadcast
channel,multiple access
? link layer addressing
? reliable data transfer,
flow control,done!
? instantiation and
implementation of various
link layer technologies
Overview:
? link layer services
? error detection,
correction
? multiple access protocols
and LANs
? link layer addressing,ARP
? specific link layer
technologies:
? Ethernet
? hibs,bridges,switches
5,DataLink Layer 5a-2
Link Layer,setting the context
5,DataLink Layer 5a-3
Link Layer,setting the context
? two physically connected devices:
? host-router,router-router,host-host
? unit of data,frame
application
transport
network
link
physical
network
link
physical
M
M
M
M
Ht
HtHn
HtHnHl MHtHnHl
framephys,link
data link
protocol
adapter card
5,DataLink Layer 5a-4
Link Layer Services
? Framing,link access:
? encapsulate datagram into frame,adding header,trailer
? implement channel access if shared medium,
? ?physical addresses? used in frame headers to identify
source,dest
? different from IP address!
? Reliable delivery between two physically connected
devices:
? we learned how to do this already (chapter 3)!
? seldom used on low bit error link (fiber,some twisted
pair)
? wireless links,high error rates
? Q,why both link-level and end-end reliability?
5,DataLink Layer 5a-5
Link Layer Services (more)
? Flow Control:
? pacing between sender and receivers
? 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
5,DataLink Layer 5a-6
Link Layer,Implementation
?implemented in,adapter”
? e.g.,PCMCIA card,Ethernet card
? typically includes,RAM,DSP chips,host bus
interface,and link interface
application
transport
network
link
physical
network
link
physical
M
M
M
M
Ht
HtHn
HtHnHl MHtHnHl
framephys,link
data link
protocol
adapter card
5,DataLink Layer 5a-7
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
5,DataLink Layer 5a-8
Parity Checking
Single Bit Parity:
Detect single bit errors
Two Dimensional Bit Parity:
Detect and correct single bit errors
0 0
5,DataLink Layer 5a-9
Internet checksum
Sender:
? treat segment contents
as sequence of 16-bit
integers
? checksum,addition (1?s
complement sum) of
segment contents
? sender puts checksum
value into UDP checksum
field
Receiver:
? compute checksum of
received segment
? check if computed checksum
equals checksum field value:
? NO - error detected
? YES - no error detected,
But maybe errors
nonethless? More later ….
Goal,detect,errors” (e.g.,flipped bits) in transmitted
segment (note,used at transport layer only)
5,DataLink Layer 5a-10
Checksumming,Cyclic Redundancy Check
? view data bits,D,as a binary number
? choose r+1 bit pattern (generator),G
? goal,choose r CRC bits,R,such that
? <D,R> exactly divisible by G (modulo 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 (ATM,HDCL)
5,DataLink Layer 5a-11
CRC Example
Want:
D.2r XOR R = nG
equivalently:
D.2r = nG XOR R
equivalently:
if we divide D.2r by
G,want reminder R
R = remainder[ ]D
.2r
G
5,DataLink Layer 5a-12
Multiple Access Links and Protocols
Three types of,links”:
? point-to-point (single wire,e.g,PPP,SLIP)
? broadcast (shared wire or medium; e.g,Ethernet,
Wavelan,etc.)
? switched (e.g.,switched Ethernet,ATM etc)
5,DataLink Layer 5a-13
Multiple Access protocols
? single shared communication channel
? two or more simultaneous transmissions by nodes,
interference
? only one node can send successfully at a time
? multiple access protocol:
? distributed algorithm that determines how stations share
channel,i.e.,determine when station can transmit
? communication about channel sharing must use channel itself!
? what to look for in multiple access protocols,
? synchronous or asynchronous
? information needed about other stations
? robustness (e.g.,to channel errors)
? performance
5,DataLink Layer 5a-14
Multiple Access protocols
?claim,humans use multiple access protocols
all the time
?class can "guess" multiple access protocols
? multiaccess protocol 1:
? multiaccess protocol 2:
? multiaccess protocol 3:
? multiaccess protocol 4:
5,DataLink Layer 5a-15
MAC Protocols,a taxonomy
Three broad classes:
? Channel Partitioning
? divide channel into smaller,pieces” (time slots,
frequency)
? allocate piece to node for exclusive use
? Random Access
? allow collisions
?“recover” from collisions
?,Taking turns”
? tightly coordinate shared access to avoid collisions
Goal,efficient,fair,simple,decentralized
5,DataLink Layer 5a-16
Channel Partitioning MAC protocols,TDMA
TDMA,time division multiple access
? access to channel in "rounds"
? each station gets fixed length slot (length = pkt
trans time) in each round
? unused slots go idle
? example,6-station LAN,1,3,4 have pkt,slots 2,5,6
idle
5,DataLink Layer 5a-17
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 pkt,frequency
bands 2,5,6 idle
fr
eq
ue
nc
y b
an
ds
5,DataLink Layer 5a-18
Channel Partitioning (CDMA)
CDMA (Code Division Multiple Access)
? unique,code” assigned to each user; ie,code set partitioning
? used mostly in wireless broadcast channels (cellular,
satellite,etc)
? all users share same frequency,but each user has own
“chipping” sequence (ie,code) to encode data
? encoded signal = (original data) X (chipping sequence)
? decoding,inner-product of encoded signal and chipping
sequence
? allows multiple users to,coexist” and transmit
simultaneously with minimal interference (if codes are
“orthogonal”)
5,DataLink Layer 5a-19
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 trasnmitting 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:
? slotted ALOHA
? ALOHA
? CSMA and CSMA/CD
5,DataLink Layer 5a-20
Slotted Aloha
? time is divided into equal size slots (= pkt trans,time)
? node with new arriving pkt,transmit at beginning of
next slot
? if collision,retransmit pkt in future slots with
probability p,until successful.
Success (S),Collision (C),Empty (E) slots
5,DataLink Layer 5a-21
Slotted Aloha efficiency
Q,what is max fraction slots successful?
A,Suppose N stations have packets to send
? each transmits in slot with probability p
? prob,successful transmission S is:
by single node,S= p (1-p)(N-1)
by any of N nodes
S = Prob (only one transmits)
= N p (1-p)(N-1)
… choosing optimum p as n -> infty,..
= 1/e =,37 as N -> infty
At best,channel
use for useful
transmissions 37%
of time!
5,DataLink Layer 5a-22
Pure (unslotted) ALOHA
? unslotted Aloha,simpler,no synchronization
? pkt needs transmission:
? send without awaiting for beginning of slot
? collision probability increases:
? pkt sent at t0 collide with other pkts sent in [t0-1,t0+1]
5,DataLink Layer 5a-23
Pure Aloha (cont.)
P(success by given node) = P(node transmits),
P(no other node transmits in [p0-1,p0],
P(no other node transmits in [p0-1,p0]
= p, (1-p), (1-p)
P(success by any of N nodes) = N p, (1-p), (1-p)
… choosing optimum p as n -> infty,..
= 1/(2e) =,18
G = offered load = Np
0.5 1.0 1.5 2.0
0.1
0.2
0.3
0.4
Pure Aloha
Slotted Aloha protocol constrainseffective channel
throughput!
5,DataLink Layer 5a-24
CSMA,Carrier Sense Multiple Access)
CSMA,listen before transmit:
? If channel sensed idle,transmit entire pkt
? If channel sensed busy,defer transmission
? Persistent CSMA,retry immediately with
probability p when channel becomes idle (may cause
instability)
? Non-persistent CSMA,retry after random interval
? human analogy,don?t interrupt others!
5,DataLink Layer 5a-25
CSMA collisions
collisions can occur:
propagation delay means
two nodes may not year
hear each other?s
transmission
collision:
entire packet transmission
time wasted
spatial layout of nodes along ethernet
note:
role of distance and
propagation delay in
determining collision prob.
5,DataLink Layer 5a-26
CSMA/CD (Collision Detection)
CSMA/CD,carrier sensing,deferral as in CSMA
? collisions detected within short time
? colliding transmissions aborted,reducing channel
wastage
? persistent or non-persistent retransmission
?collision detection:
? easy in wired LANs,measure signal strengths,
compare transmitted,received signals
? difficult in wireless LANs,receiver shut off while
transmitting
?human analogy,the polite conversationalist
5,DataLink Layer 5a-27
CSMA/CD collision detection
5,DataLink Layer 5a-28
,Taking Turns” MAC protocols
channel partitioning MAC protocols:
? share channel efficiently 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!
5,DataLink Layer 5a-29
,Taking Turns” MAC protocols
Polling:
? master node
“invites” slave nodes
to transmit in turn
? Request to Send,
Clear to Send msgs
? concerns:
? polling overhead
? latency
? single point of
failure (master)
Token passing:
? control token passed from
one node to next
sequentially.
? token message
? concerns:
? token overhead
? latency
? single point of failure (token)
5,DataLink Layer 5a-30
Reservation-based protocols
Distributed Polling:
? time divided into slots
? begins with N short reservation slots
? reservation slot time equal to channel end-end propagation
delay
? station with message to send posts reservation
? reservation seen by all stations
? after reservation slots,message transmissions ordered by
known priority
