Centralized link-scope configuration of an internet protocol (IP) network

• US 7,327,695 B2
• Filed: 12/19/2003
• Issued: 02/05/2008
• Est. Priority Date: 12/19/2003
• Status: Expired due to Fees

• Current Assignee: Telefonaktiebolaget LM Ericsson
• Original Assignee: Telefonaktiebolaget LM Ericsson
• Inventors: Gerö, Balázs Peter, Nohl, Attila Rajmund, Tóth, Gábor, Molnar, Gergely
• Primary Examiner(s): Chin; Wellington
• Assistant Examiner(s): Mais; Mark A.
• Application Number:
  US10/742,731
• Publication Number:
  US 20050135274A1
• Time in Patent Office: 1,509 Days
• Field of Search: 370/254, 370/255, 370/256
• US Class Current: 370/255
• CPC Class Codes: H04L 41/0806 for initial configuration or provisioning, e.g. plug-and-play

Abstract

A method of configuring link-scope-type managed objects in IP-based networks from a centralized management node. An IP-based network includes at least one management station, a set of network nodes, and communication links between the network nodes and between the management station and the network nodes. Preferably, an Open Shortest Path First (OSPF) topology graph of the network is prepared, and a set of target links to be configured is identified. The target links are then classified into N disjoint subsets, T₁-T_N. The links in each subset are then configured in parallel, starting with subset T₁ and sequentially handling each subset one-by-one. The target links may be classified by removing non-target links that are not to be configured from the OSPF topology graph, building a LinkGraph to determine the dependencies between the links remaining in the OSPF topology graph, and building a LinkTree from the LinkGraph to classify the target links into the subsets based upon the dependencies between the links.

Claims

1. A method of link-scope configuring an Internet Protocol (IP)-based network having at least one management station, a set of network nodes, and a plurality of communication links between the network nodes and between the management station and the network nodes, said method comprising the steps of:

preparing a topology graph of the network;

identifying a set of target links to be configured;

classifying the target links into N disjoint subsets, T₁-T_N;

establishing a communication connection with network nodes requiring configuration; and

configuring in the network nodes, the links from each subset in parallel, starting with subset T₁ and sequentially handling each subset one-by-one.

2. The method of claim 1, wherein the step of preparing a topology graph includes preparing a topology graph based on the Open Shortest Path First (OSPF) routing protocol, and the step of classifying the target links includes the steps of:

removing from the OSPF topology graph, non-target links that are not to be configured;

determining dependencies between the links remaining in the OSPF topology graph; and

classifying the target links into the subsets based upon the dependencies between the links.

3. The method of claim 2, wherein the step of determining dependencies between the links includes building a LinkGraph, said step of building a LinkGraph including the steps of:

for each target link in the OSPF topology graph, placing a new node in the LinkGraph;

for each node placed in the LinkGraph, creating a full mesh of neighboring nodes from the OSPF topology graph;

adding to the LinkGraph, a node representing the management station in the OSPF topology graph; and

connecting the node representing the management station to the links that originated from the management station in the OSPF topology graph.

4. A method of link-scope configuring an Internet Protocol (IP)-based network having at least one management station, a set of network nodes, and a plurality of communication links between the network nodes and between the management station and the network nodes, said method comprising the steps of:

preparing a topology graph of the network based on the Open Shortest Path First (OSPF) routing protocol;

identifying a set of target links to be configured;

classifying the target links into N disjoint subsets, T₁-T_N, said classifying step including removing from the OSPF topology graph, non-target links that are not to be configured;

determining dependencies between the links remaining in the OSPF topology graph; and

classifying the target links into the subsets based upon the dependencies between the links;

establishing a communication connection with network nodes requiring configuration; and

configuring in the network nodes, the links from each subset in parallel, starting with subset T₁ and sequentially handling each subset one-by-one;

wherein the step of determining dependencies between the links includes building a LinkGraph through the steps of;

for each target link in the OSPF topology graph, placing a new node in the LinkGraph;

for each node placed in the LinkGraph, creating a full mesh of neighboring nodes from the OSPF topology graph;

adding to the LinkGraph, a node representing the management station in the OSPF topology graph; and

connecting the node representing the management station to the links that originated from the management station in the OSPF topology graph; and

wherein the step of classifying the target links into the subsets based upon the dependencies between the links includes building a LinkTree from the LinkGraph, said step of building a LinkTree including the steps of;

(a) designating the node representing the management station as a first starting point;

(b) adding to the LinkTree, all of the links connecting the first starting point to nodes adjacent to the first starting point;

(c) selecting a node adjacent to the first starting point, said step of selecting an adjacent node including the steps of;

(c)(1) selecting as a second starting point, an adjacent node having the largest number of neighboring nodes that are not yet added to the LinkTree, if there is an adjacent node with more neighboring nodes than any other adjacent node; and

(c)(2) if more than one adjacent node have the largest number of neighboring nodes that are not yet added to the LinkTree, arbitrarily selecting as the second starting point, an adjacent node from the adjacent nodes having the largest number of neighboring nodes;

(d) adding to the LinkTree, all of the links originating from the second starting point, except for links already in the LinkTree;

(e) selecting as a third starting point, a node in the LinkTree, said step of selecting a node in the LinkTree including the steps of;

(e)(1) selecting a node in the LinkTree having the largest number of neighboring nodes that are not yet added to the LinkTree, if there is a node in the LinkTree with more neighboring nodes than any other node;

(e)(2) if more than one node have the largest number of neighboring nodes that are not yet added to the LinkTree, selecting as the third starting point, a node from the nodes having the largest number of neighboring nodes that is the farthest from the first starting point; and

(e)(3) if more than one node have the largest number of neighboring nodes that are not yet added to the LinkTree, and all of the nodes having the largest number of neighboring nodes are the same distance from the first starting point, arbitrarily selecting as the third starting point, a node from the nodes having the largest number of neighboring nodes;

(f) adding to the LinkTree, all of the links originating from the third starting point, except for links already in the LinkTree;

(g) determining whether all of the nodes of the LinkGraph have been added to the LinkTree;

(h) if all of the nodes of the LinkGraph have been added to the LinkTree, classifying all of the links in the LinkTree into a disjoint subset T_i.

5. The method of claim 4, further comprising the steps of:

determining whether there are any target links that did not get added to the LinkTree;

if there are target links that did not get added to the LinkTree, creating a link subgraph comprising the target links that did not get added to the LinkTree; and

repeating steps (a) through (h) to create a disjoint subset T<sub>i −

1</sub>.

6. The method of claim 5, wherein the step of configuring the links from each subset in parallel includes the steps of:

constructing in the OSPF topology graph, a skeleton comprising the non-target links not being configured; and

configuring in parallel, the nodes for all target links at the same level, provided that the last-configured node is in the skeleton.

7. A management station for link-scope configuring an Internet Protocol (IP)-based network having a set of network nodes, and a plurality of communication links between the network nodes and between the management station and the network nodes, said management station comprising:

means for preparing a topology graph of the network;

means for identifying a set of target links to be configured;

means for classifying the target links into N disjoint subsets, T₁-T_N;

means for establishing a communication connection with network nodes requiring configuration; and

means for configuring in the network nodes, the links from each subset in parallel, starting with subset T₁ and sequentially handling each subset one-by-one.

8. The management station of claim 7, wherein the means for preparing a topology graph includes means for preparing a topology graph based on the Open Shortest Path First (OSPF) routing protocol.

9. The management station of claim 8, wherein the means for classifying the target links includes:

means for removing from the OSPF topology graph, non-target links that are not to be configured;

means for determining dependencies between the links remaining in the OSPF topology graph; and

means for classifying the target links into the subsets based upon the dependencies between the links.