The 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, the paper evaluates several different strategies for on-line permanent virtual circuit routing. The authors find that a strategy based on results in competitive analysis and ideas from combinatorial optimization consistently provides the best performance. The problem of admission control is closely related to the problem of routing. The paper also provides a theoretical lower bound that suggests that non-greedy admission control is a fundamental component of an efficient on-line permanent virtual circuit routing algorithm.

This paper considers the problems of admission control and virtual circuit routing in high performance computing and communication systems. Admission control and virtual circuit routing problems arise in numerous applications, including video-servers, real-lime database servers, and the provision of permanent virtual channel in large-scale communications networks. The paper describes both upper and lower bounds on the competitive ratio of algorithms for admission control and virtual circuit routing in trees, arrays, and hypercubes (the networks most commonly used in conjunction with nigh performance computing and communication). Our results include optimal algorithms for admission control and virtual circuit routing in trees, as well as the first competitive algorithms for these problems on non-tree networks. A key result of our research is the development of on-line algorithms that substantially outperform the greedy-based approaches that are used in practice.>

Much of modernsystems programming involves designing algorithms for distributed systems in which the nodes have access to information about time.Time information can be used to estimate the time at which system or environment events occur, to detect process failures, to schedule the use of