Abstract
Most router-level measurement studies utilize the well-known Internet debugging tool tracer-
oute or its variants. Traceroute returns a path from a local system to a given remote system by
tracing the routers in between. After the collection of the path traces, the information needs
to be processed to build the corresponding network topology. Routers have multiple interfaces,
each one having a dierent IP address. A router may appear on multiple path traces with
dierent IP addresses. Therefore, there is a need to identify IP addresses belonging to the
same router. This task is named IP alias resolution. Without alias resolution, the resulting
topology map may be signicantly dierent from the real topology. The contributions of this
paper include an experimental study that demonstrates the impact of alias resolution on ob-
served topological characteristics. It introduces a new alias resolution approach, Analytical
and Probed-Based Alias Resolution,APAR, which depends on an analytical approach to infer
a large number of IP aliases. The paper concludes with an evaluation of the APAR.
Keywords: Alias resolution, traceroute, network topology, router-level measurement.

[attachment=8545]

1 Introduction
Internet topology measurement studies consist of three phases: 1) topology collection; 2)
topology construction; and 3) topology analysis.There are several projects that collect large
scale Internet maps.These projects utilize traceroute like tools for topology collection. Tracer-
oute returns a path from a local system to a given remote system by tracing the routers in
between. After the collection of the path traces, the information needs to be processed to build
the corresponding network topology. This step involves resolving IP addresses belonging to the
same router.
Each interface of router has a unique IP address. A router may respond with dierent IP
addresses to dierent queries. Alias Resolution is the process of grouping the interface IP
addresses of each router into a single node. Inaccuracies in alias resolution may result in a
network map that includes articial links/ nodes, or misses existing links/ nodes.
5
2 Related Work
The initial work on alias resolution utilizes source IP addresses. Given a set of IP addresses, the
algorithm sends probe packets to IP addresses to solicit ICMP error messages. Probing an IP
address IP1, if the returning ICMP port unreachable message has a source IP address of IP2,
then IP1 and IP2 are set as aliases. Mercator and inder use this method. Mercator improves
by sending multiple probes to the given IP addresses from a number of dierent source-routing
capable routers. inder discovers additional aliases by using the Route Record option of IP
(RFC 791). The second approach uses potential similarity in IP identication eld values in the
returning ICMP packets. Since some operating systems implement IP identication value as a
monotonically increasing counter, successive packets originating from such a router would have
consecutive IP identication values. Ally tool combines the address-based method with the IP
identication-based method to classify a pair of IP addresses as alias, not-alias, or unknown.
These methods are simple and powerful in resolving IP aliases. However, being active probing
approaches, they introduce probing overhead ( probes in the case of ally, where is the number
of IP addresses). They also depend on routers participation by replying to the probe messages.
Considering the increasing volume of measurement trac in the Internet, many ISPs congure
their routers to respond to traceroute probes, but ignore or rate limit direct probes destined to
themselves. This practice aects the utility of the existing alias resolution tools.
Compared to the existing approaches, APAR introduces a more scalable approach to resolve
IP aliases. The analytical component introduces no probing overhead and requires no router
participation. The probe-based component incurs a signicantly lower probing overhead to
improve the overall accuracy of the APAR approach. Being two orthogonal approaches, APAR
and ally do not compete, but complement each other in maximizing the success rate of the
overall alias resolution process.
6
3 Quantifying the Impact of Alias Resolution
In this section, a study on the impact of alias resolution in building traceroute-based topology
maps is done. The eect of imperfect alias resolution on a broad set of graph properties on a
genuine topology is analyzed. In general, a failure in alias resolution results in false negatives.
On the other hand, a false positive is introduced when two addresses are incorrectly considered
as alias.The eect of imperfect alias resolution on a broad set of graph properties as summarized.
The considered graph characteristics can be grouped into size, node degree, clustering, path
length, and betweenness-related characteristics.
3.1 Topology size
Topology size, in terms of the number of nodes n and links m, is the basic information regarding
a network. It also dene the average node degree (k) as k = 2m
n . According to the experiment
results, the alias resolution success rate, i.e., false negatives, has a big impact on the topology
size, as seen in Fig. 1. In the gure, each color shows the additional articial nodes/links added
into the nal topology map with diminishing success rate.In contrast to false negatives, false
positives reduce the topology size by incorrectly merging unique nodes.
Figure 1: Impact of false negatives on topology size.
3.2 Node Degree
The accuracy of the alias resolution process has considerable impact on the node degree related
characteristics. Although one may intuitively expect an improvement in the accuracy of degree-
related characteristics with an increasing success rate of the alias resolution process, such a trend
is not necessarily observed all the time, as seen in Fig. 2.
3.3 Degree Distribution
Degree distribution represents the probability P(k) that a randomly chosen node has degree
k. The degree distribution changes with the changing success rate of the alias resolution pro-
7
cess, but dierent eects are observed with dierent samples. As alias resolution success rate
improves, degree distribution converge to the distribution of real topologies.
3.4 Joint Degree distribution
Joint degree distribution (JDD) P(k,k' )characterizes the degree relation of nodes i.e., it reports
the probability that a node of degree k and a node of degree k' are connected. Assortative
coecient r is a summary statistic of JDD, and it measures the tendency of a network to
connect nodes of the same or dierent degrees. As alias resolution gets closer to 100, they
appear to be slightly assortative.
Figure 2: Degree Comparison for sample topologies.
8
3.5 Clustering
Clustering characterizes the density of the connections in the neighborhood of a node. The
clustering distribution with respect to node degree is analyzed and an increase with increasing
alias resolution success rate is observed.
3.6 Betweenness
Betweenness is a measure of centrality. It reports the total number of shortest paths that pass
through node.Average betweenness reduces with an improvement in the alias resolution success
rate. This is due to the fact that as the alias resolution rate improves, articial nodes are
removed from the network, causing a reduction in the number of path pairs that contribute to
the betweenness.
From the above analysis on various characteristics, it can be concluded that the completeness
and the accuracy of the alias resolution process has a signicant impact on the results of studies
that use traceroute-based topology data.
9
4 Observations
This section present a summary of IP address assignment practices in the Internet and show
how it can be used to identify IP aliases from a given set of path traces.
4.1 IP Address Assignment Practices
IP address space is a scarce commodity and is used in a systematic way with a great care. The
IP address assignment mechanism adheres to the guidelines presented in the Internet Registry
IP Allocation Guidelines (RFC 2050). Basically, IP addresses belonging to a domain or an
ISP network are divided into subnet ranges for each connection medium. Each subnet has a
network address, and each interface, belonging to an end host or a router within the subnet,
gets an IP address from the range of the network address given to the subnet. In general, up
to n device interfaces can be connected using a /x subnet where n = 232