单包缓冲让无遗憾学习撑起排队网络:多队列稳定所需超额容量被精确刻画
核心概要
在服务器只保留一个数据包缓冲的排队系统中,每个队列各自运行现成的无遗憾学习算法、不协调也不预知服务率。分析表明,单队列的长期吞吐至少等于各服务率的 Hamacher 和,且该界是紧的;多队列系统在到达率上界为 λ 时,稳定所需的超额容量因子恰为 1/(1-λ),在 λ=1/2 处把此前 2 到 4 的区间收紧为 2,并随 λ 趋小而趋近 1。
深度剖析
服务器带一个数据包缓冲后,单个队列即使只跑现成的无遗憾学习算法,也能同时利用多台服务器的服务能力,而不再只能锁定一台最好的服务器。 此前的无缓冲模型里,数据包只能在发出的那一步被处理,队列要稳定就必须存在单台服务率高于到达率的服务器,问题退化为找出最好的那台。 分析给出:任意无遗憾学习算法的长期平均吞吐至少为各服务率的 Hamacher 和,即总几率除以一加总几率,并证明该下界可由按几率比例抽样的平稳策略取到。
多队列竞争带缓冲服务器时,稳定所需的额外服务容量有了精确值,而不是一个区间。 此前在到达率上界为 1/2 时,已知的超额容量因子只被夹在 2 与 4 之间。 当每个队列到达率不超过 λ 时,超额容量因子 1/(1-λ) 在高概率无遗憾学习下既充分又必要;λ=1/2 时该值为 2,与已有下界吻合,λ 趋小时趋近 1。
这一保证不依赖服务器在同轮到达的多个数据包之间如何取舍。 稳定性结论对任意服务器优先级规则都成立。 与之匹配的单队列反例中不存在相互竞争的数据包,因此仅改变优先级无法降低最坏情形所需的超额容量。
启示与展望
结论建立在每台服务器仅容纳一个数据包的排队模型上,队列使用满足无遗憾性质的学习算法,多队列结果要求高概率无遗憾;单队列仿真使用 EXP3,在三臂与七臂两组服务率上运行。
多队列的紧性由单队列反例给出,该反例中没有相互竞争的数据包;所需超额容量随缓冲大小、网络拓扑以及队列可获得的反馈如何变化,仍是待研究的问题。
