加权的基于多播节点的多播路由算法

在许多多播应用中,降低多播树网络费用非常重要.本文提出了加权的基于多播节点的多播路由算法（WDDMC算法）.由于改变了DDMC（Destination-Driven routing for low-cost Multicast ）算法中的指示函数,适当降低了多播节点作为中间节点的优先级,提高非多播节点作为中间节点的优先级,从而使得多播树更接近最小Steiner树.在随机网络上的仿真结果表明,WDDMC算法的多播树网络费用优于DDMC算法.该算法的复杂度与DDMC算法完全相同.     

基于路径备用机制的应用层多播树重构方法

首先,将前向式树重构策略扩展应用于基于Chord的结构型多播树,提出了路径备用机制,该机制为多播树中每个节点预先寻找一条用于快速恢复与多播树连接的备用路径.接着,以路径备用机制为基础,进一步设计基于Chord的应用层多播协议ChordM-FR.仿真结果表明,ChordM-FR协议的多播树重构速度比采用后向式树重构策略的ChordM-SR协议平均快大约2.5倍.     

无线Ad Hoc网络Steiner树实现协议研究

针对无线Ad hoc网络多跳,拓扑结构随时可能动态变化,协作节点间数据传输需实时性强等问题,利用Netlog语言宣告声明最小Steiner树协议的构造算法方法适应解决。协议可快速构造一棵近似最小的Steiner树,每个节点独立运行声明Steiner树协议,构造Steiner节点间的虚拟全联通网络,在此网络上构造最小代价生成树;然后将此树的节点与边对应原网络的节点和边,继续构造最小代价生成树,最后将此树上的非Steiner节点的叶子节点删除,近似得到最小代价Steiner树,该方法在实验平台上得以验证,为无线移动网络中资源的选择利用提供了一种新的可尝试性的新方法。     

基于数字证书的树型结构安全多播方案

该文提出一种基于数字证书的安全多播方案，采用树型的多播拓扑结构。多播树中的每个节点都有一个标识其身份的数字证书，除了成员身份认证外，还可以安全地分发会话密钥和实现会话数据的认证，因而减少了多播群密钥管理的复杂度；由于采用分层的树型多播结构，成员加入和退出有了更大的可扩展性。     

CSM多播路由协议在移动环境中的改进

适用于视频会议与在线聊天室的CSM（Conference Steiner Multicast）协议，在支持移动主机时存在多播树切换频率过高，网络开销过大的问题。运用Range（服务范围）的概念，结合Mobile IP隧道技术，提出了一种改进的CSM协议－－RBCSM（Range Based CSM）协议。RBCSM协议在降低多播切换频率，节省网络带宽方面性能优越。同时由于运用了Mobile IP的隧道技术，还有进一步提高网络安全性的可能，最后，对CSM和RBCSM的多播树切换频率及多播树路径总长度两个性能指标进行了仿真模拟比较。     

支持延时约束的覆盖多播路由协议的研究

研究有度和延时约束的覆盖多播路由问题,提出了一个新的覆盖多播路由协议-延时受限的树协议(DBTP)。该协议采用分布式和树优先的策略,使多播组成员之间能自组织地构建一棵基于源的覆盖多播树。DBTP协议采用了一种新的启发式局部优化算法,通过调节启发因子,能灵活地在延时和代价之间进行折衷。仿真实验表明,无论在静态还是动态节点模型下,选择适当的启发参数,DBTP都能获得较高的节点接纳率。     

基于主动网络层次的多播体系结构

研究了多播路由协议及多播源分发数据报文的机制,提出一种新型的基于主动网络层次的多播体系结构,在自治系统AS中的分枝节点,亦可以根据该策略,构造以分枝节点为根的动态管理方式,从而可以动态地构造层次多播体系结构,在动态层次多播路由的具体实现中引入了agent和主动网络的概念,从而可以动态的加载多播路由,使得网络体系结构灵活与可编程.     

一种节点自分布最优Ad Hoc多播树及其应用

为无线单播模式设计的RTS/CTS信道握手机制不适用于多播模式,导致Ad hoc多播树节点易与隐藏终端发生冲突.通过提出m阶冲突域、节点在冲突域中的分布指标,结合无线网多播数据通信机制分析树节点所在m阶冲突域的冲突概率,进而得到节点自分布最优树的概念,并将它融入多播树的适应函数的设计中,淘汰不良树,优化树节点在m阶冲突域中的分布,在网络层形成一种预防机制,可降低隐藏终端冲突概率;应用于MAODV协议中,提高了MAODV的端到端数据分组平均投递率,这也能够为基于网的和混合式的其他类型MANETs多播路由协议的路由节点分布优化提供有价值的参考.     

BowCast：一种适应非对称链路延时网络的P2P多播路由协议

虽然IP多播的性能优势无可否认,但是它却面临着部署上的困难。近年来,P2P多播作为提供多播服务的另一可行途径正不断为人们所认可。研究非对称链路延时网络环境下P2P多播的路由问题,提出一个新的P2P多播路由协议：BowCast.该协议采用基于树（tree-based）的分布式路由策略,使多播组成员之间能自组织地构建一棵基于源的最小延时P2P多播树。BowCast主要利用范围受限的单向探测技术（BOW）来实现路由优化算法。BOW能提供端系统节点间的单向相对延时,无需全局的同步时钟。仿真实验表明,BowCast能很好地适应非对称链路延时环境。通过调节BOW的探测范围,BowCast能灵活地在路由性能和控制开销之间进行折中。     

基于部分网络编码的移动自组网实时多播协议研究

传统网络编码可以减少数据包的转发次数,但会造成数据包较大的延时,且容易造成网络的拥塞.本文提出一种基于部分网络编码的实时多播协议——PNCRM.该协议将部分网络编码与mesh的建立结合在一起,有效地减小了端到端的延时,并且改善了网络吞吐量性能.仿真结果表明,与PUMA或基于传统网络编码的实时多播协议相比,PNCRM更好地适应接收节点较多、动态性较大的环境,且在数据包投递率及端到端的延时方面有着显著的优势.     

共享路径优先组播路由算法

求解开销最小组播树在数学上归结为Steiner树问题,但由于寻找最优的Steiner树问题是NP-Complete问题,因此在组播应用中,采用启发式算法获得次优的组播树是常见的方法。该文提出了一种新的的启发式组播路由算法(Shared Path First Heuristic,SPFH)该算法在选择目的节点加入组播树时,既考虑到目的节点到树上的距离,又考虑到先加入的节点对后续加入节点的影响。算法从距离当前组播树近的目的节点中挑选节点加入组播树,选择的规则是,把能够减小其它目的节点加入组播树开销的节点先加入树。仿真结果表明,SPFH算法能找到开销接近于最优解的组播树。     

Distributed algorithms for multicast path setup in data networks

Establishing a multicast tree in a point-to-point network of switch nodes, such as a wide-area asynchronous transfer mode (ATM) network, can be modeled as the NP-complete Steiner problem in networks. In this paper, we introduce and evaluate two distributed algorithms for finding multicast trees in point-to-point data networks. These algorithms are based on the centralized Steiner heuristics, the shortest path heuristic (SPH) and the Kruskal-based shortest path heuristic (K-SPH), and have the advantage that only the multicast members and nodes in the neighborhood of the multicast tree need to participate in the execution of the algorithm. We compare our algorithms by simulation against a baseline algorithm, the pruned minimum spanning-tree heuristic that is the basis of many previously published algorithms for finding multicast trees. Our results show that the competitiveness (the ratio of the sum of the heuristic tree's edge weights to that of the best solution found) of both of our algorithms was, on the average, 25% better in comparison to that of the pruned spanning-tree approach. In addition, the competitiveness of our algorithms was, in almost all cases, within 10% of the best solution found by any of the Steiner heuristics considered, including both centralized and distributed algorithms. Limiting the execution of the algorithm to a subset of the nodes in the network results in an increase in convergence time over the pruned spanning-tree approach, but this overhead can be reduced by careful implementation     

Algorithms for delay constrained group multicast routing

Multicast routing allows network sources to use network resources efficiently by sending only a single copy of data to all group members. In the delay constrained group multicast routing problem (DCGMRP), every group member is also a source, and has an individual minimal delay and bandwidth requirement. The routing algorithm must, for each member of the group, construct a source‐based routing tree spanning all the other member nodes without exceeding the capacities of the traversed links, while satisfying the stated delay constraints. Previous work adopted the direct, intuitive approach by first creating a source‐based multicast tree independently for each member node, and then iteratively locating network links whose capacity constraint are violated and eliminating the violation by rerouting the trees. In this paper, we investigate a number of efficient and effective algorithms, DCGM _ IA ⁺, DCGM _ GR and DCGM _ CP , for solving DCGMRP and compare their performance with previous proposals. Through extensive experiments, our proposals are shown to outperform previous algorithms in constructing group multicast trees with low costs and high success ratios. Copyright © 2005 John Wiley & Sons, Ltd.     

Resource optimization in QoS multicast routing of real-time multimedia

We consider a network design problem, where applications require various levels of Quality-of-Service (QoS) while connections have limited performance. Suppose that a source needs to send a message to a heterogeneous set of receivers. The objective is to design a low-cost multicast tree from the source that would provide the QoS levels (e.g., bandwidth) requested by the receivers. We assume that the QoS level required on a link is the maximum among the QoS levels of the receivers that are connected to the source through the link. In accordance, we define the cost of a link to be a function of the QoS level that it provides. This definition of cost makes this optimization problem more general than the classical Steiner tree problem. We consider several variants of this problem all of which are proved to be NP-Hard. For the variant where QoS levels of a link can vary arbitrarily and the cost function is linear in its QoS level, we give a heuristic that achieves a multicast tree with cost at most a constant times the cost of an optimal multicast tree. The constant depends on the best constant approximation ratio of the classical Steiner tree problem. For the more general variant, where each link has a given QoS level and cost we present a heuristic that generates a multicast tree with cost O(min{logr,k}) times the cost of an optimal tree, where r denotes the number of receivers, and k denotes the number of different levels of QoS required. We generalize this result to hold for the case of many multicast groups.     

Restricted dynamic Steiner trees for scalable multicast in datagramnetworks

The paper addresses the issue of minimizing the number of nodes involved in routing over a multicast tree and in the maintenance of such a tree in a datagram network. It presents a scheme where the tree routing and maintenance burden is laid only upon the source node and the destination nodes associated with the multicast tree. The main concept behind this scheme is to view each multicast tree as a collection of unicast paths and to locate only the multicast source and destination nodes on the junctions of their multicast tree. The paper shows that despite this restriction, the cost of the created multicast trees is not necessarily higher than the cost of the trees created by other algorithms that do not impose the restriction and therefore require all nodes along the data path of a tree to participate in routing over the tree and in the maintenance of the tree     

CRAM: Cell Re-labeling At Merge-points for ATM multicast

Many distributed multimedia applications involve data delivery from a source to multiple destinations, the participating nodes forming a multicast group. In the naive solution, separate connections can be established from each source to other group members. However, a tree can be established for each source with the participants as the leaf nodes or just have one tree spanning all the participants. In this paper, we introduce a data forwarding model to support such shared multicast trees over the ATM networks called CRAM (Cell Re-labeling At Merge-points for ATM multicast). Our work allows VC merging in the MPLS architecture and supports recently proposed wide area multicast protocols (like CBT and PIM) in ATM networks. This revised version was published online in August 2006 with corrections to the Cover Date.     

Minimizing Intermediate Multicast routing for dynamic multi-hop ad hoc networks

A Minimizing Intermediate Multicast Routing protocol （MIMR） is proposed for dynamic multi-hop ad hoc networks. In MIMR, multicast sessions are created and released only by source nodes. In each multicast session process, the source node keeps a list of intermediate nodes and destinations, which is encapsulated into the packet header when the source node sends a multicast packet. Nodes receiving multicast packets decide to accept or forward the packet according to the list. Depending on topology matrix maintained by unicast routing, the shortest virtual hierarchy routing tree is constructed by improved Dijkstra algorithm. MIMR can achieve the minimum number of intermediate nodes, which are computed through the tree. No control packet is transmitted in the process of multicast session. Load of the network is largely decreased. Experimental result shows that MIMR is flexible and robust for dynamic ad hoc networks.     

A new heuristic algorithm for finding minimum‐cost multicast trees with bounded path delay

This article presents a new heuristic algorithm called DDBMA (Dynamic Delay Bounded Multicast Algorithm) to construct a minimum‐cost multicast tree. The heuristic depends on (1) bounded delay along paths from source nodes to each destination node; (2) minimum cost of the multicast tree; (3) dynamic multicast tree status which is maintained by updating the existing multicast tree when nodes in the network request to join or leave. Copyright © 1999 John Wiley & Sons, Ltd.     

Improved neural heuristics for multicast routing

Future networks must be adequately equipped to handle multipoint communication in a fast and economical manner. Services requiring such support include desktop video conferencing, tele-classrooms, distributed database applications, etc. In networks employing the asynchronous transfer mode (ATM) technology, routing a multicast is achieved by constructing a minimum cost tree that spans the source and all the destinations. When the network is modeled as a weighted, undirected graph, the problem is that of finding a minimal Steiner tree for the graph, given a set of destinations. The problem is known to be NP-complete. Consequently, several heuristics exist which provide approximate solutions to the Steiner problem in networks, We show how the random neural network (RNN) can be used to significantly improve the quality of the Steiner trees delivered by the best available heuristics which are the minimum spanning tree heuristic and the average distance heuristic. We provide an empirical comparison and find that the heuristics which are modified using the neural network yield significantly improved trees