Network coding approach to rapid information dissemination

• US 8,102,837 B2
• Filed: 12/30/2004
• Issued: 01/24/2012
• Est. Priority Date: 12/30/2004
• Status: Active Grant

• Current Assignee: Massachusetts Institute of Technology
• Original Assignee: Massachusetts Institute of Technology
• Inventors: Deb, Supratim, Medard, Muriel
• Primary Examiner(s): Tsang, Fan
• Assistant Examiner(s): SHARIFZADEH, IBRAHAM KALEL
• Application Number:
  US11/026,483
• Publication Number:
  US 20060146791A1
• Time in Patent Office: 2,581 Days
• Field of Search: 370/352, 709223-240
• 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, wherein said random code vector is calculated according to the equation

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

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

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

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

6. The method of claim 5 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.

7. The method of claim 6 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.

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

9. A computer implemented method of retrieving information comprising:

collecting, by a computer, code vectors from at least one peer, wherein said code vectors were calculated according to the equation

10. The method of claim 9 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.

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

12. A non-transitory 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, wherein said random code vector is calculated according to the equation

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

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

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

16. The computer readable medium of claim 12 further comprising instructions for retrieving the information.

17. The computer readable medium of claim 16 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.

18. The computer readable medium of claim 17 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.

19. The computer readable medium of claim 18 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.

20. A non-transitory computer readable medium of retrieving information comprising:

instructions for collecting code vectors from at least one peer, wherein said code vector was calculated according to the equation

21. The computer readable medium of claim 20 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.

22. 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.