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

1. 发明申请

US20050157712A1 Method and apparatus for generating and using enhanced tree bitmap data structures in determining a longest prefix match 有权
标题翻译：用于在确定最长前缀匹配中生成和使用增强树位图数据结构的方法和装置
公开(公告)号：US20050157712A1
公开(公告)日：2005-07-21
申请号：US10278623
申请日：2002-10-23
申请人： Vijay Rangarajan , Dalit Sagi , William Eatherton
发明人： Vijay Rangarajan , Dalit Sagi , William Eatherton
IPC分类号： G06F17/30 , H04L12/56 , H04Q11/00
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. 发明授权

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.
摘要翻译：公开了用于在确定最长前缀匹配中，例如在路由器，分组交换系统中生成和使用增强树位图数据结构的方法和装置。一个实现组织树位图以最小化在查找操作期间必须访问的内部节点的数量。在每个特里或搜索节点中都包含一个指针，以便在叶或结果数组中进行最佳匹配，从而允许直接访问该结果，而无需解析对应的内部节点。此外，一个实现将特定级别的内部节点存储在其子阵列中的第一个元素。另外，一个实现使用可以同时遍历多个树位图或其他数据结构的通用查找引擎，并且执行完整的搜索，部分搜索和恢复部分搜索，例如在接收到要搜索的附加数据之后。

3. 发明授权

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.
摘要翻译：公开了用于在确定最长前缀匹配中，例如在路由器，分组交换系统中生成和使用增强树位图数据结构的方法和装置。一个实现组织树位图以最小化在查找操作期间必须访问的内部节点的数量。在每个特里或搜索节点中都包含一个指针，以便在叶或结果数组中进行最佳匹配，从而允许直接访问该结果，而无需解析对应的内部节点。此外，一个实现将特定级别的内部节点存储在其子阵列中的第一个元素。另外，一个实现使用可以同时遍历多个树位图或其他数据结构的通用查找引擎，并且执行完整的搜索，部分搜索和恢复部分搜索，例如在接收到要搜索的附加数据之后。

4. 发明授权

US07508829B2 Method and apparatus providing prioritized recursion resolution of border gateway protocol forwarding information bases 有权
标题翻译：提供边界网关协议转发信息库优先递归解析的方法和装置
公开(公告)号：US07508829B2
公开(公告)日：2009-03-24
申请号：US11291940
申请日：2005-11-30
申请人： Vijay Rangarajan , Clarence Filsfils , John Bettink
发明人： Vijay Rangarajan , Clarence Filsfils , John Bettink
IPC分类号： H04L12/28
CPC分类号： H04L47/6215 , H04L45/02 , H04L45/021 , H04L45/023 , H04L45/028 , H04L45/54 , H04L45/60 , H04L47/50
摘要： A method, performed in a network packet routing element, comprises establishing a forwarding information base (FIB) lacking a hierarchical data structure but in which one or more dependent FIB entries are associated with a parent FIB entry; establishing a plurality of strict priority queues, each having an associated priority; receiving a change to the parent FIB entry; for each of the dependent FIB entries, selecting one of the queues and enqueuing the dependent FIB entries in the selected queues for re-resolution; dequeuing the dependent FIB entries for re-resolution, according to a priority order of the queues.
摘要翻译：一种在网络分组路由选择单元中执行的方法，包括：建立一个缺少分层数据结构的转发信息库（FIB），其中一个或多个从属FIB表项与父FIB表项相关联; 建立多个严格优先级队列，每个具有相关优先权; 接收对父FIB条目的更改; 对于每个依赖FIB条目，选择一个队列并对所选队列中的依赖FIB条目进行排队以进行重新分辨; 根据队列的优先级顺序对依赖FIB条目进行队列重新分辨。

5. 发明申请

US20070121524A1 Method and apparatus providing prioritized recursion resolution of border gateway protocol forwarding information bases 有权
标题翻译：提供边界网关协议转发信息库优先递归解析的方法和装置
公开(公告)号：US20070121524A1
公开(公告)日：2007-05-31
申请号：US11291940
申请日：2005-11-30
申请人： Vijay Rangarajan , Clarence Filsfils , John Bettink
发明人： Vijay Rangarajan , Clarence Filsfils , John Bettink
IPC分类号： H04J1/16 , G06F15/173 , H04L12/26
CPC分类号： H04L47/6215 , H04L45/02 , H04L45/021 , H04L45/023 , H04L45/028 , H04L45/54 , H04L45/60 , H04L47/50
摘要： A method, performed in a network packet routing element, comprising establishing a forwarding information base (FIB) lacking a hierarchical data structure but wherein one or more dependent FIB entries are associated with a parent FIB entry; establishing a plurality of strict priority queues, wherein each of the queues has an associated priority; receiving a change to the parent FIB entry; for each of the dependent FIB entries, selecting one of the queues and enqueuing the dependent FIB entries in the selected queues for re-resolution; dequeuing the dependent FIB entries for re-resolution, according to a priority order of the queues.
摘要翻译：一种在网络分组路由选择单元中执行的方法，包括建立缺少分级数据结构的转发信息库（FIB），但是其中一个或多个从属FIB表项与父FIB表项相关联; 建立多个严格优先级队列，其中每个队列具有相关联的优先级; 接收对父FIB条目的更改; 对于每个依赖FIB条目，选择一个队列并对所选队列中的依赖FIB条目进行排队以进行重新分辨; 根据队列的优先级顺序对依赖FIB条目进行队列重新分辨。

6. 发明申请

US20110243136A1 Forwarding multi-destination packets in a network with virtual port channels 有权
标题翻译：在具有虚拟端口通道的网络中转发多目的数据包
公开(公告)号：US20110243136A1
公开(公告)日：2011-10-06
申请号：US12798131
申请日：2010-03-30
申请人： Pirabhu Raman , Dinesh Dutt , Mahesh Maddury , Subbarao Arumilli , Vijay Rangarajan , Ray Kloth , Sanjay Sane
发明人： Pirabhu Raman , Dinesh Dutt , Mahesh Maddury , Subbarao Arumilli , Vijay Rangarajan , Ray Kloth , Sanjay Sane
IPC分类号： H04L12/56
CPC分类号： H04L49/201 , H04L45/60 , H04L49/354 , H04L49/70
摘要： In one embodiment, a method includes receiving a multi-destination packet at a switch in communication with a plurality of servers through a network device, identifying a port receiving the multi-destination packet at the switch or a forwarding topology for the multi-destination packet, selecting a bit value based on the identified port or forwarding topology, inserting the bit value into a field in a virtual network tag in the multi-destination packet, and forwarding the multi-destination packet with the virtual network tag to the network device. The network device is configured to forward the multi-destination packet to one or more of the servers based on the bit value in the multi-destination packet. An apparatus for forwarding multi-destination packets is also disclosed.
摘要翻译：在一个实施例中，一种方法包括通过网络设备在与多个服务器通信的交换机处接收多目的地分组，识别在交换机处接收多目的地分组的端口或多目的地分组的转发拓扑基于所识别的端口或转发拓扑来选择位值，将所述位值插入到所述多目的地分组中的虚拟网络标签中的字段中，并将具有所述虚拟网络标签的所述多目的地分组转发到所述网络设备。网络设备被配置为基于多目的地分组中的比特值将多目的地分组转发到一个或多个服务器。还公开了用于转发多目的地分组的装置。

7. 发明授权

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组存储器通道中的不同的一组中。

8. 发明授权

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组内存通道。用于存储特定级别的存储器通道通常基于存储器通道的一个或多个当前占用电平来分配。

9. 发明授权

US08249069B2 Forwarding multi-destination packets in a network with virtual port channels 有权
标题翻译：在具有虚拟端口通道的网络中转发多目的数据包
公开(公告)号：US08249069B2
公开(公告)日：2012-08-21
申请号：US12798131
申请日：2010-03-30
申请人： Pirabhu Raman , Dinesh Dutt , Mahesh Maddury , Subbarao Arumilli , Vijay Rangarajan , Ray Kloth , Sanjay Sane
发明人： Pirabhu Raman , Dinesh Dutt , Mahesh Maddury , Subbarao Arumilli , Vijay Rangarajan , Ray Kloth , Sanjay Sane
IPC分类号： H04L12/28
CPC分类号： H04L49/201 , H04L45/60 , H04L49/354 , H04L49/70
摘要： In one embodiment, a method includes receiving a multi-destination packet at a switch in communication with a plurality of servers through a network device, identifying a port receiving the multi-destination packet at the switch or a forwarding topology for the multi-destination packet, selecting a bit value based on the identified port or forwarding topology, inserting the bit value into a field in a virtual network tag in the multi-destination packet, and forwarding the multi-destination packet with the virtual network tag to the network device. The network device is configured to forward the multi-destination packet to one or more of the servers based on the bit value in the multi-destination packet. An apparatus for forwarding multi-destination packets is also disclosed.
摘要翻译：在一个实施例中，一种方法包括通过网络设备在与多个服务器通信的交换机处接收多目的地分组，识别在交换机处接收多目的地分组的端口或多目的地分组的转发拓扑基于所识别的端口或转发拓扑来选择位值，将所述位值插入到所述多目的地分组中的虚拟网络标签中的字段中，并将具有所述虚拟网络标签的所述多目的地分组转发到所述网络设备。网络设备被配置为基于多目的地分组中的比特值将多目的地分组转发到一个或多个服务器。还公开了用于转发多目的地分组的装置。

你已经成功收藏专利！

检索式保存成功!

IPRDB

热门服务

关于我们

友情链接

联系方式