Multipath-Based Multicasting Strategies for Wormhole-Routed Star Graph Interconnection Networks

The star graph interconnection network has been recognized as an attractive alternative to the popular hypercube network. In this paper, we present a multipath-based multicast routing model for wormholerouted star graph networks, propose two efficient multipath routing schemes, and contrast the performance of the proposed schemes with the performance of the scheme presented in our previous work. Both of the two proposed schemes have been proven to be deadlock-free. The first scheme, simple multipath routing, uses multiple independent paths for concurrent multicasting. The second scheme, two-phase multipath routing, includes two phases: source-to-relay and relay-to-destination. For each phase, multicasting is carried out using simple multipath routing. Experimental results show that, for short and medium messages with small message startup latencies, the proposed schemes reduce multicast latency more efficiently than other schemes.     

Turn Grouping for Multicast in Wormhole-Routed Mesh Networks Supporting the Turn Model

Multicast is an important collective communication in scalable parallel computers. One efficient scheme to perform multicast is multidestination messaging[8]. In multidestination messaging, destination nodes of a multicast are partitioned into disjoint groups. Nodes in each group are reached with a multidestination message that conforms to the base routing algorithm of the system. A systematic way of partitioning the nodes is critical to the efficiency of multidestination messaging. In this paper we propose a node grouping method, called turn grouping, for partitioning the destination nodes in a multicast. Turn grouping is general in the sense that it supports any base routing algorithm derivable from the turn model [5]. Given such a base routing algorithm and the corresponding prohibited turns, turn grouping can systematically produce a proper schedule for multicasting the message. We evaluated the performance of turn grouping using three typical turn model-based routing algorithms. The simulation results show that our approach performs better than the Umesh [12] and the Hamiltonian-path [8] algorithms.     

An Efficient Tree-Based Multicasting Algorithm on Wormhole-Routed Star Graph Interconnection Networks Embedded with Hamiltonian Path

Multicasting is an important issue for numerous applications in parallel and distributed computing. In multicasting, the same message is delivered from a source node to an arbitrary number of destination nodes. The star graph interconnection network has been recognized as an attractive alternative to the popular hypercube network. In this paper, we propose an efficient and deadlock-free tree-based multi-cast routing scheme for wormhole-routed star graph networks with hamiltonian path. In our proposed routing scheme, the router is with the input-buffer-based asynchronous replication mechanism that requires extra hardware cost. Meanwhile, the router simultaneously sends incoming flits on more than one outgoing channel. We perform simulation experiments with the network latency and the network traffic. Experimental results show that the proposed scheme reduces multicast latency more efficiently than other schemes.     

All-To-All Personalized Communication in Wormhole-Routed 2D/3D Meshes and Multidimensional Interconnection Networks

2004.29计算机工程与应用1INTRODUCTIONInamessage-passingmulti-computernetwork,processorsoftenneedtocommunicatewitheachotherforvariousrea-sons,suchasloadbalancing,eventsynchronization,anddataexchange.Basedonthenumberofsendingandreceivingpro-cessors,thesecommunicationscanbeclassifiedintocommuni-cationpatternssuchasone-to-one(unicast),one-to-many(multicast),one-to-all(broadcast),andall-to-all.Thenatureofthemessagetobesentcanbeclassifiedaspersonalizedornon-personalized.Theall-to-allpersonalized…     

Fault-Tolerant Broadcasting in 2-D Wormhole-Routed Meshes

In this paper, a fault-tolerant broadcast scheme in 2-D meshes with randomly generated faults is provided. This approach is based on an early work on time-step optimal broadcasting in square-shape fault-free 2-D meshes with optimal total communication distance (TCD). An extension to any rectangular-shape fault-free 2-D meshes is first given. The fault block model is used in which all faulty nodes in the system are contained in a set of disjoint blocks. The boundary lines of blocks divide the whole mesh into a set of fault-free polygons and a sequence of rectangular fault-free regions is derived from these polygons. The broadcast process is carried out at two levels: inter-region and intra-region. In the inter-region-level broadcast, the broadcast message is sent from a given source to a special node (called eye [1]) in each rectangular fault-free region. In the intra-region-level broadcast, the extended optimal fault-free broadcast is applied. Some analytical results are given including an upper bound of TCD.     

超立方体互连网络中的组播算法研究

在高性能计算中,涉及全局数据迁移、进程控制等操作的通信被称为聚合通信。高效的聚合通信服务不仅能够简化编程,而且能够提高系统效率和整体性能。组播作为聚合通信的通用模式之一,长期以来都是人们的研究重点,包括硬件加速、软件优化、针对不同拓扑结构的研究等。本文研究了超立方体网络中的组播算法,并分析了进一步的研究方向。     

移动机会网络组播路由的研究进展

在移动机会网络中,节点进行机会式的连接通信,该方式被广泛应用于移动社交网络、车载智能网络、移动自组网络等场景中。移动机会网络群组通信在抢险救灾、社区消息分发及智能交通等领域具有极高的应用价值,组播路由技术是其关键技术之一。将移动机会网络组播路由分为传统组播路由和智能组播路由两类,重点介绍了智能组播路由的研究现状,并采用通用的性能指标对各组播路由策略进行了比较分析。分析结论为:智能组播路由由于考虑了移动机会网络的社会特性、节点缓存、能量及安全等特性,因此具有较好的综合性能。最后展望了组播路由在大数据缓存管理、群组安全策略、车载自组网及动态感知方面的研究前景。     

一种适合2D-Mesh互连网络的树状多播算法

针对虫蚀寻径的2D－Mesh互连的多处理机网络，归纳了多播算法的要求，在分析比较路状多播和树状多播算法的基础上，提出一种结合两者优点的新型树状多播算法，该算法基于Hamilton寻径，即源节点到每一个目标节点的路径为最短路径，且具有无死锁的特性，同时，多播数据在源节点发送，途径节点转发所需计算的时间复杂度均为O（1），与多播目标节点集的大小和分布无关，数据模拟测试的结果表明，该算法的性能优越。     

基于虫孔交换的树型多播无死锁充要条件分析

多播作为其他聚合通信的基础操作,对并行系统的性能有着重要的影响。在无死锁、无拥塞的情况下,基于虫孔交换的树型多播能够取得较高的性能和信道利用率。本文在对树型多播过程中消息依赖关系分析的基础上,给出了基于虫孔交换的树型多播无死锁的充要条件。     

移动Ad Hoc网络多播路由协议的研究进展

移动AdHoc网络是一个自组织、移动节点通过无线链路组成的动态拓扑变化的网络.由于网络规模小、无基础设施、构建迅速等特点,从而广泛用于紧急事件、军事和民用领域以及多媒体应用等.随着网络应用规模的增长,在移动AdHoc网络中支持多播路由成为网络领域中一类重要的研究课题.该文综述了移动AdHoc网络多播路由方面的一些最新工作,论述了设计移动AdHoc网络多播路由协议的特性、问题和技术,详细描述和比较了目前典型的移动AdHoc网络多播路由协议,为进一步的应用和研究提出了新的课题.     

Ad Hoc网络中基于熵的QoS多播路由研究

Ad Hoc网络自身固有的特点使得Ad Hoc网络的QoS路由协议面临许多新的挑战和机遇,而且出现了许多新的网络系统,如视频点播、远程教学、远程医疗等,这些多媒体实时系统已经不满足网络的单播数据。因此,网络数据的多播提上了日程。本文对QoS多播路由进行了阐述,提出了一种基于熵的稳定的QoS多播路由,并且对它进行了分析以及与已经存在的多QoS约束多播路由进行了比较。     

Ad Hoc网络QoS多播路由协议

随着高性能网络、移动网络及Internet的不断发展,具有QoS约束的多播路由技术已成为网络及分布式系统领域的一个重要研究课题．该文研讨了Ad Hoc网络中具有Qos约束的多播路由问题,其中主要包含延迟、带宽、代价等Qos约束．文中描述了一种适应于研究Ad Hoc网络Qos多播路由的网络模型,提出了Ad Hoc网络中一种具有QoS约束的多播路由协议(QMRP)．文中给出了该协议的正确性证明和复杂性分析．仿真实验结果表明,该协议较其它协议更适合于网络状态变化比较频繁的环境以及实时多媒体应用,优化了多播树的代价．QMRP为Ad Hoc网络QoS约束多播路由提供了一种新的有效途径．     

InfiniBand中面向有限多播表条目数的多播路由算法

高性能计算中,硬件支持的多播操作对集合通信的性能具有重要影响.随着超级计算机系统规模的不断扩大,多播组的个数急剧增加,可能会超过硬件支持的多播表条目数,而现有的多播路由算法没有给出相应的解决方案.提出一种面向有限多播表条目数的多播路由算法MR4LMS(multicast routing for limited MFT size),该算法使用先构造后染色、先染色后构造2种多播树构建方法,可显著降低所需的多播表条目数;而在多播表条目数不足时,通过合并算法将多个相似的多播组合并到一起以进一步减少所需的多播表条目数.在多种典型拓扑结构及通信模式下对MR4LMS进行了测试,结果表明仅需设置256个多播表条目就能够支持数千甚至数万个多播组,满足典型应用的需求.还对多播路由算法的最大EFI(edge forwarding index)及运行时间进行了测试,获得了令人满意的结果,表明MR4LMS可用于超大规模互连网络.     

Pseudo-cycle-based multicast routing in wormhole-routed networks

This paper addresses the problem of fault-tolerant multicast routing in wormholerouted multicomputers.A new pseudo-cycle-based routing method is presented for constructing deadlock-free multicast routing algorithms.With at most two virtual channels this technique can be applied to any connected networks with arbitrary topologies.Simulation results show that this technique results in negligible performance degradation even in the presence of a large number of faulty nodes.     

AODV路由算法的多播通信

ah—hoc网络具有网络拓扑结构易变的特性，苒加上移动网络本身具有的通信带宽有限，电池能源有限等特性。使得设计适合ad-hoc的路由协议具有一定的难度。AODV（Ad Hoc On—demand Distance Vector）是现在被广泛应用于adhoc网络中的一种按需路由算法，并且还设计了多播功能。多播是指一次给一个有明确定义的组发送消息。AODV的多播功能是路由器通过建立多播书树的方法实现的。本文主要介绍AODV路由协议算法的多播通信，其中详细介绍了多播树的建立过程和维护过程。并且选取传输半径和发包率为参     

Ad Hoc网络中的多播路由协议

无线Ad Hoc网络是指一组无线移动节点组成的多跳的,临时性的,无基础设施支持的无中心网络。多播是一种面向群组计算的通信传播方式,它使用单一的源地址把数据发给一组主机。如何在移动自组网中实现有效的多播路由技术是当前此领域研究中亟待解决的问题。文中对当前一些典型的多播路由协议进行了研究,并对它们各自的工作方式进行了分析,最后对它们各自的特点进行了比较。     

Ad Hoc网络中的多播路由协议

无线Ad Hoc网络是指一组无线移动节点组成的多跳的,临时性的,无基础设施支持的无中心网络。多播是一种面向群组计算的通信传播方式,它使用单一的源地址把数据发给一组主机。如何在移动自组网中实现有效的多播路由技术是当前此领域研究中亟待解决的问题。文中对当前一些典型的多播路由协议进行了研究,并对它们各自的工作方式进行了分析,最后对它们各自的特点进行了比较。     

基于PIM-DM的区分服务组播路由协议

区分服务和组播是下一代网络需要支持的两种关键技术。但是,在区分服务中支持组播需要解决被忽略的预约子树(NRS)和组成员异构性问题。解决这两个问题需要对传统的组播路由协议进行修改,使其满足区分服务网络的要求。论文改进了域内组播路由协议PIM-DM,解决了该协议在区分服务网络中应用时遇到的NRS和组成员异构性问题。由于PIM-DM和DVMRP都是工作在密集模式下数据驱动的组播路由协议,因此论文的方法同样适用于DVMRP协议。该方法在ns-2模拟器上进行了验证。     

一种基于分群的移动自组网多播路由协议

为提高多播协议的可扩展性,提出一个基于分群的高效多播路由协议(ECMRP)。采用改进的基于权重的分群算法对移动自组网中的移动节点进行分层管理,并应用软状态方法在群首间建立多播树,减小当网络拓扑结构动态变化时重构、维护多播树结构的控制开销。仿真实验结果表明,该算法在路由开销和分组投递率上均优于多播按需距离矢量和按需多播路由协议,更适合于高动态、大规模的自组网。     

WDM网络中实时组播的分布式优化RWA算法

在WDM网络中,由于每条链路上可用波长是动态变化的,在考虑波长转换延迟时间的条件下,实现实时组播连接的路由选择与波长分配是十分困难的。论文提出了一种用于建立实时组播连接的分布式路由选择与波长分配算法。该算法将路由选择与波长分配统一进行,大大减少连接的建立时间。组播路由算法以Prim最小生成树算法为基础,生成一棵满足给定延迟时限的最小成本树。波长分配使用最少波长转换和同一波长最长使用策略。