Abstract:
A network management method provides optical performance and configuration management to satisfy user demands. Network information of the network is stored for retrieval and, when inputting a plurality of user demands each for a change of performance of the network, a modified design of the network is provided based on the network information to satisfy the user demands.

Description:
BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     The present invention generally relates to a network management system, and in particular to system and method which manage the network based on the capabilities and operation states of network components. 
     2. Description of the Related Art 
     There has been disclosed an example of a conventional network management system in Japanese Patent Unexamined Publication No. 8-328984. According to the conventional system, the network information regarding the capabilities and operation states of network components is collected from the existing network using a management protocol such as SNMP (Simple Network Management Protocol). The collected network information is stored onto a network database. In the case where the network is modified on demand, a simulation of the modified network is performed using the network database prior to actually making a modification to the existing network. In this manner, it can be determined in advance whether the simulation of the modified network provides the expected performance. If the modified network is good in the simulation, the modification is made to the existing network. 
     However, if the simulation of the modified network does not provide acceptable performance, it is necessary for a network manger to redesign the modification of the network and then to perform the simulation of the redesigned network again. This is a time-consuming and inefficient procedure. 
     SUMMARY OF THE INVENTION 
     An object of the present invention is to provide network management system and method which can automatically perform the redesign of a network in response to user&#39;s demands, 
     Another object of the present invention is to provide management system and method which can automatically produce an optimal plan for updating the settings of network components. 
     According to the present invention, network information of the network is stored for retrieval and, when inputting a plurality of demands each for a change of performance of the network, a modified design of the network is provided based on the network information to satisfy the demands. 
     An initially-modified design of the network may be produced by determining a minimum-cost route for each of the demands, end then the initially-modified design may be optimized to produce the modified design by changing the minimum-cost route for each of the demands so that cost of modification of the network is minimized as a whole. 
     Since the modified design of the network is provided based on the network information to satisfy the demands, optimal performance and configuration management to satisfy the demands can be automatically obtained. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a block diagram showing a network management system according to a first embodiment of the present invention; 
     FIG. 2 is a diagram showing a schematic configuration of a network for explanation an operation of the embodiment; 
     FIG. 3A is a diagram showing a cost function with respect of required bandwidth for each link connecting two adjacent nodes; 
     FIG. 3B is a diagram showing a cost function with respect of increase in bandwidth in the case where a 7-Gbps switch or a 20-Gbps switch is introduced to a node in place of a 5-Gbps switch; 
     FIG. 4 is a flow chart showing a schematic operation of the network designation section 
     FIG. 5 is a flow chart showing an initial determination routine performed by the network designing section; 
     FIG. 6 is a flow chart showing a route optimization routine performed by the network designing section; 
     FIG. 7 is a block diagram showing a network management system according to a second embodiment of the present invention; 
     FIG. 8 is a block diagram showing a network management system according to a third embodiment of the present invention; and 
     FIG. 9 is a block diagram showing a network management system according to a fourth embodiment of the present invention. 
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     Referring to FIG. 1, a network management system  10  according to an embodiment of the present invention collects performance and other information about the existing network  20  or about particular nodes on the network  20 . Further, the network management system  10  performs network redesigning on user demands and network information installation as will be described hereinafter. 
     The network management system  10  is provided with a network information collecting section  101  which collects at least information required for network redesigning from the existing network  20  or particular nodes on the network  20 . The network information includes configuration information, that is, states, settings, capabilities about nodes and links and topology information and may further include traffic information indicating the level of network activity in the network  20  or in each link. The collected network information is stored onto a network database  102  for later retrieval. 
     The network management system  10  is further provided with a network designing section  103  which inputs the collected network information from the network database  102  and redesigns the network so as to satisfy the user demands received from the user interface  105 . The network designing section  103  may be comprised of a program-controlled processor, a read-only memory storing a network designing program, and a memory for storing input user demands, network information and other information. These circuit blocks are not shown in FIG.  1 . 
     The modified network information including modified settings, capabilities and other data about nodes and links is stored onto the network database  102  and a modified network information installation section  104  writes or installs the modified network information into nodes of the network  20 . 
     Since the network information collecting section  101  and the modified network information installation section  104  have been known, the details are omitted. The user interface  105  may be comprised of an input device, a monitor for displaying necessary information, and other devices. The input device is used to input various instructions such as network information collecting instruction, network information installation instructions, network designing instruction and further to input user demands. 
     As shown in FIG. 2, consider for simplicity that a network consisting of four nodes NODE 1 -NODE 4  is operating kith initial settings of the nodes. For example, in the case of occurrence of a demand D( 1 , 4 ) specifying two nodes NODE 1  and NODE 4  and a requested bandwidth it is necessary to modify the settings and capabilities of nodes and links of a selected route between NODE 1  and NODE 4  to allow communications of the requested bandwidth. Such modification causes an increase in cast for each node and link. As shown in FIG. 2, a cost increase of a NODE( 1 ) is indicated by ΔC( i ) and a cost increase of a LINK( i,j ) between NODE( i ) and NODE( j ) is indicated by ΔC( i,j ). The details of cost increase will be described hereinafter. 
     Referring to FIG. 3A, consider that NODE( i ) and NODE( j ) are provided with a switch having a capacity of bandwidth W D  and then a bandwidth W D  wider than W 0  is demanded of that node. To satisfy the requirement of the bandwidth W D , the NODE( i ) and NODE( j ) must be upgraded to at least the capacity of bandwidth W D . Introducing the higher-capacity switch causes a node cost increase indicated by ΔC=ΔC(i)+ΔC( j ) according to a cost curve  301 . 
     In general, since it is the same with a LINK( i,j ) between them, a cost increase is indicated by ΔC=ΔC( i ) +ΔC( j )+ΔC( i,j ). In the case where one of the nodes has already satisfied the demand, the corresponding cost increase ΔC( i ) or ΔC( j ) is zero. Similarly, when the link has already satisfied the demand, the corresponding cost increase ΔC( i,j ) is zero. 
     To describe more specifically, assuming that the node is equipped with a 5-Gbps switch and the capacity of the node can be upgraded to 7-Gbps or 20-Gbps by replacing the 5-Gbps switch with the 7-Gbps or 20-Gbps snitch or by adding an extended module to the 5-Gbps switch. And further assuming that a bandwidth of 3 Gbps has been occupied, resulting in an available bandwidth of 2 Gbps left in that node. 
     In this case, as shown in FIG. 3B, the node can accommodate an increase in bandwidth up to 2 Gbps without the need of additional cost. When a bandwidth increase due to the demand is more than 2 Gbps and not more than 4 Gbps, the 7-Gbps switch is introduced to the node, so that the cost increases to the introduction cost C 7C . When a bandwidth increase due to the demand is more than 4 Gbps and not more than 17 Gbps, the 20-Gbps switch is introduced to the node, so that the cost further increases to the introduction cost C 20G . Therefore, the cost function for each node is a step-like function  302  depending on the existing capacity and activity of the node. 
     As described before, in the case of the demand D( 1 , 4 ) as shown in FIG. 2, there are four possible route candidates as follows: 
     1) first route candidate: NODE 1 -NODE 2 -NODE 3 -NODE 4 , 
     2) second route candidate: NODE 1 -NODB 2 -NODE 4 . 
     3) third route candidate: NODE 1 -NODB 3 -NODB 4 , and 
     4) fourth route candidate: NODE 1 -NODE 3 -NODE 2 -NODE 4 . 
     Among the four possible route candidates, an optimal route is selected with respect to cast increase. Assuming that a cost increase in two adjacent nodes NODE( i ) and NODE( j ) and the LINK( i,j ) is represented by ΔC=ΔC( i )+ΔC( j )+ΔC( i,j ) and a network cost increase in all nodes included in a selected route for each demand D I  is represented by ΔC NT  and, the first route candidate costs a network cost increase ΔC NT1 =ΔC( 1 )+ΔC( 2 )+ΔC( 3 )+ΔC( 4 )+ΔC( 1 , 2 )+ΔC( 2 , 3 )+ΔC( 3 , 4 ), the second route candidate costs a network cost increase ΔC NT2 =ΔC( 1 )+ΔC( 2 )+ΔC( 4 )+ΔC( 1 , 2 )+ΔC( 2 , 4 ), the third route candidate costs a network cost increase ΔC NT3 =ΔC( 1 )+ΔC( 3 )+ΔC( 4 )+ΔC( 1 , 3 )+ΔC( 3 , 4 ), and the fourth route candidate costs a network cost increase ΔC NT4 =ΔC( 1 )+DG( 3 )+ΔC( 2 )+ΔC( 4 )+ΔC( 1 , 3 )+ΔC( 2 , 3 )+ΔC( 2 , 4 ). 
     There is selected an optimal route having the minimum network cost increase. Far example, when the second route candidate is the optimal route, the respective settings and capabilities of NODE 1 , NODE 2  and NODE 4  and LINK( 1 , 2 ) and LINK( 2 , 4 ) are modified to allow communications of the requested bandwidth. Such an optimal route can be searched for using well-known Dijkstra algorithm (see “Algorithms” written by Robert Sedgewick, second edition, Addison Weslep, pp.461-465). 
     NETWORK DESIGNING 
     The network designing section  103  inputs the collected network information from the network database  102  and redesigns the network so as to satisfy the user demands. The minimum cost route is obtained by solving a kind of minimum cost flow problem in a network. Therefore, even though the respective optimal routes satisfying a plurality of demands are obtained, a combination of the optimal routes is not always the optimal solution for the whole network. Then, according to the present invention, the network designing section  103  first performs a local minimum cost route determination procedure and then n whole-network-minimum cost route determination procedure. 
     Referring to FIG. 4, upon receipt of N user demands D 1 -D N  from the user interface  105 , the network designing section  103  performs an initial determination procedure which determines the minimum-cost route fat each demand which is selected in decreasing order of requested bandwidth (step  501 ). 
     Subsequently, the network designing section  103  performs a route optimization procedure which optimizes the initially-determined routes so that the total network cost increase is reduced to the minimum value (step S 402 ). As will be describer a network cost increase is minimized by removing each demand from the network and determining a minimum-cost route for the removed demand in the state of the network from which the demand has been removed. Thereafter, if it is determined whether the total network cost increase is minimized and, if it is not minimized, the route optimization steps are repeatedly performed until the total network cost increase is minimized. In this manner, the optimal modification of the network information can be obtained. The details will be described hereinafter. 
     INITIAL DETERMINATION 
     Referring to FIG. 5, when receiving N user demands D 1 -D N  from the user interface  105 , the network designing section  103  stores the N user demands D 1 -D N  onto a memory and sorts them in decreasing order of requested bandwidth to produce the sorted demands D (0)   1 -D (0)   N  (step S 501 ). After a variable I is initialized (step S 502 ), a demand D (0)   I  is read from the memory (step S 503 ) and then cost increases ΔC (0)   I  of possible route candidates which would be caused by the selected demand D (0)   I  are calculated as described before referring to FIG.  2  and FIGS. 3A and 3B (step S 504 ). Among the possible route candidates, the minimum-cost increase route R (0)   I  is searched for as an optimal route using the Dijkstra algorithm (step S 505 ). 
     Thereafter, the settings of the nodes and links forming the minimum-cost increase route R (0)   I  are modified to satisfy the demand D (0)   I  (step S 506 ). The initially-modified network information is temporarily stored onto the memory. It is determined whether the variable I reaches N (step S 507 ) and, if not, the variable I is incremented by one (step S 508 ), then control goes back to the step S 503 . The stops S 503 -S 508  are repeatedly performed until the variable I reaches N (YES in step S 507 ). In this manner, the initially-modified network information including the respective minimum-cost increase routes R (0)   1 -R (0)   N  for all the sorted demands D (0)   1 -D (0)   N  are obtained and stored in the memory. 
     ROUTE OPTIMIZATION 
     Subsequently, the network designing section  103  performs the route optimization procedure which optimizes the initially-determined routes R (0)   1 -R (0)   N  so that the total network cost increase is minimized. 
     First, the network designing section  103  sorts the N user demands in a different way from the step S 501  of the initial determination procedure. After a variable I is initialized (step S 601 ), a demand D I  is read from the memory (step S 602 ). Then the network deigning section  103  removes the demand D I  from the initially-modified network information stored in the memory and calculates a network cast decrease ΔC NT (I), which would be caused by removing the selected demand D I  (step S 603 ). It is determined whether the variable I reaches N (step S 604 ) and, if not, the variable I is incremented by one (step S 605 ), then control goes back to the step S 602 . The steps S 602 -S 605  are repeatedly performed until the variable I reaches N (YES in step S 604 ). 
     In this manner, the respective network cost decreases C NT ( 1 )−ΔC NT   (N)  for all the demands D 1 -D N  are obtained. Thereafter, the network designing section  103  sorts the N user demands D 1 -D N  in decreasing order of network cost decrease to produce the sorted demands D (1)   1 -D (1)   N  (step S 606 ). 
     Subsequently, after a variable I is initialized (step S 607 ). a demand D (1)   I  is read from the memory. Then the bandwidths and other settings of the nodes and links associated with the demand D (1)   I  are removed from the initially-modified network information to produce a changed network information (step S 608 ). Under this condition, the demand D (1)   I  is input again. As described before, cost increases ΔC (1)   I  of possible route candidates which would be caused by the demand D (1)   I  are calculated (step S 609 ). Among the possible route candidates, the minimum-cost increase route R (1)   I  is searched for as an optimal route using the Dijkstra algorithm (step S 610 ). 
     Thereafter, the settings of the nodes and links forming the minimum-cost increases route R (1)   I  are modified to satisfy the demand D (1)   I  and the modified network information is stored onto the memory (step S 611 ). It is determined whether the variable I reaches N (step S 612 ) and, if not, the variable I is incremented by one (step S 613 ), then control goes back to the step S 608 . The steps S 608 -S 613  are repeatedly performed until the variable I reaches N (YES in step S 612 ). In this manner, the modified network information including the respective minimum-cost increase routes R (1)   1 -R (1)   N  for all the sorted demands D (1)   1 -D (1)   N  are obtained and stored in the memory. 
     Thereafter, if the variable I reaches N (YES in step S 612 ). then it is determined whether the total network cost increase is minimized (step S 614 ) and the route optimization steps S 601 -S 613  are repeatedly performed until the total network cost increase is minimized. In this manner, the optimal modification of the network information can be obtained and the modified network information is output to the network database  102 . 
     Variations of the network management system  10  are shown in FIGS. 7-9 In FIG. 7, the system  10  is provided with a controller  701  which controls the network information collecting section  101 , the network database  102 , the network designing section  103 , and the network information installation section  104 . Further the controller  701  is provided with a communication means for communicating the existing network  20 . Since the functions and operations of these sections are the same as in FIG. 1, the descriptions are omitted. 
     In FIG. 8, the system  10  has the same configuration as in FIG. 1 but the network information installation section  104 . In this embodiment the network information installation is performed offline. Contrarily, the system  10  as shown in FIG. 9, the system  10  has the same configuration as in FIG. 1 but the network information collecting section  101 . In this embodiment, the network information of the existing network  20  is collected offline.