Method and system for planning and installing communication networks

For use in cooperation with a computer having memory, a system for placing Self-Healing Rings (SHRs) in a Synchronous Optical Network (SONET) and routing point-to-point demand in accordance with projected customer demand over a selected multi-period time interval, comprising:

• means for determining a number of nodes within the SONET;
• means for identifying a number of periods within the selected multi-period time interval;
• means for determining the projected customer demand between said nodes over said selected multi-period time interval;
• means for determining a discounted add-drop cost for a plurality of Add/Drop Multiplexers (ADMs);
• means for determining optimized discounted fixed and interconnection costs for said plurality of selected ADMs in accordance with a first selected mixed integer program;
• means for determining a set of logical SHRs and corresponding preliminary routing plans;
• means for storing in the memory of the computer logical SHR data and preliminary routing data corresponding to said set of logical SHRs and corresponding preliminary routing plans;
• means for determining from said logical SHR data and preliminary routing data the optimized placement of physical SHRs, optimized cash flow out and optimal traffic routing in accordance with a second selected mixed integer program;
• means for storing in the memory of the computer optimized placement data of physical SHRs, optimized cash flow data and optimal traffic routing data corresponding to the determined optimized placement of the physical SHRs, the determined optimized cash flow and said determined optimal traffic routing such that said SHRs may be placed in the SONET in accordance therewith.

For use in cooperation with a computer having memory, a method of placing Self-Healing Rings (SHRs) in a Synchronous Optical Network (SONET) and routing point-to-point demand in accordance with projected customer demand over a selected multi-period time interval, comprising:

• determining a number of nodes within the SONET;
• identifying a number of periods within the selected multi-period time interval;
• determining demand between said nodes during each of said multi-period time intervals;
• determining a discounted add-drop cost for a plurality of selected Add/Drop Multiplexers (ADMs);
• loading traffic to existing rings by repetitively identifying a smallest point-to-point demand between nodes on said existing rings and assigning said demand to said rings until no demand left can be routed;
• creating a proposed ring by identifying a greatest unsatisfied point-to-point demand between two adjacent nodes and assigning said nodes to said rings;
• randomly creating additional proposed rings until all demand has been satisfied;
• randomly expanding said created rings until all demand has been satisfied by:
• (a) repetitively determining a largest unsatisfied demand of neighbor nodes for each of said created rings, (b) identifying a plurality of said neighbor nodes having the greatest unsatisfied demand, (c) determining a deficit of each of said created rings, (d) identifying a plurality of said created rings with the greatest deficit, and (e) randomly selecting for expansion one of said plurality of created rings and one of said plurality of neighbor nodes and assigning the same to one another;
• loading inter-ring traffic to said created rings until all demand has been routed by repetitively identifying demand that can be routed the greatest distance through the smallest number of said created rings and assigning said demand accordingly so as to determine a set of logical SHRs and preliminary routing plans;
• storing in the memory of the computer logical SHR data and preliminary routing data corresponding to said set of logical SHRs and corresponding preliminary routing plans;
• determining from said logical SHR data and preliminary routing data the optimized placement of physical SHRs, optimized cash flow out and optimal traffic routing in accordance with a second selected mixed integer program;
• storing in the memory of the computer optimized placement data of physical SHRs, optimized cash flow data and optimal traffic routing data corresponding to the determined optimized placement of the physical SHRs, the determined optimized cash flow and said determined optimal traffic routing;
• and
• placing said SHRs in said SONET in accordance with said optimized SHR placement data, said optimized cash flow out data and said optimal traffic routing data.

For use in cooperation with a computer having memory, a system for placing Self-Healing Rings (SHRs) in a Synchronous Optical Network (SONET) and routing point-to-point demand in accordance with projected customer demand over a selected multi-period time interval, comprising:

• means for determining a number of nodes within the SONET;
• means for identifying a number of periods within the selected multi-period time interval;
• means for determining the projected customer demand between said nodes over said selected multi-period time interval;
• means for determining a discounted add-drop cost for a plurality of Add/Drop Multiplexers (ADMs);
• means for determining optimized discounted fixed and interconnection costs for said plurality of selected ADMs in accordance with a first selected mixed integer program;
• means for determining a set of logical SHRs and corresponding preliminary routing plans;
• means for storing in the memory of the computer logical SHR data and preliminary routing data corresponding to said set of logical SHRs and corresponding preliminary routing plans;
• means for determining from said logical SHR data and preliminary routing data the optimized placement of physical SHRs, optimized cash flow out and optimal traffic routing in accordance with a second selected mixed integer program;
• means for storing in the memory of the computer optimized placement data of physical SHRs, optimized cash flow data and optimal traffic routing data corresponding to the determined optimized placement of the physical SHRs, the determined optimized cash flow and said determined optimal traffic routing such that said SHRs may be placed in the SONET in accordance therewith.