IILM UNIVERSITY GREATER NOIDA

Course Name:

Course Code :

Topic: Greedy Strategy:

Session : 5

1
 About the Educator
Instructor Name :

Designation : Assistant Professor

Machine Learning & Data Science

School of Computer Science &

Engineering

2
 Outline of Lecture

1. Topic Name: Automatic Repeat Request (ARQ)

2. Topic Name: High-Level Data Link Control (HDLC)
3. Topic Name: Point-to-Point Protocol (PPP)
4. Topic Name:Multiple Access Protocols

3
 Automatic Repeat Request
ARQ (Automatic Repeat Request) is an error-control protocol that ensures reliable data transmission by detecting
and retransmitting lost or corrupted frames.
1.1 Stop-and-Wait ARQ
•How it Works:
• The sender transmits one frame and waits for an ACK (Acknowledgment) before sending the next.
• If the ACK is not received within a timeout period, the sender retransmits the frame.
• The receiver sends an ACK only if the frame is error-free.
•Advantages:
• Simple to implement.
• No need for buffering at the receiver.
•Disadvantages:
• Low efficiency due to waiting time (especially in high-latency networks).
• If the ACK is lost, the sender unnecessarily retransmits.
•Performance Analysis:
• Utilization (U) = (T_frame) / (T_frame + 2 * T_propagation)
• Where:
• Tframe T_frame​= Time to transmit one frame.
• Tpropagation T_propagation​= Propagation delay.
4
• 1.2 Go-Back-N ARQ
• How it Works:
• Uses a sliding window mechanism where the sender can transmit multiple frames (window size =
N) without waiting for individual ACKs.
• The receiver only accepts in-order frames. If a frame is lost, all subsequent frames are discarded.
• The sender retransmits all unacknowledged frames starting from the lost one.
• Advantages:
• More efficient than Stop-and-Wait (better bandwidth utilization).
• Disadvantages:
• Wastes bandwidth by retransmitting correctly received frames.
• Requires buffering at the sender but not at the receiver.
• Example:
• If frames 1, 2, 3, 4 are sent, but frame 2 is lost:
• Receiver discards 3 & 4 (even if correct).
• Sender retransmits 2, 3, 4.

5
 • 1.3 Selective Repeat ARQ
• How it Works:
• Only lost or corrupted frames are retransmitted.
• The receiver buffers out-of-order frames and sends NAK (Negative ACK) for missing ones.
• The sender retransmits only the requested frame.
• Advantages:
• Most efficient ARQ (no unnecessary retransmissions).
• Better for high-error-rate networks.
• Disadvantages:
• Complex implementation (requires buffering at both sender and receiver).
• Higher overhead due to individual ACKs/NAKs.
• Example:
• If frames 1, 2, 3, 4 are sent, but frame 2 is lost:
• Receiver buffers 3 & 4 and sends NAK for 2.
• Sender retransmits only frame 2.
6
 High-Level Data Link Control (HDLC)

HDLC basically provides reliable delivery of data frames over a

network or communication link. HDLC provides various operations
such as framing, data transparency, error detection, and correction,
and even flow control. Primary stations simply transmit commands
that contain address of secondary stations. The secondary station
then simply transmits responses that contain the primary address.

7
 High-Level Data Link Control (HDLC)
HDLC is a bit - oriented protocol where each frame contains up to six fields. The
structure varies according to the type of frame. The fields of a HDLC frame are −
• Flag − It is an 8-bit sequence that marks the beginning and the end of the frame. The
bit pattern of the flag is 01111110.
• Address − It contains the address of the receiver. If the frame is sent by the primary
station, it contains the address(es) of the secondary station(s). If it is sent by the
secondary station, it contains the address of the primary station. The address field
may be from 1 byte to several bytes.
• Control − It is 1 or 2 bytes containing flow and error control information.
• Payload − This carries the data from the network layer. Its length may vary from one
network to another.
• FCS − It is a 2 byte or 4 bytes frame check sequence for error detection. The standard
code used is CRC (cyclic redundancy code)

8
 High-Level Data Link Control (HDLC)

Types of HDLC Frame

There are three types of HDLC frames. The type of frame is determined by the control field of the frame −

I-frame − I-frames or Information frames carry user data from the network layer. They also include flow and error
control information that is piggybacked on user data. The first bit of control field of I-frame is 0.
S-frame − S-frames or Supervisory frames do not contain information field. They are used for flow and error control
when piggybacking is not required. The first two bits of control field of S-frame is 10.
U-frame − U-frames or Un-numbered frames are used for myriad miscellaneous functions, like link management. It
may contain an information field, if required. The first two bits of control field of U-frame is 11.
9
 High-Level Data Link Control (HDLC)

10
2.2 HDLC Frame Types
1.Information (I-Frames):
1. Carries user data.
2. Includes sequence numbers for flow control.
2.Supervisory (S-Frames):
1. Used for ACKs, NAKs, and flow control.
2. Examples:
1. RR (Receive Ready): ACK with next expected frame.
2. RNR (Receive Not Ready): Pauses transmission.
3. REJ (Reject): Requests retransmission (Go-Back-N).
3.Unnumbered (U-Frames):
1. Used for link setup, teardown, and control.
2. Examples:
1. SABM (Set Asynchronous Balanced Mode): Establishes connection.
2. DISC (Disconnect): Terminates connection.
2.3 HDLC Operational Modes
4.Normal Response Mode (NRM):
2. Used in primary-secondary setups (e.g., mainframe-terminals).
3. Secondary devices transmit only when polled.
5.Asynchronous Balanced Mode (ABM):
2. Peer-to-peer communication (both devices can initiate transmission).
11 3. Used in PPP.
 Point-to-Point Protocol (PPP)

PPP is a data link layer protocol used for direct connections (e.g., dial-up, DSL).
3.1 PPP Frame Format

12
 3.2 PPP Phases of Operation
1.Link Establishment (LCP):
1. Negotiates authentication, compression, and error detection.
2. Uses LCP packets (Configure-Request, Configure-Ack, Terminate).
2.Authentication (Optional):
1. PAP (Password Authentication Protocol): Plaintext credentials.
2. CHAP (Challenge-Handshake Protocol): Encrypted challenge-response.
3.Network Layer Configuration (NCP):
1. Assigns IP addresses (using IPCP for IPv4).
4.Link Termination:
1. Sent when the connection is closed.

13
 Multiple Access Protocols
4.1 Random Access (Contention-Based)
Random access methods allow stations to transmit data without centralized control, leading to possible collisions. These are best for bursty
traffic (irregular transmissions).
1.1 Pure ALOHA
•How it Works:
• Stations transmit whenever they have data.
• If two stations transmit simultaneously → collision occurs.
• After a collision, stations wait for a random backoff time before retransmitting.
•Advantages:
• Simple to implement.
• No need for synchronization.
•Disadvantages:
• Low efficiency (18%) due to high collision probability.
•Example: Early wireless networks.
1.2 Slotted ALOHA
•Improvement over Pure ALOHA:
• Time is divided into fixed slots.
• Stations can transmit only at the start of a slot.
•Advantages:
• Higher efficiency (36%) than Pure ALOHA.
•Disadvantages:
• Requires synchronization.
• Still has collisions if multiple stations transmit in the same slot.
•Example: Satellite communication.
14
1.3 CSMA (Carrier Sense Multiple Access)
•Principle: "Listen before talk" – stations check if the medium is free before transmitting.
Types of CSMA:
1.1-Persistent CSMA:
1. If the channel is idle, transmit immediately.
2. If busy, keep sensing until idle.
3. High collision probability if multiple stations wait.
2.Non-Persistent CSMA:
1. If the channel is busy, wait for a random time before sensing again.
2. Reduces collisions but introduces higher delays.
3.p-Persistent CSMA:
1. If the channel is idle, transmit with probability p, or defer with (1-p).
2. Used in Wi-Fi (CSMA/CA).

15
CSMA/CD (Collision Detection)
•Used in Ethernet (wired LANs).
•How it Works:
• Stations detect collisions while transmitting.
• If a collision is detected, they stop transmission and send a jam signal.
• Retransmit after a random backoff (Binary Exponential Backoff).
•Example: Traditional Ethernet (10BASE5, 10BASE2).
CSMA/CA (Collision Avoidance)
•Used in Wi-Fi (wireless LANs) since collisions cannot be detected reliably.
•How it Works:
• DIFS (DCF Interframe Space): Waits for a short idle period before transmitting.
• RTS/CTS (Request-to-Send / Clear-to-Send): Optional handshake to reserve the channel.
• NAV (Network Allocation Vector): Virtual carrier sensing to inform other stations of transmission
duration.
•Example: IEEE 802.11 (Wi-Fi).

16
2. Controlled Access Protocols
Controlled access methods avoid collisions by allowing stations to transmit only when permitted.
2.1 Polling
•How it Works:
• A master device (controller) polls slave devices one by one.
• Slaves transmit only when polled.
•Advantages:
• No collisions.
• Good for priority-based systems.
•Disadvantages:
• High overhead (polling messages).
• Single point of failure (master).
•Example: Bluetooth (Piconet), mainframe-terminal networks.
2.2 Token Passing
•How it Works:
• A special frame (token) circulates in the network.
• Only the station holding the token can transmit.
• After transmission, the token is passed to the next station.
•Advantages:
• No collisions.
• Fair access (each station gets a turn).
•Disadvantages:
• Token overhead (if lost, a new one must be generated).
• Latency in large networks.
•Examples:
• Token Ring (IEEE 802.5)
17 • FDDI (Fiber Distributed Data Interface)
3. Channelization (Channel Partitioning)
Channelization divides the bandwidth into separate channels to avoid interference.
3.1 FDMA (Frequency Division Multiple Access)
•How it Works:
• The frequency band is divided into sub-channels.
• Each station gets a fixed frequency band.
•Advantages:
• No collisions.
• Suitable for analog signals.
•Disadvantages:
• Wastes bandwidth if a station is idle.
• Guard bands needed to prevent interference.
•Examples:
• FM/AM radio.
• 1G/2G cellular networks (AMPS, GSM).

18
3.2 TDMA (Time Division Multiple Access)
•How it Works:
• Time is divided into fixed slots.
• Each station transmits in its assigned slot.
•Advantages:
• Efficient for digital signals.
• No frequency interference.
•Disadvantages:
• Requires synchronization.
• Wastes slots if a station has no data.
•Examples:
• GSM (2G cellular).
• TDM in leased lines.
3.3 CDMA (Code Division Multiple Access)
•How it Works:
• All stations transmit simultaneously but with unique codes.
• The receiver uses the code to filter out unwanted signals.
•Advantages:
• No time/frequency division needed.
• Resistant to interference.
•Disadvantages:
• Complex signal processing.
• Requires power control.
•Examples:
• 3G (UMTS, CDMA2000).
• GPS.
19
20