期刊名称：Oriental Journal of Computer Science and Technology
印刷版ISSN：0974-6471
出版年度：2011
卷号：4
期号：1
页码：51-58
语种：English
出版社：Oriental Scientific Publishing Company
摘要：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 “Asymmetric Linear search” on hash tables organized by prefix lengths. Our scheme scales very well when traffic on routers is unevenly distributed and in genera it requires only 3-4 lookups, independent of the address bits and table size. Thus it scales very well for IPv4 and IPv6 under such network conditions. Using the proposed techniques a router can achieve a much higher packet forwarding rate and throughput.
关键词：Best Matching Prefix ; Longest Prefix Match ; IP lookup ; IPv6 ; Distributed Memory Organization ; Mutating Binary search
Loading...
