JP6473406B2 - Virtual network allocation apparatus, virtual network allocation method, and virtual network allocation program - Google Patents

Description

  The present invention relates to an apparatus, a method, and a program for assigning a physical network to a virtual network.

  A virtual network allocation method has been proposed (see, for example, Non-Patent Document 1). The technique of Non-Patent Document 1 allocates a physical network to a virtual network requested by a user. At this time, the topology of the virtual network requested by the user needs to be appropriately designed by the user. On the other hand, it is natural for a user to request a dense network (a network whose topology is a complete graph) in which links exist between all nodes based on traffic traffic for forecasting demand (Traffic Matrix).

However, as the number of requested network links increases, the computation time required to discover virtual network assignments increases. For example, when using a linear programming relaxation is a virtual network allocation typically approach (see Non-Patent Document 1.), The number of links computation time required virtual network | E | approximately the third power of | proportional to ³ | E. When the number of requested virtual network nodes | V | is 100, the virtual network O (| E |) = O (| V |) with a sparse link and the virtual network O (| E |) = O (| Comparing V | ² ), the calculation time is 100 ³ = 10 ⁶ .

  There is no way to convert a dense virtual network into a sparse virtual network. Vertex / branch deletion and contraction are considered as general graph operations, but not for virtual network allocation. Therefore, a method for obtaining a virtual network assignment (pre-conversion assignment) of a virtual network before conversion from a virtual network assignment (post-conversion assignment) of the converted virtual network is not considered.

  First, the virtual network allocation problem will be described. Assume that there is a virtual network usage request from the user shown in FIG. 1 and a physical network of the network equipment provider shown in FIG. A virtual network is a communication network in which virtual nodes are connected by virtual links. A physical network is a communication network in which physical nodes are connected by physical links. In FIG. 1, the alphabet in the frame indicates the virtual node name, the number in the frame indicates the usage request amount of the virtual node, and the numerical value associated with each virtual link connecting the virtual nodes indicates the usage request amount of the virtual link. . In FIG. 2, the alphabet in the frame indicates the physical node name, the number in the frame indicates the free capacity in the physical node, and the numerical value associated with each physical link connecting the physical nodes indicates the free capacity of the physical link.

  The virtual network is composed of virtual nodes and virtual links, and usage requests (the number of CPU clocks and communication bandwidth) are given to each. It is assumed that the topology of the virtual network is a complete graph, that is, all virtual node pairs are connected by virtual links. However, even when the topology of the virtual network is not a complete graph, it can be handled as a complete graph by adding a virtual link whose required communication bandwidth is 0.

  The physical network is composed of physical nodes and physical links, each having free capacity and allocation cost. In FIG. 2, node and link allocation costs are omitted.

The virtual network assignment problem is to assign virtual nodes and virtual links to physical nodes and physical links that satisfy their required capacity. A virtual node is assigned to one physical node. Virtual links are assigned to one or more physical paths. Here, the “physical path” is a physical link column in which adjacent physical links share an end point among the physical link columns. And assign the plurality of physical paths, for example, the physical path P ₁ to 30% of the required communication bandwidth of the virtual links in the 20% physical path P _2, is such as assigning each of 50% to a physical path P ₃ .

  FIG. 3 shows an example of allocation of virtual networks to physical networks. Virtual nodes a, b, and c are assigned to physical nodes A, B, and E, respectively. Virtual link (a, b) is assigned to physical path {(A, B)}. Virtual link (a, c) is assigned to physical path {(A, D), (D, E)}. The virtual link (b, c) is assigned to two physical paths {(B, D), (D, E)} and {(B, C), (C, E)}.

  The cost of virtual network allocation is the total cost of all physical nodes and physical links used for allocation. When assigning a virtual network, an assignment that minimizes the total cost is obtained.

M.M. Chowdy, M.C. Rahman, and R.M. Boutaba, “ViNEYard: Virtual Network Embedding Algorithms With Coordinated Node and Link Mapping,” IEEE / ACM Trans. Netw. , Vol. 20, no. 1, pp. 206-219, 2012.

  When a user requests a dense virtual network, there is a problem that calculation time becomes long when an allocation that minimizes the total cost is obtained. I did not know how to convert a dense virtual network to a sparse virtual network or how to determine the pre-conversion assignment from the post-conversion assignment.

  Accordingly, an object of the present invention is to convert a requested dense virtual network into a sparse virtual network in assigning a virtual network requested by a user.

The virtual network allocation device according to the present invention is:
An input unit for acquiring a virtual network to be assigned to a physical network;
A virtual network conversion unit that converts the input virtual network acquired by the input unit into a sparse virtual network in which the number of virtual links is reduced compared to the virtual links included in the input virtual network;
A virtual network allocation calculation unit that allocates the obtained sparse virtual network to the physical network;
An allocation conversion unit that converts an allocation to the sparse virtual network allocated by the virtual network allocation calculation unit into an allocation to the input virtual network using a difference between the input virtual network and the sparse virtual network; ,
Is provided.

  The allocation conversion unit converts a physical path included in the physical network allocated to the sparse virtual network to a virtual link not included in the sparse virtual network among virtual links included in the input virtual network. The assignment to the sparse virtual network may be converted into the assignment to the input virtual network.

  The conversion in the virtual network conversion unit may be performed by performing a link contraction process for deleting one of the three virtual links forming a triangle a plurality of times.

The conversion in the virtual network conversion unit is:
Dividing a virtual node included in the input virtual network into a plurality of divided node groups;
Said core node connected with each virtual node and the virtual link included in the split node groups generated for each of the division nodes, a virtual link said core node and each virtual node is connected to the access link, connecting the core node between The virtual link to be used is the core link,
You may carry out by deleting each virtual link contained in the said input virtual network, leaving the said access link and the said core link.

A virtual network allocation method according to the present invention includes:
When acquiring a virtual network to be allocated to a physical network, a virtual network conversion procedure for converting the acquired input virtual network into a sparse virtual network in which the number of virtual links is smaller than the number of virtual links included in the input virtual network;
A virtual network allocation calculation procedure for allocating the obtained sparse virtual network to the physical network;
An allocation conversion procedure for converting an allocation to the sparse virtual network allocated in the virtual network allocation calculation procedure into an allocation to the input virtual network using a difference between the input virtual network and the sparse virtual network; ,
Are sequentially executed by the virtual network allocation device.

  The virtual network allocation program according to the present invention is a program for causing a computer to execute each procedure included in the virtual network allocation method according to the present invention.

  The above inventions can be combined as much as possible.

  According to the present invention, when a virtual network requested by a user is allocated, the requested dense virtual network can be converted to a sparse virtual network, and the allocation calculation can be performed at high speed. .

An example of a virtual network is shown. An example of a physical network is shown. An example of allocation of the virtual network to a physical network is shown. It is a block diagram which shows an example of a virtual network allocation apparatus. 3 shows an example of virtual network conversion according to the first and second embodiments. An example of the input virtual network with the utilization request | requirement in Embodiment 3 and 4 is shown. An example of the sparse virtual network which concerns on Embodiment 3 is shown. An example of the sparse virtual network which concerns on Embodiment 4 is shown.

  Hereinafter, embodiments of the present invention will be described in detail with reference to the drawings. In addition, this invention is not limited to embodiment shown below. These embodiments are merely examples, and the present invention can be implemented in various modifications and improvements based on the knowledge of those skilled in the art. In the present specification and drawings, the same reference numerals denote the same components.

  The virtual network allocation method according to the present embodiment is a method executed by the virtual network allocation apparatus according to the present embodiment, and allocates a physical network held by a network facility provider to a virtual network requested by a user. Thereby, the network equipment provider can request | require virtual network allocation which satisfy | fills the request | requirement with respect to the virtual network utilization request | requirement from a user.

  Here, the network equipment provider is an Internet service provider (ISP) or the like that holds network resources and ICT resources and provides them to users. Virtual network allocation is to determine which network equipment and ICT (Information & Communication Technology) resources to use and how to connect them according to the virtual network usage request. It is.

  In this embodiment, the allocation is found at high speed by reducing the number of links of the requested virtual network before searching for the virtual network allocation. In the present embodiment, virtual network conversion and allocation conversion are performed in order to reduce the number of links of the virtual network requested to be used. In addition, an existing method can be used for finding (calculating) allocation.

  Four types of conversion methods will be described as virtual network conversion methods for reducing the number of links in the virtual network. In the first embodiment, the link contraction is described, in the second embodiment, the multiple link contraction is performed, in the third embodiment, the k-node insertion link contraction is described, and in the fourth embodiment, the pseudo k-node insertion link contraction is described. .

  FIG. 4 shows a configuration example of the virtual network allocation device according to the present embodiment. The virtual network allocation device according to the present embodiment includes an input unit 11, a virtual network conversion unit 12, a virtual network allocation calculation unit 13, and an allocation conversion unit 14.

  The virtual network allocation device according to the present embodiment can be configured using a computer including a CPU (Central Processing Unit) and a storage unit. In this case, the CPU in the virtual network assignment device executes the computer program stored in the storage unit, thereby realizing each functional unit provided in the virtual network assignment device. As described above, the virtual network assignment device according to the present embodiment can be realized by a computer and a program, and can be recorded on a recording medium or provided through a network.

The input unit 11 receives a physical network and a virtual network which are input in question.
The virtual network conversion unit 12 performs virtual network conversion so that the number of links of the virtual network requested to be used is reduced. Thereby, the input virtual network is converted into a sparse virtual network.
Next, the virtual network allocation calculation unit 13 calculates a virtual network allocation for the sparse virtual network converted by the virtual network conversion unit 12. Virtual network allocation can be performed using existing virtual network allocation techniques.
Next, the allocation conversion unit 14 performs allocation conversion on the allocation of the virtual network allocation calculation unit 13 and calculates the allocation of the input virtual network before the virtual network conversion. This is output as a result. Allocation conversion uses the difference between the input virtual network and the sparse virtual network.

  In Embodiments 1 to 4 to be described later, a specific example of virtual network conversion in which the virtual network conversion unit 12 performs link contraction will be described. Any of the virtual network conversion methods described in the first to fourth embodiments is not limited to a virtual network and a physical network to be applied. Therefore, any method can be used in the virtual network conversion unit 12.

  In the “link contraction” of the first embodiment, the number of virtual links is decreased by one. In the “multiple link reduction” in the second embodiment, the “node insertion link reduction” in the third embodiment, and the “pseudo node insertion link reduction” in the fourth embodiment, a plurality of virtual links can be reduced. Therefore, the conversion technique used in the virtual network conversion unit 12 is “multiple link contraction” in the second embodiment, “node insertion link contraction” in the third embodiment, or “pseudo node insertion link contraction” in the fourth embodiment. It is preferable that

The “node insertion link contraction” in the third embodiment is obtained by adding a virtual link having an appropriate required communication bandwidth to the virtual network obtained by the “pseudo-node insertion link contraction” in the fourth embodiment. For example, the converted virtual network in FIG. 7 is obtained by adding branches to the pseudo-core nodes u ₁ , u ₂ , and u ₃ in FIG. Therefore, the pseudo node insertion link contraction is a virtual network that is sparser than the node insertion link contraction.

  The “pseudo-node insertion link contraction” of the fourth embodiment completes conversion at a higher speed than the “multiple link contraction” of the second embodiment. This is because, in the multiple link contraction, virtual links are processed one by one, but in the pseudo node insertion link contraction, the links can be processed in a lump.

(Embodiment 1)
In the present embodiment, “link contraction” will be described as a first example of virtual network conversion. Link contraction is an operation to delete one virtual link from the virtual network.

(Virtual network conversion)
FIG. 5 shows an example of virtual network conversion according to the present embodiment. In the link contraction process, when the virtual network is three virtual links e, x, and y forming a triangle, the virtual link e which is an arbitrary side is deleted, and the requested communication band r (e) of the virtual link is left. This is a process of adding to the two virtual links x and y. This is equivalent to the virtual link e is added constrained to through the virtual node N ₂ is the shared end point of the virtual nodes x and y. By this link contraction process, the number of virtual links is reduced by one.

(Assignment conversion)
The virtual network allocation calculated by the virtual network allocation calculation unit 13 has no allocation corresponding to the deleted virtual link e. Therefore, the allocation conversion unit 14 performs allocation corresponding to the virtual link e. In addition, since the virtual nodes N ₁ , N ₂ , and N ₃ are not changed between the input virtual network and the sparse virtual network, the virtual node assignment does not need to be converted.

The bandwidth is excessively allocated to the virtual links x and y after the virtual network allocation. The surplus bandwidth is just r (e). This is assigned to the virtual link e. Specifically, each physical link to which the virtual links x and y are assigned is one physical path P _x {(N ₁ , N ₂ )} and P _y {(N ₂ , N ₃ )}, respectively. Assume that At this time, the virtual link e is connected to a path {(N ₁ , N ₂ ), (N that connects the physical path P _x {(N ₁ , N ₂ )} and the physical path P _y {(N ₂ , N ₃ )}. ₂ , N ₃ )}.

Here, when there are physical links e ₁ , e ₂ , e ₃ , and e ₄ , the connection between the physical path {e ₁ , e ₂ } and the physical path {e ₃ , e ₄ } is expressed by the following equation, for example. The

  When the virtual links x and y are assigned to a plurality of physical paths, one physical path having a surplus bandwidth is selected and connected from each physical path, and a virtual link e is assigned thereto. This is repeated until the necessary bandwidth is allocated to the virtual link e. Thereby, the allocation to the sparse virtual network can be converted into the allocation to the input virtual network.

(Embodiment 2)
In the present embodiment, “multiple link contraction” will be described as a second example of virtual network conversion. Multiple link contraction is an operation of executing link contraction of the first embodiment a plurality of times.

(Virtual network conversion)
The link contraction operation described in the first embodiment is executed a plurality of times. If the number of executions is s, the number of virtual links is reduced by s.

(Assignment conversion)
In the virtual network conversion, the i-th deleted virtual link is set to e _i , and the triangle is set to e _i , x _i , y _i . However, i = 1, 2,..., S. The calculated virtual network allocation was virtual network allocation calculating section 13, the virtual link e _1, e 2, which was deleted, _... no allocations corresponding to e _s. Therefore, assignment conversion unit 14 generates an allocation corresponding to the virtual link e _i. It should be noted that the virtual node assignment does not need to be converted because there is no change in the virtual node in the link contraction.

Allocation is performed for each virtual link in the order of virtual links e _s , e _s−1 ,... E ₂ , e ₁ . When creating the assignment of the virtual link e _i , as in the first embodiment, a physical path to which the virtual link e _i is assigned is created by combining the physical paths P _xi and P _yi to which the virtual links x _i and y _i are assigned. To do. By creating physical path assignments in the reverse order of virtual network conversion, the assignment of the remaining virtual links x _i , y _i in the triangle has been created when creating the assignment of the deleted virtual link e _i Can be guaranteed.

(Embodiment 3)
In the present embodiment, “node insertion link contraction” will be described as a third example of virtual network conversion. The k-node insertion link contraction is an operation of adding k virtual nodes and reducing the number of links. FIG. 6 shows a dense input virtual network before conversion, and FIG. 7 shows a sparse virtual network after conversion.

(Virtual network conversion)
The “node insertion link contraction” of the present embodiment performs virtual node conversion and virtual link conversion.

The virtual node conversion will be described. A set V of virtual nodes is divided into k, and k divided node groups are generated. A set of divided node groups after the division is defined as {V ₁ , V ₂ , V ₃ ,..., V _k }. k virtual nodes {u ₁ , u ₂ ,..., u _k } are added for each divided node group. FIG. 7 shows an example of a sparse virtual network when k = 3. The added virtual nodes u ₁ , u ₂ and u ₃ are called core nodes, and the original virtual nodes v _{1 to} v ₉ are called access nodes. The required capacity of the added core node is set to zero.

The virtual link conversion will be described. The virtual link will be described by dividing it into the following three types. A link (u _i , u _j ) between core nodes is called a “core link”. A link (u _i , v) between the core node u _i and the access node vεV _i is called an “access link”. A link between access nodes (original link eεE) is called an “original link”.

  In this embodiment, as shown in FIG. 7, the core link and the access link are added, and the original link is deleted. A thick solid line indicates a core link, and a thin solid line indicates an access link. The requested communication band of the core link and the access link is set so as to include the requested communication band of the original link as follows.

と設定する（ただし、ｉ≠ｊ）。 The requested communication band r ((u _i , u _j )) of the core link (u _i , u _j )

(Where i ≠ j).

Here, E (V _i , V _j ) is a set of original links between the divided node group V _i and the divided node group V _j . That is, it is a set of original links in which one virtual node at the end point of the original link is included in the divided node group V _i and the other virtual node is included in the divided node group V _j . For example, when the virtual nodes v ₁ , v ₂ , v ₃ are included in the divided node group V ₁ and the virtual nodes v ₄ , v ₅ , v ₆ are included in the divided node group V ₂ , the virtual node v ₂ The original link included in the virtual node v ₄ is included in the set E (V ₁ , V ₂ ).

と設定する（ただしｖ∈Ｖ_ｉ）。ここで「／」は差集合を表す集合演算子である。 The requested communication band r ((u _i , v)) of the access link (u _i , v)

(Where vεV _i ). Here, “/” is a set operator representing a difference set.

となる。２＜｜Ｖ｜のときｋ＜｜Ｖ｜−１となるｋを選ぶことで仮想リンクの数を減らすことができる。 With this operation, the number of virtual nodes becomes | V | + k, and the number of virtual links is

It becomes. The number of virtual links can be reduced by selecting k that satisfies k <| V | -1 when 2 <| V |.

(Assignment conversion)
In this embodiment, there is an assignment corresponding to the core link and the access link, but there is no assignment corresponding to the original link. Therefore, the assignment conversion unit 14 needs to create an assignment corresponding to the original link. Since the virtual nodes v _{1 to} v ₉ are not changed, the virtual node assignment does not need to be converted. Since the core nodes u _{1 to} u ₃ have no nodes corresponding to the input virtual network before conversion, the allocation is deleted.

The original link assignment is created from the core link assignment and the access link assignment. At this time, when the virtual node at the end point of the original link is included in the same divided node group V _i (assignment conversion example I), the virtual node at the end point of the original link is included in the different divided node group V _i and the divided node group V _j . This is divided into two cases (assignment conversion example II).

(Assignment conversion example I)
Description will be given of a case where the end point v and w are included in the end point and is and the same division nodes V _i of the original link. For example, the end points v and w are virtual nodes v ₁ and v ₃ included in the divided node group V ₁ .

By connecting the physical paths to which the two access links (u _i , v) and (u _i , w) are assigned in the same manner as in the first embodiment, the physical path corresponding to the original link (v, w) can be obtained. can get. Access links (v, w) are assigned to these physical paths.

Here, since the access links (u _i , v) and (u _i , w) included in the virtual network after the virtual network conversion do not exist in the input virtual network before the conversion, it is not necessary to secure the required communication bandwidth. . Therefore, the communication band allocated to these access links can be allocated to the original link (v, w) of the input virtual network before conversion. Further, since the required communication band of the original link is included in the required communication band of the core link and the access link, a necessary and sufficient band for the original link is allocated to the access link and the core link.

(Allocation conversion example II)
The case where the end points v and w are the end points of the original link and are included in different divided node groups V _i and divided node groups V _j will be described. Let vεV _i and wεV _j . For example, the end point v is the virtual node v ₂ included in the divided node group V ₁ , and the end point w is the virtual node v ₄ included in the divided node group V ₂ .

Physical path to which the access link (u _i , v) is assigned, physical path to which the access link (u _j , w) is assigned, and physical path to which the core link (u _i , u _j ) is assigned And a physical path corresponding to the original link (v, w) is obtained. The rest is the same as in the case of (assignment conversion example I), and the original link (v, w) is assigned to these physical paths.

(Embodiment 4)
In the present embodiment, “pseudo-node insertion link contraction” will be described as a fourth example of virtual network conversion. The pseudo k-node insertion link contraction is an operation for performing virtual network conversion like the k-node insertion link contraction described in the third embodiment, but the core node is not added to the virtual node of the input virtual network. This is a conversion using a virtual node of the input virtual network as a core node.

(Virtual network conversion)
In the “pseudo-node insertion link contraction” of the present embodiment, virtual node conversion and virtual link conversion are performed in the same manner as the k-node insertion link contraction of the third embodiment.

Similarly to the k-node insertion link contraction of the third embodiment, the node set V is divided into k, and divided node groups {V ₁ , V ₂ ,..., V _k } after the division are obtained. FIG. 8 shows an example of a sparse virtual network when k = 3. One virtual node is arbitrarily selected from each divided node group V _i , represented as u _i , and called a “pseudo core node”. For example, in FIG. 8, the virtual node v ₂ included in the divided node group V ₁ is a pseudo core node u ₁ , the virtual node v ₅ included in the divided node group V ₂ is a pseudo core node u ₂ , and the divided node group V ₃ the virtual node _{v 8} contained was pseudo core node _{u 3.} Virtual nodes v ₁ , v ₃ , v ₄ , v ₆ , v ₇ , v ₉ that are not pseudo core nodes are called “pseudo access nodes”.

Next, the virtual link after conversion will be described. Similar to the k-node insertion link contraction, the description will be divided into three types. The link (u _i , u _j ) between the pseudo core nodes is called “pseudo core link”. A link (u _i , v) between the pseudo core node u _i and the pseudo access node vεV _i is called a “pseudo access link”. Links other than the above two types are called “pseudo-original links”.

  In the present embodiment, as shown in FIG. 8, all pseudo original links are deleted, and all pseudo core links and pseudo access links are left. A thick solid line indicates a pseudo core link, and a thin solid line indicates a pseudo access link.

と設定する（ただし、ｉ≠ｊ）。 Next, the requested communication band will be described. In order to distinguish from the required communication band r before the virtual network conversion, the required communication band after the virtual network conversion is written as r ′. The required communication bandwidth r ′ ((u _i , u _j )) of the pseudo core link (u _i , u _j )

(Where i ≠ j).

と設定する（ただし、ｖ∈Ｖ_ｉ）。 Also, the required communication bandwidth r ′ ((u _i , v)) of the pseudo access link (u _i , v) is

(Where vεV _i ).

となる。ｋ＜｜Ｖ｜となるｋを選ぶことで、仮想リンクの数を減らすことができる。 With this operation, the number of virtual links is

It becomes. By selecting k that satisfies k <| V |, the number of virtual links can be reduced.

(Assignment conversion)
In this embodiment, there is an assignment corresponding to the pseudo core link and the pseudo access link, but there is no assignment of the pseudo original link. Therefore, the assignment conversion unit 14 needs to create an assignment corresponding to the pseudo original link. Since the virtual nodes v _{1 to} v ₉ are not changed, the virtual node assignment does not need to be converted.

The pseudo original link assignment is created from the pseudo core link assignment and the pseudo access link assignment in the same manner as the assignment conversion described in the third embodiment. At this time, if the virtual node at the end point of the pseudo original link is included in the same divided node group V _i (assignment conversion example III), the divided node group V _i and the divided node group V _j having different virtual nodes at the end point of the pseudo original link (Allocation conversion example IV).

(Assignment conversion example III)
Description will be given of a case where the end point v and w are included in the end point and is and the same division nodes V _i pseudo original link. For example, the end points v and w are virtual nodes v ₁ and v ₃ included in the divided node group V ₁ .

By connecting the physical paths to which the two pseudo access links (u _i , v) and (u _i , w) are assigned in the same manner as in the first embodiment, the physical corresponding to the pseudo original link (v, w) is obtained. A pass is obtained. Pseudo original links (v, w) are assigned to these physical paths.

  Here, since the pseudo access link has an excessive communication bandwidth, the surplus is assigned to the pseudo original link. Further, since the required communication bandwidth of the pseudo-original link is included in the required communication bandwidth of the pseudo-core link and the pseudo-access link, a necessary and sufficient bandwidth is allocated to the pseudo-core link and the pseudo-access link.

(Assignment conversion example IV)
The case where the end points v and w are end points of the pseudo original link and are included in different divided node groups V _i and divided node groups V _j will be described. Let vεV _i and wεV _j . For example, the end point v is the virtual node v ₁ included in the divided node group V ₁ , and the end point w is the virtual node v ₄ included in the divided node group V ₂ .

A physical path to which the access link (u _i , v) is assigned, a physical path to which the access link (u _j , v) is assigned, and a physical path to which the core link (u _i , u _j ) is assigned To obtain a physical path corresponding to the pseudo-original link (v, w). The rest is the same as in (Assignment Conversion Example III), and pseudo-original links (v, w) are assigned to these physical paths.

  The present invention can be applied to the information communication industry.

11: Input unit 12: Virtual network conversion unit 13: Virtual network allocation calculation unit 14: Virtual network allocation calculation unit

Claims (6)

An input unit for acquiring a virtual network to be assigned to a physical network;
A virtual network conversion unit that converts the input virtual network acquired by the input unit into a sparse virtual network in which the number of virtual links is reduced compared to the virtual links included in the input virtual network;
A virtual network allocation calculation unit that allocates the obtained sparse virtual network to the physical network;
An allocation conversion unit that converts an allocation to the sparse virtual network allocated by the virtual network allocation calculation unit into an allocation to the input virtual network using a difference between the input virtual network and the sparse virtual network; ,
A virtual network allocation device comprising: The allocation conversion unit converts a physical path included in the physical network allocated to the sparse virtual network to a virtual link not included in the sparse virtual network among virtual links included in the input virtual network. To assign the assignment to the sparse virtual network to the assignment to the input virtual network,
The virtual network allocation device according to claim 1. The conversion in the virtual network conversion unit is performed by performing link contraction processing for deleting one of three virtual links forming a triangle a plurality of times.
The virtual network assignment device according to claim 1 or 2. The conversion in the virtual network conversion unit is:
Dividing a virtual node included in the input virtual network into a plurality of divided node groups;
Said core node connected with each virtual node and the virtual link included in the split node groups generated for each of the division nodes, a virtual link said core node and each virtual node is connected to the access link, connecting the core node between The virtual link to be used is the core link,
Leaving the access link and the core link and deleting each virtual link included in the input virtual network;
The virtual network assignment device according to claim 1 or 2. When acquiring a virtual network to be allocated to a physical network, a virtual network conversion procedure for converting the acquired input virtual network into a sparse virtual network in which the number of virtual links is smaller than the number of virtual links included in the input virtual network;
A virtual network allocation calculation procedure for allocating the obtained sparse virtual network to the physical network;
An allocation conversion procedure for converting an allocation to the sparse virtual network allocated in the virtual network allocation calculation procedure into an allocation to the input virtual network using a difference between the input virtual network and the sparse virtual network; ,
A virtual network allocation method in which the virtual network allocation device sequentially executes.   A virtual network allocation program for causing a computer to execute each procedure according to claim 5.

Images