关于本文相信很多人都在节假日的高速公路上遇到过大拥堵，但是最终拥堵会解除。也有人在质疑路由器队列的长度，以为最终路由器会拒绝服务。我曾经在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分钟，那么他很可能就不会来了，比如面试，如果你面试完还没回到家，刚刚面试的公司就打来电话了，那么你很有可能被录取了。 这就是泊松分布和指数分布下真实的排队场景。任务输入速率符合泊松分布前提下的排队分析真实的排队场景如下图所示：人若软弱就是自己最大的敌人
