Disrupted adaptive routing

• US 9,369,381 B2
• Filed: 05/15/2014
• Issued: 06/14/2016
• Est. Priority Date: 05/17/2013
• Status: Active Grant

• Current Assignee: Raytheon BBN Technologies Corp. (Rtx Corporation)
• Original Assignee: Raytheon BBN Technologies Corp. (Rtx Corporation)
• Inventors: Redi, Jason Keith, Khanna, Bakul Grover
• Primary Examiner(s): Pham, Chi H
• Assistant Examiner(s): Hom, Shick
• Application Number:
  US14/278,786
• Publication Number:
  US 20140341227A1
• Time in Patent Office: 761 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: H04L 45/32 Flooding denial of service attacks H04L63/1458
• CPC Class Codes: H04L 45/70 Routing based on monitoring results
• CPC Class Codes: H04W 40/023 Limited or focused flooding to selected areas of a network

Abstract

According to one aspect, embodiments of the invention provide a node comprising a processor, a memory including a predefined mapping, the predefined mapping correlating network characteristics to related critical thresholds at which a delivery ratio of the node is close to a maximum level and at which a total number of transmissions by the node is close to a minimum number necessary to achieve the delivery ratio, and a component configured to communicate with one-hop neighbors of the node and configured to determine at least one characteristic of a dynamic network based on information received from the one-hop neighbors of the node, wherein, in reference to the predefined mapping, the processor is configured to identify a critical threshold associated with the at least one characteristic of the network and is configured to transmit a first packet to at least one one-hop neighbor based on the critical threshold.

Claims

1. A node configured to communicate with other nodes of a dynamic network, the node comprising:

a processor;

a memory coupled to the processor, the memory including a predefined mapping, the predefined mapping correlating network characteristics to related critical thresholds at which a delivery ratio of the node is close to a maximum level and at which a total number of transmissions by the node is close to a minimum number necessary to achieve the delivery ratio; and

a component coupled to the processor, the component configured to communicate with one-hop neighbors of the node and configured to determine at least one characteristic of the dynamic network based on information received from the one-hop neighbors of the node,

wherein, in reference to the predefined mapping, the processor is configured to identify one of the related critical thresholds in the predefined mapping associated with the at least one characteristic of the network and is configured to transmit a first packet to at least one one-hop neighbor based on the identified critical threshold, and

wherein the related critical thresholds of the predefined mapping include critical gossip probabilities.

2. The node of claim 1, wherein, in reference to the predefined mapping, the processor is configured to identify a critical gossip probability associated with the at least one characteristic of the network and to transmit the first packet to a group of the at least one one-hop neighbors, the group determined by the processor based on the critical gossip probability.

3. The node of claim 2, wherein the processor is further configured to identify, within a portion of the first packet, the group of the at least one one-hop neighbors.

11. The node of claim 1, wherein the processor is further configured to receive a second packet from a one-hop neighbor of the node, the second packet identifying, within a portion of the second packet, a group of intended recipients of the second packet.

12. The node of claim 11, wherein the processor is further configured to determine whether the node is included within the group of intended recipients, and, in response to a determination that the node is included within the group of intended recipients, to forward the second packet to at least one one-hop neighbor based on the identified critical threshold.

13. The node of claim 1, wherein the at least one characteristic of the network determined by the component is a size of the network.

14. The node of claim 1, wherein the at least one characteristic of the network determined by the component is a node density of the network.

15. The node of claim 1, wherein the component is further configured to periodically update the at least one characteristic of the dynamic network based on information received from the one-hope neighbors of the node, and

wherein, in reference to the predefined mapping, the processor is further configured to adjust the identified critical threshold based on an updated at least one characteristic of the dynamic network.

4. A node configured to communicate with other nodes of a dynamic network, the node comprising:

a processor;

a memory coupled to the processor, the memory including a predefined mapping, the predefined mapping correlating network characteristics to related critical thresholds at which a delivery ratio of the node is close to a maximum level and at which a total number of transmissions by the node is close to a minimum number necessary to achieve the delivery ratio; and

a component coupled to the processor, the component configured to communicate with one-hop neighbors of the node and configured to determine at least one characteristic of the dynamic network based on information received from the one-hop neighbors of the node,

wherein, in reference to the predefined mapping, the processor is configured to identify one of the related critical thresholds in the predefined mapping associated with the at least one characteristic of the network and configured to transmit a first packet to at least one one-hop neighbor based on the identified critical threshold, and

wherein the related critical thresholds of the predefined mapping include critical packet lifetimes.

5. The node of claim 4, wherein, in reference to the predefined mapping, the processor is configured to identify a critical packet lifetime associated with the at least one characteristic of the network, program the first packet with the critical packet lifetime, and transmit the first packet to the at least one one-hop neighbor of the node.

6. The node of claim 4, wherein the processor is further configured to receive a second packet from a one-hop neighbor of the node, the second packet identifying, within a portion of the second packet, a group of intended recipients of the second packet.

7. The node of claim 6, wherein the processor is further configured to determine whether the node is included within the group of intended recipients, and, in response to a determination that the node is included within the group of intended recipients, to forward the second packet to at least one one-hop neighbor based on the identified critical threshold.

8. The node of claim 4, wherein the at least one characteristic of the network determined by the component is a size of the network.

9. The node of claim 4, wherein the at least one characteristic of the network determined by the component is a node density of the network.

10. The node of claim 4, wherein the component is further configured to periodically update the at least one characteristic of the dynamic network based on information received from the one-hope neighbors of the node, and

wherein, in reference to the predefined mapping, the processor is further configured to adjust the identified critical threshold based on an updated at least one characteristic of the dynamic network.

16. A method for transmitting packets between nodes of a dynamic network, the method comprising:

receiving, by a component of a first node, information from at least one one-hop neighbor of the first node, the information indicative of at least one characteristic of the dynamic network;

referencing a predefined table stored in the first node, the predefined table correlating network characteristics to related critical thresholds at which a delivery ratio of the first node is close to a maximum level and at which a total number of transmissions by the first node is close to a minimum number necessary to achieve the delivery ratio;

identifying, in response to referencing the predefined table, one of the related critical thresholds in the predefined table associated with the first node; and

transmitting, by the first node, a packet to at least one one-hop neighbor of the first node based on the identified critical threshold,

wherein identifying one of the related critical thresholds includes identifying, in reference to the predefined table, a critical gossip probability of the first node.

17. The method of claim 16, wherein transmitting the packet to at least one one-hop neighbor of the first node includes transmitting the packet to a subset of the first nodes one-hop neighbors, the subset based on the critical gossip probability.

18. The method of claim 17, further comprising identifying, within a portion of the packet, the subset of the first nodes one-hop neighbors.

19. The method of claim 18, further comprising:

receiving, by a second node, the transmitted packet from the first node;

determining, by the second node, whether the second node is included in the subset of nodes identified in the received packet; and

in response to a determination, by the second node, that the second node is included in the subset of nodes identified in the received packet, forwarding the packet to at least one one-hop neighbor of the second node.

20. The method of claim 19, wherein forwarding the packet to at least one one-hop neighbor of the second node comprises:

referencing a predefined table stored in the second node, the predefined table correlating network characteristics of the second node to related critical thresholds of the second node at which a delivery ratio of the second node is close to a maximum level and at which a total number of transmissions by the node is close to a minimum number of transmissions necessary to achieve the delivery ratio of the second node;

identifying, in response to referencing the predefined table of the second node, one of the related critical thresholds in the predefined table of the second node associated with the second node; and

transmitting, by the second node, the packet to the at least one one-hop neighbor of the second node based on the identified critical threshold of the second node.

25. The method of claim 16, wherein receiving information indicative of at least one characteristic of the dynamic network includes receiving information indicative of at least one of a size of the dynamic network and a node density of the dynamic network.

26. The method of claim 16, further comprising generating the predefined table based on a plurality of network simulations including varying network characteristics.

21. A method for transmitting packets between nodes of a dynamic network, the method comprising:

receiving, by a component of a first node, information from at least one one-hop neighbor of the first node, the information indicative of at least one characteristic of the dynamic network;

referencing a predefined table stored in the first node, the predefined table correlating network characteristics to related critical thresholds at which a delivery ratio of the first node is close to a maximum level and at which a total number of transmissions by the first node is close to a minimum number necessary to achieve the delivery ratio;

identifying, in response to referencing the predefined table, one of the related critical thresholds in the predefined table associated with the first node; and

transmitting, by the first node, a packet to at least one one-hop neighbor of the first node based on the identified critical threshold,

wherein identifying one of the related critical thresholds includes identifying, in reference to the predefined table, a critical packet lifetime of the first node.

22. The method of claim 21, further comprising assigning the critical packet lifetime to the packet.

23. The method of claim 21, wherein receiving information indicative of at least one characteristic of the dynamic network includes receiving information indicative of at least one of a size of the dynamic network and a node density of the dynamic network.

24. The method of claim 21, further comprising generating the predefined table based on a plurality of network simulations including varying network characteristics.