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

摘要

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