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.
- 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
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
Last Updated on Dec 5, 2012.