Static and dynamic path selection on expander graphs (preliminary version)
Andrei Broder, ALAN M. FRIEZE, Eli Upfal · 1997
This paper addresses the problem of virtual circuit switching in bounded degree expander graphs.We study the static and dynamic versions of this problem.Our solutions are baaed on the rapidly mixing properties of random walks on expander graphs.In the static version of the problem an algorithm is required to route a path between each of K pairs of vertices so that no edge is used by more than g paths.A natural approach to this problem is through a multicommodity flow reduction.However, we show that the random walk approach leads to significantly stronger results than those recently obtained by Leighton and Rao [10] using the multi-commodity flow setup.In the dynamic version of the problem connection requests are continuously injected into the network, Once a connection is established it utilizes a path (a virtual circuit) for a certain time until the communication terminates and the pat h is deleted.Again each edge in the network should not be used by more than g paths at once.The dynamic version is a better model for the practical use of communication networks.Our random walk approach gives a simple and fully distributed solution for this problem.We show that if the injection to the network and the duration of connections are both controlled by Poisson processes then our algorithm achieves