Methods and protocol for simultaneous tuning of reliable and non-reliable channels of a single network communication link

• US 6,438,603 B1
• Filed: 04/30/1999
• Issued: 08/20/2002
• Est. Priority Date: 04/30/1999
• Status: Expired due to Term

• Current Assignee: Zhigu Holdings Limited
• Original Assignee: Microsoft Corporation
• Inventors: Ogus, Aaron W.
• Primary Examiner(s): Coulter, Kenneth R.
• Application Number:
  US09/302,559
• Time in Patent Office: 1,208 Days
• Field of Search: 709/238, 709/239, 709/237, 709/233, 709/232, 370/238
• US Class Current: 709/233
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/11 Identifying congestion
• CPC Class Codes: H04L 47/18 End to end
• 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 67/62 Establishing a time schedule for servicing the requests
• 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/162 involving adaptations of sockets based mechanisms secure socket layer H04L63/168
• CPC Class Codes: H04L 69/163 In-band adaptation of TCP data exchange; In-band control procedures
• CPC Class Codes: H04L 69/164 Adaptation or special uses of UDP protocol
• CPC Class Codes: H04L 69/165 Combined use of TCP and UDP protocols; selection criteria therefor
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]

Abstract

An application layer protocol supports reliable and non-reliable message transfer between a local and remote computer on a shared communications link. The application layer protocol uses a non-reliable transport layer protocol to implement both reliable and non-reliable channels over the shared link. When application programs want to send reliable data messages, they designate the data as such, and the application layer protocol sends the data in reliable messages with a request for acknowledgement. When application programs want to send non-critical data, they designate the data as such, and the application layer protocol sends the data in non-reliable messages that are not re-sent when dropped. Though it does not ensure delivery of non-reliable messages, the application layer selectively uses a request for acknowledge for non-reliable messages to gather operational data about the link. The protocol uses requests for acknowledgement for the dual purpose of ensuring reliable delivery for reliable messages and maintaining operational characteristics used to tune the link. In particular, the protocol uses the operational characteristics to detect link saturation, to calculate outbound bandwidth, to calculate a wait time for clearing backlogged messages and for adjusting the send rate based on the calculated bandwidth. This scheme enables the protocol to adapt the send rate based on varying link conditions.

Claims

1. A computer readable medium having software for tuning reliable and non-reliable channels on a single network communications link simultaneously, the link connecting a first computer with a second computer and having a variable bandwidth, the software comprising:

an application protocol for sending messages on the reliable and non-reliable channels of a single network communications link, the application protocol being operable to send reliable messages over the link by requesting an acknowledge message for selected reliable messages and re-transmitting reliable messages that have been dropped, the application protocol being operable to send non-reliable messages for which selected non-reliable messages include a request for acknowledgement; and

a non-reliable transport protocol in communication with the application protocol for sending both the reliable and non-reliable messages in response to requests from the application protocol over the single network communications link.

2. The computer readable medium of claim 1 wherein the selected reliable messages and selected non-reliable messages include:

a message identifier, and a request for acknowledgement operable to prompt a remote computer to send an acknowledge message;

wherein the acknowledge message includes;

a message identifier used to match the reliable messages and selected non-reliable messages with corresponding acknowledge messages, a count of data received, and a remote receive time;

and wherein the application protocol is operable to record a local send time for the selected reliable messages and selected non-reliable messages.

3. The computer readable medium of claim 2 wherein the application protocol is operable to maintain a measure of the clock offset between a clock on a local computer and a clock of a remote computer based on the local send time and remote receive times.

4. The computer readable medium of claim 2 wherein the application protocol is operable to detect link saturation on the network communications link.

5. The computer readable medium of claim 4 where the application protocol detects link saturation by maintaining a measure of round-trip latency and monitoring for a pre-defined increase in the round-trip latency.

6. The computer readable medium of claim 4 wherein the application protocol detects link saturation by maintaining a clock offset between a local computer clock and a remote computer clock and monitoring for a condition where a change in the clock offset is greater than a predetermined fraction of a measure of round trip latency, where the application protocol is operable to compute the measure of round trip latency based on the local send times and local receive times of the acknowledge messages.

7. The computer readable medium of claim 1 wherein the application protocol is operable to compute outbound bandwidth on the network communication link.

9. The method of claim 8 including:

repeating the steps of claim 1 during communications from the first computer to the second computer to adjust the message send rate according to the calculated bandwidth.

8. A method for tuning reliable and non-reliable channels on a single network communications link simultaneously, the link connecting a first computer with a second computer and having a variable bandwidth, the method comprising;

sending reliable messages over the reliable channel and non-reliable messages on the non-reliable channel from the first computer to the second computer while increasing the rate at which the messages are sent according to a predetermined scheme until saturation of the link is detected, the link saturation creating a backlog of messages across the link;

wherein reliable messages are sent with a request for acknowledgement and are re-transmitted when dropped, and wherein non-reliable messages are not re-transmitted when dropped;

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

reducing the message send rate from the first computer to the second computer over the link to the calculated bandwidth;

calculating a wait time to clear out the backlogged messages; and

stalling issuance of messages from the first computer to the second computer over both the reliable and non-reliable channels from the first computer to the second computer over the link for a time equal to the calculated wait time.

10. The method of claim 8 wherein selected reliable messages and selected non-reliable messages are marked to request an acknowledge message from the second computer;

wherein an acknowledge message identifies a message being acknowledged, a remote receive time indicating a time the message being acknowledged was received in the second computer, and a count of data received in the remote computer at the remote receive time; and

wherein the remote receive times and the count of data received are used to calculate the bandwidth of the link.

11. The method of claim 8 wherein:

outbound messages sent from the first computer to the second computer, including selected reliable messages and selected non-reliable messages, have a unique message number and a request for acknowledgement,

a send time for the outbound messages is recorded in the first computer, and

the outbound messages are 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.

12. The method of claim 11 wherein the statistically-significant deviation is at least three standard deviations.

13. The method of claim 11 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.

14. The method of claim 8, wherein the first computer is a local computer having a clock and the second computer is a remote computer having a clock, and wherein selected reliable messages and selected non-reliable messages have a unique identifier, and a request for acknowledgement, the method including:

recording for selected reliable messages and the selected non-reliable messages a local send time marking the time that each of the messages was sent from the local computer according to the local computer clock;

receiving acknowledge messages acknowledging receipt of reliable messages and non-reliable messages that requested acknowledgement, the acknowledge messages each including a remote receive time marking the time an acknowledged message was received according to the remote computer clock, an identifier identifying the acknowledged message, and a count of data received in the remote computer; and

calculating outbound bandwidth of the link in the local computer by dividing an amount of data received in the remote computer as indicated in first and second acknowledge messages by a time period over which the data was received as indicated in the remote receive times of the first and second acknowledge messages.

15. The method of claim 8 wherein calculating the wait time includes:

calculating an amount of un-acknowledged data sent from the first computer; and

dividing the amount of un-acknowledged data by the calculated bandwidth of the link to determine the wait time.

16. The method of claim 15 further including:

before the dividing step, reducing the amount of un-acknowledged data by an estimate of outbound messages representing an amount of messages sent from the first computer yet not received in the second computer, and inbound acknowledge messages representing an amount of messages received in the second computer but whose acknowledge messages have not been received in the first computer.

17. The method of claim 16 wherein the estimate of outbound messages is computed as the calculated outbound bandwidth multiplied by a measure of outbound latency, and the estimate of inbound acknowledge messages is computed as a measure of the inbound bandwidth multiplied by a measure of inbound latency.

18. The method of claim 17 wherein the measure of outbound latency is half of an average roundtrip latency computed from the send times of outbound messages and receive times of inbound acknowledge messages corresponding to the outbound messages, and the measure of inbound bandwidth is the calculated outbound bandwidth.

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

20. A computer-readable medium having stored thereon a first data structure comprising;

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

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

(c) a third data field including an acknowledge field; and

further including a second data structure comprising

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

(e) a second data field including a count of data received at a second computer from a first computer; and

(f) 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 when an acknowledge request is indicated in the acknowledge field by sending an acknowledge message comprising the second data structure to the local computer, the unique message identifier fields of the first and second data structures being used to match the outbound messages with the acknowledge messages.