M. Al-Fares, A. Loukissas, A. Vahdat, M. Al-Fares, A. Loukissas, and A. Vahdat, “A scalable, commodity data center network architecture,” ACM SIGCOMM Computer Communication Review, vol. 38, no. 4, pp. 63–74, Oct. 2008.

这篇paper提出的Fat Tree网络拓扑被后续做DCN带宽分配，或者flow调度的论文纷纷引用。是DCN方面非常经典的一篇论文。

Problem:

  1. 数据中心规模越来越大，承载更多更复杂的任务，需要更大规模和性能更好的网络。switch port不够用了。
  2. 要实现大规模的交换网络，如果采用大型的交换机，一方面价格难以承受，另一方面性能不够且难以扩展。如果采用传统的树形结构，扩展起来价格呈非线性增长，另外层次的累积将对上层交换机的带宽提出更高要求。
  3. 就是 性能 + 价格

Goal:

  1. 任意一对host能够达到本地端口的全带宽，比如跟host直接相连的link为1Gbps，那么这1Gbps对于该host必须能达到
  2. 低成本扩展，加入更多的host并不需要购买更贵的设备来满足
  3. 向后兼容，现有的或者一起的Ethernet/IP设备能够使用。（即做最小的软件和硬件改动）

Method:

Fat Tree中全部采用3层交换机。

  1. Clos Networks/Fat-Trees 的交换架构

    • k port的commodity switch 组成k个pod，包含$(k/2)^2$个k port的core switch. 因为upper layer里一共$k/2$个switch，每个switch有$k/2$个port连不同的core switch，因此一共有$k^2/4$个core switch。
    • pod里分为upper layer 和lower layer。
    • 一共 $k(k/2)^2$个host
  2. Fat-Tree 的静态路由分配和查询delay的减小。
    • 采用prefix 和 suffix 两层路由表。并由全局Controller初始化写入
    • 采用TCAM的(Content Addressing Memory)快速查询减小route lookup delay
  3. 提供额外的Fat-Tree动态路由
    • 根据port的load
  4. Fault Tolerance
    • 分情况讨论，用到了BFD(Bidirectional Forwarding Detection)的session技术。如果是pod内部switch间的link或者switch挂了将对哪些类型的流量造成影响，如何解决。
    • 如果是upper layer和core switch间的link或者switch挂了
    • 如果是lower layer的switch挂了，则提供该层的冗余switch备用.

Related:

Misc:

  • 2层交换机相连成环，一般通过配置STP生成树协议来保证不成环。

  • 补充了一下关于non-blocking的知识：

    • strict-sense nonblocking, meaning that an unused input on an ingress switch can always be connected to an unused output on an egress switch, without having to re-arrange existing calls.

    任意一个free的input能够通到一个unused的output

      m >= 2n-1
    • rearrangeably nonblocking, meaning that an unused input on an ingress switch can always be connected to an unused output on an egress switch, but for this to take place, existing calls may have to be rearranged by assigning them to different centre stage switches in the Clos network.

    通过调整重分配，能够让一个free的input通往一个unused的output

      m >= n

  • Achieving an oversubscription ratio of 1:1 in practice may be difficult because of the need to prevent packet reordering for TCP flows?

    HKUST SING Lab 白神说

    如果你要实现真的1：1

    你就需要一个绝对意义上的均匀把数据包分到每条链路上

    万一某段时间就一个大流在那里传

    你是不是也应该把他的数据包均匀分呢

    但是你一分，就乱序了

    所以说，绝对的良好的负载均衡是和TCP有矛盾的

    比如说uplink为800Mbps带宽，但是host的interface是1Gbps，那么如果不将host的flow分流，那么host就只能使用到interface的800Mbps带宽。在Fat Tree中，分流的话，会造成TCP reordering。因此无法实现真正的1:1

  • $ 4k(k/2)^2 $?