Title :
A quasi-nonblocking self-routing network which routes packets in log2N time
Author :
De Biase, Giuseppe A. ; Ferrone, Claudia ; Massini, Annalisa
Author_Institution :
Dipartimento di Scienze dell´´Inf., Roma Univ., Italy
Abstract :
A self-routing multi-log-N permutation network is presented and studied. This network has log2N depth and N(log22N+log2N )/2 nodes, where N is the number of network inputs. Its parallel routing algorithm runs in log2N time. The network architecture guarantees that only a negligible quantity of information is blocked, while the quasi-totality of the information synchronously reaches the network outputs in log2N steps. This network works in pipeline, it has a modular architecture suitable for very large N, it can be used as very high performance fast packet switching fabric, and it is suitable for information exchange in very-large-scale multiprocessor systems
Keywords :
multiprocessing systems; packet switching; parallel algorithms; switching networks; telecommunication network routing; fast packet switching fabric; information exchange; modular architecture; network architecture; network inputs; network outputs; parallel routing algorithm; permutation network; quasi nonblocking self routing network; very-large-scale multiprocessor systems; Fabrics; Intelligent networks; Large-scale systems; Multiprocessing systems; Multiprocessor interconnection networks; Packet switching; Pipelines; Remuneration; Routing; Switches;
Conference_Titel :
INFOCOM '93. Proceedings.Twelfth Annual Joint Conference of the IEEE Computer and Communications Societies. Networking: Foundation for the Future, IEEE
Conference_Location :
San Francisco, CA
Print_ISBN :
0-8186-3580-0
DOI :
10.1109/INFCOM.1993.253402
