专利快速检索-快速检索全球专利，免费商用专利数据库-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. 发明申请

US20080123689A1 Oversubscription of guaranteed bandwidth 有权
标题翻译：过载保证带宽
公开(公告)号：US20080123689A1
公开(公告)日：2008-05-29
申请号：US11504208
申请日：2006-08-14
申请人： Eyal Oren , Doron Shoham , Dalit Sagi
发明人： Eyal Oren , Doron Shoham , Dalit Sagi
IPC分类号： H04J3/16
CPC分类号： H04L47/60 , H04L47/50 , H04L47/527 , H04L47/6225
摘要： A method for communication includes allocating target bandwidths to two or more packet sources and defining one or more of the packet sources as preferred sources. Quantum values defining maximum amounts of data to be sent during a single scheduling round are defined for the respective packet sources. Repetitive scheduling rounds are performed in order to determine a schedule for processing pending data packets produced by the packet sources. In each scheduling round, all pending packets that are produced by the preferred sources and are within the target bandwidths allocated to the preferred sources are scheduled. Pending packets produced by packet sources other than the preferred sources are scheduled in accordance with the quantum values, within the target bandwidths allocated to the packet sources other than the preferred sources. The pending packets are processed responsively to the schedule. The target bandwidths may comprise, for example, guaranteed bandwidths or excess bandwidths.
摘要翻译：一种用于通信的方法包括将目标带宽分配给两个或更多个分组源，并将一个或多个分组源定义为优选源。为相应的分组源定义定义在单个调度周期期间发送的最大数据量的量子值。执行重复调度循环以便确定用于处理由分组源产生的未决数据分组的调度。在每个调度循环中，调度由优选源产生并且在分配给优选源的目标带宽内的所有待处理分组。在分配给除了优选源之外的分组源的目标带宽内，根据量子值调度由除了优选源之外的分组源产生的等待分组。响应于时间表处理待处理的数据包。目标带宽可以包括例如保证带宽或超额带宽。

3. 发明授权

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

4. 发明授权

US07177276B1 Pipelined packet switching and queuing architecture 有权
标题翻译：流水线分组交换和排队架构
公开(公告)号：US07177276B1
公开(公告)日：2007-02-13
申请号：US10219462
申请日：2002-08-15
申请人： Garry P. Epps , Dalit Sagi
发明人： Garry P. Epps , Dalit Sagi
IPC分类号： G08C15/00 , H04J3/14 , H04L12/66 , H04L12/56
CPC分类号： H04L47/527 , H04L47/10 , H04L47/21 , H04L47/326 , H04L47/50 , H04L47/6215 , H04L49/1546 , H04L49/205 , H04L49/3009 , H04L49/3018 , H04L49/3063 , H04L49/50 , H04L49/552 , H04L49/602 , H04L49/90 , H04L49/9078
摘要： A pipelined linecard architecture for receiving, modifying, switching, buffering, queuing and dequeuing packets for transmission in a communications network. The linecard has two paths: the receive path, which carries packets into the switch device from the network, and the transmit path, which carries packets from the switch to the network. In the receive path, received packets are processed and switched in a multi-stage pipeline utilizing programmable data structures for fast table lookup and linked list traversal. The pipelined switch operates on several packets in parallel while determining each packet's routing destination. Once that determination is made, each packet is modified to contain new routing information as well as additional header data to help speed it through the switch. Using bandwidth management techniques, each packet is then buffered and enqueued for transmission over the switching fabric to the linecard attached to the proper destination port. The destination linecard may be the same physical linecard as that receiving the inbound packet or a different physical linecard. The transmit path includes a buffer/queuing circuit similar to that used in the receive path and can include another pipelined switch. Both enqueuing and dequeuing of packets is accomplished using CoS-based decision making apparatus, congestion avoidance, and bandwidth management hardware.
摘要翻译：用于接收，修改，切换，缓冲，排队和排队数据包以在通信网络中传输的流水线线卡架构。线路卡具有两条路径：从网络将数据包传送到交换机设备的接收路径，以及将交换机传送到网络的数据包的发送路径。在接收路径中，使用可编程数据结构在多级流水线中对接收到的数据包进行处理和切换，以便进行快速表查找和链表遍历。流水线交换机在确定每个数据包的路由目的地时并行操作多个数据包。一旦进行了确定，每个数据包被修改为包含新的路由信息以及额外的标题数据，以帮助通过交换机加速速度。使用带宽管理技术，每个数据包然后被缓冲并排入队列，以便通过交换结构传输到连接到适当目标端口的线卡。目的线路卡可能与接收入站分组或不同物理线卡一样的物理线卡。发送路径包括类似于在接收路径中使用的缓冲器/排队电路，并且可以包括另一流水线开关。使用基于CoS的决策设备，拥塞避免和带宽管理硬件来实现分组的入队和出队。

5. 发明授权

US06807187B1 Method and apparatus for determining a next round robin element using a cascaded approach 失效
标题翻译：使用级联方法确定下一个循环元件的方法和装置
公开(公告)号：US06807187B1
公开(公告)日：2004-10-19
申请号：US09676261
申请日：2000-09-28
申请人： Dalit Sagi
发明人： Dalit Sagi
IPC分类号： G06F1300
CPC分类号： H04L47/6225 , H04L47/50 , H04L47/58
摘要： Methods and apparatus are disclosed for determining a next round robin element requesting service using a cascaded approach. The cascaded approach could be implemented in numerous ways, including, inter alia, a circuit or in software, and be used, inter alia, in a network or computer system. In one implementation, a first stage of the cascaded implementation is divided into multiple groups, each of the multiple groups receives an indication of elements requesting service. Based on a last round robin result and its address, each of the multiple groups determines a candidate for the next result. In the situation where the last result was in a group and the group has a requesting element subsequent in the round robin sequence, that next requesting element is selected and forced to be the selected next result. Otherwise, this processing is repeated by subsequent stages to determine the round robin result. One implementation selects a next result from 4096 requesting inputs within a single clock period using three sixteen input cascaded stages.
摘要翻译：公开了用于使用级联方法确定下一个循环元素请求服务的方法和装置。级联方法可以以许多方式实现，包括电路或软件，尤其用于网络或计算机系统中。在一个实现中，级联实现的第一级划分为多个组，多个组中的每一个接收请求服务的元素的指示。基于最后一轮循环结果及其地址，多个组中的每一个确定下一个结果的候选。在最后一个结果在一个组中并且该组在循环序列中具有一个请求元素的情况下，该下一个请求元素被选择并被强制为所选择的下一个结果。否则，该处理在后续阶段重复以确定循环结果。一个实现使用三个十六个输入级联级在一个时钟周期内从4096个请求输入中选择下一个结果。

6. 发明授权

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

7. 发明授权

US07756037B2 Oversubscription of guaranteed bandwidth 有权
标题翻译：过载保证带宽
公开(公告)号：US07756037B2
公开(公告)日：2010-07-13
申请号：US11504208
申请日：2006-08-14
申请人： Eyal Oren , Doron Shoham , Dalit Sagi
发明人： Eyal Oren , Doron Shoham , Dalit Sagi
IPC分类号： H04L12/26
CPC分类号： H04L47/60 , H04L47/50 , H04L47/527 , H04L47/6225
摘要： A method for communication includes allocating target bandwidths to two or more packet sources and defining one or more of the packet sources as preferred sources. Quantum values defining maximum amounts of data to be sent during a single scheduling round are defined for the respective packet sources. Repetitive scheduling rounds are performed in order to determine a schedule for processing pending data packets produced by the packet sources. In each scheduling round, all pending packets that are produced by the preferred sources and are within the target bandwidths allocated to the preferred sources are scheduled. Pending packets produced by packet sources other than the preferred sources are scheduled in accordance with the quantum values, within the target bandwidths allocated to the packet sources other than the preferred sources. The pending packets are processed responsively to the schedule. The target bandwidths may comprise, for example, guaranteed bandwidths or excess bandwidths.
摘要翻译：一种用于通信的方法包括将目标带宽分配给两个或更多个分组源，并将一个或多个分组源定义为优选源。为相应的分组源定义定义在单个调度周期期间发送的最大数据量的量子值。执行重复调度循环以便确定用于处理由分组源产生的未决数据分组的调度。在每个调度循环中，调度由优选源产生并且在分配给优选源的目标带宽内的所有待处理分组。在分配给除了优选源之外的分组源的目标带宽内，根据量子值调度由除了优选源之外的分组源产生的等待分组。响应于时间表处理待处理的数据包。目标带宽可以包括例如保证带宽或超额带宽。

8. 发明授权

US07583678B1 Methods and apparatus for scheduling entities using a primary scheduling mechanism such as calendar scheduling filled in with entities from a secondary scheduling mechanism 有权
标题翻译：使用主调度机制调度实体的方法和装置，例如从辅助调度机制填充实体的日程表调度
公开(公告)号：US07583678B1
公开(公告)日：2009-09-01
申请号：US10260059
申请日：2002-09-27
申请人： Danny Levy , Dalit Sagi
发明人： Danny Levy , Dalit Sagi
IPC分类号： H04L12/56
CPC分类号： H04L47/527 , H04L47/50 , H04L47/522 , H04L47/568 , H04L47/60 , H04L47/6225 , H04L47/6255
摘要： Methods and apparatus are disclosed for scheduling entities in a system, such as, but not limited to a computer or communications system. Typically, calendar scheduling is used as a primary scheduling mechanism, with spare time allocated to a secondary scheduling mechanism. The secondary scheduling mechanism can use a round robin technique or variant thereof, or any other scheduling methodology. A calendar entry is examined to determine whether to process a calendar scheduled entity corresponding to the calendar entry or to process a secondary scheduled entity. Which scheduling entity to process is typically determined based on an eligibility of an entity corresponding to the primary scheduled event, a scheduling mechanism indicator, and/or an entity indicator. These combinations of scheduling mechanisms can be used to identify which packets to send, queues or ports to access, processes or threads to execute, or for any other purpose.
摘要翻译：公开了用于在系统中调度实体的方法和装置，诸如但不限于计算机或通信系统。通常，日历调度被用作主调度机制，其中空闲时间被分配给辅助调度机制。二次调度机制可以使用循环技术或其变体，或任何其他调度方法。检查日历条目以确定是否处理与日历条目相对应的日历预定实体或处理二次调度实体。要处理的调度实体通常基于与主调度事件对应的实体的资格，调度机制指示符和/或实体指示符来确定。这些调度机制的组合可用于识别要发送的分组，要访问的队列或端口，执行的进程或线程，或用于任何其他目的。

你已经成功收藏专利！

检索式保存成功!

IPRDB

热门服务

关于我们

友情链接

联系方式