WNM 2013 logo
IEEE

LCN 2012 Keynote by Prof. Mark Crovella, Boston University

Wednesday, 24 October 2012

A Fine-Grained Distance Metric for Analyzing Internet Topology

Prof. Mark Crovella

Computer Science Department, Boston University, Boston, Massachusetts, USA

 

ABSTRACT

One of the defining properties of small worlds is the prevalence of short paths connecting node pairs. Unfortunately, as a result the usual notion of distance is not particularly helpful in distinguishing neighborhoods in such graphs. This is the case, for example, when analyzing the interdomain routing system of the Internet.

We describe a motivating problem that requires a finer-grained notion of distance. The problem is quite simple to state: how can any given network operator in the Internet determine which paths pass through its network? Surprisingly, the nature of Internet routing makes this question rather hard to answer.

To address this problem, we define a new distance metric on graph nodes. This metric has useful and interesting properties: it is easy to compute and understand, it can be used to sharply distinguish neighborhoods in networks, and it remains useful even in small-world networks. We show how we use this metric to address our motivating problem, and more generally how it can be used for visualization and dimensionality reduction of complex networks.

 

ABOUT THE SPEAKER

Mark Crovella is Professor of Computer Science at Boston University, where he has been since 1994. During 2003-2004, he was a Visiting Associate Professor at the Laboratoire d'Infomatique de Paris VI (LIP6). He received a B.S. from Cornell University in 1982, and an M.S. from the State University of New York at Buffalo. He received his Ph.D. in Computer Science from the University of Rochester in 1994. From 1984 to 1994 he worked at Calspan Corporation in Buffalo NY, eventually as a Senior Computer Scientist.

His research interests are in performance evaluation, focusing on parallel and networked computer systems. In the networking arena, he has worked on characterizing the Internet and the World Wide Web. He has explored the presence and implications of self-similarity and heavy-tailed distributions in network traffic and Web workloads. He has also investigated the implications of Web workloads for the design of scalable and cost-effective Web servers. In addition he has made numerous contributions to Internet measurement and modeling; and he has examined the impact of network properties on the design of protocols and the construction of statistical models. As of 2012, Google Scholar reports over 16,000 citations to his work. He has given numerous invited talks and tutorials, and is a founder of and consultant to companies involved in Internet technologies.

Professor Crovella is co-author of Internet Measurement: Infrastructure, Traffic, and Applications (Wiley Press, 2006) and is the author of over one hundred papers on networking and computer systems. He holds five patents deriving from his research. Between 2007 and 2009 he was Chair of ACM SIGCOMM. He is a past editor for Computer Communication Review, IEEE/ACM Transactions on Networking, Computer Networks, and IEEE Transactions on Computers. He was the Program Chair for the 2003 ACM SIGCOMM Internet Measurement Conference and for IFIP Networking 2010, and the General Chair of the 2005 Passive and Active Measurement Workshop. His paper (with Azer Bestavros) "elf-Similarity in World Wide Web Traffic: Evidence and Possible Causes" received the 2010 ACM SIGMETRICS Test of Time Award, and his paper (with Paul Barford) "Critical Path Analysis of TCP Transactions" was nominated for the 2002 William Bennett Prize, given annually to the best paper published in IEEE/ACM Transactions on Networking. Professor Crovella is a Fellow of the ACM and the IEEE.