Date: Monday, November 4, 2002
Time: 4:00 PM (Talk)
Place: 313 EGRC, NCSU Centennial Campus (click for
courtesy parking request)
Speaker: Ian Munro , U. of Waterloo
Frequency Estimation of Internet Packet Streams with Limited Space
Abstract: A fundamental difficulty with measuring traffic behavior on the Internet is that there is simply too much data to be recorded for later analysis, on the order of gigabytes a second. As a result, network routers can collect only relatively few statistics about the data, indeed it has been suggested that the only viable approaches for gathering any information at all are those based on sampling. The central problem addressed here is to use the limited memory of routers to determine essential features of the network traffic stream. A particularly difficult and representative subproblem is to determine the top k categories to which the most packets belong, for a desired value of k and for a given notion of categorization such as the destination IP address.
Short Bio: Ian Munro is Professor of Computer Science and holder of the Canada Research Chair in Algorithm Design at the University of Waterloo, where he has been a faculty member since completing his PhD at the University of Toronto in 1971. His research has concentrated on the efficiency of algorithms and data structures, with a particular focus on techniques that are both time and space efficient. He has authored well over 100 research papers and supervised fifteen Ph.D.'s on the subject. Dr. Munro has held visiting positions at a number of major universities and research labs, including ATT Bell Labs, Princeton University and the Max Planck Institute for Informatics. His consulting activities have included work with government and major computer companies as well as successful several startup companies. Dr. Munro has served on numerous editorial boards, grant selection committees and the program committees of most of the major conferences in his research area. Prior to his appointment as Canada Research Chair he was holder of the University of Waterloo's Marsland Fellowship for outstanding sustained academic excellence. He is a former Director of the University of Waterloo's Institute for Computer Research and was a founder of the Information Technology Research Centre of Ontario.
Host: Lars Arge, Duke U.