Google 已經(jīng)將其數(shù)據(jù)中心廣域網(wǎng) (WAN) 的設(shè)計(jì)和部署經(jīng)驗(yàn)完整地公之于眾，為什么 Google 要用SDN?如何把 SDN 漸進(jìn)地部署到現(xiàn)有的數(shù)據(jù)中心?透過(guò)本文，我們能窺見 Google 全球數(shù)據(jù)中心網(wǎng)絡(luò)的冰山一角。

[[87573]]

流量的巨大浪費(fèi)

眾所周知，網(wǎng)絡(luò)流量總有高峰和低谷，高峰流量可達(dá)平均流量的 2~3 倍。為了保證高峰期的帶寬需求，只好預(yù)先購(gòu)買大量的帶寬和價(jià)格高昂的高端路由設(shè)備，而平均用量只有 30%~40%。這大大提高了數(shù)據(jù)中心的成本。

這種浪費(fèi)是必然的嗎?Google 觀察到，數(shù)據(jù)中心中的流量是有不同優(yōu)先級(jí)的：

用戶數(shù)據(jù)拷貝 到遠(yuǎn)程數(shù)據(jù)中心，以保證數(shù)據(jù)可用性和持久性。這個(gè)數(shù)據(jù)量最小，對(duì)延遲最敏感，優(yōu)先級(jí)最高。

遠(yuǎn)程存儲(chǔ)訪問 進(jìn)行 MapReduce 之類的分布式計(jì)算。

大規(guī)模數(shù)據(jù)同步 以同步多個(gè)數(shù)據(jù)中心之間的狀態(tài)。這個(gè)流量最大，對(duì)延遲不敏感，優(yōu)先級(jí)最低。

Google 發(fā)現(xiàn)高優(yōu)先級(jí)流量?jī)H占總流量的 10%~15%。只要能區(qū)分出高優(yōu)先級(jí)和低優(yōu)先級(jí)流量，保證高優(yōu)先級(jí)流量以低延遲到達(dá)，讓低優(yōu)先級(jí)流量把空余流量擠滿，數(shù)據(jù)中心的廣域網(wǎng)連接(WAN link)就能達(dá)到接近 100% 的利用率。要做到這個(gè)，需要幾方面的配合：

應(yīng)用(Application)需要提前預(yù)估所需要的帶寬。由于數(shù)據(jù)中心是 Google 自家的，各種服務(wù)所需的帶寬都可以預(yù)估出來(lái)。

低優(yōu)先級(jí)應(yīng)用需要容忍高延遲和丟包，并根據(jù)可用帶寬自適應(yīng)發(fā)送速度。

需要一個(gè)中心控制系統(tǒng)來(lái)分配帶寬。這是本文討論的重點(diǎn)。

Why SDN?

計(jì)算機(jī)網(wǎng)絡(luò)剛興起時(shí)，都是插一根線連到交換機(jī)上，手工配置路由規(guī)則。在學(xué)校機(jī)房之類網(wǎng)絡(luò)不復(fù)雜的情況下，時(shí)至如今也是這么做的。但是，只要增加一個(gè)新設(shè)備，就得鉆進(jìn)機(jī)房折騰半天;如果一個(gè)舊設(shè)備壞了，就會(huì)出現(xiàn)大面積的網(wǎng)絡(luò)癱瘓。廣域網(wǎng)絡(luò)的維護(hù)者們很快就不能忍受了，于是就誕生了分布式、自組織的路由協(xié)議，如BGP、ISIS、OSPF 等。

為什么設(shè)計(jì)成這樣呢?有兩方面原因。首先，七八十年代廣域網(wǎng)絡(luò)剛剛興起時(shí)，網(wǎng)絡(luò)交換設(shè)備很不穩(wěn)定，三天兩頭掛掉，如果是個(gè)中心服務(wù)器分配資源，那么整個(gè)網(wǎng)絡(luò)就會(huì)三天兩頭癱瘓。其次，Internet 是多家參與的，是 Stanford 愿意聽 MIT 指揮，還是 MIT 愿意聽 Stanford 指揮?

今天，在數(shù)據(jù)中心里，這兩個(gè)問題都不復(fù)存在。首先，現(xiàn)在的網(wǎng)絡(luò)交換設(shè)備和服務(wù)器足夠穩(wěn)定，而且有 Paxos 等成熟的分布式一致性協(xié)議可以保證“中心服務(wù)器”幾乎不會(huì)掛掉。其次，數(shù)據(jù)中心的規(guī)模足夠大，一個(gè)大型數(shù)據(jù)中心可以有 5000 臺(tái)交換機(jī)(switch)，20 萬(wàn)臺(tái)服務(wù)器，與七八十年代整個(gè) Internet 的規(guī)模已經(jīng)相當(dāng)了。數(shù)據(jù)中心是公司自家的，想怎么搞就怎么搞。

因此，Software Defined Networking (SDN) 應(yīng)運(yùn)而生。以 OpenFlow 為代表，SDN 把分散自主的路由控制集中起來(lái)，路由器按照 controller 指定的規(guī)則對(duì) packet 進(jìn)行匹配，并執(zhí)行相應(yīng)動(dòng)作。這樣，controller 就可以利用整個(gè)網(wǎng)絡(luò)的拓?fù)湫畔⒑蛠?lái)自 application 的需求信息計(jì)算出一組接近全局最優(yōu)的路由規(guī)則。這種 Centralized Traffic Engineering (TE) 有幾個(gè)好處：

使用非最短路的包轉(zhuǎn)發(fā)機(jī)制，將應(yīng)用的優(yōu)先級(jí)納入資源分配的考慮中;

當(dāng)連接或交換機(jī)出現(xiàn)故障，或者應(yīng)用的需求發(fā)生變化時(shí)，動(dòng)態(tài)地重新分配帶寬，快速收斂;

在較高的層次上指定規(guī)則，例如Gmail 的流量不經(jīng)過(guò)天朝。

#p#

Design

Overview

交換機(jī)硬件是 Google 定制的，負(fù)責(zé)轉(zhuǎn)發(fā)流量，不運(yùn)行復(fù)雜的控制軟件。

OpenFlow Controller (OFC) 根據(jù)網(wǎng)絡(luò)控制應(yīng)用的指令和交換機(jī)事件，維護(hù)網(wǎng)絡(luò)狀態(tài)。

Central TE Server 是整個(gè)網(wǎng)絡(luò)邏輯上的中心控制器。

第一條虛線上面是 Central TE (Traffic Engineering) Server。

一二兩條虛線之間是每個(gè)數(shù)據(jù)中心(Site)的控制器，被稱為 Network Control Server (NCS)，其上運(yùn)行著 OpenFlow Controller (OFC) 集群，使用 Paxos 協(xié)議選出一個(gè) master，其他都是熱備(hot standby)。

二三兩條虛線之間是交換機(jī)(switch)，運(yùn)行著 OpenFlow Agent (OFA)，接受 OFC 的指令并將 TE 規(guī)則寫到硬件 flow-table 里。

Switch Design

Google 定制的 128 口交換機(jī)由 24 個(gè) 16 口 10Gbps 通用交換機(jī)芯片制成。(在本文中，“交換機(jī)”和“路由器”是通用的。需要說(shuō)明工作在 MAC 層還是 IP 層時(shí)，會(huì)加定語(yǔ) layer-2 或 layer-3)拓?fù)浣Y(jié)構(gòu)見下圖。

[[87574]]

藍(lán)色的芯片是對(duì)外插線的，綠色的芯片充當(dāng)背板(backplane)。如果發(fā)往藍(lán)色芯片的 packet 目標(biāo) MAC 地址在同一塊藍(lán)色芯片上，就“內(nèi)部解決”;如果不是，則發(fā)往背板，綠色芯片發(fā)到目標(biāo)地址所對(duì)應(yīng)的藍(lán)色芯片。

交換機(jī)上運(yùn)行著用戶態(tài)進(jìn)程 OFA (OpenFlow Agent)，連接到遠(yuǎn)程的 OFC (OpenFlow Controller)，接受 OpenFlow 命令，轉(zhuǎn)發(fā)合適的 packet 和連接狀態(tài)到 OFC。例如，BGP 協(xié)議的 packet 會(huì)被轉(zhuǎn)發(fā)到 OFC 上，在 OFC 上運(yùn)行 BGP 協(xié)議棧。

Routing

RIB: Routing Information Base，路由所需要的網(wǎng)絡(luò)拓?fù)?、路由?guī)則等

Quagga: Google 采用的開源 BGP/ISIS 協(xié)議實(shí)現(xiàn)

RAP: Routing Application Proxy，負(fù)責(zé) OFA 與 OFC 之間的互聯(lián)

如上圖所示，Quagga 路由協(xié)議棧中的 RIB 保存著路由規(guī)則，如發(fā)往某個(gè)子網(wǎng)的包要從某兩個(gè)端口選一個(gè)出去。數(shù)據(jù)中心網(wǎng)絡(luò)中一個(gè) packet 一般會(huì)有多條路線可走，一方面提高冗余度，一方面充分利用帶寬，常用的協(xié)議是 Equal Cost Multiple Path (ECMP)，即如果有多條最短路，就從其中隨機(jī)選一條走。

在 OFC 中，RIB 被分解為 Flows 和 Groups。要理解這個(gè)拆分的必要性，先要理解網(wǎng)絡(luò)交換設(shè)備是怎樣工作的?，F(xiàn)代網(wǎng)絡(luò)交換設(shè)備的核心是 match-action table。Match 部分就是 Content Addressable Memory (CAM)，所有條目可以并行地匹配，匹配結(jié)果經(jīng)過(guò) Mux 選出優(yōu)先級(jí)最高的一條;Action 則是對(duì)數(shù)據(jù)包進(jìn)行的動(dòng)作，比如修改包頭、減少 TTL、送到哪個(gè)端口、丟棄數(shù)據(jù)包。

對(duì)路由規(guī)則來(lái)說(shuō)，僅支持精確匹配的 CAM 是不夠的，需要更高級(jí)的 TCAM，匹配規(guī)則支持 bit-mask，也就是被 mask 的位不論是0還是1都算匹配。例如需要匹配 192.168.0.0/24，前24位精確匹配，最后8位設(shè)為掩碼即可。

在 OFC 中，F(xiàn)lows 對(duì)應(yīng)著 Match 部分，匹配得出 Action 規(guī)則編號(hào);Groups 對(duì)應(yīng)著 Action 部分，采用交換機(jī)中現(xiàn)有的 ECMP Hash 支持，隨機(jī)選擇一個(gè)出口。

#p#

TE 算法

優(yōu)化目標(biāo)

系統(tǒng)管理員首先決定每個(gè)應(yīng)用在每對(duì)數(shù)據(jù)中心之間所需的帶寬和優(yōu)先級(jí)，這就形成了一系列 {Source site, Dest site, Priority, Required bandwidth} 四元組(此處為了便于理解，對(duì)原論文進(jìn)行了修改)。將這些四元組按照 {Source site, Dest site, Priority}分組，把所需帶寬加起來(lái)，就形成了一系列 Flow Group (FG)。每個(gè) FG 由四元組 {Source site, Dest site, Priority, Bandwidth} 表征。

TE Optimization 的目標(biāo)是 max-min fairness，就是在公平的前提下滿足盡可能多的需求。由于未必可以滿足所有需求，就要給“盡可能多”和“公平”下個(gè)定義。我們認(rèn)為，客戶的滿意度是跟提供的帶寬成正比的，也是跟優(yōu)先級(jí)成反比的(優(yōu)先級(jí)越高，就越不容易被滿足);如果已經(jīng)提供了所有要求的帶寬，則滿意度不再提高。在此假設(shè)基礎(chǔ)上，引入 fair share 的概念，兩個(gè) Flow Group 如果 fair share 相同，就認(rèn)為這兩個(gè)客戶的滿意度相同，是公平的。

例子：App1 需要 15G 帶寬，優(yōu)先級(jí)為10;App2 需要 5G 帶寬，優(yōu)先級(jí)為1;App3 帶寬多多益善(無(wú)上限)，優(yōu)先級(jí)為0.5。

TE Optimization 算法分下面三步：

Tunnel Selection: 選擇每個(gè) FG 可能走的幾條路線(tunnel)

Tunnel Group Generation: 給 FG 分配帶寬

Tunnel Group Quantization: 將帶寬離散化到硬件可以實(shí)現(xiàn)的粒度

選路

Tunnel Selection：利用 Yen 算法 [2]，選出 k 條最短路，k 是一個(gè)常量。

例如下面的網(wǎng)絡(luò)拓?fù)?，?k = 3：

算法描述：

分配流量

Tunnel Group Generation: 根據(jù)流量需求和優(yōu)先級(jí)分配流量。(論文中沒有算法描述，我自己整理了一下。由于有些名詞用中文寫出來(lái)很別扭，就用英文了)

Initialize each FG with their most preferred tunnels.

Allocate bandwidth by giving equal fair share to each preferred tunnel.

Freeze tunnels containing any bottlenecked link.

If every tunnel is frozen, or every FG is fully satisfied, finish.

Select the most preferred non-frozen tunnel for each non-satisfied FG, goto 2.

繼續(xù)上面的例子：

流量離散化

Tunnel Group Quantization: 由于硬件支持的流量控制不能無(wú)限精細(xì)，需要對(duì)上一步計(jì)算出的流量進(jìn)行離散化。求最優(yōu)解是個(gè)整數(shù)規(guī)劃問題，很難快速求解。因此論文使用了貪心算法。

Down quantize (round) each split.

Add a remaining quanta to a non-frozen tunnel that makes the solution max-min fair (with minimum fair share).

If there are still remaining quantas, goto 2.

繼續(xù)上面的例子：

離散化會(huì)降低性能嗎

上圖展示了離散化對(duì)性能的影響，這里的 Throughput Delta 是相對(duì)優(yōu)化之前而言的，越大越好。可以看到，當(dāng)流量分配粒度達(dá)到 1/16 后，再提高精細(xì)程度，就沒有太多作用了。

在 Google 最終的實(shí)現(xiàn)中，tunnel 個(gè)數(shù)(前面的 k)設(shè)置為4，分配粒度為 1/4。至于為什么這么設(shè)置，you ask me, I ask who。

#p#

TE 實(shí)現(xiàn)

Tunneling

Encap Switch 是連接終端機(jī)器的邊界路由器，它們將 IP packet 封裝起來(lái)，包上路由專用的 source ip 和 destination ip。

Transit Switch 是中間傳輸路由器，它們只接受經(jīng)過(guò) Encap Switch 封裝的 IP packet，并在數(shù)據(jù)中心之間進(jìn)行路由。

Decap Switch 是連接終端機(jī)器的邊界路由器，其實(shí)跟 Encap Switch 是同一批機(jī)器。它們將被封裝的 IP packet 剝掉一層皮，送給終端機(jī)器。

TE as Overlay

SDN “一步到位”的做法是設(shè)計(jì)一種統(tǒng)一的、集中式的服務(wù)，囊括路由和 Traffic Engineering。但這樣的協(xié)議研發(fā)過(guò)程會(huì)很長(zhǎng)。另外，萬(wàn)一出問題了，大家就都上不了 Google 了。

在這個(gè)問題上，Google 又發(fā)揚(yáng)了“小步快走”的敏捷開發(fā)思想，把 TE 和傳統(tǒng)路由兩個(gè)系統(tǒng)并行運(yùn)行，TE 的優(yōu)先級(jí)高于傳統(tǒng)路由，這樣 SDN 就可以逐步部署到各個(gè)數(shù)據(jù)中心，讓越來(lái)越多的流量從傳統(tǒng)路由轉(zhuǎn)移到 TE 系統(tǒng)。同時(shí)，如果 TE 系統(tǒng)出現(xiàn)問題，隨時(shí)可以關(guān)閉 TE，回到傳統(tǒng)路由。

Google SDN 所承載的流量變化曲線

每個(gè)交換機(jī)都有兩張路由表，LPM (Longest Prefix Match) Table 由基于最短路徑的傳統(tǒng)路由協(xié)議(BGP/ISIS)維護(hù)。ACL Table 是 TE 使用的路由表，優(yōu)先級(jí)高于 LPM，也就是 LPM 和 ACL 都匹配出條目時(shí)，ACL 說(shuō)的算。

上圖的例子是 Encap Switch。匹配結(jié)果是一個(gè) Multipath Table Index 和可選條數(shù)，也就是從 Index 開始的這么多條規(guī)則中根據(jù) Hash 值選出一條規(guī)則。這條規(guī)則寫明了出口(port)和路徑(tunnel)，再?gòu)穆窂奖?Encap Tunnel Table)里查到要被封裝到 IP packet 頭部的 source IP 和 dest IP。對(duì)于 Transit Switch，就不需要路徑表了。

操作依賴

一次 TE 變更可能涉及多個(gè)交換機(jī)的插入/刪除規(guī)則操作，而這些操作不能以任意的順序進(jìn)行，否則就有可能出現(xiàn)丟包。因此有了兩條規(guī)則：

在修改 Tunnel Group 和 Flow Group 之前，先在所有受影響的數(shù)據(jù)中心建立好 tunnel

在所有引用某 tunnel 的條目被刪除之前，不能刪除這個(gè) tunnel

為了在有網(wǎng)絡(luò)延遲和數(shù)據(jù)包亂序 (reordering) 的情況下保證依賴關(guān)系，中心 TE 服務(wù)器為每個(gè)事務(wù)(session)中的有序操作分配遞增的序列號(hào)。OpenFlow Controller 維護(hù)當(dāng)前最大的 session 序列號(hào)，拒絕任何比它小的 session 序列號(hào)。TE 服務(wù)器如果被 OFC 拒絕，將在超時(shí)后重試這個(gè)操作。

#p#

部署效果

統(tǒng)計(jì)

每分鐘 13 次拓?fù)渥兓?/p>

去除維護(hù)造成的更新，每分鐘 0.2 次拓?fù)渥兓?/p>

拓?fù)渲械倪吿砑?刪除事件，一天 7 次(TE 算法運(yùn)行在拓?fù)渚酆虾蟮囊晥D上。兩個(gè)數(shù)據(jù)中心之間可能有上百條 link，把它們聚合成一條容量巨大的 link。)

這方面的經(jīng)驗(yàn)是：

拓?fù)渚酆厦黠@降低了路徑顛簸和系統(tǒng)負(fù)載

即使有拓?fù)渚酆希刻煲矔?huì)發(fā)生好幾次邊的刪除

WAN link 對(duì)端口顛簸(反復(fù)變化)很敏感，用中心化的動(dòng)態(tài)管理收效較好

錯(cuò)誤恢復(fù)

在數(shù)據(jù)中心，設(shè)備、線路損壞是常有的事，因此錯(cuò)誤的影響范圍和恢復(fù)速度很重要。

由上表可見，單條線路損壞只會(huì)中斷連接 4 毫秒，因?yàn)槭苡绊懙膬膳_(tái)交換機(jī)會(huì)立即更新 ECMP 表;一個(gè) Encap Switch 損壞會(huì)使周邊的交換機(jī)都更新 ECMP 表，比單條線路損壞多耗時(shí)一些。

但臨近 Encap Switch 的 Transit Switch 掛掉就不好玩了，因?yàn)?Encap Switch 里有個(gè)封裝路徑表(Encap Tunnel Table)，這個(gè)表是中心維護(hù)的，出現(xiàn)故障后鄰近的 Encap Switch 要匯報(bào)給 OFC，OFC 匯報(bào)給全球中心的 TE Server(高延遲啊)，TE Server 再按照操作依賴的順序，逐個(gè)通知受影響的 Encap Switch 修改路徑。由于這種操作很慢，需要 100ms，整個(gè)恢復(fù)事務(wù)需要 3300ms 才能完成。

OFC、TE Server 的故障都沒有影響，首先因?yàn)樗鼈兪褂昧?Paxos 分布式一致性協(xié)議，其次即使全都掛掉了，也只是不能修改網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，不會(huì)影響已有的網(wǎng)絡(luò)通信。由于前面提到的 TE as Overlay，關(guān)閉 TE 時(shí)，整個(gè)網(wǎng)絡(luò)會(huì)回到基于最短路徑的傳統(tǒng)路由協(xié)議，因此也不會(huì)造成網(wǎng)絡(luò)中斷。

優(yōu)化效果

(a) 是平均帶寬使用率，可以看到帶寬使用率平均可達(dá) 95%。

(b) 是丟包率，其中占 10%~15% 比例(紅線)的高優(yōu)先級(jí) packet 幾乎沒有丟包(藍(lán)色)，而低優(yōu)先級(jí) packet 有較多的丟包(綠色)。如果低優(yōu)先級(jí)應(yīng)用使用通常的 TCP 協(xié)議，在這么高的丟包率下很難高效工作。因此傳輸層協(xié)議也是要特殊設(shè)計(jì)的，不過(guò)論文并未透露。

一次事故

Google 的 SDN 系統(tǒng)曾經(jīng)出現(xiàn)一次重大事故。過(guò)程是這樣的：

一個(gè)新加入的交換機(jī)被不小心配置成了跟原有交換機(jī)一樣的 ID。

兩個(gè) ID 相同的交換機(jī)分別發(fā)送 ISIS Link State Packet，收到的其他交換機(jī)感覺很奇怪，怎么這兩份拓?fù)渫耆灰粯幽?這兩個(gè) ID 相同的交換機(jī)都堅(jiān)持自己的觀察是正確的，導(dǎo)致網(wǎng)絡(luò)中出現(xiàn)洪泛。

TE 控制信令要從 OFC 發(fā)給 OFA，被網(wǎng)絡(luò)阻塞了，造成了長(zhǎng)達(dá) 400MB 的等待隊(duì)列。

ISIS Hello message(心跳包)也因?yàn)殚L(zhǎng)隊(duì)列而阻塞了，交換機(jī)們都認(rèn)為周圍的交換機(jī)掛掉了。不過(guò) TE 流量仍然正常運(yùn)行，因?yàn)樗膬?yōu)先級(jí)高于傳統(tǒng)路由。

此時(shí)，由于網(wǎng)絡(luò)擁塞，TE Server 無(wú)法建立新的 tunnel。雪上加霜的是，TE 依賴機(jī)制要求序列號(hào)較小的操作成功后才能進(jìn)行下一個(gè)操作(見上文)，建立新 tunnel 更是不可能了。因此，任何網(wǎng)絡(luò)拓?fù)渥兓蛟O(shè)備故障都會(huì)導(dǎo)致受影響的網(wǎng)絡(luò)仍在使用已經(jīng)不能用的 tunnel。前面有統(tǒng)計(jì)數(shù)字，每分鐘都會(huì)發(fā)生拓?fù)渥兓虼诉@個(gè)問題是很嚴(yán)重的。

系統(tǒng)運(yùn)維人員當(dāng)時(shí)并不知道問題的根源，于是就重啟了 OFC。不幸的是，這一重啟，觸發(fā)了 OFC 中未發(fā)現(xiàn)的一個(gè) bug，在低優(yōu)先級(jí)流量很大時(shí)不能自啟動(dòng)。

文中說(shuō)，這次故障有幾個(gè)經(jīng)驗(yàn)/教訓(xùn)：

OFC 與 OFA 之間通信的可擴(kuò)展性和可靠性很重要。

OFA 的硬件編程操作應(yīng)該是異步并行的。

應(yīng)該加入更多系統(tǒng)監(jiān)控措施，以發(fā)現(xiàn)故障前期的警告。

當(dāng) TE 連接中斷時(shí)，不會(huì)修改現(xiàn)有的路由表。這是一種 fail-safe 的措施，保證這次故障中已經(jīng)建立的 tunnel 沒有被破壞。

TE Server 需要處理 OFC 無(wú)響應(yīng)的情況。如果有的 OFC 掛掉了，與其禁止所有新建 tunnel 的操作，不如先讓其中一部分運(yùn)轉(zhuǎn)起來(lái)。

一些未來(lái)研究方向：

硬件編程的開銷。OpenFlow 的規(guī)則順序是很重要的，插入一條規(guī)則可能導(dǎo)致后面的規(guī)則都要移動(dòng)，因此操作起來(lái)很慢。這是可靠性的主要瓶頸。

OFC 與 OFA 間的通信瓶頸。OFC 和 OFA 間通信的可擴(kuò)展性和可靠性不足。OpenFlow 最好能提供兩個(gè)通信端口，分別支持高優(yōu)先級(jí)操作和需要大帶寬的數(shù)據(jù)傳輸。

原文鏈接：http://boj.blog.ustc.edu.cn/index.php/2013/08/google-dcn/