根据排队论阐述路由器和高速公路的拥堵以及拥堵缓解问题

关于本文

相信很多人都在节假日的高速公路上遇到过大拥堵，但是最终拥堵会解除。也有人在质疑路由器队列的长度，以为最终路由器会拒绝服 务。我曾经在10年前天真地以为高速公路的设计者和路由器交换机的设计者工作是多么的轻松。然而现在，当我知道更多后，发现事实并不如此。需要更多的权衡 和博弈，不仅仅是技术方面的，还涉及到了心理学，社会学，经济学。
       因此本文旨在用最简单的描述分析一下排队理论对高速公路以及分组交换网络的指导。文中没有复杂的数学推导，这种推导请自行完成，或者请背诵大学概率论教科书的相关章节，如果你不感兴趣，请记住结论即可，如果你存有疑义-正如我一样，请阐述。

排队理论概述

排 队背后的理论就是排队论...而排队论是分组交换的核心。不光如此，它也是高速公路建设等所有涉及到排队的场景(缴费，银行服务等)的核心。不管怎么说， 它非常重要。事实上它也非常简单。参考了一篇很好的文章《A Dash of Queueing Theory》，非常简单的描述了大多数人认为非常复杂的排队论，因此我就趁着周末写一篇 读后感吧。顺便谈一下我个人对分组交换和统计复用的理解。
       分组交换之所以可行，背后的理论就是排队论。事实上，早在分组交换还没有的时候，排队论早就应用了好几百年乃至上千年，分组交换网络只是在这个事实被理论化的同时恰逢网络发展的春天，二者就联姻了。
       分组交换的另一个核心就是统计复用。事实上，早在分组交换还没有的时候，统计复用早就存在了几千年乃至几千万年。我们生活的世界本身就是统计复用的，道路，土地，公共设施，都是统计复用的。
       统计复用之所以可被接受，背后的理论依然是排队论，即排队公平性。当然，在历史的早期，由于没有采用统计复用从而导致不公平，最终形成了蝴蝶效应，随之国王，帝国，统治者相继出现...不过，这不是本文讨论的。

将任务(数据包，车辆)排队过程和被服务过程按时间分别展开

我们把一个单独的排队过程按照时间展开，就会得到下面的图示(入队速率固定)：

那如果我们把一个消费队列里实体的输出服务消费的过程按照时间展开，就会得到下面的图示：

任务(数据包，车辆)排队过程和被服务过程合并

如 果任由排队实体持续排队，队列将会变得无限长。事实上，任何队列都不会无限长，否则大家为何在那排队去等待一个永恒不被接受的服务....小说《十年》里 的那个废弃火车站等车的并不存在于现实。为什么？因为只要有排队，就会有服务处理队头，即排队在队尾，服务在队头，这是一个简单的先进先出的过程。
       那么，我们把上面两个图合并，就会发现，合并后的两条曲线中间的带状，就是队列，如下图所示：

任务在固定速率输入情形下的排队分析

1.任务输入率和服务的吸收率相等的情形

这 种情况，从初始状态开始，是不会产生排队现象的，比如单位时间到达三个人需要服务，而服务台拥有三个服务员，忽略服务时间的假设下，每单位时间总是会有三 个服务员为人民服务。但是一旦加入其它的因素，比如处理某个人的业务过久(服务时间是不能忽略的)，就会产生排队现象，一旦某个服务被延迟，就会总体拖慢 服务输出率，这是导致排队的主因。

2.任务输入率和服务的吸收率不等的情形

如果服务输出率大于队列输入率且持续大于，那么队列最终会消失，如果持续小于队列输入率，队列会越来越长，这些都是常识，但是这些都是深入分析的基础。

3.结论

我们从下图的分析可以看出，增加服务资源一点点即可，不需要增加太多，我们要达到的效果就是，偏差一个角度，让服务输出曲线和队列输入曲线最终相交即可：

真实情况：输入的泊松分布与输入间隔的指数分布

前 面的分析和图示，让我们感觉到排队系统是多么的不稳定啊，要么队列变为0，要么持续增长。持有这种观点的，一定会质疑路由器的可用性。可是事实上，不管在 现实中，比如高速公路拥堵，抢购物品，买票还是网络世界，比如路由器，交换机，服务器，我们都没有看到过队列快速变为0或者持续增长的情况，队列总是在波 动，排队的实体除非自己放弃，不然总会得到服务，队列也从来没有无限加长。这是为什么？
       因为排队的入队率并不是一个常数，而是符合泊松分布的一个范围，说白了就是，入队率有一个平均值，偏离这个平均值越多的入队率，越是不可能看到的。比如说 一个入队率平均值是10，那么单位时间排队10个实体是最可能的，排队9个或者11也是次可能的，8个或者12个，7个或者13个，都有可能，...那么 1个或者19个相对于前面那些，就显得可能性很小了。
      由于入队率的泊松分布，相邻两个排队实体的排队间隔也应该有一个分布规律，这是可以从泊松分布推导出来的，由于数学只是一个工具，我就不贴推导过程了，直 接贴出答案，相邻排队实体的排队间隔符合指数分布，意思是说，下一个排队者最可能会在最短的时间到来，比如1分钟内，如果5分钟还没有来，你指望它15分 钟内来的希望也是比较渺茫的，这也叫做“下一个马上到”定律。这是非常符合常识的，比如你在等人的时候，他如果迟到了20分钟，那么他很可能就不会来了， 比如面试，如果你面试完还没回到家，刚刚面试的公司就打来电话了，那么你很有可能被录取了。
       这就是泊松分布和指数分布下真实的排队场景。

任务输入速率符合泊松分布前提下的排队分析

真实的排队场景如下图所示：

把图放远看，你会忽略些许弯曲的细节，整个输入曲线就是一个直线，实际上服务输出曲线也一样，这正如分形理论阐述的一样。有两点要牢记：

a).大部分情形下，输入率都是平均输入率，起码向平均输入率收敛(泊松分布起作用了)；
b).大部分情形下，在符合a的前提下，下一个排队者马上就到(指数分布起作用了)。

高速公路上的排队拥堵与缓解

排队拥堵示例

1.单车道情形

前 车停止，后面的车便无法通过，毕竟它们不会飞。那么就会造成排队，前面的车按照停车之间的固定速率开行，车队里的车辆一辆接着一辆出队，然而队列并不会快 速消失，因为队尾还有很多车辆在陆续入队，如果入队速率和出队速率一致，则队列永远不会消失，如果出队速率小于入队速率，则队列永远不会消失，还会持续加 长，如果出队速率大于入队速率，则队列最终消失。

2.双车道不考虑加塞，变道情形

这种情况几乎可以不考虑，因为它事实上不可能在一个统计复用的信道中发生。这种情况说的是一个带有“队头拥塞”的车道与一条正常不排队的车道的无干涉叠加，两根车道互不影响，一根车道完全停滞，另一根车道全速畅通，你见过这种情况吗？反正我是没有。
       这是为什么？
       统计复用网络或者通道建立的前提之一就是排队公平性！这是核心中的核心，也正是因为这个原则，分组交换网络才有了理论合理性，才具有可用性。考虑电路交换 网或者火车，通道是专有的，通道存在其间，即便是空闲也不能被他人借用。每个通信实体要想使用通道，都必须申请一条专用的，自己私用，后来鉴于节约资源考 虑，有了各种复用，然而这些复用的粒度还是很粗，仍然会有空闲间隙。以京广线上的火车TDM为例，虽然很多列火车都在不同的时间共享这条铁路线，但是你依 然会看到大量的时间，铁路上是无车通行的，这种严格的时隙复用是严格的，需要相当的时钟同步机制，因此相邻的两个时隙之间的间隙要足够长，开销巨大，或者 说对于运输任务并不固定的地方铁路货运来讲，你无法保证今天分给货车A的时间间隙T一定会被货车A用到，因为它今天可能没有运输任务。那如果要把时隙T再 分给别人，就需要复杂的调度机制...最高尚且合理的方案是什么？就是彻底消除浪费。复用粒度进一步变小，最终消除中心管控，变成完全的自由市场，由通信 实体自己根据自己需求来决定复用流程，这就是统计复用。
       没有规则就是最好的规则！
       最重要的无规则就是插队，加塞，见缝插针。这是存在，也就是合理的，因为所有的复用都要有一个前提，那就是公平性，完全的私用通道，TDM，FDM都不会 造成排队，因为对于多个通信实体，它们的通道在物理上或者逻辑上是分离的，然而对于统计复用，通道是完全混合的，公平性需要自行构建。畅行无阻时，大家都 是公平的，不公平的时刻永远都是在出现排队，拥塞的情况下才会被感知，因此就需要一种在排队时期也需要的公平机制，这个机制就是加塞，变道，也就是自行构 建虚拟输出队列(VOQ)。排队车道在排队的车辆拥有这个权利，因为它们和正常车道上正常行驶的车辆是完全等位的，是队头造成了排队拥塞，与排队者无关， 排队者排队是无辜的，体现了不公平，为了采取公平措施，只能拉低全部车道的畅通质量。

3.为什么拥堵会快速蔓延

在理解 了上述分析以后，你会看到，指数分布下，下一个排队者马上就来，不管是针对泊松分布的期望，还是针对泊松分布的边缘，都是如此。下一个排队者总是最可能在 最短的时间间隔内到来，这就是迅速蔓延的根本。对比上面的图示，可以看到，两条曲线之间的带状区域，它会迅速增大面积，导致局部拥塞引发全局拥塞。

4.真实情形：普遍排队，大面积拥堵

以 上讲了为何在高速公路排队拥堵时不可能不加塞，那么真实的情况是什么呢？不说大家也明白，有时候在高速公路上堵了一小时，缓慢前行，到前面发现离自己最远 的一根车道上两辆车轻微碰擦...单向4车道的宽阔道路，最外侧车道的事故怎么会影响到最内侧车道，怎么会带来大面积，可能超级几十公里的排队长度？
       前面的1，2情形，都是不允许加塞，变道的情形，因此它只影响一根车道，也就是说造成一根车道的排队拥堵。真实情况是，这根排队的车道上的车辆肯定会觉得 这不公平-这是前面提到的，这种情况在路由器中叫做”队头拥塞(HOL，Head of Line)“，由于车辆和数据包不同，它们是自路由的，于是排队车道的车辆开始自行建力VOQ，即虚拟输出队列，说白了就是加塞，变道，变道到不排队的车 道上，后者会引发进一步的VOQ自键过程，连锁反应，如此一来，排队拥堵车道的流量就均分到正常车道上了，于是乎正常车道的输入率超过了常规。引发正常车 道上同样出现排队...
       这种情况和TCP/IP网络的情形完全一致，即不管是对于车辆还是对于数据包，网络都是统计复用的，并不存在什么严格的规则，比如严格TDM，FDM等， 说得明白点就是见缝插针，通道只要空着，你不用时我就用，还记得CSMA/CD吗？基本就是这样。一辆车和前车车距超过安全距离时，就会有旁边车道的车子 想加塞，他会首先来一个“载波监听，冲突检测”，比如闪灯，以确保自己的行为被后车知道，如此等等。虽然这不是什么好的绅士风度，但是这就是所有统计复用 通道的本质。这是一个冒险求效率的过程，也可以说是一个互惠共赢的局面，这局面中冲突在统计复用潜规则(若没有潜在的规则，你能想象在拥堵的市中心，各种 箱货车，轿车，行人，电瓶车，毕竟竟然毫无碰擦，你要知道后视镜是有死角的，而司机也不见得各个都能把握自己车子的长宽高已经转矩...)影响下永远都是 局部的，少量的事件，因此值得冒险，然而一旦发生冲突，比如碰擦，事故等，就会造成全局的大面积拥塞，这个我们前面已经提到，那么接下来要说的是，这种排 队拥堵是如何得到缓解的呢？它一定会得到缓解，若不是如此，这种统计复用的网络便完全不可用！且接着读。

高速公路的排队拥堵是怎么缓解的

我 们知道，道路是会拥堵的，但是这种拥堵总是会缓解的，按照理想情况，以固定输入率到达且以固定输出率输出的车辆一旦排队，队列将永远保持，这也是上面的理 论分析得到的结论，然而真实的情况是，虽然在排队拥堵缓解的那一刻，输出率是固定的，但是输入率并不固定，输入率的泊松分布使得拥堵最终缓解。
       诚然，增加一根车道，相当于增加了服务资源一点点。依照我们前面的讨论，考虑固定速率的输入和固定的服务率，即固定的服务资源，如果输入曲线和输出服务曲 线二者平行，拥堵期间造成的队列将永远存在，且队列长度不变，但是如果增加哪怕一根车道，输出服务的曲线就会向上陡一些，终究会和输入曲线相交，使队列消 失。可谓一种差之毫厘，谬以千里的效果。
       当然，考虑到真实情况无疑要复杂的多，要考虑到加塞，变道等不文明行为导致的拥塞进一步加剧，当然这是坏的一方面。那么在真实情况下，好的一方面是，输入 曲线并不是一根直线，其斜率是可变的，怎么变呢？简单的来讲，就是这条曲线的趋势还是如固定输入率的方向所指向，但是其每一个点的协议总的来讲是符合泊松 分布的，其期望值就是固定输入率的斜率！我们来看一下这个泊松分布在输出服务恢复时是怎么救我们出泥潭的。分两种情况。
情况1：输出服务暂停-比如两车碰擦或者交通事故导致了车道封闭
在事故未疏通时，泊松分布对拥堵是没有效果的，无论如何，到来的车辆只是加长了排队的队列，只是说由于车辆到来速率符合泊松分布，有时候来的车多一点，有时候少一点，不管怎样，队列长度均增加，只是增加的速度不同。
       等到事故疏通以后，事故点的交通完全恢复，排在队列第一个的车子首先发动开走，紧接着是第二辆，然后第三辆...此时事故点的车子离开速率是固定的，且是 全速率的，好像这个地点的车辆通过率达到了泊松分布中概率最小的最大值一样，此时队列尾部的车辆到达率还是符合标准的泊松分布。在队列未消失之前，事故点 即队列头的车辆通行率都是固定的，且大于队列尾部的车辆到达率，久之，队列消失。
       如果队列尾部的车辆到达率和队列头的车辆通行率相等，那么队列将永远维持！
情况2：输出服务延缓-比如遇到了收费站
考 虑车道数量和收费窗口数量相等的情况，按照前面的分析，由于收费站就在那里，且永远不会消失，因此它造成的排队拥堵便”永远不会恢复到正常“，因此情况1 的解释便不能用于情况2，可是我们依然看到事实上高速公路在非节假日时并不会因为收费站而大面积不可恢复的排队拥堵，这是为什么呢？
       因为收费窗口数量要大于车道数量，虽然它增加了单辆车的延迟，但是它却可以并行处理多辆车，所以总的吞吐(或者说线速能力)并没有变化，总的来看，排队拥堵还是缓解了。
       这情况2值得注意，这就是路由器的做法！！
       本节最后，我们看一个基本事实。上海境内沪嘉高速(S5高速)，于2012年前后拆除了收费站，于2013年前后拆除了中央隔离绿化带，与两侧硬路肩一起 增加了单向一根车道。想想这是为什么？为什么只在单向增加了一根车道而不是两根，为什么拆了收费站增加了一根车道这种简单的事就带来了容量的大增。通过上 面的分析应该可以得到答案，注意，不要单单从收费与否与车主的利益上考虑。
       还有一个思考题，那就是古罗马帝国道路系统的设计，但是这不是排队拥堵问题的范畴，而是连通性问题的范畴，连通性怎么带来收益指数级倍增的？

高速公路收费站节假日免费的另一个原因
并 不仅仅是钱的问题，而是收费站本身就不合理。我说一句类似的，就是大流量时，骨干路由器会消除一些针对流量的审计策略，留给认证过的可信任BGP另一端， 入IGP域内部的边缘路由器来完成这种审计功能，是不是和节假日取消收费类似呢？是它容量吃不消，不是因为想为大家省钱，钱是省不了的，全体开车出行，全 交给旅游景点了...
       高速公路跟路由器一样，在设计之初，其平均容量，最大容量，最恶劣的排队时延，收费站时延，并行度都是经过复杂数学计算的，其不可避免地要涉及到泊松分 布，指数分布，另外心理学，气候因素等也有极重的权值，而这个计算结果并不会针对突发流量，也就是说，任何组织都不会将高速公路，路由器缓冲区设计成以突 发流量为基准的系统，这样的话，过高的成本带不来可观的收益，但是如果真的是这样，那真就是为人民服务了。这种排队系统得设计只是针对平均容量的，总容量 会比平均容量稍微大一点，以应对不可预知的小型突发，更多的时候，完全依靠以下的冒险假设来缓解排队拥堵：
输入曲线是一条弯弯曲曲的曲线，总趋势为一条直线，其斜率为输入率期望值，而大多数时候的情况下，输出服务率只要比输入期望稍微大一点点即可，以达到大多数时候，输出服务曲线可以向上追赶输入曲线，大多数情况下可以使两条曲线相交即可！

路由器缓冲区大小以及调度算法的设置

在 分析了这么多之后，你是不是突然发现，该为路由器设置多少缓冲区-即排队区域，并不是一件很简单的事。因为你要事先预测平均流量，最小流量，最小流量持续 时间，最大突发流量，突发流量的持续时间，突发时间段，然后作出一个基于服务质量-分解为输入率和输出率，成本之间马鞍面那个可以坐人位置的判断。总之， 路由器的缓冲区可能是动态变化的，这里面的数学计算特别复杂，其根本就是一场博弈，因此除了排队论之外，你还要了解博弈论。
       缓冲区的设置仅仅针对输入，对于输出，还要有一个调度算法的设置。真的，路由器比高速公路复杂多了，因为高速公路的车辆是自路由，自建输出队列的(通过转向灯，加塞变道等行为)，而路由器则是完全靠路由器内部的算法进行盲导航的。
       不过，真的希望高速公路的例子可以让人更加理解路由器的本质，together with分组交换以及统计复用的本质。