可保障數(shù)據(jù)無中斷傳輸?shù)娜哂鄻渌惴ㄑ芯?/h1>
2016-10-13 03:41:44羅軍舟
計算機(jī)研究與發(fā)展 2016年9期
夏 怒 李 偉 陸 悠 蔣 健 單 馮 羅軍舟
(東南大學(xué)計算機(jī)科學(xué)與工程學(xué)院 南京 211189)
?
可保障數(shù)據(jù)無中斷傳輸?shù)娜哂鄻渌惴ㄑ芯?/p>
夏怒李偉陸悠蔣健單馮羅軍舟
(東南大學(xué)計算機(jī)科學(xué)與工程學(xué)院南京211189)
(xia_nu@seu.edu.cn)
隨著大數(shù)據(jù)應(yīng)用的發(fā)展，保障數(shù)據(jù)無中斷傳輸?shù)男枨笕找嬖鰪?qiáng).針對單點或單鏈路失效的情況，現(xiàn)有的保障數(shù)據(jù)無中斷傳輸方法存在主備份路徑的數(shù)據(jù)傳輸性能較低、抵御多節(jié)點邊失效能力不強(qiáng)等問題.為解決以上問題，提出一種可保障數(shù)據(jù)無中斷傳輸?shù)陌催呅蜻x環(huán)的冗余樹算法CSES(circle selecting by edge sorting based redundant tree algorithm for uninterrupted data delivery)，可用于構(gòu)建數(shù)據(jù)傳輸性能優(yōu)化的主備份路徑，并使數(shù)據(jù)傳輸具有較強(qiáng)的抵御多節(jié)點邊失效的能力. 該算法首先根據(jù)網(wǎng)絡(luò)拓?fù)錁?gòu)建以數(shù)據(jù)源為根節(jié)點的最小傳輸樹，以最小化主傳輸路徑上的轉(zhuǎn)發(fā)跳數(shù)；其次，為了減少備份路徑的轉(zhuǎn)發(fā)跳數(shù)并提高數(shù)據(jù)傳輸?shù)钟喙?jié)點邊失效的能力，對拓?fù)渲胁辉谧钚鬏敇渖系倪呥M(jìn)行排序，將樹上根節(jié)點到邊上2個端點的路徑上節(jié)點數(shù)量之和較小的邊排在前列. 隨后按序?qū)⑦吿砑拥阶钚鬏敇渖弦詷?gòu)建冗余環(huán)，并基于冗余環(huán)生成冗余枝添加到最小傳輸樹上，最終形成以數(shù)據(jù)源為根節(jié)點的冗余樹.實驗結(jié)果表明，相比于其他冗余樹算法，基于CSES算法構(gòu)建的冗余樹所生成的主備份路徑的轉(zhuǎn)發(fā)跳數(shù)更少且抵御多節(jié)點邊失效的能力更強(qiáng).
數(shù)據(jù)無中斷傳輸；最小傳輸樹；邊排序；冗余環(huán)；冗余樹
隨著新型應(yīng)用以及網(wǎng)絡(luò)用戶數(shù)量的快速增長，各個領(lǐng)域的數(shù)據(jù)量急劇增加，為了充分利用大數(shù)據(jù)資源，當(dāng)前絕大多數(shù)研究是圍繞數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)以及數(shù)據(jù)分析等方面展開的，而在網(wǎng)絡(luò)對大數(shù)據(jù)的支撐方面所做的研究甚少.正如文獻(xiàn)[1]指出：研究大數(shù)據(jù)傳輸對于大數(shù)據(jù)應(yīng)用發(fā)展的重要意義；數(shù)據(jù)中心網(wǎng)絡(luò)是支撐大數(shù)據(jù)傳輸?shù)暮诵脑O(shè)施，近年來隨著MapReduce、虛擬機(jī)遷移等數(shù)據(jù)應(yīng)用的發(fā)展，愈來愈多的數(shù)據(jù)需要在數(shù)據(jù)中心內(nèi)傳輸以用于處理和分析，因此數(shù)據(jù)中心網(wǎng)絡(luò)對數(shù)據(jù)傳輸?shù)闹文芰χ苯佑绊懙酱髷?shù)據(jù)應(yīng)用的部署與發(fā)展.然而，隨著數(shù)據(jù)中心網(wǎng)絡(luò)規(guī)模日益擴(kuò)大以及網(wǎng)絡(luò)結(jié)構(gòu)日趨復(fù)雜化，影響網(wǎng)絡(luò)穩(wěn)定性的因素如人為配置錯誤、惡意攻擊、軟件漏洞、路由節(jié)點或鏈路硬件故障等逐漸增多，同時由于數(shù)據(jù)中心網(wǎng)絡(luò)中廣泛采用了低成本的網(wǎng)絡(luò)設(shè)備，致使數(shù)據(jù)中心網(wǎng)絡(luò)面臨愈來愈嚴(yán)重的節(jié)點和鏈路失效風(fēng)險，當(dāng)前數(shù)據(jù)中心支撐的應(yīng)用在執(zhí)行過程中往往需要在短時間內(nèi)傳輸少量數(shù)據(jù)(TCP短流)以實時地響應(yīng)用戶請求(數(shù)據(jù)庫查詢、使用WEB服務(wù)等).對于這類應(yīng)用需求，一個很重要的要求就是快速響應(yīng)，從而數(shù)據(jù)傳輸?shù)目煽啃詫Υ祟悜?yīng)用的執(zhí)行性能有很大影響.此外還值得注意的是，雖然TCP 短流理應(yīng)和 TCP 長流獲得相等的網(wǎng)絡(luò)資源，然而在實際中卻是TCP長流占據(jù)了大部分鏈路帶寬，這導(dǎo)致例如當(dāng)別的用戶在下載大文件時一些用戶打開簡單網(wǎng)頁的時間都會指數(shù)上升，因此如果不能保障TCP長流快速無中斷地傳輸，也會增大TCP短流在傳輸隊列中的等待時間進(jìn)而降低應(yīng)用響應(yīng)用戶請求的速度.因此，需要數(shù)據(jù)中心網(wǎng)絡(luò)能夠提供有效的失效恢復(fù)策略和容錯機(jī)制來保障數(shù)據(jù)傳輸?shù)目煽啃?遺憾的是，有研究表明：現(xiàn)有數(shù)據(jù)中心網(wǎng)絡(luò)針對網(wǎng)絡(luò)節(jié)點失效的容錯性較差[2]，基于鏈路狀態(tài)協(xié)議重新計算數(shù)據(jù)傳輸路徑[3-4]往往導(dǎo)致路由收斂時間過長，無法滿足實時性要求較高的數(shù)據(jù)應(yīng)用的需要.因此，研究可保障數(shù)據(jù)無中斷傳輸?shù)募夹g(shù)具有重要意義.
需要指出的是，雖然數(shù)據(jù)中心網(wǎng)絡(luò)拓?fù)渚哂衅渥陨淼奶攸c，然而以Fat-tree[5]為代表的數(shù)據(jù)中心網(wǎng)絡(luò)拓?fù)渲忻總€中間節(jié)點可以有多個父節(jié)點，即增加了上下層集合交換機(jī)之間以及集合交換機(jī)與核心交換機(jī)之間的鏈路，從而較大幅度地增大了網(wǎng)絡(luò)的連通性，使得一對交換節(jié)點之間有多條路徑相連，因此基于Fat-tree的數(shù)據(jù)中心網(wǎng)絡(luò)中3個層次的交換設(shè)備所構(gòu)成的網(wǎng)絡(luò)拓?fù)淇沙橄蟪梢话憔W(wǎng)絡(luò)拓?fù)?，特別是以Camdoop[6]為代表的服務(wù)器互連并將服務(wù)器作為數(shù)據(jù)處理轉(zhuǎn)發(fā)節(jié)點的數(shù)據(jù)中心網(wǎng)絡(luò)中，服務(wù)器組成的網(wǎng)絡(luò)拓?fù)渑c一般網(wǎng)絡(luò)拓?fù)涓鼮榻咏⑶疫B接度更大.
為了實現(xiàn)數(shù)據(jù)無中斷傳輸，從網(wǎng)絡(luò)故障發(fā)生后減少恢復(fù)數(shù)據(jù)傳輸所需時間的角度出發(fā)，相比發(fā)生節(jié)點或鏈路失效時再重新尋找備份路徑的方法[3-4,7]，預(yù)先計算數(shù)據(jù)傳輸備份路徑被視為一種有效方法.文獻(xiàn)[8]針對由節(jié)點失效或路徑擁塞所導(dǎo)致數(shù)據(jù)無法繼續(xù)轉(zhuǎn)輸?shù)那闆r，將失效路徑上正在轉(zhuǎn)發(fā)的數(shù)據(jù)轉(zhuǎn)移到另一條預(yù)先設(shè)置的備份路徑上，進(jìn)而提高數(shù)據(jù)傳輸可靠性.文獻(xiàn)[9]為了提高備份路徑的負(fù)載均衡以及QoS，提出了在拓?fù)渲袨閿?shù)據(jù)傳輸路徑盡力尋找與其分離度最高且跳數(shù)相近的備份路徑的方法.文獻(xiàn)[10]認(rèn)為網(wǎng)絡(luò)中每個鏈路的失效概率并不相同，因此首先對鏈路的重要性進(jìn)行評估，然后根據(jù)評估結(jié)果有選擇地為重要鏈路預(yù)先計算與其不相交的冗余路徑.文獻(xiàn)[11]為拓?fù)渲忻恳粚?jié)點設(shè)置多條備份路徑，以便當(dāng)網(wǎng)絡(luò)故障發(fā)生時在保障數(shù)據(jù)無中斷傳輸?shù)耐瑫r實現(xiàn)負(fù)載均衡.然而，上述方法針對每條鏈路或每個節(jié)點失效尋找備份路徑時需要反復(fù)深度遍歷網(wǎng)絡(luò)拓?fù)洌瑢?dǎo)致算法復(fù)雜度較高.值得注意的是，由于冗余樹算法在保障數(shù)據(jù)無中斷傳輸方面具有算法復(fù)雜度較小、故障恢復(fù)時間短等特點[12]，逐漸引起研究者的關(guān)注，其中Médard等人提出的冗余樹算法MFBG[13]被廣泛使用并被認(rèn)為對未來網(wǎng)絡(luò)故障快速恢復(fù)技術(shù)的發(fā)展具有重要意義[14].MFBG算法通過在網(wǎng)絡(luò)拓?fù)渲须S機(jī)構(gòu)建環(huán)的方式構(gòu)建藍(lán)、紅2棵樹，這2棵樹具有共同的根節(jié)點，藍(lán)樹用作數(shù)據(jù)傳輸?shù)闹鳂?primary tree)，紅樹則為備份樹(secondary tree)，在移除拓?fù)渲腥我?個節(jié)點或1條邊后，剩余的節(jié)點仍然可以通過2棵樹中的1棵與根節(jié)點保持連通.然而，該算法在構(gòu)建冗余樹時未考慮對路徑傳輸性能如延遲和開銷等進(jìn)行優(yōu)化，因此其所采取的隨機(jī)選環(huán)方式導(dǎo)致主備份路徑的傳輸性能不佳.一些學(xué)者基于MFBG算法展開進(jìn)一步研究，文獻(xiàn)[15]提出了僅僅利用本地信息構(gòu)建紅藍(lán)2棵樹的方法，文獻(xiàn)[16]通過盡可能多地將拓?fù)渲械倪吋尤胫鱾鬏敇?藍(lán)樹)以期在故障發(fā)生后降低啟用備份路徑的頻率進(jìn)而降低恢復(fù)開銷，文獻(xiàn)[17]構(gòu)建路徑長度接近的紅藍(lán)2棵樹以平衡主備份傳輸路徑的性能.然而，上述方法在多點邊失效的情況下會有較多的節(jié)點失去與數(shù)據(jù)源節(jié)點的連接，抵御多節(jié)點邊失效的能力較差，并且同樣未對紅樹和藍(lán)樹上路徑傳輸性能進(jìn)行優(yōu)化.盡管Xue等人對MFBG算法做出改進(jìn)并提出了G-MFBG算法[18]，優(yōu)先選擇傳輸性能較好的路徑作為主傳輸路徑(藍(lán)樹上路徑)，然而，由于G-MFBG算法仍然是基于MFBG算法所提出的先在拓?fù)渲猩森h(huán)再構(gòu)建紅藍(lán)2棵樹的思想，這導(dǎo)致主傳輸樹(藍(lán)樹)上路徑傳輸性能無法達(dá)到最優(yōu)化，同時，該算法也沒有考慮優(yōu)化備份傳輸樹(紅樹)上的路徑傳輸性能.因此，上述方法均無法滿足數(shù)據(jù)傳輸對于延遲等性能指標(biāo)的要求[19].綜上所述，對于大數(shù)據(jù)傳輸，不僅要保障數(shù)據(jù)無中斷傳輸，還要保障數(shù)據(jù)傳輸性能.
考慮到在數(shù)據(jù)中心網(wǎng)絡(luò)中選擇轉(zhuǎn)發(fā)跳數(shù)較小的路徑可以減少數(shù)據(jù)傳輸延遲、提高流量轉(zhuǎn)發(fā)效率、降低路由節(jié)點或鏈路失效對數(shù)據(jù)傳輸?shù)挠绊慬20]，因此，為了保障無中斷數(shù)據(jù)傳輸并且降低數(shù)據(jù)傳輸路徑的轉(zhuǎn)發(fā)跳數(shù)，本文提出了一種可保障數(shù)據(jù)無中斷傳輸?shù)陌催呅蜻x環(huán)的冗余樹算法CSES(circle selecting by edge sorting based redundant tree algorithm for un-interrupted data delivery).首先，為了減少主傳輸路徑的轉(zhuǎn)發(fā)跳數(shù)，本算法根據(jù)網(wǎng)絡(luò)拓?fù)湟詳?shù)據(jù)源為根節(jié)點構(gòu)建1棵最小傳輸樹作為主傳輸路徑，該樹上根節(jié)點與其他節(jié)點之間的轉(zhuǎn)發(fā)跳數(shù)是最少的;其次，為了降低備份路徑的轉(zhuǎn)發(fā)跳數(shù)并提高抵御多節(jié)點邊失效的能力，對拓?fù)渲胁辉谧钚鬏敇渖系倪呥M(jìn)行排序，將樹上根節(jié)點到邊上2個端點的路徑上節(jié)點數(shù)量之和較小的邊排在前列;隨后，依次將這些邊添加到最小傳輸樹上構(gòu)成冗余環(huán)，并基于冗余環(huán)生成冗余枝添加到最小傳輸樹上，最終形成1棵冗余樹.實驗結(jié)果表明，相比于其他冗余樹算法，基于本文算法構(gòu)建的冗余樹所生成的主備份路徑的轉(zhuǎn)發(fā)跳數(shù)更少并且抵御多節(jié)點邊失效的能力更強(qiáng).
1 問題描述
在數(shù)據(jù)中心網(wǎng)絡(luò)中，當(dāng)某個節(jié)點需要向其他節(jié)點發(fā)送數(shù)據(jù)時，該節(jié)點為數(shù)據(jù)源節(jié)點，其他節(jié)點為目的節(jié)點.本文的目標(biāo)是為數(shù)據(jù)源節(jié)點構(gòu)建到達(dá)目的節(jié)點之間具有最小轉(zhuǎn)發(fā)跳數(shù)的傳輸路徑，并且保障在網(wǎng)絡(luò)中出現(xiàn)單節(jié)點或單鏈路失效時可通過快速啟用具有較小轉(zhuǎn)發(fā)跳數(shù)的備份路徑(不經(jīng)過故障節(jié)點或鏈路的路徑)恢復(fù)源節(jié)點向受網(wǎng)絡(luò)故障影響的節(jié)點傳輸數(shù)據(jù)，同時保障數(shù)據(jù)傳輸具有較強(qiáng)的抵御多點邊失效的能力.
為方便描述本文所采用的方法，將網(wǎng)絡(luò)抽象成1個無向圖G(V,E).其中，V為網(wǎng)絡(luò)拓?fù)渲械墓?jié)點集合，每個節(jié)點表示1個網(wǎng)絡(luò)設(shè)備；E為網(wǎng)絡(luò)拓?fù)渲械倪吋希織l邊表示1條直接連接2個網(wǎng)絡(luò)設(shè)備的數(shù)據(jù)傳輸鏈路.任選拓?fù)渲?個節(jié)點為數(shù)據(jù)源節(jié)點，本文期望構(gòu)建1棵以數(shù)據(jù)源節(jié)點為根節(jié)點的冗余樹，該樹同時包含轉(zhuǎn)發(fā)跳數(shù)優(yōu)化的主備份路徑.在冗余樹上出現(xiàn)任意1個節(jié)點(根節(jié)點除外)或1條邊失效的情況下，冗余樹的根節(jié)點仍然可以通過樹上的備份路徑與其他節(jié)點保持連接，在多點邊失效的情況下，可有效保障冗余樹的根節(jié)點與樹上其他盡可能多的節(jié)點的連通性.需要指出的是，雖然為滿足實時性較強(qiáng)的應(yīng)用對數(shù)據(jù)傳輸可靠性的需求是本文的主要關(guān)注點，然而本文的算法理念與負(fù)載均衡技術(shù)并不沖突：當(dāng)路徑負(fù)載較小時，為保障數(shù)據(jù)傳輸?shù)男芎涂煽啃裕蛇x取最小跳數(shù)傳輸路徑進(jìn)行數(shù)據(jù)傳輸；而當(dāng)路徑負(fù)載較大時，可多路徑均衡負(fù)載即主傳輸路徑和備份路徑都可以用于同時傳輸數(shù)據(jù)，在出現(xiàn)節(jié)點或鏈路故障時，主傳輸路徑與備份路徑互為冗余以實現(xiàn)無中斷數(shù)據(jù)傳輸.
為確保在單節(jié)點或單邊失效情況下能夠為拓?fù)渲泄?jié)點尋找到冗余樹根節(jié)點與之相連的備份路徑，與其他冗余樹算法一樣，本文也假設(shè)網(wǎng)絡(luò)拓?fù)渲腥我?個節(jié)點之間至少存在2條節(jié)點和邊均互不相交的路徑，由于基于Fat-tree[5]以及Camdoop[6]技術(shù)的數(shù)據(jù)中心網(wǎng)絡(luò)中數(shù)據(jù)交換節(jié)點(交換機(jī)或服務(wù)器)之間的連通性非常豐富，因此上述假設(shè)的合理性得以保障.一個滿足本文假設(shè)的網(wǎng)絡(luò)拓?fù)淙鐖D1所示:
Fig. 1 Network topology.圖1 網(wǎng)絡(luò)拓?fù)?/p>
2 冗余樹算法思想
基于引言對現(xiàn)有保障數(shù)據(jù)無中斷傳輸?shù)娜哂鄻渌惴ǖ姆治?，為了減少主備份傳輸路徑的轉(zhuǎn)發(fā)跳數(shù)，本文不采取先構(gòu)建環(huán)再生成主備份傳輸路徑的方式，而是首先基于Dijkstra算法建立1棵最小傳輸樹作為主傳輸路徑.
定義1. 最小傳輸樹.是網(wǎng)絡(luò)拓?fù)渲?棵以節(jié)點s為根節(jié)點的樹，該樹上根節(jié)點s到其他任意1個節(jié)點x的轉(zhuǎn)發(fā)跳數(shù)是網(wǎng)絡(luò)拓?fù)渲泄?jié)點s到節(jié)點x的所有路徑中轉(zhuǎn)發(fā)跳數(shù)最少的.
在圖1中以節(jié)點A為根節(jié)點的1棵最小傳輸樹如圖2所示:
Fig. 2 The minimal delivery tree.圖2 最小傳輸樹
2.1基于剩余邊排序的選環(huán)
本文以通過向最小傳輸樹上添加剩余邊構(gòu)建冗余環(huán)的方式為最小傳輸樹上節(jié)點尋找轉(zhuǎn)發(fā)跳數(shù)較少的備份路徑.
定義2. 剩余邊.是網(wǎng)絡(luò)拓?fù)渲胁辉谧钚鬏敇渖系倪?
定義3. 冗余環(huán).是基于剩余邊和最小傳輸樹所形成的環(huán)，當(dāng)該環(huán)上有1個節(jié)點或1條邊失效時，環(huán)上其他節(jié)點與最小傳輸樹根節(jié)點之間仍然存在可達(dá)路徑.
結(jié)合圖2所示最小傳輸樹可知，圖1中的邊(B,C)為1條剩余邊，將該剩余邊加入圖2中的最小傳輸樹中，可構(gòu)成環(huán)(A,B,C,A).當(dāng)該環(huán)上任意1個節(jié)點(不包含A)或1條邊失效時，環(huán)上其他節(jié)點仍可以與根節(jié)點A保持連接，因此該環(huán)為冗余環(huán).
然而，需要指出的是，基于不同冗余環(huán)所形成的同一節(jié)點的備份路徑的轉(zhuǎn)發(fā)跳數(shù)是不同的，由圖1和圖2可知，包含根節(jié)點A和節(jié)點G的冗余環(huán)有多個，如(A,F,G,J,C,A)和(A,F,G,H,A)，當(dāng)節(jié)點F失效時，根節(jié)點A到達(dá)節(jié)點G的備份路徑(A,C,J,G)的轉(zhuǎn)發(fā)跳數(shù)為3，另一條備份路徑(A,H,G)的轉(zhuǎn)發(fā)跳數(shù)則為2.因此，為了給最小傳輸樹上的節(jié)點構(gòu)建具有較少轉(zhuǎn)發(fā)跳數(shù)的備份路徑，本文首先對剩余邊按照邊的節(jié)點度進(jìn)行排序，然后再進(jìn)行冗余環(huán)的構(gòu)建.
定義4. 如果剩余邊e的2個頂點分別為x和y，則剩余邊e的節(jié)點度NDe為最小傳輸樹上根節(jié)點s分別到節(jié)點x和節(jié)點y的路徑上所包含的節(jié)點數(shù)量之和.
為了減少備份路徑的轉(zhuǎn)發(fā)跳數(shù)，本文并非隨機(jī)選擇剩余邊和最小傳輸樹構(gòu)建冗余環(huán)，而是先為每一條剩余邊e計算其節(jié)點度NDe，然后根據(jù)節(jié)點度值從小到大對剩余邊進(jìn)行排序，這樣做在減少備份路徑的轉(zhuǎn)發(fā)跳數(shù)的同時也提高了冗余樹抵御多點邊失效的能力.接著，按照從小到大的順序依次將剩余邊添加到最小傳輸樹上構(gòu)建冗余環(huán).然而值得注意的是，剩余邊和最小傳輸樹所形成的環(huán)并非都是冗余環(huán).以圖2為例，將剩余邊(E,I)加入到最小傳輸樹上，可構(gòu)成環(huán)(B,E,I,B)，由于該環(huán)上節(jié)點B為根節(jié)點A到達(dá)節(jié)點E和節(jié)點I必須要經(jīng)過的節(jié)點，一旦節(jié)點B失效，則無路徑可將節(jié)點E和節(jié)點I與節(jié)點A相連，因此根據(jù)定義3可知環(huán)(B,E,I,B)不是冗余環(huán).
定理1. 如果1個基于剩余邊和最小傳輸樹所形成的環(huán)滿足以下條件之一：
1) 該環(huán)包含根節(jié)點；
2) 該環(huán)中至少有2個節(jié)點屬于其他冗余環(huán)；
則該環(huán)是冗余環(huán).
證明. 1)由于該環(huán)包含根節(jié)點，所以從該環(huán)上去掉除根節(jié)點以外的任意1個節(jié)點或1條邊，該環(huán)上剩余節(jié)點仍然可以與根節(jié)點相連通，根據(jù)定義3可知，該環(huán)為冗余環(huán).2)由于該環(huán)中至少有2個節(jié)點屬于其他冗余環(huán)，不失一般性，設(shè)這2個節(jié)點分別為x和y，根據(jù)定義3可知，節(jié)點x和節(jié)點y與根節(jié)點之間一定存在可達(dá)路徑，當(dāng)該環(huán)上1個節(jié)點(包括節(jié)點x和節(jié)點y)失效時，該環(huán)其他節(jié)點至少可以通過節(jié)點x和節(jié)點y中的1個節(jié)點與根節(jié)點相連接，因此該環(huán)是冗余環(huán).
證畢.
根據(jù)定理1，對于由網(wǎng)絡(luò)拓?fù)銰(V,E)生成的最小傳輸樹和剩余邊序列Seq，基于剩余邊排序的冗余環(huán)構(gòu)建方法如下：
1) 初始化，令節(jié)點集合T={s}，其中s為網(wǎng)絡(luò)拓?fù)銰的最小傳輸樹的根節(jié)點，按序?qū)⑹Ｓ噙呅蛄蠸eq中的剩余邊添加到最小傳輸樹上形成相應(yīng)的環(huán)并按序存儲這些環(huán).
2) 讀取序列Seq中排在最前面的剩余邊在最小傳輸樹上形成的環(huán).
3) 如果該環(huán)包含根節(jié)點s或者至少已有2個節(jié)點屬于T，則該環(huán)為冗余環(huán)，將環(huán)上不在T中的節(jié)點添加到T，同時從Seq中刪除該剩余邊；否則，讀取Seq中的下一條剩余邊在最小傳輸樹上形成的環(huán)，返回到步驟3)繼續(xù)執(zhí)行.
4) 如果T=V或者Seq=?，則構(gòu)建冗余環(huán)的過程結(jié)束，否則返回到步驟2)繼續(xù)執(zhí)行.
2.2冗余樹的生成
當(dāng)冗余環(huán)上1個節(jié)點或1條邊失效時，該環(huán)上其他節(jié)點通過剩余邊仍然可達(dá)最小傳輸樹的根節(jié)點.因此，可以將構(gòu)成冗余環(huán)的剩余邊作為冗余枝添加到最小傳輸樹上，從而生成1棵冗余樹.假設(shè)構(gòu)成冗余環(huán)的剩余邊e的2個頂點分別為x和y，那么添加冗余枝的方法如下：
1) 在構(gòu)建冗余環(huán)的過程中，如果構(gòu)成冗余環(huán)的剩余邊e只有1個頂點為根節(jié)點或已經(jīng)屬于其他冗余環(huán)，不失一般性，設(shè)該頂點為x，則將邊(x,y)添加到最小傳輸樹的節(jié)點x上，使得節(jié)點y成為節(jié)點x在冗余樹上的子節(jié)點，從而構(gòu)成根節(jié)點通過節(jié)點x到達(dá)節(jié)點y的備份路徑.而節(jié)點x要么是根節(jié)點，要么屬于其他冗余環(huán)，均已具有根節(jié)點可達(dá)的備份路徑，不需要通過在節(jié)點y上添加冗余枝的方式構(gòu)成根節(jié)點到達(dá)節(jié)點x的備份路徑.
2) 在構(gòu)建冗余環(huán)的過程中，如果構(gòu)成冗余環(huán)的剩余邊e的2個頂點都不是根節(jié)點，也都不屬于其他冗余環(huán)，則在最小傳輸樹的節(jié)點x和節(jié)點y上分別添加邊(x,y)和邊(y,x)，形成2條冗余枝，從而分別構(gòu)成根節(jié)點通過節(jié)點x到達(dá)節(jié)點y的備份路徑和通過節(jié)點y到達(dá)節(jié)點x的備份路徑，最后在1個冗余枝序列中按序?qū)⑸傻娜哂嘀尤?，該序列用于表示冗余枝加入最小傳輸樹的順?
基于上述方法，在選擇冗余環(huán)的過程中不斷添加冗余枝到最小傳輸樹上，直到基于剩余邊排序的選環(huán)過程結(jié)束，最終生成1棵基于最小傳輸樹的冗余樹.以圖1中節(jié)點A作為根節(jié)點所生成的冗余樹如圖3所示(具體生成步驟將作為算法示例在第3節(jié)中給出)，其中實邊表示最小傳輸樹上的邊，虛邊表示冗余枝，虛邊上的標(biāo)號表示冗余枝被添加到最小傳輸樹上的順序，標(biāo)號的目的是為了在根據(jù)冗余樹生成根節(jié)點A到達(dá)其他節(jié)點的備份下一跳路徑時，能夠體現(xiàn)對備份路徑轉(zhuǎn)發(fā)跳數(shù)的優(yōu)化.
Fig. 3 The redundant tree.圖3 冗余樹
根據(jù)帶有冗余枝標(biāo)號的冗余樹，可以生成冗余樹上根節(jié)點到其他節(jié)點的主備份傳輸路徑的路由轉(zhuǎn)發(fā)表.對于根節(jié)點為s的冗余樹，其路由轉(zhuǎn)發(fā)表的具體生成方法為：
1) 在冗余樹中的最小傳輸樹上，對于根節(jié)點s的每一個子節(jié)點，分別遍歷該子節(jié)點的所有子樹，將該子節(jié)點設(shè)為到達(dá)自身及其在最小傳輸樹上所有子孫節(jié)點的主下一跳.
3) 當(dāng)所有冗余枝按照生成順序被遍歷完后，根節(jié)點s的主備傳輸路徑轉(zhuǎn)發(fā)表生成完畢.
根據(jù)上述路由轉(zhuǎn)發(fā)表的生成方法，以圖3為例，節(jié)點A的轉(zhuǎn)發(fā)表如圖4所示.
Fig. 4 The forwarding table of the primarysecondary delivery paths for node A.圖4 節(jié)點A的主備傳輸路徑轉(zhuǎn)發(fā)表
3 算法描述
基于第2節(jié)對冗余樹算法思想的介紹，本節(jié)給出冗余樹構(gòu)建算法的具體描述，并通過示例對算法的執(zhí)行過程進(jìn)行說明.為方便描述算法，設(shè)Ere為剩余邊集合，Seq為剩余邊序列，用T表示參與冗余環(huán)構(gòu)建的節(jié)點集合，對于網(wǎng)絡(luò)拓?fù)銰(V,E)，以s∈V為根節(jié)點的冗余樹的構(gòu)建算法如算法1所示：
算法1. 冗余樹構(gòu)建算法.
輸入：G(V,E),s,Ere,Seq,T;
輸出：冗余樹.
①T={s},Ere={},Seq=[];
② 根據(jù)G(V,E)和根節(jié)點s使用Dijkstra算法構(gòu)建最小傳輸樹Tr(V,Emin);
(2)真空低溫烹飪。將腌制好的雞翅放入真空包裝袋，進(jìn)行真空包裝，放在烤架上，再放入烤箱中間層，選擇蒸汽低溫烹調(diào)模式，調(diào)節(jié)溫度、時間，然后開始低溫烹飪。
③Ere=E-Emin;
④ for eache∈Eredo
⑤ 計算邊e的節(jié)點度NDe;
⑥ 按照節(jié)點度值從小到大的順序?qū)⑦卐插入到Seq中;
⑦ end for
⑧ 按序?qū)eq中的邊加入到Tr中構(gòu)成相應(yīng)的環(huán)R(Vring)，并按序存儲這些環(huán);
⑨i=0;*標(biāo)記冗余枝的添加順序*
⑩ while (T≠V) do
下面對構(gòu)建冗余樹算法的時間復(fù)雜度進(jìn)行分析：設(shè)網(wǎng)絡(luò)拓?fù)渲泄?jié)點數(shù)量為n，邊的數(shù)量為m，剩余邊數(shù)量為k(k1) 針對網(wǎng)絡(luò)拓?fù)涫褂肈ijkstra算法生成最小傳輸樹，所需時間復(fù)雜度為O(n2)；
2) 計算1條剩余邊的節(jié)點度所需時間復(fù)雜度為O(logn)，故總的計算節(jié)點度的時間復(fù)雜度為O(klogn)，對剩余邊基于節(jié)點度由小到大進(jìn)行排序，所需時間復(fù)雜度為O(k2)，可知該部分所需時間復(fù)雜度為O(klogn+k2)；
3) 為每條剩余邊在最小傳輸樹上構(gòu)建相應(yīng)的環(huán)，每次構(gòu)環(huán)的最壞時間復(fù)雜度為O(logn)，因此總的構(gòu)環(huán)時間復(fù)雜度為O(klogn)；
4) 在隨后的冗余樹生成過程中，在最壞情況下每遍歷1次剩余邊序列只有1個節(jié)點加入節(jié)點集合T，由于節(jié)點集合T初始包含根節(jié)點且第1個形成的冗余環(huán)至少包含3個節(jié)點(其中1個是根節(jié)點)，可知最多要遍歷n-2次剩余邊序列，因此冗余樹生成部分的最壞時間復(fù)雜度為O(kn).
綜上所述，整個構(gòu)建冗余樹算法的時間復(fù)雜度為O(n2+k2+klogn+kn).作為比較，MFBG算法[13]與G-MFBG算法[18]的時間復(fù)雜度分別為O(n2(m+n))和O(n2(m+nlogn)).相比其他算法，本文算法在提升主傳輸路徑以及備份傳輸路徑性能的同時還降低了算法時間復(fù)雜度.
下面以圖1所示網(wǎng)絡(luò)拓?fù)錇槔?，說明構(gòu)建以A為根節(jié)點的冗余樹的具體過程：
1) 基于Dijkstra算法生成以A為根節(jié)點的最小傳輸樹，如圖2所示，并對冗余環(huán)節(jié)點集合T賦初值T={A}.
2) 根據(jù)圖1和圖2，將剩余邊按照邊的節(jié)點度進(jìn)行排序，得到的剩余邊序列RS如表1所示.隨后，按序?qū)⑹Ｓ噙吿砑拥阶钚鬏敇渖闲纬上鄳?yīng)的環(huán).
Table 1 The Sorting Table of Redundant Edge
Fig. 5 Selecting (B,C).圖5 選取(B,C)
3) 讀取剩余邊序列中的第1條邊(B,C)在最小傳輸樹上形成的環(huán)(A,B,C,A)，如圖5(a)所示.由于該環(huán)包含根節(jié)點A，可知該環(huán)為冗余環(huán).由于邊(B,C) 上的2個端點都不屬于T，即節(jié)點B和節(jié)點C都不屬于其他冗余環(huán)，因此分別向最小傳輸樹上的節(jié)點B和節(jié)點C添加冗余枝(B,C)和(C,B)，并都標(biāo)上序號1，生成的冗余樹如圖5(b)所示.隨后將環(huán)(A,B,C,A)上不在T中的節(jié)點B和C加入到T中得到更新后的T={A,B,C}，并將邊(B,C)從剩余邊序列中刪除，更新后的剩余邊序列如圖5(c)所示.
4) 讀取更新后的剩余邊序列中的第1條邊(F,C)在最小傳輸樹上形成的環(huán)(A,F,C,A)，如圖6(a)所示.由于該環(huán)包含根節(jié)點A，可知該環(huán)為冗余環(huán).由于邊(F,C)上端點C已經(jīng)屬于T，即節(jié)點C已屬于其他冗余環(huán)，因此只需向最小傳輸樹上的節(jié)點C添加冗余枝(C,F)并標(biāo)上序號2即可，生成的冗余樹如圖6(b)所示.隨后將環(huán)(A,F,C,A)上不在T中的節(jié)點F加入到T中得到更新后的T={A,B,C,F}，并將邊(F,C)從剩余邊序列中刪除，更新后的剩余邊序列如圖6(c)所示.
Fig. 6 Selecting (F,C).圖6 選取(F,C)
Fig. 7 Selecting (H,F).圖7 選取(H,F)
5) 讀取更新后的剩余邊序列中的第1條邊(H,F)在最小傳輸樹上形成的環(huán)(A,H,F,A)，如圖7(a)所示.由于該環(huán)包含根節(jié)點A，可知該環(huán)為冗余環(huán).由于邊(H,F)上端點F已經(jīng)屬于T，即節(jié)點F已屬于其他冗余環(huán)，因此只需向最小傳輸樹上的節(jié)點F添加冗余枝(F,H)并標(biāo)上序號3即可，生成的冗余樹如圖7(b)所示.隨后將環(huán)(A,H,F,A)上不在T中的節(jié)點H加入到T中得到更新后的T={A,B,C,F,H}，并將邊(H,F)從剩余邊序列中刪除，更新后的剩余邊序列如圖7(c)所示.
6) 讀取更新后的剩余邊序列中的第1條邊(B,J)在最小傳輸樹上形成的環(huán)(A,B,J,C,A)，如圖8(a)所示.由于該環(huán)包含根節(jié)點A，可知該環(huán)為冗余環(huán).由于邊(B,J)上端點B已經(jīng)屬于T，即節(jié)點B已屬于其他冗余環(huán)，因此只需向最小傳輸樹上的節(jié)點B添加冗余枝(B,J)并標(biāo)上序號4即可，生成的冗余樹如圖8(b)所示.隨后將環(huán)(A,B,J,C,A)上不在T中的節(jié)點J加入到T中得到更新后的T={A,B,C,F,H,J}，并將邊(B,J)從剩余邊序列中刪除，更新后的剩余邊序列如圖8(c)所示.
Fig. 8 Selecting (B,J).圖8 選取(B,J)
Fig. 9 Selecting (H,G).圖9 選取(H,G)
7) 讀取更新后的剩余邊序列中的第1條邊(H,G)在最小傳輸樹上形成的環(huán)(A,H,G,F,A)，如圖9(a)所示.由于該環(huán)包含根節(jié)點A，可知該環(huán)為冗余環(huán).由于邊(H,G)上端點H已經(jīng)屬于T，即節(jié)點H已屬于其他冗余環(huán)，因此只需向最小傳輸樹上的節(jié)點H添加冗余枝(H,G)并標(biāo)上序號4即可，生成的冗余樹如圖9(b)所示.隨后將環(huán)(A,H,G,F,A)上不在T中的節(jié)點G加入到T中得到更新后的T={A,B,C,F,H,J,G}，并將邊(H,G)從剩余邊序列中刪除，更新后的剩余邊序列如圖9(c)所示.
8) 讀取更新后的剩余邊序列中的第1條邊(E,I)在最小傳輸樹上形成的環(huán)(B,E,I,B)，如圖10(a)所示.由于該環(huán)上只有1個節(jié)點B屬于T且不包含根節(jié)點A，可知該環(huán)不是冗余環(huán)，則將邊(E,I)擱置，保持冗余樹、集合T和剩余邊序列均不變，如圖10(b)(c)所示.
9) 由于邊(E,I)在最小傳輸樹上形成的環(huán)不是冗余環(huán)，則讀取剩余邊序列中的下一條邊(G,J)與最小傳輸樹所形成的環(huán)(A,F,G,J,C,A)，如圖11(a)所示.由于該環(huán)包含根節(jié)點A，可知該環(huán)為冗余環(huán)，然而由于該環(huán)上所有節(jié)點都已經(jīng)屬于T，說明環(huán)上除根節(jié)點A之外的所有節(jié)點都已存在與根節(jié)點A相通的備份路徑，則保持冗余樹和集合T不變，如圖11(b)所示，只需將邊(G,J)從剩余邊序列中刪除即可，更新后的剩余邊序列如圖11(c)所示.
Fig. 11 Selecting (G,J).圖11 選取(G,J)
10) 由于邊(G,J)在最小傳輸樹上形成的環(huán)是冗余環(huán)，需要讀取更新后的剩余邊序列中的第1條邊(E,I)與最小傳輸樹所形成的環(huán)(B,E,I,B)，如圖12(a)所示.由于該環(huán)上仍然只有1個節(jié)點B屬于T且不包含根節(jié)點A，可知該環(huán)不是冗余環(huán)，則繼續(xù)將邊(E,I)擱置，保持冗余樹、集合T和剩余邊序列均不變，如圖12(b)(c)所示.
Fig. 12 Selecting (E,I).圖12 選取(E,I)
11) 由于邊(E,I)在最小傳輸樹上形成的環(huán)不是冗余環(huán)，則讀取剩余邊序列中的下一條邊(D,E)與最小傳輸樹所形成的環(huán)(A,C,J,D,E,B,A)，如圖13(a)所示.由于該環(huán)包含根節(jié)點A，可知該環(huán)為冗余環(huán).由于邊(D,E)上的2個節(jié)點都不屬于T，即節(jié)點D和節(jié)點E都不屬于其他冗余環(huán)，因此分別向最小傳輸樹上的節(jié)點D和節(jié)點E添加冗余枝(D,E)和(E,D)，并都標(biāo)上序號6，生成的冗余樹如圖13(b)所示.隨后將環(huán)(A,C,J,D,E,B,A)上不在T中的節(jié)點D和節(jié)點E加入到T中得到更新后的T={A,B,C,F,H,J,G,D,E}，并將邊(D,E)從剩余邊序列中刪除，更新后的剩余邊序列如圖13(c)所示.
Fig. 13 Selecting (D,E).圖13 選取(D,E)
12) 讀取更新后的剩余邊序列中的第1條邊(E,I)在最小傳輸樹上形成的環(huán)(B,E,I,B)，如圖14(a)所示.由于此時該環(huán)上的節(jié)點B和E均已經(jīng)加入T，因此該環(huán)上已經(jīng)有2個節(jié)點屬于T，可知該環(huán)為冗余環(huán).由于邊(E,I)上端點E已經(jīng)屬于T，即節(jié)點E已屬于其他冗余環(huán)，因此只需向最小傳輸樹上的節(jié)點E添加冗余枝(E,I)并標(biāo)上序號7即可，生成的冗余樹如圖14(b)所示.隨后將環(huán)(B,E,I,B)上不在T中的節(jié)點I加入到T中得到更新后的T={A,B,C,F,H,J,G,D,E,I}，并將邊(E,I)從剩余邊序列中刪除，更新后的剩余邊序列如圖14(c)所示.由于此時有T=V，冗余樹構(gòu)建結(jié)束，此時所構(gòu)建的冗余樹即為最終的冗余樹，與圖3所示冗余樹完全相同.
Fig. 14 Selecting (E,I).圖14 選取(E,I)
4 實 驗
為了驗證本文提出的CSES算法的效能，使用NS2構(gòu)建網(wǎng)絡(luò)仿真環(huán)境，使用Java作為開發(fā)工具.首先，為與其他冗余樹算法進(jìn)行公平的比較，仿真所需的部分拓?fù)鋮⒄瘴墨I(xiàn)[18]所提出的拓?fù)湟?guī)模并由拓?fù)渖善鰾RITE生成，節(jié)點規(guī)模分別是50,100,200節(jié)點，邊的規(guī)模分別為3n和nlbn，其中n為節(jié)點數(shù).因此可生成6種不同規(guī)模的拓?fù)?，可用?jié)點數(shù)×邊數(shù)的形式表示，即拓?fù)?為50×150，拓?fù)?為50×250，拓?fù)?為100×300，拓?fù)?為100×600，拓?fù)?為200×600，拓?fù)?為200×1400.其次，為驗證本文算法在數(shù)據(jù)中心網(wǎng)絡(luò)拓?fù)渲械挠行裕勒瘴墨I(xiàn)[5]中所展示的基于Fat-tree的數(shù)據(jù)中心網(wǎng)絡(luò)拓?fù)錁?gòu)建仿真網(wǎng)絡(luò)拓?fù)洌⒁罁?jù)該拓?fù)鋵Ρ缺疚呐c其他冗余樹算法的效能.
實驗1. 比較不同規(guī)模拓?fù)湎禄贑SES算法、MFBG算法、G-MFBG算法所生成的主傳輸路徑的轉(zhuǎn)發(fā)跳數(shù).
首先，分別在6種不同拓?fù)渲须S機(jī)選擇1個節(jié)點為數(shù)據(jù)源節(jié)點，使用CSES，MFBG，G-MFBG算法生成傳輸樹；然后計算傳輸樹上根結(jié)點到達(dá)其他節(jié)點的轉(zhuǎn)發(fā)跳數(shù)的平均值，對上述實驗重復(fù)50次，結(jié)果取平均值.如圖15所示，基于CSES算法的傳輸樹具有最小的平均轉(zhuǎn)發(fā)跳數(shù);由于MFBG算法在構(gòu)建傳輸樹時沒有考慮到傳輸路徑的轉(zhuǎn)發(fā)跳數(shù)，隨機(jī)選環(huán)策略導(dǎo)致平均轉(zhuǎn)發(fā)跳數(shù)較大.盡管G-MFBG算法考慮到路徑性能，但是其所得平均轉(zhuǎn)發(fā)跳數(shù)高于CSES算法所得平均轉(zhuǎn)發(fā)跳數(shù)，這是因為CSES算法生成的路徑具有最小轉(zhuǎn)發(fā)跳數(shù).
Fig. 15 The comparison of the average forwarding hop count of the primary path.圖15 主傳輸路徑平均轉(zhuǎn)發(fā)跳數(shù)比較
實驗2. 比較不同規(guī)模拓?fù)湎禄贑SES算法、 MFBG算法、G-MFBG算法所生成的備份路徑的轉(zhuǎn)發(fā)跳數(shù).
首先，比較單邊失效后不同算法產(chǎn)生的備份路徑的平均轉(zhuǎn)發(fā)跳數(shù)，對3種算法隨機(jī)選擇相同的1條邊令其失效，仿真結(jié)果如圖16(a)所示.CSES算法所得備份路徑的平均轉(zhuǎn)發(fā)跳數(shù)最少，這是因為該算法采取了基于剩余邊節(jié)點度排序的選環(huán)方法，從而減少了備份路徑的平均轉(zhuǎn)發(fā)跳數(shù).對于G-MFBG算法，由于其對備份路徑的轉(zhuǎn)發(fā)跳數(shù)沒有考慮，故該算法產(chǎn)生的備份路徑的平均轉(zhuǎn)發(fā)跳數(shù)較多.其次，比較單節(jié)點失效后不同算法產(chǎn)生的備份路徑的平均路由，仍然對3種算法隨機(jī)選擇相同的1個節(jié)點(非根節(jié)點)令其失效，仿真結(jié)果如圖16(b)所示.盡管相比單邊失效情況下CSES算法所得備份路徑的平均轉(zhuǎn)發(fā)跳數(shù)有所增加，但是CSES算法所得備份路徑的平均轉(zhuǎn)發(fā)跳數(shù)仍然是最少的，這仍然是因為CSES算法為了降低備份路徑的轉(zhuǎn)發(fā)跳數(shù)對剩余邊按節(jié)點度值進(jìn)行了排序.
Fig. 16 The comparison of the average forwarding hop count of the secondary path in the case of single edgenode failure.圖16 單邊點失效時備份路徑平均轉(zhuǎn)發(fā)跳數(shù)比較
實驗3. 驗證在相同拓?fù)湟?guī)模和不同節(jié)點失效比例下，基于CSES算法、MFBG算法、G-MFBG算法所生成的冗余樹抵御多節(jié)點失效的能力.
為方便比較，使用在啟用備份路徑后尚能與根節(jié)點保持連接的節(jié)點數(shù)目與總節(jié)點數(shù)目的比例(簡稱連接節(jié)點比例)作為度量指標(biāo).首先，針對50×150，100×300，200×600這3種拓?fù)浞謩e設(shè)置5%～50%的節(jié)點失效率(增長幅度為5%)，并通過遍歷啟用相應(yīng)冗余枝后的冗余樹來計算連接節(jié)點比例，分別重復(fù)計算50次，最終將所有結(jié)果取平均值，實驗結(jié)果如圖17所示.在不同的拓?fù)渲?，MFBG算法抵御多節(jié)點失效的能力最差，而CSES算法抵御多節(jié)點失效能力最好，這是因為CSES算法使用節(jié)點度值對剩余邊進(jìn)行排序，從而可生成更多的冗余枝用于構(gòu)建備份路徑.
Fig. 17 The comparison of the resistant ability in the case of multiple nodes failure.圖17 不同節(jié)點失效比例下抵御多節(jié)點失效能力
實驗4. 驗證在相同拓?fù)湟?guī)模和不同邊失效比例下，基于CSES算法、MFBG算法、G-MFBG算法所生成的冗余樹抵御多邊失效的能力.
與實驗3同樣使用節(jié)點連接比例作為度量指標(biāo)，針對50×150，100×300，200×600這3種拓?fù)浞謩e設(shè)置5%～50%的邊失效率(增長幅度為5%)并計算連接節(jié)點比例，分別重復(fù)計算50次，最終將所有結(jié)果取平均值，實驗結(jié)果如圖18所示.在不同的拓?fù)渲?，相比于多?jié)點失效情況，多邊失效情況下各個算法所得出的連接節(jié)點比例有所提高，其中，本文CSES算法依舊保持最高的連接節(jié)點比例，MFBG算法的抵御多邊失效能力最差.
Fig. 18 The comparison of the resistant ability in the case of the multiple edges failure.圖18 不同邊失效比例下抵御多邊失效能力
實驗5. 在基于Fat-tree的數(shù)據(jù)中心網(wǎng)絡(luò)拓?fù)湎买炞CCSES算法、MFBG算法、G-MFBG算法的效能.
依照文獻(xiàn)[5]中所展示的基于Fat-tree的數(shù)據(jù)中心網(wǎng)絡(luò)拓?fù)渌鶚?gòu)建仿真網(wǎng)絡(luò)拓?fù)淙鐖D19所示.
Fig. 19 The Fat-tree based network topology in data center.圖19 基于Fat-tree的數(shù)據(jù)中心網(wǎng)絡(luò)拓?fù)?/p>
1) 隨機(jī)選擇1個邊界層交換機(jī)作為數(shù)據(jù)源節(jié)點，使用CSES，MFBG，G-MFBG算法生成傳輸樹，然后計算傳輸樹上根結(jié)點到達(dá)其他節(jié)點(邊界層交換機(jī))的轉(zhuǎn)發(fā)跳數(shù)的平均值，對上述實驗重復(fù)50次，結(jié)果取平均值，實驗結(jié)果如圖20所示，基于CSES算法的傳輸樹具有最小的平均轉(zhuǎn)發(fā)跳數(shù).
2) 比較單邊失效后不同算法產(chǎn)生的備份路徑的平均轉(zhuǎn)發(fā)跳數(shù)，對3種算法隨機(jī)選擇拓?fù)渲邢嗤?條邊令其失效，仿真結(jié)果如圖20所示，CSES算法所得備份路徑的平均轉(zhuǎn)發(fā)跳數(shù)最少.
Fig. 20 The comparison of the average forwarding hop count of the primarysecondary path.圖20 主備份傳輸路徑的平均轉(zhuǎn)發(fā)跳數(shù)比較
3) 比較單節(jié)點失效后不同算法產(chǎn)生的備份路徑的平均路由，在3種算法中隨機(jī)選擇相同的1個節(jié)點(非根節(jié)點)令其失效，仿真結(jié)果如圖20所示，盡管相比單邊失效情況下CSES算法所得備份路徑的平均轉(zhuǎn)發(fā)跳數(shù)有所增加，但是CSES算法所得備份路徑的平均轉(zhuǎn)發(fā)跳數(shù)仍然是最少的，這是因為CSES算法為了降低備份路徑的轉(zhuǎn)發(fā)跳數(shù)對剩余邊按節(jié)點度值進(jìn)行了排序.
Fig. 21 The comparison of the resistant ability in the case of multiple nodesedges failure.圖21 不同節(jié)點失效比例下抵御多節(jié)點邊失效能力比較
5 結(jié)束語
本文提出一種可保障數(shù)據(jù)無中斷傳輸?shù)陌催呅蜻x環(huán)的冗余樹算法.該算法首先基于網(wǎng)絡(luò)拓?fù)錁?gòu)建最小傳輸樹，該樹上根節(jié)點與其他節(jié)點之間的轉(zhuǎn)發(fā)跳數(shù)是最少的.隨后，為減少備份路徑的轉(zhuǎn)發(fā)跳數(shù)，本文對剩余邊按節(jié)點度從小到大進(jìn)行排序，依次將剩余邊添加到最小傳輸樹上構(gòu)建冗余環(huán)，并將冗余環(huán)上的冗余枝添加到最小傳輸樹上，最終構(gòu)建一棵冗余樹.實驗結(jié)果表明，相比于其他冗余樹算法，基于本文算法構(gòu)建的冗余樹所生成的主備份路徑的轉(zhuǎn)發(fā)跳數(shù)更少且抵御多節(jié)點邊失效能力更強(qiáng).
[1]Yi Xiaomeng, Liu Fangming, Liu Jiangchuan, et al. Building a network highway for big data: Architecture and challenges[J]. IEEE Networking, 2014, 3(4): 1-25[2]Li Dan, Chen Guihai, Ren Fengyuan, et al. Data center network research progress and trends[J]. Chinese Journal of Computers, 2014, 37(2): 259-274 (in Chinese)(李丹, 陳貴海, 任豐原, 等. 數(shù)據(jù)中心網(wǎng)絡(luò)的研究進(jìn)展與趨勢[J]. 計算機(jī)學(xué)報, 2014, 37(2): 259-274)[3]Greenberg A, Hamilton J R, Jain N, et al. VL2: A scalable and flexible data center network[C]Proc of the ACM SIGCOMM’09. New York: ACM, 2009: 51-62[4]Niranjan M R, Pamboris A, Farrington N, et al. Portland: A scalable fault-tolerant layer 2 data center network fabric[C]Proc of the ACM SIGCOMM’09. New York: ACM, 2009: 39-50[5]Al-Fares M, Loukissas A, Vahdat A. A scalable, commodity data center network architecture[C]Proc of the ACM SIGCOMM’08. New York: ACM, 2008: 63-74[6]Costa P, Donnelly A, Rowstron A, et al. Camdoop: Exploiting in-network aggregation for big data applications[C]Proc of the 9th USENIX Conf on Networked Systems Design and Implementation. Berkeley, CA: USENIX Association, 2012: 51-75[7]Xiao Bailong, Guo Wei, Liu Jun, et al. Research on local route repair algorithm in mobile ad hoc networks[J]. Journal of Computer Research and Development, 2007, 44(8): 1383-1389 (in Chinese)(肖百龍, 郭偉, 劉軍，等. 移動自組網(wǎng)路由局部修復(fù)算法的研究[J]. 計算機(jī)研究與發(fā)展, 2007, 44(8): 1383-1389)[8]Zhang Li, Li Jinbao. Multi-Path based reliable routing in wireless sensor network[J]. Journal of Computer Research and Development, 2011, 48(Suppl 2): 171-175 (in Chinese)(張莉, 李金寶. 無線傳感器網(wǎng)絡(luò)中基于多路徑的可靠路由協(xié)議研[J]. 計算機(jī)研究與發(fā)展, 2011, 48(增刊2): 171-175)[9]Challal Y, Ouadjaout A, Lasla N, et al. Secure and efficient disjoint multipath construction for fault tolerant routing in wireless sensor networks[J]. Journal of Network and Computer Applications, 2011, 34(4): 1380-1397[10]Xu M, Hou M, Wang D, et al. An efficient critical protection scheme for intra-domain routing using link characteristics[J]. Computer Networks, 2013, 57(1): 117-133[11]Suchara M, Xu D, Doverspike R, et al. Network architecture for joint failure recovery and traffic engineering[C]Proc of the ACM Sigmetrics (SIGMETRICS’11). New York: ACM, 2011: 97-108[12]Su Jinshu, Hu Qiaolin, Zhao Baokang. Disruption-free forwarding survivable routing protocols on Internet[J]. Journal of Software, 2010, 21(7): 1589-1604 (in Chinese)(蘇金樹, 胡喬林, 趙寶康. 互聯(lián)網(wǎng)無中斷轉(zhuǎn)發(fā)的生存性路由協(xié)議[J]. 軟件學(xué)報, 2010, 21(7): 1589-1604)[13]Médard M, Finn S G, Barry R A, et al. Redundant trees for preplanned recovery in arbitrary vertex redundant or edge redundant graphs[J]. IEEEACM Trans on Networking, 1999, 7(5): 641-652[14]Aun H, Richard H. Recovery techniques in next generation networks[J]. IEEE Communications Surveys & Tutorials, 2007, 9(3): 2-17[15]Jayavelu G, Ramasubramanian S, Younis O. Maintaining colored trees for disjoint multipath routing under node failures[J]. IEEEACM Trans on Networking, 2009, 17(1): 346-359[16]Cho S, Elhourani T, Ramasubramanian S. Independent directed acyclic graphs for resilient multipath routing[J]. IEEEACM Trans on Networking, 2012, 20(1): 153-162[17]Yong O L, Narasimha R. Constructing disjoint paths for failure recovery and multipath routing[J]. Computer Networks, 2012, 56(2): 719-730[18]Xue G, Chen L, Thulasiraman K. Quality-of-service and quality-of-protection issues in preplanned recovery schemes using redundant trees[J]. Journal on Selected Areas in Communications, 2003, 21(8): 1332-1345[19]Wu K, Xiao J, Ni L M. Rethinking the architecture design of data center networks[J]. Frontiers of Computer Science, 2012, 6(5): 596-603[20]Rojas E, Ibanez G, Gimenez-Guzman J M, et al. All-Path bridging: Path exploration protocols for data center and campus networks[J]. Computer Networks, 2015,79(14): 120-132
Xia Nu, born in 1981. PhD candidate. His main research interests include network management.
Li Wei, born in 1978. Associate professor and master supervisor. Member of China Computer Federation. His main research interests include next generation network architecture and service computing.
Lu You, born in 1977. PhD candidate. Member of China Computer Federation. His main research interests include network management.
Jiang Jian, born in 1986. PhD candidate. His main research interests include network management.
Shan Feng, born in 1985. PhD candidate. His main research interests include wireless sensor network and algorithm design.
Luo Junzhou, born in 1960. Professor and PhD supervisor. Senior member of China Computer Federation. His main research interests include next generation network architecture, protocol engineering, network security, wireless network and cloud computing.
The Redundant Tree Algorithm for Uninterrupted Data Delivery
Xia Nu, Li Wei, Lu You, Jiang Jian, Shan Feng, and Luo Junzhou
(SchoolofComputerScience&Engineering,SoutheastUniversity,Nanjing211189)
With the development of the big data applications, the requirement for guaranteeing un-interrupted data delivery is growing gradually. To address the problem of single nodelink failure, researchers had conducted lots of work. However, current methods for guaranteeing uninterrupted data delivery face the deficiencies of low performance of the primarysecondary delivery paths and the low resistant ability to the multiple nodeslinks failure. In order to solve the above problems, a circle selecting by edge sorting based redundant tree algorithm for uninterrupted data delivery CSES is presented. At first, a minimal delivery tree with the data source as the root node is built in this algorithm, on which the routing hop count of the primary paths is the smallest. Secondly, in order to reduce the hop count of the secondary paths and to enhance the resistant ability of the multiple nodesedges failure, the edges in network topology but not included in the tree are sorted based on the sum of the nodes on the paths between the root node and the two nodes of the edge. Then, the edges are added to the minimal tree to form the redundant circles and the redundant branches of the redundant circles are added to the minimal tree. Finally, a redundant tree rooted by the data source is built. The experimental results show that, compared with the other redundant tree algorithms, the hop count of the primarysecondary paths on the redundant tree built by CSES algorithm is smaller and the resistant ability of multiple nodesedges failure of CSES algorithm is better.
the uninterrupted data delivery; the minimal delivery tree; edge sorting; the redundant circle; the redundant tree
2015-05-21；
2015-10-29
國家自然科學(xué)基金項目(61320106007)；國家“八六三”高技術(shù)研究發(fā)展計劃基金項目(2013AA013503)；江蘇省未來網(wǎng)絡(luò)創(chuàng)新研究院未來網(wǎng)絡(luò)前瞻性研究項目(BY2013095-2-07)；教育部計算機(jī)網(wǎng)絡(luò)與信息集成重點實驗室(東南大學(xué))基金項目(93K-9)；江蘇省網(wǎng)絡(luò)與信息安全重點實驗室基金項目(BM2003201)；無線通信技術(shù)協(xié)同創(chuàng)新中心資助項目；軟件新技術(shù)與產(chǎn)業(yè)化協(xié)同創(chuàng)新中心部分資助項目；住建部科研項目(2015-K6-012)
This work was supported by the National Natural Science Foundation of China (61320106007), the National High Technology Research and Development Program of China (863 Program) (2013AA013503), the Prospective Research Project on Future Networks of Jiangsu Future Networks Innovation Institute (BY2013095-2-07), the Project Funded by Key Laboratory of Computer Network and Information Integration (Southeast University) of Ministry of Education of China (93K-9), the Project Funded by Jiangsu Provincial Key Laboratory of Network and Information Security (BM2003201), the Project Funded by Collaborative Innovation Center of Wireless Communication Technology, the Project Funded by Collaborative Innovation Center of Novel Software Technology and Industrialization, and the Project Funded by Ministry of Housing and Urban-Rural Development (2015-K6-012).
TP391
夏 怒 李 偉 陸 悠 蔣 健 單 馮 羅軍舟
(東南大學(xué)計算機(jī)科學(xué)與工程學(xué)院 南京 211189)
?
可保障數(shù)據(jù)無中斷傳輸?shù)娜哂鄻渌惴ㄑ芯?/p>
夏怒李偉陸悠蔣健單馮羅軍舟
(東南大學(xué)計算機(jī)科學(xué)與工程學(xué)院南京211189)
(xia_nu@seu.edu.cn)
隨著大數(shù)據(jù)應(yīng)用的發(fā)展，保障數(shù)據(jù)無中斷傳輸?shù)男枨笕找嬖鰪?qiáng).針對單點或單鏈路失效的情況，現(xiàn)有的保障數(shù)據(jù)無中斷傳輸方法存在主備份路徑的數(shù)據(jù)傳輸性能較低、抵御多節(jié)點邊失效能力不強(qiáng)等問題.為解決以上問題，提出一種可保障數(shù)據(jù)無中斷傳輸?shù)陌催呅蜻x環(huán)的冗余樹算法CSES(circle selecting by edge sorting based redundant tree algorithm for uninterrupted data delivery)，可用于構(gòu)建數(shù)據(jù)傳輸性能優(yōu)化的主備份路徑，并使數(shù)據(jù)傳輸具有較強(qiáng)的抵御多節(jié)點邊失效的能力. 該算法首先根據(jù)網(wǎng)絡(luò)拓?fù)錁?gòu)建以數(shù)據(jù)源為根節(jié)點的最小傳輸樹，以最小化主傳輸路徑上的轉(zhuǎn)發(fā)跳數(shù)；其次，為了減少備份路徑的轉(zhuǎn)發(fā)跳數(shù)并提高數(shù)據(jù)傳輸?shù)钟喙?jié)點邊失效的能力，對拓?fù)渲胁辉谧钚鬏敇渖系倪呥M(jìn)行排序，將樹上根節(jié)點到邊上2個端點的路徑上節(jié)點數(shù)量之和較小的邊排在前列. 隨后按序?qū)⑦吿砑拥阶钚鬏敇渖弦詷?gòu)建冗余環(huán)，并基于冗余環(huán)生成冗余枝添加到最小傳輸樹上，最終形成以數(shù)據(jù)源為根節(jié)點的冗余樹.實驗結(jié)果表明，相比于其他冗余樹算法，基于CSES算法構(gòu)建的冗余樹所生成的主備份路徑的轉(zhuǎn)發(fā)跳數(shù)更少且抵御多節(jié)點邊失效的能力更強(qiáng).
數(shù)據(jù)無中斷傳輸；最小傳輸樹；邊排序；冗余環(huán)；冗余樹
隨著新型應(yīng)用以及網(wǎng)絡(luò)用戶數(shù)量的快速增長，各個領(lǐng)域的數(shù)據(jù)量急劇增加，為了充分利用大數(shù)據(jù)資源，當(dāng)前絕大多數(shù)研究是圍繞數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)以及數(shù)據(jù)分析等方面展開的，而在網(wǎng)絡(luò)對大數(shù)據(jù)的支撐方面所做的研究甚少.正如文獻(xiàn)[1]指出：研究大數(shù)據(jù)傳輸對于大數(shù)據(jù)應(yīng)用發(fā)展的重要意義；數(shù)據(jù)中心網(wǎng)絡(luò)是支撐大數(shù)據(jù)傳輸?shù)暮诵脑O(shè)施，近年來隨著MapReduce、虛擬機(jī)遷移等數(shù)據(jù)應(yīng)用的發(fā)展，愈來愈多的數(shù)據(jù)需要在數(shù)據(jù)中心內(nèi)傳輸以用于處理和分析，因此數(shù)據(jù)中心網(wǎng)絡(luò)對數(shù)據(jù)傳輸?shù)闹文芰χ苯佑绊懙酱髷?shù)據(jù)應(yīng)用的部署與發(fā)展.然而，隨著數(shù)據(jù)中心網(wǎng)絡(luò)規(guī)模日益擴(kuò)大以及網(wǎng)絡(luò)結(jié)構(gòu)日趨復(fù)雜化，影響網(wǎng)絡(luò)穩(wěn)定性的因素如人為配置錯誤、惡意攻擊、軟件漏洞、路由節(jié)點或鏈路硬件故障等逐漸增多，同時由于數(shù)據(jù)中心網(wǎng)絡(luò)中廣泛采用了低成本的網(wǎng)絡(luò)設(shè)備，致使數(shù)據(jù)中心網(wǎng)絡(luò)面臨愈來愈嚴(yán)重的節(jié)點和鏈路失效風(fēng)險，當(dāng)前數(shù)據(jù)中心支撐的應(yīng)用在執(zhí)行過程中往往需要在短時間內(nèi)傳輸少量數(shù)據(jù)(TCP短流)以實時地響應(yīng)用戶請求(數(shù)據(jù)庫查詢、使用WEB服務(wù)等).對于這類應(yīng)用需求，一個很重要的要求就是快速響應(yīng)，從而數(shù)據(jù)傳輸?shù)目煽啃詫Υ祟悜?yīng)用的執(zhí)行性能有很大影響.此外還值得注意的是，雖然TCP 短流理應(yīng)和 TCP 長流獲得相等的網(wǎng)絡(luò)資源，然而在實際中卻是TCP長流占據(jù)了大部分鏈路帶寬，這導(dǎo)致例如當(dāng)別的用戶在下載大文件時一些用戶打開簡單網(wǎng)頁的時間都會指數(shù)上升，因此如果不能保障TCP長流快速無中斷地傳輸，也會增大TCP短流在傳輸隊列中的等待時間進(jìn)而降低應(yīng)用響應(yīng)用戶請求的速度.因此，需要數(shù)據(jù)中心網(wǎng)絡(luò)能夠提供有效的失效恢復(fù)策略和容錯機(jī)制來保障數(shù)據(jù)傳輸?shù)目煽啃?遺憾的是，有研究表明：現(xiàn)有數(shù)據(jù)中心網(wǎng)絡(luò)針對網(wǎng)絡(luò)節(jié)點失效的容錯性較差[2]，基于鏈路狀態(tài)協(xié)議重新計算數(shù)據(jù)傳輸路徑[3-4]往往導(dǎo)致路由收斂時間過長，無法滿足實時性要求較高的數(shù)據(jù)應(yīng)用的需要.因此，研究可保障數(shù)據(jù)無中斷傳輸?shù)募夹g(shù)具有重要意義.
需要指出的是，雖然數(shù)據(jù)中心網(wǎng)絡(luò)拓?fù)渚哂衅渥陨淼奶攸c，然而以Fat-tree[5]為代表的數(shù)據(jù)中心網(wǎng)絡(luò)拓?fù)渲忻總€中間節(jié)點可以有多個父節(jié)點，即增加了上下層集合交換機(jī)之間以及集合交換機(jī)與核心交換機(jī)之間的鏈路，從而較大幅度地增大了網(wǎng)絡(luò)的連通性，使得一對交換節(jié)點之間有多條路徑相連，因此基于Fat-tree的數(shù)據(jù)中心網(wǎng)絡(luò)中3個層次的交換設(shè)備所構(gòu)成的網(wǎng)絡(luò)拓?fù)淇沙橄蟪梢话憔W(wǎng)絡(luò)拓?fù)?，特別是以Camdoop[6]為代表的服務(wù)器互連并將服務(wù)器作為數(shù)據(jù)處理轉(zhuǎn)發(fā)節(jié)點的數(shù)據(jù)中心網(wǎng)絡(luò)中，服務(wù)器組成的網(wǎng)絡(luò)拓?fù)渑c一般網(wǎng)絡(luò)拓?fù)涓鼮榻咏⑶疫B接度更大.
為了實現(xiàn)數(shù)據(jù)無中斷傳輸，從網(wǎng)絡(luò)故障發(fā)生后減少恢復(fù)數(shù)據(jù)傳輸所需時間的角度出發(fā)，相比發(fā)生節(jié)點或鏈路失效時再重新尋找備份路徑的方法[3-4,7]，預(yù)先計算數(shù)據(jù)傳輸備份路徑被視為一種有效方法.文獻(xiàn)[8]針對由節(jié)點失效或路徑擁塞所導(dǎo)致數(shù)據(jù)無法繼續(xù)轉(zhuǎn)輸?shù)那闆r，將失效路徑上正在轉(zhuǎn)發(fā)的數(shù)據(jù)轉(zhuǎn)移到另一條預(yù)先設(shè)置的備份路徑上，進(jìn)而提高數(shù)據(jù)傳輸可靠性.文獻(xiàn)[9]為了提高備份路徑的負(fù)載均衡以及QoS，提出了在拓?fù)渲袨閿?shù)據(jù)傳輸路徑盡力尋找與其分離度最高且跳數(shù)相近的備份路徑的方法.文獻(xiàn)[10]認(rèn)為網(wǎng)絡(luò)中每個鏈路的失效概率并不相同，因此首先對鏈路的重要性進(jìn)行評估，然后根據(jù)評估結(jié)果有選擇地為重要鏈路預(yù)先計算與其不相交的冗余路徑.文獻(xiàn)[11]為拓?fù)渲忻恳粚?jié)點設(shè)置多條備份路徑，以便當(dāng)網(wǎng)絡(luò)故障發(fā)生時在保障數(shù)據(jù)無中斷傳輸?shù)耐瑫r實現(xiàn)負(fù)載均衡.然而，上述方法針對每條鏈路或每個節(jié)點失效尋找備份路徑時需要反復(fù)深度遍歷網(wǎng)絡(luò)拓?fù)洌瑢?dǎo)致算法復(fù)雜度較高.值得注意的是，由于冗余樹算法在保障數(shù)據(jù)無中斷傳輸方面具有算法復(fù)雜度較小、故障恢復(fù)時間短等特點[12]，逐漸引起研究者的關(guān)注，其中Médard等人提出的冗余樹算法MFBG[13]被廣泛使用并被認(rèn)為對未來網(wǎng)絡(luò)故障快速恢復(fù)技術(shù)的發(fā)展具有重要意義[14].MFBG算法通過在網(wǎng)絡(luò)拓?fù)渲须S機(jī)構(gòu)建環(huán)的方式構(gòu)建藍(lán)、紅2棵樹，這2棵樹具有共同的根節(jié)點，藍(lán)樹用作數(shù)據(jù)傳輸?shù)闹鳂?primary tree)，紅樹則為備份樹(secondary tree)，在移除拓?fù)渲腥我?個節(jié)點或1條邊后，剩余的節(jié)點仍然可以通過2棵樹中的1棵與根節(jié)點保持連通.然而，該算法在構(gòu)建冗余樹時未考慮對路徑傳輸性能如延遲和開銷等進(jìn)行優(yōu)化，因此其所采取的隨機(jī)選環(huán)方式導(dǎo)致主備份路徑的傳輸性能不佳.一些學(xué)者基于MFBG算法展開進(jìn)一步研究，文獻(xiàn)[15]提出了僅僅利用本地信息構(gòu)建紅藍(lán)2棵樹的方法，文獻(xiàn)[16]通過盡可能多地將拓?fù)渲械倪吋尤胫鱾鬏敇?藍(lán)樹)以期在故障發(fā)生后降低啟用備份路徑的頻率進(jìn)而降低恢復(fù)開銷，文獻(xiàn)[17]構(gòu)建路徑長度接近的紅藍(lán)2棵樹以平衡主備份傳輸路徑的性能.然而，上述方法在多點邊失效的情況下會有較多的節(jié)點失去與數(shù)據(jù)源節(jié)點的連接，抵御多節(jié)點邊失效的能力較差，并且同樣未對紅樹和藍(lán)樹上路徑傳輸性能進(jìn)行優(yōu)化.盡管Xue等人對MFBG算法做出改進(jìn)并提出了G-MFBG算法[18]，優(yōu)先選擇傳輸性能較好的路徑作為主傳輸路徑(藍(lán)樹上路徑)，然而，由于G-MFBG算法仍然是基于MFBG算法所提出的先在拓?fù)渲猩森h(huán)再構(gòu)建紅藍(lán)2棵樹的思想，這導(dǎo)致主傳輸樹(藍(lán)樹)上路徑傳輸性能無法達(dá)到最優(yōu)化，同時，該算法也沒有考慮優(yōu)化備份傳輸樹(紅樹)上的路徑傳輸性能.因此，上述方法均無法滿足數(shù)據(jù)傳輸對于延遲等性能指標(biāo)的要求[19].綜上所述，對于大數(shù)據(jù)傳輸，不僅要保障數(shù)據(jù)無中斷傳輸，還要保障數(shù)據(jù)傳輸性能.
考慮到在數(shù)據(jù)中心網(wǎng)絡(luò)中選擇轉(zhuǎn)發(fā)跳數(shù)較小的路徑可以減少數(shù)據(jù)傳輸延遲、提高流量轉(zhuǎn)發(fā)效率、降低路由節(jié)點或鏈路失效對數(shù)據(jù)傳輸?shù)挠绊慬20]，因此，為了保障無中斷數(shù)據(jù)傳輸并且降低數(shù)據(jù)傳輸路徑的轉(zhuǎn)發(fā)跳數(shù)，本文提出了一種可保障數(shù)據(jù)無中斷傳輸?shù)陌催呅蜻x環(huán)的冗余樹算法CSES(circle selecting by edge sorting based redundant tree algorithm for un-interrupted data delivery).首先，為了減少主傳輸路徑的轉(zhuǎn)發(fā)跳數(shù)，本算法根據(jù)網(wǎng)絡(luò)拓?fù)湟詳?shù)據(jù)源為根節(jié)點構(gòu)建1棵最小傳輸樹作為主傳輸路徑，該樹上根節(jié)點與其他節(jié)點之間的轉(zhuǎn)發(fā)跳數(shù)是最少的;其次，為了降低備份路徑的轉(zhuǎn)發(fā)跳數(shù)并提高抵御多節(jié)點邊失效的能力，對拓?fù)渲胁辉谧钚鬏敇渖系倪呥M(jìn)行排序，將樹上根節(jié)點到邊上2個端點的路徑上節(jié)點數(shù)量之和較小的邊排在前列;隨后，依次將這些邊添加到最小傳輸樹上構(gòu)成冗余環(huán)，并基于冗余環(huán)生成冗余枝添加到最小傳輸樹上，最終形成1棵冗余樹.實驗結(jié)果表明，相比于其他冗余樹算法，基于本文算法構(gòu)建的冗余樹所生成的主備份路徑的轉(zhuǎn)發(fā)跳數(shù)更少并且抵御多節(jié)點邊失效的能力更強(qiáng).
1 問題描述
在數(shù)據(jù)中心網(wǎng)絡(luò)中，當(dāng)某個節(jié)點需要向其他節(jié)點發(fā)送數(shù)據(jù)時，該節(jié)點為數(shù)據(jù)源節(jié)點，其他節(jié)點為目的節(jié)點.本文的目標(biāo)是為數(shù)據(jù)源節(jié)點構(gòu)建到達(dá)目的節(jié)點之間具有最小轉(zhuǎn)發(fā)跳數(shù)的傳輸路徑，并且保障在網(wǎng)絡(luò)中出現(xiàn)單節(jié)點或單鏈路失效時可通過快速啟用具有較小轉(zhuǎn)發(fā)跳數(shù)的備份路徑(不經(jīng)過故障節(jié)點或鏈路的路徑)恢復(fù)源節(jié)點向受網(wǎng)絡(luò)故障影響的節(jié)點傳輸數(shù)據(jù)，同時保障數(shù)據(jù)傳輸具有較強(qiáng)的抵御多點邊失效的能力.
為方便描述本文所采用的方法，將網(wǎng)絡(luò)抽象成1個無向圖G(V,E).其中，V為網(wǎng)絡(luò)拓?fù)渲械墓?jié)點集合，每個節(jié)點表示1個網(wǎng)絡(luò)設(shè)備；E為網(wǎng)絡(luò)拓?fù)渲械倪吋希織l邊表示1條直接連接2個網(wǎng)絡(luò)設(shè)備的數(shù)據(jù)傳輸鏈路.任選拓?fù)渲?個節(jié)點為數(shù)據(jù)源節(jié)點，本文期望構(gòu)建1棵以數(shù)據(jù)源節(jié)點為根節(jié)點的冗余樹，該樹同時包含轉(zhuǎn)發(fā)跳數(shù)優(yōu)化的主備份路徑.在冗余樹上出現(xiàn)任意1個節(jié)點(根節(jié)點除外)或1條邊失效的情況下，冗余樹的根節(jié)點仍然可以通過樹上的備份路徑與其他節(jié)點保持連接，在多點邊失效的情況下，可有效保障冗余樹的根節(jié)點與樹上其他盡可能多的節(jié)點的連通性.需要指出的是，雖然為滿足實時性較強(qiáng)的應(yīng)用對數(shù)據(jù)傳輸可靠性的需求是本文的主要關(guān)注點，然而本文的算法理念與負(fù)載均衡技術(shù)并不沖突：當(dāng)路徑負(fù)載較小時，為保障數(shù)據(jù)傳輸?shù)男芎涂煽啃裕蛇x取最小跳數(shù)傳輸路徑進(jìn)行數(shù)據(jù)傳輸；而當(dāng)路徑負(fù)載較大時，可多路徑均衡負(fù)載即主傳輸路徑和備份路徑都可以用于同時傳輸數(shù)據(jù)，在出現(xiàn)節(jié)點或鏈路故障時，主傳輸路徑與備份路徑互為冗余以實現(xiàn)無中斷數(shù)據(jù)傳輸.
為確保在單節(jié)點或單邊失效情況下能夠為拓?fù)渲泄?jié)點尋找到冗余樹根節(jié)點與之相連的備份路徑，與其他冗余樹算法一樣，本文也假設(shè)網(wǎng)絡(luò)拓?fù)渲腥我?個節(jié)點之間至少存在2條節(jié)點和邊均互不相交的路徑，由于基于Fat-tree[5]以及Camdoop[6]技術(shù)的數(shù)據(jù)中心網(wǎng)絡(luò)中數(shù)據(jù)交換節(jié)點(交換機(jī)或服務(wù)器)之間的連通性非常豐富，因此上述假設(shè)的合理性得以保障.一個滿足本文假設(shè)的網(wǎng)絡(luò)拓?fù)淙鐖D1所示:
Fig. 1 Network topology.圖1 網(wǎng)絡(luò)拓?fù)?/p>
2 冗余樹算法思想
基于引言對現(xiàn)有保障數(shù)據(jù)無中斷傳輸?shù)娜哂鄻渌惴ǖ姆治?，為了減少主備份傳輸路徑的轉(zhuǎn)發(fā)跳數(shù)，本文不采取先構(gòu)建環(huán)再生成主備份傳輸路徑的方式，而是首先基于Dijkstra算法建立1棵最小傳輸樹作為主傳輸路徑.
定義1. 最小傳輸樹.是網(wǎng)絡(luò)拓?fù)渲?棵以節(jié)點s為根節(jié)點的樹，該樹上根節(jié)點s到其他任意1個節(jié)點x的轉(zhuǎn)發(fā)跳數(shù)是網(wǎng)絡(luò)拓?fù)渲泄?jié)點s到節(jié)點x的所有路徑中轉(zhuǎn)發(fā)跳數(shù)最少的.
在圖1中以節(jié)點A為根節(jié)點的1棵最小傳輸樹如圖2所示:
Fig. 2 The minimal delivery tree.圖2 最小傳輸樹
2.1基于剩余邊排序的選環(huán)
本文以通過向最小傳輸樹上添加剩余邊構(gòu)建冗余環(huán)的方式為最小傳輸樹上節(jié)點尋找轉(zhuǎn)發(fā)跳數(shù)較少的備份路徑.
定義2. 剩余邊.是網(wǎng)絡(luò)拓?fù)渲胁辉谧钚鬏敇渖系倪?
定義3. 冗余環(huán).是基于剩余邊和最小傳輸樹所形成的環(huán)，當(dāng)該環(huán)上有1個節(jié)點或1條邊失效時，環(huán)上其他節(jié)點與最小傳輸樹根節(jié)點之間仍然存在可達(dá)路徑.
結(jié)合圖2所示最小傳輸樹可知，圖1中的邊(B,C)為1條剩余邊，將該剩余邊加入圖2中的最小傳輸樹中，可構(gòu)成環(huán)(A,B,C,A).當(dāng)該環(huán)上任意1個節(jié)點(不包含A)或1條邊失效時，環(huán)上其他節(jié)點仍可以與根節(jié)點A保持連接，因此該環(huán)為冗余環(huán).
然而，需要指出的是，基于不同冗余環(huán)所形成的同一節(jié)點的備份路徑的轉(zhuǎn)發(fā)跳數(shù)是不同的，由圖1和圖2可知，包含根節(jié)點A和節(jié)點G的冗余環(huán)有多個，如(A,F,G,J,C,A)和(A,F,G,H,A)，當(dāng)節(jié)點F失效時，根節(jié)點A到達(dá)節(jié)點G的備份路徑(A,C,J,G)的轉(zhuǎn)發(fā)跳數(shù)為3，另一條備份路徑(A,H,G)的轉(zhuǎn)發(fā)跳數(shù)則為2.因此，為了給最小傳輸樹上的節(jié)點構(gòu)建具有較少轉(zhuǎn)發(fā)跳數(shù)的備份路徑，本文首先對剩余邊按照邊的節(jié)點度進(jìn)行排序，然后再進(jìn)行冗余環(huán)的構(gòu)建.
定義4. 如果剩余邊e的2個頂點分別為x和y，則剩余邊e的節(jié)點度NDe為最小傳輸樹上根節(jié)點s分別到節(jié)點x和節(jié)點y的路徑上所包含的節(jié)點數(shù)量之和.
為了減少備份路徑的轉(zhuǎn)發(fā)跳數(shù)，本文并非隨機(jī)選擇剩余邊和最小傳輸樹構(gòu)建冗余環(huán)，而是先為每一條剩余邊e計算其節(jié)點度NDe，然后根據(jù)節(jié)點度值從小到大對剩余邊進(jìn)行排序，這樣做在減少備份路徑的轉(zhuǎn)發(fā)跳數(shù)的同時也提高了冗余樹抵御多點邊失效的能力.接著，按照從小到大的順序依次將剩余邊添加到最小傳輸樹上構(gòu)建冗余環(huán).然而值得注意的是，剩余邊和最小傳輸樹所形成的環(huán)并非都是冗余環(huán).以圖2為例，將剩余邊(E,I)加入到最小傳輸樹上，可構(gòu)成環(huán)(B,E,I,B)，由于該環(huán)上節(jié)點B為根節(jié)點A到達(dá)節(jié)點E和節(jié)點I必須要經(jīng)過的節(jié)點，一旦節(jié)點B失效，則無路徑可將節(jié)點E和節(jié)點I與節(jié)點A相連，因此根據(jù)定義3可知環(huán)(B,E,I,B)不是冗余環(huán).
定理1. 如果1個基于剩余邊和最小傳輸樹所形成的環(huán)滿足以下條件之一：
1) 該環(huán)包含根節(jié)點；
2) 該環(huán)中至少有2個節(jié)點屬于其他冗余環(huán)；
則該環(huán)是冗余環(huán).
證明. 1)由于該環(huán)包含根節(jié)點，所以從該環(huán)上去掉除根節(jié)點以外的任意1個節(jié)點或1條邊，該環(huán)上剩余節(jié)點仍然可以與根節(jié)點相連通，根據(jù)定義3可知，該環(huán)為冗余環(huán).2)由于該環(huán)中至少有2個節(jié)點屬于其他冗余環(huán)，不失一般性，設(shè)這2個節(jié)點分別為x和y，根據(jù)定義3可知，節(jié)點x和節(jié)點y與根節(jié)點之間一定存在可達(dá)路徑，當(dāng)該環(huán)上1個節(jié)點(包括節(jié)點x和節(jié)點y)失效時，該環(huán)其他節(jié)點至少可以通過節(jié)點x和節(jié)點y中的1個節(jié)點與根節(jié)點相連接，因此該環(huán)是冗余環(huán).
證畢.
根據(jù)定理1，對于由網(wǎng)絡(luò)拓?fù)銰(V,E)生成的最小傳輸樹和剩余邊序列Seq，基于剩余邊排序的冗余環(huán)構(gòu)建方法如下：
1) 初始化，令節(jié)點集合T={s}，其中s為網(wǎng)絡(luò)拓?fù)銰的最小傳輸樹的根節(jié)點，按序?qū)⑹Ｓ噙呅蛄蠸eq中的剩余邊添加到最小傳輸樹上形成相應(yīng)的環(huán)并按序存儲這些環(huán).
2) 讀取序列Seq中排在最前面的剩余邊在最小傳輸樹上形成的環(huán).
3) 如果該環(huán)包含根節(jié)點s或者至少已有2個節(jié)點屬于T，則該環(huán)為冗余環(huán)，將環(huán)上不在T中的節(jié)點添加到T，同時從Seq中刪除該剩余邊；否則，讀取Seq中的下一條剩余邊在最小傳輸樹上形成的環(huán)，返回到步驟3)繼續(xù)執(zhí)行.
4) 如果T=V或者Seq=?，則構(gòu)建冗余環(huán)的過程結(jié)束，否則返回到步驟2)繼續(xù)執(zhí)行.
2.2冗余樹的生成
當(dāng)冗余環(huán)上1個節(jié)點或1條邊失效時，該環(huán)上其他節(jié)點通過剩余邊仍然可達(dá)最小傳輸樹的根節(jié)點.因此，可以將構(gòu)成冗余環(huán)的剩余邊作為冗余枝添加到最小傳輸樹上，從而生成1棵冗余樹.假設(shè)構(gòu)成冗余環(huán)的剩余邊e的2個頂點分別為x和y，那么添加冗余枝的方法如下：
1) 在構(gòu)建冗余環(huán)的過程中，如果構(gòu)成冗余環(huán)的剩余邊e只有1個頂點為根節(jié)點或已經(jīng)屬于其他冗余環(huán)，不失一般性，設(shè)該頂點為x，則將邊(x,y)添加到最小傳輸樹的節(jié)點x上，使得節(jié)點y成為節(jié)點x在冗余樹上的子節(jié)點，從而構(gòu)成根節(jié)點通過節(jié)點x到達(dá)節(jié)點y的備份路徑.而節(jié)點x要么是根節(jié)點，要么屬于其他冗余環(huán)，均已具有根節(jié)點可達(dá)的備份路徑，不需要通過在節(jié)點y上添加冗余枝的方式構(gòu)成根節(jié)點到達(dá)節(jié)點x的備份路徑.
2) 在構(gòu)建冗余環(huán)的過程中，如果構(gòu)成冗余環(huán)的剩余邊e的2個頂點都不是根節(jié)點，也都不屬于其他冗余環(huán)，則在最小傳輸樹的節(jié)點x和節(jié)點y上分別添加邊(x,y)和邊(y,x)，形成2條冗余枝，從而分別構(gòu)成根節(jié)點通過節(jié)點x到達(dá)節(jié)點y的備份路徑和通過節(jié)點y到達(dá)節(jié)點x的備份路徑，最后在1個冗余枝序列中按序?qū)⑸傻娜哂嘀尤?，該序列用于表示冗余枝加入最小傳輸樹的順?
基于上述方法，在選擇冗余環(huán)的過程中不斷添加冗余枝到最小傳輸樹上，直到基于剩余邊排序的選環(huán)過程結(jié)束，最終生成1棵基于最小傳輸樹的冗余樹.以圖1中節(jié)點A作為根節(jié)點所生成的冗余樹如圖3所示(具體生成步驟將作為算法示例在第3節(jié)中給出)，其中實邊表示最小傳輸樹上的邊，虛邊表示冗余枝，虛邊上的標(biāo)號表示冗余枝被添加到最小傳輸樹上的順序，標(biāo)號的目的是為了在根據(jù)冗余樹生成根節(jié)點A到達(dá)其他節(jié)點的備份下一跳路徑時，能夠體現(xiàn)對備份路徑轉(zhuǎn)發(fā)跳數(shù)的優(yōu)化.
Fig. 3 The redundant tree.圖3 冗余樹
根據(jù)帶有冗余枝標(biāo)號的冗余樹，可以生成冗余樹上根節(jié)點到其他節(jié)點的主備份傳輸路徑的路由轉(zhuǎn)發(fā)表.對于根節(jié)點為s的冗余樹，其路由轉(zhuǎn)發(fā)表的具體生成方法為：
1) 在冗余樹中的最小傳輸樹上，對于根節(jié)點s的每一個子節(jié)點，分別遍歷該子節(jié)點的所有子樹，將該子節(jié)點設(shè)為到達(dá)自身及其在最小傳輸樹上所有子孫節(jié)點的主下一跳.
3) 當(dāng)所有冗余枝按照生成順序被遍歷完后，根節(jié)點s的主備傳輸路徑轉(zhuǎn)發(fā)表生成完畢.
根據(jù)上述路由轉(zhuǎn)發(fā)表的生成方法，以圖3為例，節(jié)點A的轉(zhuǎn)發(fā)表如圖4所示.
Fig. 4 The forwarding table of the primarysecondary delivery paths for node A.圖4 節(jié)點A的主備傳輸路徑轉(zhuǎn)發(fā)表
3 算法描述
基于第2節(jié)對冗余樹算法思想的介紹，本節(jié)給出冗余樹構(gòu)建算法的具體描述，并通過示例對算法的執(zhí)行過程進(jìn)行說明.為方便描述算法，設(shè)Ere為剩余邊集合，Seq為剩余邊序列，用T表示參與冗余環(huán)構(gòu)建的節(jié)點集合，對于網(wǎng)絡(luò)拓?fù)銰(V,E)，以s∈V為根節(jié)點的冗余樹的構(gòu)建算法如算法1所示：
算法1. 冗余樹構(gòu)建算法.
輸入：G(V,E),s,Ere,Seq,T;
輸出：冗余樹.
①T={s},Ere={},Seq=[];
② 根據(jù)G(V,E)和根節(jié)點s使用Dijkstra算法構(gòu)建最小傳輸樹Tr(V,Emin);
(2)真空低溫烹飪。將腌制好的雞翅放入真空包裝袋，進(jìn)行真空包裝，放在烤架上，再放入烤箱中間層，選擇蒸汽低溫烹調(diào)模式，調(diào)節(jié)溫度、時間，然后開始低溫烹飪。
③Ere=E-Emin;
④ for eache∈Eredo
⑤ 計算邊e的節(jié)點度NDe;
⑥ 按照節(jié)點度值從小到大的順序?qū)⑦卐插入到Seq中;
⑦ end for
⑧ 按序?qū)eq中的邊加入到Tr中構(gòu)成相應(yīng)的環(huán)R(Vring)，并按序存儲這些環(huán);
⑨i=0;*標(biāo)記冗余枝的添加順序*
⑩ while (T≠V) do
下面對構(gòu)建冗余樹算法的時間復(fù)雜度進(jìn)行分析：設(shè)網(wǎng)絡(luò)拓?fù)渲泄?jié)點數(shù)量為n，邊的數(shù)量為m，剩余邊數(shù)量為k(k 1) 針對網(wǎng)絡(luò)拓?fù)涫褂肈ijkstra算法生成最小傳輸樹，所需時間復(fù)雜度為O(n2)； 2) 計算1條剩余邊的節(jié)點度所需時間復(fù)雜度為O(logn)，故總的計算節(jié)點度的時間復(fù)雜度為O(klogn)，對剩余邊基于節(jié)點度由小到大進(jìn)行排序，所需時間復(fù)雜度為O(k2)，可知該部分所需時間復(fù)雜度為O(klogn+k2)； 3) 為每條剩余邊在最小傳輸樹上構(gòu)建相應(yīng)的環(huán)，每次構(gòu)環(huán)的最壞時間復(fù)雜度為O(logn)，因此總的構(gòu)環(huán)時間復(fù)雜度為O(klogn)； 4) 在隨后的冗余樹生成過程中，在最壞情況下每遍歷1次剩余邊序列只有1個節(jié)點加入節(jié)點集合T，由于節(jié)點集合T初始包含根節(jié)點且第1個形成的冗余環(huán)至少包含3個節(jié)點(其中1個是根節(jié)點)，可知最多要遍歷n-2次剩余邊序列，因此冗余樹生成部分的最壞時間復(fù)雜度為O(kn). 綜上所述，整個構(gòu)建冗余樹算法的時間復(fù)雜度為O(n2+k2+klogn+kn).作為比較，MFBG算法[13]與G-MFBG算法[18]的時間復(fù)雜度分別為O(n2(m+n))和O(n2(m+nlogn)).相比其他算法，本文算法在提升主傳輸路徑以及備份傳輸路徑性能的同時還降低了算法時間復(fù)雜度. 下面以圖1所示網(wǎng)絡(luò)拓?fù)錇槔?，說明構(gòu)建以A為根節(jié)點的冗余樹的具體過程： 1) 基于Dijkstra算法生成以A為根節(jié)點的最小傳輸樹，如圖2所示，并對冗余環(huán)節(jié)點集合T賦初值T={A}. 2) 根據(jù)圖1和圖2，將剩余邊按照邊的節(jié)點度進(jìn)行排序，得到的剩余邊序列RS如表1所示.隨后，按序?qū)⑹Ｓ噙吿砑拥阶钚鬏敇渖闲纬上鄳?yīng)的環(huán). Table 1 The Sorting Table of Redundant Edge Fig. 5 Selecting (B,C).圖5 選取(B,C) 3) 讀取剩余邊序列中的第1條邊(B,C)在最小傳輸樹上形成的環(huán)(A,B,C,A)，如圖5(a)所示.由于該環(huán)包含根節(jié)點A，可知該環(huán)為冗余環(huán).由于邊(B,C) 上的2個端點都不屬于T，即節(jié)點B和節(jié)點C都不屬于其他冗余環(huán)，因此分別向最小傳輸樹上的節(jié)點B和節(jié)點C添加冗余枝(B,C)和(C,B)，并都標(biāo)上序號1，生成的冗余樹如圖5(b)所示.隨后將環(huán)(A,B,C,A)上不在T中的節(jié)點B和C加入到T中得到更新后的T={A,B,C}，并將邊(B,C)從剩余邊序列中刪除，更新后的剩余邊序列如圖5(c)所示. 4) 讀取更新后的剩余邊序列中的第1條邊(F,C)在最小傳輸樹上形成的環(huán)(A,F,C,A)，如圖6(a)所示.由于該環(huán)包含根節(jié)點A，可知該環(huán)為冗余環(huán).由于邊(F,C)上端點C已經(jīng)屬于T，即節(jié)點C已屬于其他冗余環(huán)，因此只需向最小傳輸樹上的節(jié)點C添加冗余枝(C,F)并標(biāo)上序號2即可，生成的冗余樹如圖6(b)所示.隨后將環(huán)(A,F,C,A)上不在T中的節(jié)點F加入到T中得到更新后的T={A,B,C,F}，并將邊(F,C)從剩余邊序列中刪除，更新后的剩余邊序列如圖6(c)所示. Fig. 6 Selecting (F,C).圖6 選取(F,C) Fig. 7 Selecting (H,F).圖7 選取(H,F) 5) 讀取更新后的剩余邊序列中的第1條邊(H,F)在最小傳輸樹上形成的環(huán)(A,H,F,A)，如圖7(a)所示.由于該環(huán)包含根節(jié)點A，可知該環(huán)為冗余環(huán).由于邊(H,F)上端點F已經(jīng)屬于T，即節(jié)點F已屬于其他冗余環(huán)，因此只需向最小傳輸樹上的節(jié)點F添加冗余枝(F,H)并標(biāo)上序號3即可，生成的冗余樹如圖7(b)所示.隨后將環(huán)(A,H,F,A)上不在T中的節(jié)點H加入到T中得到更新后的T={A,B,C,F,H}，并將邊(H,F)從剩余邊序列中刪除，更新后的剩余邊序列如圖7(c)所示. 6) 讀取更新后的剩余邊序列中的第1條邊(B,J)在最小傳輸樹上形成的環(huán)(A,B,J,C,A)，如圖8(a)所示.由于該環(huán)包含根節(jié)點A，可知該環(huán)為冗余環(huán).由于邊(B,J)上端點B已經(jīng)屬于T，即節(jié)點B已屬于其他冗余環(huán)，因此只需向最小傳輸樹上的節(jié)點B添加冗余枝(B,J)并標(biāo)上序號4即可，生成的冗余樹如圖8(b)所示.隨后將環(huán)(A,B,J,C,A)上不在T中的節(jié)點J加入到T中得到更新后的T={A,B,C,F,H,J}，并將邊(B,J)從剩余邊序列中刪除，更新后的剩余邊序列如圖8(c)所示. Fig. 8 Selecting (B,J).圖8 選取(B,J) Fig. 9 Selecting (H,G).圖9 選取(H,G) 7) 讀取更新后的剩余邊序列中的第1條邊(H,G)在最小傳輸樹上形成的環(huán)(A,H,G,F,A)，如圖9(a)所示.由于該環(huán)包含根節(jié)點A，可知該環(huán)為冗余環(huán).由于邊(H,G)上端點H已經(jīng)屬于T，即節(jié)點H已屬于其他冗余環(huán)，因此只需向最小傳輸樹上的節(jié)點H添加冗余枝(H,G)并標(biāo)上序號4即可，生成的冗余樹如圖9(b)所示.隨后將環(huán)(A,H,G,F,A)上不在T中的節(jié)點G加入到T中得到更新后的T={A,B,C,F,H,J,G}，并將邊(H,G)從剩余邊序列中刪除，更新后的剩余邊序列如圖9(c)所示. 8) 讀取更新后的剩余邊序列中的第1條邊(E,I)在最小傳輸樹上形成的環(huán)(B,E,I,B)，如圖10(a)所示.由于該環(huán)上只有1個節(jié)點B屬于T且不包含根節(jié)點A，可知該環(huán)不是冗余環(huán)，則將邊(E,I)擱置，保持冗余樹、集合T和剩余邊序列均不變，如圖10(b)(c)所示. 9) 由于邊(E,I)在最小傳輸樹上形成的環(huán)不是冗余環(huán)，則讀取剩余邊序列中的下一條邊(G,J)與最小傳輸樹所形成的環(huán)(A,F,G,J,C,A)，如圖11(a)所示.由于該環(huán)包含根節(jié)點A，可知該環(huán)為冗余環(huán)，然而由于該環(huán)上所有節(jié)點都已經(jīng)屬于T，說明環(huán)上除根節(jié)點A之外的所有節(jié)點都已存在與根節(jié)點A相通的備份路徑，則保持冗余樹和集合T不變，如圖11(b)所示，只需將邊(G,J)從剩余邊序列中刪除即可，更新后的剩余邊序列如圖11(c)所示. Fig. 11 Selecting (G,J).圖11 選取(G,J) 10) 由于邊(G,J)在最小傳輸樹上形成的環(huán)是冗余環(huán)，需要讀取更新后的剩余邊序列中的第1條邊(E,I)與最小傳輸樹所形成的環(huán)(B,E,I,B)，如圖12(a)所示.由于該環(huán)上仍然只有1個節(jié)點B屬于T且不包含根節(jié)點A，可知該環(huán)不是冗余環(huán)，則繼續(xù)將邊(E,I)擱置，保持冗余樹、集合T和剩余邊序列均不變，如圖12(b)(c)所示. Fig. 12 Selecting (E,I).圖12 選取(E,I) 11) 由于邊(E,I)在最小傳輸樹上形成的環(huán)不是冗余環(huán)，則讀取剩余邊序列中的下一條邊(D,E)與最小傳輸樹所形成的環(huán)(A,C,J,D,E,B,A)，如圖13(a)所示.由于該環(huán)包含根節(jié)點A，可知該環(huán)為冗余環(huán).由于邊(D,E)上的2個節(jié)點都不屬于T，即節(jié)點D和節(jié)點E都不屬于其他冗余環(huán)，因此分別向最小傳輸樹上的節(jié)點D和節(jié)點E添加冗余枝(D,E)和(E,D)，并都標(biāo)上序號6，生成的冗余樹如圖13(b)所示.隨后將環(huán)(A,C,J,D,E,B,A)上不在T中的節(jié)點D和節(jié)點E加入到T中得到更新后的T={A,B,C,F,H,J,G,D,E}，并將邊(D,E)從剩余邊序列中刪除，更新后的剩余邊序列如圖13(c)所示. Fig. 13 Selecting (D,E).圖13 選取(D,E) 12) 讀取更新后的剩余邊序列中的第1條邊(E,I)在最小傳輸樹上形成的環(huán)(B,E,I,B)，如圖14(a)所示.由于此時該環(huán)上的節(jié)點B和E均已經(jīng)加入T，因此該環(huán)上已經(jīng)有2個節(jié)點屬于T，可知該環(huán)為冗余環(huán).由于邊(E,I)上端點E已經(jīng)屬于T，即節(jié)點E已屬于其他冗余環(huán)，因此只需向最小傳輸樹上的節(jié)點E添加冗余枝(E,I)并標(biāo)上序號7即可，生成的冗余樹如圖14(b)所示.隨后將環(huán)(B,E,I,B)上不在T中的節(jié)點I加入到T中得到更新后的T={A,B,C,F,H,J,G,D,E,I}，并將邊(E,I)從剩余邊序列中刪除，更新后的剩余邊序列如圖14(c)所示.由于此時有T=V，冗余樹構(gòu)建結(jié)束，此時所構(gòu)建的冗余樹即為最終的冗余樹，與圖3所示冗余樹完全相同. Fig. 14 Selecting (E,I).圖14 選取(E,I) 為了驗證本文提出的CSES算法的效能，使用NS2構(gòu)建網(wǎng)絡(luò)仿真環(huán)境，使用Java作為開發(fā)工具.首先，為與其他冗余樹算法進(jìn)行公平的比較，仿真所需的部分拓?fù)鋮⒄瘴墨I(xiàn)[18]所提出的拓?fù)湟?guī)模并由拓?fù)渖善鰾RITE生成，節(jié)點規(guī)模分別是50,100,200節(jié)點，邊的規(guī)模分別為3n和nlbn，其中n為節(jié)點數(shù).因此可生成6種不同規(guī)模的拓?fù)?，可用?jié)點數(shù)×邊數(shù)的形式表示，即拓?fù)?為50×150，拓?fù)?為50×250，拓?fù)?為100×300，拓?fù)?為100×600，拓?fù)?為200×600，拓?fù)?為200×1400.其次，為驗證本文算法在數(shù)據(jù)中心網(wǎng)絡(luò)拓?fù)渲械挠行裕勒瘴墨I(xiàn)[5]中所展示的基于Fat-tree的數(shù)據(jù)中心網(wǎng)絡(luò)拓?fù)錁?gòu)建仿真網(wǎng)絡(luò)拓?fù)洌⒁罁?jù)該拓?fù)鋵Ρ缺疚呐c其他冗余樹算法的效能. 實驗1. 比較不同規(guī)模拓?fù)湎禄贑SES算法、MFBG算法、G-MFBG算法所生成的主傳輸路徑的轉(zhuǎn)發(fā)跳數(shù). 首先，分別在6種不同拓?fù)渲须S機(jī)選擇1個節(jié)點為數(shù)據(jù)源節(jié)點，使用CSES，MFBG，G-MFBG算法生成傳輸樹；然后計算傳輸樹上根結(jié)點到達(dá)其他節(jié)點的轉(zhuǎn)發(fā)跳數(shù)的平均值，對上述實驗重復(fù)50次，結(jié)果取平均值.如圖15所示，基于CSES算法的傳輸樹具有最小的平均轉(zhuǎn)發(fā)跳數(shù);由于MFBG算法在構(gòu)建傳輸樹時沒有考慮到傳輸路徑的轉(zhuǎn)發(fā)跳數(shù)，隨機(jī)選環(huán)策略導(dǎo)致平均轉(zhuǎn)發(fā)跳數(shù)較大.盡管G-MFBG算法考慮到路徑性能，但是其所得平均轉(zhuǎn)發(fā)跳數(shù)高于CSES算法所得平均轉(zhuǎn)發(fā)跳數(shù)，這是因為CSES算法生成的路徑具有最小轉(zhuǎn)發(fā)跳數(shù). Fig. 15 The comparison of the average forwarding hop count of the primary path.圖15 主傳輸路徑平均轉(zhuǎn)發(fā)跳數(shù)比較 實驗2. 比較不同規(guī)模拓?fù)湎禄贑SES算法、 MFBG算法、G-MFBG算法所生成的備份路徑的轉(zhuǎn)發(fā)跳數(shù). 首先，比較單邊失效后不同算法產(chǎn)生的備份路徑的平均轉(zhuǎn)發(fā)跳數(shù)，對3種算法隨機(jī)選擇相同的1條邊令其失效，仿真結(jié)果如圖16(a)所示.CSES算法所得備份路徑的平均轉(zhuǎn)發(fā)跳數(shù)最少，這是因為該算法采取了基于剩余邊節(jié)點度排序的選環(huán)方法，從而減少了備份路徑的平均轉(zhuǎn)發(fā)跳數(shù).對于G-MFBG算法，由于其對備份路徑的轉(zhuǎn)發(fā)跳數(shù)沒有考慮，故該算法產(chǎn)生的備份路徑的平均轉(zhuǎn)發(fā)跳數(shù)較多.其次，比較單節(jié)點失效后不同算法產(chǎn)生的備份路徑的平均路由，仍然對3種算法隨機(jī)選擇相同的1個節(jié)點(非根節(jié)點)令其失效，仿真結(jié)果如圖16(b)所示.盡管相比單邊失效情況下CSES算法所得備份路徑的平均轉(zhuǎn)發(fā)跳數(shù)有所增加，但是CSES算法所得備份路徑的平均轉(zhuǎn)發(fā)跳數(shù)仍然是最少的，這仍然是因為CSES算法為了降低備份路徑的轉(zhuǎn)發(fā)跳數(shù)對剩余邊按節(jié)點度值進(jìn)行了排序. Fig. 16 The comparison of the average forwarding hop count of the secondary path in the case of single edgenode failure.圖16 單邊點失效時備份路徑平均轉(zhuǎn)發(fā)跳數(shù)比較 實驗3. 驗證在相同拓?fù)湟?guī)模和不同節(jié)點失效比例下，基于CSES算法、MFBG算法、G-MFBG算法所生成的冗余樹抵御多節(jié)點失效的能力. 為方便比較，使用在啟用備份路徑后尚能與根節(jié)點保持連接的節(jié)點數(shù)目與總節(jié)點數(shù)目的比例(簡稱連接節(jié)點比例)作為度量指標(biāo).首先，針對50×150，100×300，200×600這3種拓?fù)浞謩e設(shè)置5%～50%的節(jié)點失效率(增長幅度為5%)，并通過遍歷啟用相應(yīng)冗余枝后的冗余樹來計算連接節(jié)點比例，分別重復(fù)計算50次，最終將所有結(jié)果取平均值，實驗結(jié)果如圖17所示.在不同的拓?fù)渲?，MFBG算法抵御多節(jié)點失效的能力最差，而CSES算法抵御多節(jié)點失效能力最好，這是因為CSES算法使用節(jié)點度值對剩余邊進(jìn)行排序，從而可生成更多的冗余枝用于構(gòu)建備份路徑. Fig. 17 The comparison of the resistant ability in the case of multiple nodes failure.圖17 不同節(jié)點失效比例下抵御多節(jié)點失效能力 實驗4. 驗證在相同拓?fù)湟?guī)模和不同邊失效比例下，基于CSES算法、MFBG算法、G-MFBG算法所生成的冗余樹抵御多邊失效的能力. 與實驗3同樣使用節(jié)點連接比例作為度量指標(biāo)，針對50×150，100×300，200×600這3種拓?fù)浞謩e設(shè)置5%～50%的邊失效率(增長幅度為5%)并計算連接節(jié)點比例，分別重復(fù)計算50次，最終將所有結(jié)果取平均值，實驗結(jié)果如圖18所示.在不同的拓?fù)渲?，相比于多?jié)點失效情況，多邊失效情況下各個算法所得出的連接節(jié)點比例有所提高，其中，本文CSES算法依舊保持最高的連接節(jié)點比例，MFBG算法的抵御多邊失效能力最差. Fig. 18 The comparison of the resistant ability in the case of the multiple edges failure.圖18 不同邊失效比例下抵御多邊失效能力 實驗5. 在基于Fat-tree的數(shù)據(jù)中心網(wǎng)絡(luò)拓?fù)湎买炞CCSES算法、MFBG算法、G-MFBG算法的效能. 依照文獻(xiàn)[5]中所展示的基于Fat-tree的數(shù)據(jù)中心網(wǎng)絡(luò)拓?fù)渌鶚?gòu)建仿真網(wǎng)絡(luò)拓?fù)淙鐖D19所示. Fig. 19 The Fat-tree based network topology in data center.圖19 基于Fat-tree的數(shù)據(jù)中心網(wǎng)絡(luò)拓?fù)?/p> 1) 隨機(jī)選擇1個邊界層交換機(jī)作為數(shù)據(jù)源節(jié)點，使用CSES，MFBG，G-MFBG算法生成傳輸樹，然后計算傳輸樹上根結(jié)點到達(dá)其他節(jié)點(邊界層交換機(jī))的轉(zhuǎn)發(fā)跳數(shù)的平均值，對上述實驗重復(fù)50次，結(jié)果取平均值，實驗結(jié)果如圖20所示，基于CSES算法的傳輸樹具有最小的平均轉(zhuǎn)發(fā)跳數(shù). 2) 比較單邊失效后不同算法產(chǎn)生的備份路徑的平均轉(zhuǎn)發(fā)跳數(shù)，對3種算法隨機(jī)選擇拓?fù)渲邢嗤?條邊令其失效，仿真結(jié)果如圖20所示，CSES算法所得備份路徑的平均轉(zhuǎn)發(fā)跳數(shù)最少. Fig. 20 The comparison of the average forwarding hop count of the primarysecondary path.圖20 主備份傳輸路徑的平均轉(zhuǎn)發(fā)跳數(shù)比較 3) 比較單節(jié)點失效后不同算法產(chǎn)生的備份路徑的平均路由，在3種算法中隨機(jī)選擇相同的1個節(jié)點(非根節(jié)點)令其失效，仿真結(jié)果如圖20所示，盡管相比單邊失效情況下CSES算法所得備份路徑的平均轉(zhuǎn)發(fā)跳數(shù)有所增加，但是CSES算法所得備份路徑的平均轉(zhuǎn)發(fā)跳數(shù)仍然是最少的，這是因為CSES算法為了降低備份路徑的轉(zhuǎn)發(fā)跳數(shù)對剩余邊按節(jié)點度值進(jìn)行了排序. Fig. 21 The comparison of the resistant ability in the case of multiple nodesedges failure.圖21 不同節(jié)點失效比例下抵御多節(jié)點邊失效能力比較 本文提出一種可保障數(shù)據(jù)無中斷傳輸?shù)陌催呅蜻x環(huán)的冗余樹算法.該算法首先基于網(wǎng)絡(luò)拓?fù)錁?gòu)建最小傳輸樹，該樹上根節(jié)點與其他節(jié)點之間的轉(zhuǎn)發(fā)跳數(shù)是最少的.隨后，為減少備份路徑的轉(zhuǎn)發(fā)跳數(shù)，本文對剩余邊按節(jié)點度從小到大進(jìn)行排序，依次將剩余邊添加到最小傳輸樹上構(gòu)建冗余環(huán)，并將冗余環(huán)上的冗余枝添加到最小傳輸樹上，最終構(gòu)建一棵冗余樹.實驗結(jié)果表明，相比于其他冗余樹算法，基于本文算法構(gòu)建的冗余樹所生成的主備份路徑的轉(zhuǎn)發(fā)跳數(shù)更少且抵御多節(jié)點邊失效能力更強(qiáng). [1]Yi Xiaomeng, Liu Fangming, Liu Jiangchuan, et al. Building a network highway for big data: Architecture and challenges[J]. IEEE Networking, 2014, 3(4): 1-25[2]Li Dan, Chen Guihai, Ren Fengyuan, et al. Data center network research progress and trends[J]. Chinese Journal of Computers, 2014, 37(2): 259-274 (in Chinese)(李丹, 陳貴海, 任豐原, 等. 數(shù)據(jù)中心網(wǎng)絡(luò)的研究進(jìn)展與趨勢[J]. 計算機(jī)學(xué)報, 2014, 37(2): 259-274)[3]Greenberg A, Hamilton J R, Jain N, et al. VL2: A scalable and flexible data center network[C]Proc of the ACM SIGCOMM’09. New York: ACM, 2009: 51-62[4]Niranjan M R, Pamboris A, Farrington N, et al. Portland: A scalable fault-tolerant layer 2 data center network fabric[C]Proc of the ACM SIGCOMM’09. New York: ACM, 2009: 39-50[5]Al-Fares M, Loukissas A, Vahdat A. A scalable, commodity data center network architecture[C]Proc of the ACM SIGCOMM’08. New York: ACM, 2008: 63-74[6]Costa P, Donnelly A, Rowstron A, et al. Camdoop: Exploiting in-network aggregation for big data applications[C]Proc of the 9th USENIX Conf on Networked Systems Design and Implementation. Berkeley, CA: USENIX Association, 2012: 51-75[7]Xiao Bailong, Guo Wei, Liu Jun, et al. Research on local route repair algorithm in mobile ad hoc networks[J]. Journal of Computer Research and Development, 2007, 44(8): 1383-1389 (in Chinese)(肖百龍, 郭偉, 劉軍，等. 移動自組網(wǎng)路由局部修復(fù)算法的研究[J]. 計算機(jī)研究與發(fā)展, 2007, 44(8): 1383-1389)[8]Zhang Li, Li Jinbao. Multi-Path based reliable routing in wireless sensor network[J]. Journal of Computer Research and Development, 2011, 48(Suppl 2): 171-175 (in Chinese)(張莉, 李金寶. 無線傳感器網(wǎng)絡(luò)中基于多路徑的可靠路由協(xié)議研[J]. 計算機(jī)研究與發(fā)展, 2011, 48(增刊2): 171-175)[9]Challal Y, Ouadjaout A, Lasla N, et al. Secure and efficient disjoint multipath construction for fault tolerant routing in wireless sensor networks[J]. Journal of Network and Computer Applications, 2011, 34(4): 1380-1397[10]Xu M, Hou M, Wang D, et al. An efficient critical protection scheme for intra-domain routing using link characteristics[J]. Computer Networks, 2013, 57(1): 117-133[11]Suchara M, Xu D, Doverspike R, et al. Network architecture for joint failure recovery and traffic engineering[C]Proc of the ACM Sigmetrics (SIGMETRICS’11). New York: ACM, 2011: 97-108[12]Su Jinshu, Hu Qiaolin, Zhao Baokang. Disruption-free forwarding survivable routing protocols on Internet[J]. Journal of Software, 2010, 21(7): 1589-1604 (in Chinese)(蘇金樹, 胡喬林, 趙寶康. 互聯(lián)網(wǎng)無中斷轉(zhuǎn)發(fā)的生存性路由協(xié)議[J]. 軟件學(xué)報, 2010, 21(7): 1589-1604)[13]Médard M, Finn S G, Barry R A, et al. Redundant trees for preplanned recovery in arbitrary vertex redundant or edge redundant graphs[J]. IEEEACM Trans on Networking, 1999, 7(5): 641-652[14]Aun H, Richard H. Recovery techniques in next generation networks[J]. IEEE Communications Surveys & Tutorials, 2007, 9(3): 2-17[15]Jayavelu G, Ramasubramanian S, Younis O. Maintaining colored trees for disjoint multipath routing under node failures[J]. IEEEACM Trans on Networking, 2009, 17(1): 346-359[16]Cho S, Elhourani T, Ramasubramanian S. Independent directed acyclic graphs for resilient multipath routing[J]. IEEEACM Trans on Networking, 2012, 20(1): 153-162[17]Yong O L, Narasimha R. Constructing disjoint paths for failure recovery and multipath routing[J]. Computer Networks, 2012, 56(2): 719-730[18]Xue G, Chen L, Thulasiraman K. Quality-of-service and quality-of-protection issues in preplanned recovery schemes using redundant trees[J]. Journal on Selected Areas in Communications, 2003, 21(8): 1332-1345[19]Wu K, Xiao J, Ni L M. Rethinking the architecture design of data center networks[J]. Frontiers of Computer Science, 2012, 6(5): 596-603[20]Rojas E, Ibanez G, Gimenez-Guzman J M, et al. All-Path bridging: Path exploration protocols for data center and campus networks[J]. Computer Networks, 2015,79(14): 120-132 Xia Nu, born in 1981. PhD candidate. His main research interests include network management. Li Wei, born in 1978. Associate professor and master supervisor. Member of China Computer Federation. His main research interests include next generation network architecture and service computing. Lu You, born in 1977. PhD candidate. Member of China Computer Federation. His main research interests include network management. Jiang Jian, born in 1986. PhD candidate. His main research interests include network management. Shan Feng, born in 1985. PhD candidate. His main research interests include wireless sensor network and algorithm design. Luo Junzhou, born in 1960. Professor and PhD supervisor. Senior member of China Computer Federation. His main research interests include next generation network architecture, protocol engineering, network security, wireless network and cloud computing. The Redundant Tree Algorithm for Uninterrupted Data Delivery Xia Nu, Li Wei, Lu You, Jiang Jian, Shan Feng, and Luo Junzhou (SchoolofComputerScience&Engineering,SoutheastUniversity,Nanjing211189) With the development of the big data applications, the requirement for guaranteeing un-interrupted data delivery is growing gradually. To address the problem of single nodelink failure, researchers had conducted lots of work. However, current methods for guaranteeing uninterrupted data delivery face the deficiencies of low performance of the primarysecondary delivery paths and the low resistant ability to the multiple nodeslinks failure. In order to solve the above problems, a circle selecting by edge sorting based redundant tree algorithm for uninterrupted data delivery CSES is presented. At first, a minimal delivery tree with the data source as the root node is built in this algorithm, on which the routing hop count of the primary paths is the smallest. Secondly, in order to reduce the hop count of the secondary paths and to enhance the resistant ability of the multiple nodesedges failure, the edges in network topology but not included in the tree are sorted based on the sum of the nodes on the paths between the root node and the two nodes of the edge. Then, the edges are added to the minimal tree to form the redundant circles and the redundant branches of the redundant circles are added to the minimal tree. Finally, a redundant tree rooted by the data source is built. The experimental results show that, compared with the other redundant tree algorithms, the hop count of the primarysecondary paths on the redundant tree built by CSES algorithm is smaller and the resistant ability of multiple nodesedges failure of CSES algorithm is better. the uninterrupted data delivery; the minimal delivery tree; edge sorting; the redundant circle; the redundant tree 2015-05-21； 2015-10-29 國家自然科學(xué)基金項目(61320106007)；國家“八六三”高技術(shù)研究發(fā)展計劃基金項目(2013AA013503)；江蘇省未來網(wǎng)絡(luò)創(chuàng)新研究院未來網(wǎng)絡(luò)前瞻性研究項目(BY2013095-2-07)；教育部計算機(jī)網(wǎng)絡(luò)與信息集成重點實驗室(東南大學(xué))基金項目(93K-9)；江蘇省網(wǎng)絡(luò)與信息安全重點實驗室基金項目(BM2003201)；無線通信技術(shù)協(xié)同創(chuàng)新中心資助項目；軟件新技術(shù)與產(chǎn)業(yè)化協(xié)同創(chuàng)新中心部分資助項目；住建部科研項目(2015-K6-012) This work was supported by the National Natural Science Foundation of China (61320106007), the National High Technology Research and Development Program of China (863 Program) (2013AA013503), the Prospective Research Project on Future Networks of Jiangsu Future Networks Innovation Institute (BY2013095-2-07), the Project Funded by Key Laboratory of Computer Network and Information Integration (Southeast University) of Ministry of Education of China (93K-9), the Project Funded by Jiangsu Provincial Key Laboratory of Network and Information Security (BM2003201), the Project Funded by Collaborative Innovation Center of Wireless Communication Technology, the Project Funded by Collaborative Innovation Center of Novel Software Technology and Industrialization, and the Project Funded by Ministry of Housing and Urban-Rural Development (2015-K6-012). TP3914 實 驗
5 結(jié)束語
