PPT《高级计算机网络》

高级计算机网络 内容提要 7.

1 概述7.2 现代通信中的排队理论 7.3 现代通信业务的自相似特性 7.4拥塞控制7.5 通信量控制 7.6 ABR通信量管理 7.1 概述 高速网络设计的关键是对性能参数的进行建模和估计的能力.设计者需要有能力在观察到的通信量的基础上估计未来的通信量的大小和特性.通信量的统计特性对很多类设计和配置问题都有影响,这些问题包括资源预留协议,在路由器和ATM交换机上使用的排队规则和缓存大小.另外,为了做出明智的资源预留决定,用户也需要能够对计划的通信量特性进行描述.对描述数据通信量而言由许多参数很重要. 吞吐量特性 平均速率:信源提供的平均负载对于确定分配给该信源的总量是十分关键的.平均速率表示信源在较长的时间里持续发出的流量. 吞吐量特性 峰值速率 这个参数告诉网络通信量最大的速率是多少,以便网络能够通过预留足够的数据传输容量和缓存空间接纳此通信量. 吞吐量特性 可变性 峰值是可变性的一种度量;

一种更直接的度量是吞吐量的变化.可变性衡量一个信源的突发性,它是统计复用被用于提高资源利用效率的程度的一个度量. 时延特性 传输时延 这个参数度量的是数据从信源到目的地的过程中网络所施加的时延.最大传输时延也常常被应用程序作为一项需求提出来. 时延特性 时延偏差 传输时延的偏差大小是实时应用的一个重要参数,在实时应用中目的端应该以平滑连续的速率播放收到的数据,该速率与信源产生的速率匹配.这些以及相似的参数对于网络配 网络性能分析 排队分析提供了一个简单的,容易处理的方法来得到有用的结果,这些结果可以用来知道网络的设计和扩展.几十年来,基于泊松通信量假设的排队分析一直是网络性能分析人员的应用工具.然而,近些年出现了一个对于大家来讲是惊人的结果:至少在某些情况下,数据通信量实质上不是泊松分布的而是自相似(self-similar)或分形(fractal)的.对于这种通信量,网络的性能不能再用排队分析的清楚的公式来描述,网络的时延比预期的更大,吞吐量更低.自从最初的发现之后,对于许多的通信量类型自相似的结果被证实了很多次. 7.2 现代通信中的排队理论 排队理论也称为随机服务理论,是现代运筹学以及通信网理论的重要基础之一.然而尽管经典的排队论有一些漂亮的数学结果,它还是与现代通信技术所要研究的排队问题有一定的差距. 主要的排队分析法 早期的排队研究,主要针对一类输入为泊松过程,服务时间为负指数分布的排队系统.在这种系统中,由于到达和服务的无后效性特点,可用生灭过程(或称生死过程)描述. 扩大状态空间的方法 当输入或服务不再具有无后效性时,直接应用生灭过程理论求解就显得无能为力.这时采用补充变量,用扩大状态空间的方法将非马尔柯夫过程的排队化成一个状态空间为多维的马尔柯夫过程求解.这类方法统称为扩大状态空间法.处理M/Er/1/∞和Er/M/1/∞等排队系统便可以采用这种方法.我们经常提到的相位法属于此类方法. 半马氏分析法 当一个排队系统的服务过程不是马尔柯夫过程,但到达或服务二者之间有一个具有无后效性时,往往可以采用嵌入马氏链法.当可以用半马氏过程描述排队队长变化过程,或输入过程(或服务时间)本身即为一个半马氏过程时,或可嵌入一个半马氏过程时,往往采用半马尔柯夫(Semi-Markov)理论对这类系统进行分析.这种方法称为半马氏分析法. 近似逼近法 对于更一般的排队系统,如G/G/1排队系统,其队长变化过程是一般的随机过程.这时,要求出平稳分布极为困难.可采用积分微分方程法近似求解.不等式定界法近年来也用于分析一般的排队系统,可将之看作近似逼近法的一种.另外的近似逼近法包括系统逼近法和过程逼近法.流体流方法就是一种过程逼近法. 现代通信中排队的特点 现代通信的发展趋势之一是业务综合.它要求实现多种业务在同一个网中传输.显然排队系统的输入将是复合业务流,也就是说输入过程将更加复杂,不再具有Poisson输入过程的无后效性(马尔柯夫性)特点.另外,服务过程和排队策略(规则)也变得更复杂.即使是现有的通信网络在引入新业务之后也会表现出这些特点.比如传统的PSTN网主要是针对普通电话业务设计的,在拨号入(Internet)网业务大量出现之后,描述呼叫的排队系统发生了深刻的变化,Erlang公式不再适应.自然依据该公式设计的PSTN网出现呼损急剧增大甚至系统崩溃等现象便不足为奇了.下面具体地针对ATM这一通信领域最新技术来加以分析.我们需要在三个层次上利用排队理论,分别是呼叫级、突发级和信元级. ATM网 对于呼叫级分析而言,由于ATM网中可以同时传输多种业务,包括面向连接的数据业务、语音业务和视频业务,以及无连接的业务等.业务呼叫的发生(即顾客到达)具有相当复杂的特点,用简单的Poisson输入过程或Erlang输入过程描述也许是不精确的.同时每种业务的持续时间(即服务时间)也将是比较复杂的.突发级排队也具有类似的特点.呼叫级排队分析的目的是要了解呼损的大小等参数.突发级排队分析的目的是要了解以突发级为单位的丢失大小等参数. 信元级分析 需要指出,ATM网中的呼叫接入控制,带宽分配等是以是否能满足一定的业务要求(QOS)为判断标准的,而QOS是以信元丢失率、时延等量描述的.因此还需要将以上两个层次上的分析结果,特别是以突发为单位的丢失,转化为信元丢失率、时延等量.因此更为关键的是信元级分析. 排队策略 ATM排队系统的排队策略(规则)比较复杂.首先,ATM网中存在优先级,包括丢失优先级和时延优先级.这样,信元到达排队系统后就要根据其优先级采取相应的排队策略,这是一个多优先级排队问题.其次,为了满足多种业务的QOS要求,控制策略多种多样,对应于排队系统便是排队策略的不一致.比如ABR业务的引入使得其排队是一个有反馈的闭环系统.另外,根据ATM 论坛关于业务分类的新建议,多队列排队将是ATM排队系统的另一特点. 业务建模 业务模型 On-Off模型 MMPP模型 MMDP模型 排队系统模型B/D/1/K(这里B表示On-Off输入)MMPP/D/1/KMMDP/D/1/K 现代通信研究中常用的排队分析方法 不等式定界逼近方法扩大状态空间法半马氏分析法流体流方法 分组语音通信 半马尔柯夫过程模型及连续时间马尔柯夫链模型.在前一个模型中,首先利用扩大状态空间法将状态定义为一个二维变量,包括信源状态和排队队长.由于采用了多个On-Off语音模型的复合信源作为排队输入,可以用一个马尔柯夫链(在这里更特殊地它是一个生死链)描述,在每一个信源状态下语音分组按一个与状态有关的速率均匀发出.在该文限定的条件下排队状态(二维)服从一个半马尔柯夫过程.我们可以认为这前一个排队模型所采用的分析方法是扩大状态空间法与半马氏分析法的结合. 分组语音通信 后一个模型中,也利用扩大状态空间法将状态定义为一个二维变量,包括信源状态和排队队长.不过它的排队输入是多个两状态MMPP模型的复合信源(即多状态MMPP),在每一个信源状态下语音分组的发出服从Poisson过程.于是整个排队状态(二维)服从一个连续时间马尔柯夫过程.显然这个排队模型所采用的分析方法是扩大状态空间法. 流体流方法 流体流方法(Fluid Flow Method)是一种排队近似分析法.它忽略到达过程及排队队长的离散性质,将到达及队长变化看成连续变化,属于前面介绍的系统逼近法.由于它计算简单、物理意义明确,在文献[Anick 82]将之引入通信领域之后很快得到广泛运用.例如,文献[Daigle 86]分析了它在分组语音通信中的应用.文献[Yin 90]利用它研究语音通信(多On-Off复合输入)中的拥塞控制;