Routing Algorithm Characteristics


Routing protocol algorithms can be classified by type. Key characteristics include the following categories:

  • Static and dynamic

  • Single- path and multipath

  • Flat and hierarchical

  • Host-intelligent and router- intelligent

  • Intradomain and interdomain

  • Distance vector and link-state

  • Classful and classless

  • Convergence

We discuss these characteristics in more detail in the following sections.

Static and Dynamic

The static routing process is really not an actual algorithm but rather a set of table mappings established by the network administrator before the beginning of the routing process. These mappings do not change unless the administrator adjusts them. Static routes provide a high degree of administrative simplification, control, and security. They function best in environments in which network traffic is relatively predictable and the network design is relatively simple. The downside to static routing is the administrative overhead and lack of scalability. You use the following global configuration command to add a static route to an IP routing table:

  ip route  prefix mask {address  interface} [distance] 

Table 2.2 explains the ip route command options.

Table 2.2. Description of the ip route Command

ip route

Description

prefix mask

Prefix and mask for the destination added to the IP routing table

address

IP address of the next hop router to the destination

interface

Outbound interface to reach the destination

distance

Administrative distance (optional)

Static routing systems do not react to network changes; therefore, they are generally considered unsuitable for medium to large, constantly changing networks. If only one path exists to the Internet or another autonomous system, it might be appropriate to use a default or static route.

ip route Configuration Options

Some subtle differences exist between the next-hop address parameter and the next-hop interface parameter. For example, a static route that uses the next-hop address has a default AD of 1 , whereas the interface parameter sets the AD of the static route to . In other words, the next-hop address parameter makes the route appear as a typical static route (AD=1) as opposed to a directly connected link (AD=0). You should use the next-hop address option if you are configuring multiaccess media for Ethernet LANs, Frame Relay, ISDN, and so on.

If you want your static route to have an administrative distance that is higher than the default, you can create what is known as a floating static route . You can generate a floating static route by setting the administrative distance higher than the default or learned routes. For example, if you wanted to generate a path of last resort, you could statically configure a route to be overridden by routes that are learned via a dynamic routing protocol. If the dynamically learned information became unavailable, you could fail over to the floating static route. You will see some examples of this technique when learning about the BGP protocol in Chapter 8, "Configuring Border Gateway Protocol."


Static routes can complement dynamic routing algorithms when necessary. For example, a router of last resort (the router to which all unroutable packets are sent) can be designated to forward packets if no path to the destination exists in the routing table. If a network has only one outbound WAN connection to an ISP, for example, an administrator can configure a static default route to the provider.

Most of the dominant routing algorithms used today are dynamic routing algorithms, which adjust to changing network circumstances by analyzing incoming routing update messages. If the message indicates that a network change has occurred, the routing software recalculates the routes and sends out new routing update messages. These communications filter through the network and motivate routers to recalculate their algorithms and update their tables accordingly . This book focuses almost exclusively on the operations of dynamic routing algorithms.

Single-Path and Multipath

Some advanced routing protocols support multiple paths to the same destination. Unlike a single-path algorithm, a multipath algorithm allows traffic to be multiplexed over multiple equal-cost or unequal -cost lines. All the covered IP dynamic routing protocols can load balance across multiple equal-cost paths to deliver packets.

Only the Cisco proprietary routing protocols ”IGRP and EIGRP ”can load balance across multiple, unequal-cost paths.


The advantages of multipath are really seen on the routers that function at the highest hierarchical level (the backbone) of the routing topology. The principle benefit of hierarchical routing is that it can imitate the company's organizational structure and provide support for practical traffic patterns.

Intradomain and Interdomain

The ISO created a hierarchical framework that helps describe the router switching process. Using this framework, network devices that do not have the means of forwarding packets between subnetworks are called end systems (ESs) , whereas network devices with these capabilities are called intermediate systems (ISs) . ISs are then divided into two subsystems: ISs that can communicate within routing domains are known as intradomain ISs, and those that communicate both within and between routing domains are called interdomain ISs.

Some routing algorithms work only within domains or autonomous systems, whereas others work within and between autonomous systems. Intradomain routing protocols are also known as interior gateway protocols (IGPs). These protocols are used to exchange routing information within a domain and are represented by protocols such as RIP and IGRP.


A routing domain (or area ) is typically defined as a system that is part of an internetwork and under a common administrative authority controlled by a specific set of rules. Routing domains are also commonly known as autonomous systems. In addition, routing domains can be further divided into routing areas with certain routing protocols even though intradomain routing protocols are still used for switching both within and between areas.

Interdomain protocols are sometimes generically referred to as Exterior Gateway Protocols (EGPs) . This is a broad term that represents protocols used to exchange routing information between autonomous systems. Border Gateway Protocol (BGP) is a commonly used interdomain EGP. Because the very nature of these two algorithm types is different, it stands to reason that the best choice for an intradomain routing algorithm would not necessarily be an optimal interdomain routing algorithm.

Classful and Classless

Routing protocols can also be categorized as classful or classless protocols. RIPv1 and IGRP are considered classful protocols because they do not send subnet mask information with the network address in the routing update message. Classful addresses use a scheme in which the major network number is either Class A, B, C, D, or E. In a classful protocol environment, all the subnets of the major network address class must use the same subnet mask. For instance, if a router receives an update that has the same major network number (for example, 172.16.0.0) that is configured on the inbound interface, the router applies the subnet mask configured for the interface. However, if the routing update is for a major network different from the inbound interface, the default Class A, B, or C subnet mask is used and applied to the routing table.

You must know how to determine the class of an IP address by looking at the decimal value of the first octet. This is discussed in more detail in Chapter 3, "Extending IP Addresses."


If routing information is swapped between networks using different major network numbers , the receiving routers will not know the subnet mask being implemented because the subnet information is not stored in the routing update packets. As a result, subnetwork information from all the major networks must be summarized to a classful network number using the default subnet mask before the update is added to the table. Only routers configured for the major networks to which the subnets belong can trade subnetted route information; the routers that belong to different major networks trade the classful summary routes. Classful routing protocols automatically generate a classful summary route at major network boundaries, as shown in Figure 2.2.

Figure 2.2. RIPv1 routers do not deliver subnet mask information.

As you can see, only routing devices within the same major network share subnetworked route information. Classful summary routes are automatically generated at Class A, B, and C network boundaries by routers using classful routing protocols such as RIPv1 and IGRP.

Be sure that you allocate the same subnet mask to all interfaces on all of the routing devices in the major network in the classful routing area. This is crucial to ensure the proper advertisement of all subnetwork routes.


Classless routing protocols were originally developed to overcome the limitations inherent to classful protocols such as RIPv1. The classless routing protocols commonly used by Cisco router devices are OSPF, EIGRP, RIPv2, IS-IS, and BGP-4. Classless protocols have the advantage of including the subnet mask for each route to perform a more advanced lookup in the routing table. Classless routing protocols also implement a manual summarizing technique that allows summarization at any bit position in the network. Route summarization is the process of consolidating advertised addresses in a routing table. This technique leads to smaller routing tables, reduced update traffic, and lower processing and memory overhead. This really comes in handy because the routing tables of the Internet routers seem to expand almost exponentially with the growth of the Web. Route summarization is also referred to as route aggregation.

Classless routing protocols have the benefit of understanding the concept that different routes can have different masks in a major network. This technique of using different subnet masks is called variable-length subnet masking ( VLSM ) . VLSM enables network engineers to optimize the available address space and construct a hierarchical addressing scheme that fits the environment. This concept is explored in depth in Chapter 3.

Distance Vector and Link-state

The notion of a vector in networking relates to both the distance and the direction to a destination. Distance vector protocols, such as RIP, use the Bellman-Ford algorithm and call for each router to send all or some portion of the routing table to their directly connected neighbors. Distance vector routers know about, and send updates to, only these neighbors. Therefore, a router's picture of the network topology depends on the perspective of its neighbors. This process is also affectionately known as routing by rumor . The Cisco IOS supports several distance vector protocols, including RIPv1, RIPv2, and IGRP. As far as the OSI model is concerned , IGRP functions at the network layer with a protocol number of 9 in the IP header. RIP also functions primarily at the network layer, uses UDP port 520, and finds the best path to a remote network using hop count as a metric. IP RIP has a maximum hop count of 15, and IGRP has a maximum of 255. Tables 2.3 and 2.4 show the characteristics and comparisons of distance vector routing protocols, respectively.

Table 2.3. Attributes of Distance Vector Protocols

Attribute

Description

Protocols

RIPv1, RIPv2, IGRP, and EIGRP (hybrid).

Periodic updates

Updates sent at a set interval ”for example, 30 seconds with RIPv1.

Full table updates

Pure distance vector sends the entire routing table.

Broadcast updates

Devices running distance vector routing protocols listen for broadcast updates to 255.255.255.255.

Triggered updates

Flash update is sent when change occurs apart from default update.

Split horizon

Prevents routing loops and preserves bandwidth by preventing a network from being forwarded on the same interface on which it was learned.

Count to infinity

Maximum hop count value varies with protocol.

Algorithm

Bellman-Ford and Diffusing Update Algorithm (DUAL). DUAL is a hybrid convergence algorithm used in Enhanced IGRP.

Table 2.4. Contrasting IP Distance Vector Routing Protocols

Attribute

RIPv1

RIPv2

IGRP

EIGRP

Count to infinity

X

X

X

 

Split horizon

X

X

X

X

Hold-down timers

X

X

X

 

Triggered updates with route poisoning

X

X

X

X

Equal path load balancing

X

X

X

X

Unequal path load balancing

   

X

X

Metric

Hops

Hops

Composite

Composite

Algorithm

Bellman-Ford

Bellman-Ford

Bellman-Ford

DUAL

Maximum hop count (default)

15

15

100

100

Support for VLSM

 

X

 

X

Link-state algorithms, such as OSPF, are also referred to as shortest path first algorithms. Link-state protocols generate routing updates only when a change occurs and flood the resulting routing information to all nodes in the internetwork in the form of a link-state advertisement (LSA). Each router sends only a portion of the routing table that describes the state of its own links. Link-state routers build a picture of the entire network in a topology table and typically require a hierarchical design (except EIGRP). Because they can converge more quickly, link-state algorithms are somewhat less prone to routing loops than distance vector algorithms. On the other hand, link-state algorithms typically require more CPU power and memory than distance vector protocols. Although link-state protocols are generally more scalable than distance vector protocols, they can also be more expensive to implement and support. EIGRP is actually a hybrid routing protocol that has some attributes of link-state operation. Other link-state protocols covered in this book are OSPF and IS-IS. Tables 2.5 and 2.6 show the characteristics and comparisons of link-state routing protocols, respectively.

Table 2.5. Attributes of Link-state Protocols

Attribute

Description

Protocols

OSPF, IS-IS

Periodic updates

Only when a change occurs. OSPF also sends a summary every 30 minutes

Broadcast updates

Devices running link-state routing protocols listen for broadcast updates to a multicast address

Database

IP routing table that holds all topological information

Convergence

Faster than distance vector

Resources

Higher CPU and memory resource usage

Algorithm

Dijkstra

Find out more about Dijkstra in Chapter 4, "Implementing OSPF in a Single Area" and Chapter 5, "Interconnecting OSPF Areas."


Table 2.6. Contrasting IP Link-state Routing Protocols

Attribute

EIGRP

IS - IS

OSPF

Requires hierarchy

 

X

X

Retains information of all possible routes

X

X

X

Manual route summarization

X

X

X

Automatic route summarization

X

   

Announcements triggered by changes

X

X

X

Equal path load balancing

X

X

X

Unequal path load balancing

X

   

Metric

Composite

Cost

Cost

Algorithm

DUAL

IS-IS

Dijkstra

Maximum hop count (default)

100

1024

Unlimited

Support for VLSM

X

X

X

Convergence

Routing algorithms must provide at least one single, loop-free route to every possible destination network. All the routing tables in the routing domain or area must eventually be synchronized and in agreement with a useable route to each destination network. This course of action is known simply as convergence. Convergence is defined as the rate and capability of a collection of router devices running a common routing protocol to agree on optimal routes. When a network event causes routes to either go down or become recently available, routers dispense routing update messages to permeate the network and stimulate the recalculation of optimal routes. The goal is to eventually cause all routers to agree on these optimal routes. Routing algorithms that suffer from slow convergence can create routing loops or even network outages. As with the other characteristics of routing protocols previously mentioned, convergence time varies depending on the efficiency of the routing algorithm being used, the size of the network, and several configurable timers.

A route that is going up and down in a short period of time is referred to as a flapping route. The cause of this phenomenon is typically the intermittent failure of network device interfaces and network media.


Convergence is affected by changes in the status of network links, and several ways are available to detect them. For example, if a device functioning at OSI Layer 1 or 2 (an Ethernet network interface) fails to receive a certain number of consecutive keepalive messages, the link is marked as down. In addition, if the Layer 3 protocol fails to receive a number of consecutive hello packets or regular update messages, the link is marked as down. Most routing algorithms use different sets of timers for loop prevention and network topology stabilization during times of recalculation of routing tables.

Understanding how individual protocols converge is critical to effective network engineering as well as success on the Cisco exam.


RIPv1 and RIPv2 Convergence Basics

The RIP version 1 routing protocol is one of the first interior gateway protocols used and has a long history in several routed network environments, including Unix and Microsoft. Besides the lack of scalability (it has a maximum hop count of 15), the other downside to RIPv1 is its rather high time to converge after a network event. Regardless, this routing protocol is the first example to help demonstrate the basic convergence process. Figure 2.3 shows how various routing protocols accomplish convergence.

Figure 2.3. Sample network to demonstrate various methods of convergence.

In Figure 2.3, RouterC notices a failure on network 10.10.0.0 between itself and RouterA. RouterC generates an update, called a flash update , when an event occurs. This special update consists of the full routing table as well as a RIP poisoned route with a metric of 16 (unreachable). The flash update is sent to the neighbors of RouterC: RouterB and RouterD. Subsequently, RouterD generates a flash update and sends it to RouterE. Next, RouterC removes the entry for network 10.10.0.0 and all associated routes from its route table. Because this network is running RIPv2, RouterC sends a query to multicast address 224.0.0.9 to locate another path to network 10.10.0.0 (RIPv1 would use broadcast address 255.255.255.255). RouterD overrides the split horizon rule by sending a poison reverse to network 10.10.0.0. RouterB responds to RouterC with a higher hop count to RouterA, and RouterC adds it to the routing table because it purged it early in the process. Responses to queries are also complete routing tables.

During the state of hold-down, advertised routes that have the same or a poorer metric value than the one the router originally held for a network are summarily ignored.


Next, RouterD goes into a state of hold-down, and it eventually gets an advertisement from RouterC with the weaker metric it learned from RouterB. According to the rules of hold-down, RouterD ignores the weaker metric. Eventually, RouterD and RouterE come out of hold-down (180 seconds) and update their routing tables with the path to network 10.10.0.0 through RouterB. The time for RouterE to converge fully could be as much as 3 1/2 minutes.

You should run the debug ip rip and debug ip routing commands in your test environment to thoroughly monitor and understand the process of RIPv1 and RIPv2 convergence.


IGRP Convergence Basics

Using Figure 2.3 as the prototypical design, IGRP offers greater scalability and flexibility but typically a longer convergence time than RIP. After RouterC notices the failed Ethernet 10.10.0.0 it shares with RouterA, it poisons the route with a flash update to RouterB and RouterD.

Distance vector networks, such as RIP and IGRP, have a maximum network diameter (or hop count) in that they were not designed to operate in environments with hundreds of links and routers. The maximum network diameter designates the distance that a datagram can travel (the maximum number of hops) before the destination is considered unreachable, forcing the datagram to be discarded. IP RIPv1 and RIPv2 both have a maximum hop count of 15, which means anything beyond 15 hops is unreachable. IGRP's default maximum hop count is 100, although it is technically configurable up to 255 hops.


Next, RouterD generates and sends its own flash update to RouterE as RouterC flushes the directly connected downed link from its routing table. Just as with RIP, an IGRP-loaded RouterC also eradicates all the routes related to that link from its routing table. Next, RouterC broadcasts all its interfaces, using logical network address 255.255.255.255, to its neighbors in search of another path to 10.10.0.0. RouterD generates a poison reverse, and RouterC then issues a flash update omitting the failed link that was purged.

Remember that the poison reverse update message is an override exception to the split horizon rule.


Next, RouterB responds to RouterC with a poorer metric value to network 10.10.0.0 than the one originally held by RouterC. RouterC adds it to its routing table and floods the network with a flash update containing the new information. RouterD ignores this update from RouterC because it is in hold-down and the metric is poorer than the one originally known for network 10.10.0.0. It continues to send poisoned updates to RouterC, however. After RouterD and RouterE reach the hold-down timer interval (the default is 280 seconds), they update their tables with the new route from RouterC. The time for RouterE to converge fully could be almost 7 minutes taking into consideration all the IGRP timers.

You should run the debug ip routing and debug ip igrp transactions commands in your test environment to thoroughly monitor and understand the process of IGRP convergence.


EIGRP Convergence Basics

Continuing with the network infrastructure shown in Figure 2.3, EIGRP can provide very rapid convergence in contrast to RIP and IGRP. Although this process is covered in greater detail in later chapters, it is necessary to address some terminology before exploring the EIGRP convergence process. Table 2.7 introduces some key EIGRP concepts.

Table 2.7. Survey of EIGRP Terminology Relating to Convergence

Concept

Description

Advertised distance

The cost between the next-hop router and destination

Feasible distance (FD)

The lowest -cost route to a destination

Feasible successor (FS)

A downstream neighbor with respect to the destination but not the least-cost path for forwarding decisions

Successor

A neighboring router used for forwarding packets along a least-cost path

Topology table

Structure that holds all destinations advertised by neighbor routers

In this routing convergence scenario, the EIGRP-loaded RouterC observes a link failure between itself and RouterA on network 10.10.0.0. RouterC then looks in its topology table to find a feasible successor but does not find a suitable alternative route and begins to look for a new route (the Active state) by sending a query to neighbor routers on EIGRP multicast address 224.0.0.10. RouterD replies that there is no other path to network 10.10.0.0, and RouterB replies with an alternative route containing an entry with a higher feasible distance.

EIGRP uses a bidirectional update scheme in which all routers acknowledge each other's updates to ensure that the neighbor is aware of any changes to the topology.


Next, RouterC sends a new message out all interfaces with this updated information from its topology and routing tables. All of RouterC's neighbors acknowledge the update and send their updates back to RouterC to synchronize and converge the EIGRP network topology. The time for RouterE to converge fully is very rapid and efficient, occurring in as few as 2 “3 seconds.

You should run the debug ip routing, debug ip eigrp neighbors, debug ip eigrp summary , and debug ip eigrp notification tools in your testing to observe and comprehend EIGRP convergence.


OSPF Convergence Basics

Although the OSPF routing protocol is covered extensively in later chapters, we should look at how OSPF converges compare to the previous distance vector protocol types. OSPF also has its own set of terms that set it apart from other algorithms, as shown in Table 2.8.

Table 2.8. Survey of OSPF Terminology Relating to Convergence

Concept

Description

Dead interval

Amount of time an OSPF router will wait before announcing that its neighbor is down

Designated router (DR)

Router chosen to generate LSAs on the OSPF network

Hello packets

Sent periodically to ensure that the router interfaces are still alive

Link-state advertisement

Broadcast packets used to maintain path cost and neighbor information in OSPF routing tables

Referring back to Figure 2.3, the moment that OSPF RouterC notices the failed link to RouterA, it attempts to carry out an election for a designated router (DR) on interface E0. When it fails to reach the neighbor, it deletes the route to network 10.10.0.0 from the routing table. Next, RouterC floods an LSA to RouterB and RouterD. These routers, in turn , flood a copy of this LSA packet out every interface other than the one on which it was received. By default, OSPF routers wait 5 seconds after they receive an LSA before recalculating the shortest path first algorithm. Next, RouterC adds the new route through 10.20.0.0 to its routing table, and RouterB, RouterD, and RouterE update the metric in their routing tables as well.

After a 40-second dead interval, RouterA sends an LSA because it has not received a hello packet from RouterC. The DR on the network up to this point was RouterC, so RouterA becomes the DR and floods another advertisement on the network. The other routers wait 5 seconds and run the shortest path first algorithm so that, eventually, network 10.10.0.0 is reached via RouterB. RouterE eventually becomes converged based on the total detection time and the total LSA flooding time plus 5 seconds. The time for the entire network to converge, however, could take from 45 seconds to 1 minute based on the network design.

You should run the debug ip routing, debug ip ospf adj, debug ip ospf events , and debug ospf packet commands so you can better understand the OSPF convergence process.




Cisco BSCI Exam Cram 2 (Exam Cram 642-801)
CCNP BSCI Exam Cram 2 (Exam Cram 642-801)
ISBN: 0789730170
EAN: 2147483647
Year: 2003
Pages: 170

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net