Essential Computer Networking Protocols and Mechanisms

Border Gateway Protocol (BGP)

BGP (Border Gateway Protocol) is a routing protocol used to exchange routing information between different networks or Autonomous Systems (AS) on the Internet. It is called an inter-domain routing protocol because it works between different networks.

Roles of BGP

• Connects different Autonomous Systems.
• Exchanges routing information between networks.
• Selects the best path for data transmission.
• Prevents routing loops.
• Maintains internet routing tables.

Example: When a user using Airtel internet accesses a Google server, BGP helps choose the best route between the Airtel network and the Google network.

CSMA/CD: Collision Detection in Ethernet

CSMA/CD stands for Carrier Sense Multiple Access with Collision Detection. It is a network protocol used in Ethernet LANs to reduce data collisions during transmission.

Working Mechanism

1. A device first checks whether the channel is free or busy.
2. If the channel is free, it sends data.
3. If two devices send data at the same time, a collision occurs.
4. Devices stop transmission immediately.
5. After waiting for a random time, they retransmit the data.

Example: If two computers send data simultaneously in an Ethernet network, a collision occurs. CSMA/CD detects the collision and retransmits the data after some time.

Advantages

• Reduces collisions.
• Improves network efficiency.
• Simple and effective protocol.

ALOHA Random Access Protocols

ALOHA is a random access protocol used for data transmission in computer networks.

Pure ALOHA

In Pure ALOHA, devices can send data at any time.

• Features: Simple method, high chance of collision, lower efficiency (18.4%).

Slotted ALOHA

In Slotted ALOHA, time is divided into slots and data is sent only at the beginning of a slot.

• Features: Less collision, better efficiency (36.8%), requires synchronization.

Hamming Code for Error Correction

Hamming Code is an error detection and error correction technique used in computer networks and digital communication. It can detect 2-bit errors and correct 1-bit errors.

Working Process

1. Extra parity bits are added to data bits.
2. The receiver checks the parity bits.
3. If an error is found, the incorrect bit is identified and corrected automatically.

Example: Suppose data sent is 1011; parity bits are added before transmission to detect and correct errors.

Applications and Advantages

• Computer memory (RAM).
• Satellite communication.
• Digital communication systems.
• Error correction in networks.
• Improves data reliability and reduces retransmission.

Sliding Window Protocol Flow Control

The Sliding Window Protocol is a flow control mechanism used to control the rate of data transmission between a sender and a receiver. It allows the sender to send multiple frames before receiving an acknowledgement, thereby improving network efficiency.

Working Mechanism

1. The sender maintains a window containing frames that can be transmitted.
2. The sender sends multiple frames without waiting for individual acknowledgements.
3. The receiver receives the frames and sends acknowledgements (ACKs).
4. As acknowledgements are received, the sender's window moves forward.
5. New frames are transmitted as space becomes available in the window.

TCP Congestion Control Mechanisms

TCP Congestion Control is used to prevent congestion in a network and ensure efficient data transmission.

1. Slow Start

• TCP starts with a small congestion window.
• The window size increases rapidly after each ACK.
• Growth is exponential and continues until the threshold is reached.

2. Congestion Avoidance

• Starts after reaching the threshold.
• The congestion window increases slowly (linear growth).
• Helps avoid network congestion.

3. Fast Recovery

• Activated when three duplicate ACKs are received.
• The lost packet is retransmitted immediately.
• The congestion window is reduced but not reset to 1.
• Transmission continues without restarting.

Hidden Terminal Problem and CSMA/CA

The Hidden Terminal Problem occurs in wireless networks when two devices cannot hear each other but both send data to the same receiver at the same time, causing a collision.

Example: Computer A and another device cannot hear each other. Both send data to B simultaneously; a collision occurs at B.

CSMA/CA (Collision Avoidance)

CSMA/CA stands for Carrier Sense Multiple Access with Collision Avoidance. It reduces collisions using:

• RTS (Request to Send): Sender sends RTS.
• CTS (Clear to Send): Receiver replies with CTS.
• Other stations hearing the CTS wait before transmitting, thus avoiding collisions.

TCP Three-Way Handshake Process

The TCP Three-Way Handshake mechanism is a process used to establish a reliable connection between a client and a server before data transmission.

• Step 1 (SYN): The client sends a SYN (Synchronize) packet to the server, requesting a connection.
• Step 2 (SYN-ACK): The server replies with a SYN-ACK (Synchronize-Acknowledge) packet indicating it is ready.
• Step 3 (ACK): The client sends an ACK packet to the server.

After these steps, the connection is established and data transfer can begin.

Link State Routing and Dijkstra's Algorithm

Link State Routing is a routing technique in which every router maintains a complete map of the network and finds the shortest path using Dijkstra's algorithm.

Steps in Link State Routing

1. Neighbor Discovery: Each router discovers its directly connected neighbors.
2. Measure Link Cost: The cost of each link is calculated based on distance, bandwidth, or delay.
3. Create Link State Packet (LSP): Each router creates an LSP containing the Router ID, neighbor information, and link costs.
4. Flooding: The LSP is sent to all routers in the network.
5. Build Topology Database: Every router stores all received LSPs and creates a complete network map.

Error Detection and Correction Techniques

During data transmission, errors may occur due to noise, interference, or transmission problems. To ensure reliable communication, networks use error detection and correction techniques.

Error Detection

The process of identifying whether an error occurred during transmission.

• Parity Check: An extra parity bit (even or odd) is added. Simple but cannot detect all errors.
• Checksum: Data is divided into segments; a checksum value is calculated and sent. The receiver recalculates it to detect errors.
• Cyclic Redundancy Check (CRC): Uses a generator polynomial; very effective for transmission errors.

Error Correction

Detects and corrects errors without retransmission.

• Hamming Code: Uses redundant bits to detect and correct single-bit errors.
• Forward Error Correction (FEC): Additional redundant bits allow the receiver to correct errors without requesting retransmission.

Selective Repeat ARQ vs. Go-Back-N

Selective Repeat ARQ (Automatic Repeat Request) is an error control protocol for reliable data transmission. Only the lost or damaged frame is retransmitted, improving efficiency and saving bandwidth.

Example: If frames F1, F2, F3, F4 are sent and F2 is lost, the receiver accepts F1, F3, and F4, but requests only F2. The sender retransmits only F2.

Comparison of ARQ Protocols

• Selective Repeat ARQ: i) Only lost frames are retransmitted. ii) More efficient. iii) Requires more memory. iv) More complex. v) Faster recovery from errors. vi) High implementation cost. vii) Receiver stores out-of-order frames.
• Go-Back-N ARQ: i) Lost frame and all following frames are retransmitted. ii) Less efficient. iii) Simpler implementation. iv) Discards out-of-order frames.

Token Bucket Traffic Control Algorithm

The Token Bucket algorithm is a traffic control mechanism used to control the amount of data transmitted. Tokens are generated and stored in a bucket at a fixed rate. A device can send data only if sufficient tokens are available.

Working Mechanism

1. Tokens are added to the bucket at regular intervals.
2. Each token allows the transmission of a fixed amount of data.
3. When a packet arrives: if tokens are available, the packet is sent; if not, the packet waits or is discarded.
4. The bucket has a limited capacity for tokens.