Parallel path assignment of multicast connections in multi-path networks

In large multistage interconnection networks (MINs) supporting multicast (many-to-many) connections, a source-destination(s) connection may be blocked by some other established connection, even if the required destination is not busy. Moreover, switch and/or link faults may prevent servicing a number of connections. Blocking and switch/link faults can therefore significantly degrade the overall network performance in a random access environment. To make the network more robust and less susceptible to blocking, multiple-path MINs have been proposed. However, with multiple-paths MINs, the problem of conflict-free and fault-free path assignment for concurrent multicasts becomes a formidable task. In this paper, we review one serial algorithm that solves the path assignment problem in multi-path fault-tolerant multicast-connected MINs. The time complexity of this algorithm is O(m ρ^m), where m is the number of simultaneous multicast requests (sources) and ρ is the number of alternate paths in the multi-path network. We introduce another serial algorithm for path assignment with time complexity O(m ρ^2ξ), where ξ is the number of edges in the constraint graph specifying the conflict-free and fault-free paths servicing all pairs of multicast connections (sources). A parallel (SIMD) version of the second serial algorithm requiring O(ξ) processors is also presented. This parallel algorithm, with time complexity O(m(ρ⁴+log₂ξ)) under the single match assumption, further reduces the execution time of the parallel path assignment problem