Routing Protocol Classes

There are two major classes of routing protocols – Distance Vector and Link State. Distance Vector routing protocols traditionally use a one-dimensional vector when determining the most optimal path(s) through the network, while Link State routing protocols use the Shortest Path First (SPF) when determining the most optimal path(s) through the network. Before delving into the specifics of these two classes of routing protocols, we will first take a look at vectors, as well as at the elusive SPF algorithm.

Understanding Vectors

A one-dimensional vector is a directed quantity. It is simply a quantity (number) in a particular direction or course. The vector concept is illustrated in Figure 10.11 below:

Figure 10.11 – Understanding Vectors

Referencing Figure 10.11, the first line starts at 0 and ends at 8, and the second line begins at 8 and ends at 13. The vector for the first line is 8, while the vector for the second line is 5. Using basic math, we know that 8 + 5 = 13. The starting and ending points of the vector are not relevant. Instead, the only thing that actually matters is how long the vector is and how far it travels.

NOTE: Vectors can also travel in the opposite direction (i.e., they represent negative numbers).

The Shortest Path First Algorithm

The SPF algorithm creates a shortest-path tree to all hosts in an area or in the network backbone with the router that is performing the calculation at the root of that tree. In order for the SPF algorithm to work in the correct manner, all routers in the area should have the same database information. In OSPF, this is performed via the database exchange process.

Distance Vector Routing Protocols

Distance Vector is a routing protocol that uses distance or hop count as its primary metric for determining the best forwarding path. Distance Vector routing protocols are primarily based on the Bellman-Ford algorithm. Distance Vector routing protocols periodically send their neighbour routers copies of their entire routing tables to keep them up to date on the state of the network. While this may be acceptable in a small network, it increases the amount of traffic that is sent across networks as the size of the network grows. All Distance Vector routing protocols share the following characteristics:

• Counting to infinity
• Split horizon
• Poison reverse
• Hold-down timers

Utilising the counting to infinity characteristic, if a destination network is farther than the maximum number of hops allowed for that routing protocol, the network would be considered unreachable. The network entry would therefore not be installed into the IP routing table.

Split horizon mandates that routing information cannot be sent back out of the same interface through which it was received. This prevents the re-advertising of information back to the source from which it was learned. While this characteristic is a great loop prevention mechanism, it is also a significant drawback, especially in hub-and-spoke networks.

Poison reverse (or route poisoning) expands on split horizon. When used in conjunction with split horizon, poison reverse allows the networks to be advertised back out of the same interface on which they were received. However, poison reverse causes the router to advertise these networks back to the sending router with a metric of “unreachable” so that the router that receives those entries will not add them back into its routing table.

Hold-down timers are used to prevent networks that were previously advertised as down from being placed back into the routing table. When a router receives an update that a network is down, it begins its hold-down timer. This timer tells the router to wait for a specific amount of time before accepting any changes to the status of that network.

During the hold-down period, the router suppresses the network and prevents advertising false information. The router also does not route to the unreachable network, even if it receives information from another router (that may not have received the triggered update) that the network is reachable. This mechanism is designed to prevent black-holing traffic.

The two most common Distance Vector routing protocols are RIP and IGRP. EIGRP is an advanced Distance Vector routing protocol, using features from both Distance Vector and Link State (i.e., it’s a hybrid protocol).

Link State Routing Protocols

Link State routing protocols are hierarchical routing protocols that use the concept of areas to logically group routers within a network. This allows Link State protocols to scale better and operate in a more efficient manner than Distance Vector routing protocols. Routers running Link State routing protocols create a database that comprises the complete topology of the network. This allows all routers within the same area to have the same view of the network.

Because all routers in the network have the same view of the network, the most optimal paths are used for forwarding packets between networks and the possibility of routing loops is eliminated. Therefore, techniques such as split horizon and route poisoning do not apply to Link State routing protocols as they do to Distance Vector routing protocols.

Link State routing protocols operate by sending Link State Advertisements or Link State Packets to all other routers within the same area. These packets include information on attached interfaces, metrics, and other variables. As the routers accumulate this information, they run the SPF algorithm and calculate the shortest (best) path to each router and destination network. Using the received Link State information, routers build the Link State Database (LSDB). When the LSDBs of two neighbouring routers are synchronised, the routers are said to be adjacent.

Unlike Distance Vector routing protocols, which send their neighbours their entire routing table, Link State routing protocols send incremental updates when a change in the network topology is detected, which makes them more efficient in larger networks. The use of incremental updates also allows Link State routing protocols to respond much faster to network changes and thus converge in a shorter amount of time than Distance Vector routing protocols. Table 10.4 below lists the different Interior Gateway Protocols (IGPs) and their classification:

Table 10.4 – IGP Classification