Method for coding-based, delay-efficient data transmission
A method, apparatus and computer program product for -based, delay-efficient data transmission for broadcasting a single file is presented. A file (f) comprised of K packets to be broadcast to a plurality of receivers is determined. A plurality of packets (P k ) of the file are selected for transmission during a timeslot (t). Next, a linear combination of the selected packets (P[t]) are produced, the linear combination of packets are selected at random within the file. The linear combination of selected packets is then transmitted to a plurality of receivers over unreliable channels.
1. A method of coding-based, delay-efficient data transmission for broadcasting a single file, the method comprising;
determining a complete pre-existing file (f) comprised of K packets to be broadcast to a plurality of receivers;
selecting a plurality of packets (P k ) of said file for transmission during a timeslot (t);
providing a linear combination of said selected packets (P[t]), said linear combination of packets are selected at random within said file wherein said providing a linear combination of said selected packets (P[t]) is done in accordance with the formula
P
[
t
]
=
∑
k
=
1
K
a
k
[
t
]
P
k
where (P[t]) is the linear combination of said selected packets, K is the size of the file, and a k [t] is a random coefficient associated with P k , and P k is packet k of file f;
transmitting said linear combination of selected packets to a plurality of receivers over unreliable channels;
receiving, at a receiver, said linear combination of selected packets;
decoding received linear combinations of selected packets when K linear independent combinations of packets are collected at said receiver; and
wherein the mean number of packets necessary to decode the file is equal to
∑
k
=
1
K
1
(
1
-
(
1
/
q
)
k
)
where q is the field size.
2. The method of claim 1 wherein said transmitting said linear combination of selected packets to a plurality of receivers is done in accordance with the formula
Transmit
P
[
t
]
=
∑
k
=
1
K
a
k
[
t
]
P
k
,;
t
←
t
+
1
;
where (P[t]) is the linear combination of said selected packets, K is the size of the file, a k [t] and a k [t] is a random coefficient associated with P k , and P k is packet k of file f, and t is the timeslot.
3. The method of claim 1 further comprising utilizing a channel state vector C[t] and performing said transmitting said linear combination of selected packets to a plurality of receivers over a channel when the channel state vector for said channel indicates said receiver is available to receive a transmission.
4. The method of claim 1 wherein said file is selected from the group consisting of a group of files, a single file, streaming media and a collection of data.
5. The method of claim 1 wherein said linear combinations of selected packets are received and are decoded when K linearly independent combinations of packets are collected.
6. A method of coding-based, delay-efficient data transmission for multiple unicast transmissions, the method comprising:
defining a set of coding classes (Class j) that partition a set of files ( ) into J subsets;
defining a set of complete, pre-existing files C j within Class j;
selecting a plurality of packets (P k ) of a plurality of files having a same class for transmission during a timeslot (t);
providing a linear combination of said selected packets (P[t]), said linear combination of packets are selected at random within said plurality of files having a same class, wherein said providing a linear combination of said selected packets (P[t]) is done in accordance with the formula
P
[
t
]
=
∑
f
∈
ℱ
∑
k
=
1
K
f
a
f
,
k
[
t
]
P
k
,
f
,
where (P[t]) is the linear combination of said selected packets, f is the file, is the set of files, K is the size of the file, and a k [t] is a random coefficient associated with P k , and P k is packet k of file; and
transmitting said linear combination of selected packets to a plurality of receivers;
receiving, at a receiver, said linear combination of selected packets;
decoding received linear combinations of selected packets when K linear independent combinations of packets are collected at said receiver; and
wherein the mean number of packets necessary to decode the file is equal to
∑
k
=
1
K
1
(
1
-
(
1
q
)
k
)
wherein q is the field size.
7. The method of claim 6 wherein said transmitting said linear combination of selected packets to a plurality of receivers is done in accordance with the formula
Transmit
P
[
t
]
=
∑
k
=
1
K
a
k
[
t
]
P
k
,;
t
←
t
+
1
;
where (P[t]) is the linear combination of said selected packets, K is the size of the file, a k [t] and a k [t] is a random coefficient associated with P k , and P k is packet k of file f, and t is the timeslot.
8. The method of claim 7 wherein when all receivers are to receive different files, said coding is performed within files.
9. The method of claim 6 further comprising utilizing a channel state vector C[t] and performing said transmitting said linear combination of selected packets to a plurality of receivers over a channel when the channel state vector for said channel indicates said receiver is available to receive a transmission.
10. The method of claim 9 wherein said performing said transmitting includes determining the next packet to be transmitted to a particular receiver and a number of packets yet to be transmitted to a particular receiver.
11. The method of claim 10 wherein said transmitting is done in accordance with the formula
Transmit
P
i
*
,
Q
i
*
;
Q
i
*
←
max
(
0
,
Q
i
*
-
1
)
;
where Q i is a pointer to the index of the next packet to be transmitted to receiver-i, and is the number of packets to be transmitted to receiver-i, and l is
∈
{
1
,
…
,
N
}
.
12. The method of claim 6 wherein said file is selected from the group consisting of a group of files, a single file, streaming media and a collection of data.
13. The method of claim 6 wherein when all receivers are to receive all the files, said coding is performed across the files.
14. The method of claim 6 wherein said linear combinations of selected packets are received and are decoded when K linearly independent combinations of packets are collected.