Mixed integer programming model for minimizing leased access network costs

• US 8,443,079 B2
• Filed: 04/27/2011
• Issued: 05/14/2013
• Est. Priority Date: 07/23/2008
• Status: Expired due to Fees

• Current Assignee: Verizon Patent and Licensing Incorporated (Verizon Communications Inc.)
• Original Assignee: Verizon Patent and Licensing Incorporated (Verizon Communications Inc.)
• Inventors: Venugopal, Nandagopal, Newcomer, Thomas P.
• Primary Examiner(s): Yohannes, Tesfay
• Application Number:
  US13/095,383
• Publication Number:
  US 20110202638A1
• Time in Patent Office: 748 Days
• Field of Search: 709/201, 709/224, 370/222, 370/460
• US Class Current: 709/224
• CPC Class Codes: H04L 41/0806 for initial configuration or provisioning, e.g. plug-and-play
• CPC Class Codes: H04L 41/0823 characterised by the purposes of a change of settings, e.g. optimising configuration for enhancing reliability for optimising operational conditions of wireless networks H04W24/02
• CPC Class Codes: H04L 41/0856 by backing up or archiving configuration information

Abstract

A device receives network configuration information from a network, determines a logical network based on the network configuration information, and constructs a mixed integer programming (MIP) model based on the logical network. The device also calculates an optimal solution, which minimizes network costs, using the mixed integer programming (MIP) model, performs a post-optimization mapping procedure on the optimal solution to produce an optimal network configuration mapping, and outputs the optimal network configuration mapping for implementation.

Claims

1. A computing device-implemented method, the method comprising:

receiving network configuration information from a network;

determining an entrance facility capacity model of the network by;

determining one or more available entrance facilities in the network,

and

creating one or more arcs via the one or more available entrance facilities;

determining a logical network based on the entrance facility capacity model of the network, a new capacity model of the network, and an incumbent capacity model of the network, the entrance facility capacity model, the new capacity model, and the incumbent capacity model being based on the network configuration information;

constructing a mixed integer programming (MIP) model based on the logical network, the entrance facility capacity model, the new capacity model, and the incumbent capacity model;

calculating a solution that minimizes network costs, using the mixed integer programming (MIP) model;

performing a mapping procedure on the solution to produce a network configuration mapping; and

outputting the network configuration mapping for implementation.

2. The computing device-implemented method of claim 1, further comprising:

storing the network configuration mapping.

3. The computing device-implemented method of claim 1, further comprising:

determining the new capacity model of the network by;

creating a digital signal 3 (DS3) arc between a first pair of network nodes of a partial logical network created by the new capacity model;

calculating a cost associated with the digital signal 3 (DS3) arc;

creating a digital signal 1 (DS1) arc between a second pair of network nodes provided by the new capacity model, the digital signal 1 (DS1) arc representing an interconnection between nodes of the network; and

calculating a cost associated with the digital signal 1 (DS1) arc.

4. The computing device-implemented method of claim 1,

where the one or more arcs are digital signal 1 (DS1) arcs.

5. The computing device-implemented method of claim 1, further comprising:

determining the incumbent capacity model of the network by;

creating an incumbent arc between a pair of network nodes provided by the incumbent capacity model; and

associating the incumbent arc with a demand identifier associated with the pair of network nodes.

6. The computing device-implemented method of claim 1, where constructing the mixed integer programming (MIP) model comprises:

forming sets of network nodes and arcs for the mixed integer programming (MIP) model;

defining decision variables for the mixed integer programming (MIP) model based on the logical network;

defining parameters for mixed integer programming (MIP) model based on the logical network; and

formulating the mixed integer programming (MIP) model based on the sets, the decision variables, and the parameters.

7. The computing device-implemented method of claim 1, where performing the mapping procedure on the solution comprises:

calculating a demand offset for digital signal 1 (DS1) circuits based on the solution;

sorting the digital signal 1 (DS1) circuits based on the solution;

producing one or more candidate paths based on the offset demand/sorted digital signal 1 (DS1) circuits;

assigning digital signal 3 (DS3) lines based on the one or more candidate paths;

producing digital signal 1 (DS1) moves information based on the one or more candidate paths; and

storing information regarding the assigned digital signal 3 (DS3) lines and the digital signal 1 (DS1) moves information.

8. The computing device-implemented method of claim 1, where the network configuration information comprises one or more of:

a quantity of network elements associated with the network;

operational states of the network elements associated with the network;

routing information associated with the network;

interconnection information associated with the network;

or

cost information associated with the network.

9. A device comprising:

a processor; and

a memory to store one or more instructions that when executed by the processor, cause the processor to;

receive network configuration information from a network,

determine a new capacity model of the network based on the network configuration information,

determine an entrance facility capacity model of the network based on the network configuration information, the processor, when determining the entrance facility capacity model, being further to;

determine one or more available entrance facilities in the network, and

create one or more arcs via the one or more available entrance facilities,

determine an incumbent capacity model of the network based on the network configuration information,

construct a mixed integer programming (MIP) model based on the new capacity model, the entrance facility capacity model, and the incumbent capacity model,

calculate a solution that minimizes network costs, using the mixed integer programming (MIP) model,

perform a mapping procedure on the solution to produce a network configuration mapping, and

output the network configuration mapping for implementation.

10. The device of claim 9, where the new capacity model, the entrance facility capacity mode, and the incumbent capacity model comprise a logical network that models the network.

11. The device of claim 9, where the network configuration information comprises one or more of:

a quantity of network elements associated with the network,

operational states of the network elements associated with the network,

routing information associated with the network,

interconnection information associated with the network, or

cost information associated with the network.

12. The device of claim 9, where the network configuration mapping comprises information for routing traffic between network elements associated with the network in a manner that reduces access transport costs and increases cost savings.

13. The device of claim 9, where the processor is further to execute instructions in the memory to:

store the network configuration mapping.

14. The device of claim 9, where, when the processor is to determine the new capacity model, the processor is to:

create a digital signal 3 (DS3) arc between a first pair of network nodes of a partial logical network created by the new capacity model;

calculate a cost associated with the digital signal 3 (DS3) arc;

create a digital signal 1 (DS1) arc between a second pair of network nodes provided by the new capacity model, the digital signal 1 (DS1) arc representing an interconnection between nodes of the network; and

calculate a cost associated with the digital signal 1 (DS1) arc.

15. The device of claim 9, where

the one or more arcs are digital signal 1 (DS1) arcs.

16. The device of claim 9, where, when the processor is to determine the incumbent capacity model, the processor is to:

create an incumbent arc between a pair of network nodes provided by the incumbent capacity model; and

associate the incumbent arc with a demand identifier associated with the pair of network nodes.

17. The device of claim 9, where, when the processor is to construct the mixed integer programming (MIP) model, the processor is to:

form sets of network nodes and arcs for the mixed integer programming (MIP) model;

define decision variables for the mixed integer programming (MIP) model based on the logical network;

define parameters for mixed integer programming (MIP) model based on the logical network; and

formulate the mixed integer programming (MIP) model based on the sets, the decision variables, and the parameters.

18. The device of claim 9, where, when the processor is to perform the mapping procedure on the solution, the processor is to:

calculate a demand offset for digital signal 1 (DS1) circuits based on the solution;

sort the digital signal 1 (DS1) circuits based on the solution;

produce one or more candidate paths based on the offset demand/sorted digital signal 1 (DS1) circuits;

assign digital signal 3 (DS3) lines based on the one or more candidate paths;

produce digital signal 1 (DS1) moves information based on the one or more candidate paths; and

store information regarding the assigned digital signal 3 (DS3) lines and the digital signal 1 (DS1) moves information.

19. A system associated with an access network, the system comprising a plurality of network elements, and a plurality of links interconnecting the network elements, the system comprising:

a device to;

receive, from the network, network configuration information associated with the plurality of network elements and the plurality of links,

determine a new capacity model of the network based on the network configuration information,

determine an entrance facility capacity model of the network based on the network configuration information, the device, when determining the entrance facility capacity model, being further to;

determine one or more available entrance facilities in the network, and

create one or more arcs via the one or more available entrance facilities,

determine an incumbent capacity model of the network based on the network configuration information,

construct a mixed integer programming (MIP) model based on the new capacity model, the entrance facility capacity model, and the incumbent capacity model,

calculate a solution that minimizes network costs using the mixed integer programming (MIP) model,

perform a mapping procedure on the solution to produce a network configuration mapping, where, when the device is to perform the mapping procedure, the device is to assign digital signal 3 (DS3) lines based on the solution and produce digital signal 1 (DS1) moves information based on the solution.

20. The system of claim 19, where when the device is to assign the digital signal 3 (DS3) lines based on the solution, the device further is to:

calculate an offset demand for digital signal 1 (DS1) circuits based on the solution,

sort the digital signal 1 (DS1) circuits based on the solution, and

determine a candidate path based on the offset demand and the sorted digital signal 1 (DS1) circuits.

21. The system of claim 19, where the one or more arcs are digital signal 1 (DS1) arcs.