Routing in circuit-switched networks: optimization, shadow prices and decentralization
- 1 March 1988
- journal article
- research article
- Published by Cambridge University Press (CUP) in Advances in Applied Probability
- Vol. 20 (01), 112-144
- https://doi.org/10.1017/S0001867800017973
Abstract
How should calls be routed or capacity allocated in a circuit-switched communication network so as to optimize the performance of the network? This paper considers the question, using a simplified analytical model of a circuit-switched network. We show that there exist implicit shadow prices associated with each route and with each link of the network, and that the equations defining these prices have a local or decentralized character. We illustrate how these results can be used as the basis for a decentralized adaptive routing scheme, responsive to changes in the demands placed on the network.Keywords
This publication has 14 references indexed in Scilit:
- One-Dimensional Circuit-Switched NetworksThe Annals of Probability, 1987
- Asymptotic analysis and computational methods for a class of simple, circuit-switched networks with blockingAdvances in Applied Probability, 1987
- Convergence and finite-time behavior of simulated annealingAdvances in Applied Probability, 1986
- Blocking probabilities in large circuit-switched networksAdvances in Applied Probability, 1986
- A chaotic asynchronous algorithm for computing the fixed point of a nonnegative matrix of unit spectral radiusJournal of the ACM, 1986
- Convergence of an annealing algorithmMathematical Programming, 1986
- The use of learning algorithms in telephone traffic routing—A methodologyAutomatica, 1983
- Asynchronous Iterative Methods for MultiprocessorsJournal of the ACM, 1978
- A Minimum Delay Routing Algorithm Using Distributed ComputationIEEE Transactions on Communications, 1977
- Application of Learning Automata to Telephone Traffic Routing and ControlIEEE Transactions on Systems, Man, and Cybernetics, 1977