Parallel Routing Lookup System Based on Non-Overlapping Prefix Sets

LIANG Zhi-yong; XU Ke; WU Jian-ping; CHAI Yun-peng

您当前的位置：

首页 >

文章列表页 >

Parallel Routing Lookup System Based on Non-Overlapping Prefix Sets

更新时间：2025-07-16

- Parallel Routing Lookup System Based on Non-Overlapping Prefix Sets
- Acta Electronica Sinica Vol. 32, Issue 8, Pages: 1277-1281(2004)
- 作者机构：
  
  清华大学计算机科学与技术系,北京,100084
- 作者简介：
- 基金信息：
- DOI：
  CLC： TP393
- Published：2004
- 稿件说明：
移动端阅览
LIANG Zhi-yong, XU Ke, WU Jian-ping, et al. Parallel Routing Lookup System Based on Non-Overlapping Prefix Sets[J]. Acta Electronica Sinica, 2004, 32(8): 1277-1281.
DOI：

LIANG Zhi-yong, XU Ke, WU Jian-ping, et al. Parallel Routing Lookup System Based on Non-Overlapping Prefix Sets[J]. Acta Electronica Sinica, 2004, 32(8): 1277-1281. DOI：

摘要

快速的路由查找机制是高性能路由器设计的关键.最长匹配查找是路由查找的难点所在.本文提出一个并行路由查找系统.它使用一种路由表划分方法

可将路由表中的前缀划分为若干个集合

集合内前缀没有重叠.从而把路由表前缀的最长匹配查找转化为若干个集合内前缀的唯一匹配查找.基于这种方法

本文还提出一个通用的并行路由查找框架

框架适用于大多数路由查找算法.并行查找框架可简化查找算法的设计

提高查找算法的速度.使用二分查找算法

并行查找系统可以达到log

(2N/B)的查找复杂度 (

为路由表前缀数目

B为大于4的整数).同时

并行查找系统对IPv6也具有很好的扩展性.

Abstract

Fast routing lookups are crucial for the forwarding performance of IP routers.Longest prefix match makes routing lookups difficult.This paper proposes a parallel routing lookup system that applies a method to partition a routing table.The method can divide all prefixes in a routing table into several prefix sets where prefixes don't overlap.Based on the method

this paper also presents a common parallel lookup framework that reduces "longest prefix matching" in all the prefixes to "only prefix matching" in several prefix sets.The framework can effectively simplify the design of lookup algorithms and improve lookup performance.The framework is suitable for most lookup algorithms.For simple binary search algorithm

our system can reach log

(2N/B) lookup complexity (where N is prefix number in a rou

ting table and B is an integer bigger than 4).Also

the system can be scaled to IPv6 easily.

关键词

Keywords

references

Views

880

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

TSB:A Multi-Stage Algorithm for IPv6 Routing Table Lookup

A New Regional Code Label Switching and Network Performance Analysis

Related Author

LI Zhen-qiang

ZHENG Dong-qu

MA Yan

QIU Zhi-liang

SHI Yan

LIU Huan-feng

CHEN Peng

LIU Zeng-ji

Related Institution

School of Computer Science and Technology,Beijing University of Posts and Telecommunications

Network Information Center,Beijing University of Posts and Telecommunications

School of Computer Science and TechnologyBeijing University of Posts and TelecommunicationsBeijing 100876China

Network Information CenterBeijing University of Posts and TelecommunicationsBeijing 100876China

National Key Lab. of Integrated Service Networks, Xidian Univ.

⁰