论文标题
D负载平衡系统的大规模和关键功率的平均等待时间
Mean Waiting Time in Large-Scale and Critically Loaded Power of d Load Balancing Systems
论文作者
论文摘要
平均现场模型是用于分析负载平衡策略的流行工具。在某些情况下，平均场限制的等待时间分布具有明确的形式。在其他情况下，可以将其计算为一组微分方程的解决方案。在这里，我们研究了平均等待时间$ e [w_λ] $的限制，因为到达率$λ$接近$ 1 $的$ 1 $，当工作尺寸指数级（平均$ 1 $）时，许多负载平衡策略（即系统接近不稳定）。由于$ e [w_λ] $偏向无穷大，我们用$ - \ log（1-λ）$扩展，并提出一种计算限制$ \ lim_ {λ\ rightArrow 1^ - }的方法，e [w_λ]/\ log（1-λ）$。对于考虑的负载平衡算法，此限制具有令人惊讶的简单形式。我们提出了一个总体结果，该结果适用于相关的微分方程满足假设列表的任何策略。对于LL（d）策略，将传入的作业分配给服务器的服务器最少，在随机选择的服务器中剩下的最少工作，这些假设经过了仔细的验证。对于此策略，我们证明限制由$ \ frac {1} {D-1} $给出。我们进一步表明，LL（d，k）策略将$ k $作业分配给$ k $最少的服务器之间的d随机选择的服务器，满足假设，限制等于$ \ frac {k} {k} {d-k} $。对于使用概率$ p_i $应用LL（$ D_I $）的策略，我们表明限制由$ \ frac {1} {\ sum_ip_ip_id_i-1} $给出。我们进一步指出，我们的主要结果也可以用于具有冗余或内存的负载平衡器。此外，我们提出了一个替代缩放$ - \ log（p_λ）$，而不是$ - \ log（1-λ）$，其中限制$ \ lim_ {λ\ rightArrow 0^+} - e [w_λ]/\ log（p_λ）$已很好地定义和非定义（与$ \ lim \ lim_/lim_/lim_/λ相反） 0^+} - e [w_λ] / \ log（1-λ）$），而$ \ lim_ {λ\ rightarrow 1^ - } \ log（1-λ） / \ log（p_λ）= 1 $。
Mean field models are a popular tool used to analyse load balancing policies. In some cases the waiting time distribution of the mean field limit has an explicit form. In other cases it can be computed as the solution of a set of differential equations. Here we study the limit of the mean waiting time $E[W_λ]$ as the arrival rate $λ$ approaches $1$ for a number of load balancing policies when job sizes are exponential with mean $1$ (i.e. the system gets close to instability). As $E[W_λ]$ diverges to infinity, we scale with $-\log(1-λ)$ and present a method to compute the limit $\lim_{λ\rightarrow 1^-}-E[W_λ]/\log(1-λ)$. This limit has a surprisingly simple form for the load balancing algorithms considered. We present a general result that holds for any policy for which the associated differential equation satisfies a list of assumptions. For the LL(d) policy which assigns an incoming job to a server with the least work left among d randomly selected servers these assumptions are trivially verified. For this policy we prove the limit is given by $\frac{1}{d-1}$. We further show that the LL(d,K) policy, which assigns batches of $K$ jobs to the $K$ least loaded servers among d randomly selected servers, satisfies the assumptions and the limit is equal to $\frac{K}{d-K}$. For a policy which applies LL($d_i$) with probability $p_i$, we show that the limit is given by $\frac{1}{\sum_ip_id_i-1}$. We further indicate that our main result can also be used for load balancers with redundancy or memory. In addition, we propose an alternate scaling $-\log(p_λ)$ instead of $-\log(1-λ)$, for which the limit $\lim_{λ\rightarrow 0^+}-E[W_λ]/\log(p_λ)$ is well defined and non-zero (contrary to $\lim_{λ\rightarrow 0^+}-E[W_λ]/\log(1-λ)$), while $\lim_{λ\rightarrow 1^-}\log(1-λ) / \log(p_λ)=1$.
