Method of Optimizing Routing of Demands in a Network
First Claim
1. A method of optimizing routing of demands in a network comprising nodes interconnected by links, each demand comprising a source node, a destination node and at least one demand parameter requirement, the method comprising:
- a) partitioning nodes and links of a network into a set of clusters of links and nodes;
b) imposing a hierarchical tree structure on the set of clusters such that any pair of clusters has a unique path between them via a closest common ancestor;
c) determining optimum paths for all demands such that the paths meet the at least one demand parameter requirement by processing the demands in each cluster only after all descendent clusters in the hierarchical tree structure have been processed, the processing for each cluster comprising;
i. splitting each demand into an intra-cluster demand in which the source and destination nodes are in the same cluster and, if appropriate, an inter-cluster demand in which the source and destination nodes are in different clusters;
ii. determining optimum paths for all intra-cluster demands so as to meet the at least one demand parameter requirement; and
iii. passing all inter-cluster demands upwards to the next cluster in the hierarchical tree structure to be processed as a demand therein.
1 Assignment
0 Petitions
Accused Products
Abstract
The present invention relates to a method for optimization of demands in a packet switched communication network, especially, though not exclusively, for the optimization of demands in a Multi Protocol Label Switching (MPLS) packet switched communication network. The present invention provides a method to enable network nodes, such as routers to be clustered into components, with the components organised in a hierarchical fashion, and with the network “core” at the root of this hierarchy. Demands that originate or terminate at components outside the core, but that traverse the core, are temporarily replaced by demands that originate and terminate within the core component. Having optimized the resulting set of demands it is then shown how to use the solution to satisfy the original demands. Multi-access networks cause some complications, and these are taken into account. Also, further demand replacement methods have been developed that take into account complex access situations, In particular, as mentioned, the case has been considered, where there is an existing partitioning of the routers, e.g. into core and access routers, which needs to be respected.
-
Citations
8 Claims
-
1. A method of optimizing routing of demands in a network comprising nodes interconnected by links, each demand comprising a source node, a destination node and at least one demand parameter requirement, the method comprising:
-
a) partitioning nodes and links of a network into a set of clusters of links and nodes; b) imposing a hierarchical tree structure on the set of clusters such that any pair of clusters has a unique path between them via a closest common ancestor; c) determining optimum paths for all demands such that the paths meet the at least one demand parameter requirement by processing the demands in each cluster only after all descendent clusters in the hierarchical tree structure have been processed, the processing for each cluster comprising; i. splitting each demand into an intra-cluster demand in which the source and destination nodes are in the same cluster and, if appropriate, an inter-cluster demand in which the source and destination nodes are in different clusters; ii. determining optimum paths for all intra-cluster demands so as to meet the at least one demand parameter requirement; and iii. passing all inter-cluster demands upwards to the next cluster in the hierarchical tree structure to be processed as a demand therein. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. A demand optimizer for optimizing routing of demands in a network comprising nodes interconnected by links, the demand optimizer comprising:
-
an input handler for receiving details of the network structure and demands to be optimized; a memory for storing the details of the network structure and demands; and a network structure analyser coupled to the memory configured to analyze the network by; partitioning nodes and links of a network into a set of clusters of links and nodes; imposing a hierarchical tree structure on the set of clusters such that any pair of clusters has a unique path between them via a closest common ancestor; determining optimum paths for all demands such that the paths meet the at least one demand parameter requirement by processing the demands in each cluster only after all descendent clusters in the hierarchical tree structure have been processed, the processing for each cluster comprising; splitting each demand into an intra-cluster demand in which the source and destination nodes are in the same cluster and, if appropriate, an inter-cluster demand in which the source and destination nodes are in different clusters; determining optimum paths for all intra-cluster demands so as to meet the at least one demand Parameter requirement; and passing all inter-cluster demands upwards to the next cluster in the hierarchical tree structure to be processed as a demand therein.
-
Specification