T. Tajimi, T. Sasama, and H. Masuyama (Japan)
optical multistage interconnection networking, multicast ing communication, greedy method, graph coloring algo rithm, Odd-Even algorithm, all-to-all personalized commu nication
Optical multistage interconnection networking presents different and interesting challenges to the study of multi casting or the more dense collective communication prob lem of electronic counterparts, because of a different un desired coupling of two signals within a switching element and of a demand for higher speed processing. That is, an efficient routing process through an optical network while avoiding “crosstalk” is required, and this can be achieved by minimizing total processing time (initial route comput ing time and real routing time). The former factor is to determine a routing algorithm whose time complexity is the minimum. The latter one is to determine the optimum routing by which all data can be routed from the inputs to the appropriate outputs in the minimum number of passes through the network. These two factors are in counterpoint to each other. In this paper, first, one approach (named source-order routing) for minimizing the total processing time required in multicasting communication, based on the greedy method, is examined by comparing it with two other approaches; a heuristic graph coloring algorithm and the Odd-Even algorithm. Next, all-to-all personalized commu nication is taken up as the most densely collective com munication, and this communication algorithm with single fault-tolerant capability is investigated.
Important Links:
Go Back
