一種流量矩陣的估計方法
2023-06-24 22:26:06 1
專利名稱:一種流量矩陣的估計方法
技術領域:
本發明屬於網際網路技術領域,特別涉及ー種流量矩陣的估計方法。
背景技術:
近年來,隨著網際網路技術的飛速發展以及網絡規模大型化、類型多祥化、結構複雜化,網絡中各種性能參數的變化也越來越複雜。對ー個規模空前龐大的網絡進行網絡性能的優化、監控及管理,是當前網際網路領域所面臨的ー個全新的研究領域。流量矩陣作為網絡流量工程的重要參數,可以為網絡設計、容量規劃、擁塞控制、流量檢測、異常檢測等流量エ程和網絡管理提供有效的保障。流量矩陣(Traffic Matrix, TM)是網絡中流量的具體描述,由OD(Origin-Destination)流(即源節點到目的節點的流量)組成,反映了一個網絡中所有源節點和目的節點之間的流量需求。根據源節點目的節點的不同類型,OD流量矩陣能定義在任何尺度上,是網絡中節點對間流量大小的具體值。流量矩陣也給出了網絡流量在全 網中各個OD對間流量的分布情況。它作為網絡流量工程的重要輸入參數,受到國內外理論界和エ業界的廣泛重視,現已成為Internet的ー個重要研究熱點。同時也是網絡層析成像當中ー個重要的研究方向,具有它重要的現實意義。流量矩陣在理論界和エ業界受到了廣泛關注,學術界也對流量矩陣估計問題提出多種多樣的算法。而對於直接測量網絡的流量矩陣,在當今的網絡環境下則是難以行得通的。因為如今的實際網絡情況紛繁複雜,為了確保現有網絡的高效運行,一方面不能過多增加網絡負荷,即不能主動在需要估計流量矩陣的網絡中發送過多探測包,這樣將加重網絡的負載,影響網絡的效率;另ー方面網絡服務提供商基於商業考慮,通常也不會允許網絡中所有節點參與協作,且在不同域間獲得網絡節點的充分協作也很困難,直接測量最終可能覆蓋不到需要測量的網絡節點;所以在網絡中通過直接測量獲取流量矩陣是很困難甚至於不可行的。在現有的流量矩陣估計中不管是直接測量方法還是間接估算方法都有它的局限性。由於流量矩陣的目的是捕獲網絡流量的全局狀態,而網際網路規模越來越龐大,直接監控測量代價非常高,在實際上幾乎是不可行的。由間接觀測進行流量矩陣估算是目前獲得骨幹網絡流量矩陣的主要方法。在可測的鏈路數據、路由矩陣和流量矩陣之間具有確定的線性關係,由於可測的鏈路數目遠大於OD (Original-destination)流數目,層析成像流量矩陣估計是欠定性反問題求解。因此,流量矩陣估計問題本身是ー個欠定反問題,存在多解性,要獲得真實解,需要根據流量矩陣估計問題的特點,引入OD流量矩陣的ー些約束信息,縮小解空間,從而克服流量矩陣估計的多解性。因而,目前主要通過間接測量鏈路流量等較易獲得的網絡相關信息,通過估計模型或算法來獲得流量矩陣。但現有的估計模型對先驗信息和測量中的值的丟失非常的敏感,估計得到的結果有一定的誤差。近年來,流量矩陣的估計已成為ー個非常熱門的研究領域。與本發明相關的現有技術包括近年來,通過利用鏈路負載統計數據和其他的測量數據,結合間接流量矩陣估計算法來估計流量矩陣已經成為了ー個非常熱門的領域。在網絡層析成像理論中,流量矩陣的估算算法可統ー描述如下式(1-1)所示;其流量矩陣X,路由矩陣A,鏈路流量矩陣Y三者之間存在以下線性關係Y = AX (1-1)在網絡中,由於OD流的數量要遠遠多於鏈路的條數,如果直接求解式(1-1 ),意味著式(1-1)將有無窮多個可能的解,是病態反問題(ill-posec linear inverse problem)。因此求解上述問題吋,需要許多先驗信息來克服欠定性或者病態性問題。許多學者圍繞流量矩陣的估計方法等相關問題進行了大量的研究,提出了很多的估計算法,也取得了一定的成效。現有的估算算法可以歸納為幾類重力模型方法、統計推斷方法、第三代方法、獨立連接模型方法。(I)重力模型方法重力模型(gravity model)是最常見的ー種計算流量矩陣的方法,它的名字來源於牛頓的地球重力定律,通常被社會科學家用來模型化地域間人口、貨物或者信息的流動。·將重力模型引入流量矩陣估計領域,其基本思想是如果我們不知道網絡流量在全網中如何分布,可以估計OD流量佔從該源節點流入網絡的總流量的比例;也就是OD對目的節點總流出流量中有一定比例流量是來自於該源節點的,而這個比例就是OD對源節點總流入流量與整個網絡總流入流量的比值。如果對流量的來去無從得知,則最好的推測是估算網絡中每個節點接收和發送的流量值的比例。重力模型一般表達式如下
權利要求
1.一種流量矩陣的估計方法,其特徵在於包括如下步驟 步驟一、通過測量工具測量獲取路由矩陣A、鏈路流量矩陣Y及可測部分OD對流量; 步驟二、對路由矩陣A、鏈路流量矩陣Y及可測部分OD對流量作預處理將流量矩陣X中可測部分OD對流量剔除掉,將路由矩陣A中的對應列剔除掉,將鏈路流量矩陣Y的對應行表示的流量值減去剔除的OD對流量; 步驟三、運用線性規劃方法,對不可測部分OD對流量進行估計; 步驟四、將由步驟一測量得到的可測部分OD對流量和由步驟三估計得到的不可測部分OD對流量重新組成完整的流量矩陣,並標記出流量矩陣中測量得到的可測部分OD對流量; 步驟五、運用Zernike-Moment方法對由步驟四得到的流量矩陣進行插值修正,得到最終流量矩陣。
2.根據權利要求I所述的一種流量矩陣的估計方法,其特徵在於步驟三所述的運用線性規劃方法,對不可測部分OD對流量進行估計的方法為 1)構建目標函數f= min| |A' V -V I |,其中A'為步驟二中處理過的路由矩陣,V為待求的估計OD流,Y'為步驟二中處理過的鏈路流量矩陣; 2)構建約束條件
3.根據權利要求I所述的一種流量矩陣的估計方法,其特徵在於步驟五所述的運用Zernike-Moment方法對由步驟四得到的流量矩陣進行插值修正的方法為 1)將Zernike函數的積分形式離散化,得到求和形式的Zernike函數; 2)根據求和形式的Zernike函數,求取Zernike距; 3)根據Zernike距,求取權值w; 4)根據最小化能量函數,求取Z[k,I]; 5)根據最小化目標函數,最終求取流量矩陣X。
全文摘要
本發明公開了一種流量矩陣的估計方法。提出了一種基於線性規劃方法和Zernike-Moment相結合的流量矩陣估計算法,在本發明方法中,由於採用了線性規劃方法,通過目標函數的選擇來代替先驗信息,排除了模型對先驗信息的敏感性。而Zernike-Moment方法的插值處理,解決了K-NN算法中不能解決的大量數據丟失的情況,而且排除了模型對丟失值的敏感性,同時也克服了輸入信息中的噪聲對估計結果的影響。而且Zernike-Moment方法還可以利用LP方法得到的流量矩陣估計值,以及流量矩陣數據之間的結構相似性、冗餘信息、時空約束信息,來修正線性規劃方法的結果,進一步提高了流量矩陣估計的準確度。
文檔編號H04L12/24GK102801629SQ201210299129
公開日2012年11月28日 申請日期2012年8月22日 優先權日2012年8月22日
發明者錢峰, 龍利雄, 胡光岷, 姚興苗 申請人:電子科技大學