单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,3.3 排队论在数据网中的应用,早期的数据网络是采用信息交换的方式，而后采用分组交换的方式,路由的控制方式分为面向连接和无连接两种,。,为了便于讨论，采用了,Kleinrock,的模型，讨论面向连接的数据网络。,要描述数据业务，比电话业务复杂的多。第一是业务特征突发性强，速率差别较大，并没有一个一致的简单业务模型；第二，数据业务的质量不再象电话业务主要由呼损描述，而是由延时组成，当然这是在一定误码率的基础上讨论。,为了保证低误码率，就要有对抗差错的措施。可能采用反馈重发或前向纠错等手段，而前者会大大影响整个网络延时的讨论。另一个影响延时的因素是路由安排，在网络控制中，路由是核心内容。不同的路由策略甚至使网络面貌有本质变化。下面首先讨论信息交换再讨论分组交换。,网络由许多节点组成。假设信息的长度服从负指数分布，平均为 （,bit），,处理时间与长度成正比；每个节点有无限大存储器；到每个节点的信息包数服从,Poisson,过程，这样假设之后，每个节点均可采用,M/M/1,模型，处理时间为：,，,c,为信道速率，单位,bit/,秒。若:,信息在某个节点的等待时间为：,系统时间,为：,上面对一个节点的一个输出端口来讨论。若假定只采用固定路由，再根据下面这个关于,M/M,问题的输入输出问题定理就可以讨论整个网络了。,定理3.5：,M/M/m,不拒绝排队系统的输出过程与输入过程相互独立，并具有同样的分布规律，即都是以,为均值的,Poisson,流。,例,3.9,两次排队的问题,信息转接：包到达为,Poisson,流，且到达率为入包,/,秒，,包长不定，服从负指数分布，平均包长为,a bit,；,其中,C,1,，C,2,为信道速率，单位为,bit/s。,A,B,有存储器足够大，两个排队系统为不拒绝系统。,服务率,：,设:,r-,第1个排队系统中的包数，,s-,第2个排队系统中的包数；,状态转移图为：,状态方程为：,归1,令通解,:,上面的结果表明可以将两个排队系统分离考虑。,例3.10：若将业务量集中,n,倍，系统时间为原来的1/,n,。,从而，对数据业务也适宜集中，能降低时延。由于前面的输入-输出定理，网络的每个节点的输出端口都可由,M/M/1,来拟合,全程的时延可将各个端点的时延汇集起来就可以了。下面采用,Klenirock,定义的网络总时延来讨论。,定义 为从节点,j,至节点,k,的信息到达率；那么进入网络的总信息率为,穿过链路,i,的系统时间为：,网络平均时延,:,如果根据每对节点分别计算端对端时延,再根据流量比例加权得到的全网平均时延和上面的,Klenirock,网络平均时延是一致的。,Klenirock,关于网络优化的讨论是根据上述假设和,T,的定义得来。网络优化问题包括如何选择链路容量或路由而使,T,最小等。,下面举一个例来描述,T,的计算：,例3.11：有5个节点的网络如图，节点对之间容量是一样的；节点对之间 如下表，也是对称的。,路由是这样固定安排且唯一：能直达就直达；,A，E,是,A,B,E；A，D,是,A,C,D；C，E,是,C,D,E；,另一个方向也经过相同的节点。而链路容量（单位比特/秒）为：,C,1,=C,2,=3130，C,9,=C,10,=2990，C,3,=C,4,=5390，C,5,=C,6,=1340，C,7,=C,8,=517，C,11,=C,12,=3020，C,13,=C,14,=2790,这样,最后，计算得到,T=0.045,秒。显然这个结果是与路由有关的，不同的路由会有不同的结果。,由于信息交换方式引入较大时延，且对节点处理要求较高，不能适宜数据网的要求。,X.25,等分组交换方式与信息交换方式有了很大不同，,X.25,将信息分割成较小的分组，并加上复杂的通信协议，能够大大改善节点的吞吐量和大大减低时延。这主要包括两个方面：分组交换方式下，节点不需要收齐全部分组后再传输，这使等待时延大大缩小。另外由于可以引入灵活的路由策略，而能充分利用全网资源，使节点的吞吐能力大大提高。,应用排队论知识对全网讨论比较困难，从信息交换中可以看到用,M/M/1,拟合实际过程是做了许多假设，要再用,M/M/1,拟合分组交换近似性就更差。考虑到纠错措施和路由的安排，问题就变得更加复杂。数据网的发展日新月异，鉴于理论分析的复杂性，研究很多采用计算机模拟和实际建网后运行获得许多经验数据来进行。,