{'fraction_non_alphanumeric': 0.05971941699874447, 'fraction_numerical': 0.012446094219116764, 'mean_word_length': 3.7229777634547214, 'pattern_counts': {'":': 0, '<': 48, '<?xml version=': 0, '>': 30, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 18, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Asymptotic Optimality of Speed-Aware JSQ for Heterogeneous Systems

The Join-the-Shortest-Queue (JSQ) load-balancing scheme is known to minimise the average delay of jobs in homogeneous systems consisting of identical servers. However, it performs poorly in heterogeneous systems where servers have different processing rates. Finding a delay optimal scheme remains an open problem for heterogeneous systems. In this paper, we consider a speed-aware version of the JSQ scheme for heterogeneous systems and show that it achieves delay optimality in the fluid limit. One of the key issues in establishing this optimality result for heterogeneous systems is to show that the sequence of steady-state distributions indexed by the system size is tight in an appropriately defined space. The usual technique for showing tightness by coupling with a suitably defined dominant system does not work for heterogeneous systems. To prove tightness, we devise a new technique that uses the drift of exponential Lyapunov functions. Using the non-negativity of the drift, we show that the stationary queue length distribution has an exponentially decaying tail - a fact we use to prove tightness. Another technical difficulty arises due to the complexity of the underlying state-space and the separation of two time-scales in the fluid limit. Due to these factors, the fluid-limit turns out to be a function of the invariant distribution of a multi-dimensional Markov chain which is hard to characterise. By using some properties of this invariant distribution and using the monotonicity of the system, we show that the fluid limit is has a unique and globally attractive fixed point.


Introduction
The average response time of user requests is a key performance measure in modern largescale service systems such as web server farms and cloud data centers. How incoming user requests or jobs are assigned to servers can significantly impact the performance of such systems. The canonical model for studying the effect of job assignment schemes on the mean response time of jobs consists of N servers each having its own queue, a stream of incoming jobs arriving at rate N λ, and a job dispatcher. The job dispatcher assigns every incoming job to a server in the system according to a specific job assignment scheme. For homogeneous systems consisting of identical servers, a natural job assignment scheme to consider is the Join-the-Shortest-Queue (JSQ) scheme in which each incoming job is assigned to the server with the minimum queue length. For finite N , this scheme is known to achieve the minimum average response time of jobs in a variety of settings [1][2][3][4]. Furthermore, in the large system limit (N → ∞) it has been shown that the average queuing delay of jobs (average time a job spends in the queue before its processing starts) under JSQ approaches to zero.
Variants of the JSQ scheme such as SQ(d) scheme and the Join-the-Idle-Queue (JIQ) scheme have also been extensively studied in the literature [5][6][7]. In the SQ(d) scheme, each job is assigned to the shortest of d randomly sampled queues; in the JIQ scheme, each job is assigned to an idle queue if one is available and is otherwise sent to a randomly sampled queue. These schemes require less messaging overhead than JSQ but achieve the same asymptotic performance as JSQ in the large system limit.
The (asymptotic) optimality of JSQ and its variants crucially relies on the assumption of homogeneity of server speeds. However, this assumption is not accurate in practice since data centres typically contain multiple-generations of physical devices with different processing capabilities [8]. Processing speeds of servers can vary also due to the presence of various types of acceleration devices such as GPUs, FPGAs and ASICs [9,10]. Finding the delay optimal scheme for such systems remains an open problem to this date. For such systems, speed-unaware schemes such as JSQ and SQ(d), designed primarily for homogeneous systems, may perform very poorly [11][12][13]. Speed-aware schemes which assign jobs based on both queue lengths and server speeds can significantly outperform speed-unaware schemes. To see this, consider a speed-aware version of JSQ, henceforth referred to as the Speed-Aware JSQ (SA-JSQ) scheme, in which each arrival is assigned to a server with the highest speed among the ones with the minimum queue length. In Figure 1, we compare the JSQ scheme with the SA-JSQ scheme for a system with two types of servers. Inter-arrival and service times of jobs are assumed to be exponentially distributed with rates N λ and 1, respectively. We observe that the average response time of jobs is almost 60% lower under the SA-JSQ scheme than under the JSQ scheme for loads (λ) less than 0.5. This example clearly highlights the need to design speed-aware schemes which can lead to much improved performance compared to speed-unaware schemes for heterogeneous systems.
There are various ways in which server speeds can be incorporated into job dispatching decisions. A natural scheme is to send each job to the queue with the shortest expected delay (SED), i.e., the queue where the ratio of the queue length to the server-speed is minimum. As we shall see later, for finite N this scheme performs slightly better than the SA-JSQ scheme discussed above but this difference vanishes quickly as the number of servers increases. Thus, the key questions in the context of heterogeneous systems are the following: what is the minimum achievable mean response time of jobs in heterogeneous systems? and is it possible achieve this minimum with some simple speed-aware variants of the JSQ scheme in the limit as the system size becomes large?

Contributions
To answer the questions above we need to find a lower bound on the mean-response time of jobs in heterogeneous systems and analytically characterise the performance of speedaware dispatching schemes in the limit as N → ∞. These are the primary aims of this Figure 1: Comparison of mean response time of jobs under JSQ and SA-JSQ schemes. Both schemes are applied to a heterogeneous system consisting of two types of servers: a fraction γ i of servers have rate µ i . We choose γ 1 = 1 − γ 2 = 1/5, and µ 1 = 4µ 2 = 20/8.

paper.
Our key finding is that in the fluid limit the SA-JSQ scheme achieves the lowest possible mean response time of jobs for heterogeneous systems. Note that to prove such optimality results, it is essential to develop the necessary tools to analyse job assignment schemes for heterogeneous systems. One would expect the fluid limit techniques applicable to homogeneous systems would easily generalise to heterogeneous systems. However, this turns out to be not the case. As explained later, the stochastic coupling technique, used to obtain uniform bounds on the stationary queue lengths in homogeneous systems, is not generalizable to heterogeneous systems. Consequently, we develop a new method based on exponential Lyapunov functions to obtain similar uniform bounds for heterogeneous systems. This method is sufficiently general to be applicable to other systems where a direct coupling is difficult to construct. Furthermore, the increased complexity of the underlying state space for heterogeneous systems results in a fluid limit which depends on the invariant distribution of a multi-dimensional birth-death process. Deriving exact analytical expressions for this invariant distribution is difficult. We find properties that are sufficient to show the existence, uniqueness and global stability of the fluid limit. From this point onward, we use the term 'optimality' to refer to optimality in the fluid limit unless otherwise mentioned. Our contributions are listed below: 1. Stochastic comparison and lower bound: Our first contribution is to compare the heterogeneous system, which consists of separate queues, with a similar heterogeneous system where all the servers serve a single central queue. We show that the system with separate queues stochastically dominates the system with the central queue.
From this stochastic comparison result and the fluid limit of the system with central queue, we obtain a lower bound on the mean response time of jobs that holds for any dispatching scheme applied to the system with separate queues. It is important to note that studying fluid limit of the system with a single central queue and heterogeneous servers can be of independent interest.
2. Stability and tightness: We next show that the heterogeneous system is stable under the SA-JSQ policy and obtain uniform bounds (not depending on the system size) on the tails of the stationary queue length distribution. The latter result is required to show the tightness of the sequence of stationary distributions indexed by the system size. The usual approach for proving tightness via coupling does not work in the heterogeneous setting as it is difficult to construct a coupling that maintains the desired stochastic dominance. Thus, we take a new approach and establish this result by analysing the drift of an exponential Lyapunov function. This technique is sufficiently general to be applicable to other systems where direct stochastic comparison is difficult.
3. Fluid limit analysis: Our final contribution is the fluid limit analysis of the SA-JSQ scheme in the heterogeneous system. This analysis turns out to be considerably more challenging than conventional fluid analysis due to the increased complexity of the underlying state space for heterogeneous systems and the separation of two time-scales in the fluid limit. The main idea in establishing the fluid limit of SA-JSQ is to first use the martingale functional central limit theorem (FCLT) and then characterise the limit of any convergent subsequence using Lemma 2 and Theorem 3 of [14]. The fluid limit in the heterogeneous setting turns out to be a function of the invariant distribution of a multi-dimensional Markov process whose exact analysis seems intractable. However, we are able to prove properties of the invariant distribution sufficient to characterise the fluid limit and its unique fixed point. Using these properties and the monotonicity of the system we also show that the fluid limit is globally stable. This final result establishes the asymptotic optimality of the SA-JSQ policy for heterogeneous systems.

Related works
There exists a vast literature on load-balancing policies for multi-server systems. Here, we only discuss the works that are most relevant to our paper. For a comprehensive review of existing works, we refer the reader to [15]. The JSQ policy was first shown to minimise the average delay of jobs for finite systems consisting of identical servers in [1] under the assumption of Poisson arrivals and exponential service times. This optimality result was later extended to general stochastic arrival processes and service-time distributions with non-decreasing hazard rates in [2], to queues with state-dependent service rates in [3], and to systems with finite buffer-buffers and general batch arrivals in [4]. Recent works [7,16] have considered the fluid and diffusion limits of the JSQ scheme. In the fluid limit, it has been shown in [7] that the fraction of servers with two or more jobs converges to zero under the JSQ scheme. This implies that in the fluid limit all jobs find an idle server to join. In the Halfin-Whitt regime, where the normalized arrival rate λ varies with the system size N as λ = 1 − β/ √ N for some β > 0, it has been shown in [16] that the diffusion-scaled process approaches to a two-dimensional reflected to the SA-JSQ scheme has been considered for constrained heterogeneous systems with finite buffer sizes. They prove the asymptotic optimality of this scheme using Lyapunov drifts methods. Although the scheme is technically the same as the SA-JSQ scheme for constrained systems, their analysis crucially relies on the assumption that the queues have finite buffer sizes. Hence, in their setting tightness and stability results follow immediately. In contrast, in the setting considered in this paper, the queues have infinite buffer sizes and proving optimality in this setting requires showing the tightness of the stationary distributions. As discussed before, this is one of the key difficulties in our model and we employ a new technique to establish tightness. Furthermore, the drift technique, applicable to finite-buffer systems, is difficult to generalise to our setting. Instead, to prove asymptotic optimality, we use martingale methods outlined in [28].
In this paper, the drift of the fluid-scaled Markov chain depends on the un-scaled state of the system through an indicator function. This dependence ultimately gives rise to a timescale separation in the fluid limit. A similar drift structure involving indicator functions was studied in [29]. Here, the challenge is to tackle the discontinuity of the drift at the boundaries of the state-space. It has been shown in [29] that in such cases the finite system can be viewed as a stochastic approximation of a differential inclusion. In [30], the author study optimal scheduling schemes for users competing for a common resource. They show that a tie-breaking rule similar to JSQ, where users with highest departure probability are preferred, leads to asymptotic optimality.

General Notations
We use the following notations throughout the paper. The sets R, N, Z + denote the set of real numbers, natural numbers, and non-negative integers, respectively. We also use the set Z + to denote the extended setZ + = Z + {∞}. For x, y ∈ R, we use x ∧ y, x ∨ y, and (x) + to denote max(x, y), min(x, y), and max(x, 0), respectively. For any n ∈ N, [n] denotes the set {1, 2, . . . , n}. For any complete separable metric space E, we denote D E [0, ∞) to be the set of all cadlag functions from [0, ∞) to E endowed with the Skorohod topology. Moreover, the notation B(E) is used to denote the Borel sigma algebra generated by the set E. The notation ⇒ is used for weak convergence. We use 1(A) to denote indicator function for set A.

Organisation
The rest of the paper is organized as follows. In Section 2, we introduce the system model and define the SA-JSQ policy. In Section 3, we obtain a lower bound on the mean response time of jobs that holds for any scheme in the heterogeneous system by comparing the system with a similar system having a central queue. In Section 4, we state our main results for the SA-JSQ policy. We prove the stability of the SA-JSQ scheme in Section 5 and the uniform bounds on the tails of the stationary queue lengths distribution in Section 6. The monotonicity property for SA-JSQ for a finite N system is shown in Section 7. In Section 8, we prove the process convergence result for SA-JSQ and characterise its fixed point in Section 9. The proof of resource pooled optimality is given in Section 10. Numerical studies comparing different schemes under heterogeneous setting is given in Section 11. Finally, we conclude the paper in Section 12.

System Model
We consider a system M N consisting of N parallel servers, each with its own queue of infinite buffer size. The servers are assumed to be heterogeneous, i.e., they have different service rates. Specifically, we assume that there are M different server types or pools. Each type j ∈ [M ] server has a service rate of µ j . The proportion of type j ∈ [M ] servers in the system is assumed to be fixed at γ j ∈ [0, 1] with j∈[M ] γ j = 1. We further assume without loss of generality that µ 1 > µ 2 > . . . > µ M and j∈[M ] γ j µ j = 1 (normalised system capacity is unity). For simplicity of exposition we also assume that there exists N ∈ N such that N γ j ∈ N for all j ∈ [M ]. 1 Jobs are assumed to arrive at the system according to a Poisson process with a rate N λ. Each job requires a random amount of work, independent and exponentially distributed with mean 1. The inter-arrival and service times are assumed to be independent of each other. Upon arrival, each job is assigned to a server where it either immediately receives service (if the server is idle at that instant) or joins the corresponding queue to be served later. The queues are served according to the First-Come-First-Server (FCFS) scheduling discipline. For this system, the term queue length will refer to the total number of jobs in a queue including the current job in service.
Our main interest is to find a job assignment policy that minimises the steady state mean response time of jobs in the system. To this end, we shall analyse a modified version of the classical Join-the-Shortest-Queue (JSQ) policy which is known to be optimal for homogeneous systems [2]. We shall refer to the modified policy as the Speed-Aware JSQ or the SA-JSQ policy. It is defined as follows Definition 1. Under the SA-JSQ policy, upon arrival of a job, it is sent to a server with the minimum queue length among all the servers in the system. Ties among servers of different types are broken by choosing the server type with the maximum speed and ties among servers of the same type are broken uniformly at random.
Note that unlike the classical JSQ policy, which breaks ties uniformly at random, the SA-JSQ policy breaks ties among servers of different types by choosing the server type with the maximum service rate. Furthermore, unlike the classical JSQ policy, the SA-JSQ policy is not optimal for the heterogeneous system for finite N : numerical simulations shown in Figure 2 show that a scheme which assigns jobs to servers based on the shortest expected delay (SED) (i.e., queue length divided by the service rate) performs marginally better than the SA-JSQ policy for small system sizes. However, as we show later in the paper, the gap vanishes as N → ∞. More specifically, we show that in the limit as N → ∞ there is no better scheme than SA-JSQ for heterogeneous systems.

Lower Bound on the Mean Response Time
A key ingredient in establishing the optimality of the SA-JSQ policy is finding a uniform lower bound on the steady state mean response time of jobs in system M N for all N under any stationary job assignment policy Π. We later show that this lower bound is achieved by the SA-JSQ policy as N → ∞.
To obtain this lower bound, we show that the total number of jobs in system M N under any stationary policy Π stochastically dominates the total number of jobs in a similar heterogeneous system M N working under a specific policy, referred to as the Join-the-Fastest-Free-Server (JFFS) policy.
Description of system M N : In system M N , the servers remain the same as in system M N , i.e., there are N servers in total with N γ j of them having service rate µ j for j ∈ [M ]. However, unlike system M N , we have a central queue for the whole system. Upon arrival, a job joins the central queue if all the servers are busy. Otherwise, the job is assigned to an idle server. Here, the central queue consists of only those jobs that are waiting for service and it excludes the jobs already in service.
JFFS policy: If multiple servers are idle and the queue is non-empty, a decision needs to be made on which server the next job should be assigned to. To this end, we consider the following job assignment policy referred to as the Join-the-Fastest-Free-Server (JFFS) policy.

Definition 2.
Under the JFFS policy, if idle servers are available and there are jobs waiting in the central queue, then the head-of-the-line (HOL) job is assigned to the idle server with the highest service rate. Ties within the same server type are broken uniformly at random. Hence, unlike system M N where each server only serves its own queue, in system M N , the central queue is served by all the servers. This system is, therefore, referred to as the resource pooled system [31].
The evolution of the resource pooled system M N under the JFFS policy can be described by the Markov chain Z (N ) = (Z (N ) (t), t ≥ 0), where Z (N ) (t) ∈ Z + denotes the total number of jobs in system M N at time t under the JFFS policy. Clearly, under the JFFS policy, the number of busy type j servers at time t ≥ 0 is given by (Z (N ) Hence, the transition rate q Z (N ) (k, l) of Z (N ) from state k to state l is given by otherwise. (1) The following two propositions characterise the stationary behaviour of the chain Z (N ) for finite N and for N → ∞, respectively.
Proposition 3. For λ < 1, the Markov chain Z (N ) is positive recurrent. Furthermore, if Z (N ) (∞) denotes the stationary number of jobs in the system, then Proposition 4. If λ < 1, then for system M N operating under the JFFS policy we have as N → ∞ Proposition 3 implies that the resource pooled system is stable for λ < 1. It also provides a uniform upper bound on the steady-state expected (scaled) number of jobs in the system for all N . These results are utilised to prove Proposition 4 which shows that the steady-state (scaled) number of jobs in the resource pooled system converges weakly to z * as N → ∞, where z * is as defined in (3).
In (3), the expression within the brackets on the RHS is maximised for Note that the existence of such a j * is guaranteed because λ < 1 = j∈[M ] γ j µ j . For j * as defined above, it is easy to see that the fraction of busy type j servers is one for all j ∈ [j * − 1] and zero for all j ≥ j * + 1. Furthermore, in pool j * , the fraction of busy servers is given by Since z * < 1, the central queue in the limiting system is empty in the steady-state.
To show that the system M N operating under any stationary policy Π stochastically dominates the system M N operating under the JFFS policy, we describe the state of the system M N under a stationary policy Π by the Markov chain X (N,Π) = (X (t) denotes the number of type j servers with at least i jobs. Let R (N,Π) (t) = i,j X (N,Π) i,j (t) denote the total number of jobs in system M N at time t ≥ 0 under policy Π. We have the following stochastic comparison result.
Theorem 5. For any stationary policy Π if Z (N ) (0) ≤ R (N,Π) (0), then the processes Z (N ) and X (N,Π) can be constructed on the same probability space such that The above theorem implies that if both Z (N ) and R (N,Π) are ergodic chains, then In subsequent sections, we establish that the above lower bound is achieved with equality when SA-JSQ is employed as the job assignment policy in M N . This will imply the asymptotic optimality of the SA-JSQ policy for M N .

Analysis setup and main results
In this section, we introduce the key ingredients and notations for our analysis of the SA-JSQ policy. In particular, we discuss the different state-descriptors used in the analysis and discuss some key properties of the space they belong to. We also state our main results for the SA-JSQ policy and discuss their implications.
The state of the system M N at any time t ≥ 0 under the SA-JSQ policy can be described in two different ways. These are as defined below: 1. Queue-length descriptor: We define the queue-length vector at time t ≥ 0 as k,j (t) denotes the queue length of the k th server of type j at time t.
2. Empirical measure descriptor: We define the empirical tail measure on the queue lengths at time t as i,j (t) denotes the fraction of type j servers with at least i jobs at time t. For completeness, we set x It follows from the Poisson arrival and exponential job size assumptions that both processes Q (N ) = (Q (N ) (t), t ≥ 0) and x (N ) = (x (N ) (t), t ≥ 0) are Markov. It is possible to switch from first descriptor to the second by noting the following We use both descriptors above to state and prove our results.
One important observation to make is that the SA-JSQ policy does not distinguish between servers of the same type. Hence, if the distribution ν of the initial state of the system is exchangeable within each server type, i.e., if for each j we have P ν (Q k l ,j (0) = r l , l ∈ [r]) = P ν (Q σ(k l ),j (0) = r l , l ∈ [r]) for all permutations σ of the numbers k 1 , k 2 , . . . , k r ∈ [N γ j ], then for any time t ≥ 0, we must have P ν (Q k l ,j (t) = r l , l ∈ [r]) = P ν (Q σ(k l ),j (t) = r l , l ∈ [r]), where P ν is the probability measure conditional on the initial state being distributed according to ν. This property is crucial in connecting the distribution of Q (N ) to that of x (N ) . In particular, by taking expectation on both sides of (5) we have where in the second equality we employ the exhangeability property discussed above. Clearly, the process Q (N ) takes values in Z N + and the process x (N ) takes values in the space S (N ) defined as Note that for finite N , the space S (N ) is countable since each x (N ) i,j can only take finitely many values. We further define the space S as follows where the 1 -norm, denoted by · 1 , is defined as s 1 max j∈[M ] i≥1 |s i,j | for any s ∈ S. It is easy to verify that the space S is complete and separable under the 1 -norm. Furthermore, if the system's state x (N ) belongs to S (N ) ∩ S, then there are finitely many jobs in the system. Starting with a state in S (N ) ∩ S we can ensure that chain x (N ) remains in S ∩S (N ) for all t ≥ 0 only if the process x (N ) , or equivalently the process Q (N ) , is positive recurrent. Our first main result states that this is indeed the case when λ < 1.
Theorem 7. The process Q (N ) or equivalently x (N ) is positive recurrent for each λ < 1 and each N .
The theorem above implies that for λ < 1 the stationary distributions of Q (N ) and x (N ) exist and they are unique. Let Q (N ) (∞) = lim t→∞ Q (N ) (t) (resp. x (N ) (∞) = lim t→∞ x (N ) (t)) denote the state of the system distributed according to the stationary distribution of Q (N ) (resp. x (N ) ). The stability of the system guarantees that the steadystate expected number of jobs in the system is finite, i.e., x (N ) (∞) belongs to S almost surely. However, to establish the asymptotic optimality of the SA-JSQ policy, we require the stronger result that the sequence (x (N ) (∞)) N of stationary states indexed by the system size is tight in S. Here, it is important to observe that S is not a compact space. The relatively compact subsets of S and the tightness criterion for sequences in S are stated in E. The tightness criterion essentially requires the expected tail sums approach to zero as l → ∞ uniformly in N . To show that (x (N ) (∞)) N satisfies this criterion, we need the following important result which states that the stationary tail probabilities of the queue lengths decay exponentially and the decay rate is uniform in N . where Our next main result establishes a key monotonicity property of the system for finite N . For two states q andq in Z N + we say q ≤q if q k,j ≤q k,j for each k ∈ [N γ j ], j ∈ [M ]. The inequality s ≤s is similarly defined for s,s ∈ S. We have the following result.
Theorem 9. Consider two systems with initial states x N andx N ) denote the corresponding processes describing the two systems under the SA-JSQ policy. Then, the processes Q (N ) andQ (N ) (resp. x N andx N ) can be constructed on the same probability space such that The monotonicity property stated above implies that if two systems, both working under the SA-JSQ policy, start at two different initial states such that the queue lengths in the first system are dominated by the corresponding queue lengths in the second system, then this dominance is maintained for all t ≥ 0. This property turns out to be essential in establishing the global asymptotic stability of the fluid limit process.
Our next set of results characterise the asymptotic properties of the process x (N ) as N → ∞. The first result states that the sequence (x (N ) ) N of processes indexed by N converges weakly to a deterministic process x = (x(t), t ≥ 0) defined on S. To describe the limiting process, we define l j (s) = min{i : s i+1,j < 1} for any state s ∈ S to be the minimum queue length in pool j ∈ [M ] in state s. where and l j (s) = 0, then p 0,j (s) = 1.
In the theorem above, p i−1,j (s) can be interpreted as the limiting probability of an incoming arrival being assigned to a type j server with queue length i − 1 when the system is in state s ∈ S. With this interpretation, the properties of p i,j (s) listed above follow intuitively from the assignment rule under the SA-JSQ policy. Indeed, properties P4 and P5 state that if in state s ∈ S pool j ∈ [M ] is the pool with the highest speed containing idle servers, then with probability 1, incoming jobs are assigned to idle servers in pool j in state s. Similarly, properties P2 and P3 imply that for any state s ∈ S and any pool j ∈ [M ] with minimum queue-length l j (s), jobs can only be assigned to queues with lengths l j (s) − 1 and l j (s) in the limiting system.
The exact expressions for p i,j (s) are complicated as they depend on the stationary probabilities of a multi-dimensional Markov chain (we explain this more in Section 8). In Theorem 10, we only list the properties essential to characterise the fixed point x * = (x * i,j ) of the fluid limit x. In our final result stated below, we show that the fixed point x * is unique and globally attractive.

Theorem 11.
(i) For λ < 1, there exists a unique fixed point (ii) (Global Stability): If λ < 1, then for any solution x of (10) with (iii) (Interchange of Limits): Let λ < 1. Then, the sequence (x (N ) (∞)) N converges weakly to x * , i.e., Note that the last statement of the theorem implies that the sequence of stationary distributions indexed by the system size concentrates on the point x * . Furthermore, the first statement of the theorem implies that in state x * ∈ S the fraction of servers with two or more jobs is zero. This is similar to the classical JSQ result except that in this case if , then all servers in pools k ∈ [j − 1] have exactly one job and in pool j a fraction (λ − j−1 k=1 µ k γ k )/µ j γ j of servers have exactly one job; all remaining servers are idle. Thus, the total (scaled) number of jobs in state x * is equal to z * as defined by (3). Thus, by Little's law, the mean response time of jobsT N under the SA-JSQ policy converges to z * /λ as N → ∞, which by Corollary 6 implies the asymptotic optimality of the SA-JSQ policy.

Stability
To show that the process Q (N ) is positive recurrent for all λ < 1, we use an appropriately defined Lyapunov function and show that its drift along any trajectory of Q (N ) is negative outside a compact subset of the state space. For any function f : Z N + → R, defined on the state space of the process Q (N ) , the drift evaluated at a state Q ∈ Z N + is given by where k,j denotes the N-dimensional unit vector with one in the (k, j) th position; r ±,N k,j (Q) are the transition rates from the state Q to the states Q ± e (N ) k,j . Intuitively, the drift, defined above, represents the expected infinitesimal rate at which f (Q (N ) (t)) changes when Q (N ) (t) = Q. Under the SA-JSQ policy, for each state where I min,j (Q) denotes the set of servers with the minimum queue length in pool j in state Q and j † (Q) denotes the fastest pool that contains a server with the minimum queue length in state Q. The upward transition rate r +,N k,j (Q) is obtained by multiplying the total arrival rate with the probability that the k th server in the j th pool receives an arrival. Similarly, the downward transition rate r −,N k,j (Q) is simply the service rate of the k th server in the j th pool if the server is busy.
Proof of Theorem 7: To prove Theorem 7, we compute the drift of the Lyapunov function Φ : From (12) we have that for any where B j (Q) denotes the number of busy servers in pool j in state Q. In the second equality, we have used the facts that j,k r +,N k,j (Q) = N λ and k r −,N k,j (Q) = µ j B j (Q) which follow easily from (13) and (14), respectively. We further note from (13) and (14) that In the second line, we have used the facts that j µ j k Q k,j ≥ j µ j k Q min = N Q min and B j (Q) ≤ N γ j . Hence, it follows from the above that if λ < 1, then the drift is strictly negative whenever j µ j k Q k,j > N (1+λ) 1−λ , and is bounded by N (1 + λ) otherwise. Thus, using the Foster-Lyapunov criterion for positive recurrence (see, e.g., Proposition D.3 of [32]) we conclude that Q (N ) is positive recurrent.

Uniform bounds and tightness
In this section, we first prove Theorem 8 which shows that the stationary queue length distribution has a uniformly decaying tail for all system sizes. We then use this uniform bound to establish the tightness of the sequence (x (N ) (∞)) N in S.
For homogeneous systems working under the classical JSQ policy, uniform bounds, similar to (9) can be obtained by coupling the system with another similar system working under a 'worse performing' policy such as the random policy in which the destination server for each job is chosen uniformly at random from the set of all servers. A coupling similar to the one described in [33] ensures that the total number of jobs in the first system is always smaller than that in the second system. However, in the heterogeneous setting, it is difficult to construct a similar coupling since the arrival of a job to a given pool in one system does not guarantee that the job will join the same pool in the other system.
To overcome this difficulty, we use a completely different approach based on analysing the drift of an exponential Lyapunov function. In particular, we analyse the drift of the Lyapunov function Ψ θ : for some θ > 0. They key idea we employ to prove Theorem 8 is the following: we show that for some positive values of θ the steady-state expected drift From this, we obtain bounds on the weighted sum of moment generating functions of the stationary queue lengths of different pools, i.e., on k,j (∞))] for some positive θ. Using Chernoff bounds, we then obtain the bounds on the tail probabilities as in Theorem 8.
Note that although we would normally expect the steady-state expected drift to satisfy all moments of the stationary queue lengths exist. However, the stability condition only guarantees the existence of the first moment, but it does not guarantee the existence of higher moments of the queue lengths. Thus, to prove Theorem 8, we use a weaker condition given by Proposition 1 of [34] which states that for any non-negative function f : However, to use this result we first need to show that the function Ψ θ satisfies the above condition for some positive θ. This is shown in the following lemma.
Lemma 12. For Ψ θ as defined in (19) and θ ≥ 0, we have and the steady-state drift of Ψ θ satisfies Proof. From (12) and (19), we have that for any Q ∈ Z N First, note that from (13), we can write where Q min denotes the minimum queue length in state Q and the equality on the second line follows from the fact that for k ∈ I min,j † (Q) (Q) the queue length at the k th server of type j † (Q) is Q min . Furthermore, using (14), we can write Hence, using (24) and (25), we can write We further note that for any θ > 0 we have Using this fact in (26), we have that for any θ ≥ 0 This proves the first statement of the lemma. In order to prove the next statement, note that for all θ ∈ [0, − log λ), we have λe θ − 1 < 0. Therefore, from (20) it follows that for all where in the second inequality we have used the fact that The last statement of the lemma now follows from the application of Proposition 1 of [34].
Proof of Theorem 8: We are now equipped to prove Theorem 8 using the result of the lemma above. Taking expectation of (20) with respect to the stationary distribution and applying (22) we obtain where B j (Q) = N γ j − I j (Q) denotes the number of busy servers in pool j in state Q. In the last inequality we have used the fact that due to erogodicity of the process Q (N ) , the steady state rate of departure from the system E[ j µ j B j (Q)] is equal to the arrival rate N λ. Hence, from (28) we have that for all θ ∈ [0, − log λ) where the second equality follows from the exchangeability of the stationary measure. Thus, Now, for each positive θ we have .
The statement of the theorem now follows by using (29) on the above inequality.
Using Theorem 8, we now show that the sequence of stationary states (x (N ) (∞)) N is tight in the space S under the 1 -norm. According to Prohorov's theorem [35] the tightness of this sequence will imply that the sequence has convergent subsequences with limits in S. We shall show later that all convergent subsequences of (x (N ) (∞)) N have the same limit, thereby establishing the convergence of the original sequence (x (N ) (∞)) N to the same limit.
The necessary and sufficient criterion for tightness of the sequence (x (N ) (∞)) N in S under the 1 -norm is derived in Lemma 22 of E and is given by The proof of Proposition 13 consists of verifying this condition using the uniform bounds derived in Theorem 8. The formal proof is given in B.

Monotonicity
In this section, we prove the monotonicity property stated in Theorem 9. The key idea here is to couple the arrivals and the departures of the two systems such that if the inequality is satisfied just before the arrival or departure event at time t then it is also satisfied after the event has taken place. Proof of Theorem 9: We refer to the systems corresponding to the processes Q (N ) andQ (N ) as the smaller and larger systems, respectively. Furthermore, in both systems, we call the k th server in the j th pool as the server with index (k, j).
To couple the departures, we first generate a sequence of potential departure instants at the points of a Poisson process with rate N . At each potential departure instant, a server index (k, j) is chosen as follows: First, a server type j ∈ [M ] is chosen with probability µ j γ j (recall that j∈[M ] µ j γ j = 1). Then, any server k ∈ [N γ j ] within the chosen type j is selected uniformly at random. Once the server index (k, j) is chosen as described above, the server with the index (k, j) is selected for departure in both systems. In each system, an actual departure occurs from the selected server if the selected server is busy; otherwise, no departure occurs from the selected server (this is why the term potential departure is used to describe the event). Let (k, j) denote the index of the chosen server and D denote the potential departure instant. Assume that the inequality Q To couple the arrivals, we generate a common Poisson arrival stream with rate N λ for both systems. At each arrival instant A, the job assignment decision is made following the SA-JSQ policy in each system independently of the other system, unless the pool containing the destination server is the same for both systems. If j † (Q (N ) (A − )) = j † (Q (N ) (A − )) = j, then we perform the following steps sequentially: (1) In the smaller system, the destination server is chosen uniformly at random from the servers having the minimum queue length in pool j. Let the index of this chosen server be (k, j). (2) We check if the server having the same index (k, j) in the larger system has the minimum queue length. If so, then this server is chosen as the destination server in the larger system. (3) Otherwise, the destination server in the larger system is chosen uniformly at random (and independently of the smaller system) from the servers having the minimum queue length in pool j in the larger system. Let (k s , j s ) and (k l , j l ) be the indices of the destination servers in the smaller and the larger systems, respectively, at an arrival instant A. Let S = Q If (k s , j s ) = (k l , j l ), then the inequality trivially holds at t = A. If (k s , j s ) = (k l , j l ), then we have the following possibilities: 1. If j s < j l : In the larger system, the incoming arrival joins the server with index (k l , j l ) and there is no arrival to the server with index (k l , j l ) in smaller system. Hence, after the arrival we have Thus, for (31) to be violated we must have Q k l ,j l (A − ) which contradicts with the fact that the server with index (k l , j l ) is the destination server in the larger system, i.e., it is the fastest server with the minimum queue length in the larger system, because a faster server of type j s (< j l ) has smaller queue length. Hence, (31) must hold in this case.
2. If j s = j l = j, k s = k l : Similarly as before, the inequality Q ks,j (A − ) = S before the arrival. Since the arrival is assigned to the server with index (k l , j) in the larger system, we must have L =Q In this case, our coupling rule dictates that if we have chosen the index (k s , j) as the destination server for the smaller system, then we must also choose the same indexed server in the larger system as the destination server. This leads to a contradiction because k s = k l . Hence, (31) must hold in this case.
3. If j s > j l : Similar to the first two cases, the inequality Q Hence, there must be a tie between the servers of indices (k s , j s ) and (k l , j l ) in both systems. Therefore, according to the SA-JSQ policy the incoming arrival should be assigned to the server having index (i l , j l ) in smaller system because j l < j s . This leads to the contradiction because job has been assigned to the server having index (i s , j s ) in the smaller system. Hence, (31) must hold in this case.
This completes the proof of the theorem.

Process convergence
In this section, we outline the proof of Theorem 10 using the martingale approach of [28] and the time-scale separation technique of [14]. Here, we discuss the main steps of the proof and characterise the fluid limit process x. The proof consists of the following three steps Step 1: Martingale representation: The first step is to express the evolution of each component of the process x (N ) in terms of suitably defined martingales and a process V (N ) which evolves at a faster time scale than the components of x (N ) . In particular, the process i,j (t) counts the number of type j servers with at most i − 1 jobs at time t. It is easy to see that V (N ) is a Markov process defined on E = (Z ∞ + ) M with transition rates where R i,j for all i ≥ 1 and j ∈ [M ] is defined as The set R i,j represents the set of states where the minimum queue length is at least i for the pools in {1, . . . , j − 1}, exactly i − 1 for pool j, and at least i − 1 for the pools in {j + 1, . . . , M }. Thus, when V (N ) (t) ∈ R i,j , an incoming job under the SA-JSQ scheme will be assigned to a type j server with queue length i − 1. We can therefore express x (N ) i,j for each i ≥ 1 and j ∈ [M ] as follows i+1,j (s))ds where M To treat them as a single object and characterise its limit, we define the joint process for any A 1 ∈ B([0, ∞)) and A 2 ∈ B(E). Hence, (34) can be rewritten in terms of β (N ) for i ≥ 1 and j ∈ [M ] as follows i+1,j (s))ds Step 2: Relative compactness: The second step in proving Theorem 10 consists of showing that the sequence of processes ((x (N ) , β (N ) )) N is relatively compact in D S [0, ∞)×L 0 where L 0 is defined as the space of measures on [0, ∞)×E satisfying β([0, t]×E) = t for each t ≥ 0 and each β ∈ L 0 . We equip L 0 with the topology of weak convergence of measures restricted to [0, t] × E for each t. In the next lemma, we show that ((x (N ) , β (N ) )) N is a relatively compact sequence in D S [0, ∞) × L 0 and characterise the limit of any convergent subsequence.
Lemma 14. If x N (0) ⇒ x(0) ∈ S as N → ∞, then the sequence ((x (N ) , β (N ) )) N is relatively compact in D S [0, ∞) × L 0 and the limit (x, β) of any convergent subsequence satisfies for The proof of Lemma 14 consists of verifying standard conditions of relative compactness in D S [0, ∞) given in Proposition 3.2.4 of [36]. This is achieved using an approach similar to [7]. The details are given in F.
Step 3: Characterisation of the limit: The final step in proving Theorem 10 is the characterisation the limit β([0, t], R i,j ) appearing in (36). To do so, we define for any x ∈ S a Markov process V x on E with transition rates From Lemma 2 and Theorem 3 of [14], it follows that the limit β( where π x is a stationary measure of the process V x and π x satisfies the following for all Hence, we can write (36) in terms of π x as We set p i−1,j (x) = π x (R i,j ). Hence, to complete the proof of Theorem 10, it remains to show that x uniquely determines the stationary measure π x and it satisfies the properties P1-P5 listed in Theorem 10. First note from (33) that the sets R i,j for i ≥ 1, j ∈ [M ] form a partition of E. Since π x is a probability measure on E, it follows that i≥1,j∈[M ] p i−1,j (x) = i≥1,j∈[M ] π x (R i,j ) = 1. This proves P1. Since x 1 < ∞ for each x ∈ S, there exists l j (x) = min{i : x i+1,j < 1} for all j ∈ [M ] and x ∈ S. Observe that for each j ∈ [M ] we have x i,j = 1 for all 0 ≤ i ≤ l j (x), and x i,j < 1 for all i ≥ l j (x) + 1. Therefore, from (38), it follows that Hence, from the definition of the set R i,j in (33) it follows that p i−1,j (x) = π x (R i,j ) = 0 for all i ≥ l j (x) + 2 and j ∈ [M ]. This proves the property P2.
Hence, the only part left to prove Theorem 10 is to show that π x is uniquely determined by x for all x ∈ S. To show this, it is sufficient to prove that the stationary distribution of (V l j (x),j : j ∈ [M ]) is uniquely determined by x because the stationary distribution of all other components of V x has already been uniquely characterised by (40) and (41). The transition rates of the individual components of the chain (V l 1 (x),1 , V l 2 (x),2 , . . . , V l M (x),M ) are given by Note that the Markov chain given by (42) is defined onZ M + and has 2 M communicating classes since each component of the chain can be either finite or infinite. To show the uniqueness π x we need to show that π x is concentrated only on a single communicating class among these 2 M classes. This is equivalent to showing π x (V l j (x),j = ∞) = 0 or 1 for each j ∈ [M ]. To show the above, we use the result of the next lemma which characterises the stationary distribution of a finite dimensional Markov chain whose transition rates have a form similar to (42).
where e i denotes the K-dimensional unit vector with entry 1 at i th position. The Markov chain U is positive recurrent if and only if i∈[K] ν i λ < 1. Furthermore, if π denotes the stationary distribution of the chain U, then we have Using Lemma 15, we show that π x (V l j (x),j = ∞) = 0 or 1 for each j ∈ [M ] in I.

Fixed Point Characterisation
In this section, we prove Theorem 11 which characterises the fixed point x * of the fluid limit x and shows that the fixed point is globally attractive. For the proof of uniqueness of the fixed point, we explicitly use properties P1-P5 listed in Theorem 10. Moreover, to prove global stability we use the monotonicity of the process x (N ) proved in Theorem 9.
The proofs of global stability and limit interchange are given in H.

Optimality of the Resource Pooled System
In this section, we prove Theorem 5. We use the following lemma which establishes that when both M N and M N have the same total number of jobs i, the rate of departure Proof of Theorem 5: We construct a coupling between the processes Z (N ) and Let the current instant be t and assume that Z (N ) (t) ≤ R (N,Π) (t). We shall describe a way of generating the next event and the time for the next event s such that Z (N ) (s) ≤ R (N,Π) (s) is maintained right after the event has taken place.
We generate the time until the next potential arrival for both systems as an exponentially distributed random variable with mean N λ. Hence, for both systems, arrivals occur at the same instants.
If Z (N ) (t) < R (N,Π) (t) then the time until the next potential departure is generated independently for each system as exponential random variables with means q Z (N ) (Z (N ) (t), Z (N ) (t)− 1) and j µ j X (N,Π) 1,j (t) for systems M N and M N , respectively. If Z (N ) (t) = R (N,Π) (t) = i, then we generate the time D until the next potential departure for M N as an exponential random variable with mean j µ j X (N,Π) 1,j (t). We also generate another independent exponential random variable C with mean q Z (N ) (i, i − 1) − j µ j X (N,Π) 1,j (t) ≥ 0. Note that we can do so by Lemma 16. Now we generate the time until the next potential departure for M N as D = min(D, C). Therefore, D ≤ D and D is exponentially distributed with mean Once all the potential arrival and departures are generated as described above, the next true event is taken to be the potential event which occurs the earliest; all other potential events are discarded (which is possible because of the memoryless property of the exponential distribution). Due to the construction above, it is clear that Z (N ) (s) ≤ R (N,Π) (s) is maintained right after the next true event. This completes the proof.

Numerical Studies
In this section, we present simulation results for different load balancing schemes. For all simulations, we have assumed M = 2 and taken the number of arrivals to be 3 × 10 5 . In Figure 3(a), we have plotted the mean response time of jobs for different schemes as a function of the normalised arrival rate λ. For performance comparison we also simulated a scheme proposed in [37] and referred to as the SQ(d 1 , d 2 ) scheme. For the SQ(d 1 , d 2 ) scheme, upon job arrival d j servers of type j are sampled uniformly at random from the set of N γ j servers for j ∈ [2]. The job is then sent to the server with the minimum queue length among the sampled servers. Ties within different types servers are broken by selecting the type with the maximum rate. We see that with SA-JSQ we obtain upto 60% reduction in average response time of jobs compared to classical JSQ. As expected, the performance of SQ (2,2) lies in between classical JSQ and SA-JSQ. To investigate the convergence rate to the fixed point of the fluid limit, in Figure 3 i,j | as a function of N for λ ∈ {0.5, 0.7, 0.9}. We note that for large values of λ the distance is higher than that for smaller values of λ.

Conclusion and Future Works
In this paper, we have investigated speed-aware JSQ-type load balancing schemes for heterogeneous systems. We obtained a lower bound on the mean response time of jobs under any load balancing scheme by comparing the system with an appropriate resource pooled system. We showed that the lower bound is achieved by the SA-JSQ scheme in the fluid limit, thereby establishing the asymptotic optimality of SA-JSQ. Moreover, in establishing the fluid limit of SA-JSQ, we have proved uniform bounds on the stationary measures of queue lengths which are required to prove tightness. Using coupling, we have also shown that any stationary load balancing scheme in a system of parallel queues stochastically dominates the JFFS scheme in the resource pooled system. There are many interesting avenues for future work. Characterising the performance of the SA-JSQ scheme in the Halfin-Whitt regime remains as an open problem. It is also interesting to analytically characterise the distance between x (N ) (∞) and the fixed point x * as a function of the system size N . In this section, we analyse the resource pooled system M N as described in Section 3 under the JFFS policy and prove the results stated in Propositions 3 and 4.

A.1 Proof of Proposition 3
To prove the proposition, we construct a coupling between the resource pooled system M N and an M/M/1/N system with Poisson arrival rate N λ and N identical serves, each with rate 1. Let Y (N ) (t) denote the number of jobs in the M/M/1/N system at time t ≥ 0. The transition rates q Y (N ) (k, l), for k, l ∈ Z + , of the chain From the standard results on M/M/1/N queues, it follows that the process Y (N ) = (Y (N ) (t), t ≥ 0) is positive recurrent for λ < 1. Furthermore, if Y (N ) (∞) denotes the stationary number of jobs in the system, then from the standard results on M/M/1/N queues we have Hence, to prove the proposition it suffices to construct a coupling between Z (N ) and for all t ≥ 0. First, note that for each Markov chain, the transition rate out of any state is bounded above by the constant B = N (λ + 1). Hence, we can generate both Z (N ) and Y (N ) processes by constructing the corresponding uniformized discrete-time Markov chainsZ (N ) = (Z (N ) (m), m ∈ Z + ) and Ỹ (N ) = (Ỹ (N ) (m), m ∈ Z + ). The one-step transition probabilities of these two chains from state k to state l are respectively given by where q Z (N ) and q Y (N ) denote the transition rates for Z (N ) and Y (N ) , respectively. To construct the continuous-time sample paths of the original chains Z (N ) and Y (N ) on the same probability space, we generate a common Poisson process with rate B and embed the time-steps of bothZ (N ) andỸ (N ) into the points of the Poisson process. It is easy to see from the transition rates that pZ We let the chainsZ (N ) andỸ (N ) evolve independently of each other except at instants when they become equal. IfZ (N ) (m) =Ỹ (N ) (m) = k ∈ Z + for some time step m ∈ Z + , we first constructỸ (N ) (m + 1) according to the transition probabilities pỸ (N ) .

A.2 Proof of Proposition 4
To prove Proposition 4, we study the limit of the process z (N ) = z (N ) (t), t ≥ 0 defined as Thus, z (N ) (t) denotes the scaled number of jobs in M N under the JFFS scheme at time t. We first characterise the limit of the sequence of processes (z (N ) ) N in the lemma below.
is the unique deterministic process satisfying the following integral equation Furthermore, the process z satisfying (50) has a unique fixed point z * given by Proof. Let (A(t) : t ≥ 0) and (D(t) : t ≥ 0) be independent unit-rate Poisson processes. We can express the evolution of the total number Z (N ) (t) of jobs in the system M N as follows: where Z (N ) (0) = N z (N ) (0) and T : R + → R + is defined as Hence, for Z ∈ Z + , T (Z) represents the total rate at which jobs depart the system in state Z. Dividing (52) by N , we have where M (N ) Using Lemma 3.
Using the martingale functional central limit theorem [28], we have From (53) and (50), we see that both z (N ) and z can be expressed as is defined as the mapping that takes (b, y) to x determined by the following integral equation Hence, if f is well-defined and continuous, then the continuous mapping theorem proves the first statement of the lemma. From Theorem 4.1 of [38]), it follows that to show that f is well-defined and continuous, it is sufficient to show that T is Lipschitz continuous. Since, . Therefore, the sum of Lipschitz functions is again Lipschitz with constant (µ 1 ∨ µ 2 ∨ . . . ∨ µ M ). This establishes the first statement of the lemma.
To prove the second statement of the lemma, note that we can can express (50) in its differential form as follows Hence, any fixed point z * of the process z must satisfy the equation λ − T (z * ) = 0. Since T is a piecewise-linear map, it is easy to solve the above equation in closed form and find the unique solution to be (51).
Proof. We prove the first statement of the lemma by considering the following two cases (i) u ≥ z * and (ii) u < z * . We only provide the proof for the first case as the proof of the second case is similar. If u ≥ z * then z(u, t) ≥ z * for all t ≥ 0. To see this, assume on the contrary that z(u, t) < z * for some t > 0. Since z(0, u) = u ≥ z * and z(u, ·) is continuous, there must exist a t 1 ∈ (0, t) such that z(u, t 1 ) = z * . But since z * is a fixed point, this implies that z(t) = z * for all t ≥ t 1 which leads to a contradiction. Now consider the Lypunov function V : where We further note that T is a strictly increasing function of its argument. Hence,V (z(u, t)) < 0 when z(u, t) > z * . This implies that V (z(u, t)) → 0 as t → ∞, thereby proving the first part of the lemma.
To prove the second part of the lemma, we first show that the sequence z (N ) (∞) N is tight. By the application of Markov inequality and the bound in (2), we have This shows that to make sup N ≥1 P(z (N ) (∞) > a) < for any > 0, there exists appropriate choice a( ) not dependent on N . This shows that the sequence z (N ) (∞) N is tight. The rest of the lemma now follows from the same line of arguments as in the proof of the second statement of Theorem 11.

B Proof of Proposition 13
Fix any > 0 and l ≥ 1. Using Markov inequality, we obtain P max i is a sequence non-negative random variables for each j ∈ [M ], using monotone convergence theorem we can interchange the sum and the expectation on the RHS. Hence, we have P max where the last equality follows from (5). Now, from Theorem 8 we know that for any θ ∈ [0, − log λ) we have 1 µ j γ j . Since the RHS of the above inequality is not dependent on N , using (55) we have for all θ ∈ [0, − log λ) and all l ≥ 1. Hence, the condition of tightness given by (30) is verified by fixing some θ ∈ (0, − log λ) and letting l → ∞.

C Martingale Representation and Its Convergence
We first write the evolution of x (N ) i,j (t) for all t ≥ 0 in terms of number of arrivals and departures from system till time t, for i ≥ 1 and j ∈ [M ] as i+1,j (s))ds.
We next show that the processes M i+1,j (u))du , 0 s t . . Moreover, the predictable quadratic variation processes are given by Next, we prove that The proof of square-integarble martingales and its corresponding predictable quadratic variation processes then follows immediately using Lemma 3.2 from [38]. Note that using crude inequality we can write Similarly, we can show E(L i,j (t)) < ∞ and E A i,j (L i,j (t)) < ∞. Now we can write the martingale representation of equation (57) for all t ≥ 0, i ≥ 1, and j ∈ [M ] as i+1,j (s))ds In below lemma, we prove that the martingale part in (58) converges to 0 with respect to 1 . Lemma 20. Following convergence holds as N → ∞ Proof. The proof is similar to the proof of Proposition 4.3 in [7] using Doob's inequality.

D Proof of Lemma 16
To prove (47), we consider the following linear optimisation problem The first constraint in (59) is true as the total number of busy servers j∈[M ] X (N,Π) 1,j (t) at time t in M N is always less than equal to the total number of customers in system that is i. The above optimisation problem has a unique maximum which is obtained in following way. First, note that the objective function is given as the weighted sum of X (N,Π) 1,j (t) with weight µ j for j ∈ [M ]. We know that the maximum weight is µ 1 . Therefore, the maximum value that X (N,Π) 1,1 (t) takes is (i ∧ N γ 1 ). Moreover, the second maximum weight is µ 2 , hence the maximum value that X (N,Π) 1,2 (t) takes is ((i − N γ 1 ) + ∧ N γ 2 ). Proceeding in this way the maximum value that X , which completes the proof.

E Characterisation of Compact Sets and Tightness Criteria
In the lemma below, we characterise compact sets in the space S. Proof. Suppose any B ⊆ S satisfying (60). To show B is relatively compact in S, we need to show that any sequence (y (N ) ) N ≥1 in B has a Cauchy subsequence. Since S is complete under 1 , therefore the sequence (y (N ) ) N ≥1 has a convergent subsequence whose limit lies inB which will complete the proof. Next we show that the sequence (y (N ) ) N ≥1 has a Cauchy subsequence. Fix any > 0 and choose l ≥ 1 such that Using (61), and (62), for all R, N ≥ N and for y (N ) , y (R) ∈ B we have along the sequence of indices (N m ) m≥1 . This shows the existence of a Cauchy subsequence. Moreover, the limit point lies in S follows from the completeness of 1 space and the fact that S is a closed subset of 1 . Now for the only if part, let B be a relatively compact set in S. Assume that there exists a > 0 such that This implies that for each k ≥ 1, there exists a y (k) ∈ B, such that max j∈[M ] i≥l y (k) i,j ≥ 2 . Therefore, if y * be the limit of the sequence (y (k) ) k≥1 , then (63) implies that max j∈[M ] i≥l y * i,j ≥ 2 for all l ≥ 1, this leads to the contradiction that y * ∈ 1 .
Next, we prove the criteria for a sequence to be tight in S. Proof. For if part, we construct a relatively compact set B for any > 0 such that P y (N ) ∈ B < , ∀N ∈ N.
As (y (N ) ) N ≥1 satisfies (64), therefore there exists a l( ) ≥ 1 for all > 0 such that and there exists a N ≥ 1 such that Moreover, since y (1) , . . . , y (N ) are random elements of S, there exists k( ) = max {l 1 ( ), . . . , l N ( )} such that This implies that there exists an increasing sequence (l(n)) n≥1 such that P max From Lemma 21, the set B is relatively compact in S. Therefore, we have where the first inequality follows from union bound. For only if part, assume that there exists a > 0 such that Since (y (N ) ) N ≥1 is tight in S, therefore there exists a convergent subsequence (y (N k ) ) k≥1 with limit y * . From (65), we can write where the last inequality follows from Portmanteau's theorem for closed set. This leads to the contradiction that y * ∈ 1 .

F Proof of Lemma 14
To prove relative compactness of the sequence ((x (N ) , β (N ) )) N ≥1 , we start with proving that for all finite time t the system occupancy state lies in some compact set.
Lemma 23. Assume x (N ) (0) ⇒ x(0) ∈ S, as N → ∞. Then for any T ≥ 0, there exists a L(T, x(0)) > 2 such that under the SA-JSQ policy, the probability that an arriving job joins a server with at-least L(T, x(0)) − 1 active jobs upto time T tends to 0 as N → ∞.
Proof. Let A (N ) (t) denote the total number of arrivals up to time t. Arrivals are happening with rate N λ. Then for any > 0 we have is the minimum queue length in the j th pool at time t for N th system. The probability at which an arrival joins a server with at-least L(T, x(0)) − 1 jobs during the time interval [0, T ] is given by where X (N ) (t)the is the total number of jobs in system at time t. From conservation of flow, we can write is the total number of departures from system till time t. Therefore, from (66), we can write Therefore, we have From (66), (67), (68) and choosing L(T, We now prove the relative compactness of the sequence ((x (N ) , β (N ) )) N ≥1 by showing the relative compactness of individual component. Note that the space E is compact. Therefore, relative compactness of the sequence (β (N ) ) N ≥1 follows from Prohorov's theorem [35]. To prove relative compactness of the sequence (x (N ) ) N ≥1 , we need to verify following conditions. 1. For every η > 0 and rational t ≥ 0, there exists a compact set B η,t ⊂ S such that 2. For every η > 0 and for T > 0 there exists a δ > 0 and a finite partition We first prove condition (69). From Lemma 23, for any fix t ≥ 0 we have Now it can be easily verified that the sequence (x (N ) (0)) N ≥1 is tight in S. Therefore, using previous condition we can write for any > 0 Hence, from Lemma 22 the sequence (x (N ) (t)) N ≥1 is tight in S. This implies that the condition (69) is satisfied. Next for any t 1 < t 2 , we consider i+1,j (s))ds Using the above equation we can write 1 distance between x (N ) (t 1 ) and x (N ) (t 2 ) as where P(ζ (N ) > η 2 ) < η for all sufficiently large N . Take δ = η/(4( λ γ min + µ 1 )) and any partition with max l∈[n] (t l − t l−1 ) < η/(2( λ γ min + µ 1 )) and min l∈[n] |t l − t l−1 |> δ, we have on the event {ζ (N ) ≤ η 2 }. Therefore, for sufficiently large N we obtain P max Hence the condition (70) is satisfied. Next, we show that the limit (x, β) of any convergent subsequence of the sequence ((x (N ) , β (N ) )) N ≥1 satisfies (36). We first show that the right side of (35) is a continuous map and then the result follows from an application of continuous mapping theorem. Consider, ). Now we next prove that the map W = (W i,j ) i,j is continuous. First, assume that the sequence ((x (N ) , m N )) N ≥1 converges to (x, m), then there exists a N 1 ∈ N such that sup Also, there exists a N 2 ∈ N such that sup t∈[0,T ] m (N ) (t) − m(t) 1 < /4. Second, assume that the sequence (x (N ) (0)) converges to x(0) with respect to 1 . Therefore, there exists a N 3 ∈ N such that x (N ) (0) − x(0) 1 < /4. Now we claim that there exists a N 4 ∈ N such that λ γ j max The equation (73) implies that the convergence of the sequence (( for any t ≥ 0 is 1 convergence. However, we know only the weak convergence of the sequence of measures (β (N ) ) N ≥1 , which does not directly implies (73). Therefore, we show using weak convergence of the sequence (β (N ) ) N ≥1 that (73) is indeed true in our case. Since x(0) ∈ S, there exists a m j (x(0)) for all j ∈ [M ] such that x i,j (0) < 1 for all i ≥ m j (x(0)). Furthermore, from Lemma 23 we can write Therefore, for N = max m j (x(0)), L(T, x(0)) we have Using (74) and (33) we get Also, weak convergence of (β (N ) ) N implies that Hence, using (75) and (76) This shows that the map W is continuous, which completes the proof.

G Proof of Lemma 15
To prove positive recurrent of the Markov chain U, we consider the Lyapunov function Moreover, from (43) we can write the generator G U acting on the function f for a state R ∈ Z K + as Define the set B = S ∈ Z K + : where B c is the compliment of the set B and is given by Otherwise Hence, using the Foster-Lyapunov criterion for positive recurrence from [32], we conclude that the chain U is positive recurrent if Next, we proceed to prove that the unique stationary distribution π of the chain U satisfies (44). We prove this using induction on K. First observer that π(U 1 > 0) = ν 1 /λ if the birth-death process corresponding to the component U 1 is stable. This proves the base case, i.e., K = 1. Now for the induction hypothesis assume that (44) is true for all j ∈ [K − 1]. Note that the positive recurrence of the chain U implies that Ef (U) < ∞, where the expectation is with respect to the stationary distribution π. Therefore, we can set the steady-state expected drift to 0 which gives Hence, using the induction hypothesis for all j ∈ [K − 1] in the above expression we get which completes the proof for (44). Now we show that the condition j∈[K] ν j < λ is necessary for the chain U to be positive recurrent. Suppose the chain U is positive recurrent and, therefore, it has a unique stationary measure π. From (77) it is clear that π must satisfy (44). Therefore, we can write where the last inequality follows since the chain U is positive recurrent.

H Proof of Theorem 11
Proof of Theorem 11.(ii): To prove this, we need the following lemma which extends the monotonicity of the process x (N ) for finite N to the monotonicity of the limiting process x.
Proof. First, note that for any u ∈ S, there exists a sequence u (N ) We can simply construct such a sequence by setting u . This construction also satisfies the property that if u, v ∈ S are such that u ≤ v and if the sequences (u (N ) ) N and (v (N ) ) N are constructed from their corresponding limits u and v as described above, then u (N ) ≤ v (N ) for all N .
For u ∈ S, we define v n,j (t, u) = i≥n x i,j (t, u) and v n,j (u) = i≥n u i,j for each n ≥ 1 and j ∈ [M ]. Furthermore, let v n (t, u) = j∈[M ] γ j v n,j (t, u) and v n (u) = j∈[M ] γ j v n,j (u) for each n ≥ 1 and u ∈ S. µ j γ j x n,j (t, u), ∀n ≥ 1.
In particular, we have Proof. We can write the differential form of (10) as Multiplying the above by γ j and summing first over i ≥ n and then over j ∈ [M ] we obtain (79). Equation (80) follows from (79) by using P1.
From Lemma 24 it follows that for any x(0) ∈ S and any t ≥ 0 we have where min(u, v) with u, v ∈ S is defined by taking the component-wise minimum. Hence, to prove global stability it is sufficient to show that the (component-wise) convergence x(t, x(0)) → x * holds for initial states satisfying either of the following two conditions: (i) To prove the above, we first show that for any solution x(·, x(0)) ∈ S, v n (t, x(0)) is uniformly bounded in t for all n ≥ 1. Consider the case when x(0) ≥ x * . From Lemma 24 it follows that for x(0) ≥ x * , we have x(t, x(0)) ≥ x * for all t ≥ 0. Therefore, we can write where the last equality follows from (46). Hence, from (80) we have dv 1 (t,x(0)) dt ≤ 0 from which it follows that 0 ≤ v 1 (t, x(0)) ≤ v 1 (x(0)) for all t ≥ 0. Since the sequence (v n (t, x(0))) n≥1 is non-increasing, we have 0 ≤ v n (t, x(0)) ≤ v 1 (x(0)) for all n ≥ 1 and for all t ≥ 0. This proves that v n (t, x(0)) is uniformly bounded in t for each n ≥ 1 if x(0) ≥ x * . Now consider the case x(0) ≤ x * . From Lemma 24 it follows that for x(0) ≤ x * , we have x(t, x(0)) ≤ x * for all t ≥ 0. Therefore, we have v 1 (t, x(0)) ≤ v 1 (x * ) for all t ≥ 0. This shows that the component v n (t, x(0)) is uniformly bounded in t for each n ≥ 1 for x(0) ≤ x * .
Since v n (t, x(0)) is uniformly bounded in t, the convergence x i,j (t, x(0)) → x * i,j for all i ≥ 1 and for all j ∈ [M ] will follow from for the case x(0) ≥ x * and from ∞ 0 (x * i,j − x i,j (t, x(0)))dt < ∞, j ∈ [M ], i ≥ 1, for the case x(0) ≤ x * . We now prove (83) to show convergence for the case x(0) ≥ x * ; the proof of other case follows similarly. To show (83) it is sufficient to prove that µ j γ j (x i,j (t, x(0)) − x * i,j )dt < ∞, ∀i ≥ 1.
Proof of Theorem 11.(iii): We first recall from Proposition 13 that the sequence (x (N ) (∞)) N is tight in S under the 1 -norm. Hence, by Prohorov's theorem, the sequence has convergent subsequences with limits in S. Thus, it suffices to show that all convergent subsequences has the same limit point x * . Let (x (N k ) (∞)) k be any such convergent subsequence of the sequence (x (N ) (∞)) N with limit point x * * ∈ S. Now, from Theorem 10, we have that the distribution of x * * must be invariant under the map u → x(t, u). By the global stability result proved earlier it follows that the only measure invariant under the map u → x(t, u) is δ x * . Hence, we must have x * * = x * .

I Unique Characterisation of Stationary Distribution from Given State
The main idea of the proof is to show that the transition rates of the chain (V l 1 (x),1 , V l 2 (x),2 , . . . , V l M (x),M ) defined in (42) have a form similar to that of the transition rates of the Markov chain defined in (43). The proof then follows by the application of Lemma 15.
We first reduce the dimension of the chain above and then rearrange the remaining components by performing the following steps sequentially: 1.
Step 1: We first note from (42) that the stationary rate of the transition V l j (x),j → V l j (x),j − 1 is zero (whereas the rate of the transition V l j (x),j → V l j (x),j + 1 is strictly positive) for any component j ∈ [M ] for which either (i) l j (x) > l i (x) for some i < j or (ii) l j (x) − 1 > l i (x) for some i = j. This is because for pairs i, j ∈ [M ] satisfying any of the above two conditions we have π x (V l j (x),i = ∞) = 1 and if V l j (x),i = ∞, then from the definition of R i,j we have 1 V ∈ R l j (x),j = 0. Therefore, for each j ∈ [M ] which satisfies one of the above two conditions we have π x (V l j (x),j = ∞) = 1. Hence, in the first step, we remove all these components from the chain C.

2.
Step 2: Next, we arrange the remaining components of the chain C in the increasing order of their corresponding minimum queue lengths (i.e., increasing order of l j (x)). The components having the same minimum queue length (i.e., the same value of l j (x)) are then arranged in the decreasing order of their service rates. It can then be easily verified from the definition of R i,j that the remaining components have transition rates of the form given by (43).
Let Y = (Y m 1 ,p 1 , Y m 2 ,p 2 , . . . , Y m H ,p H ) denote the chain obtained after performing the steps mentioned above, where for each i ∈ [H], Y m i ,p i is the leftover component of the chain C with minimum queue length m i in pool p i . Note that m i ≤ m i+1 and p i ≤ p i+1 for all i ∈ [H]. Moreover, the transition rate from Y m i ,p i → Y m i ,p i + 1 is given by then we have π x (V m 1 ,p 1 = ∞) = · · · = π x (V m L ,p L = ∞) = 0, π x (V m L+1 ,p L+1 = ∞) = · · · = π x (V m H ,p H = ∞) = 1.
Suppose L i=1 ρ i < 1 and L+1 i=1 ρ i ≥ 1. Now we use contradiction to prove that π x (Y m i ,p i = ∞) = 0 for all i ∈ [L]. Assume π x (Y m i ,p i = ∞) = ∈ (0, 1] for i ∈ [L]. Also, assumeπ x to be the unique stationary distribution of (Y m 1 ,p 1 , . . . , Y m i ,p i ) given that Y m r ,pr is finite for all r ∈ [i]. Note that the stationary measureπ x is same as the stationary measure π given in Lemma 15. Therefore, we can write where we useπ x (0 = Y m 1 ,p 1 = · · · = Y m i−1 ,p i−1 < Y m i ,p i ) = ν i λ from (44). Now substituting the above in the differential form of (10) we obtain where the last step follows as ν i λ < 1. Now, since x m i ,p i (t) = 1 as m i is the minimum queue length in pool p i , we must have dx m i ,p i (t) dt < 0 which leads to a contradiction. Therefore, we have π x (Y m i ,p i = ∞) = 0 for all i ∈ [L]. Now observe that L+1 i=1 ρ i ≥ 1 implies ρ L+1 ≥ 1 − L i=1 ρ i . Therefore, using Lemma 15, we know that the chain (Y m 1 ,p 1 , . . . , Y m L+1 ,p L+1 ) is unstable. Moreover, again from Lemma 15, L i=1 ρ i < 1 insures that the chain (Y m 1 ,p 1 , . . . , Y m L ,p L ) is stable. Hence, we haveπ x (Y m L+1 ,p L+1 ≥ l) = 1 for all l ≥ 0. This shows that π x (Y m L+1 ,p L+1 = ∞) = 1. Now observe that the rate of transition from Y m i ,p i → Y m i ,p i − 1 is λ1 0 = Y m 1 ,p 1 = · · · = Y m i−1 ,p i−1 < Y m i ,p i = 0 for each i ∈ {L + 2, . . . , H}. Hence, with only non-zero rate of transition from Y m i ,p i → Y m i ,p i + 1 we have π x (Y m i ,p i = ∞) = 1 for each i ∈ {L + 2, . . . , H}.