专利快速检索-快速检索全球专利，免费商用专利数据库-IPRDB

1. 发明授权

US07349415B2 Method and apparatus for generating and using enhanced tree bitmap data structures in determining a longest prefix match 有权
标题翻译：用于在确定最长前缀匹配中生成和使用增强树位图数据结构的方法和装置
公开(公告)号：US07349415B2
公开(公告)日：2008-03-25
申请号：US10278623
申请日：2002-10-23
申请人： Vijay Rangarajan , Dalit Sagi , William N. Eatherton
发明人： Vijay Rangarajan , Dalit Sagi , William N. Eatherton
IPC分类号： H04L12/56
CPC分类号： H04L45/00 , G06F17/30961 , G06F17/30985 , H04L45/54 , H04L45/7457
摘要： Methods and apparatus are disclosed for generating and using an enhanced tree bitmap data structure in determining a longest prefix match, such as in a router, packet switching system. One implementation organizes the tree bitmap to minimize the number of internal nodes that must be accessed during a lookup operation. A pointer is included in each of the trie or search nodes to the best match so far entry in the leaf or results array which allows direct access to this result without having to parse a corresponding internal node. Moreover, one implementation stores the internal node for a particular level as a first element in its child array. Additionally, one implementation uses a general purpose lookup engine that can traverse multiple tree bitmaps or other data structures simultaneously, and perform complete searches, partial searches, and resume partial searches such as after receiving additional data on which to search.
摘要翻译：公开了用于在确定最长前缀匹配中，例如在路由器，分组交换系统中生成和使用增强树位图数据结构的方法和装置。一个实现组织树位图以最小化在查找操作期间必须访问的内部节点的数量。在每个特里或搜索节点中都包含一个指针，以便在叶或结果数组中进行最佳匹配，从而允许直接访问该结果，而无需解析对应的内部节点。此外，一个实现将特定级别的内部节点存储在其子阵列中的第一个元素。另外，一个实现使用可以同时遍历多个树位图或其他数据结构的通用查找引擎，并且执行完整的搜索，部分搜索和恢复部分搜索，例如在接收到要搜索的附加数据之后。

2. 发明授权

US07899067B2 Method and apparatus for generating and using enhanced tree bitmap data structures in determining a longest prefix match 有权
标题翻译：用于在确定最长前缀匹配中生成和使用增强树位图数据结构的方法和装置
公开(公告)号：US07899067B2
公开(公告)日：2011-03-01
申请号：US10161504
申请日：2002-05-31
申请人： Vijay Rangarajan , Dalit Sagi , William N. Eatherton
发明人： Vijay Rangarajan , Dalit Sagi , William N. Eatherton
IPC分类号： H04L12/56
CPC分类号： H04L45/00 , G06F17/30961 , G06F17/30985 , H04L45/54 , H04L45/7457
摘要： Methods and apparatus are disclosed for generating and using an enhanced tree bitmap data structure in determining a longest prefix match, such as in a router, packet switching system. One implementation organizes the tree bitmap to minimize the number of internal nodes that must be accessed during a lookup operation. A pointer is included in each of the trie or search nodes to the best match so far entry in the leaf or results array which allows direct access to this result without having to parse a corresponding internal node. Moreover, one implementation stores the internal node for a particular level as a first element in its child array. Additionally, one implementation uses a general purpose lookup engine that can traverse multiple tree bitmaps or other data structures simultaneously, and perform complete searches, partial searches, and resume partial searches such as after receiving additional data on which to search.
摘要翻译：公开了用于在确定最长前缀匹配中，例如在路由器，分组交换系统中生成和使用增强树位图数据结构的方法和装置。一个实现组织树位图以最小化在查找操作期间必须访问的内部节点的数量。在每个特里或搜索节点中都包含一个指针，以便在叶或结果数组中进行最佳匹配，从而允许直接访问该结果，而无需解析对应的内部节点。此外，一个实现将特定级别的内部节点存储在其子阵列中的第一个元素。另外，一个实现使用可以同时遍历多个树位图或其他数据结构的通用查找引擎，并且执行完整的搜索，部分搜索和恢复部分搜索，例如在接收到要搜索的附加数据之后。

3. 发明授权

US07613134B2 Method and apparatus for storing tree data structures among and within multiple memory channels 有权
标题翻译：用于在多个存储器通道内和之内存储树数据结构的方法和装置
公开(公告)号：US07613134B2
公开(公告)日：2009-11-03
申请号：US12059329
申请日：2008-03-31
申请人： Vijay Rangarajan , Shyamsundar N. Maniyar , William N. Eatherton
发明人： Vijay Rangarajan , Shyamsundar N. Maniyar , William N. Eatherton
IPC分类号： H04L12/28
CPC分类号： H04L45/00 , G06F17/30961 , G06F17/30985 , H04L45/54 , H04L45/7457
摘要： Methods and apparatus are disclosed for storing tree data structures among and within multiple memory channels, which may be of particular use with, but not limited to tree bitmap data structures. A subtree (or entire tree) typically includes one or more leaf arrays and multiple tree arrays. One or more leaf arrays are typically stored in a first set of memory channels of N+1 sets of memory channels, the N+1 sets of memory channels including N sets of memory channels plus the first set of memory channels. Each of N contiguous levels of the multiple tree arrays are stored in a different one of said N sets of memory channels, wherein each of the multiple tree arrays at a same level of said N contiguous levels is stored in the same memory channel set of said N sets of memory channels. A memory channel for storing a particular level is typically assigned based on one or more current occupancy levels of the memory channels.
摘要翻译：公开了用于在多个存储器通道内和之内存储树数据结构的方法和装置，其可以特别用于但不限于树位图数据结构。子树（或整个树）通常包括一个或多个叶阵列和多个树阵列。一个或多个叶阵列通常存储在N + 1组存储器通道的第一组存储器通道中，N + 1组存储器通道包括N组存储器通道加上第一组存储器通道。多个树阵列的N个连续级别中的每一个存储在所述N组存储器通道中的不同的一组中，其中在所述N个连续级别的同一级别的多个树阵列中的每一个被存储在与所述N个连续级别相同的存储器通道组中 N组内存通道。用于存储特定级别的存储器通道通常基于存储器通道的一个或多个当前占用电平来分配。

4. 发明授权

US07352739B1 Method and apparatus for storing tree data structures among and within multiple memory channels 有权
标题翻译：用于在多个存储器通道内和之内存储树数据结构的方法和装置
公开(公告)号：US07352739B1
公开(公告)日：2008-04-01
申请号：US10356262
申请日：2003-01-31
申请人： Vijay Rangarajan , Shyamsundar N. Maniyar , William N. Eatherton
发明人： Vijay Rangarajan , Shyamsundar N. Maniyar , William N. Eatherton
IPC分类号： H04L12/50
CPC分类号： H04L45/00 , G06F17/30961 , G06F17/30985 , H04L45/54 , H04L45/7457
摘要： Tree data structures are stored among and within multiple memory channels, which may be of particular use with, but not limited to tree bitmap data structures. A subtree (or entire tree) typically includes one or more leaf arrays and multiple tree arrays. One or more leaf arrays are typically stored in a first set of memory channels of N+1 sets of memory channels, the N+1 sets of memory channels including N sets of memory channels plus the first set of memory channels. Paths of the multiple tree arrays are typically stored in said N memory channels, wherein each tree array of the multiple tree arrays associated with one of said paths is stored in a different one of said N sets of memory channels.
摘要翻译：树数据结构存储在多个存储器通道内并在多个存储器通道内，其可以特别用于但不限于树位图数据结构。子树（或整个树）通常包括一个或多个叶阵列和多个树阵列。一个或多个叶阵列通常存储在N + 1组存储器通道的第一组存储器通道中，N + 1组存储器通道包括N组存储器通道加上第一组存储器通道。多个树阵列的路径通常存储在所述N个存储器通道中，其中与所述路径之一相关联的多个树阵列的每个树阵列被存储在所述N组存储器通道中的不同的一组中。

5. 发明授权

US07237059B2 Performing lookup operations on associative memory entries 有权
标题翻译：对关联内存条目执行查找操作
公开(公告)号：US07237059B2
公开(公告)日：2007-06-26
申请号：US11321918
申请日：2005-12-28
申请人： William N. Eatherton , Jaushin Lee , Bangalore L. Priyadarshan , Priyank Ramesh Warkhede , Fusun Ertemalp , Hugh Weber Holbrook , Dileep Kumar Devireddy , Bhushan Mangesh Kanekar , Venkateshwar Rao Pullela
发明人： William N. Eatherton , Jaushin Lee , Bangalore L. Priyadarshan , Priyank Ramesh Warkhede , Fusun Ertemalp , Hugh Weber Holbrook , Dileep Kumar Devireddy , Bhushan Mangesh Kanekar , Venkateshwar Rao Pullela
IPC分类号： G06F12/00
CPC分类号： G06F17/30982
摘要： Methods and apparatus are disclosed for performing lookup operations using associative memories, including, but not limited to modifying search keys within an associative memory based on modification mappings, forcing a no-hit condition in response to a highest-priority matching entry including a force no-hit indication, selecting among various sets or banks of associative memory entries in determining a lookup result, and detecting and propagating error conditions. In one implementation, each block retrieves a modification mapping from a local memory and modifies a received search key based on the mapping and received modification data. In one implementation, each of the associative memory entries includes a field for indicating that a successful match on the entry should or should not force a no-hit result. In one implementation, an indication of which associative memory blocks or sets of entries to use in a particular lookup operation is retrieved from a memory.
摘要翻译：公开了用于使用关联存储器执行查找操作的方法和装置，包括但不限于基于修改映射修改关联存储器内的搜索关键字，响应于最高优先级的匹配条目来响应不受限制的条件，包括力 - 指示，在确定查找结果中选择各种组或存储器中的关联存储器条目，以及检测和传播错误条件。在一个实现中，每个块从本地存储器检索修改映射，并且基于映射和接收到的修改数据修改接收到的搜索密钥。在一个实现中，每个关联存储器条目包括用于指示条目上的成功匹配应该或不应该强制无命中结果的字段。在一个实现中，从存储器检索在特定查找操作中使用的哪些关联存储器块或条目集合的指示。

6. 发明授权

US06654342B1 Accumulating and distributing flow control information via update messages and piggybacked flow control information in other messages in a packet switching system 有权
标题翻译：通过分组交换系统中的其他消息中的更新消息和捎带流控制信息来累积和分发流量控制信息
公开(公告)号：US06654342B1
公开(公告)日：2003-11-25
申请号：US09521278
申请日：2000-03-07
申请人： Zubin D. Dittia , William N. Eatherton , John Andrew Fingerhut , Michael B. Galles , Jonathan S. Turner
发明人： Zubin D. Dittia , William N. Eatherton , John Andrew Fingerhut , Michael B. Galles , Jonathan S. Turner
IPC分类号： G01R3108
CPC分类号： H04L12/5602
摘要： Methods and apparatus are disclosed for accumulating and distributing flow control information via update messages and piggybacked flow control information in other messages. One implementation operates using at least two techniques. Using a first technique, for every packet entering the switching system from a line card, the switching system conveys flow control information (typically congestion or both congestion and no-congestion indications) for the packet's destination to the line card. Using a second technique, the switching system will periodically convey congestion and no-congestion indications for all destinations to the line cards. In one implementation, when the first technique is used to provide only congestion indications, the periodic distribution of flow control information using the second technique provides non-congested indications which allows the line cards and their sources to resume or begin sending to the non-congested destinations.
摘要翻译：公开了用于通过更新消息积累和分发流量控制信息的方法和装置以及其他消息中的捎带流控制信息。一个实现使用至少两种技术来进行操作。使用第一种技术，对于从线路卡进入交换系统的每个分组，交换系统将分组目的地的流量控制信息（通常拥塞或两者拥塞和无拥塞指示）传送到线路卡。使用第二种技术，交换系统将周期性地向线路卡传送所有目的地的拥塞和无拥塞指示。在一个实现中，当第一技术被用于仅提供拥塞指示时，使用第二技术的流量控制信息的周期性分布提供非拥塞指示，其允许线路卡及其源恢复或开始发送到非拥塞目的地。

7. 发明授权

US07496035B1 Methods and apparatus for defining flow types and instances thereof such as for identifying packets corresponding to instances of the flow types 有权
标题翻译：用于定义流类型和实例的方法和装置，例如用于识别与流类型的实例对应的分组
公开(公告)号：US07496035B1
公开(公告)日：2009-02-24
申请号：US10355831
申请日：2003-01-31
申请人： Ganesh Sadasivan , Rengabashyam Srinivas , William N. Eatherton , Xiaoxue Ma , Peram Marimuthu
发明人： Ganesh Sadasivan , Rengabashyam Srinivas , William N. Eatherton , Xiaoxue Ma , Peram Marimuthu
IPC分类号： G08C15/00
CPC分类号： H04L49/901 , H04L47/10 , H04L47/2441 , H04L49/90 , Y10S707/99943
摘要： Methods and apparatus are disclosed for defining flow types and instances thereof such as for identifying packets corresponding to instances of the flow types. A flow type is defined and includes a set of properties including at least one of the possible properties selectable when defining a flow type. An instance of the flow type is defined and a set of corresponding associative memory entries is generated. A lookup word generator of a packet processing engine is typically notified of the use of the flow type, and one or more lookup words are generated typically by extracting fields from a received packet and/or from other sources. Based on a result of lookup operations on the set of associative memories entries using the generated one or more lookup words, the received packet can be identified as whether it matches or does not match the instance of the flow type.
摘要翻译：公开了用于定义流类型和实例的方法和装置，例如用于识别与流类型的实例对应的分组。定义流类型并且包括一组属性，其包括在定义流类型时可选择的可能属性中的至少一个。定义流类型的实例，并生成一组对应的关联内存条目。典型地通过从所接收的分组和/或来自其它来源提取字段来生成分组处理引擎的查找词生成器，使用流类型，并且生成一个或多个查找词。基于使用所生成的一个或多个查找词的关联存储器条目集合的查找操作的结果，可以将接收的分组识别为与流类型的实例匹配还是不匹配。

8. 发明授权

US07313093B1 Methods and apparatus for selectively discarding packets during overload conditions 有权
标题翻译：在过载条件下有选择地丢弃数据包的方法和装置
公开(公告)号：US07313093B1
公开(公告)日：2007-12-25
申请号：US10304421
申请日：2002-11-26
申请人： William N. Eatherton , John H. W. Bettink
发明人： William N. Eatherton , John H. W. Bettink
IPC分类号： H04L12/56
CPC分类号： H04L47/10 , H04L47/30 , H04L47/32
摘要： Methods and apparatus are disclosed for selectively discarding packets such as in, but not limited to a packet switching system, by reacting to packet traffic conditions to reduce or eliminate the indiscriminate discarding of packets during identified overload conditions. Typically, a first element forwards multiple packets to a second element, each of the multiple packets being associated with a packet overload condition type of possible packet overload condition types, including, but not limited to a discard-on-overload type and a retain-on-overload type. The first element forwards a condition indication to the second element. The second element receives the condition indication and a particular packet. The second element discards the particular packet if the received condition indication is associated with the overload state and the packet overload condition type of the particular received packet is associated with the discard-on-overload type. Otherwise, the second element typically further processes the particular packet.
摘要翻译：公开了用于选择性地丢弃分组的方法和装置，所述分组例如在但不限于分组交换系统中，通过对分组业务条件做出反应以减少或消除在所识别的过载条件期间不加区分地丢弃分组。通常，第一元件将多个分组转发到第二元素，多个分组中的每一个与可能的分组过载条件类型的分组过载条件类型相关联，包括但不限于丢弃过载类型和保留 - 过载类型。第一个元素将条件指示转发给第二个元素。第二个元件接收条件指示和特定数据包。如果接收到的条件指示与过载状态相关联并且特定接收到的分组的分组过载状况类型与丢弃过载类型相关联，则第二元素丢弃该特定分组。否则，第二元素通常进一步处理特定分组。

9. 发明授权

US07249149B1 Tree bitmap data structures and their use in performing lookup operations 有权
标题翻译：树位图数据结构及其在执行查找操作中的用途
公开(公告)号：US07249149B1
公开(公告)日：2007-07-24
申请号：US10833532
申请日：2004-04-26
申请人： William N. Eatherton , Zubin D. Dittia
发明人： William N. Eatherton , Zubin D. Dittia
IPC分类号： G06F7/00
CPC分类号： H04L12/56 , H04L45/7457 , Y10S707/99943 , Y10S707/99945 , Y10S707/99948
摘要： Disclosed are, inter alia, methods, apparatus, data structures, computer-readable media, mechanisms, and means for defining, creating and using tree bitmap data structures, such as for, but not limited to their use in performing lookup operations (e.g., longest prefix matching, etc.). The data structure typically includes a tree bitmap for identifying for each node of multiple nodes within a stride of a number of tree levels greater than one whether each node is a prefix or vacant node, the multiple nodes representing multiple tree levels, a lowest level subset of the multiple nodes corresponding to a lowest level of the tree levels in the stride, the lowest level subset of the multiple nodes including two or more nodes. A child bitmap is typically used for identifying which trie paths emanate and which trie paths do not emanate from the lowest level subset of the multiple nodes.
摘要翻译：公开的方法，装置，数据结构，计算机可读介质，机制和用于定义，创建和使用树位图数据结构的装置，诸如但不限于它们在执行查找操作中的用途（例如，最长前缀匹配等）。数据结构通常包括树位图，用于识别大于每个节点是否为前缀或空闲节点的多个树级别的步长内的多个节点的每个节点，多个节点表示多个树级别，最低级别子集对应于步幅中的树级的最低级的多个节点，包括两个或多个节点的多个节点的最低级子集。子位图通常用于识别出现哪些特洛伊路径，哪些特里路径不从多个节点的最低级子集发出。

10. 发明授权

US06728211B1 Method and apparatus for delaying packets being sent from a component of a packet switching system 有权
标题翻译：用于延迟从分组交换系统的组件发送的分组的方法和装置
公开(公告)号：US06728211B1
公开(公告)日：2004-04-27
申请号：US09520685
申请日：2000-03-07
申请人： Vinod Gerard John Peris , Jonathan S. Turner , Zubin D. Dittia , William N. Eatherton
发明人： Vinod Gerard John Peris , Jonathan S. Turner , Zubin D. Dittia , William N. Eatherton
IPC分类号： H04L1226
CPC分类号： H04L47/10 , H04L47/12 , H04L47/26 , H04L47/32 , H04L49/101 , H04L49/20 , H04L49/201 , H04L49/254 , H04L49/3027
摘要： Methods and apparatus are also disclosed for responding to received flow control messages indicating a previously congested port is now in a non-congested state. Many different components that have packets to send to a particular output will receive an indication that they are now allowed to send these packets at roughly the same time as the other components. If all components start sending at the same time, then the packet switch might become congested, possibly very quickly. If the packet switch cannot respond and transmit flow control messages to all of these sources fast enough, certain internal buffers could overflow and thus packets might be lost. On implementation causes components to start sending to the destination at varying times to gradually increase the traffic being sent to the destination. In this manner, the traffic in the packet switch gradually rises which allows buffers within the packet switch to drain while new traffic is arriving, and allows the packet switch time to react and throttle-back the traffic in a reasonable manner should paths leading to the output become congested.
摘要翻译：还公开了用于响应指示先前拥塞的端口现在处于非拥塞状态的接收的流控制消息的方法和装置。具有发送到特定输出的数据包的许多不同组件将接收到它们现在允许与其他组件大致相同的时间发送这些数据包的指示。如果所有组件同时开始发送，则分组交换机可能会变得拥塞，可能非常快。如果分组交换机不能快速响应并向所有这些源发送流量控制消息，某些内部缓冲区可能会溢出，从而数据包可能丢失。在实施时，组件可以在不同的时间开始发送到目的地，以逐渐增加发送到目的地的流量。以这种方式，分组交换机中的业务量逐渐上升，这允许分组交换机内的缓冲区在新的业务到达时消失，并且允许分组交换时间以合理的方式作出反应并节省流量，如果通向输出变得拥塞。

你已经成功收藏专利！

检索式保存成功!

IPRDB

热门服务

关于我们

友情链接

联系方式