Routing protocols are the glue of the internetwork. They are the foundation of routers and are what has allowed the Internet to grow to its gargantuan size . Your mastery of routing protocols is a critical skill in designing and implementing IP networks. The upcoming sections define what routing protocols are, give the different types and metrics of each, and compare two major classes of routing protocols ”distance vector protocols and link-state protocols.
Part IV includes the following chapters:
Chapter 9, "Distance Vector Protocols: Routing Information Protocol Versions 1 and 2 (RIP-1 and RIP-2)"
Chapter 10, "Distance Vector Protocols: Interior Gateway Routing Protocol (IGRP)"
Chapter 11, "Hybrid: Enhanced Interior Gateway Routing Protocol (EIGRP)"
Chapter 12, "Link-State Protocols: Open Shortest Path First"
What Are Routing Protocols?
A protocol is a routed protocol if it contains an explicit network address and enough information is in its network layer address to allow for a router to make an intelligent forwarding decision. Routing is the process by which a packet gets from one network to another. A routing protocol supports a routed protocol by providing a means for propagating routing information. This information includes elements such as the available routes, a cost to the routes, and the next -hop address. The routing protocol uses messages between routers that allow for communication with other routers to update and maintain routing tables. It is important to note that routing protocols do not carry end-user traffic from network to network. Routing protocols only build the paths that end- user data uses to travel.
The Route Table
Many routing protocols are in use today. As different as they are from each other, they all serve the same purpose of performing routing operations and maintaining a route table.
The route table contains the following information:
-
Lists of networks/routes or host routes.
-
The means by which the route was learned, either dynamically from a routing protocol or statically from manual configuration.
-
Administrative distances of the routes.
-
The metric or cost of the route.
-
The address of the next-hop router to the route.
-
The current status of the route. This can include the amount of time since the last update, whether the route is in holddown, and so forth.
-
The interface associated with reaching the route. This is the interface from which the packet will be forwarded to the next-hop router.
Example IV-1 depicts a complex routing table, illustrating OSPF, EIGRP, and default routing.
Example IV-1 Routing Table
r2# show ip route Codes: C - connected, S - static, I - IGRP, R - RIP, M - mobile, B - BGP D - EIGRP, EX - EIGRP external, O - OSPF, IA - OSPF inter area N1 - OSPF NSSA external type 1, N2 - OSPF NSSA external type 2 E1 - OSPF external type 1, E2 - OSPF external type 2, E - EGP i - IS-IS, L1 - IS-IS level-1, L2 - IS-IS level-2, * - candidate default U - per-user static route, o - ODR Gateway of last resort is 172.16.128.1 to network 0.0.0.0 10.0.0.0/24 is subnetted, 1 subnets O 10.10.10.0 is a summary, 03:05:49, Null0 129.201.0.0/24 is subnetted, 1 subnets O E1 129.201.1.0 [110/90] via 172.16.2.66, 03:05:45, TokenRing1 128.200.0.0/24 is subnetted, 1 subnets D EX 128.200.1.0 [170/679936] via 172.16.192.3, 05:42:57, Serial1 129.200.0.0/24 is subnetted, 1 subnets O E1 129.200.1.0 [110/90] via 172.16.2.66, 03:05:45, TokenRing1 128.201.0.0/24 is subnetted, 1 subnets D EX 128.201.1.0 [170/679936] via 172.16.192.3, 05:42:57, Serial1 C 201.201.101.0/24 is directly connected, Loopback0 O E2 132.31.0.0/16 [110/2] via 172.16.2.66, 00:58:04, TokenRing1 O E2 131.31.0.0/16 [110/2] via 172.16.2.66, 00:58:04, TokenRing1 172.16.0.0/16 is variably subnetted, 27 subnets, 4 masks O IA 172.16.152.0/24 [110/71] via 172.16.2.66, 03:05:45, TokenRing1 O IA 172.16.150.0/24 [110/80] via 172.16.2.66, 03:05:45, TokenRing1 O IA 172.16.151.0/24 [110/71] via 172.16.2.66, 03:05:45, TokenRing1 C 172.16.144.0/21 is directly connected, Loopback20 C 172.16.136.0/21 is directly connected, Ethernet1 C 172.16.128.0/21 is directly connected, Ethernet0 C 172.16.192.0/24 is directly connected, Serial1 C 172.16.192.3/32 is directly connected, Serial1 O IA 172.16.42.2/32 [110/70] via 172.16.2.66, 03:05:46, TokenRing1 O IA 172.16.42.3/32 [110/70] via 172.16.2.66, 03:05:46, TokenRing1 O E2 172.16.42.0/24 [110/2] via 172.16.2.66, 03:05:46, TokenRing1 O IA 172.16.42.1/32 [110/6] via 172.16.2.66, 03:05:46, TokenRing1 O IA 172.16.21.0/24 [110/76] via 172.16.2.66, 03:05:46, TokenRing1 O IA 172.16.22.0/24 [110/71] via 172.16.2.66, 03:05:46, TokenRing1 O E2 172.16.1.0/24 [110/2] via 172.16.2.66, 03:05:46, TokenRing1 O E2 172.16.2.0/24 [110/2] via 172.16.2.66, 03:05:46, TokenRing1 D 172.16.102.0/24 [90/679936] via 172.16.192.3, 05:42:59, Serial1 D 172.16.103.0/24 [90/409600] via 172.16.128.1, 05:42:59, Ethernet0 O E2 172.16.84.0/24 [110/2] via 172.16.2.66, 03:05:47, TokenRing1 O E2 172.16.85.0/24 [110/2] via 172.16.2.66, 03:05:47, TokenRing1 O E2 172.16.81.0/24 [110/2] via 172.16.2.66, 03:05:47, TokenRing1 O E2 172.16.82.0/24 [110/2] via 172.16.2.66, 03:05:47, TokenRing1 O E2 172.16.83.0/24 [110/2] via 172.16.2.66, 03:05:47, TokenRing1 O E2 172.16.64.0/24 [110/2] via 172.16.2.66, 03:05:47, TokenRing1 C 172.16.1.64/26 is directly connected, TokenRing0 C 172.16.2.64/26 is directly connected, TokenRing1 D*EX 0.0.0.0/0 [170/20028160] via 172.16.128.1, 05:43:00, Ethernet0
You can see many of the routing table components mentioned previously by examining the highlighted line. The route 172.16.102.0/24 is being reported by EIGRP. The administrative distance of the route is 90, and the EIGRP metric is 67,9936. The route was reported more than 5 hours and 42 minutes ago. The next-hop router is over interface Serial1, and its IP address is 172.16.192.3.
The Routing Protocol Algorithm
All dynamic routing protocols are built around a general algorithm. The routing algorithm addresses the following areas:
-
A procedure for distributing reachability information about networks to and from other routers
-
A procedure for determining and recording optimal routes, based on the reachability information received from other routers
-
A procedure to advertise and compensate for topology changes
When Does the Router Route?
By default, all Cisco routers will route all routable protocols, such as IP or IPX, first. If routing for the routable protocol is not enabled and bridging for that protocol is enabled, the router will bridge it. How a router handles a protocol depends not only on the protocol being a routable protocol, but also on how routing is enabled for that protocol. For example, if the router receives an IPX packet and has IPX routing enabled, it tries to route or forward the packet to the next-hop address. This is the normal operation of IPX. However, if the router receives an IPX packet and does not have IPX routing enabled, the router forwards that packet out any bridged interfaces, including DLSw ports. This is because the router no longer recognizes IPX as a routable protocol.
To successfully route a packet, a router must know the following:
-
The protocol must be routable, and routing for that protocol suite must be enabled.
-
The router must know the destination network or have a default route installed.
-
A valid next-hop address must exist, or an interface pointing at the destination network must exist.
When the decision to route the packet is made, the router checks the packet to see if the final destination is a locally connected network. If the destination is local, the router forwards it out the appropriate port. If the network is not local, the router must consult the route table. The route table consists of known networks, the costs associated with those networks, and the path to the next-hop router. The router compares the packet to entries in its route tables by performing a longest match lookup. The entry that has the longest match to the destination address is the entry used to determine the forwarding path. The longest match route can also be referred to as the most explicit route. The longest match is only 100 percent true if ip classless is enabled, and it applies mostly to classless routing protocols.
NOTE
The longest match lookup occurs when a router must determine which entry in the route table to use in forwarding a packet. For example, imagine that the router receives a packet that has a destination network of 172.16.1.0/24. It has two routes, 172.0.0.0/8 out S1 and 172.16.0.0/16 out S2. Which interface should the router forward the packet out? This is when the router performs a longest match lookup. To accomplish this, the router compares the bits of the destination network, from left to right, with the bits in route in the routing table. The router compares each bit in sequence and stops the comparison process at the bit before the first bit that doesn't match in the route table entry being compared. The router chooses the path/route where the greatest number of consecutive bit matches has occurred. In this case, the router uses the 172.16.1.0 route over the 172.16.0.0 route because the 172.16.1.0 route is the longest match ”or, in other words, more explicit.
Routing Metrics
Another important aspect of routing protocols is to provide a loop-free topology of the network while locating the best path to every destination network. Routers advertise the path to a network in terms of a metric. The metric value or metric type depends on the routing protocol. For example, RIP uses hop count as its metric, whereas OSPF uses cost. The router uses the metric value when evaluating multiple paths to the same network. The metrics for all routing protocols can be adjusted, thereby influencing which path the router will select in forwarding traffic. The following list is a brief description of the most common routing metrics:
-
Hop count ” A metric that counts router hops. The more hops, the less desirable the path.
-
Bandwidth ” A metric that measures bandwidth. The higher the bandwidth, the more preferable the path.
-
Load ” A metric that reflects the amount of traffic on a links to a path. The lower the load, the more preferable the path.
-
Delay ” A metric that measures the time that a packet takes to traverse a route. The lower the delay, the more preferable the route.
-
Reliability ” A metric that measures the probability that a link will fail. The higher the reliability, the more preferred the path.
-
Cost ” A configured metric. The lower the cost, the more preferred the route.
Because each routing protocol has a unique application of metrics, we will discuss routing protocol specific metrics in the upcoming chapters.
Administrative Distance
At any given time, more than one routing protocol can be active on a router. The router needs a way to classify the routes received from one routing protocol against the routes received from another. Cisco uses the concept of administrative distance to measure the trustworthiness of the source of IP routing information. The lower the value of the administrative distance is, the more preferred the route is. The distance can be changed for each routing protocol with the distance command. Table IV-1 lists the default administrative distances of route sources.
Table IV-1. Default Administrative Distances on Cisco Routers
| Route Source/Type | Default Administrative Distance |
| Connected interface | |
| Static route pointing to an interface | |
| Static route to a next-hop interface | 1 |
| EIGRP summary route | 5 |
| External BGP | 20 |
| EIGRP | 90 |
| IGRP | 100 |
| OSPF | 110 |
| IS-IS | 115 |
| RIP-1 and RIP-2 | 120 |
| EGP | 140 |
| External EIGRP | 170 |
| Internal BGP | 200 |
| Unknown route Unreachable | 255 |
Distance Vector and Link-State Protocols
Most routing protocols can be divided into two major classes:
Cisco's EIGRP is the exception and is often referred to as a hybrid protocol because it combines aspects of link-state and distance vector protocols. EIGRP is closer to a distance vector protocol than a link-state protocol because it uses metrics for distance and does not use the link states for routing advertisements.
Distance Vector Protocols
Distance vector-based algorithms, also known as Bellman-Ford algorithms, pass periodic copies of a route table from router to router. Regular updates between routers happen during topology changes. Distance vector protocols advertise routes in terms of vectors. Each vector has a distance and direction associated with it. For example, in RIP, the subnet 172.10.0.0 is the vector, its distance is five hops away, and the direction is the next-hop router.
Here is a simplistic way of how distance vector protocols operate :
-
At a specific timed interval, the router broadcasts its entire route table out each interface. It does not include routes suppressed by filters, split horizons, or routes that exist on a different major bit boundary than the interface sending the broadcast. The broadcast contains the network or route and a metric associated with that route.
-
Each adjacent router receives the update and compares the routes in the update to the routes in the route table. The routes with the best metric, the ones with the lower metric, are stored in the forwarding table.
-
Each adjacent router now propagates its new routing table route to all its neighbors.
-
The routers continue to broadcast their route tables to their neighbors at a periodic interval. RIP, for example, uses a periodic interval of 30 seconds.
All distance vector protocols have the following common characteristics:
-
Periodic full routing updates ” At the end of a certain time limit, usually 10 to 90 seconds, a full routing table is broadcast to every neighbor.
-
Neighbors ” Neighbors can be defined as routers sharing a common data link. Distance vector routers send updates to all neighbors and depend on them to pass along that information to their neighbors.
-
Broadcast updates ” The router uses a broadcast address to locate its neighbors and to advertise its route table.
-
Route invalidation timers ” These timers provide a means for the router to start to degrade the cost of the route and eventually remove it from the route table. The timers are reset when a new update is received.
-
Split horizon ” A route pointing back to the router where it was received is called a reverse route. Split horizon prevents reverse routes between routers. The rule of simple split horizons states that when sending an update out an interface or subinterface, do not include networks learned from that interface. Split horizon is enabled or enforced by default on all serial interfaces and subinterfaces. We discuss split horizons more throughout the book, especially how this relates to Frame Relay point-to-point and multipoint interfaces.
-
Maximum hop count or count to infinity ” Distance vector networks have a ceiling on how many hops a route can be away before the route is declared unreachable. RIP has a maximum hop count of 16.
-
Poison reverse ” The rule for poison reverse is to advertise a route out the interface on which it was received with an unreachable metric. Different routing protocols employ this rule at different times to control routing loops .
The following is a list of distance vector routing protocols:
-
IP Routing Information Protocol (RIP)
-
Xerox Networking System's XNS RIP
-
IPX RIP
-
Cisco's Internet Gateway Routing Protocol (IGRP)
-
DEC's DNA Phase IV
-
AppleTalk's Routing Table Maintenance Protocol (RTMP)
-
Gateway-to-Gateway Protocol (GGP)
-
Exterior Gateway Protocol (EGP)
Link-State Protocols
The other class of routing protocols is called link-state protocols. As distance vector protocols are based on algorithms by R.E. Bellman, L.R. Ford, and D.R. Fulkerson, link-state protocols are based on an algorithm by E.W. Dijkstra.
Link-state protocols operate in a significantly different manner than that of distance vector protocols. Some of the major differences include the following:
-
Support for variable-length subnet masking (VLSM) ” All link-state protocols support VLSM. One reason for this is because the routing update includes a subnet mask.
-
Neighbors ” All link-state environments establish neighbors through the use of a Hello protocol.
-
Nonstub routers ” Nonstub routers retain a complete map of all paths in the network.
-
Event-triggered routing announcements ” Routing updates are propagated by a means of flooding link states from one area to the next. The SPF/Dijkstra algorithm directs the flooding of LSAs.
-
Link-state database ” The link-state database stores link-state advertisements (LSAs) as a series of records. The information in the database includes a record of router IDs, connected networks, and adjacent routers, and the cost associated with them.
-
Hierarchical topology required ” External areas require connections to backbone areas. Link-state networks must be designed around these requirements. OSPF virtual links will allow this rule to be broken, but they should be avoided.
Here is a simplistic way of how link-state protocols operate:
-
The router establishes an adjacency with each of its neighbors.
-
Each router sends link-state advertisements (LSAs) or link-state packets (LSPs) to its neighbors. One LSA is generated for each route in the table. The LSA identifies the route, the state of the route, the cost or metric of the interface associated with the route, and any neighbors connected to the route. Each neighbor that receives an advertisement forwards it to its neighbors.
-
Each router stores a copy of all the LSAs that it has received in a database.
-
The database is called a link-state database. It contains a map or tree of the entire network. The router uses the Dijkstra algorithm and calculates a shortest path to each network; it enters this information into the routing table.
The most common link-state protocols are as follows :
-
Open Shortest Path First (OSPF) for IP
-
Intermediate System-to-Intermediate System, for ISO IS-IS
-
DEC's DNA Phase V
-
Novell's NetWare Link Services Protocol (NLSP)
Distance Vector Versus Link-State Routing Protocols
Table IV-2 highlights the major differences between distance vector and link-state routing protocols.
Table IV-2. IP Routing Protocol Comparison
| | RIP-1 | RIP-2 | IGRP | EIGRP | OSPF | IS-IS |
| Split horizon “ sensitive | X | X | X | | | |
| Periodic updates | X | X | X | | | |
| Triggered updates | X | X | X | X | X | X |
| VLSM support | | X | | X | X | X |
| Equal-path load balancing | X | X | X | X | X | X |
| Unequal-path load balancing | | | X | X | | |
| Automatic classful route summarization | X [1] | X | X | X | | |
| Manual classless route summarization | | | | X | X | X |
| Routing metric | Hop count | Hop count | Delay, MTU load, BW, reliability | Delay, MTU load, BW, reliability | Cost | Default, delay, expense, error |
| Authentication type | None | Type 1 | None | Type 2 | Type 1 | Type 1 |
| Type 1 ”clear text | | Type 2 | | | Type 2 | |
| Type 2 ”MD5 | | | | | | |
| Hop-count limit | 15 | 15 | 255 | 255 | Unlimited | 1024 |
| Hierarchical design required | | | | | X | X |
| Scalability | Small | Small | Medium | Large | Large | Very large |
| Routing algorithm | Bellman- Ford | Bellman- Ford | Bellman- Ford | DUAL | Dijkstra | IS-IS |
| Cisco administrative distance | 120 | 120 | 100 | 90/5 [2] | 110 | 115 |
[1] Route summarization cannot be disabled.
[2] 5 is the distance for an EIGRP summary route.
The upcoming chapters are intended to be a technical overview of the configuration of RIP, IGRP, EIGRP, and OSPF. For a thorough and, in my opinion, one of the best explanations of routing protocols, study Jeff Doyle's book, Routing TCP/IP, Volumes I and II.
