JP5876860B2 - Network design apparatus and method - Google Patents

Description

  The present invention relates to a network design apparatus and method, and more particularly, to a network design apparatus and method for designing a physical medium network that is robust against an area disaster.

  Up to now, network reliability has been ensured by taking measures so that the probability of connection between certain nodes becomes a certain value or more, mainly on the premise of failure occurring independently. However, the loss of network functions due to a face-to-face disaster is far from the premise of an independent failure, so such reliability measures are insufficient. In reliability engineering, there are attempts to upgrade existing theories based on the concept of correlated failures, but it cannot be considered that failures can occur due to geographical concepts such as area damage.

  On the other hand, an algorithm for obtaining a connection probability between two nodes when a damaged area occurs on a straight line by integral geometry is shown (for example, see Non-Patent Document 1).

S. Neumayer and E. Modiano, Network Reliability With Geographically Correlated Failures, INFOCOM 2010.

However, in the technique of Non-Patent Document 1 described above,
(1) It is not just damage on a straight line, it is not a surface damage consistent with earthquakes and tsunamis;
(2) Not a design method;
There is a problem.

  The present invention has been made in view of the above points, and a network design apparatus and method capable of designing a path of a physical medium based on a model corresponding to an area disaster when the network function is lost due to the area disaster. The purpose is to provide.

According to one aspect, a network design device capable of responding to an area disaster,
Evaluation method of probability of connection between node O and node k on the network (hereinafter referred to as “connection probability”) and physical medium route candidate including line bundle partial route candidate and individual line partial route candidate are input. A connection probability maximizing means for obtaining the worst value of the connection probabilities of the node O and the node k on the network or the sum of the connection probabilities and storing them in the storage means together with the route candidates in the event of a disaster ,
There is provided a network design device comprising route selection means for selecting, from the route candidates in the storage means, a route having a maximum worst connection probability or a sum having the maximum connection probability.

  According to one aspect, in the network design for determining the physical medium path, the connection probability between the root node O and each of the other nodes k is the worst among the candidate paths based on the model corresponding to the area disaster. It is possible to design a network that optimizes the connection probability between O and k.

It is an example of a structure of the network design apparatus in one embodiment of this invention. It is a disaster area model. It is an example of the line bundle in one embodiment of the present invention. It is an example of a line bundle path candidate and an individual line partial path candidate in an embodiment of the present invention. It is a flowchart of operation | movement of the network design apparatus in one embodiment of this invention.

  Hereinafter, embodiments of the present invention will be described with reference to the drawings.

  FIG. 1 shows the configuration of a network design apparatus according to an embodiment of the present invention.

  The network design device 100 shown in FIG. 1 includes an input unit 110, a connection probability maximization processing unit 120, a route / connection probability storage unit 130, a route selection unit 140, and an output unit 150.

  Before explaining each of the above configurations, the theory behind this is presented. For a certain plane figure X, | X |

をXのconvex hull（与えられた集合を含む最小の凸集合）とする。

Let X be a convex hull of X (the smallest convex set containing the given set).

It is assumed that there is a physical medium network such as an optical fiber cable in A ₀ in the convex area, and there is a path p (i, j) between two nodes i and j in the network, and a disaster occurs here. It is assumed that all network parts included in the disaster area are broken. A disaster area model is shown in FIG. It is assumed that the disaster area boundary is included in a belt-like region B having a width w. The affected area is approximated by a half-plane which is the union of the band-like region B and the half-plane R _B. Affected areas and on a plane including A _0, occurs at random, including angle.

  At this time, Formula (1) is obtained by analysis of integral geometry.

但し、

However,

は、i，j間が接続可能であることを示す。式（1）は、被災エリアがA₀に掛かる条件下で、i，jが接続可能である確率を与えている。そこで、ルートノードOとその他の各ノードｋ間のこの確率を最大化するネットワークを設計することにする。

Indicates that i and j can be connected. Equation (1) gives the probability that i and j can be connected under the condition that the affected area is A ₀ . Therefore, a network that maximizes this probability between the root node O and each other node k is designed.

  From equation (1), this probability is maximized by the outer perimeter of the convex hull of the O-k path.

を最小化すればよいことがわかる。そこで、本発明では、各kについて、O−k間経路のconvex hullの外周長を最小化するネットワークを設計することにする。

It can be seen that it is sufficient to minimize. Therefore, in the present invention, for each k, a network that minimizes the outer perimeter of the convex hull of the O-k path is designed.

  In addition,

の代わりに、ルートノードOとその他の各ノードk間の接続確率をそのまま使ってもよい。

Instead of this, the connection probability between the root node O and each other node k may be used as it is.

  In the input unit 110 of FIG. 1, as a parameter, a line bundle path candidate, a physical medium path candidate including a formulated individual line path candidate, and a connection probability between the nodes i and j as a probability evaluation method are set. The required expression (1) is input.

  As shown in FIG. 3, the physical medium is composed of a line bundle part a and an individual line part b. Although the two-stage configuration is used for simplicity, the present invention can be similarly applied to a multi-stage configuration. As shown in FIG. 4, there are 1 to n channel bundle route candidates (hereinafter referred to as “line bundle partial route candidates”) obtained in consideration of conditions such as cost by the existing method. Let S (i, k) be the individual line partial path candidate set for the individual line k (line for the node k) obtained for the route candidate i in consideration of conditions such as cost by the existing method.

  For each individual line partial path candidate k, the connection probability maximization processing unit 120 first fixes a certain line bundle partial path candidate i, and for each path of the individual line partial path candidate set S (i, k), O Perimeter length of convex hull of path between k

を評価し、その最小値をf(i,k)とし、その時の経路をr(i,k)とし、当該最小値とr(i,k)を経路・接続確率記憶部１３０に格納する。

The minimum value is set to f (i, k), the path at that time is set to r (i, k), and the minimum value and r (i, k) are stored in the path / connection probability storage unit 130.

  Since the route selection for the individual line partial path candidate does not affect other individual lines, r (i, k) should be adopted when the line bundle partial path candidate i is adopted.

  The route selection unit 140 selects, from the route / connection probability storage unit 130, the route with the minimum max_k f (i, k) for the line bundle partial route candidates 1 to n. Here, max_k f (i, k) is determined for the worst node k when the line bundle partial path candidate i is adopted.

であるので、これが最小となるよう経路選択を行うものである。なお、max_k f(i,k)の代わりに、f(i,k)の和を最大化する

Therefore, route selection is performed so that this is minimized. Note that instead of max_k f (i, k), the sum of f (i, k) is maximized.

を用いることもできる。

Can also be used.

  The output unit 150 outputs the route selected by the route selection unit 140.

  FIG. 5 is a flowchart of the operation of the network design apparatus according to the embodiment of the present invention.

  When the formulated line bundle route candidate and individual line route candidate are input, the input unit 110 passes them to the connection probability maximization processing unit 120 (step 101).

  The connection probability maximization processing unit 120 initializes the processing target counter i of the line bundle partial path candidate to be processed and the processing target counter k of the individual line partial path candidate to be processed to 1 (steps 102 and 103).

  The connection probability maximization processing unit 120 is configured as described above.

を評価し、その最小値f(i,k)と、その時の経路r(i,k)を経路・接続確率記憶部１３０に格納する（ステップ１０４）。

And the minimum value f (i, k) and the route r (i, k) at that time are stored in the route / connection probability storage unit 130 (step 104).

  If the process of step 104 is performed for all individual line partial path candidates k (step 105, Yes), the process proceeds to step 107, and if there is an unprocessed individual line partial path candidate k (step 105, No) ), The value of k is set to k = k + 1 (step 106), and the process returns to step 104.

  When the processing for all line bundle partial route candidates i is completed (step 107, Yes), the process proceeds to step 109, and when there is an unprocessed line bundle partial route candidate i (step 107, No). , I is set to i = i + 1 (step 108), and the process returns to step 103.

  The route selection unit 140 selects the route i having the worst maximum value max_k f (i, k) from the route / connection probability storage unit 130, names the route i_opt, and the route i_opt and the route / connection probability. The route / connection probability storage unit stores the individual line partial route candidate r (i_opt, k) (k = 1, 2,...) Where i = i_opt in the route r (i, k) held in the storage unit 130. It is stored in 130 (step 109).

  The output unit 150 reads i_opt and r (i_opt, k) from the path / connection probability storage unit 130 and outputs them (step 110).

  It is also possible to select a route that minimizes the outer perimeter of the convex hull of the route between the root node O and each other node k. When minimizing the outer perimeter of the convex hull of the route between O and k, the outer perimeter of the convex hull of the route is stored in the route / connection probability storage unit 130 for all individual line partial route candidates and all line bundle partial route candidates. The connection probability maximization processing unit 120 minimizes the maximum value of the outer circumference of the convex hull of the route.

  The operation of each component of the network design apparatus shown in FIG. 1 can be constructed as a program, installed in a computer used as the network design apparatus and executed, or distributed via a network. is there.

100 Network Design Device 110 Input Unit 120 Connection Probability Maximization Processing Unit 130 Route / Connection Probability Storage Unit 140 Route Selection Unit 150 Output Unit

Claims (4)

A plurality of line bundle portions that are route candidates for the line bundle portion in a network including a line bundle portion connected to the node O and a plurality of individual line portions bundled in the line bundle portion and connected to a plurality of nodes k. An input unit that receives input of a plurality of individual line partial route candidates that are route candidates related to the individual line portion for each of the route candidates and the line bundle partial route candidates and for each node k;
For each line bundle partial path candidate and for each node k, the connection probability regarding the line bundle partial path candidate and a plurality of individual line partial path candidates for the node k is evaluated, and the minimum value of the connection probability is specified. A connection probability maximization unit to
Of the plurality of line bundle partial path candidates, the line bundle having the smallest maximum value among the minimum values evaluated for each node k or the sum of the minimum values evaluated for each node k. A route selector for selecting partial route candidates;
A network design apparatus comprising: A plurality of line bundle portions that are route candidates for the line bundle portion in a network including a line bundle portion connected to the node O and a plurality of individual line portions bundled in the line bundle portion and connected to a plurality of nodes k. An input unit that receives input of a plurality of individual line partial route candidates that are route candidates related to the individual line portion for each of the route candidates and the line bundle partial route candidates and for each node k;
For each line bundle partial path candidate and for each node k, the circumference length of the convex set relating to the line bundle partial path candidate and a plurality of individual line partial path candidates related to the node k is evaluated, and the minimum of the outer circumference length is evaluated. A connection probability maximization unit that identifies a value;
Of the plurality of line bundle partial path candidates, the line bundle having the smallest maximum value among the minimum values evaluated for each node k or the sum of the minimum values evaluated for each node k. A route selector for selecting partial route candidates;
A network design apparatus comprising: A plurality of line bundle portions that are route candidates for the line bundle portion in a network including a line bundle portion connected to the node O and a plurality of individual line portions bundled in the line bundle portion and connected to a plurality of nodes k. An input procedure for receiving input of a plurality of individual line partial route candidates that are route candidates related to the individual line part for each route candidate and each line bundle partial route candidate and for each node k;
For each line bundle partial path candidate and for each node k, the connection probability regarding the line bundle partial path candidate and a plurality of individual line partial path candidates for the node k is evaluated, and the minimum value of the connection probability is specified. Connection probability maximization procedure, and)
Of the plurality of line bundle partial path candidates, the line bundle having the smallest maximum value among the minimum values evaluated for each node k or the sum of the minimum values evaluated for each node k. A route selection procedure for selecting partial route candidates;
A network design method characterized in that a computer executes . A plurality of line bundle portions that are route candidates for the line bundle portion in a network including a line bundle portion connected to the node O and a plurality of individual line portions bundled in the line bundle portion and connected to a plurality of nodes k. An input procedure for receiving input of a plurality of individual line partial route candidates that are route candidates related to the individual line part for each route candidate and each line bundle partial route candidate and for each node k;
For each line bundle partial path candidate and for each node k, the circumference length of the convex set relating to the line bundle partial path candidate and a plurality of individual line partial path candidates related to the node k is evaluated, and the minimum of the outer circumference length is evaluated. A connection probability maximization procedure to identify the value;
Of the plurality of line bundle partial path candidates, the line bundle having the smallest maximum value among the minimum values evaluated for each node k or the sum of the minimum values evaluated for each node k. A route selection procedure for selecting partial route candidates;
A network design method characterized in that a computer executes .

Images