● 摘要
互联网拓扑对于网络管理以及更好地理解网络内部结构有着非常重要的作用。然而，由于网络的分布式构建和管理，使得获取精确的网络拓扑非常困难。目前，获取网络拓扑的方法主要是采用基于traceroute的主动探测技术：收集从少量源节点集合到大量目的节点集合之间的路由。然而，使用该方法得到的拓扑图并不完整，而且有可能在采样过程中引入偏差。 精确的路由模型可以使拓扑探测的模拟更加接近真实探测过程，有助于分析网络的传输能力和进行路由性能评估。简单的模拟策略可以采用节点之间最短路径来作为模拟路由。但是，真实路由并非静态的节点间最短路径，而是具有动态性、膨胀性以及多样性等特征。简单的策略会导致模拟过程存在一定的偏差。 本文以研究traceroute探测过程的偏向性以及采样得到的拓扑结构与真实的网络拓扑之间的差异为目标，通过大量实验从多个拓扑属性的角度，在多个数据集上进行分析。对于Internet拓扑采样偏差的问题，本文的主要成果为：（1）根据节点探测概率与节点的局部拓扑属性之间的关系来探究采样过程的偏向性。实验结果表明，traceroute探测方法倾向于采集度数大、介数高和聚类系数低的节点。（2）由于采样过程的偏向性，导致网络核心被采集得更加完全，网络边缘的节点和边被探测到概率较小。（3）通过增加探测源节点，可以有效地降低大多数采样图拓扑属性的偏差。（4）真实的网络拓扑将更加稠密，网络的核数被低估了，真实网络应具有更高的连通性以及鲁棒性。（5）在实际的拓扑探测过程中，可以将探测源节点部署到高聚类系数、低核数以及低介数的网络边缘节点上，从而提高采样精确性。 另外，本文提出了一种基于AS路径信息的层次路由模型。该模型根据真实网络中的路由策略，分别从域间以及域内对路由进行模拟。相比于最短路径模型，该方法所产生的节点之间的路由具有多样性以及非对称的特性。同时，在模拟过程中，考虑了负载均衡等相关因素。实验评估的结果表明，与其他路由模型相比，本文提出的模型具有更高的路径相似度，与真实路由较接近的平均路径长度和跳数分布。通过该方法进行模拟采样得到的拓扑子图在许多拓扑属性上与合并真实路由生成的子图较接近。