Source: http://www.google.com/patents/US7016971?dq=2040248
Timestamp: 2016-05-04 09:18:47
Document Index: 430453509

Matched Legal Cases: ['arts 0', 'art 0', 'art 1', 'art 1', 'art 2', 'art 3']

Patent US7016971 - Congestion management in a distributed computer system multiplying current ... - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign inPatentsA 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...http://www.google.com/patents/US7016971?utm_source=gb-gplus-sharePatent US7016971 - Congestion management in a distributed computer system multiplying current variable injection rate with a constant to set new variable injection rate at source nodeAdvanced Patent SearchPublication numberUS7016971 B1Publication typeGrantApplication numberUS 09/980,760PCT numberPCT/US2000/014294Publication dateMar 21, 2006Filing dateMay 24, 2000Priority dateMay 24, 1999Fee statusPaidPublication number09980760, 980760, PCT/2000/14294, PCT/US/0/014294, PCT/US/0/14294, PCT/US/2000/014294, PCT/US/2000/14294, PCT/US0/014294, PCT/US0/14294, PCT/US0014294, PCT/US014294, PCT/US2000/014294, PCT/US2000/14294, PCT/US2000014294, PCT/US200014294, US 7016971 B1, US 7016971B1, US-B1-7016971, US7016971 B1, US7016971B1InventorsRenato J. Recio, David J. Garcia, Michael R. Krause, Patricia A. Thaler, John C. KrauseOriginal AssigneeHewlett-Packard Company, Ibm Corporation, Compaq Computer Corporation, Adaptec, Inc.Export CitationBiBTeX, EndNote, RefManPatent Citations (17), Non-Patent Citations (14), Referenced by (59), Classifications (21), Legal Events (10) External Links: USPTO, USPTO Assignment, EspacenetCongestion management in a distributed computer system multiplying current variable injection rate with a constant to set new variable injection rate at source node
US 7016971 B1Abstract
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.
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.
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.
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.
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.
dropping frames that are marked droppable for a time period in response to the detected congestion.
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:
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.
This application claims the benefit of 60/135,664, filed May 24, 1999 and claims the benefit of 60/154,150, filed Sep. 15, 1999.
The present invention generally relates to communication in distributed computer systems and more particularly to congestion management in distributed computer systems.
In conventional distributed computer systems, distributed processes, which are on different nodes in the distributed computer system, typically employ transport services, to communicate. A source process on a first node communicates messages to a destination process on a second node via a transport service. A message is herein defined to be an application-defined unit of data exchange, which is a primitive unit of communication between cooperating sequential processes. Messages are typically packetized into frames for communication on an underlying communication services/fabrics. A frame is herein defined to be one unit of data encapsulated by a physical network protocol header and/or trailer.
Messages communicated over the underlying communication services/fabrics can often experience congestion for various reasons, such as head of line blocking. There are conventional congestion control mechanisms. Congestion control mechanisms typically fall into three categories which include congestion detection mechanisms; congestion reporting mechanisms; and congestion response mechanisms. Congestion reporting mechanisms report the occurrence of congestion provided from congestion detection mechanisms possibly for short term use in alleviating congestion and possibly for long term network management. The congestion response mechanisms attempt to alleviate or remove congestion. Congestion in large distributed computer systems is a significant problem today, especially in infrastructures of remote computer systems having congestion resulting from message traffic over an internet or intranet coupling the remote computer systems.
For reasons stated above and for other reasons presented in greater detail in the Description of the Preferred Embodiments section of the present specification, there is a need for an improved congestion management architecture for distributed computer systems to alleviate congestion problems in the distributed computer systems resulting from communicating messages between remote processes over the underlying communication services/fabrics. Such an improved congestion management architecture should provide congestion detection mechanisms; congestion reporting mechanisms; and congestion response mechanisms which efficiently operate together to better address congestion problems encountered today in infrastructures of remote computer systems connected by an internet or an intranet.
The present invention provides a distributed computer system having links and routing devices. The routing devices are coupled between the links and route 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.
FIG. 1 is a diagram of a distributed computer system for implementing the present invention.
FIG. 12 is a diagram of a simple tree configuration having mixed bandwidth lengths and adaptable links.
FIG. 13 is a diagram of a simple tree with mixed bandwidth lengths and adapter and router links.
Distributed computer system 30 includes a system area network (SAN) 32 which is a high-bandwidth, low-latency network interconnecting nodes within distributed computer system 30. A node is herein defined to be any device attached to one or more links of a network and forming the origin and/or destination of messages within the network. In the example distributed computer system 30, nodes include host processors 34 a–34 d; redundant array independent disk (RAID) subsystem 33; and I/O adapters 35 a and 35 b. The nodes illustrated in FIG. 1 are for illustrative purposes only, as SAN 32 can connect any number and any type of independent processor nodes, I/O adapter nodes, and I/O device nodes. Any one of the nodes can function as an endnode, which is herein defined to be a device that originates or finally consumes messages or frames in the distributed computer system.
In distributed computer system 30, host processor nodes 34 a–34 d and RAID subsystem node 33 include at least one system area network interface controller (SANIC) 42. In one embodiment, each SANIC 42 is an endpoint that implements the SAN 32 interface in sufficient detail to source or sink frames transmitted on the SAN fabric. The SANICs 42 provide an interface to the host processors and I/O devices. In one embodiment the SANIC is implemented in hardware. In this SANIC hardware implementation, the SANIC hardware offloads much of CPU and I/O adapter communication overhead. This hardware implementation of the SANIC also permits multiple concurrent communications over a switched network without the traditional overhead associated with communicating protocols. In one embodiment, SAN 32 provides the I/O and IPC clients of distributed computer system 30 zero processor-copy data transfers without involving the operating system kernel process, and employs hardware to provide reliable, fault tolerant communications.
The host processors 34 a–34 d include central processing units (CPUs) 44 and memory 46.
In one embodiment, SAN 32 supports channel semantics and memory semantics. Channel semantics is sometimes referred to as send/receive or push communication operations, and is the type of communications employed in a traditional I/O channel where a source device pushes data and a destination device determines the final destination of the data. In channel semantics, the frame transmitted from a source process specifies a destination processes' communication port, but does not specify where in the destination processes' memory space the frame will be written. Thus, in channel semantics, the destination process pre-allocates where to place the transmitted data.
The reliable datagram service greatly improves scalability because the reliable datagram service is connectionless. Therefore, an endnode with a fixed number of QPs can communicate with far more processes and endnodes with a reliable datagram service than with a reliable connection transport service. For example, if each of N host processor nodes contain M processes, and all M processes on each node wish to communicate with all the processes on all the other nodes, the reliable connection service requires M2�(N�1) QPs on each node. By comparison, the connectionless reliable datagram service only requires M QPs+(N−1) EE contexts on each node for exactly the same communications.
An example host processor node is generally illustrated at 200 in FIG. 5. Host processor node 200 includes a process A indicated at 202, a process B indicated at 204, and a process C indicated at 206. Host processor 200 includes a SANIC 208 and a SANIC 210. As discussed above, a host processor endnode or an I/O adapter endnode can have one or more SANICs. SANIC 208 includes a SAN link level engine (LLE) 216 for communicating with SAN fabric 224 via link 217 and an LLE 218 for communicating with SAN fabric 224 via link 219. SANIC 210 includes an LLE 220 for communicating with SAN fabric 224 via link 221 and an LLE 222 for communicating with SAN fabric 224 via link 223. SANIC 208 communicates with process A indicated at 202 via QPs 212 a and 212 b. SANIC 208 communicates with process B indicated at 204 via QPs 212 c–212 n. Thus, SANIC 208 includes N QPs for communicating with processes A and B. SANIC 210 includes QPs 214 a and 214 b for communicating with process B indicated at 204. SANIC 210 includes QPs 214 c–214 n for communicating with process C indicated at 206. Thus, SANIC 210 includes N QPs for communicating with processes B and C.
A portion of a distributed computer system is generally illustrated at 250 in FIG. 6. Distributed computer system 250 includes a subnet A indicated at 252 and a subnet B indicated at 254. Subnet A indicated at 252 includes a host processor node 256 and a host processor node 258. Subnet B indicated at 254 includes a host processor node 260 and host processor node 262. Subnet A indicated at 252 includes switches 264 a–264 c. Subnet B indicated at 254 includes switches 266 a–266 c. Each subnet within distributed computer system 250 is connected to other subnets with routers. For example, subnet A indicated at 252 includes routers 268 a and 268 b which are coupled to routers 270 a and 270 b of subnet B indicated at 254. In one example embodiment, a subnet has up to 216 endnodes, switches, and routers.
An example embodiment of a switch is generally illustrated at 280 in FIG. 7. Each I/O path on a switch or router has an LLE. For example, switch 280 includes LLEs 282 a–282 h for communicating respectively with links 284 a–284 h. The naming scheme for switches and routers is similar to the above-described naming scheme for endnodes. The following is an example switch and router naming scheme for identifying switches and routers in the SAN fabric. A switch name identifies each switch or group of switches packaged and managed together. Thus, there is a single switch name for each switch or group of switches packaged and managed together.
If a reliable transport service is employed, after a request frame reaches its destination endnode, the destination endnode sends an acknowledgment frame back to the sender endnode. The acknowledgment frame permits the requestor to validate that the request frame reached the destination endnode. An acknowledgment frame is sent back to the requestor after each request frame. The requester can have multiple outstanding requests before it receives any acknowledgments. In one embodiment, the number of multiple outstanding requests is determined when a QP is created.
In the example transactions, host processor node 302 includes a client process A indicated at 320. Host processor node 304 includes a client process B indicated at 322. Client process 320 interacts with SANIC hardware 306 through QP 324. Client process 322 interacts with SANIC hardware 308 through QP 326. QP 324 and 326 are software data structures. QP 324 includes send work queue 324 a and receive work queue 324 b. QP 326 includes send work queue 326 a and receive work queue 326 b. Process 320 initiates a message request by posting WQEs to send queue 324 a. Such a WQE is illustrated at 330 in FIG. 9A. The message request of client process 320 is referenced by a gather list 332 contained in send WQE 330. Each entry in gather list 332 points to a virtually contiguous buffer in the local memory space containing a part of the message, such as indicated by virtual contiguous buffers 334 a–334 d, which respectively hold message 0, parts 0, 1, 2, and 3.
Referring to FIG. 9B, hardware in SANIC 306 reads WQE 330 and packetizes the message stored in virtual contiguous buffers 334 a–334 d into frames and flits. As illustrated in FIG. 9B, all of message 0, part 0 and a portion of message 0, part 1 are packetized into frame 0, indicated at 336 a. The rest of message 0, part 1 and all of message 0, part 2, and all of message 0, part 3 are packetized into frame 1, indicated at 336 b. Frame 0 indicated at 336 a includes network header 338 a and transport header 340 a. Frame 1 indicated at 336 b includes network header 338 b and transport header 340 b. As indicated in FIG. 9B, frame 0 indicated at 336 a is partitioned into flits 0–3, indicated respectively at 342 a–342 d. Frame 1 indicated at 336 b is partitioned into flits 4–7 indicated respectively at 342 e –342 h. Flits 342 a through 342 h respectively include flit headers 344 a–344 h. Frames are routed through the SAN fabric, and for reliable transfer services, are acknowledged by the final destination endnode. If not successively acknowledged, the frame is retransmitted by the source endnode. Frames are generated by source endnodes and consumed by destination endnodes. The switches and routers in the SAN fabric neither generate nor consume frames.
As illustrated in FIG. 10B, flits 342 a–h are transmitted from SANIC 306 to switch 310. Switch 310 consumes flits 342 a–h at its input port, creates flits 348 a–h at its output port corresponding to flits 342 a–h, and transmits flits 348 a–h to switch 312. Switch 312 consumes flits 348 a–h at its input port, creates flits 350 a–h at its output port corresponding to flits 348 a–h, and transmits flits 350 a–h to SANIC 308. SANIC 308 consumes flits 350 a–h at its input port. An acknowledgment flit is transmitted from switch 310 to SANIC 306 to acknowledge the receipt of flits 342 a–h. An acknowledgment flit 354 is transmitted from switch 312 to switch 310 to acknowledge the receipt of flits 348 a–h. An acknowledgment flit 356 is transmitted from SANIC 308 to switch 312 to acknowledge the receipt of flits 350 a–h. Acknowledgment frame 346 a fits inside of flit 358 which is transmitted from SANIC 308 to switch 312. Switch 312 consumes flits 358 at its input port, creates flit 360 corresponding to flit 358 at its output port, and transmits flit 360 to switch 310. Switch 310 consumes flit 360 at its input port, creates flit 362 corresponding to flit 360 at its output port, and transmits flit 362 to SANIC 306. SANIC 306 consumes flit 362 at its input port. Similarly, SANIC 308 transmits acknowledgment frame 346 b in flit 364 to switch 312. Switch 312 creates flit 366 corresponding to flit 364, and transmits flit 366 to switch 310. Switch 310 creates flit 368 corresponding to flit 366, and transmits flit 368 to SANIC 306.
Congestion Management Architecture
Congestion Control Mechanisms
Congestion control mechanisms fall into three categories: congestion detection mechanisms; congestion reporting mechanisms; and congestion response mechanisms.
Congestion detection mechanisms covers the mechanisms used to detect congestion in the various network topologies given SAN fabric will support.
Congestion reporting mechanisms covers the mechanism used to report the occurrence of congestion for short term use in alleviating congestion and for long term network management use (e.g., to allow a network management entity to analyze the network and recommend further actions to the system administrator).
Congestion response mechanisms covers the mechanisms used to alleviate or remove congestion from the various network topologies the SAN fabric will support.
SAN fabric congestion detection mechanisms are tailored for end points and switches and must be supported by the end points (e.g., hosts and I/O) In one embodiment, all types of switches (i.e., low to high end) support given SAN fabric congestion detection mechanism. In one embodiment, the switch case is more flexible: high-end switches must support all the mechanisms, low-end switches must support only the abnormal congestion detection. The problem with this second approach is it is difficult to pin the distinction between a low-end and high-end switch, and as a result a high-end switch may not implement much of the congestion control mechanisms, which would defeat the purpose.
Congestion Detection Mechanisms
One embodiment of the present invention is directed to a congestion management architecture in distributed computer systems which provide for efficient congestion control implementations to alleviate congestion problems in the distributor computer system, such as computer distributor system 30 of FIG. 1.
Switch and Router Mechanisms
Queue depth watermarking when queues in a switch reach a HighWaterMark amount of total queue capacity, being to drop all frames that are marked droppable. When queues remain at the HighWaterMark for an AbnormalCongestionTimer period or no forward progress is made on any single switch send port, consider the condition Abnormal Congestion and begin to drop all frame types.
If switch queues are not very large, then the ration between HighWaterMark and total queue capacity may be too small to handle droppable frames in a fair manner. For low-end San fabric switches, with small queues, a queue depth based congestion detection mechanism is not practical.
Time in queue Timestamp all frames placed in the switch queue upon reception. If a frame is queued in the switch for longer than a (programmable) time period, it will be discarded. Another option is for the switch to use virtual lane (VL) credits for congestion detection and respond by discarding frames marked with the oldest timestamps.
Similar to queue depth watermarking, the time in queue approach assume switch queues are relatively large, which for low-end SAN fabric switches is a poor assumption.
VL credit starvation there are two components to this switch congestion detection process: sender starvation and receiver starvation, both must have occurred several times over a NormalCongestionTime period for the switch to be under Normal Congestion. Sender starvation occurs when the switch has accepts an incoming frame, but does not have a space in the sending port's frame (retransmission) queue. Receiver starvation occurs when the switch detects VL credit starvation at a switch receive port. If both conditions occur simultaneously, the switch has detected Normal Congestion.
VL credit starvation can be used to detect congestion in switches that have small queues for large queues. The VL credit starvation approach described here must be supported by San fabric switches.
The switches must have two congestion detection timers: AbnormalCongestionTimer and NormalCongestionTimer.
The AbnormalCongestionTimer is used to detect a very long time period over which no forward progress has been made on any single switch receive/VL port. FN An architectural alternative would be to detect lack of forward progress at the receiver port by determining if any switch receiver/VL has gone a timer period without having any link credits are available. Either approach works. Lack of forward progress at a switch receiver port sounds backwards but it detects lack of forward progress at the point where actions taken at the detection point can ease congestion in the fabric. The switch detects lack of forward progress at any single one of its receive ports, by determining if any switch receive/VL port has gone an AbnormalCongestionTime period without having any link credits available. FN That is, the switch was not able to provide credits, on any single VL, to the nearest neighbor connected to the switches receiver port. If so, the switch reports an AbnormalCongestionTime condition and responds with the Abnormal Congestion mechanisms described below.
For Normal Congestion control the switch uses a combination of receive/VL port credit and send/VL port output buffer starvation.
A switch detects congestion at a send/VL port when the switch has a frame available for the send/VL port, but the send/VL port has no output (e.g., frame retransmission buffer) space available to accept the frame. If this occurs a programmable number of SendPortCongestion times during a NormalCongestionTime period, then the send/VL port is considered to be under congestion. The SendPortCongestion time will have a default value of the flit round trip time between the switch end port and it's nearest neighbor receiver port divided by the number of frames the switch output buffer can store.
However, this condition alone is sufficient to differentiate between switch congestion and excessive flow queue depth, because it only detects congestion at the send/VL port (vs a switch receive/VL-to-send/VL port flow).
A switch detects congestion at a receiver/VL port when any single VL at the switch's receive port has no credits available (i.e. the switch has non VL credits available to send the nearest neighbor attached to that receiver/VL port). If this occurs a programmable number of ReceivePortCongestion times during a NormalCongestionTime period, then the receive/VL port is considered to be under congestion. The ReceivePortCongestion time will have a default value of the flit round trip time between the switch receive port and it's nearest neighbor send port divided by the number of frames the switch output buffers can store.
If both congestion conditions occur a maximum programmable number of SwitchCongest time during a NormalCongestionTime period, then the switch in under Normal Congestion. The SwitchCongested value will have some default value (e.g., 5). In one embodiment, a methodology is used for setting the SwitchedCongested default value based on switch utilization, (e.g., the higher the switch is utilized, the lower the value).
The default value for the abnormal congestion timer will be set to a (high) value (e.g., 100 ms). For example, 100 ms corresponds with 256 KB frames at 1 GB/s for the first 10 generation. That is, no forward progress was allowed on the switch receive ports for 256 4 KB frame cycle. An alternative is the set the default as scalable with link bandwidth, as the link bandwidth goes up, the default value goes down. But if the maximum frame size increases as well, then a fixed value can have the same cycle attributes. In one embodiment, the default value for the normal congestion timer will be set to 1/Nth of the abnormal congestion timer.
End Point Mechanisms
Explicit detection end point congestion detection mechanisms are implemented at the end point receivers (i.e., destinations). Destination detection under this approach the destination must detect Forward Explicit Congestion Notification (FECN) conditions forwarded at the flit level. The destination will forward the FECN to the source. The source will then make the injection rate adjustments. In source detection under this approach, the source must also detect FECN conditions forwarded at the flit level for Read RDMAs. The source will then make the injection rate adjustments.
Implicit detection end point congestion detection mechanisms are implement at the end point sender (i.e., sources).
A network can implement a few implicit congestion detection mechanisms, from the simple to the complex. One embodiment supports one (ACK time-out).
Frame to ACK cycle timing not recommended due to complexity and inability to function correctly when the network contains a mix of local and remote endpoints.
Under this approach, the injection rate (i.e., bytes per second) is adjusted by monitoring the previous injection rate and the cycle time of frames within the network. The cycle time calculation needs to be made on the basis of the round trip time between a frame and it's corresponding ACK. The cycle time calculation cannot be made based on the time gap between ACKs, because the source may not always have frames to send and compensating for the frame sending time gap is not possible. If the source's frame injection rate is not continuous (i.e., the sources' send rate has time gaps), then those time gaps need to be accounted for in a cycle time calculation that strictly looks at time gaps between ACKs. This compensation becomes very problematic. Let's say, the source calculates the time delay caused by the congested switch stage by calculating the time gap between incoming frame ACKs. For example, the ACK for frame 1 was received at time A and the ACK for frame 2 was received at time B, so that time gap would be B-A. This approach would correctly reflect the time gap caused by the congested stage, so long as the source injection rate has no time gaps. However, if the source's frame injection rate also has a tie gap, then the time gap would have to be compensated for by calculating the time gap between frame sends. For example frame sequence number 1 was sent at time X, frame sequence number 2 was sent at time Y the time gap would be Y-Z. Unfortunately, the frame injection time (Y-X) cannot be easily removed from the time gap caused by the congested state (B-A), because the (B-A−Y-X) calculation would not longer just reflect the effect of the congested stage. This assumption is invalid for SAN traffic. The way this approach works is as follows.
The source monitors the number of outstanding requests over a source-destination/VL path; the number of bytes/second that the source is ending over the source-destination/VL path; and the time gap between each frame and it's corresponding ACK.
The source calculates the frame cycle time by calculating the time delay between a frame send and it's corresponding ACK or RNR_NAK received from the destination.
The source would then calculate the throughput as: Original frame size divided by the cycle time.
The source would then increase the injection rate until the throughput beings to decrease. When the throughput begins to decrease, the source would back up to the previous injection rate size.
The main issue with this approach is the complexity it causes for the source's scheduler. It is believed that this complexity makes this approach unobtainable.
The problem with using a slight simpler ACK gap time approach is that it doesn't compensate for source injection gaps (i.e., through put variations at the source that are not caused by fabric congestion adjustments, but rather by source demand rate adjustments) and as a result it doesn't perform it' intended function. A second, perhaps more important problem with ACK gap timing is that when a given source has flows with more than one minimum bandwidth, under congestion the higher bandwidth flow will have the same ACK gap timing as the lower bandwidth flows. As a result, the source will lower the link injection rate of all flows vs isolating the flows that are congested.
Performing ACK timeouts under this approach, the injection rate (i.e., bytes/seconds outstanding) is adjusted by monitoring ACK time-outs. The injection rate can be lowered at various levels; message, frame, flit, or bytes/second. Given the wide range of frame sizes in a local fabric (e.g., from 32 byte request to a 4 GB disk sequential write. For this example, SAN fabric injection rate is in bytes/second. When an ACK time-out occurs, the source assumes the ACK time-out occurred due to congestion. That is, a stage in the network has dropped the frame due to congestion. When an ACK time-out occurs, the source will modify the injection rate by half and resume transmission form the last frame expected. The source will then wait a fixed WANCongestionCleared time period before increasing the window size. After the WANCongestionCleared time period has elapsed, the source would increase the window size linearly.
Of these two implicit congestion detection approaches, ACK time-outs seem less complex for the source's scheduler. It is required to support SAN Fabric over LAN/WAN fabrics. The proposal would be to use implicit congestion detected based on ACK time-outs for paths that include non-SAN fabrics, as follows.
The source's Transport level ERP would detect the ACK timeout. The source's schedule would cut the injection rate for the affected path (source-destination/VL) by half. The source would then begin retransmission of the affected queue pair starting at the next expected frame. IN one embodiment, the source would wait a WANCongestionCleared time period before increasing the injection rate. When the WANCongestionCleared timer pops the source would increase the injection rate linearly.
In an alternative embodiment, the source would wait to receive ACK for a programmable number of WANUncongested frames. If WANUncongested frames get ACK'd, then the SAN Fabric WAN traffic is no longer under congestion. So increase the injection rate linearly.
Congestion Reporting Mechanism
The forward explicit congestion notification is architected into the flit and frame layers of the fabric. For Send and Write RDMA frames FECN is detected at the flit layer and reported at the frame layer. For FetchOP and Read RDMA frames FECN is detected at the flit layer and reported at the flit and frame layer: frames from source-destination (e.g., Read RDMA request) will get reported at the frame layer, and frames from destination-source (e.g., Read RDMA data) will get reported at the flit layer. For ACK/NAK frames FECN is detected at the flit layer, but the end-point will discard. FN Alternatively, and end-point may discriminate between ACK/NAK received in response to a Send/Write-RDMA frame; and don't adjust the injection rte for ACK/NAKs with a non-zero FECNCount received in response to a FetchOp/Read-RDMA frame.
In one embodiment, flits have 4 bits to carry FECN. These 4 bits are called the FECNCount and are contained in the flit delimeter. The source must set the FECNCount to zero. SAN fabric switches will increment the FECNCount if the switch is under congestion, until the FECNCount reaches the maximum value (15). When the FECNCount is equal to 15, switches will not increment it, because it's already at its maximum. Each switch state is responsible for maintaining the flit level FECN notification as it goes across the switch's internal receive to sender path. This can be done by carrying the flit types fields around, or simply carrying a bit around.
For a given flow (source destination/VL), the FECNCount accumulates the number of switches that are under congestion.
In one embodiment, flits have 4 bits to carry FECN. These 4 bits are called the FECNCount and are contained in the flit delimeter. The source must set the FECNCount to zero. SAN fabric switches will increment the FECNCount if the switch is under congestion, until the FECNCount reaches the maximum value (15). When the FECNCount is equal to 15, switches will not increment it, because it's already at its maximum. Each switch stage is responsible for maintaining the flit level FECN notification as it goes across the switch's internal receiver the sender path. This can be done by carrying the flit types fields around, or simply carrying a bit around.
SAN Fabric to non-SAN Fabric routers are not responsible for propagating the FECNCount fields across the non-SAN fabric. However, they are responsible for sending a frame level Backward Explicit Congestion Notification (BECN) frame containing the FECNCount to the source of the flit that experienced congestion. That is, if a router receives a flit with a non-zero FECNCount, the router is responsible for:
Generating a No-Op frame with the FECNCount field equal to the highest FECNCount in the flit delimeters of the outbound frame.
Sending the No-Op frame to the source of the outbound frame that experienced congestion. The NOP frame will be sent must ACK'd by the source (i.e., or the source may not get any if the intermediate switches discard unACK'd frames).
The destination's link layer is responsible for detecting the flit level FECN notification and passing the FECN to the destination's transport layer. Irregardless of the frame's error state (i.e., whether the destination will ACK or NAK the frame), the destination's transport layer is responsible for reporting the FECN back to the source for reliable service classes. The destination will set the FECNCount field in the outbound ACK/NAK frame to the highest FECNCount received in the flit delimiters associated with the inbound frame.
Congestion Response Mechanism
The source's scheduler should be contained in hardware for SAN Fabric traffic over SAN fabrics, otherwise the major benefits of SAN Fabric can be lost. A design issues is how much additional complexity does the dynamic adjustment add to the source's scheduler.
The source's scheduler has the ability to lower the max QP injection rate based on the reception of an ACK or NAK with a non-zero FECNCount from the destination. There are several options for lowering the max QP injection rate based on FECN.
One standard approach is to maintain two counters per QP: FECN0 and FECN1. FECN0 counts the number of ACK/NAKs received with a zero FECNCount. FECN1 accumulates FECNCount(s) received from ACK/NAKs. The counts are accumulated over a time period FECN_Time of 4� static end—end RTT. If FECN1>=FECN0 over FECN_Time, then set the max QP injection rate to half (often percentage values can be used, such as 0.875). The previous max QP injection rate to twice the previous max QP injection rate FN two more bits and one more timer can be implemented to dampen and settle down the injection rate oscillations. This basically uses aggressive QP injection rate acceleration, which can cause larger fluctuations in traffic, but also aggressively removes congestion. For a SAN, where the large fluctuations may impact performance, a more reasonable approach seems to be to modify the max QP injection rate more linearly, say by reducing max QP injection rates at 85% under congestion and increasing max QP injection rates at 1.15% when congestion subsides.
This approach requires the following state per VL at the source's scheduler:
FECN0 accumulates the number of frames with no congestion. FECN1 accumulates the FECN count FECN_Time counts down to zero. When it pops FECN 0 and FECN1 are compared. Increment Injection Rate when set its used to increment the injection rate. Decrement Injection Rate when set decrements the injection rate.
A second approach is to start a timer upon the first reception of an ACK/NAK with a non-zero FECNCount from the destination and then accumulate the number of FECNCounts over a period of time starting with the time of the first FECN and ending with a FECN_TIMER_POP. If the total number of FECNCounts collected over the time period is greater than a variable percentage (e.g., half) of the number of outstanding frames during that same time period, then reduce the injection rate. Otherwise, treat the condition as slight congestion and don't change the injection rate.
If a link has been idle for a long time, then set the max QP injection rate to half the previous maximum CP injection rate and increase the Injection Rate (IR) using the slow start algorithm: IR(i+1)=IR(i)*2. Where IR(i) is a rate measurement of the bytes/second that were ACK'd back from the destination.
The QP injection rate is on a bytes/second basis.
When the NormalCongestionTime pops, the switch will enter NC-State. When in this state, the switch will drop all frames that are marked droppable (i.e., unreliable datagram and raw frames). All frames received on receive ports marked droppable will be dropped. The switch will make the link credits that are freed from this process available to the switch's nearest neighbor using centralized weighted fairness.
The switch will continue to drop frames marked droppable for a time period of 2� the NormalCongestionTimer. This provides weighted fairness (a NormalCongestionTime period) for droppable frames. The switch will then rest the NC_state and restart the NormalCongestionTime timer.
When the AbnormalCongestionTime pops, the switch will drop all frames and consider the situation a permanent error. Meaning the condition has not gone away over a long period and for all intents and purposes it's due to a permanent error, (e.g., dead link, dead destination, broke destination (i.e., no receive WQEs ever). In any case, the source will detect an ACK timeout and will respond according to the policies set in the next sections.
Congestion Behavior
In one embodiment, SAN Fabric components implement levers (mechanisms) appropriate to the component type. In one embodiment, SAN Fabric switches implement a weighted fairness queuing algorithm that prevent receiver starvation. Some levers will be set to a fixed value. Some levers will be variable and set by an algorithm defined in the SAN Fabric specification.
EXAMPLE CONGESTION MANAGEMENT POLICIES
No Drops within SAN Fabric, Drops when Non-SAN Fabric Transports Solely Over a SAN Fabric Network
Link lever back pressure is used. This means there are not any lot frames due to congestion.
The NormalCongestionTimer=Abnormal Congestion Timer.
Each QP uses the minimum number of outstanding requests to achieve the desired BW for the necessary distance to the destination. (i.e., once maximum BW is achieved, a larger window size can only increase congestion).
Each QP should inject frames at no higher than the maximum W of the slowest link in use. This is important if there are multiple speed SAN Fabric links in use.
The request-response timer should be set high enough that a time-out implies a frame is lost due to an error (as opposed to congestion).
Legacy Protocols Solely over an SAN Fabric network.
Legacy protocol (e.g. TCP) are sent as Raw Datagram frames. These frames do not have an SAN Fabric acknowledgment frame. All acknowledgment occur at the legacy ULP level.
Link lever back pressure means there aren't any lost frames due to congestion.
Frames are injected into the network at some maximum injection rate (e.g. specified in MB/s or frames/second). This maximum rate is based on a QoS parameter and of course on the minimum speed SAN Fabric link in the path between source and destination.
The ULP SW reduces the window size if ULP acknowledgments do not return within a certain time period. In addition to reducing window size, the ULP SW may choose to reduce the injection rate of frames into the SAN Fabric network (i.e. scale back to BW transmitted).
The SW stack controlling the QP should be able to easily set the maximum injection rate, e.g., with a WQE or as port of the post Send verb.
Dropped frames (e.g., due to bit errors or other improbably occurrences) are handled by the ULP and not by the SANIC driver.
SAN Fabric Transport over Both an SAN Fabric Network and WAN Networks(s)
Link level back pressure is used within the SAN Fabric network.
Should the WAN drop frames due to congestion, the frame ACK timer will expire and invoke the implicit congestion response mechanism.
Legacy Protocols over a Mix of SAN Fabric and WAN Networks
As above, the maximum BW injected into the SAN Fabric network should be less than or equal to the maximum BW of the WAN and link level back pressure is used within the SAN Fabric network. WAN is assumed to be slower than the SAN Fabric.
Should the WAN drop frames due to congestion, the legacy ULP will timeout and notice it hasn't received an acknowledgment. It will retransmit frames with a smaller window size and/or with a lower rate of injection into the SAN Fabric network.
The legacy ULP driver will upon receiving acknowledgments increase its window size and/or increase its rate of injection into the SAN Fabric.
Drop Datagram and Raw Frame Under Normal Congestion within SAN Fabric, Drops when Non-SAN Fabric Transports Solely Over a SAN Fabric Network
Link level back pressure is used. This means there aren't any lost frames due to congestion.
NormalCongestionTimer is set to 1/Nth the value of the AbnormalCongestionTimer.
All of the normal congestion detection, reporting and response mechanisms are implemented, summarized below for completeness:
Switch—Detects congestion by analyzing receive and send port resources as stated earlier. Source—Detects congestion reported by analyzing the FECNCount field in the frame transport header as stated earlier. Destination—Detects congestion reported by analyzing the FECNCount field in the frame transport header as stated earlier. Reporting:
Switch—Propagates the FECNCount field in the flit delimiters as stated earlier. Routers—When a flit has non-zero FECNCount field, sends a No-Op frame to the flit source with the FECNCount field equal to the highest FECNCount of the flits associated with the frame. Destination—Sets the ACK/NAK FECNCount field equal to the highest FECNCount of the flits associated with the frame. Response:
Switch—Drops frames when NormalCongestion is encountered as stated earlier.
Source—Lowers injection rate based on FECNCount as described earlier.
Legacy Protocols Solely Over a SAN Fabric Network
Legacy protocols (e.g., TCP) are sent as Raw Datagram frames. These frames do not have a SAN Fabric acknowledgment frame. All acknowledgments occur at the legacy ULP level.
By setting the NormalCongestionTimer AbnormalCongestionTimer, frames will be lost due to normal congestion.
Frame loss will invoke the legacy protocol's injection rate or window size reduction algorithms.
SAN Fabric Transport Over Both a SAN Fabric and WAN Network(s)
The legacy ULP driver will upon receiving acknowledgments increase its window size and/or increase its rate of injection into the SAN Fabric network.
Drop frames under normal congestion within SAN Fabric, Drops when non-SAN Fabric SAN Fabric transports solely over a SAN Fabric network
Link level back pressure is effectively used strictly for short lived flow control between link segments.
AbnormalCongestionTimer is set to a very low value (e.g., 10s of frames vs. 100s or 1000s).
Frames will be lost under moderate congestion and invoke the implicit congestion detection, reporting and response mechanism.
Legacy Protocols Solely Over a SAN Fabric
Frames will be lost due to moderate congestion.
SAN Fabric Transport Over Both a SAN Fabric Network and WAN Network(s)
Should the WAN drop frames due to congestion, the frame Ack timer will expire and invoke the implicit congestion response mechanism defined in section 18.10.1.3.
Congestion Scenarios in Example Topologies
Scenario 1—Singleton Host tree with Adapter Leaves.
A simple tree configuration is generally illustrated at 500 in FIG. 12. This simple tree configuration may cause severe head of line blocking problems in switch A for adapters A and D. Whether switch A experiences these severe problems or not depends on the host's scheduling algorithm and the switch A's congestion control algorithm.
For example, if host A's scheduler doesn't provide a weighted fair schedule queuing (i.e., the host scheduler would use round robin selection for all traffic on the same VL, but would weight traffic for higher priority VLs higher than the traffic for low-priority VLs) that compensates for link bandwidth differences. Weighted fair queuing that compensates for link bandwidth differences means the host scheduler would use round robin selection for all traffic on the same VL, would weight traffic for higher priority VLs higher than traffic for low-priority VLs AND would also weight traffic with the highest minimum path bandwidth higher than traffic with the lowest minimum path bandwidth, then when the host has multiple frames to send adapter B or C (or adapter B and C request multiple Read Remote DMA frames from Host A.), the host can cause long periods of head of line blocking by consuming switch A queue resources. Switch A will free queue resources at the link rate of adapters B and C. As a result, the host will experience periods where no virtual lane credits are available for transfers to adapters A and D.
Several congestion control mechanisms were considered for sources, including: link level back-pressure, Implicit congestion control based on Frame-ACK timing and explicit congestion control based on FECN. Of the several forms of congestion control mechanisms considered, SAN Fabric sources must implement the explicit congestion control approach. The following describes how explicit congestion control works under scenario 1. It will also describe the difficulties with the implicit congestion control approach that was considered.
Use explicit congestion detection by means of FECN back to the source and use slow start with multiplicative decrease.
Under this approach, when head of line blocking at switch A occurs, the switch detects congestion then it marks flits on just the send ports that have detected Normal Congestion with a FECN. To be clear, the switch congestion detection process described in this chapter has two components: sender starvation and receiver starvation, both must have occurred several times over a NormalCongestionTime period for the switch to be under Normal Congestion. Sender starvation: A switch detects a lack of credit at a send port when the switch has a frame queued for the send port, but has no credits available to send data through that send port. If this occurs N times during a NormalCongestionPeriod, then the send port is under congestion. However, this condition alone is insufficient to differentiate between switch congestion and excessive flow queue depths. Receiver starvation: For the switch to determine its under congestion, the switch also has to determine if it has not been able to send credits to any one of its neighbors M times during a NormalCongestionPeriod. If both conditions apply, N occurrence of being out of credits at any send port and M occurrences of being out of credits at any receive port, then the switch is under NormalCongestion. If intermediate switches were included in scenario 1, they would need to pass through the accumulated FECNs to the next stage in the network. In scenario 1's configuration, assuming the flows are a result of long lived workload patterns, then links 3 and 4 will get a FECN before links 2 and 5. As a result, adapters B and C will ACK back to the destination to the FECN, but adapters A and D will not. The host will adjust the injection rates for adapters B and C when they are the cause of congestion.
Use implicit congestion detection by means of Frame-to-ACK timing and use slow-start and multiplicative decrease to respond to congestion. (FN—This is a derivative of TCP Vegas).
Under this approach, when head of line blocking at switch A occurs, the Frame-ACK timing for adapters B and C will appear to be the same as the Frame-ACK timing for adapters C and D. That is, assuming all switch A flows attempt to fully compete for link 1, then all switch A flows will get their injection rates reduced at the host, not just link 1->3 and link 1->4 flows. (This is specially true if Host-AdapterB and Host-AdapterC flows are long and occur before Host-AdapterA and Host-AdapterD flow begin.
Once the injection rates have been reduced, and congestion subsized, all flows will again attempt to increase their injection rates. Assuming the flows are a result of relatively long lived workload patterns, then two cases need to be treated: A) all flows set their injection rate increase time interval to constant; and B) all flows set their injection rate increase time interval based on a function of the Frame-ACK timing during uncongested operations. The Frame-ACK timing will be set to a different value depending on the flow. For example, in the scenario 1 configuration link 1->2 flows will have a much lower frame-ACK value, than link 1->3 flows.
If all flows attempt to increase their injection rates at the same constant time interval, then all flows will find the same conditions are still in effect and the applied load will continue to operate in the middle (lower portion) of the uncongested region. The reason for this being that link 3 and link 4 will continue to cause HOL as long as all flow increase their injection rates simultaneously. This causes the network throughput to operate at a sub-optimal point in the uncongested region.
However, if all flows attempt to increase their injection rates based on a function of the Frame-ACK timing during uncongested operations, then flows with a higher minimum path bandwidth will increase their injection rates at a faster rate than the flows with lower minimum path bandwidths. In this case, link 1->3 and link 1->4 flows will attempt to increase their injection rates more slowly (longer time period between injection rate increases) than link 1->2 and link 1->5 flows (which use a shorter time period between injection rate increases).
Just using link level back-pressure alone by reducing the number of credits available to the host is not very efficient, because the host cannot determine which flows are under end—end back pressure and which flows are not. Again, this will cause all switch A flows to operate at a sub-optimal point in the uncongested region.
If host A's scheduler provides weighted fair schedule queuing that compensates for only static link bandwidth differences, then host A will adjust the injection rate so as to not exceed the lowest link bandwidth rate. For example, the injection rate for host A to adapter B flow would be set to a maximum of the low bandwidth rate; and the injection rate for host A to adapter A flow would be set to a maximum of the high bandwidth rate. This approach would work fine, as long as the configuration is kept to singleton host tree with no peer—peer adapter transfers and no routers. However, scenario 2 and 3 will describe how static flow control is insufficient for a singleton host tree that contains routers or adapters performing peer—peer operations.
For a simple tree network, with no peer—peer and no routers into the internet, dynamic injection rate control using either of the two methods described above will keep the network operating near the optimal point of the uncongested region on average, with intermediate periods of normal congestion.
For a simple tree network, with no peer—peer and no routers into the internet, static injection rate control (i.e. host A's scheduler provides weighted fair schedule queuing that compensates for link bandwidth differences) is also effective at keeping network operation near the optimal point in the uncongested region. However, the next two scenarios will describe why static injection control alone is not effective at keeping network congestion near the optimal point, if this simple singleton host network includes peer—peer and routers into the internet.
Scenario 2—Singleton Host Tree with Peer—Peer Adapter Leaves
This scenario simply adds peer—peer adapter transfers to the configuration depicted in scenario 1.
Again, several congestion control mechanisms were considered for sources, including: link level back-pressure, Inplicit congestion control based on Frame-ACK timing and explicit congestion control based on FECN. Of the several forms of congestion control mechanisms considered, SAN Fabric sources must implement the explicit congestion control approach. The following describes how explicit congestion control works under scenario 2. It will describe the difficulties with the implicit congestion control approach that was considered.
Use explicit congestion detection by means of FECN back to the source and use slow start with mulitplicative decrease.
Under this approach, when HOL blocking at switch A occurs, the switch detects congestion and marks flits with an FECN on just the send ports that have detected Normal Congestion. Assuming the flows are a result of long live workload patterns, the links that are responsible for the congestion will get a FECN before links that are not responsible for the congestion. As a result, the flows that are responsible for congestion will get their injection rates reduced before those that are not. For example, if host A and adapter A both attempt to fully utilize link 5 by attempting to consume link 5's full bandwidth during transfers to adapter E, then both host A and adapter A will lower their injection rates and recover from the congestion.
Use implicit congestion detection by means of Frame-to-ACK timing and use slow-start and mulitplicative decrease to respond to congestion.
Under this approach, when HOL blocking at switch A occurs, the host A's Frame-ACK timing for link 1->3 and link 1->4 flows will appear to be the same as the Frame-ACK timing for the link 1->2 and link 1-5>flows. Similarly, adapter A's Frame-ACK timing for link 3->1 and link 3->5 will appear the same. If host A and adapter A each set their injection rate increase time interval based on a function of the Frame-ACK timing during uncongested operations, then Normal Congestion problems will be quickly detected and recovered allowing the network to operate in the uncongested region.
But now the main problem with a Frame-ACK timing based (e.g. TCP Vegas style dynamic injection rate control surfaces: fairness. There is an enhanced TCP Vegas style injection create control algorithm that is claimed to improve fairness significantly, but at the cost of greater instability. This enhanced algorithm should be analyzed for applicability. If host A is consuming the full bandwidth available on link 5, and adapter A begins to also transfer data over link 5, then soon host A and adapter A will get their injection rates lowered. If host A was operating at a higher rate than adapter A, then it will get a large share of link 5's bandwidth.
Just using link level back-pressure alone by reducing the number of credits available to the host is not very efficient, because the host cannot determine which flows are under end—end back-pressure and which flows are not. Again, this will cause all switch A flows to operate at a sub-optimal point in the uncongested region.
If host A and adapter A's scheduler provides weighted fair schedule queuing that compensates for only static link bandwidth differences, then host A and adapter A will not adjust their injection rates when their flows conflict and cause normal congestion.
Scenario 3—Singleton Host Tree with Adapter and Router Leaves.
As second simple tree configuration is generally illustrated at 600 in FIG. 13 to illustrate scenario 3. As illustrated in FIG. 13, scenario 3 replaces adapter B in the configuration depicted in scenario 1 with a router (B).
Again, several congestion control mechanisms were considered for sources, including: link level backpressure, Implicit congestion control based on Frame-ACK timing and explicit congestion control based on FECN. Of the several forms of congestion control mechanisms considered, SAN Fabric sources must implement the explicit congestion control approach. The following describes how explicit congestion control works under scenario 3. It will also describe the difficulties with the implicit congestion control approach that was considered.
Under this approach, when HOL blocking at switch A occurs, the switch detects congestion and marks flits with an FECN on just the send ports that have detected Normal Congestion. Assuming the flows are a result of long lived workload patterns, the links that are responsible for the congestion will get a FECN before links that are not responsible congestion. As a result, the flows that are responsible for congestion will get their injection rates reduced before those that are not. For example, if congestion occurs at router B due to a high send rate from host A, then the switch will forward a FECN to router B. Router B will return the FECN to host A through a No-Op frame. Host A will lower its injection rates and the local fabric will recover from the congestion.
Use implicit congestion detection by means of Frame-to-ACK timing and use slow-start and multiplicative decrease to respond to congestion.
Under this approach, if router B becomes congested it will quickly (through the link level back pressure) cause switch A to become congested.
Static injection rate control. If router B is part of a private network that is well managed, such that host A can determine all SAN Fabric and non-SAN Fabric link bandwidths per flow, then host A can adjust the injection rate so as to not exceed the lowest link bandwidth in use for each flow over the private network. This approach requires: tight private network topology; and the ability for management software to extract the lowest bandwidth link for a flow within the private network's topology. Given these abilities, the management software can set the injection rates for a source-destination flow that traverse the private network. However, this approach is very complicated, but more importantly it is ineffective at preventing congestion in the local fabric, because the private network may get congested due to traffic from other clients and hosts sharing the private network. If router B is a router tied to the internet, the situation becomes more exasperated.
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS4475192Feb 16, 1982Oct 2, 1984At&T Bell LaboratoriesData packet flow control scheme for switching networksUS5063562 *May 23, 1990Nov 5, 1991International Business Machines CorporationFlow control for high speed networksUS5193151 *Aug 30, 1989Mar 9, 1993Digital Equipment CorporationDelay-based congestion avoidance in computer networksUS5313454 *Apr 1, 1992May 17, 1994Stratacom, Inc.Congestion control for cell networksUS5506964Apr 16, 1992Apr 9, 1996International Business Machines CorporationSystem with multiple interface logic circuits including arbitration logic for individually linking multiple processing systems to at least one remote sub-systemUS5701292 *Dec 4, 1995Dec 23, 1997Lucent Technologies Inc.Method and apparatus for controlling data transfer rates of data sources in asynchronous transfer mode-based networksUS5734653May 30, 1996Mar 31, 1998Hitachi, Ltd.Cell/ packet assembly and disassembly apparatus and network systemUS5734825 *Jul 18, 1994Mar 31, 1998Digital Equipment CorporationTraffic control system having distributed rate calculation and link by link flow controlUS5802051Jun 10, 1996Sep 1, 1998Telefonaktiebolaget Lm EricssonMultiplexing of voice and data minicellsUS5802295Sep 8, 1995Sep 1, 1998Canon Kabushiki KaishaInformation processing method and system thereforUS5812527Apr 1, 1996Sep 22, 1998Motorola Inc.Simplified calculation of cell transmission rates in a cell based netwookUS5987506May 2, 1997Nov 16, 1999Mangosoft CorporationRemote access and geographically distributed computers in a globally addressable storage environmentUS6026448Sep 9, 1997Feb 15, 2000International Business Machines CorporationMethod and means for exchanging messages, responses and data between different computer systems that require a plurality of communication paths between themUS6047323Jun 27, 1996Apr 4, 2000Hewlett-Packard CompanyCreation and migration of distributed streams in clusters of networked computersUS6088736Jul 18, 1996Jul 11, 2000Fujitsu Network Communications, Inc.Joint flow control mechanism in a telecommunications networkUS6286052Dec 4, 1998Sep 4, 2001Cisco Technology, Inc.Method and apparatus for identifying network data traffic flows and for applying quality of service treatments to the flowsUS6434624Jul 23, 2001Aug 13, 2002Cisco Technology, Inc.Method and apparatus for identifying network data traffic flows and for applying quality of service treatments to the flows* Cited by examinerNon-Patent CitationsReference1"Congestion Avoidance Overview," pp. QC-69-QC76.2"Weighted Random Early Detection on the Cisco 12000 Series Router," pp. 1-26.3Brakmo, Lawrence S. et al., "TCP Vegas: End to End Congestion Avoidance on a Global Internet," IEEE Journal on Selected Areas in Communications, vol. 13, No. 8, pp. 1465-1480 (Oct. 1995).4Cisco Systems, Inc., "Optimizing Your Network Design," Macmillan Publishing USA, pp. 1-23, (1999). <www.cisco.com>.5Elloumi, Omar et al., "Improving Congestion Avoidance Algorithms for Asymmetric Networks," IEEE, pp. 1417-1421 (1997).6Henderson, Thomas R. et al., "On Improving the Fairness of TCP Congestion Avoidance," IEEE, pp. 539-544 (1998).7IBM Corp., "Direct Memory Access Tag Architecture," IBM Technical Disclosure Bulletin, vol. 32, No 4B, pp. 143-151 (Sep. 1989).8Kim, Jin-Ho et al., "TCP Deadlock Due to Coarse Timer Granularities in Unix-Based Systems," Electronic Letters, vol. 35, No. 14, (Jul. 8, 1999).9Misra, Archan et al., "The Window Distribution of Idealized TCP Congestion Avoidance with Variable Packet Loss," IEEE, pp. 1564-1572 (1999).10Moldeklev, Kjersti et al., "How a Large ATM MTU Causes Deadlocks in TCP Data Transfers," IEEE/ACM Transactions on Networking, vol. 3, No. 4, pp. 409-422 (Aug. 1995).11Parsa, Christina et al., "Improving TCP Congestion Control over Internets with Hetergeneous Transmission Media," IEEE Computer Society, Seventh International Conference on Network Protocols (ICNP'99), pp. 213-221 (Oct. 31-Nov. 3, 1999).12Ren, Jing-Fei et al., "Flow Control and Congestion Avoidance in Switched Ethernet LANs," IEEE, pp. 508-512 (1997).13Rohrs, Charles E. et al., "A Control Engineer's Look at ATM Congestion Avoidance," IEEE, pp. 1089-1094 (1995).14Rosenberg, Jonathan et al., "Timer Reconsideration for Enhanced RTP Scalability," IEEE, pp. 233-241 (1998).Referenced byCiting PatentFiling datePublication dateApplicantTitleUS7380019 *Mar 17, 2004May 27, 2008Hitachi, Ltd.Path control methodUS7486685 *Jun 29, 2001Feb 3, 2009Rankin Linda JSystem for sharing channels by interleaving flitsUS7543195 *Oct 28, 2003Jun 2, 2009Netapp, Inc.Method and system for managing time-out events in a storage area networkUS7564869Jul 21, 2009Cisco Technology, Inc.Fibre channel over ethernetUS7577748 *Feb 23, 2005Aug 18, 2009Seiko Epson CorporationInformation device and controlling method of the sameUS7602720Oct 13, 2009Cisco Technology, Inc.Active queue management methods and devicesUS7801125Sep 21, 2010Cisco Technology, Inc.Forwarding table reduction and multipath network forwardingUS7830793 *Nov 9, 2010Cisco Technology, Inc.Network device architecture for consolidating input/output and reducing latencyUS7839777 *Nov 23, 2010International Business Machines CorporationMethod, system, and apparatus for accelerating resolution of network congestionUS7873759 *Dec 23, 2008Jan 18, 2011Hitachi, Ltd.Information processing system and method of allocating I/O to paths in sameUS7961621Jun 14, 2011Cisco Technology, Inc.Methods and devices for backward congestion notificationUS7969971 *Jun 28, 2011Cisco Technology, Inc.Ethernet extension for the data centerUS8121038Aug 21, 2007Feb 21, 2012Cisco Technology, Inc.Backward congestion notificationUS8149710Jul 5, 2007Apr 3, 2012Cisco Technology, Inc.Flexible and hierarchical dynamic buffer allocationUS8160094Apr 17, 2012Cisco Technology, Inc.Fibre channel over ethernetUS8238347Aug 7, 2012Cisco Technology, Inc.Fibre channel over ethernetUS8259720Sep 4, 2012Cisco Technology, Inc.Triple-tier anycast addressingUS8532099Sep 17, 2010Sep 10, 2013Cisco Technology, Inc.Forwarding table reduction and multipath network forwardingUS8565231May 20, 2011Oct 22, 2013Cisco Technology, Inc.Ethernet extension for the data centerUS8655940 *Nov 19, 2010Feb 18, 2014Fujitsu LimitedComputer for performing inter-process communication, computer-readable medium storing inter-process communication program, and inter-process communication methodUS8743738Aug 13, 2012Jun 3, 2014Cisco Technology, Inc.Triple-tier anycast addressingUS8792352May 5, 2011Jul 29, 2014Cisco Technology, Inc.Methods and devices for backward congestion notificationUS8804529Jan 24, 2012Aug 12, 2014Cisco Technology, Inc.Backward congestion notificationUS8842694 *Apr 11, 2012Sep 23, 2014Cisco Technology, Inc.Fibre Channel over EthernetUS8879390 *Mar 29, 2011Nov 4, 2014International Business Machines CorporationMethod, communication network and datacenter for traffic management in a communication networkUS9246834Sep 15, 2014Jan 26, 2016Cisco Technology, Inc.Fibre channel over ethernetUS9264939 *Oct 7, 2011Feb 16, 2016Hewlett-Packard Development Company, L.P.Communication over a wireless connectionUS9325619 *Nov 7, 2012Apr 26, 2016Oracle International CorporationSystem and method for using virtual lanes to alleviate congestion in a fat-tree topologyUS20020078184 *Dec 10, 2001Jun 20, 2002Eiji UjyoRecord medium, multicast delivery method and multicast receiving methodUS20020194361 *Aug 10, 2001Dec 19, 2002Tomoaki ItohData transmitting/receiving method, transmitting device, receiving device, transmiting/receiving system, and programUS20030002493 *Jun 29, 2001Jan 2, 2003Rankin Linda J.System for sharing channels by interleaving flitsUS20050108444 *Nov 19, 2003May 19, 2005Flauaus Gary R.Method of detecting and monitoring fabric congestionUS20050188109 *Mar 17, 2004Aug 25, 2005Kenta ShigaPath control methodUS20050198358 *Feb 23, 2005Sep 8, 2005Seiko Epson CorporationInformation device and controlling method of the sameUS20060087989 *Mar 30, 2005Apr 27, 2006Cisco Technology, Inc., A Corporation Of CaliforniaNetwork device architecture for consolidating input/output and reducing latencyUS20060098589 *Jun 14, 2005May 11, 2006Cisco Technology, Inc.Forwarding table reduction and multipath network forwardingUS20060098681 *Mar 10, 2005May 11, 2006Cisco Technology, Inc.Fibre channel over EthernetUS20060101140 *Mar 18, 2005May 11, 2006Cisco Technology, Inc.Ethernet extension for the data centerUS20060171318 *Jun 16, 2005Aug 3, 2006Cisco Technology, Inc.Active queue management methods and devicesUS20060203730 *Feb 15, 2006Sep 14, 2006Zur Uri EMethod and system for reducing end station latency in response to network congestionUS20060251067 *Apr 6, 2006Nov 9, 2006Cisco Technology, Inc., A Corporation Of CaliforniaFibre channel over ethernetUS20070022192 *Oct 28, 2003Jan 25, 2007Tuan NguyenMethod and system for managing time-out events in a storage area networkUS20070081454 *Oct 11, 2005Apr 12, 2007Cisco Technology, Inc. A Corporation Of CaliforniaMethods and devices for backward congestion notificationUS20080186968 *Feb 2, 2007Aug 7, 2008Cisco Technology, Inc.Triple-tier anycast addressingUS20080298248 *May 27, 2008Dec 4, 2008Guenter RoeckMethod and Apparatus For Computer Network Bandwidth Control and Congestion ManagementUS20090052326 *Aug 21, 2007Feb 26, 2009Cisco Technology, Inc., A Corporation Of CaliforniaBackward congestion notificationUS20090086637 *Sep 27, 2007Apr 2, 2009International Business Machines CorporationMethod, system, and apparatus for accelerating resolution of network congestionUS20090252038 *Jun 16, 2009Oct 8, 2009Cisco Technology, Inc.Fibre channel over ethernetUS20090282163 *May 6, 2009Nov 12, 2009Takanori WashiroCommunication Apparatus, Communication Method, Program and Communication SystemUS20090311962 *Jun 15, 2009Dec 17, 2009Jun IwasakiCommunication Apparatus, Communication System, Communication Method and ProgramUS20100115154 *Dec 23, 2008May 6, 2010Hitachi, Ltd.Information processing system and method of allocating i/o to paths in sameUS20110007741 *Sep 17, 2010Jan 13, 2011Cisco Technology, Inc.Forwarding table reduction and multipath network forwardingUS20110125824 *Nov 19, 2010May 26, 2011Fujitsu LimitedComputer for performing inter-process communication, computer-readable medium storing inter-process communication program, and inter-process communication methodUS20110242976 *Oct 6, 2011International Business Machines CorporationMethod, communication network and datacenter for traffic management in a communication networkUS20120195310 *Aug 2, 2012Cisco Technology, Inc.Fibre channel over ethernetUS20130121149 *Nov 7, 2012May 16, 2013Oracle International CorporationSystem and method for using virtual lanes to alleviate congestion in a fat-tree topologyUS20130227066 *Mar 23, 2012Aug 29, 2013Nec CorporationData transfer apparatus and data transfer methodUS20140341202 *Oct 7, 2011Nov 20, 2014Andrew J. PattiCommunication Over A Wireless ConnectionUS20150312126 *Apr 25, 2014Oct 29, 2015International Business Machines CorporationMaximizing Storage Controller Bandwidth Utilization In Heterogeneous Storage Area Networks* Cited by examinerClassifications U.S. Classification709/233, 709/234International ClassificationG06F15/16Cooperative ClassificationH04L47/11, H04L47/12, H04L47/27, H04L47/10, H04L47/17, H04L47/26, H04L47/32, H04L47/37, H04L47/24European ClassificationH04L47/37, H04L47/24, H04L47/26, H04L47/17, H04L47/10, H04L47/32, H04L47/12, H04L47/27, H04L47/11Legal EventsDateCodeEventDescriptionJun 24, 2002ASAssignmentOwner name: ADAPTEC, INC., CALIFORNIAFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:RECIO, RENATO J.;GARCIA, DAVID J.;KRAUSE, MICHAEL R.;ANDOTHERS;REEL/FRAME:013098/0470;SIGNING DATES FROM 20020325 TO 20020420Owner name: IBM CORPORATION, NEW YORKFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:RECIO, RENATO J.;GARCIA, DAVID J.;KRAUSE, MICHAEL R.;ANDOTHERS;REEL/FRAME:013098/0470;SIGNING DATES FROM 20020325 TO 20020420Owner name: HEWLETT-PACKARD COMPANY, COLORADOFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:RECIO, RENATO J.;GARCIA, DAVID J.;KRAUSE, MICHAEL R.;ANDOTHERS;REEL/FRAME:013098/0470;SIGNING DATES FROM 20020325 TO 20020420Owner name: COMPAQ COMPUTER CORPORATION, TEXASFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:RECIO, RENATO J.;GARCIA, DAVID J.;KRAUSE, MICHAEL R.;ANDOTHERS;REEL/FRAME:013098/0470;SIGNING DATES FROM 20020325 TO 20020420Sep 21, 2009FPAYFee paymentYear of fee payment: 4Sep 22, 2011ASAssignmentOwner name: HEWLETT-PACKARD DEVELOPMENT COMPANY, L.P., TEXASFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:HEWLETT-PACKARD COMPANY;REEL/FRAME:026945/0699Effective date: 20030131Jul 29, 2013ASAssignmentOwner name: PMC-SIERRA, INC., CALIFORNIAFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:ADAPTEC, INC.;REEL/FRAME:030899/0567Effective date: 20100608Aug 6, 2013ASAssignmentOwner name: BANK OF AMERICA, N.A., NORTH CAROLINAFree format text: SECURITY INTEREST IN PATENTS;ASSIGNORS:PMC-SIERRA, INC.;PMC-SIERRA US, INC.;WINTEGRA, INC.;REEL/FRAME:030947/0710Effective date: 20130802Aug 21, 2013FPAYFee paymentYear of fee payment: 8Jun 19, 2015ASAssignmentOwner name: HEWLETT-PACKARD COMPANY, CALIFORNIAFree format text: MERGER;ASSIGNOR:COMPAQ COMPUTER CORPORATION;REEL/FRAME:035867/0049Effective date: 20040430Nov 9, 2015ASAssignmentOwner name: HEWLETT PACKARD ENTERPRISE DEVELOPMENT LP, TEXASFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:HEWLETT-PACKARD DEVELOPMENT COMPANY, L.P.;REEL/FRAME:037079/0001Effective date: 20151027Feb 1, 2016ASAssignmentOwner name: PMC-SIERRA US, INC., CALIFORNIAFree format text: RELEASE BY SECURED PARTY;ASSIGNOR:BANK OF AMERICA, N.A.;REEL/FRAME:037675/0129Effective date: 20160115Owner name: PMC-SIERRA, INC., CALIFORNIAFree format text: RELEASE BY SECURED PARTY;ASSIGNOR:BANK OF AMERICA, N.A.;REEL/FRAME:037675/0129Effective date: 20160115Owner name: WINTEGRA, INC., CALIFORNIAFree format text: RELEASE BY SECURED PARTY;ASSIGNOR:BANK OF AMERICA, N.A.;REEL/FRAME:037675/0129Effective date: 20160115Feb 3, 2016ASAssignmentOwner name: MORGAN STANLEY SENIOR FUNDING, INC., NEW YORKFree format text: PATENT SECURITY AGREEMENT;ASSIGNORS:MICROSEMI STORAGE SOLUTIONS, INC. (F/K/A PMC-SIERRA, INC.);MICROSEMI STORAGE SOLUTIONS (U.S.), INC. (F/K/A PMC-SIERRA US, INC.);REEL/FRAME:037689/0719Effective date: 20160115RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services