Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1997-07-11
2002-07-16
Chin, Wellington (Department: 2664)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S227000, C714S004110
Reexamination Certificate
active
06421349
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to methods for restoring networks of spans, for example telecommunications networks, upon the occurrence of a failure of one of the spans or nodes of the network.
BACKGROUND OF THE INVENTION
Methods for the restoration of digital transport networks have been studied for several years. Some researchers have concluded that distributed real-time protocols may operate too slowly to meet operational objectives, such as the 2 second call-dropping threshold in voice networks. This problem can be overcome by preparing the network for anticipated failures by optimally preconfiguring resources which will be used to react to the failure. This places the network into a state of “best readiness” to face a given set of anticipated failures. See W. D. Grover and M. H. MacGregor, “Potential for spare capacity preconnection to reduce crossconnection workloads in mesh-restorable networks”, Electronics Letters, Vol. 30, No. 3, pp. 194-195, Feb. 3, 1994. By contrast, M. Herzberg and. S. J. Bye, “An optimal spare-capacity assignment model for survivable networks with hop limits”, Proceedings of IEEE Globecom '94, Vol. 3, pp. 1601-1606, IEEE, 1994 deals with the problem of optimum spare capacity amount determination, but does not pre-configure such spares.
The tremendous interest in real-time network restoration over the last few years is evidence both of the importance and difficulty of this problem. Evidence has been mounting that it may not always be possible to meet operational requirements with real-time techniques. The suggested cures have ranged from high speed, parallel computing architectures for digital crossconnect machines to simplified network architectures where restoration can be made to occur more quickly in real-time. The proposal of Grover and MacGregor suggests anticipating failures, and preconfiguring the network to handle them so that real-time computation or reaction delay (one or both) is not required except at the endpoints of the failure. Thus, preconfiguration methods apply where computing a reaction or implementing it (or both) is/are too lengthy a process.
One of the inventors has previously disclosed, in Canadian patent application no. 2,161,847 published May 1, 1997, a method for restoring traffic in a network in which the network is pre-configured for span restoration. The network includes plural distinct nodes interconnected by plural distinct spans, each span having working links and spare links. Each node has a digital cross-connect switch for making and breaking connections between links in adjacent spans forming paths or path segments (span pairs) through nodes. In a broad characterization of the method, there are three steps.
Step 1: For each of at least two possible span failures, (a) find the number of restoration routes available in case of the occurrence of each span failure, (b) determine the resources used by each restoration route, and (c) determine the amount of flow to be restored for each span failure.
Step 2: find, in a computer, the amount of flow f
p
to be restored along each restoration route that minimizes total unrestored flow for all possible span failures identified in step 1.
Step 3: form connections at each digital cross-connect switch in the network along each restoration route before occurrence of one of the possible span failures identified in step 1 to permit the amount of flow f
p
determined in step 2 to be carried by each respective restoration route upon the occurrence of one of the possible span failures identified in step 1.
PC-restoration design may be generated using trees and unconstrained patterns of genetic algorithm techniques. These approaches have a practical drawback in that there is no constraint on the nodal degrees that a pattern can have (other than the degrees of the underlying nodes.)
The inventor has also proposed, in U.S. Pat. No. 4,956,835, issued Sep. 11, 1990, a method and apparatus of restoring communications between a pair of nodes in a network having an arbitrary number of nodes and an arbitrary number of spans interconnecting the nodes. Each span has working circuits between nodes designated for transmitting actual communications traffic and spare circuits capable of, but not designated for, transmitting actual communications traffic. The method comprises the steps of (a) establishing one or more independent communication paths between the pair of nodes through a series of spare circuits of spans interconnecting the pair of nodes and other interconnected nodes in the network; and (b) redirecting communications traffic intended for one or more failed spans interconnecting the pair of nodes through one or more of the paths. However, self-healing networks operating pursuant to the method described in U.S. Pat. No. 4,956,835 are reactive in that the establishment of a communications path occurs only after the occurrence of a span failure, or in response to a demand for additional capacity. In addition, the self-healing network utilizes distinct end nodes for the initiation of a broadcast of signatures and initiating construction of a restoration path. Further, the self-healing network utilizes the broadcast of signatures that in themselves do not contain the information required to construct the restoration path.
There also has been proposed, in order to enhance survivability of networks, the concept of self-healing rings (Wu, “Fiber Network Service Survivability”, Boston, USA, 1992, in particular, Ch. 4). In a self-healing ring, nodes are interconnected by spans organized into rings. Each span includes working links and spare links. Add-drop multiplexers (ADMs) at the nodes react to a span failure on the ring to restore a communications path in one of two ways. If only a working link is lost, communications may be restored along the same span by dropping the working link and adding a spare link on that span. If an entire span is lost, communications may be restored by re-routing traffic in the opposite direction around the ring, using either working or spare links in the ring.
Self-healing rings only protect the spans on the ring itself and provide at most one restoration route per failure. In addition, protection paths of one ring overlapping a span are only available to failed working spans in the same ring. A working path routing must be realized by a succession of ring-arc tranversals and ring to ring transfers. Each ring functions on its own in its as built configuration.
SUMMARY OF THE INVENTION
There is proposed a method that overcomes disadvantages in these aforementioned network restoration schemes. Therefore, in accordance with one aspect of the invention, there is proposed a method of operating a telecommunications network in which the telecommunications network includes plural distinct nodes interconnected by plural distinct spans, each node having a digital cross-connect switch for making and breaking connections between links in adjacent spans forming span paths through the node, the method comprising the steps of:
a) providing a set of successive nodes capable of forming a closed path in the network, with at least one spare link between each pair of adjacent nodes in the closed path;
b) forming a cross-connection at each node in the closed path to connect spare links in each of the adjacent spans lying in the closed path and thus form a span path through each node in the closed path.
By configuration of the controller of the digital cross-connect switch at a node, upon occurrence of a span failure on any span between any two nodes in the closed path, wherein the span failure is not at a span in the closed path, telecommunications traffic may be routed along the closed path.
Preferably, according to an aspect of the invention, providing a set of successive nodes capable of forming a closed path comprises:
(a1) selecting an originating node; and
(a2) searching for and identifying a set of intermediate nodes that, together with the originating node, may form a closed path having at least one spare link between each pair of adjacent nodes in the clo
Chin Wellington
Lambert Anthony R.
Nguyen Steven
Telecommunications Research Laboratories
LandOfFree
Distributed preconfiguration of spare capacity in closed... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Distributed preconfiguration of spare capacity in closed..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Distributed preconfiguration of spare capacity in closed... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2907906