Constrained shortest path routing method

• US 6,321,271 B1
• Filed: 12/22/1998
• Issued: 11/20/2001
• Est. Priority Date: 12/22/1998
• Status: Expired due to Term

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Lau, Wing Cheong, Kodialam, Muralidharan Sampath, Yan, Anlu
• Primary Examiner(s): Maung, Zarni
• Assistant Examiner(s): Cardone, Jason D.
• Application Number:
  US09/218,576
• Time in Patent Office: 1,064 Days
• Field of Search: 709/238, 709/241, 709/244, 370/351, 370/255, 710/131, 379/220.01, 379/221.06
• US Class Current: 709/241
• CPC Class Codes: H04L 2012/562 Routing
• CPC Class Codes: H04L 2012/5623 Network design, dimensioning, topology or optimisation
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

A real-time method for routing subject to an acceptable delay constraint between nodes in high-speed data networks, such as PNNI protocol networks, uses an illustrative two-phase algorithm employing Dijkstra'"'"'s algorithm at each phase. In an illustrative first phase, the Dijkstra SPF algorithm is used in seeking the shortest cumulative delay from the destination to the source, thereby generating cumulative delay labels from a node j to the destination node k. The delay results are then employed in the second phase, where the Dijkstra SPF algorithm is illustratively employed for determining administrative weight (AW) as the link metric subject to modification in accordance with results obtained in the first phase.

Claims

1. A method for choosing a path in a network from a source to a destination, the network comprising a plurality of nodes, each node connected to a plurality of other nodes by links, each link having a weights reflecting at least first and second link parameters, paths connecting said source and said destination comprising a plurality of links, said paths being subject to a constraint on the cumulative value of said second parameter for links in a path, the method comprising the steps of:

a. for paths from said destination to said source, performing a minimum-weight path identification based on said second parameter for paths in said network, thereby to generate labels identifying weights for said second parameter for each nodej to destination k,

b. for paths from said source to said destination performing a minimum-weight path identification from said source using said first parameter as a link metric, and

c. eliminating any nodes that would cause the constraint on said cumulative value for said second parameter to be violated.

2. The method of claim 1 wherein said minimum-weight path identification for paths from said destination is accomplished using a Dijkstra SPF algorithm.

3. The method of claim 2 wherein said minimum-weight path identification for paths from said source is accomplished using a Dijkstra SPF algorithm.

4. The method of claim 3 wherein the method further comprises repeating steps a, b and c for paths between said source node and each possible destination node in said network.

5. The method of claim 4 wherein for destination nodes after a first destination node, path information from said source to one or more other destinations is used in determining acceptable paths to each said nodes after said first destination.

6. The method of claim 1 wherein said step of performing a minimum-weight path identification from said source comprises (i) labeling a node i with cumulative AW from the source node, and (ii) tracking cumulative delay (D_s,i) from the source based on values for said second parameter during said minimum-weight path identification from said destination.

7. The method of claim 6 wherein said step of eliminating comprises labeling neighboring nodes j of a permanently labeled node i only if (D_s,i+d_j,k+δ

_i,j) is less than the specified end-to-end constraint on said second parameter, where δ

_i,j is the value of said second parameter for the link between nodes i and j, and d_j,k is the value for said second parameter for the link between nodes j and k.

8. The method of claim 7 wherein said second parameter is link delay.

9. The method of claim 6 wherein said second parameter is link delay.

10. The method of claim 1 wherein operation of said network is in accordance with PNNI protocols.

11. The method of claim 10 wherein said second parameter is link delay.

12. The method of claim 1 wherein said first parameter is administrative weight (AW).

13. The method of claim 1 comprising the further step of eliminating any paths in said minimum-weight path identification for paths from said source for which the cumulative value for said first parameter exceeds a predetermined maximum.