通信网技术第八章.ppt

通信网技术 第八章 网络流量设计基础 高级计算机网络 3 网络流量是个广泛使用的术语 如 交通网中的车流量 运输网中的货流量 通信网中的信息流量 话务 数据等 网络的作用是传递各种业务流 业务流量的大小反应了人们对网络的需求和网络具有的传送能力 通信网络流量设计应根据业务流量预测值和服务指标要求确定交换设备和线路的容量 并对网内的流量进行合理的分配 以达到节省网络资源的目的 进行网络流量设计首先必须掌握有关通信流量的特性 参数和网内流量的分析方法 高级计算机网络 4 8 1网络流量的基本概念 8 1 1流量的特征 通信网中的信息量受到各种因素的影响 因此 信息流量处在经常的变化之中 这种随时间变化的特性常称为流量的波动性 这种波动性具有随机特征 但从长期平均角度看 它又具有一定的周期性 话务量的波动性 随机性和周期性是研究电话网内流量各种问题的出发点 传输各种业务的通信网 都有各自流量特征 有的与话务量特征相拟 有的则不尽相同 但都具有随机特征 因此要用概率论和随机过程理论来研究 高级计算机网络 5 8 1 2话务量的定义与计算 话务量是用来反映电话用户的通信频繁程度和通话时间的长短的一个参数 电话用户进行通话时 必然要用交换设备和线路设备 通话次数多少和每次通话时间和长短反映了占用设备的程度 同时也反映了用户对电话网设备的需求 从数量上表示这种程度或需求的参数就是话务量Y 它可表示为 话务量强度反映了用户通话设备的程度 也反映了用户对通话设备的需求程度 这实际上是两个不同的概念 话务量还可分为流入话务量和完成话务量 高级计算机网络 6 1 流入话务量 流入话务量等于在平均时长内话源发生的平均呼叫次数 故又称为活源话务量 2 完成话务量 一组设备的完成话务量等于该组设备在平均占用时长内发生的平均占用次数 显然 完成话务量就等于话源话务量减去由于设备的不足而损失的话务量 高级计算机网络 7 8 1 3网络的服务质量 当用户进行呼叫时 希望网络能够为其与呼叫对方迅速建立起信息的通道 对于实时性语言信号 一般采用即时拒绝系统 即如果用户进行呼叫时系统已经被占用满 设有空闲的中断线路 则呼叫被拒绝 这种现象称为呼损 对于非实时性数据传输业务 经常采用延时拒绝系统 即用户输入信息时如果系统已被占满 则延迟一段时间后才被传送 因此会引入时延 所以网络的服务质量主要用呼损和时延来表示 高级计算机网络 8 呼损又叫阻塞率 因为在出现呼损时系统是阻塞的 阻塞率主要有两种定义方法 一种是以系统阻塞时间占总观察时间的百分比定义的时间阻塞率 另一种是以被拒绝的呼叫次数占总呼叫次数的百分比定义呼叫阻塞率 它们可分别表示为 时间阻塞率 呼叫阻塞率 高级计算机网络 9 2 时延 时延通常指从信息进入网络后直到被服务完毕所需时间的总和 包括等待时间 服务时间 传输时延和处理时间 因为传输时延和处理时间一般比较小 因此引起人们关注的主要是延迟拒绝系统的等待时间和服务时间 高级计算机网络 10 8 1 4线路利用率 网络规划设计除了满足服务质量要求外 还要提高网络的效率 如果网中的信道总是没有空闲则会增加呼损 如果信道空闲时间很长 网的效率就很低 因此线路的利用率可以用来表示网和系统的效率 从 完成话务量 中可知 一条中继线的完成话务量实际上就是它的利用率 该线路利用率 可以用每个信道所承担的平均完成话务量表示 即 高级计算机网络 11 8 2 1排队论的基本概念 排队论又称随机服务系统理论 它的奠基人是丹麦数学家爱尔兰 A K Erlang 20世纪初 爱尔兰服务于哥本哈根电话公司 通过对电话交换机使用状况的研究 发表了排队论方面的第一篇论文 70年代以后 这一理论广泛用于通信和计算机等领域 成为通信网业务分析和性能计算不可缺少的工具 8 2排队论基础 高级计算机网络 12 1 排队系统 资源的有限性和需求的随机性是排队现象存在的基础 由要求服务的顾客和提供服务的服务员双方构成的系统通常称为排队系统 研究排队系统的复杂性在于它的随机性 由于顾客到达与服务完毕的时间都是不确定的 绝大多数排队系统工作于随机状态 一个高效的排队系统应能为顾客提供满意服务的同时 尽量提高资源的利用率 因此 排队论是利用概率论和随机过程理论 研究排队系统内服务机构与顾客需求之间的关系 以便合理地设计和控制排队系统 使之即能满足一定的服务质量要求 又能节省服务机构的费用 高级计算机网络 13 2 排队系统的基本参数 任何排队系统在运行中包括三个过程 顾客到达过程 排队过程和顾客接受服务然后离去的过程 描述这三个过程有三个基本参量m 和 称为排队模型的三要素 1 窗口数目m 窗口数目m或服务员数目 表征系统的资源量 表示系统有多少服务设备可同时向顾客提供服务 例如 通信系统中的信道数等 当m 1 可称为单窗口排队系统 当m 1 就是一个多窗口排队系统 高级计算机网络 14 2 顾客到达率 顾客到达率 即单位时间 s 内平均到达系统的顾客数 它反映了顾客到达系统的快慢程度和规律 对系统的工作有很大的影响 越大说明系统的负载量越重 对电话系统 就是单位时间内发生的呼叫次数 对数据传输系统 就是单位时间内输入到系统的平均信息量 3 系统服务率 系统服务率 即单位时间内由一个窗口服务而离去的平均顾客数 顾客接受服务的时间也是个随机变量 其统计平均值称为平均服务时间 的倒数称为系统服务率 即 高级计算机网络 15 3 顾客到达间隔时间和服务时间统计分布 窗口数m 顾客到达率 和系统服务时间率 是排队系统的三个基本参数 但要充分描述并分析其系统的运行状态还是不够的 排队系统的性能主要取决于顾客到达时间间隔和服务时间的统计分布和排队规则 高级计算机网络 16 在常见的排队系统中 对顾客的输入过程一般做如下假设 平稳性 在时间间隔t内 到达k个顾客的概率只与t有关 而与t在时间轴上的位置无关 无后效性 顾客到达时刻相互独立 即在某一 t内顾客到达的概率与下一个 t及其他 t内顾客到达的概率无关 稀疏性 在足够小的时间间隔 t内 到达两个及两个以上的顾客的概率可认为是零 即只有一个或没有顾客到达 且有限时间内到达的顾客数是随机的 满足上述三个条件的顾客流称为最简单流或泊松流 高级计算机网络 17 4 排队系统的工作方式 排队系统的运行性能不仅与上述统计分布有关 还与系统预先规定的工作方式有关 1 按排队规则划分 拒绝方式 当顾客输入时 若系统已有n个顾客且m个窗口均被占用而遭到拒绝 即不容许他排队而离去 当n m时 称为即时拒绝系统 电话通信系统就属于即时拒绝系统 当n m时 称为延时拒绝系统 此时 允许一定人数在排队等待 超过时就被拒绝而离去 带有缓冲存储器的数据通信系统就属于这一类 不拒绝方式 顾客到达时 若窗口不空 就依次排队等待 且对队长没有限制 直到被服务完毕后才离去 高级计算机网络 18 2 按服务规则划分 先到服务 即顺序服务 这是常见的情况 通信网一般采用这种方式 后到先服务 如计算机中内存中数据的提取 优先制服务 对各类顾客赋以不同的优先级 优先级愈高 愈提前服务 在通信网中这种情况也较为常见 高级计算机网络 19 5 排队系统的性能指标 在分析排队系统时 往往需要定量地求解系统的性能指标 通常主要有以下4个 1 排队长度k 排队长度k 简称队长 即某一时刻系统顾客的数量 包括正在被服务的顾客 k是一个非负离散的随机变量 它与输入过程 窗口数目和服务时间均有关系 通常队长为k的概率用 表示 k的统计平均 值为平均队长 高级计算机网络 20 2 等待时间w 等待时间w是指顾客到达至开始服务这段时间 w是连续随机变量 其统计平均值 称为平均等待时间 顾客希望 愈小愈好 在通 信网中 是信息的平均时延的主要部分 其他时延如传输时间 处理时间等一般均为常量 且比较小 3 系统效率 它可定义为平均窗口占用率 若某刻有r个窗口被占用 共有m个窗口 则系统的效率 可用r的统计平均值 与窗口数m的比值表示 愈大 系统服务资源利用率愈高 高级计算机网络 21 4 系统稳定性 令 m 称 为排队强度 右 1 即 m 说明平均到达系统的顾客数小于平均离开系统的顾客数 这系统是稳定的 可以采用不拒绝方式 若 1 即 m 说明平均到达系统的顾客数大于平均离开系统的顾客数 若采用不拒绝方式 系统内顾客的队长将会愈来愈长 平均等待时间趋于无限大 系统会陷入混乱 不能稳定工作 若采取拒绝方式 可人为地限制顾客的队长 保证系统的稳定性 高级计算机网络 22 6 排队系统的表示方法 排队系统的性能取决于它的基本参数和特征 人们为了方便 通常使用符号 来表示一种排队系统 其中X表示顾客到达间隔时间的分布 Y表示服务时间的分布 m表示窗口数目 N表示潜在的顾客总数 对于无限潜在顾客源 可省去该项 n表示截止队长 当n 时 表示不拒绝系统 可省去这一项 高级计算机网络 23 8 2 2M M 1排队系统 M M 1系统是最简单的排队系统 是分析复杂排队系统的基础 上述两式就是M M 1排队问题的系统方程 分析排队系统 就是要解这些系统方程 先解出稳态解 再讨论暂态解 高级计算机网络 24 稳态方程 用递推法可得 高级计算机网络 25 M M 1排队系统的系统方程可以用状态转换图表示 如图8 1所示 图中数字代表系统的状态 箭头表示状态间的转移关系 转移率 表示转移概率为 t 转移率 表示转移概率为 dt 则 8 15 式就可直接从图8 1中看出来 高级计算机网络 26 M M 1排队系统的指标 平均队长为 等待时间w的方差 高级计算机网络 27 平均系统停留时间为 其方差为 对M M 1系统 它的系统效率就是系统内的顾客数的概率 高级计算机网络 28 系统的暂态解 这在短期平稳的系统中更为重要 高级计算机网络 29 M M m n 的问题 从述分析可知 M M 1系统的主要缺点是服务质量与系统效率之间矛盾不易解决 要使排队系统在保证稳定性运行的情况下提高效率 必须采取措施减小等持时间 以达到一定的质量要求 这问题主要是如何压缩排队长度 通常有两种措施 1 增加窗口数 对于一定的到达数 增加窗口数量显然能减少等待时间 同时也能提高效率 在通信网中 增加信道数 扩大线路的传输带宽或提高传输速率和处理速率 都属于这类措施 当然 增加窗口数来提高总服务效率意味着投资加大 2 截止排队长度 也就是采用拒绝系统 这是一种消极措施 截止排队长度的系统又可分为即时拒绝系统和延迟拒绝两种 实际电话系统就属于即时拒绝排队系统 这两种措施可兼用 成为截止型多窗口排队系统 多窗口情况下一般有两种排队方式 其中一个为混合排队方式 即顾客排成一个队 依次接受m个窗口服务 另一个分别排m个队接受m个窗口的服务 若不准中途转队 则为m个独立的M M 1系统 若允许转队 应规定转队规则 不同的规则会有不同的性能参量 高级计算机网络 30 下面我们讨论混合排队方式的M M m n 系统 该系统的特征为 有m个窗口 每个窗口的服务率均为 服务时间和顾客的到达时间间隔均为指数分布 到达率为 截止队长为n 窗口未占满时 顾客到达后立即接受服务 窗口占满时 顾客依次先到先服务规则等待 任一窗口有空即被服务 当队长 包括正在被服务的顾客 长达n时 新来的顾客即被依次拒绝而离去 这种问题的解具有一般性 以前的讨论的M M 1 M M m M M 1 n 和M M m m 系统都是它的特例 高级计算机网络 31 令系统内顾客数k作为系统的状态变量 此时只有n 1种状态 状态转移图如图8 5所示 k增加的转移率均为 但减少转移率与k有关 当k m时 有k个窗口在被占用 则服务率为 当m k n时 m个窗口均被占用 则服务率为 图8 5M M m n 系统的状态转换图 高级计算机网络 32 根据状态转移图可直接得到系统方程 高级计算机网络 33 以下只求稳态解 即 与 无关 记为 上式成为 高级计算机网络 34 上式中有n 1个变量 n 1个线性方程式 这些方程式不是线性无关的 因为它们的和恒等于零 其实在状态转移图中 每一个转移率求和时必然出现两次 一次作为进某状态以正值出现 另一次作为离开某状态的负值出现 所以求和时就相互抵消 由此可见 只要满足其中n个方程 最后一个方程将自动满足 同时 为了解这些 尚须有一个方程式 这就是的归一性 即 高级计算机网络 35 令 对于不拒绝系统 是稳定的充分必要条件 此时平均到达人数 将小于平均离去人数 保证队长不会无限增大 用的方程 可得 再用0 k m的公式 可以递推得 高级计算机网络 36 因而得通解为 再用k m的公式递推 可得 当k n时 就是顾客被拒绝的概率 即 高级计算机网络 37 以上各式的是系统内无顾客的概率 可用概率归一性求得 即 关于的公式 再综合如下 高级计算机网络 38 8 3电路交换网分析 对于电路交换系统 从呼损的角度 可分为呼损系统和溢呼系统两大类 前者是不考虑话务在高效直达路电上的溢出 只考虑在直达路由上的话务损失 而后者是考虑话务在直达路由上溢出到迂回路由后的话务损失 这是迂回路由设置的依据 下面分别进行讨论 高级计算机网络 39 呼损系统 1 呼损清除 传流的电话交换网就是电路交换网 它是具有若干个交换节点 交换节点之间由中继线路群相连接而组成的网络 如果在交换节点的全部出线都被占用的情况下仍有新的呼叫发生 交换节点向用户传送忙着 表示将这一呼叫从交换系统中清除 这种现象称为呼损 相应的系统称为呼叫清除系统 对于某一交换节点来说 如果呼叫到达是泊松过程 中继线群是全利用度线群 阻塞的呼叫立即予以清除 且达到统计平衡状态 则呼叫损失概率 高级计算机网络 40 爱尔兰B公式是在求解电话系统阻塞率或中继线数中常用的计算公式 话务量 中线数和阻塞概率三者之间的关系曲线如图8 7所示 图8 7呼损系统的阻塞率曲线图 高级计算机网络 41 2 呼损返回在上述呼损清除系统的分析中 假定第一次清除的呼叫并不返回 但是在实际情况下 阻塞的呼叫会以重拔的形式返回本系统 每个使用电话的人都会有这样的经历 下面对呼损返回系统作两个基本假定 1 经过多次重拔以后 全部阻塞呼叫都能返回本系统 并且最后被拔通 2 包括第一次呼叫以后重复呼叫的总呼叫次数仍然服从泊松分布 呼损返回系统的阻塞率与话务量及中继线数之间的关系如图8 7中虚线所示 当工作于低阻塞率时 返回话务量的影响很小 可不考虑 但在高阻塞概率时 就需要把返回话务量考虑在内 高级计算机网络 42 溢呼系统 在电话网的交换节点之间既设置直达路由 又设置迂回路由 当流入话务量在高效直达路由上被阻塞以后即溢出到迂回路由上 这种系统称为溢呼系统 溢呼系统是与迂回路由联系在一起的 如图8 8所示的网络连接图 在节点1和2之间除直达路由外 还有三条迂回路由即 1 3 3 2 1 4 4 5 5 2 1 3 3 4 4 5 5 2 节点1和2之间可以通过这几条路由中任意一条来完成接续 图8 8具有迂回路由选择的网络示例图 高级计算机网络 43 在网中设置迂回路由的原因是 一是为提高网络的可靠性 二是提高经济性 对于提高可靠性是不言而喻的 对于提高经济性 下面作进步说明 假设我们希望从节点1到节点2的线群 1 2 的呼损限制为0 02 如不设迂回路由 必须在这个线群中设置足够的电路以使呼损不超过0 02 对比之下 如果设迂回路由 则可在线群 1 2 中配备较少的电路 使有较高的呼损 譬如0 1 如果从节点1到节点2的呼叫遭到呼损 则可经一条呼损为0 2的迂回路由完成接续 由于最终的呼损为0 1 0 2 0 02 所以用户觉察到的总呼损和原来设计的0 02是一样的 于是 线群 1 2 得到了节省 因此 由直达路由承担两节点之间的主要话务量 而迂回路由承担部分话务量 可取得更好的经济效果 高级计算机网络 44 1 溢呼话务量的峰值特性 在溢呼系统中 有两类话务量 一类是到达高效直达路由的话务量 另一类是从高效直达路由溢出到迂回路由的溢出话务量 前者是一种从泊松分布的随机话务量 后者则是不具有随机特征的溢出话务量 高效路由溢呼话务量的特性如图8 9所示 由图可见 由于溢呼路由的话务量曲线比随机话务量曲线更尖锐 所以只确定其平均值不足以描述其特点 还必须把方差考虑进去 图8 9高效路由溢呼话务量特性曲线图 高级计算机网络 45 为了对于话务量的特性进行区分 我们引入峰值比概念 峰值比定义为话务量的方差与均值之比 随机话务量是服从泊松分布的话务量 对于泊松分布 如前所述 它的平均值M和方差V可由下式给出 M T V M T 这就是说 随机话务量的均值和方差相等 它的峰值等于1 当AErl的流入话务量送入N条电路时 其溢呼话务量的均值M可以表示为 M A B N A 此值正好是在随机话务量情况下溢呼话务量送入容量为无穷大的线群的平均占用电路数 高级计算机网络 46 2 等效随机话务量对于随机话务量 可以利用爱尔兰呼损公式来求呼损概率 而对于溢呼话务量 爱尔兰呼损公式就不再适用 为了解决这个问题 威尔金森 Wilknson 提出了一种用 等效随机话务量 来确定迂回路由的呼损概率和迂回路由所需电路数的方法 图8 10所示为一溢呼系统 一般有数条高效直达路由的话务量溢出到同一条迂回路由上 因此迂回路由iT上的溢出话务量的均值和方差为 图8 10典型的溢呼系统示意图 高级计算机网络 47 在图8 10中 迂回路由iT除高效直达路由的的溢呼话务量以外 还有本身的话务量 其均值为 前者是非随机话务 后者就是随机话务量 总的话务量为它们的均值和方差之和 即 根据威尔金森等效随机话务理论 等效话务量和等效中继线数量可表示为 高级计算机网络 48 3 网中的阻塞概率现在讨论具有迂回路由的网中阻塞概率的计算 图8 12所示是一个具有迂回路由的网 直达路由的话务量受到呼损后就溢出到迂回路由中去 a12 40a13 25a23 15节点之间忙时话务量 Erl c12 40c13 30c23 20连路点的容量 电路数 8 12具有迂回路由的网络示例图 高级计算机网络 49 路由选择见表8 1所示 对阻塞概率分析过程中所使用的符号作如下说明 为节点对ij的阻塞概率 为节点对ij的接通概率 为链路ij的阻塞概率 为链路ij的接通概率 为节点对ij的流入话务量 为链路ij的流入话务量 为链路ij的完成话务量 高级计算机网络 50 同时又作如下两点假设 1 链路阻塞概率 和是统计独立的 2 在计算阻塞概率时 溢呼话务量与直达随机话务量没有什么区别 即溢呼话务量的峰值比为1 图8 12所示的网络 可以得到如下表达式为 利用上述几个表达式 只要知道 四个量中的一个量 就可以求出其它各量 高级计算机网络 51 阻塞率和话务量之间的关系可以表示为 完成话务量为 高级计算机网络 52 上面公式中的又可表示为 式中利用了 求链路阻塞就是求满足完成话务量 又满足接通概率的一组 的值 高级计算机网络 53 对于图8 12中的网络 已知 要求 可按如下步骤进行 第一步 设的一组初值为 第二步 设代入公式 计算 第三步 以代入公式 计算得 第四步 以代入公式 计算得到 如此不断继续下去 直到的值收敛为止 在图8 12所示的网络中 只需迭代几次 所求的值就会收敛 在得到后即可求得具有迂回路由的网络的阻塞概 高级计算机网络 54 分组交换网分析 在电路交换系统中采用即对拒绝系统 而分组交换网络采用存贮转发方式 是一个延时拒绝系统 由于有时延的存在 可提高系统效率和降低呼损 然而时延不能太大 太大会降低网络的服务质量 因此 如何计算确定分组交换网的时延是一个至关重要的问题 图8 13所示是一个交换节点的数学模型示意图 经常用一个M M 1排队模型来表示交换节点中的缓冲器 图8 13交换节点中的缓冲过程模型 高级计算机网络 55 节点延时 为了分析信息的时延 假定一个信息到达时 平均已有n个信息等待在缓冲器内 因此 信息在系统中的平均时延T包括等待的时间和被服务的时间 即 T 服务时间 等待时间 服务时间是信息在网络中每段链路传输时间的总和 等待时间是信息在每个节点上等待链路空闲消耗的时间总和 在分组网中 为信息平均长度 bit分组 为链路i的容量或速率 bit s 则每个分组信息在链路上传输时间或服务时间为 为了计算由链路i传送的分组点上的时延 应保持单服务排队系统的假设条件 也就是分组到达率为泊松分布 分组长度服从负指数分布 于是 平均等待时间为 高级计算机网络 56 式中 为链路i中的分组到达率 单位为 分组 s 在分组交换网中 因为还要传送诸如表示数据分组已确接收的一些有意义的控制和附加分组 因此以上1 应考虑控制和数据两类分组的链路总到达率 如果一般设单服务员排队系统完全适用于控制和数据的混合分组流 则经链路i传递的所有分组平均服务时间为 则分组信息在系统中的平均时延为 如图8 14是一个多节点的分组交换网 这样的网络有两类时延 端 端时延和网络平均时延 这两类时延的分组都是建立在单缓冲器时延分析基础上 实际上 分组从源点传到目的地时 经常需要经过若干链路 端 端时延的分析需要考虑每一假链路的时延所造成的影响 网络平均时延仅反映了整体性能 因此 这两类时延的分析和求解有着它的实际意义 网络平均时延 高级计算机网络 57 图8 14分组交换网示例图在图8 14的网络中 我们继续假设分组的到达服从泊松分布 分组的离去为指数统计特性 且这些分组的离去为指数流计特性 我们用表示节点j的分组到达率 且这些分组是发送到节点k的 例如 表示用户发送到节点1并以节点4为目的分组到达率 所有用户发送到分组网络中的总分组到达率 表示为 式中 N为网中总节点数 在这个网络中采用固定路由选择 也就是说对于任何节点 所有j到k的分组只能经过一条路由 所选的路由不必是最短路由 也不允许有迂回路由 高级计算机网络 58 是第i条链路的分组到达率 它是j到k的路由中包含第i条链路的分组到达率为和 即 式中 j k 且通路j k包含链路i 如前所示 1 表示分组的平均长度 且假设分组长度为负指数分布 在实际过程中 分组一旦从用户端发出 在整个分组网传输过程中长度始终不变 如果在这一条件下求解时延 在数学处理上有严重的困难 因此 克莱因洛克引入一种简化的假设 这个假设叫独立假设 即分组网中的节点每次收了分组以后加以存储 然后转发到下一节点 在每一个节点给分组随机地选择一个新的长度 这一假设虽然与实际不符 但根据这一假设作出的分析仍与实际很接近 根据独立性假设和每一链路模型为M M 1排队 可以得到分组经过链路i的平均时延仍如前所述为 高级计算机网络 59 分组信息经过端一端的平均时延是由m个级联的M M 1排队引起的 即有 式中 为端一端的平均时延 m为经过的链路总数 同样 我们可以求得所有分组信息在系统中的平均时延为 式中的求和应当包括网络中的所有链路 高级计算机网络 60 图8 15计算分组时延的网络示意图对于分组交换网而言 信息在系统中的平均时延应包括链路传输时间和节点处理时间 该链路的传输时间为 该节点处理为如将服务时间 等待时间 链路传输时间 节点处理时间加在一起 可求得单个信息在系统中的平均时延 式中 为送入网络中数据分组的总到达率 高级计算机网络 61 如果每条信息由m条分组 m 1 组成 则在网络中传送时在系统中的平均时延由下式计算 式中 是全满数据分组长度 单位为bit 一般情况下 因为是所有数据分组的平均长度 其中也包括小于全满长度分组 是全网总消息的通过量 单位是 数据分组 s 高级计算机网络 62 链路容量的分配 是链路平均利用率 是消息经过的平均链路数 是一个全满分组就所在链路进行平均的传输时间 上面我们分析了分组交换网的平均时延 由于时延是衡量分组交换网性能的重要尺度 因此要尽可能地减少时间延迟 下面要分析的容量分配就是在一定条件下减少时延的一种方法 容量分配是在链路容量为定值的约束条件下 选择每一单向链路的容量 使得系统中的平均时延为最小 高级计算机网络 63 在分析过程中 同样需要若干假设条件 如分组到达服从泊松分布 具有固定路由选择 以及独立假设条件 有约束条件的最小值可以利用拉格朗日乘数法求解 令 现将函数F对求导 可以得到函数的最小值 并可求得第i条链路的最优容量 式中n 为分组信息经过的所有链路的平均数 得出分组信息经过链路i的系统中的平均时延 所有分组信息在系统中的平均时延 高级计算机网络 64 局域网分析 为使得出的有一个可行解 每条链路应具备足够大的容量 以保证其平均速率 也就是必须保持 必须使 1 n 或者说 以使和T所得数值在一定界限内 计算机网络就信道而言可分为两类 采用点到点连接的网络和采用介质共享的广播信道的网络 在介质共享的广播网络中 关键的问题是 当信道的使用发生竞争时 如何分配信道的使用权 广播信道又称多路访问信道或随机访问信道 在相关的通信协议中 有关广播信道分配部分属于数据链路层的子层 称为介质访问控制 MAC 子层 MAC子层在局域网中尤为重要 在竞争的多用户之间分配信道有静态分配与动态分配两种 由于静态分配方法不能有效地处理通信的突发性 我们必须采用信道动态分配 目前 已有多种广为人知的动态分配技术 如随机访问技术 集中式按需分配技术 分散按需分配技术和混合分配技术 各种技术又有多种算法 如图8 17所示 本节主要分析介质共享随机访问信道的基本性能 高级计算机网络 65 图8 17信道访问方式示意图随机访问的特征是访问信道的站没有严格的顺序 一个站次访问不需要其它站的协调 就可以自由传递其报文 也就是说每一个站都能随机地传输其独立分组 因此 随机访问技术就是解决在多站共享信道系统中的冲突问题 最简单的协议是ALOHA协议 这是一个已被广泛的使用的协议 有些文献称为阿罗华系统 要发送信息的站完全无需检测信道状态 无论何时只要有 高级计算机网络 66 数据送来就传输 当两个或更多分组重叠造成冲突时 冲突的分组将失效 并在一个随机时间段后再次重传 ALOHA协议有两种类型 即纯ALOHA和时隙ALOHA 一般来说 纯ALOHA协议的信道利用率较低 纯ALOHA为0 18 时隙ALOHA为0 368 有一种具有俘获能力的时隙ALOHA信道的最大利用率可达0 53 一种能减小潜在冲突的ALOHA协议 称为载波侦听多址访问 CSMA 与ALOHA协议相比 增加了传输前的监听性能 一个站在传输前监听信道 根据信道状况决定传输或等待 尽管增加了传输前的监听性能 冲突仍然可能发生 因为传播延迟并非零 而且站与站之间没有任何协调程序 但与ALOHA协议相比 CSMA具有更好的性能 JP2 为了减少冲突中引起的带宽浪费 CSMA协议增加了传输中的监听性能 一旦发觉冲突 立即停止传输 这种带冲突检测的CSMA称CSMA CD 带冲突的载波侦听多址访问协议 高级计算机网络 67 坚持和非坚持CSMA方式 与ALOHA类似 在CSMA协议中没有中央控制器来协调对信道的访问 也没有时隙和频带的划分 有三种基本的CSMA 不坚持方案 P 坚持方案和l 坚持方案 在不坚持方案中 一个站检测到信道忙就不传送信号而监听传送媒质 它在以后的时间按一定的概率分布延迟后重新安排传递 延迟后如果信道空闲 站就传送分组 反之则重复以上不坚持方案 在P 坚持方案中 站检测到信道空闲 就以概率P传送分组 反之则以概率 1 P 延迟传送 1 坚持方案 是P 坚持方案的一个特例 即P 1 这三种CSMA主要不同在于终端检测信道后的处理方法不同 CSMA协议成功地应用于以太局域网 1 CSMA CD传送原理 CSMA CD是上述CSMA访问方式的改进 上面三种CSMA存在一个相同的问题 报文分组发生冲突后 仍然继续发送到全部结束 我们设想 如果冲突各方检测到冲突后能及时停止发送 使可使信道有效利用率得到提高 载波侦听多址访问 冲突检测 CSMA CD 就是依此原理改进而来的 CSMA CD也是有非坚持 P 坚持和1 坚持三种 IEEE制定的局域网标准IEEE802 3中的介质访问就是按1 坚持CSMA CD方式 其工作原理是 当站点希望传送时 它就侦听 如果线路正忙它就等待线路空闲 如果线路正闲就立即传输 要是两个或多个 高级计算机网络 68 CSMA CD方式 站同时在空闲的电缆上开始传输 它们就会冲突 于是所有冲突站点终止传送 等待一个随机的时间后 再重复上述过程 CSMA CD以及许多局域网协议都采用如图8 18所示的概念模型 此概念模型描述了竞争周期 W 送传周期 T 以及所有站均处于静止时的空闲周期之间的关系 在处 一个站点已经完成了帧的传送 其它想要发送的站点现在都可以尝试发送 如果两个或两个以上的站点同时决定传送 将会产生冲突 站点利用检测回复信号的能量或脉冲宽度突并将之与传送信号比较 就可判断是否产生了冲突 当一个站点检测到冲突后 它便取消传送 等待一个随机时间后 重新尝试传送 假定在此时并没有其它站点开始传送 图8 18CSMA CD的三种状态 竞争 传输和空闲关系示意图 高级计算机网络 69 CSMA CD性能分析 下面我们分析在繁重业务 网络上所有k个站都有分组准备传送 假设下的CSMA CD性能 假设信道按2 的时间间隔划分成时隙 是信道单向传播的最大时延 应注意信道在繁重业务假设下 信道没有空闲 信道中成功和竞争时间间隔交替出现 前面假定冲突时间间隔宽度为W 成功时间间隔的宽度等于一个分组帧的传送时间T 因此网络的利用率 或称吞吐量 是信道传送成功分组的时间函数 信道吞吐量 我们再假定一个用户站准备以概率p传送 或以概率1 p延迟发送 并定义A为一个站成功传送的概率 假定在稳定繁重业务情况下总是有k个站点准备发送 如果站点在竞争时隙内发送的概率为p 此时lk 1个站点将会处于等待状态 以概率1 p 则该时隙内某个站点获得信道成功传送的概率A为 高级计算机网络 70 令为竞争时间间隔宽度内占j个时隙 每个时隙等于2 的概率 例如 在第1个时隙有一个以上的站传送 以概率1 A 下一个时隙有一个站要传送 以概率A 的情况下 竞争时间间隔等于一个时隙 在第1 2两个时隙有一个以上的站传送 在第3个时隙有一个站传送 则竞争时间间隔等于两个时隙 依此类推 所以等于前j个时隙有一个以上的站传送而随后的第j 1个时隙有一个站传送的概率即 则竞争间隔的平均时隙数为 前面已假设每个时隙持续2 则W为 代入吞吐量公式得 高级计算机网络 71 当p 1 k时 A为最大值 可得 当k趋向无穷大时趋于 当时 可得信道吞吐量S为 式中a T 由上可见 当a趋于零时 信道利用率趋于单位1 当a趋于无穷大时 信道利用率趋于零 实际中我们常常期望a 0 1 对于给定电缆长度 即给定 信道传输速率 则a反比于分组长度L 增加L使a减少 信道吞吐量增加 减少L使a增加 信道吞吐量减少 由此可以看出 两站点间的最大电缆长度会影响信道的效率 所以IEEE802 3针对不同电缆长度有不同的版本和不同的电缆拓扑 高级计算机网络 72 ATM网络分析 ATM是采用固定长度信元 面向连接的交换系统 当然 这不是物理连接 而是一种虚连接 VC 对于虚连接方式 不仅有像电路交换那样的在连接建立期间引起的阻塞 而且还有消息传送期间引起的阻塞 传送阻塞 1 输入信元的到达过程 输入信元的到达过程是具有独立的贝努里过程和几何分布的突发过程 对于每个输入端口 每个时隙的信元到达率 也就是输入线的负荷 这种贝努里过程是独立的和等同分布的贝努里过程 on off模型是描述突发过程的一种简单模型 如图8 19所示 图中突发 burst 与静止 silence 之间交替 1个突发含6个信元 目的地址均为2 另一个突发含4个信元 目的地址均为3 图8 19 b 表示状态on与状态off之间的概率转移关系 在on状态 转移到off状态的概率是p 仍保持原状态的概率为1 p 在off状态 转移到on状态的概率为q 保持原状态的概率是1 q 高级计算机网络 73 ATM业务流模型 图8 19on off业务流模型图 突发 的长度是具有参数p的几何分布 一个 突发 持续k个时隙的概率为 k 1表示每个 突发 至少持续1个时隙 即至少1个信元 突发 的平均长度为 高级计算机网络 74 信元输出的分配过程 静止 的长度是具有参数q的几何分布 一个 静止 持续k个时隙的概率为 静止 的持续时隙数k可以等于0 表明一个突发可以紧接一个突发而无静止期 这相当2个不同流的复用 当然2个突发的目的端口不同 静止 的平均长度为 每条入线负荷为 上述突发过程也可称为中断的贝努里过程 2 信元输出的分配过程 信元输出的分配过程可有均匀型和非均匀的hot Spot型 高级计算机网络 75 1 均匀型 所谓均匀型是输入信元的目的地址是独立而均匀分布在所有输出端之间 也就是对于N个输出而言 输入信元以1 N的概率选择每个输出端 2 hot Spot型 所谓hot Spot型是指有很多输入端口的信元都要送往某个输出端口 即hot Spot上 呈现不均匀的业务流 设输入端口的信元到达率为 则有 h相当于去向hot Spot的百分比 也就是有 h个信元去向hot Spot上 1 h 个信元则均匀分布在所有输出端口 3 常用业务流模型 由于业务流模型包含输入过程和输出过程 常用的业务流模型有以下3种 高级计算机网络 76 常用业务流模型 1 均匀业务流 输入过程为独立的贝努里分布 输出分配过程为均匀型的业务流称为均匀业务流模型 均匀业务流模型也称随机业务流 除去这种均匀业务流外 其余均为非均匀业务流模型 均匀业务流便于交换结构的数学模型分析 在实用上对于骨干网交换节点具有分配级的交换结构也颇为接近于均匀分配型 2 突发业务流 突发业务流是指输入过程为突发型 但每个突发 包含相同出端地址的一组信元 的目的地址仍是从N个输出地址中均匀选择 3 Hot Spot业务流 Hot Spot业务流是指输入过程为独立的贝努里分布 但输出的分配是不均匀的 高级计算机网络 77 ATM交换性能分析 缓冲策略或称排队策略是对ATM交换性能具有重要影响的 缓冲策略包括缓冲器设置方式 缓冲器的数量 队列的存取控制及缓冲器的管理 缓冲器的设置方式简称缓冲方式 缓冲方式分为外部缓冲和内部缓冲两大类 外部缓冲是指缓冲器设在交换结构的外部 内部缓冲是指缓冲器设在交换结构的内部 我们知道 排队缓冲器是为了在多个信元随机竞争的情况下减少信元丢失 而竞争又分为出线竞争和内部竞争 由于在外部缓冲方式中 缓冲器不在交换结构的内部 因而这时ATM的内应是一个没有竞争的无阻塞网络 对于有内部竞争的网络应采用内部缓冲方式 外部缓冲主要有输入缓冲 输出缓冲 输入与输出缓冲 环回缓冲等四种方式 内部缓冲又有交叉点缓冲 共享缓冲以及输入或输出缓冲等方式 这里重点介绍输入缓冲和输出缓冲方式的原理与性能 1 输入缓冲性能分析 输入缓冲一般采用简单的先进先出的排队规则 当入线上每个时隙到来时 各个非空输入队列的队首信元进行竞争的仲裁 在竞争中失败的信元暂时留在输入缓冲器中 等待下一轮的竞争和传送 高级计算机网络 78 图8 20HOl阻塞现象示意图输入缓冲存在排头阻塞现象 HOl 所谓HOl阻塞是指在发生出线竞争时 排在竞争中失败的信元之后的去向空闲出线的信元也不能传送的现象 图8 20给出了说明HOl阻塞的示例 缓冲器内的数字表示该信元要去的端号码 入线1与入线2缓冲器中排头信元均要传送到出端2 造成竞争 假定入线2在竞争中失败 队首信元仍留在缓冲器中等待下一轮机会 此时 出线了在该时隙内空闲 无信元传送 而在入线2队列中第2个信元明明是要到出线3 由于排头信元在竞争中失败以及FIFO规则 因此也不能传送 这就是所谓HOl阻塞 由于HOl阻塞 会使出线