ComputerNetwork

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

北京郵電大學(xué)

計(jì)算機(jī)學(xué)院

王小茹

THENETWORKLAYER

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

Parti

基本理論框架

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

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

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

*5,2路由算法

*5.3擁塞控制

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

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

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

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

5.1NETWORKLAYERDESIGNISSUE

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

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

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

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

EndtoEndVSPointtoPoint

為什么要?jiǎng)?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ù)鏈路層

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

Store-and-ForwardPacketSwitching

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

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

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

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

ServicesProvidedtoTransportLayer

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

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

?無連接的服務(wù)

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

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

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

每個(gè)分組只攜帶虛電路號(hào)沿著建立好的虛電路進(jìn)行傳輸。

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

ConnectionlessService

5.1.3無連接的服務(wù)

Transport

Network

Datalink

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

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

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

也向嗑發(fā)送分組

乩向也發(fā)送分組

路徑可能變化

6

QH5

分組交換網(wǎng)

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

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

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

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

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

?

?一

HQ分組交換網(wǎng)

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

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

HQ

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

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

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

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

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

要求進(jìn)行通信，同時(shí)尋找一條合適路由。若主機(jī)&同意

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

出向嗜發(fā)送的

所有分組都沿此

要和H通信

5虛電路傳送。

虛電路

______

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

H3g

__

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

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

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

先進(jìn)先出的原則沿著此管道傳送到目的站主機(jī)。

HQ分組交換網(wǎng)

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

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

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

HQ分組交換網(wǎng)

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

優(yōu)缺點(diǎn)的歸納

對(duì)比的方面虛電路服務(wù)數(shù)據(jù)報(bào)服

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

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

連接的建立必須有彳

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

使用，每個(gè)分組使目的站的全地址

用短的虛電路號(hào)

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

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

優(yōu)缺點(diǎn)的歸納

對(duì)比的方面虛電路服務(wù)數(shù)據(jù)報(bào)服

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

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

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

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

故障時(shí)結(jié)點(diǎn)的虛電路分組，一4

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

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

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

優(yōu)缺點(diǎn)的歸納

對(duì)比的方面虛電路服務(wù)數(shù)據(jù)報(bào)服

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

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

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

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

優(yōu)缺點(diǎn)的歸納

對(duì)比的方面虛電路服務(wù)數(shù)據(jù)報(bào)

服務(wù)

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

一定

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

序

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

負(fù)責(zé)

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

___LnAT±7

ROUTINGALGORITHMS

5.2路由算法

■路由算法的概念

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

■距離矢量路由

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

■分級(jí)路由

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

基本概念一路由器的兩個(gè)動(dòng)作

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

■每個(gè)分組到達(dá)的時(shí)候，在路由表中查找該分

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

■路由選擇(routing)

■使用路由算法。

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

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

RoutingAlgorithm

.路由算至

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

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

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

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

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

4理想的路由算法

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

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

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

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

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

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

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

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

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

Non-adaptiveandAdaptive

路由算法的分類

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

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

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

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

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

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

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

想想看:

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

有什么作用?

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

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

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

?匯集樹(SinkTree)

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

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

匯集樹(sinktree)

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

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

ShortestPathRouting

.5.2.2最短路徑路由算法

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

r基本思想

■構(gòu)建子網(wǎng)的拓?fù)鋱D，圖中的每個(gè)結(jié)點(diǎn)代表一個(gè)路

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

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

A測(cè)量路徑長(zhǎng)度的方法

■結(jié)點(diǎn)數(shù)量

■地理距離

■傳輸延遲

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

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

Dijkstra算法

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

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

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

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

點(diǎn)；

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

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

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

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

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

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

計(jì)算機(jī)學(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é)點(diǎn)A的路由表

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

A

BB

CB

DB

EB

FB

GB

HB

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

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

目的站下一站

結(jié)點(diǎn)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)橋的“武功秘笈”

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

擴(kuò)散算法(Flooding)

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

■基本思想

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

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

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

■將來會(huì)有多個(gè)分組的副本到達(dá)目的地端，最

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

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

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

擴(kuò)散算法：Step2

A

<?

擴(kuò)散算法：Step3

想想看?

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

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

■不需要事前知道任何網(wǎng)絡(luò)的拓?fù)湫畔ⅲ?/p>

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

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

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

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

你該出手了!

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

I的

決方

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

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

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

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

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

■源端在每個(gè)分組中放置一個(gè)序號(hào)；

■每個(gè)收端路由器記錄｛源端地址，序號(hào)｝;

■每個(gè)路由器將得到的同一源端的分組的最大序列號(hào)

分組記錄下來，小于該序號(hào)的丟棄。

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

選擇性擴(kuò)散算法⑴

▲

▲

▲

選擇性擴(kuò)散算法（2）

選擇性擴(kuò)散算法⑶

1

選擇性擴(kuò)散算法

.(SelectiveFlooding)

建擇性擴(kuò)散算法是擴(kuò)散法的一種改進(jìn)。

■能夠消除多余的分組。

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

■對(duì)路由器和線路的資源過于浪費(fèi)，實(shí)際的商用

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

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

■作為衡量標(biāo)準(zhǔn)評(píng)價(jià)和初級(jí)拓?fù)湎@得方式應(yīng)

用于其它路由算法。

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

動(dòng)態(tài)路由算法

距離矢量路由算法

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

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

DistanceVectorRouting

15.2.4距離矢量路由算法

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

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

》基本思想

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

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

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

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

同時(shí)，它也接收每個(gè)鄰居結(jié)點(diǎn)發(fā)來的距離表；

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

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

目的站延遲下一站

10,

222

353

414

563

683

DIS1

結(jié)點(diǎn)1測(cè)取相來自相鄰結(jié)點(diǎn)時(shí)延向量結(jié)點(diǎn)1的路由表-更新后

D151

求"12和%：

e

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

"13+42=4+3=7

"14+42=2+2=4

源站點(diǎn)1：利用中間站點(diǎn)2到達(dá)目的站點(diǎn)2。

求"12和%：

,

/f712+rf22=1+0=1

[13+42=4+3=7

〃i4+42=2+2=4

源站點(diǎn)1：利用中間站點(diǎn)3到達(dá)目的站點(diǎn)2。

結(jié)點(diǎn)1測(cè)取相來自相鄰結(jié)點(diǎn)時(shí)延向量結(jié)點(diǎn)1的路由表-更新后

DIS1

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

"13+42=4+3=7

"14+42=2+2=4

源站點(diǎn)1：利用中間站點(diǎn)4到達(dá)目的站點(diǎn)2。

,

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

?二.12=1，$12=2

[13+42=4+3=7

〃i4+42=2+2=4

結(jié)點(diǎn)1測(cè)取相來自相鄰結(jié)點(diǎn)時(shí)延向量結(jié)點(diǎn)1的路由表-更新后

求：源站點(diǎn)1,目的站點(diǎn)3,分別利用2,3,4O

結(jié)點(diǎn)1測(cè)取施1來自相鄰結(jié)點(diǎn)時(shí)延向量結(jié)點(diǎn)1的路由表-更新后

鄰結(jié)點(diǎn)的時(shí)延站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é)點(diǎn)1測(cè)取木I

鄰結(jié)點(diǎn)的時(shí)延

嚴(yán)2=1

及

九二4

回4=2

求“16和%6：

"13+”36

"14+〃46

?.?46=5,

巨離矢

試著扮演一次路由器吧!

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

初始時(shí),

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

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

1:各個(gè)路由器各自重新測(cè)量到鄰居的距離；

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

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

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

第一次交換開始:

路由器B

BO

C1

DC1C

D0-

更新后

C說

:“我到D的距離是1。”

此

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

離BD,

距

過

經(jīng)

是2C95

O

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

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

B1B

B0-CO?

C1CD1Dc1c

D0-

B1B

CO-

D1D

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

B0-B1B

C1CC0-

D2CD1D

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

好事傳千里，壞事不出門！！

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

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

一個(gè)好消息，A鏈路修好了!

■思考：

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

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

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

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

B0-B2C

初始時(shí):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é):

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

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

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

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

一個(gè)壞消息,A路由器壞了!

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

A

■思考：

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

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

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

A0

B1BB:A1

2B

D3BC:A2

ABCD

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

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

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

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

B收到C的更新報(bào)文后，誤認(rèn)為可經(jīng)過C到達(dá)A,于是更

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

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

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

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

是RIP的一個(gè)主要缺點(diǎn)。

1234

DCNDCNDCNDCNDCNDCNDcN

A1AA00-A3CA3CA5CA5CA7c

BC1CC1cC1CC1CC1CC1CC1c

D2CD2cD2cD2cD2cD2cD2c

DCNDCNDCNDCNDCNDCND￡N

AAAADA公D

A2BA2BA2BA6B

I業(yè)J

C十委攵

B1BB1BB1B股隼個(gè)斷更新卜云，TBB

D1DD1DD1D劃兀為。D1D

DCNDCNDCNDcNDcNDcNDcN

A3CA3CA3CA3CA5CA5C

D士C

B2CB2CB2CB2CB2CB2CC

C1cC1cC1cC1cC1cC1cc

*time

如何解決上述問題?

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

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

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

,如何解決上述問題?

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

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

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

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

1

1

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

當(dāng)距離=16時(shí)，認(rèn)為網(wǎng)絡(luò)是不可達(dá)的！！

亨CNDCNDCNDCNDCNDCNDcN

A1AA00-A3CA3CA5CA5CA7c

BC1CC1cC1CC1CC1CC1CC1c

D2CD2cD2cD2cD2cD2cD2c

DCNDCNDCNDCNDCNDCNDN

AAAADA公D

A2BA2BA2BA6B

C十麥攵

B1BB1BB1B缺隼個(gè)斷更新I、太，TBB

D1DD1DD1D劃兀為。DNF

DCNDCNDCNDcNDcNDcN_?J_EJN

A3CA3CA3CA3CA5CA5C

DC

B2CB2CB2CB2CB2CB2CC

C1cC1cC1cC1cC1cC1cc

*time

、

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

由”

y

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

B:A12B

況AB

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

路由消息！訴我的

我要做個(gè)標(biāo)記

C說：“我到A的距離是2,是經(jīng)過B。”

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

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

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

L=U

00D

A|A-t=>B仁A8B

說：壞消息：“我無法到達(dá)A了！！！

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

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

雖然這時(shí)C并不知道A出了故障,

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

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

adnewsisbetterthannonews!

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

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

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

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

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

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

的拓?fù)浣Y(jié)果是的水平分割+毒性逆轉(zhuǎn)的方法更好？

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

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

.(LinkStateRouting)

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

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

■路由收斂速度慢。起牙

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

?OSPF

?IS-IS

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

算法的基本操作

問候

確定可達(dá)性

問候

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

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

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

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

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

鏈路狀態(tài)請(qǐng)求

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

鏈路狀態(tài)確認(rèn)

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

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

HELLO

確定可達(dá)性

HELLO

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

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

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

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

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

ECHO

測(cè)量鄰居開銷

ECHO

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

遲，或者至少有一個(gè)合理的估計(jì)值。

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

ECHO包，來回時(shí)間除以2即為延遲。

北郵計(jì)算機(jī)學(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

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

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

鏈路狀態(tài)分組

擴(kuò)散發(fā)布

鏈路狀態(tài)分組

鏈路狀態(tài)分組

鏈路狀態(tài)分組

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

鏈路狀態(tài)分組

鏈路狀態(tài)分組

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

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

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

時(shí)加1。

■路由器記錄信息對(duì)（源路由器，序號(hào)），當(dāng)一個(gè)鏈路狀

態(tài)分組到達(dá)時(shí)：

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

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

■若序號(hào)比路由器記錄的最大序號(hào)小，則認(rèn)為過時(shí)而丟棄；

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

使用的是可靠的擴(kuò)散法

JACK報(bào)文

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

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

■解決辦法：

■使用32位序號(hào)；

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

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

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

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

?如果:

■路由器崩潰后，序號(hào)重置；

■或者序號(hào)出錯(cuò)；

■解決方法

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

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

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

包，保留新包；

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

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

B2C

43

A\AZ

E8F

SendflagsACKflags

SourceSeq.AgeAcFAcFData

A2160011100

F2160110001

E2159010101

C2060101010

D2159100011

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

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

一個(gè)經(jīng)過EFB;

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

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

5.計(jì)算到每個(gè)其它路由器的最短路徑

■每個(gè)路由器都獲得了自己的路由拓?fù)鋱D

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

■生成自己的路由表

THEEND

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

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

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

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

■LS

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

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

的報(bào)文

■DV

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

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

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

算法(DV)的比較

■收斂(Convergence)速度

-LS

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

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

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

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

■DV

■收斂時(shí)間不定

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

■count-to-infinityfi5]|§

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

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

算法(DV)的比較

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

.LS

結(jié)點(diǎn)會(huì)廣播錯(cuò)誤的鏈路開銷

每個(gè)結(jié)點(diǎn)只計(jì)算自己的路由表

?DV

結(jié)點(diǎn)會(huì)廣播錯(cuò)誤的路徑開銷

每個(gè)結(jié)點(diǎn)的路由表被別的結(jié)點(diǎn)使用，錯(cuò)誤會(huì)傳播到全網(wǎng)

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

作業(yè)2:

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

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

林小:V0~++標(biāo)示：VI"林小：V2P林小：V3「初'小：V4d

序號(hào):“序號(hào)：52序號(hào):加序號(hào)：9卡序號(hào):4

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

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

3〃V*3〃⑵⑵3P

2〃恬3〃恬