Mapping Internet Black Holes

You're trying to log on to a Web site and it's not working. You try again and again. But persistence doesn't pay off. The site you want is inexplicably, frustratingly, out of reach.

The other computer might just be turned off, but the causes could be more mysterious. At any given moment, a proportion of computer traffic ends up being routed into information black holes. These are situations where a path between two computers does exist, but messages -- a request to visit a Web site, an outgoing e-mail -- get lost along the way.

A University of Washington system named Hubble looks for these black holes and maps them on a Web site, providing an ever-changing constellation of the Internet's weak points.

The Hubble map lets visitors see a map of problems worldwide or type in a specific Web page or network address to check its status. The work is being presented next week in San Francisco at the Usenix Symposium on Networked Systems Design and Implementation.

"There's an assumption that if you have a working Internet connection then you have access to the entire Internet," said first author Ethan Katz-Bassett, a UW doctoral student in computer science and engineering. "We found that's not the case."

The project is named for the Hubble Space Telescope, which can observe black holes in deep space, because the UW tool performs a similar function for the maze of routers and fiber-optic cables that make up the Internet. In fact, research on the Internet's structure and performance is sometimes described as Internet astronomy.

"It's the idea of peering into the depths of something and trying to figure out what's going on, without having direct access," Katz-Bassett said.

The UW researchers send test messages around the world to look for computers that can be reached from some but not all of the Internet, a situation known as partial reachability. Short communication blips are ignored; a problem has to register in two consecutive 15-minute trials to appear on the site. A test last fall found that more than 7 percent of computers worldwide experienced this type of error at least once during a three-week period.

"When we started this project, we really didn't expect to find so many problems," said Arvind Krishnamurthy, a UW research assistant professor of computer science and engineering and Katz-Bassett's doctoral adviser. "We were very surprised by the results we got."

Other co-authors on the study are Harsha Madhyastha, John P. John, David Wetherall and Thomas Anderson, all in the UW's department of computer science and engineering. The research received funding from the National Science Foundation.

Now the team has created an online global map, updated every 15 minutes, showing locations currently experiencing problems. Hubble shows a flag on the area that's experiencing problems and lists the numerical address for the group of computers affected. Each address typically describes a few hundred to a few thousand individual computers. Hubble also reports what percentage of test probes was successful, and how long each problem has persisted.

Clicking a flag reveals which locations were and were not able to reach that machine. Future versions of Hubble will try to pinpoint the cause of each black hole.

Hubble's virtual eye on the Internet is made possible by PlanetLab, a shared worldwide network of academic, industrial and government computers. The UW researchers use about 100 PlanetLab computers in about 40 countries to send virtual probes to computers around the globe. Hubble monitors about 90 percent of the Internet, researchers said.

The new map can satisfy a frustrated user's idle curiosity about why a Web site is not loading. But the tool promises to be especially useful to professional network operators who keep the Internet running smoothly. Right now, when a computer network experiences a problem the administrator typically turns to online discussion boards.

"You would think that the network operators of Internet service providers would have access to better data," said Katz-Bassett. "That's not the case. The general approach has been to mail something out to a listserv and say, 'Hey, can you try this and see if you have a problem?'"

In a world that relies increasingly on online communication for e-mail, banking, television, phone calls, medical information and emergency communications, researchers want to make the overall network more transparent and more reliable.

"We want to give operators a way to tell what's going on quicker, catch problems quicker and solve them quicker," Krishnamurthy said.