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

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.我们接下来证明,找到最优的容器编排策略等同于找到最大子集和问题的解决办法.最优的容器编排策
   283   284   285   286   287   288   289   290   291   292   293