HULA: Scalable Load Balancing Using Programmable Data Planes

一 文章概述

这篇文章针对当前multi-rooted拓扑结构的数据中心网络（leaf-spine，Fat Tree）中带宽使用效率问题，提出了一种在可编程数据层面实现的基于拥塞感知的分布式的流量均衡策略。这个策略就是每个交换机上维护一个包含nexthop和带宽使用率的表，作为报文路由的依据，策略执行过程主要有两个部分，首先是表的更新，此时通过周期性probe报文的反向传输，来更新每一个交换机上的Path Util Table。然后是实际报文正向传输时，依据表中的nexthop来路由发送，同时将flow的粒度细分为flowlet进行路由。Probe报文可以将整个链路上的使用率信息传递到每个交换机，同时也可以检测到故障链路。
本文提出的方法有下面优点：
1.交换机不需要记录到达某个TOR交换机的整个路径的信息，而是每个交换机只保存最优路径的相邻交换机，有利于均衡策略的可扩展性
2.使用P4可编程语言实现，不需要定制相关功能硬件

二 这篇文章主要贡献

文章主要贡献主要有以下两点：
1.第一个在可编程交换机上提出了HULA，一种可扩展的数据层面负载均衡策略
2.在NS-2上实现了HULA并与最新的策略做了对比

三 回答四个问题

1 该文章解决的核心问题？前人使用的方法为什么不能解决本文提出的问题，困难在哪？本文提出的方法为什么能够有效解决这些问题？

• 该文章解决的核心问题
  这篇文章解决的是数据中心网络中一个传统问题——流量负载均衡问题。背景是目前的数据中心采用的multi-rooted拓扑架构中，TOR交换机之间通信时存在的链路带宽使用不均衡的问题。
• 前人使用方法的问题，以及困难
  对于网络流量均衡问题作者在最后的related work里面都进行了列举。这里主要介绍一下和本文最相近的两个策略，以及存在的问题。
  1.ECMP（equal-cost multiple-path routing）,没有感知拥塞信息，直接选择平均传播，导致网络中出现故障变成非对称网络来说会严重不均衡。
  2.CONGA 需要专门的硬件支持，开发周期长，一旦实现无法修改.另外CONGA需要在叶节点交换机维护每个路径的拥塞状况，交换机存储有限，导致扩展不了，只适合two-tier Leaf-Spine拓扑结构。
• 本文方法为什么有效解决了这个问题
  本文方法在数据层通过可编程交换机感知链路的拥塞信息。同时每个交换机只维护最好路径的下一条nexthop以及对应的链路使用率，从而不用保存所有链路拥塞信息，减少了算法的内存使用量。
  另外本文使用了可编程交换机，从而解决了需要定制硬件的问题。

2 该核心问题的解决带来了什么冲击？正负面都有哪些影响？

• 正面影响
  之前的许多流量负载均衡都是中心化的，控制层的，会导致调度延迟很低，后面开始有在数据层做流量负载均衡（CONGA），但是存在硬件定制问题以及硬件存储资源紧缺问题。本文首先在数据层做，同时做的分布式的方法，并且在可编程交换机上做。从而改善了前面提到的调度方法的局限性。
• 负面影响
  通过额外的probe报文更新路由表项，增加了网络负载，另外如何调节好probe发送频率等等都是一些需要讨论的问题

3 作者如何进行验证？数学推导还是实验测试？是否完备？如果你进行验证，你会采取什么办法？如果你的方法和本文不一样，思考作者为什么不采用你想的方法？采用你想的方法，会有什么困难？如果你用文中方法，你回遇到什么困难？

• 作者采用实验测试的方法进行了验证。使用的workload是两种应用的数据Web-search和Data-mining（此处只说明了workload是“obtained from production datacenters”没有引用，另外对于报文的到达率也只是说付出一个指数分布，也没有引用）。主要做了以下实验：
  1.分析了两种应用中流量大小的分布情况，得出了小报文占大多数的结论。
  2.在对称网络结构下，两种应用在不同算法（HULA CONGA ECMP）下随着负载增加，平均流完成时间（FCT）的变化的比较。得出结论HULA > CONGA > ECMP
  3.非对称网络结构下，不同算法的FCT比较
  4.除了测试了平均FCT，还测试了尾延迟，就是那些完成时间最长的流的FCT
  5.测试了队列增长趋势，就是将某个链路断开来使得某个链路拥塞。然后观察这个拥塞链路的报文队列长度。
  6.测试了稳定性，将链路断开然后再连接之后观察每个链路的使用情况。结论是，可以很好的适应链路故障。
  7.测试了不同probe频率的FCT的变化
• 目前感觉作者验证的指标很完善，但是可能由于没有硬件，所以使用NS2进行模拟，另外模拟的架构也是最为简单的。如果要做硬件真实仿真，那需要多个交换机与服务器，这种环境比较难搭建
• 用文中的测试方法，我感觉到的困难时，FCT具体怎么去测？,这个后面回去研究以下

4 找本文不完善的地方，是否还有可改进的空间？

个人感觉本文不完善的地方主要有以下几点：
1.文章提出的方法，主要是两个部分，我这里概括为前后台。后台是不断发送的probe，来检测网络状态并更新交换机中的路由表，前台读取路由表，按照指导进行寻路。
这种方法给网络增加了额外流量，尽管文中作者分析了占用流量不大，得出的结论是probe发送频率为1ms时，负载只有1.28%，但是真实实验时使用的probe发送频率变成了200微秒，也就是0.2ms，那按照上面计算大概是5倍，当然作者最后说了probe频率对效果影响不明显（所以这个问题其实作者回答的还是比较好的）
2.实验部分，对于workload的介绍有，但是有一些细节就简单糊弄过去了，关键是没有引用，包括workload的出处，以及报文到达率的设置，这导致结果不是很可信
3.使用NS2模拟实现的，真机如果能实现更好