Computer

Networks:
Unit 3: DLL
Prof. Swarnalata Bollavarapu
Contact: swarnalata.b@nmims.edu
Contents
Data link layer design issues
error detection and correction
elementary data link protocols
Sliding Window Protocols
Example of Data Link Protocol: HDLC

Ref Book: Tanenbaum, “Computer Networks”

Introduction
Introduction
There are certain limitations that have important implications for
the efficiency of the data transfer.
What do you think are the limitations?
The protocols used for communications must take all these
factors into consideration.
 Data Link Layer Goals/design issues
Providing a well-defined service interface to the network
layer.

Dealing with transmission errors.

Regulating the flow of data so that slow receivers are not

swamped by fast senders.
Data Link Layer Design issues
To accomplish goals data link layer (DLL) takes the packets
it gets from network layer
Encapsulates them into frames for transmission
Frame contains frame header, a payload field for holding the
packet and Trailer
Data Link Layer Design issues
Services provided to the network layer
Framing
Error control
Flow control
Services Provided to Network Layer
Transmitting data from network layer of source machine to
network layer of destination machine

Process at network layer on source machine gives bits to DLL to

transmit it to the destination

The job of the DLL is to transmit the bits to the destination

machine so that they can be handed over to the network layer
there.
Services Provided to Network
Layer
Services Provided to Network
Layer
The data link layer offers many services most commonly
provided are :
Unacknowledged connectionless service
Acknowledged connectionless service
Acknowledged connection – oriented service
 Unacknowledged connectionless service
Source machine sends independent frames to destination
Destination do not acknowledge
No logical connection established
If a frame is lost due to noise, no attempt is made by DLL to
recover loss
Suitable for services where error rates are less so that recovery is
left to higher layers
Example Voice: late data worse than bad data
Most LANs uses unacknowledged connectionless service
 Acknowledged connectionless service
No logical connection established

Each frame received is acknowledged to improve reliability

Sender comes to know whether frames are received or not

If not received within specified time interval frames will be

retransmitted
Useful over unreliable channels as wireless systems.
Connection Oriented service
First phase: Connection establishment
Initialize variables and counters to keep track which frames are
received and which ones have not
Second phase: actual data transmission frames are transmitted
Third Phase: The connection is released, freeing up the variables
,counters and other resources used to establish connection
Framing
Provides service to network layer
Uses service of physical layer to provide service to network
layer
Physical layer accepts bit stream and deliver it to destination
Bits cannot be error free
Number of bits received can be equal to, less than or greater
than number of bits transmitted and they may have different
values
It is responsibility of DLL to detect error and correct error
Framing
DLL break bit stream into frames.
Compute checksum for each frame
Checksum is appended in frame.
When frame is received again checksum is computed.
If new checksum and old checksum in header matches frame
is received correctly without error.
If differs than DLL knows that error has occurred and takes
necessary steps
Framing
Breaking bit stream into frames is difficult
One way : insert time gaps between frames
Like space between words
but networks rarely guarantee about timings, some different
method is required.
Framing
Four methods are there to break bit stream into frames:
Character count
Flag bytes with byte stuffing
Starting and ending flags with bit stuffing
Physical layer coding violations
Framing
First method uses character count field in the header
That tells total number of characters in frame
When frame is arrived at destination DLL at destination sees
character count in header
From character count it knows how many characters follow
and hence where the end of frame is.
Disadvantage of character count
method
Count can be garbled by a transmission error
Destination will get out of sync and will unable to locate the start of
next frame
Even if checksum is wrong destination knows that frame is bad, but
how destination will tell which frame to be retransmitted to sender
Framing
The second method is to have a solution of resynchronization after
error has occurred

Each frame will have start and end with special bytes called a flag bytes

If receiver loses sync it can just search for the flag byte to find the end
of the current frame

Two consecutive flag bytes indicate the end of one frame and starting
of another
Framing
Framing
Problem: it may easily happen that the flag byte’s bit pattern appears in
data

Solution: sender’s data link layer insert a special escape byte just
before each “accidental” flag byte in the data.

The DLL at receiving side removes the escape byte before the data are
given to the network layer

The technique is called byte stuffing or character stuffing

Framing
Next technique is begin and end each frame with special bit
pattern ,01111110
Whenever sender’s data link layer encounters five consecutive 1s in
the data it automatically stuffs a 0 bit into the outgoing bit stream
When the receiver sees five consecutive incoming 1 bits followed by
a 0 bit it automatically destuffs the 0 bit
If the user’s data contain the flag pattern 01111110 this flag is
transmitted as 011111010
Known as bit stuffing
Framing

Bit stuffing
(a) The original data.
(b) The data as they appear on the line.
(c) The data as they are stored in receiver’s memory after
destuffing
Error Control
To ensure reliable delivery : provide some feedback to sender
Protocol should be designed in such a way for receiver to send some
special control frames to sender
Special control frames include positive or negative ack
If sender receives positive ack, it knows frame has been received
correctly
If negative ack then something has gone wrong and frame must be
retransmitted
If frame is lost due to hardware problem receiver will do nothing,
sender will go on waiting for ack.
Error Control
Solution : timers in DLL
When sender transmits frame it starts timer
The timer is set to expire after an interval long enough for the frame
to reach destination, be processed there and time taken for ack to
reach back to sender
If timer expires and no ack is received sender will notice some
problem and retransmit frame
Problem: Reciever might receive same frame twice
Solution : Give sequence number to each frame
Flow Control
Occurs when sender want to transmit frames faster than receiver can
accept them
Occurs when sender is running on fast computer and receiver is
running on slow computer
Even if transmission is error free, at certain point of time receiver
will be not able to handle frames and start losing it
To prevent this two approaches are there:
Feedback based flow control
Rate based flow control
Flow Control
In feedback based flow control receiver sends back information to
sender giving it permission to send more data

For example, when a connection is set up, the receiver might say:
''You may send me n frames now, but after they have been sent, do
not send any more until I have told you to continue.'' We will
examine the details shortly.

In the second one, rate-based flow control, the protocol has a built-in
mechanism that limits the rate at which senders may transmit data,
without using feedback from the receiver.
Error Detection and Error
Correction
Two basic strategies for dealing with errors:
Error correcting codes
Error detecting codes

• Include enough redundant information with each block of data sent , to

enable receiver to deduce what the transmitted data must have been – Error
correcting codes

• Include enough redundancy to allow receiver to deduce that an error has

occurred but not which error and request retransmission. – Error Detecting
codes

• Error correcting codes are also known as forward error correction.

Error Detection and Error
Correction
• On channels that are highly reliable, such as fiber, it is cheaper to
use an error detecting code and just retransmit the occasional
block found to be faulty.

• However, on channels such as wireless links that make many

errors, it is better to add enough redundancy to each block for the
receiver to be able to figure out what the original block was, rather
than relying on a retransmission, which itself may be in error.
Error Detection and Error
Correction
• Framework:
• add redundant information to a frame to detect or correct errors

• At sender:
• Add k bits of redundant data to a m bit message
• K is derived from orginal message through some algorithm
• At receiver: reapply same algorithm as sender to detect errors, take
corrective action if necessary
Recap
Goals of DLL
Services provided by DLL/Design issues of DLL
Types of transmission errors
Error detection and correction
Basic framework
Types of transmission errors
Error Detection
Wireless transmission : more errors : requires error correcting codes
rather than retransmission

Copper wire : less errors: requires error detecting codes and initiate
retransmission
Error Detection techniques
• Parity check
• Checksum
• Cyclic Redundancy Check (CRC)
Error Detection
• Parity Check:
The parity check is done by adding an extra bit, called parity bit to the data to
make a number of 1s either even in case of even parity or odd in case of odd
parity.
While creating a frame, the sender counts the number of 1s in it and adds the
parity bit in the following way
•In case of even parity: If a number of 1s is even then parity bit value is 0. If the
number of 1s is odd then parity bit value is 1.
•In case of odd parity: If a number of 1s is odd then parity bit value is 0. If a
number of 1s is even then parity bit value is 1.

On receiving a frame, the receiver counts the number of 1s in it. In case of even
parity check, if the count of 1s is even, the frame is accepted, otherwise, it is
rejected.
Error Detection

• Advantage: detects any single-bit error. Infact, detects odd number of bits
Error Detection
• 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 to get the sum. The sum is complemented.
•If the result is zero, the received data is accepted; otherwise discarded.
Error Detection
• Checksum:
• Add two binary numbers 11100 and 10101
Error Detection
• Checksum:
Error Detection
• CRC:
•Basic idea: treat string of bits as coefficients of a polynomial that uses
modulo 2 arithmetic – Ex. 1 0 1 0 0 1 represents x 5 + x 3 + 1
•Based on binary division.
•In CRC, a sequence of redundant bits, called cyclic redundancy check bits,
are appended to the end of data unit so that the resulting data unit becomes
exactly divisible by a second, predetermined binary number.
•At the destination, the incoming data unit is divided by the same number. If
at this step there is no remainder, the data unit is assumed to be correct and
is therefore accepted.
•A remainder indicates that the data unit has been damaged in transit and
therefore must be rejected.
Error Detection
• CRC:
Error Detection
• Example:
• Find the CRC for the frame 100100 transmitted using divisor 1101
Error Detection
• CRC:
Error Correction : Hamming Codes
Given any two codewords say, 10001001 and 10110001—
it is possible to determine how many corresponding bits differ. In this
case, 3 bits differ. To determine how many bits differ, just XOR the two
codewords and count the number of 1 bits in the result.

10001001
10110001
00111000
• The number of bit positions in which two code words differ is called
the Hamming distance (Hamming, 1950).

• If two code words are a Hamming distance d apart, it will require d

single-bit errors to convert one into the other.
Error Correction
• In most data transmission applications, all 2 m possible data
messages are legal, but due to the way the check bits are
computed, not all of the 2n possible code words are used.

The error-detecting and error-correcting properties of a block code

depend on its Hamming distance.

• To detect d errors requires distance d+1 code

• To correct d errors requires a distance 2d+1 code
Error Correction
At sender end:
• 1. calculate the no. of redundant bits
• 2. Determine the position of the redundant bits
• 3. Calculate the values of the redundant bits

At receiver end:
• 1. calculate the no. of redundant bits
• 2. Determine the position of the redundant bits
• 3. parity checking
• 4. error detection or correction
Error Correction
At sender end:
• 1. calculate the no. of redundant bits
• 2. Determine the position of the redundant bits
• 3. Calculate the values of the redundant bits

• 1. following equation should hold 2r ≥ m+r+1

• 2. The r redundant bits placed at bit positions of powers of 2,
i.e. 1, 2, 4, 8, 16 etc
• 3. The redundant bits are parity bits, even or odd
• Each redundant bit, ri, is calculated as the parity, generally
even parity, based upon its bit position. It covers all bit
positions whose binary representation includes a 1 in the
ith position except the position of ri
Error Correction
At receiver end:
• 1. calculate the no. of redundant bits
• 2. Determine the position of the redundant bits
• 3. parity checking
• 4. error detection or correction

• 3. c1 = parity(1, 3, 5, 7, 9, 11 and so on)

• c2 = parity(2, 3, 6, 7, 10, 11 and so on)
• c3 = parity(4-7, 12-15, 20-23 and so on)
• 4. The decimal equivalent of the parity bits binary values is
calculated. If it is 0, there is no error. Otherwise, the decimal
value gives the bit position which has error.
Error Correction
Example: 7-bit hamming code, if v have 4 data bits, 1011
Error Correction
• How distance 2?
• Consider even parity
• Consider number like 1011010 to make even parity 0 will be
added hence 10110100
• If error occurred and second 0 is converted into 1 that is 11110100
• Original number : 10110100 Number with error: 11110100
• Perform exclusive OR
10110100
11110100
01000000
Error Correction
As a simple example of an error-correcting code, consider a code
with only four valid code words:

0000000000, 0000011111, 1111100000, and 1111111111

This code has a distance 5
it can correct double errors.
If the codeword 0000000111 arrives, the receiver knows that the
original must have been 0000011111.
If, however, a triple error changes 0000000000 into 0000000111,
the error will not be corrected properly
Error Correction
To use hamming codes for error detection and correction bits of code
words are numbered consecutively starting from 1 at the left hand, bit
2 to its immediate side and so on.

The bits that are power of 2 (1,2,4,8,16 etc..) are check bits

The rest(3,5,7,9..) are m data bits

Total number of check bits in entire codeword should be either even

or odd.
Calculating the Hamming
Code(how to create code word)
Mark all bit positions that are powers of two as parity bits.
(positions 1, 2, 4, 8, 16, 32, 64, etc.)

All other bit positions are for the data to be encoded. (positions
3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17, etc.)

Each parity bit calculates the parity for some of the bits in the
code word. The position of the parity bit determines the
sequence of bits that it alternately checks and skips.
Calculating the Hamming
Code(how to create code word)
Position 1: check 1 bit, skip 1 bit, check 1 bit, skip 1 bit, etc.
(1,3,5,7,9,11,13,15,...)

Position 2: check 2 bits, skip 2 bits, check 2 bits, skip 2 bits,

etc. (2,3,6,7,10,11,14,15,...)

Position 4: check 4 bits, skip 4 bits, check 4 bits, skip 4 bits,

etc. (4,5,6,7,12,13,14,15,20,21,22,23,...)
Calculating the Hamming
Code(how to create code word)
Position 8: check 8 bits, skip 8 bits, check 8 bits, skip 8 bits,
etc. (8-15,24-31,40-47,...)

Position 16: check 16 bits, skip 16 bits, check 16 bits, skip

16 bits, etc. (16-31,48-63,80-95,...)

Position 32: check 32 bits, skip 32 bits, check 32 bits, skip

32 bits, etc. (32-63,96-127,160-191,...)
etc.
Calculating the Hamming
Code(how to create code word)
Set a parity bit to 1 if the total number of ones in the
positions it checks is odd. Set a parity bit to 0 if the total
number of ones in the positions it checks is even.
Calculating the Hamming
Code(how to create code word)
Example
A byte of data: 10011010

Create the data word, leaving spaces for the parity

bits: _ _ 1 _ 0 0 1 _ 1 0 1 0

Calculate the parity for each parity bit

Calculating the Hamming
Code(how to create code word)
Position 1 checks bits 1,3,5,7,9,11:
? _ 1 _ 0 0 1 _ 1 0 1 0. Even parity so set position 1 to a 0: 0 _ 1 _ 0 0
1_1010
Position 2 checks bits 2,3,6,7,10,11:
0 ? 1 _ 0 0 1 _ 1 0 1 0. Odd parity so set position 2 to a 1: 0 1 1 _ 0 0 1
_1010
Position 4 checks bits 4,5,6,7,12:
0 1 1 ? 0 0 1 _ 1 0 1 0. Odd parity so set position 4 to a 1: 0 1 1 1 0 0 1
_1010
Position 8 checks bits 8,9,10,11,12:
0 1 1 1 0 0 1 ? 1 0 1 0. Even parity so set position 8 to a 0: 0 1 1 1 0 0
101010
Code word: 011100101010
Calculating the Hamming
Code(Finding and fixing a bad
bit)
code word : 011100101010
Received code word with error : 011100101110
Receiver will calculate which bit was wrong and
correct it
Check each check bit
Write down all incorrect parity bits
Here parity bits 2 and 8 are wrong so 2+8=10, 10th bit
is a position of wrong bit
Elementary Data Link Layer
Protocols
Three types
An unrestricted simplex protocol
A simplex stop-and-wait protocol
A simplex protocol for a noisy channel
Unrestricted Simplex protocol
Assumptions:
Data are transmitted in one direction
Both the transmitting and receiving N/W layers are always
ready
Processing time is ignored
Infinite buffer space available
No loss of frame, communication channel is never damaged
2 procedures: sender and receiver
Protocol is known as “utopia”
Unrestricted Simplex protocol
void sender (void) void receiver (void)
{ {
frame s; frame r;
packet buffer; event_type event;
while (true) while (true)
{ from_network_layer(&buf { wait_for_event(&event);
fer); from_physical_layer(&r);
s.info = buffer; to_network_layer(&r.info);
to_physical_layer(&s); }
} }
}
Unrestricted
Simplex
protocol
Unrestricted Simplex protocol
• Protocol consist two procedure
– Sender : runs in DLL of sending machine
– Receiver: runs in DLL of receiving machine

• No ACK or Seq Number

• Only one event : frame_arrival
Unrestricted Simplex protocol
•Sender will be in infinite loop
•Loop includes three actions
– Go fetch a packet from network layer
– Construct frame using variable s
– Send the frame on its way
• Receiver waits for something to happen

• Only possibility is arrival of undamaged frame

• Receiver will wait using wait_for_event procedure

Unrestricted Simplex protocol
Advantages:
1. Simple protocol
2. Highly unrealistic

Disadvantages:
Flooding
A Simplex Stop and Wait protocol
• Assumptions:
Communication channel is error free
Data traffic is in one direction
Receiver has only finite buffer capacity and finite processing
speed

• Problem Focused: Prevent the sender from flooding the

receiver with data faster than receiver can handle them
A Simplex Stop and Wait protocol
Receiver provides feedback to sender

After passing packet to network layer, receiver will send dummy

frame to sender giving permission to transmit next frame

After sending frame sender will wait for dummy frame from
receiver

Protocols in which the sender sends one frame and then waits
for an acknowledgement before proceeding are called stop-and-
wait.
Unrestricted Simplex protocol
void sender (void) void receiver (void)
{ {
frame s; frame r, s;
packet buffer; event_type event;
event_type event; while (true)
while (true) { wait_for_event(&event);
{ from_network_layer(& from_physical_layer(&r);
buffer); to_network_layer(&r.info);
s.info = buffer; to_physical_layer(&s);
to_physical_layer(&s); }
wait_for_event(&event); }
}}
A Simplex
Stop and
Wait protocol
A Simplex Stop and Wait protocol
• Advantages:
• Simple reliable transmission

• Disadvantages:
• Sender always wait for the ack frame to send the next frame
• If the ack frame gets corrupted the sender cannot perform
any anymore
A Simplex protocol for noisy
channel
Assumptions:
data transfer is only in one direction
Finite processing capacity and speed at the receiver
Errors in the data frames or ack frames are expected

Every frame has a unique sequence number

Timer is kept, if the ack is not received withing the time frame,
the frame gets retransmitted
A Simplex protocol for noisy
channel
The network layer on A gives packet 1 to its data link layer. The
packet is correctly received at B and passed to the network layer on
B. B sends an acknowledgement frame back to A.
The data link layer on A eventually times out. Not having received an
acknowledgement, it (incorrectly) assumes that its data frame was
lost or damaged and sends the frame containing packet 1 again.

The duplicate frame also arrives at the data link layer on B perfectly
and is unwittingly passed to the network layer there. If A is sending a
file to B, part of the file will be duplicated (i.e., the copy of the file
made by B will be incorrect and the error will not have been
detected). In other words, the protocol will fail.
A Simplex protocol for noisy
channel
Problem : Some way is required for the receiver to
distinguish a frame

Solution : Sequence number in the header of the

frame
A Simplex
protocol for
noisy
channel
A Simplex protocol for noisy
channel
After transmitting frame sender starts the timer
Sender waits for something to happen
Three possibilities are there:
An ACK arrives undamaged
Damaged ACK arrives
Timer expires
A Simplex protocol for noisy
channel Receiver side process
If valid ACK arrives: Sender fetch packet from network layer and
put it in buffer

Advances sequence number

When a valid frame arrives at receiver : sequence number is checked

Check if it is duplicate
If not, accept it pass to network layer and ACK is generated
Duplicates and damaged frame are not passed to network layer
A Simplex protocol for noisy channel
Protocols in which the sender waits for a positive
acknowledgement before advancing to the next data item are
often called ARQ (Automatic Repeat reQuest) or PAR (Positive
Acknowledgement with Retransmission).
Advantage:
Handle lost frames by using timer
Disadvantages:
If the interval is too short, retransmissions occur
If too long, bandwidth is wasted as sender waits too long before
doing a transmission
Sliding Window Protocols
Previous protocols : One Way transmission

Need for transmitting data in both direction

Solution : Have two separate communication channel

So two separate physical circuits each with forward channel (for

data) and reverse channel (for ACK)

Reverse Channel bandwidth will be wasted.

Sliding Window Protocols
Solution : use same circuit for data in both direction.
Reverse channel has same capacity as forward channel
Present scenario : Sender send’s data frame and wait for ACK.
Receiver receive data frame and send ACK
Sender receiving ACK transmit next frame.
Disadvantage: Bandwidth wasted in present scenario.
Sliding Window Protocols
Solution :
When data frame arrives instead of immediately
sending ACK receiver will wait till network layer
provide some next packet
The ACK is attached with data frame
The ACK gets free ride on the next outgoing data
frame.
Technique is known as piggybacking
Sliding Window Protocols
Advantage of Piggybacking:

Better use of channel bandwidth

fewer frames sent means fewer “frame arrival”

interrupts and fewer buffers

It do not cost more than few bits

Sliding Window Protocols
Disadvantage of Piggybacking:

How long should the data link layer wait for a

packet onto which to piggyback the ACK?

If longer wait time: sender will timeout:

retransmission :duplicate frames
Solution : Decide some fixed time, if packet come
within that time, piggyback ACK else send ACK
separately
Sliding Window Protocols
Each frame in sliding window protocol will have
sequence number ranging from 0 to some
maximum

Sliding window protocols are bidirectional

The maximum is 2n -1 .

sequence number fits exactly in n bits.

Sliding Window Protocols
Sender maintains a set of sequence numbers corresponding to
frames it is permitted to send
These frames are said to fall within the sending window
Receiver also maintains a receiving window corresponding to
the set of frames it is permitted to accept.
Sender’s window and receiver’s window need not have the same
lower and upper limits or even have the same size.
Sliding Window Protocols
Frames within sender’s window represent frames that have
been sent or can be sent but are not yet acknowledged

Whenever a packet arrives from network layer, it is given

the next highest sequence number and the upper edge of the
window is expanded by one
When an ACK comes in lower edge is advanced by one.

In this way window continuously maintains a list of

unacknowledged frames.
Example: HDLC
Link could be point-to-point or broadcast

Protocol:
Define the format of frames
In response to frames, action to be taken by nodes
Example: Ethernet, PPP etc
Example: HDLC
DLL is divided into two sub-layers: logic link control (LLC) and
Media Access Control (MAC)
LLC : interface between network layer and MAC sub-layer
Responsible for:
Error detection and correction
Flow control

MAC: controls access to the physical media

Example: HDLC
Bit oriented protocols –
It views the frame as a collection of bits
Eg., HDLC

Byte oriented protocols-

It views frames as collection of bytes (not bits)
Examples:
PPP (point –to –point protocol)
BISYNC- Binary synchronous communication protocol by IBM
Example: HDLC
HDLC: High-level Data link Control
Bit –oriented protocol
The synchronous Data link control (SDLC) protocol developed by
IBM
Later standardized by ISO as HDLC protocol

Forms basis for other protocols

Very important DLL protocol
Example: HDLC
Frame format:
Beginnin Header Body CRC Ending
g sequence
sequence (16) (16) (8)
(8)

Beginning and ending sequence: uses bit pattern 01111110

Header: Address and Control field
Body: payload (variable size)
CRC: error detection
Example: HDLC
Types of frames:
Types of frame is determined by the control field
I-frame: Information frame
S-frame: Supervisory frame
U-frame: Un-numbered frame
I-frame Ist bit is 0

S-frame Ist bit is 10

U-frame Ist bit is 11