標題: IP lookup by scalable multi-way search on prefix lengths
作者: Ting, PC
Lee, TH
資訊科學與工程研究所
Institute of Computer Science and Engineering
關鍵字: IP lookup;binary search oil prefix lengths;pre-computation;marker
公開日期: 2003
摘要: IP routing table lookup is an essential technology for supporting high-speed routers. To achieve high speed IP routing table lookup, in this paper, we propose an efficient and scalable algorithm, called multi-way search on prefix lengths. The multi-way search scheme is derived from binary search on prefix lengths which groups route prefixes of identical lengths into individual tables and applies hashing technique in these tables to find matching prefixes. However, the multi-way search scheme significantly improves the average look-lip performance of binary search scheme without any loss of its worst-case lookup performance. Further the proposed scheme is so simple that it basically does not increase the complexity in constructing the search tree and in memory requirement. Through experiments on real backbone routing tables, we found that the improvement can be more than 37% for all routing tables.
URI: http://hdl.handle.net/11536/18633
ISBN: 1-892512-45-9
期刊: PDPTA'03: PROCEEDINGS OF THE INTERNATIONAL CONFERENCE ON PARALLEL AND DISTRIBUTED PROCESSING TECHNIQUES AND APPLICATIONS, VOLS 1-4
起始頁: 430
結束頁: 436
Appears in Collections:Conferences Paper