Wireless reliability architecture and methods using network coding

Abstract

Network-coding-enabled reliability architectures and techniques are provided that are capable of enhancing data transfer reliability and efficiency in next generation wireless networks. In some embodiments, the techniques and architectures utilize a flexible thread-based coding approach to implement network coding. The techniques and architectures may also, or alternatively, utilize systematic intra-session random linear network coding as a packet erasure code to support reliable data transfer.

What is claimed is:  
     
       1. A method for use in providing reliable data transfer in a wireless network, the method comprising:
 receiving coded segments from a remote wireless node, each coded segment being associated with a specific coding thread and being coded with a random linear network code (RLNC); 
 reading thread identifiers within the received coded segments and directing the coded segments to corresponding decoder worker threads based thereon, each decoder worker thread having a corresponding encoder worker thread associated with the remote wireless node, wherein the coded segments for each decoder worker thread are received in rounds, with Nm coded segments per round and a nominal delay of Tr between rounds; 
 using the coded segments within the corresponding decoder worker threads to recover original data elements; 
 receiving uncoded segments from the remote wireless node, each uncoded segment being associated with a specific coding thread, wherein the uncoded segments are received before the corresponding coded segments for each decoder worker thread; 
 reading thread identifiers within the received uncoded segments and directing the uncoded segments to corresponding decoder worker threads based thereon; 
 wherein using the coded segments within the corresponding decoder worker threads to recover original data elements includes using the coded segments as redundant information to the uncoded segments within the decoder worker threads to recover the original data elements using systematic RLNC; and 
 sending an acknowledgement (ACK) message from a decoder worker thread to a corresponding encoder worker thread associated with the remote wireless node in response to recovery of all original data elements associated with corresponding segments. 
 
     
     
       2. The method of  claim 1 , wherein:
 using the coded segments within the corresponding decoder worker threads to recover original data elements includes performing a Gauss-Jordan elimination operation for each new coded segment. 
 
     
     
       3. The method of  claim 1 , wherein using the coded segments within the corresponding decoder worker threads to recover original data elements comprises:
 recovering a corresponding coding block within a first decoder worker thread; 
 removing padding from the coding block, if any, within the first decoder worker thread; and 
 separating the coding block into original data elements. 
 
     
     
       4. The method of  claim 1 , further comprising:
 delivering the original data elements recovered by the decoder worker threads to a corresponding application. 
 
     
     
       5. A communication device comprising:
 a wireless transceiver; and 
 one or more processors configured to:
 receive coded segments from a remote wireless node, via said wireless transceiver, each coded segment being associated with a specific coding thread and being coded with a random linear network code (RLNC); 
 read thread identifiers within the received coded segments and direct the coded segments to corresponding decoder worker threads based thereon, each decoder worker thread having a corresponding encoder worker thread that is associated with the remote wireless node; and 
 use the coded segments within the corresponding decoder worker threads to recover original data elements. 
 
 
     
     
       6. The communication device of  claim 5 , wherein:
 the one or more processors are configured to:
 receive uncoded segments from the remote wireless node, each uncoded segment being associated with a specific coding thread; 
 read thread identifiers within the received uncoded segments and direct the uncoded segments to corresponding decoder worker threads based thereon; and 
 use the coded segments as redundant information to the uncoded segments to recover the original data elements within the decoder worker threads, using systematic RLNC. 
 
 
     
     
       7. The communication device of  claim 6 , wherein:
 each decoder worker thread is configured to send an acknowledgement (ACK) message to a corresponding encoder worker thread associated with the remote wireless node in response to recovery of all original data elements associated with the decoder worker thread. 
 
     
     
       8. The communication device of  claim 6 , wherein:
 each decoder worker thread is configured to perform a Gauss-Jordan elimination operation when a new coded segment is received. 
 
     
     
       9. A method for use in a wireless system, comprising:
 transmitting systematic packets to a remote node; and 
 transmitting one or more nonsystematic packets to the remote node, the non-systematic packets being encoded with a random linear network code (RLNC), the nonsystematic packets to serve as redundant information to the systematic packets for implementing systematic RLNC. 
 
     
     
       10. The method of  claim 9 , wherein:
 transmitting one or more nonsystematic packets to the remote device includes transmitting the one or more nonsystematic packets to the remote device in successive rounds, each round having N m  packets. 
 
     
     
       11. The method of  claim 10 , wherein:
 transmitting the one or more nonsystematic packets to the remote device in successive rounds includes transmitting the packets with a nominal inter-round delay of T r . 
 
     
     
       12. The method of  claim 10 , further comprising:
 before transmitting the systematic packets, generating the systematic packets, at least in part, within a plurality of encoder threads, each systematic packet including a thread identifier (TID) to identify a corresponding encoder thread; and 
 before transmitting the nonsystematic packets, generating the nonsystematic packets, at least in part, within the plurality of encoder threads, each nonsystematic packet including a thread identifier (TID) to identify a corresponding encoder thread. 
 
     
     
       13. The method of  claim 12 , wherein generating the nonsystematic packets includes:
 obtaining a coding block within a first encoder thread; 
 segmenting the coding block into a number of segments; 
 generating first random coefficients for the segments; and 
 linearly combining the segments using the first random coefficients to generate a first nonsystematic segment. 
 
     
     
       14. A method for use in a wireless system, comprising:
 obtaining a coding block; 
 segmenting the coding block into a number of equal-length uncoded segments; 
 generating one or more coded segments by applying random linear network coding (RLNC) to the number of equal-length segments; and 
 transmitting the uncoded segments and the one or more coded segments to a remote node via a wireless channel, the one or more coded segments for use as redundant information by the remote node to recover one or more of the uncoded segments should they be erased in the wireless channel. 
 
     
     
       15. The method of  claim 14 , wherein:
 segmenting the coding block into a number of equal-length uncoded segments includes padding the coding block if a size of the coding block is not a multiple of a desired segment length. 
 
     
     
       16. The method of  claim 14 , wherein generating one or more coded segments includes:
 generating a set of random coefficients for the equal-length uncoded segments; and 
 linearly combining the equal-length uncoded segments using the random coefficients to generate a first coded segment.