二维环网中基于自适应维度气泡路由的组播算法

Multicast Algorithm Based on the Adaptive Dimensional Bubble Routing on 2-D Torus Network

介绍了一种称为二维环网维度气泡组播路由(2DTDBMR)的新型算法.基于在一套网络中,采用相同的路由策略支持报文的单播操作和组播操作的思想,在二维环网中,基于TADBR自适应路由,设计实现了2DTDBMR组播算法.该组播算法在路由器中实现了多目标路由以及报文复制,而且算法是无死锁的.通过对二维环网中报文所有可能的路由情况进行分析发现当采用2DTDBMR组播算法时,报文最终都可以到达目标点.最后,在自行设计的模拟工具RingNetSim上实现了2DTDBMR组播算法.在RingNetSim上分析了2DTDBMR算法的性能,结果显示环网维度气泡组播算法的性能优异.

One novel multicast （2DTDBMR） is presented in algorithm called 2-D torus＇ dimensional bubble multicast routing this paper. According to the idea of the unicast and multicast communication operations supported by the same underlying routing strategy, the 2DTDBMR multicast algorithm based on torus＇ adaptive dimensional bubble routing （TADBR） algorithm is realized on the 2-D torus network. The multicast algorithm supports multicast packets to realize multi-destinations routing and packet＇s replications by the router, Furthermore, 2DTDBMR multicasting algorithm is deadlock-free. By the analysis of all possible situations of routing packets in the 2-D torus network, it is concluded that all kinds of packets can arrive at their destinations when the 2DTDBMR multicasting algorithm is accepted. The detail proof is provided for these conclusions in the paper. Lastly, the 2-D torus simulator called RingNetSim is adapted. The simulator realized the 2DTDBMR multicasting algorithm. At the same time, some traditional multicast routing algorithms are also realized in the simulator such as BRCP-HL algorithm, Hamilton algorithm, Umesh algorithm and so on： The performance of the 2DTDBMR on RingNetSim is tested. The performance of those multicast routing algorithms are evaluated by adopting different buffering space, communication models and arbitration algorithms. The results show that the 2DTDBMR algorithm owns preferable performance.