Method and computer program product for efficiently and reliably sending small data messages from a sending system to a large number of receiving systems

• US 6,381,215 B1
• Filed: 06/29/1998
• Issued: 04/30/2002
• Est. Priority Date: 06/29/1998
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Hamilton, Keith S., Meizlik, Robert Steven
• Primary Examiner(s): MARCELO, MELVIN C
• Application Number:
  US09/106,400
• Time in Patent Office: 1,401 Days
• Field of Search: 370/229-232, 370/235, 370/236, 370/390, 370/474
• US Class Current: 370/236
• CPC Class Codes: H04L 1/0002 by adapting the transmission rate
• CPC Class Codes: H04L 1/0015 characterised by the adaptation strategy
• CPC Class Codes: H04L 1/1685 the supervisory signal being transmitted in response to a specific request, e.g. to a polling signal
• CPC Class Codes: H04L 1/1848 Time-out mechanisms
• CPC Class Codes: H04L 1/1854 Scheduling and prioritising arrangements
• CPC Class Codes: H04L 1/1883 using multiple timers
• CPC Class Codes: H04L 1/1887 Scheduling and prioritising arrangements
• CPC Class Codes: H04L 2001/0093 Point-to-multipoint

Abstract

In a network with a sending system networked to at least one receiving system, it is sometimes desirable to transfer relatively short messages between the sending system and one or more receiving systems in a highly reliable yet highly efficient manner. The present invention defines two short message protocols, one of which relies on a statistical model and the other of which uses positive acknowledgement to track receipt of transmitted packets by intended recipient. The statistical reliability mode is based on the observation that for each packet in a message that is transmitted, the probability that at least one packet of the message is received by a given system increases. Thus, in the statistical reliability mode messages are divided into a guaranteed minimum number of packets, with additional packets being added if the message length is insufficient to fill the minimum number of packets. The positive reliability mode of the present invention periodically sets an acknowledgement flag in the packets transmitted for a message. Receiving systems send an acknowledgement in response to receipt of that packet. The sending system tracks receipt of acknowledgements by intended recipient and retransmits any unacknowledged packets so as to positively assure the packets are received. Receiving systems send negative acknowledgements to request retransmission of missing packets. Negative acknowledgement suppression is implemented at both the sender and receiver to prevent a flood of negative acknowledgements from overwhelming the network. Packets are transmitted by the sending system at a transmission rate selected to avoid any adverse impact on the packet loss rate of the network.

Claims

1. In a network comprising a sending system networked together with at least one receiving system, a method for efficiently and reliably transmitting a data message from the sending system to the at least one receiving system in a manner that minimizes network traffic while maintaining high reliability, the method comprising the steps of:

dividing the message to be sent into a plurality of data blocks and placing each data block into a sequentially identified transmission packet;

detecting if the message fills a number of transmission packets that is less than a defined minimum number, and if so, then creating additional sequentially identified transmission packets until said defined minimum number are available;

selecting a transmission rate to be used in transmitting said plurality of data blocks, said transmission rate being selected between a minimum and maximum value according to a defined method which uses a measure of the packet loss rate in the network to adjust the transmission rate so that the packets may be transmitted as quickly as possible while minimizing the effect of transmitting the packets on the packet loss rate of the network;

transmitting said sequentially identified transmission packets from the sending system to the at least one receiving system at the selected transmission rate; and

at each receiving system which receives at least one of said sequentially identified transmission packets, determining if a transmission packet making up the message has not been received, and in response to the determination, sending a negative acknowledgment to the sending system identifying the unreceived packet so that the unreceived packet may be re-transmitted.

2. A method for transmitting a message as recited in claim 1 wherein said transmission rate is selected as a weighted sum of a transmission rate calculated according to a defined method on a current iteration of the method and a transmission rate calculated according to the defined method on a previous iteration of the method.

3. A method for transmitting a message as recited in claim 2 wherein the defined method comprises the steps of measuring a quantity indicative of the packet loss rate in the network and determining the amount that the current packet loss rate is above or below a target loss rate by subtracting the target loss rate from the current packet loss rate.

4. A method for transmitting a message as recited in claim 3 wherein the quantity indicative of the packet loss rate is a measurement of the number of requests for packet retransmission that are received.

5. A method for transmitting a message as recited in claim 1 wherein the defined method that selects the transmission rate selects a transmission rate such that:

when the measure of the packet loss rate indicates steadily degrading network conditions, the defined method steadily adjusts the transmission rate downward until either the minimum value is reached or until network conditions improve;

when the measure of the packet loss rate indicates steadily improving network conditions, the defined method steadily adjusts the transmission rate upward until either the maximum value is reached or until network conditions degrade;

when the measure of the packet loss rate indicates either a short term improvement or degradation of network conditions, the defined method leaves the transmission rate relatively unchanged;

when the measure of the packet loss rate indicates a prolonged condition where the packet loss rate is above the desired maximum packet loss rate, the defined method adjusts the transmission rate downward until the minimum value is reached; and

when the measure of the packet loss rate indicates a prolonged condition where the packet loss rate is below the desired maximum packet loss rate, the defined method adjusts the transmission rate upward until the maximum value is reached.

6. A method for transmitting a message as recited in claim 1 wherein the transmission rate is selected by performing at least the steps of:

measuring a quantity indicative of the current packet loss rate in the network;

subtracting the quantity from a second quantity indicative of the desired packet loss rate and comparing the resultant value to a threshold value and if the resultant value is below the threshold, then setting a difference parameter to zero, otherwise setting the difference parameter to the resultant value;

setting a rate change parameter equal to a base rate change value if the difference parameter is zero, otherwise setting the rate change parameter equal to the negative of the base rate change value multiplied by the difference parameter;

calculating a raw transmission rate for a current iteration of the method equal to the sum of the rate change parameter and a weighted transmission rate calculated on a previous iteration of the method;

selecting, as the transmission rate, a weighted sum of the raw transmission rate for the current iteration of the method and a raw transmission rate on the previous iteration of the method.

7. In a network comprising a sending system networked together with at least one receiving system, a method for efficiently and reliably transmitting a data message from the sending system to the at least one receiving system in a manner that minimizes network traffic while maintaining high reliability, the method comprising the steps of:

dividing the message to be sent into a plurality of data blocks each of which is carried by a sequentially identified transmission packet, and if the total number of transmission packets is less than a defined minimum number, then creating additional sequentially identified transmission packets until said defined minimum number are available;

selecting a transmission rate to be used in transmitting said plurality of data blocks, said transmission rate being selected between a minimum and maximum value according to a defined method which uses a measure of the packet loss rate in the network to adjust the transmission rate so that the packets may be transmitted as quickly as possible while minimizing the effect of transmitting the packets on the packet loss rate of the network;

transmitting said sequentially identified transmission packets from the sending system to the at least one receiving system at the selected transmission rate;

waiting for a negative acknowledgment to be received from the at least one receiving system requesting retransmission of at least one transmission packet; and

upon receipt of said negative acknowledgement, determining if the requested at least one transmission packet has been transmitted within a designated period of time, and if so, then ignoring said negative acknowledgment, otherwise retransmitting the requested at least one transmission packet.

8. A method for transmitting a message as recited in claim 7 wherein the defined method that selects the transmission rate selects a transmission rate such that:

when the measure of the packet loss rate indicates steadily degrading network conditions, the defined method steadily adjusts the transmission rate downward until either the minimum value is reached or until network conditions improve;

when the measure of the packet loss rate indicates steadily improving network conditions, the defined method steadily adjusts the transmission rate upward until either the maximum value is reached or until network conditions degrade;

when the measure of the packet loss rate indicates either a short term improvement or degradation of network conditions, the defined method leaves the transmission rate relatively unchanged;

when the measure of the packet loss rate indicates a prolonged condition where the packet loss rate is above the desired maximum packet loss rate, the defined method adjusts the transmission rate downward until the minimum value is reached; and

when the measure of the packet loss rate indicates a prolonged condition where the packet loss rate is below the desired maximum packet loss rate, the defined method adjusts the transmission rate upward until the maximum value is reached.

9. A method for transmitting a message as recited in claim 7 wherein the transmission rate is selected by performing at least the steps of:

measuring a quantity indicative of the current packet loss rate in the network;

subtracting the quantity from a second quantity indicative of the desired packet loss rate and comparing the resultant value to a threshold value and if the resultant value is below the threshold, then setting a difference parameter to zero, otherwise setting the difference parameter to the resultant value;

setting a rate change parameter equal to a base rate change value if the difference parameter is zero, otherwise setting the rate change parameter equal to the negative of the base rate change value multiplied by the difference parameter;

calculating a raw transmission rate for a current iteration of the method equal to the sum of the rate change parameter and a weighted transmission rate calculated on a previous iteration of the method;

selecting, as the transmission rate, a weighted sum of the raw transmission rate for the current iteration of the method and a raw transmission rate on the previous iteration of the method.

10. A method for transmitting a message as recited in claim 9 wherein the quantity indicative of the packet loss rate is a measurement of the number of requests for packet retransmission that are received.

11. In a network comprising a sending system networked together with at least one receiving system, a method for efficiently and reliably transmitting a data message from the sending system to the at least one receiving system in a manner that minimizes network traffic while maintaining high reliability, the method comprising the steps of:

dividing the message to be sent into a plurality of data blocks and placing each data block into a sequentially identified transmission packet;

selecting a transmission rate to be used in transmitting said plurality of data blocks, said transmission rate being selected between a minimum and maximum value by performing at least the steps of;

measuring a quantity indicative of the current packet loss rate in the network;

subtracting the quantity from a second quantity indicative of the desired packet loss rate and comparing the resultant value to a threshold value and if the resultant value is below the threshold, then setting a difference parameter to zero, otherwise setting the difference parameter to the resultant value;

setting a rate change parameter equal to a base rate change value if the difference parameter is zero, otherwise setting the rate change parameter equal to the negative of the base rate change value multiplied by the difference parameter;

calculating a raw transmission rate for a current iteration of the method equal to the sum of the rate change parameter and a weighted transmission rate calculated on a previous iteration of the method;

selecting, as the transmission rate, a weighted sum of the raw transmission rate for the current iteration of the method and a raw transmission rate on the previous iteration of the method; and

transmitting said sequentially identified transmission packets from the sending system to the at least one receiving system at the selected transmission rate.

12. A computer readable medium having computer executable instructions carried thereon for use in a network comprising a sending system networked together with at least one receiving system, where messages are sent from said sending system to at least one receiving system using transmission packets designed to carry a designated quantity of data among a plurality of systems connected together in a network configuration, the computer executable instructions comprising:

means for dividing a message into a plurality of individual transmission packets and for adding additional transmission packets if the message fills less than a minimum number of individual transmission packets;

means for selecting a transmission rate between a minimum and maximum value according to a defined method which uses a measure of the packet loss rate in the network to adjust the transmission rate so that the packets may be transmitted as quickly as possible while minimizing the effect of transmitting the packets on the packet loss rate of the network;

means for sending the message comprised of a guaranteed minimum number of individual transmission packets at the selected transmission rate;

means for receiving requests for packet retransmission and for retransmitting the requested packets; and

means for suppressing packet retransmission if a request for retransmission is received within a designated time after a given packet has been transmitted.

13. A computer readable medium as recited in claim 12 further comprising means for receiving acknowledgments from the receiving systems.

14. A computer readable medium as recited in claim 12 further comprising means for tracking receipt of messages by intended recipient so that receipt of individual packets by a given intended recipient can be confirmed.

15. A computer readable medium as recited in claim 12 further comprising means for identifying recipients which have not acknowledged receipt of packets.

16. A computer readable medium as recited in claim 12 further comprising means for retransmitting packets that have already been sent.

17. A computer readable medium as recited in claim 12 wherein the means for selecting a transmission rate further comprises means for executing a method to select the transmission rate, said method comprising the steps of:

measuring a quantity indicative of the current packet loss rate in the network;

subtracting the quantity from a second quantity indicative of the desired packet loss rate and comparing the resultant value to a threshold value and if the resultant value is below the threshold, then setting a difference parameter to zero, otherwise setting the difference parameter to the resultant value;

setting a rate change parameter equal to a base rate change value if the difference parameter is zero, otherwise setting the rate change parameter equal to the negative of the base rate change value multiplied by the difference parameter;

calculating a raw transmission rate for a current iteration of the method equal to the sum of the rate change parameter and a weighted transmission rate calculated on a previous iteration of the method; and

selecting, as the transmission rate, a weighted sum of the raw transmission rate for the current iteration of the method and a raw transmission rate on the previous iteration of the method.

18. A computer readable medium having computer executable instructions carried thereon for use in a network comprising a sending system networked together with at least one receiving system, where messages are sent from said sending system to at least one receiving system using transmission packets designed to carry a designated quantity of data among a plurality of systems connected together in a network configuration, the computer executable instructions comprising:

a sender comprising;

a first software component adapted to divide a message into a plurality of individual transmission packets;

a second software component adapted to select a transmission rate by performing at least the steps of;

measuring a quantity indicative of the current packet loss rate in the network;

subtracting the quantity from a second quantity indicative of the desired packet loss rate and comparing the resultant value to a threshold value and if the resultant value is below the threshold, then setting a difference parameter to zero, otherwise setting the difference parameter to the resultant value;

setting a rate change parameter equal to a base rate change value if the difference parameter is zero, otherwise setting the rate change parameter equal to the negative of the base rate change value multiplied by the difference parameter;

calculating a raw transmission rate for a current iteration of the method equal to the sum of the rate change parameter and a weighted transmission rate calculated on a previous iteration of the method; and

selecting, as the transmission rate, a weighted sum of the raw transmission rate for the current iteration of the method and a raw transmission rate on the previous iteration of the method; and

at least one other software component adapted to transmit the individual transmission packets on the network at the selected transmission rate; and

a NAK receiver adapted to receive NAKs and further adapted to retransmit the packets requested in the NAKs.

19. A computer readable medium as recited in claim 18 further comprising a retransmission suppressor adapted to check a timer associated with a previously retransmitted packet when a NAK for the previously retransmitted packet is received and if the timer has not yet expired, then ignoring the NAK.

20. A computer readable medium as recited in claim 18 further comprising a transmit list adapted to track receipt of messages by intended recipient so that receipt of individual packets by intended recipient can be confirmed.

21. A computer readable medium as recited in claim 20 further comprising an ACK receiver adapted to receive acknowledgments from intended recipients and further adapted to update the transmit list in order to track receipt of individual packets.

22. A computer readable medium as recited in claim 20 further comprising a send verifier having access to said transmit list in order to determine which recipients have not acknowledged receipt of packets, said send verifier being adapted to retransmit packets that have not been acknowledged.

23. A computer readable medium as recited in claim 20 further comprising a memory return having access to said transmit list in order scan the transmit list for packets that have already been acknowledged by all intended recipients, said memory return further being adapted to free memory occupied by said transmit list that is no longer needed.