Research News, May/June 1998

Previous News Next News

Return to Research News Index

Issue of May 1998.

---



[29/05/98] The Princeton Meeting on Analysis of Algorithms.
Sorry that Administration has swallowed up a fair amount of my time since January. At least, the AofA Booklet of the Princeton Meeting on Analysis of Algorithms is ready. The dates are July 20-24, 1998, in Princeton New Jersey, as most of you should know. In this page, you'll find informations about

What is it about?, First announcement, List of prospective participants, Hotels, Air Travel, Limousine service, Visas, for reimbursed participants. Useful links, Where in town?, Main organizer, Mail to us!.
and a few other useful tips as time goes..
DIMACS also has the officialWorkshop Announcement Page with the registration form.

---

[05/06/98] Theory and Practice: Routers, address lookup in networks, and tries.
Currently, in the Internet, communication is achieved by packets that each try to find their way, hoping for the best as regards global quality of service. In the community of people involved in networking, friends tell me, there is a fairly hot debate between the supporters of distributed anarchy, with IP [Internet Protocol] and its new version IPv6, and the proposers of a meticulously planned approach, with ATM [Asynchronous Transfer Mode], that is based on order and careful but costly reservation of resources.

One of the objections often raised against the IPv6 approach is the difficulty for routers to maintain large lists of addresses whose length goes from the current 32 bits to the new 128 bits, with sizes perhaps of the order of several hundred thousand entries, and with rather high dynamics. All this while providing very fast access in a fraction of a microseconds. In a nutshell, for each packet received, the router should be able to provide almost instantly the place to which it should be sent next. One thus has to maintain a very large dictionary data structure with extremely fast response time.

It is interesting that answers to this problem have been provided by people in or originating from the "design and analysis of algorithms" community.

• Mikael Degermark, Andrej Brodnik, Svante Carlsson and Stephen Pink have proposed a solution in their paper of SIGCOMM'97 that is entitled Small Forwarding Tables for Fast Routing Lookups. The data structure is largely a multilevel digital trie that is reminiscent of the Patricia tree optimization.
• Stefan Nilsson and Gunnar Karlsson have also demonstrated the usefulness of trie structures with combined path and level compression. This is described in their paper Fast address look-up for Internet routers and these authors even provide complete code!
It is fascinating to see some of the data structures that we teach, finely tuned as well as thoroughly and intelligently optimized to fit a real-life application. Each paper gives all details of its implementation. Surely, some interesting questions must remain regarding analysis and/or optimization.

The impact of this research is not to be underestimated. My colleagues that move in networking circles do confirm their importance. This is well summarized by the introduction of one of the papers under review:

``For some time, the networking community has assumed that it is impossible to do full IP routing lookups in software running on general purpose microprocessors fast enough to support routing at gigabit speeds. In fact, some [even believed] that IP routing lookups cannot be done quickly at low cost in hardware...''
Thus fast routing in software now becomes a reality. Seldom do we have a chance get access to the end-to-end solution of a problem like this one. Also, it is fashionable nowadays in many technocratic circles to claim that research makes sense only if it is directly subordinate to an application and that almost anything can be invented from scratch when the need arises. The works discussed here are anchored in a solid long-term tradition of algorithmic research and they provide, I think, valuable counterexamples.