Complex adaptive routing system and method for a nodal communication network

• US 7,280,545 B1
• Filed: 12/20/2001
• Issued: 10/09/2007
• Est. Priority Date: 12/20/2001
• Status: Active Grant

• Current Assignee: ARRIS Enterprises LLC (CommScope Holding Company, Inc.)
• Original Assignee: MeshNetworks, Inc. (Motorola Solutions, Inc.)
• Inventors: Nagle, Darragh J.
• Primary Examiner(s): Kizou, Hassan
• Assistant Examiner(s): ROBERTS, BRIAN S
• Application Number:
  US10/022,283
• Time in Patent Office: 2,119 Days
• Field of Search: 370/237, 370/255, 370/437, 370/471, 709/285, 709/246, 709/224
• US Class Current: 370/400
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/566 Routing instructions carried by the data packet, e.g. active networks
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing
• CPC Class Codes: H04W 40/24 Connectivity information management, e.g. connectivity discovery or connectivity update

Abstract

A complex adaptive routing system and method for routing data packets in a nodal network, in particular, an ad-hoc nodal network. Each data packet contains data representing its routing strategy for routing to a destination node. When a node receives the data packet, it executes an agent program to determine the best route for routing the data packet to its destination node based on the routing strategy and other factors, such as the current conditions of the nodes and paths to the nodes. The agent program updates the strategy data in the data packet, as well as the routing table of the node, before the node sends the data packet to the next node in the selected route. The system and method therefore enables the data packet routing decisions to be dynamically adapted to changing conditions in the network.

Claims

1. A method for routing a data packet in a network comprising nodes interconnected by links, the method comprising at a routing node:

receiving said data packet;

extracting routing strategy data from said received data packet, said routing strategy data including information pertaining to at least one routing path via which to route said received data packet to a destination node, each said routing path including at least one other of said nodes;

comparing said routing strategy data with one or more routing information including one or more alternative routing strategies stored within said routing node;

selecting a routing path via which to route said data packet based on said comparing of said routing strategy data;

assigning credits to the routing strategy data and the one or more alternative routing strategies;

selecting a revised routing strategy by comparing the assigned credits when the selected routing path differs from the routing strategy data; and

updating said routing strategy data in said data packet.

2. A method as clamed in claim 1, wherein:

said routing strategy data includes information representing at least some of said nodes that said data packet visited prior to being received by said node.

3. A method as claimed in claim 1, further comprising:

transmitting said data packet to a node along said selected routing path.

4. A method as claimed in claim 1, further comprising:

updating a routing table at said routing node based on said updated routing strategy data.

5. A method as claimed in claim 1, wherein:

said selecting selects as said selected routing path one of said at least one routing path identified by said routing strategy data.

6. A method as claimed in claim 1, wherein:

said selecting selects as said selected routing path a routing path different than any said at least one routing path identified by said routing strategy data.

7. A method as claimed in claim 1, wherein:

said updating includes combining data representing at least two routing paths to generate data representing a different routing path.

8. A method as claimed in claim 1, further comprising:

sending said updated routing strategy data to other said nodes.

9. A method as claimed in claim 1, wherein:

said updating includes generating a new routing strategy.

10. A method as claimed in claim 1, wherein:

said network comprises an ad-hoc network.

11. A node for routing a data packet in a network comprising nodes interconnected by links, the node comprising:

a receiver, for receiving said data packet; and

a controller, for extracting routing strategy data from said received data packet, said routing strategy data including information pertaining to at least one routing path via which to route said received data packet to a destination node, each said routing path including at least one other of said nodes, for comparing said routing strategy data with one or more routing information including one or more alternative routing strategies stored within said routing node, for selecting a routing path via which to route said data packet based on said comparing of said routing strategy data, for assigning credits to the routing strategy data and the one or more alternative routing strategies, and selecting a revised routing strategy by comparing the assigned credits when the selected routing path differs from the routing strategy data, and for updating said routing strategy data in said data packet.

12. A node as clamed in claim 11, wherein:

said routing strategy data includes information representing at least some of said nodes that said data packet visited prior to being received by said node.

13. A node as claimed in claim 11, further comprising:

a transmitter, for transmitting said data packet to a next node along said selected routing path.

14. A node as claimed in claim 11, further comprising:

a routing table stored within a memory,

wherein said controller is further for updating said routing table based on said updated routing strategy data.

15. A node as claimed in claim 11, wherein:

said controller selects as said selected routing path one of said at least one routing path identified by said routing strategy data.

16. A node as claimed in claim 11, wherein:

said controller selects as said selected routing path a routing path different than any said at least one routing path identified by said routing strategy data.

17. A node as claimed in claim 11, wherein:

said controller performs said updating by combining data representing at least two routing paths to generate data representing a different routing path.

18. A node as claimed in claim 11, further comprising:

a transmitter for sending said updated routing strategy data to other said nodes.

19. A node as claimed in claim 11, wherein:

said controller performs said updating by generating a new routing strategy.

20. A node as claimed in claim 11, wherein:

said network comprises an ad-hoc network.

21. A method for routing a data packet within an adhoc network comprising

generating a data packet at an originator node, the data packet comprising:

a node history,

a routing strategy, and

a destination node field;

receiving the data packet by a routing node;

when the routing node is not the destination node, at the routing node;

identifying a best routing strategy by comparing the routing strategy to one or more route information stored in the routing node,

assigning credits to each of the routing strategy and the one or more alternative routing strategies and selecting a revised data packet route by comparing the assigned credits,

generating the revised data packet route including a revised routing strategy when the best routing strategy differs from the routing strategy, and

transmitting the data packet to a next routing node along a data packet route associated with the best routing strategy; and

repeating the receiving, identifying, generating, and transmitting steps at the next routing node.

22. A method for routing a data packet within an adhoc network as claimed in claim 21, further comprising, prior to the generating step, storing the one or more route information in a routing table in a memory of the routing node.

23. A method for routing a data packet within an adhoc network as claimed in claim 22, wherein the one or more route information comprises one or more information about at least one other data packet that had previously traversed the routing node selected from a group comprising a routing strategy and a selected destination node.

24. A method for routing a data packet within an adhoc network as claimed in claim 22, further comprising prior to the repeating step:

updating the routing table at the routing node using the node history, the routing strategy, and the destination node of the data packet, and

wherein the repeating step includes repeating the updating step.

25. A method for routing a data packet within an adhoc network as claimed in claim 22, further comprising prior to the repeating step:

updating the routing table at the routing node using the revised routing strategy and the destination node of the data packet, and

wherein the repeating step includes repeating the updating step.

26. A method for routing a data packet within an adhoc network as claimed in claim 22, further comprising at the routing node prior to the receiving step:

receiving a routing table broadcast from a neighbor node; and

updating the routing table using the routing table broadcast.

27. A method for routing a data packet within an adhoc network as claimed in claim 21, wherein the node history comprises one or more data representing one or more nodes through which the data packet has previously passed through.

28. A method for routing a data packet within an adhoc network as claimed in claim 21, wherein the routing strategy comprises a desired route which the data packet is to traverse when traveling to the destination node.

29. A method for routing a data packet within an adhoc network as claimed in claim 21, wherein the routing strategy is associated with one or more routing goals for the data packet.

30. A method for routing a data packet within an adhoc network as claimed in claim 29, wherein the one or more routing goals can are selected from a group of routing goals comprising a route speed, a route performance, a route length, and a route probability of success.

31. A method of operation of a node within an adhoc network comprising:

receiving a data packet, the data packet comprising;

a node history,

a routing strategy, and

a destination node field;

comparing the node to the destination node;

when the node is not the destination node,

identifying a best routing strategy by comparing the routing strategy to one or more route information stored in the node,

assigning credits to each of the routing strategy and the one or more alternative routing strategies and selecting a revised data packet route by comparing the assigned credits,

generating the revised data packet route including a revised routing strategy when the best routing strategy differs from the routing strategy, and

transmitting the data packet to a next node along a data packet route associated with the best routing strategy.

32. A method of operation of a node within an adhoc network as claimed in claim 31, further comprising, prior to the receiving step,

storing the one or more route information in a routing table in a memory of the node.

33. A method of operation of a node within an adhoc network as claimed in claim 32, wherein the one or more route information comprises one or more information about at least one other data packet that had previously traversed the node selected from a group comprising a routing strategy and a selected destination node.

34. A method of operation of a node within an adhoc network as claimed in claim 32, further comprising:

updating the routing table using the node history, the routing strategy, and the destination node of the data packet.

35. A method of operation of a node within an adhoc network as claimed in claim 32, further comprising:

updating the routing table using the revised routing strategy and the destination node of the data packet.

36. A method of operation of a node within an adhoc network as claimed in claim 32, further comprising:

receiving a routing table broadcast from a neighbor node; and

updating the routing table using the routing table broadcast.

37. A method of operation of a node within an adhoc network as claimed in claim 31, wherein the node history comprises one or more data representing one or more nodes through which the data packet has previously passed through.

38. A method of operation of a node within an adhoc network as claimed in claim 31, wherein the routing strategy comprises a desired route which the data packet is to traverse when traveling to the destination node.

39. A method of operation of a node within an adhoc network as claimed in claim 31, wherein the routing strategy is associated with one or more routing goals for the data packet.

40. A method of operation of a node within an adhoc network as claimed in claim 31, wherein the one or more routing goals can are selected from a group of routing goals comprising a route speed, a route performance, a route length, and a route probability of success.