Optimal dynamic cloud network control
Various exemplary embodiments relate to a network node in a distributed dynamic cloud, the node including: a memory; and a processor configured to: observe a local queue backlog at the beginning of a timeslot, for each of a plurality of commodities; compute a processing utility weight for a first commodity based upon the local queue backlog of the first commodity, the local queue backlog of a second commodity, and a processing cost; where the second commodity may be the succeeding commodity in a service chain; compute an optimal commodity using the processing utility weights; wherein the optimal commodity is the commodity with the highest utility weight; assign the number of processing resource units allocated to the timeslot to zero when the processing utility weight of the optimal commodity is less than or equal to zero; and execute processing resource allocation and processing flow rate assignment decisions based upon the optimal commodity.
1. A network node in a distributed dynamic cloud network, the network node comprising:
a memory; and
a processor configured to observe a local queue backlog, for each of a plurality of commodities, wherein each commodity represents a respective network flow at a given stage of a service chain, compute a processing utility weight for each of the plurality of commodities based upon the local queue backlog of the plurality of commodities, and the local queue backlog of another commodity, wherein the other commodity is the succeeding commodity in the service chain, compute an optimal commodity using the processing utility weights, wherein the optimal commodity is the commodity with a highest utility weight, assign a number of processing resource units allocated to a timeslot to zero when the processing utility weight of the optimal commodity is less than or equal to zero, and execute processing resource allocation and processing flow rate assignment decisions based upon the optimal commodity.
2. The network node of claim 1 , wherein the processor is further configured to observe a neighbor queue backlog of a neighbor of the network node at the beginning of the timeslot, for each of the plurality of commodities; and compute a transmission utility weight for each of the plurality of commodities based upon the observed neighbor queue backlog, a local queue backlog of the network node, and a transmission cost.
3. The network node of claim 2 , wherein the processor is further configured to compute an optimal commodity using the transmission utility weights, where the optimal commodity is the commodity with a highest utility weight.
4. The network node of claim 3 , wherein the processor is further configured to assign the number of transmission resource units allocated to the timeslot to zero when transmission utility weight is less than or equal to zero.
5. The network node of claim 4 , wherein the processor is further configured to execute transmission resource allocation and transmission flow rate assignment decisions based upon the optimal commodity.
6. The network node of claim 5 , wherein the processor is further configured to: introduce a bias term into the transmission utility weight, where the bias term represents a number of hops and/or a geometric distance to a destination.
7. The network node of claim 1 , wherein the processor is further configured to, for each commodity (d,ϕ,m), compute the processing utility weight as such:
W
i
(
d
,
ϕ
,
m
)
(
t
)
=
1
r
(
ϕ
,
m
+
1
)
[
Q
i
(
d
,
ϕ
,
m
)
(
t
)
-
ξ
(
ϕ
,
m
[
0.6
]
+
1
)
Q
i
(
d
,
ϕ
,
m
[
0.6
]
+
1
)
(
t
)
-
Ve
i
]
+
,
where the processing utility weight W i (d,ϕ,m) (t) indicates a benefit of executing function (ϕ,m+1) to process commodity (d,ϕ,m) into commodity (d,ϕ,m+1) at time t , in terms of a local backlog reduction per processing unit cost.
8. The network node of claim 7 , wherein the processor is further configured to compute the optimal commodity (d,ϕ, m)* according to:
(
d
,
ϕ
,
m
)
*
=
argmax
(
d
,
ϕ
,
m
)
{
W
i
(
d
,
ϕ
,
m
)
(
t
)
}
.
9. The network node of claim 8 , wherein the processor is further configured to: assign a number of allocated resource units k*=0 when W ij (d,ϕ,m)* (t)=0; and otherwise assign
k
*
=
argmax
k
{
C
i
,
k
W
i
(
d
,
ϕ
,
m
)
*
(
t
)
-
Vw
i
,
k
}
.
10. The network node of claim 9 , wherein the processor is further configured to perform the following resource allocation and flow rate assignment decisions:
y
i
,
k
*
(
t
)
=
1
y
i
,
k
(
t
)
=
0
∀
k
≠
k
*
μ
i
,
pr
(
d
,
ϕ
,
m
)
*
(
t
)
=
1
r
(
ϕ
,
m
+
1
)
*
C
i
,
k
*
μ
i
,
pr
(
d
,
ϕ
,
m
)
(
t
)
=
0
∀
(
d
,
ϕ
,
m
)
≠
(
d
,
ϕ
,
m
)
*
.
11. A method of optimizing cloud control on a network node in a distributed dynamic cloud, the method comprising:
observing a local queue backlog at, for each of a plurality of commodities, wherein each commodity represents a respective network flow at a given stage of a service chain;
computing a processing utility weight for each of the plurality of commodities based upon the local queue backlog of the plurality of commodities, the local queue backlog of another commodity, wherein the other commodity is the succeeding commodity in the service chain;
computing an optimal commodity using the processing utility weights, wherein the optimal commodity is the commodity with a highest utility weight;
assigning a number of processing resource units allocated to a timeslot to zero when the processing utility weight of the optimal commodity is less than or equal to zero; and
executing processing resource allocation and processing flow rate assignment decisions based upon the optimal commodity.
12. The method of claim 11 , further comprising:
observing a neighbor queue backlog of a neighbor of the network node at the beginning of the timeslot, for each of the plurality of commodities; and
computing a transmission utility weight for each of the plurality of commodities based upon the observed neighbor queue backlog, a local queue backlog of the network node, and a transmission cost.
13. The method of claim 12 , further comprising:
computing an optimal commodity using the transmission utility weights, where the optimal commodity is the commodity with a highest utility weight.
14. The method of claim 13 , further comprising:
assigning a number of transmission resource units allocated to the timeslot to zero when transmission utility weight is less than or equal to zero.
15. The method of claim 14 , further comprising:
executing transmission resource allocation and transmission flow rate assignment decisions based upon the optimal commodity.
16. The method of claim 15 , further comprising:
introducing a bias term into the transmission utility weight, where the bias term represents a number of hops and/or a geometric distance to a destination.
17. The method of claim 11 , further comprising:
for each commodity (d,ϕ,m), computing the processing utility weight as such:
W
i
(
d
,
ϕ
,
m
)
(
t
)
=
1
r
(
ϕ
,
m
+
1
)
[
Q
i
(
d
,
ϕ
,
m
)
(
t
)
-
ξ
(
ϕ
,
m
[
0.6
]
+
1
)
Q
i
(
d
,
ϕ
,
m
[
0.6
]
+
1
)
(
t
)
-
Ve
i
]
+
,
where the processing utility weight W i (d,ϕ,m) (t) indicates a benefit of executing function (ϕ,m+1) to process commodity (d,ϕ,m) into commodity (d,ϕ,m+1) at time t, in terms of a local backlog reduction per processing unit cost.
18. The method of claim 17 , further comprising:
computing the optimal commodity (d,ϕ,m)* according to:
(
d
,
ϕ
,
m
)
*
=
argmax
(
d
,
ϕ
,
m
)
{
W
i
(
d
,
ϕ
,
m
)
(
t
)
}
.
19. The method of claim 18 , further comprising:
assigning k*=0 when W ij (d,ϕ,m)* (t)=0; and
otherwise assigning
k
*
=
argmax
k
{
C
i
,
k
W
i
(
d
,
ϕ
,
m
)
*
(
t
)
-
Vw
i
,
k
}
.
20. The method of claim 19 , further comprising:
performing the following resource allocation and flow rate assignment decisions:
y
i
,
k
*
(
t
)
=
1
;
y
i
,
k
(
t
)
=
0
∀
k
≠
k
*
;
μ
i
,
pr
(
d
,
ϕ
,
m
)
*
(
t
)
=
1
r
(
ϕ
,
m
+
1
)
*
C
i
,
k
*
;
and
μ
i
,
pr
(
d
,
ϕ
,
m
)
(
t
)
=
0
∀
(
d
,
ϕ
,
m
)
≠
(
d
,
ϕ
,
m
)
*
.