Making up VMs from Many Weak Nodes of Edge Computing

·¢²¼ÓÚ£º2021-10-25 10:58:15

In last blog we have discuss virtualization and using virtual machine to provide services for users. However, differences between cloud computing and edge computing make it impossible to apply theories of creating VMs and load balance mechanisms of cloud computing to edge computing directly. Firstly, resources of smart edge devices that make up edge computing nodes are relatively small and limited. Besides, due to the physical nodes of fog computing join and quit system frequently, tasks and resource change dynamically.

A graph repartition method is proposed by Song Ningning et al. to solve the above problem of edge computing[1]. The main idea of it is that dividing powerful physical machine into several virtual machine nodes and combining a number of weak physical machine to one virtual machine.

I¡¢Dividing Powerful Physical Machine Nodes to Several VMs

The physical nodes in an edge computing system can be expressed as a non-directed and weight value connected graph

Gp={Vp,Ep}
,

Vp
represents a collection of physical nodes in an edge computing system and

Ep
represents a collection of link between physical nodes.

We assume that resource required by a standard VM in this system is noted as

¦¤
. If resource of a physical machine greater than

¦¤
, then it will be divided into

k
VMs and a virtual physical node. k can be obtained by using this formula:

k=res(Vpi)/¦¤
, where

res(Vpi)
means resource of a physical machine

Vpi
. A virtual physical node is composed by remnant resource that is not enough to make up one VM after removing

k
VMs from original physical machine.
All virtual physical nodes and original physical nodes that are smaller than ¦¤ are in collection

V¡äp
. Initializing

Vnew={}
and let

Enew={}
.

II¡¢Combining Weak Physical Nodes to One VM

In the collection

Ep
, we select the edge

e=
that is biggest link weight value and node

u
is an element of the collection ofV¡äp and not in the collection

Vnew
. When there are multiple choices, we choose the biggest one and put

v
into collection Vnew and put

e
into collection Enew. Repeat this operation until all nodes in

V¡äp
are traversed and form a new collection

T={Vnew,Enew}
.Removing some low weighted edges in

T
to form a forest F={fw} and

res(fw)>¦¤
.Physical nodes and virtual physical nodes of all the trees in the forest

F
$F$ are aggregated to form a virtual machine node.When physical nodes come in or drop out of the system, the system should repeat this algorithm to obtain a new partition scheme.

The process can be shown in the following picture.

Original Paper: Ningning, Song & Chao, Gong & Xingshuo, An & Qiang, Zhan. (2016). Fog computing dynamic load balancing mechanism based on graph repartitioning. China Communications. 13. 156-164. 10.1109/CC.2016.7445510.