ONLINE 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 r outing problem complicated. Routing decisions must be made on-line wit hout any knowledge of future request sets. Furthermore, frequent rerou ting to correct inefficiencies that can result from the on-line routin g decisions is not possible since rerouting creates a service disrupti on for the customer. Finally, the forward and reverse bandwidth of a v irtual circuit must be routed over the same single path. Using an exte nsive set of simulations, this paper evaluates several different strat egies for on-line permanent virtual circuit routing. We find that a st rategy based on recent results in competitive analysis and ideas from combinatorial optimization consistently provides the best performance.