首页 | 本学科首页   官方微博 | 高级检索  
     

基于短前缀长度分割的高速二维分组分类算法
引用本文:彭元喜,龚正虎,刘耀.基于短前缀长度分割的高速二维分组分类算法[J].计算机研究与发展,2002,39(9):1038-1042.
作者姓名:彭元喜  龚正虎  刘耀
作者单位:国防科学技术大学计算机学院,长沙,410073
基金项目:国家“八六三”高技术研究发展计划基金 ( 86 3-30 0 -0 1-0 3-99),国家自然科学基金重点项目基金 ( 90 10 40 0 1)资助
摘    要:分组分类是路由器根据IP分组的多个域,从分类器数据库中匹配每个输入分组,确定分组转发规则的技术,分类器为实现因特网新业务提供了统一的方式,这些新业务包括:防火墙,网络地址翻译等,二维分组分类问题在未来的因特网体系结构中占有十分重要的地位,目前,人们已经提出了几种分组分类算法,但没有一种是理想的,提出基于短前缀长度分割的二维分组分类算法,它使用短前缀长度分割(SPLS)技术对分类器集合进行分割,使得分割后的小分类器子集合可以使用巳有快速IP路由查找方法进行查找,实现时以多叉树作为基本数据结构,实验显示它具有存储需求小,平均查询时间快,更新时间快,适合于大的分类器等特点,是一种较好的二维分组分类算法。

关 键 词:短前缀长度分割  二维分组分类算法  四叉树  因特网  IP地址

HIGH-SPEED ALGORITHMS OF 2-DEMENSION PACKET CLASSIFICATION BASED ON SHORTER PREFIX LENGTH SPLITTING
PENG Yuan-Xi,GONG Zheng-Hu,and LIU Yao.HIGH-SPEED ALGORITHMS OF 2-DEMENSION PACKET CLASSIFICATION BASED ON SHORTER PREFIX LENGTH SPLITTING[J].Journal of Computer Research and Development,2002,39(9):1038-1042.
Authors:PENG Yuan-Xi  GONG Zheng-Hu  and LIU Yao
Abstract:Packet classification is a technique to match each incoming packet at a router against a database of classifier and specify forwarding rules for the packets. Classifiers are a powerful and uniform way to implement new network services such as firewalls, network address translation (NAT). Several algorithms of packet classification have been proposed recently, but none is ideal. In this paper an algorithm of 2-demension packet classification based on the shorter prefix length splitting (SPLS) is proposed. The SPLS is realized by splitting a larger database of classifier into many smaller databases of classifier according to the shorter prefix length between the IP source address and IP destination address. After splitting it, the IP routing lookup algorithm can be used to the smaller database of classifier. Multi-bit tree (or n-ary tree) is the basic data structure for SPLS. The performance when implementing SPLS in quadtree is examined. The algorithm has characteristics of fast average search time, fast update time, small memory space and suiting for large classifiers, and is a better algorithm for Internet routers.
Keywords:shorter prefix length splitting (SPLS)  quadtree  packet classification  layer 4 switching
本文献已被 CNKI 维普 万方数据 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号