第32卷第4期 哈尔滨工程大学学报 Val.32.4 2011年4月 Journal of Harbin Engineering University Apr.2011 doi:10.3969/j.issn.1006-7043.2011,04.010 全源NT技术的接入网链路丢包率推断 段琪，蔡皖东，田广利 (西北工业大学计算机学院，陕西西安710072) 摘要：针对接人网链路丢包率具有非对称性，单源和多源的NT技术只能推断单向链路性能的问题，提出全源T的测 量模式，研究了基于全源T的链路丢包率估计技术，提出了将全源网络结构转化为可辨识网络结构的方法，并给出采 用EM算法和MCMC算法的链路丢包率估计方法.仿真实验表明该推断方法是有效的. 关键词：NT;链路丢包率：链路性能推断：EM算法：MCMC算法 中图分类号：TP393文献标识码：A文章编号：1006-7043(2011)04-045107 Research on access network link loss rate inference of full source network tomography DUAN Qi,CAI Wandong,TIAN Guangli (School of Computer Science,Northwestern Polytechnical University,Xian 710072,China) Abstract:The link loss rate of access network has asymmetry.However,single and multiple source network tomo- graphy can only infer the link performance of one direction.Therefore,a full source measurement pattern was pro- posed and link loss rate inference technology based on full source network tomography was researched in this paper. A method of transforming the full source network to the identifiable network was proposed.Furthermore,the EM al- gorithm and the MCMC algorithm which infer the link loss rate were derived,and their effectiveness was validated by simulation results. Keywords:network tomography;link loss rate;link parameter inference;EM algorithm;MCMC algorithm 目前，随着网络硬件的升级，骨干网络的丢包率等.多源测量采用多个源节点对多个目的节点的端 通常很低，相对骨干网，接人网的性能往往无法保到端测量，是单源测量方法的扩展.设源节点和目的 证，丢包较严重的情况一般出现在接人网.同时，由节点的个数分别为M、N,则测量覆盖的网络结构称 于接人网带宽和用户数据流量具有的非对称性，链为M-by-N网络结构，研究成果主要集中在拓扑推 路丢包率普遍存在非对称性.NT(network tomo- 断上[3).由于链路性能的非对称性，采用单源或多 graphy)是在网络拓扑固定的条件下，根据网络外部 源测量方式，只能得到从源节点到目的节点路径方 的测量信息来分析和推断网络内部的性能以及网络 向的丢包率，无法得到从目的节点到源节点路径方 拓扑1).目前，NT技术研究主要采用单个测量源节 向上的丢包率. 点（简称单源NT),如AT&T和马萨诸塞州立大学的 本文提出全源测量模式.全源测量是多源测量 MINC multicast-based inference of network-internal 的扩展，即每个部署节点都向其他部署节点发送测 characteristics)以及莱斯大学研究的单播NT项目 量包.在部署节点数量相同的情况下，全源测量可以 覆盖更多的链路，推导出更多的链路性能信息.更主 收稿日期：2009-11-13 要的是，全源测量可以推断链路上行和下行2个方 墓金项目：国家863计划资助项目(2009AA01Z424):教育部博士点 基金资助项目(200806990030). 向上的性能，解决接人网性能的非对称问题.但另一 作者简介：段琪(1983-)，男，博士研究生，E-mail:dug0118@hotmail. com; 方面，全源测量的拓扑推断和链路性能的推导也是 蔡皖东(1955-)，男，教授，博士生导师. 最困难.目前尚未见全源NT拓扑推断和链路性能 通信作者：段琪， 推断研究文献.综上，研究端用户如何通过端到端测 万方数据
第32卷第4期 2011年4月 哈尔滨工程大学学报 Journal of Harbin Engineering University V01．32№．4 Apr．2011 doi：10．3969／j．issn．1006—7043．201 I．04．010 全源NT技术的接入网链路丢包率推断 段琪，蔡皖东，田广利 (西北工业大学计算机学院，陕西西安710072) 摘要：针对接入网链路丢包率具有非对称性，单源和多源的NT技术只能推断单向链路性能的问题，提出全源NT的测 量模式，研究了基于全源NT的链路丢包率估计技术．提出了将全源网络结构转化为可辨识网络结构的方法，并给出采 用EM算法和MCMC算法的链路丢包率估计方法．仿真实验表明该推断方法是有效的． 关键词：NT；链路丢包率；链路性能推断；EM算法；MCMC算法 中图分类号：TP393文献标识码：A文章编号：1006-7043(2011)04-0451-07 Research on access network link loss rate inference of full source network tomography ·DUAN Qi，CAI Wandong，TIAN Guangli (School of Computer Science，Northwestern Polytechnical University。)(i锄710072，China) Abstract：The link lOSS rate of access network has asymmetry．However．single and multiple source network tomo． graphy can only infer the link performance of one direction．Therefore，a full source measurement pattern was pro· posed and link loss rate inference technology based on full source network tomography was researched in this paper． A method of transforming the full source network to the identifiable network was proposed．Furthermore．the EM a1． gorithm and the MCMC algorithm which infer the link loss rate were derived，and their effectiveness was validated by simulation results． Keywords：network tomography；link loss rate；link parameter inference；EM algorithm；MCMC algorithm 目前，随着网络硬件的升级，骨干网络的丢包率 通常很低，相对骨干网，接入网的性能往往无法保 证，丢包较严重的情况一般出现在接入网．同时，由 于接入网带宽和用户数据流量具有的非对称性，链 路丢包率普遍存在非对称性．NT(network tomo． graphy)是在网络拓扑固定的条件下，根据网络外部 的测量信息来分析和推断网络内部的性能以及网络 拓扑¨引．目前，NT技术研究主要采用单个测量源节 点(简称单源NT)，如AT&T和马萨诸塞州立大学的 MINC(muhicast—based inference of network—internal characteristics)以及莱斯大学研究的单播NT项目 收稿日期：2009·1l-13． 基金项目：国家863计划资助项目(2009AA012424)；教育部博士点 基金资助项目(200806990030)． 作者简介：段琪(1983一)，男，博士研究生，E-mail：duqoll8@hotmail． corn； 蔡皖东(1955-)，男，教授，博士生导师． 通信作者：段琪． 等．多源测量采用多个源节点对多个目的节点的端 到端测量，是单源测量方法的扩展．设源节点和目的 节点的个数分别为M、N，则测量覆盖的网络结构称 为M-by一Ⅳ网络结构，研究成果主要集中在拓扑推 断上【3剖．由于链路性能的非对称性，采用单源或多 源测量方式，只能得到从源节点到目的节点路径方 向的丢包率，无法得到从目的节点到源节点路径方 向上的丢包率． 本文提出全源测量模式．全源测量是多源测量 的扩展，即每个部署节点都向其他部署节点发送测 量包．在部署节点数量相同的情况下，全源测量可以 覆盖更多的链路，推导出更多的链路性能信息．更主 要的是，全源测量可以推断链路上行和下行2个方 向上的性能，解决接入网性能的非对称问题．但另一 方面，全源测量的拓扑推断和链路性能的推导也是 最困难．目前尚未见全源NT拓扑推断和链路性能 推断研究文献．综上，研究端用户如何通过端到端测 万方数据
·452· 哈尔滨工程大学学报 第32卷 量估计接人网的上行链路和下行链路的丢包率具有 2个路径的丢包率，则可以推导另外一个路径的丢 重要意义 包率 1网络模型 证明：因为log(PJ）=log0(p.A+log0(P4）,且 (P)和(Pw)相互独立，根据卷积定理已知其中 全源测量覆盖的网络结构称为全源网络结构. 2个路径的丢包率可以算出另外一个路径的丢包 图1(a)中有5个部署节点，包括1个源节点和4个 率. 目的节点，逻辑拓扑中包含7个链路；图1(b)有5 在单播单源NT中，普遍采用的测量方法是，将 个部署节点，包括2个源节点和3个目的节点，逻辑 1-by-N网络分解为多个1-by-2子网，分别采用包对 拓扑中包含10个链路：图1(c)有4个部署节点，逻 进行测量，如图2(a)所示.由于包对中2个报文间 辑拓扑中包含16个链路.从中可以看出全源网络结 隔很小，可以认为在公共路径P[s1,b]上2个报文 构是图型结构，包含更多的逻辑链路，最接近真实的 网络行为相同，利用此相关性可以证明1y-网络 物理拓扑结构. 链路丢包率是可辨识的（定理2）.如图2(b)所示， 对于2by-1子网，源节点31和32分别发送探测包 pk和pk21,由于pk.:和pk2.在路径P[s]和P[s2, 门上的时延是随机的，无法保证pk,,和pk.1同时到 达汇合点而形成包对.因此对于2-by-1子网链路丢 @@@@ 包率的推断，2-by-1子网是不可辨识的.因此本文的 测量方法也是对每个1-by-2子网采用包对进行测 (a)单源测量 (b)多源测绿 (c)全源测量 量 图1网络测量结构示意图 Fig.1 The sketch map of the network measurements structure 假设测量网络具有以下特性：1)网络节点之间 不存在多路径：2)测量过程中网络拓扑稳定；3)骨 干网的链路丢包率远小于接人网的链路丢包率.用 G(V,L)来描述全源网络拓扑，其中V是节点集合，L (a)1-by-2 b)2-by-1 是连接节点的链路集合.节点集合S和I分别表示 源节点集合（同时也是目的节点集合）和中间节点 图21-by-2子网和2-by-1子网的测量方法 Fig.2 Measurements methods of the 1-by-2 network 集合，V=SU1.其中，中间节点的入度和出度大于等 and the 2-by-1 network 于1，且不能同时为1.人度大于1的中间节点叫汇 由于全源网络结构包含更多的链路，采用包对 合节点，出度大于1的中间节点叫分叉节点.部署节 测量无法保证每个链路是可辨识的.以3个源节点 点和中间节点之间的链路属于接入网，中间节点之 的全源网络结构为例.网络拓扑结构包含6种网络 间的链路属于骨干网.节点到节点j的路径用 结构，如图3所示.为方便表示，0(P[54,)] P[iJ]表示；路径p的丢包率用9(P）表示，通过率 (s4eS,ieI)简记为0,0(P[i,sk])简记为0'； 用0表示，0=1-0；为了方便表示，链路1的丢包率 (P[。,i。])(i。,6∈)简记为a.对图中每个网络 用0.P[k,]和P[k,j]的共享路径用P[k;i,门表 结构中的3组1-y-2子网进行包对测量，根据定理 示，分叉节点用b(k;,)表示，由源节点k和目的节 2,可以得到一些链路的丢包率，然后利用定理1不 点i,J组成的1-by-2子网记为G 断推导，直到无法找到满足推导条件的链路.最后可 定义对某种网络结构，采用端到端的测量，通 辨识链路的丢包率（采用通过率表示）如表1所示. 过测量数据可以唯一无偏地估计网络中逻辑链路的 可以看出，6种网络结构中只有图3(c)所示结构所 链路性能参数，称该逻辑链路是可辨识的，如果链路 有链路丢包率是可辨识的，由于骨干网链路丢包率 中所有逻辑链路是可辨识的，称该网络结构是可辨 相当很小，可以采用c近似估计0，根据表1所示， 识的. 所有接入网的上行和下行丢包率是可以近似估 定理1路径P,包含路径P.和P,已知其中 计的 万方数据
·452· 哈尔滨工程大学学报 第32卷 量估计接入网的上行链路和下行链路的丢包率具有 重要意义． 1 网络模型 全源测量覆盖的网络结构称为全源网络结构． 图1(a)中有5个部署节点，包括1个源节点和4个 目的节点，逻辑拓扑中包含7个链路；图l(b)有5 个部署节点，包括2个源节点和3个目的节点，逻辑 拓扑中包含10个链路；图1(c)有4个部署节点，逻 辑拓扑中包含16个链路．从中可以看出全源网络结 构是图型结构，包含更多的逻辑链路，最接近真实的 物理拓扑结构． 瓜×× (a)单源测量 (b)多源测量 (c)全源测量 图1 网络测量结构示意图 Fig．1 The sketch map of the network measurements structure 假设测量网络具有以下特性：1)网络节点之间 不存在多路径；2)测量过程中网络拓扑稳定；3)骨 干网的链路丢包率远小于接入网的链路丢包率．用 G(y，L)来描述全源网络拓扑，其中y是节点集合，三 是连接节点的链路集合．节点集合|s和，分别表示 源节点集合(同时也是目的节点集合)和中间节点 集合，V=Su，．其中，中间节点的人度和出度大于等 于1，且不能同时为1．人度大于1的中间节点叫汇 合节点，出度大于1的中间节点叫分叉节点．部署节 点和中间节点之间的链路属于接入网，中间节点之 间的链路属于骨干网．节点i到节点J的路径用 P[i,j]表示；路径P的丢包率用O(p)表示，通过率 用0表示，0=1—日；为了方便表示，链路z的丢包率 用01．P[k，i]和P[．|}，-『]的共享路径用P[I|}；i，，]表 示，分叉节点用b(k；iJ)表示，由源节点k和目的节 点i，．『组成的1一by一2子网记为G：，． 定义对某种网络结构，采用端到端的测量，通 过测量数据可以唯一无偏地估计网络中逻辑链路的 链路性能参数，称该逻辑链路是可辨识的，如果链路 中所有逻辑链路是可辨识的，称该网络结构是可辨 识的． 定理1 路径P“，包含路径Pm和风，，已知其中 2个路径的丢包率，则可以推导另外一个路径的丢 包率． 证明：因为l090(pf，f)=l090(p{，女+l090(pI．，)，且 0(p泓)和o(p¨)相互独立，根据卷积定理已知其中 2个路径的丢包率可以算出另外一个路径的丢包 率． 在单播单源NT中，普遍采用的测量方法是，将 1一by—N网络分解为多个1-by-2子网，分别采用包对 进行测量，如图2(a)所示．由于包对中2个报文间 隔很小，可以认为在公共路径P[s。，b]上2个报文 网络行为相同，利用此相关性可以证明1．by—N网络 链路丢包率是可辨识的(定理2)．如图2(b)所示， 对于2-by-l子网，源节点s。和s：分别发送探测包 础¨和p后：’1，由于础1'l和础：，。在路径P[s。，]和P[s：， ，]上的时延是随机的，无法保证础¨和pI|}：．。同时到 达汇合点而形成包对．因此对于2·by-1子网链路丢 包率的推断，2．by．1子网是不可辨识的．因此本文的 测量方法也是对每个1．by-2子网采用包对进行狈0 量． (a)1-by一2 (b)2-by-1 图2 1-by-2子网和2-by-1子网的测量方法 Fig．2 Measurements methods of the 1-byr-2 network and the 2-by-1 network 由于全源网络结构包含更多的链路，采用包对 测量无法保证每个链路是可辨识的．以3个源节点 的全源网络结构为例．网络拓扑结构包含6种网络 结构，如图3所示．为方便表示，0(P[s。，i，)] (s女∈s，i：∈，)简记为0。，0(P[i。，靠])简记为吼’； 0(P[i。，i。])(i。，i。∈，)简记为Ot护对图中每个网络 结构中的3组1-by-2子网进行包对测量，根据定理 2，可以得到一些链路的丢包率，然后利用定理1不 断推导，直到无法找到满足推导条件的链路．最后可 辨识链路的丢包率(采用通过率表示)如表l所示． 可以看出，6种网络结构中只有图3(c)所示结构所 有链路丢包率是可辨识的．由于骨干网链路丢包率 相当很小，可以采用触近似估计0，根据表1所示， 所有接入网的上行和下行丢包率是可以近似估 计的． 万方数据
第4期 段琪，等：全源NT技术的接入网链路丢包率推断 ·453· © 络链路进行合并.网络结构中转化后的网络结构表 0,Te 示为G(V,L').转化算法如下. Input:G(V,L) nitialization:V'=Φ，IL=Φ Process: ©g 6⊙ ①ForG (a) (b) IL=ILU P[k,b[k;i,j]],p[b[k;i],i],P[b[k;i, 门门 ( ④ 8肝g End for ②Forp:eL a/ For PiEIL-p, If p:EP;do 8©≥①4 ©g ©g 6ga IL=IL-pil +ipj-Pi End if (c) d End for ④ ④ End for oe' 3 For P[i,j]eIL do V'=V'Uij A End for a12 Output:G'(V,IL) g 2链路丢包率推断算法 ©日 转换后的可辨识拓扑G(,L')中的链路个数 (e) () 记为n.测量的1-by-2子网集合记为G.对于 图33个源节点的6种全源拓扑结构 G,∈G,采用包对进行N次测量，第m次的路径 Fig.3 The six full source network structures with p[k,]的测量值记为，y=0,表示测量包丢 three sources 失，y=1表示测量包未丢失.记向量Y=(y, y,…,y),1-by-2子网的测量结果计为 表13个源节点的全源网络结构中可辨识的链路丢包奉 Y=(yy),(y,y),…,(y0,y). Table 1 The identifiable link loss rate in the full source 记N(y)表示测量值为特定值y的次数，N表示总的 network structure with three sources 测量数.测量集合记为Y.推断算法中，极大似然估 拓扑 可辨识的丢包率（通过率） 计和Bayesian估计是2种主要的推断方法，由于“不 8c4,8,'au1,d2a2a,02'an,8a4,8'ae 可见数据”的缺失，推断方法往往无法直接计算，因 8,0,'a1,8,'a3u,8,2'a2,02'a2,0,83'an,8'ag 此需要采用数值计算方法，其中EM6和MCMC?) 日1,81'，82,82'，8,8'，cn,a8,a1 方法是2种常用的方法.本文也采用EM和MCMC2 日，a2,8,'a1,8,',8,8',an,au 种方法进行推断。 e 8,a2,月'a21,8'a1,82'82,a'aa,8'an 2.1基于EM算法的MLE 8,0'ag,8,aa,82'a2,8,8' 采用极大似然估计来推断全源网络内部链路丢 包率.测量值发生概率记为g(Y;6)=P(Y=Y,0). 对于一般的全源网络结构，为了使网络结构具 所以所有的观测值的对数似然函数为 有可辨识性，同时降低推断算法复杂度，需要对网络 I(Y,0)=logg(Y;0)= 结构中的不可辨识链路进行合并，直到整个网络结 (1) 构是可以辨识的.转化过程分为3步：1)根据定理 ∑∑N(yau)logg(ywi0). VOJeQL.ije(0.I)2 2,所有1-by-2测量子网中的3个逻辑链路是可 在得到测量集合Y后，利用MLE的方法求0的估计 以辨识的：2)定理1进行推导：3)对无法辨识的网 值为 万方数据
第4期 段琪，等：全源NT技术的接入网链路丢包率推断 (e) 图3 3个源节点的6种全源拓扑结构 Fig．3 The six lull SOllllrCe network structures with three$Olll'CeS 表1 3个源节点的全源网络结构中可辨识的链路丢包率 Table 1 The|dentiffable link loss rate in the full$OUl'Ce network structure with three SOUrCeS 拓扑 可辨识的丢包率(通过率) 口010t14，0l 7口4l，吼d24，02’a42，日3a34，03’or43 6 0l，0l’o电l，0l’仪3l，02，02’a12，02’a32，03，03’a23，03’a13 c 01，01’，02，02’，03，03’，Otl2，a23，d3l d 0l，a12，0I’a3l，02，02’，岛，03’，a32，a23 e 0l，a12，0l’a2l，0I’n31，02’0’2，03’Ot23，03’n23 一 一 一 一 一 一 f 010t13，0l’d23，020t23，02 7a32，03，03’ 对于一般的全源网络结构，为了使网络结构具 有可辨识性，同时降低推断算法复杂度，需要对网络 结构中的不可辨识链路进行合并，直到整个网络结 构是可以辨识的．转化过程分为3步：1)根据定理 2，所有1一by一2测量子网中的3个逻辑链路是可 以辨识的；2)定理1进行推导；3)对无法辨识的网 络链路进行合并．网络结构中转化后的网络结构表 示为G’(∥，￡’)．转化算法如下． Input：G(V，L) Initialization：V’=函，／L=中． Process： ①For G0 ／L=见u{P[七，b[矗；i√]]，P[b[矗；ij]，i]，P[b[志；i， J]，力 End for ②For Pi∈儿 Forp，E／L一{Pi}， IfPi∈pi do 儿=见一{n}+{pJ—P；} End if End foo End for ③For P[i J]∈见do y’=y’u{i√} End for Output：G’(∥，儿) 2链路丢包率推断算法 转换后的可辨识拓扑G’(y’，￡’)中的链路个数 记为凡．测量的1一by一2子网集合记为G．对于 G：．，∈G，采用包对进行Ⅳ次测量，第m次的路径 P[后，i]的测量值记为，，∥，y蹦=0，表示测量包丢 失，y趼=1表示测量包未丢失．记向量y=(“?， ，，：?，…，y：：’)，1一by一2子网的测量结果计为 LⅫ=((y觊，，：y)，(Yk㈣,i，)，：2))，…，(以，，武，))． 记|『v(Y)表示测量值为特定值Y的次数，Ⅳ表示总的 测量数．测量集合记为y．推断算法中，极大似然估 计和Bayesian估计是2种主要的推断方法，由于“不 可见数据”的缺失，推断方法往往无法直接计算，因 此需要采用数值计算方法，其中EN[61和MCMC【7{1 方法是2种常用的方法．本文也采用EM和MCMC 2 种方法进行推断． 2．1基于EM算法的MLE 采用极大似然估计来推断全源网络内部链路丢 包率．测量值发生概率记为g(y；0)=P(y=y，0)． 所以所有的观测值的对数似然函数为 Z(y，p)=logg(Y；O)= ∑ ∑N(y蚓J)logg(y蚓J；口)． (1) V60E印t．iJ6(o，I)2 在得到i贝0量集合y后，利用MLE的方法求p的估计 值为 万方数据
·454· 哈尔滨工程大学学报 第32卷 0=argmaxel(Y;0). (2) N,(0) (8) 上式无法直接求解，采用EM算法.为此引入测 N,(1)+N,(0) 量包在各个逻辑链路的丢包率作为不可见数据以简 4)迭代.交替地使用E步和M步进行计算，直 化上式对于VGG,用=(x,x, 到估计的延迟分布概率达到收敛状态，即1+)- x,)表示第m次探测包在每条链路上丢失状态 1≤&.其中，6表示预先设定的门限值. 集合，记xw=(x,,…,）,X=(x 利用EM算法求解速度相对较快一些，但是由 G,∈G).因此完全数据的对数似然函数可以表示 于似然函数可能存在多个稳定点，但仅有一个是最 为 大值点.使用EM算法可能收敛于一个局部最大值 (Y,X:0)=logg(Y,X;0)= 点，所以要求算法要选取合适的初始值.EM算法的 logg(YX;0)logg(X;0). (3) 复杂性主要是由E步中计算条件期望N,(1)所决 实际上，在已知探测包在所有链路上的丢包率 定，其复杂性随着探测报文对的数量和网络拓扑链 集合X的条件下，必然获得相应的观测值Y,即 路数的增加而增加，计算的复杂性明显增大 2.2基于MCMC的Bayesian估计 g(YlX:0)=1,logg(Y‖X;8)=0.因此 I(Y,X:0)logg(X:0)=logg(xja)= 采用Bayesian方法对链路丢包率的分布进行估 Y床eG 计.随机近似算法MCMC(Markov Chain Monte N(0)log0:N(1)log(0:). (4) Carlo),在抽样过程中收敛速度较快，常用于概率推 测中.其中Gibbs抽样是MCMC方法之一，在先验分 在等式中，N,(1)(或N,(0))表示链路l未丢失 布密度函数未知的情况下，根据后验概率分布函数 (丢失)的报文数量.在集合X的已知条件下，而8， 不断抽样得到一个Markov链，其抽样数值的分布收 的MLE估计值8，可以通过上式进行求导来获得 敛于先验分布密度函数.现有的许多Gibbs抽样方 N(0) 8,=N,(0)+N(0) (5) 法被用于解决Bayesian推测问题，尤其是用于发现 一些隐含的或者不完整的数据信息.Dong Guo]等 集合X和N,(d)(d∈10,1{是不可以见数据， 人将MCMC方法用于单源链路报文丢包率的推测 利用EM算法进行求解，该算法使用O,和N,(d)的 上，实验结果表明该方法是可行的和有效的、 前次估计值来推断它们当前的估计值.这样，通过有 所有的测量值联合概率函数为 限步的迭代来得到收敛的6值.为此，设表示6， p(y:0)=ΠΠp(yw0). (9) 第e步的概率估计值，其中e为正整数.其过程如下 Gc0:ts(0.1)2 所示： 依据式(9)进行Bayesian推断，使得推测出的 1)初始化.选择所有链路的初始丢包率.由 参数值&符合后验概率分布p(gIY).在Bayesian分 于缺乏0的先验信息，可假设0=0.5. 析中，Beta分布经常作为二项分布的先验概率分布. 2)E步(Expectation).在已知完整的测量值集合 在逻辑链路上的报文丢失的次数就是一个二项分 Y和当前第e步估计值8'的条件下，计算对数似然函 布.假设逻辑链路报文丢失的先验概率符合Bta分 布： 数的条件期望日” T(a:+b:) Q(8",8e)=E[l(Y,X;0")1Y]= 8-Bea(a,b,）=ra)r'(1-0,)*, ∑(N,(0)log8,"+N,(1)log8,"). (6) i=1,2,…,n (10) 在无任何先验信息的情况下，设置Beta分布的 式中， 参数a,=1和b:=1,既均匀分布.下面以图2(a)为 N,(d)=E[N,(d)1Y]= 例，描述如何用Gibs抽样方法来推测链路报文丢 ∑∑N(y)logg(X()= VC时eOgi5Yk,iU 失率 dl Yid=yyi). (7) Pexy p(xpx)p(x) 3)M步(Maximization).根据上式估计的N, (d),从而获得第e+1步时延分布概率的估计值： p61&p0816p1 N)=argmaxaF(0,”,0}）= 0)p(p(e)p(). (11) 万方数据
·454· 哈尔滨工程大学学报 第32卷 0=argmax口Z(Y；O)． (2) 上式无法直接求解，采用EM算法．为此引入测 量包在各个逻辑链路的丢包率作为不可见数据以简 化上式．对于V G0∈G，用x路j=(菇蹦蛳州，茁：高训” 戈：墨M J)表示第m次探测包在每条链路上丢失状态 集合，记X。；；J=(工f}0，工：≥，…，工l：：)，x=(x。；；J G：．，∈G)．因此完全数据的对数似然函数可以表示 为 Z(y，X：0)=logg(Y，X；O)= logg(Y lI x；p)+logg(X；p)． (3) 实际上，在已知探测包在所有链路上的丢包率 集合x的条件下，必然获得相应的观测值y，即 g(Y 0 X；O)=1，logg(Y lI X；O)=0．因此 z(Y，X；O)=logg(X；0)=∑logg(xk；id；or)= VcbEG 乏：NI(0)logol+Ⅳj(1)log(0f)． (4) 在等式中，Ⅳl(1)(或Ⅳj(0))表示链路Z未丢失 (丢失)的报文数量．在集合x的已知条件下，而Ol 的MLE估计值Ot可以通过上式进行求导来获得 ¨鼎岛2丽矛葡 (5) 集合工和M(d)(d∈{0，1 f是不可以见数据， 利用EM算法进行求解，该算法使用Ol和肌(d)的 前次估计值来推断它们当前的估计值．这样，通过有 限步的迭代来得到收敛的0值．为此，设卯’表示0。 第e步的概率估计值，其中e为正整数．其过程如下 所示： 1)初始化．选择所有链路的初始丢包率耐∞．由 于缺乏Or的先验信息，可假设叫∞=o．5． 2)E步(Expectation)．在已知完整的测量值集合 y和当前第e步估计值磷的的条件下，计算对数似然函 数的条件期望佛，，． Q(仇”，口；¨)=岛：¨[z(y，x；0，”)I Y]= 芝：(ⅣJ(0)l090l”+N!(1)l090f”)． (6) 式中， NI(d)=EbI。)[Ⅳj(d)I Y]= ∑ ∑Ⅳ(j，¨J)logg(X(／)= vc,145口^．iJ6f‘．‘J d l L．iJ=Y婶J；旷’)． (7) 3)M步(Maximization)．根据上式估计的川 (d)，从而获得第e+1步时延分布概率的估计值： 觚“”=argmax／；F(茸”，研曲)= 川(0) … Ⅳf(1)+Ⅳf(0) 4)迭代．交替地使用E步和M步进行计算，直 到估计的延迟分布概率达到收敛状态，即I研“¨一 硝钉I≤￡其中，占表示预先设定的门限值． 利用EM算法求解速度相对较快一些，但是由 于似然函数可能存在多个稳定点，但仅有一个是最 大值点．使用EM算法可能收敛于一个局部最大值 点，所以要求算法要选取合适的初始值．EM算法的 复杂性主要是由E步中计算条件期望M(1)所决 定，其复杂性随着探测报文对的数量和网络拓扑链 路数的增加而增加，计算的复杂性明显增大． 2．2基于MCMC的Bayesian估计 采用Bayesian方法对链路丢包率的分布进行估 计．随机近似算法MCMC(Markov Chain Monte Carlo)，在抽样过程中收敛速度较快，常用于概率推 测中．其中Gibbs抽样是MCMC方法之一，在先验分 布密度函数未知的情况下，根据后验概率分布函数 不断抽样得到一个Markov链，其抽样数值的分布收 敛于先验分布密度函数．现有的许多Gibbs抽样方 法被用于解决Bayesian推测问题，尤其是用于发现 一些隐含的或者不完整的数据信息．Dong Guo坤1等 人将MCMC方法用于单源链路报文丢包率的推测 上，实验结果表明该方法是可行的和有效的． 所有的测量值联合概率函数为 P(Y；O)=兀 兀p(j，蜘J；鳓． (9) Vc,k,i印I；lj6(0。1)2 依据式(9)进行Bayesian推断，使得推测出的 参数值口符合后验概率分布P(OI Y)．在Bayesian分 析中，Beta分布经常作为二项分布的先验概率分布． 在逻辑链路上的报文丢失的次数就是一个二项分 布．假设逻辑链路报文丢失的先验概率符合Beta分 布：口；一Beta(口i，6i)=揣p?‘。1(1一pi)虬～， i=1，2，…，n． (10) 在无任何先验信息的情况下，设置Beta分布的 参数ai=1和b；=l，既均匀分布．下面以图2(a)为 例，描述如何用Gibbs抽样方法来推测链路报文丢 失率． P(O五，y)优l-Ip鹾’l口五)p(蠼’I口五)P④忑)= 兀p(蜡’I晓硝’)p(蠼’I岛露’)p(谨’l B)p(B)p(晓)p(岛)． (11) 万方数据
第4期 段琪，等：全源NT技术的接入网链路丢包率推断 ·455. 其中： 分布抽取0©和X,然后利用在目的节点得到的 p(y1&x)=g1-米(1-，)4，(2) 测量值抽取0和X,假设总共抽取了J=J。+J,次， p(y1g,x)=g1w(1-8)发，(13) 其中Jo是通过Gibbs抽样得到的Markov链到达稳 p(x1a)=0-w(1-g).(14) 定状态所需的抽样次数，J,是用于推测链路报文丢 把式(10)、(12)~(14)代入到式(11)中，可以 失率需要的抽样次数.利用J,轮次的抽取数值的众 得到： 数计算0，详细算法如下， p(0,X,)x[6241-(1-)-1*24]× Initialization:Draw random samples 6)and o)from [8m21-(1-8)-1+4岁]× their prior [6-121-(1-0,)-1+20].(15) Sample: Forj=1,2,…,Jdo 根据式(15)，得出逻辑链路的后验报文丢失的 For 0, 分布仍然是Beta分布，每条逻辑链路报文丢失对应 的Beta分布分别为 draw a sample 0)-p()-) End for p(I YX)- Fork=1,2,…,N, Beta(a+N-∑xb+∑x), (16) tempX=Φ； p(%1Y,X,a,4)- Fori=1,2,…,n Beta(a+∑x（1-y),h+∑y用)，(17) draw a sample () p(6IYX8B)- p(((-temp()-1), Bta(,+∑1-增)h+∑y).(18) (temp())"; 同时，网络内部节点上未观测到的数据X。可以 tempx()=tempx( 根据测量值Y推测出来.由于 End for p(x=01y4=1,0)=0, End for p(x=01y=1,0)=0, End for Inference:Calculate from p(=01y增=0，发=0，)=a+(1-8)88 Output:0 (19) 在MCMC抽样方法中，一个需要解决的问题是 所以可以将p(x=01Y,0)统一表示为 如何判断抽样得到Markov链到达了稳定状态.目前 p(x=01Y,0)= 主要的方法是采用遍历均值法判断是否收敛.当计 算的均值稳定后，可以认为gbbs抽样收敛.但是本 (1-)1-增)a+4-9,9,6（20） 中当丢包率较小时，beta分布具有很大的非对称性， 根据满条件分布式(16)~(20)，用Gibbs抽样 一个较大的抽样值对平均值的影响很大.即使 方法连续抽样，就可得到{01,02,0}和x。的抽样数 Markov链稳定，遍历均值之间依然具有较大的方 据，每个变量相应的抽样数据就分别组成一条 差.因此本文没间隔2个抽样植抽取一个值，每抽取 Markov链.在Markov链趋于稳定后，继续抽样J轮， 50值后，根据式(21)计算估计值，利用估计值判断 0的抽样值为0，就可以利用0的众数作为0的 是否收敛 估计值当抽样数量较少时，不易统计的众数， 3仿真 因此本文采用matlab中的bata函数的拟合函数bat- afit对gD进行拟合，得到后验分布bata分布的参数 采用网络仿真工具s-2进行仿真.对于每个 a'和b:',利用式(21)可以得到0的估计值： 1by-2测量子网，探测包对为2个间隔为0.01ms、周 8=8'-1 期为0.1s的CBR数据流，每个1-by-2测量子网产 a:'+6,'-2 (21) 生N个测量值.链路丢包率的产生采用在每条逻辑 对于一般的网络拓扑，用Gibbs抽样方法抽取0 链路上设置随机丢包错误模型进行实现，采用gwk 和X,使其符合联合后验概率分布P(0,X1Y).0) 工具分析仿真输出的口文件，首先将每条链路真实 和X是第轮抽样的结果.算法首先依据先验概率 的丢包率统计下来，作为真实的链路报文丢包率，用 万方数据
第4期 段琪，等：全源NT技术的接入网链路丢包率推断 其中： 烈／ydl(t’I晚，笫∥)=酽’‘1删’(1一02)。l^)州，(12) p(谨’I岛，菇∥)=毋”‘1删’(1一03)‘l”埘，(13) p(xl‘’1 0。)=O(I-xm(1一B)5哆 (14) 把式(10)、(12)一(14)代人到式(11)中，可以 得到： p(O，鼍，y)优 2-1+∑#gk)(1删’：(卜如)62-1+∑x5^)坩’-]× [伊‘1+∑则1一蠼’，(1—03)b3小y帕蜘× [矿t-l+∑(h㈣(1一B b；-I+∑2q． (15) 根据式(15)，得出逻辑链路的后验报文丢失的 分布仍然是Beta分布，每条逻辑链路报文丢失对应 的Beta分布分别为 p(B l，五，岛，岛)～ Beta(a，+J^，一∑∥A+∑∥)， (16) p(醍I y五概，岛)一 Beta(az+∑《’(1一镒’)，62+∑嚣’瑶’)，(17) p@I城A恳)一 B咖电+∑蛰’(1一蠼’)岛+∑孝’蠼’)． (18) 同时，网络内部节点上未观测到的数据瓦可以 根据测量值Y推测出来．由于 p(xl”=0 I)，￡’=1，一)=0， p(xl”=0 I蝶’=1，鳓=0， p(球’=oI瑶’=o，蠼’=o，9)2万_赫· (19) 所以可以将P(筇≯=oI Y，们统一表示为 p(戈：‘’=0 y，口)= (1一y鼽1一)，麓’’订石‰·(20) 根据满条件分布式(16)一(20)，用Gibbs抽样 方法连续抽样，就可得到{0。，612，03}和茹。的抽样数 据，每个变量相应的抽样数据就分别组成一条 Markov链．在Markov链趋于稳定后，继续抽样．，轮， 0的抽样值为0‘D，就可以利用秽‘’’的众数作为口的 估计值．当抽样数量较少时，不易统计∥’的众数， 因此本文采用matlab中的bata函数的拟合函数bal． afit对口u’进行拟合，得到后验分布bata分布的参数 ai’和bi’，利用式(21)可以得到p的估计值： a．’一】 0i 2丁确‘ (21) 对于一般的网络拓扑，用Gibbs抽样方法抽取口 和x，使其符合联合后验概率分布P(口，xI Y)．口“’ 和Xu’是第轮抽样的结果．算法首先依据先验概率 分布抽取口‘o’和x‘∞，然后利用在目的节点得到的 测量值抽取口和x，假设总共抽取了J=J0+^次， 其中厶是通过Gibbs抽样得到的Markov链到达稳 定状态所需的抽样次数，^是用于推测链路报文丢 失率需要的抽样次数．利用．，。轮次的抽取数值的众 数计算0，详细算法如下． Initialization：Draw random samples口(o)and X(o)from their prior． Sample： For_『=1，2，…，．，do For 0i∈口， draw a sample硝订～P(佛lx‘‘’一1’’J‘7一¨，0一{佛}) End for For k=1，2，…，JIv， temp X=中： For i=1，2，…，n draw a sample(髫≯)u’～ P(髫；”I秽：力，(y¨’)∞，(x仆’一tempx“’一戈：”)卜1)， (tempx¨’)“； tempx‘‘’=tempx‘‘’+㈧‘’}； End for End for End for Inference：Calculate 0 from{∥’+¨，砂+”，…，p‘叫 Output：p 在MCMC抽样方法中，一个需要解决的问题是 如何判断抽样得到Markov链到达了稳定状态．目前 主要的方法是采用遍历均值法判断是否收敛．当计 算的均值稳定后，可以认为gibbs抽样收敛．但是本 中当丢包率较小时，beta分布具有很大的非对称性， 一个较大的抽样值对平均值的影响很大．即使 Markov链稳定，遍历均值之间依然具有较大的方 差．因此本文没间隔2个抽样植抽取一个值，每抽取 50值后，根据式(21)计算估计值，利用估计值判断 是否收敛． 3 仿 真 采用网络仿真工具as一2进行仿真．对于每个 1．by-2测量子网，探测包对为2个间隔为0．0lms、周 期为0．1 S的CBR数据流，每个1一by-2测量子网产 生J)v个测量值．链路丢包率的产生采用在每条逻辑 链路上设置随机丢包错误模型进行实现．采用gawk 工具分析仿真输出的tr文件，首先将每条链路真实 的丢包率统计下来，作为真实的链路报文丢包率，用 万方数据
·456· 哈尔滨工程大学学报 第32卷 于与推断的丢包率进行比较，评价算法的准确性，同 所示分别给出两组迭代次数和推断值之间的关系. 时将目的节点的获得的测量集合Y写人到文件，用 第一组中设置推断算法初始链路丢包率为0.5，第二 matlab程序实现推断算法，并将Y文件作为输人文 组中设置推断算法初始接入网丢包率为0.15，骨干 件进行分析，根据算法推断出来的丢包率（或者通 网为005.算法的效率，即算法收敛速度受丢包率 过率)称为推断值.推断值与真实值之间差值的平 初始值影响，通过对比可以看出，初始链路丢包率越 方，称为推断误差. 接近真实值，收敛速度越快. 3.1推断算法有效性 然后采用bs抽样算法，随着算法的不断抽 对图3(d)所示的具有3个源节点的全源结构 样，Markov链到达了稳定状态后推断值非常接近真 进行仿真，以验证算法的有效性.仿真设置2种场 实值，验证了算法的正确性.如图5所示给出了 景：1)网络中所有接人网链路的丢包率为确定值， Markov链稳定以后的62的抽样值变化情况.图6为 以方便对比.设置接入网上行链路丢包率为0.1，接 统计出来的82的抽样值分布率，可以看出众数值为 入网下行链路丢包率为0.2，骨干网链路丢包率为 0.105,接近真实值0.1， 0.01:2)网络中所有接人网链路的报文丢失不确 0.14 定，以使仿真结果更具有一般性.设置接人网链路丢 0.12 包率为0.1~0.3，骨干网链路丢包率为0.0~0.05. 在场景1)中，转化后的8个链路丢包率的真实 0.10 值1-01a12、1-0,'a3t、02、02'、03、03'、a2、a23分别 0.08 为：0.11、0.21、0.1、0.2、0.1、0.2、0.01、0.01.每个 0.06 1by-2测量子网，产生4000测量值 1-(1-81-a 0.04 1-(1-0,1-a) 500 600 700800 9001000 0.30 0 、 抽样次数 0.25 G2 图5 Markov链稳定以后的02的抽样值 0.20 Fig.5 The example values of after the Markov 0.15 chains were stable 0.10 35r 0.05 30 3 020406080100120140160180200 迭代次数 20 (a)第一组 10 0.30 0.25 0.20 00.10.2030.40.50.60.70.80.91.0 8 0.15 0.10 97 图6A2的抽样值分布率 0.05 Fig.6 The example values PDF of 利用更具有一般性的场景2)研究推断算法的 020406080100120140160180200 推断误差.推断算法首先受到迭代次数或者抽样次 迭代次数 数的影响.但当推断算法收敛后，更多的迭代次数或 (b)第二组 者抽样次数，不能再减少推断误差.推断误差还受到 图4推断值与迭代次数关系 测量值个数N的影响，测量值个数越多误差越小 Fig.4 The inference value vs.iteration 图7给出了采用EM算法和gbbs抽样算法的链路 首先采用EM算法，随着算法的不断迭代，推断 丢包率02的推断误差，图中误差为相同测量值场景 值逐渐趋向于真实值，验证了算法的正确性.如图4 仿真100次的平均值.在EM算法中，仿真设置推断 万方数据
·456- 哈尔滨工程大学学报 第32卷 于与推断的丢包率进行比较，评价算法的准确性，同 时将目的节点的获得的测量集合y写入到文件．用 matlab程序实现推断算法，并将y文件作为输人文 件进行分析．根据算法推断出来的丢包率(或者通 过率)称为推断值．推断值与真实值之间差值的平 方，称为推断误差． 3．1推断算法有效性 对图3(d)所示的具有3个源节点的全源结构 进行仿真，以验证算法的有效性．仿真设置2种场 景：1)网络中所有接入网链路的丢包率为确定值， 以方便对比．设置接入网上行链路丢包率为0．1，接 入网下行链路丢包率为0．2，骨干网链路丢包率为 0．01；2)网络中所有接入网链路的报文丢失不确 定，以使仿真结果更具有一艘陛．设置接入网链路丢 包率为o．1—0．3，骨干网链路丢包率为0．0～0．05． 在场景1)中，转化后的8个链路丢包率的真实 值l一01a12、1—0l’a3l、02、02 7、a3、日3’、0c32、仅23分另0 为：O．1l、O．21、0．1、0．2、0．1、0．2、O．01、0．01．每个 1一by-2测量子网，产生4 000测量值． ——1-(I-0．)(1一a】') O．30 O．25 0．20 龟0．15 0．10 O．05 ……‘l一(1—0，)(1一a31) ”2 V' ··…-乱一一a32 —一目，——吐23 —，一’ O≮20 40 60 80 l()()120140160180200 迭代次数 0'30 0．25 0．20 吣0．15 0．10 0．05 (a)第一组 r k 、∥一 一—— ≮≮一 0 20 40 60 80 l 0()120140160180200 迭代次数 (b)第二组 图4推断值与迭代次数关系 Fig．4 The inference value VS．iteration 首先采用EM算法，随着算法的不断迭代，推断 值逐渐趋向于真实值，验证了算法的正确性．如图4 所示分别给出两组迭代次数和推断值之间的关系． 第一组中设置推断算法初始链路丢包率为O．5，第二 组中设置推断算法初始接入网丢包率为O．15，骨干 网为0．05．算法的效率，即算法收敛速度受丢包率 初始值影响，通过对比可以看出，初始链路丢包率越 接近真实值，收敛速度越快． 然后采用gibbs抽样算法，随着算法的不断抽 样，Markov链到达了稳定状态后推断值非常接近真 实值，验证了算法的正确性．如图5所示给出了 Markov链稳定以后的吼的抽样值变化情况．图6为 统计出来的0：的抽样值分布率，可以看出众数值为 0．105，接近真实值0．1． 抽样次数 图5 Markov链稳定以后的吼的抽样值 Fig．5 The example values of倪after the Markov chains were stable 0 嘎 图6晚的抽样值分布率 Fig．6 The example values PDF of岛 利用更具有一般性的场景2)研究推断算法的 推断误差．推断算法首先受到迭代次数或者抽样次 数的影响．但当推断算法收敛后，更多的迭代次数或 者抽样次数，不能再减少推断误差．推断误差还受到 i贝0量值个数Ⅳ的影响，测量值个数越多误差越小． 图7给出了采用EM算法和gibbs抽样算法的链路 丢包率口：的推断误差，图中误差为相同测量值场景 仿真100次的平均值．在EM算法中，仿真设置推断 万方数据
第4期 段琪，等：全源NT技术的接人网链路丢包率推断 457· 算法初始接入网丢包率为0.15，骨干网为0.05；迭 算法在网络规模不大于30个源节点时推断速度更 代次数为200.在gibbs抽样算法中，抽样次数为 快一些.本文的研究扩展了单源断层扫描技术推断 5000.从图中可以看出：首先，当随着测量值个数的 链路的能力和适用范围 增加，推断误差逐步减少，但误差减少速度也逐步减 小：其次gbbs抽样算法的误差相对于EM算法要小 参考文献： 一些，说明gbbs抽样算法的精度高一些. [1]COATES A,HEROIII A O,NOWAK R,et al.Internet tomo- 25,*10 graphy[J].IEEE Signal Processing Magazine,2002,19(3): 765. 20 [2]CASTRO R,COATES M,LIANG G,et al.Interet tomo- 5 graphy:recent developments[J].Statistical Science,2004, 52(3):499-517. 10 [3]COATES M,RABBAT M,NOWAK R.Merging logical to- pologies using end-to-end measurements [C]//ACM SIG- ×102 COMM Conference on Internet Measurement.Miami,USA. 0246810121416182022 2003:192-203. N [4]RABBAT M,COATES M,NOWAK R.Multiple source in- 图7A,的推断误差与测量包数量关系 temet tomography [J].IEEE Joumal on Selected Areas in Fig.7 The variance of 6,vs.the number of Communications..2006,24(12):2221-2234.. measurement packets [5]BESTAVROS,BYERS J,HARFOUSH K.Inference and la- 3.2推断算法可扩展性 beling of metric-induced network topologies [J].IEEE 对工具GT-TM产生的具有20个和40个源 Transactions on Parallel and Distributed Systems,2005,16 (11):1053-1065. 节点的全源结构进行仿真，以分析算法的可扩展性、 [6]COATES M,NOWAK R.Unicast network tomography using 用仿真程序执行需要的时间表示该算法的计算量. EM algorithms[R].Houston:Rice University,2000. 在主频为2.0GHz双核CPU的计算机机上运行仿 [7]ZHU Weiping.Using Bayesian network on network tomo- 真程序，计算从推测算法开始执行到推测算法收敛， graphy[J].Computer Communications,2003,6(2):155- 计算算法执行的时间，计算结果如表2所示， 163. 表2算法的执行时间表 [8]GUO Dong,WANG Xiaodong.Bayesian inference of net- Table 2 The execution time of the algorithm work loss and delay characteristics with applications to TCP 源节点个数 performance prediction [J].IEEE Transactions on Signal 算法 3 Processing,200351(8):2205-2218. 20 40 [9]ARYA V,DUFFIELD N,VEITCH D.Temporal delay tomo- EM 3 56 900 graphy[C]//IEEE Infocom 2008.Phoenix,USA,008: Gibbs 14 192 720 276-280. 表中数据显示EM算法的执行时间小于Gbbs [10]LAWRENCE E,MICHAILIDIS G,NAIR V.Network de- 抽样算法，但随网络规模的增加，EM算法的执行时 lay tomography using flexicast experiments []Joumal of Royal Statistical Society Series B,2006,68(5):785-813. 间增加速度高于Gibbs抽样算法. [11]MENG F S,HERO III A O.Unicast based inference of 4结论 network link delay distributions with finite mixture models [J].IEEE Transactions on Signal Processing, 为了解决非对称链路性能推断问题，本文提出 2003,51(8):2219-2228. 了全源NT的测量模式，并给出采用EM算法和MC [12]LIANG G,YU B.Maximum pseudo likelihood estimation in MC算法的链路丢包率推断方法.仿真结果不仅验 network tomography [J].IEEE Transactions on Signal 证了该技术的有效性，而且通过对比，可以发现 Processing,2003,51(8):2043-2053. gbbs抽样方法比EM算法的推断误差更小；而EM [责任编辑：陈峰] 万方数据
第4期 段琪，等：全源NT技术的接人网链路丢包率推断 ·457· 算法初始接入网丢包率为0．15，骨干网为0．05；迭 代次数为200．在gibbs抽样算法中，抽样次数为 5 000．从图中可以看出：首先，当随着测量值个数的 增加，推断误差逐步减少，但误差减少速度也逐步减 小；其次gibbs抽样算法的误差相对于EM算法要小 一些，说明gibbs抽样算法的精度高一些． 剁 悠 1 02 图7巩的推断误差与测量包数量关系 Fig．7 The variance of巩、rs．the number of measurement packets 3．2推断算法可扩展性 对工具GT—ITM产生的具有20个和40个源 节点的全源结构进行仿真，以分析算法的可扩展性． 用仿真程序执行需要的时间表示该算法的计算量． 在主频为2．0 GHz双核CPU的计算机机上运行仿 真程序，计算从推测算法开始执行到推测算法收敛， 计算算法执行的时间，计算结果如表2所示． 表2算法的执行时间表 Table 2 The execution time of the algorithm S 表中数据显示EM算法的执行时间小于Gibbs 抽样算法，但随网络规模的增加，EM算法的执行时 间增加速度高于Gibbs抽样算法． 4 结 论 为了解决非对称链路性能推断问题，本文提出 了全源NT的测量模式，并给出采用EM算法和MC． MC算法的链路丢包率推断方法．仿真结果不仅验 证了该技术的有效性，而且通过对比，可以发现 gibbs抽样方法比EM算法的推断误差更小；而EM 算法在网络规模不大于30个源节点时推断速度更 快一些．本文的研究扩展了单源断层扫描技术推断 链路的能力和适用范围． 参考文献： [1]COATES A，HEROIII A 0，NOWAK R，et a1．Internet tomo． graphy[J]．IEEE Signal Processing Magazine，2002，19(3)： 7．65． [2]CASTRO R，COATES M，LIANG G，et a1．Internet tomography：recent developments[J]．Statistical Science，2004， 52(3)：499-517。 [3]COATES M，RABBAT M，NOWAK R．Merging logical to_ pologies using end—to-end measurements[C]／／ACM SIC,- COMM Conference on Internet Measurement．Miami，USA． 2003：192-203． [4]RABBAT M，COATES M，NOWAK R．Multiple source internet tomography[J]．IEEE Journal on Selected Areas in Communications，2006，24(12)：2221-2234．． [5]BESTAVROS，BYERS J，HARFOUSH K．Inference and labeling of metric-induced network topologies[J]．IEEE Transactions on Parallel and Distributed Systems，2005，16 (11)：1053-1065． [6]COATES M，NOWAK R．Unieast network tomography using EM algorithms[R]．Houston：Rice University，．2000． [7]ZHU Weiping．Using Bayesian network on network tomography[J]．Computer Communications，2003，6(2)：155- 163． [8]GUO Dong，WANG Xiaodong．Bayesian inference of net— work loss and delay characteristics with applications to TCP performance prediction[J]．IEEE Transactions on Signal Processing，2003 51(8)：2205-2218． [9]ARYA V，DUFFIELD N，VEITCH D．Temporal delay tomography[C]／／IEEE Infocom 2008．Phoenix，USA，2008： 276．280． [10]LAWRENCE E，MICHAILIDIS G，NAIR V．Network de— lay tomography using flexicast experiments[J]．Journal of Royal Statistical Society Series B，2006，68(5)：785-813． [11]MENG F S，HERO III A 0．Unicast based inference of network link delay distributions with finite mixture models[J]．IEEE Transactions on Signal Processing， 2003，51(8)：2219-2228． [12]LIANG G，YU B．Maximum pseudo likelihood estimation in network tomography[J]．IEEE Transactions on Signal Processing，2003，51(8)：2043-2053． 【责任编辑：陈峰] 万方数据