Fat Tree 分析

本文是源于USTC Advance Computer Network 的课程内容做的总结

论文来源：A scalable, commodity data center network architecture

本文将分析Fat Tree的 拓扑结构、编址方案和路由算法三个方面。

拓扑结构

该文章中从传统数据中心通信的问题提出了FatTree的拓扑结构来连接以太交换机。提出的结构如下（图示为一个参数K=4的 FatTree）：

对于参数为K的FatTree有如下特征：

• Pod： 有K个Pod，每个Pod包含2层Switch，每层k/2个Switch。

• 边缘层Edge：其Switch有K个输出端口，

  • 前k/2个输出端口从左往右的顺序依次连接主机，
  • 后k/2个输出端口依次连接聚合层Aggregation的Switch。

• 聚合层Aggregation：其Switch有K个输出端口，

  • 前k/2个输出端口从左往右的顺序依次连接边缘层Edge的Switch，
  • 后k/2个输出端口依次连接核心层Core的Switch，从左往右优先级每个Switch分配k/2个核心层Switch。

• 核心层Core：有（k/2）^2个Switch，呈二维(j,i)阵列，

  • 每个Switch的Port 编号连接对应Pod，K个Port从左往右顺序连接K个Pod；
  • 具体到Pod中的Switch时，阵列第j行的Switch均连向聚合层的第j个Switch。

• 主机Hosts:不同Pod的hosts之间有(k/2)^{2个最短路径,只使用其中一条，每条路有5跳（核心层有（k/2）}2个Switch选择）。

注意：1.每个Switch交换机均相同为K个输入输出端口（降低网络成本）；2.支持在横向拓展的同时拓展路径数目。

编址方案

• 网络中所有的地址均在私有空间10.0.0.0/8中。

• Pod交换机：编码为 10.${Pod}.${Switch}.1

  • Pod表示所在的Pod号，范围[0,k-1]。
  • Switch:表示在某Pod中的Switch编号，编号规则为从左到右，自底向上的优先顺序，范围是[0,k-1]（如图示中，左下10.0.0.1，右下10.0.1.1，左上10.0.2.1,右上10.0.3.1）。

• 核心交换机（core）：编码为 10.${k}.${j}.${i}，在上图中k=4，（j,i）表示Switch在core中的坐标，i\j范围[1,k]。

• 主机（host）：编码为10.${pod}.${switch}.${ID},pod switch 同上述规则，表示属于哪一个Pod，与哪一个边缘层edge的Switch相连；ID为所处子网的位置，范围[2,k/2+1]，从左往右编址（由于1已经被Switch占用，故ID从2开始）

路由算法

FatTree的路由算法特点是两层路由表（前缀匹配路由表，后缀匹配路由表），向上使用两层路由，向下使用一层前缀匹配路由。

由上图，二级后缀路由表在一级前缀路由表中的记录是0.0.0.0/0。

该路由算法涉及三层（核心层、聚合层、边缘层）路由器的路由表生成算法。

聚合层Aggregation

其路由算法如下图伪代码：

• 第一行是对所有Pod循环，编号范围是[0,k-1]

• 第二行对 聚合层 的Switch循环，编号范围是[(k/2),k-1]

• 第3~5行是对每一个 边缘层Edge 的Switch循环，连接该聚合层的Switch到边缘层的Switch；第4行中表示将第i个边缘层Switch连接到该聚合层Switch的输出Port i

• 第6~9是将该聚合层Switch向外输出到核心层Core，用于跨子网Pod的通信；根据(i-2+z)mod(k/2)+(k/2)计算出的端口可以将跨pod访问指定主机的信息从正确的端口转发出去，模运算的目的是保证负载均衡。（注意计算公式恰好是通过i和z的偏移映射到对应的核心层Core的Switch）

边缘层Edge

边缘层Switch的路由算法和聚合层的大致相同，区别在于无需向下路由（向下到host按照标准路由模式），同时Switch z伪代码的取值范围改变为其编号范围。

• 第6~9行同上也一样的负载均衡映射模式，只是出口变为了向上连接到聚合层的Switch。
  

核心层Core

核心层Switch的路由表生成算法如下图伪代码

• j\i表示对Core阵列Switch坐标遍历

• 第3~5行是对指定的pod，从指定的端口转发出去（本文第一部分中说明核心Switch Port i正好连到第i个Pod）
  

案例

如下图，需要从Pod0中的10.0.1.2发送一帧信息到目的host 10.2.0.3

1. 10.0.1.2 to 10.0.1.1：由标准路由完成，因为10.0.1.1是主机网管。
2. 10.0.1.1 to 10.0.2.1：查前缀路由表进入0.0.0.0/0的二级后缀路由表查到0.0.0.3/8在Port 2出（由代码6~9行表明,i=3,z=1，算出port=2,端口0、1映射下面主机，端口2、3映射聚合层Switch，从左往右2表示10.0.2.1）。
3. 10.0.2.1 to 10.4.1.2：查前缀路由表进入0.0.0.0/0的二级后缀路由表查到0.0.0.3/8在Port 3出（由代码6~9行表明,i=3,z=2，算出port=3,端口0、1映射下面edge的Switch，端口2、3映射Core Switch第0行第0、1个，从左往右3表示10.4.1.2）。
4. 10.4.1.2 to 10.2.2.1: 由前缀路由表匹配的到Pod值为2，发送到第2个Pod;由于j=1，故发送给Pod2中第1个Switch 10.2.2.1
5. 10.2.2.1 to 10.2.0.1: 由前缀表匹配到（代码3~5行中i=0），指向第0个Edge层Switch 10.2.0.1
6. 10.2.0.1 to 10.2.0.3:标准路由技术