Inter-domain constraint-based shortest path first technique for supporting hierarchical routing in interconnected multi-domain optical transport networks

• US 7,215,644 B2
• Filed: 03/19/2003
• Issued: 05/08/2007
• Est. Priority Date: 03/19/2003
• Status: Expired due to Fees

• Current Assignee: RPX Corporation
• Original Assignee: Alcatel-Lucent SA (Nokia Corporation)
• Inventors: Wu, Fuming, Skoog, Frederick H.
• Primary Examiner(s): Shah; Chirag G.
• Application Number:
  US10/392,227
• Publication Number:
  US 20040184441A1
• Time in Patent Office: 1,511 Days
• Field of Search: None
• US Class Current: 370/248
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/50 using label swapping, e.g. multi-protocol label switch [MPLS]

Abstract

Method and system for implementing an inter-domain constraint-based shortest path first (“IrD-CSPF”) technique for supporting hierarchical routing in interconnected multi-domain OTNs are described. In one embodiment, the invention is a method for calculating a network path in an interconnected multi-domain network. The method comprises receiving a path setup request message for a new traffic flow in the network identifying a source node in one domain of the network and a destination node in a second domain of the network; determining a common ancestor hierarchical routing domain that includes ancestor nodes of both the source and destination nodes; calculating an inter-domain path from one ancestor node to the other ancestor node that determines, for each lower-level domain, border nodes in the domain from the source node to the destination node; and for each bottom-level domain, calculating an intra-domain path between the border nodes that were determined for the domain.

Claims

1. A method for calculating a network path in an interconnected multi-domain network, the method comprising:

receiving a path setup request message for a new traffic flow in the network, wherein the path setup request message identifies a source node in one domain of the network and a destination node in a second domain of the network;

determining a common ancestor hierarchical routing domain that includes ancestor nodes of both the source and destination nodes;

calculating an inter-domain path from the ancestor node of the source node to the ancestor node of the destination node in the common ancestor hierarchical routing domain that determines, for each lower-level domain, border nodes in the domain from the source node to the destination node using a traffic engineering network database (“

TEDB”

) that stores network topology information for the common ancestor hierarchical routing domain; and

for each bottom-level domain, calculating an intra-domain path between the border nodes that were determined for the domain.

2. The method of claim 1 wherein the determining is performed in a bottom-up manner.

3. The method of claim 1 wherein the determining comprises determining a lowest common ancestor hierarchical routing domain that includes the ancestor node of the source node and the ancestor node of the destination node.

4. The method of claim 1 wherein the path setup request message comprises a Soft Permanent Connection (“

SPC”

) request.

5. The method of claim 1 wherein the connection request comprises a Switched Connection (“

SC”

) request.

6. The method of claim 5 further comprising searching a local Domain Information Database (“

DIDB”

) to confirm that a node that hosts a source TNA address is the source node.

7. The method of claim 1 wherein the inter-domain path is calculated using an Inter-Domain Constraint-Based Shortest Path First (“

IrD-CSPF”

) procedure.

8. The method of claim 1 wherein the intra-domain path is calculated using an Intra-Domain CSPF (“

IaD-CSPF”

) procedure.

9. The method of claim 1 further comprising verifying legibility of traffic attributes in the path setup request message.

10. A method for calculating a path through an interconnected multi-domain network responsive to receipt of a path setup request message, the path setup request message identifying a source node and a destination node, wherein the network can be represented by a hierarchical routing structure comprising a bottom level and at least one upper level, the method comprising:

determining whether the source and destination nodes are in a common bottom level domain;

if the source and destination nodes are not in a common bottom level domain, determining a common ancestor hierarchical routing domain that includes ancestor nodes of both the source and destination nodes;

calculating an inter-domain path from the ancestor node of the source node to the ancestor node of the destination node in the common ancestor hierarchical routing domain, wherein the inter-domain path specifies, for each immediately lower-level domain, border nodes in the domain along a path from the source node to the destination node; and

for each bottom-level domain, calculating an intra-domain path between the border nodes that were determined for the domain.

11. The method of claim 10 further comprising repeating the calculation of an inter-domain path for each successively lower level until the bottom level is reached.

12. The method of claim 10 further comprising if the nodes are in the same bottom level domain, using an IaD-CSPF procedure to determine an intra-domain route from the source node to the destination node.

13. The method of claim 10 wherein the calculating an inter-domain path comprises using a traffic engineering network database (“

TEDB”

) that stores network topology information for the common ancestor hierarchical routing domain.

14. The method of claim 10 wherein the determining comprises determining a lowest common ancestor hierarchical routing domain that includes the ancestor node of the source node and the ancestor node of the destination node.

15. The method of claim 10 wherein the path setup request message comprises a Soft Permanent Connection (“

SPC”

) request.

16. The method of claim 10 wherein the connection request comprises a Switched Connection (“

SC”

) request.

17. The method of claim 10 wherein the inter-domain path is calculated using an Inter-Domain Constraint-Based Shortest Path First (“

IrD-CSPF”

) procedure.

18. The method of claim 10 wherein the intra-domain path is calculated using an Intra-Domain CSPF (“

IaD-CSPF”

) procedure.

19. The method of claim 10 further comprising verifying legibility of traffic attributes in the path setup request message.

20. A system for calculating a network path in an interconnected multi-domain network, the system comprising:

means for receiving a path setup request message for a new traffic flow in the network, wherein the path setup request message identifies a source node in one domain of the network and a destination node in a second domain of the network;

means for determining a common ancestor hierarchical routing domain that includes ancestor nodes of both the source and destination nodes;

means for calculating an inter-domain path from the ancestor node of the source node to the ancestor node of the destination node in the common ancestor hierarchical routing domain that determines, for each lower-level domain, border nodes in the domain from the source node to the destination node using a traffic engineering network database (“

TEDB”

) that stores network topology information for the common ancestor hierarchical routing domain; and

means for calculating an intra-domain path between the border nodes that were determined for each bottom-level domain.

21. The system of claim 20 wherein the means for determining comprises means for determining a lowest common ancestor hierarchical routing domain that includes the ancestor node of the source node and the ancestor node of the destination node.

22. The system of claim 20 wherein the path setup request message comprises a Soft Permanent Connection (“

SPC”

) request.

23. The system of claim 20 wherein the connection request comprises a Switched Connection (“

SC”

) request.

24. The system of claim 23 further comprising:

a local Domain Information Database (“

DIDB”

); and

means for searching the local DIDB to confirm that a node that hosts a source TNA address is the source node.

25. The system of claim 20 wherein the means for calculating an inter-domain path comprises an Inter-Domain Constraint-Based Shortest Path First (“

IrD-CSPF”

) procedure.

26. The system of claim 20 wherein the means for calculating an intra-domain path comprises an Intra-Domain CSPF (“

IaD-CSPF”

) procedure.

27. The system of claim 20 further comprising means for verifying legibility of traffic attributes in the path setup request message.

28. An apparatus for calculating a network path in an interconnected multi-domain network representable by a hierarchical routing structure comprising a bottom hierarchical level and at least one upper hierarchical level, the apparatus comprising:

a routing controller (“

RC”

) located at a domain of each upper hierarchical level;

a Traffic Engineering Database (“

TEDB”

) associated with each RC;

a Domain Information Database (“

DIDB”

) associated with each RC; and

an inter-domain Constraint Based Shortest Path First (“

IrD-CSPF”

) procedure for calculating an inter-domain path from an ancestor node of a source node identified in a path setup request message to an ancestor node of a destination node identified in the path setup request message, wherein the ancestor nodes are located in a lowest common ancestor hierarchy domain of the identified source and destination nodes; and

at each bottom level domain, an intra-domain CSPF (“

IaD-CSPF”

) procedure for calculating a path through the domain between a pair of border nodes identified for the domain by the IrD-CSPF procedure.

29. The apparatus of claim 28 wherein the TEDB stores network topology information for the common ancestor hierarchical routing domain.

30. The apparatus of claim 28 wherein the DIDB stores domain-related information of the domain.