ACM TechNews

UC San Diego Researchers' New Algorithm Significantly Boosts Routing Efficiency of Networks

University of California, San Diego (08/18/08) Mueller, Paul K.

University of California, San Diego computer scientists have developed XL, a new algorithm for helping computer networks find the most efficient way of sending data. The XL algorithm increases network routing efficiency by suppressing updates from parts of the system, which previously forced connected networks to continuously recalculate the paths used to send data. "Routing in a static network is trivial," say the authors of a paper on the algorithm, which will be presented at ACM SIGCOMM. "But most real networks are dynamic--network links go up and down--and thus some nodes need to recalculate their routes in response." The algorithm reduces the overhead of route re-computation after a network change, allowing for the support of larger networks. The major innovation in the new algorithm is that it propagates only some network updates. The algorithm determines which updates are important and which can be suppressed by establishing three rules for update propagation. "The rules ensure that selected routes are nearly as good as if complete information about the network were available, but at a fraction of the overhead required for maintaining such a state of perfect knowledge," says team member Ramamohan Paturi. The researchers believe that the efficiency of link-state routing can be further improved.

http://ucsdnews.ucsd.edu/newsrel/science/08-08Networks.asp

---

© Copyright 2008 Information, Inc. This service may be reproduced for internal distribution.