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

[[87573]]

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

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

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

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

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

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

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

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

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

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

Why SDN?

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

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

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

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

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

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

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

#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 是整個網(wǎng)絡(luò)邏輯上的中心控制器。

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

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

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

Switch Design

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

[[87574]]

藍(lán)色的芯片是對外插線的，綠色的芯片充當(dāng)背板(backplane)。如果發(fā)往藍(lán)色芯片的 packet 目標(biāo) MAC 地址在同一塊藍(lán)色芯片上，就“內(nèi)部解決”;如果不是，則發(fā)往背板，綠色芯片發(fā)到目標(biāo)地址所對應(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 會被轉(zhuǎn)發(fā)到 OFC 上，在 OFC 上運(yùn)行 BGP 協(xié)議棧。

Routing

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

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

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

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

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

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

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

#p#

TE 算法

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

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

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

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

TE Optimization 算法分下面三步：

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

Tunnel Group Generation: 給 FG 分配帶寬

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

選路

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

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

算法描述：

分配流量

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

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: 由于硬件支持的流量控制不能無限精細(xì)，需要對上一步計算出的流量進(jìn)行離散化。求最優(yōu)解是個整數(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ù)上面的例子：

離散化會降低性能嗎

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

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

#p#

TE 實現(xiàn)

Tunneling

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

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

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

TE as Overlay

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

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

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

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

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

操作依賴

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

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

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

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

#p#

部署效果

統(tǒng)計

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

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

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

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

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

即使有拓?fù)渚酆?，每天也會發(fā)生好幾次邊的刪除

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

錯誤恢復(fù)

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

由上表可見，單條線路損壞只會中斷連接 4 毫秒，因為受影響的兩臺交換機(jī)會立即更新 ECMP 表;一個 Encap Switch 損壞會使周邊的交換機(jī)都更新 ECMP 表，比單條線路損壞多耗時一些。

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

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

優(yōu)化效果

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

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

一次事故

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

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

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

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

ISIS Hello message(心跳包)也因為長隊列而阻塞了，交換機(jī)們都認(rèn)為周圍的交換機(jī)掛掉了。不過 TE 流量仍然正常運(yùn)行，因為它的優(yōu)先級高于傳統(tǒng)路由。

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

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

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

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

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

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

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

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

一些未來研究方向：

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

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

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