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

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

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

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

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

6、類 按應用場合 廣域網(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ù)學基礎圖論 5.5 最短路徑算法 5.1.3 路由算法的實現(xiàn)路由表 路由算法的實現(xiàn)通過路由表。 節(jié)點上的路由表指明該節(jié)點如何選擇分組的傳送路徑。節(jié)點1上的路由表節(jié)點4上的路由表目的節(jié)點23456目的節(jié)點12356下一個節(jié)點22442下一個節(jié)點12355 路徑選擇原則是使到達目的節(jié)點的鏈路數(shù)最少。 當存在2條以上具有相同鏈路數(shù)的最少鏈

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

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

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

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

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

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

13、該鏈路是有方向的（或單向鏈路）。 如果節(jié)點i和j之間同時有i j 及j i的鏈路，則稱該鏈路是無方向的（或雙向鏈路）。5.3 數(shù)學基礎圖論 (2) 方向圖：當圖G中的每一條邊都有規(guī)定方向，則稱該圖為有向圖（方向圖）；對應的無方向圖G=(N，A)。 關聯(lián)（Incident）：它表示鏈路與節(jié)點的關系。在方向圖中，鏈路用關聯(lián)的節(jié)點來表示，若A1=(1,2)，則表示鏈路A1關聯(lián)的兩個節(jié)點是1（起點）和2（終點）。 注意：這里討論的圖不允許任何鏈路關聯(lián)的兩個節(jié)點相同，即不允許有一條自環(huán)的鏈路。5.3 數(shù)學基礎圖論 (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ù)學基礎圖論 (4) 連通：對于無方向圖，若節(jié)點u、v之間存在一條路徑（鏈路），則稱u和v是連通的。 若圖G中的任意兩個節(jié)點都是連通的，則稱圖是連通的，否則就是非連通的圖。非聯(lián)通的圖可分解為若干連通的子圖。5.3 數(shù)學基礎圖論 (5) 連通的方向圖：對于方向圖，去掉方向之后該圖是連通的。強連通

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

16、為B-F算法）是一種集中式的點到多點的路由算法，即尋找網(wǎng)絡中一個節(jié)點到其它所有節(jié)點的路由。 假定節(jié)點1是“目的節(jié)點”，我們要尋找網(wǎng)絡中其它所有的節(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次迭代后結束。例 5.25.4 最短路徑算法Dijkstra算法 Dijkstra算法也是一種典型的點到多點的路由算法，即尋找網(wǎng)絡中一個節(jié)點到其它所有節(jié)點的路由。 算法的基本思想是按照路徑長度增加的順序來尋找最短路徑。（也即是通過逐步標定到達目的節(jié)點路徑長度的方法來求解最短的路徑）。 設每個節(jié)點i標定的到達目的節(jié)點1的最短路徑長度估計為Di。如果在迭代的過程中，Di已變成一個確定的值，稱節(jié)點i為永久標定的節(jié)點，這些