JP7209665B2 - Reachability test method, test program and test system between node pairs in network - Google Patents

Description

The present invention relates to a reachability test between nodes in a network topology, and relates to a reachability test method and a test program between node pairs for shortening the test time for testing (confirming) reachability between end-to-end node pairs. and test systems.

When a network administrator designs or changes a network to operate, it is necessary to test (confirm) reachability between arbitrary end-to-end node pairs in order to confirm that there are no errors in the network design. It is done. For example, Non-Patent Document 1 describes a verification that combines a white-box switch (WB-SB) and OSS to automatically generate a failure at any location within the verification requirement range in the verification network, and confirms the behavior of the network. Design methods for automated systems have been proposed.

Non-Patent Document 2 proposes a technique for estimating reachability between node pairs by communicating packets to a network.

A network generally has a redundant configuration so that communication can be performed even in the event of a failure. For this reason, it is necessary to check the reachability between node pairs not only for the shortest route between each node pair but also for redundant routes that become effective in the event of a failure. For that purpose, it was necessary to confirm reachability for all paths of all node pairs in the network.
Even if the end node pair is the same, if the nodes passing through are different, the paths are treated as different paths, so the number of tests for reachability confirmation becomes enormous.

The Institute of Electronics, Information and Communication Engineers IEICE Technical Report NS2016-34 (2016-6) p35-40 "A Proposal for Designing a Verification Automation System for Networks Utilizing White Box Switches and OSS" The Society of Instrument and Control Engineers, Vol.55, p990-995 "Network Tomography Based on Sparsity of Communication Quality"

To check the presence or absence of reachability between node pairs when performing reachability tests between all node pairs in the network, and if there is no reachability, where the error is on the route (such as lack of redundant paths) , a huge number of tests were required, and there was a problem that the reachability test took a long time.

DISCLOSURE OF THE INVENTION The present invention has been proposed in view of the above circumstances, and includes a method for testing reachability between node pairs, a test program, and a test capable of shortening test time when performing a reachability test between node pairs in a network. The purpose is to provide a system

In order to achieve the above object, a method for testing reachability between node pairs in a network according to claim 1 of the present invention is a method for testing reachability between arbitrary node pairs for paths between a plurality of nodes and each node that constitute the topology of the network. The test method for confirming is characterized by including the following procedures.
A route calculation procedure for calculating a path serving as a route between each node pair and the path length (k) of the path from topology information.
A test execution procedure for selecting a node pair with a long path length (k) and executing a reachability test on the path of the node pair.
Then, when the reachability between the node pair can be confirmed in the test execution procedure, the reachability test for the path sharing the destination between the node pair is not required, and when the reachability between the node pair cannot be confirmed removes one path from the beginning of the path and sets the path with the path length (k-1) as a new path, and repeats the test execution procedure until the path length (k-1) becomes 1.

Claim 2 is the method for testing reachability between node pairs in the network of claim 1,
The route calculation procedure is a shortest route calculation procedure for calculating a path serving as the shortest route between each node pair and a path length (k) of the path from topology information,
The test execution procedure is characterized by selecting a node pair having the longest path length (k) of the shortest path and executing a reachability test on the path of the node pair.

Claim 3 is the method for testing reachability between node pairs in the network of Claim 2,
The route calculation procedure includes, in addition to the shortest route calculation procedure, a redundant route calculation procedure for calculating a path serving as a redundant route with respect to the shortest route and a path length (k) of the path,
The test execution procedure is characterized by selecting a node pair having the longest path length (k) of the redundant route and executing a reachability test on the path of the node pair.

Claim 4 is a method for testing reachability between node pairs in a network according to any one of claims 1 to 3,
The reachability test of the test execution procedure is characterized in that while the paths of all node pairs in the network are tried, the paths that have been tested once are considered to have been tested, and duplicate tests are not performed.

According to a fifth aspect of the present invention, there is provided a test program for inter-node pair reachability in a network, which uses a computer to execute each procedure according to the first to fourth aspects.

Claim 6 is characterized by comprising the following configuration in a test system for confirming reachability between an arbitrary pair of nodes with respect to a plurality of nodes constituting a network topology and a path between each node.
Topology information derivation part. The topology information deriving unit derives a plurality of node pairs including a plurality of paths connecting a plurality of nodes as topology information of the network.
Node pair selection part. This node pair selection unit determines the longest path length (k) from the topology information obtained by calculating the path serving as the route between each node pair and the path length (k) of the path for each node pair derived by the topology information derivation unit. select a pair of nodes.
Pass Attainment Test Department. This path reachability test section conducts a reachability test on all paths of the selected node pair. Further, when the reachability between the node pair can be confirmed in the reachability test, the path reachability test unit dispenses with the reachability test for paths sharing the destination between the node pair. If the reachability cannot be confirmed, a path with a path length (k-1) obtained by removing one path from the head is used as a new path, and the reachability test is repeated until the path length (k-1) becomes 1. .

According to the present invention, when performing a reachability test between node pairs, a node pair having a long path length (k) is selected, and the reachability is checked comprehensively by performing the reachability test on the paths of the node pair. , When reachability between node pairs can be confirmed, the number of tests can be minimized by eliminating the need for reachability tests for paths that share the same destination between node pairs, without performing duplicate path tests. can be done.

By performing the shortest path calculation and the redundant path calculation, it is possible to check the location where the redundancy is insufficient on the path in the network.

Duplicate test execution can be omitted by using the test result to mark a path that has undergone a reachability test once as having been tested.

1 is a model diagram showing an example of network topology; FIG. 2(a) to 2(d) are explanatory diagrams for performing a reachability test between node pairs in the network topology of FIG. 1; FIG. FIG. 4 is a model diagram showing an example of a case where there is no redundancy between node pairs A and B in network topology; 1 is a block diagram showing the configuration of a node pair reachability test system; FIG. FIG. 10 is a flow chart for explaining a reachability test method in the preprocessing unit of the inter-node-pair reachability test system; FIG. 1 is a model diagram showing a network topology to be tested; FIG. (a) is a table of node connection links obtained in the preprocessing of the reachability test between node pairs, and (b) is a table of loop path lists. FIG. 10 is a table of a node pair list (after preprocessing) obtained in preprocessing of inter-node pair reachability test; FIG. FIG. 7 is a model diagram for explaining path routes (path #1 to path #4) between node pairs (A, D) in the network topology of FIG. 6; 10 is a flow chart for explaining a reachability test method in the reachability test unit of the inter-node-pair reachability test system; 4 is a path list table obtained in a reachability test between node pairs; FIG. 11 is a table of a node pair list obtained in a node pair reachability test (after the end of the test); FIG.

An overview of the node pair reachability test method in the network of the present invention will be described with reference to FIGS. 1 to 3. FIG.
The inter-node pair reachability test method in the network of the present invention tests the known network topology and the route between the node pairs in the routing table on each node. Each node in the network is, for example, a network device such as a server, a router, or a switch. A path in the case of →C is expressed as <A, B, C>. Note that (A, C) and (C, A) are different node pairs. Routes between node pairs are determined using routing tables held by nodes.

The reachability test between node pairs is basically performed on the path (path length k) from Src (source) to Dst (destination) of the node pair, and then a new path with one removed from the end of the path (path length k=k−1) and test against this path. This test is repeated until path length k=1.

As a result of conducting reachability tests for each path, if there is reachability (represented by "○" in reachability), it is judged that there is reachability for the path and all paths that have the same destination as the path (these All paths are marked with reachability "○"), and the subsequent tests for these paths are omitted and are considered to have been tested. If the destination is the same path, it can be determined that the reachability is ensured, thereby reducing the number of tests. On the other hand, if there is no reachability (represented by "x" in reachability), a new path (path length k-1) is created and a reachability test is attempted. Note that the test is not performed for paths that have already been tested for reachability.

For example, as shown in FIG. 1, when considering a node pair (A, D) in a network topology consisting of nodes A, B, C, D, E, F, and G, path 1< A, B, C, D> and a path 2<A, G, F, E, D> as a redundant route. A reachability test is performed for each of these two paths.

First, test 1 (path length k=3) for path 1 <A, B, C, D> is performed ((a) in FIG. 2). ), the following tests 2 (path length k=2) and 3 (path length k=1) are not performed, and paths <B, C, D> and <C, D> also reach If test 1 has reachability “○”, test 2 (path length k=2) and test 3 (path length k=1 ) can be omitted (the number of tests can be reduced).

On the other hand, if there is no reachability in test 1 (represented by "x" in reachability), the test of paths <B, C, D> with one less from the top of the paths is performed (test 2). As a result, when the reachability is "O", the reachability of the path <C, D> is determined to be "O" without executing the test 3. This reduces the number of tests.
If the reachability is "x" in test 2, the test of path <C, D> with one less than the first path is performed (test 3). In this way, when the reachability is "x", the reachability test is repeated until the path length k=1.

To determine reachability ``○'' or reachability ``X'' in the reachability test, check whether the destination (node pair Dst) and the next hop node in the routing table follow the route of the path. by This confirms whether a forward path from Src to Dst can be reached, and for the reverse direction, exchanges the end points Src and Dst of the node pair.
In the case of pass 1, if Src and Dst are interchanged, pass 1 <D, C, B, A> is obtained, and test 1 (path length k=3) is performed ((b) in FIG. 2). ○”, so the following test 2 (path length k=2) and test 3 (path length k=1) are not performed, and paths <D, C, B> and <D, C> are also reachable. Confirm “O” and register “Completed” in the Test completed column.Therefore, if Test 1 is “Achieved O”, Test 2 (path length k = 2) and Test 3 (path length k = 1) can be omitted (the number of tests can be reduced).

As another method of confirming reachability, data (hereinafter referred to as "probe") can be directly transferred to the network and tested in the same way. Alternatively, the reachability is determined as “x”.
In addition, in reachability tests using probes, there is also a method of confirming connectivity (simultaneous forward and reverse direction tests) using probe responses sent from Src to Dst. In this test method, between paths <C, D>, it cannot be determined that either the forward or reverse direction (or both) is reached x. It is necessary to carry out and judge.

Subsequently, the reachability test described above is similarly performed for path 2 <A, G, F, E, D>. In this example, the reachability test (test 1) of path <A, G, F, E, D> with path length k=4 and the path The reachability test (test 2) of path <G, F, E, D> with length k = 3 becomes reachability "x", and the reachability test (test 2) of path <F, E, D> with path length k = 2 Since test 3) results in reachability "○", the reachability of path <E, D> is "○" without executing the reachability test (test 4) of path <E, D> with path length k=1. is determined. That is, since the reachability of test 3 is "O", only the execution of test 4 (path length k=1) can be omitted (the number of tests is reduced) (FIG. 2(c)).

In the test of path 2 <D, E, F, G, A> in which Src and Dst are exchanged, the reachability test of path <D, E, F, G, A> with path length k = 4 (test 1) , the reachability test (test 2) of path <E, F, G, A> with path length k = 3, and the reachability test (test 3) of path <F, G, A> with path length k = 2 reach Only the reachability test (test 4) of the path 2<G, A> with the path length k=1 is marked with the reachability of "X". In this case, all paths are tested ((d) no reduction in the number of tests in FIG. 2).

For all node pairs, the results of the reachability test for each path are registered in the node pair list, and if all the paths between the node pairs have reachability "O", the node pair is "reachable (redundant) )”.

As shown in the network of FIG. 3, if the number of paths between the node pairs (A, B) (B, A) is 1, there is an error on the route (insufficient redundant paths). I judge.

Next, a node pair reachability test system for performing the reachability test method between node pairs in the network described above will be described with reference to FIG. The inter-node pair reachability test is performed at the time of designing a network on an actual machine or desk or at the time of a change due to the addition of a node or the like. The node pair reachability test system is constructed on a computer by downloading and installing software via a recording medium storing a node pair reachability test program or via the Internet.

The computer on which the inter-node-pair reachability test system is constructed consists of a ROM in which a basic program including an operating system (OS) and various basic devices are stored, and a hard disk drive (HDD) in which various programs and data are stored. , a media drive device that reads programs and data from storage media such as CD-ROMs and DVDs, a CPU that executes programs, a RAM that provides a work area for this CPU, and an input/output interface (I / F) It has a general configuration mainly composed of a connected display, a keyboard, a pointing device such as a mouse, and a parallel/serial I/F for communicating with an external device.
In the node pair reachability test system of this embodiment, the node pair reachability test program is input from the serial/parallel I/F or read by the media drive device and prestored in the HDD. The inter-node pair reachability test program is stored in a storage medium, read by a media drive device, and installed in the HDD.

As shown in FIG. 4, the node pair reachability test system constructed by installing the node pair reachability test program includes a preprocessing unit 10 for detecting configuration information of a network to be tested, and a detected configuration It has a reachability test section 20 for performing a reachability test on information, and performs a reachability test between node pairs on a network to which a computer on which a reachability test system between node pairs is constructed is connected.

The preprocessing unit 10 includes a topology information derivation unit 11. The topology information derivation unit 11 generates nodes connected to the network and paths connecting the nodes as configuration information (topology information) for the network topology to be tested. Also, a process of deriving a link serving as a connection point, a topology loop connecting Src (source) and Dst (destination) nodes, and a node pair corresponding to Src and Dst is performed.
The reachability testing section 20 includes a node pair selection section 21 and a path reachability testing section 22 . The node pair selection unit 21 selects each node pair derived by the topology information derivation unit 11, and the path reachability test unit 22 performs a reachability test on all paths of the selected node pairs.

In addition, even if the computer on which the reachability test system between node pairs is constructed is not necessarily connected to the test target network, if topology information and route information of each node are stored on the computer on which the system is constructed, each Since the next hop is known from the route information on the node, it is possible to determine whether or not the node can be reached by tracing this. Therefore, a reachability test can be performed on the desk at the design stage before actually constructing the network.

Detailed processing in the preprocessing unit 10 will be described with reference to the flowchart of FIG. 5 and FIGS. 6 to 9. FIG. The network to be tested is composed of nodes A, B, C, D, E, and F, as shown in FIG. Assume a model (FB has an error in connection setup).

Analyze the network topology to be tested, find all nodes, all links, and all loops by graph search, and create a node connection link table (Fig. 7(a)) and a loop path list (Fig. 7(b)) as topology information. and register (step 101).
The node connection link table (FIG. 7(a)) grasps the connection points between each node, and manages "1" when connected and "0" when not connected.
The loop path list (FIG. 7(b)) treats multiple nodes forming a loop in the topology as one roof path. Whether a loop exists in the topology is derived by graph search (if all the links connected to the node are traced and the same node appears, the partial route between them is regarded as a loop). In the case of the network of FIG. 6, there are three roof paths: "A, B, F", "B, C, D, E, F" and "A, B, C, D, E, F".

Subsequently, a node pair list (FIG. 8) for grasping the information of all node pairs forming the network is created. For example, in the case of the node pair (A, D) in the network shown in FIG. 6, as shown in FIG. 9, there are four paths #1 to #4 from node A to node D, and each path is registered in the node pair list.

When creating the node pair list, first, each data of the node pair list is initialized (step 102).
Next, for each node pair, the number of paths connecting the node pairs (total number of paths), the shortest path (path #1), and other redundant paths (paths #2 to #4) are derived. , paths (nodes constituting the paths) and path lengths k are set and registered for the path #1 that is the shortest path and the paths #2 to #4 that are the redundant paths, respectively.
Also, in the node pair list, the test completed column of the reachability test described later ("Untested" is set if not executed), the reachability of paths #1 to #4 when the reachability test was performed, and the topology A redundancy column is provided for confirming redundancy.

The node pair list (FIG. 8) is created for all node pairs in the network topology (step 103). Here, node pairs (A, B) and (B, A) are treated as separate pairs.

A specific node pair list creation process will be described.
When creating the node pair list, one of the node pairs in the network topology is selected (step 104).

Based on the topology information derived in step 101, it is determined whether or not the path of the node pair contains a loop (step 105). There are three loops in the node pair path in the network of FIG. If the path does not include a loop, the shortest path between each node pair and the path length k are calculated and registered in path #1 of the node pair list (step 106).

If the path contains a loop in step 105, it is decomposed into single paths, and all q decomposed paths are registered in path #1, path #2, . (step 107).

Additionally, the total number of paths in the node pair is set (step 108). For example, for node pair (A, D), the paths are path #1 <A, B, C, D>, path #2 < A, F, E, D>, path #3 < A, B, F, E, D> and pass #4<A, F, B, C, D>, so the number of passes=4 is set.
Similarly, the number of paths is set to 4 for the node pair (A, C) and the node pair (A, E), and the number of paths to 3 for the node pair (A, B) and the node pair (A, F). (Fig. 8).

The processing of steps 104 to 108 is performed (step 109) until the number of paths has been set for all node pairs (step 108), and the node pair list (FIG. 8) in which each information is set for all node pairs is completed. do.

Next, detailed processing in the arrival test unit 20 will be described with reference to the flowchart of FIG. 10 and the tables of FIGS. 11 and 12. FIG.

When performing a reachability test after the preprocessing 100 in the preprocessing unit 10 (FIG. 4) is completed, one node pair is selected (step 201). The selection of the node pair is performed from the node pair list (Fig. 8). First, the node pair M that has not been tested (the "tested column" is "untested") and the path length k of path #1 (shortest route) is the longest. to select. For example, in the node pair list of FIG. 8, the node pair (A, D) indicated by the arrow is selected, and the path P becomes <A, B, C, D>.

The path P of the node pair M selected in step 201 is selected (step 202), and the selected path p and all paths including partial paths are registered in the path list (FIG. 11) as test paths (step 203).

To register a test pass, follow the steps below.
First, the path #1 (shortest path) selected in step 201 is defined as a path P (path p, path length k). It is registered together with the information (before replacement=1) (test number 1 in FIG. 11).

Next, a path obtained by removing one path from the top of the path p is registered as a new path p in the path list. This process is repeated until path length k=1 (test numbers 2 and 3 in FIG. 11).
For example, if node pair M = (A, D) and path P = <A, B, C, D>, <A, B, C, D> with k = 3, <B, C, D with k = 2 > and <C, D> with k=1 are registered.

Subsequently, the same processing is performed for the path p in which Src and Dst of the path P are exchanged, and <D, C, B, A> for k=3, <C, B, A> for k=2, k = 1 <B, A> three paths are registered (test numbers 4 to 6 in FIG. 11). After replacement, Src/Dst information (after replacement=2).

Next, for path P=<A, F, E, D>, which is path #2 (redundant path), the same process as for path #1 is performed, and <A, F, E, D>, k <F, E, D> at k=2, <E, D> at k=1, <D, E, F, A> at k=3 with Src and Dst exchanged, <E, F at k=2, A>, six paths of <F, A> with k=1 are registered (test numbers 7 to 12 in FIG. 11).

Next, for path P=<A, B, F, E, D> which is path #3 (redundant path), <A, B, F, E, D> with k=4 and <B with k=3 , F, E, D>, <F, E, D> at k = 2, <E, D> at k = 1, <D, E, F, B, A at k = 4 with Src Dst replaced >, <E, F, B, A> with k = 3, <F, B, A> with k = 2, and <B, A> with k = 1 (Test No. 13-20).

Next, for path P=<A, F, B, C, D> which is path #4 (redundant path), <A, F, B, C, D> at k=4, <F at k=3 , B, C, D>, <B, C, D> at k = 2, <C, D> at k = 1, <D, C, B, F, A at k = 4 with Src Dst replaced >, <C, B, F, A> with k = 3, <B, F, A> with k = 2, and <F, A> with k = 1 (test number in FIG. 11). 21-28).
As described above, registration of all test paths relating to the selected node pair M=(A, D) (indicated by arrows in FIG. 8) to the path list in FIG. 11 is completed.

One of the paths registered in the path list (FIG. 11) in step 203 is selected (referred to as p) in the order of registration, and is set as path p' for which the reachability test is to be performed (step 204).

A reachability test is performed on the path p' (step 205).
As a reachability test method, one-way reachability confirmation (following the route table sequentially) is basically used. Even if the test environment is an actual device and a two-way simultaneous test method (for example, ping command) is used, in order to determine the direction of non-reachability in the non-reachability section, one-way reachability confirmation means is required. to implement.

The reachability of the path p' is determined (step 206), and if it is reached, the reachability "o" is recorded in the reachability column of the path list (FIG. 11) (step 207). In this case, reachability "0" is recorded in the list for the remaining routes (paths) that have the same destination (Dst), and testing of the remaining paths is omitted.
For example, in the case of the node pair <A, D> of the path #1 described above, if reachability is confirmed by the test of the path p'=<A, B, C, D>, the remaining paths <B, C, D >, <C, D> are also set to reachability “O”.
When the test of the relevant path p of the selected node pair is completed, reachability "◯" is recorded in the reachability column of the relevant paths (path #1 to path #4) in the node pair list (FIG. 12) (step 208).

As a result of the determination of the reachability of path p' (step 206), if the reachability is not reached, the reachability column of the corresponding path (path #1 to path #4) in the node pair list (Fig. 11) is marked with "x". Record (step 209).

If the reachability of the path p' is "x", determine whether the length of the selected path is k>1 (step 210); if k>1, remove one tip of the selected path; This is taken as the newly selected path p' (k=k-1) (step 211), and the processing from step 205 is repeated.

On the other hand, if k=1 at step 210, the test of the selected path p is completed, and the arrival result is stored in the node pair list (FIG. 12) (step 208).

Next, it is determined whether or not the exchange of Src and Dst has been completed (step 213). If the exchange has not been completed yet, the Src and Dst of the node pair are exchanged from the path list, and the path of the pair is the test path p'. (step 214), and the processing from step 205 onwards is performed.

When the replacement of Src and Dst is completed in step 213 and the test of the path p is completed, it is determined whether there is another path in the selected node pair M (step 215). repeat. If it does not exist, the test of the selected node pair M is completed, and "completed" is set in the tested column of the node pair (A, D) in the node pair list (FIG. 12) (step 216).

Next, returning to step 201, a node pair other than the node pair (A, D) whose test path registration has been completed is selected from the node pair list (FIG. 8). The selection of the node pair is based on the node pair M (node pair (other than A, D)). In this case, the node pair (A, E) is selected and the path P becomes <A, B, C, D, E>.

For the selected node pair (A, E), the test paths of the path list in FIG. Registration is performed and reachability tests (steps 202-216) for each path are performed.

Steps 201 to 216 are repeated until there are no untested node pairs in the node pair list of FIG. 8 (step 200).

When performing the reachability test on each path of the node pair, as described in step 207, for paths with a common destination, if the reachability of the path test with a long path length is "O", the path length is Short path testing can be omitted.
For example, for path 1 of node pair (A, D), test number 2 (<B, C, D> for k=2) and test number 3 (<C, D> for k=1) have already been tested. Since the reachability "○" was confirmed in test number 1 (<A, B, C, D> of k = 3) where In 2 and Test 3, the reachability “○”, which is the result of the reachability ◯× in Test 1, is registered as it is. Similarly, test numbers 5 and 6 in which Src and Dst of the node pair are exchanged in path #1 can be omitted. Therefore, the tests of test numbers 2, 3, 5 and 6 in pass #1 can be omitted (the light gray portion of pass #1 in FIG. 11).
Similarly, the tests of test numbers 8, 9, 11 and 12 in pass #2 can be omitted (light gray area of pass #2 in FIG. 11).

Also, a path that has been subjected to the reachability test once is regarded as having been tested without being subjected to the test, thereby omitting the execution of redundant tests.
For example, for path #3 of node pair (A, D), test number 13 (<A, B, F, E, D> for k=4) and test number 14 (<B, F, E , D>) becomes reachability “x”, and for test number 15 (<F, E, D> of k=2) and test number 16 (<E, D> of k=1) to be performed subsequently, path Since test numbers 8 and 9 of #2 are performed, reachability "○", which is the result of reachability ◯×, is registered as it is.
Test number 20, in which the Src and Dst of the node pair are exchanged in path #3, is also performed in test number 6 of path #1, so the reachability "○", which is the result of reachability ◯×, is registered as it is.
Therefore, the tests of test numbers 15, 16 and 20 in pass #3 can be omitted (gray portion of pass #3 in FIG. 11).

Similarly, for path #4 of node pair (A, D), test number 21 (<A, F, B, C, D> for k=4) and test number 22 (<F, B, C, D>) becomes reachability "x", and for the subsequent test number 23 (<B, C, D> of k = 2) and test number 24 (<C, D> of k = 1), Since test numbers 2 and 3 of path #1 are performed, the reachability "○", which is the result of the reachability ◯×, is registered as it is.
Test number 28, in which Src and Dst of the node pair are exchanged in path #4, is also performed in test number 12 of path #2.
Therefore, the tests of test numbers 23, 24 and 28 in pass #4 can be omitted (gray portion of pass #4 in FIG. 11).

The above example shows an example in which the test is omitted when the reachability of a path that has been tested once is "○", but the test can also be performed when the reachability of the tested path is "X". Testing can be omitted.

After all the tests are completed, for each node pair on the node pair list in FIG. 12, all existing paths (path #1 to path #4 for node pair (A, D)) have reachability In this case, it is determined that redundancy is provided, and "o" is set in the "redundancy" column (step 300).
If any route has no reachability and the reachability is "x", or if the number of paths is 1, set "x" in the "redundancy" column. The "Redundancy" column is "X" even when a non-redundant path is included as shown in FIG.
In the above example, since path #3 and path #4 have reachability "x", it is determined that there is an error on the route (insufficient redundant paths).

According to the method for testing reachability between node pairs in a network described above, when performing a reachability test between node pairs, by first selecting a path with a long path length k, it is possible to reduce the number of redundant tests performed. .
Further, by marking a path that has undergone a reachability test once as a tested path, redundant test execution can be omitted.
By performing a reachability test on each path of the shortest path and the redundant path between node pairs in the network, it is possible to determine where redundant paths are lacking.
By constructing a node pair reachability test system on a computer in which a node pair reachability test program is installed, it becomes possible to conduct a reachability test between a network node pair on a real machine and on a desk.

10... Preprocessing unit 11... Topology information derivation unit 20... Arrival test unit 21... Node pair selection unit 22... Path arrival test unit.

Claims (6)

In a test method for confirming reachability between arbitrary node pairs for paths between multiple nodes and each node that make up the topology of the network,
a route calculation procedure for calculating a path serving as a route between each node pair and a path length (k) of the path from topology information;
A test execution procedure for selecting a node pair with a long path length (k) and executing a reachability test on the path of the node pair;
If reachability between the node pair can be confirmed in the test execution procedure, the reachability test for the path sharing the destination between the node pair is not required. A path with a path length (k-1) obtained by removing one from the beginning of the node pair in a network, wherein the test procedure is repeated until the path length (k-1) becomes 1. Reachability test method. The route calculation procedure is a shortest route calculation procedure for calculating a path serving as the shortest route between each node pair and a path length (k) of the path from topology information,
2. The method of testing reachability between node pairs in a network according to claim 1, wherein said test execution procedure selects a node pair having the longest path length (k) of said shortest path and executes a reachability test on the path of said node pair. The route calculation procedure includes, in addition to the shortest route calculation procedure, a redundant route calculation procedure for calculating a path serving as a redundant route with respect to the shortest route and a path length (k) of the path,
3. The method of testing reachability between node pairs in a network according to claim 2, wherein said test execution procedure includes selecting a node pair having the longest path length (k) of said redundant path and executing a reachability test on the path of said node pair. 4. The reachability test according to any one of claims 1 to 3, wherein the reachability test of the test execution procedure is attempted for paths of all node pairs in the network, and the paths tested once are considered to have been tested, and duplicate tests are not performed. Reachability test method between node pairs in networks. 5. A reachability test program between node pairs in a network, characterized in that each procedure according to claim 1 to claim 4 is executed using a computer. In a test system that checks the reachability between arbitrary node pairs for paths between multiple nodes and each node that make up the topology of the network,
a topology information deriving unit that derives a plurality of node pairs including a plurality of paths connecting a plurality of nodes as topology information of the network;
For each node pair derived by the topology information derivation unit, a node pair having the longest path length (k) is selected from topology information obtained by calculating a path serving as a route between each node pair and the path length (k) of the path. a selection unit;
a path reachability test unit that performs a reachability test on all paths of the selected node pair,
The path reachability test unit eliminates the need for a reachability test for a path having a common destination between the node pairs when the reachability between the node pairs is confirmed in the reachability test, and the reachability between the node pairs is not confirmed, a path with a path length (k-1) removed from the beginning of the path is set as a new path, and the reachability test is repeated until the path length (k-1) becomes 1. A reachability test system between node pairs in a network characterized by:

Images