CN118784593A - Multi-level scheduler - Google Patents

Abstract

Embodiments of the present disclosure relate to a multi-level scheduler. Packet metadata for incoming packets is buffered in a queue selection buffer associated with a port of the network node. Packet data for outgoing packets is buffered in a port selection buffer associated with the port. At the selection clock period, when the port scheduler of the network node selects a subset of the subset packet data for the outgoing packet from the port selection buffer, the queue scheduler of the port simultaneously selects a subset of the packet metadata for the subset of the incoming packet from the queue selection buffer and adds new packet data of the new outgoing packet to the port selection buffer of the port. New packet data is derived based at least in part on the subset of packet metadata for the subset of incoming packets.

Description

Multi-level scheduler

CROSS-REFERENCE TO RELATED APPLICATIONS

This application claims priority to U.S. Provisional Patent Application No. 63/457,122 filed on April 4, 2023, which is incorporated herein by reference.

Technical Field

Embodiments relate generally to packet delivery, and more particularly to multi-level schedulers.

Background Art

The approaches described in this section are approaches that could be pursued, but are not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated, it should not be assumed that any of the approaches described in this section qualify as prior art merely by virtue of their inclusion in this section.

For data communication networks or switching devices used in various computer applications, minimizing the delay of next hop and end-to-end packet delivery is usually a very important goal. As more and more high-capacity switching devices are deployed in the field, the time budget that different processing components present in the packet delivery path can be used to process more and more packets becomes shorter and shorter. As a result, some or all processing components including but not limited to network interfaces or ports may spend a lot of time idle waiting for packets to arrive. Although these network interfaces or ports may have high packet delivery capabilities or bandwidths in nominal or theoretical terms, many of such high capabilities or bandwidths may still be wasted. For example, when the upstream processing components cannot process and transmit a sufficient number of packets to these network interfaces or ports in a timely manner for packet delivery, the network interfaces or ports may be idle for a long time.

Summary of the invention

According to one or more embodiments of the present disclosure, a method is disclosed, comprising: buffering multiple packet metadata sets for multiple incoming packets in multiple queue selection buffers associated with a port of a network node; buffering one or more packet metadata sets for one or more outgoing packets in a port selection buffer associated with the port; in a selection clock cycle, when a subset of the one or more packet metadata sets for a subset of the one or more outgoing packets is selected from the port selection buffer by a port scheduler of the network node, the queue scheduler of the port simultaneously executes for multiple packet queues set for the port: selecting one or more second packet metadata sets for one or more incoming packets among the multiple incoming packets from the multiple packet metadata sets stored in the multiple queue selection buffers; and adding the one or more second packet metadata sets for one or more second outgoing packets to the port selection buffer of the port.

According to one or more embodiments of the present disclosure, a system is disclosed, comprising: one or more computing devices; one or more non-transitory computer-readable media storing instructions, which, when executed by the one or more computing devices, cause the following execution: buffering multiple packet metadata sets for multiple incoming packets in multiple queue selection buffers associated with a port of a network node; buffering one or more packet metadata sets for one or more outgoing packets in a port selection buffer associated with the port; in a selection clock cycle, when a subset of the one or more packet metadata sets for a subset of the one or more outgoing packets is selected from the port selection buffer by a port scheduler of the network node, the queue scheduler of the port simultaneously executes for multiple packet queues set for the port: selecting one or more second packet metadata sets for one or more incoming packets among the multiple incoming packets from the multiple packet metadata sets stored in the multiple queue selection buffers; and adding the one or more second packet metadata sets for one or more second outgoing packets to the port selection buffer of the port.

According to one or more embodiments of the present disclosure, one or more non-transitory computer-readable media are disclosed, storing instructions, which, when executed by one or more computing devices, cause the following execution: buffering multiple packet metadata sets for multiple incoming packets in multiple queue selection buffers associated with a port of a network node; buffering one or more packet metadata sets for one or more outgoing packets in a port selection buffer associated with the port; in a selection clock cycle, when a subset of the one or more packet metadata sets for a subset of the one or more outgoing packets is selected from the port selection buffer by a port scheduler of the network node, the queue scheduler of the port simultaneously executes for multiple packet queues set for the port: selecting one or more second packet metadata sets for one or more incoming packets among the multiple incoming packets from the multiple packet metadata sets stored in the multiple queue selection buffers; and adding the one or more second packet metadata sets for one or more second outgoing packets to the port selection buffer of the port.

BRIEF DESCRIPTION OF THE DRAWINGS

The subject matter of the invention is illustrated by way of example and not limitation in the figures of the accompanying drawings in which like references refer to similar elements, and in which:

FIG1 illustrates an example networked system;

FIG2 illustrates an example network device;

FIG. 3A illustrates an example multi-stage scheduler; FIG. 3B illustrates an example data flow; FIGS. 3C and 3D illustrate example operations of queue and port schedulers;

FIG4 illustrates an example port bundle scheduling operation;

FIG5 illustrates an example process flow;

6 is a block diagram of an example computer system.

DETAILED DESCRIPTION

In the following description, for the purpose of explanation, many specific details are set forth in order to provide a thorough understanding of the subject matter of the present invention. However, it will be apparent that the subject matter of the present invention can be practiced without these specific details. In other examples, well-known structures and devices are shown in block diagram form to avoid unnecessarily obscuring the subject matter of the present invention.

Embodiments are described herein according to the following points:

1.0. General Overview

2.0. Structural Overview

2.1. Data Unit

2.2. Network Path

2.3. Network equipment

2.4.Port

2.5. Packet Processor

2.6. Buffer

2.7. Queues

Traffic Management

2.9. Forwarding Logic

2.10. Multi-level scheduler

2.11. Others

3.0. Functional Overview

3.1. Port and Queue Scheduling

3.2. Port or queue qualified

3.3. Work Savings

3.4. Queue selection data flow

3.5. Queue Status

3.6. Queue Selection Strategy

3.7. Select Operation

3.8. Port Bundle Scheduling

4.0. Example Embodiments

5.0. Implementation Mechanism - Hardware Overview

6.0. Extensions and alternatives

1.0. General Overview

As the transmission or transfer rates of packets between different network nodes or switches and between different packet processing components within a network node or switch become higher and higher, the time between the arrival of a packet and the transmission/transfer of the packet becomes less and less.

The techniques described herein may be implemented or applied to keep ports in active packet transmission or delivery states without starvation. As part of a multi-stage scheduler, a port selection buffer may be set for one (e.g., each, etc.) port, and one or more queue selection buffers may be set for one or more queues of the port.

The port scheduler of the multi-level scheduler may perform a port scheduling operation that arbitrates access to bandwidth or port rates (e.g., egress, etc.) across (e.g., eligible) ports, and the (e.g., each, etc.) per-port queue scheduler for a port in the multi-level scheduler may perform a queue scheduling operation that arbitrates access to bandwidth or port rates (e.g., egress, etc.) across (e.g., eligible) port queues. The same or different eligibility factors, or one or more combinations thereof, may be used to determine whether a given port or queue among the ports or queues is eligible for selection or dequeuing by the port or queue scheduler from the port or queue selection buffer.

The port scheduling operation and queue scheduling operation of respectively parsing the port state of the port and the queue state of the queue associated with the port can be decoupled or deserialized from each other in a separate timing loop. These port scheduling operations and queue scheduling operations can also be decoupled or deserialized from the separate operation of transmitting or transmitting the grouping selected from the queue associated with the port.

Because the operation and timing loop of the port scheduler or port scheduling operation are decoupled from the operation and timing loop of the queue scheduler or queue scheduling operation, instead of picking up or selecting packets for transmission or transmission directly from the qualified queue associated with the port, the port scheduler or port transmission logic can pick up or select packets for qualified ports from the port selection buffer. The port selection buffer can store or buffer a packet data set of packets so that these packets can be transmitted or transmitted without or with almost no time delay. In other words, the packet data set buffered and/or selected from the port selection buffer can be specifically defined, generated, sized or composed to facilitate transmission or transmission operations at relatively high speeds and minimized delays.

Although the port has a port scheduler that performs port scheduling operations, the queues of the port have separate queue schedulers that perform queue scheduling operations in separate timing loops. Each of the one or more queues of the port has or is assigned a separate (per queue) queue selection buffer in which the queue state of the queue can be maintained, maintained or updated.

The queue selection buffer of the queue may store in the queue selection buffer entry of the packet a plurality of (e.g., relatively small data size, 50 bits, etc.) sets of packet metadata representing the queue selection buffer - or cells/transmissions divided from the packet. The packet metadata may include, but is not limited to: packet/cell control information that may be used by the queue scheduler to facilitate or control packet/cell selection operations, packet/cell copy operations, packet/cell enqueue operations to the corresponding port selection buffer, etc. The port selection buffer and the queue selection buffer may contain only packet metadata. For example, the packet metadata may be stored in the queue selection buffer (or per-queue buffer) and then transmitted to the port selection buffer upon selection. Packet metadata from one or more queue buffer entries or elements may be transmitted upon selection of a queue or a corresponding per-queue buffer. Similarly, packet metadata from one or more port buffer entries or elements may be selected upon selection of a port or port selection buffer. In some operational scenarios, the packet metadata set of the packet in the associated port or queue selection buffer may have a relatively small data size compared to the packet data or packet payload of the packet in the port selection buffer.

The queue scheduler can use queue status and relatively small data size packet metadata sets to easily make eligible queue selections in the port's queue with no or almost no time delay and no or almost no additional operations; generate (one or more) packet metadata sets for the selected (one or more) packets, and place (one or more) packet data sets including but not limited to (e.g., additional, etc.) port transmission control information into the port selection buffer of the port.

At the same time, in a separate timing loop, the port scheduler can independently and simultaneously pick up or select eligible (ready to send packets) ports, and use one or more specific packet data sets or specific port transmission control information retrieved from the port selection buffer of the eligible ports to access or determine (e.g., all, etc.) packet data to be transmitted or transmitted for packet sending (e.g., transmission or transmission, etc.).

Control information such as queue states stored in a queue selection buffer can be used to select packets/cells or corresponding queue selection buffer entries from the queue selection buffer. The queue state may include but is not necessarily limited to some or all of the following: an empty state, some or all of the empty state at pickup time, and an EOP state at the end or pickup of a packet, etc. The queue state in the queue selection buffer can be used by the queue scheduler for the next queue selection cycle. How many selections are made to dequeue a packet can be based on the cell or transmission count of the packet. Additionally, optionally or alternatively, a packet can be dequeued multiple times based on a packet copy count of the packet. The queue selection as described herein can dequeue a single cell of a packet, multiple cells of one or more packets, a single packet copy, multiple packet copies, multiple packets/cells represented in multiple queues, etc.

In some operation scenarios, a port or queue selection buffer may be implemented as a FIFO. For example, the first N packets among all packets in the queue of a port may be buffered by the queue selection buffer provided for the queue. If the queue is currently empty, the first packet that arrives may be inserted into the queue selection buffer immediately. In some operation scenarios, a port or queue selection buffer may be implemented instead of a FIFO. For example, a priority-based scheme may be used to determine which packets among all packets in the queue of a port will utilize the queue selection buffer provided for the queue to buffer.

In some operational scenarios, rather than delivering the packet as a whole to the next packet processing component (e.g., within the same network node/switch, traffic manager, packet processor, etc.) or the next hop, the packet is delivered or transmitted by transmitting or transmitting cells or transmissions divided from the packet. In these operational scenarios, the selection from the port/cell selection buffer as described herein can be made as a cell/transmission (level) selection, rather than a (whole) packet level selection.

The queue scheduler may implement or perform its queue scheduling operations using one or more queue selection policies (or queue service rules), such as strict priority (SP), weighted deficit round-robin (WDRR), weighted (WFQ), byte-based queue selection policy, packet-based queue selection policy, a combination of two or more different queue selection policies, different queue selection policies other than or in addition to those described in detail herein, etc. For example, a first queue of a plurality of queues of a port may be assigned ten (10) packets, while a second queue of a plurality of queues may be assigned five (5) packets. A maximum bandwidth may be specified for a queue or a traffic flow therein to be used as a shaping threshold for traffic shaping or rate limiting operations, such as using a token bucket shaper, a leaky bucket shaper, etc. Additionally, optionally, or alternatively, bandwidth allocations and statistics may be set or made in a multi-level hierarchy with different queues or different queue groups, rather than a single or uniform port-level or queue-level bandwidth level.

The bandwidth (allocation or consumption) determined or specified in the queue selection policy or queue service list as described herein can be associated, measured or applied within a given time period. In some operating scenarios, different bandwidths or rates can be set or configured for different time periods of the same packet processing component, port, queue, business flow, etc. Bandwidth allocation can be used to determine or set the rate to add or fill the tokens in the corresponding token bucket, while bandwidth usage or consumption can be used to remove or discard tokens from the token bucket. A specific queue selection policy selected from a plurality of different queue selection policies can be used as a backup for other policies. A backup selection policy can be applied in response to determining that other queue selection policies have been applied or executed, or after the tokens in (one or more) token buckets have been discarded and exhausted based on a specific and/or consumption rate or bandwidth in these other queue selection policies.

The port scheduling operation and queue scheduling operation in the multi-level scheduler as described herein can be work-saving. For example, the queue scheduler described herein can be configured to select a port selection buffer that fills or pushes to a port until the port selection buffer becomes full so that the port will be as idle as possible.

In some operational scenarios, the port scheduler described herein may implement a time division multiplexing (TDM) scheduling strategy or service rule. A port may be subdivided or decomposed into subports and allocated time slots of time intervals. The time slots allocated to a port may be intermixed or mixed with other time slots allocated to other ports in the same time interval to allow subports of the same port to be evenly distributed over the entire allocated time slots in the time interval and to minimize jitter at a receiving device or packet processing component. Idle ports where no packets are to be sent (or transmitted/transmitted) may be skipped from time slot allocation.

Disclosed are methods, techniques and mechanisms for scheduling packets for transmission or transfer operations by a packet processing component or a network node/switch within a network. Multiple packet metadata sets for multiple incoming packets are buffered in multiple queue selection buffers associated with a port of a network node. One or more packet data sets for one or more outgoing packets are buffered in a port selection buffer associated with a port. During a selection clock cycle, when a port scheduler of a network node selects a subset of one or more packet data sets for a subset of one or more outgoing packets from a port selection buffer, a queue scheduler of the port simultaneously performs subsequent operations for multiple message queues set for the port. One or more packet metadata sets for one or more incoming packets in a plurality of incoming packets are selected from a plurality of packet metadata sets stored in a plurality of queue selection buffers. One or more second packet data sets for one or more second outgoing packets are added to the port selection buffer of the port. One or more second packet data sets are derived based at least in part on the one or more packet metadata sets for one or more incoming packets.

In other aspects, the present subject matter encompasses computer devices and/or computer-readable media configured to perform the foregoing techniques.

2.0. Structural Overview

FIG. 1 illustrates example aspects of an example networking system 100 (also referred to as a network) according to an embodiment, in which the techniques described herein may be practiced. The networking system 100 includes a plurality of interconnected nodes 110a-110n (collectively referred to as nodes 110), each node being implemented by a different computing device. For example, the node 110 may be a single networking computing device such as a router or a switch, in which some or all of the processing components described herein are implemented in an application specific integrated circuit (ASIC), a field programmable gate array (FPGA), or (one or more) other integrated circuits. As another example, the node 110 may include one or more memories storing instructions for implementing the various components described herein, one or more hardware processors configured to execute instructions stored in the one or more memories, and various data repositories in one or more memories for storing data structures used and operated by the various components.

Each node 110 is connected to one or more other nodes 110 in the network 100 via one or more communication links (depicted as lines between nodes 110). The communication links may be any suitable wired cables or wireless links. Note that the system 100 illustrates only one of many possible arrangements of nodes within a network. Other networks may include fewer or more nodes 110 with any number of links between nodes.

2.1. Data Unit

While each node 110 may or may not have a variety of other functionalities, in an embodiment, each node 110 is configured to send, receive, and/or relay data via these links to one or more other nodes 110. In general, data is communicated as a series of discrete units or data structures represented by signals transmitted over the communication links.

Different nodes 110 within the network 100 may send, receive, and/or relay data units at different communication levels or layers. For example, a first node 110 may send a data unit (e.g., a TCP segment, etc.) at the network layer to a second node 110 via a path that includes the intermediate nodes 110. The data unit may be divided into smaller data units at various sub-levels before the data is transmitted from the first node 110. These smaller data units may be referred to as "sub-units" or "portions" of the larger data unit.

For example, a TCP segment may be divided into packets, then cells, and finally sent to the intermediate device as a collection of signal encoding bits. Depending on the network type and/or device type of the intermediate node 110, the intermediate node 110 may reconstruct the entire original data unit before routing the information to the second node 110, or the intermediate node 110 may simply reconstruct certain sub-units of the data (e.g., frames and/or cells, etc.) and route these sub-units to the second node 110 without composing the entire original data unit.

When a node 110 receives a data unit, it typically examines the addressing information within the data unit (and/or other information within the data unit) to determine how to process the unit. The addressing information may be, for example, an Internet Protocol (IP) address, an MPLS label, or any other suitable information. If the addressing information indicates that the receiving node 110 is not the destination of the data unit, the receiving node 110 may look up the destination node 110 within the receiving node's routing information and, based on forwarding instructions associated with the destination node 110 (or an address group to which the destination node belongs), route the data unit to another node 110 connected to the receiving node 110. The forwarding instructions may indicate, for example, an egress port through which the data unit is to be sent, a label to which the data unit is to be attached, etc. In the event that multiple paths (e.g., through the same port, through different ports, etc.) to the destination node 110 are possible, the forwarding instructions may include information indicating a suitable method for selecting one of the paths, or may have defined a path that is considered the best path.

Addressing information, flags, labels, and other metadata used to determine how to process a data unit are typically embedded in a portion of the data unit called a header. The header is typically located at the beginning of a data unit and is followed by the data unit's payload, which is the information actually sent in the data unit. The header typically consists of different types of fields such as a destination address field, a source address field, a destination port field, a source port field, and so on. In some protocols, the number and arrangement of fields may be fixed. Other protocols allow an arbitrary number of fields, with some or all of the fields preceded by type information that explains to the node what the field means.

A traffic flow is a series of data units, such as packets, from a source computer to a destination. In an embodiment, the source of a traffic flow may mark each data unit in the sequence as a member of a flow using a label, tag, or other suitable identifier within the data unit. In another embodiment, a flow is identified by deriving an identifier from other fields in the data unit (e.g., a "five-tuple" combination of source address, source port, destination address, destination port, and protocol, etc.). A flow is generally meant to be sent in order, and therefore, in many operational scenarios, network devices are typically configured to send all data units within a given flow along the same path to ensure that the flow is received in order.

Node 110 may operate on network data at several different layers, and therefore view the same data as belonging to several different types of data units.

2.2. Network Path

Any node in the depicted network 100 can communicate with any other node in the network 100 by sending data units via a series of nodes 110 and links (referred to as paths). For example, node B (110b) can send a data unit to node H (110h) via a path from node B to node D to node E to node H. There may be a large number of valid paths between two nodes. For example, another path from node B to node H is from node B to node D to node G to node H.

In an embodiment, the node 110 does not actually need to specify the complete path of the data unit it sends. Instead, the node 110 can simply be configured to calculate the best path for the data unit to leave the device (e.g., which egress port it should send the data unit on, etc.). When the node 110 receives a data unit that is not directly addressed to the node 110, based on the header information associated with the data unit, such as the path and/or destination information, the node 110 relays the data unit to either the destination node 110, or the "next hop" node 110 calculated by the node 110 is in a better position to relay the data unit to the destination node 110. In this way, the actual path of the data unit is the product of the routing decisions made by each node 110 along the path about how to best move the data unit to the destination node 110 identified by the data unit.

2.3. Network equipment

Fig. 2 illustrates example aspects of an example network device 200 in which the techniques described herein may be practiced according to an embodiment. Network device 200 is a computing device comprising any combination of hardware and software configured to implement the various logical components (including components 210-290) described herein. For example, the device may be a single network computing device such as a router or a switch, wherein some or all of the components 210-290 described herein are implemented using an application specific integrated circuit (ASIC) or a field programmable gate array (FPGA). As another example, the implementation device may include one or more memories storing instructions for implementing the various components described herein, one or more hardware processors configured to execute instructions stored in one or more memories, and various data repositories in one or more memories for storing data structures used and operated by the various components 210-290.

Device 200 is generally configured to receive data unit 205 and forward it to other devices in a network (e.g., network 100) by means of a series of operations performed at various components within device 200. Note that in embodiments, some or all of nodes 110 in a system such as network 100 may each be or include a separate network device 200. In embodiments, node 110 may include more than one device 200. In embodiments, device 200 itself may be one of a plurality of components within node 110. For example, network device 200 may be an integrated circuit or "chip" dedicated to performing switching and/or routing functions within a network switch or router. A network switch or router may also include one or more central processor units, storage units, memory, physical interfaces, LED displays, or other components external to the chip, some or all of which may communicate with the chip.

A non-limiting example flow of a data unit 205 through the various subcomponents of the forwarding logic of the device 200 is as follows. After being received via the port 210, the data unit 205 may be buffered in the ingress buffer 224 and queued in the ingress queue 225 by the ingress arbiter 220 until the data unit 205 can be processed by the ingress packet processor 230 and then delivered to an interconnect (or cross-connect) such as a switching fabric. The data unit 205 may be forwarded from the interconnect to the traffic manager 240. The traffic manager 240 may store the data unit 205 in the egress buffer 244 and assign the data unit 205 to the egress queue 245. The traffic manager 240 manages the flow of the data unit 205 through the egress queue 245 until the data unit 205 is released to the egress packet processor 250. Depending on the processing, the traffic manager 240 may then assign the data unit 205 to another queue so that it can be processed by another egress processor 250, or the egress packet processor 250 may send the data unit 205 to the egress arbiter 260, which temporarily stores or buffers the data unit 205 in a transmit buffer and ultimately forwards the data unit via another port 290. Of course, depending on the embodiment, the forwarding logic may omit some of these subcomponents and/or include other subcomponents in a different arrangement.

Example components of device 200 are now described in more detail.

2.4.Port

Network device 200 includes ports 210/290. Ports 210, including ports 210-1 through 210-N, are inbound ("ingress") ports through which data units, referred to herein as data units 205, are received through a network, such as network 110. Ports 290, including ports 290-1 through 290-N, are outbound ("egress") ports through which at least some of data units 205 are sent to other destinations within the network after being processed by network device 200.

The egress port 290 may operate with a corresponding transmission buffer to store data units or sub-units (e.g., packets, cells, frames, transmission units, etc.) divided therefrom to be transmitted through the port 290. The transmission buffer may have a one-to-one correspondence with the port 290, a many-to-one correspondence with the port 290, etc. The egress processor 250 or the egress arbiter 260 operating with the egress processor 250 may output these data units or sub-units to the transmission buffer before these data units or sub-units are transmitted out of the port 290.

The data unit 205 can be any suitable PDU type, such as a packet, a cell, a frame, a transmission unit, etc. In an embodiment, the data unit 205 is a packet. However, the individual atomic data units on which the depicted components can operate can actually be sub-units of the data unit 205. For example, the data unit 205 can be received, acted upon, and transmitted at the cell or frame level. These cells or frames - which can also be referred to as transmissions - can be logically linked together as the data units 205 (e.g., packets, etc.) to which they belong respectively, for the purpose of determining how to process the cells or frames. However, the sub-units may not actually be assembled into the data units 205 within the device 200, especially if the sub-units are being forwarded to another destination by the device 200.

For purposes of illustration, ports 210/290 are depicted as separate ports, but may actually correspond to the same physical hardware port (e.g., a network jack or interface, etc.) on network device 210. That is, network device 200 may receive data units 205 and transmit data units 205 through a single physical port, and the single physical port may therefore function as both ingress port 210 and egress port 290. Nevertheless, for purposes of various functions, certain logic of network device 200 may treat a single physical port as a separate ingress port 210 and a separate egress port 290. Furthermore, for purposes of various functions, certain logic of network device 200 may subdivide a single physical ingress port or egress port into multiple ingress ports 210 or egress ports 290, or aggregate multiple physical ingress ports or egress ports into a single ingress port 210 or egress port 290. Therefore, in certain operational scenarios, ports 210 and 290 should be understood as different logical constructs that map to physical ports, rather than simply as different physical structures.

In some embodiments, the ports 210/290 of the device 200 may be coupled to one or more transceivers, such as a serializer/deserializer (“SerDes”) block. For example, the port 210 may provide a parallel input of received data units into a SerDes block, which then serially outputs the data units into the ingress packet processor 230. At the other end, the egress packet processor 250 may serially input the data units into another SerDes block, which outputs the data units in parallel to the port 290.

2.5. Packet Processor

The device 200 includes one or more packet processing components that collectively implement forwarding logic by which the device 200 is configured to determine how to process each data unit 205 received by the device 200. These packet processor components may be any suitable combination of fixed circuitry and/or software-based logic, such as specific logic components implemented by one or more field programmable gate arrays (FPGAs) or application specific integrated circuits (ASICs), or general purpose processors executing software instructions.

Different packet processors 230 and 250 may be configured to perform different packet processing tasks. These tasks may include, for example, identifying a path along which to forward data unit 205, forwarding data unit 205 to egress port 290, implementing flow control and/or other policies, manipulating packets, performing statistical or debugging operations, etc. Device 200 may include any number of packet processors 230 and 250 configured to perform any number of processing tasks.

In an embodiment, the packet processors 230 and 250 within the device 200 may be arranged so that the output of one packet processor 230 or 250 may ultimately be input into another packet processor 230 or 250 in such a manner that the data unit 205 is passed from certain (one or more) packet processors 230 and/or 250 to other packet processors 230 and/or 250 in a series of stages until the data unit 205 is ultimately disposed of (e.g., by sending the data unit 205 out of the egress port 290, "discarding" the data unit 205, etc.). In some embodiments, the exact set and/or sequence of packet processors 230 and/or 250 that process a given data unit 205 may vary depending on the attributes of the data unit 205 and/or the state of the device 200. There is no limit to the number of packet processors 230 and/or 250 that may be chained together in such a manner.

In some embodiments, and/or for certain processing tasks, based on decisions made when processing data unit 205, packet processor 230 or 250 can directly manipulate data unit 205. For example, packet processor 230 or 250 can add, delete, or modify information in a data unit header or payload. In other embodiments, and/or for other processing tasks, packet processor 230 or 250 can generate control information that accompanies or is merged with data unit 205 as data unit 205 continues through device 200. Other components of device 200 can then use the control information to implement the decisions made by packet processor 230 or 250.

In an embodiment, the packet processor 230 or 250 does not necessarily need to process the entire data unit 205, but may only receive and process a sub-unit of the data unit 205 including header information of the data unit. For example, if the data unit 205 is a packet including multiple cells, the first cell or a first subset of cells may be forwarded to the packet processor 230 or 250, while the remaining cells of the packet (and possibly the first cell(s)) may be forwarded in parallel to a merging component, where they await processing results.

Ingress and egress processors

In an embodiment, the packet processors may be generally categorized as either an ingress packet processor 230 or an egress packet processor 250. Generally, the ingress processor 230 resolves the destination for the traffic manager 240 to determine which ports 290 and/or queues the data unit 205 should be deflected to. There may be any number of ingress processors 230, including only a single ingress processor 230.

In an embodiment, the ingress processor 230 performs certain ingestion tasks on the data unit 205 as it arrives. These ingestion tasks may include, for example, but are not limited to, parsing the data unit 205, performing routing-related lookup operations, absolutely blocking data units 205 with certain attributes and/or replicating certain types of data units 205 when the device 200 is in a certain state, performing initial classification of the data unit 205, etc. Once the appropriate ingestion task(s) are performed, the data unit 205 is forwarded to the appropriate traffic manager 240, to which the ingress processor 230 may be coupled directly, or via various other components such as interconnect components.

In contrast, the egress packet processor(s) 250 of the device 200 may be configured to perform non-introducing tasks necessary to implement the forwarding logic of the device 200. These tasks may include, for example, tasks such as identifying paths along which data units 205 are forwarded, implementing flow control and/or other policies, manipulating data units, performing statistical or debugging operations, etc. In an embodiment, there may be different egress packet processor(s) 250 assigned to different flows or other classes of traffic, such that not all data units 205 will be processed by the same egress packet processor 250.

In an embodiment, each egress processor 250 is coupled to a different set of egress ports 290 to which they may send data units 205 processed by the egress processor 250. In an embodiment, access to a set of ports 290 or the corresponding transmit buffers 280 of the ports 290 may be regulated via an egress arbiter coupled to the egress packet processor 250. In some embodiments, the egress processor 250 may also or instead be coupled to other potential destinations, such as an internal central processing unit, a memory subsystem, or a traffic manager 240.

2.6. Buffer

Since not all data units 205 received by the device 200 can be processed simultaneously by components such as (one or more) packet processors 230 and/or 250 and/or port 290, various components of the device 200 may temporarily store data units 205 in memory structures referred to as (e.g., ingress, egress, etc.) buffers while they are waiting to be processed. For example, a particular packet processor 230 or 250 or port 290 may only be able to process a certain amount of data, such as a certain number of data units 205 or portions of data units 205, within a given clock cycle, which means that other data units 205 or portions of data units 205 destined for the packet processor 230 or 250 or port 290 must be ignored (e.g., discarded, etc.) or stored. At any given time, a large number of data units 205 may be stored in the buffers of the device 200, depending on network traffic conditions.

Device 200 may include various buffers, each used for a different purpose and/or component. Generally speaking, data units 205 waiting to be processed by a component are held in a buffer associated with the component until the data unit 205 is "released" to the component for processing.

The buffer can be implemented using any number of banks of different memories. Each bank can be a part of any type of memory including volatile memory and/or non-volatile memory. In an embodiment, each bank includes many addressable "entries" (e.g., rows, columns, etc.) in which data units 205, subunits, link data, or other types of data can be stored. The size of each entry in a given bank is referred to as the "width" of the bank, and the number of entries in the bank is referred to as the "depth" of the bank. The number of banks can vary according to an embodiment.

Each memory bank can have associated access restrictions.For example, a memory bank can be implemented using a single-port memory, which can only be accessed once in a given time slot (e.g., clock cycle, etc.). Therefore, equipment 200 can be configured to ensure that no more than one entry is required to be read from the memory bank or written to the memory bank in a given time slot. On the contrary, a memory bank can be implemented in a multi-port memory to support two or more accesses in a given time slot. However, in many cases, for higher operating frequency and/or to reduce costs, a single-port memory may be desirable.

In an embodiment, in addition to the buffer banks, the device may be configured to aggregate certain banks together into logical banks that support additional reads or writes in a time slot and/or higher write bandwidth. In an embodiment, whether logical, physical, or another (e.g., addressable, hierarchical, multi-level, sub-bank, etc.) organizational structure, each bank is capable of being accessed simultaneously with every other bank in the same clock cycle, although it is not necessary to fully implement this capability.

Some or all components of device 200 that utilize one or more buffers may include a buffer manager configured to manage the use of those buffers. The buffer manager may, for example, maintain a mapping of data units 205 to buffer entries in which data for those data units 205 is stored, determine when a data unit 205 must be discarded because the data unit 205 cannot be stored in a buffer, perform garbage collection on buffer entries for data units 205 (or portions thereof) that are no longer needed, and the like, among other processing tasks.

The buffer manager may include buffer allocation logic. The buffer allocation logic is configured to identify which buffer entry or entries should be utilized to store a given data unit 205 or a portion thereof. In some embodiments, each data unit 205 is stored in a single entry. In yet other embodiments, for storage purposes, the data unit 205 is received as or divided into constituent data unit portions. The buffer may store these constituent portions separately (e.g., not at the same address location or even in the same storage body, etc.). One or more buffer entries in which the data unit 205 is stored are marked as used (e.g., in a "free" list, if not marked as used, then free or available, etc.) to prevent the newly received data unit 205 from overwriting the already buffered data unit 205. After releasing the data unit 205 from the buffer, one or more entries in which the data unit 205 is buffered may be marked as available for storing a new data unit 205.

In some embodiments, the buffer allocation logic is relatively simple because data units 205 or data unit portions are randomly or using a polling method to allocate to storage bodies and/or specific entries in these storage bodies. In some embodiments, data units 205 are allocated to buffers based at least in part on characteristics of those data units 205 such as corresponding traffic flows, destination addresses, source addresses, ingress ports, and/or other metadata. For example, different storage bodies can be used to store data units 205 received from different ports 210 or sets of ports 210. In an embodiment, the buffer allocation logic also or instead uses buffer status information such as utilization metrics to determine which storage body and/or buffer entry is allocated to the data unit 205 or its portion. Other allocation considerations may include buffer allocation rules (e.g., not writing two consecutive cells from the same packet to the same storage body, etc.) and I/O scheduling conflicts, for example, to avoid allocating data units to a storage body when there is a non-write operation to the storage body because other components are reading the existing contents in the storage body.

2.7. Queues

In an embodiment, various components of the device 200 may implement queuing logic to manage the order in which data units 205 are processed from the buffers. For example, an ingress queue may be used to manage the flow of data units through an ingress buffer, while an egress queue may be used to manage the flow of data units through an egress buffer.

Each data unit 205 or (one or more) buffer locations storing data units 205 are considered to belong to one or more constructs called queues. In general, a queue is a collection of memory locations (e.g., in a buffer, etc.) arranged in some order by metadata describing the queue. The memory locations can (and typically are) non-contiguous with respect to their addressing scheme and/or physical or logical arrangement. For example, the metadata for a queue may indicate that the queue consists of entry addresses 2, 50, 3, and 82 in a particular buffer, in order.

In many embodiments, the order in which the queues arrange the constituent data units 205 generally corresponds to the order in which the data units 205 or data unit portions in the queues will be released and processed. Such queues are referred to as first-in, first-out ("FIFO") queues, but other types of queues may be utilized in other embodiments. In some embodiments, the number of data units 205 or data unit portions allocated to a given queue at a given time may be limited globally or on a per-queue basis, and the limit may change over time.

Traffic Management

According to an embodiment, the device 200 also includes one or more traffic managers 240 configured to control the flow of data units to the one or more packet processors 230 and/or 250. For example, a buffer manager within the device 200 may temporarily store the data units 205 in a buffer while the data units 205 wait to be processed by the egress processor(s) 250. The traffic manager 240 may receive the data units 205 directly from the ports 210, from the ingress processors 230, and/or other suitable components. In an embodiment, the traffic manager 240 receives one TDU from each possible source (e.g., each port 210, etc.) per clock cycle or other time slot.

The traffic manager 240 may include or be coupled to an egress buffer for buffering the data units 205 before sending them to their corresponding egress processor(s) 250. A buffer manager within the traffic manager 240 may temporarily store the data units 205 in the egress buffer while the data units 205 are waiting to be processed by the egress processor(s) 250. The number of egress buffers may vary depending on the embodiment. The data units 205 or portions of data units in the egress buffer may eventually be "released" to one or more egress processors 250 for processing by reading the data units 205 from the (e.g., egress, etc.) buffers and sending them to the one or more egress processors 250. In an embodiment, the traffic manager 240 may release up to a certain number of data units 205 from the buffer to the egress processor 250 at each clock cycle or other defined time slot.

In addition to managing the use of buffers to store data units 205 (or copies thereof), the traffic manager 240 may also include queue management logic configured to assign buffer entries to queues and manage the flow of data units 205 through the queues. For example, upon receiving a data unit 205, the traffic manager 240 may identify a particular queue to which the data unit 205 is assigned. The traffic manager 240 may also determine when to release—also referred to as "dequeue"—data units 205 (or portions thereof) from a queue and provide these data units 205 to a particular packet processor(s) 250. The buffer management logic in the traffic manager 240 may also "de-allocate" buffer entries that store data units 205 for queues that are no longer linked to the traffic manager. These entries are then reclaimed through a garbage collection process for use in storing new data.

In an embodiment, different destinations may have different queues. For example, each port 210 and/or port 290 may have its own set of queues. For example, the queue to which the input data unit 205 is assigned and linked may be selected based on forwarding information indicating which port 290 the data unit 205 should deviate from. In an embodiment, different egress processors 250 may be associated with each different set of one or more queues. In an embodiment, the current processing context of the data unit 205 may be used to select which queue the data unit 205 should be assigned to.

In an embodiment, different queues may also or instead exist for different flows or flow sets. That is, each identifiable service flow or service flow group is assigned its own set of queues, to which data units 205 are respectively assigned. In an embodiment, different queues may correspond to different service classes or quality of service (QoS) levels. Different queues may also or instead exist for any other suitable distinguishing attributes of the data unit 205, such as source address, destination address, packet type, etc.

The device 200 may include any number (e.g., one or more, etc.) of packet processors 230 and/or 250 and traffic managers 240. For example, different ports 210 and/or sets of ports 290 may have their own traffic managers 240 and packet processors 230 and/or 250. As another example, in an embodiment, the traffic manager 240 may be replicated for some or all stages of processing a data unit. For example, the system 200 may include a traffic manager 240 and an egress packet processor 250 for an egress stage performed when a data unit 205 exits the system 200, and/or a traffic manager 240 and a packet processor 230 or 250 for any number of intermediate stages. Thus, a data unit 205 may pass through any number of traffic managers 240 and/or packet processors 230 and/or 250 before exiting the system 200. In other embodiments, only a single traffic manager 240 is required. If intermediate processing is required, the flow of data units 205 may be "looped back" to traffic manager 240 for buffering and/or queuing after each stage of intermediate processing.

In an embodiment, the traffic manager 240 is coupled to the ingress packet processor 230 such that a data unit 205 (or portion thereof) is assigned to a buffer only when initially processed by the ingress packet processor 230. Once in an egress buffer, the data unit 205 (or portion thereof) may be "released" to one or more egress packet processors 250 for processing by the traffic manager 240 sending link or other suitable addressing information for the corresponding buffer to the egress packet processor 250, or by sending the data unit 205 directly.

In the process of processing the data unit 205, the device 200 may copy the data unit 205 one or more times - for example, based on the copy count specified in the control information of the data unit - for multi-destination purposes, such as but not limited to multicast, mirroring, recycling, debugging, etc. For example, a single data unit 205 can be copied to multiple egress queues. For example, the data unit 205 can be linked to a separate queue for each of ports 1, 3, and 5. As another example, the data unit 205 can be copied multiple times after it reaches the head of the queue (e.g., for different egress processors 250, etc.). Therefore, although certain techniques described herein may refer to the original data unit 205 received by the device 200, it should be understood that those techniques will be equally applicable to copies of the data unit 205 that have been generated for various purposes. The copy of the data unit 205 can be partial or complete. In addition, there may be actual copies of the data unit 205 in the buffer, or a single copy of the data unit 205 can be linked to multiple queues from a single buffer location at the same time.

2.9. Forwarding Logic

The logic of the device 200 that determines how to process the data unit 205, such as where and whether to send the data unit 205, whether to perform additional processing on the data unit 205, etc., is referred to as the forwarding logic of the device 200. As described above, the forwarding logic is implemented by various components of the device 200. For example, the ingress packet processor 230 can be responsible for parsing the destination of the data unit 205 and determining a set of actions/edits to be performed on the data unit 205, and the egress packet processor 250 can perform these edits. Alternatively, in some cases, the egress packet processor 250 can also determine the action and parse the destination. In addition, there can be embodiments in which the ingress packet processor 230 also performs the editing.

Depending on the embodiment, the forwarding logic may be hard-coded and/or configurable. For example, in some cases, the forwarding logic of the device 200 or a portion thereof may be at least partially hard-coded into one or more ingress processors 230 and/or egress processors 250. As another example, the forwarding logic or elements thereof may also be configurable in that the logic changes over time in response to analysis of state information collected from various components of the device 200 and/or other nodes in the network in which the device 200 is located or instructions received.

In an embodiment, the device 200 will typically store one or more forwarding tables (or equivalent structures) in its memory that map specific data unit attributes or characteristics to actions to be taken for data units 205 having those attributes or characteristics, such as sending the data unit 205 to a selected path, or using a specified internal component to process the data unit 205. For example, such attributes or characteristics may include a quality of service level specified by the data unit 205 or associated with another characteristic of the data unit 205, a flow control group, an ingress port 210 through which the data unit 205 is received, a tag or label in a header of a packet, a source address, a destination address, a packet type, or any other suitable distinguishing attribute. The traffic manager 240 may, for example, implement logic to read such a table, determine one or more ports 290 to which the data unit 205 is to be sent based on the table, and send the data unit 205 to an egress processor 250 coupled to the one or more ports 290.

According to an embodiment, the forwarding table describes a group of one or more addresses, such as a subnet of an IPv4 or IPv6 address. Each address is the address of a network device on the network, but the network device can have multiple addresses. Each group is associated with a set of one or more actions that may be different, to be performed for data units that resolve to (e.g., directed to, etc.) the address within the group. Any suitable set of one or more actions can be associated with a group of addresses, including but not limited to forwarding a message to a specified "next hop", copying a message, changing the destination of a message, discarding a message, performing debugging or statistical operations, applying a quality of service strategy or a flow control strategy, etc.

For the purpose of illustration, these tables are described as "forwarding tables", but it will be appreciated that the scope of the (one or more) actions described by these tables can be much larger than simply forwarding the message to where. For example, in an embodiment, the table can be a basic forwarding table that simply specifies the next hop for each group. In other embodiments, the table can describe one or more complex strategies for each group. In addition, different types of tables for different purposes can exist. For example, a table can be a basic forwarding table compared with the destination address of each group, and another table can specify the strategy applied to the group when entering based on the destination (or source) group of the group, etc.

In an embodiment, the forwarding logic may read the port status data of the port 210/290. The port status data may include, for example, flow control status information describing various business flows and associated business flow control rules or policies, link status information indicating whether a link is connected or disconnected, and port utilization information indicating how the port is utilized (e.g., utilization, percentage, utilization status, etc.). The forwarding logic may be configured to implement an associated rule or policy associated with the flow to which a given packet belongs.

As data units 205 are routed through different nodes in a network, a node may sometimes drop, fail to send, or fail to receive a particular data unit 205, causing the data unit 205 to fail to reach its intended destination. The act of dropping a data unit 205 or failing to deliver a data unit 205 is generally referred to as "dropping" the data unit. Instances of dropping a data unit 205, referred to herein as "drops" or "packet losses," may occur for a variety of reasons, such as resource limitations, errors, or intentional policies. Different components of the device 200 may make decisions to drop data units 205 for a variety of reasons. For example, the traffic manager 240 may determine to drop a data unit 205 because, among other reasons, a buffer is overutilized, a queue exceeds a particular size, and/or the data unit 205 has particular characteristics.

2.10. Multi-level scheduler

3A illustrates an example multi-stage scheduler 300 in a network node or switch, which is used to schedule and select networks/packets for transmission or transmission operations through multiple ports in the network node/switch. The multi-stage scheduler 300 includes a port scheduler 308, multiple port selection buffers 306 for multiple ports (expressed as "port 0 buffer", "port 1 buffer", ... "port n buffer"), multiple queue schedulers 304 for multiple ports or port selection buffers (expressed as "QS0", "QS1", ... "QSn"), multiple groups of queue selection buffers 302 (expressed as "P0, Q0 buffer", ... "P0, Qm buffer", "P1, Q0 buffer", ... "P1, Qm buffer", ... "Pn, Q0 buffer", ... "Pn, Qm buffer"), and the queue scheduler 304 selects a network/packet from the multiple groups of queue selection buffers 302 or dequeues the network/packet to further queue or buffer to multiple port selection buffers 306, etc. In some operating scenarios, some or all of these modules, devices, systems, etc. in FIG. 3 may be implemented in part or in whole by a network or packet switch described herein. In some operating scenarios, some or all of these modules, devices, systems, etc. in FIG. 3A may be implemented in part or in whole by a network or packet switch described herein. Each block, module, device, system, etc. illustrated in the multi-stage scheduler 300 may be implemented jointly or individually with one or more components, subsystems, or devices, which may include any combination of hardware and software configured to implement the various different logical components described herein. For example, one or more computing devices may include one or more memories storing instructions for implementing the various components described herein, one or more hardware processors configured to execute instructions stored in one or more memories, and various data repositories in one or more memories for storing data structures used and operated by various components.

The multi-stage scheduler 300 includes a port scheduler that selects or dequeues a specific network/packet from a plurality of port selection buffers of a plurality of ports, for example, in real time or near real time at each CPU cycle or each reference clock cycle. Each of the plurality of port selection buffers may be set or maintained for a corresponding port in the plurality of ports for selecting, buffering, storing, enqueuing or dequeuing a set of packet data of a set of networks/packets to be transmitted or transferred through the corresponding port.

The multi-stage scheduler 300 includes a plurality of queue schedulers, which select or dequeue a specific network/packet from a plurality of sets of queue selection buffers of a plurality of ports, for example, in real time or near real time at each CPU cycle or each reference clock cycle. Each set of selection buffers in the plurality of sets of queue selection buffers can be set or maintained by a corresponding queue scheduler in the plurality of queue schedulers for a corresponding port in the plurality of ports to select, buffer, store, enqueue or dequeue a set of packet metadata of a set of networks/packets to further enqueue, store or buffer in a port selection buffer of the corresponding port.

For example, a first set of selection buffers ("P0, Q0 buffers", ... "P0, Qm buffers") may be set or maintained by a first queue scheduler ("QS0") for a first port ("Port 0") for selecting, buffering, storing, enqueuing or dequeuing a set of packet metadata of a set of networks/packets for further enqueuing, storing or buffering in a first port selection buffer ("Port 0 buffer") of the first port ("Port 0"). A second set of selection buffers ("P1, Q0 buffers", ... "P1, Qm buffers") may be set or maintained by a second queue scheduler ("QS1") for a second port ("Port 1") for selecting, buffering, storing, enqueuing or dequeuing a set of packet metadata of a set of networks/packets for further enqueuing, storing or buffering in a second port selection buffer ("Port 1 buffer") of the second port ("Port 1"). The (n+1)th group selection buffer ("Pn, Q0 buffer", ... "Pn, Qm buffer") can be set or maintained by the (n+1)th queue scheduler ("QSn") for the (n+1)th port ("port n") to select, buffer, store, enqueue or dequeue a set of packet metadata for a set of network/packets for further enqueuing, storing or buffering in the (n+1)th port selection buffer ("port n buffer") of the (m+1)th port ("port n").

2.11. Others

The device 200 or multi-stage scheduler 300 therein only illustrates one of many possible arrangements of devices or schedulers configured to provide the functions described herein. Other arrangements may include fewer, additional or different components, and the division of work between components may vary depending on the arrangement. In addition, in an embodiment, the technology described herein may be used in various computing environments other than within the network 100.

Furthermore, the figures herein illustrate only some of the various arrangements of memory that can be used to implement the described buffering techniques. Other arrangements may include fewer or additional elements in different arrangements.

3.0. Functional Overview

Described in this section are various example method flows or operations for implementing various features of the systems and system components described herein. The example method flows are non-exhaustive. Alternative method flows and flows for implementing other features will become apparent from this disclosure.

The various elements of the process flows or operations described below can be performed in various systems. In an embodiment, each process described in conjunction with the functional blocks described below can be implemented using one or more integrated circuits, logic components, computer programs, other software elements, and/or digital logic in any of a general purpose computer or a special purpose computer when performing data retrieval, conversion, and storage operations involving interaction and conversion of the physical state of the computer's memory.

3.1.Port and Queue Scheduling

According to the techniques described herein, a set of packet metadata may be generated for incoming packets (e.g., received, input) in a queue of a port and buffered/stored in a queue selection buffer associated with a port (e.g., ingress, egress, etc.) of a network node/switch. A set of packet data may be generated for outgoing packets (e.g., selected, output, to be forwarded, etc.) in a port selection buffer associated with a port.

In a selected clock cycle, when the port scheduler of the network node/switch selects a subset of the packet data set corresponding to the subset of the outgoing packets from the port selection buffer, the queue scheduler of the packet queue set for the port of the network node/switch can simultaneously select a subset of the packet metadata set corresponding to the subset of the incoming packets from the packet metadata set buffered/stored in the queue selection buffer. For a second outgoing packet corresponding to the subset of the incoming packets, a second packet data set can be derived, generated or determined by the queue scheduler based on the subset of the packet metadata set. These second packet data sets can be buffered/stored in the port selection buffer of the port by the queue scheduler at the same clock cycle.

3.2. Port or queue qualified

The port scheduler described herein performs port scheduling operations in a network node/switch to arbitrate access or allocation to the overall (e.g., egress, ingress, transmission, transmission, 1Tbps or greater than 1Tbps, 400Mbps, 100Mbps, etc.) bandwidth on some or all eligible (e.g., egress, ingress, physical, logical, etc.) ports of the network node/switch. The port scheduler can use a set of scheduling eligibility criteria (also referred to as "port eligibility criteria") of the port to determine whether the port is qualified for selecting a packet from a port selection buffer and further performing a transmission or transmission operation on it. These port eligibility criteria may include, but are not necessarily limited to, any one, some or all (or any combination) of the following: according to the applicable port profile or configuration settings or operating state, not shaped below the maximum transmission rate (e.g., measured in bits, bytes or the number of packets, etc.) or rate limited (rated limited) or blocked from transmission or transmission; not flow controlled or suspended; having transmission credits, such as signals from downstream devices based on available downstream resources on downstream devices; at least one of all queues of the port is qualified; etc.

A queue scheduler as described herein may be configured for each specific port in some or all ports of a network node/switch, and performs queue scheduling operations in the network node/switch to arbitrate access or allocation (e.g., egress, ingress, transmission, transport, etc.) to the entire port-specific bandwidth on some or all eligible queues in a plurality of (e.g., 2, 4, 8, 12, etc.) queues of a specific port of the network node/switch. Different ports of the network node/switch may be configured with the same or different (one or more) numbers of queues. The queue scheduler may use a second scheduling eligibility criteria (also referred to as a "queue eligibility criteria") set for the queues of the port to determine whether the queue is qualified for selecting packets from the queue selection buffer and further performing buffering operations using the port selection buffer of the port. These queue eligibility criteria may include, but are not necessarily limited to, any, some, or all (or any combination) of the following: not shaped or rate limited below an applicable or specified maximum transmission rate or blocked from transmission or delivery, according to an applicable queue profile or configuration setting or operating state; not subject to flow control (e.g., priority-based flow control or PFC, etc., when a higher priority traffic is currently being served in the port) or blocked from transmission or delivery; having a non-negative credit deficit, such as under a weighted deficit round-robin (WDRR) or weighted round-robin (WRR) scheduling policy or implementation; not currently empty; a previously or last unselected queue; etc. In some operating scenarios, the queue scheduler may be implemented to select a packet and not switch context until all selections associated with the packet are completed. In some other operating scenarios, the queue scheduler may be implemented to select multiple packets and switch contexts without waiting for all selections associated with a particular packet to be completed.

Different (e.g., end-user, non-user, etc.) traffic types such as video, data center traffic, etc. may be rate limited or shaped differently. In some operational scenarios, data or transfer rates to a particular processor or device or server in a data center may be specifically rate limited or shaped differently than other data/transfer rates to different processors or different devices or different servers in the same data center.

Flow control as described herein may be, but is not necessarily limited to, priority-based, such as strict priority. Flow control (PFC) from downstream applications receiving a traffic flow may depend on a particular scheduling load. Credit deficits may be used, for example, to allocate or assign weighted bandwidth distribution to different queues or corresponding traffic flows using tokens and/or thresholds under a WDRR queue scheduling policy or rule. A negative credit deficit for a queue or corresponding traffic flow results in the queue or traffic flow being determined to be ineligible for queue selection.

3.3. Work Savings

Some or all of the schedulers described herein (e.g., port or queue schedulers) may be implemented as work-saving schedulers that seek to keep the scheduled resource(s) busy or use the resource(s) on each clock cycle—access to the scheduled resource(s) being arbitrated by the scheduler. Thus, in response to determining that there are eligible packets for packet selection (or dequeuing), such a work-saving scheduler does not keep the resource(s) unused or idle (e.g., does not use the resource(s), etc.), but rather selects or dequeues some or all of the eligible packets for further operation using the resource(s).

The techniques described herein may be implemented to ensure that when a port's queue contains packets or its cells, the port is not idle and is ready to transmit packets with minimized latency, even when its port speed is relatively high, such as one or more hundreds of megabits per second (Mbps), one or more terabits per second (Tbps), etc. For such ports, the time between packet arrival and packet transmission needs to be relatively low, such as a few nanoseconds or even shorter for small packet sizes.

In order to minimize the time or delay of relatively high speed/bandwidth operation, the scheduler can maintain or keep the latest state related to the packet queuing/dequeuing operation available at all times or clock cycles during runtime. The state maintained by the scheduler to facilitate high speed/bandwidth operation may include (at any given time or clock cycle): whether the dequeue of the current scheduled cell or transmission of the packet from the queue and/or port selection buffer will cause the queue and/or port selection buffer to become empty; whether the current scheduled cell or transmission represents the final transmission of the packet (e.g., end of packet or EOP, etc.); etc.

The multi-stage scheduler including the port scheduler operated with multiple queue schedulers can be used to support relatively high-speed and low-delay packet transmission or transmission operation.These schedulers can independently obtain or dequeue the buffer entry corresponding to the network/packet in their respective selection buffers.For example, when the timing loop of the port scheduler selects, obtains or dequeues the port or specific port to select the buffer entry for transmission or transmission from the corresponding port selection buffer (for example, its head, etc.), the queue scheduler in the corresponding separate and independent timing loops Some or all of the queue schedulers can simultaneously select, obtain or dequeue specific queue selection buffer entries from the queue selection buffer (head), to further enter the queue to the port selection buffer (for example, tail, etc.).Under the technology described in this article, the timing loops associated with the parsing port and/or queue state are decoupled from each other.The port selection buffer can be used to store the selection made by the queue scheduler at any time (for example, at the tail of the port selection buffer, etc.), without any waiting, and the same port selection buffer-or qualified non-empty port selection buffer-can be used by the port scheduler to select packets for transmission or transmission operation at any time, without any waiting. The timing loops for port scheduling operations and queue scheduling operations can operate at a single relatively high clock rate, or alternatively, can operate at two or more different clock rates. For example, the port scheduling operation can be implemented to support a relatively high clock rate compared to the clock rate of the queue scheduling operation.

3.4. Queue selection data flow

FIG. 3B illustrates an example data flow associated with a set of queue selection buffers (e.g., “Port 0, Q0 buffers,” “Port 0, Qm buffers,” etc.) of a plurality of sets of queue selection buffers 302 of a port (e.g., “Port 0,” etc.) of a plurality of ports in a network node/switch and a queue scheduler (e.g., “QS0,” etc.) of a plurality of queue schedulers 304.

Multiple groups of queues (e.g., egress, ingress, 245 of FIG. 2 , 225 of FIG. 2 , etc.) may be set or maintained in a network node/switch of multiple ports in the network node/switch. Each group of queues in the multiple groups of queues may be set or maintained for a corresponding port in the multiple ports. For example, a group of queues in the multiple groups of queues may be set for a port (“port 0”) in the multiple ports to queue and dequeue networks/packets waiting to be transmitted or transmitted through the port (“port 0”).

Each queue in the queue group set or maintained for the port ("port 0") may correspond (eg, 1-1, etc.) to a corresponding queue selection buffer in the queue selection buffer group for the port ("port 0").

For example, a queue in a queue group may correspond to a queue selection buffer 302-0-0 ("Port 0, Q0 buffer") in a queue selection buffer group for a port ("Port 0"). A queue may include a collection of queue entries, each of which may correspond to a collection of networks/packets to be transmitted or transferred through the port ("Port 0") - which may be referred to as networks/packets enqueued in the queue. A subset of networks/packets may be selected from the queue (e.g., the first few at the head of the queue, the highest priority, etc.) and enqueued to a queue selection buffer 302-0-0 ("Port 0, Q0 buffer") corresponding to the queue.

The queue scheduler ("QS0") selects or dequeues a specific network/packet from the group of queue selection buffers ("Port 0") at each CPU cycle or each reference clock cycle (e.g., in real time or near real time). The specific network/packet selected by the queue scheduler ("QS0") from the group of queue selection buffers is also buffered, stored, or enqueued by the queue scheduler ("QS0") in the corresponding port selection buffer ("Port 0 buffer"). Compared to the queues in the queue group for the port ("Port 0"), a subset of all packets in the queue can have packet metadata/information stored or buffered in the corresponding queue selection buffer for fast access by the queue - for example, selection can be made for a relatively small subset of packets rather than all packets in the queue.

Thus, a network node/switch may use a port's queue selection buffer bank to overcome memory read latency to obtain the next packet(s) for transmission or transfer operations via the port.

For example, the queue scheduler ("QS0") can select or dequeue one or more networks/packets from the networks/packets represented or enqueued in the queue selection buffer 302-0-0 ("Port 0, Q0 buffer"), for example, in real time or near real time, every CPU cycle or every reference clock cycle, and further buffer/store/enqueue these selected/dequeued networks/packets from the queue selection buffer ("Port 0, Q0 buffer") in the port selection buffer ("Port 0 buffer") of the port ("Port 0").

As shown in FIG3B , a queue selection buffer (“P0, Q0 buffer”) in a queue selection buffer group (“P0, Q0 buffer” … “P0, Qm buffer”) corresponding to a queue scheduler (“QS0”) may include a set of buffer entries 310 (denoted as “port 0, Q0 buffer entries”) in a specific order represented by the vertical dashed arrows in FIG3B . The set of buffer entries 310 may correspond to or specify a set of networks/packets currently buffered/stored/enqueued in the queue selection buffer (“P0, Q0 buffer”).

Packet/cell specific queue control information may be included in the packet metadata of a packet or its cells stored in a queue selection buffer entry as described herein to drive or facilitate the (e.g., internal, etc.) operation of a queue scheduler. The packet/cell specific queue control information may include, but is not necessarily limited to: one or more data addresses and any additional metadata associated with the packet. For example, a multicast packet may be indicated or specified in the packet/cell specific queue control information by a value greater than one (1) for a packet copy count. Additional information or packet metadata such as a cell/transmission count, (one or more) packet/cell/transmission sizes, etc. may also be indicated or specified in the packet/cell specific queue control information.

Therefore, it is not necessary to store all packet data or information of a network/packet in a buffer entry in a queue selection buffer ("P0, Q0 buffer") as described herein corresponding to the packet. Instead, a set of packet metadata related to the network/packet having a relatively small data size compared to the data size of the packet may be stored or maintained in the buffer entry. The set of packet metadata stored in the buffer entry of the corresponding packet may include some or all packet control data or packet data related to the packet, such as a packet (pkt) transmission count, a packet copy count, and the like. The packet copy count in the packet metadata set of a network/packet refers to the number of packet copies of the network/packet generated and/or transmitted for the network/packet (e.g., total number, total remaining, etc.). The packet transmission count in the packet metadata set of a network/packet refers to the number of scheduler selections performed for each packet copy of the network/packet (e.g., total number, total remaining, etc.).

The network/packet may be transmitted or transferred in or with one or more cells or transfers derived from the network/packet; each cell or transfer of the network/packet carries a corresponding portion of the packet data in the network/packet. The number of scheduler selections stored in the buffer entry corresponds to or represents the number of cells or transfers of the network/packet. Each scheduler selection in the scheduler selections corresponds to or represents a corresponding cell in a cell or transfer of the network/data packet.

The packet metadata set may include additional packet information or data to facilitate the selection or dequeue operation. When all scheduler selections for each packet copy of a network/packet have been made by the queue scheduler ("QS0"), the network/packet is dequeued from the queue selection buffer ("P0, Q0 buffer") or from the corresponding queue.

As shown in Figure 3B, the buffer entry 310 in the queue selection buffer 302-0-0 ("P0, Q0 buffer") can currently buffer or store four sets of packet metadata for four networks/packets, respectively. The first buffer entry - or the head of the buffer entry in the queue selection buffer 302-0-0 ("P0, Q0 buffer") - can store a first set of packet metadata for the first of the four networks/packets ("Pkt transmission count = 3" and "Pkt copy count = 1"). The second buffer entry - or the next buffer entry in the queue selection buffer 302-0-0 ("P0, Q0 buffer") - can store a second set of packet metadata for the second of the four networks/packets ("Pkt transmission count = 9" and "Pkt copy count = 1"). The third buffer entry in the buffer entries in the queue selection buffer 302-0-0 ("P0, Q0 buffer") can store a third set of packet metadata for the third of the four networks/packets ("Pkt transmission count = 4" and "Pkt copy count = 3"). The fourth buffer entry - or the tail of the buffer entry in the queue selection buffer 302-0-0 ("P0, Q0 buffer") - can store a fourth set of packet metadata ("Pkt transmit count = 1" and "Pkt copy count = 1") for the fourth of the four networks/packets.

3.5. Queue Status

As shown in FIG3B , in addition to buffer entry 310 (“Port 0, Q0 buffer entry”), queue selection buffer 302-0-0 (“Port 0, Q0 buffer”) may be used to store queue selection information/data 312. The queue selection information/data 312 in queue selection buffer 302-0-0 (“Port 0, Q0 buffer”) may include, but is not necessarily limited to, any, some, or all of the following: empty state, empty state at pick-up, EOP state at pick-up, etc.

The empty state can be set and/or used by the queue scheduler (“QS0”) to determine (e.g., at a given CPU or clock cycle, etc.) whether the queue from which a subset of networks/packets is selected to have packet metadata stored in buffer entry 310 (“Port 0, Q0 buffer entry”) of queue selection buffer 302-0-0 (“Port 0, Q0 buffer”) is currently empty.

The queue scheduler ("QS0") can set and/or use the pick-time empty state to determine (e.g., at a given CPU or clock cycle, etc.) whether the current selection of a network/packet or the current selection of a cell/transmission of a packet made by the queue scheduler ("QS0") from queue selection buffer 302-0-0 ("Port 0, Q0 buffer") will cause the queue or its empty state to transition to empty or true.

The EOP state at pick time can be set and/or used by the queue scheduler ("QS0") to determine (e.g., at a given CPU or clock cycle, etc.) whether the current selection of a network/packet or the current selection of a cell/transmission of a packet made by the queue scheduler ("QS0") from queue selection buffer 302-0-0 ("Port 0, Q0 buffer") will cause the final or last transmission of the packet to occur or reach the end of packet (EOP) of the packet.

For example, a packet carrying 9 kilobytes in its payload can be divided or divided into 9 separate payload parts carried in 9 cells or transmissions, respectively. In the scheduling operation performed by the first queue or the corresponding first queue selection buffer in the multiple queues or queue selection buffers of the port by the queue scheduler as described herein, the queue scheduler can determine whether the cell or transmission of the current selection of the packet is the penultimate cell or transmission of the packet to be selected from the first queue or queue selection buffer and to be transmitted or transmitted by the port. If it is determined to be so, the queue scheduler can set the EOP state to true when picking up, and continue to provide a selection preference to the packet by selecting the last cell or transmission of the packet in the next clock cycle instead of another cell or transmission of another packet. On the other hand, if it is not determined to be so, the queue scheduler can set or maintain the EOP state to false when picking up, and continue to select a cell or transmission or other packets in the packet in the queue or queue selection buffer in the next clock cycle, rather than giving a selection preference to the packet based on the EOP state when picking up. As a result, compared with other ways through the port, a packet or its entire payload can be transmitted or transmitted relatively quickly.

Additionally, optionally or alternatively, in a scheduling operation performed by a queue scheduler described herein on a first queue or a corresponding first queue selection buffer of a plurality of queues or queue selection buffers of a port, the queue scheduler may determine whether the currently selected packet is the last packet to be selected from the first queue or queue selection buffer and to be transmitted or transmitted by the port. If it is determined to be so, the queue scheduler may set the pickup time-space state to true. The queue scheduler may easily (or without waiting) enter the next qualified queue in the next clock cycle to avoid inadvertently serving an empty queue or queue selection buffer (starvation) and being unable to select or generate a packet or its cell for the port in the next clock cycle. On the other hand, if it is not determined to be so, the queue scheduler may set or maintain the pickup time-space state to false. The queue scheduler may enter one or any other qualified queue (all non-empty and the pickup time-space state is false) in the same qualified queue in the next clock cycle.

As a result of using these states in queue scheduling operations, a queue scheduler for a port can be used or implemented to keep the port transmissions (active or not starved) of the port. This can help prevent or significantly reduce time delays in packet transmission/transmission operations, including but not limited to operations related to bulk transmission, multiple packet grouping, multiple select packet operations, etc.

3.6. Queue Selection Strategy

Each queue scheduler may implement one or more queue selection policies, such as those set forth in the queue scheduler configuration for the queue scheduler. By way of example and not limitation, each of some or all of the queues in the queue group for a port ("port 0") may be assigned a (queue) service rule that defines a scheduling order between the networks/packets represented in the queue. Examples of scheduling order may include, but are not necessarily limited to, any of the following: strict priority, weighted deficit round robin or WDRR, weighted fair queuing or WFQ, etc.

Additionally, optionally or alternatively, each queue in some or all of the queues in the queue group for the port ("Port 0") may be assigned a corresponding minimum bandwidth (MinBW) guarantee to ensure that the queue receives at least the allocated minimum amount of bandwidth from the multi-level scheduler (avoiding starvation) if the queue provides or contains sufficient amount of packet data for transmission or delivery that can be supported by more than the corresponding minimum amount of bandwidth.

Additionally, optionally, or alternatively, each queue in some or all of the queues in the queue group of the port ("Port 0") may be assigned a corresponding maximum bandwidth (MaxBW) limit to ensure that the amount of bandwidth (total or cumulative) provided to the queue for consumption by the multi-level scheduler is limited to or does not exceed a particular maximum bandwidth.

In some operating scenarios, the queue scheduler described herein may maintain or keep track of one or more (queue scheduler) service lists. Separate or different service lists may be used to bin or group different combinations or different subsets of queues in a queue group of a port. Some or all of the service lists maintained by the queue scheduler may be set, configured, specified, or defined based on one or more configured attributes of any, some, or all queues in a queue group of a port. The queue scheduler may use some or all of the service lists to establish or determine a specific service order for queues in a queue scheduler service queue group or a queue selection buffer in a queue selection buffer group corresponding to a queue group.

In some operational scenarios, the queue scheduler service list may include a minBW service list that specifies the corresponding minimum bandwidth of the queue. The minBW service list may be first serviced by the queue scheduler to determine a particular list of eligible queues that have not yet met the minBW guarantees, and seek to make selections to meet these minBW guarantees. The eligible queues in a particular list may be serviced in a round-robin order (e.g., packet level rather than cell level, etc.).

In some operational scenarios, the queue scheduler service list may include a strict priority (SP) service list that specifies or proposes strict priority (SP) service/scheduling rules for servicing eligible queues in a queue group managed by the queue scheduler. The SP service list may be serviced by the queue scheduler to determine a specific priority order among eligible queues and to select from among the eligible queues in a specific priority order (e.g., priority (M-1) down to priority 0, etc.). The SP service list may be serviced in response to determining that the minBW service list is empty (or that all queues have satisfied their corresponding minBW guarantees).

In some operational scenarios, the queue scheduler service list may include a WDRR service list that specifies or proposes WDRR service/scheduling rules for servicing eligible queues in a queue group managed by the queue scheduler. The WDRR service list may be serviced by the queue scheduler to select from eligible queues in a (e.g., packet level, etc.) polling order. In response to determining that both the minBW service list and the SP service list are empty (or all queues have satisfied their corresponding minBW guarantees and all strict priority queues have been served), the WDRR service list may be served last.

In some operation scenarios, the same queue may appear on multiple service lists. For example, a queue may appear on both the minBW service list and the WDRR service list.

3.7. Select Operation

3C and 3D illustrate example operations of a queue and a port scheduler associated with a port selection buffer.

As shown in FIG. 3C , multiple queue schedulers 304 (“QS0” through “QSn”) may acquire or dequeue selections (or picks) of packets or their cells/transmissions from multiple queues of a port by acquiring or dequeuing selections (or picks) of queue selection buffer entries corresponding to packets or their cells/transmissions from multiple groups of queue selection buffers 302 (“P0, Q0 buffers,” … “P0, Qm buffers,” “P1, Q0 buffers,” … “P1, Qm buffers,” … “Pn, Q0 buffers,” … “Pn, Qm buffers”). Each selection from a queue—among selections (or picks) from multiple queue groups—results in a selection or pick in a queue being dequeued and/or pushed into a corresponding port selection buffer. A port selection buffer may contain up to N selections or port selection buffer entries for a port made by a queue scheduler in a queue selection buffer group for the same port.

As shown in Figure 3D, the queue scheduler of the port can make selections until the port selection buffer becomes full - for example, all N port selection buffer entries have been used for N packet data sets of N packets. Back pressure can be asserted on the queue scheduler - or flow control operations can be performed with the queue scheduler to pause or delay the entry or pushing of packet data sets corresponding to additional selections of the queue selection buffer from the queue selection buffer group into the port selection buffer.

The port scheduler 308 and the queue scheduler can independently perform their corresponding scheduling (selection and queuing operations). The port scheduler 308 can (e.g., simultaneously, etc.) perform scheduling operations on the port corresponding to the queue scheduler, and perform scheduling operations on other (e.g., only, etc.) qualified ports with non-empty port selection buffers and/or non-empty queues.

In some operating scenarios, the port schedulers and queue schedulers described herein may be implemented or configured to perform multi-packet scheduling operations.

In a first example, a buffer entry at a queue selection or port selection level may contain multiple packets per buffer entry. Additionally, optionally or alternatively, the total number of packets per (port or queue) selection buffer entry may vary, or may vary with the size of the packet. A multi-packet scheduling operation may be used to enable or support scheduling operations to dequeue multiple packets per CPU or clock cycle to achieve relatively high throughput.

In a second example, each of some or all of the queue scheduler and the port scheduler may be implemented or configured to select multiple (queue or port) selection buffer entries per scheduling event or per CPU or clock cycle. For example, the port scheduler may be implemented or configured to select up to M packets from M different queues or M different queue selection buffer entries (in the queue selection buffer associated with the port) in a single CPU or clock cycle.

Representing that multiple packets in a single buffer entry or multiple buffer entries in a queue port selection buffer or a port selection buffer can be selected or dequeued from the queue selection buffer or the port selection buffer in a single CPU or clock cycle based at least in part on a priority indication of the packets, a sequence indication or an index/number of the packets, etc.

3.8. Port Bundle Scheduling

In some operating scenarios, in order to support relatively high-speed scheduling operations, the multi-stage scheduler described herein may be implemented or configured to support port bundle scheduling operations. As shown in FIG. 4 , a plurality of port selection buffers 306 of a plurality of ports in a network node/switch may be divided (e.g., mutually exclusively, etc.) into a plurality of different port selection buffer bundles 306-1 corresponding to a plurality of different port bundles 314 (e.g., mutually exclusively, etc.) divided from the plurality of ports. Each of the plurality of different port selection buffer bundles 306-1 may include one or more port selection buffers for one or more ports constituting a corresponding port bundle in the plurality of different port bundles 314. For example, a network node/switch may have 128 ports, which may be separated or divided into two port bundles with 64 ports per port bundle.

The plurality of port schedulers 308-1 may be implemented or configured to simultaneously and/or independently perform packet-level or cell-level scheduling operations for transmission or transfer operations through ports in the plurality of different port bundles 314. More specifically, each of the plurality of port schedulers 308-1 may be implemented or configured to perform packet-level or cell-level scheduling operations for transmission or transfer operations through ports in a corresponding port bundle in the plurality of different port bundles 314 simultaneously and/or independently of scheduling operations performed by any other (one or more) of the plurality of port schedulers 308-1.

The plurality of different port schedulers 308-1 may be implemented or configured to make or push corresponding selections or picks from the plurality of different port selection buffer bundles (e.g., "Port 0 Buffer" to "Port M Buffer", ... "Port N Buffer" to "Port Z Buffer", etc.) into the plurality of port bundle selection buffers (e.g., "Port Bundle 0" to "Port Bundle X", etc.). More specifically, each of the plurality of different port schedulers may be implemented or configured to make or push selections or picks from the corresponding port selection buffer bundles (e.g., "Port 0 Buffer" to "Port M Buffer", etc.) of the plurality of different port selection buffer bundles into the corresponding port bundle selection buffer (e.g., "Port Bundle 0", etc.) of the plurality of port bundle selection buffers. The port bundle selection buffers as described herein may contain buffer entries, each of which may have a data structure similar to the port selection buffer entries in the port selection buffer.

Techniques are described herein, including but not limited to port bundle scheduling techniques, which can be used to perform scheduling operations for transmitting or delivering packets at relatively high bandwidths or transmission/delivery rates. Under these techniques, timing risks including but not limited to starvation can be prevented or significantly reduced.

Since queues may be activated or scheduled with minimized latency by using port selection buffers and queue selection buffers to prepare packets for transmission or delivery, relatively low latency in queuing, buffering, scheduling, transmission, and/or delivery may be achieved.

Additionally, optionally or alternatively, these techniques including but not limited to port bundle scheduling 316 (or corresponding port bundle scheduler) can be scaled to relatively high individual and/or overall throughput or port rate of the port of network node/switch. The timing loop of the port scheduler and the queue scheduler in various system configurations of the multi-stage scheduler as described herein can be separate or independent. Each of some or all of the port schedulers and the queue scheduler in the multi-stage scheduler can support multiple dequeues per clock cycle, operate at a relatively high frequency, and/or work effectively with a relatively high port density (e.g., using port bundle scheduling 316, etc.).

4.0. Exemplary Embodiments

FIG5 illustrates an example processing flow according to an embodiment. The various elements of the flow described below may be performed by one or more network devices implemented using one or more computing devices. In block 502, a queue scheduler of a multi-stage scheduler buffers a plurality of packet metadata sets of a plurality of incoming packets in a plurality of queue selection buffers associated with a port of a network node.

In block 504, a port scheduler of the multi-level scheduler buffers one or more sets of packet metadata for one or more outgoing packets in a port selection buffer associated with a port.

In block 506, at a selection clock cycle, when a port scheduler of a multi-level scheduler of a network node selects a subset of one or more packet metadata sets for a subset of one or more outgoing packets from a port selection buffer, a queue scheduler of the port simultaneously selects one or more second packet metadata sets for one or more incoming packets among a plurality of incoming packets from a plurality of packet metadata sets stored in a plurality of queue selection buffers for a plurality of packet queues set for the port.

In block 508, the queue scheduler adds one or more sets of second outgoing packet metadata for the one or more second outgoing packets to a port selection buffer of the port.

In an embodiment, each queue selection buffer of the plurality of queue selection buffers is associated with a corresponding packet queue of the plurality of packet queues set for the port.

In an embodiment, each of the one or more sets of packet metadata is for a corresponding outgoing packet of the one or more outgoing packets.

In an embodiment, each queue selection buffer in the plurality of queue selection buffers comprises a corresponding set of per-queue indicators, wherein the corresponding set of per-queue indicators comprises one or more of the following: a queue empty state indicator, a queue empty indicator at pickup, a packet end indicator at pickup, and the like.

In an embodiment, each of the plurality of packet metadata sets is for a corresponding incoming packet of the plurality of incoming packets; the packet metadata set of the corresponding incoming packet includes one or more of the following: a packet copy count, a packet transfer count, etc.

In an embodiment, the port belongs to multiple ports of a network node; the multi-level scheduler also executes: buffering a second plurality of packet metadata sets for a second plurality of incoming packets in a second plurality of queue selection buffers associated with a second port among the multiple ports of the network node; buffering one or more third packet metadata sets for one or more second outgoing packets in a second port selection buffer associated with the second port; in a selection clock cycle, when a second subset of one or more third packet metadata sets for a second subset of one or more second outgoing packets is selected from the second port selection buffer by a port scheduler of the network node, simultaneously executing for the second plurality of packet queues by a second queue scheduler of the second port: selecting one or more fourth packet metadata sets for one or more second incoming packets in the second plurality of incoming packets from the second plurality of packet metadata sets stored in the second plurality of queue selection buffers; and adding one or more fourth packet metadata sets for one or more fourth outgoing packets to the second port selection buffer of the second port.

In an embodiment, the port scheduler implements a work-saving time-division multiplexing selection method.

In an embodiment, the queue scheduler performs one of the following: a strict priority-based selection method, a weighted dynamic polling selection method, a weighted polling selection method, a threshold-based selection method, a combination of two or more different selection methods, and the like.

In an embodiment, a computing device such as a switch, a router, a line card in a chassis, a network device, etc. is configured to perform any of the foregoing methods. In an embodiment, an apparatus includes a processor and is configured to perform any of the foregoing methods. In an embodiment, a non-transitory computer-readable storage medium stores software instructions that, when executed by one or more processors, implement the execution of any of the foregoing methods.

In an embodiment, a computing device includes one or more processors and one or more storage media storing a set of instructions that, when executed by the one or more processors, enable the performance of any of the foregoing methods.

Note that although separate embodiments are discussed herein, any combination of the embodiments and/or portions of the embodiments discussed herein may be combined to form additional embodiments. 5.0. Implementation Mechanism - Hardware Overview

According to an embodiment, the technology described herein is implemented by one or more special-purpose computing devices. The special-purpose computing device can be a desktop computer system, a portable computer system, a handheld device, a network device, or any other device incorporating hard wiring and/or program logic to implement these technologies. The special-purpose computing device can be hard-wired to perform these technologies, or can include a digital electronic device that is permanently programmed to perform these technologies, such as one or more application-specific integrated circuits (ASICs) or field programmable gate arrays (FPGAs). Such a special-purpose computing device can also combine custom hard-wired logic, ASICs, FPGAs, or other circuit devices with custom programming to complete these technologies.

Although some of the foregoing techniques are described with respect to hardware implementations, which provide many advantages in certain embodiments, it should also be appreciated that in other embodiments, the foregoing techniques may still provide certain advantages when implemented partially or entirely in software. Therefore, in such embodiments, suitable implementation means include a general-purpose hardware processor and are configured to perform any of the foregoing methods by executing program instructions in firmware, memory, other storage devices, or a combination thereof.

FIG6 is a block diagram illustrating an example computer system 600 that can be used to implement the above-described techniques according to an embodiment. The computer system 600 can be, for example, a desktop computing device, a laptop computing device, a tablet computer, a smart phone, a server device, a computing host, a multimedia device, a handheld device, a network device, or any other suitable device. In an embodiment, FIG6 constitutes a different view of the devices and systems described in the previous section.

The computer system 600 may include one or more ASICs, FPGAs, or other specialized circuit devices 603 for implementing the program logic described herein. For example, the circuit device 603 may include fixed and/or configurable hardware logic blocks, input/output (I/O) blocks, hardware registers or other embedded memory resources such as random access memory (RAM) for storing various data, etc., for implementing some or all of the described techniques. The logic blocks may include, for example, an arrangement of logic gates, flip-flops, multiplexers, etc., which are configured to generate output signals based on logic operations performed on input signals.

Additionally and/or alternatively, the computer system 600 may include one or more hardware processors 604 configured to execute software-based instructions. The computer system 600 may also include one or more buses 602 or other communication mechanisms for transferring information. The bus 602 may include various internal and/or external components, including but not limited to an internal processor or memory bus, a serial ATA bus, a PCI Express bus, a universal serial bus, a HyperTransport bus, an Infiniband bus, and/or any other suitable wired or wireless communication channel.

The computer system 600 also includes one or more memories 606, such as RAM, hardware registers, or other dynamic or volatile storage devices, for storing data units to be processed by one or more ASICs, FPGAs, or other dedicated circuit devices 603. The memory 606 may also or alternatively be used to store information and instructions to be executed by the processor 604. The memory 606 may be directly connected to or embedded in the circuit device 603 or the processor 604. Alternatively, the memory 606 may be coupled to the bus 602 and accessed via the bus 602. The memory 606 may also be used to store temporary variables, data units describing rules or policies, or other intermediate information during the execution of program logic or instructions.

The computer system 600 also includes one or more read only memories (ROM) 608 or other static storage devices coupled to the bus 602 for storing static information and instructions for the processor 604. One or more storage devices 610, such as solid state drives (SSDs), magnetic disks, optical disks, or other suitable non-volatile storage devices, may optionally be provided and coupled to the bus 602 for storing information and instructions.

In an embodiment, the computer system 600 may also include one or more communication interfaces 618 coupled to the bus 602. The communication interface 618 provides a data communication coupling that is usually bidirectional to a network link 620 connected to a local network 622. For example, the communication interface 618 may be an integrated services digital network (ISDN) card, a cable modem, a satellite modem, or a modem that provides a data communication connection to a telephone line of a corresponding type. As another example, the one or more communication interfaces 618 may include a local area network (LAN) card to provide a data communication connection to a compatible LAN. As yet another example, the one or more communication interfaces 618 may include a wireless network interface controller, such as a 602.11-based controller, a Bluetooth controller, a long-term evolution (LTE) modem, and/or other types of wireless interfaces. In any such implementation, the communication interface 618 sends and receives electrical, electromagnetic, or optical signals that carry digital data streams representing various types of information.

The network link 620 typically provides data communication to other data devices through one or more networks. For example, the network link 620 may provide a connection to a host computer 624 or to a data device operated by a service provider 626 through a local network 622. The service provider 626, which may be, for example, an Internet Service Provider (ISP), in turn provides data communication services through a wide area network such as the global packet data communication network now commonly referred to as the "Internet" 628. Both the local network 622 and the Internet 628 use electrical, electromagnetic, or optical signals that carry digital data streams. The signals through the various networks and the signals on the network link 620 and through the communication interface 618 are example forms of transmission media that carry digital data to and from the computer system 600.

In an embodiment, the computer system 600 may send and receive data units via (one or more) networks, network links 620, and communication interfaces 618. In some embodiments, the data may be data units that the computer system 600 has interrogated and, if necessary, redirected to other computer systems via appropriate network links 620. In other embodiments, the data may be instructions for implementing various processes associated with the described technology. For example, in the Internet example, the server 630 may transmit code requested by an application via the Internet 628, ISP 626, local network 622, and communication interface 618. The received code may be executed by the processor 604 when received and/or stored in the storage device 610 or other non-volatile memory for later execution. As another example, information received via the network link 620 may be interpreted and/or processed by a software component of the computer system 600, such as a web browser, application, or server, which in turn issues instructions to the processor 604 based on the information, possibly via an operating system and/or other intermediate layers of software components.

The computer system 600 may optionally be coupled to one or more displays 612 via bus 602 for presenting information to a computer user. For example, the computer system 600 may be connected to a liquid crystal display (LCD) monitor via a high-definition multimedia interface (HDMI) cable or other suitable cable, and/or to a light-emitting diode (LED) television via a wireless connection (such as a peer-to-peer Wi-Fi Direct connection). Other examples of suitable types of displays 612 may include, but are not limited to, plasma display devices, projectors, cathode ray tube (CRT) monitors, electronic paper, virtual reality headsets, Braille terminals, and/or any other suitable device for outputting information to a computer user. In an embodiment, any suitable type of output device, such as an audio speaker or a printer, may be used in place of the display 612.

One or more input devices 614 are optionally coupled to the bus 602 for transmitting information and command selections to the processor 604. An example of an input device 614 is a keyboard, including alphanumeric keys and other keys. Another type of user input device 614 is a cursor controller 616 such as a mouse, trackball, or cursor direction keys, for delivering direction information and command selections to the processor 604 and for controlling cursor movement on the display 612. The input device typically has two degrees of freedom on two axes, a first axis (e.g., x) and a second axis (e.g., y), which allows the device to specify a position in a plane. Another example of a suitable input device 614 includes a touch screen panel, a camera, a microphone, an accelerometer, a motion detector, and/or other sensors fixed to the display 612. In an embodiment, a network-based input device 614 can be utilized. In such an embodiment, user input and/or other information or commands can be relayed from the input device 614 to a network link 620 on the computer system 600 via a router and/or switch on a local area network (LAN) or other suitable shared network or via a point-to-point network.

As discussed, the computer system 600 may implement the techniques described herein using custom hardwired logic, one or more ASICs or FPGAs 603, firmware, and/or program logic that, in combination with the computer system, enables or programs the computer system 600 to be a special purpose machine. However, according to one embodiment, the techniques herein are performed by the computer system 600 in response to the processor 604 executing one or more sequences of one or more instructions contained in the main memory 606. Such instructions may be read into the main memory 606 from another storage medium, such as the storage device 610. Execution of the sequences of instructions contained in the main memory 606 causes the processor 604 to perform the process steps described herein.

The term "storage medium" as used herein refers to any non-transitory medium that stores data and/or instructions that cause a machine to operate in a particular manner. Such storage media may include non-volatile media and/or volatile media. Non-volatile media include, for example, optical or magnetic disks, such as storage device 610. Volatile media include dynamic memory, such as main memory 606. Common forms of storage media include, for example, floppy disks, diskettes, hard disks, solid-state drives, magnetic tapes or any other magnetic data storage medium, CD-ROMs, any other optical data storage medium, any physical medium with a pattern of holes, RAM, PROMs and EPROMs, FLASH-EPROMs, NVRAMs, any other memory chips or boxes.

Storage media are distinct from transmission media, but can be used in conjunction with transmission media. Transmission media participate in the transfer of information between storage media. For example, transmission media include coaxial cables, copper wires, and optical fibers, including the wires that make up bus 602. Transmission media can also take the form of sound or light waves, such as those generated during radio wave and infrared data communications.

Various forms of media may be involved in delivering one or more sequences of one or more instructions to the processor 604 for execution. For example, the instructions may initially be carried on a disk or solid-state drive of a remote computer. The remote computer may load the instructions into its dynamic memory and use a modem to send the instructions as a modulated signal over a network such as a wired network or a cellular network. The modem local to the computer system 600 may receive the data on the network and demodulate the signal to decode the instructions sent. Appropriate circuitry may then place the data on the bus 602. The bus 602 transfers the data to the main memory 606, from which the processor 604 retrieves and executes the instructions. The instructions received by the main memory 606 may optionally be stored on the storage device 610 before or after execution by the processor 604.

6.0. Extensions and alternatives

As used herein, the terms "first," "second," "some," and "particular" are used as naming conventions to distinguish queries, plans, representations, steps, objects, devices, or other items from one another so that these items can be referenced after they are introduced. Unless otherwise specified herein, the use of these terms does not imply an order, timing, or any other characteristic of the referenced items.

In the accompanying drawings, various components are depicted as being communicatively coupled to various other components via arrows. These arrows merely illustrate certain examples of information flow between components. The direction of arrows or the absence of arrow lines between certain components should not be interpreted as indicating the presence or absence of communication between certain components themselves. In practice, each component may have an appropriate communication interface through which the component may be communicatively coupled to other components as needed to perform any of the functions described herein.

In the foregoing specification, embodiments of the subject matter of the invention have been described with reference to many specific details, which may vary from implementation to implementation. Therefore, the sole and exclusive indicator of the subject matter of the invention, and the indicator of what the applicant intends to be the subject matter of the invention, is the set of claims issued by the present application, including the set of claims in the specific form in which such claims are issued, including any subsequent corrections. In this regard, although specific claim dependencies are set forth in the claims of the present application, it should be noted that features of the dependent claims of the present application may be appropriately combined with features of other dependent claims and with the independent claims of the present application, and not merely in terms of specific dependencies recorded in the claim group. In addition, although separate embodiments are discussed herein, any combination of embodiments and/or portions of embodiments discussed herein may be combined to form additional embodiments.

Any definitions expressly set forth herein for terms contained in such claims shall affect the meaning of such terms as used in the claims. Accordingly, any limitation, element, property, feature, advantage or attribute not expressly recited in a claim shall not limit the scope of such claim in any way. The specification and drawings are, therefore, to be regarded as illustrative rather than restrictive.

Claims (24)

1. A method comprising: buffering a plurality of sets of packet metadata for a plurality of incoming packets in a plurality of queue selection buffers associated with ports of a network node; buffering one or more sets of packet metadata for one or more outgoing packets in a port selection buffer associated with the port; At a selected clock cycle, when a subset of the one or more sets of packet metadata for a subset of the one or more outgoing packets is selected from the port selection buffer by a port scheduler of the network node, a queue scheduler of the port simultaneously performs, for a plurality of packet queues set for the port: selecting one or more second sets of packet metadata for one or more incoming packets of the plurality of incoming packets from among the plurality of sets of packet metadata stored in the plurality of queue selection buffers; The one or more sets of second packet metadata for one or more second outgoing packets are added to the port selection buffer of the port. 2 . The method according to claim 1 , wherein each queue selection buffer of the plurality of queue selection buffers is associated with a corresponding packet queue of the plurality of packet queues set for the port. 3 . The method of claim 1 , wherein each of the one or more sets of packet metadata is for a corresponding outgoing packet of the one or more outgoing packets. 4. The method of claim 1, wherein each of the plurality of queue selection buffers comprises a corresponding set of per-queue indicators; wherein the corresponding set of per-queue indicators comprises one or more of: a queue empty status indicator, a queue empty indicator at pick-up, or a packet end indicator at pick-up. 5. The method according to claim 1, wherein each of the multiple packet metadata sets is used for a corresponding incoming packet among the multiple incoming packets; wherein the packet metadata set of the corresponding incoming packet includes one or more of the following: a packet copy count or a packet transmission count. 6. The method according to claim 1, wherein the port belongs to a plurality of ports of the network node; the method further comprising: buffering a second plurality of sets of packet metadata for a second plurality of incoming packets in a second plurality of queue selection buffers associated with a second port of the plurality of ports of the network node; buffering one or more third sets of packet metadata for one or more second outgoing packets in a second port selection buffer associated with the second port; In the selection clock cycle, when the port scheduler of the network node selects a second subset of the one or more third sets of packet metadata for a second subset of the one or more second outgoing packets from the second port selection buffer, the second queue scheduler of the second port simultaneously performs, for a second plurality of packet queues: selecting one or more fourth sets of packet metadata for one or more second incoming packets of the second plurality of incoming packets from among the second plurality of sets of packet metadata stored in the second plurality of queue selection buffers; The one or more sets of fourth packet metadata for one or more fourth outgoing packets are added to the second port selection buffer of the second port. 7. The method of claim 1, wherein the port scheduler implements a work-saving time-division multiplexing selection method. 8. The method of claim 1, wherein the queue scheduler performs one of the following: a strict priority-based selection method, a weighted dynamic polling selection method, a weighted polling selection method, a threshold-based selection method, or a combination of two or more different selection methods. 9. A system comprising: one or more computing devices; One or more non-transitory computer-readable media storing instructions that, when executed by the one or more computing devices, cause the execution of: buffering a plurality of sets of packet metadata for a plurality of incoming packets in a plurality of queue selection buffers associated with ports of a network node; buffering one or more sets of packet metadata for one or more outgoing packets in a port selection buffer associated with the port; At a selected clock cycle, when a subset of the one or more sets of packet metadata for a subset of the one or more outgoing packets is selected from the port selection buffer by a port scheduler of the network node, a queue scheduler of the port simultaneously performs, for a plurality of packet queues set for the port: selecting one or more second sets of packet metadata for one or more incoming packets of the plurality of incoming packets from among the plurality of sets of packet metadata stored in the plurality of queue selection buffers; The one or more sets of second packet metadata for one or more second outgoing packets are added to the port selection buffer of the port. 10. The system of claim 9, wherein each queue selection buffer of the plurality of queue selection buffers is associated with a corresponding packet queue of the plurality of packet queues set for the port. 11. The system of claim 9, wherein each of the one or more sets of packet metadata is for a corresponding outgoing packet of the one or more outgoing packets. 12. A system according to claim 9, wherein each queue selection buffer of the multiple queue selection buffers includes a corresponding per-queue indicator set; wherein the corresponding per-queue indicator set includes one or more of the following: a queue empty status indicator, a queue empty indicator at pick-up, or a packet end indicator at pick-up. 13. A system according to claim 9, wherein each of the multiple packet metadata sets is used for a corresponding incoming packet among the multiple incoming packets; wherein the packet metadata set for the corresponding incoming packet includes one or more of the following: a packet copy count or a packet transmission count. 14. The system of claim 9, wherein the port belongs to a plurality of ports of the network node; wherein the instructions, when executed by the one or more computing devices, further cause execution of: buffering a second plurality of sets of packet metadata for a second plurality of incoming packets in a second plurality of queue selection buffers associated with a second port of the plurality of ports of the network node; buffering one or more third sets of packet metadata for one or more second outgoing packets in a second port selection buffer associated with the second port; In the selection clock cycle, when the port scheduler of the network node selects a second subset of the one or more third sets of packet metadata for a second subset of the one or more second outgoing packets from the second port selection buffer, the second queue scheduler of the second port simultaneously performs, for a second plurality of packet queues: selecting one or more fourth sets of packet metadata for one or more second incoming packets of the second plurality of incoming packets from among the second plurality of sets of packet metadata stored in the second plurality of queue selection buffers; The one or more sets of fourth packet metadata for one or more fourth outgoing packets are added to the second port selection buffer of the second port. 15. The system of claim 9, wherein the port scheduler implements a work-saving time-division multiplexing selection method. 16. The system of claim 9, wherein the queue scheduler performs one of the following: a strict priority-based selection method, a weighted dynamic polling selection method, a weighted polling selection method, a threshold-based selection method, or a combination of two or more different selection methods. 17. One or more non-transitory computer-readable media storing instructions that, when executed by one or more computing devices, cause the execution of: buffering a plurality of sets of packet metadata for a plurality of incoming packets in a plurality of queue selection buffers associated with ports of a network node; buffering one or more sets of packet metadata for one or more outgoing packets in a port selection buffer associated with the port; At a selected clock cycle, when a subset of the one or more sets of packet metadata for a subset of the one or more outgoing packets is selected from the port selection buffer by a port scheduler of the network node, a queue scheduler of the port simultaneously performs, for a plurality of packet queues set for the port: selecting one or more second sets of packet metadata for one or more incoming packets of the plurality of incoming packets from among the plurality of sets of packet metadata stored in the plurality of queue selection buffers; The one or more sets of second packet metadata for one or more second outgoing packets are added to the port selection buffer of the port. 18. The one or more non-transitory computer-readable media of claim 17, wherein each queue selection buffer of the plurality of queue selection buffers is associated with a corresponding packet queue of the plurality of packet queues set for the port. 19. The one or more non-transitory computer-readable media of claim 17, wherein each of the one or more sets of packet metadata is for a corresponding outgoing packet of the one or more outgoing packets. 20. One or more non-transitory computer-readable media according to claim 17, wherein each queue selection buffer of the plurality of queue selection buffers comprises a corresponding set of per-queue indicators; wherein the corresponding set of per-queue indicators comprises one or more of: a queue empty status indicator, a queue empty indicator at pick-up, or a packet end indicator at pick-up. 21. One or more non-transitory computer-readable media according to claim 17, wherein each of the multiple packet metadata sets is used for a corresponding incoming packet among the multiple incoming packets; wherein the packet metadata set for the corresponding incoming packet includes one or more of the following: a packet copy count or a packet transmission count. 22. The one or more non-transitory computer-readable media of claim 17, wherein the port belongs to a plurality of ports of the network node; wherein the instructions, when executed by the one or more computing devices, further cause execution of: buffering a second plurality of sets of packet metadata for a second plurality of incoming packets in a second plurality of queue selection buffers associated with a second port of the plurality of ports of the network node; buffering one or more third sets of packet metadata for one or more second outgoing packets in a second port selection buffer associated with the second port; In the selection clock cycle, when the port scheduler of the network node selects a second subset of the one or more third sets of packet metadata for a second subset of the one or more second outgoing packets from the second port selection buffer, the second queue scheduler of the second port simultaneously performs, for a second plurality of packet queues: selecting one or more fourth sets of packet metadata for one or more second incoming packets of the second plurality of incoming packets from among the second plurality of sets of packet metadata stored in the second plurality of queue selection buffers; The one or more sets of fourth packet metadata for one or more fourth outgoing packets are added to the second port selection buffer of the second port. 23. The one or more non-transitory computer-readable media of claim 17, wherein the port scheduler implements a work-saving time-division multiplexing selection method. 24. One or more non-transitory computer-readable media according to claim 17, wherein the queue scheduler performs one of the following: a strict priority-based selection method, a weighted dynamic polling selection method, a weighted polling selection method, a threshold-based selection method, or a combination of two or more different selection methods.