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

摘要

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 = [bn] heterogenous servers with total service rate ξm, and polymatroid capacity resulting from a random bipartite graph 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 = ω(log n) servers, the load per class does not exceed θ_n = o (min(n/log n, c_n)), mean service requirement of a job is v, and average server utilization is bounded by γ ＜ 1, then for each constant δ ＞ 1, the conditional expectation of delay of a typical job with respect to the σ -algebra generated by G~(n) satisfies the following: lim n→∞ P(E[D~(n)|G~(n)] ≤ δ v/ξc_n 1/γ log(1/1－γ)) = 1.