Publications of year 2018 |
Thesis |
Infrastructure-as-a-Service (IaaS) clouds such as Amazon EC2 offer various types of virtual machines (VMs) through pay-per-use pricing. Elastic resource allocation allows us to allocate and release VMs as computing demand changes while satisfying Quality-of-Service (QoS) requirements. In this thesis, we explore QoS-aware elastic resource allocation for three different data processing models: batch, micro-batch, and streaming. First, we present two frameworks for elastic batch data processing. The first elastic batch data processing framework supports autonomous VM scaling using application-level migration. It does not require any prior knowledge about the target application, but dynamically reconfigures the application to keep the CPU utilization within a certain range. The second framework uses Workload-tailored Elastic Compute Units as a measure of computing resources analogous to Amazon EC2’s ECUs. Given a deadline, our framework finds the cost-optimal resource configuration of heterogeneous VMs to satisfy the required throughput. Next, we propose an elastic micro-batch data processing framework for continuous air traffic optimization. Air traffic optimization is commonly formulated as an integer linear programming (ILP) problem. For continuous optimization, we periodically solve ILP problems with regular intervals, where each problem is a micro-batch data processing job. Since the fluctuating number of flights creates dynamically changing computational demand, our framework predicts future workload and proactively schedules VMs to solve the ILP problems in a timely manner. Finally, we propose a framework for sustainable elastic stream processing based on the concept of Maximum Sustainable Throughput (MST). It is the maximum processing throughput a streaming application can process indefinitely for a number of VMs. Stream processing is sustainable if the system’s MST is always greater than the input data rates of incoming workload. Using MST and future workload prediction models, our framework proactively schedules VMs to keep the stream processing sustainable. It explicitly incorporates uncertainties in both MST and workload prediction models, and estimates the number of VMs to satisfy a certain probability criteria. Our studies show that QoS-aware elastic data processing is effective for these processing models in both performance scalability and cost savings. For batch processing, elastic resource scheduling helps achieve the target QoS metrics such as CPU utilization and job completion time. For both micro-batch and stream processing with fluctuating workloads, QoS-aware elastic scheduling saves up to 49% cost compared to a static scheduling that covers the peak workload to achieve a similar level of throughput QoS satisfaction. These results show potential for future fully automated cloud computing resource management systems that efficiently enable truly elastic and scalable general-purpose workload. |
@PhdThesis{imai-phd-2018, author = {Shigeru Imai}, title = {Elastic Cloud Computing for QoS-Aware Data Processing}, school = {Rensselaer Polytechnic Institute}, year = 2018, keywords = {distributed computing, cloud computing, cyber physical systems, data streaming}, pdf = {http://wcl.cs.rpi.edu/theses/imai-phd.pdf}, abstract = {Infrastructure-as-a-Service (IaaS) clouds such as Amazon EC2 offer various types of virtual machines (VMs) through pay-per-use pricing. Elastic resource allocation allows us to allocate and release VMs as computing demand changes while satisfying Quality-of-Service (QoS) requirements. In this thesis, we explore QoS-aware elastic resource allocation for three different data processing models: batch, micro-batch, and streaming. First, we present two frameworks for elastic batch data processing. The first elastic batch data processing framework supports autonomous VM scaling using application-level migration. It does not require any prior knowledge about the target application, but dynamically reconfigures the application to keep the CPU utilization within a certain range. The second framework uses Workload-tailored Elastic Compute Units as a measure of computing resources analogous to Amazon EC2’s ECUs. Given a deadline, our framework finds the cost-optimal resource configuration of heterogeneous VMs to satisfy the required throughput. Next, we propose an elastic micro-batch data processing framework for continuous air traffic optimization. Air traffic optimization is commonly formulated as an integer linear programming (ILP) problem. For continuous optimization, we periodically solve ILP problems with regular intervals, where each problem is a micro-batch data processing job. Since the fluctuating number of flights creates dynamically changing computational demand, our framework predicts future workload and proactively schedules VMs to solve the ILP problems in a timely manner. Finally, we propose a framework for sustainable elastic stream processing based on the concept of Maximum Sustainable Throughput (MST). It is the maximum processing throughput a streaming application can process indefinitely for a number of VMs. Stream processing is sustainable if the system’s MST is always greater than the input data rates of incoming workload. Using MST and future workload prediction models, our framework proactively schedules VMs to keep the stream processing sustainable. It explicitly incorporates uncertainties in both MST and workload prediction models, and estimates the number of VMs to satisfy a certain probability criteria. Our studies show that QoS-aware elastic data processing is effective for these processing models in both performance scalability and cost savings. For batch processing, elastic resource scheduling helps achieve the target QoS metrics such as CPU utilization and job completion time. For both micro-batch and stream processing with fluctuating workloads, QoS-aware elastic scheduling saves up to 49% cost compared to a static scheduling that covers the peak workload to achieve a similar level of throughput QoS satisfaction. These results show potential for future fully automated cloud computing resource management systems that efficiently enable truly elastic and scalable general-purpose workload.} }
Articles in journal, book chapters |
The Cloud computing paradigm has revolutionised the computer science horizon during the past decade and has enabled the emergence of computing as the fifth utility. It has captured significant attention of academia, industries, and government bodies. Now, it has emerged as the backbone of modern economy by offering subscription-based services anytime, anywhere following a pay-as-you-go model. This has instigated (1) shorter establishment times for start-ups, (2) creation of scalable global enterprise applications, (3) better cost-to-value associativity for scientific and high-performance computing applications, and (4) different invocation/execution models for pervasive and ubiquitous applications. The recent technological developments and paradigms such as serverless computing, software-defined networking, Internet of Things, and processing at network edge are creating new opportunities for Cloud computing. However, they are also posing several new challenges and creating the need for new approaches and research strategies, as well as the re-evaluation of the models that were developed to address issues such as scalability, elasticity, reliability, security, sustainability, and application models. The proposed manifesto addresses them by identifying the major open challenges in Cloud computing, emerging trends, and impact areas. It then offers research directions for the next decade, thus helping in the realisation of Future Generation Cloud Computing. |
@Article{buyya-varela-acm2018, author = {Rajkumar Buyya and Satish Narayana Srirama and Giuliano Casale and Rodrigo Calheiros and Yogesh Simmhan and Blesson Varghese and Erol Gelenbe and Bahman Javadi and Luis Miguel Vaquero and Marco A. S. Netto and Adel Nadjaran Toosi and Maria Alejandra Rodriguez and Ignacio M. Llorente and Sabrina De Capitani di Vimercati and Pierangela Samarati and Dejan Milojicic and Carlos Varela and Rami Bahsoon and Marcos Dias de Assuncao and Omer Rana and Wanlei Zhou and Hai Jin and Wolfgang Gentzsch and Albert Zomaya and Haiying Shen}, title = {A Manifesto for Future Generation Cloud Computing: Research Directions for the Next Decade}, year = {2018}, month = {November}, pages = {1 -- 38}, volume = { 51 }, address = {New York, USA}, publisher = {ACM Press}, journal = { ACM Computing Surveys}, url = {http://www.buyya.com/papers/CloudManifesto.pdf}, keywords = {distributed computing, concurrent programming}, abstract = {The Cloud computing paradigm has revolutionised the computer science horizon during the past decade and has enabled the emergence of computing as the fifth utility. It has captured significant attention of academia, industries, and government bodies. Now, it has emerged as the backbone of modern economy by offering subscription-based services anytime, anywhere following a pay-as-you-go model. This has instigated (1) shorter establishment times for start-ups, (2) creation of scalable global enterprise applications, (3) better cost-to-value associativity for scientific and high-performance computing applications, and (4) different invocation/execution models for pervasive and ubiquitous applications. The recent technological developments and paradigms such as serverless computing, software-defined networking, Internet of Things, and processing at network edge are creating new opportunities for Cloud computing. However, they are also posing several new challenges and creating the need for new approaches and research strategies, as well as the re-evaluation of the models that were developed to address issues such as scalability, elasticity, reliability, security, sustainability, and application models. The proposed manifesto addresses them by identifying the major open challenges in Cloud computing, emerging trends, and impact areas. It then offers research directions for the next decade, thus helping in the realisation of Future Generation Cloud Computing.} }
Conference articles |
Stream processing systems deployed on the cloud need to be elastic to effectively accommodate workload variations over time. Performance models can predict maximum sustainable throughput (MST) as a function of the number of VMs allocated. We present a scheduling framework that incorporates three statistical techniques to improve Quality of Service (QoS) of cloud stream processing systems: (i) uncertainty quantification to consider variance in the MST model; (ii) online learning to update MST model as new performance metrics are gathered; and (iii) workload models to predict input data stream rates assuming regular patterns occur over time. Our framework can be parameterized by a QoS satisfaction target that statistically finds the best performance/cost tradeoff. Our results illustrate that each of the three techniques alone significantly improves QoS, from 52% to 73-81% QoS satisfaction rates on average for eight benchmark applications. Furthermore, applying all three techniques allows us to reach 98.62% QoS satisfaction rate with a cost less than twice the cost of the optimal (in hindsight) VM allocations, and half of the cost of allocating VMs for the peak demand in the workload. |
@InProceedings{ imai-patterson-varela-ccgrid-2018, author = {Shigeru Imai and Stacy Patterson and Carlos A. Varela}, title = {Uncertainty-Aware Elastic Virtual Machine Scheduling for Stream Processing Systems}, booktitle = {18th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing (CCGrid 2018)}, year = 2018, address = {Washington, DC}, month = {May}, pdf = {http://wcl.cs.rpi.edu/papers/ccgrid2018.pdf}, keywords = {distributed computing, cloud computing, stream processing}, abstract = {Stream processing systems deployed on the cloud need to be elastic to effectively accommodate workload variations over time. Performance models can predict maximum sustainable throughput (MST) as a function of the number of VMs allocated. We present a scheduling framework that incorporates three statistical techniques to improve Quality of Service (QoS) of cloud stream processing systems: (i) uncertainty quantification to consider variance in the MST model; (ii) online learning to update MST model as new performance metrics are gathered; and (iii) workload models to predict input data stream rates assuming regular patterns occur over time. Our framework can be parameterized by a QoS satisfaction target that statistically finds the best performance/cost tradeoff. Our results illustrate that each of the three techniques alone significantly improves QoS, from 52% to 73-81% QoS satisfaction rates on average for eight benchmark applications. Furthermore, applying all three techniques allows us to reach 98.62% QoS satisfaction rate with a cost less than twice the cost of the optimal (in hindsight) VM allocations, and half of the cost of allocating VMs for the peak demand in the workload.} }
We investigate MapReduce-based data aggregation for Internet-of-Things data in a multi-tier, geo-distributed datacenter architecture. Specifically, we consider 1) end-to-end hierarchical data aggregation and 2) query response for aggregated data requests made by geo-distributed clients. We first develop a realistic performance model based on previous empirical studies. We then study application performance for various deployment architectures, ranging from a purely cloud-based approach to a geo-distributed architecture that combines cloud, fog, and edge resources. From simulations created based on U.S. Census data, we characterize the trade-off between end-to-end data aggregation time and query response time. Our experiments show that for data aggregation, a purely-cloud based deployment is 53% faster than a deployment with edge resources; however, for query response, the edge approach is 46% faster due to the edge resource proximity to query clients. |
@InProceedings{imai-varela-patterson-m2fc-2018, author = {Shigeru Imai and Carlos A. Varela and Stacy Patterson}, title = {A Performance Study of Geo-Distributed IoT Data Aggregation for Fog Computing}, booktitle = {1st managed Fog-to-Cloud (mF2C) Workshop}, year = 2018, address = {Zurich, Switzerland}, month = {Dec}, pdf = {http://wcl.cs.rpi.edu/papers/mf2c2018.pdf}, keywords = {distributed computing, cloud computing}, abstract = {We investigate MapReduce-based data aggregation for Internet-of-Things data in a multi-tier, geo-distributed datacenter architecture. Specifically, we consider 1) end-to-end hierarchical data aggregation and 2) query response for aggregated data requests made by geo-distributed clients. We first develop a realistic performance model based on previous empirical studies. We then study application performance for various deployment architectures, ranging from a purely cloud-based approach to a geo-distributed architecture that combines cloud, fog, and edge resources. From simulations created based on U.S. Census data, we characterize the trade-off between end-to-end data aggregation time and query response time. Our experiments show that for data aggregation, a purely-cloud based deployment is 53% faster than a deployment with edge resources; however, for query response, the edge approach is 46% faster due to the edge resource proximity to query clients.} }
Loss of thrust (LOT) emergencies create the need for quickly providing pilots with valid trajectories for safely landing the aircraft. It is easy to pre-compute total lost of thrust trajectories for every possible initial point in a 3D flight plan, but it is impossible to predict variables like the availability of partial power, wing surface damage, and wind aloft in advance. Availability of partial power can affect the glide ratio of an aircraft while the presence of wind can significantly affect the trajectory of a gliding aircraft with respect to the ground, e.g. - a tailwind or a headwind can aid or hinder straight line glide by increasing or decreasing the ground speed. Wind can also change the shape of turns from circular to trochoidal, moving an aircraft away from its intended position. In this paper, we present a robust trajectory generation system that can take these dynamic factors into consideration. Our approach outputs valid trajectories to a target runway in the presence of constant, horizontal wind, by using purely geometric criteria for computing flyable trajectories. We model the effect of wind on different components of a possible trajectory by taking into account the observed glide ratio of the aircraft (computed from actual flight performance data) and the horizontal wind vector. We also take into account the effect of wind on ground-speed, the effective glide ratio with respect to the ground, and the shape of turns to calculate trajectories to a virtual point in 3D space which can lead an aircraft to an actual target runway. We introduce an analytical approach for calculating the virtual point for trajectories with left-straight-left or right-straight-right Dubins path segments and a heuristic iterative approach for other cases. Our approach generates trajectories that can lead an aircraft from an initial configuration (latitude, longitude, altitude, heading) to a target configuration in the presence of a constant horizontal wind. In our experiments, the computation time for trajectories ranged from 40 milliseconds to 60 milliseconds. |
@InProceedings{paul-dasc-2018, author = {Saswata Paul and Frederick Hole and Alexandra Zytek and Carlos A. Varela }, title = {Wind-Aware Trajectory Planning For Fixed-Wing Aircraft in Loss of Thrust Emergencies}, booktitle = {The 37th AIAA/IEEE Digital Avionics Systems Conference (DASC 2018)}, year = {2018}, address = {London, England}, month = {September}, pages = {558--567}, url = {http://wcl.cs.rpi.edu/papers/DASC_18.pdf}, keywords = {dddas, data streaming, cyber physical systems, trajectory generation}, abstract = {Loss of thrust (LOT) emergencies create the need for quickly providing pilots with valid trajectories for safely landing the aircraft. It is easy to pre-compute total lost of thrust trajectories for every possible initial point in a 3D flight plan, but it is impossible to predict variables like the availability of partial power, wing surface damage, and wind aloft in advance. Availability of partial power can affect the glide ratio of an aircraft while the presence of wind can significantly affect the trajectory of a gliding aircraft with respect to the ground, e.g. - a tailwind or a headwind can aid or hinder straight line glide by increasing or decreasing the ground speed. Wind can also change the shape of turns from circular to trochoidal, moving an aircraft away from its intended position. In this paper, we present a robust trajectory generation system that can take these dynamic factors into consideration. Our approach outputs valid trajectories to a target runway in the presence of constant, horizontal wind, by using purely geometric criteria for computing flyable trajectories. We model the effect of wind on different components of a possible trajectory by taking into account the observed glide ratio of the aircraft (computed from actual flight performance data) and the horizontal wind vector. We also take into account the effect of wind on ground-speed, the effective glide ratio with respect to the ground, and the shape of turns to calculate trajectories to a virtual point in 3D space which can lead an aircraft to an actual target runway. We introduce an analytical approach for calculating the virtual point for trajectories with left-straight-left or right-straight-right Dubins path segments and a heuristic iterative approach for other cases. Our approach generates trajectories that can lead an aircraft from an initial configuration (latitude, longitude, altitude, heading) to a target configuration in the presence of a constant horizontal wind. In our experiments, the computation time for trajectories ranged from 40 milliseconds to 60 milliseconds.} }
Miscellaneous |
Loss of thrust emergencies, e.g. – induced by bird strikes or fuel exhaustion – give rise to the need for expeditiously generating feasible trajectories to nearby runways, in order to guide pilots. It is possible to pre-compute total loss of thrust trajectories from every point in a 3D flight plan, but dynamic factors which affect the feasibility of a trajectory, like partial power, wind conditions, and aircraft surface damage, cannot be predicted beforehand. We present a dynamic data-driven avionics software approach for emergency aircraft trajectory generation which can account for these factors. Our approach updates a damaged aircraft performance model during flight which is used for generating valid trajectories to a safe landing site. This model is parameterized on a baseline glide ratio (g0) for a clean aircraft configuration, assuming best gliding airspeed on straight flight. The model predicts purely geometric criteria for flight trajectory generation, namely, glide ratio and radius of turn for different bank angles and drag configurations. Our model can dynamically infer the most accurate baseline glide ratio of an aircraft from real-time aircraft sensor data. We further introduce a trajectory utility function to rank trajectories for safety, in particular, to prevent steep turns close to the ground and to remain as close to the airport or landing zone as possible. Wind can significantly affect a feasible gliding trajectory with respect to the ground by changing the shape of turns from circular to trochoidal, and by increasing or decreasing the effective ground speed. Thus, in the presence of wind, otherwise feasible trajectories may become infeasible. Therefore, we present an additional wind model that takes into account the observed baseline glide ratio of an aircraft and the horizontal wind vector (−→w ). Our dynamic data-driven system uses this wind model to generate wind-aware trajectories that are feasible in the presence of a steady, horizontal wind. As a use case, we consider the Hudson River ditching of US Airways 1549 in January 2009, using a flight simulator to evaluate our trajectories and to get sensor data (airspeed, GPS location, and barometric altitude). In this example, baseline glide ratios of 17.25:1 and 19:1 enabled us to generate trajectories up to 28 seconds and 36 seconds after the birds strike respectively. We were also able to generate a feasible wind-assisted trajectory when trajectories were not possible in the absence of wind. In our experiments, the computation time for a single trajectory ranged from 40 milliseconds to 60 milliseconds. |
@MastersThesis{paul-msthesis-2018, author = {Saswata Paul}, title = {Emergency Trajectory Generation for Fixed-Wing Aircraft}, school = {Rensselaer Polytechnic Institute}, year = 2018, month = {December}, pdf = {http://wcl.cs.rpi.edu/theses/paul_ms.pdf}, keywords = {dddas, data streaming, cyber physical systems, trajectory generation}, abstract = {Loss of thrust emergencies, e.g. – induced by bird strikes or fuel exhaustion – give rise to the need for expeditiously generating feasible trajectories to nearby runways, in order to guide pilots. It is possible to pre-compute total loss of thrust trajectories from every point in a 3D flight plan, but dynamic factors which affect the feasibility of a trajectory, like partial power, wind conditions, and aircraft surface damage, cannot be predicted beforehand. We present a dynamic data-driven avionics software approach for emergency aircraft trajectory generation which can account for these factors. Our approach updates a damaged aircraft performance model during flight which is used for generating valid trajectories to a safe landing site. This model is parameterized on a baseline glide ratio (g0) for a clean aircraft configuration, assuming best gliding airspeed on straight flight. The model predicts purely geometric criteria for flight trajectory generation, namely, glide ratio and radius of turn for different bank angles and drag configurations. Our model can dynamically infer the most accurate baseline glide ratio of an aircraft from real-time aircraft sensor data. We further introduce a trajectory utility function to rank trajectories for safety, in particular, to prevent steep turns close to the ground and to remain as close to the airport or landing zone as possible. Wind can significantly affect a feasible gliding trajectory with respect to the ground by changing the shape of turns from circular to trochoidal, and by increasing or decreasing the effective ground speed. Thus, in the presence of wind, otherwise feasible trajectories may become infeasible. Therefore, we present an additional wind model that takes into account the observed baseline glide ratio of an aircraft and the horizontal wind vector (−→w ). Our dynamic data-driven system uses this wind model to generate wind-aware trajectories that are feasible in the presence of a steady, horizontal wind. As a use case, we consider the Hudson River ditching of US Airways 1549 in January 2009, using a flight simulator to evaluate our trajectories and to get sensor data (airspeed, GPS location, and barometric altitude). In this example, baseline glide ratios of 17.25:1 and 19:1 enabled us to generate trajectories up to 28 seconds and 36 seconds after the birds strike respectively. We were also able to generate a feasible wind-assisted trajectory when trajectories were not possible in the absence of wind. In our experiments, the computation time for a single trajectory ranged from 40 milliseconds to 60 milliseconds.} }
This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All person copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
Les documents contenus dans ces répertoires sont rendus disponibles par les auteurs qui y ont contribué en vue d'assurer la diffusion à temps de travaux savants et techniques sur une base non-commerciale. Les droits de copie et autres droits sont gardés par les auteurs et par les détenteurs du copyright, en dépit du fait qu'ils présentent ici leurs travaux sous forme électronique. Les personnes copiant ces informations doivent adhérer aux termes et contraintes couverts par le copyright de chaque auteur. Ces travaux ne peuvent pas être rendus disponibles ailleurs sans la permission explicite du détenteur du copyright.
This document was translated from BibTEX by bibtex2html