Routing method in asymmetric networks

• US 9,166,906 B2
• Filed: 12/15/2008
• Issued: 10/20/2015
• Est. Priority Date: 12/15/2008
• Status: Active Grant

• Current Assignee: Intergraph Corporation (Hexagon AB)
• Original Assignee: Intergraph Corporation (Hexagon AB)
• Inventors: Laskowski, Peter
• Primary Examiner(s): Ton, Dang
• Assistant Examiner(s): RANDHAWA, MANDISH K
• Application Number:
  US12/334,891
• Publication Number:
  US 20100150019A1
• Time in Patent Office: 2,500 Days
• Field of Search: 370/338, 370/235, 709/245
• US Class Current: 1/1
• CPC Class Codes: G06F 9/4862 the task being a mobile agent, i.e. specifically designed to migrate
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/08 Learning-based routing, e.g. using neural networks or artificial intelligence
• CPC Class Codes: H04L 45/26 Route discovery packet
• CPC Class Codes: H04L 67/34 involving the movement of software or configuration parameters network booting or remote initial program loading [RIPL] G06F9/4416

Abstract

A method for establishing or reinforcing a path through an asymmetric network of interconnected nodes includes storing navigation data at one or more nodes, for use by an agent in traveling from that node to a subsequent node, while ultimately traveling from a first terminal node (for example, a source node) to a second terminal node (for example, a destination node). As the agent travels from a first terminal node to a second terminal node via an intermediate node, the agent modifies the navigation data intended for use by an agent traveling from the second terminal node to the first terminal node via the intermediate node. Agents traveling complementary routes reinforce each other paths, allowing paths to be determined and reinforced.

Claims

1. A method of establishing a path from a source terminal node, which may be referred-to as a first node, to a destination terminal node, which may be referred-to as a second node, through an asymmetric network comprising a plurality of interconnected nodes, wherein an agent traveling through the network traverses links connecting one node to the next until it reaches the destination terminal node, the method including:

receiving a first agent at a third node from a fourth node, wherein the first agent originated at the source terminal node and is navigating through the network toward the destination terminal node;

prior to directing the first agent to the next node, modifying a first upstream navigation data table at the third node based on information about the path previously traveled by the first agent, wherein the data in the first upstream navigation data table is configured to direct a later agent from the third node to the source terminal node;

determining a next node on the path from the third node based on data in a first downstream navigation data table, wherein the data in the first downstream navigation data table is configured to direct the first agent to the destination terminal node; and

directing the first agent to the next node.

2. The method of claim 1, wherein the data in the first upstream navigation data table comprises information about one or more upstream nodes.

3. The method of claim 2, wherein the data in the first upstream navigation data table further comprises a first weighting factor.

4. The method of claim 1, wherein the information about the path previously traveled by the first agent comprises information about the fourth node.

5. The method of claim 4, wherein the information about the fourth node comprises information pertaining to the operating characteristics of the fourth node.

6. The method of claim 4, wherein the information about the fourth node comprises information about a link connecting the fourth node to the third node.

7. The method of claim 1 wherein modifying the first upstream navigation data table comprises changing at least one weighting factor to reinforce the path previously traveled by the first agent.

8. The method of claim 1, wherein the first downstream navigation data table comprises information about one or more downstream nodes.

9. The method of claim 8, wherein the first downstream navigation data table comprises a second weighting factor.

10. The method of claim 9, wherein the act of determining comprises assessing information about one or more downstream nodes by combining such information with data from the first downstream navigation data table.

11. The method of claim 1, further including:

sending a second agent from the destination terminal node to the source terminal node, the second agent traversing a path previously followed by the first agent, the second agent modifying navigation data in a second downstream navigation data table of at least one intermediate node to reinforce the path previously followed by the first agent, the navigation data in the second downstream navigation data table configured to direct a subsequent agent to the destination terminal node.

12. The method of claim 11 wherein modifying the navigation data comprises changing at least one weighting factor.

13. A method of establishing a path from a source terminal node, which may be referred-to as a first node, to a destination terminal node, which may be referred-to as a second node, through an asymmetric network comprising a plurality of interconnected nodes, wherein an agent traveling through the network traverses links connecting one node to the next until it reaches the source terminal node, including:

receiving a first agent at a third node from a fourth node, wherein the first agent originated at the destination terminal node and is navigating through the network to the source terminal node;

modifying a first navigation data table at the third node based on information about the path previously traveled by the first agent, wherein the data in the first navigation data table is configured to direct a later agent from the third node to the destination terminal node;

determining a next node on the path from the third node based on data in a second navigation data table, wherein the data in the second navigation data table is configured to direct the first agent to the source terminal node; and

directing the first agent to the next node.

14. The method of claim 13, wherein the data in the first navigation data table comprises information about one or more downstream nodes.

15. The method of claim 14, wherein the data in the first navigation data table further comprises a first weighting factor.

16. The method of claim 13, wherein the information about the path previously traveled by the first agent comprises information about the fourth node.

17. The method of claim 16, wherein the information about the fourth node comprises information pertaining to the operating characteristics of the fourth node.

18. The method of claim 16, wherein the information about the fourth node comprises information about the link connecting the third node to the fourth node.

19. The method of claim 13 wherein modifying the first navigation data table comprises changing at least one weighting factor to reinforce the path previously traveled by the first agent.

20. The method of claim 13, wherein the second navigation data table comprises information about one or more upstream nodes.

21. The method of claim 20, wherein the second navigation data table comprises at least a second weighting factor.

22. The method of claim 20, wherein the act of determining comprises assessing information about one or more upstream nodes, by combining such information with data from the second navigation data table.

23. The method of claim 13, further including:

sending a second agent from the source terminal node to the destination terminal node, the second agent traversing a path previously followed by the first agent, the second agent modifying navigation data of at least one intermediate node to reinforce the path previously followed by the first agent.

24. The method of claim 23, wherein modifying the navigation data comprises modifying the data in the second navigation data table.

25. The method of claim 24 wherein modifying the navigation data comprises changing at least one weighting factor.

26. A method of identifying a path through an asymmetric network of nodes interconnected by links, including a first node, a second node, and a plurality of other nodes, including:

sending a first agent from the first node to the second node via a third node, wherein the first agent determines the next node in the path based on data in a first downstream navigation data table at the third node, wherein the data in the first downstream navigation data table is configured to direct the first agent to the second node;

the first agent modifying the data in a first upstream data navigation table a at the third node, wherein the data in the first upstream data navigation table is configured to direct a subsequent agent to the first node.

27. The method of claim 26, further comprising:

sending a second agent from the second node to the first node via an intermediate node, wherein the second agent determines the next node in its path based on data in a third upstream navigation data table at the intermediate node, wherein the data in the third upstream navigation table is configured to direct the second agent to the first node; and

the second agent modifying the data in a fourth downstream navigation data table at the intermediate node, wherein the data in the fourth downstream navigation data table is configured to direct a subsequent agent to the second node.

28. The method of claim 26, further including identifying a preferred path from the first node to the second node by selecting a path followed by one or more agents arriving at the second node from the first node.

29. The method of claim 27, further including identifying a preferred path from the first node to the second node by selecting a path followed by one or more agents arriving at the first node from the second node.

30. A computer program product for identifying a path through an asymmetric network of nodes, the computer program product comprising a non-transitory tangible storage medium having computer readable code thereon, the computer readable program code including:

program code for maintaining a downstream routing table of navigation information;

program code for maintaining an upstream routing table of navigation information;

program code for sending a first agent from a first node to a second node via a third node, wherein the first agent independently navigates from the third node to its next location node by determining the next location node based on navigation information in the downstream routing table, the navigation information in the downstream routing table configured to direct the first agent to the second node; and

program code for modifying the navigation information in the upstream routing table as a function of the path traversed by the first agent prior to arriving at the third node, such that the navigation information in the upstream routing table is configured to direct a subsequent agent to the first node.

31. The computer program product of claim 30, wherein the downstream routing table is associated with the second node.

32. The computer program product of claim 30, wherein the upstream routing table is associated with the first node.

33. The computer program product of claim 30, wherein information in the navigation information in the upstream routing table includes information about at least one downstream node.

34. The computer program product of claim 33, wherein information in the navigation information in the upstream routing table includes at least one weighting factor.

35. The computer program product of claim 30, wherein navigation information in the upstream routing table includes information about at least one upstream node.

36. The computer program product of claim 35, navigation information in the upstream routing table e includes at least one weighting factor.

37. A method of establishing a path from a source terminal node, which may be referred-to as a first node, to a destination terminal node, which may be referred-to as a second node, through an asymmetric network comprising a plurality of interconnected nodes, wherein an agent traveling through the network traverses links connecting one node to the next until it reaches the source terminal node, including:

receiving a first agent at a third node from a fourth node, wherein the first agent originated at the destination terminal node and is navigating through the network to the source terminal node;

modifying a first navigation data table at the third node based on information about the path previously traveled by the first agent, wherein the data in the first navigation data table is configured to direct a later agent from the third node to the destination terminal node;

determining a next node on the path from the third node based on data in a second navigation data table, wherein the data in the second navigation data table is configured to direct the first agent to the source terminal node;

directing the first agent to the next node; and

sending a second agent from the source terminal node to the destination terminal node, the second agent traversing a path previously followed by the first agent, the second agent modifying navigation data of at least one intermediate node to reinforce the path previously followed by the first agent, wherein modifying the navigation data comprises modifying the data in the second navigation data table.

38. The method of claim 37 wherein modifying the navigation data comprises changing at least one weighting factor.