# US 2020/0396167 A1 · Proportional integral based shaper for lossless output buffer

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2020/0396167 A1
- Document ID: US20200396167A1
- Status: Published application
- Kind: A1
- Application number: 16/437,887
- Filed: 2019-06-11
- Published: 2020-12-17
- Earliest claimed: 2019-06-11
- Assignees: Cisco Technology, Inc.
- Applicants: Cisco Technology, Inc.
- Inventors: Parvin Taheri; Sha Ma; Thomas J. Edsall
- Web page: https://patentgrep.com/patent/US20200396167A1

## CPC

- H04L 47/225: {Determination of shaping rate, e.g. using a moving window}
- H04L 47/29: {using a combination of thresholds}
- H04L 47/30: in combination with information about buffer occupancy at either end or at transit nodes
- H04L 47/621: {Individual queue per connection or flow, e.g. per VC}
- H04L 47/267: sent by the destination endpoint (network streaming of media packets with control of the source by the destination H04L65/613)
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

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.

## Claims

### Claim 1

A method comprising:
at a network device having network ports to communicate with source devices and destination devices, receiving respective packets from each source device, and for each source device, respectively:
storing the respective packets that are received in a shared memory used to store all packets that are received from all of the source devices;
dequeuing the respective packets from the shared memory to send the packets to a respective one of the destination devices;
responsive to the storing and the dequeuing, respectively increasing and decreasing an input packet count associated with the source device to indicate a contribution of the respective packets to a total packet occupancy of the shared memory;
determining for the source device a packet sending rate individualized to the source device based on the input packet count and a flow control threshold that is common across all of the source devices in accordance with a proportional integral (PI) control equation; and
transmitting to the source device a control message including the packet sending rate.

### Claim 2 (depends on 1)

The method of claim 1, wherein the determining includes:
computing a change in the input packet count from a previous input packet count;
computing a deviation of the input packet count from the flow control threshold; and
computing the packet sending rate based on the change, the deviation, and a previous packet sending rate according to the PI control equation.

### Claim 3 (depends on 2)

The method of claim 2, wherein the PI control equation is given by:
the packet sending rate=the previous packet sending rate−A*(input_cnt−(the flow control threshold))−B*(input_cnt−old_input_cnt), where:
input_cnt is the input packet count;
old_input_cnt is a previous input packet count associated with the previous packet sending rate; and
A and B are control parameters.

### Claim 4 (depends on 1)

The method of claim 1, further comprising:
computing a free memory threshold that is a dynamic threshold indicative of an amount of free memory available in the shared memory for packets;
determining if the input packet count exceeds the free memory threshold;
if the input packet count exceeds the free memory threshold, setting the packet sending rate equal to a predetermined minimum packet sending rate that is less than the flow control threshold; and
if the input packet count does not exceed the free memory threshold, performing the determining the packet sending rate in accordance with the PI control equation.

### Claim 5 (depends on 1)

The method of claim 1, further comprising:
computing a free memory threshold that is a dynamic threshold indicative of an amount of free memory available in the shared memory for packets; and
performing pause control including:
determining if the input packet count exceeds the free memory threshold; and
if the input packet count exceeds or does not exceed the free memory threshold, commanding the source device to not send packets or to send packets, respectively.

### Claim 6 (depends on 5)

The method of claim 5, further comprising:
repeating at a first frequency the determining the packet sending rate in accordance with the PI control equation and the transmitting the packet sending rate; and
repeating the performing the pause control at a second frequency that is higher than the first frequency.

### Claim 7 (depends on 5)

The method of claim 5, wherein the commanding includes transmitting a control message that includes the packet sending rate as determined and either a transmit off command or a transmit on command commanding the source device to not send packets or to send packets, respectively.

### Claim 8 (depends on 1)

The method of claim 1, wherein the packet sending rate is configured to, when implemented at the source device, cause the input packet count to stabilize around the flow control threshold over time.

### Claim 9 (depends on 1)

The method of claim 1, wherein the flow control threshold for the input packet count is a predetermined static threshold.

### Claim 10 (depends on 1)

The method of claim 1, further comprising:
computing a free memory threshold that is dynamic and indicative of an amount of free memory available in the shared memory for packets; and
computing the flow control threshold as a dynamic threshold that is less than the free memory threshold.

### Claim 11

An apparatus comprising:
network ports to communicate with source devices and destination devices; and
a processor coupled to the network ports and configured to perform receiving respective packets from each source device, and for each source device, respectively, perform operations including:
storing the respective packets that are received in a shared memory used to store all packets that are received from all of the source devices;
dequeuing the respective packets from the shared memory to send the packets to a respective one of the destination devices;
responsive to the storing and the dequeuing, respectively increasing and decreasing an input packet count associated with the source device to indicate a contribution of the respective packets to a total packet occupancy of the shared memory;
determining for the source device a packet sending rate individualized to the source device based on the input packet count and a flow control threshold that is common across all of the source devices in accordance with a proportional integral (PI) control equation; and
transmitting to the source device a control message including the packet sending rate.

### Claim 12 (depends on 11)

The apparatus of claim 11, wherein the determining includes:
computing a change in the input packet count from a previous input packet count;
computing a deviation of the input packet count from the flow control threshold; and
computing the packet sending rate based on the change, the deviation, and a previous packet sending rate according to the PI control equation.

### Claim 13 (depends on 12)

The apparatus of claim 12, wherein the PI control equation is given by:
the packet sending rate=the previous packet sending rate−A*(input_cnt−(the flow control threshold))−B*(input_cnt−old_input_cnt), where:
input_cnt is the input packet count;
old_input_cnt is a previous input packet count associated with the previous packet sending rate; and
A and B are control parameters.

### Claim 14 (depends on 11)

The apparatus of claim 11, wherein the processor is further configured to perform:
computing a free memory threshold that is a dynamic threshold indicative of an amount of free memory available in the shared memory for packets;
determining if the input packet count exceeds the free memory threshold;
if the input packet count exceeds the free memory threshold, setting the packet sending rate equal to a predetermined minimum packet sending rate that is less than the flow control threshold; and
if the input packet count does not exceed the free memory threshold, performing the determining the packet sending rate in accordance with the PI control equation.

### Claim 15 (depends on 11)

The apparatus of claim 11, wherein the processor is further configured to perform:
computing a free memory threshold that is a dynamic threshold indicative of an amount of free memory available in the shared memory for packets; and
performing pause control including:
determining if the input packet count exceeds the free memory threshold; and
if the input packet count exceeds or does not exceed the free memory threshold, commanding the source device to not send packets or to send packets, respectively.

### Claim 16 (depends on 15)

The apparatus of claim 15, wherein the processor is further configured to perform:
repeating at a first frequency the determining the packet sending rate in accordance with the PI control equation and the transmitting the packet sending rate; and
repeating the performing the pause control at a second frequency that is higher than the first frequency.

### Claim 17 (depends on 15)

The apparatus of claim 15, wherein the commanding includes transmitting a control message that includes the packet sending rate as determined and either a transmit off command or a transmit on command commanding the source device to not send packets or to send packets, respectively.

### Claim 18

A non-transitory computer readable medium encoded with instructions that, when executed by a processor of a network device having network ports to communicate with source devices and destination devices, cause the processor to perform, receiving respective packets from each source device, and for each source device, respectively:
storing the respective packets that are received in a shared memory used to store all packets that are received from all of the source devices;
dequeuing the respective packets from the shared memory to send the packets to a respective one of the destination devices;
responsive to the storing and the dequeuing, respectively increasing and decreasing an input packet count associated with the source device to indicate a contribution of the respective packets to a total packet occupancy of the shared memory;
determining for the source device a packet sending rate individualized to the source device based on the input packet count and a flow control threshold that is common across all of the source devices in accordance with a proportional integral (PI) control equation; and
transmitting to the source device a control message including the packet sending rate.

### Claim 19 (depends on 18)

The non-transitory computer readable medium of claim 18, wherein the determining includes:
computing a change in the input packet count from a previous input packet count;
computing a deviation of the input packet count from the flow control threshold; and
computing the packet sending rate based on the change, the deviation, and a previous packet sending rate according to the PI control equation.

### Claim 20 (depends on 19)

The non-transitory computer readable medium of claim 19, wherein the PI control equation is given by:
the packet sending rate=the previous packet sending rate−A*(input_cnt−the flow control threshold)−B*(input_cnt−old_input_cnt), where:
input_cnt is the input packet count;
old_input_cnt is a previous input packet count associated with the previous packet sending rate; and
A and B are control parameters.
