Device for and method of network routing

• US 8,443,105 B1
• Filed: 12/12/2011
• Issued: 05/14/2013
• Est. Priority Date: 12/12/2011
• Status: Active Grant

• Current Assignee: The United States of America As Represented By The Director National Security Agency
• Original Assignee: The United States of America As Represented By The Director National Security Agency
• Inventors: Shayman, Mark A., Finkler, Todd B.
• Primary Examiner(s): Hussain, Tauqir
• Application Number:
  US13/374,638
• Time in Patent Office: 519 Days
• Field of Search: 709/238
• US Class Current: 709/238
• CPC Class Codes: H04L 45/125 based on throughput or bandwidth
• CPC Class Codes: H04W 40/24 Connectivity information management, e.g. connectivity discovery or connectivity update

Abstract

A device and method of routing traffic in a network by receiving the network, assigning a maximum temperature value to gateway nodes, calculating temperature values for router nodes, determining self-utilization values for nodes, determining neighborhood-utilization values for router nodes, determining pressure values for gateway nodes, determining pressure values for router nodes, identifying router node sent traffic, identifying neighboring nodes having higher temperatures than router node, identifying neighboring node with lowest pressure value, sending traffic to neighboring node with lowest pressure value, and stopping if the neighboring node is a gateway node, otherwise identifying the node as a router node and returning to the step of finding neighboring nodes.

Claims

1. A device for routing traffic in a mobile mesh network, comprising:

a) a network-graph receiver for receiving a graph of a mesh network, where the network includes at least one node of a first type and at least one node of a second type, where the node of the first type is a router node, where the node of the second type is a gateway node, and where nodes are neighbors if they can communicate with each other, having an input, and having an output;

b) a gateway node temperature value assigner for assigning a maximum user-definable temperature value to each gateway node, having an input connected to the output of the network graph receiver, and having an output;

c) a router node temperature value assigner for calculating a temperature for each router node, where the temperature value for each router node is the highest temperature of a neighboring node times a user-definable conductivity value, having an input connected to the output of the gateway node temperature value assigner, and having an output;

d) a node self-utilization value assigner for determining a self-utilization value for each router node and each gateway node, where the self-utilization value for each node is a user-definable percentage of a total time that the node spends transmitting, receiving, and waiting while the node'"'"'s neighboring node is transmitting, having an input connected to the output of the router node temperature value assigner, and having an output;

e) a router node neighborhood-utilization value assigner for determining a neighborhood-utilization value for each router node, where the neighborhood-utilization value for each router node is a maximum of the router node'"'"'s self-utilization value and the self-utilization values of all of its neighboring nodes, having an input connected to the output of the self-utilization value assigner, and having an output;

f) a gateway node pressure value assignor for determining a pressure value for each gateway node, where the pressure value for each gateway node is the gateway node'"'"'s self-utilization value, having an input connected to the output of the router node neighborhood-utilization value assigner, and having an output;

g) a router node pressure value assigner for determining a pressure value for each router node, where the pressure value for each router node is a function of the neighborhood-utilization value of the router node and pressure values of the router node'"'"'s neighboring nodes that have higher temperature values than the router node'"'"'s temperature value, having an input connected to the output of the gateway node pressure value assigner, and having an output;

h) a traffic router node identifier for identifying a router node that was sent traffic from a mobile device, having an input connected to the output of the router node pressure value assigner, and having an output;

i) a highest neighbor node temperature finder for identifying each node in the mesh network that is a neighbor node of the router node identified in the last operation of the device that has a higher temperature than the router node, having an input bus connected to the output of the traffic router node identifier, and having an output;

j) a lowest pressure value finder for identifying the node identified by the highest neighbor node temperature finder that has the lowest pressure value, having an input connected to the output of the highest neighbor node temperature finder, and having an output;

k) a hop-node identifier for sending traffic from the router node identified by the traffic router node identifier to the node identified by the lowest pressure value finder, having an input connected to the output of the lowest pressure value finder, and having an output connected to the input bus of the output of the highest neighbor node temperature finder, where the device stops if the node to which traffic was sent is a gateway node, otherwise the node identified by the lowest pressure value finder is a router node and operation of the device returns to the highest neighbor node temperature finder.

2. The device of claim 1, wherein said router node pressure value assigner is comprised of a router node pressure value assigner that identifies neighboring nodes with higher temperatures than the router node, identifies pressure values associated with such neighboring nodes, identifies the minimum of the identified pressures values, compares the minimum pressure value identified to the neighborhood-utilization value of the router node, setting the pressure value of the router node to the neighborhood-utilization value if the neighborhood-utilization value is greater than or equal to the minimum identified pressure value then, and setting the pressure value of the router node to the minimum identified pressure value if the minimum identified pressure value is greater than the neighborhood-utilization value.

4. The method of claim 2, wherein said step of determining a pressure value for each router node is comprised of the step of determining a pressure value for each router node by identifying neighboring nodes with higher temperatures than the router node, identifying pressure values associated with such neighboring nodes, identifying the minimum of the identified pressures values, comparing the minimum pressure value identified to the neighborhood-utilization value of the router node, setting the pressure value for the router node to the neighborhood-utilization value if the neighborhood-utilization value is greater than or equal to the minimum identified pressure value, and setting the pressure value for the router node to the minimum identified pressure value if the minimum identified pressure value is greater than the neighborhood-utilization value.

3. A method of routing traffic in a mobile mesh network, comprising the steps of:

a. receiving a graph of a mesh network, where the network includes at least one node of a first type and at least one node of a second type, where the node of the first type is a router node, where the node of the second type is a gateway node, and where nodes are neighbors if they can communicate with each other;

b. assigning a maximum user-definable temperature value to each gateway node;

c. calculating a temperature for each router node, where the temperature value for each router node is the highest temperature of a neighboring node times a user-definable conductivity value;

d. determining a self-utilization value for each router node and each gateway node, where the self-utilization value for each node is a user-definable percentage of a time that the node spends transmitting, receiving, and waiting while its neighbor node is transmitting;

e. determining a neighborhood-utilization value for each router node, where the neighborhood-utilization value for each router node is a maximum of the router node'"'"'s self-utilization value and the self utilization values of all of its neighbor nodes, if any;

f. determining a pressure value for each gateway node, where the pressure value for each gateway node is the gateway node'"'"'s self-utilization value;

g. determining a pressure value for each router node, where the pressure value for each router node is a function of the router node'"'"'s neighborhood-utilization value and pressure values of the router node'"'"'s neighbor nodes that have higher temperature values than the router node'"'"'s temperature value;

h. identifying a router node that was sent traffic from a mobile device;

i. identifying each node in the mesh network that is a neighbor node of the router node identified in the most recently performed last step that has a higher temperature than the router node;

j. identifying the node identified in step (i) that has the lowest pressure value;

k. sending traffic from the router node involved in step (i) to the node identified in step (j); and

l. stopping if the node to which traffic was sent in step (k) is a gateway node, otherwise identifying the node identified in step (j) as a router node and returning to step (i).