文件名称：Internet 拓扑的连接措施-研究论文
文件大小：634KB
文件格式：PDF
更新时间：2024-06-29 18:59:31
论文研究
Internet 的拓扑结构最初被建模为无向图，其中顶点对应于所谓的自治系统 (AS)，边对应于 AS 对之间的物理链接。 然而，为了捕捉路由策略的影响，最近很明显需要根据 AS 之间现有的经济关系（客户-供应商、点对点或兄弟）对边进行分类。 这导致了一个有向图模型，其中流量只能沿着所谓的无谷路径发送。 文献中提出了四种不同的算法，用于使用来自路由表的公开可用数据来推断 AS 关系。 我们研究了这些算法生成的图模型的差异，重点是连接性度量。 为此，我们计算了 AS 之间顶点不相交的无谷路径的最大数量以及分隔一对 AS 的最小切口的大小。 尽管这些问题对于普通图可以在多项式时间内解决，但在我们的设置中它们是 NP-hard 的。 我们将这两个问题表述为整数程序，并提出了许多解决它们的精确算法。 对于寻找最大顶点不相交路径数的问题，我们讨论了两种算法； 第一个是基于 IP 公式的分支定价算法，第二个算法是非基于 LP 的分支定界算法。 对于寻找最小切割的问题，我们使用基于该问题的 IP 公式的分支切割算法。 使用这些算法，我们可以在合理的时间内获得这两个问题的精确解。 事实证明，在无向模型和有向模型之间的连接度量方面存在很大差距。 这一发现支持了我们的结论，即在构建 Internet 拓扑时需要考虑经济关系。