Sri Krishna Institute of

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,

Technology
Karnataka)

COMPUTER NETWORKS

MODULE 2

1 /
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

Data Link Control Services

The functions of data link control layer are

• Framing
• Flow Control &
• Error Control

2 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

Framing

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.

3 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

Frame Size

Frame sizes can be

i) Fixed Size- No need for defining boundaries of the frames
ii) Variable Size – Need to define end of one frame and beginning of next.

Two approaches for variable size:

iii) Character Oriented Framing
iv) Bit oriented approach
4 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

• Character Oriented Framing

Data – 8 bit characters from ASCII
Header – carries source, destination address and control information
Trailer – error detection redundant bits
Flag – Added at the beginning and end of a frame to separate one frame
from the next.

5 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

• Byte Stuffing(Character Stuffing)

A special byte is added to the data section of the frame when there is a
character with the same pattern as the flag.
The data section is stuffed with an extra byte. This byte is usually called the
escape character (ESC) and has a predefined bit pattern.

6 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

• 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.
– 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.

A frame in a bit-oriented protocol

7 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

Bit Stuffing & Unstuffing

8 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

• Flow Control

9 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

• Whenever an entity produces items and another entity consumes

them, there should be a balance between production and
consumption rates.
• If the items are produced faster than they can be consumed, the
consumer can be overwhelmed and may need to discard some
items.
• 4 entities involved
• Network and data-link layers at the sending node
• Network and data-link layers at the receiver node
10 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

• 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.

11 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

• Buffers
– A buffer is a set of memory locations that can hold packets at the
sender and receiver.

2 buffers,
1) one buffer at sending data-link layer
2) Other buffer at receiver data-link layer

When the buffer of the receiving data-link layer is full, it informs the sending
data-link layer to stop pushing frames.

12 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

• Error Control
– Implemented using two methods.

• 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.
• In the second method, if the frame is corrupted, it is silently
discarded; if it is not corrupted, an acknowledgment is sent

13 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

• Combination of Flow and Error Control

– 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.

14 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

• 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.

It means that there is no connection between frames. The frames are not
numbered and there is no sense of ordering.

15 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

• 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).

16 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

• Data-Link Layer Protocols

– 4 protocols
• Simple
• Stop and Wait
• Go-Back-N
• Selective Repeat

17 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

• Finite State Machine

• An FSM is thought of as a machine with a finite number of states. The
machine is always in one of the states until an event occurs. Each event is
associated with two reactions: defining the list (possibly empty) of actions
to be performed and determining the next state (which can be the same
as the current state). One of the states must be defined as the initial
state, the state in which the machine starts when it turns on

18 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

Connectionless & Connection-oriented service represented as FSMs

19 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

• Simple Protocol
Our first protocol is a simple protocol with neither flow nor
error control.

20 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

• 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

21 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

• FSM for Simple Protocol

22 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

• The sender site should not send a frame until its network layer has a message to send.
• The receiver site cannot deliver a message to its network layer until a frame arrives.
• 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.

23 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

• Flow Diagram of Simple Protocol

24 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

• Stop and Wait Protocol

– Uses both flow and error control

25 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

• The sender sends one frame at a time and waits for an acknowledgment before
sending the next one.
• To detect corrupted frames, we need to add a CRC to each data frame.
• When a frame arrives at the receiver site, it is checked. If its CRC is incorrect, the
frame is corrupted and silently discarded.
• Every time the sender sends a frame, it starts a timer.
• If an acknowledgment arrives before the timer expires, the timer is stopped and the
sender sends the next frame (if it has one to send). If the timer expires, the sender
resends the previous frame, assuming that the frame was either lost or corrupted.
• This means that the sender needs to keep a copy of the frame until its
acknowledgment arrives. //skit.org.in
06/25/2025 26
skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

• FSM for the Stop and Wait Protocol

27 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

• Sender State - 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.

28 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

• Receiver
• The receiver is always in the ready state. Two events may occur:

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.

29 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

• Flow Diagram:

30 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

• Flow diagram of adding sequence number and acknowledgement

number to prevent duplicates

31 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

• Piggybacking
– To make the communication more efficient, the data in one
direction is piggybacked with the acknowledgment in the other
direction. In other words, when node A is sending data to node
B, Node A also acknowledges the data received from node B.

32 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

• HDLC – High-Level Data Link Control

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

33 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

• Configurations and Transfer Modes

– 2 common transfer modes
• Normal response mode - the station configuration is unbalanced.

• Asynchronous balanced mode- the configuration is balanced

34 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

• HDLC Frames

• Flag field. This field contains synchronization pattern 01111110, which identifies both the beginning and the

end of a frame.

• Address field. This field contains the address of the secondary station. If a primary station created the

frame, it contains a to address. If a secondary station creates the frame, it contains a from address.

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

35 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

• Information field. The information field contains the user’s data from the network

layer or management information. Its length can vary from one network to another.
• FCS field. The frame check sequence (FCS) is the HDLC error detection field. It can

contain either a 2- or 4-byte CRC.

36 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

• Control Field For I Frame

• I-frames are designed to carry user data from the network layer

• The subfields in the control field are used to define these functions.

• The first bit defines the type. If the first bit of the control field is 0, this means the frame is an I-
frame.

• The next 3 bits, called N(S), define the sequence number of the frame.

• The last 3 bits, called N(R), correspond to the acknowledgment number when piggybacking is used.

• The P/F field is a single bit with a dual purpose

Poll- the frame is sent by a primary station to a secondary
Final-when the frame is sent by a secondary to a primary

37 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

• Control Field for S-Frames

• Supervisory frames are used for flow and error control whenever piggybacking is either impossible or inappropriate.

• S-frames do not have information fields. If the first 2 bits of the control field are 10, this means the frame is an S-
frame.

• 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.

38 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

• 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.
Receive not ready (RNR).
If the value of the code subfield is 10, it is an RNR S frame
• 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
Selective reject (SREJ). 39 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

Control Field for U- Frames

• Unnumbered frames are used to exchange session management and control
information between connected devices.
• U-frames contain an information field, but one used for system management
information, not user data.
• 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.

40 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

• Example of Connection and Disconnection

41 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

Without With
Errors Errors

42 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

• Point – Point Protocol

Users need to connect to their home computers to the server of an Internet

Service provider use PPP.
Users have a traditional modem; they are connected to the Internet through a
telephone line, which provides the services of the physical layer.

43 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

• Services Provided by PPP

• PPP is designed to accept payloads from several network layers.
• Authentication is also provided in the protocol,
• Multilink PPP, provides connections over multiple links.

• it provides network address configuration

44 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

• Services Not Provided by PPP

PPP does not provide flow control
PPP does not provide a sophisticated addressing mechanism to handle frames in a

multipoint configuration.

45 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

• Framing
• PPP uses a character-oriented (or byte-oriented) frame.

• 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

46 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

• Protocol. The protocol field defines what is being carried in the data field: either
user data or other information
Payload field. This field carries e The data field is a sequence of bytes with the
default of a maximum of 1500 bytes; either the user data or other information. 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.

47 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

• Byte Stuffing
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.

48 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

• Transition Phases

49 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

Dead State: there is no active carrier (at the physical layer) and the line is quiet.
Establish State: When one of the two nodes starts the communication, the connection goes
into the establish state. In this state, options are negotiated between the two parties.

Authenticate State: If the two parties agree that they need authentication (for example, if they
do not know each other), then the system needs to do authentication (an extra step);
otherwise, the parties can simply start communication.

Open State: Data transfer takes place in the open state.

Terminate 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.

50 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

• 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).

51 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

• 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.

52 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

• LCP Packets

53 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

• There are three categories of packets.

• The first category, comprising the first four packet types, is used for link
configuration during the establish phase.
• The second category, comprising packet types 5 and 6, is used for link
termination during the termination phase.

• The last five packets are used for link monitoring and debugging.

54 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

• Common Options

55 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

• Authentication Protocols
• PAP – Password Authentication Protocol
• CHAP- Challenge Handshake Authentication Protocol

56 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

• PAP
• The user who wants to access a system sends an authentication identification (usually
the user name) and a password.
• The system checks the validity of the identification and password and either accepts or

denies connection.

57 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

• CHAP – 3 way
• The system sends the user a challenge packet containing a challenge value, usually a
few bytes.
• 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.
• 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

58 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

• Network Control Protocols

• IPCP (Internet Protocol Control Protocol) configures the link for carrying IP data packets.

• Xerox CP does the same for the Xerox protocol data packets, and so on.

IPCP
This protocol configures the link used to carry IP packets in the Internet.

59 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

• IPCP

60 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

• IPCP defines 7 packets. They are coded as follows

61 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

• IP datagram

62 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

• 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,

63 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

Example of unidirectional movement of data from the user site to the system site (such as sending

an e-mail through an ISP).

64 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

• Random Access

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

assigned control over another. At each instance, a station that has data to send uses a procedure

defined by the protocol to make a decision on whether or not to send.

Two features give this method its name. First, there is no scheduled time for a station to transmit.

Transmission is random among the stations- Random Access

Second, no rules specify which station should send next.

Stations compete with one another to access the medium – Contention Methods

65 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

ALOHA
ALOHA, the earliest random access method, was developed at the University of Hawaii in early

1970. It was designed for a radio (wireless) LAN, but it can be used on any shared medium.

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.

66 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

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.

The pure ALOHA protocol relies on acknowledgments from the receiver. When a station sends a
frame, it expects the receiver to send an acknowledgment
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 has a second method to prevent congesting the channel with retransmitted frames.
After a maximum number of retransmission attempts Kmax, a station must give up and try later

67 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

Procedure for pure ALOHA protocol

68 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

Vulnerable Time - the length of time in which there is a possibility of collision.

Pure ALOHA vulnerable time 5 2 3 T fr

69 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

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

Frames in a slotted ALOHA network

70 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

Vulnerable Time

Slotted ALOHA vulnerable time 5 T fr

71 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

Throughput
It can be proven that the average number of successful transmissions for slotted
ALOHA is
S = G × e-G. The maximum throughput Smax is 0.368, when G = 1.

72 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

CSMA
The chance of collision can be reduced if a station senses the medium before trying
to use it.
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.”

73 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

Vulnerable time
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. When a station sends a
frame and any other station tries to send a frame during this time, a collision will result.
But if the first bit of the frame reaches the end of the medium, every station will already
have heard the bit and will refrain from sending.

74 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

Persistent Methods
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
75 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

Flow Diagram for I-Persistent

76 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

Non Persistent
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.

77 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

Flow Diagram for Non-Persistent

78 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

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.

79 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

Flow Diagram for p-Persistent

1. With probability p, the station sends its

frame.
2. With 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 backoff procedure.

80 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

• CSMA/ CD
The CSMA method does not specify the procedure following a collision. Carrier sense
multiple access with collision detection (CSMA/CD) augments the algorithm to handle

the collision.
In this method, 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.

81 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

• 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 sometime after time t2. Station C detects a collision at time t3
when it receives the first bit of A’s frame

82 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

Station C immediately (or after a short time, but we assume 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.

83 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

Flow Diagram of CSMA/CD

84 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

• The first difference is the addition of the persistence process.

• The second difference is the frame transmission. In ALOHA, we first transmit
the entire frame and then wait for an acknowledgment. In CSMA/CD,
transmission and collision detection are continuous processes.
• The third difference is the sending of a short jamming signal to make sure
that all other stations become aware of the collision.

85 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

Energy Level

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.

86 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

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.

87 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

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,

88 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

Flow Diagram of CSMA/CA

89 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

Interframe Space (IFS). First, 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.
Contention Window. 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.

90 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

Acknowledgment. With all these precautions, there still may be a collision

resulting in destroyed data.

Frame Exchange Time Line

91 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

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.
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 //skit.org.in
06/25/2025 92
skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

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.

Collision During Handshaking

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

93 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

Hidden-Station Problem
The solution to the hidden station problem is the use of the handshake frames

CSMA/CA and Wireless Networks

CSMA/CA was mostly intended for use in wireless networks.

94 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

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.

95 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

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.

96 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

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.

97 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

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.

98 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

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
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

99 //skit.org.in
06/25/2025 skit.org.i
Sri Krishna Institute of
(Approved by AICTE, Accredited by NAAC, Affiliated to VTU,
Technology
Karnataka)

• Logical Ring

100 //skit.org.in
06/25/2025 skit.org.i