UNIT – III

THE DATA LINK LAYER

Contents:

THE DATA LINK LAYER

 Data Link Layer Design Issues, Error Detection and Correction,

Elementary Data Link Protocols , Improving Efficiency.

THE MEDIUM ACCESS CONTROL SUB LAYER

 The Channel Allocation Problem, Multiple Access Protocols

Data Link Layer Functions (Services) and Design Issues:

The data link layer uses the services of the physical layer to send and
receive bits over communication channels. It has a number of functions,
including:

1. Providing a well-defined service interface to the network layer.

2. Dealing with transmission errors.

3. Regulating the flow of data so that slow receivers are not swamped by
fast senders.

1. Providing services to the network layer:

1 Unacknowledged connectionless service: Appropriate for low error rate

and real-time traffic. Ex: Ethernet

2. Acknowledged connectionless service: Useful in unreliable

channels, WiFi. Ack/Timer/Resend

3. Acknowledged connection-oriented service: Guarantee frames are

received exactly once and in the right order. Appropriate over long,
unreliable links such as a satellite channel or a long distance telephone
circuit.

2. Framing: Frames are the streams of bits received from the network
layer into manageable data units. This division of stream of bits is done
by Data Link Layer.

3. Physical Addressing: The Data Link layer adds a header to the frame
in order to define physical address of the sender or receiver of the frame,
if the frames are to be distributed to different systems on the network.

4. Flow Control: A receiving node can receive the frames at a faster rate
than it can process the frame. Without flow control, the receiver's buffer
can overflow, and frames can get lost. To overcome this problem, the
data link layer uses the flow control to prevent the sending node on one
side of the link from overwhelming the receiving node on another side of
the link. This prevents traffic jam at the receiver side.

5. Error Control: Error control is achieved by adding a trailer at the end

of the frame. Duplication of frames are also prevented by using this
mechanism. Data Link Layers adds mechanism to prevent duplication of
frames.

[Link] detection: Errors can be introduced by signal attenuation and

noise. Data Link Layer protocol provides a mechanism to detect one or
more errors. This is achieved by adding error detection bits in the frame
and then receiving node can perform an error check.

Error correction: Error correction is similar to the Error detection,

except that receiving node not only detects the errors but also determine
where the errors have occurred in the frame.

6. Access Control: Protocols of this layer determine which of the devices

has control over the link at any given time, when two or more devices are
connected to the same link.

7. Reliable delivery: Data Link Layer provides a reliable delivery service,

i.e., transmits the network layer datagram without any error. A reliable
delivery service is accomplished with transmissions and
acknowledgements. A data link layer mainly provides the reliable delivery
service over the links as they have higher error rates and they can be
corrected locally, link at which an error occurs rather than forcing to
retransmit the data.

8. Half-Duplex & Full-Duplex: In a Full-Duplex mode, both the nodes

can transmit the data at the same time. In a Half-Duplex mode, only one
node can transmit the data at the same time.

FRAMING:

To provide service to the network layer, the data link layer must use the
service provided to it by the physical layer. What the physical layer does
is accept a raw bit stream and attempt to deliver it to the destination.
This bit stream is not guaranteed to be error free. The number of bits
received may be less than, equal to, or more than the number of bits
transmitted, and they may have different values. It is up to the data link
layer to detect and, if necessary, correct errors. The usual approach is for
the data link layer to break the bit stream up into discrete frames and
compute the checksum for each frame (framing). When a frame arrives at
the destination, the checksum is recomputed. If the newly computed
checksum is different from the one contained in the frame, the data link
layer knows that an error has occurred and takes steps to deal with it
(e.g., discarding the bad frame and possibly also sending back an error
report).
We will look at four framing methods:

1. Character count.

2. Flag bytes with byte stuffing.

3. Starting and ending flags, with bit stuffing.

4. Physical layer coding violations.

[Link] count method uses a field in the header to specify the

number of characters in the frame. When the data link layer at the
destination sees the character count, it knows how many characters
follow and hence where the end of the frame is. This technique is shown
in Fig. (a) For four frames of sizes 5, 5, 8, and 8 characters, respectively.

The trouble with this algorithm is that the count can be garbled by a
transmission error. For example, if the character count of 5 in the second
frame of Fig. (b) becomes a 7, the destination will get out of
synchronization and will be unable to locate the start of the next frame.
Even if the checksum is incorrect so the destination knows that the frame
is bad, it still has no way of telling where the next frame starts. Sending a
frame back to the source asking for a retransmission does not help either,
since the destination does not know how many characters to skip over to
get to the start of the retransmission. For this reason, the character count
method is rarely used anymore.

[Link] bytes with byte stuffing method gets around the problem of
resynchronization after an error by having each frame start and end with
special bytes. In the past, the starting and ending bytes were different,
but in recent years most protocols have used the same byte, called a flag
byte, as both the starting and ending delimiter, as shown in Fig. (a) as
FLAG. In this way, if the receiver ever loses synchronization, it can just
search for the flag byte to find the end of the current frame. Two
consecutive flag bytes indicate the end of one frame and start of the next
one.

It may easily happen that the flag byte's bit pattern occurs in the data.
This situation will usually interfere with the framing. One way to solve this
problem is to have the sender's data link layer insert a special escape
byte (ESC) just before each ''accidental'' flag byte in the data. The data
link layer on the receiving end removes the escape byte before the data
are given to the network layer. This technique is called byte stuffing or
character stuffing.

Thus, a framing flag byte can be distinguished from one in the data by the
absence or presence of an escape byte before it. What happens if an
escape byte occurs in the middle of the data? The answer is that, it too is
stuffed with an escape byte. Thus, any single escape byte is part of an
escape sequence, whereas a doubled one indicates that a single escape
occurred naturally in the data. Some examples are shown in Fig. (b). In
all cases, the byte sequence delivered after de stuffing is exactly the
same as the original byte sequence. A major disadvantage of using this
framing method is that it is closely tied to the use of 8-bit characters. Not
all character codes use 8-bit characters. For example UNICODE uses 16-
bit characters, so a new technique had to be developed to allow arbitrary
sized characters.

[Link] and ending flags, with bit stuffing allows data frames to
contain an arbitrary number of bits and allows character codes with an
arbitrary number of bits per character. It works like this. Each frame
begins and ends with a special bit pattern, 01111110 (in fact, a flag
byte). Whenever the sender's data link layer encounters five consecutive
1s in the data, it automatically stuffs a 0 bit into the outgoing bit stream.
This bit stuffing is analogous to byte stuffing, in which an escape byte is
stuffed into the outgoing character stream before a flag byte in the data.
When the receiver sees five consecutive incoming 1 bits, followed by a 0
bit, it automatically de- stuffs (i.e., deletes) the 0 bit. Just as byte stuffing
is completely transparent to the network layer in both computers, so is bit
stuffing. If the user data contain the flag pattern, 01111110, this flag is
transmitted as 011111010 but stored in the receiver's memory as
01111110.

With bit stuffing, the boundary between two frames can be

unambiguously recognized by the flag pattern. Thus, if the receiver loses
track of where it is, all it has to do is scan the input for flag sequences,
since they can only occur at frame boundaries and never within the data.

[Link] layer coding violations method of framing is only applicable

to networks in which the encoding on the physical medium contains some
redundancy. For example, some LANs encode 1 bit of data by using 2
physical bits. Normally, a 1 bit is a high-low pair and a 0 bit is a low-high
pair. The scheme means that every data bit has a transition in the middle,
making it easy for the receiver to locate the bit boundaries. The
combinations high-high and low-low are not used for data but are used
for delimiting frames in some protocols.

As a final note on framing, many data link protocols use combination of a

character count with one of the other methods for extra safety. When a
frame arrives, the count field is used to locate the end of the frame. Only
if the appropriate delimiter is present at that position and the checksum is
correct is the frame accepted as valid. Otherwise, the input stream is
scanned for the next delimiter.

Error Detection and Correction

Error is a condition when the receiver‟s information does not match the
sender‟s. Digital signals suffer from noise during transmission that can
introduce errors in the binary bits traveling from sender to receiver. That
means a 0 bit may change to 1 or a 1 bit may change to 0.

Data (Implemented either at the Data link layer or Transport Layer of the
OSI Model) may get scrambled by noise or get corrupted whenever a
message is transmitted. To prevent such errors, error-detection codes are
added as extra data to digital messages. This helps in detecting any
errors that may have occurred during message transmission.
Error Detection Methods
To detect errors, a common technique is to introduce redundancy bits
that provide additional information. Various techniques for error detection
include:
 Simple Parity Check
 Checksum
 Cyclic Redundancy Check (CRC)

Simple Parity Check

Simple-bit parity is a simple error detection method that involves adding
an extra bit to a data transmission. It works as:
 1 is added to the block if it contains an odd number of 1‟s, and
 0 is added if it contains an even number of 1‟s
This scheme makes the total number of 1‟s even, that is why it is
called even parity checking.

Advantages of Simple Parity Check

 Simple parity check can detect all single bit error.
 Simple parity check can detect an odd number of errors.
 Implementation: Simple Parity Check is easy to implement in both
hardware and software.
 Minimal Extra Data: Only one additional bit (the parity bit) is added
per data unit (e.g., per byte).
 Fast Error Detection: The process of calculating and checking the
parity bit is quick, which allows for rapid error detection without
significant delay in data processing or communication.
 Single-Bit Error Detection: It can effectively detect single-bit errors
within a data unit, providing a basic level of error detection for
relatively low-error environments.

Checksum
Checksum error detection is a method used to identify errors in
transmitted data. The process involves dividing the data into equally sized
segments and using a 1‟s complement to calculate the sum of these
segments. The calculated sum is then sent along with the data to the
receiver. At the receiver‟s end, the same process is repeated and if all
zeroes are obtained in the sum, it means that the data is correct.

Checksum – Operation at Sender’s Side

 Firstly, the data is divided into k segments each of m bits.
 On the sender‟s end, the segments are added using 1‟s complement
arithmetic to get the sum. The sum is complemented to get the
checksum.
 The checksum segment is sent along with the data segments.

Checksum – Operation at Receiver’s Side

 At the receiver‟s end, all received segments are added using 1‟s
complement arithmetic to get the sum. The sum is complemented.
 If the result is zero, the received data is accepted; otherwise
discarded.

Cyclic Redundancy Check (CRC)

 Unlike the checksum scheme, which is based on addition, CRC is based
on binary division.
 In CRC, a sequence of redundant bits, called cyclic redundancy check
bits, are appended to the end of the data unit so that the resulting
data unit becomes exactly divisible by a second, predetermined binary
number.
 At the destination, the incoming data unit is divided by the same
number. If at this step there is no remainder, the data unit is assumed
to be correct and is therefore accepted.
 A remainder indicates that the data unit has been damaged in transit
and therefore must be rejected.
We have given data word of length n and divisor of length k.
Step 1: Append (k-1) zero‟s to the original message
Step 2: Perform modulo 2 division
Step 3: Remainder of division = CRC
Step 4: Code word = Data with append k-1 zero‟s + CRC
Note:
 CRC must be k-1 bits
 Length of Code word = n+k-1 bits

Example: Let‟s data to be send is 1010000 and divisor in the form of

polynomial is x3+1. CRC method discussed below.

GATE-CS-2007: Home work problem

The message 11001001 is to be transmitted using the CRC polynomial
x^3 + 1 to protect it from errors. The message that should be
transmitted is:

a) 11001001000 b) 11001001011
c) 11001010 d) 110010010011
Error Correction codes
Once the errors are detected in the network, the deviated bits sequence
needs to be replaced with the right bit sequence so that the receiver can
accept the data and process it. This method is called Error Correction.

• We will examine four different error-correcting codes:

1. Hamming codes.

2. Binary convolutional codes.

3. Reed-Solomon codes.

4. Low-Density Parity Check codes

Hamming Code Error Correction

Hamming code is an error-correcting code used to ensure data accuracy
during transmission or storage. Hamming code detects and corrects the
errors that can occur when the data is moved or stored from the sender
to the receiver. This simple and effective method helps improve the
reliability of communication systems and digital storage. It adds extra bits
to the original data, allowing the system to detect and correct single-bit
errors. It is a technique developed by Richard Hamming in the 1950s.

In this method, extra parity bits are appended to the message which are
used by the receiver to correct the single bit error and multiple bit error.
Consider the below example to understand this method in a better way.
Suppose the sender wants to transmit the message whose bit
representation is „1011001.‟ In this message:
 Total number of bits(d) = 7
 Total of redundant bits(r) = 4 (This is because the message has four
1‟s in it)
 Thus, total bits(d+r) = 7 + 4 = 11

What is Redundant Bits?

Redundant bits are extra binary bits that are generated and added to the
information-carrying bits of data transfer to ensure that no bits were lost
during the data transfer. The number of redundant bits can be calculated
using the following formula:
2r ≥ m + r + 1
where m is the number of bits in input data, and r is the number of
redundant bits.
Suppose the number of data bits is 7, then the number of redundant bits
can be calculated using: = 24 ≥ 7 + 4 + 1 . Thus, the number of
redundant bits is 4.

Types of Parity Bits

A parity bit is a bit appended to a data of binary bits to ensure that the
total number of 1‟s in the data is even or odd. Parity bits are used for
error detection. There are two types of parity bits:
 Even Parity Bit: In the case of even parity, for a given set of bits, the
number of 1‟s are counted. If that count is odd, the parity bit value is
set to 1, making the total count of occurrences of 1‟s an even number.
If the total number of 1‟s in a given set of bits is already even, the
parity bit‟s value is 0.
 Odd Parity Bit: In the case of odd parity, for a given set of bits, the
number of 1‟s are counted. If that count is even, the parity bit value is
set to 1, making the total count of occurrences of 1‟s an odd number.
If the total number of 1‟s in a given set of bits is already odd, the
parity bit‟s value is 0.

Algorithm of Hamming Code

Hamming Code is simply the use of extra parity bits to allow the
identification of an error.
Step 1: Write the bit positions starting from 1 in binary form (1, 10, 11,
100, etc).
Step 2: All the bit positions that are a power of 2 are marked as parity
bits (1, 2, 4, 8, etc).
Step 3: All the other bit positions are marked as data bits.
Step 4: Each data bit is included in a unique set of parity bits, as
determined its bit position in binary form:
 a. Parity bit 1 covers all the bits positions whose binary representation
includes a 1 in the least significant position (1, 3, 5, 7, 9, 11, etc).
 b. Parity bit 2 covers all the bits positions whose binary representation
includes a 1 in the second position from the least significant bit (2, 3,
6, 7, 10, 11, etc).
 c. Parity bit 4 covers all the bits positions whose binary representation
includes a 1 in the third position from the least significant bit (4–7, 12–
15, 20–23, etc).
 d. Parity bit 8 covers all the bits positions whose binary representation
includes a 1 in the fourth position from the least significant bit bits (8–
15, 24–31, 40–47, etc).
 e. In general, each parity bit covers all bits where the bitwise AND of
the parity position and the bit position is non-zero.
Step 5: Since we check for even parity set a parity bit to 1 if the total
number of ones in the positions it checks is odd. Set a parity bit to 0 if the
total number of ones in the positions it checks is even.
Determining The Position of Redundant Bits
A redundancy bits are placed at positions that correspond to the power of
2. As in the above example:
 The number of data bits = 7
 The number of redundant bits = 4
 The total number of bits = 7+4=>11
 The redundant bits are placed at positions corresponding to power of 2
that is 1, 2, 4, and 8

 Suppose the data to be transmitted is 1011001 from sender to

receiver, the bits will be placed as follows:
Determining The Parity Bits According to Even Parity
 R1 bit is calculated using parity check at all the bits positions whose
binary representation includes a 1 in the least significant position. R1:
bits 1, 3, 5, 7, 9, 11

 To find the redundant bit R1, we check for even parity. Since the total
number of 1‟s in all the bit positions corresponding to R1 is an even
number. So, the value of R1 (parity bit‟s value) = 0.
 R2 bit is calculated using parity check at all the bits positions whose
binary representation includes a 1 in the second position from the
least significant bit. R2: bits 2,3,6,7,10,11

 To find the redundant bit R2, we check for even parity. Since the total
number of 1‟s in all the bit positions corresponding to R2 is odd the
value of R2(parity bit‟s value)=1
 R4 bit is calculated using parity check at all the bits positions whose
binary representation includes a 1 in the third position from the least
significant bit. R4: bits 4, 5, 6, 7
 To find the redundant bit R4, we check for even parity. Since the total
number of 1‟s in all the bit positions corresponding to R4 is odd so the
value of R4(parity bit‟s value) = 1
 R8 bit is calculated using parity check at all the bits positions whose
binary representation includes a 1 in the fourth position from the
least significant bit. R8: bit 8,9,10,11

 To find the redundant bit R8, we check for even parity. Since the total
number of 1‟s in all the bit positions corresponding to R8 is an even
number the value of R8(parity bit‟s value)=0. Thus, the data
transferred is:

Error Detection and Correction

Suppose in the above example the 6th bit is changed from 0 to 1 during
data transmission, then it gives new parity values in the binary number:
For all the parity bits we will check the number of 1‟s in their respective
bit positions.
 For R1: bits 1, 3, 5, 7, 9, 11. We can see that the number of 1‟s in
these bit positions are 4 and that‟s even so we get a 0 for this.
 For R2: bits 2,3,6,7,10,11 . We can see that the number of 1‟s in
these bit positions are 5 and that‟s odd so we get a 1 for this.
 For R4: bits 4, 5, 6, 7 . We can see that the number of 1‟s in these bit
positions are 3 and that‟s odd so we get a 1 for this.
 For R8: bit 8,9,10,11 . We can see that the number of 1‟s in these bit
positions are 2 and that‟s even so we get a 0 for this.
 The bits give the binary number 0110 whose decimal representation
is 6. Thus, bit 6 contains an error. To correct the error the 6th bit is
changed from 1 to 0.

Features of Hamming Code

 Error Detection and Correction: Hamming code is designed to
detect and correct single-bit errors that may occur during the
transmission of data. This ensures that the recipient receives the same
data that was transmitted by the sender.
 Redundancy: Hamming code uses redundant bits to add additional
information to the data being transmitted. This redundancy allows the
recipient to detect and correct errors that may have occurred during
transmission.
 Efficiency: Hamming code is a relatively simple and efficient error-
correction technique that does not require a lot of computational
resources. This makes it ideal for use in low-power and low-bandwidth
communication networks.
 Widely Used: Hamming code is a widely used error-correction
technique and is used in a variety of applications, including
telecommunications, computer networks, and data storage systems.
 Single Error Correction: Hamming code is capable of correcting a
single-bit error, which makes it ideal for use in applications where
errors are likely to occur due to external factors such as
electromagnetic interference.
 Limited Multiple Error Correction: Hamming code can only correct a
limited number of multiple errors. In applications where multiple errors
are likely to occur, more advanced error-correction techniques may be
required.

• To determine how many bits differ, just XOR the two codewords and
count the number of 1 bits in the result.

• For example: The number of bit positions in which two codewords

differ is called the Hamming distance. In this case, 3 bits differ.

• To reliably detect „d‟ errors, you need a distance d + 1 code.

• Similarly, to correct „d‟ errors, you need a distance 2d + 1 code.

Binary Convolutional Codes

 In convolutional codes, the message comprises of data streams of

arbitrary length and a sequence of output bits are generated by the
sliding application of Boolean functions to the data stream.
 There is no natural message size or encoding boundary as in a block
code. The output depends on the current and previous input bits.
That is, the encoder has memory.

Reed-Solomon code

 Basically, Reed-Solomon codes help in recovering corrupted

messages that are being transferred over a network. In Reed-
Solomon codes, we have:
 Encoder
 Decoder
 Reed-Solomon codes encoder receives data and before transferring
it over the noisy network it adds some parity bits with our original
data bits.
 On the other hand, we have a Reed-Solomon codes decoder that
detects corrupted messages and recovers them from error.
LDPC (Low-Density Parity Check) code

 Low - density parity check (LDPC) code is a linear error-correcting

block code, suitable for error correction in large block sizes
transmitted via very noisy channels.
 A low - density parity check (LFPC) code is specified by a parity-
check matrix containing mostly 0s and a low density of 1s.
 The rows of the matrix represent the equations and the columns
represent the bits in the code word, i.e. code symbols.

Elementary Data Link Protocols

Simplest Protocol

It is very simple. The sender sends a sequence of frames without even

thinking about the receiver. Data are transmitted in one direction only.
Both sender & receiver always ready. Processing time can be ignored.
Infinite buffer space is available. And best of all, the communication
channel between the data link layers never damages or loses frames. This
thoroughly unrealistic protocol, which we will nickname „„Utopia,‟‟ .The
utopia protocol is unrealistic because it does not handle either flow control
or error correction.
Stop-and-wait Protocol

It is still very simple. The sender sends one frame and waits for feedback
from the receiver. When the ACK arrives, the sender sends the next
frame It is Stop-and-Wait Protocol because the sender sends one frame,
stops until it receives confirmation from the receiver (okay to go ahead),
and then sends the next frame. We still have unidirectional
communication for data frames, but auxiliary ACK frames (simple tokens
of acknowledgment) travel from the other direction. We add flow control
to our previous protocol.

NOISY CHANNELS

Although the Stop-and-Wait Protocol gives us an idea of how to add flow

control to its predecessor, noiseless channels are non-existent. We can
ignore the error (as we sometimes do), or we need to add error control to
our protocols. We discuss three protocols in this section that use error
control.

Sliding Window Protocols: Automatic Repeat Request (ARQ)

1. Stop-and-Wait

2. Go-Back-N

3. Selective Repeat

1. Stop-and-Wait:

To detect and correct corrupted frames, we need to add redundancy

bits to our data frame. When the frame arrives at the receiver site, it is
checked and if it is corrupted, it is silently discarded. The detection of
errors in this protocol is manifested by the silence of the receiver.

Lost frames are more difficult to handle than corrupted ones. In our
previous protocols, there was no way to identify a frame. The received
frame could be the correct one, or a duplicate, or a frame out of order.
The solution is to number the frames. When the receiver receives a
 data frame that is out of order, this means that frames were either lost
or duplicated.

The lost frames need to be resent in this protocol. If the receiver does
not respond when there is an error, how can the sender know which
frame to resend? To remedy this problem, the sender keeps a copy of
the sent frame. At the same time, it starts a timer. If the timer expires
and there is no ACK for the sent frame, the frame is resent, the copy is
held, and the timer is restarted. Since the protocol uses the stop-and-
wait mechanism, there is only one specific frame that needs an ACK.

Error correction in Stop-and-Wait ARQ is done by keeping a copy of the

sent frame and retransmitting of the frame when the timer expires.

In Stop-and-Wait ARQ, we use sequence numbers to number the

frames. The sequence numbers are based on modulo-2 arithmetic. In
Stop-and-Wait ARQ, the acknowledgment number always announces in
modulo-2 arithmetic the sequence number of the next frame expected.

Bandwidth-delay product (BDP) is the product of a data link's

bandwidth and its round-trip delay time. It is a calculation that
determines the maximum amount of data that can be in transit in a
network at any given time.
 2. Go-Back-N

To improve the efficiency of transmission (filling the pipe), multiple

frames must be in transition while waiting for acknowledgment. In other
words, we need to let more than one frame be outstanding to keep the
channel busy while the sender is waiting for acknowledgment.

The first is called Go-Back-N Automatic Repeat. In this protocol we can

send several frames before receiving acknowledgments; we keep a copy
of these frames until the acknowledgments arrive. In the Go-Back-N
Protocol, the sequence numbers are modulo 2m, where m is the size of
the sequence number field in bits. The sequence numbers range from 0 to
2 power m- 1. For example, if m is 4, the only sequence numbers are 0
through 15 inclusive.

The sender window at any time divides the possible sequence numbers
into four regions. The first region, from the far left to the left wall of the
window, defines the sequence numbers belonging to frames that are
already acknowledged. The sender does not worry about these frames
and keeps no copies of them. The second region, colored in Figure (a),
defines the range of sequence numbers belonging to the frames that are
sent and have an unknown status. The sender needs to wait to find out if
these frames have been received or were lost. We call these outstanding
frames. The third range, white in the figure, defines the range of
sequence numbers for frames that can be sent; however, the
corresponding data packets have not yet been received from the network
layer. Finally, the fourth region defines sequence numbers that cannot be
used until the window slides.

The send window is an abstract concept defining an imaginary box of size

2m − 1 with three variables: Sf, Sn, and Ssize. The variable Sf defines
the sequence number of the first (oldest) outstanding frame. The variable
Sn holds the sequence number that will be assigned to the next frame to
be sent. Finally, the variable Ssize defines the size of the window. Figure
(b) shows how a send window can slide one or more slots to the right
when an acknowledgment arrives from the other end. The
acknowledgments in this protocol are cumulative, meaning that more
than one frame can be acknowledged by an ACK frame. In Figure, frames
0, I, and 2 are acknowledged, so the window has slide to the right three
slots. Note that the value of Sf is 3 because frame 3 is now the first
outstanding frame. The send window can slide one or more slots when a
valid acknowledgment arrives.

Receiver window: variable Rn (receive window, next frame expected) .

The sequence numbers to the left of the window belong to the frames
already received and acknowledged; the sequence numbers to the right of
this window define the frames that cannot be received. Any received
frame with a sequence number in these two regions is discarded. Only a
frame with a sequence number matching the value of Rn is accepted and
acknowledged. The receive window also slides, but only one slot at a
time. When a correct frame is received (and a frame is received only one
at a time), the window slides.( see below figure for receiving window).

Timers Although there can be a timer for each frame that is sent, in our
protocol we use only one. The reason is that the timer for the first
outstanding frame always expires first; we send all outstanding frames
when this timer expires.

Acknowledgment The receiver sends a positive acknowledgment if a

frame has arrived safe and sound and in order. If a frame is damaged or
is received out of order, the receiver is silent and will discard all
subsequent frames until it receives the one it is expecting. The silence of
the receiver causes the timer of the unacknowledged frame at the sender
side to expire. This, in turn, causes the sender to go back and resend all
frames, beginning with the one with the expired timer. The receiver does
not have to acknowledge each frame received. It can send one cumulative
acknowledgment for several frames.

Resending a Frame When the timer expires, the sender resends all
outstanding frames. For example, suppose the sender has already sent
frame 6, but the timer for frame 3 expires. This means that frame 3 has
not been acknowledged; the sender goes back and sends frames 3,4,5,
and 6 again. That is why the protocol is called Go-Back-N ARQ.

Below figure is an example(if ack lost) of a case where the forward

channel is reliable, but the reverse is not. No data frames are lost, but
some ACKs are delayed and one is lost. The example also shows how
cumulative acknowledgments can help if acknowledgments are delayed or
lost.
Why always less than 2^m??
3. Selective Repeat

In Go-Back-N ARQ, The receiver keeps track of only one variable, and
there is no need to buffer out-of- order frames; they are simply
discarded. However, this protocol is very inefficient for a noisy link. In a
noisy link a frame has a higher probability of damage, which means the
resending of multiple frames. This resending uses up the bandwidth and
slows down the transmission. For noisy links, there is another mechanism
that does not resend N frames when just one frame is damaged; only the
damaged frame is resent. This mechanism is called Selective Repeat ARQ.
It is more efficient for noisy links, but the processing at the receiver is
more complex.

Sender Window (explain go-back N sender window concept (before &

after sliding.) The only difference in sender window between Go-back N
and Selective Repeat is Window size)

Receiver window The receiver window in Selective Repeat is totally

different from the one in Go Back-N. First, the size of the receive window
is the same as the size of the send window (2m-1). The Selective Repeat
Protocol allows as many frames as the size of the receiver window to
arrive out of order and be kept until there is a set of inorder frames to be
delivered to the network layer. Because the sizes of the send window and
receive window are the same, all the frames in the send frame can arrive
out of order and be stored until they can be delivered. However the
receiver never delivers packets out of order to the network layer. Above
Figure shows the receive window. Those slots inside the window that are
colored define frames that have arrived out of order and are waiting for
their neighbors to arrive before delivery to the network layer. In Selective
Repeat ARQ, the size of the sender and receiver window must be at most
one-half of 2m
Differences between Go-Back N & Selective Repeat
One main difference is the number of timers. Here, each frame sent
or resent needs a timer, which means that the timers need to be
numbered (0, 1,2, and 3). The timer for frame 0 starts at the first
request, but stops when the ACK for this frame arrives.

There are two conditions for the delivery of frames to the network
layer: First, a set of consecutive frames must have arrived. Second,
the set starts from the beginning of the window. After the first
arrival, there was only one frame and it started from the beginning
of the window. After the last arrival, there are three frames and the
first one starts from the beginning of the window.

Another important point is that a NAK is sent. The next point is

about the ACKs. Notice that only two ACKs are sent here. The first
one acknowledges only the first frame; the second one
acknowledges three frames. In Selective Repeat, ACKs are sent
when data are delivered to the network layer. If the data belonging
to n frames are delivered in one shot, only one ACK is sent for all of
them.

Piggybacking
A technique called piggybacking is used to improve the efficiency of
the bidirectional protocols. When a frame is carrying data from A to
B, it can also carry control information about arrived (or lost)
frames from B; when a frame is carrying data from B to A, it can
also carry control information about the arrived (or lost) frames
from A.
THE MEDIUM ACCESS CONTROL SUB LAYER

The Channel Allocation Problem:

Channel allocation is a process in which a single channel is divided and

allotted to multiple users in order to carry user specific tasks. There are
user‟s quantity may vary every time the process takes place. If there are
N number of users and channel is divided into N equal-sized sub channels,
Each user is assigned one portion. If the number of users are small and
don‟t vary at times, then Frequency Division Multiplexing can be used as
it is a simple and efficient channel bandwidth allocating technique.
Channel allocation problem can be solved by two schemes: Static Channel
Allocation in LANs and MANs, and Dynamic Channel Allocation.

1. Static Channel Allocation:

It is the classical or traditional approach of allocating a single channel

among multiple competing users using Frequency Division Multiplexing
(FDM). if there are N users, the frequency channel is divided into N equal
sized portions (bandwidth), each user being assigned one portion. since
each user has a private frequency band, there is no interference between
users.

However, it is not suitable in case of a large number of users with variable

bandwidth requirements.
It is not efficient to divide into fixed number of chunks.

2. Dynamic Channel Allocation:

In dynamic channel allocation scheme, frequency bands are not
permanently assigned to the users. Instead channels are allotted to users
dynamically as needed, from a central pool. The allocation is done
considering a number of parameters so that transmission interference is
minimized.
This allocation scheme optimises bandwidth usage and results is faster
transmissions.
Dynamic channel allocation is further divided into:
1. Centralised Allocation
2. Distributed Allocation

Protocol Assumption:

 N independent stations.
 A station is blocked until its generated frame is transmitted.
 probability of a frame being generated in a period of length Dt is IDt
where I is the arrival rate of frames.
 Only a single Channel available.
 Time can be either: Continuous or slotted.
 Carrier Sense: A station can sense if a channel is already busy before
transmission.
 No Carrier Sense: Time out used to sense loss data.
Multiple Access Protocols

Multiple Access Protocols are methods used in computer networks to

control how data is transmitted when multiple devices are trying to
communicate over the same network. These protocols ensure that data
packets are sent and received efficiently, without collisions or
interference. They help manage the network traffic so that all devices can
share the communication channel smoothly and effectively.

The Data Link Layer is responsible for the transmission of data between
two nodes. Its main functions are:
 Data Link Control
 Multiple Access Control

Taxonomy of multiple-access protocols

RANDOM ACCESS
In random access or contention methods, no station is superior to another
station and none is assigned the control over another. Two features give
this method its name. First, there is no scheduled time for a station to
transmit. Transmission is random among the stations. That is why these
methods are called random access. Second, no rules specify which station
should send next. Stations compete with one another to access the
medium. That is why these methods are also called contention methods.

ALOHA
1. Pure ALOHA :The original ALOHA protocol is called pure ALOHA. This
is a simple, but elegant protocol. The idea is that each station sends a
frame whenever it has a frame to send. However, since there is only
one channel to share, there is the possibility of collision between
frames from different stations. Below Figure shows an example of
frame collisions in pure ALOHA.
 In pure ALOHA, the stations transmit frames whenever they have data
to send.
 When two or more stations transmit simultaneously, there is
collision and the frames are destroyed.
 In pure ALOHA, whenever any station transmits a frame, it expects
the acknowledgement from the receiver.
 If acknowledgement is not received within specified time, the station
assumes that the frame (or acknowledgement) has been destroyed.
 If the frame is destroyed because of collision the station waits for a
random amount of time and sends it again. This waiting time must be
random otherwise same frames will collide again and again.
 Therefore pure ALOHA dictates that when time-out period passes,
each station must wait for a random amount of time before resending
its frame. This randomness will help avoid more collisions

Slotted ALOHA
It is similar to pure aloha, except that we divide time into slots and
sending of data is allowed only at the beginning of these slots. If a station
misses out the allowed time, it must wait for the next slot. This reduces
the probability of collision.

CSMA
Carrier Sense Multiple Access ensures fewer collisions as the station is
required to first sense the medium (for idle or busy) before transmitting
data. If it is idle then it sends data, otherwise it waits till the channel
becomes idle. However there is still chance of collision in CSMA due to
propagation delay. For example, if station A wants to send data, it will
first sense the medium. If it finds the channel idle, it will start sending
data. However, by the time the first bit of data is transmitted (delayed
due to propagation delay) from station A, if station B requests to send
data and senses the medium it will also find it idle and will also send data.
This will result in collision of data from station A and B.
CSMA Access Modes

 1-Persistent: The node senses the channel, if idle it sends the data,
otherwise it continuously keeps on checking the medium for being idle
and transmits unconditionally(with 1 probability) as soon as the
channel gets idle.
 Non-Persistent: The node senses the channel, if idle it sends the
data, otherwise it checks the medium after a random amount of time
(not continuously) and transmits when found idle.
 P-Persistent: The node senses the medium, if idle it sends the data
with p probability. If the data is not transmitted ((1-p) probability)
then it waits for some time and checks the medium again, now if it is
found idle then it send with p probability. This repeat continues until
the frame is sent. It is used in Wifi and packet radio systems.
 O-Persistent: Superiority of nodes is decided beforehand and
transmission occurs in that order. If the medium is idle, node waits for
its time slot to send data.

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

Carrier sense multiple access with collision detection. Stations can

terminate transmission of data if collision is detected.

Features of Collision Detection in CSMA/CD

• Carrier Sense: Before transmitting data, a device listens to the
network to check if the transmission medium is free. If the medium
is busy, the device waits until it becomes free before transmitting
data.
• Multiple Access: In a CSMA/CD network, multiple devices share
the same transmission medium. Each device has equal access to
the medium, and any device can transmit data when the medium is
free.
• Collision Detection: If two or more devices transmit data
simultaneously, a collision occurs. When a device detects a collision,
it immediately stops transmitting and sends a jam signal to inform
all other devices on the network of the collision. The devices then
wait for a random time before attempting to transmit again, to
reduce the chances of another collision.
• Backoff Algorithm: In CSMA/CD, a backoff algorithm is used to
determine when a device can retransmit data after a collision. The
 algorithm uses a random delay before a device retransmits data, to
reduce the likelihood of another collision occurring.

Carrier sense multiple access with collision avoidance( CSMA/CA)

This method was developed to decrease the chances of collisions when

two or more stations start sending their signals over the data link layer.
Carrier Sense multiple access requires that each station first check the
state of the medium before sending.

The basic idea behind CSMA/CA is that the station should be able to
receive while transmitting to detect a collision from different stations. In
wired networks, if a collision has occurred then the energy of the received
signal almost doubles, and the station can sense the possibility of
collision. In the case of wireless networks, most of the energy is used for
transmission, and the energy of the received signal increases by only 5-
10% if a collision occurs. It can‟t be used by the station to sense collision.
Therefore CSMA/CA has been specially designed for wireless networks.

Controlled Access Protocols

In controlled access, the stations seek data from one another to find
which station has the right to send. It allows only one node to send at a
time, to avoid the collision of messages on a shared medium.

The three controlled-access methods are:

 Reservation
 Polling
 Token Passing

1. Reservation
 In the reservation method, a station needs to make a reservation
before sending data.
 The timeline has two kinds of periods:
o Reservation interval of fixed time length
o Data transmission period of variable frames.
 If there are M stations, the reservation interval is divided into M
slots, and each station has one slot.
 Suppose if station 1 has a frame to send, it transmits 1 bit during
the slot 1. No other station is allowed to transmit during this slot.

2. Polling

• process is similar to the roll-call performed in class. Just like the

teacher, a controller sends a message to each node in turn.
• In this, one acts as a primary station(controller) and the others are
secondary stations. All data exchanges must be made through the
controller.

• The message sent by the controller contains the address of the

node being selected for granting access.

• Although all nodes receive the message the addressed one responds
to it and sends data if any. If there is no data, usually a “poll
reject”(NAK) message is sent back.

• Problems include high overhead of the polling messages and high

dependence on the reliability of the controller.

3. Token Passing
 In token passing scheme, the stations are connected logically to
each other in form of ring and access to stations is governed by
tokens.
 A token is a special bit pattern or a small message, which
circulate from one station to the next in some predefined order.
 In Token ring, token is passed from one station to another
adjacent station in the ring whereas in case of Token bus, each
station uses the bus to send the token to the next station in
some predefined order.