Method and apparatus for determining maximum network failure spans forrestoration

• US 5,881,048 A
• Filed: 11/25/1996
• Issued: 03/09/1999
• Est. Priority Date: 11/25/1996
• Status: Expired due to Term

• Current Assignee: Verizon Patent and Licensing Incorporated (Verizon Communications Inc.)
• Original Assignee: MCI Communications Corporation (Verizon Communications Inc.)
• Inventors: Croslin, William D.
• Primary Examiner(s): HSU, ALPUS
• Application Number:
  US08/758,111
• Time in Patent Office: 834 Days
• Field of Search: 370/217, 370/218, 370/225, 370/228, 370/254, 370/258, 340/825.01, 340/825.03, 340/826, 340/827, 379/220, 379/221, 379/271, 379/272, 379/273, 395/181, 395/182.01, 395/182.02, 395/183.01, 395/183.16, 395/183.19, 395/200.68, 395/200.69
• US Class Current: 370/228
• CPC Class Codes: H04Q 2213/13103 Memory
• CPC Class Codes: H04Q 2213/13106 Microprocessor, CPU
• CPC Class Codes: H04Q 2213/13109 Initializing, personal profile
• CPC Class Codes: H04Q 2213/13166 Fault prevention
• CPC Class Codes: H04Q 2213/13167 Redundant apparatus
• CPC Class Codes: H04Q 2213/13204 Protocols
• CPC Class Codes: H04Q 2213/13349 Network management
• CPC Class Codes: H04Q 2213/13521 fault management
• CPC Class Codes: H04Q 2213/13565 restoration, e.g. disaster recovery, self-healing networks
• CPC Class Codes: H04Q 3/0079 involving restoration of networks, e.g. disaster recovery, self-healing networks

Abstract

A method and apparatus for analyzing a telecommunications network and providing data based on such analysis first receives physical topology data for the network based on nodes and their connections in the network. Thereafter, the method and apparatus identify several inter-node configurations in the network. Preferably, the method and apparatus identify six inter-node configurations: stranded network non-rings, non-ring network spurs, stranded network rings, spur nodes with path diversity, network segments with pass-through nodes, and network segments without pass-through nodes. From these six identified inter-node configurations, the method and apparatus identify failure spans or maximum lengths in a network that can be singularly restored. As a result, the six identified inter-node configurations or failure spans can be employed to reduce the processing time required under network restoration systems, and thus can be used to minimize the time required to isolate a failure and generate a restoral route in the network.

Claims

1. In a telecommunication network having a plurality of nodes interconnected by links, a computer-implemented method for analyzing the network comprising the steps of:

receiving physical network data for each of the plurality of nodes and links intercoupling the nodes;

identifying stranded network non-rings in the network based on the physical network data;

determining a maximum restoration span for failures in any identified stranded network non-rings in the network;

identifying non-ring network spurs in the network based on the physical network data;

determining a maximum restoration span for failures in any identified non-ring network spurs in the network;

identifying stranded network rings in the network based on the physical network data;

determining a maximum restoration span for failures in any identified stranded network rings in the network;

identifying network spur nodes with diversity in the network based on the physical network data, the spur nodes with diversity having a plurality of geographically diverse paths from the spur node to a remainder of the network;

determining a maximum restoration span for failures in any identified network spur nodes with diversity in the network;

identifying network segments with pass-through nodes in the network based on the physical network data;

determining a maximum restoration span for failures in any identified network segments with pass-through nodes in the network;

identifying network segments without pass-through nodes in the network based on the physical network data;

determining a maximum restoration span for failures in any identified network segments without pass-through nodes in the network; and

outputting data reflecting the maximum restoration spans.

2. The method of claim 1 wherein the step of identifying stranded network non-rings includes the steps of:

selecting a node having only one link from the physical network data;

locating at least one node having two links from the physical network data, the at least one located node being linked with the selected node; and

identifying a node having not greater than two links from the physical network data, the identified node being linked to the at least one located node,

and wherein the step of determining a maximum restoration span for failures in any identified stranded network non-rings includes identifying the maximum restoration span as extending from the selected node to the identified node.

3. The method of claim 1 wherein the step of identifying non-ring network spurs includes the steps of:

selecting a node having only one link from the physical network data;

locating any nodes having not greater than two links from the physical network data, each located node being linked with the selected node or with one of the located nodes; and

identifying a node having greater than two links from the physical network data, the identified node being linked to one of the located nodes,

and wherein the step of determining a maximum restoration span for failures in any identified non-ring network spurs includes identifying the maximum restoration span as extending from the selected node to the identified node.

4. The method of claim 1 wherein the step of identifying stranded network rings includes the steps of:

selecting a node having only two links from the physical network data;

locating at least one node having not greater than two links from the physical network data, each located node being linked with the selected node or with one of the located nodes; and

identifying a node from the located nodes that is identical to the selected node,

and wherein the step of determining a maximum restoration span for failures in any identified stranded network rings includes identifying the maximum restoration span as extending from the selected node to the identified node.

5. The method of claim 1 wherein the step of identifying network spur nodes includes the steps of:

selecting a node having two or more links from the physical network data; and

determining if the two or more links from the selected node are all coupled to a second node,

and wherein the step of determining a maximum restoration span for failures in any identified network spur nodes includes identifying the maximum restoration span as extending from the selected node to the second node.

6. The method of claim 1 wherein the step of identifying network segments with pass-through nodes includes the steps of:

selecting a node having two links from the physical network data;

locating all nodes having not greater than two links in a first direction from the physical network data, each located node in the first direction being linked with the selected node or with one of the located nodes and not having any terminating trunks thereat;

identifying a node having greater than two links from the physical network data, the identified node being linked to at least one located node;

locating any node having not greater than two links in a second direction from the physical network data, the any located node in the second direction being linked with the selected node and not having any terminating trunks thereat; and

determining a node having greater than two links from the physical network data, the identified node being linked to at least one located node in the second direction;

and wherein the step of determining a maximum restoration span for failures in any identified network segments with pass-through nodes includes identifying the maximum restoration span as extending from the identified node to the determined node.

7. The method of claim 1 wherein the step of identifying network segments without pass-through nodes includes the steps of:

selecting a node having greater than two links from the physical network data; and

locating a node having greater than two links from the physical network data, the located node being linked with the selected node,

and wherein the step of determining a maximum restoration span for failures in any network segments without pass-through nodes includes identifying the maximum restoration span as extending from the selected node to the located node.

8. The method of claim 1 wherein the step of receiving physical network data includes receiving network data for only DS-3 telecommunication links in the network.

9. The method of claim 1, further comprising the step of developing a plurality of network restoration plans based on at least some of the determined maximum restoration spans, wherein each restoration plan includes rerouting instructions for the network to compensate for a disruption of one of the links in the network.

22. The apparatus of claim 2 wherein the computer system:

(a) selects a first node having a selected number of paths from the network data;

(b) locates a second node having a predetermined number of paths from the network data, the second node being coupled with the selected node;

(c) identifies a third node having a preselected number of paths from the network data, the third node being coupled to the second node; and

(d) determines a maximum span as extending from the third node to the first node.

23. The apparatus of claim 2 wherein the computer system:

(a) selects a node having two or more paths from the network data;

(b) determines if the two or more paths from the selected node are all coupled to a second node; and

(c) determines a maximum span as extending from the selected node to the second node.

10. In a network having a plurality of communication paths coupling a plurality of nodes, a computer-implemented method for analyzing the network comprising the steps of:

receiving network data for each of the plurality of nodes and paths intercoupling the nodes;

identifying a plurality of inter-node configurations based on the received network data;

determining a plurality of network spans from the identified inter-node configurations in the network; and

outputting data of the plurality of network spans, and wherein the network data includes physical network topology data, and wherein the step of identifying a plurality of inter-node configurations includes locating stranded network non-rings, non-ring network spurs, stranded network rings, network spur nodes with diversity, network segments with pass-through nodes and network segments without pass-through nodes in the network from the network data.

11. The method of claim 10 wherein the plurality of communication paths in the network include communication paths having greater and lesser bandwidth, and wherein the step of receiving network data includes receiving network data for only the paths having the greater bandwidth.

12. The method of claim 10 wherein the step of identifying a plurality of inter-node configurations includes the steps of:

selecting a first node having a selected number of paths from the network data;

locating a second node having a predetermined number of paths from the network data, the second node being coupled with the selected node; and

identifying a third node having a preselected number of paths from the network data, the third node being coupled to the second node,

and wherein the step of determining a plurality of network spans includes identifying a maximum span as extending from the third node to the first node.

13. The method of claim 10 wherein the step of identifying a plurality of inter-node configurations includes the steps of:

selecting a node having only one path from the network data;

locating at least one node having two paths from the network data, the at least one located node being coupled with the selected node; and

identifying a node having not greater than two paths from the network data, the identified node being coupled to the at least one located node,

and wherein the step of determining a plurality of network spans includes determining a maximum span as extending from the selected node to the identified node.

14. The method of claim 10 wherein the step of identifying a plurality of inter-node configurations includes the steps of:

selecting a node having only one path from the network data;

locating any nodes having not greater than two paths from the network data, each located node being coupled with the selected node or with one of the located nodes; and

identifying a node having greater than two paths from the network data, the identified node being coupled to one of the located nodes,

and wherein the step of determining a plurality of network spans includes determining a maximum span as extending from the selected node to the identified node.

15. The method of claim 10 wherein the step of identifying a plurality of inter-node configurations includes the steps of:

selecting a node having only one path from the network data;

locating at least one node having not greater than two paths from the network data, each located node being coupled with the selected node or with one of the located nodes; and

identifying a node from the located nodes that is identical to the selected node,

and wherein the step of determining a plurality of network spans includes determining a maximum span as extending from the selected node to the identified node.

16. The method of claim 10 wherein the step of identifying a plurality of inter-node configurations includes the steps of:

selecting a node having two or more paths from the network data; and

determining if the two or more paths from the selected node are all coupled to a second node,

and wherein the step of determining a plurality of network spans includes determining a maximum span as extending from the selected node to the second node.

17. The method of claim 10 wherein the step of identifying a plurality of inter-node configurations includes the steps of:

selecting, from the network data, an end node adjacent to a node having only two paths;

locating all nodes, including the adjacent node, having not greater than two paths from the network data, at least one located node being coupled with the selected node and not having any terminating trunks thereat; and

identifying a node having greater than two paths from the network data, the identified node being coupled to at least one located node;

and wherein the step of determining a plurality of network spans includes determining a maximum span as extending from the end node to the identified node.

18. The method of claim 10 wherein the step of identifying a plurality of inter-node configurations includes the steps of:

selecting a node having greater than two paths from the network data; and

locating a node having greater than two paths from the network data, the located node being coupled with the selected node,

and wherein the step of determining a plurality of network spans includes determining a maximum span as extending from the selected node to the located node.

19. The method of claim 10, further comprising the step of developing a plurality of network restoration plans based on the determined plurality of network spans.

20. The method of claim 10, further comprising the steps of:

receiving a plurality of alarms from at least one of the plurality of nodes in the network; and

identifying a location of a failure in the network based on the determined plurality of network spans.

21. In a network having a plurality of communication paths coupling a plurality of nodes, an apparatus comprising:

a storage device having stored therein network data regarding each of the plurality of nodes and paths inter-coupling the nodes; and

a computer system coupled to the storage device, the computer system receiving the network data, identifying a plurality of categories of inter-node configurations based on the received network data, and determining a plurality of network spans from the identified inter-node configurations in the network, and wherein the network data includes physical network topology data, and wherein the computer system identifies a plurality of different inter-node configurations, including stranded network non-rings, non-ring network spurs, stranded network rings, network spur nodes with diversity, network segments with pass-through nodes and network segments without pass-through nodes in the network from the network data.

24. The apparatus of claim 21 wherein the computer system (a) selects from the network data an end node adjacent to a node having only two paths;

(b) locates all nodes, including the adjacent node, having not greater than two paths from the network data, at least one located node being coupled with the selected node and not having any terminating trunks thereat;

(c) identifies a node having greater than two paths from the network data, the identified node being coupled to at least one located node; and

(d) determines a maximum span as extending from the end node to the identified node.

25. In a network having a plurality of communication paths coupling a plurality of nodes, an apparatus for analyzing the network comprising:

means for receiving network data for each of the plurality of nodes and paths inter-coupling the nodes;

means, coupled to the means for receiving, for identifying a plurality of inter-node configurations based on the received network data; and

means, coupled to the means for identifying, for determining a plurality of network spans from the identified inter-node configurations in the network, and wherein the means for identifying a plurality of inter-node configurations includes means for locating stranded network non-rings, non-ring network spurs, stranded network rings, network spur nodes with diversity, network segments with pass-through nodes and network segments without pass-through nodes in the network from the network data.

26. The apparatus of claim 25 wherein the means for identifying a plurality of inter-node configurations includes:

means for selecting a first node having a selected number of paths from the network data;

means, coupled to the means for selecting, for locating a second node having a predetermined number of paths from the network data, the second node being coupled to the selected node; and

means, coupled to the means for locating, for finding a third node having a preselected number of paths from the network data, the third node being coupled to the second node,

and wherein the means for determining a plurality of network spans identifies a maximum span as extending from the third node to the first node.

27. The apparatus of claim 25 wherein the means for identifying a plurality of inter-node configurations includes:

means for selecting, from the network data, an end node adjacent to a node having only two paths;

means, coupled to the means for selecting, for locating all nodes, including the adjacent node, having not greater than two paths from the network data, at least one located node being coupled with the selected node and not having any terminating trunks thereat; and

means, coupled to the means for locating, for finding a node having greater than two paths from the network data, the identified node being coupled to at least one located node;

and wherein the means for determining a plurality of network spans determines a maximum span as extending from the end node to the identified node.