Unit V: NETWORK LAYER: Routing & Congestion Control | CSE306: COMPUTER NETWORKS | B.Tech CSE

Unit V: NETWORK LAYER: Routing & Congestion Control

⭐Routing Algorithms

Routing algorithms are used to determine the best path for data to travel from a source to a destination across a network. They play a crucial role in ensuring efficient data delivery and optimal network performance.

---

1. Types of Routing Algorithms

a) Static Routing

• Definition: In static routing, the routes are manually configured by the network administrator. Once set, these routes do not change unless manually modified.
• Characteristics:
  • Fixed paths and do not adapt to network changes.
  • Suitable for small, simple networks where the topology rarely changes.
  • Low overhead because there’s no need for route discovery or updates.
  • Not scalable or flexible because of the lack of adaptability.
  • Vulnerable to network failures because it doesn't dynamically adjust to failures or congestion.
• Advantages:
  • Simple and easy to configure.
  • No overhead in terms of routing protocols.
  • More secure because the routes are predetermined.
• Disadvantages:
  • Does not adapt to network failures or congestion.
  • Requires manual configuration and maintenance.
  • Poor scalability in large networks.

b) Dynamic Routing

• Definition: In dynamic routing, routes are automatically calculated and adjusted based on the network’s current state. Routers share information with one another to update their routing tables, allowing the network to adjust to changes in topology (e.g., failures, new links).
• Characteristics:
  • Routes are updated automatically based on current network conditions.
  • Routers periodically exchange information about their topology.
  • More complex and uses more resources (memory, CPU) than static routing.
• Advantages:
  • Automatically adjusts to network changes, ensuring continuous data delivery.
  • Scalable and adaptable to large networks.
  • Reduces manual configuration and maintenance.
• Disadvantages:
  • More complex to configure and manage.
  • Uses more bandwidth for exchanging routing information.
  • Requires more CPU and memory resources.

2. Categories of Dynamic Routing Algorithms

Dynamic routing algorithms are primarily divided into Distance Vector and Link-State categories.

a) Distance Vector Routing Algorithms

• Definition: Distance vector algorithms rely on each router knowing the distance (or cost) to reach every other router in the network. This information is shared with directly connected neighbors periodically, allowing routers to update their routing tables.

• How it works:

  • Each router shares its routing table with its neighbors.
  • Routers calculate the best path to each destination based on distance metrics like hop count, delay, or bandwidth.
  • Routers update their tables whenever they receive new information from neighbors.

• Key Characteristics:

  • Each router maintains a table that lists the best path to every other router in the network.
  • Routers only share their routing tables with directly connected neighbors.
  • Updates are periodic or triggered by changes in network topology.

• Examples of Distance Vector Protocols:

  • RIP (Routing Information Protocol): RIP is one of the most popular distance-vector protocols. It uses hop count as its metric and has a maximum hop count of 15. It is simple and easy to implement but not efficient for large networks due to slow convergence and limited scalability.

  • BGP (Border Gateway Protocol): While BGP is more advanced and used for inter-domain routing (between autonomous systems), it is based on the distance vector concept. BGP uses path vectors, but its operation is similar in terms of sharing routing information between networks.

• Advantages:

  • Simple and easy to configure.
  • Requires less memory and processing power.
  • Suitable for small networks with stable topology.

• Disadvantages:

  • Slow convergence and more prone to routing loops.
  • Limited scalability (not suitable for large networks).
  • Can suffer from the count-to-infinity problem where network instability can cause slow recovery.

b) Link-State Routing Algorithms

• Definition: Link-state routing algorithms provide each router with a complete map of the network, which helps it to independently calculate the best path to all destinations. Routers advertise their link states (i.e., the status of their direct connections) to every other router in the network.

• How it works:

  • Routers exchange link-state information to build a complete view of the network.
  • Once each router has a complete map, it calculates the best path using algorithms like Dijkstra's.
  • Link-state protocols allow routers to react quickly to network changes (e.g., router failures, congestion).

• Key Characteristics:

  • Routers have a global view of the network topology.
  • Routers flood the network with link-state advertisements (LSAs) to keep the map up to date.
  • Link-state routing algorithms require more memory and processing power than distance vector algorithms but are more efficient and scalable.

• Examples of Link-State Protocols:

  • OSPF (Open Shortest Path First): OSPF is one of the most commonly used link-state protocols in IP networks. It uses the Dijkstra algorithm to calculate the shortest path to each destination. OSPF is more scalable than RIP and converges faster.

  • IS-IS (Intermediate System to Intermediate System): IS-IS is a link-state protocol, similar to OSPF but used mostly in larger, enterprise-level networks and some ISP environments. It is designed to handle more complex network topologies.

• Advantages:

  • Fast convergence, minimizing network downtime.
  • More scalable for large and complex networks.
  • Less prone to routing loops compared to distance vector algorithms.

• Disadvantages:

  • More complex and requires more memory and processing power.
  • Requires more bandwidth due to the need to share complete network topology.
  • More overhead in terms of configuration and maintenance.

3. Hybrid Routing Algorithms

• Definition: Hybrid algorithms combine elements from both distance vector and link-state algorithms. They try to leverage the advantages of both methods, using distance vector simplicity and link-state efficiency.
• Example:
  • EIGRP (Enhanced Interior Gateway Routing Protocol): EIGRP is a Cisco proprietary protocol that combines the advantages of distance vector and link-state routing. It uses a Diffusing Update Algorithm (DUAL) to provide faster convergence and loop-free paths. It is more efficient than standard distance vector protocols like RIP and provides better scalability than link-state protocols like OSPF in certain scenarios.

4. Other Routing Algorithm Features

• Convergence: The time it takes for all routers in the network to update their routing tables after a change in network topology. Faster convergence reduces the risk of routing loops and ensures data reaches its destination quickly.

• Scalability: Refers to the ability of a routing algorithm to handle a growing network. Link-state protocols like OSPF are more scalable than distance vector protocols like RIP.

• Stability: A stable routing algorithm maintains consistent routing tables even as network conditions change. Algorithms like OSPF offer greater stability than RIP.

• Efficiency: Efficient routing algorithms minimize overhead, such as the amount of data exchanged between routers and the amount of processing required for route calculations.

⭐Shortest Path Algorithm

The Shortest Path Algorithm is used to find the most efficient path between two nodes (routers or computers) in a network. The goal is to minimize the "cost" of the path, which could represent metrics like distance, time, or number of hops.

There are two widely used algorithms to solve the shortest path problem: Dijkstra’s Algorithm and Bellman-Ford Algorithm. These algorithms are used in both routing protocols and network optimization.

---

1. Overview of Shortest Path Algorithm

• Purpose: To calculate the minimum-cost path from a source node to a destination node across a network.
• Cost Metrics: The cost can be defined in various ways, including:
  • Distance: Number of hops between nodes.
  • Bandwidth: Maximum data transfer rate along the path.
  • Latency: Delay in transmitting data over the path.
  • Packet Loss: Probability of packet loss along the route.

These algorithms work by either exploring all possible paths and selecting the best one or progressively refining the best path as more information becomes available.

2. Dijkstra’s Algorithm

Dijkstra’s Algorithm is one of the most popular and widely used shortest path algorithms, especially in Link-State Routing protocols like OSPF.

• Purpose: To find the shortest path from a source node to all other nodes in the network, ensuring the minimum total cost.

• Working Principle: It uses a greedy approach to progressively expand the shortest path from the source node.

  Steps Involved:

  1. Initialization:
     • Start by assigning a tentative cost value to every node: set the source node’s cost to 0 and all other nodes to infinity.
     • Mark all nodes as unvisited.
  2. Visit the Nearest Node:
     • Select the unvisited node with the smallest tentative cost.
  3. Update Neighboring Nodes:
     • For the selected node, examine its unvisited neighbors. Calculate their tentative cost (current node's cost + edge weight). If this new cost is lower than the previously assigned cost, update it.
  4. Mark Node as Visited:
     • Once a node has been visited, it cannot be revisited.
  5. Repeat:
     • Continue selecting the unvisited node with the smallest tentative cost, updating the neighbors, and marking nodes as visited until all nodes have been visited.
  6. Reconstruct the Path:
     • The shortest path from the source node to any other node can be reconstructed by following the nodes in reverse order of how they were updated.

• Key Features:

  • Greedy Approach: Always selects the node with the smallest known tentative cost.
  • Complexity: The algorithm’s time complexity is $O(E \log V)$, where $E$ is the number of edges, and $V$ is the number of vertices.
  • Works Only with Non-negative Weights: Dijkstra’s algorithm assumes all edge weights are non-negative, as it may fail if negative weights are present.

• Advantages:

  • Efficient for finding the shortest path in a weighted graph.
  • Guaranteed to find the shortest path if all edge weights are non-negative.

• Disadvantages:

  • Cannot handle negative edge weights.
  • Requires significant memory for large graphs.

3. Bellman-Ford Algorithm

The Bellman-Ford Algorithm is another algorithm for solving the shortest path problem, but it has the advantage of being able to handle negative edge weights.

• Purpose: It finds the shortest path from a source node to all other nodes in a network, even when negative weights exist on the edges.

• Working Principle: It repeatedly relaxes all edges in the network and updates the shortest path estimates.

  Steps Involved:

  1. Initialization:
     • Set the distance to the source node to 0 and to all other nodes to infinity.
  2. Relaxation:
     • For each edge $(u, v)$, if the distance to $v$ through $u$ is smaller than the current distance to $v$, update the distance.
     • Repeat this relaxation process $V-1$ times (where $V$ is the number of vertices).
  3. Check for Negative Weight Cycles:
     • After $V-1$ iterations, perform one more iteration. If any distance can still be updated, it means there’s a negative weight cycle in the graph.

• Key Features:

  • Works with Negative Weights: The Bellman-Ford algorithm can handle negative edge weights, unlike Dijkstra’s.
  • Time Complexity: $O(VE)$, where $V$ is the number of vertices and $E$ is the number of edges. This is slower than Dijkstra’s algorithm, especially for large graphs.

• Advantages:

  • Can handle graphs with negative weights.
  • Can detect negative weight cycles in the graph, which is a unique feature.

• Disadvantages:

  • Slower than Dijkstra’s algorithm for graphs without negative weights.
  • Requires multiple passes over the entire graph, making it less efficient for large networks.

4. Comparison of Dijkstra’s and Bellman-Ford Algorithms

Feature	Dijkstra’s Algorithm	Bellman-Ford Algorithm
Handling of Negative Weights	Cannot handle negative edge weights.	Can handle negative edge weights.
Complexity	$O(E \log V)$ (using priority queues)	$O(VE)$
Detection of Negative Cycles	Does not detect negative cycles.	Can detect negative weight cycles.
Best for	Networks with non-negative edge weights.	Networks with negative edge weights.
Performance	Faster for most graphs without negative weights.	Slower, especially for large graphs.

5. Applications of Shortest Path Algorithms

Shortest path algorithms are used in various fields and applications:

• Routing in Computer Networks:

  • Routers use these algorithms to determine the best path for forwarding packets across a network (e.g., OSPF uses Dijkstra’s algorithm).

• Traffic Management and Navigation Systems:

  • Used in GPS devices and online mapping services (like Google Maps) to find the shortest route between two locations.

• Telecommunications:

  • Used to find the most efficient path for data transmission in a network.

• Urban Planning:

  • Used to optimize road networks and public transportation routes.

⭐Distance Vector Routing

Distance Vector Routing is a type of routing algorithm used in computer networks, where each router maintains a table (vector) of the best-known distances to all other routers in the network. This type of routing algorithm relies on each router's ability to share its routing table with its directly connected neighbors to help determine the best path to a destination.

---

1. Definition

• Distance Vector Routing is a routing protocol where each router shares its distance vector (a table of distances to all destinations) with its directly connected neighbors.
• The main idea is that each router only knows the distance (or cost) to reach its directly connected neighbors, and the distance to all other nodes is indirectly learned through periodic updates from neighboring routers.

2. How Distance Vector Routing Works

1. Initialization:

   • Each router begins by setting up its routing table. Initially, the router knows only the distance to its direct neighbors, which is typically 1 (or the weight of the link), and infinity for all other destinations.

2. Exchange of Routing Tables:

   • Routers periodically share their routing tables with their directly connected neighbors.
   • A router receives the routing table from its neighbor, which includes distances to all destinations known by that neighbor.

3. Update Routing Table:

   • When a router receives a new routing table from a neighbor, it uses the Bellman-Ford Algorithm to update its own table.
   • The router checks if any new route can be found by going through the neighbor. If the distance through the neighbor is shorter than the current known distance, the router updates its table.

4. Convergence:

   • Over time, routers continue to exchange their routing tables. Eventually, all routers in the network will have consistent and correct information about the shortest paths to all destinations. This state is called convergence.

5. Periodic Updates:

   • To keep routing information up to date, routers periodically send their updated routing tables to neighbors.
   • If the network topology changes (e.g., a router or link fails), routers exchange information to adapt to the change.

3. Key Concepts in Distance Vector Routing

• Routing Table:

  • Each router has a table that stores the distance (cost) to every other router in the network.
  • The table is updated whenever a better (shorter) route is found.

• Distance Metric:

  • The metric used to calculate the shortest path could be hop count, bandwidth, delay, or other factors that reflect the cost of reaching a destination.
  • Commonly used metrics include hop count (number of intermediate nodes) or cost (cumulative weight of the links).

• Bellman-Ford Algorithm:

  • This algorithm is used by routers in distance vector routing to compute the shortest path to each destination. It works by relaxing all edges repeatedly and updating distances when a shorter path is found.

• Routing Information Protocol (RIP):

  • RIP is the most commonly used Distance Vector Routing protocol. It uses hop count as its metric, with a maximum hop count of 15 (a hop count of 16 is considered unreachable).

4. Example of Distance Vector Routing

Imagine a small network with three routers: A, B, and C. The link between A and B has a cost of 1, between B and C has a cost of 2, and A and C have a direct link with a cost of 3.

Initially:

• Router A knows:

  • To reach B: Cost = 1
  • To reach C: Cost = 3 (direct link)

• Router B knows:

  • To reach A: Cost = 1
  • To reach C: Cost = 2

• Router C knows:

  • To reach A: Cost = 3 (direct link)
  • To reach B: Cost = 2

The routers exchange their routing tables, and after a few iterations, all routers will update their tables to reflect the shortest path from each router to the others.

5. Advantages of Distance Vector Routing

• Simple and Easy to Implement: Distance Vector algorithms are conceptually simple and easy to configure, making them ideal for small networks or simple routing needs.

• Low Overhead: Initial routing information is minimal, and updates are only needed when changes occur. This makes it relatively lightweight in terms of communication overhead.

• Good for Small Networks: Works well for smaller networks where the topology does not change often and the routing table size is manageable.

• No Need for Global Knowledge: Routers only need to know the distance to their immediate neighbors, reducing the amount of data each router needs to maintain.

6. Disadvantages of Distance Vector Routing

• Slow Convergence: When a network topology changes (e.g., a link fails), it takes time for all routers to update their tables and converge on the new best path.

• Routing Loops: Distance Vector algorithms are prone to routing loops, especially when there is a network failure. This happens because routers might continue to propagate outdated information.

  • Count-to-Infinity Problem: This is a classic example of a routing loop, where routers slowly increase the cost to a destination, making it impossible to determine the correct shortest path in the case of a network failure.

• Scalability Issues: As the network grows in size, the routing tables become large, and periodic updates require more bandwidth and processing power. Distance Vector protocols do not scale well in very large networks.

• No Global View: Each router only knows about its immediate neighbors and does not have a complete view of the entire network. This can limit the router's ability to adapt to network changes quickly.

7. Routing Information Protocol (RIP)

• RIP is the most widely used implementation of Distance Vector Routing.

• Key Characteristics of RIP:

  • Hop Count Metric: RIP uses hop count as the cost metric. Each hop between routers increases the cost by 1.
  • Maximum Hop Count: The maximum number of hops allowed in RIP is 15. Any destination that is more than 15 hops away is considered unreachable.
  • Periodic Updates: RIP sends out routing updates every 30 seconds to ensure that all routers have the most up-to-date information.
  • Versions:
    • RIP v1: Older version, supports only IPv4 and broadcasts its routing updates (no authentication).
    • RIP v2: Enhanced version, supports both IPv4 and IPv6, and uses multicast for updates, which is more efficient.

• Advantages:

  • Simple and easy to configure.
  • Works well in small to medium-sized networks.

• Disadvantages:

  • Limited scalability due to the maximum hop count of 15.
  • Slow convergence and potential for routing loops.

8. Comparison with Other Routing Algorithms

Feature	Distance Vector Routing	Link-State Routing
Topology Knowledge	Routers know only the distance to neighbors.	Routers have a global view of the network topology.
Routing Information	Periodically exchanges routing tables with neighbors.	Routers exchange link-state information.
Convergence Time	Slow convergence, especially with large networks or failures.	Faster convergence due to a more detailed network view.
Scalability	Less scalable for large networks.	More scalable and efficient in large networks.
Routing Loops	More prone to routing loops and requires loop-prevention mechanisms.	Less prone to routing loops.
Example Protocols	RIP (Routing Information Protocol)	OSPF (Open Shortest Path First), IS-IS
Complexity	Simpler, less memory required.	More complex and requires more memory and processing power.

⭐Link-State Routing

Link-State Routing is a type of routing algorithm where each router in a network maintains a complete map of the network's topology. Unlike Distance Vector Routing, where routers only know the distance to their neighbors, Link-State Routing allows routers to have a global view of the entire network. This enables more accurate and efficient path calculations.

---

1. Definition of Link-State Routing

• Link-State Routing protocols use the concept of link-state advertisements (LSAs) to share information about the status of each router's directly connected links.
• Each router sends its LSA to all other routers in the network, which allows every router to independently calculate the best path to each destination using a Shortest Path Algorithm like Dijkstra’s.

2. How Link-State Routing Works

1. Network Topology Discovery:

   • Each router discovers the state of its links (interfaces) by sending Hello packets to its neighbors.
   • A router then collects this information from all other routers, which allows it to build a complete map of the network topology.

2. Flooding LSAs:

   • Once a router knows about its directly connected neighbors, it creates an LSA containing information about its links (the state of each link and the cost to reach each neighbor).
   • This LSA is then flooded throughout the network to all other routers. Flooding means each router sends the LSA to all its neighbors, which in turn forward it to their neighbors, and so on.
   • Flooding ensures that every router in the network learns about every other router’s links.

3. Building the Link-State Database (LSDB):

   • After receiving LSAs from all other routers, each router builds a Link-State Database (LSDB), which is a complete view of the network topology (graph of routers and links).

4. Running Dijkstra’s Algorithm:

   • Each router uses its LSDB to run a Shortest Path Algorithm (usually Dijkstra’s algorithm) to calculate the best (shortest) path to all other routers in the network.
   • The shortest path is computed by considering the cost of the links in the network. This ensures that each router knows the most efficient way to reach any destination.

5. Routing Table Construction:

   • After calculating the shortest paths, the router updates its Routing Table with the best paths to all destinations.

6. Periodic Updates:

   • Routers periodically exchange LSAs to update their LSDB and maintain an up-to-date network topology.
   • If a router’s link status changes (e.g., a link goes down), it sends a new LSA to inform all other routers in the network, which causes them to update their LSDBs and recompute the shortest paths.

3. Key Concepts in Link-State Routing

• Link-State Advertisements (LSA):

  • The fundamental unit of information in Link-State Routing. LSAs contain details about the router’s interfaces and their status (up or down).
  • LSAs are flooded across the network, allowing every router to obtain a full picture of the network.

• Link-State Database (LSDB):

  • A database in each router that stores information about all the links in the network. It is constructed using the LSAs received from other routers.
  • Each router has an identical LSDB, providing a consistent view of the network topology.

• Shortest Path First (SPF) Algorithm:

  • The algorithm used by routers to calculate the best (shortest) path to each destination based on the network topology.
  • Dijkstra’s Algorithm is typically used to compute the shortest path from a router to all other routers.

• Hello Protocol:

  • The Hello protocol is used by routers to discover and maintain neighbor relationships with directly connected routers.
  • It helps in detecting failures or changes in the network topology by regularly exchanging Hello packets.

4. Advantages of Link-State Routing

• Faster Convergence:
  • Link-State Routing protocols converge faster than Distance Vector Routing protocols. This is because each router has a complete and updated map of the network, enabling it to quickly adjust its routing decisions after a topology change.
• More Efficient:
  • Since routers only exchange updates when there is a change in the network (e.g., link failure or new link), the network traffic is reduced compared to protocols that send periodic updates.
• No Count-to-Infinity Problem:
  • Link-State protocols do not suffer from the count-to-infinity problem that occurs in Distance Vector Routing because every router has a complete and accurate view of the network topology.
• Improved Scalability:
  • Link-State protocols are more scalable than Distance Vector Routing protocols, making them better suited for larger networks.
• Better Loop Prevention:
  • By maintaining a complete map of the network, Link-State Routing ensures that routing loops are avoided, as the algorithm can always calculate the shortest path using accurate network information.

5. Disadvantages of Link-State Routing

• More Complex:

  • Link-State Routing protocols are more complex to configure and manage than Distance Vector Routing protocols because routers need to maintain a complete network map and run algorithms like Dijkstra’s.

• Higher Memory and CPU Requirements:

  • Since routers store a full map of the network, Link-State Routing requires more memory to maintain the LSDB.
  • Running the SPF algorithm also requires more CPU resources, especially in large networks.

• Flooding Overhead:

  • Flooding LSAs throughout the network can create overhead, particularly when there are frequent topology changes. This can lead to network congestion if not properly managed.

• Initial Delay:

  • In large networks, it may take some time for all routers to exchange their LSAs and build their LSDBs before they can compute the best paths. During this period, routers may not have a complete view of the network.

6. Example of Link-State Routing Protocols

• OSPF (Open Shortest Path First):
  • OSPF is the most widely used Link-State Routing protocol. It is commonly used in large enterprise networks and ISPs.
  • OSPF Characteristics:
    • Uses LSAs to share link-state information.
    • Employs Dijkstra’s Algorithm for shortest path calculation.
    • Divides large networks into smaller areas to reduce the size of LSAs and improve scalability.
    • Supports both IPv4 and IPv6.
• IS-IS (Intermediate System to Intermediate System):
  • IS-IS is another Link-State Routing protocol, mainly used by service providers.
  • It is similar to OSPF in its operation but differs in how it handles routing information and areas.
• Integrated IS-IS:
  • A version of IS-IS that can carry both IPv4 and IPv6 routing information in a single protocol.

7. OSPF (Open Shortest Path First)

• OSPF is the most commonly used Link-State Routing protocol and is designed for large and complex networks.
• OSPF Characteristics:
  • Hierarchical Design: OSPF supports a hierarchical network design using areas, which helps reduce the amount of routing information exchanged within the network.
  • Area 0 (Backbone): The core of the OSPF network, where all other areas must connect.
  • Router Types: OSPF defines different router types (e.g., Internal Router, Area Border Router, Backbone Router, Autonomous System Boundary Router) to provide a scalable and efficient routing structure.
  • Cost Metric: OSPF uses cost as its metric for determining the best path, typically based on the bandwidth of the links.
  • LSA Types: OSPF defines several types of LSAs for different purposes, such as for advertising network information, router information, or external routes.

8. Comparison with Distance Vector Routing

Feature	Link-State Routing	Distance Vector Routing
Topology Knowledge	Routers have a global view of the network (LSDB).	Routers only know the distance to their neighbors.
Routing Table Updates	Updates are based on changes in the network, not periodic broadcasts.	Updates are broadcast periodically.
Convergence Time	Faster convergence due to complete network view.	Slower convergence, especially in large networks.
Scalability	More scalable for larger networks.	Less scalable for larger networks.
Loop Prevention	Less prone to loops due to accurate network map.	Prone to loops, requires loop-prevention mechanisms (e.g., split horizon).
Example Protocols	OSPF, IS-IS	RIP, EIGRP (Hybrid)

⭐Unicast Routing Protocols

Unicast Routing refers to the process of sending data from one source to a single destination on a network. Unicast Routing Protocols are responsible for determining the optimal path for these data packets to travel from the source to the destination.

These protocols are primarily used in IP (Internet Protocol) networks and involve the calculation of the best path for packet delivery using various routing algorithms.

---

1. Definition of Unicast Routing

• Unicast Routing is the method by which data is sent from one specific source device to one specific destination device in a network.
• Unicast routing protocols determine the path that data packets take from the source router to the destination router by selecting the best routes based on various criteria (such as hop count, link bandwidth, or delay).

2. Types of Unicast Routing Protocols

Unicast routing protocols are divided into two major categories:

1. Interior Gateway Protocols (IGPs): These protocols operate within a single autonomous system (AS), which is a network or group of networks under the same administrative control.
   • Examples: RIP, OSPF, EIGRP
2. Exterior Gateway Protocols (EGPs): These protocols operate between different autonomous systems, typically used for routing between different networks or organizations.
   • Example: BGP (Border Gateway Protocol)

3. Common Unicast Routing Protocols

1. RIP (Routing Information Protocol)

• Definition: RIP is one of the oldest and simplest Distance Vector routing protocols, primarily used for routing within small to medium-sized networks.

• Key Features:

  • Uses hop count as its metric to determine the best path.
  • Maximum hop count is 15, so any destination more than 15 hops away is considered unreachable.
  • Routers periodically exchange routing tables to update information.
  • RIP v1 (old version) supports only IPv4 and uses broadcasting to send routing updates, while RIP v2 supports IPv4 and IPv6 and uses multicast for updates.

• Advantages:

  • Simple and easy to configure.
  • Good for small networks with few routers.

• Disadvantages:

  • Slow convergence due to the periodic updates.
  • Limited scalability with the maximum hop count of 15.
  • Prone to routing loops.

2. OSPF (Open Shortest Path First)

• Definition: OSPF is a Link-State routing protocol that uses Dijkstra’s algorithm to calculate the best path based on network topology.

• Key Features:

  • Metric: OSPF uses cost (which can be based on bandwidth, delay, etc.) as its metric to choose the shortest path.
  • Convergence: OSPF converges faster than RIP because it has a global view of the network.
  • It divides large networks into smaller areas, with Area 0 (the backbone) as the central point of communication between areas.
  • Supports both IPv4 and IPv6.

• Advantages:

  • Fast convergence and efficient in large networks.
  • Scalable and flexible with its hierarchical structure (Areas).
  • More robust than RIP, less prone to routing loops.

• Disadvantages:

  • More complex to configure and maintain.
  • Requires more memory and CPU resources.

3. EIGRP (Enhanced Interior Gateway Routing Protocol)

• Definition: EIGRP is a Hybrid Routing Protocol that combines features of both Distance Vector and Link-State protocols. It is used primarily in Cisco networks.

• Key Features:

  • Metric: EIGRP uses a combination of bandwidth, delay, load, and reliability to calculate the best route.
  • Supports IPv4 and IPv6.
  • EIGRP does not use full LSAs (like OSPF) but instead sends partial updates, meaning only changes in routing tables are shared.
  • DUAL (Diffusing Update Algorithm) is used to determine the best route and maintain loop-free paths.

• Advantages:

  • Faster convergence than RIP and OSPF.
  • More efficient updates, which reduces network traffic.
  • Easier to configure and manage than OSPF.

• Disadvantages:

  • Proprietary to Cisco (though there are some third-party implementations).
  • Requires more resources than RIP, especially in larger networks.

4. BGP (Border Gateway Protocol)

• Definition: BGP is an Exterior Gateway Protocol (EGP), used to exchange routing information between different autonomous systems (ASes) on the Internet.

• Key Features:

  • Path Vector protocol, where each BGP router maintains a path to reach the destination.
  • BGP uses AS paths and policy-based routing rather than simple metrics like hop count or cost.
  • BGP is a highly scalable protocol, designed to support the large and complex routing tables seen on the Internet.
  • Uses TCP (port 179) to establish reliable connections for routing updates.

• Advantages:

  • Extremely scalable and suitable for large networks like the Internet.
  • Allows for complex routing policies and control over path selection.
  • Provides loop prevention mechanisms.

• Disadvantages:

  • Slower convergence compared to IGPs like OSPF.
  • More complex to configure and manage.

4. Comparison of Unicast Routing Protocols

Feature	RIP	OSPF	EIGRP	BGP
Type	Distance Vector	Link-State	Hybrid	Path Vector
Metric	Hop count	Cost (bandwidth, delay)	Bandwidth, Delay, Reliability, Load	AS Path, Policy
Scalability	Limited (max 15 hops)	Scalable for large networks	Scalable, good for mid-sized networks	Highly scalable (used on the Internet)
Convergence Time	Slow	Fast	Fast	Slow
Protocol Type	Simple, less resource-intensive	Requires more memory and CPU	Moderate resources required	High resources required
Loop Prevention	Uses split horizon, poison reverse	Less prone to loops due to LSDB	DUAL algorithm for loop prevention	Uses AS path information to prevent loops
Complexity	Simple, easy to configure	Complex, requires more configuration	Moderate complexity, easier than OSPF	Complex, requires detailed policy configuration
Common Usage	Small networks	Large enterprise networks	Cisco-centric networks	Internet-wide routing, ISP-level routing

5. Choosing the Right Unicast Routing Protocol

When deciding which unicast routing protocol to use, consider the following factors:

1. Network Size:

   • RIP is best suited for small networks with fewer routers.
   • OSPF is ideal for large enterprise networks, as it scales well and offers fast convergence.
   • EIGRP is suitable for medium-sized Cisco-based networks that require faster convergence than RIP and easier configuration than OSPF.
   • BGP is used for inter-domain routing, ideal for large networks like ISPs and the Internet.

2. Scalability:

   • BGP is the most scalable and supports the vast number of routes seen on the Internet.
   • OSPF and EIGRP are both scalable within a single AS but have different complexities and resource requirements.

3. Convergence Speed:

   • OSPF and EIGRP offer fast convergence, which is essential for large networks.
   • RIP is slower to converge and can be problematic in larger networks.
   • BGP converges the slowest but is needed for Internet routing.

4. Configuration and Maintenance:

   • RIP is easiest to configure but limited in scale.
   • OSPF and EIGRP are more complex but offer better scalability and performance.
   • BGP is highly configurable but is also the most complex to manage.

⭐Congestion Control

Congestion Control refers to the mechanisms used to detect, prevent, and manage network congestion (i.e., situations where network resources, such as bandwidth, buffers, and links, are overwhelmed with traffic). When congestion occurs, data packets may be delayed, lost, or dropped, affecting the performance of the network.

The Network Layer handles congestion control in a variety of ways, using both preventive and reactive strategies. While congestion control primarily involves protocols like TCP at the Transport Layer, the Network Layer also plays a significant role by using algorithms to manage traffic and avoid bottlenecks.

---

1. Definition of Congestion Control

• Congestion occurs when the network or any of its routers/links becomes overwhelmed by the volume of data.
• The goal of Congestion Control is to maintain the efficient functioning of the network by preventing overload and minimizing packet loss, delays, and throughput degradation.

2. Causes of Network Congestion

• High Traffic Load: More data is transmitted than the network can handle (e.g., too many simultaneous users or applications).
• Insufficient Bandwidth: The available network bandwidth is insufficient to accommodate the current traffic load.
• Router Buffer Overload: Routers and switches have finite buffer space, which can fill up, causing packet loss.
• Routing Inefficiencies: Poorly configured or inefficient routing algorithms can cause congestion by directing traffic through suboptimal paths.
• Protocol Overhead: In some cases, excessive protocol overhead can reduce the overall throughput and contribute to congestion.

3. Goals of Congestion Control

• Prevent Congestion: By detecting signs of congestion early, actions can be taken to avoid network overload.
• Mitigate the Impact: In cases of congestion, reducing its impact (e.g., lowering packet loss, minimizing delays) ensures the network's performance stays optimal.
• Maximize Utilization: Efficiently using available bandwidth without overloading network resources.
• Fairness: Ensure that no single flow (user or application) monopolizes the network resources.

4. Congestion Control Algorithms

There are several algorithms and techniques employed in the Network Layer to prevent or manage congestion. These algorithms focus on controlling the amount of traffic injected into the network to avoid congestion situations.

1. Traffic Shaping and Policing

• Traffic Shaping: This involves controlling the rate at which packets are sent into the network to smooth out traffic flow.

  • Token Bucket Algorithm: Traffic is allowed to flow at a steady rate. Tokens are generated at a fixed rate, and each packet requires a token to be sent.
  • Leaky Bucket Algorithm: Traffic is sent at a fixed rate, and any excess traffic is discarded or delayed. The "leak" represents the rate at which traffic is allowed out of the bucket.

• Traffic Policing: Traffic policing involves enforcing traffic flow policies by marking or dropping packets that exceed certain thresholds (e.g., rate limits).

  • A policer checks incoming packets and either allows, delays, or discards them if they exceed the defined rate limit.

2. Queue Management Algorithms

Routers use queues to buffer packets before forwarding them. When the queues become full, packets may be dropped, leading to congestion.

• Random Early Detection (RED):

  • RED is a congestion avoidance algorithm where packets are dropped or marked with increasing probability as the queue fills up.
  • The goal is to notify the sender early before the queue becomes completely full, allowing the sender to slow down.
  • Benefits: RED prevents buffer overflow, reduces delay, and avoids global synchronization (where all flows slow down simultaneously).

• Weighted Random Early Detection (WRED):

  • Similar to RED but with the added feature of prioritizing different types of traffic. For example, high-priority traffic (e.g., voice or video) is less likely to be dropped than low-priority traffic.
  • WRED helps in managing different traffic types in a congestion-prone network.

• Active Queue Management (AQM):

  • AQM is a broader class of algorithms that include RED and WRED. The goal is to keep the queue length small and reduce the delay by actively managing packet arrival and drops.
  • By actively monitoring queue lengths, AQM can help reduce congestion and enhance performance.

3. Explicit Congestion Notification (ECN)

• ECN is a mechanism that helps routers signal congestion to end systems without dropping packets.
• When a router detects that its queue is becoming congested, it marks packets with an ECN flag rather than dropping them.
• ECN Capable Endpoints (ECE) are able to detect this signal and adjust their transmission rate accordingly (e.g., reducing the sending window).
• Benefits: ECN provides a more efficient way to handle congestion by reducing the need for packet drops, thus improving overall network efficiency.

4. TCP Congestion Control Mechanisms

Though TCP operates at the Transport Layer, it plays an essential role in congestion control by responding to network congestion signals. Several techniques are used:

• Slow Start:

  • TCP begins transmission with a small congestion window (CWND) and increases it exponentially until it detects congestion.
  • This helps avoid overwhelming the network when the connection starts.

• Congestion Avoidance:

  • Once TCP detects congestion (via packet loss or ECN), it switches to congestion avoidance mode, where the CWND is increased linearly instead of exponentially, thus avoiding rapid increases in traffic.

• Fast Retransmit and Fast Recovery:

  • When TCP detects packet loss (through triple duplicate ACKs), it retransmits the missing packet and reduces the congestion window to avoid further congestion.
  • Fast Recovery allows TCP to recover quickly after packet loss by adjusting the CWND without going back to slow start.

• Additive Increase, Multiplicative Decrease (AIMD):

  • This is the algorithm used in TCP for adjusting the CWND. When congestion is not detected, the window increases by a small, fixed amount (additive increase), but when congestion is detected, it reduces the window significantly (multiplicative decrease).

5. Congestion Control in IP Networks

• IP Layer's Role: The IP layer mainly relies on feedback from higher layers (like TCP or ECN signals) to manage congestion.
• IP Congestion Control is concerned with managing the flow of packets across routers and ensuring that no single path gets overwhelmed.
• Algorithms like RED or ECN are often implemented in the routers to manage congestion at the network level, but their effectiveness depends on the end-to-end mechanisms that operate at higher layers.

6. Comparison of Congestion Control Techniques

Technique	Description	Advantages	Disadvantages
Traffic Shaping	Controls the rate of traffic injection into the network.	Reduces burstiness, smooths out traffic flow.	Can introduce delays, complex to configure.
Traffic Policing	Enforces traffic flow policies by dropping or marking packets.	Prevents overuse of network resources.	Can discard legitimate traffic, leading to packet loss.
Queue Management (RED/WRED)	Actively manages queue lengths, dropping packets when necessary.	Reduces delay and prevents buffer overflow.	Requires router support and careful tuning.
ECN (Explicit Congestion Notification)	Signals congestion to endpoints without dropping packets.	More efficient than packet drops, reduces packet loss.	Requires support from end systems.
TCP Congestion Control	Uses slow start, congestion avoidance, and AIMD to manage flow.	Highly adaptive to network conditions.	Relies on packet loss or delays to trigger adjustments.

---

🚨Thanks for visiting classpdfindia✨

Welcome to a hub for 😇Nerds and knowledge seekers! Here, you'll find everything you need to stay updated on education, notes, books, and daily trends.

💗 Bookmark our site to stay connected and never miss an update!

💌 Have suggestions or need more content? Drop a comment below, and let us know what topics you'd like to see next! Your support means the world to us. 😍