Multicast in Wormhole-Switched Torus Networks Using Edge-Disjoint Spanning Trees

A tree-based multicast algorithm for wormhole-switched networks which makes use of multiple edge-disjoint spanning trees is presented. The disjoint spanning-tree multicast, or DSTM, algorithm provides deadlock-free multicast routing that is fully compatible with unicast. The application of the DSTM algorithm to 2-dimensional torus networks is considered. A family of constructions of two spanning trees in the torus is given along with a formal proof of their edge-disjointness. Two constructions from this family are selected and shown to produce diameters no greater than twice that of the torus. Flit-level simulation results are presented to show that DSTM outperforms the best single spanning tree multicast approach by up to a factor of two. The DSTM algorithm is also simulated for different spanning tree constructions. The results show that our novel tree construction is significantly better for multicast than those produced by a general tree construction method that applies to arbitrary-topology networks (J. Roskind and R. Tarjan, Math. Oper. Res.10 (Nov. 1985), 701–708). Finally, two approaches to providing single link fault tolerance with DSTM are presented and evaluated.     

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.     

Multicast communication in wormhole-routed 2D torus networks with hamiltonian cycle model

In this paper, we propose an efficient multipath multicast routing algorithm in wormhole-routed 2D torus networks. We first introduce a hamiltonian cycle model for exploiting the feature of torus networks. Based on this model, we find a hamiltonian cycle in torus networks. Then, an efficient multipath multicast routing algorithm with hamiltonian cycle model (mulitpath-HCM) is presented. The proposed multipath multicast routing algorithm utilizes communication channels more uniformly in order to reduce the path length of the routing messages, making the multicasting more efficient. Simulation results show that the multicast latency of the proposed multipath-HCM routing algorithm is superior to that of fixed and dual-path routing algorithms.     

An optimal multicast algorithm for cube-connected cycles

This paper presents an efficient algorithm that implements one-to-many,or multicast,communication in one-port wormhole-routed cube-connected cycles(CCCs) in the absence of hardware multicast support.By exploiting the propoeries of the switching technology and the use of virtual channels,a minimumtime multicast algorithm is presented for n-dimensional CCCs that use deterministic routing of unicast messages.The algorithm can deliver a multicast message to m-1 destinations in [log2m] message-passing steps,while avoiding contention among the constitutent unicast messages,Performance results of a simulation study on CCCs with up to 10,240 nodes are also given.     

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.     

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     

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

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

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.     

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

对于一个由多个成员组成的分布式应用如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.     

基于调度集合的多播单播数据联合调度算法

首先定义和分析了IEEE802.16e无线城域网中的一个新问题,即如何在保证移动终端服务质量的前提下,通过合理地调度终端的单播业务和多播业务来降低终端能耗.针对该问题,提出一种基于调度集合的联合调度算法(scheduling set based integrated scheduling,简称SSBIS).SSBIS算法将所有移动终端划分到多播调度集合或单播调度集合中,并利用多播数据的传输特点,在多播数据传输的相邻时隙内发送多播调度集合中所有终端的单播数据,而对于单播调度集合中的终端,则通过凸优化方法求得使终端休眠时间最长的单播业务调度方案,以达到降低终端能耗的目的.仿真实验显示,SSBIS算法在满足移动终端的最小数据速率要求的同时,可以明显地降低终端能耗.     

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     

Adaptive Wormhole Routing in Hypercube Multicomputers

Both adaptive unicast routing and efficient multicast communication have been shown to be important to the performance of distributed-memory multiprocessors, or multicomputers. In this paper, we propose a uniform adaptive routing strategy for wormhole-routed hypercube networks that accommodates both unicast and multicast communication. Based on a node labeling method, the resultant routing algorithms are shown to be deadlock-free without requiring virtual channels. We present an optimal ordering algorithm that minimizes the traffic generated under the proposed paradigm. A greedy algorithm with less time complexity is also proposed.     

A real-time video multicast architecture for assured forwarding services

This paper presents our work on developing an architecture for multicasting real-time MPEG4 over IP networks that provide service differentiation. In particular, this work is targeted at assured forwarding (AF) style services. This work is an attempt to find a simple solution to the problem of multicast congestion control of real-time traffic by exploiting the service differentiation capabilities of AF networks. Our architecture assumes loss differentiation in the network and assumes the network's ability to provide explicit congestion notification messages to the sender. We do not consider policing/shaping at the edge routers. Rather, we consider a more general case where packet marking and flow control are provided at the senders. For this network model, we built an end-to-end architecture and developed a rate-adaptation algorithm that can operate in both unicast and multicast applications with a minor modification. The simulation results show how the rate-adaptation algorithm accommodates different receivers with different networking capabilities and provides receivers with different levels of quality by taking advantage of the queue management capabilities of the AF service. We test how the architecture scales to a large number of receivers, how multiple multicast sessions interact, and how it interacts with TCP.     

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

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

Mathematical theory of teletraffic and its application to the analysis of multiservice communication of next generation networks

This paper presents a survey of the authors results to discuss the model of a multiservice network with “triple play” (unicast, multicast, and elastic) traffic. The main results are given for the model with multicast traffic. Two service disciplines for multicast traffic are considered in the form of systems with transparent requests. An algorithm for the calculation of the blocking probabilities for models involving both unicast and multicast traffic is proposed. In conclusion, the lines of further research are outlined: the analysis of models of the session initiation protocol (SIP), including design problems to control overloads in SIP server networks, the planning of cross-layer interfaces for orthogonal frequency division multiplexing in mobile networks long term evolution (LTE), and the design of methods for the analysis of the quality factors of the file exchange and streaming in peer-to-peer (P2P) networks.     

无线Mesh 网络低干扰组播

不同于无线传感器网络和移动Ad Hoc网络,无线Mesh网络中的组播主要侧重于提高吞吐量,而干扰是影响吞吐量的重要因素。在构建组播拓扑时,传统的方法主要考虑最小价值或最短路径,而通过减少干扰来提高组播性能的研究较少,且它们的干扰计算方法都采用单播的思想,并不适合于组播。例如,当n个接收节点同时从一个节点接收数据时,在组播中这n个接收节点之间不存在干扰,而在单播中认为存在干扰。因此,提出了组播冲突图来计算组播干扰,给出组播树干扰的定义。可以发现,求最小干扰组播扰树是NP完全问题,然后提出基于万有引力的启发式算法构建具有较小干扰的组播树。为了适用于多信道的情况,提出了满足不同干扰范围的多跳信道分配算法。最后,仿真结果显示,与MCM相比,所提出的算法无论是在单天线单信道还是多天线多信道下,都能取得较高的吞吐量和较低的延迟。     

Architectural support for efficient multicasting in irregularnetworks

Parallel computing on networks of workstations is fast becoming a cost-effective high-performance computing alternative to MPPs. Such a computing environment typically consists of processing nodes interconnected through a switch-based irregular network. Many of the problems that were solved for regular networks have to be solved anew for these systems. One such problem is that of efficient multicast communication. In this paper, we propose two broad categories of schemes for efficient multicasting in such irregular networks: network interface-based (NI-based) and switch-based. The NI-based multicasting schemes use the network interface of intermediate destinations for absorbing and retransmitting messages to other destinations in the multicast tree. In contrast, the switch-based multicasting schemes use hardware support for packet replication at the switches of the network and a concept known as multidestination routing to convey a multicast message from one source to multiple destinations. We first present alternative schemes for efficient multipacket forwarding at the NI and derive an optimal k-binomial multicast tree for multipacket NI-based multicast. We then propose two switch-based multicasting schemes that differ in the power of the encoding scheme and the complexity of the decoding logic at the switches. These multicasting schemes use path-based multidestination worms that can cover all nodes connected to switches along a valid unicast path and tree-based multidestination worms that can cover entire destination sets in a single phase using one worm, respectively. For each scheme, we describe the associated header encoding and decoding operation, the method for deriving multidestination worms that cover arbitrary multicast destination sets, and the multicasting scheme using the derived multidestination worms     

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

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