具有时间分阶段批量到达的Erlang丢失队列作为通信网络中交通控制的模型

抽象的

考虑了一个没有缓冲区但有客户批量到达的多服务器队列模型。与标准批到达不同，在标准批到达中，整个批到达系统在一个epoch，我们假设一批(流)的客户以指数分布的时间单独到达。服务时间呈指数分布。流动的到达是按照平稳泊松到达过程进行的。流动尺寸分布呈几何分布。可以同时进入系统的流量数量是在控制之下的。以固定的概率从一个已承认的流中失去任何客户，意味着流到达的终止。对任意流的停留时间和损失概率进行了分析。

1.介绍

排队系统有效地描述了许多通信网络的信道和服务器的运行，从丹麦数学家和工程师a . K. Erlang的开创性工作开始，在概率文献中受到了极大的关注。2009年将举行排队理论诞生100周年庆典。Erlang著名的客户损失概率公式 0 served as the basis for capacity planning and performance evaluation of telecommunication networks for an entire century. Sevastjanov proved in [1]，该损失公式适用于更一般的排队系统也在 [2-4.]，将Erlang模型的分析推广到具有(批马尔可夫到达过程)的系统。BMAP．

它被认为是[2-4.]，客户可以以随机大小的批次到达，并且标准假设，在一个批到达期，所有的批客户同时到达系统。然而，如今，它是许多通信网络的一个典型特征，知识产权特别是网络，客户批量到达，但批次客户的到货不是即时的。为了将标准批次与本文中考虑的批次区分开，后者是命名的流程。流量的第一个客户在流量到达时到达时，而其他客户在随机间隔期间单独地到达。流量尺寸是随机的，并且在流量到达时可能尚不知道先验。这种情况是典型的，例如，在模拟视频和多媒体信息的传输中。这种情况也在[5.关于替代数据包溢出路由的建模方案网络。在这种方案中，流代表一组必须在同一通道中按顺序路由的数据包。当数据包到达时，它被确定(例如，通过知识产权地址）如果数据包是先前跟踪的流程的一部分。如果数据包属于现有流，则标记数据包以进行传输。如果尚未跟踪流程并且缓冲区和频道容量仍然可用，则数据包录取到系统，并且流量计数增加。否则，流程在溢出链路（或被丢弃）上路由，并且在所考虑的信道中拒绝分组。完成后，跟踪的流量被清除。如果在特定时间间隔内未接收到属于该流的更多分组，则执行清除非活动流。流动的跟踪和清除由令牌机制执行。在物理上，令牌可以被解释为在流入院时代期间激活的特定计时器，并且在其他客户的时期从该流量到达时重新启动，并且如果特定的固定超时到期并且从此流中的新客户终止而终止到达。令牌的数量（定时器），它定义可以同时录取系统的最大流量，是一个非常重要的控制参数。 If this number is too small, the channel may be underutilized. If this number is too large, the channel may become congested. Many packets from admitted flows may be lost, and grade of service is poor. In addition, the delay and jitter of flows may inherently increase. So, the problem of defining the optimal number of tokens is practically important and nontrivial. In [5.]的业绩衡量味道路由方案知识产权通过计算机仿真评估网络。在 [6.]，并根据排队模型对该方案进行了描述。

此外，在关系数据库中还有一个类似的信息检索模型，除了CPU和磁盘内存之外，还必须提供一些额外的线程或连接，以启动用户的应用程序处理。在这种解释中，流意味着应用程序，而客户是将在该应用程序中处理的查询。

在 [6.]，一个具有有限缓冲区的多功能马尔可维亚排队模型，适用于替代数据包溢出路由方案的性能评估知识产权网络，以及其他现实世界系统的时间分布的客户到达流，被构建和分析研究。具体计算了系统中客户数量和流量的联合分布。该排队模型的一个非常重要的性能度量是流的逗留时间，从流到达的瞬间开始计算，直到该流的所有客户在系统中完成他们的到达和处理的瞬间。

在 [6.[仅针对单个服务器队列的情况计算用于流动静音时间分布的Laplace-Stieltjes变换。在本文中，我们计算了具有损失（没有缓冲区）的多功能队列的这种分布。考虑的模型比[6.]，在以下方面：假设在[6.从录取的流程中失去任何客户的损失不会影响系统的进一步行为。在本文中，我们假设具有固定概率，整个流程从该流程丢失客户后终止其到达。这种假设在各种情况下是现实的，例如，如果对用户丢失的语音或视频分组（以及语音或电影质量）的百分比变得不可接受，则连接的终止可以提前发生。

本文的其余部分组织如下。节2，对模型进行了描述。第一部分给出了系统中流量和用户数量的稳态联合分布3.．章节4.和5.包含本文的主要贡献:一个流逗留时间分布的分析，和一个可接受流的损失概率的表达式，由于一个特定的客户从该流的损失。本节给出了数值说明6.．

2.数学模型

我们考虑一个排队系统相同的服务器，其中服务器中的服务时间与参数呈指数分布系统没有缓冲。客户在流程中到达系统。流体到达系统时遵循一个稳定的泊松到达过程根据[5.]时，我们假设流量的进入是通过令牌．假设可用令牌的总数为数量可以看作是一个控制参数，可以解决各种优化问题。

如果在流到达时间点没有可用的令牌，或者所有服务器都很忙，则流将被拒绝。它将永远离开这个系统。如果可用令牌的数量是正的，并且至少有一个空闲服务器，则流被允许进入系统，可用令牌的数量减少1。该流进入后，该流的下一个用户可以在具有该参数的指数分布时间内到达系统．

如果在已承认流程的客户到达时存在空闲服务器，则该客户被允许进入系统。否则，客户将被拒绝。的概率这种拒绝不会影响系统未来的行为。但是有补充概率这种拒绝导致流到达的终止。但是，来自此流的客户(以前被允许进入系统)只有在服务器处理后才能离开系统。

流中的客户数量具有几何分布，具有参数也就是说，气流组成的概率顾客等于流程中的客户的平均数等于．

如果是指数分布的时间(参数)，因为流的前一个客户的到达已经过期，而新客户没有到达，这意味着流的到达已经完成。此流到达时获得的令牌将返回给可用令牌池。该流的客户(在令牌返回时留在系统中)必须由系统处理。当服务最后一个客户时，就认为流程在系统中的逗留时间已经结束。

它直观地显然，这种令人抵达机制通过令牌的限制是合理的。在拒绝某些流动的费用时，它可以降低损失客户的损失，从入院的流量，流动苏姆斯时间和抖动。它在建模现实世界系统方面很重要，因为接受信息单位的传输质量必须满足服务质量（QoS）的施加要求。

3.系统中流量和客户数量的平稳分布

让表示系统在epoch期间的客户总数然后让在纪元期间表示具有令牌的流量的流量这里，有这样的符号意味着假设来自集合的值．很明显，二维过程是一款有限的不可续定期连续时间马尔可夫链。

让是马尔可夫链的发电机块维度由强度组成马尔科夫链从国家转变到国家矩阵的对角线条目是消极的，以及进入的模量定义离开状态的总强度马尔可夫链。

这里，我们引入以下符号:

(我) ;(2) 也就是说，有对角元素的对角矩阵;（iii） 是单位矩阵，是一个零矩阵， 是尺寸的柱矢量由1 s组成，一个行向量是维数吗由0秒组成;（iv） （v） (vi)方阵相应大小的所有零条目都有，除了条目，这等于1.如果矩阵的大小未明确地指示为后缀，则假定其等于;（vii） 是矩阵的克罗内克积的符号，是克朗伯克特斯三角洲。

引理3.1。无穷小生成器马尔科夫链具有以下三个块对角线结构： 非零块在哪里是计算的

引理的证明包括对马尔可夫链的分析在无限时间间隔期间转换，并将相应的转换强度与矩阵块组合。

因为马尔科夫链是不可减少的，常规，具有有限的状态空间，存在静止概率：

我们可以应用一种有效且数值稳定的算法来计算马尔可夫链的这种概率，其生成子形式为(3.3.)，(在[4.])。

一旦稳定概率已经计算过，我们可以计算系统的各种性能测量。最重要的措施如下。

推论3.2。平均数量单位时间内系统处理的客户(吞吐量)由 概率抵达时的任意流量拒绝是计算的

4.分配苏尿时间

让表示被研究系统中任意流停留时间的分布函数，令表示其拉普拉斯- stieltjes变换(LST): 我们派生了一个表达通过非常强大的集体标记方法（额外事件的方法，灾难方法）;看 [7.那8.］．为此，我们解释变量作为特定虚拟固定泊松过程的强度灾难。所以，功能表示在任意（标记）流动的悬垂时间期间没有灾难到达的概率。

让表示突变从具有强度的平稳泊松过程中突变的概率在系统条件下，在系统条件下，将不会到达在系统条件下，在给定的即时，系统中处理的流量等于客户的数量等于来自标记流的客户数量等于函数的线性代数方程组由总概率定律推导，表示为: 在哪里

的证明(4．2)可以通过考虑这一点来澄清

(我) 是新流量的强度，获得系统的入场;(2) 是从标记流开始的客户服务完成强度;（iii） 是来自非标记流的客户的服务完成强度;（iv） 是来自标记流的新客户到达的强度，当系统未满时;（v） 当系统不满时，新客户到达新客户的到达强度是否;(vi) 从所有录取的流程到全系统的新客户的到达的强度是完整的系统，这不会导致终止相应的流量;（vii） 是非标记流终止(由于到达的客户丢失)的强度;(八) 是标记流终止(由于到达的客户丢失)的强度;（IX） 是完成客户从标记流到达的强度;(x) 是完成来自非标记流的客户到达的强度;(十一) 从标记流程完成客户到达后，概要难以到达，何时来自此流程的客户在到达终点时在系统中得到服务。

解决系统（4．2），以下矢量表示法很有用： 让矩阵函数由它的条目定义: 的矩阵是由单位矩阵得到的吗通过用柱子将其从右侧（左）侧侧面辅作矩阵是由单位矩阵得到的吗通过用行从上到下补充它．

使用此表示法，系统(6.1）可以很容易地表达为

考虑这个关系，利用总概率定律，我们可以很容易地证明下列命题。

定理4.1。这通过计算 的向量由条件拉普拉斯-斯蒂尔切变换组成是计算的

备注4.2。可以证明矩阵的对角线条目主导每一行。因此(见[9.])矩阵是毫无乐趣的任何．

推论4.3。平均逗留时间任意流的计算 值的位置是作为向量的相应元素来计算的吗它是由 平均逗留时间由任意接受的流量计算

5.任意容许流的损失概率

在这一节中，我们推导了任意容许流的损失概率表达式。回想一下，承认的流有可能丢失，因为从这个流程中失去了任何客户。

让表示在给定时刻，系统中处理的流的数量等于的条件下，在标记流在系统中逗留的剩余时间内，灾难不会到来的概率系统中的客户数等于来自标记流的客户数量等于并且该流不会因为从该流中丢失特定客户而被拒绝(终止)。

与前一节类似，我们可以证明下列命题。

定理5.1。损失的概率按照任意录取的流量计算 的功能是这个向量的元素吗由公式计算 在哪里是由此定义的矢量

5.2的话。与古典的Erlang损失模型相比，这是值得提及的，其中损耗概率可以通过简单的分析表达来计算，计算任意流动的损耗概率，以及流量到来的模型中的任意录取流程，需要开发算法工具。这种工具是本文的主要贡献。

6.数值例子

演示所提出的特征计算方法的可行性，并深入了解主要系统性能度量对其参数和令牌数量的依赖性我们给出了各种数值实验的结果。

6.1实验。在该实验中，我们修复了系统的以下参数：数字1显示了平均停留时间的依赖性对服务器数量的任意承认流程代币的数量．
请注意平均逗留时间随着服务器数量的增加而增加增加。这个令人惊讶的效应很容易解释如下。任意容许流量的停留时间随流量的增加而增加，因为流因客户流失而终止流的概率随着流量的增加而降低．

6.2实验。在该实验中，我们修复了系统的以下参数并假设令牌的数量数字2说明了损耗概率的依赖性对服务器数量的任意承认流程和概率当来自此流的客户被拒绝时，流终止的。
如预期的那样，当概率时，任意录取的流量的损失概率增加由于其客户拒绝增加，流动终止增加。随着服务器数量的增加，这种效果下降。

6.3实验。在实验中，我们展示了改变参数的效果，它定义了流程中的客户数量。我们将与上一个实验中的相同的参数进行修复，并设置相同数字3.说明了损耗概率的依赖性对服务器数量的任意承认流程和参数．
任意容许流量的损失概率随参数的增大而增大（以及流量的平均客户数）增加。随着服务器数量的增加，这种效果下降。

实验6.4。很明显，决策者通过流到达控制模型的操作，目的是增加令牌的数量提供系统的最高吞吐量。但是，增加了这明显导致了流动之间的竞争加剧，增加了损失的可能性任意录取的流程。为保护用户的利益，应施加一些QoS要求。自然需求是确保任意录取的流量的损失概率低于特定预测的水平．
因此出现以下优化问题： 受限制
在本实验中，我们考虑了这个优化问题，并举例说明了服务器数量的影响,概率当来自此流的客户被拒绝时，流终止的参数这是一个流中客户数量分布的特征。
首先，我们修复了系统的以下参数：数字4.显示值的依赖性什么是解决问题的方法6.1），（6.2），在服务器的数量上适用于各种可接受的价值损失概率。

从这个数字可以清楚地看出，如果这个数字服务器的数量小于或等于四个，即使是令牌的数量损失概率大于为了损失概率可以保证。为了和相应地，损失概率和可以保证。通过增加服务器的数量数量可以迅速增加。

其次，我们确定了系统的以下参数:数字5.显示依赖什么是解决问题的方法6.1），（6.2），概率流量终止，当来自此流量的客户被拒绝，各种值可容许的损失概率。

如预期，概率增加意味着减少．

最后，我们修复了系统的以下参数：数字6.显示依赖在参数上．

因为流程中的均值的平均数量等于这个数字迅速增加时接近1.相应地，什么是解决问题的方法6.1），（6.2),迅速降低。的值等于0.997,0.9997,0.99997，它分别对应于等于330,3330和33330的批量的平均数量，系统不能提供所需的QoS，即使是何时其中的值是分别。

7.结论

我们分析了苏姆斯时间分布，任意流量的损失概率，以及多元体损耗排队系统中的任意录取流，流量到来。结果可以利用绩效评估和系统的能力规划知识产权电话和其他信息传输系统没有缓冲，但有时间分配(流)到达客户。结果可方便地推广到病例中地图流程到达流程和阶段型服务时间分配。然而，这种相位型服务时间分布的特殊考虑导致了所研究的马尔可夫链状态空间的内在增加。结果还可以推广到流中客户数量的任意分布情况。然而，在这种情况下，马尔可夫链的状态空间也内在地增加了，因为有必要记录之前到达每个流的客户数量。为了弱化关于流中到达间隔时间的指数分布和几何批大小分布的假设，另一种方法是假设流中客户到达的阶段型机制。客户到达发生在阶段型分布的底层马尔可夫过程的转换时刻。对这种模型的分析正在进行中。

承认

本研究得到韩国研究基金会、KRF-2007-521-D00330和韩国中小企业管理局的资助。

参考

1. Sevastjanov，“电话系统中任意分配通话时长下的Erlang公式”第三届全联合会数学大会的诉讼程序《科学研究院》，第4卷，第68-70页，莫斯科，俄罗斯，1959年。视图:谷歌学者
2. C. S. Kim，A. Dudin，V.Klimenok和V.Khramova，“Erlang损失排队系统，具有随机环境中运行的批量抵达，”计算机与运筹学，卷。36，不。3，pp。674-697，2009。视图:出版商的网站|谷歌学者
3. V. Klimenok，“多服务器队列与损失和爆发流量的特征计算”自动控制和计算机科学，第32卷，第393-415页，1999年。视图:谷歌学者
4. 五，克里米诺克，C.S.Kim，D. Orlovsky和A. Dudin，“案例中缺乏Erlang损失模型的不变性。地图输入”,排队系统，第49卷，第2期。2，页187-213,2005。视图:出版商的网站|谷歌学者|Zentralblatt数学|MathSciNet
5. A. A. Kist, B. Lloyd-Smith和R. J. Harris，“一个简单的IP流阻塞模型”，在第19届国际TeletraChic大会关于高效下一代网络的绩效挑战（ITC'05）2005年8月至9月，中国北京，355-364页。视图:谷歌学者
6. M. H. Lee，S. Dudin和V.Klimenok，“排队模型与时间相位批量到来，”第20届融合网络通信性能管理国际电信通信会议论文集(ITC '07)，第4516卷计算机科学讲义，PP。2007年6月，加拿大渥太华719-730。视图:出版商的网站|谷歌学者
7. H. Kasten和J.Th。奔腾堡，排队优先问题，Mathematisch Centrum，阿姆斯特丹，荷兰，1956年。视图:MathSciNet
8. D. van Dantzig， " Chaînes de Markof dans les ensembles and applications aux procesavec régions absorbtes and au problème des boucles， "annales de l'Institut HenriPoincaré，卷。14，pp。145-199,1955。视图:谷歌学者|Zentralblatt数学|MathSciNet
9. f·r·Gantmakher矩阵理论《科学》，莫斯科，俄罗斯，1967年。

版权

版权所有©2008 Moon Ho Lee和Sergey A. Dudin。这是分布下的开放式访问文章创意公共归因许可证，允许在任何媒介上不受限制地使用、分发和复制，只要原稿被适当引用。