Congestion management in a distributed computer system multiplying current variable injection rate with a constant to set new variable injection rate at source node
View Patent ↗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.
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.
2. 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.
3. 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.
4. 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.
5. 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.
6. 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.
7. 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.
8. 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.
9. 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.
10. 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.
11. 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.
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.
13. 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.
14. 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.
15. 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.
16. 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.
17. 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.
18. 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.
19. The method of claim 12 further comprising:
detecting congestion on a path the frames route through the at least one routing device.
20. 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.
21. The method of claim 12 further comprising:
dropping frames that are marked droppable for a time period in response to the detected congestion.
22. 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.
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.