EEE 51101 -

Computers
Networks

Lecture
5
 The Data Link Layer
 Introduction Application
 Data Link Layer Services Presentation
 Error detection and Session
correction Transport
 Multiple access protocols
Network
Data Link
Physical
OSI Model
EEE51101 – Computers Networks 2
 Link Layer: Introduction
“link”
Terminology:
 hosts and routers are nodes
(bridges and switches too)
 communication channels
that connect adjacent nodes
along communication path
are links
 Layer 2 packet is a frame,
encapsulates datagram
data-link layer has responsibility
of transferring datagram from one
node to adjacent node over a link
EEE51101 – Computers Networks 3
 Data Link Layer Services
 Framing, link access:
 encapsulate datagram into frame, adding header,
trailer
 ‘physical addresses’ used in frame headers to identify
source and destination (different from IP address!)
 Reliable delivery between adjacent nodes
 a link-layer reliable-delivery service is achieved with
acknowledgments and retransmissions
 A link-layer reliable-delivery service is often used for
links that are prone to high error rates, ex: wireless
links
EEE51101 – Computers Networks 4
 Data Link Layer Services
 Flow Control: (Flow control techniques)
 pacing between adjacent sending and receiving nodes
 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
EEE51101 – Computers Networks 5
 Adaptors Communicating
 link layer implemented
in “adaptor” (NIC)
 sending side:  receiving side
 encapsulates datagram in  looks for errors, reliable
a frame data transfer, flow control,
 adds error checking bits, etc
reliable data transfer, flow  extracts datagram, passes
control, etc. to receiving node
datagram receiving
sending link layer protocol node
node
frame frame
adapter adapter
EEE51101 – Computers Networks 6
 Error Detection
 EDC= Error Detection and Correction bits (redundancy)
 D = Data protected by error checking, may include header
 Error detection not 100% reliable!
• protocol may miss some errors, but rarely
• larger EDC field yields better detection and correction

EEE51101 – Computers Networks 7

 Error Detection Techniques
 Parity checks
 Check-summing methods
 Cyclic Redundancy Checks

EEE51101 – Computers Networks 8

 Parity Checking
 Two Dimensional Bit Parity
 Single Bit Parity
 Detect and correct single bit
 Detect single bit
errors
errors

0 0

EEE51101 – Computers Networks 9

 Checksums
 Interpret the data as if it were a sequence
of integers and add them together to get an
integer result called a checksum
 Add in any carry bits too
 Append the checksum to the frame
 16 and 32 bit checksums are common and
are usually computed for a whole packet

EEE51101 – Computers Networks 10

 Example failure of checksums
Source Destination
data item integer data item integer
(binary) value (binary) value
0001 1 0011 3
0010 2 0000 0
0011 3 0001 1
0001 1 0011 3
Checksum 7 Checksum 7

EEE51101 – Computers Networks 11

 Cyclic Redundancy Check
 Sender wants to send D, a piece of data d bits long
 Sender and receiver agree a generator, G, a bit pattern
that is r + 1 bits long
 the sender will choose r additional bits: D = d+r
 Sender appends R (an additional sequence of r bits) to D
so that the resulting sequence is exactly divisible by G
using binary (modulo 2) arithmetic
 Receiver divides the received bit pattern by G and checks
whether the remainder is 0

EEE51101 – Computers Networks 12

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

D.2r
R = remainder[ ]
G

EEE51101 – Computers Networks 13

 Multiple Access Links and Protocols
 point-to-point
 Point-to-Point Protocol (PPP) for dial-up access
 point-to-point link between Ethernet switch and host
 broadcast (shared medium)
 traditional Ethernet
 upstream HFC
 802.11 wireless LAN

EEE51101 – Computers Networks 14

 Multiple Access protocols
 single shared broadcast 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 nodes
share channel, i.e., determine when node can
transmit
 communication about channel sharing must use
channel itself!
EEE51101 – Computers Networks 15
 MAC Protocols: a taxonomy
 It is necessary to coordinate the transmissions of
the active nodes. This coordination job is the
responsibility of the multiple access protocol.
 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”
 tightly coordinate shared access to avoid collisions
EEE51101 – Computers Networks 16
 Channel Partitioning: TDMA
TDMA: Time Division Multiple Access
 TDM (Time Division Multiplexing): channel divided into N
time slots, one per user; inefficient with low duty cycle
users and at light load.
 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 packets, slots 2,5,6
idle

EEE51101 – Computers Networks 17

 Channel Partitioning: 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 packets, frequency
bands 2,5,6 idle
frequency bands

EEE51101 – Computers Networks 18

 Channel Partitioning: CDMA
CDMA (Code Division Multiple Access)
 unique “code” assigned to each user; i.e., code set
partitioning
 used mostly in wireless broadcast channels (cellular,
satellite, etc)
 all users share same frequency, but each user has own
“chipping” sequence (i.e., 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”)
EEE51101 – Computers Networks 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 transmitting nodes -> “collision”,
 random access MAC protocol specifies:
 how to detect collisions
 how to recover from collisions
 Examples of random access MAC protocols:
 ALOHA
 slotted ALOHA
 CSMA, CSMA/CD, CSMA/CA

EEE51101 – Computers Networks 20

 Pure ALOHA
 If you have data to send, send the data
 while you are transmitting data, you receive any
data from another station, there has been a message
collision. All transmitting stations will need to try
resending "later".
 Disadvantages of
Pure ALOHA:
 Time is wasted
 Data is lost

21
EEE51101 – Computers Networks 21
 Slotted ALOHA
 all frames same size
 time divided into equal
size slots (time to
transmit 1 frame)
 nodes start to transmit
only at slot beginning
 nodes are synchronized
 if 2 or more nodes
transmit in slot, all
nodes detect collision

22
EEE51101 – Computers Networks 22
 Slotted ALOHA
 when node obtains  Pros:
fresh frame, transmits  single active node can
in next slot continuously transmit at
full rate of channel
 if no collision: node can  highly decentralized: only
send new frame in next slots in nodes need to be
slot in sync
 Simple
 if collision: node
retransmits frame in  Cons:
 collisions, wasting slots
each subsequent slot  idle slots
with prob. p until  clock synchronization
success 23
EEE51101 – Computers Networks 23
 CSMA (Carrier Sense Multiple
Access)
CSMA: listen before transmit:
 If channel sensed idle: transmit entire
frame
 If channel sensed busy, defer transmission
 Human analogy: don’t interrupt others!
- Listen before speaking.
- If someone else begins talking at the same time,
stop talking

EEE51101 – Computers Networks 24

 CSMA collisions
spatial layout of nodes
 collisions can still occur:
 propagation delay means
two nodes may not hear
each other’s transmission
 collision:
 entire packet transmission
time wasted

note:
role of distance & propagation
delay in determining collision
probability
EEE51101 – Computers Networks 25
 CSMA/CD (Collision Detection)
CSMA/CD: carrier sensing, deferral as in CSMA
 collisions detected within short time
 colliding transmissions aborted, reducing channel
wastage
 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

EEE51101 – Computers Networks 26

 CSMA/CD collision detection

EEE51101 – Computers Networks 27

 “Taking Turns” MAC protocols
 Token bus protocol
 each user given (in turn) an
opportunity to transmit
 user may only transmit if in
possession of the `token‘
 after transmitting (or not)
token passed to next user

EEE51101 – Computers Networks 28

 EEE51101 -
Computers
Networks

thank you
for your
attention