Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userComplete resource pooling of a load balancing policy for a network of battery swapping stations
421
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
To reduce carbon emission in the transportation sector, there is currently a steady move taking place to an electrified transportation system. This brings about various issues for which a promising solution involves the construction and operation of a battery swapping infrastructure rather than in-vehicle charging of batteries. In this paper, we study a closed Markovian queueing network that allows for spare batteries under a dynamic arrival policy. We propose a provisioning rule for the capacity levels and show that these lead to near-optimal resource utilization, while guaranteeing good quality-of-service levels for Electric Vehicle (EV) users. Key in the derivations is to prove a state-space collapse result, which in turn implies that performance levels are as good as if there would have been a single station with an aggregated number of resources, thus achieving complete resource pooling.
rate research
Read More
Randomized load balancing networks arise in a variety of applications, and allow for efficient sharing of resources, while being relatively easy to implement. We consider a network of parallel queues in which incoming jobs with independent and identically distributed service times are assigned to the shortest queue among a randomly chosen subset of $d$ queues, and leave the network on completion of service. Prior work on dynamical properties of this model has focused on the case of exponential service distributions. In this work, we analyze the more realistic case of general service distributions. We first introduce a novel particle representation of the state of the network, and characterize the state dynamics via a sequence of interacting measure-valued stochastic processes. Under mild assumptions, we show that the sequence of scaled state processes converges, as the number of servers goes to infinity, to a hydrodynamic limit that is characterized as the unique solution to a countable system of coupled deterministic measure-valued equations. We also establish a propagation of chaos result that shows that finite collections of queues are asymptotically independent. The general framework developed here is potentially useful for analyzing a larger class of models arising in diverse fields including biology and materials science.
The recently created IETF 6TiSCH working group combines the high reliability and low-energy consumption of IEEE 802.15.4e Time Slotted Channel Hopping with IPv6 for industrial Internet of Things. We propose a distributed link scheduling algorithm, called Local Voting, for 6TiSCH networks that adapts the schedule to the network conditions. The algorithm tries to equalize the link load (defined as the ratio of the queue length over the number of allocated cells) through cell reallocation. Local Voting calculates the number of cells to be added or released by the 6TiSCH Operation Sublayer (6top). Compared to a representative algorithm from the literature, Local Voting provides simultaneously high reliability and low end-to-end latency while consuming significantly less energy. Its performance has been examined and compared to On-the-fly algorithm in 6TiSCH simulator by modeling an industrial environment with 50 sensors.
In this note, we apply Steins method to analyze the performance of general load balancing schemes in the many-server heavy-traffic regime. In particular, consider a load balancing system of $N$ servers and the distance of arrival rate to the capacity region is given by $N^{1-alpha}$ with $alpha > 1$. We are interested in the performance as $N$ goes to infinity under a large class of policies. We establish different asymptotics under different scalings and conditions. Specifically, (i) If the second moments linearly increase with $N$ with coefficients $sigma_a^2$ and $ u_s^2$, then for any $alpha > 4$, the distribution of the sum queue length scaled by $N^{-alpha}$ converges to an exponential random variable with mean $frac{sigma_a^2 + u_s^2}{2}$. (3) If the second moments quadratically increase with $N$ with coefficients $tilde{sigma}_a^2$ and $tilde{ u}_s^2$, then for any $alpha > 3$, the distribution of the sum queue length scaled by $N^{-alpha-1}$ converges to an exponential random variable with mean $frac{tilde{sigma}_a^2 + tilde{ u}_s^2}{2}$. Both results are simple applications of our previously developed framework of Steins method for heavy-traffic analysis in cite{zhou2020note}.
This paper considers the steady-state performance of load balancing algorithms in a many-server system with distributed queues. The system has $N$ servers, and each server maintains a local queue with buffer size $b-1,$ i.e. a server can hold at most one job in service and $b-1$ jobs in the queue. Jobs in the same queue are served according to the first-in-first-out (FIFO) order. The system is operated in a heavy-traffic regime such that the workload per server is $lambda = 1 - N^{-alpha}$ for $0.5leq alpha<1.$ We identify a set of algorithms such that the steady-state queues have the following universal scaling, where {em universal} means that it holds for any $alphain[0.5,1)$: (i) the number of of busy servers is $lambda N-o(1);$ and (ii) the number of servers with two jobs (one in service and one in queue) is $O(N^{alpha}log N);$ and (iii) the number of servers with more than two jobs is $Oleft(frac{1}{N^{r(1-alpha)-1}}right),$ where $r$ can be any positive integer independent of $N.$ The set of load balancing algorithms that satisfy the sufficient condition includes join-the-shortest-queue (JSQ), idle-one-first (I1F), and power-of-$d$-choices (Po$d$) with $dgeq N^alphalog^2 N.$ We further argue that the waiting time of such an algorithm is near optimal order-wise.
Randomized load-balancing algorithms play an important role in improving performance in large-scale networks at relatively low computational cost. A common model of such a system is a network of $N$ parallel queues in which incoming jobs with independent and identically distributed service times are routed on arrival using the join-the-shortest-of-$d$-queues routing algorithm. Under fairly general conditions, it was shown by Aghajani and Ramanan that as $Nrightarrowinfty$, the state dynamics converges to the unique solution of a countable system of coupled deterministic measure-valued equations called the hydrodynamic equations. In this article, a characterization of invariant states of these hydrodynamic equations is obtained and, when $d=2$, used to construct a numerical algorithm to compute the queue length distribution and mean virtual waiting time in the invariant state. Additionally, it is also shown that under a suitable tail condition on the service distribution, the queue length distribution of the invariant state exhibits a doubly exponential tail decay, thus demonstrating a vast improvement in performance over the case $d=1$, which corresponds to random routing, when the tail decay could even be polynomial. Furthermore, numerical evidence is provided to support the conjecture that the invariant state is the limit of the steady-state distributions of the $N$-server models. The proof methodology, which entails analysis of a coupled system of measure-valued equations, can potentially be applied to other many-server systems with general service distributions, where measure-valued representations are useful.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
