JP5325167B2 - Link bandwidth variation upper limit calculation apparatus and link bandwidth variation upper limit calculation method - Google Patents

Abstract

<P>PROBLEM TO BE SOLVED: To provide a link band fluctuation upper limit calculation apparatus and a link band fluctuation upper limit calculation method capable of reducing the time for calculating an upper limit value of band fluctuation for each link in accordance with linear scheduling. <P>SOLUTION: A link band fluctuation upper limit calculation apparatus 1 acquires a link band vector 100 of a network to perform link band design thereon; an AC traffic route matrix 200, and a route changed AC traffic route matrix 300. The link band fluctuation upper limit calculation apparatus 1 reduces the number of parameters (AC traffic bands t<SB POS="POST">j</SB>) to be used for a computational expression according to linear scheduling and the number of restriction conditional expressions and then performs computation processing in accordance with linear scheduling, thereby generating a link band fluctuation upper limit vector 1000 that is an upper limit value of band fluctuation for each link at the time when a route of each AC traffic is changed in response to a route change. <P>COPYRIGHT: (C)2012,JPO&amp;INPIT

Description

  The present invention relates to a link bandwidth fluctuation amount upper limit calculation apparatus and a link bandwidth fluctuation amount upper limit calculation method used for bandwidth design of each link on a network.

  Network services characterized by quality assurance require the design and operation of safe and high-quality IP (Internet Protocol) networks. In addition to continuation of services in the event of a failure, the occurrence of congestion due to detour traffic is considered. Network design is required. In the conventional general equipment design, the band of the link unit is periodically measured, and when the band exceeds a predetermined threshold, a link is added (see Non-Patent Document 1).

  However, the technology for measuring the bandwidth of each link described in Non-Patent Document 1 does not consider the AC traffic between the edge routers, and it is difficult to design a strict link bandwidth as described below. .

  If the link traffic and the path of each AC traffic before and after the occurrence of a fault are known in advance, if the band of each AC traffic can be identified, the band fluctuation value of each link due to the fault occurrence can be obtained. For example, in FIG. 12, when a failure occurs in link # 1 through which AC traffic A (band: a), B (band: b), and C (band: c) flows, links # 4, # 5, and # 6 The increase amount is a + b, and the increase amount of the links # 7, # 8, # 9, and # 10 is c. However, in the prior art, it is difficult to specify the AC traffic band, and therefore, as a link band fluctuation range that does not consider each AC traffic band, the band value of the failed link before the failure occurs is set as the upper limit of the fluctuation range. That is, according to the prior art, in FIG. 12, the upper limit of the band fluctuation of the links # 4, # 5, # 6 and the links # 7, # 8, # 9, # 10 is set to the bandwidth of the link # 1 before the failure occurs. The band design is performed as a + b + c, which is the sum of the bands of AC traffic A, B, and C. However, compared to the actual amount of bandwidth fluctuation, the bandwidth of c + in links # 4, # 5, and # 6, and the bandwidth of a + b in links # 7, # 8, # 9, and # 10 are wasted.

  Therefore, as a link bandwidth design method that considers avoidance of congestion due to detour traffic, the AC traffic bandwidth is treated as a variable, and the bandwidth of each link when the route of each AC traffic is changed from the link bandwidth information by linear programming. A method for calculating the upper limit of the fluctuation amount has been proposed (see Non-Patent Document 2).

  The method of calculating the upper limit value of the bandwidth fluctuation amount by this linear programming method is the linear programming of the upper limit value (maximum value) of the link bandwidth fluctuation amount when the route of each AC traffic is changed due to a route change or failure occurrence. The bandwidth is designed for each link based on the upper limit value obtained by the law. Here, the calculation formula by linear programming is expressed by the following (formula 1) to (formula 3).

The calculation formulas based on the linear programming shown in (Equation 1) to (Equation 3) are calculated by changing each t _j within a range satisfying the constraint equation (Equation 2) and (Equation 3). The upper limit value of the fluctuation amount of the link bandwidth satisfying 1) is maximized.

  The upper limit value of the bandwidth fluctuation amount of each link obtained by solving the calculation formula by this linear programming method is the minimum value among the amount of bandwidth expansion estimated after the path change. Therefore, it is possible to reduce the surplus bandwidth from the necessary bandwidth extension amount, that is, the wasteful bandwidth design amount.

Hisashi Kojima, et al., “Proposal of Network Design and Operation Method Using AC Traffic”, IEICE General Conference, B-6-9 March 2009 Ryuta Sugiyama, et al., “Calculation method for upper limit of link bandwidth when IP network fails”, IEICE General Conference, B-6-12 September 2009

However, in the method of calculating the upper limit value of the band fluctuation amount using the calculation formulas according to the linear programming method of (Equation 1) to (Equation 3), the number of variables (AC traffic band t _j ) used in this linear programming method and the constraints Since the number of conditional expressions is the number of AC traffic and the number of links in the target network, the number of variables and the number of constraint expressions increase as the network size increases, resulting in a long calculation time using linear programming. End up.

  The present invention has been made in view of such a background, and the present invention can reduce the calculation time of the upper limit value of the link bandwidth fluctuation amount by linear programming even when the network size is large. It is an object of the present invention to provide a fluctuation amount upper limit calculation apparatus and a link bandwidth fluctuation amount upper limit calculation method.

In order to solve the above-described problem, the invention according to claim 1 is directed to a network including a plurality of nodes and a plurality of links connecting the plurality of nodes. A link bandwidth fluctuation amount upper limit calculation device for calculating an upper limit value of the network, wherein an input / output unit that transmits / receives information about the network, and information about the network received by the input / output unit are: (1) A link band vector indicating band information, (2) an AC traffic path matrix indicating a path of AC traffic that is traffic between nodes, and (3) after a path change indicating a path of the AC traffic after the path change. As an AC traffic route matrix, an information collection unit to be stored in a storage unit, the link band vector, the AC traffic route matrix, and the previous Extraction and said storage unit after the path change alternating traffic matrix is stored, based on the formula by linear programming described below, an alternating traffic band t _j of the AC traffic route is changed in the objective function (Equation 1) Then, a constraint condition for selecting the set of equality conditional expressions including the extracted AC traffic band t _j as a constraint condition expression (Expression 2-1) from the expressions constituting the constraint condition expression (Expression 2) Select the AC traffic band t _j used in the selection unit and each equality conditional expression shown in the constraint conditional expression (Expression 2-1) as a set of variables (V-1) used in the equivalent conditional expression And the objective function (Equation 1) using the AC traffic band t _j included in the variable set (V-1) as a variable as an objective function (Equation 1-1), and the objective function (Equation 1-1) 1-1), the restriction The link band vector, the AC traffic path matrix, and the post-change AC traffic path matrix stored in the storage unit, which are calculated by the linear programming method using the formula (Formula 2-1) and the constraint condition formula (Formula 3) A link bandwidth fluctuation amount upper limit vector calculation unit that generates a link bandwidth fluctuation amount upper limit vector that is an upper limit value of the bandwidth fluctuation amount of each link when the path of the AC traffic is changed, An information output unit that outputs the generated link bandwidth fluctuation amount upper limit vector via the input / output unit is provided. However, the calculation formula according to the linear programming method is the calculation formula according to claim 1.

According to a fourth aspect of the present invention, for a network including a plurality of nodes and a plurality of links connecting the plurality of nodes, the upper limit value of the bandwidth fluctuation amount of each link after the path change is calculated. A link bandwidth fluctuation amount upper limit calculation method used in a link bandwidth fluctuation amount upper limit calculation device, wherein the link bandwidth fluctuation amount upper limit calculation device transmits / receives information related to the network, and the input / output unit receives The information regarding the network is as follows: (1) a link band vector indicating band information of each link, (2) an AC traffic path matrix indicating a path of AC traffic that is traffic between nodes, and (3) path change And a storage unit for storing the route as a post-change AC traffic route matrix indicating the route of the AC traffic after being performed, and the link Based on a step of obtaining information indicating the area vector, the AC traffic route matrix, and the AC traffic matrix after the route change through the input / output unit, and a calculation formula by linear programming shown below, an objective function (Formula 1 ) In which the AC traffic band t _j of the AC traffic whose route has been changed is extracted, and a set of equality conditional expressions including the extracted AC traffic band t _j is an expression constituting a constraint condition expression (Expression 2) And selecting an AC traffic band t _j used in each equality conditional expression shown in the constraint conditional expression (Expression 2-1) as a constraint conditional expression (Expression 2-1). the objective function used and selecting a set of variables used in the conditional expression (V-1), an alternating traffic band t _j included in the set of the variables (V-1) as a variable ( 1) is an objective function (formula 1-1), and a calculation formula by linear programming based on the objective function (formula 1-1), the constraint condition formula (formula 2-1), and the constraint condition formula (formula 3), Band fluctuation amount of each link when the route of the AC traffic is changed by solving using the link band vector, the AC traffic route matrix and the post-change AC traffic route matrix stored in the storage unit Generating a link bandwidth fluctuation amount upper limit vector, which is an upper limit value of the link bandwidth, and outputting the generated link bandwidth fluctuation amount upper limit vector via the input / output unit. The fluctuation amount upper limit calculation method was adopted. However, the calculation formula according to the linear programming method is a calculation formula according to claim 4.

  Therefore, according to the present invention, since the number of variables used in the linear programming method and the number of constraint condition expressions are reduced and the calculation is performed by the linear programming method, it is possible to prevent the calculation time from becoming long. . That is, the calculation process of the link bandwidth fluctuation amount upper limit calculation apparatus can be speeded up.

According to a second aspect of the present invention, the information collection unit relates to the number of variables used in the calculation formula based on the linear programming via the input / output unit, and indicates an index indicating an increase in the number of variables as the numerical value increases. A target acceleration level n (n is a positive integer), which is a target value of the acceleration level, is further acquired and stored in the storage unit, and the constraint condition selection unit performs the constraint condition expression (Expression 2- In the next speed-up level after 1) is selected, the AC traffic band t _j included in the set of variables (V-1) is included from among the expressions constituting the constraint condition expression (Expression 2). A set of equality conditional expressions is selected as a constraint condition expression (Expression 2-2), and the variable selection unit uses AC traffic used in each equality condition expression indicated by the constraint condition expression (Expression 2-2). set of variables band t _j, used in the equality condition (V-2 And the constraint condition selection unit and the variable selection unit store the selection of the set of equality conditional expressions from the constraint condition expression (Formula 2) and the selection of the set of variables in the storage unit. By repeating up to the number of times indicated by the target acceleration level n, the constraint condition selection unit selects a constraint condition expression (Formula 2-n), and the variable selection unit selects the constraint condition formula (Formula 2- n) The AC traffic band t _j used in each equality conditional expression shown in (n) is selected as a set of variables (Vn) used in the equality conditional expression, and the link band fluctuation amount upper limit vector calculating unit , The objective function (Equation 1) using the AC traffic band t _j included in the set of variables (Vn) as a variable is an objective function (Equation 1-n), and the objective function (Equation 1-n), The constraint condition formula (Formula 2-n) and the constraint condition formula By solving the calculation formula by the linear programming method according to Equation 3) using the link band vector, the AC traffic route matrix, and the post-change AC traffic route matrix stored in the storage unit, the route of the AC traffic can be obtained. The link bandwidth fluctuation amount upper limit calculation device according to claim 1, wherein a link bandwidth fluctuation amount upper limit vector which is an upper limit value of the bandwidth fluctuation amount of each link when changed is generated.

According to a fifth aspect of the present invention, the speed-up is an index indicating an increase in the number of variables as the numerical value increases with respect to the number of variables used in the calculation formula by the linear programming via the input / output unit. The target acceleration level n (n is a positive integer) that is the target value of the level is further acquired and stored in the storage unit, and the following after selecting the constraint expression (Formula 2-1) A set of equality conditional expressions including the AC traffic band t _j included in the variable set (V-1) is constrained from the expressions constituting the constraint conditional expression (Expression 2) at the speed-up level. The step of selecting as the conditional expression (Expression 2-2) and the AC traffic band t _j used in each equality conditional expression shown in the constraint conditional expression (Expression 2-2) are used in the equivalent conditional expression. Selecting as a set of variables (V-2); The step of selecting a set of equality conditional expressions from the constraint condition expression (Expression 2) and the step of selecting the set of variables are repeated up to the number of times indicated by the target acceleration level n stored in the storage unit. By selecting the constraint condition expression (Equation 2-n), the AC traffic band t _j used in each equality conditional expression indicated by the selected constraint condition expression (Equation 2-n) The step of selecting as a set of variables (Vn) used in the conditional expression and the objective function (Expression 1) using the AC traffic band t _j included in the set of variables (Vn) as a variable are the objective function. (Equation 1-n), and a calculation formula by linear programming based on the objective function (Equation 1-n), the constraint condition equation (Equation 2-n), and the constraint condition equation (Equation 3) is stored in the storage unit. The link band vector, the AC A link bandwidth fluctuation amount upper limit vector that is an upper limit value of the bandwidth fluctuation amount of each link when the route of the AC traffic is changed is generated by solving using the traffic route matrix and the AC traffic route matrix after the route change. The link bandwidth variation upper limit calculation method according to claim 4, wherein the link bandwidth fluctuation amount upper limit calculation method according to claim 4 is performed.

  Therefore, according to the present invention, after setting the target acceleration level n, the number of variables used in the linear programming method and the number of constraint expressions can be reduced, and the calculation processing by the linear programming method can be performed.

According to a third aspect of the present invention, the link bandwidth fluctuation amount upper limit calculation apparatus further includes a variable number output unit and a variable number determination unit, and the constraint condition selection unit includes the constraint condition expression (Formula 2-1). In the next speed-up level after selecting), an equal sign including the AC traffic band t _j included in the set of variables (V-1) among the expressions constituting the constraint condition expression (expression 2). A set of conditional expressions is selected as a constraint conditional expression (Expression 2-2), and the variable selection unit uses the AC traffic band t used in each equality conditional expression indicated by the constraint conditional expression (Expression 2-2). _j is selected as a set of variables (V-2) used in the equality conditional expression, and the constraint condition selection unit and the variable selection unit The selection of the set and the selection of the set of variables are performed by the linear programming method. Regarding the number of variables used in the calculation formula, the constraint condition selecting unit is repeated by repeating the number of times indicated by the acceleration level k (k is a positive integer) that is an index indicating the increase in the number of variables as the numerical value increases. Selects a constraint condition expression (Expression 2-k), and the variable selection unit determines the AC traffic band t _j used in each equality condition expression indicated by the constraint condition expression (Expression 2-k) The variable number output unit selects the set of variables (Vk) used in the equality conditional expression, and the variable number output unit includes the AC traffic band t _j included in the variable set (Vk) selected by the variable selection unit. N (V−k), which is a number, is calculated, and the variable number determination unit is N (V−k) at the acceleration level k calculated by the variable number output unit and one before the acceleration level k. The number-of-variables output unit calculates at the acceleration level (k−1) of Set of variables (V- (k-1)) is the number of alternating traffic band t _j included in N (V- (k-1) ) and it is determined whether the same, the variable number determining section When it is determined that N (V−k) at the acceleration level k and N (V− (k−1)) at the acceleration level (k−1) are the same number, the link bandwidth The fluctuation amount upper limit vector calculation unit uses the objective function (Equation 1) using the AC traffic band t _j included in the set of variables (Vk) as a variable as an objective function (Equation 1-k), and the objective function The link band vector, the AC traffic path matrix stored in the storage unit, the calculation formula by the linear programming based on (Expression 1-k), the restriction condition expression (Expression 2-k), and the restriction condition expression (Expression 3). And using the AC traffic route matrix after the route change The link bandwidth fluctuation amount upper limit vector according to claim 1, wherein a link bandwidth fluctuation amount upper limit vector that is an upper limit value of the bandwidth fluctuation amount of each link when the path of the AC traffic is changed is generated by A computing device was used.

Further, in the invention according to claim 6, at the next speed-up level after selecting the constraint equation (Equation 2-1), the equation constituting the constraint equation (Equation 2) is selected from the equations constituting the constraint equation (Equation 2). Selecting a set of equality conditional expressions including the AC traffic band t _j included in the variable set (V-1) as a constraint condition expression (Expression 2-2); and the constraint condition expression (Expression 2-2) From the constraint condition expression (Expression 2), the step of selecting the AC traffic band t _j used in each equality condition expression expressed as) as a set of variables (V-2) used in the equality condition expression An index indicating an increase in the number of variables as the value increases with respect to the number of variables used in the calculation formula by the linear programming, the step of selecting a set of equality conditional expressions and the step of selecting the set of variables. Said acceleration level k, where k is a positive integer By repeated until the number of times indicated, and select the constraint condition (Formula 2-k), the selected constraint equation alternating traffic band t _j used in each equality condition represented by (Formula 2-k) , A step of selecting as a set of variables (Vk) used in the equality conditional expression, and N (V−) which is the number of AC traffic bands t _j included in the selected set of variables (Vk). k), N (V−k) at the calculated acceleration level k, and the set of variables calculated at the acceleration level (k−1) immediately before the acceleration level k. Determining whether or not N (V− (k−1)), which is the number of AC traffic bands t _j included in (V− (k−1)), is equal to N at the acceleration level k; (V-k) and the speed-up level (k-1) N (V− (k−1)) is the same number, the objective function (formula) using the AC traffic band t _j included in the set of variables (V−k) as a variable. 1) is an objective function (Equation 1-k), and a calculation formula based on linear programming based on the objective function (Equation 1-k), the constraint equation (Equation 2-k) and the constraint equation (Equation 3), Band fluctuation amount of each link when the route of the AC traffic is changed by solving using the link band vector, the AC traffic route matrix and the post-change AC traffic route matrix stored in the storage unit And generating a link bandwidth fluctuation amount upper limit vector which is an upper limit value of the link bandwidth fluctuation amount upper limit calculation method according to claim 4.

  Therefore, according to the present invention, calculation can be performed with the highest priority given to calculation accuracy and the number of variables and the number of constraint equations used in linear programming are reduced.

  According to the present invention, it is possible to provide a link bandwidth fluctuation amount upper limit calculation apparatus and a link bandwidth fluctuation amount upper limit calculation method capable of reducing the calculation time of the upper limit value of the link bandwidth fluctuation amount by linear programming. .

It is a figure which shows an example of the network which the link bandwidth fluctuation amount upper limit calculation apparatus which concerns on this embodiment performs the upper limit calculation process of a link bandwidth fluctuation amount. It is a figure for demonstrating the link band vector which concerns on this embodiment. It is a figure for demonstrating the alternating current traffic band vector which concerns on this embodiment. It is a figure for demonstrating the alternating current traffic route matrix which concerns on this embodiment. It is a functional block diagram which shows the structural example of the link band fluctuation amount upper limit calculation apparatus which concerns on the 1st Embodiment of this invention. It is a flowchart which shows the flow of the link band fluctuation amount upper limit calculation process which concerns on the 1st Embodiment of this invention. It is a functional block diagram which shows the structural example of the link band fluctuation amount upper limit calculation apparatus which concerns on the 2nd Embodiment of this invention. It is a flowchart which shows the flow of the link band variation | change_quantity upper limit calculation process which concerns on the 2nd Embodiment of this invention. It is a functional block diagram which shows the structural example of the link band variation | change_quantity upper limit calculation apparatus which concerns on the 3rd Embodiment of this invention. It is a flowchart which shows the flow of the link band variation | change_quantity upper limit calculation process which concerns on the 3rd Embodiment of this invention. It is a figure which shows the experimental result which compared the link bandwidth fluctuation amount upper limit calculation method which concerns on embodiment of this invention, and the conventional method. It is a figure for demonstrating the determination method of the band fluctuation value in a prior art.

  Next, modes for carrying out the invention (hereinafter referred to as “embodiments”) will be described in detail with reference to the drawings as appropriate. First, each piece of network information handled in the link bandwidth fluctuation amount upper limit calculation process according to the present embodiment will be described.

  FIG. 1 is a diagram illustrating an example of a network in which the link bandwidth fluctuation amount upper limit calculation apparatus 1 according to the present embodiment performs link bandwidth fluctuation amount upper limit calculation processing. In the network shown in FIG. 1, an example of processing in which the link bandwidth fluctuation amount upper limit calculation device 1 calculates the upper limit of the link bandwidth fluctuation amount of each link after the path change when the occurrence of a node failure or a link failure is assumed. Will be described.

  As shown in FIG. 1, for example, four nodes of a node “0”, a node “1”, a node “2”, and a node “3” are connected by links. The link connects the transmission source node and the transmission destination node. For example, the link from the node “0” to the node “1” is from the link # 0 and the node “1” depending on the direction of traffic flow between the nodes. The link to the node “0” is set separately depending on the direction of traffic flow, such as link # 5.

  The link bandwidth fluctuation amount upper limit calculation apparatus 1 according to the present embodiment includes a link bandwidth vector 100 indicating information on the current bandwidth (before a route change) of each link, and an AC traffic route indicating a current traffic route (before the route change). By using the matrix 200 and the AC traffic route matrix 300 after the route change when it is assumed that the route of each AC traffic is changed due to the occurrence of a failure or the like, A link bandwidth fluctuation amount upper limit vector 1000 that is an upper limit value of the link bandwidth fluctuation amount is generated.

  Here, the link band vector 100, the AC traffic band vector, and the AC traffic path matrix 200 will be described.

  FIG. 2 is a diagram for explaining the link band vector 100 according to the present embodiment. The link bandwidth vector 100 is a vector display of the traffic bandwidth measured in each link in the order of link numbers. For example, in the network shown in FIG. 2A, the link bandwidth vector 100 displays the vectors measured in the links # 0 to # 9 in the order of link numbers as shown in FIG. 2B. Here, for example, the bandwidth measured at link # 0 is “15 (Mbps)”, and the bandwidth measured at link # 1 is “9 (Mbps)”.

The link bandwidth vector 100 is
Link band vector X = (x ₀ , x ₁ ,..., X _L−1 ) ^tr
Where tr means transposition of the matrix (vector) (transposition of rows and columns).

  FIG. 3 is a diagram for explaining an AC traffic band vector according to the present embodiment. AC traffic refers to the flow of traffic between two nodes in the network. The AC traffic band means a band value of AC traffic. FIG. 3A shows the AC traffic in the four nodes from node “0” to node “3”, and FIG. 3B shows the AC traffic amount (AC traffic band) measured in each AC traffic. ) In the order of AC traffic numbers. For example, the AC traffic amount (AC traffic band) of AC traffic “0” (node “0” to node “1”) is “4 (Mbps)”.

This AC traffic band vector is
AC traffic band vector T = (t ₀ , t ₁ ,..., _{T T−1} ) ^tr
Can be written.

  FIG. 4 is a diagram for explaining an AC traffic route matrix 200 according to the present embodiment. The AC traffic route matrix 200 indicates whether or not each AC traffic passes through each link by “1” when it passes, and “0” when it does not pass, thereby indicating a route of each AC traffic. It is. When each AC traffic is routed through each link as shown in FIG. 4A, the AC traffic route matrix is a matrix indicating the relationship between each link and each AC traffic as shown in FIG. 4B. Is displayed. For example, the AC traffic “1” (traffic from the node “0” to the node “2”) indicates that the values of the link # 0 and the link # 1 are “1” in the AC traffic route matrix 200 of FIG. Therefore, it is indicated that the link # 0 and the link # 1 are routed.

となる交流トラヒック帯域ｔ_ｊ）を抽出する。そして、その抽出した交流トラヒック帯域ｔ_ｊを用いて、線形計画法による計算式における、変数（交流トラヒック帯域ｔ_ｊ）の数と、制約条件式の数とを削減し、線形計画法による計算時間を短縮して、経路変更後の各リンクの帯域変動量の上限値を計算するものである。第２の実施形態は、第１の実施形態の線形計画法による計算処理に比べ、計算速度が低下しても計算精度を向上させることを目的に、計算精度を上げるための処理を所定回数繰り返し行った上で、経路変更後の各リンクの帯域変動量の上限値を計算するものである。この計算精度を上げるための処理は、第１の実施形態においては、計算処理の対象外とした変数（交流トラヒック帯域ｔ_ｊ）および制約条件式のうちの一部を、新たに計算処理の対象に加えることで、計算制度を向上させる。また、この計算精度を上げるため繰り返される処理回数は、高速化レベルｋとして入力される。そして、第３の実施形態は、従来技術における線形計画法による計算処理に比べ、計算精度を低下させないように、変数（交流トラヒック帯域ｔｊ）の数および制約条件式の数を削減し、経路変更後の各リンクの帯域変動量の上限値を計算するものである。 Next, first to third embodiments of the present invention will be described. In the first embodiment, the link bandwidth fluctuation amount upper limit calculation apparatus 1 acquires the AC traffic route matrix 300 after the route change and compares it with the AC traffic route matrix 200 before the route change, so that the route is changed. AC traffic band t _j (that is,

The AC traffic band t _j ) is extracted. Then, using the extracted AC traffic band t _j , the number of variables (AC traffic band t _j ) and the number of constraint condition expressions in the calculation formula by linear programming are reduced, and the calculation time by linear programming is reduced. And the upper limit value of the bandwidth fluctuation amount of each link after the path change is calculated. The second embodiment repeats the processing for increasing the calculation accuracy a predetermined number of times for the purpose of improving the calculation accuracy even if the calculation speed is reduced compared to the calculation processing by the linear programming method of the first embodiment. Then, the upper limit value of the bandwidth fluctuation amount of each link after the route change is calculated. In the first embodiment, the processing for increasing the calculation accuracy is performed by newly calculating a part of the variable (AC traffic band t _j ) and the constraint condition expression that are excluded from the calculation processing target. In addition to improving the calculation system. In addition, the number of processes repeated to increase the calculation accuracy is input as the acceleration level k. The third embodiment reduces the number of variables (AC traffic band tj) and the number of constraint condition expressions so as not to reduce the calculation accuracy as compared with the calculation processing by the linear programming method in the prior art, and changes the path. The upper limit value of the bandwidth fluctuation amount of each subsequent link is calculated.

<< First Embodiment >>
First, the link bandwidth fluctuation amount upper limit calculation apparatus 1 (1a) according to the first embodiment of the present invention will be described.

(Outline of processing)
The link bandwidth fluctuation amount upper limit calculation apparatus 1 (1a) according to the first embodiment uses a variable (AC traffic bandwidth t _j ) in a calculation formula based on the linear programming of (Expression 1) to (Expression 3) used in the prior art. ) And the number of constraint conditions are reduced, and calculation processing by linear programming is performed. An outline of processing will be described using a specific example shown below.

となる交流トラヒック帯域ｔ_ｊ）が、ｔ_０とｔ_１であるものとしている。また、（式２）および（式３）は、（式１）を計算する際の制約条件式である。（式２）は、リンク毎の等号条件式で表わすことができ、その具体例を、等号条件式（２−ａ）,（２−ｂ），（２−ｃ），（２−ｄ）であるとする。 In the calculation formula by the linear programming shown in [Equation 2], (Expression 1) represents an objective function s for obtaining the upper limit value of the bandwidth fluctuation amount of each link. Here, by comparing the AC traffic route matrix 300 after the route change with the AC traffic route matrix 200 before the route change, the AC traffic band t _j (that is, the AC traffic band t _j (ie,

It is assumed that the AC traffic band t _j ) becomes t ₀ and t ₁ . Further, (Equation 2) and (Equation 3) are constraint equations for calculating (Equation 1). (Expression 2) can be expressed by an equality conditional expression for each link, and specific examples thereof are equivalent conditional expressions (2-a), (2-b), (2-c), (2-d ).

The link bandwidth fluctuation amount upper limit calculation apparatus 1 (1a) according to the first embodiment of the present invention extracts AC traffic bands t ₀ and t ₁ used in (Equation 1). Then, the link bandwidth fluctuation amount upper limit calculation device 1 (1a) includes an equality conditional expression including the AC traffic bands t ₀ and t ₁ extracted from the equality conditional expressions (2-a) to (2-d). (2-a) and (2-b) are selected, and a set of these two expressions is used as a constraint condition expression (Expression 2-1) (see Equation 3 below).

Next, the link band fluctuation amount upper limit calculation apparatus 1 (1a) uses the AC traffic bands t ₀ , t ₁ , t ₃ used in the selected equality conditional expressions (2-a) and (2-b). , extracts the _{t 4,} as a constraint condition expression set of variables used in the equation (2-1) (V-1).
The link bandwidth fluctuation amount upper limit calculation apparatus 1 (1a) uses the AC traffic bands t ₀ , t ₁ , t ₃ , and t ₄ included in the variable set (V-1) as variables (Equation 1). And an objective function (formula 1-1) (see [Equation 3] described later).

  Using the objective function (Equation 1-1), constraint equation (Equation 2-1), and constraint equation (Equation 3) shown in the following [Equation 3], the link bandwidth variation upper limit is generated. The calculation apparatus 1 (1a) performs calculation processing by linear programming.

The calculation formula by the linear programming shown in [Equation 3] is different from the calculation formula by the conventional linear programming shown in [Equation 2] until the number of AC traffic bands t _j as variables is from t ₀ to t _5. Are reduced to four t ₀ , t ₁ , t ₃ , t ₄ , and the constraint condition expression (Expression 2) is changed from four equality conditional expressions to two equality conditional expressions (Expression It has been reduced to 2-1). Therefore, the link bandwidth fluctuation amount upper limit calculation apparatus 1 (1a) according to the first embodiment of the present invention can reduce the number of variables and the number of constraint expressions, and shorten the processing time, as compared with the conventional technique. Can be planned.

(Configuration of Link Bandwidth Variation Upper Limit Calculation Device in the First Embodiment)
Next, the configuration of the link bandwidth fluctuation amount upper limit calculation apparatus 1 (1a) according to the first embodiment of the present invention will be described.
FIG. 5 is a functional block diagram showing a configuration example of the link bandwidth fluctuation amount upper limit calculation apparatus 1 (1a) according to the first embodiment of the present invention. As shown in FIG. 5, the link bandwidth fluctuation amount upper limit calculation device 1 a includes an input / output unit 10, a processing unit 20, and a storage unit 30.

  The input / output unit 10 receives, for example, a link band vector 100 (see FIG. 2), an AC traffic route matrix 200 (see FIG. 4), and an AC traffic route after a route change from a network management device (not shown) provided in the network. Information relating to traffic of the target network such as the matrix 300 is acquired. In this case, the post-change AC traffic route matrix 300 does not pass through a node or link that cannot be used when a network designer assumes that a network inspection or a failure has occurred in a certain node or link. It represents the route of AC traffic after the designed route change.

  Note that the AC traffic route matrix 200 is calculated using the topology information indicating the connection relationship between each node and each link in the network, for example, using the Dijkstra method for OSPF (Open Shortest Path First). . Further, the post-change AC traffic route matrix 300 is also represented as a Dijkstra as a post-change AC traffic matrix 300 indicating a detour route after the occurrence of a failure based on the topology information and failure location information such as the occurrence of a failure of a node or link. It can be calculated using a method or the like. These pieces of information are calculated by a network management device (not shown) and input to the link bandwidth fluctuation amount upper limit calculation device 1.

  Further, the input / output unit 10 outputs a link band fluctuation amount upper limit vector 1000, which will be described later, generated by the processing unit 20. The input / output unit 10 includes an input / output interface and a communication interface.

  The processing unit 20 is responsible for overall control of the link bandwidth fluctuation amount upper limit calculation device 1a, and includes an information collection unit 21, a constraint condition selection unit 22, a variable selection unit 23, a link bandwidth fluctuation amount upper limit vector calculation unit 28, And an information output unit 29. Note that the processing unit 20 and the input / output unit 10 are configured such that, for example, a program stored in the storage unit 30 of the link bandwidth variation upper limit calculation device 1 (1a) is stored in a CPU (Central Processing Unit) RAM (Random Access Memory). This is realized by deploying and executing.

  The information collection unit 21 acquires information on the bandwidth of each link and the AC traffic route via the input / output unit 10, and the link bandwidth vector 100, the AC traffic route matrix 200, and the route-changed AC traffic route matrix 300. Is stored in the storage unit 30.

  The constraint condition selection unit 22 uses an equality conditional expression for each link indicating the constraint condition expression (Expression 2) among the calculation expressions based on the linear programming shown in [Equation 1] used by the link bandwidth variation upper limit vector calculation section 28. A process of selecting an equality conditional expression to be used for calculation is performed.

となる１つ以上の交流トラヒック帯域ｔ_ｊ、つまり、交流トラヒックの経路変更前と経路変更後において経路の変更がある１つ以上の交流トラヒックの交流トラヒック帯域ｔ_ｊを抽出する。そして、制約条件選択部２２は、記憶部３０内の制約条件情報４００に記憶した制約条件式（式２）を示すリンク毎の等号条件式の中から、抽出した１以上の交流トラヒック帯域ｔ_ｊを含む等号条件式の集合を制約条件式（式２−１）として選択し、制約条件情報４００に記憶する。 Specifically, the constraint condition selection unit 22 uses the link bandwidth vector 100 stored in the storage unit 30 and the AC traffic route matrix 200 before the route change to use the linear plan used by the link bandwidth variation upper limit vector calculation unit 28. An equality conditional expression for each link indicating a constraint conditional expression (Formula 2) among the calculation formulas obtained by the method is generated and stored in the constraint condition information 400 in the storage unit 30. In addition, the constraint condition selection unit 22 uses the AC traffic route matrix 200 and the post-change AC traffic route matrix 300 stored in the storage unit 30, in the objective function (Equation 1) of the calculation formula by linear programming,

One or more alternating traffic band t _j as _a, that is, extracts the AC traffic band t _j of one or more exchanges traffic there is a change of route after the route change before and rerouting of the AC traffic. The constraint condition selection unit 22 then extracts one or more AC traffic bands t extracted from the equality condition equation for each link indicating the constraint condition equation (Equation 2) stored in the constraint condition information 400 in the storage unit 30. A set of equality conditional expressions including _j is selected as a constraint conditional expression (Formula 2-1) and stored in the constraint condition information 400.

The variable selection unit 23 uses the AC traffic band t _j used in each equality conditional expression of the restriction condition expression (Expression 2-1) selected by the restriction condition selection part 22 as the restriction condition expression (Expression 2-1). As a set of variables (V-1) to be stored and stored in the variable information 500 in the storage unit 30.

The link bandwidth fluctuation amount upper limit vector calculation unit 28 calculates the upper limit value of the bandwidth fluctuation amount for each link after the path change using a calculation formula based on linear programming.
Specifically, the link band fluctuation amount upper limit vector calculation unit 28 extracts each AC traffic band t _j included in the variable set (V-1) selected by the variable selection unit 23, and the extracted AC traffic band. An objective function (expression 1) using t _j as a variable is generated as an objective function (expression 1-1). The link bandwidth fluctuation amount upper limit vector calculation unit 28 then generates the generated objective function (Equation 1-1), the constraint condition equation (Equation 2-1) and the constraint condition equation (Equation 3) selected by the constraint condition selection unit 22. The link bandwidth fluctuation amount upper limit vector 1000 is generated by solving the calculation formula using the linear programming method. Then, the link bandwidth variation upper limit vector calculation unit 28 stores the generated link bandwidth variation amount upper limit vector 1000 in the storage unit 30.

  The information output unit 29 outputs the link bandwidth fluctuation amount upper limit vector 1000 stored in the storage unit 30 to a network management device (not shown) or the like via the input / output unit 10.

  Next, the storage unit 30 is a storage unit configured by a hard disk, a flash memory, or the like, and includes a link band vector 100, an AC traffic route matrix 200, a route-changed AC traffic route matrix 300, constraint information 400, and variable information 500. , And a link bandwidth fluctuation amount upper limit vector 1000 is stored.

  The constraint condition information 400 stores an equality conditional expression for each link indicating a constraint condition expression (Expression 2) of a calculation formula based on linear programming generated by the constraint condition selection unit 22. In addition, a constraint condition expression (expression 2-1) that is a set of equality condition expressions selected from the equality condition expressions for each ring indicating the constraint condition expression (expression 2) by the constraint condition selection unit 22 is stored. The

The variable information 500 stores a set (V-1) of variables (AC traffic band t _j ) used in the constraint condition expression (Expression 2-1).

(Link bandwidth fluctuation amount upper limit calculation process of the first embodiment)
Next, the flow of the link bandwidth fluctuation amount upper limit calculation process of the link bandwidth fluctuation amount upper limit calculation device 1a will be described. FIG. 6 is a flowchart showing the flow of the link bandwidth fluctuation amount upper limit calculation process according to the first embodiment of the present invention.

  First, the information collection unit 21 of the link bandwidth fluctuation amount upper limit calculation apparatus 1a acquires the information of the link bandwidth vector 100, the AC traffic route matrix 200, and the AC traffic route matrix 300 after the route change via the input / output unit 10. (Step S <b> 101) and stored in the storage unit 30.

となる１つ以上の交流トラヒック帯域ｔ_ｊ、つまり、交流トラヒックの経路変更前と経路変更後において経路の変更がある１つ以上の交流トラヒックの交流トラヒック帯域ｔ_ｊを抽出する。そして、制約条件選択部２２は、記憶部３０内の制約条件情報４００に記憶した制約条件式（式２）を示すリンク毎の等号条件式の中から、抽出した１以上の交流トラヒック帯域ｔ_ｊを含む等号条件式の集合を制約条件式（式２−１）として選択し、制約条件情報４００に記憶する。 Next, the constraint condition selection unit 22 performs a process of selecting a constraint condition expression (Formula 2-1) (step S102).
Specifically, the constraint condition selection unit 22 uses the link bandwidth vector 100 stored in the storage unit 30 and the AC traffic route matrix 200 before the route change to calculate a constraint condition equation (formula 2) based on linear programming. The equality conditional expression for each link indicating) is generated and stored in the constraint condition information 400 in the storage unit 30. Subsequently, the constraint condition selection unit 22 uses the AC traffic route matrix 200 and the route-changed AC traffic route matrix 300 stored in the storage unit 30 to calculate the objective function (Equation 1) of the calculation formula by linear programming.

One or more alternating traffic band t _j as _a, that is, extracts the AC traffic band t _j of one or more exchanges traffic there is a change of route after the route change before and rerouting of the AC traffic. The constraint condition selection unit 22 then extracts one or more AC traffic bands t extracted from the equality condition equation for each link indicating the constraint condition equation (Equation 2) stored in the constraint condition information 400 in the storage unit 30. A set of equality conditional expressions including _j is selected as a constraint conditional expression (Formula 2-1) and stored in the constraint condition information 400.

Subsequently, in step S102, the variable selection unit 23 converts the AC traffic band t _j used in each equality conditional expression of the restriction condition expression (Expression 2-1) selected by the restriction condition selection part 22 into the restriction condition expression ( It is selected as a set (V-1) of variables used in Expression 2-1) (step S103) and stored in the variable information 500 in the storage unit 30.

Next, the link bandwidth fluctuation amount upper limit vector calculation unit 28 uses an objective function (Equation 1) that uses the AC traffic bandwidth t _j included in the variable set (V-1) as a variable as an objective function (Equation 1-1). (Step S104). Then, the link bandwidth variation upper limit vector calculation unit 28 performs linear programming based on the generated objective function (Equation 1-1), the constraint condition equation (Equation 2-1) selected in Step S102, and the constraint condition equation (Equation 3). Is calculated using the link band vector 100, the AC traffic route matrix 200 and the post-route-changed AC traffic route matrix 300 stored in the storage unit 30, thereby generating the link band fluctuation amount upper limit vector 1000 (step S105). Then, the link bandwidth variation upper limit vector calculation unit 28 stores the generated link bandwidth variation amount upper limit vector 1000 in the storage unit 30.

  Next, the information output unit 29 outputs the link bandwidth fluctuation amount upper limit vector 1000 stored in the storage unit 30 via the input / output unit 10 (step S106).

By doing so, according to the link bandwidth fluctuation amount upper limit calculation apparatus 1 (1a) according to the first embodiment of the present invention, the number of variables (AC traffic bandwidth t _j ) used in the calculation formula by the linear programming method. Since the calculation by the linear programming method is performed after reducing the number of equality conditional expressions in the constraint condition expression (Expression 2), it is possible to prevent the calculation time from becoming long. That is, the calculation process of the link bandwidth fluctuation amount upper limit calculation apparatus 1 (1a) can be speeded up.
Since the upper limit value of the bandwidth fluctuation amount of each link calculated by the link bandwidth fluctuation amount upper limit calculation device 1 (1a) is the minimum value of the bandwidth extension amount of each link necessary after the path change, the link bandwidth design In this case, a wasted bandwidth can be suppressed.

<< Second Embodiment >>
Next, the link bandwidth fluctuation amount upper limit calculation apparatus 1 (1b) according to the second embodiment of the present invention will be described.

(Outline of processing)
First, an outline of processing according to the second embodiment of the present invention will be described.
The link bandwidth fluctuation amount upper limit calculation apparatus 1 (1b) according to the second embodiment of the present invention repeatedly performs the processing for improving the calculation accuracy shown below a predetermined number of times, so that the link bandwidth according to the first embodiment Compared to the upper limit calculation processing of the fluctuation amount, the number of variables (AC traffic band t _j ) and the number of equality conditional expressions used in the constraint condition expression (Expression 2) are not reduced excessively (that is, in the first embodiment). The upper limit value of the bandwidth fluctuation amount of each link after the path change is calculated by increasing the number of variables and the number of equality conditional expressions) rather than the calculation processing of the linear programming method.

If it demonstrates using a specific example, the link band fluctuation amount upper limit calculation apparatus 1 (1b) which concerns on 2nd Embodiment will be a set of variables used for the constraint condition expression (Formula 2-1) shown by [Equation 3]. An equality conditional expression including AC traffic bands t ₀ , t ₁ , t ₃ , and t ₄ as (V-1) is expressed as a constraint condition expression (formula 2) stored in the constraint condition information 400 in the storage unit 30. Select from the equality conditional expressions for each link shown. As a result, equality conditional expressions (2-a), (2-b), and (2-d) are selected, and a set of these three expressions is defined as a constraint conditional expression (2-2) (described later 4]).

Next, the link band fluctuation amount upper limit calculation device 1 (1b) uses the AC traffic band t ₀ used in the selected equality conditional expressions (2-a), (2-b), and (2-d). , T ₁ , t ₂ , t ₃ , t ₄ are extracted as a set of variables (V-2) used in the constraint condition expression (formula 2-2).
The link bandwidth fluctuation amount upper limit calculation apparatus 1 (1b) uses the AC traffic bands t ₀ , t ₁ , t ₂ , t ₃ , and t ₄ included in this variable set (V-2) as variables (formulas). 1) is generated as an objective function (Formula 1-2) (see [Equation 4] described later).

  Using the objective function (Equation 1-2), constraint equation (Equation 2-2), and constraint equation (Equation 3) shown in the following [Equation 4], the upper limit of the link bandwidth fluctuation amount is generated. The calculation device 1 (1b) performs calculation processing by linear programming.

Then, the link bandwidth fluctuation amount upper limit calculation apparatus 1 (1b) according to the second embodiment increases the number of variables and the number of equality conditional expressions, and performs a process for increasing the calculation accuracy. Repeat until speed-up level “n”. “N” is a positive integer and represents the number of times (n times) the process of increasing the number of variables is repeated in order to increase the calculation accuracy.
By doing in this way, the link bandwidth fluctuation amount upper limit calculation apparatus 1 (1b) according to the second embodiment increases the calculation speed as compared with the prior art, and also considers the calculation accuracy, and becomes a target high speed. The upper limit value of the bandwidth fluctuation amount of each link after the route change can be calculated.

(Configuration of link bandwidth fluctuation amount upper limit calculation apparatus in the second embodiment)
Next, the configuration of the link bandwidth fluctuation amount upper limit calculation apparatus 1 (1b) according to the second embodiment of the present invention will be described.
FIG. 7 is a functional block diagram showing a configuration example of the link bandwidth fluctuation amount upper limit calculation apparatus 1 (1b) according to the second embodiment of the present invention. As shown in FIG. 7, the link bandwidth fluctuation amount upper limit calculation device 1b includes an input / output unit 10, a processing unit 20, and a storage unit 30 in the same manner as the link bandwidth fluctuation amount upper limit calculation device 1a shown in FIG. Consists of including. Note that in the second embodiment, configurations having the same functions as those of the link bandwidth fluctuation amount upper limit calculation apparatus 1a shown in FIG.

  The input / output unit 10 in the second embodiment includes, for example, a link band vector 100, an AC traffic route matrix 200, an AC traffic route matrix 300 after a route change, and a target from a network management device (not shown) provided in the network. Information on the acceleration level “n” is acquired. Then, the information collecting unit 21 stores these pieces of information in the storage unit 30. Information relating to the target acceleration level “n” is stored in the target acceleration level information 600 described later in the storage unit 30 by the information collecting unit 21.

Here, the target acceleration level “n” is a target value of the acceleration level “k (positive integer)”. When the acceleration level “k” is the acceleration level “1”, the link bandwidth fluctuation amount upper limit calculation apparatus 1 (1b) according to the second embodiment is the same as the process according to the first embodiment. The number of variables (AC traffic band t _j ) and the number of equality conditional expressions in the constraint condition expression (Expression 2) are reduced most. As a result, the calculation processing speed is the fastest. In addition, as the speedup level “k” increases, the number of variables (AC traffic band t _j ) and the number of equality conditional expressions increase. As a result, priority is given to improving accuracy over calculation speed. Can be processed.

  In addition to the configuration of the processing unit 20 of the link bandwidth fluctuation amount upper limit calculation device 1a shown in FIG. 5, the processing unit 20 in the second embodiment of the present invention includes an acceleration level processing unit 24 and an acceleration level determination unit. 25.

  The acceleration level processing unit 24 initializes the acceleration level “k” stored in the acceleration level information 700 described later in the storage unit 30 to “0”. The acceleration level processing unit 24 increases the speed every time the processing by the constraint condition selection unit 22 and the variable selection unit 23 (processing for increasing the number of variables and the number of equality conditional expressions to increase the calculation accuracy) is repeated. The speed-up level “k” stored in the speed level information 700 is updated by adding “+1”.

  The acceleration level determination unit 25 determines whether or not the acceleration level “k” stored in the acceleration level information 700 matches the value of the target acceleration level “n” stored in the target acceleration level information 600. Determine.

In addition, when the value of the acceleration level “k” is “1”, the constraint condition selection unit 22 in the second embodiment performs the same process as the process of the constraint condition selection unit 22 in the first embodiment. Do. Then, when the value of the acceleration level “k” is a value equal to or greater than “2”, the constraint condition selection unit 22 stores the constraint condition information (Equation 2) stored in the constraint condition information 400 for each link. An equality conditional expression including an AC traffic band t _j used in a set of variables (V− (k−1)) selected by the variable selection unit 23 from the conditional expression is expressed as a constraint conditional expression (Expression 2- k) and stored in the constraint information 400.

The variable selection unit 23 in the second embodiment uses the AC traffic band t _j used in each equality conditional expression of the constraint condition expression (Expression 2-k) at the acceleration level “k” selected by the constraint condition selection unit 22. Are selected as a set of variables (Vk) used in the constraint condition expression (Expression 2-k) and stored in the variable information 500 in the storage unit 30.

The link bandwidth fluctuation amount upper limit vector calculation unit 28 according to the second embodiment, when the acceleration level determination unit 25 determines that the values of the acceleration level “k” and the target acceleration level “n” match, An objective function (Expression 1) using the AC traffic band t _j included in the variable set (Vn) selected by the selection unit 23 as a variable is generated as an objective function (Expression 1-n). Then, the link bandwidth variation upper limit vector calculation unit 28 uses the generated objective function (Equation 1-n), the constraint condition equation (Equation 2-n) selected by the constraint condition selection unit 22, and the constraint condition equation (Equation 3). A link bandwidth variation upper limit vector 1000 is generated by solving a calculation formula based on linear programming.

  In addition to the configuration of the storage unit 30 in the first embodiment, the target acceleration level information 600 and the acceleration level information 700 are stored in the storage unit 30 in the second embodiment. The target acceleration level information 600 stores information on the target acceleration level “n” acquired by the information collection unit 21 via the input / output unit 10. The acceleration level information 700 stores an acceleration level “k” that is set or updated by the acceleration level processing unit 24.

(Link bandwidth fluctuation amount upper limit calculation processing of the second embodiment)
Next, the flow of the link bandwidth fluctuation amount upper limit calculation process of the link bandwidth fluctuation amount upper limit calculation device 1b will be described. FIG. 8 is a flowchart showing the flow of the link bandwidth fluctuation amount upper limit calculation process according to the second embodiment of the present invention.

  First, the acceleration level processing unit 24 of the link bandwidth variation upper limit calculation device 1b initializes the acceleration level “k” stored in the acceleration level information 700 in the storage unit 30 to “0” (step S201). ).

  Next, the information collection unit 21 acquires the information of the link band vector 100, the AC traffic route matrix 200, the post-change AC traffic route matrix 300, and the target acceleration level “n” via the input / output unit 10. (Step S <b> 202) and stored in the storage unit 30. The information collection unit 21 stores the acceleration level “n” in the target acceleration level information 600 in the storage unit 30.

  Hereinafter, as will be described later, the processing from step S203 to S206 is repeated until the target speedup level n is reached, but the first processing in steps S203 to S206 is processing at the speedup level “1”. The second process of steps S203 to S206 is a process at the acceleration level “2”, and similarly, the kth process of steps S203 to S206 is a process at the acceleration level “k”.

[Acceleration level "1" processing]
First, the acceleration level processing unit 24 adds “+1” to the acceleration level “k” stored in the acceleration level information 700 in the storage unit 30 (step S203). Therefore, here, “+1” is added to the acceleration level “0” stored in the acceleration level information 700, and the acceleration level “1” is set.

となる１つ以上の交流トラヒック帯域ｔ_ｊを抽出する。続いて、制約条件選択部２２は、記憶部３０内の制約条件情報４００に記憶した制約条件式（式２）を示すリンク毎の等号条件式の中から、抽出した１以上の交流トラヒック帯域ｔ_ｊを含む等号条件式の集合を制約条件式（式２−１）として選択し、制約条件情報４００に記憶する。 Next, the constraint condition selection unit 22 performs a selection process of the constraint condition expression (formula 2-1) similar to step S102 in FIG. 6 (step S204). Specifically, the constraint condition selection unit 22 uses the link bandwidth vector 100 stored in the storage unit 30 and the AC traffic route matrix 200 before the route change to calculate a constraint condition equation (formula 2) based on linear programming. The equality conditional expression for each link indicating) is generated and stored in the constraint condition information 400 in the storage unit 30. Then, the constraint condition selection unit 22 calculates the objective function (Formula 1) of the calculation formula by the linear programming method.

One or more AC traffic bands t _j are extracted. Subsequently, the constraint condition selection unit 22 extracts one or more AC traffic bands extracted from the equality condition equation for each link indicating the constraint condition equation (Equation 2) stored in the constraint condition information 400 in the storage unit 30. A set of equality conditional expressions including t _j is selected as a constraint conditional expression (Formula 2-1) and stored in the constraint condition information 400.

Then, in step S204, the variable selection unit 23 converts the AC traffic band t _j used in each equality conditional expression of the restriction condition expression (Expression 2-1) selected by the restriction condition selection part 22 into the restriction condition expression (Expression 2-1) is selected as a set of variables (V-1) to be used (step S205), and stored in the variable information 500 in the storage unit 30.

  Subsequently, the speed-up level determination unit 25 determines the values of the speed-up level “k” stored in the speed-up level information 700 and the target speed-up level “n” stored in the target speed-up level information 600. It is determined whether or not they match (step S206). Therefore, it is determined here whether or not the acceleration level “1” matches the target acceleration level “n”.

If the acceleration level determination unit 25 determines that the acceleration level “1” matches the target acceleration level “n” (step S206 → Yes), the process proceeds to steps S207 to S209. The processes in steps S207 to S209 are the same as those in steps S104 to S106 shown in FIG. That is, the link bandwidth variation upper limit vector calculation unit 28 generates an objective function (Equation 1-1) using a set of variables (V-1) in Step S207, and then obtains the objective function (Equation 1-1). ), The constraint equation (Equation 2-1) selected in Step S204, and the constraint equation (Equation 3) are used to solve the calculation formula by linear programming, and the link bandwidth variation upper limit vector 1000 is generated ( In step S208), the information output unit 29 outputs the information via the input / output unit 10 (step S209).
In this way, it is possible to generate the link bandwidth fluctuation amount upper limit vector 1000 at the acceleration level “1”.

  On the other hand, if it is determined in step S206 that the acceleration level “1” does not match the target acceleration level “n” (step S206 → No), the process returns to step S203.

[Acceleration level "2" processing]
Next, in step S <b> 203, the acceleration level processing unit 24 adds “+1” to the acceleration level “k” stored in the acceleration level information 700 in the storage unit 30. Therefore, here, “+1” is added to the acceleration level “1” stored in the acceleration level information 700, and the acceleration level “2” is set.

Subsequently, the constraint condition selection unit 22 is selected by the variable selection unit 23 in step S205 from the equality condition formula for each link indicating the constraint condition expression (Formula 2) stored in the constraint condition information 400. The equality conditional expression including the AC traffic band t _j used in the variable set (V-1) is selected as the constraint condition expression (Formula 2-2) (step S204) and stored in the constraint condition information 400.

Then, the variable selection unit 23 converts the AC traffic band t _j used in each equality conditional expression of the restriction condition expression (Expression 2-2) selected by the restriction condition selection part 22 in Step S204 into the restriction condition expression (Expression 2). -2) is selected as a set of variables (V-2) to be used (step S205) and stored in the variable information 500 in the storage unit 30.

  Subsequently, the speed-up level determination unit 25 determines whether the speed-up level “2” stored in the speed-up level information 700 and the target speed-up level “n” stored in the target speed-up level information 600 are the same. It is determined whether or not they match (step S206).

  If the speed-up level determination unit 25 determines that the speed-up level “2” matches the target speed-up level “n” (step S206 → Yes), the process proceeds to the next step S207.

In step S207, the link band fluctuation amount upper limit vector calculation unit 28 uses the objective function (formula 1) using the AC traffic band t _j included in the variable set (V-2) as a variable as the objective function (formula 1-2). ). Then, the link bandwidth variation upper limit vector calculation unit 28 performs linear programming using the generated objective function (Equation 1-2), the constraint condition equation (Equation 2-2) selected in Step S204, and the constraint equation (Equation 3). The link bandwidth fluctuation amount upper limit vector 1000 is generated by solving the calculation formula (1) (step S208), and the information output unit 29 outputs it via the input / output unit 10 (step S209).
By doing in this way, it is possible to generate the link band fluctuation amount upper limit vector 1000 of the acceleration level “2”.

On the other hand, if it is determined in step S206 that the acceleration level “2” does not match the target acceleration level “n” (step S206 → No), the process returns to step S203.
Then, the speed-up level determination unit 25 determines the value of the speed-up level “k” stored in the speed-up level information 700 and the value of the target speed-up level “n” stored in the target speed-up level information 600. Are matched, the processes in steps S203 to S205 are repeated until it is determined in step S206. When the acceleration level determination unit 25 determines that the acceleration level “k” matches the target acceleration level “n”, the link bandwidth variation upper limit vector calculation unit 28 sets the variable set (V−n). An objective function (Expression 1) using the included AC traffic band t _j as a variable is generated as an objective function (Expression 1-n). Then, the link bandwidth variation upper limit vector calculation unit 28 performs linear programming based on the generated objective function (Expression 1-n), the constraint condition expression (Expression 2-n) selected in Step S204, and the constraint condition expression (Expression 3). The link bandwidth fluctuation amount upper limit vector 1000 is generated by solving the calculation formula (1) (step S208), and the information output unit 29 outputs it via the input / output unit 10 (step S209). In this way, it is possible to generate the link bandwidth fluctuation amount upper limit vector 1000 having the target speedup level “n”.

Therefore, according to the link bandwidth fluctuation amount upper limit calculation apparatus 1b according to the second embodiment of the present invention, after setting the target acceleration level “n”, the variable (AC traffic bandwidth) used in the calculation formula by the linear programming method is set. By reducing the number of t _j ) and the number of equality conditional expressions in the constraint condition expression (Expression 2), it is possible to perform calculation processing by linear programming.
When the target acceleration level “n” is set to “1”, the same processing as in the first embodiment is performed, and the number of variables and the constraint conditions are compared with those after the acceleration level “2”. The processing time can be reduced by reducing the number of On the other hand, each time the speed-up level “k” is increased, the number of variables and the number of equality conditional expressions increase, and the processing speed decreases, but the calculation accuracy can be improved.

<< Third Embodiment >>
Next, the link bandwidth fluctuation amount upper limit calculation apparatus 1 (1c) according to the third embodiment of the present invention will be described.

(Outline of processing)
First, an outline of the process according to the third embodiment will be described.
The link bandwidth fluctuation amount upper limit calculation apparatus 1 (1c) according to the third embodiment of the present invention is for increasing the calculation accuracy similar to that of the link bandwidth fluctuation amount upper limit calculation apparatus 1 (1b) according to the second embodiment. Process. The difference between the third embodiment and the second embodiment is that in the second embodiment, processing is performed until the input target acceleration level “n” and the acceleration level “k” match. I am doing so. In contrast, the link bandwidth fluctuation amount upper limit calculation device 1 (1c) according to the third embodiment has the number of variables (AC traffic bandwidth t _j ) in the variable set (Vk) selected by the variable selection unit 23. Is calculated as N (V−k), and the number of variables is compared with the number N (V− (k−1)) of variables at the previous acceleration level “k−1”. Processing is performed until the numbers match. That is, when using a calculation formula based on linear programming, if the number of variables does not change (if the number of variables does not increase), even if the processing for increasing the calculation accuracy in this embodiment is repeated, the calculation accuracy is It will not rise. Therefore, the link band fluctuation amount upper limit calculation apparatus 1 (1c) according to the third embodiment uses the number of variables (AC traffic band t _j ) at the previous speed-up level and the speed-up level being processed. When the number of variables (AC traffic band t _j ) becomes the same, the processing is terminated at the speed-up level, and calculation processing by linear programming is performed.

  By doing in this way, the link bandwidth fluctuation amount upper limit calculation apparatus 1 (1c) according to the third embodiment reduces the number of variables and the number of constraint condition expressions compared to the conventional link bandwidth fluctuation amount upper limit calculation apparatus. As a result, the upper limit value of the bandwidth fluctuation amount of each link after the path change can be calculated without further reducing the calculation accuracy.

(Configuration of link bandwidth fluctuation amount upper limit calculation processing in the third embodiment)
Next, the configuration of the link bandwidth fluctuation amount upper limit calculation apparatus 1 (1c) according to the third embodiment of the present invention will be described.
FIG. 9 is a functional block diagram showing a configuration example of the link bandwidth fluctuation amount upper limit calculation apparatus 1 (1c) according to the third embodiment of the present invention. As shown in FIG. 9, the link bandwidth fluctuation amount upper limit calculation device 1c is similar to the link bandwidth fluctuation amount upper limit calculation devices 1a and 1b shown in FIGS. 5 and 7, and the input / output unit 10, the processing unit 20, And the storage unit 30. Note that in the third embodiment, configurations having the same functions as those of the link bandwidth fluctuation amount upper limit calculation apparatuses 1a and 1b illustrated in FIGS. 5 and 7 are denoted by the same reference numerals, and description thereof is omitted.

  The input / output unit 10 in the third embodiment is, for example, from a network management device (not shown) provided in the network, like the input / output unit 10 in the first embodiment, the link band vector 100, the AC traffic route. Information regarding the matrix 200 and the post-route change AC traffic route matrix 300 is acquired. Then, the information collecting unit 21 stores these pieces of information in the storage unit 30.

  Further, the processing unit 20 in the third embodiment of the present invention does not include the acceleration level determination unit 25 as compared with the configuration of the processing unit 20 of the link bandwidth fluctuation amount upper limit calculation apparatus 1b illustrated in FIG. On the other hand, a variable number output unit 26 and a variable number determination unit 27 are provided.

The variable number output unit 26 calculates the number of variables (AC traffic band t _j ) used for the objective function (Equation 1) of the calculation formula by linear programming from the information of the AC traffic route matrix 200 stored in the storage unit 30. The number of variables is calculated and stored as N (V-0) in the variable number information 800 described later in the storage unit 30.
Further, the variable number output unit 26, when the speed-up level processing unit 24 sets the value of the speed-up level to “k”, the constraint condition expression (formula 2-k) selected by the constraint condition selection unit 22 And the number of variables (AC traffic band t _j ) is calculated, and the number of variables is stored as N (V−k) in the variable number information 800 described later in the storage unit 30.

The variable number determination unit 27 includes N ( _Vk ), which is the number of variables (AC traffic band t _j ) stored in the variable number information 800, and the variable at the previous acceleration level “k−1”. It is determined whether or not N (V− (k−1)), which is the number of That is, when the numerical value of the acceleration level “k” is “+1”, it is determined whether or not the number of variables (AC traffic band t _j ) in the calculation formula based on the linear programming increases. When the variable number determination unit 27 determines that the number of variables N (V−k) and N (V− (k−1)) do not match, the information is output to the acceleration level processing unit 24. Then, “+1” is added to the acceleration level “k” to continue the processing. On the other hand, if the variable number determination unit 27 determines that N (V−k) and N (V− (k−1)) match, even if the value of the acceleration level “k” is further increased, Since the number of variables does not change and the accuracy is not improved, the processing is terminated, and information on the speed-up level “k” is output to the link bandwidth fluctuation amount upper limit vector calculation unit 28.

The link bandwidth fluctuation amount upper limit vector calculation unit 28 in the third embodiment determines that the variable number determination unit 27 matches the number of variables N (V−k) and N (V− (k−1)). In this case, an objective function (Equation 1) that uses the AC traffic band t _j included in the variable set (Vk) selected by the variable selection unit 23 as a variable is generated as an objective function (Equation 1-k). Then, the link bandwidth fluctuation amount upper limit vector calculation unit 28 uses the generated objective function (Equation 1-k), the constraint condition equation (Equation 2-k) selected by the constraint condition selection unit 22, and the constraint condition equation (Equation 3). A link bandwidth variation upper limit vector 1000 is generated by solving a calculation formula based on linear programming.

  Further, the storage unit 30 in the third embodiment does not include the target acceleration level information 600 as compared with the configuration of the link bandwidth variation upper limit calculation device 1b illustrated in FIG. On the other hand, variable number information 800 is provided.

In the variable number information 800, the number of variables (AC traffic band t _j ) used for the objective function (Equation 1) calculated by the variable number output unit 26 is stored as N (V-0). Further, the number of variables (AC traffic band t _j ) included in the constraint condition expression (expression 2-k) selected by the constraint condition selection unit 22 and calculated by the variable number output unit 26 is stored as N (V−k). Is done.

(Link Bandwidth Fluctuation Upper Limit Calculation Processing of Third Embodiment)
Next, the flow of the link bandwidth fluctuation amount upper limit calculation process of the link bandwidth fluctuation amount upper limit calculation device 1c will be described. FIG. 10 is a flowchart showing the flow of the link bandwidth fluctuation amount upper limit calculation process according to the third embodiment of the present invention.

  First, the acceleration level processing unit 24 of the link bandwidth variation upper limit calculation device 1c initializes the acceleration level “k” stored in the acceleration level information 700 in the storage unit 30 to “0” (step S301). ).

  Next, the information collection unit 21 acquires information of the link band vector 100, the AC traffic route matrix 200, and the AC traffic route matrix 300 after the route change via the input / output unit 10 (step S302), and the storage unit 30. To remember.

Subsequently, the variable number output unit 26 uses the variable (AC traffic band t _j ) used for the objective function (Equation 1) of the calculation formula by the linear programming from the information of the AC traffic route matrix 200 stored in the storage unit 30. The number of variables is stored in the variable number information 800 in the storage unit 30 as N (V-0) (step S303).

Hereinafter, as will be described later, the number of variables (AC traffic band t _j ) stored in the variable number information 800 does not change even when the speed-up level “k” is increased, as will be described later. Repeat until.

[Acceleration level "1" processing]
First, the acceleration level processing unit 24 adds “+1” to the acceleration level “k” stored in the acceleration level information 700 in the storage unit 30 (step S304). Therefore, here, “+1” is added to the acceleration level “0” stored in the acceleration level information 700, and the acceleration level “1” is set.

となる１つ以上の交流トラヒック帯域ｔ_ｊを抽出する。続いて、制約条件選択部２２は、記憶部３０内の制約条件情報４００に記憶した制約条件式（式２）を示すリンク毎の等号条件式の中から、抽出した１以上の交流トラヒック帯域ｔ_ｊを含む等号条件式の集合を制約条件式（式２−１）として選択し、制約条件情報４００に記憶する。 Next, the constraint condition selection unit 22 performs a selection process of the constraint condition expression (formula 2-1) similar to step S102 of FIG. 6 (step S305). Specifically, the constraint condition selection unit 22 uses the link bandwidth vector 100 stored in the storage unit 30 and the AC traffic route matrix 200 before the route change to calculate a constraint condition equation (formula 2) based on linear programming. The equality conditional expression for each link indicating) is generated and stored in the constraint condition information 400 in the storage unit 30. Then, the constraint condition selection unit 22 calculates the objective function (Formula 1) of the calculation formula by the linear programming method.

One or more AC traffic bands t _j are extracted. Subsequently, the constraint condition selection unit 22 extracts one or more AC traffic bands extracted from the equality condition equation for each link indicating the constraint condition equation (Equation 2) stored in the constraint condition information 400 in the storage unit 30. A set of equality conditional expressions including t _j is selected as a constraint conditional expression (Formula 2-1) and stored in the constraint condition information 400.

In step S305, the variable selection unit 23 converts the AC traffic band t _j used in each equality conditional expression of the restriction condition expression (Expression 2-1) selected by the restriction condition selection part 22 into the restriction condition expression (Expression 2-1) is selected as a set of variables (V-1) to be used (step S306), and stored in the variable information 500 in the storage unit 30.

Subsequently, the variable number output unit 26 calculates the number of variables (AC traffic band t _j ) of the variable set (V-1) used in the constraint condition expression (Formula 2-1). The number of variables is stored as N (V-1) in the variable number information 800 (step S307).

  Next, the variable number determination unit 27 is selected based on the number N (Vk) of variables in the variable set (Vk) stored in the variable number information 800 and the previous acceleration level. It is determined whether or not the number N (V- (k-1)) of variables in the set of variables (V- (k-1)) matches (step S308). Therefore, here, the variable number determination unit 27 determines whether N (V−1), which is the number of variables stored in the variable number information 800, matches N (V−0).

  If the variable number determination unit 27 determines that N (V-1) and N (V-0) match (step S308 → Yes), the process proceeds to steps S309 to S311. The processing in steps S309 to S311 is similar to the processing in steps S104 to S106 illustrated in FIG. That is, the link bandwidth variation upper limit vector calculation unit 28 generates an objective function (Equation 1-1) using a set of variables (V-1) in Step S309, and then obtains the objective function (Equation 1-1). ), The constraint equation (Equation 2-1) selected in Step S305, and the constraint equation (Equation 3) are used to solve the calculation formula based on linear programming to generate the link bandwidth variation upper limit vector 1000 ( In step S310, the information output unit 29 outputs the information via the input / output unit 10 (step S311).

  On the other hand, if the variable number determination unit 27 determines in step S308 that N (V-1) and N (V-0) do not match (step S308 → No), the process returns to step S304.

[Acceleration level "2" processing]
Next, in step S <b> 304, the acceleration level processing unit 24 adds “+1” to the acceleration level “k” stored in the acceleration level information 700 in the storage unit 30. Therefore, here, “+1” is added to the acceleration level “1” stored in the acceleration level information 700, and the acceleration level “2” is set.

Subsequently, the constraint condition selection unit 22 is selected by the variable selection unit 23 in step S306 from the equality condition formula for each link indicating the constraint condition expression (Formula 2) stored in the constraint condition information 400. The equality conditional expression including the AC traffic band t _j used in the variable set (V-1) is selected as the constraint condition expression (Formula 2-2) (step S305) and stored in the constraint condition information 400.

Then, the variable selection unit 23 converts the AC traffic band t _j used in each equality conditional expression of the restriction condition expression (Expression 2-2) selected by the restriction condition selection part 22 in Step S305 into the restriction condition expression (Expression 2). -2) is selected as a set of variables (V-2) to be used (step S306) and stored in the variable information 500 in the storage unit 30.

Next, the variable number output unit 26 calculates the number of variables (AC traffic band t _j ) of the variable set (V-2) used in the constraint condition expression (Formula 2-2). The number of variables is stored as N (V-2) in the variable number information 800 (step S307).

  Subsequently, the variable number determination unit 27 determines whether N (V-2), which is the number of variables stored in the variable number information 800, matches N (V-1) (step S308). .

  If the variable number determination unit 27 determines that N (V−2) and N (V−1) match (step S308 → Yes), the process proceeds to step S309.

In step S309, the link bandwidth fluctuation amount upper limit vector calculation unit 28 uses the objective function (Formula 1) using the AC traffic bandwidth t _j included in the variable set (V-2) as a variable as the objective function (Formula 1-2). ). Then, the link bandwidth variation upper limit vector calculation unit 28 performs linear programming using the generated objective function (Equation 1-2), the constraint condition equation (Equation 2-2) selected in Step S305, and the constraint condition equation (Equation 3). The link bandwidth fluctuation amount upper limit vector 1000 is generated by solving the calculation formula (1) (step S310), and the information output unit 29 outputs it via the input / output unit 10 (step S311).

  On the other hand, when the variable number determination unit 27 determines in step S308 that N (V-2) and N (V-1) do not match (step S308 → No), the process returns to step S304.

In step S308, the variable number determination unit 27 repeats the processing from step S304 to S308 until it is determined that N (V−k) and N (V− (k−1)) match. A link bandwidth fluctuation amount upper limit vector 1000 is generated.
Even if the value of the acceleration level “k” is further increased after N (V−k) and N (V− (k−1)) coincide with each other, the variable (AC) Since the number of traffic bands t _j ) and the number of equality conditional expressions in the constraint condition expression (Expression 2) do not change, the calculation accuracy does not change.

By doing in this way, according to the link band fluctuation amount upper limit calculation apparatus 1 (1c) according to the third embodiment of the present invention, the number of variables (AC traffic band t _j ) used in the calculation formula by the linear programming method. The link bandwidth fluctuation amount upper limit vector 1000 can be generated without reducing the calculation accuracy after reducing the number of equality conditional expressions in the constraint condition expression (Expression 2).

≪Experimental example≫
Next, an experimental example comparing the link bandwidth fluctuation amount upper limit calculation method according to the embodiment of the present invention and the conventional link bandwidth fluctuation amount upper limit calculation method will be described.

  The experiment was performed assuming two network topologies. One is an NSF (National Science Foundation Network) shown in FIG. 11A, which is configured with a relatively small network topology having 14 nodes and 21 links. The other is COST266 (all-European network) shown in FIG. 11B, which has 26 nodes and 56 links, and is configured with a larger network topology than NSF. For these two networks, the link bandwidth fluctuation amount upper limit vector 1000 for the case where the acceleration level “k” in this embodiment is “1” to “4” and the conventional link bandwidth fluctuation amount upper limit method (conventional method). Comparing calculation time and calculation accuracy to generate Note that the left bar graph at the acceleration level k in the present embodiment represents the total processing time obtained by adding the processing time for selecting the calculation formula by the linear programming method and the processing time of the calculation formula by the linear programming method. The bar graph represents only the processing time of the calculation formula by linear programming.

  From this graph, in both cases of NFS shown in FIG. 11A and COST 266 shown in FIG. 11B, the calculation time of the link bandwidth fluctuation amount upper limit calculation method in this embodiment is shortened. I understand that. In particular, when the number of variables and the number of constraint conditions are further reduced at the acceleration level “1”, the processing speed is reduced by one-tenth or more compared to the conventional method. Further, looking at the calculation accuracy (line graph) at the high speed level “1”, the error is within 5% for NSF and within 2% for COST266. Furthermore, even when the speed-up level is set to “3” or “4”, the number of variables and the number of constraint condition expressions do not change, so the calculation accuracy does not change compared to the conventional method, and unnecessary variables and constraint conditions are not changed. It was shown that the calculation time was shortened by reducing the number of equations.

DESCRIPTION OF SYMBOLS 1 Link bandwidth variation upper limit calculation apparatus 10 Input / output part 20 Processing part 21 Information collection part 22 Restriction condition selection part 23 Variable selection part 24 Acceleration level processing part 25 Acceleration level determination part 26 Variable number output part 27 Variable number determination part 28 Link Bandwidth Variation Upper Limit Vector Calculation Unit 29 Information Output Unit 30 Storage Unit 100 Link Band Vector 200 AC Traffic Route Matrix 300 Route Changed AC Traffic Route Matrix 400 Constraint Condition Information 500 Variable Information 600 Target Acceleration Level Information 700 Acceleration Level Information 800 Number of variables information 1000 Link bandwidth fluctuation amount upper limit vector

Claims (6)

For a network comprising a plurality of nodes and a plurality of links connecting the plurality of nodes, a link bandwidth fluctuation amount upper limit calculation device for calculating an upper limit value of a bandwidth fluctuation amount of each link after a path change,
An input / output unit for transmitting and receiving information about the network;
Information regarding the network received by the input / output unit includes (1) a link band vector indicating information on the band of each link, and (2) an AC traffic path matrix indicating a path of AC traffic that is traffic between nodes. And (3) an information collecting unit that stores in a storage unit as a post-route-change AC traffic route matrix indicating a route of the AC traffic after the route is changed,
The storage unit storing the link band vector, the AC traffic route matrix, and the AC traffic matrix after the route change;
An AC traffic band t _j of the AC traffic whose path has been changed in the objective function (Equation 1) is extracted based on a calculation formula by linear programming shown below, and an equal sign including the extracted AC traffic band t _j A constraint condition selection unit that selects a set of conditional expressions as a constraint condition expression (Expression 2-1) from among expressions constituting the constraint condition expression (Expression 2);
A variable selection unit that selects the AC traffic band t _j used in each equality conditional expression represented by the constraint conditional expression (Formula 2-1) as a set of variables (V-1) used in the equality conditional expression. When,
The objective function (Equation 1) using the AC traffic band t _j included in the set of variables (V-1) as a variable is an objective function (Equation 1-1), and the objective function (Equation 1-1), The link band vector, the AC traffic path matrix, and the AC traffic path after the path change stored in the storage unit by calculation equations based on the linear programming based on the constraint condition expression (Expression 2-1) and the constraint condition expression (Expression 3) A link bandwidth fluctuation amount upper limit vector calculation unit that generates a link bandwidth fluctuation amount upper limit vector that is an upper limit value of the bandwidth fluctuation amount of each link when the path of the AC traffic is changed by solving using a matrix;
An information output unit that outputs the generated link bandwidth fluctuation amount upper limit vector via the input / output unit;
A link bandwidth fluctuation amount upper limit calculation apparatus comprising:
However, the calculation formula by the linear programming method is

The information collection unit is a target value of an acceleration level that is an index indicating an increase in the number of variables as the numerical value increases, with respect to the number of variables used in the calculation formula by the linear programming via the input / output unit. A target acceleration level n (n is a positive integer) is further acquired and stored in the storage unit,
The constraint condition selection unit
Included in the set of variables (V-1) among the expressions constituting the constraint condition expression (Expression 2) at the next speed-up level after selecting the constraint condition expression (Expression 2-1) A set of equality conditional expressions including the AC traffic band t _j to be generated is selected as a constraint conditional expression (Expression 2-2),
The variable selection unit
The AC traffic band t _j used in each equality conditional expression shown in the constraint conditional expression (Expression 2-2) is selected as a set of variables (V-2) used in the equivalent conditional expression,
The constraint condition selection unit and the variable selection unit are configured to select a set of equality conditional expressions from the constraint condition expression (Formula 2) and a selection of the set of variables from a target high speed stored in the storage unit. The constraint condition selection unit selects a constraint condition expression (Formula 2-n) by repeating up to the number of times indicated by the conversion level n, and the variable selection unit indicates the constraint condition expression (Formula 2-n). AC traffic band t _j used in each equality conditional expression is selected as a set of variables (Vn) used in the equality conditional expression,
The link bandwidth fluctuation amount upper limit vector calculation unit,
The objective function (Equation 1) using the AC traffic band t _j included in the set of variables (Vn) as a variable is an objective function (Equation 1-n), the objective function (Equation 1-n), The link band vector, the AC traffic path matrix, and the AC traffic path after the path change stored in the storage unit by a calculation formula based on the linear programming method based on the constraint condition expression (Expression 2-n) and the constraint condition expression (Expression 3). The link bandwidth fluctuation amount upper limit vector which is the upper limit value of the bandwidth fluctuation amount of each link when the path of the AC traffic is changed is generated by solving using a matrix. Link bandwidth fluctuation amount upper limit calculation device. The link bandwidth fluctuation amount upper limit calculation device further includes a variable number output unit and a variable number determination unit,
The constraint condition selection unit
Included in the set of variables (V-1) among the expressions constituting the constraint condition expression (expression 2) at the next speed-up level after selecting the constraint condition expression (expression 2-1) A set of equality conditional expressions including the AC traffic band t _j is selected as a constraint conditional expression (Expression 2-2),
The variable selection unit
The AC traffic band t _j used in each equality conditional expression shown in the constraint conditional expression (Expression 2-2) is selected as a set of variables (V-2) used in the equivalent conditional expression,
The constraint condition selection unit and the variable selection unit use selection of a set of equality conditional expressions from the constraint condition expression (Formula 2) and selection of the set of variables in a calculation formula based on the linear programming method. With respect to the number of variables, the constraint condition selection unit repeats until the number of times indicated by the speed-up level k (k is a positive integer) that is an index indicating the increase in the number of variables as the value increases. The equation (Equation 2-k) is selected, and the variable selection unit determines the AC traffic band t _j used in each equality conditional expression indicated by the constraint conditional expression (Equation 2-k) as the equality conditional expression. Select as a set of variables (Vk) used in
The variable number output unit includes:
N (Vk), which is the number of AC traffic bands t _j included in the set of variables (Vk) selected by the variable selector, is calculated;
The variable number determination unit
N (V−k) at the acceleration level k calculated by the variable number output unit and the variables calculated by the variable number output unit at the acceleration level (k−1) immediately before the acceleration level k. It is determined whether N (V− (k−1)), which is the number of AC traffic bands t _j included in the set (V− (k−1)), is the same.
The variable number determination unit determines that N (V−k) at the acceleration level k and N (V− (k−1)) at the acceleration level (k−1) are the same number. In case,
The link bandwidth fluctuation amount upper limit vector calculation unit,
The objective function (Equation 1) using the AC traffic band t _j included in the set of variables (Vk) as a variable is an objective function (Equation 1-k), the objective function (Equation 1-k), The link band vector, the AC traffic path matrix, and the AC traffic path after the path change stored in the storage unit by calculation equations based on the linear programming method using the constraint condition expression (Expression 2-k) and the constraint condition expression (Expression 3) The link bandwidth fluctuation amount upper limit vector which is the upper limit value of the bandwidth fluctuation amount of each link when the path of the AC traffic is changed is generated by solving using a matrix. Link bandwidth fluctuation amount upper limit calculation device. A link used in a link bandwidth fluctuation amount upper limit calculation device for calculating an upper limit value of a bandwidth fluctuation amount of each link after a path change for a network including a plurality of nodes and a plurality of links connecting the plurality of nodes. Bandwidth fluctuation upper limit calculation method,
The link bandwidth fluctuation amount upper limit calculation device,
An input / output unit for transmitting and receiving information about the network;
Information regarding the network received by the input / output unit includes (1) a link band vector indicating information on the band of each link, and (2) an AC traffic path matrix indicating a path of AC traffic that is traffic between nodes. And (3) a storage unit that stores the route as the AC traffic route matrix after the route change indicating the route of the AC traffic after the route change,
Obtaining information indicating the link band vector, the AC traffic route matrix, and the AC traffic matrix after the route change via the input / output unit;
An AC traffic band t _j of the AC traffic whose path has been changed in the objective function (Equation 1) is extracted based on a calculation formula by linear programming shown below, and an equal sign including the extracted AC traffic band t _j Selecting a set of conditional expressions as a constraint condition expression (Expression 2-1) from expressions constituting the constraint condition expression (Expression 2);
Selecting the AC traffic band t _j used in each equality conditional expression represented by the constraint condition expression (Expression 2-1) as a set of variables (V-1) used in the equality conditional expression;
The objective function (Equation 1) using the AC traffic band t _j included in the set of variables (V-1) as a variable is an objective function (Equation 1-1), and the objective function (Equation 1-1), The link band vector, the AC traffic path matrix, and the AC traffic path after the path change stored in the storage unit by calculation equations based on the linear programming based on the constraint condition expression (Expression 2-1) and the constraint condition expression (Expression 3) Generating a link bandwidth fluctuation amount upper limit vector that is an upper limit value of the bandwidth fluctuation amount of each link when the path of the AC traffic is changed by solving using a matrix;
Outputting the generated link bandwidth fluctuation amount upper limit vector via the input / output unit;
A link bandwidth fluctuation amount upper limit calculation method characterized in that:
However, the calculation formula by the linear programming method is

With respect to the number of variables used in the calculation formula based on the linear programming via the input / output unit, a target acceleration level n that is a target value of an acceleration level that is an index indicating an increase in the number of variables as the numerical value increases. Further acquiring (n is a positive integer) and storing it in the storage unit;
Included in the set of variables (V-1) among the expressions constituting the constraint condition expression (Expression 2) at the next speed-up level after selecting the constraint condition expression (Expression 2-1) Selecting a set of equality conditional expressions including the AC traffic band t _j to be generated as a constraint conditional expression (Expression 2-2);
Selecting the AC traffic band t _j used in each equality conditional expression represented by the constraint conditional expression (Formula 2-2) as a set of variables (V-2) used in the equality conditional expression;
The step of selecting a set of equality conditional expressions from the constraint condition expression (Expression 2) and the step of selecting the set of variables are repeated up to the number of times indicated by the target acceleration level n stored in the storage unit. By selecting the constraint condition expression (Equation 2-n), the AC traffic band t _j used in each equality conditional expression indicated by the selected constraint condition expression (Equation 2-n) Selecting as a set of variables (Vn) used in the conditional expression;
The objective function (Equation 1) using the AC traffic band t _j included in the set of variables (Vn) as a variable is an objective function (Equation 1-n), the objective function (Equation 1-n), The link band vector, the AC traffic path matrix, and the AC traffic path after the path change stored in the storage unit by a calculation formula based on the linear programming method based on the constraint condition expression (Expression 2-n) and the constraint condition expression (Expression 3). Generating a link bandwidth fluctuation amount upper limit vector that is an upper limit value of the bandwidth fluctuation amount of each link when the path of the AC traffic is changed by solving using a matrix;
The link bandwidth fluctuation amount upper limit calculation method according to claim 4, wherein: Included in the set of variables (V-1) among the expressions constituting the constraint condition expression (expression 2) at the next speed-up level after selecting the constraint condition expression (expression 2-1) Selecting a set of equality conditional expressions including an AC traffic band t _j as a constraint conditional expression (Expression 2-2);
Selecting the AC traffic band t _j used in each equality conditional expression represented by the constraint conditional expression (Formula 2-2) as a set of variables (V-2) used in the equality conditional expression;
The step of selecting a set of equality conditional expressions from the constraint condition expression (Expression 2) and the step of selecting the set of variables are related to the number of variables used in the calculation formula by the linear programming method as the numerical value increases. By repeating the number of times indicated by the acceleration level k (k is a positive integer) that is an index indicating an increase in the number of variables, a constraint condition expression (Formula 2-k) is selected, and the selected constraint condition Selecting the AC traffic band t _j used in each equality conditional expression represented by the formula (Formula 2-k) as a set of variables (Vk) used in the equality conditional expression;
Calculating a N (V-k) is the number of alternating traffic band t _j included in the set of the selected variable (V-k),
N (V−k) at the calculated acceleration level k and the set of variables (V− (k−1)) calculated at the acceleration level (k−1) immediately before the acceleration level k. ) Determining whether or not N (V− (k−1)) which is the number of AC traffic bands t _j included in
When it is determined that N (V−k) at the acceleration level k and N (V− (k−1)) at the acceleration level (k−1) are the same number,
The objective function (Equation 1) using the AC traffic band t _j included in the set of variables (Vk) as a variable is an objective function (Equation 1-k), the objective function (Equation 1-k), The link band vector, the AC traffic path matrix, and the AC traffic path after the path change stored in the storage unit by calculation equations based on the linear programming method using the constraint condition expression (Expression 2-k) and the constraint condition expression (Expression 3) Generating a link bandwidth fluctuation amount upper limit vector that is an upper limit value of the bandwidth fluctuation amount of each link when the path of the AC traffic is changed by solving using a matrix;
The link bandwidth fluctuation amount upper limit calculation method according to claim 4, wherein:

Images