California-Irvine group develops efficient algorithm to map internet networks

The internet may appear to work like magic in cyberspace, but it is actually a vast, complex connection of physical networks. Mapping those networks visually has been done in several ways, for example, geographically or by IP space. 

Network mapping is used to help improve the network efficiency and maintain it. It's important to know how data gets from one point to another and to correct any errors in the process.

At the International Online Symposium on Theoretical Aspects of Computer Science, March 15-18,  a group of researchers from the University of California, Irvine's Department of Computer Science presented a new, simplified algorithmic approach to network mapping. Their paper is titled "Mapping Networks via Parallel kth-Hop Traceroute Queries."

Mapping software and techniques exist to look at specific networks and interconnections with servers, devices and other networks.  Mapping also involves its own "language," terms for describing the tools and objects of mapping. 

The mapping is accomplished by sending out specific queries that provide information about the route used for data to get from one place to another in a network. In this way a topology of the network can be reconstructed.

Some mapping basics

Ramtin Afshar, lead author of the study, described some of the basic language and operations.

 "Network mapping is the study of learning how the nodes (components) of a network, such as the internet, are connected," he said.

Afshar is a Ph.D. candidate in the computer science department.

"Not all the nodes are connected together," Afshar said. "Think about each connection as a bridge that connects two nodes. The goal of the network mapping is to reveal the pairs of nodes that are connected together. A common technique for network mapping is active probing, which utilizes a tool such as traceroute to perform queries that reveal routing-path information."

Basically, it's a three-dimensional graphing system, where the object is to find the number of edges on the shortest path between vertices. Only certain information about nodes is available, known as a vantage point.

"We can perform our queries only from those nodes," Afshar said. "Our purpose is to reveal the connection between nodes in vantage point." 

The data packets travel in "hops," and hops are counted. The "kth hop" indicates any particular hop in a series.

Afshar noted "Traceroute works by sending a series of packets in a network from a source, u, to a destination, v, with the packets having increasing time-to-live (TTL) values, up to an upper bound." TTL refers to the amount of hops that a packet is programmed to exist before a router will discard it.

"The network mapping problem is related to graph reconstruction, which is very well studied," he said. "However, there are a number of differences between graph reconstruction and network mapping, each introducing novel challenges. Most significantly, the graph reconstruction problem assumes queries can be performed for any vertices in a particular subset, whereas in the network mapping problem, we may only issue kth-hop queries for nodes in the subset, vantage point. 

"In addition, previous work on graph reconstruction has not considered kth-hop queries, which form the `inner-loop' for how traceroute works," Afshar noted. "Another difference between the network mapping problem and graph reconstruction is that previous work on graph reconstruction has mostly focused on how to sequentially reconstruct the graph, whereas the network mapping problem is inherently parallel, due to the motivation from mapping real-world networks, where each node is a computer.”

An efficient algorithm

Describing the paper's advances, Afshar said, "In this paper we introduce a new technique that may be of independent interest, where we provide a new parallel implementation of a well-known graph clustering technique. In doing so we introduce a parameter that allows us to trade off parallel time and cluster size. We will then use this new construction to compute a graph-theoretic Voronoi diagram in our network mapping algorithm."

A Voronoi diagram is a partition of a plane into regions close to each of a given set of objects.

"Our paper provides the first mapping algorithm that efficiently, in parallel, reveals a shortest path graph between the vantage point using a subquadratic number of kth hop traceroute queries in constant number of parallel rounds," Afshar said. 

"Our results are significant in that we are the first to give an algorithm with a non-trivial number of queries to learn the network when we can only access vantage points to issue our queries," he added.

-----

R. Afshar, et al.,  "Mapping Networks via Parallel kth-Hop Traceroute Queries," International Online Symposium on Theoretical Aspects of Computer Science, March 15-18, 2022. https://drops.dagstuhl.de/opus/volltexte/2022/15814/pdf/LIPIcs-STACS-2022-4.pdf