U20CS404 COMPUTER NETWORKS NOTES - UNIT 2

UNIT II : DATA-LINK LAYER & MEDIA ACCESS

Introduction – Link-Layer Addressing – DLC Services – Data-Link Layer
Protocols – HDLC – PPP – Media Access Control – Wired LANs: Ethernet –
Wireless LANs – Introduction – IEEE 802.11, Bluetooth – Connecting Devices

1. INTRODUCTION
 In the OSI model, the data link layer is the 2nd layer from the bottom.
 It is responsible for transmitting frames from one node to next node.
 The main responsibility of the Data Link Layer is to transfer the datagram
across an individual link.
 An important characteristic of a Data Link Layer is that datagram can be
handled by different link layer protocols on different links in a path.
 The other responsibilities of this layer are
o Framing - Divides the stream of bits received into data units called
frames.
o Physical addressing – If frames are to be distributed to different
systems on the same network, data link layer adds a header to the
frame to define the sender and receiver.
o Flow control- If the rate at which the data are absorbed by the
receiver is less than the rate produced in the sender ,the Data link
layer imposes a flow control mechanism.
o Error control- Used for detecting and retransmitting damaged or
lost frames and to prevent duplication of frames. This is achieved
through a trailer added at the end of the frame.
o Medium Access control - Used to determine which device has
control over the link at any given time.

Nodes and Links

 Communication at the data-link layer is node-to-node.
 The communication channel that connects the adjacent nodes is known as
links, and in order to move the datagram from source to the destination, the
datagram must be moved across an individual link.
 A data unit from one point in the Internet needs to pass through many
networks (LAN and WAN) to reach another point.
 Theses LANs and WANs are connected by routers.
 The two end hosts and the routers are nodes and the networks in- between
are links.

1
U20CS404 COMPUTER NETWORKS NOTES - UNIT 2

 The first node is the source host; the last node is the destination host.
 The other four nodes are four routers.
 The first, the third, and the fifth links represent the three LANs; the second
and the fourth links represent the two WANs.
Two Categories of Links
Point- to-Point link and Broadcast link.
 In a point-to-point link, the link is dedicated to the two devices
 In a broadcast link, the link is shared between several pairs of devices.

Data Link Layer Services

 The data-link layer is located between the physical and the network layers.
 The datalink layer provides services to the network layer; it receives
services from the physical layer.
 When a packet is travelling, the data-link layer of a node (host or router) is
responsible for delivering a datagram to the next node in the path.
 For this purpose, the data-link layer of the sending node needs to
encapsulate the datagram and the data-link layer of the receiving node
needs to decapsulate the datagram.

 The datagram received by the data-link layer of the source host is

encapsulated in a frame.
 The frame is logically transported from the source host to the router.

2
U20CS404 COMPUTER NETWORKS NOTES - UNIT 2

 The frame is decapsulated at the data-link layer of the router and

encapsulated at another frame.
 The new frame is logically transported from the router to the destination
host.

Sublayers in Data Link layer

 We can divide the data-link layer into two sublayers: data link control
(DLC) and media access control (MAC).
 The data link control sublayer deals with all issues common to both point-
to-point and broadcast links
 The media access control sublayer deals only with issues specific to
broadcast links.

2. LINK-LAYER ADDRESSING
 A link-layer address is sometimes called a link address, sometimes a
physical address, and sometimes a MAC address.
 Since a link is controlled at the data-link layer, the addresses need to belong
to the data-link layer.
 When a datagram passes from the network layer to the data-link layer, the
datagram will be encapsulated in a frame and two data-link addresses are
added to the frame header.
 These two addresses are changed every time the frame moves from one link
to another.

THREE TYPES OF ADDRESSES

The link-layer protocols define three types of addresses: unicast, multicast, and
broadcast.

3
U20CS404 COMPUTER NETWORKS NOTES - UNIT 2

Unicast Address :
Each host or each interface of a router is assigned a unicast address.
Unicasting means one-to-one communication. A frame with a unicast
address destination is destined only for one entity in the link.

Multicast Address :
Link-layer protocols define multicast addresses. Multicasting means one-to-
many Communication but not all.

Broadcast Address :
Link-layer protocols define a broadcast address. Broadcasting means one-
to-all communication. A frame with a destination broadcast address is sent
to all entities in the link.

ADDRESS RESOLUTION PROTOCOL (ARP)

o ARP stands for Address Resolution Protocol.
o ARP is the most important protocol of the Data Link Layer.
o ARP is a network layer protocol used to convert a IP address
(Network/Logical address) into a MAC Address (Hardware /Physical
address).

o The computer programs/applications use logical address (IP address) to

send/receive messages, however the actual communication happens over
the physical address (MAC address).
o To send a datagram over a network, we need both the logical and physical
address.
o IP addresses are made up of 32 bits whereas MAC addresses are made up of
48 bits.
o ARP enables each host to build a table of IP address and corresponding
physical address.
o ARP relies on broadcast support from physical networks.
o The Address Resolution Protocol is a request and response protocol.
o The types of ARP messages are:
1. ARP request
2. ARP reply

4
U20CS404 COMPUTER NETWORKS NOTES - UNIT 2

ARP Operation
o ARP maintains a cache table in which MAC addresses are mapped to IP
addresses.
o If a host wants to send an IP datagram to a host,it first checks for a mapping
in the cache table.
o If no mapping is found, it needs to invoke the Address Resolution Protocol
over the network.
o It does this by broadcasting an ARP query onto the network.
o This query contains the target IP address.
o Each host receives the query and checks to see if it matches its IP address.
o If it does match, the host sends a response message that contains its link-
layer address (MAC Address) back to the originator of the query.
o The originator adds the information contained in this response to its ARP
table.
o For example,
To determine system B’s physical (MAC) address, system A broadcasts
an ARP request containing B’s IP address to all machines on its
network.

o All nodes except the destination discard the packet but update their ARP
table.
o Destination host (System B)constructs an ARP Response packet
o ARP Response is unicast and sent back to the source host (System A).
o Source stores target Logical & Physical address pair in its ARP table from
ARP Response.
o If target node does not exist on same network, ARP request is sent to
default router.

5
U20CS404 COMPUTER NETWORKS NOTES - UNIT 2

ARP Packet

RARP – Reverse ARP

o Reverse Address Resolution protocol (RARP) allows a host to convert its
MAC address to the corresponding IP address.

3. DLC SERVICES
 The data link control (DLC) deals with procedures for communication
between two adjacent nodes—node-to-node communication—no matter
whether the link is dedicated or broadcast.
 Data link control service include
(1) Framing (2) Flow Control (3) Error Control

1. FRAMING
 The data-link layer packs the bits of a message into frames, so that each
frame is distinguishable from another.

 Although the whole message could be packed in one frame, that is not
normally done.
 One reason is that a frame can be very large, making flow and error control
very inefficient.

6
U20CS404 COMPUTER NETWORKS NOTES - UNIT 2

 When a message is carried in one very large frame, even a single-bit error
would require the retransmission of the whole frame.
 When a message is divided into smaller frames, a single-bit error affects
only that small frame.
 Framing in the data-link layer separates a message from one source to a
destination by adding a sender address and a destination address.
 The destination address defines where the packet is to go; the sender
address helps the recipient acknowledge the receipt.

Frame Size
 Frames can be of fixed or variable size.
 Frames of fixed size are called cells. In fixed-size framing, there is no need
for defining the boundaries of the frames; the size itself can be used as a
delimiter.
 In variable-size framing, we need a way to define the end of one frame and
the beginning of the next. Two approaches were used for this purpose: a
character-oriented approach and a bit-oriented approach.

Character-Oriented Framing
 In character-oriented (or byte-oriented) framing, data to be carried are 8-bit
characters.
 To separate one frame from the next, an 8-bit (1-byte) flag is added at the
beginning and the end of a frame.
 The flag, composed of protocol-dependent special characters, signals the
start or end of a frame.

 Any character used for the flag could also be part of the information.
 If this happens, when it encounters this pattern in the middle of the data,the
receiver thinks it has reached the end of the frame.
 To fix this problem, a byte-stuffing strategy was added to character-
oriented framing.

Byte Stuffing (or) Character Stuffing

 Byte stuffing is the process of adding one extra byte whenever there is a
flag or escape character in the text.
 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.
 The data section is stuffed with an extra byte. 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, not as a delimiting flag.

7
U20CS404 COMPUTER NETWORKS NOTES - UNIT 2

Bit-Oriented Framing
 In bit-oriented framing, the data section of a frame is a sequence of bits to
be interpreted by the upper layer as text, graphic, audio, video, and so on.
 In addition to headers and trailers), we still need a delimiter to separate one
frame from the other.
 Most protocols use a special 8-bit pattern flag, 01111110, as the delimiter to
define the beginning and the end of the frame

 If the flag pattern appears in the data, the receiver must be informed that
this is not the end of the frame.
 This is done by stuffing 1 single bit (instead of 1 byte) to prevent the pattern
from looking like a flag. The strategy is called bit stuffing.

Bit Stuffing
 Bit stuffing is the process of adding one extra 0 whenever five
consecutive 1s follow a 0 in the data, so that the receiver does not
mistake the pattern 0111110 for a flag.
 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.
 The extra bit is added after one 0 followed by five 1’s regardless of the
value of the next bit.
 This guarantees that the flag field sequence does not inadvertently appear in
the frame.

8
U20CS404 COMPUTER NETWORKS NOTES - UNIT 2

2. FLOW CONTROL
o Flow control refers to a set of procedures used to restrict the amount
of data that the sender can send before waiting for acknowledgment.
o The receiving device has limited speed and limited memory to store the
data.
o Therefore, the receiving device must be able to inform the sending device to
stop the transmission temporarily before the limits are reached.
o It requires a buffer, a block of memory for storing the information until they
are processed.

Two methods have been developed to control the flow of data:

o Stop-and-Wait
o Sliding Window
o
STOP-AND-WAIT
o The simplest scheme is the stop-and-wait algorithm.
o In the Stop-and-wait method, the sender waits for an acknowledgement
after every frame it sends.
o When acknowledgement is received, then only next frame is sent.
o The process of alternately sending and waiting of a frame continues until
the sender transmits the EOT (End of transmission) frame.

9
U20CS404 COMPUTER NETWORKS NOTES - UNIT 2

o If the acknowledgement is not received within the allotted time, then the
sender assumes that the frame is lost during the transmission, so it will
retransmit the frame.
o The acknowledgement may not arrive because of the following three
scenarios :
1. Original frame is lost
2. ACK is lost
3. ACK arrives after the timeout

Advantage of Stop-and-wait
o The Stop-and-wait method is simple as each frame is checked and
acknowledged before the next frame is sent

Disadvantages of Stop-And-Wait
o In stop-and-wait, at any point in time, there is only one frame that is sent
and waiting to be acknowledged.
o This is not a good use of transmission medium.
o To improve efficiency, multiple frames should be in transition while
waiting for ACK.

10
U20CS404 COMPUTER NETWORKS NOTES - UNIT 2

PIGGYBACKING

o A method to combine a data frame

with ACK.
o Piggybacking saves bandwidth
o Station A and B both have data to
send.
o Instead of sending separately,
station A sends a data frame that
includes an ACK.
o Station B does the same thing.

SLIDING WINDOW
o The Sliding Window is a method of flow control in which a sender can
transmit the several frames before getting an acknowledgement.
o In Sliding Window Control, multiple frames can be sent one after the
another due to which capacity of the communication channel can be utilized
efficiently.
o A single ACK acknowledge multiple frames.
o Sliding Window refers to imaginary boxes at both the sender and receiver
end.
o The window can hold the frames at either end, and it provides the upper
limit on the number of frames that can be transmitted before the
acknowledgement.
o Frames can be acknowledged even when the window is not completely
filled.
o The window has a specific size in which they are numbered as modulo-n
means that they are numbered from 0 to n-1.
o For example, if n = 8, the frames are numbered from
0,1,2,3,4,5,6,7,0,1,2,3,4,5,6,7,0,1........
o The size of the window is represented as n-1. Therefore, maximum n-1
frames can be sent before acknowledgement.
o When the receiver sends the ACK, it includes the number of the next frame
that it wants to receive.
o For example, to acknowledge the string of frames ending with frame
number 4, the receiver will send the ACK containing the number 5.
o When the sender sees the ACK with the number 5, it got to know that the
frames from 0 through 4 have been received.

11
U20CS404 COMPUTER NETWORKS NOTES - UNIT 2

Sender Window Receiver Window

o At the beginning of a transmission, the o At the beginning of transmission, the

sender window contains n-1 frames. receiver window does not contain n frames,
o When a frame is sent, the size of the but it contains n-1 spaces for frames.
window shrinks. o When the new frame arrives, the size of the
o For example, if the size of the window window shrinks.
is ‘w’ and if three frames are sent out, o For example, the size of the window is w
then the number of frames left out in and if three frames are received then the
the sender window is w-3. number of spaces available in the window
o Once the ACK has arrived, then the is (w-3).
sender window expands to the number o Once the acknowledgement is sent, the
which will be equal to the number of receiver window expands by the number
frames acknowledged by ACK. equal to the number of frames
acknowledged.

Example of Sliding Window

12
U20CS404 COMPUTER NETWORKS NOTES - UNIT 2

3. ERROR CONTROL

Data can be corrupted during transmission. For reliable communication, errors

must be detected and corrected. Error Control is a technique of error detection and
retransmission.
TYPES OF ERRORS
SINGLE-BIT ERROR
The term Single-bit error means that only one bit of a given data unit (such as byte,
character, data unit or packet) is changed from 1 to 0 or from 0 to 1.

BURST ERROR
The term Burst Error means that two or more bits in the data unit have changed
from 1 to 0 or from 0 to 1.

ERROR DETECTION TECHNIQUES / METHODS

The basic idea behind any error detection scheme is to add additional information
to a frame that can be used to determine if errors have been introduced.

PARITY CHECK
 One bit, called parity bit is added to every data unit so that the total number
of 1’s in the data unit becomes even (or) odd.
 The source then transmits this data via a link, and bits are checked and
verified at the destination.
 Data is considered accurate if the number of bits (even or odd) matches the
number transmitted from the source.
 This techniques is the most common and least complex method.

13
U20CS404 COMPUTER NETWORKS NOTES - UNIT 2

1. Even parity – Maintain even number of 1s

E.g., 1011 → 1011 1
2. Odd parity – Maintain odd number of 1s
E.g., 1011 → 1011 0

CYCLIC REDUNDANCY CHECK

 Cyclic codes refers to encoding messages by adding a fixed-length check
value.
 CRCs are popular because they are simple to implement, easy to analyze
mathematically and particularly good at detecting common errors caused in
transmission channels.

Steps Involved :
 Consider the original message (dataword) as M(x) consisting of ‘k’ bits and
the divisor as C(x) consists of ‘n+1’ bits.
 The original message M(x) is appended by ‘n’ bits of zero’s. Let us call
this zero-extended message as T(x).
 Divide T(x) by C(x) and find the remainder.
 The division operation is performed using XOR operation.
 The resultant remainder is appended to the original message M(x) as CRC
and sent by the sender(codeword).

Example 1:
 Consider the Dataword / Message M(x) = 1001
 Divisor C(x) = 1011 (n+1=4)
 Appending ‘n’ zeros to the original Message M(x).
 The resultant messages is called T(x) = 1001 000. (here n=3)
 Divide T(x) by the divisor C(x) using XOR operation.

14
U20CS404 COMPUTER NETWORKS NOTES - UNIT 2

Sender Side :

Receiver Side:
(For Both Case – Without Error and With Error)

15
U20CS404 COMPUTER NETWORKS NOTES - UNIT 2

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.

INTERNET CHECKSUM

 Checksum is a calculated value that is used to determine the integrity of

data.

16
U20CS404 COMPUTER NETWORKS NOTES - UNIT 2

Example : Let the message to be transmitted be 7,11,12,0,6.

ERROR CONTROL

 Error control includes both error detection and error correction.

 Whenever an error is detected, specified frames are retransmitted
 It allows the receiver to inform the sender if a frame is lost or damaged
during transmission and coordinates the retransmission of those frames by
the sender.
 Includes the following actions:
o Error detection
o Positive Acknowledgement (ACK): if the frame arrived with no
errors
o Negative Acknowledgement (NAK): if the frame arrived with errors
o Retransmissions after Timeout: Frame is retransmitted after certain
amount of time if no acknowledgement was received
 Error control in the data link layer is based on automatic repeat request
(ARQ).

Categories of Error Control

17
U20CS404 COMPUTER NETWORKS NOTES - UNIT 2

STOP-AND-WAIT ARQ
 Stop-and-wait ARQ is a technique used to retransmit the data in case of
damaged or lost frames.
 This technique works on the principle that the sender will not transmit the
next frame until it receives the acknowledgement of the last transmitted
frame.

Two possibilities of the retransmission in Stop and Wait ARQ:

o Damaged Frame: When the receiver receives a damaged frame(i.e., the

frame contains an error), then it returns the NAK frame. For example, when
the frame DATA 1 is sent, and then the receiver sends the ACK 0 frame
means that the data 1 has arrived correctly. The sender transmits the next
frame: DATA 0. It reaches undamaged, and the receiver returns ACK 1.
The sender transmits the third frame: DATA 1. The receiver reports an error
and returns the NAK frame. The sender retransmits the DATA 1 frame.

o Lost Frame: Sender is equipped with the timer and starts when the frame is
transmitted. Sometimes the frame has not arrived at the receiving end so
that it cannot be acknowledged either positively or negatively. The sender
waits for acknowledgement until the timer goes off. If the timer goes off, it
retransmits the last transmitted frame.

18
U20CS404 COMPUTER NETWORKS NOTES - UNIT 2

SLIDING WINDOW ARQ

Sliding Window ARQ is a technique used for continuous transmission error

control.

Two protocols used in sliding window ARQ:

1. GO-BACK-N ARQ
o In Go-Back-N ARQ protocol, if one frame is lost or damaged, then it
retransmits all the frames after which it does not receive the positive ACK.

o In the above figure, three frames (Data 0,1,2) have been transmitted before
an error discovered in the third frame.
o The receiver discovers the error in Data 2 frame, so it returns the NAK 2
frame.
o All the frames including the damaged frame (Data 2,3,4) are discarded as it
is transmitted after the damaged frame.
o Therefore, the sender retransmits the frames (Data2,3,4).

2. SELECTIVE-REJECT(REPEAT) ARQ

o Selective-Reject ARQ technique is more efficient than Go-Back-n ARQ.

o In this technique, only those frames are retransmitted for which negative
acknowledgement (NAK) has been received.
o The receiver storage buffer keeps all the damaged frames on hold until the
frame in error is correctly received.
o The receiver must have an appropriate logic for reinserting the frames in a
correct order.
o The sender must consist of a searching mechanism that selects only the
requested frame for retransmission.

19
U20CS404 COMPUTER NETWORKS NOTES - UNIT 2

o In the above figure, three frames (Data 0,1,2) have been transmitted before
an error discovered in the third frame.
o The receiver discovers the error in Data 2 frame, so it returns the NAK 2
frame.
o The damaged frame only (Data 2) is discarded.
o The other subsequent frames (Data 3,4) are accepted.
o Therefore, the sender retransmits only the damaged frame (Data2).

4. DATA-LINK LAYER PROTOCOLS

Four protocols have been defined for the data-link layer controls.
They are
1. Simple Protocol
2. Stop-and-Wait Protocol
3. Go-Back-N Protocol
4. Selective-Repeat Protocol

1. SIMPLE PROTOCOL

o The first protocol is a simple protocol with neither flow nor error control.
o We assume that the receiver can immediately handle any frame it receives.
o In other words, the receiver can never be overwhelmed with incoming
frames.
o The data-link layers of the sender and receiver provide transmission
services for their network layers.

20
U20CS404 COMPUTER NETWORKS NOTES - UNIT 2

o The data-link layer at the sender gets a packet from its network layer, makes
a frame out of it, and sends the frame.
o 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.

NOTE :

2. STOP-AND-WAIT PROTOCOL
REFER STOP AND WAIT FROM FLOW CONTROL

3. GO-BACK-N PROTOCOL
REFER GO-BACK-N ARQ FROM ERROR CONTROL

4. SELECTIVE-REPEAT PROTOCOL
REFER SELECTIVE-REPEAT ARQ FROM ERROR CONTROL

5. HDLC (HIGH-LEVEL DATA LINK CONTROL)

o High-level Data Link Control (HDLC) is a bit-oriented protocol

o HDLC is used for communication over point-to-point and multipoint links.
o HDLC implements the Stop-and-Wait protocol.

HDLC CONFIGURATIONS AND TRANSFER MODES

HDLC provides two common transfer modes that can be used in different
configurations:
1. Normal response mode (NRM)
2. Asynchronous balanced mode (ABM).

21