北京郵電大學(xué)《計算機網(wǎng)絡(luò)》5

ComputerNetwork

計算機網(wǎng)絡(luò)

北京郵電大學(xué)

計算機學(xué)院

王小茹

THENETWORKLAYER

第5章網(wǎng)絡(luò)層

Parti

基本理論框架

北郵計算機學(xué)院：王小茹

第5章網(wǎng)絡(luò)層

5.1網(wǎng)絡(luò)層的設(shè)計要點

*5,2路由算法

*5.3擁塞控制

*5.4服務(wù)質(zhì)量

*5.5網(wǎng)絡(luò)互聯(lián)

5.6網(wǎng)絡(luò)層IP協(xié)議

北郵計算機學(xué)院：王小茹

5.1NETWORKLAYERDESIGNISSUE

.網(wǎng)絡(luò)層的基本概念

■■網(wǎng)絡(luò)層的目標(biāo):

?將分組從源端沿著網(wǎng)絡(luò)路徑送到目標(biāo)端。

北郵計算機學(xué)院：王小茹

EndtoEndVSPointtoPoint

為什么要創(chuàng)建網(wǎng)絡(luò)層?

，網(wǎng)絡(luò)層與數(shù)據(jù)鏈路層的區(qū)別

■網(wǎng)絡(luò)層是將源端發(fā)出的分組經(jīng)各種途徑送到目的端。

■而數(shù)據(jù)鏈路層僅將數(shù)據(jù)幀從傳輸介質(zhì)的一端送到另一端。

?因此，網(wǎng)絡(luò)層是處理端到端數(shù)據(jù)傳輸?shù)淖畹蛯印?/p>

-網(wǎng)絡(luò)層要解決的關(guān)鍵問題

■路由選擇

■擁塞控制

■網(wǎng)絡(luò)互連

■網(wǎng)絡(luò)層指明端到端的總體路徑方向，數(shù)據(jù)鏈路層

腳踏實地地一條一條鏈路的實現(xiàn)。北郵計算機學(xué)院：王小茹

Store-and-ForwardPacketSwitching

q5ii存儲轉(zhuǎn)發(fā)，分組交換

■硬件結(jié)構(gòu)

■存儲轉(zhuǎn)發(fā)的方式

北郵計算機學(xué)院：王小茹

ServicesProvidedtoTransportLayer

、5.1.2網(wǎng)絡(luò)層提供的服務(wù)

嗎傳輸層提供服務(wù)

?無連接的服務(wù)

每個分組攜帶源地址和目的地址，被直接發(fā)送與接收。

A面向連接的服務(wù)

連接建立、數(shù)據(jù)傳送和連接釋放；

每個分組只攜帶虛電路號沿著建立好的虛電路進行傳輸。

北郵計算機學(xué)院：王小茹

ConnectionlessService

5.1.3無連接的服務(wù)

Transport

Network

Datalink

北郵計算機學(xué)院：王小茹

網(wǎng)絡(luò)隨時接受主機發(fā)送的分組（即數(shù)據(jù)報）

網(wǎng)絡(luò)為每個分組獨立地選擇路由O

也向嗑發(fā)送分組

乩向也發(fā)送分組

路徑可能變化

6

QH5

分組交換網(wǎng)

網(wǎng)絡(luò)盡最大努力地將分組交付給目的主機,

但網(wǎng)絡(luò)對源主機沒有任何承諾。

網(wǎng)絡(luò)不保證所傳送的分組不丟失

也不保證按源主機發(fā)送分組的先后順序

以及在時限內(nèi)必須將分組交付給目的主機

?

?一

HQ分組交換網(wǎng)

當(dāng)網(wǎng)絡(luò)發(fā)生擁塞時

網(wǎng)絡(luò)中的結(jié)點可根據(jù)情況將一些分組丟棄

HQ

數(shù)據(jù)報提供的服務(wù)是不可靠的，

它不能保證服務(wù)質(zhì)量。

實際上“盡最大努力交付”的服務(wù)

就是沒有質(zhì)量保證的服務(wù)。

主機乩先向主機飛發(fā)出一個特定格式的控制信息分組,

要求進行通信，同時尋找一條合適路由。若主機&同意

通信就發(fā)回響應(yīng)，然后雙方就建立了虛電路。

出向嗜發(fā)送的

所有分組都沿此

要和H通信

5虛電路傳送。

虛電路

______

同理，主機也和主機嗑通信之前，也要建立虛電路。

H3g

__

在虛電路建立后，網(wǎng)絡(luò)向用戶提供的服務(wù)就好像在

兩個主機之間建立了一對穿過網(wǎng)絡(luò)的數(shù)字管道。

所有發(fā)送的分組都按順序進入管道，然后按照

先進先出的原則沿著此管道傳送到目的站主機。

HQ分組交換網(wǎng)

到達目的站的分組順序就與發(fā)送時的順序一致，

因此網(wǎng)絡(luò)提供虛電路服務(wù)對通信的

服務(wù)質(zhì)量QoS(QualityofService)有較好的保證。

HQ分組交換網(wǎng)

數(shù)據(jù)報服務(wù)和虛電路服務(wù)

優(yōu)缺點的歸納

對比的方面虛電路服務(wù)數(shù)據(jù)報服

思路可靠通信應(yīng)當(dāng)可靠通信后

由網(wǎng)絡(luò)來保證由用戶主機來保證

連接的建立必須有彳

目的站地址僅在連接建立階段每個分組都笨

使用，每個分組使目的站的全地址

用短的虛電路號

北郵計算機學(xué)院：王小茹

數(shù)據(jù)報服務(wù)和虛電路服務(wù)

優(yōu)缺點的歸納

對比的方面虛電路服務(wù)數(shù)據(jù)報服

分組的轉(zhuǎn)發(fā)屬于同一條虛電路每個分組獨立選

的分組均按照同一路由進行轉(zhuǎn)發(fā)

路由進行轉(zhuǎn)發(fā)

當(dāng)結(jié)點出所有通過出故障的故障結(jié)點可能2

故障時結(jié)點的虛電路分組，一4

均不能工作可能會發(fā)生變

北郵計算機學(xué)院：王小茹

數(shù)據(jù)報服務(wù)和虛電路服務(wù)

優(yōu)缺點的歸納

對比的方面虛電路服務(wù)數(shù)據(jù)報服

服務(wù)質(zhì)量能夠?qū)崿F(xiàn)困難

擁塞控制能夠?qū)崿F(xiàn)困難

北郵計算機學(xué)院：王小茹

數(shù)據(jù)報服務(wù)和虛電路服務(wù)

優(yōu)缺點的歸納

對比的方面虛電路服務(wù)數(shù)據(jù)報

服務(wù)

分組的順序總是按發(fā)送順序到達目的站時不

一定

到達目的站按發(fā)送順

序

端到端的可以由分組交換網(wǎng)由用戶主機

負責(zé)

差錯處理和負責(zé)也可以由用戶北郵計算機學(xué)院：王小茹

___LnAT±7

ROUTINGALGORITHMS

5.2路由算法

■路由算法的概念

■最優(yōu)化的原則

■距離矢量路由

■鏈路狀態(tài)路由

■分級路由

北郵計算機學(xué)院：王小茹

基本概念一路由器的兩個動作

■轉(zhuǎn)發(fā)(forwarding)

■每個分組到達的時候，在路由表中查找該分

組所對應(yīng)的輸出路徑。

■路由選擇(routing)

■使用路由算法。

■負責(zé)填充和更新路由表。

北郵計算機學(xué)院：王小茹

RoutingAlgorithm

.路由算至

?就是產(chǎn)生路由表的算法；

■是網(wǎng)絡(luò)層軟件的一部分。

■子網(wǎng)采用數(shù)據(jù)報方式，每個包都要做路由選擇；

■子網(wǎng)采用虛電路方式，只需在建立連接時做一次路由選擇。

北郵計算機學(xué)院：王小茹

4理想的路由算法

r正確性(correctness):算法必須正確；

，簡單性(simplicity):算法開銷小，效率高；

r健壯性(robustness):算法能適應(yīng)網(wǎng)絡(luò)負荷和拓樸的變化；

，穩(wěn)定性(stability):算法必須收斂，不能振蕩發(fā)散；

振蕩：算法得出的路由是在一些路由之間回蕩。

，公平性(fairness):算法對所有用戶必須是平等的；

，最優(yōu)性(optim疝ty):算法應(yīng)提供最佳路徑選擇；

最佳：鏈路長度、傳輸時延、數(shù)據(jù)速率、鏈路容量、鏈路差錯率、鏈路丟失率等。

北郵計算機學(xué)院：王小茹

Non-adaptiveandAdaptive

路由算法的分類

非自適應(yīng)算法（靜態(tài)路由算法）

■采用離線方式求出路由表

■簡單、開銷小，但不能適應(yīng)網(wǎng)絡(luò)狀態(tài)變化

自適應(yīng)算法（動態(tài)路由算法）

■能適應(yīng)網(wǎng)絡(luò)狀態(tài)變化

■復(fù)雜、開銷大使用？

北郵計算機學(xué)院：王小茹

想想看:

最優(yōu)化原則，對于計算機網(wǎng)絡(luò)中的分組轉(zhuǎn)發(fā)

有什么作用?

如果I,J,K的最佳路由是「產(chǎn)「2,則當(dāng)I把分組交

給J時，J一定會沿著r2把分組轉(zhuǎn)發(fā)出去。

北郵計算機學(xué)院：王小茹

?匯集樹(SinkTree)

A從所有的源結(jié)點到一個給定的目的結(jié)點的最優(yōu)路由

的集合形成了一個以目的結(jié)點為根的樹，稱為

匯集樹(sinktree)

A路由算法的目的是找出并使用匯集樹。

子網(wǎng)路由器B的匯集樹

ShortestPathRouting

.5.2.2最短路徑路由算法

A屬于靜態(tài)路由算法

r基本思想

■構(gòu)建子網(wǎng)的拓撲圖，圖中的每個結(jié)點代表一個路

由器，每條弧代表一條通信線路。為了選擇兩個

路由器間的路由，算法在圖中找出最短路徑。

A測量路徑長度的方法

■結(jié)點數(shù)量

■地理距離

■傳輸延遲

■距離、信道帶寬等參數(shù)的加權(quán)函數(shù)

北郵計算機學(xué)院：王小茹

Dijkstra算法

①每個結(jié)點用從源結(jié)點沿已知最佳路徑到本結(jié)點的距離

家標(biāo)注，標(biāo)注分為臨時性標(biāo)注和永久性標(biāo)注；

②初始時，所有結(jié)點都為臨時性標(biāo)注，標(biāo)注為無窮大；

③將源結(jié)點標(biāo)注為o,且為永久性標(biāo)注，并令其為工作結(jié)

點；

④檢查與工作結(jié)點相鄰的臨時性結(jié)點，若該結(jié)點到工作

結(jié)點的距離與工作結(jié)點的標(biāo)注之和小于該結(jié)點的標(biāo)

注，則用新計算得到的和重新標(biāo)注該結(jié)點；

⑤在整個圖中查找具有最小值的臨時性標(biāo)注結(jié)點，將其

變?yōu)橛谰眯越Y(jié)點，并成為下一輪檢查的工作結(jié)點；

重復(fù)第④、⑤步，直到所有結(jié)點成為工作結(jié)點；

計算機學(xué)院：王小茹

D（8._）

智能科學(xué)與網(wǎng)絡(luò)工程系：王小茹

D(OO-)

VG(5,E)<G(6A)(d)

VC(9,B)=C(9,F),

???G(5,E)取代G(6,A)

???不等就住a

B<2.A)八e（9,B）

AD(?-)

⑻

智能科學(xué)與網(wǎng)絡(luò)工程系：王小茹

結(jié)點A的路由表

結(jié)點A的匯集樹目的站下一站

A

BB

CB

DB

EB

FB

GB

HB

同理，以結(jié)點E為源結(jié)點，采用Dijkstia算法,

求出結(jié)點E的匯集樹和路由表：結(jié)點E的路由表

目的站下一站

結(jié)點E的匯集樹B

A

B

B

F

C

DF

?

E

FF

GG

HF

#defineMAX_NODES1024/*maximumnumberofnodes*/

#defineINFINITY1000000000/*anumberlargerthaneverymaximumpath*/

intn,dist[MAX_NODES][MAX_NODES];/*dist[i][j]isthedistancefromitoj*/

voidshortest_path(ints,intt,intpath[])

{structstate{/*thepathbeingworkedon*/

intpredecessor;/*previousnode*/

intlength;/*lengthfromsourcetothisnode*/

enum{permanent,tentative}label;/*labelstate*/

}state[MAX_NODES];

inti,k,min;

structstate*

P；

for(p=&state[O];p<&state[n];p++){initializestate*/

p->predecessor=—1;

p->length=INFINITY;

p->label=tentative;

}

state[t].length=O;state[t].label=permanent;

k=t;kistheinitialworkingnode*/

do{Isthereabetterpathfromk?*/

for(i=O;i<n;i++)thisgraphhasnnodes*/

if(dist[k][i]]=0&&state[i].label==tentative){

if(state[k].length+dist[k][i]<state[i].length){

state[i].predecessor=k;

state[i].length=state[k].length+dist[k][i];

)

/*Findthetentativelylabelednodewiththesmallestlabel.*/

k=O;min=INFINITY;

for(i=O;i<n;i++)

if(state[i].label==tentative&&state[i].length<min){

min=state[i].length;

k=i;

)

state[k].label=permanent;

}while(k!=s);

/*Copythepathintotheoutputarray.*/

i=0;k=s;

}do{path[i-4-?-]=k;k=state[k].predecessor;}while(k>=O);

透明網(wǎng)橋的“武功秘笈”

北郵計算機學(xué)院：王小茹

擴散算法(Flooding)

■屬于靜態(tài)路由算法

■基本思想

■事先不需要任何網(wǎng)絡(luò)信息；

■路由器把收到的每一個分組，向除了該分組

到來的線路外的所有輸出線路發(fā)送。

■將來會有多個分組的副本到達目的地端，最

先到達的，可能是走了“最優(yōu)”的路徑。

北郵計算機學(xué)院：王小茹

擴散算法：結(jié)點1與6之間的通信，Stepl

擴散算法：Step2

A

<?

擴散算法：Step3

想想看?

如何消除：過時的/重復(fù)的分組?

了算法的優(yōu)點是什么？

■不需要事前知道任何網(wǎng)絡(luò)的拓撲信息；

■所有的網(wǎng)絡(luò)路徑都被嘗試過；

■第一個到達的分組走的路徑可能是最優(yōu)的。

-算法的主要問題是什么？

■產(chǎn)生大量重復(fù)分組。

你該出手了!

北郵計算機學(xué)院：王小茹

I的

決方

■F端收到分組時，在每個分組的頭部增加一個計數(shù)器。

此后，每經(jīng)過一跳該計數(shù)器減1,為。時丟棄。

■計數(shù)器的初值=最佳路徑的跳數(shù)/子網(wǎng)的直徑；

■每個路由器記錄收到已經(jīng)擴散過的分組，從而避免再

次發(fā)送這些分組。

■源端在每個分組中放置一個序號；

■每個收端路由器記錄｛源端地址，序號｝;

■每個路由器將得到的同一源端的分組的最大序列號

分組記錄下來，小于該序號的丟棄。

北郵計算機學(xué)院：王小茹

選擇性擴散算法⑴

▲

▲

▲

選擇性擴散算法（2）

選擇性擴散算法⑶

1

選擇性擴散算法

.(SelectiveFlooding)

建擇性擴散算法是擴散法的一種改進。

■能夠消除多余的分組。

■擴散算法的應(yīng)用情況

■對路由器和線路的資源過于浪費，實際的商用

網(wǎng)絡(luò)很少直接采用；

■具有極好的健壯性，可用于軍事應(yīng)用；

■作為衡量標(biāo)準(zhǔn)評價和初級拓撲消息獲得方式應(yīng)

用于其它路由算法。

北郵計算機學(xué)院：王小茹

動態(tài)路由算法

距離矢量路由算法

鏈路狀態(tài)路由算法

北郵計算機學(xué)院：王小茹

DistanceVectorRouting

15.2.4距離矢量路由算法

?屬于動態(tài)路由算法

最初應(yīng)用于ARPANET,后來應(yīng)用于因特網(wǎng)的RIP協(xié)議（路由信息協(xié)議）。

》基本思想

■每個結(jié)點通過測取與相鄰結(jié)點的距離，再依據(jù)與其相鄰結(jié)點

交換的距離信息，間接地求出路由表；

■各結(jié)點周期性地測取相鄰結(jié)點的距離；

向相鄰結(jié)點發(fā)送它到每個目的結(jié)點的距離表，

同時，它也接收每個鄰居結(jié)點發(fā)來的距離表；

■結(jié)點中的老路由表在計算中不被使用。

北郵計算機學(xué)院：王小茹

目的站延遲下一站

10,

222

353

414

563

683

DIS1

結(jié)點1測取相來自相鄰結(jié)點時延向量結(jié)點1的路由表-更新后

D151

求"12和%：

e

/f/12+r/22=1+0=1

"13+42=4+3=7

"14+42=2+2=4

源站點1：利用中間站點2到達目的站點2。

求"12和%：

,

/f712+rf22=1+0=1

[13+42=4+3=7

〃i4+42=2+2=4

源站點1：利用中間站點3到達目的站點2。

結(jié)點1測取相來自相鄰結(jié)點時延向量結(jié)點1的路由表-更新后

DIS1

?〃12+〃22=1+0=1

"13+42=4+3=7

"14+42=2+2=4

源站點1：利用中間站點4到達目的站點2。

,

/f712+rf22=1+0=1?最小

?二.12=1，$12=2

[13+42=4+3=7

〃i4+42=2+2=4

結(jié)點1測取相來自相鄰結(jié)點時延向量結(jié)點1的路由表-更新后

求：源站點1,目的站點3,分別利用2,3,4O

結(jié)點1測取施1來自相鄰結(jié)點時延向量結(jié)點1的路由表-更新后

鄰結(jié)點的時延站2站3站4

23

pdl2=1032

九=4及302

220

，%4=2***I■.—

311

533

D27)32)4\D161

求"14和*4：求"15和S15：'、\

.?"2+〃24=1+2=3vf/12+f/25=l+>4

"13+"35=4"5

"13+44=4+2亍6

"14+144=240=2一最小"14+〃45=2+1=3一最小

、??

???d14=2,$14=4

,,[15=3,s15=4

結(jié)點1測取木I

鄰結(jié)點的時延

嚴(yán)2=1

及

九二4

回4=2

求“16和%6：

"13+”36

"14+〃46

?.?46=5,

巨離矢

試著扮演一次路由器吧!

北郵計算機學(xué)院：王小茹

初始時,

路由器中的路由表只有到相鄰路由器的信息

器B到C路由器"J"l”表示“距離是1”

1:各個路由器各自重新測量到鄰居的距離；

2：然后把自己上一狀態(tài)的路由表去掉轉(zhuǎn)發(fā)項，

項變成“距離表”發(fā)送出去。

3:收取鄰居發(fā)來的“距離表”，重新計算路由表。

第一次交換開始:

路由器B

BO

C1

DC1C

D0-

更新后

C說

:“我到D的距離是1?！?/p>

此

因現(xiàn)在也可以到

離BD,

距

過

經(jīng)

是2C95

O

路由器C收到相鄰路由器B和D的距離表

路由器D收到相鄰路由器C的距離表

B1B

B0-CO?

C1CD1Dc1c

D0-

B1B

CO-

D1D

最終所有的路由器的路由表都更新了

B0-B1B

C1CC0-

D2CD1D

,對鏈路故障的反應(yīng)

好事傳千里，壞事不出門?。?/p>

一個靠鄰居“謠言”活著的路由協(xié)議

北郵計算機學(xué)院：王小茹

一個好消息，A鏈路修好了!

■思考：

■A需要多久才能獲得全網(wǎng)的路由信息？

■B需要多久才能知道可達A的路由信息?

■C需要多久才能知道可達A的路由信息?

■D需要多久才能知道可達A的路由信息?

B0-B2C

初始時:C1CC1C

D2CDO-

ABD

A0.A1AHLL

B1RKB0.co

Ml、__■

C2BC1cD1D

D3BD2cnnr

A0,A1AA2B

B1BB0-1

DDBB

C2BC1cc°■

D3BD2cDD

A_ll

o■AAA2B

1旦B0-B1B

2Bc1cC0■

3BD2CD1D

總結(jié):

■對鏈路“好消息”的反應(yīng)很快!

■網(wǎng)絡(luò)再次收斂的速度很快！

■正所謂：好事快馬加鞭傳千里!

北郵計算機學(xué)院：王小茹

一個壞消息,A路由器壞了!

北郵計算機學(xué)院：王小茹

A

■思考：

■B需要多久才能知道不可達A的路由信息?

■C需要多久才能知道不可達A的路由信息?

?D需要多久才能知道不可達A的路由信息?

A0

B1BB:A1

2B

D3BC:A2

ABCD

第一次交換時：B、C、D仍把自己的路由表改成距離表，發(fā)送。

第一次交換后：C和D的路由表不變。

一開始，B得知了壞消息：“我無法到A!!!

C卻通過“距離表”說：別著急，我能到達A,嘿嘿!

B收到C的更新報文后，誤認為可經(jīng)過C到達A,于是更

新自己的路由表，說：“我到A的距離是3,下一跳經(jīng)過

C”。然后再等待下次的交換時，將此更新信息發(fā)送給C。

這就是好消息傳播得快，而壞消息傳播得慢。網(wǎng)絡(luò)出

故障的傳播時間往往需要較長的時間（例如數(shù)分鐘）。這

是RIP的一個主要缺點。

1234

DCNDCNDCNDCNDCNDCNDcN

A1AA00-A3CA3CA5CA5CA7c

BC1CC1cC1CC1CC1CC1CC1c

D2CD2cD2cD2cD2cD2cD2c

DCNDCNDCNDCNDCNDCND￡N

AAAADA公D

A2BA2BA2BA6B

I業(yè)J

C十委攵

B1BB1BB1B股隼個斷更新卜云，TBB

D1DD1DD1D劃兀為。D1D

DCNDCNDCNDcNDcNDcNDcN

A3CA3CA3CA3CA5CA5C

D士C

B2CB2CB2CB2CB2CB2CC

C1cC1cC1cC1cC1cC1cc

*time

如何解決上述問題?

先想想：導(dǎo)致上述問題

的本質(zhì)原因是什么？

北郵計算機學(xué)院：王小茹

,如何解決上述問題?

手段L頭疼治頭，腳痛治腳;

手段2：治標(biāo)又要治本！

北郵計算機學(xué)院：王小茹

AD計數(shù)到無窮的問題

1

1

C3規(guī)定一個最大距離（跳數(shù)）：16,

當(dāng)距離=16時，認為網(wǎng)絡(luò)是不可達的?。?/p>

亨CNDCNDCNDCNDCNDCNDcN

A1AA00-A3CA3CA5CA5CA7c

BC1CC1cC1CC1CC1CC1CC1c

D2CD2cD2cD2cD2cD2cD2c

DCNDCNDCNDCNDCNDCNDN

AAAADA公D

A2BA2BA2BA6B

C十麥攵

B1BB1BB1B缺隼個斷更新I、太，TBB

D1DD1DD1D劃兀為。DNF

DCNDCNDCNDcNDcNDcN_?J_EJN

A3CA3CA3CA3CA5CA5C

DC

B2CB2CB2CB2CB2CB2CC

C1cC1cC1cC1cC1cC1cc

*time

、

“我有一條到A的路記住，我是原創(chuàng)!

由”

y

說：“我到A的距離是1”

B:A12B

況AB

我得到了到A的這是由B告

路由消息！訴我的

我要做個標(biāo)記

C說：“我到A的距離是2,是經(jīng)過B?！?/p>

將來我不能向B告知網(wǎng)1的任何消息。

這是“水平分割”技術(shù)。

這是：水平分割+毒性逆轉(zhuǎn)!

L=U

00D

A|A-t=>B仁A8B

說：壞消息：“我無法到達A了?。?！

C說：沒關(guān)系，我能到達！??！

C在收到B的更新報文之前，還發(fā)送原來的報文,

雖然這時C并不知道A出了故障,

但報文是加了毒性逆轉(zhuǎn)的形式。

水平分割vs水平分割+毒性逆轉(zhuǎn)

adnewsisbetterthannonews!

北郵計算機學(xué)院：王小茹

1作業(yè)：分析網(wǎng)絡(luò)協(xié)議的有效性

福通的距離矢量協(xié)議;

2.使用帶水平分割的距離矢量協(xié)議；

3,使用水平分割+毒性逆轉(zhuǎn)方法是否比僅使用水平分

割的方法好？如果能，說明原因；不能，給出什么樣

的拓撲結(jié)果是的水平分割+毒性逆轉(zhuǎn)的方法更好？

北郵計算機學(xué)院：王小茹

5.2.5鏈路狀態(tài)路由算法

.(LinkStateRouting)

-距離向量路由算法的主要問題.

?選擇路由時，沒有考慮線路帶寬；邃

■路由收斂速度慢。起牙

■鏈路狀態(tài)路由算法

?OSPF

?IS-IS

北郵計算機學(xué)院：王小茹

算法的基本操作

問候

確定可達性

問候

數(shù)據(jù)庫描述

數(shù)據(jù)庫描述

達到數(shù)據(jù)庫的同步

數(shù)據(jù)庫描述

數(shù)據(jù)庫描述

鏈路狀態(tài)請求

新情況下的同步鏈路狀態(tài)更新

鏈路狀態(tài)確認

北郵計算機學(xué)院：王小茹

1,發(fā)現(xiàn)鄰居結(jié)點，并學(xué)習(xí)它們的網(wǎng)絡(luò)地址

HELLO

確定可達性

HELLO

■路由器啟動后，通過發(fā)送HELLO包發(fā)現(xiàn)鄰居結(jié)點；

■線路另一端的路由器應(yīng)該送回一個應(yīng)答來說明它是誰。

■這些名字必須是全局唯一的。

北郵計算機學(xué)院：王小茹

2,測量到各鄰居節(jié)點的延遲或者開銷

ECHO

測量鄰居開銷

ECHO

■要求城一個路由器知道它到各個鄰居節(jié)點之間的延

遲，或者至少有一個合理的估計值。

■一種直接的方法是：發(fā)送一個要對方立即響應(yīng)的

ECHO包，來回時間除以2即為延遲。

北郵計算機學(xué)院：王小茹

3.創(chuàng)建鏈路狀態(tài)分組

創(chuàng)建鏈路狀態(tài)分組

BCDEF

A

Seq.Seq.Seq.Seq.Seq.

Seq.

AgeAgeAgeAgeAge

Age

A4B2C3A5B6

B4

C2D3F7C1D7

E5

F6E1F8E8

北郵計算機學(xué)院：王小茹

4.使用擴散法發(fā)布鏈路狀態(tài)分組

鏈路狀態(tài)分組

擴散發(fā)布

鏈路狀態(tài)分組

鏈路狀態(tài)分組

鏈路狀態(tài)分組

達到數(shù)據(jù)庫的同步

鏈路狀態(tài)分組

鏈路狀態(tài)分組

北郵計算機學(xué)院：王小茹

4.使用擴散法發(fā)布鏈路狀態(tài)分組

■為控制洪泛，每個分組含一個序號，每次發(fā)送新分組

時加1。

■路由器記錄信息對（源路由器，序號），當(dāng)一個鏈路狀

態(tài)分組到達時：

-若是新的，則分發(fā)；

-若是重復(fù)的，則丟棄；

■若序號比路由器記錄的最大序號小，則認為過時而丟棄；

北郵計算機學(xué)院：王小茹

使用的是可靠的擴散法

JACK報文

■開動腦筋：存在的問題(1)

具口果序列號回轉(zhuǎn)了，則可能會產(chǎn)生混淆。

■解決辦法：

■使用32位序號；

■即使每秒鐘產(chǎn)生一個鏈路狀態(tài)分組，也需要137

年才可能發(fā)生回轉(zhuǎn)。

北郵計算機學(xué)院：王小茹

B開動腦筋：存在的問題(2)

?如果:

■路由器崩潰后，序號重置；

■或者序號出錯；

■解決方法

■增加年齡(age)域，每秒鐘年齡減1,為零則丟棄。

■鏈路狀態(tài)包到達后，延遲一段時間，并與其它已到達

的來自同一路由器的鏈路狀態(tài)包比較序號，丟棄重復(fù)

包，保留新包；

■鏈路狀態(tài)包需要應(yīng)答;

北郵計算機學(xué)院：王小茹

B2C

43

A\AZ

E8F

SendflagsACKflags

SourceSeq.AgeAcFAcFData

A2160011100

F2160110001

E2159010101

C2060101010

D2159100011

Fig.5-16.ThepacketbufferforrouterBinFig.5-15.

■從E發(fā)來的鏈路狀態(tài)包有兩個，一個經(jīng)過EAB,另

一個經(jīng)過EFB;

■從D發(fā)鏈路狀態(tài)包有兩個，一個經(jīng)過DCB,另一個

經(jīng)過DFB;北郵計算機學(xué)院：王小茹

5.計算到每個其它路由器的最短路徑

■每個路由器都獲得了自己的路由拓撲圖

■據(jù)Dijkstra算法計算最短路徑；

■生成自己的路由表

THEEND

北郵計算機學(xué)院：王小茹

鏈路狀態(tài)算法(LS)

和距離矢量算法(DV)的比較

■路由信息的復(fù)雜性

■LS

-路由信息向全網(wǎng)發(fā)送

■N節(jié)點，E個連接的情況下，每個節(jié)點發(fā)送O(nE)

的報文

■DV

-僅在鄰居節(jié)點之間交換

北郵計算機學(xué)院：王小茹

鏈路狀態(tài)算法(LS)和距離向量

算法(DV)的比較

■收斂(Convergence)速度

-LS

■使用最短路徑優(yōu)先算法，算法復(fù)雜度為O(n**2)

■n個結(jié)點(不包括源結(jié)點)，需要n*(n+1)/2次比較

■使用更有效的實現(xiàn)方法，算法復(fù)雜度可以達到O(nlogn)

■可能存在路由振蕩(oscillations)

■DV

■收斂時間不定

■可能會出現(xiàn)路由循環(huán)

■count-to-infinityfi5]|§

北郵計算機學(xué)院：王小茹

鏈路狀態(tài)算法(LS)和距離向量

算法(DV)的比較

!健壯性：如果路由器不能正常工作會發(fā)生什么?

.LS

結(jié)點會廣播錯誤的鏈路開銷

每個結(jié)點只計算自己的路由表

?DV

結(jié)點會廣播錯誤的路徑開銷

每個結(jié)點的路由表被別的結(jié)點使用，錯誤會傳播到全網(wǎng)

北郵計算機學(xué)院：王小茹

作業(yè)2:

一個通信子網(wǎng),使傭鏈路狀態(tài)路由選擇算法,已知各節(jié)點產(chǎn)生的鏈路

狀態(tài)數(shù)據(jù)包如下2

林小:V0~++標(biāo)示：VI"林?。篤2P林?。篤3「初'?。篤4d

序號:“序號：52序號:加序號：9卡序號:4

Age:1010^Age:1000*21Age:975~Age:800~Age:500，

丫1"82心*V0，心2c心6-

3〃V*3〃⑵⑵3P

2〃恬3〃恬