F AST Background
Overview
The development
of robust and stable ultrascale networking, at 100 Gbps and higher speeds
in the wide area, is critical to support the new generation of ultrascale
computing and Petabyte to Exabyte datasets that promise to drive discoveries
in fundamental and applied sciences of the next decade. Continued advances
in computing, communication, and storage technologies, combined with the
development of national and global Grid systems, hold the promise of providing
the required capacities and an effective environment for computing and
science.
The key challenge we face, and intend to overcome, is that some of our
current network control and resource sharing algorithms, that are at the
foundation of these transformative trends in science and computer science,
cannot scale to this regime.
Our goal is to develop theory, algorithms and prototypes to design,
demonstrate, and deploy protocols that are scalable to arbitrary network
capacity and size in order to fulfill the vision of ultrascale networking.
Ultrascale Network Protocols for Computing and Science in the 21st Century
J. J. Bunn, J. C. Doyle, S. H. Low, H. B. Newman and S. M. Yip, White paper to US Department of Energy's Ultrascale Simulation for Science (USS) initiative, September 2002 (pdf 100K)
H. B. Newman, InterAct Magazine, September, 2002 (pdf 276K)
Theory
Equilibrium and Dynamics of Current Protocols Congestion
control is a distributed algorithm to share network resources among competing
users. It consists of two components: and a network algorithm that updates
and feeds back, implicitly or explicitly, congestion information to sources,
and a source algorithm that dynamically adjusts rate (or window size)
in response to congestion in its path. In the current Internet, the source
algorithm is carried out by TCP, and the link algorithm is carried out
by (active) queue management (AQM) schemes such as DropTail or RED.
We can interpret TCP/AQM algorithms as distributed asynchronous primal-dual
algorithms carried out over the Internet in real-time to solve a utility
maximizaiton probelm. All equilibrium properties, such as throughput,
loss and delay, or fairness, can be understood in terms of the underlying
optimizaiton problem. Different algorithms, AIMD (Reno) or Vegas, differ
in the utility functions they implicitly optimize.
S. H. Low, ITC Specialist Seminar on IP Traffic Measurement, Modeling and Management, September 18-20, 2000, Monterey, CA (USA) (ps 507K). To appear in IEEE/ACM Transactions on Networking, October 2003.
S. H. Low, Larry Peterson and Limin Wang, Journal of ACM, 49(2):207-235, March 2002 (pdf 793K)
Is the system equilibrium stable? It can be shown that, locally, the equilibrium can become unstable as delay increases, or more strikingly, as network capacity increases!
C. Hollot, V. Misra, D. Towsley and W. B. Gong, IEEE Inforcom, April 2001. (pdf 295K)
S. H. Low, F. Paganini, J. Wang, S. Adlakha and J. C. Doyle, IEEE Infocom, June 2002 (pdf 435K)
Can we design
TCP/AQM algorithms, as simple and decentralized as the current protocols,
that maintain stability as networks scale up in capacity in size? To do
this, we need to step back and understand the optimization problem TCP/AQM
implicitly solves, and the delay and decentralization constriants under
which it operates.
Scalable
and Robust Protocols
Instead
of first designing a TCP/AQM and then deduce the underlying optimization
problem, as we did to understand existing protocols, we proceed in the
opposite direction: start with an optimization problem and deduce the
appropriate algorithms.
The first paper below formulates the TCP/AQM problem as a constrained
convex optimization and proposes a `primal algorithm' to solve it. The
second paper proposes a `dual algorithm' to solve its Lagrangian dual.
These algorithms are proved to be globally stable either in the absence
of delay, or with a conservative bound on stepsize (responsiveness to
congestion) in the presence of delay and other asynchronism.
F. P. Kelly, A.K. Maulloo and D. K. H. Tan, Journal of the Operational Research Society 49 (1998), 237-252.
S. H. Low and D. E. Lapsley IEEE/ACM Transactions on Networking, 7(6):861-75, Dec. 1999 (pdf 270K)
The original primal algorithm can be enhanced to maintain local stability for arbitrary capacity, under a suitable bound on delay.
Glenn Vinnicombe, IFAC 2002. (pdf 73K)
Glenn Vinnicombe, submitted for publication (pdf 219K)
The dual algorithm can be specialized to maintain local stability for arbitrary delay and capacity.
Fernando Paganini, J. C. Doyle and S. H. Low, IEEE CDC, Orlando, FL, December 2001. (ps 475K)
The primal
and dual algorithms are complementary in many ways. The primal algorithms
allow general utility functions, and hence arbitrary fairness in rate
allocation, but give up tight control on utilization. The dual algorithm,
on the other hand, can achieve very high utilization, but is restricted
to a specific class of utility functions, and hence fairness in rate allocation.
By adding slow timescale dynamics at links (for primal algorithm) or at
sources (for dual algorithm), it is possible to achieve both high utilization
and arbitrary fairness.
S. Kunniyur and R. Srikant, Asian Control Conference, September 2002, Singapore (ps 186K)
Fernando Paganini, Zhikui Wang, Steven H. Low, John C. Doyle, Proc. of 39th Annual Allerton Conference on Communication, Control, and Computing, Monticello, IL, October 2002 (pdf 1.36M)
D. H. Choe and S. H. Low, Proc. of 39th Annual Allerton Conference on Communication, Control, and Computing, Monticello, IL, October 2002
Our first FAST implementation will be based on Stabilized Vegas.
Towards
an Internet Theory
An emerging theoretical foundation for the Internet is discussed at:
FAST v1: Stabilized Vegas
TCP Vegas was proposed in 1994 by Lawrence Brakmo and Larry Peterson as an alternative to TCP Reno, in
L. Brakmo and L. Peterson, IEEE Journal on Selected Areas in Communication, 13(8):1465-1480, October 1995
In addition
to many enhancements, the most important difference is a new congestion
avoidance algorithm that uses queueing delay, as opposed to packet loss
as Reno does, as a measure of congestion. This has important equilibrium
and stability implications.
The Vegas algorithm implies that it has a log utility function and achieves
proportional fairness in equilibrium, see, e.g.,
S. H. Low, Larry Peterson and Limin Wang, Journal of ACM, 49(2):207-235, March 2002
The implicit link algorithm in Vegas has the right scaling with respect to network capacity. This makes Vegas potentially scalable to high bandwidth, in stark contrast to Reno and its variants which becomes unstable as capacity increases. However, Vegas can become unstable if delay is large; but a simple modification can stabilize it, as explained in:
D. H. Choe and S. H. Low, Proc. of 39th Annual Allerton Conference on Communication, Control, and Computing, Monticello, IL, October 2002
Our first implementation will be based on Stabilized Vegas, which works with DropTail routers that are predominate in the current Internet and which has a natural incremental deployment path where some routers are DropTail and others implement a new AQM (active queue management).
References
Some Background
Xiaoyun Zhu, Jie Yu and John Doyle, IEEE Inforcom, April 2001 (ps 392K)
K. B. Kim and S. H. Low, Caltech Technical Report caltechCSTR:2002.009, March, 2002 (pdf 539K)
AIMD, Fairness and Fractal Scaling of TCP Traffic Francois Baccelli and Dohy Hong, IEEE Infocom, June 2002, New York, NY. (pdf 811K)
Tom Kelly, Cambridge University Engineering Department Technical Report, July 2002 (pdf 142K)
Recent Surveys and Links
R. Srikant, in "Perspectives in Control Engineering: Technologies, Applications, New Directions," Tariq Samad (Ed.), IEEE Press, 2000, pp. 462-488. (ps 1.85M)
S. H. Low, F. Paganini and J. C. Doyle
IEEE Control Systems Magazine, 22(1):28-43, Feb. 2002 (ps 672K)
Victor Firoiu, Jean-Yves Le Boudec, Don Towsley and Zhi-li Zhang, Proceedings of IEEE, May 2002 (pdf 320K)
Vegas References
(Send us links to relevant
work)
J. S. Ahn, P. B. Danzig, Z. Liu, and L. Yan, Proceedings of SIGCOMM'95, 1995.
O. Ait-Hellal and E. Altman, Telecommunication Systems, 2000 (A short version appeared in IEEE International Conference on Communications (ICC'97) , Montreal, 8-12 june 1997)
Thomas Bonald, Performance Evaulation, 36(37):307-332, 1999
J. Mo, R. La, V. Anantharam, and J. Walrand, Proceedings of IEEE Infocom, March 1999.
C. Boutremans and J. Y. Le Boudec, Proceedings of International Zurich Seminar on Broadband Communications, pages 163--170, February 2000.
U. Hengartner, J. Bolliger, and T. Gross, Proceedings of IEEE Infocom, March 2000.
Jeonghoon Mo and Jean Walrand. IEEE/ACM Transactions on Networking, 8(5):556--567, October 2000.
Yong Xia, David Harrison, Shivkumar Kalyanaraman, Kishore Ramachandran, Arvind Venkatesan, submitted, 2002
Eric Weigle and Wu-chun Feng, 9th International Symposium on High Performance Distributed Computing (HPDC'01), August, 2001