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

1. 发明申请

US20090125535A1 STRUCTURE FOR DELETING LEAVES IN TREE TABLE STRUCTURES 失效
标题翻译：树木结构中的叶片结构
公开(公告)号：US20090125535A1
公开(公告)日：2009-05-14
申请号：US12350493
申请日：2009-01-08
申请人： Claude Basso , Jean L. Calvignac , Gordon T. Davis , Marco Heddes , Piyush C. Patel , Steven R. Perrin , Grayson W. Randall , Sonia K. Rovner
发明人： Claude Basso , Jean L. Calvignac , Gordon T. Davis , Marco Heddes , Piyush C. Patel , Steven R. Perrin , Grayson W. Randall , Sonia K. Rovner
IPC分类号： G06F17/30
CPC分类号： G06F17/30625 , Y10S707/99936 , Y10S707/99942 , Y10S707/99943
摘要： Techniques and articles of manufacture are provided comprising computer readable programs that, when executed on the computer, cause the computer to delete a leaf from a Patricia tree having a direct table and a plurality of PSCB's which decode portions of the pattern of a leaf in the tree without shutting down the functioning of the tree. A leaf having a pattern is identified as a leaf to be deleted. Using the pattern, the tree is walked to identify the location of the leaf to be deleted. The leaf to be deleted is identified and deleted, and any relevant PSCB modified, if necessary. The technique also is applicable to deleting a prefix of a prefix.
摘要翻译：提供了技术和制造物品，其包括计算机可读程序，当在计算机上执行时，计算机可以使计算机从具有直接表的帕特里夏树中删除叶片，并且多个PSCB解码部分叶片的图案树，而不关闭树的功能。具有图案的叶被识别为要被删除的叶。使用图案，树被移动以识别要删除的叶子的位置。要删除的叶被识别和删除，并且必要时修改任何相关的PSCB。该技术也适用于删除前缀的前缀。

2. 发明授权

US07490101B2 Method and structure for deleting leaves in tree table structures 失效
标题翻译：在树表结构中删除树叶的方法和结构
公开(公告)号：US07490101B2
公开(公告)日：2009-02-10
申请号：US11462404
申请日：2006-08-04
申请人： Claude Basso , Jean L. Calvignac , Gordon T. Davis , Marco Heddes , Piyush C. Patel , Steven R. Perrin , Grayson W. Randall , Sonia K. Rovner
发明人： Claude Basso , Jean L. Calvignac , Gordon T. Davis , Marco Heddes , Piyush C. Patel , Steven R. Perrin , Grayson W. Randall , Sonia K. Rovner
IPC分类号： G06F7/00 , G06F17/00 , G06F17/30
CPC分类号： G06F17/30625 , Y10S707/99936 , Y10S707/99942 , Y10S707/99943
摘要： A technique is provided to delete a leaf from a Patricia tree having a direct table and a plurality of PSCB's which decode portions of the pattern of a leaf in the tree without shutting down the functioning of the tree. A leaf having a pattern is identified as a leaf to be deleted. Using the pattern, the tree is walked to identify the location of the leaf to be deleted. The leaf to be deleted is identified and deleted, and any relevant PSCB modified, if necessary. The technique also is applicable to deleting a prefix of a prefix.
摘要翻译：提供一种技术来从具有直接表的帕特里夏树和多个PSCB中删除叶，该PSCB解码树中的叶的图案的部分，而不关闭树的功能。具有图案的叶被识别为要被删除的叶。使用图案，树被移动以识别要删除的叶子的位置。要删除的叶被识别和删除，并且必要时修改任何相关的PSCB。该技术也适用于删除前缀的前缀。

3. 发明授权

US07149749B2 Method of inserting and deleting leaves in tree table structures 失效
标题翻译：在树表结构中插入和删除叶子的方法
公开(公告)号：US07149749B2
公开(公告)日：2006-12-12
申请号：US10453245
申请日：2003-06-03
申请人： Claude Basso , Jean L. Calvignac , Gordon T. Davis , Marco Heddes , Piyush C. Patel , Steven R. Perrin , Grayson W. Randall , Sonia K. Rovner
发明人： Claude Basso , Jean L. Calvignac , Gordon T. Davis , Marco Heddes , Piyush C. Patel , Steven R. Perrin , Grayson W. Randall , Sonia K. Rovner
IPC分类号： G06F17/30
CPC分类号： G06F17/30625 , Y10S707/99936 , Y10S707/99942 , Y10S707/99943
摘要： A technique is provided to either insert or delete a leaf in a Patricia tree having a direct table and a plurality of PSCB's which decode portions of the pattern of a leaf in the tree without shutting down the functioning of the tree. A leaf having a pattern is identified as either a leaf to be inserted or deleted. Using the pattern, the tree is walked once to identify the location of the leaf to be deleted or the location where the leaf is to be inserted. If it is a delete operation, the leaf to be deleted is identified and deleted, and any relevant PSCB modified, if necessary. If it is an insert operation, the tree is walked a second time to insert the leaf and reform or create any PSCB in the chain that needs to be reformed or created. The technique also is applicable to inserting or deleting a prefix of a prefix.
摘要翻译：提供了一种技术来插入或删除具有直接表的Patricia树中的叶子，以及多个PSCB，其解码树中的叶子的图案的部分，而不关闭树的功能。具有图案的叶被识别为要插入或删除的叶。使用图案，树一次走一次，以确定要删除的叶的位置或叶被插入的位置。如果是删除操作，则要删除的叶被识别和删除，并且必要时修改任何相关的PSCB。如果是插入操作，则树第二次移动以插入叶，并在需要重新创建或创建的链中重新构建或创建任何PSCB。该技术也适用于插入或删除前缀的前缀。

4. 发明授权

US06963868B2 Multi-bit Patricia trees 失效
标题翻译：多比特Patricia树
公开(公告)号：US06963868B2
公开(公告)日：2005-11-08
申请号：US10448528
申请日：2003-05-30
申请人： Claude Basso , Jean L. Calvignac , Gordon T. Davis , Marco Heddes , Piyush C. Patel , Steven R. Perrin , Grayson W. Randall
发明人： Claude Basso , Jean L. Calvignac , Gordon T. Davis , Marco Heddes , Piyush C. Patel , Steven R. Perrin , Grayson W. Randall
IPC分类号： G06F7/00 , G06F17/30
CPC分类号： H04L45/00 , H04L45/56 , H04L45/7457 , Y10S707/99933
摘要： A tree structure and method to organize routing information for processing messages within a network, each message being associated with a search key of “n” bits. The processing determines where to send the message next. The structure has a direct table (DT) of 2x entries for decoding the first “x” bits of the search key, and one or more pattern search control blocks (PSCB's), each having 2m entries for decoding subsequent groups of “m” bits. Each PSCB entry and DT entry includes a pointer to data associated with a specific route, if at this point a specific routing table entry is a potential match to the search key or a pointer to a subsequent PSCB if the end of a search trail is not identified. Each PSCB entry DT entry also indicates that the search has been resolved to the end of the search trail.
摘要翻译：一种用于组织用于处理网络内的消息的路由信息的树结构和方法，每个消息与“n”比特的搜索关键字相关联。该处理确定接下来发送消息的位置。该结构具有用于对搜索关键字的第一个“x”比特进行解码的2个“<”条目的直接表（DT），以及一个或多个模式搜索控制块（PSCB），每个具有2个

5. 发明授权

US08135752B2 Deleting leaves in tree table structures 失效
标题翻译：删除树表结构中的树叶
公开(公告)号：US08135752B2
公开(公告)日：2012-03-13
申请号：US12350493
申请日：2009-01-08
申请人： Claude Basso , Jean L. Calvignac , Gordon T. Davis , Marco Heddes , Piyush C. Patel , Steven R. Perrin , Grayson W. Randall , Sonia K. Rovner
发明人： Claude Basso , Jean L. Calvignac , Gordon T. Davis , Marco Heddes , Piyush C. Patel , Steven R. Perrin , Grayson W. Randall , Sonia K. Rovner
IPC分类号： G06F7/00 , G06F17/00 , G06F17/30
CPC分类号： G06F17/30625 , Y10S707/99936 , Y10S707/99942 , Y10S707/99943
摘要： Techniques and articles of manufacture are provided comprising computer readable programs that, when executed on the computer, cause the computer to delete a leaf from a patricia tree having leaf keys and pattern search control blocks containing a prefix and either an end-of-trail leaf or a pointer to another of the pattern search control blocks, by placing each of the prefixes in a tree prefix table; searching for a key in the tree; searching for the key in the prefix table if the tree searching does not find the key in the tree; confirming that the key is deleted if the key is not found in the prefix table; deleting the key from one of the pattern search control blocks; and collapsing the patricia tree by eliminating the left most pattern search control block from the patricia tree if the patricia tree searching finds the key.
摘要翻译：提供的技术和制品包括计算机可读程序，当在计算机上执行计算机可读程序时，使计算机从具有叶键的图案搜索控制块和包含前缀的叶片的叶片中删除叶或指向另一个模式搜索控制块的指针，通过将每个前缀放置在树前缀表中; 在树中搜索一个键; 如果树搜索没有在树中找到密钥，则在前缀表中搜索密钥; 如果在前缀表中没有找到密钥，则确认该密钥被删除; 从模式搜索控制块之一删除密钥; 并且如果所述爱好者树搜索找到所述密钥，则通过从所述爱好树中消除所述最左图案搜索控制块来折叠所述爱好者树。

6. 发明授权

US07089240B2 Longest prefix match lookup using hash function 失效
公开(公告)号：US07089240B2
公开(公告)日：2006-08-08
申请号：US10879964
申请日：2004-06-29
申请人： Claude Basso , Jean L. Calvignac , Gordon T. Davis , Piyush C. Patel
发明人： Claude Basso , Jean L. Calvignac , Gordon T. Davis , Piyush C. Patel
IPC分类号： G06F17/30
CPC分类号： H04L45/00 , G06F17/30985 , H04L12/66 , H04L45/745 , H04L45/7457 , Y10S707/99933 , Y10S707/99935 , Y10S707/99936
摘要： A method and apparatus are used for finding the longest prefix match in a variable length prefix search when searching a direct table within a routing table structure of a network processor. The search through the routing table structure is expedited by hashing a first segment of an internet protocol address with a virtual private network number followed by concatenating the unhashed bits of the IP address to the result of the hash operation to form an input key. Patterns are compared a bit at a time until an exact match or the best match is found. The search is conducted in a search tree that provides that the matching results will be the best possible match.

7. 发明授权

US07702630B2 Longest prefix match lookup using hash function 失效
标题翻译：使用哈希函数的最长前缀匹配查找
公开(公告)号：US07702630B2
公开(公告)日：2010-04-20
申请号：US11353841
申请日：2006-02-14
申请人： Claude Basso , Jean L. Calvignac , Gordon T. Davis , Piyush C. Patel
发明人： Claude Basso , Jean L. Calvignac , Gordon T. Davis , Piyush C. Patel
IPC分类号： G06F7/00
CPC分类号： H04L45/00 , G06F17/30985 , H04L12/66 , H04L45/745 , H04L45/7457 , Y10S707/99933 , Y10S707/99935 , Y10S707/99936
摘要： A method and apparatus are used for finding the longest prefix match in a variable length prefix search when searching a direct table within a routing table structure of a network processor. The search through the routing table structure is expedited by hashing a first segment of an internet protocol address with a virtual private network number followed by concatenating the unhashed bits of the IP address to the result of the hash operation to form an input key. Patterns are compared a bit at a time until an exact match or the best match is found. The search is conducted in a search tree that provides that the matching results will be the best possible match.
摘要翻译：当在网络处理器的路由表结构中搜索直接表时，使用方法和装置来在可变长度前缀搜索中找到最长的前缀匹配。通过路由表结构的搜索是通过用互联网协议地址的第一段与虚拟专用网络号进行散列加速，然后将IP地址的未分配比特连接到散列操作的结果以形成输入密钥。模式一次比较一点，直到找到完全匹配或最佳匹配。搜索在搜索树中进行，其提供匹配结果将是最佳匹配。

8. 发明授权

US07929438B2 Scheduler pipeline design for hierarchical link sharing 失效
标题翻译：调度器管道设计用于分层链路共享
公开(公告)号：US07929438B2
公开(公告)日：2011-04-19
申请号：US12175479
申请日：2008-07-18
申请人： Claude Basso , Jean L. Calvignac , Chih-jen Chang , Gordon T. Davis , Fabrice J. Verplanken
发明人： Claude Basso , Jean L. Calvignac , Chih-jen Chang , Gordon T. Davis , Fabrice J. Verplanken
IPC分类号： H04J1/16
CPC分类号： H04L47/60 , H04L47/15 , H04L47/50 , H04L47/52 , H04L49/90
摘要： A pipeline configuration is described for use in network traffic management for the hardware scheduling of events arranged in a hierarchical linkage. The configuration reduces costs by minimizing the use of external SRAM memory devices. This results in some external memory devices being shared by different types of control blocks, such as flow queue control blocks, frame control blocks and hierarchy control blocks. Both SRAM and DRAM memory devices are used, depending on the content of the control block (Read-Modify-Write or ‘read’ only) at enqueue and dequeue, or Read-Modify-Write solely at dequeue. The scheduler utilizes time-based calendars and weighted fair queueing calendars in the egress calendar design. Control blocks that are accessed infrequently are stored in DRAM memory while those accessed frequently are stored in SRAM.
摘要翻译：描述了用于网络流量管理中的流水线配置，用于以分层链接排列的事件的硬件调度。该配置通过最小化外部SRAM存储器件的使用来降低成本。这导致一些外部存储器设备被不同类型的控制块共享，例如流队列控制块，帧控制块和层次控制块。使用SRAM和DRAM存储器件，这取决于控制块的内容（仅读取 - 修改 - 写入或仅读取）在排队和出队，或仅读出 - 修改 - 写出。调度器在出口日历设计中使用基于时间的日历和加权公平排队日历。不频繁访问的控制块存储在DRAM存储器中，而频繁访问的控制块存储在SRAM中。

9. 发明授权

US07457241B2 Structure for scheduler pipeline design for hierarchical link sharing 失效
标题翻译：用于分层链路共享的调度器流水线设计的结构
公开(公告)号：US07457241B2
公开(公告)日：2008-11-25
申请号：US10772737
申请日：2004-02-05
申请人： Claude Basso , Jean L. Calvignac , Chih-jen Chang , Gordon T. Davis , Fabrice J. Verplanken
发明人： Claude Basso , Jean L. Calvignac , Chih-jen Chang , Gordon T. Davis , Fabrice J. Verplanken
IPC分类号： H04J1/16
CPC分类号： H04L47/60 , H04L47/15 , H04L47/50 , H04L47/52 , H04L49/90
摘要： A pipeline configuration is described for use in network traffic management for the hardware scheduling of events arranged in a hierarchical linkage. The configuration reduces costs by minimizing the use of external SRAM memory devices. This results in some external memory devices being shared by different types of control blocks, such as flow queue control blocks, frame control blocks and hierarchy control blocks. Both SRAM and DRAM memory devices are used, depending on the content of the control block (Read-Modify-Write or ‘read’ only) at enqueue and dequeue, or Read-Modify-Write solely at dequeue. The scheduler utilizes time-based calendars and weighted fair queueing calendars in the egress calendar design. Control blocks that are accessed infrequently are stored in DRAM memory while those accessed frequently are stored in SRAM.
摘要翻译：描述了用于网络流量管理中的流水线配置，用于以分层链接排列的事件的硬件调度。该配置通过最小化外部SRAM存储器件的使用来降低成本。这导致一些外部存储器设备被不同类型的控制块共享，例如流队列控制块，帧控制块和层次控制块。使用SRAM和DRAM存储器件，这取决于控制块的内容（仅读取 - 修改 - 写入或仅读取）在排队和出队，或仅读出 - 修改 - 写出。调度器在出口日历设计中使用基于时间的日历和加权公平排队日历。不频繁访问的控制块存储在DRAM存储器中，而频繁访问的控制块存储在SRAM中。

10. 发明授权

US07406080B2 Method and structure for enqueuing data packets for processing 失效
标题翻译：排队处理数据包的方法和结构
公开(公告)号：US07406080B2
公开(公告)日：2008-07-29
申请号：US10868725
申请日：2004-06-15
申请人： Claude Basso , Jean L. Calvignac , Chih-jen Chang , Gordon T. Davis , Fabrice J. Verplanken
发明人： Claude Basso , Jean L. Calvignac , Chih-jen Chang , Gordon T. Davis , Fabrice J. Verplanken
IPC分类号： H04L12/56
CPC分类号： H04L49/90 , H04L49/9042 , H04L49/9073 , H04L69/22
摘要： A method and structure is provided for buffering data packets having a header and a remainder in a network processor system. The network processor system has a processor on a chip and at least one buffer on the chip. Each buffer on the chip is configured to buffer the header of the packets in a preselected order before execution in the processor, and the remainder of the packet is stored in an external buffer apart from the chip. The method comprises utilizing the header information to identify the location and extent of the remainder of the packet. The entire selected packet is stored in the external buffer when the buffer of the stored header of the given packet is full, and moving only the header of a selected packet stored in the external buffer to the buffer on the chip when the buffer on the chip has space therefor.
摘要翻译：提供了一种在网络处理器系统中缓冲具有报头和余数的数据分组的方法和结构。网络处理器系统在芯片上具有处理器和芯片上的至少一个缓冲器。芯片上的每个缓冲器被配置为在处理器中执行之前以预先选择的顺序缓冲数据包的报头，并且数据包的剩余部分存储在与芯片分离的外部缓冲器中。该方法包括利用报头信息来识别分组的其余部分的位置和范围。当给定分组的存储报头的缓冲器已满时，整个所选分组被存储在外部缓冲器中，并且当芯片上的缓冲器仅将存储在外部缓冲器中的选定分组的报头移动到芯片上的缓冲器时有空间。

你已经成功收藏专利！

检索式保存成功!

IPRDB

热门服务

关于我们

友情链接

联系方式