{fkshen, pchang, wzhang}@ecnu.edu.cn 基于层析成像技术的网络拓扑判定研究 Presented by: 沈富可 合作者:常潘，张巍 网络中心 华东师范大学 {fkshen, pchang, wzhang}@ecnu.edu.cn

Agenda 层析成像技术简介 网络拓扑探测技术 网络拓扑推断 系统聚类树算法及实验 总结

大型异构网络拓扑测量的困难 已有的网络拓扑测量工具，如traceroute等，主 要依赖于所有的中间路由器在测量期间提供准确 的信息。 只有这些中间网络设备支持ICMP，并能够向测量 工具提供所需的信息时，才能够进行网络拓扑的 判别。 由于安全的原因，很多设备ICMP是关掉的。 其他原因，管理人员不配合（不希望别人知道拓 扑结构）。

层析成像技术简介 网络层析成像（Network Tomography）技术也称为推理性的网络监视技术，基于对大规模网络中有限个节点的传输测量，使用统计学的原理来估算或推断网络的性能参数。 只在网络边缘观察，不需要中间节点及管理人员 的支持。

Tomography •Computer assisted tomography (CAT scanning) •Positron emission tomography (PET scanning) •Single photon emission tomography (SPECT scanning)

Network Tomography The term network tomography was first used by Vardi(1996) to capture the similarities between origin destination (OD) matrix estimation through link counts and medical tomography: in network inference, it is common that one does not observe quantities of interest but their aggregations instead and this goes beyond OD estimation. Vardi(1996) also devised the linear tomography model for OD traffic estimation which is shown later to approximate other network tomography problems (cf. Coates, Nowak, Hero and Yu, 2002).

Why Network Tomography? Network monitoring and management need Link packet loss probability Link delay Origin-Destination (OD) traffic matrix Topology/connectivity discovery Intrusion detection and prevention ... They are not easily measured directly, but easily measurable indirectly. Network engineering and resource allocation include Routing optimization (OD information needed) Quality of service guarantee …

Multicast Link Delay Estimation 探包从组播树的根节点发出，在节点1处进行复制并向下游发送，在接收节点2、3处观察时延(Y)。通过推演得到内部链路时延 (X)。 Y=AX, where 1's in the i throw of A specify the links that the ith component Y travels through.

网络层析成像 Yt =AXt +ε, 此处Yt是在时间t对网络中不同的节点所测量的关于包计数或端到端延迟等的向量；A是一个路由矩阵；ε是噪音向量；Xt是时间相关的包参数，如传输延迟、一个链路上包传输率的对数或者是随机的源/目的传输向量等

网络层析成像 在基于层析成像技术对拓扑进行估算的方法中，只在网络边缘进行测量，不需要网络内部设备间的合作。网络的物理拓扑可以用直观的图形来表示，每一个节点表示一个物理设备（如一个路由器），边线表示对应设备之间的连接。依靠网络传输和排队的一些特性，可以判别得到的网络的逻辑拓扑。

网络层析成像 物理与逻辑拓扑间的差别，暗色的节点为没有产生传输分支的网络设备，不出现在逻辑拓扑中 (a)物理拓扑 (b)对应的逻辑拓扑

网络拓扑探测技术 三明治探测的测量方案 由三个包组成，源节点发送“一大两小”三个数据报探针。较大的探测包发给节点2，两个小的探测包发给节点3。由于小探测包p2排列在大的包后面（大包的尺寸由每个链路的带宽限制决定），两个小的探测包间的初始间隔d将随着在从节点0到1这段共享路径传送而增加。增加的延迟是由第二个小的包在大的包后面在所共享路径上的链路中排队而导致的。在理想的网络环境中[6]，共享路径上的每个链路产生不同的平均延迟是和其带宽相关的，而测量值是随着共享路径增长而增大的。一般，为准确起见，在测量Δd的时候往往取多次测试的平均值。

网络拓扑推断 R是测试中接收节点的集合，xij为对节点i,j(i,j∈ R, i≠j)多次不同延迟的采样平均 xij ～N(γij,σij2) R是测试中接收节点的集合，xij为对节点i,j(i,j∈ R, i≠j)多次不同延迟的采样平均 交叉传输在测量时间段是稳定的，且初始的两个小包的间隔d足够大，以保证大些的包和第二个小包在任何时候都是排队在第一个小包的后面。发出探针保持足够的间隔，这样可假定每次测量是相互独立的。假设测量是统计上独立的而且测量值是有限的，因此经验平均趋向于正态分布。

如何判定逻辑拓扑 我们可以对树中每个内部的节点指定一度量值dk。考虑度量有单调性：一个内部节点有一个比其子孙节点小的度量值（如在图1中d5>d2)）。由于拓扑未知，我们不能直接得出度量值，但可以间接估算出它们。用a(i,j)表示一对接收者i,j∈R的共同祖先，如a(4,9)=2,定义dij≡da(i,j)。值dij认为是从根到节点i和j路径中共同部分的特性。 这个模型中有一个强制的对称性：dij=dji。根据成对的度量值和单调特性，我们完全可以判别出逻辑拓扑 。

如何判定逻辑拓扑（续） 由于在网络中探测往往会受到网络流量的干扰，所以在实际测量中不能够得到准确的成对度量值。如果采用一个统计模型可以将未知的度量值和测量结果关联起来，就可以把拓扑判定问题作为一个极大似然估计（Maximum Likelihood Estimation）的过程。

极大似然估计 对于一个未知的树Ｔ，有一个接收者的集合R，Xij是参数为γij的随机变量，其中i,j ∈ R，i≠j，令γ={γij}。p(x|γ)表示这些随机变量的联合密度函数。假设x ≡ {xij:i,j∈R,i≠j}是随机变量Xij的一个样本，即探测获得的成对测量结果。 Ｆ表示以R为叶节点的所有树的集合，g(T)是对树Ｔ满足单调性的所有γ的集合，sup表示p(x|γ)在γ∈g(Ｔ)下的条件极大似然估计。则上式的结果为极大似然树（Maximum Likelihood Tree, MLT）。 计算开销非常大

系统聚类树算法 考虑一个有N个叶节点的树，则最小的森林大小是N!/2。 结合上面对网络拓扑所作测量得到的结果xij，其对节点成对测量的结果反映的就是两两节点间的相似程度的统计值，令γ为xij的算术平均值Dij。为了进行逻辑拓扑的判断，我们使用了系统聚类树（System Clustering Tree, SCT）算法，可以作为MLT的近似。

系统聚类树算法 SCT算法中先将n个节点各自看成一类，共有n类。然后规定节点之间的距离。开始时，由于n个节点各自成一类，在这里选择最大距离作为分类距离，将满足分类距离的一对合并成一个新类，计算新类与其他类的距离，再将距离满足分类距离的类进行合并，直至满足聚类的要求（只剩下一个节点）为止。

系统聚类树算法

SCT实验 在实验中使用模拟数据采用SCT算法进行逻辑拓扑推断。对左图所示的拓扑，算法得出的逻辑拓扑如右图（注意：得到的节点编号与左图中的编号不同）所示： 由图中可以看出使用SCT算法得到的逻辑拓扑，它非常接近于左图中所示的物理拓扑。

Conclusions 在一个大规模通讯网络中，运用端到端的测量对网络拓扑进行快速推断的问题，可以得到由源端点到各个接收节点之间的拓扑树。通过多个源拓扑树的合并可以得到一个完整的网络拓扑结构。这种方法有望取代Traceroute等工具。 文中给出的拓朴判定算法从实验结果来看，所推断出的逻辑拓扑是非常接近真实网络拓扑的。但在实际测量中，网络的规模会比实验环境大得多，测量结果往往也会受到网络噪音及流量的干扰，如何对测量数据进行处理（在测量的次数有限的情况下γ为xij的算术平均值Dij的这一假设是很难成立的，重尾分布及Pareto分布？）是在以后工作中需要进一步研究的。

谢谢！