基於莫比烏斯立方體網絡構建數據中心網絡容錯的方法與流程
2023-10-28 07:06:07
本發明涉及基於莫比烏斯立方體網絡構建數據中心網絡容錯的方法，屬於計算機與數學交叉技術領域。
背景技術：
作為雲計算的基礎設施和下一代網絡技術的創新平臺，數據中心網絡的研究成為了近年來學術界和工業界關注的熱點。數據中心網絡拓撲結構本質上是網絡互連結構的一種應用實例，其作為雲計算和數據密集型計算的底層基礎設施，必須向上層應用提供高效可靠的網絡通信服務，是重要的信息支撐平臺，對我國軍事、金融、電信等核心領域的信息化發展具有舉足輕重的作用。數據中心網絡的性能在很大程度上決定雲計算的性能。由於數據中心網絡存在大量的交換機和伺服器以及鏈路，發生故障的情形是很難避免的。容錯性確保數據中心網絡中某些資源(伺服器、交換機或鏈路)發生故障時，正在執行的各種任務(如信息處理或者算法)能正常運行。因此研究網絡的抗容錯性能具有重大的實際意義。
在數據中心網絡中，由於組成設備多、鏈路連接複雜、網絡規模較大，因此單設備或單條鏈路故障發生的頻次比普通的網絡要多，是否具有較好的容錯性是評價數據中心很重要的標準。根據目前的研究發展現狀來看，適用於數據中心網絡的網絡結構大體分為三種類型：以交換機為中心的網絡，以伺服器為中心的網絡和不規則的網絡。隨著數據中心的不斷發展，傳統的數據中心網絡，即樹形結構、Fat-tree網絡結構等，逐漸暴露出越來越多的缺陷和不足。如樹形結構一般包含兩至三層的網絡設備，分別為核心層，聚合層和邊緣層。其中伺服器與底層的邊緣層交換機連接，邊緣層交換機與聚合層路由器連接，聚合層路由器再與核心層路由設備連接。如果聚合層網絡設備出現故障，將會導致失效設備的下層結點與其他結點失去連接，因此這種結構存在明顯的單點失效問題，網絡容錯性較差。Fat-tree網絡結構在聚合層引入大量的冗餘交換機，因此經濟性問題並沒有得到很好地解決。
技術實現要素：
為了克服上述的不足，滿足數據中心新的設計要求，提高數據中心網絡的可擴展性、可靠性等拓撲性能，本發明提供了一種數據中心網絡結構容錯的方法。採用莫比烏斯立方體網絡MQn構建高效、容錯、可擴展的數據中心網絡。它是遞歸結構形式，而且具有在節點規模、路徑長度和容錯性上的良好性質。
本發明的技術方案：
一種基於莫比烏斯立方體網絡構建數據中心網絡容錯的方法，步驟如下：
(1)當莫比烏斯立方體網絡MQn中錯誤的邊|Fe|和錯誤的點|Fv|的個數之和|Fv|+|Fe|≤n-2時，對於莫比烏斯立方體網絡的維數n≥5，MQn中的任意一個正確邊e都存在長為2n-2-2≤l≤2n-|Fv|的圈包含邊e。判斷莫比烏斯立方體網絡MQn中是否存在長為2n-2-2≤l≤2n-|Fv|的圈的算法，包括以下三個部分：
(a)MQn的構造：根據MQn的定義，生成MQn的關聯矩陣代碼，將MQn中每個頂點和頂點間的鄰接關係保存在關聯矩陣(Incidence_matrix)中；
(b)生成錯誤集，在關聯矩陣中剔除錯誤集；首先對MQn中所有邊和點進行標號，然後生成所有可能的錯誤子集；如6條邊中錯2條邊的所有可能錯誤子集是{1,2}{1,3}{1,4}{1,5}{1,6}{2,3}{2,4}，{2,5}{2,6}{3,4}{3,5}{3,6}{4,5}{4,6}{5,6}。
(c)將關聯矩陣中錯誤子集剔除，剩餘部分即為子矩陣；對於子矩陣進行深度優先遍歷，尋找所需要的路徑即判斷子矩陣中是否存在指定長度的圈，並記錄一個符合條件的圈。
(2)判斷莫比烏斯立方體網絡MQn中是否存在指定長Len(Len＝l)的圈的原則：
1)令邊e的一個端點為路徑起點(Vbegin)及另一個端點為路徑終點(Vend)。將Vbegin和Vend放入搜索路徑(path)中去，標記路徑起點Vbegin已經訪問，路徑終點Vend先不標記訪問。
2)將路徑起點Vbegin作為當前訪問節點Current_Vertex，即Current_Ver＝Vbegin，開始進行深度優先遍歷；同時標記當前點為已經訪問節點，保證回溯時能回到正確的位置。
3)尋找當前訪問節點Current_Vertex的(下一個)沒訪問的鄰接點Vertex，將節點Vertex加入到搜索路徑path中去，路徑長度PathLen加1；
如果當前訪問節點Current_Vertex的所有鄰接點Vertex都被訪問過且PathLen<Len-1，則做如下回溯操作：
visited[Current_Vertex]＝false；//標記當前節點沒有訪問過；
PathLen--；//當前路徑長度減1；
Current_Vertex＝path[PathLen-1]；//將路徑中的上一個節點作為當前節點；
Start[Current_Vertex]++；//當前節點從下一個節點開始訪問；
回溯結束後以新的當前訪問節點Current_Vertex開始新的訪問。
若直到路徑起點Vbegin所有的鄰接點都訪問過，還未找到PathLen＝Len-1，則表示沒有相應的圈。
4)將當前訪問節點Current_Vertex的鄰接點Vertex作為當前訪問節點Current_Vertex，即Current_Vertex＝vertex，並標記為已訪問節點，重複步驟3)；
當路徑長度PathLen＝Len-1時，判斷當前訪問節點Current_Vertex的鄰接節點Vertex中是否有路徑終點Vend。
如果當前訪問節點Current_Vertex的鄰接節點Vertex中沒有路徑終點Vend，則將當前節點Current_Vertex標記為未訪問節點，並將路徑中上一個節點標記為當前節點Current_Vertex，路徑長度PathLen減1，回溯到步驟3)；
如果當前訪問節點Current_Vertex的鄰接節點Vertex中有路徑終點Vend，則該圈就是要找的圈。
本發明的有益效果：本發明研究了莫比烏斯立方體網絡MQn的容錯性，即當一個大型網絡(可建模為莫比烏斯立方體網絡MQn)在運行時出現各種問題時，它的容錯能力是n-2。即當網絡中出現n-2個錯誤時，仍能保證系統的剩餘部分能夠正常運行，提高了系統的容錯能力。
具體實施方式
以下結合技術方案，進一步說明本發明的具體實施方式。
(Ⅰ)0-MQ5關聯矩陣的構造如下所示的0-MQ5關聯矩陣。
(Ⅱ)生成錯誤集。此時，錯誤的是點1,2,3，在關聯矩陣中剔除錯誤集後，0-MQ5的關聯矩陣如下所示的剔除錯誤集後的0-MQ5的關聯矩陣：
(Ⅲ)對於剩餘子圖進行深度優先遍歷(按照剔除錯誤集後的0-MQ5的關聯矩陣)，對邊4-8尋找長為6的圈，即尋找4-8長為5的路徑。
(1)令Vbegin為點4和Vend為點8。將Vbegin和Vend放入搜索路徑(path)中去，路徑終點Vend先標記訪問。
(2)將路徑起點4作為當前訪問節點Current_Vertex，開始進行深度優先遍歷。同時標記當前點4為已經訪問節點，保證回溯時能回到正確的位置。
(3)尋找當前訪問節點Current_Vertex(點4)的沒訪問的鄰接點Vertex(點12)，此時path中的路徑長度pathLen為1。
(4)將Vertex(點12)放入路徑path中，並標記Vertex已訪問，然後將Vertex標記為當前訪問節點Current_Vertex，回到(3)繼續訪問。
(3)尋找當前訪問節點Current_Vertex(點12)的沒訪問的鄰接點Vertex(點10)，將Vertex(點10)放入路徑path中，此時path中的路徑長度pathLen為2。
(4)將Vertex標記為當前訪問節點Current_Vertex，並標記為已訪問節點，回到(3)繼續訪問。
(3)尋找當前訪問節點Current_Vertex(點10)的沒訪問的鄰接點Vertex(點9)，將Vertex(點9)放入路徑path中，此時path中的路徑長度pathLen為3。
(4)將Vertex標記為當前訪問節點Current_Vertex，並標記為已訪問節點，回到(3)繼續訪問。
(3)尋找當前訪問節點Current_Vertex(點9)的沒訪問的鄰接點Vertex(點11)，將Vertex(點11)放入路徑path中，此時path中的路徑長度pathLen為4。
(4)此時長度為Len-1，但點11不是點8的鄰接點，標記點9為當前訪問節點Current_Vertex，此時path中的路徑長度pathLen為3，回溯到步驟(3)。
(3)尋找當前訪問節點Current_Vertex(點9)的下一個沒訪問的鄰接點Vertex(點16)，將Vertex(點16)放入路徑path中，此時path中的路徑長度pathLen為4。
(4)此時pathLen長度為Len-1，但點10不是點30的鄰接點，標記點8為當前訪問節點Current_Vertex，此時path中的路徑長度pathLen為4，回溯到步驟(3)。
(4)此時長度為Len-1，且點8是點16的鄰接點，則包含邊4-8長度為6的圈已找到。
最後得到剩餘子矩陣中，包含邊4-8長為6的圈有4，12，10，9，16，8。按照以上步驟，可以得出MQ5中的任意一個正確邊e，都存在長為6的圈包含這個正確邊。即當交叉立方體網絡MQ5中錯誤的邊(|Fe|)和錯誤的點(|Fv|)的個數之和即|Fv|+|Fe|≤n-2＝3時，MQ5中的任意一個正確邊e，都存在長為l(l＝6)的圈包含邊e。接下來，用數學歸納法可以得出當交叉立方體網絡MQn中錯誤的邊(|Fe|)和錯誤的點(|Fv|)的個數之和即|Fv|+|Fe|≤n-2時，對於n≥3(n為交叉立方體網絡MQn的維數)，MQn中的任意一個正確邊e，都存在長為2n-2-2≤l≤2n-|Fv|的圈包含邊e。