JP7701700B2 - NETWORK FAILURE LOCALIZATION DEVICE, NETWORK FAILURE LOCALIZATION METHOD, AND PROGRAM - Google Patents

Description

The present invention relates to technology for identifying fault locations in a network.

In recent years, networks have become more complex, resulting in the occurrence of failures that cannot be detected using traditional methods that rely solely on data such as logs and metrics output by network devices.

As a means of detecting such failures, a method called "network tomography" has attracted attention. Network tomography measures the end-to-end communication status between multiple distant nodes (this is called path measurement) and integrates records of this connectivity to pinpoint the location of the failure (failed node or failed link).

In particular, methods that estimate the binary state (fault/no fault) of each network component (node, link) are also called binary network tomography and are being actively researched [Non-Patent Document 1].

Most existing techniques for binary network tomography assume that routing is deterministic. However, in reality, there are load balancing mechanisms and protocols such as ECMP that distribute traffic among paths with equal weights, which can lead to situations in which routing behaves probabilistically. There are also a small number of existing methods for network tomography under probabilistic routing [Non-Patent Documents 2, 3].

N. Duffield, "Simple network performance tomography," in Proceedings of the 3rd ACM SIGCOMM conference on Internet measurement. ACM, 2003, pp. 210-215. H. Herodotou, B. Ding, S. Balakrishnan, G. Outhred, and P. Fitter, "Scalable near real-time failure localization of data center networks," in Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2014, pp. 1689-1698. R. Tagyo, D. Ikegami, and R. Kawahara, "Network tomography using routing probability for undeterministic routing," IEICE Transactions on Communications, vol. E104.B, no. 7, pp. 837-848, 2021. T. Soma and Y. Yoshida, "Maximizing monotone submodular functions over the integer lattice," Mathematical Programming, vol. 172, no. 1, pp. 539-563, 2018. T. Soma, N. Kakimura, K. Inaba, and K.-i. Kawarabayashi, "Optimal budget allocation: Theoretical guarantee and efficient algorithm," in Proceedings of International Conference on Machine Learning (ICML). PMLR, 2014, pp. 351-359. S. Knight, H.

In probabilistic routing, even if node pairs are determined, the path connecting them is not uniquely determined, so a large number of path measurements are required to correctly identify the location of a fault. In general, large-scale path measurements should be avoided as much as possible, as they can take a long time to identify the location of a fault and place a heavy load on the network.

However, existing network tomography methods under probabilistic routing [Non-Patent Documents 2, 3] assume that a large amount of path measurement data has already been obtained, and there is a possibility that an unnecessarily large number of path measurements will be performed.

The present invention has been made in consideration of the above points, and aims to provide a fault location identification technology that identifies the fault location as accurately as possible with a limited number of path measurements under probabilistic routing.

According to the disclosed technology, there is provided a network fault location identification device for identifying a fault location in a target network, comprising:
a test optimization unit for calculating path measurement tests to be performed on the target network;
a test execution unit that executes the test calculated by the test optimization unit on the target network;
a test result analysis unit that narrows down the state of the target network according to the result of the test by the test execution unit,
a network fault location identification device, the network fault location identification device repeating, one or more times, a process in which the test optimization unit calculates a further test using an analysis result obtained by the test result analysis unit, the test execution unit executes the further calculated test, and the test result analysis unit narrows down the state of the target network according to the result of the further calculated test;
A network fault location identification device is provided, in which the test optimization unit calculates a further test which is an optimal or near-optimal solution to a problem of maximizing mutual information between a random variable representing the result of executing the test and a random variable representing the state of the target network.

The disclosed technology makes it possible to pinpoint the location of a fault as accurately as possible using a limited number of path measurements under probabilistic routing.

1 is a system configuration diagram according to an embodiment of the present invention. FIG. 1 is a diagram showing Algorithm 1. FIG. 2 is a diagram showing Procedure 2. FIG. 3 is a diagram showing Procedure 3. FIG. 1 illustrates an example of the configuration of a network failure point identification device 100. 4 is a flowchart showing a processing procedure of the network failure point locating device 100. FIG. 1 is a diagram showing the topology used in the evaluation. FIG. 1 is a diagram showing evaluation results of Missouri. FIG. 1 shows the evaluation results of ION. FIG. 13 is a diagram showing the evaluation results of Ntelos. FIG. 2 illustrates an example of a hardware configuration of the apparatus.

The following describes an embodiment of the present invention (the present embodiment) with reference to the drawings. The embodiment described below is merely an example, and the embodiment to which the present invention is applicable is not limited to the following embodiment.

(Overall system configuration and operation overview)
An example of the overall configuration of a system according to this embodiment is shown in Fig. 1. As shown in Fig. 1, this system has a configuration in which a network fault location identification device 100 is connected to a target network 200, which is a network for which a network fault location is to be identified. The network fault location identification device 100 identifies the fault location by repeating one or more times a process in which the path measurement device performs a test related to path measurement and obtains the results, based on routing topology information of the target network 200, routing information that may change dynamically, and constraint information of the path measurement device.

The target network 200 has multiple nodes and multiple links, and data is sent and received using probabilistic routing. The links may also be called branches or edges.

In this embodiment, the network fault location identification device 100 identifies the fault location as accurately as possible with a limited number of path measurements under probabilistic routing. The outline of the operation of the network fault location identification device 100 for this purpose is as follows.

In this embodiment, the network fault location identification device 100 expresses the effectiveness of path measurements in narrowing down the fault location using "mutual information." Mutual information can be naturally defined even in probabilistic routing. Path measurements with large mutual information, i.e., path measurements that are expected to most effectively narrow down the fault location, are performed preferentially to obtain measurement data.

The network fault location identification device 100 updates the probability distribution representing the possible fault locations in the Bayesian estimation framework according to this measurement data. By repeating these steps, the fault locations are gradually narrowed down.

In this embodiment, the network fault location identification device 100 uses highly effective path measurements and sequentially determines the measurements to be performed according to Bayesian estimation, thereby efficiently narrowing down the fault location with a small number of measurements and resolving the above-mentioned problem.

The processing performed by the network fault location identification device 100 is explained in detail below.

(Problem setting)
First, the formulation of the problem in this embodiment will be described. However, the technology according to this embodiment can be applied even in situations that do not strictly follow the following definition. For example, although the following formulation is performed regarding the identification of a link failure, the technology according to this embodiment can be similarly applied to the identification of a node failure.

The target network is an undirected graph G(V,E). V={v _i } where _i is a set of vertices, and E={e _j } where _j is a set of edges. A "network state" or simply a "state" is represented by a binary vector s=(s ₁ ,...,s _|E| )∈S⊂{0,1} ^|E| , where s _j =1 (s _j =0) indicates that edge e _j is abnormal (normal), and S represents the set of all possible states.

The monitoring path set A = {a1, ..., a|A|} is a set of "monitoring paths" represented by a binary vector _aj = ( _aj1 , ..., _aj|E| ) ∈ {0, 1} ^|E| . If _ajl = 1, it means that the monitoring path _aj includes an edge _e1 . Since the monitoring path can be regarded as simply a set of edges, paths with loops are also allowed.

When a test of a monitoring path _aj is executed, if even one edge in _aj is abnormal, a result of 1 is obtained, and if all edges are normal, a result of 0 is obtained. In other words, a result of 1 indicates that the monitoring path is not connected, and a result of 0 indicates that the monitoring path is connected. In this embodiment, since probabilistic routing is assumed, _aj cannot be specified directly, and only a "group" of multiple monitoring paths that have the same source vertex (S node) and destination vertex (D node) can be specified.

For a group c _i ∈ C, it is assumed that the tests of the monitoring path a _j are independently executed with probability p _ij (i=1, ..., |C|, j=1, ..., |A|).

が成り立つ。事前にルーティングの統計を解析しておくことにより、（ｐ_ｉｊ）_ｉ，ｊは既知と見なせる。状態ｓの下でｃ_ｉが実行されると、確率

holds. By analyzing the routing statistics in advance, (p _ij ) _i,j can be considered as known. When c _i is executed under state s, the probability

で結果１を得る。ここで

to get result 1. Here,

は引数が真であれば１を、偽であれば０を返す指示関数である。ｕ_ｉ（ｓ）を行列表示したものをＵ＝（ｕ_ｉ（ｓ））_ｉ，ｓと表す。実際のネットワーク運用では、パス測定装置が同時に複数の方向にプローブパケットを送信したり、統計値を得るために同じ方向に対して複数パケットを一度に送ったりできるように、監視システムが設計されていることもある。

is an indicator function that returns 1 if the argument is true and 0 if it is false. The matrix representation of _{u i} (s) is expressed as U = (u _i (s)) _i,s . In actual network operation, a monitoring system may be designed so that a path measurement device can simultaneously send probe packets in multiple directions, or send multiple packets in the same direction at once to obtain statistics.

Taking such a situation into consideration, a "probe test" or simply a "test" ξ _i ∈X={ξ ₁ , ..., ξ _|X| } is defined.

を実行すると、ｃ_ｊがξ_ｉｊ回実行される（ｊ＝１，・・・，｜Ｃ｜）。ここでＺ_＋は非負整数全体の集合を表す。すなわち、ξ_ｉは異なるノードペア間の同時測定や、複数回測定を一つのテストとしてパッケージ化したものである。一度のテストに同数の測定が含まれるように、｜ξ_ｉ｜＝Σ_ｊξ_ｉｊをｉによらない定数とするのが自然である。

When C is executed, c _j is executed ξ _ij times (j = 1, ..., |C|). Here, Z ₊ represents the set of all non-negative integers. That is, ξ _i is a package of simultaneous measurements between different node pairs or multiple measurements as one test. It is natural to set |ξ _i | = Σ _j ξ _ij as a constant independent of i so that one test contains the same number of measurements.

The problems with this embodiment are as follows:

Now, assume that the state s∈S is unknown. Also assume that the prior distribution of s and the number N of tests ξ that can be performed are given. In this case, what is the most efficient strategy for performing the tests (when and how many times each test should be performed) in order to identify the true state as accurately as possible by performing N tests? Also, how should the true state be estimated based on the results of the tests? Note that in the following explanation, it is assumed that the state s does not change dynamically, but the technology related to this embodiment can be applied even if it changes during the process.

(Details of Processing by Network Fault Location Identification Device 100)
In this embodiment, an "adaptive measurement" approach is adopted. In this approach, the network fault location identification device 100 sequentially determines the next test to be performed depending on the currently obtained test results. Adaptive measurement is more complicated to implement than a non-adaptive approach in which all N tests are determined at once, but since the information available for determining the optimal test increases step by step, it is expected that a small number of tests will result in highly accurate state identification.

Specifically, this is formulated as a batch process as follows:

Divide the N tests into B batches of size N _B , i.e., N _B ×B=N. In the bth batch ((b∈[1,B]∩Z ₊ )), the test design

を決定する。これはテストξ_ｉ（ｉ＝１，・・・，｜Ｘ｜）を実施する回数を表したものであり、｜Ｍ_ｂ｜＝Ｎ_Ｂである。Ｍ_ｂを決定した後、それを実行して、結果

This represents the number of times to execute the test ξ _i (i=1, . . . , |X|), where |M _b |=N _B. After determining M _b , execute it and obtain the result

を得る。ここで

where

は、グループｃ_ｉの

is the number of groups c _i

回の実行の中で、結果１を得た回数を表している。ｂ＜Ｂ（つまり最終バッチ以外）のときは、ｙ^Ｍ＿ｂとそれ以前のバッチの結果に基づき、次のテスト設計Ｍ_ｂ＋１を決定していくこととなる。以上より、考えるべき問題は、各バッチにおいて状態を効率的に絞り込む上で、どのようにＭ_ｂを設計するかである。なおバッチサイズとバッチ回数（Ｎ，Ｂ_Ｎ）に関しては、運用の実態（一回のテスト実行に要する時間や許容されるネットワーク負荷など）に応じて決定されるハイパーパラメータである。

It represents the number of times that a result 1 was obtained in the number of executions. When b<B (i.e., other than the final batch), the next test design M _b+1 is determined based on y ^M_b and the results of the previous batch. From the above, the problem to be considered is how to design M _b in order to efficiently narrow down the states in each batch. Note that the batch size and the number of batches (N, B _N ) are hyperparameters that are determined according to the actual operation (the time required to execute one test, the allowable network load, etc.).

When designing M (the subscript b in _Mb will be omitted as appropriate), it is necessary to quantitatively express the "goodness" of M. Since the purpose is to identify the true state, a natural strategy is to sharpen the probability distribution of the state as much as possible, i.e., to reduce the entropy.

Therefore, in this embodiment, the mutual information I(S; ^YM ) between ^YM and S is used as an index of the effectiveness of yM obtained by executing ^M (when ^yM or s is regarded as a random variable, capital letters are used, such as ^YM and ^S ). I(S; YM) represents the average reduction in the entropy of the state distribution by observing ^YM . This allows the problem considered in this embodiment to be written as follows:

[Problem]: Prior distribution Pr(s) and measurement results obtained up to the (b-1)th batch

が与えられたとき、

Given

を求めよ。

Seek.

Here, I(S; Y ^M |D _b-1 ) is the mutual information between Y ^M and S when D _b-1 is given, and is given by the following Equation 1.

また数式１右辺の各量は、下記の数式２、３で与えられる。

The quantities on the right side of Equation 1 are given by Equations 2 and 3 below.

上記の問題は、組合せ最適化問題であり、ＮＰ困難であることが示せる。従って、ネットワーク障害箇所特定装置１００は、一例として以下に示す貪欲法に基づくアルゴリズムによって近似解を求める。

The above problem is a combinatorial optimization problem, and can be shown to be NP-hard. Therefore, the network fault location identification device 100 obtains an approximate solution by, for example, an algorithm based on the greedy method shown below.

However, the technology according to this embodiment is not limited to the greedy method, and other approximate optimization methods or optimization methods can also be used. Also, although the case where the routing probability does not change dynamically is described here, the technology according to this embodiment can be applied even if it changes, as long as the information can be obtained.

The procedure (algorithm) of the process executed by the network fault location identification device 100 is shown in Algorithm 1 in Figure 2. First, in the second line, there is a StateSpaceReduction process that reduces the number of possible states, which will be described later.

In the batch processing starting from line 5, M is created based on the greedy algorithm in lines 6 to 10. In the while loop, ξ _{i_max} that gives the largest increment in I(S; Y ^M |D _b-1 ) is selected sequentially, and the i _max component of M is incremented. After M is created, it is executed to obtain y ^M , and the posterior distribution Pr(s|D _b ) is updated in lines 11 to 13.

Next, the method of calculating the mutual information on line 8 will be described. The mutual information is based on Procedure 2 shown in Fig. 3. Basically, it is based on the formula I(S; Y ^M |D _b-1 ) in Equation 1, but since the sum related to y ^M in Equation 3 is the sum of an exponential number of terms, it is difficult to execute strictly. Therefore, Monte Carlo sampling is performed as follows.

First, N _y samples of y ^M are obtained according to the binomial distribution in line 4. For each sample, the posterior distribution is calculated using the method described below in lines 6 and 7, and its entropy is calculated. Then, the average is taken in line 8. In Procedure 2, it is assumed that all possible states s can be enumerated, but if |S| is large, the sum over s may also be replaced with the sample average.

Next, we will explain the calculation of the posterior distribution Pr(s|D _b ) (Pr(s|D _b-1 ) and so on) that appears on line 13 of Algorithm 1 and lines 2, 6, and 8 of Procedure 2. Pr(s|D _b ) is

と記述することができる。ここでベイズの定理と、ｓが与えられた下でｙ^Ｍ＿ｂとＤ_ｂ－１が条件付き独立であることを用いた。Ｐｒ（ｓ｜Ｄ_ｂ－１）は既知であり、Ｐｒ（ｙ^Ｍ＿ｂ）｜ｓ）は下記の数式４により計算することができる。

Here, we use Bayes' theorem and the fact that y ^M_b and D _b-1 are conditionally independent under the condition s. Pr(s|D _b-1 ) is known, and Pr(y ^M_b )|s) can be calculated by the following Equation 4.

実装する際は、ｌｏｇｕ_ｉ（ｓ）、ｌｏｇ（１－ｕ_ｉ（ｓ））やコンビネーションのｌｏｇの値をメモ化して、

When implementing, memoize the values of log _{u i} (s), log(1-u _i (s)), and the log of the combination,

の代わりに

instead of

を計算するとよい。

It is a good idea to calculate

Now, Algorithm 1 is an approximation algorithm based on the greedy method, but it can be shown that it has a constant approximation in the sense of maximizing mutual information as follows. In other words, even in the worst case, it is guaranteed that the mutual information will be equal to or greater than a certain value.

[Theorem]: When _Ny is sufficiently large, let _Mb obtained by Algorithm 1 ^{be 〜} _Mb , and let the optimal _Mb be

とする。このとき、

In this case,

が成り立つ。

holds true.

(abbreviated proof)
By using the fact that the routing probabilities are mutually independent, the mutual information I(S; Y ^M |D _b-1 ) is

の関数として単調ＤＲ劣モジュラ［非特許文献４］という性質を持つことが示せる。一般に単調ＤＲ劣モジュラ関数の最大化問題は貪欲法により（１－１／ｅ）－近似を達成できることが知られている［非特許文献５］。（証終）
最後に、Ａｌｇｏｒｉｔｈｍ１の２行目にあったＳｔａｔｅＳｐａｃｅＲｅｄｕｃｔｉｏｎの処理について説明を行う。この処理は、あらかじめあり得ない状態をＳから取り除いておくことで、Ａｌｇｏｒｉｔｈｍ１の実行時間を短縮するためのものである。一般に行列Ｕには０や１を値に持つ成分が多く含まれている。

It can be shown that it has the property of being monotone DR submodular as a function of [Non-Patent Document 4]. It is generally known that the maximization problem of a monotone DR submodular function can achieve (1-1/e)-approximation by a greedy method [Non-Patent Document 5]. (End of Proof)
Finally, we will explain the processing of StateSpaceReduction in the second line of Algorithm 1. This processing is intended to reduce the execution time of Algorithm 1 by removing impossible states from S in advance. In general, a matrix U contains many components with values of 0 and 1.

In fact, a group c usually contains only a small portion of the edges of the entire network, so there are many 0s, and monitoring paths within the same group often pass through some common edges, so there are many 1s. In addition, the following trivial proposition also holds: "Let u _i (s) = 1 (0). In this case, if group c _i is executed and the result is 1 (0), then the true state is not s." Based on the above, the following definition is introduced.

[Definition] (Removable state): When group c _i is executed and the result 1 (0) is obtained, state s that satisfies u _i (s)=0 (1) is removable.

A state that is clearly removable may be removed from the state space S. The following lemma also holds.

[Lemma]: The expected number of removable states when performing test ξ, R(U, ξ), is given by the following formula 5.

ここでδ_ｄ（ｘ）＝１（ｘ＝ｄ）、δ_ｄ（ｘ）＝０（その他）であり（ｄ＝０，１）、０^０＝１である。特にξ＝ｅ_ｌ（第ｌ成分のみが１であるような単位ベクトル）のときは下記の数式６となる。

Here, δ _d (x) = 1 (x = d), δ _d (x) = 0 (otherwise) (d = 0, 1), and 0 ⁰ = 1. In particular, when ξ = e _l (a unit vector in which only the l-th component is 1), the following Equation 6 is obtained.

ここで、

Where:

である。

It is.

(abbreviated proof)
From the linearity of expectation

となる。各グループの実行がベルヌーイ試行であることを踏まえると、

Considering that each group's execution is a Bernoulli trial,

と記述できるので、これの余事象をとってｉについて和を取ればよい。数式６はξ＝ｅ_ｌを代入して計算し、不等式は

Since we can write it as follows, we can take the complementary event of this and sum it with respect to i. Equation 6 is calculated by substituting ξ＝e _l , and the inequality becomes

から得られる。（証終）
上の補題を基に、ＳｔａｔｅＳｐａｃｅＲｅｄｕｃｔｉｏｎの処理をまとめたものが、図４のＰｒｏｃｅｄｕｒｅ３である。各グループｃ_ｌに対して数式６を計算し、それを最大化するｃ_{ｌ＿ｍａｘ}を得る。次にｃ_{ｌ＿ｍａｘ}を含むようなテストξを任意に選んで実行する。実行結果に応じて除去可能な状態をＳから除外し、行列Ｕも小さくする。以上の工程をＮ_ｉｔｅｒ回繰り返す。

It is obtained from (end of proof).
Based on the above lemma, the processing of StateSpaceReduction is summarized in Procedure 3 in Figure 4. Calculate Equation 6 for each group c _l , and obtain c _{l _max} that maximizes it. Next, arbitrarily select and execute a test ξ that includes c _{l _max} . Depending on the execution result, remove removable states from S, and also reduce the matrix U. The above process is repeated N _iter times.

In addition, instead of formula 6, ξ that maximizes formula 5 may be arbitrarily selected and executed. Formulas 5 and 6 are lighter than the calculation of mutual information, so the total calculation time of Algorithm 1 is reduced as a result.

(Example)
As an embodiment of the above process, a configuration example of the network fault location identification device 100 and a processing procedure example using this configuration will be described.

Figure 5 shows an example of the configuration of the network fault location identification device 100. As shown in Figure 5, the network fault location identification device 100 has an input UI 110, a state number reduction unit 120, a test execution unit 130, a mutual information maximization unit 140, a posterior distribution calculation unit 150, and an output UI 160. The state number reduction unit 120, the test execution unit 130, and the posterior distribution calculation unit 150 are connected to the target network 200 as shown in the figure. Note that the "state number reduction unit 120 + mutual information maximization unit 140" may be called a test optimization unit. Also, the posterior distribution calculation unit 150 may be called a test result analysis unit.

The processing procedure of the network fault location identification device 100 having the above configuration will be explained with reference to the flowchart in Figure 6.

In S101, data and parameters (prior distribution Pr(s), U, N _B , B, etc.) required for executing the algorithm are first input to the input UI 110. In S102, the state number reduction unit 120 determines ξ based on this in accordance with Procedure 3 and passes it to the test execution unit 130.

In S103, the test execution unit 130 executes a test on the target network 200 using a connectivity check program such as ping. In S102 again, the state number reduction unit 120 determines the next ξ based on the obtained results in accordance with Procedure 3.

After steps S102 and S103 have been performed a set number of times, in step S104, the mutual information maximization unit 140 creates M according to the greedy method of Algorithm 1. This is passed to the test execution unit 130, which executes a test on the target network 200 in step S105.

The result is passed to the posterior distribution calculation unit 150, and in S106, the posterior distribution is calculated according to the Bayesian estimation framework. The obtained posterior distribution is passed to the mutual information maximization unit 140, and the above steps (S104 to S106) are repeated according to the loop of Algorithm 1. After a predetermined number of executions, the estimated state is output to the output UI 160 as the maximum likelihood value from the final posterior distribution. In S107, the output UI outputs the estimated state.

(About the effects)
The technology according to the present embodiment described above makes it possible to pinpoint a fault location as accurately as possible with a limited number of path measurements under probabilistic routing. This technology prioritizes path measurements that are effective for fault identification, so the number of path measurements required to identify a fault is reduced, and it is expected to shorten the time required to identify a fault and reduce the network load.

The evaluation was performed using the three network data [Non-Patent Document 6] in Fig. 7. In Fig. 7, #failures represents the number of simultaneously failed edges, and |S _k | is the total number of possible states. The following settings are considered for each network.

The number of groups is |C| = 3|V|, and for each node, when it is the S node, three randomly selected nodes are the D nodes, and node pairs (groups) are determined. For each node pair, the shortest path, the second shortest path, and the third shortest path are considered as monitoring paths (|A| = 9|V|). The i-th shortest path for each group has the probability

で選択されるようにした（ｌ_ｉはパスの長さ）。Ｓノードを同じくする３つのグループを一度ずつ実行するものを一つのプローブテストξとみなし、全部で｜Ｘ｜＝｜Ｖ｜パターンのテストを考えた。初期状態分布Ｐｒ（ｓ）は一様とし、Ｎ_ｙ＝３０とした。また、Ｐｒｏｃｅｄｕｒｅ３による状態削減はＮ_ｉｔｅｒ＝１０として実施した。

(l _i is the path length). Three groups with the same S node are executed once each, which is regarded as one probe test ξ, and a total of |X| = |V| patterns were considered for testing. The initial state distribution Pr(s) was uniform, and N _y = 30. In addition, state reduction by Procedure 3 was performed with N _iter = 10.

In addition to the technique according to the present embodiment (denoted as PM), we also carried out Random, LS [Non-Patent Document 2], and LASSO [Non-Patent Document 3] for comparison. Random is the technique according to the present embodiment in which ξ is selected randomly without using mutual information.

LS and LASSO are existing methods that use non-adaptive approaches proposed as network tomography in probabilistic routing. For LASSO, we performed the experiment by changing the hyperparameter λ to 0.0001, 0.001, and 0.01.

The accuracy rate was used as the evaluation index. For a state with two faulty branches, the answer was considered correct only when both were identified. For Missouri, experiments were performed for all true state patterns, and for ION and Ntelos, experiments were performed for 50 true state patterns (selected at random), and the accuracy rate was calculated.

The experimental results are shown in Figures 8 to 10. In each figure, the horizontal axis is the total number of tests N, and the vertical axis is the accuracy rate. It can be seen that the method PM according to this embodiment shows higher performance than the existing methods LS and LASSO. For example, to exceed a accuracy rate of 0.96, the best existing methods require 160 (Missouri), 320 (ION), and 640 (Ntelos) tests, whereas PM requires only 22, 34, and 34 tests, respectively. PM also exceeds the results of Random, demonstrating the usefulness of using mutual information.

(Hardware configuration example)
The network failure point identification device 100 can be realized, for example, by causing a computer to execute a program. This computer may be a physical computer or a virtual machine on the cloud.

That is, the network fault location identification device 100 can be realized by executing a program corresponding to the processing performed by the network fault location identification device 100 using hardware resources such as a CPU and memory built into a computer. The above program can be recorded on a computer-readable recording medium (such as a portable memory) and stored or distributed. The above program can also be provided via a network such as the Internet or email.

Figure 11 is a diagram showing an example of the hardware configuration of the computer. The computer in Figure 11 has a drive device 1000, an auxiliary storage device 1002, a memory device 1003, a CPU 1004, an interface device 1005, a display device 1006, an input device 1007, an output device 1008, etc., all of which are interconnected by a bus BS.

The program that realizes the processing on the computer is provided by a recording medium 1001, such as a CD-ROM or a memory card. When the recording medium 1001 storing the program is set in the drive device 1000, the program is installed from the recording medium 1001 via the drive device 1000 into the auxiliary storage device 1002. However, the program does not necessarily have to be installed from the recording medium 1001, but may be downloaded from another computer via a network. The auxiliary storage device 1002 stores the installed program as well as necessary files, data, etc.

When an instruction to start a program is received, the memory device 1003 reads out and stores the program from the auxiliary storage device 1002. The CPU 1004 realizes functions related to the light touch maintenance device 100 in accordance with the program stored in the memory device 1003. The interface device 1005 is used as an interface for connecting to a network, etc. The display device 1006 displays a GUI (Graphical User Interface) or the like according to a program. The input device 1007 is composed of a keyboard and mouse, buttons, a touch panel, etc., and is used to input various operational instructions. The output device 1008 outputs the results of calculations.

(Additional Note)
This specification discloses at least the network fault location locating device, the network fault location locating method, and the program described in the following sections.
(Section 1)
A network fault location identification device for identifying a fault location in a target network, comprising:
a test optimizer for computing optimal path measurement tests to perform on the target network;
a test execution unit that executes the test calculated by the test optimization unit on the target network;
a test result analysis unit that narrows down the network state according to the result of the test performed by the test execution unit;
The test optimization unit calculates a test using the analysis result obtained by the test result analysis unit, the test execution unit executes the test, and the test result analysis unit repeats the process of narrowing down the network state according to the test result, one or more times.
(Section 2)
A network fault location identification device as described in claim 1, in which the routing information in the target network does not uniquely determine the path connecting the source and destination nodes, but is determined probabilistically, and it is not possible to observe which path was selected in the test, and only the probability distribution is available.
(Section 3)
The network fault location identification device described in claim 1 or 2, wherein the test optimization unit selects a test that is an optimal solution or a near-optimal solution to a problem of maximizing mutual information between a random variable representing a test execution result and a random variable representing a state of the target network.
(Section 4)
4. The network fault location identification device according to claim 1, wherein the test optimization unit selects a test that increases an expected value of a number of network states that can be excluded as candidates based on a result of the test execution.
(Section 5)
4. The network fault location identification device according to claim 1, wherein the test result analysis unit updates a probability distribution representing a network state based on a result of execution of the test in accordance with a framework of Bayesian estimation.
(Section 6)
A network fault location identification method executed by a network fault location identification device for identifying a fault location in a target network, comprising:
a test optimization step for computing optimal path measurement tests to be performed on the target network;
a test execution step of executing the test calculated by the test optimization step on the target network;
a test result analysis step of narrowing down the network state according to the result of the test performed by the test execution step;
A network fault location identification method, comprising: calculating a test in the test optimization step using the analysis results obtained in the test result analysis step; executing the test in the test execution step; and narrowing down the network state according to the test results in the test result analysis step, the above steps being repeated one or more times.
(Section 7)
A program for causing a computer to function as each unit in the network fault location locating device according to any one of claims 1 to 5.

Although the present embodiment has been described above, the present invention is not limited to this specific embodiment, and various modifications and variations are possible within the scope of the gist of the present invention described in the claims.

100 Network fault location identification device 110 Input UI
120 State number reduction unit 130 Test execution unit 140 Mutual information maximization unit 150 Posterior distribution calculation unit 160 Output UI
1000 Drive device 1001 Recording medium 1002 Auxiliary storage device 1003 Memory device 1004 CPU
1005 Interface device 1006 Display device 1007 Input device 1008 Output device

Claims (7)

A network fault location identification device for identifying a fault location in a target network, comprising:
a test optimization unit for calculating path measurement tests to be performed on the target network;
a test execution unit that executes the test calculated by the test optimization unit on the target network;
a test result analysis unit that narrows down the state of the target network according to the result of the test by the test execution unit,
a network fault location identification device, the network fault location identification device repeating, one or more times, a process in which the test optimization unit calculates a further test using an analysis result obtained by the test result analysis unit, the test execution unit executes the further calculated test, and the test result analysis unit narrows down the state of the target network according to the result of the further calculated test;
The test optimization unit calculates a further test that is an optimal solution or a near-optimal solution of a problem of maximizing mutual information between a random variable representing the result of executing the test and a random variable representing the state of the target network. A network fault location identification device for identifying a fault location in a target network, comprising:
a test optimization unit for calculating path measurement tests to be performed on the target network;
a test execution unit that executes the test calculated by the test optimization unit on the target network;
a test result analysis unit that narrows down the state of the target network according to the result of the test by the test execution unit,
a network fault location identification device, the network fault location identification device repeating, one or more times, a process in which the test optimization unit calculates a further test using an analysis result obtained by the test result analysis unit, the test execution unit executes the further calculated test, and the test result analysis unit narrows down the state of the target network according to the result of the further calculated test;
The test optimization unit calculates further tests that will increase an expected value of the number of states of the target network that can be excluded as candidates based on results of the tests. A network fault location identification device for identifying a fault location in a target network, comprising:
a test optimization unit for calculating path measurement tests to be performed on the target network;
a test execution unit that executes the test calculated by the test optimization unit on the target network;
a test result analysis unit that narrows down the state of the target network according to the result of the test by the test execution unit,
a network fault location identification device, the network fault location identification device repeating, one or more times, a process in which the test optimization unit calculates a further test using an analysis result obtained by the test result analysis unit, the test execution unit executes the further calculated test, and the test result analysis unit narrows down the state of the target network according to the result of the further calculated test;
The test result analysis unit updates a probability distribution representing the state of the target network based on the execution results of the test in accordance with a Bayesian estimation framework. A network fault location identification method executed by a network fault location identification device for identifying a fault location in a target network, comprising:
a test optimization step for computing path measurement tests to be performed on the target network;
a test execution step of executing the test calculated by the test optimization step on the target network;
a test result analysis step of narrowing down the state of the target network according to the result of the test performed by the test execution step;
a test optimization step using an analysis result obtained by the test result analysis step, a test execution step executing the further calculated test, and a process of narrowing down the state of the target network according to the result of the further calculated test by the test result analysis step, the process being repeated one or more times;
A network fault location method, in which in the test optimization step, a further test is calculated which is an optimal solution or a near-optimal solution of a problem of maximizing mutual information between a random variable representing the result of executing the test and a random variable representing the state of the target network. A network fault location identification method executed by a network fault location identification device for identifying a fault location in a target network, comprising:
a test optimization step for computing path measurement tests to be performed on the target network;
a test execution step of executing the test calculated by the test optimization step on the target network;
a test result analysis step of narrowing down the state of the target network according to the result of the test performed by the test execution step;
a test optimization step using an analysis result obtained by the test result analysis step, a test execution step executing the further calculated test, and a process of narrowing down the state of the target network according to the result of the further calculated test by the test result analysis step, the process being repeated one or more times;
A network fault location method, comprising: calculating, in the test optimization step, a further test that increases an expected value of the number of states of the target network that can be excluded as candidates, based on a result of executing the test. A network fault location identification method executed by a network fault location identification device for identifying a fault location in a target network, comprising:
a test optimization step for computing path measurement tests to be performed on the target network;
a test execution step of executing the test calculated by the test optimization step on the target network;
a test result analysis step of narrowing down the state of the target network according to the result of the test performed by the test execution step;
a test optimization step using an analysis result obtained by the test result analysis step, a test execution step executing the further calculated test, and a process of narrowing down the state of the target network according to the result of the further calculated test by the test result analysis step, the process being repeated one or more times;
In the test result analysis step, a probability distribution representing the state of the target network is updated based on the execution results of the tests in accordance with a Bayesian estimation framework. A program for causing a computer to function as each part of a network fault location identification device according to any one of claims 1 to 3.

Images