通过改变开关状态实现多源点多播

在并行和分布式环境中 ,多个结点之间的通讯一直是研究工作的焦点问题 ,这些通讯主要包括置换、多播(Multicast)及多源点多播 (Multiple Multicast) .L ai提出了适用于一类与带缓存的 Cube网相互拓扑等价的网络的置换算法 ,硬件代价为 O(N log N ) ,算法的时间复杂度为 O(N ) .Feng提出的 inside- out算法实现了 Omega- 1 × Omega网上的置换 ,总的路由时间复杂度为 O(N log N) ,硬件代价为 O(N log N) .支持严格无阻塞置换的三级 Clos网的总的交叉点数为O(N32 ) .支持严格无阻塞的多播的三级 Clos网为 O(N32 logrloglogr) .Yang提出了一种新的多播网络 ,硬件复杂度为 O(N log2 N ) .为了支持多源点多播 ,多级互联网硬件代价往往大幅上升 .本文借鉴了 L ai提出的规则改变开关状态的方法 ,并把这种算法推广到了多源点多播的情况 .提出了一种新的多源点多播路由算法 ,此算法也同样适用于这一类相互拓扑等价的多级互联网 ,包括 Baseline、Om ega、Cube等 .在此算法中 ,每个数据流被划分为固定大小的数据包 ,在网络中独立传送 ,网络中的每个开关的状态按照固定的状态每个时步规则变化 ,每个数据包两次经过网络后到达目标结点 .此类的网络的硬件代价为 O(Nlog N ) ,此多源点多播路由算法的时间复杂度为 O(N )

Performing Multiple Multicasts by Changing Switch Status

In parallel and distributed systems, the communication among multiple nodes is the focus of research work. The communication includes permutation, multicast and multiple multicasts. Lai proposed a permutation algorithm for a kind of networks that are topologically equivalent to the Cube network with buffer. The time complexity of Lai's permutation algorithm is O(N), whereas the time complexity of Feng's inside out algorithm is O(NlogN).And the hardware cost of this network isO(NlogN), which is optimal by now. For example, the hardware cost of Clos typed networkis O(N 32 logrloglogr) and the hardware cost of Yang's network isO(Nlog 2N) . In this paper, we studied Lai's permutation algorithm and proposed a new algorithm for multiple multicasts. This algorithm is also applicable to a kind of networks including Baseline, Omega, Cube networks. In this algorithm, every data stream is divided into several fix sized packages and the packages are transferred in the network independently. The switch status is changed regularly in every step,and each package can arrive its destination(s) after passing the network twice. The hardware cost of this network is O(NlogN). and the time complexity of this multicast algorithm is O(N).