Method and system for planning and installing communication networks

• US 5,515,367 A
• Filed: 10/01/1993
• Issued: 05/07/1996
• Est. Priority Date: 05/08/1990
• Status: Expired due to Term

• Current Assignee: Qwest Communications International Incorporated (Lumen Technologies, Inc.)
• Original Assignee: U.S. West Advanced Technologies, Inc.
• Inventors: Lu, Lu, Tegan, George E., Qiu, Yuping, Cox, Louis A. Jr.
• Primary Examiner(s): Chin, Wellington
• Application Number:
  US08/130,350
• Time in Patent Office: 949 Days
• Field of Search: 370/13, 370/17, 370/60, 370/60.1, 370/94.1, 370/94.2, 370/85.13, 370/85.14, 370/85.15, 370/16.1
• US Class Current: 370/404
• CPC Class Codes: H04J 2203/0057 Operations, administration and maintenance [OAM]
• 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/0826 for reduction of network costs H04L41/0833 takes precedence
• CPC Class Codes: H04L 41/145 involving simulating, designing, planning or modelling of a network
• CPC Class Codes: H04L 41/22 comprising specially adapted graphical user interfaces [GUI]
• CPC Class Codes: H04Q 3/002 Details
• CPC Class Codes: H04Q 3/0083 Network planning or design; Modelling of planned or existing networks

Abstract

A method is disclosed for use in cooperation with a computer having memory in a Synchronous Optical Network (SONET) for generating an optimized transition plan for the placement of Self-Healing Rings (SHR) and the routing of point-to-point demand in accordance with projected customer demand over a selected multi-period time interval. By determining the number of nodes within a SONET, the demand therebetween over selected time interval as well as the discounted add-drop cost for a plurality of selected Add-Drop Multiplexers (ADMs), a set of logical rings as well as a set of physical rings and detailed routing information may be obtained and graphically illustrated. Logical rings may be determined by optimizing discounted fixed and interconnection costs for the plurality of ADMs in accordance with a selected mixed integer program to generate a corresponding electrical signal for receipt by the computer memory. Thereafter, the placement of physical self-healing rings, the cash flow out and optimal traffic routing may be determined in accordance with a second selected mixed integer program whereupon a second electrical signal may be generated corresponding thereto. Utilizing a heuristic approach, where the number of nodes under study is high, logical rings may be determined through an iterative process of randomly generating new proposed rings or, in the alternative, randomly expanding existing proposed rings until all demand has been satisfied.

Claims

1. 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 the projected customer demand between said nodes over said selected multi-period time interval;

determining a discounted add-drop cost for a plurality of selected Add/Drop Multiplexers (ADMs);

determining optimized discounted fixed and interconnection costs for said plurality of ADMs in accordance with a first selected mixed integer program;

determining a set of logical SHRs and corresponding 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, 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 optimized traffic routing data.

2. The method of claim 1, wherein said first mixed integer program may be expressed as:

##EQU5## to subject ##EQU6## wherein, n=number of central offices in the network;

T=number of time periods in the planning horizon;

d_ikt =demand in units of DS3 between offices i and k in period t;

a_jt =discounted fixed cost for an ADM of ring j installed in period t;

B_jrt =discounted optical inter-ring traffic cost between ring j and ring r in period t;

b_jrt =b_jrt =B_jrt =B_jr,t+1, 1≦

j<

r≦

m_T ;

C_jrt =discounted electrical inter-ring traffic cost between ring j and ring r in period t;

c_jrt =c_jrt =C_jrt -C_jr,t+1, 1≦

j<

r≦

m_T ;

m_t =maximum number of rings to be installed by time period t;

l_t =number of fixed rings to be installed in time period t;

C_j =capacity of ring j in units of OC;

S_j =maximum size of ring j;

N_j =set of offices on fixed ring j;

f_ikjrt =traffic between offices i and k routed from ring j to ring r in period t;

(office i is on ring j, office k is on ring r).

h_jrt =number of optical OC3 connections between ring j and ring r in period t;

g_jrt =electrical inter-ring traffic routed from ring j to ring r in period t;

x_ij =x_ij =1 if office i is on ring j;

x_ij =0 otherwise. and

(i) discounted fixed cost for an ADM of ring j in period t;

a_jt = Shelf+20/E plug+(ADM OC3+MUX OC3+Equiv Elec drop)/2)·

e_t ;

(ii) discounted optical inter-ring traffic cost per OC3 between ring j and ring r in period t;

B_jrt = 2 ADM OC3 of ring j+2 ADM OC3 of ring r!·

e_t ;

(iii) discounted electrical inter-ring traffic cost per DS3 between ring j and ring r in period t;

C_jrt = 2 (ADM OC3+MUX OCS+Equiv Elec drop) of ring j+2 (ADM OC3+MUX OC3+Equiv Elec drop) of ring r!·

e_t /3;

wherein e_t =(1+α

)^-t, and α

is the annual discount rate.

3. The method of claim 1, wherein said second mixed integer program may be expressed as:

##EQU7## subject to ##EQU8## where, d_ik ;

demand between offices i and k, i<

k;

J;

index set of fixed rings;

R_j ;

set of offices on ring j, j ε

J;

b_jr ;

optical OC3 inter-ring traffic cost between rings r and r,j<

r;

c_jr ;

electrical inter-ring traffic cost between rings j and r,j<

r, |R_j ∩

R_r ∩

|≧

2;

C_j ;

capacity of ring j, j ε

J;

r;

r=2|J|max{b_jr +c_jr } Σ

d_ik ;

z;

fraction of total demand being covered;

f_ikjr ;

traffic between offices i and k routed from ring j to ring r (i is on ring j, k on ring r);

h_jr ;

number of optical OC3 connections between rings j and r;

g_jr ;

electrical inter-ring traffic routed form ring j to ring r.

4. The method of claim 1, further comprising converting said logical SHR data and preliminary routing data to graphic data;

and

displaying said graphic data on a user-friendly interface.

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

6. The system of claim 5, further comprising means for converting said logical SHR data and preliminary routing data to graphic data;

and

means for displaying said graphic data on a user-friendly interface.

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

8. The method of claim 7, wherein said selected mixed integer program may be expressed as:

##EQU9## subject to ##EQU10## where, d_ik ;

demand between offices i and k, i<

k;

J;

index set of fixed rings;

R_j ;

set of offices on ring j, j ε

J;

b_jr ;

optical OC3 inter-ring traffic cost between rings r and r,j<

r;

c_jr ;

electrical inter-ring traffic cost between rings j and r,j<

r, |R_j ∩

R_r ∩

|≧

2;

C_j ;

capacity of ring j, j ε

J;

r;

r=2|J|max{b_jr +c_jr } Σ

d_ik ;

z;

fraction of total demand being covered;

f_ikjr ;

traffic between offices i and k routed from ring j to ring r

g_jr ;

pelectrical inter-ring traffic routed form ring j to ring r.

9. The method of claim 7, further comprising converting said logical SHR data and preliminary routing data to graphic data;

and

displaying said graphic data on a user-friendly interface.

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

11. The system of claim 10, further comprising means for converting said logical SHR data and preliminary routing data to graphic data;

and

means for displaying said graphic data on a user-friendly interface.