FSDC：靈活的高可擴展數據中心網絡結構

余達明，張 震

暨南大學 信息科學技術學院，廣州510632

數據中心網絡是云計算的基礎，許多在線服務，如搜索、郵件、視頻流以及基礎設施服務，如GFS（Google file system）、Map-Reduce、BigTable等，都是通過數據中心網絡為用戶提供服務的。數據中心網絡是由海量服務器、存儲設備和網絡設備構成的一個網絡結構。這意味著，數據中心網絡結構的設計對整個數據中心網絡的性能起著重要作用。

根據服務器是否參與數據轉發，數據中心網絡結構可以劃分為兩類：以交換機為中心的互連結構和以服務器為中心的互連結構。典型的以交換機為中心的數據中心網絡結構通常為層次型結構，并且能支持部署數以萬計的服務器。與此相對，以服務器為中心的數據中心網絡結構借助服務器的網絡接口卡（network interface controller,NIC）完成數據轉發。通過大量服務器NIC 之間的連接以及低端交換機的使用，避免了以交換機為中心方案的布線復雜和高昂的交換機成本。

近年來，隨著數字化信息的普及，網絡數據量呈現海量增長。為了處理這些海量增長的數據，許多大型數據中心被構建起來。這些大型數據中心中含有海量的硬件、軟件和數據資源，可以動態為數百萬用戶提供服務。然而，隨著網絡數據量和用戶數量的不斷增加，數據中心需要不斷擴展，例如：谷歌的數據中心的數據量大概每年翻一番。隨著5G 網絡在世界各地投入使用，全球范圍內接入到互聯網的終端設備將大大增加。因此，未來數據的增加速度將比以往更快。數據量的增長對數據中心網絡的設計提出了更高的要求：

（1）高擴展性：為了應對快速增長的業務需求和數據量，數據中心網絡需要不斷地添加設備以提升整個網絡的計算和儲存能力，而在擴展過程中，當前網絡的性能不會受到影響。

（2）高帶寬：隨著不同在線應用的出現，數據中心的流量特性也發生了巨大變化，從原來80%的外部用戶與數據中心內部服務器之間交互的“南北”流量，變為80%的需要大量服務器協同完成工作的“東西”流量。高帶寬是數據中心網絡性能的重要指標。

（3）高容錯率：設備和鏈路的故障會嚴重影響數據中心網絡的性能。隨著數據中心規模的不斷變大，故障也會變得越發頻繁。如何在故障條件下保持網絡的整體性能也是設計網絡結構的巨大挑戰。

（4）成本效益：當前數據中心的花費主要由四部分組成，45%用于服務器（中央處理器、內存和存儲系統），25%用于基礎設施（電力調配和散熱），15%用于能耗（電力成本），15%用于網絡（鏈路、傳輸設備）。數據中心網絡的設計必須在性能和成本之間取得平衡。

為此，本文提出了一種基于笛卡爾乘積圖的新型數據中心網絡結構FSDC（flexible and highly scalable data center network）。采用不同結構的基礎圖可以構建不同類型的笛卡爾乘積圖。基于不同的笛卡爾乘積圖，可以采用商用端口交換機和2 端口服務器構建不同類型的FSDC 數據中心網絡結構。由于笛卡爾乘積圖底層基礎圖的不同，FSDC 數據中心網絡可以以不同的規模進行擴展，具有良好的靈活性和高可擴展性。

通過對FSDC 拓撲性質的分析、能耗對比分析以及吞吐量模擬實驗，結果表明，與當前其他數據中心網絡結構相比，FSDC 在性能和成本效益方面取得了良好的平衡。

1 相關工作

隨著近年來大數據以及云計算的快速發展，學術界和工業界都對數據中心網絡開展了許多研究工作。

考慮到傳統三層結構的不足，Fares 等人提出了一種改進的三層結構，即FatTree。該結構可使用大量鏈路和小型交換機進行擴展，通過部署大量的冗余交換機和鏈路，FatTree 能實現1：1 的超額訂購。VL2和Potland都是基于FatTree 的結構構建的，它們分別通過平面尋址和分層尋址提供“即插即用”的功能。然而，FatTree 的可擴展性受限于交換機端口數目，即，如果需要擴展FatTree，則必須更換高層的交換機以提供更多的交換機端口。隨著層數的不斷增加，FatTree的構建成本會不斷升高。

DCell是一種遞歸定義的數據中心結構，DCell結構中的服務器具有多端口網卡。高層的DCell 通過一定數量的底層DCell 互相連接而構建。DCell 利用其分布式容錯路由協議將流量均勻分散到不同鏈路當中，以實現高容錯和高帶寬。DCell 使用多端口服務器和復雜的布線來替代昂貴的核心交換機，而使用多端口的服務器會增加成本開銷。

BCube利用服務器的多端口進行拓撲的連接。將數據中心硬件設備部署在集裝箱中，減輕了BCube 布線的問題，最大化其鏈路資源豐富的優勢，使得部署更加簡單。當需要擴展時，只需互連若干個規模相同的集裝箱即可。此外，BCube 使用多端口服務器互連多個交換機，并把路由線路的選擇放置在服務器上。實驗證明，BCube 能支持各種帶寬密集型的應用程序，并且擁有良好的容錯能力，但是大規模使用多端口服務器不可避免地會帶來開銷增加。

XDCent使用多端口的服務器進行數據中心網絡結構的構建，并且與BCube 的連接模式非常相似。XDCent首先依照BCube的互連方式構建數據中心網絡，直到各個服務器只剩余1 個端口。然后，利用各服務器剩余的端口，采用非完整復合圖方式進行連接，確保了整個結構能持續擴展。

FiConn是一種以服務器為中心數據中心結構，采用2 端口的服務器和低端商用交換機構建。與DCell 相似，FiConn 也是通過遞歸方法構建的。與DCell 不同，FiConn 在遞歸擴展過程中會預留一部分服務器端口用于以后的擴展。也就是說，FiConn 的擴展過程不受交換機端口數和服務器端口數的限制。在FiConn 中，同一層但不同分區的部分進行通信時，只依賴于一條鏈路，導致對分帶寬較低，吞吐量和容錯性受到較大的影響。

不同于現有的結構，本文提出了一種全新數據中心網絡結構FSDC，它擁有以下的特性：

（1）靈活擴展：FSDC 不僅擁有高擴展性，并且能根據現實需求來選擇不同的擴展規模。

（2）成本效益：FSDC 具有較好的成本能耗優勢。

（3）高容錯性：FSDC 提供了一種高效的容錯路由機制來應對數據中心可能出現的各種類型故障，保證了通信效率。

2 FSDC 網絡架構

本章首先介紹笛卡爾乘積圖的定義；隨后給出FSDC 網絡結構的構建方法，并且分析其拓撲特性；最后根據其拓撲特性設計出FSDC 結構的路由算法。表1 列出了本文中常用的一些符號。

表1 文中常用符號Table 1 Denotations used in this paper

2.1 乘積圖的定義與性質

笛卡爾乘積圖可以由兩個無向圖和構成，即=?，其具體定義如下：

笛卡爾乘積圖=?中的節點與邊的定義如下：

（1）節點定義：={(,)|∈,∈}。

（2）邊定義:={(,)|=且(,)∈，或=且(,)∈}。

如圖1 所示，乘積圖由和構成，其中為四節點環圖，為三節點環圖。

圖1 笛卡爾乘積圖Fig.1 Cartesian product graph

根據定義1，可以推斷出圖的度數等于圖和圖度數之和。這表示，只要和的度數之和等于，就能靈活地構建具有相同度數的不同種類的笛卡爾乘積圖。

2.2 FSDC 結構

FSDC 是一種基于笛卡爾乘積圖，并通過遞歸的方式構建的數據中心網絡結構，其中笛卡爾乘積圖G=??…?是由1 個和(-1)個通過笛卡爾乘積獲得，這里被稱為基礎圖，被稱為擴展圖。由笛卡爾積的定義可知，圖G可以通過擴展圖繼續進行擴展，擴展形成的G的節點數量是G的倍，其中為擴展圖節點數量。

選擇節點數為的環圖和-1 個節點數為的環圖來構建一個笛卡爾乘積圖G。利用臺2 口服務器連接一個端口交換機組成FSDC 的基本單元，稱之為。將G中的所有節點用替換，再通過服務器的備用端口連接不同的。最后，能夠獲得一個FSDC(,)結構。FSDC 的具體定義如下：

FSDC(,)結構中節點和邊的定義：

（1）交換機和服務器分別定義為(x…;0)和(x…;)，其中1 ≤≤(-1),0 ≤x≤(-1),0 ≤≤(-1),1 ≤≤。

（2）在FSDC(,)中存在三種類型的邊：

①交換機與服務器之間的邊：

②第1 層的服務器與服務器之間的邊：

③第層服務器與服務器之間的邊：

其 中，+(-1)(-1)≤≤+(-1)-1,′=2(+-)--,′=(+x)mod。

圖2 是FSDC 結構的一個示例，一個6 端口交換機連接6 個服務器形成一個，使用去替換圖1 中的節點，進而得到一個(3,4) 結構。此外，通過不同的笛卡爾乘積圖，采用相同類型的交換機可以構建出不同種類的FSDC 結構。如圖3，使用了相同類型的6 端口交換機可以構建另一種FSDC結構(3,3)。

圖2 FSDC2(3,4)結構Fig.2 FSDC2(3,4) structure

圖3 FSDC2(3,3)結構Fig.3 FSDC2(3,3)structure

根據笛卡爾積的定義，圖G可以通過擴展圖進一步擴展形成G。基于G，FSDC 網絡結構也可由層的FSDC(,)擴展為+1層的FSDC(,)。FSDC(,) 是由個FSDC(,)構成的。如圖4 所示，(3,4)結構可進一步擴展為(3,4)結構。

圖4 FSDC3(3,4)結構Fig.4 FSDC3(3,4)structure

在FSDC 中，每個服務器使用一個端口連接中的交換機，使用另一個端口來互聯不同中的服務器。此外，服務器(x…;)由兩部分組成，其中，(x…)表示服務器所在的序列號，表示中服務器的序列號。當∈[1,-1]時，當前服務器為第一層服務器，而當∈[+(-1)(-1),+(-1)-1]時，當前服務器為第(+1)層服務器。

根據定義1和定義2，可以推論出定理1和定理2。

在FSDC(,)中，交換機數量為×t，服務器數量為××t，邊數量為3(××t)/2。

FSDC(,)中，的數量等于G的節點數，而一個包含1臺交換機和臺服務器。因此，交換機數量為×t，而服務器數量為××t。此外，因為FSDC(,)中所有服務器端口都占用，所以邊的數量為3(××t)/2。

FSDC(,)中服務器數量為FSDC(,)中的服務器數量的倍，其中為的節點數量(≥2)。

由定理1 可得，FSDC(,)包含××t臺服務器，而FSDC(,)包含××t臺服務器。因此：

根據定理2，當FSDC 結構由-1 層擴展為層時，整個網絡擴大了倍。

作為拓撲屬性，直徑可用于衡量互聯網絡中的通信時延，直徑小意味著網絡中通信延遲低。以()表示圖的直徑，其中圖的直徑為圖中任意兩頂點之間的最短距離的最大值。

由于FSDC(,) 中的服務器總數為=××t，FSDC(,)的直徑為(logN)。這表示FSDC(,)結構的直徑較小。

當互連網絡的邊數與帶寬相等時，對分帶寬可以定義為將網絡的節點集合劃分為兩個相等子集合時所需移除邊數的最小值。如果網絡具有較大的對分帶寬，則說明該網絡具有更高的吞吐量和更好的容錯性。對于數據中心網絡而言，可以假設當前網絡的邊數與帶寬相等，則通過將拓撲劃分為兩個大小相等的子結構，然后計算其中一個子結構的邊數量，以此來表示當前網絡的對分帶寬。

FSDC(,)的對分帶寬不大于3(××t)/4。

FSDC(,)的對分帶寬可以分為以下三種條件討論：

（1）是偶數

當為偶數時，FSDC(,)的拓撲為對稱結構。通過移去第層一部分邊來將FSDC(,)劃分為兩個大小相等子結構。因為FSDC(,)包含3(××t)/2條邊，所以子結構的邊數少于3(××t)/4。

（2）是奇數，是偶數

由圖2 可知，當滿足條件（2）時，FSDC(,)也是對稱結構。因此，該結構也能劃分為兩個完全相等的子結構，但需要移除的邊分布在第1 層到第層。故每個子結構的邊數少于3(××t)/4。

（3）和都是奇數

如圖3，當嘗試使用條件（2）中描述的方法將網絡分為兩個相同部分時，其中一個結構會比另一個結構多一個。但是，隨著網絡規模的增長，可以逐漸忽略這個多余的，因為它在子結構中所占比例越來越少，即對結構的影響逐漸減少，所以可以把這兩個子結構視為大小相等。因此子結構的邊數少于3(××t)/4。

因為FSDC(,)中包含的服務器數量為=××t，所以其對分帶寬為()。

容錯路由算法可以繞過故障設備或鏈路，并快速到達目標節點。根據FSDC(,)的連接模式，當網絡擴展到第層時，第層的服務器使用其備用端口互連不同的。針對FSDC，本文提出了一種容錯路由算法，此路由算法主要利用笛卡爾乘積圖中不同節點之間存在多條路徑的性質。算法1 的路由原理是，對于任何一對不同位(x,y)(0 ≤≤-1),在第(+1)層的兩個服務器之間存在一條邊或路徑，可以轉換不同位為相同位。因此，源服務器到目標服務器的路徑可以通過遞歸計算得到。

FSDC 容錯路由算法

算法1描述了如何從源服務器發送數據到目標服務器的詳細過程。首先，通過函數-()得到和之間不同位(x≠y)的數量（第1 行），如果等于0，則和在同一個，可以直接返回路徑即可（第2 行）。否則，尋找一對不同位，并將該不同位的對所在的層次位置返回給（第3 行）。使用參數、x和y，可以得到一條第(+1)層的鏈路(,′),通過該鏈路可以將x轉換為y（第4 行）。接下來，測試該鏈路的狀態，若鏈路正常，則返回由(,)，(,′)，(′,)組成的完整路徑（第5 行）；若鏈路失效，則尋找第(+1)層中其他的鏈路(,′),通過該鏈路可以將u轉換為y。然后，構建一條中間路徑(,′)來繞過當前失效的鏈路（第6～8 行）。最后，返回一條由(,)、(,′)、(′,)組成的路徑。

當網絡中不存在任何設備故障或鏈路失效的情況下，算法1 的路由路徑會構建從源服務器和目標服務器之間的最短路徑。例如，若圖2 中網絡設備和鏈路都正常，源服務器和目標服務器分別為[0,2;1]和[2,1;2]，則路由算法構建的最短路徑如下：

當網絡中存在設備故障或鏈路失效的情況時，容錯路由算法會通過檢測，繞過故障設備或鏈路，通過有效的鏈路建立從源服務器到目標服務器的一條非最優路徑。例如，若圖2 中源服務器和目標服務器分別為[0,2;1]和[2,1;2]，而[0,1;3]到[1,1;4]的鏈路失效。算法1 在到達服務器[0 ,1;3]，發現鏈路失效后，會即時選擇一個中間服務器[0,1;4]繞過當前失效的鏈路，則整個路由路徑為：

3 性能比較

本章將FSDC 與其他數據中心網絡結構的性能進行對比，包括FatTree、BCube、DCell 和FiConn 等結構。分析比較的內容包括：網絡拓撲性質、可擴展性、吞吐量、成本和能耗等。為了便于比較，假設所有數據中心結構包含相同數量的服務器，并且使用相同類型的端口交換機。

3.1 拓撲性質

網絡拓撲性質對數據中心網絡的性能有重大影響，如直徑可以用于衡量網絡中的通信時延，網絡直徑小代表當前網絡中通信時延低。對分帶寬可以衡量網絡的吞吐量和容錯性，較大的對分帶寬意味著較高的網絡吞吐量和更好的容錯性。表2 列出了FatTree、BCube、DCell、FiConn 和FSDC 的主要拓撲性質，包括可擴展性、靈活性、直徑、對分帶寬、交換機數量和邊的數量等。

由表2 可知，FatTree 的直徑為2 乘以它的拓撲高度，即直徑為2 lb。DCell 和FiConn 直徑的準確值未知，但它們的上界都為2 logN-1。BCube 是所有結構中網絡直徑最小的，其直徑為logN。而FSDC與DCell、FiConn 的直徑相近，為logN。

表2 FSDC 與其他數據中心網絡結構的性質比較Table 2 Characteristics comparison of FSDC with other data center network structures

FatTree和BCube的對分帶寬都為/2，而DCell、FiConn 確切的對分帶寬仍然未知，但它們的下界為/(4 logN) 。FSDC 的對分帶寬的上界為3/4，其值與FatTree、BCube 相似，但大于DCell 和FiConn。

3.2 可擴展性

如表2 所示，BCube 和DCell 的擴展受限于所使用服務器的端口數。當數據中心需要擴展時，需要服務器增加更多的NIC 端口。因為每次擴展都預留了服務器端口，FiConn 的擴展性不會受限于交換機端口數和服務器端口數。FatTree 和FSDC 的擴展性則受限于交換機的端口數，這表示當交換機的端口數被使用完時，將無法添加設備到這些網絡結構中。唯一的解決辦法是把當前網絡使用的交換機更換為端口數量更多的交換機。FatTree 結構能容納的服務器數量過少，如使用196 端口交換機構建的FatTree，最多只能部署1 882 384 臺服務器。表3 展示了FatTree 和FSDC 使用相同端口交換機所構建的網絡能容納的服務器數量，可以看到FSDC 的服務器數量遠高于FatTree。此外，多端口交換機的價格會比較昂貴，如果大量使用來構建數據中心的話會使得成本非常高。因此，隨著規模的不斷擴大，FatTree的構建成本會急速增加。

大多數以服務器為中心的數據中心網絡結構是通過遞歸式構建的，而這些結構會存在這樣一個問題，即，每次擴展服務器的數量會出現海量的增加。例如，使用8 端口交換機構建一個DCell 網絡結構，包含72 臺服務器，包含5 256 臺服務器，而的服務器數量為27 630 792。這種擴展方式不符合現實的需求，并且會帶來大量的資源浪費。如定理2 所述，每次擴展過程中，FSDC 結構的服務器數量可以增加到原來的倍。這意味著，通過選擇不同的參數，FSDC 可以具有更好的可擴展性。

3.3 靈活性

對于FatTree、FiConn、DCell 和BCube 等數據中心網絡結構而言，當確定了構建數據中心網絡結構的交換機類型之后，即交換機端口數確定之后，這些數據中心網絡的結構就已經固定了，其構建靈活性較差。

基于笛卡爾乘積圖的性質，可以通過選擇不同的基礎圖和擴展圖，使用相同類型的交換機來構造不同類型的FSDC 結構。如表3 所示，當使用16 端口交換機可以構建不同類型的FSDC 結構，這些FSDC結構具有不同的服務器數量，其擴展性也有很大的彈性空間。由此可見，FSDC 結構比其他數據中心網絡結構具有更好的靈活性，更適合于構建大規模的數據中心網絡。

表3 服務器數量的比較Table 3 Comparison of the number of servers

3.4 吞吐量

為比較不同結構的吞吐量，本文使用mtCloudSim模擬器進行流量模擬。mtCloudSim 是基于文獻[27]提出來的方法，用于模擬現實中數據中心的數據流的轉發過程。mtCloudSim 使用圖來表示數據中心網絡結構，其中鏈路對應結構中的邊。根據文獻[28]，機架之間不同服務器的往返時間（round-trip time，RTT）約為100 μs。因此可以把流的RTT 設置為從源主機到目標主機之間最短距離乘以100 μs。對于數據集，本文使用了文獻[27]中的綜合流工作負載，其中包含80 000個流，總大小為4 TB。最小的流為1 KB，最大的流為1 GB，主機范圍從0 到4 096，且工作流的產生是隨機生成的。

模擬實驗構建了5 個不同的拓撲結構，分別為FatTree、BCube、DCell、FiConn 和FSDC。實驗中設定不同結構的服務器數量約為5 000 臺，鏈路的傳輸速率設置為2 Gbit/s。圖5 展示了5 個數據中心結構的吞吐量變化與完成轉發所需的時間。由于有大量的交換機和冗余鏈路，FatTree 和BCube 不僅實現了約為300 Gbit/s 的最高帶寬，而且還最先完成了數據的傳輸。DCell 和FSDC 則在使用較少的交換機和鏈路情況下，實現了較好的吞吐量，約為280 Gbit/s。此外FSDC 的數據傳輸時長只比FatTree 和BCube 多10 s。FiConn的吞吐量只有250 Gbit/s，并且傳輸時長比其他結構多出幾十秒。這與FiConn的連接模式，即不同部分之間只有一條鏈路互連，有很大的關系。當鏈路的帶寬完全被占用時，傳輸被嚴重延遲。

圖5 不同結構的吞吐量Fig.5 Throughput of different structures

3.5 成本與能耗

成本和能耗是建立數據中心網絡需要考慮到的兩個重要因素。為了全面分析這兩個因素，本文構建了4 種不同規模的數據中心網絡，其服務器數量分別為1 024、2 048、4 096 和8 192 臺。

表4 中列舉出在構建網絡時所用到的交換機和NIC 設備的價格與能耗。因為網絡規模相等且使用相同類型的服務器，所以可以忽略服務器的價格與能耗。盡管交換機和NIC 的價格隨市場變動，但不同價格不會影響比較結果。

表4 設備價格與能耗Table 4 Price and power consumption of devices

如圖6 所示，BCube 和DCell 的總成本和總能耗比其他的結構更高，這是因為它們的服務器需要裝配具有多端口的NIC。FatTree使用了最多數量的交換機，因此其交換機成本比其他結構更大。而FiConn 和FSDC 則是這些結構中成本和能耗最低的。由于鏈路數量也是一個影響成本的重要因素，圖6 也給出了不同結構的鏈路數量的變化。

從圖6 可知，隨著網絡的不斷擴展，FiConn 和FSDC 的成本、能耗和鏈路數量保持著較低的增長速度。而FSDC 具有比FiConn 更好的靈活性、可擴展性和吞吐量，因此FSDC 結構更適合于以低成本構建一個低能耗的數據中心網絡。

圖6 成本、能耗和鏈路花費的對比Fig.6 Comparison of cost,power,and links

4 結束語

本文提出了一種基于笛卡爾乘積圖的新型數據中心網絡結構FSDC。通過選擇不同的基礎圖和擴展圖，可以實現不同比例的靈活擴展。在分析了FSDC 的拓撲特性的前提下，提出一種基于笛卡爾乘積圖性質的容錯路由算法。最后通過與其他數據中心網絡結構的對比和分析，說明了FSDC 在直徑、對分帶寬和擴展性方面具有良好的平衡。

FSDC 結構是通過兩個環圖之間的笛卡爾積所構建的數據中心網絡結構。未來可以嘗試用其他不同的圖來構建笛卡爾乘積圖，以此獲得具有更好拓撲特性的數據中心網絡。此外，除了以服務器為中心和以交換機為中心的方案外，如何使用笛卡爾乘積圖構建其他類型的數據中心網絡也是未來的工作之一。