1.9 Routing Protocols

There are two types of dynamic routing protocols: Interior Gateway Protocols (IGP) and External Gateway Protocols (EGP). IGPs are used to exchange routing information within an autonomous system (AS), which is a collection of routing domains under the same administrative control the same routing domain. An EGP, on the other hand, is used to exchange routing information between different ASs.

IGPs can be broken into two classes: distance-vector and link-state, and can also be broken into two categories: classfull routing protocols and classless routing protocols.

1.9.1 Distance-Vector Routing

Distance-vector routing is consists of two parts: distance and vector. Distance is the measure of how far it is to reach the destination and vector is the direction the packet must travel to reach that destination. The latter is determined by the next hop of the path. Distance-vector routing protocols will learn routes from its neighbors. This is called routing by rumor. Examples of distance-vector routing protocols are: Routing Information Protocol (RIP), Interior Gateway Routing Protocol (IGRP), and Enhanced Interior Gateway Routing Protocol (EIGRP).

Most distance-vector routing protocols have common characteristics:

Broadcast Updates. When a router becomes active it will send out a message to the broadcast address stating it is alive. In return neighboring routers participating in the same routing protocol will respond to this broadcast.
Periodic Updates, which is the length of time before a router will send out an update. For RIP this time is 30 seconds. For IGRP the time is 90 seconds. This means that once the periodic update timer expires, a broadcast of the routing table will be sent.
Routing by Rumor, which describes the means by which the router learns routes from its neighbors.
Neighbors, which is another router on the same logical, or data link, connection. In a distance-vector routing protocol, a router will send its routing table to its connected neighbors. Those neighbors will send their updated routing tables to their connected neighbors. This continues until all the routers participating in the selected routing protocol have updated routing tables.
Full Routing Table Updates, which is when the distance-vector routing protocol sends its entire routing table to its neighbors. This occurs when the periodic update timer expires.
Invalid Timer, which solves the problem of router failure. Since the failed router will not send out updates, the other routers in the network do not know that a router has gone down and the routes are unreachable. Hence, the routers continue to send packets to the routes connected to the missing router. An invalid timer solves this problem by associating a period of time with a route. If the route is not updated in the routing table in this set period of time, the route is marked unreachable and the router will send this new information in its periodic update.
Split Horizon, which prevents a reverse route. A reverse route occurs when a router learns a route from a neighbor and the router turns around and sends that route back to the neighbor that the router learned it from, causing an infinite loop. The split horizon prevents this by setting a rule that a route cannot be advertised out the same interface the route was learned on.
Counting to Infinity. In networks that are slow to converge, another type of routing loop can occur when routers have multiple paths to the same destination. In this case, the routing table is populated with the best route to the destination even though it has two routes to the same destination. When the destination network goes down, the updates about the destination being unreachable can arrive at the router at different times. The router in turn advertises out that it has another route to the destination. This will continue across the network incrementing the hop count at each router it encounters. Even though the destination network is down, all of the routers participating in the routing process think they have an alternate route to the network causing a loop. This is known as Counting to Infinity and is solved by enforcing maximum hop counts. When a route reaches the maximum hop count limit, the route is marked unreachable and removed from the router's routing table.
Triggered Updates, which one of the means of speeding up convergence on a network. Instead of the routers waiting until the periodic update timer expires and sends out an update, a triggered update will send out an update as soon a significant event occurs.
Hold-down Timer, which is used when information about a route changes. When the new information is received or a route is removed the router will place that route in a hold-down state. This means that the router will not advertise nor will it accept advertisements about this route for the time period specified by the hold-down timer. After the time period expires, the router will start accepting and sending advertisements about the route. This will reduce the amount of wrong information being advertised about routes.

1.9.1.1 Route Poisoning

Route poisoning is a feature that distance vector protocols use to reduce the chance of routing loops. Route poisoning begins when a router notices that a connected route is no longer valid. The router then advertises that route out all its interfaces and with a very large metric so that other routers consider the metric infinite and the route invalid. However, route poisoning does not solve the counting-to-infinity problem.

1.9.1.2 Split Horizon

Count To Infinity

As mentioned earlier, route poisoning does not solve the counting-to-infinity problem. Counting-to-infinity can occur when one router has a valid metric that points to an address that is reachable through an intermediate router while the intermediate router has an infinite-distance route to the same address. If routing table updates are sent by both routers at the same in time, the intermediate router will advertise that the route to the destination address is an infinite-distance route while the other router will advertise that the route has a valid metric. Because the two routers use the same update interval between updates, this process repeats itself with the next routing update, with the difference that the valid metric will be

incremented by 1 each time until an infinite metric is reached, hence this phenomenon is called counting to infinity.

Split horizon solves the counting-to-infinity problem by preventing a router from sending routing updates out the same interface on which it learnt the route. Thus, in the figure shown, the router would have learnt the route to the destination address across the link from the intermediate router. With split horizon, that router cannot then send advertisements about the route to the destination address out across the same link. Therefore the intermediate router will not receive the valid metric from the route to the destination address from the other router ad the count to infinity problem will not occur, solving the count-to-infinity problem on a single link.

1.9.1.3 Split Horizon with Poison Reverse

Split horizon with poison reverse, or simply poison reverse combines the two features. When a route fails the router uses route poisoning, i.e., the router advertises an infinite-metric route about that subnet out all interfaces, including interfaces previously prevented by split horizon. This ensures that all routers know for sure that the route has failed, while split horizon prevents counting to infinity.

1.9.1.4 Hold-Down Timer

Split horizon solves the counting-to-infinity problem over a single link but the counting to infinity problem can also occur in networks with multiple or redundant paths because there are more than one path to a router. In such networks, the hold-down timer feature prevents the counting-to-infinity problem.

With the Hold-down timer feature, a router ignores any information about an alternative route to a destination address for a time equal to the hold-down timer once it has learnt that a route to the destination address has failed.

1.9.1.5 Triggered Updates

Distance vector protocols typically send updates based on a regular update interval. However, most looping problems occur when a route fails. Therefore, some distance vector protocols send triggered updates as soon as a route fails. This causes the information about the route whose status has changed to be forwarded more quickly and also starts the hold-down timers more quickly on the neighboring routers.

1.9.2 Link-State Routing

Link-state routing differs from distance-vector routing in that each router knows the exact topology of the network. This reduces the number of bad routing decisions that can be made because every router in the process has an identical view of the network. Each router in the network will report on its state, the directly connected links, and the state of each link. The router will then propagate this information to all routers in the network. Each router that receives this information will take a snapshot of the information. This ensures all routers in the process have the same view of the network, allowing each router to make its own routing decisions based upon the same information.

In addition, link-state routing protocols generate routing updates only when there is a change in the network topology. When a link, i.e., a point on a route, changes state, a link-state advertisement (LSA) concerning that link is created by the device that detected the change and propagated to all neighboring devices using a multicast address. Each routing device takes a copy of the LSA, updates its topological database and forwards the LSA to all neighboring devices. An LSA is generated for each link on a router. Each LSA will include an identifier for the link, the state of the link, and a metric for the link. With the use of LSAs, link-state protocols reduces routing bandwidth usage.

Examples of link-state routing protocols are: Open Shortest Path First (OSPF) and Integrated Intermediate System to Intermediate System (IS-IS). Another protocol, Enhanced Interior Gateway Routing Protocol (EIGRP) is considered a hybrid protocol because it contains traits of both distance-vector and link-state routing protocols. Most link-state routing protocols require a hierarchical design, especially to support proper address summarization. The hierarchical approach, such as creating multiple logical areas for OSPF, reduces the need to flood an LSA to all devices in the routing domain. The use of areas restricts the flooding to the logical boundary of the area rather than to all devices in the OSPF domain. In other words, a change in one area should only cause routing table recalculation in that area, not in the entire domain.

1.9.3 Classfull Routing

Classfull routing is used in routing packets based upon the class of IP address. IP addresses are divided into five classes: Class A, Class B, Class C, Class D, and Class E. Class A, Class B and Class C are used to private and public network addressing; Class D is used for multicast broadcasting; and Class E is reserved by the Internet Assigned Numbers Authority (IANA) for future use

Classfull routing is a consequence of the fact that routing masks are not advertised in the periodic, routine, routing advertisements generated by distance vector routing protocols. In a classfull environment, the receiving device must know the routing mask associated with any advertised subnets or those subnets cannot be advertised to it. There are two ways this information can be gained:

Share the same routing mask as the advertising device
If the routing mask does not match, this device must summarize the received route a classfull boundary and send the default routing mask in its own advertisements.

Classfull routing protocols, such as Routing Information Protocol version 1 (RIPvl) and Interior Gateway Routing Protocol (IGRP), exchange routes to subnetworks within the same network if network administrator configured all of the subnetworks in the major network have the same routing mask. When routes are exchanged with foreign networks, subnetwork information from this network cannot be included because the routing mask of the other network is not known. As a result, the subnetwork information from this network must be summarized to a classfull boundary using a default routing mask prior to inclusion in the routing update. The creation of a classfull summary route at major network boundaries is handled automatically by classfull routing protocols. However, summarization at other points within the major network address is not allowed by classfull routing protocols.

1.9.4 Classless Routing

One of the most serious limitations in a classfull network environment is that the routing mask is not exchanged during the routing update process. This requires the same routing mask be used on all subnetworks. The classless approach advertises the routing mask for each route and therefore a more precise lookup can be performed in the routing table. Classless routing, which is also known as Classless Interdomain Routing (CIDR), is thus not dependent on IP address classes but, instead, allows a variable-length subnet mask (VLSM), which extends IP addressing beyond the limitations of using fixed-length subnet masks (FLSM),to be sent in the routing update with the route. This allows you to conserve IP addresses, extending the use of IP addresses. Classless routing protocols also addressed the need to summarize to a classfull network with a default routing mask at major network boundaries. In the classless environment, the summarization process is manually controlled and can be invoked at any point within the network.

The routing protocols that support classless routing protocols are: Routing Information Protocol version 2 (RIPv2); Enhanced Interior Gateway Routing Protocol (EIGRP); Open Shortest Path First (OSPF); and Integrated Intermediate System to Intermediate System (IS-IS).

1.9.5 Multipath Routing

A few sophisticated routing protocols support multiple paths to the same destination. A multipath algorithm permits traffic to be multiplexed across multiple equal-cost lines or unequal-cost lines. The IP dynamic routing protocols are able to load balance over multiple equal-cost lines to convey packets. Only the Cisco proprietary routing protocols (GRP and EIGRP) are able to load balance over multiple and unequal-cost lines.