JP7587188B2 - NETWORK MANAGEMENT DEVICE, NETWORK MANAGEMENT METHOD AND PROGRAM - Google Patents

Description

The present invention relates to a network management device, a network management method and a program.

Non-Patent Document 1 discloses a technique for calculating redundant routes to improve network reliability. According to Non-Patent Document 1, the primary route and the redundant route are two routes that have the same sending and receiving nodes and do not have a common relay node. Of the two routes, the one with the shorter route length is the primary route, and the one with the longer route length is the redundant route. If the primary route and the redundant route have overlapping relay nodes, both the primary route and the redundant route cannot be used if a failure occurs in the relay node. However, by not having overlapping relay nodes, the reliability of the redundant route against failures in the primary route can be increased.

R. Bhandari, “Optimal Physical Diversity Algorithms and Survivable Networks”, IEEE Conference Paper, pp. 433-441

When the technology described in Non-Patent Document 1 is applied to a communication network, the difference in path length between the primary path and the redundant path may become large depending on the combination of transmitting and receiving nodes. One of the reasons for this is that the communication network is not a complete graph, and the selectable edges are limited. If the path length difference is large, communication performance will decrease when the communication path is switched from the primary path to the redundant path. Therefore, it is desirable to identify combinations of transmitting and receiving nodes for which the decrease in communication performance due to the path length difference between the primary path and the redundant path is relatively large, and to modify the network so that an appropriate redundant path can be configured.

The object of the present invention is to provide a network management device, a network management method, and a program that can identify pairs of transmitting and receiving nodes in a communication network that experience a degradation in communication performance when switching from a primary path to a redundant path.

One aspect of the present invention is a network management device that manages a communication network having a plurality of nodes and a plurality of edges connecting the nodes, and includes a route identification unit that identifies, for each node pair that is a pair of nodes on the communication network, a main route and a redundant route that are composed of the plurality of edges and connect the node pair, where a relay node on the main route does not overlap with a relay node on the redundant route; a route length difference calculation unit that calculates the route length difference between the main route and the redundant route for each of the node pairs; and an extraction unit that extracts outlying pairs of node pairs that will experience a decrease in communication performance when switched from the main route to the redundant route based on the route length difference.

One aspect of the present invention is the above-mentioned network management device, which includes an additional edge identification unit that identifies an additional edge that is not included in the communication network and that, when added to the communication network, suppresses a decrease in communication performance when switching from the main path to the redundant path in the lost pair, and the path identification unit identifies, for a plurality of candidate edges that are candidates for the additional edge, the main path and the redundant path for each of the lost pairs when the candidate edges are added to the communication network, and the additional edge identification unit identifies, among the plurality of candidate edges, the edge that has the smallest index value related to the path length difference of the lost pair as the additional edge.

In one aspect of the present invention, in the above-mentioned network management device, the extraction unit extracts the outlying pairs by statistical processing based on a combination of the path length difference and the distance between the node pairs.

One aspect of the present invention is a network management method for managing a communication network having a plurality of nodes and a plurality of edges connecting the nodes, the method comprising the steps of: for each node pair, which is a pair of nodes on the communication network, identifying a main path and a redundant path that are composed of the plurality of edges and connect the node pair, and in which a relay node on the main path does not overlap with a relay node on the redundant path; determining a path length difference between the main path and the redundant path for each of the node pairs; and extracting outlying pairs of node pairs that would experience a degradation in communication performance when switched from the main path to the redundant path based on the path length difference.

One aspect of the present invention is a program that causes a computer managing a communication network having a plurality of nodes and a plurality of edges connecting the nodes to execute the steps of: identifying, for each node pair that is a pair of nodes on the communication network, a main path and a redundant path that are composed of the plurality of edges and connect the node pair, where a relay node on the main path does not overlap with a relay node on the redundant path; determining a path length difference between the main path and the redundant path for each of the node pairs; and extracting outlying pairs of node pairs that would experience a degradation in communication performance when switched from the main path to the redundant path based on the path length difference.

According to at least one of the above aspects, it is possible to identify node pairs in a communication network that experience a degradation in communication performance when switching from a primary path to a redundant path.

FIG. 2 is a diagram illustrating an example of a primary path and a redundant path according to the first embodiment; 1 is a schematic block diagram showing a configuration of a network management device according to a first embodiment. 4 is a flowchart showing the operation of the network management device according to the first embodiment. FIG. 1 is a diagram illustrating an example of the distribution of path length differences between node pairs in a communication network. 11 is a diagram showing an example of the distribution of path length differences between node pairs when an additional edge is determined by the method according to the first embodiment; FIG. FIG. 1 is a schematic block diagram illustrating a configuration of a computer according to at least one embodiment.

First Embodiment
Hereinafter, the embodiments will be described in detail with reference to the drawings.
The network management device 1 according to the first embodiment manages a communication network.
1 is a diagram showing an example of a primary route Rp and a redundant route Rs according to the first embodiment. The communication network is composed of a plurality of nodes N and edges E connecting the nodes N. The nodes of the communication network according to the first embodiment communicate with each other via the primary route Rp under normal circumstances, and when a failure occurs in the primary route Rp, they communicate by switching to the redundant route Rs.

The primary route Rp and the redundant route Rs do not have a common relay node. A relay node is a node that constitutes a route, excluding the transmitting node and the receiving node. Of the two routes, the one with the shorter route length is the primary route Rp, and the one with the longer route length is the redundant route Rs. The communication network shown in FIG. 1 has six nodes N, from node N1 to node N7. In this communication network, when the transmitting node is N1 and the receiving node is N7, the shortest route is the route that connects N1, N2, N3, and N7 in that order. However, this shortest route cannot be used as the primary route Rp because it is not possible to configure a redundant route Rs that does not have a common relay node. In the example shown in FIG. 1, the route that connects N1, N4, N3, and N7 in that order is the primary route Rp, and the route that connects N1, N2, N6, N5, and N7 in that order is the redundant route Rs.

If the difference in path length between the primary path Rp and the redundant path Rs is large, the communication performance will be degraded when the communication path is switched from the primary path Rp to the redundant path Rs. In order to reduce the difference in path length, it is necessary to add an edge to the communication network. For example, in the example shown in FIG. 1, the redundant path Rs passes through node N6, which is relatively far from other nodes N, so the path length of the redundant path Rs is longer than that of the primary path Rp. In contrast, by adding an edge connecting node N2 and node N5, the redundant path Rs becomes a path connecting N1, N2, N5, and N7, and the path length of the redundant path Rs can be shortened. On the other hand, large-scale construction is required to add an edge to the communication network. Therefore, the network management device 1 according to the first embodiment determines an appropriate additional edge so that the quality of multiple paths with low communication performance is improved. In other words, the network management device 1 identifies the minimum additional edge that improves the communication performance of the entire communication network.

Configuration of network management device 1
2 is a schematic block diagram showing the configuration of the network management device 1 according to the first embodiment. The network management device 1 includes a request receiving unit 11, a network database 12, a node pair identifying unit 13, a path identifying unit 14, a path length difference calculating unit 15, an extracting unit 16, a candidate edge identifying unit 17, an index value calculating unit 18, and an additional edge determining unit 19.

The request receiving unit 11 receives a request for improvement of the communication network. The improvement request includes the ID of the communication network to be improved. The network management device 1 starts the process of determining an additional edge in response to the reception of the improvement request.

For each communication network, the network database 12 stores information on the nodes and edges that make up that communication network. For example, the network database 12 stores the latitude and longitude of each node, and the start node, end node, and length of each edge. In addition, the network database 12 stores information on edges that should not be added (prohibited edges) for each communication network. Examples of prohibited edges include edges that are expensive to add, such as edges that connect nodes separated by mountain ranges.

The node pair identification unit 13 identifies all combinations of transmitting nodes and receiving nodes (node pairs) from the multiple nodes that constitute the communication network based on the information stored in the network database 12.

The path specification unit 14 specifies a primary path Rp and a redundant path Rs that connect the node pairs specified by the node pair specification unit 13. As shown in Fig. 1, the primary path Rp and the redundant path Rs are two paths that have the same sending node and receiving node and do not have a common relay node. The path specification unit 14 specifies the primary path Rp and the redundant path Rs so that the sum of the path lengths of the primary path Rp and the redundant path Rs is minimized, for example.
The path identification unit 14 can identify the primary path Rp and the redundant path Rs by, for example, the method described in Non-Patent Document 1.

The path length difference calculation unit 15 calculates the path length of each of the primary path Rp and the redundant path Rs identified by the path identification unit 14, and the path length difference between the primary path Rp and the redundant path Rs. The path length may be calculated, for example, by the sum of the lengths associated with the edges that make up the path, or by the sum of the distances between the relay nodes that make up the path. The distance between nodes can be calculated from the latitude and longitude of the nodes.

The extraction unit 16 extracts outlier pairs, which are node pairs with a relatively large path length difference, based on the path length and path length difference calculated by the path length difference calculation unit 15. For example, the extraction unit 16 extracts outlier pairs in the following procedure. First, the extraction unit 16 sets the sum of path lengths and the path length difference as attributes of multiple node pairs. Next, the extraction unit 16 generates a discrimination boundary that identifies a normal class using a one-class SVM (Support Vector Machine). At this time, the extraction unit 16 extracts node pairs that are closer to the origin than the set discrimination boundary as outlier pairs. Note that the extraction unit 16 according to another embodiment may extract outlier pairs using a method other than SVM. For example, the extraction unit 16 according to another embodiment may learn a Gaussian mixture model that represents the distribution of path length differences based on node pairs, and extract outlier pairs by comparing with the Gaussian mixture model.

The candidate edge identification unit 17 identifies multiple candidate edges that are candidates for edges to be added to the communication network based on the information stored in the network database 12. The candidate edge identification unit 17 identifies, as a group of candidate edges, the edges that constitute a complete graph made up of the group of nodes that constitute the communication network, excluding edges that already exist in the communication network and prohibited edges.

The index value calculation unit 18 calculates an index value indicating the degree of degradation in communication performance when switching from the primary route Rp to the redundant route Rs for the multiple out-of-band pairs extracted by the extraction unit 16. The index value serves as an index for optimizing communication performance. The index value is calculated by taking the root mean square of the route length differences for the multiple out-of-band pairs extracted by the extraction unit 16.

The additional edge determination unit 19 identifies the candidate edge identified by the candidate edge identification unit 17 that has the smallest index value as the additional edge.

<<Operation of the network management device 1>>
FIG. 3 is a flowchart showing the operation of the network management device 1 according to the first embodiment.
When a communication network manager wishes to consider improving the performance of a communication network, he or she sends an improvement request to the network management device 1. When the request receiving unit 11 of the network management device 1 receives a communication network improvement request, the node pair identifying unit 13 reads information related to the network to be improved from the network database 12 based on the ID of the communication network included in the improvement request (step S1). The node pair identifying unit 13 identifies all combinations of transmitting nodes and receiving nodes (node pairs) from all nodes constituting the network (step S2). The network management device 1 selects each of the identified node pairs (step S3) and performs the following calculations in steps S4 and S5 for the selected node pairs.

The route identification unit 14 identifies the primary route Rp and the redundant route Rs connecting the transmitting node and the receiving node for the node pair selected in step S3 (step S4). The route length difference calculation unit 15 calculates the route lengths of the primary route Rp and the redundant route Rs identified in step S4 and the route length difference between the primary route Rp and the redundant route Rs (step S5).

After calculating the path length and path length difference for each node pair, the extraction unit 16 uses the sum of the path lengths and the path length difference as attributes to identify a classification boundary for identifying a normal class using a one-class SVM (step S6). The extraction unit 16 extracts, from among the node pairs identified in step S2, those closer to the origin than the set classification boundary as outlier pairs (step S7).

The candidate edge identification unit 17 identifies multiple candidate edges that are candidates for edges to be added to the communication network based on the information stored in the network database 12 (step S8). The network management device 1 selects the multiple candidate edges identified in step S8 one by one (step S9) and performs the following calculations of steps S10 to S13 for each candidate edge.

The network management device 1 selects each of the multiple outlier pairs extracted in step S7 (step S10), and performs the following calculations in steps S11 and S12 for each outlier pair. The route identification unit 14 identifies the primary route Rp and the redundant route Rs that connect the outlier pairs selected in step S10 for the candidate network obtained by adding the candidate edge selected in step S9 to the communication network read in step S1 (step S11). The route length difference calculation unit 15 calculates the respective route lengths of the primary route Rp and the redundant route Rs identified in step S11, and the route length difference between the primary route Rp and the redundant route Rs (step S12).

After calculating the path length and path length difference for each outlier pair, the index value calculation unit 18 calculates the root mean square of the path length differences of the multiple outlier pairs calculated in step S12 as an index value (step S13).

The additional edge determination unit 19 identifies, from among the candidate edges identified in step S8, the edge with the smallest index value calculated in step S13 as the additional edge (step S14). The additional edge determination unit 19 displays the identified additional edges on a terminal operated by the manager of the communication network. At this time, the additional edge determination unit 19 may display the distribution of path length differences in the current communication network and the distribution of path length differences in the communication network when the additional edge is added so that they can be compared. For example, the additional edge determination unit 19 may show the degree of improvement by superimposing and displaying the graphs in Figures 4 and 5 described below.

<<Example>>
FIG. 4 is a diagram showing an example of the distribution of path length differences between node pairs in a communication network.
FIG. 4 is a graph in which the horizontal axis represents the path length difference of node pairs, and the vertical axis represents the frequency and cumulative relative frequency of the path length difference. In the example shown in FIG. 4, the path length difference has a distribution close to a log-normal distribution. On the other hand, in the example shown in FIG. 4, it can be seen that node pairs with long path length differences are scattered. According to the network management device 1 according to the first embodiment, such node pairs are extracted as out-of-range pairs. From the example shown in FIG. 4, it can be seen that in such out-of-range pairs, when switching between the primary route Rp and the redundant route Rs occurs, deterioration of communication performance occurs. The network management device 1 according to the first embodiment can change the communication network so that the out-of-range pairs have a path length difference according to the distribution by determining an additional edge so that the root mean square of the path length difference of such out-of-range pairs is small.

Figure 5 is a diagram showing an example of the distribution of the path length difference of node pairs when an additional edge is determined by the method according to the first embodiment. In the example shown in Figure 5, it can be seen that the number of outlier pairs seen in Figure 4 has decreased. In this way, according to the first embodiment, the quality of the entire communication network can be improved by determining an additional edge so that the communication performance of the outlier pairs is improved. In particular, the network management device 1 can reduce the amount of calculation related to the process of determining the additional edge by limiting the calculation of the primary path Rp and the redundant path Rs when a candidate edge is added to the outlier pairs. In addition, the network management device 1 can determine the additional edge so that the outlier pairs are actively eliminated by limiting the calculation target of the index value to the outlier pairs. When the index value is calculated based on all node pairs, there is a possibility that an additional edge that reduces the path length difference of the outlier pairs and already follows the distribution is obtained.

<Action and Effects>
In this way, the network management device 1 according to the first embodiment extracts deviating pairs based on the path length difference between the primary path Rp and the redundant path Rs for each node pair on the communication network. This allows the network management device 1 to identify which nodes in the communication network experience a decrease in communication performance. In other words, the network management device 1 can identify node pairs for which a decrease in communication performance occurs when switching from the primary path Rp to the redundant path Rs.

In addition, the network management device 1 according to the first embodiment identifies, for each of a plurality of candidate edges, the primary route Rp and the redundant route Rs for each of the losing pairs when the candidate edge is added to the communication network, and identifies the candidate edge that has the smallest index value for the path length difference of the losing pair as the additional edge. The additional edge identified by this method is an edge that contributes greatly to shortening the path length difference of the losing pair. This allows the network management device 1 to determine the additional edge so as to proactively eliminate losing pairs.

In addition, the network management device 1 according to the first embodiment extracts outlier pairs by SVM using a combination of the path length difference and the sum of the path lengths as elements. The sum of the path lengths of the main path Rp and the redundant path Rs is a value according to the distance between the node pairs. The path length difference between the main path Rp and the redundant path Rs varies depending on the distance between the node pairs. The redundant path Rs has a constraint that it does not include the same relay node as the main path Rp that connects the node pairs by the shortest path. Therefore, the longer the distance between the node pairs, the longer the length of the redundant path Rs may be. Therefore, by finding outliers using a combination of the path length difference and the sum of the path lengths as elements, it is possible to prevent those whose path length difference becomes longer depending on the distance between the node pairs from becoming outliers.

Other Embodiments
Although one embodiment has been described in detail above with reference to the drawings, the specific configuration is not limited to the above, and various design changes are possible. That is, in other embodiments, the order of the above-mentioned processes may be changed as appropriate. Also, some of the processes may be executed in parallel.
The network management device 1 according to the above-described embodiment may be configured as a single computer, or the configuration of the network management device 1 may be distributed across multiple computers, and the multiple computers may work together to function as the network management device 1.

The network management device 1 according to the embodiment described above identifies multiple outlier pairs that are node pairs with low communication performance and determines appropriate additional edges to improve the quality of the multiple outlier pairs, but is not limited to this. For example, the network management device 1 according to another embodiment may extract and present outlier pairs in a communication network, but not determine additional edges.

The network management device 1 according to the embodiment described above extracts outlier pairs by performing statistical processing such as SVM using the sum of the path lengths of the primary path Rp and the redundant path Rs as an element, but is not limited to this. For example, in other embodiments, other values according to the distance between the node pairs, such as the number of hops between the node pairs or the straight-line distance between the nodes, may be used as elements. Furthermore, the network management device 1 according to other embodiments may extract outlier pairs based only on the path length, without using a value according to the distance between the node pairs.

The network management device 1 according to the above-described embodiment stores information related to the network configuration in advance in the network database 12, but is not limited to this. For example, the network management device 1 according to other embodiments may not have the network database 12 when receiving an improvement request that includes data related to the communication network to be improved.

Computer Configuration
FIG. 6 is a schematic block diagram illustrating a computer configuration according to at least one embodiment.
The computer 90 comprises a processor 91 , a main memory 93 , a storage 95 , and an interface 97 .
The above-mentioned network management device 1 is implemented in a computer 90. The operations of each of the above-mentioned processing units are stored in the form of a program in a storage 95. The processor 91 reads the program from the storage 95, loads it in the main memory 93, and executes the above-mentioned processing in accordance with the program. The processor 91 also secures storage areas in the main memory 93 corresponding to each of the above-mentioned storage units in accordance with the program. Examples of the processor 91 include a CPU (Central Processing Unit), a GPU (Graphic Processing Unit), and a microprocessor.

The program may be for realizing part of the functions to be performed by the computer 90. For example, the program may be for realizing the functions by combining with other programs already stored in the storage or by combining with other programs implemented in other devices. In another embodiment, the computer 90 may be provided with a custom LSI (Large Scale Integrated Circuit) such as a PLD (Programmable Logic Device) in addition to or instead of the above configuration. Examples of PLDs include PAL (Programmable Array Logic), GAL (Generic Array Logic), CPLD (Complex Programmable Logic Device), and FPGA (Field Programmable Gate Array). In this case, part or all of the functions realized by the processor 91 may be realized by the integrated circuit. Such an integrated circuit is also included as an example of a processor.

Examples of storage 95 include a magnetic disk, a magneto-optical disk, an optical disk, a semiconductor memory, and the like. Storage 95 may be an internal medium directly connected to the bus of computer 90, or an external medium connected to computer 90 via interface 97 or a communication line. In addition, when this program is distributed to computer 90 via a communication line, computer 90 that receives the program may expand the program in main memory 93 and execute the above-mentioned processing. In at least one embodiment, storage 95 is a non-transitory tangible storage medium.

The program may be for realizing part of the above-mentioned functions. Furthermore, the program may be a so-called differential file (differential program) that realizes the above-mentioned functions in combination with another program already stored in storage 95.

1...Network management device 11...Request receiving unit 12...Network database 13...Node pair identification unit 14...Path identification unit 15...Path length difference calculation unit 16...Extraction unit 17...Candidate edge identification unit 18...Index value calculation unit 19...Additional edge determination unit E...Edge N...Node Rp...Primary path Rs...Redundant path

Claims (5)

A network management device that manages a communication network having a plurality of nodes and a plurality of edges connecting the nodes,
a route specifying unit that specifies, for each node pair on the communication network, a main route and a redundant route that are configured with the plurality of edges and connect the node pair, and in which a relay node on the main route and a relay node on the redundant route do not overlap;
a path length difference calculation unit that calculates a path length difference between the primary path and the redundant path for each of the node pairs;
an extracting unit that extracts, from among the node pairs, a deviating pair that will experience a decrease in communication performance when switching from the primary path to the redundant path based on the path length difference ;
an additional edge identifying unit that identifies an additional edge that is not included in the communication network and that, by adding it to the communication network, suppresses a decrease in communication performance when switching from the primary path to the redundant path in the disconnected pair;
A network management device comprising: the path identification unit identifies, for a plurality of candidate edges that are candidates for the added edge, a primary path and a redundant path for each of the pairs to be removed when the candidate edges are added to the communication network;
The network management device according to claim 1 , wherein the edge to be added is identified as the edge to be added by one of the plurality of candidate edges that has the smallest index value related to the path length difference between the outgoing pairs. A network management device that manages a communication network having a plurality of nodes and a plurality of edges connecting the nodes,
a route specifying unit that specifies, for each node pair on the communication network, a main route and a redundant route that are configured with the plurality of edges and connect the node pair, and in which a relay node on the main route and a relay node on the redundant route do not overlap;
a path length difference calculation unit that calculates a path length difference between the primary path and the redundant path for each of the node pairs;
an extracting unit that extracts, from among the node pairs, a deviating pair that will experience a decrease in communication performance when switching from the primary path to the redundant path based on the path length difference;
Equipped with
The network management device according to claim 1 , wherein the extraction unit extracts the outlying pairs by statistical processing based on a combination of the path length difference and the distance between the node pairs. A network management method for managing a communication network having a plurality of nodes and a plurality of edges connecting the nodes, comprising the steps of:
identifying a primary route and a redundant route that are configured with the plurality of edges and connect the node pair for each node pair on the communication network, the primary route and the redundant route having no overlapping relay nodes on the primary route and no overlapping relay nodes on the redundant route;
calculating a path length difference between the primary path and the redundant path for each of the node pairs;
extracting a deviating pair from the node pairs, which will cause a decrease in communication performance when switching from the primary path to the redundant path, based on the path length difference ;
identifying an additional edge that is not included in the communication network and that, when added to the communication network, suppresses a decrease in communication performance when switching from the primary path to the redundant path in the removed pair;
The network management method includes: A computer that manages a communication network having a plurality of nodes and a plurality of edges connecting the nodes,
identifying a primary route and a redundant route that are configured with the plurality of edges and connect the node pair for each node pair on the communication network, the primary route and the redundant route having no overlapping relay nodes on the primary route and no overlapping relay nodes on the redundant route;
calculating a path length difference between the primary path and the redundant path for each of the node pairs;
extracting a deviating pair from the node pairs, which will cause a decrease in communication performance when switching from the primary path to the redundant path, based on the path length difference ;
identifying an additional edge that is not included in the communication network and that, when added to the communication network, suppresses a decrease in communication performance when switching from the primary path to the redundant path in the removed pair;
A program for executing the above.

Images