Page 288 - 《软件学报》2021年第12期

3952 Journal of Software 软件学报 Vol.32, No.12, December 2021

和 p exit 分别表示入口容器和出口容器所在的集群,那么用户 u 到 p entry 和 p exit 的延迟我们也简单表示为 d entry 和
d exit .
另外,为了表示某个容器是否被编排到某个边缘集群,我们令 f(c,p)表示为
⎧ 1, 容器 c被编排到集群 p上
(, )p = ⎨
fc .
⎩ 0, 容器 c不被编排到集群 p上
对于用户 u 提交的任务,当容器被编排到对应的集群时,任务的计算延迟包括 3 部分:一部分是在服务器上
的计算消耗时间,一部分是容器间的通信时间,另一部分是用户传送数据给容器所在的边缘服务器的延迟.我们
定义容器 c 的实际开始执行时间(actual start time)为 AST(c)和实际完成执行时间(actual finish time)为 AFT(c).
类似地,我们定义将容器 c 在集群 p 上最早的开始执行时间(earliest start time)为 EST(c,p),并且:
EST (c , )p = ( d u , , )c p + max{avail [ ],maxp c m pred∈ ()c (AFT (c m ) ω+ ( , ))}c c .
m
其中,avail[p]表示为集群 p 准备好执行容器 c 的时间,而公式后面的 max 函数指的是集群 p 等待执行完容器 c
的父容器的最大时间.特别地,对于入口容器 c entry ,它的最早开始执行时间为用户到入口容器所在的集群延迟,
即 EST(c entry ,p entry )=d entry .我们同时定义容器 c 在集群 p 上的最早完成执行时间(earliest finish time)为 EFT(c,p),
其中,该值的大小包括容器 c 的执行时间加上最早执行时间,即:
EFT (, )c p = t + c EST ( , ).c p
我们指出,EST(c,p)和 EFT(c,p)的值可以通过迭代的方式计算得到.同时,当容器已经确认被编排到某个计
算集群上时,它在集群上的最早执行时间就等于实际开始执行时间;同时,它在集群上的最晚完成时间就等于实
际完成实行时间.在本文中,我们的目标是让所有任务的计算延迟最小(其中包括各个容器在集群上的计算时
间、容器间的数据通信时间以及用户到容器的延迟).因此,算法的目标是让某个任务的最后一个出口容器的计
算延迟最小,同时满足设备的闲置资源和容器的资源需求,我们将其形式化为
min max AFT (c exit )
s.t. ∑ rc f ( , )c p ≤ I ( )p
( )×
∈
∈
cC , p P
3.2 编排算法
我们指出,存在最优算法得到计算延迟最小的容器编排策略.最优算法的主要思路是:遍历所有满足限制要
求的容器编排策略,并最终选出一个计算延迟最小的编排方案.我们指出:只要等待足够长的时间,最优算法始
终能计算出最优的容器编排方案,任务的计算延迟也必然是最小的.但是,最优算法不能够在线性时间内解决,
这对于一个实际应用的系统显然是不合适的.接下来,我们会证明使用最优算法来得到最优的容器编排策略是
一个 NP 难的问题.
定理 1. 找到一个最优的容器编排策略是一个 NP 难问题.
证明:在线性时间内,验证一个给定的容器编排策略是可行的.因此,找到一个最优的容器编排策略属于 NP
问题的范畴.为了证明该问题是一个 NP 难问题,我们将最大子集和问题归约为最优容器编排问题.其中,最大子
集和问题已经被证明为 NP 完全问题 [16] .最大子集和问题是:给定一个有限集合 Q,对于每一个 q∈Q,都有一个特
定的值 v(q)∈Z 、一个正整数 B∈Z ,找到一个子集 Q′⊆Q,让 ∑ vq B 并 且 ∑ vq
+
+
() 最小化.
()≤
qQ′ qQ′
∈
∈
假设现在有两个边缘计算集群 p A 和 p B ,并假设用户 u 到它们的延迟分别为 d(u,p A )和 d(u,p B ),其中, d(u,p A )
的值很小,而 d(u,p B )的值很大.同时假设 p A 和 p B 的可分配算力为θ(p A )和θ(p B ),并假设θ(p A )的值很大,而θ(p B )的值
很小.并且假设任务在 p A 预计完成的时间很短,而 p B 预计完成的时间很长.因此,对于待编排容器列表
C={c 1 ,c 2 ,…,c m }来说,如果有更多的容器被编排到 p A ,那么系统就能取得更好的计算时间性能.
令 Q 代表待编排的容器,并且每一个容器 c 都会请求 p A 的服务,同时,r(c)|c∈C 等同于 v(q)|q∈Q.由于 d(u,p A )
与 d(u,p B )以及θ(p A )与θ(p B )之间的值相差很大,因此 p A 是唯一可选的边缘计算平台,并且令它的闲置资源
I(p A )=B.我们接下来证明,找到最优的容器编排策略等同于找到最大子集和问题的解决办法.最优的容器编排策