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.     

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     

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.     

Ad hoc网络中一种带预测的路由算法

在自组网中,由于网络节点的移动性及拓扑结构的易变性,设计稳定的路由成为最受关注的问题。根据可靠性为多路径路由选择更多的可靠路径,以满足自组网中多路径传输在路径的数量和质量方面的需求,是多路径路由技术中的一个重要研究课题。为此,基于GRID模型和预测模型提出了一种带预测的稳定不相交备用路由算法,其利用有效限制路由查询包的泛洪区域,并结合预测策略和节点不相交路径算法来选择一条最稳定的不相交备用路由,从而进一步提高该路由算法的性能。模拟结果显示,与其他3个多路径路由相比较,该算法是一个有效的自组网路由算法。     

Resource deadlocks and performance of wormhole multicast routingalgorithms

We show that deadlocks due to dependencies on consumption channels are a fundamental problem in wormhole multicast routing. This type of resource deadlocks has not been addressed in many previously proposed wormhole multicast algorithms. We also show that deadlocks on consumption channels can be avoided by using multiple classes of consumption channels and restricting the use of consumption channels by multicast messages. We provide upper bounds for the number of consumption channels required to avoid deadlocks. In addition, we present a new multicast routing algorithm, column-path, which is based on the well-known dimension-order routing used in many multicomputers and multiprocessors. Therefore, this algorithm could be implemented in existing multicomputers with simple changes to the hardware. Using simulations, we compare the performance of the proposed column-path algorithm with the previously proposed Hamiltonian-path-based multipath and an e-cube-based multicast routing algorithms. Our results show that for multicast traffic, the column-path routing offers higher throughputs, while the multipath algorithm offers lower message latencies. Another result of our study is that the commonly implemented simplistic scheme of sending one copy of a multicast message to each of its destinations exhibits good performance provided the number of destinations is small     

一种新的基于混沌神经网络的组播路由算法

探讨了在高速包交换计算机网络中,具有端到端时延及时延抖动限制的组播路由问题,提出了基于混沌神经网络的组播路由优化算法。所提出的方法具有许多优良特性,即暂态混沌特性和平稳收敛特性,能有效地避免传统Hopfield神经网络极易陷入局部极值的缺陷。它通过短暂的倒分叉过程,能很快进入稳定收敛状态。通过计算机仿真,和其它的一些方法进行了对比,结果表明：该算法能根据组播应用对时延和时延抖动的要求,快速、有效地构造最优组播树,具有较强的实时性。     

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.     

基于暂态混沌神经网络的组播路由算法

讨论了高速包交换计算机网络中具有端到端时延的组播路由问题。首先给出了这类问题的网络模型及其数学描述，然后提出了基于暂态混沌神经网络的组播路由算法。实验结果表明，该算法能够快速有效地实现组播路由优化，并且计算性能及解的质量优于基于Hopfield神经网络的路由算法。     

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.     

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.     

一种新的多路径自组网路由算法

传统的单路径路由使自组网路由性能一直不能获得太大的突破。因此,设计有效的和稳定的多路径路由成为最受关注的问题。为此提出了一种新的多路径路由算法,其在路由发现阶段使用了一种新的多路径转发策略。在基于稳定性因子的基础上,该算法计算路径间海明距离并据此选择多条相似的稳定不相交多路由,从而进一步提高该路由算法的性能。模拟结果显示,与经典的多路径路由相比较,该算法是一个有效的多路径自组网路由算法。     

基于量子粒子群算法的组播路由优化

不确定网络性能参数下的多约束QoS组播路由优化已成为安全组播领域以及下一代Internet和高性能网络的一个重要研究课题。多约束QoS组播路由优化是NP-完全的多目标优化问题。提出了一个新的量子粒子群算法,其具有收敛速度快、全局性能好等特点。通过应用该算法求解多约束QoS组播路由优化问题的仿真实现,结果表明,该算法取得了较好的效果。     

A novel optimization-based bandwidth-aware minimum power multicast routing algorithm in green wireless networks

Multicast routing in wireless networks that possess the wireless multicast advantage could significantly reduce the power and energy consumption. However, this kind of multicast routing that only addresses the transmission radius coverage might not be able to meet the bandwidth requirement of the users. As a result, additional transmissions are required to incur more energy consumption and carbon dioxide emissions that make existing algorithms not applicable to bandwidth constrained applications. In this paper, for the first time, we address the bandwidth aware minimum power multicast routing problem in wireless networks where the objective function is to minimize the total power consumption subject to the users?? bandwidth requirements. This problem is a challenging cross-layer design problem that requires seamless and sophisticated integrated design in the network layer (multicast routing) and physical layer (bandwidth-aware wireless transmission and power control). We first formulate this problem as a mixed integer linear programming problem and then propose a Lagrangian relaxation based algorithm to solve this problem. Numerical results demonstrate that the proposed approach is a sound green networking algorithm that outperforms the existing power efficient multicast routing approaches under all tested cases, especially in large bandwidth request, fine radius granularity, large group size and sparse network.     

在线多点广播路由的动态方法探讨

多点广播是网络支持多媒体业务的关键技术之一。在线多点广播问题是指组中的成员加入或离开后多点广播路由树的更新问题。本文以服务质量（QoS)指标中的带宽和时延为优化选路准则，提出了一种受限的动态多点广播路由算法，仿真结果证明了该算法比传统算法更简洁。     

Constructing Multicast Routing Tree for Inter-cloud Data Transmission: An Approximation Algorithmic Perspective

Networking plays a crucial role in cloud computing especially in an inter-cloud environment, where data communications among data centers located at different geographical sites form the foundation of inter-cloud federation. Data transmissions required for inter-cloud federation in the complex inter-cloud networking system are often point-to-multi points, which calls for a more effective and efficient multicast routing algorithm in complex networking systems. In this paper, we investigate the multicast routing problem in the inter-cloud context with K constraints where K ≥ 2. Unlike most of existing algorithms that are too complex to be applied in practical scenarios, a novel and fast algorithm for establishing multicast routing tree for inter-clouds is proposed. The proposed algorithm leverages an entropy-based process to aggregate all weights into a comprehensive metric, and then uses it to search a multicast tree (MT) on the basis of the shortest path tree (SPT). We conduct complexity analysis and extensive simulations for the proposed algorithm from the approximation perspective. Both analytical and experimental results demonstrate that the algorithm is more efficient than a representative multi-constrained multicast routing algorithm in terms of both speed and accuracy, and thus we believe that the proposed algorithm is applicable to the inter-cloud environment.      

基于相关因子的节点不相交的Ad Hoc多路径路由算法

多路径路由算法可以均衡负载、提高可靠性，但是Ad Hoc网络的无线多播特性（WMA）使得多路径数据传输存在严重的；中突隐患，即便是节点不相交的多路径，以并发的方式来进行数据传输的效率并没有理论上的高．为此本文提出基于相关因子的节点不相交的多路径路由算法（NDCF），该算法引入相关因子来衡量多条节点不相交路径以并发的方式进行数据传输时发生；中突的可能性的大小，从而选择冲突可能性最小的节点不相交路径．仿真结果表明，NDCF算法可明显提高数据包的投递率．降低端到端的传输时延．     

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

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

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.     

A theory of deadlock-free adaptive multicast routing in wormholenetworks

A theory for the design of deadlock-free adaptive routing algorithms for wormhole networks, proposed by the author (1991, 1993), supplies sufficient conditions for an adaptive routing algorithm to be deadlock-free, even when there are cyclic dependencies between channels. Also, two design methodologies were proposed. Multicast communication refers to the delivery of the same message from one source node to an arbitrary number of destination nodes. A tree-like routing scheme is not suitable for hardware-supported multicast in wormhole networks because it produces many headers for each message, drastically increasing the probability of a message being blocked. A path-based multicast routing model was proposed by Lin and Ni (1991) for multicomputers with 2D-mesh and hypercube topologies. In this model, messages are not replicated at intermediate nodes. This paper develops the theoretical background for the design of deadlock-free adaptive multicast routing algorithms. This theory is valid for wormhole networks using the path-based routing model. It is also valid when messages with a single destination and multiple destinations are mixed together. The new channel dependencies produced by messages with several destinations are studied. Also, two theorems are proposed, developing conditions to verify that an adaptive multicast routing algorithm is deadlock-free, even when there are cyclic dependencies between channels. As an example, the multicast routing algorithms of Lin and Ni are extended, so that they can take advantage of the alternative paths offered by the network     

A Novel Gradient Boosted Energy Optimization Model (GBEOM) for MANET

Mobile Ad Hoc Network (MANET) is an infrastructure-less network that is comprised of a set of nodes that move randomly. In MANET, the overall performance is improved through multipath multicast routing to achieve the quality of service (quality of service). In this, different nodes are involved in the information data collection and transmission to the destination nodes in the network. The different nodes are combined and presented to achieve energy-efficient data transmission and classification of the nodes. The route identification and routing are established based on the data broadcast by the network nodes. In transmitting the data packet, evaluating the data delivery ratio is necessary to achieve optimal data transmission in the network. Furthermore, energy consumption and overhead are considered essential factors for the effective data transmission rate and better data delivery rate. In this paper, a Gradient-Based Energy Optimization model (GBEOM) for the route in MANET is proposed to achieve an improved data delivery rate. Initially, the Weighted Multi-objective Cluster-based Spider Monkey Load Balancing (WMC-SMLB) technique is utilized for obtaining energy efficiency and load balancing routing. The WMC algorithm is applied to perform an efficient node clustering process from the considered mobile nodes in MANET. Load balancing efficiency is improved with a higher data delivery ratio and minimum routing overhead based on the residual energy and bandwidth estimation. Next, the Gradient Boosted Multinomial ID3 Classification algorithm is applied to improve the performance of multipath multicast routing in MANET with minimal energy consumption and higher load balancing efficiency. The proposed GBEOM exhibits ∼4% improved performance in MANET routing.