Routing Algorithms

Routing Algorithms

Up to now in this section, we've mostly looked at the network layer's forwarding function. We studied that when a packet arrives to a router, the router indexes a forwarding table and determines the link interface to which the packet is to be directed. We also studied that routing algorithms, operating in network routers, exchange and compute the information that is used to configure these forwarding tables. The interplay between routing algorithms and forwarding tables was shown in "The Network Layer" Figure 2. Having explored forwarding in some depth we now turn our attention to the other main topic of this section, namely, the network layer's critical routing function. Whether the network layer provides a datagram service (in which case different packets between a given source-destination pair may take different routes) or a VC service (in which case all packets between a given source and destination will take the same path), the network layer must nonetheless determine the path that packets take from senders to receivers. We'll see that the job of routing is to determine good paths (equivalently, routes), from senders to receivers, through the network of routers.

Normally a host is attached directly to one router, the default router for the host (also called the first-hop router for the host). Whenever a host sends a packet, the packet is transferred to its default router. We refer to the default router of the source host as the source router and the default router of the destination host as the destination router. The problem of routing a packet from source host to destination host clearly boils down to the problem of routing the packet from source router to destination router, which is the focus of this section.

The purpose of a routing algorithm is then simple: given a set of routers, with links connecting the routers, a routing algorithm finds a "good" path from source router to destination router. Normally, a good path is one that has the least cost. We'll see, however, that in practice, real-world concerns such as policy issues (for instance, a rule such as "router x, belonging to organization Y, should not forward any packets originating from the network owned by organization Z") also come into play to complicate the conceptually simple and elegant algorithms whose theory underlies the practice of routing in today's networks.

A graph is used to formulate routing problems. Remember that a graph G = (N,E) is a set N of nodes and a collection E of edges, where each edge is a pair of nodes from N. In the context of network-layer routing, the nodes in the graph represent routers - the points at which packet-forwarding decisions are made - and the edges connecting these nodes represent the physical links between these routers. Such a graph abstraction of a computer network is shown in Figure 1. To view some graphs representing real network maps, see [Dodge 2007, Cheswick 2000]; for a discussion of how well different graph-based models model the Internet, see [Zegura 1997, Faloutsos 1999, Li 2004].

As illustrated in Figure 1, an edge also has a value representing its cost. Normally, an edge's cost may reflect the physical length of the corresponding link (for instance, a transoceanic link might have a higher cost than a short-haul terrestrial link), the link speed, or the monetary cost associated with a link. For our purposes, we'll simply take the edge costs as a given and won't worry about how they are determined. For any edge (x,y) in E, we denote c(x,y) as the cost of the edge between nodes x and y. If the pair (x,y) does not belong to E, we set c(x,y) = ∞. Also, throughout we consider only undirected graphs (i.e., graphs whose edges do not have a direction), so that edge (x,y) is the same as edge (y,x) and that c(x,y) = c(y,x). Also, a node y is said to be a neighbor of node x if (x,y) belongs to E.

Given that costs are assigned to the various edges in the graph abstraction, a natural goal of a routing algorithm is to identify the least costly paths between sources and destinations. To make this problem more precise, remember that a path in a graph G = (N,E) is a sequence of nodes (x1, x2,..., xp) such that each of the pairs (x1,x2), (x2,x3),...,(xp-1,xp) are edges in E. The cost of a path (x1,x2,...,xp) is simply the sum of all the edge costs along the path, that is, c(x1,x2) + c(x2,x3) +...+ c(xp-1,xp). Given any two nodes x and y, there are usually many paths between the two nodes, with each path having a cost. One or more of these paths is a least-cost path. The least-cost problem is therefore clear: Find a path between the source and destination that has least cost. In Figure 1, for instance, the least-cost path between source node u and destination node w is (u, x, y, w) with a path cost of 3. Note that if all edges in thegraph have the same cost, the least-cost path is also the shortest path (that is, the path with the smallest number of links between the source and the destination).

Abstract graph model of a computer network

As a simple exercise, try finding the least-cost path from node u to z in Figure 1 and reflect for a moment on how you calculated that path. If you are like most people, you found the path from u to z by examining Figure 1, tracing a few routes from u to z, and somehow convincing yourself that the path you had chosen had the least cost among all possible paths. (Did you check all of the 17 possible paths between u and z? Probably not!) Such a calculation is an example of a centralized routing algorithm - the routing algorithm was run in one location, your brain, with complete information about the network. Generally, one way in which we can classify routing algorithms is according to whether they are global or decentralized.

●  A global routing algorithm computes the least-cost path between a source and destination using complete, global knowledge about the network. That is, the algorithm takes the connectivity between all nodes and all link costs as inputs. This then requires that the algorithm somehow obtain this information before actually performing the calculation. The calculation itself can be run at one site (a centralized global routing algorithm) or replicated at multiple sites. The key distinguishing feature here, however, is that a global algorithm has complete information about connectivity and link costs. In practice, algorithms with global state information are often referred to as link-state (LS) algorithms, since the algorithm must be aware of the cost of each link in the network. We'll study LS algorithms in "The Link-State (LS) Routing Algorithm".

●  In a decentralized routing algorithm, the calculation of the least-cost path is performed in an iterative, distributed manner. No node has complete information about the costs of all network links. Instead, each node begins with only the knowledge of the costs of its own directly attached links. Then, through an iterative process of calculation and exchange of information with its neighboring nodes (that is, nodes that are at the other end of links to which it itself is attached), a node gradually calculates the least-cost path to a destination or set of destinations. The decentralized routing algorithm we'll study below in "The Distance-Vector (DV) Routing Algorithm" is called a distance-vector (DV) algorithm, because each node maintains a vector of estimates of the costs (distances) to all other nodes in the network.

A second broad way to classify routing algorithms is according to whether they are static or dynamic. In static routing algorithms, routes change very slowly over time, often as a result of human intervention (for instance, a human manually editing a router's forwarding table). Dynamic routing algorithms change the routing paths as the network traffic loads or topology change. A dynamic algorithm can be run either periodically or in direct response to topology or link cost changes. While dynamic algorithms are more responsive to network changes, they are also more susceptible to problems such as routing loops and oscillation in routes.

A third way to classify routing algorithms is according to whether they are load-sensitive or load-insensitive. In a load-sensitive algorithm, link costs very dynamically to reflect the current level of congestion in the underlying link. If a high cost is associated with a link that is currently congested, a routing algorithm will tend to choose routes around such a congested link. While early ARPAnet routing algorithms were load-sensitive [McQuillan 1980], a number of difficulties were encountered [Huitema 1998]. Today's Internet routing algorithms (such as RIP, OSPF and BGP) are load-insensitive, as a link's cost does not clearly reflect its current (or recent past) level of congestion.


forwarding tables, network layer, source router, destination router, routing algorithm

Copy Right

The contents available on this website are copyrighted by TechPlus unless otherwise indicated. All rights are reserved by TechPlus, and content may not be reproduced, published, or transferred in any form or by any means, except with the prior written permission of TechPlus.