早在ARPANET年代就出现了对网络延时的系统测量,并用于考察延时在一天内的不同时刻,或者一周内的不同日期之间的变化情况【Queueing Systems. Volume 2: Computer Applications, Wiley-Interscience, New York 1976】.此后,Mills【Internet delay experiments. RFC-889】为改进TCP的重传机制,研究了数据包的往返延时与数据包的长度的关系.
上世纪90年代初,有学者开始把互联网的端到端延时与丢包率等特性一起进行研究,但与近年来满足新兴的强交互性应用需求的目的不同,这些研究通常把端到端延时的剧烈变化作为证实互联网动态特性的根据,或者与数据包丢失等现象一起作为间接反映网络墉塞的启发式信息.尽管如此,早期研究中观测到的现象却客观地反映了互联网端到端延时的本质特点.【On the Dynamics and Significance of Low Frequency Components of Internet Load, Technical Report CIS-92-83, University of Pennysylvania, Philadelphia, PA, December 1992】使用每间隔1分钟发送一组ICMP ECHO数据包的方法探测延时,每组10个数据包,相邻数据包的发送间隔为1秒钟,对每个数据包计算延时后按组平均.本文使用的数据的采集方法除相邻两组的发送间隔为15分钟外与该文基本相同.作者通过统计一对主机间不同时刻的延时均值的概率密度发现,每对主机间的延时分布都能很好地用带有一个常数偏移量的Gamma分布描述,参数的取值取决于具体的主机和时段.而且该文还指出丢包率以及需要重排序的数据包数量都与延时的各种统计特征正相关.【Experimental Assessment of End-to-End Behavior on Internet】持续地每39.06毫秒发送一个基于UDP的小数据包探测分别部署在UMD,Stanford和MIT的3台主机间的延时.尽管使用了更小的探测间隔,但一对节点节点间的延时未表现出任何规则性的变化规律,按作者的结论"RTT会在短期内会发生实质性的变化".Bolot在【Characterizing End-to-End Packet Delay and Loss in the Internet】一文中对之前关于端到端延时的研究做了充分总结.该文探讨了使用时间序列模型研究延时的可行性,并使用简单的有限长度的先入先出缓冲区模型解释了端到端延时表现出的部分现象和特点.
【Analysis of End-to-End Delay Measurements in Internet】开始强调端到端延时对新兴互联网业务的意义,并把延时作为一个独立的研究问题.与其它研究中测量延时的方法不同,作者使用了100字节的IP数据包探测单向端到端延时.该文根据造成延时的原因把端到端延时分为处理延时,传输延时,传播延时和排队延时四部分,然后又从测量的角度把延时分为随机的和确定的两部分.作者把一段时间内延时的概率分布情况分为四大类,除少数延时的概率密度函数曲线出现多峰等现象外,约84%的表现出类似于Gamma分布的重尾特征.,作者测量了无负载情况下确定部分的延时,并估计了每台路由器造成的平均延时.
数据集
狭义的端到端延时是指数据包从源节点开始发送到它被目标节点成功接收的单向的延时,但因为测量单向延时需要源节点和目标节点间进行时间同步等协作,复杂性较高,所以在实际应用中,衡量端到端延时最常用的指标是数据包在两端主机间的往返延时,即RTT.本文中端到端延时的含义属于往返延时,更确切地说是指基于PING的方式计算的RTT;我们此后默认RTT与端到端延时的含义相同.
相比网络流量和路由信息的数据都能够用被动方式采集,端到端延时一般需要采用主动探测的方式,这不可避免地将为互联网造成额外负载,影响互联网的正常业务运行.有时候甚至会使某些自治域的管理员或入侵检测系统误以为受到了非法攻击. PAPP项目提供的端到端延时数据帮助解决了这个问题.本节将首先介绍PlanetLab网络平台和PAPP项目的基本情况,解释RTT数据采集的具体方法;然后,说明数据的正确性检验;最后,讨论本文抽象和使用数据的方法及其对研究结果的影响.
PAPP项目
PlanetLab是一个用于部署,评估和实验全球规模的网络服务的分布式平台,由一个研究团体负责管理和维护.截至到2005年11月,PlanetLab已经包含分布在世界各地的600多台主机,覆盖近300个域.运行PlanetLab相关服务的主机一般被称作节点,我们将在下文中沿用这一名称.
All Pairs Pings起始于2003年2月,是到目前为止PlanetLab平台上历时最久的项目之一.它使用被广泛用于检测网络可用性的网络探测工具PING来测量一对节点间的RTT.PING的工作原理基于RFC-792中定义的ICMP反射功能.测量一对节点间的RTT时,发起探测的节点(源节点)首先向目标节点的IP地址发送一个缺省为64字节(8字节ICMP包头和56字节数据)长的ECHO_REQUEST请求数据包,其中包含一个时间戳记录发送时间.如果两个节点间的网络连接及目标节点都工作正常,目标节点在接收到该请求数据包后立即回送一个ECHO_RESPONSE的应答数据包.源节点在接到应答数据包后就能够计算出一个数据包在其自身与目标节点之间往返需要的时间,即RTT.All Pairs Pings在每个连续运行的PlanetLab节点(Production Node)上部署一组Perl脚本,用于控制该节点周期性探测所有其它节点.每间隔15分钟(一个时段),每个节点就会使用PING向所有其它节点陆续发起一轮不间断的探测,直到源节点得到10次有效的RTT或者在120秒后因超时导致该次探测结束.源节点如果在超时前采集到一组到达目标节点的有效的RTT,那么就会统计并记录下这组RTT的最小值,均值和最大值(我们称这样一组RTT的最小值,均值和最大值为一个RTT元组);否则就认为目标节点在该轮探测中不可达.All Pairs Pings使用一台特定的服务器每隔1小时左右收集一次所有节点记录的它自身与其它节点间的RTT元组数据,并把属于同一轮探测的RTT元组整理成一个RTT元组矩阵,与该轮探测中在线节点的IP地址列表一起存储在一个文件里.
PAPP数据的选择和检验
经过比较和调研,我们选用了PAPP项目从2005年6月1日到2005年8月31日(在这段时期内PAPP数据的各时段的节点数量相对稳定)的数据进行研究.这些数据共包括8813个文件,对应于8813轮探测结果,平均每轮探测又包含大约478个节点的IP地址列表以及这些节点的RTT元组矩阵.如果按照All Pairs Pings相邻两轮探测的时间间隔为15分钟计算,这段时间内应该进行了8832轮探测,这说明All Pairs Pings在长时间采集大量数据时可能出现意外或错误.因此,为保证研究结果的可靠性,我们检查了本文使用的所有数据,并将数据中出现的错误和冲突分为以下3种情况:
不可修正错误:延时元组残缺不全或者混入了难以正确分离的字符,例如".945/156.088/",称为元组错误;或者,延时元组矩阵中某一行的延时元组数量与该时段的节点数量不等,称为行错误;
可修正错误:某些非法字符串混入延时元组中,但可人为实现无歧义地修复,例如 "199.77.128.193148.945/149.088/149.281",而"199.77.128.193"为该时段内某个节点的IP地址;
矛盾数据:延时元组的最小值,均值和最大值之间相互矛盾,例如"171.196/2114.788/21546.315"中均值小于最大值的1/10,根据All Pairs Pings的原理这种元组是不可能出现的.
实际上,出现错误的延时元组的比例非常小:8813个延时元组矩阵中仅有唯一1个矩阵出现了1个行错误,我们将该行的全部延时元组作缺失数据处理;约1,400,000,000个延时元组中仅出现了130个可修正错误,分布在128个延时元组矩阵中,我们一一进行了手工修正;还有197个矛盾数据分布在179个延时元组矩阵中,因大部分矛盾数据实际上由舍入误差造成,我们未做任何改动.
除排除数据错误外,因为All Pairs Pings在各文件中使用IP地址标识节点,所以我们必须考虑是否存在同一个IP地址先后被多个不同节点使用的问题.PlanetLab的另一个项目CoMon提供了每5分钟更新一次的PlanetLab的节点列表.通过分析该项目的历史数据,我们发现所有的IP地址在与本文研究有关的一段时期内都仅对应过一个域名,所以有理由相信在这段时间内每个IP都对应唯一的节点.
PAPP数据的使用方法
如果一对节点在时段的RTT元组数据有效,我们就用其中的均值作为这对节点的RTT在时段的采样值,记为.在此,需要考察这样一个问题:均值能否表征这个时段的RTT;换句话说,如果一个时段内连续探测得到的一组RTT过于分散,那么它们的均值并不适合作为RTT在该时段的采样值.假设一组RTT为,均值为,则它们的无偏标准差与均值的比值是衡量这组RTT分散程度的常用指标,我们称为这组RTT生成的RTT元组的分散系数.但是,由于PAPP的RTT元组仅记录了的最小值,均值和最大值,我们无法直接求取这组RTT的标准差和分散系数,我们借助以下定理1解决这个问题.
定理1 对任意个非负实数,已知其最小值,均值,最大值分别为,且定义函数和如下
其中,则这个数的标准差使不等式 成立.
依据定理1,由于是的单调递减函数,故仅需计算便可求得分散系数的下限;要计算 的上限,需要先求出的最大值,我们使用了将从2到10(由于无偏标准差的定义在时无意义,所以如果一个延时元组的最小值,均值和最大值都相等,我们假设该元组至少由两个或两个以上的测量值计算所得)穷举的方法.
图 1 全部RTT元组分散系数的上限和下限的累积概率分布函数;
的累积概率分布函数曲线应介于图中的两条曲线之间
从图 1可以看到80%以上的RTT元组的分散系数小于0.1,90%以上小于0.25,这说明每个时段内的连续探测得到的一组RTT相当集中地分布在均值附近,因此均值有很好的表征作用,我们用均值作为RTT在一个时段的采样值是合理的.
按照上述方法,PAPP的数据可以看作每对节点的RTT间隔为15分钟的采样间序列.根据采样定理,只有当采样频率不低于RTT本身变化的最高频率分量的两倍时,才可能完全恢复RTT在一段时间内的变化过程.然而,这在现实中是无法实现的:首先,我们无法知道RTT本身变化的最高频率分量;其次,测量RTT的探测方法本身也受到设备收发数据包能力的限制而具有频率上限.图 2为2005年12月23日连续30分钟内分别使用200毫秒,1秒和5秒的间隔探测一对节点(源节点为pli2-pa-1.hpl.hp.com,目标节点为thu1.6planetlab.edu.cn)的RTT得到的时间序列图像,可以看出RTT在不同采样间隔下的时间序列图像之间并无实质差别,互联网上的端到端延时与网络流量类似,也表现出自相似性的特点.这说明采样间隔并不会影响本文研究结果的一般性.
图 2 不同采样间隔下的RTT时间序列图像
端到端延时的随机过程模型
图 3是一对节点间的RTT在有限时间内的不同时刻的采样值,通常被称为RTT的时间序列图像,它直观地说明了众多现有研究都已指出的互联网的端到端延时会在短期内发生剧烈变化的特点.从图中可以直观地发现RTT随时间变化的情况大致分为两类:一类是持续不断的无规则变化,我们称之为"摄动";另一类则使RTT的本质特征都发生了变化,我们称之为"跃变".我们将基于本节稍后给出的RTT的随机过程模型更严谨地解释"摄动"和"跃变"的含义.
图 3 一对节点间RTT的时间序列图像
随机过程模型
根据对图 3和其它近百对节点的RTT的时间序列图像的观察,我们提出一对节点的RTT可以抽象为随机过程模型:假设为一对节点间RTT的样本空间,随机变量表示它们的RTT在时刻的取值,那么可以用一族依赖于的随机变量来描述这对节点间的RTT,简记为随机过程.
在这个模型的基础上,一对节点的RTT在这段时间内发生了"跃变"的含义是这对节点的RTT分别在时刻和对应随机变量和具有不同的统计特征(数学期望和方差).如果一对节点的RTT在一段时间内仅发生"摄动"变化,我们就假设这对节点的RTT在内的随机过程为均值遍历的(宽)平稳过程;在后文中,我们称这种过程为RTT的摄动过程.
理论上,数学期望是在最小二乘意义下对一个平稳过程的最佳常值估计;而均值遍历性则保证一个平稳过程的时间均值与统计均值即数学期望相等.依据这两个性质,我们能够用一对节点的RTT在当前或过去一段时间内的测量值去估计这对节点的RTT的数学期望,并用它预测这对节点间未来一段时间的RTT;而且,直到这对节点的RTT发生下一次跃变之前,数学期望能够在所有常值估计中使均方误差最小.
跃变和摄动的主要原因
为分析造成RTT发生跃变和摄动的主要原因,更深入地理解互联网端到端延时特性,我们首先把端到端延时分为几部分,然后逐一分析影响各部分的主要因素.
根据数据交换网络中一个数据包在端到端通信中经历的过程,我们把一对节点的RTT分为三部分:
终端延时:终端节点接收,发送和处理数据包的时间;
交换延时:网络中继设备接收,发送和处理数据包的时间;
传播延时:数据包在通信媒介中传播的时间.
表 1 影响RTT的主要因素(加*表示该因素与路由有关)
组成
决定性因素
随机性因素
终端延时
终端节点的处理能力
终端节点的接入方式
终端节点的接入带宽
终端节点的处理器负载
终端节点的网络负载
交换延时
* 经过的网络中继设备数量
* 每台网络中继设备的处理能力
* 网络中继设备的负载
* 网络中继设备的调度策略
传播延时
* 传输媒介
* 传输路程
无
表 1为给定一条路由时,影响每部分延时的决定性因素和随机性因素.不难发现,当路由不变时,造成RTT变化的因素主要是终端节点和网络中继设备的负载变化,它们的统计特征基本上不受时间影响;但当路由发生变化时,不仅会影响某些随机性因素,还会同时改变RTT的很多决定性因素,从而使RTT的根本性质也发生变化.
基于以上分析,我们认为一对节点的RTT发生跃变主要是这对节点间的路由变化造成的;而RTT的摄动则主要是终端节点和网络中继设备的处理器和网络的负载发生变化造成的.
模型的验证
为检验4.1节提出的随机过程模型是否与实际相符,首先,我们把PAPP数据中一对节点的RTT在各个时段内的采样值可以看作是随机过程的一个样本函数的采样序列,称为这对节点的RTT序列,用表示;然后,我们设计一种判别RTT跃变的方法,将一对节点的RTT序列划分为若干个摄动过程的子序列;最后,我们用这些子序列验证摄动过程的平稳性和均值遍历性.
跃变的判别方法
我们用时段附近的(为便于计算,一般选为奇数)个连续的RTT采样值的中位数来估计一对节点的RTT在时段的数学期望.用少量样本估计一个随机变量的数学期望的常用方法有两种:一种是使用样本的平均值;另一种是使用样本的中位数.根据现有的研究成果及我们的直观观察,一对节点的RTT可近似为类似与Gamma分布的单向重尾分布.当样本数量较少时,使用中位数能够比平均值更准确的估计这种分布的数学期望.
图 4 跃变判别方法示意图
本文把用于估计RTT的数学期望的个连续的RTT采样值称为一个采样窗.如图 4所示,我们用采样窗估计一对节点的RTT在当前时段的数学期望,用采样窗估计一对节点的RTT在过去某一时段的数学期望,而且使采样窗与之间存在一定间隔(在图中用表示).我们假设当和在一对节点的RTT序列上滑动到达一次摄动过程的边缘即将发生跃变时的时刻为,跃变前和跃变后的摄动过程的数学期望分别为和,方差分别为和,跃变后的摄动过程持续的时间为(假设).我们分别用和表示采样窗和的中位数,分别用和表示二者的方差.在随后一段时间内,,和,的取值大致分别如图 5 (a),(b),(c),(d)所示.下面,我们以求取在时刻的取值为例说明近似计算和随时间变化情况的方法:首先求采样窗在时刻的均值;然后由求得采样窗在时刻的方差为可见是的二次函数,而且可近似为为轴的开口向下的抛物线.
图 5 采样窗的数学期望和方差随时间的变化
如果采样窗和估计的RTT的数学期望的变化量在某个时刻超过某一阈值,我们就认为RTT在对应的时段内发生了一次跳跃:若,就称RTT发生了一次上跳;否则,若,就称RTT发生了一次下跳.我们将所有RTT在其中发生上跳和下跳的时段按各时间顺序排成一列上跳序列和下跳序列.由于存在着摄动变化的影响,并不是RTT在(或)中的每个时段内都一定发生了跃变.为减小摄动的干扰,降低对RTT跃变的误判率,我们设计了以下两种机制:
我们把跃变的阈值设定为(其中为常数);
只有当序列(或)中的一个时段满足时,我们才判定在RTT在时段到时段之间发生了一次跃变,然后,我们用迭代公式对(或)处理后再搜索下一次跃变.
第一种机制的思想是在判定RTT跃变时参考摄动的程度,如果摄动剧烈那么判定跃变的阈值也应该相应提高.图 6解释了第二种机制的思想:当采样窗和滑经一对节点的RTT的一次跃变时,一旦采样窗和估计的RTT的数学期望的变化量在某个时刻超过了跃变阈值,那么这种状态将至少持续个时段(事实上,我们放松了约束条件,仅要求在未来个时段内有个时段出现相同方向的RTT跳跃).
尽管上述判别方法降低了将RTT的摄动判定为跃变的错误率,但它可能会使漏判率增加.因为当RTT的相邻两次跃变相隔的时间较短时,若两次相邻跃变方向相同,一般会漏判第一次跃变;若方向相反,则一般会同时漏判这两次跃变.因此,在确定参数,和的取值时需要兼顾跃变的误判率和漏判率.
图 6 采样窗数学期望的变化量与跃变阈值的关系
RTT的跃变频率和跃变间隔
使用上述判别RTT跃变的方法,我们考察了【附录1】中590对节点(要求源节点与目标节点不同)的RTT序列.我们选择的参数的取值如表 2所示,这样赋值会对相隔小于6个时段(1.5个小时)的RTT跃变发生漏判;不过,根据文献【End-to-End Routing Behavior in the Internet,Dynamics of Internet Routing Information】的研究成果――互联网上的端到端路径主要由一条占绝对优势的路由控制,而且90%以上的路由会持续几个小时以上,又考虑到路由变化是造成RTT跃变的主要原因(本文4.2节),所以因此被漏判的RTT跃变应该不超过10%.
表 2 RTT跃变判定方法的参数取值
参数名称
参数值
5
3
5
对于一对节点的RTT序列,我们定义它们的RTT的跃变频率为.图 7说明80%以上的节点对的RTT序列的跃变频率小于0.01;所有节点对的RTT序列的跃变频率都小于0.03,也就是说所有节点对的RTT都平均每隔30个时段(大约7.5个小时)以上的时间才发生一次RTT跃变.
图 7 跃变频率的累积概率密度函数曲线
跃变频率无法精确地反映RTT的跃变间隔,因为一对节点的RTT可能集中在某段较短时间内频繁发生跃变,此时即使RTT的跃变频率很低,这对节点的RTT发生相邻两次跃变的实际间隔仍可能远远低于平均间隔.图 8给出了跃变间隔的统计状况,可以看出大约40%以上的跃变间隔大于50个时段(12个小时左右).我们对跃变间隔的估计是保守的,因为在表 2中设定的参数值偏向于保证较低的漏判率,所以,当RTT在某段时间内的摄动剧烈时很可能被误判为跃变.
图 8 跃变间隔的累积概率密度函数曲线
摄动过程的平稳性
摄动过程的平稳性是RTT随机过程模型的重要假设,我们通过考察一对节点的摄动过程的RTT序列是否平稳来间接地检验这一假设的合理性.观察时间序列图像是检验序列平稳性最简单的方法,我们提出的模型就源于观察图像受到的启发,但这种方法容易受主观因素影响,更严格地检验序列平稳性的方法是统计检验中普遍采用的"单位根"方法.
我们选用了单位根方法中最常用的ADF检验【Eviews4 User's Guide】,有关单位根检验和ADF检验的具体原理和过程请参阅相关资料,我们在此仅不严格地说明这种检验方法的基本思想.首先,我们建立零假设,假设待检验的时间序列是非平稳的(是存在单位根的随机游走序列);基于假设的模型,我们计算这个时间序列的某个统计量;然后,对于某个选定的显著性水平(通常取1%或5%),我们从ADF临界值表中查到临界值;最后,我们把与比较:若,则拒绝假设(显著),并认为待检验序列是平稳的,而且我们判断错误的概率不会超过显著性水平(一般越小,我们的判断就越可靠);反之,则认为假设成立(不显著),待检验序列的确是不平稳的.
下面,我们以源节点为pli2-pa-1.hpl.hp.com,目标节点为thu1.6planetlab.edu.cn的一对节点(图 3)分别在2005年7月26日和2005年8月31日的RTT序列为例,解释ADF检验结果的含义.由于PAPP存在数据缺失,为对比公平,我们选择的两组时间序列都包含92个对应时刻的采样点(去掉的4个采样点对应的时刻分别为2:15,9:45,21:45和22:15).我们使用Eviews软件对这两组RTT序列的平稳性进行ADF检验的结果如表 3所示.从表中的结果可以看出,在显著性水平为1%的情况下,这对节点在2005年8月31日的RTT序列的检验统计量仍明显小于ADF检验的临界值,因此我们有99%以上的把握判定这组序列是平稳的;而即使在显著性水平为5%的情况下,RTT在7月26日的时间序列的检验统计量仍大于ADF检验的临界值,不能否定假设,所以这组序列是不平稳的,而造成这种结果的主要原因是这对节点的RTT在7月26日上午发生了一次跃变(图 3所示).
表 3 RTT序列平稳性的ADF检验结果
RTT的时间序列
2005年7月26日
2005年8月31日
检验统计量
-2.775
-6.109
检验统计量
的临界值
1%显著性水平下
-3.503
-3.501
5%显著性水平下
-2.893
-2.893
使用上述的ADF检验方法,我们随机检验了50对节点的RTT的摄动过程序列,发现它们都能在在显著性水平1%的情况下否定假设,即表现出平稳性.检验时,我们选用了ADF检验中仅含有常数项的回归方程,并把最大滞后项设置为3.
摄动过程的均值遍历性
遍历性又称各态历经性,是平稳随机过程的最重要的性质之一,只有当一个平稳过程是各态历经的,这个过程的统计特征才与它的一个样本函数在不同时刻的采样值的统计特征相同.在本文的随机过程模型中,摄动过程满足均值遍历性是使用一对节点过去一段时间内的RTT的采样值估计这对节点未来短期内的RTT的理论基础.
研究一个平稳随机过程的均值遍历性的常用方法是借助均值各态历经性定理.均值各态历经性定理证明平稳随机过程满足均值遍历性,即的充要条件是,其中为的自相关系数.
下面,我们通过检验摄动过程的RTT序列是否满足均值各态历经性定理的充要条件来间接验证摄动过程具有均值遍历性的假设.具体讲,假设某对节点的RTT在某段时间内的摄动过程的RTT序列为,如果(其中),则说明这段摄动过程的RTT序列是均值遍历的;如果很多不同的节点对的RTT的各段摄动过程的RTT序列对应的都接近于0,那么就证实了摄动过程的确具有均值遍历性.
使用本文5.1节中提出的判别跃变的方法,我们将【附录1】中源节点与目标节点不同的590对节点的RTT序列划分成若干段摄动过程的子序列.从图 9可以看出60%以上的摄动过程的RTT序列的值都小于0.02,80%以上的都小于0.5.而且,我们发现造成某些摄动过程的RTT序列的值大于1(甚至达到左右)的主要原因是这些RTT序列的除个别采样值极大(10000到100000之间)外,其它采样值基本相等(95%的致信区间的宽度小于平均值的1%);这些反常的采样值非常可能是意外因素造成的.总之,上述结果基本上能够证实RTT的摄动过程具有均值遍历性.
图 9 的累积概率分布函数曲线
基于同质节点对的验证方法
在描述这种方法之前,我们先定义以下几个概念:
同拓扑节点:由同一组织维护,且具有相同的域名,地理位置及24位以上的IP地址前缀的节点;基本上可判定同拓扑节点位于同一局域网内;
同质节点:具有相同的硬件配置,接入方式和带宽的同拓扑节点;
同质节点对:如果若干对节点的源节点和目标节点都分别是同质节点,那么这些节点对称为同质节点对.
基于同质节点对的验证方法的基本原理是:如果RTT的摄动过程可近似为均值遍历的平稳过程,那么同质节点对的RTT在长时间相同时段内采样的平均值应该基本相等.其中要求在相同时段对同质节点对的RTT采样是为了消除跃变的干扰,因为不同时段的RTT采样可能属于不同的摄动过程.出于这种考虑,只有当一个时段内每个同质节点对的RTT的采样值都在PAPP的数据中存在时,我们才把该时段作为RTT序列的一个采样点.尽管在同一时段内两对同质节点对的RTT的采样也不是完全同步的,仍可能在其间发生路由变化,但这种可能造成的影响是可忽略的.
图 10为源节点为planetlab1.singapore.equinix.planet-lab.org,目标节点分别为Duke大学的3个同质节点planetlab1/2/3.cs.duke.edu构成的三对同质节点对的RTT的时间序列图像.可以看出在同一时段内,同质节点对的RTT采样值之间可能差别很大,而它们的RTT序列的均值却基本相等,分别为279.93ms,281.71ms和280.64.
图 10 同质节点对的RTT序列
为确信RTT的随机性变化背后的确隐含着基本不变的统计特征,我们选择了100个节点与Duke大学的3个节点组成100组(每组3对)同质节点对.图 11分别为这100组同质节点对的RTT采样序列(每组节点对的RTT的采样次数都大于8000)的均值和方差,可以看出每组同质节点对的统计特征基本相同.这在一定程度上证实了RTT的随机过程模型及性质.
图 11 统计节点对具有基本相同的统计特征
RTT的直接估计方法
使用大量测量值估计RTT的数学期望是无法在实际中应用的.在短期内进行频繁探测会给网络和终端系统带来严重负载,甚至会被入侵检测系统误认为攻击;而依靠长时间的采样积累则会受RTT跃变影响降低跟踪能力.目前对RTT的直接估计一般都使用最简单的方法,即用RTT的最近一次测量值进行预测.本节的目的是找到一种能更准确预测未来短期内的RTT的方法,但仍然仅需要依靠少量的近期RTT采样值.
评价指标
寻找和评价一种RTT的直接估计方法,可以在数学上抽象为以下问题:假设表示一对节点的RTT序列,现在希望找到一个映射:,使估计误差最小,其中为和之间的某种距离函数.注意,一种RTT的估计方法除与映射本身有关外,还与使用的历史采样值的个数和预测持续的时间有关.对于任意给定的和,最简单常用的直接估计方法是,我们将这种方法的估计误差称为标准误差.
本文选用最常用的平方误差作为距离函数,即,这样估计误差就变成了最小二乘意义下的均方误差.由于各种方法的估计误差可能差别较大,为便于比较,我们将使用一种方法的估计误差与标准误差的比值作为评价这种方法估计效果的指标,称为相对估计误差.
估计方法及其比较
对于任意给定的和,以下3种映射都可构成3种不同的估计方法.
均值映射:;
中位数映射:,其中表示的中位数:假设已经由小到大排列,若为奇数则它们的中位数等于处于中间位置的那个数,若为偶数则它们的中位数等于处于中间位置的两个数的均值.
最小值映射:;
随和分别取不同的值,我们称使用相同映射的估计方法为同族的.下面我们将使用【附录1】中的610对PAPP节点的RTT序列作为测试集,表 5给出了使用不同的历史采样值的个数和预测持续的时间时,各族估计方法的平均相对误差.
表 4 各族估计方法的平均相对误差(//)
.856/.856/.763
.843/.843/.730
.840/.840/.718
.839/.839/.712
.839/.839/.708
.832/.846/.809
.808/.800/.759
.800/.781/.737
.796/.771/.724
.794/.765/.715
.837/.830/.869
.804/.781/.805
.790/.760/.774
.782/.748/.755
.777/.741/.741
.854/.900/.931
.811/.833/.853
.792/.801/.813
.781/.782/.788
.773/.769/.769
从表 5中可以看到,族估计方法的误差基本上随着使用的历史采样值个数的增加而减小,这是由于RTT的分布为类似Gamma分布的重尾分布,使用样本的平均值估计这种分布的数学期望时通常需要较多的样本才能消除"重尾"效应;但是当大到一定程度后,RTT跃变的影响逐渐显现出来,使得误差减小的趋势明显变缓甚至出现了反弹.
族估计方法的误差随的变化情况基本与族的方法相同;的估计效果一般优于,这是由于RTT的分布为单边重尾分布,当样本数较少时使用中位数能够比平均值更准确地估计这种分布的数学期望;对比和的情况可以发现,RTT跃变导致误差反弹的现象在族方法中比族方法中更为明显,这是因为当RTT发生跃变时族方法的误差一般会大于族方法.
令人意外的是,在表 5中比较的所有估计方法中,使用最近两次()RTT采样的最小值()来预测未来的RTT竟然达到了最好的估计效果.
也许有人会注意到一个与直观感受相悖的现象――表 5给出的结果中各族估计方法的相对误差都随着的增大而减小,这是否意味着越大即预测未来的时间越长估计的误差就越小呢 事实上,根据相对误差的定义,它是一种估计方法的均方误差与标准误差的比值,而标准误差本身就是随变化的函数,所以,每种方法在不同值下的相对误差并不具备直接的可比性.
图 12 三种RTT估计方法的相对误差的累积概率密度函数曲线
图 12给出了时映射,和分别对应的最佳(平均相对误差最小)估计方法对测试集中的610对节点估计得到的相对误差的概率分布情况.可以看到并不存在一种估计方法对于所有节点对的RTT的估计效果都优于其它方法,只能在统计意义上评价一种估计方法的优劣.一般地,族估计方法对不同节点对的RTT序列的估计效果的差别最大,对某些节点对的效果优于族方法,而对于另外一些节点对的效果却可能不如族方法.
相比之下,族的估计方法则同时具有其它二者的优点,既跟族估计方法一样具有普适性(对不同节点对的RTT的估计效果差别较小),又能达到与族估计方法一样的最好情况(适于估计某些特定节点对的RTT).此外,考虑到族的估计方法在时达到最优,即仅要求使用最近两次RTT测量值中的较小者预测未来的RTT,因此,无论从方法复杂性角度还是测量代价角度,这种估计方法都具有显著优势.
估计RTT的启发信息
某些情况下,需要在没有通过探测得到RTT的测量值之前对一对节点间的端到端延时具有粗略的估计.例如,当某个玩家希望从数百台服务器中选择延时最小的玩在线游戏时,如果用直接估计方法测量玩家中断到每台服务器间的RTT,那么不仅会给网络和处理器带来较重负载,而且会使用户等待较长时间;但是,如果能够依靠某些容易获得的启发信息预先对候选的服务器进行选择或排序,则能够有效减小测量开销和等候时间.为此,我们将在本节分别研究两种启发信息――地理位置关系和IP地址的共同前缀的长度,与RTT的平均值的联系.在此之前,我们先考察终端节点的异质性对RTT平均值的影响程度.
终端节点的异质性对RTT均值的影响
PlanetLab节点的异质性主要体现在硬件配置以及接入的方式和带宽上.在使用PING探测RTT的应用背景下,终端节点处理数据包的计算量很小,PlanetLab上一般配置的节点(如Dell Precision 420)处理数据包花费的平均时间应该不超过几十纳秒,这相对于互联网上几十到几百毫秒的RTT是完全可以忽略的.为了验证上面的想法,我们选择了分别由美国的MIT,UCB和意大利Hebrew大学维护的3组仅硬件配置不同的同质节点,它们的数量及硬件配置情况如表 5所示.
表 5 三组仅硬件配置不同的同质节点
MIT
Berkeley
Hebrew
配置I
Dell Poweredge 1650
HP DL320 G2
IBM ThinkCenter (P4 2.4GHz)
数量I
2
1
1
配置II
Dell 650
Dell 650
Dell Precision 420
数量II
3
9
2
图 13为MIT的一组节点分别作为源节点和目标节点时,与其它200个节点的RTT的平均值情况,可以看出两种不同硬件配置并未导致MIT的这组节点与其它节点的RTT的平均值出现显著差别.从Berkeley和Hebrew的两组节点得到的结果与MIT的在实质上几乎完全相同,因篇幅问题,我们不再赘述.
图 13 200个节点与MIT的一组节点间的RTT均值
接入带宽对端到端延时的影响与使用的探测数据包的大小有关,而数据包的大小除应用层数据,ICMP包头和IP包头外,根据不同的接入方式,还可能需要添加不同长度的链路层包头.尽管如此,我们可以先粗略估算一下接入方式和带宽对延时可能造成的影响的程度.假设PAPP使用的询问和应答的探测数据包大小都为100字节,每次探测两端节点都需要各自发送和接收1个数据包,相当于各传送200字节数据;若探测节点和目标节点的接入带宽都为100Kbps,则传输数据所用的总时间为200 * 8 / (100 * 1000)) = 0.0016 s = 1.6 ms,即使两端节点的接入带宽都增大1000倍变为100Mbps,也仅能将端到端延时减小1.5ms左右.使用类似的方法,我们也研究了若干组仅接入带宽不同的同质节点的RTT均值,结果证明终端节点的接入方式和带宽对平均RTT的影响也是可以忽略的.
对比图 13中两图可以发现,一对节点颠倒源节点和目标节点后,它们的RTT均值基本不变,这一方面启示我们一对节点的RTT具有对称性,另一方面也在某种说明了终端节点的异质性几乎不影响RTT的均值.
地理位置对RTT的影响
两端节点的地理位置是影响它们的网络拓扑关系的重要因素,而后者又直接决定了RTT各组成部分中的交换延时和传播延时,但是由于互联网拓扑和域间路由的复杂性,节点的地理位置与RTT并不是简单相关的.由于无法从PAPP的数据中恢复出两节点间路由的历史信息,而且在长达3个月的时间内两点间的路由可能会发生多次变化,所以我们难以获知一个数据包从源节点到达目标节点在通信媒介中传播的精确距离.为此,我们把地球假设为一个半径为1的球体,利用PlanetLab节点的经,纬度坐标计算两节点间的球面距离.
图 14 采样次数大于1000的节点对的平均RTT与地理距离的关系
图 14为PAPP数据中RTT的有效采样次数大于1000的全部节点对(共133519对)的平均RTT与地理距离的关系,初步来看二者并不具有明显的相关性.出人意料的是,有相当数量的节点对之间的平均RTT达到了10秒钟,这是难以用正常情况下造成互联网端到端延时的原因解释的,尽管我们无法找到确切的证据,但这些明显超出互联网上正常端到端延时(广域网RTT应在几十到几百毫秒之间)的RTT很可能是由于链路故障或终端节点的处理器负载过重等特殊原因造成的.
图 15 采样次数大于8500的节点对的平均RTT与地理距离的关系
图 15为PAPP数据中RTT的有效采样次数大于8500的全部节点对(共29373对)的平均RTT与地理距离的关系,可以发现与图 14的图像存在显著差别.节点对的RTT不仅与地理距离表现出相关性,而且为近似正比的关系,尤其是在各种距离下的RTT下限(图 15的红色直线).如果假设地球的半径近似为6500千米,则根据图 15中直线的斜率可以估算出数据包的最大平均传播速度为60千米/毫秒.注意数据包经由的实际地理路径一般与连接两点的地球球面圆弧并不吻合,但图 15的图像说明确实存在着网络路径与球面圆弧非常接近的节点对,即使两节点间的地理距离很远.我们认为图 15与图 14的差别可以这样解释:PAPP数据中有效采样次数大的节点对之间的网络路径和节点本身的可靠性都比较高.从这种意义上说,图 15反映的节点对的RTT和地理距离的关系具有更大的代表性和可信度.图 15的平均RTT一般都在正常范围之内,而图 14中违背规律的节点对的平均RTT一般都明显超过正常范围也证明了这一点.
图 16分别为数据包在中国,美国,欧洲内部,以及跨越太平洋或大西洋时,两端节点的地球球面距离(假设地球半径为6500千米)与RTT的比值(我们在本文中称之为数据包的传播速度)的概率分布函数曲线.可以看到,中国内部和美国内部的曲线非常相似;相比之下,数据包在欧洲内部的平均传播速度则明显低于在中国内部和美国内部.当数据包在不同大洲之间远距离传输时,它的传播速度差别更为显著:统计意义上,数据包在美国和欧洲之间传播最快,在中国和美国之间次之,但在两种情况都比在中国和欧洲之间快1倍左右.从RTT的均值来看,中国和美国之间为283.4毫秒,美国和欧洲之间为233.8毫秒,而中国和欧洲之间接近二者之和为456.4毫秒.
图 16 数据包在不同地理位置的节点间传播速度的累计概率密度函数曲线
(假设地球为半径为6500千米的球体)
某些网络具有特殊的网络拓扑,这会对RTT造成显著影响,从而使地理位置的启发信息失效.例如,由于中国教研网(CERNET)的所有对外出口都设置在北京(图 17所示),所以尽管位于广州的华南理工大学的节点与香港科技大学的节点仅距离150千米左右,数据包却要先从广州经由2000千米以外的北京的对外出口再到达香港.华南理工的节点与清华的节点间的平均RTT约为40毫秒左右,清华与香港科技的节点间的平均RTT约为100毫秒左右,而华南理工与香港科技间的平均RTT恰好约为前两者之和为140毫秒左右.
图 17 CERNET拓扑图
IP地址共同前缀的长度与RTT的关系
IP地址由互联网信息中心(InterNIC)负责管理和分配.IP-V4的地址为32位,起初被划分为A,B,C,D,E五类,实际中一般常提到前三类;每类地址都含有一个固定的前缀和相应的范围.由于A类地址太少,而一个C类地址段对一个组织机构而言又通常不够用,所以大多数情况下被分配都是B类地址,致使B类地址已快被分发殆尽.为解决这个问题,InterNIC在1993-1994年前后采用了无类别地址域间路由(CIDR)技术【An Architecture for IP Address Allocation with CIDR】.CIDR使用一个IP地址前缀作为子网掩码,如果两个IP地址与子网掩码进行位与运算结果相同,那么路由器会认为它们位于同一地址段.例如,166.111.248.0/25表示与166.111.248.0具有相同的25位前缀IP地址段,该段共含有128个IP地址.这样, InterNIC就能够通过子网掩码更灵活地控制分配的IP地址段的容量.
CIDR的另一个重要作用是有效减小域间路由器的路由表长度.在BGP协议中,路由器一般为同一网段的所有IP仅存储一条路由记录,例如,"166.111.248.0/25 next_hop"表示目标地址为166.111.248.0到166.111.248.128的任意数据包都将被转发到同一台下一跳的路由器.
从上面的原理不难看出,IP地址前缀在一定程度上与物理网络的拓扑结构对应,因而会直接影响端到端的延时性能.直观上考虑,两个节点具有的IP地址前缀越长,它们的网络距离越小,同属于一个接入网或网络服务商(ISP)的可能性越大,它们通信时经过的自治域和网络中继设备的数量越少,所以,它们的端到端延时性能会越好.
图 18 按位计算的IP地址共同前缀的长度分别与RTT和地理距离的关系
从图 18可以看出,随着节点的IP地址共同前缀长度的增大,它们的RTT和地理距离都在统计意义上称减小趋势,但这种关系并不是简单单调的,这启示我们应该使用较大的划分粒度来减小误用启发信息的概率,例如使用字节为单位计算IP地址共同前缀的长度与RTT和地理距离的启发式关系(图 19所示).
图 19 按字节计算的IP地址共同前缀的长度分别与RTT和地理距离的关系
结论
本文提出了一种描述互联网端到端延时的随机过程模型,将延时的变化分为跃变和摄动两种.延时的跃变主要是路由变化造成的,发生的频率较低,但一般会改变延时的统计特征;延时的摄动主要是处理器和网络负载变化造成的,无时无刻不在发生,但在摄动过程中延时的统计特征一般保持不变,可以近似为均值遍历的平稳过程.我们使用PAPP项目的RTT数据分别验证了端到端延时的确具有这些性质,从而证实了模型的有效性.这个模型为使用近期测量值预测未来短期内的延时提供了理论基础.
我们用PAPP的数据实际考察和比较了几种延时预测方法,结果表明使用最近两次测量的较小值能够使预测的均方误差最小.
最后,我们研究了地理位置和IP地址共同前缀的长度与节点间端到端延时的联系,讨论如何恰当地利用它们作为启发信息,在使用探测手段前对延时进行初步的粗略估计.
附录一 节点对列表
源节点IP列表
128.214.112.92
130.208.18.30
160.36.57.172
192.38.109.144
198.78.49.56
128.223.6.112
130.75.87.83
161.106.240.18
193.10.64.35
202.79.220.49
129.240.228.138
132.227.74.40
169.229.50.8
193.205.215.74
205.189.32.129
129.242.19.197
132.65.240.102
171.64.64.217
198.32.154.187
205.189.33.178
129.74.152.66
147.83.118.123
192.208.48.3
198.32.154.227
219.243.201.65
目标节点IP列表
219.243.201.65
205.189.33.178
205.189.32.129
198.32.154.187
198.32.154.202
171.64.64.217
160.36.57.172
198.32.154.210
198.32.154.227
128.223.6.112
219.243.200.41
219.243.200.49
129.240.228.138
130.208.18.30
128.214.112.92
169.229.50.8
193.10.64.35
193.205.215.74
143.89.126.13
129.242.19.197
132.227.74.40
130.75.87.83
147.83.118.123
192.38.109.144
132.65.240.102
IP地址
域名
维护单位
128.214.112.92
planetlab2.hiit.fi
Helsinki Institute for Information Technology
128.223.6.112
planetlab2.cs.uoregon.edu
University of Oregon
129.240.228.138
planetlab2.simula.no
Simula Research Laboratory
129.242.19.197
planetlab2.cs.uit.no
University of Tromso
129.74.152.66
planetlab1.cse.nd.edu
University of Notre Dame
130.208.18.30
planetlab2.ru.is
Reykjavik University - Network Laboratory
130.75.87.83
planet1.learninglab.uni-hannover.de
L3S University of Hannover
132.227.74.40
planetlab-01.ipv6.lip6.fr
Laboratoire d'Informatique de Paris
132.65.240.102
planet3.cs.huji.ac.il
The Hebrew University of Jerusalem
143.89.126.13
plab2.cs.ust.hk
The Hong Kong University of Science and Technology
147.83.118.123
planetlab3.upc.es
Universitat Politenica de Catalunya
160.36.57.172
pl1.cs.utk.edu
University of Tennessee at Knoxville
161.106.240.18
planetlab1lannion.rdfrancetelecom.com
France Telecom R&D Lannion
169.229.50.8
planetlab6.millennium.berkeley.edu
University of California at Berkeley
171.64.64.217
planetlab-2.stanford.edu
Stanford University
192.208.48.3
pli1-crl-1.crl.dec.com
HP Labs, Cambridge
192.38.109.144
planetlab2.diku.dk
Datalogisk Institut Copenhagen
193.10.64.35
planetlab1.sics.se
Swedish Institute of Computer Science
193.205.215.74
planetlab1.science.unitn.it
University of Trento - DIT
198.32.154.187
planetlab2.dnvr.internet2.planet-lab.org
Internet2 0 Denver
198.32.154.202
planetlab1.kscy.internet2.planet-lab.org
Internet2 - Kansas City
198.32.154.210
planetlab1.losa.internet2.planet-lab.org
Internet2 - Los Angeles
198.32.154.227
planetlab2.wash.internet2.planet-lab.org
Internet2 - Washington
198.78.49.56
planetlab4.nbgisp.com
Intel Labs - Oregon
202.79.220.49
planetlab1.singapore.equinix.planet-lab.org
Equinix - Singapore
205.189.32.129
planet1.calgary.canet4.nodes.planet-lab.org
Canarie - Calgary
205.189.33.178
planet1.ottawa.canet4.nodes.planet-lab.org
Canarie - Ottawa
219.243.200.41
tju1.6planetlab.edu.cn
CERNET - Tianjin University
219.243.200.49
neu1.6planetlab.edu.cn
CERNET - Northeast University
219.243.201.65
pku2.6planetlab.edu.cn
CERNET - Peiking University
注:由于PAPP的数据缺失问题,上述节点共组成610对节点(15对节点的RTT序列缺失),所有节点对的RTT序列的采样次数都大于8390.
附录二 定理1的证明
证明:若,则易得,命题成立;
若,不失一般性,假设,则.由于
又根据柯西不等式,可得 ,
所以,有 ,当且仅当时等号成立;
要严格证明,可把问题转化为以为目标函数对进行有约束非线性规划的问题,借助Lagrange成子和Kuhn-Tucker条件可以求出的最大值即为.因篇幅限制,我们用另一种直观的方法来证明右边不等号成立.首先证明当取得最大值时,中至多有1个数既不不等于,也不等于,即不存在这样的和满足.使用反证法,假设存在这样的和,若,令,显然,而且;若,令,同样有,而且;故有
这与已使取得最大值的条件矛盾.而不难证明,当中至多有1个数既不不等于,也不等于时,,即是的最大值,从而.
证毕.
6月有数十个文件在RTT元组矩阵后多出了一行非法字符,因其不对本文造成任何影响,故没有列出.
这与两端节点的网络拓扑关系有关,因为有研究结果表明互联网的负载受人类的作息习惯影响,例如企业网络在工作日的负载高于周末,而家庭用户则恰恰相反;但是,当两个节点间的路由需要经过较多异质网络(如两个位于不同大洲的节点)时,这种效应几乎可以忽略.
选择的原则是它们与Duke大学的3个节点间RTT采样数据缺失最少
本文的讨论仅限于PAPP中使用PING探测RTT的情况.在实际应用中,如果上次业务要求终端节点对数据包进行较大计算量的处理或者需要传送较大的数据包,那么终端节点的硬件配置,接入方式和带宽可能会对平均RTT造成不可忽略的影响.
从PING的工作原理来看,源节点和目标节点进行的操作不同.如果RTT的数学期望受终端节点的硬件配置或接入方式和网络带宽的影响显著,那么RTT应该不具有对称性.
考虑到RTT的均值具有对称性(本文3.3.5节),所以我们仅统计了中国的节点作为源节点,美国和欧洲的节点分别作为目标节点;以及美国的节点作为源节点,欧洲节点作为目标节点的节点对.
