对于一个Hadoop控制器，一个job控制器会把它分成m个规模类似的task，交给不同的物理节点(node)去执行，每个节点可以执行任意多（或不执行）task。总共有n个不同的物理节点。
现在需要一个策略，把这m个task，分给不同的节点，确定每个节点分配到多少个不同的task。这个过程叫做scheduling
这些task依赖的数据，存在某些node上。因此这些node，执行完一个task的时间就会比较短$C_{loc}$, 其它结点执行完的一个task时间$C_{rem}$就会更长（因为要把原来节点的数据复制过来）
基于上述原因，之前的调度算法（文献详见hadoop scheduling algorithms，其中除了BAR和SDN那篇之外都是综述），主要的目的有：
- 使得schedule的方案中，最后一个task执行完的时间最短(Minimum span problem, NP)，于是就有了很多启发式的方法，例如BAR
- 使得平均完成时间最短
- Energy-saving
- 如果每个node的计算能力不等价该怎么搞（heterogeneous）
但是，它们都没有考虑到一个问题：网络情况。例如一个link的bandwidth是有限的，那么某种数据搬移都集中在这条link上的schedule就不太有效（迁移时间=数据总量 / BW）。基于这个原因，有人提出利用SDN监测带宽来进行调度（hadoop scheduling algorithms， Bandwidth-Aware Scheduling With SDN in Hadoop: A New Trend for Big Data）。其在schedule的时候探测一下每个link的剩余带宽，使得这个schedule在迁移数据时不会超过link的bandwidth，而且尽量利用带宽更大的路径。
其算法大致是：
When job comes:
Use current bandwidth to calculate residue time between nodes
assign tasks so that Min { Max{ Finish_time(node[i]) } }
而$finish_time = computation_time + data_movement_time = \ computation_time + data_size / \min{link_bandwidth_from_source_to_dest}$ 用了一个类似贪心的方法动态调整schedule。
但是，这样有一些问题：
- 每次只会选取bandwidth较多的一个node, 即使这个会造成bottleneck, 使得整体的完成时间增大
- 只考虑了一个task自身的影响，而没有考虑到task之间的相互作用
这些问题其实都是SDN QoS routing中的问题，可以见上周的slides
能不能将这些routing algorithm中考虑到的全局最优性融入schedule算法中？