北京邮电大学《计算机网络》5

ComputerNetwork

计算机网络

北京邮电大学

计算机学院

王小茹

THENETWORKLAYER

第5章网络层

Parti

基本理论框架

北邮计算机学院：王小茹

第5章网络层

5.1网络层的设计要点

*5,2路由算法

*5.3拥塞控制

*5.4服务质量

*5.5网络互联

5.6网络层IP协议

北邮计算机学院：王小茹

5.1NETWORKLAYERDESIGNISSUE

.网络层的基本概念

■■网络层的目标:

・将分组从源端沿着网络路径送到目标端。

北邮计算机学院：王小茹

EndtoEndVSPointtoPoint

为什么要创建网络层?

，网络层与数据链路层的区别

■网络层是将源端发出的分组经各种途径送到目的端。

■而数据链路层仅将数据帧从传输介质的一端送到另一端。

•因此，网络层是处理端到端数据传输的最低层。

-网络层要解决的关键问题

■路由选择

■拥塞控制

■网络互连

■网络层指明端到端的总体路径方向，数据链路层

脚踏实地地一条一条链路的实现。北邮计算机学院：王小茹

Store-and-ForwardPacketSwitching

q5ii存储转发，分组交换

■硬件结构

■存储转发的方式

北邮计算机学院：王小茹

ServicesProvidedtoTransportLayer

、5.1.2网络层提供的服务

吗传输层提供服务

»无连接的服务

每个分组携带源地址和目的地址，被直接发送与接收。

A面向连接的服务

连接建立、数据传送和连接释放；

每个分组只携带虚电路号沿着建立好的虚电路进行传输。

北邮计算机学院：王小茹

ConnectionlessService

5.1.3无连接的服务

Transport

Network

Datalink

北邮计算机学院：王小茹

网络随时接受主机发送的分组（即数据报）

网络为每个分组独立地选择路由O

也向嗑发送分组

乩向也发送分组

路径可能变化

6

QH5

分组交换网

网络尽最大努力地将分组交付给目的主机,

但网络对源主机没有任何承诺。

网络不保证所传送的分组不丢失

也不保证按源主机发送分组的先后顺序

以及在时限内必须将分组交付给目的主机

©

©一

HQ分组交换网

当网络发生拥塞时

网络中的结点可根据情况将一些分组丢弃

HQ

数据报提供的服务是不可靠的，

它不能保证服务质量。

实际上“尽最大努力交付”的服务

就是没有质量保证的服务。

主机乩先向主机飞发出一个特定格式的控制信息分组,

要求进行通信，同时寻找一条合适路由。若主机&同意

通信就发回响应，然后双方就建立了虚电路。

出向嗜发送的

所有分组都沿此

要和H通信

5虚电路传送。

虚电路

______

同理，主机也和主机嗑通信之前，也要建立虚电路。

H3g

__

在虚电路建立后，网络向用户提供的服务就好像在

两个主机之间建立了一对穿过网络的数字管道。

所有发送的分组都按顺序进入管道，然后按照

先进先出的原则沿着此管道传送到目的站主机。

HQ分组交换网

到达目的站的分组顺序就与发送时的顺序一致，

因此网络提供虚电路服务对通信的

服务质量QoS(QualityofService)有较好的保证。

HQ分组交换网

数据报服务和虚电路服务

优缺点的归纳

对比的方面虚电路服务数据报服

思路可靠通信应当可靠通信后

由网络来保证由用户主机来保证

连接的建立必须有彳

目的站地址仅在连接建立阶段每个分组都笨

使用，每个分组使目的站的全地址

用短的虚电路号

北邮计算机学院：王小茹

数据报服务和虚电路服务

优缺点的归纳

对比的方面虚电路服务数据报服

分组的转发属于同一条虚电路每个分组独立选

的分组均按照同一路由进行转发

路由进行转发

当结点出所有通过出故障的故障结点可能2

故障时结点的虚电路分组，一4

均不能工作可能会发生变

北邮计算机学院：王小茹

数据报服务和虚电路服务

优缺点的归纳

对比的方面虚电路服务数据报服

服务质量能够实现困难

拥塞控制能够实现困难

北邮计算机学院：王小茹

数据报服务和虚电路服务

优缺点的归纳

对比的方面虚电路服务数据报

服务

分组的顺序总是按发送顺序到达目的站时不

一定

到达目的站按发送顺

序

端到端的可以由分组交换网由用户主机

负责

差错处理和负责也可以由用户北邮计算机学院：王小茹

___LnAT±7

ROUTINGALGORITHMS

5.2路由算法

■路由算法的概念

■最优化的原则

■距离矢量路由

■链路状态路由

■分级路由

北邮计算机学院：王小茹

基本概念一路由器的两个动作

■转发(forwarding)

■每个分组到达的时候，在路由表中查找该分

组所对应的输出路径。

■路由选择(routing)

■使用路由算法。

■负责填充和更新路由表。

北邮计算机学院：王小茹

RoutingAlgorithm

.路由算至

•就是产生路由表的算法；

■是网络层软件的一部分。

■子网采用数据报方式，每个包都要做路由选择；

■子网采用虚电路方式，只需在建立连接时做一次路由选择。

北邮计算机学院：王小茹

4理想的路由算法

r正确性(correctness):算法必须正确；

，简单性(simplicity):算法开销小，效率高；

r健壮性(robustness):算法能适应网络负荷和拓朴的变化；

，稳定性(stability):算法必须收敛，不能振荡发散；

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

，公平性(fairness):算法对所有用户必须是平等的；

，最优性(optim疝ty):算法应提供最佳路径选择；

最佳：链路长度、传输时延、数据速率、链路容量、链路差错率、链路丢失率等。

北邮计算机学院：王小茹

Non-adaptiveandAdaptive

路由算法的分类

非自适应算法（静态路由算法）

■采用离线方式求出路由表

■简单、开销小，但不能适应网络状态变化

自适应算法（动态路由算法）

■能适应网络状态变化

■复杂、开销大使用？

北邮计算机学院：王小茹

想想看:

最优化原则，对于计算机网络中的分组转发

有什么作用?

如果I,J,K的最佳路由是「产「2,则当I把分组交

给J时，J一定会沿着r2把分组转发出去。

北邮计算机学院：王小茹

・汇集树(SinkTree)

A从所有的源结点到一个给定的目的结点的最优路由

的集合形成了一个以目的结点为根的树，称为

汇集树(sinktree)

A路由算法的目的是找出并使用汇集树。

子网路由器B的汇集树

ShortestPathRouting

.5.2.2最短路径路由算法

A属于静态路由算法

r基本思想

■构建子网的拓扑图，图中的每个结点代表一个路

由器，每条弧代表一条通信线路。为了选择两个

路由器间的路由，算法在图中找出最短路径。

A测量路径长度的方法

■结点数量

■地理距离

■传输延迟

■距离、信道带宽等参数的加权函数

北邮计算机学院：王小茹

Dijkstra算法

①每个结点用从源结点沿已知最佳路径到本结点的距离

家标注，标注分为临时性标注和永久性标注；

②初始时，所有结点都为临时性标注，标注为无穷大；

③将源结点标注为o,且为永久性标注，并令其为工作结

点；

④检查与工作结点相邻的临时性结点，若该结点到工作

结点的距离与工作结点的标注之和小于该结点的标

注，则用新计算得到的和重新标注该结点；

⑤在整个图中查找具有最小值的临时性标注结点，将其

变为永久性结点，并成为下一轮检查的工作结点；

重复第④、⑤步，直到所有结点成为工作结点；

计算机学院：王小茹

D（8._）

智能科学与网络工程系：王小茹

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(«-)

⑻

智能科学与网络工程系：王小茹

结点A的路由表

结点A的汇集树目的站下一站

A

BB

CB

DB

EB

FB

GB

HB

同理，以结点E为源结点，采用Dijkstia算法,

求出结点E的汇集树和路由表：结点E的路由表

目的站下一站

结点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);

透明网桥的“武功秘笈”

北邮计算机学院：王小茹

扩散算法(Flooding)

■属于静态路由算法

■基本思想

■事先不需要任何网络信息；

■路由器把收到的每一个分组，向除了该分组

到来的线路外的所有输出线路发送。

■将来会有多个分组的副本到达目的地端，最

先到达的，可能是走了“最优”的路径。

北邮计算机学院：王小茹

扩散算法：结点1与6之间的通信，Stepl

扩散算法：Step2

A

<®

扩散算法：Step3

想想看?

如何消除：过时的/重复的分组?

了算法的优点是什么？

■不需要事前知道任何网络的拓扑信息；

■所有的网络路径都被尝试过；

■第一个到达的分组走的路径可能是最优的。

-算法的主要问题是什么？

■产生大量重复分组。

你该出手了!

北邮计算机学院：王小茹

I的

决方

■F端收到分组时，在每个分组的头部增加一个计数器。

此后，每经过一跳该计数器减1,为。时丢弃。

■计数器的初值=最佳路径的跳数/子网的直径；

■每个路由器记录收到已经扩散过的分组，从而避免再

次发送这些分组。

■源端在每个分组中放置一个序号；

■每个收端路由器记录｛源端地址，序号｝;

■每个路由器将得到的同一源端的分组的最大序列号

分组记录下来，小于该序号的丢弃。

北邮计算机学院：王小茹

选择性扩散算法⑴

▲

▲

▲

选择性扩散算法（2）

选择性扩散算法⑶

1

选择性扩散算法

.(SelectiveFlooding)

建择性扩散算法是扩散法的一种改进。

■能够消除多余的分组。

■扩散算法的应用情况

■对路由器和线路的资源过于浪费，实际的商用

网络很少直接采用；

■具有极好的健壮性，可用于军事应用；

■作为衡量标准评价和初级拓扑消息获得方式应

用于其它路由算法。

北邮计算机学院：王小茹

动态路由算法

距离矢量路由算法

链路状态路由算法

北邮计算机学院：王小茹

DistanceVectorRouting

15.2.4距离矢量路由算法

»属于动态路由算法

最初应用于ARPANET,后来应用于因特网的RIP协议（路由信息协议）。

》基本思想

■每个结点通过测取与相邻结点的距离，再依据与其相邻结点

交换的距离信息，间接地求出路由表；

■各结点周期性地测取相邻结点的距离；

向相邻结点发送它到每个目的结点的距离表，

同时，它也接收每个邻居结点发来的距离表；

■结点中的老路由表在计算中不被使用。

北邮计算机学院：王小茹

目的站延迟下一站

10,

222

353

414

563

683

DIS1

结点1测取相来自相邻结点时延向量结点1的路由表-更新后

D151

求"12和%：

e

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

"13+42=4+3=7

"14+42=2+2=4

源站点1：利用中间站点2到达目的站点2。

求"12和%：

,

/f712+rf22=1+0=1

[13+42=4+3=7

〃i4+42=2+2=4

源站点1：利用中间站点3到达目的站点2。

结点1测取相来自相邻结点时延向量结点1的路由表-更新后

DIS1

・〃12+〃22=1+0=1

"13+42=4+3=7

"14+42=2+2=4

源站点1：利用中间站点4到达目的站点2。

,

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

・二.12=1，$12=2

[13+42=4+3=7

〃i4+42=2+2=4

结点1测取相来自相邻结点时延向量结点1的路由表-更新后

求：源站点1,目的站点3,分别利用2,3,4O

结点1测取施1来自相邻结点时延向量结点1的路由表-更新后

邻结点的时延站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

结点1测取木I

邻结点的时延

严2=1

及

九二4

回4=2

求“16和%6：

"13+”36

"14+〃46

・.・46=5,

巨离矢

试着扮演一次路由器吧!

北邮计算机学院：王小茹

初始时,

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

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

1:各个路由器各自重新测量到邻居的距离；

2：然后把自己上一状态的路由表去掉转发项，

项变成“距离表”发送出去。

3:收取邻居发来的“距离表”，重新计算路由表。

第一次交换开始:

路由器B

BO

C1

DC1C

D0-

更新后

C说

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

此

因现在也可以到

离BD,

距

过

经

是2C95

O

路由器C收到相邻路由器B和D的距离表

路由器D收到相邻路由器C的距离表

B1B

B0-CO・

C1CD1Dc1c

D0-

B1B

CO-

D1D

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

B0-B1B

C1CC0-

D2CD1D

,对链路故障的反应

好事传千里，坏事不出门！！

一个靠邻居“谣言”活着的路由协议

北邮计算机学院：王小茹

一个好消息，A链路修好了!

■思考：

■A需要多久才能获得全网的路由信息？

■B需要多久才能知道可达A的路由信息?

■C需要多久才能知道可达A的路由信息?

■D需要多久才能知道可达A的路由信息?

B0-B2C

初始时: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

总结:

■对链路“好消息”的反应很快!

■网络再次收敛的速度很快！

■正所谓：好事快马加鞭传千里!

北邮计算机学院：王小茹

一个坏消息,A路由器坏了!

北邮计算机学院：王小茹

A

■思考：

■B需要多久才能知道不可达A的路由信息?

■C需要多久才能知道不可达A的路由信息?

・D需要多久才能知道不可达A的路由信息?

A0

B1BB:A1

2B

D3BC:A2

ABCD

第一次交换时：B、C、D仍把自己的路由表改成距离表，发送。

第一次交换后：C和D的路由表不变。

一开始，B得知了坏消息：“我无法到A!!!

C却通过“距离表”说：别着急，我能到达A,嘿嘿!

B收到C的更新报文后，误认为可经过C到达A,于是更

新自己的路由表，说：“我到A的距离是3,下一跳经过

C”。然后再等待下次的交换时，将此更新信息发送给C。

这就是好消息传播得快，而坏消息传播得慢。网络出

故障的传播时间往往需要较长的时间（例如数分钟）。这

是RIP的一个主要缺点。

1234

DCNDCNDCNDCNDCNDCNDcN

A1AA00-A3CA3CA5CA5CA7c

BC1CC1cC1CC1CC1CC1CC1c

D2CD2cD2cD2cD2cD2cD2c

DCNDCNDCNDCNDCNDCND£N

AAAADA公D

A2BA2BA2BA6B

I业J

C十委攵

B1BB1BB1B股隼个断更新卜云，TBB

D1DD1DD1D划兀为。D1D

DCNDCNDCNDcNDcNDcNDcN

A3CA3CA3CA3CA5CA5C

D士C

B2CB2CB2CB2CB2CB2CC

C1cC1cC1cC1cC1cC1cc

*time

如何解决上述问题?

先想想：导致上述问题

的本质原因是什么？

北邮计算机学院：王小茹

,如何解决上述问题?

手段L头疼治头，脚痛治脚;

手段2：治标又要治本！

北邮计算机学院：王小茹

AD计数到无穷的问题

1

1

C3规定一个最大距离（跳数）：16,

当距离=16时，认为网络是不可达的！！

亨CNDCNDCNDCNDCNDCNDcN

A1AA00-A3CA3CA5CA5CA7c

BC1CC1cC1CC1CC1CC1CC1c

D2CD2cD2cD2cD2cD2cD2c

DCNDCNDCNDCNDCNDCNDN

AAAADA公D

A2BA2BA2BA6B

C十麦攵

B1BB1BB1B缺隼个断更新I、太，TBB

D1DD1DD1D划兀为。DNF

DCNDCNDCNDcNDcNDcN_?J_EJN

A3CA3CA3CA3CA5CA5C

DC

B2CB2CB2CB2CB2CB2CC

C1cC1cC1cC1cC1cC1cc

*time

、

“我有一条到A的路记住，我是原创!

由”

y

说：“我到A的距离是1”

B:A12B

况AB

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

路由消息！诉我的

我要做个标记

C说：“我到A的距离是2,是经过B。”

将来我不能向B告知网1的任何消息。

这是“水平分割”技术。

这是：水平分割+毒性逆转!

L=U

00D

A|A-t=>B仁A8B

说：坏消息：“我无法到达A了！！！

C说：没关系，我能到达！！！

C在收到B的更新报文之前，还发送原来的报文,

虽然这时C并不知道A出了故障,

但报文是加了毒性逆转的形式。

水平分割vs水平分割+毒性逆转

adnewsisbetterthannonews!

北邮计算机学院：王小茹

1作业：分析网络协议的有效性

福通的距离矢量协议;

2.使用带水平分割的距离矢量协议；

3,使用水平分割+毒性逆转方法是否比仅使用水平分

割的方法好？如果能，说明原因；不能，给出什么样

的拓扑结果是的水平分割+毒性逆转的方法更好？

北邮计算机学院：王小茹

5.2.5链路状态路由算法

.(LinkStateRouting)

-距离向量路由算法的主要问题.

・选择路由时，没有考虑线路带宽；邃

■路由收敛速度慢。起牙

■链路状态路由算法

・OSPF

・IS-IS

北邮计算机学院：王小茹

算法的基本操作

问候

确定可达性

问候

数据库描述

数据库描述

达到数据库的同步

数据库描述

数据库描述

链路状态请求

新情况下的同步链路状态更新

链路状态确认

北邮计算机学院：王小茹

1,发现邻居结点，并学习它们的网络地址

HELLO

确定可达性

HELLO

■路由器启动后，通过发送HELLO包发现邻居结点；

■线路另一端的路由器应该送回一个应答来说明它是谁。

■这些名字必须是全局唯一的。

北邮计算机学院：王小茹

2,测量到各邻居节点的延迟或者开销

ECHO

测量邻居开销

ECHO

■要求城一个路由器知道它到各个邻居节点之间的延

迟，或者至少有一个合理的估计值。

■一种直接的方法是：发送一个要对方立即响应的

ECHO包，来回时间除以2即为延迟。

北邮计算机学院：王小茹

3.创建链路状态分组

创建链路状态分组

BCDEF

A

Seq.Seq.Seq.Seq.Seq.

Seq.

AgeAgeAgeAgeAge

Age

A4B2C3A5B6

B4

C2D3F7C1D7

E5

F6E1F8E8

北邮计算机学院：王小茹

4.使用扩散法发布链路状态分组

链路状态分组

扩散发布

链路状态分组

链路状态分组

链路状态分组

达到数据库的同步

链路状态分组

链路状态分组

北邮计算机学院：王小茹

4.使用扩散法发布链路状态分组

■为控制洪泛，每个分组含一个序号，每次发送新分组

时加1。

■路由器记录信息对（源路由器，序号），当一个链路状

态分组到达时：

-若是新的，则分发；

-若是重复的，则丢弃；

■若序号比路由器记录的最大序号小，则认为过时而丢弃；

北邮计算机学院：王小茹

使用的是可靠的扩散法

JACK报文

■开动脑筋：存在的问题(1)

具口果序列号回转了，则可能会产生混淆。

■解决办法：

■使用32位序号；

■即使每秒钟产生一个链路状态分组，也需要137

年才可能发生回转。

北邮计算机学院：王小茹

B开动脑筋：存在的问题(2)

・如果:

■路由器崩溃后，序号重置；

■或者序号出错；

■解决方法

■增加年龄(age)域，每秒钟年龄减1,为零则丢弃。

■链路状态包到达后，延迟一段时间，并与其它已到达

的来自同一路由器的链路状态包比较序号，丢弃重复

包，保留新包；

■链路状态包需要应答;

北邮计算机学院：王小茹

B2C

43

A\AZ

E8F

SendflagsACKflags

SourceSeq.AgeAcFAcFData

A2160011100

F2160110001

E2159010101

C2060101010

D2159100011

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

■从E发来的链路状态包有两个，一个经过EAB,另

一个经过EFB;

■从D发链路状态包有两个，一个经过DCB,另一个

经过DFB;北邮计算机学院：王小茹

5.计算到每个其它路由器的最短路径

■每个路由器都获得了自己的路由拓扑图

■据Dijkstra算法计算最短路径；

■生成自己的路由表

THEEND

北邮计算机学院：王小茹

链路状态算法(LS)

和距离矢量算法(DV)的比较

■路由信息的复杂性

■LS

-路由信息向全网发送

■N节点，E个连接的情况下，每个节点发送O(nE)

的报文

■DV

-仅在邻居节点之间交换

北邮计算机学院：王小茹

链路状态算法(LS)和距离向量

算法(DV)的比较

■收敛(Convergence)速度

-LS

■使用最短路径优先算法，算法复杂度为O(n**2)

■n个结点(不包括源结点)，需要n*(n+1)/2次比较

■使用更有效的实现方法，算法复杂度可以达到O(nlogn)

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

■DV

■收敛时间不定

■可能会出现路由循环

■count-to-infinityfi5]|§

北邮计算机学院：王小茹

链路状态算法(LS)和距离向量

算法(DV)的比较

!健壮性：如果路由器不能正常工作会发生什么?

.LS

结点会广播错误的链路开销

每个结点只计算自己的路由表

・DV

结点会广播错误的路径开销

每个结点的路由表被别的结点使用，错误会传播到全网

北邮计算机学院：王小茹

作业2:

一个通信子网,使佣链路状态路由选择算法,已知各节点产生的链路

状态数据包如下2

林小:V0~++标示：VI"林小：V2P林小：V3「初'小：V4d

序号:“序号：52序号:加序号：9卡序号:4

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

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

3〃V*3〃⑵⑵3P

2〃恬3〃恬