因特网AS级拓扑的健壮性测度与健壮性演化

Robustness measurement and evolution for the Internet AS-level topology

以自治系统(autonomous system,AS)为基本组成单元的域间路由系统是因特网(Internet)的核心组成部分,研究Internet AS级拓扑的健壮性对于整个Internet的健壮性设计具有重要意义.2003年的北美停电事故与2006年、2010年的台湾地震表明,当今Internet的健壮性仍亟待增强.本文结合基本的拓扑理论与实际的路由策略约束,利用Internet AS级拓扑的层次特性,从"单个AS"和"全局拓扑"两个不同的层面研究AS级拓扑的健壮性测度与健壮性演化:1)提出了对单个AS的健壮性测度的方法;2)对全局AS级拓扑的健壮性测度提出了k容错模型---任意k个AS级的节点/链路故障不影响任何其他两个AS之间的连通性;3)基于健壮性测度方法和k容错模型,提出了健壮性演化的机制与方法.对当今Internet AS级拓扑的统计分析表明:1)25.8%的AS节点还不能承受1个AS级的链路故障,26.4%的AS节点还不能承受1个AS节点故障;2)将现有的AS级拓扑演化为k容错拓扑不仅能保证任意节点对之间可达性的k容错,在故障数超过k的情况下,k容错拓扑的健壮性也显著优于原拓扑.

The inter-domain routing system consisting of autonomous systems（AS） is the key infrastructure of the Internet.It is critical to study the robustness of the Internet AS topology for the design of the robustness of the whole Internet.The Northeast Blackout（2003） and the Taiwan earthquakes（December of 2006 and March of 2010） reveal that the robustness of today＇s Internet still needs to be improved.Taking into account both basic theory of network topology and practical compliance to routing policies,this paper investigates the robustness measurement and evolution of the Internet AS topology at two scales：1）we propose a method for measuring the robustness of ＂individual ASes＂ against AS link and node failures;2）we propose a k-fault tolerant model for measuring the robustness of ＂the global AS topology＂;3）based on the two measuring methods,we present mechanisms and methods for the robustness evolution at both of the scales.Studying on today＇s real AS topology,we find that：1）25.8% of all ASes bear even single AS link failures,and 26.4% of all ASes cannot are still vulnerable to single AS node failures;2）augmenting existing AS topology to k-fault tolerance cannot only guarantee the reachability of any node pairs under arbitrary k failures,but also providing significantly better robustness under cases of more than k failures.