Network administrators have long used Van Jacobson's traceroute [15] to identify the path taken by outgoing packets towards a given destination. Each ``hop'' on the outgoing path is a router, and most routers will respond to a traceroute-style packet with the IP address of one of its network interfaces.
By obtaining a list of all announced networks on an internet, and discovering the path to each of these networks, we build a good picture of the ``center'' of the Internet, and a kind of picture of what the Internet looks like as a whole. Of course, this is an egocentric view, as it only captures the paths taken by our outgoing packets. Thus, the picture is a reachability graph, not a complete map.
In the course of developing and testing our mapping software, we discovered that mapping is a more generally useful pursuit, as it became obvious that mapping an intranet is valuable. Large intranets are hard to manage and offer many security problems. A map can yield a lot of information and can help spot likely leaks in a company's perimeter security.
Each morning the mapping program scans two separate networks: Lucent's intranet and the Internet itself. On Lucent's intranet, the mapping program does run full scans daily. On the Internet, our daily scans cover about one tenth of the destinations, reaching each announced network about three times a month. The mapping program runs full scans of the Internet about once a month. The Internet data is published on a web page [23] and saved to CD-ROM. We plan to run these scans for years.
This scanning allows us to detect long-term routing and connectivity changes on the Internet. We are likely to miss the outage of a major backbone for a few hours, unless it happens while we are scanning. But a natural disaster, or major act of terrorism or war, may well show up.
Due to the magnitude of the resulting databases, a method of visualizing it is required. The eye can help us gain some understanding of the collected data. We can pick out interesting features for further investigation and find errors in Internet router configurations, such as routers that return invalid IP addresses. We'd like to have a large paper map with the properties of traditional flat maps: they can help one navigate towards destinations, determine connectivity, readily reveal major features and interesting relationships, and are hard to fold up.
We use a spring-force algorithm to position the nodes on the map. A few simple rules govern the adjustment of a point's position based on proximity of graph neighbors, number of incident edges, and the number and position of close nodes that are not neighbors. We shuffle these points for 20 hours on a 400MHz Pentium to obtain the maps shown in this paper. The maps of Lucent take 20 minutes to an hour to lay out, depending on whether all the links are shown or just a spanning tree. Sample graph sizes are:
| networks | edges | nodes | |
| Lucent | 3,366 | 1,963 | 1,660 |
| Internet | 94,046 | 99,664 | 88,107 |