基于SimCT的多播路由及故障恢复研究

在数据交换网络中,颜色树是一种通过节点不相交的多路径路由数据报文的有效方法。这种方法中组建两棵以某一节点为根节点的颜色树,即Red树和Blue树,网络中各节点到根节点的路径是节点不相交的。本文在分析和研究SimCT算法的基础上,提出了一种基于颜色树的多播树生成方法及单节点/链路故障的多播通信恢复方案。该方法根据SimCT算法构造的颜色树来组建一棵多播转发树,在多播树中单节点或单链路故障后,故障检测节点本地执行故障恢复方案,将受影响的故障节点的下游子树重新连接到多播树。仿真实验表明,本文所提出的多播树生成方案相比现有方案可以减少网络资源的浪费,并且故障恢复后的代价与原多播通信树相当。     

Distributed formation of core-based forwarding multicast trees in mobile ad hoc networks

A core-based forwarding multicast tree is a shortest path tree rooted at core node that distributes multicast packets to all group members via the tree after the packets are sent to the core. Traditionally, the bandwidth cost consumed by transmitting a packet from the core via the tree is evaluated by the total weights of all the edges. And, the bandwidth cost is minimized by constructing the multicast tree that has minimum total weights of edges to span all group members. However, when the local broadcast operation is used to multicast a packet, we found that the bandwidth cost is supposed to be evaluated by the total weights of all senders that include the core and all non-leaves. Since the multicast tree with the number of nodes greater than or equal to three has minimum bandwidth cost only when the core is not a leaf, it leads us to find the multicast tree with the minimum number of non-leaves when each sender node has a unit weight. However, no polynomial time approximation scheme can be found for the minimum non-leaf multicast tree problem unless P = NP since the problem is not only NP-hard but also MAX-SNP hard. Thus, a heuristic is proposed to dynamically reduce the number of non-leaves in the multicast tree. Experimental results show that the multicast tree after the execution of our method has smaller number of non-leaves than others in the geometrically distributed network model.     

Stateless overlay multicast with in-packet bloom filters

Due to the difficulty of deploying Internet protocol (IP) multicast on the Internet on a large scale, overlay multicast has been considered as a promising alternative to develop the multicast communication in recent years. However, the existing overlay multicast solutions suffer from high costs to maintain the state information of nodes in the multicast forwarding tree. A stateless overlay multicast scheme is proposed, in which the multicast routing information is encoded by a bloom filter (BF) and encapsulated into the packet header without any need for maintaining the multicast forwarding tree. Our scheme leverages the node heterogeneity and proximity information in the physical topology and hierarchically constructs the transit-stub overlay topology by assigning geometric coordinates to all overlay nodes. More importantly, the scheme uses BF technology to identify the nodes and links of the multicast forwarding tree, which improves the forwarding efficiency and decreases the false-positive forwarding loop. The analytical and simulation results show that the proposal can achieve high forwarding efficiency and good scalability.     

Family ACK tree (FAT): supporting reliable multicast in mobile ad hoc networks

A new protocol, called family ACK tree (FAT), is proposed to support a reliable multicast service for mobile ad hoc networks. For each reliable multicast protocol, a recovery scheme is used to ensure end-to-end delivery of unreliable multicast packets for all group members. FAT employs a tree-based recovery mechanism that localizes ACKs and retransmissions to avoid feedback implosion. To cope with node movements, FAT constructs an ACK tree on which each node maintains reachability information to three generations of nodes on the ACK tree. When a tree is fragmented due to a departed node, the fragments are glued back to the tree using the underlying multicast routing protocol. FAT then adopts an adaptive scheme to recover missed packets that have been multicast to the group during fragmentation and are not repaired by the new reliability agent. We have conducted simulations to compare the performance of FAT with existing solutions. The results show that FAT achieves better performance for the provision of reliable service in ad hoc networks, in terms of reliability, scalability, and delivery efficiency.     

A Framework for Mitigating Attacks Against Measurement-Based Adaptation Mechanisms in Unstructured Multicast Overlay Networks

Many multicast overlay networks maintain application-specific performance goals by dynamically adapting the overlay structure when the monitored performance becomes inadequate. This adaptation results in an unstructured overlay where no neighbor selection constraints are imposed. Although such networks provide resilience to benign failures, they are susceptible to attacks conducted by adversaries that compromise overlay nodes. Previous defense solutions proposed to address attacks against overlay networks rely on strong organizational constraints and are not effective for unstructured overlays. In this work, we identify, demonstrate and mitigate insider attacks against measurement-based adaptation mechanisms in unstructured multicast overlay networks. We propose techniques to decrease the number of incorrect adaptations by using outlier detection and limit the impact of malicious nodes by aggregating local information to derive global reputation for each node. We demonstrate the attacks and mitigation techniques through real-life deployments of a mature overlay multicast system.      

Resilient multicast using overlays

We introduce Probabilistic Resilient Multicast (PRM): a multicast data recovery scheme that improves data delivery ratios while maintaining low end-to-end latencies. PRM has both a proactive and a reactive components; in this paper we describe how PRM can be used to improve the performance of application-layer multicast protocols especially when there are high packet losses and host failures. Through detailed analysis in this paper, we show that this loss recovery technique has efficient scaling properties-the overheads at each overlay node asymptotically decrease to zero with increasing group sizes. As a detailed case study, we show how PRM can be applied to the NICE application-layer multicast protocol. We present detailed simulations of the PRM-enhanced NICE protocol for 10 000 node Internet-like topologies. Simulations show that PRM achieves a high delivery ratio (>97%) with a low latency bound (600 ms) for environments with high end-to-end network losses (1%-5%) and high topology change rates (5 changes per second) while incurring very low overheads (<5%).     

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.     

Ad hoc mobile multicast routing using the concept of long‐lived routes

Mobile ad hoc networks are recognized by their abilities to form, sustain, and deform networks on‐the‐fly without the need for any pre‐established and fixed infrastructures. This wireless multi‐hop technology requires adaptive networking protocols with low control overhead and low power consumption to operate efficiently. Existing research so far are mainly concerned with unicast routing for ad hoc mobile networks. There is a growing interest in supporting multicast communication in an ad hoc mobile environment. In this paper, the associativity‐based ad hoc multicast (ABAM) routing protocol is proposed. The concept of association stability is utilized during multicast tree discovery, selection, and reconfiguration. This allows routes that are long‐lived to be selected, thereby reducing the frequency of route reconstructions. ABAM employs a localized route reconstruction strategy in response to migrations by source, receiver, and tree nodes. It can repair an affected subtree via a single route reconstruction operation. ABAM is robust since the repair can be triggered by a node in the tree or by the migrated node itself. ABAM is also capable of handling multicast group dynamics when mobile hosts decide to join and leave an existing multicast group. Our simulation results reveal that under different mobility scenarios and multicast group size, ABAM has low communication overhead and yields better throughput performance. Copyright © 2001 John Wiley & Sons, Ltd.     

oStream: asynchronous streaming multicast in application-layer overlay networks

Although initially proposed as the deployable alternative to Internet protocol multicast, the application-layer overlay network actually revolutionizes the way network applications can be built, since each overlay node is an end host and is able to carry out more functions than simply forwarding packets. The paper addresses the on-demand media distribution problem in the context of an overlay network. We take advantage of the strong buffering capabilities of end hosts, and propose a novel overlay multicast strategy, oStream. We have performed extensive analysis and performance evaluation with respect to the scalability and the efficiency of oStream. With respect to the required server bandwidth, we show that oStream defeats the theoretical lower bound of traditional multicast-based approaches, under both sequential and nonsequential stream access patterns. oStream is also robust against bursty requests. With respect to bandwidth consumption on the backbone network, we show that the benefit introduced by oStream overshadows the topological inefficiency (e.g., link stress and stretch) introduced by using application-layer multicast.     

高稳定的可扩展覆盖网多播算法

提出了一种高稳定的可扩展覆盖网多播（SOM-HS, scalable overlay multicast with high stability）算法。SOM-HS算法定义了节点稳定度因子以及链路权重,能保证高稳定的节点位于多播树骨干网中。在分层分簇构造过程中,SOM-HS算法限制节点出度,保证节点负载均衡。实验结论表明,与现有其他算法相比,在不同组规模下,使用SOM-HS算法时的最大多播延时都最小。     

Multicast with network coding in application-layer overlay networks

All of the advantages of application-layer overlay networks arise from two fundamental properties: 1) the network nodes in an overlay network, as opposed to lower-layer network elements such as routers and switches, are end systems and have capabilities far beyond basic operations of storing and forwarding; 2) the overlay topology, residing above a densely connected Internet protocol-layer wide-area network, can be constructed and manipulated to suit one's purposes. We seek to improve end-to-end throughput significantly in application-layer multicast by taking full advantage of these unique characteristics. This objective is achieved with two novel insights. First, we depart from the conventional view that overlay nodes can only replicate and forward data. Rather, as end systems, these overlay nodes also have the full capability of encoding and decoding data at the message level using efficient linear codes. Second, we depart from traditional wisdom that the multicast topology from source to receivers needs to be a tree, and propose a novel and distributed algorithm to construct a two-redundant multicast graph (a directed acyclic graph) as the multicast topology, on which network coding is applied. We design our algorithm such that the costs of link stress and stretch are explicitly considered as constraints and minimized. We extensively evaluate our algorithm by provable analytical and experimental results, which show that the introduction of two-redundant multicast graph and network coding may indeed bring significant benefits, essentially doubling the end-to-end throughput in most cases.     

Characterizing Overlay Multicast Networks and Their Costs

Overlay networks among cooperating hosts have recently emerged as a viable solution to several challenging problems, including multicasting, routing, content distribution, and peer-to-peer services. Application-level overlays, however, incur a performance penalty over router-level solutions. This paper quantifies and explains this performance penalty for overlay multicast trees via: 1) Internet experimental data; 2) simulations; and 3) theoretical models. We compare a number of overlay multicast protocols with respect to overlay tree structure, and underlying network characteristics. Experimental data and simulations illustrate that the mean number of hops and mean per-hop delay between parent and child hosts in overlay trees generally decrease as the level of the host in the overlay tree increases. Overlay multicast routing strategies, overlay host distribution, and Internet topology characteristics are identified as three primary causes of the observed phenomenon. We show that this phenomenon yields overlay tree cost savings: Our results reveal that the normalized cost L(n)/U(n) is propn^0.9 for small n, where L(n) is the total number of hops in all overlay links, U(n) is the average number of hops on the source to receiver unicast paths, and n is the number of members in the overlay multicast session. This can be compared to an IP multicast cost proportional to n^0.6 to n^0.8     

固定组成员的应用层组播树不稳定问题

传统的组播树稳定性研究一般都是基于组播成员的动态变化的.但在应用层组播中,由于组播树的组成节点是应用层的端系统节点,组播成员可以通过欺骗以企图在组播树上占据更有利的位置,从而在组播成员不变时也会造成组播树的不稳定.本文建立了应用层组播节点的欺骗模型,并讨论了在固定组成员的情况下,节点欺骗引起的组播树不稳定问题.模拟实验结果表明,节点欺骗对应用层组播树的稳定性有极大的负面影响.     

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

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

Loss Recovery in Application-Layer Multicast

Application-layer multicast (ALM), sometimes called overlay multicast, can help circumvent the limitations in IP multicast and unicast. In this article, we discuss and compare different recovery mechanisms in ALM. The major challenge in loss recovery is how to achieve low residual loss rate with low recovery overhead. As discussed, a promising approach might be a combination of proactive and reactive techniques.     

Overlay,Borůvka‐based,Ad‐hoc multicast Protocol: description and performance analysis

This paper presents a novel Mobile Ad‐hoc NETworks (MANET) multicast protocol, named Overlay Borůvka‐based Ad‐hoc Multicast Protocol (OBAMP), and evaluates its performance. OBAMP is an overlay protocol: it runs only in the end‐systems belonging to the multicast group. OBAMP has three distinctive features, which give to the protocol a good performance in terms of distribution efficiency: (i) its distribution tree closely resembles the minimum spanning tree; (ii) it exploits broadcast communications; (iii) its design limits not only overlay signaling but also network‐layer signaling. In addition, OBAMP can cope with node failures in a very short time. As a consequence, OBAMP has a low latency and a high delivery ratio, even when the group size increases. To prove these statements, we analyze the performance of OBAMP with ns‐2 and compare it with three state‐of‐the‐art protocols, namely ODMRP (a network‐layer protocol), ALMA, and AMRoute (two overlay protocols). The overlay protocols are assumed to use AODV as underlying routing protocol. Also, we stress that we have implemented OBAMP, in Java, and we have tested it on the field, to prove its feasibility; to allow fellow researchers to reproduce and test our work we published all simulation and implementation codes. Copyright © 2007 John Wiley & Sons, Ltd.     

A Novel Shared Segment Protection Algorithm for Multicast Sessions in Mesh WDM Networks

This paper investigates the problem of protecting multicast sessions in mesh wavelength‐division multiplexing (WDM) networks against single link failures, for example, a fiber cut in optical networks. First, we study the two characteristics of multicast sessions in mesh WDM networks with sparse light splitter configuration. Traditionally, a multicast tree does not contain any circles, and the first characteristic is that a multicast tree has better performance if it contains some circles. Note that a multicast tree has several branches. If a path is added between the leave nodes on different branches, the segment between them on the multicast tree is protected. Based the two characteristics, the survivable multicast sessions routing problem is formulated into an Integer Linear Programming (ILP). Then, a heuristic algorithm, named the adaptive shared segment protection (ASSP) algorithm, is proposed for multicast sessions. The ASSP algorithm need not previously identify the segments for a multicast tree. The segments are determined during the algorithm process. Comparisons are made between the ASSP and two other reported schemes, link disjoint trees (LDT) and shared disjoint paths (SDP), in terms of blocking probability and resource cost on CERNET and USNET topologies. Simulations show that the ASSP algorithm has better performance than other existing schemes.     

Approximation and Heuristic Algorithms for Minimum-Delay Application-Layer Multicast Trees

In this paper we investigate the problem of finding minimum-delay application-layer multicast trees, such as the trees constructed in overlay networks. It is accepted that shortest path trees are not a good solution for the problem since such trees can have nodes with very large degree, termed high-load nodes. The load on these nodes makes them a bottleneck in the distribution tree, due to computation load and access link bandwidth constraints. Many previous solutions limited the maximum degree of the nodes by introducing arbitrary constraints. In this work, we show how to directly map the node load to the delay penalty at the application host, and create a new model that captures the trade offs between the desire to select shortest path trees and the need to constrain the load on the hosts. In this model the problem is shown to be NP-hard. We therefore present an approximation algorithm and an alternative heuristic algorithm. Our heuristic algorithm is shown by simulations to be scalable for large group sizes, and produces results that are very close to optimal     

基于灰狼算法的无线网络组播路由优化

针对无线网络中资源受限的组播路由问题,考虑网络节点的节点度限制和网络链路的带宽约束,以最小化组播路由开销为目标,提出了一种二进制编码方式的基于灰狼优化算法的组播路由策略.在给定的网络拓扑下,基于灰狼优化算法的组播路由策略可以迅速找到一棵包含源和目的节点的最小开销组播树.仿真结果表明,相比于遗传算法,所提出的基于灰狼优化算法的组播路由策略可以得到一棵开销更小的组播树,并且在相同的时间复杂下具有更强的算法稳定性.     

ZBFR: zone based failure recovery in WSNs by utilizing mobility and coverage overlapping

Wireless sensor networks are more prone to failures as compared to other traditional networks. The frequent faults and failures sometime create large holes causing loss of sensing and connectivity coverage in the network. In present work, a zone based failure detection and recovery scheme is presented to reliably handle such node failures. We first propose a consensus and agreement based approach to elect a suitable monitor node called as zone monitor (ZM). ZM is responsible for coordinating failure recovery activities and maintaining desired coverage within a zone. In order to overcome failure overhead due to false failure detection, a consensus is carried out amongst neighboring nodes of a suspicious node to confirm the correct status with high accuracy. On confirmation of a node failure, the impact of resulting hole on coverage is analyzed and if impact exceeds beyond a particular threshold, a recovery process is initiated. The recovery process utilizes backup nodes having overlapping sensing coverage with failed node and may also relocate some nodes. Firstly a backup node is probed and activated if available. If no backup node is found, the solution strives to recover coverage jointly by recursively relocating some mobile nodes and probing backup nodes. The proposed scheme is analyzed and validated through NS-2 based simulation experiments.