无阻塞Clos-Type网上的多源点多播

MULTIPLE MULTICASTS ON CLOS-TYPE NONBLOCKING MULTICAST NETWORK

在并行和分布式环境中 ,提供无阻塞的多对多通信是至关重要的 .Clos- Type网络能很好地满足这些要求 ,因此得到广泛的应用 .但是目前对于这类网中的多源点多播 ,通常的办法是通过对输入端的请求逐个进行一到多播送的方式来实现 ,这样的方式算法效率较低 ,在 N× N的网络中时间复杂度达到Θ (N3/2 ) ,其中 N为网络输入端的总数 .文章主要研究的是 Clos- Type网上进行多源点多播的充分条件 ,并且通过引入分组、竞争互斥等机制 ,在中间级开关数目数量级不变的情况下使路由算法的时间复杂度降低至 :Θ N log Nloglog N2 log N ,从而在

In parallel and distributed systems, non blocking communications among multiple nodes are very important. The Clos Type network can satisfy this need quite well, so it is being used widely. But most of the multiple multicasts in this network are now accomplished by implementing the one to many communications step by step according to the input ports. The efficiency of this technique is low, and, in an N×N Clos Type network, the time complexity of the multicast routing algorithm using this technique is Θ(N 3/2 ) , and here N is referred to as the total number of input ports. In this paper, the sufficient condition of non blocking multiple multicasts in the Clos Type network is studied. And by using the grouping, competing and mutex schemes, the time complexity of the multicast routing algorithm in this network is reduced to ΘN log N loglog N 2log N , while the number of the switches in the middle stage of the network remains the same as above. Thus non blocking multiple multicasts in the Clos Type network are accomplished with quite lower time complexity.