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

• US 20040162718A1
• Filed: 02/17/2004
• Published: 08/19/2004
• Est. Priority Date: 12/22/1999
• Status: Active Grant

• Current Assignee: Verizon Patent and Licensing Incorporated (Verizon Communications Inc.)
• Original Assignee: MCI WorldCom, Inc. (Verizon Communications Inc.)
• Inventors: Venugopal, Nandagopal, Watkins, Kristen L.
• Granted Patent: US 7,318,016 B2
• Time in Patent Office: Days
• 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 system for optimizing placement of network equipment and distribution of information load in a network disposed among at least two sites, comprising:

a demand input structure having a plurality of demands organized by their respective time points;

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;

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

updating means to recursively update said network model and said cost function for each time point in said demand input structure based on said solution set obtained for a previous time point.

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 each of said plurality of demands is associated with a selected communications channel rate desired between said sites.

4. The system as set forth in claim 3, wherein said selected communications channel rate desired between said sites is the same for each of said plurality of demands.

5. The system as set forth in claim 3, wherein said selected communications channel rate desired between said sites is different for said plurality of demands.

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

7. The system as set forth in claim 1, 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 7, further comprising means for optimizing said portion of Priority 2 demands after each of 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 1 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, said network including a span disposed between at least two sites, 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;

(B) sorting said plurality of demands by their time points;

(C) starting with a demand set having the earliest time point,

(C1) transforming said network into a network model;

(C2) optimizing the routing of said demand set using said network model and a cost function associated therewith;

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

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

(D) repeating steps (C2)-(C4) for the 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.

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 each of said plurality of demands is associated with a selected communications channel rate desired between said sites.

13. The planning method as set forth in claim 12, wherein said selected communications channel rate desired between said sites is the same for each of said plurality of demands.

14. The planning method as set forth in claim 12, wherein said selected communications channel rate desired between said sites is different for said plurality of demands.

15. 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.

16. 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.

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

18. The planning method as set forth in claim 17, 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.

19. 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.

20. 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.

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

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

23. 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.

24. A network planning system for optimally deploying network equipment in a Fiber Optic Network having one or more rings (designated as a “

network topology”

) disposed among at least two sites, comprising;

a computer-readable demand input data structure having a plurality of demands 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 sorting said plurality of demands by their time points;

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

processor means for optimizing the routing of said demands using said multi-nodal directed graph 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 multi-nodal directed graph model and said cost function associated therewith for each time point of said demand input data structure based on said solution set.

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

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

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