Lee Gang U , An Jong Seog

The KIPS Transactions:PartA, Vol. 11, No. 2, pp. 129-142, Apr. 2004
10.3745/KIPSTA.2004.11.2.129,   PDF Download:

Abstract

As the Internet gets faster,the demand for high-speed routers that are capable of forwarding more than giga bits of data per second keeps increasing. In the previous research,Bitmap Trie algorithm was developed to rapidly execute LPM(longest prefix matching) process which is well known as the severe performance bottleneck. In this paper,we introduce a novel algorithm that drastically enhanced the performance of Bitmap Trie algorithm by applying three techniques. First,a new table called the Count Table was devised. Owing to this table,we successfully eliminated shift operations that was the main cause of performance degradation in Bitmap Trie algorithm. Second,memory utilization was improved by removing redundant forwarding information from the Transfer Table. Lastly,the range of prefix lookup was diversified to optimize data accesses. On the other hand,the processing delays were classified into three categories according to their causes. They were,then,measured through the execution-driven simulation that provides the higher quality of the results than any other simulation techniques. We tried to assure the reliability of the experimental results by comparing with those that collected from the real system. Finally the Enhanced Bitmap Trie algorithm reduced 82% of time spent in previous algorithm.

Statistics
Cite this article