Method and apparatus for optimizing routing through network nodes

• US 20050060400A1
• Filed: 10/27/2004
• Published: 03/17/2005
• Est. Priority Date: 02/14/2000
• Status: Active Grant

• Current Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Liou, Yuh-mei Marie, Mannepalli, Rao Y., Ramanujam, Vedha
• Granted Patent: US 7,372,816 B2
• Time in Patent Office: Days
• US Class Current: 709/223
• 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/12 Shortest path evaluation

Abstract

A method for reducing the problem space associated with determining intra-network circuit provisioning paths within a large communications network by selecting only a sub-set of the total network nodes, including the start-node and end-node of a communication path by bounding, using one of a plurality of predefined shapes having an appropriate size, and calculating the best path using only the network elements included within the sub-set of total nodes.

Claims

1. An apparatus for managing a communications network comprising a plurality of nodes, said apparatus comprising:

means for representing each node within said network according to its respective geographic position;

means for defining a window comprising a start-node, an end-node and a plurality of intervening nodes, each of said start-node, end-node and intervening nodes having at least one communication link to a respective adjacent node; and

means for calculating, using said nodes included within said window, a shortest communication path between said start-node and said end-node,

wherein said window includes a predefined percentage of the total geographic area occupied by said network and is selected from the group of shapes consisting of;

a rectangle defined by a line segment beginning at said start-node and ending at said end-node, said line segment traversing a distance (D) and a rectilinear area about said line segment, said rectilinear area comprising those nodes approximately within a perpendicular distance (δ

) of said start-node, said end-node, or said line segment between said start-node and said end-node,

a circle having a mid-point equidistant from said start-node and said end-node, said circle having a diameter greater than the distance between said start-node and said end-node; and

an ellipse defined by the equation d₁+d₂=D+2δ

, where d₁ is the distance from the start-node SN to the boundary of the ellipse, d₂ is the distance from the end-node E_n to the boundary of the ellipse, D is the distance between the start-node and the end-node, and δ

is a control parameter.

2. The apparatus of claim 1, wherein said predefined percentage is in the range of approximately 3-10% of the total geographic area occupied by said network.

3. The apparatus of claim 2, wherein said predefined percentage is approximately 5% of the total geographic area occupied by said network.

4. The apparatus of claim 1 wherein said means for representing each node is a database.

5. The apparatus of claim 4 wherein said database contains normalized representations of each node.

6. The apparatus of claim 1 wherein said means for defining a window is a controller coupled to said means for representing each node.

7. The apparatus of claim 1 wherein said means for calculating is a controller processing a selected portion of nodes in the network according to a shortest path algorithm.

8. The apparatus if claim 7 wherein the shortest path algorithm in Dijkstra'"'"'s algorithm.

9. The apparatus of claim 1, wherein said window is defined as a double circle.

10. The apparatus of claim 9, wherein said double circle window is further defined by a radius of a first circle having a midpoint at the start-node a radius of a second circle having a midpoint at the end-node.