EP0969623A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Method and computer program product for efficiently and reliably sending small data messages from a sending system to a large number of receiving systems
Assignee: Microsoft Corp
•
Filing: 1999-06-28
•
Granted: —
•
Expires: 2019-06-28
Abstract
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.
Inventors
- 👤 Keith S. Hamilton
- 👤 Robert Steven Meizlik
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-11-02 09:55
CPC Classifications
H; H04; H04L; H04L1/00; H04L1/0001; H04L1/0015; H04L1/0002; H04L1/12; H04L1/16; H04L1/1607; H04L1/1685; H04L1/18; H04L1/1829; H04L1/1848; H04L1/1854; H04L1/1867; H04L1/188; H04L1/1883; H04L1/1887; H04L2001/0092; H04L2001/0093
Claims Analysis
Total Claims: 24
Claim 1
Independent Claim
227 words
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 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 retransmitted.
Claim 2
Dependent Claim
51 words
A method for transmitting a message as recited in claim 1 further
comprising the step of 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
Claim 3
Dependent Claim
55 words
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.
Claim 4
Dependent Claim
61 words
A method for transmitting a message as recited in claim 3 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.
Claim 5
Dependent Claim
34 words
A method for transmitting a message as recited in claim 4 wherein the
quantity indicative of the packet loss rate is a measurement of the number of requests
for packet retransmission that are received.
Claim 6
Dependent Claim
201 words
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.
Claim 7
Dependent Claim
190 words
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.
Claim 8
Dependent Claim
266 words
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.
Claim 9
Dependent Claim
201 words
A method for transmitting a message as recited in claim 8 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.
Claim 10
Dependent Claim
190 words
A method for transmitting a message as recited in claim 8 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.
Claim 11
Dependent Claim
34 words
A method for transmitting a message as recited in claim 10 wherein the
quantity indicative of the packet loss rate is a measurement of the number of requests
for packet retransmission that are received.
Claim 12
Dependent Claim
297 words
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.
Claim 13
Dependent Claim
217 words
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.
Claim 14
Dependent Claim
19 words
A computer readable medium as recited in claim 13 further comprising
means for receiving acknowledgments from the receiving systems.
Claim 15
Dependent Claim
34 words
A computer readable medium as recited in claim 13 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.
Claim 16
Dependent Claim
22 words
A computer readable medium as recited in claim 13 further comprising
means for identifying recipients which have not acknowledged receipt of packets.
Claim 17
Dependent Claim
20 words
A computer readable medium as recited in claim 13 further comprising
means for retransmitting packets that have already been sent.
Claim 18
Dependent Claim
202 words
A computer readable medium as recited in claim 13 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.
Claim 19
Dependent Claim
312 words
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 selling a difference parameter to zero,
otherwise setting the difference parameter to the resultant
value; selling a rate change parameter equal to a base rate
change value if the difference parameter is zero, otherwise
selling 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.
Claim 20
Dependent Claim
47 words
A computer readable medium as recited in claim 19 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.
Claim 21
Dependent Claim
35 words
A computer readable medium as recited in claim 19 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.
Claim 22
Dependent Claim
37 words
A computer readable medium as recited in claim 21 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.
Claim 23
Dependent Claim
45 words
A computer readable medium as recited in claim 21 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.
Claim 24
Dependent Claim
56 words
A computer readable medium as recited in claim 21 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.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.