一種隨機化的路由方法
2023-05-03 13:46:16 2
專利名稱：一種隨機化的路由方法
技術領域：
本發明涉及數據通信領域，具體地說，涉及一種IP網絡中消息傳輸的路由方法。
目前IP網絡中路由器選擇鏈路傳輸的方法主要有兩種距離矢量(Distance Vector，簡稱DV)方法和鏈路狀態(Link State，簡稱LS)方法。在1997年清華大學出版的Computer Networks 3rded.和1998年IEEE NetworkWorking Group的OSPF Version 2中介紹了這兩種方法，其基本思路是首先通過在各路由結點之間傳遞控制報文，獲得本結點到自治系統中其他各結點的全局最短路徑樹，然後每個結點基於局域最優的思想，為自己所處理的報文儘可能地選擇某種距離測度下的最優路由(即最短路徑)，這裡距離測度通常包括鏈路帶寬、傳輸延遲、緩存長度等性能指標。這兩種方法的區別在於獲得全局最短路徑樹的方法不同DV方法是直接利用各相鄰結點的全局最短路徑樹獲得本結點的全局最短路徑樹，而LS方法的全局最短路徑樹是通過本結點的計算獲得。
如果網絡帶寬總是充分的，那麼局域最優能夠近似對應於全局最優，但是由於網絡業務量具有無特徵尺度的突發性，帶寬資源經常可能處於相對稀缺的臨界狀態，在這種情況下，基於局域最優思想的路由器傳輸方法會產生一個嚴重的問題路由振蕩。
下面根據
圖1來說明採用確定性局域最優路由方法導致路由振蕩的過程。圖1中，左、右兩個子網通過鏈路a、b連接，在路由表更新周期t內，如果鏈路a由於突發性的業務流而發生擁塞，則左子網中的路由結點A將根據局域最優路由方法選擇c-b鏈路作為到右子網的報文在下一周期t+1內的路由。出於同樣的理由，路由結點B也會選擇b鏈路作為周期t+1內的到右部子網的路由。這樣會導致在周期t+1內，左右子網之間的通信全部集中在鏈路b上，而又由於清空傳輸緩存所需的時間通常遠小於路由表更新周期，因此鏈路a在周期t+1內基本上處於空閒狀態。而在周期t+2內，情況發生了反轉，c-a鏈路將可能被局域最優的路由方法一致地判定為最優路徑，從而導致鏈路b空閒，鏈路a擁塞。如此循環往復，在沒有外生擾動的情況下，這種路由振蕩過程將穩定地持續下去。
由於確定性方法一般不可能精確地建模真實系統的全部動態特徵，因此一旦真實系統的狀態偏離了該方法的先驗假設，那麼該方法可能會導致一個不可接受的下優性能，而某些下優性能所對應的系統狀態可能是相對穩定的，這樣的話，該確定性方法將較長時間地被吸引在下優性能上，比如產生路由振蕩。
本發明的目的在於提供一種隨機化的路由方法，以克服現有局域最優路由方法所產生的路由振蕩問題，提高帶寬的利用率。
本發明通過在現有局域最優路由方法中引入隨機化機制來實現隨機化的路由方法，具體包括以下步驟一、擴展路由器的路由表，並為各結點初始化概率Popt(S)；二、新的路由表周期開始，路由結點根據基本LS方法或DV方法獲得本結點到系統內其他所有結點的全局最短路徑樹；三、路由結點通過直接計算或網絡通信獲得與其相鄰的各結點的全局最短路徑樹；四、路由結點建構本結點到自治系統內所有其他結點的隨機路由集；五、判斷當前是否有需要處理的報文，若有，則進入步驟六；若無，則等待；六、判斷當前需處理報文是否具有優先級；若報文具有優先級，則轉步驟八；七、若報文不具有優先級，則所述路由結點以概率Popt(S)按局域最優路由方法獲得的最優路由發送流經它的報文，以概率1-Popt(S)按隨機路由集發送流經它的報文；然後轉步驟十一；
八、判斷高優先級報文在所有報文中出現的概率Ph是否大於概率Popt(S)，若概率Ph不大於概率Popt(S)，則轉步驟十；九、若概率Ph大於概率Popt(S)，則高優先級報文以概率 按最優路由發送，以概率 按隨機路由集發送；低優先級報文均以概率1按隨機路由集發送；然後轉步驟十一；十、高優先級報文以概率1按最優路由發送；低優先級報文以概率 按最優路由發送，以概率 按隨機路由集發送；十一、判斷路由表更新周期是否結束，若是，則轉步驟二；若否，則轉步驟五。
本發明所述隨機化的路由方法還可以是自適應的，其特徵在於在路由表更新周期結束時，根據公式(4)動態調整概率Popt(S)的值Popt(t+1)(S)=B{Popt(t)(S)-T[Popt(t)(S)]N[D(t+1)(S)]},>0---(4).]]>所述步驟四中，路由結點依據公式(1)建立隨機路由集C(S，D)≡{Bi|Lopt(S，D)≤l(s，Bi)+Lopt(Bi，D)，Lopt(S，D)＞Lopt(Bi，D)}-{Bopt(S，D)(1)其約束條件為(Lopt(S，D)≤l(s，Bi)+Lopt(Bi，D))Λ(Lopt(S，D)＞Lopt(Bi，D)) (2)。
所述步驟四也可以是在一個由報文頭包含的新的源-目地址對首次出現時計算該源-目地址對的隨機路由集，並存儲應用於整個路由周期。
所述按隨機路由集發送報文還進一步包括1)確定隨機路由集內的路由結點被選為報文路由的後驗概率；2)生成隨機數；3)選擇隨機發送路徑發送報文。
下面根據附圖進一步詳細說明本發明。
圖1是說明產生路由振蕩的網絡示意圖。
圖2是本發明所述隨機化的路由方法(基於LS方法)的流程圖。
圖3是本發明所述自適應隨機化的路由方法(基於LS方法)的流程圖。
圖4是應用本發明所述隨機化路由方法對於非突發性業務源，概率Popt與跨子網報文平均傳輸延遲之間的關係示意圖。
圖5是應用本發明所述隨機化路由方法對於突發性業務源，概率Popt與跨子網報文平均傳輸延遲之間的關係。
圖1所示的關於路由振蕩產生的原理，已在前文中詳細描述，這裡不再贅述。
圖2給出了隨機化路由方法的基本流程。本發明的核心在於在現有局域最優化路優方法的基礎上引入隨機化思想，既適用於鏈路狀態路由方法，也適用於距離矢量路由方法。
首先，對於現有的基於基本LS方法或DV方法的路由器，需相應地擴展路由表，使其包括最優路由和隨機路由兩類表項。
各路由結點在每個路由表更新周期開始時，利用基本LS方法，在自治系統內進行擴散(Flood)通告，一個路由結點發出的擴散通告裡包括了該結點與其所有相鄰結點的距離，可用於計算全局最短路徑樹。路由結點利用其他路由結點的最新擴散通告，構造出自治系統的全局拓撲圖，並利用Dijkstra算法建構本結點到系統內所有結點的全局最短路徑樹，其中距離測度一般為傳輸延遲、跳(Hop)數、隊列長度或上述指標的權重平均。也可以採用基本DV方法來獲得本地結點的全局最短路徑樹。
然後，每個路由結點獲得所有與其相鄰的結點的全局最短路徑樹，對於有CPU瓶頸的結點，最好在約定了相鄰結點互發全局最短路徑樹的通信協議後通過直接網絡通信獲得；對於有帶寬瓶頸的結點，其相鄰結點的全局最短路徑樹最好由本地結點直接計算獲得。
設S為自治系統中任一路由結點，其鄰結點集B(S)＝{B1，B2，...，Bk}，鄰點Bi所對應的鄰邊的長度是l(S，Bi)，i＝1，2，...，k。若結點S當前處理的報文的目的地址為D，則結點S利用如下公式構造該報文的隨機路由集C(S，D)C(S，D)≡{Bi|Lopt(S，D)≤l(s，Bi)+Lopt(Bi，D)，Lopt(S，D)＞Lopt(Bi，D)}-{Bopt(S，D) (1)其中，Bopt(S，D)為既屬於從S到D的最短路徑、又屬於B(S)的路由結點，若存在多個這樣的結點，即對應有多條測度相同的最短路徑，則任選其中一個作為Bopt(S，D)；Lopt(X，Y)為結點X與結點Y之間的最短路徑長度。C(S，D)和Bopt(S，D)一經獲得即被存儲並應用於整個路由表更新周期。
在圖1中，假設結點A到右子網的最佳路由是a，而結點B點到右子網的最佳路由是b；結點A到右部子網的次優路由是c，再經b，而結點B到右部子網的次優路由也是c，再經a。這樣，如果一個目的地址在右部子網的報文在A點經由次優路由c發送到結點B，而結點B也可能選擇次優路由c發送這個報文，這個過程可能任意重複下去，就構成了所謂的路由環。為消除路由環，本發明所述方法進一步引入了無環約束條件(Lopt(S，D)≤l(s，Bi)+Lopt(Bi，D))Λ(Lopt(S，D)＞Lopt(Bi，D))(2)。
隨機路由集建構完成後，路由結點需判斷當前是否有需要處理的報文，如果沒有，則等待。如果需處理的報文沒有優先級，那麼路由結點S以概率Popt(S)按最優路由Bopt(S，D)發送報文；以概率Prnd(S)≡1-Popt(S)根據隨機路由集發送報文。如果報文具有優先級，且報文被賦予高優先級的概率是Ph，則路由結點S發送報文的路由規則需做如下修改1)如果Ph≤Popt，則高優先級報文以概率1按最優路由發送；低優先級報文以概率 按最優路由發送，以概率 按隨機路由集C(S，D)發送。
2)如果Ph＞Popt，則高優先級報文將以概率 按最優路徑發送，以概率 按隨機路由集C(S，D)發送；低優先級報文以概率1按隨機路由集C(S，D)發送。
例如，如果Popt＝0.4，Ph＝0.25，則所有高優先級報文將以概率1按最優路由發送，而低優先級報文將以概率Popt-Ph1-Ph=0.2]]>按最優路由發送，以概率0.8隨機發送。
當隨機發送時，根據公式(3)確定C(S，D)中的路由結點Cj被選為報文路由的後驗概率 其中，r是用來調整路徑距離測度與路徑被選擇的概率之間的關係，此後驗概率用於選擇隨機路徑。
為模擬隨機機制，需要隨機數發生源來生成隨機數。隨機數可以由路由結點的偽隨機數發生器生成，也可以直接利用報文中的某些欄位作為隨機信息源。如果一個路由結點沒有滿足無環路由規則的隨機路徑，則流經它的所有報文強制按優化路由Bopt(S，D)發送。
圖3是關於自適應的隨機化路由方法的流程圖。非自適應方法和自適應方法的區別在於對關鍵參數Popt(S)的設定。
自適應隨機化路由方法的思路是通過動態調整概率Popt(S)的數值，實現優化的負載平衡。自適應性主要體現在當前的調整策略是由上一步調整策略的效果決定的。具體地說，在第t個路由表更新周期結束時，自適應隨機化路由方法根據路由結點的各輸出鏈路長度和的變化，通過公式(4)計算下一周期概率 的值。Popt(t+1)(S)=B{Popt(t)(S)-T[Popt(t)(S)]N[D(t+1)(S)]},>0---(4)]]>其中Popt(t)(S)=Popt(t)(S)-Popt(t-1)(S),]]>D(t+1)(S)=i=1kl(t+1)(S,Bi)-i=1kl(t)(S,Bi),]]> 閾值函數T保證每次調整量的絕對值不小於閾值h，且可以避免偶然出現的零值ΔD(S)使其後的Popt(S)全部歸零；規範化函數N用於規範 的取值範圍，使其不會由於 的隨機性大波動而劇烈變化。
概率Popt(S)調整後，其餘的流程與非自適應的隨機化路由方法相同。
顯然，當Popt(S)＝1時，本發明與基本的鏈路狀態路由或距離矢量路由局域最優方法是等效的。在自適應隨機化方法中，不妨將Popt(S)的初值取為1，其後Popt(S)會由控制策略自適應地調節。
為了驗證本發明的效果，對本發明進行了仿真。仿真採用了圖1所示的網絡拓撲結構，並涉及3類對象鏈路，結點和報文。鏈路負責報文的傳輸，結點除了負責路由轉發，也是新報文的生成源，業務模型分別使用了非突發性的泊松過程和突發性的分數差分噪聲過程。
每個報文對象的參數主要包括產生時間、死亡時間、拋棄標誌、源地址、目地址和優先級。所有的報文參數均初始化為-1，在仿真過程中被動態設置和修改。優先級表明了報文要求的服務類別，本發明的優先級只設定「高」、「低」兩種，分別代表了高服務質量要求或低服務質量要求。在所有仿真過程中，每個新生成的報文以概率Pb＝0.25被賦予高優先級，以概率Pl＝0.75被賦予低優先級。
圖4示出了業務源為泊松過程的情況下，利用本發明所述方法進行路由時仿真網絡關鍵結點A和B的概率Popt與源、目的地址不在同一個子網的跨子網報文的平均傳輸延遲(Average Delay)之間的關係，其中橫軸表示概率Popt，縱軸表示平均傳輸延遲。上、中、下三個子圖分別示出了所有報文的平均傳輸延遲(不考慮優先級)、高優先級報文的平均傳輸延遲和低優先級報文的平均傳輸延遲。由圖4可知，在業務源為非突發性泊松模型的情況下，引入隨大豆是於1999年10月26日收割的。有Phytophthoram的存在，並且是於1999年9月2日鑑定的。Cobra處理顯著的降低了Phytophthora的發生率，並且顯著增加了產量。對於總異黃酮，如下計算LSD(P＝0.05)＝3835.87；SD＝1919.86；CV＝9.36；處理概率(F)＝0.153。
表11
斜體字表示的製劑是對照組。後邊跟有相同字母的均值沒有顯著的差別(P＝.05，Student-Newman-Keuls)E)Pioneer 93B01 RR是在位於俄亥俄州MT.Vernon的Springer農場的田地裡種植的。是在1999年6月30日使用製劑的。大豆是於1999年10月26日收割的。有Phytophthora m的存在，並且是於1999年9月2日鑑定的。Cobra處理顯著的降低了Phytophthora的發生率，並且顯著增加了產量。對於總異黃酮，如下計算LSD(P＝0.05)＝4189.86；SD＝2097.06；CV＝10.47；處理概率(F)＝0.2878。
權利要求
1.一種隨機化的路由方法，其特徵在於，包括以下步驟一、擴展路由器的路由表，並為各結點初始化概率Popt(S)；二、新的路由表周期開始，路由結點根據基本LS方法或DV方法獲得本結點到系統內其他所有結點的全局最短路徑樹；三、路由結點通過直接計算或網絡通信獲得與其相鄰的各結點的全局最短路徑樹；四、路由結點建構本結點到自治系統內所有其他結點的隨機路由集；五、判斷當前是否有需要處理的報文，若有，則進入步驟六；若無，則等待；六、判斷當前需處理報文是否具有優先級；若報文具有優先級，則轉步驟八；七、若報文不具有優先級，則所述路由結點以概率Popt(S)按局域最優路由方法獲得的最優路由發送流經它的報文，以概率1-Popt(S)按隨機路由集發送流經它的報文；然後轉步驟十一；八、判斷高優先級報文在所有報文中出現的概率Ph是否大於概率Popt(S)，若概率Ph不大於概率Popt(S)，則轉步驟十；九、若概率Ph大於概率Popt(S)，則高優先級報文以概率 按最優路由發送，以概率 按隨機路由集發送；低優先級報文均以概率1按隨機路由集發送；然後轉步驟十一；十、高優先級報文以概率1按最優路由發送；低優先級報文以概率 按最優路由發送，以概率 按隨機路由集發送；十一、判斷路由表更新周期是否結束，若是，則轉步驟二；若否，則轉步驟五。
2.如權利要求1所述的隨機化的路由方法，其特徵在於在路由表更新周期結束時，根據公式(4)動態調整概率Popt(S)的值Popt(t+1)(S)=B{Popt(t)(S)-T[Popt(t)(S)]N[D(t+1)(S)]},>0---(4).]]>
3.如權利要求1或2所述的隨機化的路由方法，其特徵在於所述步驟四中，路由結點依據公式(1)建立隨機路由集C(S，D)≡{Bi|Lopt(S，D)≤l(s，Bi)+Lopt(Bi，D)，Lopt(S，D)＞Lopt(Bi，D)}-{Bopt(S，D)(1)其約束條件為(Lopt(S，D)≤l(s，Bi)+Lopt(Bi，D))Λ(Lopt(S，D)＞Lopt(Bi，D)) (2)。
4.如權利要求3所述的隨機化的路由方法，其特徵在於所述步驟四也可以是在一個由報文頭包含的新的源-目地址對首次出現時計算該源-目地址對的隨機路由集，並存儲應用於整個路由周期。
5.如權利要求1或2所述的隨機化的路由方法，其特徵在於所述按隨機路由集發送報文還進一步包括1)確定隨機路由集內的路由結點被選為報文路由的後驗概率；2)生成隨機數；3)選擇隨機發送路徑發送報文。
6.如權利要求5所述的隨機化的路由方法，其特徵在於根據公式(3)確定所述隨機路由集內的路由結點Cj被選為報文路由的後驗概率
7.如權利要求5所述的隨機化的路由方法，其特徵在於隨機數可以由路由結點的偽隨機數發生器生成，也可以直接利用報文中的某些欄位作為隨機信息源。
全文摘要
本發明提供的隨機化的路由方法，適用於IP網絡消息的傳送，通過在現有的局域最優方法的基礎上引入隨機化的思想來實現，同時還可自適應地調整最由路由概率，有效地避免了路由振蕩，實現了對空閒次優鏈路的利用，提高了網絡整體傳輸性能。自適應隨機化路由方法對最優路由概率P
文檔編號H04Q3/00GK1398091SQ0112620
公開日2003年2月19日 申請日期2001年7月13日 優先權日2001年7月13日
發明者侯越先 申請人:深圳市中興通訊股份有限公司