Internet Traffic Matrices and Compressive Sensing

Internet Traffic Matrices and Compressive Sensing

-
Walter Willinger, Darthmouth College
Fine Hall 214

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).)