通过轻量级仿真捕获TCP猝发性

1、通过轻量级仿真捕获TCP猝发性作者：黄宝仪译注1，瑞士联邦科技研究所 John Heideman译注2，美国南加州大学信息科学研究所关键词：TCP模拟，网络仿真，抽象技术，有限状态自动机摘要:数据传输过程中的猝发性（burstiness）译注3日益成为协议分析中无法忽视的关键属性。为了保存TCP通信出现的这种猝发性或伸缩（scaling）现象，我们开发出一种行为模型，用以捕获TCP的窗口控制与闭环控制。通过一种称之为"穷举状态探查"的全新模拟技术，我们在限定了连接长度和丢包率的情况下系统地检验了各个TCP状态。这种限制范围覆盖了TCP在通常万维网数据交换条件下的大多数行为。

2、当连接超出此范围时，我们将引发一个抽象错误并切换至一个更具体的模型，以此保持模拟的精确性。通过对那些到达时间间隔落入某临界区间即往返时间（RTT）或重发超时（RTO）的包进行计数，我们能创造一个显示背对背包译注4传送回合状态及其转变的有限状态自动机(FSA)。我们证明一个TCP的FSA近似可以产生一些适用于生成后台传输量的TCP轻量级仿真模型，并且这些模型能够精确地再现IP网络传输中多重分形的伸缩行为。一、介绍：仿真已经成为研究大规模网络协议的必要工具。有着数千节点的实验台并不适合通用目的。仿真研究通常通过研究特定后台传输量下的一些新的数据流来考量一种新的协议(如运输协议，排队规则等)。对后台

3、传输量的仿真是困难的，原因如下：必须精确地模拟因特网传输中固有的猝发性；必须模拟大量的连接，并且必须能够有效地模拟万维网数据传输量，因为万维网是当前因特网的最主要应用。正确地模拟数据传输量对得出正确结论而言是极其重要的。例如：关于RED12的研究在不同的仿真12和模拟研究5中得出了十分不同的结论。这些研究的一个关键差异就是对模拟传输的猝发性估计不同。用以捕获猝发性的一种很有希望的解决方案就是在传输建模时采用结构化的方法9，仔细模拟在一个真实网络中数据传输量是如何产生的。在捕获多种时间尺度下的因特网行为的过程中有两种机制是至关重要的：1， 用户级属性：呈指数分布的万维网会话到达时间和呈重尾分布译

4、注5的会话期限会导致较大时间尺度内的持续猝发。例如，大尺度内的自相似性。2， 网络机制：TCP的闭环控制和基于窗口的传送机制对中小时间尺度内的异常猝发性有着很大影响。例如，往返时间尺度下的周期性和小尺度下的多重分形性。使用这种传输建模方法的一个问题就是状态开销。一个对有400用户的ISP网络的仿真要使用几千个随机变量来保存用户级属性，并且要使用数十万个TCP连接来捕获多种网络机制。即使采用并行仿真技术，随着仿真规模的扩大，内存利用率也往往是关键的瓶颈。最后，仿真模型必须正确地模拟当前的因特网传输量。TCP是因特网最重要的传输协议（占字节传输量的95%，包传输量的90%，数据流的80%，见6，2

5、9），并且万维网传输量（HTTP）占TCP传输量的绝大多数(经常达到60-80%)。虽然长期存在的TCP数据流的稳态行为已经被仔细研究、模拟和分析过（由Floyd开始10，详见15第二部分），但是这些研究未对较短的数据流进行模拟。虽然那些较长的数据流占因特网字节转送量的大多数，但大多数数据流是较短的。有些研究29，7指出流量或万维网文件尺寸呈一种幂次法则译注6分布，平均值为15-30个包或5-10千字节。 而且，TCP在慢启动阶段变化最快，因此必须小心地模拟这一阶段，这对捕获那些影响到小时间尺度行为的网络机制来说是十分重要的。我们工作的主要贡献在于提供了一种能够有效模拟短期TCP连接的途径，用

6、以产生后台传输量。我们能做到这一点是由于利用了因特网传输量的重尾分布特性，而且我们的方法可以在更具体地表示长期连接的同时非常高效地表示短期连接。由于大多数数据流是短的，这种方法能极大地减少仿真的内存需求。我们用一个有限状态自动机(FSA)模型来有效地表示短连接。我们用一种全新的技术建立了这个FSA模型：模拟器辅助的穷举状态分析。我们利用一个模拟器来研究定量数据段丢失的全部可能情形。通过这些研究，我们构造了一个FSA来近似模拟TCP的拥塞控制行为。根据TCP规格或其某一实现来手工创建这个FSA是非常容易产生误差的。因此我们利用一个模拟器自动地枚举状态空间，并且我们正在开发软件以便完全自动地创建F

7、SA。我们的方法要求对TCP行为作出三种假设。第一，我们假设大多数较短的TCP数据流可以被模拟成若干背对背包的传送回合，这些回合由约一次往返时间的延迟分隔开13（出现误差时延迟会增加）。第二，丢包率是独立同分布的（与猝发丢失相反）。我们在4.6节中将用我们的FSA模型仿真与详细的TCP仿真相比较，以验证我们的这些假设。第三，我们现在的模型只考虑每个数据流最多发生一次丢失的情形，在数据流较短且丢失率较低（5%）的情况下这种假设是适当的。当这些假设被违背时，我们能检测到，并且会用一个充分详细的等价TCP模型替换我们的FSA TCP模型，这样一来，我们就能通过产生一个抽象错误来保持仿真的精确性。我们

8、在4.2节中验证了第三个假设，并且当我们把FSA模型应用于后台传输量仿真时，我们仍然能够调整它。二、相关工作：我们的工作建立在前人的三方面工作基础之上：穷举状态分析方法是基于通过总体状态探查而进行的协议分析和短期TCP传输分析的。我们的总体TCP行为分析是基于TCP启动阶段行为模拟研究的。我们的FSA仿真模型应用是基于仿真抽象研究的。通过状态探查而进行的协议分析：有限状态图是用以理解协议的行为、正确性和性能的工具之一。人们习惯于用FSA协议近似法来证明协议的正确性。这种工作通常面临的问题之一就是控制那些必须考虑的状态空间的大小。典型的做法就是通过假设来限定问题的范围，或者采用一些技术尽来可能地

9、合并状态（例如21）。我们的工作同时采用了这两种技术来限定状态空间，并且采用模拟器驱动的FSA结构，以此降低出错的可能性并减少状态空间的开销。此外，与前人在大型FSA表示方面的研究不同，我们所关注的是性能分析和近似，而不是正确性评估。TCP稳态的性能分析：关于TCP稳态行为描述方面的研究已经有很多了。早在1991年Floyd就提出了一种简单的试探式分析方法，可以预测在多个路由器拥塞的情况下的TCP性能。Ott、Kemperman和Mathis完成了一次关于TCP窗口大小行为的正式分析研究24，Lakshman和Madhow提出了一个更加精细的TCP模型19，这个模型假设了较高的延迟-带宽积和随

10、机的包丢失。Mathis等人22和Lakshman等人19分别独立地导出相似的闭型方程，可以近似计算在无序丢失的假设下的TCP稳态带宽（无重发超时时限）。最近Padhye等人25计算出了那些会导致重发超时和推迟确认的包丢失的概率。 他们的模型在上述方程基础上增加了对最大窗口大小和超时区间的考虑，能够较好地预言长TCP连接的带宽。这些研究的一个共同点就是它们都集中关注非限定长度的TCP连接的稳态行为。有人建议把这些近似值用于确定可接受的拥塞控制界限（由Floyd首先提出11，最近的建议见27，26）。对现实的因特网业务的研究表明，尽管长连接占用了大量带宽，但绝大多数连接是短的。更准确地说，连接长

11、度服从重尾分布，其均值相当小，约为15-30个包或5-10千字节29，7。 我们参考的这些相关工作与我们自己的工作之间的主要差别就在于对这些短数据流的检验。TCP慢启动性能分析：对短TCP连接的分析已经有两种研究了。Heidemann等人13模拟了假设无丢失情况下的短TCP连接，以此来比较若干种可选的请求/应答协议。Cardwell等人综合了上述模型和稳态模型25，推导出了有关短连接和长连接丢包率的闭型解。他们模拟了连接建立时间（包括SYN丢失的情况）、慢启动阶段发送的报文段数量和慢启动阶段的耗时，这都是初始窗口大小和慢启动窗口增加率的函数。象上述两种研究一样，我们也用背对背报文段的传送回合来

12、模拟TCP，这种回合以第一个报文段被发出为开始，以收到确认为结束。与13不同，我们考虑了包丢失的可能性。与Cardwell等人不同，我们采用的是穷举状态分析技术。这样我们就可以更精确地模拟非线性的慢启动速度，而他们只能用一个指数来近似的表示。另外，我们也说明了我们的方法如何能够轻易地用于对TCP传输量的高效仿真。仿真抽象：甚大规模仿真需要采用抽象技术，以便从仿真中去除那些对结果无影响的细节。一个常用的抽象技术实例就是把以太网当做10Mb/s的“管道”，而不去模拟MAC层争用和重传的细节。Ahn和Danzig建议在数据流仿真中进行包一级的抽象2；他们并不模拟一个数据流中的各个包，而是把它们视为背

13、对背包组。 在上述建议和13的启发下，我们利用这种方法来判断TCP运行时间状态。尽管我们现在分别表示了传输中的各个报文段，但是采用Ahn和Danzig的数据流表示法将减少运行时间和内存开销。另一个有希望的建议就是把TCP模拟成一组微分方程23。虽然这种方法在一定程度上考虑了传输量的动态变化，但在模拟的传输量具有高猝发性的时候它就无法精确地模拟了。三、TCP建模：流量与拥塞控制机制是任何网络传输协议的核心。这些算法决定了数据包是如何快速地注入网络的。开环协议把包注入网络而不考虑网络或接收方的情况；闭环协议却会对网络或接收方发出的拥塞或缓冲区分配信号作出反应。采用了端到端拥塞控制的闭环协议（如TC

14、P）是因特网获得成功的关键，因为它们能够适应拥塞现象11。我们的目标就是很好地捕获TCP闭环拥塞控制机制的关键方面，以便精确地模拟TCP。理想中我们的模型将能够很好地再现TCP合计传输量译注7，在较大时间尺度内，它应该与详细的TCP的合计传输量没什么区别。这一节简要概述了TCP的拥塞控制机制，并且描述了我们如何用若干背对背包的传送回合来模拟TCP，这些回合由约一次往返时间的延迟分隔开（见13）。然后我们描述了我们是如何利用仿真版的TCP来把这一模型植入我们所考量的领域的。3.1 关键的算法与时间尺度TCP的拥塞控制17和推迟确认3算法决定了短TCP连接的行为。具体地说，TCP是ACK定时的-这

15、就是说，只有在收到接收方的确认之后才会发送新的TCP报文段，发送的新报文段的数量受到拥塞窗口（简称cwnd）的限制。在慢启动期间，每收到一个ACK，cwnd就加1。当慢启动阀值所指定的数据量（简称ssthresh）已经被发送，或者报文段丢失时，慢启动就结束了。按照推迟确认规则，客户在收到两个完整的报文段或者定时器到期之后就发出ACK。如果报文段丢失，TCP将会检测到，并将用两种方法予以恢复。第一种方法是快速重传法18，28，这是恢复单个包丢失的优化方法。如果接收方检测到一个丢失的报文段，那么它就开始为每一个已经收到的报文段发送ACK。发送方把三个连续的ACK视为该包的丢失信号并且会立即进行重发

16、。第二种方法就是，如果无法使用快速重传法，则发送方最终将超时（在一个RTO的延迟之后），并将重发未确认的报文段。我们可以在多种时间尺度下观察TCP的行为：在最粗糙的粒度下（秒），用户发起新的连接。慢启动、快速重传和超时的时间尺度都可以用发送方接收方之间的往返时间来衡量。而ACK定时则发生在非常细小的时间尺度上，可以与包发送的时间相比较。由于这些多种时间尺度的存在，因特网传输量表现出一种复杂的、多重分形的行为方式9。 要模拟TCP就必须考虑这种多样性。试图再现TCP行为的其它研究（基于速率的RAP方法，见27）的经验表明，对粗粒度TCP行为的模拟可以再现非常类似TCP的传输量，但是在传输量统计中

17、明显缺少细粒度的修正。3.2 简单FSA的推导我们用一个简单模型来近似表示TCP，目标是再现中粒度与粗粒度的TCP行为。我们模拟了TCP的慢启动、快速重传和超时机制的效果，但我们没有直接复制那些算法。接下来我们将说明我们能够再现很大的时间尺度下的TCP合计传输量，但我们不期望（也不声称）我们能再现很细粒度的ACK定时效果。图1：左一：在一个短TCP连接中的包交换。左二：序号FSA。左三：回合规模FSA。右一：带有推迟确认接收器的Reno TCP FSA。图1的左边显示了一个典型的万维网TCP连接请求。连接建立之后，请求被发出，然后数据被发回给万维网用户。数据传输由TCP的慢启动算法控制，通过一

18、系列“回合”进行传送。每一回合都以传送一个数据段开始，以收到对该段的确认结束。若发出了多个报文段，则会收到多个ACK；我们假设这些传送可以重叠。我们分别模拟了有推迟确认机制的接收方和没有推迟确认机制的接收方。若接收方实施了推迟确认，我们会立即为第一个数据段产生ACK。而在真实的实现中，这些报文段将是定时器驱动的，有1-500ms的随机延迟，在典型的实现中延迟平均值为100ms。我们通过两个步骤把这个模型绘制为一个状态机。第一，考虑图1的中间部分。各状态上的数字显示被发送报文段的序号。灰色椭圆形中的短弧显示一个包传送时间的延迟；较长的水平弧显示大约一次往返的延迟，这相当于发出包后等待确认的时间。

19、状态图顶上的那一排状态记录了在没有发生丢失的条件下该图左部进行包交换的行为。（这部分图左上方的状态是传送一个报文段，然后经历一个RTT的延迟，然后有两个报文段处于状态二，依此类推。）为了模拟包丢失的效果我们向下扩展了这个FSA。包丢失不仅影响了发送下一个报文段之前的延时，也影响到下一回合发送的报文段的数量。丢失一个包可能引发一次超时或者一次快速重传，我们用向下的粗线表示超时，用向下的细线表示快速重传，这两种线都标有丢失的报文段的号码。丢失报文段的重传和其他的报文段（如果有的话）共同决定了新的状态。图1中间的FSA显示如果1号报文段丢失，那么TCP连接将等待一次重传超时，然后重新发送这个报文段。

20、如果3号报文段丢失，那么TCP会先继续发出两个报文段，然后丢失的3号报文段才会发生超时。这一模型创造了一个完整却又冗长的FSA。为了简化这个状态机，我们把一系列接连发送的包（背对背包）组合起来，只用弧表示超时和往返延迟。图1中间的FSA用灰色的圆把这些回合组合起来。图1的右边我们表示的是同样的信息，但是圆内的数字代表的是这一回合内发送的报文段的数量。粗弧仍然代表一次超时延迟，而所有的细弧都表示大约一个RTT的延迟。若一回合中发送了多个报文段，那么这些回合相应的状态就有多条向下的细线来表示状态的转变，每条细线都标有该回合内丢失的报文段的号码。这个FSA中的位置表示的是TCP的拥塞窗口（wnd）和

21、慢启动的阀值（ssh）。我们采用的另一个优化措施就是合并了图中有着相同的拥塞窗口与慢启动阀值的状态。图1右边的FSA显示了这一点，由于在第一或者第二回合中丢失了第一个包而导致的超时都会引起状态的变化，在新的状态中只会发送一个报文段。这种抽象也允许在不同的丢失模式都终结于同一状态的情况下进行一定程度的状态聚合，条件是其终结状态的待发包数量、拥塞窗口大小、慢启动阀值都相同。最后，我们得到一个更加易于管理的状态机（即图1的右一），这个状态机可以捕获TCP连接动态变化的实质。3.3 完整FSA的创建根据TCP规格或其某一实现来手工创建这个FSA是很容易产生误差的。而且，TCP有许多变异的版本，我们希望

22、都能考虑到。我们在同一个模拟器上系统地进行了一系列试验。我们对各种规模的传输都进行了数据流追踪（考虑了发送方产生的数据流）。我们计算了包的到达时间间隔，在RTT与RTO已知的前提下，对FSA的相应部分进行了后台计算。我们系统地为每一个可能丢失的报文段重复这种计算过程。例如，我们构造了一个具有四个节点的网络：瓶颈链路的速度为1.5Mb/s，延迟为100ms，有两个边缘链路，速度为5Mb/s，延迟为2ms（因此总往返时间为204ms）。 对图1左边的状态机而言，一次追踪会显示出这样的报文段序号/到达时间间隔序列：1/316.7ms，2/1.6，3/220，4/1.6，5/1.6，6。这个序列表明传

23、送1个报文段之后会有一个RTT的延迟（外加由推迟确认计时器导致的另外100ms的延迟），传送2个背对背报文段之后会有一个RTT的延迟，然后传送3个背对背报文段，这就转化成了FSA顶上那一排状态。当我们在丢失了第三个包的情况下重复这一试验时，我们看到这样的序列：1/316.7ms，2/1.6，3/316.7，4/1.6，5/898.4，3。 我们再一次看到1个报文段与一个RTT的延迟（外加推迟确认导致的延迟），然后是2个报文段与一个RTT的延迟（外加推迟确认导致的延迟），在丢失的报文段被重传之前又发送了2个报文段并且发生了一次超时。在图1右一中，这表现为：从左上角的节点开始，向右移动，然后顺着细

24、线向下，然后顺着粗线向下。根据经验法则，我们把到达时间间隔少于50%的情况看作背对背包，到达时间间隔超过200%时看作重传，但是这种方法并不区分推迟确认定时器的影响。如上所述，这种方法与基于仿真的典型的协议研究是不同的，那些典型研究只探查随机的或者指定的配置，而且通常只考虑TCP行为的统计摘要。利用这种方法，我们建立了多个TCP FSA模型，在这些模型中有的模拟Tahoe TCP，有的模拟Reno TCP译注8，有的模拟发送方，有的模拟接收方，有的采用推迟确认机制，有的不采用。我们采用了ns-2译注9的单路TCP实现，在每个数据流丢失0个或1个包且每个数据流最多传送31个报文段的前提下探查了状

25、态空间。15中的图2和图3显示了最终得到的FSA模型。这两个图和图1右一很类似（线条代表RTO或RTT延迟，圆中的数字代表该回合发送了多少报文段，向下的线条显示出第i个报文段在该回合内丢失）。 另外，靠近某些节点的括号中的数字表示在发生一次丢失之后的cwnd与ssthresh值。尽管这种追踪是自动生成的，但是对追踪结果的分析却是徒手进行的。这一过程的自动化实现并不困难，而且将有助于更深入地探查状态空间，同时还有助于探查其他的TCP变异版本。我们可以再现一个TCP连接的进行过程，这只需要从图中左上角标有“1”的状态开始，对剩余的待发报文段的数量进行持续追踪即可。如果这一回合中没有丢失报文段，那么

26、就可以在一个RTT的延迟之后向右移向标有“2”的状态。如果在整个连接期间都没有丢失包，那么这个FSA TCP连接将一直向右平移，直到全部的报文段被发送完毕。然而，如果有一个报文段被丢弃，那么FSA TCP连接将沿着那条对应于这个被丢弃的包的线向下移动（可能是这一回合传送的第1个、第2个或第n个包）。从节点边上括号中的那两个数字可以看出Reno TCP和Tahoe TCP调整其慢启动阀值的方法相同，而这两者减小其拥塞窗口大小的方法却略有不同。当由于重复确认而导致的包重传发生时，Reno TCP把拥塞窗口的大小减小到当前窗口大小的一半。而Tahoe TCP总是把拥塞窗口的大小减至1。四、为网络仿真

27、产生后台传输量我们的TCP FSA模型的一种应用就是对TCP进行轻量级仿真，这就可以产生大量类似于万维网的后台传输量，以便供网络仿真使用。我们的方法就是把FSA模型转化成一个抽象版的TCP。下文将说明我们的方法可以大大减少多数据流仿真中的内存消耗，同时又可以保持在很大时间尺度范围内的仿真精确性。4.1 构造轻量级TCP代理我们已经在ns-2模拟器中实现了我们的FSA TCP代理4。 我们实现的FSA驱动TCP协议模拟器由若干部分组成。我们直接用一套C+数据结构实现了TCP FSA模型的状态。各个活动的FSA TCP连接都在FSA中保留一个指针，用来表明它在这个状态机中的位置、剩余的待发报文段的

28、数量和RTT的近似值。FSA TCP代理向该模拟器发送规则的包；我们对这些包所消耗的内存大小做了一定的优化。当这些包中有一个包被丢弃（因为路由器队列溢出或者包损坏），对应的FSA TCP代理将直接得到通知。FSA模拟器的实现与该模型的一个重要差异就在于我们处理违背了模型限制的情形的方法不同。在模拟器中我们可以检测到违背限制的情形（例如，一个数据流中丢失了两个包），并且会产生一个抽象错误。为了从错误中恢复，我们用一个常规的（即充分详细的）TCP代理来替代我们的抽象FSA TCP代理。我们不能重新生成全部的TCP状态（例如，RTT估计值的准确细节），但是我们可以保存cwnd和ssthresh的值。

29、由于有了这种求助于一个更详细的TCP实现的能力，我们就能够在限制了模型规模的前提下对TCP行为进行精确仿真。4.2 每一数据流的单个包丢失我们现在实现的FSA TCP考虑了每个数据流最多只发生一次丢失的情形。这个限制是因为我们创造的状态机现在只是半自动的。假设包丢失的概率是独立同分布的，我们可以对我们的模型不能涵盖某一给定数据流的概率进行量化，这只需要对FSA中所有穿越了2条（或更多）丢包路径的路径求和即可。这可以简化为：其中p是一个报文段丢失的概率，n是待发的报文段数量。（直观地看，这就是每种连接长度下，我们丢失了2个报文段并且正确发送了其他报文段的概率。）图2显示了该方程对各种误差率的计算

30、结果。该图确定了我们预期在仿真中产生多少抽象错误。当丢包率超出我们假定范围不太多（少于2%）时，模型失效的概率是相当低的，但是对于更高的丢包率和更长的连接来说，要精确地建模就必须能够处理至少每数据流丢失2个包的情况。图2：单包丢失模型失效的概率是连接长度的函数，对于带有推迟确认机制的Reno TCP协议而言，这个概率也随着p取值译注10的不同而变化。（由方程1计算得到）图3：用于评估FSA TCP仿真的一个类似于ISP的拓扑结构。420个客户（左）通过快速接入媒体与40个服务器（右）进行连接。4.3 试验方法论我们用一种通常的情形来评估FSA TCP的性能（内存开销与执行时间）及其精确性。我们

31、使用了一个类似于ISP的拓扑结构（图3）译注11，这个结构和Feldmann等人先前用于伸缩分析9的结构很相似。为了表明FSA TCP的伸缩性，我们在10个万维网会话到100个万维网会话的范围内连续改变TCP连接数，每个会话大约包含200个TCP连接。这些TCP连接的到达时刻服从泊松随机分布，连接长度服从帕累托分布译注12，均值为10KB，伸缩系数（alpha）为1.2。为了进行这一组FSA TCP仿真，我们用FSA TCP替换了那些小于等于31KB的TCP连接，其他较长的连接用原先的TCP实现来处理。所有仿真运行在详细交付模式下，在4200秒仿真时间（比一小时略长）后停止。我们使用了一台Pe

32、ntium II 450MHz机器，物理内存为1GB，运行FreeBSD 3.0和我们修改过的ns-2.1b5。4.4 仿真性能图4计算了我们的FSA TCP在内存和时间开销方面的性能，并与模拟器中常规的（详细的）TCP做了比较。图4中的每一个点都是一次仿真的结果。仿真结果是确定的，用同样的随机种子重复运行就一定会产生同样的结果，因此我们并未给出置信区间。图4：FSA TCP仿真的内存和时间开销。图5：FSA TCP引起的失真：吞吐量译注13差异（用百分比表示）和延迟差异。图4的左图表明FSA TCP较之详细的TCP而言，内存利用率显著提高。创建的TCP连接越多，FSA TCP节省的内存就越多

33、。这也说明对涉及数以百计的并发TCP连接的仿真试验来说，TCP状态的总开销占了内存开销的一大部分。（ns 2.1b6版所作的优化可能改变这一差异；我们还未在该平台下进行此实验。）FSA TCP对大量的细节作了抽象，只需要很少的状态，实质上只需要在FSA中保存一个指向当前状态的指针和一个记录RTT的浮点数。在图4右图中，可以看出FSA TCP在运行时间开销方面并没有太大改进。这是因为仿真时间与事件调度表的大小成正比（除非物理内存耗尽），而调度表的大小是由各时刻预定的事件或包的数量决定的。现在，如FSA图所示，我们在ns-2中实现的FSA TCP可以准确地产生指定数量的单个的包。这样，对详细的TC

34、P和FSA TCP来说预定的事件或包的数量是一样多的，因此我们在仿真运行时间方面没有多大改进。我们正在考虑对FSA TCP进行一项优化，即按照Ahn与Danzig的建议2，用一个代表性的包事件来代表各回合的所有包。这种方法能够避免对单个的包进行调度，从而可以极大地减小事件队列的规模并加快仿真的运行速度。4.5 独立数据流的失真抽象技术带来的一个风险就是它可能导致仿真中的失真和误差。FSA TCP并未实现详细的TCP中那种RTT估计机制，而且它也不模拟由ACK定时引发的独立包与ACK之间的间隔。这将导致延迟上的差异，进而导致那些与延迟相关的度量标准的差异。为了给这些差异定量，我们测量了连接吞吐量

35、和出于瓶颈队列中的各个包的排队延迟。对不同数量的连接，我们都运行了两次相同的仿真。一次采用FSA TCP，另一次采用详细的TCP。我们计算了各个连接的吞吐量差异比率和瓶颈队列排队延迟的绝对差。图5的左图表明FSA TCP的吞吐量与详细的TCP相差大约3%，而且这种失真基本上不受传输量的影响。图5右图表明FSA TCP中（处于瓶颈队列中的）每个包的延迟与详细的TCP相差约10-20ms，换言之就是在RTT为140-400ms的网络中相差5-14%。 这些结果说明FSA TCP可以用于为只要求较粗粒度精确性（粒度达到数百毫秒或按RTT计算）的场合生成后台传输量。然而我们应该避免在捕获细粒度时间尺度

36、（粒度低于10ms或按包计算）下的TCP行为时使用FSA TCP。4.6 合计传输量中的失真我们在TCP仿真中采用FSA近似法的主要目标就是利用有限的资源来模拟大量的后台传输量。为了计算FSA在这一方面的效能，我们必须了解4.5节所述的失真现象是如何出现在合计传输量中的。我们将说明这些失真带来的的影响并不发生相互作用（潜在地有可能相互放大），而且在中、长时间尺度下（即长于10ms），这些影响是难以察觉的。我们采用了小波分析方法8，9来评估FSA TCP合计传输量的伸缩行为。在这一节中，我们首先简要描述小波分析及其产生的定标图的解释方法。然后，我们将用这一工具来比较FSA合计传输量和详细的TCP

37、的传输量。小波分析我们利用一个时间序列的小波变换来研究传输中的全局伸缩性质。特别地，我们检验了每一追踪尺度内包含的平均能量，并且研究了当我们由较粗尺度移向较细尺度时这个数值会如何变化。在j尺度下的平均能量是小波系数平方（即）的和；例如：其中是j尺度下系数的个数。为了确定数据的全局伸缩性质，我们在图6中把绘制成尺度j的一个函数，j沿最粗尺度向最细尺度展开；我们也定性地确定了在什么尺度范围内与尺度j之间存在线性关系；换而言之，就是在什么样的时间尺度范围内存在自相似伸缩性（详见1）。对一个精确的自相似追踪加入某一特殊的时间尺度的周期后就会出现一个倾角；这就是说，在这个时间尺度内存在一个更高频率的包到

38、达时间间隔。当我们在实况网络追踪中应用这种全局伸缩分析方法时，我们经常观察到在大时间尺度下存在一种线性关系模式，在RTT尺度下存在一个倾角。在图6中，底轴是尺度j，作为参考我们把j对应的时间标在顶轴上（以秒计）。图6：详细的TCP和FSA TCP的全局伸缩性的比较。（图中有两条线，但彼此重合。）对FSA TCP进行小波分析我们运行了我们的类似于ISP的方案脚本，同时在连接较短时尽可能地采用了FSA TCP。 我们对从瓶颈链路上采集到的包的追踪纪录进行分解，从而得到了10ms时间序列。在对这一时间序列进行小波分析之后，我们得到了图6所示的全局伸缩图。图中有两条线，一条是详细的TCP传输量，另一条

39、是FSA TCP传输量，这两条线在所有时间尺度下都重叠。这表明我们的FSA TCP可以很好地保持合计传输量中的自相似性和小时间尺度下的不规则行为。这证明FSA TCP抽象可以在大于10ms的时间尺度下精确地模仿后台传输。包一级的网络数据传输具有自相似或分形的特性，在细时间尺度下有非平凡的伸缩行为。Feldmann等人提出：引起小时间尺度下的非平凡伸缩行为的原因就是TCP的闭环控制9。由于FSA TCP可以精确地再现具体的行为，人们可能产生这样的直觉：它能捕获中、粗粒度下的TCP闭环控制的效果，而且当连接过长或发生多个包丢失时我们能够产生一个抽象错误，并且用完全详细的表示方法来代替FSA TCP

40、。五、结论与展望我们已经描述了如何生成一个基于TCP包交换行为抽象的TCP FSA表示。我们也说明了如何生成一个TCP状态的抽象FSA表示，以便在仿真中产生后台传输量；以及如何在抽象模型和详细模型间做出必要的选择，以便优化内存利用率并提高精确性。我们证明：对后台传输量的FSA TCP仿真可以产生和详细的TCP仿真相同的结果。这些结果都表明FSA模型可以在中、粗时间尺度下捕获TCP的关键特性，即这一模型有其适用的领域。显然，未来的工作将包含以下若干方面：首先，我们会使FSA的创建过程完全自动化。我们已经能够对各个丢包情形进行自动追踪，而对这些追踪的分析也将可以自动完成。这将使我们能够更轻易地探查

41、每一连接的多包丢失和猝发丢失，以及推迟确认机制如何影响性能的具体细节。其次，我们也会探查其他的TCP变异版本。利用这些工具与带有选择性应答机制的TCP版本译注14做出比较将是很有趣的。最后，我们在4.4节提出：若能以单个对象来表示多个背对背包，那么FSA TCP仿真的运行时间性能就可以得到提高。对此，我们也将作进一步研究。致谢我们要感谢Sally Floyd，他在对TCP性能的讨论中提出了用穷举状态探查法进行分析的思想。我们要感谢Deborah Estrin为这些模型及其仿真应用做出的技术贡献，同时还要感谢Vishwesh Kulkarni，他参与了这一工作的初期讨论。我们还要感谢Ted Fa

42、ber、George Fankhauser、Ulrich Fiedler和Lukas Ruf，他们仔细审阅了这篇论文。译注：1： 黄宝仪，女，1999年在南加州大学取得计算机科学博士学位，随后在瑞士联邦科技研究所做博士后工作，现任台湾大学电子工程系助理教授。2： John Heideman，1995年在南加州大学取得计算机科学博士学位，后任南加州大学信息科学研究所助理教授，曾担任黄宝仪的指导教师。3： burstiness，又译偶发性、丛发性，指网络传输量的不均衡现象。4： back-to-back packet，指以物理媒体所允许的最小间隔连续发送的包，具体定义见RFC 1242。5： he

43、avy-tailed distribution，重尾分布，若一随机变量X满足重尾分布，则P X>xx-a，当x时，0<a<2。在这种分布中，当a减小时，大量的概率质量集中在分布的尾部。6： power-law，幂次法则，描述了个体的规模与名次之间存在的幂次反比关系：R(x)=ax-b。其中x为规模，R(x)为名次，a为系数，b为幂次。7： aggregated TCP traffic，TCP合计传输量，指的是包括新数据包、重传数据包和丢失数据包在内的传输量的总和。8： 目前TCP协议主要包含有四个版本：TCP Tahoe、TCP Reno、TCP NewReno和TCP SA

44、CK。TCP Tahoe是早期的TCP版本，它包括了3个最基本的拥塞控制算法：“慢启动”、“拥塞避免”和“快速重传”。TCP Reno在TCP Tahoe基础上增加了“快速恢复”算法。TCP NewReno对TCP Reno中的“快速恢复”算法进行了修正。TCP SACK避免了之前版本的TCP重传一个窗口内所有数据包的情况，只重传那些被丢弃的数据包。另外，还有一种未被大规模使用的版本：TCP Vegas，它通过观察TCP连接中RTT值改变感知网络是否发生拥塞，从而控制拥塞窗口大小。9： ns-2，一种面向对象的、离散事件驱动的网络环境模拟器，由UC Berkeley分校开发，可以模拟各种IP网

45、络。它通过“代理”（agent）对象来模拟各种协议，用户可以自行实现某些协议的代理；通过“追踪”（trace）对象来记录出队、入队、丢弃、接收事件。10：原文作“q的取值”，应为笔误，故改作“p的取值”。11：原文作“（图2）”，应为笔误，故改作“（图3）”。12：Pareto，帕累托分布，最简单的一种重尾分布，其密度函数为p(x)=akax-a-1，a，k>0,x>=k，分布函数为F (x)=P X=<x=1-(k/x) a。13：throughput，吞吐量，指的是在不发生丢失的情况下所能达到的最高速率，具体定义见RFC 1242。14：即SACK TCP。参考书目：1

46、P. Abry and D. Veitch. Wavelet analysis of long-range dependenttraffic. IEEE Transactions on Information Theory, 44:2-15, 1998.2 J. Ahn and P. B. Danzig. Speedup vs. simulation granularity. IEEE/ACM Transactions on Networking, 4(5):743-757, October 1996.3 R. Braden. Requirements for Internet hosts-c

47、ommunication layers.RFC 1122, Internet Request For Comments, October 1989.4 L. 4 Breslau, D. Estrin, K. Fall, S. Floyd, A. Helmy, J. Heidemann, P. Huang, S. McCanne, K. Varadhan, H. Yu, Y. Xu, and VINT Project. Advances in network simulation. IEEE Computer, 33(5):59-67, May 2000.5 M. Christiansen, K

48、. Jeffay, D. Ott, and F. D. Smith. Tuning red forweb traffic. In Proceedings of the ACM SIGCOMM, pages 139-150, Stockholm, Sweden, August 2000.6 K. Claffy, G. Miller, and K. Thompson. The nature of the beast: Recent traffic measurements from an Internet backbone. In Proc. of the INET '98, July 1

49、998.7 C. R. Cunha, A. Bestavros, and M. E. Crovella. Characteristics of WWWClient-based Traces. Technical Report BU-CS-95-010, Computer Science Department, Boston University, July 1995.8 A. Feldmann, A. Gilbert, and W. Willinger. Data networks as cascades: Explaining the multifractal nature of inter

50、net wan traffic. In Proceedings of the ACM SIGCOMM, pages 42-55, Vancouver, Canada, September 1998. ACM.9 A. Feldmann, A. C. Gilbert, P. Huang, and W. Willinger. Dynamics of IP traffic: A study of the role of variability and the impact of control. In Proceedings of the ACM SIGCOMM, pages 301-313, Ca

51、mbridge, MA, August 1999. ACM.10 S. Floyd. Connections with multiple congested gateways in packetswitched networks part 1: One-way traffic. ACM Computer Communication Review, 21(5):30-47, October 1991.11 S. Floyd and K. Fall. Promoting the use of end-to-end congestion control in the internet. ACM/IE

52、EE Transactions on Networking, 7(4):458-473, August 1999.12 S. Floyd and V. Jacobson. Random early detection gateways for congestion avoidance. IEEE/ACM Transactions on Networking, 1(4):397-413, Sept 1993.13 John Heidemann, Katia Obraczka, and Joe Touch. Modeling the performance of HTTP over several

53、 transport protocols. ACM/IEEE Transactions on Networking, 5(5):616-630, October 1997.14 Ahmed Helmy, Deborah Estrin, and Sandep Gupta. Fault-oriented test generation for multicast routing protocol design. In Proceedings of the Formal Description Techniques & Protocol Specification, Testing, and

54、 Verification (FORTE/PSTV), pages 93-109, Paris, France, November 1998. IFIP.15 P. Huang and J. Heidemann. Capturing TCP Burstiness for Lightweight Simulation. Technical Report TIK-Nr.92, Computer Engineering and Networks Laboratory, Swiss Federal Institute of Technology, Zurich, 2000.16 V. Jacobson

55、 and R.T. Braden. TCP extensions for long-delay paths. RFC 1072, Internet Request For Comments, October 1988.17 Van Jacobson. Congestion avoidance and control. In Proceedings of the SIGCOMM '88, pages 314-329, Stanford, California, August 1988. ACM.18 Van Jacobson. Berkeley TCP evolution from 4.3-Tahoe to 4.3-Reno. In Proceedings of the 18th Internet Engineering Task Force, pages 363-376, Vancouver, Canada, July 1990. Talk slides and notes.19 T.V. Laks