Impact of fairness and heterogeneity on delays in large-scale centralized content delivery systems

Virag Shah () and Gustavo Veciana ()
Additional contact information
Virag Shah: The University of Texas at Austin
Gustavo Veciana: The University of Texas at Austin

Queueing Systems: Theory and Applications, 2016, vol. 83, issue 3, No 7, 397 pages

Abstract: Abstract We consider multiclass queueing systems where the per class service rates depend on the network state, fairness criterion, and is constrained to be in a symmetric polymatroid capacity region. We develop new comparison results leading to explicit bounds on the mean service time under various fairness criteria and possibly heterogeneous loads. We then study large-scale systems with a growing number of service classes n (for example, files), $$m = \left\lceil {bn} \right\rceil $$ m = b n heterogenous servers with total service rate $$\xi m$$ ξ m , and polymatroid capacity resulting from a random bipartite graph $${\mathcal {G}}^{(n)}$$ G ( n ) modeling service availability (for example, placement of files across servers). This models, for example, content delivery systems supporting pooling of server resources, i.e., parallel servicing of a download request from multiple servers. For an appropriate asymptotic regime, we show that the system’s capacity region is uniformly close to a symmetric polymatroid—heterogeneity in servers’ capacity and file placement disappears. Combining our comparison results and the asymptotic ‘symmetry’ in large systems, we show that large randomly configured systems with a logarithmic number of file copies are robust to substantial load and server heterogeneities for a class of fairness criteria. If each class can be served by $$c_n=\omega (\log n)$$ c n = ω ( log n ) servers, the load per class does not exceed $$\theta _n=o\left( \min (\frac{n}{\log n}, c_n)\right) $$ θ n = o min ( n log n , c n ) , mean service requirement of a job is $$\nu $$ ν , and average server utilization is bounded by $$\gamma 1$$ δ > 1 , the conditional expectation of delay of a typical job with respect to the $$\sigma $$ σ -algebra generated by $${\mathcal {G}}^{(n)}$$ G ( n ) satisfies the following: $$\begin{aligned} \lim _{n\rightarrow \infty } P\left( E[D^{(n)}|{\mathcal {G}}^{(n)}] \le \delta \frac{ \nu }{ \xi c_n} \frac{1}{\gamma }\log \left( \frac{1}{1-\gamma }\right) \right) = 1. \end{aligned}$$ lim n → ∞ P E [ D ( n ) | G ( n ) ] ≤ δ ν ξ c n 1 γ log 1 1 - γ = 1 .

Keywords: Delays; Fairness; Heterogeneity; Robustness; Queueing; Asymptotic symmetry; Content delivery systems; Primary 68M20; Secondary 60K30 (search for similar items in EconPapers)
Date: 2016
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s11134-016-9491-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:queues:v:83:y:2016:i:3:d:10.1007_s11134-016-9491-0

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/11134/

DOI: 10.1007/s11134-016-9491-0

Access Statistics for this article

Queueing Systems: Theory and Applications is currently edited by Sergey Foss

More articles in Queueing Systems: Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().