We consider a system with n unit-rate servers where jobs arrive according a Poisson process with rate nλ (λ<1). In the standard Power-of-d or Pod scheme with d≥2, for each incoming job, a dispatcher samples d servers uniformly at random and sends the incoming job to the least loaded of the d sampled servers. However, in practice, load comparisons may not always be accurate. In this paper, we analyze the effects of noisy load comparisons on the performance of the Pod scheme. To test the robustness of the Pod scheme against load comparison errors, we assume an adversarial setting where, in the event of an error, the adversary assigns the incoming job to the worst possible server, i.e., the server with the maximum load among the d sampled servers. We consider two error models: load-dependent and load-independent errors. In the load-dependent error model, the adversary has limited power in that it is able to cause an error with probability ϵ∈[0,1] only when the difference in the minimum and the maximum queue lengths of the d sampled servers is bounded by a constant threshold g≥0. For this type of errors, we show that, in the large system limit, the benefits of the Pod scheme are retained even if g and ϵ are arbitrarily large as long as the system is heavily loaded, i.e., λ is close to 1. In the load-independent error model, the adversary is assumed to be more powerful in that it can cause an error with probability ϵ independent of the loads of the sampled servers. For this model, we show that the performance benefits of the Pod scheme are retained only if ϵ≤1/d; for ϵ>1/d we show that the stability region of the system reduces and the system performs poorly in comparison to the random scheme. Our mean-field analysis uses a new approach to characterise fixed points which neither have closed form solutions nor admit any recursion. Furthermore, we develop a generic approach to prove tightness and stability for any state-dependent load balancing scheme.

We consider a system with n unit-rate servers where jobs arrive according a Poisson process with rate nλ (λ < 1). In the standard Power-of-two or Po2 scheme, for each incoming job, a job dispatcher samples two servers uniformly at random and sends the incoming job to the least loaded of the two sampled servers. However, in practice, the load information may not be accurate at the job dispatcher. In this paper, we analyze the effects of erroneous load comparisons on the performance of the Po2 scheme. Specifically, we consider load-dependent and load-independent errors. In the load-dependent error model, an incoming job is sent to the server with the larger queue length among the two sampled servers with an error probability ε if the difference in the queue lengths of the two sampled servers is less than or equal to a constant g; no error is made if the queue-length difference is higher than g. For this type of errors, we show that, in the large system limit, the benefits of the Po2 scheme are retained for all values of g and ε as long as the system is heavily loaded, i.e., λ is close to 1. In the load-independent error model, the incoming job is sent to the sampled server with the maximum load with an error probability of ε independent of the loads of the sampled servers. For this model, we show that the performance benefits of the Po2 scheme are retained only if ε ≤ 1/2; for ε > 1/2 we show that the stability region of the system reduces and the system performs poorly in comparison to the random scheme. To prove our stability results, we develop a generic approach to bound the drifts of Lyapunov functions for any state-dependent load balancing scheme. Furthermore, the mean-field analysis in our paper uses a new approach to characterise fixed points which do not admit a recursion.

A fundamental problem in large-scale data centers is to reduce the average response time of jobs. The Join-the-Shortest-Queue (JSQ) load balancing scheme is known to minimise the average response time of jobs for homogeneous systems consisting of identical servers. However, heterogeneous systems consisting of servers with different speeds, JSQ performs poorly. Furthermore, JSQ suffers from high communication overhead as it requires knowledge of the queue length of all servers while assigning incoming jobs to one of the destination servers. Therefore, the Join-the-Idle-Queue (JIQ) scheme was introduced which not only reduces the communication overhead but also minimises the average response time of jobs under homogeneous systems. Despite these advantages, JIQ is still known to be inefficient in minimising the average response time of jobs under heterogeneous systems. In this paper, we consider a speed-aware version of JIQ for heterogeneous systems and show that it achieves delay optimality in the fluid limit. One of the technical challenges to establishing this optimality is to show the tightness of the sequence of steady-state distributions indexed by system size. We show this tightness result by evaluating the drift of appropriate Lyapunov functions. This approach to proving tightness is different from the usual coupling approach used for homogeneous systems. Another important challenge in proving the optimality result is to establish the fluid limit which is done using the time-scale separation technique. Finally, using the monotonicity of the fluid process we have shown that the fluid limit has a unique and globally attractive fixed point.

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.

We consider the status updates of a physical process over an unreliable channel. In this setting, one may not be able to reliably transmit the current state at all times. Instead, one is interested in the timeliness of the accurately received information. This is a setting for several cyber-physical system applications that require real-time monitoring and control. In this paper, we study periodic data transmission schemes at a single source which exploit the temporal correlation in the source messages. When the source has no feedback, it can periodically send the actual information, interspersed with differential messages. On the availability of receiver's feedback at the source, it can decide to send either the differential or the actual information at each transmission opportunity. For a fixed length coding, we show that the differential encoding improves the timeliness performance only if the receiver's feedback is available.

For timely sensor update, the traditional approach is to send new information at every available opportunity. Recent research has shown that with limited receiver feedback, sensors can improve the update timeliness by transmitting differential information for slowly varying correlated sources. One can elect to transmit either the actual or the differential state information based on a differential encoding threshold for a general Markov source. This threshold captures the natural trade-off between differential transmission opportunities and the coding gains. Using matrix-geometric method, we find the limiting age distribution for a Markov source as a function of the encoding threshold, from which several other performance metrics of interest, such as mean age, peak age, and the probability of decoding failure can be derived.

For timely sensor update, the traditional approach is to send new information at every available opportunity. Recent research has shown that with limited receiver feedback, sensors can improve the update timeliness by transmitting differential information for slowly varying correlated sources. In general, correlated sources can elect to transmit actual or differential state information depending on the current state. This encoding scheme generalizes the actual and differential updates schemes. Using this generalized scheme, we quantify the timeliness gains for some example sources. Further, we show a stochastic ordering among the actual update, the differential update, and the generalized update schemes.

For many applications in sensor networks and cyber-physical systems, receiving timely information is of utmost importance. In this article, we study data transmission schemes for a single source, sending periodic updates to a receiver through an unreliable channel. We consider two schemes that exploit the temporal correlation in the source messages, to send differential information to the receiver. Taking advantage of the receiver feedback in the first scheme, the source can decide between the differential and the actual information, to be sent at each transmission opportunity. Contrastingly, in the second scheme without any feedback, the source periodically sends the actual information, interspersed with differential messages. We observe that the differential encoding improves the timeliness performance, only if the receiver feedback is available.