（通信與信息系統(tǒng)專業(yè)論文）ip網(wǎng)絡(luò)鏈路時延和帶寬利用率的有效測量模型研究.pdf

重慶郵l 乜學(xué)院碩1 ：論文 摘要 及時、準確獲取網(wǎng)絡(luò)內(nèi)部各條鏈路的時延和帶寬利用率信息，以便實時、充 分了解網(wǎng)絡(luò)的狀態(tài)，是資源管理、擁塞控制、多路徑路由等網(wǎng)絡(luò)管理與控制手段 的關(guān)鍵之。高速i p 網(wǎng)絡(luò)要求測量方法滿足快速、及時、準確和低開銷的特點。 目前針對時延和帶寬利用率的測量分別采用了不同的測量模型架構(gòu)，要想同 時獲得鏈路時延或利用率信息，必須啟動兩套測量系統(tǒng)，這樣既增加了測量開銷， 也不利于測量系統(tǒng)的維護和測量結(jié)果的進一步分析和使用。而且，現(xiàn)有的時延測 量模型存在測量精度差、安全性差等問題，影響了其在實際網(wǎng)絡(luò)中的實用性。而 帶寬利用率測量模型通?；趕 n m p r m o n 機制，或基于類似n e t f l o w 的機制，加 重了路由器的處理負擔，影響路由器的轉(zhuǎn)發(fā)性能。 本文提出一種可以同時獲取網(wǎng)絡(luò)內(nèi)部鏈路的時延和帶寬利用率的測量模型， 稱為線卡采集代理模型。通過設(shè)置于網(wǎng)絡(luò)節(jié)點接口上的線卡采集器實時監(jiān)測并統(tǒng) 計鏈路上的流量，由預(yù)先設(shè)置好的線卡采集代理點集合發(fā)來的探測包將統(tǒng)計信息 帶回代理點，同時，通過計算發(fā)往同一條鏈路兩個端點的探測包的往返時間差得 到該鏈路時延，各代理點將匯總后的結(jié)果向網(wǎng)絡(luò)監(jiān)測中心( n o c ) 報告，由n o c 進 一步得到全網(wǎng)監(jiān)測結(jié)果。該模型以項點覆蓋和邊覆蓋的相關(guān)理論為基礎(chǔ)，證明了 以最小代價混合覆蓋全網(wǎng)的問題是n p 一難的，并提出新的貪心近似算法，仿真結(jié) 果驗證了算法的有效性。 作為模型的實現(xiàn)技術(shù)基礎(chǔ)，本文提出的線卡采集技術(shù)便于硬件實現(xiàn)，符合未 來路由器技術(shù)的發(fā)展趨勢，也可作為傳統(tǒng)測量方法信息采集技術(shù)的有效補充?；?于f p g a 實現(xiàn)了線卡采集模塊的硬件功能仿真，進行了模塊級功能測試，結(jié)果顯 示功能與性能達到了設(shè)計要求。最后，對整個模型系統(tǒng)進行了仿真測試，結(jié)果說 明文中模型是可行的。 關(guān)鍵詞：測量模型，時延，帶寬利用率，n p 一難，貪心算法，f p g a 重慶郵電學(xué)院碩十論文 一一 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 獨創(chuàng)性聲明 本人聲明所呈交的學(xué)位論文是本人在導(dǎo)師指導(dǎo)下進行的研究工 作及取得的研究成果。據(jù)我所知，除了文中特別加以標注和致謝的地 方外，論文中不包含其他人已經(jīng)發(fā)表或撰寫過的研究成果，也不包含 為獲得重迭鰹電堂瞳或其他教育機構(gòu)的學(xué)位或證書而使用過的材 料。與我一同工作的同志對本研究所做的任何貢獻均已在論文中作了 明確的說明并表示謝意。 學(xué)位論文作者簽名：幕愛躑 簽字日期：妒爭年細哆日 學(xué)位論文版權(quán)使用授權(quán)書 本學(xué)位論文作者完全了解重廢整皇堂瞳有關(guān)保留、使用學(xué) 位論文的規(guī)定，有權(quán)保留并向國家有關(guān)部門或機構(gòu)送交論文的復(fù)印件 和磁盤，允許論文被查閱和借閱。本人授權(quán)重龐由g 電堂瞳可以 將學(xué)位論文的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫進行檢索，可以采用影 印、縮印或掃描等復(fù)制手段保存、匯編學(xué)位論文。 ( 保密的學(xué)位論文在解密后適用本授權(quán)書) 學(xué)位論文作者簽名：融螂 簽字日期：f ；f 年籮月乃e t ， 導(dǎo)師簽名：7 妻紅 簽字日期：似f f 年f 月巧e l 重慶郵電。學(xué)院碩士論文 1 1 引言 第一章緒論 1 1 1 對i p 網(wǎng)絡(luò)測量的必要性 未來，i p 網(wǎng)絡(luò)是否能夠繼續(xù)取得巨大的成功，關(guān)鍵之一是看其能否提供令用 戶滿意的服務(wù)質(zhì)量( o o s ) ，通常需要保證o o s 的應(yīng)用以低時延、低時延抖動的實 時應(yīng)用為主。但是，i p 網(wǎng)絡(luò)在本質(zhì)上只提供“盡力而為服務(wù)”，無法滿足諸如v o i p 、 實時媒體等應(yīng)用的o o s 要求。因而迫使網(wǎng)絡(luò)服務(wù)提供商( i s p ) 改善網(wǎng)絡(luò)設(shè)備性 能，增加傳輸帶寬，如使用更先進的交換機實現(xiàn)業(yè)務(wù)處理，采用高帶寬的光纖介 質(zhì)滿足高速數(shù)據(jù)傳輸?shù)男枰猨 。這樣增加基礎(chǔ)設(shè)施的辦法，雖然能在一定程度上 緩減用戶數(shù)據(jù)傳輸帶寬和o o s 保證的壓力，但同時也使i p 骨干網(wǎng)絡(luò)鏈路平均利 用率愈來愈低。產(chǎn)生這種現(xiàn)象的原因主要是i n t e r n e t 流量極端不對稱，網(wǎng)絡(luò)流 量的分布極不平衡及其增長難于預(yù)測，而快速的傳輸技術(shù)的出現(xiàn)使大量增加鏈路 容量在經(jīng)濟上可行，造成鏈路帶寬的過量供應(yīng)【2 j 。另外，今天的運營商缺乏對網(wǎng) 絡(luò)內(nèi)部鏈路贄源利用率情況的了解，也是造成鏈路帶寬過量供應(yīng)的原因之一。因 為如果不知道網(wǎng)絡(luò)內(nèi)部資源利用的情況，就無法量化提供q o s 與資源過量供應(yīng)的 對比成本，運營商不得不采用寧多勿少地增加帶寬的策略，靠進一步降低鏈路利 用率來滿足低時延的應(yīng)用需求【3 】。因此，當今天的運營商面對出于故障、擁塞引 起的網(wǎng)絡(luò)震蕩、不穩(wěn)定進一步加劇擁塞，嚴重影響網(wǎng)絡(luò)性能問題時，依靠帶寬過 量供應(yīng)，保持網(wǎng)絡(luò)的低利用率解決這類問題【4 l 。這樣與傳統(tǒng)基于時分復(fù)用的電信 網(wǎng)絡(luò)比較，大量的鏈路資源閑餐，使得基于統(tǒng)計復(fù)用的i p 網(wǎng)絡(luò)高效的資源利用 率的優(yōu)越性無從體現(xiàn)j 。 然而，僅僅依靠鏈路帶寬過量供應(yīng)，降低鏈路平均利用率并不能避免嚴重擁 塞和網(wǎng)絡(luò)資源利用率的進一步下降【4 】，也就必然不能令用戶滿意，因為用戶不僅 需要低時延，還需要低的時延抖動，要求網(wǎng)絡(luò)利用率的低變化率1 2 】。因此迫切需 要大型i s p 和自治系統(tǒng)( a s ) 具有可行的控制網(wǎng)絡(luò)資源、優(yōu)化網(wǎng)絡(luò)性能的管理和 監(jiān)控機制。及時獲取網(wǎng)絡(luò)內(nèi)部備條鏈路的時延和帶寬利用率信息，以便實時。充 分了解網(wǎng)絡(luò)內(nèi)部的狀態(tài)，是資源管理、擁塞控制、多路徑路由等控制手段的關(guān)鍵 之。 而網(wǎng)絡(luò)內(nèi)部的動態(tài)信息只能通過測量的手段來獲得( w i h i a m s o nc 和 p a x s o nv ) 。同時，高速i p 網(wǎng)絡(luò)要求測量方法滿足快速、及時、準確和低開銷 要求。a c ms i g c o m m 從2 0 0 j 年開始連續(xù)舉辦了三屆網(wǎng)絡(luò)測量工作組會議，專門 重慶郵電學(xué)院碩十論文 討論測量模型、體系、工具等問題，以期對動態(tài)路由調(diào)整和靈活的網(wǎng)絡(luò)控制能力 提供測量支持。 1 1 2i p 網(wǎng)絡(luò)測量技術(shù)應(yīng)該滿足的基本要求 i p 網(wǎng)絡(luò)對網(wǎng)絡(luò)測量技術(shù)的基本要求： 有效性 高速鋇4 量 準確性 實時性 1 有效性：就是低丌銷，是網(wǎng)絡(luò)測量中研究的重要問題，因為要滿足業(yè)務(wù)級、 應(yīng)用級管理的現(xiàn)代網(wǎng)管系統(tǒng)( n m s ) 對網(wǎng)絡(luò)參數(shù)的需求，網(wǎng)絡(luò)測量過程需 要相當大的數(shù)據(jù)量和相當高的數(shù)據(jù)采集頻率連續(xù)不斷地監(jiān)測網(wǎng)絡(luò)狀態(tài)及 變遷，例如，每隔1 5 分鐘，以免漏掉相關(guān)變化、應(yīng)用行為或業(yè)務(wù)可靠性的 衰退變化1 5 】。所以，在網(wǎng)絡(luò)大范圍內(nèi)進行經(jīng)常性的數(shù)據(jù)采集、通信、匯總， 必然引起大量的網(wǎng)絡(luò)資源耗費。這意味著，收集網(wǎng)絡(luò)帶寬利用率信息時減 少對下層網(wǎng)絡(luò)的影響是網(wǎng)絡(luò)測量方法的基本要求【6 】。 2 高速測量：隨著鏈路傳輸速率的快速增長以及i n t e r n e t 用戶和流量的大 量增長，測量技術(shù)也必須滿足高速測量的要求。 3 準確性：對網(wǎng)絡(luò)控制的粒度越來越來細比如包級別、流級別的控制，而且 網(wǎng)絡(luò)流量的可預(yù)測性低，需要測量的數(shù)據(jù)盡量準確。 4 實時性：因為要對網(wǎng)絡(luò)資源進行實時的調(diào)度、控制，要求測量也能及時監(jiān) 測到網(wǎng)絡(luò)的狀態(tài)變化。 1 2 選題背景 i p 鏈路帶寬利用率是指在一段時間內(nèi)i p 層的吞吐量占總吞吐能力的比重， 鏈路時延就是鏈路對數(shù)據(jù)包傳輸、傳播、排隊等待的總延遲。鏈路時延和帶寬利 用率是i p 網(wǎng)絡(luò)進行監(jiān)測和控制的兩個基本參數(shù)，通常兩者對于不同類型的應(yīng)用 表現(xiàn)的重要性不相同，實時性業(yè)務(wù)對時延比較敏感，而大數(shù)據(jù)量型業(yè)務(wù)對帶寬利 用率敏感。但對于網(wǎng)絡(luò)的一些精細控制，需要同時獲取這兩個參數(shù)，比如很多 q o s 路由選擇算法將網(wǎng)絡(luò)多條路徑的時延和帶寬利用率作為輸入。而且，同時獲 取鏈路時延和帶寬利用率信息，可以更加細致的把握網(wǎng)絡(luò)內(nèi)部狀態(tài)，因為同時獲 取兩個參數(shù)信息可以將兩者在同一個時間軸上分析，能夠發(fā)現(xiàn)網(wǎng)絡(luò)中隱藏的問 題，比如出現(xiàn)帶寬利用率低但是時延較大的異常情況時，網(wǎng)絡(luò)管理者可以據(jù)此進 一步調(diào)查。在全網(wǎng)范圍以最低開銷、及時、準確獲取這兩個參數(shù)，對于合理規(guī)劃 利用網(wǎng)絡(luò)資源、平衡網(wǎng)絡(luò)流量、動態(tài)服務(wù)器路由、服務(wù)等級( s l a ) 確認、錯誤 2 重慶郵電z 院碩十論文 ，7 故障定位檢測等有非常重要的作用1 7 】j ，因此研究高速i p 網(wǎng)絡(luò)的帶寬利用率和 時延測量，對于網(wǎng)絡(luò)管理和控制及網(wǎng)絡(luò)發(fā)展具有重要的意義。e h u ，時延和帶寬 利用率的測量使用的方法明顯不同，較細粒度的帶寬利用率依靠被動監(jiān)測技術(shù)， 而時延測量需要通過主動探測包。所以要想同時獲耿這兩個參數(shù)，需要研究有效 的網(wǎng)絡(luò)測量模型，在模型中合理運用主動和被動測量技術(shù)。另外，有效的網(wǎng)絡(luò)測 量模型對于降低網(wǎng)絡(luò)測量開銷，以及確保網(wǎng)絡(luò)測量的其他要求具有關(guān)鍵性作用。 論文選題是以重慶市科技攻關(guān)項目“高速i p 網(wǎng)絡(luò)測量系統(tǒng)”為基礎(chǔ)，主要 研究內(nèi)容包括： 網(wǎng)絡(luò)的有效測量模型研究 流量信息采集技術(shù)的研究 1 3 論文主要工作 1 主要研究內(nèi)容和貢獻 ( 1 ) 從i p 網(wǎng)絡(luò)測量的必要性全網(wǎng)測量的基本要求出發(fā)，討論和分析了現(xiàn)有 的測量模型存在的開銷大、不能同時獲得時延和帶寬信息、信息采集影響節(jié)點轉(zhuǎn) 發(fā)性能等問題。本文提出_ 種新的全網(wǎng)測量模型線卡采集代理模型，綜合運 用了被動監(jiān)測和主動探測兩者的優(yōu)點，能夠同時測量時延和帶寬利用率。系統(tǒng)用 于帶寬利用率測量和時延測量的資源可在更深程度上共享，從而進一步降低了測 量開銷。 ( 2 ) 證明了最小混和覆蓋問題是n p 一難的，并提出兩個有利于最小化開銷的 貪心近似算法，仿真驗證了算法的有效性。 ( 3 ) 作為模型的實現(xiàn)技術(shù)基礎(chǔ)，本文提出了線卡采集技術(shù)，基于f p g a 實現(xiàn) 了線卡采集模塊的硬件功能仿真，進行了模塊級功能測試，結(jié)果顯示功能與性能 達到了設(shè)計要求。 ( 4 ) 對整個模型系統(tǒng)進行了仿真測試，結(jié)果說明文中模型是可行的。 2 主要創(chuàng)新點 ( 1 ) 在現(xiàn)有測量模型的基礎(chǔ)上，綜合了頂點覆蓋和邊覆蓋的優(yōu)點，巧妙應(yīng)用 了被動監(jiān)測和主動探測技術(shù)，提出的測量模型能夠同時測量時延和利用率這兩個 不同的參數(shù)。 ( 2 ) 針對本文測量模型映射成的兩個特定n p - 難問題，深入挖掘了其相互關(guān) 聯(lián)因素，提出兩個具有關(guān)聯(lián)因素的貪心算法，使得最終的算法結(jié)果優(yōu)于直接使用 兩個無關(guān)聯(lián)的貪心算法結(jié)果，為解決這種具有關(guān)聯(lián)關(guān)系的n p 一難問題提供了一種 思路。 ( 3 ) 針對現(xiàn)有網(wǎng)絡(luò)監(jiān)測技術(shù)在高速網(wǎng)絡(luò)環(huán)境下不能線速統(tǒng)計、影響所在節(jié)點 轉(zhuǎn)發(fā)性能、無法滿足大量實時任務(wù)對統(tǒng)計結(jié)果的實時查詢需要等問題，提出的線 3 重慶郵叱學(xué)院碩十論文 卡采集技術(shù)對于網(wǎng)管任務(wù)或應(yīng)用中所需的最普遍、最基本的那些統(tǒng)計任務(wù)用 f p g a ( 現(xiàn)場可編程門陣列) 實現(xiàn)，可快速、準確、及時地統(tǒng)計，不會對數(shù)據(jù)包轉(zhuǎn) 發(fā)性能造成任何負面影響，符合未來路由器技術(shù)的發(fā)展趨勢，也可作為傳統(tǒng)測量 方法信息采集技術(shù)的有效補充?；趂 p g a 實現(xiàn)，代價小，易于現(xiàn)場升級，增加 了采集功能的靈活性。 3 論文安排 論文按下面章節(jié)組織： 第1 章：緒論，簡單介紹i p 網(wǎng)絡(luò)測量的必要性，對網(wǎng)絡(luò)測量方法的一些要求 指出論文工作就是為了滿足這些要求所做的努力。 第2 章：研究現(xiàn)狀與分析，詳細介紹和分析了現(xiàn)有模型和信息采集技術(shù)，提 出可能存在的諸多問題，指明論文工作努力的方向。 第3 章：基于線卡采集代理的有效網(wǎng)絡(luò)測量模型與算法仿真，論述模型結(jié) 構(gòu)，證明模型的難點歸結(jié)為兩個n p - 難問題，提出近似算法并給出仿真結(jié)果， 結(jié)果驗證算法是有效的。并簡要介紹了測量模型系統(tǒng)的主要方面。 第4 章：線卡采集器的f p g a 實現(xiàn)，詳細描述線卡采集器的功能模塊結(jié)構(gòu)， 以及每一個模塊的具體實現(xiàn)和仿真測試。 第5 章：測量模型功能的o p n e t 仿真，在o p n e t 中搭建真實網(wǎng)絡(luò)的模擬環(huán)境， 通過修改路由器節(jié)點模型，使其具備線卡采集器功能，讓一些節(jié)點行使監(jiān) 測代理功能，最終驗證了測量模型的可行性。 第6 章是論文的總結(jié)與下一步工作的展望。 一4 重慶郵電學(xué)院碩1 論文 第二章研究現(xiàn)狀與分析 2 1 概述 眾所周知，s n m p r m o n l 9 】是i p 網(wǎng)絡(luò)廣泛使用的管理監(jiān)視機制。網(wǎng)絡(luò)管理中 心不僅僅關(guān)心網(wǎng)絡(luò)上單個節(jié)點的狀態(tài)和行為，也關(guān)心網(wǎng)絡(luò)本身的流量。遠程監(jiān)視 r m o n 是指為了網(wǎng)絡(luò)管理，通過網(wǎng)絡(luò)上的一個節(jié)點( 通常是網(wǎng)絡(luò)運行中心n o c ) 來監(jiān)視整個網(wǎng)絡(luò)。在s n m p 環(huán)境中，已經(jīng)定義了r m 卟m i b 。r m o nm i b 規(guī)定了遠程 監(jiān)視器要采集和存儲的信息，該規(guī)范中也定義了監(jiān)視器的功能以及管理站監(jiān)視器 的相互作用功能。為了監(jiān)視全網(wǎng)，需要在網(wǎng)絡(luò)中每個節(jié)點設(shè)置監(jiān)視器，n o c 和各 監(jiān)視器通過輪詢( p o l l i n g ) 或事件報告( e v e n tr e p o r t i n g ) 將監(jiān)視信息匯集在 n o c 。這種在每個節(jié)點設(shè)置監(jiān)視器的方法雖然直觀，但有個致命的缺陷是開銷太 大，在實際網(wǎng)絡(luò)環(huán)境中無法使用，不僅是s n m p r m o n 機制如此，其他測量機制也 遇到了類似的開銷問題，這些開銷包括： 設(shè)置在節(jié)點的監(jiān)視器軟硬件成本、設(shè)備維護的昂貴的人力成本 信息匯集的通信成本，主要是占用的鏈路帶寬資源 監(jiān)視器采集、存儲信息時對所在節(jié)點處理器資源的耗費，會嚴重影響節(jié)點 的處理速度或吞吐量，從而使節(jié)點成為新的網(wǎng)絡(luò)瓶頸 為了降低i p 網(wǎng)絡(luò)測量開銷，人們積極研究： i 一方面研究有效的測量模型，使得設(shè)置在網(wǎng)絡(luò)中的監(jiān)視器最少，精心設(shè)計 信息匯集的通信路徑與通信時刻，使得通信成本最低，當然有效的測量模 型并不局限于只為s n m p r m o n 機制服務(wù)，不同的測量機制可以有不同的測 量模型； 2 另一方面測量模型離不開有效的信息采集技術(shù)的支撐，研究有效的信息采 集技術(shù)，目的是占用所在節(jié)點最少的處理器資源，從而不對節(jié)點的轉(zhuǎn)發(fā)性 能造成負面影響。 同時，從i p 網(wǎng)絡(luò)測量技術(shù)的基本要求得出，有效的測量模型和信息采集工 具需滿足以下約束條件： 覆蓋全網(wǎng) 結(jié)果準確 快速及時 本文從測量模型的開銷方面著手，在滿足上述約束條件下從l ，2 兩方面進 行了較深入研究。下面是目前有關(guān)的研究現(xiàn)狀和分析。 5 照慶郵l 乜學(xué)院碩十論文 2 2 有效測量模型研究現(xiàn)狀與分析 2 2 1 問題描述 定義1 給定無向圖g = ( v ，e ) ，其中v 是頂點集，e 是邊集，s 是v 的子集，若 根據(jù)與s 中頂點按特定關(guān)系相關(guān)的各條邊的參數(shù)，可以確定e 中任意邊的參數(shù)， 則稱s 是圖g 的基于頂點的測量集。 定義2 給定無向圖g = ( v ，e ) ，其中v 是頂點集，e 是邊集，s 是v 的子集，a 是從s 中頂點發(fā)射的探測包集，若通過a 得到與s 按特定關(guān)系相關(guān)的各條邊的參 數(shù)，可以確定e 中任意邊的參數(shù)，則稱a 是圖g 基于邊的測量集。 有效測量模型問題的目標是求給定圖g = ( v ，e ) 關(guān)于流量和時延的最小頂點測 量集或最小邊測量集。 2 2 2 現(xiàn)有測量模型概述 目前，有效的網(wǎng)絡(luò)測量模型主要思想是將網(wǎng)絡(luò)利用最小測量集覆蓋，并且設(shè) 計一種使測量集相互合作的機制，利用資源共享使測量開銷進一步最小化，從而 避免對運營網(wǎng)絡(luò)的共享資源引起不適當?shù)膿p傷。在網(wǎng)絡(luò)中智能化設(shè)置測量集通常 是一些圖論里的難題，類似于設(shè)備放置問題( f l a ) 中心設(shè)置問題( c p ) 、集合覆 蓋問題( s c ) 、頂點覆蓋問題( v c ) ，這些都是著名的n p 一難問題。同時在i p 網(wǎng) 中，利用路由器、交換機或者路由路徑等條件，還可以挖掘出其他約束條件，比 如，非葉子結(jié)點的流守恒方程、路由路徑樹覆蓋鏈路，使得找到最小測量集( 近 似) 成為可能。根據(jù)測量集覆蓋網(wǎng)絡(luò)方式的不同，有效測量可分為基于頂點覆蓋 ( v c ) 、基于邊覆蓋( e c ) 、或混合覆蓋( m c ) 。 基于頂點覆蓋( v c ) 的測量集 頂點覆蓋( v c ) 是指圖g = ( v ，e ) 中v 的子集s 互v ，對任意e e ，e 至少有 一個端點屬予s 。基于v c 的測量集是網(wǎng)絡(luò)圖的一個頂點覆蓋的子集，利用面向 結(jié)點的采集工具統(tǒng)計網(wǎng)絡(luò)參數(shù)信息。難點是找到個最小的頂點測量集。雖然采 用求解最小頂點覆蓋問題的算法可以求出一個頂點測量集，但已證明，最小頂點 覆蓋問題是個n p 一難問題，尚無多項式時間的求解算法，并且求出的測量集也 未必是最小頂點測量集。這是因為，在實際網(wǎng)絡(luò)環(huán)境中測量集往往滿足一些特定 的約束條件，如果加以合理利用可以有效減d , n 量集。例如下面所述的弱頂點覆 蓋。 ，6 重慶郵也學(xué)院碩十論文 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 是網(wǎng)絡(luò)流量測量方法的最新成 果。假定無向圖g = ( v ，e ) 滿足對任意1 ，礦有d e g r e e ( v ) 2 2 ，稱s c 礦是圖g 的若 頂點覆蓋集，當且僅當執(zhí)行以下操作能使e 中所有邊可以被標記：( 1 ) 標記所有 與s 中頂點相關(guān)聯(lián)的邊。( 2 ) 若某個頂點v 的d e g r e e ( v ) 一1 條相關(guān)聯(lián)的邊已被標 記，則標記剩下的那條相關(guān)聯(lián)的邊。( 3 ) 重復(fù)第( 2 ) 步直到不能再標記新的邊 為止。w v c 基于非葉子節(jié)點流守恒原理，且依托廣泛使用的面向結(jié)點的測量技術(shù) s n m p r m o n 代理，或n e t f o w 。結(jié)點的流守恒原理是流入結(jié)點的流量等于流出結(jié) 點的流量。當然流守恒只是近似，若考慮結(jié)點丟包、組播等因素時，流入結(jié)點跟 流出結(jié)點的流量并不總是相同，在當前的網(wǎng)絡(luò)環(huán)境下相差低于0 0 5 6 】。將來網(wǎng) 絡(luò)中媒體流的組播應(yīng)用大量增加時，流守恒偏差可能加大。流守恒原理的具體應(yīng) 用：假如一個路由器結(jié)點有k 條鏈路相連，當已知其中的k l 條鏈路的流量時， 則剩下的第k 條鏈路的流量根據(jù)流守恒原理也可以得到。如圖2 1 所示，( b ) 中 只需在v i 和v 2 點設(shè)置監(jiān)測工具，就可以得到網(wǎng)絡(luò)圖中所有邊上的流量。這個方 案的關(guān)鍵問題是找到最小頂點測量集，也就是尋找最小弱頂點覆蓋集，是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 ) 反復(fù)刪除度不超過1 的所有頂點及其相關(guān)聯(lián) 的邊，直到不能再刪除新的頂點和邊為止。令6 為最后得到的圈) 返回集合u ) w v c 方法可以使用目前廣泛應(yīng)用的監(jiān)測工具如s n m p r m o 、代理，或 n e t f l o w 】，特別是n e t f l o w 工具可以基于流粒度的統(tǒng)計，測得的流量數(shù)據(jù)應(yīng)用 范圍更廣，比如：基于使用的用戶計費，服務(wù)等級約定( s l a ) 確認等。但是， 監(jiān)測工具對所在結(jié)點轉(zhuǎn)發(fā)性能的負面影響無法消除，而且，w v c 的算法通常選擇 度較大的結(jié)點【6 1 0 】，流過結(jié)點的流量通常較大，所以監(jiān)測工具必須以很高的速率 統(tǒng)計流量數(shù)據(jù)，加重了結(jié)點處理資源負擔，很可能使此結(jié)點成為新的網(wǎng)絡(luò)瓶頸， 例如圖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 叫可以減 少一部分影響，然而在全網(wǎng)測量的實際應(yīng)用中依然存在較大的問題【i 4 1 。 基于邊覆蓋( e c ) 測量集 邊覆蓋( e c ) 是指探測包集經(jīng)過的邊集包含圖g 的所有邊?；赾 的測量 集是向網(wǎng)絡(luò)發(fā)射的探測包集，探測包沿路徑集流過網(wǎng)絡(luò)，利用面向路徑的監(jiān)測技 術(shù)獲得網(wǎng)絡(luò)參數(shù)。這種方法的關(guān)鍵步驟是對給定路徑集配置最小探測包集，有兩 方面的含義，第一是探測包數(shù)最少，第二是探測包占用的鏈路總代價最小，例如， 探測包經(jīng)過的鏈路總數(shù)最少。尋找最小探測包集也是n p 一難問題，通?？紤]探測 包共用來減少探測包數(shù)，讓探測包沿最短路徑轉(zhuǎn)發(fā)來減少對鏈路資源的占用。探 測包共用思想如圖2 2 所示，測量路徑集p = p i ，p 2 ，p 3 的探測包集可以有多種 不同的選擇，例如：( a ) ，( b ) 。其中，( b ) 考慮了探測包共用，明顯減少了探測 包集的大小。接下來，關(guān)鍵問題是設(shè)計一個算法：尋找一個能夠準確測量給定路 徑集的最小探測包集，最小探測包集施加給網(wǎng)絡(luò)的附加流量最小。可以證明這個 問題能夠在多項式時間內(nèi)映射成著名的n p 一難問題：設(shè)備位置問題( f l p ) i s l 1 6 i 。 可用啟發(fā)式算法在多項式時間內(nèi)求得對數(shù)因子的近似解，如下所示。 v o ( a ) 3 圖2 2 測量路徑p 】，p 2 ，p 3 朐探測包集 8 一 v 0 ( b ) 3 重慶郵電學(xué)院碩十論文 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 ) = 網(wǎng)絡(luò)圖。 p = 待測路徑集。 v _ 給定錨點集。 o u t p u t ：a ，= 對于圪和p 的一個最優(yōu)探測包集。 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 是網(wǎng)絡(luò)圖的一個探測包發(fā)射頂點) ： 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 測量位于其路由路徑以外的鏈路時需要得到源路由的支持，但在實際網(wǎng)絡(luò) 環(huán)境中，源路由選項常常得不到支持，因為i s p 或a s 由于安全原因，不允許使 用源路由選項。人們也提出了別的方法，將v c 和e c 結(jié)合起來使用，就是下匭描 述的基于混合覆蓋( m c ) 模型。 基于混合覆蓋( i c ) 測量集 基于混合覆蓋( m c ) 測量集是指綜合了v c 和e c 的特點，先確定個最小頂 點測量集，然后在頂點測量集的基礎(chǔ)上確定最小邊測量集。例如在網(wǎng)絡(luò)圖頂點廣 泛設(shè)置監(jiān)測代理【8 】【1 7 】【1 8 j 【1 9 ，監(jiān)測代理使用探測包收集網(wǎng)絡(luò)參數(shù)信息。比較而言， m c 的優(yōu)點是比較靈活，可以組合利用被動測量和主動測量的優(yōu)點。m c 的缺點是 模型比較復(fù)雜。m c 問題通常也是n p 一難的。 減少測量開銷的其他方法 除了上述主要測量模型外，還有另外一些方法可以減少測量開銷。文獻 2 0 9 一 重慶郵i u 學(xué)院碩十論文 提出：用基于組播的方法測得的一組m 絡(luò)路徑端到端時延作為已知量，將更小的 路徑段時延作為未知量，通過解一個線性方程組來計算更小的路徑段的時延。文 獻 2 1 研究了檢測閥值警戒的方法來減少監(jiān)測時的通信開銷。分布式輪詢引擎 ( 例如 2 2 ) 、關(guān)于“批處理”s n m p 一輪詢消息的提議1 2 3 1 、更有效的s n m p 一輪詢策 略i 2 4 j 等工作也是為了減少使用s n m p 代理測量開銷。 2 2 3 有效測量模型總結(jié) 上面描述了不同類型的測量模型，v c 適合流量監(jiān)測，e c 更適合于時延測量。 v c 的模型簡單，但是需要在網(wǎng)絡(luò)中廣泛設(shè)置測量代理，設(shè)備費用、維護、人工 費用高，而且可能會影響所在結(jié)點設(shè)備的性能。e c 模型不需在網(wǎng)絡(luò)中設(shè)置測量 設(shè)備，但需要網(wǎng)絡(luò)中間設(shè)備某種形式的參與合作，比如i c m pe c h o ，發(fā)送的探測 流量需要精心計算，若不加控制會給網(wǎng)絡(luò)帶來額外的開銷。m c 融合兩者之長， 更加靈活。 這些模型存在的主要問題是： 網(wǎng)絡(luò)的有效測量模型依賴于現(xiàn)有的信息采集機制，機制本身的缺陷比如， 測量速度、測量開銷等問題，在網(wǎng)絡(luò)測量時并不會改善和消除，特別是信 息采集對網(wǎng)絡(luò)節(jié)點轉(zhuǎn)發(fā)性能有時會產(chǎn)生較大影響。 目前帶寬利用率和時延的獲取分別使用了不同的模型機制，沒有一種模型 能夠既得到時延信息，又獲得帶寬利用率信息。實際中，兩者都是相當重 要的，要同時獲得這兩個參數(shù)必須啟動兩套系統(tǒng)。這樣一來，兩個系統(tǒng)之 間資源便無法共享，比如，探測包共享或探測路徑共享，所以，與使用了 資源共享比較，相當于對下層網(wǎng)絡(luò)施加了更多的測量開銷，也不利于測量 系統(tǒng)的維護以及測量結(jié)果的分析和使用。 本文針對這些問題在兩方面進行了深入研究，一方面是信息采集技術(shù)，另一 方面是測量模型。關(guān)于測量模型，我們提出了一種混和覆蓋( m c ) 模型，綜合了 v c 和e c 的優(yōu)點，能夠充分利用被動監(jiān)測和主動監(jiān)測技術(shù)的優(yōu)勢，將時延和利用 率兩個完全不同的度量同時在一個模型中獲得。關(guān)于信息采集技術(shù)，在下面進行 詳細描述。 2 3 信息采集技術(shù)現(xiàn)狀與分析 2 3 1 現(xiàn)有采集技術(shù)概述 被動監(jiān)測技術(shù) 被動監(jiān)測是在網(wǎng)絡(luò)中的特定點收集流量信息，如：s n m p r m o n 探測或c j s c o 1 0 重慶郵電學(xué)院碩士論文 n e t f l o w 工具，它們面向結(jié)點，從網(wǎng)絡(luò)設(shè)備( 路由器、交換機、主機) 上收集 監(jiān)測信息，也有的是一個獨立的設(shè)備，面向鏈路，被動地監(jiān)測網(wǎng)絡(luò)鏈路的流量， 如o c x m o n 。這些工具可以用來收集統(tǒng)計信息和計費信啟、測量單獨網(wǎng)絡(luò)設(shè)備的 性能( 例如，鏈路帶寬使用) 。無論如何，除非在每個設(shè)備或鏈路上安裝監(jiān)測工具， 否則，這些工具無法監(jiān)測涉及多個部分的網(wǎng)絡(luò)參數(shù)，像多條鏈路或路徑流量。基 于軟件的測量技術(shù)，先天決定測量速度很難適應(yīng)測量高速網(wǎng)絡(luò)環(huán)境下帶寬，而且， 要占用所在路由器的處理器資源，有些技術(shù)嚴重影響路由器吞吐量( 例如， s n m p r m o x 代理會影響所在路由器的吞吐量，嚴重時使所在路由器吞吐量減少 l j 一2 0 l 6 】) 。所以抽樣測量、流量聚合也是監(jiān)測技術(shù)的熱點之一，如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 ，對節(jié)點減少了一部分影響?，F(xiàn)有的基于硬 件實現(xiàn)的技術(shù)如o c x - m o n l ”】，需要專門的硬件( 例如，d a g 卡、g p s 天線、分光器) 和獨立監(jiān)測工作站【2 ，通常用來離線式( o f f 一1 i n e ) 的i n t e r n e t 流量特征分析和 建模，不利于在全網(wǎng)廣泛布置和維護這些高成本的設(shè)備，難以達到及時收集全網(wǎng) 參數(shù)的目的。 主動監(jiān)測技術(shù) 成熟的主動監(jiān)測工具有：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 】。 這些測量技術(shù)屬于主動測量的范疇，測量過程中產(chǎn)生新的網(wǎng)絡(luò)流量，這些注入網(wǎng) 絡(luò)的新的流量是為了引起網(wǎng)絡(luò)部件的特殊響應(yīng)( 如：t r a c e t o u t e r ) ，至少要多個 網(wǎng)絡(luò)內(nèi)部部件某種形式的參與。要完成主動式的測量要求網(wǎng)絡(luò)內(nèi)部各元素廣泛的 合作如，i c m pe c h o 請求應(yīng)答響應(yīng)，然而，常常為了安全等因素使這種合作不可 得，例如，常用的i c m p 請求應(yīng)答機制會導(dǎo)致d o s ( d e n i a lo fs e r v i c e ) 攻擊，所 以i s p 或a s 經(jīng)常會拒絕合作，t c p p i n 9 1 2 9 】就是對付這種問題的一種方法。另外， 主動式的測量給網(wǎng)絡(luò)增加了額外的載荷，這些附加的流量若不仔細控制，會擾亂 網(wǎng)絡(luò)，產(chǎn)生h e i s e n b e r g 效應(yīng)，歪曲網(wǎng)絡(luò)分析結(jié)果1 3 0 。這一點體現(xiàn)了有效的網(wǎng)絡(luò) 測量模型研究的必要性，因為有效的測量模型的目的正是為了使網(wǎng)絡(luò)附加的測量 流量最小化。 也正是因為主動時延測量向網(wǎng)絡(luò)注入了流量，這些流量穿越了網(wǎng)絡(luò)內(nèi)部，切 身“感受”了網(wǎng)絡(luò)內(nèi)部性能，所以精心設(shè)計的注入流量反映出來的時延可以間接 推斷網(wǎng)絡(luò)內(nèi)部參數(shù)，這也是主動帶寬測量技術(shù)基本思想。 總的說來，帶寬測量比較困難【3 ”，特別是在高速網(wǎng)絡(luò)環(huán)境下準確測量帶寬更 加困難。主動帶寬測量技術(shù)簡單的說是利用時延推斷帶寬，已經(jīng)出現(xiàn)了大量的成 果，諸如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 】等。這些 工具的基本思想是通過精一山安排注入網(wǎng)絡(luò)的信息包，包括包的數(shù)目、包之間的間 隔、包的大小等，然后依據(jù)包返回的信息利用統(tǒng)計推斷方法估計網(wǎng)絡(luò)路徑的帶寬 信息，這些帶寬信息，有的是路徑瓶頸帶寬，有的是鏈路容量，有的是有效帶寬， 照慶郵電學(xué)院碩 論文 或者他們之中的幾個f 3 4 j 1 3 6 j 。這些技術(shù)同時也是面向路徑的，簡單、靈活，不需 要在網(wǎng)絡(luò)中進行特別的設(shè)鷺，特別適合于網(wǎng)絡(luò)用戶或網(wǎng)絡(luò)研究人員用來分析指定 網(wǎng)絡(luò)路徑的流量行為。所以成為目| j 帶寬測量研究的熱點之一，但畢竟是對網(wǎng)絡(luò) 帶寬的估計，偏差不可避免存在，特別是對高速網(wǎng)絡(luò)測量時( 例如，超過5 0 0 m b s ) 精確度仍有待提高p 。而且測量時向網(wǎng)絡(luò)注入的探測包數(shù)相對太多( 為了精確測 量帶寬，源端需要發(fā)送一系列的探測包，比本身時延測量引起的額外流量多很多 倍) ，限制了其應(yīng)用范圍。目前還沒有發(fā)現(xiàn)被用來全網(wǎng)帶寬監(jiān)測。 2 3 2 采集技術(shù)總結(jié) 從全網(wǎng)測量的角度來看，與主動測量相比較，被動測量工具本身在統(tǒng)計流最 數(shù)據(jù)時完全沒有附加流量和h e i s e n b e r g 效應(yīng)，這些優(yōu)點使人們更愿意使用被動 帶寬測量技術(shù)進行全網(wǎng)測量。但目前的被動監(jiān)測技術(shù)存在缺陷： 對所在節(jié)點線速轉(zhuǎn)發(fā)性能影響較大 統(tǒng)計速度跟不上鏈路傳輸速率的增長速度 從上面的分析可以看出，在高速網(wǎng)絡(luò)環(huán)境下，不論是被動監(jiān)測技術(shù)還是主動 探測技術(shù)都遇到了極大挑戰(zhàn)，現(xiàn)有技術(shù)各有其優(yōu)缺點。從全網(wǎng)帶寬利用率( 流量) 測量的角度來看，被動監(jiān)測仍然是目前必須依賴的技術(shù)，但必須滿足兩點要求， 點是不會對所在節(jié)點的數(shù)據(jù)包轉(zhuǎn)發(fā)性能產(chǎn)生負面影響，另一點是能夠進行線速 統(tǒng)計。我們針對這些問題提出了線卡采集器技術(shù)，基于硬件實現(xiàn)，不會對節(jié)點轉(zhuǎn) 發(fā)造成任何負面影響，而且能對網(wǎng)絡(luò)數(shù)據(jù)( 數(shù)據(jù)包數(shù)，字節(jié)數(shù)，簡單的流) 進行 快速準確的統(tǒng)計。 2 3 3 線卡采集器 隨著傳輸技術(shù)的迅速發(fā)展，鏈路傳輸速率快速增長，從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 ) ，相應(yīng)地，路由器也需要能夠快速處理。 另一方面，路由器為了保證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 、基于流調(diào)度等功能”“，路由器已 逐漸成為限制網(wǎng)絡(luò)速率的瓶頸?；陔娮蛹夹g(shù)的路由器將接近其性能極限，全光 路由器中光數(shù)據(jù)包的緩存、光包頭的讀寫等難題尚未很好解決，人們依賴于電路 由器的體系結(jié)構(gòu)的改進來提高數(shù)據(jù)包處理速度。目前，高端路由器大多采用線卡 轉(zhuǎn)發(fā)引擎加高速交換結(jié)構(gòu)來實現(xiàn)1 3 8 】。為提高轉(zhuǎn)發(fā)速率，引擎通常使用a s i c 來設(shè) 計，而且發(fā)展趨勢是在硬件中提供更多的功能口9 1 。關(guān)于這一點有其技術(shù)方面的深 層次的原因：c m o s ( 互補金屬氧化物半導(dǎo)體) 在更新?lián)Q代上滿足1 8 2 4 月翻一 番的m o o r 定律，但這只局限于晶體管密度。考慮到全局布線因素，交換芯片的 1 2 弧慶郵l 也學(xué)院碩十論文 時鐘速率每一代僅能增加5 - 1 0 所以運行其上的軟件處理速率增加有限，而且 由于高速路由器線卡功耗、空間、健壯性等的要求，限制了線卡上網(wǎng)絡(luò)處理器 ( n p ) 的個數(shù)，故依靠多個處理器并行來提高軟件速率、增加功能的想法不太 實際“。所以利用芯片卜越來越多的品體管實現(xiàn)更多的功能成為路由器設(shè)計的長 遠發(fā)展趨勢。 為了監(jiān)視下一代極高速鏈路的流量，i e t f 工作組也有人提出了用專用硬件 結(jié)合流量壓縮與采樣技術(shù)完成對o c 7 6 8 的監(jiān)測，同時，也認為部分功能可能嵌 入路由器線卡硬件中1 4 0 。 本文針對目前i p 網(wǎng)絡(luò)監(jiān)測技術(shù)的不足，提出了線卡采集器，在包分類的部 分模塊基礎(chǔ)上增加一些功能來實現(xiàn)，能夠快速準確的實現(xiàn)數(shù)據(jù)包的統(tǒng)計 ( p a c k e t s s 、b y t e s s ) 、簡單的流統(tǒng)計( p a c k e t s c l a s s 、b y t e s c l a s s ) ，作為現(xiàn)有測量 方法的補充機制。主要特點是用硬件實現(xiàn)，幾乎不會對節(jié)點處理資源造成影響， 同時，實現(xiàn)線速統(tǒng)計，不會丟失信息，也符合路由器設(shè)計的發(fā)展趨勢。而且，能 夠?qū)崟r響應(yīng)探測包的對統(tǒng)計信息的查詢，可以為一些需要及時獲取網(wǎng)絡(luò)信息的業(yè) 務(wù)和應(yīng)用提供測量支持，比如將測量結(jié)果作為q o s 路由算法的輸入，為動態(tài)服 務(wù)器選擇提供依據(jù)等。本文對線卡采集器的實現(xiàn)是基于f p g a ( 現(xiàn)場可編程門陣 列) ，用f p g a 實現(xiàn)難度低，成本小，能夠進行現(xiàn)場升級，增加了硬件實現(xiàn)功能 的靈活性，從而能滿足更大范圍的應(yīng)用需求。 1 3 重慶郵電學(xué)院碩十論文 第三章基于線卡采集代理的有效測量模型 3 1 概述 本文工作的目標是針對大型i s p 網(wǎng)絡(luò)或a s 確定有效的測量模型，在準確、 及時測量的基礎(chǔ)上最大程度的減d , n 量開銷： 給定鏈路( 子) 集合的帶寬利用率( 流量) 測量。通過統(tǒng)計段時間內(nèi) 鏈路上承載的載荷或者流量值，與這段時問鏈路所能承受的最大載荷之比，就是 鏈路的帶寬利用率。通常固定鏈路的最大載荷是定值，可以通過查詢網(wǎng)絡(luò)配胃的 鏈路標稱速率( 或其他形式的速率) 得到，帶寬利用率隨鏈路載荷或流量值變化， 所以等價于鏈路流量值的統(tǒng)計。很明