System and method for staggering time points for deployment of rings in a fiber optic network simulation plan

• US 7,318,016 B2
• Filed: 02/17/2004
• Issued: 01/08/2008
• Est. Priority Date: 12/22/1999
• Status: Expired due to Fees

• Current Assignee: Verizon Patent and Licensing Incorporated (Verizon Communications Inc.)
• Original Assignee: Verizon Business Global LLC (Verizon Communications Inc.)
• Inventors: Venugopal, Nandagopal, Watkins, Kristen L.
• Primary Examiner(s): FERRIS III, FRED O
• Application Number:
  US10/778,021
• Publication Number:
  US 20040162718A1
• Time in Patent Office: 1,421 Days
• Field of Search: 703/13, 703/21, 370/250, 370/255, 709/226
• US Class Current: 703/21
• CPC Class Codes: H04L 41/145 involving simulating, designing, planning or modelling of a network

Abstract

A system and method for optimizing placement of network equipment and information load in a network over a period of time. A demand input structure having a plurality of demands organized by their time points is provided as an input to a model generator and an optimization processor associated therewith. Starting with the earliest demand set to be serviced by the network, a directed graph network model is obtained by using appropriate transformation techniques. A cost function associated with the network model is constructed using a flow cost term and an equipment cost term. Appropriate constraints are imposed on the cost function for optimization. A solution set comprising network placement information and demand routing information is obtained for a current time point. When the next demand set is taken up for optimization, the network model and associated cost function are recursively updated by using the solution set obtained for the demand set at a prior time point. The recursive optimization process takes place for each of the demand sets provided in the demand input structure in accordance with their time points. Preferably, Priority 1 demands are optimized first. Thereafter, Priority 2 demands are optimized by employing a capacitated shortest path algorithm with respect to each Priority 2 demand presented in its order.

Claims

1. A planning method for optimally deploying network equipment in a network over a period of time, said network including a span disposed between at least two sites, the method comprising:

providing a demand input structure having a plurality of demands to be serviced by said network, each of the demands being associated with a corresponding time point and a demand quantity indicating units of communication capacity;

sorting said plurality of demands by their time points;

starting with a set of the demands having an earliest time point;

transforming said network into a network model including a multi-nodal directed graph having a plurality of arcs, said transforming being based on a topology of said network;

optimizing the routing of said set of demands using said multi-nodal directed graph and a cost function associated therewith;

obtaining network equipment placement information and demand routing information based on said optimizing of the routing of said set of demands;

updating said network model and said cost function associated therewith based on said network equipment placement information and said demand routing information;

repeating said optimizing, said obtaining, and said updating for remaining time points provided in said demand input structure, using said updated network model and cost function to optimize the routing of the remaining demands associated with said time points; and

outputting a network equipment deploying solution based on the updated network model and the cost function associated therewith when all time points have been processed.

2. The planning method of claim 1, further comprising:

scheduling successive deployment of said network equipment in said network based on said network equipment placement information obtained for each of said time points.

3. The planning method of claim 1, wherein each of said plurality of demands is associated with a selected communications channel rate between said sites.

4. The planning method of claim 3, wherein said selected communications channel rate is the same for each of said plurality of demands.

5. The planning method of claim 3, wherein said selected communications channel rate is different for said plurality of demands.

6. The planning method of claim 1, wherein said demand input structure comprises a data structure residing in a computer-readable medium device.

7. The planning method of claim 1, wherein said plurality of demands comprises a portion of higher priority demands and a portion of lower priority demands.

8. The planning method of claim 7, wherein said transforming, said optimizing, said obtaining, and said updating are performed first for optimizing said portion of higher priority demands.

9. The planning method of claim 8, further comprising optimizing said portion of lower priority demands by using a capacitated shortest path algorithm with respect to each of said lower priority demands.

10. The planning method of claim 1, wherein said network equipment placement information comprises an indication of the presence of an Add/Drop Multiplexer at a selected site.

11. The planning method of claim 1, wherein said network equipment placement information comprises an indication of the absence of an Add/Drop Multiplexer at a selected site.

12. The planning method of claim 1, wherein said cost function comprises a flow cost term and an equipment cost term.

13. The planning method of claim 1, wherein said optimizing is performed by employing an integer programming technique.

14. The planning method of claim 1, wherein said multi-nodal directed graph is derived from a ring structure associated with said network.

15. The planning method of claim 1, wherein the demand quantity indicates a particular multiplexer level.

16. The planning method of claim 1, wherein said optimizing further comprises sorting the plurality of demands by corresponding ones of the demand quantities.

17. The planning method of claim 16, wherein said sorting is performed in descending order based on the corresponding ones of the demand quantities.

18. The planning method of claim of claim 1, wherein said optimizing further comprises providing a time-slot-assignment-compliant solution set.

19. The planning method of claim 18, wherein said time-slot-assignment-compliant demand routing is derived from at least one time-slot-interchange-compliant solution set.