An Efficient IP Address Lookup Scheme Using Balanced Binary Search with Minimal Entry and Optimal Prefix Vector
スポンサーリンク
概要
- 論文の詳細を見る
Although IP address lookup schemes using ternary content addressable memory (TCAM) can perform high speed packet forwarding, TCAM is much more expensive than ordinary memory in implementation cost. As a low-cost solution, binary search algorithms such as a binary trie or a binary search tree have been widely studied. This paper proposes an efficient IP address lookup scheme using balanced binary search with minimal entries and optimal prefix vectors. In the previous scheme with prefix vectors, there were numerous pairs of nearly identical entries with duplicated prefix vectors. In our scheme, these overlapping entries are combined, thereby minimizing entries and eliminating the unnecessary prefix vectors. As a result, the small balanced binary search tree can be constructed and used for a software-based address lookup in small-sized routers. The performance evaluation results show that the proposed scheme offers faster lookup speeds along with reduced memory requirements.
- （社）電子情報通信学会の論文
- 2011-11-01
著者
-
Kang Sungho
Dept. Of Electrical And Electronic Eng. Yonsei University
-
Kang Sungho
Dept. Of Electrical & Electronic Eng. Yonsei University
-
Park Hyuntae
Dept. Of Electrical And Electronic Eng. Yonsei University
-
Hong Hyejeong
Dept. Of Electrical And Electronic Eng. Yonsei University
-
Hong Hyejeong
Dept. Of Electrical And Electronic Eng. Yonsei Univ.
-
Park Hyuntae
Dept. Of Electrical And Electronic Eng. Yonsei Univ.
関連論文
- A Fast IP Address Lookup Algorithm Based on Search Space Reduction
- A Memory-Efficient Pattern Matching with Hardware-Based Bit-Split String Matchers for Deep Packet Inspection
- MTR-Fill : A Simulated Annealing-Based X-Filling Technique to Reduce Test Power Dissipation for Scan-Based Designs
- A Pattern Partitioning Algorithm for Memory-Efficient Parallel String Matching in Deep Packet Inspection
- Selective Scan Slice Grouping Technique for Efficient Test Data Compression
- A Selective Scan Chain Activation Technique for Minimizing Average and Peak Power Consumption
- Grouped Scan Slice Repetition Method for Reducing Test Data Volume and Test Application Time
- A New Built-in Self Test Scheme for Phase-Locked Loops Using Internal Digital Signals
- A Low-Cost BIST Based on Histogram Testing for Analog to Digital Converters
- A New Analog-to-Digital Converter BIST Considering a Transient Zone(Integrated Electroics)
- Efficient Test Generation Using Redundancy Identification
- A Hardware-Efficient Pattern Matching Architecture Using Process Element Tree for Deep Packet Inspection
- A Clustered RIN BIST Based on Signal Probabilities of Deterministic Test Sets(Dependable Computing)
- An Efficient IP Address Lookup Scheme Using Balanced Binary Search with Minimal Entry and Optimal Prefix Vector
- An accurate diagnosis of transition fault clusters based on single fault simulation
- A memory-efficient heterogeneous parallel pattern matching scheme in deep packet inspection