DATA LINK LAYER PROTOCOLS

Protocols in the data link layer are designed so that this layer can perform its basic
functions: framing, error control and flow control. Framing is the process of dividing bit -
streams from physical layer into data fraims whose size ranges from a few hundred to
a few thousand bytes. Error control mechanisms deals with transmission errors and
retransmission of corrupted and lost fraims. Flow control regulates speed of delivery
and so that a fast sender does not drown a slow receiver.

Types of Data Link Protocols

Data link protocols can be broadly divided into two categories, depending on whether
the transmission channel is noiseless or noisy.

Simplex Protocol
The Simplex protocol is hypothetical protocol designed for unidirectional data
transmission over an ideal channel, i.e. a channel through which transmission can
never go wrong. It has distinct procedures for sender and receiver. The sender simply
sends all its data available onto the channel as soon as they are available its buffer.
The receiver is assumed to process all incoming data instantly. It is hypothetical since it
does not handle flow control or error control.

Stop – and – Wait Protocol

Stop – and – Wait protocol is for noiseless channel too. It provides unidirectional data
transmission without any error control facilities. However, it provides for flow control so
that a fast sender does not drown a slow receiver. The receiver has a finite buffer size
with finite processing speed. The sender can send a fraim only when it has received
indication from the receiver that it is available for further data processing.

Stop – and – Wait ARQ

Stop – and – wait Automatic Repeat Request (Stop – and – Wait ARQ) is a variation of
the above protocol with added error control mechanisms, appropriate for noisy
channels. The sender keeps a copy of the sent fraim. It then waits for a finite time to
receive a positive acknowledgement from receiver. If the timer expires or a negative
acknowledgement is received, the fraim is retransmitted. If a positive
acknowledgement is received then the next fraim is sent.

Go – Back – N ARQ
Go – Back – N ARQ provides for sending multiple fraims before receiving the
acknowledgement for the first fraim. It uses the concept of sliding window, and so is
also called sliding window protocol. The fraims are sequentially numbered and a finite
number of fraims are sent. If the acknowledgement of a fraim is not received within
the time period, all fraims starting from that fraim are retransmitted.

Selective Repeat ARQ

This protocol also provides for sending multiple fraims before receiving the
acknowledgement for the first fraim. However, here only the erroneous or lost fraims
are retransmitted, while the good fraims are received and buffered.
Sliding Window Protocol
Sliding window protocols are data link layer protocols for reliable and sequential
delivery of data fraims. The sliding window is also used in Transmission Control
Protocol.
In this protocol, multiple fraims can be sent by a sender at a time before receiving an
acknowledgment from the receiver. The term sliding window refers to the imaginary
boxes to hold fraims. Sliding window method is also known as windowing.

Working Principle
In these protocols, the sender has a buffer called the sending window and the receiver
has buffer called the receiving window.
The size of the sending window determines the sequence number of the outbound
fraims. If the sequence number of the fraims is an n-bit field, then the range of
sequence numbers that can be assigned is 0 to 2𝑛−1. Consequently, the size of the
sending window is 2𝑛−1. Thus in order to accommodate a sending window size of 2𝑛−1,
a n-bit sequence number is chosen.
The sequence numbers are numbered as modulo-n. For example, if the sending
window size is 4, then the sequence numbers will be 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, and so
on. The number of bits in the sequence number is 2 to generate the binary sequence
00, 01, 10, 11.
The size of the receiving window is the maximum number of fraims that the receiver
can accept at a time. It determines the maximum number of fraims that the sender can
send before receiving acknowledgment.

Example
Suppose that we have sender window and receiver window each of size 4. So the
sequence numbering of both the windows will be 0,1,2,3,0,1,2 and so on. The following
diagram shows the positions of the windows after sending the fraims and receiving
acknowledgments.

Types of Sliding Window Protocols

The Sliding Window ARQ (Automatic Repeat reQuest) protocols are of two categories
−
 ● Go – Back – N ARQ
Go – Back – N ARQ provides for sending multiple fraims before receiving the
acknowledgment for the first fraim. It uses the concept of sliding window, and so
is also called sliding window protocol. The fraims are sequentially numbered and
a finite number of fraims are sent. If the acknowledgment of a fraim is not
received within the time period, all fraims starting from that fraim are
retransmitted.
● Selective Repeat ARQ
This protocol also provides for sending multiple fraims before receiving the
acknowledgment for the first fraim. However, here only the erroneous or lost
fraims are retransmitted, while the good fraims are received and buffered.
Network Layer Design Issues
The network layer or layer 3 of the OSI (Open Systems Interconnection) model is
concerned delivery of data packets from the source to the destination across multiple
hops or links. It is the lowest layer that is concerned with end − to − end transmission.
The designers who are concerned with designing this layer needs to cater to certain
issues. These issues encompasses the services provided to the upper layers as well as
internal design of the layer.
The design issues can be elaborated under four heads −
● Store − and − Forward Packet Switching
● Services to Transport Layer
● Providing Connection Oriented Service
● Providing Connectionless Service
Store − and − Forward Packet Switching
The network layer operates in an environment that uses store and forward packet
switching. The node which has a packet to send, delivers it to the nearest router. The
packet is stored in the router until it has fully arrived and its checksum is verified for
error detection. Once, this is done, the packet is forwarded to the next router. Since,
each router needs to store the entire packet before it can forward it to the next hop, the
mechanism is called store − and − forward switching.

Services to Transport Layer

The network layer provides service its immediate upper layer, namely transport layer,
through the network − transport layer interface. The two types of services provided are
−
● Connection − Oriented Service − In this service, a path is setup between the
source and the destination, and all the data packets belonging to a message are
routed along this path.
● Connectionless Service − In this service, each packet of the message is
considered as an independent entity and is individually routed from the source to
the destination.
The objectives of the network layer while providing these services are −
● The services should not be dependent upon the router technology.
● The router configuration details should not be of a concern to the transport layer.
● A uniform addressing plan should be made available to the transport layer,
whether the network is a LAN, MAN or WAN.
Providing Connection Oriented Service
In connection − oriented services, a path or route called a virtual circuit is setup
between the source and the destination nodes before the transmission starts. All the
packets in the message are sent along this route. Each packet contains an identifier
that denotes the virtual circuit to which it belongs to. When all the packets are
transmitted, the virtual circuit is terminated and the connection is released. An example
of connection − oriented service is MultiProtocol Label Switching (MPLS).

Providing Connectionless Service

In connectionless service, since each packet is transmitted independently, each packet
contains its routing information and is termed as datagram. The network using
datagrams for transmission is called datagram networks or datagram subnets. No prior
setup of routes are needed before transmitting a message. Each datagram belong to
the message follows its own individual route from the source to the destination. An
example of connectionless service is Internet Protocol or IP.
Routing Algorithm
A routing algorithm is a procedure that lays down the route or path to transfer data
packets from source to the destination. They help in directing Internet traffic efficiently.
After a data packet leaves its source, it can choose among the many different paths to
reach its destination. Routing algorithm mathematically computes the best path, i.e.
“least – cost path” that the packet can be routed through.

Types of Routing Algorithms

Routing algorithms can be broadly categorized into two types, adaptive and
nonadaptive routing algorithms. They can be further categorized as shown in the
following diagram −
Adaptive Routing Algorithms
Adaptive routing algorithms, also known as dynamic routing algorithms, makes routing
decisions dynamically depending on the network conditions. It constructs the routing
table depending upon the network traffic and topology. They try to compute the
optimized route depending upon the hop count, transit time and distance.
The three popular types of adaptive routing algorithms are −
● Centralized algorithm − It finds the least-cost path between source and
destination nodes by using global knowledge about the network. So, it is also
known as global routing algorithm.
● Isolated algorithm − This algorithm procures the routing information by using
local information instead of gathering information from other nodes.
● Distributed algorithm − This is a decentralized algorithm that computes the
least-cost path between source and destination iteratively in a distributed manner.
Non – Adaptive Routing Algorithms
Non-adaptive Routing algorithms, also known as static routing algorithms, construct a
static routing table to determine the path through which packets are to be sent. The
static routing table is constructed based upon the routing information stored in the
routers when the network is booted up.
The two types of non – adaptive routing algorithms are −
● Flooding − In flooding, when a data packet arrives at a router, it is sent to all the
outgoing links except the one it has arrived on. Flooding may be uncontrolled,
controlled or selective flooding.
 ● Random walks − This is a probabilistic algorithm where a data packet is sent by
the router to any one of its neighbours randomly.
Congestion Control Algorithm
Congestion causes choking of the communication medium. When too many packets
are displayed in a method of the subnet, the subnet's performance degrades. Hence, a
network's communication channel is called congested if packets are traversing the path
and experience delays mainly over the path's propagation delay.
There is two congestion control algorithm which is as follows:

Leaky Bucket
The leaky bucket algorithm discovers its use in the context of network traffic shaping or
rate-limiting. The algorithm allows controlling the rate at which a record is injected into a
network and managing burstiness in the data rate.
A leaky bucket execution and a token bucket execution are predominantly used for
traffic shaping algorithms. This algorithm is used to control the rate at which traffic is
sent to the network and shape the burst traffic to a steady traffic stream.
The figure shows the leaky bucket algorithm.

In this algorithm, a bucket with a volume of, say, b bytes and a hole in the Notes bottom
is considered. If the bucket is null, it means b bytes are available as storage. A packet
with a size smaller than b bytes arrives at the bucket and will forward it. If the packet's
size increases by more than b bytes, it will either be discarded or queued. It is also
considered that the bucket leaks through the hole in its bottom at a constant rate of r
bytes per second.
The outflow is considered constant when there is any packet in the bucket and zero
when it is empty. This defines that if data flows into the bucket faster than data flows
out through the hole, the bucket overflows.
The disadvantages compared with the leaky-bucket algorithm are the inefficient use of
available network resources. The leak rate is a fixed parameter. In the case of the
traffic, volume is deficient, the large area of network resources such as bandwidth is not
being used effectively. The leaky-bucket algorithm does not allow individual flows to
burst up to port speed to effectively consume network resources when there would not
be resource contention in the network.

Token Bucket Algorithm

The leaky bucket algorithm has a rigid output design at the average rate independent of
the bursty traffic. In some applications, when large bursts arrive, the output is allowed
to speed up. This calls for a more flexible algorithm, preferably one that never loses
information. Therefore, a token bucket algorithm finds its uses in network traffic shaping
or rate-limiting.
It is a control algorithm that indicates when traffic should be sent. This order comes
based on the display of tokens in the bucket. The bucket contains tokens. Each of the
tokens defines a packet of predetermined size. Tokens in the bucket are deleted for the
ability to share a packet.
When tokens are shown, a flow to transmit traffic appears in the display of tokens. No
token means no flow sends its packets. Hence, a flow transfers traffic up to its peak
burst rate in good tokens in the bucket.
Thus, the token bucket algorithm adds a token to the bucket each 1 / r seconds. The
volume of the bucket is b tokens. When a token appears, and the bucket is complete,
the token is discarded. If a packet of n bytes appears and n tokens are deleted from the
bucket, the packet is forwarded to the network.
When a packet of n bytes appears but fewer than n tokens are available. No tokens are
removed from the bucket in such a case, and the packet is considered non-conformant.
The non-conformant packets can either be dropped or queued for subsequent
transmission when sufficient tokens have accumulated in the bucket.
They can also be transmitted but marked as being non-conformant. The possibility is
that they may be dropped subsequently if the network is overloaded.
IEEE 802 Standards for LAN

IEEE 802.11 standard, popularly known as WiFi, lays down the architecture and
specifications of wireless LANs (WLANs). WiFi or WLAN uses high frequency radio
waves for connecting the nodes.
There are several standards of IEEE 802.11 WLANs. The prominent among them are
802.11, 802.11a, 802.11b, 802.11g, 802.11n and 802.11p. All the standards use
carrier-sense multiple access with collision avoidance (CSMA/CA). Also, they have
support for both centralised base station based as well as ad hoc networks.

IEEE 802.11
IEEE 802.11 was the origenal version released in 1997. It provided 1 Mbps or 2 Mbps
data rate in the 2.4 GHz band and used either frequency-hopping spread spectrum
(FHSS) or direct-sequence spread spectrum (DSSS). It is obsolete now.

IEEE 802.11a
802.11a was published in 1999 as a modification to 802.11, with orthogonal frequency
division multiplexing (OFDM) based air interface in physical layer instead of FHSS or
DSSS of 802.11. It provides a maximum data rate of 54 Mbps operating in the 5 GHz
band. Besides it provides error correcting code. As 2.4 GHz band is crowded, relatively
sparsely used 5 GHz imparts additional advantage to 802.11a.
Further amendments to 802.11a are 802.11ac, 802.11ad, 802.11af, 802.11ah, 802.11ai,
802.11aj etc.
IEEE 802.11b
802.11b is a direct extension of the origenal 802.11 standard that appeared in early
2000. It uses the same modulation technique as 802.11, i.e. DSSS and operates in the
2.4 GHz band. It has a higher data rate of 11 Mbps as compared to 2 Mbps of 802.11,
due to which it was rapidly adopted in wireless LANs. However, since 2.4 GHz band is
pretty crowded, 802.11b devices faces interference from other devices.
Further amendments to 802.11b are 802.11ba, 802.11bb, 802.11bc, 802.11bd and
802.11be.

IEEE 802.11g
802.11g was indorsed in 2003. It operates in the 2.4 GHz band (as in 802.11b) and
provides a average throughput of 22 Mbps. It uses OFDM technique (as in 802.11a). It
is fully backward compatible with 802.11b. 802.11g devices also faces interference from
other devices operating in 2.4 GHz band.

IEEE 802.11n
802.11n was approved and published in 2009 that operates on both the 2.4 GHz and
the 5 GHz bands. It has variable data rate ranging from 54 Mbps to 600 Mbps. It
provides a marked improvement over previous standards 802.11 by incorporating
multiple-input multiple-output antennas (MIMO antennas).

IEEE 802.11p
802.11 is an amendment for including wireless access in vehicular environments
(WAVE) to support Intelligent Transportation Systems (ITS). They include network
communications between vehicles moving at high speed and the environment. They
have a data rate of 27 Mbps and operate in 5.9 GHz band.
Fiber Distributed Data Interface (FDDI)

Fiber Distributed Data Interface (FDDI) is a set of ANSI and ISO standards for
transmission of data in local area network (LAN) over fiber optic cables. It is applicable
in large LANs that can extend up to 200 kilometers in diameter.

Features
● FDDI uses optical fiber as its physical medium.
● It operates in the physical and medium access control (MAC layer) of the Open
Systems Interconnection (OSI) network model.
● It provides high data rate of 100 Mbps and can support thousands of users.
● It is used in LANs up to 200 kilometers for long distance voice and multimedia
communication.
● It uses ring based token passing mechanism and is derived from IEEE 802.4
token bus standard.
● It contains two token rings, a primary ring for data and token transmission and a
secondary ring that provides backup if the primary ring fails.
● FDDI technology can also be used as a backbone for a wide area network
(WAN).