Federated Learning (FL) has emerged as a powerful approach for decentralized model training, yet its deployment in large-scale Internet of Things (IoT) environments faces significant challenges. These challenges include fluctuating bandwidth, frequent node failures, and the resource constraints. Such issues are particularly amplified in multilayer Edge-Fog-Cloud infrastructures. Traditional single-layer FL frameworks often fail to address these issues, leading to disrupted training and poor scalability. To tackle these challenges, we propose FTFormer, a novel fault-tolerant, Transformer-based layer offloading framework designed for multilayer federated split learning. FTFormer leverages a Transformer-based policy network to capture the complex interdependencies among Edge, Fog, and Cloud nodes, including bandwidth variability, compute power, and failure probabilities. Combined with an online Proximal Policy Optimization (PPO) algorithm, the framework dynamically adapts offloading decisions in real time, ensuring efficient task allocation under dynamic conditions. Additionally, FTFormer integrates fault-tolerance mechanisms that enable task re-routing and backup deployment to mitigate the impact of node failures and overloads, maintaining smooth training progress. Using a large-scale event-driven simulator capable of modeling thousands of Edge devices and hundreds of Fog/Cloud nodes, we validate FTFormer's performance. Experimental results show that FTFormer significantly improves training speed, fault resilience, and scalability, outperforming state-of-the-art techniques under high-load and failure-prone scenarios. This work highlights FTFormer as a robust solution for deploying resilient FL in real-world IoT systems.

The integration of Network Function Virtualization (NFV) and Mobile Edge Computing (MEC) allows for efficient, advanced network services via Service Function Chains (SFCs). SFCs are sequences of ordered network functions designed to provide specific network services. However, the placement of SFCs is critical, especially for latency-sensitive applications such as telemedicine, due to spatial proximity between service functions, their processing order, and limited edge resources. This paper addresses the multi-SFC placement problem in MEC-NFV networks, aiming to reduce both deploying cost and routing cost. We propose an innovative algorithm based on topological sort, called TD-NFP, to solve this problem. The experimental results show that the proposed TD-NFP approach outperforms other benchmarks.

Videos are projected to account for roughly 80% of global mobile data traffic by 2028. Many camera-equipped mobile devices, such as surveillance drones, require realtime video analytics, encompassing tasks like object detection and action recognition. These devices, restricted by limited resource constraints, need to offload videos to Mobile Edge Computing (MEC) to simultaneously optimize video analytics performance and minimize delay. However, MEC is facing significant challenges in providing efficient video offloading solutions, especially due to uncertainties caused by dynamic device mobility and the associated trade offs in selecting video quality for offloading. Offloading high-quality videos enhances video analytics performance, such as object detection accuracy. Yet, as a mobile device relocates, lower video quality or serving by a different MEC cloudlet may be required (triggering a service migration) to maintain a satisfactory service performance. In this paper, we study the Video Offloading Problem (VOP) in MEC to address these challenges. We propose two uncertainty-aware approaches that model the uncertainties in the environment to solve VOP. Our first approach, focusing on system side, is based on Two-stage Stochastic Program and proposing a unique clustering-based Sample Average Approximation to effectively solve TSP-VOP. The second approach, focusing on device side, employs an online learning algorithm based on a multi-armed bandit to learn and select the optimal offloading solution online. Through extensive experiments, we show that our proposed approaches significantly enhance video offloading decisions, with high video quality and reduced service migration costs under uncertain device mobility, compared to other benchmarks.

The increasing demand for high-volume multimedia services through mobile user equipment (UEs) has imposed a significant burden on mobile networks. To cope with this growth in demand, it is necessary to extend the 5G network's ability to meet quality-of-service (QoS) requirements. The integration of Multi-access Edge Computing (MEC) with 5G technology, 5G-MEC, emerges as a pivotal solution, offering ultra-low latency, ultra-high reliability, and continuous connectivity to support various latency-sensitive applications for UEs. Despite these advancements, the mobility of UEs introduces significant spatio-temporal uncertainties, posing a major challenge on optimizing content delivery routes and directly impacting both latency and service continuity for UEs. Addressing this challenge necessitates suitable approaches for selecting optimal 5G-MEC components, with the goal of minimizing latency and reducing the frequency of handovers, ultimately ensuring a seamless content delivery experience. This paper proposes two learning-based approaches to tackle the problem of 5G-MEC component selection to facilitate QoS-aware content delivery in the absence of complete information about the dynamics of the 5G-MEC environment. First, we design an online sequential decision-making approach, called QCS-MAB, to decide on the content delivery routes in real-time while achieving a bounded performance. We then propose a deep learning approach, called QCS-DNN, to efficiently solve large-scale 5G-MEC component selection problems. We evaluate the effectiveness of our proposed approaches through extensive experiments using a real-world dataset. The results demonstrate that both QCS-MAB and QCS-DNN achieve near-optimal latency and significantly reduced handover times, significantly enhancing the 5G-MEC content delivery experience.

Cloudlets are resource-rich computing infrastructures of edge computing that are located at physical proximity of users to provide one-hop, high-bandwidth wireless access to additional computational resources. They enable computation offloading for user applications, which compensates for the resource limitation of user devices by providing ultra-low latency processing for their applications. Although the computation capability of user devices is dramatically augmented by offloading, spatio-temporal uncertainties due to user mobility and changes in application specifications bring the most challenging obstacles in deciding where to offload to provide minimum latency. In this paper, we focus on these challenges by designing efficient offloading approaches that take into account these uncertainties and dynamics in order to minimize the turnaround time of the applications, which is constituted by offloading latency, migration delay, and execution time. We first formulate this NP-hard problem as an integer programming model to obtain optimal offloading decisions. We tackle its intractability by designing two novel offloading approaches, called S-OAMC and G-OAMC, that fully assign applications to cloudlets by considering their expected future locations and specifications predicted by Matrix Completion, a machine learning method. S-OAMC is a sampling-based approximation dynamic programming approach that enhances scalability and obtains near-optimal solutions. G-OAMC is a fast greedy-based approach for finding low-turnaround time offloading decisions. We conduct extensive experiments to assess the performance of our proposed approaches. The results show that S-OAMC and G-OAMC lead to near-optimal turnaround time in a reasonable time, and they both obtain low migration rates.

Many mobile device applications require low end-to-end latency to edge computing infrastructure when offloading their computation tasks in order to achieve real-time perception and cognition for users. User mobility brings significant challenges in providing low-latency offloading due to the limited coverage area of cloudlets. Virtual machine (VM)/container handoff is a promising solution to seamlessly transfer services from one cloudlet to another to maintain low latency as users move. However, an inefficient path planning for the handoff can result in system congestion and consequently poor quality of service (QoS). The situation can even worsen by selfish users who intentionally lie about their true parameters to achieve better service at the cost of degrading the whole system's performance. To fill this research gap, we propose an Online Service Handoff Mechanism (OSHM) to provide an efficient path dynamically for transferring VM/container from the current serving cloudlet to a nearby cloudlet at the destination of a mobile user. Our proposed path planning algorithm is based on a label correction methodology, leading to polynomial time complexity. OSHM is accompanied by our proposed payment determination function to discourage misreporting of unknown parameters. We discuss the theoretical properties of our proposed mechanism in implementing a system equilibrium and ensuring truthfulness. We also perform a comprehensive assessment through extensive experiments which show the efficiency of OSHM in terms of workload, handoff time, consumed energy, and other metrics compared to several benchmarks. Experimental results show that OSHM outperforms other algorithms, reducing at least 61% in average workload, 33% in average handoff time, and 29% in average energy consumption.

Buildings, producing more carbon footprints than the transportation sector, account for a significant portion of the United States’ total energy consumption. By designing modern automation techniques, smart buildings can significantly reduce energy consumption, protect the environment, and consequently improve quality of life. This article focuses on the automation of elevator scheduling, which is an NP-Hard problem, to reduce energy usage in smart buildings and improve users’ quality of experience. We propose an optimal mathematical model for the elevator scheduling problem using integer programming. We then propose a novel game-theoretic approach that captures interactions within the elevator system to reduce energy consumption and enhance user experience. We propose a request coalition formation game, where nonoverlapping coalitions of user requests are served by elevators to minimize their movements and energy consumption while reducing service time and stops for users. We analyze the performance of our proposed approach using the optimal solution as a benchmark and Nearest Car and Fixed Sectoring algorithms as rivals. The experiments show that our approach is significantly efficient in terms of energy consumption and service time, making it suitable for smart buildings.

Edge computing is a new computing paradigm, which aims at enhancing user experience by bringing computing resources closer to where data is produced by Internet of Things (IoT). Edge services are provided by small data centers located at the edge of the network, called cloudlets. However, IoT users often face strict Quality of Service (QoS) constraints for a proper remote execution of their applications on edge. Each user has specific resource requirements and budget limitations for her IoT application, while each cloudlet offers a limited number and types of resources, each with a specific cost. Therefore, a key challenge is how to efficiently match cloudlets to IoT applications and enable a convenient any-time access to edge computing services considering preferences and incentives of users and cloudlets. In this article, we address this problem by proposing a novel two-sided matching solution for edge services considering QoS requirements in terms of service response time. In addition, we determine dynamic pricing of edge services based on the preferences and incentives of cloudlets, IoT users, and the system. The proposed matching is incentive compatible, individually rational, weakly budget balanced, asymptotically allocative efficient, and computationally efficient. We perform a comprehensive assessment through extensive performance analysis experiments to evaluate our proposed matching and pricing solutions.

Emerging applications with low-latency requirements such as real-time analytics, immersive media applications, and intelligent virtual assistants have rendered Edge Computing as a critical computing infrastructure. Existing studies have explored the cloudlet placement problem in a homogeneous scenario with different goals such as latency minimization, load balancing, energy efficiency, and placement cost minimization. However, placing cloudlets in a highly heterogeneous deployment scenario considering the next-generation 5G networks and IoT applications is still an open challenge. The novel requirements of these applications indicate that there is still a gap in ensuring low-latency service guarantees when deploying cloudlets. Furthermore, deploying cloudlets in a cost-effective manner and ensuring full coverage for all users in edge computing are other critical conflicting issues. In this article, we address these issues by designing a bifactor approximation algorithm to solve the heterogeneous cloudlet placement problem to guarantee a bounded latency and placement cost, while fully mapping user applications to appropriate cloudlets. We first formulate the problem as a multi-objective integer programming model and show that it is a computationally NP-hard problem. We then propose a bifactor approximation algorithm, ACP, to tackle its intractability. We investigate the effectiveness of ACP by performing extensive theoretical analysis and experiments on multiple deployment scenarios based on New York City OpenData. We prove that ACP provides a (2,4)-approximation ratio for the latency and the placement cost. The experimental results show that ACP obtains near-optimal results in a polynomial running time making it suitable for both short-term and long-term cloudlet placement in heterogeneous deployment scenarios.

In this paper, we introduce a model-free online algorithm that is driven by dynamic regret to minimize the network traffic in edge computing in a non-stationary environment that is caused by user mobility and their varying demands for edge services. Our approach is based on Monte Carlo sampling of past experiences that are used to calculate the regret and adjust the exploration and exploration tendencies; moreover, the proposed approach does not assume any mobility patterns for the user, nor does it require any hyperparameter tuning. Preliminary results show that the proposed approach adapts to the ever-changing environmental conditions and converges towards the new optimal service deployment.

Most camera-based mobile devices require ultra low-latency video analytics such as object detection and action recognition. These devices face severe resource constraints, and thus, video offloading to Mobile Edge Computing (MEC) seems a reasonable solution. However, MEC is facing several key challenges-especially due to uncertainties caused by dynamic device mobility-to provide efficient video offloading solutions that enable both maximum performance for video analytics and minimum latency. In this paper, we study the Video Offloading Problem (VOP) in MEC in detail to address these challenges. We formulate VOP as a Two-stage Stochastic Program, called TSP-VOP, to model the uncertainties in the environment. We propose a novel clustering-based Sample Average Approximation to effectively solve TSP- VOP in uncertain dynamic environments, while satisfying the required latency. We perform extensive experiments to validate the effectiveness of our proposed algorithm.

By 2022, videos will account for 82% of global Internet traffic. Many camera-based mobile devices, though with limited resources, require ultra low-latency video analytics such as object detection and action recognition. To facilitate these devices with video offloading solutions, Mobile Edge Computing (MEC) is facing several key challenges due to uncertainties associated with the problem. This paper addresses these challenges by proposing a Two-stage Stochastic Program and a novel clustering-based Sample Average Approximation to effectively solve the video offloading problem in uncertain dynamic environments, while satisfying the required latency. The video offloading quality and other offloading decisions are adaptively made to jointly optimize the video quality and migration cost under the consideration of uncertain device mobility.

Cloud providers can form cloud federations by pooling their resources together to balance their loads, reduce their costs, and manage demand spikes. However, forming cloud federations is a challenging problem, especially when considering the incentives of the cloud providers making their own decisions to participate in cloud federations. In this paper, we model the formation of cloud federations necessary to provide resources to execute Map-heavy/Reduce-heavy programs while considering the trust and reputation among the participating cloud providers. The objective is to form cloud federations with highly reputable cloud providers that achieve maximum profit for their participation. This is an NP-hard bicriteria optimization problem. We introduce a coalitional graph game, called trust-aware cloud federation formation game, to model the cooperation among cloud providers. We design a mechanism for cloud federation formation that enables the cloud providers with high reputation to organize into federations reducing their costs. Our proposed mechanism guarantees the highest profits for the participating cloud providers in the federations, and ensures high reliability of the formed federations in executing the applications. We perform extensive experiments to characterize the properties of the proposed mechanism. The results show that our proposed mechanism produces Pareto optimal and stable cloud federations that not only guarantee that the participating cloud providers have high reputation, but also high individual profits.

Service providers leverage discounted prices of reserved instances offered by cloud providers to amortize their operational costs. They reserve a certain number of instances to cover a significant portion of their computing resource requirements, and further employ on-demand instances to cover remaining requirements not satisfied by the reserved instances. Because of the higher price of on-demand instances, service providers seek to lower their usage to minimize operational costs. In this work, we propose ApproxDNN approach for Machine Learning as a Service to reduce operational costs of service providers by incentivizing approximate results, based on the capabilities of cutting-edge GPUs and a discounted pricing model. When the deadlines of jobs submitted by users are very tight, a service provider might not be able to execute all of them on reserved instances under the default precision. In such cases, Ap- proxDNN leverages the reduced-precision instructions to reduce the execution time of the jobs with slight reduction in their final accuracy, and consequently, to minimize the employment of on- demand instances. To incentivize users to accept the approximate results of reduced-precision instructions, ApproxDNN offers them a discounted price for the service based on a newly designed pricing model. Our proposed pricing model of ApproxDNN guarantees lower or equal cost for service providers compared to the conventional method that solely depends on employment of on-demand instances in case of the reserved instance shortage. We employ real-world traces to conduct an extensive set of experiments and evaluate the performance of our proposed approach. The results show that ApproxDNN reduces the cost of service providers by 18%, while never exceeding the cost of the conventional method and slightly affecting the accuracy by 0.14%.

A key use case of edge computing is computation offloading that augments the capabilities of resource-constrained mobile devices by conserving their energy consumption and reducing latency of their applications. Edge computing resources, called cloudlets, are resource-rich computing infrastructures nearby users that aim at mitigating the overload of mobile devices and providing low-latency services. A main challenge in computation offloading to cloudlets is how to assign mobile applications to cloudlets efficiently such that the assignment captures the mobility inherent of mobile devices and leads to minimum latency during runtime of the applications. We address this problem by proposing a novel offloading approach that considers dynamics of mobile applications including mobility and changing specifications, and fully assigns applications to cloudlets, while minimizing their turnaround time (latency and execution time). We first formulate the problem as an integer programming model to minimize the turnaround time of mobile applications. This problem is an NP-hard problem. To tackle the intractability, we design a computation offloading algorithm, called OAMC, utilizing future specifications of mobile applications to obtain smart mobility-aware offloading decisions based on our prediction models. We conduct several experiments to evaluate the performance of our proposed approach. The results reveal that OAMC leads to near-optimal turnaround time in a reasonable running time.

One of the well-known challenges in Edge Computing is strategic placement of cloudlets. The fundamental goals of this challenge are to minimize the deployment cost of cloudlets and to guarantee minimum latency for users of edge services. However, building cloudlet infrastructure may not be feasible in many situations and areas (e.g., disaster situations, unexpected surge in demand, and remote rural areas). Vehicular edge computing, VEC, introduces mobile cloudlets to augment edge computing capacity, enhance its coverage, and reduce latency significantly. However, efficient cloudlet placement is even more critical in VEC as it is not a long-term decision and needs to be repeated over time. In this paper, we address this challenge by designing a generalized cost-aware cloudlet placement approach that places a set of heterogeneous cloudlets in a region and fully maps user applications to appropriate cloudlets while ensuring their latency requirements. We first formulate the problem as a multi-objective integer programming model in a general deployment scenario. This is a computationally NP-hard problem. To tackle its intractability, we then propose a genetic algorithm-based approach, GACP. We investigate the effectiveness of GACP by performing extensive experiments on multiple deployment scenarios based on New York City OpenData. The results show that GACP obtains close to optimal cost placement in significantly reduced time.

Edge computing is a new paradigm of computing, which aims at enhancing user experience by bringing computing resources closer to where data is produced by Internet of Things (IoT). Cloudlets, additional infrastructure components nearby users, facilitate edge services to decrease latency and network traffic. IoT users require edge services for their applications meeting a strict quality of service (QoS). A key challenge is how to efficiently match cloudlets to IoT applications to enable a convenient any-time access to edge computing services. In this paper, we address this problem by proposing novel two-sided matching solutions for edge services considering QoS requirements in terms of service response time. The matching mechanisms enhance the quality of experience of the users. In addition, we determine dynamic pricing of the edge services based on preferences and incentives of cloudlets, IoT users, and the system. The proposed matchings are Pareto-efficient, incentive compatible, weakly budget balanced, and computationally efficient. We perform a comprehensive assessment through extensive performance analysis experiments to evaluate our proposed matching and pricing solutions.

We consider a competitive environment for reward-based scheduling of periodic tasks, where the execution of each task consists of a mandatory and an optional part. Each task obtains a value if the processor successfully schedules all its mandatory part, and also an additional reward value if the processor successfully schedules a part of its optional execution. Each task is owned by a self-interested agent who has multiple choices for its requests based on its optional part. We model the reward-based scheduling problem by considering such multi-minded agents. However, the agent may try to manipulate the system to obtain an unfair optional allocation. We address this challenge by designing novel truthful mechanisms in which it is always in the agent's best interest to report their true task characteristics. We propose two truthful mechanisms (an exact and approximate) for selecting a feasible subset of agents and an allocation of optional execution that maximizes the total reward obtained by the selected tasks. To address the pseudo-polynomial complexity of the exact mechanism, we show that our proposed approximate mechanism is a polynomial-time approximation scheme (PTAS). Our extensive experiments show that our proposed approximation mechanism is capable of finding near-optimal solutions efficiently while guaranteeing truthfulness.

Cloud providers provision their various resources such as CPUs, memory, and storage in the form of virtual machine (VM) instances which are then allocated to the users. The users are charged based on a pay-as-you-go model, and their payments should be determined by considering both their incentives and the incentives of the cloud providers. Auction markets can capture such incentives, where users name their own prices for their requested VMs. We design an auction-based online mechanism for VM provisioning, allocation, and pricing in clouds that considers several types of resources. Our proposed online mechanism makes no assumptions about future demand of VMs, which is the case in real cloud settings. The proposed online mechanism is invoked as soon as a user places a request or some of the allocated resources are released and become available. The mechanism allocates VM instances to selected users for the period they are requested for, and ensures that the users will continue using their VM instances for the entire requested period. In addition, the mechanism determines the payment the users have to pay for using the allocated resources. We prove that the mechanism is incentive-compatible, that is, it gives incentives to the users to reveal their actual requests. We investigate the performance of our proposed mechanism through extensive experiments.

The amount of computing resources required by current and future data-intensive applications is expected to increase dramatically, creating high demands for cloud resources. The cloud providers' available resources may not be sufficient enough to cope with such demands. Therefore, the cloud providers need to reshape their business structures and seek to improve their dynamic resource scaling capabilities. Federated clouds offer a practical platform for addressing this service management issue. We introduce a cloud federation formation game that considers the cooperation of the cloud providers in offering cloud IaaS services. Based on the proposed federation formation game, we design a cloud federation formation mechanism that enables the cloud providers to dynamically form a cloud federation maximizing their profit. In addition, the proposed mechanism produces a stable cloud federation structure, that is, the participating cloud providers in the federation do not have incentives to break away from the federation. We analyze the performance of the proposed mechanism by performing extensive experiments. The results of the experiments show that the cloud federation obtained by our proposed mechanism is stable, yielding high profit for the participating cloud providers.

We address the problem of physical machine resource management in clouds considering multiple types of physical machines and resources. We formulate this problem in an auction-based setting and design optimal and approximate strategy-proof mechanisms that solve it. Our proposed mechanisms consist of a winner determination algorithm that selects the users, provisions the virtual machines (VMs) to physical machines (PMs), and allocates them to the selected users; and a payment function that determines the amount that each selected user needs to pay to the cloud provider. We prove that our proposed approximate winner determination algorithm satisfies the loser-independent property, making the approximate mechanism robust against strategic users who try to manipulate the system by changing other users' allocations. We show that our proposed mechanisms are strategy-proof, that is, the users do not have incentives to lie about their requested bundles of VM instances and their valuations. In addition, our proposed mechanisms are in alignment with green cloud computing strategies in which physical machines can be powered on or off to save energy. Our theoretical analysis shows that the proposed approximation mechanism has an approximation ratio of 3. We perform extensive experiments in order to investigate the performance of our proposed approximation mechanism compared to that of the optimal mechanism.

Cloud providers provision their heterogeneous resources such as CPUs, memory, and storage in the form of virtual machine (VM) instances which are then allocated to the users. One of the major challenges faced by the cloud providers is to allocate and provision these resources such that their profit is maximized, and the resources are utilized efficiently. Recently, cloud providers have introduced auction-based models which allow users to submit bids for their requested VMs. We address the problem of autonomic VM provisioning and allocation for the auction-based model considering multiple types of resources by designing an approximation mechanism. In addition, the mechanism determines the payment the users have to pay for using the allocated resources. This problem is computationally intractable, and our proposed mechanism is by far the strongest approximation result that can be achieved for this problem. We show that the proposed approximation mechanism is a polynomial-time approximation scheme (PTAS). Furthermore, our proposed mechanism drives the system into an equilibrium in which the users do not have incentives to manipulate the system by untruthfully reporting their VM bundle requests and valuations. We perform extensive experiments using real workload traces in order to investigate the performance of the proposed mechanism.

The majority of large-scale data intensive applications executed by data centers are based on MapReduce or its open-source implementation, Hadoop. Such applications are executed on large clusters requiring large amounts of energy, making the energy costs a considerable fraction of the data center's overall costs. Therefore minimizing the energy consumption when executing each MapReduce job is a critical concern for data centers. In this paper, we propose a framework for improving the energy efficiency of MapReduce applications, while satisfying the service level agreement (SLA). We first model the problem of energy-aware scheduling of a single MapReduce job as an Integer Program. We then propose two heuristic algorithms, called energy-aware MapReduce scheduling algorithms (EMRSA-I and EMRSA-II), that find the assignments of map and reduce tasks to the machine slots in orderto minimize the energy consumed when executing the application. We perform extensive experiments on a Hadoop cluster to determine the energy consumption and execution time for several workloads from the HiBench benchmark suite including TeraSort, PageRank, and K-means clustering, and then use this data in an extensive simulation study to analyze the performance of the proposed algorithms. The results show that EMRSA-I and EMRSA-II are able to find near optimal job schedules consuming approximately 40 percent less energy on average than the schedules obtained by a common practice scheduler that minimizes the makespan.

A major challenging problem for cloud providers is designing efficient mechanisms for virtual machine (VM) provisioning and allocation. Such mechanisms enable the cloud providers to effectively utilize their available resources and obtain higher profits. Recently, cloud providers have introduced auction-based models for VM provisioning and allocation which allow users to submit bids for their requested VMs. We formulate the dynamic VM provisioning and allocation problem for the auction-based model as an integer program considering multiple types of resources. We then design truthful greedy and optimal mechanisms for the problem such that the cloud provider provisions VMs based on the requests of the winning users and determines their payments. We show that the proposed mechanisms are truthful, that is, the users do not have incentives to manipulate the system by lying about their requested bundles of VM instances and their valuations. We perform extensive experiments using real workload traces in order to investigate the performance of the proposed mechanisms. Our proposed mechanisms achieve promising results in terms of revenue for the cloud provider.

Cloud providers provision their various resources such as CPUs, memory, and storage in the form of Virtual Machine (VM) instances which are then allocated to the users. We design online mechanisms for VM provisioning and allocation in clouds that consider several types of available resources. Our proposed online mechanisms make no assumptions about future demand of VMs, which is the case in real cloud settings. The proposed mechanisms are invoked as soon as a user places a request or some of the allocated resources are released and become available. The mechanisms allocate VM instances to selected users for the period they are requested for, and ensure that the users will continue using their VM instances for the entire requested period. In addition, the mechanisms determine the payment the users have to pay for using the allocated resources. We prove that the mechanisms are incentive-compatible, that is, they give incentives to the users to reveal their true valuations for their requested bundles of VM instances. We investigate the performance of our proposed mechanisms through extensive experiments.

The big data trend is generating compute-intensive and data-intensive applications requiring unique services that are different from conventional computing services. Therefore, there is a need to fundamentally address such requirements by developing market mechanisms for managing, trading, and pricing big data computing services. The cloud computing platforms have a great potential to meet the economic requirements of market mechanisms for big data applications due to their technological advances, cost benefit ratios, and easy to use services. We design a two-sided mechanism for trading computing resources for big data applications. Our proposed mechanism is universally strategy-proof, providing incentives for both cloud providers and users to voluntarily reveal their true private information. We perform extensive experiments to evaluate our proposed mechanism.

The ever-growing demand for cloud resources places the resource management at the heart of the design and decision-making processes in cloud computing environments. Cloud providers offer heterogeneous resources such as CPUs, memory, and storage in the form of Virtual Machine (VM)instances. Recently, cloud providers have introduced auction-based models to sell their unutilized resources in an auction market which allow users to submit bids for their requested VMs. In this PhD dissertation, we address the problem of autonomic VM provisioning and allocation for the auction-based model considering multiple types of resources by designing exact and approximation mechanisms. The mechanisms also determine the payment the users have to pay for using the allocated resources. Furthermore, our proposed mechanisms drive the system into an equilibrium in which the users do not have incentives to manipulate the system by untruthfully reporting their VM bundle requests and valuations.

One of the benefits of cloud computing is that a cloud provider can dynamically scale-up its resource capabilities by forming a cloud federation with other cloud providers. Forming cloud federations requires taking the data privacy and security concerns into account, which is critical in satisfying the Service Level Agreements (SLAs). The nature of privacy and security challenges in clouds requires that cloud providers design data protection mechanisms that work together with their resource management systems. In this paper, we consider the privacy requirements when outsourcing data and computation within a federation of clouds, and propose a framework for minimizing the cost of outsourcing while considering two key data protection restrictions, the trust and disclosure restrictions. We model these restrictions as conflict graphs, and formulate the problem as an integer program. In the absence of computationally tractable optimal algorithms for solving this problem, we design a fast heuristic algorithm. We analyze the performance of our proposed algorithm through extensive experiments.

Executing large-scale application programs in grids requires resources from several grid service providers (GSPs). These providers form virtual organizations (VOs) by pooling their resources together to provide the required capabilities to execute the application. We model the VO formation in grids using concepts from the coalitional game theory and design a mechanism for VO formation. The mechanism enables the GSPs to organize into VOs reducing the cost of execution and guaranteeing maximum profit for the GSPs. Furthermore, the mechanism guarantees that the VOs are stable, that is, the GSPs do not have incentives to break away from the current VO and join some other VO. We perform extensive simulation experiments using real-workload traces to characterize the properties of the proposed mechanism. The results show that the mechanism produces VOs that are stable yielding high revenue for the participating GSPs.

Abstract—Computing Nash equilibria is a very important problem in strategic analysis of markets, conflicts and resource allocation. Unfortunately, computing these equilibria even for moderately sized games is computationally expensive. To obtain faster execution times it is essential to exploit the available parallelism offered by the currently available massively parallel architectures. To address this issue, we design a GPU-based parallel support enumeration algorithm for computing Nash equilibria in bimatrix games. The algorithm is based on a new parallelization method which achieves high degrees of parallelism suitable for massively parallel GPU architectures. We perform extensive experiments to characterize the performance of the proposed algorithm. The algorithm achieves significant speedups relative to the OpenMP-based parallel implementation of the support enumeration method running on conventional multicore machines. I.

Designing efficient mechanisms for Virtual Machine (VM) provisioning and allocation is a major challenging problem that needs to be solved by cloud providers. We formulate the VM provisioning and allocation problem in clouds as an integer program and design truthful greedy mechanisms that solve it. We show that the proposed mechanisms are truthful, that is, the users do not have incentives to lie about their requested bundles of VM instances and their valuations. We perform extensive experiments in order to investigate the performance of the proposed mechanisms.

In order to execute large scale applications programs in grids, several Grid Service Providers (GSPs) pool their resources together by forming Virtual Organizations (VOs). Forming such VOs is a challenging problem especially when the trust relationships among GSPs have to be considered. In this paper, we model the formation of VOs in grids by considering the trust and reputation of the participating GSPs. We design a mechanism for VO formation that enables the GSPs with high reputation to organize into a VO reducing the cost of execution and guaranteeing the maximum profit for the participating GSPs. Furthermore, the mechanism guarantees that the formed VO is stable, that is, the GSPs that are part of the VO do not have incentives to break away from it. We perform extensive simulation experiments using real workload traces to characterize the properties of the proposed mechanism. The results show that the mechanism produces stable VOs composed of GSPs with high reputation that obtain high individual profits.

Computing Nash equilibria is a very important problem in strategic analysis of markets, conflicts and resource allocation. Unfortunately, computing these equilibria even for moderately sized games is computationally expensive. To obtain faster execution times it is essential to exploit the available parallelism offered by the currently available massively parallel architectures. To address this issue, we design a GPU-based parallel support enumeration algorithm for computing Nash equilibria in bimatrix games. The algorithm is based on a new parallelization method which achieves high degrees of parallelism suitable for massively parallel GPU architectures. We perform extensive experiments to characterize the performance of the proposed algorithm. The algorithm achieves significant speedups relative to the OpenMP-based parallel implementation of the support enumeration method running on conventional multicore machines.

We model the Virtual Organization (VO) formation problem in grids using concepts from coalitional game theory and design a distributed mechanism for solving it. The proposed distributed mechanism enables the formation of VOs guaranteeing the maximum profit for their participating Grid Service Providers (GSPs). We show that the proposed mechanism produces stable VOs, that is, the GSPs do not have incentives to break away from the current VO and join some other VO. We perform extensive simulation experiments using real workload traces to characterize the properties of the proposed distributed mechanism. The results show that the proposed distributed mechanism not only produces VOs that are stable yielding high revenue for the participating GSPs, but also decides the structure of the VOs in a reasonable amount of time.

Executing large scale application programs in grids requires resources from several Grid Service Providers (GSPs). These providers form Virtual Organizations (VOs) by pooling their resources together to provide the required capabilities to execute the application. We model the VO formation in grids using concepts from coalitional game theory and design a mechanism for VO formation. The mechanism enables the GSPs to organize into VOs reducing the cost of execution and guaranteeing maximum profit for the GSPs. Furthermore, the mechanism guarantees that the VOs are stable, that is, the GSPs do not have incentives to break away from the current VO and join some other VO. We perform extensive simulations to characterize the properties of the proposed mechanism. The results show that the mechanism produces VOs that are stable yielding high revenue for the participating GSPs.