摘要： 路由器中将分组分类成"流"的过程称为分组分类,属于同一流中的所有分组遵循相同的预定规则且路由器对其进行相似的处理。非 "尽力而为"的服务需要对分组进行分类，例如：防火墙，QoS，区分服务等。该文描述3种不同的分类方法并比较分析各种分类（Packet Classification）算法的查找时间复杂度、存储开销。

关键词: 组分类, Grid-of-tries, 元组空间, TCAMs

Abstract: The process of categorizing packets into "flows" in an Internet router is called packet classification. All packets belonging to the same flow obey a pre-defined rule and are processed in a similar manner by the router. Packet classification is needed for non "best-effort" services, such as firewalls, quality of service, DiffSev etc. this paper describes three different algorithms that are representative of different category, and compares their time complexity ,storage complexity and scalable.

中图分类号: 

• TN915.05