To search, Click below search items. |
| All Published Papers Search Service |
|
|
|
Title |
Advanced Routing Algorithm for IP Lookup (IPv6) |
|
Author |
Pankaj Gupta, Uma Nagaraj, Nikhil Anthony, Deepak Jain, Pranav Gupta, Harsh Bhojwani |
| Citation |
Vol. 11 No. 4 pp. 144-150 |
|
Abstract |
Internet address lookup is a challenging problem because of increasing routing table sizes, increased traffic, higher speed links, and the migration to 128 bit IPv6 addresses. IP routing lookup requires computing the best matching prefix, for which standard solutions like hashing were believed to be inapplicable. The best existing solution we know of, BSD radix tries, scales badly as IP moves to 128 bit addresses. This paper presents a novel algorithm “Distributed memory organization” for lookup of 128 bit IPv6 addresses and “Mutating binary search” on hash tables organized by prefix lengths. Our scheme scales very well as address and routing table sizes increase: independent of the table size, it requires a worst case time of log2 (address bits) hash lookups. Thus only 5 hash lookups are needed for IPv4 and 7 for IPv6.We have also introduced Marker Storage algorithm for optimized storage. Using the proposed techniques a router can achieve a much higher packet forwarding rate and throughput. |
|
Keywords |
Best Matching Prefix, Longest Prefix Match, IP lookup, IPv6, Distributed Memory Organization, Mutating Binary search. |
|
URL |
