Optimal Congestion Control in Single Destination Networks

We present an algorithm for optimal routing in communication networks, resulting in minimum time and minimum total delay clearing of congested traffic towards a single destination. The algorithm is suitable for on-line implementation and can also be applied in the presence of time constant external arrival rates. In the case where several optimal solutions exist, the solution given is of the simplest form. The results are discussed and compared to existing ones, in particular to optimal feedback solutions found in the literature. The simplicity of approach and results allows us to give necessary and sufficient conditions for arrival rates, so that the minimal value for the maximal delay encountered by any packet in the network does not increase when these external arrivals are present. This suggests a flow control policy which, together with optimal routing, gives a guaranteed upper limit for traffic delay, while inhibiting incoming traffic as little as necessary. A thorough geometric interpretation is given and examples illustrate the applicability of results.