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

摘要：

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

关键词：域间路由系统、自治系统、健壮性、k容错、拓扑

所属期刊栏目：42

分类号：TP391.41(计算技术、计算机技术)

资助基金：国家自然科学基金;国家高技术研究发展计划（863计划）

在线出版日期：2012-10-29（万方平台首次上网日期，不代表论文的发表时间）

页码：395-409