[發明專利]基于加權一階局域法的公共擁塞路徑檢測方法

無效

• 申請號: 200910047466.6
• 申請日: 2009-03-12
• 公開（公告）號: CN101505268A
• 公開（公告）日: 2009-08-12
• 發明（設計）人: 潘理;張清源
• 申請（專利權）人: 上海交通大學
• 主分類號: H04L12/56
• 分類號: H04L12/56;H04L12/26
• 代理公司: 上海交達專利事務所
• 代理人: 王錫麟;王桂忠

技術領域

本發明的是一種網絡信息技術領域的路徑檢測方法，具體地說，涉及的是一種 基于加權一階局域法的公共擁塞路徑檢測方法。

背景技術

網絡擁塞信息對于網絡資源管理是至關重要的，而其中一個基本問題是如何準 確地判斷出兩個流是否經過了公共擁塞路徑。這種信息對于重疊網絡則更為重要， 因為重疊網絡的網絡拓撲不能預先知道，僅靠試探的方法建立連接，這可能導致 大量的流經過同一段瓶頸路徑。如果這種公共擁塞信息能夠被及時檢測到，就能 夠調整路由策略或改變重疊網絡的拓撲結構來避免瓶頸路徑的出現，從而優化網 絡性能。

經對現有技術的文獻檢索發現，2002年Rubenstein等在《IEEE/ACM Transactions?on?Networking》上發表的《Detecting?shared?congestion?of?flows via?end-to-end?measurement》一文中提出的一種用計算互相關性檢測公共擁塞 路徑的方法，他們的方法利用一個泊松過程向兩條路徑發送檢測包，用兩個檢測 流端到端時延序列的互相關系數作為判斷是否經過公共擁塞路徑的標準。這種方 法基于線性計算技術對網絡流量的特征參數進行分析，從而進行判斷。其優點是 復雜度低，收斂速度快。但是，網絡本身是一個復雜的非線性系統，僅僅用基于 線性計算分析技術的方法很難對網絡流量行為做出準確的估計，這也限制了這種 方法的性能。

發明內容

本發明的目的在于針對現有技術的不足，提供一種基于加權一階局域法的公 共擁塞路徑檢測方法，結合重疊網絡擁有的智能節點和分布式計算能力，以及擁 塞環境下網絡流量的非線性系統特性，基于混沌信號處理技術對網絡流量特征進 行檢測，從而得出對其是否經過共同擁塞路徑的判斷。本發明在同等收斂速度下 具有更高的判斷準確性。

本發明是通過以下技術方案實現的，本發明首先在被測系統兩端構造探測流 量，利用其端到端時延序列作為其行為特征量，然后基于加權一階局域法對時延 序列進行預測并與實際網絡行為作比較，最后將預測結果的相似性作為參數來判 斷兩個網絡流是否經過了公共擁塞路徑。網絡中端到端時延的變化主要決定于路 徑中路由器緩存隊列長度的變化。重負載會導致擁塞，此時由于路由器緩存隊列 長度變化較大，則端到端時延也會有較大的波動。相反，當負載較輕時，時延則 相對穩定。因此，端到端時延序列的特征能夠很大程度上反映網絡的運行狀況。 當兩條網絡流連接經過同一段擁塞路徑時，它們的端到端時延序列就會表現出一 些相似的特性，本發明正是基于這一原理，采用非線性系統分析方法提取兩個網 絡流時延序列的相似性特征量，從而判斷出兩條網絡流是否經過了公共擁塞路徑。

本發明包括如下步驟：

步驟一：在被測網絡系統兩端構造兩個探測流并分別進行采樣，得到兩個探 測流的端到端時延序列；

步驟二：對步驟一其中一個探測流繼續采樣，得到一個延時序列；

步驟三：采用加權一階局域法對步驟一的兩個時延序列進行預測，尋找待預 測點在重構相空間中最鄰近的點作為預測結果；

步驟四：將步驟三得到的兩個采樣序列的預測結果和步驟二采樣得到的延時 序列作比較，計算相對誤差，得到預測結果的相似性；

步驟五：根據兩個探測流預測結果的相似性判斷是否存在公共擁塞路徑。

所述的步驟一，具體為：從自身時鐘的某時刻開始，兩個探測流分別以一定 速率發送一個UDP包隊列，同時加蓋時間戳，每一個這樣的UDP包稱作一個檢測 包。當收到一個檢測包后，流的目的節點計算端到端時延并發送，并同時將原始 的時間戳一并發送至源節點。然后源節點記錄端到端時延和時間戳作為一個延時 采樣。兩個采樣延時序列用于后續的加權一階局域法預測。

所述的步驟二，具體為：選擇步驟一兩條路徑的其中一條路徑繼續采樣一段 時間，得到序列D_actual(1，2，…n)，D_actual反映了實際的網絡行為，用于和后面的預 測序列進行比較。

所述的步驟三，具體為：分別采用步驟一得到的兩個采樣延時序列用相空間 重構的方法對系統進行建模擬合，然后利用加權一階局域法對采樣序列進行預測， 預測的主要原理是尋找待預測點在重構相空間中最鄰近的點作為預測結果，然后 將預測結果用于誤差比較。