Fast reroute from single link and single node failures for IP multicast

The rise in multicast implementations has seen with it an increased support for fast failure recovery from link and node failures. Most recovery mechanisms augment additional services to existing protocols causing excessive overhead, and these modifications are predominantly protocol-specific. In this paper, we develop a multicast failure recovery mechanism that constructs protocol independent fast reroute paths to recover from single link and single node failures. We observe that single link failure recovery in multicast networks is similar to recovering unicast traffic, and we use existing unicast recovery mechanisms for multicast traffic. We construct multicast protection trees that provide instantaneous failure recovery from single node failures. For a given node x, the multicast protection tree spans all its neighbors and does not include itself. Thus, when the node fails, the neighbors of the node are connected through the multicast protection tree instead of node x, and forward the traffic over the multicast protection tree for the duration of failure recovery. The multicast protection trees are constructed a priori, without the knowledge of the multicast traffic in the network. Based on simulations on three realistic network topologies, we observe that the multicast protection trees increase the routing table size only by 38% on average and the path length between any source–destination pair by 13% on average.     

Multicast protection scheme in survivable WDM optical networks

The protection design is a key issue in survivable wavelength division multiplexing (WDM) optical networks. Most researches focused on protecting unicast traffic against the failure of a single network component such as a link or a node. In this paper, we investigate the protection scheme for multicast traffic in meshed WDM optical networks under dual-link failure consideration, and propose a novel protection algorithm called shared segment protection with reprovisioning (SSPR). Through dynamically adjusting link-cost according to the current network state, SSPR establishes a primary light-tree and corresponding link-disjoint backup segments for each multicast connection request. A backup segment can efficiently share wavelength capacity of its working tree or the common resource of other backup segments. Capacity reprovisioning establishes new segments for the vulnerable connections after a link failure and tolerates following link failures. The simulation results show that SSPR not only can make good use of wavelength resources and protect multicast sessions against any single-link failure, but also can greatly improve the traffic restorability in the event of dual-link breakdown.     

Comparison of recovery schemes to maximize restorable throughput in multicast networks

Multicast networks have many applications especially in real-time content delivery systems. For high-quality services, users do not expect to witness any interruption; thus, network link failure has to be handled gracefully. In unicast networks there are many approaches for dealing with link failures using backup paths. Recently, Cohen and Nakibly categorized these methods, provided linear programming formulations for optimizing network throughput under the assumption that the paths are splitable, and compared them experimentally. In this work, we take their approach and apply to the multicast failure recovery problem. We propose backup bandwidth allocation algorithms based on linear programs to maximize the throughput, and perform an experimental study on the performance of recovery schemes. We study many recovery schemes in multicast networks and propose a new recovery scheme that performs better than all other recovery scheme except the one that recomputed the whole multicast tree from scratch for each link failure.     

Optimal replication algorithms for hierarchical mobility management in PCS networks

In the context of heterogeneous networks and diverse communication devices, real person-to-person communication can be achieved with a universal personal identification (UPI) that uniquely identifies an individual and is independent of the access networks and communication devices. Hierarchical mobility management techniques (MMTs) have been proposed to support UPI. Traditional replication methods for improving the performance of such MMTs are threshold based. In this paper, we present optimal replication algorithms that minimize the network messaging cost based on network structure, communication link cost, and user calling and mobility statistics. We develop our algorithms for both unicast and multicast replica update strategies. The performance of these replication algorithms is studied via large scale network simulations and compared to results obtained from the threshold-based method.     

A Robust Spanning Tree Topology for Data Collection and Dissemination in Distributed Environments

Large-scale distributed applications are subject to frequent disruptions due to resource contention and failure. Such disruptions are inherently unpredictable and, therefore, robustness is a desirable property for the distributed operating environment. In this work, we describe and evaluate a robust topology for applications that operate on a spanning tree overlay network. Unlike previous work that is adaptive or reactive in nature, we take a proactive approach to robustness. The topology itself is able to simultaneously withstand disturbances and exhibit good performance. We present both centralized and distributed algorithms to construct the topology, and then demonstrate its effectiveness through analysis and simulation of two classes of distributed applications: Data collection in sensor networks and data dissemination in divisible load scheduling. The results show that our robust spanning trees achieve a desirable trade-off for two opposing metrics where traditional forms of spanning trees do not. In particular, the trees generated by our algorithms exhibit both resilience to data loss and low power consumption for sensor networks. When used as the overlay network for divisible load scheduling, they display both robustness to link congestion and low values for the makespan of the schedule     

A stability-based distributed routing mechanism to support unicast and multicast routing in ad hoc wireless network

An ad hoc network can be envisioned as a collection of mobile routers, each equipped with a wireless transceiver, which are free to move about arbitrarily. In ad hoc wireless networks, even if two nodes are outside the wireless transmission range of each other, they may still be able to communicate in multiple hops using other intermediate nodes. However, the dynamics of these networks, as a consequence of mobility and disconnection of mobile hosts, pose a number of problems in designing routing schemes for effective communication between any pair of source and destination. In this paper, a stability-based unicast routing mechanism, that considers both link affinity and path stability in order to find out a stable route from source to destination, is proposed. It is then extended to support multicast routing as well where only local state information (at source) is utilized for constructing a multicast tree. The performance of the proposed scheme is evaluated on a simulated environment to show that the stability-based scheme provides a unified framework for both unicast and multicast routing and reduces the probability of route error drastically in both the cases.     

多单播模型下的网络编码研究

每个信源-信宿对之间只有一个商品流(Commodity)唯一地表示从信源到信宿的流量,该模型称为多单播模型.由于无线网络、P2P等应用均可看作基于多单播模型,所以如何在多单播模型下提升网络的性能成为研究的重点.网络编码近年来作为能有效提升网络性能的方法之一,其应用于多单播模型下的各种科学问题成为研究热点.本文研究多单播模型下的网络编码关键理论,主要内容包括网络容量区域、编码构造算法和联合编码等方面,最后讨论基于多单播模型下网络编码的研究前景.     

Quantitative performance comparison of different content distribution modes

We develop methods for quantifying the gain of using multicast or a combination of broadcast and unicast for transmitting popular content in telecommunication networks. The gain is evaluated in a single link, such as the radio interface of a cellular network. Two approaches to define such a gain are presented: one based on the average link occupancy, and another based on the blocking probability. The developed methods enable determining how popular the most popular contents should be in order to justify the use of multicast or a combination of broadcast and unicast from a performance point of view.     

无线Mesh 网络低干扰组播

不同于无线传感器网络和移动Ad Hoc网络,无线Mesh网络中的组播主要侧重于提高吞吐量,而干扰是影响吞吐量的重要因素。在构建组播拓扑时,传统的方法主要考虑最小价值或最短路径,而通过减少干扰来提高组播性能的研究较少,且它们的干扰计算方法都采用单播的思想,并不适合于组播。例如,当n个接收节点同时从一个节点接收数据时,在组播中这n个接收节点之间不存在干扰,而在单播中认为存在干扰。因此,提出了组播冲突图来计算组播干扰,给出组播树干扰的定义。可以发现,求最小干扰组播扰树是NP完全问题,然后提出基于万有引力的启发式算法构建具有较小干扰的组播树。为了适用于多信道的情况,提出了满足不同干扰范围的多跳信道分配算法。最后,仿真结果显示,与MCM相比,所提出的算法无论是在单天线单信道还是多天线多信道下,都能取得较高的吞吐量和较低的延迟。     

Island Multicast: Combining IP Multicast With Overlay Data Distribution

Traditional overlay protocols use unicast connections to form delivery trees. While it can achieve global multicast across the Internet, it is not as efficient as IP multicast. In this paper, we integrate IP multicast into overlay data distribution to improve delivery efficiency. We investigate island multicast where unicast connections are used to connect multicast domains and IP multicast is used within multicast domains. We first explore a centralized island multicast protocol (termed CIM), which relies on a central server to construct a delivery tree. We then study a distributed protocol (termed DIM), where hosts can distributedly join islands and form a delivery tree. We study the key issues in both protocols. We also discuss how to apply these protocols to media streaming applications. We have evaluated both protocols on Internet-like topologies. We have also implemented a prototype for CIM and tested it on PlanetLab. The results show that our approaches can significantly im prove network performance as compared to pure overlay protocols. Our study shows that it is important to consider local multicast capability when designing overlay protocols.     

多组共享式应用层组播算法

利用单播传输路径的重叠特性所构建的叠加组播树可以部分模拟IP层的有源组播,而单组会话中成员主机在网络中分布的不足可以通过多组会话中的主机来弥补。该文根据这一特点提出了一种基于多组会话成员共享的应用层组播算法,该方法采用了源主机和接收主机之间的单播传输路径和多组协作机制,为每个组播源建立单独的组播树。通过模型分析,该文算法所构建的组播树可以比单组会话计算方法获得较大优势的链路利用率。     

Protecting multicast services in optical internet backbones

Many applications in the future Internet will use the multicasting service mode. Since many of these applications will generate large amounts of traffic, and since users expect a high level of service availability, it is important to provision multicasting sessions in the future Internet while also providing protection for multicast sessions against network component failures. In this paper we address the multicast survivability problem of using minimum resources to provision a multicast session and its protection paths (trees) against any single-link failure. We propose a new, and a resource efficient, protection scheme, namely, Segment-based Protection Tree (SPT). In SPT scheme, a given multicast session is first provisioned as a primary multicast tree, and then each segment on the primary tree is protected by a multicast tree instead of a path, as in most existing approaches. We also analyze the recovery performance of SPT and design a reconfiguration calculation algorithm to compute the average number of reconfigurations upon any link failure. By extending SPT to address dynamic traffic scenarios, we also propose two heuristic algorithms, Cost-based SPT (CB_SPT) and Wavelength-based SPT (WB_SPT). We study the performance of the SPT scheme in different traffic scenarios. The numerical results show that SPT outperforms the best existing approaches, optimal path-pair-based shared disjoint paths (OPP_SDPs). SPT uses less than 10% extra resources to provision a survivable multicast session over the optimal solution and up to 4% lower than existing approaches under various traffic scenarios and has an average number of reconfigurations 10–86% less than the best cost efficient approach. Moreover, in dynamic traffic cases, both CB_SPT and WB_SPT achieves overall blocking probability with 20% lower than OPP_SDP in most network scenarios.     

A new approach for designing fault-tolerant WDM networks

In recent years, path protection has emerged as a widely accepted technique for designing survivable WDM networks. This approach is attractive, since it is able to provide bandwidth guarantees in the presence of link failures. However, it requires allocating resources for backup lightpaths, which remain idle under normal fault-free conditions. In this paper, we introduce a new approach for designing fault-tolerant WDM networks, based on the concept of survivable routing. Survivable routing of a logical topology ensures that the lightpaths are routed in such a way that a single link failure does not disconnect the network. When a topology is generated using our approach, it is guaranteed to have a survivable routing. We further ensure that the logical topology is able to handle the entire traffic demand after any single link failure. We first present an ILP that optimally designs a survivable logical topology, and then propose a heuristic for larger networks. Experimental results demonstrate that this new approach is able to provide guaranteed bandwidth, and is much more efficient in terms of resource utilization, compared to both dedicated and shared path protection.     

Survivable telecommunications network design under different types of failures

Telecommunications networks are expected to provide near-instantaneous restoration in the event that some network elements fail. Models for designing survivable networks are very complex and difficult to solve optimally. In this paper, we provide simple heuristics that augment existing network resources to ensure restoration under several scenarios of a single failure. The goal is to demonstrate that effective, though not necessarily optimal, survivable designs can be achieved by augmenting capacities along prudently selected variants of spanning tree and ring structures, without resorting to complex mathematical programming methods. The first model considers line restoration (reroutes around the failed link) under a partial link failure. We propose a heuristic that augments capacities of selected network links by forming a "virtual" spanning tree of restoration capacity. The second model provides line restoration under a complete link failure. We propose a heuristic that ensures survivability by repeatedly constructing spanning trees to various subnetworks. The third model provides path restoration (end-to-end reroutes) under a node failure. We propose a heuristic that repeatedly constructs restoration rings that cover a subset of source-destination nodes that carry traffic through intermediate nodes.     

组播协议在OPNET中的建模与仿真

该文以IP组播技术为重点,结合网络仿真软件OPENT Modeler,分析该软件环境下IP组播网络的建模机制,包括参考标准、组的管理、支持的应用、组播路由协议的选择,节点加入组播组与发送源发送组播数据的流程。以校园网视频会议和FTP传输应用为例,构建网络仿真模型,一方面比较单播与组播方式下的网络性能,分析了视频流量的发送情况、视频会议分组的端到端延时,FTP传输的响应时间,骨干网络点到点链路吞吐量;另一方面比较了组播方式采用共享树机制和由共享树切换到最短路径树在网络性能上的改进,包括分组延迟的降低、汇合点路由器上拥塞发生的减少等。同时,也对无线移动通信网络环境下的组播技术提出更多需要考虑的因素。     

Scalable network-on-chip architecture for configurable neural networks

Providing highly flexible connectivity is a major architectural challenge for hardware implementation of reconfigurable neural networks. We perform an analytical evaluation and comparison of different configurable interconnect architectures (mesh NoC, tree, shared bus and point-to-point) emulating variants of two neural network topologies (having full and random configurable connectivity). We derive analytical expressions and asymptotic limits for performance (in terms of bandwidth) and cost (in terms of area and power) of the interconnect architectures considering three communication methods (unicast, multicast and broadcast). It is shown that multicast mesh NoC provides the highest performance/cost ratio and consequently it is the most suitable interconnect architecture for configurable neural network implementation. Routing table size requirements and their impact on scalability were analyzed. Modular hierarchical architecture based on multicast mesh NoC is proposed to allow large scale neural networks emulation. Simulation results successfully validate the analytical models and the asymptotic behavior of the network as a function of its size.     

Approximation Algorithms for Data Management in Networks

This paper deals with static data management in computer systems connected by networks. A basic functionality in these systems is the interactive use of shared data objects that can be accessed from each computer in the system. Examples for these objects are files in distributed file systems, cache lines in virtual shared memory systems, or pages in the WWW. In the static scenario we are given read and write request frequencies for each computer–object pair. The goal is to calculate a placement of the objects to the memory modules, possibly with redundancy, such that a given cost function is minimized. With the widespread use of commercial networks, as, e.g., the Internet, it is more and more important to consider commercial factors within data management strategies. The goal in previous work was to utilize the available resources, especially the bandwidth, as best as possible. We present data management strategies for a model in which commercial cost instead of the communication cost is minimized, i.e., we are given a metric communication cost function and a storage cost function. We introduce new deterministic algorithms for the static data management problem on trees and arbitrary networks. Our algorithms aim to minimize the total cost. Note that this problem is MaxSNP-hard on arbitrary networks. Our main result is a combinatorial algorithm that calculates a constant factor approximation for arbitrary networks in polynomial time. Further, we present a dynamic programming algorithm for trees that calculates an optimal placement of all objects in $X$ on a tree $T=(V,E)$ in time $O(|X| \cdot |V| \cdot \di(T) \cdot \log(\de(T)))$.     

关于实际构造最大带宽路径算法的研究

建立最大带宽路径一直是网络路由研究，尤其是在最近的网络QoS路由研究中的基本问题，在以往的文献中，有人提出了利用修改的Dijkstra算法或修改的Bellman-Ford算法来构建最大带宽路径。该文给出了一个简单的证明，指出了最大生成树与最大带宽路径之间的特殊关系，证明了可以使用修改的Kruskal算法来构建最大带宽路径，文中给出了修改的Kruskal算法，并且与已有的Kijkstra算法作了性能上的比较，尽管从理论上说，Dijstra算法和Kruskal算法的时间复杂度具有同样的阶，但在多种不同网络结构上的模拟测试结果表明，用Kruskal算法构建最大带宽路径的实际运行比Dijkstra算法至少要快3倍，而且在实际上比Dijkstra算法更简单，灵活。     

无线传感器网络中一种分布式冗余检测算法

无线传感器网络覆盖控制中现有的大部分冗余检测算法都是针对节点感知半径相同的同构网络的,无法应用于异构网络.提出一种保持网络k级覆盖的适应异构传感器网络的分布式冗余检测算法.该算法根据节点的冗余分布特性设计了有效覆盖邻居选取,通过有效覆盖邻居感知半径关系及交点处的覆盖程度判断检测冗余.仿真表明:算法中有效覆盖邻居选取的设计,大大降低了节点执行冗余计算的时间,算法的运行效率较高;算法在异构WSN中性能优异,冗余检测彻底、充分,有益于节省节点能量,延长网络生存时间.     

A QoS Multicast Routing Algorithm Working with Imprecise State Information

In large networks, maintaining precise global network state information is almost impossible. Many factors, including non-negligible propagation delay, infiequent link state update due to overhead concerns, link state update policy, and hierarchical topology aggregation, have impacts on the precision of the network state information. The existing QoS multicast routing algorithms do not provide satisfactory performance with imprecise state information. In this paper, we propose a distributed QoS multicast routing scheme based on traffic lights, called QMRI algorithm, which can probe multiple feasible tree branches, and select the optimal or near-optimal branch through the UR or TL mode for constructing a multicast tree with QoS guarantees if it exists. The proposed algorithm considers not only the QoS requirements but also the cost optimality of the multicast tree. Extensive simulations show that our algorithm achieves high call-admission ratio and low-cost multicast trees with modest message overhead. The algorithm can tolerate high degree of state information imprecision.