Parallel algorithms for routing in nonblocking networks

Abstract Non-blocking networks have many applica-tions in communications. Typical examples are tele-phone switching networks and communication networks among processors or between processors and memory devices. We construct non-blocking networks that are efficient not only as regards their cost and delay, but also as regards the time and space required to control them. In this paper, we present the first simultane-ous “weakly optimal ” solutions for the explicit construc-tion of non-blocking networks, the design of algorithms and the design of data-structures. “Weakly optimal ” is in the sense that all measures of complexity (size and depth of the network, time for the algorithm, and space for the data-structure) are within one or more factors of Iogn of their smallest possible values. In fact, we explicit ly construct a scheme in which networks with n inputs and n outputs have size 0(n(/ogn)2) and depth O(logn). And we present deterministic and random-ized on-line parallel algorithms to establish and abol-ish routes dynamically in these networks. The de-terministic algorithm uses 0((/ogn)5) steps to process any number of transactions in parallel (with one pro-cessor per transaction), maintaining a data structure that use O (n(/ogn)2) words and the randomized algo-rithm uses O((logn)2) expected steps to process any number of transactions in parallel (with one processor per transaction), maintaining a data structure that use 0(n(/ogn)2) words. Permission to copy without fee all or part of this material is granted pro-vided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association for Computing Machinery. To cepy otherwise, or to republish, requires a fee and/or specific permission