Routing

C H A PT ER

5

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 roles of routed or network protocols. Subsequent chapters in Part 6, "Routing Protocols," of this book address specific routingprotocols in more detail, while the network protocols that use routing protocols are discussed in Part 5, "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 thesame 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 indifferent 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 fairly simple, homogeneous environments. Only relatively recently has large-scale internetworking become popular.

Routing Components
Routinginvolves 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 switching. Although switching is relatively straightforward, path determination can be very complex.

Path Determination
A metric is a standard of measurement, such aspath length, 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 Basics 5-1

Routing Components

Routing algorithms fill routing tables with a variety ofinformation. Destination/next hop associations tell a router that a particular destination can be gained 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/nexthop routing table.
Figure 5-1 Destination/next hop associations determine the data’s optimal path.
Send to: Node A Node B Node C Node A Node A Node B Node A . . .

To reach network: 27 57 17 24 52 16 26 . . .

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 differdepending 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 fromall 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 topology to enable routers to determine optimal routes to network destinations.

Switching
Switching algorithms are...