无阻塞Clos-Type网上的多源点多播

在并行和分布式环境中 ,提供无阻塞的多对多通信是至关重要的 .Clos- Type网络能很好地满足这些要求 ,因此得到广泛的应用 .但是目前对于这类网中的多源点多播 ,通常的办法是通过对输入端的请求逐个进行一到多播送的方式来实现 ,这样的方式算法效率较低 ,在 N× N的网络中时间复杂度达到Θ (N3/2 ) ,其中 N为网络输入端的总数 .文章主要研究的是 Clos- Type网上进行多源点多播的充分条件 ,并且通过引入分组、竞争互斥等机制 ,在中间级开关数目数量级不变的情况下使路由算法的时间复杂度降低至 :Θ N log Nloglog N2 log N ,从而在 Clos-Type网络上以较低的时间复杂度无冲突地实现了多源点多播     

严格无阻塞多播三级Clos网的优化

如何在严格无阻塞情况下保持最低的硬件代价,是多播三级Clos网设计中的一个重要问题.提出一种优化网络硬件代价的方法,分别给出了在没有多播受限和中间级多播受限两种情况下,严格无阻塞多播三级Clos网硬件代价的最优值.分析表明,优化后网络的硬件代价得到了有效降低,在某些情况下甚至低于广义无阻塞网.同时,与广义无阻塞网相比,该网络无需特定的路由算法就能始终保持严格无阻塞状态,在一定程度上降低了时间复杂度.     

基于二进制寻路法和多Omega网络的自路由无阻塞多级网

提出了一种可以无阻塞地传输其输入与输出间任意多播信号的新型自路由无阻塞多级网。该网络采用了循环重建法,以二进制扩散概念为基础。它由一个二进制扩散网络和两个二分之一大小的多播路由网络循环构建而成。多播信号由第一个Omega网复制并二分扩散到输出端口,进入N×N的Omega×Omega-1网络,再进入紧随其后的N/2×N/2的Omega×Omega-1网络……。每个Omega×Omega-1网络负责依照目的地址的有效标志位将输入置换到输出的上半部分和下半部分,再分别进入上下两个子Omega×Omega-1网络中做同样的处理,如此类推,直到全部地址有效位处理完毕,从而完成自路由无阻塞的多播传输。由于各大小不等的Omega×Omega-1网络皆可并行设置和并行路由,故此种新型多Omega网络的设置时间为O(NlogN),路由时间为O(log2N),硬件代价则为O(Nlog2N)。它比现行已知的多播网络设计具有较优的代价。     

一种新型的可重排多播网络

在并行分布式系统中，多播操作（包括一对多播送和多源点多播）是一种常见的操作，关于多播操作（尤其是多源点多播）的研究是一个有一定难度，但又具有重要应用价值的问题，也是目前升级互连网络研究领域中的一个热门课题，已有的关于多播的成果大多只针对现有的多级网络，并且一般只能实现单个多播。Yang在[3]中针对多源点多播的并发。提出了一种新的多播网络，硬件复杂度为O（Nlog^2N).本文提出了一种基于Omega网的多播网络（5－Omega网），通过重排各级开关的状态，可以并发的实现任意的多源点多播，所需开关元件总数为5／2NlongN,与Yang提出的多播网络相比，硬件代价小得多，同时，5－Omega网上的多播路由时间复杂度能达到O（NlogN)，在相关的成果中也算是最优的，并且由于Omega网的结构较为简单，这种网的硬件集成也非常容易，因此更具有实用价值，在这种网络的构造基础上，还提出了一种新的多播网络模型，为以后设计多播网络提供了一种参考方法。     

多播3-Omega交换网的设计思想

阐述了具有最佳硬件复杂度且可无阻地在输入/输出间传输任意多播信号的多播3-Omega网的设计思想，设计理念可表述为“置换-复制-置换”，组成形式为“Omega-1+Omega+Omega-1”。它具有O(nlogn)的硬件代价，存储空间和时间复杂度均为O(nlogn)，连接建立时间为(logn)，传输延迟O(logn)，符合Shannon的硬件代价极限标准，具有良好的可实现性。     

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

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

基于多QoS约束的多播路由算法研究

论文讨论了具有延迟、带宽和低代价等多QoS约束的多播路由算法，提出了适应于研究QoS多播路由的网络模型，并给出了一种具有多QoS约束的动态多播路由算法，分析了算法的复杂度。仿真实验证明，该算法是稳定有效的。它能够在满足多约束的情况下，使多播树的代价优化。     

基于优先级的动态分层应用层多播模型

应用层多播(ALM)作为IP多播的替代在互联网中得到广泛的应用。提出一个新的基于优先级的动态分层应用层多播模型CDMP(The Classified Dynamic Model Based on the Priority in Application-Level Multicast),模型通过对不同性质的结点的分层来搭建整个架构,通过分域将性质接近的结点放在一起以保证数据传输的效率和数据共享的公正性,并且减少了结点寻找路由的代价,加快了当结点失败时的路由修复速度。通过分析和仿真实验证明,CDMP协议具有良好的上述性质。     

一个快速的时延有界低代价多播路由算法

基于ＱｏＳ的多播路由算法需要在满足每个个体ＱｏＳ需求的同时,又能高效管理网络资源,提出了一种满足端端时延限制的低代价多播路由算法。算法使用一个修改的Ｓｔｅｉｎｅｒ树近似算法先构建时延有界的低代价多播树,再通过最小时延路径与其它尚不在多播树的且结点相连。     

基于斐波那契序列的多播算法

该文提出了一种基于斐波那契序列的多播算法 ,并在 log P模型 [1 ] 下对算法的性能进行了分析 .log P模型是一种广泛使用的并行计算模型 ,它利用 L,o,g,P四个参数来分别表示发送一条消息的等待时间或最大延迟、处理器的开销、源结点发送消息的时间间隔、处理器 /存储器模块数 .在 log P模型下 ,该文所述的基于斐波那契序列的多播算法的时间复杂度为 0 .72 0 2 2· log2 K· (g m ax{ L 2· o,2· g} ) ,而传统的采用均匀二分的多播算法时间复杂度为 log2 K· (L 2· o) ,其中 K为结点数 .当 g 0 .3884· (L 2· o)时 ,基于斐波那契序列的多播算法性能将优于采用均匀二分策略的多播算法 .由于实际情况中 L 2 o g,因此 ,基于斐波那契序列的多播算法性能更优 .实验结果也验证了这一结论     

Suboptimal network coding subgraph algorithms for 5G minimum-cost multicast networks

To reduce the transmission cost in 5G multicast networks that have separate control and data planes, we focus on the minimum-power-cost network-coding subgraph problem for the coexistence of two multicasts in wireless networks. We propose two suboptimal algorithms as extensions of the Steiner tree multicast. The critical 1-cut path eliminating (C1CPE) algorithm attempts to find the minimum-cost solution for the coexistence of two multicast trees with the same throughput by reusing the links in the topology, and keeps the solution decodable by a coloring process. For the special case in which the two multicast trees share the same source and destinations, we propose the extended selective closest terminal first (E-SCTF) algorithm out of the C1CPE algorithm. Theoretically the complexity of the E-SCTF algorithm is lower than that of the C1CPE algorithm. Simulation results show that both algorithms have superior performance in terms of power cost and that the advantage is more evident in networks with ultra-densification.     

应用层多播协议研究

应用层多播不需要对现有网络基础结构做任何修改,不需要路由器支持,在虚拟叠加网的基础上由参与多播的端系统完成包的复制、路由计算、转发等功能,从而能方便、灵活地在因特网上进行部署。本文将按照树优先、网优先和层次结构三种应用层多播叠加网拓扑构建方式对应用层多播协议进行讨论。     

一种三层以太网交换机的组播方案

介绍一款自主研发的三层以太网交换机SW224的组播方案的设计与实现．针对我们的IP宽带社区接入网的应用要求，将三层以太网交换机的二层域组播和三层域组播有机地结合起来，以更为灵活的方式实现组播功能，并利用交换机的硬件支持．通过优化驱动算法等手段保证IP组播的服务质量．     

Adaptive binary sorting schemes and associated interconnectionnetworks

Many routing problems in parallel processing, such as concentration and permutation problems, can be cast as sorting problems. In this paper, we consider the problem of sorting on a new model, called an adaptive sorting network. We show that any sequence of n bits can be sorted on this model in O(lg² n) bit-level delay using O(n) constant fanin gates. This improves the cost complexity of K.E. Batcher's binary sorters (1968) by a factor of O(lg² n) while matching their sorting time. The only other network that can sort binary sequences in O(n) cost is the network version of columnsort algorithm, but this requires excessive pipelining. In addition, using binary sorters, we construct permutation networks with O(n lg n) bit-level cost and O(lg³ n) bit-level delay. These results provide the asymptotically least-cost practical concentrators and permutation networks to date. We note, of course, that the well-known AKS sorting network has O(lg n) sorting time and O(n lg n) cost, but the constants hidden in these complexities are so large that our complexities outperform those of the AKS sorting network until n becomes extremely large     

Communication reduction in multiple multicasts based on hybrid static-dynamic scheduling

This paper presents a novel approach to reducing the communication costs incurred when performing multiple multicasts on wormhole routed two-dimensional mesh multiprocessor systems. Both unicast and path-based implementations of multicasting incur communication costs due to the inherent message passing and contention for network resources. The start-up time dominates the transmission time when the data volume is small. However, in the presence of multiple multicasts when the data volume is very large, the communication delays due to message blocking and resource contention become very significant. Because of this, we present a hybrid static-dynamic technique to reduce the communication costs incurred when performing multiple multicasts on wormhole routed direct networks. This technique requires a focus on ordering and routing information for the individual message transmissions. At compile time, each message is assigned a priority using the recently developed collision graph model. Then at runtime these priorities are used to arbitrate the message transmissions. As a base, dimension-ordered routing is used. However, to further reduce the communication costs, some messages will be rerouted. This technique is useful either as a stand-alone algorithm or as an embedded procedure into existing algorithms. Furthermore, the techniques can be applied to higher dimension direct networks. For a single multicast, our work performs as well as conventional methods. For multiple multicasts, results show that our approach provides significant improvement over baseline techniques.     

Ad hoc网络中基于MCDS构建延迟定界组播转发结构*

根据无线信号传播方式的特殊性,重新定义了无线组播路由中的代价和时延函数,基于图论中最小连通支配集（MCDS）理论,提出的基于图论中点着色思想的时延定界组播转发结构的构建方法,通过求解MCDS来实现构建最小代价组播路由结构的目的,提出了组播路由时延定界的概念,并在该约束下构建MCDS。理论推导证明了该算法的正确性,与同类算法相比,较低的近似比证明了该算法的有效性,同时具有O(n)的时间复杂度和O(n)的消息复杂度,进一步证明了其高效性,具有适应于灵活多变的Ad hoc网络的优势。     

基于遗传算法的无线网状网QoS多播路由算法

探讨了基于遗传算法的无线网状网QoS多播路由算法,选用边集表示方式对多播树进行编码,其空间复杂度为O(N),给出了该编码方式下的初始种群生成算法RandWalkMT,同时对传统的遗传操作进行改进使子代个体中不会产生非法多播树,从而避免了复杂的惩罚机制或多播树修复算法。实验表明该算法收敛快且性能较好。     

Nonblocking k-fold multicast networks

Multicast communication involves transmitting information from a single source to multiple destinations and is a requirement in high-performance networks. Current trends in networking applications indicate an increasing demand in future networks for multicast capability. Many multicast applications require not only multicast capability, but also predictable communication performance such as guaranteed multicast latency and bandwidth. In this paper, we present a design for a nonblocking k-fold multicast network, in which any destination node can be involved in up to k simultaneous multicast connections in a nonblocking manner. We also develop an efficient routing algorithm for the network. As can be seen, a k-fold multicast network has significantly lower network cost than that of k copies of ordinary 1-fold multicast networks and is a cost effective choice for supporting arbitrary multicast communication.     

Ad Hoc网络QoS多播路由协议

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

A note on distributed multicast routing in point-to-point networks

The distributed algorithm for a multicast connection set-up, based on the ‘cheapest insertion’ heuristic, is reviewed. The multicast routing problem is translated into a Steiner tree problem in point-to-point networks where nodes have only a limited knowledge about the network. A solution is proposed in which the time complexity and the amount of information exchanged between network nodes are proportional to the number of members of the multicast group. The Steiner tree is constructed by means of a distributed table-passing algorithm. The analysis of the algorithm presented, backed up by simulation results, confirms its superiority over the algorithm based on ‘waving technique’.Scope and purposeMulticasting is a mechanism used in communication networks that allows distribution of information from a single source to multiple destinations. The problem of finding a multicast connection for a static group of communicating entities in connection-oriented point-to-point network can be formulated in graph theory as a minimum Steiner tree problem. Due to NP-completeness of the Steiner tree problem multicast, routing algorithms are based on heuristics. The diversity of network environments and the lack of centralised information about network topology require an effective distribution of the multicast routing algorithms among the network nodes. This article presents an alternative to the distributed algorithm proposed by Rugelj and Klavzar that implements the same heuristics for the construction of a minimum cost multicast connection in point-to-point networks. The present algorithm constitutes a substantial improvement over that previously proposed with regard to running time and the amount of the information exchanged between network nodes.