文献类型：期刊文献

中文题名：基于元组空间的位并行包分类算法

英文题名：Packet Classification Using Tuple Space-based Bit-Parallelism

作者：韩晓非[1];杨明福[1];王学光[1]

机构：[1]华东理工大学计算机科学与工程系,上海200237

年份：2003

卷号：39

期号：29

起止页码：188

中文期刊名：计算机工程与应用

外文期刊名：Computer Engineering and Applications

收录：CSTPCD;;北大核心:【北大核心2000】；CSCD:【CSCD2011_2012】；

语种：中文

中文关键词：数据包分类;路由查找;住并行;元组空间

外文关键词：packet classification,routing lookup,bit-parallelism,tuple space

摘要：随着网络的发展,路由器需要完成数据包过滤、QOS、流量计费等额外服务,这要求路由器能够以线速(wirespeed)完成对数据包的分类处理。位并行算法是一种快速的包分类算法,但由于空间占用量过大,它不能扩展到大规模规则库。该文从位并行算法入手,通过引入元组空间的概念提出了一种新的算法,在时间复杂度与空间复杂度上都较位并行算法有很大改进,并具有很好的扩展性。
With the development of the Internet,routers must support extra functions such as packet filtering,QOS and trafic billing.The input packets should be processed at wire speed to meet these demands.Bit-Parallelism is a fast scheme for packet classification,but it scales poorly as the filter databases grow in size.In this article,by taking the Bit-Parallelism scheme and adding the idea of tuple space,we produce a new algroithm called Tuple Space-based Bit-Parallelism(TSBP).The new algorithm reduces the complexities of both the time and storage and it can scale well with the growth of the filter databases in size.