Flow control for high speed networks

• US 5,063,562 A
• Filed: 05/23/1990
• Issued: 11/05/1991
• Est. Priority Date: 05/23/1990
• Status: Expired due to Term

• Current Assignee: Intergraph Hardware Technologies Company (Hexagon AB)
• Original Assignee: International Business Machines Corporation
• Inventors: Kaplan, Marc A., Barzilai, Tsipora P., Chen, Mon-Song, Kadaba, Bharath K.
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): Chin, Wellington
• Application Number:
  US07/527,609
• Time in Patent Office: 531 Days
• Field of Search: 370/82, 370/83, 370/84, 370/94.1, 370/94.2, 370/94.3, 370/89, 370/79, 370/95.1, 370/95.2, 370/95.3, 370/85.8, 370/85.7, 370/29, 370/24
• US Class Current: 370/231
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/18 End to end
• CPC Class Codes: H04L 47/26 using explicit feedback to the source, e.g. choke packets
• CPC Class Codes: H04L 47/27 Evaluation or update of window size, e.g. using information derived from acknowledged [ACK] packets

Abstract

A method and apparatus for dynamically adjusting the window size in a session between a sender and a receiver over a link of a packet transmission network. This invention discloses a dynamic window adjustment scheme to determine the optimum window size with a minimum number of iterations. This invention also covers a method and apparatus for sharing pacing credits among a number of sessions during which packets are transmitted over the network. With this invention sessions having no packets to transmit will send pacing credits to a shared credit pool while pacing credits will be distributed to those session having packets to transmit.

Claims

1. In a packet transmission network, a method of adjusting the window size in a session between a sender and a receiver on a link of said network, said method comprising:

transmitting a pacing response to said sender indicating the size of a subsequent window to be transmitted in a session between said sender and said receiver, said size of said subsequent window being a number of packets that said sender can transmit in a subsequent window,

said subsequent window size (WS) being determined by decreasing a previous window size if when said window size is to be calculated, either QL≠

0, or QL=0 and a pacing request was not received within a specified time interval, said window size thus being determined according to the following formula;

space="preserve" listing-type="equation">WS=max(W.sub.min, CNT-QL+B),

where CNT is the number of packets received by said receiver from said sender during a round trip delay which is the time needed for a first packet to be transmitted from said sender to said receiver plus the time needed for a second packet to be transmitted from said receiver to said sender after said first packet is received by said receiver, where QL is the number of packets stored in a queue of said receiver for future transmission to another node of said network, where W_min is a prespecified parameter denoting a minimum window size, and where B is also a prespecified parameter,

said subsequent window size being determined by increasing a previous window size if when said subsequent window size is to be calculated, QL=0 and a pacing request was received in said specified time interval, said subsequent window size thus assuming a value between CNT and W_max, where W_max is a prespecified parameter.

2. In a packet transmission network, a method of adjusting a window size in a session between a sender and a receiver on a link of said network, said method comprising:

transmitting a pacing request to said receiver indicating a request for a subsequent window size for a subsequent window, said subsequent window size being a number of packets that said sender can transmit in said subsequent window of said session; and

transmitting, in response to said pacing request, a pacing response to said sender indicating the size of said subsequent window to be transmitted in said session between said sender and said receiver,

said subsequent window size being determined by decreasing a previous window size if when said subsequent window size (WS) is to be calculated, either QL≠

0, or QL=0 and a pacing request was not received in a specified time interval, said subsequent window size thus being determined according to the following formula;

WS=max( W_min, CNT-QL+B), where CNT is the number of packets received by said receiver from said sender during a round trip delay which is the time needed for a first packet to be transmitted to said sender to said receiver plus the time needed for a second packet to be transmitted from said receiver to said sender after said first packet is received by said receiver, where QL is the number of packets stored in a queue of said receiver future transmission to another node of said network, where Wmin is a prespecified parameter denoting a minimum window size, and where B is also a prespecified parameter,

said subsequent window size being determined by increasing a previous window size if when said subsequent window size is to be calculated, QL=0 and a pacing request was received in said specified time interval, said subsequent window size assuming a value between CNT and W_max, where W_max is a prespecified parameter.

3. In a packet transmission network, a method of adjusting a window size in a session between a sender and a receiver of a link of said network, said method comprising:

transmitting, while a first window is being transmitted, a pacing response to said sender indicating a size of a second window to be transmitted in a session between said sender and said receiver, said second window being the window transmitted in said session after the transmission of said first window in said session without any other window being transmitted in the time between the transmission of said first and second windows, said size of said second window being a number a packets that said sender can transmit in said second window,

said size of said second window being determined by decreasing a window size of said first window if, when said size of said second window is to be calculated, either QL≠

0, or QL=0 and a pacing request was not received by said receiver in a specified time interval, said subsequent window size thus being determined according to the following formula;

WS(window size)= max( W_min, CNT-QL+B), where CNT is the number of packets received by said receiver from said sender during a round trip delay which is the time needed for a first packet to be transmitted from said receiver to said sender plus the time needed for a second packet to be transmitted from said sender to said receiver after said first packet is received by said sender, where QL is the number of packets stored in a transmission queue of said receiver, where W_min is a prespecified parameter denoting a minimum window size, and where B is also a prespecified parameter,

said window size of said second window being determined by increasing a size of said first window if when said size of said second window is to be calculated, QL=0 and a pacing request was received by said receiver in said specified time interval, said size of said second window thus assuming a value between CNT and W_max where W_max is a prespecified parameter.

4. In a packet transmission network, a method of adjusting the window size in a session between a sender and a receiver of a link of said network, said method comprising:

transmitting, in a first window, a pacing request to said receiver indicating a request for a window size for a second window, said window size being a number of packets that said sender can transmit in said second window of said session; and

transmitting, while a first window is being transmitted and in response to said pacing request, a pacing response to said sender indicating said window size of said second window to be transmitted in a session between said sender and said receiver, said second window being the window transmitted in said session after the transmission of said first window in said session without any other windows being transmitted in the time between the transmission of said first and second windows, said window size of said second window being a number of packets that said sender can transmit in said second window,

said window size of said second window being determined by decreasing a window size of said first window if, when said window size of said second window is to be calculated, either QL≠

0, or QL=0 and said pacing request was not received by said receiver in a specified time interval, said window size thus being determined according to the following formula;

WS (window size)= max( W_min,CNT-QL+B), where CNT is the number of packets received by said receiver from said sender during a round trip delay which is the time needed for a first packet to be transmitted from said receiver to said sender plus the time needed for a second packet to be transmitted from said sender to said receiver after said first packet is received by said sender, where QL is the number of packets stored in a transmission queue of said receiver, where W_min is a prespecificed parameter denoting a minimum window size, and where B is also a prespecified parameter,

said size of said second window determined by increasing a size of said first window, if when said size of said second window is to be calculated, QL=0 and a pacing request was received by said receiver in said specified time interval, said size of said second window thus assuming a value between CNT and W_max where W_max is a prespecified parameter.

5. In a packet transmission network, a method of adjusting the window size in a session between a sender and a receiver of a link of said network, said method comprising:

transmitting pacing requests to said receiver, each of said pacing requests being at least a bit in a packet indicating a request for a window size for a respective window immediately following a window containing a respective one of said pacing requests;

transmitting pacing responses to said sender, each of said pacing responses being in response to a respective one of said pacing requests, each pacing response being at least a bit in a packet indicating a window size for respective window immediately following a window containing each pacing request;

transmitting acknowledgement bits to said receiver from said sender, each of said acknowledgement bits being transmitted in the next packet immediately following the reception of a respective one of said pacing responses by said sender, each acknowledgement bit indicating the reception of a respective pacing response of said pacing responses;

determining window sizes upon reception of said acknowledgement bits, each window size being determined upon each reception of one of said acknowledgement bits, each window size to be included in one of said pacing responses which is to be the next pacing response transmitted to said sender after each reception of one of said acknowledgement bits,

each said window size being determined using the following formula;

WS(windowsize)= max( W_min, CNT-QL+B) if QL≠

0, or if QL=0 and a last packet received by said receiver does not contain one of said pacing requests, otherwise, each said window size being determined to assume a value between CNT and W_max where, for each determination of each of said window sizes, QL is the number of packets stored in a queue of said receiver when a corresponding one of said acknowledgement bits is received but before a packet containing said corresponding acknowledgement bit is stored in said queue, where CNT is the number of packets transmitted from said sender to said receiver during the interval between the reception of said corresponding acknowledgement bit and the reception of a last one said pacing requests that is received prior to said corresponding acknowledgement bit, where W_max and W_min are respectively, prespecified maximum and minimum window size that can be used in said session, and where B is a prespecified constant.

6. An apparatus for adjusting a window size in a session between a sender and a receiver communicating over a link of a packet communications network, said apparatus comprising:

transmitting means for transmitting a pacing response to said sender indicating the size of a subsequent window to be transmitted in a session between said sender and said receiver, said size of said subsequent window being a number of packets that said sender can transmit in a subsequent window; and

determining means for determining said subsequent window size (WS) wherein said subsequent window size is determined by decreasing a previous window size if when said window size is to be calculated, either QL≠

0, or QL=0 and a pacing request was not received in a specified time interval, then said subsequent window size being a size decreased from said previous window size according to the following formula;

WS=Max W_min, CNT-QL+B), where CNT is the number of packets received by said receiver from said sender during a round trip delay which is the time needed for a first packet to be transmitted from said sender to said receiver plus the time needed for a second packet to be transmitted from said receiver to said sender after said first packet is received by said receiver, where QL is the number of packets stored in a queue of said receiver for future transmission to another node of said network, where W_min is a prespecified parameter denoting a minimum window size, and where B is also a prespecified parameter, and wherein said subsequent window size is determined by increasing said previous window size if when said window size is to be calculated, QL=0 and a pacing request was received in said specified time interval, said subsequent window size thus assuming a value between CNT and W_max, where W_max is a prespecified parameter.

7. An apparatus for adjusting a window size in a session between a sender and a receiver communicating over a link of a packet communications network, said apparatus comprising:

means for transmitting a pacing request to said receiver indicating a request for a subsequent window size, said subsequent window size being a number of packets that said sender can transmit in a subsequent window in said session;

means for transmitting, in response to said pacing request, a pacing response to said sender indicating the size of subsequent window to be transmitted in said session between said sender and said receiver; and

means for determining said subsequent window size (WS) wherein said subsequent window size is determined by decreasing a previous window size if when said window size is to be calculated, either QL≠

0, or QL=0 and a pacing request was not received in a specified time interval, said window size then being decreased according to the following formula;

WS=max( W_min, CNT-QL+B), where CNT is the number of packets received by said receiver from said sender during a round trip delay which is the time needed for a first packet to be transmitted to said sender to said receiver plus the time needed for a second packet to be transmitted from said receiver to said sender after said first packet is received by said receiver, where QL is the number of packets stored in a queue of said receiver for future transmission to another node of said network, where W_min is a prespecified parameter denoting a minimum window size, and where B is also a prespecified parameter, and wherein said subsequent window is determined by increasing said previous window size if when said window size is to be calculated, QL=0 and a pacing request was received in said specified time interval, said subsequent window size being increased from said previous value to assume a value between CNT and W_max,where W_max is a prespecified parameter.

8. An apparatus for adjusting a window size in a session between a sender and a receiver communicating over a link of a packet communications network, said apparatus comprising:

means for transmitting, in a first window, a pacing request to said receiver indicating a request for a window size for a second window, said window size being a number of packets that said sender can transmit in said second window of said session;

means for transmitting, while a first window is being transmitted and in response to said pacing request, a pacing response to said sender indicating the size of said second window to be transmitted in said session between said sender and said receiver, said second window being a window transmitted in said session after the transmission of said first window in said session without any other windows being transmitted in the time between the transmission of said first and second windows, said size of said second window being a number of packets that said sender can transmit in said second window; and

means for determining said size of said second window wherein said second window size is determined by decreasing a window size of said first window if, when said size of said second window is to be calculated, either Q≠

0, or QL=0 and said pacing request was not received by said receiver in a specified time interval, said first window size then being decreased to said second window size according to the following formula;

space="preserve" listing-type="equation">WS(windowsize)= max( W.sub.min, CNT-QL+B),

where CNT is the number of packets received by said receiver from said sender during a round trip delay which is the time needed for a first packet to be transmitted from said receiver to said sender plus the time needed for a second packet to be transmitted from said sender to said receiver after said first packet is received by said sender, where QL is the number of packets stored in a transmission queue of said receiver, where W_min is a prespecified parameter denoting a minimum window size, and wherein said size of said second window is determined by increasing from a window size of said first window, if when said size of said second window is to be calculated, QL=0 and a pacing request was received by said receiver in said specified interval, said size of said second window being increased to assume a value between CNT and W_max where W_min is a prespecified parameter.

9. An apparatus for adjusting a window size in a session between a sender and a receiver communicating over a link of a packet communications network, said apparatus comprising:

means for transmitting pacing requests to said receiver, each of said pacing requests being at least a bit in a packet indicating a request for a window size for a respective window immediately following a window containing each pacing request;

means for transmitting pacing responses to said sender, each of said pacing responses being in response to a respective one of said pacing requests, each pacing response being at least a bit in a packet indicating a window size for respective window immediately following a window containing a respective one of said pacing requests;

means for transmitting acknowledgement bits to said receiver from said sender, each of said acknowledgement bits being transmitted in the next packet immediately following the reception of a respective one of said pacing responses by said sender, each acknowledgement bit indicating the reception of a respective pacing response of said pacing responses;

means for determining window sizes upon reception of said acknowledgement bits, each window size being determined upon each reception of one of said acknowledgement bits, each window size to be included in one of said pacing responses which is to be the next pacing response transmitted to said sender after each reception of one of said acknowledgement bits, each said window size being determined using the following formula;

WS(window size)= MaxW_min, CNT-QL+B) if QL≠

0, or if QL=0 and a last packet received by said receiver does not contain one of said pacing requests, otherwise, each said window size being determined to assume a value between CNT and W_max where, for each determination of each of said window sizes, QL is the number of packets stored in a queue of said receiver when a corresponding one of said acknowledgement bits is received but before a packet containing said corresponding acknowledgement bit is stored in said queue, where CNT is the number of packets transmitted from said sender to said receiver during the interval between the reception of said corresponding acknowledgement bit and the reception of a last one said pacing requests that is received prior to said corresponding acknowledgement bit, where W_max and W_min are respectively, prespecified maximum and minimum window sizes that can be used in said session, and where B is a prespecified constant.

10. In a packet transmission network, a method of sharing pacing credits among selected sessions of a plurality of sessions during which packets are to be transmitted, said method comprising:

polling each of said sessions to determine if a send queue corresponding to said each session has packets stored therein for transmission;

storing, for each of said selected sessions, at least one pacing credit in a shared credit pool if a send queue corresponding to said each selected session has no packets stored therein for transmission when said each selected session is polled; and

distributing pacing credits stored in said shared credit pool to those of said selected sessions whose corresponding send queues have packets stored therein for transmission.

11. A method as recited in claim 10 wherein, for each of said selected sessions, pacing credits are stored in said shared credit pool only if the pacing count for each selected session is greater the W'"'"', a first selected value.

12. A method as recited in claim 10 wherein, for each of said selected sessions, pacing credits stored in said shared credit pool are distributed to said each selected session only if said each selected session has a pacing count which is less than a second selected value.

13. A method as recited in claim 10, wherein each of said sessions may assume either of two modes, one of said modes being an exclusive scheduling mode in which pacing credits are neither distributed from nor sent to said shared credit pool, the other of said modes being a share scheduling mode in which pacing credits can be sent to or distributed from said shared credit pool, said method having at least one of said sessions in the shared scheduling mode, said sessions in said share scheduling mode being said selected session.

14. A method as recited in claim 13 wherein a first session of said sessions in said exclusive scheduling mode will change to said share scheduling mode when no one of said sessions transmits any packets during the time between two consecutive scheduling of said first session and during the time of the latter scheduling of said first session, and wherein any second session of said sessions will change from said share mode to said exclusive mode as soon as said second session can transmit a packet without receiving pacing credits distributed from the shared credit pool.

15. In a packet transmission network, an apparatus for sharing pacing credits among selected sessions of a plurality of sessions during which packets are to be transmitted, said method comprising:

means for polling each of said sessions to determine if a send queue corresponding to said each session has packets stored therein for transmission;

means for storing, for each of said selected sessions, at least one pacing credit in a shared credit pool if a send queue corresponding to said each selected session has no packets stored therein for transmission when said each selected session is polled; and

means for distributing pacing credits stored in said shared credit pool to those of said selected sessions whose corresponding send queues have packets stored therein for transmission.