Constraining topology size and recursively calculating routes in large networks

• US 8,817,798 B2
• Filed: 08/10/2012
• Issued: 08/26/2014
• Est. Priority Date: 08/10/2012
• Status: Active Grant

• Current Assignee: Ciena Corporation
• Original Assignee: Ciena Corporation
• Inventors: Skalecki, Darek, Swinkels, Gerard L
• Primary Examiner(s): Mattis, Jason
• Assistant Examiner(s): CHIANG, KUO TUNG
• Application Number:
  US13/571,771
• Publication Number:
  US 20140044008A1
• Time in Patent Office: 746 Days
• Field of Search: 370/254, 370/400, 370/392, 370/393
• US Class Current: 370/400
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 45/025 Updating only a limited number of routers, e.g. fish-eye update
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• 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/123 Evaluation of link metrics techniques for monitoring network metrics H04L43/08
• CPC Class Codes: H04L 45/124 using a combination of metrics
• CPC Class Codes: H04L 45/127 based on intermediate node capabilities
• CPC Class Codes: H04L 45/20 Hop count for routing purposes, e.g. TTL
• CPC Class Codes: H04L 45/26 Route discovery packet

Abstract

A method of managing a network comprising a plurality of nodes. Each node maintains a respective topology database containing topology information of the network within a local region of the node, the local region encompassing a subset of the plurality of nodes of the network. The nodes of the network implementing a Recursive Path Computation algorithm to compute end-to-end routes through the network.

Claims

1. A method of managing a network comprising a plurality of nodes, the method comprising:

each node maintaining a respective topology database containing topology information of the network within a local region of the node, the local region encompassing a subset of the plurality of nodes of the network; and

the nodes of the network implementing a Recursive Path Computation algorithm to compute end-to-end routes through the network;

wherein implementing a Recursive Path Computation algorithm comprises a first node performing the steps of;

determining whether a destination address is in a respective topology database of the first node;

when the destination address is not in the respective topology database of the first node;

sending a request message to each boundary node of the first node'"'"'s local region, the request message containing the destination address;

receiving a respective reply message from at least one of the boundary nodes, each reply message including path information defining a path from the respective boundary node to the destination address;

for at least one received reply message, calculating a respective candidate path from the first node to the destination address via the respective boundary node; and

selecting, from among the calculated candidate paths, a best path from the first node to the destination address.

2. The method of claim 1 wherein maintaining a respective topology database comprises:

each node implementing a Link State Advertisement (LSA) messaging protocol to exchange topology information of the network, wherein LSA messages have a Time-To-Live (TTL) parameter limiting a maximum number of hops over which the LSA message can be propagated.

3. The method of claim 1 wherein calculating a respective candidate path comprises:

calculating a shortest path from the first node to the respective boundary node; and

appending the calculated shortest path to the path defined by the path information of the received reply message to define the respective candidate path.

4. The method of claim 1 wherein the step of calculating a respective candidate path is only performed for a subset of received reply messages.

5. The method of claim 4 wherein the subset of received reply messages comprises any one or more of:

reply messages received within a predetermined delay period; and

a predetermined number of earliest received reply messages.

6. The method of claim 1 further comprising:

when the destination address is in the respective topology database of the first node, computing a shortest path between the first node and the destination address.

7. The method of claim 1 wherein the first node is a source node of a connection to be set up through the network to the destination address, and wherein the method further comprises setting up the connection using the selected best path.

8. The method of claim 1 wherein the first node is not a source node of a connection to be set up through the network to the destination address, and wherein the method further comprises the first node performing the steps of:

receiving, from a second node, a request message containing the destination address; and

sending, the to second node, a reply message containing path information defining the selected best path.

9. The method of claim 8, wherein the request message contains an identifier, and wherein the method further comprises the first node performing the step of:

discarding the received request message if the identifier matches a respective identifier of a previously received request message.

10. The method of claim 9, wherein the identifier is a path identifier assigned by the source node.

11. The method of claim 8, wherein the request message contains a Time-To-Live (TTL) parameter for limiting a maximum number of iterations of the Recursive Path Computation.

12. The method of claim 8, wherein the request message contains a listing of nodes to which the request message has previously been sent, and wherein, when the destination address is not in the first node'"'"'s topology database, the first node sends its request message to each boundary node of the first node'"'"'s local region except those identified in the listing of nodes to which the request message has previously been sent.

13. A non-transitory computer-readable storage medium comprising software code for execution by a node of a network, the software code controlling the node to perform the steps of:

maintaining a respective topology database containing topology information of the network within a local region of the node, the local region encompassing a subset of the plurality of nodes of the network; and

implementing a Recursive Path Computation algorithm to compute end-to-end routes through the network;

wherein implementing a Recursive Path Computation algorithm comprises a first node performing the steps of;

determining whether a destination address is in a respective topology database of the first node;

when the destination address is not in the respective topology database of the first node;

sending a request message to each boundary node of the first node'"'"'s local region, the request message containing the destination address;

receiving a respective reply message from at least one of the boundary nodes, each reply message including path information defining a path from the respective boundary node to the destination address;

for at least one received reply message, calculating a respective candidate path from the first node to the destination address via the respective boundary node; and

selecting, from among the calculated candidate paths, a best path from the first node to the destination address.

14. A communications network comprising a plurality of nodes, wherein at least one of the nodes is operative to perform the steps of:

maintaining a respective topology database containing topology information of the network within a local region of the node, the local region encompassing a subset of the plurality of nodes of the network; and

implementing a Recursive Path Computation algorithm to compute end-to-end routes through the network;

wherein implementing a Recursive Path Computation algorithm comprises a first node performing the steps of;

determining whether a destination address is in a respective topology database of the first node;

when the destination address is not in the respective topology database of the first node;

sending a request message to each boundary node of the first node'"'"'s local region, the request message containing the destination address;

receiving a respective reply message from at least one of the boundary nodes, each reply message including path information defining a path from the respective boundary node to the destination address;

for at least one received reply message, calculating a respective candidate path from the first node to the destination address via the respective boundary node; and

selecting, from among the calculated candidate paths, a best path from the first node to the destination address.