Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 780.68005
Autor: Erdös, Paul; Hsu, D.Frank
Title: Distributed loop network with minimum transmission delay. (In English)
Source: Theor. Comput. Sci. 100, No.1, 223-241 (1992).
Review: Distributed loop networks are networks with at least one ring structure. They are widely used in the design of local area networks, multimodule memory organizations, data alignments in parallel memory systems, and supercomputer architecture. In this paper, we give a systematic and unified method of solutions in the design and implementation of these networks. We show that doubly linked loop networks with transmission delay less than or equal to (1+\epsilon)\sqrt {3N} can be constructed asymptotically for sufficiently large N, the number of nodes in the network. This is close to the optimal value within a number which is small as compared to N. We then give several infinite classes of values of N for which optimal doubly linked loop networks can be actually designed. The method is then generalized to obtain a new upper bound for possible transmission delays in multiply linked loop networks. Routing and rerouting algorithms are designed for the optimal loop networks.
Classif.: * 68M10 Computer networks
Keywords: Distributed loop networks; design; implementation; doubly linked loop networks; transmission delays; multiply linked loop networks; Routing and rerouting algorithms
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag