計(jì)算機(jī)網(wǎng)絡(luò)chapter5(3版+4版)網(wǎng)絡(luò)層

Chapter5

THENETWORKLAYER

（網(wǎng)絡(luò)層）

?NetworkLayerDesignIssues

?RoutingAlgorithm（路由算法）

?CongestionControlAlgorithms（擁塞控制算法）

?QualityofService

?Internetworking（網(wǎng)絡(luò)互連）

?TheNetworkLayerintheInternet

1

14:45:55

NetworkLayerDesignIssues

?網(wǎng)絡(luò)層涉及

-分組從源端-〉目的端

-處理端到端數(shù)據(jù)傳輸?shù)淖畹蛯?/p>

?數(shù)據(jù)鏈路層涉及

-數(shù)據(jù)幀從導(dǎo)線的一端到另一端

2

14:45:55

Networklayerdesignissues:Introduction

?Datalinklayerv.s.networklayer

-Datalinklayer:tomoveframesfromoneendofawiretothe

other.

-Networklayer:tomovepacketsfromthesourcealltheway

tothedestination.Itdealswithend-to-endtransmissions.

?Networklayer

-Mustknowaboutthetopologyofthecommunicationsubnet

andchooseappropriatepathsthroughit.

-Mustchooseroutestoavoidoverloadingsomeofthe

communicationlinesandrouterswhileleavingothersidle.

-Todealwithinternetworkdifferentnetworks.

3

14:45:55

5.1.1Stored-and-forwardpacketswitching

?Ahostwithapackettosendtransmitsittothenearest

router.Thepacketisreceived,verified,andstored.Then

itisforwardedtothenextrouter.Thisstepcanbe

repeatedmanytimes.Finallythepacketreachesthe

destinationhost.

4

14:45:55

5.1.2Servicesprovidedtothetransport

layer

?Thenetworklayerserviceshavebeendesignedwith

thefollowinggoalsinmind.

-Theservicesshouldbeindependentoftheroutertechnology

-Thetransportlayershouldbeshieldedfromthenumber,type,

andtopologyoftherouterspresent.

-Thenetworkaddressesmadeavailabletothetransportlayer

shoulduseauniformnumberingplan,evencrossLANsand

WANs.

5

14:45:55

Servicesprovidedtothetransportlayer

?Two-typeofservices:

-Connection-lessservices:("Datagram)

?30yearsofexperiencewiththecomputernetwork,unreliable

internet,hostsdoingerrorcontrolandflowcontrol

一Connection-orientedservices.(->VirtualCircuit)

?100yearsofexperiencewiththeworldwidetelephonesystem,

qualityofservice

->Connection-less+connection-orientedservices.

6

14:45:55

5.1.3ImplementationofConnectionless

Service

14:45:55Routingwithinadiagramsubnet.

(

①

-

q

圖l

u

①

S

>S

」B

o)

-

s」

蔓9

B」A

sA。B

B擊-

s--pU

①40

t*4」

-o」o4

udOId8

osM0s

:Mu-一

一uIZd

B①6HBy

t①j」UU」e

4個(gè)4

u：:Z：:

二IZmLZN

uHzHd

工HH

個(gè)

oq個(gè)

寸

個(gè)

個(gè)

個(gè)

個(gè)

。山

個(gè)sLs

怎

個(gè)

je個(gè)

Z」>」

oH①」ua

AM山p」M

BaMB

Uca個(gè)

-B個(gè)B

o」」-

OU-OO-t

(J。J

4Not旦Wo

s個(gè)sCD

d4a個(gè)d

Boq巴BO

a」s

個(gè)dEO4n4

U-MnMu

ds①:oo

個(gè)

個(gè)^

①sl」」B

Tdu①①①U

tHps」

一TT4

u￡bUjjq

9c:Is：.jH.H:：

l一INZ

opII

-dH)HHHg

dim

Ed?????

Iib

5.1.4ImplementationofConnection-Oriented

Service

A'stableC'stableE'stable

H11C1A1E1C1F1

H31C2A2E2C2F2

InOut

Routingwithinavirtual-circuitsubnet

9

14:45:55

5.1.5ComparisonofVirtual-CircuitandDatagramSubnets

IssueDatagramsubnetVirtual-circuitsubnet

CircuitsetupNotneededRequired

EachpacketcontainsEachpacketcontainsa

thefullsourceandshortVCnumber

destinationaddress

StateinformationRoutersdonotholdEachVCrequiresrouter

stateinformationaboutconnectionstablespaceperconnection

EachpacketisRoutechosenwhenVC

routedindependentlyissetup;allpackets

followit

EffectofrouterfailuresNone,exceptforpacketsAllVCsthatpassed

lostduringthecrashthroughthefailed

routerareterminated

QualityofserviceDifficultEasyifenoughresources

canbeallocatedin

advanceforeachVC

一DifficultEasyifenoughresources

canbeallocatedin

advanceforeachVC

14:45:55

ComparisonofVirtual-CircuitandDatagram

Subnets

?Servertrade-offsexistbetweenvirtualcircuitsand

datagrams

-Routermemoryspacev.s.bandwidth

-Setuptimev.s.addressparsingtime.

-Largeroutingtablespacefordatagramsubnets

-EasyQoSforVCsubnets

-VulnerabilityproblemforVCsubnets

11

14:45:55

5.2ROUTINGALGORITHMS

?功能：將分組從源端機(jī)器經(jīng)選定路由送到目的端機(jī)

器

?路由選擇算法

-希望具有的特征：

?正確性、簡單性、健壯性、穩(wěn)定性、公平性和最優(yōu)性

?公平性與最優(yōu)性之間的矛盾-

ABC

A'B'C

14:45:55Fig.5-4.Conflictbetweenfairnessandoptimality.

5.2ROUTINGALGORITHMS

?路由選擇算法

-數(shù)據(jù)報(bào)和虛電路采用不同的選擇方法

-算法分類：

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

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

13

14:45:55

5.2.1Theoptimalityprinciple

?最優(yōu)化原則

-如果路由器j在從路由器i到K的最佳路由上，那

么J到K的最佳線路就會(huì)在同一路由上

?匯集樹-

-從所有源端到目的端的最佳路由集合，形成了以

目的地為根的樹

Fig.5-5.

14:45:55(a)Asubnet,(b)AsinktreeforrouterB.

5.2.2最短路由選擇

(Shortestpath)

-測量路徑長度的方法(依據(jù))：

?站點(diǎn)數(shù)量、距離、信道帶寬、平均通信量、通信

開銷、隊(duì)列平均長度、測量到的時(shí)延。。。

-(Dijkstra)算法實(shí)例：計(jì)算從A到D的最短路徑-

?從源到終節(jié)點(diǎn)

一算法程序一

?從終結(jié)點(diǎn)到源節(jié)點(diǎn)

15

14:45:55

AD(oo,-)

HG(6,A)H(co,-)

(b)

B(2.A)C(9.B)

D(~1)

(d)

C(9,B)B(2.A)C(9,B)

AD(oo,-)AD(oo_)

G(5.E)H(9.G)

(e)

Fig.5-6.Thefirstfivestepsusedincomputingtheshortest

pathfromAtoD.Thearrowsindicatetheworkingnode.

14:45:55

52路由選擇算法

#defineMAX^NODES1024/*maximumnumberofnodes*/

#defineINFINITY1000000000/*anumberlargerthaneverymaximumpath*/

intn,dist(MAX_NODESHMAX_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->labd=tentative:

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

/*kistheinitialworkingnode*/

/?Isthereabetterpathfromk??/

/*thisgraphhasnnodes*/

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

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

statefi].predecessor=k;

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

|

14:45:55)

52路由選擇算法

/?Findthetentativelylabelednodewiththesmallestlabel.*/

k=0;min=INFINITY;

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

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

min=state[i].length;

k=i;

}

state[k].label=permanent;

}while(k?=s);

/?Copythepathintotheoutputarray.*/

i=0;k=s;

}do{pathfi**)=k;k=statefk].predecessor;}while(k>=0);

Fig.5-7.Dijkstra'salgorithmtocomputetheshortestpath

throughagraph.

18

14:45:55

5.2.3擴(kuò)散法(Flooding)

-原理：將收到的每個(gè)分組，從除了分組到來的線

路外的所有線路上發(fā)出

-問題：產(chǎn)生大量的分組

-抑制措施：

■在分組頭中包含“站點(diǎn)計(jì)數(shù)器”，當(dāng)其減到零

時(shí)即被丟棄

?記錄下分組擴(kuò)散的路徑

-改進(jìn)：選擇性擴(kuò)散法

?僅將分組擴(kuò)散到與正確方向接近的線路上

-應(yīng)用：實(shí)際應(yīng)用較少

19

14:45:55

5.2.4基于流量的路由選擇（*）

-原理：根據(jù)已知載荷量和平均流量，計(jì)算出分組

平均延遲，最終找出產(chǎn)生網(wǎng)絡(luò)最小延遲的路由

-須預(yù)先知道：網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)、通信量矩陣、各線

路容量的矩陣

20

14:45:55

5.2.5Distancevectorrouting

原理：

?讓每個(gè)路由器維護(hù)一張向量表，表中給出每個(gè)目的地已知

的最佳距離和線路

?通過與相鄰路由器交換信息來更新表的信息

應(yīng)用：ARPANET>因特網(wǎng)、DECNet、NovellIPX、Cisco

Routers等

Newestimated

算法描述：RouterdelayfromJ

e

Kin

ToA

B02420218A

C1236312820A

D2518193628I

E402782420H

F147302217I

G2320194030I

H183163118H

I172001912H

J210142210I

K9117100一

L24222206K

29339915K

JAJIJHJK

delaydelaydelaydelayNew

isisisisrouting

810126table

forJ

Vectorsreceivedfrom

Fig.5-10.(a)Asubnet,(b)InputfromA,/,HyK,andthenewJtsfourneighbors

routingtablefbrJ.(b)

5.2.5Distancevectorrouting

?無窮計(jì)算問題

-算法的缺陷：算法收斂較慢。（對(duì)好消息反應(yīng)迅

速，對(duì)壞消息反應(yīng)遲鈍）-

ABCDEABCDE

i------?-------?-------?-..--?---fl--?.

ooooooooInitially1234Initially

1ooooooAfter1exchange3234After1exchange

128ooAfter2exchanges3434After2exchanges

123ooAfter3exchanges5454After3exchanges

1234After4exchanges5656After4exchanges

7676After5exchanges

(a)7878After6exchanges

OOOO8cx)

(b)

14:45:55Fig.5-11.Thecount-to-infmityproblem.

5.2.5Distancevectorrouting

?水平分裂算法-解決“壞消息”反應(yīng)慢的問

題

特點(diǎn)：至Ux的距離常

告A

受敗的情況:

A-〉D=2,B->D=2

ifCD斷了，

C告知A、B不可到達(dá)D

但，A知道B可達(dá)D,

長度二2,所以A-〉B-〉D

長度二3；

同樣B->A->D長度二3

14:45:55

5.2.6鏈路狀態(tài)路由選擇

(Linkstaterouting)

-距離矢量路由選擇存在的問題

?沒有考慮線路的帶寬

?記錄信息耗時(shí)過多，算法收斂速度慢

-工作原理(對(duì)每個(gè)路由器)：

?發(fā)現(xiàn)鄰居節(jié)點(diǎn)，及其網(wǎng)絡(luò)地址

?測量線路開銷或延遲

■構(gòu)造鏈路狀態(tài)分組

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

?計(jì)算新最短路由

24

14:45:55

5.2.6Linkstaterouting

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

?通過發(fā)送Hello分組來實(shí)現(xiàn)

⑶(b)

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

25

14:45:55

5.2.6Linkstaterouting

-測量線路開銷或延遲

?發(fā)送ECHO分組，將響應(yīng)時(shí)間/2

?考慮載荷，某些爭議-

Fig.5-14.AsubnetinwhichtheEastandWestpartsarecon-

nectedbytwolines.

26

14:45:55

5.2.6Linkstaterouting

-構(gòu)造鏈路狀態(tài)分組-

?何時(shí)構(gòu)造？定期創(chuàng)建或出現(xiàn)重大事件時(shí)再創(chuàng)建

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

27

14:45:55

5.2.6Linkstaterouting

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

?基本思想：利用擴(kuò)散法發(fā)布鏈路狀態(tài)分組；每個(gè)

分組包含一個(gè)順序號(hào)；每次發(fā)送新分組時(shí)順序號(hào)

力口

?問題

-崛序號(hào)的嬉環(huán)使用一

-路由器崩靄，造成順序號(hào)丟失

-順序號(hào)傳送錯(cuò)誤

?解決辦法

-每不分組的順序號(hào)后加年齡字段（age）

?算法的改進(jìn)-

-路由器將分組先存儲(chǔ)，比較后再發(fā)送

SendflagsACKflags

14:45:55Fig.5-16.ThepacketbufferforrouterBinFig.5-15.

5.2.6Linkstaterouting

-計(jì)算新最短路由

-應(yīng)用

?OSPF

?中間系統(tǒng)至中間系統(tǒng)IS-IS

?兩者的區(qū)別：IS-IS可同時(shí)攜帶多個(gè)網(wǎng)絡(luò)層協(xié)議

的信息

29

14:45:55

5.2.7分級(jí)路由選擇（*）

-網(wǎng)絡(luò)增大、路由表成比例增大

-將路由器按區(qū)域分組-

14:45:55

5.2.8移動(dòng)主機(jī)路由選擇（*）

靜態(tài)用戶-從不移動(dòng)的用戶

非靜態(tài)用戶（遷移用戶、漫游用戶）-〉移動(dòng)用戶

網(wǎng)絡(luò)世界模型-

外地代理-管理所有來當(dāng)?shù)氐膭?dòng)態(tài)用戶

主代理-管理本屬本區(qū)域，但當(dāng)時(shí)正在外地的用戶

MAN

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

14:45:55

5.2.8移動(dòng)主機(jī)路由選擇（*）

-典型的登錄過程：

i.外地代理定期廣播分組，宣布自己的存在及地址

；同時(shí)，移動(dòng)主機(jī)可以廣播，問“這里有沒有外

地代理？”

2.移動(dòng)主標(biāo)登錄到外地代理

3.外地代理與移動(dòng)主機(jī)的主代理聯(lián)系

4.主代理檢查安全性信息

5.外地代理得到主代理的確認(rèn)后，建立一個(gè)表項(xiàng)，

并通知移動(dòng)主機(jī)已經(jīng)登錄了

-退出登錄

32

14:45:55

5.2.8移動(dòng)主機(jī)路由選擇（*）

14:45:55

2

?

9廠播路由選擇（*）

3種.算五

算法

1

算法分別發(fā)送分組到每個(gè)目的端

2

算法擴(kuò)散法

3

算法多目的地路由選擇

4

利用發(fā)起廣播的路由器的信息樹或利用生成樹

(a)(b)(c)

Fig.5-20.Reversepathforwarding.(a)Asubnet,(b)Aspan-

ninetree,(c)Thetreebuiltbyreversepathfonvardinu.

34

14:45:55

5.2.10多點(diǎn)播送路由選擇（*）

?多點(diǎn)播送（Multicast）

?實(shí)現(xiàn)方法

-良好的小組管理機(jī)制

?創(chuàng)建和取消小組

?允許進(jìn)程進(jìn)入、離開小組

-發(fā)送時(shí)，第一個(gè)路由器檢查生成樹，修剪小組成

員不能到達(dá)的線路-

-修剪生成樹的方法

?使用鏈路狀態(tài)時(shí)使用，從樹葉開始，向樹根發(fā)展

?對(duì)距離矢量路由，采用逆向路由轉(zhuǎn)發(fā)（缺點(diǎn)：存儲(chǔ)

空間占用大）

?核心基本樹：每個(gè)組只計(jì)算一棵生成樹。樹根靠近

組的中間部位（優(yōu)點(diǎn)：降低存儲(chǔ)開銷）

35

14:45:55

5.2.10多點(diǎn)播送路由選擇(*)

Fig.5-21.(a)Asubnet,(b)Aspanningtreefortheleftmost

router,(c)Amulticasttreefbrgroup1.(d)Amulticasttreefor

group2.

36

14:45:55

5.3擁塞控制算法（*）

■擁塞-當(dāng)通信子網(wǎng)中有太多的分組時(shí)，其性能降

彳氐-

-造成擁塞的原因

?擁塞控制與流量控制__________________________

Perfect

Maximumcarrying,

p

iacapacityofsubnet

>①Desirable

-

pa

s

o,Congested

oM

dB

Packetssent

Fig.5-22.Whentoomuchtrafficisoffered,congestionsetsin

14:45:55andperfbmiancedegradessharply.

5.3.1擁塞控制的基本原理

-控制論

-開環(huán)與閉環(huán)

-解決擁塞的辦法：增加資源或降低載荷

-虛電路一網(wǎng)絡(luò)層中解決

-數(shù)據(jù)報(bào)一傳輸層中解決

38

14:45:55

5.3.2擁塞預(yù)防策略

?影響擁塞的策略-

LayerPolicies

Transport?Retransmissionpolicy

?Out-of-o