BCS502 - COMPUTER NETWORKS Module 2 Notes

Module-2
Data Link Layer: Error Detection and Correction
Networks must be able to transfer data from one device to another with acceptable accuracy. A
system must guarantee that the data received are identical to the data transmitted. Many factors
can alter one or more bits of a message when it is transmitted from one node to another. Some
applications require a mechanism for detecting and correcting errors.

Random errors in audio or video transmissions may be tolerable, but when we transfer text, we
expect a very high level of accuracy.

Types of Errors

Whenever bits flow from one point to another, they are subject to unpredictable changes
because of interference. This interference can change the shape of the signal.

The single-bit error means that only 1 bit of a given data unit (such as a byte, character, or
packet) is changed from 1 to 0 or from 0 to 1. The burst error means that 2 or more bits in the
data unit have changed from 1 to 0 or from 0 to 1.

A burst error is more likely to occur than a single-bit error because the duration of the noise
signal is normally longer than the duration of 1 bit, which means that when noise affects data,
it affects a set of bits. The number of bits affected depends on the data rate and duration of
noise. If we are sending data at 1 kbps, a noise of 1/100 second can affect 10 bits

1kbps = 1000 bits per second

Duration of noise = 1/100 second

Number of bits affected = 1000 * 1/100 = 10 bits.

Dilip. S, Dept. of AIML Page 1 of 57 Vemana IT

BCS502 - COMPUTER NETWORKS Module 2 Notes

Similarly if we are sending data at 1 mbps, a noise of 1/100 second can affect 10000 bits

1mbps = 1000000 bits per second

Duration of noise = 1/100 second

Number of bits affected = 1000000 * 1/100 = 10000 bits.

Redundancy

To detect or correct errors, we need to send some extra bits with our data known as redundant
bits. These redundant bits are added by the sender and removed by the receiver. Redundant bits
allow the receiver to detect or correct corrupted bits.

Detection versus Correction

The process of detecting errors is known as error detection. The process of correcting detected
errors is known as error correction.

In error detection, we are only looking to see if any error has occurred. We are not even
interested in the number of corrupted bits. A single-bit error is the same for us as a burst error.

In error correction, we need to know the exact number of bits that are corrupted and, more
importantly, their location in the message.
If we need to correct a single error in an 8-bit data unit, we need to consider eight possible error
locations. if we need to correct two errors in 8-bit data unit we need to consider 8C2 = 28
possibilities.

Coding

Redundancy is achieved through various coding schemes. We can divide coding schemes into
two broad categories: block coding and convolution coding.

Block Coding

In block coding, we divide 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. With k bits, we can create a combination of 2k datawords; with n bits, we can create
a combination of 2n codewords. The block coding process is one-to-one; the same data word is
always encoded as the same codeword. 2n − 2k codewords that are not used. These codewords
invalid or illegal.

Dilip. S, Dept. of AIML Page 2 of 57 Vemana IT

BCS502 - COMPUTER NETWORKS Module 2 Notes

Error Detection in block coding

If the following two conditions are met, the receiver can detect errors.

1. The receiver has (or can find) a list of valid codewords.

2. The original codeword has changed to an invalid one.

Process of error detection in block coding

The sender creates code words out of datawords by using a generator. Each codeword sent to
the receiver. If the received codeword is the same as one of the valid codewords, the word is
accepted; the corresponding dataword is extracted for use. If the received code word is not
valid, it is discarded. One of the limitation of this approach is if the codeword is corrupted
during transmission but the received word still matches a valid codeword, the error remains
undetected.

Example

Let us assume that k = 2 and n = 3.

Assume the sender encodes the dataword 01 as 011 and sends it to the receiver. Consider the
following cases:

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

Dilip. S, Dept. of AIML Page 3 of 57 Vemana IT

BCS502 - COMPUTER NETWORKS Module 2 Notes

2. The codeword is corrupted during transmission, and 111 is received (the leftmost bit is cor
rupted). This is not a valid codeword and is discarded.

3. The codeword is corrupted during transmission, and 000 is received (the right two bits are
corrupted). This is a valid codeword. The receiver incorrectly extracts the dataword 00. Two
corrupted bits have made the error undetectable.

Hamming Distance

The Hamming distance between two words (of the same size) is the number of differences
between the corresponding bits. Hamming distance between two words x and y is represented
as d(x, y).

Hamming distance between the received codeword and the sent codeword is the number of bits
that are corrupted during transmission.

For example, if the codeword 00000 is sent and 01101 is received, 3 bits are in error and the
Hamming distance between the two is d(00000, 01101) = 3.

The Hamming distance can easily be found if we apply the XOR operation (⊕) on the two
words and count the number of 1s in the result. Note that the Hamming distance is a value
greater than or equal to zero.

Minimum Hamming Distance for 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.

Linear Block Codes

A linear block code is a code in which the exclusive OR (addition modulo-2) of two valid
codewords creates another valid codeword.

Minimum Distance for Linear Block Codes

The minimum Hamming distance is the number of 1s in the nonzero valid codeword with the
smallest number of 1s.

Parity-Check Code

Dilip. S, Dept. of AIML Page 4 of 57 Vemana IT

BCS502 - COMPUTER NETWORKS Module 2 Notes

Parity-Check Code is a linear block code. In this code, a k-bit dataword is changed to an n-bit
codeword where n = k + 1. The extra bit, called the parity bit, is selected to make the total
number of 1s in the codeword even.

Simple parity-check code C(5, 4)

Encoder and decoder for simple parity-check code

The encoder uses a generator that takes a copy of a 4-bit dataword (a0, a1, a2, and a3) and
generates a parity bit r0. The dataword bits and the parity bit create the 5-bit codeword. The
parity bit that is added makes the number of 1s in the codeword even.

r0 = a3 + a2 + a1 + a0 (modulo-2)

The sender sends the codeword, which may be corrupted during transmission. The receiver
receives a 5-bit word. The checker at the receiver does the same thing as the generator in the
sender the addition is done over all 5 bits. The result, which is called the syndrome, is just 1
bit.

s0 = b3 + b2 + b1 + b0 + q0 (modulo-2)

Dilip. S, Dept. of AIML Page 5 of 57 Vemana IT

BCS502 - COMPUTER NETWORKS Module 2 Notes

The syndrome is passed to the decision logic analyzer. If the syndrome is 0, there is no
detectable error in the received codeword; the data portion of the received code word is
accepted as the dataword; if the syndrome is 1, the data portion of the received codeword is
discarded. The dataword is not created.

Example:

Let us look at some transmission scenarios. Assume the sender sends the dataword 1011. The
code word 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
data word is created. Note that although none of the dataword bits are corrupted, no dataword
is created because the code is not sophisticated enough to show the position of the corrupted
bit.

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. The simple parity-check decoder cannot detect an
even number of errors. The errors cancel each other out and give the syndrome a value of 0.

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.

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 result is another codeword.

For example, if 1011000 is a codeword and we cyclically left-shift, then 0110001 is also a
codeword. In this case, if we call the bits in the first word a0 to a6, and the bits in the second
word b0 to b6, we can shift the bits by using the following: b1 = a0 b2 = a1 b3 = a2 b4 = a3 b5 = a4

Dilip. S, Dept. of AIML Page 6 of 57 Vemana IT

BCS502 - COMPUTER NETWORKS Module 2 Notes

b6 = a5 b0 = a6 In the rightmost equation, the last bit of the first word is wrapped around and
becomes the first bit of the second word.

Cyclic Redundancy Check (CRC)

CRC encoder and decoder

• In the encoder, the dataword has k bits, the codeword has n bits.
• n – k bits 0s are appended to the right hand side of dataword.
• The n-bit result is fed into the generator. The generator uses a divisor of size n − k + 1,
predefined and agreed upon.
• The generator divides the augmented dataword by the divisor (modulo-2 division).
• The quotient of the division is discarded; the remainder ( n-k bits ) is appended to the
dataword to create the codeword.
• The decoder receives the codeword. A copy of all n bits is fed to the checker, which is
a replica of the generator.
• The remainder produced by the checker is a syndrome of n – k which is fed to the
decision logic analyzer.
• Analyzer checks If the syndrome bits are all 0s, the k left most bits of the codeword
are accepted as the dataword (interpreted as no error) else the k bits are discarded
(error).

Example - Encoder

Dilip. S, Dept. of AIML Page 7 of 57 Vemana IT

BCS502 - COMPUTER NETWORKS Module 2 Notes

Example – Decoder

Polynomials

A pattern of 0s and 1s can be represented as a polynomial with coefficients of 0 and 1. The

power of each term shows the position of the bit; the coefficient shows the value of the bit.

Dilip. S, Dept. of AIML Page 8 of 57 Vemana IT

BCS502 - COMPUTER NETWORKS Module 2 Notes

A polynomial to represent a binary word

Degree of a Polynomial

The degree of a polynomial is the highest power in the polynomial. For example, the degree of
the polynomial x6 + x + 1 is 6. Note that the degree of a polynomial is 1 less than the number
of bits in the pattern. The bit pattern in this case has 7 bits.

Adding and Subtracting Polynomials

Adding and subtracting polynomials in mathematics are done by adding or subtracting the
coefficients of terms with the same power.

If the coefficients are only 0 and 1, and adding is in modulo-2 and addition and subtraction are
the same (2 mod 2 = 0 in case of addition and 1-1 =0 in case of subtraction).

Adding x5 + x4 + x2 and x6 + x4 + x2 gives just x6 + x5

Multiplying or Dividing Terms

Multiplying a term by another term is just adding the powers.

Ex: x3 × x4 is x7

For dividing, we just subtract the power of the second term from the power of the first.

Ex: x5/x2 is x3.

Multiplying Two Polynomials

Multiplying a polynomial by another is done term by term. Each term of the first polynomial
must be multiplied by all terms of the second.

(x5 + x3 + x2 + x)(x2 + x + 1) = x7 + x6 + x5 + x5 + x4 + x3 + x4 + x3 + x2 + x3 + x2 + x = x7 + x6
+ x3 + x

Dividing One Polynomial by Another

Dilip. S, Dept. of AIML Page 9 of 57 Vemana IT

BCS502 - COMPUTER NETWORKS Module 2 Notes

Division of polynomials is conceptually the same as the binary division we discussed for an
encoder. We divide the first term of the dividend by the first term of the divisor to get the first
term of the quotient. We multiply the term in the quotient by the divisor and subtract the result
from the dividend. We repeat the process until the dividend degree is less than the divisor
degree.

Shifting

A binary pattern is often shifted a number of bits to the right or left. Shifting to the left means
adding extra 0s as rightmost bits; shifting to the right means deleting some right most bits.
Shifting to the left is accomplished by multiplying each term of the polynomial by xm, where
m is the number of shifted bits; shifting to the right is accomplished by dividing each term of
the polynomial by xm. We do not have negative powers in the polynomial representation.

Cyclic Code Encoder Using Polynomials

Consider the dataword 1001 is represented as x3 + 1. The divisor 1011 is represented as x3 + x

+ 1.

To find the augmented dataword, we have left-shifted the dataword 3 bits (multiplying the
dataword by x3). The result is x6 + x3.

Dilip. S, Dept. of AIML Page 10 of 57 Vemana IT

BCS502 - COMPUTER NETWORKS Module 2 Notes

The divisor in a cyclic code is normally called the generator polynomial or simply the generator.

Cyclic Code Analysis

We can analyze a cyclic code to find its capabilities by using polynomials. We define the
following, where f(x) is a polynomial with binary coefficients.

Dataword: d(x) Codeword: c(x) Generator: g(x) Syndrome: s(x) Error: e(x)

If s(x) is not zero, then one or more bits is corrupted. However, if s(x) is zero, either no bit is
corrupted or the decoder failed to detect any errors.

The received codeword is the sum of the sent codeword and the error.

Received codeword = c(x) + e(x)

The receiver divides the received codeword by g(x) to get the syndrome.

The first term at the right-hand side of the equality has a remainder of zero. So the syndrome
is actually the remainder of the second term on the right-hand side. If this term does not have

Dilip. S, Dept. of AIML Page 11 of 57 Vemana IT

BCS502 - COMPUTER NETWORKS Module 2 Notes

a remainder (syndrome = 0), either e(x) is 0 or e(x) is divisible by g(x). In a cyclic code, those
e(x) errors that are divisible by g(x) are not caught.

Single-Bit Error

If the generator has more than one term and the coefficient of x0 is 1, all single-bit errors can
be caught.

Two Isolated Single-Bit Errors

If a generator cannot divide xt + 1 (t between 0 and n - 1), then all isolated double errors can
be detected.

Odd Numbers of Errors

A generator that contains a factor of x + 1 can detect all odd-numbered errors.

Burst error

If L is the length of error and r is the length of remainder then

All burst errors with L ≤ r will be detected.

All burst errors with L = r + 1 will be detected with probability 1 – (1/2)r–1

All burst errors with L > r + 1 will be detected with probability 1 – (1/2)r.

A good polynomial generator needs to have the following characteristics: 1. It should have at
least two terms.

2. The coefficient of the term x0 should be 1.

3. It should not divide xt + 1, for t between 2 and n - 1.

4. It should have the factor x + 1.

Dilip. S, Dept. of AIML Page 12 of 57 Vemana IT

BCS502 - COMPUTER NETWORKS Module 2 Notes

Standard Polynomials

ATM (Asynchronous Transfer Mode )

AAL (ATM Adaptation Layer)

HDLC (High-level Data Link Control)

Advantages of Cyclic Codes

1. Cyclic codes have a very good performance in detecting single-bit errors, double errors,
an odd number of errors, and burst errors.
2. They can easily be implemented in hardware and software.
3. They are fast when implemented in hardware.

Other Cyclic Codes

Reed Solomon code used today for both detection and correction.

Hardware Implementation

Encoder and decoder can easily and cheaply be implemented in hardware by using a handful
of electronic devices.

Dilip. S, Dept. of AIML Page 13 of 57 Vemana IT

BCS502 - COMPUTER NETWORKS Module 2 Notes

General design of encoder and decoder of a CRC code

We have n – k, 1-bit shift registers in both the encoder and decoder. We have up to n – k, XOR
devices.

Checksum

Checksum is an error-detecting technique that can be applied to a message of any length.

At the source, the message is first divided into m-bit units. The generator then creates an extra
m-bit unit called the checksum, which is sent with the message. At the destination, the checker
creates a new checksum from the combination of the message and sent checksum. If the new
checksum is all 0s, the message is accepted; otherwise, the message is discarded.

Checksum

One’s Complement Addition

Dilip. S, Dept. of AIML Page 14 of 57 Vemana IT

BCS502 - COMPUTER NETWORKS Module 2 Notes

One’s complement of a number is obtained by changing 1 to 0 and 0 to 1. In One’s complement

addition given numbers are first converted to 1’s complement and added. If there is a carry over
it is added to right most bit.

Example:

Sender side

7 = 0111, 11 = 1011, 12 = 1100, 0 = 0000, 6 = 0110, 0 = 0000

Adding 2 words at a time in 1’s complement we get

0111+ 1011= 1 0010 = 0011

0011+ 1100 = 1111

1111 + 0000 = 1111

1111+ 0110 =1 0101 = 0110

0110 + 0000 = 0110 = 6

Finally we take 1’s complement of 0110 to get 1001 = 9

Receiver side

7 = 0111, 11 = 1011, 12 = 1100, 0 = 0000, 6 = 0110, 9 = 1001

0111+ 1011= 1 0010 = 0011

0011+ 1100 = 1111

1111 + 0000 = 1111

1111+ 0110 =1 0101 = 0110

Dilip. S, Dept. of AIML Page 15 of 57 Vemana IT

BCS502 - COMPUTER NETWORKS Module 2 Notes

0110 + 1001= 1111 = 15

Finally we take 1’s complement of 1111 to get 0000 = 0

Since the calculated checksum is 0 the message is accepted.

Internet Checksum

Flowchart to calculate a traditional checksum

Performance

Dilip. S, Dept. of AIML Page 16 of 57 Vemana IT

BCS502 - COMPUTER NETWORKS Module 2 Notes

It is not as strong as the CRC in error-checking capability.

For example, if the value of one word is incremented and the value of another word is
decremented by the same amount, the two errors cannot be detected because the sum and
checksum remain the same.

If the values of several words are incremented but the sum and the checksum do not change,
the errors are not detected.

Other checksums

Fletcher Checksum

Fletcher has proposed two algorithms: 8-bit and 16-bit. The first, 8-bit Fletcher, calculates on
8-bit data items and creates a 16-bit checksum. The second, 16-bit Fletcher, calculates on 16-
bit data items and creates a 32-bit checksum.

The calculation is done modulo 256 (28), which means the intermediate results are divided by
256 and the remainder is kept. The algorithm uses two accumulators, L and R. The first simply
adds data items together; the second adds a weight to the calculation.

The 16-bit Fletcher checksum is similar to the 8-bit Fletcher checksum, but it is calculated over
16-bit data items and creates a 32-bit checksum. The calculation is done modulo 65,536

Flowchart to calculate an 8-bit Fletcher checksum

Adler Checksum

Dilip. S, Dept. of AIML Page 17 of 57 Vemana IT

BCS502 - COMPUTER NETWORKS Module 2 Notes

It is similar to the 16-bit Fletcher with three differences. First, calculation is done on single
bytes instead of 2 bytes at a time. Second, the modulus is a prime number (65,521) instead of
65,536. Third, L is initialized to 1 instead of 0. It has been proved that a prime modulo has a
better detecting capability in some combinations of data.

Flowchart to calculate an Adler checksum

DLC(Data Link Control) Services

The data link control (DLC) deals with procedures for communication between two adjacent
nodes—node-to-node communication.

Data link control functions include framing and flow and error control.

Framing

Data transmission in the physical layer means moving bits in the form of a signal from the
source to the destination. The data-link layer, needs to pack bits into frames, so that each frame
is distinguishable from another. Framing in the data-link layer separates a message from one
source to a destination by adding a sender MAC address and a destination MAC address.

Frame Size

Dilip. S, Dept. of AIML Page 18 of 57 Vemana IT

BCS502 - COMPUTER NETWORKS Module 2 Notes

Frames can be of fixed or variable size. In fixed-size framing, there is no need for defining the
boundaries of the frames; the size itself can be used as a delimiter. An example of this type of
framing is the ATM WAN, which uses frames of fixed size called cells of 53 bytes size.

In variable-size framing, we need a way to define the end of one frame and the beginning of
the next. There are two types of framing a character-oriented framing and a bit-oriented
framing.

Character-Oriented Framing

Data to be carried are 8-bit characters which are encoded using ASCII.

The header, carries the source and destination addresses and other control information

The trailer, which carries error detection redundant bits, are also multiples of 8 bits.

To separate one frame from the next, an 8-bit flag is added at the beginning and the end of a
frame.

A frame in a character-oriented protocol

The flag, is composed of protocol-dependent special characters, which signals the start or end
of a frame. The flag could be selected to be any character not used for text communication.
When we send other types of information such as graphs, audio, and video if the flag selected
is part of the data sent then the receiver, when it encounters this pattern in the middle of the
data, thinks it has reached the end of the frame.

To overcome the above problem a byte-stuffing strategy was added to character-oriented

framing. In byte 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. This byte is usually called the escape character
(ESC) and 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.

Dilip. S, Dept. of AIML Page 19 of 57 Vemana IT

BCS502 - COMPUTER NETWORKS Module 2 Notes

Byte stuffing and unstuffing

In general Byte stuffing is the process of adding one extra byte whenever there is a flag or
escape character in the text.

The universal coding systems in use today, such as Unicode, have 16-bit and 32-bit characters
that conflict with 8-bit characters, in general, the tendency is moving toward the use of the bit-
oriented protocols.

Bit-Oriented Framing

In bit oriented framing, most protocols use a special 8-bit pattern flag, 01111110, as the
delimiter to define the beginning and the end of the frame, along with header and trailer.

A frame in a bit-oriented protocol

If the flag appears as part of data we need to somehow inform the receiver that this is not the
end of the frame. We do this by stuffing 1 single bit (instead of 1 byte) to prevent the pattern
from looking like a flag. The strategy is called bit stuffing. In bit stuffing, if a 0 and five
consecutive 1 bits are encountered, an extra 0 is added. This extra stuffed bit is eventually
removed from the data by the receiver.

Dilip. S, Dept. of AIML Page 20 of 57 Vemana IT

BCS502 - COMPUTER NETWORKS Module 2 Notes

Bit stuffing and unstuffing

Flow Control

If the items are produced faster than they can be consumed, the consumer can be overwhelmed
and may need to discard some items. If the items are produced more slowly than they can be
consumed, the consumer must wait, and the system becomes less efficient.

Flow control at the data-link layer

The figure shows that the data-link layer at the sending node tries to push frames toward the
data-link layer at the receiving node. If the receiving node cannot process and deliver the packet
to its network at the same rate that the frames arrive, it becomes overwhelmed with frames.
Flow control in this case can be feedback from the receiving node to the sending node to stop
or slow down pushing frames.

Error Control

The technology at the physical layer is not fully reliable we need to implement error control at
the data-link layer to prevent the receiving node from delivering corrupted packets to its
network layer.

Dilip. S, Dept. of AIML Page 21 of 57 Vemana IT

BCS502 - COMPUTER NETWORKS Module 2 Notes

Error control can be implemented using one of the following two methods. In both methods, a
CRC is added to the frame header by the sender and checked by the receiver.

In the first method, if the frame is corrupted, it is silently discarded; if it is not corrupted, the
packet is delivered to the network layer. This method is used mostly in wired LANs such as
Ethernet.

In the second method, if the frame is corrupted, it is silently discarded; if it is not corrupted, an
acknowledgment is sent (for the purpose of both flow and error control) to the sender.

Combination of Flow and Error Control

Flow and error control can be combined. In a simple situation, the acknowledgment that is sent
for flow control can also be used for error control to tell the sender the packet has arrived
uncorrupted. The lack of acknowledgment means that there is a problem in the sent frame.

Connectionless and Connection-Oriented

Connectionless protocol

In a connectionless protocol, frames are sent from one node to the next without any relationship
between the frames; each frame is independent. the term connectionless here does not mean
that there is no physical connection (transmission medium) between the nodes; it means that
there is no connection between frames.

Connection-Oriented Protocol
In a connection-oriented protocol, a logical connection should first be established between the
two nodes (setup phase). After all frames that are somehow related to each other are transmitted
(transfer phase), the logical connection is terminated (teardown phase). In this type of
communication, the frames are numbered and sent in order. If they are not received in order,
the receiver needs to wait until all frames belonging to the same set are received and then
deliver them in order to the network layer.

DATA-LINK LAYER PROTOCOLS

Simple Protocol

Dilip. S, Dept. of AIML Page 22 of 57 Vemana IT

BCS502 - COMPUTER NETWORKS Module 2 Notes

Simple protocol has neither flow nor error control. It is assumed that the receiver can
immediately handle any frame it receives. the receiver is never overwhelmed with incoming
frames.

Simple protocol

The data-link layer at the sender gets a packet from its network layer, makes a frame out of it,
and sends the frame. The data-link layer at the receiver receives a frame from the link, extracts
the packet from the frame, and delivers the packet to its network layer. The data-link layers of
the sender and receiver provide transmission services for their network layers.

FSM (Finite State Machine)

Each FSM has only one state, the ready state. The sending machine remains in the ready state
until a request comes from the process in the network layer. When this event occurs, the sending
machine encapsulates the message in a frame and sends it to the receiving machine. The
receiving machine remains in the ready state until a frame arrives from the sending machine.
When this event occurs, the receiving machine decapsulates the message out of the frame and
delivers it to the process at the network layer.

FSMs for the simple protocol

Flow diagram for simple protocol

Dilip. S, Dept. of AIML Page 23 of 57 Vemana IT

BCS502 - COMPUTER NETWORKS Module 2 Notes

Flow diagram for simple protocol

Stop-and-Wait Protocol

Stop-and-Wait protocol, uses both flow and error control.

Sender before sending the frame starts a timer and saves the copy of the frame in buffer.

Sender waits for acknowledgement from receiver.

If sender receives acknowledgement, it discards the saved frame from buffer transmits next
frame if it has one.

If the acknowledgement is not received within timeout interval then timer is reset and resends
the buffered frame.

Receiver receives the frame it checks CRC, if the received frame has no error it sends
acknowledgement, if it has any error it is discards the frame.

Stop-and-Wait protocol

FSM

Dilip. S, Dept. of AIML Page 24 of 57 Vemana IT

BCS502 - COMPUTER NETWORKS Module 2 Notes

FSM for the Stop-and-Wait protocol

Sender States

The sender is initially in the ready state, but it can move between the ready and blocking state.

Ready State: When the sender is in this state, it is only waiting for a packet from the network
layer. If a packet comes from the network layer, the sender creates a frame, saves a copy of the
frame, starts the only timer and sends the frame. The sender then moves to the blocking state.

Blocking State: When the sender is in this state, three events can occur:

a. If a time-out occurs, the sender resends the saved copy of the frame and restarts the timer.

b. If a corrupted ACK arrives, it is discarded.

c. If an error-free ACK arrives, the sender stops the timer and discards the saved copy of the
frame. It then moves to the ready state.

Receiver states

The receiver is always in the ready state.

Two events may occur:

Dilip. S, Dept. of AIML Page 25 of 57 Vemana IT

BCS502 - COMPUTER NETWORKS Module 2 Notes

a. If an error-free frame arrives, the message in the frame is delivered to the network layer and
an ACK is sent.

b. If a corrupted frame arrives, the frame is discarded.

Consider the following example1

The first frame is sent and acknowledged. The second frame is sent, but lost. After time-out, it
is resent. The third frame is sent and acknowledged, but the acknowledgment is lost. The frame
is resent. However, there is a problem with this scheme. The network layer at the receiver site
receives two copies of the third packet, which is not right.

Flow diagram for Example1

Sequence and Acknowledgment Numbers

To correct the duplicate packet problem of network layer at receiver side receiving duplicate
packet we need to add sequence numbers to the data frames and acknowledgment numbers to
the ACK frames. However, numbering in this case is very simple. Sequence numbers are 0, 1,
0, 1, 0, 1, . . . ; the acknowledgment numbers can also be 1, 0, 1, 0, 1, 0, … In other words, the

Dilip. S, Dept. of AIML Page 26 of 57 Vemana IT

BCS502 - COMPUTER NETWORKS Module 2 Notes

sequence numbers start with 0, the acknowledgment numbers start with 1. An acknowledgment
number always defines the sequence number of the next frame to receive.

Consider the example 2 where frames are sent with sequence numbers and acknowledgement
numbers.

Flow diagram for example 2.

Piggybacking

The simple protocol and stop-and-wait protocol are designed for unidirectional
communication, in which data is flowing only in one direction. However, to make the
communication more efficient, the data in one direction is piggybacked with the
acknowledgment in the other direction.

HDLC (High-level Data Link Control)

HDLC is a bit-oriented protocol for communication over point-to-point and multipoint links.
It implements the Stop-and-Wait protocol.

HDLC provides two common transfer modes that can be used in different configurations.

Dilip. S, Dept. of AIML Page 27 of 57 Vemana IT

BCS502 - COMPUTER NETWORKS Module 2 Notes

1. Normal Response Mode (NRM)

2. Asynchronous Balanced Mode (ABM).

In NRM the station configuration is unbalanced. We have one primary station and multiple
secondary stations. A primary station can send commands; a secondary station can only
respond. The NRM is used for both point-to-point and multipoint links.

In ABM, the configuration is balanced. The link is point-to-point, and each station can
function as a primary and a secondary.

Normal response mode

Asynchronous balanced mode

Framing

HDLC defines three types of frames:

Information frames (I-frames) – I-frames are used to carry both user data and control
information.

Supervisory frames (S-frames) - S-frames are used only to transport control information.

Unnumbered frames (U-frames) - U-frames are reserved for system management.

Each frame in HDLC may contain up to six fields, a beginning flag field, an address field,
a control field, an information field, a frame check sequence (FCS) field, and an ending
flag field.

Dilip. S, Dept. of AIML Page 28 of 57 Vemana IT

BCS502 - COMPUTER NETWORKS Module 2 Notes

HDLC frames

Flag field : This field contains synchronization pattern 01111110, which identifies both the
beginning and the end of a frame.

Address field : If a primary station created the frame, it contains a to address. If a secondary
station creates the frame, it contains a from address. The address field can be one byte or
several bytes long, depending on the needs of the network.

Control field : The control field is one or two bytes used for flow and error control.

Information field : The information field contains the user’s data from the network layer or
management information.

FCS field. The frame check sequence (FCS) is the HDLC error detection field. It can
contain either a 2- or 4-byte CRC.

Control field for I frames

I-Frames along with user data carries flow and error control information. The subfields in
the control field are used to define these functions. I-Frame has first bit of the control field
as 0. The next 3 bits define the sequence number of the frame N(S). We can define a
sequence number between 0 and 7. The last 3 bits, called N(R), correspond to the
acknowledgment number when piggybacking is used. The bit between N(S) and N(R) is
P/F bit. When this bit is set it can be either poll or final. It means poll when the frame is
sent by a primary station to a secondary (when the address field contains the address of the

Dilip. S, Dept. of AIML Page 29 of 57 Vemana IT

BCS502 - COMPUTER NETWORKS Module 2 Notes

receiver). It means final when the frame is sent by a secondary to a primary (when the
address field contains the address of the sender).

Control Field for S-Frames

Supervisory frames (S Frames) are used for flow and error control whenever piggybacking
is either impossible or inappropriate. S-Frames will have first 2 bits as 10. The last 3 bits,
called N(R), correspond to the acknowledgment number (ACK) or negative
acknowledgment number (NAK), depending on the type of S-frame. The 2 bits called code
are used to define the type of S-frame itself. With 2 bits, we can have four types of S-
frames. Depending on the value of 2 bits we have 4 different types of S frames.

Receive ready (RR) - If the value of the code subfield is 00, it is an RR S-frame. This kind
of frame acknowledges the receipt of a safe and sound frame or group of frames. In this
case, the value of the N(R) field defines the acknowledgment number.

Receive not ready (RNR) - If the value of the code subfield is 10, it is an RNR S frame. This
kind of frame is an RR frame with additional functions. It acknowledges the receipt of a
frame or group of frames, and it announces that the receiver is busy and cannot receive
more frames. It acts as a kind of congestion-control mechanism by asking the sender to
slow down. The value of N(R) is the acknowledgment number.

Reject (REJ) - If the value of the code subfield is 01, it is an REJ S-frame. This is a NAK
frame, It is a NAK that can be used in Go-Back-N ARQ to improve the efficiency of the
process by informing the sender, before the sender timer expires, that the last frame is lost
or damaged. The value of N(R) is the negative acknowledgment number.

Selective reject (SREJ) - If the value of the code subfield is 11, it is an SREJ S frame. This
is a NAK frame used in Selective Repeat ARQ. Note that the HDLC Protocol uses the term
selective reject instead of selective repeat. The value of N(R) is the negative
acknowledgment number.

Control Field for U-Frames

Dilip. S, Dept. of AIML Page 30 of 57 Vemana IT

BCS502 - COMPUTER NETWORKS Module 2 Notes

Unnumbered frames are used to exchange session management and control information
between connected devices. U-frame codes are divided into two sections: a 2-bit prefix
before the P/ F bit and a 3-bit suffix after the P/F bit. Together, these two segments (5 bits)
can be used to create up to 32 different types of U-frames.

Consider the following example Node A asks for a connection with a set asynchronous
balanced mode (SABM) frame; node B gives a positive response with an unnumbered
acknowledgment (UA) frame. After these two exchanges, data can be transferred between
the two nodes (not shown in the figure). After data transfer, node A sends a DISC
(disconnect) frame to release the connection; it is confirmed by node B responding with a
UA (unnumbered acknowledgment).

Dilip. S, Dept. of AIML Page 31 of 57 Vemana IT

BCS502 - COMPUTER NETWORKS Module 2 Notes

Example of connection and disconnection

Consider the example two exchanges using piggybacking. The first is the case where no
error has occurred; the second is the case where an error has occurred and some frames are
discarded.

POINT-TO-POINT PROTOCOL (PPP)

Internet users who need to connect their home computers to the server of an Internet service
provider use PPP.

Services Provided by PPP

PPP is designed to accept payloads from several network layers

Dilip. S, Dept. of AIML Page 32 of 57 Vemana IT

BCS502 - COMPUTER NETWORKS Module 2 Notes

Authentication is also provided in the protocol, but it is optional.

The new version of PPP, called Multilink PPP, provides connections over multiple links.

Services Not Provided by PPP

PPP does not provide flow control.

PPP has a very simple mechanism for error control. A CRC field is used to detect errors. If the
frame is corrupted, it is silently discarded; the upper-layer protocol needs to take care of the
problem. Lack of error control and sequence numbering may cause a packet to be received out
of order. PPP does not provide a sophisticated addressing mechanism to handle frames in a
multipoint configuration.

Framing

PPP frame format

Flag: A PPP frame starts and ends with a 1-byte flag with the bit pattern 01111110.

Address: The address field in this protocol is a constant value and set to 11111111 (broadcast
address).

Control: This field is set to the constant value 00000011 PPP does not provide any flow control.
Error control is also limited to error detection.

Protocol: The protocol field defines what is being carried in the data field: either user data or
other information. This field is by default 2 bytes long, but the two parties can agree to use only
1 byte.

Payload field: The data field is a sequence of bytes with the default of a maximum of 1500
bytes; but this can be changed during negotiation. The data field is byte-stuffed if the flag byte
pattern appears in this field. Because there is no field defining the size of the data field, padding
is needed if the size is less than the maximum default value or the maximum negotiated value.

FCS: The frame check sequence (FCS) is simply a 2-byte or 4-byte standard CRC.

Byte Stuffing

Dilip. S, Dept. of AIML Page 33 of 57 Vemana IT

BCS502 - COMPUTER NETWORKS Module 2 Notes

Since PPP is a byte-oriented protocol, the flag in PPP is a byte that needs to be escaped
whenever it appears in the data section of the frame. The escape byte is 01111101, which means
that every time the flaglike pattern appears in the data, this extra byte is stuffed to tell the
receiver that the next byte is not a flag. Obviously, the escape byte itself should be stuffed with
another escape byte.

Transition Phases

FSM, starts with the dead state. In this state there is no active carrier (at the physical layer) and
the line is quiet.

When one of the two nodes starts the communication, the connection goes into the establish
state.

If the two parties agree that they need authentication then the system needs to do authentication
otherwise, the parties can simply start communication. Data transfer takes place in the open
state.

The connection remains in this state until one of the endpoints wants to terminate the
connection. In this case, the system goes to the terminate state.

Transition phases

Multiplexing

Three sets of protocols are defined to make PPP powerful: the Link Control Protocol (LCP),
two Authentication Protocols (APs), and several Network Control Protocols (NCPs). At any
moment, a PPP packet can carry data from one of these protocols in its data field.

Dilip. S, Dept. of AIML Page 34 of 57 Vemana IT

BCS502 - COMPUTER NETWORKS Module 2 Notes

Multiplexing in PPP

Link Control Protocol

The Link Control Protocol (LCP) is responsible for establishing, maintaining, configuring, and
terminating links. It also provides negotiation mechanisms to set options between the two
endpoints. All LCP packets are carried in the payload field of the PPP frame with the protocol
field set to C021 in hexadecimal.

LCP packet encapsulated in a frame

The code field defines the type of LCP packet.

Dilip. S, Dept. of AIML Page 35 of 57 Vemana IT

BCS502 - COMPUTER NETWORKS Module 2 Notes

There are many options that can be negotiated between the two endpoints. Options are inserted
in the information field of the configuration packets. In this case, information field is divided
into three fields: option type, option length, and option data.

Authentication Protocols

Authentication means validating the identity of a user who needs to access a set of resources.
PPP has created two protocols for authentication: Password Authentication Protocol and
Challenge Handshake Authentication Protocol.

PAP

The Password Authentication Protocol (PAP) is a simple authentication procedure with a two-
step process:

a. The user who wants to access a system sends an authentication identification (usually the
user name) and a password.

b. The system checks the validity of the identification and password and either accepts or denies
connection.

Dilip. S, Dept. of AIML Page 36 of 57 Vemana IT

BCS502 - COMPUTER NETWORKS Module 2 Notes

PAP packets encapsulated in a PPP frame

When a PPP frame is carrying any PAP packets, the value of the protocol field is 0xC023. The
three PAP packets are authenticate-request, authenticate-ack, and authenticate-nak. The first
packet is used by the user to send the user name and pass word. The second is used by the
system to allow access. The third is used by the system to deny access.

CHAP

The Challenge Handshake Authentication Protocol (CHAP) is a three-way hand shaking

authentication protocol that provides greater security than PAP. In this method, the password is
kept secret; it is never sent online.

a. The system sends the user a challenge packet containing a challenge value, usually a
few bytes.
b. The user applies a predefined function that takes the challenge value and the user’s own
password and creates a result. The user sends the result in the response packet to the
system.
c. The system does the same. It applies the same function to the password of the user
(known to the system) and the challenge value to create a result. If the result created is
the same as the result sent in the response packet, access is granted; otherwise, it is
denied. CHAP is more secure than PAP, especially if the system continuously changes
the challenge value. Even if the intruder learns the challenge value and the result, the
password is still secret.

Dilip. S, Dept. of AIML Page 37 of 57 Vemana IT

BCS502 - COMPUTER NETWORKS Module 2 Notes

CHAP packets encapsulated in a PPP frame

CHAP packets are encapsulated in the PPP frame with the protocol value C223 in
hexadecimal. There are four CHAP packets: challenge, response, success, and failure.
The first packet is used by the system to send the challenge value. The second is used
by the user to return the result of the calculation. The third is used by the system to
allow access to the system. The fourth is used by the system to deny access to the
system.

Network Control Protocols

PPP is a multiple-network-layer protocol. It can carry a network-layer data packet from
protocols defined by the Internet, OSI, Xerox, DECnet, AppleTalk, Novel, and so on.
To do this, PPP has defined a specific Network Control Protocol for each network
protocol. IPCP (Internet Protocol Control Protocol) configures the link for carrying IP
data packets. Xerox CP does the same for the Xerox protocol data packets.
IPCP
One NCP protocol is the Internet Protocol Control Protocol (IPCP). This protocol
configures the link used to carry IP packets in the Internet.

Dilip. S, Dept. of AIML Page 38 of 57 Vemana IT

BCS502 - COMPUTER NETWORKS Module 2 Notes

IPCP packet encapsulated in PPP frame

Data from the Network Layer

If PPP is carrying data from the IP network layer, the field value is 0021.

IP datagram encapsulated in a PPP frame

Multilink PPP
In multilink PPP a logical PPP frame is divided into several actual PPP frames. A
segment of the logical frame is carried in the payload of an actual PPP frame.

Media Access Control (MAC)

Dilip. S, Dept. of AIML Page 39 of 57 Vemana IT

BCS502 - COMPUTER NETWORKS Module 2 Notes

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. Media Access Control
(MAC) is a sublayer in the data-link layer.

Taxonomy of multiple-access protocols

Random Access

In random-access or contention methods, no station is superior to another station and none is

assigned control over another. There is no scheduled time for a station to transmit. Transmission
is random among the stations. No rules specify which station should send next. Stations
compete with one another to access the medium.

ALOHA

ALOHA, the earliest random access method.

Pure ALOHA: Each station sends a frame whenever it has a frame to send (multiple access).
However, since there is only one channel to share, there is the possibility of collision between
frames from different stations.

Dilip. S, Dept. of AIML Page 40 of 57 Vemana IT

BCS502 - COMPUTER NETWORKS Module 2 Notes

Frames in a pure ALOHA network

There are four stations (unrealistic assumption) that contend with one another for access to the
shared channel. The figure shows that each station sends two frames; there are a total of eight
frames on the shared medium. Some of these frames collide because multiple frames are in
contention for the shared channel. Only two frames survive: one frame from station 1 and one
frame from station 3.

The pure ALOHA protocol relies on acknowledgments from the receiver. When a station sends
a frame, it expects the receiver to send an acknowledgment. If the acknowledgment does not
arrive after a time-out period, the station assumes that the frame (or the acknowledgment) has
been destroyed and resends the frame.

A collision involves two or more stations. If all these stations try to resend their frames after
the time-out, the frames will collide again. Pure ALOHA dictates that when the time-out period
passes, each station waits a random amount of time before resending its frame. The randomness
will help avoid more collisions. We call this time the backoff time TB.

Procedure for pure ALOHA protocol

Example:

The stations on a wireless ALOHA network are a maximum of 600 km apart. If we assume that
signals propagate at 3 × 108 m/s, we find Tp = (600 × 103) / (3 × 108) = 2 ms. For K = 2, the

Dilip. S, Dept. of AIML Page 41 of 57 Vemana IT

BCS502 - COMPUTER NETWORKS Module 2 Notes

range of R is {0, 1, 2, 3}. This means that TB can be 0, 2, 4, or 6 ms, based on the outcome of
the random variable R.

If each frame takes Tfr seconds to send.

Pure ALOHA vulnerable time = 2 x Tfr

Example:

A pure ALOHA network transmits 200-bit frames on a shared channel of 200 kbps. What is the
requirement to make this frame collision-free? Solution

Average frame transmission time Tfr is 200 bits/200 kbps or 1 ms. The vulnerable time is 2 × 1
ms = 2 ms. This means no station should send later than 1 ms before this station starts
transmission and no station should start sending during the period (1 ms) that this station is
sending.

Throughput

Let us call G the average number of frames generated by the system during one frame
transmission time. Then it can be proven that the average number of successfully trans mitted
frames for pure ALOHA is S = G × e−2G. The maximum throughput Smax is 0.184, for G = 1/2.

Example

A pure ALOHA network transmits 200-bit frames on a shared channel of 200 kbps. What is the
throughput if the system (all stations together) produces

a. 1000 frames per second?

b. 500 frames per second?

c. 250 frames per second?

The frame transmission time is 200/200 kbps or 1 ms.

a. If the system creates 1000 frames per second, or 1 frame per millisecond, then G = 1. In this
case S = G × e−2G = 0.135 (13.5 percent). This means that the throughput is 1000 × 0.135 =
135 frames. Only 135 frames out of 1000 will probably survive.

b. If the system creates 500 frames per second, or 1/2 frames per millisecond, then G = 1/2. In
this case S = G × e−2G = 0.184 (18.4 percent). This means that the throughput is 500 × 0.184

Dilip. S, Dept. of AIML Page 42 of 57 Vemana IT

BCS502 - COMPUTER NETWORKS Module 2 Notes

= 92 and that only 92 frames out of 500 will probably survive. Note that this is the maximum
throughput case, percentagewise.

c. If the system creates 250 frames per second, or 1/4 frames per millisecond, then G = 1/4. In
this case S = G × e−2G = 0.152 (15.2 percent). This means that the throughput is 250 × 0.152
= 38. Only 38 frames out of 250 will probably survive.

Slotted ALOHA

In slotted ALOHA we divide the time into slots of Tfr seconds and force the station to send only
at the beginning of the time slot.

Frames in a slotted ALOHA network

Because a station is allowed to send only at the beginning of the synchronized time slot, if a
station misses this moment, it must wait until the beginning of the next time slot. This means
that the station which started at the beginning of this slot has already finished sending its frame.
Of course, there is still the possibility of collision if two stations try to send at the beginning of
the same time slot. However, the vulnerable time is now reduced to one-half, equal to Tfr.

Vulnerable time for slotted ALOHA protocol

Dilip. S, Dept. of AIML Page 43 of 57 Vemana IT

BCS502 - COMPUTER NETWORKS Module 2 Notes

Throughput

The throughput for slotted ALOHA is S = G x e-G. The maximum throughput Smax = 0.368
when G = 1.

Example:

A slotted ALOHA network transmits 200-bit frames using a shared channel with a 200-kbps
bandwidth. Find the throughput if the system (all stations together) produces

a. 1000 frames per second.

b. 500 frames per second.

c. 250 frames per second.

Solution This situation is similar to the previous exercise except that the network is using
slotted ALOHA instead of pure ALOHA. The frame transmission time is 200/200 kbps or 1
ms.

a. In this case G is 1. So S = G × e−G = 0.368 (36.8 percent). This means that the throughput is
1000 × 0.0368 = 368 frames. Only 368 out of 1000 frames will probably survive. Note that this
is the maximum throughput case, percentagewise.

b. Here G is 1/2. In this case S = G × e−G = 0.303 (30.3 percent). This means that the throughput
is 500 × 0.0303 = 151. Only 151 frames out of 500 will probably survive.

c. Now G is 1/4. In this case S = G × e−G = 0.195 (19.5 percent). This means that the throughput
is 250 × 0.195 = 49. Only 49 frames out of 250 will probably survive.

CSMA

To minimize the chance of collision and, therefore, increase the performance, the CSMA
method was developed. Carrier sense multiple access (CSMA) requires that each station first
listen to the medium (or check the state of the medium) before sending. In other words, CSMA
is based on the principle “sense before transmit” or “listen before talk.”

Dilip. S, Dept. of AIML Page 44 of 57 Vemana IT

BCS502 - COMPUTER NETWORKS Module 2 Notes

Space/time model of a collision in CSMA

At time t1, station B senses the medium and finds it idle, so it sends a frame. At time t2 (t2 > t1),
station C senses the medium and finds it idle because, at this time, the first bits from station B
have not reached station C. Station C also sends a frame. The two signals collide and both
frames are destroyed.

The vulnerable time for CSMA is the propagation time Tp. This is the time needed for a signal
to propagate from one end of the medium to the other.

Persistence Methods

What the channel should do if the channel is idle or busy, there are three approaches 1-persistent
method, the nonpersistent method, and the p-persistent method.

1-Persistent

The 1-persistent method is simple and straightforward. In this method, after the station finds
the line idle, it sends its frame immediately (with probability 1). This method has the highest
chance of collision because two or more stations may find the line idle and send their frames
immediately.

Nonpersistent

In the nonpersistent method, a station that has a frame to send senses the line. If the line is idle,
it sends immediately. If the line is not idle, it waits a random amount of time and then senses
the line again. The nonpersistent approach reduces the chance of collision because it is unlikely
that two or more stations will wait the same amount of time and retry to send simultaneously.

Dilip. S, Dept. of AIML Page 45 of 57 Vemana IT

BCS502 - COMPUTER NETWORKS Module 2 Notes

However, this method reduces the efficiency of the network because the medium remains idle
when there may be stations with frames to send.

p-Persistent

The p-persistent method is used if the channel has time slots with a slot duration equal to or
greater than the maximum propagation time. The p-persistent approach combines the
advantages of the other two strategies. It reduces the chance of collision and improves
efficiency. In this method, after the station finds the line idle it follows these steps:

1. With probability p, the station sends its frame

[Link] probability q = 1 − p, the station waits for the beginning of the next time slot and
checks the line again.

a. If the line is idle, it goes to step 1.

b. If the line is busy, it acts as though a collision has occurred and uses the back off
procedure.

Behaviour of three persistence methods

Dilip. S, Dept. of AIML Page 46 of 57 Vemana IT

BCS502 - COMPUTER NETWORKS Module 2 Notes

Flow diagram for three persistence methods

CSMA/CD

Carrier sense multiple access with collision detection (CSMA/CD) augments the algorithm to
handle the collision. A station monitors the medium after it sends a frame to see if the
transmission was successful. If so, the station is finished. If, however, there is a collision, the
frame is sent again.

Dilip. S, Dept. of AIML Page 47 of 57 Vemana IT

BCS502 - COMPUTER NETWORKS Module 2 Notes

Collision of the first bits in CSMA/CD

At time t1, station A has executed its 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 the bits in its frame, which propagate both to the left and to the
right.

The collision occurs some time after time t2. Station C detects a collision at time t3 when it
receives the first bit of A’s frame. Station C immediately aborts transmission.

Station A detects collision at time t4 when it receives the first bit of C’s frame; it also
immediately aborts transmission.

Collision and abortion in CSMA/CD

Minimum Frame Size

For CSMA/CD to work, we need a restriction on the frame size. Before sending the last bit of
the frame, the sending station must detect a collision, if any, and abort the transmission. This
is so because the station, once the entire frame is sent, does not keep a copy of the frame and
does not monitor the line for collision detection. Therefore, the frame transmission time Tfr
must be at least two times the maximum propagation time Tp.

Example:

Dilip. S, Dept. of AIML Page 48 of 57 Vemana IT

BCS502 - COMPUTER NETWORKS Module 2 Notes

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?

The minimum 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.

Flow diagram for the CSMA/CD

In ALOHA, we first transmit the entire frame and then wait for an acknowledgment. In
CSMA/CD, transmission and collision detection are continuous processes. We do not send the
entire frame and then look for a collision. The station transmits and receives continuously and
simultaneously (using two different ports or a bidirectional port).

Energy Level

We can say that the level of energy in a channel can have three values: zero, normal, and
abnormal. At the 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. A station that has a frame to send or is sending
a frame needs to monitor the energy level to determine if the channel is idle, busy, or in collision
mode.

Dilip. S, Dept. of AIML Page 49 of 57 Vemana IT

BCS502 - COMPUTER NETWORKS Module 2 Notes

Energy level during transmission, idleness, or collision

Throughput

The throughput of CSMA/CD is greater than that of pure or slotted ALOHA. The maximum
throughput occurs at a different value of G and is based on the persistence method and the value
of p in the p-persistent approach. For the 1-persistent method, the maximum throughput is
around 50 percent when G = 1. For the nonpersistent method, the maximum throughput can go
up to 90 percent when G is between 3 and 8.

CSMA/CA

Carrier sense multiple access with collision avoidance (CSMA/CA) was invented for wireless
networks. Collisions are avoided through the use of CSMA/CA’s three strategies: the interframe
space, the contention window, and acknowledgments.

Dilip. S, Dept. of AIML Page 50 of 57 Vemana IT

BCS502 - COMPUTER NETWORKS Module 2 Notes

Flow diagram of CSMA/CA

Interframe Space (IFS):

Collisions are avoided by deferring transmission even if the channel is found idle. When an
idle channel is found, the station does not send immediately. It waits for a period of time called
the interframe space or IFS. Even though the channel may appear idle when it is sensed, a
distant station may have already started transmitting. The distant station’s signal has not yet
reached this station. The IFS time allows the front of the transmitted signal by the distant station
to reach this station. After waiting an IFS time, if the channel is still idle, the station can send,
but it still needs to wait a time equal to the contention window.

Contention Window:

Dilip. S, Dept. of AIML Page 51 of 57 Vemana IT

BCS502 - COMPUTER NETWORKS Module 2 Notes

The contention window is an amount of time divided into slots. A station that is ready to send
chooses a random number of slots as its wait time. The number of slots in the window changes
according to the binary exponential backoff strategy. This means that it is set to one slot the
first time and then doubles each time the station cannot detect an idle channel after the IFS
time.

Contention window

With all these precautions, there still may be a collision resulting in destroyed data. In addition,
the data may be corrupted during the transmission. The positive acknowledgment and the time-
out timer can help guarantee that the receiver has received the frame.

CSMA/CA and NAV

1. Before sending a frame, the source station senses the medium by checking the energy level
at the carrier frequency.

a. The channel uses a persistence strategy with backoff until the channel is idle.

Dilip. S, Dept. of AIML Page 52 of 57 Vemana IT

BCS502 - COMPUTER NETWORKS Module 2 Notes

b. After the station is found to be idle, the station waits for a period of time called the DCF
interframe space (DIFS); then the station sends a control frame called the request to send (RTS).

2. After receiving the RTS and waiting a period of time called the short interframe space (SIFS),
the destination station sends a control frame, called the clear to send (CTS), to the source
station. This control frame indicates that the destination station is ready to receive data.

3. The source station sends data after waiting an amount of time equal to SIFS.

4. The destination station, after waiting an amount of time equal to SIFS, sends an
acknowledgment to show that the frame has been received. Acknowledgment is needed in this
protocol because the station does not have any means to check for the successful arrival of its
data at the destination. On the other hand, the lack of collision in CSMA/CD is a kind of
indication to the source that data have arrived.

Network Allocation Vector

When a station sends an RTS frame, it includes the duration of time that it needs to occupy the
channel. The stations that are affected by this transmission create a timer called a network
allocation vector (NAV) that shows how much time must pass before these stations are allowed
to check the channel for idleness. Each time a station accesses the system and sends an RTS
frame, other stations start their NAV. In other words, each station, before sensing the physical
medium to see if it is idle, first checks its NAV to see if it has expired.

Collision During Handshaking

What happens if there is a collision during the time when RTS or CTS control frames are in
transition, often called the handshaking period? Two or more stations may try to send RTS
frames at the same time. These control frames may collide. However, because there is no
mechanism for collision detection, the sender assumes there has been a collision if it has not
received a CTS frame from the receiver. The backoff strategy is employed, and the sender tries
again.

Hidden-Station Problem

CSMA/CA and NAV figure shows that the RTS message from B reaches A, but not C. However,
because both B and C are within the range of A, the CTS message, which contains the duration
of data transmission from B to A, reaches C. Station C knows that some hidden station is using
the channel and refrains from transmitting until that duration is over.

Dilip. S, Dept. of AIML Page 53 of 57 Vemana IT

BCS502 - COMPUTER NETWORKS Module 2 Notes

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.

Reservation

In the reservation method, a station needs to make a reservation before sending data. Time is
divided into intervals. In each interval, a reservation frame precedes the data frames sent in that
interval.

If there are N stations in the system, there are exactly N reservation minislots in the reservation
frame. Each minislot belongs to a station. When a station needs to send a data frame, it makes
a reservation in its own minislot. The stations that have made reservations can send their data
frames after the reservation frame.

Reservation access method

Polling

Polling works with topologies in which one device is designated as a primary station and the
other devices are secondary stations. All data exchanges must be made through the primary
device even when the ultimate destination is a secondary device. The primary device controls
the link; the secondary devices follow its instructions. It is up to the primary device to
determine which device is allowed to use the channel at a given time. The primary device,
therefore, is always the initiator of a session This method uses poll and select functions to
prevent collisions. However, the drawback is if the primary station fails, the system goes down.

Dilip. S, Dept. of AIML Page 54 of 57 Vemana IT

BCS502 - COMPUTER NETWORKS Module 2 Notes

Select and poll functions in polling-access method

Select

The select function is used whenever the primary device has something to send. Remember
that the primary controls the link. If the primary is neither sending nor receiving data, it knows
the link is available. If it has something to send, the primary device sends it. What it does not
know, however, is whether the target device is pre pared to receive. So the primary must alert
the secondary to the upcoming transmission and wait for an acknowledgment of the
secondary’s ready status. Before sending data, the primary creates and transmits a select (SEL)
frame, one field of which includes the address of the intended secondary.

Poll

The poll function is used by the primary device to solicit transmissions from the secondary
devices. 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 (in the form of a data frame) if it does. If the response
is negative (a NAK frame), then the primary polls the next secondary in the same manner until
it finds one with data to send. When the response is positive (a data frame), the primary reads
the frame and returns an acknowledgment (ACK frame), verifying its receipt.

Token Passing

In the token-passing method, the stations in a network are organized in a logical ring. In other
words, for each station, there is a predecessor and a successor. The predecessor is the station
which is logically before the station in the ring; the successor is the station which is after the
station in the ring. The current station is the one that is accessing the channel now. The right to

Dilip. S, Dept. of AIML Page 55 of 57 Vemana IT

BCS502 - COMPUTER NETWORKS Module 2 Notes

this access has been passed from the predecessor to the current station. The right will be passed
to the successor when the current station has no more data to send.

In this method, a special packet called a token circulates through the ring. The possession of
the token gives the station the right to access the channel and send its data. When a station has
some data to send, it waits until it receives the token from its predecessor. It then holds the
token and sends its data. When the station has no more data to send, it releases the token,
passing it to the next logical station in the ring. The station cannot send data until it receives
the token again in the next round. In this process, when a station receives the token and has no
data to send, it just passes the data to the next station.

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. For example, if a station that is holding the token fails, the token will disappear
from the network. Another function of token management is to assign priorities to the stations
and to the types of data being transmitted. And finally, token management is needed to make
low-priority stations release the token to high-priority stations.

Logical Ring

Logical ring and physical topology in token-passing access method

In the physical ring topology, when a station sends the token to its successor, the token cannot
be seen by other stations; the successor is the next one in line. This means that the token does

Dilip. S, Dept. of AIML Page 56 of 57 Vemana IT

BCS502 - COMPUTER NETWORKS Module 2 Notes

not have to have the address of the next successor. The problem with this topology is that if
one of the links—the medium between two adjacent stations—fails, the whole system fails.

The dual ring topology uses a second (auxiliary) ring which operates in the reverse direction
compared with the main ring. The second ring is for emergencies only (such as a spare tire for
a car). If one of the links in the main ring fails, the system automatically combines the two
rings to form a temporary ring. After the failed link is restored, the auxiliary ring becomes idle
again. Note that for this topology to work, each station needs to have two transmitter ports and
two receiver ports. The high-speed Token Ring networks called FDDI (Fiber Distributed Data
Interface) and CDDI (Copper Distributed Data Interface) use this topology.

In the bus ring topology, also called a token bus, the stations are connected to a single cable
called a bus. They, however, make a logical ring, because each station knows the address of its
successor (and also predecessor for token management purposes). When a station has finished
sending its data, it releases the token and inserts the address of its successor in the token. Only
the station with the address matching the destination address of the token gets the token to
access the shared media. The Token Bus LAN, standardized by IEEE, uses this topology.

In a star ring topology, the physical topology is a star. There is a hub, however, that acts as the
connector. The wiring inside the hub makes the ring; the stations are connected to this ring
through the two wire connections. This topology makes the network less prone to failure
because if a link goes down, it will be bypassed by the hub and the rest of the stations can
operate. Also adding and removing stations from the ring is easier. This topology is still used
in the Token Ring LAN designed by IBM.

Dilip. S, Dept. of AIML Page 57 of 57 Vemana IT