Optimal expansion of a telecommunications network

• US 8,265,061 B1
• Filed: 10/31/2005
• Issued: 09/11/2012
• Est. Priority Date: 10/31/2005
• Status: Expired due to Fees

• Current Assignee: Verizon Patent and Licensing Incorporated (Verizon Communications Inc.)
• Original Assignee: Verizon Services Corporation (Verizon Communications Inc.)
• Inventors: Smith, Donald E., Schneur, Rina R., Sivaraman, Raghavendran, Tobin, Roger L., Liu, Hui, Crom, Lawrence W.
• Primary Examiner(s): Nawaz, Asad M
• Assistant Examiner(s): Hamel, Joel
• Application Number:
  US11/261,602
• Time in Patent Office: 2,507 Days
• Field of Search: 370464-465, 370254-258, 370352-356, 705/7.12, 705/7.25, 705/7.31
• US Class Current: 370/352
• CPC Class Codes: H04L 12/66 Arrangements for connecting between networks having differing types of switching systems, e.g. gateways
• CPC Class Codes: H04L 41/142 using statistical or mathematical methods
• CPC Class Codes: H04L 41/145 involving simulating, designing, planning or modelling of a network

Abstract

There is assigned at least one first cost for expanding at least one link to a circuit-switched network that is part of a hybrid network comprising the circuit switched network and a packet switched network. All paths in the packet switched network are represented with a virtual link. A cost is assigned to the virtual link. An integer programming problem is solved to determine a number of links to add to the network, the integer programming problem having as inputs a model of the hybrid network and a demand forecast matrix.

Claims

1. A method, comprising:

assigning at least one first cost for expanding at least one link to a circuit-switched network that is part of a hybrid network comprising the circuit switched network and a packet switched network;

representing all paths in the packet switched network as a virtual link in the hybrid network;

assigning a second cost to the virtual link, wherein the virtual link connects at least two circuit-switched network devices and wherein the second cost represents that hops within the packet switched network between the at least two circuit-switched network devices have no associated cost;

solving an integer programming problem in a computer having a processor and a non-transitory memory to determine a number of links to add to the hybrid network, the integer programming problem having as inputs a model of the hybrid network and a demand forecast matrix, wherein solving the integer programming problem includes determining whether a trunk group is permitted to grow, and wherein solving the integer programming problem includes considering the following variables;

a set of trunk groups, a trunk group in the set, a cost of adding a circuit to the trunk group, and a number of circuits added to the trunk group.

2. The method of claim 1, further comprising using a path decomposition heuristic to find a set of paths to which at least one link may be expanded.

3. The method of claim 1, further comprising determining whether to migrate network traffic from the circuit-switched network to the packet switched network based on a result of solving the integer programming problem.

4. The method of claim 1, further comprising expanding links to the circuit-switched network according to a solution to the integer programming problem.

5. The method of claim 4, further comprising routing network traffic such that availability capacity on shorter routes is consumed before available capacity on longer routes.

6. The method of claim 1, wherein the model of the hybrid network includes a set A of all links in the network and a set S of all switches in the network.

7. The method of claim 1, wherein the integer programming problem takes the form:

Minimize

8. The method of claim 1, wherein the second cost assigned to the virtual link is the same as the first cost for expanding at least one link to the circuit-switched network.

27. The method of claim 1, wherein the circuit switched network and the packet switched network are connected by a plurality of softswitches, and wherein the second cost to the virtual link further represents that all paths between any two of the plurality of softswitches have the same associated cost.

9. A system, comprising:

a model of a hybrid network that comprises a circuit-switched network including a plurality of links and a packet switched network that is represented as a virtual link in the hybrid network, each of the links and the virtual link being associated with a cost;

wherein the virtual link connects at least two circuit-switched network devices and wherein the cost associated with the virtual link represents that hops within the packet switched network and between the at least two circuit-switched network devices have no associated cost;

a demand matrix for the hybrid network; and

an integer programming module stored in a non-transitory computer memory as a set of computer-executable instructions, the module configured to provide a solution to an integer programming problem to determine an amount of capacity to add to the hybrid network, the integer programming problem having as input at least the model of the hybrid network and the demand matrix, wherein the solution to the integer programming problem considers whether a trunk group is permitted to grow and the following variables;

a set of trunk groups, a trunk group in the set, a cost of adding a circuit to the trunk group, and a number of circuits added to the trunk group.

10. The system of claim 9, further comprising a path decomposition module configured to find a set of paths in the circuit-switched network to which at least one link may be added.

11. The system of claim 9, the integer programming module further configured to provide a solution to the integer programming problem that may be used to determine whether to migrate network traffic from the circuit-switched network to the packet switched network based on the solution.

12. The system of claim 9, further comprising a link allocation module for adding links to the circuit-switched network according to the solution.

13. The system of claim 12, wherein the link allocation module is configured to route network traffic such that availability capacity on shorter routes is consumed before available capacity on longer routes.

14. The system of claim 9 wherein the model of the hybrid network further comprises a set A of all links in the network and a set S of all switches in the network.

15. The system of claim 9, further comprising a cost determination module for determining the cost.

16. The system of claim 9, wherein the integer programming problem takes the form:

Minimize

17. The system of claim 9, further comprising a first cost associated with the circuit switched network and a second cost associated with the packet switched network.

18. A non-transitory computer-readable medium tangibly embodying computer-executable instructions, the instructions comprising:

assigning at least one first cost for expanding at least one link to a circuit-switched network that is part of a hybrid network comprising the circuit switched network and a packet switched network;

representing all paths in the packet switched network as a virtual link in the hybrid network;

assigning a second cost to the virtual link, wherein the virtual link connects at least two circuit-switched network devices and wherein the second cost represents that hops within the packet switched network between the at least two circuit-switched network devices have no associated cost;

solving an integer programming problem in a computer having a processor and a non-transitory memory to determine a number of links to add to the hybrid network, the integer programming problem having as inputs a model of the hybrid network and a demand forecast matrix, wherein solving the integer programming problem includes determining whether a trunk group is permitted to grow, and wherein solving the integer programming problem includes considering the following variables;

a set of trunk groups, a trunk group in the set, a cost of adding a circuit to the trunk group, and a number of circuits added to the trunk group.

19. The medium of claim 18, further comprising instructions for using a path decomposition heuristic to find a set of paths in the circuit-switched network to which at least one link may be added.

20. The medium of claim 18, further comprising instructions for determining whether to migrate network traffic from the circuit-switched network to the packet switched network based on a solution to the integer programming problem.

21. The medium of claim 18, further comprising instructions for adding links to the circuit-switched network according to a solution to the integer programming problem.

22. The medium of claim 21, further comprising instructions for routing network traffic such that availability capacity on shorter routes is consumed before available capacity on longer routes.

23. The medium of claim 18, wherein the model of the hybrid network includes a set A of all links in the network and a set S of all switches in the network.

24. The medium of claim 18, wherein the integer programming problem takes the form:

Minimize

25. The instructions of claim 18, wherein the second cost assigned to the virtual link is the same as the first cost for expanding at least one link to the circuit-switched network.

26. A method, comprising:

assigning a cost to adding at least one link to a network, the cost representing that hops within a packet switched network between at least two circuit-switched network devices have no associated cost and that all paths between softswitches that connect a circuit-switched network to the packet switching network have the same associated cost;

solving an integer programming problem in a computer having a processor and a non-transitory memory to determine a number of links to add to the network, the integer programming problem having as inputs a model of the network and a demand forecast matrix, wherein solving the integer programming problem includes determining whether a trunk group is permitted to grow, and wherein solving the integer programming problem includes considering the following variables;

a set of trunk groups, a trunk group in the set, a cost of adding a circuit to the trunk group, and a number of circuits added to the trunk group;

using a path decomposition heuristic to find a set of paths to which at least one link may be added.