System and method for planning multiple MUX levels in a fiber optic network simulation plan

• US 6,654,354 B1
• Filed: 12/22/1999
• Issued: 11/25/2003
• Est. Priority Date: 12/22/1999
• Status: Expired due to Fees

• Current Assignee: Verizon Patent and Licensing Incorporated (Verizon Communications Inc.)
• Original Assignee: WorldCom, Inc. (Verizon Communications Inc.)
• Inventors: Venugopal, Nandagopal, Watkins, Kristen L.
• Primary Examiner(s): Kizou, Hassan
• Assistant Examiner(s): ODLAND, DAVID E
• Application Number:
  US09/469,691
• Time in Patent Office: 1,434 Days
• Field of Search: 370/211, 370/229-231, 370/235, 370/238, 370/254, 370/255, 370/258, 370/351, 370/546, 379/112.05, 710/29, 710/36-45, 710/107
• US Class Current: 370/258
• CPC Class Codes: H04J 2203/0055 Network design, dimensioning, topology or optimisation
• CPC Class Codes: H04J 3/085 for ring networks, e.g. SDH/SONET rings, self-healing rings, meashed SDH/SONET networks
• 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 and MUX levels is provided as an input to a model generator and an optimization processor associated therewith. Starting with the earliest demand with the highest MUX level to be serviced by the network, a directed graph network model is obtained by using appropriate transformation techniques. A MUX modularity constraint is imposed in order to obtain a filtered network model that can support a MUX level of a selected demand at a particular time point. A cost function associated with the filtered 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 MUX level at a current time point. When the next MUX level of the demand is taken up for optimization, the filtered network model and associated cost function are recursively updated by using the solution set obtained for the previous MUX level. The recursive optimization process takes place for each time point, covering all MUX levels at that time point, as provided in the demand input structure. 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 system for optimizing placement of network equipment and distribution of information load in a network, comprising:

a demand input structure having a plurality of demands organized by their respective MUX levels;

a model generator coupled to said demand input structure for receiving demand data therefrom, said model generator for transforming said network into a network model;

a modularity structure for applying a MUX modularity constraint with respect to said network model in order to obtain a filtered network model that can support a MUX level of a selected demand;

an optimization processor associated with said model generator for acting on said filtered network model, said optimization processor operating to minimize a cost function corresponding to said filtered network model so as to generate a solution set comprising network placement information and demand routing information for said MUX level; and

updating means to recursively update said network model and said cost function for each MUX level in said demand input structure based on said solution set obtained for a previous MUX level, said updating means operating responsive to said modularity structure.

2. The system as set forth in claim 1, wherein said network model comprises a multi-nodal directed graph derived from transforming a ring structure associated with said network by said model generator.

3. The system as set forth in claim 1, wherein said demand input structure further comprises a time point variable such that each of said plurality of demands is associated with a corresponding time point, said plurality of demands being partitioned by said MUX level within each time point.

4. The system as set forth in claim 3, wherein said updating means recursively updates said network model and said cost function for each time point in said demand input structure, after updating said filtered network model and said cost function for each MUX level within each time point.

5. The system as set forth in claim 4, wherein said MUX levels are selected from a group consisting of:

OC-192, OC-48, OC-12, OC-3, and DS-3 levels.

6. The system as set forth in claim 4, wherein said demand input structure comprises a data structure residing in a computer-readable medium device.

7. The system as set forth in claim 4, wherein said plurality of demands comprises a portion of Priority 1 demands and a portion of Priority 2 demands.

8. The system as set forth in claim 4, further comprising means for optimizing said portion of Priority 2 demands after said Priority 1 demands have been optimized by recursively updating said network model and said cost function for all time points associated with said Priority demands.

9. The system as set forth in claim 8, wherein said means for optimizing said portion of Priority 2 demands comprises a structure for executing a capacitated shortest path algorithm with respect to each of said Priority 2 demands.

10. A planning method for optimally deploying network equipment in a network over a period of time, comprising the steps of:

(A) providing a demand input structure having a plurality of demands to be serviced by said network, wherein each demand is associated with a corresponding time point and a MUX level;

(B) partitioning said plurality of demands by their time points, each time point having one or more MUX levels;

(C) starting with a demand having the earliest time point and highest MUX level within said time point,

(C1) transforming said network into a network model;

(C2) applying a MUX modularity constraint with respect to said network model in order to obtain a filtered network model that can support a MUX level of a selected demand;

(C3) optimizing the routing of said selected demand using said filtered network model and a cost function associated therewith;

(C4) obtaining network equipment placement information and demand routing information from said optimizing step; and

(C5) updating said filtered network model and said cost function associated therewith based on said network equipment placement information and said demand routing information, said updating step being subject to said MUX modularity constraint; and

(D) repeating steps (C2)-(C5) for each remaining MUX level within each remaining time point provided in said demand input structure, using said updated filtered network model and cost function to optimize the routing of the remaining demands.

11. The planning method as set forth in claim 10, further comprising the step of:

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

12. The planning method as set forth in claim 10, wherein said demand input structure comprises a data structure residing in a computer-readable medium device.

13. The planning method as set forth in claim 10, wherein said plurality of demands comprises a portion of Priority 1 demands and a portion of Priority 2 demands.

14. The planning method as set forth in claim 13, wherein steps (C1)-(C5) are performed first for optimizing said portion of Priority 1 demands.

15. The planning method as set forth in claim 14, further comprising the step of optimizing said portion of Priority 2 demands by using a capacitated shortest path algorithm with respect to each of said Priority 2 demands.

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

17. The planning method as set forth in claim 10, wherein said network equipment placement information comprises an indication of the absence of an Add/Drop Multiplexer at a selected site.

18. The planning method as set forth in claim 10, wherein said cost function comprises a flow cost term and an equipment cost term.

19. The planning method as set forth in claim 10, wherein said optimizing step (C3) is performed by employing an integer programming technique.

20. The planning method as set forth in claim 10, wherein said net work model comprises a multi-nodal directed graph derived from a ring structure associated with said network.

21. A network planning system for optimally deploying network equipment in a Fiber Optic Network having at least one ring (designated as a “

network topology”

), comprising;

a computer-readable demand input data structure having a plurality of demands with different MUX levels to be serviced by said network topology over a series of time points, wherein each demand is associated with a corresponding time point;

means for partitioning said plurality of demands by their time points and MUX levels, wherein each time point includes one or more MUX levels;

means for transforming said network topology into a multi-nodal directed graph network model having a plurality of arcs;

MUX modularity means for applying a MUX modularity constraint with respect to said network model in order to obtain a filtered network model that can support a MUX level of a selected demand at a particular time point;

processor means for optimizing the routing of said demands using said filtered network model and a cost function associated therewith, said processor means providing a solution set comprising network equipment placement information and demand routing information for a current time point; and

updating means to recursively update said filtered network model and said cost function associated therewith for each MUX level within each time point of said demand input data structure based on said solution set obtained previously, said updating means operating in conjunction with said MUX modularity means.

22. The network planning system as set forth in claim 21, wherein said cost function includes a flow cost term and an equipment cost term.

23. The network planning system as set forth in claim 21, wherein said network equipment placement information comprises an indication of the presence of an Add/Drop Multiplexer at a selected site.

24. The network planning system as set forth in claim 21, wherein said network equipment placement information comprises an indication of the absence of an Add/Drop Multiplexer at a selected site.