（計算機應(yīng)用技術(shù)專業(yè)論文）遺傳算法在qos組播路由算法中的應(yīng)用.pdf

遺傳算法在q o s 組播路由算法中的應(yīng)用 遺傳算法在q o s 組播路由算法中的應(yīng)用 摘要 在計算機網(wǎng)絡(luò)中，隨著大量新興多媒體實時業(yè)務(wù)的應(yīng)用，以及 i n t e m e t 上商業(yè)化應(yīng)用的飛速發(fā)展，網(wǎng)絡(luò)對q o s 需求增長，高效的q o s 支持變得越來越重要。而路由機制是實現(xiàn)q o s 保證的關(guān)鍵之一，應(yīng)將 路由選擇和q o s 相關(guān)聯(lián)。 目前組播路由算法的研究大多都針對無約束組播路由問題和時延 受限組播路由問題，多采用啟發(fā)式等方法。本論文研究如何將遺傳算 法這一新型優(yōu)化算法應(yīng)用到q o s 組播路由算法問題中，利用該算法的 并行搜索、群體優(yōu)化的特點，為解決q o s 組播路由問題尋找新的途徑。 本文主要研究四類典型的q o s 組播路由問題求解。主要研究工作共分 四個部分： 第一部分是緒論，對計算機網(wǎng)絡(luò)的組播通信進行了綜述。主要介 紹組播引入的背景、特點、組播技術(shù)，還敘述了q o s 的相關(guān)內(nèi)容、研 究現(xiàn)狀、組播路由協(xié)議和應(yīng)用。 第二部分是研究的基礎(chǔ)部分，主要介紹了q o s 的描述參數(shù)、數(shù)學(xué) 模型、存在問題以及組播路由算法研究現(xiàn)狀。 第三部分介紹了遺傳算法的歷史、特點、優(yōu)缺點和應(yīng)用，還介紹 遺傳算法的基本步驟，混合遺傳算法，還包括在遺傳算法中用于解決 約束優(yōu)化問題的常用方法。 遺傳算法舀q o s 組播路由算法中的應(yīng)用 第四部分是本文研究的重點，著重介紹目前的研究熱點一基于遺傳 算法的組播路由算法。主要研究四個方面的問題：時延約束組播路由 問題；時延和時延抖動約束組播路由問題；帶度約束的組播路由問題； 多個q o s 約束的組播路由問題。根據(jù)q o s 組播路由的特點，結(jié)合遺傳 算法的尋優(yōu)特性，提出來一種新的混合遺傳算法解決時延約束組播路 由算法和一種新的混合遺傳算法解決多個q o s 約束的組播路由問題的 組播路由算法。 關(guān)鍵詞：組播路由，q o s 組播，遺傳算法，組播樹 一 望堡竺鯊壟旦! ! 塑塑墮叟篁鯊! 塑些里 s t u d y0 n q o sm u l t i c a s tr o u t i n gp r o b l e mb a s e d o ng e n e t i ca l g o r i t h m a b s t r a c t a st h ed e m a n d sf o r q u a l i t yo fs e i c e ( q o s ) b ym u l t i s e i c ei ni n t e m e ta r er a p j d l y i n c r e a s i n 呂e f 艷c t i v ea n de 踴c i c n tq o ss u p p o n h a s b e c o m i n gm o r e a i l dm o r e i m p o r t a n t t h er o u t i n gt e c h n o l o g yi so n eo fm ek e yr o l e st o g u a r a n t e eq o s ，s ot h er o u t i n g m e c h a n i s ma n dq o sm u s t b eb e c o m e t o g e t h e l n o w ，r e s e a r c h e so nm u l t i c a s tr o u t i n ga l g o r i t l l i i lm a i n l yf o c u so nm u l t i c a s t i n g a i g o r i t h mw i t h o u tc o n s 仃a i n t s a 1 1 d d e l a y c o n s t r a i n e 王m u l t i c a s tr o u t i n a i l da l s ou s e h e 曲s t i ca l g o 五m m t h er e s e a r c ho ft h i st h e s i sf o c u s e so nh o ww ec a l l 印p l yg e n e t i c a l g o r i t h mt oq o s m u m c a s tr o u t i n gp r o b l 咖s b e c a u s ei th a ss om a l l ya “鋤t a g e s ，s u c h a sc o n c u r r e n ts e a r c h i n ga 1 1 dc o l o n y0 p t i n l i z e ，a st op r o v i d eu ss o m en e wm e t h o d st o s 0 1 v et h eq o sm u l t i c a s tr o u t i n gp r o b l e m s f o l l rt y p i c a lp r o b l 鋤sa r ed i s c u s s e di nt h e t l l e s i s s om e 1 c s i sh a sf o l l rp a r t s ： t h ef i r s t p a r t i si n 仃o d u c t i o n w es u m m a r i z eo nm u l t i c a s tc 優(yōu)n m u n i c a t i o n si n c o m p u t e rn e 柳o r k s w ep r e s e n t t h eb a c k g r o l u l do fm u n i c a s t ，s p e c i a lf e a t i l r ea n d t e c h n 0 1 0 9 y w e a l s on a r r a t et h ec o n t e n to n q o sm u l t i c a s t ，m ep r e s e n tr e 8 e a r c hs i m a t i o n ， m u l t i c a s t r o u t i n ga g r e e m e n t a n d u s i n g t h es e c o n d p a n i sm ef o u d 鋤e n t a l p a n o f t l l er e s e a r c h w b 百v ea na c c o u n to f q o s m e m c ，鏟印hm o d e la l l dm ee x i s t i n gp r o b l e m ，a i l dt l er e s e a r c ho fp r e s e n to n m u l t i c a s t r o u t i n ga l g o f i t l l m t h et h j r dp a nr e c o 蚴鋤dt h ed e v e l o p m e m1 1 i s t o r yo fg e n e t i ca l g 鰣t 協(xié)，a 1 1 d i n c l u d i n gc h a r a c t e r i s t i c ，a d v a n t a g e a n dd i s a d v a m a g e w ea l s o 舀v em eb a s i c s t 印， h y b r i dg e n c t i ca l g o r i 蚰n ，s o m ed c t a i l sh a v ey e tt ob em s c u s s e da b o u ts 0 1 u t i n g t h e c o n s t r a i mq o sw i m g e n e t i ca l g o r i t t l m t h ef b u n h p a f t j st h e 鋤p h a s j so f t l l ef e s e a r c h t h ep r e s e n tr e s e a f c hh o 印o n s1 】1 a t a p p l yg e n e t i ca l g o r i m m t oq o sm u l t i c a s t r o u t i n ga r em a i l l l yd i s c u s s e d w eh a v es t u d i e d f o u r i “巾o n a n tm u l t i c a s tr o u t i n g ，p m b l e m sw i mq o sp a r a m e t e rc o n s t r a i m ss u c h a s t i m e d e l a yc o n s 仃a i n t ，t i m e d e l a yv 撕a t i o nc o n s t r a i n t ，d e 乒e ec o n s 仃a i l l t sa n ds o m eq o s p a r 鋤e t e rc o n s 仃a i n t a c c o r d i n g t ot h ec h a r a c t e ro f q o sm u “i c 勰tr o u t i n ga i l do p t i m i z e c h a r a c t e ro fg e n e t i ca 1 9 0 r i m m ，an e wa p p r o a c hb a s e do nh y b f i dg e n c l i ca l g 叫m mi s p m p o s e d t os 0 1 v et i m e d e l a yp a r a m e t e rc o n s 仃a i n tp r o b l e ma n da n o t h e rh y b r i dg e n e t i c a l g o r i t h m b eu s e do ns o m eq o sm u l t i c a s tr o u t i n gp r o b l e m k e yw o r d s ：m u n i c a s tr o u t i n g ，q o s ，g e n e t i ca 1 9 0 d m m ，m u l t i c a s t i n g t r e e 遺傳算法北0 0 s 組播路由算法中的應(yīng)用 第一章緒論 1 1 引言 世界上第一臺數(shù)字電子計算機自1 9 4 6 年問世后，在最初1 0 年內(nèi)，計算機和 通信沒有什么關(guān)系。當(dāng)時計算機以“計算中心”的服務(wù)模式工作。直至1 9 5 4 年， 一種收發(fā)器( t r a n s c e i n e r ) 的終端制造出來后，人們才首次使用這種終端通過電話 將數(shù)據(jù)發(fā)送到遠地的計算機。此后，計算機開始與通信結(jié)合，計算中心的服務(wù)模 式逐漸讓位于計算機網(wǎng)絡(luò)的服務(wù)模式。實踐表明，計算機網(wǎng)絡(luò)的產(chǎn)生與發(fā)展，對 人類社會的發(fā)展產(chǎn)生了深遠的影響。 采用計算機網(wǎng)絡(luò)通信，不僅大大提高通信線路的利用率，改善通信質(zhì)量，而 且為實現(xiàn)全數(shù)字化、寬頻帶、多媒體信息的高速傳輸以及計算機、電視和電話的 三合一奠定了基礎(chǔ)。這種相互連接的計算機信息網(wǎng)絡(luò)，把距離和時間縮小到零， 大大降低了人們物理位置靠近的必要，通過計算機網(wǎng)把整個社會結(jié)構(gòu)緊密結(jié)合在 一起，將改變?nèi)藗兊纳睢W(xué)習(xí)和工作方式。 1 1 1 網(wǎng)絡(luò)數(shù)據(jù)傳輸方式 網(wǎng)絡(luò)數(shù)據(jù)傳主要有單播，組播和廣播技術(shù)三種方式： 單播( u n i c a s t ) 傳輸：在發(fā)送者和每一接收者之間實現(xiàn)點對點網(wǎng)絡(luò)連接。如 果一臺發(fā)送者同時給多個的接收者傳輸相同的數(shù)據(jù)，也必須相應(yīng)的復(fù)制多份的相 同數(shù)據(jù)包。如果有大量主機希望獲得數(shù)據(jù)包的同一份拷貝時，將導(dǎo)致發(fā)送者負擔(dān) 沉重、延遲長、網(wǎng)絡(luò)擁塞；為保證一定的服務(wù)質(zhì)量需增加硬件和帶寬。 組播( m u l t i c a s t ) 傳輸：在發(fā)送者和每一接收者之間實現(xiàn)點對多點網(wǎng)絡(luò)連接。 如果一臺發(fā)送者同時給多個的接收者傳輸相同的數(shù)據(jù)，也只需復(fù)制一份的相同數(shù) 據(jù)包。它提高了數(shù)據(jù)傳送效率。減少了骨干網(wǎng)絡(luò)出現(xiàn)擁塞的可能性。主要用于視 頻會議等應(yīng)用場合，這種應(yīng)用需要將一份數(shù)據(jù)同時發(fā)送給多個用戶。而多播技術(shù) 具有帶寬利用率高、減輕主機路由器的負擔(dān)、避免目的地址不明確所引起的麻煩 等優(yōu)點，從而滿足這種應(yīng)用。 廣播( b r o a d c a s t ) 傳輸：是指在i p 子網(wǎng)內(nèi)廣播數(shù)據(jù)包，所有在子網(wǎng)內(nèi)部的主 機都將收到這些數(shù)據(jù)包。廣播意味著網(wǎng)絡(luò)向子網(wǎng)每一個主機都投遞一份數(shù)據(jù)包， 不論這些主機是否樂于接收該數(shù)據(jù)包。所以廣播廣播的主要的缺點就是每個廣播 都要發(fā)送數(shù)據(jù)至所有機器，消耗了所有機器上的資源，即使數(shù)據(jù)要被網(wǎng)絡(luò)中大多 數(shù)機器所丟棄，使用范圍非常小，只在本地子網(wǎng)內(nèi)有效，通過路由器和交換機網(wǎng) 絡(luò)設(shè)備控制廣播傳輸。 單播傳送發(fā)送數(shù)據(jù)的多個拷貝，每個拷貝發(fā)送到一個接收者，主機輪流發(fā)送 數(shù)據(jù)的拷貝，網(wǎng)絡(luò)分別將它們轉(zhuǎn)發(fā)至每個接收者，主機一次只能發(fā)送至一個接收 者。而組播傳送則只把發(fā)送數(shù)據(jù)的個拷貝發(fā)送到多個接收者，主機發(fā)送數(shù)據(jù)的 遺傳算法托q o s 組播路由算法中的應(yīng)用 一個拷貝，可同時發(fā)送到多個接收者。網(wǎng)絡(luò)在每個接收者的最后一個路由器或主 機復(fù)制它，在一個給定的網(wǎng)絡(luò)上每一個包只傳送一次。 1 1 ，2 組播技術(shù)引入的必要性 隨著寬帶多媒體網(wǎng)絡(luò)的不斷發(fā)展，各種寬帶網(wǎng)絡(luò)應(yīng)用層出不窮。i pt v 、視頻 會議、數(shù)據(jù)和資料分發(fā)、網(wǎng)絡(luò)音頻應(yīng)用、網(wǎng)絡(luò)視頻應(yīng)用、多媒體遠程教育等寬帶 應(yīng)用都對現(xiàn)有寬帶多媒體網(wǎng)絡(luò)的承載能力提出了挑戰(zhàn)。采用單播技術(shù)構(gòu)建的傳統(tǒng) 網(wǎng)絡(luò)已經(jīng)無法滿足新興寬帶網(wǎng)絡(luò)應(yīng)用在帶寬和網(wǎng)絡(luò)服務(wù)質(zhì)量方面的要求，因為服 務(wù)器必須為每一個接收者提供一個相同內(nèi)容的i p 報文拷貝，同時網(wǎng)絡(luò)上也重復(fù)地 傳輸相同內(nèi)容的報文，占用了大量資源。雖然i p 廣播允許個主機把一個i p 報 文發(fā)送給同一個網(wǎng)絡(luò)的所有主機，但是由于不是所有的主機都需要這些報文，因 而浪費了網(wǎng)絡(luò)資源隨之而來的是網(wǎng)絡(luò)延時、數(shù)據(jù)丟失等等問題。在這種情況下組 播( m u l t i c a s t ) 應(yīng)運而生，它的出現(xiàn)解決了一個主機向特定的多個接收者發(fā)送消息 的方法。組播網(wǎng)絡(luò)中，即使組播用戶數(shù)量成倍增長，骨干網(wǎng)絡(luò)中網(wǎng)絡(luò)帶寬也無需 增加。簡單來說，成百上千的組播應(yīng)用用戶和一個組播應(yīng)用用戶消耗的骨干網(wǎng)帶 寬是一樣的，從而最大限度的解決目前寬帶應(yīng)用對帶寬和網(wǎng)絡(luò)服務(wù)質(zhì)量的要求。 1 2 組播技術(shù) 1 2 1 簡介 組播技術(shù)可形象的描述如下：假設(shè)一個企業(yè)分布于各地的子公司( 兩個以上) 之間需要通過i n t e m e t 進行實時的交換信息( 數(shù)據(jù)，聲音，圖像) ，他們的計算機可 能不屬于同一物理網(wǎng)絡(luò)，甚至不屬于同一自治系統(tǒng)，這種通信的特點是“多點” 式的。子公司發(fā)出的數(shù)據(jù)希望其他子公司都能收到，而總部發(fā)出的指示全體子公 司都應(yīng)收到。這種多點通信方式為組內(nèi)廣播，即組播技術(shù)，也稱多播技術(shù)，多目 網(wǎng)關(guān)技術(shù)。 組播傳輸可在數(shù)據(jù)鏈路層( 第二層) 和網(wǎng)絡(luò)層( 第三層) 實現(xiàn)，支持的媒體 類型包括以太網(wǎng)、f d d i 和a r m 。大多數(shù)路由器提供商支持坤組播，不支持彈組 播的網(wǎng)絡(luò)通過組播隧道技術(shù)傳輸組播信息包。 組播首先要解決發(fā)送給誰的問題。按不同應(yīng)用項目( 如體育、文藝、娛樂或 學(xué)習(xí)等) 進行分組，組成員要向組播路由器通過i g m p ( i n t e m e tg m u pm a l l a g e m e n t p r o t o c 0 1 ) 協(xié)議進行注冊登記，用戶主機發(fā)出請示，提出具體組播地址。邛組播的 地址采用d 類p 地址確定組播的組。在i n t e m e t 的“小數(shù)點”表示法中，組播地址 范圍是從2 2 4 o o o 到2 3 4 2 5 5 2 5 5 2 5 5 。為發(fā)送一份d 組播數(shù)據(jù)包，發(fā)送者要確定 一個合適的組播地址，這個地址代表一個組。然后，組播數(shù)據(jù)通過普通的p 發(fā)送 操作發(fā)送出去。 其次要解決的問題是如何接收組播信息，有時在同一網(wǎng)段中有多個組播組的 成員。對于信息的發(fā)送方來說相當(dāng)簡單，但接收方卻十分復(fù)雜。為了能夠正確地 遺傳算法托q o s 組播路由算法中的應(yīng)用 接收感興趣的組播信息數(shù)據(jù)包，主機上的應(yīng)用首先要申請?zhí)囟ńM播組的成員。這 種申請通過i n t e m e t 組管理協(xié)議( i g m p ) 傳送到本網(wǎng)段上的路由器完成，如有必 要，相關(guān)的信息還可能要傳送到發(fā)送方的路由器，這取決于使用的組播路由協(xié)議。 這一步完成，接收主機的網(wǎng)絡(luò)接口卡開始偵聽與新組播組地址相關(guān)的數(shù)據(jù)鏈路層 組播地址。路由器把由發(fā)送方送來的組播數(shù)據(jù)包一跳跳地發(fā)送到有接收者的網(wǎng) 段上的路由器，局域網(wǎng)路由器根據(jù)組播信息包中的組地址轉(zhuǎn)換出與它相關(guān)的數(shù)據(jù) 鏈路層地址，并用這個地址建立數(shù)據(jù)鏈路層的報文。接收方的網(wǎng)絡(luò)接口卡和網(wǎng)絡(luò) 驅(qū)動程序偵聽這個地址，收到該組播包后，將口層的組播數(shù)據(jù)包取出，傳向上層 t c p p 協(xié)議堆棧，從而使數(shù)據(jù)適合用戶的應(yīng)用。 第三個問題是用戶主機在注銷對某個組的興趣時如何通知組播路由器。如果 接收方使用的是i g m p v 2 ，會主動地通知路由器離開。但如果是i g h 佃v 1 主機，注 銷就不會通知路由器，這時服務(wù)器要在一定時間后向本網(wǎng)段發(fā)出查詢，接收主機 的應(yīng)答，若無用戶應(yīng)答，路由器就認為不再有接收者，不會再向該網(wǎng)段上轉(zhuǎn)發(fā)組 播信息。 第四個問題是組播信息的轉(zhuǎn)發(fā)，要根據(jù)所使用的組播路由協(xié)議建立組播轉(zhuǎn)發(fā) 樹。根據(jù)該轉(zhuǎn)發(fā)樹進行組播信息的轉(zhuǎn)發(fā)，當(dāng)某個處于轉(zhuǎn)發(fā)樹中的路由器收到一個 組播信息后，對要轉(zhuǎn)發(fā)的組播包進行拷貝和轉(zhuǎn)發(fā)。如果路由器為最后一跳，組播 包就以廣播的方式傳送到該網(wǎng)段中各主機接收者。 122 組播的特點 與單播應(yīng)用相比，使用組播技術(shù)分發(fā)信息常常能從本質(zhì)上減少整個網(wǎng)絡(luò)帶寬 的需求，一個典型的例子就是音頻與視頻網(wǎng)。這些例子常常用來說明組播的優(yōu)點， 體現(xiàn)在以下幾個方面。 1 帶寬 對于音頻與視頻網(wǎng)來說，大量的用戶經(jīng)常要在大致相同的時間里訪問相同的 信息，如果使用單播，網(wǎng)絡(luò)帶寬的消耗就會呈線性增長。由于典型的m p e g 一2 視 頻信息流需要大約l m b p s 5 m b p s 的帶寬用于流暢且逼真的影像，顯然用組播來 發(fā)送節(jié)目是一種明智的選擇。因為重復(fù)數(shù)據(jù)流被單一傳送所代替，從而使得網(wǎng)絡(luò) 帶寬得到了更有效地使用。 2 服務(wù)器負載 如果音頻與視頻網(wǎng)的網(wǎng)絡(luò)運營商繼續(xù)使用單播傳送機制，隨著用戶的增長， 它將需要不斷增加它的實時音頻服務(wù)器的能力和數(shù)量以滿足連接用戶的增長。當(dāng) 服務(wù)器負載增加到一定程度，服務(wù)器就不能再發(fā)出信息流。如果運營商使用組播 來發(fā)布它們的節(jié)目，那么就不需要購買越來越多高性能的服務(wù)器以滿足客戶數(shù)目 的增長。很明顯組播提供的主要優(yōu)勢在于通過大大減少需要轉(zhuǎn)發(fā)和處理的數(shù)據(jù)量， 從而降低了所需服務(wù)器性能。 3 分布式應(yīng)用 遺傳算法住q 。s 組描路由算法中的應(yīng)用 在單播的情況下，隨著需求與應(yīng)用的增長，多點應(yīng)用不太可能，因為單播通 信中的客戶數(shù)量不能無限增長。而組播幾乎不受客戶數(shù)量增長的限制。 盡管在網(wǎng)絡(luò)里使用組播會帶來許多好處，但是像任何技術(shù)一樣，這項技術(shù)也 有其局限性和不盡如人意的地方，包括不可靠的信息包傳送和組播信息包的復(fù)制。 1 30 0 s 組播 1 3 1 定義 q o s 即服務(wù)質(zhì)量( q u a l i t yo fs e r 、r i c e ) ，指發(fā)送和接收信息的用戶之間以及用戶 與傳輸信息的服務(wù)網(wǎng)絡(luò)之間關(guān)于信息傳輸?shù)馁|(zhì)量約定。q o s 包括用戶要求和網(wǎng)絡(luò) 服務(wù)提供者的行為兩個方面。用戶要求指用戶在i n t e m e t 網(wǎng)絡(luò)上進行多媒體通信時 所要求的服務(wù)類型以及相應(yīng)的傳輸性能和質(zhì)量。用戶最關(guān)心的是端到端的q o s ， 由于多媒體應(yīng)用的自身特點，所以多媒體應(yīng)用對網(wǎng)q o s 的要求同時體現(xiàn)：丟包 率、傳送時延、時延抖動、網(wǎng)絡(luò)帶寬等方面。 1 3 2 多播機制中o o s 的必要性 在實際的網(wǎng)絡(luò)中，使用多播機制，o o s 路由技術(shù)是必需的。在多播中，需要 消耗比最大努力的單播多得多的路由器資源。因此，多播的使用者應(yīng)該比單播使 用者交更多的費用。然而，目前此方面的討論還不多，也沒有提出有效的協(xié)議。 可是，預(yù)支持多播的供應(yīng)商迫切需要種合理的計費系統(tǒng)。對于多播通信而言，從 經(jīng)濟的角度看，提供一種允許用戶選擇一條較少費用的路徑也是必需的。否則， 多播供應(yīng)商可能會選擇較高費用的路徑，因而給用戶帶來不必要的費用。選擇滿 足用戶q o s 要求的路徑的方法是不可避免的。沿著滿足q o s 要求的路徑，通過信 令的方法( 也就是q o s 路由技術(shù)) 可以找到這樣的路徑。正如前面所述的，多播中 除了資源預(yù)留功能外，合并功能和復(fù)制功能也是必需的。假定一個未授權(quán)的接收 者向發(fā)送者發(fā)出一個0 0 s 請求。因為對路徑上的路由器而言，要判斷一個請求授 權(quán)與否比較困難，故而q o s 請求被執(zhí)行。因此，從發(fā)送者到一個未授權(quán)接收者之 間的路徑上，0 0 s 也被實現(xiàn)。 1 3 3 服務(wù)質(zhì)量要求 多媒體應(yīng)用對服務(wù)質(zhì)量的要求可歸納為下述幾個主要方面。 1 ) 通信帶寬 時間相關(guān)媒體對網(wǎng)絡(luò)的通信帶寬有最低要求。原理上，時間無關(guān)媒體對網(wǎng)絡(luò) 帶寬不應(yīng)提出最低通信帶寬要求，但是為了保證媒體流之間同步，多媒體中的時 間無關(guān)媒體也存在最低信帶寬問題。例如，當(dāng)電視上的字幕是獨立于電視信號傳 輸?shù)模敲醋帜恍畔⒌膫鬏敱囟ㄓ型ㄐ艓挼淖畹鸵?，否則字幕和電視信號的 同步就無法保證。 多媒體的數(shù)據(jù)速率是各個媒體流數(shù)據(jù)速率之和。多媒體的數(shù)據(jù)速率分平均速 遺傳算法_ f i ：q o s 組播路由箅法中的應(yīng)用 率和峰值速率2 種。網(wǎng)絡(luò)的通信帶寬應(yīng)達到或超過給定多媒體的數(shù)據(jù)速率。非壓 縮媒體的傳輸要占用極大的通信帶寬，因此，信息壓縮是分布式多媒體系統(tǒng)的一 種關(guān)鍵技術(shù)。壓縮媒體的帶寬呈波峰狀變化，對網(wǎng)絡(luò)提出了最高通信帶寬和最低 通信帶寬的要求，因此，q o s 控制就成為分布式多媒體系統(tǒng)的一種非常復(fù)雜的技 術(shù)。 2 ) 延時 不同多媒體應(yīng)用對延時有不同的要求。對于視頻點播系統(tǒng)，視頻流從視頻服 務(wù)器傳送到用戶的機頂盒，其延時的大小對用戶觀看節(jié)目沒有多大影響。但是， 對于交互多媒體系統(tǒng)( 如視頻會議和協(xié)同計算環(huán)境) ，延時是一項重要指標(biāo)，延時 過大將影響交互效果。 網(wǎng)絡(luò)延時由2 部分組成：第一部分為信號傳播時間；第二部分為網(wǎng)絡(luò)設(shè)備( 交 換機，路由器) 排隊調(diào)度時間。信號傳播延時是固定的、不可改變的，但排隊調(diào) 度時間可通過服務(wù)質(zhì)量控制來保證。延時要求一般以延時上界( 最大延時) 的形 式給出，網(wǎng)絡(luò)通過服務(wù)質(zhì)量控制保證媒體流的傳輸不超過延時上界。 3 ) 延時抖動 延時抖動( j i t t e r ) 對時間相關(guān)媒體來說是一項極重要的傳輸性能參數(shù)。延時 抖動指媒體流各單元之間的時間差異。例如，數(shù)字聲音采樣間隔為1 2 5 u s ，通過網(wǎng) 絡(luò)傳輸之后，如果它們之間的時間在1 1 0u s 一1 4 0u s 之間，那么延時抖動為1 5u s 。 延時抖動可在輸出端設(shè)置緩沖器來消除，抖動越大，緩沖器要求越多。用這 種方法消除延時抖動將增加媒體流的端到端延時，因此，網(wǎng)絡(luò)應(yīng)通過服務(wù)質(zhì)量控 制來最大可能的抑制延時抖動。 4 ) 數(shù)據(jù)丟失率 相對于二進制數(shù)據(jù)傳輸來說，音頻和視頻對數(shù)據(jù)丟失率的要求比較低，話音 最大可接受的數(shù)據(jù)丟失率可達1 0 ，視頻可達1 0 。這就減輕了網(wǎng)絡(luò)對差錯控制的 要求。 1 3 4 研究現(xiàn)狀 多媒體高速網(wǎng)絡(luò)的研究開發(fā)近幾年進展得異常迅速，q o s 問題的研究已經(jīng)有了 一些基本成果，這些成果大量地反映在i e e en 盯0 c o m 每年的會議論文集和 h t e m e t 的i e t fr f c ( r e q u e s tf o rc o m m e n t s ) 標(biāo)準(zhǔn)草案中。但是，目前q o s 的研究開 發(fā)在很多方面仍然是開放的，其主要問題有：( 1 ) 網(wǎng)絡(luò)系統(tǒng)狀態(tài)和鏈路帶寬容量變 化的不確定性，傳輸通路端一到一端帶寬預(yù)留缺乏有效的保證；( 2 ) q o s 選路、資源 預(yù)留和信息傳輸調(diào)度算法的復(fù)雜性，還不能適應(yīng)高速信息傳輸處理時間的要求；( 3 ) 0 0 s 要求所導(dǎo)致的資源利用的無效性，不能充分利用網(wǎng)絡(luò)資源提高網(wǎng)絡(luò)的吞吐量； ( 4 ) q o s 控制方案基本上還是靜態(tài)方案，缺乏有效的動態(tài)控制方案；( 5 ) 一些基本 研究成果主要存在于理論中，還沒有形成專利或技術(shù)產(chǎn)品?，F(xiàn)存的網(wǎng)絡(luò)交換機或路 由器還不能完全保證用戶服務(wù)質(zhì)量，缺乏簡單而有效的控制方案和算法的實現(xiàn)，傳 迷傳算法在q 。s 紐播路由算法中的應(yīng)用 輸管理與控制亟待改進。在i n t e m e t 中，為了使i p ( i n t e m e tp r o t o c 0 1 ) 網(wǎng)絡(luò)不僅能傳 輸非實時的數(shù)據(jù)信啟、，而且還能傳輸實時的多媒體信息，國際上的標(biāo)準(zhǔn)化組織，如 i t u ，i e t f 等已開始起草并完成了一些用于口實時通信的標(biāo)準(zhǔn)，如實時傳輸協(xié)議實 時控制協(xié)議r t p r t c p ( r e a l 一t i m ep r o t o c o l r e a l 一c i i l l ec o n t r 0 1p r o t o c 0 1 ) 、資源預(yù)留協(xié)議 r s v p ( r e s o u r c er e s e r v a t j o np r o t o c o j ) 以及h3 2 3 標(biāo)準(zhǔn)等。這些協(xié)議和標(biāo)準(zhǔn)對用戶 服務(wù)質(zhì)量控制的研究提供了一定的基礎(chǔ)，但還有很遠的路要走。 q o s 控制主要包括信息傳輸?shù)膶崟r性和信息丟失的管理與控制等問題。在多 媒體網(wǎng)絡(luò)中，不同用戶可能有不同的傳輸要求。例如，視頻和音頻的傳輸有實時的 要求，超時的信息不能使用，但同時可以容忍某種程度的信息丟失；而數(shù)據(jù)的傳輸 則不容許信息的丟失，但傳輸?shù)臅r延則不成問題。因此，要保證信息傳輸?shù)膶崟r性 和丟失的綜合要求是多媒體網(wǎng)絡(luò)傳輸控制的一個重要問題。 新開發(fā)的路由技術(shù)不再僅僅是為數(shù)據(jù)傳輸找到一條通道就行，還需要考慮所 選路徑的傳輸容量和服務(wù)質(zhì)量，即具有q o s 能力的路由算法，并且還得要分析全 網(wǎng)負荷，以平衡網(wǎng)絡(luò)中各條通道的數(shù)據(jù)流量，此外，不論是對單播還是組播、域 內(nèi)還是域問路由，都要求路由算法具有快速收斂性和高效的路由表查詢技術(shù)。具 有0 0 s 和流量均衡能力的路由算法探索及相應(yīng)規(guī)范的制定將是未來的研究熱點之 1 4 組播路由協(xié)議 為了實現(xiàn)組播通信，就必須建立支持組播的路由協(xié)議根據(jù)對網(wǎng)絡(luò)中的組播成 員的分布和使用的不同，組播路由協(xié)議分為兩類：密集模式路由協(xié)議( d m ) 和稀 疏模式路由協(xié)議( s m ) 。 1 4 1 密集模式路由協(xié)議( d m ) d m ( d e n s e 寸v i o d e ) 路由協(xié)議通常用于組播成員較為集中、數(shù)量較多一網(wǎng)絡(luò)的大 部分用戶、并且有足夠帶寬的網(wǎng)路環(huán)境，比如公司或園區(qū)的局域網(wǎng)。因此，d m 路 由協(xié)議用定期廣播組播報文的方法維護組播分布樹。d m 協(xié)議只使用源分布樹 ( s p t ) ，組播流量被廣播到網(wǎng)絡(luò)中所有的組播路由器。d m 路由協(xié)議有：d 、n 根p 、 m o s p f 、p i m d m 。 1 4 1 1 距離向量組播路由協(xié)議( d v m r p ) d v m i o ：距離向量組播路由協(xié)議( d i s t a n c ev e c t o rm u i i t i c a s tr o u t i n gp r o t o c 0 1 ) 。這是一種基于距離向量算法的組播路由協(xié)議。目前已基本上被p d 訌和m o s p f 所取代。d v m r p 是m b o n e 【2 】上廣泛運用的組播路由協(xié)議，它采用距離向量算法。 在m b o n e 上采用隧道( t u n n e l i n g ) 技術(shù)，使組播通信得以在支持組播的子網(wǎng)之間實 現(xiàn)。由于m b o n e 的飛速發(fā)展，由d r p 而導(dǎo)致的大量路由控制分組定期在網(wǎng)絡(luò) 中的擴散開銷限制了網(wǎng)絡(luò)規(guī)模的發(fā)展。為此提出了分層d v m r p ( h i e r a r c h i c a l d v m r p ) ，按照區(qū)域分割的方式對m b o n e 進行多層管理，區(qū)域內(nèi)組播可以按照任 何協(xié)議進行，而區(qū)域之間的組播由邊界路由器在d v m r p 協(xié)議下進行。由于采用 遺傳算法牲q o s 組播路由算法中的應(yīng)用 組播協(xié)議的層次疊加，減少了路由控制信息開銷。 141 2 組播開放式最短路由優(yōu)先協(xié)議( m 0 s p f ) m o s p f ：組播0 s p f 協(xié)議( m u l t i c a s to p e n s h o r t e s tp a t hf i r s t ) 引。m 0 s p f 是利 用點到點的鏈路狀態(tài)數(shù)據(jù)庫，以o s p fv 2 為基礎(chǔ)的組播路由協(xié)議。由于o s p f 應(yīng) 用d i k s t r a 算法進行路由選擇，因此每個節(jié)點都要保存全網(wǎng)的拓撲信息。所有節(jié)點 對網(wǎng)絡(luò)的看法是一致的，它不需發(fā)送任何分組，節(jié)點就可根據(jù)全網(wǎng)鏈路狀態(tài)表計 算組中每個信源的組播樹，而且各節(jié)點對該樹的看法一致。因此，鏈路利用率比 d v m r p 高。為了減少計算量，m 0 s p f 可以按需執(zhí)行算法，即只有當(dāng)一個節(jié)點收 到一個信源關(guān)于某個組播組的第一個分組時，才執(zhí)行算法。這種做法的缺點是對 第一個分組帶來較大延時。m o s p f 的最大優(yōu)點是享有o s p f 對網(wǎng)絡(luò)拓撲的變動快 速反應(yīng)能力。然而這個能力是以路由器c p u 資源的巨大消耗為基礎(chǔ)的。而且隨著 網(wǎng)絡(luò)中組數(shù)量的增加，這種消耗也在迅速增加。 141 3 協(xié)議無關(guān)組播協(xié)議一密集模式( p i m d m ) p “一d m ：協(xié)議無關(guān)組播協(xié)議一密集模式( p r o t o c a li n d 印e n d e n t m u l t i c a s t d e n s e m o d e 。它不需要單獨的組播協(xié)議，利用路由器上單播路由協(xié)議的路由表 作反向路徑轉(zhuǎn)發(fā)檢查，由此獲得組播分布樹。相比另兩種協(xié)議，p d 訌一d m 的開銷 要小很多，它用于組播源和目的非?？拷?、接收者數(shù)量大于發(fā)送者數(shù)量并且組播 流量比較大的環(huán)境中效果很好。 j 4 2 稀疏模式路由協(xié)議( s m ) 在網(wǎng)路中稀疏分布、網(wǎng)絡(luò)也沒有充足帶寬的情況，如廣域網(wǎng)環(huán)境，可以使用 s m ( s p a r s e m o d e ) 路由協(xié)議。因此，s m 路由協(xié)議采用選擇性的建立和維護分布樹 的方式，由空樹開始，僅當(dāng)成員顯式的請求加入分布樹才做出修改。s m 路由協(xié)議 有：p v i s m 和c b t 。 1 4 2 1 有核樹組播路由協(xié)議( c b t ) c b t ：基于中心的分布樹協(xié)議( r f c2 2 0 1 ) ( c o r e - b a s e dt r e e s ) 。協(xié)議由以一個 中心的路由器為根構(gòu)造一個共享分布樹，所有的組播流量都經(jīng)由這個中心路由器 轉(zhuǎn)發(fā)。 14 2 2 協(xié)議無關(guān)組播協(xié)議一稀疏模式( p i m s m ) p i m s m ：協(xié)議無關(guān)組播協(xié)議一稀疏模式吼工作原理與p d 訌一d m 類似，但 專門針對稀疏環(huán)境優(yōu)化。適用于組播組中接收者較少、間歇性組播流量的情況。 不同于p d v 工一d m 的廣播方式，p m i s m 定義了一個集合點( r p ) ，所有的接收者在 r p 注冊，組播分組由r p 轉(zhuǎn)發(fā)給接收者。 1 4 2 3 a t m 網(wǎng)絡(luò)條件下的對組播路由的支持協(xié)議 a t m 論壇定義了a t m 對組播的支持。當(dāng)前a t m 標(biāo)準(zhǔn)沒有對組地址進行規(guī)范， 信源必須知道所有組成員的地址，建立點到多點虛電路( v c ) ，成員的加入和離開 由信源管理，因而點到多點v c 不能提供對大多數(shù)組通信需求的靈活支持。 遺傳算法以0 0 s 組播路由算法中的應(yīng)用 a t m 論壇給出了兩種支持組播的建議模式【6 】，v c 網(wǎng)絡(luò)模式是建立從信源到組 中所有成員的點到多點v c ，當(dāng)成員的加入和離開之后需要重新v c 。組播服務(wù)器 模式指選擇一個服務(wù)器作為代理，組內(nèi)每個信源與組播服務(wù)器建立點到點v c 連 接。由組播服務(wù)器向一個組中的所有信宿建立組播服務(wù)器點到多點v c 。組播服務(wù) 器接收組中所有信源的數(shù)據(jù)，交織之后發(fā)送到相應(yīng)點到多點v c 上。v c 網(wǎng)絡(luò)的通 量性能比組播服務(wù)器要好，延遲??；但組播服務(wù)器更適合于對組成員的動態(tài)管理。 另外一種s m a r t 模式采用了共享a t m 組播樹，由文獻 7 】提出，協(xié)議通過對 給定多點應(yīng)用分配一至多個多點到多點a t m 虛通道連接( v c c ) ，構(gòu)造組播樹實現(xiàn) 多點間通信。 對于組播的研究早在8 0 年代就已經(jīng)開始有許多組播路由協(xié)議已經(jīng)投入使用。 像p 、m b g p ( m u t i c a s tb o r d e rg a t e w a yp r o t o c 0 1 ) 以及d r p 等協(xié)議的應(yīng)用都 比較廣泛，但是目前還沒有一種可靠的組播協(xié)議已經(jīng)具備了處理大范圍的組分發(fā)、 發(fā)送者要求的反饋或各種類型使用路由器應(yīng)用的能力。 1 5 組播的應(yīng)用 由于組播能有效減少網(wǎng)絡(luò)和主機開銷，較單播和廣播有其獨特優(yōu)越性，因此， 組播已經(jīng)得到了廣泛的應(yīng)用。組播應(yīng)用大致可以分為三類：點對多點應(yīng)用，多點 對點應(yīng)用和多點對多點應(yīng)用。 1 5 1 點對多點的應(yīng)用 點對多點應(yīng)用是指一個發(fā)送者，多個接收者的應(yīng)用形式，這是最常見的組播 應(yīng)用形式。典型的應(yīng)用包括： 媒體廣播：如演講、演示、會議等按日程進行的事件。其傳統(tǒng)媒體分發(fā)手段 通常采用電視和廣播。這一類應(yīng)用通常需要一個或多個恒定速率的數(shù)據(jù)流，當(dāng)采 用多個數(shù)據(jù)流( 如語音和視頻) 時，往往它們之間需要同步，并且相互之間有不 同的優(yōu)先級。它們往往要求較高的帶寬、較小的延時抖動，但是對絕對延時的要 求不是很高。 媒體推送：如新聞標(biāo)題、天氣變化、運動比分等一些非商業(yè)關(guān)鍵性的動態(tài)變 化的信息。它們要求的帶寬較低、對延時也沒有什么要求。 信息緩存：如網(wǎng)站信息、執(zhí)行代碼和其他基于文件的分布式復(fù)制或緩存更新。 它們對帶寬的要求一般，對延時的要求也一般。 事件通知：如網(wǎng)絡(luò)時間、組播會話日程、隨機數(shù)字、密鑰、配置更新、有效 范圍的網(wǎng)絡(luò)警報或其他有用信息。它們對帶寬的需求有所不同，但是一般都比較 低，對延時的要求也一般。 狀態(tài)監(jiān)視：如股票價格、傳感設(shè)備、安全系統(tǒng)、生產(chǎn)信息或其他實時信息。 這類帶寬要求根據(jù)采樣周期和精度有所不同，可能會有恒定速率帶寬或突發(fā)帶寬 要求，通常對帶寬和延時的要求一般。 遺傳算法往q o s 組播路由算法中的應(yīng)用 152 多點對多點的應(yīng)用 多點對多點應(yīng)用是指多個發(fā)送者和多個接收者的應(yīng)用形式。通常，每個接收 者可以接收多個發(fā)送者發(fā)送的數(shù)據(jù)，同時，每個發(fā)送者可以把數(shù)據(jù)發(fā)送給多個接 收者。典型應(yīng)用包括： 多點會議：通常音視頻和白板應(yīng)用構(gòu)成多點會議應(yīng)用。在多點會議中，不同 的數(shù)據(jù)流擁有不同的優(yōu)先級。傳統(tǒng)的多點會議采用專門的多點控制單元來協(xié)調(diào)和 分配它們，采用組播可以直接由任何一個發(fā)送者向所有接收者發(fā)送，多點控制單 元用來控制當(dāng)前發(fā)言權(quán)。這類應(yīng)用對帶寬和延時要求都比較高。 資源同步：如日程、目錄、信息等分布數(shù)據(jù)庫的同步。它們對帶寬和延時的 要求一般。 并行處理：如分布式并行處理。它對帶寬和延時的要求都比較高。 協(xié)同處理：如共享文檔的編輯。它對帶寬和延時的要求一般。 遠程學(xué)習(xí)：這實際上是媒體廣播應(yīng)用加上對上行數(shù)據(jù)流( 允許學(xué)生向老師提 問) 的支持。它對帶寬和延時的要求一般。 討論組：類似于基于文本的多點會議，還可以提供一些模擬的表達。 1 5 3 多點對點的應(yīng)用 多點對點應(yīng)用是指多個發(fā)送者，一個接收者的應(yīng)用形式。通常是雙向請求響 應(yīng)應(yīng)用，任何一端( 多點或點) 都有可能發(fā)起請求。典型應(yīng)用包括： 資源查找：如服務(wù)定位，它要求的帶寬較低，對時延的要求一般。 數(shù)據(jù)收集：它是點對多點應(yīng)用中狀態(tài)監(jiān)視應(yīng)用的反向過程。它可能由多個傳 感設(shè)備把數(shù)據(jù)發(fā)回給一個數(shù)據(jù)收集主機。帶寬要求根據(jù)采樣周期和精度有所不同， 可能會有恒定速率帶寬或突發(fā)帶寬要求，通常這類應(yīng)用對帶寬和延時的要求一般。 網(wǎng)絡(luò)竟拍：拍賣者拍賣產(chǎn)品，而多個竟拍者把標(biāo)價發(fā)回給拍賣者。 信息詢問：詢問者發(fā)送一個詢問，所有被詢問者返回應(yīng)答。通常這對帶寬的 要求較低，對延時不太敏感。 j u k eb o x ：如支持準(zhǔn)點播( n e a r o n d e m a l l d ) 的音視頻倒放。通常接收者采用 “帶外的”協(xié)議機制( 如h t t p 、r t s p 、s m t p ，也可以采用組播方式) 發(fā)送倒放 請求給一個調(diào)度隊列。它對帶寬的要求較高，對延時的要求一般。 1 6 本文的重要研究內(nèi)容 目前推廣組播網(wǎng)絡(luò)技術(shù)的困難在于組播應(yīng)用難以提供有效的用戶認證和計費 手段，缺乏成熟的商業(yè)化基礎(chǔ)；同時，還缺乏有效的手段保證服務(wù)質(zhì)量( q o s ) ， 包括延時、丟失率和對異質(zhì)鏈路的支持等。q o s 組播路由問題是一個n p 完全問題， 如何較好的解決該問題已成為網(wǎng)絡(luò)資源優(yōu)化問題研究的熱點之一。目前已有采用 啟發(fā)式算法和神經(jīng)網(wǎng)絡(luò)算法等來解決此類問題，但還存在各種缺點，如結(jié)果不夠 穩(wěn)定，性能不能得到保證等。 迷傳算法扯q o s 組播路由算法中的應(yīng)用 遺傳算法是近幾年發(fā)展起來的一種嶄新的全局優(yōu)化算法，特別適合于處理傳 統(tǒng)搜索算法解決不好的復(fù)雜和非線性問題，并已顯示了良好的性能和效果。本論 文主要研究遺傳算法在該問題中的應(yīng)用。 圍繞這個主題，本論文共分成七章： 第章是緒論，對計算機網(wǎng)絡(luò)的組播通信進 亍綜述，主要介紹了組播引入的 背景、特點、組播技術(shù)，還敘述了q o s 的相關(guān)內(nèi)容、研究現(xiàn)狀、組播路由協(xié)議和 應(yīng)用。 第二章是研究的基礎(chǔ)部分，介紹了q o s 的描述參數(shù)、數(shù)學(xué)模型、存在問題以 及組播路由算法研究現(xiàn)狀 第三章介紹了遺傳算法的歷史、特點、優(yōu)缺點和應(yīng)用，還介紹遺傳算法的基 本步驟、混合遺傳算法，還包括在遺傳算法中用于解決約束優(yōu)化問題的常用方法。 端到端的延遲和抖動延遲是兩個較關(guān)鍵的性能參數(shù)。在第四章和第五章中分 別討論了如何用g a 求解時延約束的組播路由問題、時延和時延抖動約束的組播 路由問題，同時針對有時延限制的組播路由問題，提出了一種新的混合遺傳算法， 其采用啟發(fā)式和遺傳算法相結(jié)合的策略，改進了編碼和解碼，使算法編碼大大簡 化。實驗表明，該算法能加速遺傳進化，提高進化過程中的搜索效率。 第六章討論了有度約束情況下的組播問題，給出了基于遺傳算法的求解算法。 第七章考慮多個約束的組播路由問題中，運用遺傳算法解決上述問題的2 種 算法，并提出了一種綜合q o s 參數(shù)約束的組播路由算法。 最后，對本文所做的工作做了一個總結(jié)，并對組播路由通信問題的求解進行 展望。 遺傳算法赴q o s 組播路由箅法中的應(yīng)用 第二章組播路由選擇算法 2 1i n t e r n e t 中的路由選擇 2 11 定義 路由選擇是指為發(fā)送報文分組選擇一條路徑的過程，在抽t e m e t 中通過路由器 完成這種選擇。路徑選擇算法的好壞關(guān)系到網(wǎng)絡(luò)資源利用率和網(wǎng)絡(luò)性能的高低。 從理論上講，路由選擇軟件應(yīng)當(dāng)考慮網(wǎng)絡(luò)負荷、數(shù)據(jù)報長度、數(shù)據(jù)報報頭中規(guī)定 的服務(wù)類型等情況，但由于實現(xiàn)上的困難，通常以最短路由為前提進行路由選擇。 i n t e m e t 中的路由選擇算法通常使用路由選擇表，表中的每一項是一對地址 ( n ，r ) ，其中n 是報宿網(wǎng)絡(luò)地址，而r 是下一個路由器的p 地址。計算機使用 的路由選擇表中列出的所有路由器都必須在該計算機直接連接的各個網(wǎng)絡(luò)上，這 樣，該計算機就可以直接到達這些路由器。 21 2 路由選擇算法設(shè)計目標(biāo) 路由選擇算法通常具有下列一個或多個設(shè)計要求： 1 最優(yōu)性 2 簡易性和低開銷 3 強壯性和穩(wěn)定性 4 快速收斂性 5 靈活性 最優(yōu)性是指路由選擇算法選擇最優(yōu)路徑的能力。最優(yōu)路徑取決于計量標(biāo)準(zhǔn)和 用于計算的權(quán)值，例如一個路由選擇算法可以同時使用站點的數(shù)日和延遲開銷， 但在計算過程中更重視延遲開銷，因此，路由選擇協(xié)議必須嚴格定義其計算方法。 路由選擇算法應(yīng)盡可能地簡單。換言之，路由選擇算法必須用量少的軟件和 最低的開銷來提供最有效的功能，實現(xiàn)路由選擇算法的軟件運行在有限物理資源 的計算機上，效率顯得尤為重要。 路由選擇算法必須具有強壯性，這意味著它們必須在出現(xiàn)異常或非預(yù)見性情 況時( 如硬件故障，高負荷狀態(tài)和不正確的操作) ，也能正常運行，由于路由器位 于網(wǎng)絡(luò)連接點上它們發(fā)生故障會引起更為嚴重的問題，因此，最佳路由選擇算法 必須經(jīng)受時間的考驗，且在各種不同的網(wǎng)絡(luò)環(huán)境下有很好的穩(wěn)定性。 此外，路由選擇算法必須能夠迅速收斂，收斂是所有路由器在最佳路徑上取 得一致的過程，當(dāng)一個網(wǎng)絡(luò)由于某種事件造成路由停機或開通時，路由器就會發(fā) 送修正路由消息，該消息在網(wǎng)絡(luò)上傳播，引發(fā)路由器重新計算最優(yōu)路由，并最終 促使所有路由器承認新的最優(yōu)路由。路由選擇算法收斂過慢，會導(dǎo)致路由循環(huán)或 網(wǎng)絡(luò)發(fā)生故障。 路由選擇算法還應(yīng)當(dāng)具有靈活性，這就意味著路由選擇算法必須迅速準(zhǔn)確地 遺傳算法詛：o o s 組播路由算法中的應(yīng)用 適應(yīng)不同的網(wǎng)絡(luò)環(huán)境。例如假設(shè)某網(wǎng)段失敗，路由選擇算法在意識到這個問題 后，應(yīng)能盡快為所有路由選擇最佳路徑，避免使用那段網(wǎng)絡(luò)。路由選擇算法在設(shè) 計時應(yīng)能適應(yīng)網(wǎng)絡(luò)帶寬，路由器隊列大小和網(wǎng)絡(luò)延遲以及其它的變化。 2 1 3 路由選擇算法類型 按類型劃分，路由選擇算法主要包括以下幾種： 1 靜態(tài)和動態(tài)路由選擇算法 2 單路徑和多路徑路由選擇算法 3 平面和分層路由選擇算法 4 主機智能和路由器智能路由選擇算法； 5 域內(nèi)和域間路由選擇算法； 6 鏈接狀態(tài)和距離向量路由算法 路由算法形式多樣，得到廣泛應(yīng)用的有兩種：距離向量算法和鏈路狀態(tài)算法。 目前大多數(shù)路由協(xié)議都是基于這兩種路由算法之一。 2 1 3 1 距離向量算法 距離向量算法( d i s t a i l c e v e c t o ra l g o r i t h m ) 是基于下面的計算公式：d ( i ，i ) = o 、 d ( i j ) = m i n d ( i ，k ) + d ( 幻) 。其中，d ( i j ) 表示從節(jié)點( 節(jié)點為網(wǎng)絡(luò)或路由器) i 到節(jié) 點i 的最短路徑，d ( i ，k ) 表示從節(jié)點i 到k 的直接路徑，也就是說節(jié)點i 和k 之間沒 有中介節(jié)點。 具體運算步驟如下： ( 1 )