Multiplex communications – Pathfinding or routing – Through a circuit switch
Reexamination Certificate
1998-08-28
2002-10-08
Hsu, Alpus H. (Department: 2665)
Multiplex communications
Pathfinding or routing
Through a circuit switch
C370S386000, C370S385000, C370S254000, C370S406000, C370S410000, C379S221100, C709S220000, C709S241000
Reexamination Certificate
active
06463058
ABSTRACT:
TECHNICAL FIELD
This invention relates to methods for designing communication networks.
BACKGROUND ART
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.
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.
Each model has different capacity and engineering parameters.
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.
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.
At the third level of the SS7 network hierarchy, regional STPs (RSTPs) serve to interconnect TSTPs within their region and SCPs.
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.
SUMMARY OF THE INVENTION
It is an object of the present invention to select nodes for removal from a hierarchical communications network.
Another object of the present invention is to determine the reconnection of elements in a hierarchical communications network once a node has been removed.
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.
A further object of the present invention is to reconnect terminal nodes originally connected to excluded LSTPs to LSTPs remaining in the network configuration.
A still further object of the present invention is to rehome remaining LSTPs to TSTPs after removal of at least one LSTP.
Yet a further object of the present invention is to reduce the cost of an SS7 network subject to a set of constraints.
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.
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.
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.
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.
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.
REFERENCES:
patent: 5915008 (1999-06-01), Dulman
patent: 5949872 (1999-09-01), Khalil et al.
patent: 5953399 (1999-09-01), Farris et al.
patent: 6167129 (2000-12-01), Fikis et al.
Slides from INFORMS Conference, San Diego, CA (May 1997).
Bastien Pierre L.
Chiu Steve Y.
Lee Young-ho
Okeson Victoria L. C.
Hsu Alpus H.
Nguyen Toan D.
Qwest Communications International Inc.
Townsend and Townsend & Crew LLP
LandOfFree
Method for optimally selecting nodes for removal from a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for optimally selecting nodes for removal from a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for optimally selecting nodes for removal from a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2943966