UNIT IV

Framing, Flow Control, Error Detection &

Correction, CSMA, CSMA/CD, HDLC and PPP
Agenda

▪ Framing, Flow Control Mechanisms

▪ Stop Wait Protocol
▪ Goback N ARQ, Selective Reject ARQ
▪ CRC, Checksum
▪ Types of Errors
▪ Error Correction
▪ CSMA, CSMA/CD
▪ HDLC
▪ PPP
 FRAMING

• Data transmission in the physical layer means moving bits in the

form of a signal from the source to the destination.
• The physical layer provides bit synchronization to ensure
that the sender and receiver use the same bit durations and timing
• Framing in the data link layer separates a message from one source
to a destination, or from other messages to other destinations, by
adding a sender address and a destination address.

Types of Framing
1. Fixed-Size Framing
2. Variable-Size Framing
 FRAMING

1. Fixed-Size Framing
In fixed-size framing, there is no need for defining the boundaries of the
frames; the size itself can be used as a delimiter
Ex : ATM wide-area network
2. Variable-Size Framing
In variable-size framing, we need a way to define the end of the frame
and the beginning of the next
Two approaches used to delimit the frame
i. a character-oriented approach
ii. a bit-oriented approach
 FRAMING

Character-Oriented Protocols
The flag could be selected to be any character not used for text communication.

In byte stuffing (or character stuffing), a special byte is

added to the data section of the frame when there is a character with the same
pattern as the flag.

The data section is stuffed with an extra byte. This byte is usually called the
escape character (ESC), which has a predefined bit pattern.

Whenever the receiver encounters the ESC character, it removes it from the
data section and treats the next character as data, not a delimiting flag.

Byte stuffing and Unstuffing show in fig-1

FRAMING(Fig-1)
 FRAMING

Bit-Oriented Protocols
In a bit-oriented protocol, the data section of a frame is a sequence of bits to be
interpreted by the upper layer as text, graphic, audio, video, and so on

However, in addition to headers (and possible trailers), we still need a delimiter to

separate one frame from the other.

Most protocols use a special 8-bit pattern flag 01111110 as the delimiter to
define the beginning and the end of the frame,

A frame in a Bit oriented protocol shown in Fig below

FRAMING
Flow & Error Control
Data Link Control

Line Discipline: Determines which device can send and when it

can send
Flow Control: Coordinates the amount of data that can be sent
before receiving acknowledgement. Linked with error control
Error Control: Allows the receiver to inform the sender of any
frames lost or damaged in transmission and coordinates
retransmission of those frames by the sender
 Line Discipline

In Line discipline whatever the system is, no device should be

allowed to transmit until that device has evidence that the
intended receiver is ready to receive the transmission
Line discipline can be done in two ways:

❖ Enquiry/Acknowledgment (ENQ/ACK)
❖ Poll/Select
Flow Control
Second aspect of Data link control- Flow Control
Set of procedures that tells the sender as how much data it can
transmit before waiting for an acknowledgment from the receiver.
Receiver got set of memory blocks called the BUFFER that store
the incoming data before they are processed.
If buffer begins to fill up, receiver must be able to tell the sender to
send fewer data frames or halt the transmission until the buffer is
free to accept the data frame again.
Under this we got two techniques:

❖ Stop- and Wait

❖ Sliding Window
Stop and Wait
In stop- and- wait flow control, the sender waits for an
acknowledgment after every data frame it sends.
Only when acknowledgement has been received, the next data frame
is sent.
The process of alternatively sending and waiting repeats until the
sender transmits an end of transmission frame
Advantage: of stop and wait flow control is simplicity as each frame
is checked and acknowledged before transmitting next frame
Disadvantage: It is very slow as each frame must travel all the way
to the receiver and acknowledgement must travel all the way back
before the next frame can be sent.
If distance between the devices are too long, time spent waiting for
ACKs between each frame can add to the transmission time.
Sliding Window
In Sliding window, the sender can transmit several data
frames before needing an acknowledgment

Frames can be sent one after another i.e. link can carry
several frames at once and its capacity can be used
efficiently

The receiver acknowledges only some of the frames

using a simple ACK to confirm the receipt of multiple data
frames
Sliding window is like an imaginary boxes at both the
sender and receiver side
These windows can hold the data frames and provides
the upper limit on the number of data frames that can be
transmitted before receiving an acknowledgement.
Frames may be transmitted to the receiver as long as
window is not full.

The frames are numbered 0 to n-1 . For example if n=8,

frames are numbered
0,1,2,3,4,5,6,7,0,1,2,3,4,5,6,7,0,1………

The size of the window is n-1. Window always cover n-1

data frames and not n data frames.
When the receiver sends an ACK it can include the
number of next frame it is expected to receive. For
example when the sender sees an ACK with number 5, it
means all frames upto 4 ( 0 to 4) has been received.
Sender Window

At the beginning of transmission sender’s window contains n-1 data frames.

As frames are sent out, left boundary of window moves inward shrinking the
size of the window
Given a window size w, if three frames have been transmitted since last

ACK, number of frames left in window is w-3

For example say we have a window of size 7. ( 0 to 6)

Say Frames 0 through 3 have been sent and no ACK have been received,
sender’s window contains only 4,5 & 6.
Once ACK is received with number 4, then four frames have been received (
0 through 3) and sender’s window expands to include next four frames in
buffer to contain totally 6 frames as 4,5,6,7,0,1,2.
If say received ACK is numbered 2, the sender’s window would have been
expanded only by two frames to contain totally 6 as 2,3,4,5,6,7,0 only.
Sender & Receiver Window
Receiver Window

At receiver we got not n-1 data frames but n-1 spaces for frames
As new frames come in the size of the receiver window shrinks
Receiver window does not represent number of frames received but
number of frames that may still be received before an ACK can be
sent.
If a receiver got a window size of w, if three frames are received
without being acknowledged , number of spaces in window is w-3.
As soon as ACK is received , the window expands to include more
spaces for number of frames equal to number of frames
acknowledged
Let us take the receiving window of size 7 i.e 0 through 6
With the arrival of data frame 0, receiving window shrinks moving
from 0 to 1 and receiver window has now shrunk to six frames before
sending an ACK
Once say frames 0 through 3 are received without sending an ACK,
receiving window now shrinks to 3 frame spaces.
Sliding Window
Automatic Repeat Request (ARQ)

Error correction in data link layer is implemented simply:

anytime an error is detected in an exchange, a negative
acknowledgement (NAK) is received and specified frames
are transmitted- ARQ
Frame is so damaged because of noise and receiver
cannot recognize the frame, ARQ allows us to say that the
frame has been lost.
Other function of ARQ is retransmission of last frames
including lost acknowledgement
Stop and wait is implemented as Stop and Wait ARQ
Sliding window is implemented as sliding window ARQ
which comes under two variants: Go-back-n and Selective
Reject
Stop and Wait ARQ

It is an extension of Stop-and –wait flow control to include

retransmission of data in case of lost or damaged frames. For
retransmission to work, four features are added:
❖ Sending device keeps track of last frames transmitted until it
receives an acknowledgment for that frame. Keeping a copy allows
the sender to retransmit lost or damaged frames until they are
received correctly
❖ For identification purposes both data and ACK frames are numbered
alternatively 0 and 1.
❖ If an error is discovered in a data frame, indicating that it has been
corrupted in a transit, a NAK frame is returned. When an NAK frame
is returned, it resends the frame transmitted after the last
acknowledgement irrespective of the number
❖ Sending device is equipped with a timer. If an expected
acknowledgment is not received within a allotted time period, sender
assumes that last data was lost in transit and send it again
Damaged Frames

when a frame is discovered by the receiver to be an error,

it returns an NAK frame and sender retransmits the last
frame again.
Let us take for example a sender transmits data frame
and one of it is found to be an error.
Sender transmits data frame 0 and receives an
acknowledgment ACK1 indicating it is expecting data 1
Now sends data 1 and receives acknowledgment ACK0
Sender now transmits next frame data 0 . Receiver
discovers an error in it and returns an NAK
Sender retransmits data 0 again and receives ACK1.
Damaged Frames
ARQ- Lost Frames

Sender is equipped with a timer that starts every time the

data frame is transmitted
If the frame never makes it to the receiver , the receiver
can neither acknowledge it positively or negatively
Sending devices waits for an ACK or NAK until the timer
goes off at which point it tries again
Now it retransmits the data frame and starts the timer
once again and wait for an acknowledgement
ARQ- Lost Acknowledgement

Here data frame has made it to the receiver has been

found as either acceptable or not acceptable
But the ACK or NAK frame returned by receiver has been
found to be lost in transit
Now the sending device waits until the timer goes off,
then retransmits the data frame again.
Receiver here checks the number of new data frame.
If lost frame was a NAK, the receiver accepts the new
copy and returns an ACK for it
If lost frame was an ACK, the receiver recognizes the new
copy as a duplicate, acknowledges its receipt, discards
the frame and waits for next frame.
ARQ Lost Acknowledgement
Go Back N ARQ

In Go-back-n ARQ, if a frame is lost or damaged all

frames sent since last frame acknowledged are
retransmitted
Similarly if an acknowledgment is lost, sliding window
waits for the acknowledgement for some specified time. If
acknowledgement does not arrive within the time, the
data is retransmitted again
Go-back-n: Damaged Frame
● We can see that six frames Frame 0,1,2,3,4,5 are being
transmitted before an error is discovered in frame 3.
● An ACK3 has been returned by receiver showing that frames
0,1,2 have been received undamaged. The ACK3 has been sent
before data 3 has arrived
● Data 3 is found to be damaged and so NAK3 has been sent
immediately and frames 4 and 5 are discarded
● Sending device now retransmits all frames 3,4,5 sent since last
acknowledgement and process continues
● Receiver discards frames 4 and 5 till it receive data 3
undamaged.
Go-back-n: Lost Data Frame
● In this send five data frames 0 through 4 are transferred.
● Two data frames data 0 and data 1 arrive intact but data 2 is lost
● Next frame expected at the receiver is data 3.
● Receiver is now expecting data 2 and so considers data3 to be an
error and sends an NAK 2 indicating that 0 and 1 have been
accepted but 2 is lost.
● Data 4 is transmitted before receiving NAK2 which is out of
sequence and is therefore discarded.
● Once NAK2 is received, sender now retransmits 2,3,4.
Go-back-n: Lost Acknowledgement
● In here the sender have transmitted first three frames 0 through
2.
● An acknowledgment ACK3 is now being sent to the sender
saying three data frames have been received.
● The sender now waits a predetermined amount of time for an
acknowledgment of three frames sent.
● Once ACK3 is not received within this time, all data frames are
retransmitted again.
Selective Reject ARQ

In selective reject ARQ, only specific damaged or lost

frame is retransmitted
If a frame is corrupted in transit, NAK is returned and
frame is resent out of sequence
Receiving device must be able to sort the frames it has
and insert the transmitted frames into proper place in
sequence
● The sender transmits 6 data frames 0 through 5
● Once data frames 0 and 1 arrives it is not acknowledged.
● Once data 2 is found be damaged, NAK2 is sent which acknowledges that
previously unacknowledged data frames that have arrived intact and current
data frame is found to be damaged
● NAK2 here tells that data 0 and 1 have been accepted and only data 2 has to
be resent being damaged unlike go-back-n
● Frames received after the damaged frames cannot be acknowledged until
the damaged frames have been retransmitted
● Receiver accepts data 3,4 5 while waiting for a new copy of data 2.
● Once data 2 arrives undamaged, ACK5 can be sent acknowledging new data
2 and original data frames 3,4 and 5.
● Logic is needed by the receiver to sort out of sequence transmission and keep
track of frames are still missing and which have not yet been acknowledged
Go Back N Vs Selective Reject ARQ

● Though retransmitting a specific damaged frame seem to be

more efficient than resending all frames

● Because of Complexity of storing and sorting required by the

receiver and extra logic needed by sender to select specific
frames for retransmission, Selective reject ARQ is expensive and
not often used

● Selective reject ARQ gives better performance but in practice it

is usually discarded in favour of go-back-n for simplicity of
implementation
Error Detection & Correction

42
Error Detection & Correction

When an electromagnetic signal flows from one point to

another it is subject to interference from heat, magnetism
and other forms of electricity
This interference can change the shape of signal
When these signals is carrying binary data, such
changes can alter meaning of data resulting in error.
Error when we say can be classified into two types-
Single bit and Burst

❖ Single bit error: Error where only one bit of given data
unit such as byte, character or packet is changed from 0
to 1.
❖ Burst Error : Error where two or more bits in a given data
unit have changed from 1 to 0 or 0 to 1.
43
Single Bit Error

44
Burst Error

45
Error Detection Techniques

Once a data is transmitted from sender to receiver, we

need to check whether data received is error free or not.
For that we got some Error detection methods that is
been used.
Some of them are :

❖ Cyclic Redundancy Check (CRC)

❖ Checksum

46
Redundancy

Most basic method of error detection is to send every data unit

twice
Receiving device would compare both versions of data unit
Any discrepancy would indicate an error and an appropriate
correction mechanism could be set in place
This mechanism would be completely accurate but it would be
slow.
This would double the transmission time and time it takes to
compare bit by bit also must be added.
An improvement of this method is to include EXTRA
INFORMATION FOR PURPOSE OF COMPARISON.
This technique is called Redundancy as extra bits are
redundant to the information and discarded as soon as the
accuracy of information is determined

47
48
Four types of redundancy checks are used
in data communications
Vertical Redundancy Check - VRC
Performance

▪ It can detect single bit error

▪ It can detect burst errors only if the total number of errors is
odd.
Longitudinal Redundancy Check - LRC
Performance

▪ LCR increases the likelihood of detecting burst errors.

▪ If two bits in one data units are damaged and two bits in
exactly the same positions in another data unit are also
damaged, the LRC checker will not detect an error.
VRC and LRC
Cyclic Redundancy Check (CRC)

The most powerful redundancy checking technique is CRC

This method uses binary division unlike LRC and VRC which
uses binary addition.
In CRC instead of adding bits together to achieve a desired
parity, Sequence of redundant bits called CRC or CRC
remainder is appended to the end of data unit so the resultant
data unit becomes exactly divisible by second predetermined
number which is the divisor.
At receiver, incoming data unit is divided by the same divisor
If there is no remainder, data unit is assumed to be intact and
accepted.
If there is a remainder it means data is been damaged in
transit and must be rejected.
CRC
CRC Algorithm

First a string of 0’s appended to data unit. The number n

is less than the number of bits in the divisor which is n+1
Secondly new elongated data is divided by the divisor
using a process of modulo 2 binary division
Remainder resulting from division is CRC
CRC of n bits derived which is the remainder is appended
to the data unit by replacing the appended 0’s
This data unit arrives at the receiver followed by CRC
Now the receiver divides the data unit by the same
divisor to find the remainder
If remainder is 0 it means data is error free and is
accepted
If remainder is non zero, data got error and is rejected.
CRC Generator

CRC generator i.e. divisor is often represented as a string

of 1s and 0s but as algebraic polynomial
Polynomial is represented as x7+ x6+ x4 +x3 +x +1
Relationship of polynomial to corresponding binary
representation is 11011011
Standard CRC polynomials are CRC-12, CRC-16,
CRC-ITU-T and CRC-32
Polynomial
Polynomial and Divisor
CRC Example

Example: Suppose sender want to transmit the information

string: 1111101. The receiver and sender decide to use the
(arbitrary) polynomial pattern, 1101 which is the divisor
CRC

Remainder is 0111 through modulo 2 division which is

added to the data unit by replacing the appended 0’s to
get 1111101000+ 0111= 1111101111
Receiver divides the appended data unit by the divisor to
see if remainder is zero. If zero it is error free
66
 Checksum

Error detection used by higher layer protocols is

Checksum
Checksum also is based on the concept of redundancy

Check sum Generator :

In sender, checksum generator subdivides the data unit

into equal segments of n bits usually 16
These segments are added together using one’s
complement arithmetic so that total is also n bits long
The total is then complemented and appended to the end
of the original data unit as redundancy bits called
checksum bits

67
Checksum

68
At the sender

▪ The unit is divided into k sections, each of n bits.

▪ All sections are added together using one’s complement to get
the sum.
▪ The sum is complemented and becomes the checksum.
▪ The checksum is sent with the data
At the
Receiver

▪ The unit is divided into k sections, each of n bits.

▪ All sections are added together using one’s complement to get
the sum.
▪ The sum is complemented.
▪ If the result is zero, the data are accepted: otherwise, they are
rejected.
Performance

▪ The checksum detects all errors involving an odd number

of bits.
▪ It detects most errors involving an even number of bits.
▪ If one or more bits of a segment are damaged and the
corresponding bit or bits of opposite value in a second
segment are also damaged, the sums of those columns will
not change and the receiver will not detect a problem.
Data Unit and Checksum
Error Correction

Mechanisms covered till now would detect errors but not

correct them
One method is when an error is detected by the receiver,
the receiver can have the sender retransmit the entire
data unit
Another technique is to have error correcting codes by
the receiver.
These Error correcting codes are efficient to correct
single bit error only
Not efficient in correcting a burst errors.
Based on this we will now see one of the famous Error
correcting code- Hamming Code
 Hamming Code
• Basic Idea:
• Codeword: Digital representation of a data symbol in transmission (e.g.
A -> 01000001, & -> 00100110, etc.)
• Valid vs. Invalid Codewords: Set of codewords of same size (number
of bits) used to interpret all data symbols is called valid codewords,
while the set of codewords which does not belong to this set is called
invalid codewords
• Both valid and invalid codewords are known to both sender and receiver in
transmission
• A bit error can transfer a valid codeword to an invalid codeword
• Codeword = Data bits + Redundancy/Check bits
• Redundant bits are added to check whether the data is correct or some
errors have been taken place
• Distance between codewords: The distance between two codewords
Ci and Cj, denoted as Dist (Ci , Cj), is the number of bit positions, the
codewords differ
• E.g. distance between codewords: 01101 and 10100 is 3
 Hamming Code

• Basic Idea (Contd.):

• We can check whether a codeword is valid or invalid

• Error Detection:
• For a single bit error detection, the distance between any pair of valid
codewords must be at least 2
• Suppose C1 and C2 are two valid codewords and the distance between
C1 and C2 is 1: C1 = 101101 and C2 = 101100 (the last bit differs)
• Due to single bit error in C2 in the last bit position, C2 becomes C1,
also a valid codeword
• Error detection fails
• If the distance is 2, a single bit error still make their difference at least 1
• Error detection successful
• For detecting k errors, the distance must be at least (k+1)
 Hamming Code

• Error Correction:
• Received codeword with bit errors can only be corrected if we can
determine the bit positions where the bit errors have been taken place
• After correction, the received codeword will be converted to one and only one
valid codeword
• For single bit error correction, the distance must be at least 3

Sent: 100100 100111 000100 100111 Distance =

C1 C2 C1 C2 3
Received: 100101 = 100101 000101 ≠ 100101
Distance =
2 000101 100101

110101 010101
Invalid Invalid
101101 codewords 001101
codewords
100001 000001

100111 000111
Valid Valid
100100 codewords 000100 codeword
 Hamming Code
• Illustration of k bit Error Correction:
• For k bit error correction, the distance must be at least (2k+1)

Distance = 2k
Common Part K bit K bit Unchanged Part K bit changed

C1

C2

Common Part K bit K bit K bit changed

bit

Common Part K bit K bit Unchanged Part K bit changed

1

C1

C2

K bit changed
bit

Common Part K bit K bit

1

Distance = 2k+1
 Hamming Code
• Encoding and decoding technique developed by R.W. Hamming [1950]
• Up to one bit error correction and two bit error detection can be done
• Minimum distance in hamming code is 3
• Number of redundancy bits (r) can be determined for a given data block
size of ‘m’ bits by using the following formula:

• For example, if m = 7, minimum of ‘r’ would be 4 as it satisfies the above

equation: 24>= 7+4+1
• Hence, the size of the codeword will be 7+4=11
• To generate a hamming code, following steps are executed:
 Hamming Code

Step 1: Calculate the value of ‘r’ using the above formula

Step 2: All the redundancy bit positions are in the power of 2 (20=1,
21=2, 22=4, 23=8, .......) as shown below (where d is the data bit):

f8 f4 f2 f1

Step 3: Each data bit is included in a unique set of redundancy, as

determined its bit position in binary form
a) Redundancy bit 1 covers all the bit positions whose binary
representation includes a 1 in the least significant
position (1 = 0 + 1, 3 = 0 + 1 + 2, 5 = 0 + 1 + 4, 7 = 0 + 1 + 2 +4, 9
= 0 + 1 + 8, 11 = 0 + 1 + 2 + 8, etc).
 Hamming Code
Step 3 (Contd.): b) Similarly redundancy bit 2 covers all the bit positions
whose binary representation includes a 1 in the second position from
the least significant bit (2, 3, 6, 7, 10, 11, etc)
c) Similarly, 4 covers 4–7, 12–15, 20–23, etc, 8 covers 8–15, 24–31,
40–47, and so on
To mark the dependent bit positions of the redundancy bits, we can
prepare a table as follows:
Positions f1 f2 f4 f8 ..........
..
1 ×
2 ×
3 × ×
4 ×
5 × ×
6 × ×
7 × × ×
8 ×
9 × ×
10 × ×
11 × × ×
....
 Hamming Code

Step 4: Now we perform even parity check for each column of the
above table. Set a parity bit to 1 to ‘f1’ if the total number of ones in
the corresponding positions of its column is
odd. Set a parity bit to 0 if the total number of ones in the positions
it checks is even. Then, we repeat this process for ‘f2’, ‘f4’, ‘f8’ and
so on.
 Hamming Code
Example: Suppose we have to transmit a data block 7 bits: 1001101. We
need to generate a hamming code of this data block.
Step 1: We need to determine minimum value of ‘r’ first, where 2r >= 7+r+1.
We find r = 4.
Step 2: The codeword will be looked like as follows:
11 10 9 8 7 6 5 4 3 2 1
1 0 0 f8 1 1 0 f4 1 f2 f1
Step 3 & 4: Determination of redundancy bits:
f1 depends upon the bits in the positions of 3, 5, 7, 9, 11. Number of ones
is 3, which is odd. To make it even, the redundancy bit f1 will be 1
f2 depends upon the bits in the positions of 3, 6, 7, 10 and 11. Number of
ones is 4, which is even. So, the redundancy bit f2 will be 0
Following the similar procedure, the value of f4 and f8 will be 0 and 1
respectively
Hence the final codeword will be as follows:

11 10 9 8 7 6 5 4 3 2 1
1 0 0 1 1 1 0 0 1 0 1
 Hamming Code
Illustration:

f1

f2

f4

f8
 Hamming Code
• Error Detection and Correction:
Suppose in the above example the 5th bit is changed from 0 to 1
during data transmission, then it gives new parity values for the
codeword:
11 10 9 f8 7 6 5 f4 3 f2 f1 11 10 9 f8 7 6 5 f4 3 f2 f1
1 0 0 1 1 1 0 0 1 0 1 1 0 0 1 1 1 1 0 1 0 1
Sent bits Received bits
Bit Positions Number New Parity The bits give the binary number
of 1s values as 0101 whose decimal
representation is 5. Thus, the bit
f1,3,5,7,9,11 5 (odd) 1 5 contains an error. To correct
f2,3,6,7,10,11 4 (even) 0 the error the 5th bit is changed
from 1 to 0.
f4,5,6,7 3 (odd) 1
f8,9,10,11 2 (even) 0
 Hamming Code

• Exercise 1: An error correcting code has the following code

words: 00000000, 00001111, 01010101, 10101010, 11110000. What is the
maximum number of bit errors that can be corrected?
Answer: Minimum hamming distance between any pair of codewords, d =
4 (check every pair). If maximum bit that can be corrected = k, then
d = 2k + 1,
⇒ 4 = 2k + 1
⇒ K = 3/2 = 1.5, So maximum bit error that ca be corrected will be 1.
 Hamming Code
• Exercise 2: Assume that a 12-bit Hamming codeword consisting of 8-bit
data and 4-bit check bits is d8 d7 d6 d5 c8 d4 d3 d2 c4 d1 c2 c1, where
the data bits and the check bits are given in the following tables:
Data Bits Check bits
d8 d7 d6 d5 d4 d3 d2 d1 c8 c4 c2 c1
1 1 0 x
Determine x and y. 0 1 0 1 y 0 1 0

b12 b11 b10 b9 b8 b7 b6 b5 b4 b3 b2 b1

Answer: Codeword is:
d8 d7 d6 d5 c8 d4 d3 d2 c4 d1 c2 c1

▪ b1 ⊕ b3 ⊕ b5 ⊕ b7 ⊕ b9 ⊕ b11 = 0 c1 ⊕ d1 ⊕ d2 ⊕ d4 ⊕ d5 ⊕ d7 = 0 0 ⊕ 1 ⊕
0⊕0⊕x⊕1=0 x=0
▪ b2 ⊕ b3 ⊕ b6 ⊕ b7 ⊕ b10 ⊕ b11 = 0 c2 ⊕ d1 ⊕ d3 ⊕ d4 ⊕ d6 ⊕ d7 = 0 1 ⊕ 1
⊕ 1 ⊕ 0 ⊕ 0 ⊕ 1 = 0 (No x or y)
▪ b4 ⊕ b5 ⊕ b6 ⊕ b7 ⊕ b12 = 0 c4 ⊕ d2 ⊕ d3 ⊕ d4 ⊕ d8 = 0 0 ⊕ 0 ⊕ 1 ⊕ 0 ⊕ 1
= 0 (No x or y)
▪ b8 ⊕ b9 ⊕ b10 ⊕ b11 ⊕ b12 = 0 c8 ⊕ d5 ⊕ d6 ⊕ d7 ⊕ d8 = 0 y ⊕ x ⊕ 0 ⊕ 1 ⊕
1 = 0 y =0
 Forward Error Correction (FEC)

• Forward error correction (FEC) is an error correction

technique to detect and correct a limited number of errors in
transmitted data without the need for retransmission.
• The sender sends a redundant error-correcting code along
with the data frame.
• The receiver performs necessary checks based upon the
additional redundant bits.
• If it finds that the data is free from errors, it executes
error-correcting code that generates the actual frame.
• It then removes the redundant bits before passing the
message to the upper layers
 Advantages and Disadvantages

• Because FEC does not require handshaking between the

source and the destination, it can be used for broadcasting of
data to many destinations simultaneously from a single
source.
• Another advantage is that FEC saves bandwidth required for
retransmission. So, it is used in real time systems.
• Its main limitation is that if there are too many errors, the
frames need to be retransmitted.
 Types of FEC
Block codes
• A block code encoder divides the information sequence "u"
into message blocks of "k" information bits (symbols) and
converts each message "u" into an n-bit code (symbols). The
coding rate is defined as "R = k/n". The redundant bits
(symbols), n-k, give the code the ability to deal with channel
noise.
• The minimum distance, dmin, between two closest codewords,
which specifies the minimum amount of data changes required
to turn one valid codeword into another, is an essential
parameter of a block code. This parameter determines a
code's ability to detect and rectify errors.
• Usually, an FEC code can detect and correct up to
(dmin-1)/2 mistakes per codeword.
 Types of FEC

Convolutional codes
• A convolutional code encoder accepts k-bit blocks of the
information sequence "u" and generates an encoded
sequence "v" of n-symbol blocks. However, each encoded
block is dependent on "m" prior message blocks and the
matching k-bit message block at the same time unit.
• To provide reliable transmission across a noisy channel and
redundant bits, n-k, further redundancy is added by raising the
memory order "m" of the code.
 Medium Access control
Methods –CSMA, CSMA/CA &
/CD
MULTIPLE ACCESS PROTOCOLS

• When nodes or stations are connected and use a common link called
a multipoint or broadcast link. We need a multiple-access protocol to
coordinate access to the link.
• The problem of controlling the access to the medium is similar to the
rules of speaking in an assembly.
• The procedures guarantee that the right to speak is upheld and ensure
that
• Two people do not speak at the same time,

• Do not interrupt each other,

• Do not monopolize the discussion, and so on.

Taxonomy of Multiple-Access Protocols
Random Access Methods
In random access or contention methods, no station is
superior to another station and none is assigned the control
over another.

No station permits, or does not permit, 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.

This procedure depends on the state of the medium

whether it is idle or busy.
Reason for Random Access or Contention

Two features give this methods its name

No scheduled time for a station to transmit and Transmission

is random among the stations. So these methods are called
random access.

No specific rules as which station should send next . Stations

compete with one another to access the medium. So called
Contention methods
Procedure followed by Station for Random Access

Each station has the right to the medium without being controlled by
another station
If more than one station tries to send, there is an access conflict-
collision and frames will be either destroyed or modified
To avoid access conflict or to resolve it when it happens, each
station follows a procedure which answers the following queries:
▪ When can station access the medium
▪ What can station do if medium is busy
▪ How can the station determine the success or failure of the
transmission
▪ What can station do if there is an access conflict
 Random access methods we would be studying have evolved
from a very interesting protocol known as ALOHA which uses a
very simple procedure called Multiple Access (MA)

Method was later improved with the addition of procedure that

forces the station to sense the medium before transmitting.
This was called Carrier Sense Multiple Access

This later evolved into two parallel methods

▪ Carrier Sense Multiple Access (CSMA)

▪ Carrier Sense Multiple Access with Collision Detection and

Avoidance (CSMA/CD) & (CSMA/CA)

97
CSMA protocol

■ To minimize the chance of collisions and increase the performance, the

CSMA (Carrier Sense Multiple Access) method was developed

■ CSMA requires that each station first listen to the medium before sending

■ CSMA can reduce the possibility of collision but cannot eliminate it.

■ Possibility of collisions still exists due to propagation delay

■ Two CSMA protocols developed were: Persistent and non-persistent

Vulnerable time in CSMA
■ Vulnerable time in CSMA is the propagation time which is Tp i.e.
time needed for a signal to propagated from one end to other.

■ When a station sends a frame and any other station sends a frame
during this time, a collision will result.

■ But if the first bit of frame reaches the end of medium, every
station will have heard the bit and will refrain from sending.

■ Figure in next slide shows the worst case where a frame sent by
station A at time t1 reaches the rightmost station D at time t1+ Tp
Vulnerable Time in CSMA
Behavior of three persistence methods
1-Persistent CSMA protocol

When station finds the medium is idle, it sends its frame

immediately with a probability of 1.

If the medium is busy it waits until it becomes idle and sends its
frame with a probability of 1.

Method has highest chance of collisions because two or more

stations may find the line idle and send their frames immediately.
Non-persistent CSMA protocol
■ Station senses a channel
■ If channel is idle, station begins transmitting
■ If channel is busy, station does not continually wait for accessing the
channel
■ Instead it waits a random period of time and then repeats algorithm again-
Exponential Back off
■ This method reduces the collision as it is unlikely two or more stations
will wait the same amount of time and retry to send simultaneously
p-persistent CSMA protocol
This method is used if channel has time slots with slot duration
equal to or greater than maximum propagation time
p-persistence approach combines the advantages of other two
methods.
Reduces the chances of collision and improves efficiency
Here once the station finds the line is idle, it follows these steps:
i With probability p, station sends its frame
ii With probability q= 1-p, station waits for beginning of the next
time slot and checks the line again
a. If line is idle, it goes to step i
b. If line is busy, it acts as collision has occurred and uses back off
procedure.
Flow Diagram of three persistence methods
Carrier Sense Multiple Access with Collision
Detection
(CSMA/CD)
CSMA method does not specify the procedure following a collision

CSMA/CD augments the algorithm to handle collision

In this method, a station monitors the medium after it sends a frame

to see if the transmission was successful

If successful, the station is finished

If not, frame is sent again.

We can better understand CSMA/CD with the diagram in next

slide.
Collision of first bit in CSMA/CD
 At time t1, Station A has executed the persistence procedure and
starts sending the bits of its frame
At time t2 station C has not yet sensed the first bit sent by A .
Station C executes its persistence procedure and starts sending
bits in frame which propagates to both left and right
Collision occurs after time t2.
Station C detects a collision at time t3
when it receives first bit of A’s frame.
Station C aborts its transmission
Station A detects collision at time t4 when it receives first bit of C’s
frame; it also aborts its transmission immediately.
We see that A transmits for a duration of t4-t1; C transmits for
duration of t3-t2.
At time t4 transmission of A’s frame though incomplete is aborted;
time t3 transmission of C’s frame though incomplete is aborted
Collision and abortion in CSMA/CD
Minimum Frame size for CSMA/CD
For CSMA/CD we need restriction of the frame size

Before sending the last bit of frame, sending station must detect
collision , if any must abort the transmission

Reason for this is a station once sent the entire frame does not
monitor the line for collision detection

So, Frame Transmission time Tfr = 2 * Tp

If two stations involved in collision are maximum distance apart,

signals from first takes time Tp to reach the second and effect of
collision takes another time Tp to reach the first.

Requirement is first station should still be transmitting after 2 Tp

Flow Diagram for CSMA/CD
 Example

A network using CSMA/CD has a bandwidth of 10 Mbps. If the

maximum propagation time (including the delays in the devices and
ignoring the time needed to send a jamming signal, as we see later)
is 25.6 μs, what is the minimum size of the frame?

Solution
The frame transmission time is Tfr = 2 × Tp = 51.2 μs. This means, in the worst
case, a station needs to transmit for a period of 51.2 μs to detect the collision. The
minimum size of the frame is 10 Mbps × 51.2 μs = 512 bits or 64 bytes. This is
actually the minimum size of the frame for Standard Ethernet.
HDLC and PPP
The Data Link Layer in the Internet
A home personal computer acting as an internet host.

Technology like Ethernet cannot provide

“high-level” functionality like connection
management and parameter negotiation
Point to Point Data Link Control

• One sender, one receiver, one link: easier than broadcast

link:
• No Media Access Control
• No need for explicit MAC addressing
• E.g., dialup link, ISDN line
• Popular point-to-point and high-level DLC protocols:
• PPP (point-to-point protocol)
• HDLC: High level data link control (Data link used to be
considered “high layer” in protocol stack). HDLC is also used in
multi-point links (one station many receivers)

• These protocols can often be run over other data link

technologies providing best of both worlds
• E.g., PPPoE, HDLC encapsulation by Ethernet

115
PPP Design Requirements [RFC 1557]

Functionality : (similar to link layer services + extra

management functions)
• Packet framing - encapsulation of network-layer
datagram in data link frame
• Multi-protocol - carry network layer data of any network layer
protocol (not just IP) at same time ability to demultiplex
upwards
• Bit transparency - must carry any bit pattern in the data
field (even if underlying channel can't)
• Error detection - not correction

116
PPP Design Requirements (cont.)

The extra stuff:

• Connection liveness: detect, signal link failure to network
layer
• Network layer address negotiation: endpoint can
learn/configure each other’s network address and other
characteristics.
• Authentication: who are you (or at least whose account do
I bill for your dial-in time?)
• This information is used by traffic management software to control
bandwidth to individual subscribers
• Management features: loopback detection

117
PPP non-requirements

• No error correction/recovery
(modems do one layer FEC, one layer packetization +
retransmission “under the covers” anyway; other
technologies are pretty reliable)
• No flow control
• Out of order delivery OK

Error recovery, flow control, data re-ordering

all relegated to higher layers!

118
PPP Data Frame

• Flag: delimiter (framing)

• Address: ignored. (historical)
• Control: ignored. (historical)
• Protocol: upper layer protocol to which frame
delivered (e.g., PPP-LCP, IP, IPCP, etc)

119
PPP Data Frame

• info: upper layer data being carried

• check: cyclic redundancy check for error detection

120
 Byte Stuffing

flag byte
pattern
in data
to send

flag byte pattern

plus
stuffed byte in
transmitted data
PPP Data Control Protocol

Before exchanging network-layer

data, data link peers must
• Configure PPP link (max. frame
length, authentication)
• Learn/configure network
layer information
• for IP: carry IP Control
Protocol (IPCP) msgs
(protocol field: 8021) to
configure/learn IP address

122
Where does PPP get used?

• Dial-up – PPP over async serial, over modem

• ADSL – PPP over Ethernet
• Backbone – Packet over SONET (POS)
• Why?
• Framing (dialup, POS)
• Efficiency (POS)
• Authentication, address negotiation (PPPoE)

123
 High-Level Data Link Control (HDLC)

• HDLC was defined by ISO for use on both

point-to-point and multipoint data links.
• It supports full-duplex communication
• Other similar protocols are
• Synchronous Data Link Control (SDLC) by IBM
• Advanced Data Communication Control Procedure (ADCCP)
by ANSI
• Link Access Procedure, Balanced (LAP-B) by CCITT, as part
of its X.25 packet-switched network standard
 HDLC Overview

Broadly HDLC features are as follows:

• Reliable protocol
• selective repeat or go-back-N
• Full-duplex communication
• receive and transmit at the same time
• Bit-oriented protocol
• use bits to stuff flags occurring in data
• Flow control
• adjust window size based on receiver capability
• Uses physical layer clocking and synchronization to
send and receive frames
 HDLC Overview

• Defines three types of stations

• Primary
• Secondary
• Combined
• Defines three types of data transfer mode
• Normal Response mode
• Asynchronous Response mode
• Asynchronous Balanced mode
• Three types of frames
• Unnumbered
• information
• Supervisory
 HDLC

• The three stations are :

• Primary station
• Has the responsibility of controlling the operation of data flow the
link.
• Handles error recovery
• Frames issued by the primary station are called commands.
• Secondary station,
• Operates under the control of the primary station.
• Frames issued by a secondary station are called responses.
• The primary station maintains a separate logical link with each
secondary station.
• Combined station,
• Acts as both as primary and secondary station.
• Does not rely on other for sending data
 HDLC

Unbalanced Mode
Commands
Primary
Responses

Secondary Secondary

Balanced
mode
Combined Combined
commands/Responses
 HDLC

• The three modes of data transfer operations are

• Normal Response Mode (NRM)
• Mainly used in terminal-mainframe networks. In this case,
• Secondaries (terminals) can only transmit when specifically instructed by the
primary station in response to a polling
• Unbalanced configuration, good for multi-point links
• Asynchronous Response Mode (ARM)
• Same as NRM except that the secondaries can initiate transmissions without
direct polling from the primary station
• Reduces overhead as no frames need to be sent to allow secondary nodes to
transmit
• Transmission proceeds when channel is detected idle , used mostly in
point-to-point-links
• Asynchronous Balanced Mode (ABM)
• Mainly used in point-to-point links, for communication between combined
stations
 Non-operational Modes

• Normal Disconnected Mode

• Asynchronous Disconnected Mode

Both the above modes mean that the secondary node is logically
disconnected from the primary node

• Initialization Mode
• A node negotiates transmission parameters with the other node E.g., flow
control information
• Parameters negotiated in this mode are used during any of the data
transfer modes
Data Link Control HDLC frame structure

(a) Frame
Format

(b) Control
field
format
 Data Link Control
HDLC frame structure

(c) Extended address field (d) Extended control field

 HDLC

• Flag: 01111110- start and ending delimiter. Bits are stuffed for flags in data frames
• FCS: 16-bit CRC using generating polynomial
G(x) = x16 + x12 + x5 + 1
• Address field:
• mainly used in multidrop link configuration, and not used in point-to-point
• In unbalanced configuration, every secondary is assigned a unique address. Contains
address of secondary station in both command and response frames
• In balanced mode, command frame has destination address and response frame has sending
node’s address
• Group addresses are also possible. E.g., One command sent to all the secondaries
• In I-frames, N(s) is the sequence number of the frame being sent, and R(s) is the
sequence number of the frame being expected.
• The P/F bit, known as the poll/final bit, is used with different meaning in different
contexts.
• It is used to indicate polling, to indicate the final I-frame, etc
 HDLC

• There are three different classes of frames used in

HDLC
• Unnumbered frames, used in link setup and disconnection,
and hence do not contain ACK.
• Information frames, which carry actual information. Such
frames can piggyback ACK in case of ABM
• Supervisory frames, which are used for error and flow
control purposes and hence contain send and receive sequence
numbers
 HDLC

• There are four different supervisory frames

• SS=00, Receiver Ready (RR), and N(R) ACKs all frames
received up to and including the one with sequence number
N(R) - 1
• SS=10, Receiver Not Ready (RNR), and N(R) has the same
meaning as above
• SS=01, Reject; all frames with sequence number N(R) or
higher are rejected, which in turns ACKs frames with
sequence number N(R) -1 or lower.
• SS=11, Selective Reject; the receive rejects the frame with
sequence number N(R)
 HDLC

• The unnumbered frames can be grouped into the following

categories:
• Mode-setting commands and responses
• Recovery commends and responses
• Miscellaneous commands and responses
 Review of Link Layer

• Services
• Framing
• Error control
• Reliability
• Connection management
• Medium access control
• Switching
• Protocols, Standards
• Ethernet
• Token Ring
• FDDI
• Wireless
• PPP
• HDLC