Reliable bulk data dissemination using rateless codes

• US 9,350,683 B2
• Filed: 06/18/2013
• Issued: 05/24/2016
• Est. Priority Date: 06/18/2013
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Hui, Jonathan W., Hong, Wei, Vasseur, Jean-Philippe
• Primary Examiner(s): Gillis, Brian J
• Assistant Examiner(s): Lee, Gil H.
• Application Number:
  US13/920,802
• Publication Number:
  US 20140372585A1
• Time in Patent Office: 1,071 Days
• US Class Current: 1/1
• CPC Class Codes: H03M 13/3761 using code combining, i.e. using combining of codeword portions which may have been transmitted separately, e.g. Digital Fountain codes, Raptor codes or Luby Transform [LT] codes
• CPC Class Codes: H04L 1/004 by using forward error control H04L1/0618 takes precedence; coding, decoding or code conversion, for error detection or correction H03M13/00
• 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 49/20 Support for services

Abstract

In one embodiment, an aggregating node receives feedback messages from one or more destination nodes in the network. The destination nodes are designated to receive data as packets from a source node using rateless coding. Further, the feedback messages indicate whether packets are needed at a corresponding destination node to complete the data. Then, the feedback messages are aggregated into a single aggregated message, and the aggregated message is transmitted toward the source node.

Claims

1. A method, comprising:

receiving, at an aggregating node in a network, feedback messages from one or more destination nodes in the network, the destination nodes being designated to receive data as packets from a source node using rateless coding, wherein the feedback messages indicate whether packets are needed at a corresponding destination node to complete the data;

determining, from the feedback messages, an amount of packets needed by each of the corresponding destination node;

calculating and storing a maximum amount of packets needed by a single destination node;

aggregating the feedback messages into a single aggregated message, wherein the aggregated message is a single integer that represents the maximum amount of packets needed at any one of the one or more destination nodes, wherein the maximum amount of packets is indicated in the aggregated message only when a difference between a greatest amount of packets needed by a single destination node and a least amount of packets needed by a single destination node is less than a threshold value; and

transmitting the aggregated message toward the source node.

2. The method according to claim 1, further comprising:

detecting a previous maximum amount of packets needed by a single destination node that was previously stored, wherein

the maximum amount of packets is indicated in the aggregated message only when the maximum amount of packets exceeds the previous maximum amount of packets.

3. The method according to claim 1, further comprising:

determining, from the feedback messages, identities of the one or more destination nodes; and

indicating, in the aggregated message, the identities of the one or more destination nodes.

4. The method according to claim 3, further comprising:

determining, from the feedback messages, an amount of destination nodes of the one or more destination nodes, wherein

the identities of the one or more destination nodes are indicated in the aggregated message only when the amount of destination nodes is less than a threshold value.

5. The method according to claim 4, further comprising:

indicating, in the aggregated message, the amount of packets needed by each of the one or more destination nodes only when the amount of destination nodes is less than the threshold value.

6. The method according to claim 4, further comprising:

indicating, in the aggregated message, an identity of the aggregating node when the amount of destination nodes is not less than the threshold value.

7. The method according to claim 1, further comprising:

indicating, in the aggregated message, a time-based component based on a time of transmission of the aggregated message.

8. The method according to claim 1, further comprising:

determining, from the feedback messages, a time-based component associated with each feedback message;

determining, based on the time-based component, a timing relationship between the feedback messages and feedback messages that were previously received; and

reducing an amount of packets requested in the aggregated message.

9. The method according to claim 1, further comprising:

transmitting the aggregated message as a 1-hop distributed message.

10. The method according to claim 1, wherein:

the one or more destination nodes can migrate between networks, and

the one or more destination nodes receive a randomly coded packet in each network.

11. An apparatus, comprising:

one or more network interfaces that communicate with a network;

a processor coupled to the one or more network interfaces and configured to execute a process; and

a memory configured to store program instructions which contain the process executable by the processor, the process comprising;

receiving, at an aggregating node in the network, feedback messages from one or more destination nodes in the network, the destination nodes being designated to receive data as packets from a source node using rateless coding, wherein the feedback messages indicate whether packets are needed at a corresponding destination node to complete the data;

determining, from the feedback messages, an amount of packets needed by each of the corresponding destination nodes;

calculating and storing a maximum amount of packets needed by a single destination node;

aggregating the feedback messages into a single aggregated message, wherein the aggregated message is a single integer that represent the maximum amount of packets needed at any one of the one or more destination nodes, wherein the maximum amount of packets is indicated in the aggregated message only when a difference between a greatest amount of packets needed by a single destination node and at least amount of packets needed by a single destination node is less than a threshold value; and

transmitting the aggregated message toward the source node.

12. The apparatus according to claim 11, wherein the process further comprises:

detecting a previous maximum amount of packets needed by a single destination node that was previously stored, wherein

the maximum amount of packets is indicated in the aggregated message only when the maximum amount of packets exceeds the previous maximum amount of packets.

13. The apparatus according to claim 11, wherein the process further comprises:

determining, from the feedback messages, identities of the one or more destination nodes; and

indicating, in the aggregated message, the identities of the one or more destination nodes.

14. The apparatus according to claim 13, wherein the process further comprises:

determining, from the feedback messages, an amount of destination nodes of the one or more destination nodes, wherein

the identities of the one or more destination nodes are indicated in the aggregated message only when the amount of destination nodes is less than a threshold value.

15. The apparatus according to claim 14, wherein the process further comprises:

indicating, in the aggregated message, the amount of packets needed by each of the one or more destination nodes only when the amount of destination nodes is less than the threshold value.

16. The apparatus according to claim 14, wherein the process further comprises:

indicating, in the aggregated message, an identity of the aggregating node when the amount of destination nodes is not less than the threshold value.

17. The apparatus according to claim 11, wherein the process further comprises:

indicating, in the aggregated message, a time-based component based on a time of transmission of the aggregated message.

18. The apparatus according to claim 11, wherein the process further comprises:

determining, from the feedback messages, a time-based component associated with each feedback message;

determining, based on the time-based component, a timing relationship between the feedback messages and feedback messages that were previously received; and

reducing an amount of packets requested in the aggregated message.

19. The apparatus according to claim 11, wherein the process further comprises:

transmitting the aggregated message as a 1-hop distributed message.

20. The apparatus according to claim 11, wherein:

the one or more destination nodes can migrate between networks, and

the one or more destination nodes receive a randomly coded packet in each network.

21. A tangible non-transitory computer readable medium storing program instructions that cause a computer to execute a process, the process comprising:

receiving, at an aggregating node in a network, feedback messages from one or more destination nodes in the network, the destination nodes being designated to receive data as packets from a source node using rateless coding, wherein the feedback messages indicate whether packets are needed at a corresponding destination node to complete the data;

determining, from the feedback messages, an amount of packets needed by each of the corresponding destination nodes;

calculating and storing a maximum of packets needed by a single destination node;

aggregating the feedback messages into a single aggregated message, wherein the aggregated message is a single integer that represents the maximum amount of packets needed at any one of the one or more destination nodes, wherein the maximum amount of packets is indicated in the aggregated message only when a difference between a greatest amount of packets needed by a single destination mode and a least amount of packets needed by a single destination node is less than a threshold value; and

transmitting the aggregated message toward the source node.