Network coding approach to rapid information dissemination

• US 20060146791A1
• Filed: 12/30/2004
• Published: 07/06/2006
• Est. Priority Date: 12/30/2004
• Status: Active Grant

• Current Assignee: Massachusetts Institute of Technology
• Original Assignee: Massachusetts Institute of Technology
• Inventors: Medard, Muriel, Deb, Supratim
• Granted Patent: US 8,102,837 B2
• Time in Patent Office: Days
• US Class Current: 370/352
• CPC Class Codes: H04L 1/0041 Arrangements at the transmitter end

Abstract

A method, apparatus and computer program product for providing rapid information dissemination using network coding is presented. A coded message including a payload and a code vector, is transmitted from a first node of the network to a second node of the network. The information thus stored can also be retrieved by collecting code vectors from at least one node and viewing the collected code vectors as a matrix. A determination is made regarding whether a dimension of the matrix is equal to a predefined number. When the dimension of the matrix equals the predefined number, the information is retrieved using the collection of code vectors in the matrix.

Claims

1. A method using network coding to provide rapid information dissemination, the method comprising:

transmitting, from a first node of the network to a second node of the network, a coded message including a payload; and

transmitting, from the first node to the second node of the network, a random code vector with said message.

2. The method of claim 1 wherein said payload of said message is calculated in accordance with the equation

$e=\sum _{}^{}$

fl = 1 

S 1 

⁢

β

i ⁢

f l

wherein β

is the coding vector.

3. The method of claim 1 wherein said random coding vector is calculated according to the equation

$\mathrm{Pr}$

( β

l = β

) = 1 q ⁢

∀

β

∈

F q

4. The method of claim 1 wherein said message is constructed by appending the code vector to the payload

5. The method of claim 1 wherein said transmitting is done using a gossip-based protocol.

6. The method of claim 1 further comprising retrieving the information.

7. The method of claim 6 wherein said retrieving the information comprises:

collecting code vectors from at least one peer;

viewing collected code vectors as a matrix;

determining whether a dimension of the matrix is equal to a predefined number, and when the dimension of the matrix does not equal the predefined number then repeating said collecting, said viewing and said determining; and

when the dimension of the matrix equals the predefined number, then retrieving said information using the collection of code vectors in the matrix.

8. The method of claim 7 wherein said viewing collected code vectors as a matrix comprises viewing said collected code vectors as a n×

k matrix wherein n is the number of coded messages and k is the total number of messages.

9. The method of claim 8 wherein determining comprises determining when the dimension of the matrix is equal to the number of messages to be disseminated.

10. A method of retrieving information comprising:

collecting code vectors from at least one peer;

viewing collected code vectors as a matrix;

determining whether a dimension of the matrix is equal to a predefined number, and when the dimension of the matrix does not equal the predefined number then repeating said collecting, said viewing and said determining; and

when the dimension of the matrix equals the predefined number, then retrieving said information using the collection of code vectors in the matrix.

11. The method of claim 10 wherein said viewing collected code vectors as a matrix comprises viewing said collected code vectors as a n×

k matrix wherein n is the number of coded messages and k is the total number of messages.

12. The method of claim 10 wherein determining comprises determining when the dimension of the matrix is equal to the number of messages to be disseminated.

13. A computer readable medium having computer readable code thereon for providing rapid information dissemination using network coding, the medium comprising:

instructions for transmitting, from a first node of the network to a second node of the network, a coded message including a payload; and

instructions for transmitting, from the first node to the second node of the network, a random code vector with said message.

14. The computer readable medium of claim 13 including instructions for calculating said payload of said message in accordance with the equation

$e=\sum _{}^{}$

fl = 1 

S 1 

⁢

β

i ⁢

f l

wherein β

is the coding vector.

15. The computer readable medium of claim 13 including instructions for calculating said random coding vector according to the equation

$\mathrm{Pr}$

( β

l = β

) = 1 q ⁢

∀

β

∈

F q

16. The computer readable medium of claim 13 including instructions for constructing said message by appending the code vector to the payload.

17. The computer readable medium of claim 13 wherein said instructions for transmitting comprises instructions for transmitting using a gossip-based protocol.

18. The computer readable medium of claim 13 further comprising instructions for retrieving the information.

19. The computer readable medium of claim 18 wherein said retrieving the information comprises:

instructions for collecting code vectors from at least one peer;

instructions for viewing collected code vectors as a matrix;

instructions for determining whether a dimension of the matrix is equal to a predefined number, and when the dimension of the matrix does not equal the predefined number then repeating said collecting, said viewing and said determining; and

instructions for when the dimension of the matrix equals the predefined number, then retrieving said information using the collection of code vectors in the matrix.

20. The computer readable medium of claim 19 wherein said instructions for viewing collected code vectors as a matrix comprises instructions for viewing said collected code vectors as a n×

k matrix wherein n is the number of coded messages and k is the total number of messages.

21. The computer readable medium of claim 20 wherein said instructions for determining comprises instructions for determining when the dimension of the matrix is equal to the number of messages to be disseminated.

22. A computer readable medium of retrieving information comprising:

instructions for collecting code vectors from at least one peer;

instructions for viewing collected code vectors as a matrix;

instructions for determining whether a dimension of the matrix is equal to a predefined number, and when the dimension of the matrix does not equal the predefined number then repeating said collecting, said viewing and said determining; and

instructions for when the dimension of the matrix equals the predefined number, then retrieving said information using the collection of code vectors in the matrix.

23. The computer readable medium of claim 22 wherein said instructions for viewing collected code vectors as a matrix comprises instructions for viewing said collected code vectors as a n×

k matrix wherein n is the number of coded messages and k is the total number of messages.

24. The computer readable medium of claim 22 wherein said instructions for determining comprises instructions for determining when the dimension of the matrix is equal to the number of messages to be disseminated.