Routing Algorithms, FTP, and CSMA Protocols Explained
Distance Vector Routing Algorithm
The Distance Vector algorithm is a distributed routing algorithm where routers share their routing table information with their immediate neighbors periodically. It is based on the Bellman-Ford algorithm.
Key Features
- Vector of Distances: Each router maintains a table (vector) of distances to all other nodes in the network. Distance is typically measured in terms of hop count or other metrics like delay or cost.
- Periodic Updates: Routers exchange their routing tables with neighboring routers periodically, even if there are no changes.
- Simple and Easy to Implement: The algorithm is straightforward but can become inefficient in large or dynamic networks.
- Routing by Rumor: Routers only have knowledge of their immediate neighbors and rely on them for information about the rest of the network.
How It Works
- Each router initializes its routing table with direct neighbors and marks all other nodes as unreachable.
- The router periodically sends its routing table to its immediate neighbors.
- Upon receiving an update, the router updates its own table using the formula: New Distance = Distance to Neighbor + Neighbor’s Distance to Destination
- The process repeats until all routers have consistent tables (convergence).
Link State Routing Algorithm
The Link State algorithm is a dynamic routing protocol where routers maintain a complete view of the network’s topology and compute the shortest path to every destination using Dijkstra’s algorithm.
Key Features
- Topology Awareness: Each router has a complete map of the network, including all nodes and links.
- Efficient Convergence: Changes in the network are quickly propagated, leading to faster convergence compared to Distance Vector algorithms.
- Periodic Updates: Routers send updates only when a link state changes (event-driven), rather than periodically.
- Resource-Intensive: Requires more memory and computational power due to maintaining the entire topology and running Dijkstra’s algorithm.
How It Works
- Link State Advertisement (LSA): Each router broadcasts LSAs containing information about its neighbors and link costs.
- Topology Database: Routers use LSAs to build a complete topology database of the network.
- Shortest Path Calculation: Each router runs Dijkstra’s algorithm on the topology database to compute the shortest path tree and populate its routing table.
- Forwarding: Data packets are forwarded along the shortest paths computed.
Hierarchical Routing Algorithm
Hierarchical Routing is a scalable routing approach where the network is divided into multiple regions or hierarchical levels, reducing the size of routing tables and overhead.
Key Features
- Network Segmentation: The network is divided into smaller, manageable regions or domains. Routers in a region only have detailed routing information for their own region and abstract information for other regions.
- Efficient Scalability: Reduces the size of routing tables, making it suitable for very large networks like the Internet.
- Reduced Overhead: By maintaining abstracted routing information for external regions, routers save memory and bandwidth.
How It Works
- Intra-Region Routing: Routers within the same region communicate using detailed routing algorithms like Link State or Distance Vector.
- Inter-Region Routing: Between regions, only summary or aggregate information is exchanged, reducing the complexity.
- Hierarchical Levels: Multiple levels of hierarchy can be created (e.g., regional, national, international) to further enhance scalability.
File Transfer Protocol (FTP)
FTP (File Transfer Protocol) is a standard network protocol used for transferring files between a client and a server over a TCP/IP-based network, such as the Internet. It operates on the client-server model and uses separate control and data connections to improve efficiency.
Key Components of FTP
- Client: Initiates the connection and requests file transfers (upload/download).
- Server: Hosts files and responds to client requests.
- Control Connection: Manages commands and responses between client and server.
- Data Connection: Transfers the actual files.
Steps in FTP File Transfer
- Establishing a Control Connection: The client establishes a TCP connection to the server on port 21 for control communication. Commands (e.g., login, directory navigation) and responses are exchanged over this connection.
- Authentication: The client provides credentials (username and password) to log in to the server. Anonymous FTP may allow access without credentials.
- Establishing a Data Connection: A separate connection is created for transferring files:
- Active Mode: The server opens the data connection to the client.
- Passive Mode: The client opens the data connection to the server (useful in firewalled environments).
- File Transfer: Files are uploaded/downloaded through the data connection. FTP supports both text (ASCII) and binary modes for data transfer.
- Closing the Connections: Once the file transfer is complete, the data connection is terminated. The control connection remains open for further commands until explicitly closed.
Carrier Sense Multiple Access (CSMA)
Carrier Sense Multiple Access (CSMA) is a medium access control (MAC) protocol used in networks to manage how data packets are transmitted on a shared communication channel. In CSMA, a device listens to the channel (carrier sensing) before transmitting data to avoid collisions.
Key Principles of CSMA
- Carrier Sensing: Devices sense the communication medium to check whether it is idle or busy before attempting to transmit.
- Collision: If two devices transmit simultaneously, a collision occurs, causing data corruption.
- Recovery Mechanism: CSMA includes strategies to detect or avoid collisions and retransmit data as necessary.
Variations of CSMA
- Pure CSMA
- CSMA with Collision Detection (CSMA/CD)
- CSMA with Collision Avoidance (CSMA/CA)
Pure CSMA
Definition: In Pure CSMA, a device first senses the channel to check if it is idle. If the channel is busy, it waits until the channel becomes idle before transmitting data.
Working
- The device continuously senses the channel.
- If the channel is idle, it transmits data immediately.
- If a collision occurs (multiple devices transmitting at the same time), no mechanism exists to detect it immediately. Devices only retransmit after a timeout.
Drawbacks
Collisions still occur because propagation delays prevent devices from sensing transmissions in progress. Inefficient in high-load scenarios.
CSMA with Collision Detection (CSMA/CD)
Definition: CSMA/CD enhances Pure CSMA by detecting collisions while a device is transmitting. It is used in wired networks like Ethernet.
Working
- A device listens to the channel before transmitting. If the channel is idle, it begins transmission.
- While transmitting, the device continues to monitor the channel for collisions.
- If a collision is detected:
- The device immediately stops transmitting.
- It sends a jam signal to notify other devices of the collision.
- It waits for a random backoff period before retransmitting.
Advantages
Reduces the time wasted on collisions by detecting them early.
Limitations
CSMA/CD is not effective in wireless networks due to the hidden terminal problem and propagation delays.
CSMA with Collision Avoidance (CSMA/CA)
Definition: CSMA/CA is designed for wireless networks, where collisions are difficult to detect. Instead of detecting collisions, CSMA/CA tries to avoid them.
Working
- A device senses the channel before transmitting. If the channel is idle, it does not transmit immediately.
- Backoff Mechanism: The device waits for a random backoff time even if the channel is idle to minimize the chances of collisions.
- Request-to-Send (RTS) and Clear-to-Send (CTS):
- To further reduce collisions, the device may use RTS and CTS signals.
- Before sending data, the device sends an RTS packet to the receiver. If the receiver is ready, it responds with a CTS packet.
- This exchange reserves the channel for communication.