1:15 PM, February 22, 2001
Gates Building, Room 104

Optimization Problems in Internet Congestion Control

Richard Karp,
AT&T Center for Internet Research at ICSI (ACIRI)

About the talk:

The Internet carries packets on a best-effort basis with no guarantees as to when, or even if, packets will be delivered. When the Internet is congested, packet delays are large and packet drop rates are high. One of the crucial elements in the Internet's success has been its ability to adequately control congestion. The predominant form of congestion control is embodied in the TCP protocol. The additive-increase, multiplicative-decrease policy within this protocol can be thought of as a probing algorithm designed to find the maximum rate at which TCP can send packets under current conditions without incurring packet drops. In this talk we seek to broaden our understanding of congestion probing algorithms in a systematic fashion. To do so, we formulate congestion probing as an optimization problem. We first consider the case where the other traffic remains constant, and we find that the optimal probing solution is a novel and intriguing variant of binary search. We then go on to consider the on-line algorithm problem of determining the worst-case behavior of probing strategies in the presence of changing available bandwidth. This is joint work with Elias Koutsoupias, Christos Papadimitriou and Scott Shenker.

About the speaker:

Richard M. Karp was born in Boston, Massachusetts in 1935 and was educated at the Boston Latin School and Harvard University, where he received the Ph.D. in Applied Mathematics in 1959. From 1959 to 1968 he was a member of the Mathematical Sciences Department at the IBM Thomas J. Watson Research Center. From 1968 to 1994 he was a Professor of Computer Science, Mathematics and Operations Research at the University of California, Berkeley. From 1988 to 1995 he was also associated with the International Computer Science Institute (ICSI)in Berkeley. In 1995 he became a Professor of Computer Science and Engineering and an Adjunct Professor of Molecular Biotechnology at the University of Washington.

In June, 1999 Karp returned to the University of California at Berkeley as a University Professor. His principal appointment is in Computer Science, and he also holds appointments in Mathematics and Bioengineering. In addition, he is a research scientist at the International Computer Science Instittue. For the 1999-2000 academic year he was the Hewlett-Packard Visiting Professor at the Mathematical Sciences Research Institute in Berkeley, on leave from UC Berkeley and ICSI.

The unifying theme in Karp's work has been the study of combinatorial algorithms. His 1972 paper ``Reducibility Among Combinatorial Problems,'' shows that many of the most commonly studied combinatorial problems are disguised versions of a single underlying problem, and thus are all of essentially the same computational complexity. The problems in this class are called the NP-complete problems.

Much of Karp's work has concerned the development of parallel algorithms, the probabilistic analysis of combinatorial optimization problems, and the construction of randomized algorithms for combinatorial problems. His current research is focused on computational molecular biology and on algorithmic problems related to the Internet.

Karp has received the U.S. National Medal of Science, the Harvey Prize (Technion), the Turing Award (ACM), the Centennial Medal (Harvard University) the Fulkerson Prize(AMS and Math. Programming Society), the von Neumann Theory Prize(ORSA-TIMS), the Lanchester Prize (ORSA) the von Neumann Lectureship (SIAM) and the Distinguished Teaching Award (Berkeley). He is a member of the National Academy of Sciences, the National Academy of Engineering and the American Philosophical Society,as well as a Fellow of the American Academy of Arts and Sciences. He holds four honorary degrees.

For more information:

R. M. Karp, E. Koutsoupias, C. H. Papadimitriou, S. Shenker. "Optimization Problems in Congestion Control". FOCS 2000.