Skip navigation

Please use this identifier to cite or link to this item:
Title: Small Forwarding Tables for Fast Routing Lookups
???metadata.dc.contributor.*???: Getachew Hailu (PhD)
Musa, Hayato
Keywords: Address lookup;Complete Trie;Data Structure
Issue Date: Jul-2011
Publisher: AAU
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.
Appears in Collections:Thesis - Computer Engineering

Files in This Item:
File Description SizeFormat 
Musa Hayato.pdf769.35 kBAdobe PDFView/Open
Show full item record

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.