Routing scheme based on virtual space representation

• US 7,231,459 B2
• Filed: 12/17/2003
• Issued: 06/12/2007
• Est. Priority Date: 12/17/2002
• Status: Expired due to Fees

• Current Assignee: Girish P. Saraph
• Original Assignee: Girish P. Saraph
• Inventors: Saraph, Girish P.
• Primary Examiner(s): Maung; Zarni
• Assistant Examiner(s): Tran; Nghi
• Application Number:
  US10/739,655
• Publication Number:
  US 20040193729A1
• Time in Patent Office: 1,273 Days
• Field of Search: 709/241, 709/224, 709/242, 709/220
• US Class Current: 709/241
• CPC Class Codes: H04L 41/145 involving simulating, designing, planning or modelling of a network
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/122 by minimising distances, e.g. by selecting a route with minimum of number of hops
• CPC Class Codes: H04L 45/124 using a combination of metrics
• CPC Class Codes: H04L 45/125 based on throughput or bandwidth
• CPC Class Codes: H04L 45/14 Routing performance; Theoretical aspects
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04L 45/247 using M:N active or standby paths

Abstract

A method and apparatus for a routing scheme based on virtual space representation is described and illustrated. In one embodiment, the invention is a method of operating a network. The method includes translating a topology of the network into a digital representation in the form of multi-dimensional spatial configuration wherein a directed distance to any destination node or site indicates the available path options with the least or low number of hops through the network. The method also includes adding transmission cost data to the digital representation. The method further includes operating the network based on the digital representation.

Claims

1. A method of operating a network, comprising:

representing a network topology of individual nodes and connections of the network in a digital representation of spatial configuration;

simulating an attractive force between directly connected nodes, a repulsive force between not directly connected nodes, and a deterministic pseudo-random forces on the individual nodes in a multi-dimensional space to transform the digital representation into a new representation of the same nodes and connections by letting the network evolve under the influence of the simulated forces, wherein a directed spatial distance within the digital representation to any destination node or site indicates the available path options with a low number of hops through the network; and

operating the network using the digital representation.

2. The method of claim 1, further comprising:

propagating the digital representation to nodes of the network.

3. The method of claim 1, further comprising:

propagating the digital representation throughout the network.

4. The method of claim 1, further comprising:

detecting changes to the network; and

repeating the representing and the simulating.

5. The method of claim 1, further comprising:

detecting a periodic update time; and

updating the digital representation.

6. The method of claim 1, further comprising:

recording usage data of individual network links;

assigning costs to the network links and nodes;

assigning a total cost to a link that reflects both cost based on low-hop path to destination and link and node costs based on usage data; and

using the total cost value for path selection at an intermediate node towards the destination.

7. The method of claim 6, further comprising:

detecting changes to the usage data of individual network links; and

updating the link and node costs.

8. The method of claim 6, further comprising:

detecting failure in individual network links or nodes; and

updating the link and node costs to reflect failure.

9. The method of claim 6, further comprising:

detecting a periodic update time; and

updating the link and node costs based on usage data.

10. The method of claim 1, further comprising:

exploring the network to determine the topology of the network.

11. The method of claim 1, wherein:

the network is an electronic network for transmission of data packets, including processor nodes.

12. The method of claim 1, wherein:

the network is a transportation network for goods, including community nodes and transportation links.

13. The method of claim 1, wherein:

the digital representation includes a graph of the network.

14. The method of claim 1, wherein:

within the digital representation a node represents a cluster of nodes in the network.

15. The method of claim 6, wherein:

the network is an electronic network for transmission of data packets, including processor nodes.

16. The method of claim 6, wherein:

the network is an electronic network for transmission of data packets, including processor nodes and the method is used for path selection.

17. The method of claim 6, wherein:

the network is an electronic network for transmission of data packets, including processor nodes and the method is used for primary and back-up path selection.

18. The method of claim 6, wherein:

the network is a transportation network for goods, including community nodes and transportation links.

19. The method of claim 1, wherein:

the attractive and repulsive force magnitudes depend on the spatial distances between the nodes in a spatial representation of the network.

20. The method of claim 1, further comprising:

converting external network addresses into addresses related to the digital representation.

21. An apparatus, comprising:

a network topology translator to produce a digital representation of network topology in the form of multi-dimensional spatial configuration;

a simulator module to simulate an attractive force between directly connected nodes, a repulsive force between not directly connected nodes, and a deterministic pseudo-random force on the individual nodes in a multi-dimensional space to transform the digital representation into a new representation of the same nodes and connections by letting the network under the influence of the simulated forces, wherein a directed spatial distance within the digital representation to any destination node or site indicates the available path options with a low number of hops through the network;

a link and node cost update module;

a network digital representation storage module coupled to the network topology translator and the link and node cost update module; and

a network controller.

22. The apparatus of claim 21, wherein:

the network topology translator includes a force simulator.

23. The apparatus of claim 21, further comprising:

a network change detector coupled to the network controller.

24. The apparatus of claim 21, further comprising:

a network periodic update timer coupled to the network controller and the link and node cost update module.

25. The apparatus of claim 21, wherein:

The network digital representation storage module further stores usage data and link and node costs of the network.

26. The apparatus of claim 21, further comprising:

a network topology exploration module.

27. The apparatus of claim 21, wherein:

the digital representation storage module stores a graph of the network.

28. The apparatus of claim 21 further comprising:

an address converter coupled to the controller.

29. The apparatus of claim 21, wherein:

the cost update module, digital representation storage module, and the network controller are implemented in a distributed manner using nodes in the network.

30. A computer readable medium embodying instructions, the instructions, when executed by a processor, causing the processor to execute a method of operating a network, the method comprising:

translating a topology of the network into a digital representation in the form of multi-dimensional spatial configuration;

simulating an attractive force between directly connected nodes, a repulsive force between not directly connected nodes, and a deterministic pseudo-random force on the individual nodes in a multi-dimensional space to transform the digital representation into a new representation of the same nodes and connections by letting the network evolve under the influence of the simulated forces, wherein a directed spatial distance within the digital representation to any destination node or site indicates the available path options with a low number of hops through the network;

adding transmission usage cost data; and

operating the network based on the digital representation and usage data.

31. The medium of claim 30, wherein the method further comprises:

converting external network addresses into addresses related to the digital representation.

32. The medium of claim 30, wherein the method further comprises:

propagating the digital representation to nodes of the network.

33. The medium of claim 30, wherein the method further comprises:

propagating the digital representation throughout the network.

34. The medium of claim 30, wherein the method further comprises:

detecting changes to the network; and

repeating the translating the network in a changed state.

35. The medium of claim 30, wherein the method further comprises:

recording usage data of the network;

detecting a periodic update time; and

determining usage costs in the network in an updated state.

36. The medium of claim 30, wherein:

the digital representation includes a graph of the network.

37. The medium of claim 30, wherein:

translating a topology of the network into the digital representation includes simulating multi-dimensional forces acting on nodes of the network.

38. The medium of claim 37, wherein:

the forces include an attractive force between directly connected nodes, a repulsive force between not directly connected nodes, and a deterministic pseudo-random force on each node.

39. The medium of claim 30, wherein the method further comprises:

exploring the network to determine the topology of the network.

40. The medium of claim 30, wherein:

the network is an electronic network for transmission of data packets, including processor nodes.

41. The medium of claim 30, wherein:

the network is a transportation network for goods, including community nodes and transportation links.

42. An apparatus for operating a network, comprising:

means for translating a topology of the network into a digital representation in the form of multi-dimensional spatial configuration;

means for simulating an attractive force between directly connected nodes, a repulsive force between not directly connected nodes, and a deterministic pseudo-random force on the individual nodes in a multi-dimensional space to transform the digital representation into a new representation of the same nodes and connections by letting the network evolve under the influence of the simulated forces, wherein a directed spatial distance within the digital representation to any destination node or site indicates the available path options with a low number of hops through the network;

means for adding transmission cost data to the digital representation; and

means for operating the network based on the digital representation.

43. The apparatus of claim 42, further comprising:

means for detecting changes to the network.

44. The apparatus of claim 42, further comprising:

means for detecting a periodic update time;

means for recording usage data of the network; and

means for determining usage costs in the network in an updated state.

45. The apparatus of claim 42, further comprising:

means for exploring the network to determine the topology of the network.

46. A method of operating a network, comprising:

translating a topology of the network into a digital representation;

simulating an attractive force between directly connected nodes, a repulsive force between not directly connected nodes, and a deterministic pseudo-random force on the individual nodes in a multi-dimensional space to transform the digital representation into a new representation of the same nodes and connections by letting the network evolve under the influence of the simulated forces, wherein a directed spatial distance within the digital representation to any destination node or site indicates the available path options with a low number of hops through the network;

simulating the network using the digital representation to adjust the digital representation; and

operating the network based on the digital representation.

47. A computer readable medium embodying instructions, the instructions, when executed by a processor, causing the processor to execute a method of operating a network, the method comprising:

translating a topology of the network into a digital representation;

simulating an attractive force between directly connected nodes, a repulsive force between not directly connected nodes, and a deterministic pseudo-random force on the individual nodes in a multi-dimensional space to transform the digital representation into a new representation of the same nodes and connections by letting the network evolve under the influence of the simulated forces, wherein a directed spatial distance within the digital representation to any destination node or site indicates the available path options with a low number of hops through the network;

simulating the network using the digital representation to adjust the digital representation; and

operating the network based on the digital representation.