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

In a network comprising a sending system networked together with at least one receiving system where data messages comprising a plurality of transmission packets are transmitted between the sending system and at least one receiving system, and where receiving systems that do not receive at least one transmission packet send negative acknowledgments to the sending system requesting retransmission of the missing transmission packets, a method for transmitting negative acknowledgments from the receiving systems to the sending system in a manner that does not create a flood of negative acknowledgments that can adversely affect the performance of the network, comprising the steps of:

• waiting, at a receiving system, for a triggering event comprising at least one of either receipt of a transmission packet or expiration of a negative acknowledgment wait timer;
• upon the triggering event of receipt of a transmission packet, then checking the received transmission packet to determine if one or more previous packets have been missed, and if one or more previous packets have been missed then performing at least the steps of:
• selecting a negative acknowledgment wait time according to a defined probability density function that is adjusted based on both the number of systems in the network and the packet loss rate so that 1) the probability of selecting a relatively shorter wait time is reduced as the number of systems in the network increases in order to maintain a relatively constant number of negative acknowledgments from the receiving systems as the number of receiving systems increases, and 2) the probability of selecting a relatively shorter wait time is increased as the packet loss rate increases in order to increase the probability that a negative acknowledgment sent early will reach the sending system;
• and
• setting a negative acknowledgment wait timer for the message associated with the transmission packet using the selected negative acknowledgment wait time;
• and
• upon the triggering event of expiration of a negative acknowledgment wait timer, then sending a negative acknowledgment to the sender system.

In a network comprising a sending system networked together with at least one receiving system where data messages comprising a plurality of transmission packets are transmitted between the sending system and at least one receiving system, and where receiving systems that do not receive at least one transmission packet send negative acknowledgments to the sending system requesting retransmission of the missing transmission packets, a method for transmitting negative acknowledgments from the receiving systems to the sending system in a manner that does not create a flood of negative acknowledgments that can adversely affect the performance of the network, comprising the steps of:

• waiting, at a receiving system, for a triggering event comprising at least one of either receipt of a transmission packet or expiration of a negative acknowledgment wait timer;
• upon the triggering event of receipt of a transmission packet, then checking the received transmission packet to determine if one or more previous packets have been missed, and if one or more previous packets have been missed then performing at least the steps of:
• selecting a negative acknowledgment wait time by performing at least the steps of:
• generating a pseudo-random number between a specified random number minimum value and a specified random number maximum value;
• multiplying the pseudo-random number by a bias curve of the form Y=X.sup.n in order to generate an unscaled wait time with a probability density function that is dependent on the bias curve;
• measuring a parameter that is indicative of the packet loss rate in the network and based on the parameter and the number of systems in the network, calculating a scale factor that is inversely proportional to the number of systems in the network and inversely proportional to the packet loss rate in the network;
• scaling said unscaled wait time to create a scaled wait time by multiplying the unscaled wait time by the scale factor;
• generating a wait time that is above a minimum wait time by adding the minimum wait time to the scaled wait time if the scaled wait time is less than a minimum wait time, otherwise setting the wait time equal to the scaled wait time;
• and
• generating a selected wait time by reducing the wait time to a maximum wait time value if the wait time is above the maximum wait time value, otherwise setting the selected wait time equal to the wait time;
• and
• setting a negative acknowledgment wait timer for the message associated with the transmission packet using the selected wait time;
• and upon the triggering event of expiration of a negative acknowledgment wait timer, then sending a negative acknowledgment to the sender system.

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 receiving individual packets of a message comprised of a guaranteed minimum number of individual transmission packets;
• means for storing received packets until the complete message can be reassembled in the proper order or until it is determined that the complete message will not be received;
• means for transmitting a request for packet retransmission if a packet in the message has not been received;
• and
• means for suppressing requests for retransmission of packets so that requests for retransmission from a plurality of receiving systems are not sent at the same time, said means for suppressing requests comprising means for selecting a wait time according to a defined probability density function, that is adjusted based on both the number of systems in the network and the packet loss rate so that 1) the probability of selecting a relatively shorter wait time is reduced as the number of systems in the network increases in order to maintain a relatively constant number of negative acknowledgments from the receiving systems as the number of receiving systems increases, and 2) the probability of selecting a relatively shorter wait time is increased as the packet loss rate increases in order to increase the probability that a negative acknowledgment sent early will reach the sending system.

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 readable medium comprising:

• a receiver adapted to receive individual packets of the message and to place them in a message receive list for the message;
• said message receive list comprising a buffer to store individual packets of the message until the complete message can be reassembled in the proper order or until it is determined that the complete message will not be received;
• a transmitter adapted to transmit a NAK requesting retransmission of at least one missed packet in the message;
• and
• a NAK suppressor comprising a NAK wait timer and a wait time selector adapted to select a NAK wait time by executing at least the steps of:
• generating a pseudo-random number between a specified random number minimum value and a specified random number maximum value;
• multiplying the pseudo-random number by a bias curve in order to generate an unscaled wait time with a probability density function that is dependent on the bias curve;
• measuring a parameter that is indicative of the packet loss rate in the network and based on the parameter and the number of systems in the network, calculating a scale factor that is inversely proportional to the number of systems in the network and inversely proportional to the packet loss rate in the network;
• scaling said unscaled wait time to create a scaled wait time by multiplying the unscaled wait time by the scale factor;
• generating a wait time that is above a minimum wait time by adding the minimum wait time to the scaled wait time if the scaled wait time is less than a minimum wait time, otherwise setting the wait time equal to the scaled wait time;
• and
• generating a NAK wait time by reducing the wait time to a maximum wait time value if the wait time is above the maximum wait time value, otherwise setting the NAK wait time equal to the wait time.