--路由算法詳解課件

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 路由選擇算法的分類(lèi) 5.1.2 對(duì)路由選擇算法的要求 5.1.3 路由算法的實(shí)現(xiàn)路由表 5.2 常用的路由算法 5.4 數(shù)學(xué)基礎(chǔ)圖論 5.5 最短路徑算法 5.1 路由算法概述 (1) 網(wǎng)絡(luò)層的功能包括尋址和選擇路由，建立、保持和終止網(wǎng)絡(luò)連接等。 路由算法是網(wǎng)絡(luò)層的核心，其主要功能是指引分組通過(guò)通信子網(wǎng)到達(dá)正確的目的節(jié)點(diǎn)。具體表現(xiàn)

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

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

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

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

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

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

8、5.2 常用的路由算法 (1) 不同的應(yīng)用場(chǎng)合對(duì)路由算法有不同的要求。 廣域網(wǎng)內(nèi)的路由主要解決子網(wǎng)內(nèi)分組的傳輸路徑問(wèn)題，它主要包括三種路由算法： 廣播 最短路由 最佳路由 互連網(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)中最常用的方式，用來(lái)傳播公共信息、拓?fù)渥兓畔ⅲòü?jié)點(diǎn)和鏈路工作變化和故障等信息）。 廣播分組的接收節(jié)點(diǎn)通常是全網(wǎng)所有成員。如果接收節(jié)點(diǎn)為一個(gè)組或部分網(wǎng)絡(luò)節(jié)點(diǎn)，則稱(chēng)為多播（Multicast）。5

9、.2 常用的路由算法 (3) 廣播中的路由算法 (2) 可以逐一地把要廣播的分組按照點(diǎn)對(duì)點(diǎn)的路由算法（Unicast）發(fā)送給每一個(gè)目的節(jié)點(diǎn)，但這種方法可能會(huì)浪費(fèi)大量的網(wǎng)絡(luò)資源，并且廣播節(jié)點(diǎn)需要知道全網(wǎng)所有節(jié)點(diǎn)的路由信息。廣播時(shí)采用的路由算法可以有多種方法：如泛洪（Flooding）路由、采用生成樹(shù)（Spanning Tree）的廣播方式等。5.2 常用的路由算法 (4) 廣域網(wǎng)內(nèi)的路由主要解決子網(wǎng)內(nèi)分組的傳輸路徑問(wèn)題，它主要包括三種路由算法： 廣播 最短路由 最佳路由 互連網(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) 許多實(shí)際的路由算法如RIP（Routing Information Protocol），OSPF（Open Shortest Path First）等都是基于最短路徑這一概念。 分組交換網(wǎng)絡(luò)的各種路由算法實(shí)質(zhì)上都是建立在某種形式的最小費(fèi)用準(zhǔn)則的基礎(chǔ)上。 譬如，我們把準(zhǔn)則定為“最短路徑”，那就有 “最短路徑路由算法”； 注意：這里所說(shuō)的“最短路徑”并不單純意味著一條物理長(zhǎng)度最短的通路，它可以是從發(fā)送節(jié)點(diǎn)到達(dá)接收節(jié)點(diǎn)的中轉(zhuǎn)次數(shù)最少。5.2 常用的路由算法 (6) 最短路

11、由（Shortest Path Routing） (2) 最短路由關(guān)心一個(gè)節(jié)點(diǎn)對(duì)之間的一條路徑的選擇和求解，因而有兩個(gè)方面的缺陷： 為每對(duì)節(jié)點(diǎn)之間僅提供一條路由，因而限制了網(wǎng)絡(luò)的通過(guò)量； 適應(yīng)業(yè)務(wù)變化的能力受到防止路由振蕩的限制。5.2 常用的路由算法 (7) 廣域網(wǎng)內(nèi)的路由主要解決子網(wǎng)內(nèi)分組的傳輸路徑問(wèn)題，它主要包括三種路由算法： 廣播 最短路由 最佳路由 互連網(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é)點(diǎn)到達(dá)接收節(jié)點(diǎn)的信息流的時(shí)延最小、流量最大，而不是局限于一條所謂的最短路徑。采用最佳路由（基于平均時(shí)延最佳化）可以克服最短路徑的上述缺陷，它可以將節(jié)點(diǎn)對(duì)之間的流量分配在多條路徑上，從而可使網(wǎng)絡(luò)的通過(guò)量最大，時(shí)延最小。第5章 內(nèi)容概述 5.1 路由算法概述 5.2 常用的路由算法 5.4 數(shù)學(xué)基礎(chǔ)圖論 5.5 最短路徑算法 5.3 數(shù)學(xué)基礎(chǔ)圖論 (1) 每一個(gè)網(wǎng)絡(luò)都可以抽象成一個(gè)圖。一個(gè)圖G由一個(gè)非空的節(jié)點(diǎn)集合 N 和節(jié)點(diǎn)間的鏈路 A 組成，即 G= ( V , E)。 有方向/無(wú)方向 如果節(jié)點(diǎn)i和j之間僅有i j 的鏈路，則稱(chēng)

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

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

15、方向圖：對(duì)于方向圖的任意兩個(gè)頂點(diǎn)u和v之間存在u到v的路徑和v到u的路徑時(shí)，稱(chēng)該圖為強(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算法是點(diǎn)對(duì)多點(diǎn)的最短路徑算法 Floyd-Warshall算法則是多點(diǎn)對(duì)多點(diǎn)的最短路徑 算法。5.4 最短路徑算法 B-F算法 典型的Bellman-Ford算法（簡(jiǎn)記

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