Removing 'black sheep' could make Internet run more efficiently

Feb 28, 2012 by Lisa Zyga report
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.”

Explore further: Using 'Big Data' approach to map relationships between human and animal diseases

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

Related Stories

Internet Growth Follows Moore's Law Too

Jan 14, 2009

(PhysOrg.com) -- Originally, Moore’s Law described the number of transistors that can fit on an integrated circuit, which doubles approximately every 18 months. Now, a team of researchers from China has ...

MIT researchers create new Urban Network Analysis toolbox

Sep 06, 2011

MIT researchers have created a new Urban Network Analysis (UNA) toolbox that enables urban designers and planners to describe the spatial patterns of cities using mathematical network analysis methods. Such tools can support ...

How quickly things spread

Feb 21, 2012

Understanding the spread of infectious diseases in populations is the key to controlling them. If we were facing a flu pandemic, how could we measure where the greatest spreading risk comes from? This information ...

How to control complex networks

May 12, 2011

At first glance, a diagram of the complex network of genes that regulate cellular metabolism might seem hopelessly complex, and efforts to control such a system futile.

Recommended for you

User comments : 16

Adjust slider to filter visible comments by rank

Display comments: newest first

infinite_energy
3 / 5 (6) Feb 28, 2012
Perhaps it is time to lay more optical fiber and upgrade routers.
jibbles
4.2 / 5 (5) Feb 28, 2012
"The Internet is a combination of many interconnected networks". i stand corrected then. i thought it was a series of tubes.
axemaster
4.7 / 5 (6) Feb 28, 2012
Wouldn't it make more sense to make routers choose a semi-random path? That way the main links wouldn't get overloaded so much due to being shortcuts.
Foolish1
2 / 5 (2) Feb 28, 2012
While useful this research does not apply to the Internet as stated in the summary. In their simulation "routers use a shortest path routing strategy". The Internet actually uses least cost which normally is not the same as shortest path.

Also problematic edges are already congestion aware. Metering lights are already built into the network.
Argiod
1.5 / 5 (4) Feb 28, 2012
I thought the phone company worked out all this for communications. Didn't the old Vax Unix computers take over the switching so that there would be no bottlenecks on the phone network? Why can't they do the same for the internet? It seems it would be a simple code to write, to ease traffic on busy hubs in 'rush hour' traffic, to go around by slightly longer paths. Maybe I'm expecting too much from our current state-of-the-art tech...?
Argiod
3 / 5 (6) Feb 28, 2012
Perhaps it is time to lay more optical fiber and upgrade routers.


Along those lines, wouldn't it be a simple software upgrade to the routers of the internet hubs to ease heavy trafficked hubs by rerouting traffic to quieter nodes? Or perhaps a rewrite of the IP protocols...
bottomlesssoul
3.5 / 5 (2) Feb 28, 2012
I actually expect human capacity to consume bandwidth is unlimited. Double it and we'll absorb it. That is, bandwidth congestion will always be a problem.

I think it's beautiful. Information will set you free; unless you get addicted to youtube monkey urination videos...
plasticpower
3.5 / 5 (2) Feb 29, 2012
I like the comment about picking nodes at random at times. I also think there should be a way for nodes to dynamically communicate their load levels to each other, which would allow the routers to continue using the same shortest path algorithm, but it would give different results based on congestion. This would, of course, require additional communication between nodes. Or not, if perhaps you can very slightly redesign the messaging protocol to include this information in regular messages that already go through these nodes.
Caz
2.5 / 5 (2) Feb 29, 2012
Internet capacity is not infinite. We may be able to solve congestion problems in the short term but ultimately everything has its limits. I'm with Bottomlesssoul, use it wisely.
Urgelt
2.5 / 5 (2) Feb 29, 2012
I'm not seeing a lot of value-added by this study.

First, they set up initial conditions which do not much resemble the way the internet is organized. Then they demonstrated a method, not of improving routing algorithms, but of forcing longer reroutes. Hardly mentioned is that what they're really doing is they're making a trade-off between network carrying capacity and latency. At the end of it all they announce the supremacy of carrying capacity as a networking goal, then hedge their bets by declaring that following that dictum too far might (duh) degrade network performance.

It's all rubbish.

Tell 'em to come back when they've got better routing algorithms. There's no need to delete connections if we're using what we have effectively.
antialias_physorg
5 / 5 (1) Feb 29, 2012
Wouldn't it make more sense to make routers choose a semi-random path?

Was thinking the same thing.
Give each edge of the graph (connection between two hubs) a weight which is periodically updated by the hubs sending back and forth the load they are under (including a hysteresis term).
Then have the hubs shunt the packages along the paths according to the weights (which correspond to a probability - with low load paths having a higher pobability of getting a packet).

A deterministic pathing (always sending along the path of lowest load) would not be good, because a hub reporting low load would be bombarded into oblivion the next instant with packets.
Foolish1
2 / 5 (1) Feb 29, 2012
I'm not seeing a lot of value-added by this study.

First, they set up initial conditions which do not much resemble the way the internet is organized. Then they demonstrated a method, not of improving routing algorithms, but of forcing longer reroutes.


By simulating simple networks you are sometimes able to detect emergent behavior and gain insights which *might* be leveraged to improve other systems. I believe if you ignore the marketing speak (All references to Internet:) the real item of interest is the result itself. In the real world not many people actually deal with heterogeneous networks or shortest path routing as you mentioned so the reasonable question to ask is any of this knowledge transferrable to real world networks with much more complex routing algorithms?
that_guy
2.3 / 5 (3) Feb 29, 2012
Seriously, did NO ONE understand this article?

Let me lay it out simply for you:

Think of a highway, where you have to stop at every town along the way. If you remove all the towns between the origin and the destination, you will get there more quickly.

The "in betweeness" value reflects how often a server is an unnecessary stop between two other servers, versus how often it is an important stop for traffic.

The extra stop at an unnecessary server is redundant and increases latency and transit time.

It would be like making Mississippi and alabama disappear. You could get from florida to louisiana much quicker, and you wouldn't really lose anything important in the process.
fiberhalo
1 / 5 (1) Feb 29, 2012
Many have attempted to build utilization awareness into routing protocols and many have failed. It is very difficult to get right. The main issue tends to be oscillations that occur because the very act of moving traffic changes the metrics used to route such traffic. What used to be congested is no longer congested when the new path gets used, but now the new path is congested.

In real networks, MPLS and RSVP are used such that when primary paths fill up, some of the LSPs get re-optimized to alternate (sometimes longer) paths. It takes many parallel LSPs to make this work smoothly but is the best way I know of to make the most of capacity in your network.
that_guy
2.3 / 5 (3) Feb 29, 2012
Many have attempted to build utilization awareness into routing protocols and many have failed. It is very difficult to get right. The main issue tends to be oscillations that occur because the very act of moving traffic changes the metrics used to route such traffic. What used to be congested is no longer congested when the new path gets used, but now the new path is congested.


The article clearly states that they are not intending to use new algorithms. They are only proposing to remove servers that serve primarily as extra stops in what would otherwise be a more direct path.
Grizzled
1.8 / 5 (5) Mar 04, 2012
That_guy: I'm afraid it's YOU who completely misunderstood the article so don't blame others for your own faults.

Contary to what you say, they do NOT propose to remove servers to get the more direct path. What they propose is adding MORE servers to the path to circumvent the few but heavily loaded ones on the most direct route.

Do us all a favor - don't blame others for your own misunderstandings.