Chapter Goals
`(cid:127) Learn the basics of routing protocols.
`(cid:127) Learn the differences between link-state and distance vector routing protocols.
`(cid:127) Learn about the metrics used by routing protocols to determine path selection.
`(cid:127) Learn the basics of how data travels from end stations through intermediate stations and on to the
`destination end station.
`(cid:127) Understand the difference between routed protocols and routing protocols.
`
`Routing Basics
`
`This chapter introduces the underlying concepts widely used in routing protocols. Topics summarized
`here include routing protocol components and algorithms. In addition, the role of routing protocols is
`briefly contrasted with the role of routed or network protocols. Subsequent chapters in Part VII,
`“Routing Protocols,” address specific routing protocols in more detail, while the network protocols that
`use routing protocols are discussed in Part VI, “Network Protocols.”
`
`What Is Routing?
`Routing is the act of moving information across an internetwork from a source to a destination. Along
`the way, at least one intermediate node typically is encountered. Routing is often contrasted with
`bridging, which might seem to accomplish precisely the same thing to the casual observer. The primary
`difference between the two is that bridging occurs at Layer 2 (the link layer) of the OSI reference model,
`whereas routing occurs at Layer 3 (the network layer). This distinction provides routing and bridging
`with different information to use in the process of moving information from source to destination, so the
`two functions accomplish their tasks in different ways.
`The topic of routing has been covered in computer science literature for more than two decades, but
`routing achieved commercial popularity as late as the mid-1980s. The primary reason for this time lag
`is that networks in the 1970s were simple, homogeneous environments. Only relatively recently has
`large-scale internetworking become popular.
`
`I 1-58705-001-3
`
`Internetworking Technologies Handbook
`
`5-1
`
`PETITIONERS - AMERICAN/SOUTHWEST, Exhibit 1029
`Page 1 of 10
`
`

`

`H
`
`Routing Components
`
`Chapters Routing Basics
`
`|
`
`Routing Components
`Routing involves two basic activities: determining optimal routing paths and transporting information
`groups (typically called packets) through an internetwork. In the context of the routing process, the latter
`of these is referred to as packet switching. Although packet switching is relatively straightforward, path
`determination can be very complex.
`
`Path Determination
`
`Routing protocols use metrics to evaluate what path will be the best for a packet to travel. A metric is a
`standard of measurement, such as path bandwidth, that is used by routing algorithms to determine the
`optimal path to a destination. To aid the process of path determination, routing algorithms initialize and
`maintain routing tables, which contain route information. Route information varies depending on the
`routing algorithm used.
`Routing algorithms fill routing tables with a variety of information. Destination/next hop associations
`tell a router that a particular destination can be reached optimally by sending the packet to a particular
`router representing the “next hop” on the way to the final destination. When a router receives an
`incoming packet, it checks the destination address and attempts to associate this address with a next hop.
`Figure 5-1 depicts a sample destination/next hop routing table.
`
`Figure 5-1 Destination/Next Hop Associations Determine the Data's Optimal Path
`
`Router 1
`
`Router 2
`
`Packet to
`router X
`
`Routing table
`
`Dest.:
`
`Send to:
`R2
`
`Already updated
`
`Routing table
`
`Dest.:
`
`Send to:
`R1
`
`Not yet updated
`
`Routing tables also can contain other information, such as data about the desirability of a path. Routers
`compare metrics to determine optimal routes, and these metrics differ depending on the design of the
`routing algorithm used. A variety of common metrics will be introduced and described later in this
`chapter.
`Routers communicate with one another and maintain their routing tables through the transmission of a
`variety of messages. The routing update message is one such message that generally consists of all or a
`portion of a routing table. By analyzing routing updates from all other routers, a router can build a
`detailed picture of network topology. A link-state advertisement, another example of a message sent
`between routers, informs other routers of the state of the sender’s links. Link information also can be
`used to build a complete picture of network topology to enable routers to determine optimal routes to
`network destinations.
`
`j
`
`Internetworking Technologies Handbook
`
`5-2
`
`1-58705-001-3
`
`I
`
`PETITIONERS - AMERICAN/SOUTHWEST, Exhibit 1029
`Page 2 of 10
`
`

`

`| Chapters Routing Basics
`
`Switching
`
`Routing Components M
`
`Switching algorithms is relatively simple; it is the same for most routing protocols. In most cases, a host
`determines that it must send a packet to another host. Having acquired a router’s address by some means,
`the source host sends a packet addressed specifically to
`a router’s physical (Media Access Control [MAC]-layer) address, this time with the protocol (network
`layer) address of the destination host.
`As it examines the packet’s destination protocol address, the router determines that it either knows or
`does not know how to forward the packet to the next hop. If the router does not know how to forward the
`packet, it typically drops the packet. If the router knows how to forward the packet, however, it changes
`the destination physical address to that of the next hop and transmits the packet.
`The next hop may be the ultimate destination host. If not, the next hop is usually another router, which
`executes the same switching decision process. As the packet moves through the internetwork, its
`physical address changes, but its protocol address remains constant, as illustrated in Figure 5-2.
`The preceding discussion describes switching between a source and a destination end system. The
`International Organization for Standardization (ISO) has developed a hierarchical terminology that is
`useful in describing this process. Using this terminology, network devices without the capability to
`forward packets between subnetworks are called end systems (ESs), whereas network devices with these
`capabilities are called intermediate systems (ISs). ISs are further divided into those that can
`communicate within routing domains (intradomain ISs) and those that communicate both within and
`between routing domains (interdomain ISs). A routing domain generally is considered a portion of an
`internetwork under common administrative authority that is regulated by a particular set of
`administrative guidelines. Routing domains are also called autonomous systems. With certain protocols,
`routing domains can be divided into routing areas, but intradomain routing protocols are still used for
`switching both within and between areas.
`
`I 1-58705-001-3
`
`Internetworking Technologies Handbook
`
`j
`
`5-3
`
`PETITIONERS - AMERICAN/SOUTHWEST, Exhibit 1029
`Page 3 of 10
`
`

`

`H
`
`Routing Algorithms
`
`Chapters Routing Basics
`
`|
`
`Figure 5-2 Numerous Routers May Come into Play During the Switching Process
`Source host
`PC
`
`Packet
`
`To: Destination host (Protocol address)
`Router 1
`(Physical address)
`
`Router 1 |
`
`Packet
`
`To: Destination host (Protocol address)
`Router 2
`(Physical address)
`
`Router 2
`
`Router 3
`
`To: Destination host (Protocol address)
`Router 3
`(Physical address)
`
`Packet
`
`To: Destination host
`Destination host
`
`(Protocol address)
`(Physical address)
`
`Destination host
`PC
`
`Packet
`
`Routing Algorithms
`Routing algorithms can be differentiated based on several key characteristics. First, the particular goals
`of the algorithm designer affect the operation of the resulting routing protocol. Second, various types of
`routing algorithms exist, and each algorithm has a different impact on network and router resources.
`Finally, routing algorithms use a variety of metrics that affect calculation of optimal routes. The
`following sections analyze these routing algorithm attributes.
`
`Design Goals
`
`Routing algorithms often have one or more of the following design goals:
`(cid:127) Optimality
`(cid:127) Simplicity and low overhead
`(cid:127) Robustness and stability
`(cid:127) Rapid convergence
`(cid:127) Flexibility
`
`Internetworking Technologies Handbook
`
`5-4
`
`1-58705-001-3
`
`I
`
`PETITIONERS - AMERICAN/SOUTHWEST, Exhibit 1029
`Page 4 of 10
`
`

`

`| Chapters Routing Basics
`
`Routing Algorithms M
`
`Optimality refers to the capability of the routing algorithm to select the best route, which depends on the
`metrics and metric weightings used to make the calculation. For example, one routing algorithm may use
`a number of hops and delays, but it may weigh delay more heavily in the calculation. Naturally, routing
`protocols must define their metric calculation algorithms strictly.
`Routing algorithms also are designed to be as simple as possible. In other words, the routing algorithm
`must offer its functionality efficiently, with a minimum of software and utilization overhead. Efficiency
`is particularly important when the software implementing the routing algorithm must run on a computer
`with limited physical resources.
`Routing algorithms must be robust, which means that they should perform correctly in
`the face of unusual or unforeseen circumstances, such as hardware failures, high load conditions, and
`incorrect implementations. Because routers are located at network junction points, they can cause
`considerable problems when they fail. The best routing algorithms are often those that have withstood
`the test of time and that have proven stable under a variety of network conditions.
`In addition, routing algorithms must converge rapidly. Convergence is the process of agreement, by all
`routers, on optimal routes. When a network event causes routes to either go down or become available,
`routers distribute routing update messages that permeate networks, stimulating recalculation of optimal
`routes and eventually causing all routers to agree on these routes. Routing algorithms that converge
`slowly can cause routing loops or network outages.
`In the routing loop displayed in Figure 5-3, a packet arrives at Router 1 at time tl. Router 1 already has
`been updated and thus knows that the optimal route to the destination calls for Router 2 to be the next
`stop. Router 1 therefore forwards the packet to Router 2, but because this router has not yet been updated,
`it believes that the optimal next hop is Router 1. Router 2 therefore forwards the packet back to Router
`1, and the packet continues to bounce back and forth between the two routers until Router 2 receives its
`routing update or until the packet has been switched the maximum number of times allowed.
`
`Figure 5-3 Slow Convergence and Routing Loops Can Hinder Progress
`
`To reach network:
`
`Send to:
`
`27
`
`57
`
`17
`
`24
`
`52
`
`16
`
`26
`
`Node A
`
`Node B
`
`Node C
`
`Node A
`
`Node A
`
`Node B
`
`Node A
`
`Routing algorithms should also be flexible, which means that they should quickly and accurately adapt
`to a variety of network circumstances. Assume, for example, that a network segment has gone down. As
`many routing algorithms become aware of the problem, they will quickly select the next-best path for all
`routes normally using that segment. Routing algorithms can be programmed to adapt to changes in
`network bandwidth, router queue size, and network delay, among other variables.
`
`I 1-58705-001-3
`
`Internetworking Technologies Handbook
`
`5-5
`
`PETITIONERS - AMERICAN/SOUTHWEST, Exhibit 1029
`Page 5 of 10
`
`

`

`M Routing Algorithms
`
`Chapters Routing Basics
`
`|
`
`Algorithm Types
`Routing algorithms can be classified by type. Key differentiators include these:
`(cid:127) Static versus dynamic
`(cid:127) Single-path versus multipath
`(cid:127) Flat versus hierarchical
`(cid:127) Host-intelligent versus router-intelligent
`(cid:127)
`Intradomain versus interdomain
`(cid:127) Link-state versus distance vector
`
`Static Versus Dynamic
`
`Static routing algorithms are hardly algorithms at all, but are table mappings established by the network
`administrator before the beginning of routing. These mappings do not change unless the network
`administrator alters them. Algorithms that use static routes are simple to design and work well in
`environments where network traffic is relatively predictable and where network design is relatively
`simple.
`Because static routing systems cannot react to network changes, they generally are considered unsuitable
`for today’s large, constantly changing networks. Most of the dominant routing algorithms 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 routes and sends out new routing update messages. These messages permeate the
`network, stimulating routers to rerun their algorithms and change their routing tables accordingly.
`Dynamic routing algorithms can be supplemented with static routes where appropriate. A router of last
`resort (a router to which all unroutable packets are sent), for example, can be designated to act as a
`repository for all unroutable packets, ensuring that all messages are at least handled in some way.
`
`Single-Path Versus Multipath
`
`Some sophisticated routing protocols support multiple paths to the same destination. Unlike single-path
`algorithms, these multipath algorithms permit traffic multiplexing over multiple lines. The advantages
`of multipath algorithms are obvious: They can provide substantially better throughput and reliability.
`This is generally called load sharing.
`
`Flat Versus Hierarchical
`
`Some routing algorithms operate in a flat space, while others use routing hierarchies. In aflat routing
`system, the routers are peers of all others. In a hierarchical routing system, some routers form what
`amounts to a routing backbone. Packets from nonbackbone routers travel to the backbone routers, where
`they are sent through the backbone until they reach the general area of the destination. At this point, they
`travel from the last backbone router through one or more nonbackbone routers to the final destination.
`Routing systems often designate logical groups of nodes, called domains, autonomous systems, or areas.
`In hierarchical systems, some routers in a domain can communicate with routers in other domains, while
`others can communicate only with routers within their domain. In very large networks, additional
`hierarchical levels may exist, with routers at the highest hierarchical level forming the routing backbone.
`
`j
`
`Internetworking Technologies Handbook
`
`5-6
`
`1-58705-001-3
`
`I
`
`PETITIONERS - AMERICAN/SOUTHWEST, Exhibit 1029
`Page 6 of 10
`
`

`

`| Chapters Routing Basics
`
`Routing Algorithms M
`
`The primary advantage of hierarchical routing is that it mimics the organization of most companies and
`therefore supports their traffic patterns well. Most network communication occurs within small company
`groups (domains). Because intradomain routers need to know only about other routers within their
`domain, their routing algorithms can be simplified, and, depending on the routing algorithm being used,
`routing update traffic can be reduced accordingly.
`
`Host-Intelligent Versus Router-Intelligent
`
`Some routing algorithms assume that the source end node will determine the entire route. This is usually
`referred to as source routing. In source-routing systems, routers merely act as store-and-forward devices,
`mindlessly sending the packet to the next stop.
`Other algorithms assume that hosts know nothing about routes. In these algorithms, routers determine
`the path through the internetwork based on their own calculations. In the first system, the hosts have the
`routing intelligence. In the latter system, routers have the routing intelligence.
`
`Intradomain Versus Interdomain
`
`Some routing algorithms work only within domains; others work within and between domains. The
`nature of these two algorithm types is different. It stands to reason, therefore, that an optimal
`intradomain-routing algorithm would not necessarily be an optimal interdomain-routing algorithm.
`
`Link-State Versus Distance Vector
`
`Link-state algorithms (also known as shortest path first algorithms) flood routing information to all
`nodes in the internetwork. Each router, however, sends only the portion of the routing table that describes
`the state of its own links. In link-state algorithms, each router builds a picture of the entire network in
`its routing tables. Distance vector algorithms (also known as Bellman-Ford algorithms) call for each
`router to send all or some portion of its routing table, but only to its neighbors. In essence, link-state
`algorithms send small updates everywhere, while distance vector algorithms send larger updates only to
`neighboring routers. Distance vector algorithms know only about their neighbors.
`Because they converge more quickly, link-state algorithms are somewhat less prone to routing loops than
`distance vector algorithms. On the other hand, link-state algorithms require more CPU power and
`memory than distance vector algorithms. Link-state algorithms, therefore, can be more expensive to
`implement and support. Link-state protocols are generally more scalable than distance vector protocols.
`
`Routing Metrics
`
`Routing tables contain information used by switching software to select the best route. But how,
`specifically, are routing tables built? What is the specific nature of the information that they contain?
`How do routing algorithms determine that one route is preferable to others?
`Routing algorithms have used many different metrics to determine the best route. Sophisticated routing
`algorithms can base route selection on multiple metrics, combining them in a single (hybrid) metric. All
`the following metrics have been used:
`(cid:127) Path length
`(cid:127) Reliability
`(cid:127) Delay
`(cid:127) Bandwidth
`
`I 1-58705-001-3
`
`Internetworking Technologies Handbook
`
`5-7
`
`PETITIONERS - AMERICAN/SOUTHWEST, Exhibit 1029
`Page 7 of 10
`
`

`

`_____________________________________________________________________________________________________________________Chapters Routing Basics
`■
`Network Protocols
`
`|
`
`(cid:127) Load
`(cid:127) Communication cost
`Path length is the most common routing metric. Some routing protocols allow network administrators to
`assign arbitrary costs to each network link. In this case, path length is the sum of the costs associated
`with each link traversed. Other routing protocols define hop count, a metric that specifies the number of
`passes through internetworking products, such as routers, that a packet must take en route from a source
`to a destination.
`Reliability, in the context of routing algorithms, refers to the dependability (usually described in terms
`of the bit-error rate) of each network link. Some network links might go down more often than others.
`After a network fails, certain network links might be repaired more easily or more quickly than other
`links. Any reliability factors can be taken into account in the assignment of the reliability ratings, which
`are arbitrary numeric values usually assigned to network links by network administrators.
`Routing delay refers to the length of time required to move a packet from source to destination through
`the internetwork. Delay depends on many factors, including the bandwidth of intermediate network
`links, the port queues at each router along the way, network congestion on all intermediate network links,
`and the physical distance to be traveled. Because delay is a conglomeration of several important
`variables, it is a common and useful metric.
`Bandwidth refers to the available traffic capacity of a link. All other things being equal, a 10-Mbps
`Ethernet link would be preferable to a 64-kbps leased line. Although bandwidth is a rating of the
`maximum attainable throughput on a link, routes through links with greater bandwidth do not necessarily
`provide better routes than routes through slower links. For example, if a faster link is busier, the actual
`time required to send a packet to the destination could be greater.
`Load refers to the degree to which a network resource, such as a router, is busy. Load can be calculated
`in a variety of ways, including CPU utilization and packets processed per second. Monitoring these
`parameters on a continual basis can be resource-intensive itself.
`Communication cost is another important metric, especially because some companies may not care about
`performance as much as they care about operating expenditures. Although line delay may be longer, they
`will send packets over their own lines rather than through the public lines that cost money for usage time.
`
`Network Protocols
`Routed protocols are transported by routing protocols across an internetwork. In general, routed
`protocols in this context also are referred to as network protocols. These network protocols perform a
`variety of functions required for communication between user applications in source and destination
`devices, and these functions can differ widely among protocol suites. Network protocols occur at the
`upper five layers of the OSI reference model: the network layer, the transport layer, the session layer, the
`presentation layer, and the application layer.
`Confusion about the terms routed protocol and routing protocol is common. Routed protocols are
`protocols that are routed over an internetwork. Examples of such protocols are the Internet Protocol (IP),
`DECnet, AppleTalk, Novell NetWare, OSI, Banyan VINES, and Xerox Network System (XNS). Routing
`protocols, on the other hand, are protocols that implement routing algorithms. Put simply, routing
`protocols are used by intermediate systems to build tables used in determining path selection of routed
`protocols. Examples of these protocols include Interior Gateway Routing Protocol (IGRP), Enhanced
`Interior Gateway Routing Protocol (Enhanced IGRP), Open Shortest Path First (OSPF), Exterior
`Gateway Protocol (EGP), Border Gateway Protocol (BGP), Intermediate System-to-Intermediate
`System (IS-IS), and Routing Information Protocol (RIP). Routed and routing protocols are discussed in
`detail later in this book.
`
`j
`
`Internetworking Technologies Handbook
`
`5-8
`
`1-58705-001-3
`
`I
`
`PETITIONERS - AMERICAN/SOUTHWEST, Exhibit 1029
`Page 8 of 10
`
`

`

`| Chapters Routing Basics
`
`Review Questions M
`
`Review Questions
`Q—Describe the process of routing packets.
`A— Routing is the act of moving information across an internetwork from a source to a destination.
`Q—What are some routing algorithm types?
`A— Static, dynamic, flat, hierarchical, host-intelligent, router-intelligent, intradomain, interdomain,
`link-state, and distance vector.
`Q—Describe the difference between static and dynamic routing.
`A— Static routing is configured by the network administrator and is not capable of adjusting to changes
`in the network without network administrator intervention. Dynamic routing adjusts to changing
`network circumstances by analyzing incoming routing update messages without administrator
`intervention.
`Q—What are some of the metrics used by routing protocols?
`A— Path length, reliability, delay, bandwidth, load, and communication cost.
`
`I 1-58705-001-3
`
`Internetworking Technologies Handbook
`
`5-9
`
`PETITIONERS - AMERICAN/SOUTHWEST, Exhibit 1029
`Page 9 of 10
`
`

`

`M Review Questions
`
`Chapters Routing Basics
`
`|
`
`j
`
`Internetworking Technologies Handbook
`
`5-10
`
`1-58705-001-3
`
`I
`
`PETITIONERS - AMERICAN/SOUTHWEST, Exhibit 1029
`Page 10 of 10
`
`