Data Encoding

• A Digital Fountain Approach to Reliable Distribution of Bulk Data, SIGCOMM 1998
  By John W. Byers, Michael Luby, Michael Mitzenmacher, Ashutosh Rege
   
  Key property of a gitial fountain -- ideally, the source data can be reconstructed intact from any subset of the encoding packets equal in total size to the source data.
  2 types of erasure codes:
  • Reed Solomon Code -- requires large encoding/decoding time, need k packets to recover k packets.
    
  • Tornado code -- small encoding/decoding time, need k + e (e << k) to recover k packets.
  With Tornado coding, the source can set the data, including original data and redundant encoding data, in cycles. Receivers can begin receiving any time. As long as they get enough distinct packets, they can recover original data.
  The paper includes an implementation of a reliable distribution protocol based on layer multicast (each layer for different rate with higher layer including lower layers).

Single-Rate Multicast Congestion Control

• Achieving bounded fairness for multicast and TCP traffic in the Internet, SIGCOMM 1998
  Huayan Amy Wang and Mischa Schwartz (Columbia University)
   
  Define essential fairness with TCP with a restricted topology: all paths to receivers have the same average RTT.
  Uses a method similar to loss event to detect congestion with 2RTT instead of RTT. 2RTT is simulation measurement result.
  Basic idea: with n receivers sending congestion signals, the source accepts each signal with probability 1/n. Its an ACK-based and windows-based protocol.
  Provides analytical proof to TCP fairness and inter-session fairness.

• Inter-Receiver Fairness: A Novel Performance Measure for Multicast ABR Sessions, SIGMETRIC 1998
  Tianji Jiang, Mostafa H. Ammar, Ellen W. Zegura
   
  Assuming the receivers can tolerate loss to some extent, e.g. those in video/audio transmission, this paper proposes a scheme to optimize the source transfer rate larger than the minimum bottleneck bandwidth. Specifically for ATM, the excessive packets on bottlenecks will be dropped before getting into queues and thus won't affect other flows at the switch. Bottleneck rates feedback by receivers are to be aggregated by the ATM switches. The source need bottleneck rates from all receivers, though perhaps classified by switches, to calculate the optimal rate. If the receivers cannot tolerate loss, the scheme will degrade to having the lowest bottleneck bandwidth as source rate.
  My question: if a receiver can tolerate loss to bandwidth of w', just set the source rate to min (w'). What's the point of finding the optimal point according to the inter-receiver fairness definition? The definition makes sense only when the excessive packets can affect other flows (how to define the effect analytically?).

• A Multicast Congestion Control Mechanism Using Representatives,Proceedings of the IEEE ISCC'98
  Dante DeLucia, Katia Obraczka
   
  

• Multicast Feedback Suppression Using Representatives, IEEE Infocom97
  Dante DeLucia, Katia Obraczka
   
  

• A Rate-based End-to-end Multicast Congestion Control Protocol, Proceedings of IEEE Symposium on Computer and Communications (ISCC 2000), July 2000
  Sherlia Shi, Marcel Waldvogel,
   
  There two types of feedback aggregation in this scheme. The first one is, the source multicasts the metric (1/(RTT.sqrt(p))) of the agent (the worst receiver) to all receivers. Only those receivers with its metric worse than the agent's will send feedback. The second one is, the source chooses only the feedback with the worst metric among those from all receivers. The source needs to maintain ACK-like traffic (called positive feeback) with the agent.
  There are some unsolved problems: estimation of various RTT between source and different receivers, etc. The situation of agent's going offline has not been fully discussed. For example, there can be a case that the current agent with metric M is absent, whereas other receivers have metrics much higher than M. Although the simulation shows that the scheme can handle it, there is no description of how to do that.

• Extending Equation-Based Congestion Control to Multicast Applications , SIGCOMM 2001
  Joerg Widmer, Mark Handley
   
  

• pgmcc: A TCP-friendly Single-Rate Multicast Congestion Control Scheme, SIGCOMM 2000
  Luigi Rizzo
   
  

• A TCP Friendly, Rate-Based Mechanism for Nack-Oriented Reliable Multicast Congestion Control, Globecom 2001
  Joseph P. Macker, R. Brian Adamson
   
  The receivers calcuate their estimated throughput rates with RTT and loss rates. The source keeps a pool of representative and choose the one with the lowest throughput rate as the Worst Path Representative to react on. It needs control message from source to receivers, containing 5 types of information, e.g. RTT, current rate etc. It talks about feedback suppression.

Multi-Rate Multicast Congestion Control

• Inter-Receiver Fair Multicast Communication Over the Internet, NOSSDAV 1999
  Tianji Jiang, Ellen W. Zegura, Mostafa Ammar
   
  Provides two groups: B-group and V-group. The B-group runs at the lowest bandwidth allowed by the application. V-group uses variable bandwidth while trying to achieve max inter-receiver fairness. Group size and receiver isolated rates need to be estimated by polling (based on "Scalable Feedback Control for Multicast Video Distribution in the Internet"). Receivers can switch group, or have to quit the session, according to their isolated rates.
  The benefit of inter-receiver fairness is still not carefully addressed.

• On the Use of Destination Set Grouping to Improve Inter-Receiver Fairness for Multicast ABR Sessions, Infocom 2000
  Tianji Jiang (Georgia Institute of Technology), Mostafa Ammar (Georgia Institute of Technology), Ellen Zegura (Georgia Institute of Technology)
   
  Within the aggregate bandwidth of the fastest receiver, in 3 heuristic steps, the source splits a single multicast group to multiple groups in order to improve the inter-receiver fairness. It also defines an expression to evalute the effect of the scheme on the whole network.
  Group merging is only touched fundementally here. The scheme is base on ATM, but the principle may be extened to Internet.

• Fine-Grained Layered Multicast, Infocom 2001
  John Byers (Boston University), Michael Luby (Digital Fountain), Michael Mitzenmacher (Harvard University)
   
  The scheme uses non-cumulative layer with Fibonacci-based bandwidth assignment. A receiver subscribes to layer i (smallest unsubscribed layer) and unsubscribe layer i - 1 and i - 2 to achieve additive increase, unsubscribes the highest layer to simulate multiplicative decrease. The bandwidth assignment and the subscription/unsubscription policy can be tuned for different applications.

• STAIR: Practical AIMD Multirate Multicast Congestion Control, NGC 2001
  John W. Byers (Boston University), Gu-In Kwon (Boston University)
   
  Given bandwidth K = a ^ j + r, a ^ j is provided with cumulative layering, r with non-cumulative layering proposed by fine grained layered multicast. Furthermore, there are some dynamic layers, called "stair layers", classified by RTT. In these layers, beginning from 1 pKT / RTT, bandwidth increases by 1 pkt / RTT until a maximum value, then back to start. A receiver stays in a chosen stair layer according to its RTT. No loss at the stair layer's maximum point means the need to subscribe to a higher non-cumulative layer. Loss means to unsubscribe from the highest non-cumulative and cumulative layer. Layer adjustment is needed if r reaches a ^ (j + 1).

• Rendezvous Points Based Layered Multicast, IEICE Trans. Commun., Vol. E84-B, No. 12, Dec. 2001.
  Tran Ha NGUYEN,Kiyohide NAKAUCHI,Masato KAWADA,Hiroyuki MORIKAWA,Tomonori AOYAMA
   
  Layered multicast congestion control use multiple multicast groups. However, there may be a problem that these groups take different routes. This paper proposed an enhanced layered multicast congestion control scheme for PIM-SM and CBT, which can deal with the situation that different groups choose different RPs and thus different routes.

Multicast Congestion Control Analysis

• Architectural Issues for Multicast Congestion Control, NOSSDAV 1999
  Anindya Basu and S. Jamaloddin Golestani
   
  General discussion about 3 components: feedback consolication, RTT measurement and loss detection. However, it misses some realistic restriction of multicast, like, communcation between receivers is not easy. Therefore, to me, at current stage, it does not make much sense.

• Pathological Behaviors for RLM and RLC, NOSSDAV 2000
  Arnaud Legout and Ernst W. Biersack, Institut EURECOM
   
  Exhibits pathological behaviors of McCanne's RLM (Receiver-driven Layered Multicast) and Vicisano's RLC (TCP-like CC for Layered Multicast) on simple scenarios. "Most of the problems come form the bandwidth inference mechanism used that is responsible for transient periods of congestion, instability, and periodic losses.". Improvements of the bandwidth inference mechanism could improve both schemes' performance.
  The author's another paper for layered multicast (PLM) used packet pairs to infer the availabel bandwidth, thus gets better performance than RLM and RLC. However, that requires fair queueing (shown to be feasible in reality).

• Impact of TCP-Like Congestion Control on the Throughput of Multicast Groups, IEEE/ACM Transactions on Networking, Vol. 10, No. 4, August 2002
  Augustin Chaintreau, Francois Baccelli, Christophe Diot
   
  Use matrix calculation instead of discrete event to simulate multicast. The conslusion is that average throughput drops when receive number increases. However, one assumption makes it happen: the source sends (W + n)th packet only when all receivers have received the n-th packet, where W is the congestion window size. That is equivalent to the fact that the source adapts to the worst case receiver at any time without proper feedback filtering. Therefore, the authors conclude pessimistically.

Multicast Feedback Suppression

• Extremum Feedback for Very Large Multicast Groups, Technical Report, Praktische Informatik IV, Unversity of Mannheim, Germany, May 2001
  Jorg Widmer, Thomas Fuhrmann
   
  

• On The Scaling of Feedback ALgorithms for Very Large Multicast Groups, Computer Communications 2001
  T. Fuhrmann and J. Widmer
   
  

• Scalable Multicast Representative Member Selection, Infocom 2001
  Michael J. Donahoo, ASunila R. Ainapure
   
  The paper extends two approaches of representative selection: backoff timers (slotting and damping) and probabilistic polls. It assumes known maximum metric, assigns different probability to receivers for them to respond. Since it has not taken account of network dynamics yet, which will results in dynamic metrics, its future work may be more interesting.

Miscellaneous

• Aggregated Multicast: an Approach to Reduce Multicast State, Globecom 2001
  Aiguo Fei, Junhong Cui, Mario Gerla, Michalis Faloutsos
   
  

  If multiple multicast groups share a common tree, the inner routers of the tree need to keep forwarding state per aggragted tree instead of per group. Therefore, the number of forwarding states needed is reduced.

• Fairness Analysis of Multicast Congestion Control: A Case Study on pgmcc, Technical Report 01743, University of Southern California, CS Department, April 2001, http://citeseer.nj.nec.com/478443.html
  K. Seada, A. Helmy
  

  This paper has conducted some simulations to test PGMCC. The following problems are reported for PGMCC:
  1. Adaptive timeout mechanism is required, otherwise its fairness to TCP is affected.
  2. High loss rate cause PGMCC to be unfair to TCP, because it does not have cumulative ACK and thus can increase rate more than TCP.
  3. NACK suppression can also be a source of unfairness. In some configurations, the worst receiver behind a long RTT path may never be chosen as acker because NACKs from closer receivers suppress its NACKs.
  4. When receivers seeing similar losses have large differences in delay, acker changes can cause severe performance degradation. That is because just after acker change, its window is no longer a correct estimation of packets on flight between the sender and the acker. If the acker is changed from a long delay receiver to a short delay receiver, old ACKs from the long delay receiver won't open the window; if from short to long, the sender needs to wait a long time before ACKs can open the window.