《网络层面照相用图建模中文版2》由会员分享，可在线阅读，更多相关《网络层面照相用图建模中文版2（10页珍藏版）》请在金锄头文库上搜索。
1、网络层面照相用图建模摘要：对于我们理解网络的动态特征，链路级的性能数据，如损失率和各个环节的延迟，是至关重要的。实现这一目标的方法之一是凭借终端到终端的测量去推断性能特点。由于其效率和准确性的优势，我们使用图形模型，代替了使用传统的统计数据做推论的方法。以网络模拟器2（NS2）为基础进行模拟，由期望最大化推断（EM）算法收集数据，其结果几乎与先前提出的最大似然估计所产生的结果相同。朗读Zhiyo: Zh sh zh gun zhngyo de lin l j d xngnng shj, r snsh l h ynch gge hunji, wi wmen de yg wnglu de dngt
2、i txng de rnshi. Shxin zh y mbio d fngf zh y sh jy zhngdun do zhngdun d cling xngnng tdin de yunyn. r bsh shyng chuntng de tngj shj zu tuln, wmen shyng de txng mxng, du xiol h zhnqu xng de yush. Zi wnglu mn q 2(NS2 de) wi jch jnxng mn h shj shuj sh yu qwng zud hu tudun (EM) sunf, q jigu jh sh xingtn
3、g de zud sh rn gj de jiny yqin chnshng de jigu.字典 - 查看字典详细内容关键词：网络断层扫描，图形模型，网络的性能。1. 引言为了成功地设计，控制和管理网络，我们必须对于网络的特征有更好的了解，特别是对于数据链路层1的了解。级别链接的特征，如丢包率和平均延迟，将有助于我们了解从各种在传输介质的应用中累计流量所带来的影响。这促使一些团体调查研究方法，以此在终端至终端网络测量234 56的基础上，即所谓的网络断层的问题，来推断出内部网络行为。人们常用的一个来解决此问题的办法是，在一个或几个正在进行的流量交通（后来被称作背景流量）节点上增加探测数据包，
4、此探测包特定于数个接收器。这些接收器上的探测数据包的接收或者丢失表明相应链接上的流量交通条件。这种方法依赖于统计推断得到链路级的特点。在本文中，我们建议使用图形模型进行推理。最近，卡塞雷斯等人成功地利用该方法通过终端到终端的测量6，7，8获得数据丢失信息。他们建立了一棵组播树，通过目标网络传播，探测数据包基于定期或指数的基础从树的根部组播至叶节点。连接至叶节点的接收器纪录下到达的探测数据和未到达的探测数据，并为进一步的分析提供数据。在分析过程中，这些数据放在一起，估算各个环节的损失率。他们推理中使用的方法基于传统的最大似然估计（MLE），即使用探测数据包丢失的部分来估计背景流量交通的损失概率。
5、无论是对于组播主干网的模拟还是对于其实验研究都表明了该方法的可行性和潜力。最近，由于某些网络可能无法使用组播，Harfoush等人建议使用单播来发现链路级性能 9。他们使用分组配对技术在两个接收器之间建立相关性。两个及时被分离的数据包被发送到两个接收器（这两个接收器从源头共享路径的一部分），并在这两个接收器之间建立相关性，然后在观察这两个接收器的基础上，他们可以使用基于组播研制的技术来识别共享及不共享路径上的损失率。他们的模拟证实了其方法的有效性。同样，科茨和诺瓦克也采用了分组配对技术来推测链路级的特点。他们用期望最大化推断算法（EM算法）来推测链接的数据包之间的相关性，以及相关链接的损耗特性
6、10。我们使用图形模型（GM）推断链路级行为,而不是使用传统的最大似然估计（MLE）来推测链路级的损失率。在 11中发现的模型可以用来作为一个链接的先验概率，然后被用来从观察中推断后验概率。每次当一个新的观察变得可行，这个过程便重复一次，这使系统适应流量的变化。这个过程确保了所有先前到目前的观测资料都能在目前观测到的资料中得到总结。朗读r bsh shyng chuntng de zud sh rn gj lin l j de snsh l, wmen shyng txng mxng (GM) jing tudun ch lin l j xngwi. 11 Fxin gi mxng ky yn
7、g li zuwi yg linji, rnhu yng cng gunch tudun xin yn gil hu yn gil. Zhge guchng chngf mi c dng yg xn de gunch bin de kyng, zh sh xtng shyng liling de binhu. Zhge guchng qubo le suyu qin cng mqin de gunc zlio, zi mqin gunc do de zlio zhng zn字典 - 查看字典详细内容我们进行了初步研究，使用网络模拟器2（NS2）12来模拟一个包括8个节点和7个链接，并把8个节点
8、连接成一个树状结构的网络。一个包含传输控制协议（TCP）和用户数据包协议（UDP）流量的组合被添加到不同的节点作为背景流量。定期从根部到4个叶节点发送探测数据包。通过收集在4个叶节点得到的探测信息，并使用图形模式（GM）论及损失率来推断7个链接的链路级特性，我们发现推断的结果表明了背景流量的损失率。此外，通过比较我们得出的结果与使用在678中提出的最大似然估计（MLE）获得的结果，并在消除最大似然估计（MLE）在一些链接上产生的负损失率异常情况后，发现两者几乎是相同的。这反映了图形模式（GM）的可行性和准确性。本文的其余部分组织如下。在第三部分里，我们提供了图形模式（GM）的根本原理并将其应用
9、来发现链路级的特点。然后，我们在第二部分提出我们的研究，包括流量交通涵盖的细节，并将不完整的观测研究得到的结果与模拟器收集到的实际数据进行了比较。最后一节是专门的结束语。2. 图形模型和参数学习一个图形模式（GM）是由一个三元元组（X, S, P）限定的，其中X=X1, X2， Xn 是一组变量，S为图形模式（GM）结构，它限定X变量之间的偶然影响，这些影响力是由条件概率P量化的。这些影响由一系列的条件概率p (Xi|Pai)衡量，对于每一个子变量Xi，配置一个母变量，以Pai表示。结构S描述变量之间的独立性和依赖性。给定一个X的样本中，x=x1，x2，. xn ，联合概率可以通过公式：得到，
10、其中ij表示Pai在X中的状态。如果一个节点，比如说i，没有母节点，那么p(Xi= xi|Pai=ij)=p(Xi=xi)。公式（1）表明：无论图形模式（GM）多么复杂，特定所有节点的状态，联合概率是由所有链接的条件概率产物所代表的，这个产物表明了母节点对子节点的影响。这种分解消除了自变量之间的相互影响，并大大降低了联合概率计算的复杂性。事实上，图形模式（GM）之间有个1对1的映射，以此来推断链路层的特点，并有用来发送探测数据包（NPP）的网络。这两个网络使用相同的结构，图形模式（GM）中的每个变量对应NPP中的一个链接，图形模式（GM）弧的条件概率对应于链路级特性，如NPP中的损失概率。此外
11、，每个发送到叶节点的探测器可看作一项试验，这项试验的结果是对在每个节点d=d1,d2,dn发生的相应事件的配置。如果对于一项试验，每个节点只有两种可能出现的状态，1和0，其中1表示该节点收到探头，0表示该节点没有收到探头。对于具有n个节点的系统来说，一个完整的样本空间有2 n 种可能的配置。如果考虑到相应的无回路有向图(DAG)的结构描述，可能配置的数目大大小于2n 。例如，假定如图2所示的图形模式（GM）有4个节点。当一个探头从X0至X2至X3组播时，只有5种符合条件的配置，分别是1,0,0,0，（1,1,0,0），1,1,1,0 ，1,1,0,1和1,1,1,1，而不是2 4= 16种。据
12、统计，数据显示的内容可以由下面的对数似然表示：其中D表示一组观察，D = d1, d2,dm，每一个参数表示一项试验;表示一组参数，（1，.，n），每一个参数为一个链接，它确定了这个链接相应的条件概率。可以根据配置将D进一步分组，组中的每一个成员都具有相同的配置。设n (d)是一个函数，它用配置d算出组的大小。所有可能的配置形成一个配置空间，空间由c表示。我们的目标是根据所给出的观察，找到可以使L（）最大化的，即：朗读Qzhng D biosh y z gunch, = D1 h D2,., Tngniobng, yg shnpn zh y?Th biosh y z cnsh,(th1,.,T
13、hn), wi yg linji, t qudng le xingyng de tiojin gil 1 Wi linji. D ky jnyb fnchng ling z, gnj pizh h mi yg z de chngyun jyu xingtng de pizh. Sh, dn (s) sh yg hnsh, t fnhu pizh y z dxio s Suyu knng de pizh xngchng yg pizh kngjin, kngjin yu c zhbn. Wmen de mbio sh gnj su gi ch de yjin, ky zhodo th zud h
14、u de L(th), j:字典 - 查看字典详细内容然而，在实践中有许多情况阻止我们收集到完整的数据集，如我们正在研究的这个问题，不能得到内部节点的状态，至少不能直接得到。在一些情况下，我们可以从不完全（部分）数据中很容易发现内部节点的状态。例如，如果一个接收器接收到一个探头，我们可以得出这样的结论：它的源节点一定接收这个探头。不过，推断出同步损失的原因并不容易，是指这样的一种情况：一个组播探头完全失去与连接到子树的所有接收器的联系，这个子树至少有两个子接收器。困难之处在于对同步损失原因的不确定，可能是在子树与其母体的链接处单独的损失，也可能是在一个切口的所有链接处的平行损失。这个切口可以将子树分为两个部分，其中一部分是另一部分的母体和先祖。 图1：可观察空间y vs. 隐藏空间x例如，图2显示了一个简单的子树，有四个节点（分别为X0-X3）和三个链接（l1-l3），其中l1,(l2,l3)是子树的两个切点。显然，从上述情况发现条件概率较之从完整的数据集发现更加困难，因为我们必须考虑所有可能导致相同观测结果的原因所带来的影响
