Network design apparatus and network design method

Abstract

A network design apparatus includes: a first processing unit configured to select one or more paths between nodes in response to a request for a bandwidth between pairs of nodes in a network to determine working communication routes and protecting communication routes connecting the pairs of nodes, and estimate a number of communication lines in the selected path; and a second processing unit configured to allocate logical channels of the communication lines to the working communication routes and the protecting communication routes based on the requested bandwidth, wherein the first processing unit determines the protecting communication routes while permitting the sharing of the path, and the second processing unit allocates a common logical channel to one or more communication routes, out of the protecting communication routes, that share the path and are not simultaneously used when a failure occurs in the working communication routes.

What is claimed is: 
     
         1 . A network design apparatus comprising:
 a first processing unit configured to select one or more paths in response to a request for a bandwidth to determine working communication routes and protecting communication routes connecting pairs of nodes in a network, and estimate a number of communication lines established in each of the one or more paths selected, the one or more paths being configured between nodes in the network, the bandwidth being to be used for communications between the pairs of nodes; and   a second processing unit configured to allocate logical channels to the working communication routes and the protecting communication routes based on the requested bandwidth, the logical channels being included in each of the communication lines, wherein   the first processing unit determines the protecting communication routes while permitting the protecting communication routes to share the one or more paths, and   the second processing unit allocates a common logical channel out of the logical channels to one or more communication routes out of the protecting communication routes, the one or more communication routes sharing the one or more paths and being not simultaneously used when a failure occurs in at least one of the working communication routes.   
     
     
         2 . The network design apparatus according to  claim 1 , wherein
 the first processing unit estimates the number of the communication lines with respect to each of bandwidths of the communication lines, and   each of the communication lines includes as many the logical channels as correspond to the bandwidths of the communication lines.   
     
     
         3 . The network design apparatus according to  claim 1 , wherein
 the second processing unit adds, when a number of the logical channels to be allocated to the working communication routes or the protecting communication routes is insufficient, the communication line to a corresponding path out of the one or more path and performs allocation again.   
     
     
         4 . The network design apparatus according to  claim 1 , wherein
 the first processing unit estimates the number of the communication lines so that entire cost of the communication lines in the network is minimum according to:
 a first constraint condition for the working communication routes and the protecting communication routes to be respectively one working communication route and one protecting communication route selected from communication route candidates obtained by selection of the one or more paths; 
 a second constraint condition for a total bandwidth of the communication lines, with respect to each of the one or more paths, to be greater than or equal to a value that is obtained by adding a total bandwidth of communication routes including the path out of the working communication routes to a bandwidth shared by the protecting communication routes; and 
 a third constraint condition for a bandwidth shared by the protecting communication routes, with respect to each of the one or more paths, to be a total bandwidth of at least two communication routes out of the protecting communication routes, the at least two communication routes sharing the path and being simultaneously used when a failure occurs in at least one of the working communication routes. 
   
     
     
         5 . The network design apparatus according to  claim 1 , wherein
 the second processing unit allocates the logical channels to each of the protecting communication routes that share the one or more paths so that a number of the logical channels used in the network is minimum according to:
 a fourth constraint condition for the number of the logical channels allocated to each of the protecting communication routes to be a number matching the requested bandwidth; 
 a fifth constraint condition for the number of the communication lines used for each of the protecting communication routes to be one; and 
 a sixth constraint condition for a maximum number of the protecting communication routes using each of the logical channels to be one when a failure occurs in at least one of the working communication routes. 
   
     
     
         6 . A network design method executed by a computer, the network design method comprising:
 selecting one or more paths in response to a request for a bandwidth to determine working communication routes and protecting communication routes connecting pairs of nodes in a network; the one or more paths being configured between nodes in the network, the bandwidth being to be used for communications between the pairs of nodes;   estimating the number of communication lines established in each of the one or more paths selected; and   allocating logical channels to the working communication routes and the protecting communication routes based on the requested bandwidth, the logical channels being included in each of the communication lines, wherein   the estimating of the number of the communication lines includes determining the protecting communication routes while permitting the protecting communication routes to share the one or more paths;   the allocating of the logical channels includes allocating a common logical channel out of the logical channels to one or more communication routes out of the protecting communication routes, the one or more communication routes sharing the one or more paths and being not simultaneously used when a failure occurs in at least one of the working communication routes.   
     
     
         7 . The network design method according to  claim 6 , wherein
 the estimating of the number of the communication lines includes estimating the number of the communication lines with respect to each of bandwidths of the communication lines, and   each of the communication lines includes as many the logical channels as correspond to the bandwidths of the communication lines.   
     
     
         8 . The network design method according to  claim 6 , wherein
 the allocating of the logical channels includes adding the communication line to a corresponding path out of the one or more paths and performing allocation again when a number of the logical channels to be allocated to the working communication routes or the protecting communication routes is insufficient.   
     
     
         9 . The network design method according to  claim 6 , wherein
 the estimating of the number of the communication lines includes estimating the number of the communication lines so that entire cost of the communication lines in the network is minimum according to:
 a first constraint condition for the working communication routes and the protecting communication routes to be respectively one working communication route and one protecting communication route selected from communication route candidates obtained by selection of the one or more paths; 
 a second constraint condition for a total bandwidth of the communication lines, with respect to each of the one or more paths, to be greater than or equal to a value that is obtained by adding a total bandwidth of communication routes including the path out of the working communication routes to a bandwidth shared by the protecting communication routes; and 
 a third constraint condition for a bandwidth shared by the protecting communication routes, with respect to each of the one or more paths, to be a total bandwidth of at least two communication routes out of the protecting communication routes, the at least two communication routes sharing the path and being simultaneously used when a failure occurs in at least one of the working communication routes. 
   
     
     
         10 . The network design method according to  claim 6 , wherein
 the allocating of the logical channels includes allocating the logical channels to each of the protecting communication routes that share the one or more paths so that the number of the logical channels used in the network is minimum according to:
 a fourth constraint condition for the number of the logical channels allocated to each of the protecting communication routes to be a number matching the requested bandwidth; 
 a fifth constraint condition for the number of the communication lines used for each of the protecting communication routes to be one; and 
 a sixth constraint condition for a maximum number of the protecting communication routes using each of the logical channels to be one when a failure occurs in at least one of the working communication routes. 
   
     
     
         11 . A computer readable storage medium storing a network design program causing a computer to execute a process, the process comprising:
 selecting one or more paths in response to a request for a bandwidth to determine working communication routes and protecting communication routes connecting pairs of nodes in a network; the one or more paths being configured between nodes in the network, the bandwidth being to be used for communications between the pairs of nodes;   estimating the number of communication lines established in each of the one or more paths selected; and   allocating logical channels to the working communication routes and the protecting communication routes based on the requested bandwidth, the logical channels being included in each of the communication lines, wherein   the estimating of the number of the communication lines includes determining the protecting communication routes while permitting the protecting communication routes to share the one or more paths;   the allocating of the logical channels includes allocating a common logical channel out of the logical channels to one or more communication routes out of the protecting communication routes, the one or more communication routes sharing the one or more paths and being not simultaneously used when a failure occurs in at least one of the working communication routes.   
     
     
         12 . The computer readable storage medium according to  claim 11 , wherein
 the estimating of the number of the communication lines includes estimating the number of the communication lines with respect to each of bandwidths of the communication lines, and   each of the communication lines includes as many the logical channels as correspond to the bandwidths of the communication lines.   
     
     
         13 . The computer readable storage medium according to  claim 11 , wherein
 the allocating of the logical channels includes adding the communication line to a corresponding path out of the one or more paths and performing allocation again when a number of the logical channels to be allocated to the working communication routes or the protecting communication routes is insufficient.   
     
     
         14 . The computer readable storage medium according to  claim 11 , wherein
 the estimating of the number of the communication lines includes estimating the number of the communication lines so that entire cost of the communication lines in the network is minimum according to:
 a first constraint condition for the working communication routes and the protecting communication routes to be respectively one working communication route and one protecting communication route selected from communication route candidates obtained by selection of the one or more paths; 
 a second constraint condition for a total bandwidth of the communication lines, with respect to each of the one or more paths, to be greater than or equal to a value that is obtained by adding a total bandwidth of communication routes including the path out of the working communication routes to a bandwidth shared by the protecting communication routes; and 
 a third constraint condition for a bandwidth shared by the protecting communication routes, with respect to each of the one or more paths, to be a total bandwidth of at least two communication routes out of the protecting communication routes, the at least two communication routes sharing the path and being simultaneously used when a failure occurs in at least one of the working communication routes. 
   
     
     
         15 . The computer readable storage medium according to  claim 14 , wherein
 the allocating of the logical channels includes allocating the logical channels to each of the protecting communication routes that share the one or more paths so that the number of the logical channels used in the network is minimum according to:
 a fourth constraint condition for the number of the logical channels allocated to each of the protecting communication routes to be a number matching the requested bandwidth; 
 a fifth constraint condition for the number of the communication lines used for each of the protecting communication routes to be one; and 
 a sixth constraint condition for a maximum number of the protecting communication routes using each of the logical channels to be one when a failure occurs in at least one of the working communication routes.