Yehuda Afek, Anat Bremler-Barr, and
Sariel Har-Peled
We suggest a new simple forwarding technique to speed-up IP
destination address lookup. The technique is a natural extension of
IP, requires 5 bits in the IP header (IPv4, 7 in IPv6) and performs IP
lookup nearly as fast as IP/Tag-switching but with a smaller memory
requirement and a much simpler protocol. The basic idea is that each
router adds a "clue" to each packet, telling its downstream router
where it ended the IP lookup. Since the forwarding tables of
neighboring routers are similar, the clue either directly determines
the best prefix match for the downstream router, or provides the
downstream router with a good point to start its IP lookup. The new
scheme thus prevents repeated computations and distributes the lookup
process across the routers along the packet path. Each router starts
the lookup computation at the point its up-stream neighbor has
finished. Furthermore, the new scheme is easily assimilated into
heterogeneous IP networks, does not require routers coordination, and
requires no setup time. Even a flow of one packet enjoys the benefits
of the scheme without any additional overhead. The speedup we achieve
is about 10 times faster than current standard techniques. In a sense
this paper shows that the current routers employed in the Internet are
clue-less; Namely, it is possible to speedup the IP-lookup by an order
of magnitude without any major changes to the existing protocols.
@article{abh-rwc-01,
author = "Y.~Afek and A.~{Bremler-Barr} and S.~{Har-Peled}",
journal = "IEEE\slash ACM Transactions on Networking",
title = "Routing with a Clue",
pages = "693--705",
year = "2001",
month = dec,
volume = 9,
number = 6
}
SIGCOMM page
Last updated: Sun Sep 9 12:25:30 CDT 2001