Internship proposals 2011/12

Minimizing Live Migration Performance and Energy-Costs in IaaS Clouds

Advisors : Eugen Feller, Christine Morin

Keywords : energy management, performance and energy cost modeling, live migration, consolidation algorithms, virtualization, infrastructure-as-a-service, scheduling, optimization

Description
One of the well known methods to conserve energy and increase the resource utilization in today’s virtualized data centers is to perform workload (i.e., virtual machine) consolidation. Thereby, the problem is typically modeled as an instance of the NP-hard multidimensional bin-packing problem in which the bins represent the physical servers and items the virtual machines (VMs). The objective of the consolidation algorithm is then to place all items such that the number of utilized physical machines is minimized. Therefore, enough idle-time is created in order to suspend/turn-off over provisioned servers.

Existing workload consolidation algorithms can be divided into two categories: exact (e.g., linear or constraint programming) and approximation (e.g., First-Fit, Next-Fit, Best-Fit). While, the former compute optimal solutions they need significantly longer time when the problem size increases as their worst-case complexity is exponential. The latter, on the other hand, are able to compute near-optimal solution with quadratic worst case complexity. All these algorithms model the workload consolidation problem exactly in the same manner as the bin-packing problem. However, despite existing similarities between both models, workload consolidation still differs from the traditional bin-packing. In particular, bin-packing assumes an empty state (i.e., items are not assigned to any bin yet) from which the process of finding a solution starts, while workload consolidation is performed continuously starting from an already existing state (i.e., VMs are mapped to hosts). Given such a scenario, and a single objective (i.e., minimize number of hosts) workload consolidation algorithm (e.g., First-Fit) a new schedule with minimal number of hosts could be computed. However, in order to move from one configuration to another migrations are required which are not taken into account by the traditional algorithms. Consequently, their solutions might be minimal in terms of the amount of required hosts but not in the number of migrations. For example, two solutions both requiring 4 physical machines to accommodate the virtual machines might need 10 and 8 migrations, respectively to achieve the same final configuration. In a dynamic environment such as a Cloud, each migrations represents a costly (i.e., performance and energy) operation and needs to be minimized as much as possible [1]. Hence, considering solely the amount of required physical machines is not sufficient.

Recently, several works have started to investigate the problem of workload remapping. In [7] the authors propose a linear programming (LP) model for server consolidation with migration control. In [3 ] the authors formulate the introduced problem using constraint programming. Finally, in [5] a heuristic called Sercon targeting server and migration cost minimizing is introduced. However, all these works aim at minimizing the number of migrations without taking into account the actual cost of migrations (i.e., performance and energy impact of a migration operation).

This internship will be divided into two parts: In the first part, the intern will study the state of the art in solving multi-objective bin packing problems (i.e., minimize number of hosts and migrations). Moreover, existing approaches for live migration performance and energy cost modeling will be investigated (e.g., [4]). In the second part, the intern will design and implement an multi-objective performance and energycost aware workload consolidation algorithm in the framework of the Snooze [2] IaaS-cloud infrastructure manager. Real-life experiments will be performed on the Grid5000 [5] testbed.

References :

[1] Akshat Verma, Gautam Kumar, and Ricardo Koller. 2010. The cost of reconfiguration in a cloud. In Proceedings of the 11th International Middleware Conference Industrial track (Middleware Industrial Track '10). ACM, New York, NY, USA, 11-16. DOI=10.1145/1891719.1891721 http://doi.acm.org/10.1145/1891719.1891721
[2] Eugen Feller, Louis Rilling, Christine Morin, Renaud Lottiaux, and Daniel Leprince. 2010. Snooze: A Scalable, Fault-Tolerant and Distributed Consolidation Manager for Large-Scale Clusters. In Proceedings of the 2010 IEEE/ACM Int'l Conference on Green Computing and Communications & Int'l Conference on Cyber, Physical and Social Computing (GREENCOM-CPSCOM '10). IEEE Computer Society, Washington, DC, USA, 125-132. DOI=10.1109/GreenCom-CPSCom.2010.62 http://dx.doi.org/10.1109/GreenCom-CPSCom.2010.62
[3] Fabien Hermenier, Sophie Demassey, and Xavier Lorca. 2011. Bin Repacking Scheduling in Virtualized Datacenters. The 17th International Conference on Principles and Practice of Constraint Programming; Application track. Perugia, Italy. Retrieved from: http://sites.google.com/site/hermenierfabien/hermenier-etal-cp2011.pdf
[4] Haikun Liu, Cheng-Zhong Xu, Hai Jin, Jiayu Gong, and Xiaofei Liao. 2011. Performance and energy modeling for live migration of virtual machines. In Proceedings of the 20th international symposium on High performance distributed computing (HPDC '11). ACM, New York, NY, USA, 171- 182. DOI=10.1145/1996130.1996154 http://doi.acm.org/10.1145/1996130.1996154
[5] Murtazaev A, Oh S. Sercon: Server Consolidation Algorithm using Live Migration of Virtual Machines for Green Computing. IETE Tech Rev [serial online] 2011 [cited 2011 Aug 10];28:212-31. Available from: http://tr.ietejournals.org/text.asp?2011/28/3/212/81230
[6] Raphael Bolze, Franck Cappello, Eddy Caron, Michel Dayde;, Frederic Desprez, Emmanuel Jeannot, Yvon Jegou, Stephane Lanteri, Julien Leduc, Noredine Melab, Guillaume Mornet, Raymond Namyst, Pascale Primet, Benjamin Quetier, Olivier Richard, El-Ghazali Talbi, and Irea Touche. 2006. Grid'5000: A Large Scale And Highly Reconfigurable Experimental Grid Testbed. Int. J. High Perform. Comput. Appl. 20, 4 (November 2006), 481-494. DOI=10.1177/1094342006070078
[7] Tiago C. Ferreto, Marco A. S. Netto, Rodrigo N. Calheiros, and César A. F. De Rose. 2011. Server consolidation with migration control for virtualized data centers. Future Gener. Comput. Syst. 27, 8 (October 2011), 1027-1034. DOI=10.1016/j.future.2011.04.016 http://dx.doi.org/10.1016/j.future.2011.04.016

Contact : Eugen Feller, bureau E206 Vert, Eugen.Feller@inria.fr, tél: 02 99 84 72 68
Christine Morin, bureau E217 Vert, Christine.Morin@inria.fr, tél: 02 99 84 72 90

Start of page

Energy-Aware Distributed Ant Colony Based Virtual Machine Consolidation in IaaS Clouds

Advisors : Eugen Feller, Christine Morin

Keywords : energy management, cloud computing, infrastructure-as-a-service, swarm intelligence, ant colony optimization, workload consolidation, virtualization, scalability, fault-tolerance

Description
With the emerge of the Cloud computing paradigm and the associated need for more resources Cloud providers (e.g., Amazon, Google, Microsoft) have recently started to deploy increasing amounts of energy hungry data centers [4]. Still, the resource demand in those environments is usually of a bursty nature and thus results in a low average utilization of approximately 20-30% [7]. Therefore, a big fraction of the resources can be used to take energy conservation decisions such as consolidating the workload (i.e., virtual machines) on a subset of machines and suspending or turning off the resulting idle servers.

Given that ubiquitous virtualization solutions are able to live migrate the workload and servers can be turned on and off at any time, algorithms and frameworks can be designed in order to turn exists clusters into dynamic pools of virtualized resources. Therefor, virtual machine consolidation techniques can be utilized. Consolidation of virtual machines on the least number of physical nodes is an instance of the well known multi-dimensional bin-packing (MDBP) problem and has been studied in several works (e.g., [3], [8], [9]). Thereby, algorithms utilizing both exact (e.g., linear programming, constraint programming) as well as approximate (e.g., First-Fit, Best-Fit, Next-Fit, etc.) approaches have been proposed. However, all these techniques suffer from the same problem: high degree of centralization. Hence, there scalability and fault-tolerance is very limited. For example, both of the mentioned exact methods require a central instance to: (1) keep the model including a potentially large number of constraints in-memory and (2) compute the solution (i.e., virtual machine to host allocations). On the other hand, existing approximate solutions have similar drawbacks and require a central instance to compute the solution.

In order to overcome these drawbacks we have recently proposed to take a more distributed bio/natureinspired workload consolidation [2] approach based on the Ant Colony Optimization (ACO). In such a system agents (i.e., artificial ants) ideally work autonomously and do not require global system knowledge. Thus no single-point-of-failure (SPOF) exists and decisions are made based solely on the locally available monitoring information and indirect communication between the agents. The first simulation results have shown that the ACO-based workload consolidation is able to compute nearoptimal solutions. However, it was still formulated and implemented in a centralized manner. The internship will be divided into two main parts: In the first part, the intern will study the state of the art in both centralized and distributed ACO-based algorithms. Particularly, existing ACO-based approaches for solving bin-packing and related (e.g., graph coloring, subset selection) problems will be investigated. In the second part, the intern will design a distributed version of the ACO-based workload consolidation algorithm and implement it in our own simulator. Simulation-based experiments will be performed on the Grid5000 [12] testbed.

References :
[1] Christine Solnon and Derek Bridge. Chapter I An Ant Colony Optimization Meta-Heuristic for Subset Selection Problems. Retrieved from: http://liris.cnrs.fr/Documents/Liris-2279.pdf
[2] Eugen Feller, Louis Rilling, Christine Morin. 2011. Energy-Aware Ant Colony Based Workload Placement in Clouds. Research report (7622). Retrieved from: http://hal.inria.fr/inria-00594992/en/
[3] Fabien Hermenier, Xavier Lorca, Jean-Marc Menaud, Gilles Muller, and Julia Lawall. 2009. Entropy: a consolidation manager for clusters. In Proceedings of the 2009 ACM SIGPLAN/SIGOPS international conference on Virtual execution environments (VEE '09). ACM, New York, NY, USA, 41-50. DOI=10.1145/1508293.1508300 http://doi.acm.org/10.1145/1508293.1508300
[4] Greenpeace International. 2010. Make IT Green: Cloud Computing and its Contribution to Climate Change. Retrieved from: http://www.greenpeace.org/usa/Global/usa/report/2010/3/make-itgreen- cloud-computing.pdf
[5] John Levine and Frederick Ducatelle. 2003. Ant Colony Optimisation and Local Search for Bin Packing and Cutting Stock Problems. Journal of the Operational Research Society. Retrieved from: http://www.aiai.ed.ac.uk/~johnl/papers/levine-jors02.pdf
[6] Kathryn A. Dowsland and Jonathan M. Thompson. 2008. An improved ant colony optimisation heuristic for graph colouring. Discrete Appl. Math. 156, 3 (February 2008), 313-324. DOI=10.1016/j.dam.2007.03.025 http://dx.doi.org/10.1016/j.dam.2007.03.025
[7] Luiz Andre Barroso and Urs Hoelzle. 2007. The Case for Energy-Proportional Computing. Computer 40, 12 (December 2007), 33-37. DOI=10.1109/MC.2007.443 http://dx.doi.org/10.1109/MC.2007.443
[8] Mark Stillwell, David Schanzenbach, Frederic Vivien, and Henri Casanova. 2010. Resource allocation algorithms for virtualized service hosting platforms. J. Parallel Distrib. Comput. 70, 9 (September 2010), 962-974. DOI=10.1016/j.jpdc.2010.05.006
[9] Mark Stillwell, David Schanzenbach, Frederic Vivien, and Henri Casanova. 2009. Resource Allocation Using Virtual Clusters. In Proceedings of the 2009 9th IEEE/ACM International Symposium on Cluster Computing and the Grid (CCGRID '09). IEEE Computer Society, Washington, DC, USA, 260- 267. DOI=10.1109/CCGRID.2009.23 http://dx.doi.org/10.1109/CCGRID.2009.23
[10] Marco Dorigo, Gianni Di Caro, and Luca M. Gambardella. 1999. Ant algorithms for discrete optimization. Artif. Life 5, 2 (April 1999), 137-172. DOI=10.1162/106454699568728 http://dx.doi.org/10.1162/106454699568728
[11] Malika Bessedik, Rafik Laib, Aissa Boulmerka, and Habiba Drias. 2005. Ant Colony System for Graph Coloring Problem. In Proceedings of the International Conference on Computational Intelligence for Modelling, Control and Automation and International Conference on Intelligent Agents, Web Technologies and Internet Commerce Vol-1 (CIMCA-IAWTIC'06) - Volume 01 (CIMCA '05), Vol. 1. IEEE Computer Society, Washington, DC, USA, 786-791.
[12] Raphael Bolze, Franck Cappello, Eddy Caron, Michel Dayde;, Frederic Desprez, Emmanuel Jeannot, Yvon Jegou, Stephane Lanteri, Julien Leduc, Noredine Melab, Guillaume Mornet, Raymond Namyst, Pascale Primet, Benjamin Quetier, Olivier Richard, El-Ghazali Talbi, and Irea Touche. 2006. Grid'5000: A Large Scale And Highly Reconfigurable Experimental Grid Testbed. Int. J. High Perform. Comput. Appl. 20, 4 (November 2006), 481-494. DOI=10.1177/1094342006070078 http://dx.doi.org/10.1177/1094342006070078
[13] Suxin Wang, Leizhen Wang, Yanying Niu, and Meng Ge. 2009. Bin-packing multi-depots vehicle scheduling problem and its ant colony optimization. In Proceedings of the 21st annual international conference on Chinese control and decision conference (CCDC'09). IEEE Press, Piscataway, NJ, USA, 3765-3768.

Contact : Eugen Feller, bureau E206 Vert, Eugen.Feller@inria.fr, tél: 02 99 84 72 68
Christine Morin, bureau E217 Vert, Christine.Morin@inria.fr, tél: 02 99 84 72 90

Start of page

Performance Evaluation of Live Migration Over Distributed File Systems in IaaS Clouds

Advisors : Eugen Feller, Christine Morin

Keywords : distributed file systems, live migration, virtualization, cloud computing, performance evaluation, scalability, fault-tolerance

Description
Cloud computing has recently evolved as a new computing paradigm which promises virtually unlimited resources. Customers can rent resources based on the pay-as-you-go model and thus are charged only for as much as they have used. Thereby, resources are transparently provisioned by the cloud provider according to the customers requirements. For example, different types of virtual machine instances can be leased from existing public Infrastructure-as-a-Service (IaaS) cloud providers such as Amazon EC2 [1] or Rackspace [12] on demand.

Several open-source IaaS-cloud management frameworks (e.g., Eucalyptus [3], Nimbus [9], OpenNebula [4], OpenStack [10]) have been recently developed in order to provide alternatives to existing public cloud providers. Such frameworks can be used to either build private, public or hybrid clouds infrastructures. Thereby, virtualization technology is used in order to provide efficient resource usage. Consequently, virtual machines can be started by the users and are then managed by these frameworks.

One of the building blocks of any IaaS-cloud management software is live migration. Live migration is supported by most of the existing virtualization solutions (e.g., Xen [13], KVM [8]) and allows efficient (i.e., short downtime) virtual machine migration within a cluster. Given, that virtual machines can be live migrated, different advanced scheduling policies (e.g., workload consolidation for energysavings) can be implemented.

In order to provide efficient live migration typically the same shared storage is assumed to be mounted on all the cluster nodes. Therefor, currently mostly the Network-File-System (NFS) is used (see [9]) which is known to have a very limited scalability and fault-tolerance. Therefore, it is not suitable to serve as the storage backed for current and future large-scale IaaS-cloud management frameworks with live migration support.

As part of our work to provide energy-efficiency, scalability and fault-tolerance to IaaS-clouds we have developed a first prototype of the energy-aware, hierarchical and distributed IaaS-coud management software called Snooze [5]. Snooze is made to scale across many thousands of servers and virtual machines. However, currently the NFS-based virtual machine data storage backend becomes the bottleneck of the system.

The internship will be divided into two main parts: In the first part, the intern will study the state of the art in distributed file systems. Particularly, existing distributed file systems (e.g., XtreemFS [6], Hadoop [7], BlobSeer [2]) will be analyzed with respect to live migration support. In the second part, the intern will conduct a live migration performance evaluation on top of the selected file systems and compare those with the state-of-the-art solution (i.e., NFS). Real-life experiments will be conducted utilizing the Snooze IaaS-cloud management framework on the Grid 5000 [11] testbed.

References :
[1] Amazon EC2. http://aws.amazon.com/ec2/
[2] Bogdan Nicolae, Gabriel Antoniu, Luc Bouge, Diana Moise, and Alexandra Carpen-Amarie. 2011. BlobSeer: Next-generation data management for large scale infrastructures. J. Parallel Distrib. Comput. 71, 2 (February 2011), 169-184. DOI=10.1016/j.jpdc.2010.08.004 http://dx.doi.org/10.1016/j.jpdc.2010.08.004
[3] Daniel Nurmi, Rich Wolski, Chris Grzegorczyk, Graziano Obertelli, Sunil Soman, Lamia Youseff, and Dmitrii Zagorodnov. 2009. The Eucalyptus Open-Source Cloud-Computing System. In Proceedings of the 2009 9th IEEE/ACM International Symposium on Cluster Computing and the Grid (CCGRID '09). IEEE Computer Society, Washington, DC, USA, 124-131. DOI=10.1109/CCGRID.2009.93 http://dx.doi.org/10.1109/CCGRID.2009.93
[4] Dejan Milojicic, Ignacio M. Llorente, and Ruben S. Montero. 2011. OpenNebula: A Cloud Management Tool. IEEE Internet Computing 15, 2 (March 2011), 11-14. DOI=10.1109/MIC.2011.44 http://dx.doi.org/10.1109/MIC.2011.44
[5] Eugen Feller, Louis Rilling, Christine Morin, Renaud Lottiaux, and Daniel Leprince. 2010. Snooze: A Scalable, Fault-Tolerant and Distributed Consolidation Manager for Large-Scale Clusters. In Proceedings of the 2010 IEEE/ACM Int'l Conference on Green Computing and Communications & Int'l Conference on Cyber, Physical and Social Computing (GREENCOM-CPSCOM '10). IEEE Computer Society, Washington, DC, USA, 125-132. DOI=10.1109/GreenCom-CPSCom.2010.62 http://dx.doi.org/10.1109/GreenCom-CPSCom.2010.62
[6] Felix Hupfeld, Toni Cortes, Bjoern Kolbeck, Jan Stender, Erich Focht, Matthias Hess, Jesus Malo, Jonathan Marti, and Eugenio Cesario. 2008. The XtreemFS architecture\—a case for object-based file systems in Grids. Concurr. Comput. : Pract. Exper. 20, 17 (December 2008), 2049-2060. DOI=10.1002/cpe.v20:17 http://dx.doi.org/10.1002/cpe.v20:17
[7] Feng Wang, Jie Qiu, Jie Yang, Bo Dong, Xinhui Li, and Ying Li. 2009. Hadoop high availability through metadata replication. In Proceeding of the first international workshop on Cloud data management (CloudDB '09). ACM, New York, NY, USA, 37-44. DOI=10.1145/1651263.1651271 http://doi.acm.org/10.1145/1651263.1651271
[8] KVM. http://www.linux-kvm.org/
[9] Nimbus. http://www.nimbusproject.org
[10] OpenStack. http://www.openstack.org/
[11] Raphael Bolze, Franck Cappello, Eddy Caron, Michel Dayde;, Frederic Desprez, Emmanuel Jeannot, Yvon Jegou, Stephane Lanteri, Julien Leduc, Noredine Melab, Guillaume Mornet, Raymond Namyst, Pascale Primet, Benjamin Quetier, Olivier Richard, El-Ghazali Talbi, and Irea Touche. 2006. Grid'5000: A Large Scale And Highly Reconfigurable Experimental Grid Testbed. Int. J. High Perform. Comput. Appl. 20, 4 (November 2006), 481-494. DOI=10.1177/1094342006070078 http://dx.doi.org/10.1177/1094342006070078
[12] Rackspace. http://www.rackspace.com/
[13] Xen. http://xen.org/

Contact : Eugen Feller, bureau E206 Vert, Eugen.Feller@inria.fr, tél: 02 99 84 72 68
Christine Morin, bureau E217 Vert, Christine.Morin@inria.fr, tél: 02 99 84 72 90

Start of page

Application adaptation to dynamic pricing in private clouds

Advisors : Stefania Costache, Nikos Parlavantzas, Christine Morin

Keywords : cloud computing, adaptation, market-based resource management

Description
Cloud computing is increasingly gaining popularity as it enables users to provision computing resources on-demand while paying for their use [1]. This paradigm relies on the use of virtualization technologies to provide users with private environments that can be customized by need. Users can elastically scale these environments by adding more resources when needed. "Private cloud" systems attempt to bring these advantages to private infrastructures. However, current resource provisioning models applied by these cloud systems do not provide users with enough feedback about the resource availability of the physical infrastructure. As the infrastructure capacity is limited, users require this feedback to know how many resources they are allowed to use, while the infrastructure needs to differentiate between the importance of their requests.

To address this problem, we propose to provision virtual machines (VMs) to users through a proportional-share auction [2]. This model allocates to each VM an amount of resource (i.e., CPU) proportional to the amount that the user is willing to pay and inversely proportional to the total resource price [3]. To validate this model, we have implemented a proof-of-concept scheduler on top of the OpenNebula [4] Virtual Infrastructure Manager. When using this model, a key challenge is how to react to changes in market prices to meet application performance requirements (e.g., deadlines).

The objective of this internship is to add support for meeting application performance goals on top of the proportional-share scheduler. Specifically, the student will investigate methods to adapt the bids submitted by users given the application goals as well as the user's budget constraints. The first step of the internship will be to analyze the current state of art for executing applications under budget and QoS constraints in clouds. Then the student will select one, or possibly two, application types and design new bidding strategies to dynamically adapt the application resource requests. For example, one popular application type that we will consider is MapReduce applications [5]. The last step of the internship will be to test these strategies by implementing an agent that monitors the application's performance and adapts its resource requests accordingly.

References:

[1] AmazonEC2. http://aws.amazon.com/ec2/
[2] S. Costache, N. Parlavantzas, C. Morin and S. Kortas, An economic approach for Application QoS Management in Clouds, Europar 2011, Parallel Processing Workshops, 2011
[3] T. Sandholm and K. Lai. Dynamic proportional share scheduling in Hadoop. In 15th Workshop on Job Scheduling Strategies for Parallel Processing, 2010
[4] B. Sotomayor, R. Montero, I. Llorente, and I. Foster. An Open Source Solution for Virtual Infrastructure Management in Private and Hybrid Clouds. IEEE Internet Computing, 13(5):14–22, 2009.
[5] J. Dean and S. Ghemawat, “MapReduce: Simplified Data Processing on Large Clusters,” in 6th Symposium on Operating Systems Design and Implementation, 2004, pp. 137–149.

Contact : Stefania.Costache@inria.fr, Nikos.Parlavantzas@irisa.fr, Christine.Morin@inria.fr

Start of page

Multi-resource proportional-share allocation for private clouds

Advisors : Stefania Costache, Nikos Parlavantzas, Christine Morin

Keywords : cloud computing, resource management, proportional-share auctions

Description
Cloud computing is increasingly gaining popularity as it enables users to provision computing resources on-demand while paying for their use [1,2]. This paradigm relies on the use of virtualization technologies to provide users with private environments that can be customized by need. Users can elastically scale these environments by adding more resources when needed. "Private cloud" systems attempt to bring these advantages to private infrastructures. However, current resource provisioning models applied by these cloud systems do not provide users with enough feedback about the resource availability of the physical infrastructure. As the infrastructure capacity is limited, users require this feedback to know how many resources they are allowed to use, while the infrastructure needs to differentiate between the importance of their requests.

One approach that we see as an attractive alternative to current models is to provision VMs to users through a proportional-share auction [3]. In this model we allocate to each VM an amount of resource (i.e., CPU) proportional to the amount that the user is willing to pay and inversely proportional to the total resource price [4]. To validate this model, we have implemented a proof-of-concept scheduler on top of the OpenNebula [5] Virtual Infrastructure Manager. This scheduler uses a simple heuristic to allocate resources for each requested VM by using the proportional-share rule described above.

The main goal of this internship is to analyze the existing proportional-share allocation mechanism and extend it to handle multiple resource types beyond CPU. In the first stage, the intern will study the state of the art on VM placement algorithms in datacenters [6,7]. Afterwards, the intern will analyze the existing algorithm in terms of the resource share that VMs actually receive. Following that and based on the related work, the intern will propose an improved algorithm that maximizes the resource allocation for multiple resource types (i.e., memory and network) and takes into account the cost of VM migration. Finally, the intern will implement and integrate the algorithm in the existing scheduler.

References:

[1] AmazonEC2. http://aws.amazon.com/ec2/
[2] http://aws.amazon.com/ec2/spot-instances/
[3] T. Sandholm and K. Lai. Dynamic proportional share scheduling in Hadoop. In 15th Workshop on Job Scheduling Strategies for Parallel Processing, 2010.
[4] S. Costache, N. Parlavantzas, C. Morin and S. Kortas, An economic approach for Application QoS Management in Clouds, Europar 2011, Parallel Processing Workshops, 2011
[5] B. Sotomayor, R. Montero, I. Llorente, and I. Foster. An Open Source Solution for Virtual Infrastructure Management in Private and Hybrid Clouds. IEEE Internet Computing, 13(5):14–22, 2009.
[6] F. Hermenier, X. Lorca, and J.M. Menaud. Entropy: a consolidation manager for clusters. In Proceedings of the 2009 ACM SIGPLAN/SIGOPS international conference on Virtual Execution Environments, 2009.
[7] M. Stillwell, F. Vivien, and H. Casanova. Dynamic fractional resource scheduling for HPC workloads. In Proceedings of the 2010 IEEE International Symposium on Parallel and Distributed Processing (IPDPS), 2010

Contact : Stefania.Costache@inria.fr, Nikos.Parlavantzas@irisa.fr, Christine.Morin@inria.fr

Start of page

Algorithmes efficaces de recherche dans une machine chimique pair-à-pair

Advisors : Cédric Tedeschi

Keywords : Algorithmique distribuée, Calcul chimique, systèmes pair-à-pair

Description
Les ressources de calcul mondialement distribuées offrent aujourd'hui une capacité de calcul qui reste largement inexploitée. Programmer cette plate-forme globale de calcul apparue au-dessus de l'Internet fait apparaître de nouveaux challenges. Les ressources sont hétérogènes, géographiquement distribuées et offrent un niveau de fiabilité très disparate. Afin de rendre cette plate-forme exploitable, il est nécessaire de repenser les paradigmes de programmations traditionnels, et y injecter des propriétés telles que l'auto-organisation et la décentralisation.

Le paradigme de programmation chimique [1] a été récemment identifié comme une piste prometteuse pour la programmation de systèmes autonomes [2]. Dans ce paradigme, les calculs sont vus comme des réactions chimiques apparaissant de façon autonomes et parallèles parmi les molécules de données afin de produire une nouvelle molécule résultat. Le langage HOCL [3] implémente ces concepts et fournit l'ordre supérieur (les règles régissant les réactions peuvent elle même être réécrite dynamiquement par d'autres règles.) Exécuter des programmes chimiques sur une plate-forme distribuée se fait à travers une structure logiquement partagée, appelée multi-ensemble, contenant les molécules du calcul.

Des travaux récents ont initié la construction d'un tel multi-ensemble dans une plate-forme dynamique à large échelle, en se basant sur des technologies pair-à-pair de type "gossip" [4,5], qui montrent des bonnes propriétés de passage à l'échelle et de tolérance aux pannes, et qui permettraient donc de sous-tendre une telle machine chimique distribuée. Toutefois, rendre efficace cette plate-forme ouvre de nombreux challenges en termes d'algorithmique distribuée. En effet, retrouver des molécules d'un type particulier, ou satisfaisant une condition particulière à large échelle, reste un problème difficile. Le travail de l'étudiant consistera en la proposition et l'expérimentation de stratégies permettant la recherche efficace de molécules au-dessus d'une plate-forme de type "gossip".

Une poursuite en thèse est envisageable.

Bibliographie:

Sur le paradigme de programmation chimique:
[1] J.-P. Banâtre, A. Coutant, D. Le Métayer. A Parallel Machine for Multiset Transformation and its Programming Style. Future Generation Computer Systems. 4(2):133-144, 1988.
[2] J.-P. Banâtre, P. Fradet, Y. Radenac. Chemical Specification of Autonomic Systems. In 13th International Conference on Intelligent and Adaptive Systems and Software Engineering (IASSE 2004).
[3] J.-P. Banâtre, P. Fradet, Y. Radenac. Generalised Multisets for Chemical Programming. Mathematical Structures in Computer Science 16(4), 2006.

Sur les protocoles de dissémination de l'information pair-à-pair:

[4] R. Guerraoui, S. Handurukande, K. Huguenin, A.-M. Kermarrec, F. Le Fessant, E. Riviere. GosSkip: an Efficient, Fault-Tolerant and Self Organizing Overlay Using Gossip-based Construction and Skip-Lists Principles. In 6th IEEE International Conference on Peer-to-Peer Computing (P2P 2006).
[5] M. Bertier, Y. Busnel, A.-M. Kermarrec. On gossip and populations. In 16th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2009).

Contact : Cedric Tedeschi - Université de Rennes 1/INRIA Rennes Bretagne Atlantique Campus de Beaulieu, Rennes

Start of page

Une approche chimique pour la composition de services à large échelle

Advisors : Cédric Tedeschi, Jean-Louis Pazat

Keywords : Algorithmique distribuée, workflows, découverte de services, ordonnancement, adaptation

Description
Avec l'explosion de la quantité des ressources matérielles et logicielles disponibles, calculer à large échelle s'appuie sur de nouveaux concepts et méthodes, dont l'un des axes principaux est les architectures orientées services: toute entité digitale (espace de stockage, application distante, capteur, ...) est utilisé à travers un service. Il suffit de vous connecter à votre appStore favori pour expérimenter ce nouveau paradigme. Du point de vue de la conception des applications, cela entraîne une nouvelle façon de considérer les logiciels: ils sont de plus en plus fondé sur la composition de ces services, faite dynamiquement en fonction des requêtes d'utilisateurs au bord de l'Internet, par exemple lors de l'organisation de voyages, en s'appuyant sur un service de réservation d'hôtel, un service d'achat de billets d'avions, un service de facturation, etc. Une telle composition est aussi nommée workflow.

Les modèles actuels permettant de gérer cette multitude de workflows à satisfaire simultanément font des hypohtèses très lourdes (service de découverte des services, gestion des ressources centralisées) les randant peu viable à long terme, en raison de leur faible tolérance aux pannes et de leur extensibilité limitée (expérimentée régulièrement sur l'Internet). Avec l'ouverture et l'extension de ces architectures orientées service, il est nécessaire d'envisager une gestion totalement décentralisée et autonome de l'instanciation (découverte des services) et de leur exécution (auto-adaptation, auto-réparation).

Une approche possible est de s'appuyer sur une analogie issue de la nature, qui montre des propriétés similaires à celles recherchées dans notre cas: émergence de propriétés gloables à partir d'interactions locales, auto-adaptation, auto-réparation, etc. En particulier, les modèles d'inspiration chimique [1] dans lesquels les programmes sont vus comme un ensemble de molécules interagissant échangeant de l'information pour en créer de la nouvelle, semblent bien correspondre [2]. Récemment, ces modèles sont devenus plus concrets, avec la définition de langages d'ordre supérieur, comme HOCL [3], permettant de modéliser des systèmes très dynamiques et autonomes.

L'objectif du stage est de proposer un modèle d'instanciation et d'exécution de workflow totalement décentralisé en s'appuyant sur les abstractions des modèles de calcul d'inspiration chimique. Sa mise-en-oeuvre dans des environnements de simulation ou d'expérience à large échelle telle que la plateforme Grid'5000 pourront permettre sa validation.

Bibliographie:

Sur le paradigme de programmation chimique:
[1] Peter Dittrich, Jens Ziegler, Wolfgang Banzhaf: Artificial Chemistries-A Review. Artificial Life 7(3): 225-275 (2001)
[2] J.-P. Banâtre, P. Fradet, Y. Radenac. Chemical Specification of Autonomic Systems. In 13th International Conference on Intelligent and Adaptive Systems and Software Engineering (IASSE 2004).
[3] J.-P. Banâtre, P. Fradet, Y. Radenac. Generalised Multisets for Chemical Programming. Mathematical Structures in Computer Science 16(4), 2006.

Sur les architectures orientées service:
[4] Michael N. Huhns and Munindar P. Singh, "Service-Oriented Computing: Key Concepts and Principles", IEEE Internet Computing, vol. 9, no. 1, pp. 75-81, 2005.

Contact : Cedric Tedeschi, Jean-Louis Pazat - IRISA, Campus de Beaulieu, Rennes

Start of page