US6278716B1 — Multicast with proactive forward error correction

Claim 1

Independent Claim 166 words

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 ≧1 data packets, the transmission of the first block comprising an initial transmission of the k 1 data packets and h 1 ≧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 1 data packets; and a second block comprising k2≧1 data packets, the transmission of the second block comprising an initial transmission of the k 2 data packets and h 2 ≧0 repair packets, wherein any of the data packets and the repair packets of the second block provide sufficient information to recover the k 2 data packets of the second block and either or both k 2 and h 2 differ from k 1 and h 1 , respectively.

Claim 2

Independent Claim 166 words

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 ≧1 data packets, the transmission of the first block comprising an initial transmission of the k 1 data packets and h 1 ≧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 1 data packets; and a second block comprising k2≧1 data packets, the transmission of the second block comprising an initial transmission of the k 2 data packets and h 2 ≧0 repair packets, wherein any of the data packets and the repair packets of the second block provide sufficient information to recover the k 2 data packets of the second block and either or both k 2 and h 2 differ from k 1 and h 1 , respectively.

Claim 3

Dependent Claim 28 words

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

Claim 4

Dependent Claim 33 words

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.

Claim 5

Dependent Claim 40 words

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.

Claim 6

Dependent Claim 75 words

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.

Claim 7

Dependent Claim 36 words

The method of claim 5 , wherein the number h 2 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.

Claim 8

Dependent Claim 16 words

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

Claim 9

Dependent Claim 248 words

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 =ω i−1 −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 ω′=ω i−1 x (1−α)+B W α, and where α is decay constant 0<α≦1; and setting ρ i =ω i .

Claim 10

Dependent Claim 20 words

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

Claim 11

Independent Claim 111 words

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.

Claim 12

Independent Claim 111 words

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.

Claim 13

Dependent Claim 30 words

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.

Claim 14

Dependent Claim 24 words

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

Claim 15

Dependent Claim 32 words

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.

Claim 16

Independent Claim 101 words

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.

Claim 17

Independent Claim 101 words

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.

Claim 18

Dependent Claim 92 words

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.

Claim 19

Dependent Claim 30 words

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.

Claim 20

Dependent Claim 36 words

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.

Claim 21

Dependent Claim 20 words

The method of claim 15 , wherein the estimate of S−U is the largest sequence number received by the receiver.

Claim 22

Dependent Claim 41 words

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.

Claim 23

Dependent Claim 41 words

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.

Claim 24

Dependent Claim 24 words

The method of claim 14 , further comprising: sending to the sender a repair request requesting the identified repair packets by their sequence numbers.

Claim 25

Dependent Claim 30 words

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.

Claim 26

Dependent Claim 22 words

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

Claim 27

Dependent Claim 39 words

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.

Claim 28

Dependent Claim 27 words

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.

Claim 29

Dependent Claim 46 words

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.

Claim 30

Dependent Claim 67 words

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.

Claim 31

Dependent Claim 22 words

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

Claim 32

Dependent Claim 24 words

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

Claim 33

Dependent Claim 32 words

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.

Claim 34

Dependent Claim 37 words

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.

Claim 35

Dependent Claim 29 words

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.

Claim 36

Dependent Claim 82 words

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.

Claim 37

Dependent Claim 23 words

The method of claim 33 , wherein if D(l, k)≧P, then no further attempt is made by the receiver to obtain the block.

Claim 38

Dependent Claim 268 words

The method of claim 31 , wherein m satisfies the relationship D ( m, n ) =D ( m, n, L ) +D ( m, n, R ), where R is the state of receiving a packet, L is the state of losing a packet, the probability of a receiver in state R remaining in state R is a, the probability of losing a packet and moving to state L is 1−α, the probability of a receiver in state L losing another packet and remaining in state L is β, and the probability of receiving a packet and moving to state R is 1−β, where D(m, n, L) is the probability of sending m packets, receiving at least n packets, and ending up in state L, and D(m, n, R) is the probability of sending m packets, receiving at least n packets, and ending up in state R, D ( m, n, L ) =D ( m− 1 , n, L ) β+D ( m− 1 , n, R )(1−α), D ( m, n, R ) =D ( m− 1 , n− 1 , L )(1−β) +D ( m− 1 , n, R )α, D ( n, n, L )=0, D ( n, n, R ) =P α α n +p β (1−β)α n−1 , D ( n , 0 , L ) =p α (1−α)β n−1 +p β β n , and D ( n, 0, R )=0 where n>0, p α is the probability of the system initially residing in state R, and p β is the probability of the system initially residing in state L.

Claim 39

Dependent Claim 38 words

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.

Claim 40

Dependent Claim 60 words

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 = n m   ( m i )  ( 1 - p ) i  p ( m - i ) .

Claim 41

Dependent Claim 136 words

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 T final =T− ( r+p n τ+t ( b, k )), where T is the time of an earliest deadline for any data packet in the block that has not yet been received, r is an estimated upper bound on round trip time to and from the sender, k is the blocksize, p n is the number of additional packets that the receiver is requesting that the sender transmit, τ is the rate at which the sender can inject packets into the network, and t(b, k) is the time required by the receiver to decode and recover b packets from a blocksize of k.

Claim 42

Dependent Claim 190 words

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 ≧1 data packets, the transmission of the first block comprising an initial transmission of the k 1 data packets and h 1 ≧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 1 data packets; and a second block comprising k 2 ≧1 data packets, the transmission of the second block comprising an initial transmission of the k 2 data packets and h 2 ≧0 repair packets, wherein any of the data packets and the repair packets of the second block provide sufficient information to recover the k 2 data packets of the second block and either or both k 2 and h 2 differ from k 1 and h 1 , respectively.

Claim 43

Dependent Claim 190 words

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 ≧1 data packets, the transmission of the first block comprising an initial transmission of the k 1 data packets and h 1 ≧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 1 data packets; and a second block comprising k 2 ≧1 data packets, the transmission of the second block comprising an initial transmission of the k 2 data packets and h 2 ≧0 repair packets, wherein any of the data packets and the repair packets of the second block provide sufficient information to recover the k 2 data packets of the second block and either or both k 2 and h 2 differ from k 1 and h 1 , respectively.

Claim 44

Dependent Claim 116 words

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.

Claim 45

Dependent Claim 116 words

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.

Claim 46

Independent Claim 234 words

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 ≧1 data packets, the transmission of the first block comprising an initial transmission of the k 2 data packets and h 1 ≧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 1 data packets; and a second block comprising k 2 ≧1 data packets, the transmission of the second block comprising an initial transmission of the k 2 data packets and h 2 ≧0 repair packets, wherein any of the data packets and the repair packets of the second block provide sufficient information to recover the k 2 data packets of the second block and either or both k 2 and h 2 differ from k 1 and h 1 , 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.

Claim 47

Independent Claim 234 words

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 ≧1 data packets, the transmission of the first block comprising an initial transmission of the k 2 data packets and h 1 ≧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 1 data packets; and a second block comprising k 2 ≧1 data packets, the transmission of the second block comprising an initial transmission of the k 2 data packets and h 2 ≧0 repair packets, wherein any of the data packets and the repair packets of the second block provide sufficient information to recover the k 2 data packets of the second block and either or both k 2 and h 2 differ from k 1 and h 1 , 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.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	2004-08-20	2005-02-19	2005-08-21	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2008-08-20	2009-02-19	2009-08-21	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2012-08-20	2013-02-19	2013-08-21	$7700.00	Window Closed / Lapsed

Multicast with proactive forward error correction

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag