A dynamic routing protocol provides a mechanism for routers to share knowledge about the network topology and available routes, and allows routing tables to be automatically constructed.
The routing protocol needs to provide a way for the router to select the best path to a destination and it must automatically react to changes within network topology (eg. a link becomes unavailable, or a new network is connected to a router). It also defines how messages will be passed between routers and the algorithm that each router will to use in order to determine optimal routes.
At minimum, a routing protocol needs to provide mechanisms for achieving the following:
Routing protocols can be broadly classified into:
When a router is configured it knows about the networks that are directly connected to it. However, how does it learn about other networks that are not directly connected to it (ie. those that are directly connected to other routers)?
In order for routers to determine available paths they need to exchange information about directly connected and otherwise reachable networks. This becomes a fairly significant challenge. Part of this challenge relates to the fact that we may receive reachability information about the same networks from multiple routers.
How do we share reachability information? Should the router forward on routing information that it has received from other routers? What should we do if we receive reachability information for a network that we already know about? How do we determine a path to a given network? What if we know about more than one way to reach the same destination?
A routing protocol will address each of these issues in some manner, defining an algorithm or process that is to be followed by each router.
When only a single route is available to a given network, we have no option but to use it if we wish to deliver traffic to that network. In the case when there are multiple routes, how should the routing protocol determine which one is "best"?
Routing protocols will make use of one or more metrics, allowing a rank or preferred order to be established. Possible routing metrics include:
One of the biggest challenges with dynamic routing protocols is that of convergence. In other words, how long will it take for a routing change to propagate from one part of the network, to the rest of the network?
When a new network is configured on a router, every other router must learn about this new network. In order for this to occur the routers must share routing information regarding the new network and potentially recalculate the preferred route.
The same problem occurs when a link becomes unavailable and the associated network becomes unreachable. This change must be propagated to all other routers - until then not all routers have the same view of the network topology and routing tables are potentially inconsistent. With some routing protocols this can take a significant amount of time, during which incorrect routing decisions will be made.
Routing protocols generally fall into one of two categories - Distance Vector or Link State. Distance vector routing protocols are often far less complex than link state protocols and work well in certain configurations, however as we will shortly see there are a number of inherent design issues.
A distance vector protocol provides two pieces of information for each route - a distance (routing metric) and a direction (next hop). Often the next hop is implied as the router that is sending the routing information.
Distance vector routing protocols typically have the following characteristics:
One of the key aspects of a distance vector routing protocol is that we are simply routing-by-rumour - that is we are relying on our neighbouring routers to provide us with accurate information.
This process simplifies things since we do not need to know about the entire network topology, however it also leads to problems due to the fact that we can only believe what we are told and have no way to verify that this information is correct.
At periodic intervals each router will inform its neighbours of routes that it knows about. Routers receiving these messages can then update their own routing tables using the information that has just been provided to it.
Routing loops can easily occur in distance vector routing protocols. If a link becomes unavailable (disconnected) the router (R1) will remove the route from it's routing table and this information will be broadcast to neighbours during the next update interval. However, let's assume that before this router gets to broadcast this information, another router (R2) sends an update - this update will state that it can reach the network that is now unreachable from R1, even though R2's route was via R1. R1 updates it's routing table with this newly learned route and we have just created a routing loop!
One way to reduce the likelihood of this problem occurring is to implement split horizon - this means that we never send information about routes back to where they came from. In this case R2 learned about the route to this network from R1, hence updates sent out this interface should not include this route, thus avoiding the creation of a routing loop.
A slight variation on this theme is split horizon with poisoned reverse - in this case rather than simply omitting the routes from the routing update we include them however ensure that they are flagged as being unreachable. This has the benefit of being able to stop routing loops and correct inaccurate information that has already been entered within a router's routing table. The trade off is larger routing messages and therefore more traffic on the network.
Whilst the implementation of split horizon with poisoned reverse will break routing loops between neighbours, they will not prevent routing loops within a network.
When a physical loop exists within a network, a link failure may result in several routers learning that the network is unreachable. However, before this unreachable information is propagated to the rest of the routers, another router may send a routing update advertising this network (even though this is via a router that just learned that it is unavailable). This can lead to a situation whereby the updates continue to loop around the network and at each router the distance is increased - this continues indefinitely.
The only real solution to this problem is to define a value for infinity - most distance vector routing protocols specify infinity as being 16 hops. This means that a looping update will eventually have a distance that is considered to be infinity and hence the route is considered to be unreachable. This is the same method used to advertise the fact that a network is no longer reachable - we simply advertise the route with a distance of infinity (or 16 hops).
Another problem with distance vector routing protocols is that of knowing when routes are no longer valid. For example, if we turn off a router then obviously the routes via it are no longer reachable. However, it will not be sending updates to advertise of this fact.
This problem is addressed via the use of route invalidation timers - each route within our routing table is only considered to be valid for a set period of time. If we do not receive an additional routing update with this route within this period we mark the route as being invalid. If an update is received the timer is reset, denoting that the route is still current.
Distance vector protocols are prone to making bad routing decisions since they are only working with information received from a neighbouring router, not the router to which the network is directly connected. Since we are routing-by-rumour, we have know way of knowing if the information we've been told is accurate. As previously mentioned, this leads to problems such as routing loops and count-to-infinity.
Link state protocols only present information about directly connected networks and the state of each link (hence the name). This data is presented to neighbouring routers in the form of a Link State Advertisement or LSA. Each neighbouring router stores a complete copy of the LSA in its database, before forwarding a copy of the LSA to its neighbours. Unlike distance vector protocols this data is not modified.
Link state routing protocols are more complex than their distance vector based counterparts. However, the general operation is as follows:
This obviously requires that we know who our neighbours are - this is determined via a neighbour discovery or "hello" protocol.
LSAs are only sent when the state of a link changes and they only detail the single link. As a result, changes are immediately propagated to the network resulting in a faster convergence time. Traffic is also reduced since we are not broadcasting full routing tables at regular intervals.
There are a number of issues regarding the implementation of flooding and LSAs which are somewhat outside the scope of this subject. We'll return to them if we get time!