Internet Traffic Matrices and Compressive Sensing

Monday, April 12, 2010 -
4:30pm to 6:30pm
Internet traffic matrices (TMs) specify the traffic volumes between origins and destinations in a network over some time period. For example, origins and destinations can be individual IP addresses, prefixes, routers, points-of-presence (PoPs), or entire networks or Autonomous Systems (ASes). Past work on TMs has almost exclusively focused on large ASes such as AS7018 (AT&T) and their router- or PoP-level TMs, mainly because the latter are critical inputs to many basic network engineering tasks, and the thrust of much of this work has been on measurement and inference of TMs. A key remaining challenge in this area is how to cope with missing values that frequently arise in real-world TMs. This problem brings TM research into the realm of compressive sensing, a generic technique for dealing with missing observations that exploits the presence of structure or redundancy in data from many real-world systems. In particular, since real-world TMs have been found to be of low rank, the concept of compressive sensing is directly applicable, at least in theory. In this talk, I will report on novel applications of compressive sensing to TM interpolation and inference and discuss how the resulting techniques work in practice. I will end by describing some challenging open problems concerning measuring and inferring the completely unknown Internet-wide AS-level TM. (This is joint work with Y. Zhang and L. Qiu (Univ. of Texas) and M. Roughan (Univ. od Adelaide).)
Walter Willinger
Darthmouth College
Event Location: 
Fine Hall 214