Nicolas Broutin

Othmane Safsafi

Davit Martirosyan

Ravi Mazumdar

Nelly Maloisel

Renaud Dessalles

Sarah Eugène

Lucas De To- Maso

Isabela Kuschnir

Amannda Dacache

Isabelle Dutra

Rodrigo Fraga

Pereira De Sá

Luiz Nilton Alves

Antônio Meirelles

Maria Alice Da Rocha

Pm

Pm N1 Dc

Flow of incoming virtual machines

A thank you also to those who have been with me during countless hours in the navette and thank you to our coffee machine neighbours from Gallium. During my whole stay at INRIA, be it close to the woods of Rocquencourt or in the very core of Paris, I always felt well surrounded.

Chapter 1 Introduction

This introduction begins with a presentation of Cloud Computing which is the main object of study of this thesis in order to familiarise non-expert readers with a certain vocabulary and important key concepts. An overview of the issues and challenges related to Cloud Computing provides reasons for why conducting research in this field is so crucial. The focus of this thesis being the dynamic allocation of resources in the framework of stochastic networks, a selection of the most relevant literature of this topic is presented.

It follows an exposition of relatively simple stochastic queueing and network models in order to facilitate the reader's understanding of the more sophisticated models used in the thesis for the analysis of different aspects of the Cloud Computing environment. These simple models rely on similar assumptions and shall provide a good first understanding of basic model mechanisms.

In a next section, the main mathematical tools are described and their usage is illustrated through their application to the simple stochastic models introduced previously. A large part of this section concerns Markov processes and related tools necessary for its analysis, namely kernel problems and scaling techniques. This is followed by a quick introduction of the stochastic averaging principle and an explanation of how the cohabitation of different time scales determines the macroscopic evolution of large scale systems.

Finally, the content of the four chapters of this thesis is presented.

Cloud Computing

Cloud Computing is a service model, whose principle is the on-demand offer of access to shared computing resources. In the literature, the definition of this relatively recent concept is not yet pinned down. Several authors interpret the term in different ways (see [YBDS08, FZRL08, VRMCL08, Gee09, ASZ + 10, ZCB10, MG11]). Among these authors, Foster et al. [START_REF] Foster | Cloud computing and grid computing 360-degree compared[END_REF] propose one of the more broad and inclusive definitions [Cloud Computing is] 'A large-scale distributed computing paradigm that is driven by economies of scale, in which a pool of abstracted, virtualised, dynamically-scalable, managed computing power, stor-age, platforms, and services are delivered on demand to external customers over the Internet.' From this extract, we retain the main concept of 'a shared large pool of digital resources delivered on demand'. From now on, we refer to this rather general definition whenever we use the term Cloud.

The idea of pooling resources together in order to mitigate idleness and benefit from economies of scale to reduce costs is not particularly new. Since the popularisation of computers and the access to Internet, many techniques have been explored to exploit the full potential of the processing power associated with these new technologies. We witnessed for example the development of Grid Computing, Utility Computing, Service Computing which are service concepts relatively similar to Cloud Computing. See Foster et al. [START_REF] Foster | Cloud computing and grid computing 360-degree compared[END_REF] for a detailed discussion of the taxonomy of these technologies and Voas and Zhang [VZ09] for a critical discussion about the existence of Cloud Computing as a new computational paradigm.

Although these techniques have been in vogue for some while, none of them was as influential as Cloud Computing. Only as Internet access and computing resources have become cheaper, more powerful and ubiquitously available, users and companies felt confident enough to adopt the new service model. Cloud Computing has particularly been boosted by the interests of major players in the Internet market such as Amazon, with the Amazon Web Services (AWS) [Ama], Microsoft, with Microsoft Azure [Mic], and Google, with Google Cloud Platform (GCP) [Goo], leading to a genuine trend over the last decade which is currently still gaining momentum. See for example Amazon's portfolio of customer success stories which provides a glimpse of how much Cloud services are penetrating the Internet market ( [Ama]).

Essential Characteristics

Despite the variety of definitions of Cloud Computing services (see for instance Armbrust et al. [ASZ + 10] and Mell and Grance et al. [START_REF] Mell | The NIST definition of cloud computing recommendations of the national institute of standards and technology[END_REF]), there exists a set of criteria recurrently cited by the authors of the field which has to be fulfilled for a service to be considered a part of the Cloud Computing environment.

Elasticity is probably the most notorious feature of Cloud services. Resources can be allotted and released (almost) instantaneously. Users can ask for more resources when in need, as well as release superfluous resources. Elasticity can be understood as an enhancement on scalability, as it does not only include keeping up with the increasing loads of jobs but also takes into account the proper adjustment for decreases in the need for resources.

Another common aspect of Cloud services and a key factor for its commercial success is the billing system. The Cloud is based on Pay-as-yougo (PAYG) charging mechanisms, where customers chose a virtual machine based on its specifications and are billed as a function of these specifications and for the time they use the service. For example, Amazon's Elastic Compute Cloud (EC2) allows users to configure their virtual machines (VM) in terms of memory RAM, CPU cores, storage space, connectivity bandwidth, Operational System (OS), etc. However, PAYG is not necessarily a characteristic of all Cloud services today. Cloud operators are currently developing middle and long term contracts, intended to smooth resource consumption, lock clients in and improve the dimensioning of their data centres. We also observe the emergence of serverless computing where Cloud containers hold only the necessary resources for the execution of a specific application, and services like Amazon Lambda, where customers do not have to reserve an entire VM any more but pay for the computing resources necessary for the execution of their tasks.

Availability is an essential condition for Cloud services because it is a precondition for people trusting in the new technology. This is why all players of the Cloud ecosystem are today committed to high availability, proposing elevated Service Level Agreements (SLA). See for instance the "SLA" section in [Ama], [Goo] and [Mic]. High availability is ensured through the offer of a reliable pool of resources and redundancy mechanisms.

Clouds can mainly be divided into either public or private Clouds, even though there also exist some hybrid forms or community Clouds which host private and public services in a single structure. The infrastructure of public Clouds is intended to serve many customers from different organisations. Customers should not be affected by the use of resources by others sharing the same physical machine (PM). Privates Clouds are designed to serve exclusively a single organisation. Today, many companies opt for this deployment level because data security issues and legislation constraints render the adoption of public services prohibitive.

Cloud Computing services can be organised into the following categories: Infrastructure as a Service (IaaS), Platform as a Service (PaaS) and Software as a Service (SaaS). This classification is usually referred to as SIP model. Certain subcategories have been proposed, such as Business Process as a Service (BPaaS) as a part of SaaS or Desktop as a Service (DaaS) as a category of PaaS. However, these subcategories fail to offer a real surplus over the original SIP model, especially in terms of mathematical modelling.

Infrastructure as a Service (IaaS) is a service model where providers offer on-demand computing resources to their customers. This is done through virtualisation, which is the emulation of a real physical system (with hardware specifications) in a virtualised manner. We say a virtual machine is instantiated in a server or data centre when the physical resources (Physical Machines (PM)) supporting the virtual machines are located there. Customers can create such virtual machines which use resources such as Random Access Memory (RAM) and Computing Processing Unit (CPU) cores. In this manner, multiple users can simultaneously allocate customised virtual machines and access them over the Internet or a local network. The provision of IaaS contributes to the reduction of equipment acquisition and maintenance costs for the users.

Platform as a Service (PaaS) allows the user to deploy onto the Cloud infrastructure applications created using programming languages, libraries, services, and tools supported by the service provider. The user does not manage or control the underlying Cloud infrastructure (the network, servers, operating systems, etc.) but he has control over the deployed applications and possibly configuration settings for the application-hosting environment.

In Service as a Service (SaaS), the user has the possibility to run the provider's applications which are deployed onto a Cloud infrastructure. The user does not manage or control the underlying Cloud infrastructure, neither individual application capabilities, with the possible exception of limited userspecific application configuration settings.

In the hierarchy of the Cloud, IaaS is considered to be the core of Cloud services because both PaaS and SaaS are dependent on the infrastructure, without which they could not exist. Emphasising the importance of infrastructure, Zhang et al. [START_REF] Zhang | Cloud computing: stateof-the-art and research challenges[END_REF] classify Cloud service providers into infrastructure providers, whose core business is the IaaS, and service providers, who propose services in the Cloud but rent resources from infrastructure providers. IaaS is also the most interesting aspect of Cloud Computing for mathematical studies as it is relatively simple to model. The requests executed in this level of Cloud require "raw" units of resources, such as CPU cores or GB of RAM, which need to be available lo host the incoming clients. In this context, the mathematical framework of Queueing Theory and also some tools from Operational Research are very promising for the analytical evaluation of the performance of Cloud systems.

Issues and challenges

Although Cloud Computing has been widely adopted by many major players in the telecommunication industry, the research in this field is still at an early stage. As for many other scientific advances, the technological possibilities develop much faster than our understanding of their functioning. Many key challenges, including automatic resource provisioning, power management and security management, are only starting to receive attention from the research community, while new challenges keep emerging from new applications and methods. See Zhang et al. [START_REF] Zhang | Cloud computing: stateof-the-art and research challenges[END_REF] for more details.

The work in this thesis focuses more particularly on the challenges related to the current emergence of new decentralised Cloud architectures. Most of the commercial Clouds are today still implemented in large data centres and operated in a centralised fashion. In this set-up, all (or most of) the requests, originated near or far from the large data centre, is executed in this unit. This design has the advantage of economies of scale and high manageability but it comes at the price of high energy expenses (usually associated with the cooling down of the data centres), elevated up-front investments in infrastructure and increased latency delays. Long transmissions across the network are costly and often associated with security risks and cross-boarder juridical issues. Furthermore, the centralised system constitutes a potential bottleneck to the further development of Cloud Services, as its delivery channels are likely to get congested due to the continuous increase in the volume of Internet traffic.

Small-sized data centres that are better geographically distributed and Chapter 1

1.1. Cloud Computing work in a decentralised manner can be more advantageous. They do not only require a less powerful and less expensive cooling system but, being located closer to the user, they also constitute a solution to the high transmission costs, saturation of delivery channels and latency times present in a centralised system. This is particularly important for response time-critical services such as content delivery and interactive gaming. In 2009, Valancius et al. [VLM + 09] propose for example the usage of small (nano) data centres for hosting of Video on Demand services. We therefore witness a general movement of data centres towards the edge of the network away from centralised structures. This distribution of Cloud Computing resources at the edge of the network is known as Fog Computing (see [WRSvdM11, BMZA12, RBG12]) and allows for example to handle the enormous amount of data generated by devices located all over the network (i.e. Internet of Things (IoT), see Atzori et al. [AIM10]). With these developments towards a more distributed Cloud architecture, the problematic of how to handle local demands relying on much smaller service units is currently gaining in importance. It is now possible that local data centres face scarcity of some resources which results in the rejection of user demands despite the total amount of resources in the system being sufficient to satisfy all user demands if the resources would be pooled in a centralised data centre. In order to reduce the occurrence of request blocking, Fog Computing data centres will have to collaborate, for example by offloading user demands to another data centres that does not face saturation. See Sharif et al. [START_REF] Sharifi | Energy efficient cloud service provisioning: Keeping data center gran-ularity in perspective[END_REF] for an extensive discussion about the perspectives for decentralised service models for Cloud technologies.

The development of new models is crucial for the study of the Cloud and future technologies building upon it. The computation associated with these models needs to be adapted to the increased volume and diversity of the Cloud Computing traffic. For instance, classical approaches for network optimisation, such as global load balancing strategies might be too slow depending on the magnitude of the system and necessitate revision. Another example, bandwidth sharing policies have to be redesigned in order to ensure a fair (equitable) division of network resources in the current context of an increase and diversification of customer demands. This thesis develops such models, taking into account the stochasticity of the arrival of user demands and duration of service times, which is absent in most of the research conducted so far.

Resource Allocation in the Cloud

The focus of this thesis is the dynamic allocation of resources in the framework of large stochastic networks. This part presents a selection of the most relevant literature on this topic.

In the context of Infrastructure as a Service, the Cloud service provider faces the challenge of allocating resources efficiently by assigning incoming requests of virtual machines to physical machines located in the Cloud data centre.

This issue of resource allocation in Cloud systems has been addressed by many authors with different perspectives, scopes and objectives. As Cloud Figure 1.1 -Representation of a Cloud providers data centre systems are very different one from another, research branches in many directions. See Jennings and Stadler [START_REF] Jennings | Resource management in clouds: Survey and research challenges[END_REF] for a complete survey about resource management techniques for Cloud services and Masdari et al. [START_REF] Masdari | An overview of virtual machine placement schemes in cloud computing[END_REF] for an overview of the techniques used in Cloud services for determining virtual machine placement.

Most of the literature focuses on Cloud Computing systems which rely on one type of resource exclusively (e.g. RAM memory, CPU cores, bandwidth, etc.). Queueing theory has been widely used for the study of such systems as it is particularly adapted to this context and provides a rich toolbox for system optimisation. One of the first works in this field is Yang et al. [START_REF] Yang | Performance Evaluation of Cloud Service Considering Fault Recovery[END_REF] who consider queues to evaluate metrics regarding the performance of Cloud services and Khazaei et al. [START_REF] Khazaei | Performance analysis of cloud computing centers using M/G/m/m+r queuing systems[END_REF] study a simple Cloud system using M/G/m/m+r queues. These papers as well as many other papers consider single resources systems. In the setting of Cloud Computing environments proposing multiple resources, the allocation of resources is more complex. The tools of queueing theory are less adapted and provide fewer information on the system under scrutiny. In the literature on multiple resources, the issue of resource allocation has classically been addressed through bin-packing and knapsack problems in the framework of stochastic optimisation [RT89, [START_REF] Ross | Multiservice loss models for broadband telecommunication networks[END_REF][START_REF] Goel | Stochastic load balancing and related problems[END_REF]. From a utility (or reward) perspective, these methods aim to determine which (possible) configuration would maximise some given utility function (over time). For example, consider a data centre which is equipped with C i units of resources i ∈ I, and VM of type j ∈ J requiring A i,j units of each resource. If a VM of type j is hosted in this system, the operator will be rewarded with a w j bonus. If we denote x j the number of VM of type j in the system, then the optimisation problem is simply defined by max x∈S j∈J w j x j with S =

   x = (x j ) ∈ N |J| : j∈J A i,j x j ≤ C i ∀i ∈ I    .
However, bin-packing and knapsack problems are NP-Complete [START_REF] Christensen | Multidimensional bin packing and other related problems: A survey[END_REF] and Chapter 1 1.1. Cloud Computing are therefore too slow to be used as a viable resource orchestration practice for large Cloud systems despite the development of many efficient heuristic methods in recent years. In addition, such methods allow only to consider the static characteristics of the systems with very limited applications in dynamical contexts.

Given these shortcomings in the multi-resource context, the recent literature focuses back on systems providing a single resource exclusively, or straightforward application of queueing theory resulting in quicker calculations and providing information on system dynamics. However, contrarily to the literature on queueing theory mentioned previously, this recent strand of literature considers more complex systems which are composed of several queues, modelling the rack of servers, servers farms or data centres. One approach in this framework of resource allocation of a single resource considering multiple queues is intelligent dispatching. Instead of running calculation power intense optimisation programs, the focus lies on the "sending" of a VM to a PM. One popular technique consists of dispatching virtual machines to the most busy physical machines in order to be able to generate as many idle PM as possible which can then be turned off (for power saving considerations). For example, Stolyar and Zhong [START_REF] Stolyar | A large-scale service system with packing constraints: Minimizing the number of occupied servers[END_REF] introduce the algorithm Greedy with sub-linear Safety Stocks (GSS) with the objective of minimising the number of active servers in a multi-resource data centre in a heuristic manner, and Xiao et al. [START_REF] Xiao | Dynamic resource allocation using virtual machines for cloud computing environment. Parallel and Distributed Systems[END_REF] present a "skewness" metric to control for unevenness in the multidimensional resource utilisation for VM dispatching, aiming to minimise the number of servers in use. On the contrary, load balancing techniques have the aim to deploy the full capacity of the system, thus tempting to assign VM homogeneously across the pool of physical machines. In telecommunications theory, a common reference is the policy known as join the shortest queue (JSQ) which is, however, only effective in small-scale systems as the state of each physical machine must be known in order to dispatch VM accordingly. For instance, Maguluri et al. [MSY12] discuss the implementation of JSQ in a multi-resource Cloud service data centre and show that this policy is not suitable for large scale systems. Other techniques aim to improve global performance using only local information (from a small sample of data centres). The power-of-choice (or supermarket model) has been introduced by Mitzenmacher [Mit96] and Vvedenskaya et al. [START_REF] Vvedenskaya | Queueing system with selection of the shortest of two queues: An asymptotic approach[END_REF]. In this approach, the dispatching program randomly compares the size of the queue in a limited amount of different physical machines (usually 2 or 3) and assigns the VM to the server with the shortest queue (the smallest workload), resulting in quick and efficient dispatching. This technique inspired the recent framework of pull based policies such as Join-Idle-Queue (JIQ), proposed by Lu et al. [LXK + 11] where a list of idle physical machines is kept to which virtual machines are then allocated. See Stolyar [START_REF] Stolyar | Pull-based load distribution in large-scale heterogeneous service systems[END_REF] and Foss and Stolyar [START_REF] Foss | Large-scale join-idle-queue system with general service times[END_REF] for a similar policy, the PULL algorithm, which assigns servers to customers instead of the common customer to server assignment.

In this thesis I consider resource allocation for on-time services, such as for example Microsoft Azure [Mic] systems, which necessitate instantiation of virtual machines as soon as they are assigned to a physical machine. If a system Chapter 1 1.1. Cloud Computing does not dispose of a sufficient amount of resources (in one or several PM) to host an arriving VM, the request is rejected. Cloud service providers have an incentive to avoid high rejection rates which result in the loss of customers and eventually a decline in revenues. On-time systems have been studied by many authors. Recently, Xie et al. [START_REF] Xie | Power of d choices for large-scale bin packing: A loss model[END_REF] and Mukhopadhyay et al. [MKMG15] use loss systems in the study of intra data centre VM allocation with power of choice mechanisms. In Xie et al., the customers require different amounts of resources during their service. In Mukhopadhyay et al., heterogeneous types of servers are considered, differentiated by their capacity (size). However, these models mostly are adapted to cases where system performance is determined exclusively by one resource (i.e. the system's bottleneck). In this thesis, similar loss systems are considered, but introducing in addition a generalisation to the multi-resource case (see Chapter 3 concerning cooperation schemes between multi-resource processing facilities).

In the literature, the allocation of resources has been focused on the intra data centre schemes, i.e. allocation of resources within a given data centre. However, as mentioned before the Cloud is evolving, there exists a need for collaboration in between small-size data centres in order to reduce the rejection of user demands in locally saturated data centres in the new Cloud architecture. For this reason, this thesis focuses on allocation of resources in between data centres (inter data centre schemes). For instance, consider a system with N servers distributed in 2 data centres -N 1 servers in data centre 1 and N 2 in data centre 2, with N 1 + N 2 = N . The system has the same capacity as Figure 1.2 -Representation of a Cloud system with multiple data centres its centralised version, but the customers in each processing facility may experience a very different quality of service due to traffic asymmetry. In the worse case, resource can be idle in one data centre while depleted in the other facility, causing "unnecessary" blocking of customers.

In Chapter 2 of this thesis, I investigate an allocation scheme for on demand video services where clients are served with the lowest service grade (level or resolution in terms of video quality) as soon as the link occupation is above a certain threshold, allowing the system to mitigate rejection of customers. Chapter 3, 4 and 5 focus on policies to enable the cooperation between decentralised facilities in a effort to improve the performance (particularly reducing the blocking rates of customers) which can find an application in the new decentralised Cloud architectures which are currently emerging. In Chapter 3, Chapter 1 1.2. Stochastic Modelling of Services I study an offloading scheme between two data centres in the multi-resource context. In the framework of resource-specialised virtual machines requiring different proportions of each resource, this policy aims to alleviate the local charge of a resource by forwarding the customers (VM) which require the most of the resource which is depleted locally. In Chapter 4, I consider the policy which forwards jobs from a data centre to another with some probability if the request cannot be served locally. And, in Chapter 5, a system similar to the one presented in Chapter 4 is considered under a another offloading policy: jobs are systematically forwarded from one data centre to the other, and are only accepted in the second data centre if there are a minimum amount of free servers. Notice that in this case, only one processing facility (data centre 1) is offloading customers to the other (data centre 2), which protects its original requests using a trunk reservation mechanism.

Stochastic Modelling of Services

This section introduces simple versions of the models used throughout this thesis for the analysis of Cloud Computing systems. The models are presented in the order of their complexity to acquaint the reader step by step to the classical tools of stochastic modelling.

Queueing Systems

A queueing system is the representation of a real system, where clients (or jobs) arrive, demand a service which takes some time, and then leave the system. A queue may be equipped with one or more servers and a buffer (or waiting) zone, such that clients who are not being served can wait for the starting of the service. If a queue has no buffer zone or if all of its servers and buffer are already used, all arriving customers are rejected until some space is freed. The duration of the time that clients are waiting is called waiting time. The duration of the time that the service is being executed is called service time.

The study of such queueing systems originated from the development of telecommunication technologies and gained in importance with the arrival of centralised computing units (main frame architecture) some years later. The main objective was to be able to calculate blocking probabilities of clients in the telephone network and waiting times of customers until access to the computing power in the main frame.

Erlang's Problem

In the beginning of the twentieth century, while working for the Copenhagen Telephone Company (CTC), the Danish engineer Agner K. Erlang (1878Erlang ( -1929) ) was confronted with the intriguing problem of dimensioning the company's telephone network.

Back then, a phone call was the realisation of a connection between a caller and receiver, using a circuit board on the links between these two interlocutors.

While the phone call was in progress, the circuit stayed occupied. If a new call was attempted when all the circuits were occupied, this call was rejected.

Local communities were connected by one board of circuits, see Newman [New10]. Erlang was responsible for determining the number of circuits to ensure a certain service level (or grade), given by the probability a client is rejected by the exhaustion of the circuits. In his efforts to engineer this system, Erlang published many papers with two being of particular importance for the development of this thesis.

His 1909 seminal paper "The Theory of Probabilities and Telephone Conversations" [START_REF] Erlang | The theory of probabilities and telephone conversations (sandsynlighedsregning og telefonsamtaler)[END_REF] 1 showed that the number of calls coming in follows a Poisson distribution. This approximation allows to calculate system performance and is used until today in many areas due to its practicality.

In 1917, Erlang published "Solution of some problems in the theory of probabilities of significance in automatic telephone exchanges". Analysing teletraffic data, Erlang observed that the duration of the phone calls were exponentially distributed with mean µ -1 . Using this, the fact that incoming calls follow a Poisson distribution at rate λ > 0 and analysing the evolution of the number of used circuits, Erlang derived his famous formula for traffic design which we call today the Erlang-C formula.

B(λ, µ, C) = (λ/µ) C /C! 1 + (λ/µ) + (λ/µ) 2 /2 + • • • + (λ/µ) C /C! . (1.1)
This formula expresses the probability of an arriving customer to be blocked in a system composed of C circuits.

It is interesting to note that the theory of stochastic processes which would offer a formal support for the study of queueing systems was developed only after Erlang's death by Andrey Kolmogorov (1903Kolmogorov ( -1987)). This means that Erlang studied the telephone network only using classic probabilistic reasoning which is remarkable. Erlang was not only a pioneer in stochastic modelling of services, but he also laid the cornerstone of Queueing Theory and its branches. See Cohen and Boxma [START_REF] Cohen | A survey of the evolution of queueing theory[END_REF] and Kingman [Kin09] for more details.

Queues with one server

Queues are characterised by a number of servers, a waiting zone, arrival and departure processes of clients and a service discipline. The simplest queue is composed of a single server and an unlimited waiting zone. Clients are served one at a time and in their order of arrival which is why this service discipline is called First Come First Served (FCSF) or First In First Out (FIFO). Those who are not served directly upon their arrival start waiting in the queue. It is assumed that clients arrive according to a Poisson process with intensity λ. The time a client occupies the server (the service time) is exponentially distributed with mean 1/µ. The key characteristic of the Poisson arrival process and the exponentially distributed service times is that they Chapter 1 1.2. Stochastic Modelling of Services describe a system which is memoryless. In Kendall's notation [START_REF] Kendall | Stochastic processes occurring in the theory of queues and their analysis by the method of the imbedded Markov chain[END_REF], this queue is therefore called a M/M/1 queue, with M standing for memorylessness and 1 for the number of servers.

The M/M/1 queue can also be analysed through an associated embedded discrete-time Markov chain. This Markov chain behaves like a random walk on N or, more illustratively, as a birth-death process, where the number of individuals (i) in a population is analogous to the number of clients in the queue. With probability λ/(λ+µ) the number of individuals (clients) transitions from i to i + 1. A decrease of the queue (the population) from i to i -1 happens with probability µ/(λ + µ), for i ≥ 1. See Chapter III of Asmussen [START_REF] Asmussen | Applied Probability and Queues[END_REF]p. 75].

0 1 • • • i • • • µ µ µ µ λ λ λ λ Figure 1.3 -Transition diagram of the M/M/1 Queue
Erlang's famous result (as introduced in the previous section) is based on his observation of the relationship between the probability of finding i clients present in the queue and the "speed" in the change of the number of clients queueing (i ± 1). He supposed that if the system reaches its equilibrium, the "flows" i → i + 1 and i + 1 → i (conversely to i → i -1) should be of the same order. These "flows" are given by π(i)q(i, i + 1) and π(i + 1)q(i + 1, i), where π(i) denotes the probability of finding i customers in the system and q(i, j) denotes the transitions rates from i to j. Thus, at equilibrium we have the following relation for i ≥ 1 π(i)q(i, i + 1) = π(i + 1)q(i + 1, i).

(1.

2)

The number of customers in the system can be described by a Markov process whose transitions for the M/M/1 queue are q(i, j) are given by

q(i, j) = λ if j = i + 1 µ1 {i>0} if j = i -1.
Recursively, if λ < µ, we have can solve difference equation for i ∈ N, and obtain

π(i) = (1 -ρ)ρ i .
One sees that this relatively simple model already provides some crucial information on the behaviour and the performance of queueing systems. Among other performance metrics that can be derived we have for example the distribution of waiting times, the utilisation rate of the server or the mean length of a queue. The simplicity and yet versatility of Erlang's results has thus propelled the popularity of queueing models. In later work, Pollaczek (1892Pollaczek ( -1981) )

Queues with many servers

Other important mathematical objects used in this thesis are queues with many servers and no waiting zone. These queueing systems are used in the modelling of on-demand services where clients do not wait for getting served and are rejected if the capacity of the system is exhausted (in case all servers are occupied). These systems are the original object of study of the works of Erlang.

The system is equipped with C servers and can host up to C clients simultaneously, which is why it is called M/M/C/C in Kendall's notation. Just as for the M/M/1 queue presented previously, customers in the M/M/C/C arrive according to a Poisson process with rate λ and service times are again independently and exponentially distributed with finite mean 1/µ.

The number of customers in the system can be described by a Markov process taking values in A def.

= {1, . . . , C}, whose transition rates are given by

q(i, j) = λ1 {j≤C} if j = i + 1, µj if j = i -1.
Note that the M/M/C/C queue is in fact a truncated version of the M/M/∞ queue because its maximal capacity is fixed at C. If the original process takes values in N and has an invariant distribution π = (π(i), i ∈ S) and the truncated process lives in A then, for any i ∈ A, one has

ν(i) = π(i)Z -1 ,
where Z is a normalisation constant given by Z = i∈A π(i). The invariant distribution of the M/M/∞ can be simply obtained by recurrence using the balance equations (the same as Equation (1.2)), such that π(i) ∝ ρ i /i!, where ρ = λ/µ. Therefore, the blocking probability in this system is simply given by Erlang's formula

ν(C) = C i=0 ρ i i! -1 ρ C C! = B(λ, µ, C).
Forty years later, Takács [Tak69] showed Erlang's formula is insensitive to the distribution of the service times, as long as the service time has a finite mean, i.e. blocking rate of customers on a M/G/C/C queue is also given by Erlang's formula.

From here on, we look at extensions of Erlang's M/M/C/C queue to more general systems, so called loss systems. These systems received their name because customers are either served directly upon their arrival or they are rejected, generating losses, in case all of the servers are occupied. Loss systems Chapter 1 1.2. Stochastic Modelling of Services are useful to model communication systems or, more generally, on-demand services where customer requests are usually served instantaneously until exhaustion of the system's resources and after which subsequent customer requests are rejected. The work in this thesis is mainly based on such loss systems.

For sake of illustration we consider the following example of a loss system. The system is equipped with C i ∈ N * units of each resource i, for 1 ≤ i ≤ I. There exist J ∈ N * types of jobs. Jobs of type 1 ≤ j ≤ J arrive in the system accordingly to a Poisson process with rate λ j and stay in the system for a service time which is exponentially distributed with rate µ -1 j , while holding A i,j ∈ N units of each resource i. If we denote by n(t) = (n j (t), 1 ≤ j ≤ J) ∈ N J the vector describing the state of the system, where n j (t) is the number of clients then (n(t)) = (n(t), t ≥ 0) is a Markov process taking values in

S = n ∈ N J : A • n ≤ C , where C = (C i , 1 ≤ i ≤ I) and A = (A i,j , 1 ≤ i ≤ I, 1 ≤ j ≤ J).
Using the fact that the Poisson processes are all independent, one can write the detailed balance equations, for n ∈ N J , π(n)λ j = π(n + e j )µ j (n j + 1)1 {n+e j ∈S} , where π = (π(n), n ∈ S) is the stationary distribution of the process (n(t)) and e j is the j-th column of the canonical base of N J . Since this system is a truncated version of a system where C i = +∞, for 1 ≤ i ≤ I, the following relation must hold

π(n 1 , . . . , n J ) ∝ J j=1 ρ n j j n j ! ,
where ρ j = λ j /µ j . Therefore, the invariant distribution is given by

π(n) = 1 Z J j=1 ρ n j j n j ! with Z = n∈S J j=1 ρ n j j n j ! . (1.3)
Hence, the blocking probability of a job of type j is

n∈B j π(n) with B j = {n ∈ S : n + e j ∈ S} .
Models similar to the current loss systems were developed as early as the beginning of the 20 th century with the rise of the telecommunication technology (see Brockmeyer et al. [START_REF] Brockmeyer | Transactions of the Danish Academy of Technical Sciences (Akademiet for de Tekniske Videnskaber[END_REF], Frenkel [START_REF] Frenkel | The grade of service in multiple-access satellite communications systems with demand assignments[END_REF], Roberts [START_REF] Roberts | A service system with heterogeneous user requirements -application to multi-service telecommunications systems[END_REF], Burman et al.

Mathematical Framework

Markovian Stochastic Processes

In this thesis, most of the queueing systems are analysed under Markovian assumptions, that is to say Poisson arrivals and Exponentially distributed service times. This is an important technical aspect of queueing modelling. In the case of M/M/1 queues, transitions from one state to another (increase or decrease of the number of customers queueing) happen with the same rate λ and µ independent of time. Due to this memorylessness, the system can be fully characterised by the number of clients in the queue at some time and the transition rates. The Markov processes in this document are Continuous-Time Markov Chains, usually analysed through the properties of its associated embedded Discrete-Time Markov Chain. The processes belong exclusively to the class of Markov jump processes. In these processes, the state might not change at all in a small time interval or, when a change does occur, the transition is discrete and of a relatively large magnitude (or "sharp") compared to the "smooth" changes such as observed in Brownian motion. We consider only irreducible and homogeneous (or at least partially homogeneous) Markov jump processes.

Kernel Methods

Let (X(t)) be a Markov process taking values on S, whose Q-matrix (or infinitesimal generator) is denote by Q = (q(x, y), x, y ∈ S). When it exists, the stationary distribution of (X(t)) is denoted by π = (π(x), x ∈ S) and the following relation holds for any function f with finite support on S

x,y∈S x =y

π(x)q(x, y)(f (y) -f (x)) = 0.
In this thesis, the invariant distribution of some Markov processes are obtained from the relation of the associated generating function and its kernel, often making us resort to the toolbox of real and complex analysis i.e. the framework of Riemann-Hilbert problems. For example, if we have a process taking values in N, the function f z (x) = z x , for z ∈ D = {z ∈ C : |z| < 1} plugged into the previous expression is associated with the generating function of the invariant distribution of such a process. Commonly, these objects are studied in the framework of functional analysis and are particularly recurrent in the field study of random walks. Consider the M/M/1 queue. If X is a random variable Chapter 1 1.3. Mathematical Framework with distribution π, the balancing equations of the embedded Markov process associated with the M/M/1 queue yield, for ϕ(z) def.

= E z X and |z| = D, ϕ(z)P (z) = µπ(0) z -1 -1 , where P (z) = λ(z -1) + µ z -1 -1 , whose roots are simply 1 and µ/λ ∈ D, considering λ < µ. As the function ϕ(z) is analytic for z ∈ D, the roots of P (z) in D need to be zeros of the right hand side of the previous equation (in this example there are none). By definition, lim z→1 ϕ(z) = 1, thus π(0) = 1 -ρ, where ρ = λ/µ. Decomposing the previous expression in partial fractions, one has

ϕ(z) = µ(1 -ρ) z -1 -1 P (z) = 1 -ρ 1 -ρz = (1 -ρ) +∞ i=0 ρ i z i and deduces π(i) = (1 -ρ)ρ i , for i ∈ N,

Ergodicity

In this document, the notion of ergodicity of Markov processes is very important as it plays a major role in the analyses of problems involving scaling techniques, particularly for the study of large loss networks in the framework proposed by Hunt and Kurtz [START_REF] Hunt | Large loss networks[END_REF]. The ergodicity of a Markov processes can be loosely understood as the equivalent concept to stability in dynamical systems, meaning that the system does not "explode" and that it has an unique invariant distribution.

In terms of queueing systems and networks, the easiest way to think of ergodicity is to consider that the queue lengths (or waiting times) do not go to infinity (or "explode" as mentioned before). For instance, in the M/M/1, the stability is given by the direct relation between arrival and service rates. The queue is stable if λ < µ or transient ("exploding") if λ > µ or null recurrent if λ = µ. The last case is a critical case and those are not considered in this thesis.

As exposed in the next section, a frequent approach for the determination of the ergodicity conditions of Markov processes is the analysis of the fluid limits associate with the processes. A Markov process is ergodic if all of its fluid limits converge to zero in a finite time (see Corollary 9.8 of Robert [Rob03, p. 259]) and see the subsequent sections for a definition of fluid limits.

Scaling Techniques

Throughout this thesis, we have to deal with Markov processes whose invariant distribution may or may not exist or may be too complicated to be calculated for obtaining practical information about the systems behaviour and performance. Therefore, we search for methods that facilitate the study of complex systems through simple models without neglecting however the main features of the system's functioning. For instance, in order to catch interesting aspects of some processes living in large state spaces, we may need to accelerate its time scale and shrink its state space, otherwise we cannot observe changes from one instant to another. The scaling considered in this thesis is of first order (functional law of large numbers). In the analysed cases, the renormalised version of a Markov process (X(t)) converges to a dynamic system (x(t)), which is the solution of some ordinary differential equation ẋ(t) = f (x, t) related to the drifts of the original Markov process. Studying the equilibrium (and transient) properties of this dynamic system allows us to retrieve key information about the associated Markov process.

Fluid Limits A fluid limit is an asymptotic description of sample paths of a Markov process with a large initial state, after the renormalisation of space and time to capture first order phenomena in the evolution of the Markov process. The renormalisation consists in accelerating the time proportionally and contracting the space inversely proportionally to the size of the initial state of the process. Note that the renormalised process starts on the unit sphere of some normed vector space. We investigate the behaviour of the renormalised process when the norm of its initial state tends to infinity.

Fluid limits are a convenient tool for the study of Markov processes behaving like random walks (at least locally). Using the same framework deployed in Rybko and Stolyar [START_REF] Rybko | Ergodicity of stochastic processes describing the operation of open queueing networks[END_REF], we are able to derive sufficient conditions for the process to be ergodic based on the contraction feature of its fluid limits. If the fluid limits of a Markov process are absorbed (reach and stay) at 0 in a deterministic finite time, then the process is ergodic. See Robert and Véber [START_REF] Ph | A stochastic analysis of resource sharing with logarithmic weights[END_REF] for an interesting application of fluid limits in the analysis of processor sharing queueing systems.

Consider the stochastic process (X(t)) which takes values in the state space S ⊆ Z d with X(0) = x and d ∈ N * . If the norm x = |x 1 | + • • • + |x d | = N then a fluid limit associated with the process (X(t)) is a stochastic process which is one of the possible limits of the process

X N (t) = X (N t) N
when N goes to infinity. Note that x/N is an element in the unit sphere of R d . For a simple example, consider the M/M/1 queue with arrival rate λ and service rate µ. Using fluid limits, we are able to show in a straightforward manner that the stability condition for such a system is simply given by λ < µ, or ρ < 1 for ρ = λ/µ. Let us denote by L(t) the number of customers in the queue at time t ≥ 0. Therefore, L(t) can be written as the solution of the following SDE

dL(t) = N λ (dt) -N µ (dt)1 {L(t -)≥0} , Chapter 1 1.3. Mathematical Framework
with L(0) = N . Consider now the renormalised process L N (t) = L(N t)/N , for t ≥ 0 and the hitting time

T 0,N = inf {t > 0 : L(t) = 0} .
For τ N = T 0,N /N , the Strong Law of Large Numbers yields the identity lim N →+∞ τ N dist.

= 1/(µ -λ). Thus, when N goes to infinity the following convergence holds for t < τ N

L N (t) = 1 + N λ ]0, N t] -N µ ]0, N t] N dist. = 1 + (λ -µ)t.
Using a simple coupling argument, we have that lim N →+∞ L N (t) = 0, for t > τ N . Hence, the following convergence holds for t ≥ 0 lim

N →+∞ L N (t) dist. = (1 + (λ -µ)t) + .
were (a) + = max(0, a) for a ∈ R. If λ < µ, then the fluid limits of (L(t)) are absorbed at 0 and the queue is stable. Figure 1.4 illustrates the adherence of the fluid limits of a typical M/M/1 queue and the evolution of the number of customers in this system where L(0) = N . This example is particularly remarkable because it illustrates the linear relation between the initial number of customers N in a M/M/1 queue and the time it takes for this queue to become empty T 0,N . Assume that the installed capacity in the system and the request arrival rate are sizeable i.e. of same order of magnitude. The server capacity is scaled up by a factor N ∈ N * and the request arrival rate is scaled up accordingly, i.e.

λ j → λ j N and C → cN .
for 1 ≤ j ≤ J. In the following, we consider two examples of the application of such technique to illustrate its power.

The M/M/N/N queue in Kelly's regime As a first illustration of the usage of Kelly's framework, consider a system equipped with N servers, where jobs arrive with rate λN (Poisson) and stay during a time exponentially distributed with mean 1/µ. Consider also that this system is under heavy traffic (or saturated), such that λ > µ. Let L N (t) describe the number of jobs in the system at time t ≥ 0 and m N (t) = N -L N (t) the number of free servers at time t. We assume that the system is saturated at time t = 0, with L N (0) = N . It is simple to see that the transition rates of process (m N (t)), for x ∈ {0, . . . , N }, are given by

x → x -1 N λ1 {x>0} x → x + 1 (N -x)µ.
We note that this process lives in the time scale t → tN . We define the random walk (m(t)) on the extended real line, such that, for n ∈ N, the transitions n → n + 1 and n → n -1 occur respectively at rates µ and λ (if n > 0). We denote by π the invariant distribution of (m(t)), which is a geometric distribution with parameter µ/λ. Using some technical arguments, we can show that, when N goes to infinity, the process (m N (t/N )) has the same invariant distribution π of (m(t)), hence the probability of a customer being blocked is simply given by π(0) = 1 -1/ρ, with ρ = λ/µ. Furthermore, it is simple to see that if ρ < 1, then after some (random) time the process (m N (t))/N converges to 1 -ρ when N goes to infinity. The system is therefore either underloaded (λ < µ) and then, with probability 1, there is always free servers (no customer is lost with probability 1), or the system is overloaded (λ > µ) and the blocking probability is simply given by 1 -µ/λ. This short example shows how Kelly's regime is a powerful tool for the characterisation of large scale systems. When N goes to infinity, the blocking probability in this system is simply (1 -1/ρ) + for ρ > 0. Note that Kelly's method relies on capturing the deterministic behaviour of the system: a "flow" intensity N λ of arriving jobs which are replaced by a flow of jobs that leave the system with rate N µ. In this deterministic setting, the blocking rate in an interval [0, t] is given by the ratio of the number of arriving customers, N λt, minus the customers which are served directly, N µt, and the arriving customers, or equivalently, (N λt -N µt)/(N λt) = 1 -µ/λ. The M/M/N/N queue under heavy traffic and two types of customers We pass on to a second example illustrating Kelly's regime. Consider this time a system similar to the one presented before, equipped with N ∈ N servers and hosting two types of jobs j = {1, 2}. Jobs of type j arrive into the system with rate λ j N (Poisson) asking for a A j ∈ N servers, where A 1 = 1, and A 2 = a > 1. If there are enough idle servers to fulfil the customer's requirements, the job is accepted and stays in the system during a certain service time which is exponentially distributed with mean 1/µ j . Otherwise the job is rejected. We consider a saturated system, meaning that, under Kelly's regime [Kel86, Kel91], ρ 1 + aρ 2 > 1, with ρ j = λ j /µ j for 1 ≤ j ≤ 2. Using the same notation as before, let L N,j (t) describe the number of jobs of type j in the system and m N (t) = N -L N,1 (t) -aL N,2 (t) the number of free servers at time t ≥ 0. The process (L N (t)) = ((L N,1 (t)/N, L N,2 (t)/N )) is given by, for 1 ≤ j ≤ 2,

L N,j (t) = L N,j (0) + M N,j (t) + λ j t 0 1 {m N (s)≥A j } ds -µ j t 0 L N,j (s) ds, where (M N (t)) = ((M N,1 (t), M N,2 (t))
) is a Martingale, whose increasing predictable process at time t is given by, for 1 ≤ j ≤ 2,

M N,j (t) = 1 N λ j t 0 1 {m N (s)≥A j } ds + µ j t 0 L N,j (s) ds .
It can be shown that (M N (t)) becomes negligible of order 1/ √ N as N goes to infinity.

The process (L N (t)) evolves in the t → t time scale while the process (m N (t)) evolves in the t → N t time scale. The system is governed by the Chapter 1 1.3. Mathematical Framework time-scale interaction between these two processes. In particular, the acceptance and rejection rates of jobs are determined by the equilibrium properties of the process (m N (t)), which are influenced by the (renormalised) number of each type of customer. To study such a process, we introduce a random walk on N ∪ {+∞} as follows: for fixed x ∈ D = {x ∈ R 2 + : x 1 + ax 2 ≤ 1}, we define the process (m x (t)) on N ∪ {+∞}, whose transitions occur from n to n at rate

µ j x j if n = n + A j , λ j 1 {n≥A j } if n = n -A j and 0 otherwise. It is simple to determine that if x ∈ ∆ = {x ∈ D : µ 1 x 1 + aµ 2 x 2 < λ 1 + aλ 2 , x 1 + ax 2 = 1}
then the Markov process (m x (t)) is ergodic on N. In this case its unique invariant distribution is denoted by π x = (π x (n), n ∈ N) (see for instance Bean et al. [START_REF] Bean | Asymptotic analysis of single resource loss systems in heavy traffic, with applications to integrated networks[END_REF] and Fricker et al. [START_REF] Fricker | On the fluid limits of some loss networks[END_REF][START_REF] Fricker | A degenerate central limit theorem for single resource loss systems[END_REF]). For convenience, we extend the definition of π x , such that if x ∈ D \ ∆, then the unique invariant distribution of (m x (t)) on N ∪ {+∞} is a Dirac mass at infinity δ +∞ .

Using the same method as Hunt and Kurtz [START_REF] Hunt | Large loss networks[END_REF], one gets the analogue of Theorem 3 of this reference. For any function f with finite support on N we have the following convergence lim

N →+∞ L N,1 (t) N , L N,2 (t) N , t 0 f (m N (s)) ds dist. = l 1 (t), l 2 (t), t 0 N f (u)π l(s) (du) ds ,
where l 1 (t) and l 2 (t) satisfy the following differential equations

lj (t) = -µ j l j (t) + λ j if l 1 + al 2 < 1, -µ j l j (t) + λ j π l(t) ([A j , . . . , +∞[) if l 1 + al 2 = 1, (1.4)
with lim N →+∞ L N,j (0) = l j (0) for 1 ≤ j ≤ 2. Note that we have indeed a convergence in distribution since, for any x ∈ D, (m x (t)) has exactly one invariant distribution. For this particular loss system under heavy traffic, there are no fixed points x ∈ R 2 + such that x 1 + ax 2 < 1 and x j = ρ j . Thus, if this system has an equilibrium point, it lays on the frontier x 1 + ax 2 = 1which sounds intuitive for a saturated system. Using the balance equations of (m x (t)), it is simple to see that if x j = ρ j β A j , for 1 ≤ j ≤ 2, then π x is a geometric distribution with parameter 0 < β < 1. Finally, if β is the unique solution in the interval (0, 1) of

ρ 1 β + aρ 2 β a = 1, (1.5)
such that x = (ρ 1 β, ρ 2 β a ) satisfies Equation (1.4), then x is the unique Equilibrium point of (l(t)) (located in the frontier x 1 +ax 2 = 1). Equation (1.5) is referred as Kelly's Fixed Point Equation (see Kelly Kelly1991).

Coexistence of distinct Time Scales

While investigating large circuit switching systems ([Kel86, Kel91]), Kelly observed that the macroscopic (and

ρ 1 1 ρ 2 1 a 1 (t) 2 (t) 0 ∆ x Figure 1
.6 -Limiting sample paths of an overloaded loss system

The Equilibrium point x is determined in Equation (1.5). Note that if l(t 0 ) ∈ ∆, for some t 0 ≥ 0, then l(t) ∈ ∆ for any t > t 0 .

slow) behaviour of these systems is intrinsically related with the local equilibrium of the microscopic (and fast) process with the parameters of the fast process depending on the slow process. For the loss networks, the process (L N (t)) evolves in the t → t time scale, since its transitions +e j occur at rate λ j and -e j at rate µ j L N,j (t), for 1 ≤ j ≤ 2, whereas the process (m N (t)) evolves in the much faster t → N t time scale, with transitions -A j and +A j occurring respectively at rates µ j L N,j and N λ j 1 {m≥A j } , for 1 ≤ j ≤ 2. When the scaling factor N is sufficient large, we observe the separation of these time scales which then coexist in a separate manner but still influence each other. The interplay of these processes is based on the Stochastic Averaging Principle (SAP). The dynamics of the limiting trajectories of the slow process are governed by the local equilibrium of the (infinitely) faster process, whose transitions depend on the slow process, seen as fixed by the fast process.

The averaging phenomenon was already established in the context of deterministic dynamical systems (see for instance Chapter 4 of Guckenheimer and Holmes [GH83, p. 168]). Hunt and Kurtz [START_REF] Hunt | Large loss networks[END_REF] further develop a convenient framework for the analysis of time-scale interaction in the framework of loss systems. However, the usage of this a framework is not straightforward in stochastic contexts due to the difficulty of determining the regularity of the properties of the invariant distributions of the fast processes.

Presentation of the following chapters

The concepts, techniques and models presented in this introduction are regularly used in the following chapters. The systems analysed in this thesis Chapter 1 1.4. Presentation of the following chapters are investigated under Markovian assumptions, i.e. Poison arrivals and exponential service times. The scaling techniques seen before are widely used in every chapter in the search for (good) approximations of the (macro-and microscopic) behaviour of these systems as well as the derivation of ergodicity conditions of some of the processes. The invariant distribution of the keyprocesses are often obtained using the framework of kernel problems and the toolbox of real and complex analysis. This thesis provides additions to the framework of the stochastic analysis of large scale systems through the exploration of Markovian models and limiting properties of large scale systems. The aim is to address the new perspectives and problems of policy design due to the changes in the architecture of Cloud Computing systems and the evolution of related technologies.

The four chapters of this thesis are somewhat related (at least in the methods deployed in their study). Chapter 2 is the most isolated from the others, since it focuses on a resource sharing policy for Video on Demand systems. The subsequent three chapters, focus on cooperative schemes between decentralised (smaller) data centres. In Chapter 3 an offloading policy is study in the context of multi-resource systems. In Chapter 4 and Chapter 5 two related offloading policies are investigated.

Allocation of resources with downgrading

In collaboration with: Christine Fricker, Fabrice Guillemin and Philippe Robert Published on: Advances in Applied Probability. vol. 49 iss. 2 doi:10.1017/apr.'.15

In the second chapter, we offer some insights about the introduction of (scaled) threshold in adaptation policies for resource sharing in Video on Demand systems. We consider a server with large capacity delivering video files encoded in various resolutions. We assume that the system is under saturation in the sense that the total demand exceeds the server capacity C. In such case, requests may be rejected. For the policies considered in this chapter, instead of rejecting a video request, it is downgraded. When the occupancy of the server is above some fixed threshold C 0 < C, the server delivers the video at a minimal bit rate. For these policies, request blocking is thus replaced with bit rate adaptation.

We assume that customers request video files encoded at various rates, say, A j for j = 1, . . . , J, with 1 = A 1 < A 2 < • • • < A J . Jobs of class j ∈ {1, . . . , J} require bit rate A j , arrive according to a Poisson process with rate λ j and have an exponentially distributed transmission time with rate µ j . We denote by L j (t) the number of jobs of type j in the system at time t, and (L(t)) = ((L j (t), 1 ≤ j ≤ J)) the Markov process which describes the state of such a system. The invariant distribution of (L(t)) does not have an explicit expression. Note that this system is closely related with the loss systems introduced previously, thus, to study this allocation scheme, a scaling approach is used. It is assumed that the server capacity is very large, namely scaled up by a factor N . The bit rate adaptation threshold and the request Chapter 1 1.4. Presentation of the following chapters arrival rates are scaled up accordingly, i.e.

λ j → λ j N 1 ≤ j ≤ J, C 0 → c 0 N and C → cN.
In the scaled version of the system, the process associated with the occupancy of the server (around the threshold) is denoted by (m N (t)) = ( J j=1 A j L N j (t)-C 0 ) and L N j (t) denotes the number of jobs of type j in the system at time t. We show that, when the scaling factor N goes to infinity, the process (m N (t)) converges to the random walk defined as follows: for λ, µ, ∈ R J + , let (m (t)) be the Markov jump process on Z whose non-negative elements of its Q-matrix, Q = (q (n, n ), n, n ∈ Z), are given by

q (n, n ) =            Λ if n = n + 1 and n ≥ 0, λ j if n = n + A j and n < 0, µ j j if n = n -A j , 0 otherwise, where Λ = λ 1 + λ 2 + • • • + λ J and 1 = A 1 < A 2 < • • • < A J .
Note n ≥ 0 represents the states where the link occupation rate is above the threshold c 0 , and in this case, all the arriving requests are treated as class 1 and otherwise, if n < 0, the customers are threaded as they request.

Using some methods from real and complex analysis related to Wiener-Hopf factorisation, we are able to obtain the unique stationary invariant distribution of such a random walk when it exists. We can derive an asymptotic expression of the key performance measure of such a policy, since, in the limiting scenario, the stationary probability that a request is transmitted at requested bitrate is given by the probability that the process (m N (t)) is on the negative half line Z * -and is the equilibrium point of this system. Our main result shows that, if c 0 is conveniently chosen, such that

Λ µ 1 < c 0 < J j=1 A j λ j µ j ,
then, as N goes to infinity, -the equilibrium probability of rejecting a job converges to 0, and -the equilibrium probability of accepting a job at requested bitrate converges to

π -def. = (c 0 -Λ/µ 1 )   J j=1 λ j µ j A j -Λ/µ 1   .
We compare this policy with the standard loss system (where no admission control is performed), and show that for systems where the access refusal is very expensive, our policy is an effective method for resource allocation between clients with very diversified demands on terms of servers. As we show, under our scheme, the system can run without rejecting customers (with probability 1 when N goes to infinity) at the price of downgrading some jobs to the minimum available service quality.

In this chapter, one of the main technical difficulties is to prove the convergence of invariant distributions of the process (m N (t)). We need to show simultaneously that the process (L N (t))/N converges in distribution to some dynamical system, which is governed by the equilibrium properties of the process (m N (t)), while the invariant distribution of (m N (t)) is influenced by (L N (t))/N . However, the regularity properties of the process (m N (t)) are not straight forward, since the invariant distribution of such a process depends on where the process (L N (t))/N is. Therefore, we need to show additionally that in the dynamical system's path (towards its equilibrium point), after some random time, the process (m N (t)) remains in the region where it is ergodic.

Cooperation mechanisms in multi-resource services

In collaboration with: Christine Fricker, Fabrice Guillemin and Philippe Robert

In the third chapter, we investigate the deployment of a local state-aware policy for load balancing in the multi-resource framework. We consider a Cloud Computing environment where virtual machines (or jobs) are instantiated upon the allocation of GB RAM and CPU core, denoted resource i ∈ {1, 2}, respectively. The system is composed of two parallel data centres denoted k ∈ {1, 2}. Each data centre k is equipped with some large (but finite) amount R k of GB RAM and C k of CPU cores. To capture the particular aspect of resource specialised (unbalanced) virtual machines, we consider two types of jobs arriving to the system, denoted type j ∈ {1, 2}. Jobs of type 1 require R > 1 GB RAM and 1 CPU core, whereas jobs of type 2 require 1 GB RAM and C > 1 CPU core. Requests of type j arrive at data centre k according to a Poisson process with rate λ j,k , for 1 ≤ j, k ≤ 2. The duration of the service of type j jobs is exponentially distributed with mean 1/µ j . We suppose that on the aggregate level the system is properly dimensioned, i.e.

R(λ

1,1 + λ 1,2 ) µ 1 + λ 2,1 + λ 2,2 µ 2 < R 1 + R 2 and λ 1,1 + λ 1,2 µ 1 + C(λ 2,1 + λ 2,2 ) µ 2 < C 1 + C 2 ,
but that locally each data centre has one resource which is saturated (with loss of generality, we consider resource p is saturated at data centre p, for 1 ≤ p ≤ 2), meaning

λ 1,1 µ 1 R + λ 2,1 µ 2 > R 1 and λ 1,2 µ 1 + λ 2,2 µ 2 C > C 2 .
Note that this case is the most interesting and challenging scenario to be investigated. The other configurations fall back into simpler models, which can be analysed using the classical toolbox of queueing theory. We propose Chapter 1 1.4. Presentation of the following chapters a threshold policy to handle local saturation and control the offloading of VM from one data centre to another. Thresholds are chosen to anticipate sufficiently in advance potential shortages of any resource in any data centre. The idea is to buffer some resources to avoid the complete jamming of a processing facility due to the lack of either resource. Jobs with the largest demand of the locally saturated resource are systematically forwarded to the other data centre when the threshold level is reached. Other requests are forwarded only if they cannot be accommodated locally. A threshold is set for the most demanded resource at each data centre, selected by the relation between its local load and capacity. The study is therefore restricted to the implementation of thresholds 0 < δ p < 1 in data centre p to avoid exhaustion of resource p by offloading the jobs of type p, for 1 ≤ p ≤ 2.

R 1 R 1 δ 1 C 1 #1 A 1 =(R, 1) λ 1,1 A 2 =(1, C) λ 2,1 R 2 C 2 C 2 δ 2 #2 A 1 =(R, 1) λ 1,2 A 2 =(1, C) λ 2,2 Figure 1.7 -System configuration
Jobs of type j arriving at data centre k with rate λ j,k requesting A j units of the resources. Data centre k is equipped with a finite capacity or each resource, namely R k GB RAM and C k CPU core, for 1 ≤ k ≤ 2. Clients of type p are forwarded to data centre 3 -p when resource p is being used above the threshold 0

< δ p < 1, for 1 ≤ p ≤ 2.
Using Kelly's scaling, we are able to express the performance of the system in terms of the invariant distribution of the random walk on the plane Z 2 in the Markovian environment defined as follows: for fixed

x = (x j,k , 1 ≤ j, k ≤ 2) ∈ R 2×2 + , let (U x (t)) = ((U x,h (t), U x,v (t)
)) be a semi-homogeneous random walk on Z 2 whose transitions occur from n = (n 1 , n 2 ) to n + b at rate

             λ 1,1 1 {n 1 <0} if b = (R, 0), λ 2,1 + λ 2,2 1 {n 2 ≥0} if b = (1, 0), λ 1,2 + λ 1,1 1 {n 1 ≥0} if b = (0, 1), λ 2,2 1 {n 2 <0} if b = (0, C) and            µ 1 x 1,1 if b = -(R, 0), µ 2 x 2,1 if b = -(1, 0), µ 1 x 1,2 if b = -(0, 1), µ 2 x 2,2 if b = -(0, C).
Chapter 1 1.4. Presentation of the following chapters Note that n 1 ≥ 0 represents the fact that the utilisation rate of resource 1 in data centre 1 is above the threshold δ 1 (the same for n 2 regarding resource 2 at data centre 2). We show that when N goes to infinity, the probability of a job being forwarded from one data centre to another given as a function of the stationary invariant distribution of this random walk i.e. the probability of this random walk to be in wither half plane determines the offloading rates between the servers. Using some fluid limits, we are able to derive the ergodicity conditions for such random walk and, resorting to the framework of kernel methods, we are able to obtain the probability which this random walk stays on each half-plane.

As main result, we show that when the scale of this system is large, we have that -the probability of rejecting jobs in both data centres converges to 0; -the probabilities of forwarding a type 2 job from data centre 1 and type 1 job from data centre 2 converge to 0;

-the probabilities of forwarding a job of type 1 from data centre 1 and type 2 from data centre 2 converge to

γ 1 (δ) def. = µ 1 (RC -1)λ 1,1 R 1 δ 1 C + C 2 δ 2 - (λ 1,1 + λ 1,2 ) µ 1 - C (λ 2,1 + λ 2,2 ) µ 2 ,
and

γ 2 (δ) def. = µ 2 (RC -1)λ 2,2 R 1 δ 1 + C 2 δ 2 R - R (λ 1,1 + λ 1,2 ) µ 1 - (λ 2,1 + λ 2,2 ) µ 2 .
The multi-resource characteristic of this system brings some extra difficulties for its analysis. In this chapter, we had to resort to some heuristic reasoning (which are then formally proved later in the chapter) in the analysis of the threshold parametrisation. Also, we have to rely on the fluid limits analysis to derive the ergodicity conditions of the process (U x (t)).

The results presented in this chapter are a first step towards the understanding of cooperation in multi-resource structures, still barely explored in literature -specially in the framework of stochastically modelling. The proposed policy work on a decentralised manner, a key aspect to be observed in the coming organisation of Cloud structures. We are able derive optimal threshold parameters, allowing the distributed Cloud Computing systems to meet the efficiency of a centralised system of equivalent total capacity serving the combined flows of requests.

Analysis of an offloading scheme for data centres in the framework of fog computing

In collaboration with: Christine Fricker, Fabrice Guillemin and Philippe Robert Published on: ACM ToMPECS. vol. 1 iss. 4 doi:10.1145/2950047

In the fourth chapter, we analyse, in the context of fog computing, a simple case when data centres are installed at the edge of the network and assume that if a request arrives at an data centre whose capacity is currently depleted, then it is forwarded to a neighbouring data centre with some probability (in a logical ring). We consider that data centres have a large number of servers and that traffic at some data centres is causing saturation. In this case the other data centres may help to cope with this saturation by accepting some of the rejected requests. Our aim is to qualitatively estimate the gain achieved via cooperation between neighbouring data centres. The analysis is focused on the behaviour of some pair of neighbouring data centres. See Figure 1.8.

#1

C 1 λ 1 p 1 1-p 1 1 1 if #1 saturated #2 C 2 λ 2 p 2 1-p 2 2 2 if #2 saturated Figure 1.8 -System configuration ("probabilistic" Offloading)
Implementation of a probabilistic offloading scheme between two data centres in the framework of Fog Computing. In data centre p, the capacity is denoted by C p and the arrival rates by λ p , for 1 ≤ p ≤ 2.

After proving some convergence results related to the scaling limits of loss systems for the process describing the number of free servers at both data centres, we show that the performance of the system can be expressed in terms of the invariant distribution of a reflected random walk on the positive quarter plane. For fixed l = (l 1 , l 2 ) ∈ R 2 + , we define the random walk (m l (t)) on (N ∪ {+∞}) 2 as follows: the transition from (m 1 , m 2 ) to (m 1 + a, m 2 + b) occurs at rate

           µ 1 l 1 if (a, b) = (1, 0), µ 2 l 2 if (a, b) = (0, 1), λ 1 + p 2 λ 2 1 {m 2 =0} if (a, b) = (-1, 0) and m 1 > 0, λ 2 + p 1 λ 1 1 {m 1 =0} if (a, b) = (0, -1) and m 2 > 0,
for (m 1 , m 2 ) ∈ (N∪{+∞}) 2 with the convention that +∞±x = +∞ for x ∈ N. We derive the ergodicity conditions for such a random walk using fluid limits. We are able obtain explicit formulas for the blocking rates of the system using and further developing existing results from the technical literature concerning random walks in the positive quarter plane, using some kernel methods. Numerical applications illustrate the power of the cooperation scheme, partic-Chapter 1 1.4. Presentation of the following chapters ularly focusing on the ability of such a policy to manage offloading systems, where one data centre is considerably larger than the other(s).

Analysis of a trunk reservation policy in the framework of Fog Computing

In collaboration with: Fabrice Guillemin Preprint on arXiv: 1604.03823 [START_REF] Guillemin | Analysis of a trunk reservation policy in the framework of fog computing[END_REF] We analyse a system similar to the one in the previous chapter. The system is composed of two data centres with limited capacity in terms of servers. When one request for a single server is blocked at the first data centre, this request is forwarded to the second one. To protect the requests originally assigned to the second data centre, a trunk reservation policy is introduced (i.e., a redirected request is accepted only if there is a sufficient large number of free servers at the second data centre). After rescaling the

#1 1 2 C 1 . . . #2 1 2 C 2 . . . a Λ 1 1 {N 1 <C 1 } Λ 1 1 {N 1 =C 1 } Λ 1 1 {N 1 =C 1 ,N 2 <C 2 -a} Λ 1 1 {N 1 =C 1 ,C 2 -a≤N 2 ≤C 2 } Λ 2 1 {N 2 <C 2 } Λ 2 1 {N 2 =C 2 } Figure 1.9 -System configuration ("truncated" offloading)
Implementation of a systematic offloading scheme between two data centres in the framework of Fog Computing, with trunk protection of a servers in the second data centre. In data centre p the number of requests hosted at p is denoted by N p , the capacity by C p and the arrival rates by Λ p , for 1 ≤ p ≤ 2. system, assuming that there are many servers in both data centres and that request arrival rates are high, we show that the system's performance is related to a random walk on the quarter plane. For fixed l = (l 1 , l 2 ) ∈ R 2 + , we define the random walk (m l (t)) on (N ∪ {+∞}) 2 as follows: the transition from Chapter 1 1.4. Presentation of the following chapters

(m 1 , m 2 ) to (m 1 + k, m 2 + ) occurs at rate            µ 1 l 1 if (k, ) = (1, 0), µ 2 l 2 if (k, ) = (0, 1), λ 1 1 {m 1 >0} if (k, ) = (-1, 0), λ 2 1 {m 2 >0} + λ 1 1 {m 1 =0,m 2 >a} if (k, ) = (0, -1),
where a is the threshold parameter. Note that this random walk has the particularity of having non-constant reflecting conditions on one boundary of the quarter plane. After some convergence results, we derive the ergodicity conditions for such a random walk. The main challenge of this chapter is the technical study of the kernel problem in the derivation of the invariant distribution of the aforementioned random walk. Contrary to usual reflected random walks, we have to determine three unknown functions, one polynomial and two infinite generating functions, in order to compute the stationary distribution of the random walk. We show that the coefficients of the polynomial are solutions to a linear system. After solving this linear system, we are able to compute the two other unknown functions. The blocking probabilities at both data centres are then derived. Numerical experiments are performed to estimate the gain achieved by the trunk reservation policy, contrasting with the model of the previous chapter as well as the scenario where both data centres operate independently from each other, showing the trade-off between both policies.

Chapter 2

Allocation Schemes of Resources with Downgrading

Introduction

Video streaming applications have become over the past few years the dominant applications in the Internet and generate the prevalent part of traffic in today's IP networks; see for instance Guillemin et al. [START_REF] Guillemin | Volatility of You-Tubecontent in Orangenetworks and consequences[END_REF] for an illustration of the application breakdown in a commercial IP backbone network. Video files are currently downloaded by customers from large data centres, like Google's data centres for YouTube files. In the future, it is very likely that video files will be delivered by smaller data centres located closer to end users, for instance cache servers disseminated in a national network. It is worth noting that as shown in Guillemin et al. [START_REF] Guillemin | Experimental analysis of caching efficiency for YouTubetraffic in an ISPnetwork[END_REF], caching is a very efficient solution for YouTube traffic. While this solution can improve performances by reducing delays, the limited capacity of those servers in terms of bandwidth and computing can cause overload.

One possibility to reduce overload is to use bit rate adaptation. Video files can indeed be encoded at various bit rates (e.g., small and high definition video). If a node cannot serve a file at a high bit rate, then the video can be transmitted at a smaller rate. It is remarkable that video bit rate adaptation has become very popular in the past few years with the specification of MPEG-DASH standard where it is possible to downgrade the quality of a given transmission, see Schwarz et + 15] (see also Fricker et al. [FGRT16b]). Adaptive streaming is also frequently used in mobile networks where bandwidth is highly varying. In this chapter, we investigate the effect of bit rate adaptation in a node under saturation.

Downgrading Policy

We assume that customers request video files encoded at various rates, say,

A j for 1 ≤ j ≤ J, with 1 = A 1 < A 2 < • • • < A J .
Jobs of class j ∈ {1, . . . , J} require bit rate A j . The total capacity of the communication link is C. If = ( j ) is the state of the network at some moment, with j being the number Chapter 2 2.1. Introduction of class j jobs, the quantity A, = A 1 1 + • • • + A J J has to be less than C. The quantity A, is defined as the occupancy of the link. The algorithm has a parameter C 0 < C and works as follows: If there is an arrival of a job of class 1 ≤ j 0 ≤ J, if -A, < C 0 then the job is accepted; -C 0 ≤ A, < C then the job is accepted but as a class 1 job, i.e. it has an allocated bit rate of A 1 = 1 and service rate µ 1 ; -A, = C, the job is rejected.

For 1 ≤ j ≤ J, jobs of class j arrive according to a Poisson process with rate λ j and have an exponentially distributed transmission time with rate µ j . Additionally, it is assumed that

µ 1 ≤ min(µ j , 2 ≤ j ≤ J).

A Scaling Approach

To study this allocation scheme, a scaling approach is used. It is assumed that the server capacity is very large, namely scaled up by a factor N . The bit rate adaptation threshold and the request arrival rates are scaled up accordingly, i.e.

λ j → λ j N, 1 ≤ j ≤ J, C 0 → c 0 N and C → cN.
(2.1)

Performances of the algorithm. Our main result shows that, for the downgrading policy and if c 0 is chosen conveniently, then 1. the equilibrium probability of rejecting a job converges to 0 as N goes to infinity;

2. the equilibrium probability of accepting a job without downgrading it converges to

π -def. =   c 0 µ 1 - J j=1 λ j     µ 1 J j=1 λ j µ j A j - J j=1 λ j   ,
as N goes to infinity. See Theorem 2.2 and Corollary 2.1.

The above formula gives an explicit expression of the success rate of this allocation mechanism. The quantity 1 -π -, the probability of downgrading requests, can be seen as the "price" of the algorithm to avoid rejecting jobs. The scaling (2.1) has been introduced by Kelly to study loss networks (see Kelly [Kel86,[START_REF] Kelly | Loss networks[END_REF]). The transient behaviour of these networks under this scaling has been analysed by Hunt and Kurtz [HK94]. This last reference provides essentially a framework to establish convenient convergence theorems involving stochastic averaging principles. This line of research has been developed in the 1990's to study uncontrolled loss networks where a request is rejected as soon as its demand cannot be accepted.

When the demand can be adapted to the state of the network, for controlled loss networks, several (scarce) examples have been also analysed during that Chapter 2

Introduction period of time. One can mention Bean et al. [BGZ95, BGZ97], Zachary and

Ziedins [START_REF] Zachary | A refinement of the Hunt-Kurtz theory of large loss networks, with an application to virtual partitioning[END_REF][START_REF] Zachary | Loss Networks[END_REF] for example. Our model can be seen as a "controlled" loss networks instead of a pure loss network. Controlled loss networks may have mechanisms such as trunk reservation or may allocate requests according to some complicated schemes depending on the state of the network. In our case, the capacity requirements of requests are modified when the network is in a "congested" state.

Contrary to classical uncontrolled loss networks, as it will be seen, the Markov process associated to the evolution of the vector of the number of jobs for each class is not reversible. Additionally, the invariant distribution of this process does not seem to have a closed form expression. Kelly's approach [Kel86] is based on an optimisation problem, it cannot be used in our case to get an asymptotic expression of some characteristics at equilibrium. For this reason, the equilibrium behaviour of these policies is investigated in a two step process:

1. Transient Analysis. We investigate the asymptotic behaviour of some characteristics of the process on a finite time interval when the scaling parameter N goes to infinity.

2. Equilibrium. The stability properties of the limiting process are analysed, we prove that the equilibrium of the system for a fixed N converges to the equilibrium of the limiting process.

For our model, the transient analysis involves the explicit representation of the invariant distribution of a specific class of Markov processes. It is obtained with complex analysis arguments. As it will be seen, this representation plays an important role in the analysis of the asymptotic behaviour at equilibrium. It should be noted that related models have recently been introduced to investigate resource allocation in a cloud computing environment where the nodes receive requests of several types of resources. We believe that this domain will receive a renewed attention in the coming years. See Stolyar [START_REF] Stolyar | An infinite server system with general packing constraints[END_REF][START_REF] Stolyar | Pull-based load distribution in large-scale heterogeneous service systems[END_REF] and Fricker et al. [START_REF] Fricker | Analysis of an offloading scheme for data centers in the framework of fog computing[END_REF] for example. In some way one could say that the loss networks are back and this is also a motivation of this chapter to shed some light on the methods that can be used to study these systems.

Outline of the chapter

We consider a system in overload. Because of bit rate adaptation, requests may be downgraded but not systematically rejected as in a pure loss system. As it will be seen, the stability properties of this algorithm are linked to the behaviour of a Markov process associated to the occupation of the link. Under exponential assumptions for inter-arrival and service times, this process turns out to be, after rescaling by a large parameter N , a bilateral random walk instead of a reflected random walk as in the case of loss networks. Using complex analysis methods, an explicit expression of the invariant distribution of this random walk is obtained. With this result, the asymptotic expression of the probability that, at equilibrium, a job is transmitted at its requested rate (and therefore does not experience a bit rate adaptation) is derived. This chapter is organised as follows: In Section 2.2, we present the model used to study the network under some saturation condition. Convergence results when the scaling factor N tends to infinity are proved in Section 2.3. The invariant distribution of a limiting process associated to the occupation of the link is computed in Section 2.4 by means of complex analysis techniques. Applications are discussed in Section 2.5.

Model description

One considers a service system where J classes of requests arrive at a server with bandwidth/capacity C. Requests of class j, 1 ≤ j ≤ J, arrive according to a Poisson process N λ j with rate λ j . A class j request has a bandwidth requirement of A j units for a duration of time which is exponentially distributed with parameter µ j . For the systems investigated in this chapter, there is no buffering, requests have to be processed at their arrival otherwise they are rejected. Without any flexibility on the resource allocation, this is a classical loss network with one link. See Kelly [START_REF] Kelly | Loss networks[END_REF] for example. This chapter investigates allocation schemes which consist of reducing the bandwidth allocation of arriving requests to a minimal value when the link has a high level of congestion. In other words the service is downgraded for new requests arriving during a saturation phase. If the system is correctly designed, it will reduce significantly the fraction of rejected transmissions and, hopefully, few jobs will in fact experience downgrading.

Downgrading policy D(C 0 )

We introduce C 0 < C, the parameter C 0 will indicate the level of congestion of the link. It is assumed that the vector of integers A = (A j ) is such that

A 1 = 1 < A 2 < • • • < A J .
The condition A 1 = 1 is used to simplify the presentation of the results and to avoid problems of irreducibility in particular but this is not essential.

If the network is in state = ( j ) and if the occupancy A, is less than C 0 , then any arriving request is accepted. If the occupancy is between C 0 and C -1, it is accepted but with a minimal allocation, as a class 1 job. Finally it is rejected if the link is fully occupied, i.e. A, = C. It is assumed that µ 1 ≤ µ j , for 1 ≤ j ≤ J, i.e. class 1 jobs are served with the smallest service rate.

Mathematically, the stochastic model is close to a loss network with the restriction that a job may change its requirements depending on the state of the network. This is a controlled loss network, see Zachary and Ziedins [START_REF] Zachary | Loss Networks[END_REF]. It does not seem that, like in uncontrolled loss networks, the associated Markov process giving the evolution of the vector has reversibility properties, or that its invariant distribution has a product form expression. Related schemes with product form are trunk reservation policies for which requests of a subset of classes are systematically rejected when the level of congestion of the link is above some threshold. See Bean et al. [START_REF] Bean | Asymptotic analysis of single resource loss systems in heavy traffic, with applications to integrated networks[END_REF] and Zachary and Ziedins [START_REF] Zachary | A refinement of the Hunt-Kurtz theory of large loss networks, with an application to virtual partitioning[END_REF] for example. Concerning controlled loss networks, mathematical results are more scarce. One can mention networks where jobs requiring congested links are redirected to less loaded links. Several mathematical approximations have been proposed to study these models. See the surveys Kelly [START_REF] Kelly | Loss networks[END_REF] and Zachary and Ziedins [START_REF] Zachary | Loss Networks[END_REF]. In our model, in the language of loss networks, the control is on the change of capacity requirements instead of a change of link.

Scaling Regime

The invariant distribution being, in general, not known, a scaling approach is used. The network is investigated under Kelly's regime, i.e. under heavy traffic regime with a scaling factor N . It has been introduced in Kelly [Kel86] to study the equilibrium of uncontrolled networks. The arrival rates are scaled by N : λ j is replaced by λ j N as well as the capacity C by C N and the threshold C 0 by C N 0 which are such that

C N = cN + o (N ) and C N 0 = c 0 N + o (N ) , for 0 < c 0 < c.
Definition 2.1. For 1 ≤ j ≤ J and t ≥ 0, L N j (t) denotes the number of class j jobs at time t in this system and L N (t) = (L N j (t), 1 ≤ j ≤ J).

It will be assumed that the system is overloaded when the jobs have their initial bandwidth requirements

A, ρ > c and Λ µ 1 < c, (R) with Λ = λ 1 + • • • + λ J and ρ j = λ j /µ j , 1 ≤ j ≤ J.
The first condition gives that, without any change on the bandwidth requirement of jobs, the system will reject jobs. The second condition implies that the network could accommodate all jobs without losses (with high probability) if all of them would require the reduced bit rate A 1 = 1 and service rate µ 1 . It should be noted that, from the point of view of the design of algorithms, the constant c 0 has to be defined. If one takes c 0 ∈ (Λ/µ 1 , c) then,

A, ρ > c 0 , (R 1 ) Λ µ 1 < c 0 . (R 2 )
hold.

If A, ρ < c, it is not difficult to see that the system is equivalent to a classical underloaded loss network with one link and multiple classes of jobs. There is, of course, no need to use downgrading policies since the system can accommodate incoming requests without any loss when N is large. See Kelly [START_REF] Kelly | Loss networks[END_REF] or Section 6.7 of Robert [Rob03, p. 164] for example.

Scaling Results

In this section, we prove convergence results when the scaling parameter N goes to infinity. These results are obtained by studying the asymptotic behaviour of the occupation of the link around

C N 0 , m N (t) def. = A, L N (t) -C N 0 . (2.2)
In the context of loss networks, the analogue of such quantity is the number of empty places. The following proposition shows that, for the downgrading policy, the boundary C N does not play a role after some time if Condition (R 2 ) holds.

Proposition 2.1. Under Condition (R 2 ) and if the initial state is such that

lim N →+∞ L N j (0) N = (0) = ( j,0 ) ∈ S def. = {x ∈ R J + : A, x < c},
then, for ε > 0, there exists t ε ≥ 0 such that, for T > t ε , lim

N →+∞ P sup tε≤t≤T A, L N (t) < (c 0 + ε)N = 1. Proof. Define L N j (t) def. = D N 1 (t) + X N (t), D N 2 (t), . . . , D N J (t) ,
where (X N (t)) is the process of the number of jobs of an independent M/M/∞ queue with X N (0) = 0, service rate µ 1 and arrival rate Λ = λ 1 + • • • + λ J and, for 1

≤ j ≤ J, D N j (t) def. = L N j (0) k=1 1 E µ j ,k >t ,
where (E µ j ,k ) is a sequence of i.i.d. exponentially distributed random variables with rate µ j .The quantity D N j (t) is the number of initial class j jobs still present at time t. Using Theorem 6.13 of Robert [START_REF] Ph | Stochastic Networks and Queues[END_REF], one gets the convergence in distribution lim

N →+∞ X N (t) N = Λ µ 1 1 -e -µ 1 t ,
and, consequently, lim

N →+∞ 1 N A, L N (t) =   Λ µ 1 1 -e -µ 1 t + J j=1 A j j,0 e -µ j t   . (2.3) Since µ 1 ≤ µ j for 1 ≤ j ≤ J, Λ µ 1 1 -e -µ 1 t + J j=1 A j j,0 e -µ j t ≤ Λ µ 1 1 -e -µ 1 t + e -µ 1 t A, (0) ≤ max(c 0 , A, (0) ),
by Condition (R 2 ). Note that the asymptotic occupancy, when N is large, remains below the initial occupancy.

If 0 < εN < C N -C N 0 and L N (0) ∈ N J such that C N 0 +εN < A, L N (0) < C N , let τ N def. = inf t > 0 : A, L N (t) ≤ C N 0 + ε 2 N
then, on the event {τ N > T }, the downgrading policy gives that the identity in distribution

L N j (t) , 0 ≤ t ≤ T dist. = L N j (t) , 0 ≤ t ≤ T (2.4) holds. Condition (R 2 ) gives the existence of t ε such that Λ µ 1 1 -e -µ 1 tε + J j=1 A j j,0 e -µ j tε = c 0 + ε 2 .
Convergence (2.3) shows that the sequence (τ N ) converges in distribution to t ε . Note that, if S ∈ (t ε , T ), as long as the process ( A, L N (t) ) stays above C N 0 on I = [t ε , S), a relation similar to (2.4) holds. Using again Convergence (2.3), one gets that, as N goes to infinity, the process ( A, L N (t) /N ) remains below c 0 + ε with probability close to 1 on I. The proposition is proved.

We are now investigating the asymptotic behaviour of the process (m N (t)) defined by Relation (2.2). The variable indicates if the network is operating in saturation at time t, m N (t) ≥ 0, or not, m N (t) < 0. In pure loss networks, when N is large, up to a change of time scale, the analogue of this process, the process of the number of empty places converges to a reflected random walk on N. In our case, as it will be seen, the corresponding process is in fact a random walk on Z. Definition 2.2. For = ( j ) ∈ S, let (m (t)) be the Markov process on Z whose Q-matrix, Q , is defined by, for x ∈ Z and 1 ≤ j ≤ J,

       Q (x, x -A j ) = µ j j , Q (x, x + A j ) = λ j , if x < 0, Q (x, x + 1) = Λ, if x ≥ 0, (2.5) with Λ def. = λ 1 + λ 2 + • • • + λ J .
Chapter 2

Scaling Results

The following proposition summarises the stability properties of the Markov process (m (t)).

Proposition 2.2. If

= ( j ) ∈ S, then the Markov process (m (t)) is ergodic if ∈ ∆ 0 with ∆ 0 def. =    x ∈ S : A, x = c 0 , J j=1 (λ j -µ j x j )A j > 0 and Λ < J j=1 µ j x j A j    (2.6)
π denotes the corresponding invariant distribution.

Proof. The Markov process (m (t)) on Z behaves like a random walk on each of the two half-lines N and Z * -. Definition (2.6) implies that if ∈ ∆ 0 , then the drift of the random walk is positive when in Z * -and negative when in N. This property implies the ergodicity of the Markov process using the Lyapounov function F (x) = |x|, for example. See Corollary 8.7 of Robert [START_REF] Ph | Stochastic Networks and Queues[END_REF] for example.

One now extends the expression π for the values ∈ S \ ∆ 0 . This will be helpful to describe the asymptotic dynamic of the system. See Theorem 2.1 further.

Definition 2.3. One denotes

π = δ -∞ , the Dirac measure at -∞ when ∈ ∆ -, with ∆ - def. =    x ∈ S : A, x = c 0 , J j=1 (λ j -µ j x j )A j ≤ 0    ∪    x ∈ S : A, x < c 0    and π = δ +∞ if ∈ ∆ + , with ∆ + def. =    x ∈ S : A, x = c 0 , J j=1 µ j x j A j ≤ Λ    ∪    x ∈ S : A, x > c 0    .

Stochastic Evolution Equations

For ξ > 0, denote by N ξ (dt) a Poisson process on R + with rate ξ and (N i ξ (dt)) an i.i.d. sequence of such processes. All Poisson processes are assumed to be independent. Classically, the process (L N (t)) can be seen as the unique solution to the following stochastic differential equations (SDE),

                         dL N 1 (t) = - +∞ k=1 N k µ 1 (dt)1 {k≤L N 1 (t-)} + 1 {m N (t-)<C N -C N 0 } N λ 1 N (dt) + J j=2 1 {0≤m N (t-)<C N -C N 0 } N λ j N (dt), dL N j (t) = - +∞ k=1 N k µ j (dt)1 {k≤L N j (t-)} + 1 {m N (t-)<0} N λ j N (dt), (2.7) for 2 ≤ j ≤ J, with initial condition (L N j (0)) ∈ N J such that A, L N (0) ≤ C N . Theorem 2.1 (Limiting Dynamical System). Under Condition (R 2 ), if the initial conditions are such that m N (0) = m ∈ Z and lim N →+∞ L N j (0) N = ( j (0)) ∈ S,
then there exists continuous process ( (t)) = ( j (t)) such that the convergence in distribution

lim N →+∞ L N j (t) N , t 0 f m N (u) du dist. = ( j (t)), t 0 Z f (x)π (u) (dx) du (2.8)
holds for any function f with finite support on Z. Furthermore, there exists t 0 > 0 such that ( (t), t ≥ t 0 ) satisfies the differential equations

           d dt 1 (t) = -µ 1 1 (t) + λ 1 + π (t) (N) J k=2 λ k , d dt j (t) = -µ j j (t) + λ j π (t) (Z * -), 2 ≤ j ≤ J,
(2.9)

where π , for ∈ S, is the distribution of Proposition 2.2 and Definition 2.3.

It should be noted that, since the convergence holds for the convergence in distribution of processes, the limit ( (t)) is a priori a random process.

Proof. Using the same method as Hunt and Kurtz [START_REF] Hunt | Large loss networks[END_REF], one gets the analogue of Theorem 3 of this reference. Fix ε > 0 such that c 0 + ε < c, from Proposition 2.1, one gets that the existence of t 0 such that lim

N →+∞ P sup t 0 ≤t≤T A, L N (t) < (c 0 + ε)N = 1, which implies that the boundary condition m N (t) < C N -C N
0 in the evolution equations (2.7) can be removed. Consequently, only the boundary condition of (m N (t)) at 0 plays a role which gives Relation (2.9) as in Hunt and Kurtz [START_REF] Hunt | Large loss networks[END_REF]. Note that, contrary to the general situation described in this reference, we have indeed a convergence in distribution because, for any ∈ S, (m (t)) has exactly one invariant distribution (which may be a Dirac mass at infinity) by Proposition 2.2. See Conjecture 5 of Hunt and Kurtz [START_REF] Hunt | Large loss networks[END_REF].

The following proposition gives a characterisation of the equilibrium point of the dynamical system ( (t)).

Proposition 2.3 (Fixed Point). Under Conditions (R 1 ) and (R 2 ), there exists a unique equilibrium point * ∈ ∆ 0 of the process ( j (t)) defined by Equation (2.8) given by *

1 = c 0 -π -(ρ 2 A 2 + • • • + ρ J A J ), * j = ρ j π -, 2 ≤ j ≤ J, (2.10)
where

π -def. = c 0 -Λ/µ 1 A, ρ -Λ/µ 1 , ( 2.11
)

with Λ = λ 1 + • • • + λ J . The process (m * (t)) is ergodic in this case.
Proof. Assume that there exists an equilibrium point * = ( * j ) of ( j (t)) defined by Equation (2.8), it is also an equilibrium point of the dynamical system defined by Equation (2.9), then

µ 1 * 1 = λ 1 + (λ 2 + • • • + λ J )(1 -π -), µ j * j = λ j π -, 2 ≤ j ≤ J, (2.12) with π -= π * Z * -. One gets J j=1 λ j = J j=1 µ j * j < J j=1 µ j * j A j = π - J j=1 λ j A j + (1 -π -) J j=1 λ j < J j=1 λ j A j .
(2.13)

We now show that the vector * is on the boundary, i.e.

J j=1

A j * j = c 0 .

(2.14)

If we assume that lim

N →+∞ L N j (0) N = ( * j ),
from Theorem 2.1 and the definition of (m N (t)), we know that, for the convergence of processes, the following relation holds lim

N →+∞ m N (t) N = (κ 0 ), with κ 0 def. = J j=1 A j * j -c 0 . For N 0 ∈ N, ε > 0 and N ≥ N 0 , 1 0 1 {|m N (u)|≥εN } du ≤ 1 0 1 {|m N (u)|≥εN 0 } du.
Using again Theorem 2.1 and the fact that * is an equilibrium point of the dynamical system, we have, for the convergence in distribution lim

N →+∞ 1 0 1 {|m N (u)|≤εN 0 } du = π * ([-εN 0 , εN 0 ]).
The left-hand side of the above expression can be arbitrarily close to 1 when N 0 is large. By convergence of the sequence (m N (t)/N ) to (κ 0 ), one gets that, for the convergence in distribution, the relation lim

N →+∞ 1 0 1 {|m N (u)|/N ≥ε} du = 0
holds for ε > 0, which implies that κ 0 = 0. Thus Relation (2.14) holds. Finally, Relations (2.12) and (2.14) give Relation (2.10). One concludes therefore that * ∈ ∆ 0 , the associated process (m * (t)) is necessarily ergodic by Proposition 2.2 and Relations (2.13).

To prove that the * defined by Relations (2.10) and (2.11) is indeed an equilibrium point of the dynamical system defined by Equation (2.9), one has to show that the right-hand side of Equation (2.11) is indeed equal to π * (Z * -). This is proved in Proposition 2.5 of Section 2.4.

Convergence of Invariant Distributions

In this section our main result establishes the convergence of the invariant distribution of the process (m N (t)) as N gets large. This will give in particular the convergence with respect to N of the probability of not downgrading a request at equilibrium. Lemma 2.1. If the process ( L N j (t)) is the process (L N j (t)) at equilibrium then, for any ε > 0 and T > 0, lim

N →+∞ P sup 0≤t≤T sup 2≤j≤J L N j (t) N ≤ ρ j + ε = 1.
Proof. Let (L N j (t)) be the process with initial state empty, then one can easily construct a coupling such that the relation

L N j (t) ≤ Q N j (t), t ≥ 0, 2 ≤ j ≤ J,
holds almost surely, where (Q N j (t)) is the M/M/∞ queue associated to class j requests. One deduces that,

L N j (0) ≤ st Q N j (0)
where Q N j (0) is a Poisson random variable with parameter ρ j N and ≤ st is the stochastic ordering of random variables. One can therefore construct another coupling such that

L N j (t) ≤ Q N j (t), t ≥ 0, 2 ≤ j ≤ J,
where ( Q N j (t)) is a stationary version of the M/M/∞ queue associated to class j requests. The lemma is then a consequence of the following convergence in distribution of processes, lim

N →+∞ Q N j (t) N = (ρ j )
for 2 ≤ j ≤ J, see Theorem 6.13 of Robert [Rob03, pp. 159] for example.

Definition 2.4. Let (y(t)) be the dynamical system on S satisfying

             d dt y 1 (t) = -µ 1 y 1 (t) + λ 1 + J k=2 λ k 1 Λ A J k=1 A k (λ k -µ k y k (t)) , d dt y j (t) = -µ j y j (t) + λ j 1 Λ A J k=1 (A k µ k y k (t) -λ k ) , 2 ≤ j ≤ J,
(2.15)

with

Λ A def. = J k=1 λ k (A k -1).
Lemma 2.2. If y(0) ∈ ∆ 0 and if there exists an instant T > 0 such that y(t) ∈ ∆ 0 for t ∈ [0, T ] then (y(t)) and ( (t) coincide on the time interval [0, T ], where ( (t)) is the solution of Equations (2.9) with (0) = y(0).

Proof. The proposition is a simple consequence of the representation (2.9) of the differential equations defining the dynamical system ( (t)) and of the explicit expression of the quantity π (Z * -) given by Relation (2.22) when ∈ ∆ 0 , see Relation (2.6).

The next proposition investigates the stability Properties of (y(t)).

Proposition 2.4. Let H 0 be the hyperplane

H 0 def. = {z ∈ S: A, z = c 0 }} if y(0) ∈ H 0 then y(t
d dt y j (t) = λ j b 0 -µ j y j (t) + λ j J k=2 b k y k (t), with b 0 def. = µ 1 c 0 -Λ Λ A and b j = A j (µ j -µ 1 ) Λ A .
In matrix form, if z(t) = (y 2 (t), . . . , y J (t)), it can be expressed as

d dt z(t) = e b + Bz(t), (2.16) Chapter 2 2.3. Scaling Results with e b = b 0 (λ 2 , . . . , λ J ) ∈ R J-1 and B = (B jk , 2 ≤ j, k ≤ J) with B jk def. = λ j b k -µ j 1 {k=j} . If v = (v 2 , . . . , v J
) is an eigenvector for the eigenvalue x of B, then

(x + µ j )v j = λ j J k=2 b k v k , 2 ≤ j ≤ J,
hence, x is an eigenvalue if and only if it is a solution of the equation

F (x) def. = J j=2 b j λ j x + µ j = 1.
If L is the number of distinct values of µ j , 2 ≤ j ≤ J, such that µ j =µ 1 , then the above equation shows that an eigenvalue is a zero of a polynomial of degree at most L. Using Conditions (R), it is easy to check that the relation F (0) < 1 holds. In particular 0 is not an eigenvalue and, consequently B is invertible. Due to the poles of F at the -µ j , 2 ≤ j ≤ J and the relations F (0) < 1 and Therefore the function (z(t)) has a limit at infinity given by -B -1 e b which is clearly ( * j , 2 ≤ j ≤ J). The proposition is proved.

µ j ≥ µ 1 for 2 ≤ j ≤ J,
One can now prove the main result of this section.

Theorem 2.2. If * is the quantity defined in Proposition 2.3, then the equilibrium distribution of (m N (t)) converges to π * when N goes to infinity.

Proof. Recall that m N (t) = A, L N (t) -C N 0 and let Π N be the invariant distribution of (L N (t)). It is assumed that the distribution of L N (0) is Π N for the rest of the proof. In particular (m N (t)) is a stationary process.

One first proves that (L N (0)/N ) converges in distribution to * . The boundary condition A, L N (0) ≤ C N gives that the sequence of random variables (L N (0)/N ) is tight. If (L N k (0)/N k ) is a convergent subsequence to some random variable ∞ , by Theorem 2.1, one gets that, for the convergence in distribution, the relation

lim k→+∞ L N k (t) N k = ( (t))
holds, where ( (t)) is a solution of Equation (2.9) with initial point at (0) = ∞ . Note that ( (t)) is a stationary process, its distribution is invariant under any time shift.

Chapter 2

Scaling Results

By Lemma 2.1 one has that the relation j (t) ≤ ρ j , for 2 ≤ j ≤ J, holds almost surely on any finite time interval and, by Proposition 2.1, A, (t) ≤ c 0 also holds almost surely on finite time intervals.

Assume that A, (0) < c 0 holds. The ODEs defining the limiting dynamical system are given by d dt j (t) = -µ j j (t) + λ j , 1 ≤ j ≤ J, as long as the condition A, (t) < c 0 holds, hence on the corresponding time interval, one has

j (t) = ρ j + ( j (0) -ρ j )e -µ j t , 1 ≤ j ≤ J, so that A, (t) = A, ρ + J j=1 A j ( j (0) -ρ j ) e -µ j t .
Since A, ρ > c 0 , there exists some t 1 > 0 such that A, (t 1 ) = c 0 . Hence, by stationarity in distribution of ( (t)), one can shift time at t 0 and assume that A, (0) = c 0 . On this event

J j=1 µ j j (0)A j ≥ µ 1 J j=1 j (0)A j = µ 1 c 0 > Λ = J j=1 λ j .
(2.17)

Similarly, since j (0) ≤ ρ j for all 2 ≤ j ≤ J,

J j=1 A j (λ j -µ j j (0)) = λ 1 -µ 1 c 0 + µ 1 J j=2 A j j (0) + J j=2 A j (λ j -µ j j (0)) = -µ 1 c 0 + J j=1 A j (λ j + (µ 1 -µ j ) j (0)) ≥ -µ 1 c 0 + J j=1 A j (λ j + (µ 1 -µ j )ρ j ) = -µ 1 c 0 + J j=1 A j λ j µ 1 µ j = µ 1 ( A, ρ -c 0 ) > 0, (2.18)
and the last quantity is independent of (0). Relations (2.17) and (2.18) show that (0) ∈ ∆ 0 and, by Equations (2.9) and (2.15), they also hold for t in a small neighbourhood I of 0 independent of (0) so that (t) ∈ ∆ 0 for t ∈ I. Consequently, the dynamical system ( (t)) never leaves ∆ 0 . Lemma 2.2 shows that the two dynamical systems ( (t)) and (y(t)) (with y(0) = (0)) coincide.

Hence, on the one hand ( (t)) is a stationary process and, on the other hand, it is a dynamical system converging to * , one deduces that it is constant and equal to * . We have thus proved that the sequence (L N (0)/N ) converges in distribution to * . Using again Theorem 2.1, one gets that, for the convergence in distribution, lim

N →+∞ 1 0 f (m N (u)) du dist. = Z f (x)π * (dx)
holds for any function f with finite support on Z. Using the stationarity of (m N (t)) and Lebesgue's Theorem, one obtains lim

N →+∞ E f (m N (0)) = Z f (x)π * (dx).
The theorem is proved.

Since a job arriving at time t is not downgraded if m N (t) < 0, one obtains the following corollary.

Corollary 2.1. As N goes to infinity, the probability that, at equilibrium, a job is not downgraded in this allocation scheme is converging to π -defined in Proposition 2.10,

π -= c 0 -Λ/µ 1 A, ρ -Λ/µ 1 .

Invariant Distribution

We assume in this section that ∈ ∆ 0 , as defined in Proposition 2.2, so that (m (t)) is an ergodic Markov process. The goal of this section is to derive an explicit expression of the invariant distribution π on Z of (m (t)). At the same time, Proposition 2.5 below gives the required argument to complete the proof of Proposition 2.3 on the characterisation of the fixed point of the dynamical system.

Functional Equation

In the following we denote by Y a random variable with distribution π = (π (n), n ∈ Z).

For r > 0, we will use the notation

D(r) def. = {z ∈ C, |z| < r} , D c (r) def. = {z ∈ C, |z| > r} and γ(r) def. = {z ∈ C, |z| = r} .
For sake of simplicity, we will use D def.

= D(1) and D c def. = D c (1).

Lemma 2.3. With the notation

ϕ + (z) def. = E z Y 1 {Y ≥0} , ϕ -(z) def. = E z Y 1 {Y <0} ,
the random variable Y is such that

P 1 (z)ϕ + (z) = P 2 (z)ϕ -(z) (2.

19)

where P 1 and P 2 are polynomials defined by

               P 1 (z) def. = J j=1 (λ j + µ j j )z A J -λ j z A J +1 -µ j j z A J -A j , P 2 (z) def. = J j=1 λ j z A J +A j + µ j j z A J -A j -(λ j + µ j j )z A J .
(2.20)

Proof. For z ∈ γ(1) define f z : Z → C such that f z (x) = z x , for x ∈ Z.
Equilibrium equations for (m (t)) give the identity

x,y∈Z x =y π (x)Q (x, y)(f z (y) -f z (x)) = 0,
where Q is the Q-matrix of (m (t)) given by Equation (2.5). After some simple reordering, one gets the relation

E z Y 1 {Y l ≥0} J j=1 λ j (1 -z) + µ j j 1 -z -A j = -E z Y l 1 {Y l <0} J j=1 λ j 1 -z A j + µ j j 1 -z -A j . (2.21)
Using the definition of ϕ + (z) and ϕ -(z), Equation (2.21) can be rewritten as Equation (2.19).

Proposition 2.5.

If ∈ ∆ 0 then π (Z * -) = J j=1 (A j µ j j -λ j ) J j=1 λ j (A j -1)
.

(2.22)

In particular if * ∈ S is given by Relation (2.10) then

π * (Z * -) = c 0 -Λ/µ 1 A, ρ -Λ/µ 1 .
Note that the right-hand side of the last relation is precisely π -of Relation (2.11) which is the result necessary to complete the proof of Proposition 2.3.

Proof. With the same notations as before, from Relation (2.19),

ϕ -(z) ϕ + (z) = P 1 (z) P 2 (z) holds for z ∈ C, with z ∈ γ(1). By definition of ϕ -(z) and ϕ + (z), lim z→1 ϕ -(z) = π (Z * -) and lim z→1 ϕ + (z) = 1 -π (Z * -).
Since 1 is a zero of P 1 and P 2 , this gives the relation

π (Z * -) 1 -π (Z * -) = P 1 (1) P 2 (1) = J j=1 (A j µ j j -λ j ) J j=1 A j (λ j -µ j j )
.

Using the expression of ( * j ), with some algebra, one gets

π * (Z * -) =   c 0 - J j=1 λ j µ 1     J j=1 ρ j A j - J j=1 λ j µ 1   = π -.
The proposition is proved.

Relation (2.19

) is valid on the unit circle, however the function ϕ + (resp. ϕ -) is defined on D (resp. D c ). This can then be expressed as a Wiener-Hopf factorisation problem analogous to the one used in the analysis of reflected random walks on N. This is used in the analysis of the GI/GI/1 queue (see Chapter VIII of Asmussen [START_REF] Asmussen | Applied Probability and Queues[END_REF] or Chapter 3 of Robert [START_REF] Ph | Stochastic Networks and Queues[END_REF] for example). In a functional context, this is a special case of a Riemann's problem (see Gakhov [START_REF] Gakhov | Boundary value problems[END_REF]). In our case, this is a random walk on Z, with a drift depending on the half-space where it is located. The first (resp. second) condition in the definition of the set ∆ 0 in Definition (2.6) implies that the drift of the random walk on Z * -(resp. in N) is positive (resp. negative). The first step in the analysis of Equation (2.19) is to determine the locations of the zeros of P 1 and P 2 . This is the purpose of the following lemma.

Lemma 2.4. (Location of the Zeros of P 1 and P 2 ) Let be in ∆ 0 .

(i) Polynomial P 2 has exactly two positive real roots 1 and z 2 ∈]0, 1[. There are A J -1 roots in D(z 2 ) and A J -1 roots whose modulus are strictly greater than 1.

(ii) Polynomial P 1 has exactly two positive real roots 1 and z 1 > 1. The A J -1 remaining roots have a modulus strictly smaller than 1.

Proof. One first notes that P 2 is a polynomial with the same form as the f defined by Equation ( 13) in Bean et al. [START_REF] Bean | Asymptotic analysis of single resource loss systems in heavy traffic, with applications to integrated networks[END_REF] (with e j = A j , κ j = λ j and ê = A J ). The roots of Q are exactly the roots of f . Lemma 2.2 of Bean et al. [START_REF] Bean | Asymptotic analysis of single resource loss systems in heavy traffic, with applications to integrated networks[END_REF] gives assertion (i) of our lemma. The proof of assertion (ii) uses an adaptation of the argument for the proof of Lemma 2.2 of Bean et al. [START_REF] Bean | Asymptotic analysis of single resource loss systems in heavy traffic, with applications to integrated networks[END_REF]. Define the function f (z) def.

= z -A J P 1 (z). Recall that P 1 is a polynomial with degree A J + 1. There are exactly two real positive roots for P 1 . Indeed, f (1) = 0 and it is easily checked that f is strictly concave with

f (1) = J j=1 (-λ j + A j µ j j ) > 0,
since ∈ ∆ 0 , by the second condition in Definition (2.6). Hence P 1 has a real zero z 1 greater than 1.

Let r ∈ (1, z 1 ) be fixed, note that P 1 (r) > 0. Define

f 1 (z) def. = Kz A J , with K def. = J j=1 (λ j + A j µ j j ) , f 2 (z) def. = J j=1 λ j z A J +1 + µ j j z A J -A j , so that P 1 = f 1 -f 2 .
Fix some z ∈ γ(r). Expressing these functions in terms of real and imaginary parts,

z A J = α 1 + iβ 1 and f 2 (z) = α 2 + iβ 2 , one gets f 1 (z) -f 2 (z) -bz A J 2 = |K(α 1 + iβ 1 ) -b(α 1 + iβ 1 ) -(α 2 + iβ 2 )| 2 = (Kα 1 -α 2 ) 2 + (Kβ 1 -β 2 ) 2 + H = |f 1 (z) -f 2 (z)| 2 + H, (2.23) with H def. = (bα 1 ) 2 -2bα 1 (Kα 1 -α 2 ) + (bβ 1 ) 2 -2bβ 1 (Kβ 1 -β 2 ) = b(b -2K)(α 2 1 + β 2 1 ) + 2b(α 1 α 2 + β 1 β 2 ).
Cauchy-Schwarz's Inequality gives the relation

α 1 α 2 + β 1 β 2 ≤ 1 K |f 2 (z)| |f 1 (z)| ≤ 1 K f 2 (r)f 1 (r), since |f i (z)| ≤ f i (|z|) for i = 1, 2. Thus, H b = (b -2K)(α 2 1 + β 2 1 ) + 2(α 1 α 2 + β 1 β 2 ) ≤ (b -2K) f 1 (r) 2 K 2 + 2f 2 (r) f 1 (r) K = f 1 (r) K 2 ((b -2K)f 1 (r) + 2Kf 2 (r)) = f 1 (r) K 2 (bf 1 (r) -2KP 1 (r)).
Since P 1 (r) > 0, b can be chosen so that bf 1 (r) < 2KP 1 (r). From the above relation and Equation (2.23), one gets that for z ∈ γ(r), the relation

f 1 (z) -f 2 (z) -bz A J < |f 1 (z) -f 2 (z)|
holds. By Rouché's theorem, one obtains that, for any r ∈ (1, z 1 ), P 1 has exactly A J roots in D(r). One concludes that P 1 has exactly A J roots in D.

It is easily checked that if z ∈ γ(1) and z ∈R then the real part of P 1 (z) is positive, hence z cannot be a root of the polynomial P 1 . Consequently, P 1 has exactly A J -1 roots in D. The lemma is proved.

Definition 2.5. For U ∈ {P 1 , P 2 }, denote by Z U the set of the zeros of U different from 1.

Define Φ(z)

def.

=                -ϕ + (z)λ J -1 (z -z 1 ) q∈Z P 2 ∩D c (z -q) -1 , z ∈ D ϕ -(z)Λ -1 q∈Z P 2 ∩D (z -q) p∈Z P 1 ∩D (z -p) -1 , z ∈ D c with Λ = λ 1 +•
. For z ∈ D c , |ϕ -(z)| ≤ E 1 {Y <0} |z| Y ≤ 1 |z| , since the cardinality of Z P 1 ∩ D (resp. Z P 2 ∩ D) is A J -1 (resp. A J ), the holomorphic function Φ is therefore bounded on C. By Liouville's theorem, Φ is constant, equal to κ ∈ C. Therefore          ϕ + (z) = -κλ J (z -z 1 ) -1 q∈Z P 2 capD c (z -q), z ∈ D, ϕ -(z) = κΛ q∈Z P 2 ∩D (z -q) -1 p∈Z P 1 ∩D (z -p), z ∈ D c .
(2.24) (1 -q) -1 1 1 -z 1 P 1 (1) + P 2 (1) , hence, using equation (2.20),

Recall that ϕ(z) = ϕ + (z) + ϕ -(z) = E z Y is
κ = z 1 -1 Λ A q∈Z P 2 ∩D (1 -q),
where Λ A is introduced in Definition 2.4. Note that κ is positive. We can now state the main result of this section.

Proposition 2.6 (Invariant Measure). If ∈ ∆ 0 defined by Relation (2.6), then the invariant measure π can be expressed, for n ∈ Z, as

π (n) =                        -κ q∈Z P 2 ∩D P 1 (q)q -n-1 (q -z 1 )(q -1)R D (q)
, n < 0,

κ α n + P 2 (z 1 )z -n-1 1 (z 1 -1)R D (z 1 ) , 0 ≤ n < A J -1, κ P 2 (z 1 )z -n-1 1 (z 1 -1)R D (z 1 ) , n ≥ A J -1,
where z 1 is defined in Lemma 2.4, and P 1 and P 2 by Relation (2.20),

R D (z) = q∈Z P 2 ∩D (z -q), κ = (z 1 -1)R D (1) Λ A , for 0 ≤ n < A J -1, α n is the coefficient of degree n of the polynomial - 1 z -z 1 P 2 (z) (z -1)R D (z) - P 2 (z 1 ) (z 1 -1)R D (z 1 )
.

Proof. Note that, for z ∈ C,

p∈Z P 1 ∩D (z -p) = - 1 Λ P 1 (z) (z -z 1 )(z -1)
.

For z ∈ D c , ϕ -(z) = κΛ q∈Z P 2 ∩D (z -q) -1 p∈Z P 1 ∩D (z -p).
Since |Z P 1 ∩ D| = A J -1 < A J = |Z P 2 ∩ D| by Lemma 2.4, ϕ -has the following partial fraction decomposition

ϕ -(z) = -κ q∈Z P 2 ∩D P 1 (q) (q -z 1 )(q -1)R D (q) 1 z -q = ∞ i=0 -κ q∈Z P 2 ∩D P 1 (q)q i (q -z 1 )(q -1)R D (q) 1 z i+1 . Denote R D c (z) = q∈Z P 2 ∩D c (z -q) = P 2 (z) λ J (z -1)R D (z) , then ϕ + (z) = -κλ J R D c (z) z -z 1 = κ -λ J R D c (z) -R D c (z 1 ) z -z 1 + P 2 (z 1 ) (1 -z 1 )R D (z 1 ) 1 z -z 1 .
One concludes using the expression of κ obtained before.

Some Moments of (π * )

Using the probability generating function ϕ(z) of π * from Equation (2.24), one can derive an explicit expression of the mean, the variance and the skewness of such distribution. The skewness of a random variable X is a measure of the asymmetry of the distribution of X, S(X)

def. = E([X -E(X)] 3 ).
See Doane and Seward [START_REF] Doane | Measuring skewness: A forgotten statistic[END_REF] for example.

Proposition 2.7. If Y * is a random variable with distribution π * then E(Y * ) = A J + θ 2 2θ 1 -S(1), V(Y * ) = θ 2 + 2θ 3 6θ 1 - θ 2 2θ 1 2 -S(1) + S (1) , S(Y * ) = θ 3 2 4θ 3 1 + θ 2 θ 2 -2θ 3 4θ 2 1 + θ 4 -θ 3 4θ 1 -S(1) + 3S (1) + S (1) ,
where, for i ≥ 1,

θ i def. = J j=2 λ j A i-1 j (A j -1), and
S(z) def. = 1 z -z 1 + q∈Z P 2 ∩D 1 z -q ,
with R D (z) defined in Proposition 2.6.

The proof is straightforward, modulo some tedious calculations of the successive derivatives of ϕ(z) evaluated at 1.

Applications

Comparison with a Pure Loss System

In this case, a request which cannot be accommodated is rejected right away. Recall that, with probability 1, our algorithm does not reject any request. The purpose of this section is to discuss the price of such a policy. Intuitively, at equilibrium the probability W L of accepting a job at requested capacity in a pure loss system is greater that the corresponding quantity W D for the downgrading algorithm. See Proposition 2.8 below. A further question is to assess the impact of such policy, i.e. the order of magnitude of the difference W L -W D .

Under the same assumptions about the arrivals and under the condition

A, ρ > c and Λ µ 1 < c, with Λ = λ 1 + • • • + λ J ,
then, as N gets large, the equilibrium probability that a request of class 1 ≤ j ≤ J is accepted in the pure loss system is converging to β A j , where β ∈ (0, 1) is the unique solution of the equation

J j=1 A j ρ j β A j = c.
(2.25)

see Kelly [Kel86,[START_REF] Kelly | Loss networks[END_REF]. Consequently, the asymptotic load of accepted requests is given by

W L def. = 1 Λ J j=1 ρ j β A j .
Under the downgrading policy, the equilibrium probability that a job is accepted without degradation is given by π -, the asymptotic load of requests accepted without degradation is

W D def. = 1 Λ J j=1 ρ j c 0 -Λ/µ 1 A, ρ -Λ/µ 1 , for c 0 ∈ (Λ/µ 1 , c).
Note that, when the service rates are constant equal to 1, then W L (resp. W D ) is the asymptotic throughput of accepted requests (resp. of non-degraded requests).

The following proposition establishes the intuitive property that a pure loss system has better performances in terms of acceptance.

Proposition 2.8. For c 0 ∈ (Λ/µ 1 , c), the relation

W D ≤ W L holds.
Proof. The representation of these quantities gives that the relation to prove is equivalent to the inequality

J j=1 ρ j β A j   J j=1 ρ j A j - J j=1 λ j µ 1   - J j=1 ρ j   c 0 - J j=1 λ j µ 1   ≥ 0.
Using the fact that c 0 < c and Equation (2.5), it is enough to show that the quantity

∆ def. = J j=1 ρ j β A j J i=1 ρ j A i - J i=1 λ i µ 1 - J j=1 ρ j J i=1 A i ρ j β A i - J i=1 λ i µ 1 is positive. But this is clear since ∆ = 1≤i,j≤J ρ i ρ j A j β A i -β A j + 1≤i,j≤J ρ j λ i µ 1 1 -β A j = 1≤i<j≤J ρ i ρ j (A j -A i ) β A i -β A j + 1≤i,j≤J ρ j λ i µ 1 1 -β A j
and the terms of both series of the right hand side of this relation are nonnegative due to the fact that 0 < β < 1. Numerical experiments have been done to estimate the difference W L -W D , see Figure 2.2. The general conclusion is that, at moderate load under Condition (R), the downgrading algorithm performs quite well with only a small fraction of downgraded jobs. As it can be seen this is no longer valid for high load where, as expected, most of requests are downgraded but nobody is lost.

Application to Video Transmission

We consider now a link with large bandwidth, 10.0 Gbps, in charge of video streaming. Requests that cannot be immediately served are lost. Video transmission is offered in two standard qualities, namely, Low Quality (LQ) and High Quality (HQ). From Añorga et al. [AAS + 15], the bandwidth requirement for YouTube's videos at 240p is 1485 Kbps, and for 720p it is 2737.27 Kbps.

Using the values above, after renormalisation, one takes A 1 = 1, N = C N = 7061 and A 2 = 2, c = 1. Jobs arrive at rate λ 2 in this system asking for HQ transmission, but clients accept to watch the video in LQ. In particular λ 1 = 0. Service times are assumed to be the same for both qualities and taken as the unity,

µ 1 = µ 2 = 1. Condition (R) is satisfied when 0.5 < λ 2 < 1.
We define C 0 = αC, with 0 < α < 1. The quantity α ε is defined as the largest value of α such that the loss probability of a job is less than ε > 0. With the notations of Section 2.4, we write

α ε def.
= sup {α ∈ (0, 1) :

P (Y * + C 0 > C) < ε} .
Note that this is an approximation, since the variable Y * corresponds to the case when the scaling parameter N goes to infinity. Using the explicit expression of the distribution of Y * of Proposition 2.6, Figure 2.3 plots the threshold α ε that ensures a loss rate less than ε as a function of ε, for several values of λ 2 . In the numerical example, taking C 0 = 0.98C is sufficient to get a loss probability less than 10 -7 . Now let π - ε be the value of π -defined by Corollary 2.1 for C 0 = α ε C. Recall that π - ε is the asymptotic equilibrium probability that a job is not downgraded is given by Relation (2.11),

π - ε = α ε λ 2 -1.
For comparison, β is defined as the corresponding acceptance probability when no control is used in the system. We show in Figure 2.4 the relation between these quantities and the workload λ 2 , for fixed loss rates of 10 -3 , 10 -6 and 10 -9 . We have β = 1 -1/(2λ 2 ), see Proposition 6.19 of Robert [Rob03, p. 169]. The difference β -π -can be seen as the fraction of jobs which are downgraded for our policy but lost in the uncontrolled policy. Intuitively it can be seen as the price of not rejecting any job. Notice also that the curves plotting π - ε for ε = 10 -3 , 10 -6 , 10 -9 are close and that β is larger than π -. One remarks nevertheless that, for high loads, the system cannot hold these demands, because our policy is no longer effective.

λ 2 π - ε |ε = 10 -3 π - ε |ε = 10 -3 π - ε |ε = 10 -3 π -|c 0 = c 1 -β Figure 2
.4 -Fraction of jobs served at requested bit-rate at equilibrium for the downgrading policy compared to the fraction of lost jobs in a pure loss system.

Chapter 3

Cooperative Schemes in the framework of multi-resource Cloud Computing

Introduction

Over the last years, Cloud Computing systems have become increasingly decentralised as processing facilities (data centres) have been moved closer to the final user in an effort to reduced the volume of data sent across networks. On average, these decentralised facilities dispose of a lower capacity of resources than centralised ones and may also face different flows of service requests. This results in a system where certain facilities may be overloaded whereas the resources of others can be underexploited.

This problem still gains in complexity, considering that the instantiation of a common virtual machine necessitates at least two different kinds of resources, namely RAM memory and CPU cores. The demand and supply of these resources might be imbalanced in a decentralised architecture. Not only can users request different amounts of each of the resources but the installed capacity of each resource may change from one processing facility to another. Due to the stochastic nature of service request arrivals and service times, mismatches between demand and supply may occur. Certain facilities might run out of one of the resources whereas the others resource have high amount of idle units, causing rejection of user demands. This is particularly critical in a system which disposes of a sufficiently large capacity on an aggregate level (summing the capacities of all the decentralised processing facilities) to serve the entire traffic of user demands. There thus exist potential gains from establishing cooperation schemes between data centres in order to handle the local demands while maintaining service standards.

It should be noted that in the framework of random access networks, allocation and dimensioning of resources have been widely investigated, beginning with the work of Erlang more than one century ago. However, from circuitswitch networks to Cloud Computing, most of the studies in this field focus on models and policies for single resource services.

One of the first among the few papers dealing with multi-resource alloc- to what is assumed in the previously mentioned literature. For example, in many Cloud services such as Microsoft Azure [Mic], jobs are not divisible. A virtual machine may actually fail to be instantiated because there are not enough resources in the data centre. As this is more likely when the data centre works close to its full capacity, exploiting at full capacity is often avoided in practice. In such systems, every data centre usually has enough idle resources to accommodate an incoming request or the request will not be hosted locally. If offloading is not possible, these systems rather fit into the framework of loss networks presented in the seminal paper by Kelly [START_REF] Kelly | Loss networks[END_REF].

In the context of cooperation in single resource systems, we refer to the papers by Fricker et al. [START_REF] Fricker | Analysis of an offloading scheme for data centers in the framework of fog computing[END_REF] and Guillemin and Thompson [START_REF] Guillemin | Analysis of a trunk reservation policy in the framework of fog computing[END_REF]. They advocate the introduction of cooperative schemes in between processing facilities to circumvent load asymmetry arising from the decentralisation of Cloud services whose performance is determined solely by one resource. For the design of cooperation schemes in the multi-resource framework, the load of jobs arriving in each data centre has to be considered, as well as the charge each resource is subjected to at the local and at the global level. This issue is particularly relevant for services whose virtual machines are resource-specialised, necessitating very different ratios of each resource. See for instance the predefined virtual machine types from Google Cloud Platform [Goo]. In the worst case scenario, the traffic asymmetry may generate a situation where each data centre is running low on some specific resource while it is available abundantly in the other processing units.

To mitigate the negative effects on system performance in such a case, we propose a cooperation scheme where jobs are forwarded to another processing facility in order alleviate the local charge of the depleted resource. We propose the introduction of a threshold on each depleted resource (on local level) which, if surpassed, triggers the offloading of the jobs with the highest requirements of the scarce resource.

Our model and assumptions

The system we consider is composed of two data centres, each equipped with a finite capacity of GB RAM and CPU cores. There are two virtual machine configurations: type 1 occupies a big chunk of GB RAM and only 1 CPU core whereas type 2 uses only 1 GB RAM and requires a large amount of CPU cores.

Introduction

Virtual machines of both types arrive at each data centre at different rates. The average service time only depends on the type of the job (virtual machine) but not on the hosting data centre. All of the necessary resources for the execution of a job should be available upon its instantiation. If the demanded resources are not free, the arriving virtual machine is either forwarded to another data centre or rejected. The resources are released after service completion.

Considering the large scale of data centres deployed in Cloud services, the service capability of the system is defined by the relation between the load of requests and the installed capacity. The present paper focuses on the cases where the capacity of the system on the aggregate level is large enough to accommodate the combined flow of jobs, meaning the system is globally underloaded. This setting is particularly interesting because it implies that the system could accommodate (with high probability) all jobs without losses on the aggregated level (see Kelly [START_REF] Kelly | Loss networks[END_REF] and Section 6.7 of Robert [Rob03, p. 164]). The aim of the presented policy is to enable the decentralised system to achieve the efficiency of a centralised architecture with the same capacity.

We focus on the case where both data centres are facing local saturation because each lacks one of the resources. Systematically, clients arriving at some data centre will be rejected due to the unavailability of the same resource which is clearly the saturated on. In this scenario, forwarding jobs after exhaustion of one of the resources is no longer effective, since jobs require both resources for the instantiation of their virtual machine. Although the probability of rejection of a job ought to be smaller than in isolated data centres, significant losses are still observed.

To bypass this, a set of thresholds is introduced to trigger the offloading of the jobs whenever a data centre faces a demand such that its resources might be depleted. The idea is to buffer some resources to avoid the complete jamming of a processing facility due to the lack of either resource. A threshold is set up for the most demanded resource at each data centre, selected by the relation between its local load and capacity. The study is therefore restricted to the implementation of thresholds 0 < δ p < 1 in data centre p to avoid exhaustion of resource p by offloading the jobs of type p, for 1 ≤ p ≤ 2. Thus, an arriving job of type p at data centre p is served locally only if resource p utilisation factor is bellow δ p , otherwise it is forwarded to data centre 3 -p, for 1 ≤ p ≤ 2.

It is shown that the rejection rates of requests become negligible (with high probability for a large system) by triggering early enough the previously defined offloading mechanism. In fact, different thresholds can be set up for each resource, type of job and data centre to improve systems performance. However, if the thresholds are poorly dimensioned, communication channels can be jammed or resources which were a priori well dimensioned for the local charge can be saturated by the large volume of offloaded jobs.

Admission Control Policy. It is assumed that jobs of type j arrive at data centre k according to a Poisson process with rate λ j,k , for 1 ≤ j, k ≤ 2. Jobs of type j hold A i,j units of resource i during their service time which is exponentially distributed with mean 1/µ j , and data centre k is equipped Chapter 3 3.1. Introduction with G i,k units of resource i, for 1 ≤ i, j, k ≤ 2. Throughout this paper, the following notation is kept

A def. = R 1 1 C and G def. = R 1 R 2 C 1 C 2 .
Let = ( j,k , 1 ≤ j, k ≤ 2) represent the number of jobs of type j at data centre k at a certain moment, for 1 ≤ j, k ≤ 2. The admission and offloading mechanism rules that, in the event of an arrival of a job of type 1 at data centre 1, if

-R 1,1 + 2,1 < R 1 δ 1 and ( 1,1 + 1) + C 2,1 ≤ C 1 then
the request is hosted in data centre 1, otherwise the request is forwarded to the other processing facility. Once forwarded to data centre 2, if -R ( 1,2 + 1) + 2,2 ≤ R 2 and ( 1,2 + 1) + C 2,2 ≤ C 2 then the request is hosted in data centre 2, otherwise the request is rejected.

In the event of an arrival of type 2 at data centre 1, if

-R 1,1 + ( 2,1 + 1) ≤ R 1 and 1,1 + C ( 2,1 + 1) ≤ C 1 then
the request is hosted in data centre 1, otherwise the request is forwarded to data centre 2. Once in the other processing facility, if

-R 1,2 + ( 2,2 + 1) ≤ R 2 and 1,2 + C ( 2,2 + 1) ≤ C 2 then
the request is hosted in data centre 2, otherwise the request is rejected.

At data centre 2 the mirror conditions rule the admission and offloading of jobs.

Because of the exponential assumptions for inter-arrival and service times, the stochastic vector describing the number of jobs of type j at data centre k is a Markov process in a finite state space. The invariant distribution of this Markov process does likely not have a closed expression, so a scaling approach is used in order to obtain qualitative and quantitative results information about the system, considering its large scale.

Scaling Approach. To study the offloading policy, a scaling approach is used such as in Kelly [START_REF] Kelly | Loss networks[END_REF]Kel86] in the analysis of loss networks. We assume that the loads and installed capacities of resources are of the same order, meaning both are scalable by a positive factor N . Namely,

G i,k → G i,k N for 1 ≤ i, k ≤ 2, λ j,k → λ j,k N for 1 ≤ j, k ≤ 2.
Asymptotic results will be derived for the rescaled system, when N goes to infinity. At the equilibrium and if the thresholds are well chosen, -the probability of rejecting jobs in both data centres converges to 0; -the probabilities of forwarding a type 2 job from data centre 1 and type 1 job from data centre 2 converge to 0;

-the probabilities of forwarding a job of type 1 from data centre 1 and type 2 from data centre 2 can be explicitly derived.

Chapter 3

Model description and notation

Using some approximations (which are rigorously verified later), we deduce that the thresholds δ 1 and δ 2 are well chosen if

         1 R 1 λ 1,1 + λ 1,2 µ 1 R + λ 2,1 + λ 2,2 µ 2 -R 2 < δ 1 < 1, 1 C 2 λ 2,2 + λ 2,1 µ 2 C + λ 1,2 + λ 1,1 µ 1 -C 1 < δ 2 < 1;
Moreover, using the same program as in Hunt and Kurtz [START_REF] Hunt | Large loss networks[END_REF] we are able to study the process of the renormalised number of customers in the system trough a dynamical system, when N goes to infinity. We show show that this dynamical system converges indeed for a fixed point which is the same obtained by the approximations previously established.

Outline of the paper

The paper is organised as follows: In Section 3.2, we describe the model, the offloading policy and the stochastic processes characterising the functioning of the model. In Section 3.3, we introduce the scaled version of the system and analyse system performance under Kelly's regime. We derive approximations of the main metrics of the scaled version of the system in steady state, such as the average occupation of each data centre and the offloading rates. We finish this section by defining the optimal operation range of the threshold parameters. In Section 3.4, we study the transient behaviour of the system and the dynamical system associated with the normalised number of virtual machines in each data centre.

Model description and notation

We consider a Cloud Computing environment where virtual machines (or jobs) are instantiated upon the allocation of GB RAM and CPU core, denoted resource i ∈ {1, 2}, respectively. To capture the particular aspect of resource specialised (unbalanced) virtual machines, we consider two types of jobs arriving to the system, denoted type j ∈ {1, 2}. Jobs of type 1 require R > 1 GB RAM and 1 CPU core, whereas jobs of type 2 require 1 GB RAM and C > 1 CPU core. We write the matrix A, analogue to the routing matrix in Kelly [START_REF] Kelly | Loss networks[END_REF] for loss networks with fixed routing, as

A def. = (A i,j , 1 ≤ i, j ≤ 2) = R 1 1 C .
We denote by A j the column vector (A i,j , 1 ≤ i ≤ 2) which represents the requirements of jobs of type j, for 1 ≤ j ≤ 2. Throughout this paper, vectorial and matrix equalities as well as inequalities are defined element wise, hence for

u, v ∈ R d , u#v if and only if u 1 #v 1 , u 2 #v 2 , . . . , u d #v d , for # ∈ {>, ≥, = , ≤, <}.
The system is composed of two parallel data centres denoted k ∈ {1, 2}, respectively. Each data centre k is equipped with some large (but finite) Chapter 3 3.2. Model description and notation amount R k of GB RAM and C k of CPU cores. We write the local capacity matrix G, as

G def. = (G i,k , 1 ≤ i, k ≤ 2) = R 1 R 2 C 1 C 2 ,
where G i,k is the capacity of resource i at data centre k. Requests of type j arrive at data centre k according to a Poisson process N λ j,k with rate λ j,k , for 1 ≤ j, k ≤ 2. If accepted, a job of type j holds the required units of each resource in the hosting data centre during its service time, which is exponentially distributed with mean µ -1 j . After service completion, the job leaves the system and releases the occupied units of both resources. It is assumed that the service rates can be different, conditioned that µ p /µ 3-p < RC, for 1 ≤ p ≤ 2.

See Figure 3.1 for an illustration of the arrival processes in the system.

R 1 R 1 δ 1 C 1 #1 A 1 =(R, 1) λ 1,1 A 2 =(1, C) λ 2,1 R 2 C 2 C 2 δ 2 #2 A 1 =(R, 1) λ 1,2 A 2 =(1, C) λ 2,2 Figure 3.1 -System configuration
Jobs of type j arriving at data centre k with rate λ j,k requesting A j units of the resources.

Load and Capacity

In order to understand the behaviour of the system, we need to examine the load its components are subject to and the ability of each resource to meet user demand. As we consider multiple resources and multiple data centres, we have to abstract the notions of service rate and, hence, of saturation from the ones used in the classical framework of queuing systems. This leads us to consider separately the local and global properties of the system for each of the resources.

The load and capacity characterisation is particularly relevant when we consider the large scale of the system, further explored in Section 3.3. These characteristics reflect the ability of the system to handle properly the current level of access and elucidates whether the fraction of jobs which will eventually be rejected is negligible or not.

The local load of a resource i in data centre k is given by

H i,k def. = A i,1 λ 1,k µ 1 + A i,2 λ 2,k µ 2 , for 1 ≤ i, k ≤ 2
This measure contrasts with the local capacity of each resource. In large scale networks, resource i is said to be saturated at data centre k if H i,k > G i,k , see Kelly [START_REF] Kelly | Loss networks[END_REF]. In the context of cooperation between data centres, we need to keep in mind the global aspects of the system. The system is said to be globally underloaded if and only if

H i,1 + H i,2 < G i,1 + G i,2 , for 1 ≤ i ≤ 2.
These relations indicate the capacity of the system to meet user demand if all resources would be aggregated in one large structure to serve the combined flows of requests.In conclusion, the scenario we are studying is characterised by local saturation of one resource of such a globally underloaded system H p,p > G p,p and H p,p + H q,p < G p,p + G q,p for q = 3 -p and 1 ≤ p ≤ 2.

Anticipated Offloading

To avoid local mismatching between the load and capacity of a resource, we propose to anticipate the offloading of some jobs. The general idea is to locally mitigate the saturation of a resource by forwarding the jobs with the largest demand for the concerned resource to another data centre much before actual depletion occurs.

Algorithm definition.

If the fraction of GB RAM being used at data centre 1 is above some threshold δ 1 ∈ (0, 1), then jobs of type 1 are systematically forwarded to data centre 2 (GB RAM being in high demand at data centre 1). If data centre 2 cannot host the job, then the request is then rejected. The symmetric admission scheme is applied to jobs of type 2 at data centre 2 according to some threshold δ 2 ∈ (0, 1) on the fraction of CPU core being used (CPU constituting the resource that is most demanded at data centre 2). Jobs of type 2 in data centre 1 and of type 1 in data centre 2 are forwarded if the original data centre cannot meet their demands upon their arrival.

To understand the effects of the deployment of such a policy, we need to look at the amount of jobs of each type instantiated in each data centre over time. Considering Poisson arrivals and exponentially distributed service times, this quantity is a Markov process described in the following. Using these notations, the control policy is formally defined in Algorithm 1.

Markovian process

Let us denote by L j,k (t) the number of jobs of type j instantiated at data centre k at time t, and

L(t) def. = (L j,k (t), 1 ≤ j, k ≤ 2) .
Because of the Poisson arrival and exponential service time assumptions, the process (L(t)) = (L(t), t ≥ 0) is a Markov process on

S def. = ∈ N 2×2 : A ≤ G .
The positive elements of its Q-matrix, Q = (q( , ), ( , ) ∈ S 2 ), are given by q( , ) =

λ j,k 1 A j,k + λ j,3-k 1 A c j,3-k ∩B j,k if = + e j,k µ j j,k , if = -e j,k , ,
for , ∈ S and 1 ≤ j, k ≤ 2, with e j,k = 1 {j=p,k=q} , 1 ≤ p, q ≤ 2 ,

A j,k = {v k < 0, u k ≥ A j } if j = k, {u k ≥ A j } if j = k, and B j,k = {u k ≥ A j } where v 1 def. = R 1,1 + 2,1 -R 1 δ 1 , v 2 def. = 1,2 + C 2,2 -C 2 δ 2 and u k def. = (G 1,k -R 1,k -2,k , G 2,k -1,k -C 2,k ) , for 1 ≤ k ≤ 2.
The invariant distribution of this process π being in general not known, we use a scaling approach. See Kelly [Kel86, Kel91], Hunt and Kurtz [HK94], Bean et al. [START_REF] Bean | Asymptotic analysis of single resource loss systems in heavy traffic, with applications to integrated networks[END_REF][START_REF] Bean | Dynamic and equilibrium behavior of controlled loss networks[END_REF] and Fricker et al. [START_REF] Fricker | On the fluid limits of some loss networks[END_REF]. For applications of such a framework in contexts similar to the one presented in this work, see also Fricker et al. [START_REF] Fricker | Analysis of an offloading scheme for data centers in the framework of fog computing[END_REF] and Guillemin and Thompson [START_REF] Guillemin | Analysis of a trunk reservation policy in the framework of fog computing[END_REF].

Scaling Results

Kelly's Regime

In this section, the system is investigated under Kellys regime which has been introduced to study the equilibrium properties of uncontrolled loss networks (see Kelly [Kel86,[START_REF] Kelly | Loss networks[END_REF]). We assume that the capacity of the system resources and the arrival rates of jobs are scalable by a positive factor N . Namely, the capacities of resource i at data centre k is replaced by

G N i,k , with lim N →+∞ G N i,k N = G i,k , for 1 ≤ i, k ≤ 2,
and the arrival rate of jobs of type j at data centre k by λ N j,k , with lim

N →+∞ λ N j,k N = λ j,k , for 1 ≤ j, k ≤ 2.
To indicate the dependency of the number of virtual machines (or jobs) of each type in this system on the parameter N , we denote by L N j,k (t) the number of jobs of type j instantiated at data centre k at time t and

L N (t) def. = L N j,k (t), 1 ≤ j, k ≤ 2 . Also, let m N (t) def. = (m i,k (t), 1 ≤ i, k ≤ 2) def. = G N -AL N (t)
represent the amount of free slots of resource i in data centre k at time t (in data centre k the vector m k (t) = (m 1,k (t), m 2,k (t)) denotes the amount of idle units of both resources) and

Y N (t) def. = Y N p (t), 1 ≤ p ≤ 2 def. = RL N 1,1 (t) + L N 2,1 (t) -N R 1 δ 1 , L N 1,2 (t) + CL N 2,2 (t) -N C 2 δ 2 (3.1)
denote the offload triggering process of jobs of type p at data centre p. If the utilisation of resource p is above the threshold δ p at time t then Y N p (t) ≥ 0, otherwise, if the amount of resource p being used is below the threshold δ p then Y N p (t) < 0.

Load and Capacity under Kelly's Regime

As said in Section 3.2, we focus our efforts on the case where each data centre is running low on one resource and has idle units of the other. Following the definition introduced before, we consider a system which is globally underloaded but where each data centre faces local saturation of one of the resources. Formally, the system is globally underloaded if

         R µ 1 (λ 1,1 + λ 1,2 ) + 1 µ 2 (λ 2,1 + λ 2,2 ) < R 1 + R 2 , 1 µ 1 (λ 1,1 + λ 1,2 ) + C µ 2 (λ 2,1 + λ 2,2 ) < C 1 + C 2 .
Locally, in data centre 1, resource 1 is exhausted and resource 2 is not if

λ 1,1 µ 1 R + λ 2,1 µ 2 > R 1 and λ 1,1 µ 1 + λ 2,1 µ 2 C < C 1 . (3.2)
In data centre 2, resource 2 is exhausted and resource 1 is not if

λ 1,2 µ 1 R + λ 2,2 µ 2 < R 2 and λ 1,2 µ 1 + λ 2,2 µ 2 C > C 2 . (3.3)
Also, no resource is exclusively the bottleneck of any data centre k if and only if

C k < R k C and R k < RC k ,
for 1 ≤ k ≤ 2. This condition implies that there exists, in the limiting case when N goes to infinity, some configuration of the available types of virtual machines which could exhaust both resources at the same time in both data centres. Otherwise, if this condition is violated at any data centre, then its performance is ruled solely by one of the resources. This assumption arises from a particular application of Farkas' Lemma, see Roos [START_REF] Roos | Farkas lemma[END_REF].

Approximations from Kelly's Regime

The following results are intended to provide a convenient framework for the analysis of the operational boundaries of thresholds δ = (δ 1 , δ 2 ), considering in particular the limiting case when the scaling factor N goes to infinity. We assess the effects of the choice of different thresholds δ on some key quantities related to the operation of this policy such as the probability of forwarding jobs from one data centre to another or the probability of a job getting blocked at a given data centre. Based on these results, we obtain some upper and lower boundaries for the different thresholds δ.

We begin by considering how the system would behave in the steady state. If the renormalised process describing the number of jobs in the system is at equilibrium in the fixed point x(δ) = (x j,k (δ), 1 ≤ j, k ≤ 2) then, the flow conservation equations, which rule the proportion of jobs that are either accepted, offloaded or rejected, imply that for 1 ≤ j, k ≤ 2 the following relation holds

µ j x j,k (δ) = λ j,k (1 -γ j,k (δ)) + (1 -β j,k (δ))λ j,3-k γ j,3-k (δ), (3.4)
where β j,k (δ) and γ j,k (δ) are respectively the rejection and forwarding probabilities for jobs of type j at data centre k as a function of δ. If there exists a set of thresholds δ = (δ 1 , δ 2 ) such that both resources in both data centres are underloaded after the deployment of this scheme, then, with probability equals to 1, no job is rejected (β j,k (δ) = 0, for 1 ≤ j, k ≤ 2) and only jobs of type 1 are forwarded from data centre 1 and jobs of type 2 from data centre 2 (γ p,3-p (δ) = 0, for 1 ≤ p ≤ 2). Therefore, if these parameters exist, the following relations must hold

         R µ 1 λ 1,1 (1 -γ 1 (δ)) + 1 µ 2 (λ 2,1 + λ 2,2 γ 2 (δ)) < R 1 , 1 µ 1 (λ 2,1 + λ 1,1 γ 1 (δ)) + C µ 2 λ 2,2 (1 -γ 2 (δ)) < C 2 , (3.5)
and

         1 µ 1 λ 1,1 (1 -γ 1 (δ)) + C µ 2 (λ 2,1 + λ 2,2 γ 2 (δ)) < C 1 , R µ 1 (λ 2,1 + λ 1,1 γ 1 (δ)) + 1 µ 2 λ 2,2 (1 -γ 2 (δ)) < R 2 , (3.6)
where γ p (δ) = γ p,p (δ), for 1 ≤ p ≤ 2. Equation (3.4) is rewritten as

µ p x p,p (δ) = λ p,p (1 -γ p (δ)),
µ q x q,p (δ) = λ q,p + λ q,q γ q (δ), (3.7)

for q = 3 -p and 1 ≤ p ≤ 2.

For practical reasons, we consider the case where neither data centre 1 has a sufficient large capacity of resource 2 to host the combined flow of jobs of type 2 nor data centre 2 disposes of enough units of resource 1 to host the combined flows of jobs of type 1, which is true if

C 1 < λ 2,1 + λ 2,2 µ 2 C and R 2 < λ 1,2 + λ 1,1 µ 1 R. (3.8)
Chapter 3

Scaling Results

Equation (3.8) combined with the Equations (3.2) and (3.3) implies that 0 < γ p (δ) < 1, for 1 ≤ p ≤ 2. Moreover γ p (δ) represents the probability that the p coordinate of the process (Y N (t)) = (Y N (t), t ≥ 0) is positive, meaning resource p is used above the threshold δ p . If the system is stable, the equilibrium point x(δ) must be such that the process (Y N (t)) stays around 0 (in both coordinates) -meaning the process is neither the whole time positive nor negative. Thus, supposing that in the steady state resource p is used "around" the threshold δ p , for 1 ≤ p ≤ 2, we obtain two additional relations

Rx 1,1 (δ) + x 2,1 (δ) = R 1 δ 1 , x 1,2 (δ) + Cx 2,2 (δ) = C 2 δ 2 .
(3.9) Equations (3.7) and (3.9) describe a linear system, whose unique solution is

x (δ) = (x j,k (δ), 1 ≤ j, k ≤ 2) and γ (δ) = γ p (δ), 1 ≤ p ≤ 2 , given by                            x 1,1 (δ) = R 1 δ 1 C + C 2 δ 2 - λ 1,1 + λ 1,2 µ 1 - λ 2,1 + λ 2,2 µ 2 C, x 2,1 (δ) = -C 2 δ 2 R -R 1 δ 1 + λ 1,1 + λ 1,2 µ 1 R + λ 2,1 + λ 2,2 µ 2 RC, x 1,2 (δ) = -R 1 δ 1 C -C 2 δ 2 + λ 2,1 + λ 2,2 µ 2 C + λ 1,1 + λ 1,2 µ 1 RC, x 2,2 (δ) = C 2 δ 2 R + R 1 δ 1 - λ 2,1 + λ 2,2 µ 2 - λ 1,1 + λ 1,2 µ 1 R (3.10)
and

         γ 1 (δ) = µ 1 (RC -1)λ 1,1 R 1 δ 1 C + C 2 δ 2 - (λ 1,1 + λ 1,2 ) µ 1 - C (λ 2,1 + λ 2,2 ) µ 2 , γ 2 (δ) = µ 2 (RC -1)λ 2,2 R 1 δ 1 + C 2 δ 2 R - R (λ 1,1 + λ 1,2 ) µ 1 - (λ 2,1 + λ 2,2 ) µ 2 .
We are now able to express the main result of this paper. We present an operational bandwidth for the thresholds δ 1 and δ 2 which ensure that both resources run beneath the total capacity of the system and that rejections and unnecessary transfers of jobs from one data centre to another are avoided as much as possible. The upper and lower boundaries for the thresholds δ 1 and δ 2 such that Inequalities (3.5) and (3.6) hold are defined in the following proposition.

Proposition 3.1 (Operational Parameters of δ). If δp < δ p < 1, for 1 ≤ p ≤ 2, then Conditions (3.5) and (3.6) hold, where

         δ1 def. = 1 R 1 λ 1,1 + λ 1,2 µ 1 R + λ 2,1 + λ 2,2 µ 2 -R 2 , δ2 def. = 1 C 2 λ 1,2 + λ 1,1 µ 1 + λ 2,2 + λ 2,1 µ 2 C -C 1 , such that x (δ) ∈ D def. = x ∈ R 2×2 + : Ax < G and γ (δ) ∈ (0, 1) 2 .
Proof. Combining Equation (3.10) and Inequality (3.6), we define the realvalued function ϕ : (0, 1)

2 → R 2 + , ϕ(δ) = (ϕ 1 (δ), ϕ 2 (δ)), such that          ϕ 1 (δ) def. = C 1 - λ 1,1 (1 -γ 1 (δ)) µ 1 - λ 2,1 + λ 2,2 γ 2 (δ) µ 2 C, ϕ 2 (δ) def. = R 2 - λ 2,1 + λ 1,1 γ 1 (δ) µ 1 R - λ 2,2 (1 -γ 2 (δ)) µ 2 .
It is simple to see that δ = ( δ1 , δ2 ) is the unique element of the set ϕ -1 (0) and is given by

         δ1 = 1 R 1 R µ 1 (λ 1,1 + λ 1,2 ) + 1 µ 2 (λ 2,1 + λ 2,2 ) -R 2 , δ2 = 1 C 2 C µ 2 (λ 2,2 + λ 2,1 ) + 1 µ 1 (λ 1,2 + λ 1,1 ) -C 1 .
Hence, if δ > δ then Inequality (3.6) holds, since the gradient ∇ δ ϕ(δ) is nonnegative. Similarly, if δ < (1, 1) then Inequality (3.5) holds. Therefore, if δ < δ < (1, 1) then Ax (δ) < G.

In addition, all the elements of the gradient ∇ δ γ(δ) are negative. Thus, the single elements in γ -1 (0) and γ -1 (1) define respectively an upper and a lower boundary for δ with

γ -1 (0) =      λ 1,1 µ 1 R + λ 2,1 µ 2 R 1 , λ 1,2 µ 1 + λ 2,2 µ 2 C C 2      and γ -1 (1) = λ 2,1 + λ 2,2 µ 2 R 1 , λ 1,2 + λ 1,1 µ 1 C 2 .
If Equations (3.2) and (3.3) hold then both elements of γ -1 (0) are greater than 1, and if Equation (3.8) holds then γ -1 (1) < δ. Therefore, if δ < δ < (1, 1) then 0 < γ 1 (δ), γ 2 (δ) < 1.

It is worth noting that the lower boundary δ is obtained by assessing which proportion of jobs can be offloaded from one data centre to another without jamming the a priori underloaded resources in the hosting data centre. With this in mind, we are able to show that the point x (δ) (and the associated offloading rates γ (δ)) is indeed the equilibrium point of the dynamical system where the probability that each coordinate of Y N (t) is positive is γ (δ). This point captures the first order behaviour of the system and the probability that (at equilibrium) a job is transferred from one data centre to another.

The limiting process

We are now investigating the asymptotic behaviour of the process (Y N (t)) defined by Relation (3.1). Recall that the resource p at data centre p is operating above the threshold level δ p at time

t if Y N p (t) ≥ 0 or bellow the threshold level if Y N p (t) < 0, for 1 ≤ p ≤ 2.
If N is large, up to the level of a change in time scale, the processes (Y N (t)) and (L N (t)/N ) coexist in different time scales. The fast process (Y N (t)) sees the show process (L N (t)/N ) as fixed while the slow process sees the fast process at equilibrium. Using the same framework of Hunt and Kurtz [START_REF] Hunt | Large loss networks[END_REF] we have that the process (Y N (t/N )) converges in distribution to a random walk U x(t) (t) on the extended integers line, where x(t) is the limit of (L N (t)/N ), seen as constant by (Y N (t/N )). In the following, we introduce the random walk U x (t).

Definition 3.1. For fixed x = (x j,k , 1 ≤ j, k ≤ 2) ∈ R 2×2 + , let (U x (t)) = ((U x,h (t), U x,v (t)), t ≥ 0)
be the Markov process on Z 2 with the positive elements of its Q-matrix,

Q U = (q x (n, n ), n, n ∈ Z 2 ),
given by

q x (n, n + b) =                                    λ 1,1 1 {n 1 <0} if b = (R, 0), λ 2,1 + λ 2,2 1 {n 2 ≥0} if b = (1, 0), λ 1,2 + λ 1,1 1 {n 1 ≥0} if b = (0, 1), λ 2,2 1 {n 2 <0} if b = (0, C), µ 1 x 1,1 if b = -(R, 0), µ 2 x 2,1 if b = -(1, 0), µ 1 x 1,2 if b = -(0, 1), µ 2 x 2,2 if b = -(0, C).
In the following, we define the regions ∆ 0 where the process U x (t) is ergodic.

Definition 3.2. The region

∆ 0 ⊂ R 2×2 + is given by ∆ 0 def. = ∆ A ∩ (∆ B.1 ∪ ∆ B.2 ∪ ∆ B.3 ) , such that -x ∈ ∆ A if and only if Rλ 1,1 + λ 2,1 > Rµ 1 x 1,1 + µ 2 x 2,1 , λ 1,2 + Cλ 2,2 > µ 1 x 1,2 + Cµ 2 x 2,2 . -x ∈ ∆ B,1 if and only if λ 2,1 + λ 2,2 < Rµ 1 x 1,1 + µ 2 x 2,1 , λ 1,2 + λ 1,1 < µ 1 x 1,2 + Cµ 2 x 2,2 . -x ∈ ∆ B,2 if and only if          λ 2,1 + λ 2,2 < Rµ 1 x 1,1 + µ 2 x 2,1 , λ 1,2 + λ 1,1 > µ 1 x 1,2 + Cµ 2 x 2,2 , λ 1,2 + λ 1,1 + λ 2,1 + λ 2,2 R < µ 1 x 1,2 + Cµ 2 x 2,2 + µ 1 x 1,1 + µ 2 x 2,1 R .
Chapter 3

Scaling Results

x ∈ ∆ B,3 if and only if

         λ 2,1 + λ 2,2 + λ 1,2 + λ 1,1 C < Rµ 1 x 1,1 + µ 2 x 2,1 + µ 1 x 1,2 C + µ 2 x 2,2 , λ 2,1 + λ 2,2 > Rµ 1 x 1,1 + µ 2 x 2,1 , λ 1,2 + λ 1,1 < µ 1 x 1,2 + Cµ 2 x 2,2 .
In the following proposition, we show that if x ∈ ∆ 0 then the process (U x (t)) is ergodic, using the framework in Kingman [START_REF] Kingman | The ergodic behaviour of random walks[END_REF], Rybko and Stolyar [START_REF] Rybko | Ergodicity of stochastic processes describing the operation of open queueing networks[END_REF] and Malyshev [Mal93]. This result builds upon the the convergence of the fluid limits associated with the process (U x (t)) to zero in a finite time.

Fluid Limits Consider the stochastic process (X(t)) which takes values in Proposition 3.2. The Markov process

Z d with X(0) = x. If x def. = |x 1 | + • • • + |x d | = N
(U x (t)) is ergodic if x ∈ ∆ 0 .
Proof. The ergodicity conditions for this Markov process are derived by determining under which conditions the associated fluid limits converge to zero after some finite time. Kingman [Kin61] takes a similar approach in the analysis of reflected random walks in N 2 , observing the fact that far away from the axes the (first order) evolution of these processes is solely defined by their mean drifts. Let ϕ : Z 2 → R 2 be the drift at any point n ∈ Z 2 , given by

ϕ(n) def. = n∈Z 2 n =n q x (n, n )(n -n).
The drift in the interior of each quadrant p is the constant vector

θ p = (θ p,h , θ p,v ) = ϕ(n),
for any n in the quadrant p, for 1 ≤ p ≤ 4, see Figure 3.2.

In the following, we prove that if x ∈ ∆ A ∩ ∆ B,2 then any fluid limit of such process starting from some initial state u ∈ N 2 reaches the ordinate axis in finite time and then evolves along this axis towards the origin of the plane. Once the fluid limit reaches abscissa axis (at the origin R 2 ), it stays. The fluid limit in the interior of N 2 We start by showing that from any initial state u ∈ N 2 , the process (U x (t)) reaches either axis in some finite time.

0 n 1 n 2 p=1 p=2 p=3 p=4 Rµ 1 x 1,1 + µ 2 x 2,1 µ 1 x 1,2 + Cµ 2 x 2,2 λ 1,2 + λ 1,1 λ 2,1 + λ 2,2 Rµ 1 x 1,1 + µ 2 x 2,1 µ 1 x 1,2 + Cµ 2 x 2,2 λ 1,2 Rλ 1,1 + λ 2,1 + λ 2,2 Rµ 1 x 1,1 + µ 2 x 2,1 µ 1 x 1,2 + Cµ 2 x 2,2 λ 1,2 + Cλ 2,2 Rλ 1,1 + λ 2,1 Rµ 1 x 1,1 + µ 2 x 2,1 µ 1 x 1,2 + Cµ 2 x 2,2 λ 1,1 + λ 1,2 + Cλ 2,2 λ 2,1
For N ≥ 1, we define the process

U N x (t) def. = U N x,h (t), U N x,v (t) , t ≥ 0
with the same Q-matrix as the process (U x (t)) and initial value

u = ( N α , N -N α ),
such that 0 < α < 1 and lim N →+∞ u/N = (α, 1 -α).

In the interior of the positive quarter plane the components of the Markov (U N x (t)) behave like independent random walks on N. Therefore, the renormalised version of the process converges as follows lim

N →+∞ U N x (N t) N , t < τ dist. = ((α, 1 -α) + θ 1 t, t < τ ) , with θ 1 = (λ 2,1 + λ 2,2 -Rµ 1 x 1,1 -µ 2 x 2,1 , λ 1,2 + λ 1,1 -µ 1 x 1,2 -Cµ 2 x 2,2 )
and

τ = α/ (-θ 1,h ) + ∧ (1 -α)/ (-θ 1,v ) + ≤ +∞. Thus, if x ∈ ∆ B,2 then θ 1,h is negative and θ 1,v is positive, so τ = α Rµ 1 x 1,1 + µ 2 x 2,1 -λ 2,1 -λ 2,2 < +∞.
Therefore, if x ∈ ∆ B,2 then any fluid limit in the interior of the positive quadrant reaches the ordinate axis after some finite time τ , or, equivalently, the time that is necessary for the horizontal component of the rescaled process to reach zero converges almost surely to τ < +∞.

The fluid limit along the ordinate axis Due to the strong Markov property, the analysis is reduced to the case where the initial state of the process (U N x (t)) satisfies lim N →+∞ u/N = (0, 1). At the fluid time scale (N t), from the perspective of the large component (in this case, the vertical) the other component (the horizontal) is at equilibrium. Moreover, at u, this point "far away" from the abscissa axis, the discontinuities involving this axis do not interfere in the evolution of the process (U N

x,v (t)). Using the results in Propositions 3.5 and 3.6 (of the Appendix), we derive the equilibrium properties of the horizontal component of this process. Particularly, the drift of the vertical component of this process is dependent on the location of its horizontal component, such that

θ 1,v = λ 1,2 + λ 1,1 -µ 1 x 1,2 -Cµ 2 x 2,2 or θ 2,v = λ 1,2 -µ 1 x 1,2 -Cµ 2 x 2,2 ,
depending on whether the horizontal component is positive or negative. Thus, the local equilibrium of the horizontal component determines the mean vertical drift of the (large) vertical component.

Indeed, far from the abscissa axis and along the ordinate axis, (U N x,h (t)) behaves like the random walk (W (t)) on Z, described in Definition 3.4, with

P = 2, B 1 = 1, B 2 = R, κ 1 = λ 2,1 + λ 2,2 , κ 2 = λ 1,1 , η 1 = µ 2 x 2,1 , η 2 = µ 1 x 1,1 , ρ 1 = λ 2,1 + λ 2,2 and ρ 2 = 0. Proposition 3.5 shows that if x ∈ ∆ A ∩ ∆ B,2
, then the associated process (W (t)) is ergodic. In this case, (U N x,v (t)) behaves like a random walk in the Markovian Environment (see Section 9.6 of Robert [START_REF] Ph | Stochastic Networks and Queues[END_REF]p. 271]). From this reference, we derive the following convergence lim

N →+∞ U N x (t) N , t < τ dist. = 0, 1 + θv t , t < τ where θv def. = θ 1,v ν(N) + θ 2,v ν(Z * -) = λ 2,1 + λ 2,2 -Rµ 1 x 1,1 -µ 2 x 2,1 R -λ 1,2 -λ 1,1 + µ 1 x 1,2 + Cµ 2 x 2,2 ,
with ν(N) and ν(Z * -) given by Proposition 3.6, and τ = 1/ -θv + . Finally, if x ∈ ∆ B,2 then θv < 0 and τ < +∞.

In the origin, if x ∈ ∆ A ∩∆ B,2 , then θ 2,h , θ 3,h , θ 3,v , θ 4,v > 0 and θ 2,v , θ 4,h < 0 such that the fluid limit does not scape from any direction. This concludes the case where x ∈ ∆ A ∩ ∆ B,2 and u ∈ N 2 .

Other cases For the cases where u ∈ N 2 , the previous arguments can be easily adapted for the cases where x ∈ ∆ 0 \ ∆ B,2 . If x ∈ ∆ A ∩ ∆ B,3 then fluid limits reach the abscissa axis instead, evolving along this axis until the origin of the plane. Or, if x ∈ ∆ A ∩ ∆ B,1 then the fluid limits reach some of the axis and then goes along until reaching the origin of the plane.

With the same sort of arguments used in the case u ∈ N 2 , the direction of the constant drift θ p for 2 ≤ p ≤ 4 is enough to extend the results for any u ∈ Z 2 \ N 2 and x ∈ ∆ 0 . The dynamics of the fluid limits are the same as before, such that the fluid limits reach some axis and evolve along it until reaching the origin of the plane where it stays. It is worth mentioning that, if u ∈ N × Z * -and x ∈ ∆ A ∩ ∆ B,2 then fluid limits may reach and cross the abscissa axis, going from N × Z * -to N 2 . However, the strong Markov property yields that this scenario is the same presented before for u ∈ N 2 . The symmetric case may happen if u ∈ Z * -× N and x ∈ ∆ A ∩ ∆ B,3 , with same consequences.

Figure 3.3 synthesises directions of the fluid limits drifts, for x ∈ ∆ 0 . Note that the mean drift in the axis of the positive quarter plane ( θv in the case above) are highlighted in red only if the relevant drifts in their neighbours do not have the same direction. The proposition is proved. Finally, the probabilities of each component of this process being either negative or positive can be derived. This measure is related to the performance of the system, since it indicates the probability of a job to be hosted locally or to be offloaded. We use a similar approach as in Proposition 3.6. Proposition 3.3 (Invariant measure). For fixed x ∈ ∆ 0 , given by Definition 3.2, the stationary probability that either component of the process (U x (t)) is negative is

0 n 1 n 2 (a) if x ∈ ∆ A ∩ ∆ B,1 0 n 1 n 2 (b) if x ∈ ∆ A ∩ ∆ B,2 0 n 1 n 2 (c) if x ∈ ∆ A ∩ ∆ B,3
π x (Z * -×Z) = RCµ 1 x 1,1 + C (µ 2 x 2,2 + µ 2 x 2,1 -λ 2,2 -λ 2,1 ) + µ 1 x 1,2 -λ 1,2 -λ 1,1 λ 1,1 (RC -1)
and

π x (Z×Z * -) = RCµ 1 x 2,2 + R (µ 1 x 1,1 + µ 1 x 1,2 -λ 1,1 -λ 1,2 ) + µ 2 x 2,1 -λ 2,1 -λ 2,2
λ 2,2 (RC -1) .

Proof. Let x ∈ ∆ 0 ,X be fixed such that the process (U x (t)) is ergodic with invariant probability measure π x = (π x (n), n ∈ Z 2 ) and X be a random variable with finite support on Z 2 and distribution π x . Also let f u : Z 2 → C be a complex-valued function, such that u def.

= (u 1 , u 2 ) and f u (n) = u n 1 1 u n 2 2 .
Chapter 3

Scaling Results

Writing the balance equation of the process (U x (t)), we obtain the following relation

n,n ∈Z 2 n =n π x (n)q x (n, n )(f u (n ) -f u (n)) = 0. (3.11) Let u ∈ ∂D 2 (1) def. = u ∈ C 2 : |u 1 | = |u 2 | = 1 and, for Z ⊆ Z 2 , E f u (X)1 {X∈Z} = n∈Z π x (n)f u (n).
Rearranging the terms of the Equation (3.11), for u ∈ ∂D 2 (1), it yields

E (f u (X)) K 1 (u) = E f u (X)1 {X∈Z * -×Z} K 2 (u) + E f u (X)1 {X∈Z×Z * -} K 3 (u), with K 1 (u) def. = µ 1 x 1,1 1 -u -R 1 + µ 2 x 2,1 1 -u -1 1 + (λ 2,1 + λ 2,2 ) (1 -u 1 ) + µ 2 x 2,2 1 -u -C 2 + µ 1 x 1,2 1 -u -1 2 + (λ 1,2 + λ 1,1 ) (1 -u 2 ) K 2 (u) def. = λ 1,1 u R 1 -u 2 K 3 (u) def. = λ 2,2 u C 2 -u 1 . By definition, for Z ⊆ Z 2 , lim u→(1,1) E f u (X)1 {X∈Z} = π x (Z),
and as the point (1, 1) is a simple root K 1 (u), K 2 (u) and K 3 (u), we have

π x Z * -×Z = lim u 1 →1 K 1 u 1 , C √ u 1 K 2 u 1 , C √ u 1 = RCµ 1 x 1,1 + C (µ 2 x 2,2 + µ 2 x 2,1 -λ 2,2 -λ 2,1 ) + µ 1 x 1,2 -λ 1,2 -λ 1,1 λ 1,1 (RC -1) .
With a similar method one obtains π x Z×Z * -, taking the limit when u 2 → 1 and u 1 = R √ u 2 . The proposition is proved.

The following corollary makes explicit that the fixed point obtained using the heuristic approach is indeed the equilibrium point of the stochastic system. Corollary 3.1. If x = x , given by Equation (3.10) then π x (N×Z) = γ 1 (δ) and π x (Z×N) = γ 2 (δ).

Time Evolution

In this section, we study the transient behaviour the system. Using a similar approach to Hunt and Kurtz [START_REF] Hunt | Large loss networks[END_REF], we are able to prove that the dynamical system associated with the Markovian process (L N (t)) has only one stable point, which is absorbent and is the same as x , given by Equation (3.10) while the probabilities that of each component of (Y N (t)) is either negative or positive converges to γ .

Stochastic Evolution Equations

For ξ > 0, let N ξ denote a Poisson process on R + with rate ξ and (N ξ ) an i.i.d. sequence of such processes. All Poisson processes are assumed to be independent. Classically, the process (L N (t)) can be seen as the unique solution to the following stochastic differential equations (SDE),

                             dL N p,p (t) = N N λp,p (dt)1 {Y N p (t -)<0,m N q,p (t -)≥1} - +∞ =1 N µp (dt)1 { ≤L N p,p (t -)} +N N λp,q (dt) 1 -1 {m N q (t -)≥Ap} 1 {m N p (t -)≥Ap} dL N q,p (t) = N N λq,p (dt)1 {m N p (t -)≥Aq} +∞ =1 N µq (dt)1 { ≤L N q,p (t -)} +N N λq,q (dt) 1 -1 {Y N q (t -)<0,m N p,q (t -)≥1} 1 {m N p (t -)≥Aq} (3.12)
for 1 ≤ p ≤ 2 and q = 3 -p, with initial condition

L N (0) ∈ N 2×2 such that AL N (0) ≤ G N .
We start the analysis showing that the equivalent dynamical system does not reach the boundaries of the convex hull where it lives if its initial point observes some conditions. Therefore, in that case, the process (m N (t)) does not influence the evolution of process (L N (t)) since, with probability 1, this process lives inside the convex hull without ever touching its boundaries. In the following, we introduce the dynamical system z(t) and the region ∆ F , where it takes values.

Definition 3.3. If x ∈ ∆ F (δ) then x 1,1 R + x 2,1 = R 1 δ 1 , x 1,1 + x 2,1 C < C 1 , and x 1,2 R + x 2,1 < R 2 , x 1,2 + x 2,2 C = C 2 δ 2 . Lemma 3.1 (Dynamical System Convergence). If (z(t)) def. = ((z i,k (t), 1 ≤ i, k ≤ 2) , t ≥ 0)
is governed by the following dynamical system żp,p (t) = -µ 1 z p,p (t) + λ p,p (1 -ψ p (z(t))), żq,p (t) = -µ q z q,p (t) + λ q,p + λ q,q ψ q (z(t)), (

Chapter 3 3.4. Time Evolution

for q = 3 -p and 1 ≤ p ≤ 2 with z(0) ∈ ∆ F (δ), ψ 1 (z(t)) = 1 λ 1,1 (RC -1) [RC (λ 1,1 -µ 1 z 1,1 (t)) + (λ 1,2 -µ 1 z 1,2 (t)) + C (λ 2,2 -µ 2 z 2,2 (t) + λ 2,1 -µ 2 z 2,1 (t))]
and

ψ 2 (z(t)) = 1 λ 2,2 (RC -1) [RC (λ 2,2 -µ 2 z 2,2 (t)) + (λ 2,1 -µ 2 z 2,1 (t)) + R (λ 1,1 -µ 1 z 1,1 (t) + λ 1,2 -µ 1 z 1,2 (t))]
then the dynamical system converges exponentially fast to the stable fixed point fixed point z /(RC -1), where z = (z i,k , 1 ≤ i, k ≤ 2) and

                           z 1,1 = R 1 δ 1 C + C 2 δ 2 - λ 1,1 + λ 1,2 µ 1 - λ 2,1 + λ 2,2 µ 2 C, z 2,1 = -C 2 δ 2 R -R 1 δ 1 + λ 1,1 + λ 1,2 µ 1 R + λ 2,1 + λ 2,2 µ 2 RC, z 1,2 = -R 1 δ 1 C -C 2 δ 2 + λ 2,1 + λ 2,2 µ 2 C + λ 1,1 + λ 1,2 µ 1 RC, z 2,2 = C 2 δ 2 R + R 1 δ 1 - λ 2,1 + λ 2,2 µ 2 - λ 1,1 + λ 1,2 µ 1 R.
(3.14) Also, for t ≥ 0, the dynamical system z(t) at t stays in region ∆ F (δ).

Proof. The mapping t → z(t) has the following integral form

z(t) = z(0) + t 0 ż(ds)
which admits the following explicit solution

z(t) =              z 1,1 (t) = z 1,1 (RC -1) -1 + α 1 e -µ 1 t + Cβ 1 e -µ 2 t , z 2,1 (t) = z 2,1 (RC -1) -1 -Rα 1 e -µ 1 t -RCβ 1 e -µ 2 t , z 1,2 (t) = z 1,2 (RC -1) -1 -RCα 2 e -µ 1 t -Cβ 2 e -µ 2 t , z 1,2 (t) = z 2,2 (RC -1) -1 + Rα 2 e -µ 1 t + β 2 e -µ 2 t ,
where

α 1 = λ 1,1 + λ 1,2 µ 1 -z 1,1 (0) -z 1,2 (0), β 1 = λ 2,1 + λ 2,2 µ 2 -z 2,2 (0) -z 2,1 (0)
,

α 2 = λ 1,1 + λ 1,2 µ 1 -z 1,1 (0) -z 1,2 (0), β 2 = λ 2,1 + λ 2,2 µ 2 -z 2,2 (0) -z 2,1 (0).
So, for t ≥ 0, the following relations hold

d dt Rz 1,1 (t) + z 2,1 (t) = d dt z 1,2 (t) + Cz 2,2 (t) = 0.
Chapter 3

Time Evolution

Finally, we can rewrite the dynamical system t → z(t) by using the autonomous system ω(t) = (ω 1 (t), ω 2 (t)), such that

Rz 1,1 (t) + z 2,1 (t) = R 1 δ 1 , z 1,2 (t) + Cz 2,2 (t) = C 2 δ 2 and z 1,1 (t) + Cz 2,1 (t) = z 1,1 + Cz 2,1 + ω 1 (t) Rz 1,2 (t) + z 2,2 (t) = Rz 1,2 + z 2,2 + ω 2 (t),
where

ω 1 (0) = z 1,1 (0) -z 1,1 + C(z 2,1 (0) -z 2,1
)

ω 2 (0) = R(z 1,2 (0) -z 1,2 ) + z 2,2 (0) -z 2,2 ,
and

ω(t) = F ω(t), with F = 1 RC -1 µ 1 -RCµ 2 C (µ 2 -µ 1 ) R (µ 1 -µ 2 ) µ 2 -RCµ 1 .
It is straightforward to see that the eigenvalues of F are negative since it is assumed that

µ p /µ 3-p < RC, for 1 ≤ p ≤ 2. Therefore, one concludes that if z(0) ∈ ∆ F (δ) then z(t) ∈ ∆ F (δ) for t > 0.
Proposition 3.4 (Limiting Dynamical System). Under Conditions (3.5) and (3.6) and for δ < δ < (1, 1), where δ is defined by Proposition 3.1, if the initial state L N (0) is such that

RL N 1,1 (0) + L N 2,1 (0) = R 1 δ 1 + o(N ), L N 1,2 (0) + CL N 2,2 (0) = C 2 δ 2 + o(N )
and

L N 1,1 (0) + CL N 2,1 (0) < C 1 + o(N ), RL N 1,2 (0) + L N 2,2 (0) < R 2 + o(N ), such that lim N →+∞ L N (0) N = l(0) ∈ ∆ F (δ)
then there exists a continuous process

(l(t)) = ((l j,k (t), 1 ≤ j, k ≤ 2), t ≥ 0), such that the convergence below lim N →+∞ L N (t) N , t 0 f Y N (u) du dist. = l(t), t 0 Z 2 f (x) π l(u) (dx) du
holds for any function f with finite support on Z 2 and l(t) satisfies

lp,p (t) = -µ p l p,p (t) + λ p,p (1 -π l(t) (A p )),
lq,p (t) = -µ q l q,p (t) + λ q,p + λ q,q π l(t) (A q ), with π l(t) given in Proposition 3.3, A p = {(y 1 , y 2 ) ∈ Z 2 : y p ∈ N}..

Proof. Just as it is common in classical stochastic calculus, (L N (t)/N ) can be written as the renormalised integral solution of Equation (3.12). However, by Lemma 3.1 we show that an equivalent dynamical system (z(t)), starting in ∆ F (δ) remains ∆ F (δ) and, consequentially, does not reach the boundaries of the closed hull where it is defined, with probability 1. Therefore, translating to the equation above, it implies that the fluid limits live sufficiently far from the borders that enclose the set

D def. = x ∈ R 2×2 + : Ax < G
such that the free slots process (m N (t)) does not influence the evolution of process (L N (t)). Thus, the solution of the SDE (3.12) is simply written as, for 1 ≤ p ≤ 2 and q = 3 -p,

                   L N p,p (t) N = L N p,p (0) N + M N p,p (t) + λ p,p t 0 1 {Y N p (s)<0} ds -µ p t 0 L N p,p (s) N ds, L N q,p (t) N = L N q,p (0) N + M N q,p (t) + λ q,p t -µ q t 0 L N q,p (s) N ds +λ q,q t 0 1 {Y N q (s)≥0} ds
where M N p,p (t) and M N q,p (t) are martingales, whose increasing predictable processes at time t are given by

           M N p,p (t) = 1 N (λ p,p t 0 1 {Y N p (s)<0} ds + µ p t 0 L N p,p (s) N ds M N q,p (t) = 1 N λ q,p t + λ q,q t 0 1 {Y N q (s)≥0} ds + µ q t 0 L N q,p (s) N ds .
Doob's inequality yields the martingale M N (t) = M N j,k (t), 1 ≤ j, k ≤ 2 becomes negligible of order 1/ √ N as N goes to infinity. For > 0,

P sup 0≤s≤t sup 1≤j,k≤2 M N j,k (s) ≥ ≤ 1 2 E sup 1≤j,k≤2 M N j,k (t) 2 -----→ N →+∞ 0.
Moreover, using the same method as Hunt and Kurtz [START_REF] Hunt | Large loss networks[END_REF], we obtain a result analogous to the Theorem 3 of this reference. As the process (Y N (t)) is ergodic, the following convergence holds lim

N →+∞ L N (t) N , t 0 1 {Y N 1 (s)<0} ds, t 0 1 {Y N 2 (s)<0} ds dist. = l(t), t 0 π l(s) Z * -×Z ds, t 0 π l(s) Z×Z * -ds .
From Proposition 3.3, we have that lim

N →+∞ π l(t) (N×Z), π l(t) (Z×N) = (ψ 1 (l(t)), ψ 2 (l(t))) .
which implies that l(t) = ż(t). Hence, if l(0) = z(0) then l(t) = z(t) for t > 0. Therefore, the convergence holds, such that lim t→+∞ l(t) = z = x . The proposition is proved.

Chapter 3

Conclusion

Corollary 3.2. The equilibrium point of the Dynamical System z(t) described in Equation (3.13) is given by z the solution of Equation (3.14). Moreover, (z , ψ(z )) = (x , γ ) .

Conclusion

We have proposed in this paper an analytical model to study a simple offloading strategy for data centres in the framework of multi-resource Cloud Computing, under asymmetric service loads such each data centre is running low on one of the resources. The strategy considered consists of forwarding jobs with the highest demand for the resource locally depleted, if this resource is being used above a fixed threshold. The key finding is that the proposed strategy can significantly improve the performance of both data centres. A next step consists of studying the implementation of a dynamic mechanism of the parametrisation of these thresholds.

0 x 1,1 x 2,1 R 1 R C 1 C R 1 δ 1 R µ 1 x 1,1 µ 2 x 2,1 λ 2,1 + λ 2,2 γ 2,2 λ 1,1 + λ 1,2 γ 1,2 µ 1 x 1,1 µ 2 x 2,1 λ 2,1 + λ 2,2 γ 2,2 λ 1,2 γ 1,2 ρ 1 0 x 1,2 x 2,2 R 2 R C 2 C C 2 δ 2 C µ 1 x 1,2 µ 2 x 2,2 λ 2,2 + λ 2,1 γ 2,1 λ 1,2 + λ 1,1 γ 1,1 µ 1 x 1,2 µ 2 x 2,2 λ 2,1 γ 2,1 λ 1,2 + λ 1,1 γ 1,1 ρ 2
m k = (m 1,k , m 2,k ) Free resources vector Require: Y k Offloading trigger Require: j ∈ {1, 2}, A j = (A 1,j , A 2,j )
Type of request Require: p ∈ {k, k } Origin of the request Ensure: q ∈ {k, k , 0} Placement, offloading or rejection

1: q ← k Initial Placement 2: if p = k then Local Job treatment 3: if j = j (k) then j (k) = k: jamming type of Job 4: if Y k > 0 then
Is occupation threshold reached?

5:
q ← k 6: else 7:

for i ← 1, 2 do ? m k ≥ A j 8: if m i,k < A i,j then 9:
q ← k Offloading end for 29: end if 30: return q Returns: Placement, offloading or rejection

Appendix: limiting Markov processes A random walk on Z

We define a random walk on Z where the transition rates depend whether the state is in either half lines Z * -or N. The goal of this analysis is to determine the stationary probability of this random walk to be in either half-line. For that the characteristic function of the invariant distribution of such process is decomposed in two (analytical) parts using some complex analysis arguments (similar to the Wiener-Hopf factorisation). This method is often used in the analysis of reflected random walks on N, such as GI/GI/1 queue, see Chapter VIII of Asmussen [Asm03, p. 220] and Section 2.2 of Robert [Rob03, p. 33] for instance. See also Fricker et al. [START_REF] Fricker | Allocation schemes of resources with downgrading[END_REF] for a similar (and extended) application of such techniques.

The random walk is properly defined as follows.

Definition 3.4. For fixed P ∈ N * , let (W (t))

def.

= (W (t), t ≥ 0) be the Markov process on Z whose non-negative elements of its Q-matrix,

Q W = q(n, n ), n, n ∈ Z , are given by q(n, n ) =            κ p if n = n + B p and n < 0, ρ p if n = n + B p and n ≥ 0, η p if n = n -B p , 0 otherwise, with 1 = B 1 < • • • < B P ∈ N and κ 1 + ρ 1 + η 1 > 0.
In the following proposition, we present the stability properties of the Markov process (W (t)).

Proposition 3.5. The Markov process (W (t)) is ergodic if

P p=1 ρ p B p < P p=1 η p B p < P p=1 κ p B p .
(3.15)

When it exists, ν = (ν(n), n ∈ Z) denotes the corresponding invariant distri- bution.
Proof. The Markov process (W (t)) on Z behaves like a random walk on each of the half-lines N and Z * -. At some point n ∈ Z, the drift of the random walk is positive if n ∈ Z * -and negative if n ∈ N. This property implies the ergodicity of the Markov process by using the Lyapounov function F (x) = |x|, for example. See Corollary 8.7 of Robert [START_REF] Ph | Stochastic Networks and Queues[END_REF]p. 214].

In the following proposition, we derive the probability that, at equilibrium, the Markov process (W (t)) is either in the negative or positive half-line. Chapter 3 3.5. Conclusion Proposition 3.6. If Equation (3.15) holds, then (W (t)) is ergodic and at equilibrium the probability that the process is either in the negative or positive half-line is given by

ν(Z * -) = P p=1 B p (η p -ρ p ) P p=1 B p (κ p -ρ p )
and ν(N)

= P p=1 B p (κ p -η p ) P p=1 B p (κ p -ρ p ) . (3.16)
Proof. Let X a random variable with finite support on Z and distribution ν and, for u

∈ C \ R -and n ∈ Z, f u : Z → C such that f u (n) = u n .
For any function f with finite support on Z, the equilibrium equations for the Markov process (W (t)) yield the following relation

ν(Q W (f )) = n,n ∈Z n =n ν(n)q(n, n )(f (n ) -f (n)) = 0, (3.17)
where Q W is the Q-matrix of (W (t)). Replacing f by f u in Equation (3.17), for u ∈ ∂D(1) = {u ∈ C : |u| = 1}, one gets the relation

E f u (X)1 {X≥0} P 1 (u) = -E f u (X)1 {X<0} P 2 (u),
where

               P 1 (u) def. = u B P P p=1 u Bp -1 ρ p + η p u -Bp -1 , P 2 (u) def. = u B P P p=1 u Bp -1 κ p + η p u -Bp -1 .
By definition,

lim u→1 E f u (X)1 {X≥0} = ν(N) and lim u→1 E f u (X)1 {X<0} = ν(Z * -).
Using Equation (3.15), the 1 is a simple root of P 1 (u) and P 2 (u) then one on obtains the following relation

ν(Z * -) ν(N) = lim u→1 - P 2 (u) P 1 (u) = - P p=1 B p (ρ p -η p ) P p=1 B p (κ p -η p )
.

Hence, using the fact that ν(Z * -) + ν(N) = 1, one gets Equation (3.16).

Chapter 4

Analysis of an offloading scheme for data centres in the framework of Fog Computing

Introduction

Cloud computing has become one of the major stakes in the development of information technology by offering the possibility of reserving computing resources online. Commercial offers already exist for customers (residential or business) relying on big data centres like Amazon or Azure [Mic] for example. This kind of technology is also relevant for network operators in the framework of network function virtualisation, where network functions can be instantiated on data centres instead of dedicated hardware. In this context, there is currently a clear trend to distribute data centres. For network operators, it is possible to instantiate at the edge of the network functions which were so far centralised in servers (e.g., mobile core functions). Furthermore, by allocating resources closer to end users, it is expected to offer better quality of experience. Distributing cloud computing resources at the edge of the network is known as fog computing (see [WRSvdM11, BMZA12, RBG12]).

Data centres involved in fog computing have a smaller capacity than those in the case of cloud computing and therefore more subject to congestion. Hence, to reduce the probability of request blocking, fog computing data centres have to collaborate. For instance, when one request cannot be accommodated by one of them, it may be forwarded to another one.

A typical example of such a situation is when data centres are located on a logical ring at the edge of the network. See Figure 4.1. A request arriving in an overloaded data centre with index i, may be forwarded to a neighbouring data centre i-1 or i+1 with some probability. Hence, if the traffic to a data centre is causing saturation, the other data centres may help alleviate this saturation regime. The aim of this chapter is of investigating the impact of such a cooperative scheme. In practice, the network could be backed up by a central (bigger) data centre at the core of the network but at a price in terms of latency. We will not consider this additional feature here.

Introduction Data Centres

i -1 i i + 1 λ i p i p i Figure 4.1 -A Fog Computing Architecture

Collaboration of Two Data Centres

Our aim here is to qualitatively estimate the gain achieved by the collaboration of data centres at the edge of the network. The main part of our analysis will concern the impact of the collaboration of two data centres. It is shown in Section 4.2.4 that the analysis applies also to more general architectures of fog computing, as in Figure 4.1, provided they are not congested.

For i ∈ {1, 2}, the external arrival process of requests to facility/data centre #i, referred to as class i requests, is Poisson with parameter λ i . If one of the C i servers is idle upon arrival, then the request is processed by this data centre. Otherwise, if the data centre is saturated, i.e., all the C i servers are busy, then with probability p i the request is forwarded to the other data centre if it is not saturated too, otherwise with probability 1 -p i the request is rejected. A request allocated at data centre #i is processed at rate µ i .

Considering the number of requests processed at both data centres, this scheme can be clearly represented by a two dimensional Markov process on {0, . . . , C 1 } × {0, . . . , C 2 }. This Markov process, related to loss networks, is not reversible in general and its invariant distribution does not have a product form expression. Even if a numerical analysis of the equilibrium equations is always possible, it is very likely that it will not give precise qualitative and quantitative results concerning the impact of rerouting parameters p 1 and p 2 of the offloading scheme. Our goal is of giving explicit closed form expressions of the equilibrium probability that a request is rejected, see Theorem 4.3 which is our main result in this domain.

To overcome the difficulty of not having an explicit expression of the equilibrium, we have chosen to study a scaled version of this network. The input rates λ 1 , λ 2 and the capacities C 1 , C 2 are assumed to be proportional to a large parameter N which goes to infinity. This scaling has been introduced by Kelly in the context of loss networks (see [START_REF] Kelly | Loss networks[END_REF]). As it will be seen, there is a relation between the parameters (see Condition (E) below), which implies that both data centres can be saturated with positive probability. We will focus mainly on this case which is, in our view, the most interesting situation to assess the benefit of offloading mechanisms in a congested environment. Otherwise, the situation is much simpler. One of the data centres will be underloaded, so that the rejection rate at equilibrium will converge to 0 as N gets large, in particular external arrivals to this data centre and the rerouted jobs from the other data centre will be accepted with probability 1 in the limit. See Proposition 4.1 and Theorem 4.1.

In this limiting regime we prove convergence results for the process describing the number of free servers at both data centres in the same way as in Hunt and Kurtz [START_REF] Hunt | Large loss networks[END_REF] for loss networks. We show that the invariant distribution of a random walk in the quarter plane is playing a key role in the asymptotic behaviour of the loss probabilities at equilibrium. The derivation of the equilibrium is based on the analysis of random walks on N 2 by [START_REF] Fayolle | The two coupled server: the reduction to a Riemann-Hilbert problem[END_REF]. Taking advantage of the specific characteristics of the random walks considered, we are able to get an explicit expression of the generating function of their invariant distributions in terms of elliptic integrals instead of contour integrals in the complex plane as in [START_REF] Fayolle | The two coupled server: the reduction to a Riemann-Hilbert problem[END_REF]. See Theorem 4.3. With these results we can then assess quantitatively the interest of this load balancing mechanism by comparing the respective loss probabilities of the two streams of requests.

The organisation of this chapter is as follows: in Section 4.2 the stochastic model is introduced and the limit results for the scaling regime are obtained. A family of random walks is shown to play a central role. Section 4.3 establishes the functional relation satisfied by the generating function of the invariant measure of one of these random walks. Section 4.4 gives an explicit representation of this generating function in Theorem 4.3 and therefore of the performance metrics of the load balancing mechanism. Section 4.5 presents some numerical examples of these results. Concluding remarks are presented in Section 4.6.

Model description

Model

We consider in this chapter two processing facilities in parallel. The first one is equipped with C 1 servers and serve requests (for computing resources) arriving according to a Poisson process with rate λ 1 ; each request requires an exponentially distributed service time with mean 1/µ 1 (a request if accepted occupies a single server). Similarly, the second processing facility is equipped with C 2 servers and serves service requests arriving according to a Poisson process with rate λ 2 ; service times are exponentially distributed with mean 1/µ 2 .

To reduce the blocking probability, we assume that requests arriving at a service facility with no available servers are forwarded to the other one with a given probability. More precisely, if a request arrives at service facility #1 with no available servers, the request is forwarded to the other service facility with probability p 1 . Similarly, a request arriving at facility #2 with no available servers is forwarded to the other facility with probability p 2 . See Figure 4.2.

Let L 1 (t) and L 2 (t) denote the number of occupied servers in facilities #1 and #2 at time t, respectively. Owing to the Poisson and exponential service time assumptions, (L(t)) = ((L 1 (t), L 2 (t))) is a Markov process with values in

#1 C 1 λ 1 p 1 1-p 1 1 1 if #1 saturated #2 C 2 λ 2 p 2 1-p 2 2 2 if #2 saturated
) to ( 1 + i, 2 + j) occurring at rate              (λ 1 + p 2 λ 2 1 { 2 =C 2 } ) • 1 { 1 <C 1 } if (i, j) = (1, 0), (p 1 λ 1 1 { 1 =C 1 } + λ 2 ) • 1 { 2 <C 2 } if (i, j) = (0, 1), µ 1 1 if (i, j) = (-1, 0), µ 2 2 if (i, j) = (0, -1)
and 0 otherwise. The equilibrium characteristics of this Markov process on a finite state space, like loss probabilities, do not seem to have closed form expressions in general. A scaling approach is used in the following to get some insight on the performance of such a strategy. We first introduce a random walk in N 2 .

A random walk in the extended positive quadrant

We now consider the following random walk in the extended positive quadrant.

Definition 4.1. For fixed l = (l 1 , l 2 ) ∈ R 2 + , one defines the random walk (m l (t)) on (N ∪ {+∞}) 2 as follows: the transition from (m 1 , m 2 ) to (m 1 + a, m 2 + b) occurs at rate

           µ 1 l 1 if (a, b) = (1, 0), µ 2 l 2 if (a, b) = (0, 1), λ 1 + p 2 λ 2 1 {m 2 =0} if (a, b) = (-1, 0) and m 1 > 0, λ 2 + p 1 λ 1 1 {m 1 =0} if (a, b) = (0, -1) and m 2 > 0,
for (m 1 , m 2 ) ∈ (N∪{+∞}) 2 with the convention that +∞±x = +∞ for x ∈ N (see Figure 4.3).

In particular (+∞, +∞) is an absorbing point for the process (m l (t)). The random walk (m l (t)) is a special case of the Markov process investigated in [START_REF] Fayolle | The two coupled server: the reduction to a Riemann-Hilbert problem[END_REF].

(iii) and (iv), the process (m l (t)) can be coupled to two queues, the first one, an M/M/1 queue which is transient and the second one, an ergodic M/M/1 queue, with an invariant distribution which is geometrically distributed.

Heavy Traffic Scaling Regime

We investigate now the case when some of the parameters of the processing facilities are scaled up by a factor N ∈ N. The arrival rates are given by λ 1 N and λ 2 N with λ 1 > 0 and λ 2 > 0. Similarly the capacities are given by C N 1 = N c 1 and C N 2 = N c 2 for some positive constants c 1 and c 2 . To indicate the dependence of the numbers of idle servers upon N , an upper index N is added to the stochastic processes. A similar approach has been used in Alanyali and Hajek [START_REF] Alanyali | Analysis of simple algorithms for dynamic load balancing[END_REF] to study a load balancing scheme in an Erlang system.

We will consider the process

(m N (t)) def. = C N 1 -L N 1 (t), C N 2 -L N 2 (t)
describing the number of idle servers in both processing facilities. As it will be seen, the random walks (m l (t)), l ∈ R 2 + , play an important role in the asymptotic behaviour of (m N (t)) as N goes to infinity.

λ 2 < µ 2 c 2 , λ 1 p 1 + λ 2 > µ 1 c 1 p 1 + µ 2 c 2 , λ 1 < µ 1 c 1 , λ 1 + λ 2 p 2 > µ 1 c 1 + µ 2 c 2 p 2 , or λ 1 > µ 1 c 1 , λ 2 > µ 2 c 2
holds, and if the initial conditions are such that m N (0) = m ∈ N 2 and lim

N →+∞ L N 1 (0) N , L N 2 (0) N = c = (c 1 , c 2 )
then, for the convergence in distribution,

lim N →+∞ L N 1 (t) N , L N 2 (t) N , t 0 f (m N (u)) du dist. = c 1 , c 2 , t N 2 f (x)π c (dx)
for any function f with finite support on N 2 , π c is the invariant distribution of the process (m c (t)) defined previously.

Proof. Using the same method as in [START_REF] Hunt | Large loss networks[END_REF], one gets an analogous result to Theorem 3 of this reference. For the convergence in distribution of processes, the relation lim

N →+∞ L N 1 (t) N , L N 2 (t) N , t 0 f (m N (u)) du dist. = l 1 (t), l 2 (t), t 0 N 2 f (x)π l(u) (dx) du (4.2)
Proposition 4.2. Under Condition (E), as N goes to infinity, the probability that at equilibrium a job of class i ∈ {1, 2} is rejected converges to

β i = π c m ∈ N 2 : m i = 0 (1 -p i ) + p i π c (0, 0) ,
where π c is the invariant distribution of (m c (t)).

Proof. Assume that (L N 1 (t), L N 2 (t)) is at equilibrium, the number of class 1 jobs rejected between 0 and t is given by

R N 1 (t) def. = t 0 1 {m N 1 (u-)=0,B 1 (u-)=0} N λ 1 N (du)+ t 0 1 {m N 1 (u-)=0,m N 2 (u-)=0,B 1 (u-)=1} N λ 1 N (du).
The probability of rejecting a class 1 job is hence given by

P m N 1 (0) = 0, B 1 (0) = 0 + P m N 1 (0) = 0, B 1 (0) = 1, m N 2 (0) = 0 = E(R N 1 (1)) λ 1 N .
Using the martingales associated with Poisson processes, one gets

E(R N 1 (1)) λ 1 N = (1 -p 1 )E 1 0 1 {m N 1 (u-)=0} du + p 1 E 1 0 1 {m N 1 (u-)=0,m N 2 (u-)=0} du ,
one concludes with the convergence of the previous theorem.

When condition (E) is not satisfied, one can obtain an analogous result. Its (elementary) proof is skipped. The results on the asymptotic blocking probability of jobs are summarised in the following proposition, where (A), (B 1 ) and (B 2 ) are exclusive.

Proposition 4.3. Let (A) def. = λ 1 < µ 1 c 1 , λ 2 < µ 2 c 2 , (B 1 ) def. = λ 2 > µ 2 c 2 , λ 1 + λ 2 p 2 < µ 1 c 1 + µ 2 c 2 p 2 and
(B 2 ) def. = λ 1 > µ 1 c 1 , λ 2 + λ 1 p 1 < c 2 µ 2 + µ 1 c 1 p 1 ,
then, at equilibrium, the loss probability of a job of class i ∈ {1, 2} is converging to β i as N goes to infinity, where

β i def. =        π c m ∈ N 2 : m i = 0 (1 -p i ) + p i π c (0, 0) if (E) holds, 0 if (A) or (B i ) holds, (1 -p i ) (1 -µ i c i /λ i ) if (B 3-i ) holds.

An Extension to Multiple Data Centres

In this section, it is assumed that there are J data centres, for 1 ≤ j ≤ J, the j-th data centre has c j N servers and the external arrivals to it are Poisson with parameter λ j N and services are exponentially distributed with parameter µ j . If an external request at data centre j finds all c j N servers occupied, it is re-routed to data centre j + 1 (with J + 1 = 1) or to data centre j -1 (with 0 = J) with probability p j , otherwise it is rejected. In particular a job is rerouted with probability 2p j in the case of congestion. See Figure 4.1.

For 1 ≤ j ≤ J, one defines the random walk (m j c (t)) on N 2 as follows: the transition from (m, n) ∈ N 2 to (m + a, n + b) occurs at rate

           µ j c j if (a, b) = (1, 0), µ j+1 c j+1 if (a, b) = (0, 1), λ j + p j+1 λ j+1 1 {n=0} if (a, b) = (-1, 0) and m > 0, λ j+1 + p j λ j 1 {m=0} if (a, b) = (0, -1) and n > 0.
If one of the conditions

λ j > µ j c j , λ j+1 > µ j+1 c j+1 , λ j+1 < µ j+1 c j+1 λ j + λ j+1 p j+1 > µ j c j + p j+1 µ j+1 c j+1 , or λ j < µ j c j , λ j+1 + λ j p j > µ j+1 c j+1 + p j µ j c j ,
holds, one gets that the associated Markov process is ergodic by Proposition 4.1, one denotes by π j c its invariant probability distribution. As before, one takes the following convention for the indices, J + 1 = 1 and 1 -1 = J.

We now give a version of the previous proposition in this context.

Proposition 4.4. At equilibrium, the loss probability of a job of class j ∈ {1, . . . , J} is converging to β j as N goes to infinity in the following cases, 1. No Congestion. If λ j < µ j c j for all j ∈ {1, . . . , J} then β j ≡ 0.

One saturated node.

If, for some j 0 ∈ {1, . . . , J}, λ j 0 > µ j 0 c j 0 and if λ j < µ j c j holds for all j = j 0 and

λ j 0 +1 + λ j 0 p j 0 < µ j 0 +1 c j 0 +1 + p j 0 µ j 0 c j 0 λ j 0 -1 + λ j 0 p j 0 < µ j 0 -1 c j 0 -1 + p j 0 µ j 0 c j 0 , then β j = 0 if j = j 0 and β j 0 = (1 -2p j 0 )(1 -µ j 0 c j 0 /λ j 0 )
3. Two saturated neighbouring nodes. If, for some j 0 ∈ {1, . . . , J}, one of the conditions (E j 0 ) holds and λ j < µ j c j holds for all j = j 0 , j 0 + 1 and

λ j 0 +2 + λ j 0 +1 p j 0 +1 π j 0 c (N×{0}) < µ j 0 +2 c j 0 +2 λ j 0 -1 + λ j 0 p j 0 π j 0 c ({0}×N) < µ j 0 -1 c j 0 -1 (4.4)
Chapter 4

4.3. Characteristics of the limiting random walk then

β j 0 = π j 0 c ({0}×N) (1 -2p j 0 ) + p j 0 π j 0 c (0, 0) β j 0 +1 = π j 0 c (N×{0}) (1 -2p j 0 +1 ) + p j 0 +1 π j 0 c (0, 0).
The proof is similar to the proof of the previous proposition and is therefore omitted. Note that Condition (3) implies that the nodes with index j 0 -1 and j 0 + 2 are underloaded, so that only nodes with index j 0 and j 0 + 1 are congested. This result covers partially the set of various possibilities but, as long as only two neighbouring nodes are congested, it can be extended quite easily to the case where only pairs of nodes are congested.

When there are at least three neighbouring congested nodes, this method does not apply. It occurs when one of the conditions (E j 0 ) holds and one of the conditions of (3) is not satisfied. One has to consider the invariant distributions of a three dimensional random walk in N 3 for which there are scarce results. Nevertheless this situation should be, in practice, unlikely if the fog computing architecture is conveniently designed so that a local congestion can be solved using the neighbouring resources.

This proposition shows that the evaluation of the performances of the offloading algorithm can be expressed in terms of the invariant distributions of the random walks (m c (t)) introduced in Definition 4.1. The rest of the chapter is devoted to the analysis of these invariant distributions when they exist. In particular, we will derive an explicit expression of the blocking probabilities β i at facility #i.

Characteristics of the limiting random walk

Fundamental equations

Throughout this section, we assume that the first condition of (E) holds. Let m c,1 and m c,2 denote the abscissa and the ordinate of the random walk (m c (t)) in the stationary regime. Under stability condition (E), it is shown in [START_REF] Fayolle | The two coupled server: the reduction to a Riemann-Hilbert problem[END_REF] that the generating function of the stationary numbers m c,1 and m c,2 , defined by P (x, y) def.

= E(x m c,1 y m c,2 ) for complex x and y such that |x| ≤ 1 and absy ≤ 1, satisfies the functional equation h 1 (x, y)P (x, y) = h 2 (x, y)P (x, 0) + h 3 (x, y)P (0, y) + h 4 (x, y)π c (0, 0), with π c (0, 0) standing for P (0, 0) and

h 1 (x, y) def. = -µ 1 c 1 x 2 y -µ 2 c 2 xy 2 + (λ 1 + λ 2 + µ 1 c 1 + µ 2 c 2 )xy -λ 1 y -λ 2 x, h 2 (x, y) def. = λ 2 ((1 -p 2 )xy -x + p 2 y) , h 3 (x, y) def. = λ 1 ((1 -p 1 )xy -y + p 1 x) , h 4 (x, y) def. = (λ 1 p 1 + λ 2 p 2 )xy -p 2 λ 2 y -p 1 λ 1 x.
It is worth noting that

λ 1 p 1 (λ 1 + λ 2 p 2 )h 2 (x, y) + λ 2 p 2 (λ 2 + λ 1 p 1 )h 3 (x, y) = λ 1 λ 2 (1 -p 1 p 2 )h 4 (x, y). (4.5)
In [START_REF] Fayolle | The two coupled server: the reduction to a Riemann-Hilbert problem[END_REF][START_REF] Fayolle | Random Walks in the Quarter-Plane[END_REF], it is shown how to compute the unknown functions using the zeros of the kernel h 1 (x, y) and the results on Riemann-Hilbert problems. In the following we briefly describe how to achieve this goal. For the system under consideration, let us recall that the performance of the system is characterised by the blocking probabilities of the two classes of customers. For customers arriving at facility #1, the blocking probability is given by

β 1 def. = P (0, 1)(1 -p 1 ) + p 1 π c (0, 0) (4.6)
and that for customers arriving at the second facility by

β 2 def. = P (1, 0)(1 -p 2 ) + p 2 π c (0, 0). (4.7)
Using the normalising condition P (1, 1) = 1, we can easily show that

λ 1 + λ 2 p 2 P (1, 0) -µ 1 c 1 = λ 1 P (0, 1) + λ 2 p 2 π c (0, 0)
and

λ 2 + λ 1 p 1 P (0, 1) -µ 2 c 2 = λ 2 P (1, 0) + λ 1 p 1 π c (0, 0).
We then deduce that

P (0, 1) = λ 1 -µ 1 c 1 + p 2 (λ 2 -µ 2 c 2 ) -p 2 (λ 2 + λ 1 p 1 )π c (0, 0) (1 -p 1 p 2 )λ 1 (4.8)
and

P (1, 0) = λ 2 -µ 2 c 2 + p 1 (λ 1 -µ 1 c 1 ) -p 1 (λ 1 + λ 2 p 2 )π c (0, 0) (1 -p 1 p 2 )λ 2 .
(4.9)

The above relations show that the blocking probabilities β 1 and β 2 can be estimated as soon as the quantity π c (0, 0) is known.

Zero pairs of the kernel

The kernel h 1 (x, y) has already been studied in Fayolle and Iasnogorodski [START_REF] Fayolle | The two coupled server: the reduction to a Riemann-Hilbert problem[END_REF] in the framework of coupled servers. For fixed y, the kernel h 1 (x, y) has two roots X 0 (y) and X 1 (y). Using the common definition of the square root such that √ a > 0 for a > 0, the solution which is null at the origin and denoted by X 0 (y), is defined and analytic in C \ ([y 1 , y 2 ] ∪ [y 3 , y 4 ]) where the real numbers y 1 , y 2 , y 3 and y 4 are such that 0 < y 1 < y 2 < 1 < y 3 < y 4 . The other solution X 1 (y) is meromorphic in C \ ([y 1 , y 2 ] ∪ [y 3 , y 4 ]) with a pole at 0. The function X 0 (y) is precisely defined by

X 0 (y) def. = -(µ 2 c 2 y 2 -(λ 1 + λ 2 + µ 1 c 1 + µ 2 c 2 )y + λ 2 ) + σ 1 (y) 2µ 1 c 1 y Chapter 4 4.4. Boundary value problems with ∆ 1 (y) def. = (µ 2 c 2 y 2 -(λ 1 + λ 2 + µ 1 c 1 + µ 2 c 2 )y + λ 2 ) 2 -4µ 1 c 1 λ 1 y 2 ,
where σ 1 (y) is the analytic continuation in C\([y 1 , y 2 ]∪[y 3 , y 4 ]) of the function ∆ 1 (y) defined in the neighbourhood of 0. The other solution is defined as

X 1 (y) def.
= λ 1 /(µ 1 c 1 X 0 (y)). When y crosses the segment [y 1 , y 2 ], X 0 (y) and X 1 (y) describe the circle C r 1 with centre 0 and radius r 1 def.

=

λ 1 /(µ 1 c 1 ) > 1, since from the first of condition of (E), we have λ 1 > µ 1 c 1 .

Similarly, for fixed x, the kernel h 1 (x, y) has two roots Y 0 (x) and Y 1 (x). The root Y 0 (x), which is null at the origin, is analytic in

C \ ([x 1 , x 2 ] ∪ [x 3 , x 4 ]),
where the real numbers x 1 , x 2 , x 3 and x 4 read 0 < x 1 < x 2 < 1 < x 3 < x 4 , and is given by

Y 0 (x) def. = -(µ 1 c 1 x 2 -(λ 1 + λ 2 + µ 1 c 1 + µ 2 c 2 )x + λ 1 ) + σ 2 (x) 2µ 2 c 2 x with ∆ 2 (x) def. = (µ 1 c 1 x 2 -(λ 1 + λ 2 + µ 1 c 1 + µ 2 c 2 )x + λ 1 ) 2 -4µ 2 c 2 λ 2 x 2 ,
where σ 2 (x) is the analytic continuation in C\([x 1 , x 2 ]∪[x 3 , x 4 ]) of the function ∆ 2 (x) defined in the neighbourhood of 0. The other root is defined as = λ 2 /(µ 2 c 2 ).

Y 1 (x)

Boundary value problems

Problem formulation

In Fayolle et al. [START_REF] Fayolle | Random Walks in the Quarter-Plane[END_REF], it is proven that the functions P (x, 0) and P (0, y) can be extended as meromorphic functions in C \ [x 3 , x 4 ] and C \ [y 3 , y 4 ], respectively. Using the fact that X 0 (y) and X 1 (y) are on circle C r 1 for y ∈ [y 1 , y 2 ], we easily deduce that the function P (x, 0), analytic in D r 1 (the disk with centre 0 and radius r 1 ), is such that for

x ∈ C r 1 i h 2 (x, Y 0 (x)) h 3 (x, Y 0 (x)) P (x, 0) = h 4 (x, Y 0 (x)) h 3 (x, Y 0 (x)) π c (0, 0) (4.10)
where

Y 0 (x) ∈ [y 1 , y 2 ].
Similarly, the function P (0, y) is analytic in D r 2 , which is the disk with centre 0 and radius r 2 , and for x ∈ C r 2 , we have i h 3 (X 0 (y), y) h 2 (X 0 (y), y) P (0, y) = h 4 (X 0 (y), y) h 2 (X 0 (y), y) π c (0, 0) . (4.11)

Using Equation (4.5), we have

h 4 (x, y) h 2 (x, y) = - p 2 (λ 2 + λ 1 p 1 ) λ 1 (1 -p 1 p 2 ) i h 3 (x, y) h 2 (x, y) .
Equation (4.11) can then be rewritten as i h 3 (X 0 (y), y) h 2 (X 0 (y), y) P (0, y) + p 2 (λ 2 + λ 1 p 1 ) λ 1 (1 -p 1 p 2 ) π c (0, 0) = 0. (4.12)

Similarly, Equation (4.10) can be rewritten as

i h 2 (x, Y 0 (x)) h 3 (x, Y 0 (x)) P (x, 0) + p 1 (λ 1 + λ 2 p 2 ) λ 2 (1 -p 1 p 2 ) π c (0, 0) = 0. (4.13)
Problem (4.13) corresponds to Problem (7.6) in [START_REF] Fayolle | The two coupled server: the reduction to a Riemann-Hilbert problem[END_REF] for which i 1 = i 2 = i 3 = 0 in the notation of that chapter. The ratio h 2 (x, Y 0 (x))/h 3 (x, Y 0 (x)) corresponds to the function J(x) in [START_REF] Fayolle | The two coupled server: the reduction to a Riemann-Hilbert problem[END_REF].

In the following, we focus on Riemann-Hilbert problem (4.12). The analysis of problem (4.13) is completely symmetrical. Moreover, to compute the blocking probabilities β 1 and β 2 , we only need to compute the quantity π c (0, 0).

Problem resolution

The function P (0, y) is analytic in the open disk D r 2 . Using the reflection principle [START_REF] Cartan | Elementary theory of one or several complex variables[END_REF], the function y → P 0, r 2 2 /y is analytic on the outside of the closed disk D r 2 . It is then easily checked that if we define

F Y (y) def. =          P (0, y) + p 2 (λ 2 + λ 1 p 1 ) λ 1 (1 -p 1 p 2 ) π c (0, 0), y ∈ D r 2 , P 0, r 2 2 /y + p 2 (λ 2 + λ 1 p 1 ) λ 1 (1 -p 1 p 2 ) π c (0, 0), y ∈ C \ D r 2 ,
the function F Y (y) is sectionally analytic with respect to the circle C r 2 , the quantity F Y (y) tends to π c (0, 0)(λ 1 + λ 2 p 2 )/(λ 1 (1 -p 1 p 2 )) when y goes to infinity, and for y ∈ C r 2

F i Y (y) = α Y (y)F e Y (
Y (y) def. = λ 2 (1 -p 1 p 2 )X 0 (y) + yR Y (X 0 (y)) y(µ 2 c 2 (1 -p 1 p 2 )yX 0 (y) + R Y (X 0 (y))) , (4.16)
where

R Y (x) def. = p 1 µ 1 c 1 (1 -p 2 )x 2 + (p 1 p 2 (µ 1 c 1 + µ 2 c 2 ) -(1 -p 2 )(λ 2 + λ 1 p 1 ))x -p 2 (λ 2 + λ 1 p 1 ). (4.17)
Proof. We have for (x, y) such that y ∈ C r 2 and x = X 0 (y)

h 3 (x, ȳ)h 2 (x, y) = λ 1 λ 2 (((1 -p 1 )x -1)((1 -p 2 )x + p 2 )y ȳ -((1 -p 1 )x -1)xȳ + p 1 x((1 -p 2 )x + p 2 )y -p 1 x 2
Using the fact that y ȳ = λ 2 /(µ 2 c 2 ) and h 1 (x, y) = 0, we deduce that

h 3 (x, ȳ)h 2 (x, y) = - λ 1 λ 2 (x -1) µ 2 c 2 y (λ 2 (1 -p 1 p 2 )x + yR Y (x)) ,
where R Y (x) is defined by Equation (4.17), and the result follows.

Since the index of the Riemann-Hilbert (4.14) is null, the solution is as follows.

Lemma 4.2. The solution to the Riemann-Hilbert problem (4.14) exists and is unique and given for y ∈ D r 2 by

F Y (y) def. = λ 1 + λ 2 p 2 λ 1 (1 -p 1 p 2 ) π c (0, 0)ϕ Y (y), (4.18)
where ϕ Y (y)

def.

= exp y π

x 2

x 1

(µ 1 c 1 x 2 -λ 1 )Θ Y (x) xh 1 (x, y) dx (4.19) and Θ Y (x) def. = ArcTan (1 -p 1 p 2 ) -∆ 2 (x) (1 -p 1 p 2 )(µ 1 c 1 x 2 -(λ 1 + λ 2 + µ 1 c 1 + µ 2 c 2 )x + λ 1 ) -2R Y (x)
.

F Y (y) = φ Y (y) exp 1 2iπ Cr 2 log α Y (z) z -y dz
where the function α Y (y) is defined by Equation (4.16) and φ Y (y) is a polynomial (see [START_REF] Dautray | Mathematical Analysis and Numerical Methods for Science and Technology: Volume 4 Integral Equations and Numerical Methods[END_REF]). Since we know that

F Y (y) → π c (0, 0) λ 1 + λ 2 p 2 λ 1 (1 -p 1 p 2 ) as |y| → ∞, then φ Y (y) = λ 1 + λ 2 p 2 λ 1 (1 -p 1 p 2 ) π c (0, 0). Let for y ∈ C r 2 and y = Y 0 (x + i0) for x ∈ [x 1 , x 2 ] Θ Y (x) = arg (-µ 2 c 2 (1 -p 1 p 2 )Y 0 (x + 0i)x -R Y (x))
Using the expression of Y 0 (x), Equation (4.20) follows. It is clear that

log α Y (Y 0 (x + 0i)) = -2iΘ Y (x). Since Y 0 (x + 0i) = Y 0 (x -0i), we have 1 2iπ Cr 2 log α Y (z) z -y dz = 1 π x 2 x 1 log α Y (Y 0 (x + 0i)) Y 0 (x + 0i) -y dY 0 dx (x + 0i) dx = 1 π x 2 x 1 -2i Y 0 (x + 0i) -y dY 0 dx (x + 0i) Θ Y (x) dx.
It is easily checked from the equation h 1 (x, Y 0 (x)) = 0 that

dY 0 dx = -2µ 1 c 1 xY 0 (x) -µ 2 c 2 Y 0 (x) 2 + (λ 1 + λ 2 + µ 1 c 1 + µ 2 c 2 )Y 0 (x) -λ 2 µ 1 c 1 x 2 + 2µ 2 c 2 xY 0 (x) -(λ 1 + λ 2 + µ 1 c 1 + µ 2 c 2 )x + λ 1 . For x ∈ [x 1 , x 2 ], we have µ 1 c 1 x 2 + 2µ 2 c 2 xY 0 (x + 0i) -(λ 1 + λ 2 + µ 1 c 1 + µ 2 c 2 )x + λ 1 = -i -∆ 2 (x) Using once again h 1 (x, Y 0 (x + 0i)) = 0, we obtain for x ∈ [x 1 , x 2 ] dY 0 dx (x + 0i) = (λ 1 -µ 1 c 1 x 2 )Y 0 (x + 0i) -ix -∆ 2 (x)
and then for real y

-2i Y 0 (x + 0i) -y dY 0 dx (x + 0i) = (µ 1 c 1 x 2 -λ 1 )y xh 1 (x, y) .
It follows that for real y

1 2iπ Cr 2 log α Y (z) z -y dz = y π x 2 x 1 (µ 1 c 1 x 2 -λ 1 )Θ Y (x) xh 1 (x,
P (0,y) def. =                λ 1 + λ 2 p 2 λ 1 (1 -p 1 p 2 ) π c (0, 0)ϕ Y (y) - p 2 (λ 2 + λ 1 p 1 ) λ 1 (1 -p 1 p 2 ) π c (0, 0), y ∈ D r 2 , λ 1 + λ 2 p 2 λ 1 (1 -p 1 p 2 ) π c (0,0)α Y (y)ϕ Y (y) - p 2 (λ 2 + λ 1 p 1 ) λ 1 (1 -p 1 p 2 ) π c (0,0), y ∈ C \ D r 2 , (4.21)
where ϕ Y (y) is defined by Equation (4.19).

Proof. Since the solution to the Riemann-Hilbert problem (4.12) is unique, the function P (0, y) coincides with the function

F Y (y) + p 2 (λ 2 + λ 1 p 1 ) λ 1 (1 -p 1 p 2 ) π c (0, 0) in D r 2 .
log α Y (z) z -y dz = α Y (y) exp y π x 2 x 1 (µ 1 c 1 x 2 -λ 1 )Θ Y (x) xh 1 (x, y) dx ,
where the last equality is obtained using the same arguments as above (consider first real y and then extend the function by analytic continuation).

For the system under consideration, let us recall that the performance of the system is characterised by the blocking probabilities of the two classes of customers. The following theorem summarises the main results of the chapter for Condition (E). Proposition 4.3 covers the other cases. Chapter 4 4.5. Numerical results: Offloading small data centres Theorem 4.3. Under Condition (E), as N goes to infinity, the probability that at equilibrium a job of facility #i, i ∈ {1, 2} is rejected converges to β i with

β 1 = (1 -p 1 ) λ 1 -µ 1 c 1 + p 2 (λ 2 -µ 2 c 2 ) -p 2 (λ 2 + λ 1 p 1 )π c (0, 0) λ 1 (1 -p 1 p 2 ) + p 1 π c (0, 0) β 2 = (1 -p 2 ) λ 2 -µ 2 c 2 + p 1 (λ 1 -µ 1 c 1 ) -p 1 (λ 1 + λ 2 p 2 )π c (0, 0) λ 2 (1 -p 1 p 2 ) + p 2 π c (0, 0)
and the quantity π c (0, 0) is given by

π c (0, 0) =                λ 1 + λ 2 p 2 -µ 1 c 1 -µ 2 c 2 p 2 (λ 1 + λ 2 p 2 )ϕ Y (1) if λ 2 > µ 2 c 2 , λ 2 + λ 1 p 1 -µ 1 c 1 p 1 -µ 2 c 2 p 1 (λ 1 + λ 2 p 2 )ϕ Y (1) if λ 2 < µ 2 c 2 , (4.22)
where ϕ Y (y) is defined by Equation (4.19).

Proof. In the case λ 2 > µ 2 c 2 , the result easily follows using Equation (4.21) for y = 1 and Equation (4.8).

In the case λ 2 < µ 2 c 2 (and then λ 1 > µ 1 c 1 by Condition (E)), we have X 0 (1) = 1 and then, by Relation (4.16), one gets the expression for α Y (1),

α Y (1) = p 1 λ 1 + λ 2 p 2 -µ 1 c 1 -µ 2 c 2 p 2 λ 2 + λ 1 p 1 -µ 1 c 1 p 1 -µ 2 c 2 .
Equation (4.22) then easily follows. The formulas for the blocking probabilities are obtained using Relations (4.6) and (4.7) for β 1 and β 2 and the expressions (4.8) and (4.9) for P (0, 1) and P (1, 0).

To conclude this section, it is worth noting that the computation of the function ϕ Y (y) in the quantity π c (0, 0) involves elliptic integrals. In addition, a similar result holds for the function P (x, 0). This enables us to completely compute the generating function P (x, y).

Numerical results: Offloading small data centres

In this section, we illustrate the results obtained in the previous sections (in particular Theorem 4.3) in order to estimate the gain achieved by the offloading scheme. We assume that the service rate at both facilities is the same and taken equal to unity (µ 1 = µ 2 = 1). Assume in addition that the first data centre has a capacity much smaller than the second one, e.g., c 1 = 1 and c 2 = 10. We consider the case when all the requests blocked at the first data centre are forwarded to the second one (p 1 = 1) and none blocked at the second data centre is forwarded to the first one (p 2 = 0).

In Figures 4.4 and 4.5, when the arrival rate λ 1 at the first data centre increases, the loss rate β 1 goes from 0 if (A) or (B 1 ) holds to a positive value if (B 2 ) or (E) holds. For example in Figure 4.4, for p 1 = 1, we can see the transition from (B 2 ) to (E) when λ 1 = 3, and for p 1 = 0.7, the transition from (B 2 ) to (E) when λ 1 = 1 + 2/0.7 3.85. We can checked that β 1 is a continuous and not differentiable function of λ 1 at 1 + 2/0.7. If p 1 = 0.35 or p 1 = 0, (E) holds for the range of values [1, 5] considered here for λ 1 . In Figure 4.4, λ 2 = 12 thus (E) holds for λ 1 ∈ [1, 5], as λ 1 > µ 1 c 1 and λ 2 > µ 2 c 2 .

In conclusion, Figures 4.4 and 4.5 show that the offloading mechanism improves a lot the loss rate β 1 of the requests of class 1 and does not significantly deteriorate the corresponding performances at facility #2 in the case of systematic rerouting (p 1 = 1), even when this data centre is already significantly loaded as in Figure 4.5 (B). This means that offloading small date centres with a big back-up data centre is a good strategy to reduce blocking in fog computing. Figures 4.6 illustrate the impact of the choice of p 1 when facility #2 is almost overloaded, λ 2 = 9.9 so that λ 2 < c 2 µ 2 , and with a high load λ 2 = 11.1. As it can be seen, even when p 1 = 1, the performances of class 2 requests are not really impacted by the offloading scheme, whereas the loss rate of class 1 is significantly changed. This confirms the benefit of the offloading strategy.

Conclusion

We have proposed in this chapter an analytical model to study a simple offloading strategy for data centres in the framework of fog computing under heavy loads. The strategy considered consists of forwarding with a certain probability requests blocked at a small data centre to a big back-up data centre. The model considered could also be used to study the offload of requests blocked at the big data centre onto a small data centre but this case has not been considered in the numerical applications. The key finding is that the proposed strategy can significantly improves blocking at a small data centre

Chapter 5

Analysis of a trunk reservation policy in the framework of Fog Computing

Introduction

Fog computing [WRSvdM11, BMZA12, RBG12] is considered by many actors of the telecommunication ecosystem as a major breakthrough in the design of networks for both network operators and content providers. For the former, deploying storage and computing data centres at the edge of the network enables them to reduce the load within the network and on critical links such as peering links. In addition, network operators can take benefit of these data centres to dynamically instantiate virtualised network functions. Content providers can take benefit of distributed storage and computing data centres to optimise service platform placement and thus to improve the quality experienced by end users.

Fog computing relies on distributed data centres, which are much smaller than big centralised data centres generally used in cloud computing. Because of potential resource limitation, user requests may be blocked if resources are exhausted at a (small) data centre. This is a key difference with cloud computing where resources are often considered as infinite. In this chapter, we consider the case of a computing resource service where users request servers available at a data centre. If no server is available, then a user request may be blocked.

To reduce the blocking probability, it may be suitable that data centres collaborate. This is certainly a key issue in fog computing, which makes the design of networks and fog computing very different from that of cloud computing. Along this line of investigations, an offloading scheme has been investigated in [START_REF] Fricker | Analysis of an offloading scheme for data centers in the framework of fog computing[END_REF], where requests blocked at a data centre are forwarded to another one with a given probability. In this chapter, we investigate the case when a blocked request is systematically forwarded to another data centre but to protect those requests which are originally assigned to that data centre, a redirected request is accepted only if there is a sufficient large number of idle servers. In the framework of telephone networks, this policy is known as trunk reservation [START_REF] Ross | Multiservice loss models for broadband telecommunication networks[END_REF].

In the following, we consider the case of two data centres, where the trunk reservation policy is applied in one server only; the analysis of the case when the policy is applied in both data centres is a straightforward extension of the case considered but involves much more computations. We further simplify the system by reasonably assuming that both data centres have a large number of servers. From a theoretical point of view, this leads us to rescale the system and to consider limiting processes. The eventual goal of the present analysis is to estimate the gain achieved by the trunk reservation policy.

Considering the number of free servers in both data centres, we are led after rescaling to analyse a random walk in the quarter plane. This kind of process has been extensively studied in the technical literature (see for instance the book by Fayolle et al. [START_REF] Fayolle | Random Walks in the Quarter-Plane[END_REF]). For the random walk appearing in this chapter, even if the kernel is similar to that analysed in [START_REF] Fayolle | The two coupled server: the reduction to a Riemann-Hilbert problem[END_REF] (and in Fricker et al. [START_REF] Fricker | Analysis of an offloading scheme for data centers in the framework of fog computing[END_REF]), the key difference is that the reflecting conditions on the boundaries of the quarter plane are not constant. More precisely, the reflecting coefficients in the negative vertical direction along the y-axis take three different values depending on a given threshold (namely, the trunk reservation threshold).

This simple difference with usual random walks in the quarter plane makes the analysis much more challenging. Contrary to the usual case which consists of determining two unknown functions, we have in the present case to decompose one unknown function into two pieces (one polynomial and one infinite generating function) and thus to determine three unknown functions. We show that the coefficients of the unknown polynomial can be computed by solving a linear system. Once this polynomial is determined, the two other functions can be derived. This eventually allows us to compute the blocking probabilities at the two data centres and to estimate the efficiency of the trunk reservation policy in the framework of fog computing.

This chapter is organised as follows: In Section 5.2, we introduce the notation and we show convergence results for the rescaled system. We analyse in Section 5.3, the limiting random walk, in particular its kernel. The associated boundary value problems are formulated and solved in Section 5.4. Finally, some numerical results are discussed in Section 5.5.

Model description

Notation

We consider in this chapter two data centres in parallel. The first one is equipped with C 1 servers and serves customers arriving according to a Poisson process with rate Λ 1 and requesting exponentially distributed service times with mean 1/µ 1 (a customer if accepted occupies a single server of the data centre); the number of busy servers in this first data centre is denoted by N 1 (t) at time t. Similarly, the second data centre is equipped with C 2 servers and accommodate service requests arriving according to a Poisson process with rate Λ 2 and service demands exponentially distributed with mean 1/µ 2 ; the calculus gives the relation f m [ν] (t/ν) = f (k, ) + M [ν] (t/ν) (5.1)

+ t 0 µ 1 νc 1 -m [ν] 1 (s/ν) ν f m [ν] (s/ν) + e 1 -f m [ν] (s/ν) ds + t 0 µ 2 νc 2 -m [ν] 2 (s/ν) ν f m [ν] (s/ν) + e 2 -f m [ν] (s/ν) ds + t 0 λ 1 1 m [ν] 1 (s/ν)>0 f m [ν] (s/ν) -e 1 -f m [ν] (s/ν) ds + t 0 λ 2 1 m [ν] 2 (s/ν)>0 f m [ν] (s/ν) -e 2 -f m [ν] (s/ν) ds + t 0 λ 1 1 m [ν] 1 (s/ν)=0,m [ν] 2 (s/ν)>a f m [ν] (s/ν) -e 2 -f m [ν] (s/ν) ds where M [ν] (t) = M [ν] 1 (t), M [ν]
2 (t) is a martingale, e 1 = (1, 0) and e 2 = (0, 1). For i = 1, 2, since the process N

[ν] i (s/ν) is stochastically bounded by a Poisson process with rate µ i c i , hence, for the convergence of processes,

lim ν→+∞ νc i -m [ν] i (s/ν) ν = (c i ).
Using by Theorem 4.5 of Jacod and Shiryaev [JS03, p. 320], one gets that the sequence of processes m

[ν] (t/ν), t ≥ 0 is tight. If (z(t)) is the limit of some convergent subsequence m [ν k ] (t/ν k ) , then, if R = r(a, b), a, b ∈ N 2 is the Q-matrix of (n(t)), Relation (5.1) gives that f (z(t)) -f (k, ) - t 0 R • f (z(u)) du
is a martingale. Some of the technical details are skipped, see Hunt and Kurtz [START_REF] Hunt | Large loss networks[END_REF] for a similar context for example. This shows that (z(t)) is the Markov process with transition matrix R, hence (z(t)) has the same distribution as (n(t)). See Section IV-20 of Rogers and Williams [RW00, p. 30]. Since this is the only possible limit, the convergence in distribution is proved.

Using the results of [START_REF] Fayolle | Topics in the constructive theory of countable Markov chains[END_REF], we have the following stability condition.

Lemma 5.1. A stationary regime exists for the random walk (n(t)) if and only if

λ 1 > µ 1 c 1 and µ 1 c 1 + µ 2 c 2 < λ 1 + λ 2 . (5.2)
To conclude this section, let us note that the limiting random walk (n(t)) describes the number of customers in two M/M/1 queues in tandem. The arrival rate at the first queue is µ 1 c 1 and the service rate is λ 1 ; this queue is independent of the second one and is stable under Condition (5.2). The arrival rate at the second queue is µ 2 c 2 and the service rate is λ 2 plus λ 1 when the first queue is empty and there are more than a customers in the second queue. This last term introduces a coupling between the two queues. See Figure 5.2 for an illustration.

where the kernel K(x, y) is defined by

K(x, y) def. = µ 1 c 1 x 2 y + µ 2 c 2 xy 2 -(λ 1 + λ 2 + µ 1 c 1 + µ 2 c 2 )xy + λ 1 y + λ 2 x
(5.5)

and the polynomial P - 2 (y) by

P - 2 (y) def. = a n 2 =0
p(0, n 2 )y n 2 .

From the functional equation (5.4), let us note that the generating function of the number of customers in the first queue is given by P (x, 1) = λ 1 λ 1 -µ 1 c 1 x P 2 (1), from which we deduce that P 2 (1) = P(n 1 = 0) = 1 -µ 1 c 1 /λ 1 . This is obvious since the first queue is an M/M/1 queue with input rate µ 1 c 1 and service rate λ 1 , independent of the second queue. See Section 6.7 of Robert [Rob03, p. 164] for a complete proof.

In addition, we have P (1, y) = λ 2 P 1 (1) -λ 1 (P 2 (y) -P - 2 (y)) λ 2 -µ 2 c 2 y .

The normalising condition P (1, 1) = 1 yields λ 1 P(n 1 = 0, n 2 ≤ a) + λ 2 P(n 2 = 0) = λ 1 + λ 2 -µ 1 c 1 -µ 2 c 2 .

(5.6)

The quantity B 1 = P(N 1 = 0, N 2 ≤ a) is the blocking probability of customers originally trying to access the first data centre and B 2 = P(n 2 = 0) is the blocking probability of customers trying to reach the second data centre. The above relation is the global rate conservation equation of the system. The performance of the system is actually characterised by the blocking probabilities, given by the generating functions as B def.

= P - 2 (1), P 1 (1) .

In the following, we intend to compute the unknown generating functions P 1 (x), P 2 (y) and P - 2 (y).

Zero pairs of the kernel

The kernel K(x, y) has already been studied in Fayolle and Iasnogorodski [START_REF] Fayolle | The two coupled server: the reduction to a Riemann-Hilbert problem[END_REF] in the framework of coupled data centres. For fixed y, the kernel K(x, y) defined by Equation (5.5) has two roots X 0 (y) and X 1 (y). Using the usual definition of the square root such that √ a > 0 for a > 0, the solution which is null at the origin and denoted by X 0 (y), is defined and analytic in C \ ([y 1 , y 2 ] ∪ [y 3 , y 4 ]) where the real numbers y 1 , y 2 , y 3 and y 4 are such that 0 < y 1 < y 2 < 1 < y 3 < y 4 . The other solution X 1 (y) is meromorphic in C \ ([y 1 , y 2 ] ∪ [y 3 , y 4 ]) with a pole at 0. The function X 0 (y) is precisely defined by X 0 (y) = (µ 2 c 2 y 2 -(λ 1 + λ 2 + µ 1 c 1 + µ 2 c 2 )y + λ 2 ) 2 -4µ 1 c 1 λ 1 y 2 .

The other solution X 1 (y)

def.

= λ 1 /(µ 1 c 1 X 0 (y)). When y crosses the segment [y 1 , y 2 ], X 0 (y) and X 1 (y) describe the circle C r 1 with centre 0 and radius r 1 = λ 1 /(µ 1 c 1 ) > 1.

Similarly, for fixed x, the kernel K(x, y) has two roots Y 0 (x) and Y 1 (x). The root Y 0 (x), which is null at the origin, is analytic in C \ ([x 1 , x 2 ] ∪ [x 3 , x 4 ]) where the real numbers x 1 , x 2 , x 3 and x 4 are such that with 0 < x 1 < x 2 < 1 < x 3 < x 4 and is given by

Y 0 (x) def. = -(µ 1 c 1 x 2 -(λ 1 + λ 2 + µ 1 c 1 + µ 2 c 2 )x + λ 1 ) + σ 2 (x) 2µ 2 c 2 x
where σ 2 (x) is the analytic extension in of the function defined in the neighbourhood of 0 as ∆ 2 (x) with ∆ 2 (x)

def. = (µ 1 c 1 x 2 -(λ 1 + λ 2 + µ 1 c 1 + µ 2 c 2 )x + λ 1 ) 2 -4µ 2 c 2 λ 2 x 2 .
The other root Y 1 (x)

def.

= λ 2 /(µ 2 c 2 Y 0 (x)) and is meromorphic in C \ ([x 1 , x 2 ] ∪ [x 3 , x 4 ]) with a pole at the origin.

When x crosses the segment [x 1 , x 2 ], Y 0 (y) and Y 1 (y) describe the circle C r 2 with centre 0 and radius r 2 = λ 2 /(µ 2 c 2 ).

Boundary value problems

To solve the boundary value problems encountered in the following, let us recall that if we search for a function P (z) analytic in the disk D r def. for some functions g(z) and h(z) analytic in a neighbourhood of C r and g(z) does not cancel in this neighbourhood, then the function P (z)

= g(z) g(z) .

The function φ(z) is given by

φ(z) def. =          exp 1 2πi Cr log α(ξ) ξ κ dξ ξ -z z ∈ D r 1 z κ exp 1 2πi Cr log α(ξ) ξ κ dξ ξ -z z ∈ C \ D r ,
where κ is the index of the Riemann-Hilbert problem defined by κ def.

= 1 2π var z∈Cr arg α(z).

The existence and the uniqueness of the solution depends on the value of the index κ. When κ = 0, the solution exists and is unique with P(z) = P (0).

Function P 1 (x)

Let us first establish a relation between the functions P 1 (x) and P - 2 (y). For this purpose, let us define for x ∈ C r 1 α 1 (x) def.

=

x(Y 0 (x) -x) x(Y 0 (x) -x) = λ 1 (Y 0 (x) -x) x(µ 1 c 1 xY 0 (x) -λ 1 )

(5.7) and let us consider the following homogeneous Riemann-Hilbert problem: The function φ 1 (x) is sectionally analytic with respect to the circle C r 1 , and for some x ∈ C r 1 φ i 1 (x) = α 1 (x)φ e 1 (x), (5.8) where φ i 1 (x) (resp. φ e 1 (x)) is the interior (resp. exterior) limit at the circle C r 1 . Lemma 5.2. The function φ 1 (x) is given for some x ∈ D r 1 , by φ 1 (x) def.

= exp

x π y 2 y 1 λ 2 -µ 2 c 2 y 2 Θ 1 (y) yK(x, y) dy , (5.9)

where Θ 1 (y)

def.

= ArcTan -∆ 1 (y) µ 2 c 2 y 2 -(λ 1 + λ 2 + µ 1 c 1 + µ 2 c 2 )y + 2λ 1 + λ 2 . (5.10)

Proof. The index of the Riemann-Hilbert problem (5.8) is given by

κ 1 def. = 1 2π var x∈Cr 1 arg α 1 (x)
where α 1 (x) is defined by Equation (5.7). For x ∈ C r 1 , we have xY 0 (x) -λ 1 µ 1 c 1 < 0, since Y 0 (x) ∈ [y 1 , y 2 ] and (x) ≤ r 1 . Hence, κ 1 = 0. The solution to the Riemann-Hilbert problem is then given for x ∈ D r 1 by

φ 1 (x) = exp 1 2πi Cr 1 log α 1 (z) z -x dz .
For x ∈ C r 1 , simple manipulations show that for x = X 0 (y + 0i) for y ∈ [y 1 , y 2 ] α 1 (x) = e -2iΘ 1 (y) , where Θ 1 (y) is defined by Equation (5.10), since x(λ 2 -µ 2 c 2 y 2 )Θ 1 (y) yK(x, y) dy,

where we have used the fact that dX 0 (y + 0i) dy = X 0 (y + 0i) -µ 2 c 2 y + λ 2 y -i -∆ 1 (y) and (X 0 (y + 0i) -x)(X 0 (y -0i) -x) = K(x, y) µ 1 c 1 y .

Equation (5.9) then follows. x(λ 2 -µ 2 c 2 y 2 )Θ 1 (ξ) yK(x, y) dy .

Also, using the fact that for x = λ 1 µ 1 c 1 x , x K(x , y) = x K(x, y) , we deduce that for x = X 0 (y ± 0i) the Cauchy integral 1 π y 2 y 1

x(µ 2 c 2 ξ 2 -λ 2 )Θ 1 (ξ) ξK(x, ξ) dξ is real and equal to Φ 1 (y) = 1 π y 2 y 1 y(λ 2 -µ 2 c 2 ξ 2 )Θ 1 (ξ) ξ(ξ -y)(µ 2 c 2 yξ -λ 2 ) dξ.

It follows that for x = X 0 (y ± 0i)

φ i 1 (x) = exp (Φ 1 (y) -iΘ 1 (y)) .
The results above allow us to establish a relation between functions P 1 (x) and P - 2 (y).

Proposition 5.2. The functions P 1 (x) and P - 2 (y) are such that for x ∈ D r 1 P 1 (x) = φ 1 (x)P (0, 0)

+ xλ 1 φ 1 (x) λ 2 π y 2 y 1
(λ 2 -µ 2 c 2 y 2 )P - 2 (y) yK(x, y) sin(Θ 1 (y))e -Φ 1 (y) dy, (5.12)

where the functions φ 1 (x) and Φ 1 (y) are defined by Equations (5.9) and (5.11), respectively.

Proof. For x = X 0 (y), we have from Equation (5.4) λ 2 X 0 (y) y -X 0 (y) P 1 (x) = -X 0 (y)λ 1 P - 2 (y) y -X 0 (y) -λ 1 P 2 (y) 1 -y ,

The above equation implies that for some y ∈ [y 1 , y 2 ], and hence x ∈ C r 1 , iλ 2 x Y 0 (x) -x P 1 (x) = i x x -Y 0 (x) λ 1 P - 2 (Y 0 (x)) , (5.13) where we have used the fact that if x = X 0 (y + 0i) with y ∈ [y 1 , y 2 ] then y = Y 0 (x).

Using the results recalled in Section 5.4.1, the solution to the Riemann-Hilbert problem (5.13) then reads for x ∈ D r 1

P 1 (x) = φ 1 (x) λ 2 π Cr 1 (h 1 (z)) g 1 (z)φ i 1 (z) dz z -x
+ φ 1 (x)P (0, 0), where

h 1 (x) def. = x x -Y 0 (x) λ 1 P - 2 (Y 0 (x)), g 1 (x) def.
= x Y 0 (x) -x , and the function φ 1 (x) is solution to the homogeneous Riemann-Hilbert problem (5.8).

Using the fact that h 1 (z) = -g 1 (z)λ 1 P - 2 (Y 0 (z)), we deduce for z = X 0 (y + 0i) (h 1 (z)) g 1 (z)φ i 1 (z) = -sin(Θ 1 (y))e -Φ 1 (y) λ 1 P - 2 (y).

Hence,

1 λ 2 π Cr 1 (h 1 (z)) g 1 (z)φ i 1 (z) dz z -x = xλ 1 λ 2 π y 2 y 1
(λ 2 -µ 2 c 2 y 2 )P - 2 (y) yK(x, y) sin(Θ 1 (y))e -Φ 1 (y) dy and Equation (5.12) follows.

Function P 2 (y)

We now establish a relation between the function P 2 (y), the function P 1 (x) and the polynomial P - 2 (y). We use the same technique as for function P 1 (x).

Proposition 5.3. The function P 2 (y) is related to polynomial P - 2 (y) as P 2 (y) = yλ 2 2πλ 1

x 2

x 1 P 1 (x)(λ 1 -µ 1 c 1 x 2 ) -∆ 2 (x) x(λ 1 + λ 2 -(µ 1 c 1 + µ 2 c 2 )x)K(x, y) dx + y 2πi Cr 2 (z -1)(λ 2 -µ 2 c 2 z 2 )X 0 (z) 2 P - 2 (z) z 2 (z -X 0 (z))K(X 0 (z), y) dz + P (0, 0). = λ 2 (y -1)X 0 (y) y -X 0 (x) P 1 (X 0 (y)) + λ 1 (y -1)X 0 (y) y -X 0 (y) P - 2 (y).

Using the results recalled in Section 5.4.1, the function P 2 (y) is given by P 2 (y) = 1 λ 1 π Cr 2 (h 2 (z)) dz z -y + P (0, 0).

(Note that we have in the present case to deal with a Dirichlet problem.) Simple computations show that for y = Y 0 (x + 0i) λ 2 (y -1)X 0 (y) y -X 0 (x) P 1 (X 0 (y)) = -

λ 2 P 1 (x) 2(λ 1 + λ 2 -(µ 1 c 1 + µ 2 c 2 )x)
-∆ 2 (x).

In addition, using the fact that the polynomial P - 2 (y) is with real coefficients, we have λ 1 y -1 y -X 0 (y) X 0 (y)P - 2 (y) = λ 1 2πi y -1 y -X 0 (y) X 0 (y)P - 2 (y) -ȳ -1 ȳ -X 0 (y) X 0 (y)P - 2 (ȳ) .

Since dY 0 (x + 0i) dx = Y 0 (x + 0i) λ 1 x -µ 1 c 1 x -i -∆ 2 (x) ,

we have

Cr 2 λ 2 (y -1)X 0 (y) y -X 0 (x) P 1 (X 0 (y)) dz z -y =

x 2 x 1 λ 2 yP 1 (x)(λ 1 -µ 1 c 1 x 2 ) -∆ 2 (x) 2x(λ 1 + λ 2 -(µ 1 c 1 + µ 2 c 2 )x)K(x, y) dx.
Moreover,

1 π Cr 2 λ 1 z -1 z -X 0 (z) X 0 (z)P - 2 (z) dz z -y = yλ 1 2πi Cr 2
(z -1)(λ 2 -µ 2 c 2 z 2 )X 0 (z)P - 2 (z) z(z -X 0 (z))(z -y)(λ 2 -µ 2 c 2 yz) dz = yλ 1 2πi Cr 2 (z -1)(λ 2 -µ 2 c 2 z 2 )X 0 (z) 2 P - 2 (z) z 2 (z -X 0 (z))K(X 0 (z), y) dz.

Assembling the two above relations, Equation (5.14) follows.

Determination of the polynomial P - 2 (y)

We use the two previous results to establish a linear system satisfied by the coefficients of the polynomial P - 2 (y). Let us first introduce some notation Set

x(θ) def. = λ 1 + λ 2 + µ 1 c 1 + µ 2 c 2 -2 √ µ 2 c 2 λ 2 cos θ -δ 1 (θ) 2µ 1 c 1 with δ 1 (θ) def. = (λ 1 + λ 2 + µ 2 c 2 + µ 1 c 1 -2 µ 2 c 2 λ 2 cos θ) 2 -4µ 1 c 1 λ 1 , so that cos θ = - µ 1 c 1 x(θ) 2 -(λ 1 + λ 2 + µ 1 c 1 + µ 2 c 2 )x(θ) + λ 1 2 √ µ 2 c 2 λ 2 x(θ) .
Moreover, define the coefficients for 0 ≤ n, k ≤ a α where β n is given by Equation (5.17

(x) = - µ 1 c 1 x 2 -(λ 1 + λ 2 + µ 1 c 1 + µ 2 c 2 )x + λ 1 2x √ µ 2 c 2 λ 2 , sin θ 2 (x) = -∆ 2 (x) 2x √ µ 2 c 2 λ 2
and then Y 0 (x + 0i) = r 2 e -iθ 2 (x) , we deduce from Equation (5.14) that r n 2 p(0, n + 1) = + 1 2πiλ 2 Cr 2 (z -1)(λ 2 -µ 2 c 2 z 2 )X 0 (z)P - 2 (z) z 2 (z -X 0 (z))

U n (cos θ 2 (X 0 (z))) dz

+ 1 2πλ 1 x 2 x 1 P 1 (x)(λ 1 -µ 1 c 1 x 2 ) -∆ 2 (x) x 2 (λ 1 + λ 2 -(µ 1 c 1 + µ 2 c 2 )x)
U n (cos θ 2 (x)) dx.

We have 1 2πiλ 2 Cr 2 (z -1)(λ 2 -µ 2 c 2 z 2 )X 0 (z)P - 2 (z) z 2 (z -X 0 (z))

U n (cos θ 2 (X 0 (z))) dz = a k=0 p(0, k)

1 2πiλ 2 Cr 2 (z -1)(λ 2 -µ 2 c 2 z 2 )X 0 (z)z k z 2 (z -X 0 (z))
U n (cos θ 2 (X 0 (z))) dz.

For the integrals appearing in the above equation, we note that 1 2πiλ 2 Cr 2 (z -1)(λ 2 -µ 2 c 2 z 2 )X 0 (z)z k z 2 (z -X 0 (z)) U n (cos θ 2 (X 0 (z))) dz = -1 πr 2 Cr 2 (z(θ) -1)X 0 (z(θ)) z(θ) -X 0 (z(θ)) z(θ) k-1 sin((n + 1)θ)dθ, where z(θ) def.

= r 2 e iθ and where we have used the fact that U n (cos θ) = sin((n + 1)θ) sin θ .

Simple computations show that the integral in the right hand side of the above equation is equal to α

(2) n,k defined by Equation (5.16). Using the fact that 2 µ 2 c 2 λ 2 sin θ 2 (x) dθ 2 (x) dx = µ 1 c 1 x 2 -λ 1 x 2

we easily obtain that

1 2πλ 1 x 2 x 1 P 1 (x)(λ 1 -µ 1 c 1 x 2 ) -∆ 2 (x) x 2 (λ 1 + λ 2 -(µ 1 c 1 + µ 2 c 2 )x)
U n (cos θ 2 (x)) dx = 2µ 2 c 2 λ 2 πλ 1 π 0 P 1 (x(θ))x(θ) λ 1 + λ 2 -(µ 1 c 1 + µ 2 c 2 )x(θ) sin((n + 1)θ) sin θdθ

iii. If a = 0, there is no protection for the requests which originally arrive at data centre 2, i.e., every request rejected at data centre 1 is systematically forwarded to data centre 2 and accepted if there are idle cores in this data centre. This scenario is a particular case of the offloading scheme studied in Fricker et al. [START_REF] Fricker | Analysis of an offloading scheme for data centers in the framework of fog computing[END_REF], where two parallel data centres forward demands they cannot hold to each other with a given probability. Namely, in the notation used in that paper, we have p 1 = 1 and p 2 = 0, where p i is probability that data centre i forwards a request to data centre 3 -i, for 1 ≤ i ≤ 2. Using Theorem 3 from this reference, we are able to calculate the blocking probabilities, denoted by

B 0 = (B 0 i , 1 ≤ i ≤ 2), such that          B 0 1 def. = λ 1 -µ 1 c 1 -(µ 2 c 2 -λ 2 ) + λ 1 φ 2 (1) , B 0 2 def. = λ 1 (1 -B 0 1 ) -µ 1 c 1 + λ 2 -µ 2 c 2 λ 2 ,
(5.20) where φ 2 (y)

def.

= exp y π

x 2

x 1 λ 1 -µ 1 c 1 x 2 xK(x, y) Θ 2 (x)dx and Θ 2 (x)

def.

= ArcTan -∆ 2 (x) (x + 1)(λ 1 -xµ 1 c 1 ) + x(λ 2 -µ 2 c 2 ) .

To evaluate the impact of the choice of the parameter a on the loss probabilities at both data centres, we compare the blocking rates in this system with the intuitive boundaries B 0 and B ∞ defined previously in Equations (5.19) and (5.20), respectively. For this purpose, we consider the case where requests are accommodated by a edge data centre possibly offloaded to the other data centre; the trunk reservation policy is implemented in the second data centre.

We first consider the case when both data centres have the same capacity, say, c = (1.0, 1.0) and the edge data centre is saturated while the other is underloaded but the global system is overloaded. To illustrate this case, we have chosen the parameters λ = (2.0, 0.9) and µ = (1.0, 1.0). Blocking rates are depicted in Figure 5.3a. We see that small values of a (say, a = 1, 2, 3) can help reduce the blocking rate of its original requests while moderately increasing that of the offloaded ones. Choosing large values of a does not improve blocking rates. The same conclusion holds when both data centres are overloaded as shown by Figure 5.3b.

To further investigate the performance of the trunk reservation policy, we have considered asymmetric data centres, the data centre 2 is larger than the data centre 1. We have specifically chosen c = (1., 5.) and still with the same mean service rates µ = (1., 1.). In the first case, λ = (1.5, 4.8) so that the second data centre is underloaded. Taking moderate values of a (say, a = 3, . . . , 10) can decrease the blocking rate at data centre 1 without

Conclusion

We have considered in this paper a trunk reservation policy implemented in a data centre accommodating external requests but also some requests from another data centre when saturated. This model reasonably illustrates what happens in a distributed data centre system. We consider in this paper a system under saturation to stress the performance of the trunk reservation policy.

The offload mechanism introduces a coupling between both data centres. By rescaling the system under an assumption of congestion, we are led to study a random walk in the quarter plane, which has the property of having non constant reflecting conditions on one axis. We have developed an original method of determining the unknown functions appearing when computing the generating function of the joint numbers of active jobs in both data centres and subsequently the blocking rates of requests. Numerical results show that

  [START_REF] Burman | Insensitivity of blocking probabilities in a circuit-switching network[END_REF], Dziong and Roberts[START_REF] Dziong | Congestion probabilities in a circuit-switched integrated services network[END_REF] and others). As the calculations involving the analysis of such systems are complicated (especially for obtaining the normalisation constant, see Louth et al. [LMK94]), much of the subsequent work has focused on expanding the mathematical toolbox (see or Choudhury et al. [CLW95] or Theberge et al. [TSM98]). It was particularly the publication of Kelly's papers [Kel86, Kel91] which through the introduction of a more simple and efficient framework for the study of the system's Chapter 1 1.3. Mathematical Framework equilibrium properties allowed the teletraffic community to gain a deeper understanding of the behaviour of loss systems. Recently, the framework of loss systems received renewed attention due to the rise of the Cloud Computing technology. The search for even more efficient calculation methods is subject of ongoing research (see Bonald and Virtamo [BV05], Jung et al. [JLS + 08] and Tan et al. [TLX12a, TLX12b] for instance).

FigureFigure 1 . 5 -

 15 Figure 1.5 -Exact Erlang Formula and Large Scale Approximation

  one has already L negative solutions of the equation F (x) = 1. All eigenvalues of B are thus negative, consequently, exp(tB) converges to 0. (See Corollary 2 of Chapter 25 of Arnol'd [Arn92, p. 223] for example.) Equation (2.16) can be solved as z(t) = e tB z(0) + B -1 e b -B -1 e b .

  a generating function, in particular ϕ(1) = 1. Plugging the previous expressions for ϕ + and ϕ -in ϕ + (1) + ϕ -(1) = 1, one gets the relation 1 = -κ q∈Z P 2 ∩D

Figure 2 . 1 -

 21 Figure 2.1 -The histogram of Y * with the parameters J = 5, A = (1, 2, 4, 8, 16), λ = (0.25, 0.2, 0.15, 0.1, 0.05), µ = (1, 1, 1, 1, 1) and c 0 = 0.97.

  Figure 2.2 -Comparison between policies

Figure 2

 2 Figure 2.3 -Maximal threshold for a loss probability equal to ε.

  then a fluid limit associated with (X(t)) is a stochastic process and one of the limits ofXN (t) = X (N t) Nwhen N goes to infinity. Note that XN (0) is an element in the unit sphere of R d . Particularly, fluid limits are a convenient tool for the study of Markov processes behaving like random walks (at least locally). If the fluid limits of a Markov process converge to zero in a deterministic finite time then the process is ergodic. See Corollary 9.8 of Robert[START_REF] Ph | Stochastic Networks and Queues[END_REF] p. 259].

Figure 3 . 2 -

 32 Figure 3.2 -Drifts on the quarter planes of Z 2

Figure 3 . 3 -

 33 Figure 3.3 -Resulting drifts of the fluids limits associated with (U x (t)).

FigureAlgorithm 1

 1 Figure 3.4 -Transitions of threshold forwarding policy

Figure 4

 4 Figure 4.2 -Load Balancing between Two Data Centres

Theorem 4. 1 .

 1 If one of the following conditions

=

  λ 2 /(µ 2 c 2 Y 0 (x)) and is meromorphic in C \ ([x 1 , x 2 ] ∪ [x 3 , x 4 ]) with a pole at the origin. When x crosses the segment [x 1 , x 2 ], Y 0 (y) and Y 1 (y) describe the circle C r 2 with centre 0 and radius r 2 def.

  Since the index of the Riemann-Hilbert (4.14) is null, the solution reads

Figure 4 . 4 -

 44 Figure 4.4 -Loss probabilities as a function of λ 1 with λ 2 = 8, c 1 = 1, c 2 = 10, µ 1 = 1, µ 2 = 1, p 2 = 0. The crosses represent simulation points while solid curves are plotted from analytical results.

Figure 4 . 5 -Figure 4 . 6 -

 4546 Figure 4.5 -Loss probabilities as a function of λ 1 with λ 2 = 12, c 1 = 1, c 2 = 10, µ 1 = 1, µ 2 = 1, p 2 = 0. The crosses represent simulation points while solid curves are plotted from analytical results.

  2 c 2 y 2 -(λ 1 + λ 2 + µ 1 c 1 + µ 2 c 2 )y + λ 2 ) + σ 1 (y) 2µ 1 c 1 y ,where σ 1 (y) is the analytic extension in C \ ([y 1 , y 2 ] ∪ [y 3 , y 4 ]) of the function defined in the neighbourhood of 0 as ∆ 1 (y) with ∆ 1 (y)def.

=

  {z ∈ C : |z| < r} for some r > 0, such that for z ∈ C r def.= {z ∈ C : |z| = r}, P (z) satisfies (ig(z)P (z)) = (ih(z))

P

  (1/z) z ∈ C \ D r is solution to the following Riemann-Hilbert problem: The function P (z) is sectionally analytic with respect to the circle C r and verifies for z ∈ C r g(z) P i (z) -g(z) P e (z) = 2i (h(z)), where P i (z) (resp. P e (z)) is the interior (resp. exterior) limit of the function P (z) at the circle C r , and D r def.= D r ∪ C r . From[START_REF] Dautray | Mathematical Analysis and Numerical Methods for Science and Technology: Volume 4 Integral Equations and Numerical Methods[END_REF], the solution to this Riemann-Hilbert problem when it exists is given for z ∈ C \ C r byP (z) g(ξ)φ i (ξ) dξ ξ -z + φ(z)P(z),where P(z) is a polynomial and φ i (z) (resp. φ e (z)) is the interior (resp. exterior) limit at the circle C r of the solution φ(z) to the following homogeneous Riemann-Hilbert problem: The function φ(z) is sectionally analytic with respect to the circle C r and, for z ∈ C r , φ i (z)def.= α(z)φ e (z), where α(z)def.

  x = -(µ 2 c 2 y 2 -(λ 1 + λ 2 + µ 1 c 1 + µ 2 c 2 )y + λ 2 ) -i ∆ 1 (y) 2µ 1 c 1 y .It follows that for x ∈ D r 1

Corollary 5 . 1 .

 51 The interior limit of the function φ 1 (x) at the circle C r 1 is given for x = X 0 (y + 0i) with y ∈ [y 1 , y 2 ] byφ i 1 (x) = exp (-iΘ 1 (y) + Φ 1 (y)) , 2 -µ 2 c 2 ξ 2 )Θ 1 (ξ) ξ(µ 2 c 2 yξ -λ 2 ) dξ ξ -y , (5.11) and the symbol denotes the Cauchy integral[START_REF] Dautray | Mathematical Analysis and Numerical Methods for Science and Technology: Volume 4 Integral Equations and Numerical Methods[END_REF].Using Plemelj's formula, we have for x = X 0 (y + 0i) with y ∈ [y 1 , y 2 ]

  value problemsProof. From Equation (5.4), we have for y = Y 0 (x)λ 2 1 -Y 0 (x) Y 0 (x) -x xP 1 (x) + λ 1 P 2 (Y 0 (x)) + λ 2 1 -Y 0 (x) Y 0 (x) -x xP - 2 (Y 0 (x)) = 0. When x ∈ [x 1 , x 2 ], Y 0 (x) ∈ Cr 2 and it then follows that the function P 2 (y) satisfies for y ∈ C r 2 (iλ 1 P 2 (y)) = (ih 2 (y)) , where h 2 (y) def.

2 c 2 λ 2 λ 1 π π 0 φ 1

 01 )φ 1 (x(θ)) λ 1 + λ 2 -(µ 1 c 1 + µ 2 c 2 )x(θ) J k (θ) sin((n + 1)θ) sin θdθ, (x(θ))x(θ) λ 1 + λ 2 -(µ 1 c 1 + µ 2 c 2 )x(θ) sin((n + 1)θ) sin θdθ, -µ 2 c 2 y 2 )y k-1 µ 2 c 2 y 2 -2y √ µ 2 c 2 λ 2 cos θ + λ 2 sin(Θ 1 (y))e -Φ 1 (y) dy, j k (θ) def. = (r 2 2 + x(θ)) sin(kθ) -x(θ)r 2 sin((k + 1)θ) -r 2 sin((k -1)θ) (1 -x(θ))(λ 1 + λ 2 -(µ 1 c 1 + µ 2 c 2 )x(θ)) .Theorem 5.1. The probabilities p(0, n) for n = 1, . . . , a can be expressed as a function of p(0, 0) by solving the linear system: for 0 ≤ n ≤ a -1 r n 2 p(0, n + 1) = β n p(0, 0) + a k=0 α n,k p(0, k)(5.18)

  ) and α n,k = α being defined by Equation (5.15) and (5.16), respectively. The probability p(0, 0) is determined by plugging the solution the linear system into equation(5.14), and such that it satisfies the normalisation condition (5.6).Proof. Using the fact that1 K(x, y) = 1 λ 2 x ∞ n=0 U n (cos θ 2 (x)) y r 2 n , where U n (x) is the n-th Chebyshev polynomials of the second kind [AS72], θ 2 (x) ∈ [0, π] is such that for x ∈ [x 1 , x 2 ] cos θ 2

  λ 1 = 2.0, λ 2 = 0.9.

  λ 1 = 2.0, λ 2 = 1.1.

Figure 5 . 3 -

 53 Figure 5.3 -Blocking probabilities in both data centres with same size as a function of a, with c = (1.0, 1.0) and µ = (1.0, 1.0)

Figure 5 . 4 -

 54 Figure 5.4 -Blocking probabilities in both data centres with different sizes as a function of a, with c = (1.0, 5.0) and µ = (1.0, 1.0)

  Poisson arrivals and general service times, (M/G/1 queues in Kendall's notation) which led to an explosion of the application possibilities of queueing systems.

	Chapter 1	1.2. Stochastic Modelling of Services
	systems with
		and
	Khinchine (1894-1959) derive further fundamental results for similar queueing

  al. [SMW07], Vadlakonda et al. [VCH + 10], Sieber et al. [SHZ + 13] and Añorga et al. [AAS

  ) ∈ H 0 for all t ≥ 0 and (y(t)) is converging exponentially fast to * defined in Proposition 2.3.

	Proof. It is easily checked that
	d dt	A, y(t) = 0,

so that if y(0) ∈ H 0 , then the function t → A, y(t) is constant and equal to c 0 , hence y(t) ∈ H 0 for all t ≥ 0.

For 2 ≤ j ≤ J,

  • •+λ J and the same notations as before. By definition, function Φ is holomorphic in D and D c and, from Relation (2.19), is continuous on γ(1). The analytic continuation theorem, Theorem 16.8 of Rudin [Rud87] for example, gives that Φ is holomorphic on C

  3.1. Introduction ation is Ghodsi et al. [GZH+ 11, GSZS12]. The authors propose the concept of Dominant Resource Fairness (DRF) allocations to share resources in an equitable (fair) manner between a fixed number of users. The authors develop the DRF by abstracting from the weighted Max-Min fairness to a multiresource context. In Ghodsi et al. [GZH+ 11], the authors show the DRF has desirable properties for sharing mechanisms such as Sharing Incentive, Strategy-proofness, Envy-freeness, Pareto efficiency, Single Resource Fairness and Bottleneck Fairness in the static environment. In Ghodsi et al.[START_REF] Ghodsi | Multi-resource fair queueing for packet processing[END_REF] the authors define the Dominant Resource Fair Queueing (DRFQ), whose goal is to promote DRF allocations in time-evolving processing systems.However, these fair allocations may lack applicability in many Cloud services where jobs are neither divisible nor preemptive nor postponable, contrary

  (y) at the circle C r 2 , and the function α Y (y) is defined on C r 2 by The solutions to Riemann-Hilbert problems of form (4.14) are given in [DL90]. We first have to determine the index of the problem defined as The function α Y (y) defined for y ∈ C r 2 by Equation (4.15) can be extended as a meromorphic function in C \ ([y 1 , y 2 ] ∪ [y 3 , y 4 ]) by setting α

	κ Y	def. =	1 2π	var y∈Cr 2 arg α Y (y).
	Theorem 7.2 of Fayolle and Iasnogorodski [FI79] it is shown that the stability
	condition (E) is equivalent to κ Y = 0.
	To obtain explicit expressions, let us first study the function α Y (y), which
	can be expressed as follows.
	Lemma 4.1.
					y),	(4.14)
	where F i Y (y) (resp. F e Y (y)) is the interior (resp. exterior) limit of the function
	F Y α Y (y)	def. =	a Y (y) a Y (y)	(4.15)
	with
		a Y (y)	def.

=

h 3 (X 0 (y), y) h 2 (X 0 (y), y) .

  It is easily checked that the function on the right hand side of the above equation can analytically be continued in the disk D r 2 and the result follows. Hence for y ∈ D r 2 , the first part of Equation (4.18) follows. When y is not in the closed disk D r 2 , similar arguments can be used to derive the second part of Equation (4.18).In view of the above lemma, we can state the main result of this section.

	Chapter 4	4.4. Boundary value problems
	Theorem 4.2. The function P (0, y) can be defined as a meromorphic function
	in C \ [y 3 , y 4 ] by setting
		y)	dx

  We can extend this function as follows. Noting that the function log α Y (y) is analytic in a neighbourhood of the circle C r 2 , the function

		y → exp	1 2iπ Cr 2	log α Y (z) z -y	dz
	α Y (y) exp	1 2iπ Cr 2

defined for y ∈ D r 2 can be continued as a meromorphic function in C \ [x 3 , x 4 ] considering the function defined for y ∈ C \ D r 2 , by

Acknowledgments

Chapter 4 4.2. Model description The following result summarises the stability properties of this random walk. Critical cases are omitted.

Proposition 4.1. For l = (l 1 , l 2 ) ∈ R 2 + , (i) If one of the conditions a) λ 2 < µ 2 l 2 and λ 1 p 1 + λ 2 > µ 1 l 1 p 1 + µ 2 l 2 b) λ 1 < µ 1 l 1 and λ 1 + λ 2 p 2 > µ 1 l 1 + µ 2 l 2 p 2 c) λ 1 > µ 1 l 1 and λ 2 > µ 2 l 2 holds then the Markov process (m l (t)) is ergodic on N 2 . In this case the unique invariant distribution on N 2 is denoted by π l .

(ii) If λ 1 < µ 1 l 1 and λ 2 < µ 2 l 2 , the unique invariant distribution of (m l (t))

on the extended state space (N ∪ {+∞}) 2 is the Dirac measure δ (∞,∞) .

(iii) If λ 1 > µ 1 l 1 , λ 2 < µ 2 l 2 and λ 1 p 1 + λ 2 < p 1 µ 1 l 1 + µ 2 l 2 , the unique invariant distribution of (m l (t)) on (N ∪ {+∞}) 2 is G δ 1 ⊗ δ ∞ , where G δ 1 is the geometric distribution with parameter δ 1 = µ 1 l 1 /λ 1 .

(iv

Proof. Due to Fayolle and Iasnogorodski [START_REF] Fayolle | The two coupled server: the reduction to a Riemann-Hilbert problem[END_REF] see also Proposition 9.15 of Robert [Rob03, p. 276], (m l (t)) is ergodic if and only if one of the conditions of (i) holds. As long as it does not hit 0, the first (resp. second) coordinate of (m l (t)) behaves as an M/M/1 queue with arrival rate µ 1 l 1 (resp. µ 2 l 2 ) and service rate λ 1 (resp. λ 2 ). Under the conditions of (ii), each of these M/M/1 queues is transient, in particular starting from 1, it has a positive probability of not returning to 0. This implies that after some random time, the process (m l (t)) stays in the interior of the quadrant N 2 and therefore behaves as a couple of independent transient M/M/1 queues. Consequently, both coordinates of (m l (t)) are converging in distribution to +∞. Similarly, for Chapter 4 4.2. Model description holds, where (l(t)) = ((l 1 (t), l 2 (t))) satisfying the following integral equations

Let us assume without loss of generality that, under condition (E), for example the first condition of (E) is satisfied. It will be assumed throughout the chapter. It is not difficult to construct a coupling so

is the Poisson process of arrivals at facility #i, using the same coupling as before one gets that the number U N 2 (t), arrivals at facility #2 up to time t, satisfies, for 0

where (B 1 (u), u ≥ 0) is a family of independent Bernoulli random variables with parameter p 1 . The lower bound includes the direct arrivals N λ 2 N [0, t] to facility #2 and the rejected jobs from #1. One gets that

queue with the arrival process (U N (t)). The ergodic theorem gives that, almost surely lim

by condition (E). Using this relation, one can show that, for the convergence in distribution, the relation lim

holds. In particular (l 2 (t)) is constant and equal to c 2 . Therefore, almost surely, (l(t)) = (c) holds, hence π l(t) = π c . Relation (4.2) shows that the theorem is proven.

The following proposition states that the performances of the load balancing mechanism can be expressed with the invariant distribution π c . Chapter 5 5.2. Model description number of requests in progress is denoted by N 2 (t) at time t. Note that the system being with finite capacity is always stable.

To reduce the blocking probability at the first service data centre without exhausting the resources of the second one, we assume that when data centre 1 is full and there are at least a servers available at data centre 2, then requests arriving at data centre 1 are served at data centre 2. Figure 5.1 shows how both data centres deal with this cooperative scheme. Dashed lines represent the flows of blocked requests.

In the following, we consider the process (m(t))

def.

= ((C

describing the number of idle servers in both data centres. In the next section, we investigate the case when the arrival rates at data centres are scaled up by a factor ν > 0.

Rescaled system

Let us assume that the arrival rates Λ 1 and Λ 2 are scaled up by a factor ν, i.e., Λ 1 = νλ 1 and Λ 2 = νλ 2 for some factor ν and real λ 1 > 0 and λ 2 > 0. We further assume that the capacities C 1 and C 2 scale with ν, namely C 1 = νc 1 and C 2 = νc 2 for some positive constants c 1 and c 2 . To indicate the dependence of the numbers of occupied and idle servers upon ν, we write N

[ν] i and m

[ν] i instead of N i and m i to denote respectively the number of occupied and idle servers in data centres i for i = 1, 2.

With the above hypotheses, we are led to consider m [ν] (t) as a random walk. For this purpose, let us introduce the random walk (n(t)) = ((n 1 (t), n 2 (t)), t ≥ 0) in the positive quadrant with transition rates for n

and the reflecting conditions for n 1 > 0 and

for n 1 = 0 and n 2 > 0 r((0, n 2 ), (k,

and for n = 0

where a is the threshold introduced in the previous section.

Proof. If f is a function on N 2 with finite support then classical stochastic Chapter 5

5.3. Analysis of the limiting random walk

Analysis of the limiting random walk

We assume in this section that the random walk is ergodic. In other words, Condition (5.2) is satisfied.

Functional equation

Let p(n 1 , n 2 ) denote the stationary probability of being in state (n 1 , n 2 ) ∈ N 2 in the stationary regime. It is easily checked that the balance equation reads for n 1 , n 2 ≥ 0 = {z ∈ C : |z| < 1} the generating functions

By definition, the function P (x, y) is analytic in D×D and the functions P 1 (x) and P 2 (y) are analytic in D.

Multiplying Equation (5.3) by the term x n 1 y n 2 and summing for n 1 and n 2 ranging from zero to infinity, we obtain the functional equation

. Numerical experiments

Simple manipulations show that the above integral can be expressed as

n,k and β n defined by Equations (5.15) and (5.17), respectively. We finally obtain the linear system (5.18).

In the next section, we show how the above theorem can be used to carry out numerical experiments.

Numerical experiments

We report in this section some numerical results in order to illustrate the computations performed in the previous sections. We analyse the implementation of a systematic offloading scheme in the framework of fog computing. Data centre 1 forwards all the requests which cannot be hosted locally to data centre 2 which, in order to protect its own requests, only accepts offloaded requests if there are a sufficient large number of free cores. We assess the potential gains on such policy using the blocking probabilities of customers at each data centre. In the following, B i denotes the blocking rate of customers assigned to data centre i, for 1 ≤ i ≤ 2.

In all cases described below, it is considered that data centre 1 is saturated by its demands, i.e., λ 1 > µ 1 c 1 , and data centre 2 is saturated by the combined flows of requests after this policy is implemented, i.e., λ 2 + λ 1 -µ 1 c 1 > µ 2 c 2 (Condition (5.2)). The analysis is decomposed into the following cases:

i. If a ∈ N * , the loss probabilities are calculated using Theorem 5.1. For this purpose, we first numerically compute the coefficients α

(1) n,k and α

(2) n,k for 0 ≤ n, k ≤ a and β n for 0 ≤ n ≤ a by taking p(0, 0) = 1 via Equations (5.15), (5.16), and (5.17), respectively. We thus obtain the unnormalised probabilities p(0, k) and then polynomial P - 2 (y) up to the normalising coefficient p(0, 0) = P (0, 0). This determines the function P 1 (x) up to the proportional coefficient p(0, 0) by using Equation (5.12) and subsequently the function P 2 (x) up to the coefficient p(0, 0). This coefficient is eventually computed by using the normalising condition (5.6). This allows us to numerically compute P - 2 (1) and P 1 (1), equal to B 1 and B 2 , respectively. ii. When a is very large the requests arriving at the second data centre are not influenced by those offloaded from first data centre. In this case, the blocking probabilities, denoted by

where we have used the global rate conservation law given by Equation (5.6).

Abstract

This PhD thesis investigates four problems in the context of Large Distributed Systems. This work is motivated by the questions arising with the expansion of Cloud Computing and related technologies (Fog Computing, VNF, etc.). The present work investigates the efficiency of different resource allocation algorithms in this framework. The methods used involve a mathematical analysis of several stochastic models associated to these networks.

Chapter 1 provides an introduction to the subject in general, as well as a presentation of the main mathematical tools used throughout the subsequent chapters.

Chapter 2 presents a congestion control mechanism in Video on Demand services delivering files encoded in various resolutions. We propose a policy under which the server deliv-ers the video only at minimal bit rate when the occupancy rate of the server is above a certain threshold. The performance of the system under this policy is then evaluated based on both the rejection and degradation rates.

Chapters 3, 4 and 5 explore problems related to cooperation schemes between data centres on the edge of the network. In the first setting, we analyse an offloading policy in the context of multi-resource cloud services. In second case, requests that arrive at a congested data centre are forwarded to a neighbouring data centre with some given probability. In the third case, requests blocked at one data centre are forwarded systematically to another where a trunk reservation policy is introduced such that a redirected request is accepted only if there are a certain minimum number of free servers at this data centre.