Introduction

This documentation presents an analytical exploration of networking principles, focusing on protocols, transmission mechanisms, and error handling strategies within the Data Link Layer. By examining protocols such as Stop-and-Wait ARQ and Sliding Window, the content outlines their operational logic, efficiency models, and applicability across different networking scenarios. Protocols for managing shared media, including ALOHA and CSMA, are critically examined, emphasizing their role in minimizing collision risks and ensuring optimal media access.

In-depth coverage is provided for controlled access methods like Polling, Reservation, and Token Passing, which regulate communication and enhance transmission efficiency. Further discussion on Ethernet-specific protocols, such as CSMA/CD, and wireless alternatives like CSMA/CA, highlights the trade-offs involved in choosing appropriate protocols for different network topologies. The mathematical models associated with these protocols are articulated to aid in understanding their efficiency and performance limitations.

The sections on error detection and framing detail essential mechanisms like parity checks, CRC, and bit stuffing, providing an examination of their utility in maintaining data integrity. Additional sections address advanced strategies such as Exponential Backoff and Token Reinsertion, offering insights into managing congestion and maintaining network fairness. Key metrics such as transmission delays, throughput, and bandwidth utilization are systematically introduced to quantify protocol efficiency.

This documentation serves as a reference for students, researchers, and practitioners, presenting theoretical foundations alongside real-world applications and computational examples. The structured presentation of topics and precise use of mathematical formulations facilitate a rigorous understanding of networking concepts and their practical implementations.

1. Data Link Layer

The Data Link Layer acts as a bridge between the physical medium and the network layer, responsible for reliable data transfer over a shared medium. This layer ensures data is properly framed, transmitted, and received without conflicts or errors.

1.1 Core Functions of the Data Link Layer

• Medium Access Control: Controls access to the shared transmission medium, preventing data collisions.
• Error Detection and Handling: Identifies and manages errors during data transmission, requesting retransmission if necessary.
• Flow Control: Coordinates data transmission rates to match the processing speeds of communicating devices.
• Framing: Encapsulates network layer packets into frames for transmission.

1.1.1 Sub-layers: Logical Link Control and Media Access Control

The Data Link Layer is divided into two sub-layers:

• Logical Link Control (LLC): Handles flow control and error notifications.
• Media Access Control (MAC): Determines which devices can access the medium, with each device identified by a unique MAC address.

1.2 Addressing with MAC Addresses

Every network interface card (NIC) or Wi-Fi card is assigned a unique 12-digit alphanumeric MAC address. MAC addresses help identify the destination device on a shared medium.

Example MAC Address: F0:18:98:97:F2:59
            

Devices ignore frames that do not match their MAC address, ensuring data reaches the intended recipient only.

1.3 Layer 2 Switches

Layer 2 switches operate at the data link layer, directing frames based on MAC addresses. These switches help reduce congestion and extend the network’s reach.

1.4 Transmission and Propagation Delays

Transmission and propagation delays impact data transfer efficiency:

• Transmission Delay (T_t): Time taken to place a frame onto the medium.

  
  Tt = L / B
  Where L = Frame size (bits), B = Bandwidth (bits per second)
              

• Propagation Delay (T_p): Time for a signal to travel through the medium.

  
  Tp = D / V
  Where D = Distance (meters), V = Signal velocity (meters/second)
              

1.5 Practical Protocols and Concepts

Protocols define how devices manage flow control, error detection, and media access. Common examples include:

• Flow Control: Adjusts transmission speed to prevent overflow.
• Multiple Access Protocols: Determines access rules for shared media (e.g., CSMA/CD).
• Error Control: Ensures data integrity with mechanisms like parity bits or CRC.

1.6 Bandwidth Conventions

In data networks, two conventions are used:

• Data: Measured in powers of 2 (e.g., 1 KB = 1024 bytes).
• Bandwidth: Measured in decimal units (e.g., 1 Kbps = 1000 bits/second).

Understanding these conventions helps avoid calculation errors when determining delays or transmission rates.

1.7 Conclusion of Concepts

By coordinating transmission timing, managing access, and implementing error checks, the Data Link Layer ensures seamless communication across shared networks. Practical tools like Wireshark allow users to observe these protocols in real-time, enhancing comprehension and troubleshooting skills.

2. Stop-and-Wait ARQ Protocol

The Stop-and-Wait ARQ is a flow control protocol ensuring that data is sent and acknowledged frame-by-frame. Each frame transmission must be acknowledged by the receiver before the next frame can be sent. This method simplifies communication by alternating between sending data and waiting for acknowledgments.

2.1 Basic Working of Stop-and-Wait ARQ

• Binary Variables: Both the sender and receiver maintain binary variables (S and R) to track frame numbers (0 and 1 alternately).
• Frame Transmission: Sender transmits frame 0 and waits for acknowledgment (ACK1). Once received, it switches to frame 1.
• Acknowledgment Mechanism: After receiving a frame, the receiver sends an acknowledgment with the number of the next expected frame (e.g., ACK1 for frame 0).

2.1.1 Flow Control Logic

The protocol alternates between sending frames 0 and 1. If no acknowledgment is received within a defined timeout, the sender retransmits the same frame.

Send Frame 0 -> Wait for ACK1
If ACK1 received: Send Frame 1
If no ACK1 (timeout): Retransmit Frame 0

2.2 Efficiency Calculation

Efficiency of Stop-and-Wait ARQ is measured as the ratio of useful time (transmission time) to the total time:

η = Tt / (Tt + 2 * Tp)
Where Tt = Transmission Time, Tp = Propagation Time

Efficiency (η) can also be expressed in terms of A = T_p / T_t:

η = 1 / (1 + 2A)

2.3 Throughput Calculation

Throughput measures the number of bits transmitted per second:

Throughput = L / (Tt + 2 * Tp)
Where L = Number of Bits in Frame

It indicates the effective bandwidth utilization of the protocol.

2.4 Handling Errors and Timeouts

If a frame or acknowledgment is lost, the protocol uses a timeout mechanism to retransmit the frame:

• Lost Data Frame: If the receiver does not receive the frame, it won’t send an acknowledgment, prompting the sender to resend the frame after the timeout.
• Lost Acknowledgment: If an acknowledgment is lost, the sender resends the previous frame, which the receiver discards but acknowledges with the expected frame number.

2.4.1 Example of Timeout Handling

Frame 0 Sent -> No ACK1 Received -> Timer Expires -> Retransmit Frame 0

2.5 Summary of Concepts

Stop-and-Wait ARQ is a simple yet effective protocol for error control. It ensures reliable data transfer through acknowledgments and retransmissions. While it is easy to implement, its efficiency can decrease over long propagation delays, making it suitable for low-latency communication environments.

3. Delayed Acknowledgement in Stop-and-Wait ARQ

Delayed acknowledgments occur when the acknowledgment (ACK) takes longer than expected to reach the sender, potentially leading to retransmissions and duplicate frames.

3.1 How Delayed Acknowledgement Works

• The sender transmits frame 0 and expects ACK1 within a set timeout.
• The receiver receives frame 0, processes it, and sends ACK1.
• Due to the delayed ACK1, the sender times out and retransmits frame 0, unaware that the receiver is waiting for frame 1.
• The receiver discards the duplicate frame 0 and re-sends ACK1, signaling the need for frame 1.

3.1.1 Handling Delayed Acknowledgements

If the sender receives the delayed ACK1 after a retransmission, it uses the latest ACK to confirm that frame 0 was successfully received and moves on to sending frame 1. Duplicate ACKs are ignored.

3.2 Piggybacking Concept

Piggybacking combines data and acknowledgments into a single frame in half-duplex communication channels, enhancing efficiency by reducing the number of separate ACK frames.

Data Frame: Host1 -> Host2 (with ACK from Host2 to Host1 piggybacked)

Both hosts act as senders and receivers, alternating data and acknowledgment piggybacks within the same frames to optimize transmission.

3.3 Solving Packet Loss Scenarios

3.3.1 Example: Packet Loss Every 4th Packet

If every 4th packet is lost, the sender must retransmit each lost packet, increasing the total number of transmissions.

Sent: 1, 2, 3, (4 lost) -> Resend 4
Sent: 5, 6, 7, (8 lost) -> Resend 8
Sent: 9, 10 -> (10 lost) -> Resend 10
Total Transmissions: 13 packets

3.4 Computing Transmissions with Error Probability

If the error probability is given, the total number of transmissions required can be calculated using geometric progression.

Total Transmissions = n / (1 - P)
Where n = Number of packets, P = Error Probability

For example, if 1000 packets are sent with an 80% error probability:

Total Transmissions = 1000 / (1 - 0.8) = 5000 packets

3.5 Channel Capacity

The capacity of a channel measures the maximum number of bits that can be present on the wire at any given moment.

Capacity = Bandwidth * Propagation Delay

If the bandwidth is 2.1 Mbps and propagation delay is 1 second, the capacity is:

Capacity = 2.1 * 10^6 bits = 2100 frames (with frame size 1000 bits)

3.6 Efficiency in Stop-and-Wait ARQ

The efficiency of Stop-and-Wait ARQ can be expressed as:

Efficiency (η) = 1 / (1 + 2 * A)
Where A = Propagation Delay / Transmission Time

If the transmission time (T_t) and propagation time (T_p) are both 1 millisecond, then:

η = 1 / (1 + 2 * 1) = 1/3

3.7 Optimizing with Sliding Window Protocols

Stop-and-Wait ARQ transmits one frame at a time, limiting efficiency. Sliding Window Protocols improve efficiency by sending multiple frames without waiting for individual acknowledgments.

These protocols will be discussed in subsequent sections to address the limitations of Stop-and-Wait ARQ.

4. Sliding Window Protocols

Sliding Window Protocols aim to improve the efficiency of data transmission by allowing multiple packets to be sent before waiting for cumulative acknowledgments. This section explores the core concepts of sliding window protocols and how they address the limitations of the Stop-and-Wait ARQ.

4.1 Key Concept of Sliding Window Protocols

• Instead of sending a single packet and waiting for its acknowledgment, multiple packets are transmitted within a *window* before waiting for an acknowledgment.
• The size of the window determines the number of packets that can be sent before stopping for acknowledgment.
• Acknowledgments can be cumulative, meaning one acknowledgment confirms the successful receipt of multiple frames.

4.1.1 Sequence Numbers and Windows

Each packet in sliding window protocols is assigned a sequence number. If the sequence number uses m bits, the total sequence numbers range from 0 to \(2^m - 1\).

If m = 2, sequence numbers = 0, 1, 2, 3 (repeating in cycles)

The sliding window shifts forward with each acknowledgment received, hence the name 'sliding window'.

4.2 Sender and Receiver Window Size

The size of the sender’s window is denoted as WS. The maximum window size is constrained by:

WS ≤ min(2^m, 1 + 2A)
Where A = Propagation Delay / Transmission Time

Each time a cumulative acknowledgment is received, the window slides, and new frames are sent within the updated window.

4.3 Problem: Window Size and Efficiency

Given: Propagation Delay = 49.5 ms, Transmission Time = 1 ms

1 + 2A = 1 + 2 * (49.5 / 1) = 100
Maximum Window Size = min(2^m, 100)

If 5 bits are used for the sequence number (2^5 = 32):
Window Size = 32
Efficiency = Window Size / (1 + 2A) = 32 / 100 = 32%

Thus, increasing the window size increases efficiency by transmitting more frames simultaneously.

4.4 Efficiency and Throughput Calculation

The efficiency \( \eta \) of a sliding window protocol is calculated as:

$$\eta = \frac{WS}{1 + 2A}$$

The throughput or effective bandwidth is:

Throughput = η * Bandwidth

In sliding window protocols, the goal is to maximize \(WS\) while keeping it within the allowed capacity to increase throughput.

4.5 Types of Sliding Window Protocols

• Go-Back-N Protocol: The sender sends multiple frames but must resend all frames after a lost frame.
• Selective Repeat Protocol: Only the lost frames are retransmitted, improving efficiency over Go-Back-N.

Selective Repeat is widely used in practical scenarios due to its higher efficiency and bandwidth utilization.

4.6 Practical Example

If the channel capacity is 100 packets and 7 bits are available for sequence numbering:

Max Window Size = min(2^7, 100) = 100
If WS = 32, Efficiency = 32 / 100 = 32%

This demonstrates the trade-off between the available sequence bits and channel capacity in sliding window protocols.

5. Go-Back-N Protocol

The Go-Back-N (GBN) protocol is a practical implementation of the sliding window concept, aiming to enhance transmission efficiency by allowing the sender to transmit multiple frames without waiting for individual acknowledgments.

5.1 Overview of Go-Back-N Protocol

• Sender’s Window: Maintains a sliding window of size WS, allowing the sender to send multiple frames before waiting for an acknowledgment.
• Receiver’s Window: The window size at the receiver is always 1, meaning the receiver only accepts frames in sequence and discards out-of-order frames.
• Cumulative Acknowledgment: Acknowledgments are cumulative, indicating that all frames up to a specific sequence number have been received successfully.

5.1.1 Window Size and Sequence Numbers

The maximum sender window size is constrained by the number of sequence bits \(m\):

WS ≤ 2^m - 1

This prevents ambiguous frame re-acceptance due to repeated sequence numbers.

5.2 How Go-Back-N Works

• Sender sends multiple frames within the window.
• Receiver expects frames in order (starting with 0).
• If a frame is lost or arrives out of order, the receiver discards all subsequent frames.
• Sender starts a timer for each frame and retransmits all frames within the window if a timeout occurs.

5.3 Handling Lost Frames and Timeouts

• Lost Frame: If a frame is lost, the receiver discards any following frames and waits for the missing frame.
• Timeout: If the sender's timer expires, it retransmits all frames within the window, starting from the first unacknowledged frame.
• Delayed Acknowledgment: If an acknowledgment arrives after timeout, the sender ignores it and proceeds with the retransmissions.

5.3.1 Example: Lost Frame

• Sender sends frames 0, 1, 2.
• Frame 2 is lost.
• Receiver discards frame 3 since it was expecting frame 2.
• Sender times out and resends frames 2 and 3.

This shows how Go-Back-N handles out-of-order frames by discarding and retransmitting from the missing frame.

5.4 Efficiency of Go-Back-N Protocol

The efficiency \(\eta\) of the Go-Back-N protocol is defined as:

$$\eta = \frac{WS}{1 + 2A}$$

Where:

• WS: Sender’s window size.
• A: Propagation delay to transmission time ratio.

The protocol's efficiency decreases when frames are lost frequently due to unnecessary retransmissions.

5.5 Example Problem: Calculating Frames Transmitted

Window Size = 3, Total Frames = 10, Every 5th Frame Lost

• Send frames 0, 1, 2 (ACK received)
• Send frames 3, 4, 5 (frame 5 lost, no ACK)
• Resend 3, 4, 5 (ACK received)
• Continue for remaining frames with similar pattern.

Total Frames Transmitted = 18

This example illustrates how unnecessary retransmissions occur when frames are lost, leading to lower efficiency.

5.6 Why Go-Back-N Uses WS <= 2^m - 1

To avoid ambiguous acceptance, Go-Back-N restricts the sender's window size to 2^m - 1:

• If the window size equals 2^m, the receiver may incorrectly accept retransmitted frames with the same sequence number.
• This leads to data corruption and loss of frame order.

Using WS <= 2^m - 1 ensures that all frames are correctly acknowledged and retransmitted only when necessary.

5.7 Conclusion

Go-Back-N is an efficient protocol for data transmission but suffers from redundant retransmissions when frames are lost. In the next section, we will explore the Selective Repeat protocol, which addresses these issues by retransmitting only the lost frames.

6. Selective Repeat Protocol (SR)

The Selective Repeat protocol (SR) is an enhanced sliding window protocol designed to avoid redundant retransmissions by only retransmitting the specific frames that are lost or corrupted. It optimizes bandwidth usage by sending individual negative acknowledgments (NAK) for problematic frames.

6.1 Overview of Selective Repeat Protocol

• Sender and Receiver Windows: Both the sender and receiver windows have the same size, with width > 1.
• Selective Retransmission: Only lost or corrupted frames are retransmitted, minimizing unnecessary bandwidth usage.
• Negative Acknowledgments (NAK): Used to explicitly notify the sender about missing frames.

6.1.1 Key Differences from Go-Back-N

• In SR, the receiver window can accept out-of-order frames and store them in a buffer.
• Go-Back-N retransmits all frames after a lost one, while SR retransmits only the missing frames.

6.2 How Selective Repeat Works

• Sender sends frames 0, 1.
• Receiver receives and stores both frames in a buffer, then sends an acknowledgment (ACK) for both.
• Sender slides its window and sends frames 2, 3.
• Frame 2 is lost, but frame 3 is accepted and stored.
• Receiver sends a NAK for frame 2.
• Sender retransmits frame 2.
• Receiver sends an ACK for frame 2, and both windows slide forward.

6.3 Handling Lost Acknowledgments

• If an acknowledgment is lost, the sender will wait for a NAK or a timeout to detect the problem.
• The sender retransmits only the required frame, avoiding the inefficiency of resending entire windows.

6.4 Window Size Constraints in SR

The maximum window size is constrained to avoid frame sequence ambiguity:

WS ≤ (2^m) / 2

Where m is the number of bits used for sequence numbers. This ensures no erroneous re-acceptance of old frames occurs.

6.5 Efficiency of Selective Repeat Protocol

The efficiency of SR is defined similarly to Go-Back-N:

$$\eta = \frac{WS}{1 + 2A}$$

Where:

• WS: Window size.
• A: Propagation delay to transmission time ratio.

The use of selective retransmissions helps optimize bandwidth in scenarios with frequent errors.

6.6 Comparison with Other Protocols

6.7 Implementation Considerations

• Selective Repeat requires more memory and computational resources than Go-Back-N due to the need to buffer out-of-order frames.
• It is ideal for error-prone networks, such as wireless networks, where minimizing retransmissions is crucial.
• Modern network interface cards (NICs) often have built-in buffers to handle selective repeat efficiently.

6.8 Conclusion

The Selective Repeat protocol strikes a balance between efficiency and complexity, making it suitable for networks with moderate bandwidth and higher error rates, such as wireless networks. While its implementation is more complex, the benefits of reduced retransmissions and better bandwidth utilization make it a preferred choice in many practical scenarios.

7. Multiple Access Protocols (Media Access Protocols)

Multiple Access Protocols (MAP), also called Media Access Protocols, manage how multiple stations (or hosts) share a communication medium to avoid collisions. These protocols ensure smooth data transmission through a shared medium, preventing interference and corrupted data.

7.1 Types of Multiple Access Protocols

MAPs are broadly classified into three categories:

• Channelization Protocols: Divide the medium using frequency, time, or code.
• Controlled Access Protocols: Access is coordinated to avoid collisions.
• Random Access Protocols: Stations transmit without pre-coordination, using strategies to handle collisions.

7.2 Channelization Protocols

Channelization protocols split the communication medium based on different factors. Below are three key types:

7.2.1 Frequency Division Multiple Access (FDMA)

FDMA divides the available frequency range into non-overlapping intervals, each allocated to a station. This prevents overlap and ensures efficient transmission.

Example:
Total Frequency: 100 MHz to 1000 MHz
Station 1: 100-199 MHz
Station 2: 200-299 MHz
...
Station 9: 900-999 MHz

This approach ensures that each station transmits in a unique frequency range, avoiding collisions.

7.2.2 Time Division Multiple Access (TDMA)

TDMA allocates time intervals to stations, allowing them to transmit one at a time in a cyclical order. Each station can transmit only during its assigned time slot.

Efficiency:
η = TT / (TT + TP)
Where:
TT = Transmission time
TP = Propagation time

A drawback of TDMA is wasted slots, which occur when a station has no data to send during its assigned slot, reducing overall efficiency.

7.2.3 Code Division Multiple Access (CDMA)

CDMA assigns a unique code to each station. All stations transmit their data simultaneously, with each data frame multiplied by the station's code. The receiver uses these codes to decode the data meant for it.

Signal on Bus: 
C1D1 + C2D2 + C3D3 + C4D4

CDMA is widely used in telecommunications due to its ability to handle multiple simultaneous transmissions without collisions.

7.3 Mathematical Model for TDMA Efficiency

The efficiency of TDMA can be derived using the following formula:

$$\eta = \frac{TT}{TT + TP} = \frac{1}{1 + A}$$

Where \(A = \frac{TP}{TT}\) represents the ratio of propagation time to transmission time.

The throughput, or effective bandwidth, is calculated as:

$$\text{Throughput} = \eta \times B$$

Where \(B\) is the total bandwidth.

7.4 Comparison of Channelization Protocols

7.5 Practical Example for TDMA

TT = 1 ms
TP = 1 ms
η = 1 / (1 + 1) = 0.5 (50%)
Bandwidth (B) = 4 Mbps

Throughput = η × B = 2 Mbps

Number of stations that can be supported:
Total throughput / Required throughput per station = 2 Mbps / 1 Kbps = 2000 stations

This calculation shows that with a throughput of 2 Mbps, 2000 stations, each requiring 1 Kbps, can be connected.

7.6 Summary

Multiple Access Protocols are crucial for managing shared media in computer networks and telecommunications. FDMA, TDMA, and CDMA offer distinct ways to divide the medium based on frequency, time, and code, respectively. Each has its unique advantages and drawbacks, making them suitable for different use cases such as radio, satellite, and mobile communications.

8. Controlled Access Protocols

Controlled access protocols ensure that access to the shared medium is regulated to avoid collisions. These protocols involve a central authority or logic to manage communication, unlike random access protocols. Let’s explore three key controlled access strategies: Polling, Reservation, and Token Passing.

8.1 Polling Protocol

In the polling protocol, a master node or controller manages communication. The master polls each host sequentially, asking if it has data to send. If a host has data, it sends it; otherwise, it sends a negative acknowledgment.

This protocol suits star topologies but can also be implemented in bus topologies.

8.1.1 Polling Process

• Master sends poll packet to Host 1.
• If Host 1 has no data: sends negative acknowledgment.
• If Host 1 has data: sends it to the master.
• Master forwards the data to the destination host (if needed).
• Process repeats for the next host in the cycle.

8.1.2 Advantages and Drawbacks

• Prioritization: The master can poll important hosts more frequently.
• Bandwidth Utilization: Low, due to time spent on polling and acknowledgments.
• Single Point of Failure: If the master fails, the entire network stalls.

8.2 Reservation Protocol

The reservation protocol optimizes time division by allowing hosts to indicate if they have data to send before the transmission begins. A reservation frame is used to gather this information.

8.2.1 Reservation Process

• A reservation frame with mini slots is broadcasted.
• Each host places a bit in its allocated mini slot:
• 1: Host wants to transmit.
• 0: Host has no data to transmit.
• Hosts transmit in the order indicated by the reservation frame.
• The process repeats with a new reservation frame.

8.2.2 Key Features

• Reduces wasted slots compared to TDMA by only allowing hosts with data to transmit.
• Some overhead is incurred by the reservation frame but is manageable with few hosts.

8.3 Token Passing Protocol

In the token passing protocol, a token gives permission to transmit. Only the host holding the token can send data. The token is passed along a logical ring, ensuring orderly transmission without collisions.

8.3.1 Token Passing Process

• Host 1 holds the token and sends data to Host 3.
• Data flows through intermediate hosts (e.g., Host 2).
• Host 3 copies the data and forwards it.
• When the data returns to Host 1, it is discarded, confirming delivery.
• If Host 1 has more data, it sends it; otherwise, it passes the token to Host 2.
• The process repeats with the token moving cyclically among the hosts.

8.3.2 Advantages of Token Passing

• No Acknowledgments Required: The returning packet confirms successful delivery.
• Efficient Broadcasting: Suitable for sending data to all hosts in the network.
• No Collisions: Only the host with the token can transmit.

8.3.3 Challenges

• Token Management: Ensuring the orderly passing of tokens requires careful logic.
• Recovery from Token Loss: If a token is lost, it must be regenerated.

8.4 Comparison of Controlled Access Protocols

8.5 Summary

Controlled access protocols regulate communication to avoid collisions and ensure orderly data transmission. Polling, reservation, and token passing offer different strategies with unique advantages and drawbacks. Polling provides control but risks inefficiency. Reservation protocols optimize time division by eliminating wasted slots. Token passing ensures collision-free transmission and facilitates broadcasting, though it requires careful token management.

9. Efficiency of Token Passing Protocols

Token passing schemes are a form of controlled access protocol where only the host holding the token can transmit data. To analyze their efficiency, we need to compute the key parameters involved in token passing systems and understand the difference between Delayed Token Reinsertion (DTR) and Early Token Reinsertion (ETR).

9.1 Concept of k-bit Delay

In computer networks, the term k-bit delay is often used to represent delay. Here’s how it is computed:

• Bandwidth (B): Number of bits transmitted per second.
• Velocity (V): Speed of signal propagation in meters per second.
• k-bit Delay: Delay in transferring k bits, represented as $k / B$ seconds.
• k-bit Distance: The distance traveled by the signal in $k / B \cdot V$ meters.

9.2 Key Metrics in Token Passing

• Ring Latency: Total time for one bit to travel through the ring.

  $$\text{Ring Latency} = \frac{D}{V} + \frac{n \cdot k}{B}$$

  Where:
  • D: Total distance in meters.
  • V: Signal velocity (meters per second).
  • n: Number of stations.
  • k: Bit delay per station.
• Token Holding Time (THT): Time a host holds the token.
• Cycle Time: Time for the token to travel through the entire cycle and return to the origin.

9.3 Efficiency of Token Passing

The formula for efficiency is:

$$\text{Efficiency} = \frac{\text{Useful Time}}{\text{Cycle Time}}$$

Assuming each station sends one frame per cycle, the efficiency becomes:

$$\text{Efficiency} = \frac{n \cdot T_t}{T_p + n \cdot THT}$$

• $n$: Number of stations.
• $T_t$: Transmission time for one frame.
• $T_p$: Propagation delay ($D / V$).
• $THT$: Token holding time.

9.4 Delayed Token Reinsertion (DTR)

In DTR, a host holds the token until its packet returns. The token holding time is:

$$THT_{DTR} = T_t + \text{Ring Latency}$$

The efficiency of DTR is:

$$\eta_{DTR} = \frac{1}{1 + (n - 1) \cdot A}$$

9.5 Early Token Reinsertion (ETR)

In ETR, the token is released immediately after the packet is sent, allowing multiple packets to coexist on the ring. The token holding time is:

$$THT_{ETR} = T_t$$

The efficiency of ETR is:

$$\eta_{ETR} = \frac{1}{1 + \frac{A}{n}}$$

9.6 Comparison: DTR vs. ETR

9.7 Summary

Both DTR and ETR provide mechanisms to manage token holding and improve efficiency. While ETR offers higher efficiency by allowing multiple packets to traverse the ring simultaneously, it may result in lower reliability. DTR, on the other hand, ensures higher reliability by allowing only one packet at a time on the ring, reducing the chance of collisions.

10. ALOHA Protocol: An Introduction to Random Access Protocols

The ALOHA protocol, developed at the University of Hawaii, is one of the earliest random access protocols. It was originally designed for wireless communication but can also be applied to wired networks. ALOHA enables hosts to transmit data without coordination, introducing the possibility of collisions.

10.1 Types of ALOHA Protocols

• Pure ALOHA: Hosts transmit whenever they have data to send, without waiting or coordination.
• Slotted ALOHA: Hosts are restricted to sending only at predefined time slots to reduce the chances of collisions.

10.2 Pure ALOHA Protocol

The core idea is simple: A host sends its frame as soon as it is ready. However, collisions can occur if two hosts transmit simultaneously. If a frame collides, the sender waits for a random backoff time and retransmits after the timeout period.

Collisions: Collisions occur when two frames overlap on the time axis. If an overlap occurs, the data becomes corrupted, requiring retransmission.

10.2.1 Vulnerable Time in Pure ALOHA

The vulnerable time is the duration when a frame is at risk of collision:

$$\text{Vulnerable Time} = 2 \cdot T_t$$

This occurs because the frame can collide if another frame starts transmission within the duration before or after the original frame.

10.2.2 Efficiency of Pure ALOHA

The efficiency of pure ALOHA, derived using Poisson distribution, is given by:

$$\eta_{\text{Pure ALOHA}} = G \cdot e^{-2G}$$

• G: Number of hosts trying to transmit within a time slot of length $T_t$.

Maximum Efficiency:

The maximum efficiency occurs when $G = 0.5$, giving:

$$\eta_{\text{Pure ALOHA Max}} = 0.184 \, (18.4\%)$$

10.3 Slotted ALOHA Protocol

In slotted ALOHA, time is divided into fixed slots of duration $T_t$. Hosts can only transmit at the start of a time slot, reducing the chance of collisions.

10.3.1 Vulnerable Time in Slotted ALOHA

The vulnerable time in slotted ALOHA is reduced to:

$$\text{Vulnerable Time} = T_t$$

10.3.2 Efficiency of Slotted ALOHA

The efficiency of slotted ALOHA is given by:

$$\eta_{\text{Slotted ALOHA}} = G \cdot e^{-G}$$

Maximum Efficiency:

Using calculus, we find the maximum efficiency when $G = 1$:

$$\eta_{\text{Slotted ALOHA Max}} = \frac{1}{e} \approx 0.368 \, (36.8\%)$$

10.4 Comparison of Pure ALOHA and Slotted ALOHA

10.5 Summary

The ALOHA protocol introduced a novel approach to random access communication. While pure ALOHA is simpler, it has lower efficiency due to a larger vulnerable time. Slotted ALOHA improves efficiency by reducing the window of collision but requires synchronization among hosts. Both protocols laid the foundation for modern wireless communication systems.

11. Carrier Sense Multiple Access (CSMA): A Group of Protocols

Carrier Sense Multiple Access (CSMA) protocols aim to improve the efficiency of networks by sensing the medium before transmitting data, unlike ALOHA. The term "carrier" refers to the communication medium. Before transmitting, a host checks if the medium is busy with other transmissions. If busy, it waits before attempting again. Multiple CSMA variants exist, each enhancing collision management in unique ways.

11.1 Variants of CSMA Protocols

• One-Persistent CSMA: Transmits as soon as the medium is sensed free, with a probability of 1.
• Non-Persistent CSMA: Waits for a random period if the medium is busy, reducing continuous sensing.
• P-Persistent CSMA: Introduces probabilistic transmission at the beginning of time slots, useful in wireless networks.

11.2 One-Persistent CSMA

In one-persistent CSMA, the host transmits its frame immediately if the medium is idle. If the medium is busy, it continuously senses it until it becomes free. Collisions may occur due to propagation delay, as hosts can sense an idle medium while another frame is still in transit.

11.2.1 Key Characteristics

• Immediate transmission with probability 1 when medium is free.
• Continuous sensing if the medium is busy.
• Collisions occur due to propagation delay.

11.2.2 Handling Collisions

If a collision occurs, the sender waits for a random back-off time before sensing the medium again. The timeout mechanism ensures the host does not reattempt transmission too quickly.

11.3 Non-Persistent CSMA

This protocol avoids continuous sensing by waiting a random period before sensing the carrier again if the medium is busy. This reduces resource usage but introduces additional delay.

11.3.1 Key Characteristics

• Random wait period if medium is busy.
• Lower resource usage compared to one-persistent CSMA.
• Increased transmission delay.

11.4 P-Persistent CSMA

P-persistent CSMA works by slotting time and transmitting with a probability P at the start of each time slot. It is particularly useful in wireless networks to manage collision risks.

11.4.1 Key Characteristics

• Time-slotted transmission.
• Transmission with probability P, waiting otherwise.
• Reduced collisions due to randomized transmissions.

11.5 CSMA with Collision Detection (CSMA/CD)

CSMA/CD detects collisions during transmission. If a collision is detected, the transmission halts, and the host waits before retrying. This method is widely used in Ethernet networks.

11.5.1 Key Characteristics

• Collisions detected during transmission.
• Immediate halt upon collision detection.
• Random back-off period before reattempting.

flowchart TD
    A[Start Transmission] --> B{Carrier Idle?}
    B -- No --> A
    B -- Yes --> C[Transmit Frame]
    C --> D{Collision Detected?}
    D -- No --> E[Successful Transmission]
    D -- Yes --> F[Wait Random Time] --> A

11.6 CSMA with Collision Avoidance (CSMA/CA)

CSMA/CA, used in wireless LANs (IEEE 802.11), aims to avoid collisions entirely. It uses a Request to Send (RTS) and Clear to Send (CTS) mechanism to ensure that nodes do not transmit simultaneously.

11.6.1 RTS/CTS Mechanism

The RTS/CTS exchange ensures that a central access point (AP) confirms availability before allowing transmission, mitigating the hidden node problem.

flowchart TD
    A[Node A wants to transmit] --> B[Send RTS to AP]
    B --> C{CTS Received?}
    C -- Yes --> D[Transmit Data]
    C -- No --> E[Wait Random Time] --> B

11.7 Comparison of CSMA Variants

11.8 Conclusion

CSMA protocols play a crucial role in network communication by reducing collisions and improving efficiency. Depending on the network type, different CSMA variants offer tailored solutions to manage collision risks effectively, with CSMA/CA being widely used in wireless networks for collision avoidance.

12. Analysis of CSMA/CD (Carrier Sense Multiple Access with Collision Detection)

CSMA/CD is a protocol used in networks to detect and handle collisions during data transmission. This analysis explores key concepts, assumptions, and mathematical analysis for understanding the behavior and efficiency of CSMA/CD. It is commonly used in Ethernet networks where short distances make it effective.

12.1 Collision Detection Mechanism

The most popular strategy to detect a collision is by observing whether the sender receives a signal while it is still transmitting. If this happens, it is a clear indication that a collision has occurred.

12.1.1 Worst Case Collision Scenario

• If Host H1 sends the first bit, it takes propagation time (Tp) to reach Host H2.
• If H2 starts transmitting just before receiving H1’s bit, both transmissions will collide.
• The collided bit takes another Tp to return to H1.

In the worst-case scenario, collision detection takes 2Tp.

flowchart TD
    A[H1 sends first bit] --> B{H2 detects idle?}
    B -- Yes --> C[H2 sends its bit]
    C --> D[Collision occurs]
    D --> E[Collision travels back in Tp]

12.2 Mathematical Analysis

The frame size and transmission time must meet specific conditions to detect collisions effectively. The minimum frame size is calculated as:

$$L \geq \frac{2 \cdot D \cdot B}{V}$$

• L: Frame size (bits)
• D: Distance between hosts
• B: Bandwidth (bits per second)
• V: Velocity of signal in the medium

12.2.1 Example Calculation

If Tp is 1 millisecond and B is 1 Mbps, the minimum frame size required is:

$$L \geq 2 \cdot 1 \, ms \cdot 1 \, Mbps = 2000 \, bits$$

12.3 Efficiency of CSMA/CD

The efficiency of CSMA/CD is calculated as:

$$Efficiency = \frac{T_t}{T_t + 2 \cdot T_p \cdot C}$$

• Tt: Transmission time
• Tp: Propagation time
• C: Number of contention slots

12.3.1 Calculating Expected Collisions

The expected number of collisions, C, can be calculated using probability:

$$C \approx e \, (E = 2.718)$$

This means, on average, a packet may encounter e collisions before successful transmission.

12.4 Factors Affecting Efficiency

• Frame Size (L): Larger frames increase efficiency as the relative impact of collisions decreases.
• Distance (D): Increased distance leads to more collisions, decreasing efficiency. CSMA/CD is ideal for small networks (like LANs).

graph LR
    A[Increase in Frame Size] --> B[Higher Efficiency]
    C[Increase in Distance] --> D[Lower Efficiency]

This is why CSMA/CD works well in Ethernet networks but not in WANs or metropolitan networks.

12.5 Summary of Key Takeaways

• Collision detection takes 2Tp in worst-case scenarios.
• The minimum frame size must be large enough to allow collision detection.
• CSMA/CD is effective in Ethernet networks due to shorter distances and higher efficiency.
• On average, e attempts are needed for a successful transmission after collisions.

13. Exponential Backoff Algorithm in CSMA/CD

The exponential backoff algorithm plays a crucial role in handling repeated collisions in CSMA/CD networks by introducing a randomized waiting time after each collision. This reduces the probability of repeated collisions and ensures fair access to the medium.

13.1 Concept of Backoff Time

After detecting a collision, both hosts stop transmitting and wait for a random amount of time before attempting retransmission. This waiting time is called backoff time.

The challenge lies in ensuring that both hosts do not choose the same waiting time, which would lead to another collision. This is where the exponential backoff algorithm is applied.

13.2 Working of Exponential Backoff Algorithm

• For each packet, a collision number (n) is tracked, representing how many times the packet has collided.
• The waiting time for each host is calculated as:

  $$W = K \cdot \text{Time Slot}$$

• K is chosen randomly from the range \( [0, 2^n - 1] \).

flowchart TD
    A[Collision Detected] --> B[Choose Random K between 0 and 2^n - 1]
    B --> C[Wait for K * Time Slot]
    C --> D[Attempt Retransmission]

The exponential backoff algorithm ensures that with each collision, the waiting time window grows exponentially, reducing the probability of repeated collisions.

13.3 Example Scenarios

Assume Host 1 (H1) and Host 2 (H2) collided during transmission. The steps are:

1. After the first collision: \(n = 1\)
2. Both hosts choose a random K from \( [0, 1] \)

• If both choose 0, a second collision occurs.
• If one chooses 0 and the other 1, the one with K = 0 will transmit successfully.

After the second collision, the range increases to \( [0, 3] \), reducing the chance of another collision.

13.4 Probability of Collisions

The probability of collisions decreases with each attempt:

• Probability of the first collision: \(1\)
• Probability of the second collision, given the first: \(1/2\)
• Probability of the third collision, given the second: \(1/4\)

This pattern follows an exponential decay, expressed as:

$$P(\text{Collision n} \mid \text{Collision n-1}) = \left( \frac{1}{2} \right)^{n-1}$$

13.5 Capture Effect

The capture effect refers to the scenario where one host (e.g., H1) consistently wins the medium due to the exponential backoff favoring previously successful hosts. If H1 wins initially, it has a higher probability of winning subsequent attempts, potentially starving other hosts.

graph LR
    A[H1 Wins] --> B[Increased Probability for H1]
    B --> C[Repeated Wins by H1]
    C --> D[Starvation of H2]

The capture effect can skew the fairness of the network.

13.6 Mitigating the Capture Effect

To address the capture effect, networks can employ collision-free algorithms like Token Passing. In token passing, only the host with the token can transmit, eliminating the possibility of collisions and ensuring fair access to the medium.

However, token passing has its own limitations, including potential delays and token loss, which can affect efficiency.

13.7 Conclusion

• The exponential backoff algorithm is effective in reducing repeated collisions in CSMA/CD networks.
• It introduces a randomized waiting time that increases exponentially with each collision attempt.
• Despite its advantages, the algorithm may suffer from the capture effect, where a single host repeatedly wins access to the medium.
• Collision-free algorithms, such as token passing, provide an alternative to CSMA/CD in networks requiring strict fairness.

14. Error Handling in the MAC Layer

Error handling at the MAC layer ensures that transmitted data packets arrive intact, with any corruption detected. The primary focus is on error detection rather than correction, as ARQ (Automatic Repeat Request) strategies allow retransmission of corrupted packets.

14.1 Error Detection vs. Error Correction

• Error Detection: Identifies if there is an error in the received data packet.
• Error Correction: Attempts to correct errors without requesting retransmission. Examples include Hamming Code and Convolutional Code.

In the MAC layer, detection strategies are preferred since ARQ protocols can manage retransmission.

14.2 Error Detection Methods

• Parity Check: Adds a bit to ensure even or odd parity. However, it is limited in detecting multiple-bit errors.
• Checksum: Divides data into chunks and performs arithmetic operations to generate error-detection bits.
• Cyclic Redundancy Check (CRC): Uses polynomial division to detect errors, offering more robust protection than parity or checksum methods.

14.3 Parity Check

In parity-based error detection, the sender and receiver agree on a parity scheme (even or odd). If the parity at the receiver does not match the expected value, the packet is considered corrupted.

Data: 1101 (3 zeros, odd parity)
Add 1 bit to make it even: 11010

Limitations: It fails to detect errors when multiple bits are altered.

14.4 Checksum Algorithm

The checksum algorithm breaks data into smaller chunks and computes a sum to generate error detection bits. The receiver recalculates the checksum to verify the data's integrity.

D1 = 1011, D2 = 1100
Checksum = D1 + D2 (ignoring carry bits)

If the checksum at the receiver matches, the data is accepted. Otherwise, it is discarded.

14.5 Cyclic Redundancy Check (CRC)

CRC is a more reliable error detection method that uses polynomial division over the Galois field. It identifies even subtle errors by adding a set of CRC bits to the transmitted data.

14.5.1 How CRC Works

• Both sender and receiver agree on a generator polynomial (e.g., \(x^3 + x + 1\)).
• The polynomial is converted into a bit string (e.g., \(1011\)).
• The sender appends zeros equal to the degree of the polynomial to the data and divides using XOR logic.

graph TD
    A[Data + CRC Bits] --> B[Division with Generator Polynomial]
    B --> C[Compute Remainder using XOR]
    C --> D[Attach Remainder as CRC]

14.5.2 CRC Example

Given Data: 101101, Generator Polynomial: \(x^3 + x + 1\)

Data + Zeros: 101101000
Divisor (Generator Polynomial): 1011
Perform XOR and continue until the data part becomes 0.
CRC Bits: 101

The transmitted message becomes 101101101. The receiver performs the same division. If the remainder is zero, the data is accepted; otherwise, it is discarded.

14.6 Key Points

• Parity is a simple technique but insufficient for multiple-bit errors.
• Checksum offers better protection by summarizing data through addition but has limitations for complex errors.
• CRC provides high reliability using polynomial division and is widely used in real-world networks.

14.7 Summary

Error handling at the MAC layer is crucial to maintaining data integrity in computer networks. While parity checks and checksums are simpler, CRC stands out as the most reliable technique due to its ability to detect subtle errors with mathematical precision.

15. Framing in Data Link Layer

Framing is the process of encapsulating data from the network layer into a frame at the data link layer, which is then transmitted to the physical layer. Each frame has a specific structure that helps with synchronization, error handling, and data identification.

15.1 Frame Structure

A frame generally consists of three parts:

• Header: Contains information like the frame number, size, MAC addresses, and start delimiters.
• Data: Encapsulates the packet received from the network layer.
• Tail: Includes error detection bits (like CRC or checksum) and end delimiters.

15.2 Header and Tail Components

The components in the header and tail vary depending on the protocol:

• Header: Contains the frame number, protocol information, source/destination MAC addresses, and start delimiters.
• Tail: Contains CRC or checksum for error detection and end delimiters to mark the end of the frame.

15.3 Fixed vs. Variable Frame Size

• Fixed Size Frames: All frames are of the same size, which can result in padding if the data is smaller than the frame size.
• Variable Size Frames: The frame size adapts to the size of the data, but requires delimiters or length fields to indicate the start and end of the frame.

In fixed-size frames, padding is used to fill unused space. In variable-size frames, the length or delimiter bits are used to mark the end.

15.4 Delimiters

Delimiters help identify the beginning and end of a frame:

• Start Delimiters: Mark the beginning of the frame.
• End Delimiters: Mark the end of the frame.

Issues arise when the delimiter pattern appears within the data. In such cases, bit stuffing is used.

15.5 Bit Stuffing

Bit Stuffing ensures that the delimiter pattern does not occur within the data. A bit is inserted at a specific location within the data to avoid confusion with delimiters.

Example:

End Delimiter: 01111110
Data: 0111110
Bit Stuffed Data: 011111010

The receiver removes the stuffed bit upon detection to recover the original data.

15.6 Practical Example with Wireshark

Using tools like Wireshark, we can observe real frames transmitted over a network. A typical Ethernet frame might contain:

• Source and Destination MAC Addresses
• Protocol Details (e.g., Ethernet, IP, TCP)
• Frame Check Sequence (CRC)
• Frame Length

Example: A frame with 74 bytes is transmitted, containing protocol information and CRC for error checking.

15.7 Bit Stuffing in Action: Example Question

Given an end delimiter 01111110 and an output bit string after stuffing 011111010, the question is to determine the original data:

End Delimiter: 01111110
Stuffed Output: 011111010

The original data was 0111110 before the bit stuffing. The receiver will remove the stuffed bit upon detection.

15.8 Key Takeaways

• Framing helps encapsulate data for efficient transmission and error handling.
• Variable-size frames increase efficiency but require delimiters or length fields for synchronization.
• Bit stuffing prevents confusion between data and delimiter patterns.
• Tools like Wireshark help observe real-time frame structures and understand protocol behavior.

Conclusion

This documentation systematically examines key networking protocols, error handling mechanisms, and access control methods within the Data Link Layer, offering a structured foundation for understanding their theoretical constructs and practical implementations. Through detailed protocol analysis—including Stop-and-Wait ARQ, Sliding Window, ALOHA, and CSMA variants—this paper highlights the importance of balancing efficiency, fairness, and reliability in network communication.

The integration of mathematical models, such as throughput calculations and efficiency metrics, enables precise evaluation of protocol performance under varying conditions. Controlled access methods like Polling, Reservation, and Token Passing are explored to demonstrate their role in maintaining orderly communication across shared networks. Additionally, error detection strategies, including parity, CRC, and bit-stuffing, are discussed to underline their significance in preserving data integrity.

The insights drawn from this documentation underline the necessity of tailoring protocol selection to network environments, as demonstrated by the trade-offs between CSMA/CD and CSMA/CA in wired and wireless networks, respectively. Advanced techniques, such as Exponential Backoff, further showcase the value of congestion management strategies for ensuring fair access and mitigating collision risks. Collectively, this study contributes to a deeper understanding of the operational challenges and optimization strategies in network communication, equipping researchers and practitioners to make informed decisions in network design and deployment.