Patent Description:
A computer network is a collection of interconnected network devices that can exchange data and share resources. Example network devices include routers, switches, and other layer two (L2) network devices that operate within layer two of the Open Systems Interconnection (OSI) reference model, i.e., the data link layer, and layer three (L3) network devices that operate within layer three of the OSI reference model, i.e., the network layer. Network devices within computer networks often include a control unit that provides control plane functionality for the network device and forwarding components for routing or switching data units.

A router of a computer network may use one or more queues facilitate bandwidth matching between senders and receivers. The network switch may receive packets from a sender and transmit a portion of the received packets from the sender to a receiver, storing a remaining portion of the received packets in the queue. After transmitting the portion of the received packets, the network switch transmits the remaining portions of the packets stored in the queue to the receiver.

In general, it is often desirable to partition and allocate the resources so as to achieve different Quality of Service (QoS) for different types of packet flows. For example, in response to receiving a packet from the source device, a network device may classify the packet as originating from the source device and identifies a particular priority provisioned in the router for the source device. The network device then typically stores the network packet as one or more discrete data units in one of a number of queues that is associated with the determined priority. The router services the queues in a manner that satisfies each of the defined priorities. For example, during operation, the network device performs dequeue operations in accordance with the provisioned priorities to select network packets from the queues to schedule delivery of the network packets. In some instances, the network device executes multiple dequeue operations in an overlapping manner to concurrently select and service multiple queues. As one example, a network device may implement dequeue and network packet scheduling operations in a pipelined fashion such that multiple network packets are being dequeued and scheduled for processing at any given point in time. By executing these dequeue operations concurrently, the network device improves the number of network packets that can be serviced in a given amount of time.

<CIT> describes techniques are described for allocating virtual output queue (VOQ) buffer space to ingress forwarding units of a network device based on drain rates at which network packets are forwarded from VOQs of the ingress forwarding units. For example, a network device includes multiple ingress forwarding units that each forward network packets to an output queue of an egress forwarding unit. Ingress forwarding units each include a VOQ that corresponds to the output queue. The drain rate at any particular ingress forwarding unit corresponds to its share of bandwidth to the output queue, as determined by the egress forwarding unit. Each ingress forwarding unit configures its VOQ buffer size in proportion to its respective drain rate in order to provide an expected delay bandwidth buffering for the output queue of the egress forwarding unit.

<CIT> describes that a network device, such as a network switch, can include an ingress to receive data packets from a network. The ingress can communicate with an egress included in the network device though a fabric included in the network device. At least one of ingress and the egress can enqueue a data packet prior to receipt of all cells of the data packet. The ingress can also commence with dequeue of the cells of the received data packet prior to receipt of the entire data packet from the network. At least one of ingress and the egress can process the data packets using cut-through processing and store-and-forward processing. In a case of cut-through processing of a data packet at both the ingress and the egress of a network device, such as CIOQ switch, the fabric can be allocated to provide a prioritized virtual channel through the fabric for the data packet.

In general, this disclosure describes techniques for improved queueing systems in network devices. A network device, such as a router or a switch, may enqueue network packets in one or more queues prior to switching internally between packet forwarding engines, or prior to transmitting the packets over the network. A queueing system for a network device may be configured to combine elements of a virtual output queue (VOQ) and combined input output queue (CIOQ). As used herein, a VOQ may refer to a buffer at an ingress side, where each input port maintains a separate virtual queue for each output port. However, maintaining a separate virtual queue for each output port does not scale well. In contrast, a CIOQ may be configured to buffer at an egress side. However, a CIOQ may limit throughput of the network device due to head-of-line (HOL) blocking. For instance, CIOQ may limit throughput of the network device due to HOL blocking across a switching fabric when an input queue aggregates multiple flows intending to reach an egress packet forwarding engine or when multiple ingress packet forwarding engines try to reach the same egress packet forwarding engine and the bandwidth of the egress packet forwarding engine is exceeded.

In accordance with the techniques of the disclosure, a network device may be configured to provide "CIOQ behavior" that enables output queue scaling. For example, the network device may be configured to use virtual output queuing at egress as the local output queue. For instance, the network device may be configured to enqueue a network packet at a VOQ for a packet forwarding engine and the packet forwarding engine will schedule the network packet to be enqueued at a particular port of the packet forwarding engine. In this instance, network device may "loopback" information indicating the network packet in the virtual output queue and that the network packet is to be enqueued at as output queue for the particular port. In this way, the network device may allow queue scale to increase as more packet forwarding engines are added to the system while helping to minimizing head-of-line blocking across the switch fabric.

An embodiment of the invention provides a method that includes: determining, by an ingress packet forwarding engine implemented in processing circuitry, in response to receiving a network packet, an egress packet forwarding engine for outputting the network packet; enqueuing, by the ingress packet forwarding engine, the network packet in a virtual output queue for output to the egress packet forwarding engine, wherein enqueuing the network packet in the virtual output queue comprises enqueuing the network packet in a first portion of a combined buffer for the ingress packet forwarding engine and the egress packet forwarding engine that is assigned to the virtual output queue;outputting, by the egress packet forwarding engine implemented in processing circuitry, in response to a first scheduling event, to the ingress packet forwarding engine, information indicating the network packet in the virtual output queue and that the network packet is to be enqueued at an output queue for an output port of the egress packet forwarding engine, wherein outputting the information comprises outputting metadata comprising the information to the ingress packet forwarding engine;dequeuing, by the ingress packet forwarding engine, in response to receiving the information, the network packet from the virtual output queue and enqueuing, by the ingress packet forwarding engine, the network packet to the output queue, wherein dequeuing the network packet from the virtual output queue comprises dequeuing the network packet from the first portion of the combined buffer, and wherein enqueuing the network packet the network packet to the output queue comprises enqueuing the network packet in a second portion of the combined buffer assigned to the output queue; and dequeuing, by the egress packet forwarding engine, in response to a second scheduling event that is after the first scheduling event, the network packet from the output queue and outputting, by the egress packet forwarding engine, the network packet at the output port.

A second embodiment of the invention provides a computing device comprising means for performing the method of the invention. A third embodiment of the invention provides a computer-readable medium conveying instructions for causing one or more programmable processors to perform the method of the invention.

The details of one or more examples of the techniques of this disclosure are set forth in the accompanying drawings and the description below. Other features, objects, and advantages of the techniques will be apparent from the description and drawings, and from the claims.

Some systems use a Combined Input and Output Queuing (CIOQ) for a large queue scale. In CIOQ systems, a packet buffer, such as, for example, a Delay Bandwidth Buffer (DBB) and Output Queues (OQ) are held at egress along with Congestion Management (CM) and hierarchical scheduling. In some examples, a CIOQ system may include fine grain queueing at ingress. Accordingly, in CIOQ, small fabric Input Queues (IQ) may be used at ingress (e.g., one per destination packet forwarding engine). With CIOQ, the queue scale increases as more packet forwarding engines are added to the system, because network packets fanout at egress per queue.

However, CIOQ systems may suffer from fabric congestion that may be addressed, for example, using fabric overspeed (e.g., 2X) to satisfy Quality of Service (QoS) targets. Fabric congestion may occur when multiple input ports on different packet forwarding engines attempt to reach the same egress OQ. In this example, the CIOQ system may drop network packets at the ingress fabric interface. The ingress fabric queues may aggregate the traffic through relatively small queues (e.g., stored in On-Chip-Memory (OCM)) with only a few priority constrains and without per-queue QoS guarantees.

To avoid the foregoing difficulties associated with CIOQ systems, some network devices may use virtual output queuing. In virtual output queuing, each ingress packet forwarding engine includes a virtual output queue (VOQ) that uniquely identifies an Egress OQ. A VOQ (e.g., one VOQ on each packet forwarding engine) may combine with an OQ to form the queue. The VOQ on ingress may provide a delay bandwidth buffer with only a small OQ at egress (e.g., only at a head of the queue is available at egress for scheduling to a port). Because the DBB is kept at ingress in virtual output queuing, such systems may omit techniques for mitigating head-of-line blocking across the switch fabric. Such head-of-line blocking may be due to the egress scheduling of the VOQ, which together with fair fabric scheduling may use little or no overspeed.

Virtual output queuing, however, may lack OQ scaling. Because each ingress packet forwarding engine may use a VOQ for each egress OQ, the number of VOQ on the ingress packet forwarding engine determines a maximum OQ scale. As such, rather than increasing queue scale as more packet forwarding engines are added, in the case of CIOQ systems, the VOQ system may have a maximum number of OQ that is determined by the number of VOQ on the ingress packet forwarding engine (e.g., <NUM>,<NUM> OQs), considering that ingress memory committed to queueing is finite and may not be easily upgraded to add additional storage capacity. Because the total number of OQ does not grow with the addition of packet forwarding engines, the average number of OQ per packet forwarding engine becomes smaller as more packet forwarding engines are added to a system. For a hierarchical quality of service solution, systems using virtual output queues may limit a number of packet forwarding engines supported in a system to a small number (e.g., <NUM> or <NUM> packet forwarding engines).

Techniques described herein describe a system configured to provide "CIOQ behavior" that enables OQ scaling in stand-alone (e.g., combined buffer (CBUF) local switching) and fabric based systems. In some examples, a system may use virtual output queues at egress as the OQ. For instance, a system may enqueue a network packet at a VOQ for a packet forwarding engine and the packet forwarding engine will schedule the network packet to be enqueued at a particular port of the packet forwarding engine. In this instance, the system may "loopback" information (e.g., packet header with packet payload, only meta data, etc.) indicating the network packet in the virtual output queue and that the network packet is to be enqueued as an output queue for the particular port. Techniques described may include a system that may loopback the information locally using metadata. In some examples, a system may loopback the information by looping back the network packet with a header and a packet payload for the network packet. In this way, the system may allow queue scale to increase as more packet forwarding engines are added to the system while helping to minimize head-of-line blocking across the switch fabric. For example, the system may have some head-of-line blocking if multiple flows aggregate through a single ingress queue on an ingress packet forwarding engine but are later separated out into separate output queues at an egress packet forwarding engine.

<FIG> is a block diagram illustrating an example system <NUM> in which network <NUM> includes routers 106A-106B (collectively, routers <NUM>). Devices 110A-110N (collectively, devices <NUM>) connect to network <NUM> via routers <NUM> in order to access resources provided by network <NUM>. Each of devices <NUM> may be an end-user computing device, such as a personal computer, a laptop computer, a mobile telephone, a network telephone, a television set-top box, a video game system, a point-of-sale device, a personal digital assistant, an intermediate network device, a network appliance, a supercomputer, a mainframe computer, an industrial robot, or another type of device capable of interfacing with and communicating over network <NUM>.

Network <NUM> may include a plurality of network devices that facilitate the access of content by devices <NUM>. Each of the plurality of network devices may comprise one of a router (e.g., routers <NUM>), a switch, a server, a database server, a hub, a firewall, an Intrusion Detection/Prevention (IDP) device and/or any other type of networking equipment or device that facilitates the transfer of data to and from devices <NUM>. Network <NUM> includes routers <NUM>, which communicate using various protocols, such as the Border Gateway Protocol and the Internet Control Message Protocol, in order to exchange routing, network configuration information, and other information. The network may be a local area network ("LAN"), such as a token ring or Ethernet network, a virtual local area network ("VLAN"), or another type of network. The network may comprise one or more wired or wireless links. For example, network <NUM> may be an Ethernet network that comprises one or more Ethernet cables. In another example, the network may be a Wireless Fidelity ("Wi-Fi") network that uses wireless radio transmissions to communicate information. In another example, network <NUM> may be a mobile network. Although shown as a single network <NUM> in <FIG>, network <NUM> may comprise any number of interconnected networks, either public or private, in which the various networks interconnect to form one or more virtual networks.

Network <NUM> provides a variety of resources that may be accessed by devices <NUM>. In the example of <FIG>, network <NUM> includes content server <NUM> that stores or otherwise sources content, which, as the term is used herein, refers to any data commonly transmitted and/or stored within a network, such as web-based applications, images, documents, web pages, video data, audio data such as voice, web-based games, scripts, or any other type of network-based content. Network <NUM> may support multicast techniques to improve the delivery efficiency of data transmitted with the network. Typically network <NUM> will also connect to a variety of other types of devices (e.g., file servers, printers, telephones, and e-mail and other application servers). Network <NUM> is also shown coupled to public network <NUM> (e.g., the Internet) via router 106B. Public network <NUM> may include, for example, one or more client computing devices. Public network <NUM> may provide access to web servers, application servers, public databases, media servers, end-user devices, and many other types of network resource devices and content.

Network <NUM> may transmit content to devices <NUM> through router 106A using one or more packet-based protocols, such as an Internet Protocol (IP) / Transmission Control Protocol (TCP). In this respect, network <NUM> may support the transmission of data via discrete data units, often referred to as "network packets," or simply "packets. " As a result, network <NUM> may be referred to as a "packet-based" or "packet switched" network. While described in this disclosure as transmitting, conveying, or otherwise supporting packets, network <NUM> may transmit data according to any other discrete data unit defined by any other protocol, such as a cell defined by the Asynchronous Transfer Mode (ATM) protocol, or a datagram defined by the User Datagram Protocol (UDP).

Network traffic delivered by network <NUM> may be classified according to a number of categories. For instance, content server <NUM> may stream live video to one of devices <NUM> through router 106A. Packets that transmit such video may be classified as streaming multimedia packets. Content server <NUM> may also send web pages to one of devices <NUM> using HTTP packets. As another example, information exchanged by routers <NUM> may be categorized as network management traffic. In addition to being classified by application, network traffic may be classified by source or destination, user, protocol, and port (for TCP and UDP), among others characteristics.

Various categories of network traffic may require a certain level of network performance. For example, streaming multimedia may require guaranteed bandwidth to provide an acceptable user experience. As another example, network management traffic should experience low delays in order to maintain the efficiency of a network. Also, internet service providers (ISPs) may prioritize traffic for certain users over others based on a service provider agreement. To meet these requirements, network <NUM> includes mechanisms to support Quality of Service (QoS) guarantees according to a number of predefined QoS levels.

Routers <NUM> receive, analyze, and classify packets to assign the packets to a suitable priority level. In addition to classifying packets, routers <NUM> process the received and classified packets according to their priority level. In this manner, routers <NUM> implement aspects of the QoS guarantees provided by network <NUM>. In addition, based on information received from other devices in system <NUM>, routers <NUM> determine the appropriate route through the system for each received packet and forwards the packet accordingly.

Routers <NUM> may regulate a speed at which packets are transmitted to prevent flooding on the network. For example, routers <NUM> may include a token bucket shaper that spends "tokens" to dequeue a corresponding amount of bytes from a queue and transmit them over the network, and may not transmit packets if the token bucket shaper has insufficient tokens to spend. In other words, each token may correspond to a number of bytes that the token bucket shaper is permitted to dequeue from the queue and transmit over the network. In this way, the token bucket shaper acts to regulate the speed at which packets are removed from the queue and transmitted on the network.

Some routers may use a CIOQ techniques, that use a delay bandwidth buffer and output queues that hold packets at egress along with congestion management and hierarchical scheduling. In this example, a CIOQ system may use fabric input queues at ingress (e.g., one per destination packet forwarding engine). As such, the queue scale increases as more packet forwarding engines are added to the CIOQ system, because network packets fanout at egress per queue. However, CIOQ systems may suffer from fabric congestion that may be addressed, for example, using fabric overspeed (e.g., 2X) to satisfy Quality of Service (QoS) targets. Fabric congestion may occur when multiple input ports on different packet forwarding engines attempt to reach the same egress OQ. In this example, the CIOQ system may drop network packets at the ingress fabric interface. The ingress fabric queues may aggregate the traffic through relatively small queues (e.g., stored in On-Chip-Memory (OCM)) with only a few priority constrains and without per-queue QoS guarantees.

Some network devices may use virtual output queuing. In virtual output queuing, a router may use a virtual output queue (VOQ) that uniquely identifies an egress OQ. A VOQ (e.g., one VOQ on each packet forwarding engine) may combine with an OQ to form the queue. The VOQ on ingress may provide a delay bandwidth buffer with only a small OQ at egress (e.g., only at a head of the queue is available at egress for scheduling to a port). Because the delay bandwidth buffer is kept at ingress in virtual output queuing, systems using VOQ techniques may omit techniques for mitigating head-of-line blocking across the switch fabric. Routers configured to use virtual output queuing, however, may lack OQ scaling. Because each ingress packet forwarding engine may use a VOQ for each egress OQ, the number of VOQ on the ingress packet forwarding engine determines a maximum OQ scale.

In accordance with the techniques of the disclosure, routers <NUM> may be configured to provide "CIOQ behavior" that enables OQ scaling in stand-alone (e.g., combined buffer (CBUF) local switching) and fabric based systems. For example, router 106A may be configured to use virtual output queues at egress as the OQ. For instance, router 106A may be configured to enqueue a network packet at a VOQ for an egress packet forwarding engine and the egress packet forwarding engine will schedule the network packet to be enqueued at a particular port of the packet forwarding engine. In this instance, router 106A may "loopback," to an ingress packet forwarding engine, information indicating the network packet in the virtual output queue and that the network packet is to be enqueued at an output queue for the particular port. Techniques described may include a system that may loopback the information locally using metadata. In some examples, router 106A may loopback the information by looping back the network packet with a header and a packet payload for the network packet. In this way, router 106A may allow queue scale to increase as more packet forwarding engines are added to the system while helping to minimize head-of-line blocking across the switch fabric.

In operation, router 106A may determine, in response to receiving a network packet, an egress packet forwarding engine for outputting the network packet. For example, router 106A may determine an egress packet forwarding engine of router 106A. In some examples, router 106A may determine the egress packet forwarding engine that corresponds to a next hop. For instance, router 106A may determine, in response to determining that a packet label of the network packet specifies an IP address, a next-hop for the network packet. In this instance, router 106A may determine the egress packet forwarding engine assigned to a port that corresponds to the next-hop for the network packet.

Router 106A may enqueue the network packet in a virtual output queue for output to the egress packet forwarding engine. For example, router 106A stores the network packet (e.g., packet payload, packet header, etc.) at the virtual output queue. In response to a first scheduling event, router 106A may output, to the ingress packet forwarding engine, information indicating the network packet in the virtual output queue and that the network packet is to be enqueued at an output queue for an output port of the egress packet forwarding engine. For example, router 106A may determine, using quality of service for different types of packet flows and/or a dequeue rate, to schedule the network packet for queueing by the egress packet forwarding engine for processing by the egress packet forwarding engine. To output the information, router 106A may output a network packet via a port of the egress router to a port of the ingress router a packet payload for the network packet and a header for the network packet that includes the information. In some examples, to output the information, router 106A may output metadata using local switching (e.g., using a combined buffer) without outputting the packet payload.

In response to receiving the information, the ingress packet forwarding engine of router 106A may dequeue the network packet from the virtual output queue. For example, router 106A may remove the network packet (e.g., packet payload and packet header) and/or a pointer representing the network packet from the virtual output queue. Router 106A may enqueue the network packet to the output queue. For example, router 106A may add the network packet and/or a pointer representing the network packet to the output queue.

In response to a second scheduling event that is after the first scheduling event, router 106A may dequeue the network packet from the output queue and output the network packet at the output port. For example, router 106A may determine, using quality of service for different types of packet flows and/or a dequeue rate, to schedule the network packet for queueing by the egress packet forwarding engine at an output queue for the output port. In response to the second scheduling event, router 106A may output the network packet (e.g., packet payload and packet header) at the output port and remove the network packet (e.g., packet payload and packet header) and/or a pointer representing the network packet from the output queue for the output port.

In this way, router 106A may have higher scalability compared to routers that use VOQ. For example, using techniques described herein, router 106A may increase the output queue scale, which may help to support a larger number of customers, thereby improving an operation of a router. For example, assuming each packet forwarding engine of four packet forwarding engines supports <NUM>,<NUM> queues, the combination of the four packet forwarding engines using VOQ techniques may support only <NUM>,<NUM> queues. However, in accordance with the techniques of the disclosure, the combination of four packet forwarding engines using combined buffer techniques may support <NUM>,<NUM> queues (i.e., 4x48,<NUM>), which may allow the router to support additional customers and, therefore, may improve a performance of router 106A. In some examples, router 106A may have a lower product cost compared to routers configured to use CIOQ. Additionally, techniques described herein may be used with VOQ techniques and/or CIOQ. For instance, router 106A may use VOQ for internet facing traffic and techniques described herein using a combined buffer for inbound traffic from the internet (e.g., for customer queueing).

Routers <NUM> may use techniques described herein to use a virtual output queue as an output queue. However, in some examples, some of routers <NUM> may use other techniques, such as, for example, virtual output queueing, CIOQ, or another queueing technique. Although the principles described herein are discussed with reference to routers <NUM>, other network devices, such as, for example, but not limited to, an Asynchronous Transfer Mode (ATM) switch, a local area network (LAN) switch, an interface card, a gateway, a firewall, or another device of system <NUM> may determine a predicted lifetime.

<FIG> is a block diagram illustrating an example router <NUM> within network <NUM> of <FIG> in accordance with the techniques of the disclosure. In general, router <NUM> may operate substantially similar to routers <NUM> of <FIG>. In this example, router <NUM> includes interface cards 230A-230N ("IFCs <NUM>") that receive network packets via incoming links 232A-232N ("incoming links <NUM>") and send network packets via outbound links 234A-234N ("outbound links <NUM>"). IFCs <NUM> may be coupled to links <NUM>, <NUM> via a number of interface ports. Router <NUM> may include a control unit <NUM> that determines routes of received packets and forwards the packets accordingly via IFCs <NUM>, in communication with control unit <NUM>.

Control unit <NUM> includes a routing engine <NUM> and a packet forwarding engine <NUM>. Routing engine <NUM> operates as the control plane for router <NUM> and includes an operating system (not shown) that provides a multi-tasking operating environment for execution of a number of concurrent processes. Routing engine <NUM>, for example, executes software instructions to implement one or more control plane networking protocols <NUM>. For example, protocols <NUM> may include one or more routing protocols, such as BGP <NUM>, for exchanging routing information with other routing devices and for updating routing information base (RIB) <NUM>. Protocols <NUM> may further include transport protocols, such as Multiprotocol Label Switching (MPLS) protocol <NUM>, and multicast management protocols, such as Internet Group Management Protocol (IGMP) <NUM>. In other examples, protocols <NUM> may include other routing, transport, management, or communication protocols.

In some examples, routing engine <NUM> includes command line interface (CLI) <NUM> to permit an administrator to configure and/or manage router <NUM>. For example, the administrator may, via CLI <NUM>, access queue manager <NUM> to configure one or more parameters of packet forwarding engines <NUM>. In another example, routing engine <NUM> includes a graphical user interface (GUI) instead of a CLI. In a still further example, routing engine executes Simple Network Management Protocol (SMNP) <NUM> to permit the administrator to configure and/or control router <NUM> from a remote terminal.

Routing protocol daemon (RPD) <NUM> may execute BGP <NUM> or other routing protocols to update RIB <NUM>. RIB <NUM> describes a topology of the computer network in which router <NUM> resides, and also includes routes through the computer network. RIB <NUM> describes various routes within the computer network, and the appropriate next hops for each route, i.e., the neighboring routing devices along each of the routes. RPD <NUM> analyzes information stored in RIB <NUM> and generates forwarding information for packet forwarding engine <NUM>, which stores the forwarding information in forwarding information base (FIB) <NUM>. RPD <NUM> may, in other words, resolve routing information stored by RIB <NUM> to obtain the forwarding information identifying a next hop for each destination within the network, storing the forwarding information to FIB <NUM>.

Combined buffer ("CBUF") <NUM> may act as queue storage for packet forwarding engines <NUM> of router <NUM>. CBUF <NUM> may include local memory (e.g., on chip memory (OCM)) and/or external memory (e.g., High Bandwidth Memory (HBM)). In accordance with the techniques of the disclosure, CBUF <NUM> may store queues for router <NUM>. In some examples, CBUF <NUM> comprises random access memory (RAM), read only memory (ROM), programmable read only memory (PROM), erasable programmable read only memory (EPROM), electronically erasable programmable read only memory (EEPROM), flash memory, comprising executable instructions for causing the one or more processors to perform the actions attributed to them.

CBUF <NUM> may include one or more queues that are a first-in first-out (FIFO) data structure for organization and temporary storage of data. In the example of <FIG>, queues of CBUF <NUM> may store one or more network packets for router <NUM>. For example, router <NUM> may store the one or more packets in one or more queues of CBUF <NUM> prior to switching internally between packet forwarding engines <NUM>. In another example, router <NUM> may store the one or more packets in one or more queues of CBUF <NUM> prior to transmitting the network packets over the network.

For example, CBUF <NUM> may include virtual output queues 227A-227N (collectively referred to herein as "VOQs <NUM>) and/or output queues 219A-219N (collectively referred to herein as "OQs <NUM>). In some examples, each VOQ of VOQs <NUM> may be assigned to a respective packet forwarding engine of packet forwarding engines <NUM>. For instance, VOQ 227A may be assigned to a first packet forwarding engine of packet forwarding engines <NUM>, VOQ 227B may be assigned to a second packet forwarding engine of packet forwarding engines <NUM>, and so on. Each OQ of OQs <NUM> may be assigned to a respective port of packet forwarding engine of packet forwarding engines <NUM>. For instance, OQ 219A may be assigned to a first port of a first packet forwarding engine of packet forwarding engines <NUM>, OQ 219B may be assigned to a second port of the first packet forwarding engine, and so on.

Packet forwarding engine <NUM> operates as the data plane for router <NUM> and includes FIB <NUM>, shaper credit update engine <NUM> and queue manager <NUM>. Packet forwarding engine <NUM>, for example, processes packets forwarded and received by router <NUM> via IFCs <NUM>. For example, packet forwarding engine <NUM> may apply filters and routing policies to outgoing packets and forward the packets to a next hop in the network. In some examples, control unit <NUM> includes a plurality of packet forwarding engines, each of which are configured to operate similar to packet forwarding engine <NUM> to provide packet forwarding functions for different flows of network traffic. As used herein, ingress packet forwarding engine and egress packet forwarding engine are merely terms for providing context relating to a specific network packet. That is, all packet forwarding engines <NUM> may act as an ingress packet forwarding engine when receiving packets and an egress packet forwarding engine when transmitting network packets. In some examples, a single packet forwarding engine may act as both the ingress packet forwarding engine and the egress packet forwarding engine for a single packet.

FIB <NUM> may associate, for example, network destinations for network traffic with specific next hops and corresponding IFCs <NUM> and physical output ports for output links <NUM>. FIB <NUM> may be a radix tree programmed into dedicated forwarding chips, a series of tables, a complex database, a link list, a radix tree, a database, a flat file, or various other data structures. In some examples, FIB <NUM> includes lookup structures. Lookup structures may, given a key, such as an address, provide one or more values. In some examples, the one or more values may be one or more next hops. A next hop may be implemented as microcode, which when executed, performs one or more operations. One or more next hops may be "chained," such that a set of chained next hops perform a set of operations for respective different next hops when executed. Examples of such operations may include applying one or more services to a network packet, dropping a network packet, and/or forwarding a network packet using an interface and/or interface identified by the one or more next hops. As shown, FIB <NUM> may include an Ingress Packet Processor (IPP) <NUM> and an Egress Packet Processor (EPP <NUM>). IPP <NUM> may determine a packet forwarding engine of packet forwarding engines <NUM> that acts as an egress packet forwarding engine for a network packet. EPP <NUM> may determine output queue forward statistics at egress.

Queue manager <NUM> of packet forwarding engine <NUM> may work with shaper credit update engine <NUM> to perform management functions for VOQs <NUM> and OQs <NUM>. For example, shaper credit update engine <NUM> may implement token bucket shaper data structures to determine dequeue rates for VOQs <NUM>. In this example, queue manager <NUM> may regulate a flow of network packets to VOQs <NUM> using the dequeue rates specified by shaper credit update engine <NUM>. Similarly, shaper credit update engine <NUM> may implement token bucket shaper data structures to determine dequeue rates for OQs <NUM>. In this example, queue manager <NUM> regulates the flow of network packets from OQs <NUM> using the dequeue rates specified by shaper credit update engine <NUM>. Shaper credit update engine <NUM> is described further with reference to <FIG>.

In accordance with techniques described herein, packet forwarding engines <NUM> may be configured to reuse VOQs <NUM> (e.g., ingress VOQs) as egress OQs. For instance, a first packet forwarding engine of packet forwarding engines <NUM> may act as an ingress packet forwarding engine that uses VOQ 227A as an ingress VOQ. In this example, VOQ <NUM> may be "reused" as an egress OQ by a second packet forwarding engine of packet forwarding engines <NUM>. In this instance, the egress packet forwarding engine may "loopback," to the ingress packet forwarding engine, information indicating the network packet in VOQ <NUM> and that the network packet is to be enqueued at an OQ 219A for the particular port. In some examples, one or more packet forwarding engines of packet forwarding engines <NUM> may use VOQs <NUM> as VOQs at ingress. Because the total number of OQ grows with the addition of packet forwarding engines, the average number of OQ per packet forwarding engine becomes larger as more packet forwarding engines are added to a system. In this way, OQ scaling may occur when multiple packet forwarding engines are added to a system (e.g., <NUM>,<NUM> per packet forwarding engine).

Each OQ of OQs <NUM> may be scheduled to an egress port, which may place queueing at an egress port. Ingress packet forwarding engines of packet forwarding engines <NUM> may support a small number of fabric input queue (e.g., one of VOQs <NUM>) per destination packet forwarding engine with OQ. For instance, queue manager <NUM> may use one VOQ per destination packet forwarding engine loopback channel with priority (e.g., up to <NUM> Priority per destination packet forwarding engine). In some examples, IPP <NUM> may perform a lookup to determine an egress packet forwarding engine of packet forwarding engines <NUM> and OQ (e.g., VOQ) per egress output port. For instance, IPP <NUM> may insert a VOQ number for an OQ at egress in a network packet prepend sent from ingress to egress.

Shaper credit update engine <NUM> may include a Grant Scheduler (GS) <NUM>, which is also referred to herein as "scheduler <NUM>" at egress, which may be configured to schedule network packets from VOQ to fabric and from OQ to the port. For instance, scheduler <NUM> may schedule fabric packets/pages from an ingress packet forwarding engine to an egress packet forwarding engine. Scheduler <NUM> may be configured to schedule network packets from OQ to the port on egress packet forwarding engine.

Scheduler <NUM> may directly schedule an egress packet forwarding engine with OQ to the port. For example, scheduler <NUM> may include an <NUM> Queue and there are five <NUM> Queues (e.g., 5x8K is <NUM> OQ per packet forwarding engine). In this instance, scheduler <NUM> may not use fabric for scheduling to port for deterministic behavior.

Router <NUM> may be configured to support mixing of VOQ and OQ in a same system. For example, router <NUM> may be configured such that some fabric destinations may be "typical" VOQ/OQ combinations when small queues per port are supported and other destinations may be OQ when larger queues per port are needed. In some examples, router <NUM> may use existing packet loopback paths on an egress packet forwarding engine to enqueue packets into an OQ with minimal changes to design to support OQ, but at possible reduced bandwidth (e.g., see <FIG>, <FIG>, <FIG>). In some examples, router <NUM> may be configured such that network packets arrive from fabric are looped back on egress packet forwarding engine to perform drop check and enqueue (NQ) to the OQ without any new data path needed. In this example, scheduler <NUM> may schedule OQ direct to port.

Router <NUM> may use dedicated data paths at egress to achieve full performance (e.g., see <FIG>, <FIG>, <FIG>). For example, router <NUM> may be configured such that network packets arrive from fabric are first checked for admittance to OQ using drop check, and if allowed are enqueued to the OQ. In this example, scheduler <NUM> may schedule from OQ direct to port. In this way, techniques described herein may use "local switching" at an egress packet forwarding engine, which may allow network packets to be received at ingress and move directly to egress without passing through fabric.

In operation, an ingress packet forwarding engine of packet forwarding engines <NUM> may determine, in response to receiving a network packet, an egress packet forwarding engine of packet forwarding engines <NUM> for outputting the network packet. For example, the ingress packet forwarding engine may determine an egress packet forwarding engine of ingress packet forwarding engines <NUM> for outputting the network packet. FIB <NUM> may determine the egress packet forwarding engine that corresponds to a next hop. For instance, FIB <NUM> may determine, in response to determining that a packet label of the network packet specifies an IP address, a next-hop for the network packet. In this instance, FIB <NUM> may determine an egress packet forwarding engine assigned to a port that corresponds to the next-hop for the network packet.

The ingress packet forwarding engine may enqueue the network packet in VOQ 227A for output to the egress packet forwarding engine. For example, the ingress packet forwarding engine stores the network packet (e.g., packet payload, packet header, etc.) at VOQ 227A. In response to a first scheduling event, an egress packet forwarding engine of ingress packet forwarding engine <NUM> may output, to the ingress packet forwarding engine, information indicating the network packet in VOQ 227A and that the network packet is to be enqueued at OQ 219A for an output port of the egress packet forwarding engine. For example, scheduler <NUM> may determine, using quality of service for different types of packet flows and/or a dequeue rate, to schedule the network packet for queueing by the egress packet forwarding engine for processing by the egress packet forwarding engine. To output the information, egress packet forwarding engine may output a network packet via a port of the egress router to a port of the ingress router a packet payload for the network packet and a header for the network packet that includes the information. In some examples, to output the information, egress packet forwarding engine may output metadata using local switching (e.g., using CBUF <NUM>) without outputting the packet payload.

In response to receiving the information, the ingress packet forwarding engine may dequeue the network packet from VOQ 227A. For example, ingress packet forwarding engine may remove the network packet (e.g., packet payload and packet header) and/or a pointer representing the network packet from VOQ 227A. Ingress packet forwarding engine may enqueue the network packet to OQ 219A. For example, ingress packet forwarding engine may add the network packet and/or a pointer representing the network packet to OQ 219A.

In response to a second scheduling event that is after the first scheduling event, egress packet forwarding engine may dequeue the network packet from OQ 219A and output the network packet at the output port (e.g., link 232A with IFC 230A). For example, scheduler <NUM> may determine, using quality of service for different types of packet flows and/or a dequeue rate, to schedule the network packet for queueing by the egress packet forwarding engine at OQ 219A for the output port. In response to the second scheduling event, the egress packet forwarding engine may output the network packet (e.g., packet payload and packet header) at the output port and remove the network packet (e.g., packet payload and packet header) and/or a pointer representing the network packet from OQ 219A for the output port.

In this way, router <NUM> may have higher scalability compared to routers that use VOQ. For example, using techniques described herein, router <NUM> may increase the output queue scale, which may help to support a larger number of customers, thereby improving an operation of a router. For example, assuming each packet forwarding engine of four packet forwarding engines supports <NUM>,<NUM> queues, the combination of the four packet forwarding engines using VOQ techniques may support only <NUM>,<NUM> queues. However, in accordance with the techniques of the disclosure, the combination of four packet forwarding engines using combined buffer techniques may support <NUM>,<NUM> queues (i.e., 4x48,<NUM>), which may allow router <NUM> to support additional customers. In some examples, router <NUM> may have a lower product cost compared to routers configured to use CIOQ. Additionally, techniques described herein may be used with VOQ techniques and/or CIOQ. For instance, router <NUM> may use VOQ for internet facing traffic and techniques described herein using a combined buffer for inbound traffic from the internet (e.g., for customer queueing).

<FIG> is a block diagram illustrating an example shaper credit update engine <NUM> of <FIG> in accordance with the techniques of the disclosure. In one example implementation, shaper credit update engine <NUM> includes rate wheel <NUM> and scheduler <NUM>. Network devices may include shaper credit update engine <NUM> to regulate a speed at which packets are transmitted to prevent flooding on the network.

Rate wheel <NUM> provides credit updates to scheduler <NUM>. Scheduler <NUM> may use credits to determine when queue / node data structure <NUM> is permitted to transmit one or more bytes enqueued by queue / node data structure <NUM>. In the example of <FIG>, rate wheel <NUM> includes rate instruction <NUM> and update rate <NUM>. Rate instruction <NUM> provides rate updates for "Guaranteed" (G) and "Maximum" (M) credit fields <NUM> to credit adder <NUM> of scheduler <NUM>. G credits may be used to allocate a guaranteed amount of bandwidth to queue / node data structure <NUM>, unless the G rate for the network is oversubscribed. M credits may be used as a rate limit to prevent queue / node data structure <NUM> from exceeding a specified average transmit rate.

In addition, update rate <NUM> represents a rate at which credits are being updated by rate wheel <NUM>. Update rate <NUM> provides a normalized dequeuing rate to queue / node data structure <NUM>. In the example of <FIG>, update rate <NUM> is the inverse of a rate update period for rate wheel <NUM>. In some examples, scheduler <NUM> applies a low-pass filter to smooth instantaneous changes in the dequeuing rate.

Scheduler <NUM> includes credit adder <NUM>, credit updater <NUM>, rate updater <NUM>, and queue/node data structure <NUM>. Credit adder <NUM> of scheduler <NUM>, based on input from clip <NUM>, provides additional credits to rate updater <NUM> using MUX <NUM>, which in turn provides such additional G / M credits <NUM> to queue / node data structure <NUM>. Depending on the value of the current credits and clip <NUM>, rate updater <NUM> may add some, all, or none of the credits to G / M credits <NUM> of queue / node data structure <NUM>. Scheduler <NUM> uses G / M credits <NUM> to determine when queue / node data structure <NUM> is permitted to transmit. In some examples, when G / M credits <NUM> for queue / node data structure <NUM> are non-negative, scheduler <NUM> may dequeue or transmit packets from queue / node data structure <NUM>. Upon dequeuing and transmitting the packets from queue / node data structure <NUM>, credit updater <NUM> removes a corresponding number of credits from G / M credits <NUM> for queue / node data structure <NUM>. Once G / M credits <NUM> for queue / node data structure <NUM> are negative, queue / node data structure <NUM> becomes ineligible for dequeuing or transmitting subsequent packets. Upon accumulating a non-negative value of G / M credits <NUM>, queue / node data structure <NUM> again becomes permitted to dequeue or transmit packets.

<FIG> is a block diagram illustrating an example first router <NUM> for switching local network traffic using loopback in accordance with techniques of this disclosure. <FIG> illustrates ports 407A-407B, 409A-409B, 417A-417B, 419A-419B, which may each represent single ports, a port group (PG), or other ports. Additionally, <FIG> illustrates congestion manager <NUM>, which may be configured to perform a network packet drop check.

Congestion manager <NUM> may check each network packet that arrives at a queue (e.g., VOQ 227A, OQ 219A, etc.) for admittance by first learning a network packet size for a respective network packet, a priority for the respective network packet, and a drop precedence for the respective network packet. For example, congestion manager <NUM> may check each network packet by looking at a current queue length to see if the network packet would exceed a drop threshold, e.g., not fit. In this example, if congestion manager <NUM> determines that the network packet would exceed the drop threshold, congestion manager <NUM> may drop the network packet (e.g., not written to queue). If congestion manager <NUM> determines that the network packet would not exceed the drop threshold (e.g., the network packet is not dropped), congestion manager <NUM> may admit the network packet to the queue. In addition to tail drop thresholds, congestion manager <NUM> may compare a network packet with Weighted random early detection (WRED) thresholds, which determine a random probability of dropping based on priority and drop precedence.

As shown, router <NUM> includes a fabric input <NUM> configured to receive network packets from the fabric (e.g., network <NUM>, the Internet, etc.) and a fabric output <NUM> configured to output network packets to the fabric. To avoid the need for an addition drop check and enqueue bandwidth, <FIG> shows a router <NUM> that is configured for egress OQ using loopback on the packet forwarding engines <NUM>. In the example of <FIG>, packet forwarding engine 226A may operate as an ingress packet forwarding engine and packet forwarding engine 226B operates an egress packet forwarding engine. The loopback path <NUM> on packet forwarding engines <NUM> may help to preserve existing data paths. In this example, network packets may arrive on packet forwarding engine 226A input ports and router <NUM> may use "local switching" (e.g., without using fabric input <NUM>, fabric output <NUM>, etc.) to move to the network packets to egress without the need for fabric. Because half the PGs may be used for loopback to emulate OQ scaling packet forwarding engine, only half of a total throughput may be used for network packet forwarding. Network packets may make two trips through CBUF <NUM> and ingress packet forwarding engine 226A and egress packet forwarding engine 226B, which may reduce the throughput of packet forwarding engines <NUM>.

<FIG> shows a local switching example using CBUF <NUM>. In the example of <FIG>, the packet is preserved in the header information when looping back to ingress from egress through a PG (e.g., port 409B). In this example, a network packet that comes into an input port (e.g., port 407A) at ingress is switched through CBUF <NUM> to packet forwarding engine 226B that has the destination output port, looped back to ingress packet forwarding engine 226A and stored in VOQ 227A. Scheduler <NUM> at egress schedules reading from VOQ 227A to port 419A, which is done via metadata since the actual packet data remains in CBUF <NUM> until read out at egress before being sent to EPP <NUM>.

In accordance with the techniques of the disclosure, ingress packet forwarding engine 226A, may determine, in response to receiving a network packet, an egress packet forwarding engine for outputting a network packet. Ingress packet forwarding engine 226A may enqueue the network packet in virtual output queue 227A for output to the egress packet forwarding engine. For example, ingress packet forwarding engine 226A may enqueue the network packet in virtual output queue 227A of ingress packet forwarding engine 226A for output to egress packet forwarding engine 226B.

Egress packet forwarding engine 226B may output, in response to a first scheduling event (e.g., determined by scheduler <NUM>) and to ingress packet forwarding engine 226A, the network packet with a header comprising information indicating the network packet in VOQ 227A and that the network packet is to be enqueued at OQ 219A for an output port of the egress packet forwarding engine 226B. For instance, scheduler <NUM> may determine the first scheduling event based on a dequeue rate at VOQ 227A.

Scheduler <NUM> may maintain per queue shaping and priority information. When a queue (e.g., VOQ 227A, OQ 219A, etc.) becomes non-empty, scheduler <NUM> may install the queue in the scheduler hierarchy (e.g., "enqueue") at the configured queue priority. When the rate shaping requirements are not met, e.g., the queue has not transmitted enough data yet, and the queue is at the current serviceable priority, scheduler <NUM> may select the queue for service by scheduler <NUM> (e.g., "dequeue"). Once a queue has met the shaping requirement, e.g., the shaping rate is met, scheduler <NUM> may remove the queue from service until a time when the queue receives addition or new shaping credits and can resume transmission again. Scheduler <NUM> may determine an amount of shaping credits a queue receives in a time period to determine a rate for the queue.

Egress packet forwarding engine 226B may output the network packet with the header from a first port (e.g., port 417B) of the egress packet forwarding engine 226B to a second port (e.g., 409B) of ingress packet forwarding engine 226A. Ingress packet forwarding engine 226B may, in response to receiving the network packet with the header, perform a drop check for the network packet.

In response to receiving the network packet with the header, ingress packet forwarding engine 226A may dequeue the network packet from virtual output queue 227A and enqueue the network packet to output queue 219A. In response to a second scheduling event that is after the first scheduling event, egress packet forwarding engine 226B may dequeue the network packet from output queue 227A and output the network packet at the output port (e.g., output port 419A). For instance, scheduler <NUM> may determine the second scheduling event based on a dequeue rate at OQ 219A. While scheduler <NUM> may determine the first scheduling event using information from queues from multiple packet forwarding engines (e.g., packet forwarding engine 226A, packet forwarding engine 226B, etc.), schedule <NUM> may determine the second scheduling event using only information for queues on packet forwarding engine 226B. As such, the first scheduling event may be considered a "coarse" scheduling while the second scheduling event may be considered a "fine" scheduling.

<FIG> is a block diagram illustrating an example router for switching fabric network traffic to egress using network packet loopback in accordance with techniques of this disclosure. <FIG> shows network switching along path <NUM> where a network packet arrives at port 407A and is stored in CBUF <NUM>, specifically VOQ 227A, at ingress. Sometime later (e.g., during a scheduling event), packet forwarding engine 226A reads the network packet out of CBUF <NUM> and outputs the network packet to fabric output <NUM> to send the network packet across the fabric to a destination packet forwarding engine.

<FIG> is a block diagram illustrating an example router for switching fabric network traffic from ingress using network packet loopback in accordance with techniques of this disclosure. <FIG> shows a network switching along path <NUM> where a network packet arriving (e.g., read by fabric input <NUM>) from across the fabric by scheduler <NUM> and arriving at egress packet forwarding engine 226B. Egress packet forwarding engine 226B stores the network packet in OQ 219A in CBUF <NUM>. Scheduler <NUM> reads the network packet out and loops the network packet back to ingress packet forwarding engine 226A through the egress PG (e.g., port 417B) to the ingress PG (e.g., port 407B).

For example, egress packet forwarding engine 226B may output, in response to a first scheduling event (e.g., determined by scheduler <NUM>) and to ingress packet forwarding engine 226A, the network packet with a header comprising information indicating the network packet in VOQ 227A and that the network packet is to be enqueued at OQ 219A for an output port of the egress packet forwarding engine 226B. For instance, egress packet forwarding engine 226B may output the network packet with the header from a first port (e.g., port 417B) of the egress packet forwarding engine 226B to a second port (e.g., 409B) of ingress packet forwarding engine 226A. Ingress packet forwarding engine 226B may, in response to receiving the network packet with the header, perform a drop check for the network packet.

In response to receiving the network packet with the header, ingress packet forwarding engine 226A may dequeue the network packet from virtual output queue 227A and enqueue the network packet to output queue 219A. For instance, IPP <NUM> of ingress packet forwarding engine 226A stores the network packet in the ingress VOQ (e.g., VOQ <NUM>). Scheduler <NUM> may later schedule the network packet to the port by the Egress GS (e.g., port 417A). For example, egress packet forwarding engine 226B may dequeue, in response to a second scheduling event that is after the first scheduling event, the network packet from output queue 227A and output the network packet at the output port (e.g., output port 419A).

<FIG> is a block diagram illustrating an example router <NUM> for switching local network traffic using metadata loopback in accordance with techniques of this disclosure. <FIG> illustrates an example router <NUM> that uses a loop-back once the packet is stored in CBUF by recirculating only the packet header and metadata from egress packet forwarding engine 226B to ingress packet forwarding engine 226A. <FIG> shows router <NUM> is configured for egress OQ. Network packets that arrive on ingress input ports (e.g., ports 407A, 407B, 409A, 409B, etc.) may use "local switching" to move to egress without the need for the fabric (e.g., fabric input <NUM>, fabric output <NUM>, etc.).

In accordance with the techniques of the disclosure, ingress packet forwarding engine 226A may determine, in response to receiving a network packet, an egress packet forwarding engine for outputting a network packet. Ingress packet forwarding engine 226A may enqueue the network packet in virtual output queue 227A for output to the egress packet forwarding engine. For example, ingress packet forwarding engine 226A may enqueue the network packet in virtual output queue 227A for output to egress packet forwarding engine 226B.

Egress packet forwarding engine 226B may output, to ingress packet forwarding engine 226A, metadata comprising information indicating the network packet in VOQ 227A and that the network packet is to be enqueued at OQ 219A for an output port (e.g., port 419A) of egress packet forwarding engine egress packet forwarding engine 226B to ingress packet forwarding engine 226A and refrain from outputting the network packet (e.g., packet payload) to ingress packet forwarding engine 226A. For instance, egress packet forwarding engine 226B may output the header data and/or metadata to the ingress packet forwarding engine using local switching (e.g., using CBUF <NUM>).

In response to receiving the metadata, ingress packet forwarding engine 226A may dequeue the network packet from virtual output queue 227A and enqueue the network packet to output queue 219A. In response to a second scheduling event that is after the first scheduling event, egress packet forwarding engine 226B may dequeue the network packet from output queue 227A and output the network packet at the output port (e.g., output port 419A).

<FIG> is a block diagram illustrating an example router for switching fabric network traffic from ingress using metadata loopback in accordance with techniques of this disclosure. Fabric input <NUM> receives network packets from the fabric and congestion manager <NUM> performs a drop check. If congestion manager <NUM> determines that the network packet is allowed, ingress packet forwarding engine 226A enqueues the network packet to OQ 219A for scheduling to the port (e.g., port 417A). <FIG> shows path <NUM> through router <NUM> to support the combined input queue and OQ model. However, this may use an additional drop check and enqueue bandwidth in order to store the network packet from the fabric in CBUF <NUM> in addition to those packets coming from locally switched ports on ingress packet forwarding engine 226A.

Egress packet forwarding engine 226B may output, in response to a first scheduling event and to ingress packet forwarding engine 226A, metadata comprising information indicating the network packet in VOQ 227A and that the network packet is to be enqueued at OQ 219A for an output port (e.g., port 419A) of egress packet forwarding engine egress packet forwarding engine 226B to ingress packet forwarding engine 226A and refrain from outputting the network packet (e.g., packet payload) to ingress packet forwarding engine 226A. For instance, egress packet forwarding engine 226B may output the header data and/or metadata to the ingress packet forwarding engine using local switching (e.g., using CBUF <NUM>).

<FIG> is a block diagram illustrating an example first process for switching network traffic in accordance with the invention. Ingress packet forwarding engine 226A determines, in response to receiving a network packet, an egress packet forwarding engine for outputting a network packet (<NUM>). For example, ingress packet forwarding engine 226A may determine an egress packet forwarding engine (e.g., egress packet forwarding engine 226B).

Ingress packet forwarding engine 226A enqueues the network packet in virtual output queue 227A for output to the egress packet forwarding engine (<NUM>). The ingress packet forwarding engine 226A enqueues the network packet in virtual output queue 227A for output to egress packet forwarding engine 226B. VOQ 227A is a combined buffer (e.g., CBUF <NUM>) for ingress packet forwarding engine 226A and the set of egress packet forwarding engines. The ingress packet forwarding engine 226A enqueues the network packet in a first portion of CBUF <NUM> that is assigned to virtual output queue 227A of ingress packet forwarding engine 226A for output to egress packet forwarding engine 226B.

Egress packet forwarding engine 226B outputs, in response to a first scheduling event and to ingress packet forwarding engine 226A, information indicating the network packet in the virtual output queue and that the network packet is to be enqueued at an output queue for an output port of the egress packet forwarding engine 226B (<NUM>). For example, egress packet forwarding engine 226B may output, to ingress packet forwarding engine 226A, the network packet with a header comprising the information. In some examples, egress packet forwarding engine 226B may output, to ingress packet forwarding engine 226A, the network packet with a header comprising the information. For instance, egress packet forwarding engine 226B may output the network packet with the header from a first port of the egress packet forwarding engine to a second port of ingress packet forwarding engine 226A. Ingress packet forwarding engine 226B may, in response to receiving the network packet with the header, perform a drop check for the network packet.

In accordance with the invention, egress packet forwarding engine 226B outputs metadata comprising the information to ingress packet forwarding engine 226A and may refrain from outputting the network packet to ingress packet forwarding engine 226A. The egress packet forwarding engine 226B outputs the metadata to the ingress packet forwarding engine and may use local switching.

In some examples, scheduler <NUM> may select the output port from a plurality of output ports at egress packet forwarding engine 226B. In this example, scheduler <NUM> or another component of egress packet forwarding engine 226B may generate the information to specify that the network packet is to be enqueued at the output queue based on the selection of the output port by scheduler <NUM>. In some examples, scheduler <NUM> may determine the first scheduling event to regulate a speed at which data is exchanged from router <NUM>. For instance, scheduler <NUM> may determine the first scheduling event based on a dequeue rate at OQ 219A.

Ingress packet forwarding engine 226A dequeues, in response to receiving the information, the network packet from virtual output queue 227A (<NUM>) and enqueue the network packet to output queue 219A (<NUM>). The ingress packet forwarding engine 226A dequeues the network packet from the first portion of CBUF <NUM> assigned to virtual output queue 227A. The ingress packet forwarding engine 226A enqueues the network packet to a second portion of CBUF <NUM> assigned to output queue 219A.

Egress packet forwarding engine 226B dequeues, in response to a second scheduling event that is after the first scheduling event, the network packet from output queue 227A (<NUM>) and output the network packet at the output port (<NUM>). For example, egress packet forwarding engine 226B may dequeue the network packet from the second portion of CBUF <NUM>. In some examples, scheduler <NUM> may determine the second scheduling event to regulate a speed at which data is exchanged from router <NUM>. For example, scheduler <NUM> may determine the second scheduling event based on a dequeue rate at OQ 219A.

Accordingly, from one perspective, there has been described an apparatus for switching network traffic includes an ingress packet forwarding engine and an egress packet forwarding engine. The ingress packet forwarding engine is configured to determine, in response to receiving a network packet, an egress packet forwarding engine for outputting the network packet and enqueue the network packet in a virtual output queue. The egress packet forwarding engine is configured to output, in response to a first scheduling event and to the ingress packet forwarding engine, information indicating the network packet in the virtual output queue and that the network packet is to be enqueued at an output queue for an output port of the egress packet forwarding engine. The ingress packet forwarding engine is further configured to dequeue, in response to receiving the information, the network packet from the virtual output queue and enqueue the network packet to the output queue.

Claim 1:
A method comprising:
determining (<NUM>), by an ingress packet forwarding engine implemented in processing circuitry, in response to receiving a network packet, an egress packet forwarding engine for outputting the network packet;
enqueuing (<NUM>), by the ingress packet forwarding engine, the network packet in a virtual output queue for output to the egress packet forwarding engine, wherein enqueuing the network packet in the virtual output queue comprises enqueuing the network packet in a first portion (227A) of a combined buffer (<NUM>) for the ingress packet forwarding engine and the egress packet forwarding engine that is assigned to the virtual output queue;
outputting (<NUM>), by the egress packet forwarding engine implemented in processing circuitry, in response to a first scheduling event, to the ingress packet forwarding engine, information indicating the network packet in the virtual output queue and that the network packet is to be enqueued at an output queue for an output port of the egress packet forwarding engine, wherein outputting the information comprises outputting metadata comprising the information to the ingress packet forwarding engine;
dequeuing (<NUM>), by the ingress packet forwarding engine, in response to receiving the information, the network packet from the virtual output queue and enqueuing (<NUM>), by the ingress packet forwarding engine, the network packet to the output queue, wherein dequeuing the network packet from the virtual output queue comprises dequeuing the network packet from the first portion of the combined buffer, and wherein enqueuing the network packet the network packet to the output queue comprises enqueuing the network packet in a second portion (219A) of the combined buffer assigned to the output queue; and
dequeuing (<NUM>), by the egress packet forwarding engine, in response to a second scheduling event that is after the first scheduling event, the network packet from the output queue and outputting (<NUM>), by the egress packet forwarding engine, the network packet at the output port.