Cheleby: An Internet Topology Mapping System

SAMPLE COLLECTED DATA IS AVAILABLE

Note: Cheleby will be up and running once we are able to get our PlanetLab servers hosted outside University firewall.

Internet is a web of interconnected backbone networks of high speed. Thousands of small and medium size Autonomous Systems (ASes) interconnect individuals, businesses, universities, and agencies over the Internet backbone. Internet is the largest man-made complex network which has far exceeded initial design goals. While the building blocks of the Internet, its protocols and individual components, have been subject to intensive studies, the immense global entity has not been precisely characterized. Moreover, the Internet's global properties cannot be inferred from local ones as it is composed of networks engineered with large technical diversity and range from small local campuses to large transcontinental backbone providers. There is a general lack of understanding of Internet topology.

Understanding the topological and the functional characteristics of the Internet is an important research issue as the Internet grows with no central authority. This understanding is not simply an intellectual curiosity, but also a necessity to better design, implement, protect and operate the underlying network technologies, protocols, and services. Complexity is a major constraint for the design and management of computer networks and protocols.

In this project, we develop a system, Cheleby, that provides insight into Internet topology by taking snapshots of the underlying networks. Cheleby will collect topology information from the Internet using PlanetLab. The system utilizes efficient algorithms to process large scale data-sets collected from various vantage points and provide topology graphs. Cheleby will help to (1) fine-tune existing services such as content distribution, (2) develop more efficient protocols, (3) monitor connectivity and identify bottlenecks, (4) and guide the development of the next generation Internet.

Below are three related slides.

• Internet Topology Discovery
• Internet Measurements
• Cheleby Mapping System

People:

• Mehmet H. Gunes (University of Nevada, Reno)
• Mehmet Burak Akgun (University of Nevada, Reno)
• Hakan Kardes (University of Nevada, Reno)

Publications:

• Hakan Kardes, Talha Oz, and Mehmet Hadi Gunes "Cheleby: A Subnet-level Internet Topology Mapping System", 4th International Conference on COMmunication Systems and NETworkS (COMSNETS), Banglore, India, Jan 3-7, 2012.
  Abstract:Understanding the topological characteristics of the Internet is an important research issue as the Internet grows with no central authority. Internet Topology mapping studies help better understand the dynamics of the Internet backbone network. Knowing underlying topology, researchers can develop new protocols and services or fine-tune existing ones. In this paper, we first discuss issues in subnet-level Internet topology mapping and present approaches to handle them. Then, we introduce Cheleby, an integrated Internet topology mapping system. Cheleby, first, dynamically probes every observed subnetwork in the Internet using a team of PlanetLab nodes around the world. Then, it utilizes efficient algorithms for resolving subnets, IP aliases, and unresponsive routers in collected data to provide subnet-level topologies. Different from current topology mapping systems, Cheleby not only samples the Internet topology but also processes the collected data to build more complete maps. Sample topologies are provided at http://cheleby.cse.unr.edu
  
• Mehmet H. Gunes and Kamil Sarac, "Resolving IP aliases in Building Traceroute-Based Internet Maps", IEEE/ACM Transactions on Networking 17(16):1738-1751, Dec 2009.
  Abstract: Alias resolution, the task of identifying IP addresses belonging to the same router, is an important step in building traceroute-based Internet topology maps. Inaccuracies in alias resolution affect the representativeness of constructed topology maps. This in turn affects the conclusions derived from studies that use these maps. This paper presents two complementary studies on alias resolution. First, we present an experimental study to demonstrate the impact of alias resolution on topology measurement studies. Then, we introduce an alias resolution approach called Analytic and Probe-based Alias Resolver (APAR). APAR consists of an analytical component and a probe-based component. Given a set of path traces, the analytical component utilizes the common IP address assignment scheme to infer IP aliases. The probe-based component introduces a minimal probing overhead to improve the accuracy of APAR. Compared to the existing state-of-the-art tool ally, APAR uses an orthogonal approach to resolve a large number of IP aliases that ally fails to identify. Our extensive verification study on sample data sets shows that our approach is effective in resolving many aliases with good accuracy. Our evaluations also indicate that the two approaches (ally and APAR) should be used together to maximize the success of the alias resolution process.
  
• Mehmet H. Gunes and Kamil Sarac, "Analyzing Router Responsiveness to Measurement Probes", Passive and Active Measurement Conference (PAM 2009), Seoul, South Korea, April 1-3 2009.
  Abstract:Active probing has increasingly been used to collect information about the topological and functional characteristics of the Internet. Given the need for active probing and the lack of a widely accepted mechanism to minimize the overhead of such probes, the traffic and processing overhead introduced on the routers are believed to become an important issue for network operators. In this paper, we conduct an experimental study to understand the responsiveness of routers to active probing both from a historical perspective and current practices. One main finding is that network operators are increasingly configuring their devices not to respond to active direct probes. In addition, ICMP based probes seem to elicit most responses and UDP based probes elicit the least.
  
• Mehmet Hadi Gunes and Kamil Sarac, "Resolving Anonymous Routers in Internet Topology Measurement Studies", IEEE INFOCOM, Phoenix, AZ, April 15-17 2008.
  Abstract:Internet measurement studies utilize traceroute to collect path traces from the Internet. A router that does not respond to a traceroute query is referred to as an anonymous router and is represented by a ‘*’ in the traceroute output. Anonymous router resolution refers to the task of identifying the occurrences of ‘*’s that belong to the same router in the underlying network. This task is an important step in building traceroute-based topology maps and obtaining an optimum solution is shown to be NP-complete. In this paper, we use a novel technique from graph data mining field to build an efficient solution. The results of our experiments on both synthetic and genuine topologies show a significant improvement in accuracy and effectiveness over the existing approaches.
  
• Mehmet Hadi Gunes and Kamil Sarac, "Inferring Subnets in Router-level Topology Collection Studies", ACM SIGCOMM Internet Measurement conference (IMC 2007), San Diego, CA, Oct 24-26 2007.
  Abstract:Internet measurement studies require availability of representative topology maps. Depending on the map resolution (e.g., autonomous system level or router level), the procedure of collecting and processing an Internet topology map involves di®erent tasks. In this paper, we present a new task, i.e., subnet inference, to advance the current state of the art in topology collection studies. Utilizing a technique to infer the subnet relations among the routers in the resulting topology map, we identify IP addresses that are connected over the same connection medium. We believe that the successful inclusion of subnet relations among the routers will yield topology maps that are closer, at the network layer, to the sampled segments of the Internet in router level topology measurement studies.
  

Last Updated on Dec 5, 2012.