DEVICE, METHOD AND PROGRAM FOR GENERATING NETWORK TOPOLOGIES

Abstract

It is an objective of the present disclosure to reduce computational complexity for obtaining a network topology configuration capable of efficiently accommodating a plurality of traffic demands assumed between nodes present in a network.

A device of the present disclosure includes: a computation traffic generation unit that creates a traffic demand matrix whose elements are values individually obtained by demands between nodes present in a target network area from a plurality of traffic demand matrices created based on predicted traffic demands between the nodes; and a network topology generation unit that generates a network topology based on the traffic demand matrix generated by the computation traffic generation unit and port information of the nodes in the network area.

Claims

1. A device comprising: a computation traffic generation unit that creates a traffic demand matrix whose elements are values individually obtained by demands between nodes present in a target network area from a plurality of traffic demand matrices created based on predicted traffic demands between the nodes; and a network topology generation unit that generates a network topology based on the traffic demand matrix generated by the computation traffic generation unit and port information of the nodes in the network area.

2. The device according to claim 1, wherein the network topology generation unit obtains a node with a largest traffic demand for each node present in the target network area by using the traffic demand matrix generated by the computation traffic generation unit, and establishes a link required to accommodate traffic to the obtained node.

3. The device according to claim 1, wherein the network topology generation unit sequentially obtains a pair of nodes with a largest traffic demand from pairs of nodes present in the target network area by using the traffic demand matrix generated by the computation traffic generation unit, and establishes a link required to accommodate traffic of the pair of nodes.

4. A method comprising: creating, by a computation traffic generation unit, a traffic demand matrix whose elements are values individually obtained by demands between nodes present in a target network area from a plurality of traffic demand matrices created based on predicted traffic demands between the nodes; and generating, by a network topology generation unit, a network topology based on the generated traffic demand matrix and port information of the nodes in the network area.

5. A program for causing a computer to perform: a step of creating a traffic demand matrix whose elements are values individually obtained by demands between nodes present in a target network area from a plurality of traffic demand matrices created based on predicted traffic demands between the nodes; and a step of generating a network topology based on the generated traffic demand matrix and port information of the nodes in the network area.

Description

BRIEF DESCRIPTION OF DRAWINGS

[0018] FIG. 1 is an example of a block diagram of the present disclosure.

[0019] FIG. 2 is an example of a network consisting of five nodes that each have ports the number of which is p=4.

[0020] FIG. 3 is an example of a traffic demand matrix.

[0021] FIG. 4 is an example of a set of traffic demand matrices.

[0022] FIG. 5 is a flow diagram showing an example of a first proposed technique according to the present disclosure.

[0023] FIG. 6 is an illustrative diagram of an initial state in a network topology configuration example by the first proposed technique.

[0024] FIG. 7 is an illustrative diagram of steps S11 and S12 in the network topology configuration example by the first proposed technique.

[0025] FIG. 8 is an illustrative diagram of steps S11 and S12 in the network topology configuration example by the first proposed technique.

[0026] FIG. 9 is an example of a network configuration obtained by the first proposed technique.

[0027] FIG. 10 is a flow diagram showing an example of a second proposed technique according to the present disclosure.

[0028] FIG. 11 is an illustrative diagram of an initial state in a network topology configuration example by the second proposed technique.

[0029] FIG. 12 is an illustrative diagram of steps S21 and S22 in the network topology configuration example by the second proposed technique.

[0030] FIG. 13 is an illustrative diagram of steps S21 and S22 in the network topology configuration example by the second proposed technique.

[0031] FIG. 14 is an example of a network configuration obtained by the second proposed technique.

DESCRIPTION OF EMBODIMENTS

[0032] Embodiments of the present disclosure will be described in detail below with reference to the drawings. Note that the present disclosure is not limited to the embodiments illustrated below. These example embodiments are merely illustrative, and the present disclosure can be carried out with various modifications and improvements based on knowledge of those skilled in the art. Note that components with the same reference signs in the description and the drawings mutually indicate the same things.

[0033] FIG. 1 is a block diagram showing a schematic configuration of functions required for determining a network topology configuration in the present embodiment. First, each of these functions will be described. A system of the present embodiment includes a traffic demand matrix prediction unit 11, a computation traffic generation unit 12, a node information storage unit 13, a network topology generation unit 14, and a network topology output unit 15. A device of the present disclosure can also be realized by a computer and a program, and it is also possible that the program is recorded on a recording medium or provided through a network.

[0034] The traffic demand matrix prediction unit 11 is a function of predicting a plurality of traffic demands that can occur between nodes in a target network and generating a set of the traffic demands. Possible examples of the traffic demand matrix prediction unit when designing or operating an actual network are as follows.

[0035] (1) Predicting and generating traffic demand matrices that will occur between nodes in the future at constant time intervals based on logs and data collected from a network traffic monitoring device, previous traffic information and the like.

[0036] (2) Generating a plurality of possible traffic demand matrices from external information (information on the flow of population, events, seasons and the like).

[0037] (3) Modeling characteristics of the target network for network designers or operators and generating a plurality of traffic demand matrices assumed from the model.

[0038] The computation traffic generation unit 12 is a function of generating a traffic demand matrix or a set of traffic demand matrices as input instances for generating a network topology from a set of traffic demand matrices given by the traffic demand matrix prediction unit 11. As an example, to evenly accommodate traffic demands that can occur, an averaged demand at each node is obtained from a plurality of assumed traffic demand matrices, and a network topology is generated based on the averaged demand.

[0039] In addition, to design a topology in consideration of peak values, one traffic demand matrix whose elements are the maximum demands occurring at each node is generated from a plurality of assumed traffic demand matrices, and a network topology is generated based on the traffic demand matrix. Furthermore, it is also possible that a traffic demand matrix indicating average demands between the nodes as discussed above and a traffic matrix whose elements are the maximum demands that can occur between the nodes are both generated to generate a network topology in consideration of variation from these two pieces of information.

[0040] The node information storage unit 13 is a database for holding port information (the number of ports, link capacity and the like) and positional information of each node in the network, each of which is input information to the network topology generation unit 14. The network topology generation unit 14 generates one or more network topologies that can be a solution, from traffic demand matrices generated by the computation traffic generation unit 12 or a set of them. When a plurality of solution candidates are generated, one final network topology configuration is determined by the network topology output unit 15.

[0041] Specific operation examples of functional blocks and calculation examples thereof, proposed by the inventors, are shown below. First, in order to describe the operation examples of the functional blocks and the calculation examples, a model of a network and a traffic demand matrix will be described. Next, formulation of a problem will be performed based on the model, and a technique for quickly obtaining a network topology capable of efficiently accommodating a plurality of assumed traffic demands between nodes will be proposed. The technique proposed here by the inventors adopts a method of calculating (generating by the computation traffic generation unit 12) an average traffic demand occurring between nodes for a given set of traffic demand matrices and establishing (generating by the network topology generation unit 14) links between nodes with higher demands on a priority basis, based on the average traffic demand. As other methods, it is possible to obtain an approximate solution based on meta-heuristics such as simulated annealing or genetic algorithm.

[0042] 1. Modeling of Network and Traffic

[0043] In FIG. 2, an example of models of a network and traffic used in the present disclosure is illustrated. In the present disclosure, a network is represented by a directed graph G=(V,E). The letter V indicates a set consisting of n nodes (V={v.sub.1, v.sub.2, . . . , v.sub.n}, |V|=n), and the letter E indicates a set of links. A link between nodes v.sub.i and v.sub.j is represented by e.sub.ij∈E. In addition, the number of ports of each node is limited and is expressed as p(<∞). In FIG. 2, as an example of a network, an example in which the number of nodes n is 5 and the number of ports of each node is 4 is illustrated. This example is represented as V={v.sub.1, v.sub.2, . . . , v.sub.5}, E={e.sub.12, e.sub.15, . . . , v.sub.54}.

[0044] Furthermore, a band that can be provided by one link is indicated as B, and a link capacity provided between nodes v.sub.i and v.sub.j is expressed as B.sub.ij. For example, when three links are created between nodes v.sub.i and v.sub.j, B.sub.ij=3*B. Thus, the network targeted for the problem is modeled as a degree-constrained valid graph G=(V,E).

[0045] Next, a model of traffic will be described. A traffic demand between nodes v.sub.i and v.sub.j is represented as t.sub.ij, and a n×n traffic demand matrix each element of which is indicated as t.sub.ij is indicated as T={t.sub.ij}.

[0046] Here, a traffic demand to the same node is not considered. That is, for every node v.sub.i∈V, t.sub.ii=0. In addition, a set of m traffic demand matrices that can occur in an assumption scenario or model is expressed as T.sub.s={T.sub.1, T.sub.2, . . . , T.sub.m}, and each element of a traffic demand matrix T.sub.k=∈T.sub.s is represented as t.sup.k.sub.ij. In FIGS. 3 and 4, an example of the traffic demand matrix and the set thereof is illustrated.

[0047] 2. Formulation of Problem

[0048] Based on the models of the network and the traffic demands discussed in chapter 1, a problem (P1) to maximize the accommodation volume of the traffic demand matrix T on the graph G is formulated. Each traffic volume that can pass from a source node v.sub.s to a destination node v.sub.d is represented as f.sub.sd. In addition, the ratio at which each traffic volume from the source node v.sub.s to the destination node v.sub.d passes through a link established between the nodes v.sub.i and v.sub.j is indicated as x.sup.sd.sub.ij. Then, the problem (P1) can be formulated as follows.

[0049] Problem (P1):

[0050] A problem to determine the maximum accommodation volume of the traffic demand matrix T on the graph G

[0051] [Input] [0052] The graph G and the traffic demand matrix T

[0053] [Output] [0054] The maximum accommodation volume of the traffic demand matrix T that can be accommodated on the graph G

[0055] [Objective Function] [0056] Maximizing the sum of traffic volumes Σ.sub.s,df.sub.sd that can pass between nodes v.sub.s and v.sub.d

[0057] [Constraint Condition] [0058] Constraint Condition 1

Σ.sub.s,dx.sub.ij.sup.sdt.sub.sd≤B.sub.ij,∀v.sub.i,v.sub.j∈VL  (1)[Math. 1] [0059] .Math. A constraint under which the traffic volume flowing between nodes v.sub.i and v.sub.j must not exceed the link capacity B.sub.ij provided therebetween [0060] Constraint Condition 2

[00001]$\begin{array}{cc}\left[\mathrm{Math}.2\right]& \\ {.Math.}_{j:e_{\mathrm{ij}}\in E}{x}_{\mathrm{ij}}^{\mathrm{sd}}{t}_{\mathrm{sd}}-{.Math.}_{j:e_{\mathrm{ji}}\in E}{x}_{\mathrm{ji}}^{\mathrm{sd}}{t}_{\mathrm{sd}}=\{\begin{array}{cc}{f}_{\mathrm{sd}},& v_i=s,s\ne d;\\ -f_{\mathrm{sd}},& v_i=d,s\ne d;\\ 0,& v_i\ne s,d;\end{array}& \left(2\right)\end{array}$ [0061] .Math. A constraint regarding flow conservation [0062] Constraint Condition 3

0≤x.sub.ij.sup.sd≤1,∀e.sub.ij∈E,∀s,d␣V  (3)[Math. 3] [0063] .Math. A range of values that can be taken by the variable x.sup.sd.sub.ij [0064] Constraint Condition 4

0≤f.sub.sd≤t.sub.sd,∀s,d∈V  (4)[Math. 4] [0065] .Math. A range of values that can be taken by the variable f.sub.sd

[0066] Next, a problem (P2) to obtain a topology (this is expressed as G.sup.S) capable of evenly accommodating the given set of traffic demand matrices T.sub.s={T.sub.1, T.sub.2, . . . , T.sub.m} is formulated. When the traffic accommodation volume obtained by solving the problem (P1) for the graph G and the traffic demand matrix T is represented as P(G,T), this problem (P2) can be formulated as follows.

[0067] Problem (P2):

[0068] A problem to determine the topology G.sup.S capable of evenly accommodating demand matrices on the traffic demand matrix T

[0069] [Input] [0070] The set of nodes V={v.sub.1, v.sub.2, . . . , v.sub.n} [0071] The set of traffic demand matrices T.sub.s={T.sub.1, T.sub.2, . . . , T.sub.m}

[0072] [Output] [0073] A set of physical links l.sub.ij, i.e., a configuration of the graph G [0074] The physical links l.sub.ij defined below [0075] l.sub.ij=the number of links established between v.sub.i and v.sub.j

[0076] [Objective Function]

[0077] Maximizing the sum of accommodation volumes of individual traffic demand matrices T∈T.sub.s for the set of traffic demand matrices T.sub.s={T.sub.1, T.sub.2, . . . , T.sub.m}

Σ.sub.T∈TsP(G,T)

[0078] [Constraint Condition]

[0079] Since no link is established between the same nodes, the following constraint condition 1 is considered.

[0080] Constraint Condition 1

l.sub.ii=0,∀v.sub.i∈V  (5)[Math. 5]

[0081] In addition, since the number of ports of each node is limited, the following constraint conditions 2 and 3 are considered for the number of links l.sub.ij that can be established between v.sub.i and v.sub.j.

[0082] Constraint Condition 2

0≤l.sub.ij≤p,∀v.sub.i,v.sub.j∈V  (6)[Math. 6]

.Math. A constraint under which the number of links that can be established between all nodes v.sub.i and v.sub.j does not exceed the number of ports p of the nodes.

[0083] Constraint Condition 3

0≤Σ.sub.jl.sub.ij+E.sub.jl.sub.ji≤p,∀v.sub.i∈V  (7)[Math. 7]

[0084] .Math. A constraint for each node v.sub.i under which the sum of the number of links established from v.sub.i to another node v.sub.j and the number of links established from another node v.sub.j to v.sub.i does not exceed the number of ports p of v.sub.i.

[0085] 3. Computational Complexity by Full Search

[0086] In this chapter, the computational complexity required for obtaining the problem formulated in chapter 1 by full search will be described. It can be understood from the constraint conditions 1 and 2 of the problem (P2) that the number of decision variables l.sub.ij and the possible value thereof are n(n−1) and p+1, respectively. Therefore, to list all network topology configurations, a computational complexity of O((p+1).sup.n(n−1)) is required.

[0087] In order to obtain a desired solution, all of these cases are listed, and from them, only those that satisfy the constraint conditions 1 to 3 of the problem (P2) are extracted as solution candidates. Then, an optimal solution can be obtained by calculating P(G,T) for all of the solution candidates. However, obtaining the optimal solution by the full search is unrealistic since the computational complexity exponentially increases with the number of nodes.

[0088] 4. First Proposed Technique

[0089] In this chapter, the details of the technique proposed by the inventors are described, and a computational complexity thereby is analyzed. In addition, it is compared with the computational complexity by the full search discussed in chapter 3 to show that an approximate solution can be obtained quickly.

[0090] First, Average Values

t.sub.ij  (11)[Math. 11]

[0091] of demands occurring between nodes v.sub.i and v.sub.j are calculated based on the given set of traffic demand matrices T.sub.s={T.sub.1, T.sub.2, . . . , T.sub.m}, and a traffic demand matrix having the average values as elements is generated. This is referred to as an average traffic demand matrix, and is represented as follows.

T={t.sub.ij}  (12)[Math. 12]

A sign representing an average may be indicated by “.sup.ave”, and the average traffic demand matrix may be denoted as “T.sup.ave”, for example.

[0092] Here, each of the average values

t.sub.ij  (13)[Math. 13]

[0093] of demands occurring between nodes v.sub.i and v.sub.j can be calculated as follows.

[00002]$\begin{array}{cc}\left[\mathrm{Math}.14\right]& \\ \stackrel{\_}{t_{\mathrm{ij}}}=\frac{1}{.Math.T_s.Math.}{.Math.}_{T^k\in T_s}{t}_{\mathrm{ij}}^k,\forall v_i,v_j\in V& \left(14\right)\end{array}$

[0094] Based on the average traffic demand matrix T.sup.ave obtained by calculating this, the number of links l.sub.ij established between v.sub.i and v.sub.j is obtained in the following procedure shown in FIG. 5.

[0095] In the Following,

┌x┐  (15)[Math. 15]

[0096] represents a ceiling function, and a specific example thereof is blow.

┌1.3┐=2  (16)[Math. 16]

[0097] In addition, P.sub.i represents the number of free ports of the node v.sub.i, and is updated every time a link is established.

[0098] Network configurations (indicated as g.sub.1, g.sub.2, . . . , g.sub.n, respectively) in the case of initially settings of the following processing procedure as v.sub.start=v.sub.i, v.sub.1, . . . , v.sub.n, respectively, are obtained, and from the set of the obtained multiple network configurations

.sup.s  (17)[Math. 17]

a graph that can most efficiently accommodate the average traffic demand matrix T.sup.ave is indicated as follows.

G.sup.S  (18)[Math. 18]

That is as follows.

[00003]$\begin{array}{cc}\left[\mathrm{Math}.19\right]& \\ G^s:=\underset{G\in g^s}{\max }P\left(G,\stackrel{\_}{T}\right)& \left(19\right)\end{array}$

[0099] [Procedure S1]

[0100] Step S10. Initialization: [0101] v.sub.start=v.sub.i [0102] P.sub.i=p [0103] ∀v.sub.i∈V

[0104] Step S11. an unexamined node v.sub.j* with the largest average traffic demand to node v.sub.i and its value

t.sup.max.sub.ij  (21)[Math. 21]

[0105] are obtained.

[0106] Here,

[00004]$\begin{array}{cc}\left[\mathrm{Math}.22\right]& \\ j^{*}=\underset{j}{\mathrm{argmax}}\left(\stackrel{\_}{t_{\mathrm{ij}}}\right);& \left(22\right)\end{array}$$\begin{array}{cc}\left[\mathrm{Math}.23\right]& \\ \stackrel{\_}{t_{{\mathrm{ij}}^{*}}^{\max }}=\underset{j}{\max }\left(\stackrel{\_}{t_{\mathrm{ij}}}\right);& \left(23\right)\end{array}$

[0107] are provided.

[0108] Step S12. Links Required to Accommodate

t.sup.max.sub.ij  (24)[Math. 24]

[0109] are established between the nodes v.sub.i and v.sub.j.

[0110] If it is impossible to establish the required number of links due to limitation on the number of ports, the number of established links is as large as possible. Note that, if it is impossible to perform establishment due to limitation on the number of ports, establishment is not performed.

[00005]$\begin{array}{cc}\mathrm{if}\left(.Math.\frac{t_{{\mathrm{ij}}^{*}}^{\max }}{B}.Math.\le P_i\wedge .Math.\frac{\stackrel{\_}{t_{{\mathrm{ij}}^{*}}^{\max }}}{B}.Math.\le P_{j^{*}}\right):& \left[\mathrm{Math}.25\right]\end{array}$

it is possible to establish the number of links required for accommodating t.sup.max.sub.ij at both of v.sub.i and v.sub.j*

[0111] [Math. 26]

[00006]$l_{{\mathrm{ij}}^{*}}=.Math.\frac{\stackrel{\_}{t_{{\mathrm{ij}}^{*}}^{\max }}}{B}.Math.;$ [0112] P.sub.i=P.sub.i−l.sub.ij*; update the number of free ports of v.sub.i [0113] P.sub.j*−P.sub.j*−l.sub.ij*; update the number of free ports of v.sub.j*

[00007]$\begin{array}{cc}\mathrm{Else}\mathrm{if}\left(.Math.\frac{\stackrel{\_}{t_{{\mathrm{ij}}^{*}}^{\max }}}{B}.Math.>P_i\vee .Math.\frac{\stackrel{\_}{t_{{\mathrm{ij}}^{*}}^{\max }}}{B}.Math.>P_{j^{*}}\right):& \left[\mathrm{Math}.27\right]\end{array}$

it is impossible to establish the number of links required for accommodating t.sup.max.sub.ij at v.sub.i or v.sub.j*

[0114] [Math. 28] [0115] l.sub.ij*=min(P.sub.i, P.sub.j*);//establish links that can be established [0116] P.sub.i=P.sub.i−l.sub.ij*; update the number of free ports of v.sub.i [0117] P.sub.j*=P.sub.j*−l.sub.ij*; update the number of free ports of v.sub.j*

[0118] Step S13. The above processing terminates when the processing is performed for all traffic demands

t.sub.ij  (29)[Math. 29]

or when there is no free port of each node, and the following step S14 is performed. Otherwise, v.sub.i is replaced with v.sub.i+1 (when i+1>n, v.sub.i is replaced with v.sub.1), and the processing returns to step S11.

[0119] Step S14. If there are two or more nodes whose number of free ports P.sub.i is greater than or equal to 1, links are established between those nodes in the order from the highest demand. This operation is performed until the number of nodes is less than or equal to 1.

[0120] Since the steps from S11 to S14 are repeated n.sup.2−n times at the maximum and these are performed for each case of v.sub.start=v.sub.1, v.sub.2, . . . , v.sub.n, it is easy to understand that the computational complexity is O(n.sup.3). Thus, it can be understood that it is possible to obtain an approximate solution in a very short time as compared to the computational complexity O((p+1).sup.n(n−1)) required in the case of performing full search.

[0121] In FIGS. 6 to 9, examples of this procedure and network topology configurations obtained thereby are illustrated.

[0122] Step S10: as shown in FIG. 6, v.sub.start=v.sub.1, P.sub.i=4, ∀v.sub.i∈V.

[0123] Step S11: from the table in FIG. 6, node v.sub.j* with the largest average traffic demand to node v.sub.1 is v.sub.4, and its value (t.sub.1.sup.max).sup.ave is 2.77.

[0124] Step S12: as shown in FIG. 7, links required to accommodate (t.sub.1.sup.max).sup.ave=2.77 are established between nodes v.sub.1 and v.sub.4. In the present embodiment, since l.sub.ij=|2.77/1.0|=3 and there are free ports at both of v.sub.i and v.sub.4, l.sub.14=3. In addition, at each of the nodes, the number of free ports is updated.

[0125] Step S13: v.sub.s is set to v.sub.2, and the processing returns to step S10.

[0126] Step S11: from the table in FIG. 6, node v.sub.j* with the largest average traffic demand to node v.sub.2 is v.sub.1, and its value (t.sub.1.sup.max).sup.ave=1.01.

[0127] Step S12: as shown in FIG. 8, links required to accommodate (t.sub.2.sup.max).sup.ave=1.01 are established between nodes v.sub.2 and v.sub.1. In the present embodiment, since l.sub.ij=|1.01/1.0|=2, the number of free ports at v.sub.1 is 1, and thus setting is made such that l.sub.<=1. In addition, at each of the nodes, the number of free ports is updated. Step S14 is performed when links are established for the traffic demands of all nodes or when there is no free port to which a link with a traffic demand can be established.

[0128] By repeating these procedures, a network configuration as in FIG. 9 is finally obtained.

[0129] 5. Second Proposed Technique

[0130] As another method for obtaining the network topology G.sup.S, a method of sequentially selecting the maximum element of all elements of the average traffic demand matrix T.sup.ave and greedily establishing links in consideration of limitation on the number of ports is proposed. The following procedure S2 shown in FIG. 10 shows a link establishment method by this method. In addition, an example of this procedure and network topology configurations obtained by this example are illustrated in FIGS. 11 to 14.

[0131] In this case, since the number of elements of the average traffic demand matrix T.sup.ave is n.sup.2, the computational complexity is O(n.sup.2), and it is possible to obtain an approximate solution with a very low computational complexity even in such a method.

[0132] [Procedure S2]

[0133] Step S20. Initialization: [0134] P.sub.i=p [0135] ∀v.sub.i∈V

[0136] In the example of FIG. 11, P.sub.i=4, ∀v.sub.i∈V.

[0137] Step S21. A pair of nodes v.sub.i* and v.sub.j* with the largest traffic demand and its value

t.sup.max.sub.i*j*  (31)[Math. 31]

are obtained.

[0138] Here,

[00008]$\begin{array}{cc}\left[\mathrm{Math}.32\right]& \\ v_{i^{*}},v_{j^{*}}=\underset{i,j}{\mathrm{argmax}}\left(\stackrel{\_}{t_{\mathrm{ij}}}\right);\stackrel{\_}{t_{i^{*}{j}^{*}}^{\max }}=\underset{i,j}{\max }\left(\stackrel{\_}{t_{\mathrm{ij}}}\right);& \left(32\right)\end{array}$

are provided.

[0139] Step S22. Links Required to Accommodate

t.sup.max.sub.i*j*  (33)[Math. 33]

are established between nodes v.sub.i* and v.sub.j*.

[0140] If it is impossible to establish the required number of links due to limitation on the number of ports, the number of established links is as large as possible. If it is impossible to perform establishment due to limitation on the number of ports, it is not performed.

[00009]$\begin{array}{cc}\mathrm{if}\left(.Math.\frac{\stackrel{\_}{t_{i^{*}{j}^{*}}^{\max }}}{B}.Math.\le P_{i^{*}}\wedge .Math.\frac{\stackrel{\_}{t_{i^{*}{j}^{*}}^{\max }}}{B}.Math.\le P_{j^{*}}\right):& \left[\mathrm{Math}.34\right]\end{array}$

it is possible to establish the number of links required for accommodating t.sup.max.sub.i*j* at both of v.sub.i* and v.sub.j*

[00010]$l_{i^{*}{j}^{*}}=.Math.\frac{\stackrel{\_}{t_{i^{*}{j}^{*}}^{\max }}}{B}.Math.;$ [0141] p.sub.i*=P.sub.i*−l.sub.i*j*; update the number of free ports of v.sub.i [0142] P.sub.j*=P.sub.j*−l.sub.i*j*; update the number of free ports of v.sub.j*

[00011]$\begin{array}{cc}\mathrm{Else}\mathrm{if}\left(.Math.\frac{\stackrel{\_}{t_{i^{*}{j}^{*}}^{\max }}}{B}.Math.>P_{i^{*}}\vee .Math.\frac{\stackrel{\_}{t_{i^{*}{j}^{*}}^{\max }}}{B}.Math.>P_{j^{*}}\right):& \left[\mathrm{Math}.35\right]\end{array}$ [0143] l.sub.i*j*=min(P.sub.i*, P.sub.j*); H establish as possible [0144] P.sub.i*=P.sub.i*−l.sub.i*j*; update the number of free ports of v.sub.i* [0145] P.sub.j*=P.sub.j*−l.sub.i*j*; update the number of free ports of v.sub.j*

[0146] In the examples of FIGS. 11 to 14, steps S21 and S22 are performed as follows.

[0147] Step S21: v.sub.i*=v.sub.1, v.sub.j*=4, and its value (t.sub.i*j*.sup.max).sup.ave is 2.77.

[0148] Step S22: links required to accommodate (t.sub.l*j*.sup.max).sup.ave=2.77 are established between nodes v.sub.1 and v.sub.4. In the example of FIG. 11, since l.sub.i*j*=|2.77/1.0|=3 and there are free ports at both of v.sub.i and v.sub.4, l.sub.14=3 as shown in FIG. 12. In addition, at each of the nodes, the number of free ports is updated.

[0149] Step S21: Excluding the average traffic demand or demands previously examined, a pair of nodes with the largest average traffic demand and its value (t.sub.i*j*.sup.max).sup.ave are obtained. As shown in FIG. 13, v.sub.i*=v.sub.5, v.sub.j*=2, and its value (t.sub.i*j*.sup.max).sup.ave is 2.17.

[0150] Step S22: links required to accommodate (t.sub.l*j*.sup.max).sup.ave=2.17 are established between nodes v.sub.5 and v.sub.2. In the example of FIG. 11, since l.sub.i*j*=|2.17/1.0|=3 and there are free ports at both of v.sub.2 and v.sub.5, l.sub.52=3 as shown in FIG. 13. In addition, at each of the nodes, the number of free ports is updated.

[0151] These steps S21 and S22 are repeatedly performed in consideration of the constraint on the number of ports. Steps S21 and S22 terminate when links are established for the traffic demands of all nodes or when there is no free port to which a link with a traffic demand can be established.

[0152] Step S23. It is determined that steps S21 and S22 are performed for all traffic demands

t.sub.ij  (38)[Math. 38]

[0153] and that there is no free port at each node. When either of these is satisfied, the following step S24 is performed.

[0154] Step S24. If there are two or more nodes whose number of free ports P.sub.i is greater than or equal to 1, links are established between those nodes in the order from the highest demand. This operation is performed until the number of nodes is less than or equal to 1.

[0155] 6. Effects Obtained by the Present Disclosure

[0156] The present disclosure makes it possible for a network designer to, based on a set of traffic demand matrices that can occur in a scenario or a model according to a communication service assumed in the future, quickly obtain an approximate solution of a network topology configuration capable of evenly accommodating them. Note that, although a traffic demand matrix whose elements are average values individually occurring between nodes is created in the computation traffic generation unit 12 in the present embodiment, the traffic demand matrix of the present disclosure can adopt any values individually obtained by demands between nodes as elements.

[0157] 7. Points of the Present Disclosure

[0158] In the present disclosure, a method for quickly and approximately calculating a network topology configuration capable of efficiently accommodating a plurality of possible traffic demands between nodes is proposed. First, this problem is formulated as a degree-constrained network design problem, and it is shown that it is difficult to obtain an optimal solution by full search. Thus, two methods of calculating an average or the like of traffic demands individually occurring between nodes for a given set of traffic demand matrices and establishing links between nodes with larger demands on a priority basis based on the traffic demands are proposed. Furthermore, it is shown that the respective computational complexities of these proposed techniques are O(n.sup.3) and O(n.sup.2). Since the computational complexities required by these proposed techniques are much smaller than the computational complexity O((p+1).sup.n(n−1)) required by full search, it is possible to quickly obtain an approximate solution of a topology configuration capable of efficiently accommodating a plurality of assumed traffic demands.

INDUSTRIAL APPLICABILITY

[0159] The present disclosure can be applied to the information and communication industry.

REFERENCE SIGNS LIST

[0160] 11: Traffic demand matrix prediction unit [0161] 12: Computation traffic generation unit [0162] 13: Node information storage unit [0163] 14: Network topology generation unit [0164] 15: Network topology output unit