JP6084583B2 - Flow path change calculation device and flow path change calculation system - Google Patents

Description

To reduce the maximum link utilization of the network, about the flow path change computing devices and flow path changing calculation system for calculating a route change of the flow.

  In a communication network, route selection when transferring a packet from a node such as a router or a switch is performed in an autonomous and distributed manner that is difficult to follow a metric set in advance for each node. In recent years, SDN (Software Defined Network) technology that can centrally manage the load status of network resources using a controller such as OpenFlow has been proposed. By adopting this technology, flexible routing control and facility operation can be realized. Maintenance cost reduction is expected. Therefore, a route control technology that realizes route optimization (load distribution) in units of “paths” determined by starting and ending points such as MPLS (Multi Protocol Label Switching) using SDN technology has been proposed (see Non-Patent Document 1). .

  In the technique (route optimization method) described in Non-Patent Document 1, the flow route is changed as a method for avoiding load concentration on a part of the network (for example, frequent packet loss and queue delay). Control is performed to reduce the maximum link utilization in the network. Here, the maximum link usage rate means the link usage rate of the link having the largest link usage rate (link traffic amount / maximum link bandwidth) of each link in the network.

  In the conventional route optimization method executed by the network control device to reduce the maximum link usage rate, a flow is defined by a pair of a destination address (destination IP address) and a source address (source IP address). Is done. Then, the flow information including all or a part of the flow (route information) and the traffic volume (flow traffic volume) in the target network and link information such as the link traffic volume are acquired, and Calculate maximum link utilization. Subsequently, when the route passing through the link having the maximum link usage rate is changed to the shortest route satisfying the following flow selection conditions (A) and (B), the flow having the minimum maximum link usage rate is selected. To do.

Flow selection condition (A): It does not pass through the link with the maximum link usage rate.
Flow selection condition (B): The maximum link usage rate of the entire network is reduced by changing the route.

  If there are a plurality of flows with the minimum maximum link usage rate, the flow is selected at random, and the process is terminated when there is no flow satisfying the flow selection conditions (A) and (B).

  A flow path change control method for reducing the conventional maximum link usage rate will be described in detail with reference to FIG.

  First, the network control device initializes a parameter (hereinafter referred to as “flow path change count”) m of a flow path change count to “0” (m = 0) (step S1).

  Next, the network control device provides topology information indicating the connection relationship between the nodes, link information, flow information including all or part of a flow path (route information) and its traffic volume (flow traffic volume) (all Alternatively, the flow information of a part of the flow is acquired (step S2). The link information includes a link metric indicating the cost (distance) of each link, the maximum bandwidth of each link, and the link traffic amount of each link. The flow information of a part of the flow means the flow information of only “the flow through the link whose link usage rate is equal to or higher than a predetermined threshold (ratio)”, and the flow information of the part of the flow is used. In addition, a flow with a small traffic amount and a small load distribution effect even when the route is changed can be excluded from the route change target in advance, and the processing time can be shortened. The flow information acquired here is flow information defined based on a destination address (destination IP address) and a source address (source IP address).

  Next, the network controller calculates the link usage rate (link traffic volume / maximum link bandwidth) of each link in the network based on the acquired link information (maximum bandwidth of each link and link traffic volume of each link). By doing so, the maximum link usage rate is calculated (step S3). By this calculation, the maximum link usage rate is calculated, and the “link having the maximum link usage rate” is specified.

  Then, the network control device sets the above flow selection condition (A) “maximum link usage” for the flow passing through the link having the maximum link usage rate in the flow information of all or some of the flows acquired in step S2. The shortest route of the route when the route is changed so as to satisfy both the flow selection condition (B) “the maximum link usage rate of the entire network is reduced by changing the route”. Then, the maximum link usage rate when the route is changed is calculated (step S4).

  Next, as a result of Step S4, the network control device determines whether or not there is a flow that satisfies both the flow selection conditions (A) and (B) and its route (Step S5). The network control device proceeds to the next step S6 when there is at least one flow that satisfies both of the flow selection conditions (A) and (B) and one or more routes (step S5 → Yes). On the other hand, if there is no flow satisfying both the flow selection conditions (A) and (B) and its route (step S5 → No), the process proceeds to step S8.

  In step S6, the network control apparatus adds “1” to the flow path change count m because there is one or more flows that can be the target of path change (m = m + 1).

Subsequently, the network control apparatus, when the flow is changed to the route among the one or more flows calculated in step S4, that is, the maximum link usage rate when each calculated flow is changed to the change destination route. The flow having the minimum value and the change destination route are extracted (step S7). As a result, in the flow path change count m (m = 1, 2,...), The flow to be changed, its change destination route, and the maximum link usage rate (and the maximum link usage rate when changing to that route) are obtained. Link) is calculated.
When there is only one combination of the extracted flow and its change destination route, the network control apparatus determines the combination of the extracted flow and the change destination route as the flow route change count m at that time (when the m-th route change). ) To be changed and the change destination route. In addition, when there are a plurality of combinations of the extracted flow and its change destination route, the network control device can change the flow to be changed and the change destination in the flow route change count m (at the m-th route change) at that time. A combination with a route is randomly determined from the plurality.

Next, the network control device returns to step S3, and (re) calculates the maximum link usage rate on the assumption that the flow determined in step S7 has been changed to the change destination route having the minimum maximum link usage rate. .
Then, the network control device performs the above-described processing in step S4 again, calculates a flow that satisfies both the flow selection conditions (A) and (B), and whether there is a flow to be changed and its route. It is determined whether or not (step S5).

In step S5, when there is no flow satisfying both of the flow selection conditions (A) and (B) and its route (step S5 → No), the network control device proceeds to step S8.
In step S8, the network control apparatus determines the flow that is the target of the path change when the flow path change count is m (m = 1, 2,...), The change destination path, and the flow path change count m (m = 1). , 2,...), And the maximum link usage rate in the route that has finally been changed.

  As described above, in the conventional flow path change control method for reducing the maximum link usage rate, all or a part of the flow paths defined by the pair of the destination address and the transmission source address ( Route information) and the flow information including the traffic volume (flow traffic volume), and after satisfying both of the flow selection conditions (A) and (B), that is, not passing through the link with the maximum link usage rate The maximum link usage rate is reduced by extracting the flow that changes the maximum link usage rate of the entire network by changing the route and the change destination route.

Ryuta Sugiyama and three others, “Examination of route optimization based on centralized control by SDN”, The Institute of Electronics, Information and Communication Engineers, 2013 IEICE Conference Proceedings, B-6-6, September 2013 3 days

  However, in the path control when the SDN technology is applied to the IP network, each node performs packet transfer based on the destination address (destination IP address). Therefore, the conventional path type, that is, the source address (source IP) In the routing control technology based on (address) and destination address (destination IP address), a plurality of output IFs (InterFace: interfaces) may be extracted for one destination address in the transfer table created at each node. There was a problem that inconsistency would occur. This will be specifically described below.

  As shown in FIG. 18, in the conventional route control, when the link between the nodes “B” and “D” is congested by a plurality of flows (in a state where the link usage rate is high), for example, the source IP address “ The route “B” → “D” of the flow defined by “p2” and the destination IP address “p4” can be changed to the route “B” → “A” → “D”. In this case, in the forwarding table (flow table) 700 (700a) of the node “A”, the output IF “2” is set in association with the transmission source address “p2” and the destination address “p4”. The transfer can be controlled without becoming.

  On the other hand, as shown in FIG. 19, when packet transfer is performed based on the destination address (destination IP address), the route of the flow via the route “B” → “D” is the same as the description with reference to FIG. Is changed from the route “B” to “A” to “D”, the node A forwarding table (flow table) 700 (700b) outputs two outputs for one destination IP address “p4”. IF “1” and “2” are set, and the route cannot be determined only by the destination address (destination IP address), that is, inconsistency occurs.

The present invention has been made in view of such a background, and when the SDN technology is applied to an IP network, the present invention enables load distribution by changing the flow path, that is, for a destination address definition flow. Te, to enable load balancing rerouting of the flow, and to provide a flow path change computing devices and flow path changing computing system.

  In order to solve the above-described problem, the invention according to claim 1 is a change destination for a change target flow among flows flowing in a network including a plurality of nodes and a plurality of links connecting the plurality of nodes. A flow path change calculation device that calculates a route, the flow route change calculation device comprising a storage unit, an input information processing unit, a maximum link usage rate calculation unit, and an output information processing unit, wherein the input The information processing unit includes (1) topology information indicating a connection relationship between the nodes, (2) a link metric indicating a cost for passing through the link, a maximum bandwidth of each link, and a link traffic amount of each link. Information, and (3) flow information including the route information of the flow defined on the basis of the destination address and the flow traffic amount thereof, and acquiring the information in the storage unit The maximum link usage rate calculation unit calculates the link usage rate of each link in the network based on the maximum bandwidth of each link and the link traffic volume of each link, and Acquire the link with the maximum link usage rate, and in the flow passing through the acquired link with the maximum link usage rate, (Condition A) Do not pass the link with the maximum link usage rate, (Condition B) Route change (Condition C) In a flow forwarding table provided in each of the plurality of nodes, a flow satisfying all of the conditions that the output IF (InterFace) is uniquely determined for each destination address is not changed. Calculate the shortest path and the maximum link utilization when changing to the shortest path, and change the flow where the maximum link utilization is the minimum value. As the target flow, the change target flow and its change destination route are determined, and the output information processing unit determines the change target flow and the change destination route thus determined, and the calculated maximum link usage rate. In the flow path change calculation device.

  By doing so, the flow path change calculation device acquires the flow path information and the flow traffic amount defined based on the destination address, and for each destination address in the flow forwarding table provided in each of the plurality of nodes. The flow to be changed and its change destination route can be calculated so that the output IF is uniquely determined, that is, the transfer table is not inconsistent in each node. Therefore, it is possible to distribute the load by changing the route of the flow for the destination address definition flow.

  According to the second aspect of the present invention, in the flow that passes through the link having the maximum link usage rate, the flow that is the target of the route change that satisfies the (condition A) and the (condition B) is changed. And a consistency check unit that checks whether or not the number of output IFs exceeding 1 is set for the same destination address in the forwarding table of each of the plurality of nodes. When at least one output IF number exceeding 1 is set among the plurality of nodes, the maximum link usage rate calculation unit determines that the output IF may not be uniquely determined, Excluding from the flow subject to path change and determining that the (condition C) is satisfied when the number of output IFs of 1 or less is set in all of the plurality of nodes. It was flow path change computing device of claim 1, symptoms.

  In this way, the flow path change calculating device uniquely outputs an output IF when there is a node that exceeds 1 for the same destination address, that is, when two or more output IFs are set in the transfer table. Since it may not be determined, the flow can be excluded from the flow whose path is changed. Therefore, the flow route change calculation device can calculate the flow to be changed and its change destination route after satisfying (Condition C).

  The invention according to claim 3 acquires a destination address for each flow that passes through the link having the maximum link usage rate, refers to route information of the flow, and determines whether a flow to the acquired destination address passes. For each node, and in the node through which the flow to the acquired destination address passes, only the link to the node that is the transfer destination of the flow of the acquired destination address is left, and the link to the other node is changed A consistency check unit that changes the topology information so as to be excluded from a link that becomes a destination route is further included, and the maximum link usage rate calculation unit refers to the changed topology information, and the (condition A) and The shortest path of a flow that satisfies the (Condition B) and a maximum link usage rate when the flow is changed to the shortest path are calculated. It was flow path change computing device.

  By doing in this way, the flow path change calculation apparatus can exclude in advance from the change destination path an IF (link) that will cause inconsistency if output from each node for each flow. Therefore, the flow path change calculation device, in each node, sets the output IF uniquely for each destination address of each flow, and then satisfies the (condition A) and (condition B) and the flow to be changed The change destination route can be calculated.

  The invention according to claim 4 is a controller connected to a plurality of nodes constituting a network, the flow path change calculation device according to claim 1 connected to the controller, the controller, and the flow path change calculation. A flow path change calculation system including a flow traffic amount calculation device connected to a device, wherein the controller is defined based on a destination address from an edge node located at a boundary of the network among the plurality of nodes. The flow traffic amount for each flow and the route information of the flow are acquired and transmitted to the flow traffic amount calculation device, and the flow traffic amount calculation device determines each edge of each flow defined based on the destination address. Uses information on the amount of flow traffic in the node and route information of each flow The flow traffic amount for each flow input to each edge node is calculated and transmitted to the flow path change calculation device, and the flow path change calculation device inputs the flow for each flow input to each edge node. The flow path change calculation system is characterized in that the flow to be changed and its change destination path are calculated using the traffic volume.

  In this way, the flow route change calculation system allows the flow traffic amount calculation device to send information on the flow traffic amount at each edge node of each flow defined based on the destination address and the route of each flow via the controller. Information can be obtained, and the amount of flow traffic for each flow input to each edge node can be calculated. Then, the flow path change calculation device can acquire the flow traffic amount for each flow input to each edge node as input information, and can calculate the flow to be changed and its change destination path. Therefore, the flow route change calculation system can perform route change control in the flow defined based on the destination address after centrally managing network information based on a technique such as SDN.

According to the present invention, when the SDN technology is applied to an IP network, load distribution by changing the flow path is possible, that is, load distribution by changing the flow path is possible for the destination address definition flow. , it is possible to provide a flow path change computing devices and flow path changing computing system.

It is a figure which shows the example of a route change (mismatch avoidance) by the route optimization which concerns on the 1st Embodiment of this invention. It is a figure which shows the structural example of the network system containing the flow path | route change calculation apparatus which concerns on the 1st Embodiment of this invention. It is a functional block diagram which shows the structural example of the flow path | route change calculation apparatus which concerns on the 1st Embodiment of this invention. It is a figure for demonstrating the inconsistency avoidance system 1 which concerns on the 1st Embodiment of this invention. It is a figure for demonstrating the inconsistency avoidance system 2 which concerns on the 1st Embodiment of this invention. It is a flowchart which shows the flow of the whole process of the flow path | route change calculation apparatus which concerns on the 1st Embodiment of this invention. It is a flowchart which shows the flow of a process of the inconsistency avoidance method 1 which concerns on the 1st Embodiment of this invention. It is a figure for demonstrating the specific example of the process of the inconsistency avoidance method 1 which concerns on the 1st Embodiment of this invention. It is a flowchart which shows the flow of a process of the inconsistency avoidance method 2 which concerns on the 1st Embodiment of this invention. It is a figure for demonstrating acquisition of the amount of flow traffic based on the transmission source address and destination address of a prior art. It is a figure for demonstrating the subject of the flow traffic amount acquisition of a prior art. It is a figure which shows the whole structure of the flow path | route change calculation system which concerns on the 2nd Embodiment of this invention. It is a functional block diagram which shows the structural example of the flow traffic amount calculation apparatus which concerns on the 2nd Embodiment of this invention. It is a figure which shows the specific example of the flow which the flow traffic amount calculation apparatus which concerns on the 2nd Embodiment of this invention calculates. It is a figure for demonstrating (Formula 2) which the flow traffic amount calculation part of the flow traffic amount calculation apparatus which concerns on the 2nd Embodiment of this invention calculates. It is a flowchart which shows the flow of a process of the flow traffic amount calculation apparatus which concerns on the 2nd Embodiment of this invention. It is a flowchart which shows the control method of the flow path change for reducing the conventional maximum link usage rate. It is a figure for demonstrating the example of a path | route change by the path | route optimization based on the conventional transmission source address and destination address. It is a figure for demonstrating the subject of the route change by the route optimization based on the conventional transmission source address and destination address.

  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 Embodiment >>
The flow path change calculation device 1 (see FIG. 2) according to the first embodiment of the present invention will be described. The flow path change calculation device 1 acquires input information including flow information defined based on a destination address as input information, and determines a flow that reduces the maximum link usage rate and its change destination path. In the first embodiment of the present invention, it is assumed that the flow information defined based on the destination address is acquired by some method using NetFlow (registered trademark) or other conventional technology.

<Overview>
First, an outline of processing executed by the flow path change calculation device 1 according to the first embodiment of the present invention will be described in comparison with a case where a conventional technique is applied.

In order to reduce the maximum link usage rate in the network, the flow route change calculation apparatus 1 according to the present embodiment performs the flow to be changed, the change destination route, the change order for changing the flow, and the route change. It is a device that calculates the maximum link utilization when it is done.
In the network control apparatus for reducing the maximum link usage rate using the conventional flow path change control technique, as described above, the flow information defined by the destination address and the source address is used as the input information. Thus, the flow to be changed and the change destination route have been determined. On the other hand, the flow route change calculation apparatus 1 according to the present embodiment uses the flow information defined only by the destination address as input information, and determines the flow to be changed and its change destination route. .

  For this reason, the flow path change calculation device 1 according to the present embodiment calculates the link usage rate of each link in the network, calculates the maximum link usage rate and the link that is the maximum link usage rate, and calculates the maximum The maximum link usage rate is obtained when a flow that satisfies the flow selection condition (C) shown below is selected in addition to the flow selection conditions (A) and (B) described above, among the flows that pass through the link that becomes the link usage rate. Select the flow that minimizes.

Flow selection condition (C): Transfer table inconsistency does not occur in each node.
This flow selection condition (C) means that “the output IF is uniquely determined for each destination address in the forwarding table of each node”.

  Then, the flow path change calculation device 1 determines which of the following [Inconsistency avoidance method 1] and [Inconsistency avoidance method 2] in order for the flow to be changed to satisfy the flow selection condition (C). This process is executed.

[Inconsistency avoidance method 1] is a method similar to that of the prior art described in Non-Patent Document 1, and it is determined that inconsistency occurs as a result of calculating the flow subject to path change and its change destination path. This is a method for excluding the flow from the target of the route change flow.
[Inconsistency avoidance method 2] is a method for calculating the change destination route by excluding IF (link) that would cause inconsistency if output from each node for each flow from the change destination route in advance. is there.
Details of [Inconsistency avoidance method 1] and [Inconsistency avoidance method 2] will be described later.

As described above, according to the flow path change calculation device 1 according to the present embodiment, even in the case of a flow defined by a destination address, as shown in FIG. When the output IF is determined by the above, it is possible to eliminate the inconsistent flow. In other words, it is possible to avoid inconsistent flows after the path change, and thus it is possible to reduce the maximum link usage rate while reducing the processing load.
FIG. 1 shows a case where the route of the flow (β) passing through the route “B” → “D” is changed from the route “B” → “C” → “D” to the node “C”. In the flow table 700c, the output IF corresponding to the destination IP address “p4” is only “3”, indicating that no inconsistency occurs.

<Network system configuration>
Next, a configuration of a network system including the flow path change calculation device 1 according to the present embodiment will be described with reference to FIG.
As shown in FIG. 2, the network system may be referred to as a communication network 4 (hereinafter simply referred to as “network”) including a plurality of nodes and links that provide communication paths by connecting the nodes. ) And a flow path change calculation device 1 that is communicably connected to each node. The flow path change calculation device 1 is configured by topology information, link information, and flow information (flow information defined by a destination address) from each node, a network management device (not shown), and the like by a predetermined method based on the prior art. Etc. Then, the flow path change calculation device 1 reduces the maximum link usage rate in the current network (communication network 4), so that the flow to be changed, its change destination path, the change order for changing the flow, and Calculate the maximum link utilization.

<Flow path change calculation device>
Next, the flow path change calculation device 1 according to this embodiment will be described. The flow path change calculation device 1 acquires, as input information, flow information (flow path information and flow traffic amount) of all or part of flows defined by a destination address, and then uses the maximum link usage rate of the network. The flow to be changed and its change destination route are calculated so as to further decrease. At this time, in addition to the above-described flow selection conditions (A) and (B), the flow path change calculation device 1 adds the flow selection condition (C) “no inconsistency in the transfer table at each node (transfer at each node). In the table, when the flow satisfying “the output IF is uniquely determined for each destination address” is selected, the flow having the minimum maximum link usage rate is selected. Thereby, the flow route change calculation device 1 can enable load distribution by changing the flow route even for a flow defined only by the destination address.

FIG. 3 is a functional block diagram illustrating a configuration example of the flow path change calculation device 1 according to the present embodiment.
As shown in FIG. 3, the flow path change calculation device 1 includes an input unit 10, a control unit 20, a memory unit 30, a storage unit 40, and an output unit 50.

The input unit 10 acquires the topology information 100, the link information 200, and the flow information 300 from a node in the communication network 4 (see FIG. 2), a network management device (not shown), and the like, and the control unit 20 (input information processing) Part 21).
Here, the topology information 100 is information indicating a connection relationship between the nodes.
The link information 200 is information including the link metric of each link, the maximum bandwidth of each link, and the amount of link traffic of each link. The link metric is information indicating the cost (distance) of each link, and is referred to when searching for the shortest path. The maximum bandwidth of the link is information indicating the maximum bandwidth that can be accommodated by each link. The amount of link traffic is the amount of traffic passing through the link at the time of measurement.
The flow information 300 stores information including the route information of all or part of the flow defined by the destination address and the traffic volume (flow traffic volume) of the flow.
The input unit 10 includes a communication interface that transmits and receives information via a communication line, and an input interface that inputs information from an input unit such as a keyboard (not shown).

  The control unit 20 controls the entire flow path change calculation apparatus 1 and includes an input information processing unit 21, a maximum link usage rate calculation unit 22, and an output information processing unit 23.

  The input information processing unit 21 acquires the topology information 100, the link information 200, and the flow information 300 via the input unit 10 and stores them in the storage unit 40.

  The maximum link usage rate calculation unit 22 reduces the maximum link usage rate in the current network (communication network 4) based on the topology information 100, the link information 200, and the flow information 300 stored in the storage unit 40. Then, the flow to be changed, the change destination route, the change order for changing the flow, and the maximum link usage rate as the processing result are calculated.

  The maximum link usage rate calculation unit 22 acquires the flow information 300 of the flow defined by the destination address, and then the flow to be changed and its change destination route so as to further reduce the maximum link usage rate of the network. Calculate At this time, the flow path change calculation apparatus 1 is a conventional flow selection condition, which is a flow selection condition (A) “does not pass through a link having the maximum link usage rate”, a flow selection condition (B) “changes the path. In addition to the above, the maximum link usage rate of the entire network is reduced. ”In addition to the flow selection condition (C), there is no inconsistency in the forwarding table at each node. The flow satisfying “uniquely determined” and the change destination route are calculated.

  The maximum link usage rate calculation unit 22 includes a consistency check unit 221 as a function for determining whether or not the flow selection condition (C) is satisfied.

  The consistency checking unit 221 performs either of the processing of [Inconsistency avoidance method 1] or [Inconsistency avoidance method 2] so that a flow that is a candidate for route change satisfies the flow selection condition (C). Run. Note that one of [Inconsistency Avoidance Method 1] and [Inconsistency Avoidance Method 2] is preset in the consistency confirmation unit 221 by a network management device (not shown) or the like.

[Inconsistency avoidance method 1] is a method similar to that of the prior art described in Non-Patent Document 1, and it is determined that inconsistency occurs as a result of calculating the flow subject to path change and its change destination path. This is a method for excluding the flow from the target of the route change flow.
For example, as shown in FIG. 4, when the link between the nodes “B” and “D” is congested by a plurality of flows (in a state where the link usage rate is high), for example, the destination IP address “p4” is defined. When the route “B” → “D” of the flow (α) to be changed from the route “B” → “A” → “D” is changed to the destination IP address “p4” in the forwarding table of the node A On the other hand, since the output IF “1” of the route to the node “C” is set, when the output IF “2” of the route to the node “D” is newly set for the destination IP address “p4” Inconsistency occurs. Therefore, the consistency confirmation unit 221 excludes the flow (α) in which such inconsistency occurs from the target of path change. Then, the route of the flow (β) that is a flow in which inconsistency does not occur is changed from the route “B” → “D” → “C” to the route “B” → “C”.

As a result, the maximum link usage rate calculation unit 22 changes the route of a flow in which inconsistency does not occur, that is, a flow that satisfies the flow selection condition (C) and satisfies the flow selection conditions (A) and (B). It can be determined as a flow.
The detailed processing contents of [Inconsistency avoidance method 1] will be described later with reference to FIGS.

[Inconsistency avoidance method 2] is a method of calculating the change destination route by excluding IF (link) that would cause inconsistency when output from each node for each flow from the change destination route in advance.
For example, as illustrated in FIG. 5, an output IF “1” that is a path toward the node “C” is already set in the node “A” for the flow of the destination IP address “p4”. Therefore, if a route other than going to the node “C” (for example, IF “2” that goes to the node “D”) is set for the same destination IP address “p4” in the node “A”. An inconsistency will inevitably occur. Consistency checking unit 221 calculates only the link (IF “1”) to node “C” that has already been set for node “A” for the flow of destination IP address “p4”. A link to another node (for example, a link to node “D”) is excluded from the change destination route.

As a result, the consistency check unit 221 excludes in advance IF (link) that would cause inconsistency when output from each node for each flow, so the maximum link usage rate calculation unit 22 generates inconsistency. A flow that does not, that is, a flow that satisfies the flow selection condition (C) and satisfies the flow selection conditions (A) and (B) can be determined as a flow whose route is to be changed.
The detailed processing content of [Inconsistency avoidance method 2] will be described later with reference to FIG.

  Returning to FIG. 3, the output information processing unit 23 calculates the flow to be changed, the change destination route, the change order for changing the flow, and the processing result calculated by the maximum link usage rate calculation unit 22. Information on the maximum link usage rate is output via the output unit 50.

  The memory unit 30 includes primary storage means such as a RAM (Random Access Memory), and temporarily stores information necessary for data processing by the control unit 20.

  The storage unit 40 includes storage means such as a hard disk and a flash memory, and stores topology information 100, link information 200, flow information 300, and the like. Note that the topology information 100, the link information 200, and the flow information 300 have been described above, and a description thereof will be omitted here.

The output unit 50 outputs the link information 400 after the flow path change and the flow information 500 after the path change, which are information of the processing result acquired from the output information processing unit 23 of the control unit 20, to output means (not shown) such as a monitor. ) Or a network management device (not shown). Here, the link information 400 after the flow path change includes information on the maximum link usage rate (and the link that becomes the maximum link usage rate) that is the final processing result. Further, the flow information 500 after the route change includes a flow that is a target of route change, a change destination route thereof, and information on a change order in which the route is changed.
The output unit 50 includes a communication interface that transmits and receives information via a communication line, and an output interface that outputs information to an output unit such as a monitor (not shown).

  When the flow path change calculation device 1 is realized by a program execution process, the storage unit 40 stores a program for realizing the function of the control unit 20 of the flow path change calculation device 1. The control unit 20 is realized by a CPU (Central Processing Unit) (not shown) expanding and executing the program stored in the storage unit 40 on a RAM or the like as the memory unit 30.

<Process flow>
Next, an overall processing flow executed by the maximum link usage rate calculation unit 22 and the like of the flow path change calculation device 1 according to the present embodiment will be described with reference to FIG. 6 (see FIG. 3 as appropriate).
FIG. 6 is a flowchart showing an overall processing flow of the flow path change calculation apparatus 1 according to the present embodiment.
Note that the storage unit 40 (see FIG. 3) of the flow path change calculation device 1 is connected to a node in the communication network 4 (see FIG. 2), a network management device (not shown), or the like via the input unit 10. The flow information 300 of all or some of the flows defined by the topology information 100, the link information 200, and the destination address is input as input information, and is stored in the storage unit 40 by the processing of the input information processing unit 21. It shall be. Also, the same processes as those in the prior art shown in FIG. 17 are denoted by the same reference numerals, and the description thereof is omitted.

  In step S20, the maximum link usage rate calculation unit 22 stores the topology information 100, the link information 200, and all or part of the flow paths stored in the storage unit 40 and indicating the connection relationship between the nodes. The flow information 300 including the flow traffic amount (flow information of all or part of flows) is acquired. Note that the flow information 300 acquired here is flow information of a flow defined based on a destination address (destination IP address).

Subsequently, in step S3, the maximum link usage rate calculation unit 22 calculates the maximum link usage rate (and “link that becomes the maximum link usage rate”).
Then, in step S40, the maximum link usage rate calculation unit 22 determines the flow described above for the flow passing through the link having the maximum link usage rate in the flow information 300 of all or some of the flows acquired in step S20. Selection condition (A) “Does not pass through link with maximum link usage rate”, Flow selection condition (B) “By changing route, maximum link usage rate of the entire network is reduced”, Flow selection condition (C) The shortest path of the path when the path is changed to satisfy all of “the inconsistency of the forwarding table in each node (the output IF is uniquely determined for each destination address in the forwarding table of each node)”; Calculate the maximum link utilization when changing to that route. The consistency confirmation unit 221 performs the process for satisfying the flow selection condition (C) by executing one of [Inconsistency avoidance method 1] and [Inconsistency avoidance method 2]. The specific processing flow of each of [Inconsistency avoidance method 1] and [Inconsistency avoidance method 2] will be described later with reference to FIGS.

  Next, in step S50, the maximum link usage rate calculation unit 22 determines whether or not a flow satisfying all the flow selection conditions (A), (B), and (C) and its route exist as a result of step S40. judge. Then, the maximum link usage rate calculation unit 22 determines whether the flow satisfying all the flow selection conditions (A), (B), and (C) and one or more paths exist (step S50 → Yes). The process proceeds to step S6. On the other hand, if there is no flow that satisfies all of the flow selection conditions (A), (B), and (C) and its route (step S50 → No), the process proceeds to step S8.

  Next, a specific processing flow of [Inconsistency Avoidance Method 1] and [Inconsistency Avoidance Method 2] executed by the consistency check unit 221 will be described.

  In [Inconsistency avoidance method 1], the flow subject to path change, which is the result calculated by the maximum link usage rate calculation unit 22 based on the flow selection conditions (A) and (B) in step S40 of FIG. The consistency checking unit 221 determines whether or not inconsistency occurs for the change destination path. Based on the determination result, the maximum link usage rate calculation unit 22 excludes the flow determined to be inconsistent from the target of the route change flow, and recalculates the flow to be changed and the change destination route. To do. This [Inconsistency avoidance method 1] will be described with reference to FIG. 7 and FIG.

  FIG. 7 is a flowchart showing the flow of the [Inconsistency Avoidance Method 1] process executed by the consistency confirmation unit 221 according to the present embodiment. FIG. 8 is a diagram for explaining a specific example of the process of [Inconsistency avoidance method 1].

  First, the consistency check unit 221 includes the topology information 100, the flow information 300 (flow path information) stored in the storage unit 40, and the maximum link usage rate calculation unit 22 in step S40 in FIG. Route information of a flow that is a target of route change, which is a result calculated based on the selection conditions (A) and (B), is acquired (step S410).

  Here, as shown in FIG. 8A, nodes “1” to “6” are connected by links (links “1” to “14”) as topology information 100 (connection relation between nodes and links). It is assumed that the topology of the network (relay network) having the above configuration has been acquired. The three flows destined for the destination IP address “10” (flows input from the nodes “1”, “2”, and “3”) include the destination IP address “10” including the flow whose path is to be changed. ”Is acquired as route information of the flow addressed to“. That is, any one of the three flows is a flow that is a target of route change, and the change destination route is included in the route of the flow illustrated in FIG.

The topology information 100 acquired by the consistency checking unit 221 is represented as a connection (coupling) matrix I = {i _{n, l} } as shown in FIG. 8B. Here, if the node n is an output point of the link l, it is _{expressed as} i _{n, l} = 1, if it is an input point, it is _{expressed as} i _{n, l} = −1, and if it is not connected, it is expressed as i _{n, l} = 0. For example, when attention is paid to the node “1”, as shown in the first line of FIG. 8B, the links “1” and “3” are the output points “1”, and the links “8” and “10”. The input point is “−1”.

Further, the flow route information is represented as a route matrix R = { _{rl, j} } as shown in FIG. Here, if the path from each input edge node j passes through the link l, r _{l, j} = 1, and if not, r _{l, j} = 0. For example, when attention is paid to the node “1” as the input edge node, as shown in the first column in FIG.

  Returning to FIG. 7, the consistency checking unit 221 next selects one node in the network (relay network). That is, the first (k = 1) node is selected from the kth nodes (k = 1,..., N) as the initial value (step S411).

Subsequently, the consistency checking unit 221 calculates the number of output IF (link) M _n at the node k = n of the corresponding flow based on (Expression 1) shown below. Then, the consistency checking unit 221 determines whether or not the value of the output IF number M _n is 1 or less (step S412). _If the value of the output IF number _Mn exceeds 1 (step S412 → No), the process proceeds to step S413. On the other hand, if the value of the output IF number _Mn is 1 or less (step S412 → Yes), the process proceeds to the next step S414.

In this (Equation 1), Σ _j max (i _{n, l} r _{l, j} , 0) indicates whether or not the flow from a certain input edge node passes through a certain link l of the node n (when it passes) "1") is to be summed over all input edge nodes. In (Expression 1), even if there are a plurality of flows output from the node n to the same link, it is determined as “1”, and when each link l of the node n is totaled, it is determined whether it is “1” or less. . Here, if the output M (link) number M _n of the node n is “0”, it indicates that no flow passes through the node n. If the value of the output IF number M _n is “1”, Indicates that one link is going to the destination address. That is, the flow of the destination address is output from one link, indicating that no inconsistency has occurred. _If the value of the output IF number M _n is “2” or more, it indicates that two or more links are directed toward the destination address. That is, it indicates that inconsistency has occurred.

In the example shown in FIG. 8A, the node “2” has a link “8” going to the node “1” and a link “4” going to the node “5”, and the number of output IFs M ₂ = 2 (See FIG. 8D). Therefore, in the forwarding table of the node “2”, two output IFs for the same destination IP address “10” are set, and inconsistency occurs. On the other hand, in the nodes “1”, “3”, “5”, and “6”, the number of output IFs M ₁ = M ₃ = M ₅ = M ₆ = 1 and there is one output IF. Does not occur (see FIG. 8D).

Returning to FIG. 7, in step S412, if the value of the output IF number _Mn exceeds 1 (step S412 → No), the consistency check unit 221 determines that the flow (target for path change) in step S413. Assuming that inconsistency occurs in (flow), the determination result is output to the maximum link usage rate calculation unit 22, and the process is terminated.

On the other hand, if the value of the output IF number _Mn is 1 or less (step S412 → Yes), the consistency check unit 221 determines whether or not all nodes N in the network (relay network) have been processed in step S414. Determine. If there is a node that has not yet been processed (step S414 → No), the consistency checking unit 221 adds 1 to k (k = k + 1) (step S415), and returns to step S412 to perform the processing. to continue. On the other hand, when the processing of all the nodes N has been completed (step S414 → Yes), the consistency checking unit 221 assumes that no inconsistency occurs in the corresponding flow in step S416, and uses the determination result as the maximum link. It outputs to the rate calculation part 22, and a process is complete | finished.

  Then, the maximum link usage rate calculation unit 22 excludes the flow determined to be inconsistent from the target of the route change flow, and recalculates the flow that is the target of the route change and the change destination route.

Next, [Inconsistency avoidance method 2] will be described.
In [Inconsistency avoidance method 2], in step S40 of FIG. 6, the consistency confirmation unit 221 outputs, in advance, an IF (link) that will cause inconsistency when output from each node for each flow from the change destination path. exclude. After that, the maximum link usage rate calculation unit 22 calculates a flow satisfying the flow selection conditions (A) and (B) and its change destination route. This [Inconsistency avoidance method 2] will be described with reference to FIG.

  FIG. 9 is a flowchart showing the flow of [Inconsistency avoidance method 2] executed by the consistency check unit 221 according to this embodiment.

  First, the consistency confirmation unit 221 acquires the topology information 100 and the flow information 300 (flow path information) stored in the storage unit 40 (step S420).

  Subsequently, in step S3 of FIG. 6, the consistency checking unit 221 selects one of the flows (flows subject to path change) passing through the link having the maximum link usage rate calculated by the maximum link usage rate calculation unit 22. And the destination address (destination IP address) is acquired (step S421).

  Next, by referring to the flow information 300 (flow path information), the consistency check unit 221 passes a flow having the same destination address (destination IP address) as the corresponding flow (flow to be changed). Is determined for each node (step S422).

  Then, when the flow of the same destination address does not pass (step S422 → No), the consistency checking unit 221 proceeds to step S424. On the other hand, when a flow with the same destination address passes (step S422 → Yes), only a link to the node that becomes the transfer destination of the flow with the same destination address as the existing flow remains in the node, and other nodes The topology information is changed so as to exclude the link going to the link as the change destination route (step S423).

  Next, in step S424, the consistency checking unit 221 determines whether or not all the flows that are the targets of path change have been processed. If there is a flow that has not yet been processed and is subject to path change (step S424 → No), the consistency checking unit 221 returns to step S421 and continues the processing. On the other hand, the consistency confirmation part 221 complete | finishes a process, when all the flow used as the object of a path | route change is processed (step S424-> Yes).

  The maximum link usage rate calculation unit 22 is the topology information changed by the consistency check unit 221 for each flow whose path is changed in step S423 of FIG. 9, that is, the flow selection condition (C) in step S40 of FIG. Using the topology information that satisfies “no inconsistency of the forwarding table at each node”, a change destination route that satisfies the flow selection conditions (A) and (B) is calculated.

By doing in this way, the flow route change calculation device 1 according to the first embodiment of the present invention uses, as input information, flow information (flow route information of all or part of flows) defined by destination addresses. And the flow traffic amount), the flow to be changed and its change destination route are calculated so as to further reduce the maximum link usage rate of the network. That is, the flow route change calculation apparatus 1 according to the present embodiment enables load distribution by changing the flow route even when the SDN technology is applied to the IP network.
Further, according to the flow path change calculation apparatus 1 according to the first embodiment of the present invention, when the number of destination addresses = the number of source addresses = n, the number of flows defined by the destination address is the source address. Since the number of flows defined by the destination address is 1 / n times, the number of flows to be changed is reduced, and as a result, the processing time of the route change calculation can be shortened.

<< Second Embodiment >>
Next, a flow path change calculation system 1000 (see FIG. 12) including the flow path change calculation apparatus 1A and the flow traffic amount calculation apparatus 5 according to the second embodiment of the present invention will be described.

  The flow route change calculation apparatus 1 according to the first embodiment has been described on the premise that the route information of the destination address definition flow and the amount of flow traffic are input as the input information based on the conventional technology. In the second embodiment of the present invention, a case will be described in which flow information and the like are acquired by applying an SDN technology that can collect network information using a controller such as OpenFlow.

<Problem of the second embodiment>
When acquiring the topology information 100, the link information 200, and the flow information 300 from each node via the controller, if the flow is defined for each flow without any problem based on the flow defined by the transmission source address and the destination address as in the prior art, Traffic volume (flow traffic volume) can be acquired. However, in the flow defined only by the destination address, there is a problem that the flow traffic amount input to the edge node cannot be directly acquired for each flow, as shown below.

  This problem will be specifically described. As shown in FIG. 10, it is assumed that the controller 6 acquires network information (here, the amount of flow traffic of each flow) from each node in the network. The controller 6 can acquire the traffic volume (flow traffic volume) in units of flows. Therefore, for flows defined based on the source address and destination address, which is a conventional general definition, the flow traffic passing between each node is obtained by acquiring the traffic volume in units of source address and destination address. The quantity can be calculated easily.

  For example, in the example shown in FIG. 10, it can be seen that the input edge node A passes the flow of the IP address “p1” → “p4” having the flow traffic amount “a” (Mbps). The input edge node B has an IP address “p1” → “p4” with a flow traffic amount “a” (Mbps) and an IP address “p2” → “p2” with a flow traffic amount “b” (Mbps). It can be seen that there are a total of three flows, the flow of “p4” and the flow of the IP address “p3” → “p4” with the flow traffic amount “c” (Mbps). These pieces of information are transmitted from each node to the controller 6.

  On the other hand, based on the flow defined only by the destination address, the traffic having the same destination address is regarded as the same flow. Therefore, the amount of flow traffic that can be acquired by the controller 6 is the traffic of flows from a plurality of source addresses. This is the total amount. Therefore, it is not possible to directly acquire the traffic amount (flow traffic amount) for each flow input to the edge node.

For example, in the example illustrated in FIG. 11, the input edge node A passes through one flow having the destination IP address “p4” having the flow traffic amount “a” (Mbps). In contrast, in the input edge node B, it can be seen that the flow of the destination IP address “p4” indicated by the total value of the flow traffic amount “a + b + c” (Mbps) passes, but the flow input in the node B The flow traffic amount “b + c” cannot be obtained directly. That is, it is not possible to directly acquire the flow traffic amount of the flow input from the edge node.
Note that information indicating the total value of the flow traffic amount “a + b + c” (Mbps) for the destination IP address “p4” in the input edge node B shown in FIG. 11 is described later, “each flow defined based on the destination address”. It shows an example of “information on the amount of flow traffic at each edge node”.

  In the second embodiment of the present invention, in order to solve the above-described problem, a flow traffic amount calculation device having a function of calculating a flow traffic amount of a flow input to each edge node for a flow of destination address definition 5 was provided. Using the flow traffic volume information input for each input edge node of each flow calculated by the flow traffic volume calculation apparatus 5, the flow path change calculation apparatus 1A according to the second embodiment may It is possible to perform path control that avoids matching flows and reduces the maximum link usage rate.

<System configuration>
Next, a flow path change calculation system 1000 including the flow path change calculation apparatus 1A and the flow traffic amount calculation apparatus 5 according to the second embodiment of the present invention will be described.
FIG. 12 is a diagram showing an overall configuration of a flow path change calculation system 1000 according to the present embodiment.
As shown in FIG. 12, a flow path change calculation system 1000 includes a controller 6 connected to each node in a network (relay network), and a flow traffic amount calculation apparatus connected to the controller 6 and the flow path change calculation apparatus 1A. 5 and a flow path change calculation device 1A connected to the controller 6 and the flow traffic amount calculation device 5.

The controller 6 is a device that acquires network information from each node and transmits control information to each node. The controller 6 is realized by, for example, a general Openflow controller. Therefore, detailed description is omitted.
The controller 6 in this embodiment includes flow information 300a (see FIG. 13) including the flow traffic amount and flow path information at each edge node of the flow defined based on the destination address, and the link traffic amount of each link. Link information 200, topology information 100, and the like are acquired. Then, the controller 6 transmits the flow information 300a to the flow traffic amount calculation device 5, and transmits other link information 200 and topology information 100 to the flow path change calculation device 1A. The controller 6 may send the flow route information to both the flow traffic amount calculation device 5 and the flow route change calculation device 1A because it is necessary for each process.

  The flow traffic amount calculation device 5 acquires the flow information 300a from the controller 6, and based on the destination address based on the information on the flow traffic amount at each edge node of each flow defined based on the destination address and the path information on each flow. The amount of flow traffic input for each input edge node of each defined flow is calculated. Then, the flow traffic amount calculation device 5 outputs the calculated flow traffic amount for each input edge node of each flow to the flow path change calculation device 1A. The detailed configuration and processing contents of the flow traffic amount calculation device 5 will be described later.

  The flow path change calculation apparatus 1A has the same functions and configurations as the flow path change calculation apparatus 1 according to the first embodiment of the present invention. Therefore, detailed description is omitted. The flow path change calculation device 1A is characterized in that the flow traffic amount information input for each input edge node of each flow defined based on the destination address is acquired from the flow traffic amount calculation device 5. The flow path change calculation device 1A has a flow to be changed based on the flow traffic amount acquired from the flow traffic amount calculation device 5 and input for each input edge node of each flow defined based on the destination address. The change destination route is calculated.

<Flow traffic volume calculation device>
Next, the flow traffic amount calculation apparatus 5 according to the second embodiment of the present invention will be described.
FIG. 13 is a functional block diagram showing a configuration example of the flow traffic amount calculation apparatus 5 according to the second embodiment of the present invention.
As shown in FIG. 13, the flow traffic amount calculation device 5 includes an input unit 51, a control unit 52, a memory unit 53, a storage unit 54, and an output unit 55.

The input unit 51 acquires the flow information 300 a from the controller 6 and passes it to the control unit 52.
Here, as described above, the flow information 300a is flow traffic amount information and route information of each flow at each edge node of each flow defined based on the destination address.
The input unit 51 includes a communication interface that transmits and receives information via a communication line, and an input interface that inputs information from an input unit such as a keyboard (not shown).

  The control unit 52 controls the entire flow traffic amount calculation device 5 and includes an input information processing unit 521, a flow traffic amount calculation unit 522, and an output information processing unit 523.

  The input information processing unit 521 acquires the flow information 300 a via the input unit 51 and passes it to the flow traffic amount calculation unit 522.

  The flow traffic amount calculation unit 522 uses the information on the flow traffic amount at each edge node of each flow defined based on the destination address and the path information of each flow included in the flow information 300a as follows (Formula 2) By solving the simultaneous equations shown below, the amount of flow traffic input for each input edge node of each flow is calculated.

Here, “f” represents a flow, “j” represents an input edge node, and “i” represents an input edge node through which the flow passes.
^"F t _j" (j = 1, ..., n) is a variable (output value), representing the amount of traffic that is input from the input edge node j of flow f (Flow traffic volume).
^f R = “ ^f r _ij ” (i, j = 1,..., n) is a constant (input value) and represents the path of the flow f. Here, when the traffic input from the edge node j of the flow f passes through the edge node i, it is represented by “1”, and when it does not pass, it is represented by “0” (see FIG. 15B).
Further, “ ^f L _i ” (i = 1,..., N) is a constant (input value) and represents the traffic amount (flow traffic amount) passing through the input edge node i of the flow f.

A specific example will be described with reference to FIG. 15, taking the network shown in FIG. 14 as an example. As shown in FIG. 14, an input edge node of a plurality of flows (hereinafter, collectively referred to as “flow (10)”) having an IP address “10” as a destination address is a node “ 1 ”,“ 2 ”,“ 3 ”,“ 4 ”,“ 5 ”, and“ 6 ”(see FIG. 15A). Here, for example, with respect to the input edge node “1”, the traffic amount (flow traffic amount) passing through the input edge node “1” of the flow (10) is represented as “ ¹⁰ L ₁ ”, and the input edge node of the flow (10) The traffic volume (flow traffic volume) input from “ ₁ ” is represented as “ ¹⁰ t ₁ ”. Also, it is assumed that there is no flow input from the nodes “7” and “8”. Therefore, in (Equation 2), calculation is performed by excluding edge nodes “7” and “8” in which there is no input flow.

Here, variables (output values) and constants (input values) in (Equation 2) are as shown in FIG.
The variable (output value) is a traffic amount “ ¹⁰ t _j ” input from each input edge node j (j = 1, 2,..., 6) of the flow (10).
The constant (input value) is the traffic amount “ ¹⁰ _Li ” at each input edge node i (i = 1, 2,..., 6) of the flow (10). Further, the route information ¹⁰ R = { ¹⁰ r _ij } of the flow (10) indicates the route matrix shown in FIG. For example, in the input edge node “2” (second column of the path matrix), the value of the input edge node “2” and the input edge node “3” through which the flow passes is “1”.

  FIG. 15C shows (Equation 2) as simultaneous equations using the above information. The flow traffic amount calculation unit 522 can obtain the flow traffic amount input for each input edge node of each flow as an output value by solving the simultaneous equations. The detailed processing flow of the flow traffic amount calculation unit 522 will be described later.

  Returning to FIG. 13, the output information processing unit 523 uses the output unit 55 to change the flow path information, which is input by each input edge node of each flow, calculated by the flow traffic amount calculation unit 522. The data is output to the calculation device 1A (see FIG. 12).

The memory unit 53 includes primary storage means such as a RAM, and temporarily stores information necessary for data processing by the control unit 52.
The storage unit 54 is configured by storage means such as a hard disk or a flash memory.

The output unit 55 outputs, to the flow path change calculation device 1A, information on the flow traffic amount input for each input edge node of each flow, which is information on the processing result acquired from the output information processing unit 523 of the control unit 52. To do.
The output unit 55 includes a communication interface that transmits and receives information via a communication line, and an output interface that outputs information to an output unit such as a monitor (not shown).

  Further, when the flow traffic amount calculation device 5 is realized by a program execution process, the storage unit 54 stores a program for realizing the function of the control unit 52 of the flow traffic amount calculation device 5. The control unit 52 is realized by a CPU (not shown) expanding and executing the program stored in the storage unit 54 on the RAM or the like that is the memory unit 53.

<Process flow>
Next, the flow of processing executed by the flow traffic amount calculation unit 522 of the flow traffic amount calculation apparatus 5 according to the second embodiment of the present invention will be described with reference to FIG. 16 (see FIG. 13 as appropriate).
FIG. 16 is a flowchart showing a process flow of the flow traffic amount calculation apparatus 5 according to the second embodiment of the present invention.

  First, the flow traffic amount calculation unit 522 of the flow traffic amount calculation device 5 receives information on the flow traffic amount at each edge node of each flow defined based on the destination address from the controller 6 via the input information processing unit 521 and Flow information 300a that is route information of each flow is acquired (step S501).

  Subsequently, the flow traffic amount calculation unit 522 selects one flow defined based on the destination address from the acquired flow information 300a (step S502).

Next, the flow traffic amount calculation unit 522 inputs the flow traffic amount information (“ ^f L _i ”) and the flow path information ( ^f R = “ ^f r _ij ”) at each edge node for the selected flow. As a value, the flow traffic amount (“ ^f t _j ”) input for each input edge node is calculated based on the above-described (Formula 2) (step S503).

  Then, the flow traffic amount calculation unit 522 determines whether or not all the flows defined based on the destination address have been processed (step S504). If there is a flow that has not yet been processed (step S504 → No), the flow traffic amount calculation unit 522 returns to step S502 and continues the processing. On the other hand, when the processes for all the flows are completed (step S504 → Yes), the process proceeds to the next step S505.

In step S505, the output information processing unit 523 of the flow traffic amount calculation apparatus 5 calculates the flow traffic amount (“ ^f t _j ”) input for each input edge node of each flow, which is the calculation result of the flow traffic amount calculation unit 522. ) Is transmitted to the flow path change calculation device 1A via the output unit 55. Then, the processing of the flow traffic amount calculation device 5 is finished.

  As described above, according to the flow path change calculation system 1000 according to the second embodiment of the present invention, the flow traffic amount calculation device 5 is obtained from the flow information defined based on the destination address acquired from the controller 6. However, it is possible to obtain the amount of flow traffic input for each input edge node of each flow. Then, using the information as input information, the flow route change calculation device 1A calculates a flow to be changed and its change destination route, and performs centralized control (centralized management) based on SDN via the controller 6. Perform route optimization processing. Therefore, it is possible to perform path control that avoids inconsistent flows after path change and reduces the maximum link usage rate.

  Further, when calculating the flow traffic amount input for each input edge node of each flow, the flow traffic amount calculation device 5 (flow traffic amount calculation unit 522), as shown in (Expression 2), the primary simultaneous system Since the equations are used, the calculation processing is simple, and the flow traffic amount calculation device 5 can be realized in a high-speed and low-spec device. In addition, when calculating (Equation 2), the flow traffic amount calculation device 5 always satisfies 1 as the number of simultaneous equation equations == the number of variables} = {the number of input edge nodes}. Can be determined.

  In the second embodiment of the present invention, the flow traffic amount calculation device 5 has been described as a single device. However, the function of the flow traffic amount calculation unit 522 provided in the flow traffic amount calculation device 5 is different from the other devices, For example, it may be configured to be incorporated in the flow path change calculation device 1A, a network management device (not shown), or the like.

1, 1A Flow path change calculation device 4 Communication network 5 Flow traffic amount calculation device 6 Controller 10, 51 Input unit 20, 52 Control unit 21, 521 Input information processing unit 22 Maximum link usage rate calculation unit 23, 523 Output information processing unit 30, 53 Memory unit 40, 54 Storage unit 50, 55 Output unit 100 Topology information 200 Link information 221 Consistency confirmation unit 300, 300a Flow information 400 Link information after flow path change 500 Flow information after path change 522 Flow traffic Quantity calculation part 700 Transfer table (flow table)
1000 Flow path change calculation system

Claims (4)

Among the flows that flow in a network that includes a plurality of nodes and a plurality of links that connect the plurality of nodes, a flow path change calculation device that calculates a change destination path for a change target flow,
The flow path change calculation device includes a storage unit, an input information processing unit, a maximum link usage rate calculation unit, and an output information processing unit,
The input information processing unit includes (1) topology information indicating a connection relationship between the nodes, (2) a link metric indicating a cost when passing through the link, a maximum bandwidth of each link, and a link traffic amount of each link. Link information including, and (3) the flow information including the flow path information and the flow traffic amount defined based on the destination address, and storing the acquired flow information in the storage unit,
The maximum link usage rate calculation unit is:
Based on the maximum bandwidth of each link and the amount of link traffic of each link, the link usage rate of each link in the network is calculated, and the link having the maximum link usage rate and the maximum link usage rate is obtained.
In the flow that passes through the link that will be the maximum link usage rate obtained,
(Condition A) Do not pass through the link with the maximum link usage rate.
(Condition B) Do not change the link with the maximum link usage rate due to the route change.
(Condition C) In the forwarding table of the flow provided in each of the plurality of nodes, an output IF (InterFace) is uniquely determined for each destination address.
Calculate the shortest path of the flow that satisfies all of the above and the maximum link usage rate when changing to the shortest path, and the flow that has the minimum value for the maximum link usage rate is the change target flow. And the change destination route,
The output information processing unit outputs the determined flow to be changed, its change destination route, and the calculated maximum link usage rate. Among the flows that pass through the link having the maximum link usage rate, when a flow that is subject to a path change that satisfies the above (Condition A) and (Condition B) is assumed to have been changed, the plurality of In the forwarding table of each node, further comprising a consistency confirmation unit for confirming whether or not the number of output IFs exceeding 1 is set for the same destination address,
The maximum link usage rate calculation unit is:
If at least one output IF number exceeding 1 is set among the plurality of nodes, the output IF may not be uniquely determined, and the flow is changed from the flow subject to the path change. Exclude
2. The flow path change calculation device according to claim 1, wherein when the number of output IFs equal to or less than 1 is set in all of the plurality of nodes, it is determined that the (condition C) is satisfied. Obtain a destination address for each flow that passes through the link that becomes the maximum link usage rate, refer to the route information of the flow, determine whether a flow to the acquired destination address passes for each node, and In the node through which the flow to the acquired destination address passes, leave only the link to the node that is the transfer destination of the flow of the acquired destination address, and exclude the link to the other node from the link that is the change destination route Further comprising a consistency checking unit for changing the topology information,
The maximum link usage rate calculation unit is:
Referring to the changed topology information, calculating the shortest path of the flow that satisfies the above (Condition A) and (Condition B) and the maximum link usage rate when changing to the shortest path,
The flow path change calculation apparatus according to claim 1, wherein: A controller connected to a plurality of nodes constituting a network, the flow path change calculation device according to claim 1 connected to the controller, and a flow traffic amount calculation connected to the controller and the flow path change calculation device A flow path change calculation system comprising a device,
The controller acquires a flow traffic amount for each flow defined based on a destination address and route information of the flow from an edge node located at a boundary of the network among the plurality of nodes, and the flow traffic is acquired. Send it to the quantity calculator,
The flow traffic amount calculation device includes:
Using the flow traffic information at each edge node of each flow defined based on the destination address and the path information of each flow, the flow traffic for each flow input to each of the edge nodes is calculated, Sent to the flow path change calculation device,
The flow path change calculation device includes:
A flow path change calculation system, wherein a flow to be changed and a change destination path thereof are calculated using a flow traffic amount for each flow input to each of the edge nodes.

Images