The network needs to understand how to get packets through from one side to the other. This can be accomplished in several ways. In a simple network with only one or two routers, it is probably most efficient to configure this routing information into the routers manually. However, in a large or complex network, the routers need to learn and update routing information through the network automatically. This is particularly true for networks that offer multiple redundant paths for fault-tolerance purposes.
Dynamic routing protocols give the network a way of healing around link or equipment failures. This is because they can see all of the different paths through a network and pick the best one at any given moment. When one path becomes unusable, another is selected.
The routing of IP packets is always handled by means of a routing table. This table is basically just a list of destination networks and the next hop required to get to these destinations. It may also contain other supplemental information, such as an estimate of how much it costs to use that particular route, and it may contain several different options for directing traffic to some destinations.
This concept of the cost of a route is relatively open and vague. The cost could be a function of any number of variables, such as the number of hops, the net latency of the path, the minimum bandwidth along the path, as well as other less tangible factors. For example, it may be better to avoid a particular route because of a usage charge. Or in some cases the network administrators direct traffic through networks under their direct control, instead of using a possibly shorter path through a foreign network.
It is interesting how these routing tables come into being, how they are updated when the topology changes, and how they avoid problems like loops. Several commonly used methods keep routing tables up-to-date.
The earliest and more popular routing protocols typically used a Distance Vector Algorithm. Then Link State Algorithms became popular. I discuss one popular protocol, Border Gateway Protocol (BGP), that uses a completely different algorithm relying on a Path Vector system.
All of these algorithms fulfill two main functions. First, they allow the routers on the network to keep track of changes in the state of the network that require changing routing tables. Second, they provide a mechanism for eliminating routing loops.
A routing loop is exactly what it sounds like: one router forwards a packet to its next hop to be delivered to the eventual destination. But instead of sending the packet on, the second router just forwards it back to the first one, perhaps via other intermediate routers. This is clearly a serious problem for a network, and it is relatively easy to get such loops when the routers are responsible for figuring out for themselves how to send data through the network. This is why sophisticated algorithms are required to prevent them.
Before discussing the more sophisticated dynamic methods of maintaining routing tables through a network, I start with simple static routing. This discussion helps explain the problems that dynamic routing was developed to solve. Further, it is common in large networks to use a mixture of static and dynamic routing, so it is important to understand where each method is useful.