排队论与计算机系统-网络.ppt

Introduction排队论与计算机系统 网络性能评价 计算机系统性能评价主要目的 1 选择在众多的系统中选择一个最需要的系统 计算机 网络 其他 或在众多的方案中选择一个较好的方案 即在一定的价格范围内选择性能最好的系统 或方案 达到较好的性能 价格比 2 改进对已有系统的性能缺陷进行改进 以便提高其运行效率 3 设计对未来设计的系统进行性能预测 在性能成本方面实现最佳设计或配置 性能参数 1可靠性或可利用性系统能正常工作的时间 其指标可以是能够持续工作的时间长度 如平均无故障时间 也可以是在一段时间内 能正常工作的时间所占的百分比 2处理能力或效率l吞吐率 系统在单位时间内能处理正常作业的个数 l响应的时间 系统得到输入到给出输出之间的时间 l利用率 在给定的时间区间中 各种部件 包括硬设备和软系统 被使用的时间与整个时间之比 l丢失率 或阻塞率 信息传输 用户呼叫 丢失量与信息传输 用户呼叫 总量之比 性能评价方法 1 计算机和网络系统性能评价常用的有以下三种方法 1测量方法 measurement l测量 通过一定的测量设备或一定的测量程序直接从系统测得各项性能指标或与之密切相关的量 l运算 求出相应的性能指标 优缺点 l最直接 最基本的方法 其它方法也要依赖于测量的量l测量方案和测量手段是测量方法的关键l比较费时间l适用于已经存在并运行的系统 性能评价方法 2 2仿真 simulation 模拟 emulation 方法用程序动态地模拟系统及其负载 l描述 模拟语言建立系统模型 l执行 事件或时间驱动系统模型 l统计分析 性能参数 优缺点l详细地刻划系统l较精确的性能指标l费时 费用较高 性能评价方法 3 3分析方法 analysis 用数学模型工具的理论与方法描述性能与系统 负载之间的关系 l StochasticProcessAlgebras 随机过程代数l StochasticPetriNets 随机Petri网l QueueingTheory 排队论优缺点l模型进行简化和假设l刻划系统的详细程度较低l与实际性能指标有差距l理论基础强 刻划各种因素之间的关系l省时 费用也较低本课程的主要内容 排队论及其模型重点讲述排队模型 排队网络模型及在计算机中的应用本课程的预修课程为 概率论和随机过程 计算机体系结构 Introduction随机过程 排队论初步 内容提要 两个重要分布 指数分布 Poisson分布随机过程简介排队论初步 ExponentialDistribution AcontinuousR V Xfollowstheexponentialdistributionwithparameter ifitspdfis Probabilitydistributionfunction Usuallyusedformodelingservicetime ExponentialDistribution contd MemorylessProperty 无后效性 不管多长时间 t 已经过去 逗留时间的概率分布与下一个事件的概率相同PasthistoryhasnoinfluenceonthefutureProof Exponential theonlycontinuousdistributionwiththememorylessproperty exp x t exp x exp t Example problem3 5 指数分布例题 习题3 5 3 5记性不好的教授在同一时间约了两个学生 应分别约见 第一个学生准时到达 第二个学生迟到5分钟 假定和每个学生谈话的时间为指数分布的随机时间 均值为30分钟 试计算整个谈话的平均 expected 时间 习题3 5 Contd 解 如果和第一个学生的谈话在5分钟内没结束 剩余的谈话时间仍为均值30分钟的指数分布时间 如果5分钟内谈完了则和他剩余的谈话时间为0 所以和第一个学生剩余谈话时间平均为 P X 5 30 P X 5 0 P X 5 30 所以和第一个学生谈话的平均时间为 5 P X 5 30 30 38整个谈话的平均 expected 时间为60 38 习题3 6 假设某一银行有4个服务窗口 某人进到银行时 看到有4个客户在4个窗口接受服务 而且没有其它客户等待 假定每个客户的服务时间都是独立的相同的指数分布 平均1分钟 1 1 这个人最后离开银行的概率是多少 2 这个人平均在银行里停留多长时间 习题3 6 Contd 1 这个人最后离开银行的概率是多少 当这4个人中有一个人离开时该人接受服务 这时其它3人的剩余服务时间仍有相同的指数分布 从对称性可知 这4个人中任何一个最后离开的概率都是1 4 2 这个人平均在银行里停留多长时间 这个人从进入银行到接受服务的时间等于min X1 X2 X3 X4 X1 X2 X3 X4为正在接受服务的4个客户的剩余服务时间 都是指数分布的随机变量 随机变量min X1 X2 X3 X4 有以下分布 P min X1 X2 X3 X4 x exp 4 x 仍为指数分布 均值 1 4 0 25分钟 所以这个人平均在银行停留的时间为1 25分钟 作业 习题3 6 c 3 8 a Trytoprove PoissonDistribution PoissonDistribution contd SumofPoissonRandomVariables SumofPoissonRandomVariables cont SamplingaPoissonVariable SamplingaPoissonVariable contd Howcome PoissonApproximationtoBinomial SmallIntervalProbabilities 内容提要 两个重要分布 指数分布 Poisson分布随机过程简介排队论初步 随机过程 随机变量X 分布函数不变如果随机变量的分布函数随时间变化 对时间集合T 得到一组随机变量 称之为随机过程如果时间集合T离散 如T 0 1 2 称为离散时间的随机过程 Xn n T 如果时间集合T连续 称为连续时间的随机过程 X t t T 如果Xn或者X t 离散 连续 称这个随机过程离散 连续 例 某路由器的IP包t时刻进入缓存等待转发 等待时间 W t t 0 是一个连续时间的连续随机过程从时间0到t到达路由器的IP包个数 N t t 0 是一个连续时间的离散随机过程Xn表示一周7天中某一天某计算机启动的进程数 n 1 2 3 4 5 6 7 Xn 是一个离散时间的离散随机过程 Xn表示一周7天中某一天某计算机的工作时间 n 1 2 3 4 5 6 7 Xn 是一个离散时间的连续随机变量 计数过程 令N t 表示在时间段 0 t 内的某种事件发生的次数 N t 称为该事件的计数过程 计数过程是一种随机过程 事件 数据包到达路由器 顾客到达商店性质 N 0 0N t 非负如果s t N s N t N t N s 是时间 s t 内发生的事件个数 例 Bernoulli过程X1 X2 是独立同分布的Bernoulli变量 成功的概率为p 令Sn X1 X2 Xn 即前n次伯努力实验的成功次数 Sn 是一个计数过程 被称为伯努力过程 Sn的分布是二项分布 Poisson过程 一个计数过程 N t t 0 如果满足以下条件 则被称为参数 的泊松过程独立增量过程 即独立时间段上的事件发生的个数是独立的 平稳过程 在任意一段时间内发生的事件个数的分布是不变的 在一小段时间h内发生一个事件的概率为 h o h 在一小段时间h内发生多于一个事件的概率为o h 被称为泊松过程的速率 定理 N t t 0 是一个速率为 的泊松过程 Y表示一段时间t 0内事件发生的个数 则证明 定义 取h 0代入初始条件 得到 参数为 t的泊松分布 对时间t h时n个事件发生的情况Pn t h 三种情况时间t时已经发生了n个事件 时间t时发生了n 1个事件 t t h 这段时间发生了1个事件时间t时发生了n k个事件 t t h 这段时间发生了k个事件 k 1取h 0 初始条件 迭代求解得到 定理 N t t 0 是一个速率为 的泊松过程 令0s N tn 1 s N tn 1 0 所以 P n s P N tn 1 s N tn 1 0 P N s 0 e s 指数分布 定理 N t t 0 是一个计数过程 事件发生间隔记为 n 如果 n 为独立同分布的随机变量 且服从参数 的指数分布 则N t 是一个泊松过程 证明 略 Merging SplittingPoissonProcesses ModelingArrivalStatistics PoissonprocesswidelyusedtomodelpacketarrivalsinnumerousnetworkingproblemsJustification providesagoodmodelforaggregatetrafficofalargenumberof independent usersntrafficstreams withindependentidenticallydistributed iid interarrivaltimeswithPDFF s notnecessarilyexponentialArrivalrateofeachstream nAsn combinedstreamcanbeapproximatedbyPoissonundermildconditionsonF s e g F 0 0 F 0 0MostimportantreasonforPoissonassumption Analytictractabilityofqueueingmodels 总结泊松过程从时间0到时间t发生的事件个数是参数 t的泊松分布事件发生间隔 n 是指数分布 泊松过程 36 例 某商店 假设顾客按照以下比例单个或者成双到达 f 1 p f 2 1 p 客户到达批次间隔服从以下分布证明时间 0 t 内累计到达的客户数量服从分布如果总共有n个客户 假设其中发生k次成对到达 n 2k次单个到达 分别可以用速率为 1 p 和p 的泊松过程表示 k次成对到达 n 2k次单个到达 k的取值范围从0到 例 给定两个泊松过程 事件发生速率分别为 1 2 从时间t 0开始 问首先观察到第一个过程事件发生的概率 假定过程1的第一个事件发生的时间是t1 过程2的第一个事件发生的时间是t2 t1和t2是参数为 1和 2的指数分布 内容提要 两个重要分布 指数分布 Poisson分布随机过程简介排队论初步 排队问题 排队随处可见顾客在超市收银柜台排队飞机在机场排队等待起飞进程在操作系统排队等待调度 排队的原因 由于服务需求大于服务能力规范用语客户 Customer 请求并接受服务者 例如顾客 飞机 进程 等等服务器 Server 提供服务的设施 例如收银员 机场跑道 CPU 等等 Kleinrock Westudythephenomenaofstanding waiting andserving andwecallthisstudyQueueingTheory Anysysteminwhicharrivalsplacedemandsuponafinitecapacityresourcemaybetermedaqueueingsystem Leonard KleinrockisDistinguishedProfessorofComputerScienceatUCLA Knownasa FatheroftheInternet hedevelopedthemathematicaltheoryofpacketnetworks thetechnologyunderpinningtheInternet whileagraduatestudentatMIT 他在其博士论文中最早用排队论证明了分组交换网络的优越性 1961 并在1969年12月 参与了美国四所大学使用接口消息处理器 IMP 建立起阿帕网 ARPANet LeonardKleinrock关于排队的定义 Book Queueingsystems ComputerapplicationsbyLeonardKleinrock publishedbyJohnWiley sons 1975 一般性定义 排队论是专门研究带有随机因素 产生拥挤现象的优化理论 排队系统也称为随机服务系统 Incomputerscience queueingtheoryisthestudyofqueuesasatechniqueformanagingprocessesandobjectsinacomputer Aqueuecanbestudiedintermsof thesourceofeachqueueditem howfrequentlyitemsarriveonthequeue howlongtheycanorshouldwait whethersomeitemsshouldjumpaheadinthequeue howmultiplequeuesmightbeformedandmanaged therulesbywhichitemsareenqueuedanddequeued Queueingtheoryforcomputerscience Queueingtheoryforstudyingnetworks ViewnetworkascollectionsofqueuesFIFOdata structuresQueuingtheoryprovidesprobabilisticanalysisofthesequeuesExamples Averagelength buffer AveragewaitingtimeProbabilitythatqueueisatacertainlengthProbabilitythatapacketwillbelost SourcesofNetworkDelay ProcessingDelayAssumeprocessingpowerisnotaconstraintQueueingDelayTimebufferedwaitingfortransmissionTransmissionDelayPropagationDelayTimespendonthelink transmissionofelectricalsignalIndependentoftrafficcarriedbythelinkFocus Queueing TransmissionDelay 排队系统六要素 一个排队系统包括六要素客户到达过程服务过程服务器数量系统容量顾客源数量排队规则 排队系统六要素 客户到达过程耐心客户 非耐心客户 中途离开 客户到达时间间隔可以看作一个随机变量用一个随机过程描述客户到达模式例如 可以用一个泊松过程表示客户到达 到达间隔服从指数分布平稳 非平稳 stationary 到达模式例如 突发大批到达客户 服务过程状态无关 状态相关服务时间可以看作一个随机变量例如 可以用一个指数分布描述服务时间平稳 非平稳 stationary 服务时间例如 服务器可以学习 提高服务效率 服务器数量单个 多个服务器多服务器多队列 多服务器单队列 多服务器多队列 多服务器单队列 系统容量客户不能立即获得服务时选择等待 离开有限 无限个等待位系统的顾客源数量有限无限排队规则FCFS LCFS 优先级抢占优先 Preemptive 非抢占优先 Nonpreemptive 52 排队系统命名法则 Kendallnotation 一个排队系统表示为A B C X Y ZA 客户到达模式B 服务模式C 服务器数量X 排队系统的最大容量当队列缓冲区容量无限时可省略Y 顾客源数量当顾客源数量无限时可省略Z 排队规则缺省值是FCFS 53 例 M D 2 FCFS 客户到达符合泊松过程 固定服务时间 2个服务器 系统容量无限 First come first serve通常假定系统容量无穷 顾客源数量无穷和FCFS 因此常用A B C描述一个排队系统比如 M M 1 M M c M M m m M G 1 D 等等 Distributions M standsfor Markovian Poisson implyingexponentialdistributionforservicetimesorinter arrivaltimes D Deterministic e g fixedconstant Ek ErlangwithparameterkHk Hyperexponentialwithparam kG General anything Thepdf x 0 todifferentsymbols M D EK HK G b x isarbitrary 服务规则 FCFS 先来先服务 LCFS 后来先服务 RSS 随机选择服务 PR 优先级服务GD 一般规约服务 即通用规约服务 Ba 集体 批量 服务 57 排队系统常见的性能指标 客户等待时间客户在队列中等待的时间 Wq 客户在整个排队系统中消耗的时间 W 队列等待时间 服务时间客户在排队系统中的累积程度等待队列中的客户数目 Nq 整个排队系统中的客户数目 N 等待队列客户数目 正在接受服务的客户数目 空闲服务器服务器空闲的时间比例系统设计目标 提高服务器利用率 缩短客户等待时间等等 目标往往是相互矛盾的排队论中的假设 在排队分析中 最重要的一个假设是到达速率服从泊松分布 等效的说法是到达间隔时间服从指数分布 这又等价于说到达是随机的并彼此独立 我们几乎一直要作这一假定 没有它 大部分的排队分析是不可能的 在这个假定的条件下 我们会发现仅仅知道到达速率和服务时间的均值和标准差就可以得到许多有用的结果 基本排队关系 Little定理 Little公式是排队论中的通用公式Little s定理可以对排队系统进行确定性分析 排队系统是随机过程 但它的一次实现 运行 是确定的过程 Ergodicity 时间平均 随机平均 Little s定理中时间平均换成处于稳态的随机过程的数学期望值仍成立 Little sTheorem customerarrivalrateN averagenumberofcustomersinsystemT averagedelaypercustomerinsystemLittle sTheorem Systeminsteady stateN T Thelong termaveragenumberofcustomersinastablesystemN isequaltothelong termaveragearrivalrate multipliedbythelong termaveragetimeacustomerspendsinthesystem T Little sTheorem contd GeneralityofLittle stheorem Little sLawisaprettygeneralresultItdoesnotdependonthearrivalprocessdistributionItdoesnotdependontheserviceprocessdistributionItdoesnotdependonthenumberofserversandbuffersinthesystem Appliestoanysysteminequilibrium aslongasnothinginblackboxiscreatingordestroyingtasks CountingProcessesofaQueue N t numberofcustomersinsystemattimet t numberofcustomerarrivalstilltimetb t numberofcustomerdeparturestilltimetTi timespentinsystembytheithcustomer TimeAverages Timeaverageoverinterval 0 t Steadystatetimeaverages Little stheoremN TAppliestoanyqueueingsystemprovidedthat LimitsT anddexist and dAboveassumptions stablesystemWegiveasimplegraphicalproofunderasetofmorerestrictiveassumptions ProofofLittle sTheoremforFCFS Assumption N t 0 infinitelyoften ForanysuchtIflimitsNt N Tt T t exist Little sformulafollowsWewillrelaxthelastassumption N t 0 infinitelyoften FCFSsystem N 0 0 t andb t staircasegraphsN t t b t Shadedareabetweengraphs ProofofLittle sTheoremforFCFS cont Ingeneral evenifthequeueisnotemptyinfinitelyoften ResultfollowsassumingthelimitsTt T t anddt dexist and d ProofofLittle sTheoremwithoutFCFS AssumeD t isthesetofcustomerswhohavedepartedthesystembytimetAssumeisthesetofcustomerswhoarestillinthesystemattimetThedelayexperienceduptotimetbyacustomerstillinthesystemattimetist tiSo Therefore ProofofLittle sTheoremwithoutFCFS cont ProbabilisticFormofLittle sTheorem HaveconsideredasinglesamplefunctionforastochasticprocessNowwillfocusontheprobabilitiesofthevarioussamplefunctionsofastochasticprocessProbabilityofncustomersinsystemattimetExpectednumberofcustomersinsystematt ProbabilisticFormofLittle stheorem cont pn t E N t dependontandinitialdistributionatt 0Wewillconsidersystemsthatconvergetosteady statethereexistpnindependentofinitialdistributionExpectednumberofcustomersinsteady state stochasticaver Foranergodicprocess thetimeaverageofasamplefunctionisequaltothesteady stateexpectation withprobability1 ProbabilisticFormofLittle sTheorem cont Inprinciple wecanfindtheprobabilitydistributionofthedelayTiforcustomeri andfromthattheexpectedvalueE Ti whichconvergestosteady stateForanergodicsystemProbabilisticFormofLittle sFormula Arrivalratedefineas Timevs StochasticAverages Timeaverages Stochasticaverages forallsystemsofinterestinthiscourseItholdsifasinglesamplefunctionofthestochasticprocesscontainsallpossiblerealizationsoftheprocessatt CanbejustifiedonthebasisofgeneralpropertiesofMarkovchains 结论 Little s定理在任何调度规则下都成立Little s定理可用于系统的任一部分 只要该部分有客户到达和离开 Little s定理可用于系统的任一特定的客户类 Little定理应用举例 1 Little定理可用于排队系统的任何部分 2 队列内平均客户数和利用率 example3 1 设 是传输线内数据包的到达速率 设NQ为队列内等待传输的包数 W是数据包在队列中的平均等待时间 不包括传输时间 则按Little s定理 有NQ W设 正在传输线上传输的平均顾客数 为包的平均传输时间 则在排队系统中 通常称为系统的利用率 为server忙的时间 比例 1 为server闲的时间 比例 3 网络平均延迟 example3 2 设 1 n为网络的各个结点的packet到达率 N为网络内平均packet数 packet平均延迟设Ni Ti为结点i的traffc在网络中的平均packet数和平均延迟 将Little s定理用于节点i的traffic流有 4 包到达和服务时间固定时的传输线性能 例题3 3 ApacketarrivesatatransmissionlineeveryKsecondswiththefirstpacketarrivingattime0 Allpacketshaveequallengthandrequire Ksecondsfortransmissionwhere 1 TheprocessingandpropagationdelayperpacketisPsecondsCalculate theaveragetimeTapacketspendsinthesystemtheaveragenumberNinthesystem 性能分析 传输时间小于到达间隔 系统无排队延迟 又因传播延迟P为常数 每个包经历确定的端 端延迟T 接收到的包间隔等于发送方发出的包间隔K 见图3 3 应用Little s定理得到链路上的平均分组数N 假定K K P 2K 则系统中至多2个包 当N t 2时线路上有在途中的packet N t 1时仅有packet在传输 注意 1 从图中可以看到系统中顾客数随时间不收敛2 使用Little定理分析的结果是能得到随时间平均的顾客数 5 窗口流控系统 example3 4 网络使用窗口流控限制进入网络的流量以防止网络拥塞 假定每个session使用的窗口大小为W 则任何时刻网络中该session的packets不会多于W个 设 为每个session中packet的到达速率 T为packet平均延迟 根据Little s定理 packet的平均延迟T满足W T 假定网络出现拥塞 每个会话在单位时间内只能传输 个数据包 这时有W T 在拥塞情况下 增加窗口大小 仅可能导致包的平均延迟增加 不可能得到更大的吞吐率 6 有K个server的排队系统 example3 4 1 ConsideraqueueingsystemwithKservers andwithroomforatmostN Kcustomers eitheri