--路由算法詳解課件

1、第5章 路由算法Fundamental of Communication Networks 通信網(wǎng)絡(luò)理論基礎(chǔ)第5章 內(nèi)容概述 5.1 路由算法概述 5.2 常用的路由算法 5.4 數(shù)學(xué)基礎(chǔ)圖論 5.5 最短路徑算法 第5章 內(nèi)容概述 5.1 路由算法概述 5.1.1 路由選擇算法的分類 5.1.2 對路由選擇算法的要求 5.1.3 路由算法的實現(xiàn)路由表 5.2 常用的路由算法 5.4 數(shù)學(xué)基礎(chǔ)圖論 5.5 最短路徑算法 5.1 路由算法概述 (1) 網(wǎng)絡(luò)層的功能包括尋址和選擇路由，建立、保持和終止網(wǎng)絡(luò)連接等。 路由算法是網(wǎng)絡(luò)層的核心，其主要功能是指引分組通過通信子網(wǎng)到達(dá)正確的目的節(jié)點。具體表現(xiàn)

2、為兩個方面的內(nèi)容： 尋徑：為不同的源節(jié)點和目的節(jié)點對（SD）選擇一條傳輸路徑； 轉(zhuǎn)發(fā)：在路由選擇好以后，將用戶的消息正確地送到目的節(jié)點。5.1 路由算法概述 (2) 路由選擇的目的和要求： 能正確、迅速、合理地傳送分組（報文）信息。 能適應(yīng)網(wǎng)絡(luò)內(nèi)節(jié)點或鏈路故障而引起的拓?fù)渥兓?，使分組（報文）在有故障的條件下一般還能到達(dá)終點。在發(fā)生故障時，允許某些線路的通信量過載而增加時延。 能適應(yīng)網(wǎng)絡(luò)流量的變化，使各通路的流量均勻，整個網(wǎng)絡(luò)的通信設(shè)備負(fù)荷平衡，充分發(fā)揮效率。 算法盡量簡單，以減少網(wǎng)絡(luò)開銷。 5.1 路由算法概述 (3) 通過一個例子來看看路由選擇對網(wǎng)絡(luò)性能的影響：兩個源節(jié)點和一個目的節(jié)點。所有

3、鏈路的容量為10單位，兩個源節(jié)點1和2的輸入業(yè)務(wù)量分別為1和2, 討論: 1=2=5單位 1=5單位, 2=15單位路由選擇對網(wǎng)絡(luò)性能的影響。5.1 路由算法概述 (4) 當(dāng)1=2=5時 如果節(jié)點1選擇136, 節(jié)點2選擇256, 則由于每條鏈路的業(yè)務(wù)量都只有信道容量的一半, 因而時延很小。 如果節(jié)點1選擇146, 節(jié)點2選擇246, 則鏈路46運(yùn)載的業(yè)務(wù)量為10單位, 達(dá)到了鏈路的最大容量，因而時延會很大。5.1 路由算法概述 (5) 當(dāng)1=5, 2=15時 節(jié)點2的輸入業(yè)務(wù)量為15個單位。由于每條鏈路的容量僅為10個單位，在僅使用一條路徑的情況下，節(jié)點2至少要丟棄5個單位的業(yè)務(wù)流量。 如果

4、節(jié)點2將輸入業(yè)務(wù)流量在246和256之間分?jǐn)?，?jié)點1選擇136，則每條鏈路上的業(yè)務(wù)流量都不超過鏈路容量的75%，因而分組的時延較小。5.1 路由算法概述 (5) 從圖中可以看出：當(dāng)節(jié)點1和2輸入的流量很大時，根據(jù)不同的路由選擇方法，網(wǎng)絡(luò)可接納的最大通過量為1030單位。 由此可以看出：一個路由算法應(yīng)當(dāng)在高業(yè)務(wù)負(fù)荷的情況下，在保證相同的時延條件下，可以增加網(wǎng)絡(luò)的通過量；在輕負(fù)荷和中等負(fù)荷的情況下，可以減少每一個分組的平均時延。第5章 內(nèi)容概述 5.1 路由算法概述 5.1.1 路由選擇算法的分類 5.1.2 對路由選擇算法的要求 5.1.3 路由算法的實現(xiàn)路由表 5.2 常用的路由算法 5.4

5、數(shù)學(xué)基礎(chǔ)圖論 5.5 最短路徑算法 5.1.1 路由選擇算法的分類 (1)路由算法的分類 算法能否跟隨網(wǎng)絡(luò)拓?fù)渥兓?非自適應(yīng)的（不根據(jù)實測或估計的網(wǎng)絡(luò)當(dāng)前業(yè)務(wù)量和拓?fù)浣Y(jié)構(gòu)來做路由選擇。路由事先就計算好，在網(wǎng)絡(luò)啟動時就下載到網(wǎng)絡(luò)路由器中。這種策略的最大優(yōu)點是簡單和開銷?。?自適應(yīng)5.1.1 路由選擇算法的分類 (2)路由算法的分類按路由決策方法 集中式 （指網(wǎng)絡(luò)的路由是由路由控制中心計算的，該中心周期性收集各鏈路的狀態(tài)，經(jīng)過路由計算后周期性地向各網(wǎng)絡(luò)節(jié)點提供路由表。） 分布式（指網(wǎng)絡(luò)中所有節(jié)點通過相互交換路由信息，獨立地計算到達(dá)各節(jié)點的路由。 ）5.1.1 路由選擇算法的分類 (3)路由算法的分

6、類 按應(yīng)用場合 廣域網(wǎng)路由 （解決一個子網(wǎng)內(nèi)的路由） 互聯(lián)網(wǎng)路由 （解決不同子網(wǎng)之間的路由）第5章 內(nèi)容概述 5.1 路由算法概述 5.1.1 路由選擇算法的分類 5.1.2 對路由選擇算法的要求 5.1.3 路由算法的實現(xiàn)路由表 5.2 常用的路由算法 5.4 數(shù)學(xué)基礎(chǔ)圖論 5.5 最短路徑算法 5.1.3 路由算法的實現(xiàn)路由表 路由算法的實現(xiàn)通過路由表。 節(jié)點上的路由表指明該節(jié)點如何選擇分組的傳送路徑。節(jié)點1上的路由表節(jié)點4上的路由表目的節(jié)點23456目的節(jié)點12356下一個節(jié)點22442下一個節(jié)點12355 路徑選擇原則是使到達(dá)目的節(jié)點的鏈路數(shù)最少。 當(dāng)存在2條以上具有相同鏈路數(shù)的最少鏈

7、路數(shù)路徑時，可以選擇其中任意一條。 路由表對每個目的節(jié)點指出分組應(yīng)發(fā)向的下一個節(jié)點。5.1.3 路由算法的實現(xiàn)路由表 當(dāng)路由表建立起來之后，在進(jìn)行路由選擇時只是簡單地查找路由表中的信息，無須再作計算。然而對自適應(yīng)路由選擇來說，會要求相當(dāng)數(shù)量的計算來維持這張路由表。 通常路由表中還會包含一些附加信息，例如基于最少鏈路數(shù)準(zhǔn)則的算法可能包括到達(dá)目的節(jié)點的估計鏈路數(shù)，這樣上表所示的路由表要修改為下表所示的形式。目的節(jié)點23456下一個節(jié)點22442鏈路數(shù)12123包含最少鏈路數(shù)的節(jié)點1上的路由表第5章 內(nèi)容概述 5.1 路由算法概述 5.2 常用的路由算法 5.4 數(shù)學(xué)基礎(chǔ)圖論 5.5 最短路徑算法

8、5.2 常用的路由算法 (1) 不同的應(yīng)用場合對路由算法有不同的要求。 廣域網(wǎng)內(nèi)的路由主要解決子網(wǎng)內(nèi)分組的傳輸路徑問題，它主要包括三種路由算法： 廣播 最短路由 最佳路由 互連網(wǎng)解決不同子網(wǎng)之間的路由，采用的設(shè)備有網(wǎng)關(guān)和路由器等。 Ad Hoc網(wǎng)絡(luò)Ad Hoc網(wǎng)絡(luò)，它是一種分布式的PRNET網(wǎng)絡(luò)，該網(wǎng)絡(luò)中使用了多種形式的路由算法。5.2 常用的路由算法 (2) 廣播中的路由算法 (1) 廣播是通信網(wǎng)中最常用的方式，用來傳播公共信息、拓?fù)渥兓畔ⅲòü?jié)點和鏈路工作變化和故障等信息）。 廣播分組的接收節(jié)點通常是全網(wǎng)所有成員。如果接收節(jié)點為一個組或部分網(wǎng)絡(luò)節(jié)點，則稱為多播（Multicast）。5

9、.2 常用的路由算法 (3) 廣播中的路由算法 (2) 可以逐一地把要廣播的分組按照點對點的路由算法（Unicast）發(fā)送給每一個目的節(jié)點，但這種方法可能會浪費(fèi)大量的網(wǎng)絡(luò)資源，并且廣播節(jié)點需要知道全網(wǎng)所有節(jié)點的路由信息。廣播時采用的路由算法可以有多種方法：如泛洪（Flooding）路由、采用生成樹（Spanning Tree）的廣播方式等。5.2 常用的路由算法 (4) 廣域網(wǎng)內(nèi)的路由主要解決子網(wǎng)內(nèi)分組的傳輸路徑問題，它主要包括三種路由算法： 廣播 最短路由 最佳路由 互連網(wǎng)解決不同子網(wǎng)之間的路由，采用的設(shè)備有網(wǎng)關(guān)和路由器等。 Ad Hoc網(wǎng)絡(luò)Ad Hoc網(wǎng)絡(luò)，它是一種分布式的PRNET網(wǎng)絡(luò)，

10、該網(wǎng)絡(luò)中使用了多種形式的路由算法。5.2 常用的路由算法 (5) 最短路由（Shortest Path Routing） (1) 許多實際的路由算法如RIP（Routing Information Protocol），OSPF（Open Shortest Path First）等都是基于最短路徑這一概念。 分組交換網(wǎng)絡(luò)的各種路由算法實質(zhì)上都是建立在某種形式的最小費(fèi)用準(zhǔn)則的基礎(chǔ)上。 譬如，我們把準(zhǔn)則定為“最短路徑”，那就有 “最短路徑路由算法”； 注意：這里所說的“最短路徑”并不單純意味著一條物理長度最短的通路，它可以是從發(fā)送節(jié)點到達(dá)接收節(jié)點的中轉(zhuǎn)次數(shù)最少。5.2 常用的路由算法 (6) 最短路

11、由（Shortest Path Routing） (2) 最短路由關(guān)心一個節(jié)點對之間的一條路徑的選擇和求解，因而有兩個方面的缺陷： 為每對節(jié)點之間僅提供一條路由，因而限制了網(wǎng)絡(luò)的通過量； 適應(yīng)業(yè)務(wù)變化的能力受到防止路由振蕩的限制。5.2 常用的路由算法 (7) 廣域網(wǎng)內(nèi)的路由主要解決子網(wǎng)內(nèi)分組的傳輸路徑問題，它主要包括三種路由算法： 廣播 最短路由 最佳路由 互連網(wǎng)解決不同子網(wǎng)之間的路由，采用的設(shè)備有網(wǎng)關(guān)和路由器等。 Ad Hoc網(wǎng)絡(luò)Ad Hoc網(wǎng)絡(luò)，它是一種分布式的PRNET網(wǎng)絡(luò)，該網(wǎng)絡(luò)中使用了多種形式的路由算法。5.2 常用的路由算法 (8) 最佳路由（Optimal Routing ）

12、(1) 最佳路由是從全網(wǎng)的范圍尋找所有可能的傳輸路徑，從而使得發(fā)送節(jié)點到達(dá)接收節(jié)點的信息流的時延最小、流量最大，而不是局限于一條所謂的最短路徑。采用最佳路由（基于平均時延最佳化）可以克服最短路徑的上述缺陷，它可以將節(jié)點對之間的流量分配在多條路徑上，從而可使網(wǎng)絡(luò)的通過量最大，時延最小。第5章 內(nèi)容概述 5.1 路由算法概述 5.2 常用的路由算法 5.4 數(shù)學(xué)基礎(chǔ)圖論 5.5 最短路徑算法 5.3 數(shù)學(xué)基礎(chǔ)圖論 (1) 每一個網(wǎng)絡(luò)都可以抽象成一個圖。一個圖G由一個非空的節(jié)點集合 N 和節(jié)點間的鏈路 A 組成，即 G= ( V , E)。 有方向/無方向 如果節(jié)點i和j之間僅有i j 的鏈路，則稱

13、該鏈路是有方向的（或單向鏈路）。 如果節(jié)點i和j之間同時有i j 及j i的鏈路，則稱該鏈路是無方向的（或雙向鏈路）。5.3 數(shù)學(xué)基礎(chǔ)圖論 (2) 方向圖：當(dāng)圖G中的每一條邊都有規(guī)定方向，則稱該圖為有向圖（方向圖）；對應(yīng)的無方向圖G=(N，A)。 關(guān)聯(lián)（Incident）：它表示鏈路與節(jié)點的關(guān)系。在方向圖中，鏈路用關(guān)聯(lián)的節(jié)點來表示，若A1=(1,2)，則表示鏈路A1關(guān)聯(lián)的兩個節(jié)點是1（起點）和2（終點）。 注意：這里討論的圖不允許任何鏈路關(guān)聯(lián)的兩個節(jié)點相同，即不允許有一條自環(huán)的鏈路。5.3 數(shù)學(xué)基礎(chǔ)圖論 (3) 路徑：由一些節(jié)點的序列組成，例如u=（n1,n2,n3nk）稱為一條路徑，也稱為方

14、向性行走（walk）。 給定每條鏈路（i, j）指定一個實數(shù)dij作為其長度，則一條方向性路徑p=（i, j, k, l, m）的長度就是各鏈路長度之和，即d= dij+ djk+dlm 。 最短路徑問題就是尋找從i到m的最小長度方向性路徑。 根據(jù)長度的不同定義，尋找最短路徑的算法有不同的含義。 5.3 數(shù)學(xué)基礎(chǔ)圖論 (4) 連通：對于無方向圖，若節(jié)點u、v之間存在一條路徑（鏈路），則稱u和v是連通的。 若圖G中的任意兩個節(jié)點都是連通的，則稱圖是連通的，否則就是非連通的圖。非聯(lián)通的圖可分解為若干連通的子圖。5.3 數(shù)學(xué)基礎(chǔ)圖論 (5) 連通的方向圖：對于方向圖，去掉方向之后該圖是連通的。強(qiáng)連通

15、方向圖：對于方向圖的任意兩個頂點u和v之間存在u到v的路徑和v到u的路徑時，稱該圖為強(qiáng)連通的。連通的方向圖強(qiáng)連通的方向圖第5章 內(nèi)容概述 5.1 路由算法概述 5.2 常用的路由算法 5.4 數(shù)學(xué)基礎(chǔ)圖論 5.5 最短路徑算法 5.4 最短路徑算法 討論三種標(biāo)準(zhǔn)的集中式最短路徑算法： Bellman-Ford算法（B-F算法） Dijkstra算法 Floyd-Warshall算法 Bellman-Ford算法和Dijkstra算法是點對多點的最短路徑算法 Floyd-Warshall算法則是多點對多點的最短路徑 算法。5.4 最短路徑算法 B-F算法 典型的Bellman-Ford算法（簡記

16、為B-F算法）是一種集中式的點到多點的路由算法，即尋找網(wǎng)絡(luò)中一個節(jié)點到其它所有節(jié)點的路由。 假定節(jié)點1是“目的節(jié)點”，我們要尋找網(wǎng)絡(luò)中其它所有的節(jié)點到目的節(jié)點1的最短路徑。 用dij表示節(jié)點 i 到節(jié)點 j 的長度；如果(i,j)不是圖中的鏈路，則dij=。 最短行走長度用 表示。5.4 最短路徑算法 B-F算法 從h步Walk中尋找最短路由的算法： 第一步：初始化。即對所有i (i1) ，令 =。 第二步：對所有的節(jié)點 j（ji），先找出一條鏈路的最短（ h1）的Walk長度； 第三步：對所有的節(jié)點 j（ j i），再找出兩條鏈路的最短（ h2 ）的Walk長度； 依次類推：如果對所有i有： （即繼續(xù)迭代下去以后不會再有變化），則算法在h次迭代后結(jié)束。例 5.25.4 最短路徑算法Dijkstra算法 Dijkstra算法也是一種典型的點到多點的路由算法，即尋找網(wǎng)絡(luò)中一個節(jié)點到其它所有節(jié)點的路由。 算法的基本思想是按照路徑長度增加的順序來尋找最短路徑。（也即是通過逐步標(biāo)定到達(dá)目的節(jié)點路徑長度的方法來求解最短的路徑）。 設(shè)每個節(jié)點i標(biāo)定的到達(dá)目的節(jié)點1的最短路徑長度估計為Di。如果在迭代的過程中，Di已變成一個確定的值，稱節(jié)點i為永久標(biāo)定的節(jié)點，這些