New algorithm boosts network routing efficiency

A newly-developed algorithm for computer network routing could significantly boost the efficiency of networks that share ever-changing Internet resources.

Called the Approximate Link State algorithm, or XL for short, the algorithm increases network routing efficiency by reducing the communications that take place within a network.

The traditional approach to network routing is to constantly update each part of the network about any changes, and have each node re-compute its best route using the new information.

Instead of broadcasting constant updates, the XL algorithm propagates only the updates that it deems significant. According to its developers, the algorithm reduces 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,” said Kirill Levchenko, a computer scientist who worked on the project at the University of California, San Diego.

“Our routing algorithm reduces the overhead of route re-computation after a network change, making it possible to support larger networks,” he explained.

“The benefits are especially significant when networks are made up of low-power devices of slow links.”

The algorithm is driven by three rules for update propagation that have been designed to ensure that the selected routes are nearly as good as if complete information about the network were available.

Researchers believe that there are ‘significant opportunities’ to improve the effiency of link-state routing even further.