Network protocol and associated methods for optimizing use of available bandwidth

• US 6,587,875 B1
• Filed: 04/30/1999
• Issued: 07/01/2003
• Est. Priority Date: 04/30/1999
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Ogus, Aaron W.
• Primary Examiner(s): EL HADY, NABIL M
• Application Number:
  US09/303,067
• Time in Patent Office: 1,523 Days
• Field of Search: 709/223, 709/224, 709/232, 709/233, 709/234, 709/235
• US Class Current: 709/223
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/11 Identifying congestion
• CPC Class Codes: H04L 47/19 at layers above the network layer network arrangements for networked applications for scheduling or organising the servicing of application requests H04L67/60
• 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/35 by embedding flow control information in regular packets, e.g. piggybacking

Abstract

A network protocol and associated methods for optimizing use of available bandwidth across a network under varying traffic conditions. The protocol and methods allow the available bandwidth for a link connecting two computers to be determined on an ongoing basis. A method for measuring a clock bias between two computers linked in communication is also presented, along with methods for determining link saturation and dropped messages. The message send rate of the link can be continually tuned based on the measured bandwidth, link saturation condition, number of backlogged messages and/or detection of dropped messages. The protocol and methods preferably are implemented as part of an application program interface. The protocol resides at the application layer, and can be used for various network protocol suites, including TCP/IP and IPX/SPX.

Claims

1. A method for optimizing the use of available bandwidth across a computer network, the network facilitating a link between a first computer in communication with a second computer, the link having a variable bandwidth, the method comprising:

(a) sending messages from the first computer to the second computer while increasing a rate at which messages are sent until saturation of the link is detected, the link saturation creating a backlog of messages across the link;

(b) calculating bandwidth of the link in response to detecting that the link is saturated;

(c) reducing the rate at which messages are sent to the calculated bandwidth;

(d) calculating a wait time to clear out the backlogged messages;

(e) stalling issuance of messages from the first computer to the second computer for a time equal to the calculated wait time;

repeating steps (a)-(e) during continued communications from the first computer to the second computer.

2. The method of claim 1, wherein:

each message sent from the first computer to the second computer is an outbound message having a unique message number,

a send time for each outbound message is recorded in the first computer,

each outbound message is acknowledged by a corresponding acknowledge message sent from the second computer to the first computer,

and further including;

calculating roundtrip latency by calculating a difference between a send time of an outbound message and a local receive time of the corresponding acknowledge message in the first computer; and

averaging roundtrip latencies for outbound messages;

wherein link saturation is determined, at least in part, by observing a statistically-significant deviation between the average roundtrip latency and the roundtrip latency for an individual message.

3. The method of claim 2, wherein the statistically-significant deviation is at least three standard deviations.

4. The method of claim 2 wherein each acknowledge message includes a remote receive time indicating a time according to a clock on the second computer that the corresponding outbound message was received;

and further including;

determining whether an increase in the roundtrip latency is due to outbound latency by;

calculating a clock bias for outbound messages by calculating a difference between the send and remote receive times for the messages,

calculating a change in the clock bias; and

evaluating whether the change in the clock bias is more than a predetermined fraction of the roundtrip latency;

wherein an increase in roundtrip latency is considered to be attributable to an increase in outbound latency when the change in clock bias is more than the predetermined fraction of the roundtrip latency.

5. A computer-readable medium having computer-executable instructions for performing the steps recited in claim 1.

6. A method for maintaining a clock offset between a first computer and a second computer, the first and second computers linked in communication across a network and each having a clock, the method comprising:

sending a first message from the first computer to the second computer on a network communication link;

recording a message send time, which is the time the message is sent according to the first computer'"'"'s clock;

receiving an acknowledgment message acknowledging receipt of the message from the second computer to the first computer that includes a remote receive time, which is the time the second computer received the message according to the second computer'"'"'s clock;

computing a clock offset by calculating a difference between the remote receive time and the message send time;

monitoring the link for link saturation;

in response to detecting link saturation, reducing a send rate;

re-computing the clock offset for a new message sent after reducing the send rate; and

calculating a wait time, the wait time being a measure of time that issuance of the new message is stalled after reducing the send rate to clear a backlog of messages on the link.

7. The method of claim 6 further including:

calculating outbound bandwidth in response to detecting link saturation; and

calculating the wait time based on the outbound bandwidth and latency of the link;

wherein outbound bandwidth is computed from acknowledge messages sent from the second computer, including receive times recorded at the remote computer and an amount of data received at the remote computer corresponding to the receive times; and

the latency is derived from recording local send times of messages sent from the first computer and acknowledge messages that the second computer sends to acknowledge receipt of the messages from the first computer.

8. A computer-readable medium having computer-executable instructions for performing the steps recited in claim 6.

9. A method for maintaining a clock offset between a first computer and a second computer, the first and second computers linked in communication across a network and each having a clock, the method comprising:

sending a first message from the first computer to the second computer on a network communication link;

recording a message send time, which is the time the message is sent according to the first computer'"'"'s clock;

receiving an acknowledgment message acknowledging receipt of the message from the second computer to the first computer that includes a remote receive time, which is the time the second computer received the message according to the second computer'"'"'s clock;

computing a clock offset by calculating a difference between the remote receive time and the message send time;

monitoring the link for link saturation;

in response to detecting link saturation, reducing a send rate;

re-computing the clock offset for a new message sent after reducing the send rate;

calculating a backlog of messages sent on the link;

stalling issuance of the new message until the calculated backlog is cleared; and

re-computing the clock offset for the new message sent after clearing the calculated backlog.

10. A method for tuning a communications link across a network linking a first local computer to a second remote computer, the local and remote computers each having a clock, the method comprising:

(a) sending outbound messages from the local computer to the remote computer, wherein each message has a message identifier, a send time is recorded for each message according to the local computer clock, and the messages are sent at a progressively increasing rate until a link saturation condition is detected, the link saturation condition causing a backlog of messages;

(b) receiving acknowledge messages from the remote computer acknowledging receipt of the outbound messages by the remote computer, the acknowledge messages including a remote receive time marking a time a corresponding outbound message was received according to the remote computer clock, the message identifier of the corresponding outbound message, and a count of bytes received on the remote computer;

(c) recording a local receive time for each acknowledge message received in the local computer according to the local computer'"'"'s clock;

(d) determining a roundtrip latency for each outbound message based on the send time recorded in (a) and the local receive time in (c);

(e) calculating an average roundtrip latency based at least on the roundtrip latency determined in step (d);

(f) calculating a clock bias between the local computer clock and the remote computer clock by calculating a difference between the local send time and the remote receive time for an outbound message;

(g) checking for a link saturation condition by comparing roundtrip latency for a recent message with the average roundtrip latency and comparing a change in the clock bias with the roundtrip latency for the recent message to determine whether an increase in roundtrip latency is due to an increase in outbound latency;

(h) in response to detecting the link saturation condition, computing outbound bandwidth in the local computer by dividing a number of bytes received in the remote computer as indicated in first and second acknowledge messages by a time period over which the number of bytes were received as indicated in the remote receive times of the first and second acknowledge messages;

(i) calculating a wait time, the wait time being an amount of time that issuance of outbound messages should be stalled to clear out the backlogged messages on the link, and stalling issuance of messages for the wait time; and

(n) adjusting a message send rater to approximate the calculated outbound bandwidth.

11. A computer-readable medium having computer-executable instructions for performing the steps recited in claim 10.

12. A method for calculating the outbound bandwidth of a network linking a first local computer to a second remote computer, the local and remote computers each having a clock, the method comprising:

(a) sending outbound messages from the local computer to the remote computer, wherein each message has a message identifier and the messages are sent at a progressively increasing rate until a link saturation condition is detected, the link saturation condition causing a backlog of messages;

(b) receiving acknowledge messages from the remote computer acknowledging receipt of the outbound messages by the remote computer, the acknowledge messages including a remote receive time marking a time the outbound message was received according to the remote computer clock, the message identifier of the corresponding outbound message, and a count of bytes received on the remote computer; and

(c) in response to detecting the link saturation condition, computing outbound bandwidth in the local computer by dividing a number of bytes received in the remote computer as indicated in first and second acknowledge messages by a time period over which the number of bytes were received as indicated in the remote receive times of the first and second acknowledge messages.

13. A computer-readable medium having computer-executable instructions for performing the steps recited in claim 12.

14. The method of claim 12 further comprising adjusting the message send rate of messages sent from the local computer to approximate the calculated outbound bandwidth.

15. The method of claim 12 further including:

calculating a wait time, the wait time being a measure of time that issuance of the new message is stalled after reducing the send rate to clear a backlog of messages on the link.

16. A computer-readable medium having stored thereon a first data structure comprising:

(a) a first data field including a message identifier; and

(b) a second data field including a message body; and

further including a second data structure comprising;

(c) a first data field including a message identifier;

(d) a second data field including a count of data received in a second computer from a first computer; and

(e) a third data field including a timestamp corresponding to the time a message is received on the second computer;

wherein outbound messages comprising the first data structure are sent between the first computer and the second computer, the second computer acknowledging receipt of the outbound messages by sending an acknowledge message comprising the second data structure to the first computer, the message identifiers of the first and second data structures being used to match the outbound messages with the acknowledge messages to detect saturation of a link between the first and second computer via isolating which part of roundtrip latency is attributable to an outbound or return path.

17. A method for determining network link saturation in a communications link across a network linking a first local computer to a second remote computer, the local and remote computers each having a clock, the method comprising:

(a) sending outbound messages from the local computer to the remote computer, wherein each message has a message identifier, a local send time is recorded for each message according to the local computer clock, and the messages are sent at a progressively increasing rate until a link saturation condition is detected, the link saturation condition causing a backlog of messages;

(b) receiving acknowledge messages from the remote computer acknowledging receipt of the outbound messages by the remote computer, the acknowledge messages including a remote receive time marking a time the outbound message was received according to the remote computer clock, the message identifier of the corresponding outbound message;

(c) recording a local receive time for each acknowledge message received in the local computer according to the local computer'"'"'s clock;

(d) determining a roundtrip latency for each outbound message based on the local send time recorded in (a) and the local receive time in (c);

(e) calculating an average roundtrip latency based at least on the roundtrip latency determined in step (d);

(f) calculating a clock bias between the local computer clock and the remote computer clock by calculating a difference between the local send time and the remote receive time for an outbound message; and

(g) checking for a link saturation condition by comparing roundtrip latency for a recent message with the average roundtrip latency and comparing a change in the clock bias with the roundtrip latency for the recent message to determine whether an increase in roundtrip latency is due to an increase in outbound latency.

18. A computer-readable medium having computer-executable instructions for performing the steps recited in claim 17.