公开(公告)号：US07515533B2

公开(公告)日：2009-04-07

申请号：US11006557

申请日：2004-12-08

Applicant: Jordan Lu ,  Robert Elliott Robotham

Inventor： Jordan Lu ,  Robert Elliott Robotham

IPC: H04L1/00

CPC classification number: H04L47/2441 ,  H04L47/24 ,  H04L47/50 ,  H04L47/56 ,  H04L47/568 ,  H04L47/623

Abstract: A system and method of scheduling and servicing events in a communications network are described. To provide improved efficiency while maintaining fairness to all traffic a two slot dynamic length Weighted Fair Queuing (WFQ) calendar is implemented. The two slot calendar can be transformed to provide fine granularity utilizing a hierarchical WFQ scheme.

Abstract translation: 描述了在通信网络中调度和维护事件的系统和方法。 为了提高效率，同时保持对所有业务的公平性，实施了两槽动态长度加权公平排队（WFQ）日历。 可以使用分层WFQ方案来转换两个时隙日历以提供精细的粒度。

公开(公告)号：US07477636B2

公开(公告)日：2009-01-13

申请号：US10722933

申请日：2003-11-26

Applicant: Asif Q. Khan ,  David B. Kramer ,  David P. Sonnier

Inventor： Asif Q. Khan ,  David B. Kramer ,  David P. Sonnier

IPC: H04B7/212

CPC classification number: H04L47/2441 ,  H04L47/22 ,  H04L47/50 ,  H04L47/522 ,  H04L47/568 ,  H04L47/58 ,  H04L2012/5679

Abstract: A processor includes a scheduler operative to schedule data blocks for transmission from a plurality of queues or other transmission elements, utilizing at least a first table and a second table. The first table may comprise at least first and second first-in first-out (FIFO) lists of entries corresponding to transmission elements for which data blocks are to be scheduled in accordance with a first scheduling algorithm, such as a weighted fair queuing scheduling algorithm. The scheduler maintains a first table pointer identifying at least one of the first and second lists of the first table as having priority over the other of the first and second lists of the first table. The second table includes a plurality of entries corresponding to transmission elements for which data blocks are to be scheduled in accordance with a second scheduling algorithm, such as a constant bit rate or variable bit rate scheduling algorithm.

Abstract translation: 处理器包括调度器，其利用至少第一表和第二表来调度用于从多个队列或其他传输元件传输的数据块。 第一表可以包括对应于根据第一调度算法（例如加权公平排队调度算法）对数据块进行调度的传输元件的条目的至少第一和第二先进先出（FIFO）列表 。 调度器维护第一表指针，其将第一表的第一列表和第二列表中的至少一个列表标识为优先于第一表的第一和第二列表中的另一列。 第二表包括对应于根据诸如恒定比特率或可变比特率调度算法的第二调度算法对其数据块进行调度的传输元件的多个条目。

公开(公告)号：US07475159B2

公开(公告)日：2009-01-06

申请号：US10670704

申请日：2003-09-25

Applicant: Lyle E. Grosbach ,  Glen H. Handlogten ,  James F. Mikos ,  David A. Norgaard

Inventor： Lyle E. Grosbach ,  Glen H. Handlogten ,  James F. Mikos ,  David A. Norgaard

IPC: G06F15/173 ,  G06F15/16

CPC classification number: H04L67/325 ,  H04L29/06 ,  H04L47/16 ,  H04L47/24 ,  H04L47/50 ,  H04L47/568 ,  H04L67/2819 ,  H04L69/329

Abstract: In a first aspect, a method is provided for scheduling connections for a network processor. The method includes the steps of, in a cache, scheduling a plurality of connections to be serviced based on quality of service parameters stored in a control structure corresponding to each connection and during a scheduling opportunity (1) identifying one or more of the plurality of connections in the cache to be serviced; (2) selecting one of the connections identified to be serviced; (3) servicing the selected connection; (4) accessing one or more portions of the control structure in the cache; (5) calculating a next service time when the selected connection is to be serviced; and (6) determining whether to schedule the selected connection to be serviced in one of the cache and a calendar based on the next service time. Numerous other aspects are provided.

Abstract translation: 在第一方面，提供了一种用于调度网络处理器的连接的方法。 该方法包括以下步骤：在高速缓存中，基于存储在与每个连接相对应的控制结构中的服务质量参数来调度要服务的多个连接，并且在调度机会（1）期间，识别多个 缓存中的连接要被服务; （2）选择被识别为被维护的连接之一; （3）维修所选择的连接; （4）访问高速缓存中的控制结构的一个或多个部分; （5）计算当所选择的连接被维护时的下一服务时间; 以及（6）基于下一个服务时间确定是否在所述高速缓存和日历中的一个中调度所选择的连接被服务。 提供了许多其他方面。

公开(公告)号：US07474662B2

公开(公告)日：2009-01-06

申请号：US11119329

申请日：2005-04-29

Applicant: Claude Basso ,  Jean Louis Calvignac ,  Chih-jen Chang ,  Natarajan Vaidhyanathan ,  Fabrice Jean Verplanken

Inventor： Claude Basso ,  Jean Louis Calvignac ,  Chih-jen Chang ,  Natarajan Vaidhyanathan ,  Fabrice Jean Verplanken

IPC: H04L12/56

CPC classification number: H04L47/623 ,  H04L47/50 ,  H04L47/568

Abstract: Systems and methods for scheduling data packets in a network processor are disclosed. Embodiments provide a network processor that comprises a best-effort scheduler with a minimal calendar structure for addressing schedule control blocks. In one embodiment, a four-entry calendar structure provides for rate-limited weighted best effort scheduling. Each of a plurality of different flows has associated schedule control blocks. Schedule control blocks are stored as linked lists in a last-in-first-out buffer. Each calendar entry is associated with a different linked list by storing in the calendar entry the address of the first-out schedule control block in the linked list. Each schedule control block has a counter and is assigned a rate limit according to the bandwidth priority of the flow to which the corresponding packet belongs. Each time a schedule control block is accessed from a last-in-first-out buffer storing the linked list, the scheduler generates a scheduling event and the counter of the schedule control block is incremented. When an incremented counter of a schedule control block equals its rate limit, the schedule control block is temporarily removed from further scheduling until a time interval concludes.

Abstract translation: 公开了一种用于在网络处理器中调度数据分组的系统和方法。 实施例提供了一种网络处理器，其包括具有用于寻址日程控制块的最小日历结构的尽力而为调度器。 在一个实施例中，四入口日历结构提供速率受限加权最佳努力调度。 多个不同流中的每一个都具有相关联的调度控制块。 计划控制块作为链表存储在先进先出缓冲区中。 通过在日历条目中存储链表中的先出时间表控制块的地址来将每个日历条目与不同的链表相关联。 每个调度控制块都有一个计数器，并根据相应数据包所属的流的带宽优先级分配速率限制。 每当从存储链表的最先进先出缓冲器访问调度控制块时，调度器生成调度事件，并且调度控制块的计数器递增。 当调度控制块的递增计数器等于其速率限制时，调度控制块暂时从进一步调度中移除，直到时间间隔结束。

公开(公告)号：US07426215B2

公开(公告)日：2008-09-16

申请号：US10819428

申请日：2004-04-06

Applicant: David Romano ,  Sanjeev Jain ,  Gilbert Wolrich ,  John Wishneusky

Inventor： David Romano ,  Sanjeev Jain ,  Gilbert Wolrich ,  John Wishneusky

IPC: H04L12/28

CPC classification number: H04L47/568 ,  H04L47/50 ,  H04L47/527

Abstract: A method and apparatus for scheduling packets using a pre-sort scheduling array having one or more smoothing registers. The scheduling array includes a number of round buffers, each round buffer having an associated smoothing register. To schedule a packet for transmission, the packet's transmission round and relative position within that round are determined, and an identifier for the packet is placed at the appropriate position within the scheduling array. A bit of the associated smoothing register is set, the set bit corresponding to the entry receiving the packet identifier. During transmission, the set bits of the smoothing register associated with a current round buffer are read to identify packets that are to be dequeued.

Abstract translation: 一种使用具有一个或多个平滑寄存器的预排序调度阵列来调度分组的方法和装置。 调度阵列包括多个循环缓冲器，每个循环缓冲器具有相关联的平滑寄存器。 为了调度分组进行传输，确定分组在该轮次内的传输轮和相对位置，并且将分组的标识符放置在调度阵列内的适当位置。 设置相关平滑寄存器的一位，该设置位对应于接收分组标识符的条目。 在传输期间，读取与当前循环缓冲器相关联的平滑寄存器的置位，以识别要出列的分组。

公开(公告)号：US07421522B1

公开(公告)日：2008-09-02

申请号：US11001745

申请日：2004-12-01

Applicant: Darren van Wageningen

Inventor： Darren van Wageningen

IPC: G06F3/00 ,  G06F5/00

CPC classification number: H04L49/90 ,  H04L47/50 ,  H04L47/568 ,  H04L49/901

Abstract: Techniques for transmitting and receiving FIFO status signals on a hard intellectual property (HIP) block of a programmable logic integrated circuit are provided. The FIFO status signals are demultiplexed after being received in the HIP block and then stored in a per port context. The FIFO status signals are retrieved from a storage block in a per port context and transmitted out of the HIP block through a multiplexer. The demultiplexing and multiplexing reduces the number of input and output ports that are needed to transmit the status signals into and out of the HIP block, yet providing the necessary status throughput for a full-rate SPI4.2 status channel implementation.

Abstract translation: 提供了在可编程逻辑集成电路的硬知识产权（HIP）块上发送和接收FIFO状态信号的技术。 FIFO状态信号在HIP块中被接收后被解复用，然后存储在每个端口上下文中。 FIFO状态信号从每个端口上下文的存储块检索，并通过多路复用器从HIP块传出。 解复用和复用减少了将状态信号传入和传出HIP块所需的输入和输出端口的数量，同时为全速率SPI4.2状态信道实现提供必要的状态吞吐量。

公开(公告)号：US07385987B1

公开(公告)日：2008-06-10

申请号：US10357878

申请日：2003-02-04

Applicant: Anna Charny ,  Robert Olsen

Inventor： Anna Charny ,  Robert Olsen

IPC: H04L12/56 ,  H04J3/22

CPC classification number: H04L47/568 ,  H04L47/50 ,  H04L47/525 ,  H04L47/60

Abstract: A scheduling method for a multi-level class hierarchy includes inserting all queues containing at least one packet in a first scheduler and inserting into a second scheduler queues contained in the first scheduler which do not exceed their maximum rate. The first scheduler is dequeued until a queue exceeding a maximum rate of the queue is reached, at which time a queue of the second scheduler is dequeued.

Abstract translation: 用于多级类层次的调度方法包括将包含至少一个分组的所有队列插入到第一调度器中并插入到不超过其最大速率的第一调度器中包含的第二调度器队列中。 第一个调度程序出队，直到达到超过队列的最大速率的队列，此时第二个调度程序的队列出队。

公开(公告)号：US07103051B2

公开(公告)日：2006-09-05

申请号：US10002416

申请日：2001-11-01

Applicant: William John Goetzinger ,  Glen Howard Handlogten ,  James Francis Mikos ,  David Alan Norgaard

Inventor： William John Goetzinger ,  Glen Howard Handlogten ,  James Francis Mikos ,  David Alan Norgaard

IPC: H04L12/56

CPC classification number: H04L47/28 ,  H04L12/64 ,  H04L47/24 ,  H04L47/50 ,  H04L47/521 ,  H04L47/525 ,  H04L47/564 ,  H04L47/568

Abstract: A scheduler, scheduling method, and computer program product are provided for implementing Quality-of-Service (QoS) scheduling of a plurality of flows with aging time stamps. Subsets of time stamp data stored in a time stamp aging memory array are sequentially accessed. Each time stamp data subset contains time stamp data for a subplurality of flows. Guaranteed aging processing steps are performed for each flow utilizing the time stamp data subsets to identify and mark invalid calendar next time values. When a new frame arrival for an empty flow is identified, flow queue control block (FQCB) time stamp data and the flow time stamp data in the time stamp aging memory array are accessed. Based on the calendar to which the new frame is directed or the target calendar for the new frame, the target calendar next time valid bit of the time stamp aging memory array data is checked. When the target calendar next time valid bit is on, a target calendar next time value from the flow queue control block (FQCB) time stamp data is compared with a current time. When the target calendar next time is less than the current time, the target calendar next time valid bit is turned off to mark the target calendar next time as invalid. The guaranteed aging processing steps for each flow in the time stamp data subset includes checking a selection indicator of the time stamp aging memory array data for the flow to identify a calendar. Responsive to the selection indicator value, a calendar valid bit is checked. When the calendar valid bit is on, a calendar next time is compared with a current time. When the calendar next time is less than the current time, the calendar valid bit is turned off to mark the calendar next time as invalid. Invalid time stamp values are identified for all scheduler calendars.

公开(公告)号：US20060120380A1

公开(公告)日：2006-06-08

申请号：US11006557

申请日：2004-12-08

Applicant: Jordan Lu ,  Robert Robotham

Inventor： Jordan Lu ,  Robert Robotham

IPC: H04L12/56 ,  H04L12/28

CPC classification number: H04L47/2441 ,  H04L47/24 ,  H04L47/50 ,  H04L47/56 ,  H04L47/568 ,  H04L47/623

Abstract: A system and method of scheduling and servicing events in a communications network are described. To provide improved efficiency while maintaining fairness to all traffic a two slot dynamic length Weighted Fair Queuing (WFQ) calendar is implemented. The two slot calendar can transformed to provide fine granularity utilizing a hierarchical WFQ scheme.

Abstract translation: 描述了在通信网络中调度和维护事件的系统和方法。 为了提高效率，同时保持对所有业务的公平性，实施了两槽动态长度加权公平排队（WFQ）日历。 可以使用分层WFQ方案来转换两个时隙日历以提供精细的粒度。

公开(公告)号：US07020133B2

公开(公告)日：2006-03-28

申请号：US10037433

申请日：2002-01-03

Applicant: Yongdong Zhao ,  Craig A. Lindahl

Inventor： Yongdong Zhao ,  Craig A. Lindahl

IPC: H04L12/56

CPC classification number: H04L47/623 ,  H04L47/568 ,  H04L47/6215 ,  H04L49/205 ,  H04L49/252 ,  H04L49/30 ,  H04L49/3009 ,  H04L49/3018 ,  H04L49/3027 ,  H04L49/90 ,  H04L49/9036

Abstract: A switch queue predictive protocol (SQPP) includes a packet switching system including: a switch fabric having a cross-point switch, and a plurality of line cards, each coupled to the switch fabric. A cross-point buffer is located at each cross-point of the cross-point switch. The switch fabric also includes a plurality of actual available queue space tables (AAQSTs), each identifying the actual queue space available in a row of the cross-point buffers. Each of the line cards includes an input buffer, an output buffer, and a predicted available queue space table (PAQST) identifying predicted queue space available in a corresponding row of the cross-point buffers. Packet information is transmitted from a source line card to the switch fabric only if available queue space is predicted by the corresponding PAQST. The switch fabric uses the AAQST to update the PAQST after packet information is transmitted to a destination line card.