Deterministic On-Line Routing on Area-Universal Networks
No Access Until
Permanent Link(s)
Collections
Other Titles
Author(s)
Abstract
Two deterministic routing networks are presented: the pruned butterfly and the sorting fattree. Both networks are area-universal, i.e., they can simulate any other routing network fitting in similar area with polylogarithmic slowdown. Previous area-universal networks were either for the off-line problem, where the message set to be routed is known in advance and substantial precomputation is permitted, or involved randomization, yielding results that hold only with high probability. The two networks introduced here are the first that are simultaneously deterministic and on-line, and they use two substantially different routing techniques. The performance of their routing algorithms depends on the difficulty of the problem instance, which is measured by a quantity