Method for optimally selecting nodes for removal from a hierarchical communication network

[0002] This invention relates to methods for designing communication networks.

[0003] Communication networks may be arranged in a hierarchical or tree-like architecture. Nodes at each level of the hierarchy may communicate with other nodes at the same level, nodes at the next lower level, or nodes at the next higher level of the hierarchy. In order to optimize an existing network, to assist in planning network expansion, or to design a new network, it may be necessary to remove a node to minimize the network cost.

[0004] One such hierarchical network is the Signaling System Number 7 (SS7) network. An SS7 network is a packet data network used for out-of-band signaling to perform call set-up and tear-down, to implement Advanced Intelligent Network (AIN) services, to route traffic to interexchange carriers (IXCs), and to access database information needed to provide certain services such as 800, CLASS, and LIDB. The core of the SS7 network consists of switches called Signal Transfer Points (STPs). The STPs are interconnected with data links. Several different switch models may be used as STPS.

[0005] Each model has different capacity and engineering parameters.

[0006] An SS7 network can be built as a three-tiered hierarchical architecture. At the first level of the hierarchy, nodes are implemented as local STPs (LSTPs). These nodes serve local access transport areas (LATAs) providing service to network elements such as switching points (SSPs or central offices) in the LATA, Service Control Points (SCPs), and points of presence (POPs) for IXCs.

[0007] At the second level of the SS7 hierarchy, territorial STPs (TSTPs) serve to interconnect the LSTPs in their territory, SCPs, and other TSTPs. TSTPs may also service SSPs, SCPs, and POPs within a LATA.

[0008] At the third level of the SS7 network hierarchy, regional STPs (RSTPs) serve to interconnect TSTPs within their region and SCPs.

[0009] What is needed is a method to select a node for removal and to reconnect the elements of the network serviced by the node without adversely affecting the performance of the network as expressed by a set of constraints. In particular, for the three-tiered SS7 hierarchical network, LSTPs should be selected for retirement and elements connected to the LSTP should be rehomed to other LSTPs. The remaining LSTPs may further be homed to different TSTPs.

[0010] It is an object of the present invention to select nodes for removal from a hierarchical communications network.

[0011] Another object of the present invention is to determine the reconnection of elements in a hierarchical communications network once a node has been removed.

[0012] Still another object of the present invention is to reduce the cost of an SS7 network by selecting LSTPs for removal without adversely affecting the performance of the network as expressed by a set of constraints.

[0013] A further object of the present invention is to reconnect terminal nodes originally connected to excluded LSTPs to LSTPs remaining in the network configuration.

[0014] A still further object of the present invention is to rehome remaining LSTPs to TSTPs after removal of at least one LSTP.

[0015] Yet a further object of the present invention is to reduce the cost of an SS7 network subject to a set of constraints.

[0016] In carrying out the above objects and other objects and features of the present invention, a method is provided for optimally selecting LSTPs for removal from an SS7 network. The network has at least one network element connected to each LSTP and each LSTP is connected to a parent node. The method includes determining each LSTP as a flexible LSTP or a fixed LSTP. A potential network configuration is formed with at least one flexible LSTP excluded from the potential network configuration. Each network element is reconnected to one LSTP in the potential network configuration, and each LSTP in the potential network configuration is reconnected to one parent node. A total cost is determined based on the potential network configuration. The best network configuration is then determined as the potential network configuration if the total cost is less than the total cost of any previous potential network configuration. For each potential network configuration resulting from removing a different combination of flexible LSTPs, forming a potential network configuration, reconnecting each network element, reconnecting each LSTP, determining a total cost, and determining the best network configuration are repeated.

[0017] In one embodiment, each parent node is a TSTP. In another embodiment, each network element is a cluster, each cluster may be all POPs connected to one LSTP, all databases connected to one LSTP, or at least one SSP connected to one LSTP.

[0018] In yet another embodiment, reconnecting each network element to one LSTP in the potential network configuration comprises determining to which LSTP in the potential network each cluster should be connected based on costs of links between network elements and LSTPs in the potential network configuration, on costs of LSTPs in the potential network configuration, and on salvage costs of LSTPs excluded from the potential network configuration subject to a set of constraints. Similarly, reconnecting each LSTP in the potential network configuration to one parent node comprises determining to which parent node each LSTP in the potential network should be connected based on minimizing the costs of links between LSTPs in the potential network configuration and parent nodes and on costs of switches in parent nodes subject to a set of constraints. In a further embodiment, the total cost is the sum of LSTP-to-network component costs and the LSTP-to-TSTP costs.

[0019] In yet a further embodiment, the method includes abandoning the potential network configuration as a possible best network configuration if reconnecting each network element connected to an excluded flexible LSTP to an LSTP in the potential network configuration results in an infeasible solution or if reconnecting each LSTP in the potential network configuration to an parent node results in an infeasible solution.

[0020] In a still further embodiment, the method includes perturbing the connections of network elements to LSTPs in the potential network configuration by assigning at least one network element to a different LSTP in the potential network configuration and repeatedly perturbing the connections until a representative sample of feasible assignments in the solution space has been examined.

[0021] The above objects and other objects, features, and advantages of the present invention are readily apparent from the following detailed description of the best modes for carrying out the invention when taken in connection with the accompanying drawings.

[0022] FIG. 1 is a block diagram of a three-tiered hierarchical SS7 network architecture that may be optimized by the present invention;

[0023] FIG. 2 is a flow diagram of an embodiment of the present invention; and

[0024] FIG. 3 is a flow diagram of an alternative embodiment of the present invention including perturbation.

[0025] Referring now to FIG. 1, a three-tiered hierarchical SS7 network architecture is shown. An SS7 network, shown generally by 20, is comprised of three tiers. In the first tier, LSTP 22 serves LATA 24. Every SSP 26 in LATA 24 is connected either directly or indirectly to LSTP 22. Each LSTP 22 handles inter-LATA traffic to and from the IXCs via POPs, one of which is indicated by 28, attached to each LSTP 22. POPs 28 provide long distance services to regional Bell operating companies (RBOCs), which would otherwise be prohibited from transporting calls across the boundaries of LATA 24. Each LSTP may also service one or more SCPs, one of which is shown as 34.

[0026] Each LATA 24 belongs to a region, one of which is indicated by 30. Each LATA 24 within region 30 may be connected to one or more TSTP 32. Each TSTP 32 may be linked to a corresponding SCP 34. TSTP 32 may also service SSPs 26 and POPs 28 within a LATA 24.

[0027] Each TSTP 32 in region 36 is connected to RSTP 38. RSTP 38 also provides access to one or more SCP 34.

[0028] The optimization problem focuses on selecting the LSTPs 22 for retirement, rehoming terminal nodes such as SSPs 26, POPs 28, and SCPs 34 assigned to the retired LSTPs 22, and homing the remaining LSTPs 22 to TSTPs 32.

[0029] FIGS. 2 and 3 show a flow diagrams illustrating operation of embodiments of the present invention. As will be appreciated by one of ordinary skill in the art, the operations illustrated are not necessarily sequential operations. Similarly, operations may be performed by software, hardware, or a combination of both. The present invention transcends any particular implementation and aspects are shown in sequential flow chart form for ease of illustration.

[0030] Referring now to FIG. 2, a flow diagram of an embodiment of the present invention is shown. Data is entered in block 80. The current network configuration, engineering restrictions such as switch model and link capacity, and predicted traffic loads are entered. Any valid network obtained by the present method will be able to carry the predicted traffic while satisfying the engineering restrictions.

[0031] At least one LSTP 22 must be designated as flexible. Flexible LSTPs are candidate nodes for elimination from the communication network. Any LSTP 22 not designated as flexible is considered fixed and must remain in the final network. In a preferred embodiment, all TSTPs 32 and RSTPs 38 are fixed.

[0032] A check is made to see if any LSTP network configurations that have not been considered still remain in block 82. Since the number of LSTPs 22 is relatively small, every potential network combination based on keeping or removing each flexible LSTP 22 is considered. If n is the number of flexible LSTPs, there are 2ⁿpotential network configurations with each combination of flexible LSTPs 22 removed. If all LSTP network configurations have been considered, results are delivered. If a configuration has not been examined, the next potential network configuration is considered.

[0033] The next LSTP network is formed in block 84. Every combination of networks with each flexible LSTP 22 either in or out of the network is considered. The order in which these combinations are considered is not critical. Any technique which generates each possible combination only once is appropriate. For example, the network containing all flexible LSTPs 22 may be considered first. Next, each network formed by removing one flexible LSTP 22 may be considered. Then each network with each pair of flexible LSTPs removed 22 may be considered. This process continues until the network with all flexible LSTPs 22 removed is considered.

[0034] The cluster-LSTP problem is formed and solved in block 86. The cluster-LSTP problem is formed by considering Equation 1: $\begin{array}{cc}{C}_1=\sum _{i\in M}\sum _{j\in N}{a}_{\mathrm{ij}}{x}_{\mathrm{ij}}+\sum _{j\in N}\sum _{s\in S}{C}_{\mathrm{js}}{Z}_{\mathrm{js}}-\sum _{j\in N}\sum _{s\in S}{g}_{\mathrm{js}}\left(1-z_{\mathrm{js}}\right)& \left(1\right)\end{array}$

[0035] where C₁, is the cost of the cluster-LSTP solution, M is the set of clusters in the network indexed by i and N is the set of LSTP nodes in the network indexed by j. The cost of a link from cluster i to LSTP j is a_ij. This includes the capital costs, installation costs, retirement costs, and yearly maintenance for new links, and only yearly maintenance and lease costs for existing links. The binary integer variable x_ijis equal to one when cluster i is assigned to LSTP j, and is zero otherwise. S is the set of switch types indexed by s. The cost of installing a switch of type s at LSTP j is c_js. This cost includes capital costs, installation costs, retirement costs, and yearly maintenance costs for a new switch type, any only yearly maintenance costs for the existing switch type. The binary integer variable z_jsis equal to one when the switch type s is installed at LSTP j, and is zero otherwise. The salvage value for removing switch type s at LSTP j is g_js.

[0036] Solving the cluster-LSTP problem involves minimizing the cost C₁in Equation 1 subject to a set of constraints. The first constraint requires that each cluster be assigned to one and only one LSTP 22. This is expressed in Equation 2: $\begin{array}{cc}\begin{array}{cc}\sum _{j\in N}{x}_{\mathrm{ij}}=1& i\in M\end{array}& \left(2\right)\end{array}$

[0037] The second constraint specifies that there is at most one switch installed at flexible LSTP 22. The second constraint is expressed as Equation 3: $\begin{array}{cc}\begin{array}{cc}\sum _{s\in S}{z}_{\mathrm{js}}\le 1& j\in N_{\mathrm{Flex}}\end{array}& \left(3\right)\end{array}$

[0038] where N_Flexis the set of flexible LSTP nodes.

[0039] The third constraint requires that exactly one switch is installed at fixed LSTP 22. The third constraint is expressed in Equation 4: $\begin{array}{cc}\begin{array}{cc}\sum _{S\in S}{z}_{\mathrm{js}}=1& j\in N_{\mathrm{Fix}}\end{array}& \left(4\right)\end{array}$

[0040] where N_Fixis the set of fixed LSTP nodes.

[0041] The fourth constraint ensures that the capacity of a switch s at LSTP j is not exceeded. Constraint 4 is expressed in Equation 5: $\begin{array}{cc}\begin{array}{cc}\sum _{i\in M}{\lambda }_{\mathrm{ihs}}{x}_{\mathrm{ij}}\le q_{\mathrm{js}}{z}_{\mathrm{js}}+B\underset{r\ne s}{\sum _{r\in S}}{z}_{\mathrm{jr}}& j\in N,h\in H,s\in S\end{array}& \left(5\right)\end{array}$

[0042] Where λ_ihsis the traffic load from cluster i in peak hour h in seconds of processor time required on switch type s, q_jsis the capacity of switch type s at LSTP j, and B is a constant. B is a number just large enough to make the constraint vacuous if z_jsequals zero.

[0043] The fifth constraint forces a switch to be installed at each LSTP j that has clusters homed to it. The fifth constraint is shown as Equation 6: $\begin{array}{cc}\begin{array}{cc}{x}_{\mathrm{ij}}\le \sum _{s\in s}{z}_{\mathrm{js}}& i\in M,j\in N\end{array}& \left(6\right)\end{array}$

[0044] When the result of Equation 1 is implemented, various configurations of flexible LSTPs are examined. To forcibly remove an LSTP j from the network, the sixth constraint is added to the formulation. The sixth constraint is shown as Equation 7: $\begin{array}{cc}\begin{array}{cc}\sum _{s\in S}{z}_{\mathrm{js}}=0& \mathrm{for}\mathrm{all}\mathrm{removed}\mathrm{LSTPs}j\end{array}& \left(7\right)\end{array}$

[0045] Once the cluster-LSTP problem has been solved, it is checked for feasibility in block 88. A solution is not feasible if any constraint cannot be met. This may happen, for example, if the traffic load of SSPs 26, POPs 28, and SCPs 34 homed to LSTP 22 exceeds the capacity of LSTP 22. If the solution is not feasible, the check for remaining LSTP network configurations is repeated. If the solution is feasible, the LSTP-TSTP problem is formed and solved.

[0046] The LSTP-TSTP problem is formed and solved in block 90. The LSTP-TSTP problem is formed by considering Equation 8: $\begin{array}{cc}{C}_2=\sum _{k\in P}\sum _{s\in S}{c}_{\mathrm{ks}}{t}_{\mathrm{ks}}+\sum _{j\in N}\sum _{k\in P}\sum _{l\in L}{b}_{\mathrm{jkl}}{v}_{\mathrm{jkl}}& \left(8\right)\end{array}$

[0047] where C₂is the cost of the LSTP-TSTP solution, P is the set of TSTP nodes in the network indexed by k and L is the set of link types indexed by l. The cost of installing a switch of type s at TSTP k is c_ks. This cost includes capital costs, installation costs, retirement costs, and yearly maintenance costs for a new switch type, and only yearly maintenance costs for the existing switch type. The binary variable t_ksis equal to one when switch type s is installed at TSTP k and is zero otherwise. The cost of installing link type l from LSTP j to TSTP k is b_jkl. This includes the capital costs, installation costs, retirement costs, and yearly maintenance costs for new links and only yearly maintenance and lease costs for existing links. The binary variable Vjkl is equal to one when a link of type l is installed from LSTP j to TSTP k and is zero otherwise.

[0048] Solving the LSTP-TSTP problem involves minimizing the cost C₂in Equation 8 subject to a set of constraints. The first constraint ensures that each LSTP homes to exactly one TSTP. The first constraint is expressed as Equation 9: $\begin{array}{cc}\begin{array}{cc}\sum _{k\in P}{y}_{\mathrm{jk}}=1& j\in N\end{array}& \left(9\right)\end{array}$

[0049] where y_jkis a binary variable equal to one when LSTP j is assigned to TSTP k and is zero otherwise.

[0050] The second constraint requires that exactly one switch is installed at each TSTP. The second constraint is expressed as Equation 10: $\begin{array}{cc}\begin{array}{cc}\sum _{s\in S}{t}_{\mathrm{ks}}=1& k\in P\end{array}& \left(10\right)\end{array}$

[0051] The third constraint forces a link to exist between LSTP j and TSTP k if LSTP j homes to TSTP k. The third constraint is expressed as Equation 11. $\begin{array}{cc}\begin{array}{cc}{y}_{\mathrm{jk}}\le \sum _{l\in L}{v}_{\mathrm{jkl}}& j\in N,k\in P\end{array}& \left(11\right)\end{array}$

[0052] The fourth constraint ensures that there is at most one link type installed between LSTP j and TSTP k. The fourth constraint is expressed as Equation 12: $\begin{array}{cc}\begin{array}{cc}\sum _{l\in L}{V}_{\mathrm{jkl}}\le 1& j\in N,k\in P\end{array}& \left(12\right)\end{array}$

[0053] The fifth constraint ensures that the capacity of link i between LSTP j and TSTP k is not exceeded. The fifth constraint is expressed as Equation 13: $\begin{array}{cc}\begin{array}{cc}{w}_{\mathrm{jh}}{y}_{\mathrm{jk}}\le \sum _{l\in L}{r}_l{v}_{\mathrm{jkl}}& j\in N,k\in P,h\in H\end{array}& \left(13\right)\end{array}$

[0054] where W_jhis the maximum link capacity in octets for LSTP j in hour h, r, is the capacity of link type l, P is the set of TSTP nodes in the network indexed by k, H is the set of peak hours indexed by h, and L is the set of link types indexed by l.

[0055] The sixth constraint ensures that the capacity of switch s at TSTP k is not exceeded. The sixth constraint is expressed by Equation 14: $\begin{array}{cc}\begin{array}{cc}\sum _{j\in N}{u}_{\mathrm{jhs}}{y}_{\mathrm{jk}}\le q_{\mathrm{ks}}{t}_{\mathrm{ks}}+B\underset{r\ne s}{\sum _{r\in S}}{t}_{\mathrm{kr}}& k\in P,h\in H,s\in S\end{array}& \left(14\right)\end{array}$

[0056] where U_jhsis the traffic load from LSTP j in peak hour h in seconds of processor time required on switch type s. q_ksis the capacity of switch type s at TSTP k, and B is a constant. B is a number just large enough to make the constraint vacuous if t_ksequals zero.

[0057] The feasibility of the LSTP-TSTP solution is determined in block 92. A solution is not feasible if any constraint cannot be met. If the solution is not feasible, a check for remaining LSTP network configurations is repeated. If the solution is feasible, the solution is compared to the best solution found so far.

[0058] The solution is compared to the best solution found so far in block 94. In the preferred embodiment, the quantitative measure of the solution is the sum of costs C₁and C₂. Since minimizing both Equations 1 and 8 is desired, a smaller sum indicates a better solution. If the sum of the cluster-LSTP solution and the LSTP-TSTP solution is not better than the best solution found so far, the check for remaining LSTP network configurations is repeated. If the sum of the cluster-LSTP solution and the LSTP-TSTP solution is better than the best solution so far, the sum of the cluster-LSTP solution and the LSTP-TSTP solution is saved along with the network configuration as the new best solution in block 96.

[0059] Results are output in block 98. Once all potential network configurations resulting from removing a different combination of flexible LSTPs have been considered, results are delivered. Results include an optimized network architecture indicating which flexible LSTPs, if any, have been removed.

[0060] Referring now to FIG. 3, a flow diagram of an alternative embodiment of the present invention is shown. The embodiment shown in FIG. 3 is similar to the embodiment shown in FIG. 2 above with the addition that the cluster-LSTP solution is perturbed prior to forming and solving the LSTP-TSTP problem.

[0061] A check for remaining cluster-LSTP perturbations is made in block 100. Assignments of clusters to LSTPs 22 is altered. If an unexamined assignment pattern remains, the cluster-LSTP solution is perturbed. When all representative feasible assignments in a given cross section of the solution space have been examined, the perturbation loop is exited and a check for remaining network configurations is performed.

[0062] The cluster-LSTP solution is perturbed in block 102. A preferred perturbation method is heuristic search. A new assignment is proposed. Small transformations of this assignment are performed at each perturbation step with the goal of reducing the cost of the proposed network configuration.

[0063] For either the method described with regards to FIG. 2 or to FIG. 3 above, a preferred embodiment groups terminal nodes into clusters to reduce computational complexity. Each TSTP 32 and fixed LSTP 22 has one cluster that contains all SSPs 26, SCPs 34, and POPs 28 attached to TSTP 32 or fixed LSTP 22. Each flexible LSTP 22 has one or more clusters, one for POPs 28 attached to flexible LSTP 22, one for the SCPs 34, attached to flexible LSTP 22, and one or more clusters for SSPs attached to flexible LSTP 22. SSPs 26 are clustered according to a geographic attribute such as, for example, LATA, city, state, metropolitan statistical area, or numbering plan area, as specified by the user. If flexible LSTP 22 is retired, its clusters are rehomed to one or more other LSTPs 22. All of the cost, traffic, and demand information for the terminal node is aggregated to form the cost, traffic, and demand data for the clusters.

[0064] While the best modes for carrying out the invention have been described in detail, those familiar with the art to which this invention relates will recognize various alternative designs and embodiments for practicing the invention as defined by the following claims.