Method for protecting a telecommunications network

Details Method for protecting a telecommunications network Method for protecting a telecommunications network

2000-04-28

2004-11-16

Olms, Douglas (Department: 2661)

Multiplex communications

Pathfinding or routing

C370S258000

Reexamination Certificate

active

06819662

ABSTRACT:

FIELD OF THE INVENTION
This invention relates to the protection of communication networks against span failures.
BACKGROUND OF THE INVENTION
The inventor Wayne D. Grover has previously proposed a method for the automated synthesis of transport network designs based on multiple SONET self-healing rings. [Grover et al, Optimized Design of ring-based Survivable Networks, Can. J. Elect. & Comp. Eng., vol. 20, No. 3, 1995] A heuristic procedure was based on insights about the trade-off between capacity efficiency and traffic capture efficiency of ring sets to find a minimum-cost composite design. The method was called RingBuilder™ Version 1. In the method, demands are first mapped onto the spans of a network via shortest-path routing, with a load leveling criterion if multiple equal-length shortest routes are present. This produces a network graph. Next, all distinct simple cycles in the network graph are identified. Then, each cycle is evaluated according to a metric to find a cycle that maximizes the metric. The proposed metric evaluated capacity efficiency. After a maximizing cycle is found, all the working capacities on spans in the maximizing cycle are set to zero for subsequent iterations of the method steps. The remaining distinct simple cycles are then evaluated according to the metric, and maximizing cycles identified at each iteration, until all spans in the network are covered by a bi-directional line-switched ring.
Some limitations of RingBuilder Version 1 are as follows. Version 1 is only suitable for designing networks that are based entirely on a single size and type of ring technology. Version 1 does not directly optimize the cost of the rings it is choosing. It pursues a weighted trade-off between capture and balance efficiency over a range of compromise weightings. Total network design cost is reported at design termination. Separate cost evaluation is required to find the minimum cost design amongst the designs generated. The process of generating complete designs at each ‘alpha’ (weighting factor) value is very time consuming. Largely because of the computational complexity of sweeping the value of alpha, Version 1 cannot afford to apply any anti-greediness methods or other forms of search to explore the design space around each sweep-generated design. Version 1 is relatively susceptible to missing very good designs because only one synthesis sequence is invested at each alpha value. If used to generate pure balance-optimized designs, Version 1 often does not escape the use of small individually efficient rings. This has the undesirable side effect that more rings than really necessary are often used in the final design. Because of this Version 1 sometimes fails to discover good designs which humans can find by careful inspection and proposal of rings. These designs often involve manually selected span eliminations, which is the deliberate disuse of a topologically existing span, because it can be more cost effective not to use the span at all in the design.
Bi-directional line-switched rings (BLSR) and uni-directional path-switched rings (UPSR) are now in common use for survivable transport networking. (Nortel Networks, “Introduction to SONET Networking,”
SONET
101
Tutorial Handbook
, Oct. 30, 1996) These protection structures offer fast restoration speeds (typically under 150 msec) and, though not as capacity efficient as mesh networks, each ring is individually simple to operate. Ring networks can also be more economical than mesh in metro applications due to their lower nodal equipment costs. (T. Flanagan, “Fiber Network Survivability,”
IEEE Comm. Mag
., pp. 46-53, June 1990)
However, the design of multi-ring networks is an exceptionally complex combinatorial optimization problem. In recent years, a number of approximate design methods have been proposed for the multiple-ring design problem which approach the design as a form of min-cost graph-covering problem. W. D. Grover, J. B. Slevinsky, M. H. MacGregor, “Optimized Design of Ring-Based Survivable Networks”,
Can. J. Elect & Comp. Eng
., Vol. 20, No.3, 1995. O. J. Wasem, T-H Wu and R. H. Cardwell, “Survivable SONET Networks-Design Methodology,”
IEEE J. on Select Areas Comm
., vol. 12, no. 1, pp. 205-212, January 1994. B. Doshi and P. Harshavardhana, “Broadband Network Infrastructure of the Future: Roles of Network Design Tools in Technology Deployment Strategies,”
IEEE Comm. Mag
., vol. 39, pp.60-71, May 1998. L. M. Gardner, I. H. Sudborough and I. G. Tollis, “Net Solver: A Software Tool for the Design of Survivable Networks,”
IEEE GLOBECOM
1995, vol. 1, pp. 39-44, November 1995).
Some schemes take a capacitated coverage view (the ring capacities placed must be adequate to carry all demand crossing the underlying span), or an uncapacitated, purely logical coverage viewpoint (at least one ring covers every span). (L. M. Gardner, M. Heydari, J. Shah, I. H. Sudborough, I. G. T
IEEE GLOBECOM
1994, vol. 3, pp. 1862-1866, 1994.)
Generally, the capacity requirements of each span are determined by routing demands over the shortest path from end-to-end. Intuitively, this can lead to coverage solutions with one or more very low-utilization rings; rings that were placed, in essence, just due to the strict coverage requirement, but serve little demand. To illustrate, consider the simple graph and demand matrix in FIG.
1
(
a
) where the capacity required on each span has been determined by shortest path routing over the native graph. If we assume OC-12 4-fibre BLSRs, a minimum of two rings is required in a ‘coverage’ design. Moreover both of these rings are forced to cover span B-D. And together they have only 2/24
th
capacity utilization on that span.
In this case it is fairly apparent by inspection that “eliminating” span B-D would force the B-D demand flow to take another route or routes (with demand bundle splitting) and, as constructed in FIG.
11
(
b
) result in a single perfectly filled OC-12 ring to cover the network graph. Note that the capacity utilization of the ring increases at the same time as fewer rings are used due to eliminating span B-D. The capacity and capture efficiency are both improved
The example is a simple one. More generally the challenge is to identify those spans of a graph which, for a given demand pattern and ring modularities, will have desirable effects as above, if eliminated. If the wrong span is eliminated, it can backfire: total (inter-ring) routing costs increase due to excessive detouring from the shortest path and ring counts can increase due to exceeding a modularity threshold. It is known that experienced manual planners, with some trial and error, can fairly effectively visualize these opportunities in complex real-sized problems. To our knowledge, however, our work is the first attempt at a systematic algorithmic approach to span elimination.
SUMMARY OF THE INVENTION
The present invention provides an improvement over RingBuilder™ Version 1 for optimized design of multiple ring networks, such as SONET and WDM networks. For example, multi-technology designs are possible, unlike in RingBuilder™ Version 1. Other advantages of the present invention include: Ring choices in each iteration are based directly on cost assessment, and not on the intermediate measures of balance and capture efficiency. The total cost of the design is known immediately at the end of the run. A minimum cost final design can be determined without sweeping. Anti-greediness tactics are employed, exploring the design space in the region of the basic synthesis sequence to a significant and user-specifiable extent.
Aspects of the invention include:
iterative ring selection via transport utility (or “bang for the buck”),
aggregating routing,
statistically “dithered” ring choice selection,
random or systematic cycle-set masking on a per iteration basis,
progressive expansion of cycle set scope as the design evolves to completion,
wide ‘horizontal’ searches of partial designs followed by progressive design depth search to completion,
systematic use of aggregation pressure for discovery of c

Affiliated with

Also associated with

Rating

Method for protecting a telecommunications network does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method for protecting a telecommunications network, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for protecting a telecommunications network will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3305191