Tuesday, December 09, 2008
The Social Life of Routers
How a 1960s sociology experiment could hold the key to better Internet routing.
By Erica Naone --- technologyreviewl.com
Just like an old-fashioned piece of mail, data traveling over the Internet normally follows a predictable path. As the Internet continues to grow, however, experts have begun to worry that current routing protocols will be unable to cope with increased congestion. And so, as researchers search for new solutions, some are taking inspiration from a famous social experiment that called on people to deliver mail using only a network of friends.
For many years, Internet routers have used a standard known as the border gateway protocol (BGP) to map out the path that data takes. BGP requires each router to store a list of network addresses, known as a routing table, which tells it where to forward packets of information (based on a complete picture of that network). But as the number of Internet-connected machines increases, routing tables grow longer and need to receive updates more frequently, potentially slowing some traffic to a crawl. A major sticking point for the BGP protocol is that every time part of the network changes, every router must process an update.
This is where the work of sociologist Stanley Milgram could help out. Milgram carried out experiments in the 1960s that helped make famous the idea of "six degrees of separation." Milgram gave volunteers the task of forwarding a letter to a stranger by sending it to friends or acquaintances that might be one step closer to the target. Milgram measured how many hops there were between the sender and the end recipient, and found it to be, on average, 5.2. (The term six degrees of separation was coined later by playwright John Guare.)
In 2000, inspired by Milgram's work, Jon Kleinberg, a professor of computer science at Cornell University, in New York, created a mathematical model for routing information across any kind of network. Kleinberg says that he drew from the fact that Milgram "demonstrated not just that short paths were present in large social networks, but that people--operating without a global view of the network--could efficiently find them."
Now, research from Marián Boguñá at the University of Barcelona and colleagues, suggests that the approach could indeed by applied to real-world networks, including the Internet's routing system. In work published recently in Nature Physics, Boguñá and his colleagues argue that the work of Kleinberg and others can be applied to real-world networks and, specifically, could be used to design a protocol that allows routers to keep track of less information about a network, thereby reducing congestion.
The key lies in identifying "hidden" bits of information that could help routers decide where to send a packet, Boguñá says. The people in Milgram's experiment used such information to figure out how to forward their letters. Instead of passing them on to a random friend, they identified criteria, such as a person's profession, that meant that they might be a step closer to the intended recipient. The work of Boguñá and his colleagues focuses on identifying and exploiting hidden information on other kinds of networks. In the case of Internet routing, the physical location of a router or the type of information it last handled could provide useful clues for forwarding information toward a final destination without knowing the complete structure of the network.
Kleinberg says that the work is "a very elegant approach to exploring the underlying structures that make navigability possible in real networks." He adds that Boguñá's group's "techniques have the potential to inform a new class of routing strategies in which global information is replaced by local strategies that follow hidden metrics."
However, Jon Crowcroft, a professor of communication systems at the University of Cambridge, U.K., warns that, while Boguñá's group has done good work in applying Kleinberg's theoretical models, it's too early to tell if the approach would actually work. "When you look at it in reality," he says, "there are other additional constraints," such as the requirements of particular applications. Nonetheless, Crowcroft believes that this direction is "absolutely worth exploring" and says that he would like to see the researchers try some real-world experiments.
Boguñá himself admits that his work is "very preliminary." The next step, he says, is to identify what "hidden metrics" could be used for Internet routing. But Boguñá expects that this could take several more years to figure out.
Posts
