06 August 2014

A Scalable, Commodity Data Center Network Architecture_SIGCOMM_2008


Introduction

  • 设计数据中心的通信体系架构的目标:
  1. 互连带宽可扩展: 数据中心内任意一台host都可以通过本地网络接口与其他host实现全带宽的通信
  2. 规模经济: 使廉价的现成的以太网交换机成为大规模数据中心网络的基础
  3. 向后兼容: 整个系统要向后兼容那些运行以太网和IP的host,使现有的普遍利用以太网和IP的数据中心无需修改就可以利用新的互连架构

  • 上图所示的拓扑是一个k元fat-tree。包含k个pod,每个pod由两层每层k/2个交换机组成。每个k-port边缘交换机直接连接k/2个host,余下的k/2个port连接到上层的汇聚交换机。共有(k/2)^2个k-port核心交换机,每个核心交换机连接k个pod(第i个port连接第i个pod)。通常,由k-port交换机构建的fat-tree支持k^3/4个host。上图所示的fat-tree为non-blocking

  • 连接到同一个边缘交换机的所有host组成一个子网。因此,某子网内的流量仅经过其对应的边缘交换机,相同pod不同子网间的流量还需经过该pod内的汇聚交换机,而不同pod间的流量需要经过核心交换机


Motivation

  • 实现fat-tree网络中最大对剖带宽的要求是任意pod传出的流量都均匀分布在核心交换机

  • k元fat-tree中,不同pod的host之间“最短路径”有(k/2)^2条。然而,传统域内路由协议例如以跳数作为“最短路径”度量标准的OSPF,只会选择其中一条路径传输流量。因此,导致交换机将发往某一子网的流量都集中在某个端口(虽然其他端口存在等价路径)。此外,根据OSPF消息到达时间的交错性,可能只有一小部分核心交换机(甚至一个)被选为pod间的中间链路(没有利用fat-tree的链路冗余),将在这些点造成严重的拥塞


Addressing

  • k元fat-tree的IP分配私有区段10.0.0.0/8。pod中交换机的地址形如10.pod.switch.1,其中“pod”定义交换机所处pod编号([0,k-1]),“switch”定义交换机在pod中所处位置([0,k-1],从左至右、从下至上递增)。核心交换机的地址形如10.k.j.i,j和i定义分别与pod内第j个汇聚交换机的第i个端口相连([1,(k/2)],从左至右递增)。host的地址形如10.pod.switch.ID,ID定义host在子网中所处位置([2,k/2+1],从左至右递增)

  • 每个边缘交换机负责一个由k/2(k<256)个host组成的/24子网,这种机制的host规模可以达到4.2M


Two-Level Routing Table

  • 主路由表(prefix,port)的表项可能指向一个次级表(suffix,port),并且一个次级表可以指向多个主表的表项。主路由表中/m表示m位前缀掩码,次级表中/m表示m位后缀掩码。上图所示的路由表位于IP为10.2.2.1的交换机中。根据路由表,传入的目的IP地址为10.2.1.2的数据包将经由端口1转发,而目的IP地址为10.3.0.3的数据包将经由端口3转发。任意一个pod内交换机(边缘交换机和汇聚交换机)所携带路由表的prefix和suffix数都不超过k/2


Routing Algorithm

  • 主要分为两部分: 网络建立阶段,静态地生成所有路由表并且将其装载到交换机中; 动态路由协议负责检测个别交换机故障并且执行故障路径切换

  • 生成pod内交换机的转发表

  • 生成核心交换机的转发表

  • addPrefix(switch,prefix,port),addSuffix(switch,suffix,port)

  • 由于fat-tree拓扑中任意一对host间存在冗余链路,因此容错问题引人注目。故采用简单的故障广播协议,允许交换机路由时绕过下行一、两跳的链路或交换机故障。在这种机制下,网络中每个交换机与其每个邻居维护一个双向转发检测(BFD)会话,用于确定链路或邻居交换机故障。从容错角度有两类故障可以容忍: (a) pod内边缘交换机和汇聚交换机间故障 (b) 汇聚交换机和核心交换机间故障。边缘交换机故障显然会导致其与直接连接的host间连接断开(唯有冗余交换机存在才能容忍这种故障)

  • 边缘交换机与汇聚交换机间链路故障:

  1. 经边缘交换机向外传输pod内、pod间的流量。故障所在边缘交换机的本地流分类器将故障所在链路的开销设置为无限,并不为其分配任何新流,选择另一个可用的汇聚交换机
  2. 经汇聚交换机传输pod内的流量。故障所在汇聚交换机广播一个链路故障标签通知同一个pod内所有其他边缘交换机。当边缘交换机为新流分配端口时会检查是否分配了标签指定的端口,并尽可能避免
  3. 经汇聚交换机向内传输pod间的流量。与故障所在汇聚交换机相连的核心交换机通过二者间的链路连接到汇聚交换机所在pod(这些核心交换机与该pod连接的唯一链路)。因此,汇聚交换机广播链路故障标签通知所有与其相连的核心交换机(表征其没有能力传输流量到故障所在边缘交换机对应子网),收到故障通知的核心交换机将标签发送给其相连的其他pod内的汇聚交换机,当为新流(目的子网为故障所在子网)分配路径时,这些汇聚交换机就会避免将流分配给那些核心交换机
  • 汇聚交换机与核心交换机间链路故障:
  1. 经汇聚交换机向外传输pod间的流量。故障所在汇聚交换机的本地路由表将故障所在链路标记为不可达,选择另一个可用的核心交换机
  2. 经核心交换机向内传输pod间的流量。故障所在核心交换机向与其相连的其他所有汇聚交换机广播一个链路故障标签(表征其没有能力传输流量到故障所在pod),收到故障通知的汇聚交换机为新流(目的pod为故障所在pod)分配路径时就会避免将流分配给故障所在核心交换机
  • 交换机故障发出相同的BFD警报,并引发同样的处理。当故障链路和交换机恢复正常,重新建立BFD会话,对故障处理反向取消

  • 在由中央调度程序实现流调度的机制下,容错问题相对简单。中央调度程序将收到故障信息所对应链路标记为繁忙或不可用,将任何包含故障所在链路的路径设置为失效,并调度大流绕过故障


Flow Classification

  • 通过动态重新分配pod内交换机的端口,避免可能出现的局部拥塞(两个流竞争同一个输出端口。即使其他未使用的端口存在等价路径)

  • 定义流: 包头域(源、目的IP地址,目的传输端口)为同一子网的数据包序列

  • 对于pod内的交换机:

  1. 识别同一个流的后续数据包,并将其通过同一个输出端口转发(防止数据包重新排序)
  2. 周期性重新分配最小数量的流输出端口,以减少不同端口的流汇聚能力间的差距(面临动态变化的流大小时,确保上行端口中流的合理分布)

  • 流分类的贪婪启发式算法

Flow Scheduling

  • 通过中央调度程序实现流调度,减少大流间的重叠

  • 边缘交换机: 最初,边缘交换机只是局部地为新流分配一个负载最小的端口。然而,边缘交换机可以检测出某些输出流的大小已经超过预先定义的阀值,并周期性地向中央调度程序发送通知,由中央调度程序指定所有大流的传输路径

  • 中央调度程序: 为每条链路维护一个布尔状态(表征链路传输大流的能力)。对于pod间流量,存在(k/2)^2条等价链路(每条路径分别对应一个核心交换机)。每当中央调度程序收到一个新流的通知,便会线性搜索核心交换机,寻找一条不涉及保留链路的路径。一旦找到一条这样的路径,中央调度程序便将路径涉及的链路标记为保留链路,并通知路径上的交换机重新分配端口。对于pod内流量,也执行类似搜索(搜索对象改为汇聚交换机)

  • 中央调度程序垃圾收集机制: 收集过期的流,清除该流对应的保留标志

  • 边缘交换机检测出大流后并不进入阻塞状态等待中央调度程序的流调度,而是继续执行默认端口转发(中央调度程序会根据已收到的大流通知对交换机的传输端口进行重新分配)

  • 流调度与流分类的区别: 流调度不允许交换机独立地改变流的传输端口,中央调度程序是唯一有权力对传输端口进行重新分配的实体



blog comments powered by Disqus