北郵計(jì)算機(jī)學(xué)院：THE

NETWORK

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

I基本理論框架第

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.1

NETWORK

LAYER

DESIGN

ISSUE網(wǎng)絡(luò)層的基本概念網(wǎng)絡(luò)層的目標(biāo)：將分組從源端沿著網(wǎng)絡(luò)路徑送到目標(biāo)端。北郵計(jì)算機(jī)學(xué)院：End

toEnd

VS

Point

to

Point為什么要?jiǎng)?chuàng)建網(wǎng)絡(luò)層？北郵計(jì)算機(jī)學(xué)院：網(wǎng)絡(luò)層指明端到端的總體路徑方向，數(shù)據(jù)鏈路層腳踏實(shí)地地一條一條鏈路的實(shí)現(xiàn)。北郵計(jì)算機(jī)學(xué)院：Store-and-Forward

Packet

Switching5.1.1轉(zhuǎn)發(fā)，分組交換硬件結(jié)構(gòu)轉(zhuǎn)發(fā)的方式Services

Provided

to

Transport

Layer5.1.2

網(wǎng)絡(luò)層提供的服務(wù)北郵計(jì)算機(jī)學(xué)院：Connectionless

Service5.1.3

無連接的服務(wù)TransportNetworkDatalink北郵計(jì)算機(jī)學(xué)院：無連接：數(shù)據(jù)報(bào)服務(wù)的特點(diǎn)H1H2

H4ADBH6EH1

向H5

發(fā)送分組H5CH3分組交換網(wǎng)H2

向H6

發(fā)送分組路徑可能變化網(wǎng)絡(luò)隨時(shí)接受主機(jī)發(fā)送的分組（即數(shù)據(jù)報(bào)）網(wǎng)絡(luò)為每個(gè)分組獨(dú)立地選擇路由。提供數(shù)據(jù)報(bào)服務(wù)的特點(diǎn)H1H2

H4ADBH6E網(wǎng)絡(luò)盡最大努力地將分組交付給目的主機(jī)，但網(wǎng)絡(luò)對源主機(jī)沒有任何承諾。H5CH3分組交換網(wǎng)提供數(shù)據(jù)報(bào)服務(wù)的特點(diǎn)H1H2

H4ADBH6E網(wǎng)絡(luò)不保證所傳送的分組不丟失也不保證按源主機(jī)發(fā)送分組的先后順序以及在時(shí)限內(nèi)必須將分組交付給目的主機(jī)H5CH3分組交換網(wǎng)提供數(shù)據(jù)報(bào)服務(wù)的特點(diǎn)H1H2

H4ADBH6E當(dāng)網(wǎng)絡(luò)發(fā)生擁塞時(shí)網(wǎng)絡(luò)中的結(jié)點(diǎn)可根據(jù)情況將一些分組丟棄H5CH3分組交換網(wǎng)提供數(shù)據(jù)報(bào)服務(wù)的特點(diǎn)H1H2

H4ADBH6E數(shù)據(jù)報(bào)提供的服務(wù)是不可靠的，它不能保證服務(wù)質(zhì)量。實(shí)際上“盡最大努力交付”的服務(wù)就是沒有質(zhì)量保證的服務(wù)。H5CH3分組交換網(wǎng)Connection-Oriented

Service5.1.4

面向連接：虛電路服務(wù)的特點(diǎn)H1H2H4ADBH6EH1

要和H5

通信主機(jī)H1

先向主機(jī)H5

發(fā)出一個(gè)特定格式的控制信息分組，要求進(jìn)行通信，同時(shí)尋找一條合適路由。若主機(jī)H5

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

向H5

發(fā)送的所有分組都沿此虛電路傳送。H5CH3分組交換網(wǎng)提供虛電路服務(wù)的特點(diǎn)H1H2H4ADBH6E同理，主機(jī)H2

和主機(jī)H6

通信之前，也要建立虛電路。H5CH3分組交換網(wǎng)提供虛電路服務(wù)的特點(diǎn)H1H2H4ADBH6E在虛電路建立后，網(wǎng)絡(luò)向用戶提供的服務(wù)就好像在兩個(gè)主機(jī)之間建立了一對穿過網(wǎng)絡(luò)的數(shù)字管道。所有發(fā)送的分組都按順序進(jìn)入管道，然后按照先進(jìn)先出的原則沿著此管道傳送到目的站主機(jī)。H5CH3分組交換網(wǎng)提供虛電路服務(wù)的特點(diǎn)H1H2H4ADBH6E到達(dá)目的站的分組順序就與發(fā)送時(shí)的順序一致，因此網(wǎng)絡(luò)提供虛電路服務(wù)對通信的服務(wù)質(zhì)量QoS

(Quality

of

Service)有較好的保證。H5CH3分組交換網(wǎng)數(shù)據(jù)報(bào)服務(wù)和虛電路服務(wù)優(yōu)缺點(diǎn)的歸納對比的方面虛電路服務(wù)

數(shù)據(jù)報(bào)服思路可靠通信應(yīng)當(dāng)由網(wǎng)絡(luò)來保證可靠通信應(yīng)由用戶主機(jī)來保證連接的建立必須有不目的站地址每個(gè)分組都有目的站的全地址僅在連接建立階段使用，每個(gè)分組使用短的虛電路號(hào)北郵計(jì)算機(jī)學(xué)院：數(shù)據(jù)報(bào)服務(wù)和虛電路服務(wù)優(yōu)缺點(diǎn)的歸納對比的方面虛電路服務(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)出故障時(shí)所有通過出故障的結(jié)點(diǎn)的虛電路均不能工作故障結(jié)點(diǎn)可能丟分組，一可能會(huì)發(fā)生變北郵計(jì)算機(jī)學(xué)院：數(shù)據(jù)報(bào)服務(wù)和虛電路服務(wù)優(yōu)缺點(diǎn)的歸納對比的方面虛電路服務(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)的歸納對比的方面虛電路服務(wù)

數(shù)據(jù)報(bào)服務(wù)分組的順序總是按發(fā)送順序到達(dá)目的站時(shí)不一定到達(dá)目的站按發(fā)送順序端到端的負(fù)責(zé)差錯(cuò)處理和可以由分組交換網(wǎng)由用戶主機(jī)負(fù)責(zé)也可以由用戶北郵計(jì)算機(jī)學(xué)院：ROUTING

ALGORITHMS5.2

路由算法

路由算法的概念

最優(yōu)化的原則

距離矢量路由

鏈路狀態(tài)路由

分級路由北郵計(jì)算機(jī)學(xué)院：基本概念－路由器的兩個(gè)動(dòng)作

轉(zhuǎn)發(fā)(forwarding)每個(gè)分組到達(dá)的時(shí)候，在路由表中查找該分組所對應(yīng)的輸出路徑。

路由選擇(routing)使用路由算法。負(fù)責(zé)填充和更新路由表。北郵計(jì)算機(jī)學(xué)院：Routing

Algorithm路由算法北郵計(jì)算機(jī)學(xué)院：理想的路由算法北郵計(jì)算機(jī)學(xué)院：Non-adaptive

an路由算法的分類ptive如何恰當(dāng)使用？北郵計(jì)算機(jī)學(xué)院：The

Optimality

Principle5.2.1

最優(yōu)化原則如果I，J，K的最佳路由是r1+r2，則當(dāng)I把分組交給J時(shí)，J一定會(huì)沿著r2把分組轉(zhuǎn)發(fā)出去。想想看：最優(yōu)化原則，對于計(jì)算機(jī)網(wǎng)絡(luò)中的分組轉(zhuǎn)發(fā)有什么作用？北郵計(jì)算機(jī)學(xué)院：計(jì)算機(jī)學(xué)院：匯集樹(Sink

Tree)Shortest

PathRouting5.2.2

最短路徑路由算法北郵計(jì)算機(jī)學(xué)院：計(jì)算機(jī)學(xué)院：智能科學(xué)與網(wǎng)絡(luò)工程系：智能科學(xué)與網(wǎng)絡(luò)工程系：智能科學(xué)與網(wǎng)絡(luò)工程系：智能科學(xué)與網(wǎng)絡(luò)工程系：透明網(wǎng)橋的“武功秘笈”北郵計(jì)算機(jī)學(xué)院：擴(kuò)散算法（Flooding）屬于靜態(tài)路由算法基本思想事先不需要任何網(wǎng)絡(luò)信息；

路由器把收到的每一個(gè)分組，向除了該分組到來的線路外的所有輸出線路發(fā)送。將來會(huì)有多個(gè)分組的副本到達(dá)目的地端，最先到達(dá)的，可能是走了“最優(yōu)”的路徑。北郵計(jì)算機(jī)學(xué)院：146235擴(kuò)散算法：結(jié)點(diǎn)1與6之間的通信，Step1124356擴(kuò)散算法：Step

2124356擴(kuò)散算法：Step

3好大的水啊！

（Flooding）算法的優(yōu)點(diǎn)是什么？不需要事前知道任何網(wǎng)絡(luò)的拓?fù)湫畔ⅲ凰械木W(wǎng)絡(luò)路徑都被嘗試過；第一個(gè)到達(dá)的分組走的路徑可能是最優(yōu)的。算法的主要問題是什么？產(chǎn)生大量重復(fù)分組。想想看？如何消除：過時(shí)的/重復(fù)的分組？你該出手了！北郵計(jì)算機(jī)學(xué)院：源端收到分組時(shí)，在每個(gè)分組的頭部增加一個(gè)計(jì)數(shù)器。此后，每經(jīng)過一跳該計(jì)數(shù)器減1，為0時(shí)丟棄。計(jì)數(shù)器的初值＝最佳路徑的跳數(shù)/子網(wǎng)的直徑；每個(gè)路由器記錄收到已經(jīng)擴(kuò)散過的分組，從而避免再次發(fā)送這些分組。源端在每個(gè)分組中放置一個(gè)序號(hào)；記錄{源端地址，序號(hào)}；每個(gè)路由器將得到的同一源端的分組的最大序列號(hào)分組記錄下來，小于該序號(hào)的丟棄。決北郵計(jì)算機(jī)學(xué)院：方選擇性擴(kuò)散算法（1）623154236154選擇性擴(kuò)散算法（2）1236選擇性擴(kuò)散算法（3）54選擇性擴(kuò)散算法（Selective

Flooding）選擇性擴(kuò)散算法是擴(kuò)散法的一種改進(jìn)。能夠消除多余的分組。擴(kuò)散算法的應(yīng)用情況對路由器和線路的資源過于浪費(fèi)，實(shí)際的網(wǎng)絡(luò)很少直接采用；具有極好的健壯性，可用于軍事應(yīng)用；作為衡量標(biāo)準(zhǔn)評價(jià)和初級拓?fù)湎@得方式應(yīng)用于其它路由算法。北郵計(jì)算機(jī)學(xué)院：動(dòng)態(tài)路由算法距離矢量路由算法鏈路狀態(tài)路由算法北郵計(jì)算機(jī)學(xué)院：Distance

Vector

Routing5.2.4

距離矢量路由算法北郵計(jì)算機(jī)學(xué)院：源站點(diǎn)1：利用中間站點(diǎn)2到達(dá)目的站點(diǎn)2。源站點(diǎn)1：利用中間站點(diǎn)3到達(dá)目的站點(diǎn)2。智能科學(xué)與網(wǎng)絡(luò)工程系：源站點(diǎn)1：利用中間站點(diǎn)4到達(dá)目的站點(diǎn)2。智能科學(xué)與網(wǎng)絡(luò)工程系：計(jì)算機(jī)學(xué)院：智能科學(xué)與網(wǎng)絡(luò)工程系：求：源站點(diǎn)1，目的站點(diǎn)3，分別利用2，3，4。智能科學(xué)與網(wǎng)絡(luò)工程系：使用距離矢量算法試著扮演一次路由器吧！離跳北郵計(jì)算機(jī)學(xué)院：B

1

BC

0

-D

1

DB

0

-C

1

C初始時(shí)，路由器中的路由表只有到相鄰路由器的信息“C”表示“從本路由器B到C路由器”“1”表示“距離是1”“-”表示“直接交付”C.

1

CD.

0

-BCA

DABCDB

1

BC

0

-D

1

D1：各個(gè)路由器各自重新測量到鄰居的距離；2：然后把自己上一狀態(tài)的路由表去掉轉(zhuǎn)發(fā)項(xiàng)，項(xiàng)變成距離表發(fā)送出去。B

0

-C

1

CC.

1

CD.

0

-B

0C

1B

1C

0D

1C

1D

0第一次交換開始：BCA

D路由器B

收到相鄰路由器C

的距離表B

1C

0D

1B.0

-C.

1

CD.

2

C更新后C

說：“我到D

的距離是1。”因此

B現(xiàn)在也可以到D，距離是2，經(jīng)過C。”B

0

-C

1

CB

1

BC

0

-D

1

DB

0C

1C.

1

CD.

0

-BCA

DB

0C

1C

1D

0路由器C

收到相鄰路由器

B和D的距離表B

1C

0D

1B.

0

-C.

1

CD.2

CB

0

-C

1

CB

1

BC

0

-D

1

DC.

1

CD.

0

-更新后B

1

BC

0

-D

1

DABCDB

1C

0D

1路由器

D收到相鄰路由器C

的距離表B.

0

-C.

1

CD.2

CB

0

-C

1

CB

1

BC

0

-D

1

DC.

1

CD.

0

-C

1D

0更新后B

1

BC

0

-D

1

DB

2

C1

C0

-ABCDB

0

-C 1

CD 2

CB

1

BC

0

-D

1

DB

2

CC 1

CD 0

-最終所有的路由器的路由表都更新了對鏈路故障的反應(yīng)好事傳千里，壞事不出門！!一個(gè)靠鄰居“

”活著的路由協(xié)議北郵計(jì)算機(jī)學(xué)院：一個(gè)好消息，A鏈路修好了！ABCDB

0

-C 1

CD 2

CB

1

BC

0

-D

1

DB

2

CC 1

CD 0

-初始時(shí)：BCDB

0

-C 1

CD 2

CB

1

BC

0

-D

1

DB

2

CC 1

CD 0

-A思考：A需要多久才能獲得全網(wǎng)的路由信息？B需要多久才能知道可達(dá)A的路由信息？C需要多久才能知道可達(dá)A的路由信息？D需要多久才能知道可達(dá)A的路由信息？初始時(shí)：BCDB

0

-C 1

CD 2

CB

1

BC

0

-D

1

DB

2

CC 1

CD 0

-AA0-B1BC2BD3BA0-B1BC2BD3BA0-B1BC2BD3BA1AB0-C1CD2CA1AB0-C1CD2CA1AB0-C1CD2CB1BC0-D1DB2CC1CD0-B2CC1CD0-A2BB1BC0-D1DA2BB1BC0-D1DA3CB2CC1CD0-總結(jié)：對鏈路“好消息”的反應(yīng)很快！網(wǎng)絡(luò)再次收斂的速度很快！正所謂：好事快馬加鞭傳千里！北郵計(jì)算機(jī)學(xué)院：一個(gè)壞消息，A路由器壞了！ABCD北郵計(jì)算機(jī)學(xué)院：A0-B1BC2BD3BA1AB0-C1CD2CA2BB1BC0-D1DA3CB2CC1CD0-BCDA思考：B需要多久才能知道不可達(dá)A的路由信息？C需要多久才能知道不可達(dá)A的路由信息？D需要多久才能知道不可達(dá)A的路由信息？B:A

1C:A

2A0-B1BC2BD3BA1AB0-C1CD2CA2BB1BC0-D1DA3CB2CC1CD0-C卻通過“距離表”說：別著急，我能到達(dá)A，嘿嘿！A

B

C

D第一次交換時(shí)：B、C、D仍把自己的路由表改成距離表，發(fā)送。第一次交換后：C和D的路由表不變。一開始，B得知了壞消息：“我無法到A

！！！B

收到C

的更文后，誤認(rèn)為可經(jīng)過C

到達(dá)A，于是更新自己的路由表，說：“我到A

的距離是

3，下一跳經(jīng)過C”。然后再等待下次的交換時(shí)，將此更新給C。C:A

2D:A

3計(jì)數(shù)到無問題1

AB

C

1DCNA1AC1CD2CBtimeDCNA2BB1BD1DDCNA3CB2CC1CCDDCNA∞-C1CD2CDCNA2BB1BD1DDCNA3CB2CC1CDCNA3CC1CD2CD

C

NA

2

BB

1

BD

1

DDCNA3CB2CC1CDCNA3CC1CD2CDCNDCNA3CB2CC1CDCNA5CC1CD2CDCNDCNA5CB2CC1CDCNA5CC1CD2CDCNA

4

B

A

4

B

A

6

BB

1

B

B

1

B

B

1

BD

1

D

D

1

D

D

1

DDCNA5CB2CC1CDCNA7CC1CD2CDCNA6BB1BD1DDCNA7CB2CC1C這樣不斷更新下去，計(jì)數(shù)到無窮。這就是好消息得快，而壞消息得慢。網(wǎng)絡(luò)出故障的時(shí)間往往需要較長的時(shí)間(例如數(shù)分鐘)。這是RIP

的一個(gè)主要缺點(diǎn)。1234如何解決上述問題？先想想：導(dǎo)致上述問題的本質(zhì)原因是什么？北郵計(jì)算機(jī)學(xué)院：如何解決上述問題？跳數(shù)水平分割帶毒1值：頭疼治頭，腳痛治腳；2轉(zhuǎn)：的治水標(biāo)平又分要割治本！北郵計(jì)算機(jī)學(xué)院：計(jì)數(shù)到無窮的問題BC1AD1規(guī)定一個(gè)最大距離（跳數(shù)）：16，當(dāng)距離＝

16時(shí)，認(rèn)為網(wǎng)絡(luò)是不可達(dá)的！！！DCNA1AC1CD2CBtimeDCNA2BB1BD1DDCNA3CB2CC1CCDDCNA∞-C1CD2CDCNA2BB1BD1DDCNA3CB2CC1CDCNA3CC1CD2CD

C

NA

2

BB

1

BD

1

DDCNA3CB2CC1CDCNA3CC1CD2CDCNDCNA3CB2CC1CDCNA5CC1CD2CDCNDCNA5CB2CC1CDCNA5CC1CD2CDCNA

4

B

A

4

B

A

6

BB

1

B

B

1

B

B

1

BD

1

D

D

1

D

D

1

DDCNA5CB2CC1CDCNA7CC1CD2CDCNA6BB1BD1DDCNA7CB2CC1C這樣不斷更新下去，計(jì)數(shù)到無窮。正常情況B:

A

1B

說：“我到A

的距離是1”“我有一條到A的路由”記住，我是！BCDA正常情況B:

A

1A

2

B我得到了到A的路由消息！我要做個(gè)標(biāo)記C

說：“我到A

的距離是2，是經(jīng)過B。”將來我不能向B告知網(wǎng)1的任何消息。這是“水平分割”技術(shù)。BCD這是由B告訴AA

∞

-A

∞

BB

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

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

在收到

B

的更

文之前，還發(fā)送原來的報(bào)文，雖然這時(shí)

C

并不知道A

出了故障，但報(bào)文是加了毒性逆轉(zhuǎn)的形式。這是：水平分割＋毒性逆轉(zhuǎn)！BCDA水平分割VS水平分割＋毒性逆轉(zhuǎn)Bad

news

is

better

than

no

news!北郵計(jì)算機(jī)學(xué)院：作業(yè)：分析網(wǎng)絡(luò)協(xié)議的有效性普通的距離矢量協(xié)議；使用帶水平分割的距離矢量協(xié)議；使用水平分割＋毒性逆轉(zhuǎn)方法。BCABCD

DA北郵計(jì)算機(jī)學(xué)院：5.2.5

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

State

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

OSPF

IS-IS北郵計(jì)算機(jī)學(xué)院：算法的基本操作問候問候數(shù)據(jù)庫描述數(shù)據(jù)庫描述數(shù)據(jù)庫描述數(shù)據(jù)庫描述鏈路狀態(tài)請求鏈路狀態(tài)更新鏈路狀態(tài)確認(rèn)確定可達(dá)性達(dá)到數(shù)據(jù)庫的同步新情況下的同步北郵計(jì)算機(jī)學(xué)院：1.發(fā)現(xiàn)鄰居結(jié)點(diǎn)，并學(xué)習(xí)它們的網(wǎng)絡(luò)地址OO確定可達(dá)性北郵計(jì)算機(jī)學(xué)院：2.測量到各鄰居節(jié)點(diǎn)的延遲或者開銷ECHOECHO測量鄰居開銷北郵計(jì)算機(jī)學(xué)院：3.創(chuàng)建鏈路狀態(tài)分組創(chuàng)建鏈路狀態(tài)分組北郵計(jì)算機(jī)學(xué)院：4.

使用擴(kuò)散法發(fā)布鏈路狀態(tài)分組鏈路狀態(tài)分組鏈路狀態(tài)分組鏈路狀態(tài)分組鏈路狀態(tài)分組鏈路狀態(tài)分組鏈路狀態(tài)分組擴(kuò)散發(fā)布達(dá)到數(shù)據(jù)庫的同步北郵計(jì)算機(jī)學(xué)院：4.

使用擴(kuò)散法發(fā)布鏈路狀態(tài)分組北郵計(jì)算機(jī)學(xué)院：使用的是可靠的擴(kuò)散法t更文ACK報(bào)文RRt3RRt1t2t4開動(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é)院：開動(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é)院：從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ì)算最短路徑;生成自己的路由表北郵計(jì)算機(jī)學(xué)院：鏈路狀態(tài)算S）和距離矢量算法（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)算

S）和距離向量算法（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-infinity問題北郵計(jì)算機(jī)學(xué)院：鏈路狀態(tài)算

S）和距離向量算法（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：北郵計(jì)算機(jī)學(xué)院：Hierarchical

Routing5.2.6

分級路由為路由器減負(fù)北郵計(jì)算機(jī)學(xué)院：不使用分級路由使用分級路由分級路由假設(shè)某個(gè)子網(wǎng)中有720臺(tái)路由器.如果不使用分級路由方法：每個(gè)路由器中的表項(xiàng)為720項(xiàng)；如果采用兩個(gè)分級，分成24個(gè)區(qū)域，每個(gè)區(qū)域30個(gè)路由器：30

本地表項(xiàng)

23

表項(xiàng)如果采用三個(gè)分級，分成8個(gè)群，每個(gè)群包含9個(gè)區(qū)域，每個(gè)區(qū)域包含10個(gè)路由器，則：10

本地表項(xiàng)8

個(gè)本地群中的區(qū)域項(xiàng)7群作業(yè)3：2,3,6,7,9,10,14,22北郵計(jì)算機(jī)學(xué)院：關(guān)于路由表的預(yù)備知識(shí)路由表的結(jié)構(gòu)（

）北郵計(jì)算機(jī)學(xué)院：用圖表示廣域網(wǎng)的例子12341結(jié)點(diǎn)邊243北郵計(jì)算機(jī)學(xué)院：每一個(gè)結(jié)點(diǎn)的轉(zhuǎn)1243目的站下一跳

1

直接233343對結(jié)點(diǎn)

1

的轉(zhuǎn)

的第一個(gè)項(xiàng)目的解釋：若到達(dá)結(jié)點(diǎn)

1

的分組的目的地址是結(jié)

則下一跳就是直接交付而不必再轉(zhuǎn)發(fā)的主機(jī)，結(jié)點(diǎn)。結(jié)點(diǎn)1

的轉(zhuǎn)北郵計(jì)算機(jī)學(xué)院：1243目的站下一跳

13

2直接3344對結(jié)點(diǎn)

2

的轉(zhuǎn)

的第一個(gè)項(xiàng)目的解釋：若到達(dá)結(jié)點(diǎn)

2

的每分組一的個(gè)目的結(jié)c

地點(diǎn)址的是結(jié)轉(zhuǎn)點(diǎn)主機(jī)，則下一跳就應(yīng)轉(zhuǎn)發(fā)到結(jié)點(diǎn)3結(jié)點(diǎn)2

的轉(zhuǎn)北郵計(jì)算機(jī)學(xué)院：在路由表中使用默認(rèn)路由12431直接233343結(jié)點(diǎn)1

的轉(zhuǎn)目的站 下一跳這三個(gè)項(xiàng)目的“下一跳”都是轉(zhuǎn)發(fā)到“3”（結(jié)點(diǎn)3）。可以合并以結(jié)點(diǎn)

1

和結(jié)點(diǎn)

2

中的轉(zhuǎn) 為例來北郵計(jì)算機(jī)學(xué)院：在路由表中使用默認(rèn)路由12431默認(rèn)直接3結(jié)點(diǎn)1

的轉(zhuǎn)目的站 下一跳默認(rèn)路由北郵計(jì)算機(jī)學(xué)院：在路由表中使用默認(rèn)路由124312343直接34結(jié)點(diǎn)2

的轉(zhuǎn)目的站 下一跳這兩個(gè)項(xiàng)目的“下一跳”都是轉(zhuǎn)發(fā)到“3”（結(jié)點(diǎn)3）。可以合并北郵計(jì)算機(jī)學(xué)院：在路由表中使用默認(rèn)路由使用默認(rèn)路由使轉(zhuǎn)更加簡潔，可減少查找轉(zhuǎn)的時(shí)間。124324默認(rèn)直接43結(jié)點(diǎn)2

的轉(zhuǎn)目的站 下一跳默認(rèn)路由北郵計(jì)算機(jī)學(xué)院：CONGESTION

CONTROL

ALGORITHMS5.3網(wǎng)絡(luò)擁塞控制網(wǎng)絡(luò)開始擁堵了！北郵計(jì)算機(jī)學(xué)院：網(wǎng)絡(luò)擁塞：網(wǎng)絡(luò)性能曲線吞吐量擁塞無擁塞控制死鎖（吞吐量=0）提供的負(fù)載輕度擁塞0北郵計(jì)算機(jī)學(xué)院：擁塞（Congestion）擁塞網(wǎng)絡(luò)資源上有太多的分組時(shí)，將會(huì)導(dǎo)致網(wǎng)絡(luò)性能下降。對資源需求的總和>可用資源資源：鏈路容量、交換節(jié)點(diǎn)中的緩存和處理機(jī)速度等。擁塞產(chǎn)生的原因低帶寬線路多個(gè)輸入對應(yīng)一個(gè)輸出節(jié)點(diǎn)緩沖容量太小結(jié)點(diǎn)處理機(jī)速度不高北郵計(jì)算機(jī)學(xué)院：擁塞的策略：決不只針對某個(gè)因素改善擁塞！！！若結(jié)點(diǎn)緩存容量太小，到達(dá)結(jié)點(diǎn)的分組無空間暫存；若增大結(jié)點(diǎn)緩存容量，而鏈路容量和處理機(jī)速度未提高，分組排隊(duì)會(huì)很長，導(dǎo)致時(shí)延增大，可能因超時(shí)發(fā)送端進(jìn)行重發(fā)，發(fā)出的分組，擁塞更加；提高結(jié)點(diǎn)處理機(jī)速度，增大鏈路容量，故然可以改善這段的擁塞，但可能只是將瓶頸轉(zhuǎn)移到其他地方。因此，針對某個(gè)因素的解決方案，只能對提高網(wǎng)絡(luò)性能起到一定的好處，甚至僅僅是轉(zhuǎn)移了影響性能的瓶頸。北郵計(jì)算機(jī)學(xué)院：擁塞控制與流量控制的差別

擁塞控制（congestion

control）需要確保通信子網(wǎng)能夠承載用戶提交的通信量，是一個(gè)全局性過程，涉及主機(jī)、路由器等很多

因素；

流量控制（flow

control)與點(diǎn)到點(diǎn)的通信量有關(guān)，主要解決快速發(fā)送方與慢速接收方的問題，是局部過程，一般都是基于反饋進(jìn)行控制的。北郵計(jì)算機(jī)學(xué)院：擁塞和流量控制的區(qū)別擁塞控制所起的作用吞吐量擁塞理想的擁塞控制實(shí)際的擁塞控制無擁塞控制死鎖（吞吐量=0）提供的負(fù)載輕度擁塞0北郵計(jì)算機(jī)學(xué)院：5.3.1

擁塞控制的通用原則有兩種思路防患未然型亡羊補(bǔ)牢型北郵計(jì)算機(jī)學(xué)院：兩種思路Open

loop（開環(huán)方法）試圖采用良好的設(shè)計(jì)來解決問題，本質(zhì)是從一開始就保證不會(huì)發(fā)生擁塞問題。一旦網(wǎng)絡(luò)系統(tǒng)啟動(dòng)運(yùn)行起來，就不需要中途做修正。Closed

loop（閉環(huán)方法）基于返回環(huán)路的概念基礎(chǔ)之上：Explicit

feedback

（顯式反饋）Implicit

feedback（隱式反饋）北郵計(jì)算機(jī)學(xué)院：5.3.2

開環(huán)方法：擁塞預(yù)防策略閉環(huán)控制策略三個(gè)步驟：監(jiān)視系統(tǒng)，檢測到何時(shí)何地發(fā)生了擁塞將該信息傳遞到能夠采取行動(dòng)的地方調(diào)整系統(tǒng)的運(yùn)行，以改正問題。北郵計(jì)算機(jī)學(xué)院：1.監(jiān)視系統(tǒng)，檢測是否發(fā)生擁塞擁塞控制使用的度量標(biāo)準(zhǔn)丟棄的分組所占的百分比（缺少緩沖區(qū)空間）平均隊(duì)列長度超時(shí)和重傳分組的數(shù)量平均分組延遲和分組延遲的標(biāo)準(zhǔn)方差北郵計(jì)算機(jī)學(xué)院：2.將擁塞信息傳輸?shù)侥軌虿扇⌒袆?dòng)的地方擁塞信息的傳輸方法（隱式和顯示反饋）給流量源發(fā)送一個(gè)分組，告知擁塞的發(fā)生；在分組中增加一個(gè)位或一個(gè)域，檢測到擁塞時(shí)，路由器填充該位，在它所有的輸出分組中填充

該域，以告警它的鄰居主機(jī)或路由器周期性地向外發(fā)送探詢分組，顯示地詢問有關(guān)擁塞狀況，然后在有問題的區(qū)域中，可以利用這些信息來路由流量。北郵計(jì)算機(jī)學(xué)院：3.

調(diào)整系統(tǒng)的運(yùn)行目的：擁塞消息將最終導(dǎo)致主機(jī)采取適當(dāng)?shù)男袆?dòng)來減輕擁塞。謹(jǐn)慎的調(diào)整時(shí)間尺度：系統(tǒng)不會(huì)產(chǎn)生劇烈震蕩擁塞機(jī)制要及時(shí)有效。北郵計(jì)算機(jī)學(xué)院：5.3.3

虛電路子網(wǎng)中的擁塞控制，??

控制（admission

control）??

基本思想：一旦發(fā)生擁塞，在問題解決之前不允許建立新的虛電路；??

另

法是發(fā)生擁塞后可以建立新的虛電路，但要繞開發(fā)生擁塞的地區(qū)；北郵計(jì)算機(jī)學(xué)院：資源預(yù)留策略（虛電路子網(wǎng)）資源預(yù)留：建立虛電路時(shí)，主機(jī)與子網(wǎng)達(dá)成協(xié)議，子網(wǎng)根據(jù)協(xié)議在虛電

為此連接預(yù)留資源。

問題是：是任何時(shí)刻都使用資源預(yù)留嗎？還是只在發(fā)生擁塞時(shí)？北郵計(jì)算機(jī)學(xué)院：5.3.4

數(shù)據(jù)報(bào)子網(wǎng)中的擁塞控制

(1

)

funew

uold

(0,1)，

e.g.

87.5%U:平均利用率f:

瞬時(shí)利用率北郵計(jì)算機(jī)學(xué)院：警告位（The

Warning

Bit）路由器當(dāng)輸出線路達(dá)到告警狀態(tài)時(shí)，路由器將發(fā)送出去的分組頭部設(shè)置告警位。目的地當(dāng)分組到達(dá)目的地時(shí)，告警位被到ACK分組中，發(fā)給源端。源端隨著帶有警告位的確認(rèn)分組不斷回來時(shí)，源端不斷的降低它的傳輸速率

當(dāng)帶有警告位的確認(rèn)分組減少到規(guī)定值時(shí)，源端增加它的傳輸速率

由于沿途的路由器都可能設(shè)置警告位，所以只有當(dāng)所有的路由器都排除了問題之后，流量才能增加上去。抑制分組（

Choke

Packets

）路由器路由器給源端返回一個(gè)抑制分組，并 原分組的目標(biāo)地址；原來的分組被打上一個(gè)標(biāo)記，防止沿途其他路由器又重復(fù)產(chǎn)生抑制分組源端主機(jī)收到抑制分組后，將發(fā)送到指定目標(biāo)的流量減少X百分比隨后到達(dá)的具有相同目的地抑制分組被忽略一段間隔后，繼續(xù)如果又有抑制分組，則進(jìn)一步降低發(fā)送流量；如果沒有抑制分組，則增加流量主機(jī)可以調(diào)節(jié)流量，例如利用一個(gè)窗口第一次可以導(dǎo)致流量減少到原來的50%,第二此可以減少到25%......

快速減少，緩慢增加逐級跳（hop-by-hop）抑制分組產(chǎn)生原因在高速、長距離的網(wǎng)絡(luò)中，由于源主機(jī)響應(yīng)太慢，抑制包算法對擁塞控制的效果并不好，可采用逐跳抑制包算法。基本思想抑制包對它經(jīng)過的每個(gè)路由器都起作用；能夠迅速緩解發(fā)生擁塞處的擁塞；上游路由器要求有 的緩沖區(qū)；AB

CDFE北郵計(jì)算機(jī)學(xué)院：锏級的方法黔驢技窮之時(shí)….北郵計(jì)算機(jī)學(xué)院：5.3.5

負(fù)載丟棄（load

shedding）原則上述算法都不能消除擁塞時(shí)，路由器只得將包丟棄；針對不同服務(wù)，可采取不同丟棄策略

隨機(jī)丟棄

Wine

&Milk

E.g.

file

transfer,

multimedia

Requires

cooperation

from

the

senders

分組帶有優(yōu)先級,

…r

to

send

than

the

high-priority

E.g.

algorithms

for

compressing

The

low-priority

packets

being

cheones,

…

RED

(Random

Early

Detection)

Drop

packets

before

the

situation

hase

hopeless

How

should

the

router l

the

source

about

theproblem?

Send

a

choke

packet

Just

discard

the

selected

packet

Sources

respond

to

lost

packets

by

slowing

down

their

transmission

rate時(shí)，為何總要從網(wǎng)絡(luò)上看緩存，緩存？想知道其中的奧秘嗎？北郵計(jì)算機(jī)學(xué)院：5.3.6

抖動(dòng)（jitter）控制抖動(dòng)：分組到達(dá)時(shí)間的變化量被稱為抖動(dòng)。路由器對抖動(dòng)的控制方法來得晚的，加快其轉(zhuǎn)發(fā)速度；

提早到達(dá)的，讓分組在緩沖區(qū)中多逗留一會(huì)。目的地接收端對抖動(dòng)的控制方法緩存，盡可能多的收集分組。北郵計(jì)算機(jī)學(xué)院：5.4

服務(wù)質(zhì)量(QoS)流(Flow)：從源端到目的地端的分組流。北郵計(jì)算機(jī)學(xué)院：服務(wù)質(zhì)量的四個(gè)衡量參數(shù)

可靠性(reliability）

延遲(delay)

抖動(dòng)(jitter)

帶寬(bandwidth)北郵計(jì)算機(jī)學(xué)院：服務(wù)質(zhì)量需求的嚴(yán)格程度5-30北郵計(jì)算機(jī)學(xué)院：ATM

網(wǎng)絡(luò):流的分類依據(jù)對QoS的需求，可將流分為：

Constant

bit

rateephony

Real-time

variable

bit

rate

compressed

conferencing

Non-real-time

variable

bit

rate

watching

a

movieover

the

Internet

Available

bit

rate

filetransfer北郵計(jì)算機(jī)學(xué)院：5.4.2獲得好的服務(wù)質(zhì)量的技術(shù)緩沖，流量整形等北郵計(jì)算機(jī)學(xué)院：1.Buffering（緩沖，在接收方）Smoothing

the

output

stream

bybuffering

packets.北郵計(jì)算機(jī)學(xué)院：2.Traffic

Sha（流量整形）流量整形用于調(diào)節(jié)數(shù)據(jù)的平均速率和突發(fā)性；與流量控制（滑動(dòng)窗口協(xié)議）是有重要區(qū)別的！！！漏桶算法（The

Leaky

Bucket

Algorithm）基本思想將用戶發(fā)出的不平滑的數(shù)據(jù)分組流轉(zhuǎn)變成網(wǎng)絡(luò)中平滑的數(shù)據(jù)分組流；可用于固定分組長的協(xié)議，如ATM；也可用于可變分組長的協(xié)議，如IP，使用字節(jié)計(jì)數(shù)；

無論負(fù)載突發(fā)性如何，漏桶算法強(qiáng)迫輸出按平均速率進(jìn)行。北郵計(jì)算機(jī)學(xué)院：漏桶算法示意圖流量整形前的輸入流量整形后的輸出(漏桶大小為1MB)北郵計(jì)算機(jī)學(xué)院：令牌桶算法（The

Token

Bucket

Algorithm）漏桶算法不夠靈活，因此加入令牌機(jī)制；基本思想：漏桶存放令牌，每T秒產(chǎn)生一個(gè)令牌，令牌累積到超過漏桶上界時(shí)就不再增加。分組傳輸之前必須獲得一個(gè)令牌，傳輸之后刪除該令牌；漏桶算法與令牌桶算法的區(qū)別流量整形策略不同漏桶算法不允許空閑主機(jī)積累發(fā)送權(quán)，以便以后發(fā)送大的突發(fā)數(shù)據(jù)；

令牌桶算法允許積累發(fā)送權(quán)，最大為桶的大小。丟棄的對象不同漏桶中存放的是數(shù)據(jù)，桶滿了丟棄數(shù)據(jù)分組；令牌桶中存放的是令牌，桶滿了丟棄令牌，不丟棄數(shù)據(jù)分組。北郵計(jì)算機(jī)學(xué)院：如何計(jì)算“以最大速率發(fā)送突發(fā)數(shù)據(jù)的持續(xù)時(shí)間”的方法突發(fā)時(shí)間長度為S；令牌桶的容量為C字節(jié)，令牌的到達(dá)速率為p字節(jié)/秒，最大的輸出速率為M字節(jié)/秒

則在長度為S秒的最大速度突發(fā)過程中，字節(jié)的數(shù)量為MS，則

MS

=

C+pS

S＝

C/(M-p)北郵計(jì)算機(jī)學(xué)院：(c)

250

KB(d)

500

KB(e)

750

KB.令牌桶＋漏桶在令牌桶后加一個(gè)漏桶，實(shí)現(xiàn)更平滑的整形效果網(wǎng)絡(luò)最大速率>漏桶的速率>令牌到達(dá)速率令牌桶的容量=500KB

漏桶速率=10MB/s10S=21.74*25+(S-21.74)*2S=62.51ms（書后習(xí)題28）最大分組長度為1000字節(jié)，令牌桶速率為每秒10MB，令牌桶的大小為1M字節(jié)，最大傳輸速率為每秒50MB，請問以最大速度傳輸?shù)耐话l(fā)數(shù)據(jù)會(huì)持續(xù)多長時(shí)間？北郵計(jì)算機(jī)學(xué)院：(書后習(xí)題27）在一個(gè)6Mbps的網(wǎng)絡(luò)上，有一臺(tái)主機(jī)通過一個(gè)令牌桶進(jìn)行流量調(diào)整。令牌桶的填充速率為1Mbps。初始時(shí)候它被填充到8Mb的容量，請問該計(jì)算機(jī)以6Mbps的全速率可以傳輸多長時(shí)間？北郵計(jì)算機(jī)學(xué)院：判斷題：使用令牌桶和漏桶算法時(shí)，都會(huì)有突發(fā)數(shù)據(jù)輸出？北郵計(jì)算機(jī)學(xué)院：5.5

網(wǎng)絡(luò)互連同類型的網(wǎng)絡(luò)互聯(lián)是少數(shù)派。學(xué)習(xí)的重點(diǎn)是互連的方法。北郵計(jì)算機(jī)學(xué)院：互聯(lián)網(wǎng)的基本概念北郵計(jì)算機(jī)學(xué)院：網(wǎng)絡(luò)互聯(lián)的示例

LAN-LAN

LAN-WAN

WAN-WAN

LAN-WAN-LAN北郵計(jì)算機(jī)學(xué)院：5.5.2如何連接網(wǎng)絡(luò)在上在對等層轉(zhuǎn)換北郵計(jì)算機(jī)學(xué)院：5.5.2如何連接網(wǎng)絡(luò)應(yīng)用層：應(yīng)用網(wǎng)關(guān)

傳輸層：傳輸網(wǎng)關(guān)網(wǎng)絡(luò)層：路由器數(shù)據(jù)鏈路層：網(wǎng)橋和交換機(jī)物理層：集線器和中繼器數(shù)據(jù)鏈路層5應(yīng)用層4傳輸層3網(wǎng)絡(luò)層2

數(shù)據(jù)鏈路層1物理層Bridge

&

RouterBridge

VS

RouterBridge(Switch):MAC

addressRouter:Layer-3

address

（如IP地址）欲知詳情，且聽下節(jié)分解！！網(wǎng)絡(luò)提供了兩種類型的服務(wù)：－面向

（虛電路）－面向無連接（數(shù)據(jù)報(bào)）下面將針對這兩種服務(wù)分別研究互聯(lián)的方法北郵計(jì)算機(jī)學(xué)院：5.5.3

級聯(lián)虛電路（Concatenated

Virtual

Circuits）??

工作過程（與虛電路子網(wǎng)工作過程相似）??

建立連接??

當(dāng)目的主機(jī)不在子網(wǎng)內(nèi)時(shí)，則在子網(wǎng)內(nèi)找一個(gè)離目的網(wǎng)絡(luò)最近的路由器，與之建立一條虛電路；??

該路由器與外部網(wǎng)關(guān)建立虛電路；??

該網(wǎng)關(guān)與下一個(gè)子網(wǎng)中的一個(gè)路由器建立虛電路；??

重復(fù)上述操作，直到到達(dá)目的主機(jī)。??

傳輸數(shù)據(jù)??

相同連接的包沿同一虛電路按序號(hào)傳輸；??