Mapping The Internet

Updated Mon Oct 16 10:20:25 PDT 1995

Here are some results from my Internet Mapping project. I am endeavouring to make maps of the Internet for various purposes. These include:
- calculation of latency pools
- backbone and domain analysis
- strategic server placement
- general navigation and visualization

The process happens in several phases.

Tracing Domain Routes

Routes are traced using ICMP to all known domains on the Internet. This is an ongoing process.

traceroute to cluon.com (205.164.127.1), 30 hops max, 40 byte packets
 1  nexus-3.catapent.com (206.26.116.65)  2 ms  2 ms  5 ms
 2  border2-serial4-6.Denver.mci.net (204.70.29.69)  29 ms  29 ms  28 ms
 3  core-fddi-1.Denver.mci.net (204.70.3.113)  29 ms  29 ms  40 ms
 4  core-hssi-3.SanFrancisco.mci.net (204.70.1.38)  52 ms  52 ms  54 ms
 5  borderx2-fddi0-0.SanFrancisco.mci.net (204.70.3.164)  53 ms  54 ms  53 ms
 6  fix-west-nap.SanFrancisco.mci.net (204.70.158.118)  56 ms  54 ms  55 ms
 7  mae-west.net99.net (198.32.136.16)  277 ms  77 ms  96 ms
 8  3-E0.SanJose.net99.net (204.137.135.187)  65 ms  62 ms  68 ms
 9  204.157.1.158 (204.157.1.158)  65 ms  66 ms  65 ms
10  r2.brainstorm.net (205.164.112.34)  66 ms  64 ms  64 ms
11  gateway.cluon.com (205.164.127.2)  89 ms  177 ms  94 ms
12  cluon.com (205.164.127.1)  115 ms  214 ms  91 ms

Building The Logical Map

Routes are parsed by the netmap tool, which builds up a web-like map of the Internet. Average latencies for each link are calculated and stored in the map.

Graph Coloring

We want to find connected areas in the Net which can all reach each other within some pre-specified latency. We display these areas as regions of the same color. There are many regions on the net, and each is assigned a random color.

A graph coloring algorithm with back-propogation is used to find these latency pools.

3D Placement

In order to view the map, a 2D or 3D topology must be generated. The current algorithm creates a 3D map. It starts by assigning a random 3D location to every node in the Network map. It looks like this:

Zero iterations.

Reaction-Diffusion

Then a reaction-diffusion style algorithm is used to move nodes around. There are an infinite number of possible algorithms that can be used. Currently I iterate through the map and apply a force-field function at each node. There are a number of these functions applied at each iteration. They are:

- Latency Attraction. a node is attracted to its directly connected neighbors. It attempts to position itself so that its distance from each connected neighbor is a linear function of its latency to that neighbor.

- Spatial Repulsion. a node exerts a repulsion field on all nodes that are within a pre-defined distance from it. This repulsion field is dampened for neighboring nodes which are topologically connected to the node.

Iteration of this algorithm tends to unfold the Net map, while creating regions which are topologically connected. The length of links in the map is propotional to the latency between those links.

40 iterations.

Organic Forms

As this reaction-diffusion algorithm runs, the repulsion effects are progressively dampened out until, in the final stages of iteration, only the latency-attractor field is in effect. As you can see in the following picture, the map is evolving to take on an organic appearance, much like a bundle of roots or a network of arteries.

180 iterations.

Even More

These maps contain all the edu domains. They also contains several thousand com domains. There are over 130,000 registered com domains, and I am gathering information about them on an ongoing basis.

These maps were generated between Oct 12, 1995 and Oct 16, 1995. The routes that make up the above maps took over 80 hours to collect, and set off at least one Internet security advisory warning! Several more weeks and we'll be done our first pass!

180 iterations of the placement algorithm on this data took 7.5 hours on a Sun Sparcstation5. It required about 7Mb of space (tiny!).

LinkExchange Member