JP6180371B2 - Topology estimation apparatus and program - Google Patents

Description

  The present invention relates to a topology estimation apparatus and program for estimating a connection relationship between apparatuses constituting a network.

  In managing and managing a network, it is important to accurately grasp the connection relationship (hereinafter referred to as “topology”) between devices constituting the network. For example, when a failure occurs in an apparatus, the influence of the failure on the entire network is grasped using the topology, and a communication path is switched in order to minimize the influence on the service. At that time, if the topology information is not accurate, the influence of the failure cannot be correctly grasped. Furthermore, normal communication may be interrupted by switching to an incorrect route.

Thus, as a technique for estimating the topology, Non-Patent Document 1 discloses a technique that uses a transmission / reception traffic amount for each IF (interface) included in the apparatus. The topology estimation method described in Non-Patent Document 1 uses the following two principles.
(Principle 1) The amount of traffic flowing into a subnet is equal to the amount of traffic flowing out.
(Principle 2) Inflow traffic from a certain node to a subnet goes out to a different node in the same subnet.
Using these two principles, the topology is estimated by obtaining all nodes sharing the subnet from the network. Here, the subnet means a closed network to which a plurality of IFs are connected. This will be specifically described below.

As shown in FIG. 1, it is assumed that s nodes N (nodes N _{1 to} N _S ) are connected to a certain subnet. At least one IF included in each node is connected to the subnet, and a total of m (m ≧ s) IFs are connected. A set of IF node N ₁ which is connected to the subnet defined as "phi _1" Similarly, the node N ₂ to N _S, and defined as "phi _2" - "phi _S". In this case, the inflow / outflow traffic to the subnet is the sum of the transmission traffic volume and the reception traffic volume of “φ ₁ ” to “φ _S ”, respectively. Therefore, (Principle 1) can be read as the following determination formula 1 using “φ ₁ ” to “φ _S ”.
(Total transmission traffic volume of φ ₁ ~φ _S) = (total incoming traffic of phi ₁ to [phi] _S)
... Judgment formula 1
Therefore, when the determination formula 1 is satisfied, it can be determined that (Principle 1) is satisfied.

Further, the inflow traffic from the node N ₁ to this subnet is the sum of the transmission traffic amount of “φ ₁ ”. According to (Principle 2), this traffic is the remaining s−1 traffic other than the node N ₁ . Among the IFs that the node N has, IFs connected to this subnet, that is, one or more IFs in “φ ₂ ” to “φ _S ” are received. Therefore, the following formula is established.
(Total amount of transmission traffic of φ ₁ ) ≦ (total amount of reception traffic of φ _{2 to} φ _S )
This also applies to the node _N 2 to N _S. Therefore, (Principle 2) can be read as the following judgment formula 2.
(Phi _i total transmission traffic amount) ≦ (excluding phi _i, the sum of received traffic of phi ₁ to [phi] _S)
[I = 1, 2,..., S]
... Judgment formula 2
Therefore, when the determination formula 2 is satisfied, it can be determined that (Principle 2) is satisfied.

  In the topology estimation method described in Non-Patent Document 1, when s number of nodes N satisfy both conditions of determination formula 1 and determination formula 2, it is considered that there is a connection relationship between these nodes. Therefore, by obtaining a set of nodes N satisfying both of the judgment formula 1 and the judgment formula 2 based on the values of the IF transmission traffic volume and the reception traffic volume of each node N to be estimated, All connection relationships can be obtained.

Naoyuki Tanji and three others, “Examination of network topology estimation technology using traffic volume”, The Institute of Electronics, Information and Communication Engineers, IEICE Technical Report, vol. 112, no. 492, ICM2012-75, pp. 95-100, March 2013

  In the topology estimation method described in Non-Patent Document 1, the connection relationship is evaluated using the degree of coincidence of the transmitted and received traffic amounts in (Principle 1). However, when the amount of transmitted / received bytes is used as the amount of transmitted / received traffic, the connection relationship may not be estimated correctly. Depending on the specifications of the device, the method of counting the amount of transmitted / received bytes may be counted including the header portion or not including the header portion. Therefore, when a device that counts including the header portion and a device that does not count including the header portion are connected, a difference in the amount of transmitted and received bytes always occurs at a constant rate, so (Principle 1) is not satisfied. Hereinafter, a specific description will be given with reference to FIG.

As shown in FIG. 2, the node _{N 1} and IF "3" and the node IF "1" in _{N 2,} a connection relationship. That is, it constitutes a subnet. Further, it is assumed that the node N ₁ is a device that does not count including the header portion as a method of counting the amount of transmitted / received bytes, and the node N ₂ is a device that counts including the header portion. Here, the transmission / reception traffic amount of the IF “3” of the node N ₁ is shown by a graph 201a and a table 201b, and the transmission / reception traffic amount of the IF “1” of the node N ₂ is shown by a graph 202a and a table 202b.

In this example, considering the case where the topology estimation method described in Non-Patent Document 1 is applied to the transmission / reception traffic volume at time t1, (judgment formula 1) refers to Table 201b and Table 202b in FIG. It becomes as follows.
(Total amount of transmitted traffic) = (Total amount of received traffic)
10 + 7 ≠ 5 + 14
Thus, when a device that counts including the header portion (node N ₂ ) and a device that does not count including the header portion (node N ₁ ) are connected, there is always a difference in the amount of transmitted and received bytes at a constant rate. Since this occurs (see reference numeral 210 in FIG. 2), the condition of (determination formula 1) is not satisfied. Therefore, in the method of estimating the topology described in Non-Patent Document 1, the nodes N ₁ and IF "3" and the node IF "1" in N _2, but in fact despite the connection relation, the connection relationship It is estimated that there is no.

  The present invention has been made in view of such a background, and even when the method of measuring the amount of transmitted / received traffic of each device (node) is different, the connection relationship (topology) between IFs is improved with improved accuracy. It is an object of the present invention to provide a topology estimation device and a program that can estimate the above.

  In order to solve the above-described problem, the invention according to claim 1 is a topology estimation device that estimates a connection relationship between devices constituting a network, and includes a transmission side and reception between IF (Interface) included in the device. Fluctuation components common to each traffic component are removed from the time-series information of each traffic on the side, and a coincidence variation that is not common to the transmission side and the reception side is extracted. A topology estimation device comprising a processing unit that determines that there is a connection relationship between the IFs if the time series information of fluctuations is synchronous.

  According to this configuration, the fluctuation component common to each traffic component on the transmission / reception side between the IFs of the nodes, which causes a misjudgment of connection determination between the nodes, is removed, and the accidental fluctuation that is a fluctuation that does not have commonality on the transmission / reception side Was extracted. For this reason, there is no cause for erroneous determination of connection between nodes. After the extraction, if the time series information of each coincidence change in transmission and reception is synchronous, it is determined that there is a connection relationship between IFs, and therefore the connection relationship between nodes can be determined appropriately without erroneous determination.

  Also, considering the fluctuation trend (variation component) of the transmission / reception traffic volume of each node, if the method of measuring the transmission / reception traffic volume of each node is different, that is, the device specifications are different, the transmission / reception traffic volume at a certain rate Even if there is a difference between the two, the possibility of correctly evaluating the connection relationship without erroneous estimation or estimation omission can be greatly improved. For this reason, it is possible to estimate the connection relationship between IFs with improved accuracy.

  The invention according to claim 2 is a topology estimation device for estimating a connection relationship between a plurality of devices constituting a network, and information on a time-series transmission traffic amount and a reception traffic amount of each IF included in the device is the IF Each of the IF transmission / reception amount information stored for each IF, and the IF transmission / reception amount information for each IF is referred to, and the number of IFs constituting the subnet is k (k ≧ 2). From the total value of the received traffic amount of each IF that constitutes the combination of IFs that are the generated determination candidates, and the determination candidate generation unit that generates all the combinations of IFs to be determined as connection relationship determination candidates A balance degree calculation unit for calculating a balance degree indicating an absolute value of a difference obtained by subtracting a total value of transmission traffic amounts, and transmission / reception between IFs constituting a combination of IFs as the determination candidates A time series processing unit that removes a common fluctuation component from the traffic component of each of the transmission and reception traffic components, and extracts a feature quantity that is a fluctuation component that has no common and remains after the removal, Based on the time-series relationship between the total value of the received traffic volume and the total value of the transmission traffic volume of each IF that constitutes a combination of IFs that are candidates for determination, the variation tendency of the feature quantities of each of the transmission and reception is matched. Among the combinations of an evaluation value calculation unit that calculates an evaluation value indicating degree, a first determination that determines that a multiplication result of the balance and the evaluation value is equal to or less than a predetermined value, and an IF that is the determination candidate From this, one IF is extracted, and the transmission traffic volume of the extracted IF is equal to or less than the sum of the reception traffic volumes of all IFs except the extracted IF. If both determinations are performed for each combination of IFs that are candidates for determination and both determinations are satisfied, the determination is performed. A topology estimation apparatus comprising a connection relationship determination unit that determines that there is a connection relationship between IFs constituting a combination of candidate IFs.

  According to this configuration, from the traffic components transmitted and received between the IFs of the nodes, in the traffic components transmitted and received, common fluctuation components (components that cause erroneous connection determination between nodes) are removed, A feature quantity that is a fluctuation component having no commonality remaining after the removal is extracted. For this reason, there is no cause for erroneous determination of connection between nodes. After extracting feature values, if the time series information of each feature value sent and received is synchronized, it is determined that there is a connection relationship between IFs, so that the connection relationship between nodes can be properly determined without erroneous determination. it can. Also, considering the fluctuation trend (variation component) of the transmission / reception traffic volume of each node, if the method of measuring the transmission / reception traffic volume of each node is different, that is, the device specifications are different, the transmission / reception traffic volume at a certain rate Even if there is a difference between the two, the possibility of correctly evaluating the connection relationship without erroneous estimation or estimation omission can be greatly improved. For this reason, it is possible to estimate the connection relationship between IFs with improved accuracy.

  According to a third aspect of the present invention, the storage unit further stores device IF correspondence information in which identification information of the IF included in each of the devices is stored, and the determination candidate generation unit includes the generated determination The device IF correspondence information is referred to for each candidate IF combination, and if there is no IF that constitutes the IF combination that is the determination candidate, the number of IFs that constitute the IF combination that is the determination candidate is 1. In this case, in any case where all of the IFs constituting the combination of IFs that are candidates for determination belong to one device, information on the IF combination corresponding to any of these cases is stored in the generated IF. The topology estimation apparatus according to claim 2, wherein the topology estimation apparatus is deleted from the combination.

  According to this configuration, combination information of IFs that cannot be connected between IFs is deleted, so that unnecessary connection determination processing can be eliminated. For this reason, topology estimation between nodes can be performed efficiently.

  In the invention according to claim 4, the storage unit stores connection determination candidate information for storing a combination of IFs as the determination candidates, and a combination of IFs determined to have a connection relationship by the connection relationship determination unit. IF connection information is further stored, and the connection relation determination unit is one of the IFs constituting the combination of IFs stored in the IF connection information in the combination of IFs stored in the connection determination candidate information. The topology estimation device according to claim 2 or 3, wherein information on a combination of IFs including the IF is deleted from the connection determination candidate information.

  According to this configuration, the IF stored in the IF connection information is in a state having the IF of the connection partner, and at present, no other IF can be held by the connection partner. For this reason, it is possible to efficiently estimate the topology between nodes by deleting the IF stored in the IF connection information from the connection determination candidate information.

  The invention according to claim 5 is a program for causing a computer to realize each function of the topology estimation device according to any one of claims 1 to 4.

  Also with this configuration, the same effect as that of any one of claims 1 to 4 can be obtained.

  Advantageous Effects of Invention According to the present invention, a topology estimation apparatus and program capable of estimating the connection relationship (topology) between IFs with improved accuracy even when each device (node) has a different method for measuring the amount of transmitted / received traffic. Can be provided.

It is a figure for demonstrating the subnet comprised by several IF with connection relation. It is a figure for demonstrating the subject in the conventional topology estimation method. It is a wave form diagram which shows the example in which the characteristic of the fluctuation component common to each traffic appears in the transmission / reception traffic between IF of each node. It is a figure which shows the data structural example of the node IF corresponding information which concerns on this embodiment. It is a figure which shows the data structural example of IF transmission / reception amount information which concerns on this embodiment. It is a figure which shows the data structural example of the connection determination completion flag information which concerns on this embodiment. It is a figure which shows the data structural example of the connection determination candidate information which concerns on this embodiment. It is a figure which shows the data structural example of IF connection information which concerns on this embodiment. It is a figure which shows the data structural example of the allowable error information containing the allowable error (sigma) and allowable error (gamma) which concern on this embodiment. The waveform of the observation traffic of the IF of the node is shown, (a) is the waveform Wa of the observation traffic of IFa, (b) is the waveform Wb of the observation traffic of IFb, (c) is the waveform Wc of the observation traffic of IFc, (d). FIG. 6 is a diagram showing a waveform Wd of IFd observation traffic. FIG. 6A shows a waveform of a predicted IF traffic of a node, where (a) is a waveform Wa1 of the predicted traffic of IFa, (b) is a waveform Wb1 of the predicted traffic of IFb, and (c) is an error obtained by subtracting the predicted traffic from the observed traffic of IFa. Waveforms Wa2 and (d) of FIG. 8 are diagrams showing an error waveform Wb2 obtained by subtracting the predicted traffic from the observed traffic of IFb. FIG. 7A shows a waveform of a predicted IF traffic of a node, where (a) is a waveform Wc1 of an IFc predicted traffic, (b) is a waveform Wd1 of an IFd predicted traffic, and (c) is an error obtained by subtracting the predicted traffic from an IFc observed traffic. Waveforms Wc2 and (d) of FIG. 6 are diagrams showing an error waveform Wd2 obtained by subtracting the predicted traffic from the observed traffic of IFd. (A) represents the time-series waveform of each sum value Tsum (t) and Rsum (t) of the IF traffic transmission / reception amount in the time domain, and (b) represents the frequency obtained by Fourier transforming the waveform of (a). (C) represents a frequency spectrum after deleting frequency components common to the lower and upper graphs of (b), and (d) represents an IF obtained by performing an inverse Fourier transform on the frequency spectrum of (c). It is the figure which represented each time series waveform of the traffic transmission / reception of in the time domain. (A) represents the time-series waveform of each sum value Tsum (t) and Rsum (t) of the IF traffic transmission / reception amount in the time domain, and (b) represents the frequency obtained by Fourier transforming the waveform of (a). (C) represents a frequency spectrum after the 24-hour spectral component common to the lower and upper graphs of (b) is deleted, and (d) is obtained by inverse Fourier transforming the frequency spectrum of (c). FIG. 6 is a diagram showing time series waveforms of IF traffic transmission / reception in the time domain. (A) represents the time-series waveform of each sum value Tsum (t) and Rsum (t) of the IF traffic transmission / reception amount in the time domain, and (b) represents the frequency obtained by Fourier transforming the waveform of (a). (C) represents the frequency spectrum after deleting the low frequency spectrum components common to the lower and upper graphs of (b), and (d) is obtained by inverse Fourier transforming the frequency spectrum of (c). FIG. 6 is a diagram showing time series waveforms of IF traffic transmission / reception in the time domain. It is a block diagram which shows the structure of the topology estimation apparatus which concerns on this embodiment. It is a 1st flowchart which shows the flow of the topology estimation process by the topology estimation apparatus which concerns on this embodiment. It is a 2nd flowchart which shows the flow of the topology estimation process by the topology estimation apparatus which concerns on this embodiment.

  Next, a mode for carrying out the present invention (hereinafter referred to as “the present embodiment”) will be described.

<Overview>
First, the basic concept and processing outline of the topology estimation processing executed by the topology estimation device 1 (see FIG. 16) and the program according to the present embodiment will be described.
(Basic concept)
The topology estimation apparatus 1 according to the present embodiment estimates the topology between nodes constituting the network. Specifically, it is necessary for topology estimation by removing rule components such as 24-hour fluctuations and day-of-week fluctuations common to the entire network from the time-series data of the traffic volumes on the transmission side and reception side between IFs of each node. Each feature amount (described later) on the transmitting side and the receiving side is extracted, and the synchronism of each extracted feature amount is determined to estimate the topology between the nodes. If each feature quantity is synchronous, it is determined that there is a connection relationship between IFs.

However, the regular component refers to the traffic of each IF such as the periodic fluctuations repeated every month or season, as well as the cyclic fluctuations repeated every month or season, and the trend fluctuations (trends) representing long-term movements. This is a common trend.
The feature amount is a random fluctuation component that is an outlier such as bursty traffic (referred to as burst traffic) in transmission / reception traffic between IFs. This random variation component has synchronization in transmission / reception between IFs. For this reason, the feature amount is also synchronized.

  For example, when IFa of a certain node and IFb of another node are connected, if an outlier of burst traffic is transmitted in IFa, IFb receives the outlier in synchronization with the transmission. Therefore, rule components common to the entire network and the region are removed from the transmitted / received traffic, and feature quantities specific to the traffic of each IFa and IFb are extracted, and the synchronism of each feature quantity is determined. At the time of this determination, the synchronism of the feature amount is determined using (Principle 1B) described later and (Principle 2) described above as determination conditions, and when it is determined that there is synchronization, the nodes are connected. Estimated.

Here, an extension of (Principle 1) described in Non-Patent Document 1 described above is the following (Principle 1A), and an extension of (Principle 1A) is the following (Principle 1B).
(Principle 1A) The fluctuation trends of the inflow traffic amount and the outflow traffic amount to a certain subnet are equal.
(Principle 1B) The characteristic features of inflow traffic and outflow traffic to a certain subnet are equal.

Here, a method for determining a topology in which (Principle 1A) is introduced will be described.
As described above with reference to FIG. 2, depending on the specifications of the apparatus, there is always a difference in the amount of transmitted and received traffic at a constant rate. For this reason, the topology estimation method described in Non-Patent Document 1 does not satisfy (Principle 1) as described above, and even if there is a connection relationship between IFs, it is estimated that there is no connection relationship. May end up.

  In this way, even when the device specifications are different, that is, when there is a certain difference in the measurement of transmission / reception traffic at each node, the transmission / reception traffic of the IFs in the connection relationship shows a consistent fluctuation tendency. (See reference numeral 220 in FIG. 2). For example, if IFa of a certain node and IFb of another node are connected, if the amount of IFa transmission bytes increases, the amount of IFb reception bytes also increases, and if the amount of IFa transmission bytes decreases, IFb reception The amount of bytes is also reduced.

Utilizing the characteristics of the synchronization of the fluctuation tendency of the transmitted and received traffic volume, the synchronization of the fluctuation tendency is determined. That is, the synchronization of the fluctuation tendency is determined by extending (Principle 1) (Principle 1A).
The calculation of the fluctuation tendency at the time of making this determination and the formulation of the fluctuation tendency will be described. Here, a subset of IF will be described. For example, if two IFa and IFb are selected from 10 IFs (IFa (first), IFb (second)),..., IFj (10th), these two IFa and IFb are It is defined as a subset of IF. The number of IFs in the IF subset is “k” (k ≧ 2). The IF subset is also referred to as an IF subset.

  The first calculation method of the fluctuation tendency will be described. First, a fluctuation tendency C between the inflow traffic amount and the outflow traffic amount to a certain subnet is obtained. For this purpose, an IF connected to the subnet is selected. This selection is performed for all IF subsets having two or more IFs, and the time series data of the total packet transmission amount of k IFs belonging to the IF subset and the k IFs belonging to the IF subset. A correlation coefficient C1 with the time-series data of the total packet reception amount is obtained. Then, the fluctuation tendency C is calculated from the equation C = 1−C1. At this time, if the synchronism of the time-series data is high, the correlation coefficient C1 approaches “1”, so the fluctuation tendency C approaches “0”. Note that the traffic amount is expressed as a packet transmission amount or a reception amount.

  A second calculation method of the fluctuation tendency will be described. First, a first-order time series difference (in other words, a difference from the first-order lag), which is a difference between adjacent data in time-series data, is expressed as a total transmission amount time series of k IF packets. It calculates | requires about each of reception amount total value time series. The degree of coincidence C2 between the positive and negative signs “+” or “−” of the obtained difference time series is obtained by an expression “number of data with positive and negative signs matched ÷ number of observation data”. And the fluctuation tendency C is calculated as C = 1-C2. At this time, if the synchronism of the time-series data is high, the code matching degree C2 approaches “1”, and the fluctuation tendency C approaches “0”.

Next, the formulation of fluctuation tendency will be described. As a formula obtained by formulating (Principle 1A), the balance is calculated using (Formula 1) shown below. However, combinations in which k IFs selected as combinations of IFs to be described later belong to the same node are excluded because they do not constitute a subnet.
“IF combination” indicates a connection combination of IFs that are candidates for determination of no connection or connection between IFs. For example, when the number of candidate IFs n = “3” and there are three “IFa, IFb, IFc”, and IF number k = “2” in the IF subset, a combination of two IFs Are generated in three ways: “IFa, IFb”, “IFb, IFc”, and “IFc, IFa”. This is nothing more than setting the number of determination candidate IFs to “n” and generating a combination of k IFs ( _n C _k patterns) from the _n IFs.

  Balance = C × (total transmission amount of IF packets connected to subnet−total reception amount of IF packets connected to subnet) (Equation 1)

However, C is a fluctuation tendency. The IF packet transmission amount total value is the k IF packet transmission amount total value, and the IF packet reception amount total value is the k IF packet reception amount total value.
In (Equation 1), it can be said that the closer the balance obtained from (Equation 1) is to “0”, the higher the synchronization is.

  Next, the following (Equation 2) expressed as an inequality (Principle 2 inequality) that "inflow traffic to a subnet from a node goes out to a different node in the same subnet" in (Principle 2) is evaluated To do.

  (Total value of IFi packet transmission amount) ≦ (Total value of received packet amount of IF connected to the subnet excluding IFi) [i = 1, 2,..., K] (Expression 2)

  In this way, the balance is calculated from (Equation 1) for all IFs in the IF subset (for example, two IFa and IFb). If this result satisfies the (equation 2) that is within the predetermined allowable error range and (equation 2), the IFa and IFb are determined to be connected.

In this way, if the connection estimation between IFs is performed using (Principle 1A) and (Principle 2) as the determination conditions, it can be determined that there is a connection when the IFs are connected. Can be solved. That is, as shown in FIG. 2, when the node N ₂ counting including the header portion and the node N ₁ not counting including the header portion are connected, the transmission / reception byte amount is always different at a constant rate. Occurs. Therefore, the node N ₁ and IF "3" and the node IF "1" in N _2, but in fact despite the a connection relationship, the connection relationship will be estimated that no there is no possible such .

However, even when connection estimation between IFs is performed using (Principle 1A) and (Principle 2) as judgment conditions, in the following cases, proper connection estimation between IFs cannot be performed.
This is a case where the topology estimation target is an IF of a node in which a lot of user traffic is aggregated like an ISP (Internet Service Provider) core network. In this case, individual traffic fluctuation components before aggregation are smoothed, and characteristics such as a 24-hour fluctuation component and a day-of-week fluctuation component common to the individual traffic appear preferentially. There is a possibility that the fluctuation component may cause the estimation of the synchronization determination of the feature amount described above to be erroneous.

FIG. 3 shows an example in which characteristics of fluctuation components common to individual traffic appear.
The vertical axis in FIG. 3 indicates the traffic volume [Gbps] between IF transmission and reception, and the horizontal axis indicates a time series in units of 3 hours (time period) from Sunday to Saturday in one week. The vertical axis and the horizontal axis indicate the waveforms W1 to W6 of the traffic amount that changes in a trend as time passes.
Each of the waveforms W1 to W6 represents a trend waveform every three hours and days of the week in May 2007. Similarly, the waveform W2 is May 2008 and the waveform W3 is May 2009. W4 represents a trend waveform for each time zone and every day of the week in May 2010, waveform W5 in May 2011, and waveform W6 in May 2012.

  Since the waveforms W1 to W6 increase when compared with the traffic volume of a certain IFa and the traffic volume of another IFb, the fluctuation trends coincide with each other. However, when compared to other IFs a year ago, the traffic volume has also increased. As described above, the characteristics of the waveforms W1 to W6 reflect the human daily behavior, and therefore tend to be similar through all IFs. As a result, the synchronism of the fluctuation tendency due to the 24-hour fluctuation component and the day-of-week fluctuation component is increased even between IFs that are not connected.

  Thus, when each waveform W1-W6 becomes the fluctuation | variation which has commonality between IF, this fluctuation | variation component may make the estimation of the synchronization determination of the feature-value mentioned above erroneous. In other words, it becomes difficult to improve the accuracy and estimate the topology between IFs. For this reason, when evaluating the coincidence of the feature amounts, it is necessary to remove the increasing tendency of the waveforms W1 to W6.

  Therefore, in the present invention, (Principle 1B) and (Principle 2) are used as determination conditions, so that the topology between IFs of each node can be estimated with high accuracy. Hereinafter, the topology estimation process of the present invention will be described.

(Outline of processing)
Next, an overview of the topology estimation process executed by the topology estimation apparatus 1 and the like according to the present embodiment will be described.
First, as a premise, when performing the procedure shown below, the node IF correspondence information (device IF correspondence information) 310 shown in FIG. 4 is stored in the storage means (corresponding to the storage unit 30 shown in FIG. 16 described later) of the topology estimation device 1. IF transmission / reception amount information 320 shown in FIG. 5, connection determination completed flag information 325 shown in FIG. 6, connection determination candidate information 330 shown in FIG. 7, IF connection information (output list) 340 shown in FIG. Assume that the allowable error information 350 including the allowable error σ and the allowable error γ shown in FIG. 9 is stored. 4 to 9 show one configuration example of each piece of information.

(Processing procedure)
<< Procedure 1: Target IF subset creation process >>
The topology estimation apparatus 1 creates a subset of IFs, and all of the subsets excluding “empty set”, “set with IF number“ 1 ””, and “set in which all IFs belong to the same node” The following steps 2 to 8 are performed using the IF of the above as an object of topology estimation determination.
Hereinafter, in the description of procedures 2 to 8, a case where the number of IFs is “n” and the number of IFs in the IF subset is “k” will be described.

<< Procedure 2: Initial setting process >>
In the topology estimation apparatus 1, for example, k = “2” is set as an initial value as an initial setting.
Of the subsets having k IFs, a subset in which an IF having a connection determination flag (FIG. 6) of the connection determination flag information 325 of “0” exists is set as a determination candidate. Steps 3 to 8 are performed for all IFs.
The connection determination flag “0” indicates that there is no connection between IFs, and “1” indicates that there is a connection between IFs. Hereinafter, the connection determined flag is also simply referred to as a flag.

Furthermore, the topology estimation apparatus 1 sets the number of determination candidate IFs to “n”, and generates a combination of k IFs ( _n C _k patterns) from the _n IFs. The generated combination of k IFs is stored in the “IF subset” column of the connection determination candidate information 330 (FIG. 7).

但し、ＩＦｉ（ｔ）．ｉｎは時刻ｔのＩＦｉのトラフィック受信量、
ＩＦｉ（ｔ）．ｏｕｔは時刻ｔのＩＦｉのトラフィック送信量、
ｋは対象としているＩＦ部分集合のＩＦ数である。 ≪Procedure 3: Calculation of equilibrium for IF subsets≫
The topology estimation device 1 selects one subset having k IFs as a determination candidate. The balance number p (t) is calculated by substituting the number of IFs of the IF subset that is the determination candidate and the time-series data of the transmission / reception traffic amount of each IF of the subset into the following (Equation 3). Do. The calculated balance p (t) is written in the connection determination candidate information 330.
Note that (Equation 3) is a formulation of (Principle 1) “The amount of traffic flowing into a certain subnet is equal to the amount of traffic flowing out” with the balance being p (t).

However, IFi (t). in is the traffic reception amount of IFi at time t,
IFi (t). out is the traffic transmission amount of IFi at time t,
k is the number of IFs in the target IF subset.

For example, as shown in FIG. 2, an example set (k = 2) of the node IF "1" IF "3" node _{N 2} of _{N 1,} when calculating the balance of p (t1), as follows: Become.

p (t1) = | {IF3 (t1). in-IF3 (t1). out}
+ {IF1 (t1). in-IF1 (t1). out} |
p (t1) = | (5-10) + (14-7) |
p (t1) = 2

<< Procedure 4: Common component removal process >>
As described above, the traffic fluctuation component is a fluctuation component common to each IF traffic such as periodic fluctuation and trend fluctuation (trend) (a fluctuation component having commonality) and a fluctuation component that does not have commonality such as burst traffic. It consists of a certain chance variation component (feature). A fluctuation component having commonality between IFs needs to be removed because there is a risk of misestimating the synchronism determination of the feature amount.

Therefore, the topology estimation apparatus 1 performs the process of removing the fluctuation component having commonality according to the procedure 4. There are various methods for the removal process in step 4. In the procedure 4, the following well-known methods using the quantification theory class I, the method using the time series model by the Holt Winters method, and the method by Fourier transform will be described as examples, but the method is limited to this. is not.
Further, in the procedure 4, for each time series of the traffic reception amount total value Rsum (t) of k IFs and the traffic transmission amount total value Tsum (t) of k IFs, the following procedure 4- It is assumed that the common fluctuation component is removed by any one of processes 1 to 4-5.

≪Procedure 4-1: Example of removing variable components with commonality using quantification theory class I≫
The removal process of the procedure 4-1 performed by the topology estimation apparatus 1 will be described.
The quantification theory class I is a multiple regression model in which qualitative variables such as day of the week and month are explanatory variables (independent variables). For example, the following model (Equation 4) is used.

Rsum (t) = C0 + C1 × t + C2 × d + C3 × w + C4 × m + C5 × s + ε
... (Formula 4)
Where Rsum (t) is the total traffic reception amount of k IFs, C0 is a constant, Ci is a multiple regression coefficient (i = 1, 2, 3, 4, 5), d is a time zone (1 o'clock, 2 o'clock,..., 24 o'clock each hour unit), w is a day of the week, m is a month, s is a season, and ε is a coincidence.
In the multiple regression model, fluctuations that can be explained by time zone, day of the week, month, season, and the like are fluctuation components having commonality, and accidental fluctuations ε are fluctuation components having no commonality. That is, the accidental variation ε is a feature amount.

  First, a constant C0 and a multiple regression coefficient Ci (i = 1 to 5) are obtained by the least square method. The fluctuation component having no commonality is a coincidence fluctuation ε, which is calculated by the following (Equation 5).

              ε (t) = observed value (t) − (C0 + C1 × t + C2 × d + C3 × w + C4 × m + C5 × s) (Formula 5)

If there are meaningless explanatory variables as a result of statistical tests, they are removed.
For the total value Tsum (t) of the traffic transmission amount of k IFs, the same calculation is performed using (Equation 5), and a fluctuation component having no commonality (accidental fluctuation ε) is obtained.

FIG. 10 shows, for example, when there are four IFs, IFa, IFb, IFc, and IFd, (a) shows the waveform Wa of the observed traffic of IFa, (b) shows the waveform Wb of the observed traffic of IFb, (C) shows the waveform Wc of the IFc observation traffic, and (d) shows the waveform Wd of the IFd observation traffic. 10 (a) to 10 (d), the vertical axis represents the observed traffic volume [Gbps] of IF, and the horizontal axis represents the time represented by 72 points for 3 days when 1 hour is 1 point. .
In the observed traffic waveforms Wa to Wd of IFa to IFd shown in FIGS. 10A to 10D, a period variation of 24 hours is seen, but the difference cannot be determined.

  Next, in FIGS. 11A and 11B and FIGS. 12A and 12B, the vertical axis indicates the predicted traffic volume [Gbps] of IF, and the horizontal axis indicates the same time as in FIG. 11 (a) and 11 (b), 12 (a) and 12 (b) show the predicted traffic waveforms Wa1, IF1 to IFd corresponding to FIGS. 10 (a) to 10 (d) according to the respective quantification theories. Wb1, Wc1, and Wd1 are shown.

11 (c) and 11 (d) and FIGS. 12 (c) and 12 (d), the vertical axis represents the error [Gbps] obtained by subtracting the predicted traffic volume from the IF observed traffic volume, and the horizontal axis represents the figure. The same time as 10 is shown.
11 (c) and 11 (d) and FIGS. 12 (c) and 12 (d) show the waveforms (prediction) of predicted traffic corresponding to the waveforms (observed values) Wa, Wb, Wc and Wd of the respective observed traffic. Value) Waveforms Wa2, Wb2, Wc2, and Wd2 as a result of subtracting Wa1, Wb1, Wc1, and Wd1 are shown. That is, Wa-Wa1 = Wa2, Wb-Wb1 = Wb2, Wc-Wc1 = Wc2, Wd-Wd1 = Wd2.
As shown in FIGS. 11C and 11D, in the error waveforms Wa2 and Wb2, it can be seen that peak traffic occurs in a time width around 10 points on the time axis. The peak traffic is an accidental variation ε.

«Procedure 4-2: Example of removing fluctuation components with commonality using the Holt Winters method»
The removal process of the procedure 4-2 performed by the topology estimation apparatus 1 will be described.
The Holt Winters method is a technique used for time series models with trends and periodic components. The first-order exponential smoothing method (weighting of predicted and actual values) is used to estimate constant terms, trends, and periodic components. Estimate using an average prediction method.
An estimated value of the total traffic reception amount Rsum (n + t) of k IFs at time n + t when observation data up to time n is given is given by the following (formula 6).

_{Rsum (n + t) = (} m n + lb n) c n-s + l + ε ... ( Equation 6)
However,
m _t = α ₀ (y _t / c _t−s ) + (1−α ₀ ) (m _t−1 −b _t−1 )
b _t = α ₂ (m _n− m _t−1 ) + (1−α ₂ ) b _t−1
c _t = α ₂ (y _t / m _t ) + (1−α ₂ ) b _t−s

ε is an accidental change, α _i is a smoothing coefficient (i = 0, 1, 2), m _t is a constant, b _t is a trend, c _t is an estimate of a periodic component, s is a period, and l is a period s It represents the value of the forecast period. For example, when a 24-hour period is used as the periodic component, s = 24. In the case of s = 24 and l = 3, three periods ahead are predicted out of 24 periods.
Further, observation data up to time n is given, and an estimated value of the traffic reception amount total value Rsum (n + 1) of k IFs ahead of the period s and l period is given by the following (formula 6a).
_{Rsum (n + l) = (} m n + lb n) c n-s + l + ε ... ( Equation 6a)
In this time-series model, fluctuations that can be explained by trend and periodic components are fluctuation components having commonality, and accidental fluctuations ε are fluctuation components having no commonality. Further, the smoothing coefficient is obtained by the least square method.

The fluctuation component having no commonality is a chance fluctuation ε and is calculated by the following (formula 7).
ε (n + t) = observed value (n + t) − (m _n + lb _n ) c _{n−s + l} (Expression 7)
In addition, for the total value Tsum (t) of the traffic transmission amount of k IFs,
A calculation similar to the amount of traffic received is performed to determine the accidental variation ε.

<< Procedure 4-3: Example 1 of removing fluctuation component having commonality using Fourier transform >>
The removal process of the procedure 4-3 performed by the topology estimation apparatus 1 will be described with reference to FIG.
The lower graph and the upper graph in FIG. 13A will be described. The vertical axis of the lower graph represents the IF traffic transmission amount total value Tsum (t), and the horizontal axis represents time. In the time domain of the vertical and horizontal axes, a time-series waveform Wa4 of the total traffic transmission amount Tsum (t) of k IFa is represented. The vertical axis of the upper graph represents the IF traffic reception amount total value Rsum (t), and the horizontal axis represents time. In the time domain indicated by the vertical and horizontal axes, a time-series waveform Wb4 of the traffic reception amount total value Rsum (t) of k IFb is represented.
The lower graph and the upper graph are also referred to as a lower graph and an upper graph, the lower graph is also referred to as a lower graph, and the upper graph is also referred to as an upper graph.

  The lower and upper graphs in FIG. 13B will be described. The vertical axis of the lower graph represents the IF traffic transmission amount total value Tsum (t), and the horizontal axis represents the frequency. The frequency spectrum f1, f2, f3, f4, f5 of the traffic transmission amount total value Tsum (t) of k IFa is represented in the frequency domain by the vertical axis and the horizontal axis. The vertical axis of the upper graph represents the IF traffic reception amount total value Rsum (t), and the horizontal axis represents the frequency. The frequency spectrum f1, f2, f3, f4, f5 of the traffic reception amount total value Rsum (t) of k IFb is represented in the frequency domain by the vertical axis and the horizontal axis.

  The vertical and horizontal axes of the lower and upper graphs in FIG. 13C are the same as those in FIG. FIG. 13C shows the frequency spectra f2, f5 after deleting the frequency spectra f1, f3, f4 of the frequency components common to the lower and upper graphs of FIG. 13B.

  The vertical and horizontal axes of the lower and upper graphs in FIG. 13D are the same as those in FIG. FIG. 13D shows the frequency spectrums f2 and f5 in the lower and upper graphs of FIG. 13C, the waveform Wa5 of the k IFa traffic transmission side time series, and the traffic reception side time series of k IFbs. The time domain when returning to the waveform Wb5 is shown.

  In the removal process of procedure 4-3, first, Fourier transform is performed on each time-series data based on the waveform Wa4 and the time-series data based on the waveform Wb4 shown in FIG. Thereby, for example, five frequency spectra f1 to f5 shown in the lower and upper graphs of FIG. 13B are converted. Next, frequency spectra f1, f3, and f4 of frequency components common to the upper and lower stages are removed from the frequency spectra f1 to f5. By this removal, frequency spectra f2 and f5 shown in FIG. 13C are extracted.

  Next, inverse Fourier transform is performed on the extracted frequency spectra f2 and f5 to return to time-domain waveforms Wa5 and Wb5 shown in FIG. These waveforms Wa5 and Wb5 are characteristic amounts on the transmitting and receiving sides after the frequency spectra f1, f3, and f4 of the common frequency components are removed.

In this removal example 1, as a method of extracting the frequency spectrums f2 and f5 as feature amounts, time series data of k IF traffic transmission amount total value Tsum (t) and k IF traffic reception amount total value The feature amount was extracted from the time series data of Rsum (t).
In addition, the feature amount may be extracted using each time series data of the transmission amount total value Tsum (t) and the reception amount total value Rsum (t) of all IF traffics to be subjected to connection estimation.

<< Procedure 4-4: Common component removal example 2 using Fourier transform >>
The removal process of the procedure 4-4 performed by the topology estimation apparatus 1 will be described with reference to FIG.
The lower and upper graphs in FIG. The vertical axis of the lower graph represents the IF traffic transmission amount total value Tsum (t), and the horizontal axis represents time. In the time domain indicated by the vertical and horizontal axes, a time-series waveform Wa6 of the total traffic reception amount Rsum (t) of k IFa is represented. The vertical axis of the upper graph represents the total IF traffic reception amount Rsum (t), and the horizontal axis represents time. In the time domain of the vertical axis and the horizontal axis, a time-series waveform Wb6 of the traffic reception amount total value Rsum (t) of k IFb is represented.

  The lower and upper graphs in FIG. 14B will be described. The vertical axis of the lower graph represents IF traffic transmission amount total value Tsum (t) in [Gbps], and the horizontal axis represents frequency. In the frequency region of the vertical axis and the horizontal axis, frequency spectra f1, f2,..., F24,..., F31 of the hour traffic unit of the total traffic transmission amount Tsum (t) of k IFa are represented. The vertical axis of the upper graph represents the IF traffic reception amount total value Rsum (t), and the horizontal axis represents the frequency. In the frequency region of the vertical axis and the horizontal axis, frequency spectra f1, f2,..., F24,..., F31 of the hourly unit of the traffic reception amount total value Rsum (t) of k IFb are represented.

  The vertical and horizontal axes of the lower and upper graphs in FIG. 14C are the same as those in FIG. FIG. 14C shows frequency spectra f1 to f31 obtained by deleting the 24-hour frequency spectrum f24 common to the lower and upper graphs of FIG. 14B. However, the frequency spectrum f24 at 24:00 is a spectrum component at time 24:00, a spectrum component having a predetermined time width centered at time 24:00, or the like.

  The vertical and horizontal axes of the lower and upper graphs in FIG. 14D are the same as those in FIG. FIG. 14D shows frequency spectra f1 to f31 obtained by deleting the 24-hour frequency spectrum f24 shown in the lower and upper graphs of FIG. 14C, and the IFa traffic transmission side time-series waveform Wa7 and IFb The time domain when returning to the traffic reception side time-series waveform Wb7 is shown.

  In the removal process of the procedure 4-4, first, Fourier transform is performed on time series data based on the waveforms Wa6 and Wb6 shown in the lower and upper graphs of FIG. Thereby, the frequency spectrums f1, f2,..., F24,..., F31 shown in the lower and upper graphs of FIG. Next, the 24-hour frequency spectrum f24, which is a frequency component common to the upper and lower stages, is removed from the frequency spectra f1, f2,..., F24,. By this removal, frequency spectra f1 to f31 not including the frequency spectrum f24 shown in FIG. 14C are extracted.

  Next, inverse Fourier transform is performed on the frequency spectrums f1... F31 that do not include the extracted frequency spectrum f24 to return to the time-domain waveforms Wa7 and Wb7 shown in FIG. These waveforms Wa7 and Wb7 are characteristic quantities on the transmitting and receiving sides after removing the 24-hour spectral component, which is a common fluctuation component.

<< Procedure 4-5: Example 3 of removing fluctuation component having commonality using Fourier transform >>
The removal process of the procedure 4-5 performed by the topology estimation apparatus 1 will be described with reference to FIG.
The lower and upper graphs in FIG. The vertical axis of the lower graph represents the IF traffic transmission amount total value Tsum (t), and the horizontal axis represents time. In the time domain indicated by the vertical and horizontal axes, a time-series waveform Wa8 of the total traffic transmission amount Tsum (t) of k IFa is represented. The vertical axis of the upper graph represents the total IF traffic reception amount Rsum (t), and the horizontal axis represents time. In the time domain of the vertical axis and the horizontal axis, the time series waveform Wb8 of the traffic reception amount total value Rsum (t) of k IFb is represented.

  The lower and upper graphs of FIG. 15B will be described. The vertical axis of the lower graph represents IF traffic transmission amount total value Tsum (t) in [Gbps], and the horizontal axis represents frequency. In the frequency domain of the vertical axis and the horizontal axis, frequency spectra f0 to f400 of constant frequency units of the traffic transmission amount total value Tsum (t) of k IFa are represented. The vertical axis of the upper graph represents the IF traffic reception amount total value Rsum (t), and the horizontal axis represents the frequency. The frequency spectrum f0 to f400 of the constant frequency unit of the traffic reception amount total value Rsum (t) of IFb is represented in the frequency domain by the vertical axis and the horizontal axis.

  The vertical and horizontal axes of the lower and upper graphs in FIG. 15C are the same as those in FIG. FIG. 15C shows the frequency spectra f168 to f400 after deleting the frequency spectrum (for example, less than f168) of the low frequency component common to the lower and upper graphs of FIG. However, the frequency spectrum less than f168 corresponds to the spectrum component of less than one week.

  The vertical and horizontal axes of the lower and upper graphs in FIG. 15D are the same as those in FIG. FIG. 15D shows the time spectrums of the frequency spectrums f168 to f400 after deleting the low-frequency component frequency spectrum (less than f168) shown in the lower and upper graphs of FIG. Represents the time domain when the waveform Wa9 is returned to the time series waveform Wb9 on the traffic reception side of IFb.

  In the removal process of the procedure 4-5, first, Fourier transform is performed on time-series data based on the waveforms Wa8 and Wb8 shown in the lower and upper graphs of FIG. As a result, the spectrum is converted into frequency spectra f0 to f400 having a constant frequency interval in the lower and upper graphs shown in FIG. Next, a frequency spectrum component (less than f168) of less than one week, which is a low frequency component common to the upper and lower stages, is removed from the frequency spectrums f0 to f400 at a certain frequency interval. By this removal, frequency spectra f168... F400 shown in FIG.

  Next, inverse Fourier transform is performed on the extracted frequency spectrums f168... F400 to return to time-domain waveforms Wa9 and Wb9 shown in FIG. These waveforms Wa9 and Wb9 become the feature quantities on the transmitting and receiving sides after removing the frequency spectrum components (less than f168) of less than one week, which are common fluctuation components.

<< Procedure 5: Calculation process of evaluation value CA of fluctuation tendency >>
The topology estimation device 1 extracts the traffic-specific feature values of the IFa and IFb on the transmission / reception side by any one of the above procedures 4-1 to 4-5, and then performs a variation tendency (random variation component) of each feature value by the procedure 5. ) And the evaluation value CA of the variation tendency of the feature amount is calculated from the degree of coincidence.
The evaluation value CA of the fluctuation tendency is a value indicating the degree of coincidence of the fluctuation tendency of each feature amount of the transmission traffic and the reception traffic, and the smaller the value, the higher the degree of coincidence. Further, the degree of coincidence of the fluctuation tendency is normalized to a value between 0 and 1. If the fluctuation trends are completely the same, “0” is taken. The value normalized in this way is set as an evaluation value CA of the variation tendency of the feature amount.

As a method for calculating the evaluation value CA, a method using a correlation coefficient and a method using the degree of coincidence of difference codes will be described as examples, but the present invention is not limited to this.
Further, in the procedure 5, for each time series of the total traffic reception amount Rsum (t) of the k IFs and the total traffic transmission amount Tsum (t) of the k traffics, the following procedure 5-1 or The evaluation value CA of the fluctuation tendency is calculated by the process of 5-2.

<< Procedure 5-1: Calculation Example of Fluctuation Trend Evaluation Value CA Using Correlation Coefficient >>
When a correlation coefficient is used as a method of calculating the evaluation value CA of the fluctuation tendency, a time-series correlation coefficient Cor of the random fluctuation ε of Rsum (t) and Tsum (t) is obtained. The correlation coefficient Cor takes a value from 0 to 1, and is “1” when there is a complete positive correlation. For this reason, the evaluation value CA of the fluctuation tendency is the difference between “1” and the correlation coefficient Cor, as represented by the following (Expression 7).

CA = 1-Cor (Expression 7)
If the time series synchronization of the random variation ε between Rsum (t) and Tsum (t) is high, the correlation coefficient Cor approaches “1”, and thus the evaluation value CA of the variation tendency approaches “0”.

  As an example, when the values of Table 201b and Table 202b shown in FIG. 2 are used, Rsum (t) and Tsum (t) are as shown in Table 1 below.

From Table 1, the correlation coefficient Cor of Rsum (t) and Tsum (t) is “0.9918”. Therefore, the evaluation value CA of the fluctuation tendency is the next value close to “0”.
CA = 1-0.9918
= 0.0082

<< Procedure 5-2: Calculation Example of Fluctuation Trend Evaluation Value CA Using a Difference Sign >>
When the sign of the difference is used as the method of calculating the evaluation value CA of the fluctuation tendency, the first order difference (first order lag difference) is obtained for each time series of Rsum (t) and Tsum (t). The degree of coincidence C2 between the positive and negative signs “+” or “−” of the obtained difference time series is obtained by an expression “number of data with positive and negative signs matched ÷ number of observation data”. By substituting this degree of coincidence C2 into the following (formula 8), an evaluation value CA of the fluctuation tendency is obtained.

CA = 1-C2 (Formula 8)
If the synchronization of the time series of the coincidence fluctuation ε of Rsum (t) and Tsum (t) is high, the coincidence degree C2 of the difference sign approaches “1”, and therefore the evaluation value CA of the fluctuation tendency becomes “0”. Get closer.

  As an example, when the values of Table 201b and Table 202b shown in FIG. 2 are used, the time series differences (Tsum-diff, Rsum-diff) of Tsum (t) and Rsum (t) are as follows: It becomes 2 streets.

  From Table 2, the number of observation data is “5”, and the number of data in which the positive and negative signs “+” or “−” match in each time series difference is “5”, so the degree of coincidence C2 = 5 ÷ 5 = 1. When this is substituted into (Equation 8), the fluctuation tendency evaluation value CA = 1-1 = 0.

<< Procedure 6: Connectivity determination process between IFs of each node >>
By using (Principle 1B) and (Principle 2) as determination conditions, the topology estimation apparatus 1 determines the topology (connection relationship) between the IFs of each node in the first determination by the following procedure 6A and the first determination by the procedure 6B. 2. Determine in order of determination.

<< Procedure 6A: Connectivity First Determination Process >>
First, the topology estimation apparatus 1 obtains the result (multiplication result) of CA × p (t), which is the product of the degree of balance p (t) obtained in step 3 and the evaluation value CA of the fluctuation tendency obtained in step 5. Then, it is determined by the following (Equation 9) whether or not the allowable error σ (FIG. 9) is less than or equal to all the times t.

  CA × p (t) ≦ σ (Formula 9)

  Next, when CA × p (t) satisfies CA × p (t) ≦ σ, the topology estimation device 1 has a small difference in input / output traffic volume between the IF subsets to be determined, and Therefore, it is determined that the fluctuation tendency of the input / output traffic value is high and satisfies (Principle 1B).

<< Procedure 6B: Second connectivity determination process >>
The topology estimation device 1 receives information on the transmission / reception traffic amount of k IFs of the IF subset that is a determination candidate, that is, IF1 (t). out-IFk (t). out and IF1 (t). in to IFk (t). Using the in information, the following (Equation 10) is calculated to determine whether (Principle 2) is established.

  IFi (t). out ≦ (total of IF1 (t) .in to IFk (t) .in, excluding IFi (t) .in) [i = 1, 2,..., k] (Equation 10)

  The topology estimation apparatus 1 sequentially extracts one IF from the IF subset as a candidate for determination, and the transmission byte amount of the extracted IF is equal to or less than the sum of the reception byte amounts of all the IFs excluding the extracted IF. It is determined by the relational expression (Expression 10). The topology estimation apparatus 1 assumes that the IF subset satisfies (Principle 2) when (Equation 10) holds at all times t.

The traffic transmission / reception amount changes with time, and a slight error may occur due to a shift in transmission / reception data collection timing. For this reason, the second determination may be performed by transforming into the following (Expression 11) using the allowable error γ (FIG. 9) in the above (Expression 10).
IFi (t). out ≦ (total of IF1 (t) .in to IFk (t) .in, excluding IFi (t) .in) + γ (Expression 11)

≪Procedure 7: Data storage and flag update process≫
When the determination between the procedure 6A (Principle 1B) and the procedure 6B (Principle 2) is established, the topology estimation apparatus 1 sets the IF subset to be determined, for example, “IFa1, IFb2” as the IF connection information 340 (FIG. Save to 8). Further, the flag of “IFa1, IFb2” (however, IFb2 is not shown in FIG. 6) in the connection determination flag information 325 (FIG. 6) is updated to “1”.

  Next, the topology estimation apparatus 1 in the “IF subset” column of the connection determination candidate information 330 (FIG. 7) all information in the first row of the subset including the connection determination flag “1”, for example, “IFa1”. Is deleted. The reason for this deletion will be described. As described above, when the flag of “IFa1” is updated to “1”, “IFa1” that has become “1” has a connection partner. As a connection rule, “IFa1” can be connected to only one partner. For this reason, the subset (group) in which “IFa1” exists in the connection determination candidate information 330 cannot be connected to other IFs, and is thus deleted from the connection determination candidates.

<< Procedure 8: End determination process >>
If the number of IFs with the flag “0” is larger than the current value of k, the topology estimation apparatus 1 increases the value of k by “1” and returns to step 3. On the other hand, when the number of IFs of the flag “0” is equal to or less than the current value of k (condition P1), the topology estimation process is terminated.

  The end determination process will be specifically described. Here, since k = “2”, IF means two combinations. For example, when there are three IFs, IFa, IFb, and IFc, if k = “2”, there are three connection combinations of “IFa, IFb”, “IFb, IFc”, and “IFc, IFa”. is there. At this time, when “IFa, IFb” is connected, each flag of “IFa, IFb” becomes “1”, and only the IFc of flag “0” remains. Since the remaining flag “0” has only one IFc, it cannot be connected to the other party. In this case, since the number of IFs of the flag “0” = “1” and k = “2”, when this is applied to the above-described determination condition P1, the condition P1 is satisfied. In this case, the topology estimation process ends.

  On the other hand, if none of the above three connection combinations satisfy (Principle 1), neither IFa, IFb, or IFc can be connected. In this case, the procedure reaches step 8 with all the IFa, IFb, and IFc flags being “0”. In procedure 8, since the flags of all IFa, IFb, and IFc are “0” and the number of IFs of “0” = “3”, it becomes larger than k = “2” and is out of the condition P1.

If the condition P1 is not satisfied, the value of k is increased by “1”, and k = “3” is set and the procedure returns to step 3. When k = “3”, there are only one combination in which three IFa, IFb, and IFc are connected.
In this case, after returning to the procedure 3, the procedures 4 to 7 are performed, and when returning to the procedure 8 again, the flags of IFa, IFb, and IFc are “1”. Since the subset (group) in which IFa, IFb, and IFc having the flag “1” exist can no longer be connected, in Step 7, it is deleted from the candidates of the connection determination candidate information 330.
Accordingly, since the number of IFs of 0 = “0” and k = “3”, the topology estimation process is completed when the condition P1 is satisfied.

<Configuration of topology estimation device>
Next, the configuration of the topology estimation apparatus 1 according to this embodiment will be specifically described.
FIG. 16 is a block diagram showing the configuration of the topology estimation apparatus 1 according to this embodiment. The topology estimation apparatus 1 is connected to a network management apparatus that manages the entire network and each node (apparatus) that configures the network, thereby acquiring information on IF of each node, and a topology between the nodes that configure the network. presume. Specifically, a combination of IFs connected as subnets is specified.

As shown in FIG. 16, the topology estimation device 1 includes a processing unit 10, an input / output unit 20, and a storage unit 30.
The input / output unit 20 performs input / output of information between devices such as a network management device (not shown) and each node constituting the network. The input / output unit 20 includes a communication interface (not shown) that transmits and receives information via a communication line, and an input / output interface that performs input / output with an input unit such as a keyboard and an output unit such as a monitor. It is prepared for.

  The storage unit 30 includes storage means such as a hard disk, a flash memory, and a RAM (Random Access Memory). The storage area includes a node list storage unit 31, an IF data storage unit 32, a connection determination candidate storage unit 33, and a connection list storage. The unit 34 and the parameter storage unit 35 are set.

  The node list storage unit 31 stores node IF correspondence information 310 (FIG. 4). The IF data storage unit 32 stores IF transmission / reception amount information 320 (FIG. 5) and connection determined flag information 325 (FIG. 6). The connection determination candidate storage unit 33 stores connection determination candidate information 330 (FIG. 7). The connection list storage unit 34 stores IF connection information 340 (FIG. 8). The parameter storage unit 35 stores allowable error information 350 (FIG. 9).

  The node IF correspondence information 310 is information indicating which IF each node (apparatus) includes. As shown in FIG. 4, the node IF correspondence information 310 is associated with the “node name” of each node and includes IF identification information. A certain “IF name” is stored. For example, the node “A” in the first row stores “IFa1”, “IFa2”, “IFa3”,.

  The IF transmission / reception amount information 320 is information indicating the transmission / reception traffic amount at a certain time for each IF. As shown in FIG. 5, “transmission traffic amount” and “reception traffic amount” are associated with each “time”. Is stored. For example, as IF transmission / reception amount information 320 of IFa1, transmission traffic amounts “10”, “14”,..., “25” and reception traffic amounts “31”, “25” at times t1, t2,. 28 ”,...,“ 45 ”are stored in association with each other.

  The connection determination flag information 325 is information set in association with the IF transmission / reception amount information 320 for each IF of each node, that is, for each IF whose topology is to be estimated. As shown in FIG. Each of IFa1, IFa2,..., IFxy is stored in association with the connection determined flag “0” or “1”. The flag is assigned “0” when it is determined that there is no connection relationship with another IF, and is “1” when it is determined that there is a connection relationship. Note that all the initial values of the flags are set to “0”. For example, each time the new IF transmission / reception amount information 320 is stored in the IF data storage unit 32, a flag is set in the connection determination completed flag information 325 in association with the IF of the IF transmission / reception amount information 320. It has come to be. This setting control will be described later.

  As illustrated in FIG. 7, the connection determination candidate information 330 is information in which “balance” and “evaluation value CA of fluctuation tendency” are set in association with each “IF subset”. For example, “0.01” of “Equilibrium” and “0.01” of “Evaluation value CA of fluctuation tendency” are associated with IFa1 and IFb2 in the first row which is “IF subset”. Stored.

  The IF connection information 340 stores IFs having a connection relationship, that is, a combination of IFs determined to constitute a subnet. For example, as shown in FIG. 8, “IFa1, IFb2” is stored in the first row as information on a combination of IFs having a connection relationship.

  As shown in an example in FIG. 9, the allowable error information 350 includes an allowable error σ = 0.1 used in the determination of (Principle 1B) and an allowable error γ = 0.1 used in the determination of (Principle 2). Information.

  The processing unit 10 illustrated in FIG. 16 controls the entire topology estimation apparatus 1 and executes a topology estimation process between nodes. The processing unit 10 includes an information input unit 11, a determination candidate generation unit 12, a balance calculation unit 13, a time series processing unit 14, an evaluation value calculation unit 15, a connection relationship determination unit 16, and an estimation end determination unit. 17 and an information output unit 18. Note that the processing unit 10 is realized by, for example, a CPU (Central Processing Unit) developing a program stored in the storage unit 30 in a RAM and executing the program.

  The information input unit 11 receives, from the network management device or the like, via the input / output unit 20, node IF correspondence information 310 indicating a correspondence relationship between a node and an IF included in the node, IF transmission / reception amount information 320 for each IF, The allowable error information 350 including the allowable error σ and the allowable error γ (FIG. 9) is received and stored in the storage unit 30. The node IF correspondence information 310 is stored in the node list storage unit 31, the IF transmission / reception amount information 320 is stored in the IF data storage unit 32, and the allowable error information 350 is stored in the parameter storage unit 35.

The determination candidate generation unit 12 performs IF subset creation processing and initial setting processing, which are topology determination targets according to the above-described procedures 1 and 2.
That is, the determination candidate generation unit 12 generates all subsets of IFs, and includes “empty set”, “subset with IF number“ 1 ””, and “subset in which all IFs belong to the same node”. Remove. Further, the determination candidate generation unit 12 sets k (for example, k = 2), which is the number of IFs in the IF subset, as an initial setting value.

  Further, the determination candidate generation unit 12 acquires the IF transmission / reception amount information 320 for each IF of each node from the IF data storage unit 32 of the storage unit 30 and also acquires the node IF correspondence information 310 from the node list storage unit 31. To do. In this acquisition, the determination candidate generation unit 12 refers to the connection determination flag information 325 in the IF data storage unit 32 and acquires the IF transmission / reception amount information 320 whose flag is “0”.

  The determination candidate generation unit 12 sets the number of IF transmission / reception amount information 320 of the acquired flag “0”, that is, the number of determination candidate IFs to “n”. Then, the determination candidate generation unit 12 generates a combination of k IFs from the n IFs. The determination candidate generation unit 12 stores the generated IF combination in the IF subset column of the connection determination candidate information 330 (FIG. 7).

  The balance degree calculation unit 13 performs a balance degree calculation process for the IF subset according to the procedure 3. That is, the balance calculation unit 13 stores the IF number of the IF subset that is the determination candidate stored in the connection determination candidate information 330 by the determination candidate generation unit 12 and the IF transmission / reception amount information 320 corresponding to the IF of the subset. The described IF transmission / reception traffic volume time series data is substituted into the above-described (Equation 3) to calculate the balance p (t). The calculated balance p (t) is written in the “balance” column of the connection determination candidate information 330 by the process of the balance calculator 13.

  The time-series processing unit 14 performs the removal process of the fluctuation component having commonality such as burst traffic according to the procedure 4 and extracts the feature quantity that is a chance fluctuation component. The procedure 4 includes at least five procedures 4-1 to 4-5 as described above. In the following description, the time series processing unit 14 uses the Fourier transform according to the procedure 4-3. It is assumed that the fluctuation component removal process is performed.

  That is, the time-series processing unit 14 acquires the IF transmission / reception amount information 320 from the storage unit 30, and the k IF traffic transmission amount total value Tsum (t) and the k IF traffic reception amount total value Rsum. Fourier transform is performed on each time-series data with (t). By this Fourier transformation, the time series data on each of the transmitting and receiving sides is converted into a plurality of frequency spectra. The time series processing unit 14 removes the frequency spectrum of the frequency component common to the transmission side and the reception side from the plurality of frequency spectra on each of the transmission and reception sides. Thereby, the fluctuation component having commonality is removed, and the frequency spectrum which is the fluctuation component having no commonality is extracted.

  Further, the time series processing unit 14 performs inverse Fourier transform on the extracted frequency spectrum to return to the original time series data format on the transmission / reception side. Each returned time-series data becomes a feature amount that is a coincidence variation component on each of the transmission and reception sides. A coincidence fluctuation component is a fluctuation component having no commonality.

  The evaluation value calculation unit 15 performs processing for calculating the evaluation value CA of the variation tendency of the feature amount according to the procedure 5. As described above, the procedure 5 includes at least two procedures 5-1 and 5-2. In the following description, the evaluation value calculation unit 15 uses the correlation coefficient according to the procedure 5-1 to change the trend. The evaluation value CA is calculated.

That is, the evaluation value calculation unit 15 acquires the IF subset that is a determination candidate stored in the connection determination candidate information 330 and the IF transmission / reception amount information 320 of each IF indicated in the IF subset. After the acquisition, the evaluation value calculation unit 15 obtains a time-series correlation coefficient Cor of the accidental variation ε between Tsum (t) and Rsum (t) from the IF transmission / reception amount information 320 of each IF. Then, the evaluation value calculation unit 15 obtains a fluctuation tendency evaluation value CA by substituting the correlation coefficient Cor into the above-described (Equation 7), and this evaluation value CA is stored in the connection determination candidate storage unit 33. The information is written in the “fluctuation tendency evaluation value CA” field of the connection determination candidate information 330 (FIG. 7).
If the time series synchronization of the random variation ε between Rsum (t) and Tsum (t) is high, the correlation coefficient Cor approaches “1”, and thus the evaluation value CA of the variation tendency approaches “0”. It will be.

  The connection relation determination unit 16 performs connectivity determination processing between IFs of each node using (Principle 1B) and (Principle 2) according to the procedure 6 (6A, 6B) as a determination condition. 7 performs data storage and flag update processing.

  First, the connection relationship determination unit 16 obtains the result of CA × p (t), which is the product of the balance p (t) described in the connection determination candidate information 330 and the evaluation value CA of the fluctuation tendency, by the procedure 6A. Whether or not the tolerance error σ (FIG. 9) is less than or equal to all the times t is determined by (Equation 9) of CA × p (t) ≦ σ. The connection relationship determination unit 16 determines that the IF subset to be determined has a small difference in input / output traffic volume when CA × p (t) satisfies CA × p (t) ≦ σ. It is determined (first determination) that the fluctuation tendency of the input / output traffic value is highly synchronized and (Principle 1B) is satisfied.

  Next, the connection relationship determination unit 16 acquires the IF transmission / reception amount information 320 and the allowable error γ (FIG. 9) of the IF to be determined from the storage unit 30 by the procedure 6B. Then, the connection relationship determination unit 16 determines whether or not the above (Equation 10) is satisfied based on the acquired time-series data of the IF transmission / reception traffic volume, and at all times t, (Equation 10) When satisfied, it is determined that (Principle 2) is satisfied (second determination).

  When there is a possibility that a slight error may occur in the traffic transmission / reception amount as described above, the connection relationship determination unit 16 considers the allowable error γ in the determination of (Equation 10) in order to eliminate the error. The second determination may be performed according to (Equation 11).

  Next, when the determinations of (Principle 1B) and (Principle 2) are established, the connection relationship determination unit 16 transfers the IF subset, for example, “IFa1, IFb2” to the IF connection information 340 (FIG. 8) according to Procedure 7. Then, the flag of IFa1 and IFb2 in the connection determination completed flag information 325 (FIG. 6) corresponding to the stored information is updated to “1”. Further, the connection relation determination unit 16 includes all information including the IF name of the flag “1”, for example, “IFa1” among the IF names described in the “IF subset” column of the connection determination candidate information 330 (FIG. 7). “IF name, balance and evaluation value CA of fluctuation tendency” are deleted.

  The estimated end determination unit 17 performs end determination processing according to procedure 8. That is, the estimation end determination unit 17 refers to the connection determination flag information 325 (FIG. 6) corresponding to each IF stored in the IF data storage unit 32, the number of IFs whose flag is “0”, and the current Compare with the value of k. When the number of IFs with the flag “0” is larger than the value of k, the connection relationship determination unit 16 increases the value of k by “1” and outputs it to the determination candidate generation unit 12 to continue the topology estimation process To do. On the other hand, if the number of IFs with the flag “0” is equal to or less than the current value of k, the connection relationship determination unit 16 ends the topology estimation process.

  The information output unit 18 outputs the IF connection information 340 stored in the connection list storage unit 34 to the network management device, the monitor provided in the topology estimation device 1 or the like via the input / output unit 20.

<Process flow>
Next, the flow of the topology estimation process of the topology estimation apparatus 1 according to this embodiment will be described. 17 and 18 are flowcharts showing the flow of the topology estimation process of the topology estimation apparatus 1 according to this embodiment.

First, in step S1 shown in FIG. 17, the information input unit 11 of the topology estimation device 1 receives node IF correspondence information 310 (FIG. 4), IF transmission / reception amount information 320 (FIG. 5) for each IF, from the network management device or the like. The allowable error σ and the allowable error γ (FIG. 9) are acquired and stored in the storage unit 30.
At this time, when the IF transmission / reception amount information 320 is stored in the storage unit 30, the determination candidate generation unit 12 initially sets the flag of the connection determination completed flag information 325 (FIG. 6) corresponding to the IF of the IF transmission / reception amount information 320. The value is “0”.

  Next, in step S2, the determination candidate generation unit 12 generates all subsets of IFs, and “empty set”, “subset with IF number“ 1 ””, “all IFs belong to the same node”. ”Is removed, and all IFs in the IF subset after the removal are determined as topology estimation determination targets.

  Next, in step S <b> 3, the determination candidate generation unit 12 sets the IF number “k” of the IF subset to an initial setting value of k = 2.

  Next, in step S <b> 4, the determination candidate generation unit 12 acquires IF transmission / reception amount information 320 for each IF from the IF data storage unit 32 of the storage unit 30. Further, the determination candidate generation unit 12 refers to the connection determination flag information 325 in the IF data storage unit 32 and acquires the IF transmission / reception amount information 320 whose flag is “0”.

  After the acquisition, the determination candidate generation unit 12 sets the number of IF transmission / reception amount information 320 of the acquired flag “0”, that is, the number of determination candidate IFs to “n”, and from these n IFs, k determinations are made. Generate a combination of IFs. Then, the determination candidate generation unit 12 stores the IF combination that is the generated determination candidate in the “IF subset” column of the connection determination candidate information 330 (FIG. 7).

  Next, in step S5, the balance calculation unit 13 calculates the balance p (t) for the IF subset generated as the determination candidate in step S4. Specifically, the balance calculation unit 13 acquires an IF subset that is a determination candidate stored in the connection determination candidate information 330 in the storage unit 30, and the IF transmission / reception amount of each IF indicated in the IF subset Information 320 is acquired.

  Then, the balance calculator 13 obtains the number of IFs of the acquired IF subset and the time series data of the traffic volume of each IF transmission / reception described in the IF transmission / reception volume information 320 corresponding to each IF as described above. Substituting into (Equation 3), the balance p (t) is calculated. The balance calculation unit 13 writes the calculated balance p (t) in the “balance” column of the connection determination candidate information 330 shown in FIG.

  Next, in step S6, the time-series processing unit 14 calculates a variation component having commonality such as burst traffic from the traffic component transmitted / received between IFs of the IF subset generated as the determination candidate in step S4. Removal is performed, and after this removal, feature amounts that are fluctuation components having no commonality are extracted.

  For example, the time-series processing unit 14 acquires the IF transmission / reception amount information 320 of each IF corresponding to the IF subset from the node list storage unit 31, and k = 2 total IF traffic transmission amount Tsum (t) Then, Fourier transform is performed on each time series data of the traffic reception amount total value Rsum (t) of k = 2 IFs. For example, as shown in the lower and upper graphs of FIG. 13 (a), each of the time series data based on the time series waveform Wa4 of k IFa Tsum (t) and the Rsum (t) of k IFb Fourier transform is performed on the time series data based on the time series waveform Wb4.

  By this Fourier transformation, the time series data on each of the transmitting and receiving sides is converted into a plurality of frequency spectra. Therefore, the time series processing unit 14 removes the frequency spectrum of the frequency component common to the transmission side and the reception side from the plurality of frequency spectra on each of the transmission and reception sides. That is, the fluctuation component having the commonality is removed, and the frequency spectrum that is the fluctuation component having no commonality is extracted.

  This removal and extraction processing is converted into five frequency spectra f1 to f5 shown in the lower and upper graphs of FIG. Next, frequency spectra f1, f3, and f4 of frequency components that are common on the transmitting and receiving sides (lower and upper graph sides) are removed from the frequency spectra f1 to f5. By this removal, frequency spectra f2 and f5 having no commonality shown in the lower and upper graphs of FIG. 13C are extracted.

  Next, the time series processing unit 14 performs inverse Fourier transform on the extracted frequency spectra f2 and f5, and returns them to the time-domain waveforms Wa5 and Wb5 shown in FIG. These waveforms Wa5 and Wb5 are characteristic amounts on the transmitting and receiving sides after the frequency spectra f1, f3, and f4 of the common frequency components are removed.

Next, in step S7, the evaluation value calculation unit 15 calculates the evaluation value CA of the tendency to change in the feature amounts on the transmitting and receiving sides obtained in step S6. For example, the evaluation value calculation unit 15 obtains a time-series correlation coefficient Cor of the coincidence variation ε corresponding to each feature amount on the transmission / reception side, and sets the correlation coefficient Cor to (Equation 7) where CA = 1−Cor. By substituting, the evaluation value CA of the fluctuation tendency is calculated. The evaluation value calculation unit 15 writes the calculated evaluation value CA of the fluctuation tendency in the “fluctuation tendency evaluation value CA” column of the connection determination candidate information 330 (FIG. 7) in the storage unit 30.
Here, if the time series synchronization of each chance variation ε is high, the correlation coefficient Cor approaches “1”, and thus the evaluation value CA of the variation tendency approaches “0”.

Next, in step S8 of FIG. 18, the connection relationship determination unit 16 refers to the connection determination candidate information 330, sequentially extracts one IF from the IF subset, and satisfies (Principle 1B). The “first determination” in which the above determination is performed using the above (formula 9), and the “second determination” in which the determination whether the (principle 2) is satisfied is performed using the above (formula 10). Do.
However, when performing the “second determination”, the connection relationship determination unit 16 may perform the determination according to the above-described (Expression 11) in consideration of the allowable error γ.

Next, in step S <b> 9, the connection relationship determination unit 16 determines whether or not the extracted IF subset satisfies both determination conditions (both determination conditions) of “first determination and second determination”.
If both determination conditions are satisfied (Yes), the process proceeds to step S10. In step S10, the connection relation determination unit 16 stores the IF subset satisfying both determination conditions, for example, “IFa1, IFb2” in the IF connection information 340 (FIG. 8), and the connection determination flag information corresponding to the storage information. The flags of IFa1 and IFb2 in 325 (FIG. 6) are updated to “1”.

  Further, in step S11, the connection relationship determination unit 16 includes any IF whose flag is updated to “1” in step S10 in the IF subset of the connection determination candidate information 330 (FIG. 7). All the information of the subset “IF subset, balance degree, fluctuation tendency evaluation value CA” is deleted. After this deletion, the process proceeds to step S12.

  On the other hand, if the determination result in step S9 does not satisfy both determination conditions, that is, if any one of “first determination and second determination” is not satisfied (No), the process proceeds to step S12.

In step S12, the connection relationship determination unit 16 has performed the connection relationship determination processing in steps S8 and S9 for all the IF subsets with the IF number k = “2” generated as the determination candidates in step S4. Determine whether or not. As a result, when all the determination processes are not performed (No), the process returns to step S8 and continues.
On the other hand, when all the determination processes have been performed as a result of the determination in step S12 (Yes), the process proceeds to the next step S13.

In step S13, the estimation end determination unit 17 determines that the number of IFs “n” whose flag of the connection determination completed flag information 325 is “0” at the present time is the k value (initial value k = 2) set in step S4. ) Determine whether or not: As a result, when it is not less than k, that is, when it is larger than the value of k (No), the process proceeds to step S14, and after setting the value of k to a value obtained by adding “1” to the current k, the step of FIG. Return to S4 and continue processing.
On the other hand, when it is k or less (Yes), the estimation end determination unit 17 ends the topology estimation process.

  After that, in step S15, the information output unit 18 sends the IF connection information 340 stored in the connection list storage unit 34 of the storage unit 30 to the network management device or the topology estimation device 1 via the input / output unit 20. Output to a monitor or the like provided in

<Effect of embodiment>
As described above, the topology estimation device 1 according to the present embodiment, when estimating the connection relationship between nodes as devices constituting the network, transmits each traffic on the transmission side and reception side between IFs included in the node. From the time series information, the fluctuation component common to each traffic component is removed, and the coincidence fluctuation that is not common to the transmission side and the reception side is extracted, and the extracted time series information of each coincidence fluctuation is extracted. If there is synchronization, the processing unit 10 is determined to determine that there is a connection relationship between IFs.

  According to this configuration, the fluctuation component common to each traffic component on the transmission / reception side between the IFs of the nodes, which causes a misjudgment of connection determination between the nodes, is removed, and the accidental fluctuation that is a fluctuation that does not have commonality on the transmission / reception side Was extracted. For this reason, there is no cause for erroneous determination of connection between nodes. After the extraction, if the time series information of each coincidence change in transmission and reception is synchronous, it is determined that there is a connection relationship between IFs, and therefore the connection relationship between nodes can be determined appropriately without erroneous determination.

The topology estimation apparatus 1 of the present embodiment that obtains this effect performs connection determination between IFs of nodes using (Principle 1B) and (Principle 2), which are extensions of the above (Principle 1A), as determination conditions.
Here, in the topology estimation apparatus that performs connection estimation between IFs using (Principle 1A) and (Principle 2) as determination conditions, the following effects are obtained. In other words, considering the fluctuation trend of the transmission / reception traffic volume of each node, if the measurement method of the transmission / reception traffic volume of each node is different, that is, the device specifications are different, there is a difference in the transmission / reception traffic volume at a certain rate Even in this case, the possibility of correctly evaluating the connection relationship without erroneous estimation or estimation omission can be greatly improved. For this reason, the connection relationship (topology) between IFs can be estimated with improved accuracy.

  Therefore, in the topology estimation apparatus 1 of the present embodiment in which (Principle 1B) and (Principle 2) are extended as the (Principle 1A) criteria, the effect of the topology estimation apparatus according to (Principle 1A) and (Principle 2) is also achieved. Can be obtained. Therefore, even if the method of measuring the amount of transmitted / received traffic at each node is different, the connection relationship (topology) between IFs can be estimated with improved accuracy without erroneous determination.

  The processing unit 10 includes at least an information input unit 11, a determination candidate generation unit 12, a balance calculation unit 13, a time series processing unit 14, an evaluation value calculation unit 15, and a connection relationship determination unit 16. It is prepared for.

The storage unit 30 stores IF transmission / reception amount information 320 in which information on a time-series transmission traffic amount and reception traffic amount of each IF included in the node is stored for each IF.
The determination candidate generation unit 12 refers to the IF transmission / reception amount information 320 for each IF, and connects all IF combinations including k IFs (k ≧ 2) that are the number of IFs constituting the subnet. Is generated as a determination candidate.

The balance calculation unit 13 is the absolute value of the difference obtained by subtracting the total value of the transmission traffic amount from the total value of the reception traffic amount of each IF constituting the combination of IFs that are the determination candidates generated by the determination candidate generation unit 12. The degree of equilibrium indicating is calculated.
The time-series processing unit 14 removes a common fluctuation component in each traffic component transmitted and received from the traffic components transmitted and received between the IFs constituting the combination of IFs that are candidates for determination, and remains after this removal. Then, a feature amount (a chance variation component) that is a variation component having no commonality is extracted.

The evaluation value calculation unit 15 calculates the variation of the feature amount of each transmission / reception from the time-series relationship between the total value of the received traffic amount and the total value of the transmission traffic amount of each IF that constitutes the combination of IFs that are candidates for determination. An evaluation value indicating the degree of coincidence of trends is calculated.
The connection relationship determination unit 16 extracts one IF from a combination of a first determination that determines that the result of multiplication of the balance and the evaluation value is equal to or less than a predetermined value, and an IF that is a determination candidate. A second determination that determines for all IFs that constitute a combination of IFs that are candidates for determination that the transmission traffic amount of the IF is equal to or less than the sum of the reception traffic amounts of all IFs except the extracted IF Both determinations are performed for each combination of IFs that are candidates for determination, and when both determinations are satisfied, it is determined that there is a connection relationship between IFs that constitute the combination of IFs that are candidates for determination.

  In addition, the storage unit 30 further stores node IF correspondence information 310 in which identification information of IF included in each node is stored. The determination candidate generation unit 12 refers to the node IF correspondence information 310 for each of the generated IF combinations as determination candidates, and if there is no IF that constitutes the IF combination as a determination candidate, the combination of IFs as determination candidates If the number of IFs constituting the IF is “1”, all IFs constituting the combination of IFs that are candidates for determination belong to one node. This information is deleted from the generated IF combination.

  According to this configuration, IF combination information that cannot be connected between IFs is deleted, so that unnecessary connection determination processing can be eliminated. For this reason, topology estimation between nodes can be performed efficiently.

  In addition, the storage unit 30 includes connection determination candidate information 330 that stores combinations of IFs that are determination candidates, and IF connection information 340 that stores combinations of IFs that are determined to have a connection relationship by the connection relationship determination unit 16. I also remember. The connection relation determination unit 16 determines the IF including IF if the IF combination stored in the connection determination candidate information 330 includes any of the IFs that constitute the IF combination stored in the IF connection information 340. The combination information is deleted from the connection determination candidate information 330.

  This configuration is realized as follows, for example. The connection relationship determination unit 16 stores an IF subset as a combination of IFs, for example, “IFa1, IFb2” in the IF connection information 340 (FIG. 8), and connection determined flag information 325 (FIG. 6) corresponding to this storage information. The flags of IFa1 and IFb2 in () are updated to “1”. Further, the connection relation determination unit 16 includes all information including the IF name of the flag “1”, for example, “IFa1” among the IF names described in the “IF subset” column of the connection determination candidate information 330 (FIG. 7). “IF name, balance and evaluation value CA of fluctuation tendency” are deleted.

  According to this configuration, IFa1 stored in the IF connection information 340 has a connection partner IFb2 and cannot currently have other IFs. For this reason, if IFa1 is deleted from the connection determination candidate information 330, topology estimation between nodes can be performed efficiently.

The present invention can also be embodied as a program for causing a computer to function as the topology estimation apparatus 1.
In addition, about a concrete structure, it can change suitably in the range which does not deviate from the main point of this invention.

DESCRIPTION OF SYMBOLS 1 Topology estimation apparatus 10 Processing part 11 Information input part 12 Determination candidate production | generation part 13 Balance degree calculation part 14 Time series processing part 15 Evaluation value calculation part 16 Connection relation determination part 17 Estimation completion | finish determination part 18 Information output part 20 Input / output part 30 Storage unit 310 Node IF compatible information (device IF compatible information)
320 IF transmission / reception amount information 325 Connection determination completed flag information 330 Connection determination candidate information 340 IF connection information 350 Allowable error information

Claims (5)

A topology estimation device for estimating a connection relationship between devices constituting a network,
Fluctuation that does not have commonality on the transmission side and the reception side is removed from the time series information of each traffic on the transmission side and reception side between IF (Interface) with which the device is provided. A topology estimation apparatus comprising: a processing unit that extracts a coincidence variation, and determines that there is a connection relationship between the IFs if the extracted time-series information of each coincidence variation is synchronous. A topology estimation device for estimating a connection relationship between a plurality of devices constituting a network,
A storage unit that stores IF transmission / reception amount information in which information on a time-series transmission traffic amount and reception traffic amount of each IF included in the device is stored for each IF;
Determination that refers to IF transmission / reception amount information for each IF and generates all IF combinations including k IFs (k ≧ 2) that are the number of IFs constituting a subnet as connection relationship determination candidates A candidate generation unit;
The degree of balance for calculating the degree of balance indicating the absolute value of the difference obtained by subtracting the total value of the transmission traffic amount from the total value of the reception traffic amount of each IF constituting the combination of the generated IFs as the determination candidates A calculation unit;
From each traffic component transmitted / received between IFs constituting the IF combination as the judgment candidate, a common fluctuation component is removed from each traffic component transmitted / received, and the commonality remaining after the removal is obtained. A time-series processing unit for extracting feature quantities that are not fluctuation components;
From the time-series relationship between the total value of the received traffic volume and the total value of the transmission traffic volume of each IF that constitutes the combination of IFs that are candidates for determination, the variation tendency of the feature quantity of each of the transmission and reception An evaluation value calculation unit for calculating an evaluation value indicating the degree of coincidence;
One IF is extracted from the combination of the first determination for determining that the result of multiplication of the balance and the evaluation value is equal to or less than a predetermined value, and the IF that is the determination candidate, and the IF of the extracted IF A second determination for determining, for all IFs constituting the combination of IFs as the determination candidates, that the transmission traffic amount is equal to or less than the sum of the reception traffic amounts of all IFs excluding the extracted IF. The connection relationship for determining that there is a connection relationship between the IFs constituting the combination of IFs that are the determination candidates when both determinations are performed for each combination of IFs that are the determination candidates and both determinations are satisfied. A topology estimation apparatus comprising: a determination unit. The storage unit further stores device IF correspondence information in which identification information of the IF included in each of the devices is stored,
The determination candidate generation unit refers to the device IF correspondence information for each IF combination that is the generated determination candidate, and becomes the determination candidate when there is no IF that constitutes the IF combination that is the determination candidate. If the number of IFs constituting the IF combination is 1, and if all of the IFs constituting the IF combination as the determination candidate belong to one device, the IF corresponding to any of these cases The topology estimation device according to claim 2, wherein the information on the combination of the IF is deleted from the generated IF combination. The storage unit further stores connection determination candidate information for storing a combination of IFs as the determination candidates and IF connection information for storing a combination of IFs determined to have a connection relationship by the connection relationship determination unit. And
The connection relation determining unit, when the IF combination stored in the connection determination candidate information includes any of the IFs constituting the IF combination stored in the IF connection information, includes the IF The topology estimation apparatus according to claim 2 or 3, wherein the combination information is deleted from the connection determination candidate information.   The program for making a computer implement | achieve each function of the topology estimation apparatus of any one of Claims 1-4.

Images