以无尺度网路绕径演算法提升企业资料安全性

1、以無尺度網路繞徑演算法提昇企業資料安全性王淑卿 朝陽科技大學資訊管理系嚴國慶 朝陽科技大學企業管理系郭敏士 朝陽科技大學資訊管理系摘 要分散式系統容錯能力的提升是達到系統可靠使用之主要因子之一，然而過去分散式容錯系統大多採用資料複製的方式來達成，但因接受複製與計算的資料需透過網路中繼節點傳送至目的地端，因此在網路中以正確的節點進行資訊傳遞一直是值得關切的議題，此問題之解決稱之為繞徑演算法。然而，以往有關容錯繞徑演算法的研究多是在隨機網路(Exponential Networks)下進行討論，但現今已有許多學者證實了無尺度網路(Scale Free Networks)的架構確有存在的必要性，但以

2、往並沒有有關無尺度網路容錯繞境演算法之研究。因此，本研究提出在KE無尺度網路下之繞徑演算法，利用規則性編號規則給予網路上每一節點編號，並以XOR方式判別訊息存在節點與目的地節點之差距，做訊息傳遞的依據，以達成分散式系統在無尺度網路連結下之容錯能力。關鍵字：容錯、隨機網路、無尺度網路、繞徑演算法1. 前言由於分散式系統有賴在異地的處理資源協助計算，然而卻可能因為少數節點的損壞，而造成整個計算結果產生錯誤，因此在分散式系統中容錯的能力十分地重要。現今企業與組織大多以資料複製或節點繞徑方式達成系統環境的容錯目的1,8,9,10，其中又以資料複製的方法最為目前企業與組織所青睞，資料複製的方法不但簡單易

3、執行並具有計算機資源的調配能力，利用遠端擁有相同複製資料的電腦協助計算減少整體計算的時間，且可同時做為異地備份之基礎，但網路中如有錯誤節點產生時，雖然資料複製的方式可以做為資料備援的機制，但網路中正常節點的資訊仍有賴剩餘的節點做傳輸的中繼，因此光是消極的做資料備份對於整體分散式系統的容錯能力仍稍嫌不足。由於在有線網路環境中，電腦處理單元所連結的網路線路都是固定的，而過去有關固定連結方式的繞徑演算法(Routing Algorithm)都是在以超立方體(Hypercube)或是網狀(Mesh)連結的多處理系統環境中探討，但這兩種網路模型與現在分散式系統網路模型大相逕庭。近期更有學者證實無尺度網路

4、(Scale Free Networks)節點的連結方式存在多數分散式系統中，而由於以往未曾有相關的研究探討在無尺度網路中如何以繞徑的方式達成分散式系統的容錯能力。本研究有鑑於此，提出一容錯繞徑演算法利用規則性編號規則給予網路上每一節點編號，並以XOR方式判別訊息存在節點與目的地節點之差距，做訊息傳遞的依據，使得KE無尺度網路(KE Scale Free Network)可利用此繞徑演算法提升無尺度網路容錯能力。在第二章回顧過去容錯演算法的作法，第三章為本研究基本架構及符號定義，第四章說明本研究所提出之無尺度網路容錯繞徑演算法，第五章總結本研究演算法並針對後續研究提出建議。2. 文獻探討由多數

5、社交網路、商業環境與網路架構的行為交織而成的網路為無尺度網路，如：網際網路、全球資訊網www、等等6,10。而無尺度網路為分散式架構的一種連結方式，無尺度網路最大的優點為對於節點意外的損壞具有極大的容忍能力6，且在無尺度網路中訊息的散播十分快速，更不受傳播最低門檻值所限制5。在分散式系統中，網路的架構直接影響網路中資訊傳播的效能與網路安全的穩定性1,2,6,7，而為解決這類系統安全的問題，所設計相關演算法與網路架構稱之為系統容錯。在分散式系統中，容錯能力的提升一直是被熱烈討論的議題之一。而達到容錯的方式大多以資料複製的方式來達成，如在P2P的分散式架構中利用資料複製使末端使用者存取的成功率提升

6、，當重複的資料越多越能容忍越多的節點損壞1,8,10，亦即容錯能力是藉由資料複製來達成，此種方法是目前在實現分散式系統容錯能力中廣泛被利用的方法之一7。但只以資料複製的方式達成容錯需要額外大量的儲存空間，將使得企業或組織儲存成本提高。但，因為子系統群組7,12計算出的結果需透過網路上沒有發生錯誤的節點進行傳遞，因此僅利用資料複製的技術並不能做為分散式系統容錯的保證。為解決此問題，有學者在固定模型下提出容錯的繞徑演算法以達到分散式系統之容錯，如在固定連結之網狀網路中的容錯繞境演算法9，與在超立方體模型中之容錯繞境演算法9。不管如何，這些研究的成果9皆假設網路是屬於隨機網路的連結方式3，因此並不適

7、用於目前現存的網際網路或全球資訊網www，亦即無法適用於無尺度網路的連結方式，因此在本研究中將探討在一無尺度分散式網路中以繞徑演算法達成其容錯能力。3. 研究架構與假設本研究是以無尺度網路為基礎，進行容錯繞徑演算法之探討，而無尺度網路大致上可分為二類：(1)BA無尺度網路(BA Scale Free Network)與(2)KE無尺度網路(KE Scale Free Network)6,11。其中KE無尺度網路具叢集特性較為接近現行分散式網路環境架構，因此可利用遞迴的方式產生KE無尺度網路，並給予網路中每一個節點唯一的編號，做為本研究之基礎架構。3.1. 利用遞迴關係產生無尺度網路無尺度網路為

8、由多數低分支度節點與少數高分支度節點組成集合的網路拓樸，節點的分支度分配會遵循公式(1)之冪次定律(Power Law)3,4,6,11，Klemm與Eguiluz兩位學利用這樣的理論基礎，加入叢集的概念使得更符合現實分散式架構具有叢集的特性，稱之為KE無尺度網路，KE無尺度網路之產生詳見圖一所示之演算法。KE無尺度網路利用遞迴的關係不斷產生新的節點(如圖二步驟2之節點2與節點3)，再由新節點產生更新的節點群組，如圖二之步驟三所示，並由新群組的末端節點連結回初始節點，如圖二步驟二之節點2與節點3連結回初始節點，因此越是新產生的群組之末端節點會有越多的連結，但初始節點會以指數成長擁有更多的連結6

9、。P(k)K-公式(1)因此，KE無尺度網路擁有群組的概念且符合冪次定律；亦由於KE無尺度網路較具節點連結規則，因此本研究採用此KE無尺度網路模型作為本研究的基礎。Algorithm KESFN. TO Generate KE Scale Free Network(SFN) 1. generate R = root_node /* 產生一初始節點 2. generate R = 3R /* 複製相同節點 3. let new R_leafe_node connect to root_node /* 新產生的未端節點連結至初始節點 4. if node < expect nodes num

10、ber /* 5. then GOTO 2 /* 6. end /* 圖一 無尺度網路產生演算法3.2. 對無尺度網路中各節點進行編號在本研究中，對網路中的每一節點給予一特定編號做為訊息傳遞的依據，並假設網路上所有節點損壞情形是穩定的。換言之，在訊息傳遞的過程中不會有新節點或是新連結發生損壞。本研究將每個節點N以三位數字(X,Y,Z)做為網路節點編號，令X為群組(代表九個節點之群組)編號，如圖二步驟3之群組，Y為次群組(代表三節點之群組)編號，如圖二步驟2之群組，Z表末端節點之歪斜方向(1表左斜，2表右斜)，如圖二所示。再者，將網路中群組最上方節點如(XOO_g)可同時代表一個九個節點之群組，

11、(XY0_g)可代表網路中一三個節點之群組。假設網路中(000_g)與(100_g)群組中(010)、(102)、(111)、(112)及(122)為損壞節點，此時若節點(100)要傳送訊息至初始節點(000)底下的(012)節點(D: Destination)，對於路徑上非S(Source)、D(Destination)之節點均稱為中繼節點，對(100)為起始節點(S: Source)而言，有四個末端節點與其相連，必需選擇該群組之一末端節點將訊息傳遞至初始節點(000)，但由於其中三個中繼節點損壞，以致無其它路徑可供選擇，傳送訊息至(000_g)群組；而又因為(010)為損壞節點因此亦無法透

12、過此節點再傳遞給(012)。所以，此時其繞徑路徑為(100)à(121)à(000)à(012)。而對於每一中繼節點而言，訊息交換至該節點時，此節點稱之為訊息中繼節點(C: Current Node)。再者，假設網路中每一節點皆擁有整個網路之連結之資訊(Global Information)，因此在KE無尺度網路上，任何訊息的傳遞均需透過(X00_g)群組裡之末端節點才可達成傳送訊息至另一(X00_g)目的地，如(100)à(121)à(000)，在繞徑的必經節點中若存在損壞節點稱此節點為不安全節點(Unsafe)，並將不安全節點再分為二類：(

13、1)對(100)節點而言，四個路徑中有三個損壞的中繼節點，這類節點稱之為極不安全節點(Strongly Unsafe)；(2)對於(200)而言，有一個以上損壞的中繼節點，稱之為一般程度不安全節點(Ordinarily Unsafe)。4. 研究步驟實施方法過去有許多學者在不同固定連接式的網路環境中，對容錯繞徑演算法(Fault Tolerant Routing Algorithm)提出諸多方法，如超立方體與網狀網路中9。但所提出的這些容錯繞徑演算法，對於現今分散式系統所採用的無尺度網路架構則不適用，因此本章所提出之繞徑演算法將利用節點不同的連結屬性，如極不安全節點與一般程度不安全節點，將訊息

14、傳送利用互斥或(XOR)方式找到可行路徑，並可適用於KE無尺度網路。步驟1步驟2步驟3步驟4圖二 KE無尺度網路編號4.1. 固定網路拓撲繞徑演算法本研究以圖二之KE無尺度網路模型做為繞徑演算法的基礎架構，並假設網路上每個節點皆擁有整個網路中所有節點的狀態(Global Information)。而以往在固定網路拓撲之繞徑演算法，大多僅考慮在超立方體或是網狀連結的網路中9，本研究所提出的演算法可適用於KE無尺度網路架構中，本研究所使用之符號如表1所示。4.2. 適當的繞徑演算法本研究提出無尺度網路容錯繞徑演算法，假設網路中每一節點已知全域資訊(Global Information)狀態，因此當

15、訊息所在節點C是(X00)群組下的節點(如(X01)、(X02)且不在目的地節點，則會先傳給(X00)再由其傳送訊息出去；若C是屬於極度不安全節點(Strongly Unsafe Node)，則表示該節點之下一個中繼節點(Next Hop)只有唯一路徑可以做資訊傳遞；當C是屬於一般程度不安全節點(Ordinarily Unsafe Node)或是安全節點(Safe Node)，則會有二個以上的中繼節點可供選擇，因此本演算法透過呼叫Location()選取一可行路徑，當有多個可行路徑時，則可任意選擇一個可行的路徑傳遞給下一訊息中繼節點。表1 本研究所用符號表符號定義符號定義Root_nodeKE

16、無尺度網路初始節點Leaf_nodeKE無尺度網路末端節點S訊息來源節點(Source Node) D訊息目的地節點(Destination Node)C目前訊息所在節點(Current Node)N網路節點之編號，由XYZ三個數字所代表(X00_g)所有節點編號首位為同一數字所成的群組集合節點(D_X00_g)目的地節點所在的(X00)群組編號互斥或(exclusive or)Location()採用的方法，首先利用互斥或(XOR)比對現存節點C與目的地節點D的位址狀態，倘若比對結果為X=0，則表示兩位址是在(X00_g)的群組之中；如果為1，則將訊息透過(X00_g)底下末端節點(XYZ，

17、X,Y,Z不為0)傳到D所在的(X00_g)，再做Y的互斥或比較。如果Y=0，則表示訊息在(XY0_g)的群組中；若不是，也將訊息傳送到(X00_g)底下末端節點做訊息傳遞之節點中繼，一直重覆此步驟則可將訊息C繞送到目的地節點D，詳細演算法如圖三所示。4.3. 容錯演算法之優劣比較容錯演算法在固定連接式的網路環境中大都在網路模型為網狀連結(如圖四所示)與超立方體連結(如圖五所示)方式下進行討論。網狀連結模型的優點是單純，但可以容錯的數量卻有相當的限制，如在i維度的網狀網路環境中，最多容許任意損壞(i-1)個節點損壞9。因此，在三個維度中，一個有八個節點的網狀網路環境，最多僅能容許任意二個節點損

18、壞，此時目的地端才可以順利利用剩餘的節點繞徑而達成容錯能力。而在超立方體連節狀態下，可容許最多錯誤節點為 én/2ù 9。在九個節點之KE無尺度網路中，若S=(X0Z)，而(X00)不為損壞節點欲繞徑至其它(X00_g)群組，則最少可容許任意三個節點損壞(九節點之Leaf-node)，最多可容忍七個節點的損壞(如：(X00)à(XYZ)，X00為S，XYZ為D)。比較不同網路架構繞徑之最短距離可發現由於網狀連結，在同樣是九個節點連結而成的網路架構中，若S=(1,1)，D=(1,3)而(1,2)與(2,2)為損壞節點，則其繞徑路徑為(1,1) à (2,1

19、) à (3,1) à (3,2) à (3,3) à (2,3) à (1,3)。而在超立方體中，J.D. Shih學者9證明繞徑距離在超立方體模型中不會超過(最短路徑距離+)。而在KE無尺度網路模型(X00)等級中，如果訊息可以從S順利到D，則在最差情況下，距離為4。除此外，在KE無尺度網路下，更會因節點數的增加使得繞徑距離縮短。不同網路架構之容錯個數與繞徑距離如表2所示。Algorithm FTKESFN. Fault-Tolerant Routing for KE Scale Free Network 1. begin 2. if N=

20、 destination then route message successful; 3. else if S=(X0Z) then 4. Forward the message to (X00); 5. else do while C not D 6. select case 1: C is a strongly unsafe node then 7. Forward the message via the only survive leaf_node; 8. select case 2: C is a ordinarily unsafe or safe node then 9. Forw

21、ard the message call Location();10. loop11. endFunction Location()1. begin2. let C D 3. if X=0 , check C at (D_XY0_g)4. if Y=0 , check C at the (D_XYZ_g)5. if Z=0 , route successes 6. else route message to D7. end if8. else route message to (0Y0_g)9. else route message to (X00_g)10. end圖三 無尺度網路容錯繞徑演

22、算法1,12,11,2圖四 網狀網路架構圖圖五 超立方體網路架構圖表2 不同網路架構比較表假設模型連結方式容錯個數繞徑距離整體表現超立方體(Hypercube)隨機連結0.250.5最短路徑+劣網狀(Mesh)隨機連結(i-1)3()+k中等KE無尺度網路(KE SF Network)無尺度網路0.3330.778(n為節點個數)優良5. 結論與未來研究方向分散式系統的容錯常有賴資料複製與訊息傳播繞徑的方式來達成，然而只依賴資料複製來達成分散式系統的容錯，其成本往往過高，且經過分散式計算的結果最終還是需要利用網路上剩存的節點協助繞徑。而以往容錯繞徑演算法都是在以超立方體或是網狀架構為基礎的隨機

23、網路上討論，但現今無尺度網路已被多數學者證實存在現實的分散式網路環境中。無尺度網路節點與分支度分佈的連結方式，最大優勢在於當承受意外損壞時具有極為強韌的特性，訊息在該網路中仍可利用僅存的節點進行訊息交換，而達成容錯的目的。因此，本研究利用KE無尺度網路的架構提出適當的演算法，藉由繞徑演算法達成分散式系統的容錯。但在本研究KE無尺度網路容錯繞徑演算法中，對於損壞節點的下一訊息傳遞之中繼節點並未探討負載平衡(Load Balance)的問題，因此未來研究將以此做為本演算法改善之依據，並藉由模擬實驗來證實此演算法之可行性。6.參考文獻1 K. Aberer and M. Punceva, “Impr

24、oving Data Access in P2P Systems,” IEEE Internet Computing, 2002, pp. 58-67.2 D. Anderson, “Providing Fault Tolerance in Distributed Systems,” Proceedings of the Computer Science Discipline Seminar Conference (CSCI 3901), 2000.3 A.L. Barabasi, R. Albert, H. Jeong, “Scale-Free Characteristics of Rand

25、om Networks: the Topology of the World Wide Web,” Physica A 272, 1999, pp. 173-187.4 A.L. Barabasi, E. Ravasz and T. Vicsek, “Deterministic Scale-Free Networks,” Physica A 299, 2001, pp. 559-564.5 A. Cherif and T. Katayama, “Replica Management for Fault-Tolerant Systems,” Micro, IEEE, vol. 18, Issue 5, 1998, pp. 54-65.6 V.M. Eguiluz and K. Klemm, “Epidemic Threshold in Structured Scale-Free Networks,” Physical Review Letters, 89(10), 2002, 108701.7 M.R. Neiforoshan, “Fault Tolerant Computing in Computer Design,” The Journal of Computing in Small Colleges, vol. 18, Issue 4, 20