Fabienne Anhalt

Sebastien Soudan

Marcos Dias De Assunção

Augustin Ragon

Philippe Martinez

Romaric Guillier

Suleyman Baikut

Hugo Caro

Ghislain Landry

Ludovic Hablot

Anne-Ccile Orgerie

Sylvie Boyer

Thomas Begin

Tram Truong Huu

Johan Montagnat

Cédric Westphal

Wai-Leong Marcelo Yeow

Pasin

a special thanks. This friend has guided me to my PhD, in addition to helping me getting settled in Lyon.

Considering my

List of Figures

 5.6The physical substrate that must allocate the VI described in Figure 5.5 comprises components hierarchically distributed and interconnected. . . . . 97 5.7 A subgraph-isomorphism mapping between G v (5.7a) and G p (5.7b) given by the application of a function f , where

f (r v A) = r p 3, f (r v B) = r p 2, f (r v C) = r p 6, f (l v A) = l p 2, f (l v B) = l p 3 ∪ l p 5, f (l v C) = l p 6,

xiii

A language for describing virtual infrastructures: We propose the Virtual Infrastructure Description Language (VXDL) as a descriptive and declarative language that allows users and systems to completely describe the relevant components of a virtual infrastructure, including the set of virtual resources, the network topology, and the organization of the internal timeline [START_REF] Koslovski | VXDL: Virtual Resources and Interconnection Networks Description Language[END_REF] [START_REF] Anhalt | Specifying and provisioning Virtual Infrastructures with HIPerNET[END_REF]. The main advantages of such language are to abstract the request formulation from the effective provisioning and thus increase the application portability. VXDL has been proven to be an efficient solution for describing VIs, being adopted by several applications and solutions for provisioning dynamic VIs. In addition, an open forum for discussions and improvements is being launched (http://www.vxdlforum.org/). This forum will allow developers and InPs to exchange experiences, suggestions, and extensions, guiding the standardization of VXDL.

Specifying and executing distributed applications: The execution of a distributed application is facilitated by a mechanism for translating workflows into VI specifications.

The mechanism extracts information from workflows and combines it with the users' expertise on the application's behavior. Both node and network requirements are addressed.

For a proof of concept, a large-scale distributed application has been executed atop VIs provisioned following different specifications. The results highlight the importance and impact of data location and proximity of virtual nodes [START_REF] Koslovski | Executing distributed applications on virtualized infrastructures specified with the VXDL language and managed by the HIPerNET framework[END_REF]. In addition, the capability of specifying elastic VIs results in an efficient tradeoff between cost and performance [START_REF] Truong Huu | Joint elastic cloud and virtual network framework for application performance optimization and cost reduction[END_REF].

Allocating resources to virtual infrastructures: We propose an approach to reduce the search space in an automatic and efficient way, accelerating the process of VI allocation and finding an effective mapping solution. In addition, our allocation algorithm exploits attributes defined in VXDL, and is guided by a problem formulation that reconciles the perspectives of both users and InPs. Experimental results have shown that by using our optimized algorithm, the objectives of InPs and users are satisfied [4] [VXAlloc] [VXCap].

Providing reliable virtual infrastructures: Finally, we propose and develop a mechanism where a user can delegate the reliability expectations of his application to the InP, contracting a transparent service. By using VXDL, each VI component can request a specific level of reliability. The internal InP mechanism translates these requirements into the effective number of replica nodes and links that must be provisioned together with the original VI. The results demonstrate that when a failure happens the service automatically activates the replica nodes, keeping the entire reliability management completely transparent to the running application [START_REF] Koslovski | Reliability support in virtual infrastructures[END_REF].

R ésum é

L e concept d'Infrastructures Virtuelles (VI, ou Virtual Infrastructures), approvisionnées dynamiquement, a émergé récemment suite la combinaison de l'approvisionnement de ressources informatiques (consolidés par le calcul dans le nuage) d'une part, et des réseaux virtuels dynamiques (introduits par les réseaux de nuage) d'autre part. Grâce la virtualisation combinée des ressource de calcul et de réseau pour l'approvisionnement dynamique de services, le concept de VI a transform l'Internet en un réservoir mondial de ressources interconnectées, où des services de calcul, de stockage et de communication sont disponibles á la demande, pour des utilisateurs et applications avec des besoins différents.

Une VI est un infrastructure de calcul et de réseau complètement virtualisée, qui est approvisionnée et gérée par un Infrastructure Provider (InP) ou fournisseur d'infrastructure en français. Pendant sa durée de vie, le contrôle sur la VI est transféré á l'utilisateur émetteur de la requête, qui a désormais le contrôle total sur cette agrégation des ressources de calcul et de réseau. Plusieurs projets ont proposé des mécanismes pour créer, allouer, déployer et gérer des machines, liens, commutateurs et routeurs, afin de pouvoir composer et fournir des infrastructures virtuelles isolées ayant une durée de vie limitée.

Avec l'innovation des VIs viennent aussi un ensemble de nouveaux défis nécessitant le développement de nouveaux modèles, technologies et procédures, pour assister la migration d'applications et de services existants d'infrastructures traditionnelles vers des VIs. L'abstraction complète des ressources physiques et de la topologie réseau, et l'indéterminisme dans les besoins des applications en termes de ressources de calcul et de communication ont fait de la spécification et de la composition de VI un problème difficile. En outre, l'allocation efficace d'un ensemble de plusieurs VIs sur un substrat physique distribué à grande échelle est un problème NP-hard. En plus de considérer les objectifs traditionnels des VIs (par exemple un usage efficace du substrat physique, un cout minimal, un revenu croissant), un algorithme d'allocation efficace doit également satisfaire les attentes des utilisateurs (par exemple la qualité de l'allocation, la localisation des données et la mobilité).

Ce manuscrit contribue aux initiatives de recherche en cours et est organisées autour des propositions suivantes :

Un langage pour décrire des infrastructures virtuelles : nous proposons VXDL (pour Virtual Infrastructure Description Language -langage de description d'infrastructures virtuelles), qui permet aux utilisateurs et aux systèmes de décrire entièrement les composants pertinents d'une infrastructure virtuelle, comprenant un ensemble de ressources virtuelles, leur topologie réseau et leur organisation temporelle [START_REF] Koslovski | VXDL: Virtual Resources and Interconnection Networks Description Language[END_REF] [START_REF] Anhalt | Specifying and provisioning Virtual Infrastructures with HIPerNET[END_REF]. VXDL est reconnu comme étant une solution efficace pour décrire des infrastructures virtuelles. Il est adopté par plusieurs applications pour approvisionner des VIs dynamiques. De plus, un forum ouvert de discussions pour la progression du langage est en cours de développement (http://www.vxdlforum.org/). Ce forum permettra aux développeurs et aux InPs d'échanger leurs expériences, suggestions et propositions d'extensions, pour conduire VXDL à la standardisation.

Spécification et exécution d'applications distribuées : l'exécution d'applications distribuées est facilitée par un mécanisme qui traduit un flux de travail en une spécification de VI. Ce mécanisme extrait l'information nécessaire des flux de travail pour la combiner avec l'expertise qu'a l'utilisateur sur le comportement de l'application. Cela répond aux besoins la fois des noeuds de calcul et du réseau. Pour valider ce concept, une application distribuée à large échelle est exécutée plusieurs fois dans des VIs, approvisionnées selon différentes spécifications à chaque fois. Les résultats mettent en évidence l'importance et l'impact de la localisation des données et de la proximité entre noeuds virtuels [START_REF] Koslovski | Executing distributed applications on virtualized infrastructures specified with the VXDL language and managed by the HIPerNET framework[END_REF]. De plus, la possibilité de spécifier des VIs élastiques permet d'aboutir à un meilleur compromis entre coût et performance [START_REF] Truong Huu | Joint elastic cloud and virtual network framework for application performance optimization and cost reduction[END_REF].

Allocation d'infrastructures virtuelles : une solution d'allocation est développée pour réduire l'espace de recherche d'une façon automatique et efficace. Elle accélère le processus d'allocation et trouve une solution d'allocation efficace. Cette solution a été brevetée. De plus, notre algorithme d'allocation exploite les attributs proposés dans VXDL. Il est guidé par la formulation du problème qui prend en compte à la fois le point de vue des utilisateurs et celui des InPs. Des résultats expérimentaux montrent qu'en utilisant notre algorithme optimisé, les objectifs des InPs ainsi que ceux des utilisateurs sont satisfaits [4] [VXAlloc] [VXCap].

Fournir des infrastructures fiables : la fiabilité devient un service offert par des InPs. Nous proposons et développons un mécanisme, avec lequel un utilisateur peut déléguer les besoins en fiabilité de son application à l'InP, en souscrivant à un service de fiabilité qui est transparent pour lui-même. En utilisant VXDL, chaque composant d'une VI peut demander un niveau de fiabilité spécifique. Le mécanisme, interne à l'InP, traduit ces niveau de fiabilité en le nombre effectif de répliques de noeuds et de liens qui doivent être approvisionnés en même temps que la VI de base. Des résultats d'expérience montrent que lorsqu'une défaillance se produit, le service active automatiquement les répliques des noeuds, tout en gardant la gestion de la fiabilité complètement transparente pour les applications en cours d'exécution [START_REF] Koslovski | Reliability support in virtual infrastructures[END_REF].

-ONE -

T

he Internet is constantly evolving, metamorphosing from a communication network into a computation-and-communication system. Nowadays, users can reserve and utilize resources and services on a pay-as-you-go basis according to their applications' requirements [Buyya, 2009]. The maturity of resource virtualization and Grid technologies has contributed to the emergence of virtualized infrastructures and business models such as Cloud Computing, which allow users to tap into a virtually unlimited reservoir of resources [START_REF] Rochwerger | The RESERVOIR Model and Architecture for Open Federated Cloud Computing[END_REF].

Cloud Computing comes at various shapes and flavors, where typically different layers of an Information Technology (IT) infrastructure are virtualized and delivered to end users as services. Examples include Software as a Service (SaaS), Platform as a Service (PaaS), and Infrastructure as a Service (IaaS). By renting only the resources that they need, when they need, small organizations can reduce their costs with IT infrastructure as they no longer need to spend on buying and managing their own servers. In fact, more and more companies have opted to outsource their IT infrastructure to Cloud providers [START_REF] Rosenberg | The Cloud at Your Service[END_REF].

Until recently, several infrastructures virtualized only server and storage resources, and paid little attention to network. Cloud Networking has changed this scenario by enabling dynamic provisioning of virtual links to interconnect virtual server components. A combination of Cloud Computing and Cloud Networking allows for the creation of entirely virtualized infrastructures (e.g., IT and network) atop a distributed physical substrate. A Virtual Infrastructure (VI) is a fully virtualized IT infrastructure that appears to be physical, but in reality, shares the underlying physical substrate with other VIs during a given time frame.

A VI can be formulated as a graph of computing and communication resources that carries substantial information. The virtual IT or network components are the vertices (e.g., nodes, routers, storage), interconnected by a set of virtual links, the edges. The dynamic provisioning of virtualized resources enables each component of a VI to vary its capacity during its lifetime. Moreover, a component can be present only in specific stages of a VI's lifetime. The resulting VI graph is a malleable and elastic entity, composed and modeled according to users' and applications' requirements.

VIs have a well-defined lifecycle composed of specification, allocation, provisioning, and release. For illustrating the use of VIs, the bottom part of Figure 1.1 presents a physical substrate as a combination of several virtualized resources. In this example, three Cloud providers are exposing their resources to the management framework. At the top, a user (e.g., person, institution, or enterprise) wants to run his legacy application (e.g., scientific application, meeting platform, game, corporate control software) in the Cloud. The application, which used to run on a physical substrate (e.g., clusters, Grids, private data centers), now has to migrate to execute on a virtualized infrastructure that is dynamically provisioned, and where each execution is charged according to the resource usage. The VI specification is submitted to a management framework responsible for provisioning the virtual resources according to the user's specifications. The framework knows about the capacities of available resources that compose the distributed physical substrate. With this information, the framework can allocate, provision, and control the VI during its lifetime.

Provisioning a VI poses a series of challenges due to: i) the indeterminism of the required VI composition for running a legacy application efficiently; ii) the abstraction of existing computational power, architecture, and geographical location; and iii) the lack of specific tools to describe and manage VIs, that consider their dynamic aspect.

Problem and objectives

The composition and usage of VIs, and the management of virtualized physical substrates are challenging tasks because although a VI is a simple entity, its virtual resources can be defined in a complex manner, carrying substantial information. By being elastic, a VI can vary its configuration, capacities, and usage on the fly. In addition, virtual resources are mobile and can move around the physical substrate.

Moreover, users who used to know their applications' behavior on physical substrates and are now migrating to the Cloud, have difficulty in defining an efficient VI composition to execute their applications. Different from a private infrastructure, in the Cloud, users have to find the tradeoff between cost and application performance before submitting the application.

From the Infrastructure Providers' (InPs) perspective, allocating and provisioning VIs are not trivial operations. Allocating resources is a complex step of the VI's lifecycle because finding an optimal mapping solution between virtual and physical resources (represented as graphs) is an NP-hard problem [Chowdhury and Boutaba, 2009]. Besides to find a satisfactory solution (considering the InP objectives) in an acceptable response time, an efficient heuristic must consider the user's expectations.

New models and tools are required to ease the composition of VI's specification, translating the abstract application requirements in well-defined attributes for composing the virtual resources. Several approaches from different projects have investigated the management of VIs [GEN] [HIP] [SAI] [GEY], but some key-points still require research and engineering efforts. We identified four key open questions characterizing the main objectives of this thesis:

1. A declarative language capable of easing the specification of distributed applications is required. A representative model should consider the different aspects of IT and network virtualization, describing their functionalities and composition. The dynamic and elastic aspects of VIs must be considered in the descriptive process. Today, Cloud providers are representing, describing, and requesting virtual resources thanks to different application programming interfaces.

2. Models, mechanisms, and tools for simplifying the VI manipulation. As users are migrating their applications from traditional infrastructures (e.g., clusters, Grids, private data centers) to a virtualized and often external substrate based on dynamic provisioning, new models and tools are required to ease the composition of VIs, translating the abstract application requirements into defined attributes to compose virtual resources.

3.

A solution for allocating VIs considering both users' and InPs' expectations. Finding an efficient mapping between the users' requirements and the substrate objectives is not trivial. In addition, the VI concept brings new objectives and expectations for the formulation of the allocation problem: i) the elasticity aspect of virtual resources; ii) the user's expectations in terms of application efficiency and quality of experience; iii) and the on-demand provisioning including pay-as-you-go model.

4.

Reliability as a Service. The on-demand service provisioning model explored by InPs leaves opportunities for the creation of new services. The provisioning of new services generally aggregates revenue for InPs, while facilitates the development and execution of complex applications. For example, a physical resource (IT or networking) is subject to the occurrence of random failures. Consequently, a VI allocated on top of a virtualized physical substrate can be also affected by physical failures. Some applications are critical and cannot tolerate failures as the absence of a single physical resource can compromise the whole execution. In addition, in a pay-as-you-go execution model, users have no control of the physical substrate, and usually have no information to treat and prevent failures.

These four open questions are routing the contributions of this thesis.

Contributions

Considering the challenges of the previously defined research issues, and defining VIs as the key entity manipulated in this work, we summarize our contributions in four main areas: i) the creation of a language for describing VIs; ii) the application and validation of the language with a distributed application; iii) efficient algorithms for allocating virtual infrastructures onto virtualized and distributed physical substrate; and iv) the proposition of VI's reliability as a service. Figure 1.2 presents the four contributions as they are distributed over the chapters, describing their interaction and workflow. User input is dealt with at the highest level. A user should be located on top of the highest level, contributing with his application and expertise, and below at the bottom level, a distributed and virtualized physical substrate is present to receive the user VI. This thesis contributions are the intermediate layers, as describe below:

Virtual Infrastructure Description Language (VXDL): The Virtual Infrastructure Description Language (VXDL) enables the description of virtual infrastructures [START_REF] Koslovski | VXDL: Virtual Resources and Interconnection Networks Description Language[END_REF]. By using VXDL, a VI can be described and modeled defining the exact requirements in terms of computing resource and network configuration [1] [8]. In addition, VXDL includes elastic and dynamic aspects of VIs and is constructed for enabling an allocation and provisioning of the VI guided by users. By defining some cross-layer attributes, users can interact with the service provisioning, indicating rules and requirements which are indispensable for the efficient execution of their applications. The descriptive capacity of VXDL has been demonstrated through use cases that represent real scenarios. Furthermore, a set of tools have explored VXDL as the main language for describing VIs [LYaTiss, 2011] [MOT].

Specifying VIs for executing distributed applications: As users migrate their applications to the Cloud, a facilitator mechanism is highly required to translate the application's requirements into VXDL documents. For translating workflow-based applications into VI specifications, we propose a mechanism whose translation strategies extract information (e.g., data dependency, execution sequence) from a workflow combining it with the application behavior (given by results of micro-benchmarks and user's expertise) composing VI specifications [START_REF] Koslovski | Executing distributed applications on virtualized infrastructures specified with the VXDL language and managed by the HIPerNET framework[END_REF].

A real large-scale distributed application is translated into different VXDL documents, which are them submitted to a management framework. An analysis is performed by comparing the results of the application when executed on top of different VIs. The analysis highlight that an optimal VI composition is essential for finding a good tradeoff between provisioning cost and application performance [START_REF] Truong Huu | Joint elastic cloud and virtual network framework for application performance optimization and cost reduction[END_REF], and the results show the importance of data and nodes location when executing the application inside a VI [START_REF] Koslovski | Executing distributed applications on virtualized infrastructures specified with the VXDL language and managed by the HIPerNET framework[END_REF].

Allocating resources to Virtual Infrastructures: As VXDL introduced attributes with which the user can define the behavioral rules (e.g., capacity and composition can vary), and enabled the definition of specific allocation constraints (e.g., a specific location, disabling the resource sharing, and composing shared risk groups), the VI allocation problem becomes also controllable by the user, and not only by the InPs. As a consequence, both users' and InPs' perspectives must be combined into the problem formulation. We formulate the VI allocation problem considering both perspectives and develop an allocation algorithm guided by these constraints and objectives [4]. The results show that our allocation algorithm reduces the costs and substrate fragmentation while guaranteeing the allocation quality. Reliable Virtual Infrastructures: Following the current reservation and execution model, the provisioning of reliable virtual resources becomes a service provided by the InP. We propose and develop a mechanism capable of interpreting the reliability requirements (specified within VXDL) and compose a reliable virtual infrastructure. VXDL acts as a participant in the Service Level Agreement (SLA) composition. The reliability level requested for each component is translated into the effective number of replicas that must be dynamically provided to guarantee the user's requirements. When a failure occurs, a replica automatically assumes the execution of the resource that failed. The recovery process is abstracted from the user.

The service is evaluated by executing a distributed application with different requirements of reliability level. The results identify the cost for provisioning, and perform a comparison between the reliable service and the application level reliability support [START_REF] Koslovski | Reliability support in virtual infrastructures[END_REF].

Thesis organization

This manuscript is organized as follow. Chapter 2 reviews the literature on the techniques and concepts related to virtual infrastructures. Chapter 3 presents our language for describing VIs. Techniques to translate workflow-based applications into VI requirements are described in Chapter 4. The execution of a large-scale distributed application is presenting as a validation of the proposition. Chapter 5 presents our algorithms for allocating virtual infrastructures. In Chapter 6, a mechanism for providing reliable virtual infrastructures as a service is introduced. Finally, Chapter 7 concludes and presents perspectives for future work.

-TWO - Part of the contents of this chapter was published at the International Journal of Network Management -special issue on Network Virtualization and its Management (IJNM 2010) [START_REF] Anhalt | Specifying and provisioning Virtual Infrastructures with HIPerNET[END_REF], and at the 20th ITC Specialist Seminar 2009 [START_REF] Vicat-Blanc | Exploring the virtual infrastructure service concept in Grid[END_REF].

State of the Art

Introduction

T

he concept of Virtual Infrastructure (VI) is emerging from a combination of resource virtualization techniques (computing and network), Grid Computing, and the innovative service model explored by Cloud Computing. This chapter reviews concepts, technologies and models related to dynamically provisioned virtual infrastructures. Section 2.2 reviews the techniques and concepts proposed to virtualize IT and network resources. Section 2.3 discusses Cloud Computing technology, its key concepts, and future directions. In Section 2.4, the concept and composition of virtual infrastructures are presented, whereas their provisioning is described in Section 2.5. Finally a summary of the literature survey is presented in Section 2.6, positioning the contributions of this thesis.

Virtualization

The virtualization of resources consists in dematerializing their physical capacity and functionalities, and representing them as virtual entities and services. This technology has been studied for decades in different contexts, such as for virtualizing resources like desktops, applications, systems, storage, and networks [START_REF] Jeong | IETF -Network Working Group -Virtual Networks Problem Statement[END_REF].

Currently, IT infrastructures are using virtualization to consolidate computational resources and to decrease administrative costs [VMWare, 2009]. Different services with specific and distinct requirements can be allocated on a single computational element or platform, sharing the capacity of physical resources. This consolidation reduces costs with energy consumption, cooling requirements, administration and management, while it increases the platform exploitation [Microsoft, 2009]. In addition, virtualization brings isolation and protection: the hardware abstraction that it provides guarantees that services hosted by virtualized elements are kept completely isolated from one another.

The available technologies exploit virtualization following four paradigms for resources sharing: abstraction, partitioning, aggregation, and transformation [START_REF] Garcia-Espin | GEYSERS Deliverable D3.1: Functional Description of the Logical Infrastructure Composition Layer (LICL)[END_REF].

• Abstraction (1:1) represents the class of physical resources exposed as a single entity that can be reserved and configured by a user (e.g., the reservation mode explored by Grid'5000 [START_REF] Cappello | Grid'5000: a large scale and highly reconfigurable grid experimental testbed[END_REF]).

• Partitioning (1:N) a physical resource into N virtual entities is the main paradigm explored by IT resource virtualization technologies. The N virtual resources share the capacities and functionalities of the physical resource;

• Aggregation (N:1) consists in grouping a set of physical resources (IT or network) and exposing the resulting combined capacity as a single entity; and

• Transformation (N:M) is a combination of both partitioning and aggregation. The virtual entities exposed by partitioned physical resources can be combined independently of the physical source.

These paradigms are explored at different levels of an IT infrastructure, including hardware, operating systems, programming languages, network equipments and links. The next sections focus on virtualization of computing and network resources.

Computing resources virtualization

In the 1960s, Goldberg explored virtualization techniques to share the computing power of large mainframes [START_REF] Popek | Formal requirements for virtualizable third generation architectures[END_REF]. Until the 2000s, most of these techniques remained confined to these platforms, having not been much explored by academia and industry. Due to the decreasing price of microcomputers and the development of modern multitask operating systems, resource virtualization techniques were not mandatory. In recent years, motivated by the increasing computing power of modern platforms coupled with a need for higher flexibility, both academia and industry have directed efforts toward resource virtualization.

Virtualization became an alternative to overcome some difficulties and limitations of existing hardware and operating systems, such as platform dependency, and inefficient usage of parallel machines. Nowadays, the computing virtualization technology consists in partitioning a physical resource and representing it as abstract entities called Virtual Machines (VM) [START_REF] Rosenblum | Virtual Machine Monitors: Current Technology and Future Trends[END_REF]. Each virtual machine offers features, services, and interfaces that are similar to those of the underlying virtualized hardware (e.g., CPU, memory, and Input/Ouput -I/O -devices). An abstraction layer, the Virtual Machine Monitor (VMM), controls the access to the physical hardware [VMWare, 2010] [ [START_REF] Barham | Xen and the art of virtualization[END_REF]. We review below the techniques used by some of the current VMMs to virtualize CPU, memory, and I/O devices.

CPU virtualization

The x86 platform was not initially designed to be virtualized and to share a single physical resource among multiple virtual machines. Although this architecture has four levels of execution privileges, operating systems assume a single and isolated execution, using by default the most privileged level, the ring 0.

Virtualizing this platform naturally requires the introduction of a virtualization layer under the operating system. Some explicit instructions cannot be virtualized due to their ring dependency (they can be only executed in the most privileged level). When executed in a higher (unprivileged) level, they require a semantic rewrite, performed by the underlying VMM.

Over the past few years, research on CPU virtualization attempted to overcome these x86 limitations, introducing new concepts and consequently new CPU technologies. The current scenario of CPU virtualization can be decomposed in three main categories [VMWare, 2010]: full virtualization; virtualization at the operating system level and paravirtualization; and hardware-assisted virtualization. The categories are reviewed below and the main technologies, advantages, and drawbacks are summarized in Table 2.1.

Full virtualization: This technology, based on the simulation of physical resources, does not require any update of operating system and legacy software running inside a virtual machine. Non-virtualizable instructions and operations requested by a hosted system are translated into real platform instructions before the execution. More specifically, full virtualization is the only technique that requires no hardware assistance or operating system updates.

Examples of common software that provides full virtualization include VirtualBox [Vir], VMWare [VMW], QEMU [QEM], and Microsoft Hyper-V Server [HYP]. VMWare combines full virtualization with real time binary translation [START_REF] Sugerman | Virtualizing I/O Devices on VMware Workstation's Hosted Virtual Machine Monitor[END_REF]. This approach translates kernel code replacing privileged instructions with new sequences that have the intended effect on the virtualized hardware. QEMU shares the same approach, also relying on dynamic binary translation to emulate a processor, but provides an intermediate mode for supporting native execution combined with binary translation. One particularity of QEMU is its capability to run on any computer without administrative rights. The technology explored by Microsoft Hyper-V Server is based on virtual partitions. Each partition can be considered as a virtual machine, in which a hosted operating system can be executed. Similarly to the other systems, operations that require privileged access to physical hardware are dynamically intercepted and translated into operations of the native physical machine.

Operating system-level virtualization and paravirtualization: Virtualization at the operating system level explores multiple isolated user-spaces offered by certain kernels implementations. Instead of using the hardware instructions directly, hosted operating systems running on user-space virtual machines use the normal system calls of the host operating system. Consequently, the interface exposed to hosted operating systems can be more limited than the physical interface. Implementations like OpenVZ [OPEb], UML [UML], Linux-VServer [VSE], and Jails [START_REF] Kamp | Jails: Confining the omnipotent root[END_REF] explore this virtualization technology, also known as containers.

Differentiating from this approach, the paravirtualization technology [START_REF] Whitaker | Denali: Lightweight virtual machines for distributed and networked applications[END_REF] [ [START_REF] Barham | Xen and the art of virtualization[END_REF] is applied on x86 architectures to overcome their existing limitations. The hosted operating systems have knowledge about the virtualized environment (the existence of a virtual machine). This approach requires modifications on virtualized operating systems introducing specific calls (the hypercalls that give the control to VMM) aiming to reduce the execution overhead with architecture dependent instructions, which in a full virtualized scenario must be trapped by the VMM before execution.

Hardware-assisted virtualization: This virtualization technique reflects the efforts of the industry to contribute with the virtualization wave and to explore it commercially. Current physical architectures, such as Intel VT-x [INT] and AMD-V [AMD] introduce a new CPU execution mode that allows the VMM to run on a privileged mode below ring 0. In this scenario, hosted privileged instructions are automatically trapped and directed to the VMM. Dynamic binary translation or paravirtualization are no longer required. Consequently, the changes needed in hosted operating systems are eliminated. Virtual machine monitors such as Xen [START_REF] Barham | Xen and the art of virtualization[END_REF], VMWare [VMW], KVM [KVM], and Microsoft Hyper-V [HYP] offer implementations exploring the hardware-assisted virtualization.

Categories

Memory virtualization

The virtualization of random access memory (RAM) is considered as a critical part of a VMM implementation [START_REF] Barham | Xen and the art of virtualization[END_REF]. The traditional approach is to give to VMM the control of a shadow image of the virtual machine's memory-management data structure. With this information, the VMM can precisely control the access to physical memory [Waldspurger, 2002], all active memory pages, and consequently, the paging mechanism. This technique can induce overheads on hosted operating systems as it frequently accesses and changes page tables. The future direction of memory virtualization is the usage of hardware-managed shadow page tables for accelerating x86 virtualization [START_REF] Rosenblum | Virtual Machine Monitors: Current Technology and Future Trends[END_REF].

Virtualization of I/O devices

The sharing of physical devices among hosted VMs requires a routing access control to efficiently distribute their capacity among the guest operating systems, while guaranteeing their isolation and protection. Some implementations rely on emulation of virtual devices proposing standard and consistent device drivers to improve the portability across platforms [START_REF] Sugerman | Virtualizing I/O Devices on VMware Workstation's Hosted Virtual Machine Monitor[END_REF]] [VMWare, 2010]. Other proposals expose a set of device abstractions [START_REF] Barham | Xen and the art of virtualization[END_REF], where access is controlled by the VMM via shared-memory and asynchronous buffer-descriptor rings, similarly to hardware interrupts implemented on operating systems. For example, the virtualization of network interface cards (NICs) enables the creation of virtual networks, including virtual switches and bridges, on a single physical host [START_REF] Sugerman | Virtualizing I/O Devices on VMware Workstation's Hosted Virtual Machine Monitor[END_REF]] [Barham et al., 2003] [8] .

Future research in this area includes the introduction of hardware support on device virtualization [START_REF] Rosenblum | Virtual Machine Monitors: Current Technology and Future Trends[END_REF], which can efficiently eliminate the I/O overhead imposed by the emulation and abstract device techniques.

Network virtualization

This kind of virtualization has been explored to co-allocate multiple virtualized networks on top of physical networks [START_REF]The FP7 4WARD project[END_REF]. Similarly to server virtualization, this technology enables the sharing of physical resources, in this case links and network equipments, among hosted virtual resources. This concept has been applied in distinct scenarios and layers of the Open System Interconnection (OSI) model [ISO, 1994], exploring different technologies [Chowdhury and Boutaba, 2010], which have paved the road toward full virtual networks.

We review these technologies, organizing the concepts into four main categories: virtual LANs, virtual private networks, overlay networks, and programable networks.

Virtual LAN

Virtual LANs (VLANs), standardized as 802.1Q by IEEE [IEE], are logically isolated networks that can co-habit on a single central network switch or switching hub [START_REF] Bell | Definitions of Managed Objects for Bridges with Traffic Classes, Multicast Filtering and Virtual LAN Extensions[END_REF]] [802.1Q, 2005] [Sincoskie and Cotton, 1988]. Typically, this virtualization technique operates at OSI's layers 2 and 3. VLANs were initially explored to reduce the collision domain of Ethernet segments interconnected by hubs in Local Area Networks (LANs). With the introduction of switches, the collision problem was controlled and VLANs started to be used for reducing broadcast domains.

This virtualization technology does not cope with traffic engineering, except when coupled with 802.1p [START_REF] Nichols | Definition of the Differentiated Services Field (DS Field)[END_REF]] it enables to prioritize part of the traffic. Current technologies for switches and routers have proposed a set of configurable options for guaranteeing quality of service provisioning, being applied to logically integrate network members into a single view, increasing the organization, segmentation and planing of local networks [Bin Tariq et al., 2009].

Virtual Private Network

A Virtual Private Network (VPN) is a communication network used to interconnect one or more IT endpoints geographically distributed over a Wide Area Network [Baugher et al., 1999] [Rosen and[START_REF] Rosen | [END_REF], by establishing tunnels over the public communication infrastructure. It was introduced for security reasons (at layer 3) maintaining privacy on data exchange through cryptography, and for accelerating routing operations (at layer 2).

VPNs have been used to interconnect distributed branches of companies, exploring secure and trusted communications [VPN]. In secured VPNs the tunnel is encrypted when transmiting sensitive data, guaranteeing that if someone intercepts the traffic, the information cannot be directly accessed. In trusted VPNs, the Service Provider (SP) responsible for the VPN and the client establish a Service Level Agreement (SLA) that aims to guarantee a secure virtual communication path over the specific trusted physical path.

VPNs comprise three classes of components [START_REF] Andersson | Provider Provisioned Virtual Private Network (VPN) Terminology (RFC4026)[END_REF]: Customer Edges (CE), Provider Edge routers (PE), and P routers, as presented in Figure 2 VPNs can be established at different levels of the OSI model, exploring multiple protocols and services. We detail these levels below.

Layer 1: The virtualization of Layer 1 network elements, such as Optical Cross-connect (OXC), or Time-Division Multiplexing (TDM) switches, enable the composition and realization of L1VPNs [Takeda, 2007]. By definition, a Layer 1 VPN uses GMPLS RSVP-TE for signaling both within the service provider network (between PEs), and between the costumer and the SP (between CE and PE) [START_REF] Fedyk | Layer 1 VPN Basic Mode (RFC5251)[END_REF].

Generalized Multiprotocol Label Switching (GMPLS) [START_REF] Farrel | GMPLS: Architecture and Applications (The Morgan Kaufmann Series in Networking[END_REF]] is an extension of the MPLS architecture [START_REF] Rosen | Multiprotocol Label Switching Architecture (RFC3031)[END_REF]. MPLS has been defined to support label-based forwarding of data. In the original architecture, the Label Switching Routers (LSRs) were assumed to have a forwarding plane capable of recognizing packet or cell boundaries. The GMPLS extension includes Label Switching Routers (LSRs) that do not forward data based on packet or cell boundaries. These LSRs include devices where the forwarding decision is based on time slots, wavelengths, or physical ports [Berger, 2003]. This extension, combined with the concept of nested Label Switched Paths (LSPs), allows the system to scale by building a forwarding hierarchy. According to their topologies, Layer 1 VPNs can be classified in Virtual Private Wire Services (VPWS) which are point-topoint, and Virtual Private Line Services (VPLS) which are point-to-multipoint [START_REF] Benhaddou | Layer 1 Virtual Private Networks in Multidomain Next-Generation Networks[END_REF].

Layer 2: Layer-2 VPNs are usually provided over Ethernet, ATM, and Frame-Relay technologies. There are two fundamental types of Layer 2 VPN services that a SP could offer to a customer [START_REF] Andersson | Framework for Layer 2 Virtual Private Networks (L2VPNs) (RFC4664)[END_REF]: Virtual Private Wire Service (VPWS) and Virtual Private LAN Service (VPLS). A VPWS is a VPN service that supplies an L2 point-to-point service, and a VPLS is an L2 service that emulates LAN service across a Wide Area Network (WAN) [START_REF] Augustyn | Service Requirements for Layer 2 -Provider-Provisioned Virtual Private Networks[END_REF].

The Layer 2 VPN protocols encapsulate the Layer 3 packets into point-to-point frames. The advantage of Layer 2 VPNs is that the higher level protocols remain with their normal operation, more specifically, the virtualization is transparent to Layer 3 protocols. Pointto-point Tunneling Protocol (PPTP) [START_REF] Hamzeh | Point-to-Point Tunneling Protocol (PPTP) (RFC2637)[END_REF], Layer 2 Tunneling Protocol (L2TP) [START_REF] Townsley | Layer Two Tunneling Protocol (L2TP) (RFC2661)[END_REF], and Layer 2 Forwarding (L2F) [START_REF] Valencia | Cisco Layer Two Forwarding (Protocol) L2F (RFC2341)[END_REF]] are examples of L2VPN protocols.

Layer 3: A Layer-3 VPN is characterized by the use of IP and/or MPLS to virtualize a shared network infrastructure (VPN backbone) [START_REF] Carugi | Service Requirements for Layer 3 -Provider Provisioned Virtual Private Networks (PPVPNs) (RFC4031)[END_REF]. The SP edge devices determine how to route VPN traffic by looking at the IP and/or MPLS headers of the packets they receive from the customer's edge devices [START_REF] Callon | A Framework for Layer 3 -Provider Provisioned Virtual Private Networks (PPVPNs) (RFC4110)[END_REF].

Layer-3 VPNs are implemented as two basic types [Chowdhury and Boutaba, 2009]: CE-and PE-based. In a CE-based VPN, the CE devices create and manage the tunnels, without interference of network provider. The CE devices encapsulate the packets and route them through carrier networks. In this scenario, three protocols are identified to create the tunnel: a carrier protocol responsible for carrying the VPN packets (such as IP); an encapsulating protocol, such as PPTP [START_REF] Hamzeh | Point-to-Point Tunneling Protocol (PPTP) (RFC2637)[END_REF], L2TP [START_REF] Townsley | Layer Two Tunneling Protocol (L2TP) (RFC2661)[END_REF], and IPSec [Kent and[START_REF] Kent | [END_REF][START_REF] Kent | [END_REF]; and the original CE passenger protocol. Already in a PE-based approach, the network provider is responsible for the establishment and management of the existing VPNs.

Overlay networks

Overlay networks are topologies constructed over existing networks. In this virtualization layer, virtual links are logically established over physical links or paths to interconnect the nodes that are part of the overlay.

Nowadays, this technology is used as an alternative to overcome diverse issues in different contexts, such as Internet routing resilience [START_REF] Andersen | Resilient overlay networks[END_REF], enable multicasting [Eriksson, 1994] [Jannotti et al., 2000], provide QoS guarantees on communications [START_REF] Subramanian | OverQos: an overlay based architecture for enhancing internet QoS[END_REF], and content distribution [START_REF] Krishnamurthy | On the use and performance of content distribution networks[END_REF]. Peer-to-Peer networks, often built at level 4 of the OSI model, are examples of overlay networks [START_REF] Androutsellis-Theotokis | A Survey of Peer-to-Peer Content Distribution Technologies[END_REF], where the content is typically exchanged atop of an IP network, as explored by Akamai solutions [AKA].

Programmable networks

This type of network can be programmed via a minimal set of Application Programming Interfaces (APIs) with which one can ideally compose an infinite spectrum of higher-level services [START_REF] Campbell | A survey of programmable networks[END_REF].

This technology supports the construction of networks enabling dynamic deployment of new services and protocols. As identified by [Chowdhury and Boutaba, 2009], two schools of thought emerged for the implementation method:

• Open Signaling: proposes a clear distinction between transport, control, and management planes. It defines an abstraction layer for physical network devices with a well-defined interface. For example, OpenFlow switches explore a bottom-up approach to dynamically configure networks [START_REF] Mckeown | OpenFlow: enabling innovation in campus networks[END_REF];

• Active Network: explores the dynamic configuration based on routers and switches information collected by analyzing packet exchange, which allows a real-time adaptation of the network according to the traffic [START_REF] Tennenhouse | Towards an Active Network Architecture[END_REF].

Discussion

Virtualization is a driving force for flexibility in the next-generation Internet, guaranteeing its growth and success, and preventing its ossification [Handley, 2006]. It can enable ubiquitous deployment of applications and foster innovations by adding a layer of abstraction between the actual hardware and running and exposed resources [START_REF] Anderson | Overcoming the Internet Impasse through Virtualization[END_REF]] [Niebert et al., 2008] [Keller and Rexford, 2010].

Although the isolation mechanisms of VMMs have an impact on the performance of virtualized systems [START_REF] Wang | [END_REF]Ng, 2010] [Schlosser et al., 2011] and some issues remain opened [START_REF] Gupta | Enforcing performance isolation across virtual machines in Xen[END_REF], virtualization enables an efficient usage and sharing of physical resources. By being de-materialized, virtual resources can be deployed on demand, configured, started, paused, saved, or deleted, like a set of programmable objects. This gives to IT and network providers the possibility to set up and manage virtual resources, allowing the dynamic provisioning of new services [START_REF] Carapinha | Network virtualization: a view from the bottom[END_REF].

Virtualization has over the years been applied to specific scenarios, such as server consolidation and VLAN composition. The timeline depicted in Figure 2.2 shows the progress of the main technologies, projects and software for virtualization of network and IT resources. Following the timeline, one can observe that virtualization technologies have increasingly shifted from solutions for specific endpoints of the Internet (e.g., servers, local networks) to more distributed resources (e.g., VPNs). Currently, different virtualization techniques can be combined for providing more elaborated services. For example, two providers with heterogeneous solutions for network virtualization (i.e., one exposing optical Layer 1 virtualization, and another a Layer 2 VPN service) can cooperate and interconnect to serve the needs of a customer who is unaware of the difference of underlaying technology. In addition, an external network operator can orchestrate resources by allocating them and composing virtual networks using services exposed by different providers [START_REF] Geysers | White paper: GEYSERS, the Revolution of Infrastructure Provisioning[END_REF].

One of the main contributions introduced by virtualization techniques is that resources can be dynamically reconfigured. IT resources can have their memory, storage, and CPU configurations redefined during the execution process, whereas a virtual link can be controlled in terms of bandwidth capacity. These dynamic configuration and provisioning features have been explored by recent technologies, as detailed in the following sections.

Cloud Computing

The maturity of resource virtualization and Grid Computing technologies [START_REF] Kesselman | The Grid: Blueprint for a New Computing Infrastructure[END_REF]] have led to the emergence of Cloud Computing. Concepts such as virtual organizations and services exposed via transparent interfaces have initially been explored in Grids [START_REF] Foster | Globus: A Metacomputing Infrastructure Toolkit[END_REF]] [Foster, 2001] [Foster, 2005]. Cloud Computing combines these concepts with new virtualization techniques and business models to enable on-demand access to a shared pool of configurable resources (e.g., servers, storage, applications and services) that can be rapidly provisioned and released with minimal management effort [START_REF] Mell | The NIST Definition of Cloud Computing[END_REF]] [Buyya, 2009] [Rimal et al., 2011].

In this way, Cloud Computing provides a new means for delivering IT services, based on cost-efficient, scalable and on-demand provisioning guided by the user's requirements. Exploiting the flexibility offered by virtualization, IT elements are exposed as a set of services (or even resources) that can be reserved by users for a specific timeframe. Currently, single users, companies, and institutions deploy dynamic computing resources on Clouds to execute their applications, exploring the advantages offered by the different levels of virtualization, including cost reduction [START_REF] Truong Huu | Joint elastic cloud and virtual network framework for application performance optimization and cost reduction[END_REF] and reliability support [START_REF] Koslovski | Reliability support in virtual infrastructures[END_REF].

The commercial model explored in Clouds differs from traditional IT commercialization by demanding smaller up-front investment. Traditionally, a user buys a software or hardware, and then uses it respecting the conditions imposed by contractual agreements (e.g., number of licenses, or number of allowed executions). Cloud Computing proposes the on-demand availability of different virtualized services that can be rented, accessed, customized, and exploited by users in a pay-as-you-go manner.

With the Cloud approach, both users and providers can explore advantages such as:

• users are not locked into a single IT solution or provider;

• software and hardware licenses' costs are diluted and distributed between providers and users;

• providers can operate close to the maximum computing capacity and, at same time, maximize revenues;

• IT administration costs are also proportionally shared by users and providers.

Types of Clouds

Clouds are classified according to the servers' location and the users who access them.

The location distinguishes private resources, belonging to a single organization, and public resources, located over a distributed infrastructure, while the access identifies the users and how they access the resources (e.g., reserving, renting, combining). A commonly used classification identifies mainly three types of Clouds: Private Clouds, Public Clouds, and Hybrid Clouds [START_REF] Zhang | Cloud computing: state-of-the-art and research challenges[END_REF].

Private Clouds

Private Clouds (also called Internal Clouds) are built using the internal resources of organizations. The exclusive use of computing power is usually restricted to members of the organization to guarantee the confidentially of internal and critical data. Administrators of private computing infrastructures have the highest level of control over performance, reliability, and security of resources. Both commercial and open-source frameworks and tools, such as VMware vCloud Director [vCl], OpenNebula [Opea], Xen Cloud Platform (XCP) [XCP], Eucalyptus Systems [Euc], and LYaTiss Weaver [START_REF] Lyatiss | [END_REF], can be used to compose and manage Private Clouds.

Public Clouds

Public Clouds (or External Clouds) make their resources available to users as services. [Net], among others. As of writing, Cloud providers do not offer the provisioning of virtual links to interconnect virtual machines. Instead, the communication is performed following a best-effort approach.

Hybrid Clouds

At times, an organization can feel compelled to reserve public on-demand resources and interconnect them with its Private Cloud. It may be the case under peak-load conditions where the organization's private resources may not suffice the application workload. A set of public services are then provisioned on-demand, hence combining private and public resources for a given timeframe. Combining public and private resources enables a finer control on sensitive data location and security than using only Public Clouds. An organization can keep the sensitive data on its Private Cloud, exploring the public resources to execute less critical tasks.

Service models

Cloud Computing can dynamically provision virtualized services at different levels. A set of virtualized servers and IT infrastructure can provide Software, Platform, and Infrastructure as a Service [START_REF] Mell | The NIST Definition of Cloud Computing[END_REF] as shown by the layers in Figure 2.4. A set of distributed and virtualized servers composing the physical substrate is shown at the bottom, while the other layers represent different models for exposing services, which are detailed below.

Software as a Service (SaaS):

SaaS, the higher level of abstraction, offers on-demand execution of applications allocated on remote servers. In contrast to the one-time licensing model commonly used in traditional software, SaaS is frequently sold using a subscription model, where customers pay an ongoing fee to use the application [Jacobs, 2005]. Examples of SaaS providers include Microsoft Online [BPO] Salesforce.com [SAL], Rackspace [RACa], SAP Business ByDesign [SAP], Google Apps [GOOb] and NetSuite [Net].

Platform as a Service (PaaS):

The PaaS model provides features to users for deploying a complete application lifecycle (for example, tools to design, develop, test, host, and integrate software) without the need for special software installation and configuration. PaaS -layer resources, such as software development frameworks, are exposed as on-demand services.

In addition, tools to manage and control scalability, security and persistency are provided as optional service components. Google App Engine [GOOa], Microsoft Windows Azure [AZUa], and Force.com [FOR] are examples of PaaS providers.

Infrastructure as a Service (IaaS):

This model offers Virtual Machines (VMs) as services. Instead of buying new servers to run his application, the client can lease a set of virtual machines. Virtual machines are dynamically provisioned and interconnected through a best-effort approach, generally without any quality of service guarantees to the network communications. Examples of IaaS providers include Amazon EC2 [AMAa], GoGrid [GOG], Rackspace [RACa], and Flexiscale [FLE].

Cloud Networking

Although Cloud Computing has consolidated the on-demand provisioning of virtual machines, an efficient network interconnection of these elements has not been addressed. Cloud providers instantiate a set of virtual machines and interconnect them using besteffort approaches in which the network is generally not controlled and the usage of communication resources is charged according to the total volume of transferred data.

The best-effort approach is not enough for network-sensitive applications. A bottleneck or increased latency between distributed modules can compromise the entire application execution [START_REF] Koslovski | Executing distributed applications on virtualized infrastructures specified with the VXDL language and managed by the HIPerNET framework[END_REF]. To overcome this limitation, Cloud Networking enables networking resources to be controlled, deployed and provisioned in a much more dynamic, flexible and scalable way [SAI]. This technology proposes the dynamic provisioning of connectivity services following the same delivery model explored by Cloud Computing: on-demand and billed according to usage.

Figure 2.5 exemplifies the dynamic provisioning of a connectivity service between a Private Cloud and a Public Cloud provider. A virtual link is reserved and dynamically provisioned to interconnect both Clouds. The provisioned capacity can vary during the reservation time: a peak on data to be computed or to be transferred requires more capacity then the nominal rate originally provided. During the peak, more resources are dynamically provisioned by the Cloud Networking provider.

Discussion

Cloud Computing consolidates the on-demand provisioning of configurable virtual machines to perform computations [AMAa] [ENO] and provide large data storage [TER]. Cloud users have been outsourcing their computing and storage infrastructure to Public Cloud providers who provision services in a pay-as-you-go service provisioning. In addition, the concept of Cloud Networking aims at dynamically provision virtual interconnections to enable efficient and secure communication between virtual entities.

Many research and engineering issues are still open in Clouds. For example, Public Cloud providers differ in the ways that their infrastructure is composed and the form their features and services are exposed (e.g., virtualization techniques, internal network topology). A user can thus expect his application to have a different behavior when executing it over different Cloud providers [START_REF] Li | CloudCmp: comparing public cloud providers[END_REF].

Usually, a provider has an API or a set of web services that enable the interaction with its reservation and provisioning systems, such as Amazon EC2 API [AMAb], Win-dows Azure API [AZUb], and Rackspace API [RACb]. These APIs can be exposed using SOAP [START_REF] Gudgin | SOAP Version 1.2 Part 1: Messaging Framework[END_REF], HTTP [START_REF] Fielding | Hypertext Transfer Protocol -HTTP/1.1[END_REF], or RESTful [START_REF] Gregorio | The Atom Publishing Protocol (RFC5023)[END_REF] interfaces. They do not follow a well-defined standard, which hence induces issues in communication and information exchange among these systems, management frameworks, and users.

Moreover, the security of Clouds is a major concern, especially when sensitive information must be outsourced to distributed public resources [Barrios Hernandez et al., 2010]. In addition to traditional security aspects that should be provided (e.g., authentication, authorization, integrity, and confidentially), Cloud Computing introduces the possibility of the misuse of resources. A large amount of computing power can be allocated and used for illegal services (e.g., DoS attack, spamming) [START_REF] Schoo | Challenges for Cloud Networking Security[END_REF].

In spite of the issues above, it is incontestable that Cloud Computing has changed the usage of the Internet. This technology has been adopted by many enterprises, each following a specific business model. Predictions for the next years indicate that more than 80% of the IT will be outsourced by the end of 2020, and Clouds will be cheaper, more reliable, more secure, and easier to use. In addition, the Cloud providers' cost will be less than 25% of that of corporate data centers [START_REF] Rosenberg | The Cloud at Your Service[END_REF].

Virtual Infrastructures

Virtual Infrastructures (VIs) extend the original IaaS paradigm to provide dynamic virtual networks of computing (also virtualized) resources [SAI] [GEN] [GEYSERS, 2011]. With the VI extension, the Internet's computational, storage and network resources can be abstracted from physical infrastructure and exposed as services that are dynamically reserved and provisioned [Laganier andVicat-Blanc Primet, 2005] [Rochwerger et al., 2009].

Figure 2.6 illustrates this new scenario: two virtual infrastructures (A and B) are allocated on a distributed and virtualized physical substrate, sharing its IT and networking capacities. Both VIs are completely isolated and have no knowledge of sharing physical resources.

Concept

We defined a Virtual Infrastructure (VI) as a time-limited group of virtual computing resources interconnected by a virtual network [START_REF] Anhalt | Specifying and provisioning Virtual Infrastructures with HIPerNET[END_REF]. By combining resource and network virtualization, the user of a VI has the illusion that he is using a private distributed system, while in reality he is using multiple systems that are part of a virtualized physical substrate. VI instances are kept isolated from one another.

VIs can span multiple networks belonging to different administrative domains. Independently of the underlying physical topology and the applied virtualization techniques, a VI user has a consistent view of a regular network stack. He can join the VI from any location, deploying and using the same application used on the Internet or his intranet.

A VI can be formally represented as a graph whose vertices are in charge of active dataprocessing functions and edges of moving data between vertices. Figure 2.7 illustrates this concept representing a virtual infrastructure composed of virtual machines interconnected through virtual links. It shows two virtual routers (vertices r v A and r v B) which are used to interconnect and perform the bandwidth control among the other virtual resources (vertices r v 1 to r v 8). The virtual routers can independently forward the traffic of the different virtual infrastructures which share the same physical network. Each edge represents a virtual link (as l v 1 and l v 2) with different configurations used to interconnect a pair of virtual resources. Moreover, a VI can be defined and modeled according to user requirements [START_REF] Koslovski | VXDL: Virtual Resources and Interconnection Networks Description Language[END_REF]. Different information can be defined for the graph components, individually or aggregated:

• Temporal attributes for each resource (time window for provisioning).

• Parameters to represent the necessary configuration of IT resources (e.g., RAM, CPU speed, and storage capability) and to define the link requirements (bandwidth and latency). This information can vary during the VI lifetime.

• The required software (e.g., operating systems) and tools (e.g., communication and programming tools) that must be provisioned with the VI.

• The resource's functionality (e.g., a set of computing nodes or storage nodes).

• Security attributes for each component (e.g., access control, confidentiality level).

• Reliability level required for each VI component.

• Commercial attributes (maximum cost).

Building blocks

As defined by LYaTiss Weaver [START_REF] Lyatiss | [END_REF], a VI is composed of the following components or building blocks (edges and vertices) [1] [16]: vNodes, vStorage, vRouters, vAc-cessPoints, and vLinks. They can be organized individually or in groups. For example, a vertex of a VI graph can be composed of a group of vNodes, vRouters, and vLinks.

vNode: is a fully customizable virtual machine that is provisioned (e.g., assigned CPU, RAM, and storage resources) and configured (e.g., set the operating system and communication tools) atop virtualized physical hosts according to the user's requirements.

vRouter: the virtual routers are special components that virtualize the data, control, and management network planes. Users can deploy customized routing protocols and configure the packet-queuing disciplines, packet filtering and monitoring mechanisms they want. In addition, as they concentrate aggregated VI traffic, vRouters represent strategic points of the network for transfer rate control. By limiting the rate and policing the traffic of different vRouters, the traffic of VIs can be controlled so that the user is provided with a fully isolated VI. vLink: the components of VIs (which can include vNodes, vRouters, vAccessPoints, vStorage and groups of these) are interconnected using vLinks (virtual links). Each vLink is a temporary path allocated over multiple physical channels for which metrics such as bandwidth (forward and reverse) and latency can be defined. In addition, by asking for vLinks it is possible to compose and model the VI, identifying for example the critical communication paths.

Discussion

Virtual Infrastructures have emerged as the blend of different concepts and techniques, such as resource and network virtualization, Grid Computing, and resources as services.

Within this new concept, users can reserve a set of interconnected IT resources and configure them according to their application requirements. VIs are provisioned on top of a distributed and virtualized physical substrate, sharing the resources in a transparent and isolated way. During a given time slot, all VI resources are made available to, configured and managed by the user.

Provisioning dynamic Virtual Infrastructures

The provisioning of a virtual infrastructure is a complex task as each of its components can vary its configuration in three dimensions: capacity, time, and cost. Following the pay-as-you-go model, cost represents the InP perspective, who is charging for the resource provisioning according to time and capacity requirements. Figure 2.8 shows the three dimensions that should be considered during a virtual resource provisioning. The virtual resource r v 1 can vary its capacity per time resulting in a specific usage cost. Four volumes of capacity per time have their own provisioning costs. Moreover, each virtual resource composing a VI can similarly vary its configuration. The following sections review the requirements for efficient VI provisioning, and present existing solutions for this purpose, detailing specifically a framework used as base for developing the contributions of this thesis.

Requirements for efficient VI provisioning

VIs have a lifecycle composed of specification, allocation, deployment, and release [START_REF] Vicat-Blanc | Exploring the Virtual Infrastructure as a Service concept with HIPerNet[END_REF]. The three dimensions (time, cost, and capacity) are present and should be treated in all steps. For provisioning efficient VIs, a management framework should respect and integrate the following requirements:

• Enabling the specification of dynamic resources. The requirements of virtual IT and network resources can vary their capacity during the reservation time. In addition, a virtual resource can be present only partially in the whole VI reservation time;

• The internal mechanism for embedding VIs should also respect this elastic aspect, as well as the user's and InP's expectations. The allocation should be performed efficiently for both, optimizing the trade-off between their goals; and

• Deploying the VIs respecting the user's requirements. Tools for guaranteeing the Quality-of-Service (QoS) should control the provisioned capacity, assuring isolation and performance for each individual component.

Existing solutions for provisioning VIs

Several projects, prototypes, and commercial solutions have been proposed to provide virtual resources, virtual networks, and VIs within different contexts, such as in Grids and Clouds. We discuss these solutions here by organizing them in IT resource provisioning, and network provisioning. They are analyzed respecting the requirements identified in Section 2.5.1.

IT virtualization

Grids have explored decoupling services from physical infrastructure with virtualization techniques. In [START_REF] Rezmerita | Private Virtual Cluster: Infrastructure and Protocol for Instant Grids[END_REF], the authors proposed PVC, combining various Grid, P2P and VPN approaches to create instant Grids. This distributed system is composed of a daemon process (peer) and a brokering service, which helps establish the connections. Distributed peers are aggregated composing a virtual Grid.

Existing commercial products, such as Amazon's Elastic Compute Cloud (EC2) [AMAa], Enomaly's Elastic Computing Platform (ECP) [ENO] and GOGRID [GOG], allow users to reserve a set of resources, choose an operating system, and customize them. Other products are less configurable, like 3Tera's AppLogic [TER] where the operating system cannot be chosen. Some frameworks for Cloud orchestration, such as OpenNebula [Opea] and Eucalyptus [Euc], provide tools for IaaS provisioning. All these Cloud solutions are suitable for performing computation and storage and are not aim to host virtual routers. Moreover, these Cloud Computing solutions do not intend to control the network or its communication performance.

Network virtualization

Some proposals have explored virtualization for enabling end-to-end control while using physical equipments from different physical infrastructure providers [START_REF] Feamster | How to lease the internet in your spare time[END_REF]. In [START_REF] Bavier | In VINI veritas: realistic and controlled network experimentation[END_REF], the authors propose VINI, a virtual network infrastructure that allows several virtual networks to share a single physical infrastructure. Researchers can run experiments in virtual-network slices running inside User Mode Linux (UML) instances.

They can configure the slices and choose a protocol, among those available, to communicate internally. This also provides full-isolation between virtual nodes and controlled resource sharing.

Trellis [START_REF] Bhatia | Hosting Virtual Networks on Commodity Hardware[END_REF], a network-hosting platform deployed on the VINI facility, is a virtual-network substrate that can run on commodity hardware. It is implemented using VServer's [VSE] container-based virtualization because of its network performance. VINI and Trellis were evaluated on PlanetLab [START_REF] Bavier | Operating system support for planetary-scale network services[END_REF]] which provides users with slices of virtual resources distributed across its overlay infrastructure. The virtual resources are VServers generally providing end-host functionalities. In the GENI design [GEN], the users are provided with slices, like in VINI, but composed of virtual machines or partitions of physical resources. GENI's goal is to provide users with multiple shareable types of resources.

ShadowNet [START_REF] Xu | [END_REF] proposes an architecture for an operational trial/test network consisting of ShadowNet nodes interconnected by a single backbone. A ShadowNet node is composed of a collection of carrier-grade equipments, namely routers, switches and servers. Each node is connected to the Internet as well as to other ShadowNet nodes via a (virtual) backbone. VIs are developed on top of ShadowNet nodes mainly for testing purposes.

In addition to these initiatives, some proposals have specifically treated the bandwidth sharing in virtual networks. A design and mathematical model of dynamic adaptation of virtual networks to their performance objectives has been proposed by DaVinci [START_REF] He | DaVinci: Dynamically Adaptive Virtual Networks for a Customized Internet[END_REF]. In addition, isolation between virtual networks is provided by slicing mechanisms, controlling the attribution of bandwidth to virtual links [START_REF] Kim | Automated and scalable QoS control for network convergence[END_REF]] [Sherwood et al., 2010].

Recent projects have addressed the VI provisioning [SAI] [GEY]. Geysers project [GEY-SERS, 2011] is investigating solutions for implementing virtual networks atop distributed optical providers, while SAIL project [SAI] is investigating the provisioning of virtual networks to interconnect distributed Cloud data centers, proposing the dynamic creation of Flash Network Slice.

HIPerNet framework

We present in this section the HIPerNet, the first framework to provide and manage dynamic virtual infrastructures proposed in the context of HIPCAL [HIP] and CARRIOCAS projects [START_REF] Audouin | CARRIOCAS project: An experimental high bit rate optical network for computing-intensive scientific and industrial applications[END_REF]] [Vicat-Blanc Primet et al., 2009]. This framework was chosen to serve as the base for the development and implementation of the contributions of this thesis. The concepts and technologies addressed by HIPerNet, which justifies this choice, are discussed here.

Concepts and design principles

HIPerNet is a framework for dynamic provisioning of networking and computing infrastructures. Conceptually, it innovates by combining system and network virtualization technologies with bandwidth sharing and advance reservation mechanisms [Laganier and Vicat-Blanc Primet, 2005] [1]. By definition, HIPerNet is transparent to all types of upper layers, such as: protocols (e.g., TCP, UDP), APIs (e.g., sockets), middleware (e.g., Globus [START_REF] Foster | Globus: A Metacomputing Infrastructure Toolkit[END_REF]), applications, services and users. It helps end users with intensive-application deployment, execution and debugging, by providing an envi-ronment to run them on scalable, controlled, distributed and high-capacity platforms. In addition, it is mostly agnostic of lower layers and can be deployed over IP as well as lambda networks.

The HIPerNet framework is responsible for the creation, management and control of VIs supervising and monitoring their status and behavior during their whole lifetime. The key principle is to have operations realized automatically. For this, HIPerNet defines and activates mechanisms to automatically control the VIs as well as the status of the underlying exposed and virtualized physical substrate.

Figure 2.9 shows the main components of HIPerNet. At the lower level, HIPerNet accesses and controls a part of the physical infrastructure that is virtualized and exposed. The physical resources are registered on the HIPerNet database and can be allocated to VIs. Once the resources have been exposed, HIPerNet gets full control over them. This set of exposed virtualized resources composes the substrate hosting the VIs. At the up layer, HIPerNet receives VI requests using a special language: VXDL (a contribution of this thesis whose is discussed in Chapter 3).

The internal mechanism of HIPerNet allocates, deploys, and configures VIs following the user's requirements. All modules of HIPerNet can be customized. For example, the allocation or deployment mechanisms can be replaced as long as they respect the defined API. This has been an important feature for devising the allocation mechanism detailed in Chapter 5, and the reliability service is discussed in Chapter 6. At run-time, the HIPerNet manager communicates with the virtual and physical resources to monitor their status and configure control tools to supervise the resource usage [HIPerNet]. Provisioning of IT resources: HIPerNet provides virtual IT resources based on Xen VMM [START_REF] Barham | Xen and the art of virtualization[END_REF]. The virtualized physical substrate is composed of a set of physical machines running a special administrative image, which is basically a Xen dom0 with a set of private management tools. To spontaneously join the virtualized physical substrate, each machine must deploy the HIPerNet image and declare its existence, configuration, and available capacity to HIPerNet, becoming a potential host for virtual IT resources. This information is automatically declared during the bootstrap.

Virtual machines are composed according to the user's specification and instantiated on physical hosts. Considering the filesystem deployment, HIPerNet follows two approaches: an image can be copied directly to physical hosts; or placed on a network file system. The operation mode is selected by the user during the instantiation process. Some services, such as live migration [START_REF] Clark | Live migration of virtual machines[END_REF] and reliability support [START_REF] Koslovski | Reliability support in virtual infrastructures[END_REF], require the provisioning using the network file system to guarantee the mobility of virtual machines.

Dynamic network provisioning: HIPerNet has explored tools and technologies for virtualizing networks at layers 1 to 3, enabling multiple virtual overlay networks to cohabit on a shared communication infrastructure. All network overlays and virtual resources are kept isolated at the network level to ensure security, performance control and adaptability.

Within HIPerNet, vLinks implemented at layer 3 are based on IPsec [START_REF] Kent | Security Architecture for the Internet Protocol (RFC4301)[END_REF] and the HIP protocol [START_REF] Moskowitz | Host Identity Protocol (HIP) Architecture (RFC4423)[END_REF]]. In addition, at this layer, the network provisioning and traffic control are based on vRouters. The initial prototyping of a vRouter consists in a software router implemented inside the Xen virtual machines [START_REF] Vicat-Blanc | Exploring the virtual infrastructure service concept in Grid[END_REF]. vRouters perform an efficient channel provisioning by combining routing and traffic engineering in order to satisfy the quality of service requirements of each VI [Divakaran and Vicat-Blanc Primet, 2007].

The implementation and provisioning of virtual links at lower layers (L1 and L2) was addressed within the CARRIOCAS projects [START_REF] Audouin | CARRIOCAS project: An experimental high bit rate optical network for computing-intensive scientific and industrial applications[END_REF]] [Vicat-Blanc Primet et al., 2009]. A prototype named Scheduling, Reconfiguration, and Virtualization (SRV) was developed for interconnecting IT resources with ultra-high speed optical networks [START_REF] Verchere | Automatic Network Services Aligned with Grid Application Requirements in CARRIOCAS Project[END_REF].

Security model: The security model is based on a combination of Simple Public Key Infrastructure (SPKI) and HIP protocol [START_REF] Vicat-Blanc | A scalable security model for enabling dynamic virtual private execution infrastructures on the internet[END_REF]. The cryptographic identification scheme is the core of the SPKI [START_REF] Ellison | SPKI Certificate Theory (RFC2693)[END_REF], which defines a flexible private authorization management layer for the VI resources. A certificate is signed by the sender using its private key. When receiving the certificate, the receiver verifies the signature using the sender's public key available in the certificate, in order to check the message integrity and authenticate the sender. Unlike the traditional PKI model, there is no need for a high level naming service to guarantee the certificate authenticity. The SPKI certificate itself carries a signed authorization associated to the resource identified by its public key.

In addition, the HIP protocol automatically associates public keys to entities [START_REF] Moskowitz | Host Identity Protocol (HIP) Architecture (RFC4423)[END_REF]. Traditionally, the IP address plays two independent roles: a locator and an identifier. Network layer protocols (e.g., IPv4, IPv6) use the locator role to route packets, while the upper layer protocols (e.g., TCP, UDP) use the identifier role. As upper layer protocols depend on location, they fail when mobility causes a modification of the IP address. HIP decouples these two roles while maintaining a binding between an identifier and a set of associated locators. The identifier namespace defined by HIP comprises the public key of the host and is called a Host Identity (HI). HIP also defines the Host Identity Tag (HIT), a 128 bit long truncated hash of the HI, used by applications for communicate.

SUMMARY CHAPTER 2. STATE OF THE ART

Discussion

The new challenges posed by VIs, particularly its multidimensional aspect, requires the development of specific tools for efficient provisioning and management. As VIs are comprehensive entities gathering substantial information, solutions for provisioning IT and network resources should be combined for efficiently manage all their dynamic aspects.

One of the first framework that proposed the combined provisioning of IT and network resources was the HIPerNet. It has demonstrated to be a flexible solution for the dynamic provisioning of virtual infrastructures. The modules composing the HIPerNet can be replaced, enabling its adaptability to different developers.

HIPerNet was used as the base framework to deploy and validate the contributions that are presented in the following chapters. Several patents have been produced [VX-Cap] [VXAlloc], and currently an industrialized version of the HIPerNet framework has been developed and maintained by the LYaTiss company (for more information please refer to http://www.lyatiss.com).

Summary

Virtualization is the main technology that drives the research to Future Internet. Distributed data centers have adopted virtualization as an efficient technology to consolidate IT platforms, improve resource usage, and decrease costs (e.g., with IT administration, power consumption, and cooling) [START_REF] Festor | Special issue on virtualization[END_REF].

A new business model has been explored for outsourcing IT infrastructures [START_REF] Rosenberg | The Cloud at Your Service[END_REF]. Instead of buying new resources, several enterprises are renting on-demand services to complete their IT infrastructures, following a pay-as-you-go model. Clouds have consolidated the on-demand provisioning of virtualized services (e.g., IaaS, PaaS, SaaS). In addition, Cloud Networking has proposed a new wave of service provisioning dedicated to dynamic interconnection of virtual entities. A dynamic virtual link can be established with a specific configuration (e.g., security, bandwidth) to interconnect distributed IT resources (e.g., data centers, Private and Public Clouds).

Recently, the combined provisioning of IT and networking resources has been proposed, composing a malleable computing-and-communication entity identified as Virtual Infrastructure. VIs can be provisioned on top of multiple distributed physical substrate, sharing their resource capacities. The HIPerNet framework was developed as a proof of concept, to provide dynamic VIs.

Although the VI concept is a motivating scenario, reviewing the existing solutions for dynamic resource provisioning, we observe that research and engineering work is still required to enable its real exploitation. As VIs are a relatively new concept, the development of tools to specify and manipulate these entities (e.g., allocate, provision, and execute) are required to facilitate its adoption by users.

Four of these tools are described in the following chapters: a language for specifying VIs; a mechanism to translate a workflow-based application into a VI specification; an allocation algorithm for mapping VIs on top of distributed and virtualized substrates; and a service for providing transparent reliability for virtual resources. Each chapter presents a literature review specifically related to the subject and problem that it addresses.

-THREE -

A language for describing VIs

Conclusions

The work presented in this chapter was published at the Second International Conference on Networks for Grid Applications (GridNets 2008) [START_REF] Koslovski | VXDL: Virtual Resources and Interconnection Networks Description Language[END_REF]. VXDL has been adopted by recent projects (such as HIPCAL [HIP], CAR-RIOCAS [START_REF] Audouin | CARRIOCAS project: An experimental high bit rate optical network for computing-intensive scientific and industrial applications[END_REF], GEYSERS [GEY], and SAIL [SAI]) as one of the languages used to specify virtual infrastructures, and is part of the solutions patented by the LYaTiss company (http: // www. lyatiss. com ) and the Institut National de Recherche en Informatique et en Automatique (IN-RIA, http: // www. inria. fr/ ) [VXCap] [VXAlloc]. In addition, an open forum for discussions and improvements is being launched (http: // www. vxdlforum. org/ ).

Introduction

W

e have seen that Virtual Infrastructure (VI) is a new concept based on combined and interconnected dynamic provisioning of IT and network resources. VIs are malleable entities requested and customized by users according to their specific requirements.

Applications differ in the hardware and software configurations required to run successfully. Standalone applications usually require VIs with high computing capacity, whereas distributed applications, in addition to computational resources, often demand VIs with large communication capabilities. Distributed applications may transfer large databases across networks for processing while exchanging very small and sensitive messages. A deadline can be specified to enforce efficient use of reserved resources as well as to shorten the task completion time [START_REF] Agapi | Optimizing deadline-driven bulk data transfers in overlay networks[END_REF]. Low latency communications (for example, Message Passing Interface -MPI [MPI, 1995]) require strong quality-of-service and can benefit from end-to-end bandwidth reservation and isolation services.

The VI concept introduces a complete abstraction of physical resources and their geographic locations, which poses new challenges in specifying and executing high-end applications. Many factors can directly impact application performance, such as the amount of data to be processed, the geographical location, distribution and confidentiality of the data, and the indeterminism of the required computational power. These factors must be translated into virtual infrastructure requirements in terms of computation, storage, and communication capacities.

In general, descriptive languages are a way to specify and detail the resources users need. Due to a VI's complexity, a language for describing its composition must be abstract enough and more adaptive than conventional resource-description languages and models. In addition, it needs to combine the spatial and temporal aspects of virtual infrastructures.

This chapter proposes the Virtual Infrastructure Description Language (VXDL), an XML-based language for specifying and modeling VIs. VXDL allows the identification and parameterization of virtual resources and groups of resources (according to their functionalities), as well as the network topology (based on the link-organization concept). It also introduces the internal virtual infrastructure timeline, which explores the elasticity of VIs, enabling application providers to specify the exact intervals when virtual resources are provisioned.

The rest of this chapter is organized as follows. Section 3.2 discusses the main projects, languages, and standards that have been proposed to describe computing resources and network topologies. It also reviews the motivations and needs for a new language for specifying virtual infrastructures. VXDL is presented in Section 3.3, and Section 3.4 concludes this chapter.

State of the art

The description of IT resources and network topologies has been the focus of several studies over the past years. Essentially, the proposed languages differ in the context and expressiveness of their grammars. In this section, we review resource and network description languages, discuss languages for describing virtual infrastructures, and review standardization efforts.

IT resource description languages

The list of languages presented here contains those used to describe computing resources in Grids and others for general purpose description. The languages are reviewed in the order they were proposed and published since a chronological analysis helps observe constant improvements in the descriptive process. In early languages, users specified only the number of computers required to execute their applications. As Grid Computing evolved, the level of detail increased.

ClassAd: this language was developed in the context of the Condor project [CON] to allow for job submission and resource reservation in Grids [START_REF] Raman | Matchmaking: Distributed Resource Management for High Throughput Computing[END_REF]]. Clas-sAd is a semi-structured language that does not specify a rigid grammar. By comparing expressions, it aims to perform a mapping between described attributes (substrate) and specified values (request). Attributes can be default values (e.g., integers, reals) or com-plete requests (queries) with parameters for resource reservation (start and end dates). ClassAd does not provide attributes to describe network topology.

Redline: proposed to improve the resource description performed by ClassAd. It presents three main innovations [START_REF] Liu | A Constraint Language Approach to Grid Resource Selection[END_REF]: the description and parameterization of groups of resources; the introduction of pre-defined functions, such as sum(), count() and max() to personalize the definition of resources; and the introduction of predicates including forall x in set, which allowed the application of a single rule for a set of resources.

SWORD: is a resource discovery system for shared wide-area platforms [START_REF] Oppenheimer | Design and implementation tradeoffs for wide-area resource discovery[END_REF]. This system supports queries described in a specific XML format (SWORD XML) or using the ClassAd language. The proposed description format, XML SWORD, enables the specification of individual resources, clusters and the union of clusters. Queries specified with SWORD can also inform simple parameters for network configuration, such as the latency and bandwidth allowed on interconnections.

JSDL: the Job Submission Description Language (JSDL) [START_REF] Anjomshoaa | Job Submission Description Language[END_REF] allows the description of simple computational tasks of non-interactive applications for traditional Grid environments. A job defined in JSDL specifies parameters such as required resources, execution limits (in terms of CPU time or consumed memory), and command line to execute the application.

GLUE: is an information model composed of objects developed to unify the modeling and representation of Grid resources and their relation [START_REF] Andreozzi | GLUE Schema Specification[END_REF]. The concept discussed in GLUE is the usage of Computing Elements (CE) that include resource features, policy tasks, and the interaction among CE's. GLUE allows the representation of homogeneous clusters and sets of heterogeneous resources. Each CE can be individually specified and parameterized; its required software and functionality can be explicitly defined.

BPDL: Broker Property Description Language follows the XML standard and proposes a grammar that enables resource description in terms of quality-of-service attributes, required software and middleware, and security policies [START_REF] Kertesz | BPDL: A Data Model for Grid Resource Broker Capabilities[END_REF]. This language was developed to represent a whole IT substrate, and later improved to include attributes for specifying monitoring metrics, fault tolerance requirements and scheduling policies.

Network description languages

The languages to describe network resources and topologies discussed here were developed with distinct contexts and goals, such as VPN representation, generic and abstract network description, network simulation, and telecommunications management network [START_REF] Pras | Introduction to TMN[END_REF]] [ITU-T, 1995]. In general, these languages enable a potential representation of networks, but without attention to IT resources.

CIM: the Common Information Model (CIM) specification [CIM, 1999] describes a common set of objects and their relationships. The CIM architecture is based on UML and provides the CIM Query Language (CQL) to select sets of properties from CIM-object instances. CQL, a subset of SQL-92 [SQL, 1992] with extensions specific to CIM, allows queries for a set of resources with certain configurations, but does not have parameters to interact with the allocation system (e.g., informing the basic location of a component).

NDL: the Network Description Language (NDL) [NDL] [der Ham et al., 2007] is a collection of schemas (topology, layer, capability, domain and physical) used to represent a network infrastructure at different levels [START_REF] Dijkstra | A multi-layer network model based on itu-t g.805[END_REF]. This language is guided by the general-purpose Resource Description Framework (RDF) [RDF], used for representing information on the Web. RDF (and NDL) explores a graph data model composed of a set of RDF triples (a subject, an object and a predicate). A subject (resource) has a set of describing objects that are interconnected by predicates.

Virtual infrastructure description languages

Other resource description models are found when analyzing projects that are also investigating network virtualization and provisioning of virtual resources.

vgDL: Virtual Grid Description Language [START_REF] Chien | The Virtual Grid Description Language: vgDL[END_REF] enables users to provide an initial description of the desirable virtual resources (similar to templates). vgDL proposes three types of virtual aggregations: LooseBag, TightBag and Cluster. The meaning of each type is abstracting the kind of network interconnection that is provisioned. libvirt: this API [LIB] is a toolkit to interact with different virtualization platforms. It contains an XML format that enables low-level description and configuration of virtual machines and virtual network entities (including bridges, Network Address Translation -NAT, and routed networks).

Rspec model: the Rspec model [RSp], developed in the context of the GENI project [GEN], aims to provide interoperability and data exchange between components of a virtualized execution scenario (e.g., users, resource allocator). The proposed language does not define boundaries in the description, which means that each component can be described with a different level of detail. This approach can help the interaction among computational entities, but it introduces complexity in defining the level of description that is enough for each situation.

Standardization efforts

Currently, several working groups are investigating and proposing standard models to enable the interaction among different contexts and technologies. We review the standardization projects related to network and resource description, and Cloud Computing models.

OGF NML-WG: the Open Grid Forum (OGF) Network Markup Language Working Group (NML-WG) [NML] is addressing the problem of inter-domain light-path provisioning by defining a standard schema for network topology description and information exchange at the network-domain level. The schema describes network objects and their relationships. The basic NML objects and extended objects can be represented in multiple syntaxes, including XML and RDF.

OGF NSI-WG: the OGF Network Service Interface Working Group (NSI-WG) [NSI] is investigating recommendations to define a generic network service interface. More specifically, this working group focuses on defining an interface that is exposed by service providers (including functionalities), and called by different entities, such as users, other network service providers, and middleware.

OGF OCCI-WG: OGF Open Cloud Computing Interface Working Group (OCCI-WG) [OCC] is investigating a solution to interface with Cloud Infrastructures exposed as a service. OCCI defines a modular API and Cloud infrastructure resources (compute, network and storage) are described using a simple key-value based descriptor format.

DMTF OVF: the specification level addressed by the Distributed Management Task Force (DMTF) Open Virtualization Format (DMTF OVF) [DMTF, 2009] is the packaging and distribution of software to be run on virtual machines. OVF enables the description and parameterization of virtual machines in terms of hardware configuration (devices such as hard-disks, network interfaces, and memory) and the information of software (e.g., operating system and specific legacy services) that runs during the execution time. In addition, OVF permits the configuration of the operating system (e.g., host names, IP address, subnets) and application (e.g., DNS name, databases and external services). An extension of OVF, proposed to address the elastic aspect of virtual infrastructures, includes the definition of key performance indicators that are monitored during the reservation time [START_REF] Galán | Service specification in cloud environments based on extensions to open standards[END_REF].

W3C USDL: the Unified Service Description Language Incubator (USDL) Group Charter [USD] is defining a language for describing general parts of technical and business services and allow them to become tradable and consumable. Technical services are those based on WSDL, REST or other specifications, whereas business services are defined as activities offered by a service provider to a consumer to create value for the latter. The business services are more general and comprise manual and technical services. This work group started in late 2010 and as of writing of this chapter the documentation and proposition were still under development.

Discussion and analysis

Users need to define the virtual infrastructures they request according to their applications' requirements. A language dedicated to virtual infrastructure description must be abstract enough and more adaptive than conventional resource description. During the specification process, new challenges coming from virtualization techniques have to complement the management, configuration and execution features of classical infrastructure description languages. For example, the description languages explored in Grids only enable the specification of computing resources and jobs that the users submit. They do not offer attributes to deal with the elastic aspect of VIs' components.

A VI is modeled as a graph composed of vertices (IT resources) and edges (network links). Due to its complexity and large number os components, attributes, and particularities, this compute and communication resource graph must be described as a single entity. Standardization groups are identifying the requirements and proposing models to specify resources and applications in the context of Cloud Computing (IT resource only), but the combined specification of IT resources and network topologies are not addressed by these models.

Usually, languages for describing networks do not offer enough attributes for specifying computing resources, which are interconnected by these networks. Although a network description language offers enough attributes to specify the network topology, it becomes necessary to complement it with an comprehensive model for defining IT resources. Moreover, a language dedicated to VI description needs to combine the space and temporal aspects of these entities.

Table 3.1 summarizes the languages reviewed in this section. The column values were selected considering the definition of a virtual infrastructure, its components and properties. The components, identified in Section 2.4 in Chapter 2, consist of: vNodes, vAc-cessPoints, vRouters, vStorage, and vLinks. The selected properties represent the key attributes for specifying a VI: location, monitoring, software configuration, reliability, and elasticity. Location is related to the interaction between user and management framework. A user can define the exact geographical location where the virtual component must be provisioned due to specific reasons (e.g., data dependency, security, governmental law). Monitoring, reliability, and elasticity indicate the presence of attributes for configuring the services exposed by an InP. For instance, defining the reliability and monitoring levels, or defining the elasticity rules (capacity variation per time). Software configuration indicates the availability of attributes to configure and interact with the legacy software running on the virtual resources (e.g., configuring rules for load balancing, number of active threads of a pager server) The value √ indicates the availability of an attribute to specify the required VI component. As we can observe, the language that offers more attributes covers only 55% of VI components and particularities. Most languages do not reach 37%, and none allows the complete description of VI components. This analysis hence shows the need for a specific language to describe virtual infrastructures, by enabling the parameterization of all their components, attributes, and particularities.

Virtual Infrastructure Description Language -VXDL

VXDL allows the description of a VI or a compute-and-communication resource graph [START_REF] Koslovski | VXDL: Virtual Resources and Interconnection Networks Description Language[END_REF]. As presented in Figure 3.1, VXDL enables the specification of a VI according to different levels of application requirements (e.g., SaaS and PaaS). It fulfills all the requirements in Table 3.1 and brings four original aspects:

• the joint specification of network and computing elements;

• a language that permits a simple and abstract description of complex virtual infrastructures; • the VI timeline specification used to describe the temporal and elastic aspects of virtual infrastructures, defining intervals where each resource is really required; and

• the specification of attributes representing the expected Quality-of-Experience (QoE). As discussed earlier, users can model VIs based on the requirements of their applications. In this context, VXDL enables the development of requests such as "I am a user from London, and I would like the provisioning of a VI composed of 2 vNodes, with reservation slot starting on 10/11/2011 at 14:00:00, lasting 1 hour. One node must be geographically located in Lyon and the other in Paris. The vNodes must have 2 GB of RAM, and 1 CPU core of 2.0 GHz. My vNodes are critical and must be provisioned with a reliability of 99.9%. My application requires a bi-directional virtual link of 10 Mbps to communicate efficiently.".

In addition, Infrastructure Providers (InPs) can share requests, propose templates, and expose a subset of virtualized resources. This information is essential in distributed discovery and allocation systems. For example, an InP A could share an information and request a VI composition using resources of InP B: "I would like to extend the VI of my client over your substrate for a reservation period starting on 10/08/2011 at 08:00:00, during 3 months. To be executed, the financial-information system operated by this company requires 8 storage servers and 20 computing nodes. Each data server must have a storage capacity of 1 TB, while the computing nodes must have 4 GB of memory. These resources will be used by a temporary branch of my client's company, and must be interconnected with the headquartered access point located in California, through a dedicated communication channel with 100 Mbps of bandwidth capacity. Both IT and network resources must be provisioned with a high-level security to guarantee the data confidentiality.".

These two sentences indicate the scenarios where VXDL acts. In Section 3.3.3 we describe examples to show how the language helps the description of VIs in both contexts.

Language grammar

VXDL proposes a simple and high level grammar to specify virtual infrastructures hiding hardware details. The syntax and lexical rules of VXDL are presented in Figure 3.2 and Figure 3.3 using the Extended Backus-Naur Form (EBNF) [START_REF] Ebnf | [END_REF]. EBNF adds the regular expression syntax of regular languages to the BNF notation [START_REF] Crocker | Augmented BNF for Syntax Specifications: ABNF (RFC2234)[END_REF], in order to allow very compact specifications. The definitions of string, integer, float, double, boolean, date and time are not presented to simplify the description, concentrating only in defining the elements of VXDL. These elements follow the international format in accordance with W3C recommendations [START_REF] Biron | W3C Recommendation: XML Schema Part 2: Datatypes[END_REF]. As observed in these figures, VXDL follows the XML standard. An XML Schema Definition (XSD) and the documentation of VXDL are maintained on http://www.ens-lyon.fr/LIP/RESO/ Software/vxdl/.

Following a tree organization, a VXDL description begins by the definition of virtual-Infrastructure, as shown by the first line of Figure 3.2. Thus, the virtual infrastructure is specified and composed respecting the defined rules. We can note that a set of elements are optional permitting the adaption of VXDL to different contexts with specific requirements. In the next section, we discuss the semantic of VXDL and demonstrate the usage of its grammar.

VXDL file structure

As presented in Figure 3.4, a VXDL file structure is conceptually composed of four parts that represent all aspects of a VI:

• the general description of the VI, and the definition of default values;

• the description of virtual resources;

• the description of the virtual network topology; and

• the description of the internal VI timeline.

A VXDL document is organized as follows: the root element virtualInfrastructure contains recursive entries for vNode, vRouter, vAccessPoint, vStorage, vLink, and vGroup elements. Each virtual resource is identified and referred by a unique identifier (id attribute). In addition, the document contains a single entry for virtualTimeline description. The description of VXDL elements is partially optional. It is possible to specify a simple communication infrastructure (for example, a virtual private network) or a simple aggregate of end resources without any network topology description.

The UML specification of VXDL is presented in Figure 3.5, showing the interaction and dependency of its components. To simplify the language definition, some of the attributes are factorized and grouped in special classes such as common and capacity. Moreover, a special component, vResource, is used to abstract the interaction among other virtual resources.

In the following sections, we detail the conceptual organization of VXDL documents.

VI general description

The first part of a VXDL document concerns the general and default attributes of a virtual infrastructure. Performing an analogy with a graph specification, this section of VXDL defines the default attributes for all VI components, and additional attributes not placed in a graph. Looking at Figure 3.5, the object virtualInfrastructure represents the general description, being composed of the following attributes (following the inheritance of common):

• the identification of the infrastructure; ', id, [after], {activate}, totalTime, '</timeline>'; after = '<after>', string, '</after>'; activate = '<activate>', string, '</activate>'; longInterval = '<interval>', longValues, '</interval>'; longValues = '<min>', long, '</min>', '<max>', long, '</max>'; longSet = '<set>', longValues, '<step>', long, '</step>', '</set>'; doubleInterval = '<interval>', doubleValues, '</interval>'; doubleValues = '<min>', double, '</min>', '<max>', double, '</max>'; doubleSet = '<set>', doubleValues, '<step>', double, '</step>', '</set>'; • an attribute informing if the VI being described is an extension of a VI already provisioned;

memoryUnit = 'MB' | 'GB' | 'TB'; frequencyUnit = 'GHz' | 'MHz'; bandwidthUnit = 'Gbps' | 'Mbps'; latencyUnit = 'us' | 'ms' | 's';
• the reservation period (start date and duration);

• the default security and reliability levels;

• the required monitoring level;

• the global geographical location;

• the owner and the list of users allowed to access and manipulate the VI;

• and the composition of Shared Risk Groups (SRGs).

The values of some attributes (e.g., the levels of monitoring, security and reliability are defined by the substrate configuration and availability) are defined and exposed by the InP during the SLA negotiation. The default definitions informed in this section can be refined for each element. For example, a VI defined with default reliability requirement of 99.9% and default security level bronze, can have internal critical components with 99.99% and gold requirements, for reliability and security, respectively.

By defining SRGs, users can identify groups of critical resources that should not be allocated on the same physical resources. This definition is an extension of the Shared Risk Link Groups (SRLGs) used to avoid the allocation of back-up MPLS tunnels in the same SRLG of the interfaces they are protecting [START_REF] Kompella | Routing Extensions in Support of Generalized Multi-Protocol Label Switching (GMPLS)[END_REF]. Besides virtual links, VXDL allows SRGs composed of IT resources. SRGs can be used for defining the reliability requirements at the user level, instead of requesting an InP service (as discussed in Chapter 6).

In addition, the virtualInfrastructure element also has entries for the components composing the other three main conceptual parts of VXDL, as described in the sequence. c Copyright 2011 by Guilherme Piêgas Koslovski

Virtual resources description

The second part of VXDL describes, in a simple and objective way, all the IT resources and groups of them. Keeping the analogy with a graph description, these components are responsible for describing the vertices. The objects with the blue color and white font shown in Figure 3.5 are mainly explored to describe virtual resources. One can observe the presence of attributes that specify the basic building blocks of virtual infrastructures: vNodes, vAccessPoints, vStorage, and vRouters, as discussed in Section 2.4.2 in Chapter 2. VXDL allows the basic resource parameterization (values for memory size, CPU speed, among others), using simple values, intervals, and sets of acceptable values. A specific attribute, the tags, enables the specification of a set of key-value pairs, allowing the interaction of VXDL with other description languages and models. Tags can also be used to transmit software configuration to the management framework, aiming for automatic configuration.

An important feature of VXDL is that it proposes cross-layer parameters (i.e. application level and physical level attributes) for all components. For example, with the specification of location and exclusivity, and the composition of shared risk groups, users can directly transmit application-specific information and constraints to the management framework. The location attribute corresponds to a physical embedding constraint, which places a virtual resource (group, or an entire VI) in a given physical location (e.g. a city, a country, a site, or a machine), for an application-or user-specific reason.

On the other hand, on a virtualized physical substrate, multiple virtual machines can be executed in the same physical host sharing the available resources. VXDL enables the specification of exclusivity, meaning that only one virtual machine must be allocated in a physical host, disabling any sharing to offer explicit security and performance guarantees. In addition, software to be deployed on resources can be specified by this part of the VI description.

Analyzing the virtual resources individually, we observe that the attributes proposed to describe vRouters enable the specification of data-planes and control-planes individually, being more adaptable to different technologies and usage scenarios [GEY] [SAI]. Also, the attributes to specify vAccessPoints enable the definition of VI boundaries, and the rules that guide the interaction of the VI with the external world, not part of the VI (e.g., a public resource, the Internet). A NAT, a set of masquerade rules, and a Load Balancer are proposed to interconnect and organize the incoming and outcoming traffic.

Finally, besides the storage capacity, attributes to identify the type of storage and the volume configuration are proposed. The type of a vStorage can be chosen among DAS (Direct-attached storage), NAS (Network-attached storage), or SAN (Storage Area Network) technologies.

Virtual network topology description

Continuing the line of a graph description, these elements define attributes to specify the edges of VI graph. These virtual links define interconnections between IT resources, between individual resources and groups, inside groups, and among groups.

The dark-blue color and white font components presented in Figure 3.5 show the main attributes available to describe virtual links. The required capacity and quality-ofservice values are defined by the bandwidth (forward and reverse) and latency attributes. Maximum and minimum values can be defined for latency and bandwidth (forward and vLinks are specified as source-destination pairs. The extremities of a virtual link can be a single IT resource (e.g., vNode, vRouter, vAccessPoint, vStorage) or a group of resources. Figure 3.6 presents some topologies that can be described with VXDL: a ring, a tree, and a star. While many topologies can be described using VXDL, we select these three to exemplify the source-destination pairs and the positioning of a vRouter. In this example, the Ring topology is described requiring a uni directional path with bandwidth of 25 Mbps to interconnect six vNodes. The fragment of VXDL presented in Figure 3.7 shows the description of this topology, where only one vLink was specified and a set of pairs defined the resources that are interconnected by this link. The Star topology exemplifies the presence of a vRouter (r v 1) to control the traffic between five vNodes.

Virtual timeline description

Finalizing the analogy with a graph description, this section of VXDL describes the elastic aspects of VIs or, in other words, the subgraphs grouped by time slots. Virtual infrastructures are allocated and provisioned for a defined time slot. Time slot duration is specific to the substrate-management framework and consequently this parameter is configured by the manager of the virtualized environment.

Often, the virtual infrastructure components are not used simultaneously or all along the virtual infrastructure lifecycle. Thus, the specification of an internal timeline for each virtual infrastructure can help optimizing the allocation, scheduling, and provisioning of virtual resources.

Figure 3.8 explains the timeline description of a VI composed of five IT resources: three computing clusters (cluster A, B, and C ), a database node, and a visualization node. This VI is divided in three stages according to the resource usage. In stage I, a data transfer is performed between the database server and the computing clusters. At this moment, a network interconnection with enough capacity is required to perform the transfer before a defined deadline. After the data transfer, stage II begins, during which a computation is performed and clusters must be interconnected with a different network configuration. Finally, in stage III a data transfer must be carried out for the final visualization of results. Again, virtual links with enough capacity must be provisioned to interconnect the computing clusters with the visualization resources.

By analyzing this example it is possible to observe that the specification of internal timelines can help management frameworks in resources allocation and provisioning: the timeline indicates the exact moment where resource are required helping InPs in not wasting over-provisioned capacities. If a VI lifetime is long enough and can be divided in well-defined stages of resource usage, the infrastructure provider can activate the virtual resource only when they are really required by the application. In Figure 3.5 the dark-blue objects represent the attributes offered to specify virtual timelines.

t i o n > </v L i n k> <v L i n k i d=" v i r t u a l l i n k 2 "> <bandwidth> <f o r w a r d > <s i m p l e >25.0 </ s i m p l e > <u n i t >Mbps</ u n i t > </f o r w a r d > </bandwidth> <s o u r c e >r v 2</ s o u r c e > < d e s t i n a t i o n >r v 3</ d e s c r i p t i o n > </v L i n k> <v L i n k i d=" v i r t u a l l i n k 3 "> <bandwidth> <f o r w a r d > <s i m p l e >25.0 </ s i m p l e > <u n i t >Mbps</ u n i t > </f o r w a r d > </bandwidth> <s o u r c e >r v 3</ s o u r c e > < d e s t i n a t i o n >r v 4</ d e s c r i p t i o n > </v L i n k> <v L i n k i d=" v i
t i o n > </v L i n k> <v L i n k i d=" v i r t u a l l i n k 6 "> <bandwidth> <f o r w a r d > <s i m p l e >25.0 </ s i m p l e > <u n i t >Mbps</ u n i t > </f o r w a r d > </bandwidth> <s o u r c e >r v 6</ s o u r c e > < d e s t i n a t i o n >r v 1</ d e s c r i p t i o n > </v L i n k> </ v i

Describing VI scenarios with VXDL

This section presents examples of scenarios where VXDL can be used. It aims to demonstrate the usage and the expressiveness of VXDL.

Requesting and provisioning vNodes and vLinks

The first example, explored in the context of the HIPCAL project [HIP], demonstrates the usage of a simple set of vNodes during the reservation and activation. The goal of this example is to show how the attributes are used in the description and provisioning processes.

Figure 3.9 presents the description of two vNodes interconnected by a single vLink. The vNodes require a 2 GHz CPU (1 core) and a memory capacity between 2 GB and 4 GB. Any value within this range is acceptable. Observe that the VI requires a monitoring service described as gold. The meaning of this keyword is defined by the infrastructure provider during the service definition and exposition.

Figure 3.9 also describes a vLink to interconnect node 1 and node 2, requiring a bandwidth capacity between 10 Mbps and 20 Mbps. For the sake of simplicity, this example does not describe the VI timeline.

A management framework that receives this VXDL description must allocate and provision the virtual resources. During the allocation, the framework decides on a single value to be provisioned within the acceptable ranges informed by the user. Usually this decision if performed by the infrastructure provider considering the load distribution, economic aspects, physical substrate fragmentation, among others factors (we discuss the allocation problem in detail in Chapter 5).

After the decision process, a new VXDL description is composed and returned to inform relevant information about the provisioned VI, such as: i) which values were provisioned between the ranges specified by the user; ii) the IP address through which the virtual resources can be accessed; and iii) the monitoring address of every resource from which a user can access on-line information and metrics (in accordance with the service exposed by the infrastructure provider).

Figure 3.10 presents a VXDL description that states the values selected to be provisioned by the management framework. In this example, node 1 was provisioned with 3 GB of memory, and node 2 with 2 GB. Also, the virtual link was configured with a bandwidth of 10 Mbps for both forward and reverse. Finally, the attributes highlighted in green show the address used to access the virtual resources, and where monitoring information is available.

Multiuser game service

This scenario presents a virtual infrastructure requested to host a multiuser game service where client requests can arrive at any time during the reservation period. This example was developed in the context of HIPCAL [HIP] and CARRIOCAS [CAR] projects, and the main objective is to demonstrate how VXDL can be used to specify dynamic VIs where the number of resources and their configuration change during the execution time.

As shown in Figure 3.11, a virtual server must be provisioned to host the game service during a defined period. Each client who wishes to play must connect to the central server. Virtual links between clients access-point and game server are dynamically provisioned to ensure the Quality-of-Service (QoS) of players. Clients can be located at different cities. The dashed boxes and links represent resources that must be dynamically provisioned, whereas the solid boxes and links represent the connected clients.

The VI that will host the multiuser game service requires a reservation slot with a duration of 10 days, starting at 2011-04-21 08:00:00 and is composed of:

• Virtual Infrastructure:

a centralized game server (vNode) able to connect to a maximum of 100 clients (vAccessPoints) using TCP protocol for communication;

-The security level required is gold among the options: basic, silver, gold, and platinum.

• Game server requirements:

-RAM capacity: 8 GB;

-Storage capacity: 100 GB;

-The game server is a critical component of this VI. Thus, a high reliability level is required (platinum in this case, among the options: basic, silver, gold, and platinum).

• Virtual links:

-100 vLinks must be dynamically provisioned, respecting the arrival of remote clients;

-Each virtual link must have at least 10 Mbps of bandwidth reserved to be provisioned when the client requests the connection. <f r e q u e n c y > <s i m p l e >2</ s i m p l e > <u n i t >GHz</ u n i t > </ f r e q u e n c y > </cpu> <memory> < i n t e r v a l > <min >2.0</min> <max>4.0</max> </ i n t e r v a l > <u n i t >GB</ u n i t > </memory> </vNode> <vNode i d=" node 2 "> <cpu> <c o r e s >1</ c o r e s > <f r e q u e n c y > <s i m p l e >2</ s i m p l e > <u n i t >GHz</ u n i t > </ f r e q u e n c y > </cpu> <memory> < i n t e r v a l > <min >2.0</min> <max>4.0</max> </ i n t e r v a l > <u n i t >GB</ u n i t > </memory> </vNode> <v L i n k i d=" l i n k 1 "> <bandwidth> <f o r w a r d > < i n t e r v a l > <min >10.0 </min> <max>20.0 </max> </ i n t e r v a l > <u n i t >Mbps</ u n i t > </f o r w a r d > <r e v e r s e > < i n t e r v a l > <min >10.0 </min> <max>20.0 </max> </ i n t e r v a l > <u n i t >Mbps</ u n i t > </ r e v e r s e > </bandwidth> <s o u r c e >node 1</ s o u r c e > < d e s t i n a t i o n >node 2</ d e s c r i p t i o n > </v L i n k> </ v i r t u a l I n f r a s t r u c t u r e > </ d e s c r i p t i o n > Within VXDL, this scenario can be presented using two types of description: one to specify the game server, and another to specify the clients. An initial VXDL file describes the game server configuration and prepares the remote vAccessPoints. The submission of a new VXDL informing the location of the new client access point is necessary for each client that arrives to play the game. At this moment, the virtual link is provisioned to interconnect client and game server. The VXDL file presented in Figure 3.12 shows the initial configuration.

The requests of client connections can arrive at any time during the reservation period. The VXDL description shown in Figure 3.13 represents the demand for provisioning a vLink to interconnect the new client to game server. In other words, this VXDL extension file informs that one of the vAccessPoints prepared during the initial configuration became active. In this case, a client located at City N informs its IP address and requests the connection to the original VI for a period of 2 hours.

We extend the discussion of this example to identify how vLinks can be provisioned to interconnect the new client with the game server. Figure 3.14 exemplifies two possible scenarios for this dynamic provisioning.

• Case A: the client is outside the administrative domain. By administrative domain we mean the domain of virtualized and exposed resources that is administered by the management framework. Thus, the vLink can be provisioned with all required guarantees (forward and reverse bandwidth) until the end of the administrative domain where the vAccessPoint is located.

• Case B: the client is within the administrative domain. In this scenario, a vLink can be provisioned until the client's vNode instead of the vAccessPoint. Consequently, the full path that provisions the vLink has the same guarantees.

VISUPIPE

The High Performance Collaborative Remote Visualization (VISUPIPE) software generates 30 images of 20 megapixels x 32 bits per second x 2 for stereo, which results in a < v i r t u a l I n f r a s t r u c t u r e i d=" m u l t i u s e r game s e r v i c e " owner=" k o s l o v s k i "> <s t a r t D a t e >2011-04-21T08 : 0 0 : 0 0 < / s t a r t D a t e > <t o t a l T i m e >P10D</t o t a l T i m e > <s e c u r i t y >g o l d </ s e c u r i t y > <vNode i d="game s e r v e r "> < r e l i a b i l i t y >p l a t i n u m </ r e l i a b i l i t y > <memory> <s i m p l e >8</ s i m p l e > <u n i t >GB</ u n i t > </memory> <s t o r a g e > <s i m p l e >100</ s i m p l e > <u n i t >GB</ u n i t > </ s t o r a g e > </vNode> <vGroup i d=" a c c e s s p o i n t s " m u l t i p l i c i t y =" 1 0 0 "> <v A c c e s s P o i n t i d=" c l i e n t "> <n The execution of the VISUPIPE application requires a virtual infrastructure composed of five clusters interconnected by virtual links with different requirements. The virtual infrastructure must be reserved for 11 hours, starting at 2011-04-21 08:00:00. More specifically, the virtual infrastructure is composed of:

• Storage cluster:
-Composed of 20 nodes, each requiring a minimum storage capacity of 200 GB; -Nodes must be interconnected by links with maximum latency of 0.200 ms.

• Filtering cluster:

-Composed of 40 nodes, each requiring a minimum memory capacity of 4 GB and a minimum CPU speed of 2 GHz;

-Nodes must be interconnected by links with maximum latency of 0.400 ms and minimum bandwidth of 100 Mbps.

• Mapping cluster:

-Composed of 30 nodes;

-Each node requires a minimum memory capacity of 4 GB, a minimum CPU speed of 2 GHz, and a minimum storage capacity of 80 GB.

• Rendering cluster:

-Composed of 10 nodes, each requiring a minimum memory capacity of 8 GB, and a minimum CPU speed of 2 GHz;

-The nodes interconnection tolerates a maximum latency of 0.150 ms.

• Visualization cluster:

-Composed of 30 components. Each node requires a minimum memory capacity of 8 GB, and a minimum CPU speed of 2 GHz;

-The nodes interconnection required is a maximum latency of 0.200 ms;

-All nodes must be interconnected with a specific device (visualization wall ) located in Lyon, France.

• Network topology configuration connecting the clusters:

-Unidirectional links with minimum bandwidth capacity of 38.4 Gbps between:

Storage cluster to Filtering cluster, Filtering cluster to Mapping cluster, Mapping cluster to Rendering cluster, and Rendering cluster to Visualization cluster.

Conclusions

VIs are malleable entities that can be composed according to users' and applications' requirements, which can differ in terms of computing, storage and communication [START_REF] Vicat-Blanc | Cluster and Computing Networks[END_REF]. The absence of one may affect the application's performance, but the over-provisioning can increase the cost for users.

An efficient and expressive description language is crucial for VI instantiation as it is the way (tool) users define the requirements of their applications. In this chapter, we presented the Virtual Infrastructure Description Language (VXDL), a powerful language that enables the complete description and parameterization of VI components. VXDL has a simple and objective grammar that offers attributes to specify virtual resources, virtual network topology, and the internal timeline of virtual infrastructures.

Examples applied to different projects were presented. In each example, we described the scenario, objectives, and how VXDL can be used. In some cases, the discussion was extended to show how a VXDL description (or a VI specification) is instantiated by infrastructure providers, and how VXDL is exploited for carrying the provisioned configuration.

Some attributes proposed by this language open opportunities for further studies. For example, a user can specify the required reliability level for a service, which is then implemented by the InP in a transparent way and charged from the final user (we discuss a mechanism to provide reliable virtual infrastructures in Chapter 6). On the other hand, an advanced user can define the shared risk groups. The benefits and drawbacks of each scenario should be identified, considering allocation costs and application performance.

Finally, it is important to mention that VXDL has been adopted by several software solutions as an intermediate communication tool between application and the execution environment, including: the HIPerNet framework [HIPerNet], the MOTEUR workflow manager [MOT], and the LYaTiss solutions for VI orchestration in the Clouds (VXDL parser [VXDLParser], LYaTiss Weaver [START_REF] Lyatiss | [END_REF], LYaTiss Designer, VXDL translator, among others).

-FOUR - The work presented in this chapter was published at the Journal of Grid Computing (JoGC 2010) [START_REF] Truong Huu | Joint elastic cloud and virtual network framework for application performance optimization and cost reduction[END_REF], the First International Conference on Cloud Computing (CLOUDCOMP 2009) [START_REF] Koslovski | Executing distributed applications on virtualized infrastructures specified with the VXDL language and managed by the HIPerNET framework[END_REF], and as a research report [START_REF] Vicat-Blanc | Exploring the Virtual Infrastructure as a Service concept with HIPerNet[END_REF]. The work has been done in collaboration with the I3S team (http: // www. i3s. unice. fr ) in the framework of the HIPCAL project [HIP].

Introduction

C

loud Computing is increasingly being exploited for providing resources on-demand to users who reserve and then adapt the allocated virtual infrastructures to their application requirements. A challenging problem, both for InPs and users, is to estimate the number of resources to allocate from the Cloud for a specific period. Commercial Clouds implement several schemes to bill for resource usage, most based on coarse-grained metering of the amount of CPU and disk space consumed [AMAa], although network bandwidth is also a critical resource in many applications. Estimating the proper number of resources to allocate is the user's responsibility, an estimation that is far from trivial, especially when considering distributed applications. Assistance in estimating resource consumption and cost management is therefore highly desirable.

The task of determining the size of a VI for supporting the execution of a given application is often difficult. Although a quasi-unlimited number of computing resources can be allocated, a balance has to be found between the VI cost and the expected application performance. Without assistance, the user has to specify a VI solely based on his previous experience in executing the application on the InP substrate.

In theory, a system can estimate the cost of a VI deployment and usage scenario if enough information is known on the application and the VI. However, it is hardly feasible to anticipate the precise needs or behavior of a parallel application on a given a VI.

The general problem of estimating resource requirements for a VI, while minimizing cost and maximizing performance, and translating them into a VI specification is intractable given that it depends on knowing the exact execution behavior of a distributed application. To make the problem tractable, we focus on workflow-based applications by proposing a solution that models the application behavior using the formalism of workflow descriptions. Such a solution is not too restrictive as many coarse-grained distributed applications can be modeled as workflows whose tasks are module invocations [START_REF] Glatard | Flexible and efficient workflow deployement of data-intensive applications on grids with MOTEUR[END_REF]. In this solution, modules to be executed are the nodes of a workflow's directed graph, whereas module dependencies are the edges. Each application module might be invoked a number of times depending on the database size and, as long as no dependency exists between invocations, modules can be performed concurrently. With the workflow formalism, the application logic can be interpreted and exploited to produce an execution schedule estimate.

This chapter thus investigates a mechanism whereby users can foresee the optimal VI components and network topology needed for their application. The mechanism allows users to automatically deploy a VI for executing their applications.

State of the art

The VI design optimization problem is to determine both the number of resources and the network topology needed to run a given application efficiently. Minimizing the number of resources needed is not necessarily the best objective function as it may be better to find a trade-off between VI cost and application performance. Such an objective can be formulated as a cost function whose parameters depend on the size of the allocated infrastructure and its configuration. Both computing resources and network bandwidth have to be considered in this cost function.

Several existing resource allocation and task scheduling strategies for Grid applications focus on matchmaking algorithms whose goal is not to find an optimal allocation, but to identify suitable resources [START_REF] Braun | A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems[END_REF]. Best-effort algorithms such as Min-Min, Max-Min [START_REF] Maheswaran | Dynamic Matching and Scheduling of a Class of Independent Tasks onto Heterogeneous Computing Systems[END_REF] or HEFT [START_REF] Topcuoglu | Performance-effective and low-complexity task scheduling for heterogeneous computing[END_REF] focus only on minimizing the application makespan whereas other QoS constrained algorithms consider a multi-objective scheduling problem [Yu andBuyya, 2005] [Sakellariou et al., 2005]. However, none takes into account the bandwidth of a link for data exchange between workflow modules. Silva et al. [START_REF] Silva | Heuristic for resources allocation on utility computing infrastructures[END_REF] presented a heuristic for resource allocation on utility computing infrastructures that optimizes the number of machines allocated to process tasks and speed up the execution within a budget. However, this heuristic is only suitable for bag-of-tasks problems where tasks are independent and do not communicate.

Some workflow-based allocation algorithms [START_REF] Blythe | Task Scheduling Strategies for Workflow-based Applications in Grids[END_REF]] [Guo et al., 2006] [Mandal et al., 2005] [Xiao et al., 2007] can deliver better performance than matchmaking [START_REF] Bittencourt | Towards the Scheduling of Multiple Workflows on Computational Grids[END_REF]. However, the objective of these algorithms is to minimize the application makespan without taking into account the execution cost on a pay-peruse platform such as Clouds. Ramakrishnan et al. [START_REF] Ramakrishnan | VGrADS: Enabling e-Science Workflows on Grids and Clouds with Fault Tolerance[END_REF] presented a fault tolerant scheduling algorithm that orchestrates multiple workflows on Grid and Cloud infrastructures by duplicating the execution of some workflows thereby increasing the probability of success of individual tasks. This kind of approach, although potentially efficient in reducing execution time, does not consider the VI allocation cost. Senkul et al. [START_REF] Senkul | An architecture for workflow scheduling under resource allocation constraints[END_REF] presented an architecture for workflow scheduling that considers allocation cost and co-allocation of tasks on the same resource, but it does not consider resource heterogeneity.

In addition, resource allocation algorithms for mapping grid-based workflows onto Grid resources have been proposed in the context of service level agreements [START_REF] Dang | Mapping Heavy Communication Grid-Based Workflows Onto Grid Resources Within an SLA Context Using Metaheuristics[END_REF] [ [START_REF] Dang | Resource allocation algorithm for light communication grid-based workflows within an SLA context[END_REF]. These algorithms try to assign the workflow tasks to Grid resources so as to meet the user's deadline and minimize cost. The algorithms do not take into account network bandwidth.

Strategies to translate workflows into VXDL

We propose a process to specify distributed applications represented using workflows into VXDL descriptions [START_REF] Koslovski | Executing distributed applications on virtualized infrastructures specified with the VXDL language and managed by the HIPerNET framework[END_REF]. This application-mapping process comprises three main steps:

1. Workflow generation: the workflow is generated using information extracted from the application, such as benchmark results, data input description, data transfer in each module, and the number of nodes required to perform a satisfactory execution.

A workflow description represents the input/output data, the data-processing modules, and the relationship of the application's modules. This representation has been well-studied into the literature (as reviewed in Section 4.2).

2. Workflow translation into VXDL: taking into account the application requirements (such as RAM, CPU speed, and storage size), users can develop a VXDL description asking for the desirable configuration of the VI. At this point, users can also declare that some components must be allocated in a specific location as well as define the virtual network topology, stating the proximity of the components (latency configuration) and the required bandwidth. In addition, users can assign critical components for identifying the virtual resources that require reliability support (a mechanism for providing reliability support is described in Chapter 6).

3. VI provisioning: a management framework allocates the VI components respecting the configuration expressed by the user (such as parameterizations and timeline composition). In addition, the software configuration (operating system, programming tools, and communication libraries), extracted directly from the application and described using VXDL, are deployed within the virtual resources that compose the VI. This step is detailed in Chapter 5.

Workflow-based applications

Complex and large scale applications are generally described as workflows and interpreted by engines that convert the work description into execution scripts. An example of a workflow composition is given in Figure 4.2, where Floating and Reference represent data units to be processed, and CrestLines, CrestMatch, PFMatchICP, PFRegister, Yasmina and Baladin are processing modules. Modules are invoked as many times as needed to process all data units received. The user describing the application focuses on the data processing logic rather than on the execution schedule. The structural application workflow is transformed into an execution schedule dynamically while the workflow engine is being executed. Several languages have been proposed in the literature to describe workflows. On Gridbased infrastructures, Directed Acyclic Graph (DAG)-based languages, such as MA-DAG used in the DIET middleware [START_REF] Caron | DIET: A Scalable Toolbox to Build Network Enabled Servers on the Grid[END_REF], have often been employed. To ease definition of large-scale distributed applications with a complex logic, more abstract languages have been introduced. For instance, Scufl was proposed within the myGrid project [myG] to present data flows enacted through the Taverna workflow engine [START_REF] Oinn | Taverna/myGrid: Aligning a Workflow System with the Life Sciences Community[END_REF]. It has been one of the first languages to focus on the application data flow rather than on the generated task graph.

The language we chose for representing workflow, GWENDIA [GWE], is a data flow oriented language that aims at easing the description of complex application data flows from a user's perspective. GWENDIA is represented in XML using the tags and syntax defined below:

• Types: values flowing through the workflow are typed. Basic types are integer, double, string, and file;

• Processors: a processor is a data production module. A regular processor invokes a service through a known interface. Special processors include workflow input (a processor with no inbound connectivity, delivering a list of externally defined data values), sink (a processor with no outbound connectivity, receiving some workflow output) and constant (a processor delivering a single, constant value);

• Processor ports: processor input and output ports are named and declared. A port may be an input (<in> tag), an output (<out> tag) or both an input/output value (<inout> tag). The input ports also define iteration strategies that control the number of invocation of the processor as a function of its inputs. A simple example is presented in Figure 4.3.

• Data link: a data link is a simple connection between a processor output port and a processor input port as exemplified in Figure 4.4.

Workflow-based applications are represented using descriptive languages and submitted to workflow managers, which are in charge of submitting the tasks and optimizing the execution process. For example, the data-intensive Grid-interfaced workflow manager (MOTEUR) [MOT] enacts workflows represented with both Scufl and GWENDIA languages. MOTEUR interprets the workflow description and submits the workflow tasks to a distributed infrastructure, optimizing the execution via three levels of parallelism: workflow parallelism, data parallelism and pipelining [START_REF] Glatard | Flexible and efficient workflow deployement of data-intensive applications on grids with MOTEUR[END_REF].

Permanent and variable parts of workflows

Considering the workflow translation into VXDL, usually, applications are composed of two different sets of modules (or workflow entities): permanents and variables. This separation is performed according to the modules' lifetime, where it is considered permanent if it is present during the whole life of a workflow, and variable otherwise. For example, in <w o r k f l o w > < i n t e r f a c e > <c o n s t a n t name=" p a r a m e t e r " t y p e=" i n t e g e r "> <v a l u e >50</ v a l u e > </ c o n s t a n t > <s o u r c e name=" r e a l s " t y p e=" d o u b l e "/> <s i n k name=" r e s u l t s " t y p e=" f i l e "/> </ i n t e r f a c e > <p r o c e s s o r s > <p r o c e s s o r name=" d o c k i n g " t y p e=" w e b s e r v i c e "> <w s d l u r l=" h t t p : / / l o c a l h o s t / d o c k i n g . w s d l " o p e r a t i o n=" d o c k "/> <i n name=" param " t y p e=" i n t e g e r "/> <i n name=" i n p u t " t y p e=" f i l e "/> <o u t name=" r e s u l t " t y p e=" d o u b l e "/> < i t e r a t i o n s t r a t e g y > <c r o s s > <p o r t name=" param "/> <p o r t name=" i n p u t "/> </ c r o s s > </ i t e r a t i o n s t r a t e g y > </ p r o c e s s o r > <p r o c e s s o r name=" s t a t i s t i c a l t e s t " t y p e=" d i e t "> < s e r v i c e p a t h=" w e i g h t e d a v e r a g e "/> <i n name=" w e i g h t s " t y p e=" d o u b l e "/> <i n name=" v a l u e s " t y p e=" l i s t ( i n t e g e r ) "/> <i n name=" c o e f f i c i e n t " t y p e=" d o u b l e "/> <o u t name=" r e s u l t " t y p e=" f i l e "/> < i t e r a t i o n s t r a t e g y > <c r o s s > <p o r t name=" c o e f f i c i e n t "/> <match t a g=" p a t i e n t "> <p o r t name=" v a l u e s "/> <p o r t name=" w e i g h t s "/> </match> </ c r o s s > </ i t e r a t i o n s t r a t e g y > </ p r o c e s s o r > </ p r o c e s s o r s > </w o r k f l o w > Figure 4.3: Description of workflow tasks using the GWENDIA language. This figure presents a few processors (or data production unit) and their interaction using input/output ports.

< l i n k s > < l i n k from=" r e a l s " t o=" s t a t i s t i c a l t e s t : c o e f f i c i e n t "/> < l i n k from=" d o c k i n g : r e s u l t " t o=" s t a t i s t i c a l t e s t : w e i g h t s "/> < l i n k from=" s t a t i s t i c a l t e s t : r e s u l t " t o=" r e s u l t s "/> </ l i n k s > . . . <vNode i d=" d a t a b a s e "> <memory> < i n t e r v a l > <min>1</min> </ i n t e r v a l > <u n i t >GB</ u n i t > </memory> <s t o r a g e > <s i m p l e >100</ s i m p l e > <u n i t >GB</ u n i t > </ s t o r a g e > </vNode> . . . The permanent part also comprises the dedicated nodes hosting middleware, framework, and database required for running the application. Figure . 4.5 presents a partial VXDL description of permanent resources, where a simple database node is described to store the data presented in Figure 4.2.

The variable part of a VI description depends directly on the information extracted from the workflow, such as input data, the number of modules, and the links between the modules. In addition, the virtual network topology is directly related to the variable part composition. The more dependence exists between workflow modules, the more complicated is the network topology.

Translation strategies

This section details the proposed strategies implemented in the MOTEUR workflow manager for designing VIs to execute workflow-based applications and for producing the VXDL files [START_REF] Truong Huu | Joint elastic cloud and virtual network framework for application performance optimization and cost reduction[END_REF]. Table 4.1 summarizes all the parameters used for formulating the strategies.

Naive strategy

This strategy is naive in the sense that it only considers a single execution stage and the resources are statically allocated to each module, even though a module may not be used during the whole execution of the workflow.

Let p be the number of modules in a workflow, and t i the benchmarked execution time of each module i ∈ 1..p. A set of m max virtual computing nodes is allocated and split proportionally to each module execution time: m max t i / j∈s t j . The network bandwidth is similarly allocated proportionally to the amount of data to transferred between each pair of modules, or the same bandwidth is reserved for all links in the infrastructure. This strategy serves as a performance baseline for comparisons.

FIFO strategy

In this approach, we assume that the resources are indistinguishable, and the workflow scheduler can request any module to be executed on any available virtual resource. A FIFO scheduling strategy is optimal in the sense that VI redeployment is unnecessary (T = T 1 ). In addition, the same bandwidth is reserved for all links in the infrastructure (b 1 = b 2 = ... = b k ).

Figure 4.6 displays the estimated execution time and the total cost of the workflow from Figure 4.2 with regard to the bandwidth (for n = 32 input data items and unit costs c r = c b = 0.2). When the bandwidth is small, the total cost is high due to the increased data transfer time, but as the bandwidth increases, both the execution time and cost decrease. However, after a 2.0 Mbps threshold, the execution time slightly reduces and the bandwidth allocation cost increases. The optimization method used to approximate numerically the optimal bandwidth leads to 0.6517 Mbps.

Optimized strategy

The FIFO strategy can only be applied with homogeneous resources without optimizing the bandwidth between each resource pair. The optimized strategy described here considers dividing the workflow execution into multiple stages and allocating resources and bandwidth independently for each stage. A cost minimization algorithm is executed for identifying the optimal number of virtual resources to be allocated to the modules involved in the stage.

Moreover, the algorithm should decide on the number of stages and when a VI reconfiguration should happen. Initially, it transforms the workflow into a Directed Acyclic Graph (DAG) using the approach presented in [START_REF] Zhao | Scheduling Multiple DAGs onto Heterogeneous Systems[END_REF]. Secondly, the DAG is divided in execution stages, as shown in the example in Figure 4.7 for the workflow of Figure 4.2. IN and OUT are special entries and exit nodes that are not considered in estimating the execution and data transfer times. An execution stage is defined as the set of invocations that have the same depth in the DAG graph.

Note that the DAG generation is only possible for workflows without unbounded loops (i.e., the exact number of invocations of each module must be known in advance), so that the workflow planer can determine a complete execution schedule. Workflows including while loops, or foreach constructs iterating over data structures of unknown size are unresolvable prior to execution. Although DAG representation limits the class of applications that can be planed, it represents a broad category of workflow applications in e-Science [START_REF] Deelman | Mapping Abstract Complex Workflows onto Grid Environments[END_REF]. A solution for dealing with workflows with unresolvable constructs is to divide them into smaller resolvable sub-workflows. This strategy was implemented, for example, in the workflow manager of the DIET middleware (MA DAG) to deal with workflows that could not be represented by DAGs [MA].

At each execution stage identified, the infrastructure is reconfigured for only deploying the specific modules involved in that stage. The resources are allocated proportionally to the number of invocations needed for each module. In a typical data intensive application execution, there are more data items to process (n) than resources available (m max ). For instance, in the case of a stage i with only one module j (e.g., stage 1, 2 or 4 in Figure 4.7), m max data items are processed concurrently by j and the process is repeated n/m max times, leading to the execution time:

T i = n m max × T j (4.1)
where T i is the execution time for j.

c Copyright 2011 by Guilherme Piêgas Koslovski . . . < v i r t u a l T i m e l i n e i d=" A p p l i c a t i o n t i m e l i n e "> < t i m e l i n e i d="T1"> <a c t i v a t e >S e r v i c e i </ a c t i v a t e > <t o t a l T i m e >PTtiS </t o t a l T i m e > </ t i m e l i n e > < t i m e l i n e i d="T2"> < a f t e r >T1</ a f t e r > <a c t i v a t e >S e r v i c e j 1 </ a c t i v a t e > <a c t i v a t e >S e r v i c e j 2 </ a c t i v a t e > <a c t i v a t e >S e r v i c e j 3 </ a c t i v a t e > <t o t a l T i m e >PTtjS </t o t a l T i m e > </ t i m e l i n e > </ v i r t u a l T i m e l i n e > . . . The next step is to introduce the bandwidth requirements as well as the IT resource configurations. Let inv j , j = 1..s be the number of invocations of module j at stage i where s is the number of modules being executed at this stage. Let vector m = (m 1 , m 2 , ..., m s ) be a combination of numbers of resources allocated to the module j, satisfying the condition s j=1 m j ≤ m max . The resulting optimal execution time to complete inv j invocations of module j is:

T j = inv j m j × T uj (4.2)
where T uj is the unit execution time of module j.

The optimized strategy composes an internal virtual timeline of a VI. Figure 4.8 presents an application example with two stages described in VXDL. The first stage has a module that executes in t i seconds, and the second stage has three modules starting together after the first stage completes.

Modules grouping optimization

The total execution cost also depends on the time at which each stage is deployed. An optimization of the total resource reservation and redeployment time was designed, extending the job grouping strategy without loss of parallelism using a technique introduced in [START_REF] Glatard | Flexible and efficient workflow deployement of data-intensive applications on grids with MOTEUR[END_REF]. This strategy minimizes the application makespan by grouping modules that would have been executed sequentially, thus reducing data transfers and the number of job invocations needed. Applying this strategy to the workflow of Figure 4.2, two module groups are identified, which do not cause loss of parallelism as shown in Figure 4.9a. The number of execution stages can also be reduced as shown in Figure 4.9b.

Starting from the execution DAG split into stages, module invocation groups are evaluated for each consecutive pair of stages. For each module a of the workflow involved in the stage i, let a 0 , a 1 , ..., a j be all children from a in stage i + 1. All possible combinations of grouping a with one or more of the a k modules is tested and the resulting execution cost is evaluated by optimizing the number of resources and the bandwidth allocated.

Executing workflow-based applications

The experiments presented here assess the performance of a workflow-based application atop several VIs allocated over a distributed and virtualized physical substrate. The main goal is to show the impact and importance of well placing the permanent and variable parts of a workflow, in terms of resources proximity. A set of VIs were composed based on the information available on the workflows and benchmarks, which represents the users' knowledge about the application. The VIs were allocated and provisioned considering different approaches for placing the virtual resources.

Medical application example

We selected a complex, real-scale medical-image analysis application, known as Bronze Standard, to illustrate the translation of a workflow into a VXDL description. The Bronze Standard technique addresses the difficult problem of validating procedures for medicalimage analysis [START_REF] Glatard | Performance evaluation of gridenabled registration algorithms using bronze-standards[END_REF], where there is usually no reference, or gold standard, to assess objectively the quality of computational results. The statistical analysis of images enables the quantitative measurement of computational errors, thereby the bronze standard technique quantifies the maximal error resulting from widely used image registration algorithms. The larger the sample image database and the number of registration algorithms to compare with, the most accurate the method. This very-scalable procedure requires the composition of a complex application workflow including different registrationcomputation modules with data transfer inter dependencies. The estimated performance of Bronze Standard depends on the size of the image database. In the experiments we use a clinical database of 32 pairs of patient images to be registered by the different algorithms in the workflow. For each run, the processing of the complete image database results in the generation of approximately 200 computing tasks. As illustrated in Figure 4.2, the workflow of this application has a completely deterministic pattern, all modules of the application have the same number of invocations. The execution time and the data volume transferred by each module have been measured in initial micro-benchmarks reported in Table 4.2. Bronze Standard's workflow is enacted with the MOTEUR workflow manager [START_REF] Glatard | Flexible and efficient workflow deployement of data-intensive applications on grids with MOTEUR[END_REF]. MOTEUR submits the workflow tasks to the VI infrastructure through the DIET middleware [START_REF] Caron | DIET: A Scalable Toolbox to Build Network Enabled Servers on the Grid[END_REF], a scalable Grid scheduler based on a hierarchy of agents communicating through CORBA [COR].

Modules

. . . <vNode i d=" Moteur "> <memory> < i n t e r v a l > <min>4</min> </ i n t e r v a l > <u n i t >GB</ u n i t > </memory> </vNode> <vGroup i d=" C l u s t e r B a l a d i n " m u l t i p l i c i t y =" 22 "> <vNode i d=" N o d e C l u s t e r B a l a d i n "> <memory> < i n t e r v a l > <min>512</min> </ i n t e r v a l > <u n i t >MB </ u n i t > </memory> </vNode> </vGroup> . . . To exemplify the translation of Bronze Standard's workflow into a VXDL file, let us consider a request for a VI of 35 nodes. Three nodes will be dedicated to the permanent part: 1 node for MOTEUR, 1 node for the middleware server and 1 node for the database server. The 32 nodes left are distributed and allocated proportionally to the execution time of the workflow modules using, for simplicity, the Naive strategy (discussed in Section 4.3.3.1); 3 nodes are used for CrestLines, 1 node for CrestMatch, 1 node for PFMatchIP, 1 node for PFRegister, 22 nodes for Baladin, and 4 nodes for Yasmina. Figure 4.11 presents the specification of a virtual node (MOTEUR) and a computing cluster (Baladin). Several variants of VI descriptions with different network topologies can be expressed for the same computing-resources set. We give examples developing two different VI compositions.

VI composition

Figure 4.12 illustrates the graph of a VI composition to execute the Bronze Standard's workflow, where the vertices represent the virtual resources and virtual clusters required to execute the application, and the edges are the network links required to enable the communication between the workflow's modules. The permanent part is differentiated from other components (i.e., MOTEUR, middleware and database nodes) including those that are critical in terms of computing and data transfer (i.e., CrestMatch, Yasmina, Baladin and PFMatchICP).

Based on this composition, we developed two descriptions for this scenario varying the network topology and requirements:

• VI 1. The network is composed of two types of links: one with low intra-cluster latency, and another with a maximum latency of 10 ms for interconnecting the clusters;

• VI 2. The network comprises three virtual links: i) one with low intra-cluster latency (maximum latency of 0.200 ms); ii) one with latency of 10 ms interconnecting the components, except the links with iii) a maximum latency of 0.200 ms between CrestMatch (dark blue) and clusters PFMatchICP, Yasmina and Baladin To illustrate how each description can be allocated on a physical substrate, we propose two solutions for each VI, which corresponds to a total of four different allocations. For the sake of illustration, these allocations were arbitrarily performed, not based on any particular algorithm (a detailed discussion is available in Chapter 5). In this example, Location 1 and Location 2 represent two geographically distributed resource sets. We use the notations r v and r p to represent virtual and physical resources, respectively.

Figure 4.14 summarizes the allocation described below:

• VI 1 -Allocation I: the intra-cluster link specification motivates the allocation of loosely connected resources with one virtual machine per physical node.

• VI 1 -Allocation II: the virtual resources of clusters CrestMatch, PFRegister, Yasmina, and Baladin share physical nodes. Each physical node allocates 2 virtual machines.

• VI 2 -Allocation III: due to the required interconnection capacity (maximum latency) all virtual resources must be allocated at the same location (for example, in the same site of a Grid, or a specific geographical location that respects the maximum latency defined). This allocation explores the allocation of 1 virtual machine per physical node.

• VI 2 -Allocation IV explores the same physical components of Allocation III but with 2 virtual machines per physical node for the clusters CrestMatch, PFRegister, Yasmina, and Baladin.

. . . <v L i n k i d=" Communication I n t e n s i v e 1 "> <l a t e n c y > < i n t e r v a l > <max>0.200 </max> </ i n t e r v a l > <u n i t >ms</ u n i t > </ l a t e n c y > <s o u r c e >C l u s t e r C r e s t M a t c h </ s o u r c e > < d e s t i n a t i o n >C l u s t e r B a l a d i n </ d e s t i n a t i o n > </v L i n k> <v L i n k i d=" Communication I n t e n s i v e 2 "> <l a t e n c y > < i n t e r v a l > <max>0.200 </max> </ i n t e r v a l > <u n i t >ms</ u n i t > </ l a t e n c y > <s o u r c e >C l u s t e r Y a s m i n a </ s o u r c e > < d e s t i n a t i o n >Cluster PFMatchICP </ d e s t i n a t i o n > </v L i n k> <v L i n k i d=" Communication I n t e n s i v e 3 "> <l a t e n c y > < i n t e r v a l > <max>0.200 </max> </ i n t e r v a l > <u n i t >ms</ u n i t > </ l a t e n c y > <s o u r c e >C l u s t e r C r e s t M a t c h </ s o u r c e > < d e s t i n a t i o n >Cluster PFMatchICP </ d e s t i n a t i o n > </v L i n k> <v L i n k i d=" Communication I n t e n s i v e 4 "> <l a t e n c y > < i n t e r v a l > <max>0.200 </max> </ i n t e r v a l > <u n i t >ms</ u n i t > </ l a t e n c y > <s o u r c e >d a t a b a s e </ s o u r c e > < d e s t i n a t i o n >C l u s t e r P F M a t c h </ d e s t i n a t i o n > </v L i n k> . . .

Application execution

The experimental testbed for executing the Bronze Standard application used physical resources from the Grid'5000 testbed [START_REF] Cappello | Grid'5000: a large scale and highly reconfigurable grid experimental testbed[END_REF]. Grid'5000 is an experimental testbed distributed across 9 sites in France, for research in large-scale parallel and distributed systems [GRI]. The sites are interconnected by a backbone infrastructure comprising 10 Gbps dedicated lambda paths provided by the French National Telecommunication Network for Technology (RENATER) [REN] as depicted in Figure 4.15. The reserved physical infrastructure was composed of the clusters capricorne (located in Lyon), bordemer (located in Bordeaux ), and azur (located in Sophia), whose nodes contain CPUs of 2.0 GHz dual-core Opterons.

The resources were virtualized by the HIPerNet framework [START_REF] Anhalt | Specifying and provisioning Virtual Infrastructures with HIPerNET[END_REF], responsible for the provisioning and management of all virtual infrastructures composed to execute the application. The VIs used a system image containing the operating system based on a standard Linux distribution Debian Etch with a kernel version 2.6.18-8 for AMD64. Each VI is composed of 35 nodes divided in permanent and variable parts: 3 nodes are dedicated to the permanent part (MOTEUR, DIET, and storage server) using 1 CPU per node, and the remaining 32 nodes to the variable part. The allocation of variable resources was performed in accordance with the following VI descriptions: VI 1 -Allocation I and VI 2 -Allocation III used 1 CPU per node while VI 1 -Allocation II and VI 2 -Allocation IV used 1 CPU core per node. For each each experiment, we executed the application 10 times and obtained the averages and standard deviations of the application makespan, The application's makespans on VI 2 -Allocation III and VI 2 -Allocation IV are 11min 44s (±49s) and 12min 3s (±50s), respectively. This corresponds to a +3.8% makespan increase due to the execution overhead when two virtual machines are collocated on the same physical resource. In addition, we present in the Table 4.3 the average execution time (in seconds) of the application modules on VI 2 -Allocations III and IV. The average execution overhead is 5.17% (10.53% in the worst case and 1.28% in the best case).

Resources distributed across 2 locations

In this experiment the VI's components were provisioned across 2 locations. We compare the application execution of a VI locally provisioned (VI 2 -Allocation IV ) with that of a VI whose resources are distributed (VI 1 -Allocation II ). The resources' locations follow the map solution proposed by VI 1 -Allocation II and VI 2 -Allocation IV.

When porting the VIs from a local provisioning to a large scale distributed provisioning, data transfers increase. transfers may be slightly reduced. However, in this case this overhead has little impact on the application makespan since it is compensated for by the parallel data transfer and computations introduced by MOTEUR [START_REF] Glatard | Flexible and efficient workflow deployement of data-intensive applications on grids with MOTEUR[END_REF]. Indeed, the makespans of VIs distributed across 2 locations are 12min (±12s) and 12min 11s (±20s) on VI 1 -Allocation I and VI 1 -Allocation II, respectively, very similar to the performance of the local VI 2 -Allocation IV.

Modules

Resources distributed across 3 locations

In the final experiment of this section, the VIs were provisioned over 3 locations. The permanent part of allocation solution VI 1 -Allocation II was placed in a single location (Lyon, in this case) whereas the variable part was randomly distributed among Lyon, Bordeaux, and Sophia locations.

As expected, further distributing computational resources causes an additional increase in the data-transfer overheads among the application's modules, with an execution makespan of 12min 13s (± 30s) and a data-transfer overhead of 176% in the worst case.

Analysis of strategies for composing VIs

The second set of experiments, also using Bronze Standard, investigates the different strategies for composing VIs. Different VIs were elaborated following the proposed strategies and the information extracted from Bronze Standard. In the following subsections we describe the testbed and the main obtained results.

Testbed composition

The testbed also uses physical resources from Grid'5000, but this time only resources located in Lyon site were reserved. The physical resources are Sun Fire V20z machines with 2.4 GHz CPUs, 2 cores, 2 GB RAM, interconnected through 1 Gbps Ethernet. Once again, the VIs were allocated and managed by the HIPerNet framework.

The experimental infrastructure is depicted in Figure 4.16. For the experiments, 35 vNodes were deployed, but this time, the MOTEUR workflow engine acted as a client of the HIPerNet framework, being hosted on a dedicated physical host, outside the VI. The HIPerNet engine deploys and manages virtual machines on-demand on the computers (dark connections), either with an operating-system image of the input database server or with the application modules. Each physical computer hosts a single virtual machine. MOTEUR produces VXDL descriptions that are submitted to the HIPerNet engine (blue connection). After receiving the information about all components allocated to the VI, MOTEUR connects to the computing nodes to invoke the application modules (red connections). The computing nodes connect to the database host to copy the input data and send the computational results. The final results are sent to MOTEUR (green connections).

For the needs of the MOTEUR planner which implements the strategies described in this Chapter, all modules involved in the Bronze Standard's workflow have been benchmarked for execution time and amount of data transferred, as reported in Table 4.2. For each experiment, the application was executed 5 times and the makespan was averaged to minimize the execution time variations encountered in distributed computing. The standard deviation is also reported.

For each strategy, the planner optimizer of MOTEUR was executed to determine the configuration with the minimal execution cost. The number of virtual machines allocated to the application and the bandwidth among the database node and computing nodes is specified by corresponding VXDL documents.

Cost model

The execution of a workflow-based application can occur in several stages. At each stage, the VI can be reallocated respecting a specific configuration, to perform the execution of part of the workflow. The VI reconfiguration between different stages, which may involve redeploying resources, is time-consuming. An extreme condition is to create a static VI for the whole workflow execution, thus sparing the redeployment cost. Another extreme is to allocate new resources, one by one, on demand.

The cost model presented in this section makes a fine-grained estimate of the resources consumed by each application run [2] [Truong Huu and Montagnat, 2010]. Note that the model is applicable to estimate the cost of a single run of an application on the infrastructure. It does not take into account other costs, such as the long term storage of data onto Cloud resources. Should users need data storage before and/or after execution, they would be charged additionally and independently of the cost calculated below.

The cost was formulated following the notation presented in Table 4.1. Let m max be the maximum number of computing nodes available on the infrastructure and s be the number of execution stages of the application. The vector m = (m 1 , m 2 , ..., m s ) is the number of nodes used at each execution stage with ∀i, m i ≤ m max . Let c r be the per-second cost of a computing resource. The total computing cost of the infrastructure allocated for the application is:

C r = c r × s i=1 m i × (T d i + T i (m i , n, b)) (4.3)
where T d i is the deployment time (including resource reservation and initialization time) and T i (m i , n, b) is the execution time at stage i. T i depends both on computing time and on data transfer time involved within stage i. It is parameterized by the number of resources reserved (m i ), the number of input data items to process (n) and the bandwidth

(b = (b 1 , b 2 , ..., b ki ), i ∈ [1.
.s]) of the network links used for data transfer. The computation of T i is possible using the application logic described through the workflow. The workflow engine used in our experiment, MOTEUR [START_REF] Glatard | Flexible and efficient workflow deployement of data-intensive applications on grids with MOTEUR[END_REF], was seminally designed to produce an execution schedule and control the distribution of an application at runtime. It was enriched with a resource allocation and scheduling planner used to estimate T i , given that information on the workflow modules execution time and transferred data is available.

The total infrastructure cost is also impacted by the data transfer time. If the per-Mbps cost of the reserved bandwidth is c b , then the total data transfer cost is:

C b = c b × s i=1 (T d i + T i (m i , n, b)) k i j=1 b j (4.4)
This cost applies to a VI where the amount of allocated bandwidth is controlled. It sums all data transfer costs involved in the workflow execution, including workflow input data transferred from outside the Cloud (at stage 1), the temporary data generated during workflow execution (at all stages) and the output data transferred to external resources (at stage s). From equations 4.3 and 4.4, the total infrastructure cost to execute the applications can be computed as:

C = C r + C b (4.5)
This cost has to be optimized considering a maximum admissible cost and the application performance scalability. A trade-off has to be found between the number of computing and network resources allocated (which impacts T i ) and the resulting cost.

Comparing strategies

The Bronze Standard application was executed over VIs composed with the different discussed strategies. We compare the single-stage strategy and multi-stage strategies to identify the application behavior when executing in an elastic VI.

Single-stage strategies

The naive and FIFO strategies are single-stage. They use the maximum available computing resources with an optimal bandwidth yielding a minimal execution cost. The virtual infrastructures of the naive and FIFO strategies are represented in Figure 4.17 and 4.18, respectively. The naive allocation strategy allocated the 34 computing nodes to application modules as follows: 3 nodes for CrestLines, 1 node for CrestMatch, 1 node for PFMatchICP, 1 node for PFRegister, 5 nodes for Yasmina, and 23 nodes for Baladin. The same bandwidth, 2.69Mbps, is required to interconnect all computing nodes. The application makespan is 67.08min ± 0.10min.

This experiment shows that the virtual resources are not well exploited during the execution. Figure 4.19 shows a schedule of this strategy. Each colored line represents one task duration: it starts once the corresponding task has been submitted and stops at the end of its execution. The first, brighter part of a line represents the task's waiting time spent from submission until a resource becomes available for execution. Colors are arbitrary and just help distinguish the different tasks. As can be seen, at the beginning of the execution, only three nodes are used to execute the CrestLines module. Other resources are wasted. Similarly, the result of CrestMatch is needed by three modules: PFMatchICP, Yasmina and Baladin, but there is only one resource allocated to this module according to this strategy, thereby becoming a bottleneck.

The makespan of the FIFO strategy is lower: 46.88min ± 0.78min with the optimal bandwidth (1.16Mbps). The standard deviation of this strategy is higher due to the variable arriving order of the tasks. Some long tasks are executed on the same computing resource, leading to an increase in the application makespan. Figure 4.20 shows a typical task schedule for this strategy.

Multi-stage strategies

The optimized strategies are multi-staged, optimized bandwidth required, and may allocate less resources than the maximum available when doing so leads to no gain. The planer determines the number of virtual resources and the bandwidth yielding a minimal execution cost.

Within the multi-stage optimization, virtual resources from stage n can be reused in stage n + 1. If stage n + 1 uses more virtual machines than stage n, additional virtual machines are deployed during the execution of stage n.

Without module grouping there are 4 execution stages, which are represented in Figure 4.21. According to the optimization results, only 30 nodes were allocated to the first, second and fourth stages (additional resources would be wasted). The required bandwidths are 4.62 Mbps, 14.74 Mbps and 3.87 Mbps, respectively. For the third stage, 4 nodes were allocated to PFMatchICP, 6 nodes for Yasmina and 20 nodes for Baladin. The bandwidth for each module in this stage is 0.87 Mbps, 1.36 Mbps and 1.29 Mbps, respectively. The corresponding application makespan is 37.05min ± 0.25min.

Further grouping the application modules as shown in Figure 4.10, the application is divided into three stages only, using 30 nodes each. As presented in Figure 4.22, the bandwidth allocated to each stage is 4.90 Mbps, 1.95 Mbps and 3.87 Mbps, respectively. The application makespan is then 22.93min ± 0.35min. Besides the execution time improvement, the number of resources consumed is lowered. As we can observe in Figure 4.23, not all tasks of the same stage finish exactly at the same time though, due to variations in execution time of the image analysis tools, which depends on the exact processed image content. This has an impact as the tasks of stage n have to wait for the longest task of stage n -1 before the system can be reconfigured.

Analysis

For complementing the analysis, we also measured the deployment time of the virtual infrastructure before running the application and the reconfiguration time between stages of the optimized strategies. The reconfiguration time takes into account bandwidth reconfiguration between the database host and computing nodes allocated to application modules in each stage.

Table 4.5 compares the performance of the strategies presented above and the associated platform cost computed using Equation 4.5. The worst case is the naive strategy which uses the maximum number of resources for a very large makespan and a long deployment. The FIFO strategy spends the same time to deploy the infrastructure, but it has a better makespan than the naive strategy. The naive and FIFO strategies reconfiguration time is null since they are single-stage. The optimized strategy without module grouping has better results than the naive and FIFO strategies, both in terms of application makespan and number of resources consumed, although it has to spend time to reconfigure the infrastructure after each stage. The best case is obtained for the optimized strategy with module grouping. It uses less resources, spends less time to reconfigure the infrastructure and returns the results faster. In terms of deployment time, the naive and FIFO strategies take 29.83 min to deploy a VI composed of 35 virtual resources. This duration corresponds to the time needed to copy the operating-system images (319 MB) from the image repository to the virtual machines and start them sequentially. The optimized strategies use only 31 machines, reducing the deployment time to 25.68 min. It is expected that a parallel deployment decreases this redeployment overhead. As expected, the cost estimated is lowered for higher performing strategies toward the reduction of the application makespan and of the network bandwidth consumed.

Impact of bandwidth control on application cost and performance

Finally, we complemented the set of experiments by evaluating the application behavior when executing following the bandwidth reservation and control mechanisms offered by the HIPerNet framework. For that, the application was executed using the optimized strategy with module grouping under two additional network bandwidth configurations: lower and higher bandwidth values than the optimal found were tested (i.e., 1 Mbps and 10 Mbps respectively). Table 4.6 displays, for each configuration, the data transfer time in each stage (in seconds), the application makespan (in minutes), and the corresponding cost. Comparing the results with the optimized bandwidth allocation, it appears that the makespan increases as expected when using a low bandwidth. However, the cost increases as well because the cost gain on network bandwidth is compensated by the loss in the computing nodes' reservation time. With the high bandwidth, the application makespan can be reduced (-22.72% in this case) at a higher cost (+102% computed with c r = c b = 0.10).

Bandwidth

Conclusions

This chapter addressed the difficult problem of composing an optimal VI to execute a distributed application. Applications have different requirements in terms of computing and communication that can vary during the execution time. In a pay-as-you-go scenario, such as Cloud Computing, an optimal VI must consider the trade-off between allocation cost and application performance. We proposed and evaluated strategies to determine optimal VIs specification for executing workflow-based distributed applications on VIs, provisioned following the pay-as-you-go model. We identified that applications can explore the dynamism provided by the elasticity of VIs. By decomposing a VI in well-defined stages, application performance can be improved while costs can be reduced, as shown by results that assess the performance of the optimized strategy with a job grouping optimization. In addition, the advanced network bandwidth reservation and control capabilities offered by management frameworks (such as HIPerNet) can be exploited to improve the applications' performance.

VXDL has acted as a key facilitator for describing VIs, since the attributes offered by this language enabled the specification of the required VI configuration in terms of computation, communication, and usage intervals. However, to guarantee the user's expectations, an efficient mechanism is highly required for translating and allocating a set of VIs onto a distributed physical substrate. The allocation mechanism should interprets and exploits all attributes of VXDL, and in addition, considers the user's expectations during the formulation of the allocation problem.

An open research line that we will investigate is the elaboration of translation mechanism for legacy applications, represented and characterized with other information (e.g., MapReduce [START_REF] Dean | Mapreduce: simplified data processing on large clusters[END_REF], web servers).

-FIVE -

Introduction

A s illustrated in Figure 5.1, once the needs of an application are identified and a VI for it is specified, the resulting VXDL file carrying the specification and substantial information on the user's requirements must be interpreted, allocated and provisioned over the distributed substrate. As a key step in the dynamic provisioning process, the allocation of a VI atop a physical substrate must reconcile the users' expectations with the Infrastructure Providers (InP) objectives. While users can compose VXDL descriptions, considering their requirements in terms of application performance and reservation cost, InPs, on the other hand, usually aim to minimize resource usage and substrate cost, or to maximize the acceptance ratio of new requests. Due to combinatorial explosion, the computational time to find a feasible solution depends exponentially on the size of the search space considered by the allocation algorithm. The optimal allocation of a virtual infrastructure with constraints on physical nodes and links is an NP-hard problem (it cannot be solved in polynomial time) [Chowdhury and Boutaba, 2009].

Moreover, the complete abstraction of physical network and IT resources, combined with the geographical independence of VIs, brings together new challenges to the allocation process, since a VI can be allocated anywhere on top of a distributed substrate. The allocation of geographically fragmented virtual infrastructures raises the following concerns for users and InPs: i) the network-communication latency between distributed virtual resources increases, which can augment the application's runtime [START_REF] Koslovski | Executing distributed applications on virtualized infrastructures specified with the VXDL language and managed by the HIPerNET framework[END_REF]; and ii) the physical substrate's fragmentation decreases the potential for accepting new requests due to increased congestion on communication channels and IT resources [START_REF] Zhu | Algorithms for Assigning Substrate Network Resources to Virtual Network Components[END_REF]. The more geographically distributed are the physical resources that host a VI, the more bandwidth capacity is required (reserved) to interconnect the virtual IT resources. In the long term, the physical substrate's fragmentation can increase costs such as energy consumption, cooling and administration, due to the simultaneous activation of several distributed physical racks and network equipments.

In the face of these challenges, the main contributions of this chapter are:

• an allocation-problem formulation that considers the user and InP metrics; and

• an allocation heuristic guided by the geographical location of virtual and physical components, which introduces a procedure to reduce the search space in an automatic and intelligent way, accelerating the allocation algorithm without compromising the cost.

The results highlight an improvement in allocation quality (the user perspective) of about 39% for different sizes of virtual infrastructures allocated on a medium-size physical substrate. In addition, the fragmentation can decrease by almost 28% on a medium-size physical substrate, while the cost can decrease by approximately 21% (the InP perspective).

This chapter is organized as follows: Section 5.2 illustrates the allocation of a virtual infrastructure and reviews the state of the art. Section 5.3 formulates the allocation problem using a graph notation, and describes the formal representation of constraints and objective functions. In Section 5.4 we propose the allocation method, describing its composition and implementation. The experiments performed with our proposition are presented in Section 5.5. Section 5.6 concludes the chapter.

State of the art

In the lifecycle of virtual infrastructures, the allocation step is responsible for identifying the mapping between virtual and physical resources. Within this step, a VI request must be interpreted and available distributed resources must be reserved. This mapping is used by the management framework to identify the exact location where the virtual resources must be provisioned. The following sections describe this mapping process and review the approaches that have been elaborated for allocating IT resources, virtual networks, and VIs.

Example scenario

VIs and physical substrates can be modeled using a graph notation, where the vertices represent the IT resources (virtual and physical), and the edges represent the communication channels (virtual links and physical paths). Consequently, a simple way to exemplify the allocation process is through a mapping of graph components: the virtual edges and vertices are mapped into physical edges and vertices, respectively, respecting the constraints and capacities of each component (virtual or physical).

To illustrate the allocation of VIs, we create two specifications (presented in Figure 5.2) and allocate them on a distributed physical substrate (as presented in Figure 5.3). Both VIs presented in Figure 5.2 are described using graphs. The VIs (VI A and VI B ) and the physical substrate have Q values attributed to links and resources. For VIs, these values represent the requirements in terms of network communication and computing configuration, and for a physical substrate, they represent the available capacity. VI A is composed of four virtual resources (r v 1, r v 2, r v 3, and r v 4), which are interconnected by three virtual links (l v 1, l v 2, and l v 3). VI B comprises three virtual resources (r v 5, r v 6, and r v 7) interconnected by two virtual links (l v 4, and l v 5). The mapping solution (present on the right side of Figure 5.3) is an allocation alternative for the VI A and VI B over the physical substrate. In this example, the IT and network resources of both VIs are distributed over the two locations. The Q values presented in this mapping solution show the available capacity of physical resources after the allocation process. Table 5.1 summarizes this allocation mapping using tuples in the format < virtual resource, physical resource, capacity, ∆t >, where ∆t means the time period during which the capacity was reserved. To simplify the description, we consider a unique time t0 in this example. Following the VI's life cycle, this mapping information is given as input to management frameworks that provision the virtual resources.

Existing solutions for allocating VIs

The allocation of virtual resources (IT and network) has been investigated over the past few years in different contexts. Initially, this problem was addressed to allocate communication channels between IT endpoints in different networking technologies, such as IP, MPLS, ATM and frame-relay, composing VPNs. In VPNs, the allocation process consists in finding paths between source-destination pairs respecting the bandwidth requirements [START_REF] Duffield | A flexible model for resource management in virtual private networks[END_REF]] [Gupta et al., 2001] [Lu and Turner, 2006]. The allocation of virtual computing resources was not addressed by these approaches. In addition, the location of source and destination endpoints were known in advance by the allocation algorithms.

[Dias de Assunção and Buyya, 2009] proposed a system termed as the InterGrid for allocating virtual machines at multiple computing sites. The concept was further extended

(r v or l v ) (r p or l p ) Q ∆t r v 1 r p 2 5 t0 r v 2 r p 3 2 t0 r v 3 r p 4 5 t0 r v 4 r p 9 5 t0 l v 1 l p 2 3 t0 l v 2 l p 3 2 t0 l v 3 l p 4 3 t0 l v 3 l p 15 3 t0 r v 5 r p 6 4 t0 r v 6 r p 5 4 t0 r v 7 r p 7 4 t0 l v 4 l p 5 5 t0 l v 5 l p 15 5 t0 l v 5 l p 8 5 t0
Table 5.1: Map of the allocation solution presented in Figure 6.4 using tuples in the format < virtual resource, physical resource, capacity, ∆t >.

to allow an organization to extend the capacity of its local cluster by borrowing resources from a Public Cloud provider. This work targeted only bag-of-tasks applications and the allocation of virtual links was not taken into consideration.

Recent work has focused on problem formulations considering node requirements together with network configuration. Due to its NP-hard complexity [Chowdhury and Boutaba, 2009], there are different proposals on solving this graph-embedding problem, most of which aim to find an optimal solution in an acceptable response time. These proposals include isomorphism-based detection, path-splitting methods, multi-commodity flow modeling, and heuristics based on substrate characteristics. In addition to exploring different approaches, these proposals have their own objectives and metrics, for example, maximizing resource usage, minimizing maximum link load, proposing fault-tolerant algorithms, and allocating virtual resources across multiple domains. We detail here selected proposals, their context, main contributions and particularities.

[ [START_REF] Ricci | A Solver for the Network Testbed Mapping Problem[END_REF] proposed a search-space restriction to accelerate the response time of the allocation process. The proposed program, called assign, explores the resource homogeneity of the Emulab testbed [START_REF] White | An Integrated Experimental Environment for Distributed Systems and Networks[END_REF] by aggregating resources into equivalence classes (vclasses and pclasses). A group of aggregated resources is interconnected by network links with capacities described in terms of bandwidth. Particularly, this program does not allow computing resources to be shared among multiple virtual machines. Assign implements an algorithm based on simulated annealing [START_REF] Kirkpatrick | Optimization by Simulated Annealing[END_REF] for finding a mapping solution.

[ [START_REF] Lu | Efficient Mapping of Virtual Networks onto a Shared Substrate[END_REF]] investigated the mapping of virtual networks on shared substrates. The proposed algorithm attempts to find the best topology in a family of backbonestar topologies. More specifically, a set of intermediate nodes is assigned as the backbone, and each remaining node is connected to the nearest backbone node aiming to minimize the network total cost. By positioning intermediate backbone nodes the search space is limited. Only a subset of nodes directly connected by the backbone-star topology are considered to determine the shortest path in terms of resource distance. [START_REF] Zhu | Algorithms for Assigning Substrate Network Resources to Virtual Network Components[END_REF] proposed a set of heuristics to allocate virtual networks on a physical substrate. This work aimed to increase the allocation efficiency by minimizing the stress on nodes and links, where the stress of a resource represents the load already supported and reserved. Based on this metric, new resources are provisioned on top of physical resources with a relatively low stress. The authors also proposed an algorithm to reconfigure the substrate by reallocating a subset of virtual resources, keeping the entire substrate with a low load. In addition, the reallocation can be guided by reconfiguration policies [START_REF] Fan | Dynamic Topology Configuration in Service Overlay Networks: A Study of Reconfiguration Policies[END_REF]. [START_REF] Houidi | A Distributed Virtual Network Mapping Algorithm[END_REF] proposed a distributed algorithm for load balancing and to allocate virtual nodes and links to physical substrates. They have designed a protocol for asynchronous communication between agents located on distributed resources to guide the allocation process. The algorithm performs a star based decomposition of the virtual network, using a hub-and-spoke approach, which maps a central node as hub and connects the other nodes as spokes (similar to the backbone-star approach, proposed in [START_REF] Lu | Efficient Mapping of Virtual Networks onto a Shared Substrate[END_REF]). The implementation was based on a multi-agent system [START_REF] Kephart | The Vision of Autonomic Computing[END_REF], where a set of autonomous and independent agents communicate and collaborate to identify a map solution. A recent approach extended this algorithm by proposing a distributed fault-tolerant allocation algorithm to handle failures and reselect new resources to replace those no longer available [START_REF] Houidi | Adaptive Virtual Network Provisioning[END_REF]] [Houidi et al., 2011]. This framework (mainly composed of resource description [START_REF] Renault | A framework to describe and search for virtual resource objects[END_REF], discovery and allocation mechanisms) monitors the physical substrate to detect when a resource fails, acting to select and allocate a new resource to replace the one that failed. [START_REF] Cadere | Virtualization and allocation of network service resources using graph embedding[END_REF] modeled an embedding graph problem considering three parameters to evaluate the quality of an allocation map: the dilatation that is the maximum length of a path and represents the communication delay; the congestion that is the maximum number of virtual links using a physical path and represents the bandwidth control; and the load that is the number of virtual resources allocated on a physical resource. The proposed multi-objective allocation heuristic aims at minimizing these metrics and consequently the number of resources used to accommodate a virtual infrastructure. The evaluation results indicate that the heuristic may have a long computation time under certain distributed physical substrates. [START_REF] Yu | Rethinking virtual network embedding: substrate support for path splitting and migration[END_REF] discussed the design of the substrate network considering virtual path migration and splitting, wherein a virtual link can be split among a set of virtual paths enabling a more efficient usage of the substrate network. In addition, a path migration is periodically performed to optimize the substrate network utilization. The problem is modeled as a multi-commodity flow problem without node remapping. According to their evaluation, the splitting of virtual links helps maximize revenue and minimize substrate resource usage. [START_REF] Lischka | A virtual network mapping algorithm based on subgraph isomorphism detection[END_REF] proposed a backtracking algorithm to identify a subgraph isomorphism between the virtual and the physical graph. The proposed algorithm is an extension of the vflib graph matching algorithm [START_REF] Cordella | A (sub)graph isomorphism algorithm for matching large graphs[END_REF] and is solvable in polynomial time. By limiting the length of a physical path in which a virtual link can be extended, the authors reduced the search space and consequently limited the response time. Within this approach, nodes and links are considered together during the allocation process.

[ Chowdhury et al., 2009] developed two algorithms (one deterministic and one randomized) to allocate virtual infrastructures with coordinated node and link mapping. With link and node constraints, the problem is formulated as a Mixed Integer Program (MIP) [Schrijver, 1998], and the integer constraints were relaxed to obtain a linear programing. In [Chowdhury et al., 2010] the allocated problem was formulated considering the allocation of VIs across multiple administrative domains that compose the physical substrate. They proposed a decentralized framework based on a hierarchical addressing scheme and on a location awareness protocol. Each local domain (or intra-domain) receives a partition of a VI request to allocate on their private resources by executing the centralized heuristic described in [Chowdhury et al., 2009]. The protocol carries information to request the VI, to negotiate the allocation, and to inform its status (success and failure). Recently, [START_REF] Yeow | Designing and Embedding Reliable Virtual Infrastructures[END_REF] extended this formulation and investigated the virtual-infrastructure allocation considering mechanisms to pool backup nodes in order to achieve the desired level of reliability together with resource allocation.

The work developed in [START_REF] Butt | Topology-Awareness and Reoptimization Mechanism for Virtual Network Embedding[END_REF] investigates a topology-aware mechanism to re-optimize and allocate initially rejected requests. This approach identifies the bottleneck of rejected requests and re-optimizes the physical substrate to accommodate their requirements. The metric used to control the physical substrate load and to determine which resources must be re-optimized are based on a scaling factor that identifies the probability of a resource becoming a bottleneck.

We summarize these approaches in Table 5.2 identifying the following characteristics:

• Centralized or distributed implementation: the majority of the proposed algorithms have been implemented with a centralized approach. The decentralization of the algorithm is justified by an improvement in scalability, robustness, and local management of partial failures.

• Reconfigurability: refers to the algorithm's skill in reconfiguring the virtual infrastructures already allocated in order to balance the load of the physical substrate.

The existence of this option may be related to the context in which the approach is inserted. Usually, this reconfiguration task can be performed by management frameworks outside of the allocation mechanism.

• Type of incoming requests: the online problem formulation refers to the scenario where the virtual infrastructure requests are not known in advance, arriving dynamically with a non-arbitrary duration (reservation time). Over the past years, this model of incoming requests has been adopted mainly to represent a real scenario, where the services (VIs) could be requested at any time.

• Problem formulation and heuristic: different solutions can be applied for solving the allocation problem. In general, software implementations have used substrate based heuristic, shortest path [Dijkstra, 1959], and subgraph-isomorphism [West, 2000] detection techniques, while simulations have explored Mixed Integer Problem formulations [Schrijver, 1998].

Proposal

Implementation Reconfigurability Requests Problem formulation / heuristic [START_REF] Ricci | A Solver for the Network Testbed Mapping Problem[END_REF] 5.2: A list of selected proposals developed to allocate virtual resources and their particularities: implementation scenario, reconfigurability, type of requests, and problem formulation.

Requirements for efficient VI allocation

As highlighted in the previous section, the allocation of virtual infrastructures has been well studied, forming an extensive background of good practices and future action points. For example, often virtual resources are not mapped adjacently, but distributed over physical resources. Consequently, the vLinks required to interconnect these resources must be extended over multiple physical communication paths, with a vLink being split over the physical substrate to provide communication between virtual source and target. The splitting of a vLink means its decomposition in many virtual links allocated over different physical components [START_REF] Yu | Rethinking virtual network embedding: substrate support for path splitting and migration[END_REF], while the extension is related to providing a QoS control mechanism along the physical path where the vLink is provisioned.

Conceptually, the abstract decomposition and extension are completely transparent to final users [START_REF] Yu | Rethinking virtual network embedding: substrate support for path splitting and migration[END_REF], who are only aware of the dynamic virtual resources provisioned to compose the VI (called by User layer ). An abstract layer is introduced between the physical layer and the user layer to implement the required mechanisms to perform traffic control and QoS provisioning [Anhalt et al., 2010]. We explain this decomposition in Figure 5.4, where a vLink (part of the user layer ) is divided and extended on multiple virtual paths (the abstract layer ) allocated on top of a virtualized and distributed physical substrate (the physical layer ). vLink l v 1 is decomposed into four new vLinks (l v 2, l v 3, l v 4, and l v 5), and two virtual routers (r v A and r v B), forming the virtual paths. The communication between virtual resources r v 1 and r v 2 is effectively divided over two physical paths resulting from vLink decomposition. [ [START_REF] Yu | Rethinking virtual network embedding: substrate support for path splitting and migration[END_REF] argued that splitting techniques can decrease the usage of physical substrate resources and increase the acceptance ratio of new requests. However, the allocation of virtual paths increases the complexity since a virtual path is directly related to the location of virtual source and target. These locations also are discovered during the mapping process, and consequently, also the virtual paths composition.

In addition, [START_REF] Ricci | Lessons from resource allocators for large-scale multiuser testbeds[END_REF] drew lessons from the implementation of an allocation algorithm in the context of PlanetLab [START_REF] Bavier | Operating system support for planetary-scale network services[END_REF] and Emulab [START_REF] White | An Integrated Experimental Environment for Distributed Systems and Networks[END_REF] testbeds. They concluded that the resource allocator should have a well-defined and asynchronous interface to enable the negotiation with users and other allocators. Although the scenario explored in their work is simpler than the allocation of virtual infrastructures, the requirements are similar and must be considered. For example, as detailed in Chapter 3, a description language plays an important role in the negotiation step.

Recently, [START_REF] Haider | Challenges in Resource Allocation in Network Virtualization[END_REF] highlighted new challenges in the allocation of virtual networks, most of which related to the need for an adaptive approach capable of dynamically adapting the resources allocated to VIs requirements. In this context, the SAIL project has determined the elastic aspect of virtual resources as an important requirement for efficient usage and implementation of VIs [SAI].

We considered these requirements along with the expectations and needs of real users to produce a complementary list of key aspects that should be addressed in allocating virtual infrastructures. The users' expectations were defined based on [START_REF] Koslovski | Executing distributed applications on virtualized infrastructures specified with the VXDL language and managed by the HIPerNET framework[END_REF] and [START_REF] Truong Huu | Joint elastic cloud and virtual network framework for application performance optimization and cost reduction[END_REF]. As discussed in Chapter 4, users can generate efficient VI descriptions that represent the application requirements, and decompose them in different stages, identifying the exact capacity required for each one. The key requirements are divided in Infrastructure Providers' (InP) and users' allocation requirements:

InPs' requirements:

• The main objective of an InP is to allocate the maximum number of VI in an efficient manner, minimizing the number of physical resources activated. To achieve this purpose, an allocation algorithm should consider nodes and links with the same weight, allocating both at the same time, as highlighted in [Chowdhury et al., 2009]. Several algorithms perform the allocation in a two-step process, first allocating the nodes and then allocating the links, solving a shortest-path problem or a multi-commodity flow problem. This approach may lead to inefficient solutions in terms of resources usage.

• Virtual infrastructure can be positioned anywhere on top of a virtualized substrate. The allocation mechanism should minimize the spreading and fragmentation of physical resources. Decreasing the number of distributed physical resources activated reduces the administrative costs (e.g., energy and cooling).

• The virtual resources composing a VI can vary their capacity requirements during the reservation time. Instead of comparing single values representing the capacity requirements, allocators should manipulate capacity profiles, which represent the capacity variation during the reservation time.

• In some cases, an IT virtual resource cannot be allocated on a single resource because its requirements exceed the physical capacity. An allocator should consider the aggregation of similar physical resources composing a single virtual entity able to provide the required capacity. A similar approach has been implemented in vLinks extension and splitting [START_REF] Yu | Rethinking virtual network embedding: substrate support for path splitting and migration[END_REF].

Users' requirements:

• As discussed in Chapters 3 and 4, the new languages and techniques developed to compose and describe virtual infrastructures enable the direct participation of users in the allocation process. Users and management framework must interact to efficiently allocate a virtual infrastructure. The constraints and requirements are explicitly detailed guiding the allocator. Moreover, a VI description can be improved after a monitored execution, and the acquired knowledge should be used to improve the next VI allocation and execution, applying for example, the adaptability concept [START_REF] Andrzejak | On Adaptability in Grid Systems[END_REF].

• Following the pay-as-you-go model applied to Cloud Computing and Cloud Networking technologies, new services can be requested by users, such as security, reliability and adaptability. To provide these new services, the allocation process must be aware of the requirements and particularities of each service. In Chapter 6, we demonstrate how a service that offers reliable virtual infrastructures can be implemented, and the important role performed by the allocation algorithm.

Problem formulation

In this section we formulate the allocation problem using a graph representation. This formulation is guided by the requirements identified in Section 5.2.3 and aims to cover the attributes proposed by the descriptive language presented in Chapter 3.

Graph embedding problem

The problem of mapping VIs to a physical substrate corresponds to a classical graph embedding problem. The graph describing the VI, G v (R v , L v ), must be mapped on the physical substrate graph, G p (R p , L p ), where R v and R p are the set of virtual and physical nodes, respectively, and L v and L p are the set of virtual and physical links, respectively. Table 5.3 summarizes the notation used to formulate the allocation problem. Let's denote by Q R (r, t) the vector of capacities (e.g., memory and CPU) of node r (∈ R v or ∈ R p ) at time t ∈ [0, T ]. In addition, let P p be the set of all the simple physical paths between any two physical nodes, Q P (p, t) be the vector of capacities of physical path p ∈ P p , and Q L (l, t) the vector of capacities of link l ∈ L v , both at time t. For a physical path p = (l 1 , l 2 , . . . ), the bandwidth capacity is the minimum of all bandwidth values of l i in p. By adopting capacity vectors indexed by time, the capacities of IT resources and links can vary during the reservation's time.

Let A R (r) be the set of geographical locations of resource r (∈ R v or ∈ R p ). For virtual resources, the value of A R (r) can be specified by users, and for physical resources it represents the exact geographical location. Finally, let E R (r) be a binary function which identifies if a virtual resource requires exclusivity on a physical host, not sharing its capacity.

A map of a VI on a physical substrate represents the reservation of all the capacity requirements specified by the user, noted as:

Resources mapping : M R : R v → R p (5.1) Notation Meaning G v (R v , L v ) a graph of virtual resources R v (vertices) and the virtual links L v (edges) S v a set of virtual graphs G v i ∈ S v r i ∈ R v a virtual IT resource r j ∈ R p a physical IT resource l i ∈ L v
a virtual link l j ∈ L p a physical link p = (l 1 , l 2 , . . . ) a physical path p composed of a set of links P p set of all physical paths between any two nodes

t ∈ [0, T ] time instant of reservation period [0, T ] Q R (r, t)
the vector of capacities of a IT resource r indexed by time t Q L (l, t) the vector of capacities of a link l indexed by time t Q P (p, t)

the vector of capacities of a path p A R (r) geographical locations of resource r E R (r) binary function identifying exclusivity of virtual resources Table 5.3: Notations used to formulate the allocation problem.

Links mapping :

M L : L v → P p (5.2)
Given a set of VI requests S v , the embedding problem is to obtain a mapping of virtual nodes R v to physical nodes R p , denoted by M R , and virtual links L v to physical paths P p , denoted by M L , such that the following conditions are satisfied:

Q R (M R (r i ), t) ≥ Q R (r i , t), ∀r i ∈ R v j , ∀G v j ∈ S v , ∀t ∈ [0, T ];
(5.3)

Q P (M L (l i ), t) ≥ Q L (l i , t), ∀l i ∈ L v j , ∀G v j ∈ S v , ∀t ∈ [0, T ]; (5.4) A R (r i ) ⊂ A R (M R (r i )), ∀r i ∈ R v j , ∀G v j ∈ S v ; (5.5) E R (r i ) = 1 =⇒ M R (r i ) = M R (r j ), ∀i ∈ R v k , ∀G v k ∈ S v , ∀j ∈ R v m , ∀G v m ∈ S v .
(5.6)

Objective functions

As identified in Section 5.2.3, different objectives and functions can be exploited for solving the allocation problem. We formulate the objective functions considering both InP and users perspectives. The former was formulated in terms of allocation cost and physical substrate fragmentation, while the latter in terms of allocation quality.

To facilitate the introduction of these functions, explaining their motivations in a real scenario, we present in Figure 5.5 a VI request and in Figure 5.6 a physical substrate that must host the virtual infrastructure. The VI is composed of three virtual resources (r v A, r v B, and r v C) which are interconnected by a set of virtual links. A particular user has access to all VI components during the reservation time.

This VI must be allocated and provisioned on top of a distributed and virtualized physical substrate. Usually, this physical substrate is hierarchically organized and in-terconnected. Figure 5.6 presents an example of this hierarchical organization using a tree structure where the leaves are the IT resources, and the parent nodes represent the geographical organization and interconnection. Starting from the bottom, the physical resources (for example, r p 1, r p 2, and r p 3) are grouped into racks. These racks are positioned at different locations, such as lyon.fr.eu and paris.fr.eu. More specifically, in this example the exact location of the physical node r p 1 is noted as rp1.rack1.lyon.fr.eu. The distance between physical resources in this hierarchical organization is given by the number of intermediate hops. For example, the distance between r p 2 and r p 3 is one hop.

Physical substrate cost

For an InP, the cost to allocate a virtual infrastructure is proportional to the number of resources required to accommodate the user's requirements. Let's define the functions C r (r, t) and C l (l, t), which set the physical substrate cost for an amount of resource r ∈ R v and the cost for an amount of link l ∈ L v , respectively, both at time t. The total cost of resources R v , over a reservation time [0, T ] is given by:

C R (R v , T ) = T 0 ( r i ∈R v C r (r i , t)) dt (5.7)
Similarly, the total cost of links L v , over a reservation time [0, T ] is defined as:

C L (L v , T ) = T 0 ( l i ∈L v C l (l i , t) × len(M L (l i ))) dt (5.8)
where len(M L (l i )) gives the length of the path provisioned to allocate virtual link l i . Consequently, the total cost of a VI G v is noted as:

C V I (G v , T ) = αC R (R v , T ) + βC L (L v , T ) (5.9)
Constants α and β are tunable weights that allow the balance and the normalization between resources' and links' costs. Given a set of VI requests S v , an immediate metric is the minimization of the total cost for the infrastructure provider, defined by: minimize:

G v i ∈S v C V I (G v i , T ) (5.10)
subject to the constraints defined by conditions (5.3)-(5.6).

Physical substrate fragmentation

The cost of a virtual infrastructure allocation is usually negotiated and charged to the final user. However, InPs have administrative costs that vary depending on the number of resources activated. These costs are difficult to be charged during the SLA negotiation, but can have a negative impact on the InP objectives. For example, the allocation of spread VI components induces long-term issues: i) it increases costs related to energy consumption, cooling, and provisioning of high-speed networks to interconnect data-centers due to the simultaneous activation of several racks and network equipments; and ii) it decreases the acceptance ratio of new requests due to increased congestion on communication and computational resources [START_REF] Zhu | Algorithms for Assigning Substrate Network Resources to Virtual Network Components[END_REF]. These issues are directly related to the physical substrate fragmentation. We define the physical substrate's fragmentation as a metric to qualify the number of physical resources (IT and network) reserved and activated on a distributed and virtualized substrate. This metric is given by the ratio of the number of activated resources to the total number of physical resources available.

To exemplify the fragmentation, lets consider the virtual infrastructure request presented in Figure 5.5 and the physical substrate described in Figure 5.6. Considering the physical substrate fragmentation, an efficient allocation mapping allocates all the virtual nodes and virtual links using the minimum number of physical components. For example, allocating the virtual nodes into physical machines r p 1, r p 2, and r p 3, respectively, only requires activating one rack and using a single physical communication path to provide network access to those components. Furthermore, an optimal allocation places all virtual nodes (r v A, r v B, and r v C) into physical machine r p 1 only requiring the activation of a single computing resource. In the long term, it is expected that minimizing the physical substrate's fragmentation increases the acceptance ratio of an InP.

InPs aim to minimize the physical resources' fragmentation. Thus, let's denote by F R the subset of physical resources r ∈ R p that supports at least one virtual resource running, and similarly, by F L the subset of physical links l ∈ L p that hosts at least one virtual link activated. The objective is to minimize the number of physical resources (IT and networking) to allocate S v : minimize: 5.11) subject to the constraints defined by conditions (5.3)-(5.6).

#F R + #F L #R p + #L p (

Allocation quality

From the user's perspective, the allocation and provisioning of spread VI components increases latency of network communications [START_REF] Koslovski | Executing distributed applications on virtualized infrastructures specified with the VXDL language and managed by the HIPerNET framework[END_REF] as follows:

• node-to-node: usually, the more distant apart the physical hosts are, the higher the latency in communication. This issue is more perceptible in communication intensive applications, but can also affect regular applications;

• user interaction: interactive applications (such as remote terminals or visualization tools) are explored by users to control the virtual infrastructure and their applications. The response time of these applications increases proportionally to the physical distance between the user and the virtual infrastructure components.

Chapter 4 showed that advanced users can specify the exact configuration required to execute their applications efficiently including the exact location where the virtual resources should be provisioned [START_REF] Koslovski | VXDL: Virtual Resources and Interconnection Networks Description Language[END_REF]. Reasons why a certain application should run in a certain location, include data-location dependency, security, and even limitations on data mobility because of governmental law. Although this location-based provisioning can be explicitly required, regular users are not aware of the efficient configuration in terms of networking and computational power. Moreover, some users are not familiar with the meaning of latency in communications, and only wish a set of VMs to execute their applications, as the approach explored in Clouds.

In this context, defining the allocation quality from the user's perspective is a difficult task as it is optimal when the virtual request is precisely defined and all resources correctly provisioned. When the request is non-absolutely defined, quality is subjective: the user does not care about the optimal configuration to execute his application, but he wants the application to run well, usually with efficient interaction among its distributed components. Figure 5.5 describes this scenario: a VI is requested by a user with access point located at lyon.fr.eu. The user does not specify any requirement in terms of virtual-resources' location or network configuration. Thus, the InP can allocate this request anywhere on top of the distributed substrate represented by Figure 5.6. The resources' proximity can be optimized for both types of users (e.g., advanced or regular) independently of the VIs description level. We call allocation quality of a VI the average of all distances (calculated in hops) between the virtual resources and one specific geographical landmark (the reference point). More specifically, the reference point can be the location of the user; or the location of a certain virtual resource, as specified by the user.

To illustrate the definition of allocation quality, let's consider the user's location as the geographical landmark for hops calculation (lyon.fr.eu). Allocating resources distributed across other locations (such as es.eu) results in a greater number of hops from the user's location than allocating resources near lyon, or even fr. More specifically, allocating all the components of this VI on physical node rp1.rack1.lyon.fr.eu results in a minimum distance (in this case, only one hop, from lyon's access point), and consequently, an optimal allocation quality.

The quality of an allocation is directly related to the location of the virtual resources. Let's define the function D R (a i , a j ) that gives the distance between locations a i and a j in number of hops, where a ∈ A R , and each hop is equivalent as one unit. Further, define a u as the location specified by the user (the reference point). The optimal allocation quality is given by the minimization of the average resources' distance: minimize: 5.12) subject to the constraints defined by the conditions (5.3)- (5.6).

r i ∈R v D R (A R (M R (r i )), a u ) #R v (
Conceptually, the quality improvement is related to the minimization of physical substrate fragmentation. This relationship is observed in results presented in Section 5.5.

A heuristic for allocating VIs

As discussed beforehand, there are different approaches to solve the graph-embedding problem, such as heuristics based on substrate characteristics, path-splitting methods, multi-commodity flow modeling, and isomorphism-based detection. Among these options, we choose a subgraph-isomorphism detection [West, 2000], solvable in polynomial time, to incorporate the allocation constraints and to examine the metrics proposed in this chapter. As result of this work, we have proposed a heuristic to allocate virtual infrastructures [VXAlloc] that drastically decreases the decision time by proposing a method to restrict the search-space. This method has been patented and is exploited by the LYaTiss startup, and for the sake of confidentiality its critical part cannot be detailed here. Therefore this section overviews the method and details experimental results obtained with our implementation of the heuristic.

Subgraph-isomorphism detection

The technique for identifying isomorphic subgraphs acts as an alternative for embedding a virtual graph in a physical one [West, 2000] [Cordella et al., 2004] [Lischka and Karl, 2009]. An isomorphism, with edges extension, from G v to G p is a function f that maps R v to R p and L v to P p such that each edge l i ∈ L v with endpoints r m ∈ R v and r n ∈ R v is mapped to a path of edges l j ∈ P p with endpoints f (r m ) ∈ R p and f (r n ) ∈ R p , subject to the constraints defined by the conditions (5.3)- (5.6).

Figure 5.7 exemplifies a subgraph isomorphism map between graphs G v and G p . Applying function f for all r i ∈ R v and for all l i ∈ L v results in a set of maps noted < x, f (x) >, where x represents both vertices or edges, contextually.

A subgraph-isomorphism mapping of non-simple graphs (e.g., VIs) requires the extension of edges to interconnect non-adjacent vertices. Figure 5.7c exemplifies this require-

(r v A) = r p 3, f (r v B) = r p 2, f (r v C) = r p 6, f (l v A) = l p 2, f (l v B) = l p 3 ∪ l p 5, f (l v C) = l p 6
, as exemplified by 5.7c.

ment: r v B and r v C were mapped on r p 2 and r p 6, respectively. Consequently, l v B must be extended over l p 3 and l p 5.

Algorithms formalization

This section formalizes the main heuristics composing the allocation algorithm. The notation presented in Table 5.3 is used to describe the pseudo-algorithms. In Algorithm 5.1 we present a general view of the location-aware algorithm. Initially, the location-aware algorithm identifies the set of physical landmarks specified by the user, as well as the set of virtual resources without location constraints. An iteration is performed on these sets. Each time, a physical location specified by the user is defined as the required location constraint for components that do not have this information. At this moment, a subgraph-isomorphism detection is performed to find a map solution. If no allocation solution is found for this configuration, the location constraint is relaxed for these resources (the location's precision is decreased).

Let's use Figure 5.6 as example. In the first iteration, the required location of virtual resources r v 1, r v 2, and r v 3 are defined as lyon.fr.eu (the user's location). Considering that no solution is found with this configuration, the geographical location of these virtual resources is relaxed from lyon.fr.eu to fr.eu. Observe that, in this way, the algorithm always tries to allocate virtual components as close as possible to the geographical landmark. The algorithm focuses on solving the embedding problem, optimizing the allocation quality and decreasing the substrate fragmentation, as discussed in Section 5.3. A R represents the combination of all locations defined in the VI request, including the original user's location (the first one to be used as reference). To induce the minimization of virtual resource distances, the algorithm temporarily sets a location constraint for these resources that have not specified this requirement. The resulting set of virtual resources (R v ) is used as input for the allocation procedure described in Algorithm 5.2. If no solution is found, the location constraints of those resources are relaxed.

Algorithm 5.2 solves a subgraph-isomorphism detection respecting the allocation constraints defined in Section 5.3. This algorithm is based on the formulations proposed in [START_REF] Cordella | A (sub)graph isomorphism algorithm for matching large graphs[END_REF] and [START_REF] Lischka | A virtual network mapping algorithm based on subgraph isomorphism detection[END_REF]. We mainly differ from the origi-nal proposition by adding the optimized constraints on generating candidates and by not using a backtracking approach.

This recursive algorithm propagates the virtual request (R v and L v ) and a set of temporary allocated resources (R v and L v ). With this information, pairs of virtualphysical candidates are generated (line 5) and covered in the following lines aiming the total allocation of a virtual infrastructure. Each allocated resource is added to a temporary set and the recursion is continued.

Experiments

This section describes a set of experiments performed with VXAlloc and the respective analysis considering the metrics proposed in Section 5.3. A complementary comparison between the wasted capacity and the acceptance-ratio of VXAlloc and non-virtualized infrastructures are discussed.

Scenario composition

We ran the experiments on machines belonging to Grid'5000 [START_REF] Cappello | Grid'5000: a large scale and highly reconfigurable grid experimental testbed[END_REF] with the following configuration: 2 CPUs Intel Xeon L5420, 4 cores, 2.5 GHz, 6 MB cache, and 32 GB RAM. We used Java Runtime Environment version 1.6.0 20 to run the allocator and the other HIPerNet tools.

The physical-substrate graphs and the virtual-request graphs were generated by the topology generation tool GT-ITM [START_REF] Calvert | Modeling Internet Topology[END_REF]. Physical substrates use the transitstub model, which results in graphs with domains interconnected by a backbone. Virtual requests were generated considering the normal model without backbone routers, following setups similar to previous work [START_REF] Yu | Rethinking virtual network embedding: substrate support for path splitting and migration[END_REF]] [Chowdhury et al., 2009].

Two physical substrates were simulated:

• a small-size substrate composed of 100 resources (domains and backbone routers) and approximately 200 physical links, organized in 4 geographical domains, and interconnected by a backbone composed of 8 resources;

• a medium-size substrate composed of 500 resources, approximately 4000 links, divided in 8 geographical domains, and interconnected by a backbone composed of 20 resources.

The values of CPU cores (2, 4 or 8) and memory capacity (2 GB, 4 GB, 8 GB or 16 GB) follow a uniform distribution. The network's bandwidth capacity was defined as 1 Gbps within domains and 10 Gbps between domains (in the backbone). To represent a realistic scenario, the allocation of computing nodes on backbone resources was disabled.

Virtual requests can require 2, 4, 6, 8, or 10 nodes. The probability of two virtual nodes being connected is 0.5, as defined in GT-ITM configuration. All VI requests require a reservation period of one hour. The values of CPU cores (1, 2 or 4) and memory capacity (256 MB, 512 MB, 1 GB, or 2 GB) also follow a uniform distribution. The same approach was used to generate network-bandwidth requirements (10 Mbps,20 Mbps,40 Mbps,100 Mbps,200 Mbps,400 Mbps,or 600 Mbps).

The values of α and β used to calculate the VI cost (C V I ) were defined as α = β = 1, indicating that nodes and links have the same weight in the InP, as explored on previous scenarios [START_REF] Yu | Rethinking virtual network embedding: substrate support for path splitting and migration[END_REF]. The cost functions (C r (r, t) and C l (l, t)) require an equivalent metric to calculate the costs. As an example of this equivalence, in terms of cost calculation, we arbitrarily set that 1 GB, 1 core, and 100 Mbps are the basic units for memory, CPU and bandwidth, respectively. The definition of these values requires a specific study based on InP policies and current substrate load, as proposed by [START_REF] Zhu | Algorithms for Assigning Substrate Network Resources to Virtual Network Components[END_REF]. We leave this implementation and analysis for future work.

The number of VI requests submitted were: 100 to the small-size substrate, and 300 to the medium-size substrate. The number of requests' sources varies (1 or 3) to represent different request-submission scenarios. Results identified by allocation with basic algorithm were obtained by executing the regular subgraph-isomorphism detection without the geographical-location optimization. The optimized execution is identified as allocation with our optimized algorithm.

All averages presented here were calculated considering 10 executions and have a confidence interval of 95%.

Physical substrate fragmentation and cost

The second experiment investigates the variation of InP allocation costs and physicalsubstrate fragmentation. For both metrics, the results were obtained considering two configurations: small-size and medium-size physical substrate. Figure 5.8 shows the average total fragmentation of a small-size physical substrate. The comparison performed in Figure 5.8 highlights that our algorithm improves the physical substrate usage by decreasing the fragmentation by approximately 10% in the case where all requests come from the same location. Its performance increases with the number of requests source: 28% when 3 sources are submitting requests. Similar results are obtained with requests submitted to the medium-size substrate (see Figure 5.9).

The average of the total cost required to allocate these requests were analyzed and presented in Figure 5.10 and Figure 5.11. For these scenarios, our optimized algorithm also decreases the average cost. Considering requests submitted by only 1 source, the cost decreases in both scenarios: approximately 4% on a small-size physical substrate, and 8% on a medium-size substrate. When analyzing requests submitted by 3 sources, the cost also decreases nearly by 17% and 21% for the small-size and the medium-size substrates, respectively.

Allocation quality

We also measured the the allocation quality. The user location (source of requests) was defined as the reference point for calculating the distances.

Figure 5.12 and Figure 5.13 present the average for the small-size and medium-size substrate, respectively. The results show that the average total distance is smaller with our algorithm in both scenarios, for requests submitted by 1 and 3 source(s). When only 1 source was submitting requests, the average total distance decreased by almost 13% for small-size and medium-size substrates. When 3 sources were submitting requests the average total distance is highly decreased: by approximately 36% and 39% for small-size and medium-size substrates, respectively. Consequently, it is expected that the users of VIs allocated by our optimized algorithm have a lower impact of the physical-resource distribution in terms of network communication. An analysis of the results of the optimized algorithm highlights the relationship between performance and the number of geographical landmarks used as reference points (in this case, the user's location). For all metrics, the results obtained with three sources of requests showed better performance than those obtained with one source of requests, independently of the physical substrate size. Consequently, increasing performance of these metrics (physical fragmentation, allocation cost, and allocation quality) is expected when the number of sources submitting VI requests is augmented.

Comparing VXAlloc with non-sharing allocation

A complementary study was performed to compare the percentage of wasted capacity and the acceptance ratio of VXAlloc (a virtualized allocation) and non-sharing allocation. For that, we simulated a physical substrate network comprising 5 racks, each one composed of 24 nodes, interconnected by a hypercube network. Every physical node disposes of a 8 core 2.4 GHz CPU, and a memory capacity of 32 GB. Physical nodes of a rack are interconnected with a bandwidth capacity of 1 Gbps, while the capacity between racks is 10 Gbps.

The virtual infrastructures were also generated by the GT-ITM tool and follow the normal model [START_REF] Calvert | Modeling Internet Topology[END_REF]. A set of virtual requests composed of 200 VI descriptions vary the number of virtual nodes (among 2, 4, and 8) following a uniform distribution. All virtual nodes require the provisioning of 1 core, varying the memory configuration among 4 GB, 8 GB, 16 GB, and 24 GB. We used the load notation to identify the percentage of total memory required by virtual resources when compared with the available 32 GB.

Results identified by non-sharing allocation are the result of requests that require exclusivity for all nodes, allocated by VXAlloc. Those with the label: allocation with our optimized algorithm are the result of the normal execution of VXAlloc. Note that by requiring exclusity for all virtual resources allocation, the physical substrate sharing is automatically disabled.

Evaluation

The first results identify the wasted capacity (in percentage) of both allocation solutions. Figure 5.14 presents this comparison. In the first graph (left side) the loads (percentage of virtual resources over the physical capacity) are analyzed individually. The virtual requests vary following the configuration described above. As expected, we observe better performance of VXAlloc in terms of physical substrate usage, highlighting one of the main advantages of virtualization: the possibility of sharing a physical resource among multiple virtual resources, respecting the user's expectations. The wasted capacity decreases by 65.6%, 72.9%, and 87.26% for loads 0.125, 0.25, and 0.5, respectively. With load 0.75 both algorithms present the same wasted capacity due to the physical limitation.

The second graph of Figure 5.14 (right side) gives the comparison when load varies (respecting the values defined in the configuration). Following the same line, VXAlloc also presents better performance in terms of resource usage, decreasing the wasted capacity by 34.2%. In addition, we performed a comparison of the acceptance ratio of both scenarios. The first graph of Figure 5.15 (left side) shows that VXAlloc has higher acceptance ratio than the non-sharing allocation under all load configurations. When the load varies following a uniform distribution (right-side graph), VXAlloc also exceeds the non-sharing values by 178% percent.

Conclusions

This chapter concentrates on the allocation of virtual infrastructures guided by the geographical location of virtual resources. Thanks to VXDL (as discussed in Chapter 3), users can interact with the allocation mechanism, informing specific attributes and setting constraints that represent their expectations and QoE requirements.

We formulated the allocation-problem and proposed metrics considering the users' (allocation quality) and the InPs' (cost and fragmentation) perspectives. An allocation heuristic that optimizes both perspectives has been implemented as a patented module of the LYaTiss Weaver. Our experiments show that it is possible to improve the virtualinfrastructure allocation's quality (approximately 39% for VIs allocated on a medium-size substrate), and simultaneously decrease the physical substrate's fragmentation and the substrate's cost (almost 28% and 21% on a medium-size substrate, respectively).

A future research line that we will explore is the interconnection of allocation strategies with information exposed by the InP management framework. For instance, the buffer capacity of virtual switches and routers are relevant information for the efficient provisioning of split and extended paths [Anhalt et al., 2010]. In addition, a different approach for modeling the allocation problem is planned as future work (discussed in Chapter 7).

-SIX -Reliable Virtual Infrastructures

Conclusions

The work presented in this chapter was published at the Second IEEE International Conference on Cloud Computing Technology and Science (Cloud-Com 2010) [START_REF] Koslovski | Reliability support in virtual infrastructures[END_REF]. It has been done in collaboration with DoCoMo Labs USA (http: // www. docomolabs-usa. com/ ) .

Introduction

O

ne of the main benefits of infrastructure virtualization is the capability of providing new services to accomplish the users' expectations. Among these new services we highlight the provisioning of transparent reliability. In other words, reliability becomes a service provided by the InPs.

Independent of the application context, some tasks are critical and their failure would cause the system to collapse. In addition, even the failure of non-critical tasks could significantly impact (for instance, delay) the completion of an application or service. In case of failure, a component of a virtual infrastructure can be migrated to a different location in the physical substrate. One key aspect in this scenario is for the infrastructure user to be able to specify the reliability associated with a task during the VI bootstrap, and for the InP to transparently provide the reliability to the user and effectively provision it through the allocation of virtual backup nodes ready to take over in case of node failure.

We discuss the motivations and gains of introducing customizable reliability of virtual infrastructures when executing large-scale distributed applications, and present a framework to specify, allocate and deploy virtualized infrastructure with reliability support. This chapter proposes an approach to efficiently specify and control the reliability at runtime. We illustrate the ideas described above by analyzing the introduction of reliability at the VI level on a real application. Experimental results, obtained with the Bronze Standard application (described in Section 4.4.1 of Chapter 4) running in virtual infrastructures provisioned on the experimental large-scale Grid'5000 platform, show the benefits of the reliability service.

The rest of this chapter is organized as follows. Section 6.2 reviews the state of the art and technologies related to reliability on distributed systems. Section 6.3 motivates the introduction of reliability in virtual infrastructures, and identifies system goals which guide the design of our proposition. In Section 6.4, we discuss the issues associated with the translation of the reliability requirements, specified with VXDL, into a reliable VI. Section 6.5 describes the allocation and provisioning of a virtual reliable graph onto the physical substrate. In Section 6.6, we show experimental results with the Bronze Standard application as well as a cost analysis. We conclude this chapter and present perspectives for future work in Section 6.7.

State of the art

Providing reliability and availability on virtualized environments is an issue that has been studied in the recent years. Within virtual nodes, hypervisors such as Xen [START_REF] Barham | Xen and the art of virtualization[END_REF] provide the capability to store live snapshots of the virtual machines to reliable storage, which can be resumed on other physical nodes if failures occur. Remus [START_REF] Cully | Remus: high availability via asynchronous virtual machine replication[END_REF] and Kemari [START_REF] Tamura | Kemari: VM Synchronization for Fault Tolerance[END_REF] improved static snapshots by periodically updating live snapshots to replica nodes that are on standby. From another perspective, proactive migration of virtual machines to other healthy nodes is considered upon early warnings of impending failures [START_REF] Nagarajan | Proactive Fault Tolerance for HPC with Xen Virtualization[END_REF]] [Clark et al., 2005].

Also, recovering from failures has received some attention in the literature. On a large-scale execution environment, the re-submission mechanism is one of the solutions used to make the application continue running when a failure is detected [Lingrand et al., 2009a[START_REF] Lingrand | Analyzing the EGEE production grid workload: application to jobs submission optimization[END_REF]. The application's makespan is longer in this case when the submitted task's execution time is long. Another possible solution is to periodically save static snapshots of the entire VI [START_REF] Kangarlou | VNsnap: Taking Snapshots of Virtual Networked Environments with Minimal Downtime[END_REF] to disk, while execution is in progress. The live snapshots are reloaded as a new submission if failures are encountered in the current execution. The application's makespan then depends on the re-submission interval and the snapshot interval, which may be long due to disk-access times. Moreover, synchronizing clocks of reloaded virtual machines is critical as it can compromise the execution of time sensitive applications [START_REF] Broomhead | Virtualize everything but time[END_REF].

Fault tolerance is provided in some contexts, such as data centers [START_REF] Mysore | PortLand: A Scalable Fault-Tolerant Layer 2 Data Center Network Fabric[END_REF]] [Guo et al., 2009]. However, it is achieved through specific engineering of the network nodes and links over-provisioned for redundancy. [START_REF] Yeow | Designing and Embedding Reliable Virtual Infrastructures[END_REF] provides mechanisms to pool backup nodes to achieve a desired level of reliability. However, it is mostly a theoretical work and does not provide any vertical integration from the user specification to the physical substrate allocation. In [START_REF] Menth | Resilience Analysis of Packet-Switched Communication Networks[END_REF], the authors focus on providing link reliability in wide-area network, by considering the most likely link failure combinations, and providing backup links for these failures. The reliability of virtual nodes is not addressed in this work.

These mechanisms, unfortunately, do not provide sufficient transparency against failures. Re-initiating or resuming applications at a later time to recover from failures will impact any time-sensitive applications. Therefore, a live protection mechanism such as Remus [START_REF] Cully | Remus: high availability via asynchronous virtual machine replication[END_REF] or Kemari [START_REF] Tamura | Kemari: VM Synchronization for Fault Tolerance[END_REF] is needed. In both Remus and Kemari, the memory state of a protected (critical) node is continuously synchronized with a replica (backup node), as with checkpointing. When a failure in the protected node occurs, the backup node can resume execution immediately, and the failover process can be made transparent to other nodes in the VI. This live protection mechanism has another advantage over prior snapshot mechanism: instead of the entire VI, only the critical nodes need to be checkpointed.

The key difference between Remus and Kemari is that Kemari initiates a checkpoint only when external events occur, such as disk writing and network-packet sending, whereas Remus checkpoints at a regular interval. One important feature of Remus is that, at every checkpoint, the external output is buffered locally in the critical node until it is assured that the backup node completes that checkpoint update. This ensures that any failover operation will be transparent to other unaffected nodes. Moreover, the protected node continues execution in parallel until the next checkpoint, thereby increasing system performance over classical lock-step checkpointing. Kemari, on the other hand, does not perform any buffering and relies on pausing the protected node to achieve the required transparency. We chose to use Remus over Kemari in our proof of concept as it provides a finer and customizable granularity between checkpoints, which can be as frequent as tens of milliseconds. As of Xen 4.0.0 [START_REF] Barham | Xen and the art of virtualization[END_REF], Remus is included in the official Xen releases.

Motivations and goals

Networking and computing infrastructures are subject to random failures of nodes and links. These failures are not rare in the case where the number of physical entities is large, especially in distributed systems. Currently, Cloud Computing providers have defined Service Level Agreements (SLAs) comprising the percentage of reliability, availability, or uptime of their systems. For instance, Amazon EC2 [AMAa] and Windows Azure [AZUa] inform an availability of 99.95%, while SalesForce [SAL] informs 99.9% of availability. However, the levels are not guaranteed: when an SLA is not respected (e.g., a failure occurs compromising the execution) a compensation in terms of credits for a new execution is offered to the user. For some users this compensation is sufficient, but for critical applications, a failure can compromise the entire execution.

The impact of a node failure to a distributed application can be very different; a failed worker node amongst hundreds of others is less significant than the failure of a database server. The reliability of a system may be evaluated quantitatively and qualitatively. The Mean Time Between Failures (MTBF) is a statistical metric to determine the failure rate of the underlying infrastructure, which can be evaluated by the InP's management system.

One approach is for the application designer to ensure reliability himself, by providing redundancy in the components and modules composing the application. However, this requires different sets of expertise: one is the expertise to design the system in order to deliver the intended application; another is to ensure that the components are integrated so as to support the desired reliability.

Furthermore, the actual reliability will depend on the physical resource upon which the system is deployed. If the application developer provides his own physical substrate (servers and switches), then he can specify the reliability of each individual element. If on the other hand the system is deployed using a virtualized infrastructure, the reliability characteristics of the physical resources might be unknown.

Since it is common for the application developer to delegate the elastic provisioning of resources to the infrastructure provider, in order to only use the proper amount of resource in the face of varying demands, the corresponding provisioning of the reliability must by the same token be delegated as well. From the application provider's perspective, it is easier and more flexible to specify a level of reliability and have the reliable virtual infrastructure provided transparently as part of a SLA. On the other hand, from the InP's perspective, reliability becomes a service that can be added and that can generate new revenue streams. Further, the infrastructure provider is free to manage reliability in light of his own constraints and optimization opportunities: a backup might be associated to different resources from different independent applications. This multiplexing of the backup resources provides economy of scale to the infrastructure provider [START_REF] Yeow | Designing and Embedding Reliable Virtual Infrastructures[END_REF].

These observations highlight a few requirements for a reliable virtualized infrastructure:

• the virtual infrastructure user should be able to specify reliability in a flexible and expressive manner (we exploit VXDL for specifying the reliability requirements, as discussed in Chapter 3);

• the InP should be able to implement and allocate reliable and backup resources efficiently (we extended the formulation presented in Chapter 5 as presented in Sections 6.4 and 6.5);

• both the virtual-infrastructure user and the physical-network provider need to see their business objectives satisfied (we discuss the results in Section 6.6).

Figure 6.1 summarizes the stages and requirements to provide reliable virtual infrastructures considering the application-provider specification. Our goal is to describe tools which allow to satisfy these requirements, and to deliver the efficient provisioning of reliability in a virtual infrastructure, as specified by the virtual infrastructure user.

From reliability requirements to reliable VIs

The VXDL language allows for describing the required reliability level for a VI. The application provider can set the reliability requirement individually for each virtual resource (nodes and links), or for a group of resources. This approach enables the composition of a VI with different requirements in terms of reliability level. For instance, an application with a master-worker architecture, e.g., MapReduce [START_REF] Dean | Mapreduce: simplified data processing on large clusters[END_REF], can require more reliability support for masters, and set the same reliability level for a group of workers. The example presented in Figure 6.2 illustrates the flexibility of the specification language. Part of a VXDL file, the example describes a group of 30 virtual nodes with a reliability specification of 99.9% (among other parameters).

The VXDL file containing the reliability requirements is interpreted by the VXDL parser [VXDLParser], a versatile tool that translates a VI specification into a resource request to the InP management framework. Specifically, it analyzes the VI specification, . . . <vGroup i d=" w o r k e r s " m u l t i p l i c i t y =" 30 "> <vNode i d=" w o r k e r "> < r e l i a b i l i t y >99.9%</ r e l i a b i l i t y > <memory> <s i m p l e >512</ s i m p l e > <u n i t >MB </ u n i t > </memory> <cpu> <c o r e s >1</ c o r e s > <f r e q u e n c y > <s i m p l e >1.0</ s i m p l e > <u n i t >GHz</ u n i t > </ f r e q u e n c y > </cpu> </vNode> </vGroup> . . . automatically fills in any missing components (e.g., default elements and values by some predefined templates), and translates the VI into a graph representation for resource allocation (see next section). Furthermore, automated inclusion of backup components into the graph for targeted reliabilities is added onto the VXDL parser. The procedure is described below.

Automatic generation of backup nodes

A targeted reliability, in general, can be achieved with sufficient backup nodes. A critical node with a low MTBF will require more backup nodes on standby (synchronized with the active node) than another node with a higher MTBF for the same reliability level, if physical failures are independent. As noted in [START_REF] Yeow | Designing and Embedding Reliable Virtual Infrastructures[END_REF], backup nodes can be shared among different groups of critical nodes to minimize the total number of backup nodes (and hence, minimal idle nodes).

For example, a VI has two groups of critical nodes with n 1 and n 2 critical nodes respectively, requires at least r 1 and r 2 reliability respectively, and k 1 and k 2 backup nodes respectively. It is possible to share the backup nodes for n 1 + n 2 nodes such that the total number of backup nodes is lower than k 1 + k 2 provided that every backup node is a standby for all other critical nodes. In [START_REF] Yeow | Designing and Embedding Reliable Virtual Infrastructures[END_REF], the Opportunistic Redundancy Pooling (ORP) mechanism imposes a sharing policy between groups of critical nodes such that it is possible to have min(k 1 , k 2 ) backup nodes so long as the reliabilities of every group is satisfied.

The VXDL parser implements ORP to evaluate the number of backup nodes required. Since ORP assumes independent physical failures, it also generates additional physicalembedding constraints such that the physical locations of all shared backup nodes and critical nodes validate that assumption. For example, virtual nodes may not be embedded onto the same physical host, or rack that is connected to the same switch, or power supply.

Backup links: consistent network topology

Failovers from the critical nodes to backup nodes are expected to be transparent to the unaffected nodes of the VI. While the virtual machine protection tool (e.g., Remus) guarantees the failover time in tens of milliseconds and consistency across the VI through output buffering, consistency in the network topology has to be guaranteed through additional links to the backup nodes. That is, failed critical nodes which are resumed at the backup nodes must be connected to the rest of the VI as described in the original specification.

To ensure failover transparency, the additional backup links are pre-allocated (together with the VI) rather than on demand after failures occurred. In the latter case, resources for backup nodes cannot be guaranteed and, even if sufficient resources are available, undesired delays may be incurred during failover. Furthermore, active synchronization from the critical nodes to backup nodes consume bandwidth, which has to be allocated as well. [START_REF] Harary | Node Fault Tolerance in Graphs[END_REF] have devised methods to minimize the number of additional links required. Specifically, a new graph G is constructed with n + k nodes such that the original VI is always a subgraph of G when any k nodes are removed. Unfortunately, this class of solutions is infeasible in our system:

1. Guaranteeing that the VI is a subgraph of G only ensures that the graph after k node failures is isomorphic. Hence, recovering from failures may result in unaffected nodes being moved around in order to recover the VI.

2. Exact solutions are found only for regular graphs such as rings, lines, square-grids and trees. For general graphs, heuristics are used [START_REF] Dutt | [END_REF]Mahapatra, 1997] [Ajtai et al., 1992].

3. The solution assumes unweighted links; adding weights on top of the solution introduces an additional layer of complexity.

As such, similar to the approach in [START_REF] Yeow | Designing and Embedding Reliable Virtual Infrastructures[END_REF], we add i) links from nodes of the VI to backup nodes such that every backup node is linked to neighbors of critical nodes, and ii) links interconnecting the backup nodes since two critical nodes which are neighbors of each other may fail simultaneously. We call the former set first-order backup links and the latter set second-order backup links. The second-order links are only required if two critical nodes are linked in the original VI.

In addition to the results of [START_REF] Yeow | Designing and Embedding Reliable Virtual Infrastructures[END_REF], we reuse the first-order backup links for synchronization between critical nodes and backup nodes whenever possible. Algorithm 6.1 shows the procedure for the generation and reuse of first-order backup links and their attributes: bandwidth (bw ) and latency (lat). We omit details on the generation of second-order links and the remaining synchronization links that were not reused from the first-order links, since the procedure is similar to that of the first order. A new link between a backup node and some other node is created if it is a neighbor of a critical node. Hence, in Figure 6.3b, node r v A connects to all three nodes. Furthermore, the attributes of link (r v A, r v 3) can function as links (r v 1, r v 3) or (r v 2, r v 3). Links (r v A, r v 1) and (r v A, r v 2) are reused for synchronization. With one more backup node (as in Figure 6.3c), the firstorder backup links of node r v B are the same as those of node r v A, and with a second-order backup link between node r v A and r v B to function as the link (r v 1, r v 2) when both critical nodes fail.

Reliable VI provisioning

Translating a VI to a graph representation results in a unified input to a resource allocation manager, regardless whether a VI requires reliability support. This immediately translates the resource allocation problem into a graph embedding problem. However, reliability support demands tighter allocation constraints, which are not present in VI's that does not require any reliability guarantee. That is, virtual nodes should be mapped in a way that virtual node failures resulting from the physical substrate should be independent. Then, virtual nodes of the same VI should not be allocated onto the same physical node. Moreover, the framework management should be able to provision and control the execution of reliable virtual infrastructures, identifying the occurrence of physical resources failures, and monitoring the efficiency of the service execution. In this section we describe the graph constraints related to the reliable VI provisioning, and describe the implementation of this service using the HIPerNet framework.

Graph embedding and mapping constraints

In Chapter 5 we presented an algorithm to allocate virtual infrastructures based on subgraph-isomorphism detection. In this section, we extend that formulation by adding the constraints related with reliability support. These constraints complement the generation of backup links described by Algorithm 6.1 and guarantee the allocation of reliable virtual nodes. While the classical graph embedding problem enforces virtual nodes to be placed only onto unique physical nodes, it is insufficient to assure independent failures.

In the example presented in Figure 6.4, the physical substrate of Figure 6.4a must host the virtual infrastructure of Figure 6.3a. The nodes to be protected r v 1 and r v 2, and backup node r v B would need to be placed on different physical resources, hence creating additional mapping constraints to the graph embedding problem.

We formulate these conditions according to the notation used in Chapter 5 (refer to Table 5.3). Initially, let B(r i ) be the set of backup nodes of virtual resource r i ∈ R v . An efficient mapping solution will not allow the sharing of physical resources among r i and the set of backup nodes R(r i ). Also, the physical resources mapping the backup nodes must have enough capacity to allocate the original virtual component in the event of a failure. More specifically, the conditions are:

M R (r i ) = M R (r j ), ∀r i ∈ R v , ∀r j ∈ B(r i ); (6.1) M R (r i ) = M R (r j ), ∀r k ∈ R v , ∀r i ∈ B(r k ), ∀r j ∈ B(r k ); (6.2) Q R (M R (r k ), t) ≥ Q R (r i , t), ∀r i ∈ R v , ∀r k ∈ B(r i ), ∀t ∈ [0, T ]. (6.
3)

The allocation mapping presented in Figure 6.4b follows the reliable allocation conditions discussed above. Virtual resources and their relative backups are not sharing the physical resources, and the virtual links were allocated to keep the network topology consistent in the case of failures.

Mapping solution

The graph embedding problem is well-known to be NP-hard [Chowdhury and Boutaba, 2010]. The additional allocation constraints between virtual nodes, however, does not make the problem less complex since solution space remains the same even though the search space may be reduced. To this end, we implemented the allocation constraints to the VXAlloc software. The subgraph isomorphism detection implemented by VXAlloc is relatively straightforward to incorporate the additional allocation constraints. We briefly review the graph embedding method as follows. It is essentially a depthfirst search that looks at all possible node mappings and eliminate the choices based on feasibility of virtual links emanating from the node in consideration. Initially, all possible node mappings are generated and sorted in some order that optimize some objective such as minimize cost and fragmentation, while maximizing the allocation quality. The sorting and ordering of physical candidates is limited to the number of candidates configured by the InP to avoid looking too deep into a search tree. We refer the reader to Chapter 5 for further details. For our purpose of incorporating the additional placement constraints, a filtering step is added to the list of generated possible mappings.

From mapping to provisioning

The mapping provided by the allocation step is interpreted and instantiated using the HIPerNet framework1 . The HIPerNet framework combines system and networking virtualization technologies with bandwidth sharing and advance reservation mechanisms to offer dynamic networking and computing infrastructures as services [1] [16] [9].

The reliability mechanisms of HIPerNet presented in this work, are based on a modified version of Remus. To enable Remus protection, all VMs file-system were deployed on a Network File System (NFS) server. The first benchmarks performed with Remus demonstrated that communication between the NFS server (source) and virtual machines (destination) should be limited to a maximum transfer rate of 100 Mbps. Otherwise, Remus cannot keep a stable copy of the critical VM for the default checkpoint intervals of 200ms. In this work, the reliability mechanisms are applied to virtual nodes. The protection of network communication and data persistent on NFS are out of scope and they are not discussed.

Evaluation through a use case application

We now evaluated the reliability service by executing an existing large-scale distributed application, named Bronze Standard, for proof of concept purpose. The bronze standard [START_REF] Glatard | Performance evaluation of gridenabled registration algorithms using bronze-standards[END_REF] technique, described in Section 4.4.1 of Chapter 4, tackles the difficult problem of validating procedures for medical-image analysis.

The bronze standard application can be represented as a workflow of computational processes with I/O data dependencies, as illustrated in Figure 4.2. In the experiments reported below, this workflow is enacted with the data-intensive Grid-interfaced MOTEUR workflow manager [START_REF] Glatard | Flexible and efficient workflow deployement of data-intensive applications on grids with MOTEUR[END_REF]. A clinical database of 59 pairs of patient images to be registered by the different algorithms involved in the workflow is used. Each service depicted in Figure 4.2 is instantiated as an independent computing task that is delegated to one of the computing nodes. For each run, the processing of the complete image database results in the generation of 354 computing tasks (with a computation time of 30 seconds to 5 minutes each on a state-of-the-art PC). The data volume transferred for each task is in the order of 30 MB. The makespan of the application's execution is in the order of 20 minutes in the absence of failures.

The experiments are carried out using VIs managed by HIPerNet within the Grid'5000 testbed [START_REF] Cappello | Grid'5000: a large scale and highly reconfigurable grid experimental testbed[END_REF]. In our experiments, we use 100 physical nodes to compose a pool of virtualized physical resources. The number of physical nodes exceeds that of virtual resources specified (see next section) because virtual machines of the same application cannot be co-located in the same physical node to prevent correlated failures and additional virtual backup nodes are needed to protect the critical nodes.

Faults are simulated by shutting down physical machines respecting the MTBF parameter. The MTBF of each node in each experiment is 60000s, 30000s and 15000s. Assuming the largest makespan to be 30 minutes, the failure probability of each node is then 0.03, 0.06 and 0.12, respectively. The initial MTBF value (60000s) is based on failure rate of servers (with a probability between 0.02 and 0.04) identified by [START_REF] Atwood | White paper: Reducing Data Center Cost with an Air Economizer[END_REF]. The other lower MTBF values represent worse failure rates which could be attributed to a variety of reasons. Some examples are improper cooling in racks, irregular maintenance and inadequate protection from power interruptions.

VI composition

The VI specification to bronze standard is based on the results presented in Chapter 4, where 31 virtual resources are configured with 512 MB of RAM, and 1 GHz of CPU, and 10 Mbps of bandwidth requirement for each virtual link between the database and the workers. Virtual nodes require exclusivity on physical nodes. As shown in Figure 4.16, the HIPerNet engine deploys and manages virtual machines on these computers on demand (dark arrows).

The MOTEUR workflow engine, as a client of the HIPerNet framework, was hosted on one physical host outside the VI. MOTEUR produces VXDL descriptions including the reliability requirements that are requested to the HIPerNet engine (blue connection). After receiving all virtual machines allocated to the VI, MOTEUR connects to the computing nodes (worker nodes) to invoke the application services (red connections). The computing nodes connect to the database host to copy the input data and send the computational results, and the final results are sent to MOTEUR (green connections).

Cost model

From an infrastructure provider point of view, the major challenge is to account (financially or not) for resource usage according to specific criteria (e.g., fair share among users, digressive price, reliability level etc). Although a quasi-unlimited amount of computing resources may be allocated, a balance has to be found among i) the allocated infrastructure cost, ii) the expected performance, and iii) the optimal performance achievable, which depends on the level of parallelization of the application.

Considering this scenario, we introduce a simple cost model for the pricing of a VI with reliability support. The InP estimates the provisioning cost of an extended VI (already with backup resources identified). We consider different prices for active and backup resources.

Following the notation presented in Table 5.3 (Chapter 5), we define a price function Ψ R (Q R (r, t), t) which sets the price for an amount of resource r at time t. Similarly, Ψ L (Q L (l, t), t) would set a price for the bandwidth. The total price for the use of the resource is thus, over the lifetime [0, T ] of the virtual infrastructure G v :

P G (T ) = T 0 ( i∈R v Ψ R (Q R (r i , t), t) + j∈L v
Ψ L (Q L (l j , t), t)) dt (6.4) Introducing link and node redundancy to increase the reliability corresponds to an additive cost to the user which has to be evaluated. The cost function is extended to calculate the total price (P G (T )) for the extended graph (G v (R v , L v )), including reliable resources (R b , L b ). The price of reliability (P B ) of a virtual infrastructure is given by

P B (T ) = T 0 ( i∈R b Ψ R (Q R (r i , t), t) + j∈L b
Ψ L (Q L (l j , t), t)) dt (6.5) and the total price of a reliable virtual infrastructure is of course P G (T ) = P G (T ) + P B (T ).

For a first order assessment of the performance of our model, we consider a pricing model based on the published prices of Amazon EC2 [AMAa] for Europe. A detailed economic analysis is outside the scope of this document and we set Ψ R (Q R (r, t), t) to correspond to a fixed price per hour use for one of two types of nodes, and one of two types of contract: basic node (with 1.7 GB RAM) and high performance node (with 7.5 GB RAM); short term lease, and long term lease, respectively. Those prices are given in Table 6.1. EC2 does not charge any link cost in between nodes of its data center, and since the data transfers in our application can be fulfilled by typical ethernet links, we do not include any specific link pricing in our basic cost analysis. For EC2-like infrastructures, there is a cost and delay associated with uploading the medical images to process up to the data center over the Internet, however this is independent of the reliability and outside of the scope discussed here.

VM Specifications 1.7 GB RAM 7.5 GB RAM Short term lease $0.095 $0.38 Long term lease $0.031 $0.031 Table 6.1: Amazon EC2 Europe prices for VMs (per hour or part thereof).

We consider prices for the user, but an analysis of the costs to the provider would yield similar results. Our intent is to provide rough estimates to illustrate the trade-off between resource and reliability.

Experimental results

The application makespan when the application is executed on a substrate without simulated failures is 1205s ± 40s, serving as the baseline. For these values, the regular cost of this VI without reliability support is $2.95 (short term lease), serving as base cost for analysis.

The first experiment examines the protection of the database node. In this case, the database is the unique component protected, and faults are submitted in accordance with MTBF definition. Table 6.2 summarizes the execution of this scenario. The application makespan increases proportionally to the number of failures detected on the database node. Comparing with the baseline, the application makespan increases by +16%, +26% and +40% with regard to the MTBF values, 60000s, 30000s and 15000s, respectively.

In our experimental setup, we provided reliability by backing up the database 1:1, and the price for all values of the MTBF would be $3.04. However, while 1:1 replication made our proof-of-concept implementation feasible (the current Remus implementation for Xen 3.4 is limited to a 1:1 protection), it does not keep the required reliability at the specified level. To calculate the theoretical price of each VI with the proper reliability support, we compute the number of backup nodes required to provide the reliability level of 99.99% as a function of the MTBF, computed according to [START_REF] Yeow | Designing and Embedding Reliable Virtual Infrastructures[END_REF]. For this scenario, the cost of database protection with reliability level 99.99% increases the VI cost by about 6%, 10%, and 13% for MTBF 60000s, 30000s, and 15000s, respectively (see Table 6.4). If we assume that the backup nodes are selected by the InP from a pool of nodes reserved for this purpose with a long-term lease, then the price of reliability amounts to an increase of 2%, 3%, and 4% for MTBF 60000s, 30000s, and 15000s, respectively (again, see Table 6.4).

Each workflow service has a pre-and post-processing stage where the input data is copied to worker nodes and the results are sent to the database. The more failures happen during these two stages, the more the application makespan increases. In Table 6.3, we present the data transfer time (in seconds) of this scenario. The data transfer time increase dominates when there are more failures detected on database node.

The second experiment analyzes the protection of workers nodes. The MTBF varies according to the failure model presented above. After an MTBF, a random physical machine is crashed. The backup virtual machine is automatically started and continues running the same workflow task. As presented in Table 6.2, the application makespan slightly increases with regard to the number of failures detected on the infrastructure. The delay on the backup node activation is compensated by other parallel executions.

Providing reliability for workers nodes (99.9%) dramatically decreases the time to complete the application, from execution time for the 15000s MTBF of 1688s down to 1244s in Table 6.2, a gain of almost 40%. Table 6.5 shows the price increase due to reliability for the different values of the MTBF, assuming that the backup nodes are drawn from the same (short term lease) pool as the rest of the virtual infrastructure, or from a long term lease pool set aside by the InP.

In both cases, database protection and workers protection, the application ran normally, with faults being transparent to the application provider. We also performed the experiments using the task resubmission mechanism (application level) to compare with the VI reliability service. In general, after a failure occurs on a worker node, a new worker node must be provisioned, and the task executed on the failed node has to be relaunched on the new worker node. We minimize the activation time of a backup node to zero by reserving, deploying and configuring backup nodes prior to the execution of the Bronze Standard. Hence, the only difference from the previous experiments is the time needed to rework the tasks on the failed worker nodes.

Short term

The number of backup nodes for task resubmission mechanism is set to be the same as that in the previous scenario (5, 8, and 12 for MTBF of 60000s, 30000s, 15000s, respectively) so that the cost and amount of resources used are equivalent. Our experimental results show that the application makespan increases significantly in comparing with the virtual infrastructure reliability service, +13.08%, +19.67% and +22.19% with respect to 60000s, 30000s and 15000s of the MTBF, as presented in Table 6.6. The makespan gap would have been more if backup nodes were not pre-allocated and configured. We do not present results otherwise since the time required for reservation, deployment and configuration may vary with the configuration and total utilization of the Grid.

MTBF Reliability Resubmission

Conclusions

We have presented a mechanism that introduces transparent reliability support into virtualized infrastructures. The transparency allows virtual infrastructure users to focus on application development and scale reliability requirements at deployment. The InP can provide reliability as a service, and implement reliability transparently from the point of view of the service operator.

Our mechanism relies on VXDL for describing the reliability requirements in a flexible and expressive manner. These requirements are translated into the real number of backup nodes and links that must be provisioned for guaranteeing the reliability level. The allocation algorithm (an extended version of VXAlloc, discussed in Chapter 5) allocates the extended VI (original resources and replicas). During the execution time, a synchronization mechanism preserves virtual machine states in case of physical node failures. We implemented the mechanism on top of the HIPerNet framework, deployed over the Grid'5000 infrastructure, and demonstrated that it effectively supports reliability and enables the transparent execution of fault-sensitive distributed applications. In particular, our implementation reduces the completion time of the application under a slight increase of the resource cost.

Further work includes the implementation of a n : k reliability ratio within our testbed, in order to fully benefit from the virtualization of reliability. This also involves implementing the sharing of redundant nodes across different virtual infrastructures to minimize the number of such nodes, as described in Section 6.4. In [START_REF] Yeow | Highly Available Virtual Machines with Network Coding[END_REF], Wai-Leong Yeow et al. have started this work proposing some algorithms to implement n : k reliability based on routing and code construction, highlighting the conditions to support optimal rates for synchronization and recovery.

For the cost benefit, we presented a simple yet promising back-of-the-envelope analysis. We would like to refine the model to better distinguish the economical trade-offs for each of the stakeholders: service customer, service provider and virtual infrastructure provider, in particular when the virtual infrastructure is hosted across different administrative domains.

-SEVEN -Conclusions & Future work the dynamic provisioning of Virtual Infrastructures, we note that the way we use Internet resources is changing. The reservation and provisioning of on-demand resources is becoming a reality as we can currently share the available computing and communication resources guided by pay-as-you-go economic models. Frameworks, such as the HIPerNet, have been designed to manage distributed and virtualized substrates on top of which dynamic virtual infrastructures can be provisioned, paving the road toward control and management of such hybrid entities. As these advances are recent and users are still migrating their applications from traditional computing platforms to the Cloud, a number of obstacles have to be addressed to facilitate the process.

Initially, we observed that the existing tools for describing a compute-and-communicate graph (the virtual infrastructure) did not meet all expectations of infrastructure providers and application architects. To overcome this limitation, we have proposed and developed a language for modeling and describing virtual infrastructures, the VXDL. VXDL has shown its strong potential allowing the specification of complex virtual infrastructures in a user-oriented manner. Various software and projects have been adopting this language for representing virtual infrastructures in different scenarios. In addition, as of writing of this manuscript, an open forum for discussions and improvements is being launched (http: //www.vxdlforum.org/). This forum will allow developers and infrastructure providers to exchange experiences, suggestions, and extensions, guiding the standardization of VXDL.

Specifying VXDL files for complex distributed applications may be a difficult task. We developed a mechanism that automatically extracts information from workflow-based applications. Workflows are a representative way for describing the data and processes interaction (e.g., dependency and parallelism). Our mechanism combines information from the workflow with user's expertise, which comes from previous workflow executions or microbenchmarks. The mechanism has been validated by executing a large-scale distributed application were different virtual infrastructure compositions have been compared. In addition to highlighting the real importance of performing an efficient VI composition, the results demonstrated the expressiveness of VXDL, which enabled several specifications corresponding to different strategies.

VIs are comprehensive entities carrying substantial information (e.g., resource capacities varying with time, location dependency, user's expectations). Consequently, the process of allocating these entities is more complex (e.g., search space, multiple objectives, more constraints on nodes and links) than provisioning the network or set of nodes. We addressed these issues by developing an allocation mechanism, the VXAlloc, which has proven to be efficient as it balances both users' and InPs' perspectives. The innovations of this solution were patented by INRIA and LYaTiss.

One of the great advantages of the on-demand model explored by the Cloud is the provisioning of new services. An InP can develop internal mechanisms and commercialize them as new value-added services. Following this line, we proposed that reliability becomes a service. A user can express the reliability requirements of his application as well as any other configuration. The InP interprets these requirements and guarantees that a reliable virtual infrastructure is provisioned, keeping any substrate failures complete abstract to the user. The contributions of this thesis aimed at making the dynamic provisioning of virtual infrastructures an easier task. It is important to observe that all contributions are articulated around the VXDL language. The language was the enabler for the proposed contributions since: i) it is powerful enough for composing different specifications for an application; ii) it enables a user to interact with the management framework by defining specific allocation's constraints directly within the VI specification; and iii) it has an important participation in the reliability service provisioning, enabling users to define the required reliability level for individual components.

Perspectives for future work

During this thesis we defined and investigated the dynamic provisioning of virtual infrastructures. However, some questions remain open, pointing to future directions of research. We select a few for discussing:

Exploring the elastic aspect of virtual infrastructures: The performance of an application can vary during the execution time due to changes in workload (increase or decrease), request peaks, among other reasons [Andrzejak et al., 2006, Arnaud and[START_REF] Arnaud | [END_REF]. As VIs are malleable entities, they can be elastic for accommodating these dynamic variations. In this context, being elastic means to vary the capacity during execution (e.g., provision more bandwidth, memory, or even migrating a node close to user for decreasing the latency in communications).

We will concentrate on this important aspect of virtual infrastructures. As a continuation of the work performed in this thesis, the elasticity requirements (known in advance or on-demand) can be specified using VXDL. In addition, the allocation-problem was formulated with capacities specified as profiles (capacity per time), being capable of allocating elastic aspects known in advance. The allocation mechanism can be extended for adapting the dynamic variation that comes during the execution time.

Monitoring virtual infrastructures: For addressing the elastic aspects of a VI and for controlling the efficient usage of provisioned resources, a monitoring tool and a set of specific metrics should be investigated [START_REF] Lahmadi | Performance of Network and Service Monitoring Frameworks[END_REF]. The monitoring tools should consider sharing of resources between VIs. An InP should have knowledge about this information, following aggregated data, whereas a user should receive only information about his private resources [START_REF] Clayman | Monitoring service clouds in the future internet[END_REF].

Moreover, a monitoring tool (or even a service) should give combined information about application and VI performance. A change in application behavior (e.g., peak usage, performance, load) will reflect in a change in VI composition (e.g., bandwidth, memory, storage). The reverse scenario may also occur. Consequently, research is required for defining metrics and efficient tools for monitoring VIs. The contributions of this thesis are a starting point for developing these tools. Similarly to the reliability service, a monitoring service could be proposed, exploring VXDL as basis for formulating requirements and gathering measurement data.

A Mechanism Design Approach for allocating virtual infrastructures: The allocation of virtual infrastructures over distributed substrates may also address the economic aspects involved in dynamic provisioning. This problem can be modeled following a Mechanism Design Approach [START_REF] Nisan | Algorithmic Game Theory[END_REF], where users inform the requirements for composing their VIs while InPs expose their substrate composition and capacities. Then, an allocation mechanism solves the allocation problem among these participants, proposing payment values for users and provisioning costs for the InP. Users can evaluate the proposed solution based on a utility function used to identify if it is feasible. A similar approach can be followed for the InP, which would identify if the proposed solution meets its objectives.

These research lines can also explore VXDL for declaring VI's requirements, and extend the allocation-problem formulation addressed in this thesis.

-A -VXDL descriptions of Chapter 3 <?xml v e r s i o n=" 1 . 0 " e n c o d i n g="UTF-8"?> < d e s c r i p t i o n xmlns=" h t t p : / /www. e n s -l y o n . f r / LIP /RESO/ S o f t w a r e / v x d l " xmlns : x s i=" h t t p : / /www. w3 . o r g / 2 0 0 1 /XMLSchema-i n s t a n c e " x s i : s c h e m a L o c a t i o n=" h t t p : / /www. e n s -l y o n . f r / LIP /RESO/ S o f t w a r e / v x d l VXDL. x s d "> < v i r t u a l I n f r a s t r u c t u r e i d="VISUPIPE" owner="CARRIOCAS p r o j e c t "> <u s e r >k o s l o v s k i </u s e r > <s t a r t D a t e >2011-04-21T08 : 0 0 : 0 0 < / s t a r t D a t e > <t o t a l T i m e >PT11H</t o t a l T i m e > <vGroup i d=" S t o r a g e c l u s t e r " m u l t i p l i c i t y =" 20 "> <vNode i d=" n o d e s s t o r a g e c l u s t e r "> <s t o r a g e > < i n t e r v a l > <min>200</min> </ i n t e r v a l > <u n i t >GB</ u n i t > </ s t o r a g e > </vNode> </vGroup> <vGroup i d=" F i l t e r i n g c l u s t e r " m u l t i p l i c i t y =" 40 "> <vNode i d=" n o d e s f i l t e r i n g c l u s t e r "> <memory> < i n t e r v a l > <min>4</min> </ i n t e r v a l > <u n i t >GB</ u n i t > </memory> <cpu> <c o r e s >1</ c o r e s > <f r e q u e n c y > < i n t e r v a l > <min >2.0</min> </ i n t e r v a l > <u n i t >GHz</ u n i t > </ f r e q u e n c y > </cpu> </vNode> </vGroup> <vGroup i d=" Mapping c l u s t e r " m u l t i p l i c i t y =" 30 "> <vNode i d=" n o d e s mapping c l u s t e r "> <memory> < i n t e r v a l > <min>4</min> </ i n t e r v a l > <u n i t >GB</ u n i t > </memory> <cpu> <c o r e s >1</ c o r e s > <f r e q u e n c y > < i n t e r v a l > <min >2.0</min> </ i n t e r v a l > <u n i t >GHz</ u n i t > </ f r e q u e n c y > </cpu> <s t o r a g e > < i n t e r v a l > <min>80</min> </ i n t e r v a l > <u n i t >GB</ u n i t > </ s t o r a g e > </vNode> </vGroup> <vGroup i d=" R e n d e r i n g c l u s t e r " m u l t i p l i c i t y =" 10 "> <vNode i d=" n o d e s r e n d e r i n g c l u s t e r "> <memory> < i n t e r v a l > <min>8</min> </ i n t e r v a l > <u n i t >GB</ u n i t > </memory> <cpu> <c o r e s >1</ c o r e s > <f r e q u e n c y > < i n t e r v a l > <min >2.0</min> </ i n t e r v a l > <u n i t >GHz</ u n i t > </ f r e q u e n c y > </cpu> </vNode> </vGroup> <vGroup i d=" V i s u a l i z a t i o n c l u s t e r " m u l t i p l i c i t y =" 30 "> <vNode i d=" n o d e s v i s u a l i z a t i o n c l u s t e r "> < l o c a t i o n >l y o n . f r a n c e . eu</ l o c a t i o n > <d e v i c e s > v i s u a l i z a t i o n w a l l </ d e v i c e s > <memory> < i n t e r v a l > <min>8</min> </ i n t e r v a l > <u n i t >GB</ u n i t > </memory> <cpu> <c o r e s >1</ c o r e s > <f r e q u e n c y > < i n t e r v a l > <min >2.0</min> </ i n t e r v a l > <u n i t >GHz</ u n i t > </ f r e q u e n c y > </cpu> </vNode> </vGroup> <v L i n k i d=" l i n k 1 L a t e n c y 0 . 2 0 0 ms"> <l a t e n c y > < i n t e r v a l > <max>0.200 </max> </ i n t e r v a l > <u n i t >ms</ u n i t > </ l a t e n c y > <s o u r c e >S t o r a g e C l u s t e r </ s o u r c e > < d e s t i n a t i o n >S t o r a g e C l u s t e r </ d e s t i n a t i o n > </v L i n k> <v L i n k i d=" l i n k 2 L a t e n c y 0 . 2 0 0 ms"> <l a t e n c y > < i n t e r v a l > <max>0.200 </max> </ i n t e r v a l > <u n i t >ms</ u n i t > </ l a t e n c y > <s o u r c e >V i s u a l i z a t i o n C l u s t e r </ s o u r c e > < d e s t i n a t i o n > V i s u a l i z a t i o n C l u s t e r </ d e s t i n a t i o n > </v L i n k> <v L i n k i d=" l i n k L a t e n c y 0 . 4 0 0 ms"> <l a t e n c y > < i n t e r v a l > <max>0.400 </max> </ i n t e r v a l > <u n i t >ms</ u n i t > </ l a t e n c y > <bandwidth> <f o r w a r d > < i n t e r v a l > <min >10.0 </min> </ i n t e r v a l > <u n i t >Mbps</ u n i t > </f o r w a r d > </bandwidth> <s o u r c e >F i l t e r i n g C l u s t e r </ s o u r c e > < d e s t i n a t i o n >F i l t e r i n g C l u s t e r </ d e s t i n a t i o n > </v L i n k> <v L i n k i d=" l i n k L a t e n c y 0 . 1 5 0 ms"> <l a t e n c y > < i n t e r v a l > <max>0.150 </max> </ i n t e r v a l > <u n i t >ms</ u n i t > </ l a t e n c y > <s o u r c e >R e n d e r i n g C l u s t e r </ s o u r c e > < d e s t i n a t i o n > R e n d e r i n g C l u s t e r </ d e s t i n a t i o n > </v L i n k> <v L i n k i d=" h i g h c a p a c i t y l i n k 1 "> <bandwidth> <f o r w a r d > < i n t e r v a l > <min >38.4 </min> </ i n t e r v a l > <u n i t >Gbps</ u n i t > </f o r w a r d > </bandwidth> <s o u r c e >S t o r a g e C l u s t e r </ s o u r c e > < d e s t i n a t i o n >F i l t e r i n g C l u s t e r </ d e s t i n a t i o n > </v L i n k> <v L i n k i d=" h i g h c a p a c i t y l i n k 2 "> <bandwidth> <f o r w a r d > < i n t e r v a l > <min >38.4 </min> </ i n t e r v a l > <u n i t >Gbps</ u n i t > </f o r w a r d > </bandwidth> <s o u r c e >F i l t e r i n g C l u s t e r </ s o u r c e > < d e s t i n a t i o n >Mapping C l u s t e r </ d e s t i n a t i o n > </v L i n k> <v L i n k i d=" h i g h c a p a c i t y l i n k 3 "> <bandwidth> <f o r w a r d > < i n t e r v a l > <min >38.4 </min> </ i n t e r v a l > <u n i t >Gbps</ u n i t > </f o r w a r d > </bandwidth> <s o u r c e >Mapping C l u s t e r </ s o u r c e > < d e s t i n a t i o n > R e n d e r i n g C l u s t e r </ d e s t i n a t i o n > </v L i n k> <v L i n k i d=" h i g h c a p a c i t y l i n k 4 "> <bandwidth> <f o r w a r d > < i n t e r v a l > <min >38.4 </min> </ i n t e r v a l > <u n i t >Gbps</ u n i t > </f o r w a r d > </bandwidth> <s o u r c e >R e n d e r i n g C l u s t e r </ s o u r c e > < d e s t i n a t i o n >V i s u a l i z a t i o n C l u s t e r </ d e s t i n a t i o n > </v L i n k> < v i r t u a l T i m e l i n e i d="VISUPIPE t i m e l i n e "> < t i m e l i n e i d=" d a t a t r a n s f e r 1 "> <a c t i v a t e >S t o r a g e C l u s t e r </ a c t i v a t e > <a c t i v a t e >F i l t e r i n g C l u s t e r </ a c t i v a t e > <a c t i v a t e >h i g h c a p a c i t y l i n k 1</ a c t i v a t e > <t o t a l T i m e >PT1H</t o t a l T i m e > </ t i m e l i n e > < t i m e l i n e i d=" F i l t e r i n g s t a g e "> < a f t e r >d a t a t r a n s f e r 1</ a f t e r > <a c t i v a t e >F i l t e r i n g C l u s t e r </ a c t i v a t e > <t o t a l T i m e >PT2H</t o t a l T i m e > </ t i m e l i n e > < t i m e l i n e i d=" d a t a t r a n s f e r 2 "> < a f t e r >F i l t e r i n g s t a g e </ a f t e r > <a c t i v a t e >F i l t e r i n g C l u s t e r </ a c t i v a t e > <a c t i v a t e >Mapping C l u s t e r </ a c t i v a t e > <a c t i v a t e >h i g h c a p a c i t y l i n k 2</ a c t i v a t e > <t o t a l T i m e >PT1H</t o t a l T i m e > </ t i m e l i n e > < t i m e l i n e i d=" Mapping s t a g e "> < a f t e r >d a t a t r a n s f e r 2</ a f t e r > <a c t i v a t e >Mapping C l u s t e r </ a c t i v a t e > <t o t a l T i m e >PT1H</t o t a l T i m e > </ t i m e l i n e >

3. 1

 1 The positioning of VXDL considering the service models offered by Cloud Computing providers. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Specification of the VXDL grammar (version 2.7) using EBNF (part 1 of 2). 3.3 Specification of the VXDL grammar (version 2.7) using EBNF (part 2 of 2). 3.4 The conceptual VXDL file structure (version 2.7). . . . . . . . . . . . . . . 3.5 UML specification of VXDL (version 2.7). . . . . . . . . . . . . . . . . . . . 3.6 Examples of network topologies used to interconnect virtual resources. . . . 3.7 Description of a ring topology using VXDL. . . . . . . . . . . . . . . . . . . 3.8 Internal timeline of a Virtual Infrastructure. Three distinct stages are identified: i) data transfer, ii) data computation, and iii) visualization of resulting data. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.9 Description of 2 vNodes interconnected by a vLink using the VXDL. . . . . 3.10 Example of a VXDL description used to inform the configuration provisioned by the management framework according to the request in Figure 3.9. 3.11 Example of a multiuser game server connected to a set of remote clients. . . 3.12 VXDL description for the initial VI configuration of the multiuser game service example. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.13 VXDL description of a client request for the multiuser game service example. 3.14 Example of clients provisioning for the multiuser game service use case. . . 3.15 Execution pipeline of the High Performance Collaborative Remove Visualization (VISUPIPE) application. . . . . . . . . . . . . . . . . . . . . . . . . 4.1 Positioning of the specification strategies and VXDL considering the module models offered by Cloud Computing providers. . . . . . . . . . . . . . . . . 60 4.2 Bronze Standard's workflow. . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 4.3 Description of workflow tasks using the GWENDIA language. This figure presents a few processors (or data production unit) and their interaction using input/output ports. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 4.4 Example of a workflow's task interconnections (data links) using the GWEN-DIA language. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 4.5 Description of a permanent database node using the VXDL language. . . . 65 4.6 Estimation of the execution time and total cost with regard to the bandwidth of the FIFO strategy. . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 4.7 DAG jobs of Bronze Standard application for n inputs. . . . . . . . . . . . . 67 4.8 Timeline description for the optimized strategy. . . . . . . . . . . . . . . . . 68 4.9 Modules grouping without parallelism loss. . . . . . . . . . . . . . . . . . . 69 4.10 Grouping CrestMatch, PFMatchICP, Yasmina and Baladin modules. . . . . 69 4.11 Description of a vNode and a computing cluster required to execute the Bronze Standard application. . . . . . . . . . . . . . . . . . . . . . . . . . . 71 4.12 A VI composition for executing the Bronze Standard's workflow. . . . . . . 72 4.13 VXDL description of the communication-intensive virtual links ofFigure 4.12. 73 4.14 Allocations of descriptions VI-1 and VI-2. . . . . . . . . . . . . . . . . . . . 74 4.15 Architecture of Grid'5000: 9 sites interconnected by 10 Gbps dedicated lambda paths (figure courtesy of the Grid'5000 community [GRI]). . . . . . 75 4.16 Experimental infrastructure used to compare the different strategies to compose VIs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 4.17 Virtual Infrastructure composition considering the naive strategy. . . . . . . 80 4.18 Virtual Infrastructure composition considering the FIFO strategy. . . . . . 80 4.19 Task schedule with the naive strategy. . . . . . . . . . . . . . . . . . . . . . 80 4.20 Task schedule with the FIFO strategy. . . . . . . . . . . . . . . . . . . . . . 81 4.21 Virtual Infrastructure composition considering the optimized strategy without grouping modules. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 4.22 Virtual Infrastructure composition considering the optimized strategy with grouping modules. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 4.23 Task schedule with optimized modules grouping. . . . . . . . . . . . . . . . 83 5.1 Positioning of a mechanism for allocating VIs specified with VXDL, considering the service models offered by Cloud Computing providers. . . . . . 86 5.2 Example of two virtual infrastructures (VI A and VI B ) using graphs. . . . 87 5.3 The representation of a physical substrate, and an example of a map solution between the VIs presented in Figure 5.2 and the physical substrate. . . . . . 88 5.4 Illustration of a vLink decomposition using extension, splitting, and vRouters. User layer represents the components exposed to users; Abstract layer remains transparent, being controlled by the InP to guarantee the users' requirements; and Physical layer represents the materialized resources that compose the distributed physical substrate. . . . . . . . . . . . . . . . . . . 93 5.5 A VI composed of resources r v A, r v B and r v C is requested by a user with access point located at lyon.fr.eu. . . . . . . . . . . . . . . . . . . . . . . . . 97 x c Copyright 2011 by Guilherme Piêgas Koslovski

  as exemplified by 5.7c. . . 101 5.8 Fragmentation of a small-size physical substrate. The number of sources requesting VIs is 1 and 3. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 5.9 Fragmentation of a medium-size physical substrate. The number of sources requesting VIs is 1 and 3. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 5.10 InP cost of allocations on a small-size physical substrate. The number of sources requesting VIs is 1 and 3. . . . . . . . . . . . . . . . . . . . . . . . . 105 5.11 InP cost of allocations on a medium-size physical substrate. The number of sources requesting VIs is 1 and 3. . . . . . . . . . . . . . . . . . . . . . . 106 5.12 Aggregated distance of VI components allocated on a small-size physical substrate. The number of sources requesting VIs is 1 and 3. . . . . . . . . . 106 5.13 Aggregated distance of VI components allocated on a medium-size physical substrate. The number of sources requesting VIs is 1 and 3. . . . . . . . . . 107 5.14 A comparison of wasted capacity between a non-sharing scenario and one virtualized, allocated using VXAlloc. . . . . . . . . . . . . . . . . . . . . . . 108 5.15 A comparison of the acceptance ratio between a non-sharing scenario and one virtualized, allocated using VXAlloc. . . . . . . . . . . . . . . . . . . . 108 6.1 The integration of reliability service from the user specification to the VI allocation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 6.2 Part of a VXDL file exemplifying the the description of reliable virtual resources: a group of critical resources requires a reliability level of 99.9%. . 115 6.3 The figures show the steps (from left to right) as each backup node is added to the original VI for reliability. Nodes r v 1 and r v 2 are critical nodes, and nodes r v A and r v B are backup nodes. Backup links are used for synchronization (in dotted lines), and the respective attributes are determined by the existing links in the original VI. . . . . . . . . . . . . . . . . . . . . . . 118 6.4 Example of embedding a graph in Figure 6.3b onto a physical substrate represented by (a), respecting the reliability constraints: original and backup nodes are not placed in the same physical resource. . . . . . . . . . . . . . . 119 A.1 VXDL description for the VISUPIPE example (part 1 of 4). . . . . . . . . . 131 A.2 VXDL description for the VISUPIPE example (part 2 of 4). . . . . . . . . . 132 A.3 VXDL description for the VISUPIPE example (part 3 of 4). . . . . . . . . . 133 A.4 VXDL description for the VISUPIPE example (part 4 of 4). . . . . . . . . . 134 c Copyright 2011 by Guilherme Piêgas Koslovski xi List of Tables 2.1 Summary of virtualization categories including their main technologies, advantages and drawbacks. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1 A comparison among some resource description languages focused on virtual infrastructure specification. √ identifies the presence of an attribute. VXDL, described in Section 3.3, fulfills all the VI requirements. . . . . . . . 4.1 Notations used in the cost function model. . . . . . . . . . . . . . . . . . . . 4.2 Benchmarks of the Bronze Standard's modules: execution time, data input and produced data volumes. . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Average execution time (in seconds) on VI 2 -Allocation III and VI 2 -Allocation IV. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4 Data transfer time (in seconds) on the local VI 2 -Allocation IV and large scale distributed VI 1 -Allocation II. . . . . . . . . . . . . . . . . . . . . . . 4.5 Performance comparison among the four strategies. . . . . . . . . . . . . . . 4.6 Evaluation of the bandwidth control mechanism. . . . . . . . . . . . . . . . 5.1 Map of the allocation solution presented in Figure 6.4 using tuples in the format < virtual resource, physical resource, capacity, ∆t >. . . . . . . . . . 5.2 A list of selected proposals developed to allocate virtual resources and their particularities: implementation scenario, reconfigurability, type of requests, and problem formulation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3 Notations used to formulate the allocation problem. . . . . . . . . . . . . . 6.1 Amazon EC2 Europe prices for VMs (per hour or part thereof). . . . . . . . 6.2 Execution time and % increase over baseline for critical database protection only (column DB), and for computing nodes protection (column CN). . . . 6.3 Total data transfer time of application services running with critical database protection scenario. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.4 Price with reliability for database protection (reliability level 99.9%) and fraction of price corresponding to reliability with backup provisioned on short term leases or long term leases. . . . . . . . . . . . . . . . . . . . . . . 6.5 Price of reliability for computing node protection (reliability level 99.9%) and fraction of price corresponding to reliability with backup provisioned on short term leases or long term leases. . . . . . . . . . . . . . . . . . . . . 6.6 Application makespan with task resubmission mechanism and percentage increased when compared with VI reliability service. . . . . . . . . . . . . .

Figure 1 . 1 :

 11 Figure 1.1: A user requesting a set of compute-and-communication resources for executing his application.

Figure 1 . 2 :

 12 Figure 1.2: The organization of chapters and contributions.

  .1. Costumer Edges are the source and target border nodes. Provider Edges and P routers are part of the SPs network. PEs are directly connected to the CEs, and P routers are used to interconnect the PEs.

Figure 2 . 1 :

 21 Figure 2.1: Representation of basic VPN components. Customer Edges (CE) are located at Customer Site. Provider Edge routers (PE) and P routers are part of Service Provider (SP) network.

Figure 2 .

 2 3 shows an example of a scenario composed of a Private Cloud, two Public Clouds (A and B), and two hybrid Clouds (A and B). The following sections detail these types of Clouds.

Figure 2 . 3 :

 23 Figure 2.3: A common classification defining three types of Clouds: Private Clouds, Public Clouds, and Hybrid Clouds.

Figure 2 .

 2 3 details the composition of Hybrid Clouds, where a subset of resources from Public Cloud A is combined with internal resources of the Private Cloud, creating the Hybrid Cloud A. Resources are interconnected by a communication channel established over the Internet. The Hybrid Cloud B is similarly composed using the on-demand resources of Public Cloud B.

Figure 2 . 4 :

 24 Figure 2.4: The service models offered by Cloud Computing providers in 2011.

Figure 2 . 5 :

 25 Figure 2.5: Example of Cloud Networking provisioning between a Private Cloud and a Public Cloud (example discussed in the context of SAIL project [SAI]).

Figure 2 . 6 :

 26 Figure 2.6: Two VIs are sharing a distributed and virtualized physical substrate.

Figure 2 . 7 :

 27 Figure 2.7: Example of a VI composition using a graph notation. The virtual IT resources are the vertices and the virtual links the edges.

Figure 2 . 8 :

 28 Figure 2.8: Dimensions that should be considered during a VI provisioning.

Figure 2 . 9 :

 29 Figure 2.9: Dynamic provisioning of VIs with the HIPerNet framework.

  VI scenarios with VXDL

Figure 3 . 1 :

 31 Figure 3.1: The positioning of VXDL considering the service models offered by Cloud Computing providers.

Figure 3 . 3 :

 33 Figure 3.3: Specification of the VXDL grammar (version 2.7) using EBNF (part 2 of 2).

Figure 3 . 4 :

 34 Figure 3.4: The conceptual VXDL file structure (version 2.7).

Figure 3 . 5 :

 35 Figure 3.5: UML specification of VXDL (version 2.7).

Figure 3 . 6 :

 36 Figure 3.6: Examples of network topologies used to interconnect virtual resources.

<

  ?xml v e r s i o n=" 1 . 0 " e n c o d i n g="UTF-8"?> < d e s c r i p t i o n xmlns=" h t t p : / /www. e n s -l y o n . f r / LIP /RESO/ S o f t w a r e / v x d l " xmlns : x s i=" h t t p : / /www. w3 . o r g / 2 0 0 1 /XMLSchema-i n s t a n c e " x s i : s c h e m a L o c a t i o n=" h t t p : / /www. e n s -l y o n . f r / LIP /RESO/ S o f t w a r e / v x d l VXDL. x s d "> < v i r t u a l I n f r a s t r u c t u r e i d="my VPXI" owner=" k o s l o v s k i "> <u s e r >g u i l h e r m e k o s l o v s k i </u s e r > <s t a r t D a t e >2011-09-21T08 : 0 0 : 0 0 < / s t a r t D a t e > <t o t a l T i m e >PT3H</t o t a l T i m e > <v L i n k i d=" v i r t u a l l i n k 1 "> <bandwidth> <f o r w a r d > <s i m p l e >25.0 </ s i m p l e > <u n i t >Mbps</ u n i t > </f o r w a r d > </bandwidth> <s o u r c e >r v 1</ s o u r c e > < d e s t i n a t i o n >r v 2</ d e s c r i p

  r t u a l l i n k 4 "> <bandwidth> <f o r w a r d > <s i m p l e >25.0 </ s i m p l e > <u n i t >Mbps</ u n i t > </f o r w a r d > </bandwidth> <s o u r c e >r v 4</ s o u r c e > < d e s t i n a t i o n >r v 5</ d e s c r i p t i o n > </v L i n k> <v L i n k i d=" v i r t u a l l i n k 5 "> <bandwidth> <f o r w a r d > <s i m p l e >25.0 </ s i m p l e > <u n i t >Mbps</ u n i t > </f o r w a r d > </bandwidth> <s o u r c e >r v 5</ s o u r c e > < d e s t i n a t i o n >r v 6</ d e s c r i p

Figure 3 . 7 :

 37 Figure 3.7: Description of a ring topology using VXDL.

Figure 3 . 8 :

 38 Figure 3.8: Internal timeline of a Virtual Infrastructure. Three distinct stages are identified: i) data transfer, ii) data computation, and iii) visualization of resulting data.

<

  ?xml v e r s i o n=" 1 . 0 " e n c o d i n g="UTF-8"?> < d e s c r i p t i o n xmlns=" h t t p : / /www. e n s -l y o n . f r / LIP /RESO/ S o f t w a r e / v x d l " xmlns : x s i=" h t t p : / /www. w3 . o r g / 2 0 0 1 /XMLSchema-i n s t a n c e " x s i : s c h e m a L o c a t i o n=" h t t p : / /www. e n s -l y o n . f r / LIP /RESO/ S o f t w a r e / v x d l VXDL. x s d "> < v i r t u a l I n f r a s t r u c t u r e i d=" e x a m p l e 1 " owner=" k o s l o v s k i "> <u s e r >g u i l h e r m e k o s l o v s k i </u s e r > <s t a r t D a t e >2011-04-21T08 : 0 0 : 0 0 < / s t a r t D a t e > <t o t a l T i m e >PT4H</t o t a l T i m e > <m o n i t o r i n g >g o l d </ m o n i t o r i n g > <vNode i d=" node 1 "> <cpu> <c o r e s >1</ c o r e s >

Figure 3 . 9 :Figure 3 . 10 :

 39310 Figure 3.9: Description of 2 vNodes interconnected by a vLink using the VXDL.

Figure 3 . 11 :

 311 Figure 3.11: Example of a multiuser game server connected to a set of remote clients.

Figure 3 . 12 :

 312 Figure 3.12: VXDL description for the initial VI configuration of the multiuser game service example.

Figure 3 . 14 :

 314 Figure 3.14: Example of clients provisioning for the multiuser game service use case.

Figure 3 . 15 :

 315 Figure 3.15: Execution pipeline of the High Performance Collaborative Remove Visualization (VISUPIPE) application.

Figures A. 1 ,

 1 Figures A.1, A.2, A.3, and A.4 of Appendix A present a VXDL specification for the VISUPIPE example. This VXDL file describes the five clusters and all network links required to execute VISUPIPE. Particularly, Figure A.3 shows the timeline composition of this scenario. The computing and data transfer stages are defined in advance (before the start of the application's execution). Each timeline (or stage) has a specific duration and begins after the end of the previous timeline.

Figure 4 .

 4 1 positions the contribution of this chapter considering the modular models offered by Cloud Computing providers. The proposed strategies translate an application description (e.g., computing nodes, middleware, framework) into VXDL files.

Figure 4 . 1 :

 41 Figure 4.1: Positioning of the specification strategies and VXDL considering the module models offered by Cloud Computing providers.

Figure 4 . 2 :

 42 Figure 4.2: Bronze Standard's workflow.

Figure 4 . 4 :

 44 Figure 4.4: Example of a workflow's task interconnections (data links) using the GWEN-DIA language.

Figure 4 . 5 :

 45 Figure 4.5: Description of a permanent database node using the VXDL language.

Figure 4 .

 4 Figure 4.2 the data modules (represented in blue) are used by different computing modules and must be available during the entire workflow execution. The computing modules, on the other hand, are only used at determined moments.The permanent part also comprises the dedicated nodes hosting middleware, framework, and database required for running the application. Figure.4.5 presents a partial VXDL description of permanent resources, where a simple database node is described to store the data presented in Figure4.2.The variable part of a VI description depends directly on the information extracted from the workflow, such as input data, the number of modules, and the links between the modules. In addition, the virtual network topology is directly related to the variable part composition. The more dependence exists between workflow modules, the more complicated is the network topology.

Figure 4 . 6 :

 46 Figure 4.6: Estimation of the execution time and total cost with regard to the bandwidth of the FIFO strategy.

Figure 4 . 7 :

 47 Figure 4.7: DAG jobs of Bronze Standard application for n inputs.

4. 3 .

 3 STRATEGIES TO TRANSLATE WORKFLOWS INTO VXDL CHAPTER 4. SPEC. VIS FOR EXEC. DISTRIB. APPS.

Figure 4 . 8 :

 48 Figure 4.8: Timeline description for the optimized strategy.

Figure 4 .

 4 10 shows the best solution for the workflow example presented in Figure 4.2. Resulting execution DAG considering n input data items

Figure 4 . 9 :Figure 4 . 10 :

 49410 Figure 4.9: Modules grouping without parallelism loss.

Figure 4 . 11 :

 411 Figure 4.11: Description of a vNode and a computing cluster required to execute the Bronze Standard application.

Figure 4 .

 4 Figure 4.12: A VI composition for executing the Bronze Standard's workflow.

Figure 4 . 13 :

 413 Figure 4.13: VXDL description of the communication-intensive virtual links of Figure 4.12.

Figure 4 . 14 :

 414 Figure 4.14: Allocations of descriptions VI-1 and VI-2.

Figure 4 . 15 :

 415 Figure 4.15: Architecture of Grid'5000: 9 sites interconnected by 10 Gbps dedicated lambda paths (figure courtesy of the Grid'5000 community [GRI]).

Figure 4 . 16 :

 416 Figure 4.16: Experimental infrastructure used to compare the different strategies to compose VIs.

Figure 4 .

 4 Figure 4.17: Virtual Infrastructure composition considering the naive strategy.

Figure 4 .

 4 Figure 4.18: Virtual Infrastructure composition considering the FIFO strategy.

Figure 4 .

 4 Figure 4.19: Task schedule with the naive strategy.

Figure 4 .

 4 Figure 4.20: Task schedule with the FIFO strategy.

Figure 4 .

 4 Figure 4.21: Virtual Infrastructure composition considering the optimized strategy without grouping modules.

Figure 4 .

 4 Figure 4.22: Virtual Infrastructure composition considering the optimized strategy with grouping modules.

Figure 4 .

 4 Figure 4.23: Task schedule with optimized modules grouping.

Figure 5 . 1 :

 51 Figure 5.1: Positioning of a mechanism for allocating VIs specified with VXDL, considering the service models offered by Cloud Computing providers.

Figure 5 . 2 :

 52 Figure 5.2: Example of two virtual infrastructures (VI A and VI B ) using graphs.

Figure 5 . 3 :

 53 Figure 5.3: The representation of a physical substrate, and an example of a map solution between the VIs presented in Figure 5.2 and the physical substrate.

Figure 5 . 4 :

 54 Figure 5.4: Illustration of a vLink decomposition using extension, splitting, and vRouters. User layer represents the components exposed to users; Abstract layer remains transparent, being controlled by the InP to guarantee the users' requirements; and Physical layer represents the materialized resources that compose the distributed physical substrate.

Figure 5 . 5 :

 55 Figure 5.5: A VI composed of resources r v A, r v B and r v C is requested by a user with access point located at lyon.fr.eu.

Figure 5 . 6 :

 56 Figure 5.6: The physical substrate that must allocate the VI described in Figure 5.5 comprises components hierarchically distributed and interconnected.

CHAPTER 5 .

 5 ALLOCATING RESOURCES TO VIRTUAL INFRASTRUCTURES 5.4. A HEURISTIC FOR ALLOCATING VIS (a) graph G v (R v , L v ). (b) graph G p (R p , L p ). (c) Subgraph isomorphism between graphs G v and G p .

Figure 5 . 7 :

 57 Figure 5.7: A subgraph-isomorphism mapping between G v (5.7a) and G p (5.7b) given by the application of a function f , where f(r v A) = r p 3, f (r v B) = r p 2, f (r v C) = r p 6, f (l v A) = l p 2, f (l v B) = l p 3 ∪ l p 5, f (l v C) = l p 6,as exemplified by 5.7c.

Figure 5 . 8 :

 58 Figure 5.8: Fragmentation of a small-size physical substrate. The number of sources requesting VIs is 1 and 3.

Figure 5 . 9 :

 59 Figure 5.9: Fragmentation of a medium-size physical substrate. The number of sources requesting VIs is 1 and 3.

Figure 5 . 10 :

 510 Figure 5.10: InP cost of allocations on a small-size physical substrate. The number of sources requesting VIs is 1 and 3.

Figure 5 . 11 :

 511 Figure 5.11: InP cost of allocations on a medium-size physical substrate. The number of sources requesting VIs is 1 and 3.

Figure 5 . 12 :

 512 Figure 5.12: Aggregated distance of VI components allocated on a small-size physical substrate. The number of sources requesting VIs is 1 and 3.

Figure 5 . 13 :

 513 Figure 5.13: Aggregated distance of VI components allocated on a medium-size physical substrate. The number of sources requesting VIs is 1 and 3.

Figure 5 .

 5 Figure 5.14: A comparison of wasted capacity between a non-sharing scenario and one virtualized, allocated using VXAlloc.

Figure 5 .

 5 Figure 5.15: A comparison of the acceptance ratio between a non-sharing scenario and one virtualized, allocated using VXAlloc.

Figure 6 . 1 :

 61 Figure 6.1: The integration of reliability service from the user specification to the VI allocation.

Figure 6 . 2 :

 62 Figure 6.2: Part of a VXDL file exemplifying the the description of reliable virtual resources: a group of critical resources requires a reliability level of 99.9%.

Algorithm 6 . 1 : 1 C 2 L 11 Figure 6 .

 6112116 Figure 6.3 shows an example of how backup links are generated. Nodes r v 1 and r v 2 request a backup node each one, identified as r v A and r v B, respectively. A new link between a backup node and some other node is created if it is a neighbor of a critical node. Hence, in Figure6.3b, node r v A connects to all three nodes. Furthermore, the attributes of link (r v A, r v 3) can function as links (r v 1, r v 3) or (r v 2, r v 3). Links (r v A, r v 1) and (r v A, r v 2) are reused for synchronization. With one more backup node (as in Figure6.3c), the firstorder backup links of node r v B are the same as those of node r v A, and with a second-order backup link between node r v A and r v B to function as the link (r v 1, r v 2) when both critical nodes fail.

Figure 6 . 3 :

 63 Figure 6.3: The figures show the steps (from left to right) as each backup node is added to the original VI for reliability. Nodes r v 1 and r v 2 are critical nodes, and nodes r v A and r v B are backup nodes. Backup links are used for synchronization (in dotted lines), and the respective attributes are determined by the existing links in the original VI.

  (a) Physical substrate. (b) Embedded Graph.

Figure 6 . 4 :

 64 Figure 6.4: Example of embedding a graph in Figure 6.3b onto a physical substrate represented by (a), respecting the reliability constraints: original and backup nodes are not placed in the same physical resource.

7. 1

 1 ConclusionsReviewing the advances in virtualization techniques, Cloud Computing, and especially

Figure A. 1 :

 1 Figure A.1: VXDL description for the VISUPIPE example (part 1 of 4).

Figure A. 2 :

 2 Figure A.2: VXDL description for the VISUPIPE example (part 2 of 4).

Figure A. 3 :

 3 Figure A.3: VXDL description for the VISUPIPE example (part 3 of 4).

  1.1 A user requesting a set of compute-and-communication resources for executing his application. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 The organization of chapters and contributions. . . . . . . . . . . . . . . . . 2.1 Representation of basic VPN components. Customer Edges (CE) are located at Customer Site. Provider Edge routers (PE) and P routers are part of Service Provider (SP) network. . . . . . . . . . . . . . . . . . . . . . . . . 2.2 A network and IT resources timeline comprising the main technologies, projects, and software explored for virtualization. . . . . . . . . . . . . . . . 2.3 A common classification defining three types of Clouds: Private Clouds, Public Clouds, and Hybrid Clouds. . . . . . . . . . . . . . . . . . . . . . . . 2.4 The service models offered by Cloud Computing providers in 2011. . . . . . 2.5 Example of Cloud Networking provisioning between a Private Cloud and a Public Cloud (example discussed in the context of SAIL project [SAI]). . . 2.6 Two VIs are sharing a distributed and virtualized physical substrate. . . . . 2.7 Example of a VI composition using a graph notation. The virtual IT resources are the vertices and the virtual links the edges. . . . . . . . . . . . . 2.8 Dimensions that should be considered during a VI provisioning. . . . . . . . 2.9 Dynamic provisioning of VIs with the HIPerNet framework. . . . . . . . . .

Table 2 .

 2

1: Summary of virtualization categories including their main technologies, advantages and drawbacks.

  Figure 3.2: Specification of the VXDL grammar (version 2.7) using EBNF (part 1 of 2).

	VXDL = '<virtualInfrastructure>', owner, {user}, [extension], common,
	{vNode | vRouter | vAccessPoint | vStorage | vLink | vGroup},
	[virtualTimeline], sharedRiskGroup, '</virtualInfrastructure>';
	common = id, [startDate], [totalTime], [reliability], [location], [security], [monitoring],
	[monitoringURL];
	id = '<id>', string, '</id>';
	startDate = '<startDate>', date, time, '</startDate>';
	totalTime = '<totalTime>', time, '</totalTime>'; vLink = '<vLink>', vResource, source, destination, [latency], [bandwidth], '</vLink>';
	owner = '<owner>', string, '</owner>'; source = '<source>', string, '</source>';
	user = '<user>', string, '</user>'; destination = '<destination>', string, '</destination>';
	extension = '<extension>', boolean, '</extension>'; bandwidth = '<bandwidth>', forward, [reverse], '</bandwidth>';
	reliability = '<reliability>', string, '</reliability>'; forward = '<forward>', (doubleInterval | doubleSet | doubleSimple), bandwidthUnit,
	security = '<security>', string, '</security>'; '</forward>';
	monitoring = '<monitoring>', string, '</monitoring>'; reverse = '<reverse>', (doubleInterval | doubleSet | doubleSimple), bandwidthUnit,
	monitoringURL = '<monitoringURL>', string, '</monitoringURL>'; '</reverse>';
	location = '<location>', string, '</location>'; latency = '<latency>', (doubleInterval | doubleSet | doubleSimple), latencyUnit,
	'</latency>';
	vAccessPoint |
	vStorage | vLink}, '</vGroup>';
	multiplicity = '<multiplicity>', integer, '</multiplicity>';
	virtualTimeline = '<virtualTimeline>', id, {timeline}, '</virtualTimeline>';
	timeline = '<timeline>
	frequencyUnit,
	'</frequency>';
	cores = '<cores>', integer, '</cores>';
	architecture = '<architecture>', string, '</architecture>';
	storage = '<storage>', (longInterval | longSet | longSimple), memoryUnit, '</storage>';
	vStorage = '<vStorage>', vResource, type, [volume], [imageURL], [ip], '</vStorage>';
	type = '<type>', 'NAS' | 'DAS' | 'SAN', '</type>';
	volume = '<volume>', string, '</volume>';
	vAccessPoint = '<vAccessPoint>', vResource, [ip], {loadBalancer | nat | masquerade},
	'</vAccessPoint>';
	loadBalancer = '<loadBalancer>', {inEndpoint}, {publicIP}, '</loadBalancer>';
	inEndpoint = '<inEndpoint>', string, '</inEndpoint>';
	publicIP = '<publicIP>', ip, '</publicIP>';
	nat = '<nat>', [inEndpoint], [inPort], protocol, [publicIP], [outPort], '</nat>';
	inEndpoint = '<inEndpoint>', string, '</inEndpoint>';
	inPort = '<inPort>', long, '</inPort>';
	outPort = '<outPort>', long, '</outPort>';
	protocol = '<protocol>', string, '</protocol>';
	masquerade = '<masquerade>', {inEndpoint}, publicIP, '</masquerade>';

sharedRiskGroup = '<sharedRiskGroup>', id, resources, '</sharedRiskGroup>'; resources = '<resources>', {id}, '</resources>

'; vResource = common, [model]

, [exclusivity], [tags]; model = '<model>', string, '</model>'; exclusivity = '<exclusivity>', boolean, '</exclusivity>'; tags = '<tags>', {key, value}, '</tags>'; key = '<key>', string, '</key>'; value = '<value>', string, '</value>'; vNode = '<vNode>', vResource, [devices], [ip], [imageURL], [storage], [cpu], [memory], '</vNode>'; imageURL = '<imageURL>', string, '</imageURL>'; devices = '<devices>', {string}, '</devices>'; ip = '<ip>', string, '</ip>'; memory = '<memory>', (longInterval | longSet | longSimple), memoryUnit, '</memory>'; cpu = '<cpu>', frequency, [cores], [architecture], '</cpu>'; frequency = '<frequency>', (doubleInterval | doubleSet | doubleSimple), vRouter = '<vRouter>', vResource, [memory], dataPlane, controlPlane, '</vRouter>'; dataPlane = '<dataPlane>', scheduling, '</dataPlane>'; scheduling = '<scheduling>', ('LQF' | 'RR' | 'FCF'), '</scheduling>'; controlPlane = '<controlPlane>', layer, type, routingProtocol, [routingTable], '</controlPlane>'; type = '<type>', ('static' | 'dynamic'), '</type>'; routingProtocol = '<routingProtocol>', ('OSPF' | 'BGP' | 'RIP'), '</routingProtocol>'; layer = '<layer>', string, '</layer>'; routingTable = '<routingTable>', rtSize, {route}, '</routingTable>'; rtSize = '<rtSize>', integer, '</rtSize>'; route = '<route>', source, destination, gateway, '</route>'; gateway = '<gateway>', string, '</gateway>'; vGroup = '<vGroup>', id, multiplicity, [location], {vNode | vRouter |

  <?xml v e r s i o n=" 1 . 0 " e n c o d i n g="UTF-8"?> < d e s c r i p t i o n xmlns=" h t t p : / /www. e n s -l y o n . f r / LIP /RESO/ S o f t w a r e / v x d l " xmlns : x s i=" h t t p : / /www. w3 . o r g / 2 0 0 1 /XMLSchema-i n s t a n c e " x s i : s c h e m a L o c a t i o n=" h t t p : / /www. e n s -l y o n . f r / LIP /RESO/ S o f t w a r e / v x d l VXDL. x s d ">

Table 4 . 2

 42

	CrestLines	31.06s ± 0.57	15 MB	10 MB
	CrestMatch	3.22s ± 0.51	25 MB	4 MB
	PFMatchICP	10.14s ± 2.41	10.2 MB	240 kB
	PFRegister	0.64s ± 0.22	240 kB	160 kB
	Yasmina	52.94s ± 12.96	15.2 MB	4 MB
	Baladin	226.18s ± 19.36	15.2 MB	4 MB

Time (average ± standard deviation) Input data Produced data : Benchmarks of the Bronze Standard's modules: execution time, data input and produced data volumes.

Table 4 .

 4 4 presents the data transfer time (in seconds) of the application modules on VI 2 -Allocation IV (local) and VI 1 -Allocation II (distributed across 2 locations). The overhead is 150% in the worst case. Conversely, some local

	Modules	VI 2 -Allocation III VI 2 -Allocation IV variation
	CrestLines	34.12 ± 0.34	36.84 ± 5.78	+7.97%
	CrestMatch	3.61 ± 0.48	3.99 ± 0.63 +10.53%
	PFMatchICP	11.93 ± 2.76	12.75 ± 5.35	+6.87%
	PFRegister	0.78 ± 0.18	0.79 ± 0.18	+1.28%
	Yasmina	59.72 ± 14.08	61.53 ± 13.98	+3.03%
	Baladin	244.68 ± 16.68	247.99 ± 19.51	+1.35%
	Table 4.3: Average execution time (in seconds) on VI 2 -Allocation III and VI 2 -
	Allocation IV.

Table 4 . 4

 44

		VI 2 -Allocation IV VI 1 -Allocation II variation
	CrestLines	2 ± 0.45	3.01 ± 1.6	+50.5%
	CrestMatch	1.99 ± 0.34	1.83 ± 0.36	-8.04%
	PFMatchICP	1.3 ± 0.4	3.25 ± 0.13	+150%
	PFRegister	0.51 ± 0.23	0.43 ± 0.09	-15.69%
	Yasmina	1.19 ± 0.27	1.16 ± 0.21	-2.52%
	Baladin	1.17 ± 0.38	1.81 ± 1.03	+54.7%

: Data transfer time (in seconds) on the local VI 2 -Allocation IV and large scale distributed VI 1 -Allocation II.

Table 4 . 5

 45

	Strategy	Makespan	#VM	Deployment Reconfiguration time time	Execution cost (×10 5 )
	Naive	67.08min ± 0.10	35	29.83min	0	1.40 × cr + 3.68 × c b
	FIFO	46.88min ± 0.78	35	29.83min	0	0.98 × cr + 1.10 × c b
	Optimized
	(without grouping) 37.05min ± 0.25	31	25.68min	79.29s	0.69 × cr + 0.98 × c b
	Optimized
	(with grouping)	22.93min ± 0.58	31	25.68min	52.86s	0.42 × cr + 0.48 × c b

: Performance comparison among the four strategies.

Table 4 .

 4 6: Evaluation of the bandwidth control mechanism.

		Stage 1	Stage 2	Stage 3	Makespan	Execution cost
		(seconds)	(seconds)	(seconds)	(minutes)	(×10 5 )
	Low (1 Mbps)	222.59 ± 2.51 316.57 ± 40.37 2.91 ± 0.50 34.78 ± 0.67 0.65 × cr + 0.31 × c b
	Optimized	53.8 ± 4.56	171.72 ± 24.66 1.53 ± 0.23 22.93 ± 0.58 0.42 × cr + 0.48 × c b
	High (10 Mbps)	30.79 ± 3.85	42.68 ± 9.55	1.09 ± 0.18 17.72 ± 0.23 0.33 × cr + 1.61 × c b

  CHAPTER 6. RELIABLE VIRTUAL INFRASTRUCTURES 6.4. FROM RELIABILITY REQUIREMENTS TO RELIABLE VIS

	r=99.999% Virtual Infrastructure Specification	translation II. Graph	:redundancy node Reliability Expansion
	r=99.9%
	r=99.9%	r=99.99%
						III. Resource
		I. Language			Allocation
		description
	Service
	requirements	System		I	I	Physical Substrate Physical Substrate
		Architecture		Physical substrate resource provisioning
	Service/Application Developer	Virtual Infrastructure Provider

Table 6 .

 6 2: Execution time and % increase over baseline for critical database protection only (column DB), and for computing nodes protection (column CN).

	MTBF	DB	Increase	CN	Increase
	∞	1205s		1205s
	60000s 1401s 16.26% 1208s	0.2%
	30000s 1524s 26.47% 1225s	1.7%
	15000s 1688s 40.08% 1244s	3.2%
	MTBF Total data transfer time
		∞	165.02s ± 44.30s
	60000s	190.20s ± 96.75s
	30000s	292.96s ± 115.38s
	15000s	299.61s ± 128.26s

Table 6 .

 6 3: Total data transfer time of application services running with critical database protection scenario.

Table 6 .

 6 4: Price with reliability for database protection (reliability level 99.9%) and fraction of price corresponding to reliability with backup provisioned on short term leases or long term leases.

	Long term

Table 6 .

 6 5: Price of reliability for computing node protection (reliability level 99.9%) and fraction of price corresponding to reliability with backup provisioned on short term leases or long term leases.

				Short term	Long term
	MTBF p F AIL n r b	P G	P B /P G	P G	P B /P G
	60000s	0.03	5	$3.42 16.1% $3.10	5.3%
	30000s	0.06	8	$3.71 25.8% $3.19	8.4%
	15000s	0.12	12 $4.09 38.7% $3.32 12.6%

Table 6 .

 6 6: Application makespan with task resubmission mechanism and percentage increased when compared with VI reliability service.

	Increase

c Copyright 2011 by Guilherme Piêgas Koslovski

c Copyright 2011 by Guilherme Piêgas Koslovski

1.3. CONTRIBUTIONS CHAPTER 1. INTRODUCTION

2.2. VIRTUALIZATION CHAPTER 2. STATE OF THE ART

2.3. CLOUD COMPUTING CHAPTER 2. STATE OF THE ART

2.4. VIRTUAL INFRASTRUCTURES CHAPTER 2. STATE OF THE ART

2.5. PROVISIONING DYNAMIC VIRTUAL INFRASTRUCTURES CHAPTER 2. STATE OF THE ART

3.2. STATE OF THE ART CHAPTER 3. VXDL

3.3. VIRTUAL INFRASTRUCTURE DESCRIPTION LANGUAGE -VXDL CHAPTER 3. VXDL

√ √ √ √ √Table 3.1: A comparison among some resource description languages focused on virtual infrastructure specification. √ identifies the presence of an attribute. VXDL, described in Section 3.3, fulfills all the VI requirements. c Copyright 2011 by Guilherme Piêgas Koslovski

3.4. CONCLUSIONS CHAPTER 3. VXDL

5.3. PROBLEM FORMULATION CHAPTER 5. ALLOCATING RESOURCES TO VIRTUAL INFRASTRUCTURES

5.4. A HEURISTIC FOR ALLOCATING VIS CHAPTER 5. ALLOCATING RESOURCES TO VIRTUAL INFRASTRUCTURES

5.6. CONCLUSIONS CHAPTER 5. ALLOCATING RESOURCES TO VIRTUAL INFRASTRUCTURES

We refer the reader to Section

2.5.3 in Chapter 2 for further details of the HIPerNet framework. c Copyright 2011 by Guilherme Piêgas Koslovski

6.7. CONCLUSIONS CHAPTER 6. RELIABLE VIRTUAL INFRASTRUCTURES

7.2. PERSPECTIVES FOR FUTURE WORK CHAPTER 7. CONCLUSIONS & FUTURE WORK

Algorithm 5.1: A heuristic for allocating VIs.

for a ∈ A R do while a = ∅ do R v ← ∅ : temporary set of virtual resources;

R v : requested virtual resources; L v : requested virtual links; R v : temporary set of allocated virtual resources; L v : temporary set of allocated virtual links;

extend vLinks from L t as described in Section 5.2.3;

< t i m e l i n e i d=" d a t a t r a n s f e r 3 "> < a f t e r >Mapping s t a g e </ a f t e r > <a c t i v a t e >Mapping C l u s t e r </ a c t i v a t e > <a c t i v a t e >R e n d e r i n g C l u s t e r </ a c t i v a t e > <a c t i v a t e >h i g h c a p a c i t y l i n k 3</ a c t i v a t e > <t o t a l T i m e >PT1H</t o t a l T i m e > </ t i m e l i n e > < t i m e l i n e i d=" R e n d e r i n g s t a g e "> < a f t e r >d a t a t r a n s f e r 3</ a f t e r > <a c t i v a t e >R e n d e r i n g C l u s t e r </ a c t i v a t e > <t o t a l T i m e >PT2H</t o t a l T i m e > </ t i m e l i n e > < t i m e l i n e i d=" d a t a t r a n s f e r 4 "> < a f t e r >R e n d e r i n g s t a g e </ a f t e r > <a c t i v a t e >R e n d e r i n g C l u s t e r </ a c t i v a t e > <a c t i v a t e >V i s u a l i z a t i o n C l u s t e r </ a c t i v a t e > <a c t i v a t e >h i g h c a p a c i t y l i n k 4</ a c t i v a t e > <t o t a l T i m e >PT2H</t o t a l T i m e > </ t i m e l i n e > < t i m e l i n e i d=" V i s u a l i z a t i o n s t a g e "> < a f t e r >d a t a t r a n s f e r 4</ a f t e r > <a c t i v a t e >V i s u a l i z a t i o n C l u s t e r </ a c t i v a t e > <t o t a l T i m e >PT1H</t o t a l T i m e > </ t i m e l i n e > </ v i r t u a l T i m e l i n e > </ v i r t u a l I n f r a s t r u c t u r e > </ d e s c r i p t i o n >