Applied Science, Faculty of
Electrical and Computer Engineering, Department of
DSpace
UBCV
Cheng, Jiaming
Master of Applied Science - MASc
University of British Columbia
Edge computing (EC) has emerged as a promising architecture for hosting critical services with stringent latency and performance requirements, challenging to address in traditional cloud computing (CC) systems. EC makes distributed computation and storage resources close to end-users, providing low-latency and high-capacity services. Notable use cases of EC include real-time data analytic services, manufacturing automation, and computational offloading for the Internet of Things. Despite the tremendous potential, EC is still in its infancy stage, and many open problems remain to be solved. This thesis lies in the intersection of operations research and network economics, with a specific focus on developing mathematical models for decision-making and economic analysis of edge-cloud network systems. To support rapid response to incidents in EC, we propose a novel resilience-aware edge service placement and workload allocation model that jointly captures the uncertainty of resource demand and node failures. The salient feature of the proposed model identifies the optimal placement and procurement solutions that can hedge against all uncertain realizations of the traffic demand within an uncertainty set. Hence, it enables service providers to balance the trade-off between the operating cost and service quality while considering demand uncertainty and node failures. Furthermore, by leveraging the column-and-constraint generation (CCG) method, we introduce two iterative algorithms that can converge to an exact optimal solution within a finite number of iterations. We further suggest an affine decision rule (ADR) approximation approach for solving large-scale problem instances in a reasonable time. Extensive numerical results then demonstrate the advantages of the proposed model and solutions.
Edge Service Placement and ResourceAllocation Under UncertaintybyJiaming ChengB.Sc., University of Alberta, 2019A THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFMASTER OF APPLIED SCIENCEinThe Faculty of Graduate and Postdoctoral Studies(Electrical and Computer Engineering)THE UNIVERSITY OF BRITISH COLUMBIA(Vancouver)September 2021© Jiaming Cheng 2021The following individuals certify that they have read, and recommend to the Faculty ofGraduate and Postdoctoral Studies for acceptance, the dissertation entitled:Edge Service Placement and Resource Allocation Under Uncertaintysubmitted by Jiaming Cheng in partial fulfillment of the requirements forthe degree of Master of Applied Sciencein Electrical and Computer EngineeringExamining Committee:Dr. Vijay K. Bhargava, Professor, Electrical and Computer Engineering, UBCSupervisorDr. Vincent W.S. Wong, Professor, Electrical and Computer Engineering, UBCSupervisory Committee MemberDr. Mohammad Shahrad, Assistant Professor, Electrical and Computer Engineering, UBCSupervisory Committee MemberiiAbstractEdge computing (EC) has emerged as a promising architecture for hosting critical services withstringent latency and performance requirements, challenging to address in traditional cloudcomputing (CC) systems. EC makes distributed computation and storage resources close toend-users, providing low-latency and high-capacity services. Notable use cases of EC includereal-time data analytic services, manufacturing automation, and computational offloading forthe Internet of Things. Despite the tremendous potential, EC is still in its infancy stage, andmany open problems remain to be solved. This thesis lies in the intersection of operationsresearch and network economics, with a specific focus on developing mathematical models fordecision-making and economic analysis of edge-cloud network systems.To support rapid response to incidents in EC, we propose a novel resilience-aware edge ser-vice placement and workload allocation model that jointly captures the uncertainty of resourcedemand and node failures. The salient feature of the proposed model identifies the optimalplacement and procurement solutions that can hedge against all uncertain realizations of thetraffic demand within an uncertainty set. Hence, it enables service providers to balance thetrade-off between the operating cost and service quality while considering demand uncertaintyand node failures. Furthermore, by leveraging the column-and-constraint generation (CCG)method, we introduce two iterative algorithms that can converge to an exact optimal solutionwithin a finite number of iterations. We further suggest an affine decision rule (ADR) approx-imation approach for solving large-scale problem instances in a reasonable time. Extensivenumerical results then demonstrate the advantages of the proposed model and solutions.iiiLay SummaryEdge computing is an emerging network architecture that distributes storage, computation,control, and networking functions closer to end-user along with cloud computing. Due to di-verse service preferences and uncertainties, it is challenging to design an efficient algorithm foredge service placement and resource allocation. In this thesis, we first introduce several moderndecision-making frameworks that are well-suited to the problem with imperfect information.Next, we propose a novel two-stage adaptive robust service placement and resource manage-ment framework designed to configure a resilient system to mitigate failures by re-assigningresources between edge nodes (ENs) in the presence of demand and failure uncertainty. Theoverarching goal of the thesis is to assist service providers in minimizing the operating costwhile maximizing the service quality by considering demand and node failures.ivPrefaceHere is the submitted journal paper under review:• J. Cheng, D. T. Nguyen, and V. K. Bhargava, “Resilient Edge Service Placement andWorkload Allocation Under Uncertainty,” (Linked to Chapter 2).I hereby declare that I am the primary researcher and author for all research contributionsmade in the submission above. The main content of the thesis also comes from the above sub-mission. I conducted the literature review to develop the original ideas and identify the researchproblems. I formulated the research problems, developed solution approaches, performed math-ematical analysis, and carried out numerical simulations. I also wrote the manuscripts for eachpublication and thesis. Prof. Duong Tung Nguyen is my research collaborator who providedvaluable guidance and insights during the model discussion and manuscript preparation. Prof.Vijay K. Bhargava is my honorable supervisor who offered insightful feedback during thepreparation.vTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiLay Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ixList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xList of Abbreviations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiAcknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiii1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1 Background and Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1.1 Architecture of EC Paradigm . . . . . . . . . . . . . . . . . . . . . . . . 21.1.2 Characteristics and Advantages . . . . . . . . . . . . . . . . . . . . . . 31.1.3 Service Placement Problem . . . . . . . . . . . . . . . . . . . . . . . . . 41.1.4 System Resilience . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61.1.5 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71.2 Decision-Making Problem Under Uncertainty . . . . . . . . . . . . . . . . . . . 81.2.1 Static Decision-Making Under Uncertainty . . . . . . . . . . . . . . . . 81.2.2 Two-Stage Decision-Making Problem Under Uncertainty . . . . . . . . 111.3 Outline of Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13vi2 Resilient Service Placement and Resource Management . . . . . . . . . . . 152.1 Introduction and Research Contributions . . . . . . . . . . . . . . . . . . . . . 162.2 Related Work on Service Placement Problem Under Uncertainty . . . . . . . . 192.3 System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222.3.1 Cost Modeling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232.4 Deterministic Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252.5 Two-stage Adaptive Robust Model . . . . . . . . . . . . . . . . . . . . . . . . . 272.5.1 Uncertainty Modeling . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272.5.2 Two-stage Adaptive Robust Formulation . . . . . . . . . . . . . . . . . 282.6 Proposed Solutions for Two-stage Adaptive Robust Model . . . . . . . . . . . 332.6.1 Column-and-Constraint Generation (CCG) . . . . . . . . . . . . . . . 342.6.2 Affine Decision Rule (ADR) Approach . . . . . . . . . . . . . . . . . . 422.7 Two-Stage Stochastic Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . 462.7.1 Uncertainty Modeling . . . . . . . . . . . . . . . . . . . . . . . . . . . . 462.7.2 Two-stage Stochastic Formulation . . . . . . . . . . . . . . . . . . . . . 472.8 Two-stage Stochastic Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . 482.8.1 Benders Decomposition (BD) Approach . . . . . . . . . . . . . . . . . . 482.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 513 Numerical Results and Operation Insights . . . . . . . . . . . . . . . . . . . . 523.1 Numerical Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 523.1.1 Simulation Setting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 523.1.2 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . 533.1.3 Sensitivity Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 563.1.4 Comparison Between CCG and ADR . . . . . . . . . . . . . . . . . . . 594 Conclusions and Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . 624.1 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 624.2 Future Research Directions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65viiAppendicesA Appendices for Chapter 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70A.1 KKT-based subproblem reformulation . . . . . . . . . . . . . . . . . . . . . . . 70A.2 ADR Reformulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72viiiList of Tables2.1 NOTATIONS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213.1 Computational time comparison . . . . . . . . . . . . . . . . . . . . . . . . . . 61ixList of Figures1.1 Edge network architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.2 Service Placement Model in Edge-Cloud Network . . . . . . . . . . . . . . . . . 61.3 Two-Stage Stochastic Framework . . . . . . . . . . . . . . . . . . . . . . . . . . 121.4 Two-Stage Robust Framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132.1 System model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222.2 Actual Operation Framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262.3 Adaptive Robust Optimization Framework . . . . . . . . . . . . . . . . . . . . . 312.4 Two-Stage Stochastic Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 462.5 Benders Decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 513.1 Performance comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 553.2 The advantage of considering failure uncertainty . . . . . . . . . . . . . . . . . 563.3 The impacts of the uncertainty set on the performance . . . . . . . . . . . . . . 573.4 The impacts of β on the system performance . . . . . . . . . . . . . . . . . . . 583.5 The impacts of the system size on the performance . . . . . . . . . . . . . . . . 583.6 Convergence of CCG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 593.7 Comparison between CCG vs ADR (β = 0.1) . . . . . . . . . . . . . . . . . . . 60xList of AbbreviationsAI Artificial IntelligenceAR Augmented RealityAP(s) Access Point(s)ARO Adaptive Robust OptimizationADR Affine Decision RuleBS(s) Base Station(s)CCG Column-and-Constraint GenerationCC Cloud ComputingDC(s) Data Center(s)EC Edge ComputingEN(s) Edge Node(s)5G Fifth GenerationIoT(s) Internet of Thing(s)KKT Karush–Kuhn–TuckerMEC Mobile Edge Computing, Multi-Access Edge ComputingMILP Mixed Integer Linear ProgrammingNFV Network Function VirtualizationxiOOT Over-the-topPOA Point of AggregationQoS Quality of ServiceRO Robust OptimizationSLA(s) Service Level Agreement(s)SFC(s) Service Function Chain(s)SO Stochastic OptimizationSP(s) Service Provider(s)SDN Software-Defined NetworkingVR Virtual RealityVNF(s) Virtual Network Function(s)VM(s) Virtual Machine(s)xiiAcknowledgementsFirst and foremost, I would like to express my most profound appreciation to my supervisor,Professor Vijay K. Bhargava, for providing me the opportunity to pursue my master’s study.He supported me with his guidance, patience, enthusiastic encouragement during the past twoyears. I have also been very impressed by his deep knowledge, charm of personality, as well assense of humor. I am genuinely encouraged by his extraordinary life experience and the lessonsthat he shared during the group lunch and coffee break. I treasure this remarkable journal ofbeing his student.I am also extremely grateful to my co-supervisor, Professor Duong Tung Nguyen. He is theperson who first introduced me to this line of research. I appreciate his continuous supportsand exceptional kindness throughout my two-year master’s study. He also devoted his timeand effort to share professional knowledge and past experience with me and encouraged me todevelop critical thinking and explore new potentials. It helps me to foster my own interests andattitudes towards research. I also wish to thank Dr. Surya Vara Prasad for their collaborationon my first published conference paper during my master’s study, and I appreciate his valuableinputs and suggestions.I would like to extend my sincere thanks to Professor Maryam Kamgapour for her thought-ful suggestions and constructive feedback during my course project. I would also thank all mycolleagues, Kevin Bradley Dsouza and Tarannum Nisha, for their friendly supports and fruitfuldiscussions. I must also thank for the financial support from Professor Vijay K. Bhargava. Thisthesis is also supported in part by grants from the Natural Sciences and Engineering ResearchCouncil of Canada (NSERC), from Mitacs, and from Rogers Communication Inc, Canada.Finally, yet importantly, I am deeply indebted to my family for their unwavering supportand profound belief in me. Especially, I would like to express my gratitude to my parents, inparticular for their unconditional and immeasurable love.xiiiChapter 1Introduction1.1 Background and MotivationThe COVID-19 pandemic have fundamentally changed the ways we live and work, with moreremote work, more virtual collaboration, as well as increased video streaming, online learning,and online gaming. These changes are expected to last for the foreseeable future, even after thepandemic. Thus, many organizations, companies, and universities across countries are acceler-ating their digital transformations and looking for technology to help them adapt to the newpattern. Cloud computing (CC) has played an essential role in dealing with the ever-growingdata traffic over the past decade. However, along with the proliferation of mobile devices andservices, new applications such as augmented/virtual reality (AR/VR), autonomous driving,manufacturing automation, real-time analytics, and tactile Internet have imposed more strin-gent requirements (e.g., latency, reliability, efficiency) on the communication network. Besides,the era of 5G is foreseeing a massive increase in the number of mobile network subscriptionsand data traffic. The number of global mobile subscriptions would climb from 7.9 billion to8.8 billion from 2021 to 2026, and the global mobile data traffic is expected to more thandouble [2]. Almost all electronic devices have become part of the Internet of things, playingthe roles of data producers and consumers. The data is increasingly produced at the edge ofthe network. It is not always efficient for centralized data processing in the cloud when thedata is produced at the edge of the network. Since cloud data centers (DCs) are often locatedfar away from end-users and data sources, it requires a wholesale rethinking of the networkarchitecture to meet these requirements. To this end, edge computing (EC) has emerged as avital technology that augments the cloud to mitigate network traffic, improve user experience,and enable novel applications [3]. EC offers a virtualized platform that distributes computing,storage, control, and network services closer to end-users to smarten the edge network.1The new architecture of the network provides a shorter communication distance. It allowsoperators to efficiently process downstream and upstream data between the cloud and thecustomer edge, resulting in significant network traffic reduction and user experience improve-ments. For example, service providers (SPs) can leverage edge caching, location-awareness,and real-time data analysis to not only fulfill user content requests locally but also to providehigh-efficiency video coding and optimize video transmission [4]. Also, most of the data gen-erated by end devices can be analyzed at the network edge. Only important content or highlycompute-intensive tasks are forwarded to the cloud for further analysis.Hence, EC has attracted significant attention from both academia and industry. Indeed,large Telcos (e.g., AT&T, Verizon) and cloud providers (e.g., Amazon, Google, Microsoft), aswell as many startups and third-parties, have been investing heavily in the EC technology [5–8].Furthermore, many organizations and groups have been formed to focus on the system design ofEC. For instance, KubeEdge is an open-source platform developed to enable edge computingby extending native containerized application orchestration capabilities to host at Edge [9].Some research groups gradually focus on the confluence of EC and artificial intelligence (AI),namely edge intelligence. It has recently emerged as a fascinating research topic and has manyinteresting and practical applications, such as autonomous driving, e-health [12–14]. From themarket perspective, the global EC market size was valued at USD 1.47 billion in 2018 and isprojected to expand at a compound annual growth rate (CAGR) of 54.0% from 2019 to 2025and reach USD 28.84 billion by 2025 [10].1.1.1 Architecture of EC ParadigmFig. 1.1 illustrates the new network architecture where an EC layer lies between the cloud andthe end devices.1. End-user layer : Bottom most layer, closest to end-users. It comprises various IoT devices(e.g., mobile phones, robotics, autonomous vehicle, manufacturing automation, drones).It is the layer where service/data is typically generated.2. Point of Aggregation (PoA) Layer : The user requests and sensor data are typicallyaggregated at POAs (e.g., switches/routers, base stations) before being transmitted to2Figure 1.1: Edge network architectureENs or the cloud for further processing, analysis, and storage. The data/services can beappropriately allocated to the selected servers (immediate upper layer), which SP decidesbased on the service requirements (e.g., latency, size).3. Edge layer : It consists of a set of one or more computing units (e.g. edge cloud, microDCs, Telecom company, idle server in enterprises, etc) that enable to process and storethe users’ requests [3, 11]. Also, an EN can be co-located with POAs.4. Cloud layer : Upper most layer in this architecture. For cloud layer, it is composed ofseveral servers and large DCs that enable to process complicated services or tasks.1.1.2 Characteristics and AdvantagesBy distributing cloud resources closer to the users, things, and sensors, EC offers significantadvantages and capabilities, such as local data processing and analytics, distributed caching,and enhanced security. Also, EC enables the implementation of various low-latency and high-reliability applications. Next, several main advantages and characteristics of EC are mentionedbelow:1. Latency : Some delay-sensitive services (e.g., AR/VR, video streaming, autonomous driv-ing, remote surgery) have stringent latency requirements (i.e., sub-second processingtime). In order to ensure the service level agreements (SLAs) between SPs and their3subscribers, the delay required for each requested service needs to be satisfied. With EC,the geo-distribution of the various ENs in different areas and their proximity to end-usersprovide lower latency and higher capacity.2. Bandwidth: To process the requested services or computational tasks, SPs may proac-tively download and install service onto chosen ENs based on the spatio-temporal featuresof demand. SPs may only forward some useful data or those tasks with significant analysisto the cloud, which unclogs the network and releases both link capacity and computa-tional capacity. Hence, it speeds up the processing of certain tasks by distributing andperforming some normal computation tasks locally.3. Efficiency and Reliability : With the advent of EC, some small tasks can be offloadedlocally. In addition, EC can provide local back-up for service or customer data (i.e., taskreplica). If any of the tasks fails or stops for any reason, the service scheduler can launchanother instance of your task to replace it in order to ensure the task finished beforethe deadline. If one or some physical machines (PMs) fail(s) at ENs, SPs can re-assignservice to some PMs or adjacent ENs in the normal state.4. Scalability : To process the users’ demand, SPs must purchase the virtual computingresources (e.g., vCPU, RAM) from the EC market to process the users’ demand. Somecompanies or research labs can outsource their idle PCs or servers on the EC market,where the SP can buy from. Without EC, all generated service requests need to be exe-cuted in the cloud, which is inefficient especially when IoT devices grow significantly. ECintervenes as a supplementary paradigm that assists SP in processing all these requestsand improving the network system’s scalability.1.1.3 Service Placement ProblemNumerous problems in EC have been studied over the last few years. There is a rich literatureon edge resource allocation and service placement [15–27]. The problem of joint allocation ofcommunication and computational resources for task offloading in mobile EC has attractedsignificant attention from the wireless community [28]. In [15, 16], the authors propose amarket equilibrium approach for fairly and efficiently allocating heterogeneous edge resources4to multiple budget-constrained services. Cloudlet placement and workload allocation are jointlyoptimized in [17] to reduce the system response time, considering a fixed number of cloudlets.Farhadi et al. [18] propose a two-time-scale optimization model for the joint service placementand request scheduling problem under multi-dimensional resource and budget constraints.In [19], the authors introduce a constant-factor approximation algorithm to determinean optimal service placement solution that maximizes the total user utility, considering theheterogeneity of user locations and edge resources. An IoT application provisioning problemis formulated in [20] to jointly optimize application placement and data routing to support alldata streams while satisfying both bandwidth and delay requirements. Zhao et al. [21] presenta ranking-based near optimal algorithm to efficiently deploy cloudlets among numerous APs inan IoT network. Lexicographic goal programming is used in [22] to address the user assignmentproblem for an SP whose goal is to minimize the number of required edge servers to run theservice while maximizing the number of served users.In essence, the service placement problem is the placement of the service function chains(SFCs), which consists of a list of virtual network functions (VNFs) (e.g., firewalls, videooptimizer, network address translations) that are “stitched” together with predefined orderin the network. Each VNF requires different types of virtual computing resources, which areconsolidated into different types of virtual machines (VMs). Furthermore, VNFs and theirlogical links can easily be embedded and shared with physical resources, which significantlybenefits resource management on large-scale network systems.In the service placement problem studied in the thesis, we assume that service providers(e.g., Over-the-top (OTT) media service providers) do not own any computing resources. Theymust procure a specific amount of virtual computing resources (vCPU, RAM, storage) for ENsfrom the EC market. For example, Netflix pays around $9.6 dollars per month for computingresource on the Amazon Web Services (AWS) that enables Netflix to quickly deploy theirservices (e.g, video streaming, 4K/8K movie) [29]. In general, service placement includesdownloading and installing service as well as finding available resources at ENs that satisfythe service(s) requirements. For instance, the amount of procured resources cannot exceed theresource capacities, and the delay-sensitive service cannot exceed the maximum delay threshold.From the SP’s perspective, they want to make service placement and resource procurement5decisions to deliver the greatest experience for their customers while keeping the operating costas low as possible. Unfortunately, few critical challenges need to be considered and addressedin practice:1. Uncertain demand : The demand is unknown to the SP at the time of making decisions,which incurs the inevitable economic loss because of the over-provisioning or under-provisioning.2. Unforeseen failures: The network system is also vastly heterogeneous with unknownresource performance. That is, some services may come to a halt or fail due to unforeseenreasons. To make matters worse, some ENs may not work for long periods of time withoutprior information.3. Efficiency : Due to the large-scale system, an efficient solution is necessary since there’sno value if SP can not get a solution at the time of making decisions.Figure 1.2: Service Placement Model in Edge-Cloud Network1.1.4 System ResilienceThe goal of the system designer is to configure a resilient network system. In general, resilienceis often referred to as “the ability to anticipate and adapt to changing conditions and mitigateor recover quickly from disruptions or failures”. As a result, the resilience of a system is oftenthe measure of system robustness for the system’s unpredictable failures.6EN failures in the edge-cloud network might severely affect the overall network’s perfor-mance and result in considerable financial losses. Although system designers expect the net-work system to work reliably, the system itself or its working environment could be severelyaffected by various factors, such as power outages. In the presence of uncertain failures, thegoal of the SP is to configure the system such that unmet demand due to an EN failure can bereassigned to a normal EN. Ignoring those issues may result in a less reliable network systemconfiguration that is inefficient in mitigating failures and reassigning tasks to the normal EN.System designers can proactively consider EN failures and the incurred cost of countermea-sures in the system design stage to improve reliability. The countermeasures, i.e., mitigationor recourse operations, involve reassigning the unmet workload to the remaining normal ENs.The unmet demand can be served, and the impact of the failures can be minimized. Hence,the system designer’s goal is to reduce the total weighted cost, which includes the operatingcost in a normal situation and the mitigation cost in a failure. The system designer’s attitudescan be adjusted by weight parameters (e.g., more/less conservative).1.1.5 OverviewIt is non-trivial to model the uncertainties and dynamics and then devise the well-suiteddecision-making algorithms in an acceptable amount of time. In this thesis, SP is primar-ily concerned with (1) location to place the requested service and (2) the specific amount ofresources purchased for each EN while considering those practical constraints.To sum up, the described service placement problem belongs to the decision-making prob-lem under uncertainty - that is, choosing actions based on often imperfect information or ob-servations with unknown consequences. Designers must take into account the various sourcesof uncertainty while balancing their designed objectives of the system. In the main chapters ofthis thesis, we focus on addressing resilience-aware service placement, resource procurement,and resource allocation problems while considering both failure and demand uncertainty. Fromthe SP’s perspective, to enhance user experience and reduce bandwidth cost, SP (e.g., AR/VRcompanies, Google, Netflix, Facebook, Uber) can proactively install their applications, espe-cially latency-sensitive ones, in the proximity of their users. Furthermore, they must ensurethe quality of service and SLAs with contractual customers, both in a normal situation and7in the presence of a failure. The stiff penalties are charged for the unmet portion of demand.To this end, we propose a novel two-stage adaptive robust optimization framework to help theSP determine optimal ENs for placing service and an optimal amount of computing resourcepurchased for each EN.1.2 Decision-Making Problem Under UncertaintyReal-world optimization problems often possess the following attributes: The data are unknownexactly, and the actual data may deviate from their predictions (i.e., forecast values). Besides,the dimension of the data and the decision vector are typically large, and therefore efficientsolutions are required to solve the underlying large-scale optimization problems [34]. In mostdecision-making problems, most planning and operational decisions are made without completeknowledge of both the current situation and the future. Plans that are made when part ofthe contextual information is uncertain are then adjusted when new information is revealed,thus allowing for recourse actions to be taken [35]. In general, this leads to some issues whenmaking a sequence of decisions, intending to balance the immediate benefits of the decisionsand their long-term consequences.This section introduces mathematical frameworks that are well-suited to the decision-making problem with imperfect information and captures the decision maker’s attitude towardsuncertainty. The field of decision-making under uncertainty has gradually gained people’s in-terest since it is more closely related to real-life problems. This chapter reviews the traditionaloptimization frameworks to deal with uncertainty, followed by notable models with some adap-tive improvements for representing uncertainty. Besides, we also highlight the connectionsbetween the different uncertainty representations and decision variables.1.2.1 Static Decision-Making Under UncertaintyStatic optimization is a traditional methodology to solve decision-making problems with uncer-tain data. The salient feature of static optimization, namely single-stage optimization frame-work, is to identify all decision variables “here-and-now”. Therefore, all decision variables maybe non-adjustable since all decisions must be made before uncertainty is revealed. For the sake8of simplicity, we assume that decision variable x represents all “here-and-now” decisions thatbelong to feasible region X .Stochastic OptimizationIn the stochastic optimization (SO) framework , the uncertain parameters are random vari-ables with an exact probability distribution. In contrast, the cost function is to minimize theexpected cost function over this distribution. Despite some known distributions (e.g., normal,Weibull, etc.), it often results in the intractable formulation. Furthermore, the limited sampledata restricts the assumption of complete information about the underlying probability distri-bution. Hence, the obtained solutions might be disappointing when decisions are tested fromthe actual realizations, namely higher out-of-sample cost. Even if the distribution is knownand reasonable, the computational time is also another vital issue needs to be well addressed.Recall that x be the decision variables that belong to feasible region X . We would liketo search over X to find a decision that minimizes the cost function Q. Let ξ be the randomrealization over the sample space Ξ. The decision x can only be determined before the uncer-tainty is disclosed. Combining the considered scenarios in sample space, the expected valueof cost function Q(x, ξ), i.e., Eξ[Q(x, ξ)] is minimized over the sample space Ξ. The generalsingle-stage SO can be expressed as:minx∈Xf(x) = Eξ[Q(x, ξ)] (1.1)Robust OptimizationThe robust optimization (RO) model assumes a complete ignorance about the probabilitydistribution of uncertain parameters. RO only requires moderate information about the un-derlying uncertainty rather than the exact probability distribution of data uncertainty. Theuncertainty in RO is captured by parametric sets, which can be described by some structures(e.g., ellipsoid or polyhedron). It is much easier to construct such an uncertainty set by priorinformation (e.g., nominal value, upper bound & lower bound), which can be easily adjustedby the experience and knowledge from the decision-makers. In the RO model, we can also in-terpret it as single-stage static RO since all decisions are made “here-and-now” before knowing9the actual demand. RO aims to seek the optimal solution that guarantees the best performancein any worst-case scenario within the predefined uncertainty set, leading to over-conservatismand non-negligible economic loss during the operations.The framework of RO incorporates several managerial insights into the decision-makingproblem. The uncertain quantities are modeled as parameters belonging to a pre-specifiedinterval, e.g., the range of forecast controlled by the decision-makers. Decision-makers wouldnot have to be concerned about the consequences of the accuracy of the forecast value. Thebiggest advantage of RO is incorporated by an additional constraint limiting the maximumdeviation of the forecast value from its nominal value. Hence, the first step for the RO model isto construct an uncertainty set based on the knowledge or experience of decision-makers. Thesimplest uncertainty set, box uncertainty set, can be constructed based on its upper bound andlower bound of uncertain realizations. The box uncertainty set was introduced in [32] whichcan be expressed in (1.2) as follows:Ξbox ={ξi | ξLi ≤ ξi ≤ ξUi , ∀i}(1.2)For the box uncertainty set, it is easy to see that the solution is too conservative, although itcan ensure the performance of the obtained decision. Therefore, we introduce a more generaluncertainty set used in this thesis, namely budget uncertainty set [33], which is defined asfollows:ΞBudget ={ξi | ξi = ξ¯i + ξ˜igi, , 0 ≤ gi ≤ 1,∑i|gi| ≤ Γ, ∀i ∈ I}(1.3)where ξ¯i is the nominal value and ξ˜i is the maximal deviation. Hence, ξi can take any valuefrom the interval [ξ¯i, ξ¯i + ξ˜i]. Besides, Γ is the budget of the uncertainty which is to controlthe conservative level of the whole uncertainty set. The value of Γ can be chosen from theinterval [0, I], where I is the number of points in set I. When Γ = 0, the actual value is equalto the forecast value and robust model becomes a deterministic model without consideringany uncertainty. When Γ = I, the uncertainty set becomes box uncertainty set that simplyconsiders all possible realizations of the uncertain point ξi between lower bound (ξ¯i) and upperbound (ξ¯i + ξ˜i).10minx∈Xmaxξ∈Ξf(x; ξ) (1.4)where ξ is the point in the predefined uncertainty set Ξ.1.2.2 Two-Stage Decision-Making Problem Under UncertaintyIn the two-stage models, the decision variables can be classified into first-stage and second-stagedecisions. The two-stage decision-making framework well represents the sequential decision-making process. The first-stage decisions are typically referred to as “here and now” decisionsmade before uncertainty is revealed, while the second-stage decisions are also referred to asthe recourse decisions in a “wait-and-see” manner depending on the respective outcome of theevent. With such a framework, decision-makers can fully utilize the newly revealed informationto make less conservative decisions. For the sake of simplicity, let x be the first stage decisionvariables while y be the second-stage variables, respectively. We assume that both first andsecond-stage variables are non-negative in the following model models, i.e., two-stage stochasticand two-stage robust models.Two-stage Stochastic ModelFor a standard two-stage stochastic model, we denote by the mathematical expectation opera-tor E[.] w.r.t the sample space Ξ. In particular, we define function Q(x, ξ) as the cost functionof the second-stage problem and therefore Eξ[Q(x, ξ)] by the expected cost over sample spaceΞ, In general, a two-stage stochastic linear programming with recourse can be stated as:minxcTx+ Eξ[Q(x, ξ)] (1.5a)s.t. Ax ≥ b, x ≥ 0 (1.5b)Q(x, ξ) = miny{q(ξ)T y | T (ξ)x+W (ξ)y ≥ h(ξ)}(1.5c)where c ∈ Rn1 , b ∈ Rm1 , A ∈ Rm1×n1 are the known parameters that appears in the first-stageproblem and its associated constraints, which do not depend on scenarios ξ. In contrast, thesecond stage problem Eξ[Q(x, ξ)] is constructed over sample space Ξ. Note that the recourse11variables and parameters vary with the realization of random event ξ. Constraint (1.5c) impliesthat inequality needs to be satisfied for all scenarios (ξ) in the sample space (Ξ). Overall,the objection function in (1.5a) is to minimize the total cost, including the first-stage costassociated with x ∈ Rn1 and the expected cost incurred by the second stage decision y ∈ Rn2over all scenarios in the sample space Ξ. Fig. 1.3 shows the two-stage stochastic frameworkwhere the scenario sample space (Ξ) connects first-stage decisions and second-stage decisions.Hence, it is easy to see that the accuracy of first-stage decisions is heavily affected by thequality and quantity of the sample space (data).Figure 1.3: Two-Stage Stochastic FrameworkAs before the expectation here is taken with to the probability distribution of the randomvector ξ. Suppose that the distribution has finite support. That is, ξ has a finite number ofrealizations with respective probability pin, n = 1, . . . , N . Then Eξ[Q(x, ξ)] can be re-writtenas∑Nn=1 pinqTn yn. It is easy to find that the original two-stage problem is equivalent to thefollowing large-scale linear programming problem.minx, yncTx+N∑n=1pinqTn yn (1.6a)s.t. Ax ≥ b, x ≥ 0 (1.6b)Tnx+Wnyn ≥ hn, ∀n (1.6c)x ≥ 0, yn ≥ 0, ∀n (1.6d)Two-stage Adaptive Robust ModelThe great majority of planning and operational decisions are made without a complete in-formation of the current situation and the future. A plan starts to develop when part of12contextual information is uncertain and then adjusted when new information is disclosed, al-lowing recourse action to be taken. Fig. 1.4 indicates the connections between decisions anduncertain realizations in the two-stage robust framework.Figure 1.4: Two-Stage Robust FrameworkSimilarly to the static RO framework, the two-stage adaptive robust model is also basedon the uncertainty. Different from the two-stage stochastic model, the second-stage decisionsare determined after identifying the worst-case scenario ξ within the uncertainty set.minxcTx+ maxξ∈Ξminy∈Ω(x,ξ)bT y (1.7a)s.t. Ax ≥ d, x ≥ 0 (1.7b)Ω(x, ξ) ={y ≥ 0, Wy + Tx ≥ h}(1.7c)where c ∈ Rn1 , b ∈ Rm1 , A ∈ Rm1×n1 are the known parameters that appears in the first-stage problem and its associated constraints. ξ represents the uncertain realizations within thepredefined uncertainty set in Ξ.1.3 Outline of ThesisNext, we will simply describe the outline of this thesis, which is organized as follows:• In Chapter 2, we study the joint optimization of the service placement, resource pro-curement, and workload allocating from the perspective of a SP. We first present thedeterministic mixed-integer linear programming (MILP) formulation without consider-ing any uncertainty. That is, demand is known exactly at the time of making a decision.In practice, SPs use forecast values to make decisions. Besides, we introduce each type13of cost that appears in the formulation and explain the meaning of each constraint. Wethen extend the deterministic model to a two-stage robust framework to assist the SP todetermine the ENs for installing their service (i.e., placement) and the amount of com-puting resource to purchase from each EN (i.e., sizing). The optimized service placementand sizing decisions of the proposed model can hedge against any uncertain realizationswithin the predefined uncertainty set, which consists of a budget uncertainty set of de-mand and a discrete (binary) uncertainty set of failure. Given the optimized placementand sizing decision obtained in the first stage, the optimal resource and workload alloca-tion decisions are determined in the second stage when the uncertainty is revealed. Byleveraging the column-and-constraint generation method [37], we introduce two iterativealgorithms that can converge to an exact optimal solution within a finite number of it-erations. We further suggest an affine decision rule approximation-based approach forsolving large-scale problem instances in a reasonable time. In addition, we also considerthe proposed problem in a two-stage stochastic framework that deals with uncertaintybased on the historical scenarios.• In Chapter 3, we first present the simulation settings and then compare the performanceof the proposed model (ARO) with several benchmarks, i.e., deterministic model (DET),heuristic model (HEU), and stochastic model (SO). We gain some operation insights bycomparison. We also take sensitivity analysis to examine the impact of important systemparameters on the optimal solution. Finally, we analyze and compare the performanceof the proposed algorithm concerning the convergence property, time complexity.• In Chapter 4, conclusions are provided and possible future research directions are alsodiscussed.14Chapter 2Resilient Service Placement andResource ManagementIn this chapter, we focus on the optimal service placement and workload allocation problemfrom the perspective of SP, who can procure computing resources from various ENs to servetheir subscribers located in different areas. The SP aims to improve the user experience whileminimizing operational cost and considering various system uncertainties, making the prob-lem even more complicated. We propose a novel resilience-aware edge service placement andworkload allocation model that jointly captures the uncertainties of resource demand and ENfailures to tackle this issue. We consider an important class of robust optimization, i.e., robustadaptive optimization (ARO), where a planning decision (e.g., service placement; resourceprocurement) is optimized while the workload allocation decision is determined in the secondstage after the uncertainty is disclosed, given the first-stage decisions. The first-stage decisionsare often referred to as “here-and-now” decisions that cannot be adjusted after the uncertaintyis disclosed, whereas the second-stage decisions are known as “wait-and-see” decisions thatcan be adapted to the actual realization of uncertain data. The salient feature of the pro-posed model is that it produces a placement and procurement solution that is robust againstany uncertain realizations within a predefined uncertainty set. By leveraging the column-and-constraint generation method, we introduce two iterative algorithms that can converge to anexact optimal solution within a finite number of iterations. We further suggest an affine de-cision rule approximation approach for solving large-scale problem instances in a reasonabletime. In order to highlight the benefits of the proposed model, we also compare the perfor-mance with other three benchmarks, e.g., Deterministic (DET), Two-stage stochastic model(SO), Heuristic approach (HEU). Extensive numerical results are conducted to demonstrate15the advantages of the proposed model and solutions.2.1 Introduction and Research ContributionsThis chapter focuses on the edge resource procurement and management for a SP which pro-vides a delay-sensitive service (e.g., AR/VR, Pokemon Go, Google Maps, cloud gaming). Toenhance the user’s experience, the SP can provide the service to different distributed ENs toreduce the delay between the users and computing nodes. The SP serves a large number ofusers located in different areas. The main objective of the SP is to maximize the quality ofservice (QoS) while minimizing the total operating cost. Here we measure the QoS in termsof network delay.Due to the heterogeneity of the ENs, it is challenging to select suitable nodes for serviceplacement. Specifically, placing the service on more ENs can lower the overall delay, increasingthe SP’s cost. Furthermore, resource prices at different ENs can vary significantly since geo-graphically distributed heterogeneous ENs have varying sizes and configurations. Therefore,some ENs closer to the users may not be selected due to their higher prices [36]. Besidesservice placement, the SP also has to determine the resource to purchase from each selectedEN. The service placement and resource procurement decisions are often referred to as serviceprovisioning, which is constrained by the operating budget of the SP.Given the provisioning decisions, the SP will optimally allocate the workloads from differentareas to the ENs, which have installed the service to minimize the overall network delay.Suppose all the system parameters are known precisely. In that case, the joint service placementand workload allocation problem can be formulated as a deterministic mixed-integer linearprogram (MILP), which can be solved efficiently using off-the-shelf MILP solvers. In practice,many system parameters are uncertain. Thus, the SP normally uses the forecast values of theseparameters as input to the MILP. However, this deterministic approach can be inefficient ifthe actual values are significantly different from the forecast values. For instance, if the actualdemand is noticeably higher than the forecast demand, under-provisioning may frequentlyoccur, which results in dropping requests and increasing unmet demand. On the other hand,if the actual demand is lower than the forecast demand, over-provisioning happens, which16unnecessarily increases the operating cost of the SP.In addition to demand uncertainty, the unpredictability of EN failures can notoriouslyaffect the system’s performance. An EN can fully or partially fail due to various reasons(e.g., extreme weather events, natural disasters, malware, cyber-attacks, software malfunctions,power outage, links/routers/switches/servers at the EN fail). Suppose the provisioning solutionof the SP contains an EN that fails during the operation period. In that case, the demandinitially assigned to that EN has to be reallocated to the other selected ENs. Thus, ENfailures can deteriorate the user experience since user requests may be reassigned to ENs thatare distant from them. Furthermore, if the procured resources at the other ENs is insufficient tomeet the reallocated demand, a portion of the workload will be dropped, which is undesirable.How to ensure an edge system works properly and automatically adapts and optimizes itsoperation during extreme events is an important and challenging question. Addressing thisquestion can help build up a resilient EC system. In this work, we propose a novel resilience-aware two-stage robust model for an SP, who provides a delay-sensitive service. The proposedmodel can assist the SP to compute an optimal resource provisioning solution that can hedgeagainst the uncertainties of edge resource demand and EN failures.While stochastic optimization (SO) is a popular tool for decision-making under uncer-tainty, it usually requires knowing the probability distribution of uncertain data, which is hardto obtain. Moreover, the uncertainty realization during the operation period may not followthe historical pattern [36]. Additionally, in SO, it is difficult to properly model discrete un-certainties such as EN failure events. Thus, we advocate robust optimization (RO) [33] totackle the joint service placement and workload allocation problem. In RO, the uncertaintiesare captured by parametric sets, known as uncertainty sets, which are much easier to derivethan exact probability distributions. Also, the EN failures can be modeled intuitively usingcardinality constrained sets [35].In our studied problem, the resource provisioning decision needs to be made before theactual workload allocation. Thus, instead of using the traditional static RO approach thatmakes all decisions at the same time, which makes solutions much conservative, we employ thetwo-stage adaptive robust optimization (ARO) approach [36–38] to address the problem. Tothe best of our knowledge, this is the first two-stage robust model for the resilient edge service17placement and workload allocation problem.In EC, there is a lack of tools and techniques for studying resilience concerns relatedto the service placement and resource allocation problem. To the best of our knowledge,no formal mathematical model adequately captures the unpredictability of failures and thedemand fluctuation that occurs after failures. If trying to summarize the previous work, we candraw the following observations: (1) Existing work on EC system has gradually concentratedon the problem of service placement and resource management problem with demand assumedto be known. (2) The stochastic and robust models are relatively less explored on the serviceplacement and sizing problem with uncertainty consideration. Existing works only considerfailure aspects and do not account for demand change that occurs as a result of unanticipatedfailures. For example, Aral et.al [46] consider the resilience aspects by introducing joint chanceconstraints which ensure the most portion of demand will be well-processed by EN with highprobabilities. Li et.al [27] consider the static robust optimization framework where solutionis relatively conservative due to the limitations of static robust model. More details of theprevious work are introduced in Section 2.2. This work improves the existing work in severalaspects. First, a two-stage robust optimization framework has been explored and applied to theproblem that jointly considers the uncertainties of both demand and node failures. Second, aweighting factor is introduced to express the attitude of the SP towards the risk of uncertainties.Third, we propose two new efficient solutions for solving the formulated problem. Our maincontributions are summarized as follows:• Modeling : We propose a novel resilience-aware two-stage robust model for joint opti-mization of edge service placement, resource procurement, and workload allocation. Theuncertainties of demand and EN failures are explicitly integrated into the proposed model,which consists of the service placement and resource procurement in the first stage aswell as the workload allocation decision in the second stage.• Solution Approaches: First, based on the column-and-constraint generation (CCG) method[37], we develop an iterative algorithm to solve the problem in a master-subproblemframework. Second, unlike [37] that uses the Karush–Kuhn–Tucker (KKT) conditions tosolve the subproblem, we propose to solve the subproblem using linear programming (LP)18duality when the demand uncertainty budget is an integer. Third, since the running-time of CCG-based algorithms is sensitive to the uncertainty sets, we introduce an affinedecision rule approximation approach, which is independent of the set sizes, to solvelarge-scale problem instances. Our proposed solutions are novel in the context of cloudand edge computing.• Simulation: Extensive numerical results are shown to demonstrate the superior perfor-mance of the proposed ARO model compared to benchmark models. We also illustratethe benefits of considering both the demand and failure uncertainties. Finally, sensitivityanalyses are conducted to examine the impacts of important system parameters on theoptimal solution.The rest of this chapter is organized as follows. Section 2.2 discuss related work on the topicof service placement problem under uncertainty. In Section 2.13, we present the system modeland problem formulation. Besides, we also describe the detailed formulation in deterministic,proposed model and the problem in a two-stage stochastic framework. Two solution approachesare introduced to solve the proposed ARO model in Section 2.6. Finally, a summary of thischapter is given in Section 2.9.2.2 Related Work on Service Placement Problem UnderUncertaintyThe edge service placement and resource management problem under uncertainty has attracteda lot of attention recently. Reference [23] presents a primal-dual online LP approach for optimalmatching between multiple distributed ENs and multiple services arriving in an online fashion.In [24], the authors formulate the dynamic service placement problem as a contextual multi-armed bandit problem and propose a Thompson-sampling based online learning algorithm tohelp users select an EN for offloading, considering the tradeoff between latency and servicemigration cost. Badri et al. [25] cast an energy-aware multi-service placement problem underdemand uncertainty as multi-stage stochastic problem, which aims to maximize the servicequality under the energy budget constraint.19Distributionally robust optimization is utilized in [26] to tackle the edge service provisioningproblem, with the goal of maximizing the expected revenue under the worst-case distribution ofthe uncertain demand. Li et al. [27] propose an approximation algorithm for the robust servicefunction chain (SFC) placement and resource allocation problem, which aims to maximize theprofit of a network operator considering demand uncertainty. In [36], we employ the KKT-based CCG approach to address the joint edge service placement and sizing problem underdemand uncertainty.A growing literature has focused on the service placement problem in EC from reliabilityand resiliency perspectives. Kherraf et al. [42] formulate an MIP for optimizing workloadassignment to different ENs, considering a probabilistic reliability model for the ENs. Reference[43] studies a reliability-aware dynamic virtual network function (VNF) placement problem tominimize the placement cost while maximizing the number of admitted services. Chemodanovet al. [44] use chance-constrained programming to study the problem of reliable orchestrationof latency-sensitive SFCs, considering probabilistic capacity constraints. Bian et al. [45] castthe distributed service chain composition problem with resource failures as a non-cooperativegame and use weighted potential game to find an optimal Nash equilibrium to reduce requestlatency and network congestion.In [46], the authors evaluate the failure resilience of a service deployed redundantly on theedge infrastructure by learning the spatio-temporal dependencies between edge server failuresand exploiting the topological information to incorporate link failures. Then, they proposea dependency and topology-aware failure resilience algorithm to minimize either redundancycost or failure probability, while maintaining low network latency. Qu et al. [47] consider aresilient edge service provisioning problem, which aims to maximize the expected utility fromserving user requests at the edge in the presence of uncertain service failures. The authorsformulate this as a static max-min RO problem and exploit the monotone submodular propertyto develop two approximation algorithms to solve the formulated problem. This is indeed asimplified model for our problem.20Table 2.1: NOTATIONSNotation MeaningEN, AP Edge Node, Access PointI, I Set and number of areas (APs)J , J Set and number of ENsi, j Area (AP) index and EN indexCj Resource capacity of EN jpj Unit price of computing resource at EN jfj Service placement cost at EN jai,j {0, 1}, “1” if EN j can serve demand from area idi,j Delay between AP i and EN jB Budget of the SPβ Delay penalty parameterPi Penalty parameter for unmet demand in area iρ Weighting factor between costs in two stagesλfi Forecast demand in area iCsj Storage cost at EN jxi,j Resource demand from area i served by EN jwi,j Workload from area i to EN j in the second stageyj Amount of resource procurement at EN jqi Amount of unmet demand in area itj {0, 1}, “1” if the service is installed at EN jl0j {0, 1}, “1” if the service is initially available at EN jzj {0, 1}, “1” if EN j failsλi Actual demand in area iK Node failure budgetΓ Demand uncertainty budgetZ Node failure uncertainty setD Demand uncertainty set212.3 System ModelIn this chapter, we examine the edge resource procurement and management for an SP, whichprovides a delay-sensitive service (e.g., AR/VR, cloud gaming). While the SP does not own anyEN, it can buy edge resources from an EC market, which consists of numerous geographicallydistributed heterogeneous ENs. The SP has subscribers located in different areas, where userrequests in each area are aggregated at an AP. To reduce the network delay and enhance theuser experience, the SP can place the service onto the ENs to serve its users directly at theedge. Hence, two major concerns for the SP are where to install its service and how muchcomputing resource to buy from each EN. Given the procured edge resources, the SP needto decide how to optimally assign workloads from different APs to the ENs. Fig. 2.1 depictsthe system model with five areas and four ENs. The service is installed on EN1, EN2, andEN4. When there is no failure, user requests in area 4 and area 5 can be served by EN4 (i.e.,their closest EN). However, when EN4 fails, the workload from these areas can be reassignedto another EN (e.g., EN2) that has installed the service.Figure 2.1: System modelThe SP is assumed to be a price-taker and has a budget B for purchasing edge resourcesfor usage during the scheduling period (e.g., an hour, a day). Let i be the area index and I bethe set of areas, each of which is represented by an AP. The resource demand in area i is λi.Define j and J as the EN index and the set of ENs, respectively. The resource capacity of ENj is Cj . Also, pj is the price of one unit of computing resource at EN j. The delay betweenAP i and EN j is di,j . In practice, an EN may need to satisfy certain hardware and software22requirements to operate the service. For instance, the service can be only deployed on ENsthat support Pytorch and Ubuntu. Additionally, for a delay-sensitive service, the requestsin an area should be served by ENs that are not too far from that area (e.g., the networkdelay should not exceed a certain delay threshold). We denote by Dmaxi,j the maximum delaythreshold for processing one unit of the given delay sensitive service. Dmaxi,j may vary withdifferent applications. Hence, we use a binary indicator ai,j to indicate whether EN j can servedemand from area i or not. Specifically, ai,j = 1 if the demand from area i can be handled byEN j. The ai,j as follows:ai,j =0, di,j ≥ Dmaxi,j1, di,j ≤ Dmaxi,j(2.1)If the SP places the service onto EN j that does not have initial service available at thebeginning of the planning horizon, SP must download the software and service from remotecloud or nearby ENs and install it onto EN j. Note that the SP only needs to download andinstall requested service at an EN that does not have any service and software installed before.Hence, we define a binary indicator l0j which is equal to 1 if the service is initially availableat EN j. We also denote by F the set of ENs with installed service at the beginning, i.e.F = {j | l0j = 1}. In this case, it incurs a actual cost fj that can be calculated as follows. Weassume that fj,0 be the cost of installing and downloading the service from the cloud to ENj. Similarly, let fj,j′ be the cost of installing and downloading service from EN j′ to EN j.Clearly, we have the following relationship (e.g., fj,0 ≥ fj′ ,j , ∀j, j′) since the distance amongENs is much shorter than the distance to the cloud. Therefore,fj = min{fj,0, minj′fj,j′}(2.2)2.3.1 Cost ModelingSP mainly considers to model several costs during the planning and operation, which includesservice placement cost, storage cost, edge resource procurement cost and network delay cost.Service placement costIf the SP decides to place the service onto EN j that does not have the service installed atthe beginning of the scheduling period, the service needs to be downloaded from the cloud or23a nearby EN, then be installed at the EN. In this case, it incurs a cost fj for downloadingand installing the service onto EN j. The service placement decision is a binary variable thatequals 1 if the service is installed at EN j. Clearly, if the service is available at EN j at thebeginning, this cost becomes zero. If the service is not available at EN j at the beginning, thiscost will be (∑j fjtj). Therefore, to capture both situations, the total service placement costCp over all the ENs can be expressed as follows:Cp =∑jfj(1− l0j )tj . (2.3)Storage costIf the SP places the service at EN j, it needs to pay a storage cost that depends on the size ofthe service and the length of the scheduling period (e.g., one hour). Let sj be the storage costfor the service at EN j. Then, the total storage cost Cs is: (unit: $ per time unit)Cs =∑jsjtj . (2.4)Edge resource procurement costNote that the SP does not own any computing resources. Therefore, SP must purchase com-puting resource from EC market. The computing resource cost at EN j equals the amountof procured resource yj multiplied by the resource price pj (unit: $ per vCPU per time unit).Thus, the total computing resource cost Cc (unit: $ per time unit) is:Cc =∑jpjyj . (2.5)Delay costNote that the network delay between AP i and EN j is di,j . Let β be the delay penaltyparameter (unit: $ per ms per unit of resource demand) for the given delay-sensitive servicethat is delay cost of processing one unit of resource demand. The delay cost between area iand EN j is proportional to the amount of workload allocation from area i to EN j and thenetwork delay between them. Thus, the total delay costs Cd,1 and Cd,2 in the normal situation24and the failure situation, respectively, are:Cd,1 = β∑i,jdi,jxi,j ; Cd,2 = β∑i,jdi,jwi,j . (2.6)Finally, the penalty for unmet demand in each area is proportional to the amount of unmetdemand and the penalty for each unit of unmet demand in that area. Hence, the total penaltyfor unmet demand Cu over all the areas is (unit: $):Cu =∑iPiqi. (2.7)2.4 Deterministic ModelIn the deterministic model, the SP jointly optimizes the service placement, resource procure-ment, and workload allocation decisions when the traffic demand is assumed to be knownexactly. For simplicity, we define auxiliary parameter hj that satisfies hj = fj(1 − l0j ) + sj .We are now interested in minimizing the total cost of the SP and ready to describe all theconstraints of the underlying optimization problem:(DET) miny,t,w,q∑jpjyj +∑jhjtj +∑iPiqi + β∑i,jdi,jwi,j (2.8a)s.t.∑jpjyj + hjtj ≤ B (2.8b)0 ≤ yj ≤ Cjtj , ∀j (2.8c)∑iwi,j ≤ yjtj , ∀j (2.8d)∑jwi,j + qi ≥ λfi, ∀i (2.8e)0 ≤ wi,j ≤ ai,jCj , ∀i, j (2.8f)tj ∈ {0, 1}, ∀j; yj ∈ Z, ∀j; qi ≥ 0, ∀i. (2.8g)Constraint (2.8b) presents the budget constraint that enforces the total operating cost, i.e.,service placement and resource procurement cost, to be less than SP’s budget. Constraint(2.8c) indicates that the amount of resource purchased for EN j must be less than that EN’smaximum capacity. Moreover, the total amount of resource allocated from EN j cannot exceed25the procured amount yj at that node, which is shown in constraint (2.8d). Besides, constraint(2.8e) represents that the resource demand (λf) in each area can either be served by someENs or be dropped (i.e., qi). The portion of dropped demand can be also familiar with unmetdemand qi. The demand from area i can be served by an EN j only if ai,j = 1, that is preciselycaptured by constraint (2.8f). Finally, constraint (2.8g) enforces the feasible regions for theunderlying deterministic optimization problem.The underlying deterministic model in (2.8) is an MILP that can be solve efficiently usingoff-and-shelves solvers. It is worth emphasizing that the deterministic model does not captureany uncertainty (i.e., demand, failure). The SP solves this deterministic problem to obtainthe optimal decision on service placement (t∗) and edge resource procurement (y∗) , using theforecast demand λf .Figure 2.2: Actual Operation FrameworkNote that the SP can then decide the optimal workload allocation (i.e., x) after observingthe actual demand. However, SP does not have prior information about the actual demandwhen making service placement and edge resource procurement decisions. Thus, the procuredresources may not be able to service the actual demand when the actual demand is much higherthan the forecast value, which incurs an higher portion on unmet demand q during the actualoperation stage. In practice, the system can be implemented as follows. The main goal of our26designed model is to find the optimal service placement and resource procurement decisions,which need to be determined before the uncertainties are disclosed. The first stage decisionsy and t are served as the input to the workload allocation problem in (2.9) during the actualoperation stage. After observing the actual realization of the demand λa and failure za, theSP solves the following problem to find the optimal workload allocation decision (w, q) giventhe obtained (t∗, y∗) from designed model.minw, q∑iPiqi + β∑i,jdi,jwi,j (2.9a)s.t. :∑iwi,j ≤ y∗j t∗j (1− zaj ), ∀j (2.9b)∑jwi,j + qi ≥ λai , ∀i (2.9c)wi,j ≤ ai,jCj , ∀i, j (2.9d)wi,j ≥ 0, ∀i, j; qi ≥ 0,∀i. (2.9e)2.5 Two-stage Adaptive Robust Model2.5.1 Uncertainty ModelingSince the exact demand and node failures are usually cannot be predicted accurately at the timeof making the first-stage decisions, these system uncertainties need to be properly capturedand integrated into the decision making model of the SP. In RO, uncertain parameters aremodeled by uncertainty sets, which represent an infinite number of scenarios. The uncertaintysets are usually constructed to balance between the robustness and conservativeness of therobust solution and to make the underlying optimization problem computationally tractable[33]. In this problem, we employ a polyhedral uncertainty set, which is widely-used in the ROliterature [33, 34, 37, 38], to model the demand uncertainty. Define λ = (λ1, λ2, . . . , λI)andλ¯ = (λ¯1, λ¯2, . . . , λ¯I) as the vector of the actual demands and the vector of the nominal valuesof the demands in different areas. Note that I is the number of areas (i.e., I = |I|). Also,let λ˜i be the maximum deviation of the demand in area i from the nominal value λ¯i. Defineλ˜ = (λ˜1, λ˜2, . . . , λ˜I) as the vector of maximum demand deviations. Then, the actual demand λi27belongs to the range of [λ¯i, λ¯i + λ˜i]. This range is normally inferred from the forecast value ofthe demand. The forecast demand λfi in area i is λ¯i +λ˜i2 . The polyhedral demand uncertaintyset D can be expressed as follows:D =λ : λi = λ¯i + giλ˜i; gi ∈ [0, 1],∀i;∑igi ≤ Γ, (2.10)where Γ is called the demand uncertainty budget, which controls the conservative level of therobust solution [33, 34, 36–38]. The uncertainty budget is set by the SP and can take any valuebetween 0 and I. The demand uncertainty set enlarges as Γ increases. If Γ = I, D becomes abox uncertainty set.Besides the demand uncertainty, the SP also faces unpredictable failures of ENs during theoperation period. To capture the uncertainty of the failure situation in the edge network, weemploy a cardinality constrained uncertainty set, which is commonly-used to describe discreteuncertainties [35]. Let zj be a binary indicator which equals 1 if EN j fails. The failureuncertainty set Z can be represented as:Z =zj ∈ {0, 1}|J | : ∑jzj ≤ K, (2.11)where the integer K expresses the maximum number of ENs that can fail at the same time.In other words, the proposed solution is robust against up to K simultaneous EN failures.Obviously, K ≤ |J | = J . As K increases, the optimal solution becomes more robust. However,it is also more conservative (i.e., higher resource provisioning cost). If K is set to be zero, itimplies that the SP does not consider potential node failures in its decision-making process.The SP can choose suitable values of Γ and K to control the level of robustness of theoptimal solution. We use the following set Ξ to jointly capture the uncertainties of demandand EN failures.Ξ =(λ, z) ∈ R|I|+ × B|J | : λ ∈ D, z ∈ Z. (2.12)2.5.2 Two-stage Adaptive Robust FormulationWe are now ready to describe the two-stage robust model, which assists the SP in minimizingits cost while enhancing the user experience. The first-stage decision variables include the28service placement (t), resource procurement (y), and workload allocation (x). In the secondstage, the SP optimizes the actual workload allocation (w) and the unmet demand (q) underthe worst-case realization of the uncertainties. These two stages are coupled by the serviceplacement and resource procurement variables.In the first stage, the SP optimizes the service placement and resource procurement deci-sions. The placement decision at EN j is represented by a binary variable tj , which equals 1if the service is installed at the EN. The amount of resource purchased from EN j is denotedby yj . In the first stage, the SP also optimizes the workload allocation decision xi,j based onthe forecast demand λfi . Given the first-stage decisions y and t, in the second stage, the SPoptimally reallocates the actual demand to different ENs, which have installed the service inthe first stage, under the worst-case uncertainty realization. Since the exact demand and ENfailures are not known to the SP in the first stage, the procured resources may not be sufficientto serve the actual demand. Hence, a portion of the user requests may be dropped. Denote byqi and Pi the amount of unmet demand and the penalty for each unit of unmet demand in areai, respectively. Also, let wi,j be the workload allocated from area i to EN j in the second stage.We often refer to (qi, wi,j) as the recourse actions. Depending on specific market settings, theSP may or may not be allowed to adjust the amount of purchased resources during the actualoperation period. In our model, we do not allow the SP to adjust yj in the second stage,which follows the current practice where cloud providers often require the buyers to purchaseresources for usage for a minimum amount of time (e.g., one hour, one day) [30, 36]. Also,during the operation period, the demand can fluctuate significantly. Thus, the EN owners maynot want the SP to frequently adjust yj for short intervals because the economic benefit issmall while the management cost increases. Our model can be easily extended to allow the SPto readjust the amount of resources in the second stage.Recall that hj = fj(1− l0j ) + sj . Also, ρ is a weighting factor that balances the first-stage29cost and second-stage cost. The two-stage RO problem of the SP can be written as follows:(P1): (1− ρ) miny,t,x∑jpjyj +∑jhjtj + β∑i,jdi,jxi,j+ ρ max(λ,z)∈Ξminw,q∑iPiqi + β∑i,jdi,jwi,j (2.13a)s.t. Ω1(x,y, t) = ∑jxi,j ≥ λfi, ∀i (2.13b)∑jpjyj +∑jhjtj ≤ B, (2.13c)∑ixi,j ≤ yj ≤ Cjtj ∀j; yj ∈ Z, ∀j (2.13d)0 ≤ xi,j ≤ ai,jCj , ∀i, j; tj ∈ {0, 1}, ∀j (2.13e)Ω2(y, t, z, λ) = ∑iwi,j ≤ yjtj(1− zj), ∀j (2.13f)∑jwi,j + qi ≥ λi, ∀i (2.13g)wi,j ≤ ai,jCj , ∀i, j (2.13h)wi,j ≥ 0, ∀i, j; qi ≥ 0,∀i; (z, λ) ∈ Ξ. (2.13i)The objective of the SP is to minimize the weighted sum of the first-stage cost and the second-stage cost. The first term in the first stage expresses the total computing resource cost. Thesecond term is the total of the service placement cost and storage cost. The last term in thefirst stage is the total delay cost. The second-stage cost consists of the penalty cost for unmetdemand and the actual delay cost, respectively. Note that the objective function (2.13a) canbe written as:miny,t,x(1− ρ)∑jpjyj +∑jhjtj + β∑i,jdi,jxi,j+ max(λ,z)∈Ξminw,qρ∑iPiqi + β∑i,jdi,jwi,j. (2.14)30Thus, problem (P1) is indeed a tri-level optimization problem shown in 2.3. The first levelrepresents the problem of the SP before the uncertainties are revealed, which seeks to minimizethe SP’s cost. The second level represents the worst-case realization of the uncertainties z andλ, which try to degrade the service quality (i.e., higher delay and more unmet demand) andmaximizes the SP’s cost. The third level represents the optimal workload allocation problemto mitigate the effects of the uncertainty realization.Figure 2.3: Adaptive Robust Optimization FrameworkThe proposed two-stage robust model can be interpreted as follows. In the first stage, theSP minimizes the total cost based on the forecast demand information. In the second stage,the SP optimizes the cost under the worst-case scenario of the uncertainties. The two stagesare interdependent through the service provisioning decision in the first stage. The weightingfactor ρ reflects the SP’s attitude towards the risk of demand fluctuation and node failures inthe actual operation stage (i.e., the second stage). A larger value of ρ implies the SP is moreconservative and willing to pay more for the resource provisioning cost in the first stage tomitigate the risk of dropping requests and increasing delay due to the system uncertainties inthe operation stage.Let Ω1(x, y, t) be the set of constraints related to the first stage. Also, Ω2(y, t, z, λ) expressesall constraints in the second stage. In particular, constraint (2.13b) indicates that the total31computing resource allocated to each area i must be sufficient to serve the forecast demandin that area. The budget constraint of the SP is presented in (2.13c). The payment (i.e.,provisioning cost) equals the total service placement and resource procurement cost, whichcannot exceed the SP’s budget. Note that β and Pi are used to control the network delay andthe amount of unmet demand. It is easy to see that the resource provisioning cost increasesas β and Pi increase. The delay cost and penalty for unmet demand are virtual costs that theSP does not have to pay.Constraint (2.13d) enforces that the total amount of resource allocated from each EN j toall areas cannot exceed the amount of purchased resource yj at that node. Furthermore, theSP should purchase resource only from the ENs at which the service is installed (i.e., tj = 1).Also, the purchased amount is limited by the capacity Cj of the EN. The workload allocationdecisions are non-negative and the placement variables are binary as shown in (2.13e).In the second stage, we can only allocate resources from ENs that have installed the service(i.e., tj = 1) and are not in a failure state (i.e., zj = 0). Moreover, the total amount of resourceallocated from an EN j cannot exceed the procured amount yj at that node in the first stage.These aspects are captured precisely by constraint (2.13f). It is easy to see that the workloadinitially assigned to a disrupted EN should be reallocated to other non-disrupted ENs. Sinceyj serves as a parameter in the second stage, it can be observed that there exists bilinearterms tj(1−zj) in the inner maxmin problem. To avoid this bilinear term, we can equivalentlyreformulate (2.13f) using the following linear constraints:∑iwi,j ≤ Cjtj(1− zj);∑iwi,j ≤ yj , ∀j. (2.15)Constraint (2.13g) represents that the resource demand in each area can either be served bysome ENs or be dropped (i.e., qi). The demand from area i can be served by an EN j only ifai,j = 1, which is shown in (2.13h). Finally, constraint (2.13i) enforces the feasible regions forthe second-stage variables and the uncertainty parameters.322.6 Proposed Solutions for Two-stage Adaptive RobustModelIn this section, we present three solution approaches, including two variants of the CCG algo-rithm [37] and an affine decision rule (ADR) approximation approach, to solve the formulatedtrilevel problem (P1). First, we can show that (P1) can be written as a large-scale MILP byenumerating over the set of extreme points of the uncertainty set Ξ. Specifically, if the inner-most minimization problem in (P1) is feasible, we can solve its dual maximization probleminstead. Hence, we write the second-stage bi-level problem as a max-max problem, which issimply a maximization problem, over z, λ and dual variables associated with the constraintsof the innermost problem. Because the resulting linear maximization problem is optimizedover two disjoint polyhedrons, the optimal solution of the second-stage problem occurs at anextreme point of set Ξ.Let Ξe = {ξ1, ξ2, . . . , ξK} be the set of K extreme points of Ξ, where ξl = (λl, zl) is thel-th extreme point of set Ξ. Note that λl = (λl1, λl2, . . . , λlI) and zl = (zl1, zl2, . . . , zlJ). Then,problem (P1) is equivalent to:(1− ρ) miny,t,x∈Ω1(x,y,t)∑jpjyj +∑jhjtj + β∑i,jdi,jxi,j+ρ max(λ,z)∈Ξemin(w,q)∈Ω2(y,t,z,λ)∑iPiqi + β∑i,jdi,jwi,j . (2.16)By enumerating all extreme points of Ξe, it is easy to see that this problem is equivalent tothe following MILP:minη,x,y,t(1− ρ)∑jpjyj +∑jhjtj + β∑i,jdi,jxi,j+ ρ η (2.17a)s.t. η ≥∑iPiqli + β∑i,jdi,jwli,j , ∀l ≤ K (2.17b)(wl, ql) ∈ Ω2(y, t, zl, λl), ∀l ≤ K. (2.17c)When Ξ contains a large number of extreme points, solving this MILP may be not practicallyfeasible. Instead of solving the full equivalent problem (2.17) for all extreme points in Ξ, wecan try to solve this problem for a subset of Ξe. Clearly, this relaxed problem contains only33a subset of constraints of the minimization problem (2.17). Thus, this relaxed problem givesus a lower bound (LB) for the optimal value of problem (2.17). By gradually adding moreconstraints (i.e., more extreme points) to the relaxed problem, we can improve the LB of theoriginal problem (P1). This is indeed the core idea behind the CCG method [37] which allowsus to solve (P1) without explicitly solving problem (2.17).2.6.1 Column-and-Constraint Generation (CCG)To solve (P1), we first develop an iterative algorithm based on the CCG method [37] thatdecomposes the original two-stage robust problem into a master problem (MP), which is arelaxation of problem (2.17), and a bi-level max-min subproblem representing the second stage.The optimal value of the MP provides a LB while the optimal solution to the subproblemhelps us compute an upper bound (UB) for the optimal value of the original problem. Also,the optimal solution to the subproblem provides a significant extreme point that is used toupdate the MP. The optimal solution y and t of the MP is used to update the subproblem. Byiteratively solving an updated MP and a modified subproblem, the UB and LB are improvedafter every iteration. Thus, CCG is guaranteed to converge to the optimal solution of theoriginal problem in a finite number of iterations.34Master ProblemInitially, the MP contains no extreme points. A new extreme point is added to the MP atevery iteration. Thus, at iteration k, the MP has k extreme points and can be written as:minx,y,t,η(1− ρ)∑jpjyj +∑jhjtj + β∑i,jdi,jxi,j+ ρη (2.18a)s.t. (2.13b)− (2.13e)η ≥∑iPiqli + β∑i,jdi,jwli,j , ∀l ≤ k (2.18b)∑iwli,j ≤ yj , ∀j (2.18c)∑iwli,j ≤ Cjtj(1− zl,∗j ), ∀j, l ≤ k (2.18d)∑jwli,j + qli ≥ λl,∗i , ∀l ≤ k (2.18e)0 ≤ wli,j ≤ ai,jCj , ∀i, j, l ≤ k; qli ≥ 0, ∀i, l ≤ k, (2.18f)where {(λ1,∗, z1,∗), (λ2,∗, z2,∗), . . . , (λk,∗, zk,∗)} is the set of optimal solutions to the subproblemin all previous iterations up to iteration k. Note that zl,∗ = (zl,∗1 , zl,∗2 , . . . , zl,∗J ) and λl,∗ =(λl,∗1 , λl,∗2 , . . . , λl,∗I ), ∀l. Clearly, the problem in (2.18) is an MILP. The optimal solution to thisMP includes the optimal service placement (tk+1,∗j , ∀j), resource procurement (yk+1,∗j , ∀j),second-stage cost (ηk+1,∗), workload allocation (xk+1,∗i,j , ∀i, j), as well as wl,∗ and ql,∗, ∀l ≤ k.The optimal service placement and resource procurement decisions y∗,k+1 and t∗,k+1 serveas input to the subproblem described in Section 2.6.1. The MP contains only a subset ofconstraints of the problem (2.17), which is equivalent to the original problem (P1). Hence,the optimal value of the MP is a LB for the optimal value of the original problem. The LBachieved after solving the MP at iteration k is:LB = (1− ρ)∑jpjyk+1,∗j +∑jhjtk+1,∗j + β∑i,jdi,jxk+1,∗i,j+ ρηk+1,∗. (2.19)Bi-level “max-min” SubproblemThe subproblem is a bi-level max-min problem representing the decision making process of theSP in the second stage. Specifically, given the first-stage decisions y and t, the subproblem is35given as follows:Q(y, t) = ρ max(λ,z)∈Ξmin(w,q)∈Ω2(y,t,z,λ)∑iPiqi + β∑i,jdi,jwi,j . (2.20)The inner problem can be written explicitly as:minw, q∑iPiqi + β∑i,jdi,jwi,j (2.21a)s.t.∑iwi,j ≤ Cjtj(1− zj), ∀j (u1j ) (2.21b)∑iwi,j ≤ yj , ∀j (u2j ) (2.21c)∑jwi,j + qi ≥ λi, ∀i (si) (2.21d)wi,j ≤ ai,jCj , ∀i, j (pii,j) (2.21e)wi,j ≥ 0, ∀i, j; qi ≥ 0,∀i, (2.21f)where u1j , u2j , si, and pii,j are dual variables associated with the corresponding constraints. Also,t and y in problem (2.21) are the optimal placement and procurement to the latest MP. Thus,at iteration k, for the subproblem, we have tj = tk+1,∗j and yj = yk+1,∗j , ∀j. It can be observedthat problem (2.21) is feasible for any uncertainty realization (λ, z) as well as any values ofy and t because (wi,j = 0, ∀i, j, qi = λi, ∀i) is always a feasible solution to this problem.Therefore, the second-stage problem satisfies the relatively complete recourse condition that isrequired for CCG [37] to work. The relatively complete recourse condition implies that thesecond-stage problem is feasible for any given values of the uncertainty realization as well asthe service placement and resource procurement computed by the MP.The subproblem is a bi-level max-min problem, which is difficult to solve. To make it easierto follow the CCG method, we temporarily assume that there is an oracle that can outputan optimal solution to problem (2.20) for any given values of y and t. We will present twoapproaches to solve the subproblem later. Let (zk+1,∗, λk+1,∗, wk+1,∗, qk+1,∗) be an optimalsolution to the subproblem at iteration k. Then, zk+1,∗ and λk+1,∗ are used as input to theMP in the next iteration. Also, the UB for the optimal value of the original problem (P1) canbe updated as follows:36UBk+1 = (1− ρ)∑jpjyk+1,∗j +∑jhjtk+1,∗j + β∑i,jdi,jxk+1,∗i,j (2.22a)+ ρ∑iPiqk+1,∗i + β∑i,jdi,jwk+1,∗i,j,UB = min{UB, UBk+1}. (2.22b)CCG-based Iterative AlgorithmBased on the description of the MP and the subproblem above, we are now ready to present theCCG algorithm for solving the two-stage robust edge service placement and workload allocationproblem (P1) in an iterative master-subproblem framework, as shown in Algorithm 1.Algorithm 1 CCG-based Iterative Algorithm1: Initialization: set k = 0, LB = −∞, and UB = +∞.2: repeat3: Solve the MP in (2.18) to obtain an optimal solution (xk+1,∗, yk+1,∗, tk+1,∗, ηk+1,∗) andupdate LB according to (2.19).4: Solve the subproblem (2.20) with t = tk+1,∗ and y = yk+1,∗ to obtain an extreme point(zk+1,∗, λk+1,∗) and update UB following (2.22).5: Update zk+1 = zk+1,∗ and λk+1 = λk+1,∗, which are used to create new cuts in the MPin the next iteration. Also, update k = k + 1. Go to Step 3.6: until UB−LBUB ≤ 7: Output: optimal placement and resource procurement decisions (t∗, y∗).The CCG algorithm starts by solving an MP in Step 3 to find an optimal placement andprocurement solution, which serves as input to the subproblem in Step 4. The subproblemgives us a new extreme point, which represents the worst-case uncertainty scenario for thegiven optimal y and t in Step 3. This extreme point is used to generate new cuts (i.e., newconstraints) to add to the MP in the next iteration. Since new constraints related to theuncertainties z and λ are added to the MP at every iteration, the feasible region of theMP decreases. Hence, the LB is weakly-increasing (i.e., improved) after each iteration. By37definition in (2.22), the UB is non-increasing. Furthermore, since Ξe is a finite set with Kelements while the subproblem produces a new extreme point at every iteration, Algorithm1 can converge in a finite number of iterations.Proposition 2.6.1. Algorithm 1 converges to the optimal solution to the original problem(P1) in O(K) iterations.Proof. Since Ξe has a finite number of K elements, to prove the Proposition 2.6.1, we onlyneed to show that before convergence, the subproblem always outputs a distinct extreme pointat every iteration. In other words, if any extreme point (z∗, λ∗) is repeated at two iterations,then LB = UB, which means convergence. We can show it as follows.Assume (x∗, y∗, t∗, η∗) is an optimal solution to the MP and (z∗, λ∗, w∗, q∗) is an optimalsolution to the subproblem in iteration k. Also, the extreme point (z∗, λ∗) has appeared in aprevious iteration. From the definition of the UB in (2.22), we have:UB ≤ (1− ρ)∑jpjy∗j +∑jhjt∗j + β∑i,jdi,jx∗i,j+ ρ∑iPiq∗i + β∑i,jdi,jw∗i,j. (2.23)Since (z∗, λ∗) appeared in a previous iteration, the cuts related to (z∗, λ∗) to be added to theMP at iteration k+1 has already been added previously to the MP. Thus, the MP in iterationk + 1 is identical to MP in iteration k. Hence, (x∗, y∗, t∗, η∗) is also the optimal solution tothe MP in iteration k + 1. Note that we have:LB ≥ (1− ρ)∑jhjt∗j +∑jpjy∗j + β∑i,jdi,jx∗i,j+ ρη∗ (2.24)On the other hands, since (z∗, λ∗, w∗, q∗) is an optimal solution to the subproblem in iter-ation k, from (2.21), obviously we have∑jPiq∗i + β∑i,jdi,jw∗i,j ≤∑jPiqi + β∑i,jdi,jwi,j , (2.25)for every (w, q) that satisfies constraints (2.21b)-(2.21f) given z = z∗ and λ = λ∗. Since theextreme point (z∗, λ∗) has already been identified and related constraints are added to the MPbefore iteration k, there exists j ≤ k where (wl, ql) needs to satisfy constraints (2.21b)-(2.21f)given z = z∗ and λ = λ∗. From (2.18b) and (2.25, at iteration k we have:∑jPiq∗i + β∑i,jdi,jw∗i,j ≤∑jPiqli + β∑i,jdi,jwli,j ≤ η∗. (2.26)38From (2.23), (2.24), and (2.26), we have: LB ≥ UB, which implies LB = UB because LBcannot exceed UB. Thus, any repeated extreme point ξ∗ = (z∗, λ∗) implies convergence. SinceΞe is a finite set with K elements, the proposed algorithm is guaranteed to converge in O(K)iterations.In CCG, we need to solve a bi-level max-min subproblem at every iteration. In Algorithm1, we assume that there is an oracle to solve the subproblem (2.20). In the following, we presenttwo approaches to implement this oracle. The first approach follows the original CCG paper[37] that uses KKT conditions to transform the bi-level subproblem into an equivalent MILP.When the demand uncertainty budget Γ is an integer, we propose an alternative approachthat converts the subproblem to an MILP by using LP duality. The resulting MILP fromthe duality-based approach has significantly less number of constraints and integer variablescompared to the MILP obtained by the KKT conditions.KKT-based Solution for bi-level “max-min” SubproblemSimilar to the CCG algorithm in [37], we can use KKT conditions to transform the subproblem(2.20) into an equivalent MILP problem. The KKT conditions are applied to the innermostproblem (2.21). The resulting set of KKT conditions contains stationarity, primal feasibil-ity, dual feasibility, complementary slackness constraints. Each non-linear complementaryconstraint can be transformed into a set of linear constraints by using Fortuny-Amat transfor-mation [41]. Please also refer to Appendix A.1 for more details. The final reformulation of the39subproblem (2.20) through KKT conditions is an MILP, which is shown as follows.max(z,λ)∈Ξ,w,qρ∑iPiqi + β∑i,jdi,jwi,j (2.27a)s.t. 0 ≤ wi,j ≤M1i,j(1− v1i,j), ∀i, j (2.27b)0 ≤ ρPidi,j + pii,j + u1j + u2j − si ≤M1i,jv1i,j , ∀i, j (2.27c)0 ≤ ρPi − si ≤M2i v2i , ∀i (2.27d)0 ≤ qi ≤M2i (1− v2i ), ∀i (2.27e)0 ≤ Cj tˆj(1− zj)−∑iwi,j ≤M3j v3j , ∀j (2.27f)0 ≤ u1j ≤M3j (1− v3j ), ∀j (2.27g)0 ≤ yˆj −∑iwi,j ≤M4j v4j , ∀j (2.27h)0 ≤ u2j ≤M4j (1− v4j ), ∀j (2.27i)0 ≤∑jwi,j + qi − λ¯i − giλ˜i ≤M5i v5i , ∀i (2.27j)0 ≤ si ≤M5i (1− v5i ), ∀i (2.27k)0 ≤ ai,jCi,j − wi,j ≤M6i,jv6i,j , ∀i, j (2.27l)0 ≤ pii,j ≤M6i,j(1− v6i,j), ∀i, j (2.27m)v1i,j , v6i,j ∈ {0, 1}, ∀i, j (2.27n)v2i , v5i ∈ {0, 1}, ∀i; v3j , v4j ∈ {0, 1}, ∀j, (2.27o)where M1i,j ,M2i ,M3j ,M4j ,M5i and M6i,j are sufficiently large numbers.Duality-based Solution for Bi-level “max-min” SubproblemInstead of the KKT-based reformulation as in [37], when the demand uncertainty budget Γ isan integer, we can transform the subproblem into an MILP using duality-based reformulation.If Γ is non-integer, the SP can round it up to the closest integer, which indeed slightly enlargesthe uncertainty set D and makes the optimal solution more robust. Thus, restricting Γ to bean integer is a mild assumption. Compared to the KKT-based reformulation, the duality-basedreformulation has the advantage of generating fewer variables and constraints, which reduces40computational time, especially for large-scale systems. By using LP duality, we first write thedual of (2.21) and then, the subproblem (2.20) becomes a max-max problem (i.e., simply amaximization problem). Hence, the subproblem (2.20) is equivalent to:ρ maxu1,u2,s,pi,g,z∑iλ¯isi +∑iλ˜isigi −∑jCjtj(1− zj)u1j −∑jyju2j −∑i,jai,jCi,jpii,j(2.28a)s.t. si ≤ Pi, ∀i (2.28b)si − u1j − u2j − pii,j ≤ βdi,j , ∀i, j (2.28c)u1j , u2j ≥ 0, ∀j; si ≥ 0, ∀i (2.28d)∑jzj ≤ K; zj ∈ {0, 1}, ∀j (2.28e)∑jgi ≤ Γ; 0 ≤ gi ≤ 1, ∀i. (2.28f)Note that λ = λ¯i + λ˜igi from (2.10). Also, y and t are parameters in problem (2.28). Due tothe bilinear terms sigi and zju1j , (2.28) is a non-linear optimization problem. Since the termzju1j is a product of a binary variable and a continuous variable, we can linearize it as follows.Define Uj = zju1j . Then, the bilinear term zju1j can be replaced by Uj and the following linearequations: Uj ≤ u1j , ∀j; Uj ≤ Mzj , ∀j; Ui ≥ u1j −M(1 − zj), ∀j; Ui ≥ 0, where M isa sufficiently large number. Furthermore, since Γ is an integer, it is easy to see that therealways exists an optimal solution where gi ∈ {0, 1}, ∀i. Then, the bilinear term sigi becomes aproduct of a continuous variable and a binary variable. Thus, similar to zju1j , we can linearizesigi using a set of equivalent linear equations. Let vi = sigi, ∀i. Then, instead of solving the41non-linear problem (2.28), we can solve the following MILP:ρ maxu1,u2,s,pi,g,z∑iλ¯isi +∑iλ˜ivi +∑jCjtjUj −∑jCjtju1j −∑jyju2j −∑i,jai,jCjpii,j(2.29a)s.t. si ≤ Pi, ∀i; si − uj − pii,j ≤ βdi,j , ∀i, j (2.29b)vi ≤ si, ∀i; vi ≤Mgi, ∀i; vi ≥ si −M(1− gi), ∀i (2.29c)Uj ≤ u1j , ∀j; Uj ≤Mzj , ∀j (2.29d)Ui ≥ u1j −M(1− zj), ∀j (2.29e)u1j , u2j , Uj ≥ 0, ∀j; vi, si ≥ 0. ∀i; pii,j ≥ 0, ∀i, j (2.29f)∑jzj ≤ K; zj ∈ {0, 1}, ∀j (2.29g)∑igi ≤ Γ, gi ∈ {0, 1}, ∀i. (2.29h)When we use the duality-based transformation to solve the subproblem (2.20), instead of using(2.22), we can update the UB at iteration k as follows:UBk+1 = (1− ρ)∑jpjyk+1,∗j +∑jhjtk+1,∗j + β∑i,jdi,jxk+1,∗i,j+ ρ∑iλ¯is∗i +∑iλ˜iv∗i +∑jCjtjU∗j −∑jCjtju1,∗j −∑jyju2,∗j −∑i,jai,jCjpi∗i,j (2.30a)UB = min{UB, UBk+1}, (2.30b)where (s∗, v∗, U∗, u1,∗, u2,∗, pi∗) is an optimal solution to problem (2.29).2.6.2 Affine Decision Rule (ADR) ApproachAlthough CCG can give an optimal solution to problem (P1) within a finite number of iter-ations, its computational time depends on the size of the uncertainty set. From Proposition2.6.1, the computational time is sensitive to the number of extreme points of the uncertaintyset Ξ, i.e., the number of element of Ξe. In the worst-case, it can take a long time to converge if42the uncertainty set has a huge number of extreme points. Hence, we propose an affine decisionrule (ADR) approximation approach [34, 38, 39], which is insensitive to the set size, to solvelarge-scale problem instances.The main idea behind ADR is to restrict the second-stage variables (i.e., recourse variables)to be affine functions of the uncertain data. If these functions are given, then for any realizationof the uncertainties, we can simply use them to compute the suboptimal recourse decisions.Thus, the goal of ADR is to find reasonable functions to approximate the optimal solutionto the original robust problem. While ADR only provides a suboptimal solution, Kuhn et al.showed that ADR performs surprisingly well on many practical problems and it is even optimalin certain problem classes [39]. This motivates us to examine the performance of ADR for ourtwo-stage robust problem (P1).Let qi(λ, z) and wi,j(λ, z) express qi and wi,j as functions of the uncertainties λ and z.Then, the original problem (P1) can be written as follows:(P ′1) : (1− ρ) miny,t,x∑jpjyj +∑jhjtj + β∑i,jdi,jxi,j+ ρ max(λ,z)∈Ξminw,q∑i∈IPiqi(λ, z) + β∑i,jdi,jwi,j(λ, z) (2.31a)s.t. x, y, t ∈ Ω1(x, y, t) (2.31b)∑iwi,j(λ, z) ≤ Cjtj(1− zj), ∀j, ∀(λ, z) ∈ Ξ (2.31c)∑iwi,j(λ, z) ≤ yj , ∀j, ∀(λ, z) ∈ Ξ (2.31d)∑jwi,j(λ, z) + qi(λ, z) ≥ λi, ∀i, ∀(λ, z) ∈ Ξ (2.31e)0 ≤ wi,j(λ, z) ≤ ai,jCj , ∀i, j, ∀(λ, z) ∈ Ξ (2.31f)qi(λ, z) ≥ 0, ∀i; ∀(λ, z) ∈ Ξ (2.31g)In ADR, the second-stage variables wi,j and qi are defined as affine functions of the uncer-tainties λ and z. Thus:wi,j(λ, z) =∑e∈IAei,jλe +∑l∈JBli,jzl +Di,j , ∀i, j (2.32)qi(λ, z) =∑e∈IEei λe +∑l∈JF li zl +Gi, ∀i, (2.33)43where e is area index and l is EN index. Also, Aei,j , Bli,j , Di,j , Eei , Fli and Gi ∈ R. It can beobserved that, for each realization of the uncertain data λ and z, we can readily compute thevalue of w and q by using (2.32) and (2.33). Thus, the objective of the ADR approach is tooptimize the coefficients Aei,j , Bli,j , Di,j , Eei , Fli and Gi in (2.32) and (2.33).By using the ADR (2.32) and (2.33) and the epigraph form for (P ′1), we obtain the followingADR model (2.34) for (P1):(PADR1 ) : (1− ρ) minx,y,tA,B,D,E,F,G∑jpjyj +∑jhjtj + β∑i,jdi,jxi,j + ρ φ (2.34a)s.t. x, y, t ∈ Ω1(x, y, t) (2.34b)φ ≥∑iPi(∑eEei λe +∑lF li zl +Gi)+ β∑i,jdi,j(∑eAei,jλe +∑lBli,jzl +Di,j),∀(λ, z) ∈ Ξ (2.34c)∑i(∑eAei,jλe +∑lBli,jzl +Di,j)≤ Cjtj(1− zj), ∀j, ∀(λ, z) ∈ Ξ (2.34d)∑i(∑eAei,jλe +∑lBli,jzl +Di,j)≤ yj , ∀j, ∀(λ, z) ∈ Ξ (2.34e)∑j(∑eAei,jλe +∑lBli,jzl +Di,j)+(∑eEei λe +∑lF li zl +Gi)≥ λi, ∀i, ∀(λ, z) ∈ Ξ(2.34f)∑eEei λe +∑lF li zl +Gi ≥ 0, ∀i,∀(λ, z) ∈ Ξ (2.34g)∑eAei,jλe +∑lBli,jzl +Di,j ≥ 0,∀i, j, ∀(λ, z) ∈ Ξ (2.34h)∑eAei,jλe +∑lBli,jzl +Di,j ≤ ai,jCj , ∀i, j, ∀(λ, z) ∈ Ξ (2.34i)To solve the ADR model (2.34), we first need to convert each robust constraint into a solvableform. Specifically, we employ LP duality to reformulate each robust constraint into an equiv-alent set of linear equations. Please refer to Appendix A.2 for more details. After converting44each robust constraint into a set of linear equations, we obtain the following MILP:(1− ρ) minx,y,tA,B,D,E,F,G∑jpjyj +∑jhjtj + β∑i,jdi,jxi,j + ρ φs.t. x, y, t ∈ Ω1(x, y, t) (2.35)(A.6)− (A.12) in Appendix A.2Although the ADR approach only gives us a suboptimal solution, our numerical results showthat the ADR solution is quite close to the exact optimal solution. Thus, it provides a goodapproximation scheme for our problem. Furthermore, for some special cases, we can show thatthe ADR approach generates an exact optimal first-stage decision for the original problem(P1). Note that we only care about the first-stage decisions because in the operation stage,the SP eventually re-optimize the second-stage decisions by solving LP problem (2.9) after theuncertainties are revealed. We have the following proposition in regards to the optimality ofthe ADR approach.Proposition 2.6.2 (Optimality of Affine Decision Rule [38]). If the uncertainty set Ξ is asimplex (i.e., the convex hull of its vertices), the affine policy can give an optimal first-stagesolution.Proof. From Proposition 2.6.2, we can show that there exists some special cases where theADR approach gives an optimal solution to the original problem (P1). For example, considerthe case where K = 0 and Γ = 1. In other words, the SP considers only demand uncertaintand set Ξ is the same as set D. Also, ∑i∈I gi ≤ 1. Let g0 ≥ 0 be a slack variable such thatg0 +∑i∈I gi = 1. We consider the following I + 1 vertices of Ξ (i.e., D): (λ¯1, λ¯2, . . . , λ¯I),(λ¯1 + λ˜1, λ¯2, . . . , λ¯I), (λ¯1, λ¯2 + λ˜2, . . . , λ¯I), . . . , (λ¯1, λ¯2, . . . , λ¯I + λ˜I).Recall from (2.10), we have λi = λ¯i + giλ˜i, ∀i. Since g0 +∑i∈I gi = 1, it is easy to seethat:λ = (λ¯1 + g1λ˜1, λ¯2 + g2λ˜2, . . . , λ¯I + gI λ˜I) (2.36)= g0(λ¯1, λ¯2, . . . , λ¯I) +∑i∈Igi(λ¯1, . . . , λ¯i + λ˜i, . . . , λ¯I).Hence, the uncertainty set Ξ is a simplex in this case. As a result, from Proposition 2.6.2,ADR gives an optimal solution to problem (P1) when K = 0 and Γ = 1. By following similar45procedure, we can also show that ADR gives an optimal solution to problem (P1) when K = 1and Γ = 0.2.7 Two-Stage Stochastic ModelThis section will discuss the two-stage Stochastic model for edge service placement and work-load allocation problem and its solution. Since the two-stage stochastic model also capturesdata uncertainty, the performance will be mainly compared with the proposed robust modelin the numerical results.2.7.1 Uncertainty ModelingUnlike RO, as mentioned in Section 1.2, SO optimizes the solution based on the defined set ofscenarios Ξ. Note that n is the scenario index and pin is the probability of scenario ξ. Everyscenario occurs with a specific probability pin such that∑n pin = 1 and the number of scenariosis finite. Given the first-stage decisions, the SP makes scenario-specific recourse decisions, i.e.,actual workload allocation (w, q), after the uncertainty is revealed. Let ξ = {ξ1, . . . , ξn, . . . , ξN}be the set of N scenarios representing the uncertain realizations of the demand and EN failures(i.e., ξn = (λn, zn)), where λni is the demand at AP i in scenario ξn and znj is the failure EN jat scenario ξn.Figure 2.4: Two-Stage Stochastic Model462.7.2 Two-stage Stochastic FormulationInstead of optimizing the workload allocation in the worst-case uncertainty realization in thesecond stage as in the ARO model (P1), in the stochastic model, the SP aims to optimize theexpected cost or “average” cost in the second stage. The meaning of costs and constraints inthe stochastic model is the same as those explained in section 2.3.1.The stochastic model assumes that pin and the demand for each AP in each scenario ξ areknown and given as input to the problem (2.37a) to (2.37f). Thus, the stochastic approachrelies heavily on the accuracy of the data to obtain the exact probability distribution of theuncertainties to have a good performance, which is hard to obtain in practice. The two-stage stochastic edge service placement and workload allocation model is formulated as amixed-integer linear program where the decision variables are continuous or binary. The exactformulation is shown as follow:minx,y,t,w,q(1− ρ)∑jpjyj +∑jfj(1− t0)tj + β∑i,jdi,jxi,j+ ρN∑n=1pinβ∑i,jdi,jwni,j +∑iPiqni (2.37a)s.t. x, y, t ∈ Ω1(x,y, t) (2.37b)∑iwni,j ≤ Cjtj(1− znj ), ∀j, n (µ1j,n) (2.37c)∑iwni,j ≤ yj , ∀j, n (µ2j,n) (2.37d)qni +∑jwni,j ≥ λni , ∀i, n (sni ) (2.37e)0 ≤ wni,j ≤ ai,jCj , ∀i, j, n; (δni,j) (2.37f)qni ≥ 0, ∀i, n (2.37g)where (wn, qn) expresses the second-stage decisions under scenario n. Similar to the AROmodel, the service placement and resource procurement decisions are made in the first stage.Since the set Ξ is finite sample space, we can re-write the expected cost in second stage similarto the form in (1.6). Note that first-stage variables (y,t,x) belong to the first-stage constraint47set Ω1(x, y, t) while (2.37c) - (2.37e) represent the constraints for second-stage variables (w,q)for each scenario n.2.8 Two-stage Stochastic SolutionNote that the problem in a two-stage stochastic framework in (2.37) is a mixed-integer linearprogram (MILP) that a commercial solver can directly solve (e.g., Gurobi, CPLEX, Mosek).However, the solution by using a solver directly may not be efficient with a larger samplespace Ξ. Typically, the two-stage stochastic model requires a large amount of historical datato get reasonable results. This section provides the Bender Decomposition (BD) based master-subproblem iterative algorithm to compute the scenario-based stochastic mixed-integer linearprograms.2.8.1 Benders Decomposition (BD) ApproachBD also requires the relatively complete recourse condition that has already explained in CCGalgorithm analysis. It can be observed that for every feasible first-stage solution y and tand every scenario n, there exists feasible recourse decisions (wi,j , qi) since (qni = λni ,∀i, n,wni,j = 0, ∀i, j, n) is always a feasible solution to this problem. Therefore, the second-stageproblem satisfies the relatively complete recourse condition, which indicates that given everyfeasible first-stage decision (yj , tj), second-stage primal problem is either feasible or bounded.SubproblemFirstly, we define the subproblem that is constructed by taking the duality of the second-stagerecourse problem in scenario n in the kth iteration for given first stage solution (yˆj , tˆj). Let(µn,sn,δn) be the dual variables for constraints (2.37c-2.37e, 2.37f). Hence, the dual problem48of the second-stage recourse problem in scenario n can be expressed as following:SPn : θn = maxx,w∑isni λni −∑jCjtj(1− znj )µ1j,n −∑jyjµ2j,n −∑i,jai,jCjδni,j (2.38a)s.t. sni − µ1j,n − µ2j,n − δni,j ≤ ρ β di,j , ∀i, j, n (2.38b)sni ≤ ρ Pi, ∀i, n (2.38c)sni ≥ 0, ∀i, n; µ1j,n ≥ 0, ∀j, n; µ2j,n ≥ 0, ∀j, n; δni,j , ∀i, j, n (2.38d)Note that the second-stage recourse problem and SPn always have a finite optimal value.Hence we can derive an optimal solution to SPn that is an extreme point of its feasible region.Let (yˆk+1,tˆk+1) be the first-stage solution to the subproblem at iteration k. Then, we canobtain the upper bound (UB) by solving (2.38). The UB can be updated as follows:UBk+1 = (1− ρ)∑jpjyj +∑jfj(1− t0)tj + β∑i,jdi,jxi,j+ θ¯UB = min{UB,UBk+1}(2.39)Master problemNext, we define the master problem for the k-th iteration as MP. we use the result obtainedfrom the subproblem to generate bender optimal cuts in (2.40f) that are linear functions of(µn,sn,δn).49MP: Vk = minθ,y,t(1− ρ)∑jpjyj +∑jfj(1− t0)tj + β∑i,jdi,jxi,j+N∑npinθns.t.∑jxi,j ≥ λfi, ∀i (2.40a)∑ixi,j ≤∑jyj ≤ Cjtj , ∀j (2.40b)∑jpjyj +∑jhjtj ≤ B (2.40c)0 ≤ xi,j ≤ ai,jCj , ∀i, j (2.40d)tj ∈ {0, 1}, ∀j; yj ∈ Z, ∀j (2.40e)θn ≥∑isni λni −∑jCjtj(1− znj )µ1j,n −∑jyjµ2j,n −∑i,jai,jCjδni,j , ∀n (2.40f)At each iteration, master problem (MP) objective value provides a lower bound of objective.Given the optimal first-stage solution at iteration k, we can also obtain an upper bound afterhaving solved the scenario subproblem. If the UB and LB are equal or “close enough”, wecan terminate the algorithm. Let  be the optimality tolerance, which can be calculated byUB−LBUB . The pseudo-code of BD for solving two-stage stochastic problem is:Algorithm 2 Benders DecompositionInput: System Parameters; ρ, β, λ, zOutput: Optimal solution (q∗,w∗, t∗,y∗)Initialization : LB = −∞, UB = +∞, k = 0repeatStep 1: Solve the MP in (2.40) and derive its optimal solution, and an optimal solution(yj ,tj) update the lower bound (LB = Vk).Step 2: For every scenario n, compute subproblem SPn, derive its optimal value θˆn andgenerate a Bender cut in 2.40f based on its optimal solution.Step 3: Compute θ¯ and update upper bound (UB) by (2.39)until UB−LBUB ≤ The algorithm terminates finitely since the extreme points of dual solution is finite. But50there is no guarantee on rate of convergence. In practice, the algorithm usually convergesfast but occasionally disastrous. Since the actual demand can be different from the generatedscenarios, which can be understood as training scenarios, we need to evaluate the performanceof the stochastic model in the actual operation stage over a set of testing scenarios. Similar toother models, the optimized variables (y,t) will also be served as inputs to the problem duringthe actual operation stage, which is defined in (2.9).Figure 2.5: Benders Decomposition2.9 SummaryIn this chapter, we focus on the edge service placement and workload allocation problem whileconsidering both demand and failure uncertainties. The proposed ARO model can assist anSP in determining optimal service placement and resource procurement solutions in the firststage and optimize the workload allocation in the second stage. By implementing this model,the SP can not only drastically improve the user experience but also reduce its cost. To solvethe underlying robust problem, we introduced three approaches, including two variants of theCCG algorithm and the ADR approach. In addition, we consider the two-stage stochasticoptimization framework to capture the uncertainties in edge service placement and workloadallocation problem.51Chapter 3Numerical Results and OperationInsights3.1 Numerical Results3.1.1 Simulation SettingWe consider an edge system with 20 areas and each area has an EN (i.e., I = |I| = |J | =J = 20). We will also perform sensitivity analysis on larger networks with more than 20 areas.Since we are not aware of any public data for edge networks, similar to [15, 17, 36], we adoptthe popular Barabasi-Albert model to generate a random scale-free edge network topology.The link delays are generated randomly in the range of [2, 5]ms [36]. Then, the network delaybetween an AP i and EN j is the delay of the shortest path between them. We assume thatall ENs area eligible to serve demand from every area, i.e., ai,j is set to be 1, ∀i, j.Using the hourly price of the m5d.xlarge Amazon EC2 instance [30] as a reference, theunit resource prices at the ENs are randomly generated from $0.02 to $0.06 per vCPU-hour.Also, the capacities of the ENs are set randomly among 32, 48, and 64 vCPUs. The serviceplacement and storage costs (hj) are randomly generated in between $0.08 and $0.1 (unit: $per hour). The budget of the SP is set to be 20 (unit: $ per hour), which can be adjusted bythe preference of the SP. We also assume that the service is not available on any EN at thebeginning (i.e., l0j = 0,∀j). By analyzing the trace in [31], we randomly generate the nominaldemand in each area between 5 and 40. Also, define α as the ratio between maximum demanddeviation λ˜i and the nominal demand λ¯i (i.e., λ˜i = αλ¯i,∀i).In the default setting, ρ = 0.2, Γ = 5, K = 2, β = 0.1, α = 0.6, and Pi = P = 5, ∀i. Wewill also vary these parameters when conducting sensitivity analysis. All the experiments are52conducted in MATLAB environment using CVX1 and Gurobi2 on a laptop with an Intel Corei7-8700K CPU and 16GB of RAM.3.1.2 Performance EvaluationFirst, we compare the performance of the proposed two-stage robust (ARO) model (P1) withthree benchmarks:1. Deterministic model (DET): see formulation in (2.8). In this model, the SP uses theforecast demand and does not consider EN failures when making decisions.2. Two-stage stochastic model (SO): see Section 2.37. This model aims to optimize theexpected system performance over a set of scenarios generated from historical data or acertain probability distribution.3. Heuristic approach (HEU ): this scheme uses the forecast demand to make the serviceplacement and workload allocation decision. The SP first sorts the areas based on theirdemands. Then, the workload in each area is allocated one by one, starting from thehighest demand area. For each area, the service is placed onto its closest EN and thewhole demand of the area is assigned to this EN if this EN has sufficient capacity.Otherwise, a portion of the demand is assigned to this EN and the remaining is allocatedto the second-closest EN. This process is repeated until the demand is fully allocated.The usable capacity of each EN is updated during the process.For the SO scheme, we generate the demand scenarios from a truncated multivariate normaldistribution [36]. These (training) scenarios are used as input to the SO model shown in Section2.37. The output of the SO model is the optimal service placement and resource procurementsolution (t, y). Similarly, we solve the deterministic model in Section 2.8, the ARO model(P1), and run the heuristic scheme to find different optimal service placement and resourceprocurement solutions. These solutions are computed before the actual operation stage. Forall four schemes, given the service placement and resource procurement decisions in the firststage, after observing the actual realization of the demand and the EN failures, the SP will1http://cvxr.com/cvx/2https://www.gurobi.com/53solve the linear problem (2.9) to determine the actual workload allocation and unmet demanddecisions. The total cost of each scheme is the total of the provisioning cost in the first stageand the actual cost in the operation stage (i.e., second stage), expressed in $ per unit time ofplanning horizon (e.g., one hour).To compare the performance of these schemes, we use Monte-Carlo simulation and generate1000 (testing) scenarios to represent the demand and failures in the actual operation stage.Specifically, the actual demand is generated from a (truncated) log-normal distribution [36]and the EN failures are generated randomly from the failure uncertainty set Z. We have alsoused other distributions to generate the demand, and observed similar trends and insights forall the figures. In the following, the average cost is the expected actual cost from the 1000generated scenarios, whereas the worst-case cost is the highest cost among these scenarios.Figs. 3.1(a)-3.1(b) compare performance of the four schemes when the failure budget Kvaries. We can find that the actual costs of all the schemes increase when the number ofpossible failures K increases. Furthermore, ARO significantly outperforms the other schemes.It is because both the demand and failure uncertainties are explicitly captured in ARO. Thus,the ARO solution typically installs the service on more ENs and procures resources moreevenly among the selected ENs, which makes it more resilient to unexpected failures of ENsand demand fluctuation. When a failure happens at an EN that has installed the service in thefirst stage, the workload initially assigned to this node can be reallocated to the other selectedENs. The SO scheme performs better than the deterministic and heuristic schemes since the SOmodel takes the uncertainties into account when making the first-stage decisions. However,SO does not consider worst-case uncertainty realization. Moreover, the actual uncertaintyrealization may not always follow the historical pattern. Hence, SO performs worse thanARO. Figs. 3.1(c)-3.1(d) further confirm the superior performance of the proposed ARO schemecompared to the other schemes. Additionally, it is easy to see that the total cost increaseswhen the unmet demand penalty P increases. Figs. 3.1(a)-3.1(d) show another advantage ofARO is that the its cost does not vary much when K or the unmet demand penalty changes.Therefore, ARO is a preferred method for SPs who require high quality of service.In the following, we study the proposed ARO scheme only. To illustrate the benefit ofintegrating failure uncertainty in the decision-making model of the SP, we compare the per-541 2 3 4 5 6 7 8Failure Budget K050100150200Total costAROSODETHEU(a) Average cost1 2 3 4 5 6 7 8Failure Budget K0100200300400Total costAROSODETHEU(b) Worst-case cost0.2 0.4 0.6 0.8 1 1.2 1.4 1.6Penalty Scaling Factor 050100150200250300Total costAROSODETHEU(c) Average cost0.2 0.4 0.6 0.8 1 1.2 1.4 1.6Penalty Scaling Factor 0100200300400Total costAROSODETHEU(d) Worst-case costFigure 3.1: Performance comparisonformance of the proposed ARO model with and without failure consideration. The reason isthat EN failure is less likely to occur in practice. In a normal state, the consideration of failuregenerally results in additional provisioning costs. This collection of experiments will show thatconsidering EN may keep provisioning costs low and assure service quality in the event of afailure. For the case without considering failures, the SP can simply set K = 0. For AROwith failure consideration, we set K to be 2 (i.e., the first-stage decisions are robust againstup to any two simultaneous failed ENs). Figs. 3.2(a)-3.2(b) imply that a small increase in theprovisioning cost for considering failures (K = 2) can significantly reduce the SP’s cost duringnode failure events. Although we do not present the result here, the benefit of considering55failures (i.e., the gap between two curves in each figure) increases drastically when the unmetdemand penalty P increases. Hence, failure consideration is important for SPs who need tomaintain high service quality (i.e., less unmet demand).For ARO with K = 2, it can be observed that the cost increases slowly when the numberof actual failures is small, which implies that a minimal preparation (for K = 2) can make thesystem more resilient to unexpected failures. When more than five ENs (i.e., more than 25% ofENs) fail simultaneously, the cost increases faster because the probability that an EN selectedfor service placement in the first stage fails increases. To hedge against a large number ofEN failures, the SP obviously should set K to be higher. However, it will increase the serviceprovisioning cost. Hence, based on the desired level of robustness and resiliency, the SP needsto decide a proper value for K.1 2 3 4 5 6 7 8Actual Number of Failures20406080100Total costK = 0K = 2(a) Average cost1 2 3 4 5 6 7 8Actual Number of Failures50100150200Total costK = 0K = 2(b) Worst-case costFigure 3.2: The advantage of considering failure uncertainty3.1.3 Sensitivity AnalysisNext, we examine the impacts of important system parameters on the optimal solution.Figs. 3.3(a)-3.3(b) illustrate the impacts of the uncertainty set on the system performance.It can be observed that the total cost increases as the uncertainty set enlarges (i.e., when Kand Γ increase). Hence, there is an inherent tradeoff between the system cost and the level ofrobustness. Also, we can see that the system cost increases when ρ increases (i.e., the SP is56more risk-averse). Note that “Objective” is the optimal objective value of (P1).0 0.2 0.4 0.6 0.8 10100200300400ObjectiveK = 1K = 3K = 5K = 7(a) Γ = 5,Varying ρ and K0 0.2 0.4 0.6 0.8 10200400600800Objective = 1 = 5 = 10 = 15 = 20(b) K = 2, varying ρ and ΓFigure 3.3: The impacts of the uncertainty set on the performanceThe impacts of the delay penalty parameter β on the optimal solution are presented inFigs. 3.4(a)-3.4(b). A higher value of β indicates the service is more delay-sensitive and resultsin a higher cost. It is because when β is high, the SP will try to allocate the demand inevery area to its closest ENs to reduce the delay penalty cost. Thus, cheaper ENs may not bechosen. Fig. 3.4(a) further shows that the cost increases as ρ increases. Additionally, it canbe seen from Fig. 3.4(b), a higher value of α (i.e., a larger uncertainty set) leads to a highercost. Indeed, although not shown here, the first-stage provisioning cost also increases whenthe uncertainty set size, the delay penalty, and ρ increase.570 0.2 0.4 0.6 0.8 1050100150200Objective = 0.1 = 0.2 = 0.3 = 0.4 = 0.5(a) Varying ρ and β0.2 0.4 0.6 0.8 1050100150200Objective = 0.1 = 0.2 = 0.3 = 0.4 = 0.5(b) Varying α and βFigure 3.4: The impacts of β on the system performanceFinally, we examine the impacts of the system size on the optimal solution. Intuitively,when the number of ENs decreases, the total edge resource capacity is reduced. When thenumber of areas increases, the total demand in the system increases. As expected, Fig. 3.5(a)shows that the total cost decreases as the number of ENs increases. The reason is that the SPhas more options (i.e., more flexibility) for purchasing resources when more ENs are available.Also, as can be seen in Fig. 3.5(b), the total cost increases when the number of areas increases.This result is intuitive since the SP needs to procure more resources to serve higher demand.10 12 14 16 18 20Number of ENs0100200300400500ObjectiveK = 1K = 3K = 5K = 7(a) Varying number of ENs10 15 20 25 30 35 40Number of Areas20406080Objective = 1 = 5 = 10 = 15 = 20(b) Varying number of areasFigure 3.5: The impacts of the system size on the performance583.1.4 Comparison Between CCG and ADRConvergence of CCGFigs. 3.6(a)-3.6(b) show the convergence of the CCG algorithm for different values of K andΓ. The algorithm converges within a small number of iterations in both cases. However, thenumber of iterations increases as K and Γ increase. Note that larger values of K and Γ implythe uncertainty set Ξ has more extreme points. Thus, the convergence of CCG is sensitive tothe uncertainty set (i.e., K and Γ here).1 2 3 4 5 6 7Iteration020406080ObjectiveUBLB(a) K = 2, Γ = 51 2 3 4 5 6 7 8 9 10111213Iteration050100150200ObjectiveUBLB(b) K = 5, Γ = 10Figure 3.6: Convergence of CCGCCG and ADRIn the following, we analyze and compare the performance of the CCG-based iterative algo-rithms and the ADR approach. Fig. 3.7(a) depicts the optimal costs produced by CCG andADR when we vary the demand uncertainty budget Γ and the failure budget K. Recall thatCCG outputs an exact optimal solution for our problem (P1) while ADR is an approximationscheme. It is easy to see that the both the total cost and the provisioning cost produced bythe ADR policy are quite close to the exact optimal values obtained from the CCG method.Additionally, the optimality gap is small when K is small. In practice, the number of simulta-neous failures is typically small, except during extreme events like natural disasters. Indeed,59two failures in our setting already corresponds to 10% of nodes fail. Hence, ADR can be analternative tool for the SP to solve most of the practical cases.1 2 3 4 5 6 7 8Failure Budget K203040506070Total costADR ( = 1)CCG ( = 1)ADR ( = 10)CCG ( = 10)(a) Total cost1 2 3 4 5 6 7 8Failure Budget K2025303540Provisioning costADR ( = 1)CCG ( = 1)ADR ( = 10)CCG ( = 10)(b) Provisioning costFigure 3.7: Comparison between CCG vs ADR (β = 0.1)Table. 3.1 reports the running-time of the KKT-based CCG, duality-based CCG, and ADRalgorithms for different values of K. From the table, we conduct the experiments based on thelarger size of uncertainty set (i.e., K = {5, 7, 9}, Γ = 10). We can see that the computationaltime of the CCG-based algorithms is sensitive to K, thus, it is sensitive to the uncertainty set.On the other hands, the computational time of ADR almost has the similar time computationw.r.t different K. It verifies the main idea of ADR that is not sensitive to the uncertainty setbecause ADR solves an MILP that does not depend on the number of extreme points of Ξ. Also,the KKT-based CCG algorithm is generally slower than the duality-based CCG algorithm sincethe KKT-based subproblem reformulation has a significantly larger size (in terms of numberof constraints and integer variables) compared to the duality-based subproblem reformulation.For example, when K = 9, the KKT-based CCG algorithm does not converge after 10 hours butduality-based CCG algorithm can still get the solution. We have also conducted experimentsfor various values of K and Γ and found that the CCG algorithm normally converges quicklyfor small values of K and Γ. Also, the duality-based CCG algorithm typically runs fasterthan the KKT-based CCG algorithm. For large uncertainty sets, instead of CCG, the SP mayuse ADR to obtain a good approximation solution in a reasonable time. In practice, the SP60can run both the duality-based CCG and ADR algorithms in parallel and only implement thesolution obtained by the ADR algorithm if the duality-based CCG does not converge after acertain amount of time.Running time comparison (Γ = 10)K Duality-based CCG KKT-based CCG ADR5 1431.5s 3387s 162.87s7 3287s 11876s 275.28s9 4416s NA 287sTable 3.1: Computational time comparison61Chapter 4Conclusions and Future Work4.1 ConclusionsEdge computing is a new and promising paradigm that aims to bring services and utilities closerto end-users for ensuring fast processing. It not only enables a variety of IoT applications butalso reduces network traffic, enhancing user experience, especially for the delay-sensitive ser-vices. By placing storage, computing, control, and networking resources closer to the networkedge, EC offers remarkable advantages and capabilities, including local data processing, lo-calized services, edge caching, edge resources pooling and sharing, and enhanced privacy andsecurity.This thesis focuses on the optimal edge service placement and workload allocation problemfrom the perspective of service providers (SPs), who serves a massive number of users locatedin different areas. The objective of the SP is to minimize the operating cost while improvingthe service quality. While placing the service on more ENs can lower the overall network delaywhen serving users’ demand, it may drastically increase the SPs’ cost. As a result, there isan inherent trade-off between the operating cost of SPs and the overall network delay of therequests.In addition, various uncertainty factors such as demand and hardware failure make theedge service placement problem even more complicated. To this end, firstly, we propose a two-stage adaptive robust optimization framework that jointly captures the demand uncertaintyand node failures. In the first stage problem, the SP determines the optimal service place-ment and resource procurement decisions before uncertainty is revealed. Given the first-stagedecision, the SP reallocates the actual demand to the selected ENs with installed service. Byimplementing this model, the SP can not only significantly improve the user experience butalso reduce the operating cost and network delay.62Secondly, to solve the underlying optimization problem, we introduce three approaches,including two variants of the Column-and-constraint generation (CCG) algorithm and theaffine decision rule (ADR) approach. The CCG-based iterative algorithm decomposes theproposed two-stage robust problem into a master problem (MP) and a bi-level ”max-min”subproblem. The bi-level ”max-min” subproblem can be reformulated using KKT or dualitytheorem that provides upper bound of solution. MP provides a lower bound. When addingmore extreme points/cuts to MP, the upper bound and lower bound are improved after everyiteration and are guaranteed to converge to the optimal solution of the original problem. Thecomputational of CCG is sensitive to the size of the uncertainty set since the algorithm needs toenumerate extreme points of the uncertainty set. Instead, we proposed another approximation-based algorithm, i.e., ADR, that can provide a sub-optimal solution to the original problem ina reasonable time. The main idea of ADR is to enforce the second-stage recourse variables tobe affine functions of uncertain parameters. Given these functions, the goal of ADR is to findthe reasonable parameters of the defined affine function to approximate the sub-optimum tothe proposed problem.Lastly, we also provide the deterministic model as well as the formulation in a two-stagestochastic framework, which can be solved by an off-and-shelves solver directly. Additionally,the conducted experiments also illustrate the advantages of the proposed two-stage adaptiverobust model compared to the deterministic, stochastic, and heuristic methods.4.2 Future Research DirectionsThere are several interesting directions for future work, which can be classified into two mainaspects:1. Modeling: We only consider one type of computing resource (vCPU) in this thesis.We would like to extend the model to consider virtual network functions (VNFs) andmultiple resource types, as well as multi-period workload allocation. Finally, we plan tomodify the proposed model to study the robust edge network design problem from theperspective of an edge infrastructure provider.2. Uncertainty: We only discuss EN failures in this thesis, which implies that the workload63must be re-assigned to other nodes if such failures occur. We would like to integrate otherfailures, such as link failures and partial EN failures, into the proposed two-stage robustmodel. Besides, we are also interested in considering constructing the correlated failureuncertainty set. Some other uncertainty factors, such as edge resource prices, can alsobe taken into account.64Bibliography[1] W. Shi, J. Cao, Q. Zhang, Y. Li, and L. Xu, “Edge computing: vision and challenges,”IEEE Internet Things J., vol. 3, no. 5, pp. 637–646, Oct. 2016.[2] [Access June 2021] https://www.ericsson.com/en/mobility-report[3] M. Chiang and T. Zhang, “Fog and IoT: An overview of research opportunities,” IEEEInternet Things J., vol. 3, no. 6, pp. 854–864, Dec. 2016.[4] X. Jiang, F. R. Yu, T. Song and V. C. M. Leung, “A survey on multi-access edge computingapplied to video streaming: some research issues and challenges,” IEEE Commun & Surv.Tut., vol. 23, no. 2, pp. 871-903, 2021.[5] [Access June 2021] https://aws.amazon.com/wavelength/[6] [Access June 2021] https://www.datacenterknowledge.com/edge-computing/why-google-cloud-and-att-may-merge-their-telco-edges[7] [Access June 2021] https://news.microsoft.com/2019/11/26/att-integrating-5g-with-microsoft-cloud-to-enable-next-generation-solutions-on-the-edge/[8] [Access June 2021] https://www.lightreading.com/the-edge/verizon-vodafone-embrace-amazons-aws-for-edge-computing-with-5g/d/d-id/756060[9] [Access June 2021] https://kubeedge.io/en/[10] [Access June 2021] https://www.grandviewresearch.com/industry-analysis/e-commerce-market[11] Y. Mao, C. You, J. Zhang, K. Huang, and K. B. Letaief, “A survey on mobile edgecomputing: the communication perspective,” IEEE Commun & Surv. Tut., vol. 19, no. 4,pp. 2322–2358, 2017.65[12] S. Wang, T. Tiffany, T.Salonidis, K. Leung, C. Makaya, T.He and K. Chan, “Adaptivefederated learning in resource constrained edge computing systems,” IEEE J. Sel. AreasCommun., vol.37, pp.1205-1221, 2019.[13] H. Li, K. Ota and M. Dong, “Learning IoT in edge: Deep learning for the Internet ofThings with edge computing.” IEEE Network, vol. 32, no. 1, pp. 96-101, 2018.[14] M. Cui, S. Zhong, B. Li, X. Chen and K. Huang, “ Offloading autonomous driving servicesvia edge computing,” IEEE Internet Things J., vol. 7, no. 10, pp. 10535-10547, Oct. 2020.[15] D. T. Nguyen, L. B. Le, and V. Bhargava, “Price-based resource allocation for edgecomputing: a market equilibrium approach,” IEEE Trans. Cloud Comput., vol. 9, no. 1,pp. 302–317, Jan.–March 2021.[16] D. T. Nguyen, L. B. Le, and V. K. Bhargava, “A market-based framework for multi-resource allocation in fog computing,” IEEE/ACM Trans. Netw., vol. 27, no. 3, pp. 1151–1164, Jun. 2019.[17] M. Jia, J. Cao, and W. Liang, “Optimal cloudlet placement and user to cloudlet allocationin wireless metropolitan area networks,” IEEE Trans. Cloud Comput., vol. 5, no. 4, pp.725-–737, Oct.–Dec. 2017.[18] V. Farhadi, F. Mehmeti, T. He, T. L. Porta, H. Khamfroush, S. Wang, K.S. Chan, andK. Poularakis, “Service placement and request scheduling for data-intensive applicationsin edge clouds,” IEEE/ACM Trans. Netw. , vol. 29, no. 2, pp. 779–792, Apr. 2021.[19] S. Pasteris, S. Wang, M. Herbster, and T. He, “Service placement with provable guaranteesin heterogeneous edge computing systems,” Proc. IEEE INFOCOM, Paris, France, Apr.2019.[20] R. Yu, G. Xue, and X. Zhang, “Provisioning QoS-aware and robust applications in internetof things: a network perspective,” IEEE/ACM Trans. Netw., vol. 27, no. 5, pp. 1931–1944,Oct. 2019.[21] L. Zhao, W. Sun, Y. Shi, and J. Liu, “Optimal placement of cloudlets for access delay66minimization in SDN-based Internet of things networks,” IEEE Internet Things J., vol.5, no. 2, pp. 1334–1344, April 2018.[22] P. Lai, Q. He, F. Chen, M. Abdlrazek, J. G. Hosking and Y. Yang , “Cost-effective appuser allocation in an edge computing environment,” IEEE Trans. Cloud Comput., to bepublished.[23] D. T. Nguyen, L. B. Le, and V. K. Bhargava, “Edge computing resource procurement: anonline optimization approach,” Proc. IEEE WF-IoT, pp. 807–812, Singapore, 2018.[24] T. Ouyang, R. Li, X. Chen, Z. Zhou and X. Tang, “Adaptive user-managed service place-ment for mobile edge computing: an online learning approach,” in Proc. IEEE INFOCOM,pp. 1468–1476, Paris, France, 2019.[25] H. Badri, T. Bahreini, D. Grosu, and K. Yang, “Energy-aware application placementin mobile edge computing: a stochastic optimization approach,” IEEE Trans. ParallelDistrib. Syst., vol. 31, no. 4, pp. 909–922, Apr. 2020.[26] L. Li, D. Shi, R. Hou, X. Li, J. Wang, H. Li, and M. Pan, “Data-driven optimization forcooperative edge service provisioning with demand uncertainty,” in IEEE Internet ThingsJ., vol. 8, no. 6, pp. 4317–4328, Mar. 2021.[27] J. Li, W. Liang, and Y. Ma, “Robust service provisioning with service function chainrequirements in mobile edge computing,” IEEE Trans. Netw. Serv. Manag., vol. 18, no.2, pp. 2138–2153, Jun. 2021.[28] Y. Mao, C. You, J. Zhang, K. Huang, and K. B. Letaief, “A survey on mobile edgecomputing: the communication perspective,” IEEE Commun. Surv. Tut., vol. 19, no. 4,pp. 2322–2358, 2017.[29] [Access June 2021] https://aws.amazon.com/solutions/case-studies/netflix-case-study/[30] [Access June 2021] https://aws.amazon.com/ec2/pricing/[31] [Access June 2021] http://gwa.ewi.tudelft.nl/datasets/67[32] A. L. Soyster, “Convex programming with set-inclusive constraints and applications toinexact linear programming,” J. Oper. Res., pp. 1154-1157, 1973.[33] A. Ben-Tal, L. El Ghaoui, and A. Nemirovski, “Robust Optimization,” Princeton, NJ,USA: Princeton Univ. Press, 2009.[34] A. Ben-Tal, A. Goryashko, and E. Guslitzer, “Adjustable robust solutions of uncertainlinear programs,” Math. Program., vol. 99, pp. 351–376, 2004.[35] D. Bertsimas and M. Sim, “The price of robustness,” J. Oper. Res., pp. 35–53, Feb. 2004.[36] D. T. Nguyen, H. T. Nguyen, N. Trieu, and V. K. Bhargava, “Two-stage robust edgeservice placement and sizing under demand uncertainty,” IEEE Internet Things J., to bepublished.[37] B. Zeng and L. Zhao, “Solving two-stage robust optimization problems using a column-and-constraint generation method,” Oper. Res. L., pp. 457–461, vol. 41, no. 5, 2013.[38] D. Bertsimas and G. Vineet, “On the power and limitations of affine policies in two-stageadaptive optimization,” Math. Program., pp 491–531, vol. 134, 2012.[39] D. Kuhn, W. Wiesemann, and A. Georghiou, “Primal and dual linear decision rules instochastic and robust optimization,” Math. Program., vol. 130, pp. 177-–209, 2011.[40] S. Boyd and L. Vandenberghe, “Convex Optimization,” Cambridge, U.K.: CambridgeUniv. Press, 2004.[41] J. Fortuny-Amat and B. McCarl, “A representation and economic interpretation of atwo-level programming problem,” J. Oper. Res. Soc., vol. 32, no. 9, pp. 783–792, Sep.1981.[42] N. Kherraf, S. Sharafeddine, C. Assi, and A. Ghrayeb, “Latency and reliability-awareworkload assignment in IoT networks with mobile edge clouds,” IEEE Trans. Netw. Ser.Manag., vol. 16, no. 4, pp. 1435–1449, Dec. 2019.68[43] M. Karimzadeh-Farshbafan, V. Shah-Mansouri, and D. Niyato, “A dynamic reliability-aware service placement for network function virtualization (NFV),” IEEE J. Sel. AreasCommun., vol. 38, no. 2, pp. 318–333, Feb. 2020.[44] D. Chemodanov, P. Calyam, F. Esposito, R. McGarvey, K. Palaniappan and A. Pescape´,“A near optimal reliable orchestration approach for geo-distributed latency-sensitiveSFCs,” IEEE Trans. Netw. Sci. Eng., vol. 7, no. 4, pp. 2730–2745, Oct.–Dec. 2020.[45] S. Bian, X. Huang, Z. Shao, X. Gao, and Y. Yang, “Service chain composition withresource failures in NFV systems: a game-theoretic perspective,” IEEE Trans. Netw.Serv. Manag., vol. 18, no. 1, pp. 224–239, Mar. 2021.[46] A. Aral and I. Brandic´, “Learning spatio-temporal failure dependencies for resilient edgecomputing services,” IEEE Trans. Parallel Distrib. Syst., vol. 32, no. 7, pp. 1578–1590,Jul. 2021.[47] Y. Qu, D. Lu, H. Dai, H. Tan, S. Tang, F. Wu and C. Dong “Resilient service provisioningfor edge computing,” IEEE Internet Things J., to be published.69Appendix AAppendices for Chapter 2A.1 KKT-based subproblem reformulationThe Lagrangian function of the inner minimization problem in the subproblem is:L(wi,j , qi, si, uj , γ1i,j , γ2i ) = ρ∑iPiqi + β∑i,jdi,jwi,j−∑iγ2i qi −∑i,jγ1i,jwi,j+∑ju1j(∑iwi,j − (1− zj)Cj tˆj)+∑ju2j(∑iwi,j − yˆj)+∑isi(λ¯i + giλ˜i − qi −∑jwi,j)+∑i,jpii,j(wi,j − ai,jCj)70The KKT conditions are:∂L∂wi,j= βρdi,j + uj + pii,j − si = γ1i,j ≥ 0, ∀i, j (A.1a)∂L∂qi= ρPi − si = γ2i ≥ 0, ∀i (A.1b)∑jwi,j + qi ≥ λi, ∀i (A.1c)∑iwi,j ≤ Cj tˆj(1− zj);∑jwi,j ≤ yˆj , ∀j (A.1d)0 ≤ wi,j ≤ ai,jCj , ∀i, j; qi ≥ 0, ∀i (A.1e)γ1i,j , pii,j ≥ 0, ∀i, j; γ2i , si ≥ 0, ∀i; u1j , u2j ≥ 0, ∀j (A.1f)(λi −∑jwi,j − qi)si = 0, ∀i (A.1g)(∑iwi,j − (1− zj)Cj tˆj)u1j = 0, ∀j (A.1h)(∑iwi,j − yˆj)u2j = 0, ∀j (A.1i)(wi,j − ai,jCj)pii,j = 0, ∀i, j (A.1j)wi,jγ1i,j = 0, ∀i, j qiγ2i = 0, ∀i (A.1k)where (A.1a) and (A.1b) are the stationary conditions, (A.1c) - (A.1e) are the primal feasibilityconditions, (A.1f) is dual feasibility condition, and (A.1g) - (A.1k) are the complementaryslackness conditions. We can then re-write the subproblem with complementary constraints:71max(λ,z)∈Ξ,w,qρ∑iPiqi + β∑i,jdi,jwi,j (A.2a)s.t. 0 ≤ ρPidi,j + uj − si ⊥ wi,j , ∀i, j (A.2b)0 ≤ ρPi − si ⊥ qi ≥ 0, ∀i (A.2c)0 ≤ Cj tˆj(1− zj)−∑iwi,j ⊥ u1j ≥ 0, ∀j (A.2d)0 ≤ yˆj −∑iwi,j ⊥ u2j ≥ 0, ∀j (A.2e)0 ≤∑jwi,j + qi − λ¯i − giλ˜i ⊥ si ≥ 0, ∀i (A.2f)0 ≤ ai,jCj − wi,j ⊥ pii,j ≥ 0, ∀i, j (A.2g)∑igi ≤ Γ; gi ∈ [0, 1], ∀i; (A.2h)∑jzj ≤ K; zj ∈ {0, 1}, ∀j, (A.2i)where (A.2i) is the constraint in uncertainty set Ξ. Note that a complimentary constraint0 ≤ x ⊥ γ ≥ 0 implies a set of constraints including (x ≥ 0, γ ≥ 0, xγ = 0). Notice that thereexists an bilinear term between primal variable x and its dual variable γ. Fortunately, thisnon-linear complimentary constraint can be transformed into exact linear constraints by usingFortuny-Amat transformation [41]. Let M be the sufficient large number and v be the binaryvariable. The equivalent transformation of complementary constraint is shown as follows:0 ≤ x ≤ vM (A.3a)0 ≤ γ ≤ (1− v)M (A.3b)By applying this transformation for all complimentary constraints (A.1g) to (A.1k), we canget exact form of problem shown in (2.27).A.2 ADR ReformulationTo transform the ADR model (2.34) into an MILP, we need to reformulate each robust con-straint from (2.34b) to (2.34i) as an equivalent set of linear equations. First, consider constraint72(2.34b). It is easy to see that (2.34b) is equivalent to:φ ≥ maxg,z∑i∈IPi∑e∈IEei (λ¯e + geλ˜e) +∑l∈JF li zl +Gi+ β∑i∈I∑j∈Jdi,j∑e∈IAei,j(λ¯e + geλ˜e) +∑l∈JBli,jzl +Di,j (A.4a)s.t.∑ege ≤ Γ, (µ0) (A.4b)0 ≤ ge ≤ 1, ∀e (η0e) (A.4c)∑jzl ≤ k, (v0) (A.4d)0 ≤ zl ≤ 1, ∀l, (σ0l ) (A.4e)where µ0, η0e , v0, and σ0l are dual variables for constraints from (A.4b) to (A.4e), respectively.Be rearranging the terms in problem (A.4), we can rewrite problem (A.4) as follows:φ ≥∑i∈I∑e∈IPiEei λ¯e +∑i∈IPiGi + β∑i∈I∑j∈J∑e∈Idi,jAei,j λ¯e + β∑i∈I∑j∈Jdi,jDi,j+ maxg,z∑i∈I∑l∈JPiFli zl +∑i∈I∑e∈IPiEei geλ˜fe + β∑i∈I∑j∈J∑l∈Jdi,jBli,jzl+ β∑i∈I∑j∈J∑e∈Idi,jAei,jgeλ˜es.t.∑ege ≤ Γ, (µ0) (A.5a)0 ≤ ge ≤ 1, ∀e (η0e) (A.5b)∑jzl ≤ k, (v0) (A.5c)0 ≤ zl ≤ 1, ∀l, (σ0l ) (A.5d)By LP theory, the dual of the maximization problem on the right hand side of (A.5) isthe following linear minimization problem. Thus, problem (A.5) (i.e., the robust constraint73(2.34b)) is equivalent to the following set of linear equations:φ−∑i∈I∑e∈IPiEei λ¯e −∑i∈IPiGi − β∑i∈I∑j∈J∑e∈Idi,jAei,j λ¯e− β∑i∈I∑j∈Jdi,jDi,j − kv0 − Γµ0 −∑e∈Iη0e −∑l∈Jσ0l ≥ 0 (A.6a)η0e + µ0 ≥ β∑i∈I∑j∈Jdi,jAei,j λ˜e +∑i∈IPiEei λ˜e, ∀e (A.6b)σ0l + v0 ≥ β∑i∈I∑j∈Jdi,jBli,j +∑i∈IPiFli , ∀l (A.6c)η0e , v0, µ0 ≥ 0; σ0l ≥ 0, ∀l. (A.6d)By following similar procedure, we can reformulate individual robust constraints from(2.34d) to (2.34i) into equivalent sets of linear equations. For the sake of brevity, we willpresent the final set of equations for each constraint only. Specifically, (2.34d) is equivalent to:∑i∈I∑e∈IAei,j λ¯e +∑i∈IDi,j − Cj tˆj +∑e∈Iη1e,j + Γµ1j +∑l∈Jσ1l,j + kv1j ≤ 0, ∀j (A.7a)η1e,j + µ1j ≥∑i∈IAei,j λ˜e, ∀e, j (A.7b)σ1l,j + v1j ≥∑i∈IBli,j , ∀l, l 6= j (A.7c)σ1l,j + v1j ≥∑i∈IBli,j + Cj tˆj ; ∀j, l = j (A.7d)η1e,j ≥ 0, ∀e, j; v1j , µ1j ≥ 0, ∀j; σ1l,j ≥ 0,∀l, j. (A.7e)The equivalent reformulation of constraint (2.34e) is:∑i∈I∑e∈IAei,j λ¯e +∑i∈IDi,j − yj +∑e∈Iη1e,j + Γµ1j +∑l∈Jσ1l,j + kv1j ≤ 0, ∀j (A.8a)η2e,j + µ2j ≥∑i∈IAei,j λ˜e, ∀e, j (A.8b)σ2l,j + v2j ≥∑i∈IBli,j , ∀l (A.8c)η2e,j ≥ 0, ∀e, j; v2j , µ2j ≥ 0, ∀j; σ2l,j ≥ 0, ∀l, j. (A.8d)74Similarly, constraint (2.34f) is equivalent to:∑j∈J∑e∈IAei,j λ¯e +∑e∈IEei λ¯e +∑j∈JDi,j +Gi − λ¯i −∑e∈Iη3i,e − Γµ3i −∑l∈Jσ3i,l − kv3i ≥ 0, ∀i(A.9a)η3i,e + µ3i ≥ −∑j∈JAei,j λ˜e − Ei,eλ˜e, ∀i, e (A.9b)η3i,e + µ3i ≥ −∑j∈JAei,j λ˜e − Ei,eλ˜e + λ˜i, ∀i, e = i (A.9c)σ3i,l + v3i ≥ −∑j∈JBli,j − F li , ∀i, l (A.9d)η3i,e ≥ 0, ∀i, e; v3i , µ3i ≥ 0, ∀i; σ3i,l ≥ 0, ∀i, l. (A.9e)Constraint (2.34g) is equivalent to:∑e∈IEei λ¯e +Gi −∑e∈Iη3i,e − Γµ4i −∑l∈Jσ4i,l − kv4i ≥ 0, ∀i (A.10a)− η4i,e − µ4i ≤ Eei λ˜e, ∀i, e (A.10b)− σ4i,l − v4i ≤ F li , ∀i, l (A.10c)η4i,e ≥ 0, ∀i, e; v4i , µ4i ≥ 0, ∀i, j; σ4i,l ≥ 0, ∀i, l. (A.10d)Constraint (2.34h) is equivalent to:∑eAei,j λ¯e +Di,j −∑eη5i,j,e − Γµ5i,j −∑lσ5i,j,l − kv5i,j≥ 0, ∀i, j (A.11a)− η5i,j,e − µ5i,j ≤ Aei,j λ˜e, ∀i, j, e (A.11b)− σ5i,j,l − v5i,j ≤ Bli,j , ∀i, j, l (A.11c)η5i,j,e ≥ 0, ∀i, j, e; v5i,j , µ5i,j ≥ 0, ∀i, j; σ5i,j,l ≥ 0, ∀i, j, l. (A.11d)75Finally, constraint (2.34i) is equivalent to:∑eAei,j λ¯e +Di,j −∑eη6i,j,e − Γµ6i,j −∑lσ6i,j,l − kv6i,j≤ ai,jCj , ∀i, j (A.12a)− η6i,j,e − µ6i,j ≤ Aei,j λ˜e, ∀i, j, e (A.12b)− σ6i,j,l − v6i,j ≤ Bli,j , ∀i, j, l (A.12c)η6i,j,e ≥ 0, ∀i, j, e; v6i,j , µ6i,j ≥ 0, ∀i, j; σ6i,j,l ≥ 0, ∀i, j, l. (A.12d)By replacing the sets of constraints from (A.6) to (A.12) into the ADR model (2.34), weobtain the MILP as shown in (2.35).76
Thesis/Dissertation
eng
Electrical and Computer Engineering
Vancouver : University of British Columbia Library
Attribution-NonCommercial-NoDerivatives 4.0 International
Graduate
Bhargava, Vijay K., 1948-
Edge service placement and workload allocation under uncertainty
Text