Network protocol and associated methods for optimizing use of available bandwidth

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.

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.

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.

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.

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.

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.