基於加權一階局域法的公共擁塞路徑檢測方法
2023-06-06 14:10:46 2
專利名稱：基於加權一階局域法的公共擁塞路徑檢測方法
技術領域：
本發明的是一種網絡信息技術領域的路徑檢測方法，具體地說，涉及的是一種 基於加權一階局域法的公共擁塞路徑檢測方法。
背景技術：
網絡擁塞信息對於網絡資源管理是至關重要的，而其中一個基本問題是如何準 確地判斷出兩個流是否經過了公共擁塞路徑。這種信息對於重疊網絡則更為重要， 因為重疊網絡的網絡拓撲不能預先知道，僅靠試探的方法建立連接，這可能導致 大量的流經過同一段瓶頸路徑。如果這種公共擁塞信息能夠被及時檢測到，就能 夠調整路由策略或改變重疊網絡的拓撲結構來避免瓶頸路徑的出現，從而優化網 絡性能。
經對現有技術的文獻檢索發現，2002年Rubenstein等在《IEEE/ACM Transactions on Networking》上發表的《Detecting shared congestion of flows via end-to-end measurement^ —文中提出的一種用計算互相關性檢測公共擁塞 路徑的方法，他們的方法利用一個泊松過程向兩條路徑發送檢測包，用兩個檢測 流端到端時延序列的互相關係數作為判斷是否經過公共擁塞路徑的標準。這種方 法基於線性計算技術對網絡流量的特徵參數進行分析，從而進行判斷。其優點是 複雜度低，收斂速度快。但是，網絡本身是一個複雜的非線性系統，僅僅用基於 線性計算分析技術的方法很難對網絡流量行為做出準確的估計，這也限制了這種 方法的性能。
發明內容
本發明的目的在於針對現有技術的不足，提供一種基於加權一階局域法的公 共擁塞路徑檢測方法，結合重疊網絡擁有的智能節點和分布式計算能力，以及擁 塞環境下網絡流量的非線性系統特性，基於混沌信號處理技術對網絡流量特徵進 行檢測，從而得出對其是否經過共同擁塞路徑的判斷。本發明在同等收斂速度下 具有更高的判斷準確性。本發明是通過以下技術方案實現的，本發明首先在被測系統兩端構造探測流 量，利用其端到端時延序列作為其行為特徵量，然後基於加權一階局域法對時延 序列進行預測並與實際網絡行為作比較，最後將預測結果的相似性作為參數來判 斷兩個網絡流是否經過了公共擁塞路徑。網絡中端到端時延的變化主要決定於路 徑中路由器緩存隊列長度的變化。重負載會導致擁塞，此時由於路由器緩存隊列 長度變化較大，則端到端時延也會有較大的波動。相反，當負載較輕時，時延則 相對穩定。因此，端到端時延序列的特徵能夠很大程度上反映網絡的運行狀況。 當兩條網絡流連接經過同一段擁塞路徑時，它們的端到端時延序列就會表現出一 些相似的特性，本發明正是基於這一原理，採用非線性系統分析方法提取兩個網 絡流時延序列的相似性特徵量，從而判斷出兩條網絡流是否經過了公共擁塞路徑。
本發明包括如下步驟-
步驟一在被測網絡系統兩端構造兩個探測流並分別進行採樣，得到兩個探 測流的端到端時延序列；
步驟二對步驟一其中一個探測流繼續採樣，得到一個延時序列；
步驟三採用加權一階局域法對步驟一的兩個時延序列進行預測，尋找待預 測點在重構相空間中最鄰近的點作為預測結果；
步驟四將步驟三得到的兩個採樣序列的預測結果和步驟二採樣得到的延時 序列作比較，計算相對誤差，得到預測結果的相似性；
步驟五根據兩個探測流預測結果的相似性判斷是否存在公共擁塞路徑。
所述的步驟一，具體為從自身時鐘的某時刻開始，兩個探測流分別以一定 速率發送一個UDP包隊列，同時加蓋時間戳，每一個這樣的UDP包稱作一個檢測 包。當收到一個檢測包後，流的目的節點計算端到端時延並發送，並同時將原始 的時間戳一併發送至源節點。然後源節點記錄端到端時延和時間戳作為一個延時 採樣。兩個採樣延時序列用於後續的加權一階局域法預測。
所述的步驟二，具體為選擇步驟一兩條路徑的其中一條路徑繼續採樣一段 時間，得到序列A^。,(1，2，…W)， A^。,反映了實際的網絡行為，用於和後面的預
測序列進行比較。
所述的步驟三，具體為分別採用步驟一得到的兩個採樣延時序列用相空間
5重構的方法對系統進行建模擬合，然後利用加權一階局域法對釆樣序列進行預測， 預測的主要原理是尋找待預測點在重構相空間中最鄰近的點作為預測結果，然後 將預測結果用於誤差比較。
所述的步驟四，具體為分別計算兩個預測序列相對於標準序列A^。,(0的平 均相對誤差e^和e/7;,同時，用它們的相似性作為參數來判斷是否存在公共擁塞。
e/7;和^7;的差為^r ，由於wr能夠反映出兩次預測結果的相似程度，因此可以
作為判斷兩個流是否經過了公共擁塞路徑的標準。
所述的步驟五，具體為在公共擁塞判決單元將步驟四所得的預測誤差的相似 程度與判決門限進行比較，若大於判決門限則認為兩條鏈路經過了公共擁塞，反 之則認為兩條鏈路是獨立的。其中判決門限的計算根據以往統計數據結合概率論 中最大似然估計的方法來確定。
本發明的優點在於從系統的觀點分析問題，充分把握擁塞網絡的混沌特性， 採用非線性方法對網絡進行準確建模；基於重疊網絡分布式的計算能力，採用基 於混沌預測的方法，提取採樣延時序列的相似性，並對預測結果誤差比較來判斷 是否產生公共擁塞。因此，在將本發明應用到協作擁塞控制及重疊網絡構建時， 可以準確的對網絡中是否產生公共擁塞進行判斷，從而有效的提高網絡帶寬的利 用率，保持整個網絡系統的穩定性，優化網絡資源的配置。總之，與相關的公共 擁塞檢測方法相比，本發明能夠對網絡進行更精確的分析，具有更高的精確性和 快速的收斂性，在重疊網絡飛速發展的今天，具有非常廣泛的應用前景。
圖1為本發明所用的網絡模型的拓撲圖。 圖2為本發明實施例的流程圖。 圖3為仿真實驗的網絡拓撲圖。 圖4為長TCP背景流環境下的仿真結果；
其中圖(a)是長TCP流公共擁塞的判定正確率與採樣時間的關係圖； 圖(b)是長TCP流獨立擁塞的判定正確率和釆樣時間的關係圖。 圖5為UDP背景流環境下的仿真結果
其中圖(a)是UDP流公共擁塞的判定正確率與採樣時間的關係6圖(b)是UDP流獨立擁塞的判定正確率和採樣時間的關係圖。 圖6為短TCP背景流環境下的仿真結果
其中圖(a)是短TCP流公共擁塞的判定正確率與採樣時間的關係圖； 圖(b)是短TCP流獨立擁塞的判定正確率和採樣時間的關係圖。
具體實施例方式
下面結合附圖對本發明的實施例作詳細說明本實施例在以本發明技術方案 為前提下進行實施，給出了詳細的實施方式和具體的操作過程，但本發明的保護 範圍不限於下述的實施例。
以圖l所示網絡拓撲說明具體實施例，這種啞鈴模型是對真實網絡的一種簡單 抽象，不影響本發明實施的一般性。
在圖1中，1^到X&和UIJ4表示了網際網路上兩條有公共路徑的連接，S到T 段為它們的公共路徑。令X的端到端時延為化，Y的端到端時延為Z), A和A分 別由兩部分組成從S到T的時延《，以及其他非公共路徑的時延，分別用《，《 表示。
Dy=《+《 (1)
圖2是本實施例的實現流程圖，圖中各部分與上述技術方案各個步驟相對應， 同時也標出了各個步驟所採用的處理單元，其中釆樣單元主要對探測流進行採樣， 獲得端到端時延序列；加權一階局域法預測單元採用加權一階局域計算方法對實 驗序列進行預測；預測誤差比較單元主要將兩個探測流的預測誤差進行處理，並 計算出兩個探測流採樣時延序列的相似性；公共擁塞判決單元主要利用採樣實驗
序列的相似性和設定的門限值對是否發生公共擁塞做出二進位判決。 本實施例具體步驟實施如下
步驟一，結合圖1具體說明採樣的過程兩個探測流分別從X^ ， U荒向， 4。以I^到義^為例，1^向；^,發送一個UDP包隊列(探測流採用UDP協議)， 其中發送速率設為/,同時加蓋時間戳，從自身時鐘的/。時刻開始。每一個這樣的UDP包稱作一個檢測包。檢測包以一個固定的速率被發送直到^+r，這裡r是
檢測間隔。當收到一個檢測包後，義&計算端到端時延並同時將原始的時間戳一 並發送返回至A^。然後義m記錄端到端時延和時間戳作為一個延時採樣。}^到 乙也以相同方法收集延時採樣。這裡記兩條路徑的採樣序列分別為
A」。一(1，2,…，")和A—，,e(i,2,…")，且採樣點數A^r/。採樣過程採用對應的
採樣單元實現，兩個採樣延時序列分別被送往加權一階局域法預測單元。由於網 絡丟包的影響，可能會使兩個探測流的數據包序列產生嚴重的不同步，這對於隨 後的預測處理的精確性有很大的影響。本方法在消除該負面影響方面採用的解決 技術是對原始的時延序列進行線性內插，即，如果某一個包丟失，那麼這個包的 時延就取相鄰兩個包的時延的平均值。
步驟二，在圖i中的兩條路徑中選擇一條路徑(不妨選擇義^到x^)繼續採
樣一段時間7;，得到序列Z)。^a,(l,2,…n)， A^。,反映了實際的網絡行為，用於和後
面的預測序列進行比較，此時採樣點數
W， (2)
序列A^K。,被送往預測誤差比較單元。
步驟三，即為加權一階局域法預測單元的實現，具體為分別利用步驟一得
到的A，—《， (o對後面的A^個點進行預測，^v應該和7;時間內採
肖肖到化""",*列的*@+目同。予則則《用w力fe力加fe—l^^⑨fe， ^ *原、,|
將相空間軌跡的最後一點作為中心點，把離中心點最近的若干軌跡點作為相關點， 然後對這些相關點進行擬合，再估計軌跡下一點的走向，最後從預測出的軌跡點 的坐標中分離出所需要的預測值。在本方法中首先採用相空間重構的方法將兩個
待預測延時採樣序列Df^(1,2,…")和Z)f^(1，2,…w)映射到多維向量空間中， 然後用加權一階局域法進行預測，得到兩個預測結果序列，分別記為A,(/)和 ， 和r、戸(0都是長度為iVpre的時間序列。其中，加權一階局域法的主要步驟是
(a) 重構相空間。根據G—P算法計算出時間序列的關聯維d，再由Takens定
理選取嵌入維數，w2 2c/ + l，得到重構相空間為
y(O = (x0)， x(/ + r)，…，x(f + (m - I)t)) " V = 1,2,…,M
其中M為重構相空間點的個數，M = iV-(m-l)r。
(b) 尋找鄰近點。在相空間中計算各點到中心點i;之間的空間距離，找出K的
參考向量集為i;， i = l， 2，， q，並且點&的的距離為《。設《是《中的最小
值，定義點i;的權值為
exp(—a(i/,-《))
》xp(-a(《-《))
其中a為參數，不妨取3=1。 (C)進行計算預測。 一階加權局域線性擬合為:formula see original document page 9
這裡就m=l的情況進行討論，ra〉l的情況類似，艮P:
formula see original document page 9
應用加權最小二乘法有
將式(6)看成是關於未知數a， b的二元函數，兩邊求偏導得到:
(6)即化簡得到關於未知數a， b的方程組為
化,+ 6Z《'=Z ^x;+i
i=l ''=1 >=1
、 j=l /=1 解方程組(8)得到a， b，然後代入式(4)得預測公式。
(d)根據預測公式進行預測。顯然，參考向量集為&， i=l， 2，
(7)
(8)
q的一步預
測為};+1， i = l， 2，…，q。
步驟四，即為預測誤差比較單元的實現，具體為由於若兩個延時採樣序列所 對應的網絡流具有公共擁塞路徑，則有可以進行相互預測。基於這一點，分別計 算兩個預測序列D 。 ， 相對於標準序列的平均相對誤差^r,
和w ，其定義式分別為式(9)和式(10)。由多次實驗結果觀測到當兩個流經過
公共擁塞路徑時，e^;和er 極為近似，而當兩個流的擁塞路徑是獨立的時候，w
和en;相差較大，因此，可以用它們的相似性作為參數來判斷是否存在公共擁塞。
定義e/7;和e^的差為^r (式11)，由於e^能夠反映出兩次預測結果的相似程度，
因此可以用來作為判斷兩個流是否經過了公共擁塞路徑的標準。
Z {[久—戸(0 -化—一,(o] /化—。咖,(0}
(9)
S {[ A， (' ) - A—(' )] /化—。咖,(W
,=i
6rr = grrT _ cat*,,
(10)
(11)
步驟五，將步驟四所得的預測誤差的相似程度與已知的判決門限進行比較，判
10斷是否存在公共擁塞鏈路。其中，對於判決門限，可依靠以往的採樣數據，計算 出公共擁塞和獨立擁塞兩種情況下預測相似性的概率分布，然後根據最大似然估 計的方法來確定。
下面給出一個具體實施的仿真實驗來闡述本發明的有效性。需要說明的是，實 驗中應用的參數不影響本發明的一般性。
仿真使用網絡仿真軟體ns2進行，圖3為仿真試驗的網絡拓撲。其中各條鏈路 的傳輸時延設為10ms，鏈路帶寬設為1. 5MB，其中節點4到節點7為公共擁塞路 段。兩個探測流的配置為
探測流l:從節點0流向節點7， UDP流，上加C服業務，包大小為20Byte, 速率4kb。
探測流2:從節點2流向節點7， UDP流，上加C服業務，包大小為20Byte， 速率4kb。
仿真實驗主要在長TCP流，短TCP流，UDP流3種網絡環境下進行，下面是3 種環境下詳細的背景流設置
(1) 長TCP流用數量不多的長TCP流來引起擁塞，非擁塞路段是空的。在公 共擁塞的情況下，20個TCP流通過這段路徑。在獨立擁塞的情況下，節點4到節點7 是空的，其他連接有TCP流，數量服從0到20的均勻分布。
(2) 開關CBR流仿真試驗用Pareto開關CBR流作為背景流，其特點是可以通 過改變背景流的數量來控制擁塞的程度。在公共擁塞情況下，IOO個開關CBR流通 過節點4到節點7。其他路徑上的開關CBR流的數量服從31到60的均勻分布。對於獨 立擁塞，節點4到節點7的開關CBR流數量服從31到70的均勻分布，其他鏈路上服從 80到140的均勻分布。
(3) 短TCP流由ns2的網站流量發生器產生的大量的短TCP流作為背景流。產 生的流量主要由網站通話所組成。對於公共擁塞的情況，250個網站通話通過節點 4到節點7，其他鏈路上網站通話的數量服從1到25的均勻分布。對於獨立的擁塞， 4到7的網站通話的數量服從1到25的均勻分布，其他鏈路上服從151到250的均勻分 布。
在上面所述三種網絡環境下，對於公共擁塞和獨立擁塞各進行了 500次實驗，
11並將本發明與Rubenstein的基於延時的方法和Harfoush的基於丟包率的方法 進行比較。作為判斷方法性能的指標，這裡定義
公共擁塞的判定正確率二實驗判斷為公共擁塞的次數/總公共擁塞實驗次數 獨立擁塞的判定正確率=實驗判斷為獨立擁塞的次數/總獨立擁塞實驗次數 圖4，圖5，圖6分別對應了三種網絡環境中3種方法的仿真結果。其中CP(chaos prediction)表示本發明，MP和BP分別表示基於延時和丟包率的方法。
從圖4可以看到，對於長TCP流，三種方法的性能較為接近，而且均能在公共 擁塞和獨立擁塞兩種情況下都達到較高的準確率(90%以上)。從圖5中看到，對 於UDP流，三種方法的性能都有所下降，尤其是BP，在公共擁塞的情況下，正確 率只有不到50%，可以認為BP已經不能檢測UDP背景流情況下的公共擁塞；而對 於CP和MP兩種方法仍然具有較好的性能，在公共擁塞情況下，CP的正確率要略 高於MP，而在獨立擁塞情況下，兩者性能較為接近，因此可以認為在UDP流環境 下，CP的性能稍好於MP。從圖6中看到，對於短TCP流，BP檢測公共擁塞的性能 仍然較差；而CP和MP相比，仍是CP性能要好於MP。從收斂性方面考慮，對於 MP，判定正確率隨時間的變化比較平滑，能夠在很短的時間內達到較高的正確率， 而對於CP，可以看到，在6s之前的準確率一般不如MP，而在6s後迅速收斂，達 到很高的準確率。總之，三種方法中，BP性能最差，只在長TCP流業務環境下有 著較好的性能，因此很難被廣泛使用；而在其餘兩種方法中，正確率方面，本發 明所提出的CP方法性能要優於MP，而在收斂性方面MP的性能要強於CP，但CP 也可以在6s後迅速收斂，對於實時性要求不是特別高的場合有很好的應用前景。
權利要求
1、一種基於加權一階局域法的公共擁塞檢測方法，其特徵在於包括如下步驟步驟一在被測網絡系統兩端構造兩個探測流並分別進行採樣，得到兩個探測流的端到端時延序列；步驟二對步驟一其中一個探測流繼續採樣，得到一個延時序列；步驟三採用加權一階局域法對步驟一的兩個時延序列進行預測，尋找待預測點在重構相空間中最鄰近的點作為預測結果；步驟四將步驟三得到的兩個採樣序列的預測結果和步驟二採樣得到的延時序列作比較，計算相對誤差，得到預測結果的相似性；步驟五根據兩個探測流預測結果的相似性判斷是否存在公共擁塞路徑。
2、根據權利要求1所述的基於加權一階局域法的公共擁塞檢測方法，其特徵是，所述的步驟一，具體為從自身時鐘的某時刻開始，兩個探測流分別以一定速率發送一個UDP包隊列，同時加蓋時間戳，每一個這樣的UDP包稱作一個檢測包；當收到一個檢測包後，流的目的節點計算端到端時延並發送，並同時將原始的時間戳一併發送至源節點，然後源節點記錄端到端時延和時間戳作為一個延時採樣，兩個採樣延時序列分別進行加權一階局域法預測。
3、 根據權利要求1所述的基於加權一階局域法的公共擁塞檢測方法，其特徵是，所述的步驟二，具體為選擇步驟一中兩條路徑的其中一條路徑繼續採樣一段時間，得到序列A^。,(1,2,…W)， A^。,反映了實際的網絡行為，用於和後面的預測序列進行比較。
4、 根據權利要求1所述的基於加權一階局域法的公共擁塞檢測方法，其特徵是，所述的步驟三，具體為分別採用步驟一得到的兩個採樣延時序列用相空間重構的方法對系統進行建模擬合，然後利用加權一階局域法對採樣序列進行預測，尋找待預測點在重構相空間中最鄰近的點作為預測結果，將預測結果用於誤差比較。
5、 根據權利要求1所述的基於加權一階局域法的公共擁塞檢測方法，其特徵是，所述的步驟四，具體為分別計算兩個預測序列相對於標準序列A^。,(Z')的平均相對誤差e^和^v;，同時，用它們的相似性作為參數來判斷是否存在公共擁塞，e^和e^的差為eir (式(IO))， err能夠反映出兩次預測結果的相似程度，作為判斷兩個流是否經過了公共擁塞路徑的標準。
6、根據權利要求1所述的基於加權一階局域法的公共擁塞檢測方法，其特 徵是，所述的步驟五，具體為在公共擁塞判決單元將步驟四所得的預測誤差的 相似程度與判決門限進行比較，若大於判決門限則認為兩條鏈路經過了公共擁 塞，反之則認為兩條鏈路是獨立的，其中判決門限的計算根據以往統計數據結合 概率論中最大似然估計的方法來確定。
全文摘要
本發明涉及一種網絡信息技術領域的基於加權一階局域法的公共擁塞路徑檢測方法。本發明在被測網絡系統兩端構造兩個探測流並分別進行採樣，得到兩個探測流的端到端時延序列；其中一個探測流繼續採樣，得到一個延時序列；採用加權一階局域法對兩個時延序列進行預測，尋找待預測點在重構相空間中最鄰近的點作為預測結果；將預測結果和採樣得到的延時序列作比較，計算相對誤差，得到預測結果的相似性；根據兩個探測流預測結果的相似性判斷是否存在公共擁塞路徑。本發明基於混沌信號處理技術對網絡流量特徵進行檢測，從而得出對其是否經過共同擁塞路徑的判斷，本發明在同等收斂速度下具有更高的判斷準確性。
文檔編號H04L12/26GK101505268SQ20091004746
公開日2009年8月12日 申請日期2009年3月12日 優先權日2009年3月12日
發明者張清源, 理 潘 申請人:上海交通大學