Network design apparatus and network design method

This application is based upon and claims the benefit of priority of the prior Japanese Patent Application No. 2008-230122, filed on Sep. 8, 2008, the entire contents of which are incorporated herein by reference.

The embodiments discussed herein are related to a network design apparatus, a computer program product, and a network design method for arranging optical transmission equipment constituting an optical network system which is placed at stations.

In recent years, in the field of WDM (Wavelength Division Multiplexing) networks, OADMs have been implemented (Optical Add Drop Multiplexers) and optical hubs, such as WXCs (Wavelength Cross Connects), that can split and insert traffic and can switch paths on a wavelength-by-wavelength basis without converting optical signals into electrical form.

The implementation of such equipment has made it possible to construct complicated networks, such as interconnected ring networks and mesh networks.

When designing a WDM network, optical network information, including information concerning stations where equipment constituting the WDM system can be placed and information concerning the optical fibers interconnecting the stations, is applied along with wavelength path information concerning wavelength paths propagating in the WDM network. Hereinafter, optical transmission equipment constituting such a WDM system may sometimes be referred to as “WDM equipment.” The WDM equipment includes, for example, equipment such as OADMs and ILAs (In-Line Amplifiers) or bypasses which are described later.

OADMs are placed at both end stations serving as the start and end points of a wavelength path, while on the other hand, at other stations serving as relay stations, ILAs or OADMs as repeaters can be placed. By using an OADM as a repeater, it is possible at each relay station to regenerate and relay any desired wavelength path and to compensate for a tilt of a WDM signal.

Rather than placing OADMs or ILAs, optical fibers may be simply connected at relay stations to relay optical signals. In the following description, any relay station where optical fibers are simply connected in this manner may sometimes be referred to as a “bypass station,” and the relay means constructed by simply connecting optical fibers may sometimes be referred to as a “bypass.”

An optical network design method is proposed which designs an optical network by using integer programming so that traffic flowing along a failed path is switched to another working optical path, thus eliminating the need to provide a dedicated protection optical path.

An optical network design method is also proposed which determines, by using integer programming, the placement of working and protection optical paths that minimizes the network cost in an optical network in which a plurality of optical transmission links share the same optical transmission equipment.

According to an embodiment, there is provided a network design apparatus includes an information acquiring unit that acquires topology information concerning an optical network, equipment information concerning the kind of optical transmission equipment that can be placed at each station in the optical network, span information indicating transmission path conditions occurring between stations adjacent to each other on the topology information, and wavelength path information concerning each wavelength path propagating in the optical network, a section dividing unit that divides the optical network, defined by the topology information into linear sections, a combination candidate determining unit that determines candidates for combinations of various kinds of optical transmission equipment to be placed at each station in each of the linear sections, a noise amount upper limit value determining unit that determines a noise amount upper limit value in accordance with a prescribed condition specified by the wavelength path information and corresponding to an upper limit to the amount of noise allowed for each wavelength path, and an equipment placement unit that determines the optical transmission equipment to be placed along each of the linear sections, by solving an integer programming problem having an objective function that minimizes the sum of the cost of the optical transmission equipment to be placed in the optical network and the cost needed to place a necessary number of OEO regenerators for each wavelength path, subject to constraints that combinations of the various kinds of optical transmission equipment are selected, one for each linear section, from among the combination candidates and that the number of OEO regenerators necessary for each wavelength path is determined by a cumulative amount of the noise occurring along the wavelength path, determined in accordance with the transmission path conditions specified by the span information, and the noise amount upper limit value determined for the wavelength path.

The object and advantages of the invention will be realized and attained by means of the elements and combinations particularly pointed out in the claims. It is to be understood that the foregoing general description and detailed description are exemplary and explanatory and are not restrictive of the invention, as claimed.

FIG. 1 is a diagram illustrating an optical network to be designed.

FIG. 2 is a diagram illustrating examples of the kinds of optical transmission equipment that can be placed at stations.

FIG. 3 is a diagram illustrating one example of an OADM depicted in FIG. 2 .

FIG. 4 is a diagram illustrating one example of an ILA depicted in FIG. 2 .

FIG. 5 is a diagram illustrating one example of a bypass depicted in FIG. 2 .

FIG. 6 is a diagram illustrating the hardware configuration of a network design apparatus of an embodiment implemented using a CPU.

FIG. 7 is a block diagram of the network design apparatus implemented by causing the CPU depicted in FIG. 6 to execute a network design program.

FIG. 8 is a block diagram of a parameter determining unit depicted in FIG. 7 .

FIG. 9 is a block diagram of an initial candidate generating unit depicted in FIG. 7 .

FIG. 10 is a block diagram of an additional candidate searching unit depicted in FIG. 7 .

FIG. 11 is a general flowchart of a network design method according to an embodiment.

FIG. 12 is a diagram (part 1 ) illustrating an example of the graph information generated by an intra-path graph generating unit depicted in FIG. 8 .

FIG. 13 is a diagram (part 2 ) illustrating an example of the graph information generated by the intra-path graph generating unit depicted in FIG. 8 .

FIG. 14 is a diagram illustrating how a first link selecting unit depicted in FIG. 8 selects an input link.

FIG. 15 is a flowchart illustrating one example of the selection process performed by the first link selecting unit depicted in FIG. 8 .

FIG. 16 is a diagram illustrating the results of the input link selection process performed by the first link selecting unit depicted in FIG. 8 .

FIG. 17 is a flowchart illustrating one example of a relay node determination process performed by a first node determining unit depicted in FIG. 8 .

FIG. 18 is a diagram illustrating the results of the relay node determination process performed by the first node determining unit depicted in FIG. 8 .

FIG. 19 is a flowchart illustrating one example of a method that determines optical transmission equipment configuration for each unit design section.

FIG. 20 is a diagram (part 1 ) illustrating an example of the graph information generated by a first intra-unit-design-section graph generating unit depicted in FIG. 9 .

FIG. 21 is a diagram (part 2 ) illustrating an example of the graph information generated by the first intra-unit-design-section graph generating unit depicted in FIG. 9 .

FIG. 22 is a diagram illustrating how a second link selecting unit depicted in FIG. 9 selects an input link.

FIG. 23 is a flowchart (part 1 ) illustrating one example of the selection process performed by the second link selecting unit depicted in FIG. 9 .

FIG. 24 is a flowchart (part 2 ) illustrating one example of the selection process performed by the second link selecting unit depicted in FIG. 9 .

FIG. 25 is a diagram illustrating the results of the input link selection process performed by the second link selecting unit depicted in FIG. 9 .

FIG. 26 is a diagram illustrating the results of the relay node determination process performed by a second node determining unit depicted in FIG. 9 .

Generally, there is a tradeoff between the cost of WDM equipment placed at a station and the transmission quality of the WDM signal transmitted via the station. That is, as the cost of the WDM equipment increases, the transmission quality of the WDM signal increases. This serves to reduce the number of OEO regenerators necessary for each wavelength path propagating in the optical network. On the other hand, as the number of pieces of low-cost WDM equipment increases, the number of OEO regenerators has to be increases.

Accordingly, a network design may be performed preferably so as to minimize the total cost of the WDM equipment and OEO regenerators, i.e., the cost required to construct a network.

A specific procedure employed in WDM equipment placement may be as follows:

(1) The network is divided into a plurality of sub-networks having a linear or ring topology. (2) The placement that minimizes the cost of the WDM equipment is determined for each sub-network.

In the thus designed WDM network, the total cost of the WDM equipment is minimized.

However, with the WDM equipment placement method described above, if there is a wavelength path extending across a plurality of sub-networks, the placement of the WDM equipment is not always optimized for such a wavelength path, and there may arise a need to increase the number of OEO regenerators to compensate for the degradation of transmission quality of the WDM signal. That is, depending on the design of the wavelength path, the placement determined by the above-mentioned WDM equipment placement method may not always minimize the total cost of the entire network.

In order to determine the combination of the various kinds of WDM equipment to be placed at the stations so as to minimize the total cost of the entire network, the number of OEO regenerators necessary for each wavelength path is estimated properly for each combination. However, to properly estimate the number, it may become necessary to consider not only OSNR (Optical Signal-to-Noise Ratio) but also impairments due to PMD (Polarization Mode Dispersion), crosstalk, etc. Since the OSNR and impairment values also depend on the combination of the various kinds of WDM equipment, it is difficult to estimate the number of OEO regenerators.

Hereinafter, the combination of the various kinds of WDM equipment to be placed at the respective stations in the network, i.e., the relative disposition of the various kinds of WDM equipment placed at the respective stations, may sometimes be referred to as the “WDM equipment configuration.”

When, for the optical signal received at any particular station, the received OSNR given by the following equation is not lower than the OSNR tolerance determined according to the kind of the optical signal, the optical signal can be transmitted to or received at that station.

Received OSNR=OSNR−Impairments

On the other hand, when the received OSNR is lower than the OSNR tolerance, since the optical signal becomes unable to be transmitted or received, the optical signal needs to be regenerated by an OEO regenerator before transmission. The amount of noise, NOISE, per unit optical power, which is the reciprocal of OSNR, is a linear value, and when an OSNR value [dB] is given, NOISE is expressed as

NOISE=10 −(OSNR/10)

When not considering impairments, the required number of OEO regenerators can be estimated from the amount of noise relatively easily, but it is difficult to estimate the required number of OEO regenerators with high accuracy by considering the impairments.

The embodiments will be described with reference to the accompanying drawings. FIG. 1 is a diagram illustrating an optical network to be designed. The optical network 200 depicted in FIG. 1 is a mesh network constituting a WDM system. Each box represents a station where an optical add-drop multiplexer is placed. The station where an optical add-drop multiplexer is placed is, for example, a station where a wavelength path terminates. Each circle represents a station, located along a path between stations indicated by boxes, for relaying a WDM optical signal between them. Each double-headed dashed arrow indicates a linear section in the optical network 200 .

The network design apparatus according to an embodiment takes each linear section in the network 200 as a unit design section, and determines the combination of the various kinds of optical transmission equipment to be placed at the respective stations in the linear network defined by the unit design section.

Hereinafter, the combination of the various kinds of optical transmission equipment to be placed at the respective stations in the network, i.e., the way the various kinds of optical transmission equipment are placed or to be placed at the respective stations, may sometimes be referred to as the “optical transmission equipment configuration.”

As depicted by dashed arrows, the linear sections are each formed by connecting two or more stations in cascade, and the stations need not necessarily be connected in a physically straight line but may be connected in a curved line fashion. For example, the linear section 202 is formed by connecting the stations 1 to 4 in cascade, the linear section 203 is formed by connecting the stations 4 to 6 in cascade, and the linear section 204 is formed by connecting the stations 11 to 18 in cascade.

The stations 1 and 4 as the start and end points of the linear section 202 , the stations 4 and 6 as the start and end points of the linear section 203 , and the stations 11 and 18 as the start and end points of the linear section 204 are each provided with optical transmission equipment capable of accommodating an OEO regenerator.

The section indicated by a semi-dashed arrow 201 represents a section through which a wavelength path d propagating in the network 200 passes. The start and end points of the wavelength path d are the stations 1 and 6 , respectively, and the path extends across a plurality of sections, i.e., two sections 202 and 203 .

FIG. 2 is a diagram illustrating examples of the kinds of optical transmission equipment that can be placed at the respective stations. The kinds of optical transmission equipment that can be placed at the stations include, for example, OADM 310 , ILA 320 , and bypass 330 . OADM 310 is the kind of optical transmission equipment that is capable of accommodating an OEO regenerator for a designated wavelength signal. The OEO regenerator can perform 3Rs which stands for Re-amplification, Re-shaping, and Re-timing.

ILA 320 and bypass 330 are optical transmission equipment not capable of accommodating an OEO regenerator. ILA 320 can only perform 1 R which stands for Re-amplification for amplifying an optical signal. Bypass 330 is a device that only passes an optical signal therethrough. Of these kinds of optical transmission equipment, the installation cost of OADM 310 is the highest, and the installation cost of bypass 330 is the lowest; the installation cost of ILA 320 is intermediate between the above two.

On the other hand, the transmission quality is the lowest when bypass 330 is installed and the highest when OADM 310 is installed; the transmission quality when ILA 320 is installed is intermediate between the above two. Therefore, the transmission quality is a tradeoff with the cost needed for the placement of the optical transmission equipment.

FIG. 3 is a block diagram illustrating one example of the OADM depicted in FIG. 2 . The OADM 400 includes an amplifier 401 , a splitter 402 , a demultiplexer 403 , OEO regenerators 404 and 405 , a multiplexer 406 , a WSS 407 , and an amplifier 408 . The amplifier 401 amplifies a WDM optical signal arriving from outside the OADM 400 , and provides the output signal to the splitter 402 . The OEO regenerator 404 is provided as required for a wavelength path that needs regenerating for further transmission from among the wavelength paths contained in the input WDM optical signal.

The splitter 402 splits the WDM optical signal output from the amplifier 401 and directs the thus split WDM optical signals to the demultiplexer 403 and the WSS 407 , respectively. The demultiplexer 403 wavelength-demultiplexes the WDM optical signal reflected by the splitter 402 , and supplies the wavelength-demultiplexed signals to the OEO regenerators 404 and 405 .

The OEO regenerators 404 and 405 regenerate the optical signals output from the demultiplexer 403 , and supply the regenerated signals to the multiplexer 406 . The multiplexer 406 wavelength-multiplexes the optical signals output from the OEO regenerators 404 and 405 , and supplies the wavelength-multiplexed WDM signal to the WSS 407 .

The WSS (Wavelength Selective Switch) 407 selects and combines the optical signals contained in the WDM optical signal transmitted through the splitter 402 and the optical signals contained in the WDM optical signal supplied from the multiplexer 406 , and provides the resulting WDM optical signal to the amplifier 408 . The WSS 407 has the further function of equalizing the level of the WDM optical signal to be output to the amplifier 408 . The amplifier 408 amplifies the WDM optical signal output from the WSS 407 , and the amplified signal is output from the OADM 400 .

FIG. 4 is a block diagram illustrating one example of the ILA depicted in FIG. 2 . The ILA 500 includes an amplifier 501 , a VAT 502 , and an amplifier 503 . The ILA 500 jointly amplifiers all the optical signals contained in the input WDM optical signal. The WDM optical signal is input to the amplifier 501 from outside the ILA 500 . The amplifier 501 amplifies the externally input WDM optical signal, and supplies the amplified signal to the VAT 502 .

The VAT (Variable Attenuator) 502 controls the power of the WDM optical signal output from the amplifier 501 by applying a variable amount of attenuation to the WDM optical signal output from the amplifier 501 . The VAT 502 supplies the thus controlled WDM optical signal to the amplifier 503 . The amplifier 503 amplifies the WDM optical signal output from the VAT 502 , and the amplified signal is output from the ILA 500 .

FIG. 5 is a block diagram illustrating one example of the bypass depicted in FIG. 2 . The WDM optical signal is externally input to the bypass 600 . The bypass 600 includes a connector 601 for connecting the output end of the optical fiber carrying the incoming WDM optical signal to the input end of an outgoing optical fiber. The WDM optical signal input into the bypass 600 passes through the connector portion 601 and is output from the bypass 600 without any processing.

In each of FIGS. 3 to 5 , only one path is depicted that is directed from left to right in the figure, but actually, there is one more path having the same configuration but directed in the opposite direction through the equipment.

FIG. 6 is a diagram illustrating the hardware configuration of the network design apparatus of an embodiment implemented using a CPU. The network design apparatus 100 includes, in addition to the CPU 101 , a memory 102 , a user interface 103 as a keyboard, mouse, etc. for accepting user operations and data inputs, a display unit 104 , a hard disk 105 , a data input unit 106 , and a data output unit 107 .

The data input unit 106 may be, for example, a CD-ROM drive unit or a DVD-ROM drive unit. Further, the data input unit 106 and the data output unit 107 may each be implemented by a flexible disk drive unit, a removable disk drive unit such as a CD-R drive unit, a DVD-R drive unit, or an MO drive unit, an access unit for accessing a flash memory device, or a network interface unit.

The data input unit 106 is used to supply the network design apparatus 100 with WDM optical network information necessary for the network design apparatus 100 to design the optical network, as will be described later.

The data output unit 107 is used to output the design data generated in the optical network design process by the network design apparatus 100 .

The hard disk 105 stores an operating system (OS) 110 , a network design program 112 installed via the data input unit 106 , WDM optical network information 113 input via the data input unit 106 , and equipment configuration candidate data 114 indicating optical transmission equipment configuration candidates generated as will be described later for each unit design section.

FIG. 7 is a block diagram of the network design apparatus 100 implemented by causing the CPU 101 depicted in FIG. 6 to execute the network design program 112 .

As depicted, the network design apparatus 100 includes an information acquiring unit 120 , a section dividing unit 121 , a parameter determining unit 123 , an equipment configuration determining unit 124 , a storage unit 126 , an OEO regenerator placement determining unit 115 , and a design data output unit 116 .

In the present embodiment, the network design apparatus 100 is implemented through software processing by the CPU 101 . However, the network design apparatus 100 may be implemented using dedicated hardware circuits. That is, some or all of the information acquiring unit 120 , section dividing unit 121 , parameter determining unit 123 , equipment configuration determining unit 124 , OEO regenerator placement determining unit 115 , and design data output unit 116 may be implemented using dedicated hardware circuits.

The information acquiring unit 120 acquires the WDM optical network information. The WDM optical network information includes network topology information, optical transmission equipment information, span information, and wavelength path information.

The network topology information includes information concerning the stations constituting the optical network to be designed and information concerning the presence or absence of a connection between each station. The following description is a case in which the network design apparatus 100 designs the optical network 200 depicted in FIG. 1 .

The optical transmission equipment information includes information concerning the type or kind of optical transmission equipment that can be placed at each particular station, information concerning the transmission path conditions of the optical transmission equipment, information concerning the type of OEO regenerator used in each particular wavelength path, and information concerning the cost needed for the placement of such equipment.

The kinds of optical transmission equipment include, for example, OADM, ILA, and bypass. The transmission conditions include the amount of noise occurring in the optical signal passing through each particular optical transmission equipment and the impairment values associated with it. The impairment values include, for example, PMD values and crosstalk values.

The span information includes information concerning the transmission path conditions that depend on the fiber connecting between adjacent stations. The transmission path conditions include, for example, the amount of optical power loss occurring due to the fiber connecting between adjacent stations and the impairment values associated with it.

The wavelength path information is information concerning the wavelength paths passing through the optical network 200 . The wavelength path information includes information defining the number of wavelength paths and the kind of signal of each wavelength path, start point information and end point information specifying the stations serving as the start point and end point, respectively, and routing information specifying the spansstation via which each path is routed. The kind of signal of each wavelength path is defined, for example, by the bit rate.

The section dividing unit 121 divides the optical network 200 , defined by the network topology information, into linear sections, i.e., unit design sections.

The parameter determining unit 123 determines each parameter used by the network design method accordance with an embodiment described below. Such parameters include, for example, the upper limit to the amount of noise allowed for each wavelength path passing through the optical network 200 and the upper limit to each impairment. The method for determining these parameters will be described later.

The parameter determining unit 123 is one of examples of the noise amount upper limit value determining unit described in the appended claims.

The equipment configuration determining unit 124 determines the optical transmission equipment configuration candidate for each of the unit design sections generated by the section dividing unit 121 . The equipment configuration determining unit 124 determines the optical transmission equipment configuration of the optical network 200 by selecting from among the optical transmission equipment configuration candidates one optical transmission equipment configuration for each unit design section.

The OEO regenerator placement determining unit 115 determines the placement of OEO regenerators in the optical transmission equipment configuration determined by the equipment configuration determining unit 124 . The OEO regenerator placement determining unit 115 generates the design data defining the optical transmission equipment configuration of the optical network 200 and the placement of OEO regenerators, by determining the placement of an OEO regenerator as required in each corresponding optical transmission equipment in the optical transmission equipment configuration determined by the equipment configuration determining unit 124 .

The design data output unit 116 outputs the design data that contains information concerning the optical transmission equipment configuration determined by the equipment configuration determining unit 124 and information concerning the placement of OEO regenerators determined by the OEO regenerator placement determining unit 115 .

In a first embodiment, the equipment configuration determining unit 124 determines the optical transmission equipment configuration of the optical network 200 by solving an integer programming problem having an objective function that minimizes the sum of the cost of the optical transmission equipment to be placed in the optical network 200 and the cost needed to place the necessary number of OEO regenerators for each wavelength path in the optical network 200 , subject to the constraints that candidates are selected, one for each unit design section, from among the optical transmission equipment configuration candidates and that the number of OEO regenerators necessary for each wavelength path is determined by the cumulative amount of noise occurring along the wavelength path and the noise amount upper limit value determined for the wavelength path.

That is, the equipment configuration determining unit 124 determines the optical transmission equipment configuration of the optical network 200 by solving the integer programming problem given by the following equation (1).

In the integer programming problem (1), equation (1-1) corresponds to the objective function that minimizes the sum of the cost of the optical transmission equipment to be placed in the optical network 200 and the cost needed to place the necessary number of OEO regenerators for each wavelength path in the optical network 200 .

Equation (1-2) corresponds to the constraint that candidates are selected, one for each unit design section, from among the optical transmission equipment configuration candidates.

Equation (1-3) corresponds to the constraint that the number of OEO regenerators necessary for each wavelength path is determined by the cumulative amount of noise occurring along the wavelength path and the noise amount upper limit determined for the wavelength path.

The meanings of the symbols used in equation (1) are as follows:

g h (h=1 to P) denotes a number, P, of unit design sections obtained by dividing the optical network 200 .

t i indicates the optical transmission equipment configuration candidate determined for any one of the unit design sections g h . When there are M determined optical transmission equipment configuration candidates, the subscript i takes any of the values 1, 2, . . . , and M.

s i (i=1 to M) is a binary variable that indicates whether or not the optical transmission equipment configuration t i (i=1 to M) is selected as the optical transmission equipment configuration of the optical network 200 . When the optical transmission equipment configuration ti is selected as the optical transmission equipment configuration of the optical network 200 , s i =1, otherwise s i =0.

d j (j=1 to N) indicates each wavelength path constructed on the optical network 200 . Here, j takes any of the values 1, 2, . . . , and N. That is, a total of N wavelength paths d j are constructed on the optical network 200 .

x j (j=1 to N) is an integer variable that indicates the number of OEO regenerators necessary for each wavelength path d j .

c(t i ) represents the cost needed to implement the transmission equipment configuration t i .

λ(d j ) represents the number of wavelength paths d j .

r(d j ) represents the cost per repeater, needed to install the OEO regenerators along the wavelength path d j .

T(g h , t i ) is a binary parameter such that, when the transmission equipment configuration ti is the optical transmission equipment configuration candidate determined for the unit design section g h , T(g h , t i )=1, otherwise T(g h , t i )=0.

Nth(d j ) is the noise amount upper limit value determined for the wavelength path d j by the parameter determining unit 123 . Nth(d j ) represents the noise amount corresponding to the OSNR tolerance which is determined according to the kind of signal of the wavelength path d j defined by the wavelength path information.

n(d j , s 1 , s 2 , . . . , s M ) represents the cumulative amount of noise occurring along the wavelength path d j depending on the optical transmission equipment configuration selected for each unit design section specified by a binary variable vector (s 1 , s 2 , . . . , s M ), and is given by the following equation (2).

The meanings of the symbols used in equation (2) are as follows:

Re(d j , t i ) is a binary parameter such that, when the wavelength path d j passes through the unit design section g h whose optical transmission equipment configuration candidate is t i , and when the reference direction predetermined for the unit design section g h is the same as the transmission direction of the wavelength path d j , Re(d j , t i )=0, otherwise Re(d j , t i )=1.

I(d, t i ) is a binary parameter such that, when the wavelength path d j passes through the unit design section g h whose optical transmission equipment configuration candidate is t i , I(d, t i )=1, otherwise, I(d, t i )=0.

nf(t i ) indicates the amount of noise that occurs on the wavelength path propagating along the unit design section g h in the same direction as the reference direction when t i is selected as the optical transmission equipment configuration for the unit design section g h whose optical transmission equipment configuration candidate is t i .

nr(t i ) indicates the amount of noise that occurs on the wavelength path propagating along the unit design section g h in the direction opposite to the reference direction when ti is selected as the optical transmission equipment configuration for the unit design section g h whose optical transmission equipment configuration candidate is t i .

The values of nf(t i ) and nr(t i ) are determined by the amount of transmission loss of the optical signal intensity between adjacent stations, defined by the span information, and the amount of noise occurring in the optical signal passing through the optical transmission equipment constituting the optical transmission equipment configuration t i and defined by the optical transmission equipment information.

In a second embodiment, the equipment configuration determining unit 124 determines the optical transmission equipment configuration of the optical network 200 by solving the following integer programming problem (3) constructed by adding, to the integer programming problem given by equation (1), the constraint that the number of OEO regenerators necessary for each wavelength path is determined by the cumulative amount of the impairment occurring on the wavelength path and the impairment upper limit value determined for the wavelength path.

The noise amount upper limit value Nth′(d j ) that considers the impairment is used instead of the noise amount upper limit value Nth(d j ) used in the integer programming problem (1).

In the integer programming problem (3), equation (3-1) corresponds to the objective function that minimizes the sum of the cost of the optical transmission equipment to be placed in the optical network 200 and the cost needed to place the necessary number of OEO regenerators for each wavelength path in the optical network 200 .

Equation (3-2) corresponds to the constraint that candidates are selected, one for each unit design section, from among the optical transmission equipment configuration candidates.

Equation (3-3) corresponds to the constraint that the number of OEO regenerators necessary for each wavelength path is determined by the cumulative amount of noise occurring along the wavelength path and the noise amount upper limit determined for the wavelength path.

Equations (3-41), (3-42), . . . , and (3-4R) each correspond to the constraint that the number of OEO regenerators necessary for each wavelength path is determined by the cumulative amount of the impairment occurring on the wavelength path and the impairment upper limit determined for the wavelength path.

More than one kind of impairment may be considered here. For example, two kinds of impairments, one due to PMD and the other due to crosstalk, may be considered. Of the constraint equations (3-41), (3-42), . . . , and (3-4R), the k-th constraint equation (3-4k) defines the constraint for the k-th kind of impairment out of the R kinds of impairments to be considered.

The meanings of the symbols used in equation (3) will be described below. In equation (3), the same symbols are used for the same terms as the terms appearing in equations (1) and (2). The description of the same symbols as those in equations (1) and (2) will not be repeated here.

Pth k (d j ) is the upper limit value of the k-th kind of impairment that the parameter determining unit 123 determined for the wavelength path d j . Pth k (d j ) is a value uniquely determined according to the kind of signal of the wavelength path d j defined by the wavelength path information.

p k (d j , s 1 , s 2 , . . . , s M ) represents the cumulative amount of the k-th kind of impairment occurring on the wavelength path d j depending on the optical transmission equipment configuration selected for each unit design section specified by a binary variable vector (s 1 , s 2 , . . . , s M ), and is given by the following equation (4).

pf kj (t i ) represents the amount of the k-th kind of impairment occurring on the wavelength path of the same kind of signal as that of the wavelength path d j when transmitting the signal along the unit design section g h in the same direction as the reference direction, when t i is selected as the optical transmission equipment configuration for the unit design section g h whose optical transmission equipment configuration candidate is t i .

pr kj (t i ) represents the amount of the k-th kind of impairment occurring on the wavelength path of the same kind of signal as that of the wavelength path d j when transmitting the signal along the unit design section g h in the direction opposite to the reference direction, when t i is selected as the optical transmission equipment configuration for the unit design section g h whose optical transmission equipment configuration candidate is t i .

The values of pf kj (t i ) and pr kj (t i ) are each a value that can be linearly added for each unit design section, and are determined according to the kind of signal of the wavelength path d j defined by the wavelength path information, the amount of impairment occurring between adjacent stations, defined by the span information for the kind of signal of the wavelength path d j , and the amount of impairment occurring in the optical signal of the same kind as that of the wavelength path d j passing through the optical transmission equipment constituting the optical transmission equipment configuration t i and defined by the optical transmission equipment information. For example, in the case of polarization mode dispersion PMD, the square of the total PMD [ps] occurring on the path is the parameter that can be linearly added.

Nth′(d j ) represents the noise amount upper limit value for the wavelength path d j . The parameter determining unit 123 determines the noise amount upper limit value Nth′(d j ) by one of the following three methods.

(First Example Method for Determining the Noise Amount Upper Limit Value Nth′(d j ))

In this method, the parameter determining unit 123 determines the noise amount upper limit value Nth′(d j ) based on the upper limit value Pth k (d j ) for each kind of impairment and the OSNR tolerance determined according to the kind of signal of each wavelength path d j .

The parameter determining unit 123 determines the OSNR lower limit value given by the following equation (5) obtained by calculating the OSNR degrading component from the impairment upper limit value Pth k (d j ) and by adding the degrading component to the OSNR tolerance, and determines the noise amount corresponding to this OSNR lower limit value as the noise amount upper limit value Nth′(d j ). In equation (5), f kj (Pth k (d j )) is a function that calculates the OSNR degrading component due to the k-th kind of impairment from the upper limit value Pth k (d j ) of the k-th kind of impairment for the wavelength path d j .

(Second Example Method for Determining the Noise Amount Upper Limit Value Nth′(d j ))

In this method, the parameter determining unit 123 determines the noise amount upper limit value Nth′(d j ) based on the OSNR tolerance, the upper limit value Pth k (d j ) for each kind of impairment, and the maximum value Pmax k (d j ) that the cumulative value of the impairment of each kind can take on each wavelength path d j .

The parameter determining unit 123 determines the OSNR lower limit value given by the following equation (6) obtained by calculating the OSNR degrading component from the upper limit value Pth k (d j ) or the maximum value Pmax k (d j ), whichever is smaller, and by adding the degrading component to the OSNR tolerance, and determines the noise amount corresponding to this OSNR lower limit value as the noise amount upper limit value Nth′(d j ).

(Third Example Method for Determining the Noise Amount Upper Limit Value Nth′(d j ))

In this method, the parameter determining unit 123 determines the noise amount upper limit value Nth′(d j ) based on the OSNR tolerance, the minimum required number REGmin(d j ) of OEO regenerators estimated for each wavelength path d j , the upper limit value Pth k (d j ) for each kind of impairment, and the maximum value Pmax k (d j ) that the cumulative value of the impairment of each kind can take on each wavelength path d j .

Of the largest integer values each smaller than the quotient of the minimum value Pmin k (d j ) that the cumulative value of the impairment can take on each wavelength path d j divided by the upper limit value Pth k (d j ) of the impairment

the parameter determining unit 123 takes the largest value among the values calculated for the R kinds of impairments

and determines it as the minimum required number REGmin(d j ) of OEO regenerators estimated for each wavelength path d j .

The parameter determining unit 123 adds 1 to the minimum required number REGmin(d j ) of OEO regenerators, and determines the sum (REGmin(d j )+1) as the number of sections into which the wavelength path d j is divided by the minimum required number of OEO regenerators.

As illustrated by the following equation (7), the parameter determining unit 123 determines the OSNR lower limit value by adding to the OSNR tolerance the OSNR degrading component calculated from the quotient of the maximum value Pmax k (d j ) that the cumulative value of the impairment can take on each wavelength path d j divided by the number of sections (REGmin(d j )+1) or from the upper limit value Pth k (d j ) of the impairment, whichever is smaller. The parameter determining unit 123 determines the noise amount corresponding to this OSNR lower limit value as the noise amount upper limit value Nth′(d j ).

According to the above method, since the maximum value of the impairment is estimated for each section when the path is divided into the minimum number of sections by the OEO regenerators, the noise amount upper limit value can be estimated more properly.

For example, suppose that, as the impairments, two kinds of impairments are considered, one being the impairment PMD due to polarization mode dispersion and the other being impairment XT due to crosstalk. For simplicity, it is assumed that the amount of each impairment [dB] can be linearly added and that f kj (Pth k (d j ))=Pth k (d j ).

It is also assumed that the upper limit value of PMD on a given wavelength path d j is 3 [dB] and that the maximum value of the cumulative value is 1 [dB] while the minimum value of the cumulative value is 0 [dB]. Similarly, it is assumed that the upper limit value of XT on that given wavelength path d j is 2 [dB] and that the maximum value of the cumulative value is 5 [dB] while the minimum value of the cumulative value is 4.5 [dB].

It is further assumed that the OSNR tolerance of the wavelength path d j is 16 [dB].

According to the first example method for determining the noise amount upper limit value Nth′(d j ), the OSNR lower limit value is calculated as 16+3+2=21 [dB], and the noise amount corresponding to the OSNR lower limit value of 21 [dB] is determined as the noise amount upper limit value Nth′(d j ).

According to the second example method for determining the noise amount upper limit value Nth′(d j ), the OSNR lower limit value is calculated as 16+1+2=19 [dB], and the noise amount corresponding to the OSNR lower limit value of 19 [dB] is determined as the noise amount upper limit value Nth′(d j ).

According to the third example method for determining the noise amount upper limit value Nth′(d j ), from the minimum value 4.5 [dB] and upper limit value 2 [dB] of XT that has the larger minimum value, the minimum required number REGmin(d j ) of OEO regenerators is calculated as int(4.5/2)=2. Accordingly, the wavelength path d j is divided into at least three sections by the OEO regenerators.

Since the values 1/3 and 5/3 obtained by dividing the maximum values of PMD and XT by 3 are both smaller than their upper limit values, the OSNR lower limit value is calculated as 16+1/3+5/3=18 [dB], and the noise amount corresponding to the OSNR lower limit value of 18 [dB] is determined as the noise amount upper limit value Nth′(d j ).

Also in the first embodiment, the constraint equation (1-3) may be defined by replacing the noise amount upper limit value Nth(d j ) in the constraint equation (1-3) by the noise amount upper limit value Nth′(d j ) used in the constraint equation (3-3) of the second embodiment.

Similarly, in the second embodiment also, the constraint equation (3-3) may be defined by replacing the noise amount upper limit value Nth′(d j ) in the constraint equation (3-3) by the noise amount upper limit value Nth(d j ) used in the constraint equation (1-3) of the first embodiment.

The equipment configuration determining unit 124 depicted in FIG. 7 solves the integer programming problem given by equation (1) or (3), by following the procedures described below.

(Procedure 1)

By solving the linear programming relaxation with the binary variable s i (i=1 to M) and integer variable x j (j=1 to N) in equation (1) or (3) as real variables, the dual price vector associated with the constraints (1-2) and (1-3) or the constraints (3-2), (3-3), and (3-41) to (3-4R) is obtained.

The dual price vector associated with the constraints (1-2) and (3-2) is denoted as π g =(π g1 , π g2 , . . . , π gP ).

The dual price vector associated with the constraints (1-3) and (3-3) is denoted as πn=(πn 1 , πn 2 , . . . , πn N )

The dual price vector associated with the constraint (3-4k) is denoted as πP k =(πp k1 , πp k2 , . . . , πp kN ).

(Procedure 2)

In accordance with the reduced-cost calculation equation determined based on the value of the dual price vector, the equipment configuration determining unit 124 searches for a new optical transmission equipment configuration candidate t′ in which the value of the reduced cost is negative for each unit design section.

When solving the linear programming relaxation of the integer programming problem given by equation (1), the reduced cost RC(t′) for the optical transmission equipment configuration candidate t′ is given by the following equation (8).

Symbol π g′ is the component in the dual price vector π g that corresponds to the unit design section g′ whose optical transmission equipment configuration candidate is the optical transmission equipment configuration t′. On the other hand, when solving the linear programming relaxation of the integer programming problem given by equation (3), the reduced cost RC(t′) for the optical transmission equipment configuration candidate t′ is given by the following equation (9).

When any new optical transmission equipment configuration candidate t′ in which the value of the reduced cost is negative is no longer found, the equipment configuration determining unit 124 determines the optical transmission equipment configuration of the optical network 200 by solving the integer programming problem given by equation (1) or (3) without linear programming relaxing the integer programming problem for the so-far found optical transmission equipment configuration candidates, and by selecting one optical transmission equipment configuration for each unit design section from among the so-far found optical transmission equipment configuration candidates.

The equipment configuration determining unit 124 depicted in FIG. 7 includes an initial candidate generating unit 125 , a linear programming relaxation solving unit 127 , an additional candidate searching unit 128 , and an integer programming problem solving unit 129 .

The combination of the initial candidate generating unit 125 , the linear programming relaxation solving unit 127 , and the additional candidate searching unit 128 is one examples of the combination candidate determining unit described in the appended claims.

The integer programming problem solving unit 129 is one examples of the equipment placement unit described in the appended claims.

The linear programming relaxation solving unit 127 reads the equipment configuration candidate data 114 stored in the storage unit 126 , and determines the dual price vector by solving the linear programming relaxation of the integer programming problem given by equation (1) or (3) for the optical transmission equipment configuration candidate indicated by the equipment configuration candidate data 114 .

Prior to the processing by the linear programming relaxation solving unit 127 , the initial candidate generating unit 125 generates, for each unit design section, at least one optical transmission equipment configuration candidate, and stores the candidate in the storage unit 126 .

In accordance with the reduced-cost calculation equation determined based on the value of the dual price vector determined by the linear programming relaxation solving unit 127 , the additional candidate searching unit 128 searches for a new optical transmission equipment configuration candidate t′ in which the value of the reduced cost is negative for each unit design section. The additional candidate searching unit 128 adds the newly found candidate t′ to the equipment configuration candidate data 114 .

The integer programming problem solving unit 129 reads the equipment configuration candidate data 114 stored in the storage unit 126 and containing the candidates determined by the initial candidate generating unit 125 and the additional candidate searching unit 128 , and determines the optical transmission equipment configuration of the optical network 200 by solving the integer programming problem given by equation (1) or (3) without relaxing the integer programming problem for the optical transmission equipment configuration candidates indicated by the equipment configuration candidate data 114 .

Next, the configuration of each unit depicted in FIG. 7 and the processing performed by each unit will be described. FIG. 8 is a block diagram of the parameter determining unit 123 depicted in FIG. 7 .

The parameter determining unit 123 includes a impairment upper limit value determining unit 130 , an intra-unit-design-section impairment upper limit value determining unit 131 , a cumulative impairment determining unit 132 , a noise amount upper limit value determining unit 133 , and an intra-unit-design-section noise amount upper limit value determining unit 134 .

The impairment upper limit value determining unit 130 determines the impairment upper limit value Pth k (d j ) for each wavelength path d j and for each kind k of impairment in accordance with the kind of signal of the wavelength path d j defined by the wavelength path information.

The impairment upper limit value Pth k (d j ) output from the impairment upper limit value determining unit 130 is input to the intra-unit-design-section impairment upper limit value determining unit 131 . Among the impairment upper limit values Pth k (d j ) (j=1 to N) determined for the wavelength paths d j passing through the respective unit design sections, the intra-unit-design-section impairment upper limit value determining unit 131 selects the smallest value as the intra-unit-design-section impairment upper limit value for each unit design section and for each of the R kinds of impairments.

The intra-unit-design-section impairment upper limit value determining unit 131 determines the intra-unit-design-section impairment upper limit value for each path transmission direction of the unit section. That is, for the unit section leading from station A to station B, the intra-unit-design-section impairment upper limit value determining unit 131 determines the intra-unit-design-section impairment upper limit value for the transmission path directed from the station A to the station B and the intra-unit-design-section impairment upper limit value for the transmission path directed from the station B to the station A.

The intra-unit-design-section impairment upper limit values determined for the respective transmission directions of the unit design section g h for the k-th kind of impairment are denoted as Pth 1 k ( g h ) and Pth 2 k ( g h ) (k=1 to R, h=1 to P), respectively.

The cumulative impairment determining unit 132 determines the maximum value Pmax k (d j ) that the cumulative value of the impairment can take on each wavelength path d j , or the maximum value Pmax k (d j ) and minimum value Pmin k (d j ) that the cumulative value of the impairment can take on each wavelength path d j . The processing performed by the cumulative impairment determining unit 132 will be described later.

The noise amount upper limit value determining unit 133 determines the noise amount upper limit value Nth(d j ) or Nth′.

When determining the noise amount upper limit value Nth(d j ), the noise amount upper limit value determining unit 133 determines as the noise amount upper limit value Nth(d j ) the noise amount corresponding to the OSNR tolerance which is determined according to the kind of signal of the wavelength path d j defined by the wavelength path information.

When determining the noise amount upper limit value Nth′(d j ) in accordance with the earlier given equation (5), the noise amount upper limit value determining unit 133 determines the noise amount upper limit value Nth′(d j ) based on the OSNR tolerance which is determined according to the kind of signal of the wavelength path d j defined by the wavelength path information and on the impairment upper limit value Pth k (d j ) determined by the impairment upper limit value determining unit 130 .

When determining the noise amount upper limit value Nth′(d j ) in accordance with the earlier given equation (6), the noise amount upper limit value determining unit 133 determines the noise amount upper limit value Nth′(d j ) based on the OSNR tolerance which is determined according to the kind of signal of the wavelength path d j defined by the wavelength path information and on the impairment upper limit value Pth k (d j ) determined by the impairment upper limit value determining unit 130 and the maximum value Pmax k (d j ) of the cumulative impairment value determined by the cumulative impairment determining unit 132 .

When determining the noise amount upper limit value Nth′(d j ) in accordance with the earlier given equation (7), the noise amount upper limit value determining unit 133 determines the noise amount upper limit value Nth′(d j ) based on the OSNR tolerance which is determined according to the kind of signal of the wavelength path d j defined by the wavelength path information and on the impairment upper limit value Pth k (d j ) determined by the impairment upper limit value determining unit 130 and the maximum value Pmax k (d j ) and minimum value Pmin k (d j ) of the cumulative impairment value determined by the cumulative impairment determining unit 132 .

The noise amount upper limit value Nth(d j ) or Nth′(d j ) output from the noise amount upper limit value determining unit 133 is input to the intra-unit-design-section noise amount upper limit value determining unit 134 . Among the noise amount upper limit values determined for the wavelength paths d j passing through the respective unit design sections, the intra-unit-design-section noise amount upper limit value determining unit 134 selects the smallest value as the intra-unit-design-section noise amount upper limit value for each unit design section.

The intra-unit-design-section noise amount upper limit value determining unit 134 determines the intra-unit-design-section noise amount upper limit value for each path transmission direction of the unit section. That is, for the unit section leading from station A to station B, the intra-unit-design-section noise amount upper limit value determining unit 134 determines the intra-unit-design-section noise amount upper limit value for the transmission path directed from the station A to the station B and the intra-unit-design-section noise amount upper limit value for the transmission path directed from the station B to the station A.

The intra-unit-design-section noise upper limit values determined for the respective transmission directions of the unit design section g h are denoted as Nth 1 ( g h ) and Nth 2 ( g h ) (h=1 to P), respectively.

The cumulative impairment determining unit 132 includes an intra-path graph generating unit 140 , an intra-path node searching unit 141 , and a cumulative value calculation unit 142 . Based on the information acquired by the information acquiring unit 120 , the intra-path graph generating unit 140 generates loopless directed graph information including the nodes corresponding to the candidates for the various kinds of optical transmission equipment to be placed at the respective stations through which the wavelength path d j passes and the links, each assigned an impairment value, for interconnecting the respective nodes.

The intra-path graph generating unit 140 includes a first node candidate generating unit 143 , a first link generating unit 144 , and an impairment determining unit 145 . Based on the optical transmission equipment information, the first node candidate generating unit 143 generates, for each station, one or more nodes corresponding to the various kinds of optical transmission equipment that can be placed.

For example, suppose that stations 1 and 2 are contained in the section through which the wavelength path d j passes. If optical transmission equipment A or B, whichever is appropriate, can be placed at the station 1 , the first node candidate generating unit 143 generates a node 1 A, which corresponds to the case where the optical transmission equipment A is placed at the station 1 , and a node 1 B, which corresponds to the case where the optical transmission equipment B is placed at the station 1 .

On the other hand, if only the optical transmission equipment A can be placed at the station 2 , the first node candidate generating unit 143 generates a node 2 A, which corresponds to the case where the optical transmission equipment A is placed at the station 2 . The first node candidate generating unit 143 supplies the thus generated nodes to the first link generating unit 144 . In this way, the first node candidate generating unit 143 generates one or more nodes for each station contained in the section through which the wavelength path d j passes.

For each node supplied from the first node candidate generating unit 143 , the first link generating unit 144 generates an input link leading from each node corresponding to a station upstream of the station corresponding to the current node. For example, when there are two nodes 1 A and 1 B corresponding to the station 1 and one node 2 A corresponding to station 2 downstream of the station 1 , the first link generating unit 144 generates an input link leading from the node 1 A to the node 2 A and an input link leading from the node 1 B to the node 2 A.

The first link generating unit 144 supplies the thus generated input links to the impairment determining unit 145 together with the nodes generated by the first node candidate generating unit 143 .

Then, based on the kind of signal of the wavelength path d j defined by the wavelength path information, the amount of impairment occurring between adjacent stations, defined by the span information for the kind of signal of the wavelength path d j , and the amount of impairment occurring in the optical signal of the same kind as that of the wavelength path d j passing through the various kinds of optical transmission equipment defined by the optical transmission equipment information, the impairment determining unit 145 determines for each kind of impairment the amount of impairment that occurs on the wavelength path d j when each input link generated by the first link generating unit 144 is selected.

For example, for the input link leading from the node 1 A to the node 2 A, the impairment determining unit 145 calculates the amount of impairment that occurs on the wavelength path d j when this input link is selected.

Further, for the input link leading from the node 1 B to the node 2 A, the impairment determining unit 145 calculates the amount of impairment that occurs on the wavelength path d j when this input link is selected.

The impairment determining unit 145 supplies the thus calculated impairment amounts to the intra-path node searching unit 141 together with the nodes generated by the first node candidate generating unit 143 and the input links generated by the first link generating unit 144 .

When the cumulative impairment determining unit 132 determines the maximum value Pmax k (d j ) of the cumulative value of the impairment, the intra-path node searching unit 141 searches through the graph information supplied from the intra-path graph generating unit 140 for the path corresponding to the placement that maximizes the cumulative value of the impairment for each kind of impairment.

On the other hand, when the cumulative impairment determining unit 132 determines the minimum value Pmin k (d j ) of the cumulative value of the impairment, the intra-path node searching unit 141 searches through the graph information supplied from the intra-path graph generating unit 140 for the path corresponding to the placement that minimizes the cumulative value of the impairment for each kind of impairment.

The intra-path node searching unit 141 includes a first link selecting unit 146 and a first node determining unit 147 . The first link selecting unit 146 selects an input link for each node supplied from the intra-path graph generating unit 140 . That is, for each node generated by the first node candidate generating unit 143 , the first link selecting unit 146 selects one of the input links that the first link generating unit 144 generated for that node.

When the cumulative impairment determining unit 132 determines the maximum value Pmax k (d j ) of the cumulative value of the impairment, the first link selecting unit 146 selects an input link such that, when the input link is selected, the impairment that accumulates up to the attention node becomes maximum.

On the other hand, when the cumulative impairment determining unit 132 determines the minimum value Pmin k (d j ) of the cumulative value of the impairment, the first link selecting unit 146 selects an input link such that, when the input link is selected, the impairment that accumulates up to the attention node becomes minimum.

For example, suppose that there are two input links to the attention node 2 A, one being the input link ( 1 A, 2 A) leading from the node 1 A and the other the input link ( 1 B, 2 A) leading from the node 1 B, and that the impairments accumulated up to the nodes 1 A and 1 B, respectively, are PNacc( 1 A) and PNacc( 1 B), while the impairments that occur when the input links ( 1 A, 2 A) and ( 1 B, 2 A) are respectively selected are PN( 1 A, 2 A) and PN( 1 B, 2 A), respectively.

In this case, the first link selecting unit 146 compares the impairment that accumulates up to the node 2 A when the input link ( 1 A, 2 A) is selected for the node 2 A, i.e., PNacc( 1 A)+PN( 1 A, 2 A), with the impairment that accumulates up to the node 2 A when the input link ( 1 B, 2 A) is selected, i.e., PNacc( 1 B)+PN( 1 B, 2 A).

When the cumulative impairment determining unit 132 determines the maximum value Pmax k (d j ), the first link selecting unit 146 selects the input link ( 1 A, 2 A) if the former is larger and selects the input link ( 1 B, 2 A) if the latter is larger.

On the other hand, when the cumulative impairment determining unit 132 determines the minimum value Pmin k (d j ), the first link selecting unit 146 selects the input link ( 1 A, 2 A) if the former is smaller and selects the input link ( 1 B, 2 A) if the latter is smaller.

The first link selecting unit 146 supplies the input links selected for the respective nodes to the first node determining unit 147 together with the impairment amounts calculated by the impairment determining unit 145 .

Based on the starting point nodes of the input links supplied from the first link selecting unit 146 , the first node determining unit 147 determines the placement of the various kinds of optical transmission equipment for the respective stations contained in the section through which the wavelength path d j passes. For example, when the starting point nodes of the input links supplied from the first link selecting unit 146 are the node 1 A, node 2 B, node 3 A, etc., the first node determining unit 147 takes the placement of the optical transmission equipment corresponding to the node 1 A, node 2 B, node 3 A, etc., to determine the placement of the various kinds of optical transmission equipment for the respective stations.

The first node determining unit 147 supplies the thus determined nodes to the cumulative value calculation unit 142 together with the impairment amounts calculated by the impairment determining unit 145 .

The cumulative value calculation unit 142 determines for each kind of impairment the impairment that accumulates along the path passing through each node determined by the first node determining unit 147 , and supplies it to the noise amount upper limit value determining unit 133 .

FIG. 9 is a block diagram of the initial candidate generating unit 125 depicted in FIG. 7 . The initial candidate generating unit 125 includes a first intra-unit-design-section graph generating unit 150 and a first intra-unit-design-section node searching unit 151 .

Based on the information acquired by the information acquiring unit 120 and the information concerning each unit design section g h that the section dividing unit 121 generated by dividing the optical network 200 , the first intra-unit-design-section graph generating unit 150 generates loopless directed graph information including the nodes corresponding to the candidates for the various kinds of optical transmission equipment to be placed along each unit design section g h and the links, each assigned a impairment value, for interconnecting the respective nodes.

The first intra-unit-design-section graph generating unit 150 includes a second node candidate generating unit 152 , a second link generating unit 153 , a cost determining unit 154 , and a transmission degradation amount determining unit 155 . Based on the optical transmission equipment information, the second node candidate generating unit 152 generates, for each station in the unit design section g h , one or more nodes corresponding to the various kinds of optical transmission equipment that can be placed.

For example, suppose that stations 1 and 2 are contained in the unit design section g h . If optical transmission equipment A or B, whichever is appropriate, can be placed at the station 1 , the second node candidate generating unit 152 generates a node 1 A, which corresponds to the case where the optical transmission equipment A is placed at the station 1 , and a node 1 B, which corresponds to the case where the optical transmission equipment B is placed at the station 1 .

On the other hand, if only the optical transmission equipment A can be placed at the station 2 , the second node candidate generating unit 152 generates a node 2 A, which corresponds to the case where the optical transmission equipment A is placed at the station 2 . The second node candidate generating unit 152 supplies the thus generated nodes to the second link generating unit 153 .

For each node supplied from the second node candidate generating unit 152 , the second link generating unit 153 generates an input link leading from each node corresponding to a station upstream of the station corresponding to the current node. For example, when there are two nodes 1 A and 1 B corresponding to the station 1 and one node 2 A corresponding to the station 2 downstream of the station 1 , the second link generating unit 153 generates an input link leading from the node 1 A to the node 2 A and an input link leading from the node 1 B to the node 2 A.

The second link generating unit 153 supplies the thus generated input links to the cost determining unit 154 and the transmission degradation amount determining unit 155 together with the nodes generated by the second node candidate generating unit 152 .

Then, based on the cost of the various kinds of optical transmission equipment defined by the optical transmission equipment information, the cost determining unit 154 determines for each input link generated by the second link generating unit 153 the cost that occurs when the input link is selected. The cost calculated here may, for example, be the cost of the optical transmission equipment to be placed at each station.

For example, for the input link leading from the node 1 A to the node 2 A, the cost determining unit 154 calculates the cost that occurs when this input link is selected. Further, for the input link leading from the node 1 B to the node 2 A, the cost determining unit 154 calculates the cost that occurs when this input link is selected.

Based on the amount of noise and the amount of impairment occurring between adjacent stations, defined by the span information, and the amount of noise and the amount of impairment occurring in the optical signal passing through the various kinds of optical transmission equipment defined by the optical transmission equipment information, the transmission degradation amount determining unit 155 determines for each input link generated by the second link generating unit 153 the amount of transmission degradation, i.e., the amount of noise and the amount of impairment for each kind of impairment, that occurs when the input link is selected.

For example, for the input link leading from the node 1 A to the node 2 A, the transmission degradation amount determining unit 155 calculates the amount of noise and the amount of impairment that occur when this input link is selected. Further, for the input link leading from the node 1 B to the node 2 A, the transmission degradation amount determining unit 155 calculates the amount of noise and the amount of impairment that occur when this input link is selected.

The transmission degradation amount determining unit 155 determines the amount of noise and the amount of impairment for the forward direction and backward direction of the input link. That is, for the input link leading from the station A to the station B, the transmission degradation amount determining unit 155 determines the amount of noise and the amount of impairment that occur on the path directed from the station A to the station B and the amount of noise and the amount of impairment that occur on the path directed from the station B to the station A.

The transmission degradation amount determining unit 155 supplies the thus calculated transmission degradation amounts to the first intra-unit-design-section node searching unit 151 together with the nodes generated by the second node candidate generating unit 152 and the input links generated by the second link generating unit 153 .

The cost determining unit 154 supplies the calculated cost to the first intra-unit-design-section node searching unit 151 .

The first intra-unit-design-section node searching unit 151 searches through the graph information supplied from the first intra-unit-design-section graph generating unit 150 for the path corresponding to the placement that minimizes the cost and in which the transmission degradation amounts that occur along the path between adjacent stations each provided with equipment capable of accommodating an OEO regenerator are held within their respective upper limits. The first intra-unit-design-section node searching unit 151 includes a second link selecting unit 156 and a second node determining unit 157 . The second link selecting unit 156 selects an input link for each node supplied from the first intra-unit-design-section graph generating unit 150 .

That is, for each node generated by the second node candidate generating unit 152 , the second link selecting unit 156 selects one of the input links that the second link generating unit 153 generated for that node. At this time, the second link selecting unit 156 selects an input link such that, when the input link is selected, the cost that accumulates up to the attention node becomes minimum.

For example, suppose that there are two input links to the attention node 2 A, one being the input link ( 1 A, 2 A) leading from the node 1 A and the other the input link ( 1 B, 2 A) leading from the node 1 B, and that the costs accumulated up to the nodes 1 A and 1 B, respectively, are COSTacc( 1 A) and COSTacc( 1 B), while the costs that occur when the input links ( 1 A, 2 A) and ( 1 B, 2 A) are respectively selected are COST( 1 A, 2 A) and COST( 1 B, 2 A), respectively.

In this case, the second link selecting unit 156 compares the cost that accumulates up to the node 2 A when the input link ( 1 A, 2 A) is selected for the node 2 A, i.e., COSTacc( 1 A)+COST( 1 A, 2 A), with the cost that accumulates up to the node 2 A when the input link ( 1 B, 2 A) is selected, i.e., COSTacc( 1 B)+COST( 1 B, 2 A); if the former is smaller, the input link ( 1 A, 2 A) is selected, but if the latter is smaller, the input link ( 1 B, 2 A) is selected.

From among the input links generated for the attention node by the first intra-unit-design-section graph generating unit 150 , the second link selecting unit 156 selects any input link such that, when the input link is selected, the transmission degradation amount that accumulates up to each node corresponding to a station downstream of the attention node and corresponding to the optical transmission equipment capable of accommodating an OEO regenerator (each such node will hereinafter called a “downstream OEO regenerative node”) is held within the threshold value, and then selects from among such input links the input link that minimizes the cost.

For example, suppose that there is a station 3 downstream of the station 2 corresponding to the node 2 A and, of the nodes 3 A and 3 B corresponding to the station 3 , the node 3 A is the optical transmission equipment capable of accommodating an OEO regenerator; in this case, the second link selecting unit 156 selects the node 3 A as the downstream OEO regenerative node. Then, the second link selecting unit 156 selects the input link that minimizes the cost from among the input links that, when selected, the transmission degradation amount that accumulates up to the node 3 A is held within the threshold value.

On the other hand, if there are a plurality of downstream OEO regenerative nodes downstream of the node 2 A, first the node where the transmission degradation amount from the node 2 A is the smallest is selected from among the plurality of downstream OEO regenerative nodes, and then the input link that minimizes the cost is selected from among the input links that, when selected, the transmission degradation amount that accumulates up to that selected node is held within the threshold value.

The second link selecting unit 156 takes, as the transmission degradation amount that accumulates up to the OEO regenerative node downstream of the attention node, the sum of the transmission degradation amount accumulated up to the starting point node of the input link, the transmission degradation amount that occurs when that input link is selected, and the minimum value of the transmission degradation amount that occurs along the path from the attention node to the downstream OEO regenerative node.

To describe the processing of the transmission degradation amount by taking as an example the noise amount occurring in the forward direction, the transmission degradation amounts accumulated up to the nodes 1 A and 1 B are denoted as NOISEacc( 1 A) and NOISEacc( 1 B), respectively, the noise amounts determined for the input links ( 1 A, 2 A) and ( 1 B, 2 A) by the transmission degradation amount determining unit 155 are denoted as NOISE( 1 A, 2 A) and NOISE( 1 B, 2 A), respectively, the minimum value of the transmission degradation amount that occurs along the path from the node 2 A to the downstream OEO regenerative node (node 3 A) is denoted as NOISEmin, and the intra-unit-design-section noise amount upper limit value in the forward direction determined by the intra-unit-design-section noise amount upper limit value determining unit 134 is taken as the threshold value NOISEth of the noise amount.

In this case, the second link selecting unit 156 calculates NOISEacc( 1 A)+NOISE( 1 A, 2 A)+NOISEmin for the input link ( 1 A, 2 A) to the node 2 A and NOISEacc( 1 B)+NOISE( 1 B, 2 A)+NOISEmin for the input link ( 1 B, 2 A), and compares the calculation results with NOISEth. The second link selecting unit 156 eliminates any input link whose calculation result is larger than NOISEth, and selects from among the remaining input links the input link that minimizes the cost.

If the attention node is a node corresponding to the optical transmission equipment capable of accommodating an OEO regenerator, the second link selecting unit 156 sets the minimum value NOISEmin of the transmission degradation amount that occurs along the path from the attention node to the downstream OEO regenerative node, to zero. Further, in this case, if the attention node is a node corresponding to the optical transmission equipment capable of accommodating an OEO regenerator, then after selecting the input link the second link selecting unit 156 resets the transmission degradation amount accumulated up to the attention node to zero.

For example, if the node 2 A is a node corresponding to the optical transmission equipment capable of accommodating an OEO regenerator, the second link selecting unit 156 calculates NOISEacc( 1 A)+NOISE( 1 A, 2 A)+0 and NOISEacc( 1 B)+NOISE( 1 B, 2 A)+0, respectively, for the node 2 A. Further, after selecting the input link, the second link selecting unit 156 resets the transmission degradation amount NOISEacc( 2 A) accumulated up to the node 2 A to zero. The transmission degradation amount accumulated up to the node 2 A is used when selecting the input link to each node corresponding to the station 3 that immediately follows the station 2 .

When the transmission degradation amount to be considered is the amount of noise occurring in the backward direction, the second link selecting unit 156 similarly determines the accumulated noise amounts and eliminates any input link whose calculation result is larger than the threshold value.

Further, when the transmission degradation amount to be considered is the amount of impairment occurring in each designated direction, the second link selecting unit 156 similarly determines the accumulated impairment amounts and eliminates any input link whose calculation result is larger than the threshold value. When taking any given kind of impairment as the transmission degradation amount, the second link selecting unit 156 uses as the threshold value of the impairment the impairment upper limit value in each designated direction determined by the intra-unit-design-section impairment upper limit value determining unit 131 .

The second node determining unit 157 determines the placement of the various kinds of optical transmission equipment for the respective stations contained in the linear section by selecting one optical transmission equipment configuration candidate, based on the starting point nodes of the respective input links supplied from the second link selecting unit 156 . For example, when the starting point nodes of the input links supplied from the second link selecting unit 156 are the node 1 A, node 2 B, node 3 A, etc., the second node determining unit 157 takes the placement of the optical transmission equipment corresponding to the node 1 A, node 2 B, node 3 A, etc., to determine the placement of the various kinds of optical transmission equipment for the respective stations. The second node determining unit 157 stores the thus determined optical transmission equipment candidate in the storage unit 126 .

In the unit design section for which the optical transmission equipment has been selected by the initial candidate generating unit 125 having the above configuration, the amount of noise that occurs along the path between adjacent stations each provided with the equipment capable of accommodating an OEO regenerator becomes smaller than the minimum value of the noise amount upper limit value determined for each wavelength path that passes through that unit design section.

Further, in the unit design section for which the optical transmission equipment has been selected by the initial candidate generating unit 125 having the above configuration, the impairment that occurs along the path between adjacent stations each provided with the equipment capable of accommodating an OEO regenerator becomes smaller than the minimum value of the impairment upper limit value determined for each wavelength path that passes through that unit design section.

FIG. 10 is a block diagram of the additional candidate searching unit 128 depicted in FIG. 7 . In accordance with the reduced-cost calculation equation determined based on the value of the dual price vector determined by the linear programming relaxation solving unit 127 depicted in FIG. 7 , the additional candidate searching unit 128 searches for a new optical transmission equipment configuration candidate t′ in which the value of the reduced cost is negative for each unit design section.

The additional candidate searching unit 128 includes a second intra-unit-design-section graph generating unit 160 , a second intra-unit-design-section node searching unit 161 , a reduced-cost determining unit 168 , and an addition permit/deny determining unit 169 .

The second intra-unit-design-section graph generating unit 160 and the second intra-unit-design-section node searching unit 161 are similar in configuration to the first intra-unit-design-section graph generating unit 150 and the first intra-unit-design-section node searching unit 151 , respectively, in the initial candidate generating unit 125 depicted in FIG. 9 .

The second intra-unit-design-section graph generating unit 160 includes a third node candidate generating unit 162 , a third link generating unit 163 , and a transmission degradation amount determining unit 165 , which are similar in function to the second node candidate generating unit 152 , second link generating unit 153 , and transmission degradation amount determining unit 155 included in the first intra-unit-design-section graph generating unit 150 .

The second intra-unit-design-section node searching unit 161 includes a third link selecting unit 166 and a third node determining unit 167 , which are similar in function to the second link selecting unit 156 and second node determining unit 157 included in the first intra-unit-design-section node searching unit 151 .

However, the second intra-unit-design-section graph generating unit 160 differs from the first intra-unit-design-section graph generating unit 150 by the inclusion of a reduced-cost change determining unit 164 in place of the cost determining unit 154 .

While the cost determining unit 154 determines the cost that occurs when each particular input link is selected, the reduced-cost change determining unit 164 determines the amount of change, ΔRC, of the reduced cost that occurs in the unit design section when each particular input link is selected.

Further, while the second link selecting unit 156 in the first intra-unit-design-section node searching unit 151 selects an input link such that, when the input link is selected, the cost that accumulates up to the attention node becomes minimum, the third link selecting unit 166 selects an input link such that, when the input link is selected, the amount of change, ΔRC, of the reduced cost that accumulates up to the attention node becomes minimum.

Just as the noise amount and the impairment value that occur along the path between stations each provided with the equipment capable of accommodating an OEO regenerator, and connected by the input link selected by the second link selecting unit 156 , become smaller than their respective threshold values as described earlier, the noise amount and the impairment value that occur along the path between stations each provided with the equipment capable of accommodating an OEO regenerator, and connected by the input link selected by the third link selecting unit 166 , also become smaller than their respective threshold values.

When the equipment configuration determining unit 124 solves the integer programming problem given by equation (1), the reduced-cost change determining unit 164 determines the equipment cost Δc and noise amounts Δnf and Δnr that increase when each particular input link is selected, based on the optical transmission equipment information defining the cost of the various kinds of optical transmission equipment and the amount of noise occurring in the optical signal passing through the various kinds of optical transmission equipment and on the span information defining the amount of noise occurring along the path between adjacent stations.

Symbol Δnf represents the amount of change of the noise amount that occurs on the wavelength path propagating along the unit design section in the same direction as the reference direction when the input link is selected, and Δnr represents the amount of change of the noise amount that occurs on the wavelength path propagating along the unit design section in the direction opposite to the reference direction when the input link is selected.

In accordance with the following reduced-cost calculation equation (10) determined based on the value of the dual price vector determined by the linear programming relaxation solving unit 127 , the reduced-cost change determining unit 164 determines the amount of change, ΔRC, of the reduced cost that occurs in the unit design section when each particular input link is selected.

When the equipment configuration determining unit 124 solves the integer programming problem given by equation (3), the reduced-cost change determining unit 164 determines the equipment cost Δc, noise amounts Δnf and Δnr, and impairment amounts Δpf kj and Δpr kj that increase when each particular input link is selected, based on the optical transmission equipment information defining the cost of the various kinds of optical transmission equipment and the amount of noise and the amount of impairment occurring in the optical signal passing through the various kinds of optical transmission equipment and on the span information defining the amount of noise and the amount of impairment occurring along the path between adjacent stations.

Symbol Δpf kj represents the amount of change of the k-th kind of impairment that occurs on the wavelength path d j propagating along the unit design section in the same direction as the reference direction when the input link is selected, and Δpr kj represents the amount of change of the k-th kind of impairment that occurs on the wavelength path d j propagating along the unit design section in the direction opposite to the reference direction when the input link is selected.

In accordance with the following reduced-cost calculation equation (11) determined based on the value of the dual price vector determined by the linear programming relaxation solving unit 127 , the reduced-cost change determining unit 164 determines the amount of change, ΔRC, of the reduced cost that occurs in the unit design section when each particular input link is selected.

The optical transmission equipment configuration selected by the second intra-unit-design-section graph generating unit 160 and second intra-unit-design-section node searching unit 161 having the above configuration is one that produces the minimum reduced cost in the unit design section.

The reduced-cost determining unit 168 determines the reduced cost RC produced by the optical transmission equipment configuration selected by the second intra-unit-design-section graph generating unit 160 and second intra-unit-design-section node searching unit 161 . For example, the reduced-cost determining unit 168 determines the reduced cost RC by obtaining the component corresponding to the unit design section from the dual price vector π g determined by the linear programming relaxation solving unit 127 , and by subtracting this component from the cumulative value of the amount of change, ΔRC, of the reduced cost that accumulates along the unit design section in the selected optical transmission equipment configuration.

The addition permit/deny determining unit 169 determines whether the reduced cost RC determined by the reduced-cost determining unit 168 is smaller than 0 or not, and reports the result of the determination to the linear programming relaxation solving unit 127 as well as to the integer programming problem solving unit 129 . If the reduced cost RC is smaller than 0, the addition permit/deny determining unit 169 stores the determined optical transmission equipment configuration candidate in the storage unit 126 .

Based on the result of the determination from the addition permit/deny determining unit 169 , the linear programming relaxation solving unit 127 determines whether or not the additional candidate searching unit 128 can find any configuration in which the reduced cost RC is negative. The linear programming relaxation solving unit 127 reads the equipment configuration candidate data 114 as a new candidate is added to it by the additional candidate searching unit 128 until the additional candidate searching unit 128 can no longer find any configuration in which the reduced cost RC is negative, and thus solves the linear programming relaxation of the integer programming problem and updates the dual price vector.

Based on the result of the determination from the addition permit/deny determining unit 169 , the integer programming problem solving unit 129 determines whether the additional candidate searching unit 128 can find any configuration in which the reduced cost RC is negative. When the additional candidate searching unit 128 can no longer find any configuration in which the reduced cost RC is negative, the integer programming problem solving unit 129 then reads the equipment configuration candidate data 114 , and determines the optical transmission equipment configuration of the optical network 200 by solving the integer programming problem without relaxing the integer programming problem.

FIG. 11 is a general flowchart of the network design method according to an embodiment.

In step S 1 , the information acquiring unit 120 depicted in FIG. 7 acquires the WDM optical network information.

In step S 2 , the section dividing unit 121 divides the optical network 200 , defined by the network topology information contained in the WDM optical network information, into unit design sections each being a linear section.

In step S 3 , the parameter determining unit 123 depicted in FIG. 8 determines the noise amount upper limit value Nth or Nth′ and the impairment upper limit value Pth k (d j ).

Further, the parameter determining unit 123 determines the intra-unit-design-section noise upper limit values Nth 1 ( g h ) and Nth 2 ( g h ) and the intra-unit-design-section impairment upper limit values Pth 1 k ( g h ) and Pth 2 k ( g h ).

As earlier described, when the parameter determining unit 123 determines the noise amount upper limit value Nth′ by the second or third example method, the cumulative impairment determining unit 132 depicted in FIG. 8 determines the minimum value Pmin k (d j ) and/or the maximum value Pmax k (d j ) that the cumulative impairment value can take on each wavelength path d j . A description will be given below of how the cumulative impairment determining unit 132 determines the minimum value Pmin k (d j ) and maximum value Pmax k (d j ) of the cumulative impairment value.

FIG. 12 is a diagram (part 1 ) illustrating an example of the graph information generated by the intra-path graph generating unit 140 depicted in FIG. 8 . Stations 1 to 6 depicted in FIG. 12 correspond to the stations 1 to 6 located along the unit design sections 202 and 203 through which the wavelength path d passes in FIG. 1 . Nodes 1 A to 6 A and nodes 2 B, 3 B, and 5 B are the nodes generated by the first node candidate generating unit 143 . Of the various kinds of optical transmission equipment that can be placed at the stations 1 to 6 , an OADM (for example, the OADM 400 of FIG. 3 ) is used as the kind of optical transmission equipment capable of accommodating an OEO regenerator.

Further, of the various kinds of optical transmission equipment that can be placed at the stations 1 to 6 , an ILA (for example, the ILA 500 of FIG. 5 ) is used as the kind of optical transmission equipment not capable of accommodating an OEO regenerator. Only an OADM that can accommodate an OEO regenerator can be placed at the station 1 , which is the originating station, and the station 2 , which is the terminating station. On the other hand, any kind of optical transmission equipment, i.e., an OADM, an ILA, or a bypass (for example, the bypass 600 of FIG. 5 ), can be placed at the stations 2 , 3 , and 5 . An ILA cannot be placed at the station 4 .

For the stations 1 to 6 , the first node candidate generating 143 generates the nodes 1 A to 6 A each indicating an OADM that can be placed at each of these stations. For the stations 2 , 3 , and 5 , the first node candidate generating 143 further generates the nodes 2 B, 3 B, and 5 B each indicating an ILA that can be placed at each of these stations. In FIG. 12 , each arrow indicates an inter-node input link generated by the first link generating unit 144 . In the following description, an input link from node Y to node X is designated as the input link (X, Y).

Since the node 1 A generated by the first node candidate generating 143 is the node corresponding to the originating station, the first link generating unit 144 does not generate an input link to the node 1 A. For the node 2 A, the first link generating unit 144 generates an input link ( 1 A, 2 A) leading from the node 1 A corresponding to the station 1 upstream of the station 2 corresponding to the node 2 A. For the node 2 B, the first link generating unit 144 generates an input link ( 1 A, 2 B) leading from the node 1 A corresponding to the station 1 upstream of the station 2 corresponding to the node 2 B.

Similarly, for the node 3 A, the first link generating unit 144 generates an input link ( 2 A, 3 A) leading from the node 2 A and an input link ( 2 B, 3 A) leading from the node 2 B both corresponding to the station 2 upstream of the station 3 corresponding to the node 3 A. For the node 3 B, the first link generating unit 144 generates an input link ( 2 A, 3 B) leading from the node 2 A and an input link ( 2 B, 3 B) leading from the node 2 B both corresponding to the station 2 upstream of the station 3 corresponding to the node 3 B.

For the node 4 A, the first link generating unit 144 generates an input link ( 3 A, 4 A) leading from the node 3 A and an input link ( 3 B, 4 A) leading from the node 3 B both corresponding to the station 3 upstream of the station 4 corresponding to the node 4 A.

For the node 5 A, the first link generating unit 144 generates an input link ( 4 A, 5 A) leading from the node 4 A corresponding to the station 4 upstream of the station 5 corresponding to the node 5 A. For the node 5 B, the first link generating unit 144 generates an input link ( 4 A, 5 B) leading from the node 4 A corresponding to the station 4 upstream of the station 5 corresponding to the node 5 B.

For the node 6 A, the first link generating unit 144 generates an input link ( 5 A, 6 A) leading from the node 5 A and an input link ( 5 B, 6 A) leading from the node 5 B both corresponding to the station 5 upstream of the station 6 corresponding to the node 6 A.

Examples of the impairment amounts determined by the impairment determining unit 145 are illustrated below. In FIG. 12 , the numeric value depicted alongside each input link indicates the impairment calculated by the impairment determining unit 145 for that input link. The impairment determining unit 145 determines the impairment as being “1” when the input link ( 1 A, 2 A) generated by the first link generating unit 144 is selected. Further, the impairment determining unit 145 determines the impairment as being “2” when the input link ( 1 A, 2 B) is selected.

The impairment determining unit 145 determines the impairment as being “1” when the input link ( 2 A, 3 A) is selected. Similarly, the impairment determining unit 145 determines the impairment as being “2” when the input link ( 2 B, 3 A) is selected. Further, the impairment determining unit 145 determines the impairment as being “2” when the input link ( 2 A, 3 B) is selected. Similarly, the impairment determining unit 145 determines the impairment as being “3” when the input link ( 2 B, 3 B) is selected.

The impairment determining unit 145 determines the impairment as being “1” when the input link ( 3 A, 4 A) is selected. Similarly, the impairment determining unit 145 determines the impairment as being “2” when the input link ( 3 B, 4 A) is selected.

The impairment determining unit 145 determines the impairment as being “1” when the input link ( 4 A, 5 A) is selected. Further, the impairment determining unit 145 determines the impairment as being “2” when the input link ( 4 A, 5 B) is selected.

The impairment determining unit 145 determines the impairment as being “1” when the input link ( 5 A, 6 A) is selected. Similarly, the impairment determining unit 145 determines the impairment as being “2” when the input link ( 5 B, 6 A) is selected. In this way, the graph information is generated that includes the nodes corresponding to the OADMs and ILAs to be placed at the respective stations 1 to 6 and the links, each assigned a impairment value, for interconnecting the respective nodes.

FIG. 13 is a diagram (part 2 ) illustrating an example of the graph information generated by the intra-path graph generating unit 140 depicted in FIG. 8 . The impairment values depicted in FIG. 12 are not depicted in FIG. 13 . FIG. 12 is a case where, for each attention node, the first link generating unit 144 generates only the input link leading from the node that immediately precedes the attention node, but in addition to the input link from the immediately preceding node, the first link generating unit 144 may also generate an input link leading from a node located two or more nodes upstream of the attention node.

Here, for the node 3 B, the first link generating unit 144 generates, in addition to the input links ( 2 A, 3 B) and ( 2 B, 3 B), an input link ( 1 A, 3 B) leading from the node 1 A corresponding to the station 1 located further upstream of the station 3 corresponding to the node 3 A. When the input link ( 1 A, 3 B) is selected for the node 3 B, a bypass is placed at the station 2 .

Similarly, for the node 4 A, the first link generating unit 144 generates, in addition to the input links ( 3 A, 4 A) and ( 3 B, 4 A), an input link ( 1 A, 4 A) leading from the node 1 A corresponding to the station 1 located further upstream of the station 4 corresponding to the node 4 A. When the input link ( 1 A, 4 A) is selected for the node 4 A, a bypass is placed at each of the stations 2 and 3 .

In this way, the input links ( 1 A, 3 B) and ( 1 A, 4 A) are generated as bypass links. The impairment determining unit 145 determines the impairment as being “7” when the input link ( 1 A, 3 B) is selected. Further, the impairment determining unit 145 determines the impairment as being “2” when the input link ( 1 A, 4 A) is selected.

For simplicity, the following description deals with the case where only the input links depicted in FIG. 12 and their bypass links are generated.

FIG. 14 is a diagram illustrating how the first link selecting unit 146 depicted in FIG. 8 selects the input link. In FIG. 14 , the same parts as those depicted in FIGS. 12 and 13 are designated by the same reference characters, and the description of such parts will not be repeated here. The following describes how the input link is selected for the node 3 B. Each input link to the node 3 B is indicated by a thick arrow, and other input links are indicated by thin arrows. The first link selecting unit 146 selects one input link from among the three input links ( 2 A, 3 B), ( 2 B, 3 B), and ( 1 A, 3 B) generated as the input links to the node 3 B by the first link generating unit 144 .

By selecting one input link for the node 3 B from among the input links ( 2 A, 3 B), ( 2 B, 3 B), and ( 1 A, 3 B), the equipment placement up to the station where an OADM or an ILA is placed immediately preceding the station 3 is determined by the first node determining unit 147 for the case where an ILA is placed at the station 3 . When the input link ( 2 A, 3 B) is selected by the first link selecting unit 146 , the first node determining unit 147 determines that an OADM is placed at the station 2 when an ILA is placed at the station 3 .

On the other hand, when the input link ( 2 B, 3 B) is selected by the first link selecting unit 146 , the first node determining unit 147 determines that an ILA is placed at the station 2 when an ILA is placed at the station 3 . When the input link ( 1 A, 3 B) is selected by the first link selecting unit 146 , the first node determining unit 147 determines that a bypass is placed at the station 2 and an OADM in the station 1 when an ILA is placed at the station 3 .

While the above description has been given by specifically dealing with the case where the first link selecting unit 146 selects one input link from among the input links generated for the node 3 B, the first link selecting unit 146 also selects one input link from among a plurality of links for each of the other nodes 2 A to 6 A, 2 B and 5 B, and thus searches for the path corresponding to the placement that minimizes or maximizes the cumulative value of the impairment occurring along the wavelength path passing through the stations 1 to 6 .

FIG. 15 is a flowchart illustrating one example of the selection process performed by the first link selecting unit 146 depicted in FIG. 8 . FIG. 15 illustrates the process when the cumulative impairment determining unit 132 determines the maximum value Pmax k (d j ) that the cumulative impairment value can take on each wavelength path d j .

In step S 10 , the first link selecting unit 146 acquires the nodes Nx (x=1 to q) generated by the first node candidate generating unit 143 .

In step S 11 , the first link selecting unit 146 sets the node number x referring to one of the thus acquired nodes Nx to 1.

In step S 12 , the first link selecting unit 146 acquires the input links li (i=1 to r) generated for the node Nx.

In step S 13 , from among the input links li (i=1 to r) to the node Nx, the first link selecting unit 146 selects as the input link L to the node Nx the input link li that maximizes the sum of the impairment amount PNacc(Ni) accumulated up to the starting point node Ni of the input link li and the impairment amount PN(li) determined for the input link li.

Here, when the cumulative impairment determining unit 132 determines the minimum value Pmin k (d j ), the first link selecting unit 146 in step S 13 selects as the input link L to the node Nx, from among the input links li (i=1 to m) to the node Nx, the input link li that minimizes the sum of the impairment amount PNacc(Ni) accumulated up to the starting point node Ni of the input link li and the impairment amount PN(li) determined for the input link li.

In step S 14 , the first link selecting unit 146 calculates the impairment amount accumulated up to the node Nx, i.e., PNacc(Nx)=PNacc(Npre)+PN(L). Here, PNacc(Npre) represents the impairment amount accumulated up to the starting point node Npre of the input link L selected in step S 13 . PN(L) represents the impairment amount when the input link L is selected.

In step S 15 , the first link selecting unit 146 determines whether the node number x is the last number q or not. If the node number x is not the last number q, the first link selecting unit 146 changes the node number x to x+1 (step S 16 ), and returns to step S 12 to repeat the above process. If the node number x is the last number q, the first link selecting unit 146 terminates the input link selection process.

Next, a description will be given of the case where the process depicted in FIG. 15 is applied to the example illustrated in FIGS. 12 to 14 . FIG. 16 is a diagram illustrating the results of the input link selection process performed by the first link selecting unit 146 depicted in FIG. 8 . In FIG. 16 , the same parts as those depicted in FIGS. 12 to 14 are designated by the same reference characters, and the description of such parts will not be repeated here.

In FIG. 16 , each arrow indicates the input link L selected by the process depicted in FIG. 15 . The numeric value depicted alongside each node indicates the accumulated impairment calculated in steps S 12 to S 16 .

The input link L to the node 2 A is determined in the following manner. The total impairment amount when the input link ( 1 A, 2 A) is selected is calculated as PNacc( 1 A)+PN( 1 A, 2 A)=0+1=1 . Since the input link ( 1 A, 2 A) is the only remaining input link, the input link ( 1 A, 2 A) is selected as the input link L to the node 2 A.

The input link L to the node 2 B is determined in the following manner. The total impairment amount when the input link ( 1 A, 2 B) is selected is calculated as PNacc( 1 A)+PN( 1 A, 2 B)=0+2=2. Since the input link ( 1 A, 2 B) is the only remaining input link, the input link ( 1 A, 2 B) is selected as the input link L to the node 2 B.

The input link L to the node 3 A is determined in the following manner. The total impairment amount when the input link ( 2 A, 3 A) is selected is calculated as PNacc( 2 A)+PN( 2 A, 3 A)=1+1=2. The total impairment amount when the input link ( 2 B, 3 A) is selected is calculated as PNacc( 2 B)+PN( 2 B, 3 A)=2+2=4. Accordingly, the input link ( 2 B, 3 A) that maximizes the total impairment amount is selected as the input link L to the node 3 A.

The input link L to the node 3 B is determined in the following manner. The total impairment amount when the input link ( 2 A, 3 B) is selected is calculated as PNacc( 2 A)+PN( 2 A, 3 B)=1+2=3. The total impairment amount when the input link ( 2 B, 3 B) is selected is calculated as PNacc( 2 B)+PN( 2 B, 3 B)=2+3=5. The total impairment amount when the input link ( 1 A, 3 B) is selected is calculated as PNacc( 1 A)+PN( 1 A, 3 B)=0+7=7. Accordingly, the input link ( 1 A, 3 B) that maximizes the total impairment amount is selected as the input link L to the node 3 B.

The input link L to the node 4 A is determined in the following manner. The total impairment amount when the input link ( 3 A, 4 A) is selected is calculated as PNacc( 3 A)+PN( 3 A, 4 A)=4+1=5. The total impairment amount when the input link ( 3 B, 4 A) is selected is calculated as PNacc( 3 B)+PN( 3 B, 4 A)=7+2=9. The total impairment amount when the input link ( 1 A, 4 A) is selected is calculated as PNacc( 1 A)+PN( 1 A, 4 A)=0+2=2. Accordingly, the input link ( 3 B, 4 A) that maximizes the total impairment amount is selected as the input link L to the node 4 A.

The input link L to the node 5 A is determined in the following manner. The total impairment amount when the input link ( 4 A, 5 A) is selected is calculated as PNacc( 4 A)+PN( 4 A, 5 A)=9+1=10. Since the input link ( 4 A, 5 A) is the only remaining input link, the input link ( 4 A, 5 A) is selected as the input link L to the node 5 A.

The input link L to the node 5 B is determined in the following manner. The total impairment amount when the input link ( 4 A, 5 B) is selected is calculated as PNacc( 4 A)+PN( 4 A, 5 B)=9+2=11. Since the input link ( 4 A, 5 B) is the only remaining input link, the input link ( 4 A, 5 B) is selected as the input link L to the node 5 B.

The input link L to the node 6 A is determined in the following manner. The total impairment amount when the input link ( 5 A, 6 A) is selected is calculated as PNacc( 5 A)+PN( 5 A, 6 A)=10+1=11. The total impairment amount when the input link ( 5 B, 6 A) is selected is calculated as PNacc( 5 B)+PN( 5 B, 6 A)=11+2=13. Accordingly, the input link ( 5 B, 6 A) that maximizes the total impairment amount is selected as the input link L to the node 6 A. In this way, the input links to the respective nodes are selected.

FIG. 17 is a flowchart illustrating one example of the relay node determination process performed by the first node determining unit 147 depicted in FIG. 8 .

In step S 20 , the first node determining unit 147 acquires the nodes Nx (x=1 to q) generated by the first node candidate generating unit 143 .

In step S 21 , the first node determining unit 147 sets the node number x referring to one of the nodes Nx acquired in step S 20 to q. The node q indicates the node corresponding to the optical transmission equipment placed at the terminating station in the unit design section to be designed.

In step S 22 , the first node determining unit 147 holds the node Nq as a relay node.

In step S 23 , the first node determining unit 147 acquires the input link L to the node Nx from among the input links L selected in step S 13 of FIG. 15 .

In step S 24 , the first node determining unit 147 acquires the starting point node Npre of the input link L acquired in step S 23 .

In step S 25 , the first node determining unit 147 holds the starting point node Npre as a relay node.

In step S 26 , the first node determining unit 147 determines whether the number pre of the starting point node Npre acquired in step S 25 is the number 1 or not. Here, the number 1 is the node number of the optical transmission equipment placed at the originating station in the unit design section to be designed.

If the number pre of the starting point node Npre is not the number 1, the first node determining unit 147 in step S 27 changes the number x of the node Nx to the number pre of the starting point node Npre, and returns to step S 23 to repeat the above process. If the number pre of the starting point node Npre is the number 1, the first node determining unit 147 terminates the series of relay node determination operations.

In the above steps, each relay node held in step S 22 or S 25 provides information indicating the kind of the optical transmission equipment placed at the corresponding station in the unit design section to be designed. Next, a description will be given in which the process depicted in FIG. 17 is applied to the example illustrated in FIGS. 12 to 14 and 16 .

FIG. 18 is a diagram illustrating the results of the relay node determination process performed by the first node determining unit 147 depicted in FIG. 8 . In FIG. 18 , the same parts as those depicted in FIGS. 12 to 14 and 16 are designated by the same reference characters, and the description of such parts will not be repeated here. In FIG. 18 , the thick arrows indicate the path of the nodes as traced by the respective steps depicted FIG. 17 . The kinds of optical transmission equipment determined by the respective steps are depicted at the bottom of the graph. The filled circle indicates a bypass. First, the node number is set to indicate the node 6 A (step S 21 ), and the node 6 A is held as one of the relay nodes (step S 22 ). The input link ( 5 B, 6 A) is acquired as the input link L to the node 6 A (step S 23 ). Further, the node 5 B is acquired as the starting point node Npre of the input link ( 5 B, 6 A) (step S 24 ), and the node 5 B is held as one of the relay nodes (step S 25 ).

Next, the node number is set to indicate the node 5 B (step S 27 ), and the input link ( 4 A, 5 B) is acquired as the input link L to the node 5 B (step S 23 ). Further, the node 4 A is acquired as the starting point node Npre of the input link ( 4 A, 5 B) (step S 24 ), and the node 4 A is held as one of the relay nodes (step S 25 ).

Next, the node number is set to indicate the node 4 A (step S 27 ), and the input link ( 3 B, 4 A) is acquired as the input link L to the node 4 A (step S 23 ). Further, the node 3 B is acquired as the starting point node Npre of the input link ( 3 B, 4 A) (step S 24 ), and the node 3 B is held as one of the relay nodes (step S 25 ).

Next, the node number is set to indicate the node 3 B (step S 27 ), and the input link ( 1 A, 3 B) is acquired as the input link L to the node 3 B (step S 23 ). Further, the node 1 A is acquired as the starting point node Npre of the input link ( 1 A, 3 B) (step S 24 ), and the node 1 A is held as one of the relay nodes (step S 25 ).

Since the node number of the node 1 A is the node number of the optical transmission equipment placed at the originating station 1 in the unit design section 201 to be designed, the relay node determination process is terminated here. By tracing the input links L backward from the node 6 A to the node 1 A in this way, the first node determining unit 147 holds the nodes 6 A, 5 B, 4 A, 3 B, and 1 A in this order as the relay nodes.

Based on the impairment values assigned to the input links interconnecting the respective relay nodes held by the first node determining unit 147 , the cumulative value calculation unit 142 determines the impairment accumulated along the path passing through the relay nodes, and supplies the result to the noise amount upper limit value determining unit 133 .

In step S 4 of FIG. 11 , the equipment configuration determining unit 124 depicted in FIG. 7 determines the optical transmission equipment configuration candidate for each of the unit design sections generated by the section dividing unit 121 . FIG. 19 is a flowchart illustrating one example of the method by which the equipment configuration determining unit 124 determines the optical transmission equipment configuration for each unit design section.

In step S 30 , prior to the processing by the linear programming relaxation solving unit 127 , the initial candidate generating unit 125 generates, for each unit design section, at least one optical transmission equipment configuration candidate that satisfies the constraint (1-3) or the constraints (3-3) and (3-41) to (3-4R), and stores the candidate in the storage unit 126 .

In step S 31 , the linear programming relaxation solving unit 127 reads the equipment configuration candidate data 114 stored in the storage unit 126 , and determines the dual price vector by solving the linear programming relaxation of the integer programming problem given by equation (1) or (3) for the optical transmission equipment configuration candidate indicated by the equipment configuration candidate data 114 .

In step S 32 , in accordance with the reduced-cost calculation equation determined based on the value of the dual price vector determined by the linear programming relaxation solving unit 127 , the additional candidate searching unit 128 searches for a new optical transmission equipment configuration candidate t′ in which the value of the reduced cost is negative for each unit design section.

In step S 33 , the additional candidate searching unit 128 determines whether a new optical transmission equipment configuration candidate t′ is found or not.

If found, the new optical transmission equipment configuration candidate t′ is added to the equipment configuration candidate data 114 , and the process returns to step S 31 .

If a new optical transmission equipment configuration candidate t′ is not found, in step S 34 the integer programming problem solving unit 129 reads the equipment configuration candidate data 114 stored in the storage unit 126 and containing the candidates determined by the initial candidate generating unit 125 and the additional candidate searching unit 128 , and determines the optical transmission equipment configuration of the optical network 200 by solving the integer programming problem given by equation (1) or (3) without relaxing the integer programming problem for the optical transmission equipment configuration candidates indicated by the equipment configuration candidate data 114 .

The processing that the initial candidate generating unit 125 performs in step S 30 to determine the optical transmission equipment configuration candidate will be described below. FIG. 20 is a diagram (part 1 ) illustrating an example of the graph information generated by the first intra-unit-design-section graph generating unit 150 in the initial candidate generating unit 125 depicted in FIG. 9 .

Stations 11 to 18 depicted in FIG. 20 correspond to the stations 11 to 18 located along the unit linear section 204 depicted in FIG. 1 . Nodes 11 A to 18 A and nodes 12 B to 17 B are the nodes generated by the second node candidate generating unit 152 .

For simplicity, the following description is given by dealing only with the noise amount in the forward direction as an example of the transmission degradation amount, but actually, the noise amount in the backward direction is also considered in the same manner. Further, various kinds of impairments are also considered in the same manner as the noise amount.

The threshold value NOISEth of the noise amount is set to 7. Of the various kinds of optical transmission equipment that can be placed at the stations 11 to 18 , an OADM (for example, the OADM 400 of FIG. 3 ) is used as the kind of optical transmission equipment capable of accommodating an OEO regenerator.

Further, of the various kinds of optical transmission equipment that can be placed at the stations 11 to 18 , an ILA (for example, the ILA 500 of FIG. 4 ) is used as the kind of optical transmission equipment not capable of accommodating an OEO regenerator. Only an OADM that can accommodate an OEO regenerator can be placed at the station 11 , which is the originating station, and the station 18 , which is the terminating station. On the other hand, any kind of optical transmission equipment, i.e., an OADM, an ILA, or a bypass (for example, the bypass 600 of FIG. 5 ), can be placed at the stations 12 to 17 .

For the stations 11 to 18 , the second node candidate generating 152 generates the nodes 11 A to 18 A each indicating an OADM that can be placed at each of these stations. For the stations 12 to 17 , the second node candidate generating 152 generates the nodes 12 B to 17 B each indicating an ILA that can be placed at each of these stations. In FIG. 20 , the arrows indicate the input links generated by the second link generating unit 153 for the nodes 11 A to 18 A and 12 B to 17 B. In the following description, an input link from node Y to node X is designated as the input link (X, Y).

Since the node 11 A generated by the second node candidate generating 152 is the node corresponding to the originating station, the second link generating unit 153 does not generate an input link to the node 11 A. For the node 12 A, the second link generating unit 153 generates an input link ( 11 A, 12 A) leading from the node 11 A corresponding to the station 11 upstream of the station 12 corresponding to the node 12 A. For the node 12 B, the second link generating unit 153 generates an input link ( 11 A, 12 B) leading from the node 11 A corresponding to the station 11 upstream of the station 12 corresponding to the node 12 B.

Similarly, for the node 13 A, the second link generating unit 153 generates an input link ( 12 A, 13 A) leading from the node 12 A and an input link ( 12 B, 13 A) leading from the node 12 B both corresponding to the station 12 upstream of the station 13 corresponding to the node 13 A. For the node 13 B, the second link generating unit 153 generates an input link ( 12 A, 13 B) leading from the node 12 A and an input link ( 12 B, 13 B) leading from the node 12 B both corresponding to the station 12 upstream of the station 13 corresponding to the node 13 B.

For the node 14 A, the second link generating unit 153 generates an input link ( 13 A, 14 A) leading from the node 13 A and an input link ( 13 B, 14 A) leading from the node 13 B both corresponding to the station 13 upstream of the station 14 corresponding to the node 14 A. For the node 14 B, the second link generating unit 153 generates an input link ( 13 A, 14 B) leading from the node 13 A and an input link ( 13 B, 14 B) leading from the node 13 B both corresponding to the station 13 upstream of the station 14 corresponding to the node 14 B.

For the node 15 A, the second link generating unit 153 generates an input link ( 14 A, 15 A) leading from the node 14 A and an input link ( 14 B, 15 A) leading from the node 14 B both corresponding to the station 14 upstream of the station 15 corresponding to the node 15 A. For the node 15 B, the second link generating unit 153 generates an input link ( 14 A, 15 B) leading from the node 14 A and an input link ( 14 B, 15 B) leading from the node 14 B both corresponding to the station 14 upstream of the station 15 corresponding to the node 15 B.

For the node 16 A, the second link generating unit 153 generates an input link ( 15 A, 16 A) leading from the node 15 A and an input link ( 15 B, 16 A) leading from the node 15 B both corresponding to the station 15 upstream of the station 16 corresponding to the node 16 A. For the node 16 B, the second link generating unit 153 generates an input link ( 15 A, 16 B) leading from the node 15 A and an input link ( 15 B, 16 B) leading from the node 15 B both corresponding to the station 15 upstream of the station 16 corresponding to the node 16 B.

For the node 17 A, the second link generating unit 153 generates an input link ( 16 A, 17 A) leading from the node 16 A and an input link ( 16 B, 17 A) leading from the node 16 B both corresponding to the station 16 upstream of the station 17 corresponding to the node 17 A. For the node 17 B, the second link generating unit 153 generates an input link ( 16 A, 17 B) leading from the node 16 A and an input link ( 16 B, 17 B) leading from the node 16 B both corresponding to the station 16 upstream of the station 17 corresponding to the node 17 B.

For the node 18 A, the second link generating unit 153 generates an input link ( 17 A, 18 A) leading from the node 17 A and an input link ( 17 B, 18 A) leading from the node 17 B both corresponding to the station 17 upstream of the station 18 corresponding to the node 18 A.

Examples of the cost and amount of noise determined by the cost determining unit 154 and transmission degradation amount determining unit 155 depicted in FIG. 9 are illustrated below. In FIG. 20 , the cost and noise amount calculated by the cost determining unit 154 and transmission degradation amount determining unit 155 for each input link are depicted as (cost, noise amount) alongside the input link. The cost determining unit 154 and transmission degradation amount determining unit 155 determine the cost and noise amount as being (2, 1) when the input link ( 11 A, 12 A) generated by the second link generating unit 153 is selected. Further, the cost determining unit 154 and transmission degradation amount determining unit 155 determine the cost and noise amount as being (1, 2) when the input link ( 11 A, 12 B) is selected.

The cost determining unit 154 and transmission degradation amount determining unit 155 determine the cost and noise amount as being (2, 1) when the input link ( 12 A, 13 A) is selected. Similarly, the cost determining unit 154 and transmission degradation amount determining unit 155 determine the cost and noise amount as being (4, 2) when the input link ( 12 B, 13 A) is selected. Further, the cost determining unit 154 and transmission degradation amount determining unit 155 determine the cost and noise amount as being (2, 2) when the input link ( 12 A, 13 B) is selected. Similarly, the cost determining unit 154 and transmission degradation amount determining unit 155 determine the cost and noise amount as being (2, 3) The cost determining unit 154 and transmission degradation amount determining unit 155 determine the cost and noise amount as being (2, 1) when the input link ( 13 A, 14 A) is selected. Similarly, the cost determining unit 154 and transmission degradation amount determining unit 155 determine the cost and noise amount as being (2, 2) when the input link ( 13 B, 14 A) is selected. Further, the cost determining unit 154 and transmission degradation amount determining unit 155 determine the cost and noise amount as being (1, 2) when the input link ( 13 A, 14 B) is selected. Similarly, the cost determining unit 154 and transmission degradation amount determining unit 155 determine the cost and noise amount as being (2, 3) when the input link ( 13 B, 14 B) is selected.

The cost determining unit 154 and transmission degradation amount determining unit 155 determine the cost and noise amount as being (2, 10) when the input link ( 14 A, 15 A) is selected. Similarly, the cost determining unit 154 and transmission degradation amount determining unit 155 determine the cost and noise amount as being (3, 10) when the input link ( 14 B, 15 A) is selected. Since the noise amount when either the input link ( 14 A, 15 A) or the input link ( 14 B, 15 A) is selected exceeds the threshold value 7 defined by NOISEth, the cost determining unit 154 and transmission degradation amount determining unit 155 delete the input links ( 14 A, 15 A), ( 14 B, 15 A), ( 15 A, 16 A), and ( 15 A, 16 B).

The cost determining unit 154 and transmission degradation amount determining unit 155 determine the cost and noise amount as being (2, 2) when the input link ( 14 A, 15 B) is selected. Similarly, the cost determining unit 154 and transmission degradation amount determining unit 155 determine the cost and noise amount as being (2, 3) when the input link ( 14 B, 15 B) is selected. Further, the cost determining unit 154 and transmission degradation amount determining unit 155 determine the cost and noise amount as being (3, 2) when the input link ( 15 B, 16 A) is selected. Similarly, the cost determining unit 154 and transmission degradation amount determining unit 155 determine the cost and noise amount as being (2, 3) when the input link ( 15 B, 16 B) is selected.

The cost determining unit 154 and transmission degradation amount determining unit 155 determine the cost and noise amount as being (2, 1) when the input link ( 16 A, 17 A) is selected. Similarly, the cost determining unit 154 and transmission degradation amount determining unit 155 determine the cost and noise amount as being (3, 2) when the input link ( 16 B, 17 A) is selected. Further, the cost determining unit 154 and transmission degradation amount determining unit 155 determine the cost and noise amount as being (1, 2) when the input link ( 16 A, 17 B) is selected. Similarly, the cost determining unit 154 and transmission degradation amount determining unit 155 determine the cost and noise amount as being (2, 3) when the input link ( 16 B, 17 B) is selected.

The cost determining unit 154 and transmission degradation amount determining unit 155 determine the cost and noise amount as being (2, 1) when the input link ( 17 A, 18 A) is selected. Similarly, the cost determining unit 154 and transmission degradation amount determining unit 155 determine the cost and noise amount as being (2, 2) when the input link ( 17 B, 18 A) is selected. In this way, the graph information is generated that includes the nodes corresponding to the OADMs and ILAs placed at the respective stations 11 to 18 and the links interconnecting the respective nodes, each link being assigned a value representing the transmission degradation amount and noise amount.

FIG. 21 is a diagram (part 2 ) illustrating an example of the graph information generated by the first intra-unit-design-section graph generating unit 150 depicted in FIG. 9 . The cost and amount of noise calculated by the cost determining unit 154 and transmission degradation amount determining unit 155 , depicted in FIG. 20 , are not depicted in FIG. 21 . FIG. 20 has illustrated the case where, for each attention node, the second link generating unit 153 generates only the input link leading from the node that immediately precedes the attention node, but in addition to the input link from the immediately preceding node, the second link generating unit 153 may also generate an input link leading from a node located two or more nodes upstream of the attention node.

For the node 13 A, the second link generating unit 153 generates, in addition to the input links ( 12 A, 13 A) and ( 12 B, 13 A), an input link ( 11 A, 13 A) leading from the node 11 A corresponding to the station 11 further upstream of the station 13 corresponding to the node 13 A. When the input link ( 11 A, 13 A) is selected for the node 13 A, a bypass is placed at the station 12 .

Similarly, for the node 13 B, the second link generating unit 153 generates, in addition to the input links ( 12 A, 13 B) and ( 12 B, 13 B), an input link ( 11 A, 13 B) leading from the node 11 A corresponding to the station 11 further upstream of the station 13 corresponding to the node 13 B. When the input link ( 11 A, 13 B) is selected for the node 13 B, a bypass is placed at the station 12 .

For the node 14 A, the second link generating unit 153 generates, in addition to the input links ( 13 A, 14 A) and ( 13 B, 14 A), an input link ( 11 A, 14 A) leading from the node 11 A corresponding to the station 11 further upstream of the station 14 corresponding to the node 14 A. When the input link ( 11 A, 14 A) is selected for the node 14 A, a bypass is placed at each of the stations 12 and 13 .

Further, for the node 14 B, the second link generating unit 153 generates, in addition to the input links ( 13 A, 14 B) and ( 13 B, 14 B), an input link ( 11 A, 14 B) leading from the node 11 A corresponding to the station 11 further upstream of the station 14 corresponding to the node 14 B and an input link ( 12 A, 14 B) leading from the node 12 A corresponding to the station 12 upstream of the station 14 .

When the input link ( 11 A, 14 B) is selected for the node 14 B, a bypass is placed at each of the stations 12 and 13 . On the other hand, when the input link ( 12 A, 14 B) is selected, a bypass is placed at the station 13 . In this way, the input links ( 11 A, 13 A), ( 11 A, 13 B), ( 11 A, 14 A), ( 11 A, 14 B), and ( 12 A, 14 B) are generated as bypass links.

The cost determining unit 154 and transmission degradation amount determining unit 155 determine the cost and noise amount as being (10, 4) when the input link ( 11 A, 13 A) is selected. Further, the cost determining unit 154 and transmission degradation amount determining unit 155 determine the cost and noise amount as being (10, 5) when the input link ( 11 A, 13 B) is selected. Similarly, the cost determining unit 154 and transmission degradation amount determining unit 155 determine the cost and noise amount as being (10, 5) when the input link ( 11 A, 14 A) is selected.

The cost determining unit 154 and transmission degradation amount determining unit 155 determine the cost and noise amount as being (10, 6) when the input link ( 11 A, 14 B) is selected. Similarly, the cost determining unit 154 and transmission degradation amount determining unit 155 determine the cost and noise amount as being (2, 2) when the input link ( 12 A, 14 B) is selected. Other bypass links can also be generated, but for simplicity, the following description deals with the case where only the input links depicted in FIG. 20 and their bypass links are generated. Since, in the generated graph, there are no input links associated with the node 15 A, the cost determining unit 154 and transmission degradation amount determining unit 155 delete the node 15 A

FIG. 22 is a diagram illustrating how the second link selecting unit 156 depicted in FIG. 9 selects the input link. In FIG. 22 , the same parts as those depicted in FIGS. 20 and 21 are designated by the same reference characters, and the description of such parts will not be repeated here. The following describes how the input link is selected for the node 13 A. Each input link to the node 13 A is indicated by a thick arrow, and other input links are indicated by thin arrows. The second link selecting unit 156 selects one input link from among the three input links ( 12 A, 13 A), ( 12 B, 13 A), and ( 11 A, 13 A) generated as the input links to the node 13 A by the second link generating unit 153 .

By selecting one input link for the node 13 A from among the input links ( 12 A, 13 A), ( 12 B, 13 A), and ( 11 A, 13 A), the equipment placement up to the station where an OADM or an ILA is placed immediately preceding the station 13 is determined by the second node determining unit 157 for the case where an OADM is placed at the station 13 . When the input link ( 12 A, 13 A) is selected by the second link selecting unit 156 , the second node determining unit 157 determines that an OADM is placed at the station 12 when an OADM is placed at the station 13 .

On the other hand, when the input link ( 12 B, 13 A) is selected by the second link selecting unit 156 , the second node determining unit 157 determines that an ILA is placed at the station 12 when an OADM is placed at the station 13 . When the input link ( 11 A, 13 A) is selected by the second link selecting unit 156 , the second node determining unit 157 determines that a bypass is placed at the station 12 and an OADM in the station 11 when an OADM is placed at the station 13 .

While the above description has been given by specifically dealing with the case where the second link selecting unit 156 selects one input link for the node 13 A from among the input links generated for that node, the second link selecting unit 156 also selects one input link from among a plurality of links for each of the other nodes 12 A to 14 A, 16 A to 18 A, and 12 B to 17 B, and thus searches for the path corresponding to the placement that holds the transmission degradation amount to within the threshold value and that minimizes the cost.

FIGS. 23 and 24 are a flowchart illustrating one example of the selection process performed by the second link selecting unit 156 depicted in FIG. 9 . FIGS. 23 and 24 deal with the case where the noise amount and the various kinds of impairments occurring in the forward and backward directions are taken as the transmission degradation amounts.

In step S 40 , the second link selecting unit 156 acquires the nodes Nx (x=1 to q) generated by the second node candidate generating unit 152 .

In step S 41 , the second link selecting unit 156 sets the node number x referring to one of the nodes Nx acquired in step S 40 to 1.

In step S 42 , the second link selecting unit 156 determines whether or not the node Nx is a node capable of accommodating an OEO regenerator.

If, in step S 42 , the node Nx is a node capable of accommodating an OEO regenerator, the second link selecting unit 156 in step S 43 sets the minimum value of the noise amount, NOISEmin, to 0. The minimum value NOISEmin defines the minimum value of the noise amount occurring along the path from the node Nx to the downstream OEO regenerative node. In step S 44 , the second link selecting unit 156 sets the minimum value of the impairment, IMPAIRMENTmin, to 0, and proceeds to step S 48 . The minimum value IMPAIRMENTmin defines the minimum value of the impairment occurring along the path from the node Nx to the downstream OEO regenerative node.

The minimum value NOISEmin is set for each of the forward and backward direction components of the noise amount.

Likewise, the minimum value IMPAIRMENTmin is set for each kind of impairment and for each of the forward and backward direction components of the impairment.

If, in step S 42 , the node Nx is not a node capable of accommodating an OEO regenerator, the second link selecting unit 156 in step S 45 searches for a minimum noise path to the downstream OEO regenerative node that follows the node Nx. The minimum noise path to the downstream OEO regenerative node that follows the node Nx refers to the path to the downstream OEO regenerative node that minimizes the sum of the noise amounts occurring along the input links to the node Nx from among the OEO regenerative nodes located downstream of the node Nx.

In step S 46 , for each of the forward and backward direction components, the second link selecting unit 156 sets the minimum value NOISEmin of the noise amount equal to the value of the noise amount of the minimum noise path found in step S 45 .

In step S 47 , for each kind of impairment and for each of the forward and backward direction components, the second link selecting unit 156 sets the minimum value IMPAIRMENTmin of the impairment to the value of the impairment of the minimum noise path found in step S 45 .

In step S 48 , the second link selecting unit 156 acquires the input links li (i=1 to r) generated for the node Nx. IMPAIRMENTmin is set equal to the value of the minimum noise path, but a separate search may be made to find a minimum impairment path, and the value of such a path may be taken as IMPAIRMENTmin.

In step S 49 , the second link selecting unit 156 sets the input link number i referring to one of the input links li acquired in step S 48 to 1.

In step S 50 , for each of the forward and backward direction components, the second link selecting unit 156 determines whether the sum of the noise NOISEacc(Ni) accumulated up to the starting point node Ni of the input link l 1 , the noise NOISE(li) that occurs when the input link li is selected, and the noise amount minimum value NOISEmin set in step S 43 or S 46 is larger than the noise threshold value NOISEth.

The second link selecting unit 156 uses as the noise threshold values NOISEth the intra-unit-design-section noise amount upper limit values Nth 1 ( g h ) and Nth 2 ( g h ) determined by the intra-unit-design-section noise amount upper limit value determining unit 134 .

If, in step S 50 , the sum is smaller than or equal to the noise threshold value NOISEth for both of the forward and backward direction components, the process proceeds to step S 51 .

In step S 51 , for each kind of impairment and for each of the forward and backward direction components, the second link selecting unit 156 determines whether or not the sum of the impairment IMPAIRMENTacc(Ni) accumulated up to the starting point node Ni of the input link l 1 , the impairment IMPAIRMENT(li) that occurs when the input link li is selected, and the impairment minimum value IMPAIRMENTmin set in step S 44 or S 47 is larger than the impairment threshold value IMPAIRMENTth.

The second link selecting unit 156 uses as the impairment threshold values IMPAIRMENTth the intra-unit-design-section impairment upper limit values Pth 1 k ( g h ) and Pth 2 k ( g h ) determined by the intra-unit-design-section impairment upper limit value determining unit 131 .

If, in step S 50 , the sum is larger than the noise threshold value NOISEth for one or other or both of the forward and backward direction components, the process proceeds to step S 52 .

Likewise, if, in step S 51 , it is determined for any one of the various kinds of impairments that the sum is larger than the impairment threshold value IMPAIRMENTth for one or other or both of the forward and backward direction components, the process proceeds to step S 52 .

In step S 52 , the second link selecting unit 156 deletes the input link li from the input links acquired in step S 48 , and proceeds to step S 53 .

If, in step S 51 , it is determined for any kind of impairment that the sum is smaller than or equal to the impairment threshold value IMPAIRMENTth for both of the forward and backward direction components, then in step S 53 the second link selecting unit 156 determines whether the input link number i is the last number r or not.

If the input link number i is not the last number r, the second link selecting unit 156 changes the input link number i to i+1 in step S 54 , and returns to step S 50 to repeat the above process.

If, in step S 53 , the input link number i is the last number r, the process proceeds to step S 55 of FIG. 24 (as indicated by symbol A).

In step S 55 , from among the input links li acquired in step S 48 but not deleted in step S 52 , the second link selecting unit 156 selects as the input link L to the node Nx the input link li that minimizes the sum of the cost COSTacc(Ni) accumulated up to the starting point node Ni and the cost COST(li) of the input link li.

In step S 56 , the second link selecting unit 156 calculates the cost accumulated up to the node Nx as COSTacc(Nx)=COSTacc(Npre)+COST(L). Here, COSTacc(Npre) represents the cost accumulated up to the starting point node Npre of the input link L selected in step S 55 . COST(L) represents the cost when the input link L is selected.

In step S 57 , the second link selecting unit 156 determines whether or not the node Nx is a node capable of accommodating an OEO regenerator (step S 57 ). If it is a node capable of accommodating an OEO regenerator, the process proceeds to step S 58 where the second link selecting unit 156 resets the noise NOISEacc(Nx) accumulated up to the node Nx to 0 for both of the forward and backward direction components. In the next step S 59 , the second link selecting unit 156 resets the impairment IMPAIRMENTacc(Nx) accumulated up to the node Nx to 0 for both of the forward and backward direction components. After that, the process proceeds to step S 62 .

If it is determined in step S 57 that the node Nx is not a node capable of accommodating an OEO regenerator, the process proceeds to step S 60 where, for both of the forward and backward direction components, the second link selecting unit 156 sets the noise NOISEacc(Nx) accumulated up to the node Nx equal to the sum of the noise NOISEacc(Npre) accumulated up to the node Npre and the noise NOISE(L) that occurs along the input link L.

In the next step S 61 , for each kind of impairment and for each of the forward and backward direction components, the second link selecting unit 156 sets the impairment IMPAIRMENTacc(Nx) accumulated up to the node Nx equal to IMPAIRMENTacc(Npre)+IMPAIRMENT(L). Here, IMPAIRMENTacc(Npre) represents the impairment accumulated up to the node Npre. In step S 62 , the second link selecting unit 156 determines whether the node number x is the last number q or not. If, in step S 62 , the node number x is not the last number q, the node number x is changed to x+1, and the process returns to step S 42 of FIG. 23 (as indicated by symbol B) to repeat the above process. If the node number x is the last number q, the input link selection process is terminated.

By repeating the above steps, the input links L to the respective nodes Nx generated by the second node candidate generating unit 152 are sequentially selected. Next, a description will be given of the case where the process depicted in FIGS. 23 and 24 is applied to the example illustrated in FIGS. 20 to 22 . For simplicity, the following description is given by using only the forward direction noise amount to represent the transmission degradation amount. Accordingly, steps S 44 , S 47 , S 51 , S 59 , and S 61 depicted in FIGS. 23 and 24 will not be described here.

FIG. 25 is a diagram illustrating the results of the input link selection process performed by the second link selecting unit 156 depicted in FIG. 9 . In FIG. 25 , the same parts as those depicted in FIGS. 20 to 22 are designated by the same reference characters, and the description of such parts will not be repeated here. In FIG. 25 , each arrow indicates the input link L selected by the process depicted in FIGS. 23 and 24 . Further, the accumulated cost COSTacc and accumulated noise NOISEacc calculated in steps S 55 to S 61 are depicted as (accumulated cost, accumulated noise amount) alongside each node.

The input link L to the node 12 A is determined in the following manner. Since the node 12 A is a node corresponding to an OADM, the minimum value NOISEmin of the noise amount is 0 (step S 43 ). Only the input link ( 11 A, 12 A) is acquired as the input link to the node 12 A (step S 48 ).

The total noise amount when the input link ( 11 A, 12 A) is selected is calculated as NOISEacc( 11 A)+NOISE( 11 A, 12 A)+NOISEmin=0+1+0=1 (step S 50 ). Since this total noise amount is not larger than the threshold value 7 defined by NOISEth, the input link ( 11 A, 12 A) is not deleted (step S 52 ).

The total cost when the input link ( 11 A, 12 A) is selected is calculated as COSTacc( 11 A)+COST( 11 A, 12 A)=0+2=2 (step S 55 ). Since the input link ( 11 A, 12 A) is the only remaining input link, the input link ( 11 A, 12 A) is selected as the input link L to the node 12 A (step S 55 ).

The cost accumulated up to the node 12 A is calculated as COSTacc( 12 A)=COSTacc( 11 A)+COST( 11 A, 12 A)=0+2=2 (step S 56 ). Since the node 12 A is a node corresponding to an OADM, the noise NOISEacc( 12 A) accumulated up to the node 12 A is reset to 0 (step S 58 ).

The input link L to the node 12 B is determined in the following manner. Since the node 12 B is a node corresponding to an ILA, the path from the node 12 B to the node 13 A is chosen as the minimum noise path to the downstream OEO regenerative node for the node 12 B (step S 45 ), and the minimum value NOISEmin of the noise amount is set to 2 (step S 46 ). Here, only the input link ( 11 A, 12 B) is acquired as the input link to the node 12 B (step S 48 ).

The total noise amount when the input link ( 11 A, 12 B) is selected is calculated as NOISEacc( 11 A)+NOISE( 11 A, 12 B)+NOISEmin=0+2+2=4 (step S 50 ). Since the total noise amount when the input link ( 11 A, 12 B) is selected is not larger than the threshold value 7 defined by NOISEth, the input link ( 11 A, 12 B) is not deleted (step S 52 ).

The total cost when the input link ( 11 A, 12 B) is selected is calculated as COSTacc( 11 A)+COST( 11 A, 12 B)=0+1=1 (step S 55 ). Since the input link ( 11 A, 12 B) is the only remaining input link, the input link ( 11 A, 12 B) is selected as the input link L to the node 12 B (step S 55 ).

The cost accumulated up to the node 12 B is calculated as COSTacc( 12 B)=COSTacc( 11 A)+COST( 11 A, 12 B)=0+1=1 (step S 56 ). Since the node 12 B is a node corresponding to an ILA, the noise accumulated up to the node 12 B is calculated as NOISEacc( 12 B)=NOISEacc( 11 A)+NOISE( 11 A, 12 B)=0+2=2 (step S 60 ).

Next, how the input link L to the node 13 A is determined will be described. Since the node 13 A is a node corresponding to an OADM, the minimum value NOISEmin of the noise amount is 0 (step S 43 ). Here, the input links ( 12 A, 13 A), ( 12 B, 13 A), and ( 11 A, 13 A) are acquired as the input links to the node 13 A (step S 48 ).

The total noise amount when the input link ( 12 A, 13 A) is selected is calculated as NOISEacc( 12 A)+NOISE( 12 A, 13 A)+NOISEmin=0+1+0=1 (step S 50 ). Likewise, the total noise amount when the input link ( 12 B, 13 A) is selected is calculated as NOISEacc( 12 B)+NOISE( 12 B, 13 A)+NOISEmin=2+2+0=4 (step S 50 ).

The total noise amount when the input link ( 11 A, 13 A) is selected is calculated as NOISEacc( 11 A)+NOISE( 11 A, 13 A)+NOISEmin=0+4+0=4 (step S 50 ). Since none of these total noise amounts are larger than the threshold value 7 defined by NOISEth, none of the input links ( 12 A, 13 A), ( 12 B, 13 A), and ( 11 A, 13 A) are deleted (step S 52 ).

The total cost when the input link ( 12 A, 13 A) is selected is calculated as COSTacc( 12 A)+COST( 12 A, 13 A)=2+2=4. Likewise, the total cost when the input link ( 12 B, 13 A) is selected is calculated as COSTacc( 12 B)+COST( 12 B, 13 A)=1+4=5. The total cost when the input link ( 11 A, 13 A) is selected is calculated as COSTacc( 11 A)+COST( 11 A, 13 A)=0+10=10. Accordingly, the input link ( 12 A, 13 A) that minimizes the total cost is selected as the input link L to the node 13 A (step S 55 ).

The cost accumulated up to the node 13 A is calculated as COSTacc( 13 A)=COSTacc( 12 A)+COST( 12 A, 13 A)=2+2=4 (step S 56 ). Since the node 13 A is a node corresponding to an OADM, the noise NOISEacc( 13 A) accumulated up to the node 13 A is reset to 0 (step S 58 ).

The input link L to the node 13 B is determined in the following manner. Since the node 13 B is a node corresponding to an ILA, the path from the node 13 B to the node 14 A is chosen as the minimum noise path (step S 45 ), and the minimum value NOISEmin of the noise amount is set to 2 (step S 46 ). The input links ( 12 A, 13 B), ( 12 B, 13 B), and ( 11 A, 13 B) are acquired as the input nodes to the node 13 B (step S 48 ).

The total noise amount when the input link ( 12 A, 13 B) is selected is calculated as NOISEacc( 12 A)+NOISE( 12 A, 13 B)+NOISEmin=0+2+2=4 (step S 50 ). Likewise, the total noise amount when the input link ( 12 B, 13 B) is selected is calculated as NOISEacc( 12 B)+NOISE( 12 B, 13 B)+NOISEmin=2+3+2=7 (step S 50 ).

The total noise amount when the input link ( 11 A, 13 B) is selected is calculated as NOISEacc( 11 A)+NOISE( 11 A, 13 B)+NOISEmin=0+5+2=7 (step S 50 ). Since none of these total noise amounts are larger than the threshold value 7 defined by NOISEth, none of the input links ( 12 A, 13 B), ( 12 B, 13 B), and ( 11 A, 13 B) are deleted (step S 52 ).

The total cost when the input link ( 12 A, 13 B) is selected is calculated as COSTacc( 12 A)+COST( 12 A, 13 B)=2+2=4. Likewise, the total cost when the input link ( 12 B, 13 B) is selected is calculated as COSTacc( 12 B)+COST( 12 B, 13 B)=1+2=3. The total cost when the input link ( 11 A, 13 B) is selected is calculated as COSTacc( 11 A)+COST( 11 A, 13 B)=0+10=10. Accordingly, the input link ( 12 B, 13 B) that minimizes the total cost is selected as the input link L to the node 13 B (step S 55 ).

The cost accumulated up to the node 13 B is calculated as COSTacc( 13 B)=COSTacc( 12 B)+COST( 12 B, 13 B)=1+2=3 (step S 56 ). Since the node 13 B is a node corresponding to an ILA, the noise accumulated up to the node 13 B is calculated as NOISEacc( 13 B)=NOISEacc( 12 B)+NOISE( 12 B, 13 B)=2+3=5 (step S 60 ).

Next, how the input link L to the node 14 A is determined will be described. Since the node 14 A is a node corresponding to an OADM, the minimum value NOISEmin of the noise amount is 0 (step S 43 ). The input links ( 13 A, 14 A), ( 13 B, 14 A), and ( 11 A, 14 A) are acquired as the input links to the node 14 A (step S 48 ).

The total noise amount when the input link ( 13 A, 14 A) is selected is calculated as NOISEacc( 13 A)+NOISE( 13 A, 14 A)+NOISEmin=0+1+0=1 (step S 50 ). Likewise, the total noise amount when the input link ( 13 B, 14 A) is selected is calculated as NOISEacc( 13 B)+NOISE( 13 B, 14 A)+NOISEmin=5+2+0=7 (step S 50 ).

The total noise amount when the input link ( 11 A, 14 A) is selected is calculated as NOISEacc( 11 A)+NOISE( 11 A, 14 A)+NOISEmin=0+5+0=5 (step S 50 ). Since none of these total noise amounts are larger than the threshold value 7 defined by NOISEth, none of the input links ( 13 A, 14 A), ( 13 B, 14 A), and ( 11 A, 14 A) are deleted (step S 52 ).

The total cost when the input link ( 13 A, 14 A) is selected is calculated as COSTacc( 13 A)+COST( 13 A, 14 A)=4+2=6. Likewise, the total cost when the input link ( 13 B, 14 A) is selected is calculated as COSTacc( 13 B)+COST( 13 B, 14 A)=3+2=5. The total cost when the input link ( 11 A, 14 A) is selected is calculated as COSTacc( 11 A)+COST( 11 A, 14 A)=0+10=10. Accordingly, the input link ( 13 B, 14 A) that minimizes the total cost is selected as the input link L to the node 14 A (step S 55 ).

The cost accumulated up to the node 14 A is calculated as COSTacc( 14 A)=COSTacc( 13 B)+COST( 13 B, 14 A)=3+2=5 (step S 56 ). Since the node 14 A is a node corresponding to an OADM, the noise NOISEacc( 14 A) accumulated up to the node 14 A is reset to 0 (step S 58 ).

The input link L to the node 14 B is determined in the following manner. Since the node 14 B is a node corresponding to an ILA, the path from the node 14 B to the node 16 A is chosen as the minimum noise path to the downstream OEO regenerative node for the node 14 B (step S 45 ), and the minimum value NOISEmin of the noise amount is given as 3+2=5 (step S 46 ). The input links ( 13 A, 14 B), ( 13 B, 14 B), ( 11 A, 14 B), and ( 12 A, 14 B) are acquired as the input nodes to the node 14 B (step S 48 ).

The total noise amount when the input link ( 13 A, 14 B) is selected is calculated as NOISEacc( 13 A)+NOISE( 13 A, 14 B)+NOISEmin=0+2+5=7 (step S 50 ). Likewise, the total noise amount when the input link ( 13 B, 14 B) is selected is calculated as NOISEacc( 13 B)+NOISE( 13 B, 14 B)+NOISEmin=5+3+5=13 (step S 50 ). The total noise amount when the input link ( 11 A, 14 B) is selected is calculated as NOISEacc( 11 A)+NOISE( 11 A, 14 B)+NOISEmin=0+6+5=11 (step S 50 ).

The total noise amount when the input link ( 12 A, 14 B) is selected is calculated as NOISEacc( 12 A)+NOISE( 12 A, 14 B)+NOISEmin=0+2+5=7 (step S 50 ). The input links ( 13 B, 14 B) and ( 11 A, 14 B) whose total noise amounts are larger than the threshold value 7 defined by NOISEth are deleted (step S 52 ).

The total cost when the input link ( 13 A, 14 B) is selected is calculated as COSTacc( 13 A)+COST( 13 A, 14 B)=4+1=5 (step S 55 ). The total cost when the input link ( 12 A, 14 B) is selected is calculated as COSTacc( 12 A)+COST( 12 A, 14 B)=2+2=4. Accordingly, the input link ( 12 A, 14 B) that minimizes the total cost is selected as the input link L to the node 14 B (step S 55 ).

The cost accumulated up to the node 14 B is calculated as COSTacc( 14 B)=COSTacc( 12 A)+COST( 12 A, 14 B)=2+2=4 (step S 56 ). Since the node 14 B is a node corresponding to an ILA, the noise accumulated up to the node 14 B is calculated as NOISEacc( 14 B)=NOISEacc( 12 A)+NOISE( 12 A, 14 B)=0+2=2 (step S 60 ).

The input link L to the node 15 B is determined in the following manner. Since the node 15 B is a node corresponding to an ILA, the path from the node 15 B to the node 16 A is chosen as the minimum noise path to the downstream OEO regenerative node for the node 15 B (step S 45 ), and the minimum value NOISEmin of the noise amount is set to 2 (step S 46 ). The input links ( 14 A, 15 B) and ( 14 B, 15 B) are acquired as the input nodes to the node 15 B (step S 48 ).

The total noise amount when the input link ( 14 A, 15 B) is selected is calculated as NOISEacc( 14 A)+NOISE( 14 A, 15 B)+NOISEmin=0+2+2=4 (step S 50 ). The total noise amount when the input link ( 14 B, 15 B) is selected is calculated as NOISEacc( 14 B)+NOISE( 14 B, 15 B)+NOISEmin=2+3+2=7. Since neither of these total amounts are larger than the threshold value 7 defined by NOISEth, neither the input link ( 14 A, 15 B) nor the input link ( 14 B, 15 B) is deleted (step S 52 ).

The total cost when the input link ( 14 A, 15 B) is selected is calculated as COSTacc( 14 A)+COST( 14 A, 15 B)=5+2=7 (step S 55 ). The total cost when the input link ( 14 B, 15 B) is selected is calculated as COSTacc( 14 B)+COST( 14 B, 15 B)=4+2=6. Accordingly, the input link ( 14 B, 15 B) that minimizes the total cost is selected as the input link L to the node 15 B (step S 55 ).

The cost accumulated up to the node 15 B is calculated as COSTacc( 15 B)=COSTacc( 14 B)+COST( 14 B, 15 B)=4+2=6 (step S 56 ). Since the node 15 B is a node corresponding to an ILA, the noise accumulated up to the node 15 B is calculated as NOISEacc( 15 B)=NOISEacc( 14 B)+NOISE( 14 B, 15 B)=2+3=5 (step S 60 ).

Next, how the input link L to the node 16 A is determined will be described. Since the node 16 A is a node corresponding to an OADM, the minimum value NOISEmin of the noise amount is 0 (step S 43 ). Only the input link ( 15 B, 16 A) is acquired as the input link to the node 16 A (step S 48 ).

The total noise amount when the input link ( 15 B, 16 A) is selected is calculated as NOISEacc( 15 B)+NOISE( 15 B, 16 A)+NOISEmin=5+2+0=7 (step S 50 ). Since the total noise amount when the input link ( 15 B, 16 A) is selected is not larger than the threshold value 7 defined by NOISEth, the input link ( 15 B, 16 A) is not deleted (step S 52 ).

The total cost when the input link ( 15 B, 16 A) is selected is calculated as COSTacc( 15 B)+COST( 15 B, 16 A)=6+3=9 (step S 55 ). Since the input link ( 15 B, 16 A) is the only remaining input link, the input link ( 15 B, 16 A) is selected as the input link L to the node 16 A (step S 55 ).

The cost accumulated up to the node 16 A is calculated as COSTacc( 16 A)=COSTacc( 15 B)+COST( 15 B, 16 A)=6+3=9 (step S 56 ). Since the node 16 A is a node corresponding to an OADM, the noise NOISEacc( 16 A) accumulated up to the node 16 A is reset to 0 (step S 58 ).

The input link L to the node 16 B is determined in the following manner. Since, in step S 42 , the node 16 B is a node corresponding to an ILA, the path to the node 17 A is chosen (step S 45 ), and the minimum value NOISEmin of the noise amount is set to 2 (step S 46 ). Only the input link ( 15 B, 16 B) is acquired as the input link to the node 16 B (step S 48 ).

The total noise amount when the input link ( 15 B, 16 B) is selected is calculated as NOISEacc( 15 B)+NOISE( 15 B, 16 B)+NOISEmin=5+3+2=10 (step S 50 ). Since this total noise amount is larger than the threshold value 7 defined by NOISEth, the input link ( 15 B, 16 B) is deleted (step S 52 ).

Since the only input link acquired in step S 48 is deleted, the process from step S 55 onward is not performed for the node 16 B. Further, the input links ( 16 B, 17 A) and ( 16 B, 17 B) starting from the node 16 B are deleted from the input links generated by the second link generating unit 153 .

Next, how the input link L to the node 17 A is determined will be described. Since the node 17 A is a node corresponding to an OADM, the minimum value NOISEmin of the noise amount is 0 (step S 43 ). Only the input link ( 16 A, 17 A) is acquired as the input link to the node 17 A (step S 48 ).

The total noise amount when the input link ( 16 A, 17 A) is selected is calculated as NOISEacc( 16 A)+NOISE( 16 A, 17 A)+NOISEmin=0+1+0=1 (step S 50 ). Since this total noise amount is not larger than the threshold value 7 defined by NOISEth, the input link ( 16 A, 17 A) is not deleted (step S 52 ).

The total cost when the input link ( 16 A, 17 A) is selected is calculated as COSTacc( 16 A)+COST( 16 A, 17 A)=9+2=11 (step S 55 ). Since the input link ( 16 A, 17 A) is the only remaining input link, the input link ( 16 A, 17 A) is selected as the input link L to the node 17 A (step S 55 ).

The cost accumulated up to the node 17 A is calculated as COSTacc( 17 A)=COSTacc( 16 A)+COST( 16 A, 17 A)=9+2=11 (step S 56 ). Since the node 17 A is a node corresponding to an OADM, the noise NOISEacc( 17 A) accumulated up to the node 17 A is reset to 0 (step S 58 ).

The input link L to the node 17 B is determined in the following manner. Since the node 17 B is a node corresponding to an ILA, the path from the node 17 B to the node 18 A is chosen as the minimum noise path to the node located downstream of the node 17 B and capable of accommodating an OEO regenerator (step S 45 ), and the minimum value NOISEmin of the noise amount is set to 2 (step S 46 ). Only the input link ( 16 A, 17 B) is acquired as the input link to the node 17 B (step S 48 ).

The total noise amount when the input link ( 16 A, 17 B) is selected is calculated as NOISEacc( 16 A)+NOISE( 16 A, 17 B)+NOISEmin=0+2+2=4 (step S 50 ). Since the total noise amount when the input link ( 16 A, 17 B) is selected is not larger than the threshold value 7 defined by NOISEth, the input link ( 16 A, 17 B) is not deleted (step S 52 ).

The total cost when the input link ( 16 A, 17 B) is selected is calculated as COSTacc( 16 A)+COST( 16 A, 17 B)=9+1=10 (step S 55 ). Since the input link ( 16 A, 17 B) is the only remaining input link, the input link ( 16 A, 17 B) is selected as the input link L to the node 17 B (step S 55 ).

The cost accumulated up to the node 17 B is calculated as COSTacc( 17 B)=COSTacc( 16 A)+COST( 16 A, 17 B)=9+1=10 (step S 56 ). Since the node 17 B is a node corresponding to an ILA, the noise accumulated up to the node 17 B is calculated as NOISEacc( 17 B)=NOISEacc( 16 A)+NOISE( 16 A, 17 B)=0+2=2 (step S 60 ).

The input link L to the node 18 A is determined in the following manner. Since the node 18 A is an OADM capable of accommodating an OEO regenerator, the minimum value NOISEmin of the noise amount is 0 (step S 43 ). The input links ( 17 A, 18 A) and ( 17 B, 18 A) are acquired as the input links to the node 18 A (step S 48 ).

The total noise amount when the input link ( 17 A, 18 A) is selected is calculated as NOISEacc( 17 A)+NOISE( 17 A, 18 A)+NOISEmin=0+1+0=1 (step S 50 ). The total noise amount when the input link ( 17 B, 18 A) is selected is calculated as NOISEacc( 17 B)+NOISE( 17 B, 18 A)+NOISEmin=2+2+0=4 (step S 50 ). Since neither of these total amounts are larger than the threshold value 7 defined by NOISEth, neither the input link ( 17 A, 18 A) nor the input link ( 17 B, 18 A) is deleted (step S 52 ).

The total cost when the input link ( 17 A, 18 A) is selected is calculated as COSTacc( 17 A)+COST( 17 A, 18 A)=11+2=13 (step S 55 ). The total cost when the input link ( 17 B, 18 A) is selected is calculated as COSTacc( 17 B)+COST( 17 B, 18 A)=10+2=12 (step S 55 ). Accordingly, the input link ( 17 B, 18 A) that minimizes the total cost is selected as the input link L to the node 18 A (step S 55 ).

The cost accumulated up to the node 18 A is calculated as COSTacc( 18 A)=COSTacc( 17 B)+COST( 17 B, 18 A)=10+2=12 (step S 56 ). Since the node 18 A is a node corresponding to an OADM, the noise NOISEacc( 18 A) accumulated up to the node 18 A is reset to 0 (step S 58 ). In this way, the input links L to the respective nodes are sequentially selected.

Based on the starting point node of each input link supplied from the second link selecting unit 156 , the second node determining unit 157 depicted in FIG. 9 selects one of the nodes generated by the second node candidate generating unit 152 and thus determines one candidate for the optical transmission equipment to be placed at the corresponding station contained in the unit design section. The node selection process performed by the second node determining unit 157 is the same as that depicted in the flowchart of FIG. 17 .

FIG. 26 is a diagram illustrating the results of the relay node determination process performed by the second node determining unit 157 depicted in FIG. 9 . In FIG. 26 , the same parts as those depicted in FIGS. 20 to 22 and 25 are designated by the same reference characters, and the description of such parts will not be repeated here. In FIG. 26 , the thick arrows indicate the path of the nodes as traced by the respective steps depicted FIG. 17 . The kinds of optical transmission equipment determined by the respective steps are depicted at the bottom of the graph. The filled circle indicates a bypass.

First, the node number is set to indicate the node 18 A corresponding to the terminating station 18 in the unit design section 204 (step S 21 ), and the node 18 A is held as one of the relay nodes (step S 22 ). The input link ( 17 B, 18 A) is acquired as the input link L to the node 18 A (step S 23 ). Further, the node 17 B is acquired as the starting point node Npre of the input link ( 17 B, 18 A) (step S 24 ), and the node 17 B is held as one of the relay nodes (step S 25 ).

Next, the node number is set to indicate the node 17 B (step S 27 ), and the input link ( 16 A, 17 B) is acquired as the input link L to the node 17 B (step S 23 ). Further, the node 16 A is acquired as the starting point node Npre of the input link ( 16 A, 17 B) (step S 24 ), and the node 16 A is held as one of the relay nodes (step S 25 ).

Next, the node number is set to indicate the node 16 A (step S 27 ), and the input link ( 15 B, 16 A) is acquired as the input link L to the node 16 A (step S 23 ). Further, the node 15 B is acquired as the starting point node Npre of the input link ( 15 B, 16 A) (step S 24 ), and the node 15 B is held as one of the relay nodes (step S 25 ).

Next, the node number is set to indicate the node 15 B (step S 27 ), and the input link ( 14 B, 15 B) is acquired as the input link L to the node 15 B (step S 23 ). Further, the node 14 B is acquired as the starting point node Npre of the input link ( 14 B, 15 B) (step S 24 ), and the node 14 B is held as one of the relay nodes (step S 25 ).

Next, the node number is set to indicate the node 14 B (step S 27 ), and the input link ( 12 A, 14 B) is acquired as the input link L to the node 14 B (step S 23 ). Further, the node 12 A is acquired as the starting point node Npre of the input link ( 12 A, 14 B) (step S 24 ), and the node 12 A is held as one of the relay nodes (step S 25 ).

Next, the node number is set to indicate the node 12 A (step S 27 ), and the input link ( 11 A, 12 A) is acquired as the input link L to the node 12 A (step S 23 ). Further, the node 11 A is acquired as the starting point node Npre of the input link ( 11 A, 12 A) (step S 24 ), and the node 11 A is held as one of the relay nodes (step S 25 ).

Since the node number of the node 11 A is the node number of the optical transmission equipment placed at the originating station 11 in the unit design section 204 , the relay node determination process is terminated here. By tracing the input links backward from the node 18 A to the node 11 A in this way, the nodes 18 A, 17 B, 16 A, 15 B, 14 B, 12 A, and 11 A are held in this order as the relay nodes.

Based on the kinds of the relay nodes determined by the process depicted in FIG. 17 , the second node determining unit 157 determines the kinds of optical transmission equipment to be placed at the respective stations 11 to 18 . Based on the node 11 A, the second node determining unit 157 places an OADM at the station 11 . Further, based on the node 12 A, the second node determining unit 157 places an OADM at the station 12 .

Since there is no node corresponding to the station 13 , the second node determining unit 157 places a bypass at the station 13 . Based on the node 14 B, the second node determining unit 157 places an ILA at the station 14 . Based on the node 15 B, the second node determining unit 157 places an ILA at the station 15 . Based on the node 16 A, the second node determining unit 157 places an OADM at the station 16 . Based on the node 17 B, the second node determining unit 157 places an ILA at the station 17 . The second node determining unit 157 stores the thus determined optical transmission equipment configuration in the storage unit 126 as the optical transmission equipment configuration candidate for the unit design section 204 .

In step S 32 depicted in FIG. 19 , the additional candidate searching unit 128 searches for a new optical transmission equipment configuration candidate t′. The process that the additional candidate searching unit 128 performs to search for the optical transmission equipment configuration candidate t′ is the same as that described with reference to FIGS. 20 to 26 in which the initial candidate generating unit 125 determines the optical transmission equipment configuration.

However, in step S 55 , the third link selecting unit 166 in the additional candidate searching unit 128 selects as the input link L to the node Nx the input link that minimizes the sum of the amount of change, ΔRC, of the reduced cost accumulated up to the starting point node Ni and the amount of change, ΔRC, of the reduced cost of the input link.

Further, in step S 56 , the third link selecting unit 166 calculates the amount of change, ΔRCacc(Nx), of the reduced cost accumulated up to the node Nx as ΔRCacc(Nx)=ΔRCacc(Npre)+ΔRC(L). Symbol ΔRCacc(Npre) represents the amount of change, ΔRC, of the reduced cost accumulated up to the starting point node Npre of the input link L selected in step S 55 . ΔRC(L) represents the amount of change, ΔRC, of the reduced cost when the input link L is selected.

In step S 5 of FIG. 11 , the OEO regenerator placement determining unit 115 depicted in FIG. 7 determines the placement of the OEO regenerators in the optical transmission equipment configuration determined by the equipment configuration determining unit 124 . The design data output unit 116 outputs the design data that contains information concerning the optical transmission equipment configuration determined by the equipment configuration determining unit 124 and information concerning the placement of the OEO regenerators determined by the OEO regenerator placement determining unit 115 .

With the network design apparatus, network design program, and network design method according to the embodiment, it becomes possible to achieve a network design that can reduce the total cost needed for the placement of the optical transmission equipment and OEO regenerators. It also becomes possible to achieve a network design that considers the number of OEO regenerators that become necessary for each wavelength path.

All examples and conditional language recited herein are intended for pedagogical purposes to aid the reader in understanding the invention and the concepts contributed by the inventor to furthering the art, and are to be construed as being without limitation to such specifically recited examples and conditions, nor does the organization of such examples in the specification relate to a showing of the superiority and inferiority of the invention. Although the embodiment(s) of the present inventions have been described in detail, it should be understood that the various changes, substitutions, and alterations could be made hereto without departing from the spirit and scope of the invention.