核心思想
实现不同特征workload下的adaptive scheduling, 而以前的调度策略只针对特定特征的workload.
2D指的是 multiplexing (比如fair sharing) 和 serialization (比如FIFO SRPT).
Observations and Insights
-
Within-workload variability 和 Across-workload variability 都存在.
-
对于同一个workload, 没有一个单一的最优策略: Cache workload, FIFO tail表现最优但是mean能比平均情况差3.5倍 （论文给了quantify的实验结果）
-
对于不同workload, 没有一个单一的使得Tail FCT最优的策略: FIFO在heavy-tailed的workload（data-mining）下比最优的差3倍. (PS指fair sharing)
2D的设计目标
对于tail FCT, 要至少和FIFO (light-tailed的workload) 或 PS (heavy-tailed的workload)一样好; 对于 low percentile 和 mean FCT, 接近SRPT
Multiplexing 和 Serialization: 两个重要的building block
multiplexing能够有效减少队头阻塞(FIFO有)和饿死问题(SRPT有), 但是对于similar size的流, multiplexing会导致这些流完成时间全部增加!
因此得出了两个重要的设计原则：multiplexing应该只在不同size的流之间进行, serialization应该在相同size之间的流进行!
2D design
- Intra-class scheduling: serialization采用FIFO, 原因是对于similar size的job, FIFO以证明是mean和tail最优的, 并且不需要preemption (有flow switch overhead), 利于做batching等优化
- Inter-class scheduling: 采用multiplex, bandwidth sharing
2D design 两个挑战
确定区分class的threshold（intra-class的size要接近）以及如何为不同的class 分配rate.
- 确定区分class的threshold（intra-class的size要接近）：拆成两个子问题：分成几个class, 然后再确定threshold. 使用 Squared Coefficient of Variation作为量化一个class variability的metric, 目标是使每个class 这个值小于等于1.（已被证明在这种情况下FIFO tail FCT最优），而且这个算法能自动算出需要的class数目
- class rate：每个class按照流的数目成比例分。。。。比较简单
Implementation and evaluation
- hybrid的方式. controller 在loose的timescale上计算threshold和rate, 不在 critical path上（跟Auto有些像）. end host: 2D transport, 需要在每个class内enforce FIFO顺序以及 rate. sequencer: 负责 global FIFO order. 只有到了顺序才发到传输层. 还需要知道的一个信息是最新的要完成的流是哪个, 论文里提出了采用多种方式可以获得这一信息, 比如集中式: 一个sequencer进行track; 分布式: end point 根据大致的gap估计; hybrid:一个将要完成的流可以把自己的id广播。还有一些专门针对小流的优化(batch local sequencing multiplex等)
- Testbed(18 client 1 server 1 controller 1 sequencer).实验对比主要是与3个调度原则（FIFO PS 非抢占SJF）和 3个启发式调度策略（Barrat的FIFO-LM、Aalo的D-CLAS、PIAS）对比. metric: p50 p90 P99 P99.5
- 4种workload（web-search data-mining uniform cache）以及动态变化的workload：workload随时间变化、mixed的workload
可能存在问题
需要提前知道size 信息; class划分至少需要3000 flow作为sample 对于某些class occupancy低的情况不友好（更长时间收敛）
