JP5159811B2 - Band calculation method and band calculation device - Google Patents

Description

  The present invention relates to a bandwidth calculation method and a bandwidth calculation device. More specifically, the present invention relates to a bandwidth calculation method and a bandwidth calculation device for calculating a bandwidth upper limit value of a communication link necessary for a detour path selected at the time of failure.

  In the communication link, a detour path is set with respect to the working path in order to improve fault tolerance. The following methods are being studied as a method of calculating the bandwidth required for the detour path.

  There is a method called Network-Tomography for estimating AC traffic between a source / destination (SD) pair from information on traffic flowing through a communication link (see Non-Patent Document 1). It is also possible to obtain the bandwidth required for the detour path from the AC traffic estimated by this Network-Tomography. However, in Network-Tomography, AC traffic is assumed to be Poisson distribution or normal distribution, and the average value is calculated using the maximum likelihood method, etc., which guarantees the upper bandwidth limit necessary for the detour path. There is a problem that is not.

  In order to solve the above problems, the bandwidth calculation that maximizes the bandwidth required for the detour path that flows through the communication link by incorporating the observation data of the traffic flowing through the communication link and the inflow / outflow traffic at the end point node into the constraint equation. A method has already been proposed (see Patent Document 1).

A. Medina et al. "Traffic Matrix Estimation: Existing Techniques and New Directions," Proceedings of the 2002 SIGCOMM conference, 2002.

Japanese Patent Application No. 2009-49110 “Communication Bandwidth Calculation Method and Device” Ryutaro Matsumura, Masayuki Kanno, Motoi Iwashita

  As described above, in Patent Document 1, the traffic between SD pairs is not known, but when the traffic flowing through the communication link is observed, the upper limit value of the bandwidth in the communication link necessary for the detour path is calculated. Can do. However, in Patent Document 1, it is necessary to solve the maximization problem on the assumption that a failure has occurred for all communication links. For this reason, there is a problem that the amount of calculation increases as the size of the network increases. In particular, it takes time to solve a large-scale network.

  Accordingly, an object of the present invention is to provide a bandwidth calculation method and a bandwidth calculation device that can reduce the amount of calculation when calculating the bandwidth required for a detour path.

In order to solve the above problem, the bandwidth calculation method of the present invention is:
A bandwidth calculation method in a bandwidth calculation device for calculating a bandwidth upper limit value of a communication link required in a bypass path when a failure occurs on a communication network in which a working path and a bypass path are set,
Obtaining the amount of traffic flowing through the communication link;
Selecting a first communication link that assumes a failure on the working path;
A bandwidth upper limit value required for the second communication link of the detour path when a failure occurs in the first communication link is determined as a maximum value of a function using the traffic amount as a constraint condition by a linear programming method. A calculating step;
Repeating the selecting step and the calculating step;
Have
In the calculating step, a bandwidth upper limit value is calculated by adding a constraint that the function exceeds a calculation result that has already been calculated.

Moreover, the bandwidth calculation apparatus of the present invention is
A bandwidth calculation device that calculates a bandwidth upper limit value of a communication link required for a detour path when a failure occurs on a communication network in which a working path and a detour path are set,
A traffic acquisition unit for acquiring the amount of traffic flowing through the communication link;
A path information storage unit for storing information on the working path and the detour path;
Necessary for the second communication link of the detour path when a failure occurs in the first communication link by selecting the first communication link assuming the occurrence of the failure on the working path from the path information storage unit. A bandwidth calculation unit that calculates a bandwidth upper limit value as a maximum value of a function that uses the traffic amount as a constraint condition by a linear programming method;
Have
The band calculating unit re-selects the first communication link and calculates a band upper limit value by adding a constraint that the function exceeds a calculation result already calculated.

  According to the embodiment of the present invention, it is possible to reduce the amount of calculation when calculating the bandwidth necessary for the detour path.

The figure which shows the communication network which concerns on the Example of this invention The figure which shows the communication system which concerns on the Example of this invention. Conceptual diagram of bandwidth calculation method using bandwidth lower limit

  Embodiments of the present invention will be described below with reference to the drawings.

  FIG. 1 is a diagram illustrating a communication network according to an embodiment of the present invention. The communication network includes a plurality of nodes A to D and communication links 1 to 4 that connect the nodes. In the communication network, there are one or more pairs of source nodes and destination nodes (SD pairs: Source-Destination pairs). In FIG. 1, node A is a source node and node C is a destination node. Although not shown, other SD pairs may also exist. It is assumed that a working path and a detour path are set in advance between the SD pairs. The working path is a path that is used during normal times when no failure occurs, and the detour path is a path that is used when a failure occurs on the working path. Note that the bandwidth of the detour path can be shared by a plurality of working paths. In FIG. 1, working paths are set for the communication links 1 and 2, and detour paths are set for the communication links 3 and 4.

  When a failure occurs in the communication link 1 for which the working path is set, the traffic between the SD pairs flows to the detour path. In this case, if the bandwidth necessary for the detour path is not set in advance, the communication quality is degraded. Therefore, in the present invention, the amount of traffic flowing through the communication link on the communication network when no failure occurs is observed, and the bandwidth required for the specific communication link of the detour path is determined from the observed traffic amount. Calculate the upper limit. Here, a communication link for calculating a bandwidth upper limit value necessary for a detour path is referred to as a “design target link”. Assume that failures occur on a single communication link at the same time.

  In order to calculate this bandwidth upper limit value, it is assumed that a failure has occurred in the communication link through the working path corresponding to the detour path set in the design target link, and the effect on the design target link at that time think of. Here, a communication link that assumes the occurrence of a failure is referred to as a “failure assumed link”. The problem of calculating the bandwidth upper limit value required for the design target link by the detour path due to the failure of the assumed failure link can be formulated as a maximization problem. By calculating the maximization problem by the linear programming method for all the failure assumption links, the bandwidth upper limit value of the design target link is calculated.

  For example, in FIG. 1, assuming that a failure has occurred in the communication link 1 (failure assumed link), the bandwidth upper limit value required for the detour path in the communication link 4 (design target link) is calculated. Note that when the failure occurs in the communication link 1 and when the failure occurs in the communication link 2, the bandwidth upper limit value required for the detour path differs in the communication link 4. As the assumed link, it is necessary to calculate a bandwidth upper limit value necessary for the detour path in the design target link. In the embodiment of the present invention, the bandwidth upper limit value when a failure occurs in the communication link 2 is calculated for a value that exceeds the calculation result already calculated in the communication link 1. In this way, the amount of calculation is reduced by adding a constraint that the objective function for obtaining the band upper limit value by the linear programming method exceeds the already calculated result.

<Configuration of communication system>
FIG. 2 is a diagram illustrating a communication system according to an embodiment of the present invention. The communication system according to the embodiment of the present invention includes a communication network as shown in FIG. 1, an operation system 10, a bandwidth calculation device 20, and a bandwidth display device 30.

  The operation system 10 is a device that manages and manages nodes and communication links on a communication network. The operation system 10 includes a network data collection unit 101 as a functional unit and a network information database 111 as a database.

  The network data collection unit 101 collects the traffic amount flowing through the communication link connected to the node on the communication network managed by the operation system 10 and accumulates it in the network information database 111 as traffic information. Information regarding the working path and the detour path set by the operator of the communication network is stored in the network information database 111 as path information.

  The bandwidth calculation device 20 is connected to the operation system 10, acquires traffic information and path information from the operation system 10, and calculates a bandwidth required for the design target link of the detour path using the acquired data. The bandwidth calculation device 20 receives a request from the bandwidth calculation device 20 that is directly operated by the operator or designer of the communication network, and transmits information about the calculated necessary bandwidth to the bandwidth display device 30.

  The bandwidth calculation device 20 includes a data acquisition unit 201 and a bandwidth calculation unit 202 as functional units, and includes a path information database 211 and a traffic information database 212 as databases.

  The data acquisition unit 201 acquires path information and traffic information as information necessary for bandwidth calculation among the information managed by the operation system 10 in the network information database 111, and the path information database 211 and the traffic information database 212, respectively. To accumulate.

  The bandwidth calculation unit 202 uses the path information and traffic information stored in the path information database 211 and the traffic information database 212 to calculate a bandwidth upper limit value and a bandwidth upper limit value required for the design target link of the detour path. A bandwidth calculation algorithm for calculating the bandwidth upper limit will be described later.

  The bandwidth display device 30 is connected to the bandwidth calculation device 20 and displays the calculated bandwidth upper limit value.

  The band display device 30 includes a band display unit 301 as a functional unit.

  The bandwidth display unit 301 accepts an operation by the operator or designer of the communication network, performs an acquisition request for the bandwidth upper limit value calculated for the design target link to the bandwidth calculation device 20, and obtains it from the bandwidth calculation device 20. Display the value.

<Bandwidth calculation algorithm>
Next, a band calculation algorithm used in the band calculation unit 202 will be described.

  A target communication network is a directed graph G = {N, E}. Here, N and E are a set of nodes and communication links belonging to the communication network, respectively.

_Let F _ij ≧ 0 be the traffic volume from node i to node j.

The route of the working path between nodes i and j is indicated by r _ij ^e ε {0,1}. Specifically, r _ij ^e = 1 when the working path between the nodes i and j passes through the link e, and r _ij ^e = 0 when the working path does not pass through the link e. The path of the working path is stored in the path information database 211.

によってノードi及びj間の迂回用パスの経路を示す。具体的には、リンクf（障害想定リンク）が故障したときにノードi及びj間の迂回用パスがリンクe（設計対象リンク）を通る場合、

Indicates the path of the detour path between nodes i and j. Specifically, when link f (failure link) fails and the detour path between nodes i and j passes through link e (design target link),

とし、通らない場合、

And if it does not pass,

とする。なお、迂回用パスの経路は、パス情報データベース２１１に格納される。

And The path of the detour path is stored in the path information database 211.

Traf (e) indicates the observed traffic on link e. The ext ⁱⁿ (i) indicates the observed value of traffic flowing into node i. By ext ^out (j), the observed value of traffic flowing out from node j is shown. These traffic observation values are stored in the traffic information database 212.

  An equation for obtaining the bandwidth of the detour path required in the communication link e when the communication link f fails by linear programming is expressed by the following equation (1).

すなわち、次の目的関数

That is, the objective function

の最大値が、リンクfが故障した場合の迂回用パスのリンクeで必要となる帯域上限値を表す。また、式(2)〜式(5)は、式(1)を算出するときの制約式である。

Represents the upper limit value of the bandwidth required for the link e of the detour path when the link f fails. Equations (2) to (5) are constraint equations for calculating Equation (1).

  Therefore, in order to calculate the bandwidth upper limit value required for the link e of the detour path, it is necessary to calculate Equation (1) to Equation (5) for all possible failure links f and to calculate the maximum value. is there. However, it takes time to simply calculate linear programming repeatedly. In the embodiment of the present invention, as described below, a band calculation method using a band lower limit value is used.

<Band calculation method using band lower limit value>
Equations (1) to (5) are solved for a specific failure assumption link f ′, and the result is set as a lower limit band c (e) for another failure assumption link f. In this case, the following constraint equation (6) is added to equations (1) to (5).

これは、線形計画化法によって帯域上限値を求めるための目的関数が、既に求解を終えている最大化問題の最大値を上回ることを制約条件に加えることに相当する。既に求解を終えている最大化問題の最大値を超えられない場合には、実行可能解が得られず、算出結果が無駄になる。従って、既に目的関数で算出された算出結果を上回る値を対象として算出することにより、計算量を削減することができる。

This corresponds to adding to the constraint that the objective function for obtaining the upper limit value of the band by the linear programming method exceeds the maximum value of the maximization problem that has already been solved. If the maximum value of the maximization problem that has already been solved cannot be exceeded, an executable solution cannot be obtained and the calculation result is wasted. Therefore, the calculation amount can be reduced by calculating a value exceeding the calculation result already calculated by the objective function.

  Expressions (1) to (6) are repeatedly calculated, and the band lower limit value c (e) is set from the result, thereby restricting the constraint condition of expression (6).

  The failure assumption link f ′ may be selected at random, but the value of the objective function, that is, the bandwidth of the detour path, is better to solve the linear programming assuming that the link having a large failure effect has failed. It is considered that the upper limit value is increased. For example, if the failure assumption link f ′ is selected and calculated in order from the link having the largest communication traffic traf (e) as a heuristic technique, the amount of calculation can be further reduced and the calculation speed can be expected to increase.

  A band calculation method using the above band lower limit value will be described with reference to FIG. FIG. 3 shows a communication network composed of 6 nodes A, B, C, D, E and F. It is assumed that the working path EDCB and the detour path EAB are set between the transmission source node E and the destination node B. The working path EDCB is switched to the detour path EAB when a failure occurs.

  The communication link e between the nodes A and B is a communication link (design target link) for which the bandwidth of the detour path is desired. When the traffic amount on each link of the working path EDCB is observed, it is 10 Mbps on the communication link ED, 100 Mbps on the communication link DC, and 10 Mbps on the communication link CB. Since the communication link with the largest traffic volume in the working path is the communication link DC, the calculation efficiency can be expected by calculating the traffic volume of the detour path on the assumption that the link DC has failed. In this way, it is possible to select the failure assumed links in descending order of the traffic volume and obtain the upper limit value of the detour path bandwidth using the equations (1) to (6).

<Effect of Example>
According to the embodiment of the present invention, the information on the working path and the detour path for transferring traffic in the communication network is given, and traffic flowing through the working path without failure is observed in the communication link. In a situation where the AC traffic flowing between the SD pairs is unknown, the bandwidth of the design target link necessary for the detour path can be calculated. Note that the bandwidth of the detour path can be shared by a plurality of working paths.

In calculating the bandwidth, simply trying to calculate the upper limit value of the bandwidth at the design target link requires resolving the maximization problem for the failure assumption link. However, in the embodiment of the present invention, each failure assumption link When the maximization problem is solved by the above, a new condition is added to the constraint condition that the objective function exceeds the maximum value of the maximization problem that has already been solved. When the maximum value of the original maximization problem solved at each failure assumption link cannot exceed the maximum value of the maximization problem that has already been solved, an executable solution cannot be obtained due to this new condition. As a result, a solution can be obtained at high speed.
The method of randomly selecting a failure assumption link is effective when a failure assumption link that gives a necessary bandwidth upper limit value for a design target link is found at an earlier time point.

  On the other hand, when a communication link with a large traffic volume is assumed to have a failure, it can be assumed that the failure of the working path on the communication link has a large influence on the entire communication network by switching to the detour path. Therefore, by selecting a failure assumption link from communication links having a large traffic volume, it is possible to expect a high speed calculation.

  As mentioned above, although the Example of this invention was described, this invention is not limited to said Example, A various change and application are possible within a claim.

  For convenience of explanation, the system according to the embodiment of the present invention is described using a functional block diagram, but the system of the present invention may be realized by hardware, software, or a combination thereof. For example, each functional unit of the bandwidth calculation device 20 may be realized by software and installed in the operation system 10. Two or more embodiments may be used in combination as necessary.

DESCRIPTION OF SYMBOLS 10 Operation system 20 Band calculation apparatus 30 Band display apparatus 101 Network data collection part 111 Network information database 201 Data acquisition part 202 Band calculation part 211 Path information database 212 Traffic information database 301 Band display part

Claims (4)

A bandwidth calculation method in a bandwidth calculation device for calculating a bandwidth upper limit value of a communication link required in a bypass path when a failure occurs on a communication network in which a working path and a bypass path are set,
Obtaining the amount of traffic flowing through the communication link;
Selecting a first communication link that assumes a failure on the working path;
A bandwidth upper limit value required for the second communication link of the detour path when a failure occurs in the first communication link is determined as a maximum value of a function using the traffic amount as a constraint condition by a linear programming method. A calculating step;
Repeating the selecting step and the calculating step;
Have
The calculating step adds a constraint condition that the function exceeds a calculation result that has already been calculated, and calculates a band upper limit value.   The bandwidth calculating method according to claim 1, wherein the selecting step selects the first communication link in descending order of traffic volume. In the calculating step, when the first communication link is f and the second communication link is e,

To calculate
Furthermore, when the calculation result that has already been calculated is c (e), the following constraints:

The bandwidth calculation method according to claim 1, wherein the bandwidth upper limit value is calculated by adding A bandwidth calculation device that calculates a bandwidth upper limit value of a communication link required for a detour path when a failure occurs on a communication network in which a working path and a detour path are set,
A traffic acquisition unit for acquiring the amount of traffic flowing through the communication link;
A path information storage unit for storing information on the working path and the detour path;
Necessary for the second communication link of the detour path when a failure occurs in the first communication link by selecting the first communication link assuming the occurrence of the failure on the working path from the path information storage unit. A bandwidth calculation unit that calculates a bandwidth upper limit value as a maximum value of a function that uses the traffic amount as a constraint condition by a linear programming method;
Have
The band calculation unit calculates a band upper limit value by adding a constraint condition that the band calculation unit reselects the first communication link and the function exceeds a calculation result already calculated.

Images