Open AccessArticle

Task Containerization and Container Placement Optimization for MEC: A Joint Communication and Computing Perspective

Ao Liu

^1,2,

Shaoshi Yang

^1,2,*

Jingsheng Tan

^1,2,

Zongze Liang

^1,2,

Jiasen Sun

^1,2,

Tao Wen

³ and

Hongyan Yan

School of Information and Communication Engineering, Beijing University of Posts and Telecommunications, Beijing 100876, China

Key Laboratory of Universal Wireless Communications, Ministry of Education, Beijing 100876, China

China Mobile Research Institute, Beijing 100053, China

Author to whom correspondence should be addressed.

Processes 2023, 11(5), 1560; https://doi.org/10.3390/pr11051560

Submission received: 6 December 2022 / Revised: 16 March 2023 / Accepted: 19 March 2023 / Published: 19 May 2023

(This article belongs to the Special Issue Application of Machine Learning and Hybrid Optimization Algorithms in IoT Engineering)

Download

Browse Figures

Figure 1
A system model for user terminals to access an MEC-based computing network. "> Figure 2
An example of DAG workflow with ten tasks. "> Figure 3
Comparison of the normalized maximum load performance (defined by Equation (<a href="#FD22-processes-11-01560" class="html-disp-formula">22</a>)) of various task partitioning algorithms, including the proposed P-NCPI and P-RI algorithms, and the classic K-means algorithm. "> Figure 4
Comparison of the average CPU utilization efficiency of the MEC-based computing network (defined by Equation (<a href="#FD24-processes-11-01560" class="html-disp-formula">24</a>)), when using the proposed four task-containerization-and-container-placement algorithms and the Spread algorithm. "> Figure 5
Comparison of the average MEM utilization efficiency of the MEC-based computing network (defined by Equation (<a href="#FD25-processes-11-01560" class="html-disp-formula">25</a>)), when using the proposed four task-containerization-and-container-placement algorithms and the Spread algorithm. "> Figure 6
Comparison of the balance degree of multi-type computing resource utilization (defined by Equation (<a href="#FD10-processes-11-01560" class="html-disp-formula">10</a>)), when using the proposed four task-containerization-and-container-placement algorithms and the Spread algorithm. "> Figure 7
Comparison of the running time of different task-containerization-and-container-placement algorithms. "> Figure 8
The ratio of the inter-container communication overhead to the inter-task communication overhead when using different task-containerization-and-container-placement algorithms. ">

Versions Notes

Abstract

Containers are used by an increasing number of Internet service providers to deploy their applications in multi-access edge computing (MEC) systems. Although container-based virtualization technologies significantly increase application availability, they may suffer expensive communication overhead and resource use imbalances. However, so far there has been a scarcity of studies to conquer these difficulties. In this paper, we design a workflow-based mathematical model for applications built upon interdependent multitasking composition, formulate a multi-objective combinatorial optimization problem composed of two subproblems—graph partitioning and multi-choice vector bin packing, and propose several joint task-containerization-and -container-placement methods to reduce communication overhead and balance multi-type computing resource utilization. The performance superiority of the proposed algorithms is demonstrated by comparison with the state-of-the-art task and container scheduling schemes.

Keywords:

edge computing; cloud computing; container; joint communication and computing; workflow; computing power network; computing force network

1. Introduction

The container technique has been increasingly adopted in operating system virtualization by cloud computing and edge computing due to its high convenience and flexibility in deploying diverse applications [1]. The lightweight, scalable, and well-isolated environment provided by containers greatly increases the applications’ portability and availability [2], but at the cost of excessive communication overhead and resource utilization imbalance. Therefore, reducing communication overhead and balancing the usage of multi-type computing resources are critical design challenges for container-based multi-access edge computing (MEC).

Zhang et al. [3] studied the joint task scheduling and containerization in an edge computing system, where the tasks associated with a given application were first scheduled into processors deployed on an edge server, then an appropriate algorithm was invoked to determine the containerization scheme. As a result, multiple containers, each representing a standard unit of software for packaging code and all related dependencies, were created for executing different tasks on individual processors, while considering the time cost of inter-container communications. Workflow is a common model for describing microservice-based application’s tasks executed in containers. Bao et al. [4] presented a microservice-based workflow scheduling algorithm for minimizing the end-to-end delay of a given single application consisting of multiple microservices under a pre-specified budget constraint in a cloud, where the inter-container communication latency was considered a component of the end-to-end delay. A dual-line container placement algorithm was proposed in [5] to decide the container placement positions in a container cluster while being aware of the inter-container communication traffic. We note that all of the above contributions concentrated on reducing communication overhead while ignoring computing resource utilization problems. Naturally, allocating the containers of the same application into the same server is beneficial for reducing the cost of inter-container communications. However, this will cause serious resource utilization imbalance, since the same type of computing resource is usually used intensively by different containers of the same application, e.g., a CPU-intensive application [6]. Hence, without a proper resource-utilization balanced container scheduler, the particular server may suffer exponentially increasing response latency [7], and the total throughput of the system may be significantly reduced.

Therefore, it is important to also consider the balanced use of computing resources when designing scheduling algorithms. Since each task has a different computing resource requirement, Li et al. [8] considered the problem of scheduling microservice tasks of workflow applications to containers configured on on-demand virtual machines (VMs) and suggested a heuristic task scheduling algorithm for guaranteeing that the precedence-constrained or independent tasks are scheduled to available containers. As a benefit, the computing resources were more efficiently utilized. Ye et al. [9] explored the stochastic hybrid workflow scheduling problem to keep the cost of computing resources to the minimum, by jointly scheduling offline and online workflows. Although these contributions considerably improve the utilization efficiency of computing resources, they impose high communication overhead, because the containers of the same application have to exchange control messages and payload data. Therefore, the effectiveness of communications among containers has a significant impact on how well services are provided.

How to keep computing resource utilization balanced while reducing inter-container communication costs remains a grave challenge. In order to reduce the total inter-container communication traffic and increase the utilization efficiency of computing resources, Wu et al. [10] proposed a container placement strategy for containerized data centers, by exploiting the inter-container communication traffic pattern that obeys a Zipf-like distribution. They assumed that the major communication traffic originates from the containers that intensively communicate with each other. Each group of such containers is treated as an individual container block, which can be deployed either on the same server or on different servers, and the authors further assumed that the communication traffic between container blocks is negligible. Unfortunately, this assumption is unreasonable in the context of collaborative MEC servers. In [11], the computing resource requirements of containers are represented by a flow network, and container scheduling is formulated as a minimum-cost flow problem. To properly prioritize the execution of containers subject to a batch of concurrent requests, the proposed approach of [11] considered the average life cycle of containers as well as the affinity between the containers and the servers. Their solution took container affinity into account and placed containers with affinity on the same server. However, it is improper for scheduling container clusters with high dependencies. Lv et al. [6] studied container placement and container reassignment strategies to balance resource use in large-scale Internet data centers, where the initial container distribution is optimized further by reassigning containers among servers. However, as far as a large number of distributed MEC servers are concerned, migrating containers among these servers may incur significant communication overhead.

Furthermore, the widely used container orchestration platforms, such as Docker, only provide simple rule-based scheduling principles. Therefore, there has been a scarcity of efforts that focus on container scheduling algorithms capable of jointly reducing the communication overhead and balancing the computing resource usage in MEC.

Against the above backdrop, in this paper, our novel contributions are summarized as follows.

We propose a task containerization and container placement optimization framework for applications running on MEC servers from a joint communication and computing perspective. The proposed framework comprises two modules. The task containerization module jointly considers low inter-container communication overhead and balanced multi-type computing resource requirements of containers. The container placement module places instantiated containers to the appropriate MEC servers by considering the balanced usage of the multi-type computing resources on MEC servers. The proposed framework is capable of achieving both low communication overhead and balanced computing resource requirement among containers, as well as balanced computing resource utilization among servers. To the best of our knowledge, our work is the first to investigate the impact of task partitioning, task containerization, and container placement on inter-container communication overhead and resource utilization balancing.
We offer a workflow modeling method for highly interdependent tasks of an application and propose a mathematical model of the workflow to reflect the interactions among the tasks, the communication overhead, and the computing resources needed by each task. Based on the workflow model of tasks, we present a method for calculating the communication overhead and the utilization efficiency deviation of multi-type computing resources in the MEC-based computing network considered. The proposed model and methods are directly applicable to various workflow-based cloud computing and edge computing platforms.
We evaluate the proposed task-containerization -and-container-placement algorithms in multiple aspects through extensive experiments, and compare them with state-of-the-art methods. Our experiments show that the proposed methods are capable of reducing the communication overhead by up to 74.10%, decreasing the normalized maximum load by up to 60.24%, improving the CPU utilization efficiency by up to 30.66%, and improving the memory utilization efficiency by up to 40.77% under the considered system configurations.

The rest of this paper is organized as follows. In Section 2, we present the MEC system model. In Section 3, we formulate the problem of jointly reducing the communication overhead and improving the degree of balance for multi-type computing resource utilization, which is solved by the algorithms proposed in Section 4, where the original problem is divided into two subproblems, namely the task containerization problem that is formulated as a graph partitioning problem [12], and the container placement optimization problem that is formulated as a multi-choice vector bin packing problem [13], which is a generalization of the classic vector bin packing problem. In Section 5, the proposed algorithms are compared with state-of-the-art methods by extensive simulations, and our conclusions are drawn in Section 6.

2. System Model

As shown in Figure 1, we consider the use case where Internet service providers set up and execute delay-sensitive applications in a computing network composed of multiple MEC servers. The MEC servers are deployed at the edge of a mobile network and connected to base stations (BSs). The user terminals (UTs) can access diverse delay-sensitive computing-intensive services, such as cloud gaming and cloud virtual reality (VR), provided by the MEC-based computing network through BSs. All the MEC servers are distributively connected to each other by optic fibers, so that their computing power can be shared via cooperation.

The MEC servers are represented by

S = {s_{1}, s_{2}, \dots, s_{S}}

, where

S = |S|

is the number of servers. In the entire MEC service process, computing resources

R = {r_{1}, r_{2}, \dots, r_{R}}

, such as CPU, memory and disk storage, are involved, where

R = |R|

is the number of resource types. For server

s_{i} \in S

, let

γ_{s_{i}, r_{k}}

denote the capacity of resource

r_{k} \in R

. We consider an application composed of multiple interdependent tasks

T = {t_{1}, t_{2}, \dots, t_{T}}

, and the number of tasks is

T = |T|

. Let the matrix

E = {[e_{i j}]}_{T \times T}

represent dependencies between tasks, and we have

e_{i j} = \{\begin{matrix} 1, & if task t_{i} sends data to task t_{j} \\ 0 . & otherwise \end{matrix}

(1)

The tasks are allocated to the container cluster

C = {c_{1}, c_{2}, \dots, c_{C}}

, which comprises

C = |C|

containers. For container

c_{i} \in C

β_{c_{i}, r_{k}}

denotes the demand for resource

r_{k} \in R

. For each task

t_{i}

, let vector

v_{i} = (v_{i}^{(r_{1})}, v_{i}^{(r_{2})}, \dots, v_{i}^{(r_{R})})

represent the individual volumes of various resources required by task

t_{i}

. Note that in order to eliminate the difficulties encountered in evaluating the usage of heterogeneous resources, in this paper the volume of a specific type of resource required is normalized as the ratio of this partial volume to the total volume of the available resources of the same type across all the servers considered. The matrix

D = {[d_{i j}]}_{T \times C}

represents the tasks deployment, where we have

d_{i j} = \{\begin{matrix} 1, & if task t_{i} is assigned to container c_{j} \\ 0 . & otherwise \end{matrix}

(2)

The resource

r_{k}

demanded by the container

c_{j}

is the sum of the resources required by the tasks assigned to

c_{j}

, namely

β_{c_{j}, r_{k}} = \sum_{i = 1}^{T} d_{i j} v_{i}^{(r_{k})} .

(3)

Let the matrix

M = {[m_{i j}]}_{C \times S}

denote the container placement strategy, as expressed by

m_{i j} = \{\begin{matrix} 1, & if container c_{i} is placed in server s_{j} \\ 0 . & otherwise \end{matrix}

(4)

3. Problem Formulation

3.1. Communication Overhead

We consider the communication overhead incurred by the communications between containers within an MEC-based computing network. Typically, the life cycle of a task includes three stages: receiving data, running algorithms, and sending output data. For example, task

t_{i}

first receives the data and stores it in memory, then it runs algorithms upon obtaining all the input information it needs. Finally, when the execution is finished, task

t_{i}

sends the output data to related tasks, which takes a transmission time of

τ_{t_{i}}

. This is also the communication time between containers, once the tasks are assigned to containers.

Let

F = {[f_{i j}]}_{C \times C}

denote the container dependency matrix. Upon assuming that the communication time between tasks assigned to the same container is negligible, the element of

F

can be expressed as:

f_{i j} = \{\begin{matrix} \sum_{q}^{T} \sum_{p}^{T} d_{p i} τ_{t_{p}} e_{p q} d_{q j}, & i \neq j \\ 0 . & i = j \end{matrix}

(5)

Similarly, we formulate the server dependency matrix as

G = {[g_{i j}]}_{S \times S}

, where we have

g_{i j} = \{\begin{matrix} \sum_{q}^{C} \sum_{p}^{C} m_{p i} f_{p q} m_{q j}, & i \neq j \\ 0 . & i = j \end{matrix}

(6)

Upon assuming that the packet size and the number of packets required in each occurrence of communication remain constant, the communication overhead in the MEC-based computing network can be modeled as the ratio of the time spent in sending data between servers to the total communication time, namely

C_{OH} (D, M) = \frac{\sum_{i}^{S} \sum_{j}^{S} g_{i j}}{\sum_{i = 1}^{T} τ_{t_{i}}} .

(7)

Computing Resource Utilization Balance

The efficiency of servers is often degraded by the unbalanced use of the various computing resources deployed on the servers. The resource

r_{k}

used by all the containers residing in the server

s_{i}

is quantified by

β_{s_{i}, r_{k}} (D, M) = \sum_{j = 1}^{C} m_{j i} β_{c_{j}, r_{k}} .

(8)

Since the total available resource

r_{k}

on the server

s_{i}

γ_{s_{i}, r_{k}}

. Then,

u_{s_{i}, r_{k}} (D, M) = \frac{β_{s_{i}, r_{k}} (D, M)}{γ_{s_{i}, r_{k}}}

represents the utilization efficiency of resource

r_{k}

on server

s_{i}

. Typically, if a server’s consumption of different types of computing resources is relatively balanced, the server is able to host more containers and more applications. Then, the balance degree of multi-type computing resource utilization on server

s_{i}

is given by

b_{i} = \sum_{k = 1}^{R} \frac{{(u_{s_{i}, r_{k}} (D, M) - {\bar{u}}_{s_{i}})}^{2}}{R},

(9)

where

{\bar{u}}_{s_{i}}

is the mean utilization efficiency of all resources on server

s_{i}

This metric reflects the deviation of the utilization efficiency of all resource types on a server from the average resource utilization efficiency. The total resource balance degree of the MEC-based computing network is the sum of the resource balance degree of all servers, and it is defined as

B_{tot} (D, M) = \sum_{i = 1}^{S} b_{i} .

(10)

Therefore, the joint optimization of the communication overhead and the degree of resource utilization balance is formulated as a weighted-sum minimization problem of

\begin{matrix} P 1 : min_{D, M} & μ_{C} C_{OH} (D, M) + μ_{B} B_{tot} (D, M) \end{matrix}

(11a)

\begin{matrix} s . t . & D \in {0, 1}^{T \times C}, \end{matrix}

(11b)

\begin{matrix} M \in {0, 1}^{C \times S}, \end{matrix}

(11c)

\begin{matrix} \sum_{j = 1}^{C} d_{i j} = 1, \end{matrix}

(11d)

\begin{matrix} \sum_{j = 1}^{S} m_{i j} = 1, \end{matrix}

(11e)

\begin{matrix} 0 \leq β_{s_{i}, r_{k}} (D, M) \leq γ_{s_{i}, r_{k}} . \end{matrix}

(11f)

In the above optimization problem,

τ_{t_{i}} \geq 0

v_{t}^{(r_{k})} \geq 0

0 \leq μ_{C} \leq 1

0 \leq μ_{B} \leq 1

t_{i} \in T

s_{i} \in S

r_{k} \in R

, and

c_{j} \in C

are all constants known a priori. Here,

τ_{t_{i}} \geq 0

indicates that the transmission time of each task is non-negative;

v_{t}^{(r_{k})} \geq 0

indicates that each task has a non-negative demand for each type of resource; while

0 \leq μ_{C} \leq 1

and

0 \leq μ_{B} \leq 1

specify the value range of the weights corresponding to each of the component objectives. (11b) and (11c) indicate that the optimization variables are matrices composed of binary-value elements. Equations (11d) and (11e) imply that each given task

t_{i}

and given container

c_{i}

have to be allocated to a single container and a single server, respectively. Furthermore, (11f) represents that the resource

r_{k}

used by all the containers residing in the server

s_{i}

must not exceed the capacity of the resource

r_{k}

on the server

s_{i}

It is worth noting that reducing communication overhead may lead to putting more tasks into fewer containers and packing as many containers as possible into fewer servers. However, this may result in a lower utilization efficiency of computing resources in the servers. In other words, there is a trade-off between the communication overhead

C_{OH}

and the computing resource utilization efficiency

B_{tot}

. We attempt to balance

C_{OH}

and

B_{tot}

rather than cram as many items as possible in a container or a server.

The problem

P 1

is essentially a multi-objective combinatorial optimization problem involving two subproblems, namely graph partitioning [12] that is corresponding to task containerization and multi-choice vector bin packing [13] that is corresponding to container placement, as shown in Figure 1. Both of them are known NP-hard problems. Hence, the existence of any polynomial time optimal solution is ruled out unless

P = NP

. Furthermore, as mentioned before, the component objectives

C_{OH}

and

B_{tot}

may conflict with each other, and both of them rely on the optimization variables

D

and

M

. Theoretically, the optimal solution to

P 1

can be found by brute-force search. However, in practice, there may be a large number of tasks, containers, and servers to deal with. Hence, the computational complexity of obtaining the optimal solution to the joint optimization problem

P 1

is prohibitive. Alternatively, it is possible to solve

P 1

more efficiently by using an iterative method, where at each iteration, the objective of

P 1

is minimized with respect to one of the two matrix variables

D

and

M

while the other matrix variable is held fixed. Nevertheless, the deployment of this strategy may require a dedicated centralized computing server to run the scheduling algorithms and is not naturally aligned with the physically sequential processes of an MEC-based computing network, where the task containerization takes place first and is then followed by container placement. In other words, in practice, it is meaningful to first obtain

D

and then obtain

M

relying on the result of

D

With this in mind, we turn our attention to a degenerate version of

P 1

so that the reformulated problem is more naturally matched to the practical sequential process of deploying an application to servers. As a result, a non-iterative sequential strategy can be invoked, which is expected to find good solutions capable of optimizing both the inter-container communication overhead and the degree of resource utilization balance at the expense of lower computational complexity. More specifically, the goal of task containerization is to minimize the weighted-sum of the inter-container communication overhead and the average deviation of multi-type resource demands by each container. Thus, we have

\begin{matrix} P 2 : min_{D} & μ_{C} \frac{\sum_{i = 1}^{C} \sum_{j = 1}^{C} f_{i j}}{\sum_{i = 1}^{T} τ_{t_{i}}} + μ_{B} \sum_{k = 1}^{R} \sum_{j = 1}^{C} \frac{{(β_{c_{j}, r_{k}} - {\bar{β}}_{r_{k}})}^{2}}{C} \end{matrix}

(12a)

\begin{matrix} s . t . & D \in {0, 1}^{T \times C}, \end{matrix}

(12b)

\begin{matrix} \sum_{j = 1}^{C} d_{i j} = 1, \end{matrix}

(12c)

where

{\bar{β}}_{r_{k}}

represents the average value of all containers’ demand for resource

r_{k}

. As pointed out before, dividing tasks into groups and putting each group of tasks into a container can essentially be formulated as a graph partitioning problem [12]. Different from the traditional treatment of graph partitioning problems, in this paper we not only take into account the weights of edges, which represent the communication overhead but also consider the weights of vertices, which represent the resource requirements of a particular task.

Furthermore, we simplify the container placement problem without considering the communication overhead caused by inter-container communications and the communication time between servers in the objective function. This is because the servers’ geographic locations have a significant impact on the communication overhead between servers and it can be difficult to ascertain the servers’ locations. After the task containerization module obtains

D

, the container placement module is intended to minimize the deviation of the utilization efficiency of various computing resources on the MEC servers, hence the container placement problem is formulated as:

\begin{matrix} P 3 : min_{M} & μ_{B} \sum_{i = 1}^{S} \sum_{k = 1}^{R} \frac{{(u_{s_{i}, r_{k}} (M) - {\bar{u}}_{s_{i}})}^{2}}{R} \end{matrix}

(13a)

\begin{matrix} s . t . & M \in {0, 1}^{C \times S}, \end{matrix}

(13b)

\begin{matrix} \sum_{j = 1}^{S} m_{i j} = 1, \end{matrix}

(13c)

\begin{matrix} 0 \leq u_{s_{i}, r_{k}} (M) \leq 1 . \end{matrix}

(13d)

The container placement problem is similar to the multi-choice vector bin packing problem [13]. In contrast to the traditional multidimensional vector bin packing problem, we have a set number of servers and a range of resource capacities for each server. The components of our vector set come from the containers obtained during the task containerization stage. Container values are not 0 or 1, but rather a vector of distinct forms of resource requirements as containers have different types of computing resource requirements. Our objective is more complicated—instead of minimizing the number of servers, placing containers into MEC servers requires matching the resources the containers need with what the servers can provide.

On the basis of making references to classic problems, it is vital to create solutions that are more fitting for our objectives. The fourth chapter will provide detailed explanations of the specific approach.

4. Task Containerization and Container Placement Schemes

As shown in Figure 1, the entire process of performing edge computing in an MEC-based computing network can be sequentially divided into two stages: first allocating tasks to containers, and then placing containers onto servers. To find a high-accuracy approximate solution to the problem (11), we can consider the task containerization and the container placement sequentially.

4.1. Task Containerization Method

A task containerization method is invoked to allocate tasks to containers. First of all, it is necessary to balance all types of resources needed by each container for achieving an equalized consumption of resources on each server. To this end, it is preferable to avoid grouping tasks that have a high demand for the same type of resource together. On the other hand, it is recommended to put tasks that have a large amount of data transmitted between each other into the same container and then place the containers having frequent communications with each other on the same server, in order to reduce the communication overhead.

We use workflow to describe the relationship between different tasks of an application. Workflow is an important concept for describing cloud computing and edge computing applications. It consists of multiple interdependent tasks which are bound together through data or functional dependencies. As shown in Figure 2, an application can be built as a workflow, where each task implements certain functionality and collaborates with the others. In Figure 2 the workflow is modelled, as a directed acyclic graph (DAG)

G = (T, E)

. Each vertex

t_{i} \in T

represents a task, and the weight vector of vertex

t_{i}

v_{i}

, which represents various resources required by

t_{i}

. The adjacency matrix of the DAG is

E

and its elements are defined by (1), where the weights of edges are not considered. The number of edges is denoted as E, i.e.,

|E| = E

, which equals the number of nonzero elements in

E

. Furthermore, let

ω (e_{i j})

denote the weight of

e_{i j}

and it represents the length of communication time from task i to task j. Then, the elements

e_{i j}

E

are updated as

ω (e_{i j})

For a cluster of vertices

A \subseteq T

, let

E (A, A)

denote the set of edges with all vertices in

A

, and let

E (A, T ∖ A)

represent the collection of edges connecting the two disjoint vertex sets of the graph cut

(A, T ∖ A)

. Furthermore, define a vertex set

P = (A_{1}, A_{2}, \dots, A_{C})

as multiple disjoint vertex sets whose union is

T

, i.e., we have

⋃_{i = 1}^{C} A_{i} = T

and

A_{i} \cap A_{j} = \emptyset

\forall i \neq j

C \geq 1

. Furthermore, we denote with

v_{A_{i}}^{(k)}

the demand of resource

r_{k}

by the subset

A_{i}

It has been established that the graph partitioning problem is NP-hard. For finding approximate solutions to the graph partitioning problem considered more efficiently, we propose two heuristic algorithms in this paper, i.e., the partitioning with non-critical path based initialization (P-NCPI) and the partitioning with random initialization (P-RI). The major operations of the proposed partitioning algorithms include determining the number of disjoint vertex sets, assigning one vertex to each of the disjoint vertex sets in the initial partition, and setting a scoring function for the remaining vertices. Both vertex weights and edge weights are taken into account in the scoring function, and each vertex is exclusively assigned to one of the disjoint vertex sets based on its score. Typically, these operations can be implemented in an appropriate container orchestration software, such as Kubernetes or KubeEdge. This process guarantees that the vertices are partitioned so that the edge weights between the disjoint vertex sets are minimal and that the vertex weights within the disjoint vertex sets are not excessive.

The NCPI and RI algorithms employed in our initial partition are described as follows.

NCPI: Tasks are sorted topologically, and the critical path is chosen as the one with the highest weight. The tasks that comprise the critical path are known as essential tasks, and they determine the minimum completion time of an application. Due to the high communication overhead between essential tasks, we first select the required number of non-essential tasks and then assign each non-essential task to a different disjoint vertex set as an initial partition to reduce communication overhead between sets.
RI: Selecting the desired tasks randomly according to the number of disjoint vertex sets and assigning each of them to a different disjoint vertex set as an initial partition.

To more conveniently describe the process of grouping the remaining vertices, we consider an alternative objective function with two components: the cost of inter-partition edge weights

C_{e}

and the cost of intra-partition vertex weights

C_{v}

. For each given set of vertices

P = (A_{1}, A_{2}, \dots, A_{C})

and a specific resource

r_{k}

, this objective function is defined as:

\begin{matrix} f (P) & = μ_{C} C_{e} (Ω (E (A_{1}, T ∖ A_{1})), \dots, Ω (E (A_{C}, T ∖ A_{C}))) \\ + μ_{B} C_{v} (v_{A_{1}}^{(k)}, \dots, v_{A_{C}}^{(k)}), \end{matrix}

(14)

where

Ω (E (A_{i}, T ∖ A_{i}))

represents the sum of weights corresponding to the edges contained in the set

E (A_{i}, T ∖ A_{i})

, and we have

C_{e} (Ω (E (A_{1}, T ∖ A_{1})), \dots, Ω (E (A_{C}, T ∖ A_{C}))) = \sum_{i = 1}^{C} Ω (E (A_{i}, T ∖ A_{i})),

(15)

C_{v} (v_{A_{1}}^{(k)}, \dots, v_{A_{C}}^{(k)}) = \sum_{i = 1}^{C} g (v_{A_{i}}^{(k)}),

(16)

with

g (v_{A_{i}}^{(k)})

representing an increasing convex function of the vertex weights in set

A_{i}

, and

C_{v} (\cdot)

being a linear function for balancing the cost of vertex weights across different sets

A_{i}

i = 1, 2, \dots, C

It should be noted that the optimization variable in the objective function (12a) is

D

, while that in (14) is

P

. Both

D

and

P

represent the mapping of tasks to containers, and both the expression

\sum_{i = 1}^{C} \sum_{j = 1}^{C} f_{i j}

in (12a) and the expression

C_{e} (\cdot)

in (14) characterize the communication time between containers. However, the differences are: (1)

\sum_{i = 1}^{C} \sum_{j = 1}^{C} f_{i j}

in (12a) is further normalized by dividing the total communication time of all the tasks, while

C_{e} (\cdot)

is a direct summation of

Ω (E (A_{i}, T ∖ A_{i}))

i = 1, 2, \dots, C

; (2)

\sum_{k = 1}^{R} \sum_{j = 1}^{C} \frac{1}{C} {(β_{c_{j}, r_{k}} - {\bar{β}}_{r_{k}})}^{2}

in (12a) is the average deviation of multi-type resource demands by each container, while

C_{v} (\cdot)

in (14) is the total demand for computing resources by all the containers. Obviously, when the demands for multi-type computing resources by the individual containers are equal, the average deviation of multi-type resource demands by each container reaches the minimum. Therefore, (12a) and (14) can be seen as different mathematical models for describing the same objective. Compared with (12a), Equation (14) directly expresses the communication time and computing resource requirements as specific analytical expressions of the variables

A_{i}

i = 1, 2, \dots, C

, thus making it more convenient to derive the solution algorithm from the graph partitioning perspective.

According to Equation (14), the task containerization method can be derived by solving the following optimization problem:

\begin{matrix} P 4 : min_{P = (A_{1}, \dots, A_{C})} f (P) & = \sum_{i = 1}^{C} μ_{C} Ω (E (A_{i}, T ∖ A_{i})) \\ + \sum_{i = 1}^{C} μ_{B} g (v_{A_{i}}^{(k)}) \\ s . t . & ⋃_{i = 1}^{C} A_{i} = T, \\ A_{i} \cap A_{j} = \emptyset, \forall i \neq j . \end{matrix}

(17)

For the convex function

g (x)

, based on [12], we select the family of functions

c (x) = α x^{θ}

, where

α > 0

and

θ \geq 1

. The parameter

θ

controls the balance degree of vertex weights between partitioned sets. The greater the value of

θ

, the greater the cost of imbalanced set weights.

θ = 1

means that the imbalance between the demand of resource

r_{k}

by the set

A_{i}

, i.e.,

v_{A_{i}}^{(k)}

, is ignored. We choose

α = E \frac{C^{θ - 1}}{T^{θ}}

to serve as a proper scaling factor. The optimization problem

P 4

is then written as:

\begin{matrix} P 5 : min_{P = (A_{1}, \dots, A_{C})} f (P) & = \frac{\sum_{i = 1}^{C} μ_{C} Ω (E (A_{i}, T ∖ A_{i}))}{E} \\ + \frac{1}{C} \sum_{i = 1}^{C} μ_{B} {(\frac{v_{A_{i}}^{(k)}}{\frac{T}{C}})}^{θ} \\ s . t . & ⋃_{i = 1}^{C} A_{i} = T, \\ A_{i} \cap A_{j} = \emptyset, \forall i \neq j . \end{matrix}

(18)

Furthermore, we define a function h as:

\begin{matrix} h (P) & = \sum_{i = 1}^{C} (μ_{C} Ω (E (A_{i}, A_{i})) - μ_{B} g (v_{A_{i}}^{(k)})) \\ = \sum_{i = 1}^{C} (μ_{C} Ω (E (T, T) - E (A_{i}, T ∖ A_{i})) - μ_{B} g (v_{A_{i}}^{(k)})) \\ = C \cdot μ_{C} Ω (E (T, T) - f (P) . \end{matrix}

(19)

Therefore, the problem of minimizing

f (P)

can be solved by maximizing

h (P)

. For any

1 \leq i < j \leq C

, if

h (A_{1}, \dots, A_{i} \cup {t}, \dots, A_{j} ∖ {t}, \dots, A_{C}) \geq h (A_{1}, \dots, A_{i} ∖ {t}, \dots, A_{j} \cup {t}, \dots, A_{C})

, vertex t is assigned to vertex set

A_{i}

. Based on this condition, we define a difference function

\begin{matrix} Δ h (t, A_{i}) = & h (A_{1}, \dots, A_{i} \cup {t}, \dots, A_{j} ∖ {t}, \dots, A_{C}) \\ - h (A_{1}, \dots, A_{i}, \dots, A_{j}, \dots, A_{C}), \end{matrix}

(20)

and assign vertex t to vertex set

A_{i}

when we have

Δ h (t, A_{i}) \geq Δ h (t, A_{j})

. Let

N (t)

denote the neighbors of vertex t (i.e., the vertices directly connected to vertex t). According to Equation (19), the difference function is rewritten as:

\begin{matrix} Δ h (t, A_{i}) = & μ_{C} Ω (E (N (t) \cap A_{i}, N (t) \cap A_{i})) - μ_{C} Ω (E (N (t) \cap A_{j}, N (t) \cap A_{j})) \\ + μ_{B} (g (v_{A_{i}}^{(k)}) + g (v_{A_{j}}^{(k)}) - g (v_{A_{i} \cup {t}}^{(k)}) - g (v_{A_{j} ∖ {t}}^{(k)})) . \end{matrix}

(21)

The details of the proposed task containerization method are shown in Algorithm 1. First, tasks are selected by the RI or NCPI algorithm for initial partitioning (Lines 2–35 of Algorithm 1). Once the initial partitioning has been determined, the remaining tasks are partitioned using the scores derived from the above calculations (Lines 36–47 of Algorithm 1), thus ensuring that the communication cost and the multi-type computing resource balancing cost are minimized during the task containerization stage.

In order to measure whether the resources required for each vertex set are balanced, we define the measurement parameter

λ

as the normalized maximum load:

λ = C \cdot \frac{{max}_{j} {\sum_{k = 1}^{R} β_{c_{j}, r_{k}} | c_{j} \in C}}{\sum_{j = 1}^{C} \sum_{k = 1}^{R} β_{c_{j}, r_{k}}} .

(22)

The balance degree of the usage of multi-type computing resources improves as

λ

approaches 1.

4.2. Container Placement Method

When tasks are divided into multiple vertex sets, each set is a container, and the resources are available to each container. We conduct a comparative study of container placement methods by using the dot product (DP) algorithm [14] and the first fit decreasing (FFD) algorithm [14] to individually solve the problem

P 3

DP considers the demands of multi-type computing resources by each container as well as the capacities of multi-type resources on each server. Any server is listed as a candidate server for a container if it has enough multi-type resources to accommodate the container. For each container

c_{i}

and one of its candidate servers

s_{j}

, the dot product of multi-type resources required by the container and multi-type resources that the server can provide is denoted as

{DP}_{i j}

. The larger the value of

{DP}_{i j}

, the more resources server

s_{j}

is able to supply to container

c_{i}

. To improve computing resource utilization, we tend to place the container on the server that has the greatest amount of resources, hence we use

{DP}_{i j}

as the matching degree between demand and supply, and for servers that are not candidates, we set the matching degree as 0. Thus we have

{DP}_{i j} = \{\begin{matrix} \sum_{k = 1}^{R} β_{c_{i}, r_{k}} \cdot γ_{s_{j}, r_{k}}, & if β_{c_{i}, r_{k}} < γ_{s_{j}, r_{k}} \\ 0 . & otherwise \end{matrix}

(23)

The procedure of the DP algorithm is shown in Algorithm 2.

FFD is a greedy algorithm in which the containers are sorted in decreasing order according to their individual weight that is determined by each container’s demands for multi-type resources, and then containers are placed sequentially in the first server that has sufficient capacity to accommodate them. As the resources required by each container are multidimensional (i.e., multi-type), the definition of dimensions and the associated weight assigned to the vector of resources required by an individual container determine the order in which the containers are placed. Containers have different resource requirements and there are multiple alternative methods for selecting an appropriate weight for each container. For example, one can calculate the weighted sum of multi-type resources required by the container as the basis for the decreasing ordering. In particular, when the weights are equal, containers are decreasingly ordered by evaluating

\sum_{k = 1}^{R} β_{c_{j}, r_{k}}

c_{j} \in C

. Additionally, if the demands of a particular type of resource always dominate the demands of the other types of resources, one can only consider the dominant type of resource to determine the weights of containers and the decreasing order. Then, upon traversing the servers, the containers are sequentially placed on the first server that can satisfy their requirements of resources. The details of FFD are presented in Algorithm 3.

To sum up, the process of the whole task containerization and container placement scheme is as follows: An application’s tasks are first grouped by the P-NCPI or the P-RI algorithm, and then each group of tasks, denoted by

A_{i}

, is encapsulated into a container

c_{i}

, which is then placed on the selected server by using the DP or the FFD algorithm. In this manner, the application is eventually executed in a given number of containers and on the selected servers. As a beneficial result, the proposed scheme exhibits minimized inter-container communication cost (some containers are possibly placed on different servers), balanced resource requirements among containers, and balanced resource utilization efficiency among the selected servers.

Algorithm 1 The proposed task containerization algorithm

Input:

G = (T, E)

R

, C,

{v_{i}}_{i = 1}^{| T |}

Output:

P

D

1:: Initialization: $P = (A_{1} = \emptyset, A_{2} = \emptyset, \dots, A_{C} = \emptyset)$
2:: if RI is the initial partitioning algorithm then
3:: select C tasks in $T$ randomly
4:: allocate each of the C tasks exclusively to all $A_{i}$ , $i = 1, 2, \dots, C$
5:: end if
6:: if NCPI is the initial partitioning algorithm then
7:: $z \leftarrow$ sort vertices in $G$ topologically
8:: if $G$ has a loop then
9:: raise Error
10:: end if
11:: Generate a $| z |$ -dimensional null vector $h$
12:: for $i = 1$ to $| T |$ do
13:: $N_{z_{i}} \leftarrow$ the indices of the adjacency vertices of $z_{i}$
14:: for $j = 1$ to $| N_{z_{i}} |$ do
15:: if $h_{N_{z_{i}} [j]} < h_{N_{z_{i}} [j]} + ω (e_{N_{z_{i}} [j], z_{i}})$ then
16:: $h_{N_{z_{i}} [j]} \leftarrow h_{N_{z_{i}} [j]} + ω (e_{N_{z_{i}} [j], z_{i}})$
17:: end if
18:: end for
19:: end for
20:: Initialize a vector $u$ with all elements being $max {h_{i} | h_{i} \in h}$
21:: Reverse the elements order of $z$
22:: Repeat Lines 12-19 to obtain $u$
23:: for $i = 1$ to $| T |$ do
24:: $N_{i} \leftarrow$ the indices of the adjacency vertices of vertex i
25:: for $j = 1$ to $| N_{i} |$ do
26:: $l \leftarrow h_{i}$
27:: $v \leftarrow u_{i} - ω (e_{N_{i} [j], i})$
28:: if $l = = v$ then
29:: include $e_{N_{i} [j], i}$ into the critical path
30:: end if
31:: end for
32:: end for
33:: Select C tasks on the non-critical path
34:: Allocate each of the C tasks exclusively to all $A_{i}$ , $i = 1, 2, \dots, C$
35:: end if
36:: Put the remaining $| T | - C$ tasks into the set $Y$
37:: for $j = 1$ to $| T | - C$ do
38:: score $\leftarrow 0$
39:: for $i = 1$ to C do
40:: calculate $Δ h (Y [j], A_{i})$ by Equation (21)
41:: if $Δ h (Y [j], A_{i}) >$ score then
42:: score $\leftarrow Δ h (Y [j], A_{i})$
43:: $k \leftarrow i$
44:: end if
45:: end for
46:: Put task $Y [j]$ into $A_{k}$
47:: end for
48:: Generate $D$ according to $P$

Algorithm 2 The DP algorithm

Input:

| T |

C

S

R

{v_{i}}_{i = 1}^{| T |}

D

Output:

M

1:: Initialization: Generate a null matrix $M = 0_{| C | \times | S |}$
2:: for $i = 1$ to $| C |$ do
3:: for $j = 1$ to $| S |$ do
4:: if server $s_{j}$ can provide all the resources required by container $c_{i}$ then
5:: ${DP}_{i j} \leftarrow$ calculate the dot product of multi-type resources required by container $c_{i}$ and multi-type resources that server $s_{j}$ can provide
6:: else
7:: ${DP}_{i j} \leftarrow 0$
8:: end if
9:: end for
10:: Select the server $s_{j}$ with the largest ${DP}_{i j}$ to accommodate the container $c_{i}$
11:: $m_{i j} \leftarrow 1$
12:: end for

Algorithm 3 The FFD algorithm

Input:

| T |

C

S

R

{v_{i}}_{i = 1}^{| T |}

D

Output:

M

1:: Initialization: Generate a null matrix $M = 0_{| C | \times | S |}$
2:: Sorts the containers in decreasing order by evaluating $\sum_{k = 1}^{R} β_{c_{j}, r_{k}}$ of each container $c_{j}$
3:: for $i = 1$ to $| C |$ do
4:: for $j = 1$ to $| S |$ do
5:: if server $s_{j}$ can provide all the resources required by container $c_{i}$ then
6:: select server $s_{j}$ to place container $c_{i}$
7:: $m_{i j} \leftarrow 1$
8:: end if
9:: if $m_{i j} = = 1$ then
10:: break
11:: end if
12:: end for
13:: end for

4.3. Analysis of Algorithm Complexity

The task containerization method groups the tasks of the given application into multiple vertex sets, each of which is encapsulated into a single container. Then the generated containers are placed on the selected appropriate servers by using the container placement method.

More specifically, two initial partitioning algorithms, i.e., P-NCPI and P-RI, are individually employed in the task containerization method. P-RI initializes a given number of vertex sets, which are supposed to represent the task partitioning, by using the same number of randomly selected tasks (see Lines 2-5 of Algorithm 1). The time complexity of P-RI is

O (T^{2} + 2 T) = O (C) + O (C) + O (T - C) + O (T (T - C)) + O (T - C) + O (T C)

, and the number of floating point operations is given by

1 + C + C + T - C + T - C + 2 T (T - C) + T - C + T C = 2 T^{2} - T C + 3 T - C + 1

. P-NCPI employs the non-critical path based initialization to conduct the graph partitioning (see Lines 6-35 of Algorithm 1). Its time complexity is

O (4 T^{2} + 2 T) = O (3 T^{2}) + O (2 C) + O (T - C) + O (T (T - C)) + O (T - C) + O (T C)

, and the number of floating point operations is given by

1 + T^{2} + 1 + 1 + T + T^{2} + 1 + T + T^{2} + C + C + T - C + T - C + 2 T (T - C) + T - C + T C = 5 T^{2} - T C + 5 T - C + 4

As far as the container placement method is concerned, two bin packing algorithms are used, namely DP (see Algorithm 2) and FFD (see Algorithm 3). The time complexity of DP is

O (C S)

and the number of floating point operations is

1 + C S + 2 C

. The time complexity of FFD is

O (C R + C S + C)

, and the number of floating point operations is

1 + C R + 2 C S + C

5. Evaluation

In this section, we present simulation results to demonstrate the effectiveness of our proposed task containerization and container placement methods. The experiments were carried out on a MacBook Pro with a 4-core CPU, 8GB of RAM, and the macOS Monterey operating system. All the algorithms presented in this paper were implemented by Python 3.9.7. For the P-RI algorithm and the K-means algorithm, we took the average of 10 sets of experimental results to obtain statistically reliable results. Moreover, all the results were calculated relying on the experiments of 10 application programs, each of which is represented by a workflow composed of a different number of tasks: 5, 9, 17, 24, 30, 47, 57, 63, 91 and 93.

We considered the CPU and memory resources of a computing network comprising 10 MEC servers. The server configurations are listed in Table 1, where the volume of each type of computing resources is normalized. We set the parameters

μ_{C}

as 0.5,

μ_{B}

as 0.5, and

θ

as 1.5. The used data regarding the application tasks were obtained from the Alibaba Cloud platform [15]. Each container hosts at least one process, and each task is set up as a separate process. In general, resources allocated to a container are more than the container needs [16]. We ignored the discrepancy between the volume of resources allocated to the container and the volume of resources demanded by the container for the convenience of statistics and visualization.

The balance degree of utilizing computing resources is a critical performance indicator for MEC. To avoid the problem of long request delay caused by insufficient resources of the servers, the utilization of multi-type computing resources on the individual servers has to be balanced. In Figure 3, we compared the normalized maximum load

λ

(defined by Equation (22)) of the proposed task partitioning algorithms and of the benchmarking K-means clustering method. Specifically, we observe in Figure 3 that the normalized maximum load

λ

of the K-means method [17] varies greatly between 1.6 and 4. Unlike those of the K-means method, the values of

λ

for P-NCPI and P-RI remain between 1.25 and 1, indicating that the resource requirements by each group of tasks are more balanced after conducting task partitioning with our proposed algorithms (e.g., decreasing the normalized maximum load by up to 60.24% on average when using P-NCPI).

In Figure 4 and Figure 5, we compared the proposed task-containerization-and-container-placement methods with the state-of-the-art strategy “Spread” [16] employed by the container orchestration tool Docker swarm, in terms of the average CPU and the memory (i.e., MEM) utilization efficiencies in the MEC-based computing network. Specifically, the average CPU utilization efficiency of the MEC-based computing network is defined as

λ_{CPU} = \frac{\sum_{n}^{N_{S}} η_{n}}{N_{S}},

(24)

where

N_{S}

represents the number of servers occupied by the application,

η_{n}

denotes the CPU utilization efficiency of server n. Similarly, the average MEM utilization efficiency of the MEC-based computing network is defined as

λ_{MEM} = \frac{\sum_{n}^{N_{S}} ζ_{n}}{N_{S}},

(25)

where

ζ_{n}

represents the MEM utilization efficiency of server n.

We see from Figure 4 and Figure 5 that the proposed P-NCPI-FFD algorithm improves the average CPU utilization efficiency by 30.66% and the average MEM utilization efficiency by 40.77%, compared with the Spread algorithm. In general, the proposed P-NCPI-FFD algorithm achieves the highest CPU and MEM utilization efficiency among all algorithms considered. The FFD algorithm attains higher resources utilization efficiency than the DP algorithm. This phenomenon can be explained as follows. The DP algorithm focuses on finding out the largest sum product of a container’s multi-type resource requirements and the volume of multi-type resources that a server can provide, whereas FFD puts as many containers having higher resource requirements as possible on the minimum possible number of servers. Therefore, when using FFD,

η_{n}

and

ζ_{n}

in Equations (24) and (25) are larger, while

N_{S}

is smaller, than those when employing DP. In addition, it is observed that the impact of the P-NCPI and P-RI algorithms on the results of CPU and MEM utilization is trivial.

For a given application, the metric defined by Equation (10) can reflect the extent to which different resources are used in a balanced manner. According to Figure 6, in most cases evaluated, our proposed algorithms outperform the Spread algorithm in terms of the balance degree of utilizing multi-type computing resources. Although the DP algorithm is generally inferior to the FFD algorithm in terms of the CPU and MEM utilization efficiencies (as shown by Figure 4 and Figure 5), it performs better than FFD in terms of the balance degree of utilizing multi-type computing resources across the MEC-based computing network. The P-NCPI and P-RI algorithms, which are invoked for the initial task partitioning, do not make much difference in this respect.

The running time results of all the task-containerization-and-container-placement algorithms considered are provided in Figure 7. It is observed that the running time of the P-RI algorithm is shorter than that of the P-NCPI algorithm. Additionally, when the number of tasks exceeds a particular value, the DP algorithm has a shorter running time than the FFD algorithm. Among the four algorithms we proposed, the P-RI-DP algorithm has the shortest running time, and in this regard, there is very little difference between the P-RI-DP algorithm and the Spread algorithm. Notably, the Spread algorithm always performs best in terms of the running time.

Finally, the results of the communication overhead for various task-containerization-and-container-placement algorithms are shown in Figure 8. We can see that when compared with the benchmarking Spread algorithm, the P-NCPI-FFD algorithm saves 74.10% of the communication overhead, while the P-RI-FFD algorithm saves 59.32%. The communication overhead of FFD is lower than that of DP, because it does not have to consider the balance between the resource demand of containers and the resource supply of servers.

To sum up, our proposed task-containerization-and-container-placement algorithms outperform the existing algorithms in general. In particular, all of our proposed algorithms exhibit a more balanced resource requirements by containers, the P-NCPI-FFD algorithm achieves the highest CPU and MEM utilization efficiencies, the P-NCPI-DP and P-RI-DP algorithms achieve a higher degree of balance in utilizing multi-type computing resources, while the P-NCPI-FFD and P-RI-FFD algorithms perform better in terms of communication overhead. Additionally, different initial task partitioning algorithms, such as P-NCPI and P-RI, do not make much difference in terms of the above performance metrics.

6. Conclusions

In this paper we have proposed four task-containerization-and-container-placement algorithms to jointly reduce the inter-container communication overhead and balance the multi-type computing resource utilization in the MEC-based computing network. We establish a workflow model to reflect the interactions between interdependent tasks. As a beneficial result, the inter-task communication overhead, the inter-container communication overhead, as well as the computing resources required by each group of tasks encapsulated in a container, are conveniently characterized. Furthermore, two task containerization algorithms have been designed to reduce the inter-container communication overhead while balancing the multi-type computing resource requirements of containers. Then we proposed a pair of container placement algorithms for optimizing the utilization of multi-type computing resources across MEC servers. Extensive simulation results demonstrated that our proposed methods are capable of reducing the inter-container communication overhead by up to 74.10%, reducing the normalized maximum load by up to 60.24%, improving the CPU utilization efficiency by up to 30.66%, and improving the memory utilization efficiency by up to 40.77% in the MEC-based computing network considered.

Author Contributions

Conceptualization, S.Y. and A.L.; methodology, S.Y.; software, A.L. and J.T.; validation, A.L., J.T., Z.L. and J.S.; formal analysis, S.Y. and A.L.; investigation, A.L., J.T. and Z.L.; resources, S.Y. and H.Y.; data curation, J.T., Z.L. and J.S.; writing—original draft preparation, A.L. and S.Y.; writing—review and editing, S.Y.; visualization, A.L.; supervision, S.Y.; project administration, S.Y., T.W. and H.Y.; funding acquisition, S.Y., T.W. and H.Y. All authors have read and agreed to the published version of the manuscript.

Funding

This work was supported in part by the Beijing Municipal Natural Science Foundation under Grant L202012, and in part by the BUPT-CMCC Joint Research Center under Grant A2022122.

Data Availability Statement

Restrictions apply to the availability of tasks data. Tasks data were obtained from Alibaba Group. These data are open source and available at https://github.com/alibaba/clusterdata/tree/master/cluster-trace-v2018.

Conflicts of Interest

The authors declare no conflict of interest. The funders had no role in the design of the study; in the collection, analyses, or interpretation of data; in the writing of the manuscript; or in the decision to publish the results.

References

Shi, W.; Cao, J.; Zhang, Q.; Li, Y.; Xu, L. Edge computing: Vision and challenges. IEEE Internet Things J. 2016, 3, 637–646. [Google Scholar] [CrossRef]
Liu, P.; Willis, D.; Banerjee, S. Paradrop: Enabling lightweight multi-tenancy at the network’s extreme edge. In Proceedings of the IEEE/ACM Symposium on Edge Computing (SEC), Washington, DC, USA, 27–28 October 2016; pp. 1–13. [Google Scholar]
Zhang, J.; Zhou, X.; Ge, T.; Wang, X.; Hwang, T. Joint task scheduling and containerizing for efficient edge computing. IEEE Trans. Parallel Distrib. Syst. 2021, 32, 2086–2100. [Google Scholar] [CrossRef]
Bao, L.; Wu, C.; Bu, X.; Ren, N.; Shen, M. Performance modeling and workflow scheduling of microservice-based applications in clouds. IEEE Trans. Parallel Distrib. Syst. 2019, 30, 2114–2129. [Google Scholar] [CrossRef]
Zhou, R.; Li, Z.; Wu, C. An efficient online placement scheme for cloud container clusters. IEEE J. Sel. Areas Commun. 2019, 37, 1046–1058. [Google Scholar] [CrossRef]
Lv, L.; Zhang, Y.; Li, Y.; Xu, K.; Wang, D.; Wang, W.; Li, M.; Cao, X.; Liang, Q. Communication-aware container placement and reassignment in large-scale Internet data centers. IEEE J. Sel. Areas Commun. 2019, 37, 540–555. [Google Scholar] [CrossRef]
Hong, Y.-J.; Thottethodi, M. Understanding and mitigating the impact of load imbalance in the memory caching tier. In Proceedings of the 4th Annual Symposium on Cloud Computing, Santa Clara, CA, USA, 1–3 October 2013; pp. 1–17. [Google Scholar]
Li, W.; Li, X.; Ruiz, R. Scheduling microservice-based workflows to containers in on-demand cloud resources. In Proceedings of the IEEE 24th International Conference on Computer Supported Cooperative Work in Design (CSCWD), Dalian, China, 5–7 May 2021; pp. 61–66. [Google Scholar]
Ye, L.; Xia, Y.; Yang, L.; Yan, C. SHWS: Stochastic hybrid workflows dynamic scheduling in cloud container services. IEEE Trans. Autom. Sci. Eng. 2022, 19, 2620–2636. [Google Scholar] [CrossRef]
Wu, Z.; Deng, Y.; Feng, H.; Zhou, Y.; Min, G.; Zhang, Z. Blender: A container placement strategy by leveraging zipf-like distribution within containerized data centers. IEEE Trans. Netw. Serv. Manag. 2022, 19, 1382–1398. [Google Scholar] [CrossRef]
Hu, Y.; Zhou, H.; de Laat, C.; Zhao, Z. Concurrent container scheduling on heterogeneous clusters with multi-resource constraints. Future Gener. Comput. Syst. 2020, 102, 562–573. [Google Scholar] [CrossRef]
Tsourakakis, C.; Gkantsidis, C.; Radunovic, B.; Vojnovic, M. FENNEL: Streaming graph partitioning for massive scale graphs. In Proceedings of the 7th ACM International Conference on Web Search and Data Mining, New York, NY, USA, 24–28 February 2014; pp. 333–342. [Google Scholar]
Patt-Shamir, B.; Rawitz, D. Vector bin packing with multiple-choice. Discret. Appl. Math. 2012, 160, 1591–1600. [Google Scholar] [CrossRef]
Panigrahy, R.; Talwar, K.; Uyeda, L.; Wieder, U. Heuristics for Vector bin Packing. January 2011, pp. 1–14. Available online: https://www.microsoft.com/en-us/research/publication/heuristics-for-vector-bin-packing/ (accessed on 18 March 2023).
Alibaba Cluster Trace Program. 2023. Available online: https://github.com/alibaba/clusterdata/tree/master/cluster-trace-v2018 (accessed on 18 March 2023).
Docker. 2023. Available online: https://docs.docker.com/engine/swarm/services/ (accessed on 18 March 2023).
Hartigan, J.A.; Wong, M.A. Algorithm AS 136: A K-means clustering algorithm. J. R. Stat. Soc. Ser. C (Appl. Stat.) 1979, 28, 100–108. [Google Scholar] [CrossRef]

Figure 1. A system model for user terminals to access an MEC-based computing network.

Figure 2. An example of DAG workflow with ten tasks.

Figure 3. Comparison of the normalized maximum load performance (defined by Equation (22)) of various task partitioning algorithms, including the proposed P-NCPI and P-RI algorithms, and the classic K-means algorithm.

Figure 4. Comparison of the average CPU utilization efficiency of the MEC-based computing network (defined by Equation (24)), when using the proposed four task-containerization-and-container-placement algorithms and the Spread algorithm.

Figure 5. Comparison of the average MEM utilization efficiency of the MEC-based computing network (defined by Equation (25)), when using the proposed four task-containerization-and-container-placement algorithms and the Spread algorithm.

Figure 6. Comparison of the balance degree of multi-type computing resource utilization (defined by Equation (10)), when using the proposed four task-containerization-and-container-placement algorithms and the Spread algorithm.

Figure 7. Comparison of the running time of different task-containerization-and-container-placement algorithms.

Figure 8. The ratio of the inter-container communication overhead to the inter-task communication overhead when using different task-containerization-and-container-placement algorithms.

Table 1. Configuration of MEC servers.

Server	CPU (%)	Memory (%)
0	7	7
1	9	8
2	10	8
3	12	11
4	6	11
5	12	14
6	14	8
7	10	11
8	9	14
9	11	8

Disclaimer/Publisher’s Note: The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of MDPI and/or the editor(s). MDPI and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.

© 2023 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https://creativecommons.org/licenses/by/4.0/).

Share and Cite

MDPI and ACS Style

Liu, A.; Yang, S.; Tan, J.; Liang, Z.; Sun, J.; Wen, T.; Yan, H. Task Containerization and Container Placement Optimization for MEC: A Joint Communication and Computing Perspective. Processes 2023, 11, 1560. https://doi.org/10.3390/pr11051560

AMA Style

Liu A, Yang S, Tan J, Liang Z, Sun J, Wen T, Yan H. Task Containerization and Container Placement Optimization for MEC: A Joint Communication and Computing Perspective. Processes. 2023; 11(5):1560. https://doi.org/10.3390/pr11051560

Chicago/Turabian Style

Liu, Ao, Shaoshi Yang, Jingsheng Tan, Zongze Liang, Jiasen Sun, Tao Wen, and Hongyan Yan. 2023. "Task Containerization and Container Placement Optimization for MEC: A Joint Communication and Computing Perspective" Processes 11, no. 5: 1560. https://doi.org/10.3390/pr11051560

APA Style

Liu, A., Yang, S., Tan, J., Liang, Z., Sun, J., Wen, T., & Yan, H. (2023). Task Containerization and Container Placement Optimization for MEC: A Joint Communication and Computing Perspective. Processes, 11(5), 1560. https://doi.org/10.3390/pr11051560

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Menu

Task Containerization and Container Placement Optimization for MEC: A Joint Communication and Computing Perspective

Abstract

1. Introduction

2. System Model

3. Problem Formulation

3.1. Communication Overhead

Computing Resource Utilization Balance

4. Task Containerization and Container Placement Schemes

4.1. Task Containerization Method

4.2. Container Placement Method

4.3. Analysis of Algorithm Complexity

5. Evaluation

6. Conclusions

Author Contributions

Funding

Data Availability Statement

Conflicts of Interest

References

Share and Cite

Article Metrics

Article Access Statistics

Further Information

Guidelines

MDPI Initiatives

Follow MDPI