A Unified Theory of Flow Control and Routing in Data Communication Networks

Book excerpt: A joint flow control and routing (JFCR) strategy is proposed for store and forward communication networks. The strategy is based on a convex optimization problem in terms of the average input rates and multi-commodity flows and is shown to have the following properties: First the average load of each buffer stays below some arbitrarily chosen level for the input rate and routing assignments of the strategy. This level can be chosen so as to upper bound the probability of buffer overflow arbitrarily. Secondly, by proper selection of the cost function, it is possible to utilize the network fully and to achieve a variety of different types of priorities in the services offered to the users. Finally, the routing assignments of the strategy correspond to a routing strategy/which tends to minimize the total delay when the network is lightly loaded and tends to prevent congestion when it is heavily loaded. Furthermore, the proposed JFCR problem is shown to be equivalent to a minimum delay routing problem corresponding to a bigger network. Accordingly, any minimum delay routing algorithm can be converted into a JFCR algorithm. Using this approach, a class of JFCR algorithms with distributed computations at the nodes are developed. Under certain conditions, a one to one correspondence is shown to exist in a store and forward network between the set of average input rates and the set of average number of outstanding packets of commodities. This unique correspondence is used to show that in practice the average input rates can be adjusted as desired by restricting the number of outstanding packets on each commodity (window strategy).