Constraining topology size and recursively calculating routes in large networks
First Claim
Patent Images
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.
6 Assignments
0 Petitions
Accused Products
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.
-
Citations
14 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
-
-
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.
-
Specification