Accomodating Heterogeneity in a Fully-Reliable Multicast Protocol

 Overview   Partitioning Algorithm Regulation Tree AMCA2 Documents Related work

Overview

Various Internet applications involve multiple parties and usually adopt a one-to-many communication paradigm (multicast). The presence of multiple receivers in a multicast session rises the problem of inter-receiver fairness. Transmitting with a rate which matches the slowest receiver will limit the throughput of other receivers and thus their satisfaction. A multi-rate mechanism can improve the inter-receiver fairness for multicast sessions. The main advantage of a multi-rate scheme is that receivers with different needs can be served at a rate closer to their needs rather than having to match the speed of the slowest receiver. In a multi-rate session, the multicast source can transmit at different rates to different receivers either through a hierarchical scheme (layering) (RLM, LVRM, RLC) or a replicated scheme (destination set grouping, DSG) . In layered multicast, each receiver controls the rate at which it receives the data, usually by using multiple multicast groups. The receivers join and leave groups depending on their path congestion state so the amount of data being received is always appropriate. Layering schemes provide more economical bandwidth usage than DSG schemes, however layering is more complicated and requires efficient hierarchical encoding/decoding algorithms and synchronization among different layers.

 
 Overview   Partitioning Algorithm Regulation Tree AMCA2 Documents Related work


 

Partitioning Algorithm

In both layered and replicated schemes, an explicit or an implicit partitioning of the receivers among subgroups is required. This partitioning is performed so that the receivers satisfaction is maximized. Receivers satisfaction can be quantified using a utility function as the ones proposed in [5] and [6]. Determining the optimal grouping for a multicast session is a difficult problem. In [1], the authors propose a number of grouping heuristics that are guidelines for a multicast source to make its splitting decisions. The authors in [6] consider the optimal partitioning of receivers into groups for multi-rate schemes. They formulated, for a general class of utility function, the partitioning problem as an optimization problem to maximize the sum of receiver utilities. They present a dynamic programming algorithm to solve the partitioning problem, and proved that the solution it finds is optimal. Both of the previous partitioning algorithms require the knowledge of the isolated rates of the different receivers which are not easily obtained in the current Internet. Jiang et al. proposed a special (two-group) DSG protocol to be deployed in the Internet. They proposed a mechanism based on the experienced losses by a receiver to estimate its isolated rate. This mechanism can be used in loss tolerant applications; however the aim of our work is to be able to perform a partitioning in the context of fully reliable multicast applications where we privilege a conservative approach where losses are to be avoided as much as possible.

We proposed a new partitioning algorithm based on the receivers RTT variations instead of their isolated rates. In this context we proposed an other formulation of the utility function using the RTT variations instead of the isolated rates. Our partitioning algorithm, although simple, performs an on-the-fly partitioning depending on the receivers' feedback. Our algorithm approximates and in many cases, achieves the optimal solution without using complex computations. For instance, in [8], a computation is performed on every candidate solution before choosing the one that maximizes the receivers satisfaction. The dynamic programming algorithm proposed in [6] requires less computation effort but still be complex.

 Overview   Partitioning Algorithm Regulation Tree AMCA2 Documents Related work


Accomodating Heterogeneity through a Regulation Tree

In order to avoid the complexity inherent to a layered scheme especially for the case of a fully reliable multicast, we propose to use a replicated scheme. However our scheme differs from the existing replicated schemes in the following main points:

More precisely, our solution consists in a distributed approach where some receivers (replicators) contribute in the replication of the data flow with an appropriate rate to other receivers of lower capacity. In this way, a regulation tree is built with the source as the root, the replicators as intermediate nodes and the remaining receivers as final nodes. In order to minimize bandwidth consumption due to data replication, the regulation tree is built in respect to the physical multicast tree. This is achieved by involving the routers in the regulation tree construction procedure. Every router performs a partition of its downstream links into subgroups and chooses a replicator for every subgroup formed. In addition to the construction of a regulation tree with a topology close to the physical multicast one, executing the partitioning algorithm at the routers instead of the source is more scalable since:


The regulation tree construction is a distributed process where each router performs locally a partitioning of its downstream links into subgroups and designates a replicator for every subgroup formed. Initially, a router maintains a list P0 that contains all of its downstream links. Every time, a downstream link experiences a relative RTT variation greater than a given parameter b, the router creates a new partition Pi with all the links that experienced a relative RTT variation greater than a parameter a (with a<b) and selects a replicator Rep_i for this subgroup.  More details of the regulation tree construction are in this document.

In our approach, a router forwards the source data packets only on the P0 links. Every time, a new subgroup Pi is formed and the corresponding replicator Rep_i is selected, the router notifies this latter to start performing data replication. A replicator Rep_i sends its replicated data packets to the receivers of its corresponding subgroup Pi. Feedbacks from subgroup Pi are sent to their corresponding replicator Rep_i while those arriving on the P0 links are forwarded to the source. In this way the source transmission rate is dedicated by the worst receiver located downstream the P0 links. Once the regulation tree is constructed, the source (and every replicator) sends data to its children with a rate that matches their minimum isolated rate without of course exceeding its reception rate (or equivalently, its parent transmission rate).
 

 Overview   Partitioning Algorithm Regulation Tree AMCA2 Documents Related work


AMCA2

In order to implement our regulation tree scheme, two approaches are possible. One approach could consist in the use of multiple multicast addresses, one per subgroup. Each replicator sends its data flow to a multicast address subscribed to by only its children in the regulation tree. In this case we need to implement a mechanism that would allow receivers (associated to a given replicator) to be aware of the multicast address on which the replicator is transmitting. For the extension of the AMCA protocol, we have adopted an other approach based on the active networking technology. An active router maintains local information about the regulation tree and notifies the replicators to start the data replication. A replicator sends its flow toward its upstream active router which will forward every flow on the appropriate set of links.

The AMCA congestion avoidance protocol has been extended to implement the regulation tree approach using ns-2.1b8ns . For practical considerations and ease of implementation, we chose to limit the number of subgroups maintained by an active router to 2. In this way, routers are not overloaded by the management of multiple subgroups. However, since every router performs locally
its own partitioning procedure, the overall number of subgroups seen by the source can be much higher. For instance, if we consider a two-level multicast tree with N intermediate nodes (routers); if every router performs a 2-subgroup partition of its downstream receivers, we will get (N+1) subgroups for the whole session. Simulation results are provided in this document.

 Overview   Partitioning Algorithm Regulation Tree AMCA2 Documents Related work


Documents

 

Related work

 Overview   Partitioning Algorithm   Regulation Tree    AMCA2   Documents   Related work



 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Nedstat Basic - Free web site statistics