基于叶节点dfs序列的网络拓扑推断算法.pdf

年 月 计 算机 工程 与设计 ．
第 卷 第 期 ． ．
基于 叶节点 序 列的网络 拓扑推断算法
石佳 玉 ，吴辰文 ，孔德 弟，张耀方
兰州交通大学 电子与信息工程学院，甘肃 兰州
摘 要 ：为了提 高 网络拓扑结构 的推 断效 率 ，在 网络断层扫描技 术 的基 础上 ，提 出了基 于叶节点 深度 优先搜 索 序
列的 网络拓扑推 断算法 。使 用递 归二 分法找 出叶节点的 序列 ，运 用叶 节点 的 序 列推 断 网络拓扑 结构 。仿 真结果
表明 ，该方 法所需要 的成对探测 包的数 量低 于 目前 常用 的聚类 算法的 ，可 以更 准确 、更 快速 的推 断 出网络 的拓 扑结
构 ，进而更 大程度 的提 高了网络拓扑推 断的效率 。
关键词 ：网络 断层 扫描 ；深度优先搜 索；网络拓 扑推断 ；成对相 关性 ；单播
中图法分类号 ：． 文献标 识号 ： 文章编 号 ： —

， ，—，
，，，
： ，
．，
，
．
，，
．
： ；；； ；
引 言 显的减少了相关性条件的限制，降低了算法的复杂度。