基于元组空间的位并行包分类算法

随着网络的发展,路由器需要完成数据包过滤、QOS、流量计费等额外服务,这要求路由器能够以线速(wirespeed)完成对数据包的分类处理。位并行算法是一种快速的包分类算法,但由于空间占用量过大,它不能扩展到大规模规则库。该文从位并行算法入手,通过引入元组空间的概念提出了一种新的算法,在时间复杂度与空间复杂度上都较位并行算法有很大改进,并具有很好的扩展性。

Packet Classification Using Tuple Space-based Bit-Parallelism

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.