Routing Algorithms

Routing is the core function of the Network Layer. It is the process of selecting a path across one or more networks for traffic to travel. The devices that perform routing are called routers. Each router maintains a routing table, which is a list of network destinations and the next 'hop' (the next router) to send a packet to in order to reach that destination. The intelligence behind how these routing tables are built comes from routing algorithms. Routing algorithms can be broadly categorized into two types: Distance Vector and Link State. Distance Vector algorithms (e.g., used by RIP) require each router to inform its neighbors of its routing table. Each router knows the distance (metric, like hop count) and the vector (next-hop router) to each destination. The main issue with this approach is the 'routing by rumor' problem, where a router only knows what its neighbors tell it, which can lead to slow convergence after a network change. Link State algorithms (e.g., used by OSPF) take a different approach. Each router constructs a complete map of the network's topology. It does this by broadcasting information about its own state (its identity, which other routers it's connected to, and the cost of those links) to all other routers on the network. With a complete map, each router can then independently run an algorithm, like Dijkstra's shortest path first algorithm, to calculate the best path from itself to every other destination. This approach converges much faster and is more robust.