A METHOD OF ALLOCATING SPARE CAPACITY TO LINKS OF A TELECOMMUNICATIONS NETWORK

The present invention relates to a method of allocating spare capacity to links of a telecommunications network, and a spare capacity allocation system.

The advent of digital telecommunications networks, in particular optical fibre networks, has made it economically viable to provide telecommunications routes with a large bandwidth and high bit rates. The networks enable telecommunications links to handle a large number of calls simultaneously, for example 1000 calls. The large traffic capacity of the links has given rise to considerable work being performed in the area of automatic network restoration and the provision of survival networks which can effectively reroute a large number of calls when a link is cut or damaged.

To enable rapid and effective restoration on link or network node failure, telecommunications networks are provided with redundant or spare capacity which can be used to reroute calls. A link is therefore considered to have a number of working channels for carrying speech and data during normal network operation, and a number of protection channels which can be used to reroute calls when another link or node fails.

Synchronous optical networks (SONET) and synchronous digital hierarchy (SDH) transmission standards provide for automatic network restoration using remotely controlled and intelligent network elements, such as digital cross connect systems (DCSs) and add drop multiplexers (ADMs), which enable fast network reconfiguration following link and nodal failures.

Most of the current work on network restoration and the allocation of spare capacity has concentrated on dealing with single-link failure, which is relatively simple, rather than providing techniques which can be used in the complex case of multi-link failure and node failure. An important factor which also needs to be taken into account, .and is often overlooked, is a restoration hop limit. The hop limit is the number of nodes in a network through which a restoration or rerouting path can pass through or "hop" without severely effecting the services on the links or nodes which have failed.

The allocation of spare capacity should also take into account economic factors, such as the costs associated with providing protection channels.

One approach, described in Sakauchi H., Nishimura Y. and Hasegawa S., "A self-healing network with an economical spare-channel assignment", GLOBECONT90, pp. 438-443, 1990, involves using a mathematical model to find a set of links for each link known as a cut set. The cut set is the set of links which for a given link cannot be allowed to fail if the given link fails because otherwise the service on the given link cannot be restored. Therefore a number of protection channels are assigned to each link in the cut set which corresponds to the number of working channels in the given link. The method however does not eliminate restoration routes which violate the hop limit. Also the method cannot be extended to multi-link or nodal failures.

Another method is discussed in Graver W.D., Bilodeau T.D. and Nenables B.D., "Near optimal spare capacity planning in a mesh restorable network", GLOBECOM'91, pp. 2007-2012, 1991, which applies a distributed approach and takes into account the hop limit. The method heuristically first finds a feasible solution, using a process termed Forward Synthesis, and then reduces redundancy whilst maintaining an effective restoration level using a process termed Design Tightening. The method however is relatively complex and possesses difficulties in adequately providing for complex failures.

A comparison of the above two methods is provided in Venables et al., "Two strategies for spare capacity placement (SCP) in mesh restorable networks", ICC93, pp. 267-271, 1993.

In accordance with the present invention there is provided a method of allocating spare capacity to links of a telecommunications network, comprising: inputting link data representing the number of working channels available on each of said links and the network nodes connected to said link; processing said link data to obtain restoration flow data representing the links which can support a restoration path for each one of said links without exceeding a node hop limit; and applying said link data and restoration data to a linear programming process which obtains a spare capacity allocation for each link on the basis that the sum of all restoration flows for each link is greater than or equal to the number of working channels of the link, the spare capacity allocation for each link is greater than or equal to sum of all restoration flows for the link and the sum of the spare capacity allocation on each link is a minimum.

The present invention further provides a spare capacity allocation system for executing the above method for links of a telecommunications network, comprising: an input part for inputting said link data; a first processing part for processing said link data to obtain said restoration flow data; and a second processing part for applying said link data and said restoration flow data to said linear programming process to obtain a spare capacity allocation for each link.

Preferred embodiments of the present invention will hereinafter be described, by way of example only, with reference to the accompanying drawings, wherein: Figure 1 is a diagram illustrating a tree search process of a spare capacity allocation system;

Figure 2 is a flow chart of a tightening procedure of the spare capacity allocation system;

Figure 3 is the layout of a network which indicates working channels on the links of the network;

Figure 4 is a histogram of total spare capacity allocated versus hop limit; and

Figure 5 is a tightening procedure of a further spare capacity allocation system.

Considering first single-link failures, in order to fully account for the hop limit in a network a traffic flow model of the network is required which takes into account all of the eligible restoration routes throughout the network. The eligible restoration routes are those which do not violate the hop limit following a single-link failure. Applying the hop limit in this manner significantly reduces the number of eligible restoration routes in very large transmission networks to quantities which can be adequately handled by conventional computing equipment.

Hereinafter, the following notation is used to represent specific data of a network: H - The hop limit value for restoration routes.

N - Number of network nodes (DCS hubs), indexed n = 1, 2, .., N.

L - Number of network links, indexed i = 1, 2, .., L.

Xi - Number of working channels through link i, i = 1, 2, .., L.

Yi - Number of spare channels assigned to link i, i = 1, 2, .., L. _ - Cost of spare channel assigned to link i, i = 1, 2, .., L. qi - The restoration level required for link i, 0 ≤ q_ ≤ 1, i = 1, 2, .., L.

Pj - Total number of eligible restoration routes (paths) which do not violate the hop limit H following the failure of link i, indexed as paths p = 1, 2, .., p. f - The "restoration flow" through the pth restoration route of link i, i = 1, 2,

.., L, p = 1, 2, .., P _j . b- - Takes the value of 1 if the pth restoration route of link i uses the link j and 0 otherwise. Fj - Total "restoration flow" through link j following the failure of link i. Z _j - Maximum "restoration flow" through link j following a single-link failure in the network.

The "restoration flow" of a link j is the spare or restoration capacity of the link j which is required to assist in providing a restoration route p for the failed link i. A restoration route p will comprise a number of connected restoration flows. A link j may form part of a number of restoration routes p. From the above it should be apparent that only data on restoration routes p which do not violate the hop limit H is considered.

For adequate restoration of a failed link, the spare capacity allocated for a link must be greater than or equal to the sum of all of the restoration flows of the link. The sum of the restoration flows which can be used by a link must also be greater than or equal to the number of working channels through the link. The costs associated with the provision of the spare capacity must also be minimised.

The allocation of spare capacity can therefore be formulated as follows:

NM _t :

Min (έ ^β _' -"w) s.t.

fu, 0, — 1» 2» ••» - , p - 1, -£, .., -T _j

The first constraints of the above formulation ensure the restoration level required. The second constraints are derived from the flow definition, from which it can be seen that the total flow Ε is calculated by summing up all flows f^ _p which use the link j, thus ignoring the flow direction, i.e. overlooking cases for which the restoration flows through link j are in opposite directions. The formulation is derived from the possibility that the hop limit might cause restoration flows, following a single-link failure, to be directed through certain links in opposite ways. This can be avoided when there is no hop limits on restoration routes. The value F^ ^j represents the expected amount of spare capacity through link j to be used following the failure of link i. The above formulation can be presented in a linear programming (LP) form in the following way:

NM ₂ :

S.t.

Σ, f > ii ' ^X r » = 1, .., I p-l

, J = 1, 2, .., N, i ≠ y p-1

= 1, 2, .., , /> = 1, 2, .., ?ι

The NM ₂ model has L ² constraints and L + P variables (P = \^_ represents all eligible restoration routes). The processing time of an LP model, when using the Simplex algorithm, dominantly depends on the number of constraints, so the above LP model is appropriate to analyse large-scale networks. The above formulation is solved for the value Z _j which represents the expected amount of spare capacity which should be .assigned to link j.

Further constraints can be added to NMj, such as including boundary constraints on spare capacity values, i.e. R^ ≥ Z _j ≥ r _j} j = 1, 2, .., N, which may be derived from maintenance and other considerations. A time consuming factor when using the above model is to find all the eligible routes P, which is of the order O[L(D - 1) ^H ] - O[N(D - 1) ^H+1 ], where D is the average number or links connected to or connectivity of the network nodes. A very large transmission network for which, for example, N = 100, D = 5 and H = 7, gives L ² - 62,500 constraints and L + P - 4.5 ^• 10 ⁶ variables, yet this can still be solved with conventional computing facilities. Moreover, it is possible to reach for this network an optimal solution with significantly reduced effort by analysing solutions for which H < 7, as discussed hereinafter. In order to find all eligible restoration routes of a certain link i connecting two nodes nj and n-j, an efficient tree search from one node 2 to the other 4 is used which is composed of H stages 6, and is schematically shown in Figure 1.

The values Z _j , obtained from the model NM ₂ , are rounded up to a complete integer solution for spare channel assignment, namely: Y _j = |Z _j |, j = 1, 2, .., N, where |Z _j | is the lowest integer which is greater or equal to the value Z _j .

Spare capacity assigned to networks in accordance with the assignment values Y _j can be determined using software developed on a Sun Microsystems Sparc II workstation. The spare capacity allocation method can also be executed by an application specific hardware device which would rapidly execute the allocation procedure and could also be developed so as to automatically adjust spare capacity within a configured network.

The software includes four main modules, an input module, a network module, a LP module, and a spare capacity module. The input module includes an input interface which allows the working channel data X _j for each link and node data specifying the links connected to the nodes to be inputted for a network, together with the hop limit H, restoration levels and cost values c_. On the basis of the network data provided, the network module then determines the eligible restoration routes P which do not violate the hop limit H and generates the P- and δ- restoration route data. The linear programming module uses the input data and the data generated by the network module to solve NM ₂ for the unknowns Z _j and ζ _p . The linear programming module uses a linear programming package produced by CPLEX that is based on the Simplex algorithm. The 2- values are rounded up to integers Y _j . The spare capacity module provides the spare capacity assignments Y- as an output, together with the restoration flows f- _p .

A listing of the software is provided on pages 21 to 47. The file assign_cap.c includes the main procedure which calls the modules, and asdef.h is a header file. The file spare_fun.c includes the input module and the linear programming module, max_flow.c includes the spare capacity module and short_alg.c includes the network module.

The Y _j values are, however, tightened after having been rounded up. The tightening process is performed by finding for each link i a maximum flow value Mj, using the following LP formulation:

NM ₃ :

s.t.

-°t

∑ ~ ' f _iJ> ≤ Y _j , j - 1, 2, .., N, j ≠ i p-\

After using NM ₃ , for all links, it is possible to associate each link i to one of two sets Sj and S-j, using the rule: i S S, if Mj - qj - Xj fc l, otherwise i E S ₂ as I-vt ≥ q _j • Xj, based on the first constraints of NM ₂ and on Y _j ≥ Z _j , j = 1, 2, .., N. The set S _j represents all links for which the desired restoration level is ensured, even if any signal spare capacity value Y _j is reduced by 1. The set S ₂ represents links for which reducing certain spare capacity values Y _j by 1 might decrease their desired restoration level. Positive "shadow prices" associated with values Y _j , appearing in the constraints of NM ₃ and related to links i, i E S__, clearly indicate Y _j values which cannot be reduced. Shadow prices are obtained as a by-product when solving LP models. The shadow prices indicate how much extra spare capacity would be required if the number of working channels X_ is increased by 1 for link i.

A tightening procedure 10, as shown in Figure 2, is used to tighten the Y _j values based on a shadow pricing test (SPT). The procedure beings at step 12 by setting i = 0 and then solving NM ₃ at step 14 for all links until i = N at step 16. The loop in which NM ₃ is solved includes a step 15 where the restoration level requirement is checked for each link. The sets S, and S ₂ are updated at step 18, on completing NM ₃ . A check is then made at step 20 to determine if the SPT is satisfied for at least one link. A link j satisfies the SPT if the shadow prices, associated with the constraints Y _j for all NM ₃ models related to links i, i 6 S^ have the value 0 (shadow prices of NM ₃ are either positive or 0). The value Y _j is therefore a potential candidate to be reduced by 1. At the beginning of the tightening procedure several links might satisfy the SPT. In such cases,

the link with the higher value C _j should be selected as a candidate. It should be noted that the flow values f- _p and the associated paths p respectively indicate the link i recommended capacity and routes.

If the SPT is satisfied, then a value Y _j is reduced by 1 for a link j which satisfies the SPT, at step 22. If the SPT is not satisfied at step 20 then the procedure 10 is stopped. If during the solution of NM ₃ for a link i produces a negative response at step 15, i.e. the restoration level required is no longer satisfied, to procedure 10 proceeds to step 24 so as to increase the last reduced value Y _j by 1 so as to again maintain the required restoration level. After step 24, a check is made to see whether any other link j satisfies the SPT at step 26, and if not the procedure 10 is stopped. Otherwise if another link j does satisfy the SPT then the procedure 10 proceeds to step 22.

An example network 30 is shown in Figure 3 which has been considered previously in Yang C. and Hasegawa S., "FITNESS: Failure immunization technology for network service survivability", GLOBECOM'88, pp. 1549-1554, 1988 and also analysed in Sakauchi H., Nishimura Y. and Hasegawa S., "A self-healing network with an economical spare-channel assignment", GLOBECOM'90, pp. 438-443, 1990, Grover W.D., Bilodeau T.D. and Venables B.D., "Near optimal spare capacity planning in a mesh restorable network", GLOBECOM'91, pp. 2007-2012, 1991, and Herzberg M., "A decomposition approach to assign spare channels in self-healing networks", GLOBECOM'93, 1993. The numbers on the links 32 between the nodes 34 are the Xj values. The method described above is used to analyse this network example for several hop limit factors H ≥ 2 and for the sake of comparison c- = t^ = 1, V _s = 1, 2, .., N.

The graph of Figure 4 presents the values ∑ _j Y _j obtained for the hop limit factors H = 2, 3 .., 8. The upper figures are the final values (∑ _j Y _j - final) and the lower figures are the values obtained from NM ₂ (∑ _j Y _j - ?__). This graph illustrates the trade-off between spare capacity and hop limit. The example clearly indicates that for highly connected networks the spare capacity required for adequate restoration or survivability rapidly converges to a lower bound with the increase of the hop limit factor, thus, an effective spare capacity solution can be found with relatively small hop limits and effort,

and that there is no gain when setting large hop limit values. Table 1 on page 16 details the final values Y _j .M _j obtained for H = 2, 3, .., 6.

An output of the value Z, and corresponding shadow prices for each link i produced by the software on performing NM ₂ for a hop limit of four is provided in Table 2 shown on page 17. The same output produced following execution of NM ₃ for a hop limit of four is provided in Table 3 on page 17. Table 4 shown on pages 18 and 19 is a further output produced by the software following execution of NM ₃ for a hop limit of 4. The table lists the links i and the eligible restoration paths p. The paths are then specifically defined by listing the node numbers included in each path. The restoration flows _jP determined for each link i and path p are listed in the right-hand column of Table 4.

The spare capacity allocation method can also be extended to produce a survivable network for multi-link and node failures, using the following notation:

H - The hop limit value for restoration routes.

N - Number of network nodes (DCS hubs) _j , indexed n = 1, 2, .., N.

L - Number of network links, indexed j = 1, 2, .., L. d, - Degree of node n (the number of links which are directly connected to node n). In a backbone network d,. ≥ 2.

D - Average degree per node, as discussed previously, which by definition D

= ∑ ^N .=. VN. K - A set of possible failure scenarios (FSs) to be considered, indexed k = 1,

2, .., K. FSs may include single-link failures, multi-link failures and node failures.

X _j - Number of working channels of link j, j = 1, 2, .., L.

Y _j - Number of spare channels assigned to link j, j = 1, 2, .., L.

C _j - Cost of a spare channel assigned to link j, j = 1, 2, .., L. When there are no major differences between link lengths all cost values are assigned the value C _j = 1, however, for vast and expensive networks, e.g. international, different cost coefficients may be included. G - Group size of transmission equipment. The value G represents the

maximal number of channels being carried by a single transmission system and is dictated by the transmission standards SONET and SDH. The actual value of G is derived from channels' bit rate.

C _j - Cost of a transmission system assigned to link j. Practically C _j <•* G • c-. S _j Number of transmission systems assigned to link j to carry spare and working capacities. Clearly S _j ≥ (Y _j + X _j )/G.

M - Number of network's node pairs (NPs), indexed i = 1, 2, .., M = N(N - l)/2. Without loss of generality, any NP which is directly connected by link j is assigned the index i = j, thus, the first L NPs represent directly connected NPs.

I _k - Set of NPs where their immediate connection is affected by FS k, k = 1, 2, .., K. |I _k | = 1 if k represents a single-link figure, |Ij.| = a if k represents a multi-link failure of a links. |I = d _B (d _B - l) 2 if k represents a node failure for node n. |I _k | is the cardinality of the set 1^. J _k - Set of links which are affected by FS k, k = 1, 2, .., K. For single-link and multi-link failures |J _k | = |I _k |, while for a failures of node n |J _k | =

W _u - Number of working channels associated with NP i being affected by FS k. The values W are determined by the working channels X _j . For single-link and multi-link failures W = X-, k = 1, 2, .., K, i E I _k . q^ - The minimal restoration level required for NP i, when FS k occurs, 0 ≤ q^ ≤ 1, i = 1, 2, .., M, k = 1, 2, .., K. P _} - Total number of all eligible restoration routes associated with NP i which do not violate the hop limit. For a given network, the value Pj depends predominantly on the hop limit value, the larger the value H the larger ?_ usually is. P - Total number of eligible restoration routes associated with NP i which do not violate the hop limit following FS k, indexed p = 1, 2, .., P _iJk . For most FSs Pj < P _j as the link sets J _k can not be used for restoration when FS k occurs. fy^ _p - "Restoration flow" through the pth restoration route of NP i following FS k, k = 1, 2, .., K, i e I _k , p = 1, 2, .., P^.

j _ δi > p Takes the value of 1 if the pth restoration route of NP i following FS k uses the link j and 0 otherwise.

Total "restoration flow" through link j for NP i following FS k.

G _k ^j Total "restoration flow" through link j following FS k.

Maximum "restoration flow" required through link j following any FS.

A model for multi-link and node failures needs to additionally take into account the manner in which the connections of node pairs are affected by an FS, and an adequate restoration level needs to be obtained for nodal pairs. This accounts for failure of the link or links between a pair and the effect on all of the links connected to a node of a pair if the node fails.

From the notation, and based on NM _] , the task of spare capacity assignment can be formulated as:

NM _*

s.t.

fit, ^≥ It* ' ^W ιtf k = 1, 2, .., K, i 6 I _k p-l

k = 1, 2, .., K, i ~ l _v j * J _k

Ol - i, K ⁼ L _f 2t _{9 **9} A. J — i_ _f _, _{9 aay} , fit, ^~ °> k = 1, 2, .., K, i E l _v p ~ 1, 2, .., _? _u

The above formulation can then be transformed to an LP model as follows:

NM ₅ :

L

Min Σ <7

S.t. ^r t*

Λ*, ^≥ «t* ^* > k = 1, 2, .., K, i €

P-l

- /<jϋ, ^≥ °> * - !» ² » ^•• » > ' ^e !» ² » ^•• » ^■ *» J ' $ ^J t ^ ^{≥ 0} _' Vfc = 1, 2, .., K, i - l _e p = 1, 2, .., U,

Plausible constraints can be added to the model NM _S . For example, boundary constraints on flow values may be included, namely: V _j ≤ Z _j ≤ V _j , j = 1, 2, .., L, which may be derived from physical limitations or other practical considerations. An LP solution for the flow values Z _j and ^ _p may not be purely integer. For asynchronous transfer mode (ATM) networks, restoration flows f-^., and protection capacities are not restricted to integer values as bit-stream rates are controlled by VP switches at the cell level. The model NM ₅ can readily be used for such cases and the values Y _j = Z _j , j = 1, 2, .., L as well as the flows f^,, obtained represent optimal spare capacities and optimal restoration flows, respectively.

For an ATM network which uses bandwidth supplied by synchronous transmission systems such as SONET/SDH, the restoration flows can still be non integer, however, spare channels assigned to each link in the ATM network are required to be integer. A feasible integer solution of spare capacity can be obtained as for the single-link failure case, by rounding up the values Z _j to obtain the spare capacity values Y _j , namely: Y _j = |Z _j |, j = 1, 2, .., L. In general, for synchronous transport networks, both spare capacities and restoration flows are required to be integer. A tightening phase aims to slightly improve the solution by reducing selected values Y _j in an iterative way, using this time a series of LP formulations NM^/), / = 1, 2, .., L, as follows:

NMJl):

S.t.

^r u

Σ f*, ~ « ^' *, O* k = 1, 2, .., K, i e I _k p-l

l, 2, .., K, j C J _k k = 1, 2, .., K, i € !„ p = 1, 2, .., J

where Y _y = Y _j - 1 if j = /, else Y _j = Y _j . The LP formulation NMg( ) checks whether its constraints are satisfied for all FS k when the spare capacity Y _z of one link is reduced by 1 whilst the remaining links are unchanged. The solution of NM^/) might be either feasible or infeasible. LP models produce an optimal solution, an infeasible solution or an unbounded solution. An infeasible solution is one which does not satisfy all of the constraints of the model. Feasibility of NM^ ) indicates that restoration levels can be achieved following a FS k even when the spare capacity Y, is reduced by 1.

The tightening phase is performed by a tightening procedure 40, as shown in Figure 5, which starts an iteration at step 42 by setting an iteration value to zero. At step 44 the procedure 40 then enters a loop where all of the failure scenarios k are checked using NM _β , a link / is selected for the NMg test and NMg solved. A check is made at step 48 to determine if NMg is feasible. If the solution for NMg is feasible, the iteration value is increased by one and the spare capacity value Y, is reduced by 1 at step 52, and the procedure 40 returns to step 44. If an infeasible solution is encountered at step 48, a check is made at step 54 to determine if all of the links have been tested, and if not then the procedure 40 moves onto the next link / at step 44. If an infeasible solution is encountered, and all of the links / have been tested, then the procedure 40 halts.

The models NM ₅ and NM _f i can be modified to address the fact that transmission

systems are generally modular. The aim is to find optimal assignment of transmission systems which carry both working and spare capacities. A major factor of this variant is the modularity value G which represents the maximal number of channels carried by a single system. The variables S _j represent the number of transmission systems required for link j to carry X _j plus Y _j channels. Model NM ₅ is modified for this case to the form:

NM ₇ :

s.t.

^r

G ' Sj - ∑∑ ^ 'f^ ≥ Xj, k = 1, 2, .., K, j = 1, 2, .., L, j € J _k iel _t p-l fa, * k = 1, 2, .., K, i e h, p - 1, 2,

The values S _j are now rounded up to obtain integer numbers of transmission systems. In order to find an improved solution the rounded up values are tightened using the following max-flow formulation:

NM _t :

^Γ U

Max l^ tLi s fi cj, k-l iel _k p-l

S.t.

Σ - 1* ' ^w i* * = i. ² » ^•• > * ' e / ₄

∑∑ ^δ ^ '^ ^ - ^ - ^ * = 1. 2, .., iT, 7 = 1, 2, ... , y C J, ιe/ _t /».l ^ ≥ 0, * - 1, 2, .., K, i ε I _e p = 1, 2, .., _? where

The above allocation methods provide a relatively simple process for assigning spare capacity for large networks whilst advantageously taking into account hop limits, and if desired multi-link and node failures.

Spare capacity assignment with restricted (low) hop limits has several advantages:

i. Restoration times are usually fast as less network elements are involved and fewer messages are sent and acknowledged during the restoration procedures;

ii. The restoration information base (RIB) is usually reduced since each network node is associated with only a few link failures. This is significant if a distributed approach with pre-planning is considered since the RIB at each node is updated frequently;

iii. Restoration is more reliable as the number of network elements included in the restoration routes is small;

iv. The network is more capable of handling independent and simultaneous failure events as less network elements are involved with each failure scenario.

30 TABLE 1

Spare Capacity Assignment Link i Workin X S are_ . Shadow

Spare Capacity Assignment

Link J Workingxj Spare Z. Shadow

1 74 54.00 2.00

2 71 1.00 1.00

3 71 19.00 0.75

4 53 12.00 0.00

5 55 20.00 1.00

6 52 74.00 0.00

7 53 20.00 1.00

8 16 71.00 0.00

9 68 19.00 0.00

10 59 18.00 0.00

11 51 36.00 0.50

12 48 27.00 0.00

13 16 42.00 1.00

14 81 3.00 0.00

15 50 1.00 0.00

16 48 22.00 0.00

17 47 28.00 0.00

18 41 16.00 1.00

19 57 8.00 0.00

20 64 22.00 0.00

21 78 34.00 2.00

22 65 35.00 0.00

23 34 78.00 1.00

TABLE 3

TABLE 4

10

15

/********** ****** * ** » ***•«****«

The header file and function list for the spare capacity assignment program.

#include "cpxdefs.inc" /* CPLEX header file */

#include <stdio.h> #include <string.h> #include <math.h>

/********* ********** ********** _spare fun.c ********** **•*»•»**» *•»*»•*«* void Introduction () ; void Parameter (int *vertices, int *edges, int *hops); void Input_Data (int nodes, int links, int *connect, int *work) ; void Var_Bound (double *xub, double *xlb, int mc); void Object (int mc, double *c, int flw) ; void Int_RHS (int *work, double *b, char *sense, int mc, int mr, int links); void Constraint (int *mbeg, int *mcnt, int *mind, double *mval, int mc, int mr, int nodes, int links, int *connect, int *paths, int flw, int num. int *rhs2) ; void Spare_Dec (int mc, int mr, int nodes, int links, double *spare_cap, int *work_cap, int *paths, double *pi, int *rhsind, double *x, int hops, int *update, int *stut, int *incr) ; void Check_Flow (int mc, int mr, int nodes, int links, int *paths, double *x, int ^# work_cap, int *okay, int hops); void Output_Results (int *work, double *spare, int iteration, int mc, int mr, double *distrb, int nodes, int links, double *pi, int *paths, int hops, double *x, double object) ; max flow.c void Max_Flow (int *con, double *spare, int *work, int *cut, double *dist, int links, int nodes, int *feas, int *cutlinks, int hflag) ; short_alg.c void Short_Alg (int *con, int *constr, int links, int nodes, int hops, int *num, int *num2);

/*

/*

This program has been written to implement the spare capacity assignment algorithm for network dimensioning. This program uses CPLEX to solve the Linear Programming formulation.

CPLEX is a product of CPLEX Optimization, Inc. (USA)

#include "asdef.h" main () {

/*....Parameter decleration....*/ char filenam[20]; int i, j. k; int nodes, links, iteration, feasible; int update, check, hops, deer, okay; double object; int *work_caρ, *connect, *spare_int, *paths; double *spare_cap, *distrb, *pi2; int •mincut, *cutlinks, *stut, *incr; int hflag, nflw, num. index2, counter;

/*....CPLEX specific variables are declared....*/ char *probname = "capassign"; int objsen = 1; char ^♦ filename = "example"; int mac, mar; double •σbjx, *rhsx; int *rhs2; char *senx; int •rnatbeg, *matcnt, *matind, *cstat, *rstat; double *matval, *bdl, *bdu; char ^♦ dataname, *objname, *rhsname, "rngname, *bndname; char *cstore, *cname, *rstore, *rname; int macsz, marsz, matsz; unsigned cstorsz, rstorsz; int lpstat; double obj;

/* . . . . Introduction and variable input. . . .*/

Introduction ( ) ;

Parameter (&nodes , &links , &hops) ; hops = hops - 1 ;

/*....Assign the appropriate amount of memory....*/ spare_cap = (double *) malloc (links * sizeof(double)) ; spare_int - (int *) malloc (links * sizeof(int)) ; work_cap = (int *) malloc (links * sizeof(int)); stut = (int *) malloc (links * sizeof(int)) ; incr = (int *) malloc (links * sizeof(int)) ; if (!spare_cap |j !spare_int || !work_cap j| !stut j| ϋncr) goto TERMINATE; connect = (int *) msilloc ( (nodes*nodes) * sizeof(int)) ; distrb = (double *) malloc ((nodes*links) * sizeof(double)) ; paths = (int *) malloc ((nodes*2000) * sizeof(int)) ; mincut = (int *) malloc ( (nodes*links) * sizeof(int)) ; cutlinks = (int *) malloc (links * sizeof(int)) ; if (!connect JJ !distrb J| !paths || !mincut |j !cutlinks) - goto TERMINATE;

/* .Input the required information, working capacity & topology....*/

Input_Data (nodes, links, connect, work_cap) ;

/*....The next stage is to determine the eligible paths and the....*/ /*....number of variables (mac) ....*/ printf(" Finding the appropriate paths....\n") ;

Short_Alg (connect, paths, links, nodes, hops, &nflw, &num) ; mac = nflw + links; mar = links + (links*links) ;

/ ^♦ ....Allocate memory for the LP formulation - CPLEX....*/

objx = (double *) malloc (mac * sizeof(double)) ; rhsx = (double *) malloc (mar * sizeof(double)) ; rhs2 = (int *) malloc (mar * sizeof(int) ) ; senx = (char *) malloc (mar * sizeof(char)) ; bdl = (double *) malloc (mac * sizeof(double)) ; bdu = (double *) malloc (mac * sizeof(double)) ; if (!objx I! !rhsx j| !rhs2 |j !senx j| !bdl j| !bdu) goto TERMINATE; matbeg = (int *) malloc (mac * sizeof(int)) ; matcnt = (int *) malloc (mac * sizeof(int)) ; matind = (int *) malloc ( (num+nflw+(links*links) ) * sizeof(int) ) ; matval = (double *) malloc ((num+nflw+(links*links)) * sizeof(double)) ; if (!matbeg j | !matcnt || !matind |j !matval) goto TERMINATE; x = (double *) malloc (mac * sizeof(double)) ; pi = (double *) malloc (mar * sizeof(double)) ; pi2 = (double *) malloc (mar * sizeof(double)) ; if (!x I! !pi I! !pi2) goto TERMINATE;

/*....Set up the LP formulation....*/

START:

Constraint (matbeg, matcnt, matind, matval, mac, mar, nodes, links, connect, paths, nflw, num. rhs2) ;

Object (mac, objx, nflw);

Int_RHS (work_cap, rhsx, senx, mac, mar, links);

Var_Bound (bdu, bdl, mac); counter = 0; update = 0; deer = 0; for (i=0; Klinks; i++) *(stut+i) = 0;

SIMPLEX:

/*....Part I - Loading, optimizing and obtaining a solution to the original problem....*/ lp = loadmprob (probname, mac, mar, 0, objsen, objx, rhsx, senx, matbeg, matcnt, matind, matval, bdl, bdu, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, mac, mar, (num+nflw+(links*links) ) , 0, 0, 0, 0, 0); if (lp == NULL) goto TERMINATE; setlogfile (NULL) ; setscr_ind (0); status = setitfoind (0, itoosmall, itoobig); if (status) goto TERMINATE;

status = setitlim (10000, &toosmall, &toobig) ; if ( status ) setitlim (toobig, itoosmall, &toobig) ;

....Optimize the problem and obtain solution....*/ status = setpreind (1); if (status) goto TERMINATE; if (counter == 0) printf(" Starting the LP \n"); status = optimize (lp); if (status) { deer = 1; goto ROUNDING;

} status = solution (lp, ilpstat, iobj, x, pi, NULL, NULL); if (counter == 0) { printf("Objective = Xlf\n", obj); object = obj; for (i=0; i<mar i++) *(pi2+i) = *(pi+i);

} if (status) goto TERMINATE; iteration = getitc (lp); unloadprob(&lp) ; counter*+;

SPARE: for (i=0; Klinks; i++) { if (counter == 1) *(spare_cap+i) = *(x+nflw+i); }

RESULTS:

/*....The next stage is to round the results to an integer solution....*/

/*. .Furthermore, we attempt to reduce the spare capacity using a ....*/ /*. .heuristic. This is on the premise that the solution obtained ....*/ /*. •from the LP is -an optimum .and non-integer....*/ if (counter -- 1) {

Max_Flow (connect, spare_cap, work_cap, mincut, distrb, links, nodes, ^feasible, cutlinks, hflag) ; check = 0; for (i=0; Klinks; i++) { *(incr+i) = 0;

*(spare_int+i) = ceil(*(spare_cap+i)) ; if (*(spare_int+i) != *(spare_cap+i)) { *(incr+i) = 1; check = 1;

} *(spare_cap+i) = *(spare_int+i) ;

} }

...In order to determine the flow distribution we need to find....*/

/*.....and update the variable bounds, the obj. function and the ....*/ /* rhs vector....*/ if ((check == l)4&(counter == 1)) { objsen = -1; /*....This is to convert the LP to maximisation....*/ for (i=nflw; Kmac; i++) { *(bdu+i) = 0.0; *(objx+i) = 0.0; } for (i=0; Knflw; i++) { *(objx+i) = 1.0; } for (i=0; Knar; i++) { if (*(rhs2+i) > 0) { index2 - *(rhs2+i) - 1; *(rhsx+i) = - (*(spare_cap+index2)) ; } } goto SIMPLEX;

} ROUNDING: okay = 0;

Check_Flow (mac, mar, nodes, links, paths, x, work_cap, &okay, hops); if ((deer == l)|j(okay == 1)) {

*(spare_cap+(update-l)) = (*(sρare_cap+(update-l) )) + 1; check = 0; deer = 0; for (i=0; Kmar; i++) { if (*(rhs2+i) > 0) { index2 = *(rhs2+i) - 1; *(rhsx+i) = - (*(spare_cap+index2)) ; } } } if (check == 1) {

Spare_Dec (mac, mar, nodes, links, spare_cap, work_cap, paths, pi, rhs2, x, hops, tupdate, stut, incr) ; if (update > 0) {

*(stut+(update-l)) = l; for (i=0; Kmar; i++) { if (*(rhs2+i) > 0) { index2 = *(rhs2+i) - 1; *(rhsx+i) = - (*(spare_cap+index2)) ; } } goto SIMPLEX;

} else { check = 1; if (update > 0) goto SIMPLEX;

}

MAXFLOW:

Max_Flow (connect, spare_cap, work_cap, mincut, distrb, links, nodes, {.feasible, cutlinks, hflag) ;

OUTPUT:

Output_Results (work_cap, spare_cap, iteration, mac, mar, distrb, nodes, links, pi2, paths, hops, x, object);

TERMINATE: if spare_cap) free((char *) spare_cap); if spare_int) free((char *) spare_int) ; if work_cap) free((char *) work_cap); if connect) free((char *) connect); if distrb) free((char *) distrb); if objx) free((char *) objx); if rhsx) free((char *) rhsx); if senx) free((char *) senx); if bdl) free((char *) bdl); if bdu) free((char *) bdu); if x) free((char *) x) ; if pi) free((char *) pi); if matbeg) free((ch.ar *) matbeg) ; if matcnt) free( (char *) matcnt) ; if matind) free( (char *) matind) ; if matval) free((char *) matval) ; return(0) ; } /*....end main....*/

/*

The functions contained within this file are used to determine the appropriate spare capacity assignment for a meshed SDH networks.

."/■include "cpxdefs.inc" /* CPLEX header file */

#include <stdio.h> ^include <string.h> ^include <math.h> *«*****•* ********** ********** ***»**•**» ********** ********** *********, void Introduction ()

{ char answer[3]; printf("\n\n *********»********»*********************»******\ _n ») . printf(" * Spare Capacity Assignment Programme *\n") printf(" * Telecom Research Laboratories *\n") printf(" **»*****»**********»***************************\ _n <<) printf("\n Do you wish to continue (y/n) ? "); scanf("JSS", answer) ; if (answer[0] == 'n') exit(l); return;

/******* * * ***** < void Parameter (int *vertices, int *edges, int *hops)

{ printf("\n Please enter the following information\n") ; printf(" The number of nodes/vertices = "); scanf("2d", vertices); printf(" The number of links/edges = "); scanf ("%d" , edges); printf ( " The hop limit = " ) ; scanf ("2d" , hops) ; return; }

/*

void Input_Data (int nodes, int links, int *connect, int *work)

{

FILE *input; char filename[20]; int i, dummy; printf("\n File describing the connectivity matrix : "); scanf("/Us", filename); if ((input = fopen( filename, "r")) == NULL) { printf("Cannot open file!\n"); exit(l); } for (i=0; K(nodes*nodes) ; i++) { if (fscanf(input,"2d", idummy) != EOF) { *(connect+i) = dummy; } } fclose(input) ; printf(" File containing the working capacity : "); scanf("2s", filename); if ((input = fopen( filename, "r")) == NULL) { printf("Cannot open file!\n"); exit(l); } for (i=0; Klinks; i++) { if (fscanf(input,"2d", &dummy) != EOF) { *(work+i) = dummy; } } fclose(input) ; return; }

/********♦ ********** *«*••••*** *••••**•• I void Var_Bound (double *xub, double *xlb, int mc)

{ int i; for (i=0; Kmc; i++) { *(xub+i) = INFBOUND; *(xlb+i) = 0.0;

} return;

/** * * ** < void Output_Results (int *work, double *spare, int iteration, int mc, int mr, double *distrb, int nodes, int links, double *pi, int *paths, int hops, double *x,

double object)

{ int i, j, k, a, b; char filename[20];

FILE *output; double total_spa, total_wkg, total_flow, tflow; int length, nflw, old_linc, line, count, old_length, flow_int; int nonint; double *sumx; double *sumy, sum; double *flow_dist; double *dist_mod; hops++; nflw = mc - links; nonint = 0; dist_mod = (double *) malloc ( (nodes*links) * sizeof(double)) ; sumx = (double *) malloc (hops * sizeof(double)) ; sumy = (double *) malloc (hops * sizeof(double)) ; flow_dist = (double *) malloc ((hops*links) * sizeof(double)) ; if (!dist_mod || !sumx || !sumy || !flow_dist) { printf("Memory allocation error!\n") ; exit(l); } printf(" Please enter a filename to write the results to : "); scanf("2s", filename); if ((output = fopen( filename, "wr")) == NULL) { printf("Cannot open file!\n"); exit(l); } printf("\n\n Spare Capacity Assignment (2d,2d):\n", mr, mc); fprintf(output,"\n Program : assign_cap.c\n") ; fprintf(output," Iterations = 2d\n", iteration); fprintf(output," Objective (Initial) = 21f\n", object); fprintf(output,"\n\n Spare Capacity Assignment (2d,2d):\n", mc, mr) ; printf(" Link Working Spare Shadow\n"); fprintf(output," Link Working Spare Shadow\n"); for (i=0; Klinks; i++) { if (*(pi+i) < 0.00001) *(pi+i) = 0.0; printf(" 23d 23d 25.21f 25.21f\n", (i+1), *(work+i), *(spare+i) , *(pi+i)) ; fprintf(output," 23d 23d 25.21f 25.21f\n", (i+1), *(work+i), *(spare+i), *(pi+i));

}

/*. The next stage is to determine the flow distribution....*/

/*....and the corresponding paths, found by solving the LP....*/ tflow = 0; length = 0; old_length = 2;

old_linc = 1; for (i=0; Knflw; i++) { line = *(paths*(i*nodes)) ; if (line != old_linc) {

*(flow_dist+((length-2)*links)+(old_linc-l)) = tflow; if (flow_int < tflow) nonint = 1; tflow s 0; flow_int = 0; old_linc = line; old_length = 2;

} a = *(paths+(i*nodes)+l) ; b = *(paths+(i*nodes)+2) ; length = 0; count = 3; while ((a!=0)ti(b!=0)) { a = b; b = *(paths+(i*nodes)+count) ; count*+; length++;

} if (length > old_length) {

*(flow_dist+((length-3)*links)+(linc-1)) = tflow; old_length = length;

} flow_int = flow_int + floor(*(x+i)) ; tflow = *(x+i) + tflow; if (i==(nflw-l)) {

*(flow_dist+((length-2)*links)+(linc-1)) = tflow;

} } if (nonint) fprintf(output,"\n There are non-integer flows....");

/*....Determine the totals for each quantity....*/ total_spa = 0; total_wkg * 0; total_flow = 0; for (k=0; k<links k++) { total_spa = total_spa + *(spare+k); total_wkg = total_wkg + *(work+k); total_flow = total_flow + *(distrb+(k*nodes)+(nodes-l)) ;

} / ^♦ ....Determine the percentage of the working capacity....*/ for (i=0; Khops; i++) { *(sumx+i) = 0; sum = 0; for (k=0; k<links k++) { sum a sum + *(flow_dist+(i*links)+k) ;

} *(sumx+i) = sum; *(sumy+i) = (sum/total_wkg)*100.00;

if (* (sumy+i) > 100.0) * (sumy+i) = 100.0; }

/* Output the table of results showing the flow distribution */ fprintf(output,"\n Flow distribution (taken from solution) :\n\n") ; fprintf(output," LINK |"); for (i=2; K(hops+l); i++) { fprintf(output," 2d ",i) ;

} fprintf(output."| MAXM | WKIG | SPAR \n"); fprintf(output," ") ; for (i=2; K(hops+l); i++) { fprintf(output," ") ;

} fprintf(output," \n"); for (j=l; j<(links+l); j++) { fprintf(output," 23d !", j); for (i=2; K(hops+l); i++) { fprintf(output,"24.01f ", *(flow_dist+((i-2)*links)+( -1))) ;

} fprintf(output,"!2"+.01f ! 23d ^" ! 23-01f\n",

*(distrb+((j-l)*nodes)+(nodes-l)),

*(work+(j-l)), *(spare+(j-l))); } fprintf(output," "); for (i=2; K(hops+l); i++) { fprintf(output," ") ;

} fprintf(output," \n"); fprintf(output." REST. |"); for (i=2; K(hops+l); i++) { fprintf(output," %-i.QlT ". *(sumx+(i-2))) ;

} fprintf(output,"| 24.01f | 24.01f |2<+.01f\n", total_flow, total_wkg, total_spa) ; fprintf(output," (2) !") ; for (i=2; K(hoρs+l); i++) { fprintf(output," 25-llf". *(sumy+(i-2))) ;

} fprintf(output,"| \n") ; fclose(output) ; return; }

/********* ********** ********** ********** ****•*•*•* ***» I void Object (int mc, double *c, int flw) {

int i; for (i=0; Kflw; i++) { *(c+i) = 0.0;

} for (i=flw; Kmc; i++) { *(c+i) = 1.0;

} return;

/****** ******* ********** ********** ********** ****** *****»**< void Int_RHS (int *work, double *b, char *sense, int mc, int mr, int links)

{ int i; for (i=0; Klinks; i++) { *(b+i) = *(work+i); *(sense+i) = 'G';

} for (i=links; Kmr; i++) { *(b+i) = 0.0; *(sense+i) = 'G';

} return;

}

/****** **** ******* ******* ***** void Constraint (int *mbeg, int *mcnt, int *mind, double *mval, int mc, int mr, int nodes, int links, int *connect, int *paths, int flw, int num. int *rhs2)

{ int i, j, k; int line, index, a, b, c, count, accum, offset, sum, common; int old_linc; int *ccount, *counter, *clink;

/*....In this function we make use of the CPLEX definitions to reduce....*/ /*....the amount of memory to store the constraint matrix....*/ ccount = (int *) calloc(links, sizeof(int)) ; counter = (int *) calloc(links, sizeof(int)) ; clink = (int *) calloc(links, sizeof(int)) ; if (!ccount i! !counter jj !clink) { printf("Memory allocation error - constraint2\n") ; exit(l) ;

} for (i=0; Kmr; i++) { *(rhs2+i) = 0.0; } for (i=0; Klinks; i++) { *(ccount+i) - 0;

* (counter+i) = 0; }

/* Set up the arrays that are used by the CPLEX libraries */ for (j=0; j<links j++) { for (k=0; k<links k++) {

*(mval+(flw+num)+k+(j*links)) = 1.0; *(mind+(flw+num)+k+(j*links)) = links*(k*links)+j;

} *(mbeg+flw+j) = (flw+num)+( *links) ; *(mcnt+flw+j) = links; } for (j=0; j<links j++) *(rhs2+index+j) = (j+1); accum = 0; index = 0; old_linc - -1; for (i=0; Kflw; i++) { line = *(paths*(i*nodes)) ; if (line != old_linc) { old_linc = line; index = index * links;

}

*(mval+accum) = 1.0; *(mind+accum) = line .- 1; *(mbeg+i) = accum; a = *(paths*(i*nodes)+1) ; b = *(paths+(i*nodes)+2); count = 1; common = 0; while ((a!=0)&&(b!=0)) { line = *(connect+((a-l)*nodes)+(b-l) ) - 1;

*(mval + accum + count) = -1.0;

*(mind + accum + count) = (index+linc) ; a = b; b = (*(paths*(i*nodes)+count+2)) ; count*+;

} *(mcnt+i) = count; accum = accum + count;

} return;

}

/»******** ********** ********* *** ****** I

void Spare_Dec (int mc, int mr, int nodes, int links, double *spare_cap, int *work_cap, int *paths, double *pi, int *rhsind, double *x, int hops, int *update, int *stut, int *incr) { int length, old_length, old_linc, line, check; int i, j, k, a, b, count, nflw, dummy; double tflow; double *flow_dist, *sp_dist; int *con;

/ ^♦ ....Initialise the parameters....*/

^♦ update = 0; nflw = mc - links; flow_dist = (double *) malloc ((hops ^# links) ^♦ sizeof(double)) ; con = (int *) malloc ((links) ^♦ sizeof(int)) ; sp_dist = (double ^♦ ) malloc ((links ^# links) ^♦ sizeof(double) ) ; if (!flow_dist ϋ Icon j| !sp_dist) { printf("Memory allocation error!\n"); exit(l);

}

/ ^♦ ....Determine the flow distribution so that we can use the max-flow....*/ tflow = 0; length = 0; old_length = 2; old_linc = 1; for (i=0; Knflw; i++) { line = ^♦ (paths*(i ^# nodes)) ; if (line != old_linc) {

*(flow_dist+((length-2)*links)+(old_linc-l)) = tflow; tflow = 0; old_linc = line; old_length = 2;

} a = *(paths*(i*nodes)+1); b = *(paths*(i*nodes)+2) ; length = 0; count = 3; while <(a!=0)&&(b!=0)) { a = b; b = *(paths*(i*nodes)+count); count**; length*+;

} if (length > old_length) {

*(flow_dist+((length-3)*links)+(linc-1)) = tflow; old_length = length;

} tflow = *(x+i) + tflow; if (i==(nflw-l)) {

*(flow_dist+((length-2) ^# links)+(linc-1)) = tflow;

} }

/ ^♦ ....The next stage is to use the max-flow, the working capacity and.... ....the shadow prices to determine which link the spare capacity can... ....be reduced.... ^♦ /

/ ^♦ ....Find the links with the max-flow equal to the working capacity.... ^♦ / for (i=0; Klinks; i++) { ^♦ (con+i) = 0; if ( ( ^♦ (flow_dist+((hops-l)ninks)+i)) == (*(work_cap+i)) ) { *(con+i) = 1; } }

/ ^♦ ....The first step is to construct an array of the shadow prices.... ^♦ / for (i=0; Klinks; i++) { for (j=0; j<links j++) {

*(sp_dist+(i*links)+j) = 0.0; } } for (i=0; Klinks; i++) { if (*(con+i) != 0) { for (j=0; j<links j++) {

*(sp_dist+(i*links)+j) = *(pi+((i+l)*links)+j) ; } } }

/*....Find a link whose spare capacity may be reduced */ for (i=0; Klinks; i++) { check = 0; if (*(incr+i) > 0) { for (j=0; j<links j++) { if (*(sP_dist+(j*links)+i) < 0) check = 1;

} if ((check == 0)&&(*(stut+i) == 0)) { *(spare_cap+i) = *(spare_cap+i) - 1; •update = (i+1) ; i = links; } } } return;

/********* ***** ****** ********** * ******** ^I void Check_Flow (int mc, int mr, int nodes, int links , int *paths , double *x, int *work cap, int *okay, int hops)

int length, old_length, old_linc, line, check; int i, j, k, a, b, count, nflw; double tflow; double ^# flow_dist;

/ ^♦ ....Initialise the parameters.... ^♦ / nflw = mc - links; flow_dist = (double ^♦ ) malloc ((hops ^# links) ^♦ sizeof(double)) ; if (!flow_dist) { printf("Memory allocation error!\n"); exit(l);

}

/ ^♦ ....Determine the flow distribution so that we can use the max-flow.... ^♦ / tflow = 0; length = 0; old_length = 2; old_linc = 1; for (i=0; Knflw; i++) { line = ^♦ (paths*(i*nodes)) ; if (line !■ old_linc) {

^♦ (flow_dist+((length-2)*links)+(old_linc-l)) = tflow; tflow = 0; old_linc = line; old_length = 2;

} a = *(paths*(i*nodes)+1) ; b - *(paths+(i*nodes)+2) ; length = 0; count = 3; while ((a!=0)8A(b!=0)) { a = b; b = *(paths*(i*nodes)+count) ; count**; length*+;

} if (length > old_length) {

*(flow_dist+((length-3)*links)+(linc-1)) = tflow; old_length = length;

} tflow = *(x+i) + tflow; if (i==(nflw-l)) {

*(flow_dist+((length-2)*links)+(linc-1)) = tflow;

} }

/*. . . . Check to see if the max-flow is less the working capacity. . . .*/ for (i=0; Klinks; i++) { if ( (*(flow_dist+( (hops-1 )*links)+i) ) < (* (work_cap+i) ) ) { *okay = 1 ;

}

} return;

/*

/********* * * *****

The function in this program can be used to determine the appropriate spare capacity assignment for a DXC meshed SDH network. The function in this file has been written to find all paths connecting the origin and destination of any link failure with a hop count less than or equal to the hop limit.

File : short_alg.c

Date : 29 MAR 93

Written : Stephen Bye

Version : 1.0 (release)

Assoc. Files :

(i) assign_cap.c (ii) asdef.h (iii) spare_fun.c (iv) m£«_flow.c (v) short_.alg.c

#include <stdio.h> #include <string.h> ^include <math.h> struct TREE { int from; int to; int f_layer; int t_layer; int path[8];

}; *******»* ********** ********** •*••••••** ********** •*****«**• *****< void Short_Alg (int *con, int *constr, int links, int nodes, int hops, int *num, int *num2)

{ int i, j, k, p, a, b, c, n, m; int *dist, *ccount, ^# ptemp; int inf. counter, MAX, count, line, sum, st, t ; int true, false, index, layer, org, check, number, accum, tindex; struct TREE ^# tp;

FILE *out;

/ ^♦ Initialise the variables....*/ hops = hops + 1; true = 1; false = 0; inf = 9999;

MAX = nodes; for (i=0); Khops; i++) { MAX = MAX*(nodes/2.0);

}

/*....Allocate the appropriate memory....*/ dist = (int *) calloc ( (nodes*nodes) , sizeof(int)) ; ccount = (int *) calloc (links, sizeof(int)) ; ptemp = (int *) calloc ((hops+1), sizeof(int)) ; tp = (struct TREE *) calloc (MAX, sizeof(struct TREE)); if (!dist ϋ Iccount !! Jptemp || !tp) { printf("Memory allocation error!\n"); exit(l);

} counter = 0; /*....This corresponds to the total number of paths....*/ for (i=0; Klinks; i++) { accum = 0; layer = 0; number = 1;

/*....The distance matrix is constructed given the connectivity....*/ for (k=0; k<nodes k++) { for (j=0; j<nodes j++) { if ((*(con+(k*nodes)*j) > 0)8A(*(con+(k*nodes)+j) != (i+1)))

*(dist+(k*nodes)+j) = 1; else *(dist+(k*nodes)+j) = inf; if (k==j) *(dist+(k*nodes)+j) = 0; if (*(con+(k*nodes)+j) == (i+1)) { st = (k+1); tm = (j+1); } } } while (layer < hops) { layer++; tindex = 0; for (n=0; n<number n++) {

/*....Find the parent node....*/ if (layer =•= 1) { for (m=0; m<(nops+l); m++) { *(ptemp+m) = 0;

} org = st;

} else { org = (tp-(n+tindex+l))->to for (m=0; m<hops m++) {

*(ptemp+m) = (tp-(n+tindex+l))->path[m];

} }

/ ^♦ ....Identify the children.... ^♦ / index - 0;

for (j=0; j<nodes j++) { if ((*(dist+((org-l)*nodes)+j) == l)S.4(org != tm) ) { check = false; for (k=0; k<layer k++) { if (*(ptemp+k) == (j+1)) check = true;

} if (check == false) { tp->from = org; tp->to = (j+1); tp->f_layer = (layer-1); tp->t_layer = layer; if (layer == 1) tp->path[0] = st; else { for (m=0; nKlayer; m++) { tp->path[m] = *(ρtemp+m); } } tp->path[layer] = (j+1); *tp++; index*+; } } } / ^♦ ....for loop for the child nodes.... ^♦ / tindex = tindex + index;

} / ^♦ ....for loop for parent nodes in the preceding layer */ number = tindex; accum = accum + tindex;

} /*....while layer is less than hop limit....*/

COMPLETE: tp = tp - accum; for (j=0; j<accum j++) { if (tp->to == tm) {

*(constr+(counter*nodes)) = (i+1) ; for (k=0; k<(hops+l); k++) { if (tp->path[k] != 0) {

*(constr+(counter*nodes)+(k+l)) = tp->path[k]; } } counter*+;

} *tp++;

} } / ^♦ ....End of the links loop.... ^# / if ((out = foρen( "lata.pth", "wr")) == NULL) { printf("Cannot open file!\n"); exit(l) ; } fprintf(out,"Possible paths determined by ^* short_alg.c' .\n") ; for (j=0; j<counter j++) { fprintf(out," 2d:", ^♦ (constr+(j ^♦ nodes))) ;

for (k=0; k<(hops+l); k++) { if (*(constr+(j*nodes)+(k+l)) != 0) { fprintf(out," 2d", *(constr+( ^# nodes)+(k+l)) ) ; } } fprintf(out,"\n");

} fclose (out) ;

^♦ num = counter; for (i=0; Klinks; i++) ^# (ccount+i) = 0; for (i=0; Kcounter; i++) { a = *(constr+(i*nodes)+l) ; b = *(constr+(i*nodes)+2) ; count = 3; while ((a!=0)&&(b!=0)) { line = *(con+((a-l)*nodes)+(b-l)) - 1;

*(ccount+linc) = *(ccount+linc) + 1; a = b; b = *(constr+(i*nodes)+count) ; count++;

} } sum = 0; for (i=0; Klinks; i++) sum •= sum + *(ccount+i);

*num2 = sum;

FINISH: return; }

/********* ********** ******** ** *,

/**** ******** ** * ******* *«***«*«

The function in this file is an implementation of Dinic's maximum flow algorithm and is used to determine the flow distribution for the solution to the spare capacity assignment program.

********** ********** ********** ********** ********** ********** *******«**,

^include <stdio.h> #include <string.h> #include <math.h>

void Max_Flow (int *con, double ^♦ spare, int *work, int *cut, double *dist, int links, int nodes, int *feas, int *cutlinks, int hflag)

{ int step, sink, source, check, link, count, hops; int index, indey, flag; double suml, sum2; int path, inc; double temp, minimum, test, temp2; int *interm, *inteπn2, *appear, *pred, *mincut; double *distl, *dist2, *flow, *sp, capacity; double *layers; int i, j, k, m, n;

/* Allocate the appropriate memory so that the layered networks can be */ /* defined and the maximum flow determined */ layers = (double *) calloc ((nodes*nodes*links) , sizeof(double)) ; interm = (int *) calloc (nodes, sizeof(int)) ; interm2 = (int *) calloc (nodes, sizeof(int)) ; pred = (int *) calloc (nodes, sizeof(int)) ; sp = (double *) calloc (links, sizeof(double)) ; if (ϋayers || ϋnterm || !interm2 j| !pred !! !sp) { printf("Memory allocation error!\n"); exit(1) ; } flow - (double *) calloc ( (links*links) , sizeof(double)) ; appear = (int *) c-alloc (nodes, sizeof(int)) ; distl = (double *) calloc ((nodes*nodes*links) , sizeof(double)) ; dist2 = (double *) calloc ((nodes*nodes*links) . sizeof(double)) ;

mincut = (int *) calloc ((nodes*links) , sizeof(int)) ; if (Iflo j| lappear jj Idistl jj !dist2 jj Imincut) { printf("Memory -allocation error!\n"); exit(l) ; }

/ ^♦ Now start the modified Dinic algorithm ^♦ / for (i=0; Klinks; i++) { step = 0; for (j=0; j<links j++) { *(sp+j) = ^# (spare+j); *(flow+(i*links)+j) = 0.0;

} for (j=0; j<(nodes*nodes*links) ; j++) { *(layers*j) = 0; } check = 0; for (j=0; j<nodes j++) { for (k=0; k<nodes k++) { if ((*(con+(j*nodes)+k) == (i+1) ) (check == 0)&&(k>j)) { sink = k; source = j; check = 1; } } } while (step != nodes) { hops = 0; for (j=0; j<nodes j++) {

*(inteπo+j) = 0;

*(appear* ) = 0;

} *(appear+source) = 1; for (k=0; k<nodes k++) { link = *(con+(source*nodes)+k) ; if ((link != 0)&&(link != (i+1))) { if (source < k) { capacity = *(sp+(link-l)) - *(flow+(i*links)+(link-l)) ;

} if (source > k) { capacity = *(sp+(link-l) ) + *(flow+(i*links)+(link-l)) ;

} if (capacity > 0) {

*(layers*(source*nodes)+k) = capacity; *(interm+k) = 1; *(appear+k) = 1; } } } hops**; count = 0; for (j=0; j<nodes j**) {

if (*(interm+j ) == 1) count++; } if (count == 0) goto MINCUT; count == 0; for (j=0; j<nodes j++) { if (*(appear* ) == 1) count = count + 1;

} if (count == nodes) goto MAXFLOW; if (count != nodes) { for (m=l; π links; m++) { for (j=0; j<nodes j++) { *(interm2+j) = 0;

} flag = 0; for (j=0; j<nodes j++) { if (*(interm+j) == 1) { for (k=0; k<nodes k++) { if (*(appear+k) != 1) { link = *(con*(j*nodes)+k) ; if ((link != 0) (link != (i+1))) { if (j < k) capacity = *(sp+(link-l)) -

*(flow+(i*links)+(link-l)); if (j > k) capacity = *(sp+(link-l)) +

*(flow*(i*links)+(link-1)) ; if (capacity > 0) {

*(layers*(j*nodes)+k+(m*nodes*nodes))

= capacity; *(interm2+k) = 1; if (k == sink) flag = 1; } } } } } } hops**; if (flag == 1) goto MAXFLOW; for (j=0; j<nodes j++) {

*(interm+j) = *(interm2+j) ;

*(appear+j) = *(appear+j) + ^♦ (interm2+j);

} count - 0; for (j=0; j<nodes j++) { if ( ^# (appear+j) == 1) count = count + 1;

} if (count == nodes) goto MAXFLOW; count = 0; for (j=0; j<nodes j++) { if ( ^♦ (interm2+j) == 1) count = count + 1;

} if (count == 0) goto MINCUT;

}

}

/* If the count is equal to the number of nodes then a layered */ /* network has been constructed. The next stage is to determine */ /* the flow contribution of the paths in the layered network. */

MAXFLOW: for (m=0; m<nodes m++) { for (j=0; j<nodes j++) { *(pred+j) = -1;

} inc = 0; path = m; index = -1; for (j=0; j<nodes j++) { temp = *(layers*(j*nodes)+sink+((hops-1)*nodes*nodes)) ; if (temp > 0) { index = j; } } *(pred+(inc++)) = sink; if (index >=0) { minimum = *(layers+(index*nodes)+sink+((hops-l)*nodes*nodes)) ; *(pred+(inc++)) = index; for (j=2; j<hops j++) { for (k=0; k<nodes k++) { temp = *(layers+(k*nodes)+index+((hops-j)*nodes*nodes)) ; if (temp > 0) { indey = k; } } test =

*(layers*(indey*nodes)+index+((hops-j) ^# nodes ^# nodes)) ; if ((test < minimum)&&(test > 0)) minimum = test; index = indey; *(pred+(inc++)) = index;

} test = *(layers*(source*nodes)+index) ; *(pred+(inc++)) = source; if ((test < minimum)&&(test > 0)) minimum = test; *(distl*((hops-1)*nodes)+path+(i*nodes*nodes)) = minimu ; if (minimum == 0) goto ENDWHILE;

/* The minimum capacity has been found and now the capacity */

/* expressions need to be updated. */

/* Updating the spare capacities and link flows */ for (j=0; j<hops j++) { if (((*(pred+j))>=0) && ((*(pred+(j+l)))>=0)) { index = *(pred+j); indey = *(pred+(j+1)) ; link = *(con+(indey*nodes)+index) ; if (link>0) { if (indey < index) *(flow+(i*links)+(link-l) ) = *(flow+(i*links)+(link-l)) + minimum; if (indey > index) *(flow+(i*links)+(link-l)) = *(flow+(i*links)+(link-l)) - minimum;

} } } for (j=0; j<hops j++) { if (((*(pred*j))>=0) S ((*(pred+(j+1) ) )>=0)) { index = *(pred+j); indey = *(pred+(j+1)) ;

*(layers*(indey*nodes)+index+( (hops-j-l)*nodes"nodes)) ■ *(layers*(indey*nodes)+index+( (hops-j-l)*nodes"nodes)) - minimum; } } for (j=0; j<(hops-1); j++) { for (k=0; k<nodes k++) { check = 0; for (n=0; n<nodes n++) { if (*(layers*(n*nodes)+k+( *nodes*nodes) ) > 0) check = 1;

} if (check == 0) { for (n=0; n<nodes n++) {

*(layers+(k*nodes)+n+((j+l)*nodes*nodes)) = 0; } } } }

} else m = nodes;

} goto ENDWHILE;

MINCUT: for (j=0; j<nodes j++) { if (*(appear*j) == 1) { *(cut+j+(i*nodes)) = 1;

} else *(cut+j+(i*nodes) ) = 0;

} step = (nodes-1) ;

ENDWHILE: step**;

} /* End of while */ } /* End of the links loop */

/* We have determined the flows on each link for each failed link */

/* The next step is to construct the flow distribution table */

/* The main difference in this part of the procedure is that only */ /* those links with valid flow are included in the layered */ /* so the difference is really in the construction of layered nets*/ for (i=0; Klinks; i++) { step = 0;

for (j=0; j<links j++) {

*(sp+j) = *(flow+(i*links)+j) ;

} for (j=0; j<(nodes*nodes*links); j++) { *(layers*j) = 0;

} check = 0; for (j=0; j<nodes j++) { for (k=0; kCnodes; k++) { if ((*(con+(j*nodes)+k) == (i+1) )&i(check == 0)&&(k>j)) { sink = k; source = ; check = 1; } } } while (step != nodes) { hops = 0; for (j=0; j<nodes j++) { *(interm+j) = 0; *(appear+j) = 0;

} *(appear+source) = 1; for (k=0; k<nodes k++) { capacity = 0; link = *(con+(source*nodes)+k) ; if ((link != 0)SA(link != (i+1))) { if ((source < k)&&(*(sp+(link-l)) > 0)) capacity = *(sp+(link-l)) ; if ((source > k)βi(*(sp+(link-l)) < 0)) capacity == - *(sp+(link-l) ) ; if (capacity > 0) {

^♦ (layers*(source ^# nodes)+k) - capacity; *(inteπu+k) = 1; *(appear+k) = 1; } } } hops++; count = 0; for (j=0; j<nodes j++) { if (*(interm+j) == 1) count++;

} if (count == 0) goto MINCUT2; count = 0; for (j=0; j<nodes j++) { if (*(appear* ) == 1) count = count + 1;

} if (count =■= nodes) goto MAXFL0W2; /* All nodes are in the single layer network */ if (count != nodes) { for (m=l; πKlinks; m++) { for (j=0; j<nodes j++) {

*(interm2+j) = 0;

} flag = 0; for (j=0; j<nodes j++) { if (*(interm+j) == 1) { for (k=0; k<nodes k++) { if (*(appe.ar+k) != 1) { capacity = 0; link = *(con+(j*nodes)+k) ; if ((link != 0)SA(link != (i+1))) { if ((j < k)SA(*(sp+(link-l)) > 0)) capacity = *(sp+(link-l)) ; if ((j > k)ii(*(sp+(link-l)) < 0)) capacity = - *(sp+(link-l)) ; if (capacity > 0) {

*(layers+(j*nodes)+k+(m*nodes*nodes)) = capacity; *(interm2+k) = 1; if (k == sink) flag = 1; } } } } } } hops++; if (flag == 1) goto MAXFL0W2; for (j=0; j<nodes j++) {

*(interm+j) = *(interm2+j);

*(appear*j) = *(appear* ) + *(interm2+j) ;

} count = 0; for (j=0; j<nodes j++) { if (*(appear*j) == 1) count = count + 1;

} if (count == nodes) goto MAXFL0W2; count = 0; for (j=0; j<nodes j++) { if (*(interm2+j) == 1) count = count + 1;

} if (count == 0) goto MINCUT2;

} } MAXFL0W2: for (m=0; π nodes; m++) { for (j=0; j<nodes j++) { *(pred+j) = -1;

} inc = 0; path = m; index = -1; for (j=0; j<nodes j++) { temp = *(layers+(j*nodes)+sink+((hops-1)*nodes*nodes) ) ; if (temp > 0) { index = j; }

} *(pred+(inc++) ) = sink; if (index >=0) { minimum = *(layers*(index*nodes)+sink+((hops-1)*nodes*nodes) ) ; *(pred+(inc++) ) = index; for (j=2; j<hops j++) { for (k=0; k<nodes k++) { temp = *(layers*(k*nodes)+index+( (hops-j)*nodes*nodes)) ; if (temp > 0) { indey = k; } } test =

*(layers*(indey*nodes)+index+((hops- )*nodes*nodes)) ; if ((test < minimum)&&(test > 0)) minimum = test; index = indey; *(pred+(inc++)) = index; } test = *(layers*(source*nodes)+index) ; ^♦ (pred+(inc++) ) = source; if ((test < minimum)&&(test > 0)) minimum = test; ^♦ (dist2+((hops-l) ^# nodes)+path+(i ^# nodes ^# nodes)) = minimum; if (minimum == 0) goto ENDWHILE; for (j=0; j<hops j++) { if (((*(pred+j))>=0) && ( (*(pred+(j+1)))>=0) ) { index = *(pred+j); indey = *(pred+(j+1)) ; link = ^♦ (con+(indey ^# nodes)+index) ; if (link>0) { if ( ^♦ (sp+(link-l))>0)

*(sp+(link-l)) = ^♦ (sp+(link-l)) - minimum; if ( ^♦ (sp+(link-l))<0)

*(sp+(link-l)) = *(sp+(link-l)) + minimum; } } } for (j=0; j<hops j++) { if (((*(pred+j))>=0) && ((*(pred+(j+l)))>=0)) { index = *(pred+j); indey = *(pred+(j+1)) ;

*(layers*(indey*nodes)+index+((hops-j-l)*nodes*nodes)) = *(layers*(indey*nodes)+index+((hops- -1)*nodes*nodes)) - minimum; } } for (j=0; j<(hops-1); j++) { for (k=0; k<nodes k++) { check = 0; for (n=0; n<nodes n++) { if (*(layers+(n*nodes)+k+( *nodes*nodes)) > 0) check = 1;

} if (check == 0) { for (n=0; n<nodes n++) {

*(layers*(k*nodes)+n+( (j+1)*nodes*nodes) ) = 0; } } } }

} else m = nodes;

} goto ENDWHILE2;

MINCUT2: for (j=0; j<nodes j++) { if (*(appear*j) == 1) {

*(mincut*j+(i*nodes)) = 1;

} else *(mincut*j*(i*nodes)) = 0;

} step = (nodes-1) ; ENDWHILE2: step**;

} /* End of while */ } /* End of the links loop */

/* Set up the distribution table for output */ for (i=0; Klinks; i++) { suml = 0; sum2 = 0; for (j=0; j<nodes j++) { for (k=0; k<nodes k+*) { suml = suml + *(distl+(j*nodes)+k+(i*nodes*nodes)) ; sum2 = sum2 + *(dist2+(j*nodes)+k+(i*nodes*nodes)) ;

} if (suml > sum2) *(dist+(i*nodes)+j) = suml; else *(dist+(i*nodes)+j) = sum2; }

}

/* The next step is to determine whether or not the spare capacity ^♦ / /* assignment is in fact feasible ^♦ /

^♦ feas - 0; count - 0; for (i=0; Klinks; i++) {

*(cutlinks+i) = 0; if (hflag > 0) { temp = ( ^# (dist+(i ^# nodes)+hflag) - *(work+i));

} else temp = (*(dist+(i*nodes)+(nodes-l)) - *(work+i)); if ( temp < -0.001) { count*+;

*(cutlinks+i) = 1;

} } if (count == 0) *feas = 1;

if layers) free((char *) layers); if interm) free((char *) interm) ; if interm2) free((char *) interm2) ; if pred) free((char *) pred) ; if sp) free((char ^♦ ) sp); if flow) free((char ^♦ ) flow); if appear) free((char ^♦ ) appear); if distl) free((char ^♦ ) distl); if dist2) free((char ^♦ ) dist2) ; if mincut) free((char ^♦ ) mincut); return;