Process for improving the efficiency of high performance routing

• US 5,901,138 A
• Filed: 11/08/1996
• Issued: 05/04/1999
• Est. Priority Date: 11/08/1996
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Bader, Lance Dana, Scott, Robert Walter, Kaminsky, David Louis, Kompella, Vachaspathi Peter
• Primary Examiner(s): Patel, Ajit
• Assistant Examiner(s): LEE, CHI HO A
• Application Number:
  US08/748,487
• Time in Patent Office: 907 Days
• Field of Search: 370/229, 370/230, 370/232, 370/235, 370/236, 370/241, 370/240, 370/395
• US Class Current: 370/229
• CPC Class Codes: H04L 2012/562 Routing
• CPC Class Codes: H04L 2012/5635 Backpressure, e.g. for ABR
• CPC Class Codes: H04L 2012/565 Sequence integrity
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

A rate based flow and congestion control mechanism for packet communications whereby the acceleration and deceleration of the sending rate is moderated to be responsive to the traffic encountered. The method of the present invention also reduces oscillation in the transmission rate by being responsive to the characteristics of the network traffic and allowing burst intervals to be borrowed on a periodic basis.

Claims

1. A closed loop rate-based flow and congestion control system for a packet communications network providing a connection for the transmission of packets between a sending end node and a receiving end node of said network, each of said packets having an associated sequence number, said control system comprising:

means at said receiving end node for determining the lower of either the rate at which said packets are delivered from said network to said receiving end node or the rate at which said packets are delivered from said receiving end node to a connected user;

means for transmitting said lower rate from said receiving end node to said sending end node of said network; and

means for adjusting the rate at which packets are launched from said sending end node on said connection in response to said lower rate, said means for adjusting comprising;

means for switching to an alternate path if said connection between said sending end node and said receiving end node is disrupted;

means at said sending end node to record a sequence number associated with the last packet sent prior to the switch to said alternate path;

means at said receiving end node of determining if one or more of said packets were sent from said sending end node and not received at said receiving node, thereby being lost;

means at said receiving end node for requesting that the sending end node resend any of said lost packets; and

,

means at said sending end node for comparing the sequence numbers of said lost packets with said recorded sequence number and, only if said sequence numbers of said lost packets are greater than said recorded sequence number said sending end node reduces said transmission rate of said network.

2. A closed loop rate-based method for controlling data packet flow and congestion in a packet communications network providing a connection for the transmission of packets between a sending end node and a receiving end node of said network, said method comprising the steps of:

determining at said receiving end node the lower of either the rate at which said packets are delivered from said network to said receiving end node or the rate at which said packets are delivered from said receiving end node to a connected user;

transmitting said lower rate from said receiving end node to said sending end node of said network; and

,

adjusting the rate at which the packets are launched from said sending end node on said connection in response to said lower rate, said adjusting step comprising the steps of;

switching to an alternate path if said connection between said sending end node and said receiving end node is disrupted;

recording, at said sending end node, a sequence number associated with the last packet sent prior to the switching to said alternate path;

determining, at said receiving node, if one or more of said packets were sent from said sending end node and not received at said receiving end node, thereby being lost;

requesting, but the receiving end node, that the sending end node resend any lost packets; and

,

comparing, at said sending end node, the sequence numbers of said lost packets with said recorded sequence number and, only if said sequence numbers of said lost packets are greater than said recorded sequence number, said sending end node reduces said transmission rate of said network.

3. A media containing programmable software implementing a closed loop rate-based flow and congestion control system for a packet communications network providing a connection for the transmission of packets between a sending end node and a receiving end node of said network, each of said packets having an associated sequence number, said control system comprising:

programmable means at said receiving end node for determining the lower of either the rate at which said packets are delivered from said network to said receiving end node or the rate at which said packets are delivered from said receiving end node to a connected user;

programmable means for transmitting said lower rate from said receiving end node to said sending end node of said network; and

programmable means for adjusting the rate at which packets are launched from said sending end node on said connection in response to said lower rate, said programmable means for adjusting comprising;

programmable means for switching to an alternate path if said connection between said sending end node and said receiving end node is disrupted;

programmable means at said sending end node to record a sequence number associated with the last packet sent prior to the switch to said alternate path;

programmable means at said receiving end node of determining if one or more of said packets were sent from said sending end node and not received at said receiving node, thereby being lost;

programmable means at said receiving end node for requesting that the sending end node resend any of said lost packets; and

,

programmable means at said sending end node for comparing the sequence numbers of said lost packets with said recorded sequence number and, only if said sequence numbers of said lost packets are greater than said recorded sequence number said sending end node reduces said transmission rate of said network.

4. A closed loop rate-based flow and congestion control system for a packet communications network providing a connection for the transmission of packets between a sending end node and a receiving end node of said network, each of said packets having an associated sequence number, said control system comprising:

means at said receiving end node for determining the lower of either the rate at which said packets are delivered from said network to said receiving end node or the rate at which said packets are delivered from said receiving end node to a connected user;

means for transmitting said lower rate from said receiving end node to said sending end node of said network; and

means for adjusting the rate at which packets are launched from said sending end node on said connection in response to said lower rate, said means for adjusting comprising;

means for switching to an alternate path if said connection between said sending end node and said receiving end node is disrupted;

means at said sending end node to record a sequence number associated with the last packet sent prior to the switch to said alternate path;

means at said receiving end node of determining if one or more of said packets were sent from said sending end node and not received at said receiving node, thereby being lost;

means at said receiving end node for requesting that the sending end node resend any of said lost packets; and

,

means at said sending end node for comparing the sequence numbers of said lost packets with said recorded sequence number and, only if said sequence numbers of said lost packets are greater than said recorded sequence number said sending end node reduces said transmission rate of said network.

5. A closed loop rate-based flow and congestion control system for a packet communications network providing a connection for the transmission of packets between a sending end node and a receiving end node of said network, said control system comprising:

means for adjusting the rate at which packets are launched from said sending end node on said connection, said means for adjusting comprising;

means for setting an initial sending rate;

means for defining an optimistic interval in terms of number of frames or packets transmitted without error or delay;

means for defining an acceleration increment;

means for defining a noise tolerance for said rate at which packets are launched;

means for determining when an optimistic interval has been obtained and, incrementing said sending rate by said acceleration increment in response to obtaining said optimistic interval;

means for determining when a packet is lost in said transmission and recording said send rate; and

,

means for decrementing said sending rate by a predetermined amount in response to a predetermined consecutive number of said lost packets within said noise tolerance of said sending rate and, correspondingly, decrementing said acceleration increment by a percentage of said previous acceleration increment.

6. A closed loop rate-based flow and congestion control method for a packet communications network providing a connection for the transmission of packets between a sending end node and a receiving end node of said network, said method comprising the steps of:

adjusting the rate at which packets are launched from said sending end node on said connection, said adjusting comprising;

setting an initial sending rate;

defining an optimistic interval in terms of number of frames or packets transmitted without error or delay;

defining an acceleration increment;

defining a noise tolerance for said rate at which packets are launched;

determining when an optimistic interval has been obtained and, incrementing said sending rate by said acceleration increment in response to obtaining said optimistic interval;

determining when a packet is lost in said transmission and recording said sending rate; and

,

decrementing said sending rate by a predetermined amount in response to a predetermined consecutive number of said lost packets within said noise tolerance of said sending rate and, correspondingly, decrementing said acceleration increment by a percentage of said previous acceleration increment.

7. Media containing programmable software comprising a closed loop rate-based flow and congestion control system for a packet communications network providing a connection for the transmission of packets between a sending end node and a receiving end node of said network, said control system comprising:

programmable means for adjusting the rate at which packets are launched from said sending end node on said connection, said programmable means for adjusting comprising;

programmable means for setting an initial sending rate;

programmable means for defining an optimistic interval in terms of number of frames or packets transmitted without error or delay;

programmable means for defining an acceleration increment;

programmable means for defining a noise tolerance for said rate at which packets are launched;

programmable means for determining when an optimistic interval has been obtained and, incrementing said sending rate by said acceleration increment in response to obtaining said optimistic interval;

programmable means for determining when a packet is lost in said transmission and recording said sending rate; and

,

programmable means for decrementing said sending rate by a predetermined amount in response to a predetermined consecutive number of said lost packets within said noise tolerance of said sending rate and, correspondingly, decrementing said acceleration increment by a percentage of said previous acceleration increment.

8. A closed loop rate-based method for controlling data packet flow and congestion in a packet communications network providing a connection for the transmission of packets between a sending end node and a receiving end node of said network, said method comprising the steps of:

determining a burst interval for said sending end node;

determining a burst size for said sending end node;

determining, when a packet is available for sending, whether the packet is capable of being sent within a next burst interval; and

,

borrowing time from the next burst interval of said sending end node, thereby allowing said packet to be sent during a current burst interval if said packet can be sent in its entirety within the next burst interval and a burst interval immediately previous to said current burst interval has not borrowed time.

9. A closed loop rate-based method for controlling data packet flow and congestion in a packet communications network providing a connection for the transmission of packets between a sending end node and a receiving end node of said network, said method comprising the steps of:

determining a burst interval for said sending end node;

determining a burst size for said sending end node;

determining, when a packet is available for sending, whether the packet is capable of being sent within a next burst interval; and

,

borrowing time from the next burst interval of said sending end node, thereby allowing said packet to be sent during a current burst interval if said packet can be sent in its entirety within the next burst interval and a burst interval immediately previous to said current burst interval has not borrowed time.