Microsoft word - mohamede_multicast.doc

Multicast Congestion Control for Multimedia Collaborative
Applications in Packet Switched Networks
emohamed@uaeu.ac.ae, wahab@cs.odu.edu Abstract
and links differ in bandwidths) and dynamics (workload varies with time). We introduce a solution for controlling We investigate the problem of congestion control for congestion by organizing the destinations into multiple multicast traffic over datagram packet switched networks multicast groups based on the capabilities of the and present an end-to-end solution to it. The focus of our destinations and their network paths from the source. study is on multimedia collaborative applications. The Finally, we present an analytic study to evaluate our group members of such applications, typically, span a heterogeneous inter-network, where routers and links may The rest of this paper is organized as follows. General vary widely in their capabilities. Recently, two end-to-end principles of congestion control are given in Section 2. approaches have been introduced for multicast congestion Section 3 is an introduction to multicast congestion control: hierarchical multicast (a window based control. In Section 4, we present our new technique. In approach), and multiple groups (a rate based approach). Section 5, we give a model for multicast congestion In this paper, we introduce a new end-to-end technique control and we present an analytical study that evaluates for multicast congestion control that utilizes multiple various approaches to this problem. Section 6 presents the groups and is window based. We have conducted an analytical study to evaluate our work, which shows encouraging results compared to other techniques. 2. Principles and techniques of congestion
1. Introduction
The success of many components of multimedia collaborative applications depends heavily on the performance of the underlying network. For example, a timely delivery of the data to the different participants of a collaborative session is essential to many components such as audio and video. Also, a low packet loss helps increase the quality of the perceived audio and video Figure 1. Congestion: incoming traffic ≥ outgoing streams. In many situations some parts of the network may get congested, degrading the overall performance of the network. For best effort networks where there is no Congestion occurs when the incoming traffic at a node admission control for network traffic, all applications approaches or exceeds that of the outgoing traffic (Figure. running over the network should cooperate to avoid 1). In such case, the length of the queue at this node grows congestion and control it would it happen [10]. indefinitely. Since routers’ queues are of finite lengths, In this paper, we consider end-to-end solutions for some of the incoming traffic may get dropped. The congestion control in multicast communications for problem gets even worse when the sources try to multimedia collaborative applications over datagram compensate for the lost packets and level up their packet switched networks. Normally, the participants of a transmission rates. Increasing the queue size may not help collaborative session may span the entire network, which much, as it has been shown in a previous study that even we assume heterogeneous (routers differ in capabilities with an infinite queue size congestion gets worse, since by * The author has moved to the College of Information Technology, United Arab Emirates University. the time packets arrive to the queue front they already data and drops some others. It is the semantic of the have been timed out and duplicates have been sent [11]. application that mandates what to choose. For example, Many solutions have been introduced to control video and audio applications may choose better delay over network congestion [1, 3, 8, 9, 16]. Basically, congestion quality to meet their real time nature, while a shared white control schemes can be classified into open loop and board may sacrifice the delay in favor of the quality. closed loop [18]. Solutions based on the open loop approach do not monitor the dynamics of the network and 3. Multicast congestion control
they do not depend on any feedback from the congested spots. Instead, they try to prevent the problem of congestion from ever occurring. In order to prevent congestion, open loop protocols generally have mechanisms for admitting traffic into the network and Closed loop congestion control solutions depend on monitoring the network, detecting congestion, and passing a feedback message that gives congestion information to the source. The source uses the feedback to adapt its transmission rate. Detection of congestion can be based on monitoring the network for the number of dropped packets, the average queue size, or the average packet delay. Congestion feedback can be explicit or implicit. Explicit feedback sends congestion information from the congestion spot to the source, while in implicit feedback the source conceives the presence of congestion along the Figure. 2. Congestion in multicast communications path to a destination when an expected acknowledgement message is timed out or is received late [12]. The problem of congestion control is magnified in In response to congestion information, sources have multicast communication since traffic originates from a two approaches to control the outgoing traffic. The first is single source and is distributed along many paths to many window based while the other is rate based. A window destinations. In a heterogeneous network, some of these based approach tries to limit the amount of data in paths may be congested while others may not, leaving the transient. A window based technique can be considered as source with a problem to decide at which rate it should a closed loop controller that uses implicit feedback. This send [2]. Moreover, sending a feedback from all approach is suitable for best effort packet switched destinations to the source may result in a feedback networks such as the Internet, where network routers do not provide much help in congestion control. An example In Figure. 2, only one links is congested while the of this approach is the sliding window mechanism used in others are normal. Three solutions exist to this problem: remove the destinations along the congested path from the Rate based approach, on the other hand, can be collaboration session, adapt the sending rate to that of the considered as open loop. Techniques following this slowest of the destinations, and send to each destination approach try to regulate the average rate of data by its own rate. The first solution may seem valid to solve transmission by smoothing down the burstiness in the some denial of service attacks. The solution, however, data. Generally, rate based approach works well in may not be acceptable in many applications where all networks that support admission control (ATM network is participants of the collaboration session must remain. an instance). Before start sending, the source and the Because of its lack of applicability in many cases, this network agree on a transmission rate, which the source solution will not be considered any further in our work. sends at. An instance of rate based approach is the leaky The second solution is not fair as it may slow down destinations that do not suffer from any congestion. In controlling congestion, using a rate based or window Moreover, and as a previous study has shown [5], this based technique, a source tries to lower its throughput to solution requires maintaining a window per destination, as meet that of the congested path. It should be noted that having only one window for all destinations unnecessarily there is a trade off between time and quality. When restricts the throughput more than that is required by the choosing to sacrifice time, the source sends data with a congested path. While seems attractive, the third solution slower rate, which results in longer delay. On the other places a large overhead on the source to keep track of hand, on sacrificing quality the source sends some of the each destination. However, a modification to this approach by grouping destinations based on the condition based on their connections to the source. The technique of the network connections from the source to the we introduce is window based in which the source destinations dramatically reduces such overhead. This maintains a window per group. To avoid feedback solution will be investigated later in this paper. implosion, we adopt a hierarchical approach in which a Many techniques have been given to control multicast representative is assigned for each group. A group congestion [5, 6, 13, 17]. Recently, two techniques have representative is responsible for collecting feedback from been proposed for end-to-end multicast congestion the rest of its group members and sending the collective control. The first utilizes multiple multicast groups and the feedback to the source. To adapt to network dynamics, our second is based on a hierarchical approach. Utilizing solution allows destinations to migrate from one group to multiple groups is an open loop rate based technique that another and it permits groups’ splitting and merging. Last, allows destinations to control congestion [17]. The we consider the cases of real time and reliable traffics. technique assumes that data can be organized into layers. There are three phases that can be considered when Each data layer then is oriented to a separate multicast developing our technique: startup, steady state, and group. Destinations join the appropriate number of layers adapting to congestion. Each of these three phases is that meet the available bandwidth and the transmission quality required. When detecting congestion in the network, a destination quits some of its layers. In order to 4.1. Startup phase
help deciding which group a destination should join, the source multicasts probe messages periodically to At the startup phase, the source multicasts the first destinations. This technique addresses the heterogeneity of packet to all destinations and starts a timeout timer. The the network and provides an efficient way to control source, then, waits for feedbacks from all destinations. For congestion. The number of multicast groups, however, is each feedback it receives, the source calculates the round limited since data can be organized into a few layers. trip time for the destination the feedback received from. Also, the technique addresses the problem of best effort After the timeout timer expires or after receiving applications where congestion is dealt with by sacrificing feedbacks from all destinations, the source categorizes the the quality of the data and does not provide an answer for destinations to groups depending on their roundtrip times reliable communications where packet retransmission is and assigns the fastest destination within each group as a required. Moreover, it assumes that the application data representative for the group. For each group, the source can be organized in layers, an assumption that may not be announces the representative to the rest of the destinations The second approach is window based that maintains a window per each destination [5]. It organizes destinations 4.2. Steady state phase
in a tree-like structure, with the source at the root of the tree. Each parent keeps a separate window for each of its At the steady state phase, the source maintains a children and advances the window when it receives an window per group. The source sends each group its data acknowledgment from the corresponding child. The independent of other groups. All destinations of a group aggregate feedback then is directed by the parent to its send their feedback to the group representative, which in immediate parent, and the process continues upward until turn sends the collective feedback to the source. The it reaches the source. The main motivation behind this source uses the representative feedback to adjust the group approach is to avoid feedback implosion at the source by window. Periodically, the source sends the group letting some of the destinations (intermediate nodes within representatives reports about the status of other groups the tree) to handle some of the feedback. The technique, (their window sizes and RTT) in order to provide however, suffers from a large overhead in building and representatives with information necessary to allow maintaining the tree. Moreover, it restricts the multicast destination migration between groups, group merging, and session to proceed with the most congested path. group splitting. After organizing destinations into groups, the source multicasts each group its data based on the 4. Multicast congestion control: A new window information maintained for the group.
technique
Our scheme considers two types of data transmissions: real time and reliable transmissions. Figure. 3 gives an In this section, we give an end-to-end solution for the example of packet transmission for real time applications problem of congestion control in multicast communication such as video and audio, while Figure. 4 gives the same to support multimedia collaborative applications. Our example for reliable transmission. In real time solution addresses network heterogeneity. It utilizes transmission, packets are dropped off for slow group (the multiple multicasts to organize destinations into groups penalty is quality), while they are transmitted later in the reliable transmission (the penalty is delay). It should be when the source detects two groups with the same noted that duplicate of the data are sent to the groups. In capability—having the same window—the source asks the the worst case, each group contains only one destination two groups to merge into one, and one of the two and the situation degenerate to multiple unicast representatives is assigned as the new group connections much similar to multiple TCP connections. In the best case, all destinations exist in one group, which can happen in homogeneous environments. Normally, the 5. Performance Evaluation
resultant situation lies between these two extremes. To evaluate our new technique we developed a simple, 4.3. Adapting to variations in the network phase
yet expressive and accurate analytical model of the congestion control problem. The goal of any congestion Variation on network status can be inferred from the control technique is to avoid the network congestion while round trip time and packet loss (which can be assumed by maximizing the throughput at the receiving end. Thus, we a missing feedback). Adapting to these variations can be use the throughput at the receiving end as the performance done in two ways: intra-group adaptation and inter-group measure in our study. In our study, we only consider the adaptation. Intra-group adaptation is required when most case of real time communications—retransmissions are of the group members experience the same variation and not allowed. We calculate the throughput under three can be performed by adjusting the group window cases: no control (source is sending regardless of the maintained at the source. On the other hand, Inter-groups status of the connections from the source to the adaptation is required when few members of the group destinations), going with the slowest destination, and experience a variation that does not affect the rest. In this using multiple groups as described in our new technique. case, those members can move to another group, or can In our model, we assume that there is a path from the start another group (group splitting). Based on the source to each group. Every path is modeled as a server information provided by the destinations and the source to that has a queue of finite length. The service time, the the representatives of the groups, three cases may happen. arrival rate, and the maximum queue length differ from First, a slow/fast destination can migrate to a slower/faster one server to another. Packets that are sent from the group if such group exists. Second, a group can be split to source towards a group of destinations go through the path several groups. Third, two or more groups can be merged. from the source towards the group destinations, where the A destination can migrate to another group if the packets are queued and then served by the server within representative of the destination’s current group determines that the destination does not belong to the The average throughput (λavg) is the total throughput group and should be moved to another one. This can for all destinations divided by the number of destinations. happen if the destination network connection to the source Given the destination throughput λi and the number of has been changed. If a destination connection to the destinations n, the average throughput can be given as: source gets less capable, the destination should be migrated to a slower group in order to avoid slowing down the rest of its current group. After its migration to a slower group, the destination should ignore all packets it has already received in its previous faster group. The destination, however, should send its feedback to the new For unicast communication, increasing the sending rate representative. On moving to a faster group, and in the increases the loss probability and consequently decreases case of reliable transmission, the destination should the destination throughput. Assuming an M/M/1/N continue its membership in its previous slower group to system—inter-arrival is exponentially distributed with a receive the data that has been sent to the faster one. In the rate of λ, service times are exponentially distributed with a case of real time transmission, the destination joins the mean of 1/µ, number of servers is 1, and buffer size is N packets—the loss probability can be related to the sending Based on the information sent from the source to the groups’ representatives, groups can be split or merged. When many of members of the groups experience some variation that does not apply to the rest of the group, and provided that there no other group with the same capability of these destinations, group splitting is required. In this case, a new group is formed and a representative is selected and announced to the source. On the other hand, The last equation gives the throughput achieved by our new approach. The throughput per group is limited to the slowest destination in the group and the overall throughput is given as the average of groups’ throughputs. The last two equations result in a nonlinear equation in P, which can be solved using iteration or trial and error. In real time, it is most likely that retransmission of lost packets is not allowed since the delay encountered in the retransmission is not affordable. In the case of no control, the throughput is limited by the capacities of the links from the source to destinations. Hence, the average throughput per destination can be given as: Where: λs is the sending rate, λi is the capacity of the link from the source to destination i, n is the number of destinations, and Pi is the loss probability of path i and is Figure. 3. Throughput in real time transmission. As the last equation illustrates, increasing the sending rate increases the received throughput until the capacities Figure. 3 compares our approach against the no control of the links and/or the destinations’ processing powers are and the going with the slowest approaches. The figure reached. Beyond this limit, increasing the sending rate assumes 9 destinations with capacities of 10, 12, 13, 50, results only on wasting the network bandwidth since the 55, 60, 100, 120, and 110 K bytes/second. All destinations extra packets will be dropped at the bottlenecks. have the same buffer size (8 packets). When grouping Going with the slowest destination, the throughput is using the new approach, we assume three groups that limited to the slowest destination. Hence, the average organize destinations based on their capacities. Also, we assume that the source limits its sending rate to be less than the capacity of the corresponding links. As the figure shows, limiting the sending rate to the slowest limits the throughput to a very small number, wasting the capacities Where: λs is the sending rate and it is ≤ λmin (the of the other destinations. Adopting a no control approach minimum link capacity from the source to all brings the throughput to zero for the destinations that have sending rate approaching the capacities of the links (the i is the loss probability of the bottleneck path in the group and is given in equations. stair case effect shown in the figure is due to this The last equation shows the performance of going with phenomenon). Using our new approach, the throughput the slowest destination approach. In this case, the average obtained is much better than that obtained when going throughput is limited to the most severe bottleneck. with the slowest destinations or that achieved if we do not Using our new approach, the average throughput per 6. Conclusion and future work
MIN (λ ,m × MIN mi In this paper we have studied the problem of congestion control in multicast communication and we have introduced a new technique based on using multiple multicast groups for it. Our new technique is window Where: λs is the sending rate, λj is the capacity of the based that establishes a window per group. Data are sent link from the source to destination j, g is the number of to every group independent of the other groups. In order to avoid overloading the source with destinations’ i is the number of destinations in group i, n is the feedback, a representative per group is designated to i is the loss probability for the collect the feedback from the rest of the group members and relay the feedback to the source. We have introduced solutions to allow destinations to migrate between groups. [9] P. Mishra, H. kanakia, and S. Tripathi, “On Hop-by-Hop We also have presented techniques for merging and Rate-Based Congestion Control,” IEEE/ACM Transactions splitting groups. To evaluate our approach, we have on Networking, vol. 4, no. 2, April 1996, pp. 224-239. presented an analytical study that compares the new technique with the cases of no control and going with the E. Mohamed, “Multicast Services for Multimedia Collaborative Applications,” Ph.D. Dissertation, Computer slowest destination in real time communications where Science Department, Old Dominion University, December retransmissions are not allowed. We have used the throughput at the destinations as the performance measure. Results of our study show that our technique [11] J. Nagle, “Congestion Control in IP/TCP Internetworks,” performs much better than the other two approaches. Computer Communication Review, vol. 25, no. 1, January Another measure that can be used to evaluate the various approaches is the delay experienced by the destinations. For reliable transmissions (using retransmissions), there G. Pal and S. Agrawal, “Window-Based Congestion are two main schemes: go back n, and selective repeat. Control in a Packet Switched Network with Voice and Data Transmission,” Computer Communications, vol. 19, no. 6- More work is needed to analytically evaluate the performance of our technique under these circumstances. [13] I. Rhee, N. Balaguru, and G. Rouskas, “MTCP: Scalable 7. References
TCP-like Congestion Control for Reliable Multicast,” Proc. Infocom’99, New York, NY, USA, March 1999. [1] E. Altman, T. Basar, and R. Srikant, “Congestion Control as a Stochastic Control Problem with Action Delays,” [14] M. Schwartz, “Telecommunication Networks: Protocols, Automatica, vol. 35, no. 12, December 1999, pp. 1937- Modeling and Analysis,” Addison-Wesley, 1987. [15] J. Turner, "New Directions in Communications (or Which [2] S. Bhattacharyya, D. Towsley, and J. Kurose, “The Loss Way to the Information Age)," IEEE Communication Path Multiplicity Problem in Multicast Congestion Magazine, vol. 24, October 1986, pp. 8-15. Control,” Proc. IEEE Infocom'99, New York, NY, USA, N. Venkitaraman, T. Kim, K. Lee, S. Lu, and V. Bharghavan, “Design and Evaluation of Congestion Control [3 ] R. Cigno and M. Gerla, “Modeling Window Based Algorithms in the Future Inernet,” Proc. Sigmetrics’99, Congestion Control Protocols with Many Flows,” Atlanta, GA, USA, May 1999, pp. 212-213. Performance evaluation, vol. 36, no. 1, August 1999, pp. [17] L. Vicisano, L. Rizzo, J. Crowcroft, “TCP-like Congestion Control for Layered Multicast Data Transfer,” Proc. IEEE [4] S. Floyd and K. Fall, “Promoting the Use of End-to-end Infocom'98, San Francisco, CA, USA, April 1998. Congestion Control in the Internet,” IEEE/ACM transactions on networking, vol. 7, no. 4, August 1999, pp. [18] C. Yang and A. Reddy, “A Taxonomy for Congestion Control Algorithms in Packet Switching Networks,” IEEE [5] S. Golestani and K. Sabnani, “Fundamental Observations Network, vol. 9, no. 4, July 1995, pp. 34-45. on Multicast Congestion Control in the Internet,” Proc. Infocom’99, New York, NY, USA, March 1999. [6] J. Huang, C. Yang, and N. Fang, “A Novel Congestion Control Mechanism for Multicast Real-time Connections,” Computer communications, vol. 22, no. 1, January 1999, pp. 56-72. [7] V. Jacobson, “Congestion Avoidance and Control,” Proc. ACM SIGCOMM’88, Stanford, CA, USA, vol. 18, no. 4, August 1988. [8] H. Kanakia, P. Mishra, and A. Reibman, “An Adaptive Congestion Control Scheme for Real Time Packet Video Tranport,” IEEE/ACM transactions on networking, vol. 3, no. 6, December 1995, pp. 671-682.

Source: http://faculty.uaeu.ac.ae/~emohamed/publications/mcastCongCtrl.pdf