JP6541598B2 - Device and Program for Determining Placement of Network Function - Google Patents

Description

  The present disclosure relates to technology for determining the arrangement position of a function of a network.

  Non-Patent Document 1 discloses virtualization of network functions for flexible service provision on a communication network.

"Network Functions Virtualisation", ETSI, [Search on March 11, 2016], Internet <URL: http://portal.etsi.org/NFV/NFV_White_Paper.pdf>

  Currently, nodes of a network are installed not only at sites managed by users themselves (hereinafter, user sites) but at sites of data center operators (hereinafter, data centers). By the virtualization technology described in Non-Patent Document 1, each function of the network can be flexibly distributed to user sites and data centers. However, for example, among the functions of the existing user network established by the user, it becomes a problem which function should be transferred to the data center.

  The present invention provides a determination apparatus and program that effectively determine the function to be transferred to the data center for the functions that constitute the network.

According to an aspect of the present invention, among the plurality of functions disposed at a plurality of user sites, the determination apparatus for determining the function to be transferred to a data center is a user site where each of the plurality of functions is disposed; A function cost of the plurality of functions, a link connecting two functions of the plurality of functions, a link cost of each link, and a transmission delay between the plurality of sites including the plurality of user sites and the data center , Holding means for holding information indicating delay allowance, weighting factors for each of the plurality of sites, and weighting factors for links, and a function other than the function for which the user specifies the placement position among the plurality of functions. Determining means for determining whether or not to relocate to the data center for one or more undetermined functions, the determination means connecting to the one or more undetermined functions The undecided function connected to the first judgment target link if the first judgment target link with the largest delay amount is to be connected to the function of the data center by judging the judgment target link and its delay amount based on the link Is determined to be transferred to the data center, and if the first determination target link is to be connected to the function of the user site, it is determined that the undetermined function to be connected to the first determination target link is not to be transferred to the data center If the first judgment target link is to connect two unjudged functions, it is judged whether or not the two unjudged functions are degenerated into one unjudged function and transferred to the data center. It is repeated to exclude the unjudged function that has been performed from the one or more unjudged functions until the number of the one or more unjudged functions becomes zero, the judgment target link One or more links that has degenerated into a single Link to connect to the function of the data center from a constant function, one connecting from one undetermined function to the function of the user site to which the undetermined function is arranged From the link that degenerates the above link into one link, and the link that connects the undecided functions, the link that connects the undecided function that degenerated multiple functions located at different user sites to the user site And the delay amount of the judgment target link is the total value of the delay amounts of the original one or more links in the case of the degenerated link, and in the case of the undegenerate link. The amount of delay of the original link, and the determination means determines whether or not to transfer the undetermined function included in the one or more undetermined functions to the data center. Find the total value of the network cost and the delay amount of the link between the multiple sites when transferring the undetermined function, which has not been determined whether to relocate to the data center at the point, to the data center, The arrangement position at which the network cost is minimized is output as a determination result while the total value of the delay amounts of the links between the plurality of sites is less than or equal to the allowable amount , and the network cost is calculated for each of the plurality of sites. The sum of the site cost and the sum of the link cost of the link between the plurality of sites multiplied by the weighting factor of the link is obtained as the sum of the site cost is the functional cost of the function placed at the site. It is characterized by being obtained as the product of the sum and the weighting factor of the site.

  According to the present invention, it is possible to effectively determine the function to be transferred to the data center regarding the function of configuring the network.

FIG. 1 shows an initial configuration of a network according to an embodiment. Explanatory drawing of the determination process by one Embodiment. Explanatory drawing of the determination process by one Embodiment. Explanatory drawing of the determination process by one Embodiment. Explanatory drawing of the determination process by one Embodiment. The figure which shows the arrangement position and link cost of each function by one Embodiment. The figure which shows the arrangement position and link cost of each function by one Embodiment. The figure which shows the arrangement position and link cost of each function by one Embodiment. 5 is a flowchart of determination processing according to an embodiment. 5 is a flowchart of determination processing according to an embodiment. The block diagram of the determination apparatus by one Embodiment.

  Hereinafter, exemplary embodiments of the present invention will be described with reference to the drawings. The following embodiment is an exemplification, and the present invention is not limited to the contents of the embodiment. Further, in each of the following drawings, components that are not necessary for the description of the embodiment will be omitted from the drawings.

  FIG. 1 is a block diagram of an existing network of a user used for describing the present embodiment. In FIG. 1, the numbers 1 to 8 enclosed by squares indicate the functions of the network, and the lines connecting the functions indicate links. In the following, the function of the number i (i is an integer of 1 to 8) surrounded by a square is referred to as a function #i. Further, a link connecting the function #i and the function #j (i and j are integers of 1 to 8 and i ≠ j) is described as a link #ij. Each function #i can be realized as a single dedicated device or as a device combined with other functions.

  The user inputs the site where the existing function is arranged as initial information, the existing link, the function cost of each function, and the link cost of each link in the determination apparatus according to the present invention. In FIG. 1, the numbers shown for each link indicate the link cost inputted by the user. Further, in this example, the functional cost of the function is set to the same value as the number enclosed by a square. That is, it is assumed that the functional cost of the function #i is i. In FIG. 1, functions # 1, # 2, # 3, # 7 and # 8 are arranged at user site # 1 (U # 1), and functions # 4, # 5 and # 6 are user sites. It is arranged in # 2 (U # 2). The link cost can be set to a larger value, for example, as the bandwidth of the link increases. Also, the function cost can be set to a larger value as the operation cost of the function becomes higher.

  Subsequently, the user inputs the site to the determination apparatus for the function for the user to specify the site to be placed. In this example, the functions # 2 and # 8 in FIG. 1 are allocated to the user site # 1, the function # 7 is allocated to the data center (D), and the functions # 4 and # 5 are allocated to the user site # 2. It is assumed that the placement is specified by the user. FIG. 6 is a diagram showing a network configuration diagram and a link cost according to the arrangement position designated by the user. As shown in FIG. 6, functions # 1, # 3, and # 6 for which the user did not specify the site to be deployed are the determination target functions of the site to be deployed. Note that what is determined in the present embodiment is whether the function to be determined is moved to the data center or left at the currently deployed user site. In other words, it is the decision whether the functions # 1 and # 3 are left at the user site # 1 or moved to the data center, and the function # 6 is judged whether to leave the user site # 2 or moved to the data center. is there. In the following description, among the functions for which the user has not specified the arrangement position, the function for which it is not determined whether to relocate to the data center is referred to as an undetermined function.

  Furthermore, the user inputs an inter-site delay amount and an allowable delay value into the determination device as initial information. In this example, the delay between the user site # 1 and the data center is 1, the delay between the user site # 2 and the data center is 1, and the delay between the user site # 1 and the user site # 2 is The delay between them shall be 3. The delay amount in the same site is assumed to be zero. Also, it is assumed that the user designates 7 as the allowable value of delay.

  FIG. 2 shows the arrangement position of the function based on the initial information input by the user and the delay amount of the link. Note that the delay amount of the link between the functions whose arrangement positions are determined is a fixed value. On the other hand, when the arrangement position of at least one function of the link is undecided, the maximum value is used as the delay amount of the link. For example, the delay amount of the link # 67 is 0 when the function # 6 is disposed at the data center, and is 1 when the function # 6 is left at the user site # 2. Therefore, we use 1 which is the maximum value.

FIG. 9 is a flowchart of determination processing according to the present embodiment. In the present embodiment, when the determination apparatus determines whether to relocate to the data center at the start of processing (S10) and the undetermined function for the undetermined function (S12), the cost Nc of the entire network and any two of them. The maximum value of the delay amount between functions (delay maximum value) dmax is calculated. First, the cost Nc is calculated by the following equation.
Nc = Σαfd + Σβfu + ΣγL (1)
Here, fd is the functional cost of the function installed in the data center, fu is the functional cost of the function installed in the user site # 1 and # 2, and L is the link cost of the link established between the sites It is. Furthermore, α, β, and γ are weighting coefficients of cost, which are values determined by users of 0 or more in advance. Generally, with regard to the function installed at the user site, the operation load is increased on the user side, so β> α. In the following description, α, β and γ will be 1, 2 and 1, respectively. The weighting factor of the user site can be set to a different value for each user site.

  Further, the delay maximum value dmax can be obtained by the sum of delay amounts of links between sites. Although the reason will be described later, the cost Nc and the delay maximum value dmax are calculated on the assumption that the undetermined function at the time of calculation is located at the data center.

  As described above, in the calculation of the cost Nc and the delay maximum value dmax in S10, it is assumed that the unjudged functions # 1, # 3 and # 6 are arranged in the data center. From FIG. 6, Σα fd of the equation (1) is 1 + 3 + 6 + 7 = 17, and ββ fu is 2 × (2 + 4 + 5 + 8) = 38. Also, when functions # 1, # 3 and # 6 are located at the data center, the links between the sites are links # 12, # 18, # 23, # 27, # 34, # 35, # 56, # 78 Therefore, γγ L is 3 + 3 + 2 + 2 + 10 + 5 + 4 + 2 = 31. Therefore, the cost Nc in the state of FIG. 6 is 86. Also, the links between the sites are links # 12, # 18, # 23, # 27, # 34, # 35, # 56, # 78, all of which are links between the user site and the data center Since the delay amounts are respectively 1, the maximum delay value dmax is 8.

  The determination apparatus of this embodiment determines the relocation of the undetermined function so that the cost Nc of the entire network is low, under the condition that the delay amount between any two functions is 7 or less which is the allowable value. Do. Therefore, the determination device uses the evaluation value R as an internal parameter. The initial value of the evaluation value R is a value much larger than the total value of the functional costs of the respective functions, and in this example, is 100000.

  The determination apparatus determines whether or not to relocate one or more undecided functions of one or more unjudged functions to the data center based on the delay in S11. FIG. 10 is a flowchart showing the process of S11. In S20, the determination apparatus determines a determination target link. Among the links connected to the undetermined function, the determination target link is a link other than the link connecting between the user sites at the current arrangement position. In FIG. 2, the link # 78 and the link # 27 are excluded from the link to be judged because they are not links connecting to the undetermined function. Further, the links # 34 and # 35 are excluded from the determination target links because they are links connecting between user sites at the current arrangement position. Therefore, in FIG. 2, the links to be processed are links # 12, # 17, # 18, # 23, # 36, # 56, and # 67. At this time, the determination apparatus degenerates links that are connected to the same site (data center, user sites # 1 and # 2) from the same function among the determination target links into one. Note that the delay of the link after degeneration is the sum of the delays of the original link. In FIG. 2, links # 12 and # 18 are degenerated into one link in order to go to the same user site # 1, and the delay thereof is 2. FIG. 3 shows the link after the above processing. In addition, in FIG. 3, only the determination target link is shown, and the other links are omitted. Also, in the following, the link connecting function #i and the function of user center # 1 is described as link #i # U1, and the link connecting function #i and the function of user center # 2 is link #i # The link connecting the function #i and the function of the data user center is written as U2, and the link is written as link # i # D.

  The determination apparatus selects the link with the largest delay among the links to be determined in S21. As shown in FIG. 3, the link with the largest delay is link # 36. The determination apparatus determines in S22 whether the link selected in S21 is a link connecting to a site or a link connecting undetermined functions. In the present example, since the link # 36 is a link connecting the undetermined functions, the determination in S22 is "No". In this case, the determination apparatus sets two functions connected by the link selected in S22 as one degenerate function, and returns to S20. In this example, since the functions included in the degeneration function are currently disposed at different user sites, only the link connecting the degeneration function and the data center is set as the processing target link. If the undecided functions included in the degeneration function are all located at the same user site, the link connecting the degeneration function and the data center, the degeneration function, and the degeneration function are included in the link. The link connecting the user site where the undecided function is located is set as the processing target link. In the following, a link connecting the degeneration function and the function of the data center is denoted as link # T # D. FIG. 4 shows a second determination target link at S20. The determination target links are the link # 1 # U1, the link # 1 #D, and the link #T #D. Among them, since the link # 1 # U1 has the largest delay, the determination apparatus selects the link # 1 # U1 in S21. Since the link # 1 # U1 is a link connecting to the user site # 1, the determination in S22 is "Yes". In this case, when the determination device arranges the undetermined function connected to the link selected in S21 at the site to which the selected link connects, in S23. That is, it is determined that the function # 1 is to be arranged at the user site # 1. In addition, when determining the link to be determined, the reason that the link connecting to the same site from one undecided function is degenerated is a delay that is reduced by arranging the undecided function at the site connected to the link It is to determine the amount.

  When the arrangement position of the undetermined function is determined in S23, the process proceeds to S12 in FIG. At S12, the determination apparatus calculates the cost Nc and the maximum delay value dmax. FIG. 7 shows a state in which the function # 1 is arranged at the user site # 1. As described above, in the calculation of the cost Nc and the maximum delay value dmax, it is assumed that the unjudged functions # 3 and # 6 are arranged at the data center, so Σα fd of the equation (1) is 3 + 6 + 7 = 16 and Σβ fu Is 2 × (1 + 2 + 4 + 5 + 8) = 40. Further, since the links between the sites are links # 17, # 23, # 27, # 34, # 35, # 56, and # 78, γγL is 2 + 2 + 2 + 10 + 5 + 4 + 2 = 27. Therefore, the cost Nc in the state of FIG. 7 is 83. Further, in the state of FIG. 7, the links between the sites are links # 17, # 23, # 27, # 34, # 35, # 56 and # 78, all of which are between the user site and the data center. The dmax is 7 because each delay amount is 1.

  The determination device determines whether the maximum delay value dmax is equal to or less than the allowable value in S13. In this example, since the maximum delay value dmax is 7 and the allowable value is 7 or less, “Yes” is obtained. Therefore, the determination apparatus determines in S14 whether the cost Nc is smaller than the current evaluation value R. In this example, since the cost Nc is 83 and is smaller than the current evaluation value R = 100, the determination device stores the current arrangement position in S15, and updates the evaluation value R to 83 in S16. Thereafter, the determination device determines whether or not there is an undetermined function in S17. In this example, since the functions # 3 and # 6 remain as undetermined functions, the determination in S17 is "Yes". Therefore, the process returns to S11. If the maximum delay value dmax is larger than the allowable value in S13, the process returns to S11. Furthermore, if the cost Nc is larger than the current evaluation value R in S14, the arrangement position at that time is not stored, and the process proceeds to S17 without updating the evaluation value R.

  The determination device determines whether to move the undetermined function in S11 according to the process shown in FIG. First, in S20, a determination target link is determined. Since it is determined that the function # 1 in FIG. 4 leaves the user site # 1 in the previous process, the link # 1 # U1 and the link # 1 # D are excluded from the determination target links. Therefore, as shown in FIG. 5, the link to be determined is only link # T # D. Therefore, the determination apparatus selects the link # T # D in S21. Since the link # T # D is to connect to the data center, the determination in S22 is "Yes". Therefore, in S23, the determination apparatus determines to transfer functions # 3 and # 6 included in the degeneration function to the data center.

  Returning to FIG. 9, in S12, the determination apparatus calculates the cost Nc and the maximum delay value dmax. As shown in FIG. 8, since the functions # 3 and # 6 are arranged at the data center, Σα fd in the equation (1) is 3 + 6 + 7 = 16, and Σβ fu is 2 × (1 + 2 + 4 + 5 + 8) = 40. Further, since the links between the sites are links # 17, # 23, # 27, # 34, # 35, # 56, and # 78, γγL is 2 + 2 + 2 + 10 + 5 + 4 + 2 = 27. Therefore, the cost Nc in the state of FIG. 9 is 83. Also, in the state of FIG. 8, the links between the sites are links # 17, # 23, # 27, # 34, # 35, # 56, and # 78, all of which are between the user site and the data center. The maximum delay value dmax is 7 because each delay amount is 1.

  The determination device determines whether the maximum delay value dmax is equal to or less than the allowable value in S13. In this example, since the maximum delay value dmax is 7 and the allowable value is 7 or less, “Yes” is obtained. Therefore, the determination apparatus stores the current arrangement position in S15, and updates the evaluation value R to 83 in S16. Thereafter, the determination apparatus determines whether or not the undetermined function remains in S17. In the present example, since the undecided function is zero, the process ends. Then, the determination apparatus finally outputs the arrangement position stored in S15 finally as the determination result. At this time, it is determined that all undecided functions at the time of the last storage in S15 are to be transferred to the data center.

  As described above, in the present embodiment, the site to be placed is determined from the undecided function connected to the link with the largest delay amount among the links to be determined. Then, if the maximum delay value dmax is equal to or less than the allowable value, the cost Nc at that time is obtained and compared with the evaluation value R. The evaluation value R indicates the smallest value of the cost Nc when the maximum delay value dmax is equal to or less than the allowable value, except when the maximum delay value dmax first becomes equal to or less than the allowable value. Therefore, when the calculated cost Nc is equal to or less than the evaluation value R, the evaluation value R is updated, and the arrangement position at that time is stored. Then, the above process is repeated until the undecided function disappears. Then, after the processing is completed, the determination device outputs the arrangement position finally stored in S15 as a final arrangement position. In addition, it is determined that the undetermined function at the time of the last storage in S15 is to be transferred to the data center. This is because, as described above, the undecided function calculates the costs Nc and dmax assuming that they are located at the data center. That is, although the delay amount is further reduced by arranging the undetermined function at the user site, the cost Nc may increase. Therefore, in the calculation of the costs Nc and dmax, in order to determine the placement position that minimizes the cost Nc under the condition that the maximum delay value dmax is equal to or less than the allowable value when the undecided function disappears, The unjudged function shall be placed in the data center. This is the reason for placing the undecided function in the data center in the calculation of the costs Nc and dmax.

  In S21, if the delay connecting the link connecting the undetermined function and the user site with the link connecting the undetermined function and the data site has the same value and is the maximum, the undetermined function is It is determined to relocate to the data center. This is because the data center cost weighting factor is less than the user site weighting factor. In the above embodiment, among the links connected to the undetermined function, the links to be determined are links other than the links connecting the user sites at the current arrangement position. However, a link connecting the undetermined function to the data center and a link connecting the undetermined function to the user site where the undecided function is arranged may be used as the determination target links. Furthermore, in the above-described embodiment, if the link selected in S21 is a link connecting undecided functions, the degeneration function is generated in S24, but the link selected in S21 is disposed at a different user site The configuration may be such that it is determined that the two undecided functions are to be placed in the data center if the two undecided functions are connected.

  FIG. 11 is a block diagram of the determination apparatus. The user interface unit 10 is a user interface for the user to input initial information into the determination apparatus, and the determination apparatus to display and output the determination result to the user. The holding unit 11 holds each piece of initial information input by the user. Specifically, the holding unit 11 has a user site in which each of a plurality of functions is arranged, a function cost of the plurality of functions, a link connecting two functions of the plurality of functions, and a link cost of each link And information indicating transmission delay among a plurality of sites including a plurality of user sites and a data center, an allowable amount of delay, a weighting factor of each of the plurality of sites, and a weighting factor of a link.

  The determination unit 12 determines the function to be transferred to the data center by the method described above based on the information held by the holding unit 11. Specifically, the determination target link and its delay amount are determined based on the links connected to one or more undetermined functions, and the first determination target link with the largest delay amount is connected to the data center function. And the undetermined function connected to the first determination target link is determined to be relocated to the data center, and the first determination target link is connected to the function of the user site, the undetermined determination connecting to the first determination target link If it is determined that the function is not relocated to the data center and the first determination target link is to connect two undecided functions, the two undecided functions are degenerated into one undecided function. Then, the determination unit 12 excludes the undecided function for which it is determined whether or not to relocate to the data center from the one or more undecided functions, the number of one or more undecided functions becomes zero. Repeat until.

  Here, the judgment target link is a link obtained by degenerating one or more links connecting from one unjudged function to the function of the data site into one link, and the unjudged function is arranged from one unjudged function A plurality of functions located at different user sites are degenerated from a link that degenerates one or more links that connect to the functions of the user site into one link, and a link that connects undecided functions It is the link except the link which connects an unjudged function to a user site. Note that the delay amount of the determination target link is the total value of the delay amounts of the original one or more links when the link is degenerated, and when the link is not degenerated, the original link Amount of delay.

  Then, each time the determination unit 12 determines whether or not to relocate the undecided functions included in one or more undecided functions to the data center, it is determined whether to relocate to the data center at that time. The total value of the network cost and the delay amount of the link between multiple sites when the undetermined function not performed is transferred to the data center is determined, and the total value of the delay amounts of the link between multiple sites is the allowable value The arrangement position at which the network cost is minimized while the value is smaller than the value is output as the determination result. The network cost is obtained as the sum of the site cost for each of a plurality of sites and the value obtained by multiplying the sum of the link costs for links between a plurality of sites by the link weighting coefficient, and the site cost is It is obtained as the product of the sum of the functional cost of the allocated function and the weighting factor of the site.

  As described above, according to the present embodiment, the network cost can be reduced while the maximum delay value between any two functions is set to the allowable value or less. The network cost is the evaluation of the cost of the link between sites and the operation cost of the function at each site. The lower the cost, the lower the operation cost of the entire network.

  The determination apparatus according to the present invention can be realized by a program that causes a computer to operate as the above-mentioned determination apparatus. These computer programs are stored in a computer readable storage medium or can be distributed via a network.

Claims (3)

A determination apparatus that determines a function to be transferred to a data center among a plurality of functions arranged at a plurality of user sites,
A user site in which each of the plurality of functions is arranged, a functional cost of the plurality of functions, a link connecting two functions of the plurality of functions, a link cost of each link, and the plurality of user sites Holding means for holding information indicating transmission delay among a plurality of sites including the data center and the data center, an allowable amount of delay, a weighting factor of each of the plurality of sites, and a weighting factor of the link;
A determination unit that determines whether or not one or more undecided functions, which are functions other than the function by which the user specifies the arrangement position, among the plurality of functions, are to be transferred to the data center;
Equipped with
The determination means determines the determination target link and the delay amount thereof based on the link connected to the one or more undetermined functions, and the first determination target link having the largest delay amount is connected to the function of the data center If it is determined that the undetermined function connected to the first determination target link is to be relocated to the data center, and if the first determination target link is connected to the function of the user site, the first determination target It is determined that the undecided function connected to the link is not relocated to the data center, and if the first determination target link is to connect two undecided functions, the two undecided functions are not yet determined. If the number of the one or more unjudged functions is zero, the unjudged function that has been degenerated into functions and determined whether to relocate to the data center is excluded from the one or more unjudged functions. Repeat until you,
The judgment target link is a link in which one or more links connected to the function of the data center from one unjudged function are degenerated into one link, and the unjudged function is arranged from one unjudged function A link in which one or more links connecting to the functions of the user site have been degenerated into one link, and a link connecting between undecided functions in which the multiple functions placed in different user sites are not degenerated A link excluding the link that connects the judgment function to the user site,
The delay amount of the judgment target link is a total value of delay amounts of the original one or more links when the link is degenerated, and when the link is not degenerated, the delay amount of the link of the original link Is the amount of delay,
The determination unit determines whether or not to relocate to the data center at that time every time it is determined to relocate to the data center about the undecided functions included in the one or more undecided functions. The total value of the delay amount of the link between the plurality of sites is obtained by calculating the total value of the network cost and the delay amount of the link between the plurality of sites when transferring the undetermined function not being performed to the data center among There is less than or equal to the allowable amount, and outputs the determination result placement position where the network cost is minimized,
The network cost is obtained as a sum of a site cost of each of the plurality of sites and a value obtained by multiplying a sum of link costs of links among the plurality of sites by a weighting factor of the link.
The determination apparatus is characterized in that the site cost is obtained as a product of a sum of function costs of functions arranged at the site and a weighting factor of the site.   The determination apparatus according to claim 1, wherein the weighting factor of the data center is smaller than the weighting factors of the plurality of user sites.   A program that causes a computer to function as the determination apparatus according to claim 1.

Images