利索-全球专利检索

  1. 登录
  2. 注册

搜索结果

89 条记录 (耗时 0.022 秒)

    Method and system for performing range rule testing in a ternary content addressable memory
    1.
    发明授权
    Method and system for performing range rule testing in a ternary content addressable memory 失效
    在三元内容可寻址存储器中执行范围规则测试的方法和系统

    公开(公告)号：US06886073B2

    公开(公告)日：2005-04-26

    申请号：US10173994

    申请日：2002-06-18

    申请人： Gordon Taylor Davis ,  Clark Debs Jeffries ,  Jan Van Lunteren

    发明人： Gordon Taylor Davis ,  Clark Debs Jeffries ,  Jan Van Lunteren

    IPC分类号： G06F12/00 ,  G06F17/30 ,  H04L29/06

    CPC分类号： H04L69/22 ,  H04L69/12

    摘要： A method and system for storing and searching for prefixes for rules, such as filter rules, in a computer system is disclosed. The method and system include providing a ternary content addressable memory (TCAM). The filter rules use range(s) of values in at least one dimension and correspond to prefix(es). The range(s) are described by prefix(es). Some filter rules may intersect. The method and system include providing priorities for the filter rules. The priorities include at least one different priority for the filter rules that intersect. The method and system also include storing the prefixes in the TCAM in block(s) in an order based upon the priorities of the filter rules. In another aspect, the method and system include searching the TCAM for a longest prefix match for a key and searching an additional storage for an almost exact match for the key in parallel with the TCAM. In this aspect, the method and system include returning the longest prefix match having a lowest or a highest location if the longest prefix match is found in the TCAM and the almost exact match is not found in the additional storage.

    摘要翻译： 公开了一种用于在计算机系统中存储和搜索诸如过滤规则的规则的前缀的方法和系统。 该方法和系统包括提供三元内容可寻址存储器（TCAM）。 过滤器规则使用至少一个维度中的值的范围，并对应于前缀（es）。 范围由前缀（es）描述。 一些过滤规则可能会相交。 该方法和系统包括为过滤规则提供优先级。 优先级至少包含与交叉的过滤规则的一个不同的优先级。 该方法和系统还包括基于过滤器规则的优先级按顺序将块中的前缀存储在块中。 在另一方面，所述方法和系统包括搜索TCAM对于密钥的最长前缀匹配，并且搜索附加存储器以与所述TCM并行的所述密钥几乎精确匹配。 在这方面，如果在TCAM中找到最长前缀匹配并且在附加存储器中找不到几乎精确的匹配，则该方法和系统包括返回具有最低或最高位置的最长前缀匹配。

    Lookups by collisionless direct tables and CAMs
    2.
    发明授权
    Lookups by collisionless direct tables and CAMs 失效
    通过无碰撞直接表和CAM进行查找

    公开(公告)号：US07116664B2

    公开(公告)日：2006-10-03

    申请号：US10144610

    申请日：2002-05-13

    申请人： Gordon Taylor Davis ,  Andreas Guenther Herkersdorf ,  Clark Debs Jeffries ,  Mark Anthony Rinaldi

    发明人： Gordon Taylor Davis ,  Andreas Guenther Herkersdorf ,  Clark Debs Jeffries ,  Mark Anthony Rinaldi

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

    CPC分类号： H04L49/3009 ,  H04L45/745 ,  H04L45/7453 ,  H04L49/351

    摘要： A structure and technique for preventing collisions using a hash table in conjunction with a CAM to identify and prevent collisions of binary keys. A portion of the hash value of a binary key, which does not collide with a portion of the hash value of any other reference binary key, is used as an entry in the hash table. If two or more binary keys have identical values of the portions of the hash values, each of these binary keys are stored in their entirety, in the CAM. The key in the CAM provides a pointer to a data structure where the action associated with that binary key is stored. If the binary key is not found in the CAM, the binary key is hashed, and a specific entry in the hash table is selected using a portion of this hash value.

    摘要翻译： 一种用于使用散列表与CAM结合来防止冲突的结构和技术，以识别和防止二进制键的冲突。 不与任何其他参考二进制密钥的散列值的一部分相冲突的二进制密钥的散列值的一部分被用作散列表中的条目。 如果两个或更多个二进制密钥具有相同的哈希值部分的值，则这些二进制密钥中的每一个都将全部存储在CAM中。 CAM中的关键字提供了指向数据结构的指针，其中存储与该二进制密钥相关联的动作。 如果在CAM中没有找到二进制密钥，则二进制密钥被散列，并且使用该哈希值的一部分来选择散列表中的特定条目。

    Lookups by collisionless direct tables and CAMS
    4.
    发明授权
    Lookups by collisionless direct tables and CAMS 有权
    通过无碰撞直接表和CAMS查找

    公开(公告)号：US08081632B2

    公开(公告)日：2011-12-20

    申请号：US11962558

    申请日：2007-12-21

    申请人： Gordon Taylor Davis ,  Andreas Guenther Herkersdorf ,  Clark Debs Jeffries ,  Mark Anthony Rinaldi

    发明人： Gordon Taylor Davis ,  Andreas Guenther Herkersdorf ,  Clark Debs Jeffries ,  Mark Anthony Rinaldi

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

    CPC分类号： H04L49/3009 ,  H04L45/745 ,  H04L45/7453 ,  H04L49/351

    摘要： Computers are caused to provide a hash table wherein each entry is associated with a binary key and indexed by a selected portion of a hash value of the associated key, and points to a data structure location for storing non-selected portions of, or the entire hash value of, the binary key, and action data corresponding to the value of the binary key. Content addressable memory entries store a binary key, or a value unique to it, and an association to a corresponding action. Pointers to the data structure use selected portions of binary key hash values as an index when not selected portions of hash values of other binary keys, and associations are established between CAM entry and associated data structure locations when selected portions of the hash values of the binary keys are the same as selected portions of hash values of one or more other binary keys.

    摘要翻译： 导致计算机提供散列表，其中每个条目与二进制密钥相关联并由相关联的密钥的哈希值的选定部分索引，并且指向用于存储未选择的部分或全部的数据结构位置 哈希值，二进制密钥和对应于二进制密钥值的动作数据。 内容可寻址存储器条目存储二进制密钥或其唯一值，以及与相应操作的关联。 指向数据结构的指针使用二进制密钥散列值的选定部分作为索引，当未选择其他二进制密钥的散列值部分时，以及在CAM条目和相关联的数据结构位置之间建立关联时，二进制对象的哈希值的选定部分 键与一个或多个其他二进制键的哈希值的选定部分相同。

    Network access traffic sorter
    5.
    发明授权
    Network access traffic sorter 失效
    网络访问流量分拣机

    公开(公告)号：US06940864B2

    公开(公告)日：2005-09-06

    申请号：US09906352

    申请日：2001-07-16

    申请人： Youssef Abdelilah ,  Gordon Taylor Davis ,  Jeffrey Haskell Derby ,  Dongming Hwang ,  Clark Debs Jeffries ,  Malcolm Scott Ware ,  Hua Ye

    发明人： Youssef Abdelilah ,  Gordon Taylor Davis ,  Jeffrey Haskell Derby ,  Dongming Hwang ,  Clark Debs Jeffries ,  Malcolm Scott Ware ,  Hua Ye

    IPC分类号： H04L12/56 ,  H04L29/06 ,  H04Q12/28

    CPC分类号： H04L65/605 ,  H04L29/06027 ,  H04L47/2441 ,  H04L47/2458 ,  H04L47/365 ,  H04L47/50 ,  H04L65/80 ,  H04L69/22

    摘要： Packetized voice, video, and data traffic (data frames) are received in a communication traffic sorter. The data frames have a dispatch priority corresponding to their transmission characteristics (flow) and a quality of service parameters. The communication traffic sorter analyzes information in data packets within each data frame and determines an optimum flow for the data frames. A data frame is assigned to a selected queue based on an analysis of the information in its data packets. A data frame may also be assigned to a queue based on a prior analysis of a data frame with like transmission characteristics. Results of analysis are stored and indexed to facilitate processing of subsequent data frames. The network access sorter has circuits to un-pack and re-pack the data frame, when called for, to allow user transmitted data to be processed to create a modified data frame. The data frame may then be dispatched with a second dispatch priority on a bus for distribution to end users where previously assigned quality of service is maintained or exceeded.

    摘要翻译： 分组化语音，视频和数据业务（数据帧）在通信流量分类器中被接收。 数据帧具有对应于其传输特性（流）和服务质量参数的调度优先级。 通信流量分类器分析每个数据帧内的数据分组中的信息，并确定数据帧的最佳流。 基于对其数据分组中的信息的分析，将数据帧分配给所选择的队列。 基于具有相似传输特性的数据帧的先前分析，也可以将数据帧分配给队列。 分析结果存储和索引，以便于后续数据帧的处理。 网络访问分拣机具有用于在被要求时解除数据帧的打包和重新打包的电路，以允许用户传送的数据被处理以创建经修改的数据帧。 然后可以在总线上以第二调度优先级调度数据帧，以便分发给维护或超过先前分配的服务质量的最终用户。

    Method and system for performing a longest prefix match search
    6.
    发明授权
    Method and system for performing a longest prefix match search 失效
    用于执行最长前缀匹配搜索的方法和系统

    公开(公告)号：US06925503B2

    公开(公告)日：2005-08-02

    申请号：US09916766

    申请日：2001-07-27

    申请人： Gordon Taylor Davis ,  Clark Debs Jeffries ,  Grayson Warren Randall ,  Sonia Kiang Rovner

    发明人： Gordon Taylor Davis ,  Clark Debs Jeffries ,  Grayson Warren Randall ,  Sonia Kiang Rovner

    IPC分类号： G06F7/00 ,  G06F15/173 ,  H04L12/56

    CPC分类号： H04L45/54 ,  H04L45/04

    摘要： A method and system for finding a longest prefix match for a key in a computer network is disclosed. The method and system include providing a main engine and providing an auxiliary engine. The main engine is for storing a first plurality of addresses and for searching the first plurality of addresses for the longest prefix match for the key. None of the first plurality of addresses is a prefix for another address of the first plurality of addresses. The auxiliary engine is for storing and searching a second plurality of addresses. A first address of the second plurality of addresses is capable of including the prefix for a second address of the first plurality of addresses or for a third address for the second plurality of addresses. None of the first plurality of addresses is the prefix for any of the second plurality of addresses. Each of the second plurality of addresses is distinct from each of the first plurality of addresses.

    摘要翻译： 公开了一种用于为计算机网络中的密钥找到最长前缀匹配的方法和系统。 该方法和系统包括提供主机并提供​​辅助发动机。 主引擎用于存储第一多个地址，并用于搜索第一多个地址以获得密钥的最长前缀匹配。 第一多个地址中没有一个是第一多个地址的另一地址的前缀。 辅助引擎用于存储和搜索第二多个地址。 第二多个地址的第一地址能够包括第一多个地址的第二地址的前缀或第二多个地址的第三地址。 第一多个地址中没有一个是第二多个地址中的任一个的前缀。 第二多个地址中的每一个与第一多个地址中的每一个不同。

    Method and system for testing filter rules using caching and a tree structure
    7.
    发明授权
    Method and system for testing filter rules using caching and a tree structure 失效
    使用缓存和树结构测试过滤规则的方法和系统

    公开(公告)号：US06529897B1

    公开(公告)日：2003-03-04

    申请号：US09540500

    申请日：2000-03-31

    申请人： Everett Arthur Corl, Jr. ,  Gordon Taylor Davis ,  Clark Debs Jeffries ,  Malcolm Scott Ware

    发明人： Everett Arthur Corl, Jr. ,  Gordon Taylor Davis ,  Clark Debs Jeffries ,  Malcolm Scott Ware

    IPC分类号： G06F1730

    CPC分类号： H04L47/10 ,  H04L47/24 ,  H04L47/2425 ,  H04L63/0227 ,  H04L63/0263 ,  H04Q11/04 ,  H04Q2213/13103 ,  H04Q2213/13343 ,  Y10S707/99932

    摘要： A method and system for testing a plurality of filter rules in a computer system is disclosed. The plurality of filter rules are used with a key that is capable of matching at least one of the plurality of filter rules. The at least one filter rule corresponds to at least one action. The computer system has a cache including a plurality of bins and a decision tree. The method and system include searching a plurality of stored keys in the cache for the key. Preferably, this search of the cache for the key includes determining whether a stored key exactly matches the key. A plurality of stored filter rules corresponds to the plurality of stored keys. A plurality of stored actions corresponds to the plurality of stored filter rules. The cache stores each of the plurality of stored keys and at least one stored action in each bin of a portion of the bins. The method and system also include obtaining the at least one action from the cache if the key is found in plurality of stored keys and otherwise obtaining the at least one action using the decision tree. Preferably, searches of the decision tree and cache start simultaneously. The decision tree search is terminated if the key is found in the cache. The cache is written to if the at least one action is obtained using the decision tree, but preferably only if the at least one filter rule has a priority of one.

    摘要翻译： 公开了一种用于测试计算机系统中的多个过滤规则的方法和系统。 多个滤波器规则与能够匹配多个滤波器规则中的至少一个的密钥一起使用。 至少一个过滤规则对应于至少一个动作。 计算机系统具有包括多个箱体和决策树的高速缓存器。 该方法和系统包括在密钥的高速缓存中搜索多个存储的密钥。 优选地，对于密钥的高速缓存的搜索包括确定存储的密钥是​​否与密钥完全匹配。 多个存储的过滤规则对应于多个存储的密钥。 多个存储的动作对应于多个存储的过滤器规则。 高速缓存存储多个存储的密钥中的每一个以及至少一个存储的动作在仓的一部分的每个仓中。 所述方法和系统还包括如果在多个存储的密钥中找到密钥并且否则使用所述决策树获得所述至少一个动作，则从所述高速缓存获得所述至少一个动作。 优选地，决策树和高速缓存的搜索同时开始。 如果在缓存中找到密钥，则决定树搜索将被终止。 如果使用决策树获得至少一个动作，则优先写入高速缓存，但是优选地仅当所述​​至少一个过滤器规则具有优先级为1时。

    Packet classification using modified range labels
    9.
    发明授权
    Packet classification using modified range labels 失效
    数据包分类使用修改的范围标签

    公开(公告)号：US07796513B2

    公开(公告)日：2010-09-14

    申请号：US12187188

    申请日：2008-08-06

    申请人： Claude Basso ,  Jean Louis Calvignac ,  Gordon Taylor Davis ,  Clark Debs Jeffries

    发明人： Claude Basso ,  Jean Louis Calvignac ,  Gordon Taylor Davis ,  Clark Debs Jeffries

    IPC分类号： H04L12/26

    CPC分类号： H04L45/00 ,  H04L12/4625 ,  H04L45/54 ,  H04L45/7453 ,  H04L63/0263

    摘要： A method and system for encoding a set of range labels for each parameter field in a packet classification key in such a way as to require preferably only a single entry per rule in a final processing stage of a packet classifier. Multiple rules are sorted accorded to their respective significance. A range, based on a parameter in the packet header, is previously determined. Multiple rules are evaluated according to an overlapping of rules according to different ranges. Upon a determination that two or more rules overlap, each overlapping rule is expanded into multiple unique segments that identify unique range intersections. Each cluster of overlapping ranges is then offset so that at least one bit in a range for the rule remains unchanged. The range segments are then converted from binary to Gray code, which results in the ability to determine a CAM entry to use for each range.

    摘要翻译： 一种方法和系统，用于以分组分类密钥中的每个参数字段的一组范围标签进行编码，以便在分组分类器的最后处理阶段中优选地仅需要每个规则仅一个条目。 根据各自的意义对多个规则进行排序。 预先确定基于分组报头中的参数的范围。 根据不同范围的规则重叠来评估多个规则。 在确定两个或更多个规则重叠时，每个重叠规则被扩展为识别唯一范围交点的多个唯一段。 然后，每个重叠范围的簇被偏移，使得该规则的范围中的至少一个位保持不变。 范围段然后从二进制转换为格雷码，这导致确定每个范围使用的CAM条目的能力。