Patent Description:
In artificial systems including a network, an operator executes a procedure such as a command to change settings and make a system transition to a target state. For example, a network operator may execute a command such as address and a route control protocol on a network device such as a router, and updates settings. The router generates a routing table according to settings and transfers a packet. When the settings contain an error, the packet does not reach the destination according to an operational policy, and a failure occurs. When a failure occurs, a network operator identifies the router that is the cause and executes a restoration command to update the settings (performs a transition to a target state where no failure occurs).

In recent years, many studies have been carried out on automatic restoration from a failure. Simply, a method of searching for a command sequence to realize a target state while attempting various commands in an actual system is conceivable. Although this method is accurate because an actual system is used, it takes time to actually execute the system. For example, in the case of a network, a waiting time of several tens of seconds is required for route convergence.

On the other hand, as disclosed in NPL <NUM>, a method using a pseudo-environment (simulator) in which a system is simply modeled has also been studied. This method can be executed in a shorter period of time than in an actual system, but no errors associated with modeling are avoided. Even a command sequence that has realized a target state on a model may not realize a target state in an actual system. In contrast, a command sequence for making an actual system transition to a target state may not reach a target state on a model.

In this context, PL <NUM> discloses an article of manufacture embodied in a computer-readable medium for use in a processing system for modeling configurations of a wireless local area network. The article of manufacture includes a characteristic and configurations receiving logic for causing the processing system to determine a set of original characteristics and configurations of the wireless local area network. As well, a simulation logic for causing the processing system to simulate an outcome based upon a set of configurations in accordance with a goal. In embodiments, the goal may be user defined or based upon historical data. Further, a configuration creation logic for causing the processing system to create a set of new configurations based upon the outcome and a management logic for causing the processing system to apply the set of new configurations to the wireless local area network are provided.

An object of the present disclosure is to search for a command sequence, while preventing overlooking as much as possible, in a shorter period of time than that of searching using only an actual system.

The present disclosure aims to shorten a period of time required to obtain a candidate command sequence by using an actual network and a simulator together.

A device according to the present disclosure is an execution procedure searching device according to claim <NUM>.

A method according to the present disclosure is an execution procedure searching method according to claim <NUM>.

A program according to the present disclosure is a program for causing a computer to implement functions included in the execution procedure searching device according to the present disclosure, and is a program for causing the computer to execute steps included in the execution procedure searching method according to the present disclosure.

According to the present disclosure, it is possible to search for a command sequence, while preventing overlooking as much as possible, in a shorter period of time than that of searching using only an actual system is used.

Note that the present disclosure is not limited to the embodiments described below. These embodiments are just illustrative examples, and the present disclosure can be implemented in forms in which various modifications and improvements are added on the basis of knowledge of those skilled in the art. Note that constituent elements with the same reference signs in the specification and the drawings are assumed to be the same constituent elements.

An operational policy to be satisfied by a network will be defined. The operational policy is defined by a set of three, that is, a packet header, a transmission source router, and a destination router. In the packet header, information of a higher layer, such as a port number, may be defined in addition to a transmission source address and a destination address. For example, in <FIG>, a transmission source address of a packet header is <NUM>. <NUM>, a reception address is <NUM>. <NUM>, a transmission source router is S, and a destination router is T. In the proposed technology, the settings of a router are changed to satisfy an operational policy.

Next, a reachability graph will be defined. This is a directed graph used to evaluate the reachability of a packet. Vertices consist of routers and interfaces. However, the interfaces are sorted into inputs and outputs, and are prepared as pairs. An edge is set between the interfaces that are connected or between a router and an interface. When the network in <FIG> is expressed by a reachability graph, <FIG> is obtained. In the drawing, S, T, A, and B are routers, and e0 and e1 are interfaces.

In the present disclosure, a method of evaluating a reachable range is not limited. A packet may be transmitted from a router of an actual network or may be simulatively evaluated by a simulator. Note that the present disclosure is based on the advent of a high speed simulator such as Batfish (NPL <NUM>). The high speed simulator is technically referred to as a control-plane verifier, and capable of evaluating reachability between designated interfaces using a function reachability. Because the high speed simulator can evaluate a reachability at the time of updating settings in a short period of time without waiting for convergence of a route control protocol, approaches of attempting various settings as in the proposed technology are practical.

<FIG> illustrates an example of the display of a reachable range on a reachability graph. A dashed line indicates a range in which a packet reaches a destination router when the packet and the destination router are given in accordance with a policy in certain router settings. In this example, the packet transmitted from a router A reaches a router T, but neither the packet transmitted from a router S nor B reaches the router T. The packet is also transmitted from the other routers even when a true transmission source is the router S, and a portion that causes this is identified by clarifying a reachable range.

Inputs of a network settings method are as follows.

In the network settings method, a reachable range of a packet described in an operational policy is evaluated in accordance with a topology and router settings, and a command sequence necessary for setting update is output in the state of inconsistency with the policy. That is, an output in the network settings method is as follows.

Note that a setting update command is a pair constituted by a router that executes the command and the command itself (<FIG>). In addition, the commands in the present disclosure include any commands related to the reachability of a packet. Specifically, the commands are setting commands related to an interface address, a route control protocol, and an access control list.

A network setting method according to the present disclosure, which is a method for searching for a command sequence to be set for a plurality of network devices, includes performing a first step for determining whether a network having executed a temporary update command sequence satisfies a predetermined operational policy, and includes executing, until satisfaction for the predetermined operational policy, processing for: performing a second step for determining whether a reachable range of a packet expands with addition of one new candidate command of one or more new candidate commands to the temporary update command sequence on condition that the predetermined operational policy is not satisfied; adding the new candidate command to the temporary update command sequence on condition that the reachable range expands with the addition of the new candidate command, or deleting a command at the end of the temporary update command sequence on condition that the reachable range does not expand with addition of any one of the new commands; and then returning to the first step.

In the present disclosure, the proposed technology will be described based on a network settings method. In the network settings method, a command is executed to update the settings of a router, and a reachable range of a packet is expanded. When a reachable range is expanded by some commands and an operational policy is satisfied, the command sequence is output as a response. In the network settings method, a state where a command sequence serving as a response is searched for can be represented as a search tree. Note that, in a network device setting method, an environment in which commands are attempted may be an actual network or may be a simulator. In the present disclosure, an actual network and a simulator are used together for an environment in which commands are attempted.

As described in the problem, system states (packet reachable ranges) at the time of inputting a command may not match in an actual network and a simulator. When reachable ranges drawn at nodes of a search tree are different, commands to be executed thereafter may also be different, and thus there is a possibility that final search trees and setting update command sequences will also be different.

The only way to confirm the correctness of a command sequence is to attempt the command sequence on an actual network, but it is attempted to reduce a period of time therefor by using a simulator in combination therewith. In addition, overlooking of correct command sequences is avoided as much as possible.

<FIG> illustrates an example of a system configuration of the present disclosure. The execution procedure searching device of the present disclosure includes an actual network reachability evaluation unit <NUM>, a simulator reachability evaluation unit <NUM>, a candidate command generation unit <NUM>, and a control unit <NUM>. The device according to the present disclosure can be implemented using a computer and a program, and the program can be recorded in a recording medium or provided through a network.

The execution procedure searching device according to the present disclosure is communicatively connected to an actual network and a simulator which are not illustrated in the drawings. The candidate command generation unit <NUM> generates candidate commands. The commands are commands that can be used in a router constituting an actual network. A command used in the simulator may be the same command as that in the actual network, but may be any command equivalent to a command in the actual network. The control unit <NUM> causes the actual network and the simulator to execute the command generated by the candidate command generation unit <NUM>. The actual network reachability evaluation unit <NUM> determines a reachable range of a packet in executing a command in the actual network. The simulator reachability evaluation unit <NUM> determines a reachable range of a packet in executing a command in the simulator.

<FIG> is a search tree of searching for a setting update command sequence only in an actual network. <FIG> is a search tree of searching for a setting update command sequence only in a simulator. Nodes of a simulator search tree are primed and referred to as T'<NUM>, T'<NUM>, and the like.

A function Goal (C) for determining whether a certain command sequence C satisfies a policy is defined. According to this function, true is returned as in the following expression when C satisfies the policy. <NUM>] <MAT> False is returned as in the following expression when C does not satisfy the policy. <NUM>] <MAT> Additionally, a function of performing determination in an actual network is defined as Goalr, and a function of performing determination in a simulator is defined as Goals.

An example in <FIG> will be described. Because <FIG> illustrates an actual network, Goalr is used. A reachable range in the initial settings is shown at a node T0 in <FIG>. No packet from any router reach the destination except for a router T that works as a destination.

Next, the candidate command generation unit <NUM> generates some candidate commands. In this specification, this generation method is not limited. The candidate command generation unit <NUM> may select a candidate command from a predetermined command set, or may select a command suitable for the current settings and a reachable range by machine learning. While NPL <NUM> limits a target command type to route information exchange, the proposed technology can handle any command.

Subsequently, the control unit <NUM> causes the actual network to execute a command (@router B. ) that is given to a branch from the root T0 to the node T1. This command executes "interface e0; no ip access-group <NUM> out" in the router B. The actual network reachability evaluation unit <NUM> determines that a packet from the router B reaches the router T.

Because the router S which is a transmission source is not included in the reachable range at the contact point T1, the policy is not satisfied. Thus, when the control unit <NUM> gives a command sequence C<NUM> ("interface e0; no ip access-group <NUM> out" is executed in the router B) with respect to the contact point T1 to Goalr, the actual network reachability evaluation unit <NUM> returns false. <NUM>] <MAT>.

Subsequently, the control unit <NUM> executes a command (@router T. ) which is given to a branch from the root T0 to the node T2. This command executes "router eigrp <NUM>;network <NUM>. <NUM><NUM>. <NUM>" in the router T. The actual network reachability evaluation unit <NUM> determines that a packet from the router A reaches the router T. Because the router S which is a transmission source is not included in the reachable range at a contact point T2, the policy is not satisfied. Thus, the actual network reachability evaluation unit <NUM> also returns false for a command sequence C<NUM> (router T. ) with respect to the contact point T2. <NUM>] <MAT>.

Subsequently, the control unit <NUM> executes a command (@router A. ) which is given to a branch from the root T2 to the node T3. This command executes "router eigrp <NUM>;no passive-interface e0" in the router A. The actual network reachability evaluation unit <NUM> determines that a packet from the router S reaches the destination router T. The actual network reachability evaluation unit <NUM> returns true only for a command sequence C<NUM> with respect to the node T3. <NUM>] <MAT>.

Here, it is assumed that the function Goalr and Goals satisfy the following. <NUM>] <MAT> This indicates that the command sequence that is true in the actual network is also true in the simulator. The converse may not be established (when the simulator is true, the actual network may be true or false). The inverse may not be established (when the actual network is false, the result in the simulator may be true or false). In other words, the simulator has false positives but no false negatives.

For example, in a simulator that does not cope with timer processing of a route control protocol, a route may be established even when a route is not established in the actual network due to an incorrect timer value. In this example,
[Math. <NUM>] <MAT> and
[Math. <NUM>] <MAT> , and thus Formula (<NUM>) is satisfied.

In addition, a simulator often may not cope with some commands, where Formula (<NUM>) is satisfied when the following is defined. <NUM>] <MAT>.

Execution procedure searching using only the actual network (<FIG>) will be described as a target for comparison with the proposed technology. Operations are the same as those in the network settings method, but description will be given using Goal defined in the preceding section.

The control unit <NUM> starts the contact point T0, which is the root in <FIG>, and obtains the command sequence C<NUM> at the contact point T1 from the candidate command generation unit <NUM>, but it is assumed that the following has been returned from the actual network reachability evaluation unit <NUM>. <NUM>] <MAT> It is assumed that the control unit <NUM> does not have a command to proceed from the contact point T1 (the reachable range can be expanded) and returns to the contact point T0.

Next, the control unit <NUM> proceeds to the contact point T2 to obtain the command sequence C<NUM> from the candidate command generation unit <NUM>, but it is assumed that the following has been returned from the actual network reachability evaluation unit <NUM>. <NUM>] <MAT>.

The control unit <NUM> further proceeds to a contact point T4 to obtain a command sequence C<NUM> from the candidate command generation unit <NUM>, but it is assumed that the following has been returned from the actual network reachability evaluation unit <NUM>. <NUM>] <MAT>.

The control unit <NUM> does not have a command to proceed from the contact point T4 and returns to the contact point T2. The control unit <NUM> proceeds to a contact point T3 to obtain a command sequence C<NUM> from the candidate command generation unit <NUM>, and confirms that the policy is satisfied by the following being returned from the actual network reachability evaluation unit <NUM>. <NUM>] <MAT>.

So far, the control unit <NUM> has evaluated the respective reachable ranges through five nodes including the contact point T0. When it is assumed that a period of time taken to evaluate the reachable ranges is <NUM> seconds, it takes <NUM> × <NUM> = <NUM> seconds.

In the proposed technology, an actual network and a simulator are used together. In the present section, execution procedure searching based on the proposed technology, provided that Formula (<NUM>) is satisfied, will be described. <FIG> illustrates a system configuration, and <FIG> is a flowchart illustrating the control unit <NUM>.

An operational policy in the actual network, topology information of the actual network, and setting information of routers constituting the actual network are input to the input unit <NUM> of the execution procedure searching device. For settings, a reachable range is displayed at each node, instead of showing specific contents.

The control unit <NUM> evaluates a reachable range for each of the candidate commands of the candidate command generation unit <NUM> (F1 in <FIG>), and adds a command to a temporary update command sequence <NUM> when the range expands, which is the same as in the network settings method. When the reachable range expands, a new node is created in the search tree.

The control unit <NUM> searches for a setting update command sequence that satisfies the policy in accordance with the flowchart of <FIG>. Starting from a contact point T'<NUM> of the search tree of the simulator, a command C<NUM> (@router B. ) which is given to a branch to a contact point T'<NUM> is executed, and the expansion of the reachable range is confirmed (F1 in <FIG>) to create the contact point T'<NUM>.

Specifically, the control unit <NUM> evaluates a reachable range of the simulator reachability evaluation unit <NUM> (F0 in <FIG>), and acquires the following from the simulator reachability evaluation unit <NUM>. <NUM>] <MAT> Here, there is no executable command, and the control unit returns to the contact point T'<NUM>.

Next, the control unit <NUM> proceeds to a contact point T'<NUM> to obtain a command sequence C<NUM> (@router T. ), and acquires the following from the simulator reachability evaluation unit <NUM>. <NUM>] <MAT>.

The control unit <NUM> further proceeds to a contact point T'<NUM> to obtain a command sequence C<NUM>, and acquires the following that satisfies the policy from the simulator reachability evaluation unit <NUM>. <NUM>] <MAT>.

Here, the control unit <NUM> proceeds to F2 in <FIG>, and executes C<NUM> in the actual network to evaluate a reachable range. However, it can be understood that the policy is not satisfied. That is, the following is acquired from the actual network reachability evaluation unit <NUM>. <NUM>] <MAT>.

The control unit <NUM> follows the contact points T'<NUM> and T'<NUM>, evaluates a reachable range of the command sequence C<NUM> by the simulator reachability evaluation unit <NUM>, and finds that the policy is satisfied by acquiring the following. <NUM>] <MAT>.

Subsequently, the control unit <NUM> executes a command C<NUM> in the actual network and confirms that the policy is satisfied. <NUM>] <MAT> Because a result in F2 in <FIG> is "YES", a temporary update command sequence C<NUM> is output, and the processing ends.

In the search tree of the simulator, a reachable range is evaluated in each of five nodes including the contact point T'<NUM>. On the other hand, in the actual network, a reachable range is only evaluated in two nodes of the contact points T4 and T3. When a period of time for the evaluation of a reachable range in the simulator is set to <NUM> second, the searching can be completed in a total of <NUM> × <NUM> + <NUM> × <NUM> = <NUM> seconds, which is shorter than a time, namely <NUM> seconds, taken by searching using only the actual network.

Note that, as long as Formula (<NUM>) is satisfied, a command sequence that is true in the actual network is also true in the simulator, and thus a command sequence satisfying the policy will not be overlooked.

Proposed Technology: Example where Formula (<NUM>) is not Satisfied In the present section, execution procedure searching where Formula (<NUM>) is not satisfied will be described. In this example, even when it is evaluated that a policy is not satisfied in the simulator, there is a possibility that the policy will be satisfied in the actual network. Consequently, in evaluating a reachable range in the simulator, the reachable range is compared with a reachable range in the actual network with a fixed probability. When the range in the actual network is wider, the searching in the simulator is stopped and switched to searching in the actual network.

A system configuration is the same as that in <FIG> in the previous section. A flowchart of the control unit <NUM> is illustrated in <FIG>. The searching proceeds in the same manner as in the previous section, and it is assumed that the searching has proceeded to the evaluation of a reachable range of a command C<NUM> given to an edge from the contact point T'<NUM> to the contact point T'<NUM>. In step F1 in <FIG>, the reachable range of the command C<NUM> is evaluated using the simulator, but it is assumed that the reachable range has not expanded this time (this is the same as the reachable range in the initial settings).

Then, the processing proceeds to step F3 in <FIG>, and it is stochastically determined whether to perform evaluation in the actual network. For example, when the probability is <NUM>%, a method of generating random numbers of <NUM> to <NUM> and performing evaluation when the random number is <NUM> or less is conceivable. It is assumed that the random number is <NUM> and a reachable range is evaluated in the actual network. Then, as at the contact point T1 in <FIG>, it can be understood that a reachable range expands in the actual network. That is, the simulator cannot correctly evaluate the command C<NUM>, and hereinafter, the node T1 and the subsequent nodes are switched to searching in the actual network.

Specifically, a network settings method is only required to be executed on the actual network by including a temporary update command sequence at that point in time (C<NUM> this time) in the initial settings of the router. Finally, the following is found ("YES" in S05), and a command C<NUM> is output to terminate the processing (S03). <NUM>] <MAT>.

In this manner, although it is stochastic, a command sequence that satisfies the policy can be searched for while avoiding overlooking.

As described above, the present disclosure provides a method for searching for a command sequence to be set for a plurality of devices constituting a system, the method including performing a first step F0 for determining whether a simulator of the system having executed a temporary update command sequence satisfies a predetermined policy, and including executing, until satisfaction for the predetermined policy of the simulator, processing for:.

An execution procedure (setting update command sequence) is searched for, while preventing overlooking as much as possible, in a shorter period of time than that of searching using only an actual system. While examples of an actual network constituted by a plurality of routers and a simulator thereof have been described in the above-described embodiments, the present disclosure can be applied to any system constituted by a plurality of devices and a simulator thereof. Here, the plurality of devices may be a plurality of virtual devices constructed on one physical resource.

When there is an evaluation environment in which a trade-off occurs between accuracy and an execution speed as in an actual network and a simulator, and the simulator has no false negatives, the simulator proceeds with searching first, and the actual network performs a final check, whereby it is possible to reduce a searching time while avoiding overlooking. Even when the simulator has false negatives, evaluation is stochastically performed in the actual network, and thus it is possible to reduce a searching time while avoiding overlooking.

Claim 1:
An execution procedure searching device that searches for a command sequence to be set for a plurality of devices constituting a system, wherein the execution procedure searching device is configured to:
perform a first step for determining whether a simulator of the system having executed a temporary update command sequence (<NUM>) satisfies a predetermined policy, wherein the predetermined policy is defined by a set of three, that is, a packet header, a transmission source router, and a destination router, and wherein the predetermined policy is satisfied when a packet from the transmission source router reaches the destination router, and
execute, until satisfaction for the predetermined policy of the simulator, processing for:
performing a second step for determining whether the simulator approaches a state where the predetermined policy is satisfied, with addition of one new candidate command of one or more new candidate commands to the temporary update command sequence (<NUM>) on condition that the simulator does not satisfy the predetermined policy, wherein the candidate commands are related to the reachability of the packet;
adding the new candidate command to the temporary update command sequence (<NUM>) on condition that the simulator approaches the state where the predetermined policy is satisfied, with the addition of the new candidate command, or
deleting a command at the end of the temporary update command sequence (<NUM>) on condition that the simulator does not approach the state where the predetermined policy is satisfied, with addition of any one of the new candidate commands; and then
returning to the first step, and
perform a third step for determining whether the actual system having executed the temporary update command sequence (<NUM>) satisfies the predetermined policy on condition that the simulator satisfies the predetermined policy, and
execute processing for returning to the second step until satisfaction for the predetermined policy of the actual system, on condition that the actual system does not satisfy the predetermined policy.