ROUTING

ROUTING

One of the most complex and crucial aspects of packet-switching network design is

routing. This section begins with a survey of key characteristics that can be used to

classify routing strategies. Then, some specific routing strategies are discussed.

The principles described in this section are also applicable to internetwork

routing, discussed in Part IV.

Characteristics

The primary function of a packet-switching network is to accept packets from a

source station and deliver them to a destination station. To accomplish this, a path

or route through the network must be determined: generally, more than one route

is possible. Thus, a routing function must be performed. The requirements for this

function include

Correctness

Simplicity

Robustness

Stability

Fairness

Optimality

Efficiency

The first two items on the list are self-explanatory. Robustness has to do with

the ability of the network to deliver packets via some route in the face of localized

failures and overloads. Ideally, the network can react to such contingencies without

the loss of packets or the breaking of virtual circuits. The designer who seeks

robustness must cope with the competing requirement for stability. Techniques that

react to changing conditions have an unfortunate tendency to either react too slowly

to events or to experience unstable swings from one extreme to another. For example,

the network may react to congestion in one area by shifting most of the load to

a second area. Now the second area is overloaded and the first is underutilized,

causing a second shift. During these shifts, packets may travel in loops through the

network.

A tradeoff also exists between fairness and optimality. Some performance criteria

may give higher priority to the exchange of packets between nearby stations

compared to an exchange between distant stations. This policy may maximize average

throughput but will appear unfair to the station that primarily needs to communicate

with distant stations.

Finally, any routing technique involves some processing overhead at each

node and often a transmission overhead as well, both of which impair network efficiency.

The penalty of such overhead needs to be less than the benefit accrued

based on some reasonable metric, such as increased robustness or fairness.

With these requirements in mind, we are in a position to assess the various

design elements that contribute to a routing strategy. Table 9.2 lists these elements.

Some of these categories overlap or are dependent on one another. Nevertheless,

an examination of this list serves to clarify and organize routing concepts.

Performance Criteria

The selection of a route is generally based on some performance criterion. The simplest

criterion is to choose the minimum-hop route (one that passes through the

least number of nodes) through the network; this is an easily measured criterion and

should minimize the consumption of network resources. A generalization of the

minimum-hop criterion is least-cost routing. In this case, a cost is associated with

each link, and, for any pair of attached stations, the route through the network

that accumulates the least cost is sought. For example, Figure 9.5 illustrates a net

work in which the two arrowed lines between a pair of nodes represent a link

between this nodes, and the corresponding numbers represent the current link cost

in each direction. The shortest path (fewest hops) from node 1 to node 6 is 1-3-6

(cost = 5 + 5 = l0), but the least-cost path is 1-4-5-6 (cost = 1 + 1 + 2 = 4). Costs

are assigned to links to support one or more design objectives. For example, the cost

could be inversely related to the data rate (i.e., the higher the data rate on a link,

the lower the assigned cost of the link) or the current queuing delay on the link. In

the first case, the least-cost route should provide the highest throughput. In the second

case, the least-cost route should minimize delay.

In either the minimum-hop or least-cost approach, the algorithm for determining

the optimum route for any pair of stations is relatively straightforward, and

the processing time would be about the same for either computation. Because the

least-cost criterion is more flexible, it is more common than the minimum-hop

criterion.

Several least-cost routing algorithms are in common use.

Decision Time and Place

Routing decisions are made on the basis of some performance criterion. Two key

characteristics of the decision are the time and place that the decision is made.

Decision time is determined by whether the routing decision is made on a

packet or virtual-circuit basis. When the internal operation of the network is

datagram, a routing decision is made individually for each packet. For internal virtual-

circuit operation, a routing decision is made at the time the virtual circuit is

established. In the simplest case, all subsequent packets using that virtual circuit

follow the same route. In more sophisticated network designs, the network may

dynamically change the route assigned to a particular virtual circuit in response to

changing conditions (e.g., overload or failure of a portion of the network).

The term decision place refers to which node or nodes in the network are

responsible for the routing decision. Most common is distributed routing, in which

each node has the responsibility of selecting an output link for routing packets as

they arrive. For centralized routing, the decision is made by some designated node,

such as a network control center. The danger of this latter approach is that the loss

of the network control center may block operation of the network. The distributed

approach is perhaps more complex, but is also more robust. A third alternative,

used in some networks, is source routing. In this case, the routing decision is actually

made by the source station rather than by a network node, and is then communicated

to the network; this allows the user to dictate a route through the network

that meets criteria local to that user.

The decision time and decision place are independent design variables. For

example, in Figure 9.5, suppose that the decision place is each node and that the values

depicted are the costs at a given instant in time; the costs, though, may change.

If a packet is to be delivered from node 1 to node 6, it might follow the route

1-4-5-6, with each leg of the route determined locally by the transmitting node. Now

let the values change such that 1-4-5-6 is no longer the optimum route. In a datagram

network, the next packet may follow a different route, again determined by

each node along the way, In a virtual-circuit network, each node will remember the

routing decision that was made when the virtual circuit was established, and will

simply pass on the packets without making a new decision.

Network Information Source and Update Timing

Most routing strategies require that decisions be based on knowledge of the topology

of the network, traffic load, and link cost. Surprisingly, some strategies use no

such information and yet manage to get packets through; flooding and some random

strategies (discussed below) are in this category.

With distributed routing, in which the routing decision is made by each

node, the individual node may make use of only local information, such as the cost

of each outgoing link. Each node might also collect information from adjacent

(directly connected) nodes, such as the amount of congestion experienced at that

node. Finally, there are algorithms in common use that allow the node to gain information

from all nodes on any potential route of interest. In the case of centralized

routing, the central node typically makes use of information obtained from all

nodes.

A related concept is that of information update timing, which is a function of

both the information source and the routing strategy. Clearly, if no information is

used (as in flooding), there is no information to update. If only local information is

used, the update is essentially continuous-that is, an individual node always knows

its local conditions. For all other information source categories (adjacent nodes, all

nodes), update timing depends on the routing strategy. For a fixed strategy, the

information is never updated. For an adaptive strategy, information is updated from

time to time to enable the routing decision to adapt to changing conditions.

As you might expect, the more information available, and the more frequently

it is updated, the more likely the network is to make good routing decisions. On the

other hand, the transmission of that information consumes network resources.

Routing Strategies

A large number of routing strategies have evolved for dealing with the routing

requirements of packet-switching networks; many having these strategies are also

applied to internetwork routing, which we cover in Part IV. In this section, we survey

four key strategies: fixed, flooding, random, and adaptive.

Fixed Routing

For fixed routing, a ro te is selected for each source-destination pair of nodes in the

network. Either of the least-cost routing algorithms described in Lesson 9A

could be used. The routes are fixed, with the exception that they might change if

there is movement in the topology of the network. Thus, the link costs used in

designing routes cannot be based on any dynamic variable such as traffic. They

could, however, be based on expected traffic or capacity.

Figure 9.6 suggests how fixed routing might be implemented. A central routing

matrix is created, to be stored perhaps at a network control center. The matrix

shows, for each source-destination pair of nodes, the identity of the next node on

the route.

Note that it is not necessary to store the complete route for each possible pair

of nodes. Rather, it is sufficient to know, for each pair of nodes, the identity of the

first node on the route; to see this, suppose that the least-cost route from X to Y

begins with the X-A link. Call the remainder of the route R1; this is the part from A

to Y. Define R2 as the least-cost route from A to Y. Now, if the cost of R1 is greater

than that of R2, then the X-Y route can be improved by using R2 instead. If the cost

of RI is less than R2, then R2 is not the least-cost route from A to Y. Therefore,

R1 = R2. Thus, at each point along a route, it is only necessary to know the identity

of the next node, not the entire route. In our example, the route from node 1 to

node 6 begins by going through node 4. Again, consulting the matrix, the route from

node 4 to node 6 goes through node 5. Finally, the route from node 5 to node 6 is a

direct link to node 6. The complete route, then, from node 1 to node 6 is 1-4-5-6.

From this overall matrix, routing tables can be developed and stored at each

node. From the reasoning in the preceding paragraph, it follows that each node

need only store a single column of the routing directory. The node's directory shows

the next node to take for each destination.

With fixed routing, there is no difference between routing for datagrams and

virtual circuits. All packets from a given source to a given destination follow the

same route. The advantage of fixed routing is its simplicity, and it should work well

in a reliable network with a stable load. Its disadvantage is its lack of flexibility; it

does not react to network congestion or failures.

A refinement to fixed routing that would accommodate link and node outages

would be to supply the nodes with an alternate next node for each destination. For

example, the alternate next nodes in the node 1 directory might be 4,3,2,3,3.

Flooding

Another simple routing technique is flooding. This technique requires no network

information whatsoever, and works as follows. A packet is sent by a source node to

every one of its neighbors. At each node, an incoming packet is retransmitted on all

outgoing links except for the link on which it arrived. For example, if node 1 in Figure

9.5 has a packet to send to node 6, it sends a copy of that packet (with a destination

address of 6), to nodes 2,3, and 4. Node 2 will send a copy to nodes 3 and 4.

Node 4 will send a copy to nodes 2,3, and 5. And so it goes. Eventually, a number

of copies of the packet will arrive at node 6. The packet must have some unique

identifier (e.g., source node and sequence number, or virtual-circuit number and

sequence number) so that node 6 knows to discard all but the first copy.

Unless something is done to stop the incessant retransmission of packets, the

number of packets in circulation just from a single source packet grows without

bound; one way to prevent this is for each node to remember the identity of those

packets it has already retransmitted. When duplicate copies of the packet arrive,

they are discarded. A simpler technique is to include a hop count field with each

packet. The count can originally be set to some maximum value, such as the diameter

(length of the longest minimum-hop path through the network) of the network.

Each time a node passes on a packet, it decrements the count by one. When the

count reaches zero, the packet is discarded.

An example of the latter tactic is shown in Figure 9.7. A packet is to be sent

from node 1 to node 6 and is assigned a hop count of 3. On the first hop, three copies

of the packet are created. For the second hop of all these copies, a total of nine

copies are created. One of these copies reaches node 6, which recognizes that it is

the intended destination and does not retransmit. However, the other nodes generate

a total of 22 new copies for their third and final hop. Note that if a node is not

keeping track of the packet identifier, it may generate multiple copies at this third

stage. All packets received from the third hop are discarded. In all, node 6 has

received four additional copies of the packet.

The flooding technique has three remarkable properties:

All possible routes between source and destination are tried. Thus, no matter

what link or node outages have occurred, a packet will always get through if

at least one path between source and destination exists.

Because all routes are tried, at least one copy of the packet to arrive at the

destination will have used a minimum-hop route.

a All nodes that are directly or indirectly connected to the source node are

visited.

Because of the first property, the flooding technique is highly robust and could

be used to send emergency messages. An example application is a military network

that is subject to extensive damage. Because of the second property, flooding

might be used to initially set up the route for a virtual circuit. The third property

suggests that flooding can be useful for the dissemination of important information

to all nodes; we will see that it is used in some schemes to disseminate routing

information.

The principal disadvantage of flooding is the high traffic load that it generates,

which is directly proportional to the connectivity of the network.

Random Routing

Random routing has the simplicity and robustness of flooding with far less traffic

load. With random routing, a node selects only one outgoing path for retransmission

of an incoming packet. The outgoing link is chosen at random, excluding the

link on which the packet arrived. If all links are equally likely to be chosen, then a

node may simply utilize outgoing links in a round-robin fashion.

A refinement of this technique is to assign a probability to each outgoing link

and to select the link based on that probability. The probability could be based on

data rate, in which case we have

The sum is taken over all candidate outgoing links. This scheme should provide

good traffic distribution. Note that the probabilities could also be based on

fixed link costs.

Like flooding, random routing requires the use of no network information.

Because the route taken is random, the actual route will typically not be the leastcost

route nor the minimum-hop route. Thus, the network must carry a higher than

optimum traffic load, although not nearly as high as for flooding.

Adaptive Routing

In virtually all packet-switching networks, some sort of adaptive routing technique

is used. That is, the routing decisions that are made change as conditions on the network

change. The principle conditions that influence routing decisions are

* Failure. When a node or trunk fails, it can no longer be used as part of a route.

* Congestion. When a particular portion of the network is heavily congested

it is desirable to route packets around, rather than through, the area of

congestion.

For adaptive routing to be possible, information about the state of the network

must be exchanged among the nodes. There is a tradeoff here between the

quality of the information and the amount of overhead. The more information that

is exchanged, and the more frequently it is exchanged, the better will be the routing

decisions that each node makes. On the other hand, this information is itself a load

on the network, causing a performance degradation.

There are several drawbacks associated with the use of adaptive routing:

The routing decision is more complex; therefore, the processing burden on

network nodes increases.

In most cases, adaptive strategies depend on status information that is collected

at one place but used at another; therefore, the traffic burden on the

network increases.

An adaptive strategy may react too quickly, causing congestion-producing

oscillation; if it reacts too slowly, the strategy will be irrelevant.

Despite these real dangers, adaptive routing strategies are by far the most

prevalent, for two reasons:

An adaptive routing strategy can improve performance, as seen by the network

user.

An adaptive routing strategy can aid in congestion control, as discussed later.

These benefits may or may not be realized, depending on the soundness of the

design and the nature of the load. By and large, it is an extraordinarily complex task

to perform properly. As demonstration of this, most major packet-switching networks,

such as ARPANET and its successors, TYMNET, and those developed by

IBM and DEC, have endured at least one major overhaul of their routing strategy.

A convenient way to classify adaptive routing strategies is on the basis of

information source: local, adjacent nodes, all nodes. An example of an adaptive

routing strategy that relies only on local information is one in which a node routes

each packet to the outgoing link with the shortest queue length, Q. This would have

the effect of balancing the load on outgoing links. However, some outgoing links

may not be headed in the correct general direction. We can improve matters by also

taking into account preferred direction, much as with random routing. In this case,

each link emanating from the node would have a bias B,, for each destination i. For

each incoming packet headed for node i, the node would choose the outgoing link

that minimizes Q + B,. Thus, a node would tend to send packets in the right direction,

with a concession made to current traffic delays.

As an example, Figure 9.8 shows the status of node 4 of Figure 9.5 at a certain

point in time. Node 4 has links to four other nodes. A fair number of packets have

been arriving and a backlog has built up, with a queue of packets waiting for each

of the outgoing links. A packet arrives from node 1 destined for node 6. To which

outgoing link should the packet be routed? Based on current queue lengths and the

Bellman-Ford algorithm .For this algorithm, each node maintains

two vectors:

Figure 9.9 provides an example of the original ARPANET algorithm, using

the network of Figure 9.10. This is the same network as that of Figure 9.5, with some

of the link costs having different values (and assuming the same cost in both directions).

Figure 9.9a shows the routing table for node 1 at an instant in time that

reflects the link costs of Figure 9.10. For each destination, a delay is specified, as

well as the next node on the route that produces that delay. At some point, the link

costs change to those of Figure 9.5. Assume that node 1's neighbors (nodes 2,3, and

4) learn of the change before node 1. Each of these nodes updates its delay vector

and sends a copy to all of its neighbors, including node 1 (Figure 9.9b). Node 1 discards

its current routing table and builds a new one, based solely on the incoming

delay vector and its own estimate of link delay to each of its neighbors. The result

is shown in Figure 9.9~.

The estimated link delay is simply the queue length for that link. Thus, in

building a new routing table, the node will tend to favor outgoing links with shorter

queues. This tends to balance the load on outgoing links. However, because queue

lengths vary rapidly with time, the distributed perception of the shortest route could

change while a packet is en route; this could lead to a thrashing situation in which

a packet continues to seek out areas of low congestion rather than aiming at the

destination.

Second Generation

After some years of experience and several minor modifications, the original routing

algorithm was replaced by a quite different one in 1979 [MCQU80]. The major

shortcomings of the old algorithm were these:

The algorithm did not consider line speed, but merely queue length. Thus,

higher-capacity links were not given the favored status they deserved.

Queue length is, in any case, an artificial measure of delay, as some variable

amount of processing time elapses between the arrival of a packet at a node

and its placement in an outbound queue.

The algorithm was not very accurate. In particular, it responded slowly to congestion

and delay increases.

The new algorithm is also a distributed adaptive one, using delay as the performance

criterion, but the differences are significant. Rather than using queue

length as a surrogate for delay, the delay is measured directly. At a node, each

incoming packet is timestamped with an arrival time. A departure time is recorded

when the packet is transmitted. If a positive acknowledgment is returned, the delay

for that packet is recorded as the departure time minus the arrival time plus transmission

time and propagation delay. The node must therefore know link data rate

and propagation time. If a negative acknowledgment comes back, the departure

time is updated and the node tries again, until a measure of successful transmission

delay is obtained.

Every 10 seconds, the node computes the average delay on each outgoing link.

If there are any significant changes in delay, the information is sent to all other

nodes using flooding. Each node maintains an estimate of delay on every network

link. When new information arrives, it recomputes its routing table using Dijkstra's

algorithm (Lesson 9A).

Third Generation

Experience with this new strategy indicated that it was more responsive and stable

than the old one. The overhead induced by flooding was moderate as each node

does this, at most, once every 10 seconds. However, as the load on the network

grew, a shortcoming in the new strategy began to appear, and the strategy was

revised in 1987 [KHAN89].

The problem with the second strategy is the assumption that the measured

packet delay on a link is a good predictor of the link delay encountered after all

nodes reroute their traffic based on this reported delay. Thus, it is an effective routing

mechanism only if there is some correlation between the reported values and

those actually experienced after rerouting. This correlation tends to be rather high

under light and moderate traffic loads. However, under heavy loads, there is little

correlation. Therefore, immediately after all nodes have made routing updates, the

routing tables are obsolete!

As an example, consider a network that consists of two regions with only two

links, A and B, connecting the two regions (Figure 9.11). Each route between two

nodes in different regions must pass through one of these links. Assume that a situation

develops in which most of the traffic is on link A. This will cause the link delay

on A to be significant, and, at the next opportunity, this delay value will be reported

to all other nodes. These updates will arrive at all nodes at about the same time, and

all will update their routing tables immediately. It is likely that this new delay value

for link A will be high enough to make link B the preferred choice for most, if not

all, interregion routes. Because all nodes adjust their routes at the same time, most

or all interregion traffic shifts at the same time to link B. Now, the link delay value

on B will become high, and there will be a subsequent shift to link A. This oscillation

will continue until the traffic volume subsides.

There are a number of reasons why this oscillation is undesirable:

1. A significant portion of available capacity is unused at just the time when it is

needed most: under heavy traffic load.

2. The overutilization of some links can lead to the spread of congestion within

the network. (This will be seen in the discussion of congestion in Section 9.3.)

3. The large swings in measured delay values result in the need for more frequent

routing update messages; this increases the load on the network at just

the time when the network is already stressed.

The ARPANET designers concluded that the essence of the problem was that

every node was trying to obtain the best route for all destinations, and that these

efforts conflicted. It was concluded that under heavy loads, the goal of routing

should be to give the average route a good path instead of attempting to give all

routes the best path.

The designers decided that it was unnecessary to change the overall routing

algorithm. Rather, it was sufficient to change the function that calculates link costs.

This was done in such a way as to damp routing oscillations and reduce routing

overhead. The calculation begins with measuring the average delay over the last

10 seconds. This value is then transformed with the following steps:

1. Using a simple single-server queuing model, the measured delay is transformed

into an estimate of link utilization. From queuing theory, utilization

can be expressed as a function of delay as follows:

In the figure, delay is normalized to the value achieved on an idle line, which

is just propagation delay plus transmission time. One curve on the figure indicates

the way in which the actual delay rises as a function of utilization; the increase in

delay is due to queuing delay at the node. For the revised algorithm, the cost value

is kept at the minimum value until a given level of utilization is reached. This feature

has the effect of reducing routing overhead at low traffic levels. Above a certain

level of utilization, the cost level is allowed to rise to a maximum value that is

equal to three times the minimum value. The effect of this maximum value is to dictate

that traffic should not be routed around a heavily utilized line by more than two

additional hops.

Note that the minimum threshold is set higher for satellite links; this encourages

the use of terrestrial links under conditions of light traffic, as the terrestrial

links have much lower propagation delay. Note also that the actual delay curve is

much steeper than the transformation curves at high utilization levels. It is this steep

rise in link cost that causes all of the traffic on a link to be shed, which in turn causes

routing oscillations.

In summary, the revised cost function is keyed to utilization rather than delay.

The function resembles a delay-based metric under light loads, as well as a capacitybased

metric under heavy loads.