Network Routing
Part III — Types of Routing Protocols (Distance Vector)
Introduction
Are you a flight person; you like to get to your destination quickly, despite having to pay a little bit more on fares? Or, are you a train person; you don’t mind getting to your destination slightly late to save on fares? In truth, there are more contexts to consider in planning our transportations, like possible delays, safety, and the comfort of the journey. Anyway, either ways works; because in the end we will still show up at our destination (perhaps at different timing).
It turns out, network packets have the same dilemma like us. They too, have to choose a path to travel from source to destination. Technically, it is the routers who decide for the packet; on which is the ‘best’ path to take. How is ‘best’ defined here? — that depends on the types of routing protocols that are deciding for the packets; and that too depends on what kind of routing are configured onto the routers. There are two types of routing protocols commonly used on the Internet; namely: distance vector and link state protocols. Here’s the comparison between them. We will discuss each of these traits in length with intuitive examples.
In this story, we will first learn about the distance vector protocol.
Distance Vector (DV) Routing Protocols
We refers to Distance Vector as DV from here onwards. As the name implies, DV chooses the best path based on the ‘distance’ metric. The distance is represented as hops count in computer networks. The goal of DV is to choose the path that consists the least number of hops (or routers) from the source to the destination (regardless of other metrics like link speed). The ‘shortest’ path is selected by the Bellman Ford algorithm. DV is comparably simpler to configure; but due to it naive nature (who says link speed is not important?), it might not give the best routing performance. Some popular DV protocols used these days are RIPv1, RIPv2, RIPv6. We will discuss each properties of DV in length next.
Route Selection
DV chooses the path with the least number of hops. Consider the network below with two paths:
(a) upper path from EdgeRouter1 → CoreRouter1 → Core Router2 → EdgeRouter2(b) bottom path from EdgeRouter1 → CoreRouter3 → CoreRouter4 →CoreRouter5 → EdgeRouter2
If DV protocol is configured on all of these routers; intuitively DV will choose the upper path simply because it has less number of routers (hops) from source to destination compared to the bottom path. For a more complex example, we need to calculate the hop counts for each path before deciding.
So, what is hop count? — a hop count is value used to keep track on how many routers (or networks) has a packet traversed. Hop count is similar to the time-to-live (TTL) value in the IP header of network packets. A packet can start with a TTL value of 128; every time this packet go pass a router, this value is decremented by 1; to 127, 126,125 and so on. It this value reaches 0 before the packet arrive at the destination; this packet will be discarded. In context of routing, hop count is simply counting how many {router — router} pairs are there in the topology. For example,
There is ONE hop in this topology:
This are TWO hops in this topology:
Based on this, we can calculate the total hop counts for both of the paths shown in the main network topology. The Bellman Ford algorithm simply select the path based on the MIN value of the hop count among all available paths. Here, the BLUE (with hop count=3) is selected over the GREEN (with hop count=4).
Note: the hop count is calculated from the end device (start point) in yellow LAN to the end device (end point) in the blue LAN.
Topology View
DV routers only ‘see’ as far as their next hop. This means that if DV is used; a router only know the routing information (as in routing table) of all the neigbouring routers that are directly connected to it. Routing table is only exchanged with adjacent router. The figure below shows the ‘visible’ view of Router1; the networks that are learnable is shown in green; while the networks that are not learnable is shown in blue.
In short, DV only sees the ‘neighbourhood’ view of the network topology, but not the entire network topology leading to the destination network.
Now, you might wonder how can Router1 know the best path to a destination far far away; if it does not know the routes beyond his neigbhour? — the magic lies in the routing table of DV. In the hop count field; this value is the aggregated values of all hop counts towards a specific destination. Although Router1 does know know how the network looks like beyond its neighbour, but its neighbour does; and the neighbour of its neighbour does too. This means the hop count to a remote network is the sum of all hops (number of routers) towards the destination network.
Routes Update (Table Exchange)
DV routers update topology information through routing table exchanges. The routing table of each router is sent to ALL neigbhours routers in broadcast. During the broadcast, the FULL table is exchanged (instead of delta update). This means that DV has high network overhead for routing updates. These routing updates happen periodically; instead of being triggered. This means that if a route go offline before the next update; this broken route will still be used for packet routing (that leads to ‘destination unreachable’ error message). When all routing tables exchange are completed; and the entries in the table stabilised; then we say that the network has reached full convergence.
Here’s a simple video to explains the process of routes updates in distance vector protocols.
Timers in RIPv1
We use RIPv1 to explain the periodicity traits in distance vector protocols. In RIPv1, there are three important timer: (a) the update timer — 30seconds, (b) the hold out timer — 180 seconds and (c) the time-out timer — 120 seconds. Consider a simple RIPv1 network with 3 routers as shown:
Looking at RouterA, suppose that the route from LAN1 to LAN3 (the link between RouterA → RouterC) is down. We know that LAN1 can still reach LAN3 via RouterB using the link RouterA →RouterB →RouterC after RouterA is informed about the link failure. Now, let’s take a look at how these timers come into play for this changes to happen.
Time Point [1]
Let’s assume that port on RouterC is damaged; thus, the link between RouterA →RouterC is down. First, RouterC will update its own routing table to indicate this change. Here, RouterC remove the first entry in the table because it can no longer directly reach LAN1 via RouterA. This is the updated table of RouterC to reflect the network changes. The bad link is flagged as ‘unusable’ for 180s. This changes is not informed to RouterB and RouterA immediately. DV only exchange routing table every 30s.
Time Point [2]
RouterC sends update:
After 30s (from the last update), RouterC sends this NEW routing table out to RouterB and RouterA. RouterA and RouterB updates their table accordingly to reflect this change. This are the new tables for RouterA and RouterB. For RouterA, the last entry is removed because the link is down. For RouterB, notice that they are no changes made (because the broken link is never in its routing table).
RouterB sends update:
At the same time, RouterB sends it routing table to RouterA and RouterC.
RouterA learnt that RouterB knows how to get to LAN3 (which is currently ‘?’ in its table). RouterA update its routing table to LAN3 via RouterB. After this update, LAN1 will go to LAN3 using the new path of RouterA →RouterB →RouterC. This is the new RouterA’s table. Notice that the hop count from LAN1 to LAN3 is ‘2’ instead of ‘1’.
RouterC learnt that RouterB knows how to get to LAN1 (which is currently ‘?’ in its routing table). RouterC updates its routing table to LAN1 via RouterB. After this update, LAN3 will go to LAN1 using the new path of RouterC →RouterB →RouterA. This is RouterC’s new table.
RouterA sends update:
At the same time, RouterA sends its routing table to RouterB and RouterC. By this time, all the best path is already updated in the routing tables of all routers. So, there are no new changes made to any of the routing table here.
Time Point [3]
The bad path will be kept in RouterA’s and RouterC’s table for 180 seconds. During these time, the link between RouterA →RouterC is flagged as ‘unusable’. This hold out timer is added to prevent a temporary failure to propagate to all the routers in the network.
Time Point [4]
After additional 120s starting from time point [3]the bad path is removed from the routing table entirely if it still does not recover. This is to prevent bad routes to be maintained to keep the routing tables small. The entire duration for a bad path to be detected until removal is 300 seconds. The routing table is trimmed to only contains usable routes like this:
See the timeline below for the important checkpoint in RIPv1 table updates.
Network Performance
‘Should I configure a distance vector or a link-state protocol on the routers?’ has probably been asked a million times. The short answer is — it depends on the routing requirements of the underlying networks. When it comes to routing configurations; it isn’t so much on right or wrong choices (every protocols have different use case); but rather the right or wrong configurations.
To make these choices easier, let’s look at a few important performance metrics of DV:
(A) Speed — Routing Table Convergence
A distance vector protocol has comparably slower convergence to its link-state counterparts. For example, RIPv1 takes 300s to fully converged from the point of any network changes. This is because DV updates periodically by design. The timer value has been set as such: 30s as updates interval, 180s to flag route as unusable and 120s to remove bad routes. These are defaults values; they can be reconfigured to shorter intervals; but these changes need to be consistent across all participating neighbour routers (to prevent split horizon & infinity loop problems). This also means that, for any link changes; it would take approximately 300s for the changes to take effect in the neighbour routers. Comparably, a link state protocol like OSPF updates as soon as there is a changes in the link through triggered updates.
Winner: Link-State
(B) Lightweight — Resources Utilisation
Distance vector normally is more lightweight computationally compared to link state. This means that it consume less router’s compute resources in terms of updating routing table and maintaning it. This is because DV’s entries are simpler, it includes ‘destination network’, ‘next hop’ and ‘hop count’; and no other states like ‘link speed’, ‘load’, or ‘reliability’ are involved. Since network updates are periodic with long timer intervals; the updates are generally less frequent compared to link-state. This allows more headroom for the routers to perform some other essential tasks like packet forwarding. The only drawback is DV sends full routing table during the updates; which consume more network bandwidth compared to link-state.
Winner: Distance Vector
(C) Speed — Packet Forwarding
In terms of packet forwarding, DV is slightly faster in route selection but lose out in packet transmission. Since DV only see as far as next hop; it is relatively easy for the router to choose the next hop to forward to (based on smallest hop count); whereas in link-state, the routers need to find the best path in terms of multiple link metrics of all the routers along the path. Because of this, the path chosen by DV might not actually be the ‘fastest’ path. Assuming that the least number of routers in a path to imply the path is ‘short’ means the link speed does not matter — that’s definitely not the case.
Look at the example network below. The upper path has only 3 hops to the destination, while the bottom path has 4 hops. The MIN link speed in upper path is 1Mbps; while the bottom path is 100Mbps (MIN = the smallest bandwidth throughout the path). Because DV is not aware of link state; it chooses the shorter path that is relatively slower (in terms of bandwidth). This means any bandwidth intensive sessions like Netflix’s streams might suffer (see fragmentations, MTU, network throughput) despite the packets having to travel shorter distance. In general, it is not easy to measure end to end ‘speed’ since the speediness is more of a combinations of hop counts and the states of links.
Winner: Draw
(D) Simplicity — Ease of Configurations
One of the advantage of dynamic routing over static routing is that dynamic routes are easier to configure when the networks become more complex. Both distance vector and link-state are relatively easy to configure; but if we had to pick a winner; it would be distance vector. Why? — simply because there are less parameters needed to configure a DV than a link-state protocols. In fact, we only need to specify the ‘networks that are directly connected’ to a router in a few lines to configure RIPv1.
Meanwhile, link-state protocols like OSPF requires additional parameters like the area information to work. In terms of troubleshooting, it is fairly easy to isolate problems in the networks for both types of dynamic routings.
Winner: Distance Vector
