动态分配有限资源,兼顾多地点多服务类的公平与效率。
Adaptive Two-Level Allocation of a Conserved Capacity Budget Across Locations and Service Classes

- 分两层分配:先类内按需求差额调节,再跨类弹性借贷盈余
- 在8个场景中保障66%-93%高优先级请求,不浪费也不超配
- 适合应对突发流量的系统设计,尤其对内容分发网络有参考价值
研究在需求不均、时变且可能超出供给的情况下,如何将单一受限容量预算在多个位置和两类服务间分配。典型场景包括:源节点请求速率上限在边缘位置的分配、优质与普通租户的带宽限制、低延迟与批量任务间的出口带宽划分。提出一种两级算法:第一级在同类内根据需求短缺与过剩按比例重新分配容量;第二级在类别间弹性借调,当一类有盈余而另一类缺时进行转移。证明该算法严格守恒预算、保持非负性,并在稳态需求下单轮迭代即达稳定分配,每轮计算复杂度为O(KN),其中K为类别数,N为位置数。评估其在抵御体积型攻击的CDN场景下的表现,两类分别为已确认合法与待验证流量。在22个节点拓扑的8种竞争场景中,成功服务66%-93%高优先级需求,性能接近单类别线性规划最优解,且在总需求满足或超过预算时从不闲置容量或超承诺。两个发现具普适意义:一、在竞争环境下最大化总吞吐量目标错误——两类别线性规划虽提升总量却降低高优先级服务量;二、跨类借贷在突发负载下可提升高优先级服务1.5个百分点(消融实验确认),而在平稳负载下无影响。5个节点原型使用真实HTTP流量验证了整个流程的有效性。
原文摘要 · Abstract (English)
We study how to share a single conserved capacity budget across many locations and two service classes when demand is uneven, time-varying, and can exceed supply. The shape recurs: an origin's request-rate cap split across its edge locations, a licensed throughput cap across premium and standard tenants, or an egress budget between latency-critical and batch workloads. We present a two-level algorithm. The first level redistributes capacity within a class across locations by proportional deficit and excess redistribution; the second lends capacity elastically between classes when one has surplus and the other deficit. We prove it conserves the budget exactly, preserves non-negativity, and reaches a stable allocation in one iteration under stationary demand because it carries no per-cycle state, at O(KN) cost per cycle for K classes and N locations. We evaluate it defending a CDN's per-domain budget under volumetric attack, where the classes are confirmed-legitimate and not-yet-cleared traffic; across 8 contention scenarios on a 22-location topology it serves 66-93% of high-priority demand, competitive with a single-class linear-programming optimum, while never leaving capacity idle or over-committing whenever aggregate demand meets or exceeds the budget (the contention regime these scenarios evaluate). Two findings carry beyond the application. First, a throughput-maximizing objective is wrong under contention: a two-class LP maximizing total served load serves less high-priority load than our demand-proportional, reservation-respecting allocator in most scenarios, because it cannot tell that some load it serves is the contention. Second, inter-class borrowing earns its complexity under bursty load, improving high-priority service by 1.5 points (isolated by ablation), and is neutral under stationary demand. A 5-location prototype with real HTTP traffic validates the pipeline.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。