文章基本信息

标题：Advanced Routing Algorithm for IP Lookup (IPv6)
本地全文：下载
作者：Pankaj Gupta ; Uma Nagaraj ; Nikhil Anthony 等
期刊名称：International Journal of Computer Science and Network Security
印刷版ISSN：1738-7906
出版年度：2011
卷号：11
期号：4
页码：144-150
出版社：International Journal of Computer Science and Network Security
摘要：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.
关键词：Best Matching Prefix; Longest Prefix Match; IP lookup; IPv6; Distributed Memory Organization; Mutating Binary search.