rfc2330.txt

很多RFC的中文文档

机制以至抽样只能看到被改动了的行为，可预测的抽样是容易被控制的。
测量的活动可能影响被测量的东西（如，注入测量流量到网络中会改变网络的拥塞
水平），而且重复的周期影响能驱动网络到同步的状态（见[FJ94]），极大地放大原本单
独来说是较小的错误。
一个更合理的途径是基于“随机附加抽样”：样本在独立地随机产生的间隔获得，间
隔有共同的统计分布G(t) [BM92]。这种抽样方法的质量依赖于分布G(t)。例如，如果
G(t)以概率1产生常值g，那么这个抽样就退化为周期是g的周期抽样。
随机附加抽样具有显著的好处：一般来说，它避免了同步效应且产生了被抽样属性
的无偏估计。它唯一的显著缺点是：
它使频率域（frequency-domain）分析变复杂，因为样本不是如傅立叶变换
（Fourier-transform）技术所假定的以固定间隔出现；
而且，除非G(t)是指数分布（见下），抽样仍会保持稍微的可预测性，如上面所讨论
的周期抽样。

11.1.1.	泊松抽样

可以证明如果G(t)是参数为λ的指数分布，即G(t) = 1 - exp(-λ * t)。那么新样本的到
达不能被预测（就是说抽样是无偏的）。此外，即使抽样活动影响了网络的状态，抽样也
是渐近无偏的。这种抽样被称作“泊松抽样”。它不会倾向于诱发同步，它能用来准确地
收集周期行为的测量样本，而且当新的样本到达时它不会倾向于被预测控制。
因为这些有价值的属性，我们通常优先使用泊松抽样来采集互联网测量的样本。
{注释：然而，我们指出可能有适合使用不同G(t)的环境。如，指数分布是极大的，
所以它的使用有时会在抽样时间之间产生过大的间隔。我们希望限制这样的最长的间隔
为一个最大值dT，以加速源于抽样的估计的收敛。这应通过G(t) = Unif(0, dT)来做，也
就是0 到dT的均匀分布。当然，如果一个几乎长达dT的间隔过去了而没出现一个样本，
这种抽样会变得高度地可预测.}
在它最纯粹的形式，泊松抽样是这样实现的：产生独立的，指数分布的时间间隔；
在每个间隔过去后采集一个测量样本。能够说明如果在时间T开始，某个人经过间隔dT
完成泊松抽样，在这期间正好做了N次测量，那么这些测量将在时间间隔[T, T+dT]内是
均匀分布。因此另一个产生泊松抽样的方法是选取dT 和N，并在间隔[T, T+dT]内均一
地产生N个随机抽样时间。这两个方法是等价的，除非N和 dT是外部知道的。这种情
况下，测量时间不能被预测的属性被削弱了（其它属性仍然保持）。N/dT方法有一个优
点：处理N 和 dT的固定值比处理固定了λ，但经过长度可变的时间间隔做可变数量的
测量简单。

11.1.2.	几何抽样

与泊松抽样紧密相关的是“几何抽样”，它以固定的概率p测量外部事件。如，某个
人可能捕获了通过链路的所有分组却只将分组记录在追踪文件，如果产生的在0到1之
间服从均匀分布的随机数小于给定的概率p。几何抽样有如泊松抽样的无偏和事前不可
预测的属性，所以如果它符合一个特定的互联网测量任务，采用它也是合理的。更多的
讨论见[CPB93]。

11.1.3.	产生帕松抽样时间间隔

要产生帕松抽样时间间隔，首先决定个体测量的平均测量间隔时间的参数λ（即，
对于30秒的平均抽样间隔，我们有λ = 1/30，如果时间单位是秒）。然后产生一系列（伪）
指数分布随机数E1, E2, ..., En 。第一个测量在时间E1做，下一个在时间E1+E2做，以
次类推。
一个产生（伪）指数分布随机数的技术是基于能够产生在0到1之间服从均匀分布
的（伪）随机数U1, U2, ..., Un的能力。许多计算机提供了做到这点的函数库。给出了
Ui,产生Ei使用公式：Ei = -log(Ui) / λ。这里log(Ui)是Ui的自然对数。{注释：这个技术
是更一般的以一给定分布产生随机数的“逆变换”的一个实例。}
实现细节：
对于近似帕松抽样至少有三种不同的方法，这里我们描叙为方法1到3。方法1是
最容易实现但有最多的错误，方法3是实现最困难的但有最少的错误（可能没有）。
方法1如下进行：
1．	产生E1并等那么久。
2．	完成一个测量。
3．	产生E2并等那么久。
4．	完成一个测量。
5．	产生E3并等那么久。
6．	完成一个测量。
这种方法的问题是“完成一个测量”步骤本身需要时间，所以抽样不是在时间E1，
E1+E2，等等做出的，而是在时间E1，E1+M1+E2，等等做出的，这里Mi是第i次测量
需要的时间。如果Mi与1/λ比较非常小那么由这个方法引起的可能错误同样也小。当
Mi与1/λ比较不可忽略时，可能的错误增大了。
方法2试着通过考虑测量所需的时间（即Mi）并与之相应的调整等待时间间隔来纠
正这个错误：
1．	产生E1并等那么久。
2．	完成一个测量，并测量它所费的时间M1
3．	产生E2并等E2-M1长时间。
4．	完成一个测量并测量M2。
只要E{i+1} >= Mi，这个方法工作得很好。但是，如果E{i+1} < Mi那么就不可能
等合适长度的时间了。（注意这种情况相当于需要同时完成两个测量。）
方法3产生一个测量间隔时间的时间表E1, E1+E2，等等，然后坚持按表进行：
1．	产生时间间隔E1, E2, ..., En。
2．	计算测量进行时间T1, T2, ..., Tn, 其中 Ti = E1 + ... + Ei。
3．	在时间T1, T2, ..., Tn安排做一次测量。
由于允许同时的测量，方法3避免了方法1和2的弱点。然而，如果同时进行的测
量彼此干扰，方法3就没有任何优点还可能被正实比方法1和2还要差。
对于互联网的现象，不知道这些方法不准确到什么程度是显著的。如果Mi远比1/λ
小，那么三种方法里的任何一种都可以采用。如果Mi比1/λ小但差得不多，那么方法2
比方法1要好。如果同时进行的测量彼此不干扰，那么可以采用方法3，尽管比较之下
它的实现相当的困难。

11.2自身一致性

合理的测量方法的一个基本要求是测量尽可能少的使用未经证实的假设。经验已经
痛苦地表明作出一个（常常是内在的）假设却实际是错误的有多容易。一个例子是在测
量中将时钟读数的同步与高度准确的时钟源混为一谈。很容易作出假设因此时间是准确
的，但由于软件故障（bug），时钟源的掉电，时钟源和时钟间通信丢失，时钟实际上可
能很不准确。
这并不是辩论说在测量时不能做任何假设，而是说在实践时，应该检验假设。做到
这一点的一个有力的方法是检查自身一致性。这样的检查既适用于测量的观察值又适用
于测量过程本身使用的值。前者一个简单的例子是在计算往返时间时应检查它是否为负
值。因为负的时间间隔没有物理意义，一旦是负值就要立即标记一个错误。这种类型的
错误应该在事后研究！弄清楚错误在哪里至关重要，因为只有坚持不懈地这样做，我们
才能对测量方法基本的合理性树立信心。例如有可能因为在测量时时钟被使它与另一个
时钟源同步的过程设置后退而得出往返时间为负值。 但是也有可能测量程序存取了它的
估计之一的未初始化的内存，并且，尽管非常少见，这会导致假的估计结果。 如果同样
的程序被其他人用来完成同样的测量，这第二种错误更严重，因为别人也会遭受错误的
结果。此外，只要没被发现它完全是固定的。
自身一致性的一个更精细的例子来自于收集单向互联网延迟样本。如果有这种延迟
的大的样本，它们是否符合一条测量时间和延迟对的直线，以观察结果有一明显的非零
斜度，能被证明是充分高效的。如果是这样，一个可能的解释是测量使用的时钟之一相
对另一个偏斜了。另一个解释是这个斜度确实是网络真正的影响。决定事实是那种解释
很有启示意义（分辨相对时钟偏移和网络的真正影响的讨论见[Pa97]）。此外，如果使这
个检查成为测量方法的一部分，那么长期斜度非常接近零这个发现就是测量可能没有被
时钟的偏斜影响致产生有偏的结果的肯定的证据。
最后一个例子阐明检查测量过程本身的自身一致性。上面我们略叙了泊松抽样技术，
它基于产生指数分布的时间间隔。一个合理的测量方法应该包括检查产生的时间间隔以
确认它们实际上是否为指数分布（也确认它们是否遭受了相关性干扰）。附录里面我们讨
论了一个这样的技术并给出了C代码，称为Anderson-Darling测试的一个普遍目的的，
充分认识的拟合良度（Goodness-of-Fit）测试。
最后，我们指出真正与互联网泊松抽样有关的常常不是测量何时开始而是与测量过
程相关的线时。由于用来完成测量的主机的复杂性，它们可能相当不同。因此，即使对
伪随机数字生成器和并发的算法有完全的信任，也提倡尽可能多的考虑应该怎样测试每
个测量过程所作的假设。
   
11.3.定义统计分布

一个描叙测量数据集合（样本）的方法是把它们看作统计分布，非正式的看作百分
点。有几个稍微不同的方法做到这点。这一节，我们定义一个标准的定义以使这些描叙
一致。
数量测量集合的经验分布函数（"empirical distribution function" ，EDF）为函数F(x)，
对于任意x，给定整个测量的部分比例<= x.。如果x小于观察到的最小值，那么F(x) 为
零。如果它大于或等于观察到的最大值，那么F(x)为1。
例如，给定了6个测量结果：
2, 7, 7, 4, 18, -5
那么F(-8) = 0, F(-5) = 1/6, F(-5.0001) = 0, F(-4.999) = 1/6, F(7) = 5/6, F(18) = 1, F(239) 
= 1。
注意我们能够恢复不同的测量值和每个测量值在F(x)里出现次数—--值域内的任何
信息都没丢失。另一方面，概括测量使用柱状图一般而言丢失了关于不同观察值的信息，
所以首选EDF。
然而，或者使用EDF，或者使用柱状图，我们都丢失了关于观测值的顺序的信息。
是否有可能这个丢失的信息重要，依赖于我们所要测量的参数。
我们将使用术语“百分点”来指示对于给定百分比a，F(x) >= a的x的最小值。所
以上面那个例子中，第50百分点是4，因为F(4) = 3/6 = 50%；而第25百分点是-2，因
为F(-5) = 1/6 < 25%,且 F(-2) = 2/6 >= 25%；第100百分点是18；第0百分点是负无穷大。
在使用百分点来概括样本时必须要小心，因为它们能导致无根据的比实际可得到的
结果更精确的现象。任何这样的概括都必须包括样本尺寸N，因为任何比1/N要低的百
分点差异都在样本的分辨率之下。
关于EDF更详细的讨论见[DS86]。
我们用对中值这一普遍（而又重要）概念的注解结束本小节。在统计学里，分布的
中值被定义为一个点X，X满足观察到的值小于等于X的概率等于观察到的值大于X的
概率。在估计一个观察值集合的中值时，这个估计依赖于观察值的数量N，它是奇数或
偶数：
如果N是奇数，那么上面所定义的第50百分点就用做估计的中值。
如果N是偶数，那么估计中值是中间两个观察值的平均；也即，要是观察值以升序
排序且配以从1到N的序号，这里N = 2*K，则估计中值是第K个和第K+1个观察值的
平均。
通常，术语“估计”被从词语“估计中值”里去掉而简单地称这个值为“中值”。

11.4.拟合良度（Goodness-of-Fit）的测试
    对于测量校准的一些形式，我们需要测试是否一组数据与那些被从特定分布里抽取
的数据一致。一个例子是：在使用泊松过程做的测量里应用自身一致性检查，一个测试是检
查是否抽样时间的分隔真正符合指数分布；或者是否使用了上面讨论的dT/N方法，是否时
间是在[T, dT]均匀分布。
{注释：至少有三组可能的数据我们应该测试：被安排的分组传输时间，通过使用一个伪
随机数字产生器获得；正好在系统呼叫传输分组之前或之后做的用户级时间戳；和使用分组
过滤器记录的分组的线时。所有这三组数据都可能提供信息：被安排的分组传输时间未能符
合指数分布意味着随机数字产生中的不准确；用户级时间戳的错误意味着调度传输的记时器
的不准确；线时的错误意味着实际分组传输中的不准确，也许是因为共享资源的竞争。}
有许多统计学拟合良度技术完成这样的测试。一个完全的讨论见[DS86]。这本参考书推
荐了Anderson-Darling EDF测试为一个好的所有目的的测试，这个测试也特别适宜检定给定