Network Layer(計(jì)算機(jī)網(wǎng)絡(luò)課件)

弟7早

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

1

主要內(nèi)容（1）

7.1網(wǎng)絡(luò)層概述

7.2路由算法

7.2.1最優(yōu)化原則

7.2.2最短路徑路由算法

7.2.3洪泛算法

7.2.4基于流量的路由算法

7.2.5距離向量路由算法

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

7.2.7分層路由

7.2.8移動(dòng)主機(jī)的路由

2

主要內(nèi)容（2）

7.3擁塞控制算法

7.3.1擁塞控制的基本原理

7.3.2擁塞控制算法

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

7.4.1級(jí)聯(lián)虛電路

7.4.2無(wú)連接網(wǎng)絡(luò)互連

7.4.3隧道技術(shù)

7.4.4互聯(lián)網(wǎng)路由

7.4.5分段

7.4.6防火墻

3

主要內(nèi)容（3）

7.5INTERNET網(wǎng)絡(luò)層協(xié)議

7.5.1IP協(xié)議

7.5.2Internet控制協(xié)議

7.5.3內(nèi)部網(wǎng)關(guān)路由協(xié)議：OSPF

7.5.4外部網(wǎng)關(guān)路由協(xié)議：BGP

7.6路由器體系結(jié)構(gòu)和關(guān)鍵技術(shù)

4

7.1網(wǎng)絡(luò)層概述（1）

■iso定義

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

絡(luò)服務(wù)數(shù)據(jù)單元提供功能和規(guī)程的方法，它使傳

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

■網(wǎng)絡(luò)層是處理端到端傳輸?shù)淖畹蛯印?/p>

■網(wǎng)絡(luò)層要解決的關(guān)鍵問(wèn)題是了解通信子網(wǎng)的拓?fù)浣Y(jié)構(gòu)

,選擇路由。

5

7.1網(wǎng)絡(luò)層概述（2）

■網(wǎng)絡(luò)層設(shè)計(jì)的有關(guān)問(wèn)題

-為傳輸層提供服務(wù)

?面向連接服務(wù)

傳統(tǒng)電信的觀點(diǎn)：通信子網(wǎng)應(yīng)該提供可靠的、

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

?無(wú)連接服務(wù)

Internet的觀點(diǎn)：通信子網(wǎng)無(wú)論怎么設(shè)計(jì)都是

不可靠的，因此網(wǎng)絡(luò)層只需提供無(wú)連接服務(wù)。

?IP/ATM

6

Fig.5-1.RunningTCP/IPoveranATMsubnet.

7

7.1網(wǎng)絡(luò)層概述（3）

-網(wǎng)絡(luò)層的內(nèi)部組織

?虛電路（virtualcircuit）

?數(shù)據(jù)報(bào)（datagram）

-虛電路子網(wǎng)與數(shù)據(jù)報(bào)子網(wǎng)的比較

-路由器內(nèi)存空間與帶寬的權(quán)衡

＞虛電路方式，路由器需要維護(hù)虛電路的狀

態(tài)信息；

?數(shù)據(jù)報(bào)方式，每個(gè)數(shù)據(jù)報(bào)都攜帶完整的目

的/源地址，浪費(fèi)帶寬

8

7.1網(wǎng)絡(luò)層概述(4)

?連接建立時(shí)間與地址查找時(shí)間的權(quán)衡

＞虛電路需要在建立連接時(shí)花費(fèi)時(shí)間

＞數(shù)據(jù)報(bào)則在每次路由時(shí)過(guò)程復(fù)雜

?服務(wù)質(zhì)量與可靠性的權(quán)衡

＞虛電路方式很容易保證服務(wù)質(zhì)量

QoS(QualityofService),適用于實(shí)時(shí)操作

，但比較脆弱。

＞數(shù)據(jù)報(bào)不太容易保證服務(wù)質(zhì)量，但是對(duì)于

通信線路的故障，適應(yīng)性很強(qiáng)。

9

7.1網(wǎng)絡(luò)層概述（5）

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

-面向連接服務(wù)：將復(fù)雜的功能放在網(wǎng)絡(luò)層（通信子

網(wǎng)）。

-無(wú)連接服務(wù)：將復(fù)雜的功能放在傳輸層。

-通信子網(wǎng)提供的服務(wù)（面向連接或無(wú)連接）與通

信子網(wǎng)結(jié)構(gòu)（虛電路或數(shù)據(jù)報(bào)）沒(méi)有必然聯(lián)系。

-服務(wù)與子網(wǎng)結(jié)構(gòu)的不同組合的例子

10

UpperlayerTypeofsubnet

DatagramVirtualcircuit

UDP

UDPover

ConnectionlessoverIP

IPover

ATM

TCPATMAAL1

Connection-orientedoverover

IPATM

Fig.5-3.Examplesofdifferentcombinationsofserviceand

subnestructure.

11

IssueDatagramsubnetVCsubnet

CircuitsetupNotneededRequired

AddressingEachpacketcontainsEachpacketcontainsa

thefullsourceandshortVCnumber

destinationaddress

StateinformationSubnetdoesnotholdEachVCrequiressubnet

stateinformationtablespace

RoutingEachpacketisRoutechosenwhenVC

routedindependentlyissetup;allpackets

followthisroute

EffectofrouterfailuresNone,exceptforpacketsAllVCsthatpassed

lostduringthecrashthroughthefailed

routerareterminated

CongestioncontrolDifficultEasyifenoughbuffers

canbeallocatedin

advanceforeachVC

Fig.5-2.Comparisonofdatagramandvirtualcircuitsubnets.

12

小結(jié)(1)

■網(wǎng)絡(luò)層的地位

-位于數(shù)據(jù)鏈路層和傳輸層之間，使用數(shù)據(jù)鏈路層

提供的服務(wù)，為傳輸層提供服務(wù)；

-通信子網(wǎng)的最高層；

-處理端到端傳輸?shù)淖畹蛯印?/p>

■網(wǎng)絡(luò)層的作用

-屏蔽各種不同類(lèi)型網(wǎng)絡(luò)之間的差異，實(shí)現(xiàn)互連

-了解通信子網(wǎng)的拓?fù)浣Y(jié)構(gòu)，選擇路由，實(shí)現(xiàn)報(bào)文

的網(wǎng)絡(luò)傳輸

13

小結(jié)(2)

■網(wǎng)絡(luò)層的兩種實(shí)現(xiàn)方式：數(shù)據(jù)報(bào)和虛電路

-都屬于分組交換，采用存儲(chǔ)轉(zhuǎn)發(fā)機(jī)制。

-數(shù)據(jù)報(bào)(datagram)：每個(gè)分組被單獨(dú)路由，分組帶

有全網(wǎng)唯一的地址

-虛電路(virtualcircuit)：先在源端和目的端之間建

立一條虛電路，所有分組沿虛電路按次序存儲(chǔ)轉(zhuǎn)

發(fā)，最后拆除虛電路。在虛電路中，每個(gè)分組無(wú)

須進(jìn)行路徑選擇。

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

-面向連接的服務(wù)和無(wú)連接的服務(wù)。

14

7.2路由算法(1)

■路由算法是網(wǎng)絡(luò)層軟件的一部分

-通信子網(wǎng)采用數(shù)據(jù)報(bào)分組交換方式，每個(gè)包都要

做路由選擇；

-通信子網(wǎng)采用虛電路分組交換方式，只需在建立

連接時(shí)做一次路由選擇。

■路由算法應(yīng)具有的特性

-正確性(correctness)

-簡(jiǎn)單性(simplicity)

-健壯性(robustness)

-穩(wěn)定性(stability)

-公平性(fairness)

-最優(yōu)性(optimality)

15

7.2路由算法(2)

■路由算法分類(lèi)

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

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

7.2.1最優(yōu)化原則

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

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

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

16

7.2路由算法(3)

■匯集樹(shù)(sinktree)

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

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

匯集樹(shù)；

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

Fig.5-5.(a)Asubnet.(b)AsinktreeforrouterB.

17

7.2路由算法(4)

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

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

■基本思想

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

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

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

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

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

-地理距離

-傳輸延遲

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

18

7.2路由算法（5）

■Dijkstra算法

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

距離來(lái)標(biāo)注，標(biāo)注分為臨時(shí)性標(biāo)注和永久性標(biāo)注

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

大；

-將源結(jié)點(diǎn)標(biāo)注為0,且為永久性標(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)

19

7.2路由算法（6）

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

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

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

-重復(fù)第四、五步，直到目的結(jié)點(diǎn)成為工作結(jié)點(diǎn)。

-算法實(shí)現(xiàn)，程序與算法的區(qū)別是：從目的結(jié)點(diǎn)開(kāi)

始。

20

(a)(b)

B(2,A)C(9,B)：(2,A)Q(9,B)

/^\^(4舊

A.—C(F(oo,-)bD(oo,-)A<><F(6,E)/)D(8.1)

*G(5,E)Hg-)

G(6,A)Hg-)

(C)(d)

呼,A)g(9,B).2,A)Q(9,B)

//A\E(4.B)/^\

(4,人

A.><F(6,E)bD(oo.-)A<><F(6,E)bD(--)

G(5,E)H(9,G)G(5,E)/H(8,F)

Fig.5-6.Thefirstfivestepsusedincomputingtheshortest

pathfromAtoD.Thearrowsindicatetheworkingnode.

21

#defineMAK.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[0];p<&state[n];p++){/*initializestate*/

p->predecessor=-1;

p->length=INFINITY;

p->label=tentative;

)

state[t].length=0;stateft].label=permanent;

k=t;/*kistheinitialworkingnode*/

do{/*Isthereabetterpathfromk?*/

for(i=0;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=0;min=INFINITY;

for(i=0;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-+-+]=k;k=state[k].predecessor;}while(k>=0);

Fig.5-7.Dijkstra'salgorithmtocomputetheshortestpath

throughagraph.22

7.2路由算法(7)

7.2.3洪泛算法(Flooding)

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

■基本思想

-把收到的每一個(gè)包，向除了該包到來(lái)的線路外的

所有輸出線路發(fā)送。

■主要問(wèn)題

-洪泛要產(chǎn)生大量重復(fù)包。

■解決措施

-每個(gè)包頭包含站點(diǎn)計(jì)數(shù)器，每經(jīng)過(guò)一站計(jì)數(shù)器減1

,為。時(shí)則丟棄該包;

-記錄包經(jīng)過(guò)的路徑

23

7.2路由算法(8)

■選擇性洪泛算法(selectiveflooding)

-洪泛法的一種改進(jìn)。將進(jìn)來(lái)的每個(gè)包僅發(fā)送到與

正確方向接近的線路上。

■應(yīng)用情況

-對(duì)路由器和線路的資源過(guò)于浪費(fèi)，實(shí)際很少直接

采用；

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

-作為衡量標(biāo)準(zhǔn)評(píng)價(jià)其它路由算法。

24

7.2路由算法(9)

7.2.4基于流量的路由算法(Flow-BasedRouting)

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

■基本思想

-既考慮拓?fù)浣Y(jié)構(gòu)，又兼顧網(wǎng)絡(luò)負(fù)荷；

-前提：每對(duì)結(jié)點(diǎn)間平均數(shù)據(jù)流是相對(duì)穩(wěn)定和可預(yù)

測(cè)的；

-根據(jù)網(wǎng)絡(luò)帶寬和平均流量，可得出平均包延遲，

因此路由選擇問(wèn)題歸結(jié)為找產(chǎn)生網(wǎng)絡(luò)最小延遲的

路由選擇算法。

-提前離線(off-line)計(jì)算。

25

7.2路由算法(10)

■需要預(yù)知的信息

-網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)；

-通信量矩陣F*

-線路帶寬矩陣Cjj；

-路由算法(可能是臨時(shí)的)。

26

Destination

ABCDEF

94174

ABABCABFDAEAEF

98324

BABCBFDBFEBF

48332

CBACBCDCECEF

13334

DFBADFBDCDCEDF

72335

⑶EAEFBECECDEF

44245

FEAFBFECFDFE

(b)

Fig.5-8.(a)Asubnetwithlinecapacitiesshowninkbps,(b)

Thetrafficinpackets/secandtheroutingmatrix.

27

iLineXj(pkts/sec)Cj(kbps)pCj(pkts/sec)Tj(msec)Weight

1AB142025910.171

2BC122025770.146

3CD61012.51540.073

4AE112025710.134

5EF135062.5200.159

6FD81012.52220.098

7BF102025670.122

8EC82025590.098

Fig.5-9.AnalysisofthesubnetofFig.5-8usingamean

packetsizeof800bits.Thereversetraffic(BA,CB,etc.)isthe

sameastheforwardtraffic.

■1/|LI=800bits

■根據(jù)排隊(duì)論，平均延遲T=1/3C-九）

28

7.2路由算法(11)

7.2.5距離向量路由算法(DistanceVectorRouting)

?屬于動(dòng)態(tài)路由算法，也稱(chēng)Bellman-Ford路由算法和

Ford-Fulkerson算法，最初用于ARPANET,被RIP協(xié)

議采用。

■基本思想

-每個(gè)路由器維護(hù)一張表，表中給出了到每個(gè)目的

地的已知最佳距離和線路，并通過(guò)與相鄰路由器

交換距離信息來(lái)更新表；

-以子網(wǎng)中其它路由器為表的索引，表項(xiàng)包括兩部

分：到達(dá)目的結(jié)點(diǎn)的最佳輸出線路，和到達(dá)目的

結(jié)點(diǎn)所需時(shí)間或距離；

29

7.2路由算法(12)

-每隔一段時(shí)間，路由器向所有鄰居結(jié)點(diǎn)發(fā)送它到

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

結(jié)點(diǎn)發(fā)來(lái)的距離表；

-鄰居結(jié)點(diǎn)X發(fā)來(lái)的表中，X到路由器i的距離為Xj,

本路由器到X的距離為m,則路由器經(jīng)過(guò)X到i的距

離為Xj+m。根據(jù)不同鄰居發(fā)來(lái)的信息，計(jì)算Xj+

m,并取最小值，更新本路由器的路由表；

-注意：本路由器中的老路由表在計(jì)算中不被使用

30

Newestimated

delayfromJ

ToAIHKJLine

A02420218A

B1236312820A

C2518193628I

402782420H

D

E147302217I

F2320194030I

G183163118H

H172001912H

—210142210I

J9117100一

K24222206K

L29339915K

<______7

JAJIJHJKV

delaydelaydelaydelayNew

isisisisrouting

810126table

<______

VforJ

Vectorsreceivedfrom

J'sfourneighbors

(b)

Fig.5-10.(a)Asubnet,(b)InputfromA,/,H,K,andthenew

routingtableforJ.

31

7.2路由算法(13)

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

算法的缺陷：對(duì)好消息反應(yīng)迅速，對(duì)壞消息反應(yīng)遲

鈍；

ABcDEABCDE

■.......■.

ooooooooInitially1234Initially

1ooooooAfter1exchange3234After1exchange

12ooooAfter2exchanges3434After2exchanges

123ooAfter3exchanges5454After3exchanges

1234After4exchanges5656After4exchanges

7676After5exchanges

(a)7878After6exchanges

(b)

Fig.5-11.Thecount-to-infinityproblem.

32

7.2路由算法(14)

■水平分裂算法

-工作過(guò)程與距離向量算法相同，區(qū)別在于到x的距

離不向真正通向X的鄰居結(jié)點(diǎn)報(bào)告，使得壞消息傳

播的也快。

-雖然廣泛使用，但有時(shí)候會(huì)失敗。

D?33

7.2路由算法(15)

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

?距離向量路由算法的主要問(wèn)題

-選擇路由時(shí)，沒(méi)有考慮線路帶寬；

-路由收斂速度慢。

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

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

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

占.

八、、，

?兩個(gè)或多個(gè)路由器連在一個(gè)LAN時(shí)，引入人工結(jié)

占.

八、\，

34

(a)(b)

Fig.5-13.(a)NineroutersandaLAN.(b)Agraphmodelof(a).

35

7.2路由算法(16)

-測(cè)量到每個(gè)鄰居結(jié)點(diǎn)的延遲或開(kāi)銷(xiāo)；

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

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

-將所有學(xué)習(xí)到的內(nèi)容封裝成一個(gè)包；

?包以發(fā)送方的標(biāo)識(shí)符開(kāi)頭，后面是序號(hào)、年齡

和一個(gè)鄰居結(jié)點(diǎn)列表；

?列表中對(duì)應(yīng)每個(gè)鄰居結(jié)點(diǎn)，都有發(fā)送方到它們

的延遲或開(kāi)銷(xiāo)；

■鏈路狀態(tài)包定期創(chuàng)建或發(fā)生重大事件時(shí)創(chuàng)建。

36

(a)

Fig.5-15.(a)Asubnet.(b)Thelinkstatepacketsforthissubnet.

37

7.2路由算法(17)

-將這個(gè)包發(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)為過(guò)時(shí)而丟棄；

?改進(jìn)

＞序號(hào)循環(huán)使用會(huì)混淆，解決辦法：使用32

位序號(hào)；

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

A序號(hào)出錯(cuò);

38

7.2路由算法(18)

＞第二、三問(wèn)題的解決辦法：增加年齡(age

)域，每秒鐘年齡減1,為零則丟棄。

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

其它已到達(dá)的來(lái)自同一路由器的鏈路狀態(tài)

包比較序號(hào)，丟棄重復(fù)包，保留新包；

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

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

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

■實(shí)用協(xié)議

-OSPF

-IS-IS

39

B2C

43

D

E8F

SendflagsACKflags

<—卜—\t—A—■>

SourceSeq.AgeACFACFData

A2160011100

F2160110001

E2159010101

C2060101010

D2159100011

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

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

經(jīng)過(guò)EFB；

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

DFB；

40

7.2路由算法(19)

■鏈路狀態(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)之間交換

41

7.2路由算法(20)

-收斂(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)

42

7.2路由算法(21)

Osc川ationspossible:

■e.g.,linkcost=amountofcarriedtraffic

...recompute...recompute...recompute

initially

routing

43

7.2路由算法(22)

?DV

＞收斂時(shí)間不定

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

□count-to-infinityfn)題

44

7.2路由算法(23)

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

?LS

＞結(jié)點(diǎn)會(huì)廣播錯(cuò)誤的鏈路開(kāi)銷(xiāo)

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

?DV

＞結(jié)點(diǎn)會(huì)廣播錯(cuò)誤的路徑開(kāi)銷(xiāo)

A每個(gè)結(jié)點(diǎn)的路由表被別的結(jié)點(diǎn)使用，錯(cuò)誤

會(huì)傳播到全網(wǎng)

45

7.2路由算法(24)

7.2.7分層路由(HierarchicalRouting)

■網(wǎng)絡(luò)規(guī)模增長(zhǎng)帶來(lái)的問(wèn)題

-路由器中的路由表增大；

-路由器為選擇路由而占用的內(nèi)存、CPU時(shí)間和網(wǎng)

絡(luò)帶寬增大。

■分層路由

-分而治之的思想；

-根據(jù)需要，將路由器分成區(qū)域(regions)＞聚類(lèi)

(clusters)、區(qū)(zones)和組(groups)...

-Fig.5-17,路由表由17項(xiàng)減為7項(xiàng)。

■分層路由帶來(lái)的問(wèn)題

-路由表中的路由不一定是最優(yōu)路由。

46

Fulltablefor1AHierarchicaltablefor1A

Dest.LineHopsDest.LineHops

Region1Region21A——1A——

市、/'5A2K1B1B11B1B1

m)1C1C11C1C1

，

\13\2C’2D2A1B221B2

\一/

、、.2B1B331C2

2C1B341C3

2D1B451C4

3A1C3

3B1C2

4A1C3

4B1C4

Region3Region4Region5

4C1C4

5A1C4

5B1C5

5C1B5

5D1C6

5E1C5

(a)(b)(c)

Fig.5-17.Hierarchicalrouting.

47

7.2路由算法(25)

7.2.8移動(dòng)主機(jī)的路由

■需要解決的問(wèn)題

-為了能夠?qū)?shù)據(jù)包轉(zhuǎn)發(fā)給移動(dòng)主機(jī)，網(wǎng)絡(luò)必須首

先要找到移動(dòng)的主機(jī)。

■網(wǎng)絡(luò)結(jié)構(gòu)示意圖

Fig.5-18.AWANtowhichLANs,MANs,andwirelesscellsareattached.48

7.2路由算法(26)

■一些基本概念

-移動(dòng)用戶(hù)(mobileusers)：包括位置發(fā)生變化，

通過(guò)固定方式或移動(dòng)方式與網(wǎng)絡(luò)連接的兩類(lèi)用戶(hù)

-家鄉(xiāng)位置(homelocation)：所有用戶(hù)都有一個(gè)

永久的家鄉(xiāng)位置，用一個(gè)地址來(lái)標(biāo)識(shí)；

-外部代理(foreignagent)：每個(gè)區(qū)域(一個(gè)LAN

或一個(gè)wirelesscell)有一個(gè)或多個(gè)外部代理，它

們記錄正在訪問(wèn)該區(qū)域的移動(dòng)用戶(hù)；

-家鄉(xiāng)代理(homeagent)：每個(gè)區(qū)域有一個(gè)家鄉(xiāng)

代理，負(fù)責(zé)記錄家鄉(xiāng)在該區(qū)域，但是目前正在訪

問(wèn)其它區(qū)域的用戶(hù)。

49

7.2路由算法(27)

■移動(dòng)用戶(hù)進(jìn)入一個(gè)新區(qū)域時(shí)，必須首先向外部代理注

冊(cè)

-外部代理定期廣播聲明自己的存在和地址的包，新

到達(dá)的移動(dòng)主機(jī)接收該信息；若移動(dòng)用戶(hù)未能收到

該信息，則移動(dòng)主機(jī)廣播包，詢(xún)問(wèn)外部代理的地址

-移動(dòng)主機(jī)向外部代理注冊(cè)，告知其家鄉(xiāng)地址、目前

的數(shù)據(jù)鏈路層地址和一些安全信息；

-外部代理與移動(dòng)主機(jī)的家鄉(xiāng)代理聯(lián)系，告知移動(dòng)主

機(jī)的目前位置、自己的網(wǎng)絡(luò)地址和一些安全信息；

-家鄉(xiāng)代理檢查安全信息，通過(guò)，則給外部代理確認(rèn)

-外部代理收到確認(rèn)后，在登記表中加入一項(xiàng)，并通

知移動(dòng)主機(jī)注冊(cè)成功。

50

7.2路由算法(28)

■移動(dòng)用戶(hù)的路由轉(zhuǎn)發(fā)過(guò)程

-當(dāng)一個(gè)包發(fā)給移動(dòng)用戶(hù)時(shí)，首先被轉(zhuǎn)發(fā)到用戶(hù)的

家鄉(xiāng)局域網(wǎng)；

-該包到達(dá)用戶(hù)的家鄉(xiāng)局域網(wǎng)后，被家鄉(xiāng)代理接收

,家鄉(xiāng)代理查詢(xún)移動(dòng)用戶(hù)的新位置和與其對(duì)應(yīng)的

外部代理的地址；

-家鄉(xiāng)代理采用隧道技術(shù)，將收到的包作為凈荷封

裝到一個(gè)新包中，發(fā)給外部代理；

-家鄉(xiāng)代理告訴發(fā)送方，發(fā)給移動(dòng)用戶(hù)的后續(xù)包作

為凈荷封裝成包直接發(fā)給外部代理；

-外部代理收到包后，將凈荷封裝成數(shù)據(jù)鏈路幀發(fā)

給移動(dòng)用戶(hù)。

51

J

Fig.5-19.Packetroutingfbrmobileusers.

52

小結(jié)(1)

■最優(yōu)化原則

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

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

-最短路徑路由算法

-洪泛算法

-基于流量的路由算法

53

小結(jié)（2）

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

-距離向量路由算法

?將自己（路由結(jié)點(diǎn)）對(duì)全網(wǎng)拓?fù)浣Y(jié)構(gòu)的認(rèn)識(shí)告

訴給鄰居

?無(wú)窮計(jì)算問(wèn)題，水平分裂算法

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

?將自己（路由結(jié)點(diǎn)）對(duì)鄰居的認(rèn)識(shí)洪泛給全網(wǎng)

■分層路由

■移動(dòng)主機(jī)的路由

54

7.3擁塞控制算法(1)

■擁塞(congestion)

-網(wǎng)絡(luò)上有太多的包時(shí)，性能會(huì)下降，這種情況稱(chēng)

為擁塞。

■擁塞產(chǎn)生的原因

-多個(gè)輸入對(duì)應(yīng)一個(gè)輸出；

-慢速處理器；

-低帶寬線路。

■解決辦法

-針對(duì)某個(gè)因素的解決方案，只能對(duì)提高網(wǎng)絡(luò)性能

起到一點(diǎn)點(diǎn)好處，甚至可能僅僅是轉(zhuǎn)移了影響性

能的瓶頸；

-需要全面考慮各個(gè)因素。

55

7.3擁塞控制算法(2)

■擁塞控制與流量控制的差別

-擁塞控制(congestioncontrol)需要確保通信子

網(wǎng)能夠承載用戶(hù)提交的通信量，是一個(gè)全局性問(wèn)

題，涉及主機(jī)、路由器等很多因素；

-流量控制(flowcontrol)與點(diǎn)到點(diǎn)的通信量有關(guān)

,主要解決快速發(fā)送方與慢速接收方的問(wèn)題，是

局部問(wèn)題，一般都是基于反饋進(jìn)行控制的。

56

Perfect

Maximumcarrying

P

Bcapacityofsubnet

$Desirable

>

ap)

S

O/Congested

'

O

B

CL

Packetssent

Fig.5-22.Whentoomuchtrafficisoffered,congestionsetsin

andperformancedegradessharply.

57

7.3擁塞控制算法(3)

7.3.1擁塞控制的基本原理

■根據(jù)控制論，擁塞控制方法分為兩類(lèi)

-開(kāi)環(huán)控制

?通過(guò)好的設(shè)計(jì)來(lái)解決問(wèn)題，避免擁塞發(fā)生；

?擁塞控制時(shí)，不考慮網(wǎng)絡(luò)當(dāng)前狀態(tài)。

-閉環(huán)控制

?基于反饋機(jī)制；

?工作過(guò)程

＞監(jiān)控系統(tǒng)，發(fā)現(xiàn)何時(shí)何地發(fā)生擁塞；

＞把發(fā)生擁塞的消息傳給能采取動(dòng)作的站點(diǎn)

＞調(diào)整系統(tǒng)操作，解決問(wèn)題。

58

7.3擁塞控制算法(4)

■衡量網(wǎng)絡(luò)是否擁塞的參數(shù)

-缺乏緩沖區(qū)造成的丟包率；

-平均隊(duì)列長(zhǎng)度；

-超時(shí)重傳的包的數(shù)目；

-平均包延遲；

-包延遲變化(Jitter)o

■反饋方法

-向負(fù)載發(fā)生源發(fā)送一個(gè)告警包；

-包結(jié)構(gòu)中保留一個(gè)位或域用來(lái)表示發(fā)生擁塞，一

旦發(fā)生擁塞，路由器將所有的輸出包置位，向鄰

居告警；

-主機(jī)或路由器主動(dòng)地、周期性地發(fā)送探報(bào)(probe

),查詢(xún)是否發(fā)生擁塞。

59

7.3擁塞控制算法（5）

7.3.2擁塞控制算法

■擁塞預(yù)防策略

-開(kāi)環(huán)控制

-影響擁塞的網(wǎng)絡(luò)設(shè)計(jì)策略

LayerPolicies

Transport?Retransmissionpolicy

?Out-of-ordercachingpolicy