Network World's Tim Greene posted an article about a new algorithm, called Approximate Link State (XL), for use in link-state routing protocols. The algorithm was developed by researchers at the University of California at San Diego. The algorithm allows link-state protocols to determine when to not forward updates to neighbors, potentially reducing the overhead of the routing protocols. The ACM paper on the algorithm says that it can reduce overhead by an order of magnitude.
The key concept behind the algorithm is that it reduces the need to manually configure areas within OSPF or IS-IS. Areas are used to limit the distribution of link-state updates, reducing the total volume of updates that each individual router has to process to only those updates that occur within its area. Are areas that important? I've heard some senior routing protocol designers say something like:
EIGRP allows people who don't have a clue to build larger networks than OSPF, but to build a very large network you have to have a clue.
The reason for this statement is that summarization is used to limit the sizes of routing domains in order to have a large network remain stable. Areas are much like water-tight doors in ships -- they limit the scope of damage when bad things happen. Even with XL, I would want to use areas to aid in troubleshooting and to restrict the extent of the network that is impacted by any number of routing problems. With these other requirements driving the need to use areas, I don't see areas disappearing as a basic network design feature. I can see that XL may allow for larger areas, potentially simplifying the design of some networks.
Another thought that I had about XL was whether the increased memory usage in routers would be worth the savings in routing overhead. The researchers have not implemented XL within a real OSPF code base, so there is no way to judge where the tradeoff exists for memory and CPU vs routing protocol traffic overhead. Overall, it may actually save CPU time, at the cost of some additional memory. We'll have to see as these researchers continue their work. It would be nice to see a follow-up paper that reports how it works in the real world. In particular, I could see XL being a big benefit in military networks that have limited bandwidth, especially mobile networks.
-Terry