JP6300369B2 - 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.

Therefore, as a technique for estimating the topology, a technique using a transmission / reception traffic amount for each IF (interface) included in the apparatus is disclosed in Non-Patent Document 1 or Patent Document 1. The disclosed topology estimation method 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 or more IFs included in each node N are 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 such a topology estimation method, when s nodes N satisfy both the 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.

Further, Non-Patent Document 1 describes estimation of the connection relationship of nodes N _{1 to} N ₃ including three or more IF ₁ to IF 3 connected to a subnet, as shown in FIG. This estimation is carried out seeking equilibrium degree of 3 or more IF1~IF3 of each node _N 1 to N _3. The degree of balance is obtained by the following (Equation 1).
Balance = (total transmission traffic amount of φ _{1 to} φ _S )
− (Total value of received traffic volume of φ _{1 to} φ _S ) (Equation 1)
However, the balance is expressed as an absolute value.

In the example of FIG. 2, the node _{N 1} of IF3, the node _{N 2} of the IF1, the balance of the IF1 of the node _{N 3,} the sum of the incoming traffic amount to three IF3, IF1, IF1 subnet (amount of transmission traffic) The value and the total value of the outflow traffic amount (reception traffic amount) from the subnet are obtained by fitting to (Equation 1) as follows.
Balance = (total value of transmitted traffic) − (total value of received traffic)
= (50 + 5 + 30)-(15 + 45 + 25)
= 0
Thus, when the inflow and the outflow completely coincide with each other, the balance is “0”. It can be said that the closer the balance is to “0”, the higher the synchronization between the transmission traffic volume and the reception traffic volume.

  When the number of IFs is 3 or more, it is estimated that IFs whose balance is less than a predetermined value (a value equivalent to an allowable error σ described later) and determined not to flow backward are in a connection relationship. However, the determination of “not backflowing” is determined as “not backflowing” when determination formula 2 is satisfied. Hereinafter, the determination that the degree of balance is equal to or less than a predetermined value and that there is no backflow is referred to as “3 or more connection determination”.

JP 2014-49851 A

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

  However, as described with reference to FIG. 2 in the contents described in Non-Patent Document 1, when there are three or more IFs of each node connected to the subnet, topology estimation is performed as described below. Sometimes it cannot be performed with high accuracy.

  For example, as shown in FIG. 3, the amount of traffic (transmission traffic amount) flowing into the subnet from five IF1, IF2, IF3, IF4, and IF5 is “5000”, “500”, “2650”, “20”, It is assumed that the traffic volume (reception traffic volume) flowing out from the subnet to each IF1 to IF5 is “2650”, “1500”, “4000”, “5”, “30”. However, IF1 to IF5 are not shown in FIG. 3, but are provided in each node as shown in FIG.

  As described above, it is assumed that there is a large difference in the amount of transmission / reception traffic (simply referred to as traffic volume) of each IF1 to IF5, in other words, a case where there is a significant difference in the ratio of traffic volume. However, the ratio of the traffic volume of each IF1 to IF5 is the ratio of the traffic volume for each IF1 to IF5 to the total value of the traffic volume of IF1 to IF5. In the example of FIG. 3, the ratio of each traffic volume is expressed as 100 minutes as follows. The ratio of each traffic amount is 46.7% for IF1, 12.2% for IF2, 40.6% for IF3, 0.2% for IF4, and 0.3% for IF5.

  Further, it is assumed that there are seven types of combinations of five IF1 to IF5 as indicated by circles in the first to seventh rows in the table of FIG. The degree of balance of the combination in the first row is obtained as (500 + 2650 + 20 + 15) − (1500 + 4000 + 5 + 30) = | 2350 | (hereinafter, the absolute value symbol is omitted) by (Equation 1) described above. Similarly, the balance of the second row is “1000”, the balance of the third row is “1350”, the balance of the fourth row is “15”, the balance of the fifth row is “15”, the sixth row Is obtained as “6”, and the balance in the seventh row is obtained as “0”.

  Here, it is assumed that the correct connection relationship in the connection example of FIG. 3 is five combinations of IF1, IF2, IF3, IF4, and IF5 in which the balance is “0” as shown in the seventh line of FIG. . As shown in the first to third lines, in the case of a combination in which any of IF1 to IF3 having a large traffic ratio is not present, the degree of balance also increases as “2350” “1000” “1350”. In this case, since the degree of balance is far away from “0”, it can be determined that there is no connection relationship between IF1 to IF5. That is, if it is assumed that the predetermined value for performing the connection determination of 3 or more is, for example, “50”, the balances “2350”, “1000”, and “1350” are all equal to or greater than the predetermined value “50”. The result of connection determination is not satisfied.

  However, as shown in the 4th to 6th lines, the balance is “15”, “15”, “0” in the case of a combination in which either one or both of IF4 and IF5 that have a significantly small traffic volume ratio do not exist. ”And so on. If the traffic volume ratio is much smaller than the traffic volume ratios of the other IF1, IF2 and IF3 as in IF4 and IF5, there is almost no influence that contributes to the balance even if IF4 and IF5 are present. There is nothing.

  Since the balance “15” or “0” is less than the predetermined value “50”, the result of the connection determination of 3 or more is established when the other condition is determined to be “no back flow”. . That is, as in the fourth to sixth lines, in the case of a combination in which either one or both of IF4 and IF5 do not exist, topology estimation is performed that there is originally no connection relationship but there is a connection relationship. . Thus, when there are three or more IFs of nodes connected to the subnet, there is a problem that the accuracy of topology estimation is low.

  The present invention has been made in view of such a background, and a topology estimation device capable of performing topology estimation between nodes with high accuracy even when there are three or more IFs of nodes connected to a subnet, and The challenge is to provide a program.

In order to solve the above-described problem, the invention according to claim 1 is a topology estimation device for estimating a connection relationship between nodes constituting a network, and includes IF (Interface) included in the node as a subnet. A generator that generates k combinations of IFs as connection candidate determination candidates, except that all k IFs (k ≧ 2) that are the number of IFs are provided in the same node , and the generated k The transmission / reception traffic volume for each IF is acquired at a predetermined interval, and the ratio of the transmission / reception traffic volume for each IF to the total value of the transmission / reception traffic volumes for the k IFs is determined for each time. a selection unit that generates a determination value based on the minimum ratio among the ratios, to select the time at which the determined value is equal to or greater than a predetermined threshold value as an analysis target time to the analyzed time Definitive, first error and traffic calculation unit for obtaining the absolute value is balance of the difference between the total value of the total value and the received traffic amount of the transmission traffic amount of each IF, balance of the analyzed time predetermined in advance One IF is extracted from the combination of the first determination condition for determining that the time is less than the IF that is the determination candidate at the same analysis target time, and the transmission traffic amount of the extracted IF is the extracted If both of the second determination conditions for determining that the received traffic volume is less than or equal to the sum of the received traffic amounts of all IFs except for the selected IF are selected, a combination of all IFs that satisfy both the selected IFs is selected. And a determination calculation unit that selects an IF combination having the smallest total value obtained by summing a predetermined number of balances of each IF combination as an optimum IF combination. A topology estimation device was used.

  According to this configuration, the following operational effects can be obtained. When k = 3, a ratio (traffic ratio) of the transmission / reception traffic amount of each IF in the combination of three IFs to be subjected to topology estimation is calculated at a predetermined interval time. A time t having a traffic ratio where the ratio is not extremely far away is selected. It is assumed that the balance of the transmission / reception traffic amount of each IF is obtained for each selected analysis target time. In this case, the degree of balance can be obtained only with an IF group having a traffic ratio in which the three IF ratios are not extremely separated, except for a traffic ratio in which the three IF ratios are extremely separated. For this reason, the value of the degree of balance is less likely to be extremely different between analysis target times.

  Furthermore, when the degree of balance satisfies both the first and second determination conditions, the combination of IFs in which the total value obtained by summing a predetermined number of the degree of balance of all three IF combinations satisfying both is the smallest. Are selected as the optimal IF combination. For this reason, since a balance with a smaller value is selected from the balances whose values are not extremely different between the analysis target times, a balance with a value closer to “0” or “0” is selected. Can do.

  The closer the balance degree is to “0”, the higher the synchronization between the transmission traffic amount and the reception traffic amount. Therefore, the combination of IFs whose balance degree is “0” or closer to “0” has a high probability of connection. I know that it can be said. From this, it can be said that the IF combination having a smaller value of balance selected as described above, that is, the optimal IF combination, has a high probability of connection. Thus, even when there are three or more IFs of nodes connected to the subnet, topology estimation between the nodes can be performed with high accuracy.

  In the invention according to claim 2, the second determination condition is that one IF is extracted from a combination of IFs that are the determination candidates at the same analysis target time, and the transmission traffic amount of the extracted IF is: 2. The topology according to claim 1, wherein the topology is a condition for determining that the sum of the received traffic amounts of all IFs excluding the extracted IF is equal to or less than a value obtained by adding a predetermined second error. It is an estimation device.

  According to this configuration, the second determination condition is a condition for determining that the second determination condition is equal to or less than the value obtained by adding the second error, and the first and second errors are shifted from the data acquisition timing of the transmission / reception traffic amount of each IF. If the value corresponds to the error due to the above, it is possible to accept an error in the data of the transmitted / received traffic amount acquired at the time of acquisition.

  The invention according to claim 3 is a program for causing a computer to realize each function of the topology estimation apparatus according to claim 1 or 2.

  Also with this configuration, the same effect as that of the first or second aspect can be obtained.

  According to the present invention, it is possible to provide a topology estimation apparatus and program capable of performing topology estimation between nodes with high accuracy even when there are three or more IFs of nodes connected to a subnet.

It is a figure for demonstrating the subnet comprised by several IF with connection relation. It is a figure which shows the transmission / reception traffic amount between IF of each node. It is a figure which shows the transmission / reception traffic amount between five IF. It is a figure which shows the balance degree of each combination pattern of five IF1-IF5 shown in FIG. It is a figure which shows the bar graph which showed the traffic ratio of three IF connected to the subnet of each node which concerns on this embodiment in every 100 minutes at the time t. It is a figure which shows the data structural example of the node IF corresponding list which concerns on this embodiment. (A) A data configuration example of an IF list according to the present embodiment, (b) a data configuration example of an IF data list, and (c) a data configuration example of a connection determined flag list. It is a figure which shows the example of a data structure of the connection determination candidate list | wrist which concerns on this embodiment. It is a figure which shows the data structural example of IF connection list which concerns on this embodiment. It is a figure which shows the data structural example of the analysis object time list which concerns on this embodiment. (A) It is a figure which shows the data structural example of the allowable error list | wrist containing the allowable error (sigma) and allowable error (gamma) based on this embodiment, and shows the data structural example of (b) threshold value list. It is a figure for demonstrating the optimization process of IF connection relation which concerns on this embodiment. 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. 13) and the program according to the present embodiment will be described.
(Basic concept)
The topology estimation device 1 according to the present embodiment estimates the topology between nodes (devices) constituting a network. The feature of the topology estimation apparatus 1 is that topology estimation between nodes can be performed with high accuracy as will be described later even when there are three or more IFs of nodes connected to the subnet.

Figure 5 (also referred to as traffic ratio) more than two traffic volume ratio of IF1~IF3 connected to the subnet of the nodes _N 1 to N ₃ shown in FIG. 2 r1, a r2, r3, each time t It is a figure which shows the bar graph shown in 100 minutes. However, the transmission / reception traffic amount shown in FIG. 2 is ignored.

  The bar graph shown in FIG. 5 is typically a bar graph surrounded by frames W1, W2, and W3. The bar graph at time t4 in the frame W1 has an IF1 ratio r1 of 42%, an IF2 ratio r2 of 8%, and an IF3 ratio. It indicates that the ratio r3 is 50%. The bar graph at time t9 in the frame W2 has an IF1 ratio r1 of 4%, an IF2 ratio r2 of 57%, and an IF3 ratio r3 of 39%, and the bar graph at time t29 in the frame W3 has an IF1 ratio r1. Is 21%, IF2 ratio r2 is 43%, and IF3 ratio r3 is 36%.

  The bar graph at time t4 has an extremely small IF2 ratio r2 of 8%, and the bar graph at time t9 has an extremely small IF1 ratio r1 of 4%. The bar graph at time t29 does not have an extremely small ratio R, and ratios r1 to r3 of IF1 to IF3 are combined in a well-balanced manner.

  In the present invention, the traffic volume at the time (for example, t4, t9) including the extremely small ratio r in the traffic volume ratios r1 to r3 of each IF1 to IF3 at each time t as shown in FIG. The amount of transmission / reception traffic at a time (for example, t29) that does not include the extremely small ratio R is excluded from the calculation target for estimation. When the transmission / reception traffic volume to be calculated is applied to the judgment formula 3 (described later) based on the principle 1 and the judgment formula 4 (described later) based on the principle 2, and when the judgment formulas 3 and 4 are matched, The optimum combination is selected from the IF combinations. By obtaining the optimum combination of IFs in this way, topology estimation can be performed accurately even when there are three or more IFs of nodes connected to the subnet.

(Outline of processing)
Next, an overview of topology estimation processing executed by the topology estimation apparatus 1 according to the present embodiment will be described.
First, as a premise, in performing the procedure shown below, the storage means (corresponding to the storage unit 30 shown in FIG. 13 described later) of the topology estimation apparatus 1 is stored in the node IF correspondence list 31a shown in FIG. ) To (c), the IF list 32a, the IF data list 32b, and the connection determined flag list 32c, the connection determination candidate list 33a illustrated in FIG. 8, the IF connection list 34a illustrated in FIG. 9, and the analysis illustrated in FIG. Assume that the target time list 35a, the allowable error list 36a including the allowable error σ and the allowable error γ, and the threshold value list 36b including the threshold value ε (k) illustrated in FIG. 11 are stored. 6 to 11 show one configuration example of the above-described lists 31a, 32a, 32b, 32c, 33a, 34a, 35a, 36a, and 36b.

(Processing procedure)
<< Procedure 1: Initial setting process >>
The topology estimation device 1 sets the number k of IFs to be subjected to topology estimation as an initial value. Initially, since the minimum value of the IF connection relation is “2”, k = “2” is set as the initial value. Hereinafter, the number of IFs to be subjected to topology estimation is also referred to as the number of IFs to be estimated, and k of the number of IFs to be estimated is also referred to as a value of k.

<< Procedure 2: Calculation processing of determination value R (t) of traffic ratio of each IF at each time t >>
First, for k IFs (IF1, IF2,..., IFk), ratios r1 (t) to r3 (t) of the transmission / reception traffic amount of each IF at each time t are calculated. For example, when k = 3 in the procedure 1 and calculation is performed for three IFs, the bar graph shown in FIG. 5 is obtained.

Here, the combination of selecting k IF sets (for example, k = 2 IF sets in the initial value) from the IF list 32a {FIG. 7A} having n IF1 to IFn is “ _n C There are “ _k ”. Therefore, after repeating steps 2 to 5 described later for all combinations of k IFs, the process proceeds to step 6 described later. However, the pattern in which the selected k IFs all belong to the same node is ignored. The IF data list 32b is information provided for every n IFs, which will be described in detail later. The n IFs are stored as IF1 to IFn in the IF list 32a shown in FIG.

  Next, the transmission traffic volume and the reception traffic volume at each time t are acquired from the IF data list 32b {FIG. 7 (b)} for each IF constituting each set of k selected IFs. Next, when the number of IFs is k, and the total amount of transmission / reception traffic of each IF (IF1, IF2, ..., IFk) at time t is IF1 (t), IF2 (t), ..., IFk (t), A determination value R (t) of the traffic ratio of each IF at each time t is calculated from the following (Equation 2).

但し、ｘ＝１，２，…，ｋとする。

Here, x = 1, 2,..., K.

  In (Expression 2), () is a calculation expression for obtaining the minimum value min of the traffic amount ratio at each time t for each of IF1 to IFk. For example, if the ratios r1 to r3 of IF1 to IF3 of the bar graph at time t4 in the frame W1 shown in FIG. 5, the minimum ratio IF2 of r2 = 0.08 (8%) is calculated.

When the determination value R (t) of the traffic ratio of each IF at each time t is calculated from (Equation 2), for example, the bar graph at time t4 in the frame W1 has a ratio r1 of IF1 of 0.42 and a ratio of IF2 Since r2 is 0.08 and IF3 ratio r3 is 0.50, R (t) = 0.08 × 3 = 0.24 is obtained from (Equation 2).
The bar graph at time t9 in the frame W2 has a ratio r1 of 0.04, a ratio r2 of 0.57, and a ratio r3 of 0.39, so R (t) = 0.04 × 3 = 0.12.
Since the ratio r1 is 0.21, the ratio r2 is 0.43, and the ratio r3 is 0.36 in the bar graph at time t29 in the frame W3, R (t) = 0.21 × 3 = 0.63 is determined.

<< Procedure 3: Analysis target time selection process using determination value R (t) and threshold value ε (k) >>
In the processing of the procedure 3, the traffic ratio of the IF group that is the target of topology estimation is calculated at each time t of a predetermined interval, and the time t having a traffic ratio that is not extremely separated from each time t. Perform the selection process.

The threshold value ε (k) is used to select the time t when the determination value R (t) of the traffic ratio of each IF at each time t is equal to or greater than the threshold value ε (k) as an analysis target for topology estimation. It is a threshold value. The time selected as the analysis target is referred to as the analysis target time.
The determination value R (t) calculated by the above (Expression 2) is a value that takes a range of 0 ≦ R (t) ≦ 1, and the determination value R (t) is as shown in the following (Expression 3). Is selected as an analysis target time at which t becomes equal to or greater than the threshold value ε (k).

  R (t) ≧ ε (k) (Formula 3)

  For example, when the threshold ε (k) = 0.5 (50%), R (t) at time t4 in the frame W1 shown in FIG. 5 is 0.24 as determined above, and is within the frame W2. R (t) at time t9 is 0.12. Since 0.24 and 0.12 are both less than the threshold value ε (k) = 0.5, the times t4 and t9 are excluded from the analysis target time as indicated by the crosses.

  On the other hand, R (t) at time t29 in the frame W3 is 0.63. Since this 0.63 is equal to or greater than the threshold value ε (k) = 0.5, the time t29 is selected as the time to be analyzed as indicated by a circle. The traffic volume of each IF1 to IF3 at the analysis target time t29 is a calculation target for topology estimation.

<< Procedure 4: Output processing of analysis target time >>
The analysis target times (for example, t1, t29) selected by the procedure 3 are described in the analysis target time list 35a (FIG. 10) in the order of selection. The analysis target time list 35a created by this description is output to the storage means.

<< Procedure 5: Principle 1a, 2a establishment determination process >>
For example, the analysis target time (for example, t1, t29) of the combination of IF1, IF2, and IF3 is acquired from the analysis target time list 35a created by the procedure 4. The transmission / reception traffic amounts of the IF1 to IF3 at the acquired analysis target times t1 and t29 are acquired from the IF data list 32b {FIG. 7B}. It is confirmed whether or not the acquired transmission / reception traffic amount satisfies the following judgment expressions 3 and 4 corresponding to the above-described principles 1 and 2.

  However, satisfying judgment formulas 3 and 4 is equivalent to satisfying principles 1 and 2 in principle. However, since it is taken into account that the tolerances σ and γ are accepted in the determination expressions 3 and 4 as described later, satisfying the determination expressions 3 and 4 is expressed as satisfying the principle 1a and 2a in principle. .

  The principle 1a is a first determination condition that accepts the allowable error σ as the first error described in the claims, and the principle 1 is a first determination condition that does not include the allowable error σ and accepts a predetermined value. . The principle 2a is a second determination condition that accepts the allowable error γ as the second error described in the claims, and the principle 2 is a second determination condition that does not include the allowable error γ.

  However, since the transmission / reception traffic volume of each IF1 to IF3 includes an error due to a shift in the data acquisition timing of the traffic volume, the determination formula 3 allows the allowable error σ and the determination formula 4 allows the allowable error γ. That is, the judgment formula 3 accepts the allowable error σ in the judgment formula 1 for judging that the principle 1 is satisfied. The judgment formula 4 accepts the allowable error γ in the judgment formula 2 for judging that the principle 2 is satisfied.

  In the judgment formula 3, the balance is obtained from the absolute value of the difference between the total value of the transmission traffic amount of each IF1 to IF3 and the total value of the reception traffic amount, and the condition that this balance degree is smaller than the allowable error σ. Is determined. Note that the total value of the transmission traffic volume of each IF1 to IF3 and the total value of the reception traffic volume are also expressed as the total value of the transmission and reception traffic volume of each IF1 to IF3.

Balance = (total transmission traffic amount of φ _{1 to} φ _S )
− (Total value of received traffic volume of φ _{1 to} φ _S ) <σ ... judgment formula 3
(Phi _i transmits the total amount of traffic) ≦ (excluding phi _i, the sum of the received traffic amount _{φ 1 ~φ S) + γ [} i = 1,2, ..., s] ... judgment formula 4

However, in the judgment formulas 3 and 4, φ _{1 to} φ _S are the values of the node N ₁ when each of the nodes N _{1 to} N _S has the same as described above with reference to FIG. a set of IF defined as "phi _1" Similarly, the node _N 2 to N _S, are as previously defined and "phi _2" - "phi _S".
<< Procedure 6: IF connection optimization process >>
Select all IF combinations that satisfy the judgment formulas 3 and 4 in step 5, and select the IF combination that has the smallest total value of the total number of balances of the selected IF combinations. Selected as a combination of IF. The selected combination of IFs is stored in the IF connection list 34a (FIG. 9).

An example of this connection relationship optimization process will be described. For example, as shown in FIG. 12, when there are seven IF1 to IF7, the connection relation of three IFs with k = 3 is estimated from these. At this time, the balance obtained by combining the three IFs is assumed to take the following values.
Balance of three IF1, IF2, and IF3 shown in the first line (1) = 0.03
Balance of three IF2, IF3, and IF4 shown in the second line (2) = 0.05
Balance of three IF3, IF4, and IF5 shown in the third line (3) = 0.04
Balance of three IF4, IF5, and IF6 shown in the fourth line (4) = 0.12
Balance degree of three IF5, IF6, and IF7 shown in the j-th line (j) = 0.05

  In this case, the balance when the three IFs are combined is further combined, and the total value of the two balances is obtained. For example, as shown in FIG. 12, when (1) + (4) is combined as the first combination and the total value of the balance is obtained, 0.03 + 0.12 = 0.15. The total value of the balance of (1) + (j) of the second combination is 0.03 + 0.05 = 0.08, and the total value of the balance of (2) + (j) of the third combination is 0.05 + 0.05 = 0.10.

  Next, a minimum value is selected from a plurality of (two in the above example) balance values, and a combination of the minimum values is selected as an optimal IF combination. This selection is made when the balance is completely equal to the transmission / reception traffic volume, and the closer the balance is to “0”, the higher the synchronization between the transmission traffic volume and the reception traffic volume. Become. This is because the higher the synchronism is, the more the IF connection relationship can be determined.

  That is, in the example of FIG. 12, the minimum value “0.08” is selected from the total values “0.15”, “0.08”, and “0.10”, and the second value of the minimum value “0.08” is selected. A combination is selected as an optimal IF combination (1) + (j). The connection determined flag {FIG. 7 (c)} of each of the selected IF1 to IF3 and IF5 to IF7 is updated to “1”. This “1” indicates that IF1 to IF3 and IF5 to IF7 are already connected. After the flag is updated to “1”, the selected connection relationships IF1 to IF3 and IF5 to IF7 are stored in the IF connection list 34a (FIG. 9).

  However, the total value of the two balances when the three IFs are combined is the smallest (1) + (3) = 0.03 + 0.04 = 0.07, but (1) and (3) IF3 is common. Since only one other IF (any one of IF1, IF2, IF4 to IF7) is connected to one IF3, a connection relationship is not established for combinations having the same IF in common. Therefore, if there is a common IF in a combination that totals a predetermined number of balances, the optimal combination is excluded from the selection targets.

<< Procedure 7: End determination process >>
When the value of k is larger than the number of IFs whose connection determination flag is “0” (also referred to as “0” IF numbers), the estimation target IF number k is the number of “0” IFs that remain unconnected. It is a state more than. In this state, since the number of remaining “0” IFs is smaller than the number of estimation target IFs k, the connection relationship based on the number of IFs to be estimated is not established. Therefore, all procedures 1 to 7 are completed. In other cases, the procedure returns to the procedure 1, the value of k is increased by "1", and the procedures 2 to 6 are repeated.

  For example, if the number of IFs of “0” = “3” and the value of k = “2” after completing step 6, it is determined in step 7 that the value of k is small. Value = 2 + 1 = “3”. Thereafter, the processing of the procedure 2 to the procedure 6 is performed, and it is determined in the procedure 7 whether or not the number of IFs of “0” <k. Such procedures 1 to 7 are repeated, and if the number of IFs of “0” = “3” and the value of k = “4” in step 6, it is determined in step 7 that the value “4” of k is large. Therefore, all procedures 1 to 7 are completed.

<Configuration of topology estimation device>
Next, the configuration of the topology estimation apparatus 1 according to this embodiment will be specifically described.
FIG. 13 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. At this time, even when there are three or more IFs of nodes connected to the subnet, topology estimation between the nodes is performed with high accuracy. The topology estimation apparatus 1 includes a processing unit 10, an input / output unit 20, and a storage unit 30.

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

  The node list storage unit 31 stores a node IF correspondence list 31a (FIG. 6). The IF data list storage unit 32 stores an IF list 32a {FIG. 7 (a)}, an IF data list 32b {FIG. 7 (b)}, and a connection determined flag list 32c {FIG. 7 (c)}. The connection determination candidate list storage unit 33 stores a connection determination candidate list 33a (FIG. 8). The connection list storage unit 34 stores an IF connection list 34a (FIG. 9). The analysis target time storage unit 35 stores an analysis target time list 35a (FIG. 10). The parameter storage unit 36 stores an allowable error list 36a and a threshold list 36b (FIG. 11).

The node IF correspondence list 31a illustrated in FIG. 6 is information indicating which IF each node (apparatus) includes, and is associated with the “node name” of each node, and is “IF information” that is IF identification information. "Name" is stored. For example, the node _{N 1} of the first row "IF1", "IF3", ... etc. are stored in association, the node _{N 2} of the second row "IF1", "IF2", ... etc., S the node N _S of row "IF3", "IF1", ... etc. are stored in association.

  The IF list 32a shown in FIG. 7A stores all IF1 to IFn provided for each node.

  The IF data list 32b shown in FIG. 7B is information provided for each IF, and stores “transmission traffic volume” and “reception traffic volume” in association with each other at time t. If the IF data list 32b is, for example, IF1, the transmission traffic volume “5”, “10”,..., “25” and the reception traffic volume “43” at each time t1, t2,. , “35”,..., “45” are stored in association with each other.

  The connection determination flag list 32c shown in FIG. 7C is information set in association with each IF of each node, that is, for each IF whose topology is to be estimated (for each IF1 to IFn of the IF list 32a). , “IF name” IF1, IF2,..., IFn, the connection determination completed flag “0” or “1” is stored in association with each other. The connection determination flag (also simply referred to as a flag) is assigned “0” when it is determined that there is no connection relationship with another IF, and “1” when it is determined that there is a connection relationship. Is attached. Note that all the initial values of the flags are set to “0”. In addition, for example, whenever a new IF IF data list 32b is stored in the IF data list storage unit 32, a flag is set in the connection determined flag list 32c in association with the IF in the list 32b. It has become.

  The connection determination candidate list 33a illustrated in FIG. 8 is information in which “balance” is set in association with each “IF combination”. For example, “0.03” of “balance” is stored in association with IF1, IF2, and IF3 in the first row, which is “IF combination”.

  The IF connection list 34a shown in FIG. 9 stores IFs having a connection relationship, that is, combinations of IFs determined to constitute a subnet for each row. For example, “IF1, IF2, IF3” is stored in the first row as information on a combination of IFs having a connection relationship.

  The analysis target time list 35a illustrated in FIG. 10 is information in which “analysis target time” selected using the threshold ε (k) is associated with “IF combinations” constituting the traffic ratio at this time. . For example, t1, t29 (see FIG. 5) of the analysis symmetry time are associated with IF1, IF2, IF3 of the IF combination, and t3, t8 are associated with IF4, IF5.

  The allowable error list 36a shown in FIG. 11A includes an allowable error σ = 0.1 used in the determination of the determination formula 3 based on the principle 1, and an allowable error γ = 0.1 used in the determination equation 4 based on the principle 2. It is information including.

  The threshold value list 36b shown in FIG. 11B stores the threshold value ε (k). For example, the threshold value ε (k) = 0.5 is stored.

  The input / output unit 20 illustrated in FIG. 13 performs input / output of information between devices with a network management device (not illustrated) and each node configuring 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 input / output unit 20 receives the node IF correspondence list 31a, the IF list 32a, the IF data list 32b for each IF, the allowable error list 36a including the allowable error σ and the allowable error γ, and the threshold list 36b from the network management device or the like. And stored in the storage unit 30. The node IF correspondence list 31a is stored in the node list storage unit 31, the IF list 32a and the IF data list 32b are stored in the IF data list storage unit 32, and the allowable error list 36a and the threshold list 36b are stored in the parameter storage unit 36.

  The input / output unit 20 outputs the IF connection list 34 a stored in the connection list storage unit 34 to a network management device, a monitor (not shown) provided in the topology estimation device 1, or the like.

  The processing unit 10 performs overall control of the topology estimation apparatus 1 and executes topology estimation processing between nodes. The processing unit 10 includes a determination candidate generation unit 11, an analysis target time selection unit 12, a traffic calculation unit 13, a determination calculation unit 14, and an estimation end determination unit 15. 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 determination candidate generation unit 11 is a generation unit described in claims, and the analysis target time selection unit 12 is a selection unit described in claims. Hereinafter, the determination candidate generation unit 11 is also simply referred to as a generation unit 11, and the analysis target time selection unit 12 is also simply referred to as a selection unit 12.

  The determination candidate generation unit 11 acquires the node IF correspondence list 31a, the IF list 32a, the IF data list 32b, and the connection determined flag list 32c stored in the storage unit 30, and generates a combination of IFs to be estimated. For this generation, the generation unit 11 sets the number of IFs (the number of “0” IFs) for which the connection determination flag in the connection determination flag list 32c is “0” {FIG. 7C) to n. The value of k received from the input / output unit 20 is set as the initial value described in the procedure 1 above. This set value of k is incremented by “1” and overwritten when the operations of the above steps 1 to 7 are repeated.

Next, as described in the procedure 2, the generation unit 11 generates a combination “ _n C _k pattern” of _k IFs from the n IF data lists 32b {FIG. 7B}. At this time, the generation unit 11 refers to the node IF correspondence list 31a and does not generate a pattern in which all k IFs belong to the same node. The generation unit 11 stores the generated combination of k IFs in the connection determination candidate list 33 a of the connection determination candidate list storage unit 33. The generation unit 11 also receives the k value from the input / output unit 20 when the estimation end determination unit 15 does not end the determination in step 7 and a new k value is input in step 1. The same operation as in the case is performed.

  The analysis target time selection unit (also simply referred to as a selection unit) 12 selects the analysis target time as described below in steps 2 and 3. First, the selection unit 12 acquires the IF data list 32b {FIG. 7 (b)} for each IF and the threshold list 36b {FIG. 11 (b)} from the storage unit 30. The acquired IF data list 32b stores the amount of transmission traffic and the amount of reception traffic measured at times t1 to tx. Further, for example, threshold value ε (k) = 0.5 is stored in the threshold value list 36b.

  For example, when k = 3 is set in the generation unit 11, the selection unit 12 acquires the transmission / reception traffic amount from the IF data list 32b of the three IF1 to IF3, and as illustrated by the bar graph in FIG. The traffic ratios r1 (t) to r3 (t) of the IF1 to IF3 at each time t are calculated.

  Next, the selection unit 12 calculates the determination value R (t) of the traffic ratios r1 (t) to r3 (t) of each IF1 to IF3 for each time t from the above (Equation 2). For example, as described in step 2, the determination value R (t) at time t4 in the frame W1 in FIG. 5 is 0.24, R (t) at time t9 in the frame W2 is 0.12, and within the frame W3. R (t) at time t29 is calculated as 0.63.

Next, the selection unit 12 sets the threshold value ε (k) = “0.5” and the above-described determination values R (t) = “0.24”, “0.12”, “t2, t9, t29”. Each of “0.63” is compared. As a result of this comparison, the time t at which the determination value R (t) is equal to or greater than the threshold value ε (k) is selected as the analysis target time, as in (Expression 3) above.
In the above example, since R (t) = 0.24 at time t4 and R (t) = 0.12 at time t9 are both less than the threshold ε (k) = 0.5, they are excluded from the analysis target time.
On the other hand, since R (t) = 0.63 at time t29 is greater than or equal to the threshold ε (k) = 0.5, the time t29 is selected as the analysis target time. The traffic amount of each IF1 to IF3 at the analysis target time t29 is a calculation target for topology estimation.

  Next, as described in step 4, the selection unit 12 describes the analysis target time t29 selected above in the analysis target time list 35a (FIG. 10) in association with the corresponding IF combinations IF1 to IF3. . This description is done in the order of selection. Further, the selection unit 12 outputs the analysis target time list 35 a created by describing the analysis target times for a predetermined time to the analysis target time storage unit 35 of the storage unit 30 and stores it.

  The traffic calculation unit 13 calculates the balance described in the procedure 5. The traffic calculation unit 13 acquires the analysis target time list 35a from the storage unit 30, and the analysis target times (for example, t1, t29) described in the list 35a and the IF combinations “IF1 to IF3” associated therewith. To get. Further, the traffic calculation unit 13 acquires the transmission traffic amount and the reception traffic amount for each of the analysis target times t1 and t29 in the IF data list 32b corresponding to the IF combination “IF1 to IF3”.

  Next, the traffic calculation unit 13 calculates the balance by fitting the total values of the transmission / reception traffic amounts of the IF1 to IF3 at the times t1 and t29 to the above-described (Equation 1), and determines this balance as a connection determination. In the balance column of the candidate list 33a (FIG. 8), it is described in association with the combination of IFs consisting of the corresponding IF1 to IF3. The list 33a after the description is overwritten on the list 33a of the connection determination candidate list storage unit 33.

  The determination calculation unit 14 determines whether the principles 1a and 2a described in the procedure 5 are satisfied. The determination calculation unit 14 acquires the connection determination candidate list 33a, the IF data list 32b corresponding to each IF1 to IF3 of the IF combinations described in the list 33a, and the allowable error list 36a from the storage unit 30. After this acquisition, the determination calculation unit 14 uses the degree of balance described in the connection determination candidate list 33a and the allowable error σ described in the allowable error list 36a to determine the above-described determination formula at the corresponding analysis target time t. 3 is determined. In this determination, it is determined whether or not the principle 1a is satisfied. For example, since the balance 0.03 of IF1 to IF3 described in the connection determination candidate list 33a is smaller than the allowable error σ = 0.1, it is determined that the principle 1a is satisfied.

Further, the determination calculation unit 14 satisfies the above-described determination formula 4 at the corresponding analysis target time t by using the total value obtained by totaling the transmission / reception traffic amounts described in the IF data list 32b of each IF1 to IF3. Determine whether or not. In this determination, it is determined whether or not the principle 2a is satisfied.
For example, if the total value of the IF1 transmission traffic amount at time t1 is “15” and the total value of the IF2 and IF3 reception traffic amounts excluding IF1 is “35”, the determination formula 4 is satisfied. It is determined to satisfy.

  Thereafter, the determination calculation unit 14 performs the connection relationship specifying process described in the procedure 6. First, the determination calculation unit 14 selects, from the connection determination candidate list 33a, the balance of all IF combinations that satisfy the principles 1a and 2a. Next, the determination calculation unit 14 selects the IF combination having the smallest total value obtained by summing the degree of balance of the selected IF combination by a predetermined number as the optimum IF combination. Then, the determination calculation unit 14 stores the selected IF combination in the IF connection list 34a (FIG. 9).

For example, in the seven IF1 to IF7 shown in FIG. 12, it is assumed that there are three IF combinations satisfying the principles 1a and 2a as shown in the first to jth rows.
In this case, the determination calculation unit 14 selects, from the connection determination candidate list 33a (FIG. 8), the balance of all IF combinations that satisfy the principles 1a and 2a, and sets the balance of the selected IF combination to 2 The total value is obtained by combining them one by one (in this case, the predetermined number is “2”). For example, (1) + (4) is combined as the first combination, and the balance is summed to obtain 0.15. Similarly, (1) + (j) is combined as the second combination, and the balance is summed to obtain 0.08. (2) + (j) is combined as the third combination, and the balance is summed to obtain 0.10.

  Next, the determination calculation unit 14 selects the minimum value “0.08” from the total values “0.15”, “0.08”, and “0.10”, and determines the minimum value “0.08”. Two combinations are selected as the optimum IF combinations IF1 to IF3 and IF5 to IF7. The determination calculation unit 14 updates the connection determined flag {FIG. 7 (c)} of each of the selected IF1 to IF3 and IF5 to IF7 to “1”, and then updates the IF connection list 34a (FIG. 9). The selected connection relationships IF1 to IF3 and IF5 to IF7 are stored.

  The estimated end determination unit 15 performs an end determination process according to the procedure 7. That is, the estimation end determination unit 15 refers to the flag of the connection determination completed flag list 32c corresponding to each IF stored in the IF data list storage unit 32, the number of IFs whose flag is “0”, and the current k Compare the value of. When the “0” IF number is larger than the value of k, the estimation end determination unit 15 increments the value of k by “1”, outputs it to the generation unit 11, and continues the topology estimation process. On the other hand, if the number of “0” IFs is less than or equal to the value of k, the topology estimation process ends.

<Process flow>
Next, the flow of the topology estimation process of the topology estimation apparatus 1 according to this embodiment will be described. FIG. 14 is a flowchart 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. 14, the input / output unit 20 of the topology estimation apparatus 1 receives a node IF correspondence list 31a, an IF data list 32b for each IF, an allowable error σ, an allowable error γ, a threshold value from a network management apparatus or the like. ε (k) is acquired and stored in the storage unit 30. Here, it is assumed that the allowable error σ = 0.1, the allowable error γ = 0.1, and the threshold ε (k) = 0.5.
At this time, when the IF data list 32b is stored in the storage unit 30, the determination candidate generation unit 11 sets the flag of the connection determined flag list 32c corresponding to the IF of the IF data list 32b to an initial value “0”. .

  Next, in step S2, the generation unit 11 sets a value of k. At this time, the input / output unit 20 outputs the value of k (initial value k = 2) to the generation unit 11, and the generation unit 11 sets the value “2” of k as the initial value. Here, the value of k is k = 2 at the initial stage, but k = 3 in step S11 described later, and k = 3 when returning to step S2 again.

Next, in step S3, the generation unit 11 generates a combination “ _n C _k pattern” of _k IFs from the n IF data lists 32b. Since k = 3 at this point, the combination of IFs is due to three IFs. However, it is assumed that the number of IFs of the flag “0” in the connection determined flag list 32c is n. The generation unit 11 does not generate a pattern in which all three IFs belong to the same node. Further, the generation unit 11 stores the combination of the three IFs generated above in the connection determination candidate list 33 a of the connection determination candidate list storage unit 33.

  Next, in step S4, the analysis target time selection unit 12 selects the analysis target time. First, since k = 3, the selection unit 12 acquires transmission / reception traffic amounts from the IF data lists 32b of the three IF1 to IF3, and, as shown by the bar graph in FIG. 5, each IF1 to each time t1 to t38. The traffic ratios r1 (t) to r3 (t) of IF3 are calculated.

  Next, the selection unit 12 calculates the determination value R (t) of the traffic ratios r1 (t) to r3 (t) of each IF1 to IF3 for each time t1 to t38 from the above (Equation 2). For example, the determination value R (t) = 0.24 at time t4 in FIG. 5, R (t) = 0.12 at time t9, and R (t) = 0.63 at time t29 are calculated.

  Next, the selection unit 12 sets the threshold value ε (k) = “0.5” in the threshold value list 36b and the determination values R (t) = “0.24”, “0.12” at the times t4, t9, and t29. ”And“ 0.63 ”, and the times t1 and t29 at which the determination value R (t) is equal to or greater than the threshold value ε (k) are selected as the analysis target times as in the above (Equation 3). . The selection unit 12 stores the selected analysis target times t1 and t29 in the analysis symmetry time column of the analysis target time list 35a in association with the corresponding IF combinations IF1 to IF3.

  Next, in step S5, the traffic calculation unit 13 calculates balance. First, the traffic calculation unit 13 detects the analysis target times t1 and t29 described in the analysis target time list 35a and the IF combinations “IF1 to IF3” associated therewith. Further, the traffic calculation unit 13 acquires the transmission traffic amount and the reception traffic amount for each of the analysis target times t1 and t29 in each IF data list 32b corresponding to the IF combination “IF1 to IF3”.

  Next, the traffic calculation unit 13 calculates the balance by fitting the total values of the transmission / reception traffic amounts of the IF1 to IF3 at the times t1 and t29 to the above-described (Equation 1), and determines this balance as a connection determination. In the balance column of the candidate list 33a, the corresponding IF1 to IF3 are stored in association with each other.

  Next, in step S6, the determination calculation unit 14 performs a determination determination process for the principles 1a and 2a. First, the determination calculation unit 14 uses the balance degree 0.03 described in IF1 to IF3 of the connection determination candidate list 33a and the allowable error σ = 0.1 described in the allowable error list 36a, as described above. It is determined whether or not the determination formula 3 is satisfied. In this case, since the balance degree 0.03 of IF1 to IF3 is smaller than the allowable error σ = 0.1, it is determined that the principle 1a is satisfied.

  Further, the determination calculation unit 14 determines whether or not the above-described determination formula 4 is satisfied by using the total value obtained by summing each of the transmission / reception traffic amounts for each of the analysis target times t1 and t29 in the IF data list 32b of each IF1 to IF3. Determine. For example, if the total value of the IF1 transmission traffic amount at time t1 is “15” and the total value of the IF2 and IF3 reception traffic amounts excluding IF1 is “35”, the determination formula 4 is satisfied. It is determined to satisfy. This determination is performed in the same manner at time t29, and is also performed in the same manner in IF2 and IF3.

Next, in step S <b> 7 shown in FIG. 15, the determination calculation unit 14 determines whether or not the processing in steps S <b> 4 to S <b> 6 has been performed for all IF combinations of “ _n C _k pattern”. If the determination result is not all, the process returns to step S4 to perform the process. On the other hand, if all the steps have been performed, the process proceeds to step S8.

  Next, in step S8, the determination calculation unit 14 determines whether or not both the principles 1a and 2a are satisfied. If satisfied, the process proceeds to step S9, and if not satisfied, the process proceeds to step S10.

  In step S <b> 9 when the above is satisfied, the determination calculation unit 14 performs an IF connection relationship optimization process. First, the determination calculation unit 14 selects, from the connection determination candidate list 33a, the degree of balance of all IF combinations that satisfy the principles 1a and 2a in step S8. Next, the determination calculation unit 14 selects the IF combination having the smallest total value obtained by summing the degree of balance of the selected IF combination by a predetermined number as the optimum IF combination. Then, the determination calculation unit 14 updates the connection determination completed flag corresponding to each IF of the selected combination to “1”, and then stores the selected IF combination in the IF connection list 34a.

After this storage or when the above step S8 is not satisfied, in step S10, the estimation end determination unit 15 determines the end of topology estimation. That is, the estimation end determination unit 15 determines that the number of IFs “n” with the flag “0” in the connection determination flag list 32c at the current time is less than or equal to the value of k (eg, k = 3) set in step S3. It is determined whether or not there is. As a result, when it is not less than or equal to k, that is, when it is larger than the value of k (No), the process proceeds to step S11, the value of k is set to a value obtained by adding “1” to the current k, and then the process proceeds to step S3. Return and continue processing.
On the other hand, when it is k or less (Yes), the estimation end determination unit 15 ends the topology estimation process.

  After the completion, in step S12, the input / output unit 20 outputs the IF connection list 34a stored in the connection list storage unit 34 to a network management device, a monitor (not shown) provided in the topology estimation device 1 or the like.

<Effect of embodiment>
As described above, the topology estimation device 1 that estimates the connection relationship between devices (nodes) constituting the network according to the present embodiment includes a determination candidate generation unit (generation unit) 11 and an analysis target time selection unit (selection). Unit) 12, a traffic calculation unit 13, and a determination calculation unit 14.

  The generation unit 11 has a combination of k IFs (Interface) included in a node, except that all IFs (k ≧ 2) that are the number of IFs constituting a subnet are provided in the same node. Are generated as connection relationship determination candidates (topology estimation candidates).

  The selection unit 12 acquires the generated transmission / reception traffic volume for each k IFs at predetermined time intervals, and the ratio of the transmission / reception traffic volume for each IF to the total value of the transmission / reception traffic volumes for the k IFs ( (Traffic ratio) is calculated for each time, a determination value based on the minimum ratio among the ratios is generated for each time, and a time at which the determination value is equal to or greater than a predetermined threshold is selected as an analysis target time.

  The traffic calculation unit 13 obtains a degree of balance that is an absolute value of a difference between the total value of the transmission traffic amount of each IF and the total value of the reception traffic amount at each analysis target time.

  The determination calculation unit 14 includes a first determination condition as a principle 1 for determining that the degree of equilibrium of the analysis target time is less than a predetermined first error σ, and an IF that is the determination candidate of the analysis target time. The second principle 2 as a principle 2 in which one IF is extracted from the combination of and the transmission traffic amount of the extracted IF is less than or equal to the reception traffic amount of all IFs except the extracted IF. When both of the determination conditions are satisfied, the IF combination having the smallest total value obtained by summing the degree of balance of all IF combinations that satisfy both the conditions is selected as the optimum IF combination.

  According to this configuration, the following effects can be obtained. When k = 3, the traffic ratio of each IF in the combination of three IFs to be subjected to topology estimation is calculated at a predetermined interval time, and the ratio of each IF is not extremely different from each time. A time t having a traffic ratio is selected. It is assumed that the balance of the transmission / reception traffic amount of each IF is obtained for each selected analysis target time. In this case, except for the traffic ratio in which the ratio of the three IFs is extremely separated as in the conventional case, the balance can be obtained only by the IF group having the traffic ratio in which the ratio of the three IFs is not extremely separated. For this reason, the value of the degree of balance is less likely to be extremely different between analysis target times.

  Furthermore, when the balance satisfies both of the principles 1 and 2, the combination of all three IFs that satisfy both is optimal for the combination of IFs that has the smallest total value of the total number of balances. Selected as a combination of IFs. For this reason, since a balance with a smaller value is selected from the balances whose values are not extremely different between the analysis target times, a balance with a value closer to “0” or “0” is selected. Can do.

  The closer the balance degree is to “0”, the higher the synchronization between the transmission traffic amount and the reception traffic amount. Therefore, the combination of IFs whose balance degree is “0” or closer to “0” has a high probability of connection. I know that it can be said. From this, it can be said that the IF combination having a smaller value of balance selected as described above, that is, the optimal IF combination, has a high probability of connection. Thus, even when there are three or more IFs of nodes connected to the subnet, topology estimation between the nodes can be performed with high accuracy.

  In addition, the second determination condition described above is that one IF is extracted from the combination of IFs that are the determination candidates at the same analysis target time, and the transmission traffic amount of the extracted IF is the extracted IF. The condition is such that it is determined to be equal to or less than a value obtained by adding a predetermined second error γ to the total received traffic amount of all IFs except for.

  According to this configuration, the second determination condition is a condition for determining that the second error γ is equal to or less than the value obtained by adding the second error γ, and the first and second errors are set to the data acquisition timing of the transmission / reception traffic amount of each IF. If a value corresponding to an error due to a deviation or the like is set, an error in data of the transmitted / received traffic amount acquired at the time of acquisition can be accepted.

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 Judgment candidate production | generation part 12 Analysis object time selection part 13 Traffic calculation part 14 Judgment calculation part 15 Estimation completion | finish judgment part 20 Input / output part 30 Storage part 31a Node IF corresponding list 32a IF list 32b IF data list 32c Connection determination completed flag list 33a Connection determination candidate list 34a IF connection list 35a Analysis target time list 36a Allowable error list 36b Threshold list

Claims (3)

A topology estimation device for estimating a connection relationship between nodes constituting a network,
The IF (Interface) that said node comprises, k pieces (k ≧ 2) all IF is the number of IF constituting the subnet except that provided in the same node, the connection relationship combinations of k combined IF A generation unit that generates a determination candidate;
The generated transmission / reception traffic volume for each of k IFs is acquired at predetermined time intervals, and the ratio of the transmission / reception traffic volume for each IF to the total value of the transmission / reception traffic volumes of the k IFs is calculated for each time. A selection unit that generates a determination value based on a minimum ratio among the ratios for each time, and selects a time at which the determination value is equal to or greater than a predetermined threshold as an analysis target time;
In the analysis target time, and traffic calculation unit for obtaining the absolute value is balance of the difference between the total value of the total value and the received traffic amount of the transmission traffic amount of each IF,
One IF is extracted from a combination of a first determination condition for determining that the balance of the analysis target time is less than a predetermined first error and an IF that is the determination candidate for the analysis target time. If both the second determination condition for determining that the transmission traffic amount of the extracted IF is equal to or less than the sum of the reception traffic amounts of all IFs except the extracted IF is satisfied. Calculation that selects all IF combinations satisfying the above-mentioned criteria, and selects the IF combination that has the smallest total value of the total number of balances of the selected IF combinations as the optimum IF combination. And a topology estimation apparatus. The second determination condition is that one IF is extracted from the combination of IFs that are the determination candidates at the same analysis target time, and the transmission traffic amount of the extracted IF is all the exceptions of the extracted IF. The topology estimation device according to claim 1, wherein the topology estimation device is a condition for determining that the sum is equal to or less than a value obtained by adding a predetermined second error to the sum of the received traffic amounts of the IF.   The program for making a computer implement | achieve each function of the topology estimation apparatus of Claim 1 or 2.

Images