LE-SBCC: Loss-Event Oriented Source-Based Multicast Congestion Control

Congestion control is an important building block of a Quality of Service (QoS) system for multicast-based multimedia services and applications on the World Wide Web. We propose an end-to-end single-rate source-based multicast congestion control scheme (LE-SBCC) for reliable or unreliable multicast transport protocols. It addresses all the pieces of the single-rate multicast congestion control problem including drop-to-zero issues, TCP friendliness and RTT estimation. The scheme design consists of a cascaded set of filters and a rate-based additive-increase multiplicative-decrease (AIMD) module. These filters together transform the multicast tree to appear like a unicast path for the purposes of congestion control. Unlike TCP, the scheme is not self-clocked but acts upon a stream of loss indications (LIs) from receivers. These LIs are filtered to get a stream of loss events (LEs) (S. Floyd et al., in SIGCOMM 2000, Aug. 2000) (at most one per RTT per receiver). This LE stream is further filtered to extract the maximum LEs from any one receiver. Then the scheme effects at most one rate-reduction per round trip time (RTT). A range of results (simulation and experimental) is presented and compared against the mathematical model of the scheme components. Furthermore, we have successfully adapted TFRC (Op. cit) to our scheme, which is important to multimedia services desiring relatively stable rates over short time scales.     

Configurable active multicast congestion control

A multicast congestion control and avoidance scheme is indispensable for group-based applications to fairly share and efficiently use network resources with unicast applications and maintain the stability of the Internet. It is difficult for the traditional pure “end-to-end” solution to address both TCP-friendliness and inter-receiver fairness [T. Jiang, M.H. Ammar, E.W. Zegura, Inter-receiver fairness: a novel performance measure for multicast ABR sessions, in: Proceedings of ACM SIGMETRICS’98; T. Jiang, E.W. Zegura, M. Ammar, Inter-receiver fair multicast communication over the Internet, in: Proceedings of NOSSDAV’99] by using only one multicast group. In this paper, we present a novel active multicast congestion control scheme (AMCC). Significantly different from the popular end-to-end congestion control approach, AMCC is a router-assisted window-based hierarchical one. With flexible configuration of parameters and effective use of network resources such as buffers at the active routers, AMCC cannot only behave as a TCP-friendly single-rate congestion control scheme, but also have the benefits of a multi-rate congestion control scheme to achieve inter-receiver fairness by limiting the effect of congestion on a specific link to a small region. In addition, when it is used with reliable multicast applications, AMCC has the special mechanisms to regulate repair packets, which are not specifically addressed by the previous work. We implement and evaluate our protocol in NS2 [http://www.isi.edu/nsnam/ns/].     

MTCP: scalable TCP-like congestion control for reliable multicast

We present MTCP, a congestion control scheme for large-scale reliable multicast. Congestion control for reliable multicast is important, because of its wide applications in multimedia and collaborative computing, yet non-trivial, because of the potentially large number of receivers involved. Many schemes have been proposed to handle the recovery of lost packets in a scalable manner, but there is little work on the design and implementation of congestion control schemes for reliable multicast. We propose new techniques that can effectively handle instances of congestion occurring simultaneously at various parts of a multicast tree.Our protocol incorporates several novel features: (1) hierarchical congestion status reports that distribute the load of processing feedback from all receivers across the multicast group, (2) the relative time delay concept which overcomes the difficulty of estimating round-trip times in tree-based multicast environments, (3) window-based control that prevents the sender from transmitting faster than packets leave the bottleneck link on the multicast path through which the sender's traffic flows, (4) a retransmission window that regulates the flow of repair packets to prevent local recovery from causing congestion, and (5) a selective acknowledgment scheme that prevents independent (i.e., non-congestion-related) packet loss from reducing the sender's transmission rate. We have implemented MTCP both on UDP in SunOS 5.6 and on the simulator ns, and we have conducted extensive Internet experiments and simulation to test the scalability and inter-fairness properties of the protocol. The encouraging results we have obtained support our confidence that TCP-like congestion control for large-scale reliable multicast is within our grasp.     

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.     

LVMSR: an efficient algorithm to multicast layered video

Layered video is a video-compression technique to encode video data in multiple layers. It typically consists of a base layer and some additional layers that provide enhanced video quality. The multicasting operation of layered video consists of many receivers dynamically joining and leaving different multicast sessions of different layers depending on their network condition. A layered video multicasting system needs to satisfy: (i) bounded end-to-end delay from the video source to each receiver; (ii) minimum total cost; and (iii) minimum delay jitter between the various video streams received by each receiver. The problem of computing such data distribution paths is NP-complete. This paper presents a new heuristic algorithm, called layered video multicast super-tree routing algorithm, with O(Rn²) time complexity and O(R²) message complexity, where n is the number of nodes in the network and R is the receiver group size. Our investigation shows that the multicast data paths computed by our algorithm can always satisfy the delay constraint with reasonably low total cost.     

Extending TCP congestion control to multicast

This paper proposes a new single-rate multicast congestion control scheme named PGMTCC, which has been implemented and investigated in PGM. The primary idea of PGMTCC is to extend Sack TCP congestion control mechanism to multicast in order to make multicast perform almost the same as Sack TCP under all kinds of network conditions. To achieve this goal, first of all, the sender should accurately select a receiver with the worst throughput as a representative (acker) by a simplified equation of TCP throughput. Then the Sack TCP congestion control mechanism, with some modifications to be adapted to multicast, is deployed to take charge of congestion control between the sender and the acker. Moreover, in our scheme, the problem of the feedback suppression is considered and solved by a selective suppression mechanism of feedback. NS2 is used to test and investigate the performance of our scheme. As expected, PGMTCC performs almost like Sack TCP under all kinds of conditions. We believe that it is TCP-friendly, robust and scalable.     

Privacy-preserving identity-based broadcast encryption

Broadcast encryption enables a broadcaster to encrypt messages and transmit them to some subset S of authorized users. In identity-based broadcast encryption schemes, a broadcasting sender typically encrypts a message by combining public identities of receivers in S and system parameters. However, previous identity-based broadcast encryption schemes have not been concerned about preserving the privacy of receivers. Consequently, all of the identities of broadcast receivers in S are exposed to the public in the previous schemes, which may be subject to attacks on user privacy in lots of pragmatic applications. We propose a novel privacy-preserving identity-based broadcast encryption scheme against an active attacker. The proposed scheme protects the privacy of receivers of broadcasted messages by hiding the identities of receivers in S. Additionally, it achieves less storage and computation costs required to encrypt and decrypt the broadcast message, compared to the previous identity-based broadcast encryption schemes that do not provide user privacy.     

TFAMCC:TCP友好的自适应分层多播拥塞控制机制

满足接收端异构性的分层多播传输机制,源端一般只用于编码及各层数据流的传输,而拥塞控制主要在接收端来完成。这里提出一种源端与接收端协同作用共同完成多播的拥塞控制机制。源端根据接收端的反馈调节多播层次数目及各层传输速率,接收端根据TCP吞吐量模型计算本地允许带宽,进行层次的接收及形成对源端调节的反馈。经试验证明,此机制具有TCP友好性、接收端带宽充分利用及良好的可扩展性。     

Network coding-based reliable multicast in wireless networks

Reliable multicast, the lossless dissemination of data from one sender to a group of receivers, has a wide range of important applications. Recently, network coding has been applied to the reliable multicast in wireless networks, where multiple lost packets with distinct intended receivers are XOR-ed together as one packet and forwarded via single retransmission, resulting in a significant reduction of bandwidth consumption. However, the simple XOR operation cannot fully exploit the potential coding opportunities and finding the optimal set of lost packets for XOR-ing is a complex NP-complete optimization problem. In this work, we intend to move beyond the simple XOR to more general coding operations. Specifically, we propose two new schemes (a static scheme which repeatedly retransmits one coding packet until all intended receivers receive it and a dynamic scheme which updates the coding packet once one or more receivers receive it) to encode packets with more general coding operations, which not only can encode lost packets with common intended receivers together to fully exploit the potential coding opportunities but also have polynomial-time complexity. We demonstrate, through both analytical and simulation results, that the proposed schemes can more greatly reduce the bandwidth requirement than the available coding-based schemes, especially in the case of high packet loss probabilities and a larger number of receivers. This reduction can vary from a few percents to over 15% depending on the packet loss probabilities and the number of receivers.     

Aggregate message authentication codes (AMACs) with on-the-fly verification

Aggregate message authentication codes (AMACs) merge multiple authenticators for multiple receivers in multicast networks. We investigate this security notion, revise the definition, derive the lower bound, and present a generic construction through Bloom filters. Different from former research, we especially focus on the new property of AMACs: on-the-fly verification, which means that given the aggregated tag, each single message can be verified without obtaining other messages, i.e., the time for verifying a single message takes time complexity $\mathcal{O }(1)$ O ( 1 ) , compared to regular MAC schemes. We derive the security lower bound of such type of AMACs and present a generic approach to build them from essentially any standard MAC scheme by Bloom filter technique. Moreover, we achieve the theoretical lower bound on security strength by adopting optimal compressed Bloom filters.     

Distributed max–min flow control for multi-rate overlay multicast

We present a distributed algorithm to compute bandwidth max–min fair rates in an overlay multicast network supporting multi-rate data delivery. The proposed algorithm is scalable in that it does not require each logical link to maintain the saturation status of all sessions and virtual sessions traveling through it, stable in that it converges asymptotically to the desired equilibrium satisfying the minimum plus max–min fairness even in the presence of heterogeneous round-trip delays, and has explicit link buffer control in that the buffer occupancy of every bottlenecked link in the network asymptotically converges to the pre-defined value. The algorithm is based on PI (proportional integral) control in the feedback control theory and by appealing to the Nyquist stability criterion, a usable stability condition is derived in the presence of sources with heterogeneous round-trip delays. In addition, we propose an efficient feedback consolidation algorithm which is computationally simpler than its hard-synchronization based counterpart and eliminates unnecessary consolidation delay by preventing it from awaiting backward control packets that do not directly contribute to the session rate. Through simulations we further verify the analytical results and the performance of the proposed multi-rate multicast flow control scheme based on these two algorithms.     

Optimal adaptive channel scheduling for scalable video broadcasting over MIMO wireless networks

Video broadcasting is an efficient way to deliver video content to multiple receivers. However, due to heterogeneous channel conditions in MIMO wireless networks, it is challenging for video broadcasting to map scalable video layers to proper MIMO transmit antennas to minimize the average overall video transmission distortion. In this paper, we investigate the channel scheduling problem for broadcasting scalable video content over MIMO wireless networks. An adaptive channel scheduling based unequal error protection (UEP) video broadcasting scheme is proposed. In the scheme, video layers are protected unequally by being mapped to appropriate antennas, and the average overall distortion of all receivers is minimized. We formulate this scheme into a non-linear combinatorial optimization problem. It is not practical to solve the problem by an exhaustive search method with heavy computational complexity. Instead, an efficient branch-and-bound based channel scheduling algorithm, named TBCS, is developed. TBCS finds the global optimal solution with much lower complexity. The complexity is further reduced by relaxing the termination condition of TBCS, which produces a (1 − ε)-optimal solution. Experimental results demonstrate both the effectiveness and efficiency of our proposed scheme and algorithm. As compared with some existing channel scheduling methods, TBCS improves the quality of video broadcasting across all receivers significantly.     

基于AIMD算法的分层多播拥塞控制

提出了一种基于AIMD算法的分层多播拥塞控制算法．算法借助AIMD算法具有的良好TCP兼容性和稳定性，采用慢增慢减的速率调节原则来防止TCP中速率减半策略所带来的速率振荡．为避免反馈处理带来的复杂性和可扩缩性问题，提出了无须反馈的收方至发方间往返时延估计方法．算法采用类似TCP的慢启动算法来提高链路的利用率和收敛速度．通过仿真评估得出，算法对TCP流、不同多播流均表现出理想的公平性，并有很高的带宽利用率和良好的稳定性．     

Distributed dynamic mobile multicast

Traditional mobile multicast schemes have either high multicast tree reconfiguration cost or high packet delivery cost. The former affects service disruption time while the latter affects packet delivery delay. Although existing region-based mobile multicast schemes offer a trade-off between two costs to some extent, most of them do not determine the size of the service range, which is critical to network performance. In this paper, we propose a novel approach, called Distributed Dynamic Mobile Multicast (D²M²), to dynamically determine the optimal service range according to the mobility and service characteristics of a user. We derive an analytical model to formulate the costs of multicast tree reconfiguration and multicast packet delivery. The model is based on a Markov chain that analyzes a mobile node’s movement in a 2D mesh network. As the complexity of computing steady probability is high, we aggregate the Markov states by leveraging mobility symmetry. Simulation shows that the network performance is enhanced through D²M².     

Network-Supported Layered Multicast Transport Control for Streaming Media

Multicast is very efficient in distributing a large volume of data to multiple receivers over the Internet. Layered multicast helps solve the heterogeneity problem in multicast delivery. Extensive work has been done in the area of layered multicast, for both congestion control and error control. In this paper, we focus on network-supported protocols for streaming media. Most of the existing work solves the congestion control and error control problems separately and does not give an integrated efficient solution. In this paper, after reviewing related work, we introduce our proposed protocols, namely, router-assisted layered multicast (RALM) and router-assisted layered FEC (RALF). The former is a congestion control protocol, whereas the latter is an error control protocol. They work under the same framework and provide an integrated solution. We also extend RALM to RALM-II, which is compatible with transmission control protocol (TCP) traffic. We analyze the complexity of the proposed protocols in the network and investigate their performance through simulations. We show that our solution achieves significant performance gains with reasonable additional complexity.     

无线接入网络中组播拥塞控制机制的研究

随着无线技术的迅速发展和无线设备的日益普及,如何有效地提高传统的组播拥塞控制机制在无线网络中的性能是一个急需解决的课题。本文提出了一种新的组播拥塞控制机制,该机制通过对无线缝路上的随机丢失分组和网络中的拥塞丢失分组进行辨别并采取相应的处理措施,有效地提高了传统的组播拥塞控制机制在无线网络中的性能,同时保证了在有线网络环境中的TCP友好性。     

ANLMCC--一种基于主动网的分层多播拥塞控制方案

多媒体多播应用在Internet上的广泛部署对多播拥塞控制提出了要求．分层多播是适应网络异构性较有效的方案．针对现有分层多播大多存在拥塞响应延时大、吞吐率抖动剧烈和不满足TCP友好的问题。提出一种新的基于主动网的分层多播拥塞控制方案(ANLMCC),利用主动网灵活的服务定制能力,采用主动标记分层、优先级分层过滤,以及主动节点间逐跳的交互信令机制,大大改进了分层多播的性能．仿真实验表明,ANLMCC具有较快的拥塞响应速度、较好的稳定性和TCP友好的优点．     

Reconfigurable multicast routing for Networks on Chip

Several unicast and multicast routing protocols have been presented for MPSoCs. Multicast protocols in NoCs are used for cache coherency in distributed shared memory systems, replication, barrier synchronization, or clock synchronization. Unicast routing algorithms are not suitable for multicast, as they increase traffic, congestion and deadlock probability. Famous multicast schemes such as tree-based and path-based schemes have been proposed originally for multicomputers and recently adapted to NoCs. In this paper, we propose a switch tree-based multicast scheme, called STBA. This method supports tree construction with a minimum number of routers. Our evaluation results reveal that, for both synthetic and real traffic loads, the proposed scheme outperforms the baseline tree-based routing scheme in a conventional mesh by up to 41% and reduces power consumption by up to 29%.     

Block-level packet recovery with network coding for wireless reliable multicast

Reliable multicast, the lossless dissemination of data from one sender to a group of receivers, has a wide range of important applications in wireless networks. In this paper, we are interested in the reliable single-hop wireless multicast. As the wireless channel is inherently error prone, it is challenging to achieve high channel utilization in reliable wireless multicast. Most schemes proposed by now for reliable single-hop wireless multicast share the same weakness in that an entire frame will be retransmitted even if it has single error bit. To alleviate this problem, this paper presents an efficient reliable multicast scheme based on block-level ARQ and network coding technique. The new scheme breaks the data stream into blocks and retransmits only erroneous blocks (rather than the entire corrupted frame), where the novel network coding technique is further adopted to minimize the total number of block retransmissions. The theoretical analysis and simulation are conducted to demonstrate the performance of the new scheme and also some typical available schemes in terms of their bandwidth efficiency. The simulation and theoretical results indicate that new reliable wireless multicast scheme can significantly enhance the channel utilization, especially in the scenarios where bit error rate is high and the number of receivers is large.