Removing 'black sheep' could make Internet run more efficiently

February 28th, 2012 by Lisa Zyga in Technology / Computer Sciences
Partial map of the Internet based on data from 2005. Links connect nodes that represent IP addresses. Image credit: Wikimedia Commons, CC BY 2.5


Partial map of the Internet based on data from 2005. Links connect nodes that represent IP addresses. Image credit: Wikimedia Commons, CC BY 2.5

(PhysOrg.com) -- Whether dealing with Internet traffic or vehicle traffic, congestion can slow everything down. One team of researchers working on improving network transmission efficiency has developed a strategy that identifies certain links or edges that can be removed to decrease the overall congestion. Somewhat counterintuitively, these links - which the researchers call "black sheep" - are those that connect the busiest hubs. In a sense, the strategy is similar to closing some of the busiest roads during rush hour, and finding that vehicles reach their destinations faster than before.

The researchers, Guo-Qing Zhang, Di Wang, and Guo-Jie Li, from the Chinese Academy of Sciences in , published the strategy in 2007. In their most recent paper, published in Scientia Sinica Informationis, they have continued to build on this idea by determining the necessary conditions for the effect’s existence.

“Our main findings reveal the effect of enhancing capacity of edge-removal in networks and the prerequisite of the effect,” Zhang told PhysOrg.com. “However, the results of capacity expansion depend on specific networks. For the popular BA model network, this method increases network capacity more than 10 times.”

The Internet is a combination of many interconnected networks, each of which consists of nodes (e.g., computers and routers) and (e.g., cables and optical fibers). Structurally, this framework is similar to all networks in areas as diverse as biology, sociology, and statistics. In the case of the Internet, data is stored as bits, and thousands of bits are combined in packets that are directed by routers to their destinations. Routers use certain strategies to get packets to their destinations as quickly as possible, sending them along links from one node to another in a split second.

The many different strategies proposed so far for increasing the Internet’s fall under two categories: developing better routing strategies and optimizing the network itself. The researchers from the show that modifying the network does not necessarily require a complicated redesign; instead, deleting just a few well-chosen links is relatively easy and effective.

The key is choosing which links to remove. To do this, the researchers analyzed a network model that simulates packet traffic. In the model, routers use a shortest path routing strategy to direct packets to their destinations. Then the researchers analyzed each node to see how often it lies along the shortest path between two other nodes. For instance, if the shortest path between nodes A and B passes through node C, then C would be between A and B, increasing C’s value of a quantity called “betweenness.” Because nodes with large betweenness values are part of a greater number of shortest paths than peripheral nodes, they become congested more easily. To decrease this congestion, the researchers removed a fraction of the links connecting two nodes with some of the highest betweenness values. As a result, packets had to detour around these hub nodes, taking a slightly longer path but easing congestion in the most congestion-prone areas.

As a consequence, removing these black sheep links significantly increased the network’s transmission capacity. From a practical perspective, removing these few links is easier than redesigning the entire network or developing a complex routing strategy. However, the researchers noted that there is a limit to removing links, where removing too many will lower the overall efficiency.

In their most recent study, the researchers show that, in order for this method to work effectively, the network structure must be heterogeneous in terms of node betweenness values. In other words, the method works best for networks that have nodes with a greater diversity of betweenness values. In this way, networks with large heterogeneity, which can be measured by the well-known Gini coefficient, have more significant effects.

“Our recent paper doesn't further improve network capacity of the method, but points out that heterogeneity of network structure is a necessary condition for the effect’s existence, highlights the rationality based on betweenness, and discusses the effect’s applications in engineering practice,” Zhang said. “It also shows that the greater the heterogeneity of a network is, the better the effect is. In essence, our method can reduce the heterogeneity, hence load balance, and then capacity is enhanced.”

Because the black sheep links often use the highest bandwidths, removing them provides another advantage: it saves energy and reduces the cost of bandwidth, construction and maintenance. The researchers hope that the combination of increased transmission capacity and reduced cost will motivate the wide application of this method to a variety of communication and transportation networks.

“Edge removal is only an abstract concept, it may have different forms in different contexts,” Zhang said. “Let me take urban transportation networks as an example: blocking the entrance ramp can relieve congestion and help traffic move more smoothly during rush hour. Here, blocking the entrance ramp logically means edge removal. For the Internet, building overlay routing is an important way to improve network reliability. This can be achieved by setting up relay nodes to obtain path diversity and enhance forwarding efficiency. A relay node needs to close some key links during heavy load. Closing links can be easily implemented and automatically finished by software. In the second instance, closing links mean edge removal. In a word, edge removal has many variants in practice.”

More information: Zhang GuoQing and Cheng SuQi. “Enhancing network capacity effects of edge-removal in small-world networks.” Scientia Sinica Informationis 2012, 42(2) 151-160 DOI: 10.1360/112011-421

Guo-Qing Zhang, Di Wang,Guo-Jie Li. “Enhancing the transmission efficiency by edge deletion in scale-free networks.” Physical Review E, 76, 017101 (2007). DOI: 10.1103/PhysRevE.76.017101

© 2011 PhysOrg.com

"Removing 'black sheep' could make Internet run more efficiently." February 28th, 2012. http://phys.org/news/2012-02-black-sheep-internet-efficiently.html