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
G
p
=
{
V
p
,
E
p
}
,
V
p
represents a collection of physical nodes in an edge computing system and
E
p
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
=
r
e
s
(
V
p
i
)
/
Δ
, where
r
e
s
(
V
p
i
)
means resource of a physical machine
V
p
i
. 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
V
n
e
w
=
{
}
and let
E
n
e
w
=
{
}
.
II、
Combining Weak Physical Nodes to One VM
-
In the collection
E
p
, we select the edge
e
=
<
u
,
v
>
that is biggest link weight value and node
u
is an element of the collection of
V
′
p
and not in the collection
V
n
e
w
. When there are multiple choices, we choose the biggest one and put
v
into collection
V
n
e
w
and put
e
into collection
E
n
e
w
. Repeat this operation until all nodes in
V
′
p
are traversed and form a new collection
T
=
{
V
n
e
w
,
E
n
e
w
}
. -
Removing some low weighted edges in
T
to form a forest
F
=
{
f
w
}
and
r
e
s
(
f
w
)
>
Δ
. -
Physical nodes and virtual physical nodes of all the trees in the forest
F
<script type=”math/tex” id=”MathJax-Element-8719″>F</script> 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.