STONY BROOK, N.Y. — A software algorithm for Internet Protocol (IP) routing developed at the State University of New York (SUNY) at Stony Brook is said to make routing table lookups five times faster than proprietary hardware routers and two orders of magnitude faster than software-based routers. The team that developed the algorithm is considering plans to make it commercially available.

The team of one professor and two doctoral candidates said their IP routing table algorithm performs up to 87.87 million lookups per second on a machine based on a 500-MHz Alpha processor. That's a 5X speedup over existing ASIC-based proprietary routers and up to 100 times faster than existing software-only NT- based low-cost routers, the researchers said.

The finding is notable because the routing table lookup operation performed by the algorithm is the most time-consuming part of IP routing. The algorithm also eliminates the need to use a special ASIC, and instead does the lookup in the CPU's cache memory.

Router vendors could use the technology to build high-performance IP routers for backbone carriers like AT&T and MCI, where the target link bit rate is 100 to 1,000 Gbits per second, and the packet rate is 10 to 100 million packets per second. The technology can also be used with low-cost NT-based routers to improve their performance, according to Tzi-Cker Chiueh, an assistant professor of computer science at Stony Brook's Experimental Computer Systems Laboratory.

Chiueh and two Stony Brook doctoral candidates, Prashant Pradhan and Anindya Neogi, used off-the-shelf Intel hardware and Gbit/second system-area-network technology from Myrinet to build a high-performance, real-time IP router that they called Suez.

Simulating the performance effects of the CPU memory hierarchy against a packet trace collected from a major network router, the team showed that the overall performance can reach 87.87 million lookups per second using the Alpha processorwith a 16-kbyte L1 cache and a 1-Mbyte L2 cache, according to Chiueh.

Rather than routing on a packet-by-packet basis, the Suez router works on a flow-by-flow basis using self-routing.

The algorithm exploits the notion of "locality." When a router sees an incoming stream of packets, it notes which packets have similar destination addresses and reuses the routing table lookup and thus avoids searching for the same addresses over and over again.

Chiueh and his students currently implement the algorithm on a 300-MHz Pentium-II as well as on a 400-MHz Alpha machine. The initial Suez prototype will be an eight-node unit using 300-MHz Pentium II processors interconnected by a Myrinet switch, with sixteen 100-Mbit/s Fast Ethernet ports. The ultimate aggregate performance goal of the Suez prototype is 20 million packets/s and 1 million real-time connections.

The Suez prototype is expected to be operational around September. Once that happens, Chiueh said the group plans to pursue the possible commercialization of its algorithm with high-end router vendors and with vendors of low-end NT-based routers.

Chiueh plans to submit a paper on the groups findings to a journal of the Institute of Electrical and Electronics Engineers, and to the Gigabit Ethernet Conference next January.