公开(公告)号：US07227842B1

公开(公告)日：2007-06-05

申请号：US10133689

申请日：2002-04-23

申请人： Hongbin Ji ,  Michael Carchia

发明人： Hongbin Ji ,  Michael Carchia

IPC分类号： H04L12/28 ,  H04L12/56

CPC分类号： H04L47/10 ,  H04L45/00 ,  H04L45/54 ,  H04L47/2441

摘要： A novel solution for fast packet classification includes a novel data structure to store classifier rules which enables fast packet classification, which structure employs bitmaps for each field of the incoming packet for which classification is desired. A fast packet classification algorithm using the novel data structure allows the matching rule with the highest priority to be quickly obtained. A novel rule update algorithm allows new classifier rules to be added into the data structure incrementally. In one practical implementation of a classification engine employing the structures and algorithms of the present invention, a configurable processor with customized instructions is used to accelerate packet classification.

摘要翻译： 用于快速分组分类的新颖解决方案包括一种新颖的数据结构，用于存储能够进行快速分组分类的分类器规则，该结构对于期望分类的输入分组的每个字段采用位图。 使用新颖数据结构的快速分组分类算法可以快速获得具有最高优先级的匹配规则。 新的规则更新算法允许将新的分类器规则逐渐添加到数据结构中。 在采用本发明的结构和算法的分类引擎的一个实际实现中，使用具有定制指令的可配置处理器来加速分组分类。

公开(公告)号：US07274697B2

公开(公告)日：2007-09-25

申请号：US10032379

申请日：2001-12-21

申请人： Hongbin Ji ,  Michael Carchia

发明人： Hongbin Ji ,  Michael Carchia

IPC分类号： G06F12/00 ,  H04L12/28

CPC分类号： G06F17/30955 ,  H04L45/7457 ,  H04L69/22

摘要： An advanced data structure allows lookup based upon the most significant 16 bits and the following variable number of K bits of the IP destination address. This 16/K scheme requires less than 2 MB memory to store the whole routing tables of present day backbone routers. A 16/Kc version utilizes bitmaps to compress the table to less than 0.5 MB. For the 16/K data structure each route lookup requires at most 2 memory accesses while the 16/Kc requires at most 3 memory accesses. By configuring the processor properly and developing a few customized instructions to accelerate route lookup, one can achieve 85 million lookups per second (MLPS) in the typical case with the processor running at 200 MHz. Further, the lookup method can be implemented using pipelining techniques to perform three lookups for three incoming packets simultaneously. Using such techniques, 100 MLPS performance can be achieved.

摘要翻译： 高级数据结构允许基于最高有效16位和IP目的地地址的以下可变数量的K位进行查找。 这种16 / K方案需要少于2MB的存储器来存储当前骨干路由器的整个路由表。 16 / Kc版本利用位图将表压缩到小于0.5 MB。 对于16 / K数据结构，每个路由查找最多需要2个存储器访问，而16 / Kc需要最多3个存储器访问。 通过正确配置处理器并开发一些自定义指令来加速路由查找，在处理器运行在200 MHz的典型情况下，可以实现每秒8500万次查找（MLPS）。 此外，可以使用流水线技术来实现查找方法，以同时对三个输入分组执行三次查找。 使用这样的技术，可以实现100 MLPS性能。