WikiGalaxy
Distance Vector Routing Basics
Overview:
Distance Vector Routing is a dynamic routing protocol that calculates the best path for data transmission by considering the distance to the destination. It uses algorithms like Bellman-Ford to determine the shortest path.
Key Characteristics:
Each router maintains a table (vector) that holds the distance to each network node. Routers periodically exchange information with their immediate neighbors to update these tables.
Advantages:
Simple to implement and manage, making it suitable for small networks.
Disadvantages:
Prone to routing loops and convergence issues, which can lead to inefficiencies in larger networks.
// Example of Distance Vector Table
Router A: {B: 2, C: 5, D: 1}
Router B: {A: 2, C: 3, D: 2}
Router C: {A: 5, B: 3, D: 2}
Router D: {A: 1, B: 2, C: 2}
Convergence:
Convergence is achieved when all routers have a consistent view of the network. It can be slow in Distance Vector protocols, especially in large networks.
Split Horizon:
A technique used to prevent routing loops by prohibiting a router from advertising a route back on the interface from which it was learned.
Console Output:
Router A: {B: 2, C: 5, D: 1}
Bellman-Ford Algorithm
Algorithm Basics:
The Bellman-Ford algorithm is used to find the shortest paths from a single source vertex to all other vertices in a weighted graph. It is particularly useful for graphs with negative weight edges.
Working Principle:
The algorithm iteratively relaxes edges, updating the distance to each vertex until no further improvements can be made.
Complexity:
The time complexity of Bellman-Ford is O(V*E), where V is the number of vertices and E is the number of edges.
// Pseudo-code for Bellman-Ford Algorithm
function BellmanFord(G, S)
for each vertex V in G
distance[V] <- INFINITY
predecessor[V] <- null
distance[S] <- 0
for i from 1 to size(G)-1
for each edge (U, V) with weight W in G
if distance[U] + W < distance[V]
distance[V] <- distance[U] + W
predecessor[V] <- U
Negative Weight Cycles:
The algorithm can detect negative weight cycles, which are cycles that reduce the total path distance indefinitely.
Use Cases:
Bellman-Ford is used in networking to calculate routes in Distance Vector protocols and to handle cases with negative weights.
Console Output:
Shortest path distances updated.
Routing Information Protocol (RIP)
Introduction:
RIP is one of the oldest distance-vector routing protocols, designed for smaller networks. It uses hop count as a routing metric.
Hop Count Limit:
The maximum number of hops allowed in RIP is 15, which limits its use to smaller networks.
Periodic Updates:
RIP routers send updates every 30 seconds, which can lead to slow convergence times.
// Example RIP Configuration
router rip
version 2
network 192.168.1.0
network 10.0.0.0
Split Horizon and Poison Reverse:
Techniques used in RIP to prevent routing loops by controlling the advertisement of routes.
RIP Versions:
RIP has two versions: RIP version 1 (RIPv1) and RIP version 2 (RIPv2), with RIPv2 supporting subnet masks and authentication.
Console Output:
RIP routing table updated.
Count to Infinity Problem
Problem Description:
In Distance Vector Routing, the count to infinity problem occurs when routers continuously increase the distance metric for a destination due to a broken link, leading to slow convergence.
Illustration:
Consider a network with routers A, B, and C. If the link between A and B fails, A may incorrectly believe it can reach B through C, causing the distance to increment indefinitely.
// Pseudo-code illustrating count to infinity
Router A: {B: 1, C: 2}
Router B: {A: 1, C: 1}
Router C: {A: 2, B: 1}
// Link between A and B fails
Router A updates: {B: 16, C: 2} (infinity)
Solutions:
Solutions include split horizon, route poisoning, and hold-down timers to prevent incorrect route propagation.
Console Output:
Distance to B: Infinity
Link-State vs Distance Vector
Comparison Overview:
Link-State and Distance Vector are two main types of routing protocols used in networks. Each has its unique approach to finding the optimal path for data packets.
Link-State Protocols:
Link-State protocols, like OSPF, maintain a complete map of the network topology and use Dijkstra's algorithm to compute the shortest path tree.
Distance Vector Protocols:
Distance Vector protocols, such as RIP, rely on information from neighboring routers to update their routing tables.
// Key Differences
Link-State: Complete network view, faster convergence
Distance Vector: Simpler, suitable for smaller networks
Scalability:
Link-State protocols are more scalable and suitable for larger networks, while Distance Vector protocols are easier to implement in smaller networks.
Convergence Time:
Link-State protocols typically achieve faster convergence compared to Distance Vector protocols.
Console Output:
Comparison complete.
Route Poisoning and Hold-Down Timers
Route Poisoning:
Route poisoning is a method to prevent routing loops by setting the distance to an unreachable destination to infinity, effectively removing the route from the table.
Hold-Down Timers:
Hold-down timers temporarily suppresses updates for a route to ensure that the network has stabilized before accepting new information.
// Route Poisoning Example
Router A detects failure
Advertises route to B as 16 (infinity)
// Hold-Down Timer Example
Router A ignores updates for 180 seconds
Benefits:
These techniques help stabilize the network by preventing incorrect routing information from propagating.
Console Output:
Route poisoned and timer set.
Triggered Updates
Concept:
Triggered updates are immediate routing updates sent when a network topology change is detected, rather than waiting for the regular update interval.
Purpose:
The primary purpose is to speed up convergence by quickly informing all routers of changes, thus reducing the time it takes for the network to stabilize.
// Example of Triggered Update
Link failure detected
Immediate update sent to neighbors
Advantages:
Triggered updates help minimize the duration of routing loops and improve the overall responsiveness of the network.
Console Output:
Triggered update sent.
Poison Reverse
Mechanism:
Poison reverse is a technique where a router advertises a route back to the originating router with an infinite metric, effectively telling the neighbor that the route is unreachable.
Role in Loop Prevention:
This mechanism helps in preventing routing loops by ensuring that a router does not use a failed route through its neighbor.
// Poison Reverse Example
Router A informs B that route to C is 16 (infinity)
Implementation:
Poison reverse is often used in conjunction with split horizon to enhance loop prevention capabilities.
Console Output:
Route to C poisoned.
