Convergence of gradient projection routing methods in an asynchronous stochastic quasi-static virtual circuit network

The convergence of the gradient projection algorithms for optimal routing in virtual circuit data networks proposed by Bertsekas is studied. The routing model explicitly takes into account stochastic generation and termination of virtual circuits, distributed asynchronous routing updates, inaccurate flow measurement, and delays in forwarding control packets. The problem of assigning paths for incoming sessions (or virtual circuits) to implement the gradient projection algorithms is also studied. A metering rule based on deficiency in a desired number of virtual circuits is proposed and analyzed. It is shown that the proposed metering rule is better than a randomized rule in some sense. The gradient projection routing algorithms implemented either by the metering rule or the randomized rule are shown to converge to a neighborhood of a long-term optimal routing. The neighborhood converges to zero if the number of the virtual circuits tends to infinity while the total traffic requirement is kept constant.