The Social Life of Routers

How a 1960s sociology experiment could hold the key to better Internet routing.

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.

source: Technology Review

--

Sam