Jianping Wang

Routing

Jianping Wang

April 22, 2004

1. Introduction

Routing plays an important role in data networks. Two main functions of routing algorithm are selecting paths for various origin-destination (OD) pairs and delivering messages to correct destinations.

In data networks, there are two main performance measurements that are substantially affected by routing algorithms: throughput (quantity of service) and average packet delay (quality of service). From the perspective of a network manager, maximum throughput is objective. From a user’s perspective, low delay is main concern. The effect of good routing is to increase throughput for the same average delay per packet under high offered load conditions and to decrease average delay per packet under low offered load conditions. The following figure shows a comparison on the good and poor routing algorithms.

To evaluate a routing algorithm usually is a difficult task. Once traffic enters into data networks, it will lose most important properties, such as independent and Poisson arrival process, etc, that are helpful to establish mathematical models and apply queue theory to analyze them. To simply the analysis on routing algorithms, Kleinrock independence approximation is usually assumed to be satisfied. Under this assumption, the queue on each router in the network is an M/M/1 queue and the results of M/M/1 queue can be applied to obtain the measurements such as delay and throughput. Suck kind of network is called queued network.

2. Optimal Capacity Assignment

To evaluate the performance of a routing algorithm, we need to quantify the notion of traffic congestion. Traffic congestion in a data network can be quantified in terms of the statistics of the arrival processes of the network queues. These statistics determine the distributions of queue length and packet waiting time at each link. One way is to measure congestion at a link in terms of the average traffic carried by the link.

congestion – flow Fij on link (i,j)

where Fij is the flow of link (i,j), in unit of [data units/sec]. Implicit in flow models is the assumption that the statistics of the traffic entering the network do not change over time.

delay – Dij

Dij

Fij

Cij

A typical network where such conditions hold is one accommodating a large number of users for each OD pair, with the traffic rate of each of these users being small relative to the total rate.

The cost function above (1) becomes the average number of packets in the system based on the hypothesis that each queue behaves as an M/M/1 queue of packets. Where Cij is the transmission capacity of link (i,j) measured in the same units as Fij, and dij is the processing and propagation delay. We can see from the above two equations that when a flow Fij approaches the corresponding link capacity Cij, it expresses the qualitatively the congestion sets. The first term on the right of equation (2) is the number in queue, while the second term is the number in transit, so the total equation represents the total number in the system.

Optimal Routing:

W={OD pairs} w=(i,j)

Pw= set of paths for OD pair W. Pw is subsets of all possible paths.

Constraints

Xp= flow (data units/sec) of path p, Xp ³0, for all pÎPw, wÎW. rw is the rate for OD pair. The total flow Fij of link (i,j) is the sum of all path flows traversing the link

Consider a cost function of the form

and the problem of finding the set of path flows {xp} that minimize this cost function subject to the constraints, by expressing the total flows Fij in terms of the flows in the cost function, the problem becomes to be

3. Characterization of optimal routing

We characterize an optimal routing in terms of the first derivatives D’ij of the functions Dij, Dij is differentiable function of Fij and is defined in an interval [0,Cij). Let x={xp} be the vector of path flows. Denote by D(x) the cost function of the Eq. (6), in form of Eq(8) below,

and by ¶D(x)/¶xp the partial derivative of D with respect to xp, we got

For each link (i,j) either pÎP(i,j), or pÏP(i,j).

If pÏP(i,j),

If pÎP(i,j),

The first derivatives D’ij are evaluated at the total flows corresponding to x. So ¶D(x)/¶xp is the length of path p when the length of each link (i, j) is taken to be the first derivative D’ij evaluated at x. And ¶D(x)/¶xp is called the first derivative length of path p.

Let x* ={x*p}be the set of optimal path flow vector. If we move a small amount d>0 form path p to any other path p’ of the same OD pair without improving the cost; otherwise, the optimality of x* would be violated. So, the change in cost

We can see that the optimal path flow is positive only on paths with a minimum first derivative length. Furthermore, at an optimum, the paths along which the input flow rw of OD pair w is split must have equal length.

Example(5.7):

Consider the two-link network shown below, where nodes 1 and 2 are the only origin and destination, respectively. The given input r is to be divided into the two path flows x1 and x2 so as to minimize a cost function based on the M/M/1 approximation

D(x) = D1(x1) + D2(x2)

where for i=1,2,

Ci is the capacity of link i.

Let x1* and x2* be the two optimal flow vectors. We have x1* + x2* = r (assume r <= C1 + C1). There are two possibilities:

1) x1*=r and x2*=0. According to the shortest path condition (13), we have

we can get r£C1-ÖC1C2

2) x1*>0 and x2*>0. We have

Since x1* + x2* = r, the solution is

x1* x2*

x1*

x2*

C1-ÖC1C2 C1+C2 r

It can be seen that for r£ C1-ÖC1C2, the faster link 1 is used exclusively. When r exceeds the threshold value C1-ÖC1C2, for which the first derivative lengths of the two links are equalized, the slower link 2 is also utilized.

4. Feasible direction methods for optimal routing

It was shown that optimal routing results only if flow travels along MFDL (Minimum First Derivation Length) paths for each OD pair. But, shift all flow of each OD pair to the shortest path, with oscillatory behavior resulting. It is more appropriate to shift only part of the flow of other paths to the shortest path.

feasible directions

Dx at feasible point x

Constraint set x

the directions (Dx) are descent direction where cost goes down .

for feasibility

we have

Since the gradient vector ÑD(x) is normal to the equal cost surfaces of the cost function D, it is shown in the below fig. that the descent condition translates to the condition that the inner product of ÑD(x) and Dx is negative, so

Gradient at x x

Surfaces of equal cost D(x)

Frank-wolfe Method

Given a feasible path flow vector x={xp}, find the MFDL path for each OD pair.

And the process is repeated. This algorithm is called the flow deviation method. A proportion a* of the flow of all the nonshortest paths is shifted to the shortest path for each OD pair w. The characteristic property here is that flow is shifted from the nonshortest paths in equal proportions.

xxshdh

5. Randomization and Metering

When a packet arrives at node A and is assigned to one of two links, one way is randomization, means the packet is assigned to one of two links with probability p and 1-p. Here we only consider p=0.5. Another way is metering, in which the packet is assigned to a queue that currently has the smallest total backlog.

As shown in above figure, packets arrives at node A according to Poisson process with rate packets/sec. Node A sends packets to node B along two links with service rate . Packet transmission times are exponential distributed and independent of interarrival times. So it is an M/M/1 system.

If packets are assigned to one of two links by randomization with probability 1/2, the arrival process on each of the two queues is Poisson process. So that each of two queues forms an M/M/1 system with arrival rate and service rate. The average delay per packet is:

If packets are assigned to one of two links by metering, we can build an equivalent M/M/2 system with arrival rate and with each link playing as a server. Applying the result from M/M/2, the average delay per packet is:

Compare (15) and (16), it can be seen that the average delay by metering is (1+) times less that by randomization. But metering destroys the Poisson character of arrival process at the point of division. When metering is used in above example, the arrival process of packets to each link is no longer a Poisson process. The accuracy of M/M/1 approximation is degraded.

In this case, we still can use G/G/1 approximation to calculate average delay. In G/G/1, there is an important result on the upper bound of delay.

where

= Variance of the interarrival times

= Variance of the service times

= Average interarrival time

When the system is heavily loaded, W is close to the upper bound.

References

[1] D. Bertsekas and R. Gallager, “Data Networks,” Prentice Hall, Second Edition, 1992.