Multicast with proactive forward error correction

• US 6,278,716 B1
• Filed: 03/23/1998
• Issued: 08/21/2001
• Est. Priority Date: 03/23/1998
• Status: Expired due to Term

• Current Assignee: University Of Massachusetts
• Original Assignee: University Of Massachusetts
• Inventors: Towsley, Donald F., Rubenstein, Daniel S., Kurose, James F.
• Primary Examiner(s): TON, DANG T
• Application Number:
  US09/046,944
• Time in Patent Office: 1,247 Days
• Field of Search: 370/390, 370/394, 370/428, 370/473, 370/474, 370/432, 370/389, 370/229, 370/401, 370/351, 370/352, 714/748, 714/749, 714/756
• US Class Current: 370/432
• CPC Class Codes: H04L 1/1819 with retransmission of additional or different redundancy
• CPC Class Codes: H04L 2001/0093 Point-to-multipoint

Abstract

Apparatus and methods for multicasting blocks of data to a plurality of receivers, the blocks including a first block and a second block, the first block comprising k₁≧1 data packets, the transmission of the first block comprising an initial transmission of the k₁ data packets and h₁≧repair packets and one or more subsequent transmissions of additional repair packets in response to repair requests, wherein any k₁ of the data packets and repair packets provide sufficient information to recover the k₁ data packets; and multicasting a second block comprising k₂≧1 data packets, the transmission of the second block comprising an initial transmission of the k₂ data packets and h₂≧repair packets, wherein any k₂ of the data packets and the repair packets of the second block provide sufficient information to recover the k₂ data packets of the second block and either or both k₂ and h₂ differ from k₁ and h₁, respectively. The invention provides multicast data transmission with adaptive proactive forward error correction (FEC) in combination with automatic repair requesting (ARQ), and reduces response feedback implosion in multicast over digital packet networks.

Claims

1. A method for transmitting data, comprising:

multicasting blocks of data to a plurality of receivers, the blocks including a first block and a second block, the first block comprising k₁≧

1 data packets, the transmission of the first block comprising an initial transmission of the k₁ data packets and h₁≧

0 repair packets and one or more subsequent transmissions of additional repair packets in response to repair requests, wherein any of the data packets and repair packets provide sufficient information to recover the k₁ data packets; and

a second block comprising k2≧

1 data packets, the transmission of the second block comprising an initial transmission of the k₂ data packets and h₂≧

0 repair packets, wherein any of the data packets and the repair packets of the second block provide sufficient information to recover the k₂ data packets of the second block and either or both k₂ and h₂ differ from k₁ and h₁, respectively.

2. The method of claim 1, wherein the number h₂ of repair packets is calculated based on a history of repair requests received for previously transmitted blocks.

3. The method of claim 1, wherein each data packer and repair packet of each of the blocks carries information identifying the block and an ordinal position of the packet within the block.

4. The method of claim 3, wherein each data packet and repair packet of each block i carries information communicating the number h_i of repair packets transmitted in the transmission of the first block and of the second block.

5. The method of claim 4, wherein each data packet and repair packet of each block carries a block number i, a sequence number defining the ordinal position of the packet among the data packets and repair packets in the block, a blocksize k_i denoting the number of data packets in the block, and a proactivity factor ρ

from which the initial number h_i of repair packets in the block can be calculated.

6. The method of claim 5, wherein the number h₂ of repair packets in the initial transmission of the second block is calculated based on a history of repair requests received for previously transmitted blocks.

7. The method of claim 5, wherein the repair packets are encoded using a Reed-Solomon encoding.

8. The method of claim 2, wherein the initial number h_i of repair packets for block i is calculated from a proactivity factor ρ

_i applied to the blocksize k_i, the method of calculating the factor ρ

_i comprising;

for a window of W blocks preceding the current block i, determining if any repair requests were received;

for any block x in the window in which no repair requests were received, setting ω

_x=ρ

_x−

1;

for any block x in the window in which a repair request was received, setting ω

_x=ρ

_x+(log_z N_x)/k, where N_x is the number of repair requests received for block x, z represents the logarithm base, and setting M_x to the greatest repair packet sequence number requested for block x;

setting A_W to the largest ω

_x obtained for all blocks in the window, and setting B_W to the average of M_x for each block x having at least one repair request;

if no repair requests were received for any of the preceding W blocks, setting ω

_i=ω

<sub>i−

1</sub>−

Dk/2, where D is the period of the data transmission rate;

if a repair request was received for at least one block in the window, calculating ω

_i to have a value ω

_i=ω

′

H(1−

α

)+A_Wα

, where ω

′

=ω

<sub>i−

1</sub>x(1−

α

)+B_Wα

, and where α

is decay constant 0<

α

≦

1; and

setting ρ

_i=ω

_i.

9. The method of claim 8, wherein W is 8, the logarithm base z is 10, and α

is 0.25.

10. A method for a receiver to receive a multicast transmission of blocks of data packets from a multicasting sender, the method comprising:

insuring to a probability ρ

that the receiver will receive enough data packets and repair packets to recover the data packets of a block no later than a deadline time by estimating the end-to-end loss of packets from the sender to the receiver; and

initiating proactive forward error correction with the sender to compensate for the estimated loss of packets and to meet the deadline time with a probability not less than ρ

, the proactive forward error correction causing the sender to send previously-unsent repair packets for the block.

11. The method of claim 10, wherein the loss of packets is estimated using a loss model of the end-to-end transmission losses of packets from the sender to the receiver.

12. The method of claim 10, wherein the receiver is one of a plurality of receivers in a multicast group receiving the multicast transmission.

13. The method of claim 10, wherein the receiver insures the probability ρ

is met regardless of any deadlines or probabilities of any other receivers of the multicast stream of data packets.

14. A method for a receiver in a multicast receiver group to receive data, comprising:

receiving from a multicasting sender the packets of a block of packets comprising k≧

1 data packets and zero or more repair packets, wherein any of the data packets and repair packets provide sufficient information to recover the k data packets and wherein each of the packets has a sequential sequence number denoting the ordinal position of the packet in the block;

calculating a number of repair packets desired by the receiver; and

calculating the sequence number of the last of any repair packets desired by the receiver.

15. The method of claim 14, wherein calculating the sequence number of the last of any repair packets desired by the receiver comprises:

calculating an estimate of S−

U, where S is the maximum sequence number sent by the sender and U is the number of data and repair packets that are underway to the receiver that will be received; and

calculating the sequence number of the last of any repair packets desired by the receiver to satisfy the relationship;

sequence number=S−

U+d, where d is the number of packets desired by the receiver.

16. The method of claim 15, wherein d=n, n being the difference between k, the number of packets the receiver needs, and the number of packets the receiver has received.

17. The method of claim 15, wherein d=m, m being a number of packets greater than the difference between k, the number of packets the receiver needs, and the number of packets the receiver has received.

18. The method of claim 15, wherein the estimate of S−

U is the largest sequence number received by the receiver.

19. The method of claim 15, wherein the estimate of S−

U is the larger of the largest sequence number received by the receiver and the largest sequence number requested in a repair request broadcast by another receiver in the receiver group.

20. The method of claim 17, wherein the estimate of S−

U is the larger of the largest sequence number received by the receiver and the largest sequence number requested in a repair request broadcast by another receiver in the receiver group.

21. The method of claim 14, further comprising:

sending to the sender a repair request requesting the identified repair packets by their sequence numbers.

22. The method of claim 14, further comprising:

sending to the sender a repair request requesting the identified repair packets by the sequence number of the last one of them.

23. The method of claim 14, wherein the repair request is multicast to a plurality of receivers in the multicast receiver group.

24. The method of claim 14, further comprising:

receiving from the sender a block identifier for each packet of the block; and

including in the repair request the block identifier of the block to which the repair request relates.

25. The method of claim 24, further comprising:

including in the repair request the sequence number of the last repair packet being requested in the repair request.

26. The method of claim 23, further comprising:

monitoring repair requests multicast by other receivers in the multicast receiver group; and

sending a repair request to the sender requesting the identified repair packets only if the identified repair packets were not previously requested by another receiver.

27. The method of claim 14, further comprising:

examining the sequence numbers of the received packets to detect gaps in the sequence of received packets of the block;

receiving from the sender the number k+h′

of packets of the block sent so far; and

sending a repair request to the sender as soon as an absence of n>

h′

packets in the sequence of received packets is detected.

28. The method of claim 27, wherein the repair request requests a number of repair packets m that is greater than n.

29. The method of claim 28, wherein the amount by which m exceeds n is calculated from a proactivity factor received from the sender.

30. The method of claim 28, wherein the amount by which m exceeds n is calculated from a history of the number of packets requested in repair requests sent by the receiver.

31. The method of claim 28, wherein m satisfies the relationship that the probability of receiving n out of m packets, D(m, n), is greater than a probability threshold P of reliable transmission established for the receiver.

32. The method of claim 31, wherein the probability of receiving n out of m packets is greater than a last chance guarantee probability threshold established for the receiver.

33. The method of claim 31, wherein the receiver implements a policy to achieve an overall block goodput rate such that the probability that a complete block is received on or before a final deadline is the probability threshold P, the method further comprising:

computing m such that the probability D(m, n) of receiving n out of m packets is greater than or equal to (P−

D(l,k))/(1−

D(l, k)), where l is the number of packets of the block previously sent by the sender.

34. The method of claim 33, wherein if D(l, k)≧

P, then no further attempt is made by the receiver to obtain the block.

35. The method of claim 31, wherein m satisfies the relationship

36. The method of claim 31, wherein the block must be decoded prior to a deadline, and m is calculated to insure that the receiver will receive at least k packets in sufficient time to decode the block.

37. The method of claim 31, wherein packet loss is modeled as a temporally-independent loss process with a packet loss probability p and D(m, n) satisfies $D$

(m,n)=∑

i=nm

 



(mi)

(1-p)i

p(m-i).

38. The method of claim 31, further comprising:

calculating a final time T_final by which a repair request should be issued to meet a hard deadline, T_final satisfying the relationship

39. Apparatus comprising a computer-readable storage medium tangibly embodying program instructions for managing a multicasting transmission of data, the apparatus comprising instructions operable for causing a programmable processor to:

multicast blocks of data to a plurality of receivers, the blocks including a first block and a second block, the first block comprising k₁≧

1 data packets, the transmission of the first block comprising an initial transmission of the k₁ data packets and h₁≧

0 repair packets and one or more subsequent transmissions of additional repair packets in response to repair requests, wherein any of the data packets and repair packets provide sufficient information to recover the k₁ data packets; and

a second block comprising k₂≧

1 data packets, the transmission of the second block comprising an initial transmission of the k₂ data packets and h₂≧

0 repair packets, wherein any of the data packets and the repair packets of the second block provide sufficient information to recover the k₂ data packets of the second block and either or both k₂ and h₂ differ from k₁ and h₁, respectively.

40. Apparatus comprising a computer-readable storage medium tangibly embodying program instructions for managing the receipt of data, the apparatus comprising instructions operable for causing a programmable processor to:

insure to a probability p that the receiver will receive enough data packets and repair packets to recover the data packets of a block no later than a deadline time by estimating the end-to-end loss of packets from the sender to the receiver; and

initiating proactive forward error correction with the sender to compensate for the estimated loss of packets and to meet the deadline time with a probability not less than p, the proactive forward error correction causing the sender to send previously-unsent repair packets for the block.

41. A system for multicasting data from a sender to a plurality of receivers, said system comprising:

a sender apparatus comprising means for multicasting blocks of data to a plurality of receivers, the blocks including a first block and a second block, the first block comprising k₁≧

1 data packets, the transmission of the first block comprising an initial transmission of the k₂ data packets and h₁≧

0 repair packets and one or more subsequent transmissions of additional repair packets in response to repair requests, wherein any of the data packets and repair packets provide sufficient information to recover the k₁ data packets; and

a second block comprising k₂≧

1 data packets, the transmission of the second block comprising an initial transmission of the k₂ data packets and h₂≧

0 repair packets, wherein any of the data packets and the repair packets of the second block provide sufficient information to recover the k₂ data packets of the second block and either or both k₂ and h₂ differ from k₁ and h₁, respectively;

a plurality of receiver apparatuses comprising means for initiating proactive forward error correction with the sender to compensate for lost packets, proactive forward error correction causing the sender apparatus to send previously-unsent repair packets for the block; and

a network connecting the sender apparatus to said plurality of receiver apparatuses.