第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文件，首先将每条链路真实 的丢包率统计下来，作为真实的链路报文丢包率，用 万方数据