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

杨术 等:功能分发网络:基于容器的智能边缘计算平台 3951

3 容器编排

3.1 问题定义
定义的记号见表 1.
Table 1 Notation list
表 1 记号表
符号 意义 符号 意义
P 边缘计算集群集合 r(c) 容器 c 运行时所需要的资源
p 一个边缘计算集群 δ(c) 容器 c 的计算量
θ(p) 集群 p 能分配的算力大小 c t 容器 c 的平均计算时间
u 一个用户 I(p) 计算设备 p 的闲置资源
J=(V,E) 一个计算任务以及对应的图结构 f(c,p) 容器 c 是否被编排到设备 p 上
ω(c i,c j) 容器 c i 和 c j 的通信代价 EST(c,p) 容器 c 在集群 p 上的最早执行时间
C 任务运行时的容器集合 EFT(c,p) 容器 c 在集群 p 上的最早完成时间
c 任务运行时的一个容器 AST(c) 容器 c 的实际开始时间
prev(c) 容器 c 的父容器集合,早于 c 计算 AFT(c) 容器 c 的实际完成时间
succ(c) 容器 c 的子容器集合,晚于 c 计算
在 FDN 系统中,定义 P={p 1 ,p 2 ,…,p n }为系统中的 n 个边缘计算集群集合,其中,p i ∈L(1≤i≤n)表示第 i 个边
缘计算集群.当一个用户 u 申请 FDN 服务时,它会向中心控制器提供该计算任务 J 运行时所需要的容器镜像信
息.对于一个计算任务 J,它可能存在着多个子任务,而且这些子任务之间存在着一定的依赖关系,执行时需要遵
循一定的先后顺序.任务 J 可抽象成一个有向无环图 J=(V,E),其中,V={v 1 ,v 2 ,…,v |V| }表示子任务集合,而 E=
{e 1 ,e 2 ,…,e |E| }表示子任务间的数据依赖关系.对于节点 v a 到节点 v b ,假设它们之间存在有向边(e a ,e b )从节点 v a 指
向节点 v b ,表示只有先执行节点 v a 才能执行节点 v b .对于一个节点 v,我们将它的父节点集合和子节点集合分别
定义为 prev(v)和 succ(v);同时,我们假设对于每一个任务 J,它都会存在唯一的入口任务(entry job,也称为 v entry ),
而出口任务(exit job,也称为 v exit )可能有多个.也就是说:入口任务的 v entry 入度为 0,而出口任务 v exit 的出度大于等
于 0.当任务在被调度和编排的时候,系统都会从 v entry 开始执行,并且最终某一个 v exit 结束计算.我们令执行入口
任务的容器称为 c entry ,令执行出口程序的容器称为 c exit .
对于任务 J,我们假设它运行时可分配的容器集合为 C={c 1 ,c 2 ,…,c m },其中,c i ∈C 代表每一个独立的容器.我
们假设每一个子任务 j 都由一个独立的容器 c 进行计算,因此一个任务 J 的执行需要由多个容器间的协同工作
来完成.由于子任务之间存在着一定的数据依赖,因此容器的编排顺序也受到了要求;同时,容器间也存在着数
据通信.当容器 c i 和 c j 被编排到两个不同的边缘计算集群时,定义通信代价为ω(c i ,c j ),其中,ω(c i ,c j )为正整数.而如
果容器 c i 和 c j 被编排到相同的边缘计算集群,那么通信代价为 0,即ω(c i ,c j )=0.由于中心云到边缘云的延迟比较
稳定,而且容器在边缘会有缓存时间,所以用户后续上传的数据都可以享受低延迟的服务.在本文中,我们主要
考虑用户的流量调度,暂不考虑中心云下发容器的过程延时.在以后的研究中,我们将会进一步研究容器从中心
云下放到边缘云的延迟这一重要因素.
对于每一个容器 c,当它被编排到某一个边缘计算集群时,需要集群内的机器花一定时间进行计算.我们假
设容器 c 的计算量为δ(c),其中,δ(c)为正整数,并且假设边缘计算集群 p 当前的闲置算力为θ(p),θ(p)也为正整数.
那么容器 c 在系统中的平均完成时间可以表示为
c ∑
t = δ ()c n .
pP θ ()p
∈
每一个容器都会有对于计算设备的需求,我们把容器 c 的需求(包括内存、存储等)定义为 r(c),其中,r(c)的
值为正整数;同时,对于集群 p∈P,它都会有当前闲置的资源量,我们将其定义为 I(p),并且 I(p)为正整数.如果容器
c 要在集群 p 上顺利运行,那么 c 的计算需求必须小于等于 p 的闲置资源,即 r(c)≤I(p).
在容器计算的过程中,用户需要实时把数据传送给对应的容器进行计算.定义 d(u,c,p)为用户 u 到容器 c 所
在的边缘计算集群 p 的延迟.为了简单起见,令每 d(u,c,p)在 0 到 1 之间变化,也就是 0≤d(u,c,p)≤1.我们令 p entry