Multiplex communications – Fault recovery – Bypass an inoperative channel
Reexamination Certificate
1997-05-29
2001-08-28
Nguyen, Chau (Department: 2663)
Multiplex communications
Fault recovery
Bypass an inoperative channel
C370S238000
Reexamination Certificate
active
06282170
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to methods of optimising a route set up for passing information through a network, methods of restoring a route set up in a network, and nodes arranged for use in such methods.
BACKGROUND TO THE INVENTION
In networks such as mesh type networks, there are numerous possible routes for passing communication between one node and another node. Many types of routing algorithms are known for finding the shortest route, or for making best use of available capacity. One particular case, or application of routing methods is for the purpose of restoring a network after a failure has been detected. Such a failure may take the form of loss of a link between nodes, or loss of a node. Methods of restoring the network can be categorised as preplanned, or adaptive. Preplanned methods require knowledge of the topology of the network. Adaptive methods involve finding out the topology of the network around the failure, in real time. This involves making use of some processing capability at the nodes.
Conventional methods may involve distributed processing at the nodes, or centralised control by a remote processing means.
Conventionally, there have been three main characteristics by which restoration methods have been assessed. Firstly the percentage of the capacity of the failed link which is restored using the alternative routes, can be measured. Secondly, the length of the alternative routes can be measured (shorter routes are preferred usually). Thirdly, the time taken to identify and establish the alternative routes can be assessed.
Clearly, the performance of a restoration method depends crucially on how much spare capacity there is in the alternative routes. If the alternative routes are heavily loaded already and have little spare capacity, then more such alternative routes will be needed, and they are likely to be longer.
In one known algorithm (Grover WD “Self Healing Networks—a distributed algorithm for k-shortest link—disjoint paths in a multigraph with applications in real time network restoration, pages 76 to 106, PhD dissertation, University of Alberta, Autumn 1989), a completely distributed k-shortest paths processing sequence with no prior knowledge of network topology at any node, is disclosed. The process is shown in
FIG. 1
, steps
50
to
55
.
FIG. 2
shows in schematic form, the layout of the nodes involved in the process.
FIG. 2
shows a relatively simple arrangement. In practice there are likely to be many around the broken link, and many nodes in each route.
When a link failure occurs, two custodial nodes are cast at the end points of the failed link. Using their unique node identification numbers, they order themselves into sender
63
and chooser
64
. The sender creates flooding instances which propagate from sender to chooser, for each failed channel, to search out available spare paths. The nodes involved in the search propagation, known as tandem nodes
65
, assign spare channels to the flooding instances, and cause the flooding instances to increase their count of the number of hops used. When a chooser receives a flooding instance, it can read the hop count to identify the shortest route. The shortest route is acknowledged, and capacity assigned by the tandem nodes is relinquished unless it is on the acknowledged shortest route. The same process is carried out for each channel which uses the failed link.
Others have proposed variations on this basic algorithm, including the concept of multiple candidate choosers, as shown in “A Distributed Restoration Algorithm for a Multiple Link and Node Failures of Transport Networks” by H Komine et al (proceedings of the IEEE Globecom 1990, pages 459 to 463). Furthermore, in “Restoration Message Transfer Mechanism and Restoration Characteristics of Double Search Self Healing ATM Network”, IEEE Journal of Select Areas in Communications, volume 12 number 1 pages 149 to 157, January 1994, there is disclosure of a double search. The sender and chooser take on each others roles, to enable searches in both directions.
However, such methods can result in a large number of search instances, if there are many channels. It is known to use only a single search instance between the sender and chooser, from “Self Healing Techniques Utilising Virtual Path Concept for ATM Networks”, Kawamura et al, Electronics and Communication in Japan, part 1, volume 75, number 4, pages 86 to 96, 1992.
However, this method involves the search instance obtaining information about capacity for groups of channels, on a channel by channel basis. Again, where there are many channels, the flooding instance will become large and complex.
With all the methods discussed, based on spare capacity being identified and allocated by each tandem node, on a channel basis, for example for each virtual path (VP) in an ATM system, the first virtual path may cause temporary allocation of spare capacity on a wide range of alternative routes, until the shortest route is acknowledged. Such temporary allocation may block a succeeding virtual path or force it to find a much longer route than would otherwise be necessary. Accordingly, performance of such restoration methods may be poor, particularly on networks such as wide area telecommunications networks which may be heavily loaded, and have little spare capacity.
It is also known to use complex max-flow algorithms at the network configuration or design stage, to calculate the minimum amount of spare capacity required to achieve 100% restoration of failures on neighbouring links or nodes. These enable performance testing of restoration algorithms, to see how close they come to optimal restoration. This is unrealistic because real networks are often so heavily loaded that 100% restoration is not possible.
Therefore there is a need for algorithms better suited to such heavily loaded networks.
SUMMARY OF THE INVENTION
The invention aims to provide improved methods and products.
According to a first aspect of the invention there is provided a method of restoring a route set up in a network following a failure of part of the network, the network comprising a plurality of fixed nodes, and links interconnecting the nodes, wherein the restored route is allocated, the method comprising the steps of:
selecting a restoration route around the failed part;
allocating to the restoration route at least a portion of the capacity of the links it uses;
determining if the restoration route already set up can be optimised so as not to use at least one of the links currently used by the restoration route;
changing the restoration route according to the result of the determination; and
making available the capacity allocated to the restoration route on the link or links no longer used, for use in setting up other routes.
Improved capacity allocation can be achieved if restored routes already set up are examined to see if they can be optimised.
Advantageously the method also comprises the step of interrogating nodes on the route to gather information on possible alternative routes. Gathering information on possible alternative routes means there is no need to have preplanned preferred routes or centralised knowledge of the configuration of the network, and thus the optimisation can be adaptive and easily take account of changes in network configuration.
Advantageously, the determining step comprises the step of interrogating nodes on the route to gather information on possible alternative routes. Having the nodes react to the gathered information means the optimisation processing can be distributed through the nodes, and no centralised control is necessary. Thus message passing to and from a centralised controller can be avoided. Distributing the processing also enables it to adapt more easily to changing network configurations.
Advantageously, the route is set up for passing cell oriented information.
Advantageously, route is a virtual path in an ATM network.
Advantageously, the route is a virtual circuit for frame relay. Virtual paths or virtual circuits can be created or torn down rapidly, and
Bentall Mark
Hobbs Christopher William Lewis
Turton Brian Charles Hargrave
Hyun Soon-Dong
Lee Mann Smith McWilliams Sweeney & Ohlson
Nguyen Chau
Nortel Networks Limited
LandOfFree
Network restoration routing optimization does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Network restoration routing optimization, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Network restoration routing optimization will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2440017