Lecture #6 - Dynamic Routing Protocols

At minimum, a routing protocol needs to provide mechanisms for achieving the following:

• Sending reachability information to other routers.
• Receiving reachability information from other routers.
• Determining the optimal route to a network.
• Determining how to react to topology changes within the network.

Routing protocols can be broadly classified into:

• Interior protocols - used inside an Autonomous System (AS).
• Exterior protocols - used to route between ASs.

Path Determination

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.

Metrics

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:

Hop Count

This metric is simply the number of routers that would need to be crossed ("hopped") in order to reach the destination. A low hop count will provide the route with the fewest number of routers, however it may not always be the best path (consider a three hop path over a 256Kbps link versus a five hop path over a 2Mbps link).

Bandwidth

Each interface along a path has an associated bandwidth, hence the path with the highest bandwidth could be selected as the preferred path. Following on from the previous example, this would then select the 2Mbps rather than the 256Kbps link. However, the 2Mbps link may have a much higher delay (eg. it might be a satellite link) or it may be already heavily loaded with traffic.

Delay

The delay for a path can either be measured or estimated in a number of ways. For example, we could use the Round Trip Time (RTT) which would include propagation delay, queueing delay and processing delay for each link along the path. Or we could use an estimated delay as configured by the network administrator. The path with the lower delay would then be preferred over a path with a higher delay.

Reliability

How reliable have the links along this path been? Have links along this path dropped or have they exhibited a high Bit Error Rate (BER)? The route that is more reliable would obviously be selected over one that has been less reliable.

Load

How much traffic is currently being sent over (or queued to be sent over) this path? Load is an interesting metric since it will vary significantly during operation. This may allow the router to offload some traffic onto a less preferred route, in order to reduce the load on a specific link. Care must be taken with this metric due to the fact that it will change depending on network traffic - this could lead to route "flapping" whereby the router flaps back and forth between two routes.

Cost

The cost of a path is a dimensionless metric - in other words it is an arbitrary value specified by the network administrator. This may be used to influence path selection based on the network administrator's knowledge of the network, or due to external policies and real world costs.

Convergence

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.

Distance Vector Routing

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:

• Periodic updates - updates to routing information are sent at regular intervals.
• Most updates provide a full copy of the router's current routing table.
• Updates are typically broadcast to all nodes on the local network. Some protocols can be configured to only send the information to specific neighbouring routers.

Distance Vector - Routing by Rumour

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 and Split Horizon

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.

Count to Infinity

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).

Route Invalidation

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.

Link State Routing

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 Protocol Operation

Link state routing protocols are more complex than their distance vector based counterparts. However, the general operation is as follows:

1. Each router establishes a relationship or adjacency with each of its neighbours.
2. Each router sends LSAs to each of its neighbours, who in turn forward the LSAs on to its own neighbours - this process is known as "flooding". Each router in the network should receive a copy of the LSA.
3. Each router stores a copy of the received LSAs in a local topological database. If the flooding process has worked correctly, each router will have an identical database.
4. The contents of the topological database is used to generate a graph of the network, determining the shortest path to each router. Combined with the link state and network information, appropriate routes can now be entered into the routing table.

Link State Advantages and Issues

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!

References

Cisco Press: Dynamic Routing Protocols