论文标题
放置还不够
Placement is not Enough: Embedding with Proactive Stream Mapping on the Heterogenous Edge
论文作者
论文摘要
边缘计算自然适合由物联网（IoT）节点生成的应用程序。物联网应用程序通常采用定向无环图（DAG）的形式，其中顶点代表相互依赖的函数，边缘代表数据流。最小化DAG的制造物的现状激发了研究最佳功能放置的研究。但是，当前的方法忽略了将数据流的主动映射到异质边缘服务器之间的物理链接，这可能会严重影响DAG的Makepan。为了解决此问题，我们同时研究数据分组的功能放置和流映射，并提出算法DPE（基于动态编程的嵌入）。理论上已验证DPE以实现嵌入问题的全局最优性。还提供了复杂性分析。在阿里巴巴群集跟踪数据集上进行的广泛实验表明，DPE的表现明显优于MakePAN中的两个最先进的联合功能放置和任务调度算法，分别为43.19％和40.71％。
Edge computing is naturally suited to the applications generated by Internet of Things (IoT) nodes. The IoT applications generally take the form of directed acyclic graphs (DAGs), where vertices represent interdependent functions and edges represent data streams. The status quo of minimizing the makespan of the DAG motivates the study on optimal function placement. However, current approaches lose sight of proactively mapping the data streams to the physical links between the heterogenous edge servers, which could affect the makespan of DAGs significantly. To solve this problem, we study both function placement and stream mapping with data splitting simultaneously, and propose the algorithm DPE (Dynamic Programming-based Embedding). DPE is theoretically verified to achieve the global optimality of the embedding problem. The complexity analysis is also provided. Extensive experiments on Alibaba cluster trace dataset show that DPE significantly outperforms two state-of-the-art joint function placement and task scheduling algorithms in makespan by 43.19% and 40.71%, respectively.
