|
|
|
| For years, the primary research hurdle to driving standards for reliable multicast was solving the problem of multicast congestion control. In helping attack this problem, we found that there was surprisingly little theoretical foundation underneath Internet congestion control, and we helped contribute to building a new theoretical foundation for both unicast and multicast congestion control. My dissertation was on tree based reliable multicast and multicast congestion control. The last document on this page, while never published except two years later as part of my dissertation, was one of a couple key documents that helped convince the research community that we understood multicast congestion control enough to create a IETF WG for reliable multicast. The algorithms proposed in my dissertation have a high degree of overlap with the independently developed TFMCC congestion control proposed by Mark Handley and others. Dissertation: Reliable Multicast Congestion Control and Tree Based Reliable Multicast (.pdf)This is my dissertation from Berkeley. It covers both RMTP-II as an example of tree based multicast, provides a new theoretical foundation for understanding Internet congestion control, and proposes a solution for multicast congestion control. Most of the congestion control work in it first appeared in 1998 paper below. A short version of the basic Internet congestion control theory it proposes can be found in the following unpublished paper from 2001. Steady State Analysis of Internet Congestion Control Algorithms, October 2001 (.pdf)Sumbitted to NGC 2002. Abstract: TCP congestion
control is widely recognized as the “magic” that has allowed the Internet to
scale exponentially without experiencing congestion collapse.
By extension, congestion control for reliable multicast has been
identified as an important research problem.
However, until recently there has been surprisingly little work done
defining the theory behind Internet congestion control, the requirements for a
congestion control algorithm, what it means to be “fair” with TCP, or even
the safe operating range for TCP congestion control.
The “drop-towards-zero” problem has been identified as a core
challenge for multicast congestion control, but has not been formally defined or
quantified. This paper helps
address these issues, by summarizing the results of a detailed theoretical
analysis of congestion control based on steady state analysis of congestion
response functions [WC98, Whetten00]. It
proposes a set of requirements that congestion control algorithms should meet,
quantifies the drop-to-zero effect, specifies the safe operating range for TCP,
analyzes the existing TCP response functions, and defines a notion of TCP
fairness. A Rate Based Congestion Control Scheme for Reliable Multicast, November 1998 (.pdf)Abstract: A congestion control algorithm fairly distributes network resources under various load and fault conditions. Congestion control for reliable multicast is an active and important area of current research. Simple approaches to this problem have suffered from the “drop-towards-zero” phenomenon, resulting in some cases with performance significantly worse than what would be achieved by using separate TCP connections from the sender to each receiver. This presents a strong disincentive to use reliable multicast. One of the primary reasons that progress in this area has been so slow is that there has not been a formal definition of what a congestion control algorithm should be trying to accomplish. In particular, there has been no agreed upon definition for what it means to fairly share the network. This paper does the following. · It specifies an abstract model for a network, and summarizes the notion of a response function for TCP. · It proposes a set of metrics to evaluate a congestion control algorithm based on analysis of its response function. These metrics provide a framework for a steady state analysis of the response function. · It evaluates the two response functions proposed for TCP, and shows that only the complex one provides safe operation. · It proposes a theoretical definition for fairness, and shows that TCP meets this definition. · It proposes a set of basic algorithms for a reliable multicast rate controller, and shows that they are both fair and safe. · It extends the basic rate controller to work with hierarchical reliable multicast protocols. These extensions help eliminate the drop to zero problem that the basic rate controller faces. The resulting algorithm is provably fair with TCP, under steady state analysis. Under steady state analysis it is also provably as safe as TCP. With the hierarchical optimizations, the drop to zero problem is mostly eliminated. The primary drawback of the algorithm is that its responsiveness is less than TCP’s. However, without explicit congestion notification from the routers, this appears to be unavoidable. |
|
Copyright © 2005
Brian Whetten
|
