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

• 作者: 刘刚 李栋 潘伟 顾乃杰
• 来源期刊: 小型微型计算机系统
• 学科: 工学
• 关键词: 多级互联网 开关状态 置换 多播 多源点多播
• 年，卷（期）: 2003,（3）
• 页码范围: 435-439
• 页数: 5页
• 分类号: TP393
• 字数: 6056字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-1220.2003.03.027

摘要

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