Resolving IP Aliases in Building Traceroute-Based Internet Maps
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
summer project pal
Active In SP

Posts: 308
Joined: Jan 2011
29-01-2011, 07:07 PM

Resolving IP Aliases in Building Traceroute-Based Internet Maps
A Seminar Report


Department of Computer Science & Engineering
College of Engineering Trivandrum
Kerala - 695016

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 di erent IP address. A router may appear on multiple path traces with
di erent 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 di erent 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.

.pdf   Resolving IP Aliases in Building.pdf (Size: 290.67 KB / Downloads: 53)

1 Introduction
Internet topology measurement studies consist of three phases: 1) topology collection; 2)
topology construction; and 3) topology analysis.There are several project and implimentations that collect large
scale Internet maps.These project and implimentations 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 di erent IP
addresses to di erent 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.
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 di erent 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 a ects 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.
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 e ect 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 e ect 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-
cess, but di erent e ects are observed with di erent 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 di erent degrees. As alias resolution gets closer to 100, they
appear to be slightly assortative.
Figure 2: Degree Comparison for sample topologies.
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.
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

Important Note..!

If you are not satisfied with above reply ,..Please


So that we will collect data for you and will made reply to the request....OR try below "QUICK REPLY" box to add a reply to this page

Quick Reply
Type your reply to this message here.

Image Verification
Please enter the text contained within the image into the text box below it. This process is used to prevent automated spam bots.
Image Verification
(case insensitive)

Possibly Related Threads...
Thread Author Replies Views Last Post
  A TECHNICAL SEMINAR ON 3D INTERNET seminar projects maker 1 752 06-04-2016, 12:37 PM
Last Post: mkaasees
  seminar report on internet of things jaseelati 0 378 29-01-2015, 04:51 PM
Last Post: jaseelati
  3d internet seminar report jaseelati 0 266 11-12-2014, 02:16 PM
Last Post: jaseelati
  3d internet seminar report jaseelati 0 350 06-12-2014, 04:25 PM
Last Post: jaseelati
  Optical Packet Buffers for Backbone Internet Routers pdf seminar projects maker 0 422 28-09-2013, 02:48 PM
Last Post: seminar projects maker
  Building Java Web services with NetBeans 7 seminar projects maker 0 432 24-09-2013, 12:44 PM
Last Post: seminar projects maker
Music SILC(Secure Internet Live conferencing) Download The Seminar Report computer science crazy 11 7,226 31-08-2013, 12:20 PM
Last Post: study tips
  INTERNET PROTOCOL VERSION 6 PPT study tips 0 591 06-08-2013, 03:20 PM
Last Post: study tips
  Internet protocol resolver PPT study tips 0 376 31-07-2013, 02:59 PM
Last Post: study tips
  Towards 3D Internet: Why, What, and How? pdf study tips 0 391 16-07-2013, 02:24 PM
Last Post: study tips