Smart Networks
Asociological theory could help overloaded routers direct traffic

Source: “Navigability of Complex Networks”
Marián Boguña et al.
Nature Physics 5: 74­-80

Results: Researchers at the University of Barcelona and the University of California, San Diego, have developed a mathematical model demonstrating that Internet routers can effectively deliver data even without detailed information about all the routers in a network. Having limited information about neighboring routers is enough.

Why it matters: The current system for routing data between the networks of different Internet service providers (ISPs) isn’t expected to continue working as the Internet grows. The routers that handle this traffic require lists of network addresses, called routing tables, which tell them where to forward packets of information. These tables must be regularly updated, a process that can take minutes for a single change. As the network grows, the number of updates increases to the point that the tables are almost never up to date, and parts of the network are not accessible because addresses are missing. These problems could be avoided with the new model, since it doesn’t require up-to-date routing tables.

Methods: The researchers looked to ­sociology experi­ments from the 1960s in which a person was asked to forward a letter to a stranger by sending it through friends and acquaintances. It took only a few hops for the letter to reach its intended recipient because people used clues, such as a friend’s profession, to guess who might help move the letter closer. Similarly, the researchers’ model shows that by using only a little bit of information about the nearest neighboring routers, such as their location and the type of traffic they recently received (data that can be acquired quickly via the direct link between neighbors), routers can continue to deliver packets of information even if their routing tables are missing addresses.

Next steps: The researchers suspect that they could further improve the performance of their model by looking at the location and traffic history of routers a few hops away from a particular router. They also hope to test the protocol in a working network.