互联网拓扑的连通性研究：模型与算法

"本研究论文探讨了互联网拓扑的连接性措施，特别是考虑了AS（自治系统）之间的经济关系如何影响拓扑结构。初始模型将互联网视为无向图，但实际应用中需要将其转化为有向图，以反映客户-供应商、点对点或兄弟关系。论文分析了四种不同的算法，用于从路由表数据中推断AS关系，并研究这些算法生成的有向图模型在连接性度量上的差异。作者通过计算最大顶点不相交的无谷路径数量和最小割点的大小，展示了这些问题在当前设置下的复杂性，并将其表述为整数规划问题。提出了精确算法，包括基于IP公式的分支定价算法和非LP基分支定界算法，以及基于问题IP公式的分支切割算法，以解决最小切割问题。实验证明，无向模型和有向模型之间的连接度量存在显著差异，强调了考虑经济关系的重要性。" 这篇研究论文深入研究了互联网拓扑结构的建模方法，尤其是在考虑AS之间的经济联系时的差异。最初，互联网拓扑被简化为无向图，每个顶点代表一个AS，边则表示AS间的物理连接。然而，由于路由策略的复杂性，研究者开始采用有向图模型，其中边的方向反映了AS间的经济关系，如客户-供应商关系或合作伙伴关系。这种有向图模型允许仅沿“无谷路径”进行流量传输，即符合路由规则的路径。 为了推断这些关系，文献中提出了四种不同的算法，这些算法依赖于公开的路由表数据。论文的重点在于比较这些算法生成的有向图在连接性方面的特性。作者通过计算两个关键指标来评估这些模型：一是AS间最大数量的不相交无谷路径，二是分割一对AS的最小切割大小。尽管这些问题在一般图论中可以高效解决，但在有向图模型中却变得非常复杂，被证明为NP-hard问题。 为了解决这些问题，研究者提出了基于整数规划的算法，包括分支定价法和非LP基分支定界法来寻找最大数量的不相交路径，以及分支切割法来确定最小切割。这些算法在实践中能够提供精确解，从而允许对模型进行详细分析。 实验结果显示，不考虑经济关系的无向模型与考虑经济关系的有向模型在连接性度量上存在显著差异。这一发现强调了在构建和理解互联网拓扑时，必须考虑AS间的经济关系，因为这直接影响到网络的连通性和性能。因此，该论文为互联网拓扑研究提供了新的视角，有助于改进网络设计和优化路由策略。