Scheduling support for multicasting sessions in broadband communication networks

Multimedia applications require support from the underlying broadband network at the end-to-end communication level. Multicasting is an important paradigm of end-to-end communication. The root node of a multicasting session is responsible for controlling the session including monitoring, maintenance, and the implementation of the multicasting protocol. The job that controls the multicasting session executes as a group of tasks at the root node of a multicasting tree. The scheduling scheme at the root node should give support to a multicasting session by improving the completion time of the jobs controlling the multicasting session, hence increasing throughput and the probability of admitting new multicast sessions into the system. In this paper, we model the tasks that carry out the multicasting session monitoring and maintenance as a fork-join job executing on a multiprocessor system. We assume that an executing task blocks for device I/O as a part of the activities associated with sending and receiving data packets. We develop two analytic models for scheduling a session control job on a multiprocessor system. The first model allows incoming job tasks to multiplex processors with existing tasks of another multicasting session, while the other model schedules a task of the incoming job to an idle processor. We assume that the overhead of rescheduling a task to another processor is large. We compare the performance of both models and show the range of conditions under which a model outperforms the other. We point out how the results can be used in the design of an adaptive scheduler that uses both models to improve throughput and consequently the probability of admitting new multicast sessions.     

Approximate bounds and expressions for the link utilization of shortest-path multicast network traffic

Multicast network traffic is information with one source node, but many destination nodes. Rather than setting up individual connections between the source node and each destination node, or broadcasting the information to the entire network, multicasting efficiently exploits link capacity by allowing the source node to transmit a small number of copies of the information to mutually-exclusive groups of destination nodes. Multicasting is an important topic in the fields of networking (video and audio conferencing, video on demand, local-area network interconnection) and computer architecture (cache coherency, multiprocessor message passing). In this paper, we derive approximate expressions for the minimum cost (in terms of link utilization) of shortest-path multicast traffic in arbitrary tree networks. Our results provide a theoretical best-case scenario for link utilization of multicast distribution in tree topologies overlaid onto arbitrary graphs. In real networks such as the Internet MBONE, multicast distribution paths are often tree-like, but contain some cycles for purposes of fault tolerance. We find that even for richly-connected graphs such as the shufflenet and the hypercube, our expression provides a good prediction of the cost (in terms of link utilization) of multicast communication. Thus, this theoretical result has two applications: (1) a lower bound on the link capacity required for multicasting in random tree topologies, and (2) an approximation of the cost of multicasting in regular LAN and MAN topologies.     

AMRST: adaptive multicast routing protocol for satellite–terrestrial networks

Multicasting facilitates the distributing of multimedia information to an entire set of destinations simultaneously. However, the subsequent mass of Internet traffic usually increases the network congestion and degrades network utilization. The unexpected congestion together with limited network capacity might challenge the provision of multimedia services especially since multicast subscribers are widely scattered. The desired QoS of the ongoing services cannot be guaranteed. To address this challenge, in addition to installing new terrestrial broadband networks, another feasible solution would be to integrate now available broadcasting-oriented broadband satellite networks into the Internet backbone. This paper presents a novel adaptive multicast routing (AMRST) protocol to deliver reliable and adaptive multicast services to global subscribers, based on an integrated infrastructure, called a satellite–terrestrial network (ST network), which provides dynamic bandwidth allocation, flexible resource management and ubiquitous transmission. In the AMRST, a proposed virtual hierarchical routing tree was applied in constructing an efficient multicast tree. A routing decision model was proposed to determine routing path for the member requests. A “hierarchical membership maintenance” approach was designed to maintain the multicast membership. The scalability of the AMRST was further addressed. The AMRST not only kept the benefits of the traditional terrestrial multicast but also promoted the multicasting performance by employing the satellite broadcasting capability. The simulation results demonstrate that the AMRST performed excellently for the ST network.     

A new locality-based IP multicasting scheme for mobile hosts

Internet protocol multicasting is a mechanism widely used in the Internet to disseminate information. Multicast delivery paths may need to be frequently restructured along with host migrations, at the expense of nontrivial overhead or multicast latency. This paper presents a scheme with short multicast latency, while retaining acceptable overhead in adapting the delivery paths to mobile host locations. We exploit the locality in host movements and keep active the networks that mobile hosts have most recently visited. As long as hosts migrate within these active networks, multicast delivery paths can remain unchanged upon host movements. Performance results show that, compared with the best known proposal, our scheme is promising.     

基于遗传算法的P2P流媒体多播模型

为解决P2P流媒体通信中的流量控制问题，给出一个P2P社区覆盖多播通信优化模型及其建立覆盖核心多播树OCMT的QoS约束条件，并采用一个面向目标的遗传算法解决建立OCMT中的路径优化问题。仿真实验结果表明该模型能为建立具有低延迟和强扩展能力的核心多播树获得较优化的方案，并且有效地降低不同P2P社区间的数据流量，实现控制Internet流量的目的。     

区分服务网络中IP多播:问题与解决方案

在下一代因特网中,越来越多的应用将会需要网络提供一定的服务质量以及进行多播传输．因为区分服务体系结构提供了一种可扩展的QoS解决方案,而多播传输则提供了一种节约网络资源的有效方法,二者的集成成为必然趋势．但是,由于区分服务体系结构与多播树结构上的差异,二者的集成存在着一些问题．详细分析了区分服务网络中进行IP多播传输可能出现的问题,并且对近年来提出的各种解决方案进行了分类比较和深入剖析,同时指出了在这一领域中未来的研究方向．     

A subtree-based approach to failure detection and protection for multicast in SDN

Software-defined networking (SDN) has received tremendous attention from both industry and academia. The centralized control plane in SDN has a global view of the network and can be used to provide more effective solutions for complex problems, such as traffic engineering. This study is motivated by recent advancement in SDN and increasing popularity of multicasting applications. We propose a technique to increase the resiliency of multicasting in SDN based on the subtree protection mechanism. Multicasting is a group communication technology, which uses the network infrastructure efficiently by sending the data only once from one or multiple sources to a group of receivers that share a common path. Multicasting applications, e.g., live video streaming and video conferencing, become popular, but they are delay-sensitive applications. Failures in an ongoing multicast session can cause packet losses and delay, which can significantly affect quality of service (QoS). In this study, we adapt a subtree-based technique to protect a multicast tree constructed for OpenFlow switches in SDN. The proposed algorithm can detect link or node failures from a multicast tree and then determines which part of the multicast tree requires changes in the flow table to recover from the failure. With a centralized controller in SDN, the backup paths can be created much more effectively in comparison to the signaling approach used in traditional multiprotocol label switching (MPLS) networks for backup paths, which makes the subtree-based protection mechanism feasible. We also implement a prototype of the algorithm in the POX controller and measure its performance by emulating failures in different tree topologies in Mininet.     

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

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

On an efficient NoC multicasting scheme in support of multiple applications running on irregular sub-networks

When a number of applications simultaneously running on a many-core chip multiprocessor (CMP) chip connected through network-on-chip (NoC), significant amount of on-chip traffic is one-to-many (multicast) in nature. As a matter of fact, when multiple applications are mapped onto an NoC architecture with applicable traffic isolation constraints, the corresponding sub-networks of these applications are mapped onto actually tend to be irregular. In the literature, multicasting for irregular topologies is supported through either multiple unicasting or broadcasting, which, unfortunately, results in overly high power consumption and/or long network latency. To address this problem, a simple, yet efficient hardware-based multicasting scheme is proposed in this paper. First, an irregular oriented multicast strategy is proposed. Literally, following this strategy, an irregular oriented multicast routing algorithm can be designed based on any regular mesh based multicast routing algorithm. One such algorithm, namely, Alternative Recursive Partitioning Multicasting (AL + RPM), is proposed based on RPM, which was designed for regular mesh topology originally. The basic idea of AL + RPM is to find the output directions following the basic RPM algorithm and then decide to replicate the packets to the original output directions or the alternative (AL) output directions based on the shape of the sub-network. The experiment results show that the proposed multicast AL + RPM algorithm can consume, on average, 14% and 20% less power than bLBDR (a broadcasting-based routing algorithm) and the multiple unicast scheme, respectively. In addition, AL + RPM has much lower network latency than the above two approaches. To incorporate AL + RPM into a baseline router to support multicasting, the area overhead is fairly modest, less than 5.5%.     

A comparison of heterogeneous video multicast schemes: Layered encoding or stream replication

The heterogeneity of the Internet's transmission resources and end system capability makes it difficult to agree on acceptable traffic characteristics among the multiple receivers of a multicast video stream. Three basic approaches have been proposed to deal with this problem: 1) multicasting the replicated video streams at different rates; 2) multicasting the video encoded in cumulative layers; and 3) multicasting the video encoded in noncumulative layers. Even though there is a common belief that the layering approach is better than the replicated stream approach, there have been no studies that compare these schemes. This paper is devoted to such a systematic comparison. Our starting point is an observation (substantiated by results in the literature) that a bandwidth overhead is incurred by encoding a video stream in layers. We argue that a fair comparison of these schemes needs to take into account this overhead, as well as the specifics of the encoding used in each scheme, protocol complexity, and the topological placement of the video source and the receivers relative to each other. Our results show that the believed superiority of layered multicast transmission relative to replicated stream multicasting is not as clear cut as is widely believed and that there are indeed scenarios where replicated stream multicasting is the preferred approach.     

Traffic distribution for end-to-end QoS routing with multicast multichannel services

With the development of multimedia group applications and multicasting demands, the construction of multicast routing tree satisfying Quality of Service (QoS) is more important. A multicast tree, which is constructed by existing multicast algorithms, suffers three major weaknesses: (1) it cannot be constructed by multichannel routing, transmitting a message using all available links, thus the data traffic cannot be preferably distributed; (2) it does not formulate duplication capacity; consequently, duplication capacity in each node cannot be optimally distributed; (3) it cannot change the number of links and nodes used optimally. In fact, it cannot employ and cover unused backup multichannel paths optimally. To overcome these weaknesses, this paper presents a polynomial time algorithm for distributed optimal multicast routing and Quality of Service (QoS) guarantees in networks with multichannel paths which is called Distributed Optimal Multicast Multichannel Routing Algorithm (DOMMR). The aim of this algorithm is: (1) to minimize End-to-End delay across the multichannel paths, (2) to minimize consumption of bandwidth by using all available links, and (3) to maximize data rate by formulating network resources. DOMMR is based on the Linear Programming Formulation (LPF) and presents an iterative optimal solution to obtain the best distributed routes for traffic demands between all edge nodes. Computational experiments and numerical simulation results will show that the proposed algorithm is more efficient than the existing methods. The simulation results are obtained by applying network simulation tools such as QSB, OpNet and MATLB to some samples of network. We then introduce a generalized problem, called the delay-constrained multicast multichannel routing problem, and show that this generalized problem can be solved in polynomial time.     

一种基于遗传算法的半动态应用层多播协议

将半动态应用层多播通信分解为静态起始和动态维护两种阶段交替出现的过程．在起始阶段．采用基于遗传算法的多播路由机制构建优化的静态多播树;在维护阶段,采用拓扑维护机制、路由性能监控机制和路由更新机制．对多播拓扑的动态进行快速响应．仿真结果表明．该协议同时具备优化多播树性能和快速维护多播拓扑的能力,改善了通信过程中多播树的整体性能．     

Analytical models for Replicate-At-Send multicasting in shared-memory switches

Shared-memory switches are still in commercial use and in the future will possibly be used in large-scale multistage architectures. The need to handle multicasting is also growing. In this paper analytical models are presented for shared-memory switches with the Replicate-At-Send-distinct address queue multicast scheme. Models for both Random (Bernoulli) and Bursty (Correlated) traffic sources are presented. The models are accurate for various loads, with different ratios of multicast traffic and a range of fanout sizes. They can be further extended to analyse more complex multicast schemes or multistage architectures.     

一种安全组播的批密钥管理方案

为了保证组播通信的机密性,安全组播使用不为组外成员所知的密钥来加密数据,并随组成员关系的变化而动态更新.目前的研究大多集中在单个组播成员加入或退出时所要进行的密钥更新.而单个密钥更新存在以下两个缺点:一是密钥更新效率低,浪费服务器资源,二是存在数据和密钥之间不同步问题.而采用组播批密钥更新策略,可以有效地提高密钥更新效率,节约服务器资源.本文提出一种基于迭代哈希函数链的批密钥更新方案.比较分析结果表明,该方案可有效地节约服务器资源.仿真结果进一步证明,与单密钥更新相比,该方案可有效地提高服务器密钥更新效率.     

HEURISTIC ALGORITHMS FOR SURVIVABLE P2P MULTICASTING

The growing volume of Internet traffic, increasing popularity of streaming services, and limited scalability of existing network techniques trigger the need to develop new delivery solutions based on a multicasting approach. Multicasting—defined as a one-to-many delivery technique—enables effective distribution of many kinds of content to end users. In this article we focus on peer-to-peer (P2P) multicasting, which combines concepts of P2P systems and multicasting solutions; in other words, the multicast tree is constructed using end hosts (peers). Because P2P multicasting can be applied to deliver content with high reliability requirements, we introduce to P2P multicasting additional survivability constraints that guarantee delivery of content in the case of network failures. We formulate a mixed-integer programming (MIP) optimization problem of survivable P2P multicasting. Because the problem is nondeterministic polynomial time (NP)-hard and exact methods such as branch-and-cut can be applied for only a relatively small problem instance, we propose two heuristic algorithms based on evolutionary approach and Tabu Search methods. Extensive computational experiments show that both heuristic algorithms provide results close to optimal—the average gap to optimal results is 0.26% and 5.15% in the case of evolutionary and Tabu Search methods, respectively.     

High throughput MAC layer multicasting over time-varying channels

Efficient, scalable and robust multicasting support from the MAC layer is needed for meeting the demands of multicast based applications over WiFi and mesh networks. However, the IEEE 802.11 protocol has no specific mechanism for multicasting. It implements multicasting using broadcasting at the base transmission rate. We identify two fundamental reasons for performance limitations of this approach in presence of interference and realistic time-varying channels: (a) Channel-state Indifference: irrespective of the current quality of the channel to the receivers, the transmission always uses the base transmission rate; (b) Demand Ignorance: packets are transmitted by a node even if children in the multicast tree have received those packets by virtue of overhearing. We propose a solution for MAC layer multicasting called HIMAC that uses the following two mechanisms: Unary Channel Feedback (UCF) and Unary Negative Feedback (UNF) to respectively address the shortcomings of 802.11. Our study is supported by measurements in simulations. We observe that the end-to-end throughput of multicast sessions using MAODV can be increased by up to 74% while reducing the end-to-end latency by up to a factor of 56.     

一种动态组播的密钥更新算法

为了保证组播通信的机密性,安全组播使用不为组外成员所知的密钥来加密数据,并随组成员关系的变化而动态更新。基于树型分层式密钥管理方式使用户变更时的密钥更新代价减小,但前提是密钥树必须保持平衡。本文提出了一种应用m序B树作为组密钥树的密钥管理方法,在组播组中加入一个新成员,本方案比传统方案减少了密钥更新开销量,提高密钥更新效率。     

An efficient and scalable loss-recovery scheme for video multicast

With the increased popularity of multimedia services on the Internet, efficient video multicast strategies that can scale easily are of critical importance. This paper addresses the issue of video multicast loss recovery and presents an efficient and scalable scheme: Active Injection Recovery (AIR). The proposed scheme has three distinguishing features: active injection of repair packets into loss regions, on-demand construction of loss-recovery structures, and unique rate control over repair traffic. All of these features can save considerable network resources in a large-scale video multicast session. In addition, the proposed scheme simultaneously meets the three well-known requirements for efficiency and scalability in multicast loss recovery: request suppression, local recovery, and retransmission scoping. Another important feature of the proposed scheme is its low recovery latency, which is essential for video multicast. Our results show that the proposed scheme achieves significantly better overall performance as compared to existing multicast loss recovery schemes.     

An efficient and easily deployable QoS-based routing scheme for online Internet multicasting

With the advent of multimedia applications, the support of online multicasting with quality of service guarantees has gained considerable attention in the field of communication networks and distributed systems. Online multicasting requires the support of online join and leave operations. In this paper, a new Simple and Efficient Low-cost Delay-bounded Online Multicasting (SELDOM) heuristic is proposed. SELDOM is particularly tailored to networks in which group membership changes frequently. SELDOM supports two modes of operations: non-rearrangeable and rearrangeable. The scheme handles join requests dynamically by determining the least-cost path which satisfies the required delay-bounds to which the new group member is to be attached. To handle a leave request, the scheme seeks to limit the number of rearrangements required in order to reduce the disturbance such a request may cause to current group members. The worst case time complexity of SELDOM is O(n²). An important research contribution of this work shows that if any non-rearrangeable multicast heuristic uses a path other than the least-delay path to add a node to the multicast tree, then the resulting multicast tree can have cycles or nodes with two incoming paths. A simulation-based comparison between non-rearrangeable and rearrangeable online multicast trees is also presented.