Path restoration of networks

Details Path restoration of networks Path restoration of networks

1997-10-20

2002-04-23

Nguyen, Chau (Department: 2739)

Multiplex communications

Fault recovery

Bypass an inoperative channel

C370S228000, C370S255000, C370S400000, C709S239000

Reexamination Certificate

active

06377543

ABSTRACT:

FIELD OF THE INVENTION
This invention relates to methods for establishing or restoring communications paths in networks, for example telecommunications networks, particularly upon the occurrence of a failure of one of the spans or nodes of the network.
BACKGROUND OF THE INVENTION
The development of Digital Crossconnect Systems (DCS), and networks with physically diverse routes, promotes the use of mesh restoration. DCS machines are in many respects similar to a computer, and a transport network consisting of Digital Crossconnects is similar in many respects to a distributed multiprocessor. Mesh-based survivable or restorable network architectures exploit the intelligence of a DCS-based transport network to minimize the amount of spare capacity required to protect working demands. See: Bates, B., Gregory, D., Voice and Data Communications Handbook, New York, NY: McGraw-Hill Inc., 1996, Barezzani, M., Pedrinelli, E., Gerla, M., “Protection planning in transmission networks”, Proc. IEEE ICC'92, 1992, pp. 316.4.1-316.4.5. Chao, C. W., Fuoco, G., Kropfl, D., “FASTAR platform gives the network a competitive edge”, AT & T Technical Journal, July/August 1994, pp. 69-81. Chng, R. S. K., Botham, C. P., Johnson, D., Brown, G. N., Sinclair, M. C., O'Mahony, M. J. Hawker, I., “A multi-layer restoration strategy for reconfigurable networks”, Proc. IEEE Globecom '94, December 1994, pp. 1872-1878. Chujo, T., Komine, H., Miyazaki, K., Ogura, T., Soejima, T., “Distributed self-healing network and its optimum spare capacity assignment algorithm”, Electronics and Communications in Japan, part 1, vol. 74, no. 7, 1991, pp. 1-8. Coan, B. A., Vecchi, M. P., Wu, L. T., “A distributed protocol to improve the survivability of trunk networks”, Proceedings of the 13th International Switching Symposium, May 1990, pp. 173-179. Coan, B. A., et al., “Using distributed topology updates and preplanned configurations to achieve trunk network survivability”, IEEE Transaction on Reliability, vol. 40, no. 4, 1991, pp. 404-416. Davis, L., Cox, A., Qiu, Y., “A Genetic Algorithm for Survivable Network Design”, Proc. of the Fifth International Conference on Genetic Algorithms, July, 1993, pp. 408-415. These networks are called “mesh restorable” not to imply that the network is a full mesh, but to reflect the ability of the rerouting mechanism to exploit a mesh-like topology through highly diverse and efficient rerouting of failed signal units.
Ideally a restoration algorithm should restore a network failure quickly (within two seconds), require little administration overhead, handle numerous failure scenarios (not just single span cuts), be highly reliable, easily accommodate network growth, adapt itself to any network topology, and require a minimum amount of spare capacity. Of all restoration architectures, mesh restorable networks employing distributed dynamic path restoration have the greatest potential to satisfy these goals (as discussed in Fujii, H., Yoshikai, N., “Restoration message transfer mechanism and restoration characteristics of double-search self-healing ATM network”, IEEE J-SAC Special Issue: Integrity of Public Telecommunication Networks, vol. 12, no. 1, Jan. '94, pp. 149-158).
To date several centralized and distributed dynamic span restoration algorithms have been reported: Barezzani, M., Pedrinelli, E., Gerla, M., “Protection planning in transmission networks”, Proc. IEEE ICC'92, 1992, pp. 316.4.1-316.4.5. Chao, C. W., Fuoco, G., Kropfl, D., “FASTAR platform gives the network a competitive edge”, AT & T Technical Journal, July/August 1994, pp. 69-81. Chng, R. S. K., Botham, C. P., Johnson, D., Brown, G. N., Sinclair, M. C., O'Mahony, M. J. Hawker, I., “A multi-layer restoration strategy for reconfigurable networks”, Proc. IEEE Globecom '94, December 1994, pp. 1872-1878. Chujo, T., Komine, H., Miyazaki, K., Ogura, T., Soejima, T., “Distributed self-healing network and its optimum spare capacity assignment algorithm”, Electronics and Communications in Japan, part 1, vol. 74, no. 7, 1991, pp. 1-8. Coan, B. A., Vecchi, M. P., Wu, L. T., “A distributed protocol to improve the survivability of trunk networks”, Proceedings of the 13th International Switching Symposium, May 1990, pp. 173-179. Coan, B. A., et al., “Using distributed topology updates and preplanned configurations to achieve trunk network survivability”, IEEE Transaction on Reliability, vol. 40, no. 4, 1991, pp. 404-416. Of these Chng et al and Chujo et al claim the ability to perform path restoration. In general, any span restoration algorithm can be turned into a rudimentary path restoration scheme by iteratively applying the span restoration algorithm to all affected source—destination demand pairs. Using a span restoration algorithm to perform path restoration in this way was previously called Capacity Scavenging [Grover, W. D., Selfhealing Networks—A Distributed Algorithm for k-shortest link-disjoint paths in a multi-graph with applications in realtime network restoration, Ph.D. Dissertation, University of Alberta, Fall, 1989, referred to herein as the Grover Thesis]. While Capacity Scavenging can be used in path (and hence node) restoration, the recovery patterns obtained from uncoordinated concurrent (or arbitrary sequential) execution of a span restoration algorithm for every demand pair affected by a node or span failure may not yield an even allocation of recovery levels amongst affected demand pairs, or synthesize the maximum number of restoration paths topologically feasible.
While a few distributed dynamic path restoration algorithms have been reported [Chow, C. E., Bicknell, J. D., Mccaughey, S., “Performance analysis of fast distributed link restoration algorithms”, International Journal of Communication Systems, vol. 8, 1995, pp. 325-345, Doverspike, R. D., Morgan, J. A., Leland, W., “Network design sensitivity studies for use of digital cross-connect systems in survivable network architectures”, IEEE J-SAC Special Issue: Integrity of Public Telecommunication Networks, vol. 12, no. 1, January '94, pp. 69-78], none attempt to find a pathset which restores the maximum amount of lost demand topologically feasible. Distributed dynamic path restoration algorithms developed to date have focused on achieving restoration within the two second call-dropping threshold, and have given capacity efficiency secondary consideration.
SUMMARY OF THE INVENTION
The research presented here is unique in that it is the first distributed dynamic path restoration algorithm which attempts to configure the surviving spare links of a path restorable network to restore failed working paths in a capacity efficient manner, and do so within the two second call-dropping threshold, while achieving the other goals for path restoration of a mesh restorable network.
There is therefore provided a method and apparatus for establishing a communications path in a telecommunications network, in which the network is formed by plural nodes interconnected by plural spans, each span containing working and spare links, each node having a cross-connect switch for connecting links in spans terminating at the node and a controller for controlling propagation and content of statelets arriving at or transmitted from the node. In a first aspect of the invention, the method comprising the steps of:
propagating statelets through the network, in which each statelet comprises fields designating a source node for the statelet, a statelet index, and a measure of the spare capacity of spans traversed by the statelet;
updating each statelet transmitted from a node on a span, except at a destination node for that statelet, to alter the measure of spare capacity according to the spare capacity of the span on which the statelet is to be transmitted; and
creating a communications path through the nodes traversed by a statelet upon arrival of a statelet at the destination node of the statelet.
In a further aspect of the invention, the statelet comprises a field identifying the destination node of the statelet.
In a further aspect

Affiliated with

Also associated with

Rating

Path restoration of networks does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Path restoration of networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Path restoration of networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2843233