排队论模型

网络发展初期,人们认为数据包的到达顺序满足 泊松分布,但是后来人们发现并不是这样。不过要先了解这些,得先了解一下排队论的基础知识。

排队论中的几种模型

排队过程可以分成三个阶段:输入过程、排队过程、服务过程

  1. 输入过程。就是顾客的到来方式,可以是成群结队的,也可以是形单影只的,可以是想来就来的(独立的),也可以是看别人来了自己就稍后再来的(相关的)……当然还有其他的输入方式。
  2. 排队过程。如果一个顾客看到一家烧饼店前已经有了很多的顾客在排队,那么他可能会选择换一家(损失制);不过如果一个顾客看到一家网红奶茶店,那么她很有可能会不顾一切地排上去(等待制);当然,最常见的就是混合制——有的人会选择排队而有些人会选择立即离开。
  3. 服务过程。常见的小型饮食店的服务过程大多是单服务器类型,也就是只有一个服务窗口,而稍微大一点的有多个服务窗口的就是多服务器模型。多服务器型的还分串联和并联之类的,

拒绝插队哦(⊙ˍ⊙)

规定基本符号

排队论是一个数学模型,因此免不了接触一大堆符号,这里先熟悉一下之后会遇到的符号。

排队论将一个排队模型用六元组标识:X/Y/Z/A/B/C。

符号 描述
X 顾客到达时间的间隔分布
Y 服务时间分布
Z 服务窗口数
A 系统容量限制
B 顾客源数目
C 服务规则,FCFS、LCFS等

由于不考虑插队,所以就忽略C中的LCFS模型了;系统容量一般受限(比如在路由器中的缓冲区),但是简化起见假设系统容量充足;顾客源数目也“不负责任”地认为无限了( ̄▽ ̄)”。这样一个六元组就只需要关注前三个X/Y/Z就好了!

X、Y都有多种类型,比如$M$(Markov,无记忆性分布,负指数分布)、$D$(Deterministic,确定型分布)、$E_k$(k阶埃尔朗分布)等。

埃尔朗分布中的“埃尔朗”就是研究电话通话排队的的电话工程师,是排队论的鼻祖

排队论的衡量指标有以下这些:

符号 含义
$L_q$ 排队中的顾客数量期望
$L_s$ 系统内顾客数量期望,包括正在被服务的顾客
$W_q$ 顾客排队的时间期望
$W_s$ 顾客在系统中消耗的时间期望,包括排队和被服务时间

之后还会遇到有关概率的表示:

符号 含义
$P_n(t_1,t_2)$ 表示为在$t_1$到$t_2$时间段内系统到达$n$个人的概率。
$\lambda$ 单位时间顾客到达的人数,也称为概率强度
$\mu$ 单位时间能被服务完成的顾客数,也称为$\mu$
$\rho$ $\lambda/\mu$,表示到达速度和离开速度的比。直观感受,$\rho$越大,系统越繁忙

M/M/1

M/M/1表示顾客的到来时间和服务时间都是服从负指数分布,且系统中只有唯一服务窗口的排队论模型。先来了解一下M分布的特点(了解了第一个M就懂了第二个M,很赚啊)

泊松分布

泊松分布有以下三个前提条件:

  1. 用户的到达是相互独立的,也就是不存在看到别人在排队就待会再来的那种情况。

  2. 在一段足够小的时间间隔$\Delta t$内,顾客到达的概率和该时间间隔长度成正比,但是和时间$t$没有关系。用公式表示就是

  3. 两个以上顾客同时到达的概率小到可以忽略。也就是在足够小的时间间隔$\Delta t$内,同时到达概率为时间间隔的高阶无穷小$o(\Delta t)$。也就是说

根据我们的经验,在一个排队论系统中,随着时间的流逝却一直无人问津的概率是随着时间递减的。并且假设起始时间为t,终止时间为t的时间片(也就是一瞬间),一定是无人到达的,其概率为1。那么我们能不能用一个公式表达出这种关系呢?

目标:推导顾客到达人数n的概率分布$P_n(t)$

简化起见,起始时间设定为0,并且令:$P_n(0,t)=P_n(t)$。

由条件1(独立性假设)和条件2(短时间内概率和时间长度成正比)可以得到:

由于条件3(2个及以上到达概率可忽略),因此在$\Delta t$时间内只有两种可能情况:1. 没有人到达,2. 1个人到达。也就是说:

知道了$P_0(\Delta t)$和$P_0(t+\Delta t)$就可以求出

同理,可以求出n一般情况下的

取$\Delta t$得极限,那么上面两个式子转化为对应得微分方程:

由于在一瞬间一定没有人到达,因此$P_0(0)=1$,因此有:

其图像符合预期——随时间递减,并且到达概率$\lambda$越大,曲线下降越快。

求解$P_n(t)$据说需要常微分方程的知识,这里先mark以下……等学会了再补充。不过之后用到M/M/1的只是最简单的$P_0(t)$

使用常微分方程知识求解$P_n(t)$得到:

在概率论中学到的泊松分布表示为$P(X=k)= \frac{\lambda^k}{k!}e^{-\lambda}$,可见这是上面那个式子在 单位时间 内发生次数的表示情况

泊松分布的应用

上面得出了泊松分布的一般形式,下面探讨泊松分布在排队论中的应用。

当顾客流为泊松流的时候,考虑两个顾客在时间t内相继到达的概率。如果将前一个顾客A到达时间固定为0,那么后一个顾客B到达前没有其他顾客X到达(否则X就变成了后者)。于是这个概率相当于求$P_0(t)=e^{-\lambda t}$。也就是说,当输入过程是泊松流时,那么顾客相继到达的时间间隔服从指数分布。

如果要求顾客的平均到达时间,那么就是求$P_0(t)$的期望:

正好是概率强度的倒数。

由于M/M/1模型中服务时间也是相同的分布,因此也有类似的结论。

了解了M/M/1的基本性质之后,假象一个到达率为$\lambda$,服务率为$\mu$排队系统。当$\lambda$和$\mu$满足一定关系的时候,这个排队的长度是怎么变化的呢?这个就要用到“生灭过程”。

生灭过程

生灭过程是一种随机过程,在排队论中,“生”表示顾客到达,“去”表示顾客离开。当然如果把系统内顾客数作为状态来看,生灭过程可以理解为系统状态的转移,Markov既视感。

令t时刻系统中的排队人数为N(t),并且在人数为n时,从t时刻开始到下一个顾客到达和离开的时间分别服从参数为$\lambda_n$以及参数为$\mu_n$的负指数分布,并且同一时刻只有以恶搞顾客到达或离开,那么这样就是一个生灭过程。

由于系统中总是有进入和出去的人,因此系统排队长度总是在发生变化的,并不是一个恒定的值,不过当最终进入平衡状态的时候,系统队长只会在很小的范围内波动,可以认为此时进入和离开的平均次数相等。此时可以列出状态转移的平衡方程

该图的思想/模型还可以用到传染病学等。比如将传染的人数比作状态,那么状态之间的跳转也可以用类似的图表示

以上方程组可以用数学归纳法解得:

为了书写方便,令

这就是系统稳定后每个状态的概率。由于总概率之和为1,因此有

因此

这样就能求出每个状态下的概率。而平衡状态下,队列长度的期望就是

绘制一下这个曲线,可以发现系统越繁忙,队伍越长。

M/M/s

我曾在MCM-ICM中用到了排队论模型,不过用的是多服务器模型。这种模型的转移图可以画成

也就是说,当顾客数量小于s时,系统服务顾客的能力随着顾客数增多而增大;但是当顾客数量超过s后,系统的服务能力达到最大且恒定不变。

排队论在信道多路复用中的使用

用排队论的思想来讨论信道多路复用的效率问题。讨论对网络性能分析和提升网络性能的数学方法的使用。

翻了一下书,信道多路复用有多种方式,比如按时间划分的TDM、按频率划分的FDM、还有CDMA(有点类似用向量空间中的一组标准正交基做解码解码的方法)

未完待续