Optimal State Allocation for Multicast Communications With Explicit Multicast Forwarding

In this paper, we propose a scalable and adaptive multicast forwarding mechanism based on explicit multicast (Xcast). This mechanism optimizes the allocation of forwarding states in routers and can be used to improve the scalability of traditional IP multicast and source-specific multicast. Compared with previous work, our mechanism needs fewer routers in a multicast tree to store forwarding states and therefore leads to a more balanced distribution of forwarding states among routers. We focus on two problems and formulate each of them as an optimization problem. The first problem, referred to as minstate, minimizes the total number of routers that store forwarding states in a multicast tree. The second problem, referred to as balancestate, minimizes the maximum number of forwarding states stored in a router for all multicast groups, which is proved to be an NP-hard problem. We design a distributed algorithm that obtains the optimal solution to the first problem and propose an approximation algorithm for the second problem. We also prove that the approach adopted by most existing works to allocate forwarding states in the branching routers of a multicast tree is a special case of our mechanism. The simulation results show that the forwarding state allocation provided by previous work is concentrated on the backbone routers in the Internet, which may cause the scalability problem. In contrast, our mechanism can balance forwarding states stored among routers and reduce the number of routers that store the forwarding states for a multicast tree.     

基于接口格式的稀疏组播转发状态压缩方案

组播转发状态随组播组个数线性增长导致组播路由协议的扩展性较差．分析了已有的用于稀疏模式组播的转发状态组内压缩方案存在的问题,提出了一个新的压缩方案．该方案根据组播树上分支路由器的位置和个数,动态调整组播转发表项中各个接口的格式,进一步减少了转发状态占用的存储空间．     

组播路由协议HBH的分析与研究

组播路由协议HBH具有良好的可扩展性且内存需求低,但其对路由路径变化的适应能力及本地组播效率有待改进。该文分析了HBH协议产生上述问题的原因,提出新的组播转发树构建方式,通过模拟试验对其进行验证。结果表明,改进的HBH协议对路由路径变化具有良好的适应能力,并在本地具备较好的组播效果。     

HIP组播路由机制研究与实现

通过对HIP(Host Identity Protocol)协议和HIP组播模型的深入研究,提出一种新的HIP组播路由机制。新机制不改变HIP组播模型中对组播树的创建和维护方式,引入组地址变量进行路由转发,降低了原模型中路由处理的复杂度。使用Linux平台模拟HIP组播路由器并实现相关协议。理论分析和实验表明,新机制提高了HIP组播数据的传输和转发效率,降低了HIP安全组播模型中组播路由器的部署难度。     

解决聚合组播的自适应拉格朗日松弛算法

组播在数据转发上有明显的优势，但是当网络中的组播组很多时，转发状态大大增加, 管理组播组需要消耗大量的资源和控制开销。聚合组播是一种新颖的减少组播状态的方法，它使网络中能够复合的组播组共用同一棵分布树，从而减少了组播树上核心路由器的开销。聚合组播问题实质上是最小集合覆盖问题，可以用自适应拉格朗日松弛算法来解决。与传统的贪婪算法相比，这个算法能得到全局最优解的可能性更大，并且更加有效地提高了聚合度，减少了组播转发状态。     

遗传算法在聚合组播问题优化中的应用

IP组播至今仍没有在Internet上被广泛应用,其中一个重要原因是组播转发状态的扩展性问题。聚合组播是一种减少组播转发状态的新技术,其主要目标是使网络中能够复合的组播组共用一棵组播分发树,从而减少转发状态,提高网络性能。采用遗传算法求解聚合组播问题。仿真结果表明,该算法对聚合组播问题有巨大的优化作用。     

基因池操作遗传算法的应用层组播路由优化

在应用层组播系统中，负责数据转发的终端节点不具备线速转发能力，较重的转发负载会引起拥塞。以拥塞节点为根的整个子路由树将与源节点失联。为解决由拥塞导致应用层组播稳定性差的问题，将构造最优组播树的过程抽象为有度约束的最小代价Steiner树问题。提出了一种用于构造节点转发能力受限应用层组播树的遗传算法，算法以组播树上各节点的直接前驱对其进行遗传表达，便于节点出度的统计。为使遗传操作适用于直接前驱编码，引入了“基因池”的概念并以此为基础实现了交叉与变异。针对度约束导致产生非可行解的问题，提出将组播树对度约束的超出量作为一个新的优化目标，从而以多目标优化的方式得到Pareto前沿，并从Pareto前沿上截取满足度约束的解作为最终输出，避免了使用惩罚函数法的求得非可行解的风险。仿真实验表明，提出的遗传算法能够构造节点转发能力受限的应用层组播路由树，具有良好的求解可靠性。     

一种基于SSM的多源组播路由协议

为满足参与方同时为收发方的组播通信模式,该文提出了一种新的基于特定源组播的多源组播路由协议SSM-MSM,该协议利用特定源组播形成的单向组播转发树维护一个与之并行的用于多方通信的双向转发树,其路由状态、树建立和控制消息开销和组播包转发时延较小,可综合几种已有的基于SSM多方通信方案的优势。     

按需分枝组播

在分析总结目前IP组播路由研究的主要成果基础上,提出了一个新的组播路由方案,按需分枝组播.它采用了一种全新的组播树维护方式,即组播树由树上的部分节点(关键节点)维护,不同于现有的组播树由所有树上节点维护的方式,从而节省了网络资源.     

用于超大Infiniband网络的负载均衡多播路由

高性能计算中,硬件支持的多播操作对应用程序性能具有至关重要的影响.Infiniband网络中现有的两类多播路由算法中,MINIHOP-MC未考虑路由均衡性问题,导致链路edge forwarding index(EFI)指数很大,严重影响多播消息性能;SSSP-MC虽然部分考虑了路由均衡性问题,但其运行时间很长,不能满...     

Ad hoc网络中基于标号的组播路由算法

针对Ad hoc网络中最小带宽消耗组播路由问题,给出一个基于标号优化的启发式算法(LOHA),介绍标号规则及修改节点间邻接关系规则,通过修改组播树中节点的标号来减少树中的转发节点数,从而最小化带宽消耗。该算法的时间复杂度为O(n3),从转发节点个数和平均跳数2个方面比较LOHA及广度优先搜索算法所生成的组播树。实验结果表明,LOHA得到的组播树带宽消耗较少。     

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

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

基于单密钥的特定源多播安全机制

由于多播网络体系结构中多播数据发送不是点对点的方式,因此传统的端到端的安全不适合多播网络体系结构.在多播数据发送前,多播数据的接收者只要公布自己的公/私钥对中的公钥以及在发送加入组成员消息时告诉多播数据的发送者它的一个密钥,而无须知道多播源发送数据的加密密钥;多播数据发送者在每一次发送多播数据时,随机地选出一个密钥对发送的信息进行加密,但该密钥不是直接告诉多播数据接收者;接收者在进行解密数据时,首先必须利用自己的私钥以及发送给多播数据发送者的密钥求得加密数据的密钥,然后才能进行原文解密.     

Scalable datacenter multicast using in-packet bitmaps

Scalability is a key issue in datacenter multicast as it needs to support a large number of groups in commodity switches with limited fast memory. Previous in-packet Bloom filter-based datacenter multicast schemes have been proposed to address the scalability issue. They encode a multicast tree in a Bloom filter carried in each packet. However, these schemes induce high bandwidth overhead due to the false positives inherent in Bloom filters, and cannot scale well to the increasing variety of group sizes. In this paper, we propose an in-packet bitmap-based approach towards scalable datacenter multicast, improving the bandwidth efficiency. We use a bitmap to encode switch ports of a multicast tree in the packet header, eliminating false positive forwarding. In addition, we use a clustered Golomb coding method to compress in-packet bitmaps for further reducing the bandwidth overhead. Experimental results on simulations and a Click-based switch prototype demonstrate that our scheme achieves up to several orders of magnitude reductions in bandwidth overhead compared to previous schemes.     

Cored-Based Tree with Forwarding Regions (CBT-FR); A Protocol for Reliable Multicasting in Mobile Ad Hoc Networks

In this paper we propose a new protocol for reliable multicast in a multihop mobile radio network. The protocol is reliable, i.e., it guarantees message delivery to all multicast nodes even when the topology of the network changes during multicasting. The proposed protocol uses a core-based shared tree. The multicast tree may get fragmented due to node movements. The notion of a forwarding region is introduced which is used to glue together fragments of multicast trees. The gluing process involves flooding the forwarding region of only those nodes that witness topology change due to node mobility. Delivery of multicast messages to mobile nodes is expedited through (i) pushing the message by witness nodes in their forwarding regions and (ii) pulling messages by a mobile node during (re)joining process. Hence, the protocol conserves network bandwidth by using a combination of the push–pull approach and by restricting flooding only to the essential parts of the network that are affected by topology change.  We develop a theoretical model to compute the probability of packet loss (as a function of the mobility rate) for our proposed scheme compared to the the core-based tree protocol (CBT); we also evaluate the effectiveness of forwarding regions as compared to traditional flooding. Our analysis shows that the proposed scheme significantly outperforms CBT.     

主动层次多目通信路由模型

许多应用需要IP多目通信.在Internet大规模应用IP Multicast时,有效的路由是关键.这样的多目路由协议必须是有效的、可伸缩的和增量可配置的.但是传统的Internet路由对性能是不敏感的,不能平衡负载和处理拥塞.现有的大多数多目通信路由协议不仅负责数据转发,还负责路由树的构造,这给路由器带来了极大的复杂性,而且协议的配置是手动的、费时费钱的工作.该文提出一个主动层次式Multicast路由的体系结构,采用主动网络技术将多目通信路由协议的数据转发和控制机制分开,根据链路的状态信息用主动报文控     

基于加权选择函数的应用层组播路由算法

尽管IP组播是一种有效的多点通信方式,但在Internet范围内部署IP组播有着许多障碍.应用层组播可以在网络层不支持组播的情况下快速提供组播服务.提出了一种基于加权选择函数的分布式应用层组播路由算法,它在构造组播树时,能在尽量减少局部的三角路由同时兼顾节点之间的邻近性.模拟实验结果证明了该方案的有效性.     

动态优化的分布式组播路由算法

为了在真实的网络环境中寻找一棵延迟受限、耗费最小的组播转发树,以便更好地支持组播通信,提出了一个可以动态优化的分布式组播路由算法,该算法利用蚁群思想解决上述组播路由问题.由于不同代的蚂蚁之间可以通过信息素来实现间接通信,而信息素又是一种可以反映环境变化的媒介质,因此,该算法能够根据网络环境的变化及时做出调整.结合实际的网络拓扑,进行仿真实验,实验结果表明,通过蚂蚁一代代的进化,算法可以找到一棵满足延迟约束并且耗费尽可能小的组播树.     

一种非随机生成聚合组播路由转发表的算法

随着组播技术的应用,基于组播源地址和组播组地址进行二元组表项存储的组播路由转发表将呈爆炸式膨胀,内存消耗随之急剧增加,最终将成为组播路由转发的瓶颈之一.将组播路由转发表进行无类域间路由聚合成为一种有效的解决组播路由转发表爆炸式膨胀的一种方式.如何获取数据集是聚合组播路由表研究课题中,必然要解决的问题.由于组播路由转发表的聚合目前尚处在研究中,很难在网络上获取具有一定代表性的聚合组播路由转发表,而高性能路由算法的设计和实现与实际路由表的结构有很大关系.根据组播主干网组播IP地址分布的特性和规律,采取赌轮选择算法,非随机生成聚合组播路由转发表的方法,为仿真组播路由转发表和研究组播路由提供了依据.目前,应用聚合组播路由表算法的研究已取得了理想效果.     

Design and analysis of a stable set-up protocol for transcoding multicast trees in active networks

Based on active networking, an advanced streaming service was designed to offer different formats of the same stream using a single multicast tree. To that end, the initial format of the stream that is sent into the tree is transcoded to the other requested formats in the nodes of the tree, based on application level functionality residing in these network nodes. To set up such a multicast tree (including the necessary forwarding state in the nodes) and to install the necessary functionality in the nodes, a number of tree set-up procedures were designed. In this paper, performance aspects of these procedures are investigated: the stability and consistency of the forwarding state during the set-up procedures and the influence of dynamic user behaviour on the multicast tree. This performance assessment is based on a thorough analysis of the different set-up procedures and on simulations of the procedures. Based on the analysis, it is seen that great care must be taken during the set-up procedures in order to avoid interference with the existing streams. Therefore, extensions for the procedures are proposed. Furthermore, the influence of dynamic user behaviour on session state and performance attributes is analysed.