IP Routing Fundamentals – Routing Protocol Classes

There are two major classes of routing protocols. These two classes are the Distance Vector and Link State routing protocol classifications. 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 protocol, 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 1-2:

Fig. 1-2. Understanding Vectors

Referencing Figure 1-2, the first arrow 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 it is and how far it travels.

NOTE: Vectors can also travel in the opposite direction (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, which will be described in detail later in this guide. The SPF calculation is performed in iterations using three sets. The three sets that are used in the SPF calculation are:

1. Unknown

2. Tentative (TENT)

3. PATH

When the SPF algorithm initializes, all nodes, except for the root, which is also referred to as ‘self’, are placed in the Unknown set or list. The root is the router performing the SPF calculation. As SPF continues to run, nodes in the Unknown set are moved to the Tentative set beginning with the nodes directly connected to the root. The Tentative set is also commonly referred to simply as the TENT set or list.

As the router goes through the SPF calculation, the node in the TENT set or list that is closest to the root is moved to the PATH or PATHS list or set. This process is repeated until all nodes are in the PATH set and the shortest-path tree is built. Once the tree has been completely built, routes are then derived from the tree. This concept is illustrated referencing the basic network topology in Figure 1-3:

Fig. 1-3. Shortest Path First Algorithm

Referencing Figure 1-3, it is assumed that R1 is the router performing the SPF calculation. The following are the sequence of steps taken by this router:

1. R1 places itself in the PATH list with a next-hop of itself and a cost of 0. When R1 places itself in the PATH list, R1 is also referred to as the PATH node, in addition to being the SPF root. All other nodes or routers are temporarily placed in the Unknown set and have their cost presently set to infinity

2. R1 examines the neighbors of the PATH node (itself) and because its only neighbor is R2, R1 adds R2 to the TENT list. OSPF is able to do so by looking at the Link State Advertisement (LSA) packets that are exchanged during the database exchange and synchronization process

3. R1 calculates the cost to R2 from the PATH node. This is performed by adding the cost to the PATH node and the cost from the PATH node to the TENT node. In this example, the cost from R1 to the PATH node (itself) is 0, and the cost from the PATH node (R1) to the TENT node (R2) is 10. The total path cost to reach R2 from R1 is  0 + 10 = 10

4. Because the cost of 10 is less than the cost of infinity that was initially assigned, the infinity value is overwritten with the cost value of 10. R2 is moved to the PATH list

5. Once R2 is placed in the PATH list, it becomes the newest PATH node and the second SPF iteration begins on R1. Remember, SPF stops when all nodes are in the PATH set

6. R1 examines the neighbors of the new PATH node (R2), which are R3 and itself. Because R1 is already added to the PATH list (in step 1) it is ignored. R3, however, is moved from the Unknown set to the TENT set

7. R1 calculates the cost to R3 by adding the cost to the PATH node (R2) and the cost from the PATH node (R2) to the TENT node (R3). The cost from R1 to the PATH node (R2) is 10, and the cost from the PATH node to the TENT node (R2) is 10. The total path cost to reach R3 from R1 is 10 + 10 = 20

8. Because the cost of 20 is less than the cost of infinity that was initially assigned, the infinity value is overwritten with the cost value of 20. R3 is moved to the PATH list

This process is repeated until there are no more routers in the TENT list on any of the routers participating in OSPF. Figure 1-4 shows the SPF tree as it would appear on routers R1 and R2:

Fig. 1-4. SPF Tree on R1 and R2

Referencing the diagram in Figure 1-4, notice that the tree is built on the perspective of the root, which is the local router itself. Figure 1-5 shows the SPF tree as it would appear on R3 and R4:

Fig. 1-5. SPF Tree on R3 and R4

Distance Vector Routing Protocols

A Distance Vector protocol is a routing protocol that uses distance or hop count as its primary metric for determining the best forwarding path. Distance Vector protocols are primarily based on the Bellman-Ford algorithm. Distance Vector routing protocols periodically send their neighbor 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 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

Utilizing the counting to infinity characteristic, if a destination network is more than the maximum number of hops allowed for that routing protocol, it 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, however, 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 for 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 that 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, which uses both Distance Vector and Link State features, is an advanced Distance Vector routing 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. Routing 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 forward 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 neighboring routers are synchronized, the routers are said to be adjacent.

Unlike Distance Vector routing protocols which send their neighbors 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 this converge in a shorter amount of time than Distance Vector routing protocols. Table 1-2 lists the different Interior Gateway Protocols (IGPs) and their classification:

Tab.1-2. IGP Classification

NOTE: Although the Border Gateway Protocol (BGP) uses the autonomous system path or AS PATH to determine the best path to a destination network, it is not considered a Distance Vector routing protocol. BGP is referred to as a Path Vector protocol, which is a derivative of Distance Vector routing protocols. Unlike RIP, for example, the BGP path selection process is complex and detailed and is not entirely based on the AS PATH. Border Gateway Protocol is a core ROUTE requirement. This protocol will therefore be described in detail later in this guide.