# US 2013/0155850 A1 · Buffer occupancy based random sampling for congestion management

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

- Number: US 2013/0155850 A1
- Document ID: US20130155850A1
- Status: Published application
- Kind: A1
- Application number: 13/330,365
- Filed: 2011-12-19
- Published: 2013-06-20
- Earliest claimed: 2011-12-19
- Assignees: International Business Machines Corporation
- Inventors: Nikolaos I. Chrysos; Rolf Clauberg; Mircea R. Gusat; Fredy D. Neeser; Kenneth M. Valk
- Web page: https://patentgrep.com/patent/US20130155850A1

## CPC

- H04L 47/26: using explicit feedback to the source, e.g. choke packets
- H04L 47/30: in combination with information about buffer occupancy at either end or at transit nodes
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

A method for buffer occupancy based congestion management includes receiving, by a computing device, a data stream including a plurality of packets from a plurality of sources and storing the packets in a buffer that includes multiple storage units. The method also includes determining if the buffer is congested, responsive to determining that the buffer is congested randomly selecting an occupied unit of the buffer and determining the source of the packet stored in the occupied unit of the buffer and sending a congestion notification message to the source of the packet stored in the occupied unit of the buffer.

## Claims

### Claim 1

A method, comprising:
receiving, by a computing device, a data stream comprising a plurality of packets from a plurality sources;
storing the packets in a buffer comprising multiple storage units;
determining if the buffer is congested;
responsive to determining that the buffer is congested randomly selecting an occupied unit of the buffer and determining the source of the packet stored in the occupied unit of the buffer; and
sending a congestion notification message to the source of the packet stored in the occupied unit of the buffer.

### Claim 2 (depends on 1)

The method of claim 1, wherein a probability the congestion notification message is sent to one of the plurality of sources is equal to a percentage of buffer units occupied by packets from the one of the plurality of sources.

### Claim 3 (depends on 1)

The method of claim 1, wherein the congestion notification message instructs the source to reduce its data transmission rate.

### Claim 4 (depends on 1)

The method of claim 1, wherein determining if the buffer is congested is triggered by an arrival of data packet at the buffer.

### Claim 5 (depends on 1)

The method of claim 1, wherein determining if the buffer is congested is done on a periodic basis.

### Claim 6 (depends on 1)

The method of claim 1, wherein randomly selecting the occupied unit of the buffer comprises concurrently checking more than one buffer unit to determine if at least one buffer unit is occupied.

### Claim 7 (depends on 1)

The method of claim 1, wherein the random selection of the occupied unit of the buffer is performed with a probability that increases with a relative buffer occupancy and with a waiting time of the packet stored in the occupied unit of the buffer.

### Claim 8

A system for buffer occupancy based congestion management comprising:
a buffer embodied in a computer readable storage medium comprising a plurality of buffer units for storing packets received from a plurality of sources;
a buffer manager that stores information about the packets stored in the buffer;
a congestion estimator that monitors a congestion level in the buffer;
an occupancy sampler that randomly selects an occupied buffer unit from the plurality of buffer units; and
a congestion notification message generator that generates a congestion notification message; wherein when the congestion level in the buffer exceeds a threshold value the congestion notification message is sent to a source of the packet stored in the occupied buffer unit.

### Claim 9 (depends on 8)

The system of claim 8, wherein the congestion estimator calculates the congestion level in the buffer periodically.

### Claim 10 (depends on 8)

The system of claim 8, wherein the congestion estimator calculates the congestion level in the buffer in response to an arrival of a packet at the buffer.

### Claim 11 (depends on 8)

The system of claim 8, wherein the occupancy sampler concurrently checks more than one buffer unit of the plurality of buffer units to determine if the buffer units are occupied.

### Claim 12 (depends on 8)

The system of claim 8, wherein a probability the congestion notification message is sent to one of the plurality of sources is equal to a percentage of buffer units occupied by packets from the one of the plurality of sources.

### Claim 13

A computer program product for buffer occupancy based congestion management, the computer program product comprising:
a computer readable storage medium having computer readable program code embodied therewith, the computer readable program code comprising:
computer readable program code configured to:
receive a data stream comprising a plurality of packets from a plurality sources;
store the packets in a buffer comprising multiple storage units;
determine if the buffer is congested;
responsive to determining that the buffer is congested randomly select an occupied unit of the buffer and determine the source of the packet stored in the occupied unit of the buffer; and
send a congestion notification message to the source of the packet stored in the occupied unit of the buffer.

### Claim 14 (depends on 13)

The computer program product of claim 13, wherein a probability the congestion notification message is sent to one of the plurality of sources is selected equal to a percentage of buffer units occupied by packets from the one of the plurality of sources.

### Claim 15 (depends on 13)

The computer program product of claim 13, wherein the congestion notification message instructs the source to reduce its data transmission rate.

### Claim 16 (depends on 13)

The computer program product of claim 13, wherein determining if the buffer is congested is triggered by an arrival of data packet at the buffer.

### Claim 17 (depends on 13)

The computer program product of claim 13, wherein determining if the buffer is congested is done on a periodic basis.

### Claim 18 (depends on 13)

The computer program product of claim 13, wherein randomly selecting an occupied unit of the buffer comprises concurrently checking more than one buffer unit to determine if the buffer units are occupied.

### Claim 19

A method, comprising:
receiving, by a computing device, a data stream comprising a plurality of data flows that each include a plurality of data packets;
storing the packets in a buffer comprising multiple storage units;
maintaining a list of candidate data flows, wherein the list includes a percentage of the buffer that each data flow occupies;
determining if the buffer is congested;
responsive to determining that the buffer is congested, randomly selecting from the list of candidate data flows a data flow with a probability proportional to the percentage of the buffer that the data flow occupies; and
sending a congestion notification message to a source of the randomly selected data flow.
