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

1. 发明申请

US20030126113A1 Method and apparatus for storing sparse and dense subtrees in a longest prefix match lookup table 有权
公开(公告)号：US20030126113A1
公开(公告)日：2003-07-03
申请号：US10336055
申请日：2003-01-02
申请人： MOSAID Technologies, Inc.
发明人： David A. Brown
IPC分类号： G06F007/00
CPC分类号： H04L45/742 , G06F17/30955 , G11C15/00 , H04L45/00 , H04L45/02 , H04L45/04 , H04L45/54 , H04L45/7453 , H04L45/7457 , Y10S707/99931 , Y10S707/99933 , Y10S707/99943
摘要： We present a lookup table which allows sparse subtree descriptors and dense subtree descriptors to be stored in the same memory. A subtree entry in the memory stores a dense subtree descriptor for a dense subtree or a plurality of sparse subtree descriptors for sparse subtrees. The subtree entry is indexed by a leaf in the previous subtree. The sparse subtree descriptor stores at least one node descriptor. The node descriptor describes a set of leaves in the sparse subtree having a common value. The common value is encoded in the node descriptor using run length encoding.

2. 发明申请

US20010043602A1 Method and apparatus for an incremental update of a longest prefix match lookup table 有权
标题翻译：用于增加更新最长前缀匹配查找表的方法和装置
公开(公告)号：US20010043602A1
公开(公告)日：2001-11-22
申请号：US09733629
申请日：2000-12-08
申请人： Mosaid Technologies, Inc.
发明人： David A. Brown
IPC分类号： H04L012/28
CPC分类号： H04L45/742 , G06F17/30955 , G11C15/00 , H04L45/00 , H04L45/02 , H04L45/04 , H04L45/54 , H04L45/7453 , H04L45/7457 , Y10S707/99931 , Y10S707/99933 , Y10S707/99943
摘要： A method and apparatus for performing an incremental update of a lookup table while the lookup table is available for searching is presented. To add or delete a route, a second set of routes is stored in a second memory space in the lookup table, while access is provided to the first set of routes stored in a first memory space in the lookup table. Access is provided to the first memory space through a first pointer stored in a subtree entry. After storing the second set of routes in the second memory space, access is switched to the first set of routes in the first memory space by replacing the first pointer stored in the subtree entry with a second pointer to the second memory space.
摘要翻译：呈现在查找表可用于搜索时执行查找表的增量更新的方法和装置。为了添加或删除路由，第二组路由被存储在查找表中的第二存储器空间中，而访问被提供给存储在查找表中的第一存储器空间中的第一组路由。通过存储在子树条目中的第一个指针将访问提供给第一个存储空间。在将第二组路由存储在第二存储器空间中之后，通过用存储在子树条目中的第一指针替换第二存储器空间的第二指针，将访问切换到第一存储器空间中的第一组路由。

3. 发明申请

US20040054655A1 Method and apparatus for searching a filtering database with one search operation 失效
标题翻译：用一个搜索操作搜索过滤数据库的方法和装置
公开(公告)号：US20040054655A1
公开(公告)日：2004-03-18
申请号：US10625320
申请日：2003-07-23
申请人： MOSAID Technologies, Inc.
发明人： David A. Brown
IPC分类号： G06F007/00
CPC分类号： H04L12/4625 , H04L12/4641 , Y10S707/959 , Y10S707/99931 , Y10S707/99933
摘要： Multiple searches of a filtering database increase the time for filtering a data packet received by a switch. A switch including a translator and a filtering database for performing a single search is presented. The translator provides a translated identifier for an identifier associated with a data packet received by the switch. The translated identifier includes a group identifier corresponding to a virtual LAN group (FID) and a group member number corresponding to an identified virtual LAN (VID). The filter data base stores a static entry and a dynamic entry. The static entry stores a forwarding decision for the data packet associated with the translated identifier. The dynamic entry stores a forwarding decision for the data packet associated with the group identifier included in the translated identifier and the group member number set to don't care. The translated identifier allows a filtering database to provide the forwarding decision stored in the static entry or the dynamic entry for the identifier from a single search operation.
摘要翻译：过滤数据库的多次搜索增加了过滤交换机接收的数据包的时间。提出了一种包括翻译器和用于执行单次搜索的过滤数据库的开关。翻译器提供与由交换机接收的数据分组相关联的标识符的翻译标识符。被翻译的标识符包括对应于虚拟LAN组（FID）的组标识符和对应于所识别的虚拟LAN（VID）的组成员编号。过滤器数据库存储静态条目和动态条目。静态条目存储与转换的标识符相关联的数据分组的转发决定。动态条目存储与包括在翻译的标识符中的组标识符相关联的数据分组的转发决定以及设置为不关心的组成员编号。翻译的标识符允许过滤数据库从单个搜索操作提供存储在静态条目中的转发决策或用于标识符的动态条目。

4. 发明申请

US20020067296A1 Multi-stage lookup for translating between signals of different bit lengths 有权
公开(公告)号：US20020067296A1
公开(公告)日：2002-06-06
申请号：US10022932
申请日：2001-12-18
申请人： MOSAID Technologies, Inc.
发明人： David A. Brown
IPC分类号： H03M007/00
CPC分类号： H04L12/4641 , H04L45/745 , H04L49/201 , H04L49/351 , H04L49/354
摘要： A method and apparatus is provided for translating an L-bit input signal to a W-bit output signal such as a virtual network identification signal to an internal virtual network signal. The translation is performed using a multi-stage lookup. The input signal is portioned into a plurality of subsets of bits. A first index to a first stage is provided by combining a portion of bits and a first delta subset of bits. A second index to a second stage is provided by combining data stored at the first index in the first stage and the a second delta subset of bits. The corresponding output signal is stored at the last index in the last stage. The use of the multi-stage lookup instead of a single-stage lookup reduces the memory required to perform the translation.

5. 发明申请

US20040062208A1 Dense mode coding scheme 有权
标题翻译：密集模式编码方案
公开(公告)号：US20040062208A1
公开(公告)日：2004-04-01
申请号：US10262643
申请日：2002-09-30
申请人： MOSAID Technologies Inc.
发明人： David A. Brown , Peter B. Gillingham
IPC分类号： H04L012/28
CPC分类号： H04L45/00 , H04L45/7457
摘要： A lookup table for searching for a longest prefix match for a key is disclosed. The lookup table provides a match for a key in a single search cycle. The number of matches stored in the lookup table is maximized by storing each match in only one location in the lookup table. The binary tree is divided into a plurality of levels and each level has a plurality of subtrees. A subtree descriptor stored for a subtree includes a field for each node in the subtree. The state of the field indicates whether an entry for the node is stored in the table. The bit vector allows indexing of the single match stored for the key.
摘要翻译：公开了一种用于搜索密钥的最长前缀匹配的查找表。查找表提供了单个搜索周期中的键的匹配。通过将每个匹配存储在查找表中的一个位置来最大化存储在查找表中的匹配数。二叉树被分成多个级别，每个级别具有多个子树。为子树存储的子树描述符包含子树中每个节点的字段。该字段的状态指示节点的条目是否存储在表中。位向量允许为密钥存储的单个匹配索引。

6. 发明申请

US20020184221A1 Load balancing in IP address lookup 有权
标题翻译： IP地址查找中的负载均衡
公开(公告)号：US20020184221A1
公开(公告)日：2002-12-05
申请号：US10132675
申请日：2002-04-24
申请人： MOSAID Technologies, Inc.
发明人： Imtiaz Ahmad , David A. Brown
IPC分类号： G06F007/00 , G06F017/00
CPC分类号： H04L45/745 , Y10S707/99933 , Y10S707/99942 , Y10S707/99943 , Y10S707/99956
摘要： A load balancing mechanism maps a binary tree representation of a routing table into a set of fixed size memories. The mechanism efficiently utilizes the memory in the routing table without violating the tree precedence constraints and the memory access requirements of a pipelined system. The mechanism stores a subtree associated with a densely populated level of the binary tree in memory associated with lower levels.
摘要翻译：负载平衡机制将路由表的二叉树表示映射到一组固定大小的存储器中。该机制有效地利用路由表中的存储器，而不违反流优先级约束和流水线系统的存储器访问要求。该机制将与二进制树的密集层次相关联的子树存储在与较低级别相关联的存储器中。

7. 发明申请

US20010044876A1 Method and apparatus for storing sparse and dense subtrees in a longest prefix match lookup table 有权
标题翻译：用于在最长前缀匹配查找表中存储稀疏和密集子树的方法和装置
公开(公告)号：US20010044876A1
公开(公告)日：2001-11-22
申请号：US09733761
申请日：2000-12-08
申请人： Mosaid Technologies, Inc.
发明人： David A. Brown
IPC分类号： G06F012/00
CPC分类号： H04L45/742 , G06F17/30955 , G11C15/00 , H04L45/00 , H04L45/02 , H04L45/04 , H04L45/54 , H04L45/7453 , H04L45/7457 , Y10S707/99931 , Y10S707/99933 , Y10S707/99943
摘要： We present a lookup table which allows sparse subtree descriptors and dense subtree descriptors to be stored in the same memory. A subtree entry in the memory stores a dense subtree descriptor for a dense subtree or a plurality of sparse subtree descriptors for sparse subtrees. The subtree entry is indexed by a leaf in the previous subtree. The sparse subtree descriptor stores at least one node descriptor. The node descriptor describes a set of leaves in the sparse subtree having a common value. The common value is encoded in the node descriptor using run length encoding.
摘要翻译：我们提出一个查找表，允许稀疏子树描述符和密集子树描述符存储在同一个存储器中。存储器中的子树条目存储密集子树的密集子树描述符或稀疏子树的多个稀疏子树描述符。子树条目由先前子树中的叶子索引。稀疏子树描述符存储至少一个节点描述符。节点描述符描述具有公共值的稀疏子树中的一组叶。公共值使用运行长度编码在节点描述符中编码。

8. 发明申请

US20010042130A1 Method and apparatus for depth expansion of a longest prefix match lookup table 审中-公开
标题翻译：用于深度扩展最长前缀匹配查找表的方法和装置
公开(公告)号：US20010042130A1
公开(公告)日：2001-11-15
申请号：US09733628
申请日：2000-12-08
申请人： Mosaid Technologies, Inc.
发明人： David A. Brown
IPC分类号： G06F015/173
CPC分类号： H04L45/742 , G06F16/902 , G11C15/00 , H04L45/00 , H04L45/02 , H04L45/04 , H04L45/54 , H04L45/7453 , H04L45/7457 , Y10S707/99931 , Y10S707/99933 , Y10S707/99943
摘要： We present a method and apparatus for increasing the depth of a lookup table. The lookup table includes at least two lookup units. A search request for a final result value corresponding to the key is issued to each of the lookup units in parallel. Each of the lookup units performs a multi-level search in parallel for the final result value. The final result value stored in only one of the lookup units is provided by one of the lookup units.
摘要翻译：我们提出了一种增加查找表深度的方法和装置。查找表包括至少两个查找单元。与密钥对应的最终结果值的搜索请求并行发布给每个查找单元。每个查找单元针对最终结果值并行执行多级搜索。存储在仅一个查找单元中的最终结果值由查询单元之一提供。

9. 发明申请

US20030218978A1 Method and apparatus for reordering entries in a multi probe lookup 有权
标题翻译：在多探针查找中重新排序条目的方法和装置
公开(公告)号：US20030218978A1
公开(公告)日：2003-11-27
申请号：US10156725
申请日：2002-05-24
申请人： MOSAID Technologies, Inc.
发明人： David A. Brown
IPC分类号： H04J001/16 , H04L012/28
CPC分类号： H04L45/54 , G06F17/30949 , H04L47/21 , H04L49/205 , H04L49/3009 , H04L49/351
摘要： A multi-probe lookup table includes an indication of the congestion level of each addressable location. A key can be stored in one of a plurality of indexed locations in the lookup table. Thrashing is reduced by inserting keys into the lookup table based on the distribution of keys already stored in the lookup table. Insert operations for all keys sharing an indexed location are recorded by modifying a swap count indicating the congestion level of the indexed location each time a key is inserted in one of the indexed locations.
摘要翻译：多探针查找表包括每个可寻址位置的拥塞级别的指示。密钥可以存储在查找表中的多个索引位置之一中。基于已经存储在查找表中的密钥的分布，将密钥插入到查找表中来减少冲突。通过修改交换计数来记录共享索引位置的所有密钥的插入操作，指示每当将键插入其中一个索引位置时索引位置的拥塞级别。

10. 发明申请

US20030026259A1 Method and apparatus for a four-way hash table 有权
标题翻译：四向哈希表的方法和装置
公开(公告)号：US20030026259A1
公开(公告)日：2003-02-06
申请号：US10187472
申请日：2002-06-28
申请人： MOSAID Technologies, Inc.
发明人： David A. Brown
IPC分类号： H04L012/28
CPC分类号： H04L45/00 , H04L45/745
摘要： A number of hash tables are accessed concurrently with a different computed index based on a single search key for each hash table. Each index identifies a location in one of the hash tables capable of storing at least one entry. If all indexed locations are used, the entries stored in the lookup table can be reordered so that the new entry can be inserted in one of the locations identified by the computed indexes.
摘要翻译：基于每个哈希表的单个搜索关键字，使用不同的计算索引同时访问多个哈希表。每个索引标识能够存储至少一个条目的哈希表之一的位置。如果使用所有索引位置，则可以重新排序存储在查找表中的条目，以便可以将新条目插入由计算的索引标识的一个位置中。

你已经成功收藏专利！

检索式保存成功!

IPRDB

热门服务

关于我们

友情链接

联系方式