面向跨數據中心網絡的節點約束存儲轉發調度方法

林 霄 姬 碩 岳勝男 孫衛強 胡衛生

1(福州大學物理與信息工程學院 福州 350116)2(區域光纖通信網與新型光通信系統國家重點實驗室(上海交通大學) 上海 200240)(linxiaocer@fzu.edu.cn)

隨著新興在線應用與云服務的迅猛發展，跨數據中心的大數據傳輸需求正呈現井噴態勢[1-2].目前典型的大數據傳輸應用，例如數據中心(datacenter, DC)備份、大科學計算等，其傳輸數據量多達數百太字節(TB)，傳輸所需帶寬高達數吉比特每秒(Gbps)，傳輸時間甚至可持續數天[3-5].這對跨數據中心網絡提出了前所未有的挑戰.由于大數據傳輸時間長(數小時到數天)，因此數據往往對傳輸延時不敏感，具有延遲容忍性(delay tolerant).為了應對上述挑戰，許多研究工作嘗試利用延遲容忍性，為大數據的傳輸與調度提供額外靈活性[3-9].

文獻[3-9]的共同特征之一是采用端到端(end-to-end, E2E)連接傳輸大數據.然而，網絡中帶寬資源的使用情況在時間和空間上均呈現不均衡性，這使得在較大網絡范圍內進行E2E數據傳輸難以實現.例如，在跨時區的數據傳輸中，由于不同時區中網絡出現帶寬使用的峰谷時間不一致，跨多個時區的E2E高帶寬通路難以實現.即便在同一個時區中，由于網絡中各條鏈路帶寬可用情況差異甚大，能夠提供給E2E傳輸的時間窗口也很小，難以滿足大數據傳輸要求[10].為承載持續上升的網絡高峰期流量，即便網絡在非高峰期有大量閑置帶寬，數據中心運營商仍然必須不斷從互聯網服務提供商(Internet service provider, ISP)購買更多的帶寬，或者持續升級其專用線路的帶寬容量.

為了克服E2E傳輸面臨的困境，DC存儲被引入數據傳輸路徑.當網絡流量進入高峰時段(例如正午)，將延遲容忍的數據緩存于途經節點(例如DC)，從而避免大、小數據流的帶寬競爭；當網絡流量進入低谷時段(例如凌晨)，充分利用大量閑置帶寬資源繼續傳輸數據，即通過存儲轉發(store-and-forward, SnF)“錯峰傳輸”大數據，已被證明能有效解決跨數據中心間大數據傳輸難題[11].

本文以海量DC存儲與光電路交換(optical circuit switching, OCS)的結合作為研究場景.一方面，OCS可以為大數據提供高帶寬、大容量、低開銷的傳輸通道.另一方面，通過SnF實現數據分段傳輸，避免了傳統OCS面臨的E2E傳輸困境[11-15].然而，存儲的引入將傳統的路由問題變為更加復雜的SnF調度問題.求解該調度問題，不僅需要在空間上尋找傳輸路徑，還需要在時間上規劃何時傳輸、何時緩存.相比傳統路由問題，SnF調度問題求解難度大，計算復雜度高[10].此外，不恰當地調度存儲、帶寬資源，反而導致繞路、網絡資源碎片化等問題，進而惡化網絡性能[13].顯然，SnF效能的發揮取決于能否高效、合理求解SnF調度問題.

本質上，SnF的靈活性取決于數據傳輸路徑上的存儲節點數.每個存儲節點都為調度決策提供一個SnF選項.存儲節點越多，SnF調度方案就越靈活.目前大多數研究工作旨在最大限度地發揮SnF的靈活性，因此將數據傳輸路徑上的所有節點均納入SnF調度決策[10-21].當每個節點接收到數據后，其必須決定是否存儲該數據、需要存儲多長時間，以及應該以何種速率將該數據傳輸到下一節點.這導致調度問題的復雜度隨傳輸路徑跳數的增加呈指數增長[10,15].因此，在大規模網絡、動態網絡場景下，調度問題將變得難以求解.

在實際傳輸過程中，數據通常只需在部分途經節點，而非途經的所有節點，進行SnF即可滿足傳輸需求[13,16].例如，文獻[16]研究表明大多數請求通過1，2次SnF即可到達目的地.此外，在OCS網絡中，每次SnF都需要進行昂貴的光電光(optical-to-electrical-to-optical, OEO)轉換，這會帶來額外的功耗和網絡管控開銷[11].由此，本文將探索如何將部分途經節點而非所有節點納入SnF調度決策，從而降低計算復雜度的方法.

本文的主要貢獻有3個方面：

1) 首先借助理論分析模型，比較了SnF與2種典型E2E傳輸方式的調度性能與復雜度.研究表明，在某些情況下，即使使用單個存儲節點傳輸方式，也可以獲得與多存儲節點傳輸方式近似的調度性能.

2) 進一步擴展理論分析模型，量化分析了參與調度決策的存儲節點數量對SnF調度性能與復雜度的影響.研究表明，在調度過程中，僅將部分途經節點納入調度問題決策，同時擴大時間維度的調度范圍，不僅能獲得更好調度性能，同時能有效降低計算復雜度.

3) 提出了節點約束SnF調度方法.該方法將部分數據途經節點納入調度決策，同時根據所選節點進行拓撲抽象.給定相同的計算復雜度限制，該方法可以對更大時間范圍內的網絡狀態進行搜索，比使用所有節點進行調度的現有調度方法作出更優的調度決策.仿真表明，該方法在阻塞率和運算時間方面優于現有調度方法.

1 相關工作

1.1 現有SnF調度方法

本文根據調度策略，將現有SnF調度方法分為2類：1)基于最大靈活性(max flexibility, MF)策略的調度方法，該策略旨在最大化SnF的調度靈活性，因此其將所有網絡節點都納入調度決策；2)基于節點約束(node constraint, NC)策略的調度方法，該策略旨在以犧牲一定的調度靈活性為代價簡化調度問題，因此其僅將部分網絡節點納入調度決策.圖1對現有SnF調度方法進行分類總結.

Fig. 1 Classification of existing SnF scheduling methods圖1 已有SnF調度方法及其分類

1) 基于MF策略的SnF調度方法

多數學者旨在充分利用現有網絡基礎架構，最大程度地發揮SnF調度的靈活性，即采用基于MF的調度策略.這些學者針對所有網絡節點均部署有存儲的網絡場景開展研究，即完全部署(full place-ment)網絡場景[10-23].

在此基礎之上，學者們提出的SnF調度方法會將數據傳輸路徑上的所有節點均納入調度決策[10-23].因此，每個節點都為SnF提供了潛在可能.在這些研究工作中，SnF調度問題被建模為優化問題，例如線性規劃問題和網絡流量問題[10-13,18-21]，并且采用經典的優化算法或啟發式算法來求解問題，實現路由、調度與資源分配的最優解.現有以優化建模為基礎的SnF調度方法復雜度較高，更適合解決小規模網絡、靜態網絡場景下的離線調度優化問題.靜態網絡場景中，請求的數量和到達時間都是提前已知的.然而，文獻[14]的研究表明，SnF調度問題的規模會隨著傳輸路徑跳數的增加而呈指數增長.這意味著當調度問題規模較大時，問題可能難以求解.因此，上述SnF調度方法難以為大規模網絡、動態網絡場景提供實時調度.在動態網絡場景中，請求是隨機到達網絡，請求的數量和到達時間都是隨機的.一部分學者同樣也針對完全部署網絡場景開展研究.但是，他們對調度過程進行了部分限制[22-23].文獻[22]旨在通過最少的SnF次數來完成數據傳輸.因此，文獻[22]所提出的調度方法是采用貪婪算法，從允許一次SnF開始逐次遞增SnF次數，直到找到可行的SnF方案為止.文獻[23]旨在減輕存儲系統的高速讀寫負擔，所以僅允許源節點緩存數據.然而，文獻[22-23]均未研究存儲節點數對SnF的性能與復雜度的影響.

2) 基于NC策略的SnF調度方法

采用基于NC的調度策略以犧牲一定的調度靈活性為代價，簡化調度問題.其中，一部分學者針對完全部署網絡場景開展研究[24-25]；另一部分學者針對僅部分網絡節點部署有存儲的網絡場景展開研究，即部分部署(partial placement)的網絡場景[26-28].

在完全部署網絡場景下，文獻[24-25]比較了SnF和提前預約機制(advance reservation, AR).AR可等價于僅有源節點具備存儲功能的一個SnF特例.文獻[24-25]研究表明，當網絡負載較高時，與SnF相比，AR所能帶來的性能增益是有限的.

在部分部署網絡場景下[27]，文獻[26]針對3節點串聯網絡展開研究，其中僅有中繼節點具備SnF能力.文獻[26]將SnF調度問題建模為單跳、單路徑傳輸問題，但并未考慮任何路由或調度問題.在文獻[27]中，當E2E光路無法建立時，調度方法將嘗試從源節點建立光路到最近的存儲節點，以便緩存數據，等待一段時間后再嘗試建立從存儲節點到目的地的光路.盡管數據傳輸路徑可能會途經多個中繼節點，但是只有一個中繼節點是存儲節點.這就極大限制了SnF的靈活性，以及所能帶來的性能增益.此外，文獻[27]將存儲部署問題轉化為設施選址問題(facility location problem)，并通過拓撲中心性求解該問題.顯然，存儲部署主要取決于網絡拓撲特征，但并未考慮任何調度復雜度問題.文獻[28]旨在以最小的存儲使用量獲得最大網絡數據傳輸能力.文獻[28]將路由問題與存儲使用問題轉化為最大流問題(maximum flow problem)，從而實現對上述2個問題的聯合優化.文獻[28]同樣也沒有考慮存儲節點數量對于調度復雜度的影響.

3) 現有研究工作的總結

多數工作主要研究基于MF策略的SnF調度方法.這些工作所提出的調度方法更適合小規模網絡、靜態網絡場景下的離線調度優化，難以為大規模網絡、動態網絡場景提供實時調度.另一部分工作研究如何使用源節點或部分中繼節點進行調度，即采用基于NC策略的SnF調度方法.然而，這些研究工作旨在于減少存儲部署或使用量，并未考慮存儲節點數量對于調度性能和復雜度的影響.顯然，調度方法的設計本質上是對性能與復雜度的折中.設計高效的SnF調度方法應當仔細考慮用于調度決策的存儲節點數.然而，現有的研究工作尚未充分考慮該問題.

與現有基于MF策略的調度方法不同，本文所提出的新型調度方法將NC調度策略融入基于時移多層圖(time-shifted multilayer graph, TS-MLG)[16]的路由調度，有效減少了調度決策過程需要的存儲節點數量.在此基礎之上，新型調度方法使用基于存儲節點的拓撲抽象，在保證調度性能的同時減小調度問題規模、降低調度問題求解難度.現有基于NC策略的調度方法通常固定選擇源節點或部分中繼節點作為存儲節點.與此不同，新型調度方法根據節點對之間路由跳數的不同，選擇合適的存儲節點數，獲得了低復雜度、高調度性能，更適合為大規模網絡、動態網絡場景提供實時、高效的調度服務.

1.2 時移多層圖

時移多層圖[16]是一種面向SnF的路由調度框架，是由多個層組成的圖,如圖2所示.TS-MLG中每層都是網絡拓撲在某個時刻的快照，反映了當時的網絡狀態.TS-MLG通過一系列拓撲快照，捕捉了隨時間變化的網絡狀態.例如，TS-MLG的最頂層表明時刻t0鏈路E—F沒有可用帶寬.第2層表明時刻t1鏈路E(1)—F(1)有可用帶寬.此外，TS-MLG引入時間鏈路(temporal link)和空間鏈路(spatial link)的概念.請求穿越時間、空間鏈路分別表示數據緩存和數據傳輸.僅需對TS-MLG進行最短路由，即可獲得一條“穿越時空的端到端”路徑，同時實現空間路由與時間調度的融合調度、帶寬與存儲資源的聯合分配，極大簡化了SnF調度問題的求解過程.

假設傳輸請求r在時刻t0到達網絡，要求從節點A向節點E傳輸數據.然而，在時刻t0無法進行E2E傳輸.但通過對圖2所示的TS-MLG進行路由搜索(例如使用Dijkstra算法)，即可找到路徑A—F—F(1)—E(1)，其中節點F是中繼存儲節點.顯然，借助TS-MLG，時空二維的SnF調度問題被轉變為一維的路由問題.

Fig. 2 Time-shifted multilayer graph (TS-MLG)圖2 時移多層圖(TS-MLG)

隨著請求的到達和離開，網絡狀態將發生改變，TS-MLG的層數也將發生動態改變.當網絡產生新狀態，新層將被添加到TS-MLG.隨著時間流逝，當現有網絡狀態超時，相應的層將被從TS-MLG中移除.

路由算法的計算復雜度通常取決于網絡拓撲的規模.TS-MLG的規模等于網絡拓撲節點數乘以TS-MLG的層數.因此，TS-MLG的層數很大程度上決定了對其進行路由搜索的計算復雜度.由于數據流的突發性可能會導致TS-MLG的層數出現短時激增，使得后續請求的路由復雜度陡然增大.為了限制復雜度，用于路由的層數必須予以限制.因此，請求是否能被網絡接收取決于請求是否能在給定的TS-MLG層數內找到有效路徑.

2 不同數據傳輸方式的比較研究

立即預約(immediate reservation, IR)和提前預約(advance reservation, AR)是OCS網絡中2種典型E2E數據傳輸方式[29].本節首先簡要介紹了IR，AR，SnF的基本原理，隨后利用理論模型比較分析了3種數據傳輸方式的性能與復雜度.本文所涉及的主要符號及其含義如表1所示:

Table 1 Table of Notations

在IR中，請求是否能被接收取決于當前網絡帶寬是否能夠提供E2E傳輸.當請求到達網絡時，網絡調度器(scheduler)必須立即根據網絡當前的帶寬資源可用情況作出調度決策.在AR中，請求的傳輸可以被推遲，并等待可用的E2E連接出現再開始傳輸.源節點具備推遲請求傳輸的能力.因此，當請求到達網絡時，網絡調度器根據網絡當前與未來的帶寬資源可用情況作出調度決策.在SnF中，每個節點都可以進行SnF.因此，當請求到達網絡時，網絡調度器根據網絡當前與未來的帶寬與存儲資源可用情況作出調度決策.IR與AR可等價為SnF在沒有任何節點或僅有源節點具備存儲能力時的2種特例.

2.1 建模分析

本文擴展了文獻[14]的分析模型，比較IR，AR，SnF.假設固定路由R={s,i1,i2,…,iN-2,d}，其中s是源節點，d是目的節點，N表示固定路由的節點總數，且N≥2.基于TS-MLG的IR，AR，SnF路由模型，如圖3所示.假定L層可以用于調度.

Fig. 3 Routing models of the three transfer manners圖3 3種傳輸方式的路由模型

IR的TS-MLG僅由一層組成，如圖3(a)所示.這是因為IR中僅考慮了當前網絡狀態.在圖3(b)中，AR的TS-MLG由L層組成，因為AR需要同時考慮當前和未來的網絡狀態.此外，僅源節點通過時間鏈路相互連接.在圖3(c)中，由于每個節點都可以進行SnF，所以TS-MLG包含多層、多條時間鏈路.令d(l)表示TS-MLG中位于第l層的目的節點d，其中l∈[1,L].在本文中，備選路徑(alternate path)定義為TS-MLG中從節點s到節點d(l)的路徑，其中l∈[1,L].備選路徑并未考慮每條鏈路的資源可用性.有效路徑(viable path)定義為在每條空間或時間鏈路都具備所需帶寬或存儲資源的備選路徑.

借助TS-MLG，本文將調度問題轉變為路由問題.求解路由問題的簡單方法之一就是列舉從s到d的所有備選路徑，并從中搜尋有效路徑.因此，備選路徑數量決定了路由問題的計算復雜度.例如，在圖3(a)中，節點對(s,d)之間只有一條備選路徑.而隨著層數增加，備選路徑可以到達不同d(l).如圖3(b)(c)所示，(s,d)之間的備選路徑數隨層數增加而增加.P(s,d)(N,L)定義為從s到d(LL)的所有備選路徑的總數，其中LL={1,2,…,l,…,L}.本文采用P(s,d)(N,L)來衡量SnF調度問題的計算復雜度.

此外，SnF的主要思想是采用存儲置換帶寬.因此，分析模型需要進一步考慮網絡資源的可用性.預約失敗率F(s,d)(N,L)定義為未能從數量為P(s,d)(N,L)的備選路徑集合中找到有效路徑的概率.令pb表示請求未能在一條空間鏈路上找到所需帶寬的概率；ps表示請求未能在一條時間鏈路上找到所需存儲的概率.本文采用F(s,d)(N,L)來衡量SnF調度問題的潛在調度性能.

(1)

(2)

N和L決定了TS-MLG的規模.增加N表示選擇一條更長的路由傳輸數據，而增加L表示擴展時間維度的調度范圍(例如允許更長的數據緩存時間).

2.2 調度性能與復雜度分析

本文借助P(s,d)(N,L)和F(s,d)(N,L)對3種傳輸方式的復雜度和調度性能進行了比較研究.

Table 2 Complexity Comparison Based on P(s,d)(N,L)

給定N，L，pbps，圖4比較了3種傳輸方式的預約失敗率，即F(s,d)(N,L).圖4(a)～(c)假設ps?pb.因為在典型的跨數據中心網絡中帶寬資源較為稀缺，而存儲資源較為豐富.在某些城域網應用場景中，例如傳統通信機房DC化(center office re-architected as datacenter, CORD)和面向邊緣計算的微型DC，有限的存儲資源可能不足以滿足大數據傳輸需求.因此，在這些網絡場景中，pb和ps的取值值得未來繼續研究.

之前的研究均考慮ps?pb的情況.為了不失一般性，本節進一步考慮ps?pb的情況.圖4(d)假設pbps=0.010.3.此時，帶寬資源充足，但是存儲資源稀缺.此時，增大L難以有效降低與

Fig. 4 Performance comparison based on F(s,d)(N,L)圖4 基于F(s,d)(N,L)的調度性能比較

2.3 分析與總結

借助復雜度與調度性能分析模型，本節比較了IR，AR，SnF這3種數據傳輸方式，主要發現如下：

1) 雖然IR和AR的復雜度較低，但對于大規模網絡、動態場景，其性能可能不足.SnF的性能優于IR和AR，但代價是復雜度較高.

2) 當N，L，pb較小時，AR和SnF之間的性能差距較小.這表明，在這種情況下，使用1個存儲節點參與調度即可獲得較好性能，而無需多個存儲節點參與調度.但隨著L的增大，AR和SnF的性能差距急劇擴大.這表明，當允許調度器在更大的時間范圍內進行資源調度時，SnF比AR更有優勢.

3) 相比IR和AR，SnF具備的高性能與高復雜度源于其能夠使用更多的存儲節點參與調度決策.因此，有必要進一步研究存儲節點數對SnF的影響.

3 存儲節點數量對SnF的影響

本節首先擴展分析模型以量化存儲節點數對SnF的影響；然后將MF調度策略與NC調度策略進行比較研究.

3.1 建模分析

Fig. 5 SnF model based on NC scheduling strategy (Ns storage nodes and Ls layers, 1

假設固定路由R={s,i1,i2,…,iN-2,d}.令Ns表示R上的存儲節點數.目的節點不能用于數據緩存.基于NC調度策略的SnF模型，簡稱NC模型，如圖5所示，其中R上的前Ns個節點是存儲節點，Ls層可以用于調度.基于MF調度策略的SnF模型，簡稱MF模型，如圖3(c)所示.L和Ls分別表示MF模型和NC模型的層數.

當Ns=1且源節點是存儲節點時，NC模型等價于圖3(b)中所示的AR模型.當Ns=N-1時，NC模型等價于MF模型，如圖3(c)所示.當1

圖6 備選路徑數和預約失敗率

(3)

給定目的節點d(l)，從s到d(l)的所有備選路徑都具有相同的空間跳數(即N-1)和時間跳數(即l-1)，并且與具體存儲節點部署方案無關.由于每條時空鏈路的pb和ps設為相互獨立，因此這些備選路徑也具有相同的預約失敗率，且與存儲節點部署方案無關.

(4)

詳細證明參見附錄A.

3.2 調度性能和復雜度分析

表3表明，Rp和Rc均隨Ns增加而增加.隨著pb減小，Rp的增幅更加明顯.這表明，獲得指定性能所需的Ns值隨著pb的減小而減小.例如，當pb=0.3時，至少需要4個存儲節點(Ns=4)才能實現Rp>0.9.但是，當pb減小到0.1時，只需要3個存儲節點(Ns=3)就能實現Rp>0.9.同時，當Ns從4降低到3時，Rc從0.625降低到0.357.與MF模型相比，當pb=0.1時，NC模型僅需要35.7%的原始復雜度，即可獲得超過90%的原始性能.這意味著僅將部分存儲節點納入調度，不僅可以獲得理想的性能，而且能有效減輕調度過程的計算負擔.當N=10時所得結果與當N=6時所得結果的變化趨勢相似.

Table 3 Rc and Rp when Ls=L and ps=0.01

盡管Rp和Rc均隨Ns增加，但Rp和Rc之間存在間距,該間距隨Ns而變化.因此存儲節點的最佳數量應當使得Rp最大化而Rc最小化.但是，由于1≤Ns≤N-1，所以該間距變化始終受限.本節繼續探索如何進一步擴大該間距，突破上述限制的方法.

繼續研究Ls>L的情況,假設N=10，L=4，ps=0.01.本節將研究Ls變化如何影響Rp和Rc,結果如表4所示.給定Ls=L=4，當Ns從2增大到4時，Rc從0.045增加到0.159.同時，當pb=0.1時，Rp從0.112增加到0.818；而當pb=0.3時，Rp從0.250增加到0.522，如表4第1行所示.可見，當pb=0.1時，增加Ns可以將Rp增加到0.818，但代價是Rc=0.159.相比之下，給定L=4且Ns保持2，當Ls從4增大到7時，Rc從0.045增加到0.127；同時，當pb=0.1時，Rp從0.112增加到29.117；而當pb=0.3時，Rp從0.25增加到0.488，如表4第4列所示.顯然，與增大Ns相比，增大Ls不僅可以提高Rp，還能保持較低的Rc.

Table 4 Rc and Rp when Ls≥L and ps=0.01

3.3 分析與總結

借助分析模型，本節研究了存儲節點數量對于SnF調度性能與復雜度的影響，主要發現如下：

1) 在時間維度的調度范圍不變的前提下(即Ls=L)，僅將傳輸路徑途經的部分節點而非所有節點納入調度決策，雖然可以減輕調度過程的計算負擔，但是調度性能也會隨之降低.

2) 當ps?pb時，擴展時間維度的調度范圍比使用更多存儲節點參與調度更有助于提高調度性能.但是，擴展時間調度范圍將導致請求經歷更長延遲.

3) 當NsL時，NC策略的調度性能不僅可能超過MF策略，而且能保持較低的復雜度.換而言之，僅將傳輸路徑沿途的部分節點而非所有節點納入調度決策，有可能同時實現高性能、低復雜度.

4) 設計高效的SnF調度方法應當聯合優化Ns和Ls，以到達性能與復雜度的最佳折中.

4 節點約束存儲轉發調度方法

4.1 網絡模型與主要假設

本文以波分復用(wavelength-division multi-plexing, WDM)網絡為基礎架構的跨數據中心網絡作為研究場景.借助基于軟件定義網絡(software-defined networking, SDN)的傳輸感知優化技術[30]，網絡運營商可以將光網絡基礎設施與DC資源有效整合，以實現跨DC的大數據傳輸.光纖中的帶寬資源按照波長通道分配.每個DC的光交換平臺均具備OEO轉換和波長轉換能力.DC可以將大數據緩存于存儲集群.存儲集群具備繞行企業級防火墻的能力，從而為大數據傳輸提供高速通道[31-32].如圖7所示，當WDM2較為繁忙時，E2E傳輸難以保障.來自DC1的大數據通過WDM1傳輸并存儲于DC2的存儲群集.當WDM2較為空閑時，大數據通過WDM2傳輸到DC3.假設每個請求占用一個波長進行數據傳輸.與傳輸延遲相比，數據傳播延遲、網絡處理開銷(例如光網絡重構所需的時間)可以忽略不計[5,33].假設存儲集群的數據讀寫速度等于單波長的傳輸容量.文獻[34]指出大數據適宜使用專門OCS資源提供傳輸服務，所以本文假設部分網絡資源專用于承載大數據流量.

Fig. 7 SnF scheme for inter-DCNs圖7 面向跨數據中心網絡的SnF傳輸方案

4.2 算法研究

受第3節的研究啟發，本文將NC調度策略與拓撲抽象融入基于TS-MLG的路由調度，從而實現NsL的組合.由此，本文提出了節點約束SnF(node-constraint SnF, NC-SnF)調度方法.

NC-SnF方法的主要思想源于2方面.首先，在請求到達網絡時，NC-SnF方法僅將部分傳輸路徑途經節點納入調度決策.其次，根據所涉節點，NC-SnF方法通過將TS-MLG中連接這些節點的空間鏈路合并，并對具有相同網絡狀態的層壓縮，從而實現拓撲抽象.一方面，NC-SnF方法縮小了TS-MLG規模，從而減輕了調度過程的計算負擔；另一方面，當可用于路由的層數有限時，相比沒有拓撲抽象的傳統調度方法，NC-SnF方法可以搜索時間上距離當前時刻更遠的層.換言之，給定相同計算復雜度上界，相比于傳統調度方法，NC-SnF方法本質上能夠為請求提供更大的時間調度范圍.因此，NC-SnF方法在降低計算復雜度的同時保持良好的調度性能.

NC-SnF方法分為5個步驟.每個節點對(i,j)均已預先計算K條最短路由，并將備選路由存儲在集合R(i,j).假設請求r的源-目的節點對為(s,d).

步驟1. 算法1第②行從集合R(s,d)中選擇一條從s到d的固定路由Rk，其中Rk∈R(s,d)且|Rk|=Nk.

步驟2. 算法1第③行根據存儲節點選擇方案，在Rk上選擇的Ns個節點用于SnF調度.令α表示Rk上可用于調度節點數占節點總數的百分比，其中0<α≤1.Ns=[(Nk-1)×α].集合S={s,I1,I2,…,Ii,…,INs-1,d}，其中Ii表示被選存儲節點，Ii∈Rk且|S|=Ns+1.集合S表示Rk被存儲節點劃分為Ns個片段.集合S的第1個節點是s，因為已有研究表明，在多數調度過程中，源節點是首個發生SnF的節點[16,24-25].為簡單起見，本文假設其他被選節點等間隔分布于Rk.網絡級存儲節點選擇或部署方案是一個有趣但復雜的問題，值得在未來深入研究.

步驟3. 算法1第④行根據Rk將原始TS-MLG圖G縮減為規模較小的圖G′.具體而言，圖G′僅包含Rk中的節點以及連接這些節點的鏈路.

步驟4. 算法1第⑤行根據集合S運行算法2對圖G′進行拓撲抽象，以獲得抽象壓縮后的子圖G″.

算法1.NC-SnF調度方法.

輸入：r={s,d}，圖G，K，R(s,d)，α；

輸出：Path和Find.

① fork=1;k≤K;k++ do

② 選擇一條從s到d的路由Rk，其中Rk∈R(s,d)且|Rk|=Nk；

③ 根據存儲節點選擇方案在Rk中選擇Ns個節點，得到路徑片段集合S={s,I1,I2,…,Ii,…,INs-1,d}，其中|S|=Ns+1，Ii∈Rk和Ns=[(Nk-1)α]；

④ 根據Rk將圖G縮減為其子圖G′；

⑤ 運行算法2，根據集合S對圖G′進行拓撲抽象，并獲得抽象壓縮后子圖G″；

⑥ 在圖G″上運行BFS算法，尋找有效路徑Path；

⑦ if找到Paththen

⑧ returnPath和Find=True；

⑨ end if

⑩ end for

算法2的主要思想是根據集合S實現拓撲抽象.該算法主要包括3個步驟：

步驟1. 算法2第①行創建1個輔助圖G″=(V″,E″)，其中V″=S和E″=?.

步驟2. 算法2第②～⑧行將圖G′中每個路徑片段內的空間鏈路狀態合并為圖G″中的邏輯鏈路.LR表示用于路由的層數.LLR表示這些層的集合，LLR={l1,l2,…,lj,…,lLR}.對于圖G′中第lj層的每個路徑片段{Ii,Ii+1}，算法2第④～⑥行找到在{Ii,Ii+1}內具有最小剩余帶寬的空間鏈路ei，將ei添加到邏輯鏈路〈Ii,Ii+1〉；同時將圖G′中屬于節點Ii和節點Ii+1的時間鏈路添加到圖G″.

算法2.基于存儲節點的拓撲抽象算法.

輸入：圖G′，LR，S；

輸出：圖G″.

① 創建輔助圖G″=(V″,E″)，其中V″=S和E″=?；

② for 圖G′中所有層LLR={l1,l2,…,lj,…,lLR} do

③ for 圖G′中第lj層的每一個路徑片段{Ii,Ii+1} do

④ 在圖G′中第lj層中找到從節點Ii到節點Ii+1具有最小剩余帶寬的空間鏈路ei；

⑤ 將ei添加到圖G″中第lj層的邏輯鏈路〈Ii,Ii+1〉；

⑥ 將連接圖G′中的節點Ii和節點Ii+1的時間鏈路添加到圖G″；

⑦ end for

⑧ end for

⑨ for 圖G″中的所有層LLR={l1,l2,…,lj,…,lLR} do

⑩ iflj+1==ljthen

4.3 算法運行示例

Fig. 8 Comparison of the reduced graph G′ with different Ns圖8 不同Ns下簡化圖G′比較

本節將通過圖8和圖9展示NC-SnF方法是如何減小TS-MLG的規模.原始TS-MLG圖G如圖2所示.圖G由多層組成，每層包含6個節點.假設請求r需要從節點A向節點D傳輸數據.路由Rk={A,B,C,D}被用于請求r的傳輸.首先，根據Rk將圖G縮減為子圖G′，如圖8(a)所示.圖G′由4層組成，每層包含4個節點.假設α=0.4，可得Ns=2.根據4.2節所述存儲節點選擇方案，選擇節點A與節點C參與調度，即S={A,C,D}.因此，省略連接節點B的時間鏈路，如圖8(b)所示.

隨后，運行算法2合并節點A和節點C之間的空間鏈路，生成邏輯鏈路〈A,C〉.合并圖G″由4層組成，每層包含3個節點，如圖9(a)所示.圖9(a)中每一層邏輯鏈路〈A,C〉表示在該時刻從節點A到節點C的最小剩余帶寬.例如，在圖8(b)中，空間鏈路A—B在t=0時剩余帶寬為0，而空間鏈路B—C在t=0時剩余帶寬為1.因此，在圖9(a)中，邏輯鏈路〈A,C〉的帶寬在t=0時為0.

Fig. 9 The merged graph G″ vs the condensed graph G″ 圖9 合并圖G″和壓縮圖G″比較

在圖9(a)中，圖G′中t=0和t=15的層表示相同的網絡狀態，即邏輯鏈路〈A,C〉繁忙.這些層不僅無法提供更多有用信息，還會給搜索帶來額外的計算負擔，因此是冗余層.算法2將t=15的層移除，得到壓縮圖G″，如圖9(b)所示.顯然，通過運行NC-SnF方法，可以極大減小TS-MLG的規模.

4.4 資源預約窗口研究

為了限制計算復雜度，請求只能在給定層數(即LR)內搜索有效路徑.LR的值決定了時間維度的調度搜索范圍.因此，算法2合并、壓縮鏈路與層之后，時間調度范圍會相應地發生改變.為了對此展開研究，資源預約窗口定義為最頂層與第LR層(即可以用于路由的最后一層)之間的時間間隔.資源預約窗口的大小與LR、層與層之間的時間間隔均有關.

Fig. 10 Comparison of the reservation windows in the graphs with different scheduling strategies (LR=3)圖10 不同策略下資源預約窗口比較(LR=3)

本節比較了圖8(a)所示的圖G′的資源預約窗口與圖9(b)所示壓縮后G″的資源預約窗口.假設LR=3.圖10展示了不同圖的資源預約窗口.在圖10(a)中，G′的資源預約窗口是最頂層和第3層之間的時間間隔，即t=0和t=20的層間距.因此，圖10(a)中的窗口大小為20.在圖10(b)中，G″的資源預約窗口同樣也是最頂層和第3層之間的時間間隔.但是，由于t=15的層被移除，第3層不再是t=20的層，而是t=40的層.因此，圖10(b)的窗口大小為40.假設請求r在t=0到達網絡，需要從節點A向節點D傳輸數據.請求r無法在圖10(a)所示的窗口內找到有效路徑，因此r被阻塞.相反，在圖10(b)所示的窗口內，有效路徑A—A(2)—C(2)—C(3)—D(3)可用于傳輸請求r.

簡而言之，給定相同計算復雜度限制，與傳統調度方法相比，NC-SnF方法能夠提供更大的資源預約窗口，因此有助于降低請求阻塞率.

4.5 計算復雜度研究

TS-MLG的規模決定了路由算法的計算復雜度.文獻[16]給出的復雜度為O((V×LR)2),V表示網絡拓撲中的節點總數.NC-SnF方法使用BFS算法對壓縮后的TS-MLG圖G″進行有效路徑搜索.BFS算法的復雜度為O(V″+E″)，V″表示圖G″的總節點數，E″表示圖G″的總邊數.在最壞的情況下，V″=LR×Ns；而E″=(LR-1)×Ns+(Ns-1)×LR.因此，NC-SnF方法的復雜度為O(K×LR×Ns).

5 結果與討論

本節模擬動態網絡環境，比較NC-SnF方法與傳統的SnF調度方法[12](即MF-SnF方法).

本節采用了4.1節的主要假設，并在研究中使用美國國家科學基金會網絡(National Science Foundation Network, NSFNET)拓撲.為簡單起見，放寬了存儲容量限制.在調度過程中不考慮存儲容量制約，網絡調度器僅根據請求是否能在給定層數(即LR)內找到有效路徑，決定請求是否被接受.假設請求到達是獨立的，并在所有節點對之中均勻分布；請求的到達服從到達率為λ的泊松分布；請求的持續時間服從服務率為μ的負指數分布.網絡負載ρ=λμ.鏈路容量，即每條鏈路的波長數，用w表示.每個節點對之間3條最短備用路由，即K=3.傳輸路徑中參與調度的節點數百分比為α.當α=1時，傳輸路徑中的所有節點均參與調度.此時，NC-SnF方法等效于MF-SnF方法.為簡單起見，假設α=0.4和α=0.6.每次仿真實驗產生500 000個請求，獨立重復20次并取平均值.

5.1 網絡性能研究

本節首先研究阻塞率(blocking probability)如何隨ρ增大而改變.可以通過增加λ或減小μ來增大ρ.由于2種情況下所得結果相似，因此在以下仿真實驗中λ=1，通過改變μ來改變ρ.

仿真結果如圖11所示.當ρ從10增加到60時，阻塞率增加.在圖11(a)中，給定w=4，LR=4，當ρ=10時，NC-SnF方法所得阻塞率為0，而MF-SnF方法所得阻塞率為5.05×10-6.隨著ρ的增加，NC-SnF方法開始出現阻塞.α值越大，阻塞率的增幅越顯著.圖11(b)中結果遵循相似的趨勢，但是請求阻塞出現在較大的ρ值上，這是由于圖11(b)中的w比圖11(a)中的w大.

Fig. 11 Blocking probability under various ρ (LR=4)圖11 不同網絡負載ρ下的阻塞率(LR=4)

直觀上，存儲節點數越少，阻塞率越高.然而，圖11卻顯示相反的結果，即存儲節點數越少，NC-SnF方法獲得的阻塞率反而越低.為了理解該結果，本節將研究重點放在圖11(a)，研究其他網絡性能指標如何隨ρ變化，結果如圖12所示.活躍請求(active request)定義為已被網絡接受但尚未完成傳輸的請求.請求緩存率(ratio of stored requests)定義為緩存請求數與請求總數的比率.延遲定義為從請求到達網絡直到請求結束傳輸的時間間隔.

Fig. 12 Network performance under various ρ (w=4, LR=4)圖12 不同網絡負載ρ下的網絡性能(w=4，LR=4)

在圖12(a)中，當ρ從10增加到30時，NC-SnF方法和MF-SnF方法的鏈路利用率相似.當ρ超過35時，α=0.6的NC-SnF方法所得鏈路利用率明顯高于其他方法，而MF-SnF方法的鏈路利用率低于其他方法.相反，在圖12(b)中，當ρ>30時，α=0.4的NC-SnF方法的活躍請求量最多.這表明，當網絡負載為中等或更高時，采用α=0.4的NC-SnF方法，網絡可以同時容納更多請求.α值越小，網絡中容納的請求越多.這是因為α=0.4的NC-SnF方法能比其他方法提供更大的資源預約窗口，如圖12(c)所示.α值越小，存儲節點越少，合并的空間鏈路就越多.這也增加了在TS-MLG中找到冗余層的機會.給定LR值，在壓縮更多冗余層的情況下，層與層的時間間距變大，NC-SnF方法也就可以在更大的時間范圍內搜索可用資源.因此，α的值越小，越多請求可以通過SnF到達目的節點，所以請求緩存率也越高，如圖12(d)所示.簡言之，得益于拓撲抽象，請求使用NC-SnF方法比使用MF-SnF方法更容易被傳輸.然而，隨著資源預約窗口增大，請求也將經歷更長的延遲，如圖12(e)所示.

隨著資源預約窗口的擴大，更多的請求可以通過SnF選擇更短的路由，而不是通過較長的路由繞行.圖12(f)表明成功傳輸請求的平均空間跳數.與α=0.6相比，α=0.4的NC-SnF方法產生的請求空間跳數更短.當ρ∈[45,60]時，與NC-SnF方法相比，MF-SnF方法產生的請求空間跳數更短.這是因為MF-SnF方法的阻塞率高于NC-SnF方法.對于需要通過較長的路由繞行才能完成傳輸的請求，MF-SnF方法難以滿足這些請求的需求.隨著這類請求被阻塞，MF-SnF方法產生的平均空跳明顯短于NC-SnF方法.

5.2 基于存儲節點的拓撲抽象算法研究

得益于拓撲抽象算法(即算法2)，空間鏈路和冗余層被合并和壓縮，使得NC-SnF方法能夠提供更大的資源預約窗口.為了驗證算法2的作用，本節比較了原始NC-SnF方法和沒有拓撲抽象功能的NC-SnF方法(即簡化NC-SnF方法).在簡化NC-SnF方法中，算法2被禁用.因此，BFS算法直接對簡化圖G′而非壓縮圖G″進行有效路徑搜索.此處，w=4，LR=4.仿真結果如圖13所示:

Fig. 13 The original NC-SnF method vs the NC-SnF method disabling the topology abstraction (α=0.4)圖13 原始NC-SnF方法與禁用拓撲抽象功能的NC-SnF方法比較(α=0.4)

給定α=0.4，原始NC-SnF方法的阻塞率優于簡化NC-SnF方法，如圖13(a)所示.這是因為原始NC-SnF方法中的資源預約窗口隨ρ增大而增大，而簡化NC-SnF方法中的資源預約窗口幾乎保持恒定，如圖13(b)所示.

隨后，繼續對比簡化NC-SnF方法與MF-SnF方法，如圖13(a)所示.MF-SnF方法優于簡化NC-SnF方法.這是因為一方面沒有了拓撲抽象功能，簡化NC-SnF方法的資源預約窗口明顯小于MF-SnF方法；另一方面MF-SnF方法能夠比簡化NC-SnF方法使用更多存儲節點，因此MF-SnF方法的調度更加靈活.

5.3 算法計算時間研究

本節研究了TS-MLG的節點數和層數是如何影響NC-SnF方法的算法計算時間.本節使用鏈路密度為0.6的隨機生成拓撲進行仿真實驗.鏈路密度定義為網絡拓撲中任意2個節點之間存在邊的概率.V表示網絡拓撲的節點數.

表5和表6描繪了不同調度方法對給定的TS-MLG進行一次路由搜索的平均計算時間.在表5中，LR=10.計算時間隨V的增加而增加.在表6中，V=10.計算時間隨著LR的增加而增加.表5和表6表明，α值越小，計算時間的增幅越小.這是因為當α值較小時，需要搜索的TS-MLG規模也相應減小.

Table 5 Computation Time Under Various V (LR=10)

Table 6 Computation Time Under Various LR (V=10)

5.4 不同網絡拓撲研究

Fig. 14 Blocking probability in different topologies圖14 不同網絡拓撲下的阻塞率

本節繼續研究了不同的網絡拓撲中阻塞率隨ρ的變化情況.選取19個節點39條鏈路的泛歐洲全光網(optical pan-european network, OPEN)和24個節點43條鏈路的美國骨干網絡(US backbone network, USNET)作為研究對象.此處，w=4，LR=4.圖14(a)(b)分別描述了在OPEN和USNET中不同ρ下的阻塞率.圖14的結果與圖11的結果類似.因此，在不同的網絡拓撲中，NC-SnF方法的阻塞性能均優于MF-SnF方法.然而，圖14中NC-SnF調度方法獲得的阻塞率略高于圖11.例如，當α=0.4和ρ=20時，在NSFNET中NC-SnF方法獲得的阻塞率為1.32×10-6；而在OPEN和USNET中NC-SnF方法獲得的阻塞率分別為4.04×10-6和1.07×10-4.這是因為OPEN和USNET的拓撲規模大于NSFNET.因此，OPEN和USNET中給定節點對之間的路由跳數多于NSFNET.給定相同的α，NC-SnF方法在OPEN和USNET中每條路由上選定的存儲節點數多于NSFNET.根據4.3節討論可知，借助拓撲抽象算法，選定的存儲節點數越少，所獲得的壓縮子圖規模就越小，相應的資源預約窗口也就越大.因此，相比OPEN和USNET，NSFNET中NC-SnF方法可獲得更大的資源預約窗口，進而獲得更低的阻塞率.

6 總 結

本文將SnF與IR和AR進行了對比.研究表明，選擇合適數量的存儲節點用于調度決策，實際上是調度性能與復雜度之間的折中問題.為此，本文提出了分析模型，揭示了存儲節點數對SnF復雜度與性能的影響.研究發現，在一定條件下，NC調度策略能夠在降低復雜度的同時獲得比傳統MF調度策略更好的調度性能.

受此啟發，本文提出NC-SnF調度方法，只將傳輸路徑上的部分節點納入調度決策.同時，NC-SnF方法引入了基于存儲節點的拓撲抽象.與傳統的MF-SnF方法相比，給定相同的計算復雜度界限，NC-SnF方法可以獲得更大的時間調度范圍.仿真結果表明，與MF-SnF方法相比，NC-SnF方法所需的計算時間更短、獲得的阻塞率更低.

盡管本論文的研究工作圍繞基于OCS的跨數據中心網絡開展，但是研究結果對于虛電路交換網絡、帶寬可管理的分組交換網絡等類似網絡同樣具有借鑒意義.本文的理論分析模型主要針對固定路由場景，而繼續將研究場景擴展到通用網絡場景，探索網絡級存儲選擇與部署方案，是未來研究方向.