Multicast routing and bandwidth dimensioning in overlay networks

Multicast services can be provided either as a basic network service or as an application-layer service. Higher level multicast implementations often provide more sophisticated features and can provide multicast services at places where no network layer support is available. Overlay multicast networks offer an intermediate option, potentially combining the flexibility and advanced features of application layer multicast with the greater efficiency of network layer multicast. In this paper, we introduce the multicast routing problem specific to the overlay network environment and the related capacity assignment problem for overlay network planning. Our main contributions are the design of several routing algorithms that optimize the end-to-end delay and the interface bandwidth usage at the multicast service nodes within the overlay network. The interface bandwidth is typically a key resource for an overlay network provider, and needs to be carefully managed in order to maximize the number of users that can be served. Through simulations, we evaluate the performance of these algorithms under various traffic conditions and on various network topologies. The results show that our approach is cost-effective and robust under traffic variations.     

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.     

Application-layer multicasting with Delaunay triangulation overlays

Application-layer multicast supports group applications without the need for a network-layer multicast protocol. Here, applications arrange themselves in a logical overlay network and transfer data within the overlay. We present an application-layer multicast solution that uses a Delaunay triangulation as an overlay network topology. An advantage of using a Delaunay triangulation is that it allows each application to locally derive next-hop routing information without requiring a routing protocol in the overlay. A disadvantage of using a Delaunay triangulation is that the mapping of the overlay to the network topology at the network and data link layer may be suboptimal. We present a protocol, called Delaunay triangulation (DT protocol), which constructs Delaunay triangulation overlay networks. We present measurement experiments of the DT protocol for overlay networks with up to 10 000 members, that are running on a local PC cluster with 100 Linux PCs. The results show that the protocol stabilizes quickly, e.g., an overlay network with 10 000 nodes can be built in just over 30 s. The traffic measurements indicate that the average overhead of a node is only a few kilobits per second if the overlay network is in a steady state. Results of throughput experiments of multicast transmissions (using TCP unicast connections between neighbors in the overlay network) show an achievable throughput of approximately 15 Mb/s in an overlay with 100 nodes and 2 Mb/s in an overlay with 1000 nodes.     

A Unified Framework for Multipath Routing for Unicast and Multicast Traffic

We study the problem of load balancing the traffic from a set of unicast and multicast sessions. The problem is formulated as an optimization problem. However, we assume that the gradient of the network cost function is not available and needs to be estimated. Multiple paths are provided between a source and a destination using application-layer overlay. We propose a novel algorithm that is based on what is known as simultaneous perturbation stochastic approximation and utilizes only noisy measurements collected and reported to the sources, using an overlay architecture.We consider three network models that reflect different sets of assumptions regarding multicast capabilities of the network. Using an analytical model we first prove the almost sure convergence of the algorithm to a corresponding optimal solution under each network model considered in this paper with decreasing step sizes. Then, we establish the weak convergence (or convergence in distribution) with a fixed step size. In addition, we investigate the benefits acquired from implementing additional multicast capabilities by studying the relative performance of our algorithm under the three network models.      

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%).     

普适环境下带宽自适应的组播策略

提出一种以树状拓扑为主干,Mesh状拓扑为辅助的组播策略.首先定义严格单源树状拓扑,并根据普适环境下结点的自治性行为提出放松单源树状拓扑.其次分析树状拓扑动态性带来的带宽瓶颈问题.通过Mesh状辅助拓扑和结点带宽使用情况动态调整结点状态,实现了自适应的带宽使用策略,保证了较高的使用率和可用性.分析模拟结果表明,与现有的方法相比,该策略能够取得较好的组播性能.     

A case for end system multicast

The conventional wisdom has been that Internet protocol (IP) is the natural protocol layer for implementing multicast related functionality. However, more than a decade after its initial proposal, IP multicast is still plagued with concerns pertaining to scalability, network management, deployment, and support for higher layer functionality such as error, flow, and congestion control. We explore an alternative architecture that we term end system multicast, where end systems implement all multicast related functionality including membership management and packet replication. This shifting of multicast support from routers to end systems has the potential to address most problems associated with IP multicast. However, the key concern is the performance penalty associated with such a model. In particular, end system multicast introduces duplicate packets on physical links and incurs larger end-to-end delays than IP multicast. We study these performance concerns in the context of the Narada protocol. In Narada, end systems self-organize into an overlay structure using a fully distributed protocol. Further, end systems attempt to optimize the efficiency of the overlay by adapting to network dynamics and by considering application level performance. We present details of Narada and evaluate it using both simulation and Internet experiments. Our results indicate that the performance penalties are low both from the application and the network perspectives. We believe the potential benefits of transferring multicast functionality from end systems to routers significantly outweigh the performance penalty incurred.     

Incremental service deployment using the hop-by-hop multicast routing protocol

IP multicast is facing a slow take-off although it has been a hotly debated topic for more than a decade. Many reasons are responsible for this status. Hence, the Internet is likely to be organized with both unicast and multicast enabled networks. Thus, it is of utmost importance to design protocols that allow the progressive deployment of the multicast service by supporting unicast clouds. This paper presents HBH (hop-by-hop multicast routing protocol). HBH adopts the source-specific channel abstraction to simplify address allocation and implements data distribution using recursive unicast trees, which allow the transparent support of unicast-only routers. An important original feature of HBH is its tree construction algorithm that takes into account the unicast routing asymmetries. Since most multicast routing protocols rely on the unicast infrastructure, the unicast asymmetries impact the structure of the multicast trees. We show through simulation that HBH outperforms other multicast routing protocols in terms of the delay experienced by the receivers and the bandwidth consumption of the multicast trees. Additionally, we show that HBH can be incrementally deployed and that with a small fraction of HBH-enabled routers in the network HBH outperforms application-layer multicast.     

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     

Real-Time Streaming Relay Mechanism for P2P Conferences on Hierarchical Overlay Networks

A peer-to-peer (P2P) multimedia conferencing service is operating that users share their resources to each other on the Internet. It can solve the problem in the centralized conferencing architecture, such as the centralized loading, single point error, and expensive infrastructure. However, P2P networks have the problem that a peer has a difference between the physical location and logical location in the overlay network. In the viewpoint of P2P networks, the nearest conference resource may be far away geographically. The P2P-session initiation protocol (P2P-SIP) multimedia conference is to construct an application-based logical multicast network efficiently according to physical network information. Thus, this paper proposes a real-time streaming relay mechanism for P2P conferences on hierarchical overlay networks. The real-time streaming relay mechanism can improve the transportation efficiency of conferencing stream exchange well based on the application-layer multicast (ALM) structure and the hierarchical overlay networks.     

OMAC: A new access control architecture for overlay multicast communications

Multicast communications concern the transfer of data among multiple users. Multicast communications can be provided at the network layer—an example is IP multicast—or at the application layer, also called overlay multicast. An important issue in multicast communications is to control how different users—senders, receivers, and delivery nodes—access the transmitted data as well as the network resources. Many researchers have proposed solutions addressing access control in IP multicast. However, little attention has been paid to overlay multicast. In this paper, we investigate the access control issues in overlay multicast and present OMAC: a new solution to address these issues. OMAC provides access control for senders, receivers, and delivery nodes in overlay multicast. The proposed architecture, which is based on symmetric key cryptosystem, centralizes the authentication process in one server whereas it distributes the authorization process among the delivery nodes. Moreover, delivery nodes are utilized as a buffer zone between end systems and the authentication server, making it less exposed to malicious end systems. To evaluate our work, we have used simulation to compare the performance of OMAC against previous solutions. Results of the simulation show that OMAC outperforms previous multicast access control schemes. Copyright © 2010 John Wiley & Sons, Ltd.     

Multicast-based inference of network-internal delay distributions

Packet delay greatly influences the overall performance of network applications. It is therefore important to identify causes and locations of delay performance degradation within a network. Existing techniques, largely based on end-to-end delay measurements of unicast traffic, are well suited to monitor and characterize the behavior of particular end-to-end paths. Within these approaches, however, it is not clear how to apportion the variable component of end-to-end delay as queueing delay at each link along a path. Moreover, there are issues of scalability for large networks. In this paper, we show how end-to-end measurements of multicast traffic can be used to infer the packet delay distribution and utilization on each link of a logical multicast tree. The idea, recently introduced in Caceres et al. (1999), is to exploit the inherent correlation between multicast observations to infer performance of paths between branch points in a tree spanning a multicast source and its receivers. The method does not depend on cooperation from intervening network elements; because of the bandwidth efficiency of multicast traffic, it is suitable for large-scale measurements of both end-to-end and internal network dynamics. We establish desirable statistical properties of the estimator, namely consistency and asymptotic normality. We evaluate the estimator through simulation and observe that it is robust with respect to moderate violations of the underlying model.     

Wireless video applications in 3G and beyond

This article surveys wireless video applications that have been commercialized recently or are expected to go to market in 3G (and beyond) mobile networks, mainly covering error control technologies in view of "wireless video." We introduce several related 3GPP standards including circuit-switched multimedia telephony, end-to-end packet-switched streaming, multimedia messaging service, and multimedia broadcast /multimedia service. We also review the supporting technologies for those four applications. The article concludes with a discussion of error control and rate control adaptability to network QoS variation, which is distinct from wired networks and critical to wireless networks. With respect to MBMS, we point out that required cell transmission power is crucial when realizing meaningful multicast coverage, and suggest a system that integrates different unicast and multicast networks, application-layer data repair, and transmission scheduling.     

Efficient rate-controlled bulk data transfer using multiple multicast Groups

Controlling the rate of bulk data multicast to a large number of receivers is difficult, due to the heterogeneity among the end systems' capabilities and their available network bandwidth. If the data transfer rate is too high, some receivers will lose data, and retransmissions will be required. If the data transfer rate is too slow, an inordinate amount of time will be required to transfer the data. In this paper, we examine an approach toward rate-controlled multicast of bulk data in which the sender uses multiple multicast groups to transmit data at different rates to different subgroups of receivers. We present simple algorithms for determining the transmission rate associated with each multicast channel, based on static resource constraints, e.g., network bandwidth bottlenecks. Transmission rates are chosen so as to minimize the average time needed to transfer data to all receivers. Analysis and simulation are used to show that our policies for rate selection perform well for large and diverse receiver groups and make efficient use of network bandwidth. Moreover, we find that only a small number of multicast groups are needed to reap most of the possible performance benefits.     

Multicast Flow Aggregation in IP over Optical Networks

It is widely believed that IP over optical networks will be a major component of the next generation Internet However, it is not efficient to map a single multicast IP flow into one light-tree, since the bandwidth of an IP flow required is usually much less than that of a light-tree. In this paper, we study the problem of multicast flow aggregation (MFA) in the IP over optical two-layered networks under the overlay model, which can be defined as follows: given a set of head ends (i.e. optical multicasting sources), each of which can provide a set of contents (i.e. multicast IP flows) with different required transmission bandwidth, and a set of requested content at the access routers (i.e. optical multicasting destinations), find a set of light-trees as well as the optimal aggregation of multicast IP flows in each light-tree. We model MFA by a tri-partite graph with multiple criteria and show that the problem is NP-complete. Optimal solutions are designed by exploiting MFA to formulate an integer linear programming (ILP), with two parameters: the multicast receiving index alpha and the redundant transmitting index beta. We also propose a heuristic algorithm. Finally, we compare the performance of MFA for different combination of alpha and beta via experiments and show our heuristic algorithm is effective for large-scale network in numerical results     

Outreach: peer-to-peer topology construction towards minimized server bandwidth costs

On-demand and live multimedia streaming applications (such as Internet TV) are well known to utilize a significant amount of bandwidth from media streaming servers, especially as the number of participating peers in the streaming session scales up. To scale to higher bit rates of media streams and larger numbers of participating peers, overlay tree or mesh topologies are typically constructed, such that peers utilize their available upload capacities to alleviate the excessive bandwidth demands on stream servers. Previous works rely on random selections of upstream peers, without optimizing the topologies towards maximized utilization of peer upload bandwidth, and as a result, minimized bandwidth costs on streaming servers. We propose Outreach, a distributed algorithm to construct overlay topologies among participating peers in streaming sessions. The design objective of Outreach is to optimize the quality of overlay topologies towards scalability, with respect to the number of participating peers in the session. To be scalable, Outreach seeks to maximize the utilization of available upload bandwidth on each participating peer, and consequently minimize the total bandwidth costs on streaming servers. With analysis, we show that Outreach constructs topologies such that peers can fully utilize their upload capacities, and present a practical distributed algorithm. With simulation-based comparison studies, we show that Outreach effectively achieves its goals in a high-churn peer-to-peer network with an assortment of peer uplink capacities and link delays     

Optimal multicast smoothing of streaming video over the Internet

A set of applications such as Internet video broadcasts, corporate telecasts, and distance learning require the simultaneous streaming of video to a large population of viewers across the Internet. The high bandwidth requirements and the multi-timescale burstiness of compressed video make it a challenging problem to provision network resources for streaming multimedia. For such applications to become affordable and ubiquitous, it is necessary to develop scalable techniques to efficiently stream video to a large number of disparate clients across a heterogeneous Internet. In this paper, we propose to multicast smoothed video over an application-level overlay network of proxies, and to differentially cache the video at the intermediate nodes (proxies) in the distribution tree, in order to reduce the network bandwidth requirements of video dissemination. We formulate the multicast smoothing problem as an optimization problem, and develop an algorithm for computing the set of transmission schedules for the tree that minimize the peak rate and rate variability, given buffer constraints at different nodes in the tree. We also develop an algorithm to compute the minimum buffer allocation in the entire tree, such that feasible transmission to all the clients is possible, when the tree has heterogeneous rate constraints. We show through trace-driven simulations that substantial benefits are possible from multicast smoothing and differential caching, and that these gains can be realized even with modest proxy caches.     

Single-Source Oriented Application Level Multicast

1　Introduction　TherearevariousIPmulticastprotocols[1～6] havebeenproposedandstandardized ,butfewofthemhavebeendeployedwidespreadlyintheglobalInter netduetotechnicalandcommercialissues[7] .RE UNITE[8] usesrecursiveunicasttreestoimplementmulticastservicewithoutIPmulticastdelpoyment.Withoutanymodificationofrouters,applicationlev elmulticastapproaches[9～ 1 4 ] usingoverlaynetworkshavebeenproposedasaviablealternativetoIPmul ticast.Theseapproachesusedifferentmetrics (de lay ,bandwidthandoth…     

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