Partitioning Stateful Data Stream Applications in Dynamic Edge Cloud Environments

Partitioning Stateful Data Stream Applications in Dynamic Edge Cloud Environments

动态边缘云环境下的有状态数据流应用的划分

摘要

计算分区是一种通过选择性地将一些计算从移动设备卸载到附近的边缘云来提高应用程序性能的重要技术。在动态环境中，边缘云的网络带宽可能会频繁变化，计算的划分需要相应地更新。分区的频繁更新导致了移动端和边缘云之间的高状态迁移成本。但是，现有的工作没有考虑状态迁移开销。因此，分区决策可能会导致重大的拥塞控制，并极大地增加整体完成时间。本文在考虑状态迁移开销的基础上，提出了一套基于网络带宽变化的分区更新算法。据我们所知，这是第一个针对动态环境中的有状态数据流应用程序进行计算分区的工作。这些算法旨在通过在动态边缘云环境中选择性迁移状态来减轻拥塞控制和最小化制造跨度。大量的仿真结果表明，该算法不仅可以选择性地迁移状态，而且在生成时间方面优于其他经典的基准算法。所提出的模型和算法将丰富有状态任务的调度理论，这是以前从未有过的研究。

介绍

边缘计算是使云计算技术能够从传统的互联网数据中心到网络边缘进行低延迟数据访问和实时数据处理[7]。作为边缘计算资源的抽象，边缘云通常分布在离终端用户较近的地方，如蜂窝基站和无线局域网。边缘计算的一般形式包括 Cloudlets [9]和 Foglets [10] ，甚至还有一小群有限的设备[8]。与传统的云数据中心相比，边缘云更轻量级，资源受限[11]。随着边缘云在当今网络基础设施中的部署越来越多，计算分区被认为是一种有效的技术，通过选择性地将一些计算从移动设备卸载到附近的边缘云[4][12][18]来提高移动应用程序的性能

为了达到不同的目的，在计算分区方面存在许多相关的工作，比如减少执行时间，节省终端设备的能源消耗，以及云的数据传输开销。这些工作对应用程序有不同的建模方法。典型的应用程序模型包括面向过程程序的方法调用树、面向服务应用程序的服务调用图和面向数据流应用程序的数据流图。/n在这些类型的应用程序中，数据流应用程序越来越受到关注，例如扩增实境和目标跟踪。应用程序由一组功能模块组成，数据流通过这些模块。数据流应用程序的分区旨在为每个传入的数据帧决定哪些函数在本地执行，哪些函数在边缘云中执行[4][12]。但是，现有的工作不考虑有状态数据流应用程序的分区。如果数据流应用程序包含有状态函数模块，我们将其定义为有状态应用程序。通过状态函数模块，如果一个数据帧流经它，那么在处理该模块的设备上将留下一个“足迹”。这个“内存占用”(也由状态命名)是下一个数据帧的处理所需要的。许多应用程序(如对象跟踪)都属于有状态应用程序。

对有状态数据流应用程序进行分区非常具有挑战性，尤其是在动态边缘云环境中，在这种环境中，到边缘云的网络连接经常发生变化，甚至可能发生断开连接。由于网络连接的动态性，应用程序的划分需要相应地更新，这将导致移动设备和边缘云之间的状态迁移。因此，我们需要通过选择性迁移状态来划分计算，以减轻网络拥塞。现有的计算划分工作考虑了应用程序的无状态功能模块。当它们应用于有状态应用程序的分区时，网络中会出现较高的状态迁移开销，这可能导致拥塞控制和应用程序的长时间完成。这就是为什么我们需要为有状态应用程序的分区特别设计新的方法，旨在平衡良好的分区和低完成时间以及网络上额外的状态迁移时间。

在本文中，我们开发了一套有效的算法来解决有状态数据流应用程序的划分问题，目的是通过选择性迁移 ing 状态来减少拥塞控制和最小化使用时间。特别地，我们设计了一种新的算法，即基于得分矩阵的启发式算法(SM-H)来解决一次性问题，该算法在边缘网络环境改变时更新当前到达数据帧的划分。SM-H 采用矩阵形式记录调整各模块执行位置的效益得分，然后始终选择得分最大的模块进行调整。调整是迭代进行的，直到没有一个模块得到正分，这意味着调整任何一个模块将导致完成时间的增加。在一次性 SM-H 算法的基础上，进一步推广到解决多步骤的分区问题。

我们通过大量的仿真对提出的算法进行评估，并将它们与几种基准方法进行比较，包括顺序调整(一种幼稚的贪婪启发式方法)、列表调度(一种经典的并行和分布式计算调度方法)、遗传算法等。结果表明，所提出的算法在制作跨度方面优于基准算法。我们将本文的贡献总结如下。

•据我们所知，我们是第一个研究有状态数据流应用程序分区问题的人。这些问题模型可以推广到分布式处理器上的有状态任务调度，这是目前在任务调度领域尚未研究的问题。/n

•我们开发了一种新算法来划分有状态数据流应用程序。该算法丰富了有状态应用任务的调度理论和方法。/n

•我们通过广泛的仿真对提出的算法进行了评估，结果表明，提出的 SM-H 算法在制作跨度方面优于基准算法。

系统模型和问题制定

定义决策变量表示分配给状态迁移、网络传输的网络带宽，将最小化make-span制定为目标并表示，限制模块之间的依赖性定义，从而定义对状态迁移的限制、对网络带宽的限制

最终形成有状态的数据流应用程序计算分区问题(SCPP)，