Fat tree 拓扑网络路由优化问题(一)

Fat Tree结构上两种传统路由算法的介绍

项目简介

近几个月来,一直跟随魏文婷和郑丹阳博士一起探索Fat Tree拓扑网络的路由优化问题。他们提出了一种有别于传统论文的全新路由手段,目前在静态路由问题上已经普遍超越了传统两种算法,预计还需几个月可以发表论文。这里先开个坑,介绍一下 Fat Tree 以及两种传统的算法。等论文发表后再回来把坑填上,介绍一下我们算法的具体细节。

Fat-tee

Fat tree 是一种常见的通信拓扑逻辑,有三层的拓扑结构,分别为Core层,Aggregation层和Edge层。以4-Fat-Tree和6-Fat-Tree为例,其结构图分别如下:

不看发现,该拓扑结构具有如下特性:

  - 每一个pod包含$(\frac {k}{2})^2$个server以及两层分别由$\frac {k}{2}$组成的K-port switch
  - 每个edge switch分别连接了$\frac {k}{2}$个server以及$\frac {k}{2}$个aggr.switch
  - 每一个aggr.switch连接了$\frac {k}{2}$个edge switch和core switch
  - 共有$(\frac {k}{2})^2$个core switch,每一个分别与k个pod相连。

目前Fat tree结构凭借其可扩展的路由以及“switch only”的拓扑结构等优秀特性,被广泛应用于实际中。

本次实验要解决的问题

Fat tree只是一个静态的拓扑结构,而利用该结构进行路由寻址的问题还有许多提升的空间。考虑下面一种情形:每一个最底层的server可以提供一些function,我们从某个core switch出发,在一定CPU和Bandwidth的限制下,如何以最短的代价完成所有需要被满足的function并到达目的core switch。

实验中,我们主要讨论4-Fat-Tree,6-Fat-Tree,8-Fat-Tree和10-Fat-Tree在100次以上的模拟效果,以比较不同情况下的算法性能。

传统算法

算法一(Nearest-Neighbor Algorithm)

这是一种轻量级的算法,算法原理较为简单。它利用Dijkstra算法寻找当前能够找到代价最小且含有未被满足的function的server,作为下一个跳点,其具体步骤如下:

  (1)生成一个空的ArrayListSFP将起始节点放入SFP中,生成一个ArrayListF_SFP存放SFP中已经提供的功能。
  (2)找到一个节点X离SFP中最后一个节点在带宽限制下最近且提供一个未被放入SFP中的功能以及足够的CPU。
  (3)将X放入SFP中,并且将X所提供的被需求的功能放入F_SFP中。
  (4)回到步骤(2),直到F_SFP满足所有被需求完成的功能后进入步骤(5).
  (5)将Destination放入SFP中,并且计算SFP中从起始节点到结束节点的距离。

我认为这是一种较为经典的“贪心算法”的思路,仅求得最优的局部最优解,而未考虑全局的情况,可能会产生许多“回溯”的现象。甚至这种算法并不一定能真正找到一个“局部最优”。例如,假设server A可以满足1个未被满足的function,而server B可以满足5个。然而可能因为server A相对代价更小一些,Nearest-Neighbor Algorithm可能还会选择server A,而放弃能够提供更多function的server B,这显然是不合理的。

Nearest-Neighbor Algorithm适合于解决较为简单的问题,,当路由变得复杂时,它的性能可能会衰减比较严重。

算法二

这是一种相对重量级的算法,旨在缓解算法一中可能会出现的大量“回溯”的问题。其算法步骤如下:

  (1)根据需求的SFs, 随机生成$N$个序列 ($N$可以自定义,可多变,是一个Integer);序列的含义是:比如 需求SFs有$f_1, f_2, f_3$; 那么可以生成$N = 3$ 个序列$f_1, f_2, f_3$; $f_1, f_3, f_2$,以及$f_2, f_3, f_1$。
  (2)找寻所有所需求SF的可被映射的物理节点,比如:$f_1$可以被放置在物理server 0号, 1号, 3号上,那么形成一个关于$f_1$的list 叫candidate list ($CL$)。$CL_{f1} = s_0, s_1, s_3$.
  (3)根据所生成的序列,生成一个由$CL$组成的物理点图。比如,对于$f_1, f_2, f_3$这个序列,那么将会生成$s, CL_{f1}, CL_{f2}, CL_{f3}, d$这样的物理点图。其中$s$和$d$代表起点和终点。
  (4)将相邻的两个点阵用最短路径连接,比如$s$将用最短路径连接到$CL_{f1}$中每一个点;$CL_{f1}$中的每一个点都会连接到$CL_{f2}$中的每一个点。
  (5)在新生成的图中,跑$s$到$d$的最短路径, 然后求N个序列的平均值。

这种算法构造了一个相当复杂的图结构,在实际测试中,它在面对需求较为复杂的功能时能够取得较好的效果,但是在计算时间上需要付出很大的代价,不适合实时性较高的问题。而且在功能较为简单的情况下,它的性能远没有算法一的效果好。

传统算法的总结

这两种传统算法,可以简单理解成“轻量级算法”和“重量级算法”。它们的优缺点也相当明显,一个适合功能需求较小,且网络较为简单的情况;一个适合功能需求较大,且网络较为复杂的情况。然而在实际中,它们并不能解决全部的问题,我们在实际问题中也很难确定哪种方法更适合当下的情况。因此,此类路由优化问题亟需一种全新的算法。

全新算法及未来展望

我们提出了一种全新的算法,目前已经在绝大多数情况下超越了前两种传统算法的性能。下面是8-Fat-Tree结构中功能需求数为10的结果,其中散点AB分别对应传统算法一二,而散点C对应我们提出的新算法模型。

由于我们研究还没有全部结束,且论文离投稿还有较长一段时间,所以在此我先给自己挖个坑,等事情结束后再继续更新我们的新算法,以及各因素对最终结果的影响,预计也会将我之前编写的代码开源。在这里也真心感谢魏博士和郑博士能带领我做research,给了我一个全新的算法思路,细心地带领着我这个小白一步步理解research每一步的含义,我也会继续努力跟进本次实验。

文章目录
  1. 1. 项目简介
  2. 2. Fat-tee
  3. 3. 本次实验要解决的问题
  4. 4. 传统算法
    1. 4.1. 算法一(Nearest-Neighbor Algorithm)
    2. 4.2. 算法二
    3. 4.3. 传统算法的总结
  5. 5. 全新算法及未来展望