本節書摘來華章計算機《計算機網絡：自頂向下方法（原書第6版）》一書中的第1章 ，第1.4節，（美）james f.kurose keith w.ross 著 陳 鳴 譯 更多章節内容可以通路雲栖社群“華章計算機”公衆号檢視。
回想在1.1節中我們講過，網際網路能夠看成是一種為運作在端系統上的分布式應用提供服務的基礎設施。在理想情況下，我們希望網際網路服務能夠在任意兩個端系統之間瞬間移動我們想要的大量資料而沒有任何資料丢失。然而，這是一個極高的目标，實踐中難以達到。與之相反，計算機網絡必定要限制在端系統之間的吞吐量（每秒能夠傳送的資料量），在端系統之間引入時延，而且實際上能夠丢失分組。一方面，現實世界的實體定律引入的時延、丢包并限制吞吐量是不幸的。而另一方面，因為計算機網絡存在這些問題，圍繞如何去處理這些問題有許多令人着迷的話題，多得足以開設一門有關計算機網絡方面的課程，可以做上千篇博士論文！在本節中，我們将開始研究和量化計算機網絡中的時延、丢包和吞吐量等問題。
前面講過，分組從一台主機（源）出發，通過一系列路由器傳輸，在另一台主機（目的地）中結束它的曆程。當分組從一個結點（主機或路由器）沿着這條路徑到後繼結點（主機或路由器），該分組在沿途的每個結點經受了幾種不同類型的時延。這些時延最為重要的是結點處理時延（nodal processing delay）、排隊時延（queuing delay）、傳輸時延（transmission delay）和傳播時延（propagation delay），這些時延總體累加起來是結點總時延（total nodal delay）。許多網際網路應用，如搜尋、web浏覽、電子郵件、地圖、即時訊息和ip語音，它們的性能受網絡時延的影響都很大。為了深入了解分組交換和計算機網絡，我們必須了解這些時延的性質和重要性。
時延的類型
我們來探讨一下圖1-16環境中的這些時延。作為源和目的地之間的端到端路徑的一部分，一個分組從上遊結點通過路由器a向路由器b發送。我們的目标是在路由器a刻畫出結點時延。值得注意的是，路由器a具有通往路由器b的對外連結路。該鍊路前面有一個隊列（也稱為緩存）。當該分組從上遊結點到達路由器a時，路由器a檢查該分組的首部以決定該分組的适當對外連結路，并将該分組導向該鍊路。在這個例子中，對該分組的對外連結路是通向路由器b的那條鍊路。僅當在該鍊路沒有其他分組正在傳輸并且沒有其他分組排在該隊列前面時，才能在這條鍊路上傳輸該分組；如果該鍊路目前正繁忙或有其他分組已經在該鍊路上排隊，則新到達的分組則将參與排隊。
檢查分組首部和決定将該分組導向何處所需要的時間是處理時延的一部分。處理時延也能包括其他因素，如檢查比特級别的差錯所需要的時間，該差錯出現在從上遊結點向路由器a傳輸這些分組比特的過程中。高速路由器的處理時延通常是微秒或更低的數量級。在這種結點處理之後，路由器将該分組引向通往路由器b鍊路之前的隊列。（在第4章中，我們将研究路由器運作的細節。）
（2）排隊時延
在隊列中，當分組在鍊路上等待傳輸時，它經受排隊時延。一個特定分組的排隊時延長度将取決于先期到達的正在排隊等待向鍊路傳輸的分組數量。如果該隊列是空的，并且目前沒有其他分組正在傳輸，則該分組的排隊時延為0。另一方面，如果流量很大，并且許多其他分組也在等待傳輸，該排隊時延将很長。我們将很快看到，到達分組期待發現的分組數量是到達該隊列的流量的強度和性質的函數。實際的排隊時延可以是毫秒到微秒量級。
（3）傳輸時延
假定分組以先到先服務方式傳輸，這在分組交換網中是常見的方式，僅當所有已經到達的分組被傳輸後，才能傳輸剛到達的分組。用l比特表示該分組的長度，用r bps(即b/s)表示從路由器a到路由器b的鍊路傳輸速率。例如，對于一條10mbps的以太網鍊路，速率r=10mbps；對于100mbps的以太網鍊路，速率r=100mbps。傳輸時延是l/r。這是将所有分組的比特推（傳輸）向鍊路所需要的時間。實際的傳輸時延通常在毫秒到微秒量級。
（4）傳播時延
一旦一個比特被推向鍊路，該比特需要向路由器b傳播。從該鍊路的起點到路由器b傳播所需要的時間是傳播時延。該比特以該鍊路的傳播速率傳播。該傳播速率取決于該鍊路的實體媒體（即光纖、雙絞銅線等），其速率範圍是2×108～3×108m/s，這等于或略小于光速。該傳播時延等于兩台路由器之間的距離除以傳播速率。即傳播時延是d/s，其中d是路由器a和路由器b之間的距離，s是該鍊路的傳播速率。一旦該分組的最後一個比特傳播到結點b，該比特及前面的所有比特被存儲于路由器b。整個過程将随着路由器b執行轉發而持續下去。在廣域網中，傳播時延為毫秒量級。
（5）傳輸時延和傳播時延的比較
計算機網絡領域的新手有時難以了解傳輸時延和傳播時延之間的差異。該差異是微妙而重要的。傳輸時延是路由器将分組推出所需要的時間，它是分組長度和鍊路傳輸速率的函數，而與兩台路由器之間的距離無關。另一方面，傳播時延是一個比特從一台路由器向另一台路由器傳播所需要的時間，它是兩台路由器之間距離的函數，而與分組長度或鍊路傳輸速率無關。
一個類比可以闡明傳輸時延和傳播時延的概念。考慮一條公路每100km有一個收費站，如圖1-17所示。可認為收費站間的公路段是鍊路，收費站是路由器。假定汽車以100km/h的速度在該公路上行駛（即傳播）（即當一輛汽車離開一個收費站時，它立即加速到100km/h并在收費站間維持該速度）。假定這時有10輛汽車的車隊在行駛，并且這10輛汽車以固定的順序互相跟随。可以認為每輛汽車是一個比特，該車隊是一個分組。同時假定每個收費站以每輛車12s的速度服務（即傳輸）一輛汽車，由于時間是深夜，是以該車隊是公路上唯一一批汽車。最後，假定無論該車隊的第一輛汽車何時到達收費站，它在入口處等待，直到其他9輛汽車到達并整隊依次前行。（是以，整個車隊在它能夠“轉發”之前，必須存儲在收費站。）收費站将整個車隊推向公路所需要的時間是（10輛車）/（5輛車/min）=2min。該時間類比于一台路由器中的傳輸時延。是以，一輛汽車從一個收費站出口行駛到下一個收費站所需要的時間是100h/（100km/h）=1h。這個時間類比于傳播時延。是以，從該車隊存儲在收費站前到該車隊存儲在下一個收費站前的時間是“傳輸時延”和“傳播時間”總和，在本例中為62min。
我們更深入地探讨一下這個類比。如果收費站對車隊的服務時間大于汽車在收費站之間行駛的時間，将會發生什麼情況呢？例如，假定現在汽車是以1000km/h的速率行駛，收費站是以每分鐘一輛汽車的速率為汽車服務。則汽車在兩個收費站之間的行駛時延是6min，收費站為車隊服務的時間是10min。在此情況下，在該車隊中的最後幾輛汽車離開第一個收費站之前，該車隊中前面的幾輛汽車将會達到第二個收費站。這種情況在分組交換網中也會發生，一個分組中的前幾個比特到達了一台路由器，而該分組中許多餘下的比特仍然在前面的路由器中等待傳輸。
如果說一圖勝千言的話，則一個動畫必定勝百萬言。與本書配套的web網站提供了一個互動式java小程式，它很好地展現及對比了傳輸時延和傳播時延。我們極力推薦讀者通路該java小程式。［smith 2009］也提供了可讀性很好的有關傳播、排隊和傳輸時延的讨論。
如果我們令dproc、dqueue、dtrans和dprop分别表示處理時延、排隊時延、傳輸時延和傳播時延，則結點的總時延由下式給定：
這些時延成分所起的作用可能變化很大。例如，dprop對于連接配接兩台位于同一個大學校園的路由器的鍊路而言可能是微不足道的（例如，幾個微秒）；然而，dproc對于由同步衛星鍊路互聯的兩台路由器來說是幾百毫秒，能夠成為dnodal中的主要成分。類似地，dtrans的影響能夠是微不足道的，也能是很大的。它的影響通常對于10mbps和更高的傳輸速率（例如，對于lan）的信道而言是微不足道的；然而，對于通過低速撥号數據機鍊路發送的長網際網路分組而言，可能是數百毫秒。處理時延dproc通常是微不足道的；然而，它對一台路由器的最大吞吐量有重要影響，最大吞吐量是一台路由器能夠轉發分組的最大速率。
結點時延的最為複雜和有趣的成分是排隊時延dqueue。事實上，排隊時延在計算機網絡中的重要程度及人們對它感興趣的程度，從發表的數以千計的論文和大量專著的情況可見一斑［bersekas 1991;daigle 1991;kleinrock 1975，1976;ross 1995］。我們這裡僅給出有關排隊時延的總體的、直覺的讨論；求知欲強的讀者可能要浏覽某些書籍（或者最終寫有關這方面的博士論文）。與其他3項時延（即dproc、dtrans和dprop）不同的是，排隊時延對不同的分組可能是不同的。例如，如果10個分組同時到達空隊列，傳輸的第一個分組沒有排隊時延，而傳輸的最後一個分組将經受相對大的排隊時延（這時它要等待其他9個分組被傳輸）。是以，當表征排隊時延時，人們通常使用統計量測度，如平均排隊時延、排隊時延的方差和排隊時延超過某些特定值的機率。
什麼時候排隊時延大，什麼時候又不大呢？該問題的答案很大程度取決于流量到達該隊列的速率、鍊路的傳輸速率和到達流量的性質，即流量是周期性到達還是以突發形式到達。為了更深入地領會某些要點，令a表示分組到達隊列的平均速率（a的機關是分組/秒，即pkt/s）。前面講過r是傳輸速率，即從隊列中推出比特的速率（以bps即b/s為機關）。為了簡單起見，也假定所有分組都是由l比特組成的。則比特到達隊列的平均速率是la bps。最後，假定該隊列非常大，是以它基本能容納無限數量的比特。比率la/r被稱為流量強度（traffic intensity），它在估計排隊時延的範圍方面經常起着重要的作用。如果la/r>1，則比特到達隊列的平均速率超過從該隊列傳輸出去的速率。在這種不幸的情況下，該隊列趨向于無界增加，并且排隊時延将趨向無窮大！是以，流量工程中的一條金科玉律是：設計系統時流量強度不能大于1。
現在考慮la/r≤1時的情況。這時，到達流量的性質影響排隊時延。例如，如果分組周期性到達，即每l/r秒到達一個分組，則每個分組将到達一個空隊列中，不會有排隊時延。在另一方面，如果分組以突發形式到達而不是周期性到達，則有很大的平均排隊時延。例如，假定每(l/r)n秒同時到達n個分組。則傳輸的第一個分組沒有排隊時延；傳輸的第二個分組就有l/r秒的排隊時延；更為一般地，第n個傳輸的分組具有（n-1）l/r秒的排隊時延。我們将該例子中的計算平均排隊時延的問題留給讀者作為練習。
以上描述周期性到達的兩個例子有些學術味。到達隊列的過程通常是随機的，即到達并不遵循任何模式，分組之間的時間間隔是随機的。在這種更為真實的情況下，量la/r通常不足以全面地表征時延的統計量。不過，直覺地了解排隊時延的範圍很有用。特别是，如果流量強度接近于0，則幾乎沒有分組到達并且到達間隔很大，那麼到達的分組将不可能在隊列中發現别的分組。是以，平均排隊時延将接近0。在另一方面，當流量強度接近1時，将存在到達率超過傳輸能力的時間間隔（由于分組到達率的波動），在這些時段中将形成隊列。無論如何， 圖1-18 平均排隊時延與
流量強度的關系随着流量強度接近1，平均排隊長度變得越來越長。平均排隊時延與流量強度的定性關系如圖1-18所示。
圖1-18的一個重要方面是這樣一個事實：随着流量強度接近于1，平均排隊時延迅速增加。該強度少量的增加将導緻時延大得多的增加。也許你在公路上經曆過這種事。如果經常在通常擁塞的公路上駕駛，這條路經常擁塞的事實意味着它的流量強度接近于1。如果某些事件引起一個甚至稍微大于平常量的流量，經受的時延就可能很大。
為了真實地感受一下排隊時延的情況，我們再次鼓勵你通路本書的web網站，該網站提供了一個有關隊列的互動式java小程式。如果你将分組到達率設定得足夠大，使流量強度超過1，那麼将看到經過一段時間後，隊列慢慢地建立起來。
丢包
在上述讨論中，我們已經假設隊列能夠容納無窮多的分組。在現實中，一條鍊路前的隊列隻有有限的容量，盡管排隊容量極大地依賴于路由器設計和成本。因為該排隊容量是有限的，随着流量強度接近1，排隊時延并不實際趨向無窮大。相反，到達的分組将發現一個滿的隊列。由于沒有地方存儲這個分組，路由器将丢棄（drop）該分組，即該分組将會丢失（lost）。當流量強度大于1時，隊列中的這種溢出也能夠在用于隊列的java小程式中看到。
從端系統的角度看，上述丢包現象看起來是一個分組已經傳輸到網絡核心，但它絕不會從網絡發送到目的地。分組丢失的份額随着流量強度增加而增加。是以，一個結點的性能常常不僅根據時延來度量，而且根據分組丢失的機率來度量。正如我們将在後面各章中讨論的那樣，丢失的分組可能基于端到端的原則重傳，以確定所有的資料最終從源傳送到了目的地。
前面的讨論一直集中在結點時延上，即在單台路由器上的時延。我們現在考慮從源到目的地的總時延。為了能夠了解這個概念，假定在源主機和目的主機之間有n-1台路由器。我們還要假設該網絡此時是無擁塞的（是以排隊時延是微不足道的），在每台路由器和源主機上的處理時延是dproc，每台路由器和源主機的輸出速率是r bps，每條鍊路的傳播時延是dprop。結點時延累加起來，得到端到端時延：dend-end=n（dproc+dtrans+dprop）（1-2）式中再次有dtrans=l/r，其中l是分組長度。值得注意的是，式（1-2)是式(1-1)的一般形式，式(1-1)沒有考慮處理時延和傳播時延。在各結點具有不同的時延和每個結點存在平均排隊時延的情況下，需要對式(1-2)進行一般化處理。我們将有關工作留給讀者。
1.traceroute
為了對計算機網絡中的時延有一個第一手認識，我們可以利用traceroute程式。traceroute是一個簡單的程式，它能夠在任何網際網路主機上運作。當使用者指定一個目的主機名字時，源主機中的該程式朝着該目的地發送多個特殊的分組。當這些分組向着目的地傳送時，它們通過一系列路由器。當路由器接收到這些特殊分組之一時，它向源回送一個短封包。該封包包括該路由器名字和位址。
更具體的是，假定在源和目的地之間有n-1台路由器。則源将向網絡發送n個特殊的分組，其中每個分組位址指向最終目的地。這n個特殊分組辨別為從1到n，第一個分組辨別為1，最後的分組辨別為n。當第n台路由器接收到辨別為n的第n個分組時，該路由器不是向它的目的地轉發該分組，而是向源回送一個封包。當目的主機接收第n個分組時，它也會向源傳回一個封包。該源記錄了從它發送一個分組到它接收到對應傳回封包所經受的時間；它也記錄了傳回該封包的路由器（或目的地主機）的名字和位址。以這種方式，源能夠重建分組從源到目的地所采用的路由，并且該源能夠決定到所有中間路由器的往返時延。traceroute實際上對剛才描述的實驗重複了3次，是以該源實際上向目的地發送了3×n個分組。rfc 1393詳細地描述了traceroute。
這裡有一個traceroute程式輸出的例子，其中追蹤的路由從源主機gaia.cs.umass.edu（位于馬薩諸塞大學）到cis.poly.edu（位于布魯克林的理工大學）。輸出有6列：第一列是前面描述的n值，即沿着路徑上的路由器編号；第二列是路由器的名字；第三列是路由器位址（格式為xxx.xxx.xxx.xxx）；最後3列是3次實驗的往返時延。如果源從任何給定的路由器接收到少于3條封包（由于網絡中的丢包），traceroute在該路由器号碼後面放一個星号，并向那台路由器報告少于3次往返時間。
在上述跟蹤中，在源和目的之間有9台路由器。這些路由器中的多數有一個名字，所有都有位址。例如，路由器3的名字是border4-rt-gi-1-3.gw.umass.edu，它的位址是128.119.2.194。看看為這台路由器提供的資料，可以看到在源和路由器之間的往返時延：3次試驗中的第一次是1.03ms，後繼兩次試驗的往返時延是0.48ms和0.45ms。這些往返時延包括剛才讨論的所有時延，即包括傳輸時延、傳播時延、路由器處理時延和排隊時延。因為該排隊時延随時間變化，分組n發送到路由器n的往返時延實際上能夠比分組n+1發送到路由器n+1的往返時延更長。的确，我們在上述例子中觀察到了這種現象：到路由器6的時延比到路由器7的更大！
2.端系統、應用程式和其他時延
除了處理時延、傳輸時延和傳播時延，端系統中還有其他一些重要時延。例如，作為它的協定的一部分，希望向共享媒體（例如在wifi或電纜數據機情況下）傳輸分組的端系統可以有意地延遲它的傳輸以與其他端系統共享媒體；我們将在第5章中詳細地考慮這樣的一些協定。另一個重要的時延是媒體分組化時延，這種時延出現在經ip語音（voip）應用中。在voip中，發送方在向網際網路傳遞分組之前必須首先用編碼的數字化語音填充一個分組。這種填充一個分組的時間稱為分組化時延，它可能較大，并能夠影響使用者感受到的voip呼叫的品質。這個問題将在本章結束的課後作業中進一步探讨。
除了時延和丢包，計算機網絡中另一個必不可少的性能測度是端到端吞吐量。為了定義吞吐量，考慮從主機a到主機b跨越計算機網絡傳送一個大檔案。例如，也許是從一個p2p檔案共享系統中的一個對等方向另一個對等方傳送一個大視訊片段。在任何時間瞬間的瞬時吞吐量（instantaneous throughput）是主機b接收到該檔案的速率（以bps計）。（許多應用程式包括許多檔案共享系統，在下載下傳期間其使用者界面顯示了其瞬時吞吐量，也許你以前已經觀察過它！）如果該檔案由f比特組成，主機b接收到所有f比特用去t秒，則檔案傳送的平均吞吐量（average throughput）是f/t bps。對于某些應用程式如網際網路電話，希望具有低延遲時間和在某個門檻值之上的一緻的瞬時吞吐量。例如，對某些網際網路電話是超過24kbps，對某些實時視訊應用程式是超過256kbps。對于其他應用程式，包括涉及檔案傳送的那些應用程式，時延不是至關重要的，但是希望具有盡可能高的吞吐量。
為了進一步深入了解吞吐量這個重要概念，我們考慮幾個例子。圖1-19a顯示了伺服器和客戶這兩個端系統，它們由兩條通信鍊路和一台路由器相連。考慮從伺服器傳送一個檔案到客戶的吞吐量。令rs表示伺服器與路由器之間的鍊路速率；rc表示路由器與客戶之間的鍊路速率。假定在整個網絡中隻有從這台伺服器到那台客戶的比特在傳送。在這種理想的情況下，我們現在問該伺服器到客戶的吞吐量是多少？為了回答這個問題，我們可以想象比特是流體，通信鍊路是管道。顯然，這台伺服器不能以快于rs bps的速率通過其鍊路注入比特；這台路由器也不能以快于rc bps的速率轉發比特。如果rs
圖1-19b此時顯示了在伺服器和客戶之間具有n條鍊路的一個網絡，這n條鍊路的傳輸速率分别是r1，r2，…，rn。應用與對兩條鍊路網絡的分析相同的方法，我們發現從伺服器到客戶的檔案傳輸的吞吐量是min{r1，r2，…，rn}，這同樣仍是沿着伺服器和客戶之間路徑的瓶頸鍊路的速率。
現在考慮由目前網際網路所引發的另一個例子。圖1-20a顯示了與一個計算機網絡相連的兩個端系統：一台伺服器和一個客戶。考慮從伺服器向客戶的檔案傳送的吞吐量。伺服器以速率為rs的接入速率與網絡相連，且客戶以速率為rc的接入速率與網絡相連。現在假定在計算機網絡核心中的所有鍊路具有非常高的傳輸速率，即該速率比rs和rc要高得多。目前網際網路的核心的确過度裝備了高速率的鍊路，進而很少出現擁塞。同時假定在整個網絡中發送的比特都是從該伺服器到該客戶。在這個例子中，因為計算機網絡的核心就像一個寬大的管子，是以比特從伺服器向目的地的流動速率仍是rs和rc中的最小者，即吞吐量=min{rs，rc}。是以，在今天網際網路中對吞吐量的限制因素通常是接入網。
作為最後一個例子，考慮圖1-20b，其中有10台伺服器和10個客戶與某計算機網絡核心相連。在這個例子中，同時發生10個下載下傳，涉及10個客戶-伺服器對。假定這10個下載下傳是網絡中當時的唯一流量。如該圖所示，在核心中有一條所有10個下載下傳通過的鍊路。将這條鍊路r的傳輸速率表示為r。假定所有伺服器接傳入連結路具有相同的速率rs，所有客戶接傳入連結路具有相同的速率rc，并且核心中除了速率為r的一條共同鍊路之外的所有鍊路傳輸速率都比rs、rc和r大得多。現在我們要問，這種下載下傳的吞吐量是多少？顯然，如果該公共鍊路的速率r很大，比如說比rs和rc大100倍，則每個下載下傳的吞吐量将仍然是min{rs，rc}。但是如果該公共鍊路的速率與rs和rc有相同量級會怎樣呢？在這種情況下其吞吐量将是多少呢？讓我們觀察一個特定的例子。假定rs=2mbps，rc=1mbps，r=5mbps，并且公共鍊路在10個下載下傳之間平等劃分它的傳輸速率。這時每個下載下傳的瓶頸不再位于接入網中，而是位于核心中的共享鍊路了，該瓶頸僅能為每個下載下傳提供500kbps的吞吐量。是以每個下載下傳的端到端吞吐量現在減少到500kbps。
圖1-19和圖1-20中的例子說明吞吐量取決于資料流過的鍊路的傳輸速率。我們看到當沒有其他幹擾流量時，其吞吐量能夠近似為沿着源和目的地之間路徑的最小傳輸速率。圖1-20b中的例子更一般地說明了吞吐量不僅取決于沿着路徑的傳輸速率，而且取決于幹擾流量。特别是，如果許多其他的資料流也通過這條鍊路流動，一條具有高傳輸速率的鍊路仍然可能成為檔案傳輸的瓶頸鍊路。我們将在課後習題中和後繼章節中更仔細地研究計算機網絡中的吞吐量。