《【教学课件】第5章计算机通信-包交换.ppt》由会员分享，可在线阅读，更多相关《【教学课件】第5章计算机通信-包交换.ppt（70页珍藏版）》请在三一办公上搜索。
1、第5章 计算机通信包交换,包交换技术数据报和虚电路差错检测差错控制流量控制路由选择拥塞控制,包交换技术(packet switching)数据报方式:为每个包单独选择路径,B,X,A,C,D,G,E,F,Y,1,2,3,包交换技术(packet switching)虚电路方式:在源和目标间先建立路径,B,X,A,C,D,G,E,F,Y,包交换技术(packet switching)数据报和虚电路,每个包独立传递，结点为包逐个选择路径，这种包称为数据报(datagram)。虚电路(virtual-circuit)，即逻辑连接(logical connection)是在主机之间事先建立的一条传输路
2、径，如X-A-B-E-Y，以后X和Y之间的包就在此路径传输。它类似线路交换网中的一条电路。但这条路径不是专用的，它是和其它包、其它连接共享的。包在每个结点仍要作短暂存储，和其它包一起放在输出队列转发。,包交换技术(packet switching)数据报和虚电路方式比较,数据报方式更原始，更灵活，可以绕过拥塞区和故障点，所以具有健壮性.。但数据报会错序；虚电路方式保证包的传递顺序，容易实现差错控制；两个主机交换大量数据时，虚电路方式更有效，若只交换少量包，数据报方式更快。,差错检测,奇偶校验(parity check)校验和(checksum)循环冗余校验码CRC(Cyclic Redunda
3、ncy Check)差错检测的局限性,奇偶校验,奇偶校验：在所发送的每个字符后面添加一个校验位，称为奇偶位(parity bit)。偶校验：字符中有奇数个1则添加1,有偶数个1 则添加0。如 1110 010 添加 0 成为 1110 0100。字符连同校验位中1 的总数为偶数。奇校验：字符中有奇数个1则添加0,有偶数个1 则添加1。如 1110 010 添加 1 成为 1110 0101。字符连同校验位中1 的总数为奇数。奇偶校验能检测什么差错？能检测奇数位差错，不能检测偶数位差错。,校验和,有的协议层在包头设置一个校验和字段。若校验和是16位的字段，发送方在发送前将待校验的字符串分成若干长
4、度为16位的段，每个段看成二进制数，进行相加等运算，结果填入校验和字段。校验和可以检测一位错误，一位以上的错误不一定能检测出来。校验和是较简单的差错检测，是计算代价和检测能力之间的一种权衡。,循环冗余校验码CRC附加帧校验序列FCS,CRC 常用在数据链路层，附加的校验序列称为帧校验序列FCS(Frame Check Sequence)，它是基于CRC计算的，这里只介绍CRC，记为 F,M,F,T,k 位,r 位,循环冗余校验码CRC帧校验CRC码 F 的计算,M 表示被发送的位串，设为 k 位。P 是 r+1 位的标准位串，rk，M、P 都看作二进制数。当 2r M 用P 除时得商 Q 和余
5、数R，余数R 就作为帧校验CRC码F，它至少比 P 少一位，可看作 r 位。网中传输的是T，T 看作二进制数，则T=2rM+F=(QP+R)+R,循环冗余校验码CRC校验的原理,这里的算术运算以 2 为模，即加不进位、减不借位。对任何二进制数 X，XX0，所以 T QP，即 T 能被 P 除尽。如果收到的 T 不能被 P 除尽，则 T 在传输中一定发生差错。如果收到的 T 能被 P 除尽，是不是 T 在传输中一定没有差错呢？,循环冗余校验码CRC例子,101101,1111001000,101101,110001,101101,111001,101101,101000,101101,10110
6、0,101101,1000,Q,余数R,例：给定M 1101011101，P 101101，计算F,循环冗余校验码CRC问题,25 M=11010 11101 00000，F=R=01000，T=25 M F=11010 11101 01000。如果收到的T 11010 10101 01000，则它不能被P 除尽，传输中有错，错了一位。如果收到的T 11111 11111 11000，它仍能被 P 除尽，但错了四位。CRC校验无法检测能被 P 除尽的错误码。,循环冗余校验码CRC 多项式运算的观点,每个二进制数都对应一个多项式，多项式系数对应二进制位。上例中数 M，P，Q，R(M=11010
7、11101，P=101101，Q=11110 01000，R=01000)等对应：M(x)=x9+x8+x6+x4+x3+x2+1P(x)=x5+x3+x2+1，.x5 M(x)=Q(x)P(x)+R(x),循环冗余校验码CRC生成多项式 P(x),T(x)=xrM(x)+R(x)=Q(x)P(x)+R(x)+R(x)=Q(x)P(x)(r 次)多项式 P(x)称为生成多项式，余式 R(x)对应 P 生成的CRC码。若传输中无差错，T(x)能被 P(x)整除，但能整除不一定传输无差错。有差错即T(x)变成 T(x)E(x)。,循环冗余校验码CRC生成多项式 P(x)的选择,若P(x)至少包含两
8、项，则可检测所有一位错误。一位错误部分 E(x)xi，P(x)不可能除尽 xi。若 P(x)是不可约多项式，且帧长 n 不大于 P(x)的周期，则可检测所有两位错误。不可约多项式P(x)的周期e是使P(x)能除尽 xe+1的最小整数(例如 x15+x14+1 的周期是32768)。两位错误部分 E(x)xi+xj，ij，则 xi+xj=xj(xi-j+1)。由于 i-j n e，P(x)除不尽 xi-j+1。另外P(x)只要多于一项就除不尽 xj。所以 P(x).除不尽 E(x)。,循环冗余校验码CRC生成多项式 P(x)的选择(续),若P(x)包含因子(x+1)，则可检测所有奇数位错。奇数位
9、错误部分E(x)的项数为奇数，它不可能被P(x)除尽，因为(x+1)不可能为奇数项多项式的因子。可找P(x)=(x+1)G(x)，G(x)为周期大于帧长的不可约多项式若 P(x)是包含常数项的 r 次多项式，则可检测长度 r 的突发性错误。这种错误部分 E(x)=xr+xr-1+xi=xi(xr-i+1)，P(x)包含常数项，所以 P(x)不能除尽 xi，又P(x)为 r 次，大于括号中的多项式次数，也不能除尽它。,循环冗余校验码CRC常用的16位CRC标准生成多项式,CRC-16：x16+x15+x2+1CRC-CCITT：x16+x12+x5+1,循环冗余校验码CRCCRC的计算电路例,C
10、4,C3,+,C2,+,C1,C0,+,输入位,P=101101 的 CRC 计算电路,CRC计算过程可以用异或门电路和移位寄存器来实现，移位寄存器共r位，异或门最多r位，它们正好对应r次生成多项式P(x)最高次项以外的项。,差错检测的局限性,差错检测都是在包中附加校验信息和数据一起传输。任何差错检测方法都只能检测到某些错误，都不是完美的。在网络结点的链路层几乎都有CRC校验，检测逐段链路传输错误。谁做校验?在主机的网络层和传输层，如 IPv4、TCP、UDP都有校验和，主要检测数据在主机或路由器发生的错误。需不需要？够不够？.,差错检测的局限性,Paxson1997经统计分析发现：通过链路层
11、CRC校验的包约 0.02%有校验和错误。Stone等1998-1999收集了22亿个包，其中 48万个包有IP，UDP 或 TCP 校验和错误。有主机软、硬件错误，路由器内存错误等。(不要太相信硬件!)校验和是必要的，它和CRC互相补充。.网络结点对包做差错检测，发现错误后丢弃包。如何恢复，就是差错控制。,差错控制,确认消息：正确认 ACK(positive acknowledgement)和超时重发。负确认 NACK或REJ(链路层)和重发。确认消息可以夹带在发送数据包的包头，称为捎带确认(piggybacking)。,停-等(确认)：每发一个包就等待确认。后退N：连发数包等确认。顺序接收
12、累计确认,第 k 个包错,从第k 个包开始全重发。选择重发：连发数包等确认，只重发出错的包。接收方需暂存已到达错序包。,停-等,包0,包1,包1,ACK1,ACK0,发送方,接收方,包丢失,超时重发,包0,包0,ACK1,ACK1丢弃重复包0,发送方,接收方,ACK丢失,超时重发,包0,包1,包0,ACK1,ACK0,ACK1,发送方,接收方,正常,序号是否需要?,后退 N(go-back-N),包 0,包 1,包 2,包 3,包 4,包 5,包 6,包 7,ACK 2,ACK 4,重发包 4,重发包 5,重发包 6,重发包 7,包 0,ACK 5,ACK 7,发送方,接收方,超时,ACK 4
13、 拒绝包5,6,7,后退 N(go-back-N)(续),包 0,包 1,包 2,包 3,包 4,包 5,包 6,ACK 2,ACK 4,重发包 4,重发包 5,重发包 6,包 7,包 0,ACK 5,ACK 7,发送方,接收方,REJ 4,拒绝包5,6,选择重发,包 0,包 1,包 2,包 3,包 4,包 5,包 6,ACK 2,ACK 4,重发包 4,包 7,包 0,包 1,包 2,ACK 7,ACK 1,发送方,接收方,NACK 4暂存包5,6,选择重发问题,0,1,2,3,4,5,6,7,0,1,2,3,包0,包1,包2,包3,包4,包5,重发包0,ACK6,发送方,接收方,发送窗口,
14、接收窗口,ACK6,包6,包7,选择重发对窗口的限制,0,1,2,3,4,5,6,7,包0,包1,包2,包3,重发包0,ACK4,发送方,接收方,发送窗口,接收窗口,序号3位(07),流量控制(flow control),控制发送方流量，使接收方有缓冲可用。“停-等”流控最简单，但网络带宽利用率低。ARPANET 的 NCP 采用“停-等”。“滑动窗口流控(sliding window flow control)”技术。通信双方准备好各自的接收缓冲，称为接收窗口，通告给对方，作为对方的发送窗口。发送窗口是发送方在收到确认前可发送的最大数据量。25层都可有流控,。.,流量控制(flow cont
15、rol)(续)滑动窗口流控,窗口滑动,1,2,3,4,5,6,7,8,9,10,11,12,窗口滑动,1,2,3,4,5,6,7,8,9,10,11,12,已确认,窗口滑动,1,2,3,4,5,6,7,0,1,2,3,4,5,6,7,已确认,0,路由选择,路由器(或交换机)的主要功能就是为主机存储、转发包。为包确定一条从源通过若干路由器(或交换机)到达目标的最优路径，将包从源主机传送到目标主机。路由选择的基本概念基本路由算法,路由选择的基本概念由谁选择？,路由器(或交换机)选择。它们只为包选择到达目标的最优路径的下一站，称之为路由选择(routing)。它们都有一张路由表，包含所有可能到达的目
16、标和到达目标的最优路径的下一站。,路由选择的基本概念静态路由,路由表可以是静态的：路由表在设置后一般不再改变。静态路由信息由管理员手工配置。当网络变化时，可由人工更新配置。静态路由的缺点是它不会随网络结构变化而变化。静态路由的优点是路由器之间无需交换路由信息，可以不占用网络带宽。静态路由可以在简单的网络环境，或速率较低的网段使用。在拨号线路上也常使用。,路由选择的基本概念动态路由,大型网络的主干结点需要采用动态路由：网络情况变化时，路由表要随时更新。动态路由信息由路由器与邻机自动交换、自动更新。但动态路由有路由摆动问题(route flapping)。动态路由的实现需要两个功能：交换路由信息(
17、通过路由协议)；计算和更新路由表(通过路由算法)。,路由选择的基本概念什么时候选择？,若包交换采用数据报方式，则每个包到达路由器(或交换机)时，为之选择路由。若包交换采用虚电路方式，则在虚电路建立时选定路径，在虚电路撤消前，不再为包作路由选择。若采用静态路由，从某源到某目标的所有包都按配置路由转发，数据报方式和虚电路方式没有差别。,路由选择的基本概念什么是所谓“最优路径”？,路由表包含最优路径信息，最优的度量：带宽：链路的数据容量；时延：包从源送达目标所需时间；可靠性：链路的误码率；负载：路由器资源占用情况；跳(hop)数：路径经过的路由器数目；费用。,路由选择的基本概念“距离”最短的路径,各
18、种度量可抽象为“距离”,它可表示时延、跳数等。这样，网络可用有标号图表示：,4,1,2,3,5,2,1,2,3,9,1,基本路由算法由网络图计算(结点1)路由表,1,3,2,4,5,1,2,2,3,9,1,基本路由算法,距离向量路由算法 DV(Distance Vector routing algorithm)告诉邻居我的世界。每处有一个路牌。链路状态路由算法 LS(Link State routing algorithm)告诉世界我的邻居。每处有一张地图。两种算法的比较,距离向量路由算法简介,算法目的：求网络图结点 i 的距离向量 Di 和后继结点向量 Si。Di表示从 i 到图中其它各点的
19、最短距离，Si 表示从 i 到达其它结点的最短路径上的下一站。是一种迭代算法。先给出各结点的Di，Si 初值，以后每个结点向邻结点通报自己的距离向量及后继结点向量值(告诉邻居我的世界),任一结点 i 再根据邻结点信息更新自己的 Di，Si。,距离向量路由算法例,结点1,2,3,4,5的初始路由信息分别是：D1=(0,2,1,),S1=(-,2,3,)D2=(2,0,2,3,),S2=(1,-,3,4,)D3=(1,2,0,9,),S3=(1,2,-,4,)D4=(,3,9,0,1),S4=(,2,3,-,5)D5=(,1,0),S5=(,4,-),1,3,2,4,5,1,2,2,3,9,1,距
20、离向量路由算法例(续),结点 2 收到邻结点1，3，4 的路由信息后，将自己的路由信息 D2，S2 更新如下：mink(D2k+Dk1)=D21，k=1,3,4 D21=D21，S21=S21，同理 D2j=D2j，S2j=S2j，j=2,3,4mink(D2k+Dk5)=D24+D45=3+1，D2=(2,0,2,3,3+1)，S2=(1,-,3,4,4),距离向量路由算法例(续),结点 1,2,3,4,5 的路由信息稳定值为：D1=(0,2,1,5,6)，S1=(-,2,3,2,2)D2=(2,0,2,3,4)，S2=(1,-,3,4,4)D3=(1,2,0,5,6)，S3=(1,2,-,
21、2,2)D4=(5,3,5,0,1)，S4=(2,2,2,-,5)D5=(6,4,6,1,0)，S5=(4,4,4,4,-),距离向量路由算法,初始值：Dii=0,Sii=-,若 i 与 j 相邻,Dij 为 i 与 j 的距离,Sij=j,若不相邻,Dij=,Sij 待定。算法(结点 i 收到相邻结点 k 的 Dk 和 Sk 后，把Di 和 Si 更新为 Di,Si)：对于 j 从1 到 n 选相邻结点v,满足(Div+Dvj)=mink(Dik+Dkj)则 Dij=Div+Dvj,Sij=Siv,距离向量路由算法问题,计数到无限(count-to-infinity)问题：上例,若结点4到5
22、的线路故障,结点4更新路由信息：D4=(5,3,5,0,),S4=(2,2,2,-,)。D=(D15,D25,D35,D45),S=(S15,S25,S35,S45)。故障后，D=(6,4,6,),S=(2,4,2,)。按算法更新D,S：D=(6,8,6,7),S=(2,3,2,2)。再更新：D=(7,8,7,11),S=(3,3,1,2)。再更新：D=(8,9,8,11),S=(3,3,1,2),。,链路状态路由算法简介,由 McQuillan 等提出，称为最短路径优先 SPF(Shortest Path First)算法，于1979年用于 ARPANET。每个结点周期地向所有结点扩散本结点
23、链路状态信息(告诉世界我的邻居)。每个结点维持一个网络拓扑信息数据库，也称链路状态库，有全部结点的链路状态信息，即网络拓扑图。每个结点可以利用 Dijkstra 最短路径算法求出以本结点为根的最短路径树，得到路由表。,链路状态路由算法例,上例中,用C 表示结点链路状态信息中的距离向量：C1=(0,2,1,)C2=(2,0,2,3,)C3=(1,2,0,9,)C4=(,3,9,0,1)C5=(,1,0),1,3,2,4,5,1,2,2,3,9,1,链路状态路由算法例(续),构造以结点 1 为根的最短路径树T1，用 D1 表示从结点 1 到其它各结点的最短距离向量。第一步：T1 树只有根结点 1，
24、D1 的初值取 C1，D1=(,2,1,)。不在树上的结点集合记为 L，L=2,3,4,5第二步：将L 中与1 最近的结点 3 加入树,更新D1和L：D1=(,2,10,),L=2,4,5。第三步：将L中与1 最近的结点 2 加入树，更新D1和L：D1=(,5,),L=4,5。,链路状态路由算法例(续),第四步：将L中与1 最近的结点 4 加入树,更新D1和L：D1=(,6),L=5。第五步：将L中与1 最近的结点 5 加入树,更新D1和L：D1=(,),这就是以结点 1 为根的最短路径树 T1。类似地，可构建以 i 为根的最短路径树 Ti有了最短路径树就可以得到路由表。,链路状态路由算法例(
25、续),1,2,2,3,4,1,5,1,3,2,4,5,1,2,2,3,9,1,链路状态路由算法,常量：M除源结点s 以外的网络所有结点集合。Cij 表示下列值：Cii=0；若 i 与 j 相邻,则Cij 为边长；若 i 与 j 不相邻,则Cij。变量：Dsk=从源结点s到结点k的最短路径的距离，Ssk=从源结点s到结点k的最短路径的下一站。计算：从源结点到其它结点的最短路径的距离向量 D 和路径的下一站向量 S。(1)初始化：L=M；Dsk=Csk；若Dsk，则Ssk=k，否则Ssk为空；,链路状态路由算法(续),(2)循环(当集合L非空)找 L中的某结点 u：对于L中所有结点w,Dsu=mi
26、nw Dsw；若Dsu=s到L中的结点无路径存在,报告错误退出；从 L 中删除 u；对于每个 v V=Lu的邻结点,若 Dsu+Cuv DsvDsv=Dsu+Cuv；Ssv=Ssu；,链路状态路由协议,每个结点要：周期地学习其相邻结点和相邻结点的网络地址；度量到相邻结点的距离，即与它相连的所有链路的当前状态；构造链路状态包LSP，描述与它相连的所有链路当前状态；将LSP发给所有结点；在收齐了全部LSP后，计算到其它结点的最短路径。,两种算法的比较,距离向量路由算法：有“计数到无限”问题。路由器的路由信息从相邻的路由器传播出去，这个过程有延迟，会出现路由不一致。交换整个路由表，交换信息量大。简单
27、，易于实现。,链路状态路由算法：路由器有相同的网络拓扑，路由计算的一致性可保证。只发送本结点的链路状态，交换信息量少。,拥塞控制,例：交通拥塞。在一定的时间间隔，当对资源的需求超过了可用资源时，拥塞就发生。设计问题：道路(链路)容量不匹配加重拥塞。管理问题：资源分配的不合理，也会造成拥塞。网络拥塞现象拥塞控制基本策略-开环控制-闭环控制-丢弃控制,网络拥塞现象,网络拥塞主要发生在路由器或包交换机。当包到达的速率接近或超过包处理和转发的速率，就在路由器或交换机的缓冲区堆积而排起队来。拥塞现象是包的传输时延变大。若无缓冲可用则包被丢弃，若引起超时重传，拥塞加剧，导致网络吞吐量突然下降，称为“拥塞崩
28、溃(congestion collapse)”。,网络拥塞现象网络拥塞对吞吐量的影响,网络吞吐量是数据通过网络的传送速率,吞吐量,负载,无拥塞,轻微拥塞,严重拥塞,A,B,拥塞对吞吐量的影响,网络拥塞现象网络拥塞对时延的影响,网络无拥塞时，包只有传播时延和交换时延，拥塞的网络还有队列时延，队列愈长时延愈大。,时延,负载,拥塞对时延的影响,拥塞控制基本策略开环控制,开环控制(open-loop control)基于资源预约和连接准入控制,用于虚电路式包交换网。开环即事先协商通信流参数，协商后不管网络是拥塞还是带宽富裕，参数不能动态改变。在连接建立时申明数据速率峰值、数据速率平均值、最大吞吐容量等
29、，请求被允许则连接建立，若资源不够则拒绝连接请求。,拥塞控制基本策略开环控制的漏桶(leaky bucket)算法,数据包,漏桶算法,拥塞控制基本策略开环控制的令牌桶(token bucket)算法,令牌,数据包,令牌桶算法,拥塞控制基本策略闭环控制,闭环控制(closed-loop control)是一种动态控制系统，它包括反馈机制和控制机制。反馈机制允许网络把拥塞情况通知数据源。路由器(或交换机)是监控拥塞程度的最好场所。显式反馈和隐式反馈.控制机制允许数据源调整给网络的负载。窗口控制和速率控制,拥塞控制基本策略丢弃控制,当路由器的资源(如缓冲区)用完，或达到某阈值，就丢弃包或拒绝包流进入
30、。丢弃队列尾：对可靠数据传输，应丢弃最新的包，以避免更多的后退 N 重发。丢弃队列头：对容忍少量丢失的视频数据，应丢弃最老的，而保留最新的包。随机丢弃：从队列中按某概率选取一个包丢弃。优先级丢弃：选队列中优先级最低的包丢弃。丢弃只能解决短期拥塞，控制数据源的发送才能解决长期拥塞。,拥塞控制基本策略拥塞控制和流量控制比较,拥塞控制：解决路由器(交换机)和链路资源的瓶颈是网络社会的约束n方是竞争的，拥塞控制有公平性问题 网上结点应遵循同样的拥塞控制策略,流量控制：解决目标资源的瓶颈问题是源和目标双方约定两方一般是合作的，公平性不是问题不同的连接可选择不同的流量控制策略,拥塞控制的增/减算法,Chi
31、u和Jain对闭环控制中源主机调整流量的增/减算法的分析工作，基本的简化假定：网络的反馈是二元信号,指示有、无拥塞；共享网络资源的所有用户收到同样的反馈，用户根据这个反馈调整负载；反馈和控制的循环对所有用户是同步的。即所有用户同时收到反馈，作出反应，网络又作出下一反馈，等等。,拥塞控制的增/减算法模型,用户1,用户2,用户n,.,xi(t)Xgoal?,网络,反馈 Y(t),n个用户共享网络的模型,x1,xn,拥塞控制的增/减算法模型(续),xi(t)：在时刻 t 用户 i 给网络的负载。xi(t)：总负载。Xgoal：网络容量,即最大允许负载。Y(t)：网络的反馈,Y(t)=0无拥塞,用户可
32、增加负载；Y(t)=1有拥塞,用户要减少负载。线性增/减：若Y(t)=0，xi(t+1)=aI+bI xi(t)；若Y(t)=1，xi(t+1)=aD+bD xi(t)。其中，aI 0，bI 1，aD0，bD1。,拥塞控制的增/减算法线性增/减控制,乘增/乘减：Y(t)=0，xi(t+1)=bI xi(t)；Y(t)=1，xi(t+1)=bD xi(t)。加增/加减：Y(t)=0，xi(t+1)=aI+xi(t)；Y(t)=1，xi(t+1)=aD+xi(t)。加增/乘减：Y(t)=0，xi(t+1)=aI+xi(t)；Y(t)=1，xi(t+1)=bD xi(t)。乘增/加减：Y(t)=0，
33、xi(t+1)=bI xi(t)；Y(t)=1，xi(t+1)=aD+xi(t)。,拥塞控制的增/减算法控制函数的选择准则,有效性：用户总负载接近网络最大容量；公平性：所有用户平等地共享网络资源。公平性度量函数：F(x)=(xi)2/(nxi2)。给 k个用户平等分配资源，则F(x)=k/n；若 k=1,F(x)=1/n，是完全不公平的分配；若 k=n,F(x)=1，这是完全公平的分配。收敛性：算法使系统逐步达到公平和有效。,拥塞控制的增/减算法加增/乘减收敛到最优点,在拥塞控制中，加增/乘减(AIMD)算法是能收敛到公平、有效状态的控制机制。,公平线,x,1,=,x,2,x,2,x,1,A,B,C,D,E,F,有效线,x,1,+,x,2,=,X,goal,
