Lecture Notes in Computer Science Commenced Publication in 1973 Founding and Former Series Editors: Gerhard Goos, Juris Hartmanis, and Jan van Leeuwen
Editorial Board David Hutchison Lancaster University, UK Takeo Kanade Carnegie Mellon University, Pittsburgh, PA, USA Josef Kittler University of Surrey, Guildford, UK Jon M. Kleinberg Cornell University, Ithaca, NY, USA Alfred Kobsa University of California, Irvine, CA, USA Friedemann Mattern ETH Zurich, Switzerland John C. Mitchell Stanford University, CA, USA Moni Naor Weizmann Institute of Science, Rehovot, Israel Oscar Nierstrasz University of Bern, Switzerland C. Pandu Rangan Indian Institute of Technology, Madras, India Bernhard Steffen TU Dortmund University, Germany Madhu Sudan Microsoft Research, Cambridge, MA, USA Demetri Terzopoulos University of California, Los Angeles, CA, USA Doug Tygar University of California, Berkeley, CA, USA Gerhard Weikum Max Planck Institute for Informatics, Saarbruecken, Germany
6868
Dieter Kranzlmüller A Min Toja (Eds.)
Information and Communication on Technology for the Fight against Global Warming First International Conference, ICT-GLOW 2011 Toulouse, France, August 30-31, 2011 Proceedings
13
Volume Editors Dieter Kranzlmüller Ludwig-Maximilians-Universität München Institut für Informatik Oettingenstrasse 67, 80538 München, Germany E-mail:
[email protected] A Min Toja Vienna University of Technology Institute of Software Technology Favoritenstraße 9-11/188, 1040 Wien, Austria E-mail:
[email protected]
ISSN 0302-9743 e-ISSN 1611-3349 ISBN 978-3-642-23446-0 e-ISBN 978-3-642-23447-7 DOI 10.1007/978-3-642-23447-7 Springer Heidelberg Dordrecht London New York Library of Congress Control Number: 2011934464 CR Subject Classification (1998): D, J.2, J.1, K.6 LNCS Sublibrary: SL 1 – Theoretical Computer Science and General Issues
© Springer-Verlag Berlin Heidelberg 2011 This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, re-use of illustrations, recitation, broadcasting, reproduction on microfilms or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965, in its current version, and permission for use must always be obtained from Springer. Violations are liable to prosecution under the German Copyright Law. The use of general descriptive names, registered names, trademarks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use. Typesetting: Camera-ready by author, data conversion by Scientific Publishing Services, Chennai, India Printed on acid-free paper Springer is part of Springer Science+Business Media (www.springer.com)
Preface
Reduction of CO2 -emissions is a topic of outmost importance for society and our planet. Today, the information and communication technology (ICT) sector is already a relevant contributor to CO2 emissions and global warming due to its tremendous presence in our everyday life. At the same time, and more importantly it is a key technology for the fight against global warming in all other sectors. This twofold situation was addressed during ICT-GLOW 2011: On the one hand, issues on the potential of ICT as enabler for the reduction of CO2 -emissions pertinent to industry, regions, organizations and society were considered. On the other hand, issues on the urgent need of hardware and software systems which are designed and operated in an energy-aware way and which steadily monitor and optimize their energy consumption was another focus of the conference. The First International Conference on ICT as Key Technology for the Fight Against Global Warming (ICT-GLOW 2011) aimed at providing an interdisciplinary scientific forum for in-depth-discussions on the reduction of the carbon footprint in the different sectors including ICT systems themselves. Emphasis within the ICT sector is laid on holistic and far-reaching approaches for green and eco-friendly ICT systems. The conference brought together researchers and practitioners from multiple disciplines ranging from green maturity models in organizations to system level design and optimization. The papers presented at this conference were selected after extensive reviews by the Program Committee and associated reviewers. We would like to thank all PC members and the reviewers for their valuable advice, and the authors for their contributions to ICT-GLOW 2011. Special thanks go to Gabriela Wagner for managing the submission and paper production process, and to Vitalian Danciu for handling the reviewing process and drafting the conference program. Dieter Kranzlm¨ uller A. Min Tjoa
Organization
Program Chairs Dieter Kranzlm¨ uller A. Min Tjoa
LMU and LRZ M¨ unchen, Germany Vienna University of Technology, Austria
Program Committee Amir Abtahi Gul A. Agha Ishfaq Ahmad Lachlan Andrew
Massachusetts Institute of Technology, USA University of Illinois, USA The University of Texas Arlington, USA Swinburne University of Technology-Melbourne, Australia Cosimo Anglano Universit` a del Piemonte Orientale-Alessandra, Italy Rami Bahsoon University of Birmingham, UK Luciano Bertini Universidade Federal Fluminense, Brazil Riccardo Bettati Texas A&M University, USA Davide Careglio Universitat Polit`ecnica de Catalunya, Spain Jian-Jia Chen Karlsruhe Institute of Technology, Germany Jinjun Chen Swinburne University of Technology-Melbourne, Australia Ayse Kivilcim Coskun Boston University, USA Thiery Coupaye Orange Labs, France Georges Da Costa IRIT Toulouse, France Marco Di Girolamo Hewlett-Packard Company, Italy Dominique Dudkowski NEC Europe, Germany Carla Schlatter Ellis Duke University, USA Paulo Ferrao MIT Portugal, Portugal Karl Fuerlinger LMU Munich, Germany Erol Gelenbe Imperial College London, UK Afitya K. Ghose University of Wollongong, Australia Keishiro Hara Osaka University, Japan Helmut Hlavacs University of Vienna, Austria Chun-Hsi (Vincent) Huang University of Connecticut, USA Herbert Huber Leibniz Supercomputing Centre (LRZ), Garching, Germany Karin Anna Hummmel University of Vienna, Austria Farook Khadeer Hussain Curtin University, Australia Omar Hussain Curtin University, Australia Vipul Jain Indian Institute of Mechanical Engineering, India Wolfgang Kabelka Bundesrechenzentrum GmbH, Austria
VIII
Organization
Vincent Keller Samee U. Khan Harald Kosch Thomas Ledoux Laurent Lef`evre Hector G. Lopez-Ruiz Yung-Hsiang Lu Thomas Ludwig Jaime Lloret Mauri Michele Mazzucco Jean-Marc Menaud Arthur Mickoleit Hiroyuki Morikawa Daniel Moss´e Binh Thanh Nguyen Svetoslav Novkov Sebastian Oberth¨ ur Manish Parashar Cathryn Peoples Barbara Pernici Mario Pickavet Jean-Marc Pierson Wojciech Piotrowicz Massimo Poncino Rastin Pries Gang Qu Sanjay Ranka Martino Ruggiero Brahmananda Sapkota Toshinori Sato Erich Schikuta Hartmut Schmeck Edwin Sha Anastasious Stamou Amirreza Tahamtan Makoto Takizawa Domenico Talia Frank Teuteberg Jordi Torres Gregg Vesonder Vladimir Vlassov Matijin Warnier Rongbo Zhu Albert Zomaya
EPFL, Switzerland North Dakota University, USA Universit¨ at Passau, Germany Ecole des Mines de Nantes, France INRIA, University of Lyon, France Transport Economics Laboratory Lyon, France Purdue University, USA Deutsches Klimazentrum, Germany Universidad Politecnica de Valencia, Spain University of Tartu, Estonia Ecole des Mines de Nantes, France OECD, France University of Tokyo, Japan University of Pittsburgh, USA International Institute for Applied Systems Analysis, Austria Technical University of Sofia, Bulgaria Free University of Brussels, Brussels Rutgers University, USA University of Ulster, UK Politecnico di Milano, Italy University of Ghent, Belgium University of Toulouse, France University of Oxford, UK Politecnico di Torino, Italy University of W¨ urzburg, Germany University of Maryland at College Park, USA University of Florida, USA University of Bologna, Italy University of Twente, The Netherlands Kyushu University, Japan University of Vienna, Austria KIT, Karlsruhe, Germany University of Texas at Dallas, USA University of Athens, Greece Vienna University of Technology, Austria Seikei University, Japan Universit` a Della Calabria, Italy Universit¨ at Osnabr¨ uck, Germany University of Catalonia, Spain ATT, USA KTH, Sweden University of Delft, The Netherlands South-Central University for Nationalities, China University of Sydney, Australia
Table of Contents
Parallel Computing Towards Energy Efficient Parallel Computing on Consumer Electronic Devices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Karl F¨ urlinger, Christof Klausecker, and Dieter Kranzlm¨ uller
1
Characterizing Applications from Power Consumption: A Case Study for HPC Benchmarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Georges Da Costa and Jean-Marc Pierson
10
Principles of Energy Efficiency in High Performance Computing . . . . . . . . Axel Auweter, Arndt Bode, Matthias Brehm, Herbert Huber, and Dieter Kranzlm¨ uller
18
ICT for Transportation Geocast Routing in Vehicular Networks for Reduction of CO2 Emissions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Maazen Alsabaan, Kshirasagar Naik, Tamer Abdelkader, Tarek Khalifa, and Amiya Nayak Limiting Pollution in Ground Control Optimization . . . . . . . . . . . . . . . . . . Ludovica Adacher and Marta Flamini A Simulation Environment for Smart Charging of Electric Vehicles Using a Multi-objective Evolutionary Algorithm . . . . . . . . . . . . . . . . . . . . . Maryam Ramezani, Mario Graf, and Harald Vogt
26
41
56
Cloud Computing Furthering the Growth of Cloud Computing by Providing Privacy as a Service . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . David S. Allison and Miriam A.M. Capretz
64
The Concept of a Mobile Cloud Computing to Reduce Energy Cost of Smartphones and ICT Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Majid Altamimi and Kshirasagar Naik
79
X
Table of Contents
Pervasive Computing A Model for Sequence Based Power Management in Cyber Physical Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Andreas Barthels, Florian Ruf, Gregor Walla, Joachim Fr¨ oschl, Hans-Ulrich Michel, and Uwe Baumgarten A System for Energy Savings in an Ambient Intelligence Environment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Thanos G. Stavropoulos, Dimitris Vrakas, Alexandros Arvanitidis, and Ioannis Vlahavas Profiling Power Consumption on Desktop Computer Systems . . . . . . . . . . Giuseppe Procaccianti, Antonio Vetro’, Luca Ardito, and Maurizio Morisio
87
102
110
Measurement and Control GAINS – An Interactive Tool for Assessing International GHG Mitigation Regimes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Thanh Binh Nguyen, Fabian Wagner, and Wolfgang Schoepp Role of Context-Awareness for Demand Response Mechanisms . . . . . . . . . Pari Delir Haghighi and Shonali Krishnaswamy An Architecture and Methodology for a Four-Phased Approach to Green Business Process Reengineering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Alexander Nowak, Frank Leymann, David Schumm, and Branimir Wetzstein
124 136
150
Storage ADSC: Application-Driven Storage Control for Energy Efficiency . . . . . . . Cinzia Cappiello, Alicia Hinostroza, Barbara Pernici, Mariagiovanna Sami, Ealan Henis, Ronen Kat, Kalman Meth, and Marcello Mura Utilization-Aware Redirection Policy in CDN: A Case for Energy Conservation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Saif ul Islam, Konstantinos Stamos, Jean-Marc Pierson, and Athena Vakali Author Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
165
180
189
Towards Energy Efficient Parallel Computing on Consumer Electronic Devices Karl F¨ urlinger, Christof Klausecker, and Dieter Kranzlm¨ uller Department of Computer Science, MNM-Team Ludwig-Maximilians-Universit¨ at (LMU) M¨ unchen, Germany
Abstract. In the last two decades supercomputers have sustained a remarkable growth in performance that even out-performed the predictions of Moore’s law, primarily due to increased levels of parallelism [19]. As industry and academia try to come up with viable approaches for exascale systems, attention turns to energy efficiency as the primary design consideration. At the same time, energy efficiency has always been the main concern in the mobile computing area. Additionally, mobile and consumer electronic devices are becoming ever more powerful as the use cases (e.g., Web 2.0 applications, video encoding, virtual and augmented reality) become more computationally demanding. It is therefore an interesting question to ask if these devices are the possible building blocks of future HPC systems. It was the workstation and server market in the past that provided the CPUs that power supercomputers and it might be the consumer electronic market that provides the underlying technology in the future. In this paper we try to analyze the current state of energy efficient parallel and distributed computing on mobile and consumer electronic devices. We provide an overview of performance characteristics of some current and announced future devices for scientific computation and we build a small proof-of-concept cluster from Apple’s second generation “Apple TV” devices and evaluate its performance on standard benchmark applications. We discuss the limiting factors, and analyze the industry trajectory that we believe could make consumer electronic-based design a feasible technology basis for future HPC system designs.
1
Introduction
Total power consumption and energy efficiency of each component have become important considerations for the design of data-centers and high performance computing facilities. For the next generation of supercomputers (exascale systems), energy efficiency will even become the single most important constraining factor [13]. At the same time, consumer electronic and handheld devices have always been designed with energy efficiency in mind, with efficient ARM-based CPUs powering the majority of devices in the recent history. Driven by use cases such as HD video streaming, rich Web 2.0 browser applications, virtual reality, and 3D gaming, there are strong market forces driving D. Kranzlm¨ uller and A M. Tjoa (Eds.): ICT-GLOW 2011, LNCS 6868, pp. 1–9, 2011. c Springer-Verlag Berlin Heidelberg 2011
2
K. F¨ urlinger, C. Klausecker, and D. Kranzlm¨ uller
the future development of theses mobile devices towards more powerful compute capabilities [15]. For example, dual and even quad core mobile CPU designs with GPU integration have been announced for the next generation of tablet computers. In the light of these developments it is therefore interesting to analyze whether consumer electronic devices could become building blocks of future HPC systems. The supercomputing market is (for the most part) too small to sustain its own CPU ecosystem and in the past has leveraged workstation and server CPUs. In the future, the underlying technology might very well come from consumer electronic space. With our AppleTV Cluster1 we try to provide a data point on the current state of energy efficient parallel and distributed computing on ARM powered consumer electronic devices. The second generation Apple TV (ATV2) is meant to be used as a video streaming client and shares most of its hardware internals with the first generation iPad. The Apple A4 processor combines an ARM Cortex-A8 running at 1 GHz with a PowerVR SGX535 GPU and 256 MB RAM. The device is small (3.9 × 3.9 × 0.9 inches / 9.8 × 9.8 × 2.3 cm) relatively inexpensive (about 100 USD) and consumes only about 2-3 Watts). We have built a small (currently containing four nodes) proof-of-concept cluster out of ATV2s and evaluate it with respect to its power and performance characteristics. The rest of this paper is organized as follows: In Sect. 2 we give a short overview of the current state of the ARM-based computing ecosystem. In Sect. 3 we describe the hardware and software setup of our cluster and in Sect. 4 we evaluate both the single node characteristics as well as the power and performance of the whole system. We discuss related work in Sect. 5 and conclude and provide an outlook on future work in Sect. 6.
2
ARM Computing
ARM holdings is a company headquartered in Cambridge, UK that develops and licenses CPU designs but does not manufacture CPUs themselves. The company was founded in 1990 as a joint venture to continue development of the Acorn RISC Machine (later known as the Advanced Risc Machine), and reports that its technology is used in over one-quarter of all electronic devices [1]. Almost every modern mobile phone is based on ARM architecture CPUs [1] and multi-core mobile devices have started to appear recently [3]. Server solutions based on ARM chips have also recently been announced. The startup company Calxeda has announced plans for a 2U server with 120 CortexA9 quad-core chips and a fast interconnect network [11]. Marvell has announced a quad-core server SoC design based on the Cortex-A9 and with support for DDR3 memory and PCI-Express 2.0 interface [4]. Most devices use the ARM Cortex-A8 (single core) or Cortex-A9 (up to quad-core) CPU designs. 1
http://www.applevtcluster.com
Towards Energy Efficient Parallel Computing
3
3
The AppleTV Cluster
We built a small cluster out of four second generation AppleTV (ATV2) devices. To enable the installation of custom software, it was necessary to perform a jailbreak. Once jailbroken, the device comes with a ssh server pre-installed that allows interactive shell access to the BSD-based iOS operating system (iOS 4.2.1, Darwin 10.4.0 kernel). The installation of a fully functional development toolchain (gcc 4.2.1) and editor is relatively straightforward from then on. Please consult our project web page at http://www.appletvcluster.com for a more detailed HOWTO guide. The ATV2 nodes in our cluster are connected to an Ethernet switch. Access to the cluster nodes is organized through a gateway system (a conventional x86based PC in our case) which is also connected to the switch. To use the cluster to run parallel jobs, we installed an MPI (Message Passing Interface) distribution as the next step. We chose MPICH 2 from Argonne National Lab and configured it using the hydra process manager and TCP transport mechanism.
4
Evaluation
In this section we provide some results of our ongoing evaluation of the characteristics of our ATV2 cluster. We divide the evaluation into a section on single node performance and aspects pertaining to the whole system. Throughout this section we either provide absolute performance numbers and a rough (order of magnitude) comparison to the performance level of contemporary server hardware or compare the ATV2 directly to a popular ARM-based computing platform, the BeagleBoard (http://www.beagleboard.org). We have used a BeagleBoard xM for this comparison which was provided courtesy of collaborators at TU Munich and is also based on the Cortex-A8 CPU. It has an Texas Instruments DM3730 SoC with a 1 GHz2 Cortex-A8 CPU, 64 KB L1 cache, 256 KB L2 cache, and 512 MB low power DDR RAM. Several benchmarking efforts have previously used the BeagleBoard to compare the Cortex-A8 with with other low-power CPU solutions (cf. Sect. 5), and we analyze the relative performance of the BeagleBoard and the ATV2 in order to make our data comparable to those published results. 4.1
Single Node
Table 1 lists several key characteristics of the ATV2’s Apple A4 SoC as reported by the operating system through the iOS “sysctl” command. To independently confirm these parameters, we have used membench [8]. This benchmark tests the memory system performance by accessing arrays of increasing sizes with varying strides. A detailed discussion of the benchmark is beyond the scope of this paper but the data in Figures 1 and 2 confirms the data in Table 1 and additionally shows that the latency to L1 cache is 1 cycle and the latency to L2 cache is 8 cycles. 2
Our board was configured to run at 800 MHz instead of 1 GHz.
4
K. F¨ urlinger, C. Klausecker, and D. Kranzlm¨ uller Table 1. Characteristics of the Apple A4 chip as listed by the “sysctl” command Property L1I cache size L1D cache size L2 cache size Cacheline size Bus frequency Memory size Page size
Value 32 KB 32 KB 512 KB 64 B 100 MHz 247 MB 4KB
sysctl entry hw.l1icachesize hw.l1dcachesize hw.l2cachesize hw.cachelinesize hw.busfrequency hw.memsize hw.pagesize
4 KB page size
64 B cache line size 160
4KB 8KB 16KB 32KB 64KB 128KB 256KB 512KB 1MB 2MB
140
120
Time (nsec)
100
80
60
40
20
0
4
16
64
256
1K
4K
16K
64K
256K
1M
Stride (bytes)
Fig. 1. Membench runs with array sizes ranging from 4 KB to 2 MB
CPU Performance: We ran the Coremark benchmark3 to measure the performance of our individual ATV2 nodes. Coremark is an open source benchmark released by the Embedded Microprocessor Benchmark Consortium (EEMBC) with the goal to provide isolated CPU performance tests. Its focus is on benchmarking CPU cores of embedded systems, however, the website also contains results of high-end desktop and server CPUs. Coremark is based on commonly used algorithms and while its isolated approach does not necessarily reflect real applications, the single value results enable to easily compare performance of different processors. Table 2 shows our benchmark results on the BeagleBoard xM and the ATV2. The results show very comparable performance on a per-MHz basis, the small differences are most likely due to different compiler versions and different cache sizes on the two platforms. 3
www.coremark.org
Towards Energy Efficient Parallel Computing
80
5
4KB 8KB 16KB 32KB 64KB 128KB 256KB 512KB 1MB 2MB
70
60
Time (nsec)
50
40
30
20
8 ns L2 latency
10
1 ns L1 latency
0
4
16
64
256
1K 4K Stride (bytes)
16K
64K
256K
1M
Fig. 2. Detail of the Membench data shown in Fig. 1, with a focus on array sizes from 4 KB to 512 KB Table 2. Coremark benchmark results Device BeagleBoard xM (800 MHz) ATV2 (1 GHz)
Coremark score Coremark per MHz 1928 2316
2.41 2.32
By comparison, we also measured an Intel Atom N270 running at 1.6 GHz at 4674 (2.92 per MHz) with two threads and 3029 (1.89 per MHz) with only one thread. Modern sever nodes achieve much higher total Coremark scores (An Intel Xeon L5640 is listed on the Coremark webpage with a score of more than 110000). However, on a per-thread and per-MHz basis, the best coremark score listed is around 4.2, indicating that the Cortex-A8 achieves comparable performance according to this metric. While Coremark largely only test the integer performance, Linpack is a popular floating point intensive benchmark. Linpack solves a dense linar system of equations using LU factorization. Table 3 shows the results we have obtained by running the (sequential) Linpack benchmark on a single node. Linpack can either be run for single (SP) or double precision (DP) floating numbers. In the case of SP, the Cortex-A8 CPU is able to utilize SIMD registers using NEON instructions. NEON registers are 128 bits wide and allow up to four SP floats to be operated on at once, however NEON is not available for double precision. Unfortunately the compiler version we used on the ATV2 is not able to generate NEON code and we where thus not able to improve the Linpack performance past the 57.2 MFlops reported in Table 3. We are still investigating the BeagleBoard’s comparatively low performance and the anomaly of faster DP than SP performance.
6
K. F¨ urlinger, C. Klausecker, and D. Kranzlm¨ uller Table 3. Linpack benchmark results
Linpack SP (w/o NEON) Linpack SP (w/ NEON) Linpack DP (w/o NEON)
BeagleBoard xM (800 MHz) ATV2 (1 GHz) 22.6 57.5 33.8 – 29.3 40.8
Memory Subsystem: To test the memory system performance we ran the standard stream [5] benchmark and the results are displayed in Table 4. The data shows the results for four variants and compares the results we obtained on the AppleTV2 with the BeagleBoard xM running at 800 MHz. The ATV2 reportedly uses 200 MHz DDR2 RAM with a 64 bit wide memory bus, which would explain the relatively large performance advantage over the BeagleBoard xM (with 166 MHz and 32 bit memory bus). By comparison, a modern Intel Core i7 CPU with 800 MHz DDR2 RAM delivers more than ten times this bandwidth. Table 4. Results of the Stream benchmark on the ATV2 and the BeagleBoard xM (in MB/s) Operation BeagleBoard xM (800 MHz) ATV2 (1 GHz) copy 481.1 749.8 scale 492.9 690.0 add 485.5 874.7 triad 430.0 696.1
4.2
Whole System
MPI Performance: We measured the basic performance characteristics of the interconnect using the OSU microbenchmark suite [16]. Figure 3 shows a plot of the achieved bandwidth and latency. Note that the ATV2 only supports 100MBit Ethernet and that our MPI implementation uses TCP as the transport mechanism. The 100MBit Ethernet is about two orders of magnitude slower than today’s modern high performance interconnects (10GigE, Infiniband QDR) and this is reflected in the comparatively poor bandwidth and latency results. High Performance Linpack (HPL) We ran the High Performance Linpack benchmark (HPL) in parallel on all four nodes of the cluster. The best performance we achieved was 160.4 MFlops in double precision arithmetic. Taking into account a power consumption of 10 Watts for the whole cluster (see the next section) this results in a performance of about 16 MFlops/Watt. For comparison, the currently (April 2011) top-ranked system in the Green500 list is a BlueGene/Q prototype with over 1600 MFlops/Watt. To put this result in perspective one has to keep in mind a couple of things though. First, in double precision the Cortex-A8 does not support SIMD parallelism using NEON and Linpack greatly benefits from wider SIMD width.
Towards Energy Efficient Parallel Computing
Latency
7
Bandwidth
700
12
Latency
600
Bandwidth
10
Bandwidth (MB/sec)
Latency (usec)
500
400
300
8
6
4
200 2
100
0
1
2
4
8
16
32
64
128
Message size (bytes)
256
512
1K
2K
4K
0
4
16
64
256
1K
4K
16K
64K
256K
1M
Message size (bytes)
Fig. 3. Latency (half round-trip latency in Microseconds) and Bandwidth (in MB/Second) as measured by the OSU Microbenchmark suite
Experiments [6] showed that doubling the SIMD width in contemporary Intel CPUs from SSE to AVX can improve the performance of Linpack (on a single node) by about 72%. Second, the VFP unit implementing the DP arithmetic is not pipelined and each floating point operation takes a full 9-17 cycles (depending on operation and operands). Assuming an average latency of 15 cycles, the peak double precision floating point rate of the Cortex-A8 would only be 66.7 MFlops (and our Linpack run achieves 40 MFlops). Third, each ATV2 contains a relatively powerful PowerVR SGX535 GPU that contributes to its power consumption and could improve the floating point performance significantly, if it could be utilized for the computation. Unfortunately, OpenCL programming is not supported on the AppleTV though and so far we found no simple way to exploit the capabilities of the GPU. Lastly, the Green500 list also contains systems that are a lot less energy efficient than the BlueGene/Q prototype. The least energy efficient system (ranked at 500) is a Dell PowerEdge Infiniband Cluster with only 21 MFlops/Watt which is close to the ATV2 cluster result. Power Consumption: We estimated power consumption using a simple power meter. As the measurement accuracy of our setup is limited, and we can only provide an approximation of the power consumption of the cluster (all four nodes). We tested power consumption with three different baseline loads and our results indicate that all the whole cluster (all four ATV2 nodes, but not including the switch) consume about four Watts when idle and and about eight to ten Watts when fully loaded running the Linpack benchmark.
5
Related Work
Several projects have previously built and benchmarked clusters composed of unconventional nodes, such as the Sony Playstation 3 [10],[17], Set-Top-Boxes [14], and the Microsoft XBox [20].
8
K. F¨ urlinger, C. Klausecker, and D. Kranzlm¨ uller
ARM-powered computer devices have also been benchmarked before. A course paper from the University of Texas [18] contains an architectural and benchmark comparison of the Cortex-A8 CPU and the Intel Atom N330. A detailed comparison of the Cortex-A8 with various x86-based solutions is also presented in an online article [2] by Van Smith. The author finds the ARM based solution to be competitive regarding their integer performance but lacking in terms of floating point and memory performance. In supercomputing, the successful IBM BlueGene line of systems can be seen as an early example of supercomputer design inspired by embedded processors. BG/L was based on a relatively low performance dual-core PowerPC 440 processor which lead to massively parallel but well balanced systems [7]. BG/P increased the number of cores to four and eased some of the programmability restrictions of the overall system. A prototype of BlueGene/Q is currently (April 2011) the most energy efficient system on the Green500 list [12] with over 1600 MFlops/Watt. While the BlueGene architecture has been specifically optimized for HPC workloads, this is not the case for ARM-based systems. For example there is currently no support for double precision floating point SIMD operations in NEON. Instead, ARM CPUs often come packaged with fairly powerful GPUs.
6
Outlook and Conclusion
In this paper we have presented the hardware and software setup of our AppleTV cluster. The second generation AppleTV (ATV2) is an example of a growing number of consumer electronic devices that combine an ARM CPU and a powerful GPU in a single package. These devices are designed for energy efficiency from the ground up and are increasingly driven by computationally intensive use cases such as video encoding and augmented reality. While the raw performance and the performance per Watt we have observed with the AppleTV cluster so far is not competitive with conventional desktop CPU (or GPU) solutions, we believe that technology from the consumer electronic sector can play an increasing role in server and high-performance computer installations. A number of technical issues will have to be addressed for this to happen though. First, NEON has to be extended to fully support double precision floating point arithmetic. While fast single precision floating point hardware has successfully been exploited before [9], most applications require a fully compliant IEEE-754 double precision implementation and a large fraction of the performance of HPC systems can be attributed to wide data parallelism in the form of GPUs or wide SIMD registers. Second, ECC memory is required for any mission critical system, and third, communication intensive applications benefit tremendously from a fast interconnect. Some of these issues are already being addresses in SoC designs such as the Marvell Armada XP [4]. We plan to continue the evaluation of the AppleTV cluster along several directions. First, we would like to conduct a more detailed study of the ATV2 in comparison to the single-core BeagleBoard and the dual-core PandaBoard platforms in order to the evaluate the properties of the ARM multicore approach.
Towards Energy Efficient Parallel Computing
9
Second, a large fraction of the compute power of future consumer electronic devices will come from integrated GPUs and we plan to investigate the capabilities of these GPUs for general purpose computing on the ATV2 and other devices. Finally, the ATV2 is much more competitive in integer than in floating point intensive calculations and we plan to investigate the use its application to non-traditional HPC workloads.
References 1. ARM company profile, http://www.arm.com/about/company-profile/index.php 2. The coming war: ARM versus x86, http://vanshardware.com/2010/08/ mirror-the-coming-war-arm-versus-x86/ 3. LG optimus 2x, http://www.lg.com/global/press-release/article/ lg-launches-world-first-and-fastest-dual-core-smartphone.jsp 4. Marvell Armada XP multicore series, http://www.marvell.com/products/ processors/embedded/armada_xp/ 5. STREAM: Sustainable memory bandwidth in high performance computers, http://www.cs.virginia.edu/stream/ 6. Vektorisierungsk¨ unstler, https://www.heise.de/artikel-archiv/ct/2011/4/ 156_Compiler-Intel-Composer-XE-2011-mit-AVX-Optimierung 7. Adiga, N. R., et al.: An overview of the BlueGene/ L supercomputer (2002) 8. Arpaci, R.H., Culler, D.E., Krishnamurthy, A., Steinberg, S.G., Yelick, K.: Empirical evaluation of the CRAY-T3D: a compiler perspective. SIGARCH Comput. Archit. News 23, 320–331 (1995) 9. Buttari, A., Dongarra, J., Langou, J., Langou, J., Luszczek, P., Kurzak, J.: Mixed precision iterative refinement techniques for the solution of dense linear systems. Int. J. High Perform. Comput. Appl. 21, 457–466 (2007) 10. Buttari, A., Luszczek, P., Kurzak, J., Dongarra, J., Bosilca, G.: SCOP3: A rough guide to scientific computing on the PlayStation 3. version 0.1. Technical Report UT-CS-07-595, Innovative Computing Laboratory, University of Tennessee Knoxville (April 2007) 11. Calxeda 5 watt ARM server, http://insidehpc.com/2011/03/14/ calxeda-boasts-of-5-watt-arm-server-node/ 12. The Green500 List, http://www.green500.org 13. Kogge, P.M., et al.: Exascale computing study: Technology challenges in achieving exascale systems. DARPA Information Processing Techniques Office (IPTO) Sponsored Study (2008) 14. Neill, R., Shabarshin, A., Carloni, L.P.: A heterogeneous parallel system running OpenMPI on a broadband network of embedded set-top devices. In: Proceedings of the 7th ACM International Conference on Computing Frontiers, CF 2010, pp. 187–196. ACM, New York (2010) 15. NVIDIA. The benefits of multiple CPU cores in mobile devices, whitepaper (2010), http://goo.gl/g3MXo 16. OSU Micro-Benchmarks, http://mvapich.cse.ohio-state.edu/benchmarks 17. PS3 cluster at NCSU, http://moss.csc.ncsu.edu/~mueller/cluster/ps3/ 18. Katie, R.-H., Hedge, P.: ARM Cortex-A8 vs. Intel Atom: Architectural and benchmark comparisons (2009) 19. The Top 500 Supercomputer Sites, http://www.top500.org 20. Unmodified Xbox Cluster, http://www.bgfax.com/xbox/home.html
Characterizing Applications from Power Consumption: A Case Study for HPC Benchmarks Georges Da Costa and Jean-Marc Pierson Toulouse University {dacosta,pierson}@irit.fr
Abstract. With the rise of Clouds and PaaS (Platform as a Service) usage, providers of large computing facilities are completely disconnected from users running jobs on their infrastructure. Thus, the old adage knowledge is power has never been so true. By having good insight on application running on their infrastructure, providers can save up to 30% of their energy consumption while not impacting too much applications. Without access to application source code, it can be quite difficult to have a precise vision of the type of application. For instance, in NAS Parallel Benchmark (NPB), seven different benchmarks are available and have different behaviors (memory consumption patterns, performance decreasing with processor frequency,...) but discriminating between them can be costly due to the monitoring infrastructure. In this article we show that using power consumption of hosts we can discriminate between applications with nearly no impact on the application execution and without a-priori knowledge.
1
Introduction and Motivation
Having a better understanding of a running application is a key feature for both application developers and hosting platform administrators. While the former have access to the source codes of their application, the latter have usually no a priori clue on the actual behavior of an application. Having such information would allow for a better transparent accounting of the resource usage per application when several customers share the same physical infrastructure. The platform providers (and the underlying management middleware) would be able to better consolidate the applications on a smaller number of actual nodes. Platform provider would be able to provide token-free license where the observation of the system permits to determine the usage of a commercial application without bothering users with the token management. When running HPC applications, knowing the communication patterns of the running jobs allows for predicting the interaction of the jobs (possibly embedded in Virtual Machines) without instrumenting the code. Detecting automatically a communication phase allows for decreasing frequency and voltage of the processor, reducing power consumption. These information also give inputs on the D. Kranzlm¨ uller and A M. Tjoa (Eds.): ICT-GLOW 2011, LNCS 6868, pp. 10–17, 2011. c Springer-Verlag Berlin Heidelberg 2011
Characterizing Applications from Power Consumption
11
matching between a job and a particular host: Detecting an heavy communicating job will help to decide to migrate it on a network-performant host; another example is the placement of similar jobs (in their communication or memory usage pattern) on the same host that may be avoided. This finally results in optimized facility management that benefits both the platform provider and its users. Classifying applications using a limited number of parameters allows for a fast response on their characterization, suitable for online usage. Observing the system and being able to detect to which class an application belongs is possible, so far using offline trace analysis. Offline performance analysis helps for long term and/or repeating services and applications, but it needs a monitoring infrastructure that is not usually transparent for the application: The observer disturbs the observed phenomena. While this is not an issue for service-oriented applications running in service clouds (where the platform usage by an application is close to a maximum of 30%), this becomes an issue for more constrained HPC applications. Most of the codes are heavily tuned to perform at best, achieving top-ranked flops per seconds performance. Adding provider-based monitoring infrastructure is not acceptable in many cases, or the data acquisition frequency is so low (not to disturb the experiment) that having pertinent usage figures is not achieved. Hence the need for low-impact monitoring and classification is mandatory in such cases. In this paper we propose a methodology with no impact on the running applications to characterize their behavior. Using only external monitored value (i.e. power and network communications) we are able to discriminate between different classes of applications at runtime, opening doors to a wide variety of transparent actions on the system. The paper is organized as follows: Section 2 exhibits related works. Section 3 describes our approach while Section 4 shows experimental results. Finally we conclude in Section 5 with current and future works.
2
State of the Art
Many authors propose offline analysis of HPC applications. In [16] authors introduce metrics to characterize parallel applications. Their motivation is to be able to chose the right platform for a given application from the classification based on static code analysis. Not taking into account the actual machines where the applications run is presented as a benefit but does not allow for online and direct classification and class detections. In [1] an approach based on a similarity-based taxonomy is proposed, but nothing is said about the differentiation of the applications in the different classes (and the number of classes). Both approaches show the possibility of classifying the parallel applications in a limited number of classes. In [4], authors manually analyze the communication patterns of 27 applications from different HPC benchmarks based on MPI communication library. Their purpose was to study the possible deterministic communication patterns in order to exploit them in fault tolerance algorithms. This code analysis is time
12
G. Da Costa and J.-M. Pierson
consuming and does not allow for runtime analysis. However it proves the potential and the value of communication pattern discovery. The authors of [12] proposes a tool for assessing the code quality of HPC applications which turns to static pattern analysis while for instance [3] proposes MAQAO to tune performance of OpenMP codes. In [6], authors present the Integrated Performance Monitor (IPM). This tool allows for MPI application profiling and workload characterization. It allows for post-mortem analysis of the application behavior to understand the computation and communication phases. Vampir [11], Tau [15], Sun Studio [9] are other examples of such performance analysis tools. In [8] authors use Periscope to automatically detect memory access patterns, after the program ends. Similarly, Scalasca [7] searches for particular characteristic event sequences in event traces automatically. From low-level event traces, it classifies the behavior and quantifies the significance of the events by searching for patterns of inefficient behaviors. It relies on a number of layers to create an instrumented code, to collect and measure via measurement libraries linked with the application, to trace the running application to finally analyze a report produced after the run. Authors of [14] use an I/O stress test benchmark, namely IOR, to reproduce and predict I/O access patterns. Analysis of the results shows that a simple testbed can be used for the characterization of more complex applications, but a manual tuning of the benchmark parameters has to be operated, which leads to impractical usage. In [10] authors examined and compared two input/output access pattern classification methods based on learning algorithms. The first approach used a feedforward neural network previously trained on benchmarks to generate qualitative classifications. The second approach used Markov models trained from previous executions to create a probabilistic model of input/output accesses. All these works propose to characterize the application after their run. They usually need instrumentation of the running code and heavy capturing tools to intercept system calls and communication routines. Other approaches like [5,13] analyze code features at run time. Performance counters on the machines are collected and mathematical models deriving power consumption of applications on the system are provided. Based on statistical analysis they do not need any instrumentation of the code itself, but only of the running system. This latter is close to the fundamental of our approach since it allows for online detection of classes.
3
Our Approach
Classification can be based on provided information or based on the application behavior. Classification will be used in order to tune systems parameters (network speed, processor frequency,...). Several applications impact the system in the same manner, depending only on their behavior. Even if being more complex, in this paper behavior detection is used: Additionally to avoid the need for provided information, it also reduces user burden: Indeed users don’t have to specify which type of application they run. It will finally remove the possibility to cheat the system (and the system administrator) on the real application run.
Characterizing Applications from Power Consumption
13
Without a-priori information (such as application name) it is necessary to obtain information on the application behavior. Several possibilities are available: Process information (performance counters, system resources used), Subsystem information (network, disks) and Host information (power consumption). Intuitively using all those information for one particular application allows for deriving in which category it fits. It enables also to understand in which phase this application is (computing, communicating, ...). Categories are defined using reference applications (in our study reference HPC applications : NAS Parallel Benchmark[2]). Initial model is obtained after running and monitoring all benchmarks and then clustering couple of characteristics to find combinations of characteristics allowing for discriminating between applications. This model of the characterization based on this clustering allows to fit any application (or phase of application) in a category. The most important part concerns the choice of characteristics used to define the model. To remove a-priori on this choice, it is necessary to test all combinations. Indeed some characteristics (such as the number of instructions processed -performance counter: PERF COUNT HW INSTRUCTIONS-) show finally only small variations on our HPC reference set of applications which are not sufficient to discriminate between these applications. Several combinations of characteristics are usable to achieve such classification. To choose between those, convenience and impact of measures are important. Network-related measurements and power-related measurements can be done outside of the computing node: Using such measures eliminated the impact of this monitoring method. This is of prime importance for HPC applications when the race for best performance does not permit extensive monitoring on the computing nodes. So we choose the external characteristic (network-related) which discriminates most when used in conjunction with power and create a first model. To improve the model we can then add new external characteristics until reaching an efficient enough model. Characteristics are defined not only as raw physical measures but also as the dynamic of those physical measures (for instance, standard deviation, average, ...).
4 4.1
Validation Experimental Method
In order to evaluate the possibility to discriminate between several applications, nodes from the Toulouse Grid5000 site have been used. Each node is connected to a watt-meter able to measure power consumption every second. Those monitored nodes are bi Dual-Core AMD Opteron processors (2218) at 2.6GHz with 8GB of memory and Gigabyte Ethernet card. Debian runs on those nodes, using 2.6.37 Linux kernel. Since the watt-meter sampling frequency is at maximum 1 (one sample every second), all the measurement infrastructure was set up for this granularity.
14
G. Da Costa and J.-M. Pierson
For this test, reference applications come from NAS Parallel Benchmark[2]. This benchmark provides 7 applications (IS, FT, EP, BT, LU, CG and SP) with workloads representatives of HPC applications. They exhibit a range of behaviors between an embarrassingly parallel code (EP) to LU decomposition of matrix (LU). Each of those applications is well described and present some well known communication and computing patterns. In the following, class C benchmarks are used. NPB classes are related to problem length. C classes problems are between half a minute to a few minutes on selected nodes. As most HPC applications, these benchmarks do not use disks so this characteristic is not taken into account in the following. For this batch of experiments, 4 nodes were used, leading to 16 cores experiment. NAS Parallel benchmark are all being configured to use 16 slots, one per core. Depending on the benchmark, some limits are imposed on the number of slots: Hence 16 cores have been used in order to have the same number of slots per benchmark. Some benchmarks need a power of two, some need a square,... 4.2
Experimental Results
1.2e+08
1.2e+08
1e+08
1e+08
Number of bytes sent per second
Number of bytes sent per second
Figures 1, 2 and 3 show the importance of taking into account application dynamism. They represent respectively the bandwidth used by CG, SP and FT benchmarks for sending data. The first one is stable during the experiment duration, the second one shows large variations (between 17Mb/s and 28Mb/s) while having a pattern, whereas the last one exhibits random variations. These characteristics show the internal execution patterns.
8e+07
6e+07
4e+07
2e+07
8e+07
6e+07
4e+07
2e+07
0
0 0
10
20
30
40 time (s)
50
60
70
80
Fig. 1. Send bandwidth for CG benchmark for one node
0
50
100
150
200
250
300
350
time (s)
Fig. 2. Send bandwidth for SP benchmark for one node
Those three figures exhibit that external measurements can at least discriminate between applications, without using exact values but only the dynamism of those values. To leverage this dynamism, measures are not only taken directly but also using statistical filters. The current filters used for evaluating relevance of measures were: 1st decile, last decile, median, mean value, standard deviation.
1.2e+08
3e+07
1e+08
2.5e+07
Number of sent bytes (1st decile)
Number of bytes sent per second
Characterizing Applications from Power Consumption
8e+07
6e+07
4e+07
2e+07
15 FT SP BT EP LU IS CG
2e+07
1.5e+07
1e+07
5e+06
0 0
20
40
60
80 100 time (s)
120
140
160
180
0 235
240
245
250 255 Power consumption (W)
260
265
270
8e+07
Fig. 3. Send bandwidth for FT benchmark Fig. 4. Send bandwidth first decile and for one node mean power are used to discriminate between IS, FT, EP, BT, LU and the block (CG, SP)
9e+07
5e+07
4e+07
Median sent bytes
6e+07
4e+07
2e+07
Number of sent bytes (med value)
7e+07
6e+07
FT SP BT EP LU IS CG
8e+07
3e+07
0e+00
2e+07
1e+07
240 0 235
240
245
250 255 Power consumption (W)
260
265
270
245
250
255
260
●
● ●●
●
● ●●
265
Mean power (W)
Fig. 5. Send bandwidth median value and Fig. 6. Automatic classification in 7 mean power are used to discriminate be- classes using R (with the fuzzy clustering tween CG, LU, BT, SP, FT and the block algorithm) (EP and IS)
Figures 4 and 5 show the best combinations to discriminate between NPB. It is a combination of mean power of all the nodes and send characteristics. These figures show that IS and FT have nearly the same send pattern, and using only this value would make it impossible to discriminate between these two. The same applies for other network characteristics. It is only by using power that it is possible to discriminate between these two benchmarks. It is also the case for SP and BT. Clustering is possible using those values as shown on Figure 6. This Figure shows the classical fuzzy clustering algorithm of R using the median value of send bandwidth and mean power consumption. Using only those two information, it is already possible to automatically differentiate between the 7 benchmarks. Without any knowledge on the application (only the fact there are 7 benchmarks), the obtained clustering is corresponding to the right one shown in Figure 5.
16
5
G. Da Costa and J.-M. Pierson
Conclusion
The experiments presented in this article show that using only external information such as power consumption and network traffic it is possible to evaluate which application is running on a particular node. This is possible in HPC environment as each node is usually dedicated to a particular application. Such method is particularly important for HPC environment as it does not have any impact on the computing infrastructure. Current experiments and the corresponding classification model are limited to the 4 nodes used. Using several architectures and number of nodes we will derive a parametrized model as a function of the architecture. In the current state of the system, an empirical comparison of the characteristics was conducted. An iteration of the mechanism will allow the system to choose itself which characteristic is the more relevant depending on the set of applications to discriminate so as to produce the classification model. Acknowledgment. Experiments presented in this paper were carried out using the Grid’5000 experimental testbed, being developed under the INRIA ALADDIN development action with support from CNRS, RENATER and several Universities as well as other funding bodies (see https://www.grid5000.fr). NPB runs on this testbed were done with the help of Damien Borgetto.
References 1. Asanovic, K., Bodik, R., Demmel, J., Keaveny, T., Keutzer, K., Kubiatowicz, J., Morgan, N., Patterson, D., Sen, K., Wawrzynek, J., Wessel, D., Yelick, K.: A view of the parallel computing landscape. Commun. ACM 52, 56–67 (2009) 2. Bailey, D., Harris, T., Saphir, W., van der Wijngaart, R., Woo, A., Yarrow, M.: The nas parallel benchmarks 2.0. Technical report. NAS Technical Report NAS-95-020, NASA Ames Research Center, Moffett Field (1995) 3. Barthou, D., Rubial, A.C., Jalby, W., Koliai, S., Valensi, C.: Performance tuning of x86 openmp codes with maqao. In: Parallel Tools Workshop, Dresden, Germany, pp. 95–113. Springer, Heidelberg (2009) 4. Cappello, F., Guermouche, A., Snir, M.: On communication determinism in parallel hpc applications. In: Proceedings of 19th International Conference on Computer Communications and Networks, ICCCN 2010, pp. 1–8 (August 2010) 5. Da Costa, G., Hlavacs, H.: Methodology of Measurement for Energy Consumption of Applications (regular paper). In: Energy Efficient Grids, Clouds and Clusters Workshop (co-located with Grid) (E2GC2), Brussels, October 25-October 29, page (electronic medium). IEEE, Los Alamitos (2010), http://www.ieee.org/ 6. F¨ urlinger, K., Wright, N.J., Skinner, D.: Performance analysis and workload characterization with ipm. In: Mller, M.S., Resch, M.M., Schulz, A., Nagel, W.E. (eds.) Tools for High Performance Computing 2009, pp. 31–38. Springer, Heidelberg (2010) 7. Geimer, M., Wolf, F., Wylie, B.J.N., Becker, D., B¨ ohme, D., Frings, W., Hermanns, M.-A., Mohr, B., Szebenyi, Z.: Recent developments in the scalasca toolset. In: M¨ uller, M.S., Resch, M.M., Nagel, W.E., Schulz, A. (eds.) Proc. of the 3rd Parallel Tools Workshop on Tools for High Performance Computing 2009, Dresden, Germany, pp. 39–51. Springer, Heidelberg (2010)
Characterizing Applications from Power Consumption
17
8. Gerndt, M., Kereku, E.: Automatic memory access analysis with periscope. In: Gervasi, O., Gavrilova, M.L. (eds.) ICCSA 2007, Part I. LNCS, vol. 4705, pp. 847–854. Springer, Heidelberg (2007) 9. Itzkowitz, M., Maruyama, Y.: Hpc profiling with the sun studio performance tools. In: Parallel Tools Workshop, Dresden, Germany, Springer, Heidelberg (2009) 10. Madhyastha, T.M., Reed, D.A.: Learning to classify parallel input/output access patterns. IEEE Transactions on Parallel and Distributed Systems 13(8), 802–813 (2002) 11. Nagel, W.E., Arnold, A., Weber, M., Hoppe, H.-C., Solchenbach, K.: Vampir: Visualization and analysis of mpi resources. Supercomputer 12, 69–80 (1996) 12. Panas, T., Quinlan, D., Vuduc, R.: Tool support for inspecting the code quality of hpc applications. In: Proceedings of the 29th International Conference on Software Engineering Workshops, p. 182. IEEE Computer Society, Washington, DC (2007) 13. Rivoire, S., Ranganathan, P., Kozyrakis, C.: A comparison of high-level full-system power models. In: Zhao, F. (ed.) HotPower, USENIX Association (2008) 14. Shan, H., Antypas, K., Shalf, J.: Characterizing and predicting the i/o performance of hpc applications using a parameterized synthetic benchmark. In: SC 2008, p. 42:1–42:12. IEEE Press, USA (2008) 15. Sameer, S.: The tau parallel performance system. Int. J. High Perform. Comput. Appl. 20, 287–311 (2006) 16. Alexander, S., van Amesfoort, A.S., Varbanescu, A.L., Sips, H.J.: Towards parallel application classification using quantitative metrics. In: ASCI 2010(2010)
Principles of Energy Efficiency in High Performance Computing Axel Auweter, Arndt Bode, Matthias Brehm, Herbert Huber, and Dieter Kranzlm¨ uller Leibniz Supercomputing Centre (LRZ) of the Bavarian Academy of Sciences and Humanities Boltzmannstr. 1, 85748 Garching bei M¨ unchen, Germany
[email protected] http://www.lrz.de/
Abstract. High Performance Computing (HPC) is a key technology for modern researchers enabling scientific advances through simulation where experiments are either technically impossible or financially not feasible to conduct and theory is not applicable. However, the high degree of computational power available from today’s supercomputers comes at the cost of large quantities of electrical energy being consumed. This paper aims to give an overview of the current state of the art and future techniques to reduce the overall power consumption of HPC systems and sites. We believe that a holistic approach for monitoring and operation at all levels of a supercomputing site is necessary. Thus, we do not only concentrate on the possibility of improving the energy efficiency of the compute hardware itself, but also of site infrastructure components for power distribution and cooling. Since most of the energy consumed by supercomputers is converted into heat, we also outline possible technologies to re-use waste heat in order to increase the Power Usage Effectiveness (PUE) of the entire supercomputing site. Keywords: High Performance Computing, Energy Efficiency, Power Usage Effectiveness, HPC, PUE.
1
Introduction
As of today, HPC sites and large data centres are among the biggest power consuming entities in the Information and Communication Technology (ICT) sector. According to a study conducted by the German Federal Ministry for the Environment, Nature Conservation and Nuclear Safety (BMU), the power consumption of the German HPC sites and data centres has more than doubled since the year 2000 and amounted to 10.1 TWh1 in 2008, which corresponded to
1
This paper is supported by PRACE-1IP, the Partnership for Advanced Computing in Europe, funded under the EU’s Seventh Framework Programme (FP7/2007-2013) under grant agreement n◦ RI-261557. http://www.prace-project.eu/ TWh: terawatt hour.
D. Kranzlm¨ uller and A M. Tjoa (Eds.): ICT-GLOW 2011, LNCS 6868, pp. 18–25, 2011. c Springer-Verlag Berlin Heidelberg 2011
Principles of Energy Efficiency in High Performance Computing
19
the emission of 6.4 million tonnes of CO2 [6] based on the German energy mix of that time. Recently, Moore’s law [12] has continued to show its validity: The number of transistors that can be put on a computer chip of constant die size has roughly doubled every 18 months. Manycore CPUs are omnipresent and in many cases supplemented by special purpose accelerators such as Graphics Processing Units (GPU) that feature similar levels of transistor density. Along with the growth of the number of transistors comes an increased demand of electrical power for the components. Thus, further increases in processing performance to support larger scientific simulations can only be achieved if the efficiency in terms of FLOPs2 per Watt is increased significantly. Although energy efficiency for ICT has been thoroughly discussed in the past, only very few HPC sites have implemented versatile power saving methods. Yet, many HPC sites operate systems with thousands of processing cores and the power consumption of the systems is getting more and more important as the number of processors increases. So far, the major drivers for energy efficient ICT have been mobile applications and commercial data centres, which were seeking longer battery runtimes and lower operating costs, respectively. Unfortunately, many of the developed energy saving technologies either do not scale to the size of HPC sites or are not applicable to HPC at all. For example, virtualisation technology has enabled data centres to increase the average usage of their servers notably, thus reducing the total amount of hardware components in use and the overall energy consumption. Yet, since HPC sites typically operate at more than 90% utilisation of their machines anyway, the use of virtualisation technologies is not a feasible way for supercomputing centres to reduce energy consumption. In this paper, we provide an overview of the existing and future promising techniques to improve the energy efficiency of HPC sites and applications. We introduce key concepts of power awareness and efficiency for both the compute hardware as well as for the surrounding HPC site infrastructure. Therefore, the next section will outline the necessary tools for energy monitoring and control, section 3 will cover possible improvements of the HPC site infrastructure, and section 4 will outline the requirements for energy efficient system hardware and operation management software.
2
Tools for Energy Monitoring and Control
A preparatory step to improve the energy efficiency in HPC consists of the fine-grained assessment of the power consumption of the entire HPC system encompassing not only compute nodes, interconnect networks and storage devices, but also site infrastructure components for cooling, monitoring and power supply. Given a holistic view of the energy consumption over time, ineffective use of components can be spotted and subsequently improved. An approach for this would be to sample the power consumption of all components at regular intervals and to store the resulting information into a central 2
FLOPs: Floating-point operations per second.
20
A. Auweter et al.
database. In addition, this database should also store information about the system’s workload and various utilisation metrics. Such metrics are the CPU load per core, additional CPU performance counter data like cycle and instruction counters, or per-node information on the interconnect network load. If the same database also holds information about the jobs running on the system, the energy consumption for a particular computation, so called energy-to-solution, can be measured. While the individual components necessary for such a monitoring system are available today, an integrated solution does not yet exist. Yet, implementation of the outlined ideas would allow fine-grained monitoring of the system’s power consumption including the attribution of power consumption on a per-job basis. In addition, a correlation between an application’s performance and its power consumption could be made enabling site operators to act accordingly, e.g. to pinpoint applications for which the energy efficiency of the calculation can be improved. Thus, the development of such a power monitoring system is subject to ongoing research.
3
Site Infrastructure Aspects
In order to minimize the power consumed by a HPC centre as a whole, one has to consider the reduction of power for running the computer system, and for the infrastructure necessary to run the computer system. Let us start with the consideration of the infrastructure. The supercomputing site infrastructure consists of the whole environment surrounding the HPC system such as the building, the necessary equipment for power supply, power distribution and cooling. The efficiency of the energy consumption spent on the supercomputing site infrastructure can be quantified using the Power Usage Efficiency (PUE) metric [11]. The PUE is defined as the ratio of the total energy used by the supercomputing site divided by the amount of energy that is consumed for pure computational work. In 2006, it was shown in [8] that typical data centres operate with PUE ratings between 1.3 and 3.0. In principal, there are three ways of improving the energy efficiency at the HPC site infrastructure level: (1) reduction of electrical loss in wires and during transformation, (2) improved cooling technologies, and (3) reuse of waste heat. Any transmission of electricity results in a certain line loss due to the ohmic, inductive and capacitive resistance of the cables in use. While the solution for large power grids is to transmit electricity at thousands of Volts which results in a reduction of line loss, ICT equipment operates at very low voltages. Through stepwise transformation, the electricity supplied to the data centre is made available at the compute and infrastructure components where internal standard ACDC power supplies provide the device-specific current. Both transformers and device power supplies themselves, as well as their distance to the final consuming entity play a significant role for the energy efficiency of the site. Keeping the low voltage paths at minimum length reduces the line loss significantly. Also, the efficiency of the internal AC-DC power supplies should be critically reviewed
Principles of Energy Efficiency in High Performance Computing
21
because their efficiency can vary significantly [3]. In case uninterruptible power supplies (UPS) are used, their efficiency should be critically assessed as well. Due to the principle of energy conservation, almost all of the energy consumed by a supercomputer is converted into heat. With today’s supercomputing sites consuming several Megawatts of power, effective and energy efficient cooling of a HPC system becomes crucial. The efficiency of the cooling apparatus directly depends on the target operation temperature of the components, the thermal conductivity and capacity of the coolant, and the energy necessary to drive the cooling system (fans, compressors, pumps,. . . ). Ordinary data centres often provide housing for customer-owned servers. Today, these machines are typically restricted to work solely with air based cooling. As an improvement, many studies such as [3] and [8] have shown the effectiveness of strictly separating hot and cold aisles in the room to avoid short-circuits of hot air into the cold air areas. Other ideas discussed include the use of watercooled racks which benefit from the improved thermal conductivity of water and avoids the extra energy spent on cooling the entire room. Since HPC installations are typically composed of a large number of homogeneous hardware components, due to the economies of scale and the type of components being freely selectable, cooling can be implemented in an even more efficient fashion: Through the use of direct liquid cooling in which all temperature-critical components are directly connected to a liquid cooling loop, the use of air as coolant is completely avoided. With an increasing demand for integration and the use of more processing cores per volume, manufacturing processes for 3D stacked silicon are currently being developed. Until now, the removal of dissipated heat was the biggest challenge for highly integrated semiconductors. New research work shows the feasibility of embedding ‘microchannels’ of 100µm diameter into multi-layered chips to provide in-chip liquid cooling [1]. Whether components are cooled at the package level or in-chip, the thermal capacity of liquid cooling systems allows for a temperature increase on the inlet side to 40◦ C or even higher temperatures while still providing sufficient cooling to the hardware. Since the resulting outlet temperatures increase accordingly, the entire system can be re-cooled freely to ambient air even on hot summer days in most areas. Alternatively, groundwater or water evaporation in the re-cooling plant can be used for re-cooling on hot days. All this renders active compressor based cooling technologies superfluous and results in minimal electricity spendings for cooling. With regard to the impact of higher operating temperatures on the mean time between failure, a promising study conducted by Intel showed no significant increase of the failure rate of a data centre that was kept at outside temperatures and humidity of up to 90◦ F (32◦ C) [2]. While relatively low outlet temperatures of a liquid cooling loop can already be used for generating warm water and heating buildings, higher temperatures are necessary for efficient re-use of waste heat for cooling or trigeneration. For driving an absorption cooling process, inlet temperatures of 75◦ C or higher are necessary to achieve a COP3 of 0.7-0.8. Another technology, adsorption cooling, 3
Coefficient of Performance:
ColdProduced DrivingHeat
.
22
A. Auweter et al.
allows lower inlet temperatures starting from 60◦ C at the price of a lower COP of 0.5-0.6 [13]. Although both cooling techniques operate at comparably low degrees of efficiency, coldness can be used in the HPC site itself to cool the remaining non-direct liquid cooled components, whereas hot water can only be used for heating in external buildings nearby.
4
System Hardware and Operation Requirements
Although current supercomputers show a continued increase in theoretical peak performance, they struggle to provide sustained performance to the user. Figure 1 shows the sustained performance of the HLRB-II supercomputer during one week of operation in March 2011. Although the majority of the 9728 CPU cores is active throughout the week, the sustained performance of the scientific applications ranges between 2 and 9 TFLOPs. Given that HLRB-II’s peak performance is 62.3 TFLOPs and during the Linpack benchmark, which is used for the Top5004 list, it achieved 56.5 TFLOPs, the tremendous gap between peak and sustained performance becomes visible. Figure 2 shows the achieved performance (in percent of the peak performance) on the HLRB-II for selected scientific application domains. Differences between peak performance and sustained performance allow for two conclusions to be drawn with regard to energy efficiency: either, the performance efficiency should be improved by closer matching software and hardware to the scientific problems to solve, or measures should be taken to ensure that hardware in idle state (which makes up the difference between peak performance and sustained performance) does not consume any power.
Fig. 1. Performance statistics gathered in March 2011 during a typical week of operation of the HLRB-II supercomputer
4
http://www.top500.org/
Fig. 2. FLOPs performance of HLRB-II in percent of the theoretical peak performance for different application domains
Principles of Energy Efficiency in High Performance Computing
23
One way to match the hardware to the scientific application can be the use of special purpose accelerators or Graphics Processing Units (GPUs) whose design is much less redundant in terms of transistor count of the executing hardware for the specific scientific applications as compared to a general purpose CPU. General Purpose GPU (GPGPU) computing has become a well studied field in recent years and its superiority for certain sets of computational workload is indisputable. Still, many workloads do not benefit from GPGPU acceleration and adaption of the codes to the accelerator architecture is expensive, if possible at all since the programmability of GPGPU accelerators remains a challenge. In an all-encompassing view of the HPC user needs, one must conclude that supercomputing cannot solely rely on this kind of hardware [9]. In contrast to GPGPUs that focus on massively parallel execution, modern CPUs incorporate sophisticated measures to improve their single-thread performance like large caches, branch prediction, speculative execution and out-oforder execution. These techniques achieve higher single thread performance at the expense of power consumption for the more redundant hardware, since for example energy spent on following a speculative execution path is lost whenever the path is not taken. A solution to this may be the use of low-power processors such as those targeted for the mobile and embedded markets that typically do not require a high general purpose single thread performance. Active research is currently being conducted within the Partnership for Advanced Computing in Europe (PRACE) to assess the feasibility of using low-cost, low-power Systemson-Chip for HPC. If changing the processing hardware is not feasible, the hardware in use might still be tuned to deliver a lower energy-to-solution. Many researchers have found that in power- and frequency-scalable clusters, applications benefit from reduced clock rates and variations in the degree of parallelism [5] [7] [14]. Since in many cases the gap between peak and sustained performance is due to the memory, communication, or I/O bandwidth boundedness, CPUs spend a lot of time idle waiting for data before continuing their calculation. In case the CPU clock frequency is reduced but memory and interconnect access times remain the same, the idle periods are shortened without a major impact on the overall application performance. Since the power consumption of a CPU running at lower clock frequencies is also lower, the overall energy-to-solution is reduced. Since some processors allow the frequency of every core to be selected individually, an empirical exploration of the configuration space is not feasible in many-core scenarios. Thus, research has been done to model and predict the optimal configuration in frequency-scalable systems [4]. In addition to freely scaling the performance of single nodes or cores, shutting down unused components entirely is also an effective measure to save energy. The necessary technologies have to be implemented at all levels. While at the chip level, automatic clock gating is already widely used to turn of inactive regions on the chip, the complete shutting down of cluster nodes that are intentionally left idle by the batch scheduler is still uncommon. In addition, batch scheduling systems that are topology-aware and implement mechanisms to force
24
A. Auweter et al.
execution of certain threads or tasks to particular cores can lead to an increased energy-efficiency if the selected pinning optimizes cache usage and inter-process communication patterns [10]. All outlined methods for improving the energy efficiency of HPC system hardand software span an optimization space of large dimensionality. Therefore, it is necessary to run site-specific tests on the correlation between selected performance and utilization metrics and their impact on the energy consumption. This allows specific optimizations for the configuration of hard- and software to be analysed in contrast to a simple trial and error approach. All this requires close interaction of monitoring and control components of the compute hardware and the site infrastructure as well as an intelligent and automatic energy-efficiency operating system software stack to relieve the application programmer from the burden of manual power optimization.
5
Conclusions
This paper gives an overview of the principles of energy efficient operation of a HPC site and shows differences and similarities to ordinary data centres. We have introduced techniques for monitoring the site, outlined an efficient site infrastructure and described the necessary features of the hardware and the system management software to operate at lowest possible power consumption while still obtaining the best possible computing power. Once the technical aspects are implemented, changes of the HPC centre’s usage policies will have to be discussed. This includes but is not restricted to ensuring that the users actively make use of the new energy-aware monitoring and control tools and user compliance with the site’s overall energy saving strategy is assured. We believe that only a holistic view and operation of the HPC site including compute and infrastructure components will allow utmost reduction of the power consumed and aid to retaining the competitiveness of HPC based simulation as a successful way of achieving scientific results. Acknowledgements. The Leibniz Supercomputing Centre (LRZ) is one of Germany’s largest supercomputing sites and a European HPC provider for the Partnership for Advanced Computing in Europe (PRACE) as well as a national HPC provider within the Gauss Centre for Supercomputing (GCS). LRZ has recently finished an expansion building to hold a 3 PetaFLOP/s supercomputer (SuperMUC) which will consist of more than 100,000 processing cores and will be installed in 2012. SuperMUC will make use of direct liquid cooling and the hot water will be reused for heating the LRZ buildings. Remaining hot water will be re-cooled freely to ambient air. SuperMUC is expected to achieve a PUE lower than 1.1. In addition, fine-grained monitoring facilities and an energyaware operating software stack as outlined in Section 2 will be implemented. As a preparatory system to implement the necessary tools for SuperMUC’s monitoring and control, and to test the feasibility of high inlet temperatures in direct liquid cooled systems, LRZ is putting into service a smaller cluster in
Principles of Energy Efficiency in High Performance Computing
25
which waste heat is re-used by an adsorption chiller to cool additional air-cooled components. The cluster will be put into service in May 2011 and first benchmark results of energy-to-solution measurements are expected to be available in Q3 2011.
References 1. Alfieri, F., Tiwari, M.K., Zinovik, I., Poulikakos, D., Brunschwiler, T., Michel, B.: 3D Integrated Water Cooling of a Composite Multilayer Stack of Chips. In: Proceedings of the 14th International Heat Transfer Conference (August 2010) 2. Atwood, D., Miner, J.G.: Reducing Data Center Cost with an Air Economizer. Technical report, Intel (August 2008), http://www.intel.com/it/pdf/reducing_ data_center_cost_with_an_air_economizer.pdf 3. Bruschi, J., Rumsey, P., Anliker, R., Chu, L., Gregson, S.: Best Practices Guide for Energy-Efficient Data Center Design. Technical report, U.S. Department of Energy (February 2010), http://www1.eere.energy.gov/femp/pdfs/ eedatacenterbestpractices.pdf 4. Maury, M.C., Blagojevic, F., Antonopoulos, C.D., Nikolopoulos, D.S.: Predictionbased power-performance adaptation of multithreaded scientific codes. IEEE Transactions on Parallel and Distributed Systems 19(10), 1396–1410 (2008) 5. Maury, M.C., Dzierwa, J., Antonopoulos, C.D., Nikolopoulos, D.S.: Online powerperformance adaptation of multithreaded programs using hardware event-based prediction. In: Proceedings of the 20th Annual International Conference on Supercomputing, ICS 2006, pp. 157–166. ACM, New York (2006) 6. Fichter, K., Clausen, J.: Energy-Efficient Data Centres - Best-Practice-Examples from Europe, the USA and Asia. Federal Ministry for the Environment Nature Conservation and Nuclear Safety (January 2010), http://www.bmu.de/english/ energy_efficiency/doc/45749.php 7. Freeh, V.W., Pan, F., Kappiah, N., Lowenthal, D.K., Springer, R.: Exploring the energy-time tradeoff in mpi programs on a power-scalable cluster. In: International Parallel and Distributed Processing Symposium, vol. 1, p. 4a (2005) 8. Greenberg, S., Mills, E., Tschudi, B., Rumsey, P., Myatt, B.: Best Practices for Data Centers: Lessons Learned from Benchmarking 22 Data Centers. In: Proceedings of the 2006 ACEEE Summer Study on Energy Efficiency in Buildings (2006) 9. Hacker, H., Trinitis, C., Weidendorfer, J., Brehm, M.: Considering gpgpu for hpc centers: Is it worth the effort? (2011) 10. Klug, T., Ott, M., Weidendorfer, J., Trinitis, C.: Autopin – automated optimization of thread-to-core pinning on multicore systems (2011) 11. Malone, C., Belady, C.: Metrics to Characterize Data Center & IT Equipment Energy Use. In: Proceedings of the Digital Power Forum (September 2006) 12. Moore, G.E.: Cramming more components onto integrated circuits. Electronics 38(8) ( April 1965) 13. N´ un ˜ez, T.: Thermally Driven Cooling: Technologies, Developments and Applications. Journal of Sustainable Energy 1(4) (December 2010) 14. Springer, R., Lowenthal, D.K., Rountree, B., Freeh, V.W.: Minimizing execution time in mpi programs on an energy-constrained, power-scalable cluster. In: Proceedings of the eleventh ACM SIGPLAN symposium on Principles and practice of parallel programming. PPoPP 2006, pp. 230–238. ACM, New York (2006)
Geocast Routing in Vehicular Networks for Reduction of CO2 Emissions Maazen Alsabaan1 , Kshirasagar Naik1 , Tamer Abdelkader1 , Tarek Khalifa1 , and Amiya Nayak2 1
Department of Electrical and Computer Engineering, University of Waterloo, Waterloo, ON, Canada N2L 3G1 2 School of Information Technology and Engineering, University of Ottawa, Ottawa, ON, Canada K1N 6N5 {malsabaa,snaik,tammabde,tkhalifa}@uwaterloo.ca,
[email protected]
Abstract. Pollution and gas emissions are increasing and negatively impacting global warming. Consequently, researchers are looking for solutions that save environment. Greenhouse gas (GHG) emissions from vehicles are considered to be one of the main contributing sources. Carbon dioxide (CO2 ) is the largest component of GHG emissions. Vehicular networks offer promising technology that can be applied for reduction of CO2 emissions. One of the major applications of vehicular networks is Intelligent Transportation Systems (ITS). To exchange and distribute messages, geocast routing protocols have been proposed for ITS applications. Almost all of these protocols evaluate network-centric performance measures, instead of evaluating the impact of the protocol on the vehicular system. Nowadays, the harmful effects of air pollutants have been the subject of considerable public debate. Vehicles’ stop-and-go condition, high speed, and high accelerations are environmentally unfriendly actions (EUF) that increase the amount of emissions. These actions can happen frequently for vehicles approaching a traffic light signal (TLS). Therefore, we propose a new protocol named environmentally friendly geocast (EFG), which focuses on minimizing CO2 emissions from vehicles approaching a TLS by avoiding the EUF actions. Simulation results demonstrate that the proposed protocol can achieve effective reduction of vehicle CO2 emissions. Keywords: CO2 emissions, environmentally friendly geocast, intelligent transportation systems, vehicular ad hoc networks.
1
Introduction
The detrimental effects of air pollution and concerns about global warming are being increasingly reported by the media. Greenhouse gas (GHG) emissions from vehicles are considered one of the main contributing sources. Carbon dioxide (CO2 ) is the largest component of GHG emissions. For example, in Japan in 2008, the amount of CO2 emissions from vehicles (200 million ton) is about 17 percent of the entire CO2 emissions from Japan (1200 million ton) [1]. The D. Kranzlm¨ uller and A M. Tjoa (Eds.): ICT-GLOW 2011, LNCS 6868, pp. 26–40, 2011. c Springer-Verlag Berlin Heidelberg 2011
Geocast Routing in Vehicular Networks for Reduction of CO2 Emissions
27
Kyoto Protocol aims to stabilize the GHG concentrations in the atmosphere at a level that would prevent dangerous interference with the climate system [2]. With increasing public awareness of the need for reduced GHG emissions from vehicles, it is important to address this problem by effectively using the capability of information technology before spending more on new roads. Geocast protocols in vehicular networks technologies are a promising research area in Intelligent Transportation Systems (ITS) applications. The main actions affecting the increase in the amount of emissions include acceleration, high speed, drivers getting lost or not taking a very direct route to their destination, idling cars on the road, stop-and-go conditions, choosing a path according to a navigation system that later becomes congested and inefficient after committing to that path. The question then becomes what role do geocast protocols play in vehicular networks to reduce the impact of some of these actions?. This paper focuses on reducing the impact of stop-and-go conditions, high speeds, and high accelerations. The effect of speed and acceleration on vehicle CO2 emissions can be investigated by using an emission model. Emission models have been studied in [3]. According to that study, the Virginia Tech Microscopic model (VT-Micro) is superior to the other models in its accuracy. To study the impact of vehicle speed, the vehicle acceleration is set to a constant value (say 0 kph/s). After that, the CO2 emissions are computed with different values of speed using VT-Micro model. Figure 1 shows that CO2 emissions increase with high speeds. Similarly, to show the effect of vehicle acceleration, the vehicle speed is set to 30 kph. Then, the CO2 emissions are calculated with different values of accelerations. Figure 2 demonstrates that negative accelerations do not affect the CO2 emissions much because vehicles do not exert power in negative accelerations. On the other hand, the amount of vehicle CO2 emissions increases with increasing the vehicle acceleration. As a result, it is logical to propose an existing scenario where some environmentally unfriendly (EUF) actions happen frequently. Based on this scenario, the capability of information technology has to be utilized to help avoid or reduce these actions.
Fig. 1. The impact of speed on vehicle CO2 emissions
28
M. Alsabaan et al.
Fig. 2. The impact of acceleration on vehicle CO2 emissions
The proposed scenario in this study involves vehicles approaching a Traffic Light Signal (TLS). The main EUF actions that can occur for these vehicles are stop-and-go condition, unnecessary excessive speed, and unnecessary high acceleration. This paper proposes an environmentally friendly geocast (EFG) protocol whose objective is to deliver the information of a TLS to approaching vehicles. Based on the TLS information, the vehicles calculate their recommended Environmentally Friendly (EF) speed (SR ) to serve three main purposes: 1. to avoid having to stop, a vehicle may adapt its speed to (SR ), such that SRmin ≤ SR ≤ SF , where SRmin is the minimum acceptable speed and SF is the free-flow (maximum allowed) speed. 2. to prevent unnecessary excessive speed, a vehicle adjusts its speed to SRmin in order to avoid unnecessary high speeds if the vehicle has to stop for the TLS. 3. to avoid high accelerations, a vehicle calculates the SR as the maximum possible speed for the vehicle to pass the TLS. As a result, after passing the TLS, the vehicle will return to the free-flow speed with low acceleration. The main contributions of this work are as follows: – Highlight the EUF actions that can be avoided by applying vehicular networks; – Identify a suitable scenario where applying vehicular geocast protocols will significantly reduce vehicle emissions; – For the identified scenario, propose and evaluate an EFG protocol that helps vehicles to avoid EUF actions. As a result, greater emissions reductions can be achieved. The remainder of this paper is organized as follows: Section 2 reviews related work about geocast protocols; Section 3 describes the system model; Section 4 proposes the EFG protocol; Section 5 presents and discusses simulation results; and finally, Section 6 draws conclusions and recommends future work.
Geocast Routing in Vehicular Networks for Reduction of CO2 Emissions
2
29
Related Work
Geocast protocols provide the capability to transmit a packet to all nodes within a geographic region. The geocast region is defined based on the applications. For instance, a message to alert drivers about congestion on a highway may be useful to vehicles approaching an upcoming exit prior to the obstruction, yet unnecessary to vehicles already in the congested area. The existing geocast protocols are classified based on the forwarding types, which are either flooding, directed flooding, or forwarding without flooding [4]. Based on performance metrics, geocast protocols are classified in this paper. Most existing geocast protocols for vehicular networks aim to minimize message latency, or to increase dissemination reliability. In this work, we want to draw the attention of researchers working in the field of communication to design geocast protocols that aim to reduce vehicle emissions. 2.1
Geocast Protocols to Minimize Message Latency
Message latency can be defined as the delay of message delivery. A higher number of wireless hops causes an increase in message latency. Greedy forwarding can be used to reduce the number of hops required to transmit a packet from a sender to a destination. In this approach, a packet is forwarded by a node to a neighbor located closer to the destination [5]. Contention period strategy can potentially minimize message latency. In reference [6], when a node receives a packet, it waits for some time before rebroadcasting. This waiting time depends on the distance between the node and the sender; as such, the waiting time is shorter for a more distant receiver. The node will rebroadcast the packet if the waiting time expires and the node did not receive the same packet from another node. Otherwise, the packet will be discarded. 2.2
Geocast Protocols to Increase the Dissemination Reliability
One of the main problems associated with geocast routing protocols is that they do not guarantee reliability, which means not all nodes inside a geographic area can be reached. Simple flooding forwarding can achieve a high delivery success ratio because it has high transmission redundancy. However, the delivery ratio will be worse with increased network size. Also, frequent broadcast in simple flooding causes message overhead and collisions. To limit the inefficiency of the simple flooding approach, directed flooding approaches have been proposed by defining a forwarding zone and applying a controlled packet retransmission scheme within the dissemination area. Location Based Multicast (LBM) protocols are based on flooding by defining a forwarding zone [7]. Emergency Message Dissemination for Vehicular environment (EMDV) protocol requires the forwarding zone to be shorter than the communication range and to lie in the direction of dissemination [8]. A retransmission counter (RC) is proposed as a packet retransmission scheme [8]. When nodes receive a packet, they cache it, increment the RC and start a timer.
30
M. Alsabaan et al.
The packet will be rebroadcast if the time is expired. Moreover, the packet will be discarded if the RC reaches a threshold. For small networks, temporary caching can potentially increase the reliability [9]. 2.3
Geocast Protocols Aim to Reduce Vehicle CO2 Emissions
To the best of our knowledge, all existing protocols focus on improving the network-centric performance measures (e.g., message delay, packet delivery ratio) instead of improving the performance metrics that are meaningful to both the scientific community and the general public (e.g., CO2 emissions). The key performance metrics of this paper are vehicle CO2 emissions. This metric can be called an EF metric. Improving the network metrics will improve the EF metric. However, the existing protocols are not EF because their delivery approach and provided information are not designed to assist drivers in reducing EUF actions. In [10,11], we have studied how vehicular networks can be used to reduce fuel consumption and CO2 emission in a city and a highway environment. However, we have not designed a geocast protocol that is suitable in applications such as reducing vehicle fuel consumption and CO2 emissions. To the best of our knowledge, our attempt is a first in the field.
3
System Model
Street segments with length L and N -lanes have been considered. At the intersections, there is TLS as shown in Fig.3. For simplicity, we consider a pre-timed TLS system. However, our work can be applied to dynamic TLS systems [12]. The free-flow speed of the street is SF m/s. The nodes in the road network are (1) Mobile nodes: vehicles; (2) Fixed nodes: TLSs. Wireless communications consist of vehicle to vehicle communication and vehicle to TLS communication. Therefore, we assume that the TLSs and vehicles are equipped with an OnBoard Unit (OBU), an entity responsible for vehicular communication such as wireless radio access, geographical ad hoc routing, network congestion control, etc. We also assume that the OBU is equipped with a (short range) wireless communication device. In addition to the OBU, vehicles are equipped with an Application Unit (AU), an entity that runs applications. It is assumed in this study that the AU is equipped with position data and an electronic road map. Therefore, the vehicles know their locations and the location of the TLS. Vehicles exchange (x, y) coordinates periodically. An ideal Medium Access Control (MAC) layer and Physical (PHY) layer are assumed. For simplicity, we make several assumptions such as vehicles approaching the intersection are not affected by an adjacent intersection, the communication range of the TLS can cover a Region of Interest (to be discussed), no lane change is considered, vehicles do not exceed the road speed limit, and they do not pass through a red TLS. Vehicles enter the system as a Poisson process with a rate of λ vph/lane. The mobility of the vehicles is based on the car-following concept [13]. To present the car-following behavior, we use a well known model named INTEGRATION
Geocast Routing in Vehicular Networks for Reduction of CO2 Emissions
31
Fig. 3. System model
[14]. The movements of the vehicles are adapted according to the space headway. Vehicles travel at the free flow speed. When the space headway of a vehicle and a vehicle driving ahead of it, or the space headway of a vehicle and a red or yellow TLS, reaches the minimum safe space headway (hmin ), the vehicle following has to be decelerated. hmin can be calculated as the average speed of the leading vehicle and the following vehicle multiplied by the time the following vehicle has to comfortably decelerate from its current speed to the speed of the vehicle in front of it. The calculation can be represented in the following equation [14]: Sf + Sl Sf − Sl )·( ) (1) 2 δ where Sf and Sl represent the speed of the following and leading vehicles, respectively and δ is the maximum comfortable deceleration rate. The following vehicle would accelerate if the leading vehicle were accelerating. The acceleration rate is governed by vehicle dynamics. A vehicle wanting to increase its speed will attempt to accelerate at the maximum possible rate [14]. hmin = (
4
Proposed Environmentally Friendly Geocast Protocol
The steps of designing our EFG protocol can be summarized as follows: (1) Define the Region of Interest (ROI) based on whether a vehicle will benefit from the information or not; (2) Specify what types of information a packet has to contain; (3) Deliver a packet with required information from to wanted vehicles; (4) Utilize the idea of VANETs; (5) Calculate the recommended speed based on the objectives; (6) Notify the TLS to retransmit if the network is disconnected; (7) Integrate an emission model with vehicular networks. As a result, the amount of CO2 emissions can be calculated. 4.1
Defining the Geocast Destination Regions or ROI
ROIs are defined to be the regions where the TLS information is necessary for vehicles in that regions to adjust their speed to SR . Vehicles calculate SR for drivers to avoid stopping at the TLS. Figure 4 shows what the SR will be when the current phase is green and red (or yellow).
32
M. Alsabaan et al.
Fig. 4. SR when the current phase is green, red, or yellow
Assuming that vehicles that do not receive a packet travel at SF , it is not necessary to geocast in a region where SR = SF . Thus, the geocast destination regions are the regions where SR < SF . For vehicles with SR < SF , their distances (d) to the TLS are in the following range: If the Current Phase is Green (Lg + (n − 1) · CL ) · SF < d < (Lg + Ty + Tr + (n − 1) · CL ) · SF where Lg is The number of seconds to switch from green to yellow, CL is the TLS cycle length (s), Ty and Tr represent the full yellow and red phase time, respectively. n = 1, 2, 3, ..., i. n is the region ID number, and i is the last region number. Defining i depends on the distance between a TLS and its preceding d −L ·S one (ds ) such as i = sCL ·Sg F F . The center of each ROI is as follows: Cen(ROIn ) =
SF · (Ty + Tr ) + (Lg + (n − 1) · CL ) · SF 2
(2)
where Cen(ROIn ) is defined as the distance between the TLS and the center of ROIn . In Fig. 5, if TLS 1 is inside ROIi , the center and diameter of ROIi will be as follows: Cen(ROIi ) =
ds − (Lg + (i − 1) · CL ) · SF + (Lg + (i − 1) · CL ) · SF 2
(3)
Dia(ROIi ) = ds − (Lg + (i − 1) · CL ) · SF
(4)
If The Current Phase is Red 0 < d < Lr · SF
,or (Lr + Tg + (n − 1) · CL ) · SF < d < (Lr + n · CL ) · SF
d −(L +T )·S
where i = s CLr ·SFg F + 1, Lr is The number of seconds to switch from red to green, and Tg is the green phase time. Cen(ROI1 ) = Cen(ROIn+1 ) =
(Ty +Tr )·SF 2
Lr · SF 2
+ (Lr + Tg + n · CL ) · SF
(5) (6)
Geocast Routing in Vehicular Networks for Reduction of CO2 Emissions
33
As shown in Fig. 5, if TLS 1 is inside ROIi , the center of ROIi will be as follows: When i = 1, Cen(ROI1 ) = d2s and Dia(ROI1 ) = ds ; otherwise, Cen(ROIi ) =
ds − (Lr + Tg + (i − 1) · CL ) · SF +(Lr +Tg +(i−1)·CL )·SF (7) 2 Dia(ROIi ) = ds − (Lr + Tg + (i − 1) · CL ) · SF
(8)
If The Current Phase is Yellow 0 < d < (Ly +Tr )·SF
,or (Ly +Tr +Tg +(n−1)·CL )·SF < d < (Ly +Tr +n·CL )·SF
Cen(ROI1 ) = Cen(ROIn+1 ) =
(Ly + Tr ) · SF 2
(Ty + Tr ) · SF + (Ly + Tr + Tg + n · CL ) · SF 2
(9) (10)
d −(L +T +T )·S
y r g F where i = s + 1 and Ly is The number of seconds to switch CL ·SF from yellow to red. As in Fig. 5, if TLS 1 is inside ROIi , the center of ROIi will be as follows: When i = 1, Cen(ROI1 ) = d2s and Dia(ROI1 ) = ds ; otherwise,
Cen(ROIi ) =
ds − (Ly + Tr + Tg + (i − 1) · CL ) · SF + (Ly + Tr + Tg + (i − 1) · CL ) · SF 2
Dia(ROIi ) = ds − (Ly + Tr + Tg + (i − 1) · CL ) · SF
(11)
(12)
In all the green, red, and yellow, the diameters of the destination regions are fixed to SF · (Ty + Tr ), while the centers of the regions are based on Lg , Ly , or Lr . Figure 6 shows the impact of Lg on ROIs.
Fig. 5. Two consecutive TLSs
Fig. 6. Distances between ROI and a TLS when the current phase is green
34
4.2
M. Alsabaan et al.
Message Delivery
The TLS uses a geocast routing protocol to deliver the message to the destination region. Preliminarily, in this paper, we assume that the distance from the previous TLS to the heading one covers only one ROI. Therefore, the proposed protocol is for delivering the message to the approaching vehicles inside ROI1 . The message delivery consists of three parts: (1) From a TLS to vehicles; (2) Inter-vehicle communication; (3) From vehicles to a TLS. 4.3
From a TLS to Vehicles
When a TLS starts to be green, it geomulticasts a packet to the first vehicle in each lane inside ROI1 . A geomulticast sends a packet to a group (not all) of nodes (vehicles) in a geographical area. The geomulticast packet contains four types of information: (1) The type of the current phase, which is green in this situation; (2) The number of seconds to switch from the current phase; (3) The traffic light schedule (Tg , Ty , and Tr ); (4) The geographical address of the first vehicle in each lane inside the ROI1 . Since a TLS communication range covers ROI1 , it can sense (x, y) coordinates from vehicles inside its coverage. Therefore, a TLS can know the position of the first vehicle inside ROI1 in each lane, where ROI1 can be calculated from Eq. 2 and Fig. 6 as follows: Center(ROI1 ) =
SF · (Ty + Tr ) + Lg · SF 2
Diameter(ROI1 ) = SF · (Ty + Tr ) Three conditions must be satisfied for a vehicle to be a destination of a TLS: (1) A vehicle is inside ROI1 ; (2) A vehicle is the first vehicle in its lane inside ROI1 ; (3) A vehicle has not received a packet yet. A vehicle discards the packet if the three conditions are not satisfied. Otherwise, the vehicle calculates and adjusts its speed to SR , which is calculated as the distance between the vehicle and the TLS after receiving the packet (d) over the required delay of the vehicle to be able to pass the TLS as in the following equation: SR = max(
d , SRmin ) (Ng − 1) · CL + Lg + Ty + Tr + M
(13)
|d/S −L |
F g where Ng = max( , 1) and CL = Tg + Ty + Tr . CL In another situation, if it is assumed that the TLS geomulticasts a packet when it starts to be red, the calculation of SR is as follows:
SR = max(
d , SRmin ) (Nr − 1) · CL + Lr + M − D
where Nr = max( |d/SCFL−Lr | , 1).
(14)
Geocast Routing in Vehicular Networks for Reduction of CO2 Emissions
35
In addition, the following equation shows the calculation of SR if it is assumed that the TLS geomulticasts a packet when it starts to be yellow. SR = max(
d , SRmin ) (Ny − 1) · CL + Ly + Tr + M − D
(15)
|d/S −L −T |
F y r where Ny = max( , 1), , SRmin is the minimum recommended or CL acceptable speed (m/s). Ng , Nr , and Ny represent the number of light cycles completed before the vehicle can pass the TLS when the current phase is green, red, and yellow, respectively. D is the packet delay (s), defined as the difference of the time of receiving the packet and the time of initiating the packet from the TLS. M is the time the vehicle has to comfortably decelerate from its current speed to the recommended speed.
4.4
Inter-vehicle Communication
After the first vehicle in each lane receives a message from the TLS, calculates, and adjusts its speed at SR , it unicasts a packet to the vehicle behind it (following) on the same lane its SR , stopping time at the TLS, The geographical address of the following vehicle, and the traffic light schedule. When the following vehicle receives the message, it calculates and adjusts its speed to the speed that makes the minimum headway when the leading vehicle reaches the TLS. In other words, it calculates and adjusts its speed to the maximum speed that the following vehicle can achieve without being affected by the leading vehicle. First, we want to determine whether the leading vehicle will stop or not. This can be done by calculating the stopping time (TSl ) as the difference of the required delay of the vehicle to be able to pass the TLS and the time of the leading vehicle to reach the TLS if it traveles at SR as follows: TSl = (Ng − 1) · CL + Lg + Ty + Tr + M − D −
d SRl
(16)
If 0 ≥ TSl ≥ −(Tg + Ty ), it means the vehicle will not stop at the TLS. In this case, the recommended speed of the following vehicle is SRf = min(max(SRl + S +S
df l − hmin , SRmin ), SF ) Tl + M
S −S
(17)
l where Tl = SdRl , hmin = ( f 2 Rl )·( f δ Rl ), d is the distance between the vehicle and the TLS after receiving the packet (m) and adjusting the speed to SRl , df l is the distance b/w the following and the leading vehicle (m), Tl is the time a leading vehicle needs to reach the TLS (s), dl is the distance between the leading vehicle and the TLS at the time the vehicle sent the packet. The leading vehicle will stop at the TLS if the above condition is not satisfied. In this case, when a following vehicle receives a packet, it determines whether it is traveling at the same speed as the leading vehicle (SRl ), whether it is going to
36
M. Alsabaan et al. d
fl pass the TLS without stopping (Is SRl > TSl )? If yes, the recommended speed of the following vehicle is calculated as
SRf = min(max(
df l − hmin , SRmin ), SF ) TSl + M
Otherwise, SRf = SRmin
(18) (19)
If SRf < SF , it means that the following vehicle is inside the ROI. Therefore, the unicast approach is repeated to the vehicle behind it. If SRf = SF , it means that the following vehicle is out of the ROI. Some remarks are (1) Vehicles know that they are out of ROI when SR = SF ; (2) Vehicles whose SR has been calculated and utilized are inside the ROI, so ROIs are moving with the vehicles; (3) A ROI is extended until SRf = SF . 4.5
From Vehicles to a TLS
When a vehicle receives a packet, it advises the driver to travel at EF speed. After adjusting the speed to be an EF, the vehicle unicasts the packet to its following vehicle if it is inside the transmission range. Otherwise, the packet has to be buffered until the following vehicle enters the transmission range. However, in a very low traffic where a vehicle might reach a TLS while it still has the packet, the vehicle notifies the TLS. As a result, the TLS geomulticasts a new packet as explained in Subsection 4.3. A flowchart represents a summary of the proposed protocol is in Fig. 7.
Fig. 7. Flowchart for the EFG protocol
Geocast Routing in Vehicular Networks for Reduction of CO2 Emissions
5
37
Simulation Study and Discussions
The simulation traffic model is shown in Fig. 8. The street has 2-lane and is in one direction. The rest of the simulation parameters are specified in Table 1.
Fig. 8. Traffic model Table 1. Simulation Parameters SF SRmin CL Tg
60 km/h 40 km/h 100 s 45 s
Ty Tr λ δ
5s 50 s 200 vph/lane -5 kph/s
The proposed EFG protocol has been evaluated based on an environmentally friendly metric (CO2 emissions). The protocol has been compared with the case where no vehicular network is applied. Moreover, The impact of communication metrics such as message delay and delivery ratio on the reduction of CO2 emissions is presented. The average CO2 emissions from vehicles traveling from O to D has been computed with different vehicles’ transmission ranges. Figure 9 shows the benefit of the EFG protocol on the environment. With no EFG, the amount of CO2 emissions is independent of the vehicles’ transmission range since no communication occurs. Zero transmission range means there is no vehicle-to-vehicle communications. However, vehicles receive packets from the TLS. As the vehicles’ transmission range increases, vehicles receive a packet early. Also, the chance of packet delivery increases. These advantages help drivers to avoid the UEF actions. As a result, the amount CO2 emissions decreases with increasing the vehicles’ transmission range as shown in Fig. 9. Since vehicles enter the system as a Poisson distribution with λ = 200 vph/lane at speed 60 km/h, the average space headway between vehicles is 300 m. The network becomes connected all the time when the transmission range is greater than or equal to every space headway between two successive vehicles. In this case, the space headway between vehicles is random. However, it can be noticed that the amount of CO2 emissions and fuel consumption start to reach the constant state after 300 m transmission range, which is equal to the average space headway between vehicles.
38
M. Alsabaan et al.
Fig. 9. Average vehicle CO2 emissions versus vehicles’ transmission range
Figure 10 shows how the EFG protocol can decrease vehicles’ stopping time. It is clear that in the absence of vehicular network, the average vehicle stopping time is around 12 seconds. This time would be shortened if the idea of vehicular networks is applied. It can be seen that with the EFG protocol, the vehicle stopping time can be decreased until 2.8 seconds with increasing vehicles’ transmission range.
Fig. 10. Average vehicle stops delay versus vehicles’ transmission range
It is clear that increasing vehicles’ transmission range contributes to reducing packet delay as shown in Figure 11. In fact, fast packet delivery enables earlier vehicles actions, thereby achieving greater reductions of CO2 emissions. It can be noticed from Figs. 9 and 11 that the amount of CO2 emissions are directly proportional to packet delay. Figure 12 demonstrates the ratio of cars that were supposed to receive a packet but did not due to the shortness in the vehicles’ transmission range. Similar to packet delay, this ratio is directly proportional to the amount of CO2 emissions. Therefore, it desirable to design a geocat protocol that has short packet delay and high packet delivery ratio for the reduction of CO2 emissions.
Geocast Routing in Vehicular Networks for Reduction of CO2 Emissions
39
Fig. 11. Average received packet delay versus vehicles’ transmission range
Fig. 12. Ratio of cars were not able to receive a packet
6
Conclusions and Future Work
This work has been inspired by the fact that, to date, rising CO2 emissions are increasingly recognized as global challenges. Geocast protocols in vehicular networks can play a key role in reducing vehicle CO2 emissions. The existing geocast protocols seek to improve mainly the performance of the communications systems; however, they do not show how improvements of the communication system would affect CO2 emissions. This work has proposed a new protocol that focuses on minimizing vehicle CO2 emissions. The goal of the protocol is to deliver the information of a TLS to approaching vehicles. Based on that information, vehicles can calculate the environmentally friendly speeds. These speeds are recommended to vehicles, in order to avoid having to stop, high accelerations, and useless high speeds. With increasing the vehicles’ transmission range, simulation results demonstrate how the performance improves in terms of vehicle CO2 emissions, stopping time, packet delay, and the ratio of vehicles that did not receive a packet, while they are inside the ROI. In the future, a protocol that considers the collaboration between adjacent TLSs will be proposed.
40
M. Alsabaan et al.
Acknowledgments. This research was supported by a research grant from the Natural Science and Engineering Research Council (NSERC) of Canada and by a scholarship from King Saud University, Saudi Arabia. The authors wish to thank Professor Hesham Rakha of Civil and Environmental Engineering at Virginia Tech for providing them a spreadsheet with the VTMicro model coefficients.
References 1. Tsugawa, S., Kato, S.: Energy ITS, another application of vehicular communications. IEEE Communications Magazine 6(11), 120–126 (2010) 2. Organization for Economic Co-operation and Development (OECD)/ International Energy Agency (IEA), CO2 Emissions from Fuel Combustion Highlights (2009) 3. Rakha, H., Ahn, K., Trani, A.: Comparison of MOBILESa, MOBILE6, VTMICRO, and CMEM Models for Estimating Hot-Stabilized Light-Duty Gasoline Vehicle Emissions. Canadian Journal of Civil Engineering 30, 1010–1021 (2003) 4. Maih¨ ofer, C.: A Survey of Geocast Routing Protocols. IEEE Communications Surveys and Tutorials 6(2), 32–42 (2004) 5. Karp, B., Kung, H.T.: GPSR: greedy perimeter stateless routing for wireless networks. In: Proc. MobiCom, pp. 243–254 (2000) 6. Briesemeister, L., Schafers, L., Hommel, G.: Disseminating messages among highly mobile hosts based on inter-vehicle communication. In: IEEE IV, pp. 522–527 (2000) 7. Ko, Y.B., Vaidya, N.H.: Location-Aided Routing (LAR) in mobile ad hoc networks. Wireless Networks 6(4), 307–321 (2000) 8. Moreno, M.T.: Inter-Vehicle Communications: Achieving Safety in a Distributed Wireless Environment: Challenges, Systems and Protocols. Dissertation, Universit¨ atsverlag Karlsruhe (2007); ISBN: 978-3-86644-175-0 9. Maihofer, C., Eberhardt, R.: Geocast in vehicular environments: caching and transmission range control for improved efficiency. In: IEEE IV, pp. 951–956 (2004) 10. Alsabaan, M., Naik, K., Nayak, A.: Applying vehicular ad hoc networks for re¨ duced vehicle fuel consumption. In: Ozcan, A., Chaki, N., Nagamalai, D. (eds.) WiMo 2010. Communications in Computer and Information Science, vol. 84, pp. 217–228. Springer, Heidelberg (2010) 11. Alsabaan, M., Naik, K., Khalifa, T., Nayak, A.: Vehicular Networks for Reduction of Fuel Consumption and CO2 Emission. In: IEEE INDIN, pp. 671–676 (2010) 12. Maslekar, N., Boussedjra, M.: VANET based Adaptive Traffic Signal Control. In: IEEE Vehicular Technology Conference (2011) 13. May, A.D.: Traffic flow fundamentals. Prentice-Hall, Englewood Cliffs (1990) 14. Van Aerde, M., and Associates, Ltd.: INTEGRATION release 2.30 for Windows: User’s Guide: Fundamental Model Features, vol. I & II (2005)
Limiting Pollution in Ground Control Optimization Ludovica Adacher1 and Marta Flamini2 1
Dipartimento di Informatica e Automazione, Universit´ a degli studi ”Roma Tre” 2 Universit´ a Telematica Internazionale UNINETTUNO Rome, Italy
[email protected],
[email protected]
Abstract. In this paper we deal with the problem of scheduling aircrafts maneuvering on ground in the specific case study of Malpensa Airport. Given a fixed route and a landing/take off time instant for each landing/departing aircraft, we consider three objective functions in the following lexicographical order: (i) the minimization of the number of tardy aircrafts; (ii) the maximization of the safety; (iii) the minimization of pollution and noise. Problem constraints are related to the safety rules. We model the problem as a job-shop scheduling problem. We develop heuristic procedures based on an alternative graph formulation of the problem to construct and improve feasible solutions. Experimental results based on real data and analysis are reported. Keywords: Air traffic control, Aircraft scheduling problem, Job-shop, Alternative Graph, Pollution.
1
Introduction
In the increase of air traffic, airports are becoming the major bottleneck in Air Traffic Control (AT C) operations. Aviation authorities are thus studying methods to optimize the use of the existing airport infrastructures and aircraft movements in the vicinity of airports, subject to a certain required level of safety. Airports management is entrusted to dispatchers in air control, local control and ground control. Air control tasks concern with routing decisions, where a route for each aircraft has to be chosen from its current position to its destination, and scheduling decisions in the vicinity of the airports, where routes are fixed and feasible aircrafts sequencing and timing have to be determined such that safety rules are satisfied. Local control is responsible of runways control and consists in sequencing and timing the use of the runway by the aircrafts. Ground control is responsible for aircraft traffic management in the Terminal Maneuvering Area (T M A), that generally includes all taxiways, runways, yards, aprons or intersections. Currently, human controllers perform AT C operations supported only by graphical representations of the aircrafts position and speed. Decision support systems would be useful both to optimize management performances and to face unexpected events without neglecting the optimization of traffic management even in such cases. Problems arising in AT C are usually hard to perform D. Kranzlm¨ uller and A M. Tjoa (Eds.): ICT-GLOW 2011, LNCS 6868, pp. 41–55, 2011. c Springer-Verlag Berlin Heidelberg 2011
42
L. Adacher and M. Flamini
in terms of both designing adequate models and projecting efficient and effective solution techniques, due to the complex real aspects that have to be included in the model representation in order to produce solutions that can be practically implemented. Several approaches have been proposed for solving both air and ground scheduling problems ([1], [2], [3]), but most of the early contributions suffer for a substantial lack of information due to the usage of very simplified models. Recent models ([4]) introduce an increased level of realism and incorporate a larger variety of constraints and possibilities, such as no-wait constraints, and earliness/tardiness penalties for each early/tardy aircraft. Most of the research efforts focus on local control ([5], [6] , [7]) where runway scheduling problems are analyzed. Due to the complexity of such problems researchers often propose the developing of heuristic procedures. Bianco et al. [8] model the single runway landing problem as a job-shop scheduling problem and propose a solution based on a mixed integer linear programming formulation. In this paper, the main focus is on the real time local and ground Aircraft Scheduling Problem ASP with fixed routes. The case study we refer is related to the T M A of Malpensa Airport (from now on T M A). The T M A has a specific layout implying the traversing of one of the runways by most part of routes. For the safety problem of T M A it is important to develop a detailed model able to adequately represent all the safety constraints. The traversing of the runway is regulated by stop bars. Whenever an aircraft has to cross the runway while another aircraft occupies the runway, the first one has to wait at a stop bar. Here the spacial safety rules are less pressing, since a reduced distance between the aircrafts is allowed. In our problem we consider three objective functions in lexicographical order, namely (i) the minimization of the number of tardy aircrafts; (ii) the minimization of the mean waiting time at the stop bars close to one of the runways; (iii) the minimization of pollution and noise. The first objective function represents one of the most analyzed indices in literature, which gives a measure of the performance of the control operations. The second objective function concerns with the safety and aims to limit the event in which two aircrafts are physically close. Regarding to the third objective function, we associate the production of pollution and noise with the total time the aircrafts keep the engine on, therefore our aim is to minimize such total time. The constraints of the problem are given by the safety rules concerning the moving of the airplanes in the terminal. We consider the ASP as a job shop scheduling problem with additional constraints. We model the problem by an alternative graph [9] and we propose some heuristic procedures producing fast feasible solutions able to face the real time nature of the problem. The paper is organized as follows. In Section 2 reader can find the detailed description of the problem that is modeled as a job-shop scheduling problem with additional constrains. In Section 3 authors propose a model for the ASP based on the alternative graph formulation [9]. Solution heuristic procedures are described in Section 4 and experimental results are reported in Section 5. Section 6 is dedicated to the conclusions.
Limiting Pollution in Ground Control Optimization
2
43
Problem Description
The case study we deal with is related to an aircraft scheduling problem (ASP ) in the Terminal Maneuvering Area (T M A) of Malpensa Airport. A schema for the layout of the T M A is depicted in Figure 1. The T M A has two parallel runways, namely 35R and 35L, two yards, two aprons, and a taxiway network. The runways are divided into segments, each between two consecutive intersections with the taxiway network. Yards are areas positioned at the beginning of the runways, in which aircrafts wait before departing. Aprons include parking bays in which the aircrafts are parked. Stop bars regulate the access to the cross points. As depicted in Figure 1, runway 35L has to be crossed by aircrafts departing/landing on runway 35R and coming from/going to apron A1. This peculiarity of the T M A makes the safety a crucial aspect while modeling and optimizing problems related to the ground control. We consider both arriving and departing aircrafts, in a given time interval. Each arriving aircraft has associated a fixed ground route from its current position to the parking bay and each departing aircraft has associated a fixed ground route from its current position to the runway. We are given a nominal landing time and an arrival time for the arriving aircrafts. The nominal landing time is the minimum time instant in which the aircraft would be able to land. The landing time is a variable of the problem, since in practice the landing instant could be postponed for optimization scopes. The arrival time represents the time instant in which the aircraft should reach the parking bay. For each departing aircraft we are given a departing time that is the time instant in which the aircraft should take-off. The arrival times and departing times are considered as due dates for the aircrafts. Problem constraints are described in Section 6 and correspond to the safety rules regulating the movings of the aircrafts in the T M A. The problem briefly consists in scheduling the movings of the aircrafts through the T M A, in order to avoid deadlocks and collisions, subject to the safety constraints. We consider three objective functions in lexicographical order: (i) the minimization of the number of tardy aircrafts; (ii) the minimization of the mean waiting time at the stop bars close to runway 35L; (iii) the minimization of pollution and noise. The first objective function gives a measure of performance of the management and control operations. An aircraft is a tardy aircraft if its arrival or departing time does exceeds its due date. When evaluating the quality of a solution we are also interested in considering some other performance indices, such that then average tardiness and absolute average lateness. The second objective function concerns with the safety and aims to limit the event in which two aircrafts are physically close, by minimizing the mean waiting time at the stop bars regulating the crossing of the runway 35L. The third objective function is evaluated by associating the production of pollution and noise with the total time the aircrafts keep the engine on, therefore our aim is to minimize such total time.
44
L. Adacher and M. Flamini
Fig. 1. Resources of the T M A
2.1
Problem Constraints
ASP can be modeled as a job-shop scheduling problem with additional constraints. Jobs are represented by aircrafts and resources by parts of the T M A. An operation is the occupation of a resource by an aircraft, therefore the processing time of an operation corresponds to the time necessary to run/occupy a certain resource. Constraints implied by safety rules, typically regulating spatial or temporal security distances, hold for each pair of aircrafts moving in the T M A. We model the T M A as a set of resources of limited capacity. The resources we consider are runway segments, taxiway segments, parking bays, stop bars, yards. All such resources but the yards have unitary capacity. Yards are assumed to have unlimited capacity. Each route associated to an aircraft corresponds to a list of resources. Standard job-shop constraints hold, namely: (i) precedence constraints: resources composing a routes have to be run in a precise order; (ii) capacity constraints: resources with unary capacity can be occupied at most by an aircraft at a time; (iii) preemption constraints: operations can not be interrupted. Additional constraints, that is no-wait, blocking and incompatibility constraints, are introduced to model real aspects of the problem related to the safety rules. No-wait constrains state that a given set of consecutive resources in a route has to be occupied without interruption. This is the case, for instance, of segments composing a runway. Blocking constraints model the absence of buffer between two resources, therefore the occupation of a resource of unary capacity by an aircraft makes such resource unavailable for other aircrafts for the entire occupation time interval. Incompatibility constraints hold when two different resources can not be occupied at the same time. In this case the two resources are said incompatible. For instance, all the segments of a runway can be occupied only by an aircraft at a time. This make each pair of segments of the same runway incompatible. A conflict arises when two aircrafts have to
Limiting Pollution in Ground Control Optimization
45
run the same resource or two incompatible resources at the same time. A conflict is solved by fixing a precedence between the two aircrafts. Therefore, a feasible solution for ASP consists in solving all the conflicts among aircrafts, avoiding deadlocks. ASP , as the majority of the problems belonging to the class of jobshop scheduling problems, is hard to resolve. Our aim is both to design a valid model, representative of most of the practical aspects and to develop fast heuristic algorithms, based on such model, in order to face the real time nature of the problem.
3
The Alternative Graph Model
In this section we describe a graph model to represent ASP as a job-shop scheduling problem with additional constraints. We model ASP by the alternative graph formulation [9], that is a generalization of the disjunctive graph, proposed by Roy and Sussman in [10] to represent the standard job-shop scheduling problem. The alternative graph is an effective model for representing complex scheduling problems arising in several sectors, such as in manufacturing [11] or in railway traffic control [12]. In our problem the route of an aircraft corresponds to the running of an ordered list of resources, which can be represented by a sequence of operations. An alternative graph is an oriented graph G(N, F, A), in which N denotes the set of nodes, F is the set of fixed arcs and A is the set of alternative arcs. We denote by R the set of problem resources, reported in Figure 1: - runways intersections {35R0, 35R1, . . . , 35R5} for runway 35R and {35L1, . . . , 35L6} for runway 35L; - taxiway cross points {X0, X1, C0, . . . , C10, W0, . . . , W7, K0, . . . , K7}; - parking bays {P0, P1, . . . , P7}; - stop bars {sb1, sb2, . . . , sb10}. Let nji ∈ N be the node associated to the occupancy of resource i ∈ R by aircraft j. For sake of simplicity we use the notation nji , both to denote a node of the alternative graph and the associated operation. Set N includes two dummy nodes, s and t associated to time zero and to the completion of the last operation, respectively. A fixed arc (nji , njk ) ∈ F , between two consecutive nodes in an aircraft route represents the precedence constraint that aircraft j cannot start operation njk before it completes operation nji . The arc weight pji indicates the processing time of operation nji , that is equal to the minimum occupation time of the resource i. The minimum occupation time for a runway intersection is equal to the running time of the runway segment succeeding the intersection. The minimum occupation time for a taxiway cross point is equal to the running time of the taxiway succeeding the cross point. The minimum occupation time for stop bars and parking bays is fixed to zero. Example 1. We are given one landing aircraft a and one departing aircraft b. Routes are Ra = {35R5, 35R4, 35R3, sb7, C1, sb2, 35L2, W 0, K1, P 1} and Rb = {P 2, W 1, W 0, sb9, 35L3, C1, C2, C3, C4, C5, C8, 35R5, . . ., 35R0} for a and b respectively. In Figure 2 the two routes are depicted as chains including fixed arcs. For sake of simplicity, we label the nodes only with the name of the resources.
46
L. Adacher and M. Flamini
Fig. 2. Example for fixed arcs of the alternative graph model for two aircrafts
A conflict occurs each time two aircrafts have to occupy the same resource or two incompatible resources. Two resources are defined incompatible if they can not be occupied at the same time due to safety rules. Each conflict is modeled by an alternative pair that is composed by two alternative arcs. An alternative pair models the two possible precedences between aircrafts involved in the conflict. Conflict arcs have a weight equal to ε → 0. A feasible solution S for ASP consists in solving all possible conflicts among aircrafts, avoiding deadlocks. In terms of alternative graph, it corresponds to construct an acyclic graph by selecting exactly one arc for each alternative pair. Such graph is called precedence graph. The head of a node nji ∈ N is denoted by hji and is equal to the length of the longest path from the dummy node s to node nji . It represents the earliest starting time of operation nji in the feasible solution, i.e. the earliest starting time in which the aircraft j can enter resource i. A simple forward visit of the precedence graph allows to compute the head of each node. The waiting time of an aircraft at a specific resource is computed by considering the heads of the nodes. In the Example 1 a conflict occurs in the occupation of resource W 0. In Figure 3 the alternative pair modeling the two possible precedences is represented by the unbroken and dotted arcs between the two chains. One of the feasible solutions for the Example 1 consists in selecting the unbroken arc (naK1 , nbW 0 ) and canceling the dotted arc (nbsb9 , naW 0 ). In such feasible solution aircraft a precedes b in the of resource W 0. The head of node nbW 0 b occupation b b a + p is equal to hW 0 = max hW 1 W 1 , hK1 + ε. The waiting time of aircraft b at W 1 is equal to the difference between hbW 0 and hbW 1 + pbW 1 that is the time instant in which b arrives in W 1 plus the running time from W 1 to W 0. In order to compute the value of a feasible solution S associated to a certain precedence graph, we denote by: - ND ⊂ N the set of nodes representing the occupation of the parking bays or of the first segment of the take-off runway by the aircrafts. - NSB ⊂ N the set of nodes representing the occupation of the stop bars adjacent to the runway 35L by the aircrafts. - NP ⊂ N the set of nodes representing the occupation of resources in which aircrafts could wait in order to give precedence to other aircrafts. The number of tardy aircrafts derives by the tardiness values. Let Tj the tardiness associated to aircraft j, it is computed as Tj = max{0, hji − ddj } where i ∈ ND and ddj is the due date of aircraft j. The formulation of the second and third objective functions is the following:
Limiting Pollution in Ground Control Optimization
47
Fig. 3. Example for the alternative graph model for two conflicting aircrafts
- min -
K
j=1 K min j=1
j j j i∈NSB (hσ(i) − (hi + pi )); j j j i∈NP (hσ(i) − (hi + pi ));
where K is the total number of aircrafts and σ(i) is the resource succeeding the resource i in the route associated to an aircraft. 3.1
Conflicts Models
In the following we illustrate the alternative graph model for some typical conflicts arising in ASP . Conflict on a unary capacity resource. Each resource but the yards can host at most one aircraft at a time. Let i the requested resource and {nai , nak } and {nbi , nbz } the partial routes associated to aircrafts a and b. The conflict on resource i is modeled by inserting the alternative pair < (nak , nbi ), (nbz , nai ) >. The first arc models the precedence of a over b and implies that aircraft b can not reach resource i before aircraft a is not in resource k. The second one models the precedence of b over a and implies that aircraft a can not reach resource i before aircraft b is not in resource z. Runway conflict. Each runway can host only one aircraft at the time, that is each pair of runway segments are incompatible. We model the incompatibility among the runway segments with a conflict pair for each pair of aircrafts requesting the runway. Let {nai , nal , . . . , nak } and {nbi , nal , . . . , nbz } be the partial routes representing the occupation of a runway by aircraft a and aircraft b, respectively. Let x and y be the first resources occupied by a and b after the occupation resources k and z, respectively. The conflict on the runway is modeled as depicted in Figure 4: if a precedes b, b can start the runway operations only once a is in x, that is when a has completely left the runway. The precedence of a over b is modeled by the alternative arc (nax , nbi ). Similarly, if b precedes a, we introduce the alternative arc (nby , nai ). Furthermore, no-wait constraints subsist among runway segments, that is runway segments have to be occupied consecutively without interruption. Hence a coherent model forbids arcs ending in one of the nodes between nal and nak for aircraft a and nal and nbz for aircraft b. Incompatibility between two sets of resources. The definition of incompatibility can be extended to sets of resources representing the same path run in opposite directions. The two sets of resources are incompatible since they can not be occupied at the same time (this could cause a deadlock). Let be Sa = {nai , nal , . . . , nam }
48
L. Adacher and M. Flamini
Fig. 4. Conflict on an unary capacity or runway
Fig. 5. Incompatibility arcs for conflict on sets of resources
and Sb = {nbm , nbg , . . . , nbi } two incompatible sets of resources representing partial routes of aircrafts a and b. The incompatibility between the two sets can be modeled by inserting the alternative pair < (nbk , nai ), (naz , nbm ) >, where k and z, k = z, are the resources succeeding the last resources of Sa and Sb , respectively (see figure 5(a)). This is the case of two aircrafts a and b running Sa = {C9, sb6, 35L4, W 4} and Sb = {W 4, sb4, 35L4, C9}, respectively. The sets of resources occupied by a and b are not identical since a considers sb6 and b considers sb4, but they represent the same physical path. In this example k = K5 and z = C4. The incompatibility between Sa and Sb can be modeled by introducing only one alternative pair, namely < (naK5 , nbW 4 ), (nbC4 , naC9) > (see figure 5(b)).
4
Heuristics
Due to the real nature of the problem we first compute different fast initial solutions, then we try to improve the quality by applying local search heuristics based on the alternative graph AG representation. Any potential conflict on
Limiting Pollution in Ground Control Optimization
49
resources between landing and departing aircrafts must be detected and solved. We consider a list of real dispatching criteria to assign the precedences (see Fig.6) to find a feasible solution. List of real criteria LP – criterion 0 : when we consider to different landing (departing) airplanes we select in AG the arc of the alternative pair on the basis of FIFO order. – criterion 1 : in runway, when we consider a landing and a departing aircraft, we always select the arc that gives the precedence to the landing airplane. – criterion 2 : in taxiway, stop bar, parking bay, when we consider a landing aircraft and a departing aircraft we always select the arc that gives the precedence at the departing aircraft.
Fig. 6. List of precedence LP
The Arc Greedy Heuristic (AGH) is based on an iterative arc selection procedure. At each step, AGH selects all the alternative arcs involving a chosen aircraft, so that the sequencing of the operations of this aircraft with respect to the others is fixed. Note that at each step the relative order of remaining aircrafts with respect to previously selected aircrafts is already fixed, so that it only remains to decide the relative order of unselected aircrafts. Once ordered all the aircrafts according to the F IF O rule with respect to nominal landing/departing time, the precedence between two consecutive landing (departing) aircrafts is given on F IF O rule. If a conflict occurs in the runway a landing aircraft always precedes a departing aircraft and if occurs in taxiway, stop bars, parking bays, a departing aircraft precedes a landing one. We also implement the EDD rule, instead F IF O, for the arc selection. The EDD rule solves aircraft conflict situations by assigning each conflicting resource to the aircraft whit minimum due date. We apply the EDD rule to optimize the first objective function, the other two types of criteria represent safety constrains. The AGH based on F IF O rule represents a good estimation of the solution currently produced by controllers in terms of both safety and quality. Note that the AGH based on EDD is implemented to reduce the number of tardy aircrafts since the precedence is given first to the aircraft with the most pressing due date. Once a feasible solution x has been constructed, it is modeled by the alternative graph and local search procedures are applied. The alternative graph, is a useful tool to rapidly estimate the effect produced by modifying the structure of a solution. The Local Greedy Heuristic (LGH) is a family of heuristic algorithms (see Fig 7). The family is based on the idea of repeatedly choose an arc at a time from set A and select the other arc of the alternative pair until an improvement is found. The exchange is not accepted if a cycle is detected or the solution does not improve. At each step the arc is selected in an ordered list S constructed on a local rule (LR). Every time an improvement is obtained the list S and
50
L. Adacher and M. Flamini
the solution x are updated. The LGH considers only the first objective function (minimization of tardy aircrafts) but we can notice that even early flights could cause coordination discomforts in the T M A management. Obviously, a tardy aircraft causes major costs with respect to an early aircraft, but we are also interested in maximizing the number of on time aircrafts (neither tardy, noor early). Hence, we implement two different local rules LR, one to improve the number of tardy aircrafts and the other to optimize the number of on time aircrafts. Local Greedy Heuristic Input: Alternative graph G = (N, F, A) given a feasible solution x from AGH S : set of selected alternative arcs constructed on the basis of a local rule (LR) begin while S = ∅ do an arc (u, v) ∈ A is select on the basis of LR(·) A := A − {(u, v)} + {(v, u)} if G(A) , x’ is not improved solution then A := A + {(u, v)} − {(v, u)} else x = x’ and update S end end. Fig. 7. LGH algorithm
The basic idea is to try and iteratively invert precedences between two aircrafts. After each inversion a forward visit of the graph detects the acyclicity of the graph and updates the nodes heads. An inversion is accepted only if the new solution is feasible and improves. The heuristics in the LGH family differ from each other for the evaluation criterion applied to choose the arc from A. Given a feasible solution from AGH, we calculate the lateness for each aircraft, comparing the due date with the heads of nodes representing (i) the arrival to the parking bay for the arriving aircrafts, and (ii) the arrival to the first segment of runway for departing aircrafts. Naturally, if the lateness is negative we have an early aircraft, if it is positive we have a tardy aircraft and if it is equal to zero we have an on time aircraft. Note that it is impossible to meet exactly the due date, for this reason we have introduced a time interval for each aircraft in which it is considered on time. On the other hand, this really small interval is trivial respect to the whole flight. Obviously, the LGH inverts precedence between aircrafts if and only if an early aircraft precedes a tardy aircraft, otherwise it is not possible to improve the solution. In fact, we can improve the first objective function only if we delay an early aircraft or if anticipate a tardy aircraft. We develop two heuristic procedures based on two different LR: mM L (maximum lateness-minimum lateness) heuristic inverts precedence between the aircraft with the minimum absolute value of lateness preceding the
Limiting Pollution in Ground Control Optimization
51
aircraft with the maximum absolute value of lateness, to reduce the number of tardy aircrafts; ET (earliness-tardiness) heuristic inverts precedence between the aircraft with minimum earliness preceding the aircraft with maximum tardiness, to improve the number of on time aircrafts. In practice, M mL detects the aircraft aM with maximum absolute value of lateness and the aircraft am with minimum absolute value of lateness; if there exists an arc from aM to am then M mL selects the other arc of the alternative pair. If this exchange does not improve the solution, or a positive length cycle is detected, the M mL heuristic continues with the second minimum and maximum absolute value of lateness and so on. Heuristic ET detects the aircraft with minimum earliness and the aircraft with maximum tardiness. If there exists the arc from early to tardy aircraft then ET selects the other arc of the alternative pair; if this exchange does not improve the solution, or a positive length cycle is detected, the ET continues with the second minimum early and the maximum tardy aircrafts, then with the third minimum early and so on. If the solution never improves ET heuristic tries with the aircraft with the second maximum tardiness and first minimum early aircraft then with the second minimum early aircraft and so on. These two types of exchange are done on the AGH feasible solution, when a change improvements the solution the LGH rules are applied on this new solution, and the scheme is repeated until a new improvement is found or a feasible solution does not exist. Given the LGH solution (calculated on the basis of ET /M mL heuristic) we try, only for the departing aircrafts, to anticipate to the parking bay the total waiting time (or a fraction of it) that an aircraft accumulates along the route (Safety-Pollution Heuristic SP H). We calculate the waiting time at the stop bars for departing aircrafts and we try to shift a fraction of such waiting time to the parking bay, utilizing the binary research. We start the research by transferring the total waiting time at the stop bar to the parking bay. If SP H does not find a feasible solution SP H we try with half waiting time, and so on. If a feasible solution is constructed SP H has reduced the total waiting time at the stop bars, improving the safety, and, at the same time, it has increased the time with the engines turned off, reducing the pollution. This change on the waiting time with the engines turned off is approved only if the number of tardy aircrafts does not increase.
5
Computational Experiments
Experiments are carried out considering as a reference test case one busy hour of arrivals and departures at the Malpensa international airport. We have tested different instances (denoted as n m x t) based on four parameters (n,m,x,t ): – – – –
n: number of departures (n ∈ {4, 5, 6, 8, 10, 15}) m: number of arrivals (m ∈ {4, 5, 6, 8, 10, 15}) x: number consecutive arrivals/departures (x ∈ {2, 3, 4, 5, 6}) t: simulation constant (t ∈ {4, 5, 6, 8, 10, 12, 20})
52
L. Adacher and M. Flamini
The simulation constant t and the T M A average throughput time X define the simulation time interval T = t ∗ X. The routing problem is solved off-line in a preliminary step and the main focus is on real-time scheduling decisions with fixed routes (we have tested only real routing). In particular, we deal with the problem of scheduling airplanes moving on ground,with the objective of minimizing the number of tardy aircrafts (or of maximizing the number of on time aircrafts). In AGH the EDD rule gives better results in comparison to F IF O: if we consider the number of tardy aircrafts the EDD improvement is around 25%, while the average tardiness improves of 60%. If we consider the number on time aircrafts the improvement is obviously inferior and it is attested around 5%, and with respect to the average lateness it is equal to 30%. The main results are shown in the following tables, where only the EDD rule is considered. The ET heuristic (based on the exchange between tardy and early aircrafts) gives better improvement respected to the minimization of the number of tardy aircrafts, and the M mL heuristic (based on the exchange between maximum lateness and minimum of jobs) gives better improvement with respect to the maximization of on-time aircrafts. But the behavior of these two types of heuristic is more or less the same. Table 1. ET improvement related to the minimization of tardy aircrafts.The results are given in percentage. Class 4444 4448 5555 5 5 5 10 6446 4646 6666 6 6 6 12 8448 4848 10 5 5 8 5 10 5 8 10 5 3 8 5 10 3 8 10 10 5 10 10 10 5 20
# Tardy AGH 29 42 48 55 40 45 52 54 37 65 44 72 44 73 68 73
aircrafts Improvement Average ET Tardiness [%] 25 28 39 9 44 8 46 15 36 9 45 5 47 10 50 7 33 8 63 7 37 9 71 4 37 10 70 5 68 2 65 7
In Table 1 the improvement of ET compared to the found feasible solution by the AGH is reported. When the number of tardy aircrafts is the same there is an improvement of the average tardiness. The number of tardy aircraft is calculated in parentage considering the number of tardy aircrafts in the solution (AGH first column and ET second column) divided by the total number of aircrafts. The last column represents the improvement of average tardiness obtained applying
Limiting Pollution in Ground Control Optimization
53
Table 2. M mL improvement related to the maximization of the number of on time aircrafts. The results are given in percentage. Class 4444 4448 5555 5 5 5 10 6446 4646 6666 6 6 6 12 8448 4848 10 5 5 8 5 10 5 8 10 5 3 8 5 10 3 8 10 10 5 10 10 10 5 20
# On time aircrafts Improvement Average AGH M mL Lateness [%] 28 34 1 11 17 7 16 22 5 12 17 4 10 16 5 17 23 3 11 14 4 11 16 5 9 17 5 30 34 3 7 13 4 8 11 2 12 18 5 9 14 9 12 19 8 3 7 4
Table 3. Local search based on the waiting times imposed at the parking bay. The results are given in percentage. Class 4444 4448 5555 5 5 5 10 6446 4646 6666 6 6 6 12 8448 4848 10 5 5 8 5 10 5 8 10 5 3 8 5 10 3 8 10 10 5 10 10 10 5 20
On time aircrafts absolute lateness 0,8 0,8 2,5 0,8 4,2 2,0 2,3 3,1 3,8 0,6 6,0 2,1 5,0 1,0 0,0 0,0
1,9 4,1 -1,1 1,2 2,0 0,4 -1,3 1,1 1,3 1,1 2,6 -1,0 1,7 -2,1 0,2 0,0
Safety ET M mL 78 39 88 39 77 28 80 21 72 0 84 38 68 8 64 6 73 12 68 21 68 10 70 12 62 5 58 8 45 21 62 0
Pollution ET M mL 95 11 85 11 75 30 84 17 88 19 74 29 74 18 72 15 72 15 57 12 82 26 63 12 58 14 62 15 57 17 52 10
the ET heuristic. Note that in these tables we have only considered the AGH solution based on EDD rule that gives an improvement of 25% compared to AGH solution. In Table 2 the improvement of M mL compared to the AGH solution is reported. The first column reports the percentage of on time aircrafts for AGH
54
L. Adacher and M. Flamini
and the second for M mL. The last column represents the absolute lateness improvement due the local search. Given the LGH solution (calculated by ET /M mL rule) we try, only for the departing aircrafts, to transfer the waiting time from the stop bars to the parking bay (Safety Pollution Heuristic SP H). The results of SP H are reported in Table 3. When we consider tardy aircrafts, the SP H improves only the safety and the pollution. It is important to notice that the local search SP H produces an improvement of the safety at least of 50% in all cases, and for the pollution an average reduction of 20%. When we consider the on time aircrafts, the SP H produces an improvement of the safety at least of 45% in all the cases and for the pollution an average reduction of 15%, but it is also obtained a small improvement for on time aircrafts and absolute average lateness (see first and second column).
6
Conclusion
In this paper we introduced the alternative graph model for Aircraft Scheduling Problem in the Terminal Meneuvring Area of Malpensa airport. We show that even a simple greedy heuristic is able to reduce the number of tardy aircrafts (improve on time aircrafts) and the average delay (average absolute lateness) when compared to commonly adopted policies. We observe that an advanced real-time scheduling system may be useful to optimize the traffic conditions, improving the safety and the pollution on ground. We are investigating if changing the lexicographic order could lead to an improvement of the objective functions or of the performance indices. Other different policies will be considered to reduce the time with the engine on, for instance by transferring the waiting time from the taxyways to the parking bays.
References 1. Anagmostakis, I., Clarke, J., Bohme, D., Volckers, U.: Runway Operations Planning and control:Sequencing and Scheduling. Journal of Aircraft 38(6) (2001) 2. Beasley, J.E., Krishnamoorthy, M., Sharaiha, Y.M., Abramson, D.: Scheduling aircraft landings - the static case. Transportation Science 34, 180–197 (2000) 3. Bianco, L., Dell’Olmo, P., Giordani, S.: Scheduling models and algorithms for TMA traffic management. In: Bianco, L., et al. (eds.) Modelling and simulation in air traffic management, pp. 139–168. Springer, Heidelberg (1997) 4. Adacher, L., Pacciarelli, D., Paluzzi, D., Pranzo, M.: Scheduling arrivals and departures in a busy airport. In: Preprints of the 5th Triennial Symposium on Transportation Analysis, Le Gosier, Guadaloupe (2004) 5. Dear, R.G., Sherif, Y.S.: An algorithm for computer assisted sequencing and scheduling of terminal area operations. Transportation Research A 25, 129–139 (1991) 6. Neuman F., Erzberger.: Analysis of Sequencing and Scheduling Methods for Arrival Traffic. NASA Technical Memorandum 102795 (April 1990)
Limiting Pollution in Ground Control Optimization
55
7. Neuman F., Erzberger.: Analysis of Delay reducing and Fuel saving sequencing and spacing algorithms for arrival spacing. NASA Technical Memorandum 103880 (October 1991) 8. Bianco, L., Dell’Olmo, P., Giordani, S.: Aircraft Flow Scheduling in the Terminal Maneuvering Area. In: Proceedings of the Triennial Symposium on Transportation Analysis (TRISTAN IV), Sao Miguel, Portugal, pp. 281–286 (2001) 9. Mascis, A., Pacciarelli, D.: Job shop scheduling with blocking and no-wait constraints. European Journal of Operational Research 143(3), 498–517 (2002) 10. Roy B., Sussman B, Les probl`em d’ordonnancement avec contraintes disjonctives. Note DS No. 9bis, SEMA, Paris (1964) 11. Pacciarelli D., M. Pranzo, Production Scheduling in a Steelmaking-continuous Casting Plant, Report DIA-50-2000, Dipartimento di Informatica e Automazione, Universit` a Roma Tre, Roma, Italy (2000) 12. Mascis, A., Pacciarelli, D., Pranzo, M.: Train scheduling in regional railway networks. In: Proceedings of the Triennial Symposium on Transportation Analysis (TRISTAN IV), Sao Miguel, Portugal, pp. 487–492 (2001)
A Simulation Environment for Smart Charging of Electric Vehicles Using a Multi-objective Evolutionary Algorithm Maryam Ramezani, Mario Graf, and Harald Vogt SAP Research, Karlsruhe, Germany {maryam.ramezani,mario.graf,harald.vogt}@sap.com
Abstract. Integration of the electric vehicles (EV) into the power grid is one of the most important efforts to reduce CO2 emissions in the transport sector. Electric vehicles can put significant stress on sections of the distribution grid while charging. In order to maintain grid availability, it is essential that the individual charging schedules are aligned with each other such that the total load does not exceed the grid’s maximum capacity. In addition to this hard constraint, user preferences, constraints enforced by the battery, other grid loads, market prices, consumer tariffs, and possibly other factors have to be considered when creating charging schedules. In this paper, we present the design of a simulation environment, which produces charging schedules using a multi-objective, evolutionary optimization algorithm.
1
Introduction
In the last decades, due to emission reduction policies, researchers have focused on developing large-scale sustainable energy systems. Among those, researchers have studied approaches to support integration of electric vehicles (EV) into the power grid. The focus on EVs and the infrastructure to support them should also take into account renewable energy resources. Since today’s inexpensive and abundant renewable energy resources have fluctuating output, we must learn to maintain a balance between demand and supply. Previous studies on the impact of charging electric vehicles on distribution grids have shown that uncoordinated charging of the batteries can have considerable impact on the performance of the distribution grid in terms of power losses and power quality [1]. While electric vehicles (EVs) can be considered a challenge to the power grid’s stability, EVs can also be used as a means for balancing supply and demand, thus contributing to grid stability as well as price stability. For example, charging loads could be increased if cheap power is available. Also, power could be transferred back into the grid through vehicle-to-grid services (V2G) [2]. In addition to constraints and benefits associated with the grid, a smart charging infrastructure should take into account other constraints and goals. For example, constraints and requirements of the batteries, the preferences of the D. Kranzlm¨ uller and A M. Tjoa (Eds.): ICT-GLOW 2011, LNCS 6868, pp. 56–63, 2011. c Springer-Verlag Berlin Heidelberg 2011
A Simulation Environment for Smart Charging of Electric Vehicles
57
users, and the market players. In this paper, we propose an intelligent charging controller that employs a multi-objective evolutionary algorithm to derive an optimized schedule for charging of batteries based on several tunable objectives. This controller is embedded within a simulation environment that allows the exploration of different scheduling strategies. There are two basic scenarios for EV battery charging that largely determine the classes of scheduling strategies: public and private charging infrastructures. In the case of public charging, different public parkings such as shopping malls, train stations, airports, corporate parking, etc can offer charging . Our goal is to provide a solution that can provide an optimized charging schedule for different environments considering various constraints and requirements. Our solution is adaptable to different scenarios based on the requirements, preferences and objectives set by the charging service provider. For example, different public parkings have various expected parking durations. A shopping mall might have an average of 3-4 hours parking duration while the average parking duration for a corporate parking might be up to 8 hours and for a train station up to 10-12 hours. Moreover, the objectives of charging providers in each parking station might be quite different. A charging station in the shopping mall might only have the objective of maximizing profit by charging as many cars as possible, while the charging provider in a company might have the objective to minimize battery degradation of the company’s car fleet. On the other hand, a charging provider in a train station or airport might have the objective of using the electric cars as capacities for stabilizing the grid. In such a scenario, the charging provider might even provide the parking spot for free to vehicles that stay there for a long time and give the permission to use their batteries as capacities for vehicle to grid purposes. The contributions of this paper are two-fold. First, we present a simulation environment where different charging scenarios are defined and parameters are set. Second, we propose a multi-objective evolutionary algorithm for smart charging of electric vehicles. This paper is a preliminary presentation of our ongoing research and does not provide experimental results. The rest of this paper is organized as follows. We review the related work in section 2. Next, in section 3 we define the problem context in terms of the constraints, objectives, and fitness functions. Section 4 outlines the multi-objective, evolutionary optimization algorithm, and describes the simulation environment in which the optimization component is embedded. Finally, section 5 concludes the paper and discusses the next steps in the work progress.
2
Related Work
Various approaches for controlling the charging of electric vehicles have been suggested in the literature. Three charge-control methods have been proposed in [3] and they are compared with a baseline case where the vehicles are assumed to be plugged in and charged as soon as they are parked. The three scenarios include
58
M. Ramezani, M. Graf, and H. Vogt
price signal-based charging, load-signal-based charging, and renewable-energysignal charging. In the price-signal-based charging the charging rate is decided based on the real time prices and in the load-signal-based charging scheme the charging rates are defined by the real time load. Renewable-energy-signal charging is based on the premise that the cars are charged only using renewable energy. When RE availability is high (e.g. in windy or sunny conditions), the cars are charged with a higher rate while they are charged at a lower rate when less RE resources are available. However, the controller ensures that all vehicles will be able to fully charge within certain time (e.g 6 hours) even when no RE resources are available. Researchers have studied approaches for optimized charging of EVs at home [1,4]. Mets et al. [4] introduce two optimization strategies and compare them with a baseline scenario where cars are charged fully as soon as they are plugged in. The first method is a local strategy where only information of one residential home where the car is charged is taken into account. Thus, the charging is optimized for local loads. The second method is a global strategy which controls the charging of multiple vehicles based on global load information over a residential area. Both strategies control the duration and rate of charging and result in charging schedules for each vehicle. The results of this study show that control strategies can lower peak load and smooth the overall load profile as a result of shifting the demand. Similarly, [1] proposes stochastic programming to compute optimal charging schedule for plug-in hybrid electric vehicles by minimizing the power losses. Our work in this paper is different from the ones mentioned above in several aspects. First, we propose an optimization algorithm that is applicable to public charging scenarios as well as a private one. Moreover, we design a multi-objective algorithm which can take into account several hard and soft constraints for optimization. Our suggested algorithm is flexibly tunable based on the preferences and requirements of the charging service provider.
3
Problem Definition
In this section we describe the hard constraints and objectives that our optimization algorithm takes into account. 3.1
Hard Constraints
Hard constraints are restrictions and limitations that must be taken into account in any schedule. There is no acceptable solution that violates the hard constraints while objectives are soft constraints. Grid Capacity. We consider the grid capacity as a hard constraint in all our scenarios. Our assumption is that the charging service provider will get updates about the available grid capacity in regular intervals, e.g. every 15 minutes. The charging controller plans the charging schedule based on the prediction of available capacity in the future. However, it reacts in real time to the deviations
A Simulation Environment for Smart Charging of Electric Vehicles
59
between the actual available capacity and the predicted once. At any time, the sum of charging loads should be below the grid capacity reserved for EV charging: P (i, t) < capacity(t) (1) ∀t : i
where P denotes the charging power level applied to EV battery i at time t, and capacity(t) is the grid capacity available for EV charging at time t, which is specified by the grid operator. For determining this value, other loads connected to the grid are taken into account. Battery Constraints. Different types of batteries have certain constraints which have to be taken into account by the charging controller, especially regarding their charging curves that have to stay within given bounds. In addition, we consider two further important constraints for the batteries: (1) the maximum amperage and (2) the possibility of intermittent charging. Only batteries that are compatible with intermittent charging will be assigned an intermittent schedule. All batteries not capable of this are assigned continuous schedules. 3.2
Optimization Objectives
We consider several objectives for the evolutionary algorithm. Each objective can be weighted according to the preferences of the charging service provider. The optimization algorithm should consider the different objectives and provide the solution that maximizes the fitness function of the objectives. Maximize Provider Profit. The provider profit is determined by the difference between the sales price and the procurement cost of the charging power. Basically, procurement takes place on two different markets. On the first market, large amounts of base load are traded for securing the long-term supply in response to determined base demand. On the second market, smaller and short-terms loads are traded, possibly at real-time prices. The cost of transactions and the price for the purchased amounts of energy determine the provider’s procurement costs. At a given time, there is a certain cost associated with the provisioning of power to the charging infrastructure. The procurement cost is denoted as priceproc (t) for a given time interval t. The optimizer should consider dynamic prices and schedule the charging such that possibly most cars get charged when procurement costs are low, and avoid charging at peak prices. In addition, we define pricecust (i, t) as the individual price value for customer i within time interval t. Charging prices might be different for different customers based on various kinds of tariffs or contracts. For example, a specific customer might have a contract that guarantees a fixed price at specific times of day. Thus, the provider profit can be calculated as: #cars
R=
(charge(i, t) × (pricecust (i, t) − priceproc (t)))
(2)
i=1 t∈T
where T is a set of mutually disjoint but continuous time intervals, and charge (i, t) is the amount of electricity charged by car i at time interval t.
60
M. Ramezani, M. Graf, and H. Vogt
Minimize Battery Degradation. The effects of combined driving and vehicleto-grid (V2G) usage on the lifetime performance of different type of batteries for EVs have been studied by several researchers including [5,6]. In our optimization algorithm we consider two different adverse influences to battery lifetime. First, impact of discontinuous charging, second the impact of charging itself. The latter depends on the used charging curve (the amperage value) of a specific battery type. We expect less Battery degradation when lower amperage is used compared to high amperages. We define degradation factors for different battery types which represent the degree of adverse influences to battery lifetime. fdisc represents the degradation factor of a specific battery for discontinuous charging and fcharge (c) represents the degradation factor of that battery when charged with charging curve c. In a real scenario, these degradation factors can be determined by long term experiments for different battery types. The overall degradation D(i) of a charging process for a car i is calculated as the sum of all degradation values: D(i) =
fcharge (c) × charge(c) + fdisc × n
(3)
c∈C
where n is the number of times the charging has been stopped and restarted during one charging process, C is the set of different charging curves used in one charging process and charge(c) is the scale of energy for a charging curve c. Maximize User Satisfaction. We assume that users specify the minimum requested charging level and the departure time. These factors are considered as hard constraints for the algorithm while the other objectives discussed so far are weighted based on user priorities. If the user has not explicitly specified his preferences regarding the significance of cheaper price, faster charging, or low battery degradation, then the algorithm considers equal weights for each objective.
4
A Simulation Environment for Smart Charging
A simulation environment for EV charging serves multiple purposes: – It can be used to evaluate user tariffs in various scenarios, determining the expected costs for EV charging under different market conditions and in different locations. The individual cost for each user can be determined, from which statistics can be derived. From this, market acceptance of tariffs can be assessed. – The power provider can use the simulation environment to estimate the amount of the base load at different times, and the level of fluctuations. This helps him to procure the required amounts of energy at low prices. Furthermore, by setting dynamic price profiles, the provider can give incentives to make use of renewable energy when possible.
A Simulation Environment for Smart Charging of Electric Vehicles
61
– The presented optimization goals are partially contradictory by nature, therefore not all possible user preferences can be fulfilled. Simulations can help to determine reasonable and meaningful user preferences, thereby providing a foundation to design tools that help users to define their preferences according to their expectations. We design a simulation environment that builds on a multi-objective optimization algorithm. Within the simulation environment, scenarios are defines and parameters are set. The optimization algorithm employs an evolutionary scheme that is able to handle contradictory optimization objectives. 4.1
Simulation Environment Properties
This simulation environment is capable of generating a scenario based on several parameters that describe a specific situation. These parameters specify minimum, maximum and average values as well as standard deviation values of Gaussian distributions, which are used to calculate realistic scenario data. In addition, several uncertainties will be considered within a scenario. For example, it is not realistic that car owners can exactly specify the fetching time of their cars prior to charging. The same applies for predictions of maximum capacity curves or car arrivals. Therefore we use Gaussian distributions to simulate deviations of what we call “expected” and “real” data. The following sections will present the most important scenario information. Scenario Meta Information. Each scenario has its unique properties, a specified time interval and a number of charging stations. In addition, it is possible to set different points in time at which scenario parameters (e.g. capacity curve) change. Location Specific Information. We consider each location to have an expected number of car arrivals during each simulation period. Moreover, we simulate the capacity curve predictions. Capacity predictions may change over time and are simulated more accurate for closer points in time relative to simulation progress. Car Owner Behavior. Cars have a specific time of arrival as well as a specific parking duration depending on the scenario. Arrivals and departures are precisely simulated. Besides, each car battery has a certain charge level on arrival and a requested charge level. Battery Information. Each car is simulated with a specific battery type for which we assume to have technical data. Characteristics of a concrete manifestation of such a battery type may differ slightly from its specification because of degradation and environmental conditions. We consider each battery to have a limited set of charging curves with different maximum amperage rates.
62
M. Ramezani, M. Graf, and H. Vogt 100.000
0,020
90.000
0,019
Power [W]
0,017
70.000
0,016
60.000
0,015 0,014
50.000
0,013
40.000
0,012
30.000
0,011
20.000
0,010
Electricity price [Cent/Wh]
0,018
80.000
0,009
10.000
0,008
0 00:00 02:00 04:00 06:00 08:00 10:00 12:00 14:00 16:00 18:00 20:00 22:00 00:00
Maximum power
Used power
Electricity price
Fig. 1. Simulation environment shows the electricity price, maximum grid capacity and the used power for charging. The charging schedule is given by an evolutionary algorithm which considers different factors.
4.2
Optimization Algorithm
As a first step of optimization, several solutions that hold all hard constraints are generated. A solution contains the charging schedule for the all the cars, specifying the start and end time of the charging as well as the used charging curve. We develop a hybrid evolutionary algorithm using a local search technique. Thereby all cars are rescheduled one after the other in a specific order until an optimum is reached and no further improvement is possible. A mutation operator that exchanges the starting charging time of several cars is used during evolution in order to escape local optima. In addition, a One-Point-Crossover is applied that combines existing charging schedules. New solutions that are generated by mutation or recombination are subsequently optimized with local optimization. To realize the charging optimization of a continuous simulation scenario, the optimizer has to be called every time planning circumstances change. For example, when a new car arrives or when the available grid capacity is different from the existing prediction. Figure 1 shows an screenshot of the simulation environment. We can see that the charging schedules are optimized so that more cars are charged when the price is cheaper.
5
Conclusion and Future Work
In this paper, we presented a simulation environment and a multi-objective evolutionary algorithm for smart charging of electric vehicles. Our suggested charging controller, with the optimization algorithm at its core, could be used in a real-world setting for creating charging schedules. This requires that the simulation environment is substituted with interfaces to real-world devices and systems.
A Simulation Environment for Smart Charging of Electric Vehicles
63
As current work in progress, we have designed benchmark scenarios to compare our evolutionary algorithm results with other baseline approaches such as first in first out, greedy algorithm and local optimization. As future work, several evaluation scenarios will be generated and stored in a database. Each scenario will be tested with all scheduling approaches and the results of a full simulation run will be evaluated based on the introduces objectives and the assigned weights to each objective. In addition, we will experiment with different levels of uncertainty to identify the impact of uncertainty on our approach. This will show the requirements of accurate predictions for a reasonable usage of multi-objective evolutionary algorithms for charging of EVs. In addition, future work can focus on better understanding the requirements. The operator of the charging infrastructure may be different from the power provider, which again may differ from the grid operator. Depending on who is the operator of the charging controller, a different set of optimization weights may be necessary.
References 1. Clement-Nyns, K., Haesen, E., Driesen, J.: The impact of charging plug-in hybrid electric vehicles on a residential distribution grid. IEEE Transactions on Power Systems 25(1), 371–380 (2010) 2. Kempton, W., Tomi´c, J.: Vehicle-to-grid power fundamentals: Calculating capacity and net revenue. Journal of Power Sources 144(1), 268–279 (2005) 3. Markel, T., Kuss, M., Denholm, P.: Communication and control of electric drive vehicles supporting renewables. In: Vehicle Power and Propulsion Conference, VPPC 2009, pp. 27–34. IEEE, Los Alamitos (2009) 4. Mets, K., Verschueren, T., Haerick, W., Develder, C., de Turck, F.: Optimizing Smart Energy Control Strategies for Plug-In Hybrid Electric Vehicle Charging. In: IEEE/IFIP Network Operations and Managament Symposium Workshops (2010) 5. Ritchie, A., Howard, W.: Recent developments and likely advances in lithium-ion batteries. Journal of Power Sources 162(2), 809–812 (2006); special issue including selected papers from the International Power Sources Symposium 2005 together with regular papers 6. Gross, S.: Review of candidate batteries for electric vehicles. Energy Conversion 15(3-4), 95 (1976)
Furthering the Growth of Cloud Computing by Providing Privacy as a Service David S. Allison and Miriam A.M. Capretz The University of Western Ontario London, ON, Canada {dallison,mcapretz}@uwo.ca
Abstract. The evolution of Cloud Computing as a viable business solution for providing hardware and software has created many security concerns. Among these security concerns, privacy is often overlooked. If Cloud Computing is to continue its growth, this privacy concern will need to be addressed. In this work we discuss the current growth of Cloud Computing and the impact the public sector and privacy can have in furthering this growth. To begin to provide privacy protection for Cloud Computing, we introduce privacy constraints that outline privacy preferences. We propose the expansion of Cloud Service Level Agreements (SLAs) to include these privacy constraints as Quality of Service (QoS) levels. This privacy QoS must be agreed upon along with the rest of the QoS terms within the SLA by the Cloud consumer and provider. Finally, we introduce Privacy as a Service (PraaS) to monitor the agreement and provide enforcement if necessary. Keywords: Cloud Computing, Privacy, Quality of Service, Privacy as a Service.
1 Introduction Cloud Computing represents an evolution of both computer hardware and software, as businesses and individuals alike no longer need to design, purchase, setup or maintain their own systems. Both hardware and software can be virtually maintained on the Cloud by a provider. Cloud Computing is desirable due to its cost effectiveness; the computing resources Cloud Computing can provide are often offered as a pay-as-yougo plan. In order for new computing evolutions, such as Cloud Computing, to gain widespread acceptance, the concerns consumers have in the technology must be addressed. Cloud Computing has shown success with consumers in some areas, such as delivering Web based email and online documents. These results, as seen in Google's Gmail [1] and Google Docs [2], are just a few of the possible uses for Cloud Computing. In order for Cloud Computing to continue its initial success and gain more widespread acceptance, major areas of consumer concern must be found and addressed. A 2010 survey of 100 IT professionals found that security was the top Cloud related concern, cited by 73% of the respondents [3]. Security is a far reaching topic in Cloud Computing and e-services, and includes such topics as authentication, authorization, auditing and privacy. D. Kranzlmüller and A M. Tjoa (Eds.): ICT-GLOW 2011, LNCS 6868, pp. 64–78, 2011. © Springer-Verlag Berlin Heidelberg 2011
Furthering the Growth of Cloud Computing by Providing Privacy as a Service
65
Privacy is a difficult topic with many unique problems. Privacy is subjective, as what can be considered private is unique to each individual. Providers prefer little consumer privacy, as the more information about a person a provider knows, the better it can create direct advertising. Due to these problems, of all the different topics in security, privacy is the least addressed [4]. Privacy is a particular concern to Cloud Computing, as Cloud providers necessarily have access to all of a consumer's data, and can use or disclose that information for unauthorized purposes, either accidentally or deliberately [5]. By addressing the issues of privacy, Cloud Computing will further gain the trust of consumers. This increase of consumer trust will give Cloud Computing a wider acceptance and will lead to its further growth as a technology. It is important for the adoption of Cloud Computing to increase not only for economic reasons, but environmental as well. Cloud Computing advocates the better management of resources, resulting in the reduction of carbon emissions and the environmental impact of IT [6]. The environment impact of IT is substantial, accounting for 2% of all global carbon emissions [7]. A 2010 study commissioned by Microsoft [8] and conducted by Accenture [9] and WSP Environment & Energy [10], found that moving business applications from in-house to the Cloud can save a substantial percentage of carbon emissions, depending on the size of the business. Smaller businesses show the greatest benefit, reducing carbon emissions by up to 90 percent. Medium businesses are able to produce a 60 to 90 percent reduction, and large businesses a 30 to 60 percent reduction [11]. These reductions in carbon emissions were in large part thanks to four key aspects of Cloud Computing: the reduction of over-allocation of infrastructure, the sharing of application instances between consumers to reduce peak loads, the increased utilization of server infrastructure, and the improved efficiency of data centers to reduce the power required for cooling and maintenance [11]. In this work the ideas and issues surrounding privacy in Cloud Computing will be discussed, and the beginning of a framework to address Cloud Computing privacy will be presented. The goal of this work is to increase the adoption of Cloud Computing by providing privacy protection, in order to increase the economic and environment benefits Cloud Computing provides. We have previous experience in developing a privacy framework containing a Privacy Service and privacy policies in the related field of Service-Oriented Architecture (SOA) [12]. This work has the additional goal of being the first step towards a larger privacy framework for Cloud Computing. Section 2 discusses the current growth of Cloud Computing, and how the public sector and privacy can increase this growth. Section 3 provides an introduction to privacy, by first defining privacy, and then defining the different classifications of private information. Section 4 extends current SLAs with privacy quality of service (QoS) parameters. To this end, privacy constraints are developed from general privacy guidelines. These privacy constraints are defined, and then introduced into the SLA as QoS level parameters. Section 5 discusses the need for monitoring and legislation related to privacy in the Cloud. It is in section 5 that the concept of Privacy as a Service (PraaS) is introduced. This PraaS adds an extra level to the Cloud, which monitors the agreed upon privacy terms of the SLA. If any infractions are detected, the PraaS will provide alerts and enforcement if necessary. Section 6 discusses related work in the field of Cloud Computing privacy. Finally, Section 7 presents conclusions and future work.
66
D.S. Allison and M.A.M. Capretz
2 Cloud Computing Growth Cloud Computing has shown much growth since its inception less than a decade ago. However there is still much room available for continued expansion. In this section the abilities of Cloud Computing that have lead to its initial success are discussed, along with the Cloud's potential future growth and the role the public sector needs to play in that growth.
Fig. 1. Services available in the Cloud
2.1 Current Reasons for Growth The main advantage of Cloud Computing is its ability to provide an infinite amount of computer resources on demand, scaling to fit each individual need [13]. This relieves the Cloud Computing consumer from the task of planning ahead for future hardware and software requirements. Each Cloud consumer is charged for only what they are using, creating a renting structure for computer resources. Cloud Computing has been successful since its inception due to the large variety of services it provides. These services, as shown in Figure 1, range from low to high complexity and allow for a wide assortment of solutions to consumer needs. •
•
Software as a Service (SaaS): SaaS allows a consumer to access the functionality of a software application over the Internet or any computer network. SaaS has the benefits of not requiring a consumer to install any software on their own computer, allowing the application to be accessed easily from multiple devices. SaaS is also economically friendly, as consumers do not have to purchase an expensive software license, but rather lower priced access bundles based on access time or number of uses [14]. Infrastructure as a Service (IaaS): IaaS allows a consumer to gain access to a bare but complete hardware computing package. This includes hardware (HaaS), data storage (DaaS), network connectivity, and some fundamental software (SaaS), such as an operating system [15].
Furthering the Growth of Cloud Computing by Providing Privacy as a Service
•
•
•
67
Hardware as a Service (HaaS): HaaS is made available through the virtualization of computer hardware over a network [16]. Access to physical hardware is made available to the Cloud consumer, who is charged based on the amount of processing power they utilize. Hardware virtualization allows the provider to use as many pieces of physical hardware as required to satisfy the demand of the consumer, while from the perspective of the consumer, only one piece of hardware is being used. HaaS provides a consumer with hardware flexibility and scalability not possible with on-premise hardware. The consumer always has access to the correct amount of hardware to meet their needs [16]. Data as a Service (DaaS): DaaS, also known as Storage as a Service, allows consumers to send and retrieve their data on externally provided storage. DaaS is uniquely defined as providing a consumer with the ability to create, read, update and delete data, rather than providing computation on data [17]. Through the use of DaaS, consumers have access to a virtual, scalable hard drive that will theoretically never run out of disk space. From the perspective of the consumer, their data is available just as if it were available on a local disk [16]. Platform as a Service (PaaS): PaaS is a remote computing environment delivered by Cloud Computing through the combination of HaaS, DaaS and SaaS [16]. PaaS builds on top of IaaS, by adding a layer of abstraction to automate the system, typically an application environment [15]. Consumers can subscribe to PaaS and gain access to a virtual platform for application development and deployment [18].
2.2 Future Growth and the Public Sector The ability of the Cloud to provide remote, scalable, on-demand services at varying levels of complexity has lead to its initial success and growth. This growth has been so strong, that some leading technologists have predicted that within the decade upwards of 90% of the world's computing and data storage will take place in the Cloud [19]. While it has become easier to predict how Cloud Computing will be used in the future, there are still many unanswered questions about the Cloud's future legal, economic and security details [19]. Privacy is one large aspect of security that needs to be addressed. In order to achieve a privacy solution, help from the public sector will be required. The public sector can adopt not only Cloud Computing, but standards and laws for providing privacy in the Cloud as well. This adoption by the public sector will also add to consumer trust of Cloud Computing technologies, leading to its further growth. The public sector's involvement in Cloud Computing can produce a significant impact on the pace of the technology's development. Governments have shown the ability to provide this impact in examples such as the adoption of telecommunication standards and the investment in needed infrastructure. As well, governments are often the largest economic entity in their country, and provide an example for other sectors of business [19]. For another example of the impact governments and public sectors can have on the growth of a new technology, one can look at the rapid growth and success of the Internet. Through the Internet's roots as the research of the United
68
D.S. Allison and M.A.M. Capretz
States Department of Defense, to the United States federal government's early adoption of Web sites and Internet Protocol [19], the public sector of the United States fueled the widespread growth of the Internet. Similar interest from public sectors around the world in Cloud Computing along with privacy protection, will greatly increase the technology's growth and adoption.
3 Privacy In order to address privacy in Cloud Computing environments, one must first address the problem of defining privacy. Privacy as a concept is subjective, and has no single definition. In this section a definition for privacy will be given, which defines how privacy is viewed in this work. Also, the different types of private information one can expose on the Cloud will be defined. 3.1 Definition of Privacy Security in computing is a large subject consisting of many different areas, such as authentication, authorization, auditing and privacy. Of these security concerns, privacy is the most difficult to define. Authentication is the process of determining that someone is who they claim to be. Authorization is the act of determining that a person or thing has the right to access a particular resource. Auditing is the task of recording the actions of a person or thing, ensuring that this person or thing cannot perform an act, and then later claim that it did not happen. These definitions are simple and unambiguous. Privacy is unique in that it has no one definition, the idea of privacy has changed and evolved over time. In 1888, privacy was defined as "the right to be left alone" by Justice Thomas M. Cooley [20]. This definition evolved into the ability to control the release of information about oneself. In the modern era, new technologies such as Cloud Computing have made releasing information about oneself often not an option, but a necessity of communication. In many cases this release of information is done without an individual's knowledge or consent. For this reason, in this work privacy is defined as the ability to protect information about oneself, and to also have some level of control over any information that has already been released. 3.2 Private Information It is impossible to universally identify all information that should be considered private. What one person considers private may not be considered private by another. For example, some people freely list their telephone number in directories, while others withhold this information. In lieu of a list of all forms of private information, it is important to identify different classifications of private information. As privacy is subjective and often relies on a given context, the classification definitions given in this section are not meant to be universal, but to apply in context to this work. •
Personally Identifiable Information (PII): Personally identifiable information is any single piece or combination of information that can uniquely be traced to an individual. Some examples of a single-piece PII include credit card
Furthering the Growth of Cloud Computing by Providing Privacy as a Service
•
•
69
numbers, social insurance numbers, license plate numbers and fingerprints. Combination type PII include any grouping of information that together are associated with a single person. For example a name and a birthday individually may each point to several people, while together they can be used to find a specific person. Sensitive Information: Sensitive information is a classification that can be associated with a large number of people, but is still considered private by many due to personal concerns or personal preference. Examples of sensitive information include wage, age, sex, religion, and sexual preference. It is important to note that sensitive information can become PII if used in combination, or even by itself if the sample size is small or not diverse. For example in a city of people, knowing the age of a person would not be enough to identify that person. However in a workplace, there may only be a single person of a given age and thus age becomes PII. Usage Information: Usage information is gathered by tracking the history of any activity of an individual. Today, this is most commonly done through the tracking of an individual's activities on the Internet. When collected in small amounts, usage information cannot be traced to an individual. However when collected in large amounts over a period of time, even usage information can be used to deduce the identify of a person [21], thus it can become PII.
4 Extending the SLA with Privacy The first step that is required to provide privacy in a Cloud Computing environment is a formal agreement between the Cloud consumer and provider, outlining how private information of the consumer will be handled by the provider. The privacy specifications of the Cloud consumer and Cloud provider will often be different and in conflict with one another. Therefore a negotiation process will need to be completed between the two parties. Once negotiations have been completed, the agreed upon privacy details will form a privacy contract. Cloud Computing currently contains a contract known as a Service Level Agreement (SLA). The SLA details the quality of service agreements between a Cloud consumer and provider, outlining the conditions under which a service can be provided to a consumer [22]. Typically, these SLAs describe technical details such as availability, accessibility, throughput, and response time. SLAs rarely, if ever, discuss privacy. Thus we propose the current standard of Cloud Computing SLAs should be expanded to include privacy terms and conditions. 4.1 Developing Privacy Constraints In order to determine what privacy constraints should be added to the SLA, it is important to look at the current state of privacy legislation. The Organisation for Economic Co-operation and Development (OECD) has developed a set of Fair Information Practices (FIP) [23] which have been used as the basis for most of the privacy legislation throughout the world [24]. The FIP outlined by the OECD are a set of standards that govern the issues of privacy, both for the gathering and usage of personal information. The OECD guidelines produce eight basic privacy principles:
70
D.S. Allison and M.A.M. Capretz
1.
2.
3.
4.
5.
6.
7.
8.
Collection Limitation Principle: Limits should be placed on the collection of any personal data. Data that is collected should be gathered legally with the knowledge or permission of the data subject. Data Quality Principle: Personal data can only be collected if it is relevant to the purposes for which it is required. The collected data must also be current, whole and accurate. Purpose Specification Principle: Any and all purposes for which the personal data is being collected should be specified at or before the time of collection. Any future changes of purpose must also be reported to the data subject. Use Limitation Principle: Any personal data that is collected will not be made known or used for any purposes other than those specified by the Purpose Specification Principle. Exceptions to this are if consent is given by the data subject, or if the request is made with the authority of law. Security Safeguards Principle: Collected personal data must be protected against dangers by reasonable security safeguards. Examples of dangers are: unauthorized access, alteration, removal, use and data leaks. Openness Principle: Data controllers should provide transparency to their data collection by providing information regarding any data related practices, policies or developments. Data subjects should be provided the means to inquire about the existence of any personal data, the type of data, the purpose of use, the identity of the data collector and the location of the data. Individual Participation Principle: Data subjects should be able to determine if any of their information has been gathered by a data controller. If any data has been collected, the data subject can request to be sent the data in an understandable format and in a reasonable amount of time. If the controller refuses either of these requests, the decision must be communicated to the subject and be challengeable. Data subjects should be able to challenge the information that has been gathered about them and if proven correct, have that data changed, removed or amended. Accountability Principle: Accountability should be present to ensure the data controller is fulfilling all the above principles.
It is from these eight principles that the information that should be negotiated as part of a Cloud Computing SLA can be gathered. The process of selecting privacy constraints from these eight principles is shown in Figure 2 and is described in detail below. We have also used the same OECD guidelines in previous work to develop similar privacy policies for SOA [25]. •
Recipient: The Use Limitation and Openness principles require the identity of the party who is allowed access to the private data be specified. This allows the proper party to not only gain access to the data, but also be available for further questions and challenges related to their data collection. Similarly, the Use Limitation principle states that there should be limits to whom the data can be disclosed. While the Openness principle requires the data controller be able to state the identities of all parties who have access to the data. From these two principles it was determined that the recipients of the data must be disclosed. This could be the single provider alone, or include parties the provider may pass information to. The recipient constraint allows this information to be known.
Furthering the Growth of Cloud Computing by Providing Privacy as a Service
71
Fig. 2. Extracting privacy constraints from OECD principles
•
•
•
What: Not surprisingly, the most common theme throughout the OECD guidelines is dealing with the data itself. The Collection Limitation principle expresses that the data subject must know what parts of their information are being collected. The Data Quality principle states that the data must be complete and accurate, while the Openness principle dictates that the nature of the data must be made available. Finally, the Individual Participation principle lists challenges the data subject should be allowed to make in regards to their own private data. From these principles it becomes clear that what type of data will be collected must be defined. Only after this has been agreed upon between Cloud consumer and provider will these privacy principles be satisfied. Retention: Another requirement seen in multiple privacy principles deals with the idea of time. Collection Limitation states that there should be limits placed on the data collection, time being one such limit. Similarly, in order to keep the data up-to-date, as specified in the Data Quality principle, the age of the data must be specified. An agreed upon retention time would allow the appropriate length of time for storage of the collected data to be specified. Purpose: The Data Quality, Purpose Specification and Openness principles all require the reasons for which the data is collected be detailed. By outlining a purpose for the data collection, it can be assured that the possible uses of the data are known to both the Cloud consumer and provider.
72
D.S. Allison and M.A.M. Capretz
Not every principle outlined in the OECD guidelines has been addressed by the requirements outlined above. This is because a privacy solution can only fulfill every privacy concern when included within a larger security framework. The Security Safeguards principle states that the data must be protected against unauthorized access and release. These concerns are addressed through the use of traditional security techniques, such as authentication, authorization and encryption. The Accountability principle states the more abstract concern of holding the Cloud provider responsible for complying with all the other principles. Accountability presents a unique problem for Cloud Computing as the ability to provide enforcement is difficult and often nonexistent. This problem must be addressed through the combination of effective legislation and a Cloud monitoring system. 4.2 Privacy Quality of Service Levels Cloud Computing environments implement SLAs in order to control the delivery and use of computing resources from a Cloud provider to a Cloud consumer. An SLA is defined by a schema containing Quality of Service (QoS) parameters. We propose the expansion of traditional SLA schemas to include a QoS privacy parameter. This privacy parameter will consist of four ordered levels of service. These levels can be organized by the provider to meet their needs. An example set of QoS levels is shown in Table 1. Each privacy constraint as defined in section 4.1 has a different value for each level of service. This expansion of the SLA with QoS privacy parameters was inspired by our previous work in creating metadata for Quality of Security Service (QoSS) for SOA [26]. The constraints in each QoS level are flexible, and can be changed to meet the requirements of any Cloud Computing environment. The constraints in each QoS level are also expandable and can be further defined. For example, the Cloud consumer and provider can create a further definition for the Data Category constraint. The data could be classified into the three categories of personal data: PII, Sensitive Information, and Usage Information. Each of these categories can contain whatever type of information is desired, and this determination is dependent on the perspective of the consumer and provider. With this extension, the consumer and provider can outline fine-grained privacy for specific types of data. Table 1. Example QoS privacy levels
Level
Recipient
Data Category
Purpose
High
Local
Moderate
Trusted
Low
Enterprise
Guest
Anyone
Consumer Specified Consumer Specified Provider Specified Not Specified
No Collection & No Distribution Collection & No Distribution Collection & Limited Distribution Collection & Distribution
Retention Time 7 days 30 days 365 days Indefinitely
Furthering the Growth of Cloud Computing by Providing Privacy as a Service
73
To help illustrate the example shown in Table 1, the Cloud consumer could select the moderate level of service from the provider. This selection would mean that the consumer allows the recipient to be anyone trusted by the consumer, meaning any other service the provider includes in the Cloud. The data category is consumer specified, meaning the Cloud consumer chooses what types of data they will allow to be collected. The purpose is for collection and no distribution, meaning the provider can read their data, but not share it with anyone. Finally the retention time outlines that the data can be held for a maximum of 30 days. The QoS privacy parameters should be added to the schema in the same format as the current schema implementation. With the addition of the new privacy constraints, when the SLA is negotiated between consumer and provider, privacy will now be considered. The sophisticated process of SLA management and negotiation [6] is outside the scope of this work, but since the privacy QoS data is added to the schema in the same format as the preexisting SLA conditions, whichever negotiation process is currently applied should be easily convertible to handle the new constraint.
5 Monitoring and Legislation While the negotiation of privacy terms within an SLA is necessary, it is not enough to provide adequate privacy in Cloud Computing environments. There must be a system in place to both monitor the status of the SLA, and to provide enforcement of its terms. In this section, we discuss how this monitoring can be done, and how legislation is required for enforcement. 5.1 Monitoring Privacy with Privacy as a Service We propose a new Privacy as a Service (PraaS) to handle the monitoring of the privacy agreement between the Cloud consumer and provider. The PraaS will ensure the agreement that was reached between Cloud consumer and provider is being adhered to. The PraaS must be created and introduced into the Cloud by a trusted third party (TTP). The PraaS will be monitoring the situation with regards to privacy within the Cloud, as well as making decisions that affect both the Cloud consumer and provider. Trust in the provider of the PraaS is required in order to ensure both the Cloud consumer and provider that this monitoring and decision making process is being done without bias. This TTP could be an established standard organization, such as the OECD [27] or World Wide Web Consortium (W3C) [28], a public sector organization, or a not-for-profit organization. The PraaS is illustrated in Figure 3. Once the PraaS is introduced into the Cloud, it will be required to monitor the system. Monitoring in a Cloud environment is more difficult and complex than compared to an enterprise application due to the large amounts of data created over a distributed environment [29]. Compounding the problem is the lack of standardization in Cloud Computing [6]. The implementation of a monitoring system within PraaS is outside the scope of this work, but there are several existing Cloud monitoring tools which can provide examples of how such a system can be done [30] [31]. As many copies of the PraaS as required to efficiently monitor the system will be deployed in the Cloud. This will be done to avoid the PraaS becoming a single point of failure and to avoid creating a bottleneck in the Cloud.
74
D.S. Allison and M.A.M. Capretz
SLA Negotiation and Agreement Consumer Communicates
Cloud PaaS PraaS Provides
SaaS
IaaS DaaS
Trusted Third Party
HaaS
Communicates
Provides
Provider
Fig. 3. Privacy as a Service Deployment
5.2 Legislation and the Public Sector If a privacy violation is detected by the PraaS, both the Cloud consumer and provider should be informed. The TTP that deploys the PraaS can perform this action, as shown in Figure 3. The communication can be handled automatically by the PraaS, or another type of service developed by the TTP. If no quick resolution to the problem can be found, or the violation is severe, enforcement will be required. Enforcement of any technology that operates over networks such as the Internet is a challenging problem. In order to provide accountability, governing bodies must create legislation addressing privacy in a Cloud environment. This legislation would assist the PraaS by providing tools for enforcement, such as an enforcement body to report to and punishments for infractions. Legislation is notoriously late when addressing problems in technology. Further research will be required to compare the differences between legislation that has already been adopted around the world, and what areas and topics still require new laws. Creating and abiding by legislation over a distributed environment is a massive topic, as different countries have different, and often conflicting laws. These problems can be compounded if information is sent across international borders. As such, determining exactly what legislation is required falls outside the scope of this work, and is an ongoing field of research [32].
6 Related Work Research into privacy for Cloud Computing is still in its infancy, and as such, there are no set guidelines or benchmarks. HP Labs Singapore has recently begun work on
Furthering the Growth of Cloud Computing by Providing Privacy as a Service
75
a service called Trust Cloud [33] to address concerns of data protection and security. The goal of this Trust Cloud is to monitor any information or file a user places in the Cloud and notify that user if any of their data has been accessed, moved or modified by the Cloud provider [33]. The monitoring proposed by HP's Trust Cloud project is similar to the monitoring required in this work, however there are currently no details available on how HP achieves this monitoring as it is still in early research. The idea of Privacy as a Service has been mentioned before in a few works, but never in the same context as presented here. Itani, Kayssi and Chehab [34] presented Privacy as a Service to provide data storage and processing in Cloud Computing architectures. This approach treats privacy as a strictly encryption based problem, where Privacy as a Service provides secure storage and processing of users' confidential data by utilizing tamper-proof cryptographic coprocessors. Private information is divided into three levels: full trust, compliance-based trust, and no trust. At the full trust level, there is no encryption applied to the data. At the compliance-based trust level, encryption is applied by the Cloud provider once the data has been sent by the consumer. At the no trust level, encryption is handled by a trusted third party before it is sent to the Cloud provider. This approach is very different from the approach presented in this work, as no privacy conditions are set, only varying methods of encryption are utilized. There is another example of Privacy as a Service [35], however this work details a framework, service, model and algorithm to address shortcomings in social platforms, specifically Facebook. This work did not attempt to provide privacy in a greater Cloud Computing environment, and shares very little with our work. The work by Pearson [36] discusses the importance of considering privacy while designing a Cloud Computing environment. This work discusses the privacy challenges presented by Cloud Computing environments, and outlines nine privacy principles which closely resemble the eight privacy principles used by the OECD. It provides guidelines to follow to mitigate the risks of privacy, but does not provide a framework for protecting privacy.
7 Conclusions and Future Work In order for computer software and hardware systems to evolve successfully, new technologies must not only be created, but also grow and gain the acceptance of consumers. Cloud Computing represents a large step forward in the evolution of software and hardware. Consumers are no longer forced to install their own copy on a single machine. With Cloud Computing, a consumer will have access to the same application using the same data from virtually anywhere. There are several issues Cloud Computing must address before it can truly become a widely accepted technology. Privacy is one of the biggest unaddressed issues Cloud Computing currently faces. It is important for Cloud Computing to gain a wider acceptance in order to take advantage of the many economic and environmental benefits it provides. The public sector also has a role to play in Cloud Computing privacy, by providing the legislation required for enforcement of privacy, and by providing an example by adopting the Cloud itself. In this work we introduced the first steps in creating a privacy solution for Cloud Computing. This solution involved identifying key aspects of privacy that must be represented in a formal agreement between the Cloud consumer and provider. These
76
D.S. Allison and M.A.M. Capretz
privacy aspects are derived from privacy legislation used throughout the world [24]. We created quality of service levels from these privacy constraints, in order to incorporate privacy into the Cloud SLA. This novel solution provides a mechanism for creating a contract between Cloud consumer and provider that outlines how private information can be used. To the best of our knowledge, this is the first attempt at incorporating privacy agreement terms into a Cloud Computing SLA. Finally this work introduced a new Privacy as a Service (PraaS). This PraaS is hosted by a trusted third party and tasked with the job of both monitoring for privacy violations and creating accountability through enforcement. Enforcement is only effective when coupled with appropriate legislation, which also must be addressed. This work is intended to be the first of many steps towards providing privacy protection in Cloud Computing environments. As such, there are many future directions for this research: •
• •
• •
The proposed SLA privacy extension will be further researched to determine if any refinements need to be done. This can be carried out through different case studies, with interest taken into how the current design of the SLA privacy terms handles different scenarios. A study into the different ways Cloud SLAs are formatted will be completed. If necessary, a standard SLA will be selected for the privacy extension. More studies will be conducted into current legislation from around the world that pertains to Cloud Computing and privacy. This research will help to identify how governments are approaching the problem, and to better develop monitoring and enforcement of the PraaS. Further research will be done to identify the best monitoring solution for the PraaS. There are many Cloud monitoring options available, and the most efficient and effective will be selected. The PraaS will first be developed in a laboratory setting, where simulations can be run to test its effectiveness and performance. Following this, the ultimate plan for this research is to implement the PraaS in a real world scenario. There is the chance that the state of local legislation at the time of the PraaS development will not allow the PraaS to provide effective enforcement. In this case, the PraaS will focus on monitoring and reporting, allowing for the future expansion of enforcement when possible.
In order for Cloud Computing to achieve widespread long term success, fundamental issues such as privacy must be addressed. This work takes the first steps towards this goal, with the hope that it will lead towards greater success and acceptance of Cloud Computing technology.
References 1. Google Mail - Gmail: Email from Google, http://mail.google.com 2. Google Docs - Online Documents, Spreadsheets, Presentations, Surveys, File Storage and More, http://docs.google.com 3. SolarWinds Cloud Survey Press Release, http://www.solarwinds.com/Company/Newsroom/Press_Releases/Ye ars/2010/21474837235.aspx
Furthering the Growth of Cloud Computing by Providing Privacy as a Service
77
4. Yee, G.: Privacy Protection for E-Services. IGI Publishing, Hershey (2006) 5. Ryan, M.: Cloud Computing Privacy Concerns on Our Doorstep. Communications of the ACM 54(1), 36–38 (2011) 6. Patel, P., Ranabahu, A., Sheth, A.: Service Level Agreement in Cloud Computing, http://knoesis.wright.edu/library/download/OOPSLA_Cloud_wsla _v3.pdf 7. Gartner Estimates ICT Industry Accounts for 2 Percent of Global CO2 Emissions Press Release, http://www.gartner.com/it/page.jsp?id=503867 8. Microsoft Corporation, http://www.microsoft.com 9. Accenture, http://www.accenture.com 10. WSP Environment & Energy, http://www.wspenvironmental.com 11. Cloud Computing and Sustainability: The Environmental Benefits of Moving to the Cloud, http://www.microsoft.com/click/services/Redirect2.ashx?CR_EA C=300012377 12. Allison, D., EL Yamany, H., Capretz, M.: A Privacy Service for Comparison of Privacy and Trust Policies within SOA. In: Gupta, M., Walp, J., Sharman, R. (eds.) Strategic and Practical Approaches for Information Security Governance: Technologies and Applied Solutions. IGI Global, New York (2011) 13. Zhou, M., Zhang, R., Xie, W., Qian, W., Zhou, A.: Security and Privacy in Cloud Computing: A Survey. In: Proceedings of the Sixth International Conference on Semantics, Knowledge and Grids, Ningbo, China (2010) 14. Sun, W., Zhang, K., Chen, S.-K., Zhang, X., Liang, H.: Software as a Service: An Integration Perspective. In: Krämer, B.J., Lin, K.-J., Narasimhan, P. (eds.) ICSOC 2007. LNCS, vol. 4749, pp. 558–569. Springer, Heidelberg (2007) 15. Durkee, D.: Why Cloud Computing Will Never Be Free. Queue 8(4) (2010) 16. Wang, L., Tao, J., Kunze, M.: Scientific Cloud Computing: Early Definition and Experience. In: Proceedings of the 10th IEEE International Conference on High Performance Computing and Communication, Dalian, China, pp. 825–830 (2008) 17. Truong, H., Dustdar, S.: On Analyzing and Specifying Concerns for Data as a Service. In: Proceedings of the 2009 IEEE Asia-Pacific Services Computing Conference, Biopolis, Singapore, pp. 87–94 (2009) 18. Lawton, G.: Developing Software Online with Platform-as-a-Service Technology. Computer 41(6), 13–15 (2008) 19. Nelson, M.: The Cloud, the Crowd, and Public Policy. Issues in Science and Technology 25(4), 71–76 (2009) 20. Cooley, T.: A Treatise on the Law of Torts or the Wrongs Which Arise Independent of Contract, 2nd edn. Callaghan & Co., Chicago (1888) 21. Kanneganti, R., Chodavarapu, P.: SOA Security. Manning Publications Co., Greenwich (2008) 22. Comuzzi, M., Kotsokalis, C., Spanoudakis, G., Yahyapour, R.: Establishing and Monitoring SLAs in Complex Service Based Systems. In: Proceedings of the 2009 IEEE International Conference on Web Services, Los Angeles, CA, USA, pp. 783–790 (2009) 23. Organisation for Economic Co-operation and Development.: OECD Guidelines on the Protection of Privacy and Transborder Flows of Personal Data, http://www.oecd.org/document/18/0,3343,en_2649_34255_1815186 _1_1_1_1,00.html 24. Cavoukian, A., Hamilton, T.: The Privacy Payoff: How Successful Businesses Build Customer Trust. McGraw-Hill Ryerson Limited, Whitby (2002)
78
D.S. Allison and M.A.M. Capretz
25. Allison, D., EL Yamany, H., Capretz, M.: Metamodel for Privacy Policies within SOA. In: The Proceedings of the 5th IEEE International Workshop on Software Engineering for Secure Systems in conjunction with the 31st IEEE International Conference of Software Engineering, Vancouver, BC, Canada (2009) 26. EL Yamany, H., Capretz, M., Allison, D.: Quality of Security Service for Web Services within SOA. In: The Proceedings of the 2009 IEEE International Conference on Cloud Computing, Los Angeles, CA, USA (2009) 27. Organisation for Economic Co-operation and Development, http://www.oecd.org 28. World Wide Web Consortium, http://www.w3.org 29. Mathew, J.: Monitoring Applications in the Cloud, http://www.infosysblogs.com/cloudcomputing/2010/05/cloud_bas ed_monitoring_tools.html 30. Nagios - The Industry Standard in IT Infrastructure Monitoring, http://www.nagios.org 31. Hyperic - Systems Monitoring, Server Monitoring & Systems Management Software, http://www.hyperic.com 32. Pearson, S., Charlesworth, A.: Accountability as a Way Forward for Privacy Protection in the Cloud. In: Jaatun, M.G., Zhao, G., Rong, C. (eds.) Cloud Computing. LNCS, vol. 5931, pp. 131–144. Springer, Heidelberg (2009) 33. HP Labs Singapore Aims for the Clouds: Research Focuses on Customer Co-Innovation and Democratizing the Cloud, http://www.hpl.hp.com/news/2011/aprjun/hp_labs_singapore.html 34. Itani, W., Kayssi, A., Chehab, A.: Privacy as a Service: Privacy-Aware Data Storage and Processing in Cloud Computing Architectures. In: Proceedings of the Eight IEEE International Conference on Dependable, Autonomic and Secure Computing, Chengdu, China, pp. 711–716 (2009) 35. Maximilien, E., Grandison, T., Sun, T., Richardson, D., Guo, S., Liu, K.: Privacy-as-aService: Models, Algorithms, and Results on the Facebook Platform. In: Proceedings of Web 2.0 Security and Privacy, Oakland, CA, USA (2009) 36. Pearson, S.: Talking Account of Privacy when Designing Cloud Computing Services. In: Proceedings of the Workshop on Software Engineering Challenges in Cloud Computing in conjunction with the 31st IEEE International Conference of Software Engineering, Vancouver, BC, Canada (2009)
The Concept of a Mobile Cloud Computing to Reduce Energy Cost of Smartphones and ICT Systems Majid Altamimi and Kshirasagar Naik Department of Electrical and Computer Engineering University of Waterloo, Waterloo, ON, Canada {maltamim,snaik}@uwaterloo.ca
Abstract. In spite of the dramatic growth in the number of smartphones in the recent years, the energy capacity challenge for these devices has not been solved satisfactorily. Moreover, the global demand for green Information and Communication Technology (ICT) motivates the researchers to consider cloud computing as a new computing paradigm that is promising for green solution. In this paper, we propose new green solutions that save smartphones energy and at the same time achieve the green ICT goal. Our green solution is achieved by what we call Mobile Cloud Computing (MCC). The MCC migrates the content from the main cloud data center to local cloud data center temporary. The Internet Service Provide (ISP) provides the MCC, which holds the required contents for the smartphone network. Our analysis and experiments show that our proposed solution significantly reduces the ICT system energy consumption by 63% - 70%. Keywords: Green ICT, Energy Saving, Cloud Computing, Mobile Cloud Computing, Data Center, Mobile, Handheld, Smartphones.
1
Introduction
The number of handheld devices is growing dramatically. Most of these devices are smartphones with WiFi, and 3G that give Internet access capability. With the success of PC-like applications on the smartphones, new constraints and challenges are introduced in design and implementation of these devices. One of the major challenges is the low and limited energy capacity of the device’s battery since the handheld devices should be lightweight. On the other hand, the improvement in battery capacity has less pace than the advances in the semiconductor technologies. To overcome this unique challenge, new approaches from other smartphones technologies, such as communication technology, should consider this challenge. Global warming encourages many technologies to become environment friendly. As Information and Communication Technology (ICT) is one of the most growing technologies, it is important to involve the green goal in ICT current and future design [1]. Cloud computing (CC) is a new computing paradigm that is D. Kranzlm¨ uller and A M. Tjoa (Eds.): ICT-GLOW 2011, LNCS 6868, pp. 79–86, 2011. c Springer-Verlag Berlin Heidelberg 2011
80
M. Altamimi and K. Naik
promising in different aspects such as environment friendliness. Cloud computing provides its resources as processing, networking, and storage capabilities to the end user with less impact on the environment because of it has high utilization of its resources [8,3,2,9]. Moreover, much has been reported in the literature for saving energy in smartphones [6]. For example, the handheld device could save its battery lifetime by offloading energy consumer task to the CC [5,4]. Therefore, the CC is the best candidate for our system. This work proposes new green solution that save smartphones energy and at the same time achieve the green ICT goal. This solution is call Mobile Cloud Computing (MCC). The MCC provides all cloud computing functionalities: (i) Software as a Service (SaaS), (ii) Platform as a Service (PaaS), and (iii) Infrastructure as a Service (IaaS). In this work, we focus on IaaS functionality where the MCC saves the ICT system energy by migrating the contents from the main CC data center to a local cloud. This migration reduces the traffic on the Internet. That is only one transfer for the requested content is made from the CC to MCC. In addition, the handheld devices save their energy by using this MCC. This paper makes the following contributions: – Introduce the concept of a Mobile Cloud Computing (MCC). – Consider the entire ICT system energy cost for green ICT technology. – Analyze and experimentally measure smartphone energy consumption. The order of the paper is as follows. Our system model is described in Section 2. The detail analysis of our system are shown in Section 3. Section 4 shows our system evaluation, and this paper is concluded in Section 5.
2
System Model
Our system consists of four major parts: handheld devices network, MCC data center, Internet, and CC data center, as depicted in Figure 1. Each handheld device is considered as a smartphone in this paper. Hereafter, we use smartphone and handheld device alternatively for the same meaning. Second, the data center provides the cloud computing functionality. This center has a LAN network, servers, and storage hard-disk arrays. There are two types of data center in our system: local and main data center. The local data center represents the infrastructure for the MCC where the main data center is for the public CC. The MCC is called by this name because of it exists to service mobile devices and its content is roaming and not static as in the case of public CC. Finally, the Internet is a set of high-speed routers and links.
3
Energy Cost Evaluation
Assume that we have N users forming the smartphones network. The users use smartphones that can access the Internet through an access point (AP) that is either Wireless Local Area Network (WLAN) or cellular 3G network. The users have the same interests and activities such as in conferences, museums,
The Concept of a Mobile Cloud Computing to Reduce Energy Cost Broadband Access Network
81
WLAN Access Network
oth
Blueto
Bluetooth
Smartphones Networks Cellular/ WiMAX
WiFi
Ethernet Switch
SaaS
PaaS IaaS WDM
Internet ISP
Core Router
Mobile Cloud
Internet Core Cloud Gateway Server and Router
Cloud Computing Data Center
Cloud LAN
Cloud Servers
SaaS PaaS IaaS
Hard-Disk Arrays
Fig. 1. System model
and academic lectures. These users have the same desired contents that they want to have at that place. The desired contents are saved originally on the CC data center by an external source of data such as sensor network, network administrator, or computation result from the cloud itself. There are two possible scenarios to download the contents from the CC as follows. 3.1
Download from the CC Data Center
In this scenario, all users download the contents from the CC through the Internet. The energy cost of downloading the contents from the CC for the entire ICT system can be divided into three parts according to our system model: (i) energy consumed in smartphones to download the new contents; (ii) energy consumed in the Internet to transport the downloaded contents; and (iii) energy consumed in the data center to store the contents and process the download requests. In the following, we investigate the energy cost for each of these parts. (i) Smartphones Network: The smartphone consumes energy in joules (J) that equals to the power consumption in watts (W) to do a specific task multiplied by the time elapsed in seconds (s) to complete this task. Based on this concept, if the contents update has size F bits, the energy cost for a smartphone to download this update is given by Ed = Pd
F Bap
(1)
where Pd is the power consumed in watts by the smartphone to download the update from the AP, and Bap represents the bandwidth in bits per second of the wireless link between the smartphone and the AP.
82
M. Altamimi and K. Naik
Consequently, the total energy cost (Esn ) for a network of N smartphones is given by: F Esn = N × Pd (2) Bap (ii) Internet Network: Measuring or analyzing the energy consumption on the Internet is very sophisticated due to the complexity of Internet topology and the variety of Internet equipments and their supplementary utilities. Moreover, the pieces of TCP packets don’t follow the same route for the same file, which makes the energy cost to transfer each packet is different from other. Therefore, the energy cost of the Internet can be estimated with sensible facts and assumptions. To the best of our knowledge, the best study investigates the Internet energy cost is the work of Baliga et al. [2]. Based on Baliga et al. work, the energy consumption of the Internet to deliver one bit can be calculated as in Eq. (3). 3Pes Pbg Pg 2Ppe 18Pc 4Pw Ei = 6F + + + + + (3) Ces Cbg Cg Cpe Cc Cw where Pes , Pbg , Pg , Ppe , Pc , and Pw are the power consumed in the ethernet switches, provider broadband gateway routers, data center gateway, provider edge router, core router, and high-capacity wavelength division multiplexed (WDM) fiber links transport equipments, respectively. Ces , Cbg , Cg , Cpe , Cc , and Cw are the capacities of the corresponding equipment in bits per second. In this scenario, the energy cost for the Internet to serve N users is calculated as in Eq. (4). EIcc = N × Ei (4) where EIcc is the energy cost for the Internet in CC scenario. (iii) CC Data Center: The cloud data center consumes energy in two major sections: cloud servers, and hard-disk arrays. In this part, the energy consumed in the cloud computing data center network is included in the Internet network since both networks have the same characteristics. The energy consumption of the cloud data center to store a file and response to N download requests in one hour is given as in Eq. (5) [2] that includes the cloud data center supplement utilities such as cooling system. 1.5Psr Pst Ecc1 = 1.5F N + 7200 (5) Csr Cst where Ecc1 is the energy cost for the main CC, Psr and Pst are the power in watts consumed by the content server and hard-disk array, respectively, and Csr and Cst are the capacity in bits per seconds of the corresponding equipments. 3.2
Download from the MCC Data Center
After we made the analysis for the system in previous scenario, we discover that the Internet is the major energy consumer. For this reason, we proposed the Mobile Cloud Computing (MCC) to avoid this consumption in our system. In
The Concept of a Mobile Cloud Computing to Reduce Energy Cost
83
this scenario, the contents update is downloaded by the Internet Service Provider (ISP) from the main CC data center to local MCC data center that is the nearest to the smartphones network. This local data center provides the MCC its cloud functionalities. This MCC could be used in several ways as SaaS, PaaS, IaaS. In this paper, we are interesting in the IaaS service to storage the content for the smartphones network. The ISP downloads the contents file based on predefined strategies. We don’t provide the possible strategies at this time because they are out of the scope of this paper. When the contents file is available on the MCC, the smartphones are able to download this file from the MCC. This scenario reduces the download traffic on the Internet as much as the number of users on the smartphones network. The ISP operates the MCC which is a new energy consumer component. However, the ISP gains two advantages from this. First, the Internet traffic is much reduced on the ISP’s routers and core Internet gateway. Second, the ISP contributes to a green ICT. The energy cost for each system part in this scenario is calculated as follows. (i) Smartphones Network: Using similar approach of previous scenario, the energy cost for the smartphones is the same a given in Eq. (2) . (ii) MCC Data Center: In these scenarios, we proposed the MCC as a new component in the ICT system. For simplicity and without loss of generality, we assume that the MCC has the same structure as the main CC. However, the size of the MCC is debatable; consequently, the energy efficiency of this data center is also debatable. The MCC could have similar CC equipments but not utilized as much as the CC. Thus, the energy cost would be higher than the energy cost of the CC. In contrast, if the MCC is equipped with small and efficient equcpments, the energy cost would be much lower than what it is for the CC. For this reason, we introduce a factor (R) that represents the ratio of the energy cost of the MCC to the CC. The energy cost of the MCC is what we have in Eq. (5) multiply by ratio R as follows. Emcc = REcc1 (6) (iii) Internet Network: The contents file is downloaded by the ISP only once. As a result, the energy cost is given as in Eq. (3) if we assume that the MCC is close to the users network where no extra energy equipments exit between the MCC and the smartphones network. (iv) CC Data Center: The main cloud data center is used to originally update and release the contents, and process ISP request. For these functions, the energy cost will be for one download as given in Eq. (7). 1.5Psr Pst Ecc2 = 1.5F + 7200 (7) Csr Cst
84
4
M. Altamimi and K. Naik
Performance Evaluation
In this section, we present a case study for our system to evaluate our approach for saving ICT system energy and validate our assumptions. We setup experiments on BlackBerry Bold 9700 and measure the actual energy consumed on this device in case of download from the cloud data center. For further detail about our experiments setup and configuration, we refer the reader to our work in [7]. For the Internet and cloud data center, we use the equipments’ companies datasheet since it is not practical to measure the energy consumption for these two parts. Table 1 shows our system parameters that we use in this case study where our experiments provide the entries of rows 2 and 3. Table 1. System parameters and their values Parameter Value Parameter Value Parameter F 1 MB N 20 nodes – Pd (W iF i) 818 mW 1 Pd (3G) 1147 mW 1 Pbtu = Pbtd Bap (W iF i) 166.15 KB/s 1 Bap (3G) 130.28 KB/s1 Bbt Pes 3.8 KW Pbg 3.3 KW Pg Ppe 4.21 KW Pc 10.9 KW Pw Psr 255 W Pst 4.9 KW Csr Ces = Cpe 160 Gb/s Cbg 60 Gb/s Cg Cc 640 Gb/s Cw 40 Gb/s Cst 1 From our experimental results
Value – 464 mW 1 100 KB/s1 5.1 KW 136 W 800 Mb/s 660 Gb/s 604.8 Tb
Using Eqs. (2)-(7), Figure 2 shows ICT total energy consumption and the energy consumed by each part of the system, which are Cloud Computing (CC) data center, Mobile Cloud Computing (MCC) data center when R = 1 , Internet, and smartphones network. The smartphones’ e