基於快速切換的覆蓋網絡故障檢測與恢復方法

2023-07-09 18:48:46 2

專利名稱：基於快速切換的覆蓋網絡故障檢測與恢復方法
技術領域：
基於快速切換的覆蓋網絡故障檢測與恢復方法屬於網絡數據傳輸技術領域。
背景技術：
通過在用戶節點上運行相應的軟體並進行配置，覆蓋網絡就能夠為Internet用戶提供高可擴展性的大規模分布式應用，這成為推動覆蓋網絡廣泛應用的主要因素。在當前的研究中，一般將重點集中在如何選擇一條低延遲或高帶寬的覆蓋網絡路徑以提高網絡性能。其中包括覆蓋網絡單播的路徑選擇，基於測量的端系統組播協議等。但是，當前大部分的研究都隱含地假設覆蓋網絡應用是獨立的，沒有考慮各個應用之間因獨立管理資源和擁塞控制而導致的流量抖動和網絡性能的下降。同時，由於在Internet上搭建的覆蓋網絡網絡鏈路延遲較大，覆蓋網絡應用的流量僅是網絡中總流量的一小部分，所以每個覆蓋網絡應用依據感知到的網絡狀態進行路徑選擇，無法保證提高整個網絡的性能。
同時由於覆蓋網絡是由穩定程度相對較低的用戶主機構成，並且由於沒有集中控制節點，主要的故障最終都歸結為節點失效，失效的原因可能是該用戶退出網絡或是相關網路中的路由錯誤等。在傳統的協議設計中，發現節點失效的方法通常比較簡單，如在發起通信時檢測，或採用定時握手的機制，但是由於網絡規模的不斷變大，這種方式的效率和自調節性都受到了極大的挑戰，同時網絡中查找的成功率也將由於故障的不斷變多而急劇下降。
本文提出了一種基於快速切換的覆蓋網絡故障檢測與恢復方法，該方法通過一系列節點之間的通訊與計算規則，量化了探測報文的發送頻率並提出了結合出錯概率與最大可用帶寬的代理節點選擇與恢復方法，在提高了使覆蓋網絡的可靠性與服務的穩定性的同時大大提高了覆蓋網絡中資源查找的成功率。

發明內容
本發明的目的在於提供一種基於快速切換的覆蓋網絡故障檢測與恢復方法。
本發明的特徵在於，它依次含有以下步驟步驟(1.)用戶終端開啟後初始化鄰居狀態表，其中包括鄰居序號，IP位址，故障判定次數，超時時間，以及標誌位，其中，鄰居序號用來標記所有鄰居和個數，其範圍為1到65535，IP位址用來唯一的標記該鄰居，故障判定次數表示連續丟失多少個探測報文才能判斷該節點失效，超時時間為判斷該次探測失敗的時間長度，標誌位為1位10進位數，其中0表示該記錄對應的鄰居為該子網的代理節點，1表示該記錄對應的鄰居為該子網的備份代理節點，2代表記錄對應的鄰居為一般普通節點；步驟(2.)初始化鄰居維護表，其包括鄰居IP位址，鄰居保活發送頻率，其中IP位址用來唯一的標記該鄰居，鄰居保活發送頻率為用於確認該鄰居存活而發送的探測報文的發送頻率；步驟(3.)當某個用戶終端加入P2P網絡以後，首先連接所述子網中的代理節點並獲取鄰居信息，同時將所述鄰居信息寫入鄰居狀態表；步驟(4.)掃描鄰居狀態表，對於每個鄰居，令α表示其故障判定次數，T為超時時間，ρ為控制負載佔總帶寬的百分比，在默認狀態下ρ取0.01，K為該鄰居的保活發送頻率，n為鄰居個數，K為鄰居的保活發送頻率單位為個每秒；並使用公式K＝2α/n+αρn+T計算K，計算完畢以後將該值寫入鄰居維護表的對應位置，並按照該頻率發送探測報文；步驟(5.)如果在探測過程中，發現某鄰居沒有回覆探測報文，則進一步判斷該節點的故障判定次數是否等於1，如果不為1，則並將故障判斷次數減1，如果為1則將改鄰居標記為失效；步驟(6.)如果所述某節點發現失效鄰居在節點鄰居狀態表中的標誌位為0，則說明該子網代理發生故障，所述節點將向鄰居狀態表中的標誌位為1的鄰居發送通告報文，讓其代替原代理節點進行工作，同時將鄰居狀態表中該備用代理的標誌位設為0；並依次按照以下步驟選擇下一個備份代理節點步驟(6.1)掃描鄰居狀態表，得到表中鄰居條目下的故障判定次數為q，最大可用帶寬為b，其中b為用戶的網絡接入帶寬與當前已使用帶寬之差，並使用G＝q*b計算所有鄰居的優先級G，並將具有最大優先級的節點IP位址廣播出去，作為自己向所有鄰居節點推薦的新備份代理節點；步驟(6.2)對收到的IP位址進行記數，並設擁有最多推薦者數量的鄰居節點的鄰居為新的份代理節點，同時在鄰居狀態表中的標誌位中標記為1；步驟(7)按照新的鄰居狀態表重新整理鄰居維護表，同時刪除已經失效的鄰居節點。
為了驗證該機制的有效性，我們使用了基於事件驅動的模擬器來進行該機制的評價與實驗工作，實驗結果顯示該發明在網絡出現高錯誤(錯誤率大於20％的情況下)能夠在隊列處理長度很小，也就是負載較輕的情況下獲得50％以上的查找成功率，具體實驗數據見圖3與圖4。


圖1.本發明的總體流程；圖2.備份代理節點選擇流程；圖3.覆蓋網絡查找成功率實驗數據表；圖4.節點負載分布情況實驗數據圖；圖5.本發明的應用示例圖。
具體實施例方式
本發明實現了一種針對原有覆蓋網絡維護與故障檢測方法的改進，使其具備了更強的穩定性並為數據查找提供了更加可靠的網絡保障。
本發明的總體流程圖見圖1.
用戶節點通過對鄰居狀態表的掃描計算不同鄰居的維護開銷以及探測報文的發送頻率，並且，該頻率的大小同時間接反映了所述鄰居節點的穩定情況，在該發送頻率下，用戶節點將動態的根據該節點的歷史失效信息按照圖1的過程動態的改變對該鄰居的維護策略。
同時，當某用戶節點發現網絡中代理節點失效以後，將比較快速的將所有數據傳輸的任務轉交給新的代理節點，並同時按照圖2的過程選擇新的備份代理節點。
備份代理節點選擇流程圖見圖2.
在該機制設計完畢後我們使用VC7實現了基於事件驅動的模擬器，來進行該機制的實驗和評價工作。
使用本方法後覆蓋網絡查找成功率實驗數據表見圖3.
圖3顯示了不同節點故障概率和恢復概率對精確路由查找成功率的影響，同時我們發現隨著節點故障率的增大，對單一副本的查找成功率將大幅度下降。同時如果節點能夠被快速恢復，將明顯提高查找成功率。根據實驗我們可知，查找不成功是因為目標節點故障、查詢在故障節點被丟棄、無效路由等原因造成的，同時發現在使用本機制情況下網絡的查找成功率是令人滿意的使用本方法後節點負載分布情況實驗數據圖見圖4.
從圖4中發現網絡中代理節點的負載較一般節點的負載重很多，我們在選擇代理節點時需要充分考慮到節點的性能。另外，網絡中節點的動態性不會對增加節點的負載。
本發明的應用示例圖見圖5.
通過對該機制的實驗評價我們發現，該機制能夠在覆蓋網絡中增強網絡的穩定性，並在此基礎上提高網絡中資源查找的成功率。
由此可見，本發明達到了預期目的。
權利要求
1.基於快速切換的覆蓋網絡故障檢測與恢復方法，其特徵在於，所述方法依次含有以下步驟步驟(1.)用戶終端開啟後初始化鄰居狀態表，其中包括鄰居序號，IP位址，故障判定次數，超時時間，以及標誌位，其中，鄰居序號用來標記所有鄰居和個數，其範圍為1到65535，IP位址用來唯一的標記該鄰居，故障判定次數表示連續丟失多少個探測報文才能判斷該節點失效，超時時間為判斷該次探測失敗的時間長度，標誌位為1位10進位數，其中0表示該記錄對應的鄰居為該子網的代理節點，1表示該記錄對應的鄰居為該子網的備份代理節點，2代表記錄對應的鄰居為一般普通節點；步驟(2.)初始化鄰居維護表，其包括鄰居IP位址，鄰居保活發送頻率，其中IP位址用來唯一的標記該鄰居，鄰居保活發送頻率為用於確認該鄰居存活而發送的探測報文的發送頻率；步驟(3.)當某個用戶終端加入P2P網絡以後，首先連接所述子網中的代理節點並獲取鄰居信息，同時將所述鄰居信息寫入鄰居狀態表；步驟(4.)掃描鄰居狀態表，對於每個鄰居，令α表示其故障判定次數，T為超時時間，ρ為控制負載佔總帶寬的百分比，在默認狀態下ρ取0.01，K為該鄰居的保活發送頻率，n為鄰居個數，K為鄰居的保活發送頻率單位為個每秒；並使用公式K＝2α/n+αρn+T計算K，計算完畢以後將該值寫入鄰居維護表的對應位置，並按照該頻率發送探測報文；步驟(5.)如果在探測過程中，發現某鄰居沒有回覆探測報文，則進一步判斷該節點的故障判定次數是否等於1，如果不為1，則並將故障判斷次數減1，如果為1則將改鄰居標記為失效；步驟(6.)如果所述某節點發現失效鄰居在節點鄰居狀態表中的標誌位為0，則說明該子網代理發生故障，所述節點將向鄰居狀態表中的標誌位為1的鄰居發送通告報文，讓其代替原代理節點進行工作，同時將鄰居狀態表中該備用代理的標誌位設為0；並依次按照以下步驟選擇下一個備份代理節點步驟(6.1)掃描鄰居狀態表，得到表中鄰居條目下的故障判定次數為q，最大可用帶寬為b，其中b為用戶的網絡接入帶寬與當前已使用帶寬之差，並使用G＝q*b計算所有鄰居的優先級G，並將具有最大優先級的節點IP位址廣播出去，作為自己向所有鄰居節點推薦的新備份代理節點；步驟(6.2)對收到的IP位址進行記數，並設擁有最多推薦者數量的鄰居節點的鄰居為新的份代理節點，同時在鄰居狀態表中的標誌位中標記為1；步驟(7)按照新的鄰居狀態表重新整理鄰居維護表，同時刪除已經失效的鄰居節點。
全文摘要
基於快速切換的覆蓋網絡故障檢測與恢復方法屬於網絡數據傳輸技術領域，其特徵在於，在用戶節點建立一個包括用於表示連續丟失多少個探測報文才能確定蓋節點失效得故障判定數，以及表示該節點代理身份得標誌位在內的鄰居狀態表，用來計算針對所有鄰居的探測報文發送頻率，並建立一個包括該鄰居所發送保活報文個數以及發送頻率的鄰居維護表，如果在規定的故障判定次數內沒有回應探測報文則將該鄰居刪除，如果被刪除的鄰居為該區域的代理節點，則進行快速切換和備份節點的選舉，以確保在最短時間內保證網絡服務的連續性。本發明同時能夠在保證覆蓋網絡可靠性的基礎上提高覆蓋網絡搜索的成功率。
文檔編號H04L12/24GK101094119SQ200710119539
公開日2007年12月26日 申請日期2007年7月26日 優先權日2007年7月26日
發明者徐恪, 劉惠山, 王海洋 申請人:清華大學