重庆大学研究生讲义 通信网络中的排队论基础 大 t929 G U 江禹生编著 O一八年九月
I 重庆大学研究生讲义 通信网络中的排队论基础 江禹生 编著 二 O 一八年九月
目录 第1章排队论概论 1.1排队系统概述 1.1.1排队论发展历程 1.1.2排队现象 1.1.3排队系统的组成和特征 1.14经典排队系统的符号表示 1.1.5排队问题的求解 12几个重要的概率分布 121定长分布 122负指数分布 123爱尔郎( Erlang)分布 124泊松( Poisson)分布 13泊松过程 14单服务者负指数分布排队系统的分析 141系统中有个i顾客的概率 142系统的运行指标 15 Little公式及其直观意义 15.1 Little公式直观意义 152 Little公式的证明 16利用因数P的定义及其物理意义
II 目 录 第 1 章 排队论概论 1.1 排队系统概述 1.1.1 排队论发展历程 1.1.2 排队现象 1.1.3 排队系统的组成和特征 1.1.4 经典排队系统的符号表示 1.1.5 排队问题的求解 1.2 几个重要的概率分布 1.2.1 定长分布 1.2.2 负指数分布 1.2.3 爱尔郎（Erlang）分布 1.2.4 泊松（Poisson）分布 1.3 泊松过程 1.4 单服务者负指数分布排队系统的分析 1.4.1 系统中有个i 顾客的概率 1.4.2 系统的运行指标 1.5 Little 公式及其直观意义 1.5.1 Little 公式直观意义 1.5.2 Little 公式的证明 1.6 利用因数 的定义及其物理意义
第1章排队论概论 1.1排队系统概述 1.1.1排队论发展历程 排队论(又称随机服务系统理论)是研究系统由于随机因素的干扰而出现排队(或 拥塞)现象的规律性的一门学科,它适用于一切服务系统,包括通信系统、交通与运输 系统、生产与服务系统、管理运筹系统和计算机系统等。可以说,凡是出现拥塞现象的 系统,都属随机服务系统。 排队论发展过程中产生过以下标志性事件: ①排队论源于电话服务理论的研究,1909年丹麦电话工程师 A.K. Erlang开创性论 文“概率论和电话通话”的发表,标志排队论的诞生。 ②20世纪30年代法国的 E Pollaczek、苏联的 A Khinchine提出了有名的P-K ( Pollaczek Khinchin,朴拉切克一辛欣)均值公式,二人被称为排队论的先驱 ③第二次世界大战后,英国的 D.C Kendall系统地阐述排队问题,并利用嵌入马尔 可夫链推动了排队论的进一步发展(1951年,1953年)。 ④排队论与存量理论、水库问题联系始于20世纪50年代末到60年代初。 ⑤20世纪60年代,近似法、排队上下限的研究成果开始应用于生产线、交通线 ⑥20世纪T0年代,用于计算机网络及通信,在排队研究中模拟技术继50年代后 再度成为注意对象 ⑦20世纪80、90年代,排队论被进一步用于网络性能分析(如端到端流控等)。 ⑧计算机网络中排队分析的有效性依赖于数据通信量的泊松性质,这是排队分析 的基础。 归纳起来,排队论的发展基本上经历了三个阶段。在第二次世界大战以前,其研究 多侧重于电话和远距离通信方面,这阶段发展较缓慢。第二次世界大战以后,由于排队 论渗透到军事、经济、生产与服务、管理等多种部门,于是迎来了理论和应用的较大发 展,使之成为运筹学和管理科学的一个热门分支。上个世纪70年代以来,随着计算机 的不断更新和发展,通信网的建立和完善,信息科学、生命科学及控制理论的蓬勃发展 均涉及到最优设计与最佳服务问题,从而使排队理论与应用获得质和量上飞速的发展。 计算机通信网目前大都采用分组交换,数据信息是以分组为单位传送的,各分组到 438
438 第 1 章 排队论概论 1.1 排队系统概述 1.1.1 排队论发展历程 排队论（又称随机服务系统理论）是研究系统由于随机因素的干扰而出现排队（或 拥塞）现象的规律性的一门学科，它适用于一切服务系统，包括通信系统、交通与运输 系统、生产与服务系统、管理运筹系统和计算机系统等。可以说，凡是出现拥塞现象的 系统，都属随机服务系统。 排队论发展过程中产生过以下标志性事件： ① 排队论源于电话服务理论的研究，1909 年丹麦电话工程师 A.K.Erlang 开创性论 文“概率论和电话通话”的发表，标志排队论的诞生。 ② 20 世纪 30 年代法国的 F.Pollaczek、苏联的 A.Khinchine 提出了有名的 P K （Pollaczek-Khinchin，朴拉切克－辛欣）均值公式，二人被称为排队论的先驱。 ③ 第二次世界大战后，英国的 D.C.Kendall 系统地阐述排队问题，并利用嵌入马尔 可夫链推动了排队论的进一步发展（1951 年，1953 年）。 ④ 排队论与存量理论、水库问题联系始于 20 世纪 50 年代末到 60 年代初。 ⑤ 20 世纪 60 年代，近似法、排队上下限的研究成果开始应用于生产线、交通线。 ⑥ 20 世纪 70 年代，用于计算机网络及通信，在排队研究中模拟技术继 50 年代后 再度成为注意对象。 ⑦ 20 世纪 80、90 年代，排队论被进一步用于网络性能分析（如端到端流控等）。 ⑧ 计算机网络中排队分析的有效性依赖于数据通信量的泊松性质，这是排队分析 的基础。 归纳起来，排队论的发展基本上经历了三个阶段。在第二次世界大战以前，其研究 多侧重于电话和远距离通信方面，这阶段发展较缓慢。第二次世界大战以后，由于排队 论渗透到军事、经济、生产与服务、管理等多种部门，于是迎来了理论和应用的较大发 展，使之成为运筹学和管理科学的一个热门分支。上个世纪 70 年代以来，随着计算机 的不断更新和发展，通信网的建立和完善，信息科学、生命科学及控制理论的蓬勃发展 均涉及到最优设计与最佳服务问题，从而使排队理论与应用获得质和量上飞速的发展。 计算机通信网目前大都采用分组交换，数据信息是以分组为单位传送的，各分组到
达网络节点(即分组交换机)进行存储转发的过程中,当多个分组要去往同一输出链路, 那么就要进行排队。计算机通信网就是一个大的排队系统,网内分组的到达是随机的、 具有突发性的。我们可借助于排队论分析计算机通信网内分组的传输时延以及流量等问 题。所以说排队论广泛应用于计算机通信领域,是计算机通信网的基础理论之一。网络 排队模型是计算机网络设计、建模、性能分析和预测的有力工具。 1.1.2排队现象 排队是日常生活和工作中常见的现象。例如顾客到商店购买物品,当售货员较少 而顾客较多时就会岀现排队。车站和码头交通枢纽的车船堵塞和疏导、故障机器的停机 待修、水库的存储调节等等都是有形或无形的排队现象。此时要求服务的数量超过服务 机构(服务者)的容量,也就是说,到达的顾客不能立即得到服务,因而出现了排队现 象。由于顾客到达和服务时间的随机性,可以说排队现象几乎是不可避免的。如果增添 服务设备,就要增加投资或发生空闲浪费;如果服务设备太少,排队现象就会严重,对 顾客个人和对社会都会带来不利影响。 众所周知,一个电话系统的功能是按照用户(或顾客)需求在主叫用户与被叫用 户之间提供通信路由(或称通信信道,也称话路)。如果在每一对电话用户之间提供 条固定的通信路由,由于其成本接近天文数字,而不可能办到。为了解决这个问题,必 须建立和保持通话的路由是“公用”的,即需要时选用,话毕时释放。这就隐含着这样 一种可能性:由于某一时刻恰好没有空闲的路由可选用,这个呼叫就不能建立。亦即, 不可能真正做到随时都能“按需”实现任意双方用户之间的通信要求,存在着(系统的) “供”和(顾客的或用户的)“需”之间的矛盾。类似的问题不仅仅只限于电话系统, 在许多系统的设计中都存在类似的矛盾。表1.列举了一些例子说明现实中形形色色的 排队系统。 表1.1排队系统举例 系统 顾客 要求服务内容 服务机构 修理厂 不能运转的机器 修理 修理技工 零配件库房 修理技工 领取修配零件发放修配零件的管理员 电话 呼叫 通话 交换机 通信网 信息包 传输 信道 计算机网络 存储转发 分组交换机 439
439 达网络节点（即分组交换机）进行存储转发的过程中，当多个分组要去往同一输出链路， 那么就要进行排队。计算机通信网就是一个大的排队系统，网内分组的到达是随机的、 具有突发性的。我们可借助于排队论分析计算机通信网内分组的传输时延以及流量等问 题。所以说排队论广泛应用于计算机通信领域，是计算机通信网的基础理论之一。网络 排队模型是计算机网络设计、建模、性能分析和预测的有力工具。 1.1.2 排队现象 排队是日常生活和工作中常见的现象。例如顾客到商店购买物品，当售货员较少 而顾客较多时就会出现排队。车站和码头交通枢纽的车船堵塞和疏导、故障机器的停机 待修、水库的存储调节等等都是有形或无形的排队现象。此时要求服务的数量超过服务 机构（服务者）的容量，也就是说，到达的顾客不能立即得到服务，因而出现了排队现 象。由于顾客到达和服务时间的随机性，可以说排队现象几乎是不可避免的。如果增添 服务设备，就要增加投资或发生空闲浪费；如果服务设备太少，排队现象就会严重，对 顾客个人和对社会都会带来不利影响。 众所周知，一个电话系统的功能是按照用户（或顾客）需求在主叫用户与被叫用 户之间提供通信路由（或称通信信道，也称话路）。如果在每一对电话用户之间提供一 条固定的通信路由，由于其成本接近天文数字，而不可能办到。为了解决这个问题，必 须建立和保持通话的路由是“公用”的，即需要时选用，话毕时释放。这就隐含着这样 一种可能性：由于某一时刻恰好没有空闲的路由可选用，这个呼叫就不能建立。亦即， 不可能真正做到随时都能“按需”实现任意双方用户之间的通信要求，存在着（系统的） “供”和（顾客的或用户的）“需”之间的矛盾。类似的问题不仅仅只限于电话系统， 在许多系统的设计中都存在类似的矛盾。表 1.1 列举了一些例子说明现实中形形色色的 排队系统。 表 1.1 排队系统举例 系统 顾客 要求服务内容 服务机构 修理厂 不能运转的机器 修理 修理技工 零配件库房 修理技工 领取修配零件 发放修配零件的管理员 电话 呼叫 通话 交换机 通信网 信息包 传输 信道 计算机网络 分组 存储转发 分组交换机
机场 飞机 起飞降落 跑道 医院 病人 诊断或动手术 医生(或包括手术台) 水库 上游河水进入水库 放水,调整水位 水闸管理员 这些系统的共同特征是:顾客的到达以及要求服务的持续时间一般是随机发生且难 以预测的。 排队现象有的是以有形的形式出现,例如上下班坐公共汽车等,这种排队称为有形 排队。而有的是以无形的形式出现,例如有许多顾客同时打电话到订购处订购车票,其 中一个顾客正在通话时,其他顾客就不得不在各自的电话机旁等待,他们可能分散在各 个地方,但却形成一个无形的队列等待通话,这种排队现象称为无形排队。 排队系统也称为“随机服务系统”,排队论则相应地称为“随机服务系统理论”,它 是为解决上述问题而发展起来的。排队论是研究拥挤现象的一门学科。 1.1.3排队系统的组成和特征 排队过程的一般模型如图1.1所示。各个顾客由顾客源出发,到达服务机构(服务 者)前排队等候接受服务,服务完了后就离开。排队结构指队列的数目和排列方式,排 队规则和服务规则是说明顾客在排队系统中按怎样的规则、次序接受服务的。排队系统 就是指图1.1中虚线所包含的部分 顾客源到排队结构服务机构 顾客离去 输出 排队规则 服务规则 排队系统 图1.1排队过程的一般模型 现实中的排队现象是多种多样的,对上面所说的“顾客”和“服务者”,要作广义 地理解。它可以是人,也可以是非生物;队列可以是具体地排列,也可以是无形的(例 如向电话交换要求通话的呼叫);顾客可以走向服务机构,也可以相反(如送货上门)。 一般的排队系统都有三个基本组成部分:输入过程、排队规则、服务机构。现在分 别说明各部分的特征。 1、输入过程 输入过程是描述顾客来源及顾客是按怎样的规律到达排队系统,可能有下列各种不
440 机场 飞机 起飞降落 跑道 医院 病人 诊断或动手术 医生（或包括手术台） 水库 上游河水进入水库 放水，调整水位 水闸管理员 这些系统的共同特征是：顾客的到达以及要求服务的持续时间一般是随机发生且难 以预测的。 排队现象有的是以有形的形式出现，例如上下班坐公共汽车等，这种排队称为有形 排队。而有的是以无形的形式出现，例如有许多顾客同时打电话到订购处订购车票，其 中一个顾客正在通话时，其他顾客就不得不在各自的电话机旁等待，他们可能分散在各 个地方，但却形成一个无形的队列等待通话，这种排队现象称为无形排队。 排队系统也称为“随机服务系统”，排队论则相应地称为“随机服务系统理论”，它 是为解决上述问题而发展起来的。排队论是研究拥挤现象的一门学科。 1.1.3 排队系统的组成和特征 排队过程的一般模型如图 1.1 所示。各个顾客由顾客源出发，到达服务机构（服务 者）前排队等候接受服务，服务完了后就离开。排队结构指队列的数目和排列方式，排 队规则和服务规则是说明顾客在排队系统中按怎样的规则、次序接受服务的。排队系统 就是指图 1.1 中虚线所包含的部分。 排队结构 服务机构 顾客到达 输入 顾客离去 输出 排队规则 服务规则 顾客源 排队系统 图 1.1 排队过程的一般模型 现实中的排队现象是多种多样的，对上面所说的“顾客”和“服务者”，要作广义 地理解。它可以是人，也可以是非生物；队列可以是具体地排列，也可以是无形的（例 如向电话交换要求通话的呼叫）；顾客可以走向服务机构，也可以相反（如送货上门）。 一般的排队系统都有三个基本组成部分：输入过程、排队规则、服务机构。现在分 别说明各部分的特征。 1、输入过程 输入过程是描述顾客来源及顾客是按怎样的规律到达排队系统，可能有下列各种不