Readings

Multicast & Congestion Control

The Loss Path Multiplicity Problem in Multicast Congestion Control
By Supratik Bhattacharyya, Don Towsley, Jim Kurose
It talked about some problems faced by multicast congestion control, e.g. loss path multiplicity (a.k.a. drop-to-zero problem) and TCP friendly.: By Supratik Bhattacharyya, Don Towsley, Jim Kurose; It talked about some problems faced by multicast congestion control, e.g. loss path multiplicity (a.k.a. drop-to-zero problem) and TCP friendly.

Modeling TCP Throughput: A Simple Model and its Empirical Validation
By Jitendra Padhye, Victor Firoiu, Don Towley, Jim Kurose
This paper gives an equation to calculate TCP throughput from RTT and lost rate.: By Jitendra Padhye, Victor Firoiu, Don Towley, Jim Kurose; This paper gives an equation to calculate TCP throughput from RTT and lost rate.

Strawman Specification for TCP Friendly (Reliable) Multicast Congestion Control (TFMCC)
By Mark Handley, Sally Floyd
As the title indicates, this paper presents a specification for TFMCC to be tested.
There is an accompanying paper with many graphs.: By Mark Handley, Sally Floyd; As the title indicates, this paper presents a specification for TFMCC to be tested.; There is an accompanying paper with many graphs.

PGM Reliable Transport Protocol (Proposed on 24 June 1999, Expires on 24 December 1999)
By Tony Speakman et al: By Tony Speakman et al

Inference of Multicast Routing Trees andBottlenec Bandwidths using End-to-end Measurements
By Sylvia Ratnasamy, Steven McCanne
This paper gives an algorithm how to infer the multicast tree topologies and bottlenect bandwidths with the loss statistics information collected from all the receivers. Since the complexity of this algorithm is proportional to the number of receivers, it is not of practical use.: By Sylvia Ratnasamy, Steven McCanne; This paper gives an algorithm how to infer the multicast tree topologies and bottlenect bandwidths with the loss statistics information collected from all the receivers. Since the complexity of this algorithm is proportional to the number of receivers, it is not of practical use.

Fundemental Observations on Multicast Congestion Control in the Internet
By S. Jamaloddin Golestani: By S. Jamaloddin Golestani

Scalable Reliable Multicast Using Multiple Multicast Groups
By Sneha K. Kasera, Jim Kurose and Don Towsley
Proposes a scheme which use a channel to send original data, and other channels to retransmit lost data. Receivers send NAKs on some specified channels to require retransmission.: By Sneha K. Kasera, Jim Kurose and Don Towsley; Proposes a scheme which use a channel to send original data, and other channels to retransmit lost data. Receivers send NAKs on some specified channels to require retransmission.

Efficient Rate-Controlled Bulk Data Transfer using Multiple Multicast Groups
By Suupratik Bhattacharyya, Ramesh Nagarajan
Proposes a scheme which using several channels to distribute data. Each receiver can subscribe to one or more channels to get data. Virtually, the channel(s) each receiver uses is(are) combined to be a single channel which can transmit all the data. The sender split the data and send them on the channels once. Since those receivers does not subscribe to all the channels will miss some of the data, the data missed will be retransmit on a subset of the channels. Still, some receivers cannot get all data, again the data they misses will be sent on a sub-sub set of the channels, and so on, until all the receivers get all the data.: By Suupratik Bhattacharyya, Ramesh Nagarajan; Proposes a scheme which using several channels to distribute data. Each receiver can subscribe to one or more channels to get data. Virtually, the channel(s) each receiver uses is(are) combined to be a single channel which can transmit all the data. The sender split the data and send them on the channels once. Since those receivers does not subscribe to all the channels will miss some of the data, the data missed will be retransmit on a subset of the channels. Still, some receivers cannot get all data, again the data they misses will be sent on a sub-sub set of the channels, and so on, until all the receivers get all the data.

Receiver-driven Layered Multicast
By Steven McCanne, Van Jacobson, Martin Vetterli
A scheme to transmit information accumulatively in different layers. By subscribing to different layers, receivers can get data of different quality. The author said it was compatiable for simulcast.: By Steven McCanne, Van Jacobson, Martin Vetterli; A scheme to transmit information accumulatively in different layers. By subscribing to different layers, receivers can get data of different quality. The author said it was compatiable for simulcast.

On the Use of Destination Set Grouping to Improve Fairness in Multicast Video Distribution
By Shun Yan Cheung, Mostafa H. Ammar, Xue Li
A complicated scheme to transmit information simultaneously via diffrent streams to receivers, a.k.a simulcast.: By Shun Yan Cheung, Mostafa H. Ammar, Xue Li; A complicated scheme to transmit information simultaneously via diffrent streams to receivers, a.k.a simulcast.

Distributed Algorithms for Computation of Fair Rates in Multirate Multicast Trees
By Saswati Sarkar, Leandros Tassiulas
An algorithm to calculate maxmin fair rates of multicast sessions and its synchronous and asynchronous implementation.: By Saswati Sarkar, Leandros Tassiulas; An algorithm to calculate maxmin fair rates of multicast sessions and its synchronous and asynchronous implementation.

Scalable feedback control for multicast video distribution in the Internet
By Jean-Chrysostome Bolot, Thierry Turletti, Ian Wakeman
A mechanism for mutlicasting realtime continuous media streams, using probing from sender and probabilistic feedback from receivers. It requires some probing and feedback packets for sender and receivers respectively.: By Jean-Chrysostome Bolot, Thierry Turletti, Ian Wakeman; A mechanism for mutlicasting realtime continuous media streams, using probing from sender and probabilistic feedback from receivers. It requires some probing and feedback packets for sender and receivers respectively.

End-to-end quality of service control using adaptive applications
By Dorgham Sisalem
Based on the real time transport protocol (RTP), this scheme proposes how to adjust the sender's rate according to receiver's feedback.: By Dorgham Sisalem; Based on the real time transport protocol (RTP), this scheme proposes how to adjust the sender's rate according to receiver's feedback.

TCP-like Congestion Control for Layered Multicast Data Transfer
By Lorenzo Vicisano, Luigi Rizzo, Jon Crowcroft
This algorithm relies on standard functionalities of multicast routers and layered organization of data. It tries to make its congestion control results similar to that of TCP thus to realize TCP-friendliness. It also tries to synchronize feedback from receivers so that to get scalability.: By Lorenzo Vicisano, Luigi Rizzo, Jon Crowcroft; This algorithm relies on standard functionalities of multicast routers and layered organization of data. It tries to make its congestion control results similar to that of TCP thus to realize TCP-friendliness. It also tries to synchronize feedback from receivers so that to get scalability.

Improving the Throughput of Point-to-Multipoint ARQ Protocols through Destination Set Splitting
By Mostafa H. Ammar, Li-Ran Wu
This method is supposed to use on automatic repeat request protocols (ARQ), mostly ACK based protocols. This article considered three versions (memoryless, limited-memory and full-memory) of the Go-Back-N protocol at the source according to the ability to remember retransmission state. The splitting is based on loss rates of receivers, shared or individual.: By Mostafa H. Ammar, Li-Ran Wu; This method is supposed to use on automatic repeat request protocols (ARQ), mostly ACK based protocols. This article considered three versions (memoryless, limited-memory and full-memory) of the Go-Back-N protocol at the source according to the ability to remember retransmission state. The splitting is based on loss rates of receivers, shared or individual.

Optimal Multicast Feedback
By Jorg Nonnenmacher, Ernst W.Biersack
It states that back-off time of exponential distribution is good and robust for multicast receiver feedback, better than that of uniform distribution. The timer-based feedback mechanism used in this paper is that sender send request to receivers for feedback.: By Jorg Nonnenmacher, Ernst W.Biersack; It states that back-off time of exponential distribution is good and robust for multicast receiver feedback, better than that of uniform distribution. The timer-based feedback mechanism used in this paper is that sender send request to receivers for feedback.

How bad is Reliable Mulitcast without Local Recovery?
By Jorg Nonnenmacher, Martin Lacher, Matthias Jung, Ernst W. Biersack, Georg Carle
Examines three types of local recovery: centralized error recovery, distributed error recovery with repairs packet as original data packets, distributed error recovery with repairs packet as FEC packets. As the result, the third is best. But for large transmission group size, the performances of the protocol with local recovery and that without come close.
Useful point:
Calculate average cost of a multicast packet per link.: By Jorg Nonnenmacher, Martin Lacher, Matthias Jung, Ernst W. Biersack, Georg Carle; Examines three types of local recovery: centralized error recovery, distributed error recovery with repairs packet as original data packets, distributed error recovery with repairs packet as FEC packets. As the result, the third is best. But for large transmission group size, the performances of the protocol with local recovery and that without come close.
Useful point:
Calculate average cost of a multicast packet per link.

An Overview of Reliable Multicast Transport Protocol II
By Brian Whetten (Talarian Corporation), Cursel Taskale (Reuters)
Overview of RMTP-II: design goals, algorithms, basic analysis of the scalabiility. Also some overview of multicast.: By Brian Whetten (Talarian Corporation), Cursel Taskale (Reuters); Overview of RMTP-II: design goals, algorithms, basic analysis of the scalabiility. Also some overview of multicast.

A Comparison of Server-Based and Receiver-Based Local Recovery Approaches for Scalable Reliable Multicast
By Sneha K. Kasera, Jim Kurose and Don Towsley (U. Mass)
Server-based local recovery (with recovery servers on intermediate routers) yields higher throughput and lower bandwidth usage than receiver-based local recovery when the repair servers have processign power slightly higher than that of a receiver and several hundred kilobytes of buffer per multicast session.: By Sneha K. Kasera, Jim Kurose and Don Towsley (U. Mass); Server-based local recovery (with recovery servers on intermediate routers) yields higher throughput and lower bandwidth usage than receiver-based local recovery when the repair servers have processign power slightly higher than that of a receiver and several hundred kilobytes of buffer per multicast session.

Equation-Based Congestion Control for Unicast Applications
By Sally Floyd, Mark Handley, Jitendra Padhye, Jorg Widmer
It proposes a protocol in which the sender explicitly adjusts its sending rate as a funciton of the measured rate of loss events which is in the feedback from the receiver. The receiver uses the Average Loss Interval method which computes a weighted average of the loss rate over the last n loss intervals, with equal weights on each of the most recent n/2 intervals. This protocol is proved to be TCP-friendly by simulations and experiments.
Useful points:
1. Guideline for calculating loss event rate.
2. The difference between the loss-event fraction and the loss fraction is at most 10%.
3. Binomial congestion control algorithm of which AIMD is a special case.
Useful reference:
1. J. Padhye, Model-based Approach to TCP-friendly Congestion Control. Ph.D. thesis, University of Massachusetts at Amherst, Mar. 2000: By Sally Floyd, Mark Handley, Jitendra Padhye, Jorg Widmer; It proposes a protocol in which the sender explicitly adjusts its sending rate as a funciton of the measured rate of loss events which is in the feedback from the receiver. The receiver uses the Average Loss Interval method which computes a weighted average of the loss rate over the last n loss intervals, with equal weights on each of the most recent n/2 intervals. This protocol is proved to be TCP-friendly by simulations and experiments.
Useful points:
1. Guideline for calculating loss event rate.
2. The difference between the loss-event fraction and the loss fraction is at most 10%.
3. Binomial congestion control algorithm of which AIMD is a special case.
Useful reference:
1. J. Padhye, Model-based Approach to TCP-friendly Congestion Control. Ph.D. thesis, University of Massachusetts at Amherst, Mar. 2000

A Digital Fountain Approach to Reliable Distribution of Bulk Data
By John W. Byers, Michael Luby, Michael Mitzenmacher, Ashutosh Rege
Useful points:
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.
Characteristics of a scalable protocol for distributing a software.
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.
An implementation of a reliable distribution protocol based on layer multicast (each layer for different rate with higher layer including lower layers).: By John W. Byers, Michael Luby, Michael Mitzenmacher, Ashutosh Rege; Useful points:
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.
Characteristics of a scalable protocol for distributing a software.
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.
An implementation of a reliable distribution protocol based on layer multicast (each layer for different rate with higher layer including lower layers).

Accessing Multiple Mirror Sites in Parallel: Using Tornado Codes to Speed Up Downloads
By John W. Byers, Michael Luby, Michael Mitzenmacher
A receiver can get packets from multiple servers in paralllel. Once k packets are got, it can constrcut source data from them, No/few feedback to server in required. Can be used for many-to-many distribution.: By John W. Byers, Michael Luby, Michael Mitzenmacher; A receiver can get packets from multiple servers in paralllel. Once k packets are got, it can constrcut source data from them, No/few feedback to server in required. Can be used for many-to-many distribution.

The Macroscopic Behavior of the TCP Congestion Avoidance Algorithm
By Matthew Mathis, Jeffrey Smeke, Jamshid Mahdavi
An approximate throughput function of TCP.: By Matthew Mathis, Jeffrey Smeke, Jamshid Mahdavi; An approximate throughput function of TCP.

Design and Analysis of Loss Indication Filters for Multicast Congestion Control
By Supratik Bhattacharyya, Don Towsley, Jim Kurose

Loss indication filter.
Derivations of throughput using stochastic differential equations.: By Supratik Bhattacharyya, Don Towsley, Jim Kurose; Loss indication filter.
Derivations of throughput using stochastic differential equations.

Resilient Multicast Support for Continuous-Media Applications
By X. Rex Xu, Andrew C. Myers, Hui Zhang, Raj Yavatkar
A protocol for trading off between interactivity and quality of continuous media stream. Not fully realiable. Both sender and receiver and router support are required.: By X. Rex Xu, Andrew C. Myers, Hui Zhang, Raj Yavatkar; A protocol for trading off between interactivity and quality of continuous media stream. Not fully realiable. Both sender and receiver and router support are required.

Consideration of Receiver Interest for IP Multicast Delivery
By Brian Neil Levine, Jon Crowcroft, Christophe Diot, J.J. Garcia-Luna-Aceves, James F. Kurose
There are two ways to send data to multiple receivers with different interests (data content, transmission performance) (1) Send all data to all receivers. Receivers filter out whatever they do not need. (2) Receivers with different interests subscribe to different groups. Different sets of data are sent to different groups. (3) Hybrid of (1) and (2). Show by simulation results that (2) is the most efficient. But current Interent does not have enough support for that.: By Brian Neil Levine, Jon Crowcroft, Christophe Diot, J.J. Garcia-Luna-Aceves, James F. Kurose; There are two ways to send data to multiple receivers with different interests (data content, transmission performance) (1) Send all data to all receivers. Receivers filter out whatever they do not need. (2) Receivers with different interests subscribe to different groups. Different sets of data are sent to different groups. (3) Hybrid of (1) and (2). Show by simulation results that (2) is the most efficient. But current Interent does not have enough support for that.

IP Multicast Channels: EXPRESS Support for Large-scale Single-source Applications
By Hugh W. Holbrook and David R. Cheriton
A single-source multicast architecture.

Host IP address + IP D class address = multicast channel ID.
Requires no change to the current fast-path mechanisms in routers. (But it does require support from routers.)
Has receiver number counting and access control support.
Shows/argue how multi-source multicast can be done using session relay nodes.: By Hugh W. Holbrook and David R. Cheriton; A single-source multicast architecture.

Host IP address + IP D class address = multicast channel ID.
Requires no change to the current fast-path mechanisms in routers. (But it does require support from routers.)
Has receiver number counting and access control support.
Shows/argue how multi-source multicast can be done using session relay nodes.

Deployment Issues for the IP Multicast Service and Architecture
By Christophe Diot, Brian Neil Levine, Bryan Lyles, Hassan Kassem, Doug Balensiefen
Examine the issues that have limited the commercial deployment of IP-multicast fromthe viewpoint of carriers. Analyzes where the model fails, what it does not offer, and discusses requirements for successful deployment of multicast services.: By Christophe Diot, Brian Neil Levine, Bryan Lyles, Hassan Kassem, Doug Balensiefen; Examine the issues that have limited the commercial deployment of IP-multicast fromthe viewpoint of carriers. Analyzes where the model fails, what it does not offer, and discusses requirements for successful deployment of multicast services.

Overlay Network/Application Level Multicast

A Third-Party Value-Added Network Service Apporach to Reliable Multicast
By Kunwadee Sripanidkulchai, Andy Myers, Hui Zhang
A scheme to add some nodes (called way-points) in the network topology to help packet recovery.: By Kunwadee Sripanidkulchai, Andy Myers, Hui Zhang; A scheme to add some nodes (called way-points) in the network topology to help packet recovery.

A Case for End System Multicast
By Yang-hua Chu, Sanjay G. Rao, Hui Zhang
Implements multicast on end systems without assuming network layer support. It constructs a overlay network by doing routing (Narada) itself. Only good for small and sparse multicast groups. Better than unicast, poorer than IP multicast.: By Yang-hua Chu, Sanjay G. Rao, Hui Zhang; Implements multicast on end systems without assuming network layer support. It constructs a overlay network by doing routing (Narada) itself. Only good for small and sparse multicast groups. Better than unicast, poorer than IP multicast.

A Waypoint Service Approachto Connect Heterogeneous Internet Address Spaces
By T.S.Eugene Ng, Ion Stoica, Hui Zhang
Waypoints (AVES) link a DNS name to a non-IP destination host (e.g. 192.168.*.*), and relay the packets from the initiator to the destination.: By T.S.Eugene Ng, Ion Stoica, Hui Zhang; Waypoints (AVES) link a DNS name to a non-IP destination host (e.g. 192.168.*.*), and relay the packets from the initiator to the destination.

REUNITE: A Recursive Unicast Approach to Multicast
By Ion Stoica, T.S.Eugene Ng, Hui Zhang
Do multicast by unicast. Routers dispatch the packets to multiple branches if necessary. (Thus, at least enhancement for those routers are needed.) Simulation is done on ns.: By Ion Stoica, T.S.Eugene Ng, Hui Zhang; Do multicast by unicast. Routers dispatch the packets to multiple branches if necessary. (Thus, at least enhancement for those routers are needed.) Simulation is done on ns.

The Design and Implementation of An Intentional Naming System
By William Adjie-Winoto, Elliot Schwartz, Hari Balakrishnan, Jeremy Lilley
A resource discovery and service location system with

A simple atrribute-value hierarchical language/directory to help service lookup.
Late binding (?) Every INS server communications with a central points (DSR), and gets a list of active servers to construct the overlay tree.: By William Adjie-Winoto, Elliot Schwartz, Hari Balakrishnan, Jeremy Lilley; A resource discovery and service location system with

A simple atrribute-value hierarchical language/directory to help service lookup.
Late binding (?) Every INS server communications with a central points (DSR), and gets a list of active servers to construct the overlay tree.

A Host-Based Multicast (HBM) Solution for Group Communications
By Vincent Roca and Ayman El-Sayed
Everything is under the control of a central rendez-vous point (RP). RP collects information and computes the tree. The hosts are devided into three classes, disconnected, leaf-only, transit-possible (relay enabled), according to their capability respectively. Redundant links bwteen nodes are added by an algorithm until the partition probability drops below some level or theoretically, zero.: By Vincent Roca and Ayman El-Sayed; Everything is under the control of a central rendez-vous point (RP). RP collects information and computes the tree. The hosts are devided into three classes, disconnected, leaf-only, transit-possible (relay enabled), according to their capability respectively. Redundant links bwteen nodes are added by an algorithm until the partition probability drops below some level or theoretically, zero.

Application-layer Multicast with Delaunay Triangulations
By Jorg Liebeherr, Michael Nahas
A technique to build overlay topology without requiring routing information exchange. But it needs node coordinates instead. Stress and RDP (Relative Delay Penalty) comparisons are done with other overlay topology methods. The enhanced triangulation methods have reasonable performance.: By Jorg Liebeherr, Michael Nahas; A technique to build overlay topology without requiring routing information exchange. But it needs node coordinates instead. Stress and RDP (Relative Delay Penalty) comparisons are done with other overlay topology methods. The enhanced triangulation methods have reasonable performance.

Application Level (End Host) Multicast Architecture

Yoid: Extending the Internet Multicast Architecture
By Paul Francis
Unreffered work. Presents a set of protocols for an overlay network above transport layer. Tries to solve multicast of broader sense across both time and space.: By Paul Francis; Unreffered work. Presents a set of protocols for an overlay network above transport layer. Tries to solve multicast of broader sense across both time and space.

Banana Tree Protocol, an End-host Multicast Protocol
By David A. Helder, Sugih Jamin, July 2000
A basic try of file distribution using end-host based multicast. Topology optimization method: A node checks its siblings to see if there is a better path to root. If is, switch to the sibling's child node. No concurrent switch is allowed to avoid loop.
It could not preform well in realistic scenarios. Does not talk about the many-to-many multicast protocol on top of it.: By David A. Helder, Sugih Jamin, July 2000; A basic try of file distribution using end-host based multicast. Topology optimization method: A node checks its siblings to see if there is a better path to root. If is, switch to the sibling's child node. No concurrent switch is allowed to avoid loop.
It could not preform well in realistic scenarios. Does not talk about the many-to-many multicast protocol on top of it.

Qos Routing

Henristic Algorithms for Multi-Constrained Quality of Service Routing
By Xin Yuan, Xingming Liu
A limited graularity henristic and a limited path heuristic algorithm for small number k of constraints.: By Xin Yuan, Xingming Liu; A limited graularity henristic and a limited path heuristic algorithm for small number k of constraints.