# US 2013/0155857 A1 · Hybrid arrival-occupancy based 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/0155857 A1 - Document ID: US20130155857A1 - Status: Published application - Kind: A1 - Application number: 13/330,407 - Filed: 2011-12-19 - Published: 2013-06-20 - Earliest claimed: 2011-12-19 - Assignees: International Business Machines Corporation - Inventors: Nikolaos I. Chrysos; Rolf Clauberg; Daniel Crisan; Mircea R. Gusat; Cyriel J. Minkenberg; Fredy D. Neeser; Kenneth M. Valk - Web page: https://patentgrep.com/patent/US20130155857A1 ## CPC - H04L 47/30: in combination with information about buffer occupancy at either end or at transit nodes - H04L 49/309: {Header conversion, routing tables or routing tags} - H04L 47/26: using explicit feedback to the source, e.g. choke packets - H04L 49/108: {using shared central buffer} - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) ## Abstract A method for hybrid arrival-occupancy based congestion management includes increasing a recent arrivals counter associated with a data flow from one or more sources in response to receiving a data packet from one of the sources and storing the data packet in a buffer including multiple storage units. The method includes determining if a 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, generating a congestion notification message, sending the congestion notification message to the source of the packet stored in the occupied unit of the buffer if the recent arrivals counter exceeds a threshold value and decreasing the recent arrivals counter associated with the source of the packet stored in the occupied unit of the buffer and discarding the congestion notification message if the recent arrivals counter has a zero value. ## Claims ### Claim 1 A method, comprising: increasing a recent arrivals counter associated with a data flow from a source in response to receiving, by a computing device, a data packet from the source; storing the data packet in a buffer comprising multiple storage units; determining if a 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; generating a congestion notification message; sending the congestion notification message to the source of the packet stored in the occupied unit of the buffer if the recent arrivals counter exceeds a threshold value and decreasing the recent arrivals counter associated with the packet stored in the occupied unit of the buffer; and discarding the congestion notification message if the recent arrivals counter of the corresponding flow is equal to or less than a threshold value. ### Claim 2 (depends on 1) The method of claim 1, wherein the recent arrivals counter has a minimum value of zero. ### Claim 3 (depends on 1) The method of claim 1, wherein the recent arrivals counter has an initial value of zero. ### Claim 4 (depends on 1) The method of claim 1, wherein an amount by which the recent arrivals counter is increased is proportional to a size of the data packet received from the source. ### Claim 5 (depends on 1) The method of claim 1, wherein the recent arrivals counter has a maximum value. ### Claim 6 (depends on 1) The method of claim 1, wherein the congestion notification message instructs the source to reduce its data transmission rate. ### Claim 7 (depends on 1) The method of claim 1, wherein determining if the buffer is congested is triggered by an arrival of the data packet at the buffer. ### Claim 8 (depends on 1) The method of claim 1, wherein determining if the buffer is congested is done on a periodic basis. ### Claim 9 A method, comprising: receiving, by a computing device, a plurality of data flows, each of the plurality of data flows are received from a source and comprise a plurality of data packets; storing the data packets in a buffer comprising multiple storage units; maintaining a first and a second list of culprit data flows; determining if a buffer is congested; responsive to determining that the buffer is congested, generating a congestion notification message; sending the congestion notification message to the source of a data flow selected from the first list of culprit data flows on condition that the selected data flow is also included in the second list of culprit data flows; and discarding the congestion notification message if the selected data flow is not included in the second list of culprit data flows. ### Claim 10 (depends on 9) The method of claim 9, wherein the second list of culprit data flows comprises one or more of the plurality of data flows associated with recently received data packets. ### Claim 11 (depends on 9) The method of claim 9, wherein the first list of culprit data flows is generated and periodically updated by inserting data flows associated with packets stored in randomly selected occupied units of the buffer ### Claim 12 (depends on 9) The method of claim 9, wherein the second list of culprit data flows comprises all data flows occupying at least a minimum number of buffer units. ### Claim 13 (depends on 9) The method of claim 9, wherein the second list of culprit data flows comprises all data flows whose recent arrivals counter is equal or above a threshold. ### Claim 14 (depends on 9) The method of claim 9, wherein a list of culprit data flows comprises at most a maximum number of flows. ### Claim 15 A system for hybrid arrival-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 recent arrivals counter that stores information about packets received from each of the plurality of sources; a congestion estimator that monitors a congestion level in the buffer; a 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 if the recent arrivals counter has a positive value. ### Claim 16 (depends on 15) The system of claim 15, wherein the recent arrivals counter is increased each time the packet is received from the source and decreased each time the congestion notification message is sent to the source. ### Claim 17 (depends on 16) The system of claim 16, wherein the recent arrivals counter is increased by an amount proportional to a size of the packet received. ### Claim 18 (depends on 15) The system of claim 15, wherein the recent arrivals counter has a minimum value of zero. ### Claim 19 (depends on 15) The system of claim 15, wherein the recent arrivals counter has an initial value of zero. ### Claim 20 (depends on 15) The system of claim 15, wherein the recent arrivals counter has a maximum value. ### Claim 21 (depends on 15) The system of claim 15, wherein the congestion notification message instructs the source to reduce its data transmission rate. ### Claim 22 (depends on 15) The system of claim 15, wherein determining if the buffer is congested is triggered by an arrival of the data packet at the buffer. ### Claim 23 A method, comprising: receiving, by a computing device, a plurality of data flows from a plurality of sources, each of the plurality of data flows comprising a plurality of data packets; storing the data packets in a buffer comprising multiple storage units; maintaining a list of culprit data flows, wherein the list of culprit data flows includes data flows that have a positive a recent arrivals counter; determining if a buffer is congested; responsive to determining that the buffer is congested randomly selecting an occupied unit of the buffer and determining a source of the packet stored in the occupied unit of the buffer; generating a congestion notification message; sending the congestion notification message to the source of the packet stored in the occupied unit of the buffer if the data flow associated with the source is included in the list of culprit data flows; and discarding the congestion notification message if the data flow associated with the source is not included in the list of culprit data flows.