本节书摘来华章计算机《计算机网络：自顶向下方法（原书第6版）》一书中的第1章 ，第1.4节，（美）James F.Kurose Keith W.Ross 著 陈 鸣 译 更多章节内容可以访问云栖社区“华章计算机”公众号查看。
1.4 分组交换网中的时延、丢包和吞吐量
回想在1.1节中我们讲过，因特网能够看成是一种为运行在端系统上的分布式应用提供服务的基础设施。在理想情况下，我们希望因特网服务能够在任意两个端系统之间瞬间移动我们想要的大量数据而没有任何数据丢失。然而，这是一个极高的目标，实践中难以达到。与之相反，计算机网络必定要限制在端系统之间的吞吐量（每秒能够传送的数据量），在端系统之间引入时延，而且实际上能够丢失分组。一方面，现实世界的物理定律引入的时延、丢包并限制吞吐量是不幸的。而另一方面，因为计算机网络存在这些问题，围绕如何去处理这些问题有许多令人着迷的话题，多得足以开设一门有关计算机网络方面的课程，可以做上千篇博士论文！在本节中，我们将开始研究和量化计算机网络中的时延、丢包和吞吐量等问题。
1.4.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通常是微不足道的；然而，它对一台路由器的最大吞吐量有重要影响，最大吞吐量是一台路由器能够转发分组的最大速率。
1.4.2 排队时延和丢包
结点时延的最为复杂和有趣的成分是排队时延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小程序中看到。
从端系统的角度看，上述丢包现象看起来是一个分组已经传输到网络核心，但它绝不会从网络发送到目的地。分组丢失的份额随着流量强度增加而增加。因此，一个结点的性能常常不仅根据时延来度量，而且根据分组丢失的概率来度量。正如我们将在后面各章中讨论的那样，丢失的分组可能基于端到端的原则重传，以确保所有的数据最终从源传送到了目的地。
1.4.3 端到端时延
前面的讨论一直集中在结点时延上，即在单台路由器上的时延。我们现在考虑从源到目的地的总时延。为了能够理解这个概念，假定在源主机和目的主机之间有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的更大！
你想自己试试Traceroute程序吗？我们极力推荐你访问http://www.traceroute.org，它的Web界面提供了有关路由跟踪的广泛的源列表。你选择一个源，并为任何目的地提供主机名，该Traceroute程序则会完成所有工作。有许多为Traceroute提供图形化界面的免费软件程序，其中我们喜爱的一个程序是PingPlotter［PingPlotter 2012］。
2.端系统、应用程序和其他时延
除了处理时延、传输时延和传播时延，端系统中还有其他一些重要时延。例如，作为它的协议的一部分，希望向共享媒体（例如在WiFi或电缆调制解调器情况下）传输分组的端系统可以有意地延迟它的传输以与其他端系统共享媒体；我们将在第5章中详细地考虑这样的一些协议。另一个重要的时延是媒体分组化时延，这种时延出现在经IP语音（VoIP）应用中。在VoIP中，发送方在向因特网传递分组之前必须首先用编码的数字化语音填充一个分组。这种填充一个分组的时间称为分组化时延，它可能较大，并能够影响用户感受到的VoIP呼叫的质量。这个问题将在本章结束的课后作业中进一步探讨。
1.4.4 计算机网络中的吞吐量
除了时延和丢包，计算机网络中另一个必不可少的性能测度是端到端吞吐量。为了定义吞吐量，考虑从主机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中的例子更一般地说明了吞吐量不仅取决于沿着路径的传输速率，而且取决于干扰流量。特别是，如果许多其他的数据流也通过这条链路流动，一条具有高传输速率的链路仍然可能成为文件传输的瓶颈链路。我们将在课后习题中和后继章节中更仔细地研究计算机网络中的吞吐量。
