Routing Method in Asymmetric Networks

• US 20100150019A1
• Filed: 12/15/2008
• Published: 06/17/2010
• Est. Priority Date: 12/15/2008
• Status: Active Grant

• Current Assignee: Intergraph Corporation (Hexagon AB)
• Original Assignee: Intergraph Software Technologies Company
• Inventors: Laskowski, Peter
• Granted Patent: US 9,166,906 B2
• Time in Patent Office: Days
• US Class Current: 370/254
• 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 to a destination terminal 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;

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 associated with the source terminal node;

determining a next node on the path based on data in a second navigation data table, wherein the data in the second navigation data table is associated with 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 navigation data table comprises information about one or more upstream nodes.

3. The method of claim 2, wherein the data in the first 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 the a link connecting the fourth node to the third node.

7. The method of claim 1 wherein modifying the first 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 second navigation data table comprises information about one or more downstream nodes.

9. The method of claim 8, wherein the second 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 second 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 of at least one intermediate node to reinforce the path previously followed by the first agent.

12. The method of claim 11, wherein modifying the navigation data comprises modifying the data in the first navigation data table.

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

14. A method of establishing a path from a source terminal node to a destination terminal 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 associated with the destination terminal node;

determining a next node on the path based on data in a second navigation data table, wherein the data in the second navigation data table is associated with the source terminal node; and

directing the first agent to the next node.

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

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

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

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

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

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

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

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

23. The method of claim 21, 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.

24. The method of claim 14, 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.

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

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

27. 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 navigation data table at the third node, wherein the data in a first navigation data table is associated with the second node;

the first agent modifying the data in a second navigation data table at the third node, wherein the data in the second navigation data table is associated with the first node.

28. The method of claim 27, 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 navigation data table at the intermediate node, wherein the data in the third navigation table is associated with the first node; and

the second agent modifying the data in a fourth navigation data table at the intermediate node, wherein the data in the fourth navigation data table is associated with the second 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 second node from the first node.

30. The method of claim 28, 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.

31. An asymmetric network of nodes interconnected by links, including:

a first terminal node, a second terminal node, and a plurality of other nodes, wherein at least one of the plurality of other nodes contains a first data repository for storing navigation data associated with the first terminal node, and a second data repository associated with the second terminal node.

32. The network of claim 31 further comprising wherein the navigation data in the first data repository is modifiable by an agent traveling from the first terminal node to the second terminal node.

33. The network of claim 31 further comprising wherein the navigation data in the second data repository is modifiable by an agent traveling from the second terminal node to the first terminal node.

34. The network of claim 31 further comprising wherein the navigation data in the first data repository is modifiable by an agent traversing a pre-defined path from the second terminal node to the first terminal node.

35. The network of claim 31 further comprising wherein the navigation data in the second data repository is modifiable by an agent traversing a pre-defined path from the first terminal node to the second terminal node.

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

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

program code for maintaining a second 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 first routing table; and

program code for modifying the navigation information in the second routing table as a function of the path traversed by the first agent prior to arriving at the third node.

37. The computer program product of claim 36, wherein the first table of navigation information is associated with the second node.

38. The computer program product of claim 36, wherein the second table of navigation information is associated with the first node.

39. The computer program product of claim 36, wherein information in the first routing table includes information about at least one downstream node.

40. The computer program product of claim 39, wherein information in the first routing table includes at least one weighting factor.

41. The computer program product of claim 36, wherein information in the second routing table includes information about at least one upstream node.

42. The computer program product of claim 41, wherein information in the second routing table includes at least one weighting factor.