Please add second and in some cases third level heads, exercises, figures (with captions), tables, a Q & A section, and the Self Test Questions and Answers with explanations

GLOBAL KNOWLEDGE NETWORKä CERTIFICATION PRESS
Cisco Certified Network Associate Exam
Router and Switching Study Guide

Chapter 5

IP Routing Protocols

BOOK TABLE OF CONTENTS

SELF TEST

RETURN TO HOME PAGE

Certification Objectives *

Theory *

Algorithms for Route Determination *

From the Classroom *

Keeping route loops from running you in circles *

Distance Vector Routing Protocols *

Link-State Routing Protocols *

Interior vs. Exterior Gateway Protocols *

EIGRP *

Certification Objectives

Why Routing Protocols?

Static Routes and Dynamic Routes

Default Routes

Link State vs. Distance Vector

RIP

IGRP

OSPF

Imagine that continental United States has a single road that simply winds around to get to every place people need to go. Every car, every truck, every bicycle, every parade, and every pedestrian must use this single road. The traffic from millions of cars would be horrific-jams all over the place. Accidents would back traffic up from New York to Los Angeles. Obviously, that much traffic needs to be turned onto different roads to split it up into manageable portions. The roads still need to intersect, so that people can still reach whichever destination they need to reach. Multiple intersections can also provide redundant routes, so that huge traffic delays can be avoided. By sending traffic on different routes, a traffic jam makes less of an impact. Everything becomes more efficient and reliable.

In this same way, internetwork traffic needs to be split up to avoid network traffic jams. The process of directing internetwork traffic onto different networks is called routing.

Why Routing Protocols?

Internetworks use routing to get data from one network to another. In order to keep data on the best path to its destination, some sort of map of the routes available on the network is needed. The mapping of the networks that the data travels to is handled by a routing protocol.

Local Area Networks (LANs) have an inherent performance limit, which is dependent upon size or complexity. Routers, and their routing protocols, can resolve some common bottlenecks and other conditions that degrade network efficiency. These limits include:

Network physical segment size
Number of hosts per segment
Redundancy
Amount of traffic
Dissimilar network topologies

Depending on the type of network, whether Ethernet, Token Ring, or other protocol, the network segment size is limited. A new segment must be created to support nodes located beyond the distance limit set by the segment size-usually measured in cabling distance, or wireless limit. For instance, Ethernet segments using twisted-pair copper wiring are limited to a maximum physical distance from the node to the hub. When a new node is added beyond this limitation, and another segment is created, there must be some way of getting traffic from one segment to the other. {Answer to Self Test Question # 21}This can be done by bridging or by routing, and more recently by switching. Bridging is the capability to connect two or more physical network segments such that the connection is transparent to the network. In bridging, broadcasts are sent to all nodes on the bridged segments, and all nodes are considered to be in the same logical network (subnet). Bridging occurs at the data link layer. Switching is a way to increase bandwidth (as well as limit the amount of traffic a node encounters) by providing a dedicated channel for each switched port. Switching occurs at the data link layer. In contrast to either of these network traffic-guiding methods, routing connects multiple logical networks such as Ethernet and Token Ring, into a single internetwork, with each separate logical network maintaining its logical network address. {Answer to Self Test Question # 22}Routing occurs at the network layer, and includes the capability to separate the management of the segments on the internetwork.

The number of hosts allowed on each segment is limited on a network topology. This limit varies, depending on the type of network topology used. For example, an Ethernet segment using twisted-pair wiring is limited to the number of hosts, or nodes. Once the maximum number of hosts has been reached, another segment must be created, and the traffic to that segment must be bridged or routed.

Bridging can offer a single path for traffic between segments. However, when multiple transmission paths are needed, routing may be implemented to support those multiple paths. When redundancy is required for internetwork traffic, a routing protocol may be implemented with that option. Figure 5-1 illustrates redundancy with routing.

Figure 1 Redundancy with routing

Congestion is the point where the amount of traffic exceeds the network capacity. Congestion in a network can be debilitating to its use. Bridging, switching and routing can control the amount of traffic.

Some routing protocols can handle flow control, so that if a router is congested, another router sending internetwork traffic to it can be notified by the routing protocol to slow down the rate that data is being sent to the router. Routing protocols do this to ensure that minimal delay is encountered when routers become overloaded. Figure 5-2 illustrates the process of traffic control with routing.

Figure 2 Traffic controlled with routing

{Answer to Self Test Question # 1}Dissimilar network topologies, such as FDDI, X.25, and ATM, cannot always be bridged or switched, because the nature of the physical media or physical layer protocol prevents it. In order to transmit internetwork traffic, dissimilar networks must be routed, as shown in Figure 5-3.

Figure 3 Dissimilar networks routed
Theory

{Answer to Self Test Question # 2}There are two basic mechanisms that make up routing:

Determination of routes
Transmission of data packets across the internetwork

These items will be discussed for each routing protocol. There are several different routing protocols, such as RIP or OSPF, and each determines the best routes in a different way. The data transmission itself is similar, if not identical across different routing protocols.

Algorithms for Route Determination

One of the terms to be aware of for route determination is metric. A metric is the value of a variable, such as the network delay, after the routing protocol algorithm has computed it. {Answer to Self Test Question # 23} The purpose of the metric is to determine the best route for selection.

{Answer to Self Test Question # 3}Routing protocols both create and maintain a routing information table, or routing table. This routing table is used in selecting the best route. {Answer to Self Test Question # 4}{Answer to Self Test Question # 24}Depending on the type of routing protocol used, the routing table may contain different types of routing information about the path to a destination network. For example, in some routing protocols, the routing table may contain the destination network and the next hop associated with it. This information states that to get to the destination network, send the data through the interface connected to the "next hop." A hop is the next router that the data should hop to, or the router's interface that is connected to the network that the data should hop to. When determining the best route, the one with the least number of hops is selected.

There are algorithms providing an association of the destination with a metric, which is some value determining the distance or cost of the destination. This method allows the determination of the best route by the route with the optimal value. For example, when using a cost metric, the path with the least cost (the cheapest route) is considered optimal.

Another method of determining the routing table is to associate the destination with the path that needs to be taken to reach that destination. This is a simplistic, hops-based routing, without any metric determination based on any other factors, since some hops-based routing protocols can use other factors in determining the metric for a best route. It is a store-and-forward type of method, whereby the packet is stored in the router momentarily and then forwarded to the next path it needs to take at each router it encounters until it reaches the destination network. In Figure 5-4, an illustration of a simple two-router, three-segment network, the routing table would look something like this for Router A:

192.168.3.0 255.255.255.0 192.168.2.2

Figure 4 A simple three-segment network

Router A does not need an associated route to the 192.168.1.0 or 192.168.2.0 networks, since they are directly connected to it, and the routing protocol will automatically create those routes for the directly-connected networks. The routing table typically includes the network, the subnet mask, and the next path, which in this case is the interface leading to that network.

{Answer to Self Test Question # 5}Routing protocols also include a methodology for maintaining their routing tables. They exchange information such as a routing update. The routing update can consist of the router's entire routing table, or only the portion that has changed. These communications are essential for keeping the routing tables accurate, as well as allowing optimal routes to be chosen. Depending on the routing protocol used, a routing update can be sent on a periodic interval, or it can be triggered by a topology change. Figure 5-5 illustrates one example of an event triggering a routing update.

Figure 5 Routing updates

The algorithm for routing a data packet from one interface to another within the router is similar for most routing protocols. A node sends a packet to another node on a different network. It sends that packet using the network/node address of the destination node, which seems fairly straightforward. {Answer to Self Test Question # 6}However, the node adds the MAC (Media Access Control) layer address of the router to the packet. The MAC layer address (also known as the hardware address) is part of the data link layer

{Answer to Self Test Question # 25} By virtue of that hardware address, the router receives the packet, and looks at the network/node address of the destination node. The router determines that it can or cannot forward the packet to the destination network. If it can, the router strips off its own MAC layer hardware address, and then puts the hardware address of the next hop onto the packet. If it cannot route the packet, the packet is either dropped or forwarded onto the default route.

If the next hop is not the ultimate destination node, it is almost always another router. That router can then perform the same operation on the packet by determining the next hop, stripping off the MAC layer address, adding the next hop's address, and forwarding the packet, and so on until the packet reaches the destination network/node. The one constant item is the network/node address. It does not change, whereas the hardware address changes at each hop.

{Answer to Self Test Question # 7}There are three major objectives of a routing algorithm:

Accuracy
Low overhead
Quick convergence

Accuracy is the capacity of the routing algorithm to determine the optimal route based on the metrics used. This means that the metrics of the routing algorithms are what determines the accuracy of the route selection.

{Answer to Self Test Question # 26} Low overhead can be applied to both bandwidth and CPU usage. When referring to CPU usage, a routing protocol would need to be elementary in its computations. A router with limited or overused resources requires the simplest routing protocol. When referring to bandwidth usage, a routing protocol would require small communication messages, at the smallest of periodic intervals. This is essential for an efficient utilization of slow network links. A router should prove stable, as well as efficient, in order to maintain the low overhead criteria.

{Answer to Self Test Question # 8}Convergence is the process of all routers synchronizing their routing information tables, or the time it takes for a single routing change to be reflected in all routers. The speedier the convergence process, the more accurate the routing tables, which leads to an efficient network. {Answer to Self Test Question # 27} If there were never changes to an internetwork's topology, then convergence would not be an issue. However, multiple changes can be made on a network: additions of network segments, additions of routers, downed interfaces on a router, entire routers that are downed, bandwidth usage changes, network bandwidth changes for network links, increases or decreases in a router's CPU usage. All of these conditions can change how a routing protocol should select the optimal routes. A fast convergence also avoids a routing loop, which is discussed later in this chapter.

Some of the types of routing algorithms are:

Static vs. dynamic
Interior vs. exterior
Distance vector vs. link state

Each of these types of algorithms determines an aspect of the routing protocol used. Each type has advantages that may make it more logical for a certain type of internetwork, depending on its size or complexity.

Static Routes and Dynamic Routes

{Answer to Self Test Question # 28} A router makes decisions about which network segment to send a packet on by consulting its routing information table. This table allows it to select just the next route step the packet needs to take, rather than selecting an entire path to the final destination. When the packet reaches another router, that next router will select the next segment to send the packet to.

{Answer to Self Test Question # 9}Dynamic routing protocols include a method for dynamically configuring the routing information table. These are considered dynamic routes. Dynamic routes depend on which links are functioning. The path selection also is based on the criteria within the dynamic routing protocol. The main advantage to dynamic routing is that a route to a remote network can be automatically reconfigured if multiple routes exist and one has gone down due to a nonfunctioning router. This is an advantage to large internetworks. Dynamic routes are both scalable and adaptable.

{Answer to Self Test Question # 10}A static route is a route that has been manually entered into the routing table. Figure 5-6 shows an example of a static route. There are many advantages to static routing.

No need for a dynamic routing protocol, which reduces overhead on the routers
Easily configured for small internetworks
Control over the route selection

Figure 6 Static route

In Figure 5-6, each router would have static route configuration.

Router A's configuration is as follows:

hostname routera

interface ethernet 0

ip address 192.168.4.1 255.255.255.0

interface ethernet 1

ip address 192.168.5.1 255.255.255.0

ip route 192.168.1.0 255.255.255.0 192.168.4.2

ip route 192.168.2.0 255.255.255.0 192.168.5.2

ip route 192.168.3.0 255.255.255.0 192.168.5.2

Router B's configuration is as follows:

hostname routerb

interface ethernet 0

ip address 192.168.1.1 255.255.255.0

interface ethernet 1

ip address 192.168.4.2 255.255.255.0

ip route 192.168.2.0 255.255.255.0 192.168.4.1

ip route 192.168.3.0 255.255.255.0 192.168.4.1

ip route 192.168.5.0 255.255.255.0 192.168.4.1

Router C's configuration is as follows:

hostname routerc

interface ethernet 0

ip address 192.168.3.2 255.255.255.0

interface ethernet 1

ip address 192.168.5.2 255.255.255.0

ip route 192.168.1.0 255.255.255.0 192.168.5.1

ip route 192.168.2.0 255.255.255.0 192.168.3.1

ip route 192.168.4.0 255.255.255.0 192.168.5.1

Router D's configuration is as follows:

Hostname routerd

interface ethernet 0

ip address 192.168.2.1 255.255.255.0

interface ethernet 1

ip address 192.168.3.1 255.255.255.0

ip route 192.168.1.0 255.255.255.0 192.168.3.2

ip route 192.168.4.0 255.255.255.0 192.168.3.2

ip route 192.168.5.0 255.255.255.0 192.168.3.2

{Answer to Self Test Question # 29} {Answer to Self Test Question # 30}Note that when configuring a static route the IP ROUTE command is followed by the network that the route will be going to, the subnet mask, and finally the IP address of the next router's interface that data packets should use when addressed to that network.

Static routes are also important when the routing protocol used cannot determine the best route to the destination network. In order to remove a static route, the NO IP ROUTE global command is used.

So, a static routing "algorithm" is simply a definition of the routing table established by the network administrator in order to allow routing on the internetwork. {Answer to Self Test Question # 31} The routing table never changes without a manual update by the administrator.

{Answer to Self Test Question # 11}Static routing does not work well in an environment that encompasses frequent network changes. In a large and constantly changing internetwork, a static routing setup is simply not viable. However, in a small, self-contained internetwork environment with rare changes, static routing would work well.

The routing protocol algorithms described in this chapter (RIP, IGRP, EIGRP and OSPF) are all dynamic. They adjust to the changes that occur within the internetworking environment. The periodic updates that are sent throughout the internetwork are analyzed by the receiving routers to determine if there have been any internetwork topology changes. In the event that the internetwork topology has changed, the routers re-run their path selection algorithms and then update their routing tables with the selected routes.

A hybrid solution of dynamic and static routing can be used to increase the stability of an internetwork. In this solution, a static route is designated for the default route or a router of last resort. (The term gateway of last resort is also used.) {Answer to Self Test Question # 32} Packets are forwarded to the default route if no routing entries match the destination address. This may not seem like the best solution, since a nonroutable packet would seem to be useless. However, in an internetwork that is connected to a larger internetwork, but which is self-contained and does not exchange routing information with that other internetwork, it works well. For example, note that in Figure 5-7, the internetwork knows all about the 192.168.1.0, 192.168.3.0, 192.168.4.0, and 192.168.5.0 networks. It is also aware of the network 202.12.37.0, which leads to the Internet. However, the network does not share routing information with the Internet without severely debilitating its routers due to the excessive overhead of all those routes. Nor is it going to be able to share information with other corporate networks, such as corporate customers to whom e-mail and files might be sent, who are also connected to the Internet, and who also do not share routing information with the Internet. In Figure 5-7, the hybrid solution works well for all packets that are nonroutable-that is, are not sent to the 192.168.1.0, 192.168.3.0, 192.168.4.0, 192.168.5.0, and 202.12.37.0 networks. In this case, the router of last resort should be the Internet router connected to Router D, specifically its interface 202.12.37.67.

Figure 7 Default route

Some routing algorithms allow for a central control of the routing table. A central router would collect the routing information from all routers and then distribute their routing tables to them. The advantage to central control is that it frees up working routers from the route calculation overhead, and it keeps routing tables consistent. The disadvantage is that it has a single point of failure in the central control router.

{Answer to Self Test Question # 33} Most routing protocols are distributed, and thus router fault tolerant. Each router maintains its own routing table. To synchronize the routing tables, or converge, some routing protocols allow for routers to periodically update each other about the status of their network links.

Some routing protocols allow for a network fault tolerance, since they support multiple "live" routes or redundant routes to the same destination network. In this case, a network segment can become unreachable by one router, but another route can be obtained to the network. Furthermore, some routing protocols allow for load balancing of network traffic across the multiple redundant routes to the single destination. Some protocols maintain a second-best, or feasible successor, entry for each route, so there is no interruption in traffic flow when the primary route fails.

{Answer to Self Test Question # 12}An autonomous system (AS) is a group of networks, or small internetwork, within a larger internetwork. This is also known as an area or domain. The autonomous system setup is known as hierarchical. Newer routing protocols tend to be hierarchical, whereas older routing protocols support flat networks.

Hierarchical routing allows the limitation of routing information propagation throughout an entire internetwork. Instead, routing information is shared only by routers within the autonomous system. Only limited information needs to be shared by routers that are on the border of an autonomous system. Routes are freely exchanged among routers within an AS. By default, routes do not flow from one AS to another, and must be specifically configured to do so. This allows full control over how much detail is shared between autonomous systems.

From the Classroom

Keeping route loops from running you in circles

Convergence time is important, because the routers in your network are making independent decisions about how to forward individual packets. If some routers have different information than their neighbors, as often happens in a network based on distance vector routing protocols, when a change in network topology occurs, packets can be forwarded from one router to another and back again until their Time to Live expires. A routing protocol with a faster convergence time will minimize the duration of these route-loop episodes, which usually correct themselves in a properly configured network.

If you have only a single routing protocol in use in your network, and your network topology is mainly hierarchical or star-shaped, rather than meshed, you should have no persistent problems with route loops. But if you use a combination of dynamic routing protocols, such as RIP and OSPF, or a combination of dynamic protocols and static routes, you will need to pay careful attention to your configurations. This will be especially true if your network includes many redundant paths, or if its topology is partially meshed.

The key to success here is to think about all your routers together as a system rather than as separately configured individuals. This can prevent loops that will never correct themselves. This is especially critical if you are making any changes to your static routes or to your dynamic protocol configurations. Be sure you understand what the impact on the entire system will be prior to making any changes.

-By Pamela Forsyth, CCIE, CCSI, CNX

Default Routes

{Answer to Self Test Question # 13}A default route is the one specified for data to follow if there is no explicit routing information for it to use in finding a direction. If a router has a connection to a small network segment, and a second connection to a large internetwork with multiple different IP subnets, then the interface connecting to the multiple different subnets would be the best interface to designate as the default route. So any packets received by the router that are not destined for the immediate network segments would be sent out the interface with the default route.

In Figure 5-8, both router B and router C can use a default route. In router B, the interface with the address 192.168.2.2 would be the default interface. In router C, the interface with the address 192.168.3.1 would be the default interface.

A default route is best used whenever a router cannot determine the routes to all other networks. One practice for designating default routers is to specify certain routers as smart routers. Smart routers contain the routing information for the entire internetwork. Then, designate a smart router as the default router for the other routers on the internetwork. A dynamic routing protocol can sometimes redistribute the default route, which is good when using the smart router internetwork configuration. Or the default router can be set manually on each individual router.

{Answer to Self Test Question # 34} To specify a static default route, use the following command in global configuration mode on the router:

ip default-network {network-number}

That command looks like this for Router B in Figure 5-8:

ip default-network 192.168.4.0

This specifies that for all packets not destined for networks 192.168.1.0 and 192.168.4.0 should be sent through the network 192.168.4.0 in order to be forwarded across the internetwork to a final destination.

Figure 8 Default network example

Here is a typical routing problem, such as you might encounter on the CCNA exam, or in the course of your work.

Gerald manages an internetwork consisting of three routers and four logical networks. He is using a static routing table. Gerald adds a connection to the Internet. If router A is connected to B, then to C, then to D, and then to the Internet, Gerald assumes that he can place a single default route on router D to send everything to the Internet. When the connection goes live, the people connected directly to networks on router D are able to use the Internet, but no one else can. What is the problem?

Because there are no default routes on Routers A, B, and C, the routers will drop the packets for which there are no existing routes. Then, the Internet cannot be reached. To correct the problem, a default route on C should send all packets to D, a default route on B should send all packets to C, and a default route on A should send all packets to B.

Link State vs. Distance Vector

Dynamic routing protocols can be classified by the way they communicate with each other to determine the routing information table. The two types of dynamic routing are link state and distance vector.

Distance Vector Routing Protocols

Distance vector routing protocols are also called Bellman-Ford protocols. A distance vector protocol router periodically sends its neighboring routers two pieces of information:

The distance in hops, the metric used, or numbers of networks it will take to get to the destination network
What the next hop is, or which direction (vector) to take to get to the destination network

Distance vector routers periodically send their neighboring routers their entire routing table. The distance vector router builds its routing information table based on this information received from neighboring routers. Then the information is passed on to its neighbors. {Answer to Self Test Question # 14}The result is that routing tables are built from second-hand information, as shown in Figure 5-9.

Figure 9 Distance vector router sending second-hand information

When a route becomes unavailable on the internetwork, the distance vector routers will learn of the change through either a route change or aging of the network link. A neighboring router to the downed link might send a "route change transmission" (or a "route unavailable") message throughout the internetwork. {Answer to Self Test Question # 35} Aging is set for all routing information. When a route has become unavailable and the information is not sent to the network with the new information sent, the distance vector routing algorithm sets an aging timer on that route. When the route reaches the end of that aging timer, it is removed from the routing table. The aging timer differs according to which routing protocol is used.

Regardless of the type of routing algorithm used, the time it takes for all the routers on an internetwork to update all the changes in their routing tables is called convergence. Convergence in distance vector routing, therefore, consists of:

Each router receiving the updated routing information
Each router updating its routing information table
Each router updating the metrics with its own information (for example, adding a hop)
Each router broadcasting the new information to its neighbors

Distance vector routing is the oldest type of routing protocol algorithm. As stated, the nature of the algorithm is such that each router builds its routing tables on information received from other routers. This means that when the routers use second-hand information in their tables, they encounter at least one problem: the count to infinity problem.

{Answer to Self Test Question # 15}The count to infinity problem is a routing loop that results from the way that distance vector routing protocols uses second-hand information when a router "goes down" or otherwise becomes unavailable to network traffic. Convergence, or the process of updating routing tables on all routers in an autonomous system, is slow in a distance vector algorithm. This is due to the fact that all routing information in a router's table is sent at once. When all routers do this together, it simply takes a long time for every one to be updated and synchronized.

Figure 5-10 illustrates how a count to infinity problem occurs. Router A sends information about the network segment 192.168.1.0 to router B. Router B will tell Router C about the segment being two hops away, but can also tell Router A that the route exists two hops away. Router A would normally select the best route, which is the connected interface. However, should that segment go down, Router A would then tell Router B that the network segment was three hops away, assuming that router B would have an alternate route to the network. Router B would then advertise that the 192.168.1.0 segment was four hops away, and the hops would increase until they reached the maximum hops, or infinity, for that protocol. For example, if the maximum hops were 16, when the hops reached 16 for the router, it would then consider that route unreachable, remove it from its table and no longer advertise the route.

Figure 10 Count to infinity

The count to infinity problem can cause an unstable network condition due to inaccurate routing that can last for several minutes. Some distance vector protocols have added some complexity to counteract this.

Split horizon
Poison reverse

Split horizon is when a router filters the updates it sends to its neighbors by omitting any references to networks learned from the interface to which it is sending updates. So in Figure 5-10, Router B would send the information about 192.168.1.0 to Router C, but not to Router A.

{Answer to Self Test Question # 16}Poison reverse is a slightly modified version of split horizon. Instead of filtering the updates, it flags that route as unreachable, usually by increasing the hop count to the "infinity" level, when that route came from the interface that it was originally sent from. So, in our example, Router B would send the correct information that network 192.168.1.0 is 2 hops away to Router C. If infinity was defined as 16 hops, Router B would send the information that network 192.168.1.0 is 16 hops away to Router A.

Although split horizon and poison reverse can do much to stabilize a network, they still do not prevent more complex internetwork systems from encountering the count to infinity problem. Figure 5-11 illustrates how a count to infinity problem can still occur.

Figure 11 Poison reverse and count to infinity

Router C will hear about network 192.168.1.0 from both Router A and Router D. It will select whichever route it hears from first. Assume that it selects Router A.
Router C will send an update to Router D that network 192.168.1.0 is available at three hops away, and send a "route unreachable" back to Router A.
Since Router D has a closer two-hop route through its other interface, it ignores this route and uses that interface.
If the interface on Router B to network 192.168.1.0 goes down, it will stop sending this route to both Router A and Router D. They will also stop sending the route to Router C.
However, Router D may receive information from Router C that the route is available three hops away, before Router C hears that the route is unavailable from the source Router A.
Instead of dropping the route, Router D updates Router B that it has another route available to the network 192.168.1.0, which Router B sends to Router A.
Then, when Router A tells Router C that its original route is not available, Router C will stop advertising that it has that route available to Router D.
But it will hear from Router A that another route is available to network 192.168.1.0 that is even further hops away.
The router will then tell Router D that this "new" further route is available.
The routing loop continues until the "infinity" mark is reached.

{Answer to Self Test Question # 36} To further counteract this behavior, a holddown interval was added to the distance vector routing protocol. In this method, when a router hears of a route that is no longer reachable, it starts a timer during which it ignores any information about that destination network. If the holddown interval is sufficiently long, it will prevent these problems. However, in large or complex internetworks, the holddown interval would have to be extremely long in duration in order to prevent the problems. For example, in a network with 100 routers, it is conceivable that an unreachable route might be advertised on a network for almost an hour before it is removed from the network.

To reduce this time, some distance vector routing protocols include negative reachability as information in their routing table updates. The route failure is usually updated in the format of having an unreachable hop count, or infinity. This propagates a route failure quickly and speeds convergence, or the delay between the time a route change has occurred and all routers being updated.

Flash updates (also know as triggered updates) are sent whenever a router's routing information table is changed in a way that affects its updates. If a router uses flash updates and negative reachability information, it can speed a failed route throughout a network in seconds. This greatly shortens convergence time.

Link-State Routing Protocols

The purpose of the link-state routing protocol is to map out the internetwork topology. Each link-state router provides information about the topology in its immediate vicinity. This includes:

The segments (link) to which the router is attached
The status (state) of the those links

The information is flooded across the network so that all routers receive first-hand information. Link-state routers do not broadcast all information included in their routing tables. Instead, the link-state routers will send information about routes that have changed. Link-state routers will send "hello" messages to their neighbors called a link-state packet (LSP) or link-state advertisement (LSA). The neighbors then copy the LSP to their routing tables and forward that information to the rest of the network. {Answer to Self Test Question # 38} This process is called flooding. It results in the sending of first-hand information to the network, building an accurate map of updated routes for the network.

{Answer to Self Test Question # 37} Link-state routing protocols use a method called cost rather than hops. Cost is assigned automatically or manually. Depending on the algorithm of the link-state protocol, cost can take into account the number of network segments that the packet will have to cross, the bandwidth of the links, the current load on the link, or even additional weighted amounts placed by the administrator.

When a link-state router comes upon a link-state internetwork, it sends a "hello" packet to learn about the neighbors.
The neighbors reply with the information about their connected links and the cost metrics associated with them.
The original router builds its routing table from this information.
Then, as part of the periodic update, the router sends a link-state packet to its neighbors. This LSP includes the links for that router and the associated costs.
Each neighbor copies the packet, and the LSP is forwarded on to the next neighbor. This process is called flooding.
Because the routers do not recalculate the routing database before flooding the LSP forward, the convergence time is reduced.

One of the major advantages to link-state routing protocols is the fact that a routing loop cannot form because of the way that link-state protocols build their routing information tables. The second advantage is that convergence is very quick in a link-state internetwork due to the updates being flooded to the internetwork immediately uon a change in the routing topology. These advantages, in turn, free up a router's resources, since there is little time spent in processing and bandwidth consumption of bad route information. Maintaining the link-state database for the router's area places a RAM burden on the router. Similarly, the Dijkstra algorithm has to be executed every time a route changes; this can places a huge CPU burden on all the routers. The Dijkstra algorithm is shortest path first, where iteration on path length determines the shortest path spanning tree. Table 5-1 compares the advantages of the two kinds of routing protocols.

	Distance Vector	Link State
Periodic updates	Entire routing table sent to neighboring routers	Link-state update packets of only the connected links are flooded to entire network
Routing table	Built on second-hand information	Built on first-hand information
Size of updates	Large	Small
Overhead	More bandwidth consumption for routing table being sent, although limited to local router links for each router	More difficult computations taking up more CPU usage
Convergence	Slow	Fast
Routing loops	More prone, uses split-horizon, poison reverse, and timers to avoid	Less prone. Creates a consistent network map
Routing metric	Hops	Cost

Table 1 Link State vs. Distance Vector
Interior vs. Exterior Gateway Protocols

In a large internetwork, such as the Internet, smaller internetworks are divided into autonomous systems. Each AS is considered a self-managed internetwork. A large corporate network connected to the Internet is its own autonomous system, since other hosts on the Internet are not managed by it, and it does not share internal routing information with the Internet routers. By the same token, no other systems on the Internet manage that corporate network either, nor do they share their routing information with the corporation's autonomous system. One key benefit of an AS is the filtering of granular routes. Instead, only summary routes are exchanged. This minimizes the number of routing updates from flapping routes.

{Answer to Self Test Question # 39} Certain routing protocols were developed for managing systems within an autonomous system. They are called Interior Gateway Protocols (IGP). Interior Gateway Protocols are also known as intra-domain, since they work within the domain, but not between domains. These protocols recognize that the routers they deal with are part of their system and freely exchange routing information with them.

Certain routing protocols were also developed for connecting autonomous systems in a larger internetwork. They are called Exterior Gateway Protocols (EGP). {Answer to Self Test Question # 40} Exterior Gateway Protocols are known as inter-domain, since they work between domains. These protocols recognize that they are on the edge of their system, and only exchange the minimum of information necessary to maintain the capability to route information. This adds a security level to the autonomous system. Figure 5-12 illustrates an IGP and an EGP.

Figure 12 Autonomous systems

RIP

{Answer to Self Test Question # 17} Routing Information Protocol (RIP) is a distance vector protocol for use intra-domain (on the interior of a gateway). There are actually two versions of RIP in the TCP/IP protocol suite. Version 1is the original. Version 2 is the updated version. Version 2 is used almost exclusively because of its enhanced capabilities.

The original RIP was designed for the Xerox PARC Universal Protocol (PUP) in 1980 and subsequently used in XNS (Xerox Network Service protocol suite). In 1982, BSD (Berkeley Standard Distribution) UNIX implemented RIP in routed protocols. RIP was finally defined in 1988 in RFC 1058. Other implementations of RIP exist in other protocol suites, such as Novell's IPX-based RIP, but they will not be discussed in this chapter.

RIP was designed for small networks. {Answer to Self Test Question # 41} It has a limitation of 16 hops, which severely limits the size and design of a network. Routes are chosen based on the hop count, not on the bandwidth or availability of a link. This means that a network with a hop count of two would be selected over a network with a hop count of three, even if the latter network had much more available bandwidth. In Figure 5-13, Router D would select the 56-Kbps link before selecting the route through Router C, and subsequently Router A, in order to reach network 192.168.1.0 through Router B. So RIP can present a large problem when requiring flexibility in route selection criteria.

Figure 13 RIP network selection

RIP version 2 includes the following enhancements:

Authentication
Automatic route summarization
Variable-length subnet masking (VLSM)

For a router with three interfaces that will be using RIP, basic RIP configuration would be as follows.

Router rip

Network 192.168.1.0

Network 192.168.2.0

Network 192.168.3.0

The first statement identifies the routing protocol and enables RIP. The next three statements associate the router's directly attached interfaces with RIP.{Answer to Self Test Question # 42} These are the only two required statement sets for RIP to be configured on a router. The remaining RIP configuration statements are optional.

In order to enable RIP routing updates to be sent to nonbroadcast networks, the router must be configured to add those routers to its neighbor's list. The statement neighbor 192.168.2.4 identifies a router with that address to be a neighbor from a nonbroadcast network. The neighbor command is neighbor {IP address}.

Sometimes, there is a need to increase the routing metrics for routes learned from RIP, either for incoming or outgoing route updates. The way to do this is with an offset-list command. The offset-list command is offset-list {name or access list number} {in|out} {offset amount}.

RIP uses a 30-second update timer for when it sends updates to neighboring routers. There are other timers used in managing how RIP works. To adjust the various timers used, there is a single command to use: timers basic {update | invalid | holddown | flush}. The timers are:

Update the number of seconds between updates

Invalid the number of seconds after which a route is declared invalid

Holddown the holddown interval of seconds on all interfaces for a route that was declared unreachable by one interface, before new updates will be accepted for that network

Flush the number of seconds before a route is removed from the routing information table.

In order to specify a version of RIP, the command VERSION 1|2 can be used. The default configuration is that the router receives RIP version 1 and version 2 updates, but will only send version 2 updates. The VERSION command allows restriction to receive and send only one version of RIP. To override the behavior for a specific interface, the ip rip send version 1|2 command and the ip rip receive version 1|2 command can be used.

{Answer to Self Test Question # 43} When using RIP version 2, RIP authentication can be used. The key-chain parameter determines the set of keys that can be used for that interface. The key-chain must be configured for authentication to work on the interface. The command to use is ip rip authentication key-chain {name of chain}. The interface can use either MD5 or plain text authentication using the command ip rip authentication mode {text|MD5}.

To disable the automatic route summarization of RIP version 2, use the command no auto-summary.

The router automatically validates the source of incoming RIP updates. For invalid source addresses, the update gets discarded. This behavior might not be desirable, and to disable it, use the command no validate-update-source.

RIP can use the split-horizon mechanism to reduce routing loops. The split-horizon behavior might not be desirable for nonbroadcast networks. To enable split-horizon, use ip split-horizon. To disable split horizon, use no ip split-horizon. The split-horizon command is interface-level, not router.

When a fast router sends updates to a slower router, there might be a need for a delay in the RIP updates. The default behavior is that there is no delay. To enable a delay of 8 - 50 milliseconds, use the output-delay {#of milliseconds} command.

Router rip

Network 192.168.1.0

Network 192.168.2.0

Network 192.168.3.0

neighbor 192.168.2.4

offset-list ethernet 0 in 2

timers basic update 60

version 2

ip rip authentication key-chain chain1

ip rip authentication mode md5

no auto-summary

no validate-update-source

output-delay 40

interface ethernet 0

ip address 192.168.2.1 255.255.255.0

ip split-horizon

IGRP

{Answer to Self Test Question # 18}IGRP stands for Interior Gateway Routing Protocol. It is a dynamic distance vector routing protocol created by Cisco. IGRP is used in an autonomous system and includes the capability to advertise interior routes, exterior routes, and system routes, as illustrated in Figure 5-14.

Interior routes routes between subnets in the network attached to a router's interface

Exterior routes routes to networks outside the autonomous system

System routes routes within the autonomous system

IGRP also includes a concept for the gateway of last resort, which is the route chosen from the exterior routes to be used when there is no other route known for a destination network. Each router can use a different gateway of last resort. When connecting to the Internet, the Internet-connected interface would be a good gateway of last resort choice.

Figure 14 Interior, exterior and system routes

{Answer to Self Test Question # 44} IGRP updates are broadcast every 90 seconds. After a route is missed for three update periods, the route is considered unreachable. After seven update periods, the route is removed from the routing information table. {Answer to Self Test Question # 19}In addition to the periodic updates, IGRP uses flash updates that advise of route changes and poison reverse updates of routes that are unreachable. This is to expedite convergence. Poison reverse is used with the holddown interval, in order to prevent routing loops.

IGRP is an Interior Gateway Protocol using distance vector algorithm. It was designed by Cisco in the mid-1980s for use in complex or large networks. In order to be used on large networks, IGRP has some significant differences from RIP. The first is that the IGRP uses a combination of metrics to determine the best route selection. {Answer to Self Test Question # 45} This includes the bandwidth, the internetwork delay, load, and reliability as factors in determining that optimal path selection. {Answer to Self Test Question # 20}The administrator is given the ability to set the metrics weighting factors to control how routes are selected. If the administrator does not set a weighting factor, then the default weightings are used to calculate the routes.

IGRP also allows multiple redundant paths to a destination network. Multiple paths are automatically failed over from a primary path to an alternate path if the primary path becomes unavailable.

Just like RIP, IGRP uses split-horizon, poison reverse and holddown intervals to reduce the occurrence of routing loops. Also, flash updates are sent when a route is determined to be unavailable, in order to speed convergence.

There are a few tasks for configuring IGRP on a router. The minimum commands for configuring IGRP are router igrp {autonomous-system} and NETWORK {network number}, which enable IGRP and associate a network with the IGRP protocol, respectively. If no network is associated with IGRP, then it will not be advertised.

IGRP can be configured further. In order to increase the metrics for routes learned via IGRP, an offset list can be set, just as it was for RIP using the offset-list {access list number|name} {in|out} {offset #}.

Like RIP, IGRP is a broadcast protocol. In order to send IGRP routing updates to nonbroadcast networks, use the NEIGHBOR {ip address} command.

IGRP allows unequal-cost load balancing, which enables network traffic to be distributed across up to four unequal-cost routes to the same destination network. The path variance (the difference in advantage of the primary and alternate paths) is used to determine whether a path is feasible-that is, it can be included in the routing table by virtue of the closeness of the next router in the path to the destination network. If that metric is within the specified variance, the path is included. The variance is by default set to 1, enabling an equal-cost load balancing. To allow unequal-cost load balancing, use the VARIANCE {number multiplier} command. To distribute network traffic proportionately to the ratio of the path costs, or to select a minimum-cost route, use the TRAFFIC-SHARE {balanced | min} command.

The timers command for RIP is identical for that of IGRP. The timers that can be adjusted are:

Update the number of seconds between updates

Invalid the number of seconds after which a route is declared invalid

Holddown The holddown interval of seconds on all interfaces for a route that was declared unreachable by one interface before new updates will be accepted for that network

Flush the number of seconds before a route is removed from the routing information table

The command for timers is TIMERS BASIC {update | invalid | holddown | flush} {#of seconds}.

To disable the holddown period, use the command no metric holddown. This can be configured to shorten convergence time in IGRP. Note that all holddown configurations must be identical on all routers within an autonomous system.

IGRP has a maximum hop count of 255 hops. The default configuration for a router is 100 hops. To change this, use the command metric maximum-hops {number of hops}.

To turn off the feature that validates the source IP address for incoming route updates, use the command no validate-update-source.

To enable or disable the split-horizon algorithm, especially for nonbroadcast networks like Frame Relay or SMDS, use the commands ip split-horizon and no ip split-horizon.

Router igrp 1

Network 192.168.1.0

offset-list ethernet 0 out 8

neighbor 192.168.8.11

variance 3

traffic-share balanced

timers basic flush 60

no metric holddown

metric maximum-hops 60

no validate-update-source

interface ethernet 0

ip address 192.168.1.8

no ip split-horizon

EIGRP

Enhanced Interior Gateway Routing Protocol is an updated version of IGRP. {Answer to Self Test Question # 47} EIGRP uses the same distance vector algorithm and distance information as IGRP. It has enhanced convergence properties, and effectively, the same efficiency. The convergence technology is known as Diffusing Update Algorithm (DUAL). DUAL guarantees that there will be no routing loops, and allows all the routers involved in a routing change to synchronize simultaneously. Routers that are not affected by the routing change do not need to synchronize.

{Answer to Self Test Question # 46} EIGRP includes the following features:

Automatic redistribution of IGRP routes into EIGRP interfaces, and EIGRP routes into IGRP interfaces, when EIGRP and IGRP use the same AS on the same router
Maximum hops of 224
Partial updates are sent when the state of a destination network changes, instead of the entire routing information table, resulting in less bandwidth and CPU usage
Variable-length subnet masks to increase the available IP addresses, or distribute them more appropriately
Neighbor discovery through a hello system used to identify neighboring routers

The neighbor discovery system is the process that routers use to identify neighboring routers dynamically, and to determine when those routes become unreachable. Small, low-overhead hello packets are used to discover the neighboring routers, and maintain the functioning status of neighbors through the continued receipt of hello packets.

Some EIGRP packets use reliable, acknowledged transport protocols, while others, such as the hello packets, do not. EIGRP gains in reliability as well as bandwidth usage with this scheme.

DUAL has a decision process for route computations. This DUAL finite-state machine uses the distance information (metric) and selects routes to be added to the routing information table based on the feasible successors. A successor is defined as a neighboring router used for packet forwarding with a least-cost path to a destination, and guaranteed not to be a part of a routing loop.

EIGRP, like OSPF, requires an autonomous system number statement in its router configuration. When using multiple processes in EIGRP, the routers in different ASs do not exchange information. The following is a common router configuration for EIGRP:

router eigrp 1

network 192.168.1.0

network 192.168.2.0

network 192.168.3.0

OSPF

OSPF stands for Open Shortest Path First. It is a link-state protocol for the TCP/IP protocol suite. OSPF uses a concept known as adjacency. OSPF routers are considered adjacent when they have synchronized link-state databases (the link-state version of a routing information table).

Route aggregation is also something that OSPF can do. Route aggregation is the capability to limit the number of entries in the link-state database through the use of a different subnet mask, making multiple routes appear to be a single route entry. For the example networks of 192.168.1.0 through 192.168.254.0, the route aggregate would be 192.168.0.0 with a subnet mask of 255.255.0.0, appearing to be the equivalent of a single Class B IP addressed network, while actually consisting of 254 Class C networks. The reduction in traffic overhead by using route aggregation can be huge when used in large, complex internetworks.

OSPF introduces areas (similar to autonomous systems) as a level of hierarchy not used in many other protocols. An area is a contiguous portion of the internetwork that does not share its internal routing information with other areas. This adds a level of scalability for larger networks, since every destination subnet will not require an entry in the routing table of every router. Routers that have all interfaces connected to a single area are called internal routers. Routers that are connected only to the backbone are backbone routers. Routers on the edge of multiple areas, which have interfaces connected to more than one area, are called area border routers. An autonomous system border router (ASBR) connects OSPF to another IGP or EGP. In configuring areas, use the following criteria:

Each area must be contiguous
Each area must border, or connect to, area 0 directly
Each network (and by virtue of connection, each router interface) must connect to a single area.
OSPF link-state advertisements will only propagate throughout a single area, but not further

The OSPF version 2 supported by Cisco is described in RFC 1583. The following features are supported:

Stub areas, which are connected to a single area through one router, which means that the network can be moved without significant reconfiguration
Route redistribution, when a route is learned from any IP routing protocol, allowing routes to be used regardless of how they are connected
Authentication, which uses either plain text or MD5 authentication, to control which neighboring routers will be allowed to gain access to this OSPF router in order to exchange routing information
NSSA (Not So Stubby Areas) as described in RFC 1587
OSPF over demand circuit as described in RFC 1793

When configuring OSPF, keep in mind that OSPF area IDs can be represented as ordinal numbers, or in dotted-decimal equivalent (for example, 0.0.0.0 is the same as area 0). In order to configure OSPF, the minimum commands needed are to enable OSPF and associate the interface with a defined area. These commands are router ospf {autonomous system} and NETWORK {address} {mask} AREA {area-id}.

The following are some basic OSPF configuration commands. To configure the OSPF costs, use the command ip ospf cost {cost}. To change the number of seconds between link-state advertisement retransmissions, use the command ip ospf retransmit-interval {seconds}. To specify the number of seconds it should take to transmit a link-state advertisement, use the command ip ospf transmit-delay {seconds}. To set the priority in order to select the designated router for an OSPF network, use ip ospf priority {number}. To specify the number of seconds between hello packets, use the command ip ospf hello-interval {seconds}. To state the number of seconds that a certain router's hello packets must be missing before the neighboring routers declare that it is down, use the command ip ospf dead-interval {seconds}. To assign a password to be used by neighboring routers for OSPF simple password authentication, use ip ospf authentication-key {key}. To enable OSPF MD5 authentication, use ip ospf message-digest-key {keyid} MD5{key}.

router ospf 1

network 192.168.1.0 0.0.0.255 area 1

network 0.0.0.0 255.255.255.255 area 0

ip ospf cost 10

ip ospf retransmit-interval 40

ip ospf transmit-delay 20

ip ospf priority 4

ip ospf hello-interval 90

ip ospf dead-interval 90

Certification Summary

Routing is used to segment congested networks, increase the number of nodes allowed on the network, filter, and manage traffic. Routing protocols are used to maintain the routes available to the network.

Metrics are used to determine the distance or cost of the destination networks from the initiating router. A metric is the value of a route variable, as computed by the routing protocol. A routing information table is maintained by the routing protocol to aid in selecting the best path to a destination network.

Routing algorithms include the capability to manage routes in a routing information table by manually updating it. These are static routes. Most routing protocols offer a dynamic method for determining routes and maintaining routing tables.

A default route is a static route that is used for any packets that are nonroutable (for which a route to their destination network address does not exist). This allows any packet with a destination address not existing in a router's routing information table to still be handled and forwarded.

Distance vector protocols are older routing algorithm protocols that select routes based on the least hop count. Hops are the number of routers that must be transversed before the destination network is reached. Distance vector protocol routers send their entire routing information table to their neighboring routers. This information is copied to that neighbor's table and then recomputed with a new hop count before being forwarded on to other neighbors. This means that distance vector routing tables are based on second-hand information. Distance vector protocols have low CPU overhead because of the simplicity of the routing table recomputation and route selection algorithms. Distance vector routing protocols easily fall prey to routing loops, but usually include split-horizon, poison reverse, or holddown intervals to counteract them.

Link-state protocols were created to be more scalable to large networks. They use a cost metric for route selection, and store the routing information in link-state databases. When a link-state router comes up on a network, it sends hello packets to its neighbors. The neighbors reply with the information about their connected links and the costs associated with them. The original router builds its link-state database from the neighbor's information. Periodically, a link-state router sends a link-state advertisement to its neighbors, including the links for that router and the associated costs. Each neighbor copies the packet, and the LSA is forwarded on to the next neighbor, through a process called flooding. Because the routers do not recalculate the routing database before flooding the LSA forward, the convergence time is reduced.

Routing Information Protocol has version 1 and version 2. Version 2 is more common. RIP is an older, distance vector protocol. It is also an Interior Gateway Protocol, with a maximum hop count of 16. Updates occur every 30 seconds. At each update period, a router sends its entire routing table to its neighbors. The neighbors recalculate routes based on any changes included in the updates. RIP uses split-horizon, poison reverse, and holddown intervals to avoid routing loops.

Interior Gateway Routing Protocol is a distance vector protocol, as well as an Interior Gateway Protocol, with a maximum hop count of 224. IGRP was created by Cisco, and has an enhanced version available: EIGRP. Instead of relying on periodic updates, IGRP uses flash updates whenever a change occurs on the network. This process speeds up convergence.

Two-Minute Drill

Internetworks use routing to get data from one network to another.
Bridging is the capability to connect two or more physical network segments such that the connection is transparent to the network.
Switching is a way to increase bandwidth (as well as limit the amount of traffic a node encounters) by providing a dedicated channel for each switched port. Switching occurs at the data link layer.
Routing occurs at the network layer, and includes the capability to separate the management of the segments on the internetwork.
There are two basic mechanisms that make up routing:
Determination of routes
Transmission of data packets across the internetwork
One of the terms to be aware of for route determination is metric. A metric is the value of a variable, such as the network delay, after the routing protocol algorithm has computed it.
Routing protocols both create and maintain a routing information table, or routing table.
The routing update can consist of the router's entire routing table, or only the portion that has changed.
There are three major objectives of a routing algorithm:
Accuracy
Low overhead
Quick convergence

Convergence is the process of all routers synchronizing their routing information tables, or the time it takes for a single routing change to be reflected in all routers.
Some of the types of routing algorithms are:
Static vs. dynamic
Interior vs. exterior
Distance vector vs. link state
Dynamic routing protocols include a method for dynamically configuring the routing information table.
A static route is a route that has been manually entered into the routing table.
Hierarchical routing allows the limitation of routing information propagation throughout an entire internetwork.
A default route is the one specified for data to follow if there is no explicit routing information for it to use in finding a direction.
The two types of dynamic routing are link state and distance vector.
A distance vector protocol router periodically sends its neighboring routers two pieces of information.

Flash updates (also know as triggered updates) are sent whenever a router's routing information table is changed in a way that affects its updates.
The purpose of the link-state routing protocol is to map out the internetwork topology.
Interior Gateway Protocols are also known as intra-domain, since they work within the domain, but not between domains. These protocols recognize that the routers they deal with are part of their system and freely exchange routing information with them.
Exterior Gateway Protocols are known as inter-domain, since they work between domains. These protocols recognize that they are on the edge of their system, and only exchange the minimum of information necessary to maintain the capability to route information.
Routing Information Protocol (RIP) is a distance vector protocol for use intra-domain (on the interior of a gateway).
IGRP is used in an autonomous system and includes the capability to advertise interior routes, exterior routes, and system routes.
EIGRP uses the same distance vector algorithm and distance information as IGRP. It has enhanced convergence properties, and effectively, the same efficiency.
OSPF stands for Open Shortest Path First. It is a link-state protocol for the TCP/IP protocol suite. OSPF uses a concept known as adjacency.

Self Test

The following questions will help you measure your understanding of the material presented in this chapter. Read all the choices carefully, as there may be more than one correct answer. Choose all correct answers for each question.

Company A has recently merged with Company B, which exists in the same building and is physically close enough for all the computers to belong on the same network segment. Company A uses an ATM backbone and Fast Ethernet for all nodes. Company B has a Token Ring environment on shielded twisted-pair wiring. Why will Company A and Company B select a router for their newly merged network?

Network segment size has reached the maximum
Network addresses are not sufficient for a merged network
Traffic must be segmented to prevent an expected bandwidth overload
A router is the usual way to connect dissimilar network types

CCNA Routing and Switching Study Guide: Self Test for Exam 640-407