题目：IPv6骨干网络中自治系统关系识别算法的研究与实现

由于自治系统(Autonomous System，简称AS)可以自主配置路由输入输出策略，所以仅仅研究AS级的网络拓扑不能正确描述互联网的特征。近几年来，对互联网中AS间商业关系的研究已经成为互联网特征研究领域中的热门之一。本文在分析原有AS关系识别算法不足的基础上，提出了一种基于AS层次信息的AS关系识别算法。首先，本文研究了AS的类型和层次划分算法。由于AS数目日益增加数据规模不断增大，对AS类型的研究需要结合有效的数据分类方法。因此，本文引入了数据挖掘分析技术，在AS分类问题上首次提出了基于AdaBoost算法的AS分类方法。实验结果表明，该分类算法取得了较高的准确率（90.3%），并成功对IPv6网络中94.5%的AS进行了类型划分，同时该算法适用于IPv4网络。其次，本文对AS关系识别算法进行了研究。本文发现原有的算法在IPv6网络上的推断结果与IPv4网络上得到的结果有比较大的差异。经分析，这是由于目前提出的AS关系识别算法普遍利用AS连接度的差异去识别AS间的关系，但基于AS连接度的关系识别算法不能有效解决反常度问题，并且在复杂的网络连接情况中，表现出不稳定的性能。由于AS类型由其运营者决定，受网络拓扑变化影响较少，因此本文利用AS类型信息分析AS间的关系，以提高AS关系识别算法在不同网络实例应用中的稳定性。通过对比AS间的层次差异，本文首先识别出部分AS关系，然后利用基于MAX2SAT的AS关系识别算法对其余的AS关系进行求解，并针对目前基于MAX2SAT的关系识别算法中单字母子句和双字母子句权重赋值形式不一致的问题，提出了基于概率的权重赋值法来解决该问题并给出了相应的证明。实验结果表明，基于概率的权重赋值法使得AS关系识别算法同时适用于部分AS关系已知的情况。最后，本文设计并实现了AS分类算法和基于AS层次信息的AS关系识别算法，并实现了算法结果的可视化展示。对AS关系识别算法的性能，本文从准确性和稳定性两方面给出了较全面的验证方法。实验证明，基于AS层次信息的AS关系识别算法在不同网络实例应用中取得了比原有AS关系识别算法更高的准确率和更好的稳定性。