网络仿真的流模型和包模型
网络仿真的流模型和包模型 流模型和包模型
2 Conceptual Overview (概念综述)
在这一节,我们讨论流模型和包模型模拟器使用的基本的模拟方法学,指出它们之间差别,各自的优点和不足。接着我们展示了我们是怎样在保持这两种模型各自优点的同时,把这两种模型范型集成到一个模拟过程中。随后的章节更详细的描述了我们的集成方法,也包括了我们用来验证我们的方法的一些实验。
2.1 Fluid Models (流模型)
一个简单的流网络模型如图一所示:
图一:简单的流模型
在使用流模型方法的网络中,系统间的数据流被建模成流经管道的流量。为了方便讨论,我们假定没有循环的流动,网络中只包正反馈。但是基本的模型方法(需要少量的修改)也能够被应用到负反馈网络中。在网络模型中的每个位置,数据流被使用如下六个过程来建模:
1. α(t): 此位置的输入流速率,它建模了在该位置收到数据的汇集速率(bit./sec)。它可以是前一个位置的输出(如图一中位置三的输入),或者是一个外部数据源模型的输出(如图一中的位置一的输入)。
2. β(t):输出通信链路能提供的输出流速率,由名可知,它表示从服务器流出的最大流量。它建模了该位置的最大输出通信链路的容量(bit./sec)。
3. с(t):缓冲区大小。我们通过监控多个竞争的流共享的缓冲区的大小,知道缓冲区大小一般来说可能是时间的函数。然而,在这里我们认为它是一个正值C位。
4. χ(t):缓冲区利用情况。表示缓冲区里的流量。它建模了在输出链路上排队和等待的数据量。
5. δ(t):从服务器流出的流量速率,它表示数据从该位置流出的速率(bit./sec),和(期望)到达下一个位置的流速(如图一所示,位置三的输入流速是位置一和位置二的输出流速之和)。要注意输出流量速率δ(t)不能大于输出通信链路能提供的输出流速率β(t)。换言之,当一个位置向另外一个随后的位置发送数据时,发送数据的速率不能大于连接两个位置的物理通信链路的最大带宽。
6. γ(t):由于缓冲区溢出而导致的数据丢失率。它表示在该位置丢失的数据。
前三个处理α(t)、β(t)、с(t),被称为预定义处理,它们刻画了一个流位置的行为。其他三个处理χ(t)、δ(t)、γ(t)由预定义处理决定,成为派生处理。参考文献[25]对流网络模型的一些基本的原理进行了说明。
在使用流方法创建的网络模拟模型中,在任意的时间点t对每个位置派生的处理(χ(t)、δ(t)、γ(t))都使用在该位置预定义处理的当前值进行被精确的计算。当一个计算的输出结果δ(t)成为随后某一位置的输入α(t)时,该位置的派生处理也要被计算。计算重复进行,直到所有预定义处理值发生改变的位置,都进行了派生处理计算为止。在这一时刻网络达到一个稳定状态,直到下面三种情况发生,否则不需要进一步的进行计算。
1. 一个外部的数据源模型通知使用一个新的数据生成速率。比如一个开-关数据源模型通知数据源由开到关或由关到开。
2. 对列从非空变成空的转变(例如在一个位置χ(t)=0)。这导致随后的位置的输入流速率的变化。
3. 队列从快满了到满了转变(例如在一个位置χ(t)= C)。这导致在该位置的溢出率的改变。
在以上三种事件的任意一种出现的情况下,每个位置的派生处理都像前面所述的那样重新计算,随后网络又达到了一个稳定状态。
以上述这种方式来建模网络的时候,需要进行许多权衡:
1. 在某些情况下,流模型的模拟的计算效率是非常高的。因为模拟只考虑速率改变事件,因此它的计算复杂度要比数据包级的模拟要小的多。我们已经在前一个实验中展示了在建模一个简单网络的模拟中,流模型比基于数据包模型的速率要快一百或者更多倍。但是当被建模的网络规模增大后,这种计算上的有效性开始变得不明显了。这主要是由于众所周知的流模型模拟中的Ripple Effect。Ripple Effect 是由非空队列上输入流的速率的改变引起的,也引起所有共享此队列的输出流速率的改变。也就是一个流的单一的速率的改变能导致相关队列的多个速率的改变。对于Ripple Effect更详细的讨论请参考Liu et al. [12, 11]
2. 流模型方法比其他模型方法更容易受数学分析的影响。Wardi et al. [24]已经表明,把网络行为描述为一组微分方程的集合会导致精确的Infinitesimal Perturbation Analysis,能够对将来网络的性能给出良好的预测。Towsley et al. [16] 使用流模型和微分方程组的方法来分析性的描述了TCP endpoints的行为和主动队列管理技术。
3. 流模型的方法会导致模拟中网络性能度量精度的降低。因为它总是采用某一段时间的平均网络状况。这样它就没有必要获得突发的网络状况所引起的后果。例如,当几个流到达一个已经满了的队列时,流模型根据每个流所占的输入速率的比例计算丢失率。在现实的网络中,在不同的时间点,不同的流的丢失率是大不相同的,这经常是由于偶然的因素或由于到达模式的stroboscopic效果。
4. 向前面提到的那样,如果网络含有反馈(或者是网络拓扑中潜在的路由循环或者是数据源根据网络的状况调整输入流速率),就很难用流模型来模拟。路由循环会导致采用流模型的模拟器所处理的速率改变事件的大量的增加。这就会导致模拟效率的迅速的降低。
尽管存在这些权衡之处和潜在的精度的降低,大量的研究人员还是报告了使用流模型模拟器所获得的很好的结果[27, 21, 22, 17, 10, 15].。
2.2 Packet Models
图二:简单的包模型
一个包模型的网络模拟的例子如图二所示。使用这个方法来建模网络,模拟器在保留每个源生成的每个包的信息同时,也在网络中的每个点上建模数据包的路径。数据包在每个链路、每个队列、每个数据源和接收器上被各自的跟踪。包的丢失的计算可以在数据包的级别上进行,这就产生了相当精确和可重复的网络行为。大量的研究成果和商业产品使用包建模的方法进行网络模拟,包括ns2 [14], pdns [19, 20], GloMoSim [28], SSF [4, 3], JavaSim [23], and OpNet [1].
数据包级建模的方法的缺点就是会导致计算复杂性增加。因为模拟器对系统中的每个包跟踪和建模每个包事件(进队列、出队列、传输、接收、丢失),这样系统中出现的要处理的包事件的总数就会非常巨大。另外,在模拟过程中的任意时间点上计算机所需要的内存也会随着数据包的增加而增加,这样内存资源就成为了包级模拟的瓶颈。