Optimized transport protocol for delay-sensitive data
Transmission delays are minimized when packets are transmitted from a source computer over a network to a destination computer. The source computer measures the network's available bandwidth, forms a sequence of output packets from a sequence of data packets, and transmits the output packets over the network to the destination computer, where the transmission rate is ramped up to the measured bandwidth. In conjunction with the transmission, the source computer monitors a transmission delay indicator which it computes using acknowledgement packets it receives from the destination computer. Whenever the indicator specifies that the transmission delay is increasing, the source computer reduces the transmission rate until the indicator specifies that the delay is unchanged. The source computer dynamically decides whether each output packet will be a forward error correction packet or a single data packet, where the decision is based on minimizing the expected transmission delays.
1. A computer-implemented process for minimizing transmission delays associated with transmitting data packets generated by a local application hosted on a source computer over a data communications network to a remote application hosted on a destination computer, comprising using the source computer to perform the following process actions:
measuring the currently available bandwidth of the network;
inputting an initial sequence of the data packets generated by the local application into a transmit queue;
forming an initial sequence of output packets from the data packets in the transmit queue;
transmitting the initial sequence of output packets over the network to the remote application during a succession of transmission opportunities, wherein the rate of transmission is started at a rate that does not employ the full amount of the last-measured available bandwidth and is then ramped up to the full amount of the last-measured available bandwidth;
in conjunction with transmitting the initial sequence of output packets over the network to the remote application, monitoring a transmission delay indicator which is routinely computed using acknowledgement packets received from the destination computer and whenever the indicator specifies that the transmission delay is increasing, reducing said rate of transmission until the indicator specifies that said delay is unchanged;
remembering the last rate of transmission used to transmit the last output packet to the remote application; and
following the occurrence of one or more transmission opportunities during which no output packets are transmitted to the remote application, and upon the formation of a subsequent sequence of output packets,
transmitting the subsequent sequence of output packets over the network to the remote application, wherein the starting rate of transmission is set to be a prescribed percentage of the remembered last rate of transmission and the rate of transmission is ramped up to the measured bandwidth, and
in conjunction with transmitting the subsequent sequence of output packets over the network to the remote application, monitoring the transmission delay indicator and whenever the indicator specifies that the transmission delay is increasing, reducing said rate of transmission until the indicator specifies that said delay is unchanged.
2. The process of claim 1 , wherein the action of measuring the currently available bandwidth of the network comprises an action of transmitting a sequence of probe packets over the network to the destination computer.
3. The process of claim 1 , wherein each output packet comprises either a forward error correction packet or a single data packet based on a decision which is dynamically calculated at each transmission opportunity, said decision being based on minimizing transmission delays due to packet loss in the network.
4. A system for transmitting data packets from a local application to a remote application, comprising:
a source computer on which the local application is hosted, wherein the local application generates a sequence of data packets which are destined for the remote application;
a destination computer on which the remote application is hosted;
a data communications network which interconnects the source computer and destination computer, wherein the source computer transmits a sequence of output packets over the network to the destination computer during a succession of transmission opportunities; and
a computer program having program modules executable by the source computer, comprising,
a transmission strategy module for dynamically deciding for each output packet, whether the output packet will be a forward error correction (FEC) packet or a single data packet, said decision being based on minimizing the expected time until each data packet becomes useful to the remote application, and
an encoder module for forming each output packet from one or more data packets based on said decision, and
wherein upon each transmission opportunity the strategy module is configured to group the sequence of data packets generated by the local application based on the current transmission status of each data packet, said grouping comprising,
a first set comprising data packets which have already been formed into output packets and transmitted over the network to the destination computer, and are definitively known to have not been successfully received by the destination computer,
a second set comprising data packets which have already been formed into output packets and transmitted over the network to the destination computer, but no definitive information is known regarding whether or not these data packets have been successfully received by the destination computer, and
a third set comprising data packets which have not yet been formed into output packets and transmitted over the network to the destination computer, and
whenever there are no data packets in the third set, but there are one or more data packets in the second set at the current transmission opportunity, the strategy module is configured to instruct the encoder module to form the next output packet as an FEC packet.
5. The system of claim 4 , wherein whenever there are no data packets in the second set, but there are one or more data packets in the third set at the current transmission opportunity, the strategy module is configured to instruct the encoder module to form the next output packet from the next data packet in the third set.
6. The system of claim 4 , wherein the FEC packet comprises a linear combination of data packets in the second set, said linear combination being over a prescribed Galois field.
7. The system of claim 6 , wherein the linear combination is given by the equation
C
[
l
]
=
∑
m
=
b
[
l
]
e
[
l
]
α
l
[
m
]
Q
[
m
]
,
wherein m indexes the data packets generated by the local application, l indexes the transmission opportunities, b[l] denotes a prescribed beginning data packet used in said linear combination, e[l] denotes a prescribed ending data packet used in said linear combination, α l [m] denotes an mth coding coefficient, and Q[m] denotes the mth data packet used in said linear combination.
8. The system of claim 4 , wherein whenever there are one or more data packets in both the second and third sets at the current transmission opportunity,
the strategy module is configured to compute a first sum of expected packet transmission delays for the data packets in the second and third sets over a prescribed number N of succeeding transmission opportunities based on the assumption that the next output packet is formed as an FEC packet,
the strategy module is configured to compute a second sum of expected packet transmission delays for the data packets in the second and third sets over the prescribed number N of succeeding transmission opportunities based on the assumption that the next output packet is formed from the next data packet in the third set,
whenever the first sum is less than the second sum, the strategy module is configured to instruct the encoder module to form the next output packet as an FEC packet, and
whenever the first sum is equal to or greater than the second sum, the strategy module is configured to instruct the encoder module to form the next output packet from the next data packet in the third set.
9. The system of claim 8 , wherein the sum of expected packet transmission delays is given by the equation
T
=
∑
m
=
0
M
-
1
∑
l
=
0
N
(
τ
[
l
]
+
δ
[
l
]
-
γ
[
m
]
)
(
p
m
(
l
)
-
p
m
(
l
-
1
)
)
,
wherein m indexes the data packets generated by the local application, M denotes the combined total number of data packets in the second and third sets, l indexes the transmission opportunities, τ[l] denotes a particular point in time at which transmission opportunity l occurs, Δ[l] denotes the duration of time it takes for an output packet transmitted from the source computer at transmission opportunity l to travel over the network and reach the destination computer, γ[m] denotes a particular point in time at which the mth data packet is generated by the local application, and p m (l) denotes the probability of the destination computer being able to decode the mth data packet after transmission opportunity l.
10. The system of claim 9 , wherein whenever the output packets are being transmitted over the network at a rate which exceeds the network's currently available bandwidth, a penalty factor is added to Δ[l] in order to reduce the probability of the next output packet being formed as an FEC packet.
11. The system of claim 4 , wherein whenever there are one or more data packets in both the second and third sets at the current transmission opportunity,
the strategy module is configured to compute a first sum of expected packet transmission delays for the data packets in the second and third sets over a prescribed number N of succeeding transmission opportunities based on the assumption that the next output packet is formed as an FEC packet,
the strategy module is configured to compute a second sum of expected packet transmission delays for the data packets in the second and third sets over the prescribed number N of succeeding transmission opportunities based on the assumption that the next output packet is formed from the next data packet in the third set,
the strategy module is configured to compute a first probability of the first sum being smaller than a prescribed threshold,
the strategy module is configured to compute a second probability of the second sum being smaller than the prescribed threshold,
whenever the first probability is greater than the second probability, the strategy module is configured to instruct the encoder module to form the next output packet as an FEC packet, and
whenever the first probability is equal to or less than the second probability, the strategy module is configured to instruct the encoder module to form the next output packet from the next data packet in the third set.
12. The system of claim 4 , wherein the computer program further comprises a probe packets generator module for generating probe packets which are transmitted to the destination computer to measure the network's currently available bandwidth.
13. The system of claim 4 , wherein the computer program further comprises a decoder module for decoding the output packets received over the network from the remote application, said decoding comprising extracting the one or more data packets included within each received output packet and delivering said extracted data packets to the local application.
14. The system of claim 4 , wherein the computer program further comprises a feedback module for processing acknowledgement (ACK) packets received over the network from the destination computer, said processing comprising routinely computing a one-way packet transmission delay indicator which specifies if the one-way packet transmission delay is increasing, decreasing or unchanged.
15. The system of claim 14 , wherein each ACK packet specifies that a particular output packet was successfully received by the destination computer or is considered lost as a later output packet was successfully received by the destination computer.
16. A computer-implemented process for minimizing transmission delays associated with transmitting data packets generated by a local application hosted on a source computer over a data communications network to a remote application hosted on a destination computer, comprising using the source computer to perform the following process actions:
measuring the currently available bandwidth of the network by transmitting a sequence of probe packets over the network to the destination computer;
inputting an initial sequence of the data packets generated by the local application into a transmit queue;
forming an initial sequence of output packets from the data packets in the transmit queue, wherein each output packet comprises either a forward error correction (FEC) packet or a single data packet based on a decision which is dynamically calculated at each transmission opportunity, said decision being based on minimizing transmission delays due to packet loss in the network;
transmitting the initial sequence of output packets over the network to the remote application during a succession of transmission opportunities, wherein the rate of transmission is ramped up to the measured bandwidth;
in conjunction with transmitting the initial sequence of output packets over the network to the remote application, monitoring a transmission delay indicator which is routinely computed using acknowledgement packets received from the destination computer and whenever the indicator specifies that the transmission delay is increasing, reducing said rate of transmission until the indicator specifies that said delay is unchanged;
remembering the last rate of transmission used to transmit the last output packet to the remote application; and
following the occurrence of one or more transmission opportunities during which no output packets are transmitted to the remote application,
inputting a subsequent sequence of the data packets generated by the local application into the transmit queue,
forming a subsequent sequence of output packets from the data packets in the transmit queue, wherein each output packet comprises either an FEC packet or a single data packet based on a decision which is dynamically calculated at each transmission opportunity, said decision being based on minimizing transmission delays due to packet loss in the network,
transmitting the subsequent sequence of output packets over the network to the remote application, wherein the starting rate of transmission is set to be a prescribed percentage of the remembered last rate of transmission and the rate of transmission is ramped up to the measured bandwidth, and
in conjunction with transmitting the subsequent sequence of output packets over the network to the remote application, monitoring the transmission delay indicator and whenever the indicator specifies that the transmission delay is increasing, reducing said rate of transmission until the indicator specifies that said delay is unchanged.