教学课件第5章计算机通信包交换.ppt

第第5章章 计算机通信计算机通信—包交换包交换•包交换技术—数据报和虚电路•差错检测•差错控制•流量控制•路由选择•拥塞控制包交换技术包交换技术(packet switching)数据报方式数据报方式:为每个包单独选择路径为每个包单独选择路径BXACDGEFY123包交换技术包交换技术(packet switching)虚电路方式虚电路方式:在源和目标间先建立路径在源和目标间先建立路径BXACDGEFY包交换技术包交换技术(packet switching)—数据报和虚电路数据报和虚电路•每个包独立传递独立传递独立传递独立传递，结点为包逐个选择路径，这种包称为数据报数据报数据报数据报 (datagram)•虚电路虚电路虚电路虚电路 (virtual-circuit) (virtual-circuit)，即逻辑连接，即逻辑连接，即逻辑连接，即逻辑连接 (logical connection)(logical connection)是在主机之间事先建立的是在主机之间事先建立的是在主机之间事先建立的是在主机之间事先建立的一条传输路径一条传输路径一条传输路径一条传输路径，如X-A-B-E-YX-A-B-E-Y，以后X和Y之间的包就在此路径传输。

它类似线路交换网中的一条电路但这条路径不是专用的，它是和其它包、其它连接共享的包在每个结点仍要作短暂存储，和其它包一起放在输出队列转发包交换技术包交换技术(packet switching)—数据报和虚电路方式比较数据报和虚电路方式比较•数据报方式更原始数据报方式更原始，更灵活更灵活，可以绕过拥塞区和故障点，所以具有健壮性健壮性...但数据报会错序；•虚电路方式保证包的传递顺序，容易实现差错控制；•两个主机交换大量数据时，虚电路方式更有效，若只交换少量包，数据报方式更快差错检测差错检测•奇偶校验 (parity check)•校验和 (checksum)•循环冗余校验码CRC (Cyclic Redundancy Check)•差错检测的局限性奇偶校验奇偶校验•奇偶校验：在所发送的每个字符后面添加一个校验位，称为奇偶位(parity bit)•偶校验偶校验偶校验偶校验：字符中有奇数个1则添加1, 有偶数个1 则添加0如 1110 0101110 010 添加 0 成为 1110 01001110 0100字符连同校验位中1 的总数为偶数•奇校验奇校验奇校验奇校验：字符中有奇数个1则添加0, 有偶数个1 则添加1。

如 1110 0101110 010 添加 1 成为 1110 01011110 0101字符连同校验位中1 的总数为奇数•奇偶校验能检测什么差错？ 能检测奇数位差错，不能检测偶数位差错能检测奇数位差错，不能检测偶数位差错能检测奇数位差错，不能检测偶数位差错能检测奇数位差错，不能检测偶数位差错校验和校验和•有的协议层在包头设置一个校验和字段•若校验和是16位的字段，发送方在发送前将待校验的字符串分成若干长度为16位的段，每个段看成二进制数，进行相加等运算，结果填入校验和字段•校验和可以检测一位错误，一位以上的错误不一定能检测出来•校验和是较简单的差错检测，是计算代价和检测能力之间的一种权衡循环冗余校验码循环冗余校验码CRC—附加帧校验序列附加帧校验序列FCS CRC 常用在数据链路层，附加的校验序列称为帧校验序列FCSFCS (F Frame C Check S Sequence)，它是基于CRC计算的，这里只介绍CRC，记为 FMFTk 位r 位循环冗余校验码循环冗余校验码CRC—帧校验帧校验CRC码码 F 的计算的计算•M 表示被发送的位串，设为 k 位 P 是 r+1 位的标准位串，r

•当 2r M 用用P 除时得商除时得商 Q 和余数和余数R ，余数，余数R 就作为帧校验就作为帧校验CRC码码F，它至少比 P 少一位，可看作 r 位网中传输的是T，T 看作二进制数，则T = 2rM + F = (QP + R) + R循环冗余校验码循环冗余校验码CRC—校验的原理校验的原理•这里的算术运算以 2 为模，即加不进位、减不借位对任何二进制数 X，X＋X＝0，所以 T ＝＝QP，即 T 能被 P 除尽•如果收到的如果收到的 T 不能被不能被 P 除尽，则除尽，则 T 在传在传输中一定发生差错输中一定发生差错•如果收到的 T 能被 P 除尽，是不是 T 在传输中一定没有差错呢？循环冗余校验码循环冗余校验码CRC—例子例子10110111110010001011011100011011011110011011011010001011011011001011011000Q余数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 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 P( (x x) )至少包含两项，则可检测所有一位错误至少包含两项，则可检测所有一位错误至少包含两项，则可检测所有一位错误至少包含两项，则可检测所有一位错误一位错误部分 E(x)＝xi，P(x)不可能除尽 xi •若若若若 P P( (x x) )是不可约多项式，且帧长是不可约多项式，且帧长是不可约多项式，且帧长是不可约多项式，且帧长 n n 不大于不大于不大于不大于 P P( (x x) )的周期，则可检测所有两位错误的周期，则可检测所有两位错误的周期，则可检测所有两位错误的周期，则可检测所有两位错误不可约多项式P(x)的周期e是使P(x)能除尽 xe +1的最小整数(例如 x15+x14+1 的周期是32768)两位错误部分 E(x) ＝ xi +xj，ij， 则 xi +xj = xj (xi-j +1)由于 i i- - - -j j < < n n     e e e e，P(x) 除不尽 xi-j +1。

另外P(x) 只要多于一项就除不尽 xj 所以 P(x)... 除不尽 E(x)循环冗余校验码循环冗余校验码CRC—生成多项式生成多项式 P(x)的选择的选择 (续续)•若若P P( (x x) )包含因子包含因子包含因子包含因子( (x x+1)+1)，则可检测所有奇数位，则可检测所有奇数位，则可检测所有奇数位，则可检测所有奇数位错错错错奇数位错误部分E(x)的项数为奇数，它不可能被P(x)除尽，因为(x+1)不可能为奇数项多项式的因子[可找P(x)=(x+1)G(x)，G(x)为周期大于帧长的不可约多项式]•若若若若 P P( (x x) ) 是包含常数项的是包含常数项的是包含常数项的是包含常数项的 r r 次多项式，则可检测次多项式，则可检测次多项式，则可检测次多项式，则可检测长度长度长度长度     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循环冗余校验码循环冗余校验码CRC—CRC的计算电路例的计算电路例C4C3+C2+C1C0+输入位P = 101101 的 CRC 计算电路CRC计算过程可以用异或门电路和移位寄存器来实现，移位寄存器共r位，异或门最多r位，它们正好对应r次生成多项式P(x)最高次项以外的项差错检测的局限性差错检测的局限性•差错检测都是在包中附加校验信息和数据一起传输任何差错检测方法都只能检测到某些错误，都不是完美的•在网络结点的链路层几乎都有CRCCRC校验校验，检测逐段链路传输错误谁做校验谁做校验? ?•在主机的网络层和传输层，如 IPv4、TCP、UDP都有校验和校验和，主要检测数据在主机或路由器发生的错误需不需要？够不够？需不需要？够不够？需不需要？够不够？需不需要？够不够？... ...差错检测的局限性差错检测的局限性•Paxson1997经统计分析发现：通过链路层通过链路层通过链路层通过链路层CRCCRC校验的包约校验的包约校验的包约校验的包约 0.02% 0.02%有校验和错误有校验和错误有校验和错误有校验和错误。

•Stone等1998-1999收集了22亿个包，其中 48万个包有IP，UDP 或 TCP 校验和错误有主机软、硬件错误，路由器内存错误等不要太相信硬件!)•校验和是必要的，它和CRC互相补充•网络结点对包做差错检测，发现错误后丢弃包如何恢复，就是差错控制差错控制差错控制确认消息：•正确认 ACK(positive acknowledgement) 和超时重发•负确认 NACK或REJ (链路层)和重发•确认消息可以夹带在发送数据包的包头，称为捎带确认(piggybacking)•停停- -等等(确认) ：每发一个包就等待确认•后退后退N N ：连发数包等确认顺序接收累计确认, 第 k 个包错, 从第k 个包开始全重发•选择重发选择重发：连发数包等确认，只重发出错的包接收方需暂存已到达错序包…停停-等等包包包包0 0包包包包1 1包包包包1 1ACK1ACK1ACK0ACK0发送方发送方接收方接收方包丢失包丢失包丢失包丢失超超时时重重发发包包包包0 0包包包包0 0ACK1ACK1ACK1ACK1丢弃丢弃丢弃丢弃重复重复重复重复包包包包0 0发送方发送方接收方接收方ACKACK丢失丢失丢失丢失超超时时重重发发包包包包0 0包包包包1 1包包包包0 0ACK1ACK1ACK0ACK0ACK1ACK1发送方发送方接收方接收方正常正常正常正常序号是否需要?后退后退 N (go-back-N)包 0包 1包 2包 3包包 4 4包 5包 6包 7ACK 2ACK 4重发包重发包 4 4重发包 5重发包 6重发包 7包 0ACK 5ACK 7发送方发送方发送方发送方接收方接收方接收方接收方超时ACK 4 拒绝包5,6,7后退后退 N (go-back-N)(续续)包 0包 1包 2包 3包包 4 4包 5包 6ACK 2ACK 4重发包重发包 4 4重发包 5重发包 6包 7包 0ACK 5ACK 7发送方发送方发送方发送方接收方接收方接收方接收方REJ 4拒绝包5,6选择重发选择重发包 0包 1包 2包 3包包 4 4包 5包 6ACK 2ACK 4重发包重发包 4 4包 7包 0包 1包 2ACK 7ACK 1发送方发送方发送方发送方接收方接收方接收方接收方NACK 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发送方发送方接收方接收方发送窗口接收窗口序号3位(0－7)流量控制流量控制 (flow control)•控制发送方流量，使接收方有缓冲可用。

•“停停停停- -等等等等”流控最简单，但网络带宽利用率低ARPANET 的 NCP 采用“停-等”•“滑动窗口流控滑动窗口流控滑动窗口流控滑动窗口流控 (sliding window flow control)” 技术通信双方准备好各自的接收缓冲，称为接收窗口，通告给对方，作为对方的发送窗口发送窗口是发送方在收到确认前可发送的最大数据量•2～5层都可有流控,流量控制流量控制 (flow control) (续续)—滑动窗口流控滑动窗口流控窗口滑动123456789 10 11 12窗口滑动123456789 10 11 12已确认窗口滑动123456701234567已确认0路由选择路由选择•路由器(或交换机)的主要功能就是为主机存储、转发包为包确定一条从源通过若干路由器(或交换机)到达目标的最优路径，将包从源主机传送到目标主机•路由选择的基本概念•基本路由算法路由选择的基本概念路由选择的基本概念—由谁选择？由谁选择？•路由器路由器(或交换机或交换机)选择选择它们只为包选择到达目标的最优路径的下一站最优路径的下一站，称之为路由选择(routing)它们都有一张路路由表由表，包含所有可能到达的目标和到达目标的最优路径的下一站。

路由选择的基本概念路由选择的基本概念—静态路由静态路由•路由表可以是静态静态静态静态的：路由表在设置后一般不再改变静态路由信息由管理员手工配置当网络变化时，可由人工更新配置•静态路由的缺点是它不会随网络结构变化而变化•静态路由的优点是路由器之间无需交换路由信息，可以不占用网络带宽•静态路由可以在简单的网络环境，或速率较低的网段使用在拨号线路上也常使用路由选择的基本概念路由选择的基本概念—动态路由动态路由•大型网络的主干结点需要采用动态动态路由：网络情况变化时，路由表要随时更新动态路由信息由路由器与邻机自动交换、自动更新但动态路由有路由摆动问题(route flapping)•动态路由的实现需要两个功能： 交换路由信息交换路由信息 (通过路由协议路由协议)； 计算和更新路由表计算和更新路由表 (通过路由算法路由算法)路由选择的基本概念路由选择的基本概念—什么时候选择？什么时候选择？•若包交换采用数据报方式，则每个包到达路由器(或交换机)时，为之选择路由•若包交换采用虚电路方式，则在虚电路建立时选定路径，在虚电路撤消前，不再为包作路由选择•若采用静态路由，从某源到某目标的所有包都按配置路由转发，数据报方式和虚电路方式没有差别。

路由选择的基本概念路由选择的基本概念—什么是所谓什么是所谓“最优路径最优路径”？？路由表包含最优路径信息，最优的度量：•带宽：链路的数据容量；•时延：包从源送达目标所需时间；•可靠性：链路的误码率；•负载：路由器资源占用情况；•跳(hop)数：路径经过的路由器数目；•费用路由选择的基本概念路由选择的基本概念—“距离距离”最短的路径最短的路径各种度量可抽象为“距离”, 它可表示时延、跳数等这样，网络可用有标号图表示：41235212391基本路由算法基本路由算法—由网络图计算由网络图计算(结点结点1)路由表路由表13245122391基本路由算法基本路由算法•距离向量路由算法 DV(Distance Vector routing algorithm)告诉邻居我的世界每处有一个路牌•链路状态路由算法 LS(Link State routing algorithm)告诉世界我的邻居每处有一张地图•两种算法的比较距离向量路由算法距离向量路由算法—简介简介•算法目的：求网络图结点 i 的距离向量距离向量距离向量距离向量 Di 和后后后后继结点向量继结点向量继结点向量继结点向量 Si。

Di表示从 i 到图中其它各点的最短距离，Si 表示从 i 到达其它结点的最短路径上的下一站•是一种迭代算法迭代算法迭代算法迭代算法先给出各结点的Di ，Si 初值，以后每个结点向邻结点通报自己的距离向量及后继结点向量值(告诉邻居我的世界), 任一结点 i 再根据邻结点信息更新自己的 Di，Si 距离向量路由算法距离向量路由算法—例例结点1, 2, 3, 4, 5的初始路由信息分别是：D D1 1=(0,2,1,=(0,2,1, , , ), S), S1 1=(-,2,3, , =(-,2,3, , ) )D D2 2=(2,0,2,3,=(2,0,2,3, ), S), S2 2=(1,-,3,4, =(1,-,3,4, ) )D D3 3=(1,2,0,=(1,2,0,9, 9, ), S), S3 3=(1,2,-,4, =(1,2,-,4, ) )D D4 4=(=( ,3,9,,3,9,0,1), S0,1), S4 4=( =( ,2,3,-,5),2,3,-,5)D D5 5=(=( , , , , ,1,0), S,1,0), S5 5=( , , =( , , ,4,-),4,-)13245122391距离向量路由算法距离向量路由算法—例例(续续)结点 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, -, 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的线路故障, 结点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 等提出，称为最短路径优先 SPFSPF (S Shortest P Path F First)算法，于1979年用于 ARPANET。

•每个结点周期地向所有结点扩散本结点链路状态信息(告诉世界我的邻居)每个结点维持一每个结点维持一每个结点维持一每个结点维持一个网络拓扑信息数据库个网络拓扑信息数据库个网络拓扑信息数据库个网络拓扑信息数据库，也称链路状态库，有全部结点的链路状态信息，即网络拓扑图每个结点可以利用 Dijkstra Dijkstra 最短路径算法求出以最短路径算法求出以最短路径算法求出以最短路径算法求出以本结点为根的最短路径树，得到路由表本结点为根的最短路径树，得到路由表本结点为根的最短路径树，得到路由表本结点为根的最短路径树，得到路由表链路状态路由算法链路状态路由算法—例例上例中, 用C 表示结点链路状态信息中的距离向量：C1 = (0, 2, 1, , )C2 = (2, 0, 2, 3, )C3 = (1, 2, 0, 9, )C4 = (, 3, 9, 0, 1)C5 = (, , , 1, 0)13245122391链路状态路由算法链路状态路由算法—例例(续续)构造以结点构造以结点构造以结点构造以结点 1 1 为根的最短路径树为根的最短路径树为根的最短路径树为根的最短路径树T T1 1，用 D1 表示从结点 1 到其它各结点的最短距离向量。

•第一步第一步：T1 树只有根结点 1 1，D1 的初值取 C1，D1=(<0>, 2, 1,  ,  )不在树上的结点集合记为 L，L={2,3,4,5}•第二步第二步：将L 中与1 最近的结点 3 3 加入树, 更新D1和L： D1=(<0>, 2, <1>, 10,  ), L={2,4,5}•第三步第三步：将L中与1 最近的结点 2 2 加入树，更新D1和L： D1=(<0>, <2>, <1>, 5,  ), L={4,5}链路状态路由算法链路状态路由算法—例例(续续)•第四步第四步：将L中与1 最近的结点 4 4 加入树, 更新D1和L：D1=(<0>, <2>, <1>, <5>, 6), L={5}•第五步第五步：将L中与1 最近的结点 5 5 加入树, 更新D1和L：D1=(<0>, <2>, <1>, <5>, <6>), 这就是以结点 1 为根的最短路径树 T1 •类似地，可构建以 i 为根的最短路径树 Ti•有了最短路径树就可以得到路由表链路状态路由算法链路状态路由算法—例例(续续)11322341513245122391链路状态路由算法链路状态路由算法常量常量常量常量：M＝除源结点s 以外的网络所有结点集合。

Cij 表示下列值：Cii =0；若 i 与 j 相邻, 则Cij 为边长；若 i 与 j 不相邻, 则Cij＝∞变量变量变量变量：Dsk=从源结点s到结点k的最短路径的距离，Ssk=从源结点s到结点k的最短路径的下一站计算计算计算计算：从源结点到其它结点的最短路径的距离向量 D 和路径的下一站向量 S1)初始化初始化初始化初始化：L=M；Dsk=Csk；若Dsk∞，则Ssk=k，否则Ssk为空；链路状态路由算法链路状态路由算法 (续续)(2) 循环循环循环循环 (当集合L非空){找 L中的某结点 u：对于L中所有结点w, Dsu= minw Dsw ；若Dsu=∞ {s到L中的结点无路径存在, 报告错误退出；}从 L 中删除 u；对于每个 v ∈V=L∩{u的邻结点},{ 若 Dsu + Cuv < Dsv{Dsv = Dsu + Cuv ；Ssv = Ssu ；} } }链路状态路由协议链路状态路由协议每个结点要：•周期地学习其相邻结点和相邻结点的网络地址；•度量到相邻结点的距离，即与它相连的所有链路的当前状态；•构造链路状态包LSP，描述与它相连的所有链路当前状态；•将LSP发给所有结点；•在收齐了全部LSP后，计算到其它结点的最短路径。

两种算法的比较两种算法的比较距离向量路由算法：•有“计数到无限”问题•路由器的路由信息从相邻的路由器传播出去，这个过程有延迟，会出现路由不一致•交换整个路由表，交换信息量大•简单，易于实现链路状态路由算法：•路由器有相同的网络拓扑，路由计算的一致性可保证•只发送本结点的链路状态，交换信息量少拥塞控制拥塞控制•例：交通拥塞在一定的时间间隔，当对资源的需求超过了可用资源时，拥塞就发生•设计问题：道路(链路)容量不匹配加重拥塞•管理问题：资源分配的不合理，也会造成拥塞•网络拥塞现象网络拥塞现象•拥塞控制基本策略拥塞控制基本策略- - 开环控制开环控制- - 闭环控制闭环控制- - 丢弃控制丢弃控制网络拥塞现象网络拥塞现象•网络拥塞主要发生在路由器或包交换机•当包到达的速率接近或超过包处理和转发的速率，就在路由器或交换机的缓冲区堆积而排起队来•拥塞现象是包的传输时延变大若无缓冲可用则包被丢弃，若引起超时重传，拥塞加剧，导致网络吞吐量突然下降，称为“拥塞崩溃 (congestion collapse)”网络拥塞现象网络拥塞现象—网络拥塞对吞吐量的影响网络拥塞对吞吐量的影响网络吞吐量是数据通过网络的传送速率吞吐量负载无拥塞轻微拥塞严重拥塞AB拥塞对吞吐量的影响网络拥塞现象网络拥塞现象—网络拥塞对时延的影响网络拥塞对时延的影响 网络无拥塞时，包只有传播时延和交换时延，拥塞的网络还有队列时延，队列愈长时延愈大。

时延负载拥塞对时延的影响拥塞控制基本策略拥塞控制基本策略—开环控制开环控制•开环控制(open-loop control)基于资源预约和连接准入控制, 用于虚电路式包交换网•开环即事先协商通信流参数，协商后不管网络是拥塞还是带宽富裕，参数不能动态改变在连接建立时申明数据速率峰值、数据速率平均值、最大吞吐容量等，请求被允许则连接建立，若资源不够则拒绝连接请求拥塞控制基本策略拥塞控制基本策略—开环控制的漏桶开环控制的漏桶(leaky bucket)算法算法数据包漏桶算法拥塞控制基本策略拥塞控制基本策略—开环控制的令牌桶开环控制的令牌桶(token bucket)算法算法令牌数据包令牌桶算法拥塞控制基本策略拥塞控制基本策略—闭环控制闭环控制•闭环控制(closed-loop control)是一种动态控制系统，它包括反馈机制和控制机制•反馈机制反馈机制允许网络把拥塞情况通知数据源路由器(或交换机)是监控拥塞程度的最好场所•显式反馈和隐式反馈...•控制机制控制机制允许数据源调整给网络的负载•窗口控制和速率控制拥塞控制基本策略拥塞控制基本策略—丢弃控制丢弃控制•当路由器的资源(如缓冲区)用完，或达到某阈值，就丢弃包或拒绝包流进入。

•丢弃队列尾丢弃队列尾丢弃队列尾丢弃队列尾：对可靠数据传输，应丢弃最新的包，以避免更多的后退 N 重发•丢弃队列头丢弃队列头丢弃队列头丢弃队列头：对容忍少量丢失的视频数据，应丢弃最老的，而保留最新的包•随机丢弃随机丢弃随机丢弃随机丢弃：从队列中按某概率选取一个包丢弃•优先级丢弃优先级丢弃优先级丢弃优先级丢弃：选队列中优先级最低的包丢弃•丢弃只能解决短期拥塞，控制数据源的发送才能解决长期拥塞拥塞控制基本策略拥塞控制基本策略—拥塞控制和流量控制比较拥塞控制和流量控制比较拥塞控制：•解决路由器(交换机)和链路资源的瓶颈•是网络社会的约束•n方是竞争的，拥塞控制有公平性问题 •网上结点应遵循同样的拥塞控制策略流量控制：•解决目标资源的瓶颈问题•是源和目标双方约定•两方一般是合作的，公平性不是问题•不同的连接可选择不同的流量控制策略拥塞控制的增拥塞控制的增/减算法减算法Chiu和Jain对闭环控制中源主机调整流量的增/减算法的分析工作，基本的简化假定：•网络的反馈是二元信号, 指示有、无拥塞；•共享网络资源的所有用户收到同样的反馈，用户根据这个反馈调整负载；•反馈和控制的循环对所有用户是同步的。

即所有用户同时收到反馈，作出反应，网络又作出下一反馈，等等拥塞控制的增拥塞控制的增/减算法减算法—模型模型用户1用户2用户n... xi(t) > Xgoal?网络反馈 Y(t)n个用户共享网络的模型x1xn拥塞控制的增拥塞控制的增/减算法减算法—模型模型(续续)xi(t)：在时刻 t 用户 i 给网络的负载∑xi(t)：总负载Xgoal：网络容量, 即最大允许负载Y(t)：网络的反馈, Y(t)=0无拥塞, 用户可增加负载；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，aD<0，bD<1拥塞控制的增拥塞控制的增/减算法减算法—线性增线性增/减控制减控制•乘增/乘减：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 Y( (t t)=0)=0，，，，x xi i( (t t+1)= +1)= a aI I+x+xi i( (t t) )；；；； Y Y( (t t)=1)=1，，，，x xi i( (t t+1)= +1)= b bD D x xi i( (t t) )。

•乘增/加减：Y(t)=0，xi(t+1)= bI xi(t)； Y(t)=1，xi(t+1)= aD+ xi(t)拥塞控制的增拥塞控制的增/减算法减算法—控制函数的选择准则控制函数的选择准则•有效性有效性：用户总负载接近网络最大容量；•公平性公平性：所有用户平等地共享网络资源公平性度量函数：F(x)=(∑∑xi)2/ /(n∑∑xi2) 给 k个用户平等分配资源，则F(x)=k/n；若 k=1, F(x)=1/n，是完全不公平的分配；若 k=n, F(x)=1，这是完全公平的分配•收敛性收敛性：算法使系统逐步达到公平和有效拥塞控制的增拥塞控制的增/减算法减算法—加增加增/乘减收敛到最优点乘减收敛到最优点在拥塞控制中，加增/乘减 (AIMD) 算法是能收敛到公平、有效状态的控制机制公平线公平线 x1= x2x2x1A AB BC CD DE EF F有效线有效线 x1+x2=Xgoal。