Tài liệu Master's thesis of science user delay tolerance aware edge node placement optimization for cost minimization

User-Delay-Tolerance-Aware Edge Node Placement Optimization for Cost Minimization A thesis submitted in fulfillment of the requirements for the degree of Master of Science Xiaoyu Zhang School of Computing Technologies College of Science, Technology, Engineering and Maths RMIT University Melbourne, Victoria, Australia May, 2022 Declaration I certify that except where due acknowledgement has been made, this research is that of the author alone; the content of this research submission is the result of work which has been carried out since the official commencement date of the approved research program; any editorial work, paid or unpaid, carried out by a third party is acknowledged; and, ethics procedures and guidelines have been followed. In addition, I certify that this submission contains no material previously submitted for award of any qualification at any other university or institution, unless approved for a jointaward with another institution, and acknowledge that no part of this work will, in the future, be used in a submission in my name, for any other qualification in any university or other tertiary institution without the prior approval of the University, and where applicable, any partner institution responsible for the joint-award of this degree. I acknowledge that copyright of any published works contained within this thesis resides with the copyright holder(s) of those works. I give permission for the digital version of my research submission to be made available on the web, via the University’s digital research repository, unless permission has been granted by the University to restrict access for a period of time I acknowledge the support I have received for my research through the provision of an Australian Government Research Training Program Scholarship. Xiaoyu Zhang School of Computing Technologies, RMIT University 07 March, 2022 Acknowledgement I would like to express my gratitude to my supervisors, Prof. Zhifeng Bao and Dr. Hai Dong, who guided me throughout this Master by Research study, for their excellent supervision, great engagement, and remarkable support in the last year. They offered me a precious and splendid research journey. I would also like to thank my family and friends who always support my study. I wish to acknowledge the help provided by the staff in the School of Computing Technology of RMIT University. Contents Declaration ii Acknowledgement iii Contents iv List of Figures vii List of Tables viii Abstract 1 1 3 Introduction 1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2 Research Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.3 Research Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.4 Thesis Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2 3 Background 11 2.1 MEC Network and Key Components . . . . . . . . . . . . . . . . . . . . . . . . 11 2.2 Literature Review . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.2.1 Delay Aware Edge Nodes Placement . . . . . . . . . . . . . . . . . . . . 12 2.2.2 Cost and Delay Aware Edge Node Placement . . . . . . . . . . . . . . . 14 Problem Formulation 16 iv CONTENTS v 3.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3.2 Coarse-grained Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.2.1 Workload Measurement . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.2.2 Delay Measurement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.2.3 Qualified EN Placement Plan . . . . . . . . . . . . . . . . . . . . . . . . 20 Fine-Grained Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3.3.1 Workload Measurement . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.3.2 Delay Measurement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.3.3 Qualified EN Placement Plan . . . . . . . . . . . . . . . . . . . . . . . . 22 Cost Minimization in MEC Edge Node Placement Problem . . . . . . . . . . . 23 3.3 3.4 4 Hardness Analysis 24 5 Solutions 26 5.1 5.2 6 MIP-based Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 5.1.1 Mixed-Integer Programming (MIP) . . . . . . . . . . . . . . . . . . . . . 26 5.1.2 Cluster-based MIP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 Heuristic-based Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 5.2.1 Coverage First Search (CFS) . . . . . . . . . . . . . . . . . . . . . . . . 30 5.2.2 Distance Aware Coverage First Search (DA-CFS) . . . . . . . . . . . . . 31 5.2.3 Fine-grained Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . 32 Experiments 6.1 6.2 35 Experiment Settings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 6.1.1 Dataset . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 6.1.2 Experiment Environment . . . . . . . . . . . . . . . . . . . . . . . . . . 36 6.1.3 Methods for Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 6.1.4 Parameter Settings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 6.1.5 Evaluation Metrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 6.2.1 38 Effectiveness Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . CONTENTS 6.3 7 vi 6.2.2 Efficiency Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 6.2.3 Discussion on Scalability . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 6.2.4 Transmission and Computation Delay in θ . . . . . . . . . . . . . . . . . 42 6.2.5 The Impact of θ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 6.2.6 Peak vs. AVG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 6.2.7 Clustering Results for MIP+Cluster . . . . . . . . . . . . . . . . . . . . 47 6.2.8 Ablation Study on τ for DA-CFS . . . . . . . . . . . . . . . . . . . . . . 48 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 Conclusion 50 Appendices 51 Credits 51 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Bibliography 52 List of Figures 1.1 Mobile Cloud Computing Network Architecture . . . . . . . . . . . . . . . . . . . 4 1.2 Mobile Edge (Multi-Access) Computing Network Architecture . . . . . . . . . . . 4 1.3 Example of Optimal EN Deployment under Different Delay Tolerance . . . . . . 7 6.1 Effectiveness and efficiency with different BS input scale . . . . . . . . . . . . . . 39 6.2 Cost generated by MIP+Cluster with running time limit of 10min and 1h per cluster 41 6.3 Distribution of BSs with different transmission delay proportions on θ . . . . . . 43 6.4 Effectiveness and efficiency with different θ value . . . . . . . . . . . . . . . . . . 45 6.5 Deployment cost: Peak vs. AVG . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 6.6 Visualise clusters on Shanghai Telecom Dataset . . . . . . . . . . . . . . . . . . . 47 vii List of Tables 1.1 Example of fine-grained workload in BS and EN . . . . . . . . . . . . . . . . . . 8 2.1 Literature review of delay minimization problems . . . . . . . . . . . . . . . . . . 13 2.2 Literature review of cost minimization problems . . . . . . . . . . . . . . . . . . . 14 3.1 Table of notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 6.1 Parameter setting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 6.2 Estimated EN coverage with different θ value . . . . . . . . . . . . . . . . . . . . 37 6.3 Cluster results on different BS input scale . . . . . . . . . . . . . . . . . . . . . . 47 6.4 Cost and # of EN selected with different τ in DA-CFS . . . . . . . . . . . . . . . 48 viii Abstract With the prosperity of 5G technologies, Mobile (or Multi-Access) edge computing (MEC) has emerged as the next generation of network architecture. Compared with the previous Mobile Cloud Computing (MCC) architecture, MEC’s decentralising network architecture empowered it amplify user accessible resource and low-latency access. Investigating how to effectively place edge nodes, which are also known as edge servers, has become a trendy research topic and attracted wide attention among researchers. Among existing studies in this research field, most of the works aim to minimize delays experienced by mobile users, which can be achieved by reaching a workload balance between edge nodes, such that the computation capacity from edge nodes can be fully used. However, considering the real use cases, cost-saving, rather than the extremely low network latency, is the prime goal that a service provider (i.e. the telecom companies) pursue when deploying edge nodes to a network as users have their delay tolerance within a threshold rather than pursuing a zero-latency network. Therefore, how to place edge nodes with the minimum cost, including the construction cost for setting up the edge nodes and the server cost for adding server units to the sites, is still worth further study. Although extensive studies have been conducted to find the optimal edge node deployment strategies with the objective of cost minimization, the formulation of such a problem is not close enough to the real-world cases. First, they barely take into account the relationship between the allocation of corresponding computation resources and users’ delay tolerance. To be more specific, instead of achieving a workload balance on each homogeneous capacitated edge node, the edge nodes can have the heterogeneous capacity, depending on the number of users they would serve and the corresponding workload. Second, the delay has not been addressed precisely enough, as most of the existing work only considers the transmission delay while ignoring the computation delay 1 which is decided by the edge node capacity and the workload together. In our work, we define a Cost Minimization in MEC Edge Node Placement (CMMENP) problem to find an optimal edge node deployment strategy such that the cost can be minimized without exceeding users’ delay tolerance. We precisely define the delay with both transmission delay and computation delay. We prove the NP-hardness of this problem and propose a series of solutions, including Clusterbased Mixed Integer Programming, Coverage First Search, and Distance-Aware Coverage First Search. Intuitively, the Cluster-based Mixed Integer Programming solves the efficiency issue in the pure MIP solution by sacrificing some degree of accuracy, while the Coverage First Search is an efficiency prioritized solution with Distance-Aware Coverage First Search to further improve its effectiveness without loss of efficiency. In addition, we propose a fine-grained optimization strategy to delicately allocate computation resources to edge nodes at the user service request level, which can remarkably decrease the deployment cost. Comprehensive experiments have been conducted on a large-scale real-world dataset, which demonstrates the competitiveness of our solutions in terms of efficiency, effectiveness and scalability compared with the state-of-art work. 2 Chapter 1 Introduction Mobile (or Multi-Access) Edge Computing (MEC) emerges as a novel computing paradigm accompanying the rise of 5G technology. In terms of the three use cases of 5G network: enhanced mobile broadband, ultra-reliable and low latency, and massive machine-type communications, it requires higher network performance to support those use cases [1]. The previous Mobile Cloud Computing (MCC) can no longer satisfy the requirement of the 5G network, which is limited by its centralized network architecture as shown in Fig 1.1. In MCC, computing resources are centralized at the cloud and such architecture has the following shortages [2]: (1) Clouds are usually far away from end-users (some of them even across continents), which inevitably causes high transmission delay. (2) even though the cloud has plenty of computation resources and has extra strong computation capacity, as the cloud is shared by a very large number of users, the resources allocated to each user are actually limited, which will cause high computation delay. MEC is proposed to leverage the performance gap of MCC. Compare with MCC, MEC has the following advantages that are beneficial from its decentralized architecture [3], as shown in Fig 1.2: (1) instead of using a single powerful centralized server, MEC deploys many small-scale servers to the network edge, which are known as edge nodes (or edge servers). Edge nodes are close to end-users (usually less than 5km), thus it will incur low transmission delay. (2) although each of the edge servers has limited computation resources, as it is shared by only a small group of users, the resource allocated to each user is richer than MCC does. Thus, it 3 CHAPTER 1. INTRODUCTION 4 incurs low computation delay accordingly. Cloud Base Station Base Station Base Station Figure 1.1: Mobile Cloud Computing Network Architecture Base Station Base Station Edge Node Base Station Edge Node Base Station Edge Node Base Station Figure 1.2: Mobile Edge (Multi-Access) Computing Network Architecture Inspired the distributed property of the MEC and its high expectation for network performance, in this thesis, we study the problem of optimal edge node deployment, aiming to provide qualified and low-latency services to massive mobile users citywide with minimum cost. There Motivation 5 are three primary factors that require to be considered during the decision-making process of edge node deployment: First, guaranteeing the Quality of Service (QoS) is a fundamental requirement of the network deployment [2]. For example, latency, as one of the most important QoS factors, should not exceed users’ tolerance [4, 5, 6, 7, 8]. Second, minimizing the deployment cost is always prioritized and should never be neglected [9, 10, 11, 12]. There are many factors that can affect the cost, including edge node site selection, computation resource allocation, computation tasks assignment, etc. Third, since the resource is limited, while MEC is designed to provide users with richer resources, it should be optimized for higher productivity [13, 14, 15, 16, 17, 18, 19]. It is always the ideal case that the selected edge nodes are allocated with “just enough” computation resources. 1.1 Motivation When it comes to deploy edge nodes to the network, there is always a trade-off between the edge node deployment cost and the delay experienced by mobile users [20]. Such a trade-off is highly related to edge node site selection and corresponding resource allocation. Deploying more edge nodes can potentially reduce the transmission delay by decreasing the average distance between base stations and edge nodes. Also, adding more servers (i.e. computing resources) into edge nodes can cut down the computation delay as edge nodes would have higher computation capacity. However, both cases will inflate the overall deployment cost. Fortunately, users would never expect a zero-latency network and instead have tolerance thresholds on the delay. Thus, by leveraging the threshold, we have an opportunity to optimize the edge node deployment strategy with the minimum overall deployment cost. The following sample scenario demonstrates how the edge node selection and the corresponding resource allocation matter to the deployment cost under various user’s delay tolerance values. Motivating scenarios. Fig. 1.3 demonstrates how users’ tolerance on service delay affects the optimal edge node deployment when considering cost-efficiency. In this figure, the blue numbers represent the distance while the black numbers represent the workload of base stations and Motivation 6 edge nodes. The workload and the distance together decide the transmission latency, while the workload matters to the computation delay. Fig. 1.3a shows the initial connections between base stations which are candidate potential locations to deploy edge nodes (i.e., edge nodes co-locate with base stations). Developing an edge node within a base station will introduce a setup cost, while adding servers to an edge node to increase its computing capacity will generate server purchase costs. Given users’ delay tolerance threshold and the goal of cost minimization, placing edge nodes at appropriate base stations with a right number of servers can significantly reduce the overall cost. With the objective of minimizing the total cost, the optimal edge node deployment strategy would vary under different users’ delay tolerance. Fig. 1.3b illustrates an optimal edge node placement in case the users’ delay tolerance threshold is 22s, where the most cost-effective deployment is to develop two edge nodes S1 and S2 . Adding one more edge node is more expensive than adding more servers to existing nodes. However, when we decrease the delay tolerance threshold to 16s, the optimal placement becomes what is shown in Fig. 1.3c. To satisfy this more rigorous delay tolerance requirement, there are two intuitive options: (1) continuously adding more servers to existing edge nodes to further decline the computation delay, or (2) installing a new edge node to decrease the transmission delay. Fig. 1.3c shows that the optimal solution is to install a new edge node instead of adding more servers. Allocating appropriate resources to each edge node is another important factor that can directly affect the deployment cost. In Fig. 1.3c, the workload is measured in a coarse-grained manner by taking the peak workload of each location. The capacity required for s1 , s2 and s3 is 13, 16 and 6 respectively. Table 1.1 records the precise workload of each edge nodes in a series of time scales (i.e., t1 to t5 ). It can be seen that the peak workload (stared number) of each location appears at different times and getting the workload of edge nodes by simply summing up the peak of each location is over-estimated. For example, the peak workload of s1 appears at t4 , which is 9, way lower than the value from the coarse-grained estimation of 13. Thus, a more accurate fine-grained workload estimation can decrease the deployment cost Motivation 7 (a) Initial network (b) OPT with 22s delay (c) OPT with 16s delay Figure 1.3: Example of Optimal EN Deployment under Different Delay Tolerance Research Questions 8 dramatically. Table 1.1: Example of fine-grained workload in BS and EN t1 t2 t3 t4 t5 C F 1 1.2 s1 1 0 4∗ 3 2 b3 4∗ 3 0 2 1 b4 0 1 1 2∗ 0 b5 1 0 0 2 3∗ s2 4∗ 3 2 0 1 b6 0 1 1 2∗ 0 13 9 b7 0 1 0 2∗ 2 16 12 b8 3 4∗ 3 1 0 b9 1 3 4∗ 1 3 s3 0 0 1 2∗ 1 b1 0 1 2 3 4∗ 6 5 C, F represent coarse-grained and fine-grained workload metric respectively Research Questions Motivated by the application scenario in section, to deploy edge nodes to an MEC network we propose the following research questions: • RQ1: How to find the optimal EN locations? – Sub-RQ1: How to define our problem to make it consider the cost and the delay simultaneously? – Sub-RQ2: How to accurately measure the workload and the delay so that it can guarantee the robustness of the network? • RQ2. How to properly allocate resources? – Sub-RQ1: How to measure the workload and delay by looking into each timestamp? – Sub-RQ2: How to efficiently process the large volume of data when it goes down to each timestamp? For RQ1, we formulate the Cost Minimization in the MEC Edge Node Placement problem, which has the goal of minimizing the cost while taking the user’s delay tolerance as the constraint. We also propose a peak-based workload measurement. Furthermore, we precisely measure both the computation delay and the transmission delay. Research Contributions 9 For RQ2, based on our problem formulation RQ1, we further extend it to a fine-grained case by precisely measuring the workload and the corresponding delay at the user request level. Also, we utilize our fine-grained measurement to further refine the resource allocation strategy on the edge nodes to further decrease the computation resource allocated and thus cut down the deployment cost. Please refer to Section 1.3 for more details. 1.3 Research Contributions To the best of our knowledge, few researchers attempted to address the trade-off between cost and delay while considering the computation resource allocation [10, 21]. Despite that, existing studies are subject to the following major limitations. First, existing studies suffer from the scalability issue, making it unpractical to deploy their solution over large-scale realworld datasets. In real-world cases, base stations are large in amount and the number is still increasing (e.g., Shanghai is projected to build 50 5G base stations per km2 [22]). Designing a highly scalable and efficient solution is therefore essential (the detailed discussions can be found in Chapter 2). Second, the issue of delay has not been well addressed. Specifically, it has been ignored by most of existing studies that the computation delay is supposed to decrease if more servers placed in edge nodes. Overall, our Main Contributions in this thesis include: • We formulate a novel yet practical problem to address the trade-off between the deployment cost from service provider’s perspective, and the transmission and computation delay from user’s perspective. We propose a peak workload metric-based measurement to guarantee the robustness of our deployment strategies; in contrast, all previous relevant studies employ the average workload and hence are not robust to handling a large number of (heavy) workloads in peak periods. Moreover, we define a practical delay measurement to ensure its feasibility in real-world cases. (Chapter 3) • We define our problem at various granularity: the base-station-based coarse-grained formulation (Chapter 3.2) and the user-request-based fine-grained formulation(Chapter 3.3). • We prove that our problem is NP-hard. (Chapter 4) Thesis Organization 10 • We develop a suite of approaches to address this problem. Specifically, we propose a Cluster-based Mixed Integer Programming (MIP) method and a Distance Aware Coverage First Search (DA-CFS) algorithm to address the efficiency and effectiveness issue of Coverage First Search (CFS) [23] and MIP [10, 21] respectively. In addition, we propose a fine-grained optimization strategy to further improve the effectiveness of CFS and DA-CFS. (Chapter 5) • We conduct comprehensive experiments over a large-scale real-world dataset to verify the performance of our proposed solutions. Also, we examine the effect of the fine-grained resource allocation strategy on improving the effectiveness of CFS and DA-CFS. It turns out that our solutions have a great advantage in scalability compared with the baseline methods and are competitive in both efficiency and effectiveness. (Chapter 6) 1.4 Thesis Organization We review the related works and identify the research gaps in Chapter 2. Then, we formulate our problem in Chapter 3 and prove the NP-hardness of the problem in Chapter 4. Base on our problem formulation, we provide a suit of solutions in Chapter 5. After that, we do an comprehensive evaluation on our proposed methods in Chapter 6. Finally, we summarise our work in Chapter 7. Chapter 2 Background 2.1 MEC Network and Key Components In the MEC network, there are two key components: base station (BS) and edge nodes (EN). Base stations are also known as cellular base stations, which provide network service to surrounding mobile users. The edge nodes are small-scale servers, which can provide not only network service, but also computing resources [24]. To deploy edge nodes to the network, the service provider is prone to make edge nodes co-located with base stations considering the costsaving. Since the base stations already have the infrastructures to provide network service, simply adding computing facilities (e.g. server units) can upgrade it into an edge node without building everything from the scratch, and thus save the edge node construction cost [2]. For the mobile users, to access the computation resource, they can either offload computing tasks to edge nodes directly, or offload the task to a base station, and the base station would further offload the task to a nearby edge node for computation resources [1]. The distributed network architecture of MEC brings many challenging research problems. In this thesis, we focus on the problem of edge node site selection and the corresponding resource allocation. In the next section, we will do the literature review of this specific research problem. 11 Literature Review 2.2 12 Literature Review Extensive studies have been carried out in the area of deploying cloudlets and edge nodes (also known as edge servers) to facilitate MEC in the past few years. The edge nodes (ENs) and cloudlets are very similar concepts, which are small-scale clouds with limited storage and computation capacity. They usually co-locate with cellular Base Stations (BSs) and WIFI Access Points (APs) [25]. Thus, we review the literature related to edge nodes and cloudlets together for the edge node deployment problem. Edge site selection has substantial effects on the QoS of the MEC network. Few works investigate to place edge devices by exploring undeveloped area[26, 18, 10], because building up everything from scratch is costly. Instead, considering the real cases that there have been well developed mobile networks in cities, the scenario of setting up edge nodes to co-located with existing infrastructures, i.e., base stations, is wildly adopted by most of the existing studies, e.g. [17, 13, 19]. Based on the different objectives, we review the literature by basically dividing them into two major categories: Delay Minimization Prioritized Edge Nodes Placement and Cost Aware Edge Node Placement 2.2.1 Delay Aware Edge Nodes Placement Minimizing delay is a hot research topic in Edge nodes placement. As shown in Table 2.1 there is various edge site selection strategy in the literature, many studies that focus on placing a fixed number of edge nodes, e.g. place K edge nodes, into the network. There are mainly two different assumptions in terms of the edge node capacity: assign edge nodes with various capacity [5, 7, 18] or each edge node has identical capped capacity [4, 6, 13, 14, 15, 16, 17, 19, 26, 27]. In the first category, with edge nodes having various capacities, to achieve the goal of minimizing the delay, the problem becomes how to place the edge nodes to the appropriate place based on the workload of each location. For example, the edge node with larger capacity should be placed into the busy area, e.g., a business center, while the edge nodes with smaller capacity are more likely to be placed in the less-visited area, e.g. rural area. The second category, however, as each node has the identical capacity, to achieve the goal of minimizing delay become to place a various number of edge nodes of each location based on the workload