Routing in circuit-switched networks: optimization, shadow prices and decentralization

F. P. Kelly

Advances in Applied Probability 20 (1988), 112-144.


How should calls be routed or capacity allocated in a circuit-switched 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: network flow; adaptive routing; decentralization.


Frank Kelly's papers