排队论模型
网络发展初期，人们认为数据包的到达顺序满足 __泊松分布__，但是后来人们发现并不是这样。不过要先了解这些，得先了解一下排队论的基础知识。
排队论中的几种模型
排队过程可以分成三个阶段：输入过程、排队过程、服务过程
- 输入过程。就是顾客的到来方式，可以是成群结队的，也可以是形单影只的，可以是想来就来的（独立的），也可以是看别人来了自己就稍后再来的（相关的）……当然还有其他的输入方式。
- 排队过程。如果一个顾客看到一家烧饼店前已经有了很多的顾客在排队，那么他可能会选择换一家（损失制）；不过如果一个顾客看到一家网红奶茶店，那么她很有可能会不顾一切地排上去（等待制）；当然，最常见的就是混合制——有的人会选择排队而有些人会选择立即离开。
- 服务过程。常见的小型饮食店的服务过程大多是单服务器类型，也就是只有一个服务窗口，而稍微大一点的有多个服务窗口的就是多服务器模型。多服务器型的还分串联和并联之类的，
拒绝插队哦(⊙ˍ⊙)
规定基本符号
排队论是一个数学模型，因此免不了接触一大堆符号，这里先熟悉一下之后会遇到的符号。
排队论将一个排队模型用六元组标识：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，很赚啊）
泊松分布
泊松分布有以下三个前提条件：
用户的到达是相互独立的，也就是不存在看到别人在排队就待会再来的那种情况。
在一段足够小的时间间隔$\Delta t$内，顾客到达的概率和该时间间隔长度成正比，但是和时间$t$没有关系。用公式表示就是
$$P_1(t,t+\Delta t)=\lambda\Delta t+o(\Delta t)$$两个以上顾客同时到达的概率小到可以忽略。也就是在足够小的时间间隔$\Delta t$内，同时到达概率为时间间隔的高阶无穷小$o(\Delta t)$。也就是说
$$\sum_{n=2}^{\infty}{P_n(t,t+\Delta t)}=o(\Delta t)$$
根据我们的经验，在一个排队论系统中，随着时间的流逝却一直无人问津的概率是随着时间递减的。并且假设起始时间为t，终止时间为t的时间片（也就是一瞬间），一定是无人到达的，其概率为1。那么我们能不能用一个公式表达出这种关系呢？
目标：推导顾客到达人数n的概率分布$P_n(t)$
简化起见，起始时间设定为0，并且令：$P_n(0,t)=P_n(t)$。
由条件1（独立性假设）和条件2（短时间内概率和时间长度成正比）可以得到：
$$
P_0(t+\Delta t) = P_0(t)P_0(\Delta t) \
P_1(t+\Delta t) = P_0(t)P_1(\Delta t) + P_1(t)P_0(\Delta t) \
\dots \
P_n(t+\Delta t) = \sum_{k=0}^{n}{P_{n-k}(t)P_k(\Delta t)}
$$
由于条件3（2个及以上到达概率可忽略），因此在$\Delta t$时间内只有两种可能情况：1. 没有人到达，2. 1个人到达。也就是说：
$$P_0(\Delta t) = 1 - \lambda\Delta t + o(\Delta t)$$
知道了$P_0(\Delta t)$和$P_0(t+\Delta t)$就可以求出
$$\frac{P_0(t+\Delta t)-P_0(t)}{\Delta t} = -\lambda P_0(t) + \frac{o(\Delta t)}{\Delta t}$$
同理，可以求出n一般情况下的
$$\frac{P_n(t+\Delta t)-P_n(t)}{\Delta t} = -\lambda P_n(t) + \lambda P_{n-1}(t) + \frac{o(\Delta t)}{\Delta t}$$
取$\Delta t$得极限，那么上面两个式子转化为对应得微分方程：
$$
\frac{P_0(t)}{dt} = -\lambda P_0(t) \
\frac{P_n(t)}{dt} = -\lambda P_n(t) + \lambda P_{n-1}(t), n=1,2,\dots
$$
由于在一瞬间一定没有人到达，因此$P_0(0)=1$，因此有：
$$P_0(t)=e^{-\lambda t}$$
其图像符合预期——随时间递减，并且到达概率$\lambda$越大，曲线下降越快。
求解$P_n(t)$据说需要常微分方程的知识，这里先mark以下……等学会了再补充。不过之后用到M/M/1的只是最简单的$P_0(t)$
使用常微分方程知识求解$P_n(t)$得到：
$$P_n(t)=\frac{(\lambda t)^n}{n!}e^{-\lambda t}, n=1,2,\dots$$
在概率论中学到的泊松分布表示为$P(X=k)= \frac{\lambda^k}{k!}e^{-\lambda}$，可见这是上面那个式子在 单位时间 内发生次数的表示情况
泊松分布的应用
上面得出了泊松分布的一般形式，下面探讨泊松分布在排队论中的应用。
当顾客流为泊松流的时候，考虑两个顾客在时间t内相继到达的概率。如果将前一个顾客A到达时间固定为0，那么后一个顾客B到达前没有其他顾客X到达（否则X就变成了后者）。于是这个概率相当于求$P_0(t)=e^{-\lambda t}$。也就是说，当输入过程是泊松流时，那么顾客相继到达的时间间隔服从指数分布。
如果要求顾客的平均到达时间，那么就是求$P_0(t)$的期望：
$$E(P_0(t)) = \int_{0}^{\infty}{e^{-\lambda t}dt} = \frac{1}{\lambda}$$
正好是概率强度的倒数。
由于M/M/1模型中服务时间也是相同的分布，因此也有类似的结论。
了解了M/M/1的基本性质之后，假象一个到达率为$\lambda$，服务率为$\mu$排队系统。当$\lambda$和$\mu$满足一定关系的时候，这个排队的长度是怎么变化的呢？这个就要用到“生灭过程”。
生灭过程
生灭过程是一种随机过程，在排队论中，“生”表示顾客到达，“去”表示顾客离开。当然如果把系统内顾客数作为状态来看，生灭过程可以理解为系统状态的转移，Markov既视感。
令t时刻系统中的排队人数为N(t)，并且在人数为n时，从t时刻开始到下一个顾客到达和离开的时间分别服从参数为$\lambda_n$以及参数为$\mu_n$的负指数分布，并且同一时刻只有以恶搞顾客到达或离开，那么这样就是一个生灭过程。
由于系统中总是有进入和出去的人，因此系统排队长度总是在发生变化的，并不是一个恒定的值，不过当最终进入平衡状态的时候，系统队长只会在很小的范围内波动，可以认为此时进入和离开的平均次数相等。此时可以列出状态转移的平衡方程
$$
\mu p_1=\lambda p_0 \
\lambda p_0+\mu p_2=(\lambda+\mu)p_1 \
\lambda p_1+\mu p_3=(\lambda+\mu)p_2 \
\dots \
\lambda p_{n-1}+\mu p_{n+1}=(\lambda+\mu)p_n \
\dots
$$
该图的思想/模型还可以用到传染病学等。比如将传染的人数比作状态，那么状态之间的跳转也可以用类似的图表示
以上方程组可以用数学归纳法解得：
$$p_n=(\frac{\lambda}{\mu})^n p_0,n=1,2,\dots$$
为了书写方便，令
$$C_n=(\frac{\lambda}{\mu})^n$$
这就是系统稳定后每个状态的概率。由于总概率之和为1，因此有
$$\sum_{n=0}^{\infty}p_n=(1+\sum_{n=1}^{\infty}{C_n})p_0=1$$
因此
$$p_0=\frac{1}{1+\sum_{n=1}^{\infty}{C_n}}$$
这样就能求出每个状态下的概率。而平衡状态下，队列长度的期望就是
$$L_q=\sum_{n=0}^{\infty}{np_n}=\frac{\lambda}{\mu-\lambda}=\frac{\rho}{1-\rho}$$
绘制一下这个曲线，可以发现系统越繁忙，队伍越长。
M/M/s
我曾在MCM-ICM中用到了排队论模型，不过用的是多服务器模型。这种模型的转移图可以画成
也就是说，当顾客数量小于s时，系统服务顾客的能力随着顾客数增多而增大；但是当顾客数量超过s后，系统的服务能力达到最大且恒定不变。
排队论在信道多路复用中的使用
用排队论的思想来讨论信道多路复用的效率问题。讨论对网络性能分析和提升网络性能的数学方法的使用。
翻了一下书，信道多路复用有多种方式，比如按时间划分的TDM、按频率划分的FDM、还有CDMA（有点类似用向量空间中的一组标准正交基做解码解码的方法）
未完待续