摘要 a b s t r a c t t o d a y , t h er a p i dp r o g r e s so fn e t w o r k st e c h n o l o g y , t h ee x p a n s i o no fn e t w o r k s d i m e n s i o n s ，t h ed i v e r s i f i c a t i o no fs e r v i c ek i n d sa n dt h ei n c r e a s eo fs e r v i c eq u a n t i t y , a r ea l lt h es t a t u so fn e t w o r k s d e v e l o p m e n t w i t l lt h ed e v e l o p m e n t m a n yp r o b l e m s h a v ea p p e a r e d ，s u c ha st h eq u a n t i t yo fs e r v i c ei m b a l a n c ei nn e t w o r k s ，n og u a r a n t e e f o rq u a l i t yo f s e r v i c e ( q o s ) i n19 9 0 s ，i ti sn 棚ce n g i n e e r i n g i nn e t w o r k st or e s o l v e t h e s ep r o b l e m s i nt h e s et e ny e a r s t r a m ce n g i n e e r i n gq u i c k l yh a sb e c o m eah o t s p o t f o rm a n yi n t e r n e ts e r v i c ep r o v i d e ra n dn e t w o r k s s t u d yg r o u p w i t ht h e d e e p l ys t u d y i n g a n dt h e t e c h n o l o g y sc o n s u m m a t i n g t h e t r a f f i c e n g i n e e r i n gb a s e d0 1 1 t h em u l t i p r o t o c o ll a b e ls w i t c h i n gb e c o m e st h ep r i m a r ym o d e lf o rl a r g e i n t e m e ts e r v i c ep r o v i d e r sn e t w o r k s ，w h i c hi st h et h i r ds t y l eo fn e t w o r k st h a ti s f u l l ym a d eu po f r o u t e r s t h et r a f f i ce n g i n e e r i n gb a s e do nt h em u l t i - p r o t o c o ll a b e ls w i t c h i n gi n v o l v e sf o u r f u n c t i o n a l c o m p o n e n t s ：p a c k e t - f o r w a r d i n gm o d e l ，r o u t i n g s e l e c t i o n m o d e l ， i n f o r m a t i o nd i s t r i b u t i o nm o d e l ，a n ds i g n a l i n gm o d e l e a c hf u n c t i o n a lc o m p o n e n ti s i n d i v i d u a la n di nc o m p a c tc o l l a b o r a t i v er e l a t i o n sw i t l lt h eo t h e r s i nw h i c hr o u t i n g s e l e c t i o nm o d u l ei so n eo f t h em o s ti m p o r t a n to n e s b a s i n go n t h ea n a l y s i st ot h ed e v e l o p i n go f m u t i n gr e s e a r c h ，t h ep a p e r p r e s e n t sa n e ws t a t i ca l g o r i t b m m u m - m e a s u r e m e n tc o n f i g u r i n gl s p a l g o r i t h mb a s e d o nc o n s t r a i n t s ( m u l t i - m e a s u r e m e n ta l g o r i t h m ) t h ea l g o r i t h mc o n s i d e r sa l l k i n d so fc o n s t r a i n t s ，w h i c hi n c l u d et h er e q u i r e m e n to fq o s d u r i n gt h er o u t i n g ，t h e c o n s t r a i n t so fn e t w o r k s r e s o u r c e ，a d m i n i s t r a n ts t r a t e g ya n ds oo n t h e s ec o n s t r a i n t s a r es a t i s f i e di nd i f f e r e n tp h a s e sd u r i n gt h er u n n i n g f i r s t l y , t h ea l g o r i t h mm a k e sa u n i t e do b j e c tb y a n a l y s e st h en e t w o r k s r u n n i n g s t a t u sa n dr e s o u r c e s t a t u s f o l l o w i n g t h e s e ，t h ea l g o r i t h mf i n d st h ee x p l i c a b l er o u t i n g ，i nw h i c he a c hr e q u i r e m e n to fq o si n t r a f f i c e n g i n e e r i n gi s f u l f i l l e da n dt h er e s o u r c eo fn e t w o r k si s f u l l yu s e d s ot h e a l g o r i t h md e c r e a s e st h ep o s s i b i l i t yo ft h ec o n g e s t i o na n di n c r e a s e st h en e t w o r k s c a p a b i l i t y f i n a l l yt h ep a p e rp r o v e st h a tt h ea l g o r i t h mi sf e a s i b l ea n dp r e f e r a b l eb y t h e o r e t i c a ld e d u c t i o na n d c o m p u t e r s i m u l a t i o n 2 糖要 a sn o wt h er e s e a r c ho ft r a f f i ce n g i n e e r i n gj u s to nt h es t a r ts p o t ，s ot h i ss t a t i c r o u t i n ga l g o r i t h mb a s e do nt h en e t w o r k s s t a t u sc a l lb ee s s e n t i a l l yi m p o r t a n tt o t h e r e s e a r c ho ft r a f f i ce n g i n e e r i n g ，a n di tc a ni m p r o v et h es c i e n t i f i cr e s e a r c ha n dt h e n e t w o r k e c o n o m i cd e v e l o p m e n t k e y w o r d s i c o m m u n i c a t i o nn e t w o r k s ，m u l t i - p r o t o c o ll a b e ls w i t c h i n 刪p l s ，t r a f f i c e n g i n e e r i n g ，q u a l i t yo fs e r v i c e ，b a s e do nc o n s t r a i n t s ，m u l t i m e a s u r e m e n t ，s t a t i c r o u t i n ga l g o r i t h m 3 獨創(chuàng)性聲明 本人聲明所呈交的學位論文是本人在導師指導下進行的研究工作和取得的 研究成果，除了文中特別加以標注和致謝之處外，論文中不包含其他人已經發(fā)表 或撰寫過的研究成果，也不包含為獲得墨生盤鱟或其他教育機構的學位或證 書而使用過的材料。與我一同工作的同志對本研究所做的任何貢獻均已在論文中 作了明確的說明并表示了謝意。 學位論文作者簽名：才勿乓裂簽字日期：力加多年j 月跏日 學位論文版權使用授權書 本學位論文作者完全了解墨鲞盤堂有關保留、使用學位論文的規(guī)定。 特授權鑫洼盤堂可以將學位論文的全部或部分內容編入有關數據庫進行檢 索，并采用影印、縮印或掃描等復制手段保存、匯編以供查閱和借閱。同意學校 向國家有關部門或機構送交論文的復印件和磁盤。 ( 保密的學位論文在解密后適用本授權說明) 學位論文作者簽名：才多蓮型一 導師簽名： 弘韻耕 簽字日期：枷年7 月矽日簽字日期：2 一多年月，o 日 第一章緒論 第一章緒論 1 9 6 9 年世界第一個分組交換網a r p a r n e t 的問世標志著網絡時代的到來。 現在計算機網絡尤其是i n t e r n e t 的飛速發(fā)展已是有目共睹的，其應用領域已經涉 及技術、工程、應用等多方面，并對社會經濟、文化、以及人們的工作方式、生 活方式都有著深遠影響?？梢院敛豢鋸埖卣f，計算機網絡己成為人類文明發(fā)展的 強勁推動力。 第一節(jié)計算機網絡體系結構簡述 首先需要清楚什么是計算機網絡。計算機網絡是地理上分散的多臺獨立自主 的計算機遵循約定的通信協議，通過軟、硬件互連以實現交互通信、資源共享、 信息交換、協同工作以及在線處理等功能的系統(tǒng)吐 計算機網絡的發(fā)展使得電子郵件、w e b 服務器、消息討論組、網絡電話以及 電子商務等各種網絡應用不斷涌現，并推動著社會各行業(yè)的變革。 計算機網絡發(fā)展到現在經歷了三個階段：第一階段是電路交換，以傳統(tǒng)電信 網應用為代表；第二階段是分組交換，1 9 7 6 年國際電報電話咨詢委員會( c c i t t ) 制定了用于公用分組交換網的協議標準x 2 5 ：第三階段是以網絡協議一一 t c p i p ( t r a n s m i s s i o nc o n t r o lp r o t o c o l i n t e m e tp r o t o c o l ，傳輸控制協議i n t e r n e t 協議) 地出現為標志，t c p i p 協議的廣泛應用也正是計算機網絡迅速發(fā)展的重 要原因之一。 i n t e r n e t 是全球最大的、開放的、由眾多網絡互連而成的計算機網絡。i n t e m e t 的定義有狹義定義和廣義定義兩種【1 】： 1 狹義定義：由全球最大的、開放的、由眾多網絡互聯而成的計算機網絡中所 有采用i p 協議( i n t e m e t p r o t o c 0 1 ) 的網絡互連而成的網絡，即i p 網絡。 2 廣義定義：i p 網加上所有能通過路由選擇至目的節(jié)點的網絡，包括使用諸如 電子郵件這類應用層網關的網絡，各類存儲轉發(fā)的網絡以及采用非i p 協議 的網絡。 i n t e m e t 核心是開放，且貫穿在整個體系結構中，i n t e m e t 體系結構如圖1 1 所示： 1 第一章緒論 圖1 1i n t e m e t 體系結構 在i n t e m e t 體系結構的最低層是物理傳輸導管，i n t e m e t 可建立在任何物理傳 輸網之上，包括租線、撥號電話網、x 2 5 、i s d n 網、以太網、f d d i 網、a t m 網、高速的h i p p i 接口以及無線網、衛(wèi)星網等。 t c p i p 協議是實現互聯網絡連接性和互操作性的關鍵，它把成千上萬 i n t e m e t 上的各種網絡互聯起來。 在高層，t c p i p 協議為i n t e m e t 用戶提供了終端訪問和客戶服務器方式的服 務工具，諸如文件傳輸f t p 、虛擬終端t e l n e t 、電子郵件s m t p 等，用戶可以根 據需要利用這些服務工具。而為管理整個網絡，i n t e m e t 制定了簡單網絡管理協 議( s i m p l e n e t w o r k m a n a g e m e n t p r o t o c 0 1 s n m p ) 【2 1 。 從概念上講，一個t c p i p 互聯網提供 了三組服務。互聯網服務的三個概念及其相 互的依賴關系如圖1 2 所示。在最低層無連 接傳送服務為其它層的服務提供了基礎。在 第二層，一個可靠的傳送服務為應用層提供 了一個高層平臺。最高層是應用服務層。 應用服務 可靠的傳送服務 無連接分組傳送服務 圖1 2 互聯網服務的三概念層 i n t e m e t 軟件是圍繞著三個層次的概念化網絡服務設計的。最基本的互聯網 2 第一章緒論 服務是由一個分組傳送系統(tǒng)組成。該服務被定義為不可靠的、盡最大努力傳送的、 無連接分組傳送系統(tǒng)。所謂不可靠，指的是不能保證正確傳送，分組可能丟失、 重復、延遲或不按序傳送，而且服務不檢測這些情況，也不通知發(fā)送方和接受方。 這種不可靠的、無連接傳送機制稱為i n t e m e t 協議。i n t e r n e t 協議提供了三個 重要定義： 1 定義了在t c p i p 互聯網上的數據傳送的基本單元，規(guī)定了互聯網上傳送的 數據格式。 2 i n t e m e t 協議軟件完成路由選擇功能，選擇數據傳送的路徑。 3 i n t e m e t 協議包含了一組不可靠分組傳送的規(guī)則，指明了分組處理、差錯信 息發(fā)生以及分組丟失等的規(guī)則。 i e m 上所述，t c p i p 協議的廣泛應用真正的推動了i n t e m e t 網絡的發(fā)展。 t c p i p 的工作原理是分層結構如圖1 3 所示，它表示了兩臺主機上的應用程序 之間傳輸報文的過程。主機b 上的第n 層接收到的正是主機a 上的第n 層發(fā)送 出來的對象。 圖1 3 t c p i p 分層工作原理 第二節(jié)流量工程的提出 計算機網絡規(guī)模的急速膨脹無論從任何一個角度衡量，如主機的數量、 一3 第一章緒論 用戶數、業(yè)務量、鏈路數、單條鏈路的帶寬、或是服務提供商( i n t e r n e ts e r v i c e p r o v i d e r ，i s p ) 網絡的增長率，其增長速度都是驚人的。這種膨脹不可避免地帶 來了諸多問題： 現有的i n t e m e t 主干速率較低，尤其是各國的國際出口，更是顯得車水馬龍、 擁擠不堪； 現有的i n t e m e t 路由器工作方式( 依靠軟件進行選路和數據包轉發(fā)，速度難 以提高；隨著i n t e m e t 的急劇膨脹，選路信息處理工作量越來越大，路由表 越來越復雜，路由信息占用大量的帶寬等) 和吞吐量無法滿足i n t e r n e t 日益 增長的需求； 各i s p 之間和其內部網絡嚴重擁擠，忙時網絡擁塞和數據包丟失非常嚴重， 極大地影響網絡傳輸的效率； 現有i n t e m e t 沒有帶寬控制和流量控制功能，服務質量( q u a l i t y o fs e r v i c e ， q o s ) 難以得到保證。 因此，網絡服務提供商必須面對i n t e r n e t 如此爆炸性的發(fā)展以及發(fā)展中出現 的問題，同時也要面對來自橫向的激烈的競爭。更好地使他們的網絡滿足客戶日 益增長的需求，并使網絡穩(wěn)定、快速、高效地運行，并且具有靈活性和可擴展性， 以適應將來網絡發(fā)展的需求。這就要求i s p 必須有效地控制業(yè)務量在網絡中的分 配，從而合理利用現有的網絡資源，為客戶提供優(yōu)良的服務。 流量工程( t r a f f i ce n g i n e e r i n g ，t e ) 【2 】就是在這時期提出的一種用于解決 以上諸多問題的工具，它使i s p 能夠在現有的網絡資源條件下，在其路由域內對 流量的分布進行精確的控制：流量工程還可以在i s p 網絡內將業(yè)務流轉移到另一 條潛在的具有更小擁塞的物理路徑上去，從而平衡網絡中各種鏈路、路由器和交 換機上的負載，使其中任何一個組成部分都不會發(fā)生過載或者未充分利用。 i n t e r n e t 流量工程定義為i n t e m e t 網絡工程的一部分。處理i p 網絡操作中的 性能估價和性能優(yōu)化【2 】。流量工程的核心是流量控制和資源管理。t e 的性能指標 分為流量導向和資源導向兩方面。流量導向的性能決定網絡對流量的處理能力和 服務能力，主要日標包括最小分組丟失率，最小傳輸延遲，最大吞吐量。服務水 平約定等；資源導向針對的是優(yōu)化資源使用，目標是合理使用資源和優(yōu)化資源配 置，尤其希望避免網絡的一部分超負荷使用而另一部分未充分使用。帶寬是關鍵 4 一 第一章緒論 和緊缺的資源，流量工程的中心管理對象是帶寬。 現在，j u n i p e r 、c i s c o 等公司已經開始熱點研究新型的骨干網路由器以及在 以新型的骨干網路由器為核心的網絡中流量工程如何滿足q o s 需求、如何應用 的問題。這些路由器用硬件進行路由查詢和包轉發(fā)，實現了選路和包轉發(fā)的分離， 大大提高了路由器的轉發(fā)速率，使下一代i n t e r n e t 網絡的建立成為可能c 5 j 【7 j 。而 用流量工程作為工具則能夠優(yōu)化可用帶寬和網絡保留能力的需要：提供新的協 議、新的路由硬件、新的交換硬件和光纖設備：預留足夠空間和適當能源的后勤 工作，配置設備以適應鏈路可用性和用戶需要。因此是否能夠提供功能強大的流 量工程機制是每一個i s p 吸引用戶，在競爭中得到成功的決定因素。 第三節(jié)選題意義和內容安排 當今，i n t e r n e t 的發(fā)展可謂日新月異。伴隨著i n t e m e t 的發(fā)展，其應用領域 也急速拓展。因此，網絡傳輸業(yè)務量成指數形式增長( 如數據量巨大網絡多媒體 傳輸) 。由此需要在新的服務體系下應用流量工程來優(yōu)化網絡性能。流量工程在 原有網絡資源基礎上可以精確控制業(yè)務量，并能提供服務質量保證。關于流量工 程的討論是目前在i n t e m e t 業(yè)界、大型的i s p 、以及如因特網工程任務i f l ( i n t e m e t e n g i n e e r i n gt a s kf o r c e ，i e t f ) 等研究組織的熱點話題。薪一代i n t e r n e t 網絡的 形成，并沒有使旨在優(yōu)化網絡運行的流量工程的研究止步，正相反，新的網絡運 營方式、新的服務要求，反而向這些研究提出了新的課題。無論是過去的、今天 的還是未來的網絡，僅僅增加網絡帶寬，提高傳輸速度，沒有流量工程的軟件支 持，路由器就不能有效地對業(yè)務流進行有效的控制，從而造成網絡資源的浪費或 者使用效率不高，從而不能從根本上解決網絡擁塞和數據丟失，而且不能滿足越 來越多的服務種類和服務質量的要求。所以，在網絡研究的領域中，流量工程的 重要性對i s p 來說日益增長的。 路由選擇是網絡中路由器交換機應具備的最基本的功能，更是流量工程中 的最重要的組成部分之一；靜態(tài)路由的配置影響網絡對處理業(yè)務流時的最初策 略，決定網絡資源的初始分配方案，對業(yè)務量的控制和動態(tài)路由的計算有著重要 的影響。在路由選擇方面，目前對動態(tài)路由的研究比較多，對靜態(tài)路由選擇的研 s 第一章緒論 究比較少，目前普遍使用的靜態(tài)路由配置方法采用傳統(tǒng)的簡單算法或者人工配 置，這種方法已經不能適應越來越大的網絡規(guī)模和越來越復雜的網絡狀態(tài)。所以 對靜態(tài)路由選擇的研究在流量工程研究中的重要性也日益顯著。 在已有研究成果的基礎上，本文提出一種新的靜態(tài)路由算法基于約束的 多量度配置l s p 算法( 簡稱多量度算法) 。算法考慮路由時要應用的q o s 需求、 網絡的資源約束和管理屬性等諸多約束；首先分階段來處理各種約束條件，分析 網絡運行狀態(tài)和資源實用狀況，隨后由分析結論制定主次目標策略，在計算路由 中運用主次目標的方法來選擇路由，從而滿足配置的l s p 的多約束需求，并使 得網絡資源得到充分的均衡的使用，減少潛在的網絡擁塞可能性。在國內，關于 流量工程的研究剛剛開展，所以這種以網絡赍源狀況為立足點的基于約束靜態(tài)路 由算法研究將會促進流量工程的發(fā)展，對我們的科研和網絡經濟的發(fā)展也具有重 要意義。 本文內容安排如下：第章為緒論，簡述計算機網絡體系結構，為了解決網 絡發(fā)展帶來的問題而提出解決方案流量工程，并給出本論文的選題意義和內 容安排；第二章詳細論述通信網的流量工程，并討論流量工程在不同的網絡類型 中的應用，其中重點闡述在新一代路由器核心網絡中的流量工程的實施方案 m p l s 技術；第三章闡述目前流量工程中使用的動態(tài)路由算法和靜態(tài)路由算法， 以及基于約束的路由算法，并指出現行算法的不足；第四章講述本文提出的一種 新的靜態(tài)路由算法基于約束的多量度配置l s p 算法，解決現行算法的缺點， 并從理論上( 算法的時間復雜度) 論證多量度算法的有效性。第五章通過網絡實 例對算法進行仿真驗證，證明算法的較優(yōu)性；最后對算法作出總結，指出算法的 優(yōu)點。第六章回顧總結全文，并提出今后還需繼續(xù)研究的相關問題。 - 6 第二章流量工程研究 第二章通信網的流量工程研究 第一節(jié)流量工程綜述 2 0 世紀9 0 年代早期，網絡規(guī)模較小，i s p 網絡由專線鏈接起來的路由器組 成。這種傳統(tǒng)路由器用軟件對數據包進行分組和轉發(fā)。當i n t e m e t 開始快速增長 的時候，路由器和帶寬就不能滿足應用的需求。i s p 為了解決這個問題，增加了 鏈路與路由器的數量。由于路由器與鏈路數量的增加，網絡的拓撲變得復雜起來， 網絡的連通度提高，同一點對問的路徑數量也增加了。如果可以對業(yè)務量在網絡 中傳輸的路徑進行控制，則可以有效的利用網絡中比較多的帶寬資源。由此提出 了對流量工程的研究。 同時，隨著客戶對帶寬及業(yè)務的需求越來越高、越來越多樣化，i s p 們面臨 的壓力不但來自于如何有效的利用網絡中寶貴的資源還來自如何使他們的網絡 滿足客戶日益增長的需求，并使網絡具有較高的靈活性和可擴展性，以適應將來 網絡發(fā)展的需求。這便要求i s p 對客戶業(yè)務在網絡中的分配進行控制，從而充分、 有效地利用現有網絡帶寬，為客戶提供優(yōu)質服務。這種將業(yè)務流量映射到現有物 理拓撲上的任務稱為流量工程【3 】 3 1 【3 3 】。 本節(jié)從流量工程實施的目的、具有的功能、實現要求以及其過程模型四個方 面闡述流量工程體系。 2 1 1 流量工程實施的目的 流量工程的目的是為i s p 網絡提供精確的流量控制，具體地說是在流量沿 定路徑傳送時為底層結構提供附加信息，使網絡運行更加有效、可靠、便利，同 時優(yōu)化網絡資源的使用。簡單地說，流量工程就是將業(yè)務量映射到實際物理網絡 拓撲上的過程【3 】【9 1 。 2 1 2 流量工程具有的功能 流量工程提供在主干網絡路由域上的流量精確控制，希望卷入進程的人工干 7 - 第二章流量工程研究 預最小化，因此流量工程需要具有以下功能： 1 對主路徑進行路由時，繞過網絡中已知的瓶頸點和阻塞點。 2 當主路徑發(fā)生一個或多個故障時，為業(yè)務如何進行重新路由提供明確控 制。 3 通過確保網絡的附屬設備不會被過度使用，同時，潛在的被選路徑上的 網絡附屬設備未被充分使用，從而對這些可用的集成帶寬和長距離光纖 進行有效的利用。 4 通過使包丟失最小化、使阻塞的保持時間最小化和使吞吐量最大化的方 法增強網絡中以業(yè)務為導向的性能特性。 5 增強網絡中將來用于支持多業(yè)務i n t e r a c t 的統(tǒng)計約束性能特性( 如，丟失 率、延遲變化、傳輸時延等) 。 6 為客戶提供更多的選擇，更低的費用和更好的服務。 2 1 3 流量工程的要求 流量工程應當看作是路由器中集成的一個網絡功能，所以流量工程的要求也 是對路由器的要求。在流量工程環(huán)境中，網絡條件和業(yè)務量的情況有了很大的變 化，路由和轉發(fā)技術不同于傳統(tǒng)i p 網絡中的技術，路由器的功能有所差別，流 量工程對路由器的要求也就有其特殊的含義。 2 1 3 1 流量工程的一般要求 流量工程的一般要求包括以下八點【2 1 1 3 1 ： 可用性：流量工程系統(tǒng)可運行在現有的網絡上，而且容易操作和維護； 自動性：流量工程系統(tǒng)能自動執(zhí)行流量工程的功能而盡可能減少人工介入； 可擴展性：流量工程系統(tǒng)應該能隨著網絡的發(fā)展而擴展： 穩(wěn)定性：系統(tǒng)對網絡狀態(tài)變化做出響應必須在快速反應性和穩(wěn)定性之間折衷 處理： 靈活性：允許優(yōu)化策略根據網絡情況靈活地改變。 可觀測性：具有從網絡中收集數據和分析數據以決定網絡性能好壞和判斷優(yōu) 化策略效果的機制，得到網絡的統(tǒng)計數據以作為網絡狀態(tài)的指示。 8 第二章流量工程研究 簡單性：流量工程系統(tǒng)在實現時應當盡量簡單，對用戶來說是不透明的。 擁塞管理：流量工程系統(tǒng)能夠把流量合理地映射到網絡上以避免或減小擁塞， 同時擁塞發(fā)生時可以迅速轉移流量。 2 1 3 2 路由選擇要求 路由控制機制是流量工程的一個最重要的方面，由于傳統(tǒng)基于最短路算法的 內部網關協議( i n t e r i o r g a t e w a y p r o t o c o l ，i g p 協議) 的限制【3 】【2 7 1 1 3 8 】口9 1 ，需要新 的控制i p 網絡中路由選擇功能的能力，這些能力包括： 基于約束的路由( c o n s t r a i nb a s e dr o u t i n g ，c r ) 選擇算法【1 4 】 1 6 】：計算出能 滿足多個約束條件的路徑。 擴展傳統(tǒng)的鏈路狀態(tài)i g p 能夠傳播c r 需要的多種拓撲狀態(tài)信息； 多條路徑上的負載分配可以配置，靈活控制流量分發(fā)； 在控制某部分流量的路由時，盡可能不影響其他部分流量的路由； 如果網絡支持多種服務類型，路由子系統(tǒng)應當有為不同類型的流選擇不同的 路的能力。 2 1 3 3 測量要求 為支持流量工程的功能，應提供設備從網絡中測量和收集統(tǒng)計數據，并有能 力對收集的統(tǒng)計數據進行分析。這些設備的行為不能對收集的統(tǒng)計數據的精確性 和整體性產生不利影響。同時，收集統(tǒng)計數據的機制也應隨著網絡發(fā)展而改進。 流量統(tǒng)計可以根據時間長短分為長期的和短期的，長期的流量統(tǒng)計反應網絡 周期性的負載，對長期的流量統(tǒng)計數據分析可得出如高峰時期特性、流量增長模 式、持續(xù)擁塞等熱點問題，以及由于路由不合理引起鏈路使用不平衡等間接的統(tǒng) 計數據；在短期類型中，流量統(tǒng)計對網絡當前狀態(tài)提供合理和可靠的指示，反應 鏈路使用和鏈路、路徑擁塞狀態(tài)。發(fā)布這些信息的例子包括s n m p 、探測技術、 f t p 、內部網關協議、鏈路狀態(tài)通告等。 2 1 3 4 ，生存性要求 網絡生存性指網絡中存在失敗時網絡維持服務的連續(xù)性的能力。要求網絡有 第二章流量工程研究 能力快速地從失敗中恢復并維持恢復后現存服務的q o s 要求。隨著i n t e m e t 中關 鍵流量、實對流量、其他高優(yōu)先級的流量傳送任務需求的目益增長，生存性已經 成為i n t e r n e t 業(yè)界非常關心的一個問題。隨著網絡技術不斷發(fā)展，失敗的監(jiān)測和 恢復能力已經可以在多層得到口兒5 6 1 。例如，第二層技術如異步傳輸模式 ( a s y n c h r o n o u st r a n s f e rm o d e 。a t m ) 用自動保護交換( a u t o m a t i cp r o t e c t i o n s w i t c h i n g ，a p s ) 和自愈環(huán)和自愈網( s e l f - h e a l i n gr i n ga n d m e s h ) 機制提供殘存 能力，在i p 層使用重路由( r e r o m i n g ) 的方法在鏈路和節(jié)點中斷后恢復服務的 連續(xù)性，i p 層的重路由在一段時間的路由收斂后發(fā)生，收斂需要幾秒到幾分鐘 完成。 2 13 ，5 離線的流量工程支持系統(tǒng)的要求 如果希望得到最佳的鏈路效率，離線的集中的流量工程支持系統(tǒng)可能作為一 個整個流量工程系統(tǒng)中一個完整的部分提供。離線和集中的流量工程支持系統(tǒng)可 以用來計算流量簇的路徑?？紤]到流量簇的要求、鏈路屬性和網絡拓撲信息離 線的流量工程支持系統(tǒng)一般可以找到比在線的流量工程系統(tǒng)更好的流量簇配置， 在線系統(tǒng)的網絡中每個路由器以分布方式基于它自己的信息找到路徑。離線的流 量工程支持系統(tǒng)可以周期地計算流量簇的路徑( 比如說每天) ，目的是再優(yōu)化。 然后計算出的路徑可以下載到路由器中。在線的流量工程系統(tǒng)仍然需要，以便路 由器可以迅速地適應變化。 2 。1 4 流量工程的過程模型 拋卻流量工程的執(zhí)行細節(jié)在網絡與網絡之間的不同，為描述大多數流量工程 過程普遍的行為，優(yōu)化運行中的系統(tǒng)性能，按照運作流量工程的順序或者更一般 的流量工程系統(tǒng)描述，流量工程實施過程可以分為四個階段： 第一階段是定義在網絡中支配運行相關的控制策略。這些策略可能基于流行 的商業(yè)模型，網絡開銷的構成，網絡運行約束，一個或多個最優(yōu)化標準，還有其 他方面。 第二個階段是一個從運行的網絡中請求測量數據的反饋過程。綜合工作負荷 可能用估算或使用以前的經驗數據或者流量特征的數學模型做出推斷，或使用其 。1 0 第二章流量工程研究 他手段。 第三階段是分析網絡狀態(tài)來描述流量負荷。一般地，性能分析可能是主動的 或者是反應性的。主動的性能分析指明并不存在的潛在問題，但是可能會在將來 發(fā)生：而反應性的性能分析指明現存的問題，通過診斷程序確定原因，如果有必 要分析代替的方法做出補救。許多定性和定量的技術可能在分析過程中使用，包 括基于建模的分析和仿真。在過程模型的分析階段，需要研究網絡流量的分布情 況和負荷特征，指出流量瓶頸和網絡異常。流量矩陣構造可能作為分析過程的一 部分。 第四個階段關于網絡性能的優(yōu)化。性能優(yōu)化階段一般包括在可選行為中做出 一系列選擇并執(zhí)行。優(yōu)化行為可能包括適當的技術用來控制流量及其分配，擴充 網絡規(guī)模，增加網絡設備，以系統(tǒng)的方式調整相關路由的參數如i g p 的量度和 b g p 的屬性，調整流量管理屬性，調整網絡參數和網絡元素的配置。 第二節(jié)i s p 網絡發(fā)展及流量工程在其中的實現 因為流量工程最終是要應用到網絡中，對其路由域內對流量的分布進行精確 的控制，所以流量工程的發(fā)展和i s p 網絡類型的發(fā)展是一致的。網絡類型的發(fā)展 大致經歷三個階段：傳統(tǒng)的路由器核心的網絡、p 覆蓋模型網絡( i p o v e r - a t m ) 、 新一代路由器核心網絡【l 】【1 4 1 。以下章節(jié)分別講述這些網絡類型以及流量工程在其 中的實現。 2 2 1 傳統(tǒng)的路由器核心網絡及流量工程的實現 在2 0 世紀9 0 年代初期，i s p 的網絡通過使用租用線- - t 1 ( 1 5 m b p s ) 和t 3 ( 4 5 m b p s ) 連接一將路由器互聯麗組成網絡。當i n t e r a c t 開始它的爆發(fā)性增長時， 對帶寬需求的增長要比單條網絡連接速率快得多。i s p 們對這一挑戰(zhàn)的反應是提 供更多的鏈接以提供額外帶寬。從這一點看，流量工程對i s p 變得越來越重要了， 因此，當存在多條并行或各選路徑時，i s p 們可以有效地使用集成網絡帶寬。 在傳統(tǒng)的路由器核心網絡中，流量工程的實現基于簡單的路由加權的流量控 - 1 1 - 第二章流量工程研究 制?；诩訖嗔慷瓤刂频牧髁抗こ踢\行的原理如圖2 1 所示。圖中標出了各條鏈 路的權值。假定網絡a 向網絡c 和d 發(fā)送大量的信息，由于網絡a 到網絡c 和 網絡a 到網絡d 的流量都經過鏈路1 、鏈路2 ，會導致這兩條鏈路擁塞。如果把 鏈路4 的權值改為2 ，a 到d 的流量就流經鏈路4 ，而a 到c 的流量仍然在鏈路 1 和鏈路2 上。這樣，鏈路1 和鏈路2 上的負載減少，擁塞的問題就解決了1 2 j 。 路由器b t 2 r l c = 1 路由器c 圖2 1 基于量度的流量工程 起初網絡規(guī)模和業(yè)務流量都非常小，這種簡單的方法直到九十年代中期還是 能夠勝任的。隨著i s p 網絡的不斷增大，而基于簡單加權的流量處理方法可擴充 性能差，不能保證對網絡某一部分的調整不會引起其他部分出現問題；傳統(tǒng)路由 器的處理能力不能承擔高負荷的處理任務；基于簡單加權的拓撲驅動的i g p 路 由計算不考慮網絡的負載情況，導致流量在網絡鏈路中不能均衡分配，鏈路負載 不均，資源得不到有效利用，擁塞的可能性增大。 傳統(tǒng)路由核心網在為流量工程提供可擴展的支持上存在的許多局限日益顯 現： 由于傳統(tǒng)路由器的匯集帶寬和包處理能力有一定的局限性，因此，傳統(tǒng)的、 基于軟件的路由器在高負荷的情況下可能成為潛在的瓶頸。 基于量度處理的流量工程不具有可擴展性。當i s p 網絡變的具有更多的鏈按 時( 即，更大、更密集的結網和更多的冗余) ，這種情況下很難保證對網絡 某個部分量度的調整而不致在網絡的其它部分引起問題?；诹慷忍幚淼牧?量工程對于增加的復雜問題提供的是一跟蹤- g q 錯的鰓決方式，而不是一個 科學的解決方案。 i g p 計算是通過拓撲驅動的，它只基于一個簡單的附加量度，如跳數或某個 管理值。i g p 不發(fā)布類似于帶寬可用性和業(yè)務特征等信息。這樣對于復雜連 1 2 第二章流量工程研究 接網絡，不利于業(yè)務所使用的鏈路進行控制以確保鏈路的負荷均衡。 2 2 2 i p 覆蓋模型網絡( i p o v e r - a t m ) 及流量工程實現 2 0 世紀9 0 年代中期( 1 9 9 4 年1 9 9 5 年) ，i n t e m e t 業(yè)務量的增長要求i s p 是他們的網絡支持t 3 ( 4 5 m b p s ) 以的速率，這時的o c 3a t m 接口技術可以使 路由器和交換機能夠得到1 5 5 m b p s 的傳輸速率，因此產生了i p o v e r a t m 網 絡，其典型結構如圖2 2 所示【2 】 6 】 1 4 ： 0 c 3 a t mi o c 1 2 硝m 圖2 2 典型的i po v i b z a t 蕞網絡結構 在i p o v e r a t m 網絡中，路由器圍繞在a t m 網絡邊緣，每個路由器通過 一系列經由a t m 物理拓撲設置的永久虛電路( p e r p e t u i t y v i s u a lc i r c u i t ，p v c ) 與其他路由器相連。路由器不能直接控制虛電路連接的信息，它只知道單獨的 p v c 就像簡單的點對點鏈路那樣連接著兩個路由器。i p o v e r a t m 網絡中物 理拓撲和邏輯拓撲的區(qū)別如圖2 3 所示。 樅惻蛔p i a 付 一名堰吣 芬 u m , lb 事c 協印b 鯽 圖2 3 i p o v e r a t m 網絡中物理拓撲和邏輯拓撲 在此，永久虛電路覆蓋的物理路徑通常是通過離線配置計算獲得的，它使用 基于需求的方式當網絡中發(fā)生擁塞新增一條干線或配置一個新的接觸點 1 3 第二章流量工程研究 ( p o i n to fp r e s e n c e ，p o p ) 。此外。一些a f m 提供上使用在線調整的方法來實 現流量工程。p v c 的實際路經和特性由一個全局優(yōu)化和配置的功能依據鏈路的 帶寬和歷史流量時間表來提供。離線計算可以提供一些輔助的p v c 以備在發(fā)生 失敗的時候使用。全局的優(yōu)化和計算完成后，配置參數下載到路由器和a t m 交 換機上，這樣便形成了一個全網絡的邏輯拓撲。實際上，離線設置程序產生路由 和交換兩部分配置。a t m 的p v c 可以映射為路由器的子接口，路由協議把i p 前綴( p r e f i x ) 與子接口對應起來。最后，a t m 的p v c 通過運行i g p 協議集成 到i p 網絡中。 現在流量工程的典型做法是在i p o v e r a t m 網絡上使用人工配置。這種 機制中，a t m 交換機提供的高速接口和明顯提高的匯集帶寬使網絡性能得到明 顯改善，鏈路資源得到比較均衡的利用，網絡具有了在線調整p v c 路由的功能 和解決擁塞問題的功能，因此避免了在網絡核心的部分因路由器引起的瓶頸的潛 在可能性，a t m 網絡的速率和帶寬為i s p 提供了確定的性能。并且，由a t m 交 換機提供的每條p v c 的統(tǒng)計信息，簡化了監(jiān)測用于優(yōu)化p v c 布局及管理的業(yè)務 參數的過程。網絡設計者最初為支持特定的流量工程目的而提供每條p v c ，然 后，他們連續(xù)監(jiān)測每條p v c 上的業(yè)務負載。當一條特定的p v c 發(fā)生擁塞時，i s p 具有所需要的信息，使其能夠通過修改虛擬或物理拓撲結構以適應便宜的業(yè)務負 荷，對發(fā)生的事件進行補救。 因此，一個基于a t m 的核心網完全支持流量工程，它可以對p v c 進行明確 的路由。p v c 的路由是通過在網絡底層的物理拓撲上提供的隨機的虛擬拓撲實 現的，而在網絡底層的物理拓撲上，通過對p v c 進行路由以使業(yè)務分配到所有 鏈路上去，以致鏈路被平均便用。這種實現避免了、韭務全部忙集到的花銷路由上 去，從而避免了鏈路的過分使用或未被充分使用。由a t m p v c 提供的流量工程 性能使i s p 在他們的市場范圍內更具競爭性，允許他們?yōu)槠淇蛻籼峁┑唾M用和確 保質量的服務。 但是，隨著網絡的迅速膨脹和用戶服務要求的不斷變億，現有的i p o v e r a t m 機制的缺陷也日益明顯。這種局限主要表現為： 必須對a t m 下層結構和邏輯上的i p 覆蓋兩個網絡同時進行管理： a t m 的接口技術未能跟上光學帶寬的最新發(fā)展，設備費用和管理費用高昂； 一1 4 - 第二章流量工程研究 轉發(fā)包時必定要支付的a t m 信元稅( c a l 卜t a x ) 導致不能對帶寬充分利用； 網絡擴充時的n 2 比例問題和故障處理鏈路更新時的n 3 比例問題。 網絡的物理拓撲結構和邏輯結構不相匹配。 除了這些缺陷，混合媒體網絡( 如光網絡) 的增長和減少i p 光纖間的層數 的目的，要求流量工程在第3 層實現，但是，基于覆蓋模型的流量工程要求支持 交換和p v c 的第二層技術存在，這使得難以提出一可行方案。 總之，i p o v e r a t m 網絡模型的諸多不利隨著i n t e r n e t 的發(fā)展，越來越顯 現突出。高速接口、確定的性能、和使用p v c 的流量工程不再使a t m 交換機明 顯區(qū)別于i n t e r a c t 骨干網路由器。而且，基于路由器的核心網的匹配問題解決了 a t m 模型的一些固有問題一一協議兩個分離系統(tǒng)的負載性和較高的費用， a t m s a r 接口的帶寬局限性，p v c 的“n “問題，i g p 壓力，不能在混合媒體 結構中運行的局限性，和不能實現第2 層和第3 層之闐的無縫連接的不利因素等。 因此，i s p 必須考慮一種新的技術來取代現有機制。 2 2 3 新一代路由器核心網絡 當i s p 開始計劃轉移到更高速的網絡時，他們會仔細檢查選擇方案，使他們 過去的流量工程策略不會約束將來網絡的增長和運行。對于運行在o c - - 4 8 速率 上的高性能骨干網，問題變化得非?？欤灾劣诒３窒嗤呗灾徊捎幂o助的( 或 主要的) 增強方式去修改或調整網絡方案己不可能。當他們不能擴展時，網絡設 計人員將重新考慮新的解決方案。 目前，c i s c o 、j u n i p e r 等大型的網絡廠商和一些新興的廠商都在致力于i n t e r n e t 骨干路由器的研究開發(fā)。新型的路由器集成了i n t e r a c t 可伸縮性、i n t e r a c t 控制和 從前只有在交換機上才有的高性能的轉發(fā)，還兼顧路由軟件的靈活性( 即可控制 性) 和穩(wěn)定性( 即可靠性) 。 與此同時，廠商們和i e t f 開始研究路由器的路由功能和a t m 交換機的轉發(fā) 功能相結合的多標記交換( m u l t i p r o t o c o l l a b e ls w i t c h i n g ，m p l s ) 技術【7 】【8 】【9 】。 m p l s 是多層交換機研究得最新進展和標準化產物。m p l s 為大型i s p 網絡實施 流量工程提供了堅實的基礎，使其成為在i n t e m e t 中實現流量工程得首