On-line routing for permanent virtual circuits

This paper considers the problem of routing a set of permanent virtual circuit requests over a backbone network. Several factors make this routing problem complicated. Routing decisions must be made on-line without any knowledge of future request sets. Furthermore, frequent rerouting to correct inefficiencies that can result from the on-line routing decisions is not possible since rerouting creates a service disruption for the customer. Finally, the forward and reverse bandwidth of a virtual circuit must be routed over the same single path. Using an extensive set of simulations, this paper evaluates several different strategies for on-line permanent virtual circuit routing. We find that a strategy based on recent results in competitive analysis and ideas from combinatorial optimization consistently provides the best performance.