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

MULTIPLE MULTICASTS ON CLOS-TYPE NONBLOCKING MULTICAST NETWORK

作　　者：顾乃杰[1] 李栋[1] 熊焰[1] 潘伟[1] 刘刚[1] 

机构地区：[1]中国科学技术大学计算机科学与技术系,合肥230027

出　　处：《计算机研究与发展》2002年第3期354-359,共6页Journal of Computer Research and Development

基　　金：华为科技基金资助

摘　　要：在并行和分布式环境中 ,提供无阻塞的多对多通信是至关重要的 .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.

关 键 词：多源点多播 路由策略 并行路由算法 无阻塞Clos-Jype网 并行计算机网络 

分 类 号：TP393[自动化与计算机技术—计算机应用技术] TP338.6[自动化与计算机技术—计算机科学与技术]