Availability aware cost modeling for optical core networks

Background of the Invention

1. TECHNICAL FIELD

0001This invention relates in general to communications networks and, more particularly, to optimization of a network design.

2. DESCRIPTION OF THE RELATED ART

0002In the design and modification of a network architecture, such as a local exchange network or a core (backbone) network, both capital expenditures and operational expenditures should be considered in evaluating the total cost of the network. Capital expenditures would include the cost of new equipment and, if necessary, additional lines (such as optical fiber lines). Operational expenditures include those expenses necessary to operate the network at the service provider's expectations. In determining the operational expenditures, the availability of the network should be considered are part of the cost, through maintenance and repair efforts.

0003The solution that provides the lowest capital expenditures may often not result in the lowest total cost. This would be true if the network with the lowest capital expenditures does not meet the service provider's requirements for availability or if additional operational expenses would be required to bring the network's availability to a reasonable level in an attempt to shorten the Mean Time To Repair (MTTR) by spending more on repair crew efforts.

0004With the large number of options available for a network configuration, such as parameters related to traffic grooming, express routes, network dimensioning, and so on, it is virtually impossible to find a solution that is a near optimum solution. Integrating similar constraints relating to availability, would increase the complexity of the problem which is already non-trivial to cope with. Moreover, the objectives of availability and cost are often conflicting. This means that when one of the objectives (e.g. cost or availability) improves, the other one (availability or cost) worsens. Service providers generally are satisfied to find a solution that works, without considering other options. This can lead to excessive present costs due to capital expenditures or excessive future costs due to ongoing operational expenditures.

0005With communications being a highly cost competitive field, it has become more necessary to reduce total costs.

0006Therefore, a need has arisen for finding a nearoptimal solution for designing a network. <patcit id="pcit0001" dnum="US5598532A"><text>US Patent 5,598,532</text></patcit> relates to a method and apparatus for optimizing computer networks. Data regarding network topology and traffic flow is collected, and a network model is created. The model is analyzed using optimization rules and network performance objectives to determine the optimal configuration of the network according to the network performance objectives. An optimization rule for positioning a shared central resource on the network identifies the communication paths between all clients of the resource and assigns a cost value to the traffic flowing between the clients and the resource. This is repeated for each potential resource position in the network. Canadian Patent Application <patcit id="pcit0002" dnum="CA2291378"><text>CA 2,291,378</text></patcit> relates to a method for designing an access network that is to carry communication traffic between end nodes and a core network. Information is provided that describes end node locations, the level of demand associated with each end node, available trunk types and their related capacities, and a cost structure. The cost structure includes a fixed overhead cost for each trunk type, and a service charge per unit distance for each trunk type. The provided information is incorporated in a linear program to find an optimal-cost access network. <patcit id="pcit0003" dnum="US2002198991A"><text>US Patent Application 2002/198991</text></patcit> describes a system and method for intelligent caching and network management includes contextual information representing needs of a user. A contextual system determines settings based on the contextual information and determines services and devices available for the user, in accordance with the contextual information. A predictor receives the contextual information, the settings, the services available and the devices available and predicts the needs of the user to make resources available to the user in accordance with predictions.

Brief Summary of the Invention

0007In the present invention, a communications network structure is determined by iteratively performing the steps of: (1) generating a cost value for a network architecture, (2) performing an availability analysis to identify which traffic-carrying paths, if any, have availability values below a predetermined threshold, and (3) improving the network architecture responsive to the identified trafficcarrying paths.

Brief Description of the Several Views of the Drawings

0008For a more complete understanding of the present invention, and the advantages thereof, reference is now made to the following descriptions taken in conjunction with the accompanying drawings, in which:

0009<figref idref="f0001">Figure 1</figref> illustrates a block diagram of a general flow for designing a cost-effective network;

0010<figref idref="f0001">Figure 2</figref> illustrates the cost modeling step of <figref idref="f0001">Figure 1</figref>;

0011<figref idref="f0002">Figure 3</figref> illustrates a path through a mesh architecture;

0012<figref idref="f0002">Figures 4a through 4b</figref> illustrate connections through a ring architecture;

0013<figref idref="f0003">Figure 5</figref> illustrates a general flow chart for a preferred embodiment of the availability analysis;

0014<figref idref="f0004">Figure 6</figref> illustrates a solution tree for the availability analysis;

0015<figref idref="f0004">Figure 7</figref> illustrates a depth-first solution tree;

0016<figref idref="f0004">Figure 8</figref> illustrates a breadth-first solution tree;

0017<figref idref="f0005">Figure 9</figref> illustrates a solution set provided by a single solution tree for a respective network architecture;

0018<figref idref="f0005">Figure 10</figref> illustrates a solution space for multiple solution sets provided by a multiple solution tree for respective network architectures.

Detailed Description of the Invention

0019The present invention is best understood in relation to <figref idref="f0001 f0002 f0003 f0004 f0005">Figures 1-10</figref> of the drawings, like numerals being used for like elements of the various drawings.

0020<figref idref="f0001">Figure 1</figref> illustrates a diagram showing a sequential iterative methodology capable of finding a solution space with different cost/availability values for multiple network architectures from which an optimal or near-optimal solution can be determined. <figref idref="f0001">Figure 1</figref> uses two main modules: modeling module 10 and availability module 12. Generally speaking, the modeling module provides a cost value for a network architecture under consideration and, once cost modeling is done, an availability analysis is performed for the architecture under analysis. The modeling module 10 and availability module 12 can be implemented on a computing device as described below.

0021The availability analysis includes calculations for end-to-end (e2e) connection availability for a channel carrying end-to-end traffic demand in the traffic demand matrix. The analysis may also include the average and the worst channel availability. The analysis module 12 provides the planner/designer with information identifying the weakest connection in the network, the availability distribution for all the end-to-end connections and the connections that are below the desired minimum level of availability acceptable for a channel connection.

0022It is possible that the overall availability and cost of a network architecture are satisfactory except the availability value for a few channels. In such a case, the availability analysis module 12 reveals the causing factors of the unsatisfactory availability for those few connections and suggests modeling modifications. Another scenario would be such that the percentage of connections that have availability values below acceptable level is high. Then, the availability analysis module may suggest switching to another architecture, even though it is not the cheapest, that may provide an acceptable level of overall availability. This feedback to the modelling module indicates whether iterative improvements in the solution space of a particular architecture is likely to produce a usable solution, or whether it is prudent to switch to another architecture in the solution volume for further considerations. The improvements on an architecture, on the other hand, can be done in this iterative manner until a reasonable level of satisfaction is reached.

0023Accordingly, by iteratively performing an availability analysis of a network, improving the network based on identified factors causing unsatisfactory availability for the network, and performing a cost analysis of the improved network, a near-optimum network can be heuristically achieved.

0024The invention described herein could be used to analyze various network architectures in a variety of applications. For purposes of illustration, the invention will be discussed in connection with backbone (core) networks where different ring and mesh architectures are evaluated.

0025<figref idref="f0001">Figure 2</figref> is a flow chart describing the cost modeling module 10. Initially, the modeling module 10 performs the cost modeling and provides a network model for each architecture under consideration, optimized by cost. According to the architectural specifics and features, steps and sequence of procedures may differ in the execution of the modeling process. The modeling process, as shown in <figref idref="f0001">Figure 2</figref>, is designed for a few different network architectures. These architectures are restorable mesh networks with and without express routes; and two ring architectures namely BLSR (Bidirectional Line Switch Protection Rings) and LSPR (Line Shared Protection Rings).

0026Briefly, a single layer mesh architecture without express routes is one of the architectures used for backbone networks. In this type of network, all optical channels going through each intermediate node will be electrically regenerated, and spans will be designed to guarantee that the quality of the optical signal is always at the required level. Additional capacity in the network is added for restoration purposes. The bandwidth dedicated to restoration is shared for all demands in an optimal way.

0027Another network architecture type is a mesh network with express routes. The network cost is dominated by the node cost, since the transmission cost is reduced significantly with the use of DWDM systems having large number of wavelengths, 40 or 80, and long regeneration spans, of up to 3,000 km. Therefore, to obtain the most economic network design, the node cost must be reduced. This is achieved by creating express routes between specific nodes, which will carry large amount of traffic bypassing intermediate nodes.

0028The alternatives to mesh are the ring architectures. Today, BLSR is the most deployed in backbone ring networks. Ring architectures allow a fast and simple restoration mechanism compared to the complexity of mesh restoration. Restoration bandwidth is allocated in each ring such a way that any single failure is resolved in that very same ring, without any repercussion on the rest of the network (ring failure isolation). Taking all that into account, it can be concluded that ring architectures are usually more robust than mesh; however, mesh architectures are more economical than ring architectures.

0029A Line Shared Protection Rings (LSPR) architecture is an extension of BLSR. LSPR takes the benefit of the fast restoration of the ring architectures, and the economics of the mesh architectures. The differential characteristic is sharing of the restoration bandwidth among several rings. The restoration bandwidth in a link is shared by several rings and can be used to protect against a failure in one ring at a time.

0030Returning to <figref idref="f0001">Figure 2</figref>, traffic grooming is performed at step 20. It is assumed that the network uses digital cross-connects and IP routers as traffic grooming devices. Here, the aim is to reduce the number of expensive OXC (optical cross connect) drop ports by bundling low bit rate traffic into optical channels. One option for bundling is end-to-end bundling where all low bit rate traffic is bundled in the same optical channel on each pair of nodes. Another option is the bundling optimization where the low bit rate signals are routed such that the number of optical channels in the network is minimized. Cost optimization could be also done for bundling. The low bit rate traffic is re-routed such that the network cost including OXC ports, amplifiers, regenerators, and fiber length are minimized. Switching between bundling techniques would change the number of optical channels, OXC ports, and the number of other transmission devices, which would in turn, result in an entire different design.

0031The modeling module then performs express route optimization in step 22 where it defines the optimal set of end-to-end optical channels by bypassing intermediate nodes in order of reduce the number of expensive OXC ports. Bypassing nodes, however, requires more transmission equipment by the regenerated spans, increasing transmission costs. While bypassing nodes thus presents a trade-off between transmission cost versus node cost (OXC ports), the savings in node costs generally dominate the extra expenses in transmission cost. The express optimization step starts with an initial set of logical spans (routes) and slowly eliminates the spans one-by-one. An integer linear programming technique is used to maximize the savings. Depending on the initial set of logical spans, the optimization could give different solutions; therefore, altering the initial set of logical spans could result in a different network design.

0032The last step in modeling is network dimensioning where nodes and spans are dimensioned to carry the traffic demand with the required protection level. Since each architecture considered has a different protection scheme (mesh, BLSR, LSPR, etc.), the dimensioning is done specifically for each architecture as shown in steps 24, 26 and 28. Working and protection paths are calculated by using one of the following criteria: (1) minimizing path length, (2) minimizing number of hops, or (3) minimizing cost, considering OXC ports, amplifiers, regenerators, and fiber. Using a different minimizing technique would give a different design; therefore, it would change the availability and cost. Span design is also done by considering different transmission types (i.e. Long Haul, Very Long Haul, Ultra Long Haul). The aim is again to minimize the cost. After all these steps, a model for each basic architecture is created and a cost for each architecture is calculated in step 30.

0033After the initial cost modeling is done for a considered architecture, the availability analysis is performed by the availability analysis module 12 given in <figref idref="f0001">Figure 1</figref>. In the availability analysis, availability for each end-to-end connection is calculated by considering working and restoration components. Since restoration is performed differently in different architectures, the availability calculation separately for mesh and rings is described below.

0034<figref idref="f0002">Figure 3</figref> illustrates a diagram of an end-to-end path for a restorable mesh architecture between source 36 and destination 38. In a restorable mesh architecture, for a connection between two end nodes of a demand, there are one working path and one or several protection paths. A path, as shown in <figref idref="f0002">Figure 3</figref>, is made up of one or more spans contains three major components: fiber 40, line equipment including line amplifiers 42 and regenerators 44, and nodal equipment including cross-connects 46.

0035Availability of a path is calculated by using the availability figures of components along each span in the path in a serial manner. Assuming that there are <i>m_i</i> number of in-line amplifiers and <i>n_i</i> number of regenerators in <i>span_i</i> , and <i>L_i</i> is the fiber length of the <i>span_i</i>, then the availability of the <i>span_i</i> would be A<i>_span</i> (given below) where A<i>_amp</i> is the availability of an amplifier, A<i>_regen</i> is the availability of a regenerator, and <i>A_fiber(L)</i> is the availability of a fiber of length <i>L</i>: <maths id="math0001" num="(1)"><math display="block"><msub><mi>A</mi><msub><mi mathvariant="italic">span</mi><mi>i</mi></msub></msub><mo>=</mo><msub><mi>A</mi><mi mathvariant="italic">fiber</mi></msub><mfenced><msub><mi>L</mi><mi>i</mi></msub></mfenced><mo>⁢</mo><mi>x</mi><mstyle displaystyle="true"><munderover><mo>∏</mo><mrow><mi>k</mi><mo>=</mo><mn>1</mn></mrow><msub><mi>m</mi><mi>i</mi></msub></munderover></mstyle><msub><mi>A</mi><msubsup><mi mathvariant="italic">amp</mi><mi>k</mi><mi>x</mi></msubsup></msub><mstyle displaystyle="true"><munderover><mo>∏</mo><mrow><mi>k</mi><mo>=</mo><mn>1</mn></mrow><msub><mi>n</mi><mi>i</mi></msub></munderover></mstyle><msub><mi>A</mi><msub><mi mathvariant="italic">regen</mi><mi>k</mi></msub></msub></math><img file="EP1533941B1_D0001.tif" /></maths>

0036Assuming that a path has <i>h</i> number of hops and A<i>_node</i> represents the availability of an intermediate node, then the availability for the path without source and destination would be A<i>_path</i> (given below): <maths id="math0002" num="(2)"><math display="block"><mrow><msub><mi>A</mi><mi>path</mi></msub><mo>=</mo><mfenced open="{" close="}" separators=""><mstyle displaystyle="true"><munderover><mo>∧</mo><mrow><mi>k</mi><mo>=</mo><mn>1</mn></mrow><mi>b</mi></munderover></mstyle><msub><mi>A</mi><msub><mi mathvariant="italic">span</mi><mi>k</mi></msub></msub></mfenced><mo>∧</mo><mo>{</mo><mstyle displaystyle="true"><munderover><mo>∧</mo><mrow><mi>k</mi><mo>=</mo><mn>1</mn></mrow><mrow><mi>h</mi><mo>-</mo><mn>1</mn></mrow></munderover></mstyle><msub><mi>A</mi><msub><mi mathvariant="italic">node</mi><mi>k</mi></msub></msub><mo>}</mo></mrow></math><img file="EP1533941B1_D0002.tif" /></maths>

0037Let A<i>_destination</i> and A<i>_source</i> represent the availability of the destination and the source nodes, respectively and let A_{<i>w</i>_<i>path</i>} and A_{<i>p</i>_<i>path</i>} represent the availability of working and protection paths, respectively. In the end-to-end channel connection availability, A<i>_e2e</i> (given below), there are working path and protection path(s) one for each potential span failure: <maths id="math0003" num="(3)"><math display="block"><msub><mi>A</mi><mrow><mi>e</mi><mo>⁢</mo><mn>2</mn><mo>⁢</mo><mi>e</mi></mrow></msub><mo>=</mo><msub><mi>A</mi><mi mathvariant="italic">source</mi></msub><mo>⁢</mo><mi>x</mi><mo>⁢</mo><msub><mi>A</mi><mi mathvariant="italic">destination</mi></msub><mo>⁢</mo><mi>x</mi><mfenced open="{" close="}" separators=""><msub><mi>A</mi><mi mathvariant="italic">w_path</mi></msub><mo>∨</mo><mfenced open="{" close="}" separators=""><mstyle displaystyle="true"><munderover><mo>∧</mo><mrow><mi>k</mi><mo>=</mo><mn>1</mn></mrow><mi>h</mi></munderover></mstyle><msub><mi>A</mi><mrow><mi mathvariant="italic">p_</mi><msub><mi mathvariant="italic">path</mi><mi>k</mi></msub></mrow></msub></mfenced></mfenced></math><img file="EP1533941B1_D0003.tif" /></maths>

0038In the equations above, the "Λ" and "V" represent a serial and parallel system availability calculation of paths, respectively considering the common components/entities that may exist in more than one path. For example, some of the nodes and/or spans may be shared in more than one protection or working path. In such cases, duplications cancel out from the solutions set.

0039<figref idref="f0002">Figures 4a-b</figref> illustrates ring structures connecting nodes 46. For a BLSR single ring, as shown in <figref idref="f0002">Figure 4a</figref>, there is a working path and, for each node or link failure on this path, there is a looped back protection path. If one or more links and/or intermediate nodes fail on the working path, a corresponding looped back protection path is formed isolating the failure section.

0040Therefore, there are multiple different protection paths covering for all the failure scenarios in the working path. After the mathematical exercise for covering all the failures is done, all restoration paths reduce to one single protection path for a given working path, shown in <figref idref="f0002">Figure 4b</figref>.

0041LSPR architectures implement Network Protection Equipment (NPE) techniques in such way that the restoration mechanism will be based on path switching instead of link switching. Therefore, as picture in <figref idref="f0002">Figure 4b</figref>, for all link and/or node failures on the working path, a single protection path is used. Notice that BLSR and LSPR become equivalent from availability perspective for a single ring. Therefore, the availability of a single ring end-to-end connection for both BLSR and LSPR is mathematically complete by the A<i>_{e2eSinglering}</i> definition: <maths id="math0004" num="(4)"><math display="block"><msub><mi>A</mi><mrow><mi>e</mi><mo>⁢</mo><mn>2</mn><mo>⁢</mo><mi>e_Singlering</mi></mrow></msub><mo>=</mo><msub><mi>A</mi><mi mathvariant="italic">source</mi></msub><mo>⁢</mo><mi>x</mi><mo>⁢</mo><msub><mi>A</mi><mi mathvariant="italic">destination</mi></msub><mo>⁢</mo><mi>x</mi><mfenced open="{" close="}" separators=""><msub><mi>A</mi><mi mathvariant="italic">w_path</mi></msub><mo>+</mo><msub><mi>A</mi><mi mathvariant="italic">p_path</mi></msub><mo>-</mo><msub><mi>A</mi><mi mathvariant="italic">w_path</mi></msub><mo>⁢</mo><mi>x</mi><mo>⁢</mo><msub><mi>A</mi><mi mathvariant="italic">p_path</mi></msub></mfenced></math><img file="EP1533941B1_D0004.tif" /></maths>

0042In the above equation, A<i>_source</i> and A<i>_destination</i> represent the availability of source and destination nodes. A_{<i>w</i>_<i>path</i>} and A_{<i>p</i>_<i>path</i>} represent the availability of working and protection paths, which are defined previously. Within the curly bracket, the parallel system availability of working and protection paths is calculated.

0043As used herein, the "gate node" is the node used to interconnect two rings and the "border section" is the common set of nodes and links between two rings. For each end-to-end connection that is routed through multiple rings, several gate nodes and border sections will be crossed. In addition to source and destination nodes, gate nodes in a multi-ring connection constitute a single point of failure where each intermediate ring has redundancy with the provided protection mechanism. Therefore, the availability of these entities is composed together in a serial manner for the end-to-end multi-ring availability, A<i>_{e2eMultiplerings}</i> (given below), in the multi-ring formula. Multiplication is used for the single point of failure entities and the Λ represents the serial system availability calculation of such rings considering the common components that may exist in the same border section. According to the ring architecture deployed, BLSR or LSPR, the border section will have more or less common elements. The end-to-end multi-ring availability can be calculated as: <maths id="math0005" num="(5)"><math display="block"><msub><mi>A</mi><mrow><mi>e</mi><mo>⁢</mo><mn>2</mn><mo>⁢</mo><mi mathvariant="italic">e_Multiplerings</mi></mrow></msub><mo>=</mo><msub><mi>A</mi><mi mathvariant="italic">source</mi></msub><mo>⁢</mo><mi>x</mi><mo>⁢</mo><msub><mi>A</mi><mi mathvariant="italic">destination</mi></msub><mo>⁢</mo><mi>x</mi><mstyle displaystyle="true"><munderover><mo>∏</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mrow><mi>N</mi><mo>-</mo><mn>1</mn></mrow></munderover></mstyle><msub><mi>A</mi><mi mathvariant="italic">gatenode_i</mi></msub><mo>⁢</mo><mi>x</mi><mfenced open="{" close="}" separators=""><mstyle displaystyle="true"><munderover><mo>∧</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>N</mi></munderover></mstyle><msub><mi>A</mi><mi mathvariant="italic">Intermediatering</mi></msub></mfenced></math><img file="EP1533941B1_D0005.tif" /></maths>

0044An intermediate ring has also working path and protection path at opposite bounds of the ring for the transit demand traffic, and its availability is calculated similar to a single ring without the source and destination nodes.

0045As stated above, the invention can be used with any type of network structure and, therefore, calculations for availability will need to be determined for the types of network structures being considered.

0046At the end of each availability analysis, a solution is classified as Acceptable, Unacceptable, or Improvable. The formal definition of this classification is done by using the notation below: <ul id="ul0001" list-style="none" compact="compact"><li>N: Number of end-to-end channel connections.</li><li>p_i : availability of connection i.</li><li>P^N(a,m) = {p₁,p₂,p₃....,p_N} : set of availability of all "N" connections by using architecture "a" and optimisation parameter set "m".</li><li>T^N={t₁,t₂,t₃,..., t_N}: set of desired availability of "N" connections.</li><li>A^N(a,m): Subset of connections whose availability values are above a threshold value t_i, A^N(a,m) ⊆ P^N(a,m) and p_i ∈ A^N(a,m) if p_i ≥ t_i.</li><li>C^N (a,m): cost of the solution with "N" connections by using architecture "a" and optimisation parameter set "m".</li><li>K: an integer value where 0&lt;K&lt;N.</li></ul>

0047If all the connections in an architecture are above their corresponding desired availability values (threshold values), as shown below, then the solution is called "Acceptable": <ul id="ul0002" list-style="none" compact="compact"><li>If |A^N(a,m) | = N then P^N(a,m) is "Acceptable".</li></ul>

0048If the number of connections above their desired availability values (threshold value) is less than K, then the solution is not considered at all and is called "Unacceptable": <ul id="ul0003" list-style="none" compact="compact"><li>If |A^N(a,m)| &lt; K then P^N(a,m) is "Unacceptable".</li></ul>

0049If the number of connections above availability threshold values is equal or greater than K, then the solution is considered for incremental improvement and is called "Improvable": <ul id="ul0004" list-style="none" compact="compact"><li>If |A^N(a,m)| ≥ K then P^N(a,m) is "Improvable".</li></ul>

0050<figref idref="f0003">Figure 5</figref> illustrates a flow chart for evaluating different network structures. In step 50, the requirements for q basic architectures under consideration are generated. In the example illustrated herein, q=4, where the four basic architectures are a mesh architecture with and without express routes, a LPSR Ring architecture and a BLSR ring architecture. The requirements will be used to evaluate the basic architectures analyze cost and availability for each architecture.

0051In step 52, the cost, C^N (a,0), of each of the q basic architectures is generated using the equipment specified in step 50, where C^N (a,m) is the cost of a solution having N connections, using architecture a (between 1 and q) and optimization set m. For the basic architecture, m=0. Also, the basic architectures are ordered by cost, such that C^N (1,0) is the least expensive solution and C^N (q,0) is the most expensive solution.

0052In steps 54 through 72, an optimum or near-optimum solution is determined, starting from the basic architectures, being modified as necessary to find an acceptable solution at an acceptable price. In step 54, an initial maximum cost is determined. C_max is set to the service provider's maximum stated cost (CustMax); if one or more of the basic architectures provide an acceptable solution at a cost below the service provider's maximum stated cost, the cost of the least expensive acceptable solution is used as C_max. If none of the basic architectures provide an improvable or acceptable solution below the service provider's maximum stated cost, then a solution cannot be found using the basic architectures. This would result in either the initial C_max being raised, or additional basic architectures being generated.

0053In step 56, the evaluation begins with the least expensive basic architecture (a=1). In step 58, if C^N (1,0) (for the first iteration) is less than or equal to C_max, then an availability analysis is performed in step 60. As stated above, if C^N(1,0)>C_max, then there would be no solutions that met the cost standard from the service provider.

0054As described above in connection with <figref idref="f0002">Figures 3, 4a and 4b</figref>, the availability analysis looks at each end-to-end connection and determines whether the connection meets a predetermined availability threshold. The number of connections which fail to meet the threshold determine whether the architecture is considered acceptable, improvable, or unacceptable.

0055In step 62, if the basic architecture is acceptable, then the evaluation is done, since the lowest cost basic architecture meets the service provider requirements. If it is not acceptable in step 62, then it is determined whether the basic architecture is improvable in step 64. If the architecture is not improvable, then it is unacceptable (too many connections below the availability threshold) and the next basic architecture is selected (steps 68 and 70). Otherwise, if the present basic architecture is improvable in step 64, then the iterative process shown in <figref idref="f0001">Figure 1</figref> is performed, preferably using a solution tree described in <figref idref="f0004">Figures 6 - 8</figref>, whereby modifications on the basic architecture are evaluated. As the solution tree is generated, C_max may be reduced if acceptable solutions are found.

0056Even if an acceptable solution is found in the solution tree of step 66, the other architectures are evaluated using steps 58 through 66. However, once an acceptable solution is found in any of the solution trees associated with a basic architecture, C_max may be reduced. This will likely reduce the size of subsequent solution trees (which will only be generated if the cost of the respective basic architectures are below C_max).

0057Once all architectures are considered, the solutions are evaluated in step 72.

0058<figref idref="f0004">Figures 6</figref> though 10 illustrate the solution tree step 64 which implements the iterative process shown in <figref idref="f0001">Figure 1</figref>. <figref idref="f0004">Figure 6</figref> illustrates a solution tree, where each node represents a solution with a specific set of optimization parameters, m_i, and corresponding cost and availability values derived by executing cost modeling 10 and availability analysis modules 12 as described above. The root of the tree represents the initial set of optimization parameters, mo, of the basic architecture. A line from a node m, <i>l</i>_i^m, represents a modification/update in the optimization parameter set m, that would improve the solution in terms of number of connections above the availability threshold, with a potential cost increase.

0059In the case where there could be an improvement, the new optimization set m_new = <i>l_i</i>^m ⊗ m with the <i>l</i>_i^m improvement on m, constitutes a child node of the parent node m. C_max remains a variable cost limitation for a solution. Initially, C_max is the ultimate maximum cost for a solution that an service provider wants to spend, including the availability improvement. However, this value may be reduced in the solution tree construction algorithm to prune some more expensive solution(s) once a lower cost "Acceptable solution" exists. Each node m has cost, C(a, m_i), and availability, P(a, m_i), values.

0060The procedure starts with an initialization function, initialize_solution_tree() given below: <ul id="ul0005" list-style="none" compact="compact"><li><b>initialize_solution_tree</b> (a, m, C_max, T^N, K)</li><li>R_a←create_tree()/*<i>initializes a tree structure & returns the pointer *</i>/</li><li>/<i>*If initial solution is Unacceptable, will return empty tree*</i>/</li><li><b>if</b> {|A^N(a,m,T^N)| ≤ K <b>or</b> C^N(a,m) > C_max} <b>then</b> insert (R_a, <b>null, null, null); return</b> (R_a)</li><li><b>end_if</b></li><li>/<i>*If initial solution is Acceptable, will return the solution only *</i>/</li><li><b>if</b> {|A^N(a,m,T^N}|==N} <b>then</b> insert(R_a,<b>null,null</b>,m); <b>return</b> (R_a)</li><li><b>end_if</b></li><li><i>l*If improvable case, search for the optimal solution by constructing</i> a <i>solution tree</i> */</li><li>Disk-Write (<b>null</b>, C_max)</li><li>construct_tree (R_a,m, T^N)</li><li>Disk-Read (m_opt, C_max)</li><li>/<i>*If optimal solution found, will return tree</i> with <i>this solution only*</i>/</li><li><b>If</b> (m_opt ≠ <b>null</b>) <b>then</b> Insert (R_a, <b>null, null</b>, m_opt); <b>return</b> (R_a)</li><li><b>end_if</b></li><li>/* <i>if optimal solution not found, will return the entire solution tree</i><i>constructed by the construct_tree(..)*</i>/</li><li><b>return</b> (R_a) /* tree <i>of improvable solutions</i> */</li><li><b>end</b> initialize_solution_tree</li></ul>

0061This procedure discovers if the initial solution is either an "Unacceptable solution" or an "Acceptable solution". In case of the unacceptable solution, it returns a null tree and the procedure ends; in the acceptable solution case it returns the root node only representing a unique solution, and the procedure ends. For the "improvable" solution case, another procedure, construct-tree(), given below, is called to build the solution space in a tree structure.

0062If an one or more acceptable solutions are found while building the solution tree, construct-tree() will return the optimal solution (i.e., the lowest cost acceptable solution). If no acceptable solutions are found, the entire solution tree will be returned, so that the various nodes can be analyzed to find the best solution.

0063The construct-tree() procedure is given below: <ul id="ul0006" list-style="none" compact="compact"><li><b>construct_tree</b> (R_a,m, T^N)</li><li><b>for</b> each modification <i>l</i>_i^m<b>do</b> m_new ← <i>l</i>_i^m ⊗ m; Disk-Read (m_opt, C_max) <b>if</b> {|A^N(a,m_new,T^N) | > |A^N(a,m,T^N)|} <b>and</b> {C(a,</li><li>m_new) ≤ C_max} insert (R_a,m, <i>l</i>_i^m, m_new); /* <i>In tree R_a,</i></li><li><i>inserts the new node</i></li><li><i>m_new to the paren node m with the link l_i^m *</i>/</li><li><b>if</b> {|A^N(a,m_new,T^N)|==N} Disk-Write (m_new, C(a, m_new)) /<i>*optimal</i></li><li><i>solution so far</i> */ <b>else</b> construct_tree(R_a, m_new, T^N) <b>end if</b><b>end if</b></li><li><b>end for</b></li><li><b>end</b> construct_tree</li></ul>

0064For each modification, a new node (m_new) is created from a parent node and the improvement. The previous optimal case (m_opt) and its cost (C_max) are read from memory. The new node is inserted to the parent node only if its availability value A^N is better than the availability value of parent node and if its cost is equal to or below C_max. If the availability of all nodes exceeds the stated thresholds, then m_new becomes the new optimal solution, since it has acceptable availability at the lowest cost. This data is then written to memory.

0065Otherwise, it is possible that new node with a further improvement can be added. If the overall availability and cost at a node are satisfactory except for the availability figures of a few end-to-end connections, the availability analysis module 12 reveals the factors which cause unsatisfactory availability for those few connections, and suggests a modelling module to perform further optimizations on those factors which can improve the connections, <i>l</i>_i^m's in the tree structure of <figref idref="f0004">Figure 6</figref>, in terms of availability. When an improvement is made, one or more connections could move above the threshold region, leading to an acceptable availability value for the network, or to an availability value that is improved, yet needs to be improved further to be acceptable.

0066Assume that acceptable level of availability for each end-to-end connection is given, as five 9's (99.999%). As a result of this analysis procedure, one can classify end-to-end connections as below threshold and above threshold. The classification may suggest improving only below-threshold connections because the percentage of such connections is relatively low and/or their availability can be easily brought over the threshold value. In such a case the modeling exercise would have enough information on factors causing low availability, to perform further improvements on those below-threshold connections. Those improvements could be: <ol id="ol0001" ol-style=""><li>1) Network element redundancy: The availability of a network element could be improved by providing internal protection through redundancy of the components (a second copy of switching matrix, power supply, etc.) implying higher cost of the network element. This could be either a network wide upgrade, such as new generation of amplifiers in every span in the network, or relating a specific NE, such as a cross connect at a congested location.</li><li>2) Reduction of number of network elements passed through: There are multiple ways to achieve this, which can be illustrated with two examples. First, advanced transmission techniques, such as Raman amplification, allows extended regeneration distances up to 3000 km between regenerators (as compared to approximately 800 km for a conventional transmission system) which in turn reduces the total number of regenerators for the path. This may significantly impact path availability, since regenerators have relatively lower availability figures. However, those advance transmission systems are very costly. Second the reduction of the number of network elements can be also achieved by modifying the end-to-end paths. For each demand, the cost optimization algorithms routes the paths such that the total network cost is minimized. Cost minimization does not always suggest the shortest path, assuming that the shortest path would also be the cheapest path in terms of quantity of network elements. Therefore, alternative working and/or protection paths with fewer network elements could be used to improve end-to-end availability over the acceptable level.</li><li>3) Path diversity enrichment: end-to-end connection availability would increase with higher diversity in working and protection paths. Therefore, another option for improvement in an unacceptable availability for an end-to-end connection is to use more diverse routes for paths. Note that link and/or node disjoint paths would further improve the end-to-end availability.</li></ol>

0067In this methodology, an iterative combination of such alternatives could be tried a reasonable number of times, to reach a design with an acceptable level for both cost and availability.

0068Another scenario would be that the percentage of connections having availability figures below the acceptable level is high, but yet the network is still an improvable case. In this case, the availability analysis module may suggest architectural changes for consideration. For a two layer architecture, for example, results of the availability analysis might suggest a change in some of the parameters that play a role in splitting the network in two different layers, (subnetworks), improving the overall availability figures. Two layer networks are discussed in <nplcit id="ncit0001" npl-type="s"><text>A. Lardies, A. Aguilar, "Planning methodology for SDH and optical networks", in Proceedings of Design of Reliable Communication Networks 1998, page 020</text></nplcit>.

0069In this case, another iteration is run for the new architecture with new parameters, to reach an acceptable level of availability for the entire network. The solution tree is initialized with the initial set of optimisation parameters, m₀, which represents the root node. If it is an improvable case, the tree construction procedure builds the solution tree, as seen in <figref idref="f0004">Figure 6</figref>.

0070<figref idref="f0004">Figure 7</figref> illustrates an example of a tree that is generated "depth-first" as shown in the construct-tree() procedure above. Each branch of the tree is labeled with a number indicating its position in the sequence. In a depth first tree, if a node does not result in acceptable availability, a new node is spawned with an improvement from that node until an acceptable availability is found, or C_max is exceeded (or until no more improvements are possible). Once the end of a branch is reached, new branches are generated from the parent node, to the extent possible.

0071Using a "depth-first" technique, C_max will generally be reduced at a faster pace, thereby eliminating more nodes from consideration.

0072<figref idref="f0004">Figure 8</figref> illustrates an example of a tree that is generated "breadth-first". In a breadth-first tree, all possible improvements for a node (or nodes at the same level) are generated prior to generating nodes at the next level.

0073In some cases, no architecture will result in a network with acceptable availability values while remaining at or below C_max. For each architecture, the solution tree is reduced to a solution plane, as shown in <figref idref="f0005">Figure 9</figref>. Every node of each tree represents a solution, with different availability and cost figures.

0074Multiple solution trees for multiple architectures are shown in <figref idref="f0005">Figure 10</figref>. For the multiple architectures considered, a "forest" of solution trees exists. By reducing each tree to a plane, a forest can be reduced to a 3-D solution space with multiple planes. From the 3D solution space, one can choose a solution with a set of certain requirements, by considering all architectures.

0075To choose a solution from the 3D solution space, several approaches can be taken. A first approach would be to take the solution with the highest availability. This solution can be determined as: <maths id="math0006" num=""><math display="block"><msub><mi>max</mi><mrow><mi mathvariant="normal">i</mi><mo mathvariant="normal">,</mo><mi mathvariant="normal">j</mi></mrow></msub><mfenced open="{" close="}" separators=""><msup><mi mathvariant="normal">A</mi><mi mathvariant="normal">N</mi></msup><mrow><mo mathvariant="normal">(</mo><msub><mi mathvariant="normal">a</mi><mi mathvariant="normal">i</mi></msub><mo mathvariant="normal">,</mo><msub><mi mathvariant="normal">m</mi><mi mathvariant="normal">j</mi></msub><mo mathvariant="normal">)</mo><mrow><mo mathvariant="normal">|</mo></mrow></mrow></mfenced></math><img file="EP1533941B1_D0006.tif" /></maths>

0076A second approach would be to take the most cost efficient solution. This solution could be determined as: <maths id="math0007" num=""><math display="block"><msub><mi>min</mi><mrow><mi mathvariant="normal">i</mi><mo mathvariant="normal">,</mo><mi mathvariant="normal">j</mi></mrow></msub><mfenced open="{" close="}" separators=""><msup><mi mathvariant="normal">C</mi><mi mathvariant="normal">N</mi></msup><mrow><mo mathvariant="normal">(</mo><msub><mi mathvariant="normal">a</mi><mi mathvariant="normal">i</mi></msub><mo mathvariant="normal">,</mo><msub><mi mathvariant="normal">m</mi><mi mathvariant="normal">j</mi></msub><mo mathvariant="normal">)</mo><mo mathvariant="normal">/</mo><mfenced open="|" close="|" separators=""><msup><mi mathvariant="normal">A</mi><mi mathvariant="normal">N</mi></msup><mfenced><msub><mi mathvariant="normal">a</mi><mi mathvariant="normal">i</mi></msub><mo>⁢</mo><msub><mi mathvariant="normal">m</mi><mi mathvariant="normal">j</mi></msub></mfenced></mfenced></mrow></mfenced></math><img file="EP1533941B1_D0007.tif" /></maths>

0077A third approach would be to use a weighted adaptive solution, where weights ω_a and ω_c are defined as the weight for availability and cost, respectively; where 0≤ ω_a ≤1, 0≤ ω_c ≤1 and ω_A + ω_C = 1.0. In this case, <maths id="math0008" num=""><math display="block"><msub><mi mathvariant="normal">A</mi><mi>max</mi></msub><mo mathvariant="normal">=</mo><msub><mi>max</mi><mrow><mi mathvariant="normal">i</mi><mo mathvariant="normal">,</mo><mi mathvariant="normal">j</mi></mrow></msub><mrow><mo mathvariant="normal">{</mo><mfenced open="|" close="|" separators=""><mi mathvariant="normal">A</mi><mfenced><msub><mi mathvariant="normal">a</mi><mi mathvariant="normal">i</mi></msub><mo>⁢</mo><msub><mi mathvariant="normal">m</mi><mi mathvariant="normal">j</mi></msub></mfenced></mfenced><mo mathvariant="normal">}</mo><mo mathvariant="normal">,</mo><msub><mi mathvariant="normal">A</mi><mi>min</mi></msub><mo mathvariant="normal">=</mo><msub><mi>min</mi><mrow><mi mathvariant="normal">i</mi><mo mathvariant="normal">,</mo><mi mathvariant="normal">j</mi></mrow></msub><mrow><mo mathvariant="normal">{</mo><mfenced open="|" close="|" separators=""><mi mathvariant="normal">A</mi><mfenced><msub><mi mathvariant="normal">a</mi><mi mathvariant="normal">i</mi></msub><mo>⁢</mo><msub><mi mathvariant="normal">m</mi><mi mathvariant="normal">j</mi></msub></mfenced></mfenced><mo mathvariant="normal">}</mo><mo mathvariant="normal">,</mo></mrow></mrow></math><img file="EP1533941B1_D0008.tif" /></maths><maths id="math0009" num=""><math display="block"><msub><mi mathvariant="normal">f</mi><mi mathvariant="normal">A</mi></msub><mo mathvariant="normal">=</mo><mfenced><msub><mi mathvariant="normal">a</mi><mi mathvariant="normal">i</mi></msub><mo>⁢</mo><msub><mi mathvariant="normal">m</mi><mi mathvariant="normal">j</mi></msub></mfenced><mo>=</mo><mn>1</mn><mo>-</mo><mrow><mrow><mo>{</mo><mrow><mo>(</mo><mrow><mo>|</mo><mi mathvariant="normal">A</mi><mfenced><msub><mi mathvariant="normal">a</mi><mi mathvariant="normal">i</mi></msub><mo>⁢</mo><msub><mi mathvariant="normal">m</mi><mi mathvariant="normal">j</mi></msub></mfenced><mo>|</mo><mo>-</mo></mrow></mrow></mrow><msub><mi mathvariant="normal">A</mi><mi>min</mi></msub><mo>)</mo><mo>/</mo><mfenced separators=""><msub><mi mathvariant="normal">A</mi><mi>max</mi></msub><mo>-</mo><msub><mi mathvariant="normal">A</mi><mi>min</mi></msub></mfenced><mo>}</mo></mrow></math><img file="EP1533941B1_D0009.tif" /></maths><maths id="math0010" num=""><math display="block"><msub><mi mathvariant="normal">C</mi><mi>max</mi></msub><mo mathvariant="normal">=</mo><msub><mi>max</mi><mrow><mi mathvariant="normal">i</mi><mo mathvariant="normal">,</mo><mi mathvariant="normal">j</mi></mrow></msub><mrow><mo mathvariant="normal">{</mo><mi mathvariant="normal">C</mi><mfenced><msub><mi mathvariant="normal">a</mi><mi mathvariant="normal">i</mi></msub><mo>⁢</mo><msub><mi mathvariant="normal">m</mi><mi mathvariant="normal">j</mi></msub></mfenced><mo mathvariant="normal">}</mo><mo mathvariant="normal">,</mo><msub><mi mathvariant="normal">C</mi><mi>min</mi></msub><mo mathvariant="normal">=</mo><msub><mi>min</mi><mrow><mi mathvariant="normal">i</mi><mo mathvariant="normal">,</mo><mi mathvariant="normal">j</mi></mrow></msub><mrow><mo mathvariant="normal">{</mo><mi mathvariant="normal">C</mi><mfenced><msub><mi mathvariant="normal">a</mi><mi mathvariant="normal">i</mi></msub><mo>⁢</mo><msub><mi mathvariant="normal">m</mi><mi mathvariant="normal">j</mi></msub></mfenced><mo mathvariant="normal">}</mo><mo mathvariant="normal">,</mo></mrow></mrow></math><img file="EP1533941B1_D0010.tif" /></maths><maths id="math0011" num=""><math display="block"><msub><mi mathvariant="normal">f</mi><mi mathvariant="normal">C</mi></msub><mo mathvariant="normal">=</mo><mfenced><msub><mi mathvariant="normal">a</mi><mi mathvariant="normal">i</mi></msub><mo>⁢</mo><msub><mi mathvariant="normal">m</mi><mi mathvariant="normal">j</mi></msub></mfenced><mo>=</mo><mrow><mo>(</mo><mi mathvariant="normal">C</mi><mfenced><msub><mi mathvariant="normal">a</mi><mi mathvariant="normal">i</mi></msub><mo>⁢</mo><msub><mi mathvariant="normal">m</mi><mi mathvariant="normal">j</mi></msub></mfenced><mo>-</mo></mrow><msub><mi mathvariant="normal">C</mi><mi>min</mi></msub><mo>)</mo><mo>/</mo><mfenced separators=""><msub><mi mathvariant="normal">C</mi><mi>max</mi></msub><mo>-</mo><msub><mi mathvariant="normal">C</mi><mi>min</mi></msub></mfenced></math><img file="EP1533941B1_D0011.tif" /></maths>

0078After choosing ω_a and ω_c, the solution is given by: <maths id="math0012" num=""><math display="block"><msub><mi>min</mi><mrow><mi mathvariant="normal">i</mi><mo mathvariant="normal">,</mo><mi mathvariant="normal">j</mi></mrow></msub><mo mathvariant="normal">=</mo><mfenced open="{" close="}" separators=""><msub><mi mathvariant="normal">ω</mi><mi mathvariant="normal">A</mi></msub><mo>⁢</mo><msub><mrow><mspace width="1em" /><mi mathvariant="normal">f</mi></mrow><mi mathvariant="normal">A</mi></msub><mfenced><msub><mi mathvariant="normal">a</mi><mi mathvariant="normal">i</mi></msub><mo>⁢</mo><msub><mi mathvariant="normal">m</mi><mi mathvariant="normal">j</mi></msub></mfenced><mo mathvariant="normal">+</mo><msub><mi mathvariant="normal">ω</mi><mi mathvariant="normal">C</mi></msub><mo>⁢</mo><msub><mrow><mspace width="1em" /><mi mathvariant="normal">f</mi></mrow><mi mathvariant="normal">C</mi></msub><mfenced><msub><mi mathvariant="normal">a</mi><mi mathvariant="normal">i</mi></msub><mo>⁢</mo><msub><mi mathvariant="normal">m</mi><mi mathvariant="normal">j</mi></msub></mfenced></mfenced><mn mathvariant="normal">.</mn></math><img file="EP1533941B1_D0012.tif" /></maths>

0079The following features and/or combinations of features may also constitute further embodiments of the described and/or claimed invention: <ul id="ul0007" list-style="dash"><li>The described and/or claimed method, further comprising reducing the predetermined maximum cost to a cost associated with a current network model having all traffic-carrying paths above the predetermined availability threshold;</li><li>The described and/or claimed method, further comprising the step of repeating said steps of modifying the network model, determining a cost for the current network model, and generating availability values for all traffic-carrying paths through the current network model until all paths of the current network model are above the predetermined availability threshold at a cost below the predetermined maximum cost, or until no further improvements can be made to the network model while remaining below the predetermined maximum cost, in order to determine whether a different network model with a lower cost can be obtained;</li><li>The described and/or claimed method, wherein said step of modifying said network model includes the step of increasing redundancy of components in a path with an availability value below a predetermined threshold;</li><li>The described and/or claimed method, wherein said step of modifying said network model includes the step of removing one or more network elements in a path with an availability value below a predetermined threshold;</li><li>A method of determining a communications network structure, comprising the steps of: defining multiple basic architectures; generating a cost value for each basic architecture; selecting a basic architecture of the network architecture; iteratively performing the steps of: generating a cost value for the selected network architecture; performing an availability analysis to identify which traffic-carrying paths, if any, have availability values below a predetermined threshold; and improving the selected network architecture responsive to the identified traffic-carrying paths; until an acceptable solution is achieved or determined not to exist for the selected network architecture, and if an acceptable solution is determined not to exist for the selected network architecture, selecting a different basic architecture for the network architecture;</li><li>The described and/or claimed method, wherein the step of selecting a basic architecture comprises the step of selecting the basic architecture with the lowest cost value;</li><li>The described and/or claimed method, further comprising the step of setting a maximum cost value as the lesser of a specified value and the cost value associated with a least expensive basic architecture with no paths below an acceptable threshold;</li><li>The described and/or claimed method, wherein an acceptable solution has no paths below an acceptable threshold and a cost value at or below the maximum cost value;</li><li>The described and/or claimed method, wherein, upon finding an acceptable solution, the maximum cost value is set to a lowest cost value associated with an acceptable solution for the selected network architecture;</li><li>The described and/or claimed method, and, if another basic architecture is selected as the basic architecture, iteratively performing the steps of: generating a cost value for the selected network architecture; performing an availability analysis to identify which traffic-carrying paths, if any, have availability values below a predetermined threshold; and improving the selected network architecture responsive to the identified traffic-carrying paths; until an acceptable solution having a cost value below the maximum cost value is achieved or determined not to exist for the selected network architecture;</li><li>A method of cost modeling a communications network design, comprising the steps of: performing traffic grooming of the network design; and performing express route optimization by bypassing intermediate nodes in one or more paths;</li><li>The described and/or claimed method, further comprising the step of: performing network dimensioning, where nodes and spans of a path are dimensioned to carry a specified traffic demand at a specified protection level.</li><li>The described and/or claimed method, wherein said step of modifying said network model includes the step of improving path diversity associated with a path with an availability value below a predetermined threshold.</li></ul>

0080Although the Detailed Description of the invention has been directed to certain exemplary embodiments, various modifications of these embodiments, as well as alternative embodiments, will be suggested to those skilled in the art. The invention encompasses any modifications or alternative embodiments that fall within the scope of the Claims.