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

問(wèn)題

1、網(wǎng)絡(luò)層提供什么服務(wù)？基本功能？

2、路由器是如何尋找路由的？

3、Internet網(wǎng)絡(luò)層有哪些協(xié)議？協(xié)議的具

體內(nèi)容？

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

■ISO給網(wǎng)絡(luò)層的定義

■網(wǎng)絡(luò)層為一個(gè)網(wǎng)絡(luò)連接的兩個(gè)傳送實(shí)體間交

換網(wǎng)絡(luò)服務(wù)數(shù)據(jù)單元提供功能和規(guī)程的方法,

它使傳送實(shí)體獨(dú)立于路由選擇和交換的方式。

■網(wǎng)絡(luò)層要解決的關(guān)鍵問(wèn)題是了解通信子

網(wǎng)的拓?fù)浣Y(jié)構(gòu)，選擇路由。

網(wǎng)絡(luò)層的功能

application

transport

network

■在收發(fā)主機(jī)之間QCITCInnx

physical

尋找路由，傳輸

分組

■網(wǎng)絡(luò)層協(xié)議必須

在每一臺(tái)主機(jī)和

路由器上實(shí)現(xiàn)

問(wèn)題

1、網(wǎng)絡(luò)層提供什么服務(wù)？基本功能？

2、路由器是如何尋找路由的？

3、Internet網(wǎng)絡(luò)層有哪些協(xié)議？協(xié)議的具

體內(nèi)容？

兩個(gè)新概念

■根據(jù)路由方式的不同，分為“虛電路”

和“數(shù)據(jù)報(bào)”網(wǎng)絡(luò)。

■什么是“虛電路”網(wǎng)絡(luò)？

■什么是“數(shù)據(jù)報(bào)”網(wǎng)絡(luò)？

，虛電路

T數(shù)據(jù)傳輸前，收發(fā)雙方需要建立連接,尋找路由，并

通過(guò)虛電路號(hào)(VC)標(biāo)識(shí)路徑，數(shù)據(jù)傳輸結(jié)束后斷開(kāi)。

■每個(gè)分組攜帶VC標(biāo)識(shí)(而不是信宿主機(jī)的ID),通過(guò)

VC路由數(shù)據(jù)包。

application

application

transport

transport

network4.Callconnected3.AcceptcuI

network

datalink；.Initiatecall2.incomingc11

datalink

physical

physical

■虛電路特點(diǎn)

L每個(gè)在收發(fā)雙方路徑上的路由器需要為正在傳輸中的

連接維持“狀態(tài)”

■鏈路，路由器資源（帶寬，緩存等）可被分能給VC

-需要信令協(xié)議來(lái)建立、維護(hù)、斷開(kāi)VC

■應(yīng)用在ATM,幀中繼，X.25（電信級(jí)服務(wù)）

■不是應(yīng)用在今天的Internet

“斷發(fā)雙方之間的路徑表現(xiàn)得如同電話線路一

-網(wǎng)絡(luò)內(nèi)部有較多的智能和性能指標(biāo)

-沿收發(fā)路徑上的網(wǎng)絡(luò)結(jié)點(diǎn)的操作比較復(fù)雜

]■數(shù)據(jù)報(bào)(Datagram)網(wǎng)絡(luò)：因特網(wǎng)模型

系-般分組使用信宿乳的ID進(jìn)行路由選擇

-路由過(guò)程類似“司機(jī)問(wèn)路”

-在網(wǎng)絡(luò)層沒(méi)有連接建立過(guò)程

-路由器：沒(méi)有端對(duì)端的連接狀態(tài)

application

transport

network

datalink1.Senddata

physical一口口

數(shù)據(jù)報(bào)和虛電路比較

問(wèn)題，:癱報(bào)子網(wǎng)[觸斜網(wǎng)

呼叫建立過(guò)程不需要必須，

地址信息每個(gè)包都有完整源目的地每個(gè)包含虛電路號(hào)

址信息

路由選擇每個(gè)包獨(dú)立選擇僅建立虛電路選擇

路由故障不作處理終止本次傳輸

相對(duì)較差:

可靠性相對(duì)可靠

差錯(cuò)處理由終端解決“由網(wǎng)絡(luò)解決

接受順序無(wú)序按序接受

數(shù)據(jù)報(bào)還是VC網(wǎng)絡(luò)：why?

犬I特網(wǎng)ATM

-數(shù)據(jù)交換在計(jì)算機(jī)之間進(jìn)行■電話網(wǎng)絡(luò)演化而來(lái)

-“彈性”服務(wù)，沒(méi)有嚴(yán)格的實(shí)■人們的交流：

時(shí)性要求-嚴(yán)格要求實(shí)時(shí)性，和可靠

-“聰明”的端系統(tǒng)（計(jì)算機(jī)）-需要服務(wù)承諾

■可進(jìn)行自適應(yīng)，執(zhí)行控制，出■“傻瓜式”的端系統(tǒng)

錯(cuò)恢復(fù)■電話機(jī)

-網(wǎng)絡(luò)內(nèi)部比較簡(jiǎn)單，”邊緣上〃■復(fù)雜性在網(wǎng)絡(luò)內(nèi)部

比較復(fù)雜

-利用了許多鏈路類型

■各具有不同的特性

■統(tǒng)一服務(wù)標(biāo)準(zhǔn)十分困難

如何選擇路由?

■任何網(wǎng)絡(luò)層都需要路由選擇

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

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

擇。

-通過(guò)路由算法選擇路由，路由算法是網(wǎng)絡(luò)層軟件的一

部分

,路由選擇

產(chǎn)路由選擇算法——

目標(biāo)：在收發(fā)雙方的通信過(guò)程

中為分組（所經(jīng)由的一系列路

由器中）確定一條“好”的路

徑

路由選擇算法的圖形抽象：

■圖中的結(jié)點(diǎn)是路由器

■圖中的線條為物理鏈路

■鏈路成本：延遲，￥費(fèi)

用，或擁塞的程度

路由算法分類

局或分散的信息?靜態(tài)或動(dòng)態(tài)的？

■所有路由器都有完整的拓■路由變化較少的情況

撲邏輯，鏈路成本信息

■路由變化較快的情況

■路由器只了解物理上鄰接-定期更新

的路由器，了解到達(dá)這些■為了響應(yīng)鏈路成本的

路由器的鏈路成本

變化

■通過(guò)迭代計(jì)算處理，可與

相鄰路由器交換信息

路由算法的最優(yōu)化原則和匯集樹(shù)

■最優(yōu)化原則

■如果路由器J在路由器I到K的最優(yōu)路由上，

那么從J到K的最優(yōu)路由會(huì)落在同一路由上。

■匯集樹(shù)(SinkTree)

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

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

匯集樹(shù)；

-路由算法的目的是找出并使用匯集樹(shù)。

路由算法的最優(yōu)化原則和匯集樹(shù)

■最優(yōu)化原則

-匯集樹(shù)

(a)一個(gè)子網(wǎng)的拓?fù)浣Y(jié)構(gòu)(b)B節(jié)點(diǎn)的匯集樹(shù)

介紹相關(guān)的路由算法

最短路徑算法(Dijkstra)

■擴(kuò)散法(flooding)

-距離矢量算法

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

最短路由選擇

Dijkstra算法（1959萬(wàn)通過(guò)用邊的權(quán)值作為

距離的度量來(lái)計(jì)算最短路徑，有最少邊數(shù)的路

徑不一定是最短路徑

如下圖：5和4之間邊數(shù)最少的路徑是5234

但最短路徑是523674

卜最短路徑路由算法(ShortestPathRouting)

-Dijkstra算法舉例

5

卜最短路徑路由算法(ShortestPathRouting)

■Dijkstra算法舉例

?設(shè)節(jié)點(diǎn)1為源節(jié)點(diǎn)，算法如下：

令D(y)為節(jié)點(diǎn)1到節(jié)點(diǎn)V的距離,l@j)為直

接相連的兩個(gè)節(jié)點(diǎn)八/間的鏈路長(zhǎng)度，N為己

找到與節(jié)點(diǎn)1之間最短通路的節(jié)點(diǎn)集。

初始化：

N={1}

D(y)=/(LY)與1直接相連

s不與1直接相連

■最短路徑路由算法(ShortestPathRouting)

_■Dijkstra算法舉例

步驟ND(2)D(3)D(4)D(5)D(6)

~(0251raoT"

1＞在N外選擇離1最近的點(diǎn)(0,并將其收入N;

2、更新距離表；

對(duì)所有不屬于N的節(jié)點(diǎn)V,

D(v)=min[D(v),D(w)+/(w,v)]

3、若所有節(jié)點(diǎn)都己屬于N,則結(jié)束表更新，否則，

回到步驟b；........................

■最短路徑路由算法(ShortestPathRouting)

■.Dijkstra算法舉例

步驟ND(2)D(3)D(4)D(5)D(6)

初始化{1}2510000

1“，4}24128

2{124}241200

3{1,2,4,習(xí)23124

4{123,4,5}23124

5(1,2,3,45,6}23124

『最短路徑路由算法(ShortestPathRouting)

■Dijkstra算法舉例

■最短通路樹(shù)(匯集樹(shù))及對(duì)應(yīng)路由表

目的節(jié)點(diǎn)后繼節(jié)點(diǎn)

22

34

44

54

64

I介紹相關(guān)的路由算法

■最短路徑算法(Dijkstra)

■擴(kuò)散法(flooding)

-距離矢量算法

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

擴(kuò)散法(flooding)

[■不計(jì)算路徑，有路就走

如從5出發(fā)到4:

數(shù)據(jù)包從5—1,2;2—3,6;3—6,4;6—3,7;7-4

要解決的問(wèn)題：數(shù)據(jù)包重復(fù)到達(dá)某一節(jié)點(diǎn)，如3,6

擴(kuò)散法（續(xù)）

解決方法

＞在數(shù)據(jù)包頭設(shè)一計(jì)數(shù)器，每經(jīng)過(guò)一個(gè)節(jié)點(diǎn)

自動(dòng)加1,達(dá)到規(guī)定值時(shí)，丟棄數(shù)據(jù)包

＞在每個(gè)節(jié)點(diǎn)上建立登記表，則數(shù)據(jù)包再次

經(jīng)過(guò)時(shí)丟棄

缺點(diǎn)：重復(fù)數(shù)據(jù)包多，浪費(fèi)帶寬

優(yōu)點(diǎn)：可靠性高，路徑最短，常用于軍事

I介紹相關(guān)的路由算法

■最短路徑算法(Dijkstra)

■擴(kuò)散法(flooding)

-距離矢量算法

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

D-V(距離矢量)算法

(DistanceVectorRouting)

-是動(dòng)態(tài)、分布式算法。

■實(shí)現(xiàn)分布式算法的三要素：

Themeasurementprocess（測(cè)量）

Theupdateprotocol（更新鄰接點(diǎn)距離矢量）

Thecalculation（計(jì)算）

$D?V算法的工作原理

-每個(gè)路由器用兩個(gè)向量Dj和&來(lái)表示

該節(jié)點(diǎn)到網(wǎng)上所有節(jié)點(diǎn)的路徑距離

及其下一個(gè)節(jié)點(diǎn)

-相鄰路由器之間交換路徑信息

?各節(jié)點(diǎn)根據(jù)路徑信息更新路由表

di1:從節(jié)點(diǎn)i到節(jié)點(diǎn)1的時(shí)延向量

d⑵從節(jié)點(diǎn)I到節(jié)點(diǎn)2的時(shí)延向量

sM.從節(jié)點(diǎn)i到節(jié)點(diǎn)1的一條最小時(shí)延路徑上的下一個(gè)節(jié)點(diǎn)

s⑵從節(jié)點(diǎn)i到節(jié)點(diǎn)2的一條最小時(shí)延路徑上的下一個(gè)節(jié)點(diǎn)

其中「網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)

口一節(jié)點(diǎn)i的時(shí)延向量

djj一節(jié)點(diǎn)i到j(luò)的最小時(shí)延的當(dāng)前估計(jì)值

Sj—節(jié)點(diǎn)i的后繼節(jié)點(diǎn)向量

Sjj—從節(jié)點(diǎn)i到j(luò)的最小時(shí)延路徑上的下一節(jié)點(diǎn)

路由表的更新

djj=min（dix+dxj）（XeA）

（從i到j(luò)的時(shí)延取途經(jīng)每個(gè)節(jié)點(diǎn)時(shí)的時(shí)延的最小值）

Sjj=X（從倒j途經(jīng)的下一個(gè)節(jié)點(diǎn)為X）

其中：A—與i相鄰的所有節(jié)點(diǎn)的集合

4j—i到j(luò)的最短距離

至的正巨離

dIix八L—i1x

dxj—x到j(luò)的最短距離

J重新估計(jì)的延時(shí)

TD通過(guò)A通過(guò)I通過(guò)H通過(guò)Ki線路

A02420218A

_B—1236312820A

C2518193628I

D402782420H

E147302217I

F2320194030I

G183163118H

H172001912H

注意：A-I為21;IfA為24I210142210I

因?yàn)椋汗?jié)點(diǎn)A和I都是各自測(cè)J9117100-

得的距離，且不一定是同一K24222206K

時(shí)刻測(cè)得的，線路狀態(tài)是動(dòng)L29339915K

態(tài)變化的理

J到AJ到I延延IIHJ到K節(jié)點(diǎn)J的

時(shí)

延時(shí)時(shí)為為延時(shí)新路由表

當(dāng)前節(jié)點(diǎn)為一

J為81012為6

D?V算法的缺點(diǎn)

-交換的路徑信息量大

-路徑信息不一致

-收斂速度慢（壞消息）

-距離矢量中不考慮帶寬因子

■不適合大型網(wǎng)絡(luò)

無(wú)窮計(jì)算問(wèn)題

年好消息傳播得快，壞消息傳播得慢

ABCDEABCDE

A下網(wǎng)了

OO__OOOo一Q—-o-

00000000初始時(shí)12孑4初始時(shí)

1888第1次交換后3234第1次交換后

12coco第2次交換后3434第2次交換后

123co第3次交換后5454第3次交換后

1234第4次交換后5656第4次交換后

7676第5次交換后

7878第6次交換后

00000000

克服收斂速度慢的方法

-水平分裂

同距離矢量法，只是到X的距離并不是真正的距離，

對(duì)下方點(diǎn)通知真正的距離，對(duì)上方點(diǎn)，給出無(wú)窮大

如上圖中的C點(diǎn)，它向D通知到A的真正距離，而向B

通知到A的距離是無(wú)窮大

■Holddown

當(dāng)發(fā)現(xiàn)不通時(shí)，不重新選路徑，而是把它設(shè)成無(wú)窮大

I介紹相關(guān)的路由算法

■最短路徑算法(Dijkstra)

■擴(kuò)散法(flooding)

-距離矢量算法

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

L-S（鏈路狀態(tài)）算法

.LinkStateRouting）

■基本思想

＞發(fā)現(xiàn)它的鄰接節(jié)點(diǎn)，并得到其網(wǎng)絡(luò)地址＞

＞測(cè)量它到各鄰接節(jié)點(diǎn)的延遲或開(kāi)銷〉

＞組裝一個(gè)分組以告知它剛知道的所有信息〉

＞將這個(gè)分組發(fā)給所有其他路由器＞

A計(jì)算到每個(gè)其他路由器的最短路徑＞

發(fā)現(xiàn)鄰接節(jié)點(diǎn)

■當(dāng)一個(gè)路由器啟動(dòng)后，向每個(gè)點(diǎn)到點(diǎn)線

路發(fā)送HELLO分組，另一端的路由器發(fā)

送回來(lái)一個(gè)應(yīng)答來(lái)說(shuō)明它是誰(shuí)

L-S（鏈路狀態(tài)）算法

.LinkStateRouting）

■基本思想

＞發(fā)現(xiàn)它的鄰接節(jié)點(diǎn)，并得到其網(wǎng)絡(luò)地址

＞測(cè)量它到各鄰接節(jié)點(diǎn)的延遲或開(kāi)銷〉

＞組裝一個(gè)分組以告知它剛知道的所有信息〉

＞將這個(gè)分組發(fā)給所有其他路由器＞

A計(jì)算到每個(gè)其他路由器的最短路徑＞

測(cè)量線路開(kāi)銷

■發(fā)送一個(gè)ECHO分組要求對(duì)方立即響應(yīng)，

通過(guò)測(cè)量一個(gè)來(lái)回時(shí)間再除以2,發(fā)送方

就可以得到一個(gè)延遲估計(jì)值，想要更精

確些，可以重復(fù)這一過(guò)程，取其平均值

-S（鏈路狀態(tài)）算法

LinkStateRouting）

■基本思想

＞發(fā)現(xiàn)它的鄰接節(jié)點(diǎn)，并得到其網(wǎng)絡(luò)地址

＞測(cè)量它到各鄰接節(jié)點(diǎn)的延遲或開(kāi)銷「

＞組裝一個(gè)分組以告知它剛知道的所有信息〉

＞將這個(gè)分組發(fā)給所有其他路由器＞

A計(jì)算到每個(gè)其他路由器的最短路徑＞

I構(gòu)造分組

X網(wǎng)及其節(jié)點(diǎn)到其鄰節(jié)點(diǎn)（路由器）的線路開(kāi)銷測(cè)量值

（即延時(shí)，假設(shè)以ms計(jì)）

子網(wǎng)的鏈路、狀態(tài)及分組情況:

ABCDEF

序號(hào)序號(hào)序號(hào)序號(hào)序號(hào)序號(hào)

年齡年齡年齡年齡年齡年齡

A4B2C3A5B6

E\5)C2D3F7C1D7

F6E1F8E8

節(jié)點(diǎn)A僅與節(jié)點(diǎn)B和E相鄰

AfB的時(shí)延為4ms

AfE的時(shí)延為5ms

-S（鏈路狀態(tài)）算法

LinkStateRouting）

■基本思想

＞發(fā)現(xiàn)它的鄰接節(jié)點(diǎn)，并得到其網(wǎng)絡(luò)地址

＞測(cè)量它到各鄰接節(jié)點(diǎn)的延遲或開(kāi)銷「

＞組裝一個(gè)分組以告知它剛知道的所有信息

＞將這個(gè)分組發(fā)給所有其他路由器＞

A計(jì)算到每個(gè)其他路由器的最短路徑＞

發(fā)布鏈路狀態(tài)

用擴(kuò)散法（向鄰接的節(jié)點(diǎn)）發(fā)布鏈路狀態(tài)分組（以B為例，B的鄰接

點(diǎn)有A、C、F）

源節(jié)點(diǎn)E的鏈路狀態(tài)分組經(jīng)A和F到節(jié)點(diǎn)B,節(jié)點(diǎn)B必須

再招1E的狀態(tài)分組轉(zhuǎn)送到C,并向A和F發(fā)ACK

發(fā)送標(biāo)志ACK標(biāo)志

源序號(hào)年齡ACFAcF

A2160011100

F2160110001

E215900000o

C2060101010

D2159100011

-S（鏈路狀態(tài)）算法

LinkStateRouting）

■基本思想

＞發(fā)現(xiàn)它的鄰接節(jié)點(diǎn)，并得到其網(wǎng)絡(luò)地址

＞測(cè)量它到各鄰接節(jié)點(diǎn)的延遲或開(kāi)銷〉

＞組裝一個(gè)分組以告知它剛知道的所有信息

＞將這個(gè)分組發(fā)給所有其他路由器「

A計(jì)算到每個(gè)其他路由器的最短路徑＞

計(jì)算新路由

■用Dijstra算法計(jì)算到每個(gè)節(jié)點(diǎn)的路由

■得到該節(jié)點(diǎn)到每個(gè)節(jié)點(diǎn)的最短路徑

L6路由算法的優(yōu)缺點(diǎn)

-LSR的優(yōu)點(diǎn)

各路由器的路由信息的一致性好

收斂性好，壞消息也一樣傳播得快

適用于大型網(wǎng)絡(luò)，報(bào)文長(zhǎng)度與網(wǎng)絡(luò)規(guī)模關(guān)系不大

■LSR的缺點(diǎn)

每個(gè)路由器需要有較大的存儲(chǔ)空間

計(jì)算工作量大

思考

■Internet中如何實(shí)現(xiàn)路由？

-用到哪些路由算法？

■運(yùn)行什么路由協(xié)議？

因特網(wǎng)的分層路由選擇

因特網(wǎng)不是一個(gè)理想化的網(wǎng)絡(luò)，所以

■不可能所有的路由器完全一樣

■網(wǎng)絡(luò)不在一個(gè)“平面

規(guī)模：5千萬(wàn)臺(tái)以上信行政自治

宿主機(jī)：■internet=networkof

-不可能把所有主機(jī)存在networks（萬(wàn)網(wǎng)之網(wǎng)）

一個(gè)路由表中！■每個(gè)網(wǎng)管都會(huì)控制自身網(wǎng)

-路由表的交換可以把鏈絡(luò)中的路由選擇

路帶寬用掉大半！

G因特網(wǎng)中的路由選擇

■全球因特網(wǎng)是由諸多AutonomousSystems(AS)

互聯(lián)而成：

■小型自治系統(tǒng)(StubAS):中小型企業(yè)

.分區(qū)自治系統(tǒng)(MultihomedAS):大型企業(yè)(非跨越的)

■跨越式自治系統(tǒng)(TransitAS):NBP等

■兩層路由選擇：

■Intra-AS:由網(wǎng)管決定

■Inter-AS:唯一性的標(biāo)準(zhǔn)

因特網(wǎng)的AS層次

Intra-AS內(nèi)部（網(wǎng)關(guān)）路由器

*因特網(wǎng)的分層路由選擇

「網(wǎng)關(guān)路由器------

-聚合路由器可以形成分

區(qū)，”自治系統(tǒng)■AS中的特殊路由器

(autonomoussystems",■與其他同一AS中的路由

AS)器使用intra-AS路由選擇

■在同一AS中的路由器運(yùn)協(xié)議進(jìn)行交往

行同樣的路由選擇協(xié)議-同時(shí)負(fù)責(zé)同AS以外的信

.Mintra-AS"路由選擇宿進(jìn)行交往或路由選擇

協(xié)議■運(yùn)行/力招/?45路由選

-不同AS中的路由器可擇協(xié)議與其他的網(wǎng)關(guān)

以運(yùn)行不同的intra-路由器進(jìn)行交互

AS路由選擇協(xié)議

Lgtra-AS和Inter-AS路由選擇

網(wǎng)關(guān)：

?在網(wǎng)關(guān)服務(wù)器之間

A.a進(jìn)行inter-AS路

A.c由選擇

B?在AS內(nèi)部進(jìn)行

intra-AS路由選

擇

A

to/fromA.d

Intra-AS和Inter-AS路由選擇

Inter-AS

—

C.brouting

between

A.QAandBHosi

A.

B

Host

o

hl

A

Intra-ASrouting

withinASA

■inter-AS利intra-AS因特網(wǎng)路由選擇協(xié)議應(yīng)用

舉例

Intra-AS路由選擇協(xié)議

■也稱為內(nèi)部網(wǎng)關(guān)協(xié)議InteriorGatewayProtocols（IGP）

■最常用的IGP有：

■RIP:RoutingInformationProtocol（路由選擇信息協(xié)

議）

■OSPF:OpenShortestPathFirst（開(kāi)放式最短路徑優(yōu)

先（協(xié)議））

■IGRP:InteriorGatewayRoutingProtocol（內(nèi)部網(wǎng)

關(guān)路由選擇協(xié)議，Cisco產(chǎn)權(quán)）

.RIP(RoutingInformationProtocol)

^^巨離向量算法(口15131^6vectoralgorithm)

■含在BSD-UNIX1982版中

■距離的度量單位：#ofhops(max=15hops)

■Canyouguesswhy?

■距離向量：通過(guò)Response報(bào)文每隔30秒交換一次（也稱為

廣^-advertisement）

IP(RoutingInformationProtocol)

DestinationNetworkNextRouterNum.ofhopstodest

wA2

yB2

zB7

x

路由器D中的路由表

RIP：鏈路失效和恢復(fù)

果某條鏈路在180秒內(nèi)沒(méi)有被聽(tīng)到廣告相鄰

結(jié)點(diǎn)/鏈路被申明取消（dedareddead）

■經(jīng)由該結(jié)點(diǎn)的路由被終止

■新的廣告送往所有其他相鄰結(jié)點(diǎn)

■其他相鄰結(jié)點(diǎn)依次發(fā)出新的廣告（如果路由表

發(fā)生變化）

■這樣鏈路失效的信息迅速傳遍整個(gè)網(wǎng)絡(luò)

■使用抑毒措施來(lái)防止乒乓循環(huán)（設(shè)置有限距離

=16hops）

土RIP路由表處理

路由表通過(guò)應(yīng)用層的進(jìn)程route-d（daemon-守護(hù)程

序）來(lái)管理

■由應(yīng)用層進(jìn)程管理的路由表為通過(guò)UDP的廣告調(diào)用，并

周期性重復(fù)

RIP路由表舉例

■router:giroflee.eurocom.fr

DestinationGatewayFlagsRefUseInterface

UH026492loO

192.168.2.U213faO

193.55.114.U358503leO

192.168.3.U225qaaO

U30leO

default29UG0143454

■連接3個(gè)C類網(wǎng)絡(luò)(LAN)

■路由器僅僅知道所連LAN的路由

■默認(rèn)路由器(Defaultrouter)用于“goup(上行)〃

■組播地址路由(Routemulticastaddress):

■回授接口(Loopbackinterface,fordebugging)

OSPF(OpenShortestPathFirst)開(kāi)放式最

短路徑優(yōu)先(協(xié)議)

■“open-開(kāi)放”：向公眾開(kāi)放

■使用鏈路狀態(tài)算法(LinkStatealgorithm)

■LS分組傳播

■在每個(gè)結(jié)點(diǎn)存放網(wǎng)絡(luò)的拓?fù)鋱D

-路由計(jì)算使用Dijkstra算法

■OSPF廣告為每個(gè)相鄰的路由器配置一個(gè)條目

■廣告彌散到整個(gè)AS(viaflooding-泛洪法)

OSPF“先進(jìn)"性（RIP所不具備的）

。全性：所有的OSPF報(bào)文須經(jīng)認(rèn)證（以防止各種可能的

攻擊）；使用TCP連接

-對(duì)每條鏈路來(lái)說(shuō)，對(duì)不同的TOS（eg,在衛(wèi)星鏈路上將盡力

而為的服務(wù)設(shè)成“低值”；而將實(shí)時(shí)應(yīng)用設(shè)成高值）可產(chǎn)生

多種成本計(jì)算標(biāo)準(zhǔn)

-多種成本計(jì)算標(biāo)準(zhǔn)可以支持集成化的單播和組播

（multicast）:

-組播OSPF（MOSPF）使用與OSPF相同的拓?fù)鋽?shù)據(jù)庫(kù)

■在大型域中可以使用層次型OSPF

居次型OSPF

boundaryrouter

Area3

Areo1

Area2

層次型OSPF

層結(jié)構(gòu)：本地，主干.

-鏈路狀態(tài)只是在本地范圍內(nèi)廣告

-每個(gè)結(jié)點(diǎn)具有詳細(xì)的本地拓?fù)洌粚?duì)其他區(qū)域中的網(wǎng)絡(luò)僅

知在某個(gè)方向(最短路徑).

-區(qū)界路由器(Areaborderrouters):“匯總”了所在區(qū)域

中到達(dá)各網(wǎng)絡(luò)的距離，同時(shí)向其他區(qū)界路由器發(fā)廣告.

■主干路由器(Backbonerouters):僅限于在主干上運(yùn)行

OSPF路由算法.

■邊界路由器(Boundaryrouters):連接其他的AS.

IGRP(InteriorGatewayRoutingProtocol)內(nèi)

部網(wǎng)關(guān)路由選擇協(xié)議

■CISCO產(chǎn)權(quán)；RIP的后繼者之一(mid80s)

■路由向量算法，類似RIP

■采用若干成本計(jì)算標(biāo)準(zhǔn)(delay,bandwidth,

reliability,loadetc)

■使用TCP交換路由更新信息

■通過(guò)基于獷筋能篁的分布式更新算法(DUAL)

產(chǎn)生無(wú)循環(huán)的路由選擇

Inter-AS路由選擇

.■因特網(wǎng)inter-AS路由選擇:BGP

fl^F(BorderGatewayProtocol,邊界網(wǎng)關(guān)協(xié)議)：事實(shí)

上的忠惟

■路徑向量(PathVector)協(xié)議：

-與距離向量協(xié)議類似

■每個(gè)邊界網(wǎng)關(guān)(BorderGateway)向其對(duì)等的相鄰實(shí)

體(peers)廣播通往信宿的螫奈琳經(jīng)(Le,一系列

ASs)

-E.g.,網(wǎng)關(guān)X可以發(fā)送從它通往信宿Z的路經(jīng)：

Path(X,Z)=X,Y1,Y2,Y3,...,Z

人因特網(wǎng)inter-AS路由選擇:BGP

網(wǎng)關(guān)X向?qū)Φ染W(wǎng)關(guān)W發(fā)送了它存有的路經(jīng)

-W可以選擇或不選擇X所提供的路經(jīng)

-成本，策略(不通過(guò)競(jìng)爭(zhēng)對(duì)手的AS),預(yù)防循環(huán)等緣由.

■如果W選擇了X廣告的路經(jīng)，那么：

Path(W,Z)=w,Path(X,Z)

■注意：X可以通過(guò)向其他對(duì)等實(shí)體發(fā)布路由信息來(lái)控制所

進(jìn)入的通信流量：

-e.g.,不讓路由通過(guò)Z-＞不要發(fā)布有關(guān)通向Z的廣告

特網(wǎng)inter-AS路由選擇:BGP

Kbp使用TCP交換報(bào)文.

■BGP報(bào)文:

-OPEN:打開(kāi)通往對(duì)等實(shí)體的TCP連接并對(duì)發(fā)送者進(jìn)行

認(rèn)證

-UPDATE:刊出新的路經(jīng)（或撤銷舊路經(jīng)）

-KEEPALIVE:在不進(jìn)行UPDATES時(shí)保持連接的激活；也

用來(lái)ACKsOPEN請(qǐng)求

-NOTIFICATION:報(bào)告先前報(bào)文的錯(cuò)誤;也用來(lái)關(guān)閉連接

什么Intra-和Inter-AS路由選擇不同？

■Inter-AS:網(wǎng)管需要控制自己信息流通的路經(jīng)，還

有誰(shuí)能路經(jīng)并通過(guò)其管轄的網(wǎng)絡(luò).

*■Intra-AS:單一的管理體制，無(wú)需選擇策略

規(guī)模：

■層次型路由選擇可以縮小路由表，并減少更新流量

性能：

■Intra-AS:將注意力集中在性能上

■Inter-AS:策略的考慮要超過(guò)對(duì)性能的要求

思考

■除了路由算法，還有什么影響路由器的

性能？

■如何選擇路由器？

路由器結(jié)構(gòu)概述

路由器的兩個(gè)關(guān)鍵功能：

■運(yùn)行路由算法/協(xié)議(RIP,OSPF,BGP)

■交換分組于輸入鏈路到輸出鏈路之間

輸入端口功能

lookup,

datalinkforwarding

line|、switch

processing

termination(protocol,llllllll

queueingfabric

decapsulation)

位流級(jí)的接收

分散化的交換;

e.g.Ethernet■按照給出的分組信宿，使用輸入端口的內(nèi)存

z中存儲(chǔ)的路由選擇表，查找輸出端口

-目標(biāo)：以“線路速度”完成輸入端口的處理

■排隊(duì)：假如分組到達(dá)的數(shù)度快于轉(zhuǎn)發(fā)到交換

網(wǎng)絡(luò)的(switchfabric)速度時(shí)

■輸入端口上的排隊(duì)

■交換網(wǎng)絡(luò)的處理速度低于所有輸入端口之和->導(dǎo)致分組

在輸入端口的隊(duì)列中排隊(duì)

■排頭(Head-of-the-Line(HOL))阻塞：在隊(duì)列的排頭上

的分組擋住了其他分組的前移

■由于輸入緩存的溢出導(dǎo)致了排隊(duì)延遲和數(shù)據(jù)丟失!

43-

switch

-O-fabric

40F-

outputportcontentiongreenpacket

attimet-onlyoneredexperiencesHOLblocking

packetcanbetransferred

輸出端口

switch

queuing:datalink

,processingT，linef

fabricbuffer

management(protocol,termination

decapsulation)

■緩存當(dāng)來(lái)自交換網(wǎng)絡(luò)的分組到達(dá)速度高于傳輸

速率時(shí)，需要進(jìn)行緩存

■謖度源財(cái)從隊(duì)列中的分組中選擇傳輸

不出端口的排隊(duì)

OutputPortContentionOnePacket

alTimetTimeLater

-當(dāng)交換速度超進(jìn)俞出線路的速率時(shí)，需要進(jìn)行

緩存

■輸出端口的溢出會(huì)造成排隊(duì)（延遲）和數(shù)據(jù)丟

九

三類交換網(wǎng)絡(luò)

AX

P口limnlimn0o*

B

limnliiiiniM

z

p口limn川川iOz>

bus

?口口IIIIIII

B

匚口IIIIIII

?crossbar

，口口IIIIIII

內(nèi)存交換(SwitchingViaMemory)

第一代路由器：

■分組通過(guò)系統(tǒng)的（單個(gè)）CPU拷貝

-速度受到內(nèi)存帶寬的限制（每個(gè)分組需2次穿越系統(tǒng)總線）

InputMemoryOutput

現(xiàn)代路由器：

■輸入端口處理器執(zhí)行查詢路由表、和拷貝的功能

■CiscoCatalyst8500

總線交換(SwitchingViaBus)

■分組通過(guò)一條共享的總線從輸入端口X

的內(nèi)存?zhèn)鬟f到輸出端口的內(nèi)存llllllll

Y

■總線競(jìng)爭(zhēng)：交換速率受限于總線的帶llllllll

N

寬llllllll

bus

■1Gb/s總線,Cisco1900:對(duì)訪問(wèn)接入

和企業(yè)級(jí)的路由器已經(jīng)足夠（但還不

適應(yīng)在區(qū)域或主干級(jí)線路上使用）

通過(guò)內(nèi)聯(lián)網(wǎng)絡(luò)交換(SwitchingViaAn

InterconnectionNetwork)

■克服了總線帶寬的限制

■Banyannetworks,內(nèi)聯(lián)網(wǎng)絡(luò)技術(shù)在發(fā)展初期是

用來(lái)連接多處理器系統(tǒng)中的處理器的

■設(shè)計(jì)先進(jìn)：把分組分割成固定長(zhǎng)度的單元，再把

這些單元送入交換網(wǎng)絡(luò)

■Cisco12000:通過(guò)內(nèi)聯(lián)網(wǎng)絡(luò)交換速度為若干

Gb/s

問(wèn)題

1、網(wǎng)絡(luò)層提供什么服務(wù)？基本功能？

2、路由器是如何尋找路由的？

3、Internet網(wǎng)絡(luò)層有哪些協(xié)議？協(xié)議的具

體內(nèi)容？

因特網(wǎng)網(wǎng)絡(luò)層

Transportlayer：TCP,UbP

IPprotocol

(addressingconventions

,datagramformat

Network,packethandlingconventions

layer

ICMPprotocol

,errorreporting

,router"signaling”

Linklayer

physicallayer

■將數(shù)據(jù)報(bào)傳送到遠(yuǎn)端主機(jī)，包括路由選擇

■定義IP數(shù)據(jù)報(bào)，這是Internet中最基本的傳

輸單位

-定義尋址方式，即IP地址

■進(jìn)行數(shù)據(jù)報(bào)的分解和重組，例如IP和X,25數(shù)

據(jù)交換

網(wǎng)際協(xié)議IP特性

■面向無(wú)連接協(xié)議

.采用數(shù)據(jù)報(bào)不建立虛電路

■IP在傳輸過(guò)程中不進(jìn)行錯(cuò)誤檢測(cè)

■不檢查目的主機(jī)是否確實(shí)收到數(shù)據(jù)

■通信信道品質(zhì)良好的網(wǎng)絡(luò)IP協(xié)議仍是可信賴

的

IP協(xié)議

■IP包格式

-IP包的分段與重組

■IP地址

IP包格式

16

31

版本|頭部長(zhǎng)服務(wù)類型總長(zhǎng)

標(biāo)識(shí)段偏移

生存時(shí)間類型_______頭__部_校驗(yàn)和

源IP地址

目的IP地址

IP可選項(xiàng)(可以省略)充填域

數(shù)據(jù)開(kāi)始..

~版本為4(Ipv4)

頭部長(zhǎng)以32位字長(zhǎng)為單位

IP包格式（續(xù)）

■服務(wù)類型：8位

01234567

優(yōu)先級(jí)DTR未用

由用戶指定數(shù)由路由器選擇哪

Throughput

據(jù)報(bào)的優(yōu)先級(jí)個(gè)最優(yōu)先，但通

總長(zhǎng)「茍括報(bào)咫%數(shù)瑞黑ty最踐奧

1,

即65535個(gè)字節(jié)

標(biāo)識(shí)、標(biāo)志、段偏移：用于數(shù)據(jù)報(bào)的分段

生存時(shí)間：以秒為單位

也可以經(jīng)過(guò)路由器的個(gè)數(shù)為單位

IP包格式（續(xù)）

-類型或協(xié)議

TCP6UDP17

ICMP1OSPF89

-頭部校驗(yàn)和：按16位相加，結(jié)果求反

■源和目的地址：32位

-IP可選項(xiàng)：用于控制和測(cè)試

-充填域：湊成32位的整倍數(shù)

IP協(xié)議

-IP包格式

-IP包的分段與重組

■IP地址

分段過(guò)程

L按MTU的及數(shù)據(jù)包的實(shí)際負(fù)載長(zhǎng)度計(jì)算所需

段數(shù)，并劃分，分段應(yīng)滿足兩個(gè)條件：

＞各段在不大于MTU的前提下，盡可能地大

＞被分出的段的長(zhǎng)度應(yīng)為8的整倍數(shù)

■原數(shù)據(jù)包的報(bào)頭作為每段的數(shù)據(jù)包報(bào)頭，并

修改其中的某些字段，指明：

＞屬原來(lái)的哪個(gè)分組（數(shù)據(jù)包）

＞屬原來(lái)分組中的第幾個(gè)分段

＞哪一個(gè)是段尾

通過(guò)標(biāo)志、標(biāo)識(shí)和段偏移實(shí)現(xiàn)

標(biāo)識(shí)(identifier)：16位

發(fā)送方每發(fā)送一個(gè)報(bào)文編號(hào)加一

各分段的標(biāo)識(shí)相同

源地址加標(biāo)識(shí)來(lái)區(qū)分各個(gè)分段

標(biāo)志(flag)：3位

保留DFMF

DF=O允許分段

=1不允許分段如剛起動(dòng)時(shí)，即Boot時(shí)不允許分段

MF=0最后一段

=1段未結(jié)束

■段偏移(fragmentationoffset)：13位

實(shí)際偏移量=段偏移值X8Byte

IP包分段舉例

「一個(gè)物理網(wǎng)絡(luò)的MTU為1500B,現(xiàn)要傳輸一個(gè)數(shù)據(jù)

報(bào)（其報(bào)頭為20B,數(shù)據(jù)區(qū)長(zhǎng)度為1400B）至（JMTU

為620B的另一個(gè)物理網(wǎng)絡(luò)，其分段情況為：

IP包分段舉例（續(xù)）

■每個(gè)分段的報(bào)頭其基本部分（如源地址、

目的地址等）是copy原數(shù)據(jù)報(bào)的報(bào)頭，

與分段相關(guān)的域則應(yīng)重新生成

原報(bào)頭分段1報(bào)頭分段2報(bào)頭分段3報(bào)頭

ID標(biāo)識(shí)33030330303303033030

M標(biāo)志0/I10

OS段偏移0//o力75150

/620///620

TL總長(zhǎng)1420，//—//220

段未結(jié)束75x8=600

________________________________z\,

數(shù)據(jù)報(bào)分段的重組

F重組是在各分段都到達(dá)目的地后才進(jìn)行

每個(gè)分段可以走不同的路徑

減少路由器中保存的信息量及路由器的工作量

■途中的任意一個(gè)路由器都無(wú)法重組

重組必須在所有的分段全部收到后，才可進(jìn)行

■Internet的互聯(lián)網(wǎng)層是遵循盡力而為來(lái)傳送IP包

的，也存在力不從心的時(shí)候，此時(shí)只能丟棄

重組主機(jī)I尋遵循：

要么重組成功，要么全部丟棄的原則

IP包實(shí)例

-現(xiàn)假設(shè)截獲一IP包，其中前20字節(jié)分別

為0x450x000x000x3COxlA0x37

0x000x000x800x010x6E0x31OxCO

0xA80x010xD40xD30x9BOxlC0x41,

試分析該IP包頭中每一個(gè)字段的值及含

義。

IP協(xié)議

-IP包格式

-IP包的分段與重組

>IP地址

IP地址的層次結(jié)構(gòu)和分類

HostID|

地址類別網(wǎng)絡(luò)數(shù)主機(jī)數(shù)

A0-127(126)16777216-2

B128-191(16384)65536-2

C192?223(2097152)256-2

,IP地址的表示

點(diǎn)分十進(jìn)制表示如：54

■特殊IP地址______________________

前綴后綴地址類型用途

全0全0本機(jī)啟動(dòng)時(shí)使用

網(wǎng)絡(luò)ID全0網(wǎng)絡(luò)標(biāo)識(shí)一個(gè)網(wǎng)絡(luò)

網(wǎng)絡(luò)ID全1直接廣播在指定網(wǎng)上廣播

全1全1有限廣播在本地網(wǎng)上廣播

127任意測(cè)試()

無(wú)盤(pán)工作站在啟動(dòng)時(shí)尚不知道自己所處的網(wǎng)絡(luò)ID,所

以用32為全1地址在本網(wǎng)段內(nèi)廣播，請(qǐng)求回答

\____________________________________________7

私有網(wǎng)絡(luò)的IP地址

地址類別地址

A類-55

B類-55

C類-55

思考

-兩級(jí)IP地址分類的地址利用率?

A類

128個(gè)網(wǎng)絡(luò)號(hào)

每個(gè)網(wǎng)絡(luò)有四百萬(wàn)個(gè)主機(jī)號(hào)

■■

H?一萬(wàn)六千個(gè)網(wǎng)絡(luò)號(hào).

H?每個(gè)網(wǎng)絡(luò)有六萬(wàn)五千個(gè)主機(jī)號(hào)■

?超過(guò)兩百萬(wàn)個(gè)網(wǎng)絡(luò)號(hào)

e每個(gè)網(wǎng)絡(luò)有二百五十六個(gè)主機(jī)號(hào)

二維IP地址缺點(diǎn)

■一個(gè)路由器端口的連接（一個(gè)物理網(wǎng)段）至少

組成一個(gè)網(wǎng)絡(luò)

?按原來(lái)的地址結(jié)構(gòu)（二維結(jié)構(gòu)），一個(gè)網(wǎng)絡(luò)至

少需要一個(gè)C類地址，因?yàn)橐粋€(gè)網(wǎng)絡(luò)需要有一

個(gè)唯一的網(wǎng)絡(luò)地址

■IP地址的緊缺和地址分配中的浪費(fèi)形成一對(duì)矛

盾！

路由器連接的三個(gè)C類網(wǎng)絡(luò)

子網(wǎng)劃分一三維地址結(jié)構(gòu)

V原有地址結(jié)構(gòu)是二維的（網(wǎng)絡(luò)地址，主機(jī)地址），增

加地址結(jié)構(gòu)的維數(shù)，可提高地址分配的靈活性和可用

性

三維結(jié)構(gòu)：網(wǎng)絡(luò)地址，子網(wǎng)地址，主機(jī)地址

■例如：在一個(gè)C類地址中僅主機(jī)地址可由網(wǎng)管人員自

主分配，向主機(jī)地址域借位組成子網(wǎng)地址以形成三維

地址結(jié)構(gòu)

其借網(wǎng)皿地址位數(shù)的確定

子網(wǎng)地址

主機(jī)地址

A.

C類地址網(wǎng)絡(luò)地址XXXXXXXX

子網(wǎng)地址=0:表示本子網(wǎng)主機(jī)

不可作為有效目的地址使用

子網(wǎng)地址=1:子網(wǎng)地址全1,不可用

因此至少要借2位

子網(wǎng)地址位數(shù)的確定（續(xù)）

主機(jī)地址

-借7位:

/子網(wǎng)地址、

C類地址網(wǎng)絡(luò)地址XXXXXXXX

主機(jī)地址=0:子網(wǎng)地址，不可作為地址分配

主機(jī)地址=1:廣播地址，不可作為地址分配

因此最多可借6位

I子網(wǎng)掩碼

子網(wǎng)掩碼的作用

因?yàn)樽泳W(wǎng)地址的位數(shù)不是固定的，所以必須告知主機(jī)地址中哪

一部分是子網(wǎng)的網(wǎng)絡(luò)地址段，哪一部分是主機(jī)地址段

-子網(wǎng)掩碼使用與IP編址相同格式

子網(wǎng)掩碼的網(wǎng)絡(luò)地址部分和子網(wǎng)地址部分全為1,它的主機(jī)部分

全為0

■一個(gè)缺省C類IP地址的掩碼為

」子網(wǎng)掩碼（續(xù)）

一個(gè)C類主機(jī)地址為9~

子網(wǎng)地址=011的子網(wǎng)掩碼是：255.255.255,224

子網(wǎng)地址

網(wǎng)絡(luò)_地址___4__主耍_址

C類IP地址11001010011110000000001101100011

202120399

掩碼11111111111111111111111111100000

255255