Competitive Routing of Virtual Circuits with Unknown Duration

摘要

In this paper we present a strategy to route unknown duration virtual circuits in a high-speed communication network. Previous work on virtual circuit routing concentrated on the case where the call duration is known in advance. We show that by allowing O(log n) reroutes per call, we can achieve O(log n) competitive ratio with respect to the maximum load (congestion) for the unknown duration case, where n is the number of nodes in the network. This is in contrast to the Ω(n) lower bound on the competitive ratio 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). Our routing algorithm can be also applied in the context of machine load balancing 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 special 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 special cases of related machines case and unit-load tasks with restricted assignment (Azar et al., 1993, Proc. Workshop on Algorithms and Data Structures, pp. 119–130; Azar et al., 1992, Proc. 3rd ACM-SIAM Symposium on Discrete Algorithms, pp. 203–210).