The Department of Computer Science at the University of Cyprus cordially invites you to the Colloquium entitled:

On Two Network Measurement Problems: Inferring Autonomous System Relationships and Computing Network Traffic Heavy Hitters


Speaker: Dr. Xenofontas Dimitropoulos
Affiliation: ETH Zurich, Switzerland
Category: Colloquium
Location: Room 148, Faculty of Pure and Applied Sciences (FST-01), 1 University Avenue, 2109 Nicosia, Cyprus (directions)
Date: Monday, May 11th, 2009
Time: 11:00 - 12:00 EET
Host: Demetris Zeinalipour (dzeina AT

Contractual relationships between Autonomous Systems (AS) affect inter-domain packet routing and shape the evolution and properties of the global AS-level topology of the Internet. In this talk, I will first describe the problem of inferring AS relationships and then will introduce novel inference heuristics finding customer-to-provider, peer-to-peer, and sibling-to-sibling relationships. I will outline validation results based on a survey with network operators showing inference accuracy between 82.8% and 96.5%. Finally, I will discuss an AS relationships repository we have opened to make our results useful for the community where we archive periodically the Internet AS-level topology annotated with inferred AS relationships. In the second part of the talk, I will switch to discussing the problem of computing network traffic heavy hitters using limited memory resources. I will briefly introduce the IBM Aurora system, which provides the context of our interest and then I will present an algorithm called Probabilistic Lossy Counting (PLC) for finding network traffic heavy hitters. PLC enhances the well-known lossy counting algorithm using on a tighter error bound on the estimated sizes of traffic flows providing probabilistic rather than deterministic guarantees on its accuracy. Performance comparison experiments show that PLC has between 34.4% and 74% lower memory consumption and between 37.9% and 40.5% fewer false positives than other state-of-the-art algorithms.

Short Bio:
Xenofontas Dimitropoulos is a Senior Researcher in the Communication Systems Group (CSG) of ETH and an Associate Tutor in the Open University of Cyprus (OUC). He received a PhD degree in Electrical and Computer Engineering from Georgia Tech. In the past, he was a post-doc in the IBM Zurich Research Laboratory, where he worked in the IBM Aurora traffic flow collector project (now part of the IBM Tivoli suite), and a visiting scholar in the Cooperative Association for Internet Data Analysis (CAIDA). His research interests focus on traffic flow measurements, inter-domain routing, and network simulation. He has had various honors, like leading the graduation oath in his BSc degree for the highest GPA, a Fulbright scholarship, a Marie Curie scholarship, a best paper award, and a best paper nomination.

  Mailing List:

Sponsor: The CS Colloquium Series is supported by a generous donation from Microsoft