重慶郵l 乜學院碩1 ：論文 摘要 及時、準確獲取網絡內部各條鏈路的時延和帶寬利用率信息，以便實時、充 分了解網絡的狀態，是資源管理、擁塞控制、多路徑路由等網絡管理與控制手段 的關鍵之。高速i p 網絡要求測量方法滿足快速、及時、準確和低開銷的特點。 目前針對時延和帶寬利用率的測量分別采用了不同的測量模型架構，要想同 時獲得鏈路時延或利用率信息，必須啟動兩套測量系統，這樣既增加了測量開銷， 也不利于測量系統的維護和測量結果的進一步分析和使用。而且，現有的時延測 量模型存在測量精度差、安全性差等問題，影響了其在實際網絡中的實用性。而 帶寬利用率測量模型通常基于s n m p r m o n 機制，或基于類似n e t f l o w 的機制，加 重了路由器的處理負擔，影響路由器的轉發性能。 本文提出一種可以同時獲取網絡內部鏈路的時延和帶寬利用率的測量模型， 稱為線卡采集代理模型。通過設置于網絡節點接口上的線卡采集器實時監測并統 計鏈路上的流量，由預先設置好的線卡采集代理點集合發來的探測包將統計信息 帶回代理點，同時，通過計算發往同一條鏈路兩個端點的探測包的往返時間差得 到該鏈路時延，各代理點將匯總后的結果向網絡監測中心( n o c ) 報告，由n o c 進 一步得到全網監測結果。該模型以項點覆蓋和邊覆蓋的相關理論為基礎，證明了 以最小代價混合覆蓋全網的問題是n p 一難的，并提出新的貪心近似算法，仿真結 果驗證了算法的有效性。 作為模型的實現技術基礎，本文提出的線卡采集技術便于硬件實現，符合未 來路由器技術的發展趨勢，也可作為傳統測量方法信息采集技術的有效補充。基 于f p g a 實現了線卡采集模塊的硬件功能仿真，進行了模塊級功能測試，結果顯 示功能與性能達到了設計要求。最后，對整個模型系統進行了仿真測試，結果說 明文中模型是可行的。 關鍵詞：測量模型，時延，帶寬利用率，n p 一難，貪心算法，f p g a 重慶郵電學院碩十論文 一一 a b s t r a c t g e t t i n gd e l a ya n db a n d w i d t hu t i l i z a t i o no fl i n k si n 1 pn e t w o r kn o to n l v a c c u r a t e l yb u ta l s ot i m e l ya r eg o o dt ok n o ws t a t e so f n e t w o r k ，h o w e v e ri t so n eo f t h e c r i s i sn e t w o r km a n a g e m e n ta n dc o n t r o l l i n gs t e pf o rr e s o u r c em a n a g i n g ，c o n g e s t i o n c o n t r o l l i n g ，m u l t i p a t hr o u t i n ge t c t om e a s u r et h eh i g hs p e e di pn e t w o r ki nl a r g e s c o p e ，m e a s u r i n gm e t h o d sn e e dt om e e tt h er e q u i r e m e n t sf o r q u i c k l y , t i m e l y , a c c u r a t e l ya n dl o wo v e r h e a d b u tt h e r ea r ed i f f e r e n c e sb e t w e e nd e l a ym o n i t o r i n gm o d e l sa n du t i l i z a t i o n m o d e l s i fo n ew a n t st og e tb o t hd e l a ya n du s e t h e nh eh a st or u nt w om o n i t o r i n g s y s t e m s t h i sh a ss o m ea p p a r e n td r a w b a c k s a b o u tl i n k s d e l a ym o n i t o r i n gm o d e l s ， t h e ym a y b ei n a c c u r a t eo ri n s e c u r i t y a b o u tl i n k s u t i l i z a t i o n ，t h em o d e l sa v cu s u a l l ) b a s e do ns n m p r m o no rn e t f o w , w h i c hc a nb en e g a t i v ei m p a c to nt h er o u t e r s p e r f o r m a n c eo ff o r w a r d i n g i n t h i sp a p e r , w ep r o p o s eam e a s u r e m e n tm o d e lb a s e do nl i n ec a r dc o l l e c t i o n a g e n t ，w h i c hc o u l dg e te a c hl i n k sv a r i a b l ep a r a m e t e r si nn e t w o r k sw i t ho v e r h e a da s l o wa sp o s s i b l e o u rm o d e lh a st h ec o m b i n a t i o nv i r t u eo fv e r t e xc o v e ra n dl i n kc o v e r , a n di tc o u l dg e tl a t e n c ya n du t i l i z a t i o nu s e st h es a m em o d e ls y s t e mw i t hm a x i m u m r a t i oo fi n f o r m a t i o na n dc o s t s m o r e o v e gt h eq u e s t i o no fm i x e dc o v e rw i t hm i n i m u m c o s ti sp r o v e dt ob en p h a r d w ed e s i g nan o v e lg r e e d ya p p r o x i m m i o na l g o r i t h mf o r i t ，a n dg i v et h ee v i d e n c ef o ri t se f f e c t i v e n e s sb ys i m u l a t i o n l i n ec a r dc o l l e c t i o n ，t h ec o r ec o m p o n e n to fo u rm o d e lc a l lb em a d ei nh a r d w a r e i tc o u l db ev a l u a b l ec o m p l e m e n t st oe x i s t i n gi n f o r m m i o nc o l l e c t i o nt e c h n i q u e s a n d r e a l i z ei nh a r d w a r ei st h em o s tp o s s i b l et r e n d so ft e c h n i q u ed e v e l o p m e n t t h ea u t h o r h a sd e s i g nal i n ec a r dc o l l e c t i o nm o d u l ei nf p g a t h et e s tr e s u l t si m p l yt h a tt h e f u n c t i o n sa n dp e r f o r m a n c ea r eq u a l i t y f i n a l l y , t h es i m u l a t i o nr e s u l t ss h o wt h a tt h e m o n i t o r i n gm o d e li sf e a s i b l eu n d e rs i m u l a t i o ne n v i r o n m e n t s k e yw o r d s ：m e a s u r e m e n tm o d e l ，d e l a y l a t e n c y , b a n d w i d t hu t i l i z a t i o n ，n p h a r d ， g r e e d ya l g o r i t h m ，f p g a 獨創性聲明 本人聲明所呈交的學位論文是本人在導師指導下進行的研究工 作及取得的研究成果。據我所知，除了文中特別加以標注和致謝的地 方外，論文中不包含其他人已經發表或撰寫過的研究成果，也不包含 為獲得重迭鰹電堂瞳或其他教育機構的學位或證書而使用過的材 料。與我一同工作的同志對本研究所做的任何貢獻均已在論文中作了 明確的說明并表示謝意。 學位論文作者簽名：幕愛躑 簽字日期：妒爭年細哆日 學位論文版權使用授權書 本學位論文作者完全了解重廢整皇堂瞳有關保留、使用學 位論文的規定，有權保留并向國家有關部門或機構送交論文的復印件 和磁盤，允許論文被查閱和借閱。本人授權重龐由g 電堂瞳可以 將學位論文的全部或部分內容編入有關數據庫進行檢索，可以采用影 印、縮印或掃描等復制手段保存、匯編學位論文。 ( 保密的學位論文在解密后適用本授權書) 學位論文作者簽名：融螂 簽字日期：f ；f 年籮月乃e t ， 導師簽名：7 妻紅 簽字日期：似f f 年f 月巧e l 重慶郵電。學院碩士論文 1 1 引言 第一章緒論 1 1 1 對i p 網絡測量的必要性 未來，i p 網絡是否能夠繼續取得巨大的成功，關鍵之一是看其能否提供令用 戶滿意的服務質量( o o s ) ，通常需要保證o o s 的應用以低時延、低時延抖動的實 時應用為主。但是，i p 網絡在本質上只提供“盡力而為服務”，無法滿足諸如v o i p 、 實時媒體等應用的o o s 要求。因而迫使網絡服務提供商( i s p ) 改善網絡設備性 能，增加傳輸帶寬，如使用更先進的交換機實現業務處理，采用高帶寬的光纖介 質滿足高速數據傳輸的需要j 。這樣增加基礎設施的辦法，雖然能在一定程度上 緩減用戶數據傳輸帶寬和o o s 保證的壓力，但同時也使i p 骨干網絡鏈路平均利 用率愈來愈低。產生這種現象的原因主要是i n t e r n e t 流量極端不對稱，網絡流 量的分布極不平衡及其增長難于預測，而快速的傳輸技術的出現使大量增加鏈路 容量在經濟上可行，造成鏈路帶寬的過量供應【2 j 。另外，今天的運營商缺乏對網 絡內部鏈路贄源利用率情況的了解，也是造成鏈路帶寬過量供應的原因之一。因 為如果不知道網絡內部資源利用的情況，就無法量化提供q o s 與資源過量供應的 對比成本，運營商不得不采用寧多勿少地增加帶寬的策略，靠進一步降低鏈路利 用率來滿足低時延的應用需求【3 】。因此，當今天的運營商面對出于故障、擁塞引 起的網絡震蕩、不穩定進一步加劇擁塞，嚴重影響網絡性能問題時，依靠帶寬過 量供應，保持網絡的低利用率解決這類問題【4 l 。這樣與傳統基于時分復用的電信 網絡比較，大量的鏈路資源閑餐，使得基于統計復用的i p 網絡高效的資源利用 率的優越性無從體現j 。 然而，僅僅依靠鏈路帶寬過量供應，降低鏈路平均利用率并不能避免嚴重擁 塞和網絡資源利用率的進一步下降【4 】，也就必然不能令用戶滿意，因為用戶不僅 需要低時延，還需要低的時延抖動，要求網絡利用率的低變化率1 2 】。因此迫切需 要大型i s p 和自治系統( a s ) 具有可行的控制網絡資源、優化網絡性能的管理和 監控機制。及時獲取網絡內部備條鏈路的時延和帶寬利用率信息，以便實時。充 分了解網絡內部的狀態，是資源管理、擁塞控制、多路徑路由等控制手段的關鍵 之。 而網絡內部的動態信息只能通過測量的手段來獲得( w i h i a m s o nc 和 p a x s o nv ) 。同時，高速i p 網絡要求測量方法滿足快速、及時、準確和低開銷 要求。a c ms i g c o m m 從2 0 0 j 年開始連續舉辦了三屆網絡測量工作組會議，專門 重慶郵電學院碩十論文 討論測量模型、體系、工具等問題，以期對動態路由調整和靈活的網絡控制能力 提供測量支持。 1 1 2i p 網絡測量技術應該滿足的基本要求 i p 網絡對網絡測量技術的基本要求： 有效性 高速鋇4 量 準確性 實時性 1 有效性：就是低丌銷，是網絡測量中研究的重要問題，因為要滿足業務級、 應用級管理的現代網管系統( n m s ) 對網絡參數的需求，網絡測量過程需 要相當大的數據量和相當高的數據采集頻率連續不斷地監測網絡狀態及 變遷，例如，每隔1 5 分鐘，以免漏掉相關變化、應用行為或業務可靠性的 衰退變化1 5 】。所以，在網絡大范圍內進行經常性的數據采集、通信、匯總， 必然引起大量的網絡資源耗費。這意味著，收集網絡帶寬利用率信息時減 少對下層網絡的影響是網絡測量方法的基本要求【6 】。 2 高速測量：隨著鏈路傳輸速率的快速增長以及i n t e r n e t 用戶和流量的大 量增長，測量技術也必須滿足高速測量的要求。 3 準確性：對網絡控制的粒度越來越來細比如包級別、流級別的控制，而且 網絡流量的可預測性低，需要測量的數據盡量準確。 4 實時性：因為要對網絡資源進行實時的調度、控制，要求測量也能及時監 測到網絡的狀態變化。 1 2 選題背景 i p 鏈路帶寬利用率是指在一段時間內i p 層的吞吐量占總吞吐能力的比重， 鏈路時延就是鏈路對數據包傳輸、傳播、排隊等待的總延遲。鏈路時延和帶寬利 用率是i p 網絡進行監測和控制的兩個基本參數，通常兩者對于不同類型的應用 表現的重要性不相同，實時性業務對時延比較敏感，而大數據量型業務對帶寬利 用率敏感。但對于網絡的一些精細控制，需要同時獲取這兩個參數，比如很多 q o s 路由選擇算法將網絡多條路徑的時延和帶寬利用率作為輸入。而且，同時獲 取鏈路時延和帶寬利用率信息，可以更加細致的把握網絡內部狀態，因為同時獲 取兩個參數信息可以將兩者在同一個時間軸上分析，能夠發現網絡中隱藏的問 題，比如出現帶寬利用率低但是時延較大的異常情況時，網絡管理者可以據此進 一步調查。在全網范圍以最低開銷、及時、準確獲取這兩個參數，對于合理規劃 利用網絡資源、平衡網絡流量、動態服務器路由、服務等級( s l a ) 確認、錯誤 2 重慶郵電z 院碩十論文 ，7 故障定位檢測等有非常重要的作用1 7 】j ，因此研究高速i p 網絡的帶寬利用率和 時延測量，對于網絡管理和控制及網絡發展具有重要的意義。e h u ，時延和帶寬 利用率的測量使用的方法明顯不同，較細粒度的帶寬利用率依靠被動監測技術， 而時延測量需要通過主動探測包。所以要想同時獲耿這兩個參數，需要研究有效 的網絡測量模型，在模型中合理運用主動和被動測量技術。另外，有效的網絡測 量模型對于降低網絡測量開銷，以及確保網絡測量的其他要求具有關鍵性作用。 論文選題是以重慶市科技攻關項目“高速i p 網絡測量系統”為基礎，主要 研究內容包括： 網絡的有效測量模型研究 流量信息采集技術的研究 1 3 論文主要工作 1 主要研究內容和貢獻 ( 1 ) 從i p 網絡測量的必要性全網測量的基本要求出發，討論和分析了現有 的測量模型存在的開銷大、不能同時獲得時延和帶寬信息、信息采集影響節點轉 發性能等問題。本文提出_ 種新的全網測量模型線卡采集代理模型，綜合運 用了被動監測和主動探測兩者的優點，能夠同時測量時延和帶寬利用率。系統用 于帶寬利用率測量和時延測量的資源可在更深程度上共享，從而進一步降低了測 量開銷。 ( 2 ) 證明了最小混和覆蓋問題是n p 一難的，并提出兩個有利于最小化開銷的 貪心近似算法，仿真驗證了算法的有效性。 ( 3 ) 作為模型的實現技術基礎，本文提出了線卡采集技術，基于f p g a 實現 了線卡采集模塊的硬件功能仿真，進行了模塊級功能測試，結果顯示功能與性能 達到了設計要求。 ( 4 ) 對整個模型系統進行了仿真測試，結果說明文中模型是可行的。 2 主要創新點 ( 1 ) 在現有測量模型的基礎上，綜合了頂點覆蓋和邊覆蓋的優點，巧妙應用 了被動監測和主動探測技術，提出的測量模型能夠同時測量時延和利用率這兩個 不同的參數。 ( 2 ) 針對本文測量模型映射成的兩個特定n p - 難問題，深入挖掘了其相互關 聯因素，提出兩個具有關聯因素的貪心算法，使得最終的算法結果優于直接使用 兩個無關聯的貪心算法結果，為解決這種具有關聯關系的n p 一難問題提供了一種 思路。 ( 3 ) 針對現有網絡監測技術在高速網絡環境下不能線速統計、影響所在節點 轉發性能、無法滿足大量實時任務對統計結果的實時查詢需要等問題，提出的線 3 重慶郵叱學院碩十論文 卡采集技術對于網管任務或應用中所需的最普遍、最基本的那些統計任務用 f p g a ( 現場可編程門陣列) 實現，可快速、準確、及時地統計，不會對數據包轉 發性能造成任何負面影響，符合未來路由器技術的發展趨勢，也可作為傳統測量 方法信息采集技術的有效補充。基于f p g a 實現，代價小，易于現場升級，增加 了采集功能的靈活性。 3 論文安排 論文按下面章節組織： 第1 章：緒論，簡單介紹i p 網絡測量的必要性，對網絡測量方法的一些要求 指出論文工作就是為了滿足這些要求所做的努力。 第2 章：研究現狀與分析，詳細介紹和分析了現有模型和信息采集技術，提 出可能存在的諸多問題，指明論文工作努力的方向。 第3 章：基于線卡采集代理的有效網絡測量模型與算法仿真，論述模型結 構，證明模型的難點歸結為兩個n p - 難問題，提出近似算法并給出仿真結果， 結果驗證算法是有效的。并簡要介紹了測量模型系統的主要方面。 第4 章：線卡采集器的f p g a 實現，詳細描述線卡采集器的功能模塊結構， 以及每一個模塊的具體實現和仿真測試。 第5 章：測量模型功能的o p n e t 仿真，在o p n e t 中搭建真實網絡的模擬環境， 通過修改路由器節點模型，使其具備線卡采集器功能，讓一些節點行使監 測代理功能，最終驗證了測量模型的可行性。 第6 章是論文的總結與下一步工作的展望。 一4 重慶郵電學院碩1 論文 第二章研究現狀與分析 2 1 概述 眾所周知，s n m p r m o n l 9 】是i p 網絡廣泛使用的管理監視機制。網絡管理中 心不僅僅關心網絡上單個節點的狀態和行為，也關心網絡本身的流量。遠程監視 r m o n 是指為了網絡管理，通過網絡上的一個節點( 通常是網絡運行中心n o c ) 來監視整個網絡。在s n m p 環境中，已經定義了r m 卟m i b 。r m o nm i b 規定了遠程 監視器要采集和存儲的信息，該規范中也定義了監視器的功能以及管理站監視器 的相互作用功能。為了監視全網，需要在網絡中每個節點設置監視器，n o c 和各 監視器通過輪詢( p o l l i n g ) 或事件報告( e v e n tr e p o r t i n g ) 將監視信息匯集在 n o c 。這種在每個節點設置監視器的方法雖然直觀，但有個致命的缺陷是開銷太 大，在實際網絡環境中無法使用，不僅是s n m p r m o n 機制如此，其他測量機制也 遇到了類似的開銷問題，這些開銷包括： 設置在節點的監視器軟硬件成本、設備維護的昂貴的人力成本 信息匯集的通信成本，主要是占用的鏈路帶寬資源 監視器采集、存儲信息時對所在節點處理器資源的耗費，會嚴重影響節點 的處理速度或吞吐量，從而使節點成為新的網絡瓶頸 為了降低i p 網絡測量開銷，人們積極研究： i 一方面研究有效的測量模型，使得設置在網絡中的監視器最少，精心設計 信息匯集的通信路徑與通信時刻，使得通信成本最低，當然有效的測量模 型并不局限于只為s n m p r m o n 機制服務，不同的測量機制可以有不同的測 量模型； 2 另一方面測量模型離不開有效的信息采集技術的支撐，研究有效的信息采 集技術，目的是占用所在節點最少的處理器資源，從而不對節點的轉發性 能造成負面影響。 同時，從i p 網絡測量技術的基本要求得出，有效的測量模型和信息采集工 具需滿足以下約束條件： 覆蓋全網 結果準確 快速及時 本文從測量模型的開銷方面著手，在滿足上述約束條件下從l ，2 兩方面進 行了較深入研究。下面是目前有關的研究現狀和分析。 5 照慶郵l 乜學院碩十論文 2 2 有效測量模型研究現狀與分析 2 2 1 問題描述 定義1 給定無向圖g = ( v ，e ) ，其中v 是頂點集，e 是邊集，s 是v 的子集，若 根據與s 中頂點按特定關系相關的各條邊的參數，可以確定e 中任意邊的參數， 則稱s 是圖g 的基于頂點的測量集。 定義2 給定無向圖g = ( v ，e ) ，其中v 是頂點集，e 是邊集，s 是v 的子集，a 是從s 中頂點發射的探測包集，若通過a 得到與s 按特定關系相關的各條邊的參 數，可以確定e 中任意邊的參數，則稱a 是圖g 基于邊的測量集。 有效測量模型問題的目標是求給定圖g = ( v ，e ) 關于流量和時延的最小頂點測 量集或最小邊測量集。 2 2 2 現有測量模型概述 目前，有效的網絡測量模型主要思想是將網絡利用最小測量集覆蓋，并且設 計一種使測量集相互合作的機制，利用資源共享使測量開銷進一步最小化，從而 避免對運營網絡的共享資源引起不適當的損傷。在網絡中智能化設置測量集通常 是一些圖論里的難題，類似于設備放置問題( f l a ) 中心設置問題( c p ) 、集合覆 蓋問題( s c ) 、頂點覆蓋問題( v c ) ，這些都是著名的n p 一難問題。同時在i p 網 中，利用路由器、交換機或者路由路徑等條件，還可以挖掘出其他約束條件，比 如，非葉子結點的流守恒方程、路由路徑樹覆蓋鏈路，使得找到最小測量集( 近 似) 成為可能。根據測量集覆蓋網絡方式的不同，有效測量可分為基于頂點覆蓋 ( v c ) 、基于邊覆蓋( e c ) 、或混合覆蓋( m c ) 。 基于頂點覆蓋( v c ) 的測量集 頂點覆蓋( v c ) 是指圖g = ( v ，e ) 中v 的子集s 互v ，對任意e e ，e 至少有 一個端點屬予s 。基于v c 的測量集是網絡圖的一個頂點覆蓋的子集，利用面向 結點的采集工具統計網絡參數信息。難點是找到個最小的頂點測量集。雖然采 用求解最小頂點覆蓋問題的算法可以求出一個頂點測量集，但已證明，最小頂點 覆蓋問題是個n p 一難問題，尚無多項式時間的求解算法，并且求出的測量集也 未必是最小頂點測量集。這是因為，在實際網絡環境中測量集往往滿足一些特定 的約束條件，如果加以合理利用可以有效減d , n 量集。例如下面所述的弱頂點覆 蓋。 ，6 重慶郵也學院碩十論文 v v j ( b ) 圖2 i ( a ) 圈g 的一個昂小頂點覆蓋v cs = v l ，v 2 ，v 3 ，v 4 。( b ) 有向圖6 的一個攝小弱頂點 覆蓋集w v cs = v l ，v 2 弱頂點覆蓋( w e a kv e r t e xc o v e rw v c ) 1 0 1 是網絡流量測量方法的最新成 果。假定無向圖g = ( v ，e ) 滿足對任意1 ，礦有d e g r e e ( v ) 2 2 ，稱s c 礦是圖g 的若 頂點覆蓋集，當且僅當執行以下操作能使e 中所有邊可以被標記：( 1 ) 標記所有 與s 中頂點相關聯的邊。( 2 ) 若某個頂點v 的d e g r e e ( v ) 一1 條相關聯的邊已被標 記，則標記剩下的那條相關聯的邊。( 3 ) 重復第( 2 ) 步直到不能再標記新的邊 為止。w v c 基于非葉子節點流守恒原理，且依托廣泛使用的面向結點的測量技術 s n m p r m o n 代理，或n e t f o w 。結點的流守恒原理是流入結點的流量等于流出結 點的流量。當然流守恒只是近似，若考慮結點丟包、組播等因素時，流入結點跟 流出結點的流量并不總是相同，在當前的網絡環境下相差低于0 0 5 6 】。將來網 絡中媒體流的組播應用大量增加時，流守恒偏差可能加大。流守恒原理的具體應 用：假如一個路由器結點有k 條鏈路相連，當已知其中的k l 條鏈路的流量時， 則剩下的第k 條鏈路的流量根據流守恒原理也可以得到。如圖2 1 所示，( b ) 中 只需在v i 和v 2 點設置監測工具，就可以得到網絡圖中所有邊上的流量。這個方 案的關鍵問題是找到最小頂點測量集，也就是尋找最小弱頂點覆蓋集，是n p 一難 問題，目前只能用近似算法求解。用類似于解決f l a 問題的貪心算法解w v c 問題， 如下所示。 w e a kv e r t e xc o v e ra g o r it h m ( g r a p hg ) 1 )u = g 2 )i = l 3 )g = g 4 ) w h i l e ( 6 的頂點集非空) 5 ) 選取圖g = ( ，e ) 中度最大的頂點v 6 ) l = u + v ) 7 ) v7 = k 一 一 - 7 - 一 醛一 。、一甾 亞慶郵電。院碩十論文 8 ) e = e a d j ( v ) 9 )j = i + l 1 0 ) 對圖g = ( 礦7 ，e 7 ) 反復刪除度不超過1 的所有頂點及其相關聯 的邊，直到不能再刪除新的頂點和邊為止。令6 為最后得到的圈) 返回集合u ) w v c 方法可以使用目前廣泛應用的監測工具如s n m p r m o 、代理，或 n e t f l o w 】，特別是n e t f l o w 工具可以基于流粒度的統計，測得的流量數據應用 范圍更廣，比如：基于使用的用戶計費，服務等級約定( s l a ) 確認等。但是， 監測工具對所在結點轉發性能的負面影響無法消除，而且，w v c 的算法通常選擇 度較大的結點【6 1 0 】，流過結點的流量通常較大，所以監測工具必須以很高的速率 統計流量數據，加重了結點處理資源負擔，很可能使此結點成為新的網絡瓶頸， 例如圖2 卜( b ) 的v 1 ，v 2 。s a m p l e dn e t f l o w 【i 2 j 和a g g r e g a t e dn e t f l o w 叫可以減 少一部分影響，然而在全網測量的實際應用中依然存在較大的問題【i 4 1 。 基于邊覆蓋( e c ) 測量集 邊覆蓋( e c ) 是指探測包集經過的邊集包含圖g 的所有邊。基于c 的測量 集是向網絡發射的探測包集，探測包沿路徑集流過網絡，利用面向路徑的監測技 術獲得網絡參數。這種方法的關鍵步驟是對給定路徑集配置最小探測包集，有兩 方面的含義，第一是探測包數最少，第二是探測包占用的鏈路總代價最小，例如， 探測包經過的鏈路總數最少。尋找最小探測包集也是n p 一難問題，通常考慮探測 包共用來減少探測包數，讓探測包沿最短路徑轉發來減少對鏈路資源的占用。探 測包共用思想如圖2 2 所示，測量路徑集p = p i ，p 2 ，p 3 的探測包集可以有多種 不同的選擇，例如：( a ) ，( b ) 。其中，( b ) 考慮了探測包共用，明顯減少了探測 包集的大小。接下來，關鍵問題是設計一個算法：尋找一個能夠準確測量給定路 徑集的最小探測包集，最小探測包集施加給網絡的附加流量最小。可以證明這個 問題能夠在多項式時間內映射成著名的n p 一難問題：設備位置問題( f l p ) i s l 1 6 i 。 可用啟發式算法在多項式時間內求得對數因子的近似解，如下所示。 v o ( a ) 3 圖2 2 測量路徑p 】，p 2 ，p 3 朐探測包集 8 一 v 0 ( b ) 3 重慶郵電學院碩十論文 a 1 9 0 rj t h mo p t i m a l p r o b e s ( g ，p ，k ) i n p u t ：g ( v ，e ) = 網絡圖。 p = 待測路徑集。 v _ 給定錨點集。 o u t p u t ：a ，= 對于圪和p 的一個最優探測包集。 1 ) a 。2 ： 2 ) f o re a c hp pd o 3 ) 令v ，屹，u f ( p ，) ，1 ( 只) ) ，使得i 舅6 m 最小，f ( 只) ，1 ( 只) 分 別為只的第一個和最后一個端點哆，。為v ，到h 的最短路徑，v o 到_ 的最短路徑為 ，( v 0 是網絡圖的一個探測包發射頂點) ： 4 ) 以2 以，u ，巧，。只) ： 其中圪求法如下：令c 為待測路徑p 的集合，j 為k 的可選錨點集。對于j j 的固定成本為v 0 到v ，的最短路徑長i ，| ，則屹為j 的一個滿足 m i n ，；， 。l 乒l + 2 2 。m i n 州，( ，州圳 l 局l + l t ，。l 的子集f j 。令對圪的探 測包集為也，則4u4 ，為最后所求的最小測量集。 v n 測量位于其路由路徑以外的鏈路時需要得到源路由的支持，但在實際網絡 環境中，源路由選項常常得不到支持，因為i s p 或a s 由于安全原因，不允許使 用源路由選項。人們也提出了別的方法，將v c 和e c 結合起來使用，就是下匭描 述的基于混合覆蓋( m c ) 模型。 基于混合覆蓋( i c ) 測量集 基于混合覆蓋( m c ) 測量集是指綜合了v c 和e c 的特點，先確定個最小頂 點測量集，然后在頂點測量集的基礎上確定最小邊測量集。例如在網絡圖頂點廣 泛設置監測代理【8 】【1 7 】【1 8 j 【1 9 ，監測代理使用探測包收集網絡參數信息。比較而言， m c 的優點是比較靈活，可以組合利用被動測量和主動測量的優點。m c 的缺點是 模型比較復雜。m c 問題通常也是n p 一難的。 減少測量開銷的其他方法 除了上述主要測量模型外，還有另外一些方法可以減少測量開銷。文獻 2 0 9 一 重慶郵i u 學院碩十論文 提出：用基于組播的方法測得的一組m 絡路徑端到端時延作為已知量，將更小的 路徑段時延作為未知量，通過解一個線性方程組來計算更小的路徑段的時延。文 獻 2 1 研究了檢測閥值警戒的方法來減少監測時的通信開銷。分布式輪詢引擎 ( 例如 2 2 ) 、關于“批處理”s n m p 一輪詢消息的提議1 2 3 1 、更有效的s n m p 一輪詢策 略i 2 4 j 等工作也是為了減少使用s n m p 代理測量開銷。 2 2 3 有效測量模型總結 上面描述了不同類型的測量模型，v c 適合流量監測，e c 更適合于時延測量。 v c 的模型簡單，但是需要在網絡中廣泛設置測量代理，設備費用、維護、人工 費用高，而且可能會影響所在結點設備的性能。e c 模型不需在網絡中設置測量 設備，但需要網絡中間設備某種形式的參與合作，比如i c m pe c h o ，發送的探測 流量需要精心計算，若不加控制會給網絡帶來額外的開銷。m c 融合兩者之長， 更加靈活。 這些模型存在的主要問題是： 網絡的有效測量模型依賴于現有的信息采集機制，機制本身的缺陷比如， 測量速度、測量開銷等問題，在網絡測量時并不會改善和消除，特別是信 息采集對網絡節點轉發性能有時會產生較大影響。 目前帶寬利用率和時延的獲取分別使用了不同的模型機制，沒有一種模型 能夠既得到時延信息，又獲得帶寬利用率信息。實際中，兩者都是相當重 要的，要同時獲得這兩個參數必須啟動兩套系統。這樣一來，兩個系統之 間資源便無法共享，比如，探測包共享或探測路徑共享，所以，與使用了 資源共享比較，相當于對下層網絡施加了更多的測量開銷，也不利于測量 系統的維護以及測量結果的分析和使用。 本文針對這些問題在兩方面進行了深入研究，一方面是信息采集技術，另一 方面是測量模型。關于測量模型，我們提出了一種混和覆蓋( m c ) 模型，綜合了 v c 和e c 的優點，能夠充分利用被動監測和主動監測技術的優勢，將時延和利用 率兩個完全不同的度量同時在一個模型中獲得。關于信息采集技術，在下面進行 詳細描述。 2 3 信息采集技術現狀與分析 2 3 1 現有采集技術概述 被動監測技術 被動監測是在網絡中的特定點收集流量信息，如：s n m p r m o n 探測或c j s c o 1 0 重慶郵電學院碩士論文 n e t f l o w 工具，它們面向結點，從網絡設備( 路由器、交換機、主機) 上收集 監測信息，也有的是一個獨立的設備，面向鏈路，被動地監測網絡鏈路的流量， 如o c x m o n 。這些工具可以用來收集統計信息和計費信啟、測量單獨網絡設備的 性能( 例如，鏈路帶寬使用) 。無論如何，除非在每個設備或鏈路上安裝監測工具， 否則，這些工具無法監測涉及多個部分的網絡參數，像多條鏈路或路徑流量。基 于軟件的測量技術，先天決定測量速度很難適應測量高速網絡環境下帶寬，而且， 要占用所在路由器的處理器資源，有些技術嚴重影響路由器吞吐量( 例如， s n m p r m o x 代理會影響所在路由器的吞吐量，嚴重時使所在路由器吞吐量減少 l j 一2 0 l 6 】) 。所以抽樣測量、流量聚合也是監測技術的熱點之一，如s a m p l e d n e t f l o w 旺 和a g g r e g a t e dn e t f l o w d 3 i ，對節點減少了一部分影響。現有的基于硬 件實現的技術如o c x - m o n l ”】，需要專門的硬件( 例如，d a g 卡、g p s 天線、分光器) 和獨立監測工作站【2 ，通常用來離線式( o f f 一1 i n e ) 的i n t e r n e t 流量特征分析和 建模，不利于在全網廣泛布置和維護這些高成本的設備，難以達到及時收集全網 參數的目的。 主動監測技術 成熟的主動監測工具有：p i n g ，t f a c e r o u t e r 2 ，s k i t t e r 28 1 ，t c p p i n g f 2 9 】。 這些測量技術屬于主動測量的范疇，測量過程中產生新的網絡流量，這些注入網 絡的新的流量是為了引起網絡部件的特殊響應( 如：t r a c e t o u t e r ) ，至少要多個 網絡內部部件某種形式的參與。要完成主動式的測量要求網絡內部各元素廣泛的 合作如，i c m pe c h o 請求應答響應，然而，常常為了安全等因素使這種合作不可 得，例如，常用的i c m p 請求應答機制會導致d o s ( d e n i a lo fs e r v i c e ) 攻擊，所 以i s p 或a s 經常會拒絕合作，t c p p i n 9 1 2 9 】就是對付這種問題的一種方法。另外， 主動式的測量給網絡增加了額外的載荷，這些附加的流量若不仔細控制，會擾亂 網絡，產生h e i s e n b e r g 效應，歪曲網絡分析結果1 3 0 。這一點體現了有效的網絡 測量模型研究的必要性，因為有效的測量模型的目的正是為了使網絡附加的測量 流量最小化。 也正是因為主動時延測量向網絡注入了流量，這些流量穿越了網絡內部，切 身“感受”了網絡內部性能，所以精心設計的注入流量反映出來的時延可以間接 推斷網絡內部參數，這也是主動帶寬測量技術基本思想。 總的說來，帶寬測量比較困難【3 ”，特別是在高速網絡環境下準確測量帶寬更 加困難。主動帶寬測量技術簡單的說是利用時延推斷帶寬，已經出現了大量的成 果，諸如n e t t i m e r 3 ”、p a t h c h a r 3 2 1 、c p r o b e 3 3 】、p a t h r a t e 3 剞、p t v s 3 5 】等。這些 工具的基本思想是通過精一山安排注入網絡的信息包，包括包的數目、包之間的間 隔、包的大小等，然后依據包返回的信息利用統計推斷方法估計網絡路徑的帶寬 信息，這些帶寬信息，有的是路徑瓶頸帶寬，有的是鏈路容量，有的是有效帶寬， 照慶郵電學院碩 論文 或者他們之中的幾個f 3 4 j 1 3 6 j 。這些技術同時也是面向路徑的，簡單、靈活，不需 要在網絡中進行特別的設鷺，特別適合于網絡用戶或網絡研究人員用來分析指定 網絡路徑的流量行為。所以成為目| j 帶寬測量研究的熱點之一，但畢竟是對網絡 帶寬的估計，偏差不可避免存在，特別是對高速網絡測量時( 例如，超過5 0 0 m b s ) 精確度仍有待提高p 。而且測量時向網絡注入的探測包數相對太多( 為了精確測 量帶寬，源端需要發送一系列的探測包，比本身時延測量引起的額外流量多很多 倍) ，限制了其應用范圍。目前還沒有發現被用來全網帶寬監測。 2 3 2 采集技術總結 從全網測量的角度來看，與主動測量相比較，被動測量工具本身在統計流最 數據時完全沒有附加流量和h e i s e n b e r g 效應，這些優點使人們更愿意使用被動 帶寬測量技術進行全網測量。但目前的被動監測技術存在缺陷： 對所在節點線速轉發性能影響較大 統計速度跟不上鏈路傳輸速率的增長速度 從上面的分析可以看出，在高速網絡環境下，不論是被動監測技術還是主動 探測技術都遇到了極大挑戰，現有技術各有其優缺點。從全網帶寬利用率( 流量) 測量的角度來看，被動監測仍然是目前必須依賴的技術，但必須滿足兩點要求， 點是不會對所在節點的數據包轉發性能產生負面影響，另一點是能夠進行線速 統計。我們針對這些問題提出了線卡采集器技術，基于硬件實現，不會對節點轉 發造成任何負面影響，而且能對網絡數據( 數據包數，字節數，簡單的流) 進行 快速準確的統計。 2 3 3 線卡采集器 隨著傳輸技術的迅速發展，鏈路傳輸速率快速增長，從o c - 3 ( 1 5 5m b s ) 到 o c 1 9 2 ( 1 0o b s 1 ，甚至o c 7 6 8 ( 4 0o b s ) ，相應地，路由器也需要能夠快速處理。 另一方面，路由器為了保證0 0 s 需要完成的功能也在不斷增加，如四層路由 ( l e v e l - 4r o u t i n g ) 、防火墻、m p l s 、d i i t s e r v 、基于流調度等功能”“，路由器已 逐漸成為限制網絡速率的瓶頸。基于電子技術的路由器將接近其性能極限，全光 路由器中光數據包的緩存、光包頭的讀寫等難題尚未很好解決，人們依賴于電路 由器的體系結構的改進來提高數據包處理速度。目前，高端路由器大多采用線卡 轉發引擎加高速交換結構來實現1 3 8 】。為提高轉發速率，引擎通常使用a s i c 來設 計，而且發展趨勢是在硬件中提供更多的功能口9 1 。關于這一點有其技術方面的深 層次的原因：c m o s ( 互補金屬氧化物半導體) 在更新換代上滿足1 8 2 4 月翻一 番的m o o r 定律，但這只局限于晶體管密度。考慮到全局布線因素，交換芯片的 1 2 弧慶郵l 也學院碩十論文 時鐘速率每一代僅能增加5 - 1 0 所以運行其上的軟件處理速率增加有限，而且 由于高速路由器線卡功耗、空間、健壯性等的要求，限制了線卡上網絡處理器 ( n p ) 的個數，故依靠多個處理器并行來提高軟件速率、增加功能的想法不太 實際“。所以利用芯片卜越來越多的品體管實現更多的功能成為路由器設計的長 遠發展趨勢。 為了監視下一代極高速鏈路的流量，i e t f 工作組也有人提出了用專用硬件 結合流量壓縮與采樣技術完成對o c 7 6 8 的監測，同時，也認為部分功能可能嵌 入路由器線卡硬件中1 4 0 。 本文針對目前i p 網絡監測技術的不足，提出了線卡采集器，在包分類的部 分模塊基礎上增加一些功能來實現，能夠快速準確的實現數據包的統計 ( p a c k e t s s 、b y t e s s ) 、簡單的流統計( p a c k e t s c l a s s 、b y t e s c l a s s ) ，作為現有測量 方法的補充機制。主要特點是用硬件實現，幾乎不會對節點處理資源造成影響， 同時，實現線速統計，不會丟失信息，也符合路由器設計的發展趨勢。而且，能 夠實時響應探測包的對統計信息的查詢，可以為一些需要及時獲取網絡信息的業 務和應用提供測量支持，比如將測量結果作為q o s 路由算法的輸入，為動態服 務器選擇提供依據等。本文對線卡采集器的實現是基于f p g a ( 現場可編程門陣 列) ，用f p g a 實現難度低，成本小，能夠進行現場升級，增加了硬件實現功能 的靈活性，從而能滿足更大范圍的應用需求。 1 3 重慶郵電學院碩十論文 第三章基于線卡采集代理的有效測量模型 3 1 概述 本文工作的目標是針對大型i s p 網絡或a s 確定有效的測量模型，在準確、 及時測量的基礎上最大程度的減d , n 量開銷： 給定鏈路( 子) 集合的帶寬利用率( 流量) 測量。通過統計段時間內 鏈路上承載的載荷或者流量值，與這段時問鏈路所能承受的最大載荷之比，就是 鏈路的帶寬利用率。通常固定鏈路的最大載荷是定值，可以通過查詢網絡配胃的 鏈路標稱速率( 或其他形式的速率) 得到，帶寬利用率隨鏈路載荷或流量值變化， 所以等價于鏈路流量值的統計。很明