（系统工程专业论文）缓存管理策略排队模型研究.pdf

江苏大学硕士研究生学位论文 摘要 交换机缓存管理与分配算法的好坏将直接影响系统的性能 本课 题针对缓存管理策略中分组丢失重传 服务公平性以及分组丢失率等 缓存性能问题 试图建立排队模型对其加以分析 以使对缓存性能分 析更准确 更能应用于实践 首先 针对具有随机丢弃分组机制的缓存管理策略 考虑被丢弃 分组以一定概率尝试重传的问题 建立了随机丢弃后重传的排队模型 求解模型然后通过数值结果比较来考察被丢弃分组重传对系统的影 响 然后 对共享缓存分组交换机提出了按需分配缓存的具有门限的 动态双队列缓存管理策略 通过建立具有优先权的尬 m 2 m 1 k 排队 模型对网络服务公平性问题进行分析 我们给出了不同优先级分组的 队长分布 丢失概率等的计算公式 最后 引入m a r k o v 随机环境 建立随机环境下的m m 1 k 排队 模型 对具体的a t m 网中a b r 业务的多门限算法下的缓存性能进行 了分析评价 特别 我们得到了条件队长分布 它动态反映了队长依 赖随机带宽环境状态的起伏变化特征 对上述三种模型求解过程中 我们利用了矩阵几何解法 使求解 过程简单明了 关键词 排队论 缓存管理 随机丢弃分组 重传 动态双队列 a b r 业务 q b d 过程 矩阵几何解 江苏大学硕士研究生学位论文 t h ea l l o c a t i o no fb u f f e ra n db u f f e rm a n a g e m e n ts c h e m e sw i l ld i r e c t l ya f f e c tt h e p e r f o r m a n c eo fap a c k e r s w i t c h e dn e t w o r k o nt h el i g h to fr e t r a n s m i s s i o n f a i r n e s sa n d p a c k e tl o s sp r o b a b i l i t yi nb u f f e rm a n a g e m e n ts c h e m e s t h i sp a p e ro u ra i m i st op r o v i d e ad e t a i l e da n a l y s i so ft h ep e r f o r m a n c eu n d e rd i f f e r e n tb u f f e rm a n a g e m e n ts c h e m e sb y t h eu s eo fq u e u e i n gt h e o r ys oa st om a k et h ea n a l y s i sb em o r ea c c u r a t e m o r eu s e f u l f i r s t l y b a s e do nt h eb u f f e rm a n a g e m e n ts c h e m ew i t hr a n d o m l yd r o p p i n gp a c k e t s m e c h a n i s m aq u e u e i n gm o d e lw i t hr a n d o m l yd r o p p i n ga n dl o s sr e t r a n s m i s s i o nw a s f o r m e d t h ee f f e c t so fr e t r a n s m i s s i o np a c k e t so nt h ep e r f o r m a n c em e a s u r ew e r eo b t a i n e d b yn u m e r i c a li n v e s t i g a t i o n s e c o n d l y ab u f f e rm a n a g e m e n ts c h e m eo fd y n a m i cd u a lq u e u e 耐n lq u e u e t h r e s h o l d d d q q t i sp r o p o s e df o ras h a r e db u f f e rp a c k e ts w i t c h e s t h es c h e m ec a n a l l o c a t eb u f f e ro nd e m a n d b a s e do hi t aa s s o c i a t e dm 1 m 2 m 1 k k q u e u e i n gm o d e l i se s t a b l i s h e d s o m ep e r f o r m a n c ee v a l u a t i o n ss u c ha sq u e u el e n g t hd e n s i t i e sa n dl o s s p r o b a b i l i t i e so f t h et w oc l a s s e sp a c k e t sa r eg i v e n f i n a l l y q u e u e i n gt h e o r yi sa p p l i e di nt h ea n a l y s i so fa ne f c i e x p l i c i tf o r w a r d c o n g e s t i o ni n d i c a t i o n b a s e dm u l t i t h r e s h o l da b r a v a i l a b l eb i tr a t e s e r v i c ef l o w c o n g e s t i o nc o n t r 0 1 a sm u l t i s e r v i c e sc o e x i s tw i t ht h es a m es w i t c h i n g c o n s i d e r i n ga b r s e r v i c ea v a i l a b l eb a n d w i d t ha sar a n d o mb a n d w i d t he n v i r o n m e n t am m 1 kq u e u e i n g m o d e li nar a n d o mb a n d w i d t he n v i r o n m e n ti sf o r m e d s t e a d y s t a t ed i s t r i b u t i o ni s w o r k e do u tb yu s i n gm a t r i xa n a l y s i s e s p e c i a l l y ac o n d i t i o n a lq u e u el e n g t hd e n s i t i e si s o b t a i n e d i nt h ep r o c e s so fr e s o l u t i o n w et r yt ou s em a t r i x g e o m e t r i cs o l u t i o nt ot h et h r e e m o u l d sa b o v em e n t i o n e d t h i sm a k e st h ep r o c e s sb es i m p l e k e yw o r d s q u e u e i n gt h e o r y b u f f e rm a n a g e m e n t r a n d o m l yd r o p p i n gp a c k e t s r e t r a n s m i s s i o n d y n a m i cd u a lq u e u e a v a i l a b l eb i tr a t es e r v i c e q b dp r o c e s s e s m a t r i x g e o m e t r i cs o l u t i o n 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留 使用学位论文的规定 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版 允许论文被查阅和借阅 本人授权江苏大学可以将本学位论文的全部 内容或部分内容编入有关数据库进行检索 可以采用影印 缩印或扫 描等复制手段保存和汇编本学位论文 本学位论文属于 保密口 在年解密后适用本授权书 不保密 学位论文作者签名 爿发吻p l 矽1 年 2 月仙 独创性声明 本人郑重声明 所呈交的学位论文 是本人在导师的指导下 独 立进行研究工作所取得的成果 除文中已注明引用的内容以外 本论 文不包含任何其他个人或集体已经发表或撰写过的作品成果 对本文 的研究做出重要贡献的个人和集体 均己在文中以明确方式标明 本 人完全意识到本声明的法律结果由本人承担 学位论文作者签名 撕b 呼纱1 舢月 7 日 江苏大学硕士研究生学位论文 1 1研究背景 第一章绪论 随着i n t e m e t 的飞速发展 人们已感觉到网络的巨大影响力 近年来 其增长 速度更加惊人 但现有的带宽总难能完全满足用户的要求 产生拥塞是在所难免 的 交换设备必须控制提供给每一个传输流的流量 带宽以及缓存资源 以提供 有区别的分组丢失率和传输延迟 来适应多种类型数据流对网络服务质量 q o s 的 要求 此时 缓存管理在网络传输控制中的作用就显得尤为重要 它是o o s 控制 的核心技术之一 也足实现网络拥塞控制的重要手段 交换机缓存管理与分配算法作为分组转发设备的一个重要功能模块 其具体 的实现技术将直接影响整个网络系统的性能 因此 对缓存管理加以研究 采用 合适的缓存技术就成为i n t e m e t 发展的必然要求 i n t e m e t 中 缓存管理通常是指利用特定的技术和算法 维护缓存的占用量及 缓存的分配方式 并影响下游链路的带宽分配 从整体上优化网络的运行性能 在分组传输过程中 其流经的网络传输节点通常采用队列缓存 延迟转发的服务 方式以提高链路的带宽利用率 缓存管理机制在分组到达队列前端时依据一定的 策略和信息决定是否允许该分组进入缓存队列 从另一个角度看 也就是做出是 否丢弃该分组的决策 因此也称为丢弃控制 由于目前的t c p i p 协议尚不能对明晰速率的反馈信号发生反应f 尽管某些试 验性的t c p 版本支持这种功能 在一般情况下 数据源端和目的端仍将分组丢失 作为网络拥塞的信号 据此调整发送速率 所以 从反馈控制的角度来看 如果 数据源支持t c p 或与之相似的端到端协议 缓存管理所采用的有针对性的分组丢 弃就可以对经过该缓存的流的通信效果发生影响 而这正是基于分组丢弃技术的 缓存管理所能发挥的一个重要作用 为了更清晰地说明基于分组丢弃技术的缓存 管理的职能 需要对分组转发设备中各个功能模块极其相互关系作一个简单的介 绍 分组转发设备的基本功能包括交换 s w i t c h i n g 路由 r o u t i n g 队列调度 s c h e d u l i n g 署b 缓存管理 b u f f e rm a n a g e m e n t 如果要支持区分优先级的分组转发 还需考虑接纳控带l j a d m i s s i o nc o n t r 0 1 资源预留 r e s o u r c er e s e r v a t i o n 流分类 江苏大学硕士研究生学位论文 c l a s s f 3 6 n g 警管 p o l i d n g 等功能 1 1 对于传统的i n t e m e t 分组转发设备 如传统p 路由器 所有业务都以同样等级 的b e s te f f o r t 尽力传送 方式转发 即不支持多优先级 当分组到达时 由缓存管理 模块决定是否对该分组进行缓存 最简单的缓存管理是1 d t a i ld r o p 尾丢弃 为了提高网络的性能 需采用其它的算法 当缓存中存放有多个分组之后 就需由分组调度器 p a c k e ts c h e d u l e r 决定分组 的转发次序 最简单的调度算法是f c f s f i r s t c o m e f i r s t s e r v e d 先到先服务 也 有其它的调度算法可供选用 如f q f a i rq u e u e i n g 公平排队 w f q w e i g h t e d f a i r q u e u e i n g 加权公平排队 等 分组转发的方向由路由控s o r o u t i n gc o n t r 0 1 模块决定 该模块按照某种路由 算法 根据网络的拓扑状态和链路的开销情况 决定将位于输入端口的分组转发 到哪个输出端口 而将分组从输入端口转发到输出端口的具体操作 则由交换结 构 s w i t c h i n gf a b r i c 控制 随着i n t e m e t 的发展 人们对网络提出了更高的要求 不仅希望网络能转发带 宽占用较少的普通的数据业务 也希望它转发高带宽的业务 如包括大量高清晰度 图象的数据文件 以及对时延敏感的业务 如i p 电话 这就要求网络能提供不同 的优先级服务 从而可以根据用户的业务需求和付费等级来决定网络的运作 在 这种情况下 分组转发设备必须支持流分类的功能 对到达分组进行归类 该功 能由分类器 c l a s s i f i e r 实现 之后 不同类别的分组将在缓存管理 调度 甚至路 由和交换等过程中受到不同的对一待 由于b e s t e f f o r t 方式难以满足多优先级服务的要求 为了协调用户需求和网络 有限的资源之间的矛盾 需要一种用户方与网络方协商的机制来为用户预定服务 质量 以使网络方可以根据双方协商达成的结果来区分用户优先级的高低并提供 服务 这就是资源预留协议 如果按照资源预留协议 网络不能满足某个用户提 出的通信要求 就不接纳来自该用户的数据分组 该功能由接纳控 1 a d m i s s i o n c o n t r 0 1 模块来实现 对于己经被网络接纳的用户 如果在实际通信过程中 它的资源占用情况超 过了原先的预定值 而此时如果网络资源不够 来自该用户的分组将有可能受到 惩罚 如被丢弃 这个功能由警管控 1 j p o l i c i n gc o n t r 0 1 模块来实现 2 江苏大学硕士研究生学位论文 排队论是用来建模和系统性能评价的传统方法 所谓性能评价 p e r f o r m a n c e e v a l u a t i o n 嘲嘲h 儿5 1 是指对系统的动态行为进行研究和优化 包括对实际系统的行 为进行测量和模型 按照一定的性能要求对方案进行选择 对现有系统的性能缺 陷和瓶颈进行改进 对未来系统的性能进行预测 以及在保证一定服务质量的前 提下进行设计 性能评价已有相当长的发展历史 它最先用于设计 测量通信系统 确保系 统的传输和开关特性 保证一定的服务质量 后来又被用于解决稀有资源的分配 问题 现在性能评价技术已经被广泛用于计算机和通信领域中 排队论通过对服务对象的到来及服务时间的统计研究 得出一些性能指标 等 待时间 队列长度 利用率 吞吐量等 的统计规律 然后根据这些规律来改进 服务系统的结构或重新组织被服务对象 使得服务系统既能满足服务对象的需要 又能使系统的费用最经济或某些指标最优 如果我们将网络中的分组视为排队论 中的顾客流 将交换机造成的时延看作为排队论中的服务过程 显而易见 排队 理论将对网络协议的制定 提高网络质量起到一定的指导作用 同时网络技术的 发展也为排队理论提供了广阔的应用舞台 缓存管理算法的排队建摸及性能分析是本文的中心 将在后续章节中成为重 点研究的问题 1 2 研究的目标与内容 研究的目标是应用排队理论 对一些缓存管理算法及其改进算法建立排队模 型 在此基础上求出相应模型的解析解 在实际缓存管理过程中 可以从这些模 型中得到的性能指标对缓存器性能进行精确评价 特别 详细讨论缓存中的分组 队长 给缓存的优化设计提供理论依据 在整个研究过程中 对如何改进缓存管 理算法提高o o s 提出一些建设性的建议 研究的内容主要是针对 1 对随机丢弃分组机制考虑重传问题 来考察分组重传对缓存性能的影响 其中 我们分别建立了分组随机丢弃后不考虑重传和考虑重传的排队模型 并研 究对应系统的性能指标变化情况 2 在提高不同优先级业务服务公平性以提供服务质量保证的同时 提高缓存 3 江苏大学硕士研究生学位论文 的整体有效利用率为目标 提出动态双队列的缓存管理策略 并做排队建模分析 3 引入m a r k o v 随机环境的概念 在网络中a b r 等多种业务共存情形下来研 究a b r 业务分组在缓存中的排队状况 1 3 本文组织结构 本文分为六章 第一章为绪论 第二章为缓存管理的基本策略及其排队模型 介绍缓存管理的一些基本概念和方法 以及缓存管理策略的一些基本的排队模型 分析方法 第三章为有关排队理论及工具 介绍本课题研究中用到的一些理论和 定理 本课题的研究是建立在第二 三章这些研究成果基础之上的 第四章为丢 失重传排队系统性能分析 第五章为有门限的动态双队列缓存管理策略排队模型 研究 第六章为随机带宽环境下a b r 业务流量控制排队模型 后三章是本课题的 主要工作重点 4 江苏大学硕士研究生学位论文 第二章缓存管理的基本策略及其排队模型 2 1 缓存管理的基本概念 2 1 1 缓存管理的基本策略 1 从缓存控制的基本原理出发 其控制策略可以从两个层次分析 在数据流的层次上 不同的流隶属于不同的用户 并且有不向的服务质量要 求 归属于不同的服务类别 从系统资源管理的角度来看 缓存管理机制需要采 用一定的资源管理策略 在流经网络传输节点的流之间公平而有效地分配系统中 的队列缓存资源 而在数据分组层次上 缓存管理机制需要采用一定的丢弃控制策略 决定在 什么情况下丢弃分组 如何选择需要丢弃的分组 这是从分组丢弃控制的角度来 看的 在网络传输控制中 有一个基本的假定 相同服务类别的分组的重要性 是等同的 不存在某个分组具有更高的特权或更重要的意义 缓存管理机制的资源管理策略和丢弃控制策略之间有着密切的联系 在设计 缓存管理方案时需要综合考虑 以获得最佳的控制效果 1 资源管理策略 就队列缓存资源管理而言 有共享和划分两种典型策略 总体而言 共享策 略的资源利用率高 但是难以保障不同用户的公平性 而划分策略虽然易于提供 服务质量保障 却降低了资源的利用率 完全共享和完全划分的控制策略都难以 达到满意的效果 由此出现了众多介于完全共享和完全划分策略之间的方案 资 源管理策略分为 完全划分策略 完全共享策略 部分共享策略 萄分组丢弃策略 从分组的角度来看 缓存管理也是分组丢弃机制 当数据分组到达队列前端 时 缓存管理方案根据一定的控制信息和当前系统状态决定是否丢弃该分组 分 组丢弃策略分为 尾部丢弃 头部丢弃 阈值丢弃 随机丢弃 非参数控制丢弃 选择性丢弃 现有的缓存管理算法中大部分都是基于输出端口排队的共享缓存结构 这种 结构能保持网络节点中分组的顺序 当有足够的缓存空问时 到达的分组可能进入 5 江苏大学硕士研究生学位论文 缓存 否则就要丢弃刚到达的分组 或者丢弃缓存中的分组以腾出空间接收刚到 达的分组 2 1 2 缓存管理的基本算法 1 r e d r a n d o me a r l yd e t e 砸o m 及其改进算法 l j 随机早期检澳i j r e d 算法是目前研究得最多的一类主动队列管理技术 它采用 概率判定机制主动地有选择地丢弃某些分组 利用t c p 对发送速率的自适应调节 能力 让某些源端降低发送速率 及时阻止拥塞的恶化 并将平均排队时延控制 在一定的范围内 虽然r e d 的有效性经过了实践的验证 但仍然存在一些缺陷 比如 r e d 算法的性能对网络状况和参数敏感 很难给出优化的参数配置 算法 的稳定性和公平性也存在一些问题 因此 很多r e d 的改进算法应运而生 我们 将r e d 的改进算法分成以下三类 1 l 增强自适应能力的改进r e d 算法 当流的数目较多时 要维持队列长度必 须设置较大的丢弃概率 这样会降低系统的吞吐量 线性的丢弃概率和固定的门 限值是造成这一现象的根本原因 自适应r e d a d a p t i v e r e d 是一种典型的r e d 改进算法 它根据网络拥塞程度相应的增大或减小丢弃概率 稳定r e d s t a b i l i z e d r e d 等算法使用类似的思想对r e d 进行改进 增强其对网络流量负载 变化的自适应能力 劲提高公平性的改进r e d 算法 r e d 没有提供公平性的保证 其随机选择 机制使得发送速率较大的用户流得到的丢弃概率也较大 这种隐含的公平性是比 较脆弱的 不同分组长度 不同往返时延 l l i l d t r i p t u n e s a r 差异 网络中的非 响应流都会损害其公平性 平衡r e d b a l a n c d r e d 算法对速率较高的流施加较 大的丢弃概率 而流砌刃田o w r e d 算法限制单个流的缓存占用量 在一定程度 上提高了r e d 算法的公平性 3 支持多业务的改进r e d 算法 为了满足用户服务区分的需要 具有高低优 先级位的r e d r e d w i t hi n o u tb i t r i 算法将到达分组分为两类 针对不同优 先级的分组实施不同的r e d 算法 基于类似的思想 加权的e d w e i g h t e d r e d 将优先级分得更细 能提供更灵活的服务优先级控制 2 a v q a d a p t i v ev i r t u a lq u e u e i n g 算法 自适应虚拟队列o w q 7 1 算法属于另一类主动队列管理算法 与r e d 算法依 6 江苏大学项士研究生学位论文 据 平均 队列长度判断系统的拥塞状态不同 a v q 算法的判断依据是当前系统的 负载情况 同时 a v q 算法认为直接对队列长度进行控制是导致算法鲁棒性较差 的原因 在系统中t c p 流数量增大的情况下更为严重 因此a v q 算法把输出链路 的带宽利用率作为首要的控制目标 3 动态阈值 d y n a m i ct h r e s h o l d 算法 动态阂值 d d 8 l 算法则是完全从系统资源分配的角度来设计的 最终目的是 最大化缓冲资源利用宰 同时提供多种类别服务的区分 d t 算法基于共享缓存器 模式的分组交换方式 首先提出了在多个物理端口之间公平分配缓冲资源的方案 为了适应服务区分的需求 d t 算法在物理端口的基础上引入不同优先级的服务的 支持 d t 算法为低优先级分组提供了一定的缓存资源 使得其总能获得一定的服 务 而且不同优先级之间的缓存资源配比可以通过参数的调节来实现 d t 算法通 过动态控制参数的调整 能够在一定程度上适应网络流量的变化 同时通过预留 缓存资源来保证不同优先级服务之间的公平性 4 成比例丢失率 p r o p o r t i o n a ll o s sr a t i o 控制算法 成比例丢失率控制 p e r 网算法是基于成比例区分服务模型提出来的 目的是 通过队列管理算法在不同等级的服务类别之间保证稳定的相对丢失率 p l r 算法 有两种形式 p l r o o 和p l r m 两者在统计分组丢失率的时间区间上有所不同 前者统计整个算法运行期间内不同服务类别的丢失率 而后者只关心最近一 段时问的情况 p l r 算法采取选择性丢弃策略 为每个服务类别保存丢失率的估 计值 在到达分组将使得缓冲空间溢出的时候 选择一类分组并丢弃其中的一个 分组 由于p l r 算法总是尽可能丢弃加权丢失率最小类别的分组 在不同服务类 别竞争网络资源的时候 p l r 算法总能在不同服务类别之间保持基本一致的加权 丢失率 即按照相对比率丢弃分组 5 动态部分缓存共享 d y n a m i c p a r t i a lb u f f e rs h a r i n g 算法 动态部分缓存共享 d b p s 1 0 算法在基于静态阈值的p b s 算法的基础上将阈 值动态变化 更能适应网络流量的变化 提高缓存资源的利用率 也解决了p b s 算法参数难以优化设定的问题 同时 在对流量统计特性已知的情况下 可以提 供对不同服务类别的区分服务 保证它们之间可确定的稳定的分组丢失率之比 7 江苏大学硕士研究生学位论文 2 1 3 缓存管理算法的评价 缓存管理算法设计的准确性和实用性是最基本的 并且除了考虑吞吐量和时 延这两个指标外 还应该考虑以下几点 1 算法的公平性 包括不同服务等级之间 相同服务等级的不同业务流之间的 公平性 不同的用户应该按照预先定义的服务质量要求公平地分享网络资源 同 时公平性能一定程度上提供业务流之间的隔离 提供保护功能 萄算法的稳定性和鲁棒性 一方面算法要适应网络流量负载的变化 目前文献 中对r e d 的改进算法和其他基于控制理论的缓存管理算法大多集中在解决该问题 上 另一方面 当网络中有其他非响应流时算法应仍保持稳定 现有文献一般通过 流量监控对t c p 非友好流等不受缓存管理算法控制的业务流进行检查 并依据相 应的策略对其进行惩罚 设计时考虑公平性的缓存管理算法如b a l a n c e d r e d f l o w r e d 等对t c p 友好流都有一定的保护作用 3 算法应该对突发业务有较强的适应性 一般认为 业务流的突发性对缓存管 理算法的性能有负面的影响 现在网络中大量存在着短时突发 具有o n o f t 特 性的网络类 w e b l i k c 业务 当这类业务流的分组进入缓存时 会影响其他业务流 的性能 同时突发业务流的速率会随缓存空间占用量而发生大幅度的振荡 所以 缓存管理算法也应该对突发业务流进行平滑 2 2 排队网络模型综述 2 2 1 排队论的基本概念 排队论 q u e u e i n gs y s t e m 是运筹学的一个重要分支 它主要研究由于顾客的 到达和离开以及服务器的工作和休假 而引起的队伍的积累和消散问题 上世纪 3 0 年代初 丹麦数学家 电气工程师a k e r l a n g 把概率理论应用于电话通话问 题 从而开创了这门应用数学学科 3 0 年代中期 wf e l l e r 引进生灭过程 排队 论逐渐被数学界承认为 f q 重要学科 从此 随着研究的深入 排队理论日益得 到了广泛的应用 人们发现通信系统 网络设计 计算机存储 物流调度等的各 种现象都可以通过排队模型来描述 同时应用相应排队理论的研究成果 可以指 导各种策略设计 给国民经济的发展带来了巨大的贡献 排队系统由三部分组成 顾客 服务台 排队室 顾客是服务台的服务对象 8 江苏大学硕士研究生学位论文 描述一个排队系统需要三个方面内容 1 输入过程 2 服务过程 3 排队规则 我们采用d g k e n d a l l 在1 9 5 3 年提出的记号 蝴来描述一个排队系统 x 表示相继到达时间间隔的概率分布 y 表示服务台对单个顾客服务时间的分布 z 表示服务台个数 a 表示系统容量 排队室大小 m 一负指数分布 d 一定长分 布 g 一般分布 e 一爱尔朗分布 f c f s 一先到先服务 l c f s 一后到先服务 p r i o r i t yq u e u e i n g 优先权排队等 2 2 2 排队论的经典研究方法和成果 从二十世纪初e r l a n g 开创性地对通讯流进行研究至今 经典的排队理论己被 历代数学家充分地发展和研究 经典的排队理论建立在模型满足马氏性的基础上 探讨平稳状态下系统的队 长 等待时间等统计特征量 一般来说 经典排队理论的求解方法主要有三类 一 为k e n d a ll t l 2 提出的嵌入马氏链方法 e m b e d d e dm a r k o vc h a i n 并被发展至马氏 更新方法 这种方法关键通过寻找过程的再生点或马氏点 运用马氏链的技巧或 建立更新方程来得到系统的统计特征量 二是c o x 提出的补充变量法f 1 3 该方法 通过增加变量 构造向量马氏过程 v m p 从而建立密度演化方程 并求解各种统 计特征量 三是n e u t s 提出的q b d 过程理论 1 4 1 他将生灭过程的方法加以推广和 引申 逐渐形成了一套可以处理一系列相关于p h m a p 马氏到达 及b m a p 批马 氏到达 分布所构成的排队模型 尤其值得提出的是q b d 理论己形成了完整的算 法程序 为排队论模型的研究提供了较好的实证结果 半个世纪以来经典排队理论的主要成果大致可总结如下 1 5 1 1 得到了所有单 服务台排队模型在到达间隔和服务时间相互独立条件下的稳态解 2 对于多服务 台排队系统 得到了在服务时间满足指数分布的稳态解 3 优先排队模型也得到 了比较明确的结果 尤其在输入流满足泊松分布以及优先级固定的情况下的排队 4 开 闭网络系统也得到了部分重要结果 随着研究的深入 各种复杂但符合实 际的模型被大量研究 例如带休假的排队模型 拥有不耐烦顾客的排队模型以及 带有灾难的清除排队模型等等 本论文讨论的排队模型将主要用到q b d 过程的理论 我们在3 4 节中给出了 这种方法的基本概念和处理步骤 9 江苏大学硕士研究生学位论文 2 2 3 排队网络模型的性能分析方法和成果 根据顾客的类型 排队网络可分为单一类别的排队网络即所有的顾客具有完 全相同的特征和多类排队网络即系统中有不同类型的顾客 每个节点中不同的顾 客可能有不同的服务请求和不同的路由行为 在网络性能分析中 传统的排队模型一般假定顾客的到达是泊松过程 服务 时间呈负指数分布 节点遵循f c f s 规则 在这种模型中 顾客到达和服务时间均 具有无后效性 后来 由于顾客到达和服务时间不具有无后效性 发展到采用补 充变量将非马尔可夫过程化成一个多维状态空间的马尔可夫过程进行求解 其中 相位法就属于这类方法 然而 对于更一般的排队模型 不易求得平稳分布 人 们只有利用积分微分方程法近似求解 由于我们主要关心系统稳定状态下的行为 所以主要进行稳态分析 5 l 首先要 判断模型在某个状态下是否稳定 即稳定状态概率是否存在 然后求解稳定状态 概率 如果是开环排队网络 可以根据j a c k s o n 定理进行求解 如果是闭环排队网 络 可以先将概率重新正则化 删除不存在的状态 然后使用开环网络的求解方 法 g o r d o n n e w e l l 定理给出了形式化的算法 对于非乘积解排队网络的分析 可 以先修改模型 将非乘积解模型转化为乘积解模型 然后使用上述乘积解模型的 分析方法进行求解 或者采用分解方法或固定点迭代方法直接进行求解 最近 网络流量的自相似特性被提出 瑚 对于自相似流量的分析建模及其对 网络性能的影响便成为网络研究中的一个热门话题 由于自相似过程存在长相关 性 并不能像传统的泊松到达过程那样可以进行精确的解析分析 所以目前仿真方 法仍然是对自相似流量下排队性能进行研究的一个重要手段 分组到达时间间隔 服从p a r e t o 分布的到达过程是最为常用的自相似模型之一 j o r d o n i i7 证明了其自 相似性 并通过仿真方法分析了p a r e t o m i k 队列的排队性能 但大多数基于自 相似流量下网络排队性能的分析都是在缓存为零或无穷情况下进行近似分析的 这在实际的网络环境中并不现实 1 0 江苏大学硕士研究生学位论文 第三章有关排队理论及工具 本章主要讲述本课题研究中所用到的一些关于排队系统的基本理论 主要有 以下几部分组成 马尔可夫链 p h 分布 生灭过程及其极限定理 拟生灭过程 q b d 随机环境等 下面将对这部分内容做简单介绍 3 1 马尔可夫链 1 连续时间参数的马尔可夫链 定义3 1 设连续时间参数随机过程伍 f 0 状态空间e 0 1 2 如 果对于任意的非负整数甩 以及任意0 t l f 2 t n t 0 其无穷小生成元为 q 墨 1 1 2 2 2 吼吼仍 江苏大学硕士研究生学位论文 其中 为历 阶非奇异矩阵 对角元素为负 表示过程在某状态的滞留时间特 性 其余元素非负 表示状态转移概率与滞留时间的比率 历维非零向量t o 满足殆 手 0 并设历 1 维行向量f 口 口叶 j 为过程的初始概率向量 且有口p 口 1 提适当维数元素全为1 的列向量 那么过程由初始状态出发最终进入吸收状态 所需时间的概率分布为 f x 一qe x p t x e xi 0 由上式定义的概率分布为连续p h 分布 口 力称为 矽的一个表示 可 以看出 解析朋分布的关键在于确定初始概率向量口和脚 历阶非奇异矩阵兀 3 2 2 离散p h 分布 定义3 4 设在有限状态空间e 1 2 t 腰 廖 1 上的m a r k o v 链 历 l 为吸收状态 转移概率矩阵表示成分块形式 q 书 其中 m 阶方阵踺子随机阵 满足乃 1 0 t e e 非负列向量于 力岛i 理非 奇异的 m a r k o v 链的初始分布是r 口 口时 满足口e 口矿 1 提适当维数的 元素全为1 的列向量 上述m a r k o v 链吸收前转移步数胸分布 即 热 p x 胡 翟唧 由上式定义的概率分布为离散p h 分布 称 口 7 是减分布 见 k 田的历阶 p h 表示 3 3 生灭过程及其极限定理 1 生灭过程 1 8 定义3 5 非负整数集 0 l 1 上的m a r k o v 过程留o f o 如果其无穷小生 成元有下列三对角形式 江苏大学硕士研究生学位论文 q 一 以 z 以 则称 j r p o 是一个生灭过程 协 嚣 o 称为生率 心 撵 o 称为灭率 生灭过程的最基本特征是 在充分短的时间内 过程只能转移到相邻的状态上 即当 f 一0 时 有 f t j a t o a t k j l p x t a t kjx t j 1 篇瓮 卸扣j 州 l yh o 出 陋一卅 2 2 极限定理3 2 1 研 令弓 l i m p t j e 1 对有限状态e 0 工2 后 的生灭过程 砖 j o 工 七 存在 与初始条 件无关 且弓 o 弓 1 即把 j o 工 尼j 为平稳分布 2 对无限状态e 0 1 2 惕 的生灭过程 若有条件1 妻鱼生二鱼 o 弓 1 即谚 0 1 2 j 为平稳分布 3 4 拟生灭过程 o b d 1 乜们 定义3 6 考虑一个二维m a r k o v 过程留o 厂p 有状态空间 q 缸 歹 七 o 1 2 历 状态集船固 所 称为水平七 k o 如果将状 态按字典顺序排序后 其生成元可写成下列分块三对角形 五 一 凡 鲍 一 厶 江苏大学硕士研究生学位论文 o 则称留o 歹 是一个拟生灭过程 q u a s ib i r t ha n d d e a t hp r o c e s s 简记q b d 其中所有子块是m 阶方阵 a 七 o 有负的对角线元素 并且行和非正 吼和c 都是非负阵 满足 c 弘 反 g 心k 1 q b d 是经典生灭过程从一维状态空间到二维状态空间的推广 经典生灭过程 的状态x t k 视为被分解成m 个子状态敝d m 这一结构顺应了刻画过 程在多层次 多相位及变动参数情况下演化的要求 e v a n s 1 9 6 7 首先在排队论分 析中使用这类过程 w a l l c a e 1 9 6 9 毛e h 算机系统研究中也遇到这类过程 并由他引 入了 拟生灭过程 这一术语 迄今广泛使用的只是一类特殊的q b d 即生成元q 中的子块从某一水平开始 不再发生变化的情形 这时 过程生成元如 q a oc o b la 1c 1 b 一la 一1c 1 ba c bac 若过程是正常返的 令i i l i m p 弘 j n v x f n 其中 k 0 1 j m 为了适应q 的分块矩阵的形式 将稳态概率向量写为 1 i n o n 1 i 1 2 其中i i i 兀舢i i 七2 1 i b k 0 这里我们不加证明 的给出关于拟生灭过程一些有用的定理 定理3 3 过程q 正常返 当且仅当矩阵方程尺2 b 删 c 0 的最d 二l i e 负解r 的谱半径印 1 并且线形齐次方程组n a 彻 0 有正解 定理3 4 若矩阵g 么 b c 所对应的稳态概率向量为 率矩阵尺满足 1 4 g 色 2 一 c 曰 g 如 0 1 2 c a b 加夙 江苏大学硕士研究生学位论文 印僻 h c e n 满足n g 0 h p 1 定理3 5 当过程正常返时 稳态概率可以用矩阵几何解表示为h r 七 k 0 1 2 其中n o 是方程组 o 衄 0 的解 且满足兀o i r e 1 二十世纪7 0 年代以来 n e u t s 1 9 8 1 等系统地发展了处理这种特殊q b d 的矩 阵分析方法 通过求率矩阵来求解 对于一般的q b d 尚未建立起平行于经典生 灭过程的理论和处理方法 3 5m a r k o v 环境 1 钔 2 在运行过程中基本参数也随机变化的系统 称为随机环境下的模型 在数学上 通常用一个m a r k o v 更新过程描述随机环境 一个m a r k o v 更新过 程是一个二元序列 以 邑 忍 吩 l 表示第n 次转移后达到的环境状态 取值于 有限环境状态集 1 2 廖 x 是环境过程在一个状态上的逗留时间 过 程在所有转移时刻上是无后效的 m a r k o v 更新过程由初始状态分布和转移率函数 矩阵q 力唯一决定 q 力是m 阶方阵 它的 k 元素是 瓯 力 u 州 i l 邑 l 力i j 七 1 k h m x 0 q o 是一个随机阵 它是m a r k o v 更新过程 u 邑 刀 凹的嵌入m a r k o v 链的 u 捍 0 转移概率矩阵 在实际应用中主要使用m a r k o v 环境 它由一个m 状态的m a r k o v 过程来刻画 一个周期循环的随机环境可描述如下 设有 个p h 分布 互 功 i o 分别有 m f 阶p h 表示 互 磁e 1 扛1 2 构造具有下列生成元的m a r k o v 过程 q 这个m a r k o v 过程刻画了一个r 状态的循环随机环境 在每一个状态上的逗留 时间服从相应的p h 分布 这就是说 一个p h 分布位相的内部转移 不改变环境 状态 只有不同p h 分布的位相集之间的转移 才导致环境状态的变化 这个环境 过程的循环时间是r 个服从p h 分布的随机变量之和 从而也是一个随机变量 z o o 轴乃 0 0 0 o勉 o o 叩上 趣乏 o o z 五o o 如 江苏大学硕士研究生学位论文 第四章基于随机丢弃机制的丢失重传排队模型 4 1引言 从分组的角度来看 缓存管理也是一种分组丢弃机制 分组丢弃策略主要由 以下几类f 6 尾部丢弃和头部丢弃策略 门限丢弃策略 随机丢弃策略 非参数控 制丢弃策略 选择性丢弃策略 传统的队列管理策略是t d t a i ld r 6 p 它只有当缓存队列满时才对新到达的 分组进行丢弃 但这种算法有两个明显的不足 一是对缓存的死锁 另一个是持 续的满队列状态 为解决这些不足 一些主动队列管理a q m a c t i v eq u e u e m a n a g e m e n t 策略位妇口习髓3 1 相继提出 这些策略通过控制排队队长来减小端到端的延 时 通过丢弃分组来避免死锁现象 a q m 策略中最常见的缓存管理策略就是r e d 窿订 r a n d o me a r l yd e t e c t i o n r e d 为队列管理增添了两种新机制 其一 不是等 队列全满后再丢弃到来的分组 而是利用概率判定机制事先丢掉部分分组来预防 可能发生的拥塞 其二 通过平均队列而非即时队列调整分组丢弃概率 尽可能 地吸收部分短暂的突发流量 利用排队论的方法能很好评价交换机缓存设备的性能 以往对于这种具有丢 弃机制的排队系统 大量文献做了研究 例如 2 4 2 5 3 2 6 但都是在系统无等 待位置时才对新到达分组丢弃 因此不具备r d r a n d o m l yd r o p 机制 文献 2 7 利 用输入稀疏化的方法 讨论了基于r d 机制的g i m 1 k 的排队系统 并给出了该 系统的一些重要性能评价指标 然而 他们都没有考虑在实际网络中分组随机丢 弃后可能重传的问题 也有文献 2 8 2 9 3 0 研究了具有重试的排队系统 但都 是在队列满时考虑丢弃分组的重试 都不具备r d 机制 因此也只适用于对基于t d 策略的重传问题做建模分析 到目前 未见到文献讨论过随机丢弃分组后考虑重传的排队系统 但实际中 分组的重传常很频繁的在通信网络中发生 在排队论中 重试排队系统的特征就 是当顾客到达服务台时发现服务台忙 则必须离开服务区域进入重试区域 o r b i t 经过一段时间后再次要求服务 在具有经典的重试策略排队系统中 每个重试顾客重试时间间隔相互独立 且服从负指数分布 重试排队实际上是重 1 6 江苏大学硕士研究生学位论文 试顾客利用经典排队论中服务台空闲 间隙 请求服务 近年来 重试排队系统已 经在计算机通信网络和电话交换系统等许多实际模型中获得了广泛的应用 c h o i b d 在文献 3 l 3 2 中分别讨论了其在通信网络a l o h a 和c s m a s c d 协议中的应用 现实网络中分组的重传实际上是一种特殊的重试 考虑重试的排队模型更适合于 对通信网络中分组丢弃现象的研究 本章就基于r d 机制建立了一种考虑分组丢弃 后以一定概率重传的排队模型 利用矩阵几何解方法给出了系统的一些重要性能 指标 并与基于r d 机制不考虑重传的系统做比较 考察了重传对系统性能的影响 4 2r d 机制 具有l i d 机制的排队系统 不论缓存队列填满与否 系统都会以一定的概率随 机丢弃到达的分组 设缓存容量为k 对缓存队列设置n 1 个门限 k l k k n 小其中0 勤 岛 幺 玉毯当缓存中分组的队长n 满足k 一 n k 时 新到达的分组则以概率呸丢弃 而以概率旷卜绣进入缓存排队 以下为了计算方 便 本文的r d 机制设计如下 取俨丘即缓存中分组队长脚 j 形五 膨时 新 到达的分组以概率纽丢弃 寻找排队系统性能评价指标的关键在于求解该系统平稳状态下的队长分 布 基于r d 机制 以下我们来讨论不考虑分组重传和考虑分组重传两种情形下排 队系统的稳态队长概率分布 4 3 基于r d 机制的m m 1 k 排队系统