Cisco Technology, Inc.

Sha Ma

Thomas James Edsall

Philip H Chen

Parvin Taheri

Chih-Tsung Huang

Wei-Jen Huang

Mohammadreza Alizadeh Attar

William L Lynch

Keerthi Manjunathan Swarnamanjunathan

Krishnan Subramani

Dennis Khoa Dang Nguyen

Sachin Agarwal

Felice Bonardi

Karthik Subramanian Mandakolathur

Earl T Cohen

Rong Pan

Peter Clarke Newman

Brian Alleyne

Georges Akis

Vinod Mitulal

Hsitung Huang

Liyuan Quan

Multiple listlets function as a single master linked list to manage data packets across one or more banks of memory in a first-in first-out (FIFO) order, while allowing multiple push and/or pop functions to be performed per cycle. Each listlet can be a linked list that tracks pointers and is stored in a different memory bank. The nodes can include a pointer to a data packet, a pointer to the next node in the listlet and a next listlet identifier that identifies the listlet that contains the next node in the master linked list. The head and tail of each listlet, as well as an identifier each to track the head and tail of the master linked list, can be maintained in cache. The individual listlets are updated accordingly to maintain order of the master linked list as pointers are pushed and popped from the master linked list.

Boosting linked list throughput

A first node of a packet switched network transmits at least one flow of protocol data units of a network to at least one output context of one of a plurality of second nodes of the network. The first node includes X virtual output queues (VOQs). The first node receives, from at least one of the second nodes, at least one fair rate record. Each fair rate record corresponds to a particular second node output context and describes a recommended rate of flow to the particular output context. The first node allocates up to X of the VOQs among flows corresponding to i) currently allocated VOQs, and ii) the flows corresponding to the received fair rate records. The first node operates each allocated VOQ according to the corresponding recommended rate of flow until a deallocation condition obtains for the each allocated VOQ.

Managing virtual output queues

A network device includes network ports to communicate with source devices and destination devices. The network device receives respective packets from each source device and, for each source device, respectively performs the following operations. The network device stores the respective packets in a shared memory that stores all packets from all of the source devices, and dequeues the respective packets from the shared memory to send the packets to destination devices. Responsive to the storing and the dequeuing, the network device respectively increases and decreases an input packet count for the source device. The network device determines for the source device a packet sending rate based on the input packet count and a flow control threshold common across all of the source devices in accordance with a proportional integral (PI) control equation. The network device transmits to the source device a control message including the packet sending rate.

Proportional integral based shaper for lossless output buffer

A network device is configured to transmit acknowledgement packets according to the length of the egress queue. The network device receives data packets from one or more endpoints and buffers the data packets in an egress buffer before transmitting the data packets. The network device also receives acknowledgement packets that are sent in response to data packets previously transmitted by the network device. The network device buffers the acknowledgement packets in an acknowledgement buffer. The network device transmits the acknowledgement packets at an acknowledgment rate that is based on a queue length of the egress buffer.

Adaptive acknowledgement control

Techniques are described for a memory device. In various embodiments, a scheduler/controller is configured to manage data as it read to or written from a memory. A memory is partitioned into a group of sub-blocks, a parity block is associated with the sub-blocks, and the sub-blocks are accessed to read data as needed. A pending write buffer is added to a group of memory sub-blocks. Such a buffer may be sized to be equal to the group of memory sub-blocks. The pending write buffer handles collisions for write accesses to the same block.

Performing multiple write operations to a memory using a pending write queue/cache

A work conserving scheduler can be implemented based on a ranking system to provide the scalability of time stamps while avoiding the fast search associated with a traditional time stamp implementation. Each queue can be assigned a time stamp that is initially set to zero. The time stamp for a queue can be incremented each time a data packet from the queue is processed. To provide varying weights to the different queues, the time stamp for the queues can be incremented at varying rates. The data packets can be processed from the queues based on the tier rank order of the queues as determined from the time stamp associated with each queue. To increase the speed at which the ranking is determined, the ranking can be calculate from a subset of the bits defining the time stamp rather than the entire bit set.

Work conserving scheduler based on ranking

A network switch includes a buffer to store network packets and packet descriptors (PDs) used to link the packets into queues for output ports. The buffer and PDs are shared among the multiple traffic pools. The switch receives a multicast packet for queues in a given pool. The switch determines if there is unused buffer space available for packets in the given pool based on a pool dynamic threshold, if there is unused buffer space available for packets in each queue based on a queue dynamic threshold for the queue, if there are unused PDs available to the given pool based on a pool dynamic threshold for PDs, and if there are unused PDs available for each queue based on a queue dynamic threshold for PDs for the queue. The network switch admits the packet only into the queues for which all of the determining operations pass.

Dynamic protection of shared memory and packet descriptors used by output queues in a network device

Work conserving schedular based on ranking

Systems, methods, and non-transitory computer-readable storage media for per-packet load balancing in a port channel. The system first maps an incoming traffic flow to queues containing packets to be transmitted through a port channel at the system, the port channel including ports grouped into a single virtual port. Next, the system assigns a port from the port channel to a queue for a predetermined period of time, wherein the port is assigned to the queue based on at least one of a port state and a service history associated with the queue. The system then de-queues at least a portion of the packets in the queue through the port for the predetermined period of time. This load balancing can ensure that traffic is efficiently and fairly load balanced across the links of the port channel, and packets of each queue are not reordered.

Randomized per-packet port channel load balancing

In a multicast networking device having a plurality of output ports, a hierarchical packet scheduling tree is generated for a first port. The hierarchical packet scheduling tree is generated from a transmission queue for the first port. A sequential search of the hierarchical scheduling tree is performed to determine a packet pointer to a first packet in the transmission queue of the first port. Based on the packet pointer, packet data for the first packet is obtained and the first packet comprising the packet data is transmitted to a destination device via the first port.

Per-port multicast processing

A networking device employing memory buffering in which a first memory is logically configured into blocks, and the blocks are logically configured into particles, where a second memory is configured to mirror the first memory in which a fixed number of bits in the second memory are allocated for each particle in the first memory so that scheduling and datagram lengths of packets stored in the first memory may be stored in the second memory. Other embodiments are described and claimed.

Memory buffering with fast packet information access for a network device

In one embodiment, separate rate meters are maintained for each flow enqueued an increased at a target rate while a packet from the flow occupies the head of a shared transmit queue. The meter value is decreased by the packet length when a packet in enqueued or dropped. The next packet that occupies the head of the shared transmit queue is dropped if the meter value corresponding to the flow is greater than a threshold.

Growing community of inventors

San Jose, CA, United States of America

Sha Ma