New Algorithm Significantly Boosts Routing Efficiency of Networks
August 18, 2008 By Paul K. Mueller
The XL algorithm developed by computer scientists at UC San Diego significantly outperforms standard link-state and distance-vector algorithms, speeding routing in computer and communications networks.
(PhysOrg.com) -- A time-and-money-saving question shared by commuters in their cars and networks sharing ever-changing Internet resources is: "What's the best way to get from here to there?"
A new algorithm developed by computer scientists at the University of California, San Diego helps answer that question, at least for computer networks, and it promises to significantly boost the efficiency of network routing.
Called XL, for approximate link state, the algorithm increases network routing efficiency by suppressing updates from parts of the system – updates which force connected networks to continuously re-calculate the paths they use in the great matrix of the Internet.
"Routing in a static network is trivial," say the authors in their paper, which will be presented at this week's ACM SIGCOMM conference. "But most real networks are dynamic – network links go up and down – and thus some nodes need to recalculate their routes in response."
The traditional approach, said Stefan Savage, professor of computer science at UC San Diego, "is to tell everyone; flood the topology change throughout the network and have each node re-compute its table of best routes – but that requirement to universally communicate, and to act on each change, is a big problem."
What the team did with their new routing algorithm, according to Savage's student Kirill Levchenko, was to reduce the "communication overhead" of route computation – by an order of magnitude.
"Being able to adapt to hardware failures is one of the fundamental characteristics of the Internet," Levchenko said. "Our routing algorithm reduces the overhead of route re-computation after a network change, making it possible to support larger networks. The benefits are especially significant when networks are made up of low-power devices of slow links."
The real technical innovation of their work, said another of the authors, Geoffrey M. Voelker, "is in how information about changes in the network is propagated. The XL routing algorithm propagates only some updates, reducing the number of updates sent through the network."
They meet the "central challenge" of determining which updates are important and which can be suppressed by using three rules for update propagation, said team member Ramamohan Paturi. "The rules ensure that selected routes are nearly as good as if complete information about the network were available," he said, "but at a fraction of the overhead required for maintaining such a state of perfect knowledge."
The computer scientists also believe that there are "significant opportunities" to improve the efficiency of link-state routing even further. They look forward to discovering an algorithm that improves on their Approximate Link work with similar boosts in efficiency.
Source: University of California - San Diego
-
Field experiment on a robust hierarchical metropolitan quantum cryptography network
Oct 16, 2009 |
5 / 5 (1) |
0
-
Self-managing internet applications flex their muscles
Oct 02, 2009 |
4 / 5 (1) |
0
-
Digital Dandelions
Aug 31, 2007 |
4.1 / 5 (15) |
0
-
Nature offers guidance on organising dynamic networks
May 26, 2006 |
4.7 / 5 (10) |
0
-
Bell Labs Researchers Push The Limits of Mobile Computing
Sep 29, 2004 |
not rated yet |
0
-
Engineers build first sub-10-nm carbon nanotube transistor
Feb 01, 2012 |
4.9 / 5 (32) |
30
-
Something old, something new: Evolution and the structural divergence of duplicate genes
Jan 31, 2012 |
4.6 / 5 (7) |
1
-
The hidden nanoworld of ice crystals: Revealing the dynamic behavior of quasi-liquid layers
Jan 30, 2012 |
5 / 5 (4) |
1
-
Stock market network reveals investor clustering
Jan 27, 2012 |
3.9 / 5 (23) |
8
-
Of microchemistry and molecules: Electronic microfluidic device synthesizes biocompatible probes
Jan 26, 2012 |
5 / 5 (2) |
0
-
Synergistic relations between computer science and technology.
Feb 06, 2012
-
how do iphone gloves work?
Feb 05, 2012
-
iPhone battery over time
Jan 30, 2012
-
Best alternate Tablet to an iPad for writing math or physics equations?
Jan 26, 2012
-
Sending SMS to a website
Jan 20, 2012
-
Need help with my technical fest!
Jan 19, 2012
- More from Physics Forums - Computing & Technology
More news stories
Google might launch Drive for cloud storage soon
(PhysOrg.com) -- Google's next big move, according to the Wall Street Journal, is a cloud storage service called Drive. Hardly first to the plate, Google is simply catching up to introducing its cloud reposi ...
Iran blocks email, restricts net access: reports
Iran has further restricted access to the Internet and blocked popular email services for the past few days, in a move a top lawmaker said could "cost the regime dearly," media reports said on Sunday.
1 hour ago |
5 / 5 (1) |
2
Love a click away in Indonesia's Twitter Republic
He was a geeky kid from Yogyakarta, she a glamorous city girl in Jakarta. In a country with one of the world's most vibrant social networking scenes they fell in love on Twitter.
9 hours ago |
4 / 5 (1) |
0
Walney offshore wind farm is world's biggest (for now)
(PhysOrg.com) -- The Walney wind farm on the Irish Sea--characterized by high tides, waves and windy weather--officially opened this week. The farm is treated in the press as a very big deal as the Walney ...
Navy to begin tests on electromagnetic railgun prototype launcher
The Office of Naval Research (ONR)'s Electromagnetic (EM) Railgun program will take an important step forward in the coming weeks when the first industry railgun prototype launcher is tested at a facility ...
Feb 06, 2012 |
4.7 / 5 (16) |
93
|
Scientists discover molecular secrets of 2,000-year-old Chinese herbal remedy
For roughly two thousand years, Chinese herbalists have treated Malaria using a root extract, commonly known as Chang Shan, from a type of hydrangea that grows in Tibet and Nepal. More recent studies suggest that halofuginone, ...
New method to examine batteries -- MRI from the inside
There is an ever-increasing need for advanced batteries for portable electronics, such as phones, cameras, and music players, but also to power electric vehicles and to facilitate the distribution and storage of energy derived ...
Lab study raises questions over nano-particle impact
Tests involving chickens have raised questions about the impact on health from engineered nano-particles, the ultra-fine grains commonly used in drugs and processed foods, scientists said on Sunday.
A mitosis mystery solved: How chromosomes align perfectly in a dividing cell
Although the process of mitotic cell division has been studied intensely for more than 50 years, Whitehead Institute researchers have only now solved the mystery of how cells correctly align their chromosomes during symmetric ...
Starve a virus, feed a cure? Findings show how some cells protect themselves against HIV
A protein that protects some of our immune cells from the most common and virulent form of HIV works by starving the virus of the molecular building blocks that it needs to replicate, according to research published online ...
Researchers find extensive RNA editing in human transcriptome
In a new study published online in Nature Biotechnology, researchers from BGI, the world's largest genomics organization, reported the evidence of extensive RNA editing in a human cell line by analysis of RNA-seq data, demons ...
Sep 08, 2008
Rank: not rated yet
http://www.freeve..._updated
http://bjacob.liv...600.html