Optimal multicast communication in wormhole-routed torus networks

This paper presents efficient algorithms that implement one-to-many, or multicast, communication in wormhole-routed torus networks. By exploiting the properties of the switching technology and the use of virtual channels, a minimum-time multicast algorithm is presented for n-dimensional torus networks that use deterministic, dimension-ordered routing of unicast messages. The algorithm can deliver a multicast message to m-1 destinations in [log₂ m] message-passing steps, while avoiding contention among the constituent unicast messages. Performance results of a simulation study on torus networks with up to 4096 nodes are also given     

Path-Based Multicast Communication in Wormhole-Routed Unidirectional Torus Networks

This paper addresses the problem of one-to-many, or multicast, communication in wormhole-routed,n-dimensional torus networks. The proposed methods are designed for systems that support intermediate reception, which permits multidestination messages to be pipelined through several nodes, depositing a copy at each node. A key issue in the design of such systems is the routing function, which must support both unicast and multicast traffic while preventing deadlock among messages. An efficient, deadlock-free routing function is developed and used as a basis for a family of multicast algorithms. TheS-torusmulticast algorithm uses a single multidestination message to perform an arbitrary multicast operation. TheM-torusalgorithm is a generalized multiphase multicast algorithm, in which a combination of multidestination messages is used to perform a multicast in one or more communication steps. Two specific instances of the M-torus algorithm, theM_d-torusandM_u-torusmulticast algorithms, are presented. These algorithms produce contention-free multicast operations and are deadlock-free under all combinations of network traffic. A simulation study compares the performance of the different multicast algorithms, and implementation issues are discussed. The results of this research are applicable to the design of architectures for both wormhole-routed massively parallel computers and high-speed local area networks with wormhole-routed switch fabrics.     

同源同宿SSM组播路由控制技术研究

由于组播报文总是沿着从组播接收者到组播发送者单播路由的相反方向进行转发,这决定了同一主机收到的同一组播源的不同组播流通常总是沿着相同的路径传送。针对某些应用场景中需要将这些报文人工分流到不同的链路传送的情况,在阐述组播转发原理的基础上,探讨了组播路径控制的关键技术,并提出了解决此类组播分流问题的思路,在现网上部署后满足了业务系统需求,同时方案简单和易于工程实现。     

Unicast-based multicast communication in wormhole-routed networks

Multicast communication, in which the same message is delivered from a source node to an arbitrary number of destination nodes, is being increasingly demanded in parallel computing. System supported multicast services can potentially offer improved performance, increased functionality, and simplified programming, and may in turn be used to support various higher-level operations for data movement and global process control. This paper presents efficient algorithms to implement multicast communication in wormhole-routed direct networks, in the absence of hardware multicast support, by exploiting the properties of the switching technology. Minimum-time multicast algorithms are presented for n-dimensional meshes and hypercubes that use deterministic, dimension-ordered routing of unicast messages. Both algorithms can deliver a multicast message to m-1 destinations in [log ₂ m] message passing steps, while avoiding contention among the constituent unicast messages. Performance results of implementations on a 64-node nCUBE-2 hypercube and a 168-node Symult 2010 2-D mesh are given     

Store-and-Forward Multicast Routing on the Mesh

We study the complexity of routing a set of messages with multiple destinations (multicast routing) on an n-node square mesh under the store-and-forward model. A standard argument proves that time is required to route n messages, where each message is generated by a distinct node and at most c messages are to be delivered to any individual node. The obvious approach of simply replicating each message into the appropriate number of unicast (single-destination) messages and routing these independently does not yield an optimal algorithm. We provide both randomized and deterministic algorithms for multicast routing, which use constant-size buffers at each node. The randomized algorithm attains optimal performance, while the deterministic algorithm is slower by a factor of O( log ² n). We also describe an optimal deterministic algorithm that, however, requires large buffers of size O(c). A preliminary version of this paper appeared in Proceedings of the 13th Annual ACM Symposium on Parallel Algorithms and Architectures, Crete, Greece, 2001. This work was supported, in part, by MIUR under project ALGO-NEXT.     

基于向量时间的因果序通信协议的研究与设计

对于一个由多个成员组成的分布式应用如CSCW、副本数据库应用等来说,一个成员为了完成其所承担的任务,通常不仅要给其它成员发送组播消息,而且还要给某个或某些成员发送单播消息,并且这些消息形成了一种相互依赖的因果序关系。为了有效地支持成员之间的交互及分布式应用的开发,提出了一个新的基于向量时间的因果序单播、组播混合通信协议－CR＿UMcast协议。该协议允许组成员既可以发送组播消息,又可以发送单播消息,并且保证按它们之间的因果优先顺序进行传递。     

A hybrid multicast–unicast assignment approach for data distribution management in HLA

The main focus of data distribution management (DDM) in HLA is to reduce the amount of data received by federates in large-scale distributed simulations. The use of limited multicast resources plays a key role in the performance of DDM. In order to improve the performance of DDM by using communication protocol effectively, a hybrid multicast–unicast data transmission problem and its formal definition are presented, and then a hybrid multicast–unicast assignment approach is proposed. The approach uses a new adaptive communication protocol selection (ACPS) strategy to utilize the advantages of multicast and unicast, avoid their disadvantages, and consider the inter-relationship between connections. It includes the ACPS static assignment algorithm and the ACPS dynamic assignment algorithm, according to the difference between the static connections and the dynamic connections. In our approach, a concept of distance is presented to measure the inter-relationship between connections for multicast and the message redundancy for unicast, which is the core of the two algorithms in order to gather the connections to a multicast group or to balance the use of unicast and multicast for best performance. As a result, our algorithms can more effectively decide whether a new connection should use unicast or multicast communication, and whether adjusting previous assignment result can further improve the performance. In addition, a control mechanism is introduced to deal with connection changes during the dynamic assignment. The experiment results indicate that our algorithms can utilize the multicast and unicast communication resources effectively, as well as can achieve better performance than existing methods in the real running environment.     

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

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

基于拥塞控制的片上网络多播路由算法

为了满足片上网络日益丰富的应用要求,多播路由机制被应用到片上网络,以弥补传统单播通信方式的不足。以Mesh和Torus类的片上网络为例,分析了基于路径的3种多播路由算法(即XY路由、UpDown路由和SubPartition路由算法),并研究了相应的拥塞控制策略。通过模拟实验表明,多播较单播通信具有更小的平均传输延时和更高的网络吞吐量,且负载分配均匀;特别是SubPartition路由算法随着规模增大效果更加明显;提出的多播拥塞控制机制,能更有效地利用多播通信,提高片上网络的性能。     

一种基于遗传算法有时延约束的选播路由算法

选播是一种新型的网络服务，是IPv6的一个新特性。与单播、组播一样，都是IP的一种通信模式。本文在分析选播通信服务的基础上，提出了一种改进的遗传算法以求解有时延约束的选播路由问题。仿真实验结果表明，该算法是有效且切实可行的。     

一种动态的单组播集成调度算法

在单组播比例发生变化的情况下,现有单组播集成调度算法无法保持较高吞吐率。针对该问题,提出一种动态的单组播集成调度算法。基于输入排队(IQ)的交换结构,通过在输入端口处监测最近若干个时隙的单组播业务输入情况,动态决定当前的单组播集成调度策略。仿真结果表明,该算法的单播吞吐率、组播吞吐率和总体吞吐率均高于FILM算法和fSCIA算法,并具有较好的时延性能。     

小型组多播协议综述

小型组多播（SGM）是未来多播的发展方向。但是,传统多播协议并不适于处理数量庞大的小型组多播,因而研究专门针对小型组的小型组多播协议得到重视和发展。小型组多播协议大幅度减少路由器多播状态,并利用单播来实现多播。本文分类介绍了若干小型组多播协议,分析其各自特点,总结了小型组多播协议的评价指标,并探讨了未来的
发展方向。     

An efficient implementation of tree-based multicast routing for distributed shared-memory multiprocessors

This paper presents an efficient routing and flow control mechanism to implement multidestination message passing in wormhole networks. The mechanism is a variation of tree-based multicast with pruning to recover from deadlocks and it is well suited for distributed shared-memory multiprocessors (DSMs) with hardware cache coherence. It does not require any preprocessing of multicast messages reducing notably the software overhead required to send a multicast message. Also, it allows messages to use any deadlock-free routing function. The new scheme has been evaluated by simulation using synthetic loads. It achieves multicast latency reductions of 30% on average. Also it was compared with other multicast mechanisms proving its benefits. Finally, it can be easily implemented in hardware with minimal changes to existing unicast wormhole routers.     

基于ECN的单播流与多播流间带宽共享算法

An ECN-based implementing bandwidth-sharing algorithm for unicast and multicast flows is presented.The algorithm uses a bandwidth allocation strategy to give an incentive to multicast flows in bandwidth allocation according to algorithm of the number of receivers, and to assure the unicast flows get their bandwidth shares fairly.Provided best-effort networks, an ECN-based congestion control algorithm is used to implement differentiated service in bandwidth allocation between unicast flows and multicast flows. In implementation, we solve the problems such asreceiver‘s number estimation, the RTT estimation and compromise between convergence and stability.The simulation results show that the algorithm can implement bandwidth sharing for TCP flows and multicast flows. Atthe same time, the algorithm not only allocates more bandwidth to multicast flows, but promises TCP flows to get their fair bandwidth share.     

求解有度约束多播路由问题的分布式算法

在应用多播(multicast)时,有效的多播路由是关键.现有的多播路由算法一般假定每个节点都支持multicast,但在实际网络中,某些节点并不支持多播,而为了保证网络速度,需限制进行多播所要复制信息的数量.为此,采用度约束来表示每个节点的多播能力,提出了一种有度约束的分布式多播路由算法.算法的复杂度和所需传递信息的数量都低于已有的同类算法.     

Multicasting in the presence of aggregated deliveries

An increasing number of distributed systems relies on forms of message correlation, which result in atomic delivery of multiple messages aggregated by following process-specific criteria. Generally, more than one process is aggregating messages, implying that messages are multicast. While delivery guarantees for multicast scenarios with single message delivery are well understood, existing systems and models for aggregated deliveries either consider only unicast, centralized setups, or focus on efficiency thus providing only best-effort guarantees. This paper investigates the foundations of Multi-Delivery Multicast (MDMcast) in asynchronous distributed systems with crash-stop failures. We first describe a succinct aggregation model with a concise and generic predicate grammar for expressing conjunctions on messages and properties for a corresponding multicast primitive, which we term Conjunction-MDMcast (C-MDMcast). We show that for processes interested in identical conjunctions to achieve agreement on delivered messages, a total order on individual messages (or equivalent oracle) is not only useful but necessary, which is clearly opposed to single-message deliveries. We show this indirectly by exhibiting an algorithm implementing C-MDMcast on top of Total Order Broadcast (TOBcast) and vice-versa for a majority of correct processes. Then, we extend our predicate grammar with disjunctions, leading to the specification of Disjunction-MDMcast (D-MDMcast). We exhibit an algorithm implementing D-MDMcast, derived from our algorithm implementing C-MDMcast. We formalize several additional properties for both of our specifications, including ordering properties on aggregated messages and a notion of agreement capturing non-identical yet “related” conjunctions, and show how our respective algorithms implement these.     

TTPM – An efficient deadlock-free algorithm for multicast communication in 2D torus networks

A torus network has become increasingly important to multicomputer design because of its many features including scalability, low bandwidth and fixed degree of nodes. A multicast communication is a significant operation in multicomputer systems and can be used to support several other collective communication operations. This paper presents an efficient algorithm, TTPM, to find a deadlock-free multicast wormhole routing in two-dimensional torus parallel machines. The introduced algorithm is designed such that messages can be sent to any number of destinations within two start-up communication phases; hence the name Torus Two Phase Multicast (TTPM) algorithm. An efficient routing function is developed and used as a basis for the introduced algorithm. Also, TTPM allows some intermediate nodes that are not in the destination set to perform multicast functions. This feature allows flexibility in multicast path selection and therefore improves the performance. Performance results of a simulation study on torus networks are discussed to compare TTPM algorithm with a previous algorithm.     

基于选择函数的分布式启发算法DCLC—DSF

QoS路由的DCLC单播路由（Delay-Constrained Least-Cost Unicast Routing）问题属于NP－完全问题。本文提出一种多项式复杂度的分布式启发算法DCLC－DSF。DCLC－DSF基于简单的选择函数,每个网络结点只需维持本地的状态信息：相邻链路的延时和代价度量。该算法有以下优点：1）简单性;2）动态性;3）重路由功能;4）协商功能。在最坏情况下,DCLC－DSF的消息复杂度为O（e^2）,结点的计算复杂度为O（n^2）;在稳定的网络环境下,消息复杂度为O（e）。此外,本文还给出DCLC－DSF算法有限状态机模型。仿真实验表明：DCLC－DSF算法的平均代价不精确度是最佳算法的5－8％,证明它是一种简单、精确、健壮的的启发式算法。     

Quorum-based power-saving multicast protocols in the asynchronous ad hoc network

The asynchronous PS (Power-Saving) unicast protocol was designed for two PS wireless hosts to transmit the unicast message in the ad hoc network even their clocks are asynchronous. However, as regard to transmit a multicast message among more than two PS hosts, the protocol could not guarantee that all PS hosts can wake up at the same time. Some PS hosts may be in the PS mode when the multicast message is transmitted. Thus, the multicast message should be retransmitted again and again until all PS hosts receive the message. It will increase the energy consumption and the usage of the bandwidth. In this paper, we propose quorum-based PS multicast protocols for PS hosts to transmit multicast messages in the asynchronous ad hoc network. In those protocols, PS hosts use quorums to indicate their wakeup patterns. We introduce the rotation m-closure property to guarantee that m different quorums have the intersection even quorums are rotated due to asynchronous clocks. Thus, m PS hosts adopting m quorums satisfying the rotation m-closure property could wake up simultaneously and receive the multicast message even their clocks are asynchronous. We propose two quorum systems named the uniform k-arbiter and the CRT (Chinese Remainder Theorem) quorum system, which satisfy the rotation m-closure property. As shown in our analysis results, our quorum-based PS multicast protocols adopting those quorum systems can save more energy to transmit multicast messages.     

Efficient broadcast and multicast on multistage interconnectionnetworks using multiport encoding

This paper proposes anew approach for implementing fast multicast and broadcast in unidirectional and bidirectional multistage interconnection networks (MINs) with multiport encoded multidestination worms. For a MIN with n stages, such worms use n header flits each. One flit is used for each stage of the network and it indicates the output ports to which a multicast message needs to be replicated. A multiport encoded worm with (d₁, d₂..., d_n, 1⩽d_i⩽k) degrees of replication for the respective stages is capable of covering (d₁×d_x×...×d_n) destinations with a single communication start-up. In this paper, a switch architecture is proposed for implementing multidestination worms without deadlock. Three grouping algorithms of varying complexity are presented to derive the associated multiport encoded worms for a multicast to an arbitrary set of destinations. Using these worms, a multinomial tree-based scheme is proposed to implement the multicast. This scheme significantly reduces broadcast/multicast latency compared to schemes using unicast messages. Simulation studies for both unidirectional and bidirectional MIN systems indicate that improvement in broadcast/multicast latency up to a factor of four is feasible using the new approach. Interestingly, this approach is able to implement multicast with reduced latency as the number of destinations increases beyond a certain number. Compared to implementing unicast messages, this approach requires little additional logic at the switches. Thus, the scheme demonstrates significant potential for implementing efficient collective communication operations on current and future MIN-based systems