# US 7,016,971 B1 · Congestion management in a distributed computer system multiplying current variable injection rate with a constant to set new variable injection rate at source node

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

- Number: US 7,016,971 B1
- Document ID: US7016971B1
- Status: Granted
- Kind: B1
- Application number: 09/980,760
- Filed: 2000-05-24
- Granted: 2006-03-21
- Earliest claimed: 1999-05-24
- Assignees: Hewlett-Packard Company; IBM Corporation; Compaq Computer Corporation; Adaptec, Inc.
- Inventors: Renato J. Recio; David J. Garcia; Michael R. Krause; Patricia A. Thaler; John C. Krause
- Web page: https://patentgrep.com/patent/US7016971B1

## CPC

- H04L 47/10: Flow control; Congestion control
- H04L 47/11: Identifying congestion
- H04L 47/12: Avoiding congestion; Recovering from congestion
- H04L 47/17: Interaction among intermediate nodes, e.g. hop by hop
- H04L 47/24: Traffic characterised by specific attributes, e.g. priority or QoS
- H04L 47/26: using explicit feedback to the source, e.g. choke packets
- H04L 47/27: Evaluation or update of window size, e.g. using information derived from acknowledged [ACK] packets
- H04L 47/32: by discarding or delaying data units, e.g. packets or frames
- H04L 47/37: {Slow start}
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

A distributed computer system includes links and routing devices coupled between the links and routing frames between the links. Each of the routing devices includes a congestion control mechanism for detecting congestion at the routing device and responding to detected congestion by gradually reducing an injection rate of frames routed from the routing device.

## Claims

### Claim 1

A distributed computer system comprising:
links; and
end stations coupled between the links, wherein types of end stations include endnodes which originate or consume frames and routing devices which route frames between the links and do not originate or consume frames, wherein the end stations include a first source endnode which originates frames at a variable injection rate, wherein the first source endnode includes:
a congestion control mechanism responding to detected congestion by multiplicatively decreasing the variable injection rate,
wherein the variable injection rate (IR) is multiplicatively decreased according to IR(i+1)=IR(i)*1/F1, wherein F1 is a constant, wherein IR(i) is equal to a previous variable injection rate and IR(i+1) is equal to a new variable injection rate.

### Claim 2 (depends on 1)

The distributed computer system of claim 1 wherein the congestion control mechanism responds to detected subsiding of congestion by multiplicatively increasing the variable injection rate.

### Claim 3 (depends on 2)

The distributed computer system of claim 2 wherein the variable injection rate (IR) is multiplicatively increased according to IR(i+1)=IR(i)*F2, wherein F2 is a constant.

### Claim 4 (depends on 1)

The distributed computer system of claim 1 wherein the end stations include a first destination endnode which consumes frames originated from the first source endnode, wherein the first destination endnode includes:
a congestion control mechanism detecting congestion on a path the frames route from the first source endnode to the first destination endnode.

### Claim 5 (depends on 4)

The distributed computer system of claim 4 wherein the first destination endnode's congestion control mechanism detects congestion based on Forward Explicit Congestion Notification (FECN) conditions, and forwards the FECN conditions to the first source endnode.

### Claim 6 (depends on 1)

The distributed computer system of claim 1 wherein the end stations include a first destination endnode which consumes frames originated from the first source endnode, wherein the first source endnode's congestion control mechanism detects congestion on a path the frames route from the first source endnode to the first destination endnode by monitoring a previous variable injection rate and a round trip time for a frame to reach the first destination endnode and an acknowledgement (ACK) for the frame from the first destination endnode to reach the first source endnode.

### Claim 7 (depends on 1)

The distributed computer system of claim 1 wherein the first source endnode's congestion control mechanism detects congestion on a path the frames route from the first source endnode by monitoring acknowledgement (ACK) timeouts.

### Claim 8 (depends on 1)

The distributed computer system of claim 1 wherein at least one routing device includes:
a congestion control mechanism detecting congestion on a path the frames route through the at least one routing device.

### Claim 9 (depends on 8)

The distributed computer system of claim 8 wherein the at least one routing device includes receive and send port resources, and wherein the at least one routing device's congestion control mechanism detects congestion by analyzing the receive and send port resources.

### Claim 10 (depends on 1)

Previously Presented) The distributed computer system of claim 1 wherein at least one routing device includes:
a congestion control mechanism responding to detected congestion by dropping frames that are marked droppable for a time period.

### Claim 11 (depends on 1)

The distributed computer system of claim 1 wherein at least one routing device includes:
a congestion control mechanism responding to detected congestion by applying link back pressure by reducing a number of credits available for routing frames though the routing device from a link.

### Claim 12

A method of controlling congestion in a distributed computer system having links and end stations coupled between the links, wherein types of end stations include endnodes which originate or consume frames and routing devices which route frames between the links and do not originate or consume frames, the method comprising:
originating, from a first source endnode, frames at a variable injection rate;
detecting congestion; and
multiplicatively decreasing the variable injection rate in response to the detected congestion including multiplicatively decreasing the variable injection rate (IR) according to IR(i+1)=IR(i)*1/F1, wherein F1 is a constant, wherein IR(i) is equal to a previous variable injection rate and IR(i+1) is equal to a new variable injection rate.

### Claim 13 (depends on 12)

The method of claim 12 further comprising detecting subsiding of congestion; and
multiplicatively increasing the variable injection rate in response to the detected subsiding of congestion.

### Claim 14 (depends on 13)

The method of claim 13 wherein multiplicatively increasing the variable injection rate includes multiplicatively increasing the variable injection rate (IR) according to IR(i+1)=IR(i)*F2, wherein F2 is a constant.

### Claim 15 (depends on 12)

The method of claim 12 further comprising:
consuming, at a first destination endnode, frames originated from the first source endnode; and
detecting congestion on a path the frames route from the first source endnode to the first destination endnode.

### Claim 16 (depends on 15)

The method of claim 15 wherein the detecting congestion on the path the frames route from the first source endnode to the first destination endnode includes detecting congestion based on Forward Explicit Congestion Notification (FECN) conditions, and the method further comprises:
forwarding the FECN conditions to the first source endnode.

### Claim 17 (depends on 12)

The method of claim 12 further comprising:
consuming; at a first destination endnode, frames originated from the first source endnode; and
detecting congestion on a path the frames route from the first source endnode to the first destination endnode by monitoring a previous variable injection rate and a round trip time for a frame to reach the first destination endnode and an acknowledgement (ACK) for the frame from the first destination endnode to reach the first source endnode.

### Claim 18 (depends on 12)

The method of claim 12 wherein the detecting includes detecting congestion on a path the frames route from the first source endnode by monitoring acknowledgement (ACK) timeouts.

### Claim 19 (depends on 12)

The method of claim 12 further comprising:
detecting congestion on a path the frames route through the at least one routing device.

### Claim 20 (depends on 19)

The method of claim 19 wherein the at least one routing device includes receive and send port resources, and the detecting congestion on a path the frames route through the at least one routing device includes analyzing the receive and send port resources.

### Claim 21 (depends on 12)

The method of claim 12 further comprising:
dropping frames that are marked droppable for a time period in response to the detected congestion.

### Claim 22 (depends on 12)

The method of claim 12 further comprising:
applying link back pressure by reducing a number of credits available for routing frames though the routing device from a link in response to the detected congestion.

### Claim 23

A distributed computer system comprising:
links; and
end stations coupled between the links, wherein types of end stations include endnodes which originate or consume frames and routing devices which route frames between the links and do not originate or consume frames, wherein the end stations include a first source endnode which originates frames at a variable injection rate, wherein at least one routing device includes a congestion control mechanism responding to detected congestion by dropping frames that are marked droppable for a time period, and wherein the first source endnode includes:
a congestion control mechanism responding to detected congestion by multiplicatively decreasing the variable injection rate and responding to detected subsiding of congestion by multiplicatively increasing the variable injection rate, wherein the variable injection rate (IR) is multiplicatively decreased according to IR(i+1)=IR(i)*1/F1, wherein F1 is a constant, wherein the variable injection rate (IR) is multiplicatively increased according to IR(i+1)=IR(i)*F2, wherein F2 is a constant, wherein IR(i) is equal to a previous variable injection rate and IR(i+1) is equal to a new variable injection rate.