计算机通信包交换

高华广学出版社

第5章计算机通信一包交换

­包交换技术一数据报和虚电路

•差错检测

•差错控制

•流量控制

•路由选择

•拥塞控制

高华广学出浙・社

:厚驾媒婴f式纵则”昌堤直翼崎骷姆，圣3

包交换技术(packetswitching)

数据报方式:为每个包单独选择路径

X

高华广学出浙・社

:厚驾媒婴f式纵则”昌堤直翼崎骷姆，圣3

包交换技术(packetswitching)

虚电路方式:在源和目标间先建立路径

高华广学出版社_

2厂fFJ/zteayf1'•N/»A

包交换技术(packetswitching)

—数据报和虚电路

•每个包独立传递，结点为包逐个选择路径，这

种包称为数据报(datagram)o

•虚电路(virtual-circuit),即逻辑连接(logical

connection)是在主机之间事先建立的一条传输

路径，如X・A・B・E・Y,以后X和Y之间的包就在

此路径传输。它类似线路交换网中的一条电路。

但这条路径不是专用的，它是和其它包、其它

连接共享的。包在每个结点仍要作短暂存储，

和其它包一起放在输出队列转发。

清华广学出版社-

;二ZJ7/上W夕A"REFF二

包交换技术(packetswitching)

—数据报和虚电路方式比较

•数据报方式更原始，更灵活，可以绕过

拥塞区和故障点，所以具有健壮性.・・。

但数据报会错序；

■虚电路方式保证包的传递顺序，容易实

现差错控制；

•两个主机交换大量数据时，虚电路方式

更有效，若只交换少量包，数据报方式

更快。

高华方学出版社

差错检测

•奇偶校验(paritycheck)

•校验和(checksum)

•循环冗余校验码CRC(CyclicRedundancy

Check)

•差错检测的局限性

高华十学出版社

奇偶校验

•奇偶校验：在所发送的每个字符后面添加一个

校验位，称为奇偶位(paritybit)。

•偶校验：字符中有奇数个1则添加1，有偶数个1

则添加0。如1110010添加0成为11100100o

字符连同校验位中1的总数为偶数。

•奇校验：字符中有奇数个1则添加0,有偶数个1

则添加1。如1110010添加1成为11100101o

字符连同校验位中1的总数为奇数。

■奇偶校验能检测什么差错？

能检测奇数位差错，不能检测偶数位差错。

唐华十学出版画

校验和

•有的协议层在包头设置一个校验和字段。

•若校验和是16位的字段，发送方在发送前将待

校验的字符串分成若干长度为16位的段，每个

段看成二进制数，进行相加等运算，结果填入

校验和字段。

•校验和可以检测一位错误，一位以上的错误不

一定能检测出来。

•校验和是较简单的差错检测，是计算代价和检

测能力之间的一种权衡。

循环冗余校验码CRC

一附加帧校验序列FCS

CRC常用在数据链路层，附加的校验序列称为

帧校验序列FCS(FrameCheckSequence),它是

基于CRC计算的，这里只介绍CRC,记为F

左位〃位

M

高华十学出版社

循环冗余校验码CRC

一帧校验CRC码F的计算

•M表示被发送的位串，设为左位。

尸是什1位的标准位串，r<k,

M、尸都看作二进制数。

•当用尸除时得商。和余数A,余数

A就作为帧校验CRC码R它至少比尸

少一位，可看作〃位。网中传输的是T,

T看作二进制数，则

T=2rM+F=(QP+R)+R

高华大学出版社

循环冗余校验码CRC—校验的原理

•这里的算术运算以2为模，即加不进位、

减不借位。对任何二进制数X,x+x=o,

所以7="，即T能被尸除尽。

•如果收到的丁不能被尸除尽，则丁在传

输中一定发生差错。

•如果收到的T能被尸除尽，是不是T在

传输中一定没有差错呢？

高华广学出浙・社

循环冗余校验码CRC—例子

例：给定玲=1101011101,P=101101,计算厂

1111001000<Q

101101/110101110100000

101101

110001

101101

111001

101101

101000

101101

101100

101101

1000余数R

循环冗余校验码CRC—问题

•25M=110101110100000,/=火=01000,

T=25M+F=110101110101000c

•如果收到的T=110101010101000,则它

不能被尸除尽，传输中有错，错了一位。

•如果收到的7=111111111111000,它仍

能被尸除尽，但错了四位。

•CRC校验无法检测能被尸除尽的错误码。

循环冗余校验码CRC

—多项式运算的观点

■每个二进制数都对应一个多项式，多项

式系数对应二进制位。上例中数X,P,

。，R(M=1101011101,尸=101101,

2=1111001000,火=01000)等对应：

M(x)=x9+x8+x6+x4+x3+x2+1

P(x)=X5+X3+X2+1,...

x5M(x)=Q(x)P(x)+A(x)

高华力学出胸社

循环冗余校验码CRC

一生成多项式P(x)

•T(x)=xrM(x)+R(x)

=Q(x)P(x)+i?(x)+R(x)

=g(x)P(x)

•位次)多项式尸(x)称为生成多项式，余式

R(x)对应P生成的CRC码。

■若传输中无差错，T(x)能被P(x)整除，

但能整除不一定传输无差错。有差错即

T(x)变成T(x)+E(x)。

高华十学出版社

循环冗余校验码CRC

一生成多项式P(x)的选择

•若P(x)至少包含两项，.则可检测所有一位错误。

一位错误部分£(%)=£,尸(x)不苛能除尽£。

•若P(x)是不可约多项式，且帧长〃不大于尸(X)

的周期，则可检测所有两位错误。不可约多项

式尸(x)的周期e是使尸(x)能除尽d+1的最小整数

(例如/+34+1的周期是32768)。

两位错误部分£(x)=£+0,2〃，六孔。不妨设

i>j,则£+/=/(1门+1)。由于

P(x)除不尽工门+1。另外尸(%)只要多于一项就

除不尽力。所以尸(x).・・除不尽£(x)。

高华十学出版社

循环冗余校验码CRC

一生成多项式P(x)的选择(续)

•若P(x)包含因子(x+1),则可检测所有奇数位错。

奇数位错误部分£(x)的项数为奇数，它不可能

被尸(x)除尽，因为(x+1)不可能为奇数项多项式

的因子。［可找尸(x)=(x+1)G(x),G(x)为周期大

于帧长的不可约多项式］

•若尸(x)是包含常数项的r次多项式，则可检测

长度Vr的突发性错误。这种错误部分£(、)=

一+%1+...+£=£(炉色+…+1),尸(%)包含常数项,

所以尸(x)不能除尽工1,又尸(x)为r次，大于括

号中的多项式次数，也不能除尽它。

高华方学出版社

循环冗余校验码CRC

—常用的16位CRC标准生成多项式

CRC-16：X16+%15+%2+1

CRC-CCITT：X16+X12+X5+1

清华十孚出版社

/•Jt7r'f、•^Z9^'/

循环冗余校验码CRC

—CRC的计算电路例

CRC计算过程可以用异或门电路和移位寄存器来

实现，移位寄存器共”立，异或门最多尸位，它们

正好对应/次生成多项式尸(x)最高次项以外的项。

输入位

<------

P=101101的CRC计算电路

薄监十字出版社=

差错检测的局限性

•差错检测都是在包中附加校验信息和数据一起

传输。任何差错检测方法都只能检测到某些错

误，都不是完美的。

•在网络结点的链路层几乎都有CRC校验，检测

逐段链路传输错误。谁做校验？

•在主机的网络层和传输层，如IPv4、TCP、

UDP都有校验和，主要检测数据在主机或路由

器发生的错误。需不需要？够不够？…

高华广学出版社

差错检测的局限性

•Paxsonl997经统计分析发现：通过链路层CRC

校验的包约0.02%有校验和错误。

•Stone等1998-1999收集了22亿个包，其中48万

个包有IP,UDP或TCP校验和错误。有主机

软、硬件错误，路由器内存错误等。（不要太相

信硬件!）

•校验和是必要的，它和CRC互相补充。..・

•网络结点对包做差错检测，发现错误后丢弃包。

如何恢复，就是差错控制。

jyjft.___rjf/r」t<J*J.

差错控制

确认消息：•停-等(确认):每发

•正确认ACK(positive一个包就等待确认。

acknowledgement)和超•后退N：连发数包等

时重发。确认。顺序接收累计

•负确认NACK或REJ(链确认，第左个包错，从

路层)和重发。第左个包开始全重发。

■确认消息可以夹带在发•选择重发:连发数包

送数据包的包头，称为等确认，只重发出错

捎带确认(piggybacking)。的包。接收方需暂存

已到达错序包…。

膏华大学出版社

停-等

发送方接收方发送方接收方发送方接收方

包

超

时ACK1

重

发

io

ACK1

丢弃

重复

包0

包丢失ACK丢失

序号是否需要?

后退N（g『back-N）接收方

发送方

包0U

包1卜ACK2

包2卜

包3V-ACK4

包4寸

包5超tACK4

代巨绝包5,6,7

包6时t

重发第4

ACK5

重发黄？ACK7

重发自Q

重发磊

高均大学出演

后退N（go-backN（续）接收方

发送方

包0

包1ACK2

包2

包3[ACK4

包4\暇矗5,6

包5

包6

重发包4jACK5

重发,24ACK7

重发射

包7

包0

港华，二学出版粒

选择重发

接收方

发送方

包0

包1ACK2

包2

包3ACK4

包4NACK4

包5暂存包5,6

包6ACK7

重发黑

包

7ACK1

包0

包1

包2

高华十字出版M

选择重发一问题

2殳

接收方

包0

包1

包2

包3

包4

包5

包

发

r一10

包

二6ACK6

包7ACK6

012345670123

发送窗口接收窗口

清华,二字出砂包

选择重发一对窗口的限制

方

2送

接收方

包o

包-1

包2

包3

ACK4

重发包0

01234567

发送窗口接收窗口

序号3位(0—7)

信'm，二字五㈤夕社.-

2V厂/•"AT『'6e?F/Cr

流量控制(flowcontrol)

•控制发送方流量，使接收方有缓冲可用。

・“停■等”流控最简单，但网络带宽利用率低。

ARPANET的NCP采用“停-等”。

•“滑动窗口流控(slidingwindowflowcontrol)”

技术。通信双方准备好各自的接收缓冲，称为

接收窗口，通告给对方，作为对方的发送窗口。

发送窗口是发送方在收到确认前可发送的最大

数据量。

•2〜5层都可有流控,。...

高华广学出浙・社

:厚驾媒婴f式纵则”昌堤直翼崎骷姆，圣3

流量控缶U(Howcontrol)(续)

一滑动窗口流控

窗口滑动

123456789101112

窗口滑动

已确认

123456789101112

已确乎—窗口滑动

01|2|34|5l6l7loll2I3I4I5I6I7

路由选择

­路由器（或交换机）的主要功能就是为主机

存储、转发包。为包确定一条从源通过

若干路由器（或交换机）到达目标的最优路

径，将包从源主机传送到目标主机。

•路由选择的基本概念

•基本路由算法

路由选择的基本概念

—由谁选择？

路由器(或交换机)选择。它们只为包选择

到达目标的最优路径的下一站，称之为

路由选择(routing)。它们都有一张路由表,

包含所有可能到达的目标和到达目标的

最优路径的下一站。

路由选择的基本概念

—静态路由

•路由表可以是静态的：路由表在设置后一般不

再改变。静态路由信息由管理员手工配置。当

网络变化时，可由人工更新配置。

■静态路由的缺点是它不会随网络结构变化而变

化。

•静态路由的优点是路由器之间无需交换路由信

息，可以不占用网络带宽。

•静态路由可以在简单的网络环境，或速率较低

的网段使用。在拨号线路上也常使用。

演毕7,二学出版社

路由选择的基本概念

一动态路由

•大型网络的主干结点需要采用动态路由:

网络情况变化时，路由表要随时更新。

动态路由信息由路由器与邻机自动交换、

自动更新。但动态路由有路由摆动问题

（routeflapping）。

•动态路由的实现需要两个功能：

交换路由信息（通过路由协议）；

计算和更新路由表（通过路由算法）。

清华二字

7td1

/7,Jr[p卜卜;/、/T押*§*-、F«J

路由选择的基本概念

一什么时候选择？

•若包交换采用数据报方式，则每个包到

达路由器（或交换机）时，为之选择路由。

•若包交换采用虚电路方式，则在虚电路

建立时选定路径，在虚电路撤消前，不

再为包作路由选择。

■若采用静态路由，从某源到某目标的所

有包都按配置路由转发，数据报方式和

虚电路方式没有差别。

路由选择的基本概念

—什么是所谓“最优路径”？

路由表包含最优路径信息，最优的度量:

•带宽：链路的数据容量；

•时延：包从源送达目标所需时间；

•可靠性：链路的误码率；

•负载：路由器资源占用情况；

•跳(hop)数：路径经过的路由器数目；

•费用。

高华广学出浙・社

:厚驾媒婴f式纵则”昌堤直翼崎骷姆，圣3

路由选择的基本概念

—“距离”最短的路径

各种度量可抽象为“距离”，它可表示时延、

跳数等。这样，网络可用有标号图表示：

3

24

2291

1

135

高华广学出浙・社

:厚驾媒婴f式纵则”昌堤直翼崎骷姆，圣3

基本路由算法

—由网络图计算（结点1）路由表

目标距离下一立占

基本路由算法

•距离向量路由算法DV(DistanceVector

routingalgorithm)

告诉邻居我的世界。每处有一个路牌。

•链路状态路由算法LS(LinkStaterouting

algorithm)

告诉世界我的邻居。每处有一张地图。

■两种算法的比较

距离向量路由算法一简介

算法目的：求网络图结点，的距离向量l）i和后

继结点向量Si。A表示从，到图中其它各点的

最短距离，E表示从，到达其它结点的最短路

径上的下一站。

是一种迭代算法。先给出各结点的Qi，£初值,

以后每个结点向邻结点通报自己的距离向量及

后继结点向量值（告诉邻居我的世界），任一结点

，再根据邻结点信息更新自己的。i，4。

高华十学出版社

距离向量路由算法一例

结点1，2,3,4,5的初始路由信

息分别是：

DI=(021，8,8)，SI=(-23…)

D2=(2,023,8),S2=(1<93A)

D3=(120,M),S3=(12-4)

D4=S39O,1),S4=(23,-,5)

D5=(oo?oo?oo?l50)5S5=(???4r)

清华7二字出z

*'.••,(f/,«•iLJ*.*«-**'IJ«/'•"/।rn.Li,J.t£.4T^rgn:c'A；

*_/jjj、9jjj_//Jj，•)'i•■.f「J*_/_/

距离向量路由算法一例(续)

结点2收到邻结点1,3,4的路由信息后，

将自己的路由信息。2,S2更新如下：

minMZhk+Oki)=。21，左=1,3,4

.*.。21'=。21，S21'=S21，

同理。2/=。为，S2j'=S2j,/=2,3,4

miru(Z)2k+Qk5)=。24+。45=3+1,

。2'=(2,0,2,3,3+1),S2，=(l,-,3,4,4)

高华广字出版社

距离向量路由算法一例（续）

结点1,2,3,4,5的路由信息稳定值为:

1=(0,2,1,5,6),H=(-,2,3,2,2)

2=(2,0,2,3,4),$2=(1,-,3,4,4)

32,0,5,6),$3=(1,2,-,2,2)

43,5,0,1),S4=(2,2,2,5)

54,6,1,0),S5=(4,4,4,4,-)

距离向量路由算法

初始值：Da=0,Sii=-，若，与，相邻，Dij为i与

）的距离，Sij=j,若不相邻,Dij=8,两待定。

算法（结点，收到相邻结点左的Qk和Sk后，把

A和S更新为。。£）：

对于j从1到n

｛选相邻结点V，满足［（Av+Qvj尸minkCAk+。©）］

则｛=DYN+Z）vj9S『=Siv）

清蚱7二字td或衽，...J标防犷品而;，一

■!r2JI•「厂，§少J-\•fJfk'PJrrlyr》'Jic*r

距离向量路由算法一问题

计数到无限(count-to-infinity)问题：

•上例,若结点4到5的线路故障,结点4更新

路由信息:。4=(535,0产),S4=(2,22-,)o

•0=(35,。25,-35,。45)，,=615,$25)邑5,^45)°

故障后，0=(6468),5=(2,42)。

•按算法更新。,S：0=(6,867),3=(232,2)。

•再更新：£>=(7,8711),5=(331,2)。

•再更新：。=(89811),S=(3,3J,2),…。

清华7,二学出版社二总工

*7*Fjy।'，『、f、ur尹，t?F尸（Fr

链路状态路由算法一简介

•由McQuillan等提出，称为最短路径优先SPF

（ShortestPathFirst）算法，于1979年用于

ARPANETo

•每个结点周期地向所有结点扩散本结点链路状

态信息（告诉世界我的邻居）。每个结点维持一

个网络拓扑信息数据库，也称链路状态库，有

全部结点的链路状态信息，即网络拓扑图。每

个结点可以利用Dijkstra最短路径算法求出以

本结点为根的最短路径树，得到路由表。

清华广学出版社

/171>j*DyhJ；）、,FF黄，ftf9^it^~

链路状态路由算法一例

上例中，用C表示结点链路

状态信息中的距离向量:

。1=(0,2,1,00,00)

。2=(2,0,2,3,8)

。3=(1,2,0,9,8)

04=3,3,9,0,1)

(00,00,00,

C5=1,0)

高华十学出版社

链路状态路由算法一例(续)

构造以结点1为根的最短路径树(，用。1表示

从结点1到其它各结点的最短距离向量。

•第一步：树只有根结点L3的初值取G，

2)i=(v0>,2,1,*co)o不在树上的结点集合

记为L£={2,3,4,5}

•第二步：将L中与1最近的结点3加入树，更新

3和乙2)i=(v0>,2,<1>,10,8),£={2,4,5}。

•第三步：将L中与1最近的结点2加入树，更新

3和£：1)1=(<0>5<2>,<1>,5,00),£={4,5}。

链路状态路由算法一例(续)

・第四步：将上中与1最近的结点4加入树，更新

。1和乙1)1=(<0>,<2>,<1>,<5>,6),L={5}O

•第五步：将［中与1最近的结点5加入树，更新

3和乙A=(vO>,<2>,<1>,<5>,<6>)?这

就是以结点1为根的最短路径树%。

­类似地，可构建以，为根的最短路径树北

•有了最短路径树就可以得到路由表。

高华尢学出版社

链路状态路由算法一例（续）

高华广学出版社

链路状态路由算法

常量：可=除源结点S以外的网络所有结点集合。

，表示下列值：Cii=O；若z•与，相邻，则Cij

为边长；若，与，不相邻，则Gj=R。

变量：&<=从源结点s到结点左的最短路径的距离,

5$]<=从源结点s到结点左的最短路径的下一站。

计算：从源结点到其它结点的最短路径的距离向

量。和路径的下一站向量S。

(1)初始化：L=M；Qsk=Csk；若。sk。00，则Ssk=左,

否则Ssk为空；

清华广学出版社

/171>j*DyhJ；）、,FF黄，ftf9^it^~

链路状态路由算法（续）

（2）循环（当集合£非空）

{找上中的某结点/对于£中所有结点》

°su=miiiwQsw；若Qsu=°0

{S到上中的结点无路径存在,报告错误退出；

从£中删除〃;

对于每个v£片£n{〃的邻结点},

{右Qsu+°UVVDsv

{Qsv=Qsu+CuV；Ssv=Ssu；}}

链路状态路由协议

每个结点要：

•周期地学习其相邻结点和相邻结点的网络地址;

•度量到相邻结点的距离，即与它相连的所有链

路的当前状态；

•构造链路状态包LSP,描述与它相连的所有链

路当前状态；

•将LSP发给所有结点；

•在收齐了全部LSP后，计算到其它结点的最短

路径。

清华十字出版社

jfJ、二厂,•二，卜｝

两种算法的比较

距离向量路由算法：链路状态路由算法：

•有“计数到无限”问­路由器有相同的网络

题。拓扑，路由计算的一

­路由器的路由信息从致性可保证。

相邻的路由器传播出

去，这个过程有延迟,•只发送本结点的链路

会出现路由不一致。状态，交换信息量少

•交换整个路由表，交

换信息量大。

■简单，易于实现。

清华广学出版社

jIjft.jf/r」J*J.

拥塞控制

•例：交通拥塞。在一定的时间间隔，当对资源

的需求超过了可用资源时，拥塞就发生。

•设计问题：道路（链路）容量不匹配加重拥塞。

■管理问题：资源分配的不合理，也会造成拥塞。

•网络拥塞现象

•拥塞控制基本策略

-开环控制

-闭环控制

-丢弃控制

高华力学出胸社

网络拥塞现象

•网络拥塞主要发生在路由器或包交换机。

•当包到达的速率接近或超过包处理和转发的速

率，就在路由器或交换机的缓冲区堆积而排起

队来。

■拥塞现象是包的传输时延变大。若无缓冲可用

则包被丢弃，若引起超时重传，拥塞加剧，导

致网络吞吐量突然下降，称为“拥塞崩溃

(congestioncollapse)”。

高华广学出浙・社

:厚驾媒婴f式纵则”昌堤直翼崎骷姆，圣3

网络拥塞现象

一网络拥塞对吞吐量的影响

网络吞吐量是数据通过网络的传送速率

吞吐量

拥塞对吞吐量的影响

一网络拥塞对时延的影响

网络无拥塞时，包只有传播时延和交换时延，

拥塞的网络还有队列时延，队列愈长时延愈大。

负载

拥塞对时延的影响

拥塞控制基本策略一开环控制

•开环控制(open-loopcontrol)基于资源预约

和连接准入控制,用于虚电路式包交换网。

•开环即事先协商通信流参数，协商后不

管网络是拥塞还是带宽富裕，参数不能

动态改变。在连接建立时申明数据速率

峰值、数据速率平均值、最大吞吐容量

等，请求被允许则连接建立，若资源不

够则拒绝连接请求。

:厚驾媒婴f式纵则”昌堤直翼崎骷姆，圣3

拥塞控制基本策略一开环控制的漏桶(leaky

bucket)算法

□

漏桶算法

:厚驾媒婴f式纵则”昌堤直翼崎骷姆，圣3

拥塞控制基本策略一开环控制的令牌桶

(tokenbucket)算法

令牌桶算法

拥塞控制基本策略一闭环控制

•闭环控制(closed-loopcontrol)是一种动态

控制系统，它包括反馈机制和控制机制。

•反馈机制允许网络把拥塞情况通知数据

源。路由器(或交换机)是监控拥塞程度的

最好场所。

•显式反馈和隐式反馈.・・

•控制机制允许数据源调整给网络的负载。

•窗口控制和速率控制

拥塞控制基本策略一丢弃控制

•当路由器的资源（如缓冲