Efficient collective communication in optical networks

• Published in: Theoretical computer science 2000-02, Vol.233 (1-2), p.165-189
• Main Authors: BERMOND, J.-C, GARGANO, L, PERENNES, S, RESCIGNO, A. A, VACCARO, U
• Format: Article
• Language: English
• Subjects: Applied sciences; Computer Science; Computer science; control theory; systems; Computer systems and distributed systems. User interface; Data Structures and Algorithms; Discrete Mathematics; Exact sciences and technology; Flows in networks. Combinatorial problems; Networking and Internet Architecture; Operational research and scientific management; Operational research. Management science; Operations Research; Social and Information Networks; Software
• ISSN: 0304-3975; 1879-2294
• DOI: 10.1016/s0304-3975(98)00018-8

This paper studies the problems of One{to{All and All{to{All Communication in optical networks. In such networks the vast bandwidth available is utilized through wavelength division multiplexing: a single physical optical link can carry several logical signals, provided that they are transmitted on di erent wavelengths. In this paper we consider both single{hop and multihop optical networks. In single{hop networks the information, once transmitted as light, reaches its destination without being converted to electronic form in between, thus reaching high speed communication. In multihop networks a packet may have to be routed through a few intermediate nodes before reaching its nal destination. In both models we give e cient One{to{All and All{to{All Communication algorithms, in terms of time and number of wavelengths. We consider both networks with arbitrary topologies and particular networks of practical interest. Several of our algorithms exhibit optimal performances.