Method for designing or routing a self-healing ring in a communications network and a self-healing ring routed in accordance with the method

• US 5,923,646 A
• Filed: 08/30/1996
• Issued: 07/13/1999
• Est. Priority Date: 08/30/1996
• Status: Expired due to Term

• Current Assignee: Verizon Patent and Licensing Incorporated (Verizon Communications Inc.)
• Original Assignee: Nynex Science & Technology
• Inventors: Mandhyan, Indur B.
• Primary Examiner(s): Pham, Chi H.
• Assistant Examiner(s): NGUYEN, STEVEN H D
• Application Number:
  US08/705,953
• Time in Patent Office: 1,047 Days
• Field of Search: 370/254, 370/256-258, 370/400-406, 370/216, 370/224
• US Class Current: 370/254
• CPC Class Codes: H04J 2203/006 Fault tolerance and recovery
• CPC Class Codes: H04J 3/085 for ring networks, e.g. SDH/SONET rings, self-healing rings, meashed SDH/SONET networks
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• 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/48 Routing tree calculation
• CPC Class Codes: H04L 45/488 using root node determination

Abstract

A method for finding or routing a ring containing predetermined ring offices of a communications network while minimizing costs of communications channels used to route the ring. The ring may be a self-healing ring, the communications channels may be optical communications channels, the costs may be fiber transport costs and the network may be a SONET network.

Claims

1. A method for routing a ring in a network having a plurality of nodes, at least two of the plurality of nodes being ring nodes which are part of the ring, and a plurality of communications channels interconnecting the plurality of nodes, each of the plurality of communications channels. having an associated cost, the method comprising steps of:

a) assigning a vertex corresponding to each of the nodes and assigning a ring vertex corresponding to each of the ring nodes;

b) assigning a link having an associated distance to each of the communications channels having an associated cost such that each of the link distances correspond to the cost of each of the communications channels;

c) forming a tree having tree nodes corresponding to the ring vertices and edges connecting the tree nodes wherein the edges are labeled by communications channels in the network and wherein the costs of the communications channels between the ring offices corresponding to the tree nodes are minimized;

d) forming a directed tree from the tree by choosing an arbitrary leaf node of the tree as a root node;

e) traversing the directed tree, in a depth first manner, to determine whether a cycle, in the graph, containing the tree nodes exists; and

f) if a cycle in the graph exists, routing a ring through the ring nodes of the network, the ring being determined by the cycle in the graph.

2. The method of claim 1 further comprising steps of:

g) if a cycle does not exist, determining whether any other leaf nodes exist;

h) if other leaf nodes exist,

i) forming a new directed tree by assigning an arbitrary one of the other leaf nodes as a root node;

ii) traversing the new directed tree, in a depth first manner, to determine whether a cycle, in the graph, containing the tree nodes exists; and

iii) if a cycle in the graph exists, routing a ring through the ring nodes of the network, the ring being determined by the cycle in the graph.

3. The method of claim 2 further comprising steps of:

h) if other leaf nodes do not exist,

i) determining whether other trees exist, and if other trees are determined to exist;

A) forming a new tree having new tree nodes corresponding to the ring vertices and edges;

B) forming a directed new tree from the new tree by choosing an arbitrary leaf node of the tree as a root node;

C) traversing the directed new tree, in a depth first manner, to determine whether a cycle, in the graph, containing the new tree nodes exists; and

D) if a cycle in the graph exists, routing a ring through the ring nodes of the network, the ring being determined by the cycle in the graph.

4. The method of claim 1 wherein the nodes are central offices.

5. The method of claim 1 wherein the nodes are add/drop multiplexers.

6. The method of claim 1 wherein the costs associated with the plurality of communications channels include:

equipment costs; and

optical fiber costs.

7. The method of claim 6 wherein the costs associated with the plurality of communications channels further include:

leasing costs.

8. The method of claim 6 wherein the costs associated with the plurality of communications channels further include:

line maintenance costs.

9. The method of claim 6 wherein the costs associated with the plurality of communications channels further include:

installation costs.

10. The method of claim 1 wherein the step of forming a tree includes sub-steps of:

i) selecting an initial tree node corresponding to an arbitrary ring vertex;

ii) selecting a tree node corresponding to a ring vertex having a shortest path, including only unused links and unused vertices, with the arbitrary ring vertex;

iii) selecting a tree node corresponding to a ring vertex having a shortest path, including only unused links and unused vertices, with any ring vertices corresponding to any selected tree nodes; and

iv) repeating sub-step (iii) until no ring vertices are left.

11. The method of claim 10 further comprising steps of:

v) if a cycle does not exist, determining whether any other leaf nodes exist;

vi) if other leaf nodes exist,

A) forming a new directed tree by assigning an arbitrary one of the other leaf nodes as a root node;

B) traversing the new directed tree, in a depth first manner, to determine whether a cycle, in the graph, containing the tree nodes exists; and

C) if a cycle in the graph exists, routing a ring through the ring nodes of the network, the ring being determined by the cycle in the graph.

12. The method of claim 11 further comprising steps of:

vi) if other leaf nodes do not exist,

A) determining whether other trees exist, and if other trees are determined to exist;

1) forming a new tree having new tree nodes corresponding to the ring vertices and edges;

2) forming a directed new tree from the new tree by choosing an arbitrary leaf node of the tree as a root node;

3) traversing the directed new tree, in a depth first manner, to determine whether a cycle, in the graph, containing the new tree nodes exists; and

4) if a cycle in the graph exists, routing a ring through the ring nodes of the network, the ring being determined by the cycle in the graph.

13. The method of claim 12 wherein the new tree is formed starting at the same root node and selecting sub-optimal paths between the tree nodes.

14. The method of claim 12 wherein the new tree is formed by selecting another leaf node as the root node.

15. The method of claim 10 wherein the nodes are central offices.

16. The method of claim 10 wherein the nodes are add/drop multiplexers.

17. The method of claim 10 wherein the costs associated with the plurality of communications channels include:

equipment costs; and

optical fiber costs.

18. The method of claim 17 wherein the costs associated with the plurality of communications channels further include:

leasing costs.

19. The method of claim 17 wherein the costs associated with the plurality of communications channels further include:

line maintenance costs.

20. The method of claim 17 wherein the costs associated with the plurality of communications channels further include:

installation costs.

21. A self-healing ring including ring nodes in a network having a plurality of nodes, a plurality of communications channels interconnecting the plurality of nodes, each of the plurality of communications channels having an associated cost, wherein the ring nodes of the self-healing ring are selected by:

a) assigning a vertex corresponding to each of the nodes and assigning a ring vertex corresponding to each of the ring nodes;

b) assigning a link having an associated distance to each of the communications channels having an associated cost such that each of the link distances correspond to the cost each of the communications channels;

c) forming a tree having tree nodes corresponding to the ring vertices and edges connecting the tree nodes wherein the edges are labeled by communications channels in the network and wherein the costs of the communications channels between the ring offices corresponding to the tree nodes are minimized;

d) forming a directed tree from the tree by choosing an arbitrary leaf node of the tree as a root node;

e) traversing the directed tree, in a depth first manner, to determine whether a cycle, in the graph, containing the tree nodes exists; and

f) if a cycle in the graph exists, routing a ring through the ring nodes of the network, the ring being determined by the cycle in the graph.