JP6557191B2 - Service path management apparatus and service path management method - Google Patents

Description

  The present invention relates to a service path management apparatus and a service path management method.

  Conventionally, a service chaining technology is known in which a plurality of processes such as address translation, packet filtering, firewall, parental control, etc. are transferred between a plurality of processing devices for one communication flow transferred over a network. (See, for example, Non-Patent Document 1).

  When processing a flow by the service chaining technique, a route called a service path (SP) is set between the processing devices in order to pass each processing device in the processing order determined for the flow. The bandwidth of one SP is limited by the resource amount of the processing device. The resource amount of the processing device is, for example, processing capacity represented by throughput. For this reason, when the amount of traffic that collects flows exceeds the resource amount of one processing device, a plurality of SPs are set even for the same processing. Then, the flow identification device serving as the SP entrance assigns SP to each flow. Then, the flow identification device distributes the packets of each flow to the assigned SP.

“Draft-ietf-sfc-architecture-02” [online], September 20, 2014, [search August 2, 2016], Internet (https://datatracker.ietf.org/doc/draft-ietf- sfc-architecture / 02 /)

  However, the conventional technique has a problem that the resource usage rate of the processing apparatus may be lowered. For example, if the amount of resources that can be allocated by the processing device matches the SP bandwidth, the processing device can allocate all resources to the SP. On the other hand, if the amount of resources that can be allocated by the processing device is larger than the SP bandwidth, the processing function may not be able to allocate all resources to the SP. Due to the influence of a processing apparatus that cannot allocate all resources to the SP, the overall resource usage rate may be lowered.

  The service path management apparatus of the present invention performs a predetermined process on the input flow, and outputs one process result flow, one from each of a plurality of processing apparatus groups having the same processing function. A route that passes through all of the extracted processing devices is set, an amount of the processing device resource corresponding to the bandwidth of the route is allocated to the route, and a flow received at the entrance of the route is distributed to the route and transferred. A service path management apparatus for managing a network system, for each processing function, calculating a ratio of a traffic amount input to the processing function with respect to a traffic amount of a flow received at an entrance of the route. Based on the bandwidth lower limit value calculation unit for calculating the bandwidth lower limit value, the resource amount of the processing device and the ratio, the resource amount is equal to or greater than the lower limit value. A unit resource candidate calculation unit that calculates a value that is less than or equal to the resource amount of the processing device that is small as a unit resource candidate that is a minimum unit of resource allocation, and a unit resource candidate calculated by the unit resource candidate calculation unit And a usage rate calculation unit that calculates a resource usage rate of the entire processing apparatus when selected as a unit resource, and among the unit resource candidates calculated by the unit resource candidate calculation unit, the usage rate calculation unit Based on the unit resource with the maximum resource usage rate calculated by the setting unit for setting the bandwidth of the route, and for each processing device based on the unit resource with the maximum resource usage rate and the ratio The bandwidth actually used is calculated, and the path with respect to the bandwidth of the route is calculated based on the calculated bandwidth. And having a allocation unit for allocating resources in the respective physical device.

  Also, the service path management method of the present invention performs a predetermined process on an input flow and outputs one of each of a plurality of processing devices having the same processing function among a plurality of processing functions for outputting a processing result flow. A route passing through all of the processing devices extracted one by one is set, an amount of the processing device resource corresponding to the bandwidth of the route is allocated to the route, and a flow received at the entrance of the route is distributed to the route. A service path management method executed by a service path management apparatus that manages a network system to be transferred, wherein the traffic amount input to the processing function with respect to the traffic amount of the flow received at the entrance of the route for each processing function And calculating a lower limit value of the band based on the ratio, a resource amount of the processing device, and the ratio A unit resource candidate calculation step of calculating a value that is equal to or greater than the lower limit value and equal to or less than the resource amount of the processing apparatus having the minimum resource amount as a unit resource candidate that is a minimum unit of resource allocation; For each of the unit resource candidates calculated in the resource candidate calculation step, the usage rate calculation step for calculating the resource usage rate of the entire processing apparatus when selected as a unit resource, and the unit resource candidate calculation step Of the unit resource candidates, a setting step for setting the bandwidth of the route based on the unit resource that maximizes the resource usage rate calculated by the usage rate calculating step, and a unit that maximizes the resource usage rate Based on the resource and the ratio, calculate the bandwidth actually used for each processing device, An assignment step, based on the band the calculated allocates resources in each of the processing device relative to the band of the path, characterized in that it contains.

  According to the present invention, the resource usage rate of the processing apparatus can be increased.

FIG. 1 is a diagram illustrating an example of a configuration of an entire service chaining system including a service path management apparatus according to the first embodiment. FIG. 2 is a diagram for explaining a resource allocation method using the service chaining technique. FIG. 3 is a diagram for explaining a resource allocation method using the service chaining technique. FIG. 4 is a diagram for explaining a case where the traffic volume decreases. FIG. 5 is a diagram for explaining a case where traffic is dispersed. FIG. 6 is a diagram for explaining a resource allocation method in a case where a reduction in traffic volume and traffic distribution are not taken into consideration. FIG. 7 is a diagram for explaining a resource allocation method in a case where a reduction in traffic volume and traffic distribution are not taken into consideration. FIG. 8 is a diagram for explaining a resource allocation method in a case where a reduction in traffic volume and traffic distribution are not taken into consideration. FIG. 9 is a diagram for explaining a resource allocation method in a case where a reduction in traffic volume and traffic distribution are not taken into consideration. FIG. 10 is a diagram for explaining a resource allocation method in a case where a reduction in traffic volume and traffic distribution are not taken into consideration. FIG. 11 is a diagram for explaining a resource allocation method in a case where a reduction in traffic volume and traffic distribution are not taken into consideration. FIG. 12 is a diagram for explaining a resource amount conversion method of the service path management apparatus according to the first embodiment. Figure 13 is a diagram showing the relationship between P and Qa _i in the first embodiment. FIG. 14 is a diagram for explaining a resource allocation method of the service path management apparatus according to the first embodiment. FIG. 15 is a diagram for explaining a resource allocation method of the service path management apparatus according to the first embodiment. FIG. 16 is a flowchart illustrating processing of the resource allocation unit of the service path management apparatus according to the first embodiment. FIG. 17 is a flowchart illustrating a process of calculating the resource usage rate of the resource allocation unit of the service path management apparatus according to the first embodiment. FIG. 18 is a flowchart illustrating a process of allocating resources of the resource allocation unit of the service path management apparatus according to the first embodiment. Figure 19 is a diagram showing the relationship between P and Qa _i in the second embodiment. Figure 20 is a diagram showing the relationship between P and Sa _i in the second embodiment. FIG. 21 is a diagram for explaining a method for converting the amount of resources to be allocated in the service path management apparatus according to the second embodiment. FIG. 22 is a flowchart showing the processing of the resource allocation unit of the service path management apparatus according to the second embodiment. FIG. 23 is a flowchart illustrating a process of calculating the resource usage rate of the resource allocation unit of the service path management apparatus according to the second embodiment. FIG. 24 is a flowchart illustrating a process of allocating resources of the resource allocation unit of the service path management apparatus according to the second embodiment. FIG. 25 is a flowchart illustrating a process of calculating Qb _i of the resource allocation unit of the service path management apparatus according to the second embodiment. Figure 26 is a Db resource allocation of the service path management device according to the second embodiment is a flowchart illustrating a process of converting the D _i. FIG. 27 is a diagram illustrating an example of a computer in which a service path management apparatus is realized by executing a program.

  Hereinafter, embodiments of a service path management device and a service path management method according to the present application will be described in detail with reference to the drawings. The service path management apparatus and the service path management method according to the present application are not limited by this embodiment.

[Configuration of First Embodiment]
First, a service chaining system including a service path management apparatus and a service path management apparatus according to the first embodiment will be described with reference to FIG. FIG. 1 is a diagram illustrating an example of a configuration of an entire service chaining system including a service path management apparatus according to the first embodiment.

  The service chaining system 1 in FIG. 1 performs a predetermined process on an input flow, and outputs one of each of a plurality of processing devices having the same processing function among a plurality of processing functions for outputting a processing result flow. A route passing through all of the extracted processing devices is set, an amount of processing device resources corresponding to the bandwidth of the route is allocated to the route, and the flow received at the entrance of the route is distributed to the route and transferred.

  A flow is a packet group transmitted when one terminal communicates with another one terminal, and packets having the same combination of destination address, source address, destination port number, and source port number in the packet header. Define as a group.

In the example of FIG. 1, one flow is processed by the processing functions SF ₁ , SF ₂ , and SF ₃ . The service chaining system 1 includes processing devices having processing functions SF ₁ , SF ₂ , and SF ₃ , a service path management device 10, and a flow identification device 20. As illustrated in FIG. 1, the service path management device 10 includes a traffic management unit 11, a device management unit 12, a resource allocation unit 13, and an SP setting unit 14. The resource allocation unit 13 functions as, for example, a bandwidth lower limit value calculation unit, a unit resource candidate calculation unit, and an allocation unit. The SP setting unit 14 functions as, for example, a setting unit.

  The traffic management unit 11 manages information of traffic to be processed. The device management unit 12 manages information on each processing device and the flow identification device 20. The resource allocation unit 13 calculates the bandwidth to be set for the SP from the traffic information held by the traffic management unit 11 and the processing device information held by the device management unit 12. The SP setting unit 14 sets the SP in the flow identification device 20 and each processing device according to the determination of the resource allocation unit 13, and allocates resources according to the bandwidth.

  Here, a resource allocation method using the service chaining technique will be described with reference to FIGS. 2 and 3 are diagrams for explaining a resource allocation method using the service chaining technique.

  First, an overview of the flow distribution and resource allocation processing will be described. The flow identification device 20 that has received the packet identifies the flow to which the packet belongs from the header information of the packet, assigns an SP to the flow, and stores the correspondence between the flow and the SP. When the received packet belongs to a flow to which an SP has already been assigned, the flow identification device 20 identifies the transfer destination SP from the information on the correspondence between the possessed flow and the SP, and transmits the packet to the SP.

Then, the processing device having the processing function SF ₁ processes the packet transmitted from the flow identification device 20, and performs processing of the next processing at the SP according to the setting performed by the SP setting unit 14, and processing having the processing function SF ₂ Transfer to device. Similarly, the processing device having the processing function SF ₂ processes the packet sent from the processing device having the processing function SF ₁ and performs the following processing at the SP according to the setting made by the SP setting unit 14. ₃ to the processing device having ₃ . Processing function processing apparatus having the SF _3, after performing the process, transfers the packet to the destination described in the header of the packet.

An example of the resource amount of each processing apparatus will be described with reference to FIG. As shown in FIG. 2, it is assumed that the resource amounts of the processing apparatuses having the same processing function are the same. For example, the resource amount of the processing device having the processing function SF ₁ is all R ₁ . Further, the resource amount of the processing apparatus having the processing function SF ₂ is all R ₂ . Further, the resource amount of the processing apparatus having the processing function SF ₃ is all R ₃ . Furthermore, it is assumed that the relationship of R ₁ ≦ R ₂ ≦ R ₃ is satisfied.

An example of the SP setting method will be described with reference to FIG. In the example of FIG. 3, R ₁ is the smallest among the resource amounts R ₁ , R _2, and R ₃ of each processing device. As shown in FIG. 3, when five SPs whose bandwidth is equal to R ₁ are set, all the resources of the processing apparatus having the processing function SF ₁ are used. On the other hand, some of the resources of the processing device having the processing function SF ₂ and the processing device having the processing function SF ₃ are not used. At this time, the ratio of the used resource amount to the total resource amount of each processing apparatus is the resource usage rate.

Incidentally, as shown in FIG. 4, there is a case where a packet is discarded by the processing in the SF, and the traffic amount is reduced on the SP. FIG. 4 is a diagram for explaining a case where the traffic volume decreases. In the example of FIG. 4, the traffic amount that was T is reduced to A ₂ T by the processing in the processing function SF ₁ .

Further, as shown in FIG. 5, there is a case where the SP branches and the traffic is distributed among the SFs. FIG. 5 is a diagram for explaining a case where traffic is dispersed. In the example of FIG. 5, the processing in the processing function SF _1, traffic amount of traffic was T is, traffic volume traffic and traffic volume of A _{2 T} is dispersed in the traffic A _{3 T.}

  As described above, in order to increase the resource usage rate when the traffic amount is reduced or the traffic is dispersed, the resource amount allocated to the SP for each SF is set according to the traffic amount in each SF. It is necessary.

  Here, first, a resource allocation method by the service path management apparatus 10 in the case where a reduction in traffic volume or traffic distribution is not considered will be described with reference to FIGS. Then, based on the resource allocation method demonstrated using FIGS. 6-11, the resource allocation method which considered the reduction | decrease of traffic amount and the dispersion | distribution of traffic is demonstrated. 6 to 11 are diagrams for explaining a resource allocation method in a case where a reduction in traffic volume and traffic distribution are not taken into consideration.

First, in FIG. 6, the resource amounts R ₁ , R ₂ , and R _{3 of the} processing devices having the three types of processing functions of the processing functions SF ₁ , SF ₂ , and SF ₃ are indicated by a rectangular vertical length. . Similarly, the bandwidth of the traffic to be processed is indicated by the width of the arrow. As shown in FIG. 6, first, the resource allocation unit 13 sets the resource amount of the device having the smallest resource amount as the SP band. In this case, as shown in FIG. 7, the resource allocation unit 13 sets the resource amount of the processing apparatus having the processing function SF ₁ as the band of SP ₁ . Then, the SP setting unit 14 sets SP ₁ to each processing apparatus having the processing functions SF ₁ , SF ₂ , and SF ₃ .

Next, a case where the second SP is set will be described with reference to FIG. After setting SP ₁ , since all the resources of the processing device having the processing function SF ₁ have been allocated to SP ₁ , the SP setting unit 14 sets SP ₂ to a new device having the processing function SF ₁ . Since the first resource remains for the processing devices having the processing functions SF ₂ and SF ₃ , the SP setting unit 14 sets SP ₂ as the first device.

The resource allocation unit 13 sets the resource amount of the processing device having the smallest remaining resource amount among the processing devices having the three types of processing functions as the SP ₂ band. In this case, since the resource amount of the processing device having the processing function SF ₂ is the smallest, the resource allocation unit 13 sets the remaining resource amount of the processing device having the processing function SF ₂ and the SP ₂ bandwidth to the same value. Then, the SP setting unit 14 sets SP ₂ to each processing apparatus having the processing functions SF ₁ , SF ₂ , and SF ₃ .

Next, a case where the third SP is set will be described with reference to FIG. After the SP _{2 is} set, since all the resources of the processing device having the processing function SF ₂ are allocated to the SP ₂ , the SP setting unit 14 sets SP ₃ to a new device having the processing function SF ₂ . Since the remaining second unit resources for processing apparatus having a processing function SF _1, SP setting unit 14 sets the SP ₃ to Second Appliance. In addition, since the first resource remains for the processing device having the processing function SF ₃ , the SP setting unit 14 sets SP ₃ as the first device.

The resource allocation unit 13 sets the resource amount of the processing device having the smallest remaining resource amount among the processing devices having three types of processing functions as the SP ₃ bandwidth. In this case, since the resource amount of the processing function SF ₃ is the smallest, the resource allocation unit 13 sets the remaining resource amount of the processing device having the processing function SF ₃ and the band of SP ₃ to the same value. Then, the SP setting unit 14 sets SP ₃ to each processing apparatus having the processing functions SF ₁ , SF ₂ , and SF ₃ .

Thereafter, the resource allocation unit 13 and the SP setting unit 14 repeat the same process as the process of setting SP ₁ , SP ₂ , and SP ₃ . FIG. 10 shows the result of setting all the SPs necessary for traffic processing. In the example of FIG. 10, seven SPs are set. The resource allocation unit 13 allocates resources according to the bandwidth set by the SP setting unit 14.

At this time, the resource amounts of the processing devices having the processing functions SF ₁ , SF ₂ , and SF ₃ are R ₁ , R ₂ , and R ₃ , respectively, and there is a relationship of R ₁ <R ₂ <R ₃ . Therefore, as shown in FIG. 11, the band of SP ₁ is R ₁ , the band of SP ₂ is R ₂ -R ₁ , the band of SP ₃ is R ₃ -R ₂ , the band of SP ₄ is 2R ₁ -R ₃ , The band of SP ₅ is represented as 2R ₂ −2R ₁ , the band of SP ₆ is represented as 3R ₁ −2R ₂ , and the band of SP ₇ is represented as 2R ₃ −3R ₁ .

From this, it can be seen that the bandwidth of each SP is a difference of an integral multiple of the resource amount of each processing device. Accordingly, assuming that the resource amounts of SF ₁ , SF ₂ , and SF ₃ are integer multiples of a certain resource amount P, the bandwidth of each SP is expressed as follows.

_{That, m 1, m 2, m} 3, n 1, n 2, n 3 an arbitrary _integer, when _{R 1 = Pm 1, R 2} = Pm 2, R 3 = Pm 3, band _{R 1} of SP ₁ = Pm ₁ , SP ₂ band R ₂ −R ₁ = P (m ₂ −m ₁ ), SP ₃ band R ₃ −R ₂ = P (m ₃ −m ₂ ), SP ₄ band 2 R ₁ −R ₃ = P (2m ₁ −m ₃ ), SP ₅ band 2R ₂ −2R ₁ = 2P (m ₂ −m ₁ ), SP ₆ band 3R ₁ −2R ₂ = P (3m ₁ −2m ₂ ), SP ₇ band 2R ₃ -3R ₁ = P (2m ₃ -3m ₁ ). Thus, the bandwidth of each SP is an integer multiple of P. Note that P is an example of a unit resource that is a minimum unit of resource allocation.

Generally, when the bandwidth of one SP is determined by the resource amount of a processing device having two arbitrary processing functions SF _A and SF _B among a plurality of processing devices, the resource amount R of the processing device having SF _A and SF _{B A} and R _B are represented by formula (1) and formula (2), respectively, where m _A and m _B are arbitrary positive integers.

At this time, the band B _SP of the _SP is expressed by Equation (3). Here, n _A and n _B are arbitrary positive integers satisfying R _A n _A > R _B n _B.

Furthermore, _BSP becomes Formula (4) using Formula (1) and Formula (2).

At this time, since m _A n _A −m _B n _B is a positive integer, the band B _SP of the _SP is an integer multiple of P. Therefore, the band B _SP of the _SP becomes the minimum value P when m _A n _A −m _B n _B = 1. Therefore, in order to guarantee the minimum bandwidth of SP, the value of P may be set to be equal to or greater than the guaranteed bandwidth.

  Since the value of P is determined by the resource amount of all the processing devices, it is necessary to adjust the resource amount of each processing device in order to make the value of P equal to or greater than the guaranteed bandwidth. Since the amount of resources of the processing apparatus is determined at the time of manufacture, for example, it cannot be increased. Therefore, the resource allocation unit 13 adjusts the resource amount of each processing device by reducing the resource amount actually used by each processing device. For example, the resource allocating unit 13 performs setting so that a predetermined amount of the resources of the processing device is not allocated to the SP.

At this time, the resource allocation unit 13 adjusts the value of the resource amount allocated to the SP so that the resource usage rate is maximized. Later, it represents the amount of resources the _R i of SF _i determined at the time of manufacture, the amount of resources allocated to the SP from the resource _{R i} of SF _i and _{Q i.} The subscript i is an SF identifier.

When the amount of input traffic differs between SFs due to packet discard or SP branching, first, the resource allocation unit 13 converts the resource amount of each SF so that the input traffic amount of each SF is the same. Here, the ratio of the input traffic amount of each SF to the input traffic amount to the SP is A _i (0 <A _i ≦ 1). That is, if the input traffic amount to the SP is T, the input traffic amount of SF _i is A _i T. Here, the converted value Ra _i of the resource amount R _i of SF _i is expressed by Equation (5).

A resource amount conversion method by the resource allocation unit 13 will be described with reference to FIG. FIG. 12 is a diagram for explaining a resource amount conversion method of the service path management apparatus according to the first embodiment. As shown in FIG. 12, the resource amount _{R 2} of SF _{2 are} converted to R 2 / A2.

Also, the converted value Qa _i of the resource amount Q _i allocated to the SP of SF _i is expressed by Equation (6).

Further, when the minimum value of Ra _i and _{Ra min,} converted value Ba _i of the minimum guaranteed bandwidth _{B min} becomes Equation (7).

Thus, the converted value of the minimum guaranteed bandwidth is different for each SF. On the other hand, since the SP band passes through all SFs, the upper limit value of P is Ra _min . Here, SP is due to the need to guarantee a minimum bandwidth on all SF, the lower limit of P is the maximum value of Ba _i. That is, when the maximum value of Ba _i and _{Ba max,} the range of P is the formula (8).

From the above, the relationship between P and Qa _i, can be expressed as in FIG. 13. Figure 13 is a diagram showing the relationship between P and Qa _i in the first embodiment.

As shown in FIG. 13, Qa _i repeats increase and decrease with increasing P. The reason for this will be described with reference to FIG. FIG. 14 is a diagram for explaining a resource allocation method of the service path management apparatus according to the first embodiment. For example, in FIG. 14, when P is Ba ₃ , the resource amount Ra ₂ of SF ₂ can include three Ps. When gradually increasing the P, when P = _{P b,} resource amount Qa ₂ corresponding to three of P is the same as Ra _2. At this time, all the resources of SF ₂ are allocated to the SP, and the resource usage rate becomes 100%.

When P further increases, the amount of resources for three P exceeds Ra _2, and thus the number of Ps that Ra ₂ can contain is two. In this case, the resource amount Qa ₂ assigned to the SP decreases, also decreases the resource utilization. When P further increases, the amount of resources allocated to the SP increases and the resource usage rate also increases.

Thus, with increasing P, the resource amount Qa ₂ of SF ₂ assigned to the SP repeatedly increases and decreases. Similarly, in SF ₁ and SF ₃ , the resource amounts Qa ₁ and Qa ₃ allocated to the SP as P increases are repeatedly increased and decreased. However, since the amount of resources for each SF is different, as shown in FIG. 13, P resource amount Qa _i assigned to SP becomes the maximum value depends SF.

Here, if P is in the range of formula (8), Qa _i becomes equation (9). However, floor is a function that rounds off the decimal point.

Next, a method for obtaining P that maximizes the resource usage rate will be described with reference to FIG. First, a P where Qa _i becomes the maximum value regardless of the type of SF and _{P lmx.} Here, as shown in FIG. 13, Qa ₁ , Qa ₂ , Qa as P increases in the range between adjacent P _a and P _b in P _lmx , that is, in the range of P _a <P ≦ P _{b. 3} monotonically increases, reaches a maximum in _{P b.}

From _this, between _{P lmx1, P lmx2} adjacent in the _{P lmx (P lmx1 <P lmx2} ), Qa it can be said to become a maximum at _{P lmx2.} Therefore, the resource allocation unit 13 selects the P _lmx that maximizes the resource usage rate from all the P _lmx within the range of the equation (8) as P, thereby guaranteeing the minimum SP bandwidth and the resource usage rate. Can be maximized.

Next, a method for calculating P _lmx of each SF will be described. Here, the number K of P that can be included in Ra _i is represented by Expression (10).

  Then, equation (11) is obtained from equations (9) and (10).

When P = P _lmx , Qa _i becomes a maximum value, and Qa _i = Ra _i . Therefore, Expression (12) is obtained from Expression (11).

Here, since P _max is in the range of Expression (8), the range of Ra _i / K is Expression (13).

  Therefore, K is an integer that satisfies Equation (14).

Therefore, the resource allocation unit 13 can calculate P _1mx from the equations (12) and (14).

Next, a method for calculating the resource usage rate will be described. In FIG. 13, the conversion is performed so that the input traffic amount of each SF can be regarded as the same, and the resource amount R _i is divided by a different value A _i for each SF. Therefore, when calculating the resource utilization of the entire system, performing calculations and return the converted value is divided by the A _i on the actual amount.

Here, if h is an identifier of a processing function, the traffic amount at SF _h is A _h T, and the resource amount allocated to SP is Q _h . Therefore, the number of devices N _{h at} this time is expressed by Equation (15).

Here, the device number _Nh is an integer, but is treated as a real number here, and the decimal point is not rounded up or rounded down. This eliminates the influence on the calculation of the resource usage rate due to the fractional traffic volume that is less than the resource of one device. For example, when 1.5 times the 1.5R resource amount R of traffic volume device, when two the number of devices N _h, not used since no traffic to be processed resource amount 0.5R occurs, resources Usage rate is low. The N _h is calculated as a real number in order to eliminate such effects.

Since the resource amount Z _h required for traffic processing at SF _h is the same as the traffic amount, Equation (16) is obtained.

The resource amount H _h of all the devices of SF _h including resources that are not allocated to the SP is expressed by Expression (17).

From equations (15) and (17), H _h becomes equation (18).

Here, if the number of SF types is m, the resource amount _Ztotal used by all SFs is expressed by equation (19) from equation (16).

Furthermore, the resource amount H _total of the devices of all SFs is expressed by Equation (20).

Further, from the equations (18) and (20), H _total becomes the equation (21).

Thus, the overall resource usage rate E _total is expressed by Equation (22).

  From equations (19), (21), and (22), the resource usage rate of the entire system is equation (23).

When the resource allocation unit 13 calculates the resource usage rate for P _lmx calculated from equations (12) and (14), first, Q _h for P _lmx is obtained from equations (5), (6), and (9). . Then, the resource allocation unit 13 calculates the resource usage rate of the entire system from Expression (23). When P _lmx that maximizes the resource usage rate is determined, the resource allocation unit 13 _obtains the resource amount Qa _i allocated to the SP in all the SFs from the value of P _lmx and Expression (9).

FIG. 15 shows the result of resource allocation using the converted value. FIG. 15 is a diagram for explaining a resource allocation method of the service path management apparatus according to the first embodiment. Assuming that the converted bandwidth of each SP is Da, since the bandwidth of the SP that is actually set in the SF _i device is A _i Da, the resource allocation unit 13 assigns A _i Da to the SP for each device.

Thus, the resource allocation unit 13 of the service path management apparatus 10 calculates the ratio A _i of the input traffic amount to each SF _i device with respect to the received traffic amount at the SP entrance for each processing function, and calculates the ratio A _i . Based on this, the lower limit value of the band is calculated. Then, based on the resource amount of the processing device and the ratio A _i , the resource allocation unit 13 calculates, as a candidate for P, a value that is not less than the lower limit value and not more than the resource amount of the processing device with the smallest resource amount. Then, the resource allocation unit 13 calculates the resource usage rate of the entire processing apparatus when each of the P candidates is selected as P. Then, the resource allocation unit 13 calculates a bandwidth actually used for each processing device based on P and the ratio A _i where the resource usage rate is maximum, and performs processing for the bandwidth of the route based on the calculated bandwidth. Allocate resources in each of the devices.

Specifically, the resource allocating unit 13 calculates, as a lower limit value of the bandwidth, the maximum value Ba _max among the values Ba _i obtained by dividing the bandwidth B _i predetermined as the minimum guaranteed bandwidth of the path by the ratio A _i. . Then, the resource allocating unit 13 sets the value of the processing device having a minimum resource amount Ba _max or more and a minimum resource amount among the values P _lmx obtained by dividing the resource amount Ra _i of the processing device by the ratio A _i by an integer. A value that is less than or equal to the resource amount Ra _min is calculated as a candidate for P. Then, the resource allocation unit 13 calculates the resource usage rate of the entire processing apparatus when the processing apparatus resources are allocated based on P candidates.

[Process of First Embodiment]
A process for obtaining P that maximizes the resource usage rate of the service path management apparatus will be described with reference to FIG. FIG. 16 is a flowchart illustrating processing of the resource allocation unit of the service path management apparatus according to the first embodiment. As shown in FIG. 16, first, the resource allocation unit 13 selects one processing function (step S101). Here, it is assumed that the processing function selected by the resource allocation unit 13 is SF _i .

Next, the resource allocation unit 13 obtains an integer K that satisfies the equation (101) from the resource amount Ra _i of the selected SF (step S102). Then, the resource allocation unit 13 selects one K (step S103). Next, the resource allocation unit 13 obtains P _1mx from the equation (102) for the value of K (step S104). Then, the resource allocation unit 13 calculates a resource usage rate E _total with respect to the value of P _1mx (step S105). Details of step S105 will be described later.

If there is a K for which E _total has not been calculated (No in step S106), the resource allocation unit 13 returns the process to step S103 and selects an unselected K. Further, when the E _total has been calculated for all K (step S106, Yes), the resource allocation unit 13 determines whether or not E _total has been calculated for all SFs (step S107).

At this time, if there is an SF for which E _total has not been calculated (step S107, No), the resource allocation unit 13 returns the process to step S101 and selects an unselected SF. Also, if it is already calculated the _{E total} for all SF (step S107, Yes), compares the _{E total} for all _{P lmx calculated, E total} selects the maximum _{P lmx} (step S108). Then, the resource allocation unit 13 allocates resources based on the selected P _lmx (step S109). Details of step S109 will be described later.

Next, the process for obtaining the resource usage rate of the service path management apparatus 10 (step S105 in FIG. 16) will be described using FIG. FIG. 17 is a flowchart illustrating a process of calculating the resource usage rate of the resource allocation unit of the service path management apparatus according to the first embodiment. As shown in FIG. 17, first, the resource allocation unit 13 selects one processing function (step S111). Here, it is assumed that the processing function selected by the resource allocation unit 13 is SF _h .

Next, the resource allocating unit 13 obtains a resource amount Qa _h to be allocated from SF _h to SP from the equation (103) (step S112). Here, when Qa _h has not been calculated for all the SF (step S113, No), the resource allocation unit 13 returns the process to step S111, selects the SF unselected.

Also, if the Qa _h all SF have already been calculated (step S113, Yes), the resource allocation unit 13 calculates the _{Q h} from the formula (104) from Qa _h (step S114). Then, the resource allocation unit 13 _obtains the resource usage rate E _total from the equation (105) for the value of P _1mx (step S115).

  Next, the process of assigning resources to the SP (step S109 in FIG. 16) will be described using FIG. FIG. 18 is a flowchart illustrating a process of allocating resources of the resource allocation unit of the service path management apparatus according to the first embodiment. First, it is assumed that no device is prepared in each SF as an initial state. In subsequent processing, devices are added to each SF. The addition of devices to the SF means that the number of devices used in the entire system increases. The resource allocation unit 13 allocates resources based on P that maximizes the resource usage rate so that the number of devices to be added is reduced as much as possible.

First, the resource allocation unit 13, replaces the amount of resources _{R i} of SF _i to Qa _i (step S121). Then, the resource allocation unit 13 adds a new device to the SF in which no resource remains (step S122). As described above, since no apparatus is prepared at the beginning, all SF resources are not left.

Then, the resource allocation unit 13 selects a device with the smallest remaining resource amount Wa _i (step S123). Next, when the remaining bandwidth of traffic is larger than the remaining resource amount Wa _i of the selected device (step S124, Yes), the resource allocation unit 13 sets the remaining resource amount Wa _i of the selected device as the SP bandwidth Da ( Step S125). Also, if not greater than the remaining resource amount Wa _i devices remaining bandwidth of traffic is selected (step S124, No), the resource allocation unit 13, the remaining bandwidth traffic and bandwidth Da of SP (step S126).

Here, the resource allocation unit 13 converts the determined bandwidth Da into the actual bandwidth A _i Da in each SF (step S127). Next, the resource allocation unit 13 sets the SP of the bandwidth A _i Da to the device where the resources of each SF remain (step S128). Then, the resource allocation unit 13 subtracts the SP bandwidth Da from the remaining resource amount Wa _i of each SF device (step S129). Then, the resource allocation unit 13 subtracts the SP bandwidth Da from the remaining traffic bandwidth (step S130).

  At this time, if there is no remaining traffic band (step S131, Yes), the resource allocation unit 13 ends the process. If there is a remaining traffic band (step S131, No), the resource allocation unit 13 returns the processing to step S122 and further allocates resources.

[Effect of the first embodiment]
The service path management device 10 performs predetermined processing on the input flow, and extracts one from each of a plurality of processing device groups having the same processing function among a plurality of processing functions that output a processing result flow. A network system that sets a route that passes through all of the processing devices, allocates resources of the processing device according to the bandwidth of the route to the route, and distributes and transfers the flow received at the entrance of the route to the route is managed.

The resource allocation unit 13 of the service path management apparatus 10 calculates the ratio A _i of the input traffic amount to the traffic amount of the flow received at the entrance of the route for each processing function, and sets the lower limit value of the band based on the ratio A _i. calculate. Then, based on the resource amount of the processing device and the ratio A _i , the resource allocation unit 13 calculates, as a candidate for P, a value that is not less than the lower limit value and not more than the resource amount of the processing device with the smallest resource amount. Then, the resource allocation unit 13 calculates the resource usage rate of the entire processing apparatus when each of the calculated P candidates is selected as P. Then, the SP setting unit 14 sets the bandwidth of the path based on the P candidate having the maximum resource usage rate. Then, the resource allocation unit 13 calculates a bandwidth actually used for each processing device based on P and the ratio A _i where the resource usage rate is maximum, and performs processing for the bandwidth of the route based on the calculated bandwidth. Allocate resources in each of the devices.

Thus, by performing the allocation of resources in view of the ratio A _i of the input traffic for the traffic flow received at the inlet pathways in the minimum guaranteed bandwidth and the processing unit, while ensuring the minimum guaranteed bandwidth, Since the resource usage rate of each processing device can be increased, the resource usage rate of the entire processing device can be increased.

Further, the resource allocation unit 13 may calculate the maximum value among the values obtained by dividing the bandwidth predetermined as the minimum guaranteed bandwidth of the route by the ratio A _i as the lower limit value of the bandwidth. In this case, the resource allocation unit 13 is equal to or less than the resource amount of the processing device having the minimum resource amount and the minimum resource amount among the values obtained by dividing the resource amount of the processing device by the ratio A _i by the integer. The value is calculated as a candidate for P. Then, the resource allocation unit 13 calculates the resource usage rate of the entire processing apparatus when the processing apparatus resources are allocated based on P candidates. As described above, the maximum value of the resource usage rate can be efficiently calculated by utilizing the fact that the resource usage rate also takes the maximum value when the resource amount to be allocated takes the maximum value.

[Configuration of Second Embodiment]
The basic configuration of the service path management apparatus and the service chaining system according to the second embodiment is the same as that of the first embodiment. In the service path management apparatus according to the second embodiment, the resource allocation method in the resource allocation unit 13 is different from that in the first embodiment.

In the first embodiment, for example, if the relationship between the converted values Ba ₁ and Ba ₂ of the minimum guaranteed bandwidths of SF ₁ and SF ₂ is Ba ₁ <Ba ₂ , the resource allocation unit 13 sets the minimum bandwidth for all SFs. In order to guarantee, P was selected only in the range of Ba ₂ ≦ P. This range, it was a prerequisite to protect the A _i.

In the second embodiment, by expanding the range of P, the number of options for P is increased so that the resource usage rate can be further selected. The upper limit value of P is Ra _min , and when P is larger than Ra _min , the SP bandwidth exceeds the SF resource amount, and an SF that cannot set the SP occurs. Therefore, since the upper limit value of P cannot be increased, the range of P is expanded by decreasing the lower limit value of P.

In the first embodiment, when the lower limit value of P is lowered, an SF that cannot guarantee the minimum bandwidth is generated. Therefore, in the second embodiment, the resource allocation unit 13 allocates resources to the SP as P = Ba _i for SF _i where P <Ba _i . On the other hand, the resource allocation unit 13 allocates resources for SF _i with P ≧ Ba _i by the same method as in the first embodiment.

Thus, in the second embodiment, the resource allocation unit 13 allocates resources as P = Ba _i when P <Ba _i , and therefore the resource amount Qa _i allocated to the SP is the same as when P = Ba _i. It becomes quantity. Here, an example of a relationship diagram of a P and Qa _i in FIG 19. Figure 19 is a diagram showing the relationship between P and Qa _i in the second embodiment. Further, assuming that the minimum value of Ba _i is Ba _min , when Ba _min ≦ P <Ba _i , the resource allocating unit 13 performs resource allocation with P = Ba _i , and thus Q a _i is expressed by Equation (24).

Moreover, when the Ba _i ≦ P ≦ _{Ra min,} as in the first embodiment, Qa _i becomes equation (25).

In the second embodiment, the resource allocation unit 13 allocates resources by the same method as in the first embodiment. Therefore, as shown in FIG. 15, the number of P included for each SP is the same in all SFs. Therefore, when performing resource allocation as P = Ba _i at P <Ba _i, since Ba _i is greater than the selected P, resource allocation unit 13, the SF _i as the P <Ba _i is , Resources larger than the SP bandwidth are allocated.

If P <Ba _i , even if P is the same, depending on the number of Ps included in the SP, the band in SF _i is smaller than the minimum guaranteed band and the band in SF _i is greater than or equal to the minimum guaranteed band SP occurs. Here, the minimum guaranteed bandwidth is a bandwidth required for one flow to communicate. Further, it is assumed that the input band of SP is T and the band of SF _i is A _i T.

When the SP band is smaller than the minimum guaranteed band at SF _i , the SP input band T is one flow or more and the band A _i T at SF _i is less than one flow. Since communication is performed in units of flows, there is no state of communication in less than one flow. Therefore, the SP bandwidth in SF _i is considered to indicate the flow arrival frequency. In SF _i , the flow may not arrive, but the resource allocation unit 13 allocates a resource necessary for guaranteeing the minimum bandwidth in case the flow arrives.

At this time, since the resource allocation unit 13 allocates resources with P = Ba _i to guarantee the minimum bandwidth, even if the SP bandwidth is greater than or equal to the minimum guaranteed bandwidth in SF _i , the resource allocation unit 13 allocates resources over the SP bandwidth. Become. Therefore, when calculating the resource utilization using Qa _i in FIG. 19, the resource usage is actually higher than.

Therefore, the resource allocation unit 13 uses the same value of P as other SFs even in SF _i where P <Ba _{i in} the calculation of the resource usage rate. The resource allocation unit 13 allocates resources with P = Ba _i in the range where the value of P is P <Ba _i . For this reason, the number of Ps that can be included in Ra _i is the same as when P = Ba _i .

Here, out of Ra _i , where Sa _i is the resource amount corresponding to the total of SP bands passing through the SF _i device, Sa _i is the product of the number of Ps that can be included in Ra _i and the P value. . Resource allocation unit 13 calculates the resource utilization with Sa _i. In addition, Sa _i is a value converted so that the SP bandwidth is the same for all the SFs for one SP, similarly to Q a _i . Therefore, the actual amount of Sa _{i S i} becomes equation (26).

Figure 20 shows an example of a relationship diagram of a P and Sa _i. Figure 20 is a diagram showing the relationship between P and Sa _i in the second embodiment. As shown in FIG. 20, in the range of P <Ba _i , the number of P included in Ra _i is constant, and therefore Sa _i monotonously decreases as P decreases.

Resource assignment unit 13 finds the P resource utilization is maximized from the relationship diagram of P and Sa _i shown in FIG. 20. As in the case of the first embodiment, the resource allocation unit 13 sets P _lmx to be P at which Sa _i has a maximum value. In FIG. 20, Sa ₁ , Sa ₂ , and Sa ₃ monotonously increase as P increases between adjacent P _a and P _b in P _lmx , that is, in a range of P _a <P ≦ P _b . the maximum in P _b. In _general, Sa _i is between the _{P lmx1, P lmx2} adjacent in the _{P lmx (P lmx1 <P lmx2} ) is maximized at _{P lmx2.}

Therefore, the resource allocation unit 13 selects the P _lmx that maximizes the resource usage rate from all the P _lmx within the range of the equation (27) as P, thereby guaranteeing the minimum SP bandwidth and the resource usage rate. Can be maximized.

Next, a method for calculating P _lmx of each SF will be described. In SF _i , when Ba _min ≦ P <Ba _i , the resource allocating unit 13 performs resource allocation with P = Ba _i , and thus Sa _i is expressed by Equation (28).

As shown in equation _(28), in the range of _{Ba min} ≦ P _{<Ba i,} since Sa _i is monotonically increasing with increasing P, the value of Sa _i in this range when the P = Ba _i Sa _i smaller. Therefore, P _lmx does not exist when Ba _min ≦ P <Ba _i .

In addition, when Ba _i ≦ P ≦ Ra _min , the resource allocation unit 13 performs resource allocation in the same manner as in the first embodiment, and thus Sa _i is expressed by Equation (29).

Here, the number K _i of P that can be included in Ra _i is represented by Equation (30).

  Then, Expression (31) is obtained from Expressions (29) and (30).

When P = P _lmx , Sa _i has a maximum value, and Sa _i = Ra _i . Therefore, Expression (32) is obtained from Expression (31).

Here, since P _max is in the range of Expression (27), the range of Ra _i / K _i is Expression (33).

Therefore, _Ki is an integer that satisfies the equation (34).

Therefore, the resource allocation unit 13 can calculate P _1mx from the equations (32) and (34).

Next, a method for calculating the resource usage rate will be described. In FIG. 20, as in the first embodiment, conversion is performed so that the input traffic amount of each SF can be regarded as the same, and the resource amount is divided by a different value A _i for each SF. Therefore, when calculating the resource utilization of the entire system, performing calculations and return the converted value is divided by the A _i on the actual amount. That is, Ra _i and Sa _i are converted to R _i and S _i , respectively.

Here, if the identifier of the processing capabilities of h, the amount of traffic in SF _h is _{A h} T, the amount of resources allocated to the SP regarded as _{S h.} Therefore, the number of devices N _{h at} this time is expressed by Equation (35).

Here, the device number _Nh is an integer, but is treated as a real number here for the same reason as in the first embodiment. Since the resource amount Z _h required for traffic processing at SF _h is the same as the traffic amount, Equation (36) is obtained.

The resource amount H _h of all the devices of SF _h including resources not allocated to the SP is expressed by Expression (37).

From equations (35) and (37), H _h becomes equation (38).

Here, if the number of types of SF is m, the resource amount Z _total used by all SFs is expressed by equation (39) from equation (36).

Further, the resource amount H _total of the devices of all SFs is expressed by Expression (40).

Further, from the equations (38) and (40), H _total becomes the equation (41).

Thus, the overall resource usage rate E _total is expressed by Equation (42).

  From equations (39), (41), and (42), the resource usage rate of the entire system is equation (43).

In the second embodiment, unlike the first embodiment, the resource assignment unit _13, for SF _i as the _{Ba min} ≦ P _{<Ba i,} and allocates resources as P = Ba _i. For this reason, the band of SP differs for every SF. Therefore, in order to be able to handle one SP as the same band in all the SFs, the resource allocation unit 13 converts the resource allocation amount according to the equation (44).

Here, it is assumed that P that maximizes the resource usage rate is P ₀ . At this time, the resource allocation unit 13 allocates the resource as P = Ba _{i in} SF _{i where} the resource Ba _min ≦ P ₀ <Ba _i . On the other hand, the resource allocation unit 13 allocates resources as P = P _{0 in} SF _{i where} the resource Ba _i ≦ P ₀ ≦ Ra _min .

At this time, the resource allocation unit 13 performs resource conversion by the method shown in FIG. As shown in FIG. 21, first, for example, for SF ₂ , since P ₀ <Ba ₂ , resource allocation unit 13 allocates resources as P = Ba ₂ . Then, the resource allocation unit 13 converts the resource allocation amount using Expression (44).

In this way, the resource allocation unit 13 uses the minimum value Ba _min of the device-specific minimum bandwidth Ba _i that is a value obtained by dividing the bandwidth B _i predetermined as the minimum guaranteed bandwidth of the route by the ratio A _i , Calculate as the lower limit. The resource allocating unit 13 then determines the resource amount of the processing device that is equal to or greater than the lower limit value Ba _min and has the smallest resource amount, among the values P _lmx obtained by dividing the resource amount of the processing device by the ratio A _i. A value equal to or lower than Ra _max is calculated as a candidate for P. Then, the resource allocation unit 13, of the processing unit, allocated on the basis of the resource candidate P is device-specific minimum bandwidth smaller processing apparatus to the apparatus by the minimum bandwidth Ba _i, and candidate P is device-specific minimum bandwidth over The resource usage rate of the entire processing apparatus is calculated when the resources of the processing apparatus are allocated based on P ₀ that is P.

Then, the resource allocation unit 13, of the processing device, the candidate device by the minimum bandwidth Ba _i is smaller than the processing device P is actually used in each processing unit based on the device-specific minimum bandwidth Ba _i and the ratio A _i For a processing device in which the P candidate is equal to or greater than the device-specific minimum bandwidth B a _i , the processing bandwidth is actually determined for each processing device based on P ₀ and the ratio A _i that maximize the resource usage rate. A bandwidth to be used is calculated, and resources are allocated in each processing device based on the calculated bandwidth.

[Process of Second Embodiment]
A process for obtaining P that maximizes the resource usage rate of the service path management apparatus will be described with reference to FIG. FIG. 22 is a flowchart showing the processing of the resource allocation unit of the service path management apparatus according to the second embodiment. As shown in FIG. 22, first, the resource allocation unit 13 selects one processing function (step S201). Here, it is assumed that the processing function selected by the resource allocation unit 13 is SF _i .

Next, the resource allocation unit 13 obtains an integer K _i that satisfies Expression (201) from the resource amount Ra _i of the selected SF (step S202). Then, the resource allocation unit 13 selects one _{K i} (step S203). Next, the resource allocation unit 13 obtains P _1mx from the equation (202) with respect to the value of K _i (step S204). Then, the resource allocation unit 13 calculates a resource usage rate E _total with respect to the value of P _1mx (step S205). Details of step S205 will be described later.

If there is a K _{i for} which E _total has not been calculated (step S206, No), the resource allocation unit 13 returns the process to step S203, and selects an unselected K _i . Further, when the E _total has been calculated for all K _i (step S206, Yes), the resource allocation unit 13 determines whether the E _total has been calculated for all SFs (step S207).

At this time, when there is an SF for which E _total has not been calculated (No at Step S207), the resource allocation unit 13 returns the process to Step S201 and selects an unselected SF. Also, if it is already calculated the _{E total} for all SF (step S207, Yes), compares the _{E total} for all _{P lmx calculated, E total} selects the maximum _{P lmx} (step S208). Then, the resource allocation unit 13 allocates resources based on the selected P _lmx (step S209). Details of step S209 will be described later.

Next, the process for obtaining the resource usage rate of the service path management apparatus 10 (step S205 in FIG. 22) will be described with reference to FIG. FIG. 23 is a flowchart illustrating a process of calculating the resource usage rate of the resource allocation unit of the service path management apparatus according to the second embodiment. As shown in FIG. 23, first, the resource allocation unit 13 selects one processing function (step S211). Here, it is assumed that the processing function selected by the resource allocation unit 13 is SF _h . Then, the resource allocation unit 13 determines whether or not the selected P _1mx satisfies Ba _h ≦ P _1mx ≦ Ra _min (step S212).

Here, when P _1mx satisfies Ba _h ≦ P _1mx ≦ Ra _min (step S212, Yes), the resource allocation unit 13 obtains the resource amount Sa _h to be allocated from SF _h to SP from the equation (203) (step S213). ). On the other hand, when P _1mx does not satisfy Ba _h ≦ P _1mx ≦ Ra _min (step S212, No), the resource allocation unit 13 obtains the resource amount Sa _h to be allocated from SF _h to SP based on the equation (204) (step S214). ). Here, when not all SFs have been selected (No at Step S215), the resource allocation unit 13 returns the process to Step S211 and selects an unselected SF.

Also, if it is selected all the SF (step S215, Yes), the resource allocation unit 13 calculates the _{S h} from the formula (205) from Sa _h (step S216). Then, the resource allocation unit 13 _obtains the resource usage rate E _total from the equation (206) with respect to the value of P _1mx (step S217).

  Next, the process of assigning resources to the SP (step S209 in FIG. 22) will be described using FIG. FIG. 24 is a flowchart illustrating a process of allocating resources of the resource allocation unit of the service path management apparatus according to the second embodiment. First, it is assumed that no device is prepared in each SF as an initial state. In subsequent processing, devices are added to each SF. The addition of devices to the SF means that the number of devices used in the entire system increases. The resource allocation unit 13 allocates resources based on P that maximizes the resource usage rate so that the number of devices to be added is reduced as much as possible.

First, the resource allocation unit 13 calculates Qb _i of SF _{i and} sets Qb _i as the resource amount of SF _i (step S221). Details of step S221 will be described later. Then, the resource allocation unit 13 adds a new device to the SF in which no resource remains (step S222). As described above, since no apparatus is prepared at the beginning, all SF resources are not left.

Then, the resource allocation unit 13 selects a device with the smallest remaining resource amount Wb _i (step S223). Next, when the remaining bandwidth of traffic is larger than the remaining resource amount Wb _i of the selected device (step S224, Yes), the resource allocation unit 13 sets the remaining resource amount Wb _i of the selected device as the SP bandwidth Db ( Step S225). If the remaining traffic band is not greater than the remaining resource amount Wb _i of the selected device (step S224, No), the resource allocation unit 13 sets the remaining traffic band as the SP band Db (step S226).

Here, the resource allocation unit 13, the determined band Db converted into actual bandwidth _{D i} for each SF (step S227). Details of step S227 will be described later. Next, the resource allocation unit 13, the apparatus remaining resources of each SF, sets the SP band _{D i} (step S228). Then, the resource allocation unit 13 subtracts the SP bandwidth Db from the remaining resource amount Wb _i of each SF device (step S229). Then, the resource allocation unit 13 subtracts the SP bandwidth Db from the remaining traffic bandwidth (step S230).

  At this time, if there is no remaining traffic band (step S231, Yes), the resource allocation unit 13 ends the process. If there is a remaining traffic band (step S231, No), the resource allocation unit 13 returns the process to step S222 and further allocates resources.

Next, the process (step S221 in FIG. 24) for calculating Qb _i of the service path management apparatus 10 will be described with reference to FIG. FIG. 25 is a flowchart illustrating a process of calculating Qb _i of the resource allocation unit of the service path management apparatus according to the second embodiment. As shown in FIG. 25, first, the resource allocation unit 13 selects one processing function (step S241). Here, it is assumed that the processing function selected by the resource allocation unit 13 is SF _i . At this time, the selected P _1mx is _set as P ₀ . Then, the resource allocation unit 13 determines whether _{P 0} satisfies the _{Ba min ≦ P 0 <Ba i} ( step S242).

When P ₀ satisfies Ba _min ≦ P ₀ <Ba _i (step S242, Yes), the resource allocation unit 13 calculates Qa _i from equation (207) (step S243). Then, the resource allocation unit 13 calculates Qb _i from the equation (208) (step S244).

On the other hand, _{if P 0} does not satisfy the _{Ba min ≦ P 0 <Ba i} ( step S242, No), the resource allocation unit 13 calculates the Qa _i from equation (209) (step S245). Then, the resource allocation unit 13 calculates Qb _i from the equation (210) (step S246). Here, when not all SFs have been selected (No at Step S247), the resource allocation unit 13 returns the process to Step S241 and selects an unselected SF. Further, when all the SFs have been selected (step S247, Yes), the resource allocation unit 13 ends the process.

Next, with reference to FIG. 26, a description will be given of a process for converting the Db of the service path management device 10 to _{D i} (step S227 in FIG. 24). Figure 26 is a Db resource allocation of the service path management device according to the second embodiment is a flowchart illustrating a process of converting the D _i. As shown in FIG. 26, first, the resource allocation unit 13 selects one processing function (step S251). Here, it is assumed that the processing function selected by the resource allocation unit 13 is SF _i . At this time, the selected P _1mx is _set as P ₀ . Then, the resource allocation unit 13 determines whether _{P 0} satisfies the _{Ba min ≦ P 0 <Ba i} ( step S252).

If P ₀ satisfies _{Ba min ≦ P 0 <Ba i} ( step S252, Yes), the resource allocation unit 13 calculates the Da _i from equation (211) (step S253). On the other hand, _{if P 0} does not satisfy the _{Ba min ≦ P 0 <Ba i} ( step S252, No), the resource allocation unit 13 calculates the Da _i from equation (212) (step S254). Then, the resource allocation unit 13 calculates a _{D i} from the equation (213) (step S255). Here, when not all SFs have been selected (step S256, No), the resource allocation unit 13 returns the process to step S251 and selects an unselected SF. If all the SFs have been selected (step S256, Yes), the resource allocation unit 13 ends the process.

[Effects of Second Embodiment]
Further, the resource allocation unit 13 may calculate the minimum value of the device-specific minimum bandwidths, which is a value obtained by dividing the bandwidth predetermined as the minimum guaranteed bandwidth of the route by the ratio _Ai , as the bandwidth lower limit value. . In this case, the resource allocation unit 13 is equal to or less than the resource amount of the processing device having the minimum resource amount and the minimum resource amount among the values obtained by dividing the resource amount of the processing device by the ratio A _i by the integer. The value is calculated as a candidate for P. Then, the resource allocating unit 13 allocates resources of the processing devices in which the P candidate is smaller than the device-specific minimum bandwidth among the processing devices based on the device-specific minimum bandwidth, and the P candidate is equal to or greater than the device-specific minimum bandwidth. The resource usage rate of the entire processing device when the processing device resources are allocated based on P candidates is calculated. Further, the resource allocation unit 13 determines the bandwidth actually used for each processing device based on the minimum bandwidth for each device and the ratio A _i for processing devices whose P candidates are smaller than the minimum bandwidth for each device. For a processing device in which the P candidate is equal to or greater than the minimum bandwidth for each device, the bandwidth actually used for each processing device is calculated based on P and the ratio A _i where the resource usage rate is maximum, and the calculation is performed. Resource allocation in each of the processing devices may be performed based on the determined bandwidth. Thereby, according to each processing function, the amount of resources used for one SP can be set more wastefully, and the resource usage rate can be further reduced.

[System configuration, etc.]
Further, each component of each illustrated apparatus is functionally conceptual, and does not necessarily need to be physically configured as illustrated. In other words, the specific form of distribution / integration of each device is not limited to that shown in the figure, and all or a part thereof may be functionally or physically distributed or arbitrarily distributed in arbitrary units according to various loads or usage conditions. Can be integrated and configured. Furthermore, all or a part of each processing function performed in each device may be realized by a CPU and a program that is analyzed and executed by the CPU, or may be realized as hardware by wired logic.

  Also, among the processes described in this embodiment, all or part of the processes described as being performed automatically can be performed manually, or the processes described as being performed manually can be performed. All or a part can be automatically performed by a known method. In addition, the processing procedure, control procedure, specific name, and information including various data and parameters shown in the above-described document and drawings can be arbitrarily changed unless otherwise specified.

[program]
As an embodiment, the service path management apparatus 10 can be implemented by installing a service path management program for executing the above service path management as package software or online software on a desired computer. For example, the information processing apparatus can function as the service path management apparatus 10 by causing the information processing apparatus to execute the service path management program. The information processing apparatus referred to here includes a desktop or notebook personal computer. In addition, the information processing apparatus includes mobile communication terminals such as smart phones, mobile phones and PHS (Personal Handy phone System), and slate terminals such as PDA (Personal Digital Assistant). .

  The service path management apparatus 10 can also be implemented as a service path management server apparatus that uses a terminal device used by a user as a client and provides the client with the above-described service path management service. For example, the service path management server device is implemented as a server device that provides a service path management service that receives the information of each device on the network that performs the service and outputs the resource allocation method for each SP for each device. Is done. In this case, the service path management server device may be implemented as a Web server, or may be implemented as a cloud that provides services related to the service path management described above by outsourcing.

  FIG. 27 is a diagram illustrating an example of a computer in which a service path management apparatus is realized by executing a program. The computer 1000 includes a memory 1010 and a CPU 1020, for example. The computer 1000 also includes a hard disk drive interface 1030, a disk drive interface 1040, a serial port interface 1050, a video adapter 1060, and a network interface 1070. These units are connected by a bus 1080.

  The memory 1010 includes a ROM (Read Only Memory) 1011 and a RAM 1012. The ROM 1011 stores a boot program such as BIOS (Basic Input Output System). The hard disk drive interface 1030 is connected to the hard disk drive 1090. The disk drive interface 1040 is connected to the disk drive 1100. For example, a removable storage medium such as a magnetic disk or an optical disk is inserted into the disk drive 1100. The serial port interface 1050 is connected to a mouse 1110 and a keyboard 1120, for example. The video adapter 1060 is connected to the display 1130, for example.

  The hard disk drive 1090 stores, for example, an OS 1091, an application program 1092, a program module 1093, and program data 1094. That is, a program that defines each process of the service path management apparatus 10 is implemented as a program module 1093 in which a code executable by a computer is described. The program module 1093 is stored in the hard disk drive 1090, for example. For example, a program module 1093 for executing processing similar to the functional configuration in the service path management apparatus 10 is stored in the hard disk drive 1090. Note that the hard disk drive 1090 may be replaced by an SSD.

  The setting data used in the processing of the above-described embodiment is stored as program data 1094 in, for example, the memory 1010 or the hard disk drive 1090. Then, the CPU 1020 reads the program module 1093 and the program data 1094 stored in the memory 1010 and the hard disk drive 1090 to the RAM 1012 and executes them as necessary.

  The program module 1093 and the program data 1094 are not limited to being stored in the hard disk drive 1090, but may be stored in, for example, a removable storage medium and read out by the CPU 1020 via the disk drive 1100 or the like. Alternatively, the program module 1093 and the program data 1094 may be stored in another computer connected via a network (LAN (Local Area Network), WAN (Wide Area Network), etc.). The program module 1093 and the program data 1094 may be read by the CPU 1020 from another computer via the network interface 1070.

DESCRIPTION OF SYMBOLS 1 Service chaining system 10 Service path management apparatus 20 Flow identification apparatus 11 Traffic management part 12 Device management part 13 Resource allocation part 14 SP setting part

Claims (5)

Among a plurality of processing functions that perform predetermined processing on the input flow and output a processing result flow, all of the processing devices extracted one by one from each of a plurality of processing device groups having the same processing function are passed through. Service path management device for managing a network system that sets a route, allocates resources of the processing device according to the bandwidth of the route to the route, and distributes and transfers flows received at the route entrance to the route Because
For each of the processing functions, a bandwidth lower limit value calculation unit that calculates a ratio of the traffic amount input to the processing function to the traffic amount of the flow received at the entrance of the route and calculates a lower limit value of the bandwidth based on the ratio. When,
Based on the resource amount of the processing device and the ratio, a value that is greater than or equal to the lower limit value and less than or equal to the resource amount of the processing device that has the smallest resource amount is calculated as a candidate for a unit resource that is the minimum unit of resource allocation A unit resource candidate calculation unit;
For each of the unit resource candidates calculated by the unit resource candidate calculation unit, a usage rate calculation unit that calculates a resource usage rate of the entire processing apparatus when selected as a unit resource;
A setting unit configured to set a bandwidth of the route based on a unit resource having the maximum resource usage rate calculated by the usage rate calculation unit among the unit resource candidates calculated by the unit resource candidate calculation unit; ,
Based on the unit resource that maximizes the resource usage rate and the ratio, the bandwidth that is actually used for each processing device is calculated, and based on the calculated bandwidth, the bandwidth of the route in each of the processing devices is calculated. An allocation unit that allocates resources;
A service path management apparatus comprising: The bandwidth lower limit value calculation unit calculates a maximum value among values obtained by dividing a bandwidth predetermined as a minimum guaranteed bandwidth of the route by the ratio, as a bandwidth lower limit value,
The unit resource candidate calculation unit is equal to or less than the resource amount of the processing device that is equal to or greater than the lower limit value and has the smallest resource amount among the values obtained by dividing the resource amount of the processing device by the ratio by an integer. Calculate the value as a candidate for the unit resource,
2. The service path management according to claim 1, wherein the usage rate calculation unit calculates a resource usage rate of the entire processing apparatus when resources of the processing apparatus are allocated based on the unit resource candidates. apparatus. The band lower limit value calculating unit calculates a minimum value of the minimum band for each device, which is a value obtained by dividing a band predetermined as a minimum guaranteed band of the route by the ratio, as a lower limit value of the band,
The unit resource candidate calculation unit is equal to or less than the resource amount of the processing device that is equal to or greater than the lower limit value and has the smallest resource amount among the values obtained by dividing the resource amount of the processing device by the ratio by an integer. Calculate the value as a candidate for the unit resource,
The usage rate calculation unit allocates a resource of a processing device in which the unit resource candidate is smaller than the device-specific minimum bandwidth among the processing devices based on the device-specific minimum bandwidth, and the unit resource candidate is the device resource 2. The service path management apparatus according to claim 1, wherein a resource usage rate of the entire processing apparatus when a resource of the processing apparatus that is equal to or greater than a minimum bandwidth for each apparatus is allocated based on the unit resource candidate is calculated. .   The allocating unit is actually used for each processing device based on the minimum bandwidth for each device and the ratio of the processing devices for which the unit resource candidate is smaller than the minimum bandwidth for each device. The bandwidth is calculated, and the processing device whose unit resource candidate is equal to or larger than the minimum bandwidth for each device is actually used for each processing device based on the unit resource and the ratio with the maximum resource usage rate. 4. The service path management apparatus according to claim 3, wherein a bandwidth is calculated, and resources are allocated in each of the processing devices based on the calculated bandwidth. Among a plurality of processing functions that perform predetermined processing on the input flow and output a processing result flow, all of the processing devices extracted one by one from each of a plurality of processing device groups having the same processing function are passed through. Service path management device for managing a network system that sets a route, allocates resources of the processing device according to the bandwidth of the route to the route, and distributes and transfers flows received at the route entrance to the route Service path management method executed in
A bandwidth lower limit value calculating step of calculating a ratio of a traffic amount input to the processing function to a traffic amount of a flow received at an entrance of the route for each processing function, and calculating a lower limit value of the bandwidth based on the ratio. When,
Based on the resource amount of the processing device and the ratio, a value that is greater than or equal to the lower limit value and less than or equal to the resource amount of the processing device that has the smallest resource amount is calculated as a candidate for a unit resource that is the minimum unit of resource allocation Unit resource candidate calculation step;
For each of the unit resource candidates calculated by the unit resource candidate calculation step, a usage rate calculation step of calculating the resource usage rate of the entire processing device when selected as a unit resource;
A setting step for setting a bandwidth of the route based on a unit resource having the maximum resource usage rate calculated by the usage rate calculation step among the unit resource candidates calculated by the unit resource candidate calculation step; ,
Based on the unit resource that maximizes the resource usage rate and the ratio, the bandwidth that is actually used for each processing device is calculated, and based on the calculated bandwidth, the bandwidth of the route in each of the processing devices is calculated. An allocation process for allocating resources;
A service path management method comprising:

Images