Competitive routing of virtual circuits with unknown duration

In this paper we present a strategy to route unknown duration virtual circu its in a high-speed communication network. Previous work on virtual circuit routing concentrated on the case where the call duration is known in advan ce. We show that by allowing O(log n) reroutes per call, we can achieve O(l og n) competitive ratio with respect to the maximum load (congestion) For t he unknown duration case, where, n is the number of nodes in the network. T his is in contrast to the Omega((4)rootn) lower bound on the competitive ra tio for this case if no rerouting is allowed (Azar et al., 1992, Proc. 33rd IEEE Annual Symposium of Foundations of Computer Science, pp. 218-225). Ou r routing algorithm can be also applied in the context of machine load bala ncing of tasks with unknown duration. We present an algorithm that makes O( log n) reassignments per task and achieves O(log n) competitive ratio with respect to the load, where n is the number of parallel machines. For a spec ial case of unit load tasks we design a constant competitive algorithm. The previously known algorithms that achieve up to polylogarithmic competitive ratio for load balancing of tasks with unknown duration dealt only with sp ecial cases of related machines case and unit-load tasks with restricted as signment (C) 2001 Academic Press.