Granted Patent B2

US 8,005,990 · App. 12/039,820 · Granted Aug 23, 2011

Abstract

Claims (77)

1. A method of decoding code packets of file delivery protocol (FDP) and file delivery control protocol (FDCP) messages, said FDP messages comprising fields having values used to generate an indices of a data packets, said FDCP messages comprising a value of a minimum number of code packets required, said code packets formed from a linear combination of said data packets of a file fragment, said method comprising:

constructing data structures adapted to decode said code packets of said file fragment, wherein said data structures comprising at least one of code nodes, a code graph, an inverse code graph, a data packet decode array, and a data packet decode order list;

processing said FDP messages until parameters required for decoding are extracted, wherein said processing comprising:

inserting said code node into a code graph bin of said code graph corresponding to weights of said code graph bin only if an FDP message corresponding to said code node is unique; and

populating said inverse code graph with a reference to said code node; and

executing a solvability algorithm when a number of received code packets reaches said minimum number of code packets required,

wherein said solvability algorithm comprises:

traversing code graph bins having code nodes starting with a code graph bin having lowest code weight, wherein said code graph bins are arranged in an ascending order of code weights;

determining if a corresponding code packet of each code node in a list connected to each of said code graph bins can be reduced further using a data packet associated with said code packet;

proceeding to a next code node in said list only if said code packet cannot be reduced further; and

incrementing a cost value of said code packet by a cost value associated with said data packet used to reduce said code packet.

2. The method of claim 1 , wherein said code nodes are connected to each other linearly.

3. The method of claim 1 , wherein said parameters required for decoding comprises at least one of:

a minimum number of said code packets to decode successfully with high probability;

a field in said FDP message containing specific values to generate data packet indices;

a file fragment ID to determine which file fragment a received FDP packet belongs to; and

a file distribution record comprising at least one of an offset of said file fragment in a file, a size of said file fragment, and a code weight map.

4. The method of claim 3 , wherein said FDP message corresponding to said code node is determined to be unique based on any of: whether at least one of a data index, a code weight index, and a prime index have not been already received.

5. The method of claim 1 , wherein said solvability algorithm further comprises:

indexing said data packet decode array using an index of a recovered data packet; and

updating a code packet storage access information, a code node reference, a data packet cost, and a reference of a decode order in said data packet decode order list, if a data packet can be recovered from said code packet.

6. The method of claim 5 , wherein said solvability algorithm further comprises:

replacing a corresponding entry in said data packet decode array by an information of a code packet from which said data packet is recovered; and

updating said reference in said data packet decode order list to reflect a new decode order, if a cost associated with said code packet is less than a cost associated with said corresponding entry in said data packet decode array.

7. The method of claim 6 , further comprising indicating a decode failure for a file reception condition if an end of a contact window is reached and no more code packets are received.

8. The method of claim 6 , further comprising executing a code packet payload reduction algorithm to reduce a stored code packet payload using an information in said data packet decode array and said inverse code graph if said solvability algorithm is successful, wherein said code packet payload reduction algorithm comprises:

indexing said inverse code graph with the index of a first data packet to be recovered using said data packet decode order list;

obtaining a code packet payload from said inverse code graph;

fetching a next entry index from said data packet decode order list;

repeating said indexing of said inverse code graph with the index of a first data packet to be recovered using said data packet decode order list; and

repeating said indexing of said inverse code graph with the index of a first data packet to be recovered using said data packet decode order list until said data packet decode order list is completely processed and all data packets have been fully recovered.

9. A computer having stored thereon data structures adapted to decode a file delivery protocol (FDP) packet of a file fragment, said data structures comprising:

a code node to store information for retrieving a payload of said FDP packet, said code node adapted to indicate if its corresponding code packet can be further reduced;

a code graph comprising bins corresponding to a code weight, said bins comprising code nodes with said code weight;

an inverse code graph array having a number of elements equivalent to a number of data packets in said file fragment;

a data packet decode array adapted to check whether all said data packets can be decoded successfully;

a data packet decode order list to store an order in which said data packets are recovered; and

instructions for performing a solvability algorithm when a number of received code packets reaches a minimum number of code packets required, wherein said solvability algorithm comprises:

traversing code graph bins having code nodes starting with a code graph bin having lowest code weight, wherein said code graph bins are arranged in an ascending order of code weights;

determining if a corresponding code packet of each code node in a list connected to each of said code graph bins can be reduced further using a data packet associated with said code packet;

proceeding to a next code node in said list only if said code packet cannot be reduced further; and

incrementing a cost value of said code packet by a cost value associated with said data packet used to reduce said code packet.

10. The computer of claim 9 , wherein said bins are arranged in order based on said code weights.

11. The computer of claim 9 , wherein said inverse code graph is indexed by an index of said data packets.

12. The computer of claim 9 , wherein said data packet decode array is indexed by an index of a recovered data packet, if said data packet can be recovered from said code packet, wherein said data packet decode array comprises a code packet storage access information, a code node reference, a data packet cost, and a reference of a decode order in said data packet decode order list.

13. An apparatus adapted to decode code packets of file delivery protocol (FDP) and file delivery control protocol (FDCP) messages, said FDP messages comprising fields having values used to generate an indices of a data packets, said FDCP messages comprising a value of a minimum number of code packets required, said code packets formed from a linear combination of said data packets of a file fragment, said apparatus comprising:

a memory unit comprising data structures adapted to decode said code packets of said file fragment, wherein said data structures comprising at least one of code nodes, a code graph, an inverse code graph, a data packet decode array, and a data packet decode order list;

a processor configured to:

process said FDP messages until parameters required for decoding are extracted;

insert said code node into a code graph bin of said code graph corresponding to weights of said code graph bin only if an FDP message corresponding to said code node is unique;

populate said inverse code graph with a reference to said code node; and

execute a solvability algorithm when a number of received code packets reaches said minimum number of code packets required,

wherein said solvability algorithm comprises:

traversing code graph bins having code nodes starting with a code graph bin having lowest code weight, wherein said code graph bins are arranged in an ascending order of code weights;

determining if a corresponding code packet of each code node in a list connected to each of said code graph bins can be reduced further using a data packet associated with said code packet;

proceeding to a next code node in said list only if said code packet cannot be reduced further; and

incrementing a cost value of said code packet by a cost value associated with said data packet used to reduce said code packet.

14. The apparatus of claim 13 , wherein said code nodes are connected to each other linearly.

15. The apparatus of claim 13 , wherein said parameters required for decoding comprises at least one of:

a minimum number of said code packets to decode successfully with high probability;

a field in said FDP message containing specific values to generate data packet indices;

a file fragment ID to determine which file fragment a received FDP packet belongs to; and

a file distribution record comprising at least one of an offset of said file fragment in a file, a size of said file fragment, and a code weight map.

16. The apparatus of claim 15 , wherein said FDP message corresponding to said code node is determined to be unique based on any of: whether at least one of a data index, a code weight index, and a prime index have not been already received.

17. The apparatus of claim 13 , wherein said solvability algorithm further comprises:

indexing said data packet decode array using an index of a recovered data packet; and

updating a code packet storage access information, a code node reference, a data packet cost, and a reference of a decode order in said data packet decode order list, if a data packet can be recovered from said code packet.

18. The apparatus of claim 17 , wherein said solvability algorithm further comprises:

replacing a corresponding entry in said data packet decode array by an information of a code packet from which said data packet is recovered; and

updating said reference in said data packet decode order list to reflect a new decode order, if a cost associated with said code packet is less than a cost associated with said corresponding entry in said data packet decode array.

19. The apparatus of claim 18 , wherein said processor is further configured to indicate a decode failure for a file reception condition if an end of a contact window is reached and no more code packets are received.

20. The apparatus of claim 18 , wherein said processor is further configured to execute a code packet payload reduction algorithm to reduce a stored code packet payload using an information in said data packet decode array and said inverse code graph if said solvability algorithm is successful, wherein said code packet payload reduction algorithm comprises:

indexing said inverse code graph with the index of a first data packet to be recovered using said data packet decode order list;

obtaining a code packet payload from said inverse code graph;

fetching a next entry index from said data packet decode order list;

repeating said indexing of said inverse code graph with the index of a first data packet to be recovered using said data packet decode order list; and

repeating said indexing of said inverse code graph with the index of a first data packet to be recovered using said data packet decode order list until said data packet decode order list is completely processed and all data packets have been fully recovered.

Assignments (31)