Small Forwarding Tables for Fast Routing Lookups
No Thumbnail Available
Date
2011-08
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Addis Ababa University
Abstract
IP address lookup is an important design issue for the high performance Internet routers. Due to
the rapid growth of traffic in the Internet, backbone links of several gigabits per second are
commonly deployed. To handle gigabit-per-second traffic rates, the backbone routers must be
able to forward millions of packets per second on each of their ports. Fast IP address lookup in
the routers, which uses the packet’s destination address to determine for each packet the next
hop, is therefore crucial to achieve the packet forwarding rates required. In the last few years,
various algorithms for high-performance IP address lookup have been proposed. The algorithm
that is under scrutiny in this project is based on matching longest IP prefix. This algorithm
incorporates a technique of complete trie in building prefix tries. This mechanism enables to
build small forwarding tables.
In this project we will present a forwarding table data structure designed for quick routing
lookups. The Forwarding tables are small enough to fit in the cache of a conventional general
purpose processor. This means that it is feasible to do a full routing lookup for each IP packet at
gigabit speeds without using special hardware.
Keywords: Address lookup, Complete Trie, Data Structure
Description
Keywords
Address Lookup, Complete Trie, Data Structure