计算机通信包交换

1、计算机通信包交换包交换技术包交换技术(packet switching)数据报方式数据报方式:为每个包单独选择路径为每个包单独选择路径BXACDGEFY123包交换技术包交换技术(packet switching)虚电路方式虚电路方式:在源和目标间先建立路径在源和目标间先建立路径BXACDGEFY包交换技术包交换技术(packet switching)数据报和虚电路数据报和虚电路每个包，结点为包逐个选择路径，这种包称为(datagram)。，如，以后X和Y之间的包就在此路径传输。它类似线路交换网中的一条电路。但这条路径不是专用的，它是和其它包、其它连接共享的。包在每个结点仍要作短暂存储，和其它

2、包一起放在输出队列转发。包交换技术包交换技术(packet switching)数据报和虚电路方式比较数据报和虚电路方式比较，可以绕过拥塞区和故障点，所以具有.。但数据报会错序；虚电路方式保证包的传递顺序，容易实现差错控制；两个主机交换大量数据时，虚电路方式更有效，若只交换少量包，数据报方式更快。差错检测差错检测 (parity check) (checksum) ( yclic edundancy heck)奇偶校验奇偶校验奇偶校验：在所发送的每个字符后面添加一个校验位，称为奇偶位(parity bit)。：字符中有奇数个1则添加1, 有偶数个1 则添加0。如 添加 0 成为 。字符连同校验

3、位中1 的总数为偶数。：字符中有奇数个1则添加0, 有偶数个1 则添加1。如 添加 1 成为 。字符连同校验位中1 的总数为奇数。奇偶校验能检测什么差错？ 。校验和校验和有的协议层在包头设置一个校验和字段。若校验和是16位的字段，发送方在发送前将待校验的字符串分成若干长度为16位的段，每个段看成二进制数，进行相加等运算，结果填入校验和字段。校验和可以检测一位错误，一位以上的错误不一定能检测出来。校验和是较简单的差错检测，是计算代价和检测能力之间的一种权衡。循环冗余校验码循环冗余校验码CRC附加帧校验序列附加帧校验序列FCS CRC 常用在数据链路层，附加的校验序列称为帧校验序列 ( rame

4、heck equence)，它是基于CRC计算的，这里只介绍CRC，记为 FMFTk 位r 位循环冗余校验码循环冗余校验码CRC帧校验帧校验CRC码码 F 的计算的计算M 表示被发送的位串，设为 k 位。 P 是 r+1 位的标准位串，rk，M、P 都看作二进制数。当 ，它至少比 P 少一位，可看作 r 位。网中传输的是T，T 看作二进制数，则循环冗余校验码循环冗余校验码CRC校验的原理校验的原理这里的算术运算以 2 为模，即加不进位、减不借位。对任何二进制数 X，XX0，所以 ，即 T 能被 P 除尽。如果收到的 T 能被 P 除尽，是不是 T 在传输中一定没有差错呢？循环冗余校验码循环冗余

5、校验码CRC例子例子110010110111110010001011011100011011011110011011011010001011011011001011011000Q余数R例：给定M 1101011101，P 101101，计算F循环冗余校验码循环冗余校验码CRC问题问题25 M =11010 11101 00000，F = R = 01000， T = 25 M F = 11010 11101 01000。如果收到的T 11010 1 101 01000，则它不能被P 除尽，传输中有错 ，错了一位。如果收到的T 11 1 111 1 1000，它仍能被 P 除尽，但错了四位。循环

6、冗余校验码循环冗余校验码CRC 多项式运算的观点多项式运算的观点每个二进制数都对应一个多项式，。上例中数 M，P，Q，R ( M = 11010 11101，P = 101101， Q = 11110 01000，R = 01000 ) 等对应：循环冗余校验码循环冗余校验码CRC生成多项式生成多项式 P(x)(r 次)多项式 P(x) 称为生成多项式，余式 R(x) 对应 P 生成的CRC码。若传输中无差错，T(x) 能被 P(x) 整除，但能整除不一定传输无差错。有差错即T(x) 变成 T(x)。循环冗余校验码循环冗余校验码CRC生成多项式生成多项式 P(x)的选择的选择一位错误部分 E(x

7、)xi，P(x)不可能除尽 xi 。不可约多项式P(x)的周期e是使P(x)能除尽 xe +1的最小整数(例如 x15+x14+1 的周期是32768)。两位错误部分 E(x) xi +xj，in，jj， 则 xi +xj = xj (xi-j +1)。由于 ，P(x) 除不尽 xi-j +1。另外P(x) 只要多于一项就除不尽 xj 。所以 P(x). 除不尽 E(x)。循环冗余校验码循环冗余校验码CRC生成多项式生成多项式 P(x)的选择的选择 (续续)。奇数位错误部分E(x)的项数为奇数，它不可能被P(x)除尽，因为(x+1)不可能为奇数项多项式的因子。可找P(x)=(x+1)G(x)，

8、G(x)为周期大于帧长的不可约多项式这种错误部分 E(x) = xr +xr-1+ xi = xi (xr-i +1)，P(x)包含常数项，所以 P(x) 不能除尽 xi ，又P(x)为 r 次，大于括号中的多项式次数，也不能除尽它。 循环冗余校验码循环冗余校验码CRC常用的常用的16位位CRC标准生成多项式标准生成多项式循环冗余校验码循环冗余校验码CRCCRC的计算电路例的计算电路例C4C3+C2+C1C0+输入位P = 101101 的 CRC 计算电路CRC计算过程可以用异或门电路和移位寄存器来实现，移位寄存器共r位，异或门最多r位，它们正好对应r次生成多项式P(x)最高次项以外的项。差

9、错检测的局限性差错检测的局限性差错检测都是在包中附加校验信息和数据一起传输。任何差错检测方法都只能检测到某些错误，都不是完美的。在网络结点的链路层几乎都有，检测逐段链路传输错误。在主机的网络层和传输层，如 IPv4、TCP、UDP都有，主要检测数据在主机或路由器发生的错误。差错检测的局限性差错检测的局限性Paxson1997经统计分析发现：。 Stone等1998-1999收集了22亿个包，其中 48万个包有IP，UDP 或 TCP 校验和错误。有主机软、硬件错误，路由器内存错误等。(不要太相信硬件!)校验和是必要的，它和CRC互相补充。.网络结点对包做差错检测，发现错误后丢弃包。如何恢复，就

10、是差错控制。差错控制差错控制确认消息： 正确认 ACK(positive acknowledgement) 和超时重发。 负确认 NACK或REJ (链路层)和重发。 确认消息可以夹带在发送数据包的包头，称为捎带确认(piggybacking)。(确认) ：每发一个包就等待确认。 ：连发数包等确认。顺序接收累计确认, 第 k 个包错, 从第k 个包开始全重发。：连发数包等确认，只重发出错的包。接收方需暂存已到达错序包。停停-等等序号是否需要?后退后退 N (go-back-N)包 0包 1包 2包 3包 5包 6包 7ACK 2ACK 4重发包 5重发包 6重发包 7包 0ACK 5ACK 7

11、超时ACK 4 拒绝包5,6,7后退后退 N (go-back-N)(续续)包 0包 1包 2包 3包 5包 6ACK 2ACK 4重发包 5重发包 6包 7包 0ACK 5ACK 7REJ 4拒绝包5,6选择重发选择重发包 0包 1包 2包 3包 5包 6ACK 2ACK 4包 7包 0包 1包 2ACK 7ACK 1NACK 4暂存包5,6选择重发选择重发问题问题0 1 2 3 4 56 7 0 1 2 3包0包1包2包3包4包5重发包0ACK6发送窗口接收窗口ACK6包6包7选择重发选择重发对窗口的限制对窗口的限制0 1 2 34 5 6 7包0包1包2包3重发包0ACK4发送窗口接收窗

12、口序号3位(07)流量控制流量控制 (flow control)控制发送方流量，使接收方有缓冲可用。“”流控最简单，但网络带宽利用率低。ARPANET 的 NCP 采用“停-等”。“ (sliding window flow control)” 技术。通信双方准备好各自的接收缓冲，称为接收窗口，通告给对方，作为对方的发送窗口。发送窗口是发送方在收到确认前可发送的最大数据量。25层都可有流控,。.流量控制流量控制 (flow control) (续续)滑动窗口流控滑动窗口流控窗口滑动1 2 3 4 5 6 7 8 9 101112窗口滑动1 2 3 4 5 6 7 8 9 101112已确认窗口

13、滑动1 2 3 4 5 6 7 0 1 2 3 4 5 6 7已确认0路由选择路由选择路由器(或交换机)的主要功能就是为主机存储、转发包。为包确定一条从源通过若干路由器(或交换机)到达目标的最优路径，将包从源主机传送到目标主机。路由选择的基本概念路由选择的基本概念由谁选择？由谁选择？。它们只为包选择到达目标的，称之为路由选择(routing)。它们都有一张，包含所有可能到达的目标和到达目标的最优路径的下一站。路由选择的基本概念路由选择的基本概念静态路由静态路由路由表可以是的：路由表在设置后一般不再改变。静态路由信息由管理员手工配置。当网络变化时，可由人工更新配置。静态路由的缺点是它不会随网络结

14、构变化而变化。静态路由的优点是路由器之间无需交换路由信息，可以不占用网络带宽。静态路由可以在简单的网络环境，或速率较低的网段使用。在拨号线路上也常使用。路由选择的基本概念路由选择的基本概念动态路由动态路由大型网络的主干结点需要采用路由：网络情况变化时，路由表要随时更新。动态路由信息由路由器与邻机自动交换、自动更新。但动态路由有路由摆动问题(route flapping)。动态路由的实现需要两个功能：(通过)； (通过)。路由选择的基本概念路由选择的基本概念什么时候选择？什么时候选择？若包交换采用数据报方式，则每个包到达路由器(或交换机)时，为之选择路由。若包交换采用虚电路方式，则在虚电路建立时

15、选定路径，在虚电路撤消前，不再为包作路由选择。若采用静态路由，从某源到某目标的所有包都按配置路由转发，数据报方式和虚电路方式没有差别。路由选择的基本概念路由选择的基本概念什么是所谓什么是所谓“最优路径最优路径”？路由表包含最优路径信息，最优的度量：带宽：链路的数据容量；时延：包从源送达目标所需时间；可靠性：链路的误码率；负载：路由器资源占用情况；跳(hop)数：路径经过的路由器数目；费用。路由选择的基本概念路由选择的基本概念“距离距离”最短的路径最短的路径各种度量可抽象为“距离”, 它可表示时延、跳数等。这样，网络可用有标号图表示：41235212391基本路由算法基本路由算法由网络图计算由网

16、络图计算(结点结点1)路由表路由表目标目标距离距离下一站下一站 1 2 3 4 5 0 2 1 5 6 - 2 3 2 213245122391基本路由算法基本路由算法(Distance Vector routing algorithm)告诉邻居我的世界。每处有一个路牌。 (Link State routing algorithm)告诉世界我的邻居。每处有一张地图。距离向量路由算法距离向量路由算法简介简介算法目的：求网络图结点 i 的和。Di表示从 i 到图中其它各点的最短距离，Si 表示从 i 到达其它结点的最短路径上的下一站。是一种。先给出各结点的Di ，Si 初值，以后每个结点向邻结点通

17、报自己的距离向量及后继结点向量值(告诉邻居我的世界), 任一结点 i 再根据邻结点信息更新自己的 Di，Si 。距离向量路由算法距离向量路由算法例例结点1, 2, 3, 4, 5的初始路由信息分别是：5,S5=( , , ,4,-离向量路由算法距离向量路由算法例例(续续)结点 2 收到邻结点1，3，4 的路由信息后，将自己的路由信息 D2，S2 更新如下：距离向量路由算法距离向量路由算法例例(续续)结点 1, 2, 3, 4, 5 的路由信息稳定值为：D5 = (6, 4, 6, 1, 0)，S5 = (4, 4, 4, 4, -)距离向量路由算法距离向量路由算法：D

18、ii = 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的线路故障, 结点4更新路由信息：D4=(5,3,5,0,), S4=(2,2,2,-,

19、)。D=(D15, D25, D35, D45), S =(S15, S25, S35, S45)。故障后，D=(6, , ,), S=(2,4,2, )。按算法更新D, S：D=( , , , ), S=(2,3,2,2)。再更新：D=( ,8, ,), S=(3,3,1,2)。再更新：D=( , , ,11), S=(3,3,1,2),。链路状态路由算法链路状态路由算法简介简介由 McQuillan 等提出，称为最短路径优先 ( hortest ath irst)算法，于1979年用于 ARPANET。每个结点周期地向所有结点扩散本结点链路状态信息(告诉世界我的邻居)。，也称链路状态库，有

20、全部结点的链路状态信息，即网络拓扑图。每个结点可以利用 。链路状态路由算法链路状态路由算法例例上例中, 用C 表示结点链路状态信息中的距离向量路状态路由算法链路状态路由算法例例(续续)，用 D1 表示从结点 1 到其它各结点的最短距离向量。：T1 树只有根结点 ，D1 的初值取 C1，。不在树上的结点集合记为 L，L=2,3,4,5：将L 中与1 最近的结点 加入树, 更新D1和L： , L=2,4,5。：将L中与1 最近的结点 加入树，更新D1和L： , L=4,5。链路状态路由算法链路状态路由算法例例(续续)：将L中与1 最近的结点 加入树, 更新D1和L：, L

21、=5。：将L中与1 最近的结点 加入树, 更新D1和L：, 这就是以结点 1 为根的最短路径树 。类似地，可构建以 i 为根的最短路径树 Ti有了最短路径树就可以得到路由表。链路状态路由算法链路状态路由算法例例(续续)11322341513245122391链路状态路由算法链路状态路由算法：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：