Control over network coding for enhanced radio transport optimization

• US 9,209,943 B1
• Filed: 06/06/2013
• Issued: 12/08/2015
• Est. Priority Date: 06/06/2012
• Status: Active Grant

• Current Assignee: BAE Systems Information and Electronic Systems Integration Incorporated (BAE Systems Plc)
• Original Assignee: BAE Systems Information and Electronic Systems Integration Incorporated (BAE Systems Plc)
• Inventors: Firoiu, Victor, DeCleene, Brian T., Lauer, Gregory, Shen, Xinzhuo
• Primary Examiner(s): Abraham, Esaw
• Application Number:
  US13/911,631
• Time in Patent Office: 915 Days
• US Class Current: 1/1
• CPC Class Codes: H04L 1/0076 Distributed coding, e.g. network coding, involving channel coding coding in both space and time H04L1/0618; cooperative diversity H04B7/022
• CPC Class Codes: H04L 1/1607 Details of the supervisory signal
• CPC Class Codes: H04L 1/1664 the supervisory signal being transmitted together with payload signals; piggybacking
• CPC Class Codes: H04L 1/1816 with retransmission of the same, encoded, message
• CPC Class Codes: H04L 1/1819 with retransmission of additional or different redundancy
• CPC Class Codes: H04L 1/1851 using multiple timers
• CPC Class Codes: H04L 1/1883 using multiple timers
• CPC Class Codes: H04L 1/189 Transmission or retransmission of more than one copy of a message
• CPC Class Codes: H04L 2001/0093 Point-to-multipoint

Abstract

A system and method for transmitting encoded data in a network is presented. The method begins with a source node of a network encoding a first generation of data using linearly-independent encoding vectors to produce an encoded first generation. Next, packets containing the encoded first generation are created. The packets are then transmitted over a subgraph of nodes with multiple paths to a destination node. A determination is made at a receiving node that an insufficient amount of packets of the encoded first generation have been received in order to decode the encoded first generation. A repair request is sent from the receiving node to nodes upstream to indicate a need for more packets of the encoded first generation without specifying a particular packet. In response to the repair request, at least one node upstream from the receiving node sends a packet with encoded first generation data.

Claims

1. A method for transmitting encoded data in a network comprising:

grouping packets into a first generation of a plurality of packets;

in a source node of a network, encoding the first generation using linearly-independent encoding vectors to produce an encoded first generation;

transmitting the encoded first generation as a plurality of packets over a subgraph of nodes over multiple paths to a destination node, wherein the subgraph of nodes is a small group of nodes of the network;

determining in a receiving node of the subgraph that an insufficient amount of packets of the encoded first generation have been received in the receiving node in order to decode the encoded first generation;

sending a first repair request from the receiving node to nodes which are upstream of the receiving node, wherein the repair request indicates a need for more packets of the encoded first generation without specifying a particular packet;

in response to the repair request, sending a packet with encoded first generation data to the receiving node from a first node which is upstream of the receiving node; and

while in a fully-reliable mode further comprising;

generating a second repair request in at least one node which is upstream of the receiving node and which does not have data of the encoded first generation, wherein the second repair request indicates a need for more packets with data of the encoded first generation without specifying a particular packet; and

sending the second repair request from the at least one node to nodes which are upstream of the at least one node until a node with data of the encoded first generation receives the second repair request.

2. The method for transmitting encoded data of claim 1 wherein the nodes which are upstream of the receiving node are a single hop away from the receiving node and while in a semi-reliable mode further comprising:

ignoring the first repair request at one or more of the nodes which are upstream of the receiving node when the one or more nodes do not have any data of the encoded first generation.

3. The method for transmitting encoded data of claim 1 wherein the encoded first generation is part of a file transfer on the network and further comprising, while in the fully-reliable mode:

joining a new destination node to the subgraph;

determining if the new destination node is too far behind in receiving the file transfer;

if the new destination node is not too far behind in receiving the file transfer, placing the new destination node in an in session mode and accepting all generations of the file transfer; and

if the new destination node is too far behind the file transfer, placing the new destination node in a not in session mode and ignoring all generations of the file transfer.

4. The method for transmitting encoded data of claim 3 further comprising:

when the new destination node is in the in session mode, sending from the new destination node to nodes which are upstream of the new destination node repair requests to request missing generations of the encoded first generation.

5. The method for transmitting encoded data of claim 3 wherein the determining if the new destination node is too far behind in receiving the file transfer is based, at least in part, on an information identification of the first encoded generation that is included in all packets of the first encoded generation.

6. The method for transmitting encoded data of claim 3 further comprising:

when encoded first generation information in the packets of the encoded first generation is equal to or greater than encoded second generation information in packets of a second encoded generation, switching the new destination node from the not in session mode to the in session mode and assigning a first generation that is to be received to the encoded second generation, wherein the assigning is done by the new destination node.

7. The method for transmitting encoded data of claim 1 further comprising:

when the source node is ending transmission of the encoded first generation to the destination node, sending from the source node to the destination node a real generation size of the encoded first generation in a packet of the encoded first generation;

determining at the destination node if encoded first generation data corresponds to the generation size; and

when the encoded first generation data corresponds to the generation size, decoding the encoded first generation data to produce un-encoded data and presenting the un-encoded data to an application.

8. The method for transmitting encoded data of claim 1 wherein the sending the first repair request comprises:

piggy backing the first repair request in a header of a data packet.

9. The method for transmitting encoded data of claim 1 further comprising:

when enough of the encoded first generation is received at the destination node, decoding the encoded first generation and providing decoded data to an application.

10. The method for transmitting encoded data of claim 9 wherein the decoding comprises:

decoding the encoded first generation based on Gaussian elimination.

11. The method for transmitting encoded data of claim 1 wherein, before the sending the packet with encoded first generation data to the receiving node, waiting a predetermined time after the first repair request is received at one of the nodes which is upstream of the receiving node.

12. The method for transmitting encoded data of claim 1 wherein the subgraph includes a forwarding node between the source node and the destination node and further comprising:

determining a forwarding factor for the forwarding node, wherein the forwarding factor is a calculated value based, at least in part, on (a) link quality between the forwarding node and other nodes and (b) available bandwidth, and wherein timing of transmissions from the forwarding node are determined based, at least in part, on the forwarding factor.

13. The method for transmitting encoded data of claim 12 wherein the forwarding factor is defined as the ratio between an average number of packets sent by the forwarding node and a number of packets having encoded first generation data received by the forwarding node.

14. The method for transmitting encoded data of claim 13 further comprising:

maintaining in the forwarding node a credit counter that is incremented by the forwarding factor upon each packet having encoded first generation data received by the forwarding node and is decremented by one for every packet sent by the forwarding node and limited to not become negative.

15. The method for transmitting encoded data of claim 1 further comprising:

assembling at the source node a complete generation of the packets of the first generation;

initializing a credit counter for the source node equal to a size of the complete generation times a forwarding factor of the source node, wherein the forwarding factor of the source node is a calculated value based, at least in part, on (a) link quality between the source node and other nodes and (b) available bandwidth; and

transmitting data from the source node based, at least in part, on the credit counter.

16. The method for transmitting encoded data of claim 1 wherein the source node and the destination node are both wireless nodes.

17. A method for transmitting encoded data in a network comprising, while in a fully-reliable mode:

grouping packets into a first generation of a plurality of packets;

in a source node of a network, encoding the first generation using linearly-independent encoding vectors to produce an encoded first generation;

transmitting the encoded first generation as a plurality of packets over a subgraph of nodes over multiple paths to a destination node, wherein the subgraph of nodes is a small group of nodes of the network;

determining in a receiving node of the subgraph that an insufficient amount of packets of the encoded first generation have been received in the receiving node in order to decode the encoded first generation;

sending a repair request from the receiving node to nodes which are upstream of the receiving node, wherein the repair request indicates a need for more packets of the encoded first generation without specifying a particular packet;

in response to the repair request, sending a packet with encoded first generation data to the receiving node from a first node which is upstream of the receiving node;

at the destination node, keeping track of the packets of the encoded first generation and a next encoded second generation and detecting a gap in generations received at the destination node by detecting that the encoded second generation is larger than expected; and

sending requests from the destination node to nodes which are upstream of the destination node for more packets of the encoded first generation until the encoded first generation is complete enough to be decoded at the destination node.

18. A method comprising:

encoding data into an encoded first generation;

transmitting from a source node to a network node a plurality of first generation packets of the encoded first generation, the first generation packets containing random linear combinations of data sets which are linearly independent within the encoded first generation;

determining that not enough of the first generation packets have been received at the network node to decode the first generation packets;

based, at least in part on the determining, generating and sending a first repair request from the network node to nodes which are upstream of the network node, wherein the repair request indicates a need for more packets of the encoded first generation;

in response to the repair request, sending a packet with encoded first generation data to the network node from a first node which is upstream of the network node; and

while in a fully-reliable mode further comprising;

generating a second repair request in at least one node which is upstream of the network node and which does not have data of the encoded first generation, wherein the second repair request indicates a need for more packets with data of the encoded first generation; and

sending the second repair request from the at least one node to nodes which are upstream of the at least one node until a node with data of the encoded first generation receives the second repair request.

19. The method of claim 18 wherein the encoding comprises encoding data into the encoded first generation using linearly-independent encoding vectors;

and

wherein the generating and sending the first repair request comprises generating and sending the first repair request without specifying any missing first generation packets.