COMPUTER NETWORKS

UNIT – II

DATA LINK LAYER

Contents
• Introduction
• Framing
• Error Detection and Correction
• Flow and Error Control
• Noiseless Channels
• Noisy Channels
• HDLC Protocol
• Point to Point Protocols
• Multiple Access Protocols
• LAN – Ethernet IEEE 802.5 – IEEE 802.11
• Random access, Controlled access, Channelization
 The Data Link Layer
• Essential property of a channel is that the bits are delivered in exactly the
same order in which they are sent.

• For ideal channel (no distortion, unlimited bandwidth and no delay), the
job of data link layer would be trivial. But limited bandwidth, distortions
and delay makes its job very difficult.

• Functions of Data Link Layer:

1. Providing a well-defined service interface to the network layer.
2. It adds reliability by detecting transmission errors.
3. Regulates the flow of data so that slow receivers are not swamped by
fast senders.
The Data Link Layer
• Data Link layer
- Takes the packets from network layer
- Encapsulates them into frames
• Each frame has a
- frame header
- field for holding the packet
- frame trailer
• Frame Management is what Data Link Layer does.
Framing
• Stream of data bits provided to data link layer may be corrupted during
transmission. Errors could be:
- Number of received bits does not match number of transmitted bits
- Change in bit value

• Transmission at data link layer starts with breaking up the bit stream
- Into discrete frames
- Computation of a checksum for each frame and
- Include the checksum into the frame before it is transmitted.

• Receiver computes its checksum for a receiving frame and if it is different

from the checksum that is being transmitted; then it has to deal with the
error.
Types of errors
• Single bit error - Only one bit in the data unit has changed.

• Burst error - Two or more bits in the data unit have changed.
Error Detection and Correction - Redundancy
• To detect or correct errors, extra (redundant) bits are added along with the
data.

• Two basic strategies to deal with errors

- Include only enough redundancy to allow the receiver to deduce

that an error has occurred (but not which error).
Error detecting codes.

- Include enough redundant information to enable the receiver to

know the exact no. of bits corrupted and their location in the
message.
Error correcting codes.
Error Correction

The two most common error correction mechanisms are:

1. Error correction by Retransmission.

- When an error is discovered, receiver asks the sender to
retransmit the entire data unit.

2. Forward Error Correction.

- Receiver can use an error-correcting mode or guess the
message by using redundant bits, which automatically corrects
certain errors.
 Error Coding
• Error Coding is a method of detecting and correcting the errors to ensure
information is transferred intact from source to destination.

• Redundancy is achieved through various coding schemes where

relationship between redundant bits and actual data bits must be known
to both sender and receiver to detect and correct errors.

• Ratio of redundant bits to data bits and robustness of the process are
important in coding schemes.

• Two categories of coding techniques:

- Block Coding
- Convolution Coding
Modular Arithmetic
• In coding, we need to use modulo-2 arithmetic. Operations in this
arithmetic use XOR for both addition and subtraction.

• In modulo-N arithmetic, we use only the integers in the range 0 to

N −1. If a number is greater than N, it is divided by N and remainder is
the result.
- Ex: If the modulus is 12, we use 0-11 inclusive.
- Modulo 12 arithmetic works like clock arithmetic.
- In clock arithmetic, if we add 2 hours to 11:00, we get 1:00.
 Block Coding
• In block coding, we divide our message into blocks, each of ‘k’ bits, called
Datawords.

• We add ‘r’ redundant bits to each block to make the length n = k + r. The
resulting n-bit blocks are called Codewords.

Datawords and Codewords in Block Coding

Block Coding
• In Block Coding, errors are detected using 2 conditions.
- Receiver has (or can find) a list of valid codewords.
- Original codeword has changed to an invalid codeword.

Process of error detection in block coding

 Example
• Let us assume that k = 2 and n = 3. Table shows the list of datawords and
codewords. Assume the sender encodes the dataword 01 as 011 and sends it to the
receiver. Consider the following cases:

• The receiver receives 011. It is a valid codeword. The receiver extracts the dataword
01 from it.

• The codeword is corrupted during transmission and 111 is received. This is not a
valid codeword and is discarded.

• The codeword is corrupted during transmission, and 000 is received. This is a valid
codeword. The receiver incorrectly extracts the dataword 00. Two corrupted bits
have made the error undetectable.
Example (Contd.)
• By adding more redundant bits to previous example, see if the receiver can correct
an error without knowing what was actually sent.

• We add 3 redundant bits to the 2-bit dataword to make 5-bit codeword. Table
shows the datawords and codewords.

• Assume the dataword is 01. The sender creates the codeword 01011.
• The codeword is corrupted during transmission, and 01001 is received. First, the
receiver finds that the received codeword is not in the table. This means an error
has occurred.
• The receiver, assuming that there is only 1 bit corrupted, uses the following
strategy to guess the correct dataword.
 Example (Contd.)
• Comparing the received codeword with the first codeword in the table (01001
versus 00000), the receiver decides that the first codeword is not the one that
was sent because there are two different bits.

• By the same reasoning, the original codeword cannot be the third or fourth one
in the table.

• The original codeword must be the second one in the table because this is the
only one that differs from the received codeword by 1 bit. The receiver replaces
01001 with 01011 and consults the table to find the dataword 01.
Hamming distance
• One of the key concepts in coding for error control is Hamming distance.
• The Hamming distance between two words is the number of differences
between the corresponding bits.
• The minimum Hamming distance, dmin is the smallest Hamming distance
between all possible pairs in a set of words which is used for designing a
code.
Ex: Let us find the Hamming distance between two pairs of words.

1. The Hamming distance d(000,011) is 2 because

2. The Hamming distance d(10101, 11110) is 3 because

Example
 Find all hamming distances in the below table

Solution:

The dmin in this case is 3.

 Error Detection & Correction
• Error Detection:
• To guarantee the detection of up to ‘s’ errors in all cases, the minimum
Hamming distance in a block code must be dmin = s + 1.
• The minimum Hamming distance for the previous example is 3.
• This code guarantees detection of up to 2 errors.

• Error Correction:
• To guarantee the correction of up to ‘t’ errors in all cases, the minimum
Hamming distance in a block code must be dmin = 2t + 1.

• A code scheme has a Hamming distance dmin = 4. What is the error detection
and correction capability of this scheme?
 Linear Block Codes
• Almost all block codes used today belong to a subset called Linear Block
Codes. A linear block code is a code in which the exclusive OR (XOR)
(modulo-2 addition) of any two valid codewords creates another valid
codeword.

Simple Parity-Check code

• A Simple Parity-Check (1-Dimensional Parity Check) code is a single-bit
error detecting code in which n = k + 1 with dmin = 2.

• Even parity – ensures that a codeword has an even number of 1’s.

• Odd parity – ensures that there are odd number of 1’s in the codeword.

• A simple parity-check code can detect an odd number of errors. It cannot

correct any errors.
Simple Parity-Check code
Simple Parity-Check code C(5,4)
Encoder and decoder for simple parity-check code

r0 = a0 + a1 +a2 +a3 s0 = b3 +b2 +b1 +b0 +q0

 Example
Let us look at some transmission scenarios. Assume the sender sends the dataword 1011.
The codeword created from this dataword is 10111, which is sent to the receiver. We
examine five cases:
1. No error occurs; the received codeword is 10111. The syndrome is 0. The dataword 1011 is
created.

2. One single-bit error changes a1 . The received codeword is 10011. The syndrome is 1. No
dataword is created.

3. One single-bit error changes r0 . The received codeword is 10110. The syndrome is 1. No
dataword is created.

4. An error changes r0 and a second error changes a3 .The received codeword is 00110. The
syndrome is 0. The dataword 0011 is created at the receiver. Note that here the dataword is
wrongly created due to the syndrome value.

5. Three bits a3, a2, and a1 are changed by errors. The received codeword is 01011. The
syndrome is 1. The dataword is not created. This shows that the simple parity check,
guaranteed to detect one single error, can also find any odd number of errors.
Two-dimensional parity-check code
• Performance can be improved by using two-dimensional parity check.

• In this method, data word is organized in rows and columns.

• Data to be sent are put in separate rows and columns.

• For each row and each column, 1 parity-check bit is calculated.

• The whole table is sent to the receiver, which finds the syndrome for each
row and each column.
Two-dimensional parity-check code
Two-dimensional parity-check code
Hamming codes
• Single parity bit can only detect error, not correct it.

• Hamming code is an important error correcting code that requires more than a
single parity bit.

• Hamming codes are codewords formed by adding redundant check bits, or parity
bits to a data word.

• All Hamming codes discussed in this unit have dmin = 3.

• Hamming Code is denoted by C(n,k), where n = 2m – 1 and k = n – m.

Structure of the encoder and decoder for a Hamming code

r0 = a2 + a1 + a0 s0 = b2 + b1 + b0 + q0
r1 = a3 + a2 + a1 s1 = b3 + b2 + b1 + q1
r2 = a1 + a0 + a3 s2 = b1 + b0 + b3 + q2
Logical decision made by the correction logic analyzer:

• If q0 is in error, s0 is the only bit affected; the syndrome is 001.

• If b2 is in error, s0 & s1 are the bits affected; the syndrome is 011.
• If b1 is in error, all 3 syndrome bits are affected; the syndrome is
111.

If two errors occur during transmission, the created dataword might

not be the right one.
Hamming code C(7, 4); n = 7, k = 4
Example
Let us trace the path of three datawords from the sender to the destination:

• The dataword 0100 becomes the codeword 0100011. The codeword

0100011 is received. The syndrome is 000, the final dataword is 0100.

• The dataword 0111 becomes the codeword 0111001. The received

codeword is 0011001. The syndrome is 011. After flipping b2 (changing 1 to
0), the final dataword is 0111.

• The dataword 1101 becomes the codeword 1101000. The codeword

0001000 is received. The syndrome is 101. After flipping b0, we get 0000, the
wrong dataword. This shows that our code cannot correct two errors.
 Burst Errors
• Burst errors are very common, particularly in wireless environments where
a fade will affect a group of bits in transit.

• One way to counter burst errors, is to break up a transmission into shorter

words and create a block (one word per row), then have a parity check per
word.

• The words are then sent column by column. When a burst error occurs, it
will affect 1 bit in several words as the transmission is read back into the
block format and each word is checked individually.
Burst error correction using Hamming code
Checksum
• In checksum error detection scheme, the data is divided into ‘k’ segments
each of ‘m’ bits.
• In the sender’s end the segments are added using 1’s complement arithmetic
to get the sum.
• The sum is complemented to get the checksum.
• The checksum segment is sent along with the data segments.
• At the receiver’s end, all received segments are added using 1’s complement
arithmetic along with the checksum to get the sum.
• The sum is complemented. If the result is zero, the received data is accepted;
otherwise it is discarded.
• The checksum detects all errors involving an odd number of bits. It also
detects most errors involving even number of bits.
Example
 Cyclic Codes
• Cyclic codes are special linear block codes with one extra property.

• In a cyclic code, if a codeword is cyclically shifted (rotated), the resultant is

another codeword.

A CRC code with C(7, 4)

CRC encoder and decoder
Division in CRC encoder
Division in the CRC decoder for two cases
Data link layer

• Two main functions of Data Link Layer (DLL) are:

- Data link control: Deals with the design and procedures of
communication between two adjacent nodes.
- Medium access control: Defines how to share the link.

• Data link control functions are:

- Framing
- Flow control
- Error control
- Protocols implemented for reliable transmission
 Framing
• The data link layer needs to pack bits into frames, so that each frame is
distinguishable from another.

• Framing in DLL separates message from one source to a destination or from

other messages to other destinations by adding addresses.

• It is done to make flow control and error control efficient. Frames can be of
fixed or variable size.

• Fixed-Size Framing – no boundaries for frames, size is used as the delimiter.

• Variable-Size Framing – defines beginning and end of frame. Two

approaches:
- Character oriented approach
- Bit oriented approach
Character Oriented Protocols
• Data to be carried are 8-bit characters. Header and trailer are also
multiples of 8-bits.
• Separation of frames is done by adding 1-byte flag at the start and end of
the frame.
• Flag – protocol dependent special characters.
• For text messages – flag could be any character not used for text comm.
• For audio, video and graph – flag could also be a part of message, that
makes the receiver think it has reached the end of the frame.
• Byte stuffing is done to fix this problem, where a special byte (ESC
character) is added to data when there is a character with same pattern as
flag.
• When receiver finds ESC character, it removes it from data and treats the
next character as data and not a delimiting flag.
• It allows presence of flag in data but creates another problem i.e., what if
the ESC character is also a part of the text ?
• An extra ESC is added to show the second one is part of the text.
A Frame In A Character-Oriented Protocol

Byte stuffing -
Process of
adding 1 extra
byte whenever
there is a flag or
escape character
in the text.
 Bit Oriented Protocols
• Data section of a frame is a sequence of bits to be interpreted as text,
graphic, audio, video and so on..
• In addition to header and possible trailers, a delimiter is used to separate
one frame from the other.
• Most protocols use a special 8-bit pattern flag 01111110 as delimiter.
• If the flag pattern appears in the data, we stuff 1 bit to prevent the pattern
from looking like a flag – BIT STUFFING.
• If a 0 is followed by 5 consecutive 1’s, an extra 0 bit is added regardless of
the next bit.
• This guarantees that the flag sequence does not appear in the frame.
A Frame In A Bit-Oriented Protocol

Bit stuffing is the process

of adding one extra 0
whenever five consecutive
1’s follow a 0 in the data, so
that the receiver does not
mistake the pattern
0111110 for a flag.
Flow and Error Control

• The most important responsibilities of the data link layer are flow control
and error control. Collectively, these functions are known as data link control.

• Flow control refers to a set of procedures that tells the sender how much
data it can send before waiting for an acknowledgment from the receiver.

• The flow of data must not be allowed to overwhelm the receiver. Most of the
receivers are provided with buffers for storing incoming data until they are
processed. If buffer is full, receiver asks to halt the transmission.

• Error control is detection and correction of lost or damaged frames. Error

control in the data link layer is based on Automatic Repeat Request (ARQ),
which is the retransmission of data.
Taxonomy of Protocols
DLL uses protocols to combine framing, flow control and error control for
the delivery of data from one node to other.
Noiseless Channels

• Noiseless channel - An ideal channel in which no frames are lost, duplicated,

or corrupted.

• Two protocols for this type of channel.

• Simplest Protocol – has no flow or error control.

• Stop-and-Wait Protocol – sender sends one frame, stops until it receives

confirmation from receiver and then sends the next frame.
Simplest Protocol

• Unidirectional protocol.

• Sender cannot send a frame until network layer has packet to send.

• Receiver cannot deliver packet to network layer until a frame arrives.

• Protocol includes certain events.

• No action is taken until a request from network layer at sender and a
notification from physical layer at receiver.

• Procedures at both sites are constantly running as they don’t know when
the event occurs.
Design of simplest protocol with no flow or error control
Sender-site algorithm
Receiver-site algorithm
Simplest Protocol
Flow diagram
 Stop-and-Wait Protocol
• If frames arrive at the receiver faster than they can be processed, they must
be stored until their use. Receiver may not have enough buffer space (may
receive data from other sources also) which results in discarding of frames
or denial of service.

• Hence, receiver sends feedback to the transmitter to prevent overwhelming

of the receiver (asks sender to slow down).

• In this protocol, sender sends a frame, stops until it receives the

confirmation from the receiver and then sends the next frame.

• Stop-and-Wait Protocol adds flow control to Simplest protocol.

Design of Stop-and-Wait Protocol
Sender-site algorithm
Receiver-site algorithm
Stop-and-Wait Protocol
Flow diagram
Noisy Channels
• Stop-and-Wait Protocol gives us an idea of how to add flow control to its
predecessor. But noiseless channels are non-existent.

• Three protocols that use error control.

- Stop-and-Wait Automatic Repeat Request

- Go-Back-N Automatic Repeat Request

- Selective Repeat Automatic Repeat Request

Stop-and-Wait Automatic Repeat Request
• It adds simple error control mechanism to the Stop and Wait protocol.

• To detect and correct corrupted frames in Stop-and-Wait ARQ, redundant bits are
added.

• When the frames arrive at receiver, they are checked and if it is corrupted, it is
silently discarded. Detection is manifested by the silence of the receiver.

• Error correction in Stop-and-Wait ARQ is done by keeping a copy of the sent frame
and starts a timer. It retransmits the frame if ACK is not received before the timer
expires.

• It is difficult to identify lost frames than corrupted frames. In Stop-and-Wait ARQ,

we use sequence numbers (based on modulo-2 arithmetic) to number the frames
so that we can identify lost or duplicated frames.

• In Stop-and-Wait ARQ, the acknowledgment number always announces in modulo-

2 arithmetic the sequence number of the next frame expected.
Design of the Stop-and-Wait ARQ Protocol
Sender-site algorithm
Sender-site algorithm (contd..)
Receiver-site algorithm
Flow Diagram
Go-Back-N Protocol
• To improve the efficiency of transmission, multiple frames must be in
transition (pipeline) while waiting for acknowledgement.

• Go-Back-N lets multiple frames to be outstanding to keep the channel busy

while sender is waiting for ACK.

• Receiver has buffer ‘W’ long and we can send up to ‘W’ frames without ACK.

• Each frame is numbered. ACK includes number of next frame expected.

Sequence Numbers
• Frames from a sender are numbered sequentially. We need to set a limit since
we need to include the sequence number of each frame in the header.

• If header of frame allows m-bits for sequence number, the sequence numbers
range from 0 to 2m – 1.
• Example for m = 3, sequence numbers are: 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5,
6, 7.

• Sliding window defines the range of sequence numbers that is the concern of
sender and receiver.

• The send window is an imaginary box with three variables: Sf, Sn, Ssize.

• Receiver has only one variable, Rn, that holds the sequence number of the
frame it expects to receive.
 Sender Sliding Window

• At the sending site, to hold

the outstanding frames until
they are acknowledged, we
use the concept of a window.
• The size of the window is at
most 2m-1 where ‘m’ is the
number of bits used for the
sequence number.
• The window slides to
include new unsent frames
when the correct ACKs are
received.
 Receiver Sliding Window
• Size of the window at the
receiving site is always 1 in this
protocol.
• Receiver is always looking for a
specific frame to arrive in a
specific order.
• The window slides when a
correct frame has arrived.
Sliding occurs one slot at a time.
• Any frame arriving out of order
is discarded and needs to be
resent.
• Receiver window slides as
shown in fig. Receiver is waiting
for frame 0 in part ‘a’.
Send window for Go-Back-N ARQ
Receive window for Go-Back-N ARQ
Acknowledgement
• Receiver sends positive ACK, if a frame arrived safe and in order.

• If the frames are damaged/out of order, receiver is silent and discard all subsequent
frames until it receives the one it is expecting.

• The silence of the receiver causes the timer of the unacknowledged frame to expire.

• Then the sender resends all frames, beginning with the one with the expired timer.

• For example, suppose the sender has sent frame 6, but the timer for frame 3 expires
(i.e. frame 3 has not been acknowledged), then the sender goes back and sends frames
3, 4, 5, 6 again. Thus it is called Go-Back-N-ARQ.

• The receiver does not have to acknowledge each frame received, it can send one
cumulative ACK for several frames.
 Go-Back-N ARQ, Normal Operation
• The sender keeps track of the outstanding frames and updates the
variables and windows as the ACKs arrive.
 Go-Back-N ARQ, lost Frame

• Frame 2 is lost.
• When the receiver
receives frame 3, it
discards frame 3 as it is
expecting frame 2
(according to window).
• After the timer for frame
2 expires at the sender
site, the sender sends
frame 2 and 3 (go back to
2).
Go-Back-N ARQ, Sender Window Size
• Size of the sender window must be less than 2m .
• Size of the receiver is always 1.
• If m = 2, window size = 2 m – 1 = 3.
• Fig. compares a window size of 3 and 4.

Accepts
as the 1st
frame in
the next
cycle-an
error
Design of Go-Back-N ARQ
 Selective Repeat ARQ
• Go-Back-N ARQ is inefficient for a noisy link.
• In a noisy link, frames have higher probability of damage, which means the
resending of multiple frames.
• This resending consumes the bandwidth and slows down the transmission.

Solution:
• Selective Repeat attempts to retransmit only those frames that are actually
lost (due to errors).
– Receiver must be able to accept frames out of order.
• It defines a Negative Acknowledgement (NAK) that report the sequence
number of a damaged frame before the timer expires.
• It is more efficient for noisy link, but the processing at the receiver is more
complex. Size of the window is (2m-1).
Selective Repeat ARQ, sender and receiver windows
• The window size is reduced to one half of 2m
• Sender window size = receiver window size = 2m/2
• Window size = 2m-1
• If m = 2, Window size = 4/2=2
• Sequence number = 0, 1, 2, 3
Selective Reject (NAK)
• Also called selective retransmission

• Only rejected frames are retransmitted

• Subsequent frames are accepted by the receiver and buffered

• Minimizes retransmission

• Receiver must maintain large buffer

Send and Receive window for Selective Repeat ARQ
 Selective Repeat ARQ, lost frame

• Frames 0 and 1 are

accepted when received
because they are in the
range specified by the
receiver window. Same
for frame 3.

• Receiver sends a NAK2

to show that frame 2
has not been received
and then sender
resends only frame 2
and it is accepted as it
is in the range of the
window.
 Selective Repeat ARQ, sender window size
• Size of the sender and receiver windows must be at most one-half of 2m.
• If m = 2, window size should be 2m/2 = 2.
• Figure compares a window size of 2 with a window size of 3.
• Window size is 3 and all ACKs are lost, sender sends duplicate of frame 0, window of
the receiver expect to receive frame 0 (part of the window), so accepts frame 0, as the
1st frame of the next cycle – which is an error.
Design of Selective Repeat ARQ
 Piggybacking
• In two way communication, whenever a data frame is received, the
receiver waits and does not send the control frame (acknowledgement)
back to the sender immediately.

• The receiver waits until its network layer passes in the next data packet.
The delayed acknowledgement is then attached to this outgoing data
frame.

• This technique of temporarily delaying the acknowledgement so that it

can be hooked up with the next outgoing data frame is known as
Piggybacking.
 Piggybacking
• The major advantage of Piggybacking is better use of available channel bandwidth.

• It improves the efficiency of bidirectional protocols since control information flow is

in both directions.

• Instead of sending an acknowledgement in an individual frame it is piggybacked on

the data frame. In the data frame itself, we incorporate one additional field for
acknowledgment (called ACK).

• Every node has two windows: Send and Receive both using the same algorithms.

• 3 types of events are involved:

- Request : Uses only send window at each site.
- Arrival : When a frame arrives, site has to handle control information and frame
itself. Uses both send and receive windows.
- Time-out
Design of Piggybacking in Go-Back-N ARQ
 HDLC & Point-to-Point Protocol

• High-level Data Link Control (HDLC) is a bit-oriented protocol for

communication over point-to-point and multipoint links. It implements the
ARQ mechanisms.

• Although HDLC is a general protocol that can be used for both point-to-
point and multipoint configurations, one of the most common protocols for
point-to-point access is the Point-to-Point Protocol (PPP).

• PPP is a byte-oriented protocol.

• PPP is a byte-oriented protocol using byte stuffing with the escape byte to
be 01111101.
High-level Data Link Control
HDLC Station Types:

• Primary station: Controls operation of link. Frames issued are called

Commands.

• Secondary station: Under control of primary station. Frames issued are

called Responses.

• Combined station: May issue both commands and responses.

HDLC Link Configurations and Transfer Modes
Normal Response Mode (NRM)
• Unbalanced configuration: Primary initiates transfer to secondary. Secondary
may only transmit data in response to command from primary.
HDLC Link Configurations and Transfer Modes
Asynchronous Balanced Mode (ABM)
• Balanced configuration: Either of the stations may initiate transmission
without receiving permission.
• In ABM the link is point-to-point.
HDLC Frame Types

• I-Frame: Information frames (user data and control data)

• S-Frame: Supervisory frames (control information)
• U-Frame: Unnumbered frames (control information for managing the link
itself)
HDLC Frame

Flag: 8-bit and the sequence 01111110 identifies the beginning and end of
the frame. Serves as synchronization pattern for receiver.
FCS: Frame Check Sequence is error detection field. Contains 2/4-byte CRC.
Address: Contains the address of the secondary station.
If ‘primary’ created the frame, it contains to address else a from address. It
can be one byte (last bit is 1) or more . If the address is more than one byte, all
bytes end with zero except the last byte ends with 1. Ending each
intermediate byte with 0 indicates to the receiver that more address bytes are
to come.
Control Field: Determine the type of frame and defines its functionality (used
for flow and error control). It is 1 or 2 byte long.
Control field format for different frame types
 I-Frame

• Information: Contains the user’s information.

• Control field:
- The first bit (0) defines the frame type (I-Frame).
- N(S): Defines the sequence number of the frame.
- N(R): Acknowledgment number when piggybacking is used.
- P/F: Valid only if set to 1 and has dual purpose:
- Poll: Frame sent by the primary station (the address field contains the address of the
receiver) to secondary.

- Final: Frame sent by secondary station (the address field contain the address of the
sender) to primary.
S-Frame Control Field in HDLC

The Code field define four types of S-frames:

1. Receiver ready (RR): 00 - receiver acknowledges the receipt of a safe frame and ready
to accept more frames.

2. Receiver not ready (RNR): 10 - receiver not ready to accept more frames because it is
busy.

3. Reject (REJ): 01 - This is NAK Frame that can be used in ‘Go-Back-N’ to improve the
efficiency by informing the sender that the last frame is lost or damaged.

4. Selective Reject (SREJ): 11 - NAK frame used in ‘Selective Repeat’.

U-Frame Control Field in HDLC
 HDLC: Example

• Connection and disconnection

Point-to-Point Protocol: PPP
• Most common protocols for point-to-point access
• Many Internet users who need to connect their home computer to the
server of an ISP use PPP
• A point-to-point link protocol is required to control and manage the
transfer of data
• PPP defines/provides
- the format of the frame to be exchanged between devices
- how two devices negotiate the establishment of the link and the
exchange of data
- how network layer data are encapsulated in the data link frame
- how two devices can authenticate each other
- multiple network layer services
- connection over multiple links
- Network address configuration
• But, several services are missing for simplicity
- no flow control, simple error control (detection and discard), no
sophisticated addressing for multipoint configuration
PPP Frame
• Flag: 01111110 the same as HDLC, but is treated as a byte because PPP is a
byte-oriented protocol

• Address: 11111111 (broadcast address)

• Control: No need because PPP has no flow control and limited error control

• PPP is a byte-oriented protocol using byte stuffing with the escape byte
01111101
PPP: Transition States

Dead: Link not in use, no

carrier detected
Establish: When node starts
communication, connection
goes into this phase
Authenticate: Optional,
several packets are sent for
authentication if agreed.
Network: Negotiation for
Network layer protocols takes
place.
Open: Data transfer take place
Terminate: Connection
terminated.
PPP: Multiplexing
• PPP uses another set of other protocols to establish the link,
authenticate the parties, and carry the network layer data
• Three sets of protocols defined for powerful PPP: LCP, two APs, several
NCPs
 MAC Sub layer

MULTIPLE ACCESS PROTOCOLS

 Multiple Access Protocols
• If more than 2 nodes send data at the same time → collision

• All collided packets are lost → waste of bandwidth

• We need multiple – access protocols to coordinate access to multipoint or broadcast

link

• Multiple access protocols are needed in LANs, Wi-Fi, and satellite networks to control
the share media.
 Human Communication Protocols
Problem of controlling the access to the medium is similar to the rules of
speaking in an assembly :
• Give everyone a chance to speak
• Raise your hand if you have a question
• Don’t speak until you are spoken to
• Don’t interrupt when someone is speaking
• Don’t monopolize the conversation

• Don’t fall asleep when someone else is talking

 MAC Sub layer
• Data link layer is divided into two sub layers: Upper and Lower
• Logical Link Control (LLC) : responsible for data link control (flow and
error control)
• Medium Access Control (MAC) : resolves the multiple access to shared
media
Taxonomy of Multiple-Access Protocols
 Random Access Protocols
• In random access or contention methods, no station is superior to another
station and none is assigned the control over another.
• No station permits another station to send.
• At each instance, a station that has data to send uses a procedure defined
by the protocol to make a decision on whether or not to send.

 ALOHA

 Carrier Sense Multiple Access (CSMA)

 Carrier Sense Multiple Access with Collision Detection(CSMA/CD)

 Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA)

 Random Access
• Each station has the right to the medium without being controlled by any
other station.

Two features gives the method its name:

• There is no schedule time for a station to transmit:
- transmission is random among stations
• Stations compete with one another to access the medium
- Contention method.

• Collision: an access conflict occurs when more than one station tries to send,
as a result the frame will be either destroyed or modified.
• Each station follows a procedure that answer the following questions to
avoid collision:
• When can the station access the medium?
• What can the station do if the medium is busy?
• How can the station determine the success or failure of the
transmission?
• What can the station do if there is an access conflict ?
 Evolution of Random-Access methods
ALOHA: Uses MA (Multiple Access) No carrier sense

CSMA: Carrier Sense Multiple Access

CSMA/CD: CSMA with Collision Detection

CSMA/CA: CSMA with Collision Avoidance

 Pure ALOHA
• Developed at the University of Hawaii
• Simple method where each station sends a frame whenever it has a frame to
send.
• Since there is only one channel to share, there is the possibility of collision
between frames from different stations.
Frames in a Pure ALOHA network
 Pure ALOHA
• It relies on acknowledgments from the receiver. If the ACK dose not arrive
after a time-out period, the station resend the frame.
• Time-out is equal to the max possible round trip time = 2 x Tp
• Tp (max propagation time) time required to send a frame between the most
widely separated station
• To minimize collisions, each station waits a random amount of time (back-
off time TB) before resending its frame.
• TB is a random value that depend on K (the number of attempted
unsuccessful transmissions) .
• After a max. no. of retransmission attempts Kmax, a station must give up and
try later to prevent congestion.
Procedure for Pure ALOHA protocol
 Slotted ALOHA
• Slotted ALOHA was invented to improve the efficiency of Pure ALOHA

• It divides the time into slots of Tfr and force the station to send only at the
the beginning of the time slot.

• If the station miss the beginning of synchronized time slot, it must wait
until the beginning of next time slot.
Frames in a Slotted ALOHA network
 Carrier Sense Multiple Access (CSMA)
Developed to minimize collisions and increase the performance
• A station now “follows” the activity of other stations
• Simple rules for a polite human conversation
• If someone else begins talking at the same time as you, stop talking
• Based on the principle “Listen before talk” or “Sense before transmit”

CSMA
• A node should not send, if another node is already sending → carrier
sensing

• A node should stop transmission if there is interference → collision

detection
 CSMA
• Sense the carrier before transmit :“listen before you talk”
• CSMA can reduce the possibility of collision, but it can not eliminate it
because of the propagation delay (a station may sense the medium
and find it idle, only because the first bit of a frame sent by another
station has not been received)
 Space/Time model of collision of CSMA

C
 Vulnerable time in CSMA
• Vulnerable time: Time in which there is a possibility of collision
• Vulnerable time for CSMA is the max propagation time, Tp needed for a
signal to propagate from one end of the medium to the other.
• When a station sends a frame, and any other station tries to send during this
time it leads to collision.
• But if the first bit of frame reaches the end of medium, every other station
will already have heard the bit and will refrain from sending
 Types of CSMA Protocols

• Different CSMA protocols determine:

- What should a station do if the channel is busy?

- What should a station do if the channel is idle?

1. 1-persistence method
2. Non-persistence method

3. P-Persistence method
 1-persistence method

 To avoid idle channel time, 1-persistent protocol used

 Station wishing to transmit listens to the medium:
 If medium idle, transmit immediately;
 If medium busy, continuously listen until medium becomes idle
& then transmit immediately with probability 1
 Performance
 1-persistent stations are selfish
 If two or more stations becomes ready at the same time,
collision guaranteed
***Chance of collision is high.
 Non-persistence method

 A station with frames to be sent, should sense the medium

1. If medium is idle, transmit
2. If medium is busy, (backoff) wait a random amount of time and repeat 1
 Non-persistent stations are deferential (respect others)
 Performance:
 Random delays reduces probability of collisions because two stations with
data to be transmitted will wait for different amount of times.
 Bandwidth is wasted if waiting time (backoff) is large because medium
will remain idle following end of transmission even if one or more stations
have frames to send
P-Persistence method
 Time is divided into slots where each
time slot typically equals maximum
propagation time
 Station wishing to transmit listens to
the medium:
1. If medium is idle,
 transmit with probability (p), OR
 wait one time slot with
probability (1 – p), then repeat 1
2. If medium is busy, continuously
listen until idle and repeat step 1
 Performance
 Reduces the possibility of
collisions like non-persistent
 Reduces channel idle time like
1-persistent
 CSMA/CD Protocol
 CSMA (all previous methods) has an inefficiency:

 If a collision has occurred, the channel is unstable until colliding packets

have been fully transmitted

 CSMA/CD (Carrier Sense Multiple Access with Collision Detection)

overcomes this as follows:

 While transmitting, the sender is listening to medium for collisions.

 Sender stops transmission if collision has occurred, reducing channel

wastage
 Carrier Sense Multiple Access /Collision Detection
• “Listen-while-talk” protocol. A host listens even while it is transmitting, and
if a collision is detected, stops transmitting
• Use one of the CSMA persistence algorithm (non-persistent, 1-persistent,
p-persistent) for transmission

• If a collision is detected by a station during its transmission then it should

do the following:
- Abort transmission and
- Transmit a jam signal (48 bit) to notify other stations of collision so that
they will discard the transmitted frame also to make sure that the
collision signal will stay until detected by the farthest station.
- After sending the jam signal, back off (wait) for a random amount of
time, then
- Transmit the frame again
Flow diagram for the CSMA/CD

Jamming signal enforces the collision in case other stations have not yet sensed
the collision
 Collision Detection
• How the station detects a collision?
• Detecting voltage level on the line
• Detecting energy level.
• Detecting simultaneous transmissions and receptions
• Energy in channel can have three values: zero, normal, and abnormal.
• At zero level, the channel is idle
• At the normal level, a station has successfully captured the channel and is
sending its frame.
• At the abnormal level, there is a collision and the level of the energy is twice
the normal level
 CSMA/CA
• In CSMA/CA, if the station finds the channel busy, it does not restart the
timer of the contention window; it stops the timer and restarts it when the
channel becomes idle.
• CSMA/CA was mostly intended for use in wireless networks

IFS – Interframe Space

Flow diagram for CSMA/CA

Contention window
size is 2K-1

After each slot:

- If idle, continue
- If busy, stop and continue
when idle
 Controlled Access
• In controlled access, the stations consult one another to find which station
has the right to send.
• A station cannot send unless it has been authorized by other stations.
• Provides in order access to shared medium so that every station has chance
to transfer (fair protocol)
• Eliminates collision completely
• Controlled Access methods
• Reservation
• Polling
• Token Passing
 Reservation Access Method
• A station needs to make a reservation before sending data.
• Time is divided into intervals
• A reservation frame precedes each time interval
• Number of stations and number of mini-slots in the reservation frame are
equal
• Each time slot belongs to a particular station
• If there are N stations in the system, there are exactly N reservation mini-
slots in the reservation frame
 Polling Access Method
• Devices are designated as a Primary station and Secondary station
• All data exchange must go through the primary station
• Primary station controls the link and initiates the session; the secondary
station follow its instructions
Two functions: Poll and Select
• Poll: If the primary wants to receive data, it asks the secondary if they have
anything to send
• Select: If the primary wants to send data, it tells the secondary to get ready
to receive data
Select function

• The Select function is used

when the primary has
frames to send

•The primary creates and

transmits a select (SEL)
frame

• SEL alerts the secondary to

the upcoming transmission

• The primary waits for ACK

to send the data
Poll function
• When the primary is ready to
receive data, it must ask (Poll)
each device in turn if it has
anything to send.

• When the first secondary is

approached, it responds either
with a NAK frame if it has nothing
to send or with data if it does.

• If the response is NAK, the

primary polls the next secondary.

• If it receives data, it sends ACK

frame.
 Token Passing

• In the Token-Passing, the stations are organized in a logical ring

• For each station there is a predecessor and a successor

• Predecessor is the station which is logically before the station in the ring

• Successor is the station which is logically after the station in the ring

• Current station is the one that accessing the channel now

• How is the right to access the channel passed from one station to another?
• Station is authorized to send data when it receives a special packet called a
token
• Stations are arranged around a ring.
• When no data are being sent, a token circulates the ring.
• If a station needs to send data, it waits for the token.
• The station captures the token and sends one or more frames (as long as it
has frames to send or the allocated time has not expired), and finally it
releases the token to be used by next station (successor).
• The maximum time any station can hold the token is limited.
• Since there is only one token, only one station transmits at a time, and
collisions never occur.
Token management is needed for this access method:

• Stations must be limited in the time they can have possession of the token.

• The token must be monitored to ensure it has not been lost or destroyed (if
the station that is holding the token fails, the token will disappear from the
network).

• Assign priorities to the stations, to make low-priority stations release the

token to high priority stations.

• Stations do not have to be physically connected in a ring; the ring can be a

logical one.
Token-Passing Procedure
Logical ring and Physical topology in Token-
Passing access method
 Channelization

• Channelization is a multiple access method in which the available

bandwidth of a link is shared in time, frequency or through code, between
different stations.
• Three methods:
• Frequency Division Multiple Access (FDMA)
• Available bandwidth of the common channel is divided into bands
that are separated by guard bands
• Time Division Multiple Access (TDMA)
• The bandwidth is just one channel that is timeshared between
different stations
• Code Division Multiple Access (CDMA)
• One channel carries all transmissions simultaneously
Frequency Division Multiple Access (FDMA)
• In FDMA, the available bandwidth is divided into frequency bands.
• Each station is allocated a band to send its data.
• To prevent station interferences, the allocated bands are separated
from one another by small guard bands.
Time Division Multiple Access (TDMA)
• In TDMA, the stations share the bandwidth of the channel in time.
• Each station is allocated a time slot during which it can send date.
• Achieving synchronization between different stations is the main
problem. This can be achieved by introducing sync bits at the
beginning of each slot.
• The concept of guard times is present in TDMA.
Code Division Multiple Access (CDMA)
 In CDMA, one channel occupies the entire bandwidth of the link.
 In CDMA, one channel carries all transmissions at the same time.
 Consider the Idea
• Let us assume, we have 4 stations 1, 2, 3, & 4 connected to same
channel. The data from station 1 is d1, from station 2 is d2, & so on.
The code assigned to the station 1 is c1, to the station 2 is c2, & so on.
• We assume that the assigned codes have two properties:
1. If we multiply each code by another, we get 0.
2. If we multiply each code by itself, we get 4 (i.e., the no. of
stations)

• With the above two properties taken into consideration, let us see
how the 4 stations can send data using the common channel.
Simple idea of communication with code
• Any station that wants to receive data from one of the other 3
multiplies the data on the channel by the code of the sender.
• For example, stations 3 and 4 are talking to each other. Station 4
wants to hear what station 3 is saying. It multiplies the data on the
channel by c3.
• Data = (d1⋅ c1 + d2 ⋅ c2 + d3 ⋅ c3 + d4 ⋅ c4) ⋅ c3
= d1⋅ c1⋅ c3 + d2 ⋅ c2 ⋅ c3 + d3 ⋅ c3 ⋅ c3 +d4 ⋅ c4 ⋅ c3
= 4 × d3
Chip Sequences
• Each station is assigned a unique chip sequence

• Chip sequences are orthogonal sequences

• Inner product of any pair must be zero
• With N stations, sequences must have the following properties:
• They are of length N
• Their self inner product is always N

• Data Representation
Transmission in CDMA
CDMA Encoding
Signal Created by CDMA
CDMA Decoding
IEEE 802.11 Wireless LAN Standard
• In response to lacking standards, IEEE developed the first
internationally recognized wireless LAN standard – IEEE 802.11
• IEEE published 802.11 in 1997, after seven years of work
• Scope of IEEE 802.11 is limited to Physical and Data Link Layers
• Benefits:
 Appliance Interoperability
 Fast Product Development
 Stable Future Migration
 Price Reductions
 The 802.11 standard takes into account the following significant
differences between wireless and wired LANs:
Power Management
Security
Bandwidth
IEEE 802.11 Terminology
 Access Point (AP): A station that provides access to the DS.
 Basic Service Set (BSS) :
 A set of stationary or mobile wireless stations and an optional central
base station, known as the access point (AP).
 Distribution System (DS): A system used to interconnect a set of BSSs
to create an ESS.
 DS is implementation-independent. It can be a wired 802.3
Ethernet LAN, 802.4 token bus, 802.5 token ring or another
802.11 medium.
 Extended Service Set (ESS):Two or more BSS interconnected by DS
 Extended service set uses two types of stations: mobile and
stationary
 The mobile stations are normal stations inside a BSS. The
stationary stations are AP stations that are part of a wired LAN.
IEEE 802.11 – MAC Sublayer
• IEEE 802.11 defines two MAC sublayers:
• The Distributed Coordination Function (DCF) and the Point
Coordination Function (PCF)

MAC layers in IEEE 802.11 standard

Distributed Coordination Function (DCF)

• It is one of the 2 protocols defined by IEEE at MAC sublayer.

• DCF uses CSMA/CA
• Wireless LAN’s cannot implement CSMA/CD because it is a costly
affair and due to increased bandwidth requirements.
CSMA/CA and NAV

DIFS – Distributed Interframe Space

RTS – Request To Send
SIFS – Short Interframe Space
CTS – Clear To Send
NAV – Network Allocation Vector
Point Coordination Function (PCF)

• The Point Coordination Function (PCF) is an optional access method

that can be implemented in an infrastructure network.
• It is implemented on top of the DCF and is mostly for time-sensitive
transmission.
• PCF has a centralized, contention-free polling access method.
• The Access Point (AP) performs polling for stations that are capable
of being polled. The stations are polled one after another, sending any
data they have to the AP.
Frame format

The MAC layer frame consists of nine fields

Frame Control (FC): The FC field is 2 bytes long and defines the type of
frame and some control information
Subfields in FC field
Frame format (Contd.)
• D (Duration):
• In all frames types (except in one type), this field defines the value of
NAV.
• In one control frame only, this field defines the ID of the frame.

• Addresses:
• There are 4 address fields, each 6 bytes long.
• The meaning of each address field depends on the value of To DS and
From DS subfields.

• Sequence Control:
• This field defines the sequence number of the frame to be used in
flow control.
Frame format (Contd.)

• Frame body:
• This field, which ranges between 0 and 2312 bytes, contains
information based on the type and the subtype defined in the FC field.

• FCS:
• The FCS field is 4 bytes long and contains a CRC-32 error detection
sequence.
 Frame Types
• IEEE 802.11 has 3 categories of frames: Management frames, Control
frames, Data frames.
• Management frames: Management frames are used for the initial
communication between stations and access points.
• Control frames: Control frames are used for accessing the channel
and acknowledging frames.

Values of subfields in
control frames

Data Frames: Data frames are used for carrying data and control information.