URL: http://www.acm.org/sigcomm/sigcomm99/papers/session6-1.pdf
http://citeseer.ist.psu.edu/afek99routing.html Entry Date: 2002-10-29 Abstract: 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. Datasets: IPMA snaphots of MAE-East (date unknown), MAE-West (date unknown), Paix (date unknown) , Format: RSD

Snapshots of AT&T-1, AT&T-2, ISP-B-1 and ISP-B-2 (dates unknown), Format: "sh ip route" Results: We have presented distributed IP lookup scheme which considerably speeds up IP lookup with little overhead. The scheme is a natural extension of IP routing, and works at least as efficient as MPLS/TAG-switching.

Distributed IP lookup can support and be employed by other current and future IP services such as: IP-multicasting, and IP packet filtering [14, 29]. For example, when a packet header is classified by several filters (in QoS, or firewall applications), the clue being added to the packet would be the filter by which the packet is classified at the last router. The receiving router would start its classification process at the restricted domain of the clue-filter.

Notice, however that the clue idea is more effective and natural in the routing table case. The effectiveness of the clue idea is due to the fact that routing tables in adjacent routers are very similar. In the case of filters (in firewalls, QoS devices and alike), which are policy based - filters in adjacent devices (e.g., firewalls, routers) are similar only in some special cases (e.g., nodes in a multicasting tree or devices along an RSVP path). References: Entry TODO: Paraphrase results.