Traditional Quality-of-Service (QoS) routing proposals compute ``best'' paths based on the current snapshop of the network configuration. Such a myopic approach suffers from significant computation and communication overhead, as paths need to be recomputed every time a new flow enters the network. Further, it can lead to sub-optimal behaviour for the entire system. When one attempts to reduce the computation and communication overhead (e.g., by reducing the frequency of path-computation and link-state updates), the routing accuracy degrades. Hence, there is a fundamental tradeoff between the accuracy of the QoS routing decisions and the computation/communication overhead.
Using the idea of simplicity in large systems, we have developed a novel approach for QoS routing in high-bandwidth networks that can substantially alleviate the computation and communication overhead of QoS routing without sacrificing the performance. The new approach (which we refer to as an ``optimization-based'' approach to QoS routing) is based on the idea that when the capacity of the network is large, simple proportional routing scheme can approach the performance of the optimal dynamic routing schemes. In a proportional routing scheme, calls are routed to alternate paths based on pre-determined probabilities. The right routing probabilities can be derived from the solution of a simple optimization problem that depends only on the average demand and capacity of the network.
We then develop an online, distributed algorithm that can efficiently solve the optimal routing probabilities. We rigorously established the convergence of the algorithm to the optimal control parameters, and provided guidelines on how to choose the parameters of the algorithm to ensure efficient control. Our optimization-based approach to QoS routing has the following advantages: