Dynamic cesaro-wardrop equilibration in networks

Borkar, V. S. ; Kumar, P. R. (2003) Dynamic cesaro-wardrop equilibration in networks IEEE Transactions on Automatic Control, 48 (3). pp. 382-396. ISSN 0018-9286

Full text not available from this repository.

Official URL: http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumb...

Related URL: http://dx.doi.org/10.1109/TAC.2003.809145


We analyze a routing scheme for a broad class of networks which converges (in the Cesaro sense) with probability one to the set of approximate Cesaro-Wardrop equilibria, an extension of the notion of a Wardrop equilibrium. The network model allows for wireline networks where delays are caused by flows on links, as well as wireless networks, a primary motivation for us, where delays are caused by other flows in the vicinity of nodes. The routing algorithm is distributed, using only the local information about observed delays by the nodes, and is moreover impervious to clock offsets at nodes. The scheme is also fully asynchronous, since different iterates have their own counters and the orders of packets and their acknowledgments may be scrambled. Finally, the scheme is adaptive to the traffic patterns in the network. The demonstration of convergence in a fully dynamic context involves the treatment of two-time scale distributed asynchronous stochastic iterations. Using an ordinary differential equation approach, the invariant measures are identified. Due to a randomization feature in the algorithm, a direct stochastic analysis shows that the algorithm avoids non-Wardrop equilibria. Finally, some comments on the existence, uniqueness, stability, and other properties of Wardrop equilibria are made.

Item Type:Article
Source:Copyright of this article belongs to Institute of Electrical and Electronic Engineers.
ID Code:5262
Deposited On:18 Oct 2010 07:39
Last Modified:20 May 2011 08:59

Repository Staff Only: item control page