routing
network congestion

Using "six degrees of separation" could lessen network congestion

Next Story

Handy chart for understanding aspect ratio and resolution

To ease the effects of increasing congestion on networks, researchers are looking to a 1960s sociology experiment that could hold the key to better Internet routing.

Internet routers are currently using the border gateway protocol (BGP) standard to map out the path that data takes. BGP requires each router to store a list of network addresses (aka routing table) which tells it where to forward packets of information. As the number of Internet-connected machines increase, routing tables are growing longer and require updates more frequently, slowing down a network. What can be done?

One proposed solution lies within a 1960s experiment you may be familiar with carried out by Stanley Milgram called the “six degrees of separation.” If you don’t know what I’m talking about, shame on you for not paying attention in school. These experiments involved giving 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 found that there was an average of 5.2 steps between the sender and the end recipient.

Professor Jon Kleinberg of Cornell University further studied Milgram’s work in 2000 and created a mathematical model for routing information across any kind of network. He explained that Milgram “demonstrated not just that short paths were present in large social networks, but that people could efficiently find them.” Kleinberg is currently working on MemeTracker, an interesting site that builds maps of the daily news cycle.

More recently, Marián Boguñá and his colleagues at the University of Barcelona suggest that the approach could by applied to real-world networks, including the Internet’s routing system. Boguñá and his colleagues explain that the work of Kleinberg and others can be applied to real-world networks and could be used to design a protocol that allows routers to keep track of less information about a network, reducing congestion.

The real-world integration of this idea would rely on identifying “hidden” bits of information that could help routers decide where to send a packet, according to Boguñá. The people in Milgram’s experiment sought information about a person that would help them to get a step closer to the end recipient. For 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.

Some warn that it’s too early to tell if the approach is feasible on real-world networks. Boguñá admits that he is in the initial stages of his research and this may take several more years to figure out. We’re rooting for you, Boguñá and colleagues.

blog comments powered by Disqus