Congestion control for internet protocol storage

• US 7,058,723 B2
• Filed: 11/29/2000
• Issued: 06/06/2006
• Est. Priority Date: 03/14/2000
• Status: Expired due to Fees

• Current Assignee: RPX Corporation
• Original Assignee: Adaptec Incorporated (Steel Partners Holdings LP)
• Inventors: Wilson, Andrew W.
• Primary Examiner(s): Etienne, Ario
• Assistant Examiner(s): Alam, Uzma
• Application Number:
  US09/726,676
• Publication Number:
  US 20010032269A1
• Time in Patent Office: 2,015 Days
• Field of Search: 709/235, 709/232, 709/230, 709/233, 709/234, 709/231, 710/61, 370/229, 370/230, 370/230.1, 370/231, 370/234
• US Class Current: 709/235
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/12 Avoiding congestion; Recovering from congestion
• CPC Class Codes: H04L 47/193 at the transport layer, e.g. TCP related
• CPC Class Codes: H04L 47/263 Rate modification at the source after receiving feedback
• CPC Class Codes: H04L 47/283 in response to processing delays, e.g. caused by jitter or round trip time [RTT]
• CPC Class Codes: H04L 47/30 in combination with information about buffer occupancy at either end or at transit nodes
• CPC Class Codes: H04L 47/31 by tagging of packets, e.g. using discard eligibility [DE] bits
• CPC Class Codes: H04L 69/16 Implementation or adaptation of Internet protocol [IP], of transmission control protocol [TCP] or of user datagram protocol [UDP]
• CPC Class Codes: H04L 69/161 Implementation details of TCP/IP or UDP/IP stack architecture; Specification of modified or new header fields
• CPC Class Codes: H04L 69/163 In-band adaptation of TCP data exchange; In-band control procedures
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers
• CPC Class Codes: H04L 69/32 Architecture of open systems interconnection [OSI] 7-layer type protocol stacks, e.g. the interfaces between the data link level and the physical level
• CPC Class Codes: Y02D 30/50 in wire-line communication networks, e.g. low power modes or reduced link rate

Abstract

A network system for actively controlling congestion to optimize throughput is provided. The network system includes a sending host which is configured to send packet traffic at a set rate. The network system also includes a sending switch for receiving the packet traffic. The sending switch includes an input buffer for receiving the packet traffic at the set rate where the input buffer is actively monitored to ascertain a capacity level. The sending switch also includes code for setting a probability factor that is correlated to the capacity level where the probability factor increases as the capacity level increases and decreases as the capacity level decreases. The sending switch also has code for randomly generating a value where the value is indicative of whether packets being sent by the sending switch are to be marked with a congestion indicator. The sending switch also includes transmit code that forwards the packet traffic out of the sending switch where the packet traffic includes one of marked packets and unmarked packets. The network system also has a receiving end which is the recipient of the packet traffic and also generates acknowledgment packets back to the sending host where the acknowledgment packets are marked with the congestion indicator when receiving marked packets and are not marked with the congestion indicator when receiving unmarked packets. In another example, the sending host is configured to monitor the acknowledgment packets and to adjust the set rate based on whether the acknowledgment packets are marked with the congestion indicator. In a further example, the set rate is decreased every time one of the marked packets is detected and increased when no marked packets are detected per round trip time (PRTT).

Claims

1. A method for optimizing data transmission in a data transfer system comprising:

monitoring a level of data transfer congestion within the data transfer system, the monitoring including marking data during data transfer congestion and detecting marked data, wherein marking data during data transfer congestion includes,

sending a data packet to a routing mechanism;

determining a fraction of an input buffer of the routing mechanism that is filled;

generating a random number between zero and one;

marking the data packet if the generated random number is less than or equal to the fraction of the input buffer of the routing mechanism that is filled, the marking indicating data transfer congestion; and

adjusting a data transfer rate corresponding to the level of data transfer congestion wherein the adjusting includes reducing the data transfer rate in direct correlation to the level of data transfer congestion as indicated by each marked data and increasing the data transfer rate in direct correlation to a lack of data transfer congestion as indicated by unmarked data during a round trip time (RTT).

2. A method for optimizing data transmission in a data transfer system as recited in claim 1, wherein the marked data is a data packet that is marked with data congestion information.

3. A method for optimizing data transmission in a data transfer system as recited in claim 1, wherein the unmarked data is a data packet without data congestion information.

4. A method for optimizing data transmission in a data transfer system as recited in claim 1, further comprising:

generating acknowledgement data by a recipient of the data packet, the acknowledgment data being marked if the data packet is marked.

5. A method for optimizing data transmission in a data transfer system as recited in claim 4, wherein the detecting marked data includes:

receiving the acknowledgment data from the recipient of the data packet; and

analyzing the acknowledgement data to determine if the data packet was marked.

6. A method for optimizing data transmission in a data transfer system as recited in claim 5, wherein the reducing further includes decreasing the data transmission rate by one data packet per round trip time (PRTT) for every marked packet detected.

7. A method for optimizing data transmission in a data transfer system as recited in claim 5, wherein the increasing further includes transmitting one additional data packet per round trip time (PRTT) where only the unmarked data packets are detected during a previous round trip time.

8. A method for optimizing data transmission in a data transfer system as recited in claim 2, wherein the marking the data packet includes setting data congestion information in an internet protocol header of the data packet.

9. A method for optimizing data transmission in a data transfer system as recited in claim 4, wherein the generating acknowledgment data includes setting data congestion information in an acknowledgment header if the data packet is marked.

10. A method for optimizing data transmission in a data transfer system as recited in claim 4, wherein the acknowledgement data is a positive acknowledgement (ACK).

11. A method for optimizing data transmission in a data transfer system as recited in claim 1, wherein the data transfer system includes at least a sending host, a sending switch, and a data recipient.

12. A method for optimizing data transmission in a data transfer system as recited in claim 11, wherein the data recipient includes at least one of a receiving host and a receiving switch connected to the receiving host.

13. A network system for actively controlling congestion to optimize throughput, comprising:

a sending host being configured to send packet traffic at a set rate;

a sending switch for receiving the packet traffic, the sending switch including,

a input buffer for receiving the packet traffic at the set rate, the input buffer being actively monitored to ascertain a capacity level, the capacity level corresponding to a fraction of the input buffer that is filled;

code for randomly generating a value between zero and one;

code for marking a packet to be sent by the sending switch with a congestion indicator if the randomly generated value is less than or equal to the capacity level of the input buffer;

code for leaving a packet to be sent by the sending switch unmarked with respect to the congestion indicator if the randomly generated value is greater than the capacity level of the input buffer;

transmit code for forwarding the packet traffic out of the sending switch; and

a receiving end being configured as the recipient of the packet traffic and configured to generate acknowledgment packets back to the sending host, the acknowledgment packets being marked with the congestion indicator when receiving marked packets and not being marked with the congestion indicator when receiving unmarked packets.

14. A network system for actively controlling congestion to optimize throughput as recited in claim 13, wherein the sending host is configured to monitor the acknowledgment packets and to adjust the set rate based on whether the acknowledgment packets are marked with the congestion indicator.

15. A network system for actively controlling congestion to optimize throughput as recited in claim 13, wherein the set rate is a number of packets sent per round trip time (RTT) as determined by a congestion window in the sending host.

16. A network system for actively controlling congestion to optimize throughput as recited in claim 15, wherein the congestion window operates to limit the amount of data that can be transmitted by the sending host before the acknowledgement packet is received.

17. A network system for actively controlling congestion to optimize throughput as recited in claim 13, wherein the sending host decreases the set rate every time one of the marked packets is detected.

18. A network system for actively controlling congestion to optimize throughput as recited in claim 17, wherein the set rate is decreased by one packet per round trip time (PRTT) for each of the marked packets that is detected by the sending host.

19. A network system for actively controlling congestion to optimize throughput as recited in claim 17, wherein the sending host increases the set rate when no marked packets are detected per round trip time (PRTT).

20. A network system for actively controlling congestion to optimize throughput as recited in claim 19, wherein the set rate is increased by one packet per round trip time (PRTT).

21. A network system for actively controlling congestion to optimize throughput as recited in claim 13, wherein the congestion indicator is data in the LP header of the packets showing that data transfer congestion exists.

22. A method for actively controlling congestion to optimize throughput comprising:

transferring a data packet to an input buffer of a sending switch at a set rate;

monitoring the input buffer to ascertain a capacity level of the input buffer, the

capacity level being equal to a fraction of the input buffer that is filled;

setting a probability factor that is a multiple of the capacity level of the input buffer, the probability factor increasing as the capacity level increases and decreasing as the capacity level decreases;

randomly generating a value between zero and one;

marking the data packet with a congestion indicator if the randomly generated value is less than or equal to the probability factor, otherwise leaving the data packet unmarked;

forwarding the data packet out of the sending switch to a recipient, the data packet being either a marked data packet or an unmarked data packet; and

generating an acknowledgment packet to be sent from the recipient to the sending host, the acknowledgment packet being marked with the congestion indicator when receiving the marked data packet and not being marked with the congestion indicator when receiving the unmarked data packet.

23. A method for actively controlling congestion to optimize throughput as recited in claim 22, further comprising:

monitoring the acknowledgment packets; and

adjusting the set rate based on whether the acknowledgment packet is marked with the congestion indicator.

24. A method for actively controlling congestion to optimize throughput as recited in claim 23, wherein the set rate is a number of data packets sent per round trip time (PRTT) as determined by a congestion window in the sending host.

25. A method for actively controlling congestion to optimize throughput as recited in claim 24, wherein the congestion window operates to limit the amount of the, data packets that can be transmitted by the sending host before the acknowledgement packet is received.

26. A method for actively controlling congestion to optimize throughput as recited in claim 22, wherein the sending host decreases the set rate every time one of the marked data packets is detected.

27. A method for actively controlling congestion to optimize throughput as recited in claim 26, wherein the set rate is decreased by one data packet per round trip time (PRTT) for each of the marked data packet that is detected by the sending host.

28. A method for actively controlling congestion to optimize throughput as recited in claim 26, wherein the sending host increases the set rate when no marked data packets are detected per round trip time (PRTT).

29. A method for actively controlling congestion to optimize throughput as recited in claim 28, wherein the set rate is increased by one data packet per round trip time (PRTT).

30. A network system for actively controlling congestion to optimize throughput as recited in claim 22, wherein the congestion indicator is data in the IP header of the data packet showing that data congestion exists.

31. A method for actively controlling congestion to optimize throughput comprising:

transferring a data packet to an input buffer of a sending switch at a set rate;

monitoring the input buffer to ascertain a capacity level of the input buffer, the

capacity level being equal to a fraction of the input buffer that is filled;

setting a probability factor that is a multiple of the capacity level of the input buffer, the probability factor increasing as the capacity level increases and decreasing as the capacity level decreases;

randomly generating a value between zero and one;

marking the data packet with a congestion indicator if the randomly generated value is less than or equal to the probability factor, otherwise leaving the data packet unmarked;

forwarding the data packet out of the sending switch to a recipient, the data packet being either a marked data packet or an unmarked data packet;

generating an acknowledgment packet to be sent from the recipient to the sending host, the acknowledgment packet being marked with the congestion indicator when receiving the marked data packet and not being marked with the congestion indicator when receiving the unmarked data packet;

monitoring the acknowledgment packets; and

adjusting the set rate based on whether the acknowledgment packet is marked with the congestion indicator.

32. A method for actively controlling congestion to optimize throughput as recited in claim 31, wherein the set rate is a number of packets sent per round trip time (PRTT) as determined by a congestion window in the sending host.