High Speed IP Lookup Algorithm with Scalability and Parallelism Based on ASIC Implementation

TAN Ming-feng; GONG Zheng-hu

您当前的位置：

首页 >

文章列表页 >

High Speed IP Lookup Algorithm with Scalability and Parallelism Based on ASIC Implementation

更新时间：2025-07-16

- High Speed IP Lookup Algorithm with Scalability and Parallelism Based on ASIC Implementation
- Acta Electronica Sinica Vol. 33, Issue 2, Pages: 209-213(2005)
- 作者机构：
  
  国防科技大学计算机学院,湖南,长沙,410073
- 作者简介：
- 基金信息：
- DOI：
  CLC： TP393
- Published：2005
- 稿件说明：
移动端阅览
TAN Ming-feng, GONG Zheng-hu. High Speed IP Lookup Algorithm with Scalability and Parallelism Based on ASIC Implementation[J]. Acta Electronica Sinica, 2005, 33(2): 209-213.
DOI：

TAN Ming-feng, GONG Zheng-hu. High Speed IP Lookup Algorithm with Scalability and Parallelism Based on ASIC Implementation[J]. Acta Electronica Sinica, 2005, 33(2): 209-213. DOI：

摘要

本文提出的IP路由查找算法基于ASIC实现

用多个Hash函数对不同长度的前缀进行映射并保存在不同的组相联存储器中

运用组相联存储器的特性很好地解决了Hash碰撞

并极大地减少了空间耗费.查找时并行查找所有存储器以进行最长前缀匹配

可在一次访存时间内完成查表

而路由更新平均只需数次访存.该算法在使用10ns的存储器件时已可满足OC-768接口的线速转发要求

而且具有良好的可扩展性和并行性

可满足更大容量的路由表和更高速度网络单元的线速转发要求.

Abstract

This paper proposes a high performance IP routing lookup algorithm based on ASIC implementation. It keeps prefixes of different length in different group associated CAMs

and uses different Hash functions to map the prefixes into the corresponding groups of the CAMs. By this means it reduces the Hash collisions and the memory usage. This scheme can finish the lookup within 1 memory access time and need only few memory accesses for each update in average. With 10ns memory

this scheme can fully match the link speed of OC-768. For its good scalability and parallelism

it can be extended to adapt larger forwarding tables and faster forwarding requirements.

关键词

Keywords

references

Views

1099

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Research on Scalability of Blockchain Based on Sharding: A Survey

Scalable Network Verification Technologies: State of the Art and Future

A New Scheduling Algorithm with O Control Messages Complexity for High-Speed Crossbars

Research and Design of a High-Performance Scalable Public-Key Cipher Coprocessor

Related Author

LIU Ting-ting

XU Jia

YE Fei

MA Peng-cheng

YANG Jing-lin

JIANG Ling-yun

HUANG Han-lin

XU Ke

Related Institution

School of Computer Science, Nanjing University of Posts and Telecommunications

Department of Computer Science and Technology， Tsinghua University

Key Laboratory of Data Engineering and Knowledge Engineering （Renmin University of China）

Institute for Network Science and Cyberspace， Tsinghua University

Beijing National Research Center for Information Science and Technology

⁰