DETERMINISTIC ONLINE ROUTING ON AREA-UNIVERSAL NETWORKS

Two deterministic routing networks are presented: the Pruned butterfly and the sorting fat-tree. Both networks are area-universal, that is, they can simulate any other routing network fitting in similar area wi th polylogarithmic slowdown. Previous area-universal networks were eit her for the off-line problem, where the message set to be routed is kn own in advance and substantial precomputation is permitted, or involve d randomization, yielding results that hold only with high probability . The two networks introduced here are the first that are simultaneous ly deterministic and on-line, and they use two substantially different routing techniques. The performance of their routing algorithms depen ds on the difficulty of the problem instance, which is measured by a q uantity lambda known as the load factor. The pruned butterfly runs in time O(lambda log(2) N), where N is the number of possible sources and destinations for messages and lambda is assumed to be polynomial in N . The sorting fat-tree algorithm runs in O(lambda log N + log(2) N) ti me for a restricted class of message sets including partial permutatio ns. Other results of this work include a ''flexible'' circuit that is area-time optimal across a range of different input sizes and an area- time lower bound for routers based on wire-length arguments.