Design and Evaluation of a High Speed Routing Lookup Architecture

• ZHANG Jun

  Department of Bioengineering and Robotics, Graduate School of Engineering, Tohoku University

• SHIM JeoungChill

  Department of Bioengineering and Robotics, Graduate School of Engineering, Tohoku University

• KURINO Hiroyuki

  Department of Bioengineering and Robotics, Graduate School of Engineering, Tohoku University

• KOYANAGI Mitsumasa

  Department of Bioengineering and Robotics, Graduate School of Engineering, Tohoku University

抄録

The IP routing lookup problem is equivalent to finding the longest prefix of a packet's destination address in a routing table [1]. It is a challenging problem to design a high performance IP routing lookup architecture, because of increasing traffic, higher link speed, frequent updates and increasing routing table size. At first, increasing traffic and higher link speed require that the IP routing can be executed at wire speed. Secondly, frequent routing table updates require that the insertion and deletion operations should be simple and low delay. At last, increasing routing table size hopes that less memory is used in order to reduce cost. Although many schemes to achieve fast lookup exist, less attention is paid on the latter two factors. This paper proposed a novel pipelined IP routing lookup architecture using selective binary search on hash table organized by prefix lengths. The evaluation results show that it can perform IP lookup operations at a maximum rate of one lookup per cycle. The hash operation ratio for one lookup can be reduced to about 1%, less than two hash operations are needed for one table update and only 512 kbytes SRAM is needed for a routing table with about 43000 prefixes. It proves to have higher performance than the existing schemes.

収録刊行物

• IEICE transactions on communications

  IEICE transactions on communications 87 (3), 406-412, 2004-03-01

  一般社団法人電子情報通信学会

キーワード

• IP routing
• selective binary search algorithm
• pipelined architecture
• cache

詳細情報

• CRID: 1570854177340943744
• NII論文ID: 110003222242
• NII書誌ID: AA10826261
• ISSN: 09168516
• 本文言語コード: en
• データソース種別:
  • CiNii Articles