Flow-Based Routing

Flow-Based Routing

Flow-Based Routing The algorithms studied thus far take solely the topology into consideration. They do not consider the load. If for example, there is always a huge amount of traffic from A to B, in Fig. 5-6, then it may be better to route traffic from A to C via AGEFC, even though this path is much longer than ABC. In this section we are going to study a static algorithmic program that uses each topology and cargo for routing. It is called flow-based routing. In some networks, the mean information flow between every try of nodes is comparatively stable and inevitable. For example, in a very company network for a place of business chain, each store might send orders, sales reports, inventory updates, and other well-defined types of messages to known sites in a predefined pattern, so the overall volume of traffic varies very little from day to day.

Under conditions during which the typical traffic from i to is thought beforehand and, to an affordable approxima tion, constant in time, it is possible to analyze the flows mathematically to optim ize the routing The basic idea behind the analysis is that for a given line, if the capacity and average flow are known, it is possible to cypher the mean packet delay on it line from queueing theory. From the mean delays on all the lines, it’s straightfor ward to calculate a flow-weighted average to induce the mean packet delay for the full subnet. The routing downside then reduces to finding the routing algorithmic program that produces the minimum average delay for the subnet. To use this system, certain information must be known in advance. First the subnet topology must be known. Second, the traffic matrix, Fij, must be given. Third, the road capability matrix, C;j, specifying the capacity of each line in bps must be available. Finally, a (possibly tentative) routing algorithmic program should be chosen. As an example of this method, consider the full-duplex subnet of Fig. 5-8(a).

The weights on the arcs give the capacities, C, in each direction measured in kbps. The matrix of Fig. 5-8(b) has an entry for each source-destination pair. The entry for source i to destination shows the route to be used for i-j traffic, and also the number of packets/sec to be sent from source i to destination i. For example, 3 packets/sec go from B to D, and they use route BFD to get there. Notice that some routing algorithm has already been applied to derive the routes shown in the matrix. Given this information, it is straightforward to calculate the total in line i, λi. For example, the B-D traffic contributes 3 packets/sec to the BF line and also 3 packets/sec to the FD line. Similarly, the A-D traffic contributes I packet/sec to each of three lines. The total traffic in each eastbound line is shown in the λi column of Fig. 5-9. In this example, all the traffic is symmetric, that is, the XY traffic is identical to the YX traffic, for all X and Y. In real networks this condition does not always hold. The figure also shows the mean number of packets/sec on each line. uc, assuming a mean packet size of 1/u = 800 bits.

The next-to-last column of Fig. 5-9 gives the mean delay for each line derived

from the queueing theory formula

T =  1/uC-λ

where i7 is the mean packet size in bits. C is that the capability in rate, and is that the mean flow in packets/sec. For example, with a capacity uC = 25 packets/sec and an actual flow = 14 packets/sec, the mean delay is 91 msec. Note that with 2=0, the mean delay is still 40 msec, because the capacity is 25 packets/sec. In other words, the “delay” includes both queueing and service time. To compute the mean delay time for the entire subnet, we take the weighted sum of each of the eight lines, with the weight being the fraction of the total traffic using that line. In this example, the mean turns out to be 86 msec. To evaluate a different routing algorithm, we can repeat the entire process. only with different flows to get a new average delay.

If we tend to prohibit ourselves to solely single path routing algorithms, as we’ve done up to now, there ar solely a finite range of how to route packets from every source to each destination. It is always possible to write a program to simply try them all, one after another, and find out which one has the smallest mean delay. Since this calculation can be done off-line in advance, the fact that it may be time consuming is not necessarily a serious problem. This one is then the best routing algorithm. Bertsekas and Gallagher (1992) discuss flow-based routing in detail.