基于核心路由器的路由選擇最優(yōu)化算法研究與實(shí)現(xiàn)（畢業(yè)論文設(shè)計(jì)-全文預(yù)覽
【正文】 Prim 算法的關(guān)鍵之處是：每次如何從生成樹(shù) T中道 T 外的所有邊中，找出一條最短邊。queue。assoc。 t=(Set::Element(v1))。 Vertex::Number const v1=()。 Edgeamp。amp。p。(())。 edge=dynamic_castWeightedEdgeamp。 queue=*new BinaryHeap(())。 for(Vertex::Number v=0。KruskalsAlgorithm(Graph constamp。當(dāng)從邊集數(shù)組中按次序選取一條邊時(shí)，若它的兩個(gè)端點(diǎn)分屬于不同的集合，則表明此邊聯(lián)通了兩個(gè)不同的連通分量，因每個(gè)連通分量無(wú)回路，所以連通后得到的連通分量仍不會(huì)產(chǎn)生回路，此邊應(yīng)保留作為生成樹(shù)的一條邊，同時(shí)把端點(diǎn)所長(zhǎng)的兩個(gè)集合合并成一個(gè)，即成為一個(gè)連通分量；當(dāng)選取的一條邊的兩個(gè)端點(diǎn)同屬于一個(gè)集合時(shí)，此邊應(yīng)放棄，因同一個(gè)集合中的頂點(diǎn)是連通無(wú)回路的，若再加入一條邊則必產(chǎn)生回路。 } Kruskal 算法原理 假設(shè) G=(V,E)是一個(gè)具有 n 個(gè)頂點(diǎn)的邊帶權(quán)無(wú)向圖， T=（ U,TE）是 G 的最小生成樹(shù)， U 的初值等于 V，即包含有 G 種的全部頂點(diǎn)， TE的初值為空。 for(Vertex::Number v=0。 result=*new DigraphAsLists(n)。assoc。 } ++p。 int const d=table[v0].distance+weight。 v1=()。 While(!()) { WeightedEdgeamp。(())。 assoc=dynamic_castAssocamp。 table[s].distance=0。 s） { unsigned int const n=()。第二個(gè)參數(shù)也是 const 型引用，是一 個(gè)指向起始點(diǎn)（頂點(diǎn)）的引用。 public: Assoc(int p,Objectamp。 int distance。每個(gè)頂點(diǎn)（除b 外）都只有一條發(fā)射邊，把它和它的下一個(gè)頂點(diǎn)連接起來(lái)，逆向構(gòu)造一條 b 至 v 的最短路徑。 在第二遍中， 選擇頂點(diǎn) a，并在數(shù)據(jù)項(xiàng)旁邊標(biāo)記 √以表明至它的最短路徑長(zhǎng)度已經(jīng)知道，從 a 至 c 有一條邊 a→ c。表中√表四最短路徑已經(jīng)知道（ truev ?k ）。 在 每次執(zhí)行過(guò)程中，只有一個(gè)頂點(diǎn)的 kv 設(shè)置為 true。 Dijkstra 算法分階段執(zhí)行，每次都執(zhí)行下列步驟： （ 1） 從 Kv=false 的頂點(diǎn)集合中，選出具有最小估計(jì)距離 Dv 的頂點(diǎn) V。 （ 2） Dv 是從 Vs 到 V 的以知道的最短路徑長(zhǎng)度。按照加權(quán)長(zhǎng)度順序首先找出最短路徑，直至最后找出最長(zhǎng)路徑。作為一種折衷的辦法，許多網(wǎng)絡(luò)試圖使分組必須經(jīng)過(guò)的站點(diǎn)減至最少?？赡芏疾恢肋@一點(diǎn)，于是有必要在全局效率與單個(gè)連接的公平性之間進(jìn)行適當(dāng)?shù)恼壑?。?C 與 C39。 穩(wěn)定性也是路由選擇算法的重要目標(biāo)，有的路由選擇算法不管運(yùn)行了多長(zhǎng)時(shí)間， 都不可能趨于穩(wěn)定， 公平性和最優(yōu)性是顯而易見(jiàn)的 —— 肯定沒(méi)有人反對(duì)，但結(jié)果證明它們常常是矛盾的。對(duì)于這些公司來(lái)說(shuō)他們寧可將數(shù)據(jù)包在自己的鏈路上進(jìn)行傳輸（即使這樣可能增加鏈路延遲）也不愿意花錢(qián)（省時(shí)間）在公用鏈路上傳輸。其中包括 CPU 的利用率和美妙處理數(shù)據(jù)包的次數(shù)。盡管帶寬越大表示鏈路傳輸能力越強(qiáng)，但通過(guò)較大帶寬鏈路的路由并不一定比通過(guò)較慢鏈路的路由更好，因?yàn)槿绻^快的鏈路非常繁忙，那么，通過(guò)它想目的節(jié)點(diǎn)傳送數(shù)據(jù)包所需的實(shí)際時(shí)間可能會(huì)更長(zhǎng)。由于延遲受幾種重要因素的影響，因此，它是一種應(yīng)用最廣且最有用計(jì)量標(biāo)準(zhǔn)。通常由網(wǎng)絡(luò)管理員給網(wǎng)絡(luò)連累分配可靠性等級(jí)。而在路由選擇協(xié)議定義了站點(diǎn)數(shù)的目的情況下，路徑長(zhǎng)度是指數(shù)據(jù)包從源節(jié)點(diǎn)到目的節(jié)點(diǎn)過(guò)程中通過(guò)網(wǎng)絡(luò)產(chǎn)品（路由器）的數(shù)目。 路由選擇計(jì)量標(biāo)準(zhǔn) 前面介紹過(guò)，路由表中包含軟件選擇的最佳路徑的信息，但路由表是如何建立的呢？路由選擇表中包含的信息是什么性質(zhì)的呢？路 由懸著算法又是如何決定最佳路由的呢？ 路由選擇算法使用許多不同的計(jì)量標(biāo)準(zhǔn)確定最佳路由，一些復(fù)雜的路由選擇算法將多多種計(jì)量標(biāo)準(zhǔn)融為一體。實(shí)際上，鏈接狀態(tài)路由算法的更新消息只傳送路由表更新的部分，而距離向量路由算法的更新消息將傳送路由表的大部分或全部傳送到與其相鄰的路由器中。這兩種算法在本質(zhì)上存在不同。在這種系統(tǒng)中，路由器具有路由選擇的智能。 4)主機(jī)智能和路由器智能路由選擇算法 一些路由選擇算法假定源節(jié)點(diǎn)決定整個(gè)發(fā)送路由，這就是通常所說(shuō)的源路由選擇 (so毗 e routlng)。在超大型的網(wǎng)絡(luò)中，可能還存在更多的層次，一般都是位于最高層的路由器形成路由器的主干。在平面路由選擇算法中，所有路由器是對(duì)等的，而在分層路由選擇算法中，路由器被劃分成主干路由器和非主干 路由器。例如為所有無(wú)法選擇 8由的數(shù)據(jù) 包指定一個(gè)最終路由器，即將所有無(wú)法選擇路由的數(shù)據(jù)包轉(zhuǎn)發(fā)到該路由器來(lái)， U保證所有數(shù)據(jù)包都得到某種方式的處理。 20世紀(jì) 90年代以來(lái)，絕大多數(shù)優(yōu)秀的路由選擇算法都是動(dòng)態(tài)的，這些動(dòng)態(tài)路由選擇算法通過(guò)分析接收到的路由修正消息適應(yīng)網(wǎng)絡(luò)環(huán)境的變化。路由選擇算法在設(shè)計(jì)時(shí)應(yīng)能夠適應(yīng)網(wǎng)絡(luò)帶寬，路由器隊(duì)列大小和網(wǎng)絡(luò)延遲等變化。但如果路由器 2還未被更新，它認(rèn)為最優(yōu)路由的下一個(gè)節(jié)點(diǎn)是路由器 2又把數(shù)據(jù)包發(fā)送回路由器 ，數(shù)據(jù)包持續(xù)在這兩個(gè)路由器之間來(lái)回傳送，直到路由器 2收到路由修正命令或者達(dá)到數(shù)據(jù)包允許轉(zhuǎn)發(fā)的最大的次數(shù)為止。當(dāng)一個(gè)網(wǎng)絡(luò)由于某種時(shí)間造成路由設(shè)備停機(jī)或開(kāi)通時(shí)，路由器就會(huì)發(fā)送修正路由信息，該消息在網(wǎng)絡(luò)上傳播，引發(fā)路由器重新 計(jì)算最優(yōu)路由，并最終促使所有路由器承認(rèn)新的最優(yōu)路由。因此，路由選擇算法必須經(jīng)受時(shí)間的考驗(yàn)，且在各種不同的網(wǎng)絡(luò)環(huán)境下有很好的穩(wěn)定性。實(shí)現(xiàn)路由選擇算法的軟件運(yùn)行在物理資 源有限的計(jì)算機(jī)上，效率顯得尤為重要。因此，路由選擇協(xié)議必須嚴(yán)格定義其計(jì)算方法。下面分別討論這些路由選擇算法的特性。他的處理速度是網(wǎng)絡(luò)通信的瓶勁之一，其可靠性則直接影響著網(wǎng)絡(luò)互連的質(zhì)量。 路由器是互聯(lián)網(wǎng)絡(luò)的樞紐，是“交通臺(tái)個(gè)警察”，是互聯(lián)網(wǎng)的主要節(jié)點(diǎn)設(shè)備。一般在路由過(guò)程中，信息會(huì)進(jìn)過(guò)一個(gè)貨多個(gè)中間節(jié)點(diǎn)。在新一代網(wǎng)絡(luò)上提供高 水平服務(wù)質(zhì)量保證己經(jīng)成為目前計(jì)算機(jī)網(wǎng)絡(luò)研究的主要課題。人們?cè)絹?lái)越多地提出了包括多媒體通信在內(nèi)的綜合服務(wù)要求。日益暴增的網(wǎng)絡(luò)流量對(duì)核心路由器的轉(zhuǎn)發(fā)能力提出了新的挑戰(zhàn)，而研究路由選擇算法提高路由選擇的速度對(duì)于提高核心路由器的性能有著重要的意義！ 路由器的定義 路由是 指通過(guò)互相連接的網(wǎng)絡(luò)把信息從源地點(diǎn)移動(dòng)到目標(biāo)地點(diǎn)的活動(dòng)。這一區(qū)別決定了路由和交換在移動(dòng)信息的過(guò)程中需要使用不同的控制信息，所以?xún)烧邔?shí)現(xiàn)各自功能的方式是不同的。作為不同 網(wǎng)絡(luò)之間相互連接的樞紐，路由器系統(tǒng)構(gòu)成了機(jī)遇 TCP/IPD 的國(guó)際互聯(lián)網(wǎng)絡(luò)的主體脈絡(luò)，也可以說(shuō)，路由器構(gòu)成了 Inter 的骨架。首先，算法設(shè)計(jì)者的設(shè)計(jì)目標(biāo)會(huì)影響路由選擇協(xié)議的運(yùn)行結(jié)果；其次，現(xiàn)有各種路由選擇算法對(duì)網(wǎng)絡(luò)和路由器資源的 影響不同；最后，不同的計(jì)量標(biāo)準(zhǔn)也會(huì)影響最佳路徑的計(jì)算結(jié)果。最優(yōu)路徑取決于計(jì)量標(biāo)準(zhǔn)和計(jì)算權(quán)值，例如一個(gè)路由選擇算法同時(shí)考慮途經(jīng)站點(diǎn)的數(shù)目和延遲開(kāi)銷(xiāo)，但在計(jì)算過(guò)程中更重視延遲開(kāi)銷(xiāo)。換句話(huà)說(shuō)，路由選擇算法必須用最低的軟 /硬件開(kāi)銷(xiāo)來(lái)提供最有效的功能。由于路由器位于網(wǎng)絡(luò)節(jié)點(diǎn)上，發(fā)生故障時(shí)會(huì)引起更為嚴(yán)重的問(wèn)題。收斂是指所有路由器都承認(rèn)新的最有路由的過(guò)程。因此，路由器 1 轉(zhuǎn)發(fā)數(shù)據(jù)包到路由器 2。例如假設(shè)某一網(wǎng)段失靈了，路由選擇
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1