CN109412865A - A kind of virtual network resource allocation method, system and electronic equipment - Google Patents
A kind of virtual network resource allocation method, system and electronic equipment Download PDFInfo
- Publication number
- CN109412865A CN109412865A CN201811430362.9A CN201811430362A CN109412865A CN 109412865 A CN109412865 A CN 109412865A CN 201811430362 A CN201811430362 A CN 201811430362A CN 109412865 A CN109412865 A CN 109412865A
- Authority
- CN
- China
- Prior art keywords
- virtual
- task graph
- network information
- graph
- network resource
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
- 238000000034 method Methods 0.000 title claims abstract description 50
- 238000013468 resource allocation Methods 0.000 title claims abstract description 39
- 238000004422 calculation algorithm Methods 0.000 claims abstract description 22
- 230000011218 segmentation Effects 0.000 claims abstract description 21
- 238000000638 solvent extraction Methods 0.000 claims abstract description 14
- 238000007726 management method Methods 0.000 claims description 19
- 238000004364 calculation method Methods 0.000 claims description 17
- 230000015654 memory Effects 0.000 claims description 15
- 239000013256 coordination polymer Substances 0.000 claims description 12
- 238000012544 monitoring process Methods 0.000 claims description 9
- 238000005516 engineering process Methods 0.000 abstract description 13
- 238000005192 partition Methods 0.000 description 10
- 238000004891 communication Methods 0.000 description 6
- 238000010586 diagram Methods 0.000 description 4
- 238000004590 computer program Methods 0.000 description 3
- 230000004931 aggregating effect Effects 0.000 description 2
- 230000000694 effects Effects 0.000 description 2
- 230000010365 information processing Effects 0.000 description 2
- 238000012545 processing Methods 0.000 description 2
- 230000009286 beneficial effect Effects 0.000 description 1
- 230000003247 decreasing effect Effects 0.000 description 1
- 230000006870 function Effects 0.000 description 1
- 238000010295 mobile communication Methods 0.000 description 1
- 238000012986 modification Methods 0.000 description 1
- 230000004048 modification Effects 0.000 description 1
- 238000003672 processing method Methods 0.000 description 1
- 239000007787 solid Substances 0.000 description 1
Classifications
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L41/00—Arrangements for maintenance, administration or management of data switching networks, e.g. of packet switching networks
- H04L41/08—Configuration management of networks or network elements
- H04L41/0896—Bandwidth or capacity management, i.e. automatically increasing or decreasing capacities
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L41/00—Arrangements for maintenance, administration or management of data switching networks, e.g. of packet switching networks
- H04L41/08—Configuration management of networks or network elements
- H04L41/0893—Assignment of logical groups to network elements
Landscapes
- Engineering & Computer Science (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Data Exchanges In Wide-Area Networks (AREA)
- Information Transfer Between Computers (AREA)
Abstract
This application involves a kind of virtual network resource allocation method, system and electronic equipments.The described method includes: step a: generating task image according to the network information of virtual machines all in physical machine, and divided using multilevel scheme partitioning algorithm to the task image, obtain k mutually disjoint segmentation subsets；Step b: the critical path with the longest deadline in each segmentation subset is calculated, the virtual machine positioned at critical path node is obtained；Step c: the virtual unit of single input and output virtualization is distributed for the virtual machine in critical path node.The application optimizes network in such a way that half virtualization technology is combined with single input and output virtualization technology, default each virtual machine and is assigned paravirtualized virtual network interface card, and the virtual unit of single input and output virtualization is only assigned to the virtual machine positioned at critical path node after multilevel scheme divides, to achieve the purpose that improve universe network bandwidth availability ratio and reduce Parallel application overall execution time.
Description
Technical Field
The present application relates to computer virtualization technologies, and in particular, to a method, a system, and an electronic device for allocating virtual network resources.
Background
Parallel computing is now becoming more popular and widely accepted due to the ever decreasing cost of computer hardware and the ever increasing power of individual computers over the last few years. Meanwhile, in order to efficiently utilize the resources of the data center, a virtualization technology is often adopted to improve the resource utilization rate of the data center. The virtualization technology is a technology that can run multiple virtual machines on one physical machine, and the virtual machine is almost indistinguishable from the physical machine in the view of a user, application software, and even an operating system. Although this can greatly improve the resource utilization, it also brings about the problem of resource allocation among different virtual machines, and therefore, how to effectively allocate virtual resources and improve the resource utilization to the greatest extent has been widely concerned and studied.
In current parallel network and distributed network environments, parallel scheduling of network resources has become an extremely important technology to improve network performance. However, in the prior art, the data center application layer is disconnected from the bottom layer and the application is disconnected from the network, which inevitably causes a semantic gap in network resource scheduling, so that the operation of the whole system is lack of harmony, and the utilization rate of the network resources is not high.
Disclosure of Invention
The application provides a virtual network resource allocation method, a virtual network resource allocation system and electronic equipment, and aims to solve at least one of the technical problems in the prior art to a certain extent.
In order to solve the above problems, the present application provides the following technical solutions:
a virtual network resource allocation method comprises the following steps:
step a: generating a task graph according to network information of all virtual machines on a physical machine, and dividing the task graph by adopting a multi-level graph division algorithm to obtain k mutually disjoint division subsets;
step b: calculating the key path with the longest completion time in each segmentation subset to obtain a virtual machine positioned at a key path node;
step c: and distributing single-root input and output virtualized virtual equipment for the virtual machine at the key path node.
The technical scheme adopted by the embodiment of the application further comprises the following steps: the step a also comprises the following steps: collecting network information of all virtual machines on each physical machine; the collection mode of the network information is as follows: each virtual machine obtains network information for a pseudo file system provided by a user for accessing a kernel by reading a UNIX operating system, the network information obtained by the virtual machine is put into a storage system, and each physical machine storage system reads the network information of all the virtual machines and uploads the network information to a host.
The technical scheme adopted by the embodiment of the application further comprises the following steps: in the step a, the generating a task graph according to the network information of all the virtual machines on the physical machine and dividing the task graph by using a multi-level graph division algorithm specifically include: the host receives the network information uploaded by all the physical machines, generates a task graph with parameters according to the network information, and divides the task graph by adopting a multi-level recursive binary division method.
The technical scheme adopted by the embodiment of the application further comprises the following steps: the method for dividing the task graph by adopting the multi-stage recursive binary division method specifically comprises the following steps: the multi-stage recursive binary division method comprises three stages of coarsening, initial division and refinement, wherein the coarsening stage generates a series of aggregated graphs with smaller complexity after a task graph is input, the complexity of the task graph is reduced through the vertex of the maximum adjacent pair of the aggregated graphs, and the coarsening stage is ended when the complexity of the task graph is reduced to the number of preset vertices; and the initial division stage is used for initially dividing the task graph by using a heuristic algorithm, and the refinement stage is used for gradually recovering the initially divided task graph.
The technical scheme adopted by the embodiment of the application further comprises the following steps: in step b, the calculation formula of the critical path is:
PathCompTime(CP)≥PathCompTime(P)
in the above formula, path refers to a certain path in the task graph, PathSet refers to the whole path set in the task graph, pathcomp time refers to the time for all nodes in the path to complete execution, symbol P refers to an arbitrary path, and CP refers to a critical path.
Another technical scheme adopted by the embodiment of the application is as follows: a virtual network resource allocation system comprising a physical machine and a host machine, the host machine comprising:
a multi-level graph partitioning module: the system comprises a task graph generating module, a task graph generating module and a task graph dividing module, wherein the task graph generating module is used for generating a task graph according to network information of all virtual machines on a physical machine and dividing the task graph by adopting a multi-level graph dividing algorithm to obtain k mutually disjoint dividing subsets;
a critical path calculation module: the virtual machine is used for calculating the key path with the longest completion time in each segmentation subset to obtain a virtual machine positioned at a key path node;
a network resource allocation module: and the virtual device is used for distributing single-root input and output virtualization for the virtual machine at the key path node.
The technical scheme adopted by the embodiment of the application further comprises the following steps: the physical machine comprises a network resource monitoring module, and the network resource monitoring module is used for collecting network information of all virtual machines on the physical machine and uploading the collected network information to a network resource management module; the collection mode of the network information is as follows: each virtual machine obtains network information for a pseudo file system provided by a user for accessing a kernel by reading a UNIX operating system, the network information obtained by the virtual machine is put into a storage system, and each physical machine storage system reads the network information of all the virtual machines and uploads the network information to a network resource management module.
The technical scheme adopted by the embodiment of the application further comprises the following steps: the host machine also comprises a network resource management module, wherein the network resource management module is used for receiving the network information uploaded by all the physical machines and inputting the network information into the multi-level graph dividing module; the multi-level graph dividing module generates a task graph with parameters according to network information and divides the task graph by adopting a multi-level recursive binary division method.
The technical scheme adopted by the embodiment of the application further comprises the following steps: the method for dividing the task graph by adopting the multi-stage recursive binary division method specifically comprises the following steps: the multi-stage recursive binary division method comprises three stages of coarsening, initial division and refinement, wherein the coarsening stage generates a series of aggregated graphs with smaller complexity after a task graph is input, the complexity of the task graph is reduced through the vertex of the maximum adjacent pair of the aggregated graphs, and the coarsening stage is ended when the complexity of the task graph is reduced to the number of preset vertices; and the initial division stage is used for initially dividing the task graph by using a heuristic algorithm, and the refinement stage is used for gradually recovering the initially divided task graph.
The technical scheme adopted by the embodiment of the application further comprises the following steps: the calculation formula of the critical path is as follows:
PathCompTime(CP)≥PathCompTime(P)
in the above formula, path refers to a certain path in the task graph, PathSet refers to the whole path set in the task graph, pathcomp time refers to the time for all nodes in the path to complete execution, symbol P refers to an arbitrary path, and CP refers to a critical path.
The embodiment of the application adopts another technical scheme that: an electronic device, comprising:
at least one processor; and
a memory communicatively coupled to the at least one processor; wherein,
the memory stores instructions executable by the one processor to cause the at least one processor to perform the following operations of the virtual network resource allocation method described above:
step a: generating a task graph according to network information of all virtual machines on a physical machine, and dividing the task graph by adopting a multi-level graph division algorithm to obtain k mutually disjoint division subsets;
step b: calculating the key path with the longest completion time in each segmentation subset to obtain a virtual machine positioned at a key path node;
step c: and distributing single-root input and output virtualized virtual equipment for the virtual machine at the key path node.
Compared with the prior art, the embodiment of the application has the advantages that: the virtual network resource allocation method, the system and the electronic device adopt a mode of combining a semi-virtualization technology and a single-input-output virtualization technology to optimize a network, each virtual machine is allocated with a semi-virtualized virtual network card by default, and the single-input-output virtualized virtual device is only allocated to the virtual machine which is positioned at the key path node after the multi-level graph is divided, so that the purposes of improving the utilization rate of the overall network bandwidth and reducing the overall execution time of parallel application are achieved.
Drawings
Fig. 1 is a flowchart of a virtual network resource allocation method according to an embodiment of the present application;
fig. 2 is a schematic structural diagram of a virtual network resource allocation system according to an embodiment of the present application;
fig. 3 is a schematic structural diagram of a hardware device of a virtual network resource allocation method according to an embodiment of the present application.
Detailed Description
In order to make the objects, technical solutions and advantages of the present application more apparent, the present application is described in further detail below with reference to the accompanying drawings and embodiments. It should be understood that the specific embodiments described herein are merely illustrative of the present application and are not intended to limit the present application.
For the problems in the prior art, the Virtual network resource allocation method in the embodiment of the present application optimizes a network by combining a semi-Virtualization technology and a Single-Root I/O Virtualization technology (SR-IOV), each Virtual machine is assigned with a semi-virtualized Virtual network card by default, and a Single-Root I/O virtualized Virtual device (VF) is only assigned to a Virtual machine located at a critical path node after multi-level graph partitioning, so as to achieve the purposes of improving the overall network bandwidth utilization rate and reducing the overall execution time of parallel application.
Specifically, please refer to fig. 1, which is a flowchart illustrating a virtual network resource allocation method according to an embodiment of the present application. The virtual network resource allocation method of the embodiment of the application comprises the following steps:
step 100: collecting network information of all virtual machines on each physical machine, and uploading the collected network information to a host;
in step 100, the network information is collected in the following manner: each virtual machine obtains network information by reading a pseudo file system/proc/net/dev provided by a UNIX operating system for a user to access a kernel, the network information obtained by the virtual machine is put into a storage system (XenStore), each physical machine is respectively provided with a network resource monitoring module, and the network resource monitoring module reads the network information of each virtual machine through the XenStore and sends the network information to the network resource management module.
Step 200: receiving network information of all virtual machines on each physical machine through a host, generating a task graph with parameters, and dividing the task graph by adopting a multi-level graph division algorithm to obtain k mutually disjoint partition subsets;
in step 200, the host includes a network resource management module and a multi-level graph partitioning module, the network resource management module is responsible for receiving network information of all virtual machines on each physical machine, inputting the network information into the multi-level graph partitioning module, and generating a task graph with parameters, the multi-level graph partitioning module partitions the task graph by using a multi-level recursive binary partitioning method to obtain k mutually disjoint partition subsets, and tasks corresponding to different partition subsets are allocated to different physical machines for computation. According to the task graph partitioning method and device, the task graph is divided into multiple levels, so that the calculation amount among the physical machines is balanced, and the total communication amount among the physical machines is minimized.
Specifically, the multi-stage recursive binary division method comprises three stages of coarsening, initial division and refinement. The coarsening stage generates a series of aggregated graphs with smaller complexity after the task graph is input, aims to reduce the complexity of the task graph by aggregating the vertexes of the maximum adjacent pair of the graphs, and ends when the complexity of the task graph is reduced to a preset vertex number (usually, the vertex number is hundreds, and the specific vertex number can be set according to practical application). In the initial division stage, because the complexity of the task graph is small, the task graph is initially divided by using a classical simple heuristic algorithm such as a K-L algorithm. In the refinement stage, the initially divided task graph is gradually restored, and the converged vertexes are moved among different segmentation subsets, so that the division effect of the task graph is improved.
Step 300: calculating a key path with the longest completion time in each partition subset to obtain virtual machines positioned at key path nodes on each physical machine;
in step 300, since the communication overhead of the virtual machines between the same physical machine can be regarded as zero, the calculation of the critical path after the division of the task graph only calculates the communication overhead between different divided subsets. Specifically, the calculation formula of the critical path is as follows:
PathCompTime(CP)≥PathCompTime(P) (1)
in the formula (1), path refers to a certain path in the task graph, PathSet refers to the whole path set in the task graph, pathcomp time refers to the time for all nodes in the path to complete execution, symbol P refers to an arbitrary path, and CP refers to a critical path.
Step 400: distributing single-root input and output virtualized virtual equipment for the virtual machines at the key path nodes on each physical machine;
in step 400, the network resource allocation method according to the embodiment of the present application is that each virtual machine is assigned with a paravirtualized virtual network card by default, and a single input/output virtualized virtual device is only assigned to a virtual machine located at a critical path node after the multi-level graph is divided. The virtual machine uses the master network card to communicate when the master network card is effective, and uses the slave network card to communicate only when the master network card is ineffective, thereby reducing network overhead.
Step 500: judging whether all the segmentation subsets are executed or not, and executing the step 600 if all the segmentation subsets are executed; otherwise, returning to step 300 to continue calculating the critical path of the next segmentation subset until all the segmentation subsets are executed;
step 600: and the virtual network resource allocation is finished.
Please refer to fig. 2, which is a structural diagram of a virtual network resource allocation system according to an embodiment of the present application. The virtual network resource allocation system comprises a physical machine and a host machine, wherein the physical machine comprises a network resource monitoring module, and the host machine comprises a network resource management module, a multi-level graph dividing module, a key path calculation module, a network resource allocation module and a task execution judgment module.
A network resource monitoring module: the system comprises a network resource management module, a network resource management module and a virtual machine management module, wherein the network resource management module is used for collecting network information of all virtual machines on each physical machine and uploading the collected network information to the network resource management module; the network information collection method comprises the following steps: each virtual machine obtains network information by reading a pseudo file system/proc/net/dev provided by a UNIX operating system for a user to access a kernel, the network information obtained by the virtual machine is put into a XenStore, and the network resource monitoring module reads the network information of each virtual machine through the XenStore and sends the network information to the network resource management module.
A network resource management module: the system comprises a multi-level graph dividing module, a network information acquisition module, a network information processing module and a network information processing module, wherein the multi-level graph dividing module is used for receiving network information of all virtual machines on each physical machine and inputting the network information into the multi-level graph dividing module;
a multi-level graph partitioning module: the system comprises a task graph generating module, a task graph generating module and a task graph analyzing module, wherein the task graph generating module is used for generating a task graph with parameters according to input network information and dividing the task graph by adopting a multi-level graph dividing algorithm to obtain k mutually disjoint partition subsets; the multi-level graph partitioning module partitions the task graph by adopting a multi-level recursive binary partitioning method to obtain k mutually-disjoint partition subsets, and tasks corresponding to different partition subsets are allocated to different physical computers for calculation. According to the task graph partitioning method and device, the task graph is divided into multiple levels, so that the calculation amount among the physical machines is balanced, and the total communication amount among the physical machines is minimized.
Specifically, the multi-stage recursive binary division method comprises three stages of coarsening, initial division and refinement. The coarsening stage generates a series of aggregated graphs with smaller complexity after the task graph is input, and aims to reduce the complexity of the task graph by aggregating the vertexes of the maximum adjacent pair of the graphs, and the coarsening stage is ended when the complexity of the task graph is reduced to only hundreds of vertexes. In the initial division stage, because the complexity of the task graph is small, the task graph is initially divided by using a classical simple heuristic algorithm such as a K-L algorithm. In the refinement stage, the initially divided task graph is gradually restored, and the converged vertexes are moved among different segmentation subsets, so that the division effect of the task graph is improved.
A critical path calculation module: the virtual machine is used for calculating the key path with the longest completion time in each partition subset to obtain the virtual machine which is positioned at the key path node on each physical machine; since the communication overhead of the virtual machines among the same physical machine can be regarded as zero, the calculation of the critical path after the division of the task graph only calculates the communication overhead among different divided subsets. Specifically, the calculation formula of the critical path is as follows:
PathCompTime(CP)≥PathCompTime(P) (1)
in the formula (1), path refers to a certain path in the task graph, PathSet refers to the whole path set in the task graph, pathcomp time refers to the time for all nodes in the path to complete execution, symbol P refers to an arbitrary path, and CP refers to a critical path.
A network resource allocation module: the virtual equipment is used for distributing single-root input and output virtualization to the virtual machines at the key path nodes on the physical machines; the network resource allocation method of the embodiment of the application is that each virtual machine is allocated with a paravirtualized virtual network card by default, and a single input/output virtualized virtual device is only allocated to a virtual machine located at a key path node after multi-level graph division. The virtual machine uses the master network card to communicate when the master network card is effective, and uses the slave network card to communicate only when the master network card is ineffective, thereby reducing network overhead.
And a task execution judging module: the system is used for judging whether all the segmentation subsets are executed or not, and if all the segmentation subsets are executed, the virtual network resource allocation is finished; otherwise, the critical path calculation of the next segmentation subset is continuously calculated through the critical path calculation module until all the segmentation subsets are completely executed.
Fig. 3 is a schematic structural diagram of a hardware device of a virtual network resource allocation method according to an embodiment of the present application. As shown in fig. 3, the device includes one or more processors and memory. Taking a processor as an example, the apparatus may further include: an input system and an output system.
The processor, memory, input system, and output system may be connected by a bus or other means, as exemplified by the bus connection in fig. 3.
The memory, which is a non-transitory computer readable storage medium, may be used to store non-transitory software programs, non-transitory computer executable programs, and modules. The processor executes various functional applications and data processing of the electronic device, i.e., implements the processing method of the above-described method embodiment, by executing the non-transitory software program, instructions and modules stored in the memory.
The memory may include a storage program area and a storage data area, wherein the storage program area may store an operating system, an application program required for at least one function; the storage data area may store data and the like. Further, the memory may include high speed random access memory, and may also include non-transitory memory, such as at least one disk storage device, flash memory device, or other non-transitory solid state storage device. In some embodiments, the memory optionally includes memory located remotely from the processor, and these remote memories may be connected to the processing system over a network. Examples of such networks include, but are not limited to, the internet, intranets, local area networks, mobile communication networks, and combinations thereof.
The input system may receive input numeric or character information and generate a signal input. The output system may include a display device such as a display screen.
The one or more modules are stored in the memory and, when executed by the one or more processors, perform the following for any of the above method embodiments:
step a: generating a task graph according to network information of all virtual machines on a physical machine, and dividing the task graph by adopting a multi-level graph division algorithm to obtain k mutually disjoint division subsets;
step b: calculating the key path with the longest completion time in each segmentation subset to obtain a virtual machine positioned at a key path node;
step c: and distributing single-root input and output virtualized virtual equipment for the virtual machine at the key path node.
The product can execute the method provided by the embodiment of the application, and has the corresponding functional modules and beneficial effects of the execution method. For technical details that are not described in detail in this embodiment, reference may be made to the methods provided in the embodiments of the present application.
Embodiments of the present application provide a non-transitory (non-volatile) computer storage medium having stored thereon computer-executable instructions that may perform the following operations:
step a: generating a task graph according to network information of all virtual machines on a physical machine, and dividing the task graph by adopting a multi-level graph division algorithm to obtain k mutually disjoint division subsets;
step b: calculating the key path with the longest completion time in each segmentation subset to obtain a virtual machine positioned at a key path node;
step c: and distributing single-root input and output virtualized virtual equipment for the virtual machine at the key path node.
Embodiments of the present application provide a computer program product comprising a computer program stored on a non-transitory computer readable storage medium, the computer program comprising program instructions that, when executed by a computer, cause the computer to perform the following:
step a: generating a task graph according to network information of all virtual machines on a physical machine, and dividing the task graph by adopting a multi-level graph division algorithm to obtain k mutually disjoint division subsets;
step b: calculating the key path with the longest completion time in each segmentation subset to obtain a virtual machine positioned at a key path node;
step c: and distributing single-root input and output virtualized virtual equipment for the virtual machine at the key path node.
The virtual network resource allocation method, the system and the electronic device adopt a mode of combining a semi-virtualization technology and a single-input-output virtualization technology to optimize a network, each virtual machine is allocated with a semi-virtualized virtual network card by default, and the single-input-output virtualized virtual device is only allocated to the virtual machine which is positioned at the key path node after the multi-level graph is divided, so that the purposes of improving the utilization rate of the overall network bandwidth and reducing the overall execution time of parallel application are achieved.
The previous description of the disclosed embodiments is provided to enable any person skilled in the art to make or use the present application. Various modifications to these embodiments will be readily apparent to those skilled in the art, and the generic principles defined herein may be applied to other embodiments without departing from the spirit or scope of the application. Thus, the present application is not intended to be limited to the embodiments shown herein but is to be accorded the widest scope consistent with the principles and novel features disclosed herein.
Claims (11)
1. A virtual network resource allocation method is characterized by comprising the following steps:
step a: generating a task graph according to network information of all virtual machines on a physical machine, and dividing the task graph by adopting a multi-level graph division algorithm to obtain k mutually disjoint division subsets;
step b: calculating the key path with the longest completion time in each segmentation subset to obtain a virtual machine positioned at a key path node;
step c: and distributing single-root input and output virtualized virtual equipment for the virtual machine at the key path node.
2. The virtual network resource allocation method according to claim 1, wherein the step a further comprises: collecting network information of all virtual machines on each physical machine; the collection mode of the network information is as follows: each virtual machine obtains network information for a pseudo file system provided by a user for accessing a kernel by reading a UNIX operating system, the network information obtained by the virtual machine is put into a storage system, and each physical machine storage system reads the network information of all the virtual machines and uploads the network information to a host.
3. The virtual network resource allocation method according to claim 2, wherein in the step a, the generating a task graph according to the network information of all the virtual machines on the physical machine and dividing the task graph by using a multi-level graph division algorithm specifically includes: the host receives the network information uploaded by all the physical machines, generates a task graph with parameters according to the network information, and divides the task graph by adopting a multi-level recursive binary division method.
4. The virtual network resource allocation method according to claim 3, wherein the dividing the task graph by using the multi-level recursive binary division method specifically comprises: the multi-stage recursive binary division method comprises three stages of coarsening, initial division and refinement, wherein the coarsening stage generates a series of aggregated graphs with smaller complexity after a task graph is input, the complexity of the task graph is reduced through the vertex of the maximum adjacent pair of the aggregated graphs, and the coarsening stage is ended when the complexity of the task graph is reduced to the number of preset vertices; and the initial division stage is used for initially dividing the task graph by using a heuristic algorithm, and the refinement stage is used for gradually recovering the initially divided task graph.
5. The virtual network resource allocation method according to any one of claims 1 to 4, wherein in the step b, the calculation formula of the critical path is:
PathCompTime(CP)≥PathCompTime(P)
in the above formula, path refers to a certain path in the task graph, PathSet refers to the whole path set in the task graph, pathcomp time refers to the time for all nodes in the path to complete execution, symbol P refers to an arbitrary path, and CP refers to a critical path.
6. A virtual network resource allocation system comprising a physical machine and a host machine, wherein the host machine comprises:
a multi-level graph partitioning module: the system comprises a task graph generating module, a task graph generating module and a task graph dividing module, wherein the task graph generating module is used for generating a task graph according to network information of all virtual machines on a physical machine and dividing the task graph by adopting a multi-level graph dividing algorithm to obtain k mutually disjoint dividing subsets;
a critical path calculation module: the virtual machine is used for calculating the key path with the longest completion time in each segmentation subset to obtain a virtual machine positioned at a key path node;
a network resource allocation module: and the virtual device is used for distributing single-root input and output virtualization for the virtual machine at the key path node.
7. The virtual network resource allocation system of claim 6, wherein the physical machine comprises a network resource monitoring module, and the network resource monitoring module is configured to collect network information of all virtual machines on the physical machine and upload the collected network information to the network resource management module; the collection mode of the network information is as follows: each virtual machine obtains network information for a pseudo file system provided by a user for accessing a kernel by reading a UNIX operating system, the network information obtained by the virtual machine is put into a storage system, and each physical machine storage system reads the network information of all the virtual machines and uploads the network information to a network resource management module.
8. The virtual network resource allocation system of claim 7, wherein the host further comprises a network resource management module, and the network resource management module is configured to receive network information uploaded by all the physical machines and input the network information into the multi-level graph partitioning module; the multi-level graph dividing module generates a task graph with parameters according to network information and divides the task graph by adopting a multi-level recursive binary division method.
9. The virtual network resource allocation system according to claim 8, wherein the dividing the task graph by using the multi-stage recursive binary division method specifically comprises: the multi-stage recursive binary division method comprises three stages of coarsening, initial division and refinement, wherein the coarsening stage generates a series of aggregated graphs with smaller complexity after a task graph is input, the complexity of the task graph is reduced through the vertex of the maximum adjacent pair of the aggregated graphs, and the coarsening stage is ended when the complexity of the task graph is reduced to the number of preset vertices; and the initial division stage is used for initially dividing the task graph by using a heuristic algorithm, and the refinement stage is used for gradually recovering the initially divided task graph.
10. The virtual network resource allocation system according to any one of claims 6 to 9, wherein the calculation formula of the critical path is:
PathCompTime(CP)≥PathCompTime(P)
in the above formula, path refers to a certain path in the task graph, PathSet refers to the whole path set in the task graph, pathcomp time refers to the time for all nodes in the path to complete execution, symbol P refers to an arbitrary path, and CP refers to a critical path.
11. An electronic device, comprising:
at least one processor; and
a memory communicatively coupled to the at least one processor; wherein,
the memory stores instructions executable by the at least one processor to enable the at least one processor to perform the following operations of the virtual network resource allocation method of any one of 1 to 5 above:
step a: generating a task graph according to network information of all virtual machines on a physical machine, and dividing the task graph by adopting a multi-level graph division algorithm to obtain k mutually disjoint division subsets;
step b: calculating the key path with the longest completion time in each segmentation subset to obtain a virtual machine positioned at a key path node;
step c: and distributing single-root input and output virtualized virtual equipment for the virtual machine at the key path node.
Priority Applications (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201811430362.9A CN109412865B (en) | 2018-11-28 | 2018-11-28 | Virtual network resource allocation method, system and electronic equipment |
| PCT/CN2019/121297 WO2020108536A1 (en) | 2018-11-28 | 2019-11-27 | Virtual network resource allocation method and system and electronic device |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201811430362.9A CN109412865B (en) | 2018-11-28 | 2018-11-28 | Virtual network resource allocation method, system and electronic equipment |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN109412865A true CN109412865A (en) | 2019-03-01 |
| CN109412865B CN109412865B (en) | 2020-08-25 |
Family
ID=65455905
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201811430362.9A Active CN109412865B (en) | 2018-11-28 | 2018-11-28 | Virtual network resource allocation method, system and electronic equipment |
Country Status (2)
| Country | Link |
|---|---|
| CN (1) | CN109412865B (en) |
| WO (1) | WO2020108536A1 (en) |
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO2020108536A1 (en) * | 2018-11-28 | 2020-06-04 | 深圳先进技术研究院 | Virtual network resource allocation method and system and electronic device |
| CN111427912A (en) * | 2020-03-31 | 2020-07-17 | 拉卡拉支付股份有限公司 | Task processing method and device, electronic equipment and storage medium |
Families Citing this family (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN112330229B (en) * | 2020-12-02 | 2023-09-22 | 北京元心科技有限公司 | Resource scheduling method, device, electronic equipment and computer readable storage medium |
Citations (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO2015028931A1 (en) * | 2013-08-29 | 2015-03-05 | Ericsson Ab | A method and system to allocate bandwidth based on task deadline in cloud computing networks |
| US20150089495A1 (en) * | 2013-09-25 | 2015-03-26 | Arm Limited | Data processing systems |
| CN104536806A (en) * | 2014-12-26 | 2015-04-22 | 东南大学 | Workflow application flexible resource supplying method in cloud environment |
| CN105357322A (en) * | 2015-12-11 | 2016-02-24 | 中国科学院信息工程研究所 | Virtual machine distribution method based on topology partition |
| CN108205461A (en) * | 2016-12-19 | 2018-06-26 | 华耀(中国)科技有限公司 | The virtual platform and dispositions method of a kind of mixed deployment |
| CN110113184A (en) * | 2019-04-17 | 2019-08-09 | 中国科学院深圳先进技术研究院 | KVM virtual machine network optimization method and device under SR-IOV environment |
Family Cites Families (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN109412865B (en) * | 2018-11-28 | 2020-08-25 | 深圳先进技术研究院 | Virtual network resource allocation method, system and electronic equipment |
-
2018
- 2018-11-28 CN CN201811430362.9A patent/CN109412865B/en active Active
-
2019
- 2019-11-27 WO PCT/CN2019/121297 patent/WO2020108536A1/en active Application Filing
Patent Citations (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO2015028931A1 (en) * | 2013-08-29 | 2015-03-05 | Ericsson Ab | A method and system to allocate bandwidth based on task deadline in cloud computing networks |
| US20150089495A1 (en) * | 2013-09-25 | 2015-03-26 | Arm Limited | Data processing systems |
| CN104536806A (en) * | 2014-12-26 | 2015-04-22 | 东南大学 | Workflow application flexible resource supplying method in cloud environment |
| CN105357322A (en) * | 2015-12-11 | 2016-02-24 | 中国科学院信息工程研究所 | Virtual machine distribution method based on topology partition |
| CN108205461A (en) * | 2016-12-19 | 2018-06-26 | 华耀(中国)科技有限公司 | The virtual platform and dispositions method of a kind of mixed deployment |
| CN110113184A (en) * | 2019-04-17 | 2019-08-09 | 中国科学院深圳先进技术研究院 | KVM virtual machine network optimization method and device under SR-IOV environment |
Non-Patent Citations (1)
| Title |
|---|
| 曲桦: "《一种基于SDN的CCN集中控制缓存决策方法》", 《电信科学》 * |
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO2020108536A1 (en) * | 2018-11-28 | 2020-06-04 | 深圳先进技术研究院 | Virtual network resource allocation method and system and electronic device |
| CN111427912A (en) * | 2020-03-31 | 2020-07-17 | 拉卡拉支付股份有限公司 | Task processing method and device, electronic equipment and storage medium |
Also Published As
| Publication number | Publication date |
|---|---|
| WO2020108536A1 (en) | 2020-06-04 |
| CN109412865B (en) | 2020-08-25 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| WO2022037337A1 (en) | Distributed training method and apparatus for machine learning model, and computer device | |
| US11521067B2 (en) | Decentralized distributed deep learning | |
| Yang et al. | A framework for partitioning and execution of data stream applications in mobile cloud computing | |
| US9367359B2 (en) | Optimized resource management for map/reduce computing | |
| US11455322B2 (en) | Classification of time series data | |
| US11501160B2 (en) | Cloud computing data compression for allreduce in deep learning | |
| US20190377606A1 (en) | Smart accelerator allocation and reclamation for deep learning jobs in a computing cluster | |
| CN109412865B (en) | Virtual network resource allocation method, system and electronic equipment | |
| US11429450B2 (en) | Aggregated virtualized compute accelerators for assignment of compute kernels | |
| EP2671152A1 (en) | Estimating a performance characteristic of a job using a performance model | |
| US9471387B2 (en) | Scheduling in job execution | |
| Nguyen et al. | Deadlock detection for resource allocation in heterogeneous distributed platforms | |
| US8028291B2 (en) | Method and computer program product for job selection and resource allocation of a massively parallel processor | |
| US9069621B2 (en) | Submitting operations to a shared resource based on busy-to-success ratios | |
| CN107204998B (en) | Method and device for processing data | |
| US20200272526A1 (en) | Methods and systems for automated scaling of computing clusters | |
| US10824481B2 (en) | Partial synchronization between compute tasks based on threshold specification in a computing system | |
| CN111914987A (en) | Data processing method and device based on neural network, equipment and readable medium | |
| Wang et al. | On optimal budget-driven scheduling algorithms for MapReduce jobs in the hetereogeneous cloud | |
| WO2017031961A1 (en) | Data processing method and apparatus | |
| US10630957B2 (en) | Scalable distributed computation framework for data-intensive computer vision workloads | |
| CN110955644A (en) | IO control method, device, equipment and storage medium of storage system | |
| KR102248978B1 (en) | Resource Allocation Method and Apparatus for Reducing the Expected Latency in Distributed Machine Learning with Multiple Users | |
| US20240111604A1 (en) | Cloud computing qos metric estimation using models | |
| CN115729704A (en) | Computing power resource allocation method, device and computer readable storage medium |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |