Three applications of dynamic programming to network management

Dynamic programming is an algorithmic technique with a wide variety of applications, from operations research to formal languages. Even when it does not solve a problem completely, it can be useful as part of an overall approach. In this talk I describe three different network problems where I was able to exploit it, the work being done in collaborations with more systems-oriented researchers at AT&T: (1) using caches for content distribution, (2) mapping IP addresses to autonomous systems, and (3) optimizing access control lists in routers.

David S. Johnson is Head of the Algorithms and Optimization Department at AT&T Labs-Research in Florham Park, NJ, and has been a researcher at the Labs (in its many incarnations) since 1973, when he received his Ph.D from MIT. The author of over 100 technical papers, he is perhaps best known as the co-author of COMPUTERS AND INTRACTABILITY: A GUIDE TO THE THEORY OF NP-COMPLETENESS, for which he shared the Lanchester Prize of the Operations Research Society of America (1979). His research interests (in addition to the theory of NP-completeness) include approximation algorithms for combinatorial problems, and the experimental analysis of algorithms, with special emphasis on bin packing, graph coloring, and the traveling salesman problem. As one of the founders of ACM\'s Kanellakis Prize, he is particularly interested in recognizing and encouraging the interaction between theory and practice in computer science.