识别和验证ipv6网络的自治系统关系 - ipv6 backbone network .doc

识别和验证IPv6网络的自治系统关系 廖彬彬，许可 (北京航空航天大学 计算机学院,北京市 ) 摘 要：关 键 词：中图分类号：TP30文献标识码：A 文章编号： On Inferring and Validating Autonomous System Relationships In IPv6 Network Liao Binbin, Xu Ke (School of Computer Science and Engineering, Beihang University, Beijing 100191) Abstract: This paper researches autonomous system relationships in IPv6 network. It classifies AS into five layers based on text classification and introduces layered information into inferring AS relationships. Some algorithms based on MAX2SAT have been used to infer AS relationships, but their forms of 1-link clauses assignment and 2-link clauses assignment are not consistent. To solve this problem, this paper puts forward a new way to give assignment to both 1-link clauses and 2-link clauses and analyzes AS relationships in IPv6 network. 1515 pairs of relationships between 937 AS have been inferred and as much as 93.86% of inferences are confirmed by AS route policies promulgated by Internet Routing Registries. Key words: autonomous system relationships; hierarchy; IPv6 引言 在众多的设备提供商和运营商的努力下，IPv6协议已经从实验室走向了应用阶段。已有50多个国家和地区加入有关IPv6的研究。目前，全球IPv6网络中的自治系统（Autonomous System，简称AS）数目（截止至2008年3月21日）已达937个，并且正以迅猛的势头增加。所以本文对IPv6自治系统间的商业关系进行了研究和分析，以帮助我们更全面理解Internet的网络结构，评估 AS 关系是如何影响互联网架构的演化以及如何构建整个互联网增长的经济模型，了解不同部门网络间的连接关系和运营情况，为优化网络结构和网络接入提供依据。 由于因特网具有分层的网络结构，越靠近网络核心层的AS越可能成为其他靠近网络边缘的AS的服务提供商。基于分层的思想，本文首先利用文本分类方法把AS分为五个层次，然后把AS分层信息引入到X. Dimitropoulos等人提出的AS关系识别算法，同时针对他们的算法中单字母子句和双字母子句的权重赋值形式不一致的问题，提出了基于概率的权重赋值法以统一单字母子句和双字母子句的权值赋值形式。经对IPv6网络中937个AS间的商业关系进行推断和分析，本文识别了1489对Customer-to-Provider关系和26对Sibling-to-Sibling关系。经验证93.86%的推断结果与Internet Routing registries公布的AS路由策略所反映的AS关系一致。 1 AS间关系及其识别算法的研究 Internet网络由大量的AS构成。一个AS是拥有同一选路策略、在同一技术管理部门下运行的一组路由器。每个AS有一个由因特网登记处或者 ISP 分配的识别码（ASN）。 边界网关协议（BGP）允许每个AS设置自己的路由选择和发布策略。例如，AS可以通过设置自己的路由发布策略使其不为其服务提供商提供服务。 由于现实网络的复杂性和商业利益的需要，Internet网络中的AS对可能具有很多不同关系，但是它们中的绝大部分可以被划分为以下四类，AS根据其与邻居AS的关系来选择路由发布策略。 客户—服务商（Customer-to-Provider）和服务商—客户（Provider-to-Cust