第四章 通信网络理论3

计算机网络理论及网络基础计算机网络理论及网络基础 第四章第四章 通信网络系统通信网络系统 西安交通大学西安交通大学唐亚哲唐亚哲4.5 4.5 流量控制流量控制4.5.1 4.5.1 流量控制的概念流量控制的概念 n流量控制在存贮转发网络中，为了不使节点的接收缓冲流量控制在存贮转发网络中，为了不使节点的接收缓冲溢出，而使信息能顺利、高效传送而施加的控制过程。溢出，而使信息能顺利、高效传送而施加的控制过程。n在在存存贮贮转转发发网网络络中中，如如果果流流量量控控制制过过程程不不完完善善，就就会会使使效效率率受受到到损损失失，甚甚至至会会引引起起网网络络瓶瓶颈颈现现象象，甚甚至至会会使使信信息传送完全停止。这与排队论中的息传送完全停止。这与排队论中的p1p1是对应的。是对应的。n流流量量控控制制就就是是把把业业务务量量密密度度p p的的平平均均值值限限制制在在某某一一恰恰当当的的范围内的控制范围内的控制。4.5.2 4.5.2 流量控制的必要性流量控制的必要性（1 1）维持和改善业务量）维持和改善业务量 中继节点中继节点B主机主机BC=1B中继节点中继节点A主机主机A中继节点中继节点SC=1C=1A0.8（固定）固定）C=10C:线路容量（或速度）线路容量（或速度）：输入业务生成率输入业务生成率 图图4.34 中继节点缓冲器公用的情况中继节点缓冲器公用的情况（2 2）防止瓶颈现象）防止瓶颈现象 1B1.80.81.10.1路径路径A路径路径A+B传输率传输率B：进入中继节点进入中继节点B的信息生成率的信息生成率 图图4.35 的网络吞吐量的网络吞吐量 （3 3）死锁现象及其避免）死锁现象及其避免 AB去节点去节点B的分组的分组去节点去节点A的分组的分组(a)ABCDE去目标去目标C的分组的分组去目标去目标B的分组的分组去目标去目标D的分组的分组去去目目标标E的分组的分组去目标去目标A的分组的分组(b)图图4.36 存储转发型死锁的例子存储转发型死锁的例子（4 4）收发信吞吐量的控制）收发信吞吐量的控制主机主机C3C2B4A3节点节点1B3C1B2B1节点节点2A4A2A1节点节点3图图4.37 报文组装型死锁例报文组装型死锁例主机主机1主机主机2A节点节点1KHJF节点节点2EDCB节点节点3图图4.38 顺序型死锁例顺序型死锁例4.5.3 4.5.3 报文分组交换网中的流量控制报文分组交换网中的流量控制n分组交换网中的分组交换网中的信息是采用分层结构传输的，所以信息是采用分层结构传输的，所以流量控流量控制也采用相应的措施。制也采用相应的措施。（l l）网络访问级的流量控制网络访问级的流量控制 对流入网络的业务量进行控制。对流入网络的业务量进行控制。（2 2）相邻节点间的流量控制）相邻节点间的流量控制 相邻节点之间进行流量控制，以保证分组顺利传送；相邻节点之间进行流量控制，以保证分组顺利传送；（3 3）发送源目标中继节点间的流量控制）发送源目标中继节点间的流量控制 为保证目标中继节点的报文分组能顺利传送，而对发送中为保证目标中继节点的报文分组能顺利传送，而对发送中继节点的报文分组发送进行控制。继节点的报文分组发送进行控制。4.5.4 4.5.4 流量控制的几种方式流量控制的几种方式 1 1、流量控制对系统性能的影响、流量控制对系统性能的影响信息负荷量信息负荷量传传输输效效率率ABCA:A:理想的情况；理想的情况；B:B:采用流量控制后的情况采用流量控制后的情况 ；C C：未使用流量控制的情况未使用流量控制的情况 图图4.39 4.39 业务量与吞吐量的关系业务量与吞吐量的关系 2、常用的几种流量控制方法、常用的几种流量控制方法（l l）利用返回允许发送信号进行控制利用返回允许发送信号进行控制 n当接收缓冲准备好之后再向发送端返回允许发送信号当接收缓冲准备好之后再向发送端返回允许发送信号的方式，可以控制报文分组的传送的方式，可以控制报文分组的传送 ；n对上面每一种流量控制都适用。对上面每一种流量控制都适用。（2 2）窗口流量控制）窗口流量控制 n窗口方式是以报文分组的连续传送为前提的，因此被窗口方式是以报文分组的连续传送为前提的，因此被传送的报文分组上都要带上循环式的连续编号（发送传送的报文分组上都要带上循环式的连续编号（发送的顺序编号），的顺序编号），n发送方和接收方之间按照事先约定的、一次可连续传发送方和接收方之间按照事先约定的、一次可连续传送报文分组的数目为送报文分组的数目为W W，该，该W W就是窗口尺寸。就是窗口尺寸。n因因为为发发送送/接接收收方方都都知知道道从从某某一一个个发发送送顺顺序序编编号号开开始始的的W W个个分分组组可可正正确确发发送送，所所以以当当接接收收方方准准备备好好W W个个空空闲闲缓缓冲冲之之后后，就就把把接接着着应应该该发发送送的的编编号号N N等等应应答答信信息息返返回回给给发送方发送方n发发送送方方接接到到应应答答信信息息后后就就发发送送从从N N号号到到（N+WN+W）号号共共W W个个报文分组报文分组。n接接收收端端接接到到报报文文分分组组时时，只只读读入入窗窗口口内内（N(NN(NW)W)）编号的报文分组，超出窗口尺寸的报文分组都不要。编号的报文分组，超出窗口尺寸的报文分组都不要。n窗窗口口方方式式除除了了流流量量控控制制外外，还还兼兼作作检检查查报报文文分分组组的的损损失、重复、恢复、控制、到达确认等功能。失、重复、恢复、控制、到达确认等功能。01顺序编号（mod 128）下一个应接收的分组接收完而未应答的分组等待接收的分组接收方窗口23127126PrPsPr+w-1(b)接收方窗口Pr:出口的左端（最后接收的报文分组顺序编号）。出口的左端（最后接收的报文分组顺序编号）。Ps:下面应该发送的报文分组顺序编号。下面应该发送的报文分组顺序编号。W：窗口尺寸，窗口尺寸，Pr+w-1：窗口的左端窗口的左端 图图4.40 窗口的结构窗口的结构顺序编号（顺序编号（mod 128）01下一个发下一个发送分组送分组发送结束等待发送结束等待应答的分组应答的分组可发送可发送的分组的分组发发送送方方窗窗口口23127126PrPsPr+w-1(a)发送方窗口发送方窗口 DT00DT10DT20DT30DT41DT51DT61DT71TR8TR7TR4TR2信息类别（数据传送）信息类别（数据传送）发送顺序编号发送顺序编号Ps接收顺序编号接收顺序编号Pr信息类别（可发送）信息类别（可发送）接收顺序编号接收顺序编号若窗口大小若窗口大小=3，这时必须返回应答这时必须返回应答确认确认Ps=0为止为止的分组已送到的分组已送到由于过负荷由于过负荷延迟返回应答延迟返回应答节点节点B节点节点A送出最末数据送出最末数据等待应答等待应答确认确认Ps=0为止为止的分组已送到的分组已送到对对方方窗窗口口大大小小（接接收收缓缓冲冲数）数）=3时，可发送时，可发送3个个DT图图4.41窗口方式的动作序列窗口方式的动作序列（3 3）许可证控制）许可证控制 n许可证控制方式是把流入网络的报文分组总数限定许可证控制方式是把流入网络的报文分组总数限定在一定范围内的广域瓶颈控制方法在一定范围内的广域瓶颈控制方法。n许可证预先存贮在终端中继节点中，要入网的分组许可证预先存贮在终端中继节点中，要入网的分组先取出许可证加在分组报头中才可在网中传送，到先取出许可证加在分组报头中才可在网中传送，到达目标中继节点后释放许可证，保存在该节点中。达目标中继节点后释放许可证，保存在该节点中。当该节点的许可证总数超过规定的数目，就向其他当该节点的许可证总数超过规定的数目，就向其他节点发送。节点发送。n该方法对均匀业务有一定的作用，对局部突发性业该方法对均匀业务有一定的作用，对局部突发性业务的作用不大。务的作用不大。4.6 4.6 报文分组广播式通信报文分组广播式通信 4.6.1 4.6.1 报文分组广播式通信的概念报文分组广播式通信的概念n典型应用：典型应用：局域网的工作方式局域网的工作方式带目标地址的分组报文广播式带目标地址的分组报文广播式的发送到各终端，但只有目标终端才接收该信息。的发送到各终端，但只有目标终端才接收该信息。n发展过程发展过程无线通信无线通信卫星通信卫星通信有线网络通信。有线网络通信。n控制方式控制方式 根据各终端报文分组发送的根据各终端报文分组发送的控制方式不同可分为：控制方式不同可分为：固定分配式、随机访问式、请求分配式。固定分配式、随机访问式、请求分配式。1 1、固定分配方式、固定分配方式n该方式是按时间或者频率该方式是按时间或者频率把把线路分割成若干线路分割成若干信道，每一条信道固定分配信道，每一条信道固定分配给给一个终端的固一个终端的固定分配方法。接收终端监视各信道报文分组定分配方法。接收终端监视各信道报文分组的的目标地址，并接收属于自己的报文分组。目标地址，并接收属于自己的报文分组。n使用这种方式即使若干个终端利用同一条传使用这种方式即使若干个终端利用同一条传输线路也不会发生竞争。输线路也不会发生竞争。n频分多路（频分多路（FDMAFDMA）：按照频率分割传输通路的）：按照频率分割传输通路的方法；方法；n时分多路时分多路(TDMA)(TDMA)：按照时间分割的方式。：按照时间分割的方式。这种方式必须在各终端之间进行时间同步，控制复杂，这种方式必须在各终端之间进行时间同步，控制复杂，但是频带分割损失小，信道带宽变更比较容易，所以是但是频带分割损失小，信道带宽变更比较容易，所以是固定分割方式的主流方法。固定分割方式的主流方法。要把信道固定分配给各发送终端，当终端数目多、业务要把信道固定分配给各发送终端，当终端数目多、业务量为间歇式变化时使用效率会降低。量为间歇式变化时使用效率会降低。2 2、随机访问方式、随机访问方式 n把一条通路作为公用线路使用，各终端若有请求就立即把一条通路作为公用线路使用，各终端若有请求就立即送出报文分组的方式；送出报文分组的方式；n当多个终端同时发送报文分组时就会发生冲突，必须进当多个终端同时发送报文分组时就会发生冲突，必须进行再送控制。因为这种方式是以冲突为前提的，所以也行再送控制。因为这种方式是以冲突为前提的，所以也叫叫争用方式争用方式这就是以太网的控制方式，目前得到了这就是以太网的控制方式，目前得到了非常广泛的应用。非常广泛的应用。3 3、请求分配方式、请求分配方式n为了避免报文分组冲突，而在呼叫设置时采用预约数据为了避免报文分组冲突，而在呼叫设置时采用预约数据传送时间片的方式，所以也叫传送时间片的方式，所以也叫预约方式预约方式；n因为它有时间片预约开销，当终端数目增多时传输效率因为它有时间片预约开销，当终端数目增多时传输效率很低，故只在局部范围内使用，很低，故只在局部范围内使用，4.6.24.6.2争用协议争用协议（1 1）ALOHAALOHA协议协议 终端终端1 1终端终端2 2终端终端3 3合成合成图图4.42 ALOHA4.42 ALOHA协议的动作协议的动作 传输效率分析传输效率分析n假设报文分组的持续时间为假设报文分组的持续时间为，初始生成率为初始生成率为 ，用，用来表示通路的传送效率；来表示通路的传送效率；n假设单位时间内初始报文分组数和再送报文分组数之假设单位时间内初始报文分组数和再送报文分组数之和的平均值为和的平均值为R R；这些报文分组发送完成为止的这些报文分组发送完成为止的2 2 时间时间内，如果不发送其他的报文分组，就不会发生冲突，内，如果不发送其他的报文分组，就不会发生冲突，所以不发生报文分组冲突的概率为所以不发生报文分组冲突的概率为e e-2R-2R；n单位时间再送报文分组的平均数为单位时间再送报文分组的平均数为R(1R(1e e-2R-2R)；则则 R R +R(1+R(1e e-2R-2R)或或 =R=R e e-2R-2R R R 加入给线路的总业务量。加入给线路的总业务量。（2 2）时间片式）时间片式ALOHAALOHA协议协议 n为了改善传送效率，而把线路按时间片进行分割的时为了改善传送效率，而把线路按时间片进行分割的时间片间片ALOHAALOHA协议。其他控制与协议。其他控制与ALOHAALOHA协议完全相同协议完全相同。n当业务量为当业务量为1.01.0时的传送效率最大为时的传送效率最大为0.3680.368 （3 3）CSMACSMA协议协议nCSMACSMA（Carrier Sense multiple accessCarrier Sense multiple access ）：）：具有冲突检测的多路访问协议，这种方式大具有冲突检测的多路访问协议，这种方式大量用于局域网中。量用于局域网中。n在报文分组送出之前，先监视线路上是否有在报文分组送出之前，先监视线路上是否有载波送出，当确认线路空闲后再发送分组，载波送出，当确认线路空闲后再发送分组，这样可减少冲突。这样可减少冲突。n若万一发生冲突，则与若万一发生冲突，则与ALOHAALOHA协议的方法进行协议的方法进行处理；处理；n当检查出线路忙的时，则控制报文分组再送的当检查出线路忙的时，则控制报文分组再送的方法有：方法有：等待随机时间之后再送的方法；等待随机时间之后再送的方法；等到线路空闲之后再送的方法；等到线路空闲之后再送的方法；当线路空闲时按照概率当线路空闲时按照概率P P直接发送，直接发送，以（以（1 1P P）的概率稍等片刻再送的方法等。的概率稍等片刻再送的方法等。n以上方法可在线路时间片分割方式下采用。以上方法可在线路时间片分割方式下采用。（4 4）争用协议的传送效率比较）争用协议的传送效率比较 n在终端数很多的情况下，争用协议的传送效率与终端数在终端数很多的情况下，争用协议的传送效率与终端数无关，而只与业务量有关。无关，而只与业务量有关。n故故争用方式更适用于多数终端都采用间歇式报文分组广争用方式更适用于多数终端都采用间歇式报文分组广播通信的情况。播通信的情况。n下图给出了各种不同控制方式下下图给出了各种不同控制方式下 R R e e-R-R 的的曲线图，从图中可以看出：曲线图，从图中可以看出：纯纯ALOHAALOHA协议下当协议下当为为0.50.5时，最大传送效率为时，最大传送效率为0.1840.184时间片时间片ALOHAALOHA协议下协议下为为1.01.0时的最大传送效率为时的最大传送效率为0.3680.368 CSMACSMA协议下，随着报文分组的传送时延与报文长度协议下，随着报文分组的传送时延与报文长度 之比之比a a的减小而增大。的减小而增大。传传输输效效率率时间片方式时间片方式ALOHAALOHA时间片方式时间片方式CSMAa=0.01CSMA a=0.001CSMA a=0.01CSMA a=0.1a=传送延迟时间传送延迟时间 报文分组的持续时间报文分组的持续时间 图图4.43 争用协议的传送效率争用协议的传送效率0.80.60.40.2 4.6.3 4.6.3 预约协议预约协议 1 1、概述、概述为了避免数据报文分组冲突而在各终端采用事为了避免数据报文分组冲突而在各终端采用事前预约时间片的方式。前预约时间片的方式。n为了使终端能相互取得预约联系，除设置数据为了使终端能相互取得预约联系，除设置数据报文分组传送线路外，还要设置预约线路。报文分组传送线路外，还要设置预约线路。n这种方式在理论上研究很多，但并不常用。这种方式在理论上研究很多，但并不常用。2 2、采用时间片、采用时间片ALOHAALOHA方式下预约协议的传送效率方式下预约协议的传送效率n假设假设1 1次次预约平均能传送预约平均能传送L L个数据报文分组个数据报文分组；n1 1个个数据报文分组需要的时间片数为数据报文分组需要的时间片数为1 1次次预约时间片的预约时间片的V V倍，倍，即即1 1个个报文需要报文需要V V次预约才能完成；次预约才能完成；n1 1次预约次预约平均可传送的数据分组数为平均可传送的数据分组数为，则，则 =VL=VL。n又假又假设时间片设时间片ALOHAALOHA协议的最大传送效率为协议的最大传送效率为C CSASA，预约线，预约线路的容量为路的容量为1 1时，数据线路的容量为时，数据线路的容量为C CSASA n在线路全部使用无浪费的情况下，预约线路容量与总量在线路全部使用无浪费的情况下，预约线路容量与总量之比之比 为：为：=1/=1/（1+C1+CSASA ）(4.5)(4.5)n传送效率：传送效率：1-1-=CSA/（1+C1+CSASA ）（4.6)4.6)3 3、固定分配方式下预约协议的传送效率、固定分配方式下预约协议的传送效率n假设把全线路的时间片总容量假设把全线路的时间片总容量把帧的间隔把帧的间隔也也换算换算为时间片后的总容量为为时间片后的总容量为M M；n1 1个个报文需要报文需要V V次预约才能完成，则次预约才能完成，则1 1个报文需要预约时个报文需要预约时间片数为：间片数为：MV MV；n设终端数为设终端数为N N，预约时间片数也为，预约时间片数也为N N，则则 N/MVN/MVn传送效率为：传送效率为：1-1-=1-=1-N/MV N/MV。L=2L=8L=4L=1M=48M=36M=24M=121008040V=5CSA=1/e0.400.81TDMATDMA方式预方式预约线路的情况约线路的情况争用方式预约争用方式预约线路的情况线路的情况图图4.444.44预约协议的传送效率预约协议的传送效率终端数终端数传传输输效效率率 时间片时间片ALOHAALOHA方式方式传输效率传输效率0.20.61.01.41.8N=50,L=1W=50kb/sTDMA使用时间片使用时间片ALOHAALOHA方式预约线路时的协议方式预约线路时的协议Wi：线路的传送速度线路的传送速度图图4.454.45报文方式广播通信的传送效率和平均传送延迟时间报文方式广播通信的传送效率和平均传送延迟时间0 0.4 0.8 1.0使用使用TDMATDMA方式方式预约线路协议预约线路协议平平均均分分组组传传输输时时延延 （完）完）