读论文[23][ICC]Multiple Resource Allocation in Multi-Tenant Edge Computing via Sub-modular Optimization

Multiple Resource Allocation in Multi-Tenant Edge Computing via Sub-modular Optimization

Published in: ICC 2023 - IEEE International Conference on Communications

1 背景与挑战

边缘计算(EC)允许用户访问网络前沿的计算资源，这为部署移动增强现实(MAR)等对延迟敏感的应用铺平了道路。在EC的概念中，计算和存储资源部署在接入网的边缘。移动设备上的几个MAR客户端可以向边缘计算(EC)服务器发送包含传感器和摄像机捕获的原始数据的MAR请求。此时，专用的计算硬件(例如图形处理单元(GPU)和中央处理单元(CPU))和软件(例如基于计算机视觉的算法)处理这些数据，然后将结果(例如对象分类或空间坐标信息)返回给移动设备。
当多个MAR服务提供商(sp)在网络边缘争夺有限的资源时，资源分配成为一个关键挑战。

2 贡献

我们解决了在边缘有多个有限资源的情况下，向竞争的异构sp分配资源的问题。
我们首先使用Erlang队列模型对流的到达和服务动态建模。
然后，在背包约束下，利用子模sub-modular极大化的方法，给出了每个sp的资源分配问题。
接下来，我们提出了一种所谓的流算法来解决分配问题，并获得了一个近似最优值，其中d是资源类型的数量，而λ是一个可控的误差项。
我们最终提供了数值结果来显示所得到的系统性能显著优于基线资源分配策略。

3 系统建模

我们考虑一个有一个网络运营商(NO)的设置，拥有一组资源R，并愿意在P个不同的服务提供商sp之间共享。然后，每个SP都可以使用其分配的共享，就好像它在边缘部署了专用硬件一样。

3.1 请求模式

SP p的MAR用户到达EC服务器遵循泊松过程，速率λp以用户/秒表示。一旦任何SP的用户连接到边缘服务器，就会创建一个会话。此会话的有效期为Tp，在此期间用户可以在该MAR应用程序中执行一系列交互。单个会话可以包含多个活动，所有这些活动都在用户连接时临时存储在会话中。每个SP在边缘运行一个虚拟服务器，例如Kubernetes POD。MAR用户与各自SP的虚拟服务器建立会话。在该会话中，它发送图像处理请求流。
当用户将其MAR设备指向一个对象时，从MAR设备摄像机中获取原始视频，并将其剪切成具有特定图像格式的帧，如JPEG和PNG，然后发送到边缘服务器[5]。视频帧被传送到AR跟踪器，以确定用户相对于物理环境的位置。根据跟踪结果，映射器可以建立环境的虚拟坐标。然后，利用具有鲁棒特征的目标识别器对视频帧中的内部目标进行识别。MAR设备最终从边缘服务器下载对象的信息。增强现实信息以叠加在物体上的3d“体验”的形式呈现。因此，用户看到的是半真实半虚拟的。由于MAR需要高数据速率、超低延迟和可能使用轻量级设备，因此在5G移动网络的边缘执行处理可以帮助保证MAR应用的要求([1]的Section III-F)。
**我们假设SP p的单个用户的会话需要一定数量的资源r，记为zrp。如果SP在边缘没有如此多的可用资源，用户将与云建立会话，从而遭受更长的延迟。一旦SP的用户被边缘服务，他的会话将被关闭并离开EC系统。**请注意，用户可以在他们决定的时候离开系统，这并不否认我们可以定义SP的平均服务率。

3.2 资源分区

NO在网络边缘拥有CPU和RAM，例如，在与城域规模的(微型)基站或中心办公室共存的服务器中。CPU的总容量为KCPU, RAM的总容量为KRAM。

3.3服务模式

我们将我们的系统建模为Erlang队列，该队列建模泊松到达，指数分布的服务时间，以及与系统中位置数量相等的服务器数量，即用户要么直接在边缘服务，要么直接服务于云。在我们的例子中，SP p的用户根据泊松分布到达边缘，平均到达率为λp，他们在系统中停留的时间为指数分布的时间Tp。
SP p的每个用户都有固定的资源需求，固定分配。
在我们的示例中，服务器数是指边缘可以容纳每个SP的最大会话数，具体如下所示。当由NO决定的资源分配为
时，我们用
表示SP p在边缘可以服务的最大用户数。

3.4 效用模型

如果SP p的用户能够满足z RAM p和z CPU p的需求，则SP p的用户直接由边缘服务。否则，相应的会话将不被接受(按照排队论的术语，我们称之为“阻塞”)并定向到远程云服务器。使用Erlang([17]的式(3.45))，SP用户被阻塞的概率为

直接在边缘建立会话的用户感知到的效用是UE，而如果会话与云在一起，则效用是UC(?，不知道此常数怎么来的)。这些效用考虑了处理每个用户请求的延迟对体验质量(QoE)的影响，考虑了到达云的更大延迟。因此，UE > UC > 0。为简单起见，我们假设所有sp的UE和UC是相同的。由于1−Bp表示SP p用户与边缘建立会话的比例，根据总概率定理，SP p用户感知到的效用期望值为:

根据总期望定理，一般用户感知到的效用为：

3.5 优化问题

NO的目的是最大化一般用户感知到的效用的预期价值:

将(8)代入上式，考虑到UC和UE是常数，则优化目标变为：

3.6 SUB-MODULAR优化

4 实验结果

4.1 实验设置

专注于一个边缘节点，它与一个为2个服务提供商提供服务的中心共存。我们将到达率λ1和λ2分别设置为20和5个用户/s，离开率µ1和µ2分别设置为1和10个用户/s。我们考虑一个类似于G4dn的边缘服务器。KRAM = 384 GB的总内存容量和第二代Intel Xeon可扩展CPU: Cascade Lake P-8259L, CPU总容量KCPU = 96 vCPU。考虑到类似于Pokemon GO的AR应用[21]，我们将SP 1和SP 2的RAM和CPU需求分别设置为:z RAM 1 = 2 GB, z CPU 1 = 1 vCPU, z RAM 2 = 0.5 GB和z CPU 2 = 4 vCPU。

4.2 结果

我们在图1a中绘制了算法1得到的解:目标函数f，它是用户与边缘(12)建立会话的概率，我们将我们的解与基线fprop进行比较，即按用户到达率成比例地将资源分配给sp时获得的与边缘建立会话的概率。在图1b中，我们显示了当λ1变化时，每个SP的阻塞概率的变化。λ1的增加导致SP 1的阻塞概率更高，这是预期的，因为更多的用户将在边缘消耗更多的资源，而剩下的资源更少。较高的λ1也会影响SP 2，但影响程度要小得多。
在资源利用率方面，我们绘制了图2。结果表明，CPU被两个sp完全利用(图2b)，而RAM没有被充分利用(如图2a所示小于20%)。

在图3中，我们绘制了一个热图，描述了关于两种到达率变化的全局目标函数f。
显然，在较低的到达率下(暗红色区域f≥0.95)，算法的性能更好。

由于CPU是阻塞资源，我们在图4中评估了系统相对于两个sp的每个用户所需的CPU量的灵敏度。首先，我们将算法和fprop得到的目标函数f、f1和f2绘制在图4a中。结果表明，无论SP 1用户对CPU的需求如何，流式算法都优于基准分配。在图4b中，我们绘制了描述流式算法获得的全局目标函数f随CPU需求变化的热图。该算法在最多5vcpu左右的要求下保持令人满意的性能(暗红色到浅绿色区域)，然后随着CPU要求的提高，性能迅速下降。

5 评价

考虑了多用户情况下的资源分配问题，但是只涉及单MEC，不涉及多MEC之间的选择。同时设定SP p的每个用户都有固定的资源需求，固定分配，这显然是不合理的。优化目标的建模虽然考虑了用户群体，但是不能充分反映用户QoE。