ASAP: an AS-Aware Peer-Relay Protocol for High Quality VoIP with Low Overhead

Introduction

Peer-to-peer (P2P) technology has been successfully applied in Internet telephony or Voice over Internet Protocol (VoIP), such as the Skype system, where P2P is used for both searching clients and relaying voice packets. Selecting a peer or multiple peers for voice packet relays is a critical factor for the quality, scalability and cost of a VoIP system. In this paper, we first present two groups of intensive Internet measurement results to confirm the benefits gained by peer relays in VoIP, and to investigate the performance of the Skype system. We obtain the following results: (1) many peer selections are suboptimal, (2) the waiting time for a peer relay node selection is quite long, and (3) there are a large number of unnecessary probes, resulting in heavy network traffic to limit scalability of the VoIP system.  Our further analysis shows that two main reasons cause these problems. First, the peer selections do not take autonomous system (AS) topology into consideration, and second, the complex communication relationship among peers is not well utilized. Motivated by our measurements and analysis, we propose an AS-aware peer-relay protocol called ASAP. Our objective is to significantly improve VoIP quality and system scalability with low overhead. Our intensive evaluation by trace-driven simulation shows ASAP is highly effective and easy to implement on the Internet for building large and scalable VoIP systems.

Our Program Source Code, Tools, and Corresponding Results Release

The following results are based on 2005-09-26 U.S. Eastern Time BGP tables and updates from the RouteViews, RIPE RIS, and China CERNET.

• Our BGP AS Paths and IP Prefixes to AS Numbers Mapping Results
  

• AS paths results
• IP Prefixes to AS number mapping results 
  

• Program to Group IP Addresses to AS and IP Prefix Clusters

• Java source code
  
• AS cluster IP counts and delegate IP Results
  

• Program to Look Up AS Number for an IP Address

• Java source code
• IP prefix to AS number mapping table we built 
  

• Annotated AS Graph Results

• IAS AS graph results based on Gao's IAS algorithm
• BPP AS graph results based on BPP algorithm

• King Utility Related Code

• Our modified King source code tar ball
  
• The King prober c code we have written
  

• ASAP Related Code

• ASAP, DEDI, RAND, MIX Java code
  
• Java code to identify the AS-hops of routing paths with specified RTTs
  

Publications

• Shansi Ren, Lei Guo, and Xiaodong Zhang, "ASAP: an AS-Aware Peer-Relay Protocol for High Quality VoIP with Low Overhead", in Proceedings of 26th International Conference on Distributed Computing Systems (ICDCS'06), Lisboa, Portugal, July 4 - 7, 2006.  presentation PPT
  

Public Sources We Have Used

•  BGP routing tables and updates repositories

• Routeviews BGP Archive
• RIPE RIS BGP raw data
  
• China CERNET BGP View

• Tools and Scripts to handle BGP raw data

• route_btoa utility to handle MRT BGP binary raw data, available at http://www.mrtd.net/   
  
• Shell scripts to extract AS paths out of BGP tables, from UMass Lixin Gao's group, available at http://rio.ecs.umass.edu/download.htm 
  

• Algorithm Source Code to build annotated AS graph

• Gao's IAS algorithm Perl source code, available at http://rio.ecs.umass.edu/download.htm 
• BPP algorithm C source code, available at http://www.dia.uniroma3.it/~compunet/relationships/ 
  

• LimeWire Open Source Gnutella

• LimeWire source code can be downloaded at http://www.limewire.com/english/content/home.shtml
  

• University of Washington's tool "King"

• tool "King" to estimate latency between arbitrary Internet end hosts, code available at http://www.mpi-sws.mpg.de/~gummadi/king/