林 霄 姬 碩 岳勝男 孫衛(wèi)強(qiáng) 胡衛(wèi)生

1(福州大學(xué)物理與信息工程學(xué)院 福州 350116)2(區(qū)域光纖通信網(wǎng)與新型光通信系統(tǒng)國(guó)家重點(diǎn)實(shí)驗(yàn)室(上海交通大學(xué)) 上海 200240)(linxiaocer@fzu.edu.cn)

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

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

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

本文以海量DC存儲(chǔ)與光電路交換(optical circuit switching, OCS)的結(jié)合作為研究場(chǎng)景.一方面，OCS可以為大數(shù)據(jù)提供高帶寬、大容量、低開銷的傳輸通道.另一方面，通過SnF實(shí)現(xiàn)數(shù)據(jù)分段傳輸，避免了傳統(tǒng)OCS面臨的E2E傳輸困境[11-15].然而，存儲(chǔ)的引入將傳統(tǒng)的路由問題變?yōu)楦訌?fù)雜的SnF調(diào)度問題.求解該調(diào)度問題，不僅需要在空間上尋找傳輸路徑，還需要在時(shí)間上規(guī)劃何時(shí)傳輸、何時(shí)緩存.相比傳統(tǒng)路由問題，SnF調(diào)度問題求解難度大，計(jì)算復(fù)雜度高[10].此外，不恰當(dāng)?shù)卣{(diào)度存儲(chǔ)、帶寬資源，反而導(dǎo)致繞路、網(wǎng)絡(luò)資源碎片化等問題，進(jìn)而惡化網(wǎng)絡(luò)性能[13].顯然，SnF效能的發(fā)揮取決于能否高效、合理求解SnF調(diào)度問題.

本質(zhì)上，SnF的靈活性取決于數(shù)據(jù)傳輸路徑上的存儲(chǔ)節(jié)點(diǎn)數(shù).每個(gè)存儲(chǔ)節(jié)點(diǎn)都為調(diào)度決策提供一個(gè)SnF選項(xiàng).存儲(chǔ)節(jié)點(diǎn)越多，SnF調(diào)度方案就越靈活.目前大多數(shù)研究工作旨在最大限度地發(fā)揮SnF的靈活性，因此將數(shù)據(jù)傳輸路徑上的所有節(jié)點(diǎn)均納入SnF調(diào)度決策[10-21].當(dāng)每個(gè)節(jié)點(diǎn)接收到數(shù)據(jù)后，其必須決定是否存儲(chǔ)該數(shù)據(jù)、需要存儲(chǔ)多長(zhǎng)時(shí)間，以及應(yīng)該以何種速率將該數(shù)據(jù)傳輸?shù)较乱还?jié)點(diǎn).這導(dǎo)致調(diào)度問題的復(fù)雜度隨傳輸路徑跳數(shù)的增加呈指數(shù)增長(zhǎng)[10,15].因此，在大規(guī)模網(wǎng)絡(luò)、動(dòng)態(tài)網(wǎng)絡(luò)場(chǎng)景下，調(diào)度問題將變得難以求解.

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

本文的主要貢獻(xiàn)有3個(gè)方面：

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

2) 進(jìn)一步擴(kuò)展理論分析模型，量化分析了參與調(diào)度決策的存儲(chǔ)節(jié)點(diǎn)數(shù)量對(duì)SnF調(diào)度性能與復(fù)雜度的影響.研究表明，在調(diào)度過程中，僅將部分途經(jīng)節(jié)點(diǎn)納入調(diào)度問題決策，同時(shí)擴(kuò)大時(shí)間維度的調(diào)度范圍，不僅能獲得更好調(diào)度性能，同時(shí)能有效降低計(jì)算復(fù)雜度.

3) 提出了節(jié)點(diǎn)約束SnF調(diào)度方法.該方法將部分?jǐn)?shù)據(jù)途經(jīng)節(jié)點(diǎn)納入調(diào)度決策，同時(shí)根據(jù)所選節(jié)點(diǎn)進(jìn)行拓?fù)涑橄?給定相同的計(jì)算復(fù)雜度限制，該方法可以對(duì)更大時(shí)間范圍內(nèi)的網(wǎng)絡(luò)狀態(tài)進(jìn)行搜索，比使用所有節(jié)點(diǎn)進(jìn)行調(diào)度的現(xiàn)有調(diào)度方法作出更優(yōu)的調(diào)度決策.仿真表明，該方法在阻塞率和運(yùn)算時(shí)間方面優(yōu)于現(xiàn)有調(diào)度方法.

1 相關(guān)工作

1.1 現(xiàn)有SnF調(diào)度方法

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

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

1) 基于MF策略的SnF調(diào)度方法

多數(shù)學(xué)者旨在充分利用現(xiàn)有網(wǎng)絡(luò)基礎(chǔ)架構(gòu)，最大程度地發(fā)揮SnF調(diào)度的靈活性，即采用基于MF的調(diào)度策略.這些學(xué)者針對(duì)所有網(wǎng)絡(luò)節(jié)點(diǎn)均部署有存儲(chǔ)的網(wǎng)絡(luò)場(chǎng)景開展研究，即完全部署(full place-ment)網(wǎng)絡(luò)場(chǎng)景[10-23].

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

2) 基于NC策略的SnF調(diào)度方法

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

在完全部署網(wǎng)絡(luò)場(chǎng)景下，文獻(xiàn)[24-25]比較了SnF和提前預(yù)約機(jī)制(advance reservation, AR).AR可等價(jià)于僅有源節(jié)點(diǎn)具備存儲(chǔ)功能的一個(gè)SnF特例.文獻(xiàn)[24-25]研究表明，當(dāng)網(wǎng)絡(luò)負(fù)載較高時(shí)，與SnF相比，AR所能帶來(lái)的性能增益是有限的.

在部分部署網(wǎng)絡(luò)場(chǎng)景下[27]，文獻(xiàn)[26]針對(duì)3節(jié)點(diǎn)串聯(lián)網(wǎng)絡(luò)展開研究，其中僅有中繼節(jié)點(diǎn)具備SnF能力.文獻(xiàn)[26]將SnF調(diào)度問題建模為單跳、單路徑傳輸問題，但并未考慮任何路由或調(diào)度問題.在文獻(xiàn)[27]中，當(dāng)E2E光路無(wú)法建立時(shí)，調(diào)度方法將嘗試從源節(jié)點(diǎn)建立光路到最近的存儲(chǔ)節(jié)點(diǎn)，以便緩存數(shù)據(jù)，等待一段時(shí)間后再嘗試建立從存儲(chǔ)節(jié)點(diǎn)到目的地的光路.盡管數(shù)據(jù)傳輸路徑可能會(huì)途經(jīng)多個(gè)中繼節(jié)點(diǎn)，但是只有一個(gè)中繼節(jié)點(diǎn)是存儲(chǔ)節(jié)點(diǎn).這就極大限制了SnF的靈活性，以及所能帶來(lái)的性能增益.此外，文獻(xiàn)[27]將存儲(chǔ)部署問題轉(zhuǎn)化為設(shè)施選址問題(facility location problem)，并通過拓?fù)渲行男郧蠼庠搯栴}.顯然，存儲(chǔ)部署主要取決于網(wǎng)絡(luò)拓?fù)涮卣?，但并未考慮任何調(diào)度復(fù)雜度問題.文獻(xiàn)[28]旨在以最小的存儲(chǔ)使用量獲得最大網(wǎng)絡(luò)數(shù)據(jù)傳輸能力.文獻(xiàn)[28]將路由問題與存儲(chǔ)使用問題轉(zhuǎn)化為最大流問題(maximum flow problem)，從而實(shí)現(xiàn)對(duì)上述2個(gè)問題的聯(lián)合優(yōu)化.文獻(xiàn)[28]同樣也沒有考慮存儲(chǔ)節(jié)點(diǎn)數(shù)量對(duì)于調(diào)度復(fù)雜度的影響.

3) 現(xiàn)有研究工作的總結(jié)

多數(shù)工作主要研究基于MF策略的SnF調(diào)度方法.這些工作所提出的調(diào)度方法更適合小規(guī)模網(wǎng)絡(luò)、靜態(tài)網(wǎng)絡(luò)場(chǎng)景下的離線調(diào)度優(yōu)化，難以為大規(guī)模網(wǎng)絡(luò)、動(dòng)態(tài)網(wǎng)絡(luò)場(chǎng)景提供實(shí)時(shí)調(diào)度.另一部分工作研究如何使用源節(jié)點(diǎn)或部分中繼節(jié)點(diǎn)進(jìn)行調(diào)度，即采用基于NC策略的SnF調(diào)度方法.然而，這些研究工作旨在于減少存儲(chǔ)部署或使用量，并未考慮存儲(chǔ)節(jié)點(diǎn)數(shù)量對(duì)于調(diào)度性能和復(fù)雜度的影響.顯然，調(diào)度方法的設(shè)計(jì)本質(zhì)上是對(duì)性能與復(fù)雜度的折中.設(shè)計(jì)高效的SnF調(diào)度方法應(yīng)當(dāng)仔細(xì)考慮用于調(diào)度決策的存儲(chǔ)節(jié)點(diǎn)數(shù).然而，現(xiàn)有的研究工作尚未充分考慮該問題.

與現(xiàn)有基于MF策略的調(diào)度方法不同，本文所提出的新型調(diào)度方法將NC調(diào)度策略融入基于時(shí)移多層圖(time-shifted multilayer graph, TS-MLG)[16]的路由調(diào)度，有效減少了調(diào)度決策過程需要的存儲(chǔ)節(jié)點(diǎn)數(shù)量.在此基礎(chǔ)之上，新型調(diào)度方法使用基于存儲(chǔ)節(jié)點(diǎn)的拓?fù)涑橄?，在保證調(diào)度性能的同時(shí)減小調(diào)度問題規(guī)模、降低調(diào)度問題求解難度.現(xiàn)有基于NC策略的調(diào)度方法通常固定選擇源節(jié)點(diǎn)或部分中繼節(jié)點(diǎn)作為存儲(chǔ)節(jié)點(diǎn).與此不同，新型調(diào)度方法根據(jù)節(jié)點(diǎn)對(duì)之間路由跳數(shù)的不同，選擇合適的存儲(chǔ)節(jié)點(diǎn)數(shù)，獲得了低復(fù)雜度、高調(diào)度性能，更適合為大規(guī)模網(wǎng)絡(luò)、動(dòng)態(tài)網(wǎng)絡(luò)場(chǎng)景提供實(shí)時(shí)、高效的調(diào)度服務(wù).

1.2 時(shí)移多層圖

時(shí)移多層圖[16]是一種面向SnF的路由調(diào)度框架，是由多個(gè)層組成的圖,如圖2所示.TS-MLG中每層都是網(wǎng)絡(luò)拓?fù)湓谀硞€(gè)時(shí)刻的快照，反映了當(dāng)時(shí)的網(wǎng)絡(luò)狀態(tài).TS-MLG通過一系列拓?fù)淇煺眨蹲搅穗S時(shí)間變化的網(wǎng)絡(luò)狀態(tài).例如，TS-MLG的最頂層表明時(shí)刻t0鏈路E—F沒有可用帶寬.第2層表明時(shí)刻t1鏈路E(1)—F(1)有可用帶寬.此外，TS-MLG引入時(shí)間鏈路(temporal link)和空間鏈路(spatial link)的概念.請(qǐng)求穿越時(shí)間、空間鏈路分別表示數(shù)據(jù)緩存和數(shù)據(jù)傳輸.僅需對(duì)TS-MLG進(jìn)行最短路由，即可獲得一條“穿越時(shí)空的端到端”路徑，同時(shí)實(shí)現(xiàn)空間路由與時(shí)間調(diào)度的融合調(diào)度、帶寬與存儲(chǔ)資源的聯(lián)合分配，極大簡(jiǎn)化了SnF調(diào)度問題的求解過程.

假設(shè)傳輸請(qǐng)求r在時(shí)刻t0到達(dá)網(wǎng)絡(luò)，要求從節(jié)點(diǎn)A向節(jié)點(diǎn)E傳輸數(shù)據(jù).然而，在時(shí)刻t0無(wú)法進(jìn)行E2E傳輸.但通過對(duì)圖2所示的TS-MLG進(jìn)行路由搜索(例如使用Dijkstra算法)，即可找到路徑A—F—F(1)—E(1)，其中節(jié)點(diǎn)F是中繼存儲(chǔ)節(jié)點(diǎn).顯然，借助TS-MLG，時(shí)空二維的SnF調(diào)度問題被轉(zhuǎn)變?yōu)橐痪S的路由問題.

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

隨著請(qǐng)求的到達(dá)和離開，網(wǎng)絡(luò)狀態(tài)將發(fā)生改變，TS-MLG的層數(shù)也將發(fā)生動(dòng)態(tài)改變.當(dāng)網(wǎng)絡(luò)產(chǎn)生新狀態(tài)，新層將被添加到TS-MLG.隨著時(shí)間流逝，當(dāng)現(xiàn)有網(wǎng)絡(luò)狀態(tài)超時(shí)，相應(yīng)的層將被從TS-MLG中移除.

路由算法的計(jì)算復(fù)雜度通常取決于網(wǎng)絡(luò)拓?fù)涞囊?guī)模.TS-MLG的規(guī)模等于網(wǎng)絡(luò)拓?fù)涔?jié)點(diǎn)數(shù)乘以TS-MLG的層數(shù).因此，TS-MLG的層數(shù)很大程度上決定了對(duì)其進(jìn)行路由搜索的計(jì)算復(fù)雜度.由于數(shù)據(jù)流的突發(fā)性可能會(huì)導(dǎo)致TS-MLG的層數(shù)出現(xiàn)短時(shí)激增，使得后續(xù)請(qǐng)求的路由復(fù)雜度陡然增大.為了限制復(fù)雜度，用于路由的層數(shù)必須予以限制.因此，請(qǐng)求是否能被網(wǎng)絡(luò)接收取決于請(qǐng)求是否能在給定的TS-MLG層數(shù)內(nèi)找到有效路徑.

2 不同數(shù)據(jù)傳輸方式的比較研究

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

Table 1 Table of Notations

在IR中，請(qǐng)求是否能被接收取決于當(dāng)前網(wǎng)絡(luò)帶寬是否能夠提供E2E傳輸.當(dāng)請(qǐng)求到達(dá)網(wǎng)絡(luò)時(shí)，網(wǎng)絡(luò)調(diào)度器(scheduler)必須立即根據(jù)網(wǎng)絡(luò)當(dāng)前的帶寬資源可用情況作出調(diào)度決策.在AR中，請(qǐng)求的傳輸可以被推遲，并等待可用的E2E連接出現(xiàn)再開始傳輸.源節(jié)點(diǎn)具備推遲請(qǐng)求傳輸?shù)哪芰?因此，當(dāng)請(qǐng)求到達(dá)網(wǎng)絡(luò)時(shí)，網(wǎng)絡(luò)調(diào)度器根據(jù)網(wǎng)絡(luò)當(dāng)前與未來(lái)的帶寬資源可用情況作出調(diào)度決策.在SnF中，每個(gè)節(jié)點(diǎn)都可以進(jìn)行SnF.因此，當(dāng)請(qǐng)求到達(dá)網(wǎng)絡(luò)時(shí)，網(wǎng)絡(luò)調(diào)度器根據(jù)網(wǎng)絡(luò)當(dāng)前與未來(lái)的帶寬與存儲(chǔ)資源可用情況作出調(diào)度決策.IR與AR可等價(jià)為SnF在沒有任何節(jié)點(diǎn)或僅有源節(jié)點(diǎn)具備存儲(chǔ)能力時(shí)的2種特例.

2.1 建模分析

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

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

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

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

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

(1)

(2)

N和L決定了TS-MLG的規(guī)模.增加N表示選擇一條更長(zhǎng)的路由傳輸數(shù)據(jù)，而增加L表示擴(kuò)展時(shí)間維度的調(diào)度范圍(例如允許更長(zhǎng)的數(shù)據(jù)緩存時(shí)間).

2.2 調(diào)度性能與復(fù)雜度分析

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

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

給定N，L，pbps，圖4比較了3種傳輸方式的預(yù)約失敗率，即F(s,d)(N,L).圖4(a)～(c)假設(shè)ps?pb.因?yàn)樵诘湫偷目鐢?shù)據(jù)中心網(wǎng)絡(luò)中帶寬資源較為稀缺，而存儲(chǔ)資源較為豐富.在某些城域網(wǎng)應(yīng)用場(chǎng)景中，例如傳統(tǒng)通信機(jī)房DC化(center office re-architected as datacenter, CORD)和面向邊緣計(jì)算的微型DC，有限的存儲(chǔ)資源可能不足以滿足大數(shù)據(jù)傳輸需求.因此，在這些網(wǎng)絡(luò)場(chǎng)景中，pb和ps的取值值得未來(lái)繼續(xù)研究.

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

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

2.3 分析與總結(jié)

借助復(fù)雜度與調(diào)度性能分析模型，本節(jié)比較了IR，AR，SnF這3種數(shù)據(jù)傳輸方式，主要發(fā)現(xiàn)如下：

1) 雖然IR和AR的復(fù)雜度較低，但對(duì)于大規(guī)模網(wǎng)絡(luò)、動(dòng)態(tài)場(chǎng)景，其性能可能不足.SnF的性能優(yōu)于IR和AR，但代價(jià)是復(fù)雜度較高.

2) 當(dāng)N，L，pb較小時(shí)，AR和SnF之間的性能差距較小.這表明，在這種情況下，使用1個(gè)存儲(chǔ)節(jié)點(diǎn)參與調(diào)度即可獲得較好性能，而無(wú)需多個(gè)存儲(chǔ)節(jié)點(diǎn)參與調(diào)度.但隨著L的增大，AR和SnF的性能差距急劇擴(kuò)大.這表明，當(dāng)允許調(diào)度器在更大的時(shí)間范圍內(nèi)進(jìn)行資源調(diào)度時(shí)，SnF比AR更有優(yōu)勢(shì).

3) 相比IR和AR，SnF具備的高性能與高復(fù)雜度源于其能夠使用更多的存儲(chǔ)節(jié)點(diǎn)參與調(diào)度決策.因此，有必要進(jìn)一步研究存儲(chǔ)節(jié)點(diǎn)數(shù)對(duì)SnF的影響.

3 存儲(chǔ)節(jié)點(diǎn)數(shù)量對(duì)SnF的影響

本節(jié)首先擴(kuò)展分析模型以量化存儲(chǔ)節(jié)點(diǎn)數(shù)對(duì)SnF的影響；然后將MF調(diào)度策略與NC調(diào)度策略進(jìn)行比較研究.

3.1 建模分析

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

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

當(dāng)Ns=1且源節(jié)點(diǎn)是存儲(chǔ)節(jié)點(diǎn)時(shí)，NC模型等價(jià)于圖3(b)中所示的AR模型.當(dāng)Ns=N-1時(shí)，NC模型等價(jià)于MF模型，如圖3(c)所示.當(dāng)1

圖6 備選路徑數(shù)和預(yù)約失敗率

(3)

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

(4)

詳細(xì)證明參見附錄A.

3.2 調(diào)度性能和復(fù)雜度分析

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

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

盡管Rp和Rc均隨Ns增加，但Rp和Rc之間存在間距,該間距隨Ns而變化.因此存儲(chǔ)節(jié)點(diǎn)的最佳數(shù)量應(yīng)當(dāng)使得Rp最大化而Rc最小化.但是，由于1≤Ns≤N-1，所以該間距變化始終受限.本節(jié)繼續(xù)探索如何進(jìn)一步擴(kuò)大該間距，突破上述限制的方法.

繼續(xù)研究Ls>L的情況,假設(shè)N=10，L=4，ps=0.01.本節(jié)將研究Ls變化如何影響Rp和Rc,結(jié)果如表4所示.給定Ls=L=4，當(dāng)Ns從2增大到4時(shí)，Rc從0.045增加到0.159.同時(shí)，當(dāng)pb=0.1時(shí)，Rp從0.112增加到0.818；而當(dāng)pb=0.3時(shí)，Rp從0.250增加到0.522，如表4第1行所示.可見，當(dāng)pb=0.1時(shí)，增加Ns可以將Rp增加到0.818，但代價(jià)是Rc=0.159.相比之下，給定L=4且Ns保持2，當(dāng)Ls從4增大到7時(shí)，Rc從0.045增加到0.127；同時(shí)，當(dāng)pb=0.1時(shí)，Rp從0.112增加到29.117；而當(dāng)pb=0.3時(shí)，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 分析與總結(jié)

借助分析模型，本節(jié)研究了存儲(chǔ)節(jié)點(diǎn)數(shù)量對(duì)于SnF調(diào)度性能與復(fù)雜度的影響，主要發(fā)現(xiàn)如下：

1) 在時(shí)間維度的調(diào)度范圍不變的前提下(即Ls=L)，僅將傳輸路徑途經(jīng)的部分節(jié)點(diǎn)而非所有節(jié)點(diǎn)納入調(diào)度決策，雖然可以減輕調(diào)度過程的計(jì)算負(fù)擔(dān)，但是調(diào)度性能也會(huì)隨之降低.

2) 當(dāng)ps?pb時(shí)，擴(kuò)展時(shí)間維度的調(diào)度范圍比使用更多存儲(chǔ)節(jié)點(diǎn)參與調(diào)度更有助于提高調(diào)度性能.但是，擴(kuò)展時(shí)間調(diào)度范圍將導(dǎo)致請(qǐng)求經(jīng)歷更長(zhǎng)延遲.

3) 當(dāng)NsL時(shí)，NC策略的調(diào)度性能不僅可能超過MF策略，而且能保持較低的復(fù)雜度.換而言之，僅將傳輸路徑沿途的部分節(jié)點(diǎn)而非所有節(jié)點(diǎn)納入調(diào)度決策，有可能同時(shí)實(shí)現(xiàn)高性能、低復(fù)雜度.

4) 設(shè)計(jì)高效的SnF調(diào)度方法應(yīng)當(dāng)聯(lián)合優(yōu)化Ns和Ls，以到達(dá)性能與復(fù)雜度的最佳折中.

4 節(jié)點(diǎn)約束存儲(chǔ)轉(zhuǎn)發(fā)調(diào)度方法

4.1 網(wǎng)絡(luò)模型與主要假設(shè)

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

Fig. 7 SnF scheme for inter-DCNs圖7 面向跨數(shù)據(jù)中心網(wǎng)絡(luò)的SnF傳輸方案

4.2 算法研究

受第3節(jié)的研究啟發(fā)，本文將NC調(diào)度策略與拓?fù)涑橄笕谌牖赥S-MLG的路由調(diào)度，從而實(shí)現(xiàn)NsL的組合.由此，本文提出了節(jié)點(diǎn)約束SnF(node-constraint SnF, NC-SnF)調(diào)度方法.

NC-SnF方法的主要思想源于2方面.首先，在請(qǐng)求到達(dá)網(wǎng)絡(luò)時(shí)，NC-SnF方法僅將部分傳輸路徑途經(jīng)節(jié)點(diǎn)納入調(diào)度決策.其次，根據(jù)所涉節(jié)點(diǎn)，NC-SnF方法通過將TS-MLG中連接這些節(jié)點(diǎn)的空間鏈路合并，并對(duì)具有相同網(wǎng)絡(luò)狀態(tài)的層壓縮，從而實(shí)現(xiàn)拓?fù)涑橄?一方面，NC-SnF方法縮小了TS-MLG規(guī)模，從而減輕了調(diào)度過程的計(jì)算負(fù)擔(dān)；另一方面，當(dāng)可用于路由的層數(shù)有限時(shí)，相比沒有拓?fù)涑橄蟮膫鹘y(tǒng)調(diào)度方法，NC-SnF方法可以搜索時(shí)間上距離當(dāng)前時(shí)刻更遠(yuǎn)的層.換言之，給定相同計(jì)算復(fù)雜度上界，相比于傳統(tǒng)調(diào)度方法，NC-SnF方法本質(zhì)上能夠?yàn)檎?qǐng)求提供更大的時(shí)間調(diào)度范圍.因此，NC-SnF方法在降低計(jì)算復(fù)雜度的同時(shí)保持良好的調(diào)度性能.

NC-SnF方法分為5個(gè)步驟.每個(gè)節(jié)點(diǎn)對(duì)(i,j)均已預(yù)先計(jì)算K條最短路由，并將備選路由存儲(chǔ)在集合R(i,j).假設(shè)請(qǐng)求r的源-目的節(jié)點(diǎn)對(duì)為(s,d).

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

步驟2. 算法1第③行根據(jù)存儲(chǔ)節(jié)點(diǎn)選擇方案，在Rk上選擇的Ns個(gè)節(jié)點(diǎn)用于SnF調(diào)度.令α表示Rk上可用于調(diào)度節(jié)點(diǎn)數(shù)占節(jié)點(diǎn)總數(shù)的百分比，其中0<α≤1.Ns=[(Nk-1)×α].集合S={s,I1,I2,…,Ii,…,INs-1,d}，其中Ii表示被選存儲(chǔ)節(jié)點(diǎn)，Ii∈Rk且|S|=Ns+1.集合S表示Rk被存儲(chǔ)節(jié)點(diǎn)劃分為Ns個(gè)片段.集合S的第1個(gè)節(jié)點(diǎn)是s，因?yàn)橐延醒芯勘砻?，在多?shù)調(diào)度過程中，源節(jié)點(diǎn)是首個(gè)發(fā)生SnF的節(jié)點(diǎn)[16,24-25].為簡(jiǎn)單起見，本文假設(shè)其他被選節(jié)點(diǎn)等間隔分布于Rk.網(wǎng)絡(luò)級(jí)存儲(chǔ)節(jié)點(diǎn)選擇或部署方案是一個(gè)有趣但復(fù)雜的問題，值得在未來(lái)深入研究.

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

步驟4. 算法1第⑤行根據(jù)集合S運(yùn)行算法2對(duì)圖G′進(jìn)行拓?fù)涑橄螅垣@得抽象壓縮后的子圖G″.

算法1.NC-SnF調(diào)度方法.

輸入：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；

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

④ 根據(jù)Rk將圖G縮減為其子圖G′；

⑤ 運(yùn)行算法2，根據(jù)集合S對(duì)圖G′進(jìn)行拓?fù)涑橄?，并獲得抽象壓縮后子圖G″；

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

⑦ if找到Paththen

⑧ returnPath和Find=True；

⑨ end if

⑩ end for

算法2的主要思想是根據(jù)集合S實(shí)現(xiàn)拓?fù)涑橄?該算法主要包括3個(gè)步驟：

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

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

算法2.基于存儲(chǔ)節(jié)點(diǎn)的拓?fù)涑橄笏惴?

輸入：圖G′，LR，S；

輸出：圖G″.

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

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

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

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

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

⑥ 將連接圖G′中的節(jié)點(diǎn)Ii和節(jié)點(diǎn)Ii+1的時(shí)間鏈路添加到圖G″；

⑦ end for

⑧ end for

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

⑩ iflj+1==ljthen

4.3 算法運(yùn)行示例

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

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

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

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

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

4.4 資源預(yù)約窗口研究

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

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

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

簡(jiǎn)而言之，給定相同計(jì)算復(fù)雜度限制，與傳統(tǒng)調(diào)度方法相比，NC-SnF方法能夠提供更大的資源預(yù)約窗口，因此有助于降低請(qǐng)求阻塞率.

4.5 計(jì)算復(fù)雜度研究

TS-MLG的規(guī)模決定了路由算法的計(jì)算復(fù)雜度.文獻(xiàn)[16]給出的復(fù)雜度為O((V×LR)2),V表示網(wǎng)絡(luò)拓?fù)渲械墓?jié)點(diǎn)總數(shù).NC-SnF方法使用BFS算法對(duì)壓縮后的TS-MLG圖G″進(jìn)行有效路徑搜索.BFS算法的復(fù)雜度為O(V″+E″)，V″表示圖G″的總節(jié)點(diǎn)數(shù)，E″表示圖G″的總邊數(shù).在最壞的情況下，V″=LR×Ns；而E″=(LR-1)×Ns+(Ns-1)×LR.因此，NC-SnF方法的復(fù)雜度為O(K×LR×Ns).

5 結(jié)果與討論

本節(jié)模擬動(dòng)態(tài)網(wǎng)絡(luò)環(huán)境，比較NC-SnF方法與傳統(tǒng)的SnF調(diào)度方法[12](即MF-SnF方法).

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

5.1 網(wǎng)絡(luò)性能研究

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

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

Fig. 11 Blocking probability under various ρ (LR=4)圖11 不同網(wǎng)絡(luò)負(fù)載ρ下的阻塞率(LR=4)

直觀上，存儲(chǔ)節(jié)點(diǎn)數(shù)越少，阻塞率越高.然而，圖11卻顯示相反的結(jié)果，即存儲(chǔ)節(jié)點(diǎn)數(shù)越少，NC-SnF方法獲得的阻塞率反而越低.為了理解該結(jié)果，本節(jié)將研究重點(diǎn)放在圖11(a)，研究其他網(wǎng)絡(luò)性能指標(biāo)如何隨ρ變化，結(jié)果如圖12所示.活躍請(qǐng)求(active request)定義為已被網(wǎng)絡(luò)接受但尚未完成傳輸?shù)恼?qǐng)求.請(qǐng)求緩存率(ratio of stored requests)定義為緩存請(qǐng)求數(shù)與請(qǐng)求總數(shù)的比率.延遲定義為從請(qǐng)求到達(dá)網(wǎng)絡(luò)直到請(qǐng)求結(jié)束傳輸?shù)臅r(shí)間間隔.

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

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

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

5.2 基于存儲(chǔ)節(jié)點(diǎn)的拓?fù)涑橄笏惴ㄑ芯?/h3>

得益于拓?fù)涑橄笏惴?即算法2)，空間鏈路和冗余層被合并和壓縮，使得NC-SnF方法能夠提供更大的資源預(yù)約窗口.為了驗(yàn)證算法2的作用，本節(jié)比較了原始NC-SnF方法和沒有拓?fù)涑橄蠊δ艿腘C-SnF方法(即簡(jiǎn)化NC-SnF方法).在簡(jiǎn)化NC-SnF方法中，算法2被禁用.因此，BFS算法直接對(duì)簡(jiǎn)化圖G′而非壓縮圖G″進(jìn)行有效路徑搜索.此處，w=4，LR=4.仿真結(jié)果如圖13所示:

Fig. 13 The original NC-SnF method vs the NC-SnF method disabling the topology abstraction (α=0.4)圖13 原始NC-SnF方法與禁用拓?fù)涑橄蠊δ艿腘C-SnF方法比較(α=0.4)

給定α=0.4，原始NC-SnF方法的阻塞率優(yōu)于簡(jiǎn)化NC-SnF方法，如圖13(a)所示.這是因?yàn)樵糔C-SnF方法中的資源預(yù)約窗口隨ρ增大而增大，而簡(jiǎn)化NC-SnF方法中的資源預(yù)約窗口幾乎保持恒定，如圖13(b)所示.

隨后，繼續(xù)對(duì)比簡(jiǎn)化NC-SnF方法與MF-SnF方法，如圖13(a)所示.MF-SnF方法優(yōu)于簡(jiǎn)化NC-SnF方法.這是因?yàn)橐环矫鏇]有了拓?fù)涑橄蠊δ埽?jiǎn)化NC-SnF方法的資源預(yù)約窗口明顯小于MF-SnF方法；另一方面MF-SnF方法能夠比簡(jiǎn)化NC-SnF方法使用更多存儲(chǔ)節(jié)點(diǎn)，因此MF-SnF方法的調(diào)度更加靈活.

5.3 算法計(jì)算時(shí)間研究

本節(jié)研究了TS-MLG的節(jié)點(diǎn)數(shù)和層數(shù)是如何影響NC-SnF方法的算法計(jì)算時(shí)間.本節(jié)使用鏈路密度為0.6的隨機(jī)生成拓?fù)溥M(jìn)行仿真實(shí)驗(yàn).鏈路密度定義為網(wǎng)絡(luò)拓?fù)渲腥我?個(gè)節(jié)點(diǎn)之間存在邊的概率.V表示網(wǎng)絡(luò)拓?fù)涞墓?jié)點(diǎn)數(shù).

表5和表6描繪了不同調(diào)度方法對(duì)給定的TS-MLG進(jìn)行一次路由搜索的平均計(jì)算時(shí)間.在表5中，LR=10.計(jì)算時(shí)間隨V的增加而增加.在表6中，V=10.計(jì)算時(shí)間隨著LR的增加而增加.表5和表6表明，α值越小，計(jì)算時(shí)間的增幅越小.這是因?yàn)楫?dāng)α值較小時(shí)，需要搜索的TS-MLG規(guī)模也相應(yīng)減小.

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

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

5.4 不同網(wǎng)絡(luò)拓?fù)溲芯?/h3>

Fig. 14 Blocking probability in different topologies圖14 不同網(wǎng)絡(luò)拓?fù)湎碌淖枞?/p>

本節(jié)繼續(xù)研究了不同的網(wǎng)絡(luò)拓?fù)渲凶枞孰Sρ的變化情況.選取19個(gè)節(jié)點(diǎn)39條鏈路的泛歐洲全光網(wǎng)(optical pan-european network, OPEN)和24個(gè)節(jié)點(diǎn)43條鏈路的美國(guó)骨干網(wǎng)絡(luò)(US backbone network, USNET)作為研究對(duì)象.此處，w=4，LR=4.圖14(a)(b)分別描述了在OPEN和USNET中不同ρ下的阻塞率.圖14的結(jié)果與圖11的結(jié)果類似.因此，在不同的網(wǎng)絡(luò)拓?fù)渲?，NC-SnF方法的阻塞性能均優(yōu)于MF-SnF方法.然而，圖14中NC-SnF調(diào)度方法獲得的阻塞率略高于圖11.例如，當(dāng)α=0.4和ρ=20時(shí)，在NSFNET中NC-SnF方法獲得的阻塞率為1.32×10-6；而在OPEN和USNET中NC-SnF方法獲得的阻塞率分別為4.04×10-6和1.07×10-4.這是因?yàn)镺PEN和USNET的拓?fù)湟?guī)模大于NSFNET.因此，OPEN和USNET中給定節(jié)點(diǎn)對(duì)之間的路由跳數(shù)多于NSFNET.給定相同的α，NC-SnF方法在OPEN和USNET中每條路由上選定的存儲(chǔ)節(jié)點(diǎn)數(shù)多于NSFNET.根據(jù)4.3節(jié)討論可知，借助拓?fù)涑橄笏惴?，選定的存儲(chǔ)節(jié)點(diǎn)數(shù)越少，所獲得的壓縮子圖規(guī)模就越小，相應(yīng)的資源預(yù)約窗口也就越大.因此，相比OPEN和USNET，NSFNET中NC-SnF方法可獲得更大的資源預(yù)約窗口，進(jìn)而獲得更低的阻塞率.

6 總 結(jié)

本文將SnF與IR和AR進(jìn)行了對(duì)比.研究表明，選擇合適數(shù)量的存儲(chǔ)節(jié)點(diǎn)用于調(diào)度決策，實(shí)際上是調(diào)度性能與復(fù)雜度之間的折中問題.為此，本文提出了分析模型，揭示了存儲(chǔ)節(jié)點(diǎn)數(shù)對(duì)SnF復(fù)雜度與性能的影響.研究發(fā)現(xiàn)，在一定條件下，NC調(diào)度策略能夠在降低復(fù)雜度的同時(shí)獲得比傳統(tǒng)MF調(diào)度策略更好的調(diào)度性能.

受此啟發(fā)，本文提出NC-SnF調(diào)度方法，只將傳輸路徑上的部分節(jié)點(diǎn)納入調(diào)度決策.同時(shí)，NC-SnF方法引入了基于存儲(chǔ)節(jié)點(diǎn)的拓?fù)涑橄?與傳統(tǒng)的MF-SnF方法相比，給定相同的計(jì)算復(fù)雜度界限，NC-SnF方法可以獲得更大的時(shí)間調(diào)度范圍.仿真結(jié)果表明，與MF-SnF方法相比，NC-SnF方法所需的計(jì)算時(shí)間更短、獲得的阻塞率更低.

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