作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2007, Vol. 33 ›› Issue (13): 127-129,. doi: 10.3969/j.issn.1000-3428.2007.13.043

• 网络与通信 • 上一篇    下一篇

基于前驱查找的快速IP路由查找和更新方案

陆笑天,李 曦,周学海,纪金松   

  1. (中国科学技术大学计算机科学技术系,合肥 230027)
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2007-07-05 发布日期:2007-07-05

Fast IP Route Lookup and Update Design Based on Predecessor Lookup

LU Xiaotian, LI Xi, ZHOU Xuehai, JI Jinsong   

  1. (Computer Science Department, University of Science and Technology of China, Hefei 230027)
  • Received:1900-01-01 Revised:1900-01-01 Online:2007-07-05 Published:2007-07-05

摘要: 路由器的转发速率通常受限于选择路由的速度,因此路由查找和更新的方法在路由器设计中至关重要。文章提出了一种可硬件实现的快速IP路由查找和更新方法,将IP前缀匹配等价为地址范围搜索,采用B-树结构存储路由表。这种方案对存储要求较低,仅由小容量的片上SRAM和片外DRAM构成。实验表明,该方案在简单硬件支持下就能够达到OC-48的转发要求。

关键词: IP路由查找, IP路由更新, B-树, 地址范围, 前驱查找

Abstract: The router’s forwarding rate is usually limited by the rate of route lookup. Thus, the method of route lookup and update are both important for router design. A method for implementing fast route lookup and update in hardware is described, which translates address range finding into prefix matching and uses B-tree for storing routing table. The method only uses a small on-chip SRAM and an off-chip DRAM. Tests show that the method can achieve the forwarding rate of OC-48.

Key words: IP route lookup, IP route update, B-tree, address range, predecessor lookup

中图分类号: