關(guān)于本文

相信很多人都在節(jié)假日的高速公路上遇到過(guò)大擁堵，但是最終擁堵會(huì)解除。也有人在質(zhì)疑路由器隊(duì)列的長(zhǎng)度，以為最終路由器會(huì)拒絕服 務(wù)。我曾經(jīng)在10年前天真地以為高速公路的設(shè)計(jì)者和路由器交換機(jī)的設(shè)計(jì)者工作是多么的輕松。然而現(xiàn)在，當(dāng)我知道更多后，發(fā)現(xiàn)事實(shí)并不如此。需要更多的權(quán)衡 和博弈，不僅僅是技術(shù)方面的，還涉及到了心理學(xué)，社會(huì)學(xué)，經(jīng)濟(jì)學(xué)。
       因此本文旨在用最簡(jiǎn)單的描述分析一下排隊(duì)理論對(duì)高速公路以及分組交換網(wǎng)絡(luò)的指導(dǎo)。文中沒(méi)有復(fù)雜的數(shù)學(xué)推導(dǎo)，這種推導(dǎo)請(qǐng)自行完成，或者請(qǐng)背誦大學(xué)概率論教科書(shū)的相關(guān)章節(jié)，如果你不感興趣，請(qǐng)記住結(jié)論即可，如果你存有疑義-正如我一樣，請(qǐng)闡述。

創(chuàng)新互聯(lián)公司從2013年創(chuàng)立，先為民樂(lè)等服務(wù)建站，民樂(lè)等地企業(yè)，進(jìn)行企業(yè)商務(wù)咨詢服務(wù)。為民樂(lè)企業(yè)網(wǎng)站制作PC+手機(jī)+微官網(wǎng)三網(wǎng)同步一站式服務(wù)解決您的所有建站問(wèn)題。

排隊(duì)理論概述

排 隊(duì)背后的理論就是排隊(duì)論...而排隊(duì)論是分組交換的核心。不光如此，它也是高速公路建設(shè)等所有涉及到排隊(duì)的場(chǎng)景(繳費(fèi)，銀行服務(wù)等)的核心。不管怎么說(shuō)， 它非常重要。事實(shí)上它也非常簡(jiǎn)單。參考了一篇很好的文章《A Dash of Queueing Theory》，非常簡(jiǎn)單的描述了大多數(shù)人認(rèn)為非常復(fù)雜的排隊(duì)論，因此我就趁著周末寫(xiě)一篇 讀后感吧。順便談一下我個(gè)人對(duì)分組交換和統(tǒng)計(jì)復(fù)用的理解。
       分組交換之所以可行，背后的理論就是排隊(duì)論。事實(shí)上，早在分組交換還沒(méi)有的時(shí)候，排隊(duì)論早就應(yīng)用了好幾百年乃至上千年，分組交換網(wǎng)絡(luò)只是在這個(gè)事實(shí)被理論化的同時(shí)恰逢網(wǎng)絡(luò)發(fā)展的春天，二者就聯(lián)姻了。
       分組交換的另一個(gè)核心就是統(tǒng)計(jì)復(fù)用。事實(shí)上，早在分組交換還沒(méi)有的時(shí)候，統(tǒng)計(jì)復(fù)用早就存在了幾千年乃至幾千萬(wàn)年。我們生活的世界本身就是統(tǒng)計(jì)復(fù)用的，道路，土地，公共設(shè)施，都是統(tǒng)計(jì)復(fù)用的。
       統(tǒng)計(jì)復(fù)用之所以可被接受，背后的理論依然是排隊(duì)論，即排隊(duì)公平性。當(dāng)然，在歷史的早期，由于沒(méi)有采用統(tǒng)計(jì)復(fù)用從而導(dǎo)致不公平，最終形成了蝴蝶效應(yīng)，隨之國(guó)王，帝國(guó)，統(tǒng)治者相繼出現(xiàn)...不過(guò)，這不是本文討論的。

將任務(wù)(數(shù)據(jù)包，車輛)排隊(duì)過(guò)程和被服務(wù)過(guò)程按時(shí)間分別展開(kāi)

我們把一個(gè)單獨(dú)的排隊(duì)過(guò)程按照時(shí)間展開(kāi)，就會(huì)得到下面的圖示(入隊(duì)速率固定)：

那如果我們把一個(gè)消費(fèi)隊(duì)列里實(shí)體的輸出服務(wù)消費(fèi)的過(guò)程按照時(shí)間展開(kāi)，就會(huì)得到下面的圖示：

任務(wù)(數(shù)據(jù)包，車輛)排隊(duì)過(guò)程和被服務(wù)過(guò)程合并

如 果任由排隊(duì)實(shí)體持續(xù)排隊(duì)，隊(duì)列將會(huì)變得無(wú)限長(zhǎng)。事實(shí)上，任何隊(duì)列都不會(huì)無(wú)限長(zhǎng)，否則大家為何在那排隊(duì)去等待一個(gè)永恒不被接受的服務(wù)....小說(shuō)《十年》里 的那個(gè)廢棄火車站等車的并不存在于現(xiàn)實(shí)。為什么？因?yàn)橹灰信抨?duì)，就會(huì)有服務(wù)處理隊(duì)頭，即排隊(duì)在隊(duì)尾，服務(wù)在隊(duì)頭，這是一個(gè)簡(jiǎn)單的先進(jìn)先出的過(guò)程。
       那么，我們把上面兩個(gè)圖合并，就會(huì)發(fā)現(xiàn)，合并后的兩條曲線中間的帶狀，就是隊(duì)列，如下圖所示：

任務(wù)在固定速率輸入情形下的排隊(duì)分析

1.任務(wù)輸入率和服務(wù)的吸收率相等的情形

這 種情況，從初始狀態(tài)開(kāi)始，是不會(huì)產(chǎn)生排隊(duì)現(xiàn)象的，比如單位時(shí)間到達(dá)三個(gè)人需要服務(wù)，而服務(wù)臺(tái)擁有三個(gè)服務(wù)員，忽略服務(wù)時(shí)間的假設(shè)下，每單位時(shí)間總是會(huì)有三 個(gè)服務(wù)員為人民服務(wù)。但是一旦加入其它的因素，比如處理某個(gè)人的業(yè)務(wù)過(guò)久(服務(wù)時(shí)間是不能忽略的)，就會(huì)產(chǎn)生排隊(duì)現(xiàn)象，一旦某個(gè)服務(wù)被延遲，就會(huì)總體拖慢 服務(wù)輸出率，這是導(dǎo)致排隊(duì)的主因。

2.任務(wù)輸入率和服務(wù)的吸收率不等的情形

如果服務(wù)輸出率大于隊(duì)列輸入率且持續(xù)大于，那么隊(duì)列最終會(huì)消失，如果持續(xù)小于隊(duì)列輸入率，隊(duì)列會(huì)越來(lái)越長(zhǎng)，這些都是常識(shí)，但是這些都是深入分析的基礎(chǔ)。

3.結(jié)論

我們從下圖的分析可以看出，增加服務(wù)資源一點(diǎn)點(diǎn)即可，不需要增加太多，我們要達(dá)到的效果就是，偏差一個(gè)角度，讓服務(wù)輸出曲線和隊(duì)列輸入曲線最終相交即可：

真實(shí)情況：輸入的泊松分布與輸入間隔的指數(shù)分布

前 面的分析和圖示，讓我們感覺(jué)到排隊(duì)系統(tǒng)是多么的不穩(wěn)定啊，要么隊(duì)列變?yōu)?，要么持續(xù)增長(zhǎng)。持有這種觀點(diǎn)的，一定會(huì)質(zhì)疑路由器的可用性?？墒鞘聦?shí)上，不管在 現(xiàn)實(shí)中，比如高速公路擁堵，搶購(gòu)物品，買(mǎi)票還是網(wǎng)絡(luò)世界，比如路由器，交換機(jī)，服務(wù)器，我們都沒(méi)有看到過(guò)隊(duì)列快速變?yōu)?或者持續(xù)增長(zhǎng)的情況，隊(duì)列總是在波 動(dòng)，排隊(duì)的實(shí)體除非自己放棄，不然總會(huì)得到服務(wù)，隊(duì)列也從來(lái)沒(méi)有無(wú)限加長(zhǎng)。這是為什么？
       因?yàn)榕抨?duì)的入隊(duì)率并不是一個(gè)常數(shù)，而是符合泊松分布的一個(gè)范圍，說(shuō)白了就是，入隊(duì)率有一個(gè)平均值，偏離這個(gè)平均值越多的入隊(duì)率，越是不可能看到的。比如說(shuō) 一個(gè)入隊(duì)率平均值是10，那么單位時(shí)間排隊(duì)10個(gè)實(shí)體是最可能的，排隊(duì)9個(gè)或者11也是次可能的，8個(gè)或者12個(gè)，7個(gè)或者13個(gè)，都有可能，...那么 1個(gè)或者19個(gè)相對(duì)于前面那些，就顯得可能性很小了。
      由于入隊(duì)率的泊松分布，相鄰兩個(gè)排隊(duì)實(shí)體的排隊(duì)間隔也應(yīng)該有一個(gè)分布規(guī)律，這是可以從泊松分布推導(dǎo)出來(lái)的，由于數(shù)學(xué)只是一個(gè)工具，我就不貼推導(dǎo)過(guò)程了，直 接貼出答案，相鄰排隊(duì)實(shí)體的排隊(duì)間隔符合指數(shù)分布，意思是說(shuō)，下一個(gè)排隊(duì)者最可能會(huì)在最短的時(shí)間到來(lái)，比如1分鐘內(nèi)，如果5分鐘還沒(méi)有來(lái)，你指望它15分 鐘內(nèi)來(lái)的希望也是比較渺茫的，這也叫做“下一個(gè)馬上到”定律。這是非常符合常識(shí)的，比如你在等人的時(shí)候，他如果遲到了20分鐘，那么他很可能就不會(huì)來(lái)了， 比如面試，如果你面試完還沒(méi)回到家，剛剛面試的公司就打來(lái)電話了，那么你很有可能被錄取了。
       這就是泊松分布和指數(shù)分布下真實(shí)的排隊(duì)場(chǎng)景。

任務(wù)輸入速率符合泊松分布前提下的排隊(duì)分析

真實(shí)的排隊(duì)場(chǎng)景如下圖所示：

把圖放遠(yuǎn)看，你會(huì)忽略些許彎曲的細(xì)節(jié)，整個(gè)輸入曲線就是一個(gè)直線，實(shí)際上服務(wù)輸出曲線也一樣，這正如分形理論闡述的一樣。有兩點(diǎn)要牢記：

a).大部分情形下，輸入率都是平均輸入率，起碼向平均輸入率收斂(泊松分布起作用了)；
b).大部分情形下，在符合a的前提下，下一個(gè)排隊(duì)者馬上就到(指數(shù)分布起作用了)。

高速公路上的排隊(duì)擁堵與緩解

排隊(duì)擁堵示例

1.單車道情形

前 車停止，后面的車便無(wú)法通過(guò)，畢竟它們不會(huì)飛。那么就會(huì)造成排隊(duì)，前面的車按照停車之間的固定速率開(kāi)行，車隊(duì)里的車輛一輛接著一輛出隊(duì)，然而隊(duì)列并不會(huì)快 速消失，因?yàn)殛?duì)尾還有很多車輛在陸續(xù)入隊(duì)，如果入隊(duì)速率和出隊(duì)速率一致，則隊(duì)列永遠(yuǎn)不會(huì)消失，如果出隊(duì)速率小于入隊(duì)速率，則隊(duì)列永遠(yuǎn)不會(huì)消失，還會(huì)持續(xù)加 長(zhǎng)，如果出隊(duì)速率大于入隊(duì)速率，則隊(duì)列最終消失。

2.雙車道不考慮加塞，變道情形

這種情況幾乎可以不考慮，因?yàn)樗聦?shí)上不可能在一個(gè)統(tǒng)計(jì)復(fù)用的信道中發(fā)生。這種情況說(shuō)的是一個(gè)帶有“隊(duì)頭擁塞”的車道與一條正常不排隊(duì)的車道的無(wú)干涉疊加，兩根車道互不影響，一根車道完全停滯，另一根車道全速暢通，你見(jiàn)過(guò)這種情況嗎？反正我是沒(méi)有。
       這是為什么？
       統(tǒng)計(jì)復(fù)用網(wǎng)絡(luò)或者通道建立的前提之一就是排隊(duì)公平性！這是核心中的核心，也正是因?yàn)檫@個(gè)原則，分組交換網(wǎng)絡(luò)才有了理論合理性，才具有可用性。考慮電路交換 網(wǎng)或者火車，通道是專有的，通道存在其間，即便是空閑也不能被他人借用。每個(gè)通信實(shí)體要想使用通道，都必須申請(qǐng)一條專用的，自己私用，后來(lái)鑒于節(jié)約資源考 慮，有了各種復(fù)用，然而這些復(fù)用的粒度還是很粗，仍然會(huì)有空閑間隙。以京廣線上的火車TDM為例，雖然很多列火車都在不同的時(shí)間共享這條鐵路線，但是你依 然會(huì)看到大量的時(shí)間，鐵路上是無(wú)車通行的，這種嚴(yán)格的時(shí)隙復(fù)用是嚴(yán)格的，需要相當(dāng)?shù)臅r(shí)鐘同步機(jī)制，因此相鄰的兩個(gè)時(shí)隙之間的間隙要足夠長(zhǎng)，開(kāi)銷巨大，或者 說(shuō)對(duì)于運(yùn)輸任務(wù)并不固定的地方鐵路貨運(yùn)來(lái)講，你無(wú)法保證今天分給貨車A的時(shí)間間隙T一定會(huì)被貨車A用到，因?yàn)樗裉炜赡軟](méi)有運(yùn)輸任務(wù)。那如果要把時(shí)隙T再 分給別人，就需要復(fù)雜的調(diào)度機(jī)制...最高尚且合理的方案是什么？就是徹底消除浪費(fèi)。復(fù)用粒度進(jìn)一步變小，最終消除中心管控，變成完全的自由市場(chǎng)，由通信 實(shí)體自己根據(jù)自己需求來(lái)決定復(fù)用流程，這就是統(tǒng)計(jì)復(fù)用。
       沒(méi)有規(guī)則就是最好的規(guī)則！
       最重要的無(wú)規(guī)則就是插隊(duì)，加塞，見(jiàn)縫插針。這是存在，也就是合理的，因?yàn)樗械膹?fù)用都要有一個(gè)前提，那就是公平性，完全的私用通道，TDM，F(xiàn)DM都不會(huì) 造成排隊(duì)，因?yàn)閷?duì)于多個(gè)通信實(shí)體，它們的通道在物理上或者邏輯上是分離的，然而對(duì)于統(tǒng)計(jì)復(fù)用，通道是完全混合的，公平性需要自行構(gòu)建。暢行無(wú)阻時(shí)，大家都 是公平的，不公平的時(shí)刻永遠(yuǎn)都是在出現(xiàn)排隊(duì)，擁塞的情況下才會(huì)被感知，因此就需要一種在排隊(duì)時(shí)期也需要的公平機(jī)制，這個(gè)機(jī)制就是加塞，變道，也就是自行構(gòu) 建虛擬輸出隊(duì)列(VOQ)。排隊(duì)車道在排隊(duì)的車輛擁有這個(gè)權(quán)利，因?yàn)樗鼈兒驼＼嚨郎险Ｐ旭偟能囕v是完全等位的，是隊(duì)頭造成了排隊(duì)擁塞，與排隊(duì)者無(wú)關(guān)， 排隊(duì)者排隊(duì)是無(wú)辜的，體現(xiàn)了不公平，為了采取公平措施，只能拉低全部車道的暢通質(zhì)量。

3.為什么擁堵會(huì)快速蔓延

在理解 了上述分析以后，你會(huì)看到，指數(shù)分布下，下一個(gè)排隊(duì)者馬上就來(lái)，不管是針對(duì)泊松分布的期望，還是針對(duì)泊松分布的邊緣，都是如此。下一個(gè)排隊(duì)者總是最可能在 最短的時(shí)間間隔內(nèi)到來(lái)，這就是迅速蔓延的根本。對(duì)比上面的圖示，可以看到，兩條曲線之間的帶狀區(qū)域，它會(huì)迅速增大面積，導(dǎo)致局部擁塞引發(fā)全局擁塞。

4.真實(shí)情形：普遍排隊(duì)，大面積擁堵

以 上講了為何在高速公路排隊(duì)擁堵時(shí)不可能不加塞，那么真實(shí)的情況是什么呢？不說(shuō)大家也明白，有時(shí)候在高速公路上堵了一小時(shí)，緩慢前行，到前面發(fā)現(xiàn)離自己最遠(yuǎn) 的一根車道上兩輛車輕微碰擦...單向4車道的寬闊道路，最外側(cè)車道的事故怎么會(huì)影響到最內(nèi)側(cè)車道，怎么會(huì)帶來(lái)大面積，可能超級(jí)幾十公里的排隊(duì)長(zhǎng)度？
       前面的1，2情形，都是不允許加塞，變道的情形，因此它只影響一根車道，也就是說(shuō)造成一根車道的排隊(duì)擁堵。真實(shí)情況是，這根排隊(duì)的車道上的車輛肯定會(huì)覺(jué)得 這不公平-這是前面提到的，這種情況在路由器中叫做”隊(duì)頭擁塞(HOL，Head of Line)“，由于車輛和數(shù)據(jù)包不同，它們是自路由的，于是排隊(duì)車道的車輛開(kāi)始自行建力VOQ，即虛擬輸出隊(duì)列，說(shuō)白了就是加塞，變道，變道到不排隊(duì)的車 道上，后者會(huì)引發(fā)進(jìn)一步的VOQ自鍵過(guò)程，連鎖反應(yīng)，如此一來(lái)，排隊(duì)擁堵車道的流量就均分到正常車道上了，于是乎正常車道的輸入率超過(guò)了常規(guī)。引發(fā)正常車 道上同樣出現(xiàn)排隊(duì)...
       這種情況和TCP/IP網(wǎng)絡(luò)的情形完全一致，即不管是對(duì)于車輛還是對(duì)于數(shù)據(jù)包，網(wǎng)絡(luò)都是統(tǒng)計(jì)復(fù)用的，并不存在什么嚴(yán)格的規(guī)則，比如嚴(yán)格TDM，F(xiàn)DM等， 說(shuō)得明白點(diǎn)就是見(jiàn)縫插針，通道只要空著，你不用時(shí)我就用，還記得CSMA/CD嗎？基本就是這樣。一輛車和前車車距超過(guò)安全距離時(shí)，就會(huì)有旁邊車道的車子 想加塞，他會(huì)首先來(lái)一個(gè)“載波監(jiān)聽(tīng)，沖突檢測(cè)”，比如閃燈，以確保自己的行為被后車知道，如此等等。雖然這不是什么好的紳士風(fēng)度，但是這就是所有統(tǒng)計(jì)復(fù)用 通道的本質(zhì)。這是一個(gè)冒險(xiǎn)求效率的過(guò)程，也可以說(shuō)是一個(gè)互惠共贏的局面，這局面中沖突在統(tǒng)計(jì)復(fù)用潛規(guī)則(若沒(méi)有潛在的規(guī)則，你能想象在擁堵的市中心，各種 箱貨車，轎車，行人，電瓶車，畢竟竟然毫無(wú)碰擦，你要知道后視鏡是有死角的，而司機(jī)也不見(jiàn)得各個(gè)都能把握自己車子的長(zhǎng)寬高已經(jīng)轉(zhuǎn)矩...)影響下永遠(yuǎn)都是 局部的，少量的事件，因此值得冒險(xiǎn)，然而一旦發(fā)生沖突，比如碰擦，事故等，就會(huì)造成全局的大面積擁塞，這個(gè)我們前面已經(jīng)提到，那么接下來(lái)要說(shuō)的是，這種排 隊(duì)擁堵是如何得到緩解的呢？它一定會(huì)得到緩解，若不是如此，這種統(tǒng)計(jì)復(fù)用的網(wǎng)絡(luò)便完全不可用！且接著讀。

高速公路的排隊(duì)擁堵是怎么緩解的

我 們知道，道路是會(huì)擁堵的，但是這種擁堵總是會(huì)緩解的，按照理想情況，以固定輸入率到達(dá)且以固定輸出率輸出的車輛一旦排隊(duì)，隊(duì)列將永遠(yuǎn)保持，這也是上面的理 論分析得到的結(jié)論，然而真實(shí)的情況是，雖然在排隊(duì)擁堵緩解的那一刻，輸出率是固定的，但是輸入率并不固定，輸入率的泊松分布使得擁堵最終緩解。
       誠(chéng)然，增加一根車道，相當(dāng)于增加了服務(wù)資源一點(diǎn)點(diǎn)。依照我們前面的討論，考慮固定速率的輸入和固定的服務(wù)率，即固定的服務(wù)資源，如果輸入曲線和輸出服務(wù)曲 線二者平行，擁堵期間造成的隊(duì)列將永遠(yuǎn)存在，且隊(duì)列長(zhǎng)度不變，但是如果增加哪怕一根車道，輸出服務(wù)的曲線就會(huì)向上陡一些，終究會(huì)和輸入曲線相交，使隊(duì)列消 失?？芍^一種差之毫厘，謬以千里的效果。
       當(dāng)然，考慮到真實(shí)情況無(wú)疑要復(fù)雜的多，要考慮到加塞，變道等不文明行為導(dǎo)致的擁塞進(jìn)一步加劇，當(dāng)然這是壞的一方面。那么在真實(shí)情況下，好的一方面是，輸入 曲線并不是一根直線，其斜率是可變的，怎么變呢？簡(jiǎn)單的來(lái)講，就是這條曲線的趨勢(shì)還是如固定輸入率的方向所指向，但是其每一個(gè)點(diǎn)的協(xié)議總的來(lái)講是符合泊松 分布的，其期望值就是固定輸入率的斜率！我們來(lái)看一下這個(gè)泊松分布在輸出服務(wù)恢復(fù)時(shí)是怎么救我們出泥潭的。分兩種情況。
情況1：輸出服務(wù)暫停-比如兩車碰擦或者交通事故導(dǎo)致了車道封閉
在事故未疏通時(shí)，泊松分布對(duì)擁堵是沒(méi)有效果的，無(wú)論如何，到來(lái)的車輛只是加長(zhǎng)了排隊(duì)的隊(duì)列，只是說(shuō)由于車輛到來(lái)速率符合泊松分布，有時(shí)候來(lái)的車多一點(diǎn)，有時(shí)候少一點(diǎn)，不管怎樣，隊(duì)列長(zhǎng)度均增加，只是增加的速度不同。
       等到事故疏通以后，事故點(diǎn)的交通完全恢復(fù)，排在隊(duì)列第一個(gè)的車子首先發(fā)動(dòng)開(kāi)走，緊接著是第二輛，然后第三輛...此時(shí)事故點(diǎn)的車子離開(kāi)速率是固定的，且是 全速率的，好像這個(gè)地點(diǎn)的車輛通過(guò)率達(dá)到了泊松分布中概率最小的最大值一樣，此時(shí)隊(duì)列尾部的車輛到達(dá)率還是符合標(biāo)準(zhǔn)的泊松分布。在隊(duì)列未消失之前，事故點(diǎn) 即隊(duì)列頭的車輛通行率都是固定的，且大于隊(duì)列尾部的車輛到達(dá)率，久之，隊(duì)列消失。
       如果隊(duì)列尾部的車輛到達(dá)率和隊(duì)列頭的車輛通行率相等，那么隊(duì)列將永遠(yuǎn)維持！
情況2：輸出服務(wù)延緩-比如遇到了收費(fèi)站
考 慮車道數(shù)量和收費(fèi)窗口數(shù)量相等的情況，按照前面的分析，由于收費(fèi)站就在那里，且永遠(yuǎn)不會(huì)消失，因此它造成的排隊(duì)擁堵便”永遠(yuǎn)不會(huì)恢復(fù)到正?！?，因此情況1 的解釋便不能用于情況2，可是我們依然看到事實(shí)上高速公路在非節(jié)假日時(shí)并不會(huì)因?yàn)槭召M(fèi)站而大面積不可恢復(fù)的排隊(duì)擁堵，這是為什么呢？
       因?yàn)槭召M(fèi)窗口數(shù)量要大于車道數(shù)量，雖然它增加了單輛車的延遲，但是它卻可以并行處理多輛車，所以總的吞吐(或者說(shuō)線速能力)并沒(méi)有變化，總的來(lái)看，排隊(duì)擁堵還是緩解了。
       這情況2值得注意，這就是路由器的做法??！
       本節(jié)最后，我們看一個(gè)基本事實(shí)。上海境內(nèi)滬嘉高速(S5高速)，于2012年前后拆除了收費(fèi)站，于2013年前后拆除了中央隔離綠化帶，與兩側(cè)硬路肩一起 增加了單向一根車道。想想這是為什么？為什么只在單向增加了一根車道而不是兩根，為什么拆了收費(fèi)站增加了一根車道這種簡(jiǎn)單的事就帶來(lái)了容量的大增。通過(guò)上 面的分析應(yīng)該可以得到答案，注意，不要單單從收費(fèi)與否與車主的利益上考慮。
       還有一個(gè)思考題，那就是古羅馬帝國(guó)道路系統(tǒng)的設(shè)計(jì)，但是這不是排隊(duì)擁堵問(wèn)題的范疇，而是連通性問(wèn)題的范疇，連通性怎么帶來(lái)收益指數(shù)級(jí)倍增的？

高速公路收費(fèi)站節(jié)假日免費(fèi)的另一個(gè)原因
并 不僅僅是錢(qián)的問(wèn)題，而是收費(fèi)站本身就不合理。我說(shuō)一句類似的，就是大流量時(shí)，骨干路由器會(huì)消除一些針對(duì)流量的審計(jì)策略，留給認(rèn)證過(guò)的可信任BGP另一端， 入IGP域內(nèi)部的邊緣路由器來(lái)完成這種審計(jì)功能，是不是和節(jié)假日取消收費(fèi)類似呢？是它容量吃不消，不是因?yàn)橄霝榇蠹沂″X(qián)，錢(qián)是省不了的，全體開(kāi)車出行，全 交給旅游景點(diǎn)了...
       高速公路跟路由器一樣，在設(shè)計(jì)之初，其平均容量，最大容量，最惡劣的排隊(duì)時(shí)延，收費(fèi)站時(shí)延，并行度都是經(jīng)過(guò)復(fù)雜數(shù)學(xué)計(jì)算的，其不可避免地要涉及到泊松分 布，指數(shù)分布，另外心理學(xué)，氣候因素等也有極重的權(quán)值，而這個(gè)計(jì)算結(jié)果并不會(huì)針對(duì)突發(fā)流量，也就是說(shuō)，任何組織都不會(huì)將高速公路，路由器緩沖區(qū)設(shè)計(jì)成以突 發(fā)流量為基準(zhǔn)的系統(tǒng)，這樣的話，過(guò)高的成本帶不來(lái)可觀的收益，但是如果真的是這樣，那真就是為人民服務(wù)了。這種排隊(duì)系統(tǒng)得設(shè)計(jì)只是針對(duì)平均容量的，總?cè)萘?會(huì)比平均容量稍微大一點(diǎn)，以應(yīng)對(duì)不可預(yù)知的小型突發(fā)，更多的時(shí)候，完全依靠以下的冒險(xiǎn)假設(shè)來(lái)緩解排隊(duì)擁堵：
輸入曲線是一條彎彎曲曲的曲線，總趨勢(shì)為一條直線，其斜率為輸入率期望值，而大多數(shù)時(shí)候的情況下，輸出服務(wù)率只要比輸入期望稍微大一點(diǎn)點(diǎn)即可，以達(dá)到大多數(shù)時(shí)候，輸出服務(wù)曲線可以向上追趕輸入曲線，大多數(shù)情況下可以使兩條曲線相交即可！

路由器緩沖區(qū)大小以及調(diào)度算法的設(shè)置

在 分析了這么多之后，你是不是突然發(fā)現(xiàn)，該為路由器設(shè)置多少緩沖區(qū)-即排隊(duì)區(qū)域，并不是一件很簡(jiǎn)單的事。因?yàn)槟阋孪阮A(yù)測(cè)平均流量，最小流量，最小流量持續(xù) 時(shí)間，最大突發(fā)流量，突發(fā)流量的持續(xù)時(shí)間，突發(fā)時(shí)間段，然后作出一個(gè)基于服務(wù)質(zhì)量-分解為輸入率和輸出率，成本之間馬鞍面那個(gè)可以坐人位置的判斷?？傊?路由器的緩沖區(qū)可能是動(dòng)態(tài)變化的，這里面的數(shù)學(xué)計(jì)算特別復(fù)雜，其根本就是一場(chǎng)博弈，因此除了排隊(duì)論之外，你還要了解博弈論。
       緩沖區(qū)的設(shè)置僅僅針對(duì)輸入，對(duì)于輸出，還要有一個(gè)調(diào)度算法的設(shè)置。真的，路由器比高速公路復(fù)雜多了，因?yàn)楦咚俟返能囕v是自路由，自建輸出隊(duì)列的(通過(guò)轉(zhuǎn)向燈，加塞變道等行為)，而路由器則是完全靠路由器內(nèi)部的算法進(jìn)行盲導(dǎo)航的。
       不過(guò)，真的希望高速公路的例子可以讓人更加理解路由器的本質(zhì)，together with分組交換以及統(tǒng)計(jì)復(fù)用的本質(zhì)。