电子科技大学硕士学位论文

Ｃａｓｔｒｏ［８】等人在单播网络测量方面提出很大改进，他们提出了一种利用共享链路队列延迟的Ｓａｎｄｗｉｃｈ探测方法，Ｓａｎｄｗｉｃｈ包由中间的一个大包和两个小包组成，大包和小包的目的节点不同。第二个小包在他们分开之前总是在队列中排在大包后面。这个链路测量等同于共享链路上的队列延迟。Ｃａｓｔｒｏ还提出ＡＬＴ算法

【９】（ＡｇｇｌｏｍｅｒａｔｉｖｅＴｒｅｅＡｌｇｏｒｉｔｈｍ）实现拓扑重构，将ＤＢＴ进行修改以适应测量值

ｄｅｎｓｉｔｙ在概率密度函数（ｐｒｏｂａｂｉｌｉｔｙｆｕｎｃｔｉｏｎ）上的分布。为使此方法不用

设定门限并适用于一般树结构，Ｃａｓｔｒｏ等人继而提出了反转跳马尔科夫链蒙特卡洛（ＲｅｖｅｒｓｉｂｌｅＪｕｍｐＭａｒｋｏｖＣｈａｉｎＭｏｎｔｅＣａｒｌｏ）算法进行最大似然估计的拓扑识别【８】，通过插入和删除节点建立一个侯选树，能够得到最大似然的候选树将作为估计的结果。

Ｍｅｎｇ—ＦｕＳｈｉｈ等人通过建立有限混合模型【１０】获得“Ｓａｎｄｗｉｃｈ’’包对均值的时延差分布，进而采用图聚类【ｌｌ】的方法获得网络拓扑结构。不同于以前的用启发式（ｈｅｕｒｉｓｔｉｃ）或蒙特卡罗方法（Ｍｏｎｔｅ—Ｃａｒｌｏ）先估计一个二叉树然后扩充为普通树，他们的方法直接估计一个普通树。方法的核心是把问题抽象成一个基于节点对相似度测量的叶节点分层聚类问题。中间的每个节点代表了一个特定的聚类团，这个聚类团里的叶节点有一个共同的祖先节点。并将在同一个类（ｃｌｕｓｔｅｒ）里的节点称为类中（ｉｎｔｒａ－ｃｌｕｓｔｅｒ），将不再同一个类的节点称为类间（ｉｎｔｅｒ—ｃｌｕｓｔｅｒ）。一对叶节点的相似度可以用和共享路径（从根节点到两个叶节点最近代共同的祖先节点的路径）相关联的单调函数表示。任何可以准确估计不同相似度度量的方法都可以用在这里。有三种不同的端到端的相似度度量方法：使用三明治包测量的队列延迟（ｑｕｅｕｉｎｇｄｅｌａｙ），使用背靠背包（ｐａｃｋｅｔｐａｉｒｓ）的延迟的方差（ｄｅｌａｙｖａｒｉａｎｃｅ）和使用背靠背的丢包率（１０ｓｓｒａｔｅ）。修改节点对相似模型引入每个节点对最近的祖先节点对先验分布（ｐｒｉｏｒｄｉｓｔｒｉｂｕｔｉｏｎ）。推出一个有限混合模型，当中每个混合成份对应单源树中的一个中间节点。对由中间节点和中间节点子节点分割的后代叶节点，混合模型中有最小均值的混合成份对应类间（ｉｎｔｅｒ—ｃｌｕｓｔｅｒ）的叶节点对。将这个成份叫做类间成份（ｉｎｔｅｒ—ｃｌｕｓｔｅｒｃｏｍｐｏｎｅｎｔ）。为了定义一个分类的相似度将每个类中的叶节点分为类间对（ｉｎｔｅｒ—ｃｌｕｓｔｅｒｐａｉｒｓ）和类中对（ｉｎｔｒａ－ｃｌｕｓｔｅｒｐａｉｒｓ）等组合。这个相似度表示为类间相似度和类中相似度的乘积。每个类中相似度符合有限混合模型，类间相似度由类间成份决定。

相对于传统的拓扑识别方法，网络拓扑识别的层析成像方法存在的主要问题４