资源描述：
《以竞赛为载体培养创造型人才》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、中国AS级拓扑测量与分析基金资助:本文受国家自然科学基金(60203021),973国家重点基础研究发展计划(2007CB311100)的资助联系作者:张宇,E-mail:zhangyu@pact518.hit.edu.cn张宇1方滨兴1张宏莉11（哈尔滨工业大学计算机网络与信息安全技术研究中心,黑龙江哈尔滨,150001）摘要:为描绘中国AS(AutonomousSystems)级拓扑图景,本文运用综合集成的思想来考察不同拓扑数据之间在数据本身和统计特征上的差异.首先,采用基于BGP,基于traceroute和基于IRR的方法从不同数据源获取了
2、拓扑快照和十年间历史.其次,对快照进行基于集合运算的分组比较,并得到一幅较完整可信的图.接着,从生灭过程角度,分析三类增长机制,指出了‘灭’过程的缺失.然后,运用复杂网络特征化方法,比较三幅图的特征及显著性,发现平均度主导了多数差异,并指出有关Rich-Club现象的争议根源之一在于数据差异.最后,给出了特征演化的四点观察,包括相关模型中未能重演的平均度增长现象.关键词:拓扑测量;拓扑建模;拓扑演化;复杂网络;自治域;综合集成1．引言Internet宏观结构可被抽象为一幅以AS(AutonomousSystems,自治域)为点,域际互连关系为边的
3、图.AS级拓扑测量与分析作为一项互联网络基础研究,旨在寻找这幅包含Internet结构信息的图并探索其内在规律,从而预测网络结构与技术,政策,经济之间的互动.本文以展现中国网络结构的宏观图景为目标,探讨当前研究中存在三个关键问题:1)测量技术与数据源的多样性改善了完整性问题,但尚未解决,同时又增加了提高准确性的难度.相关问题包括:基于traceroute测量的失真[1],基于BGP(BorderGatewayProtocol)测量的时间窗选择[2,3],基于IRR(InternetRoutingRegistry)测量的可信验证[2,3],以及演化
4、拓扑的‘存活性’[4].目前所达成的一个共识是:AS级拓扑都只是“推测的”.2)测量数据的差异导致在拓扑特征化上的争议,这阻碍了复杂网络特征化框架的建立.例如,文献[5]指出,发现度分布幂律[6]时所用的AS图丢失了20%~50%的链接,而更完整拓扑的度分布并不严格服从幂律.最近,Colizza等[7]和Zhou[8]就AS级拓扑是否具有RC(Rich-Club)现象展开了争论,而此现象是Zhou等[9]提出的PFP(Positive-FeedbackPreference)模型的基础之一.3)尽管现有拓扑演化模型能够再生部分图论特征,但还无法重现
5、演化过程.多项工作[4,5,10,11]相继指出BA(Barabási-Albert)模型[12]与观测的历史有较大差异.一些改进模型,例如GLP(GeneralizedLinearPreference)模型[11]和PFP模型[9],虽然引入了新的增长机制,但与实际历史的匹配程度还有待考察.我们认为上述问题的症结在于两点:一是在研究内容上,对数据间差异认识不足.数据在横向上有不同来源的快照,纵向上有不同时期的历史;差异既存在于数据本身,也存在于统计特征;二是在研究方法上,以往工作中缺乏综合,大多是采用单一方法的测量,对单一度量的分析,或在单一快
6、照上对模型验证.为此,本文将采用复杂巨系统研究中的综合集成(meta-synthetic)方法论[13],其关键思想之一在于将各方面研究综合起来,在以往彼此孤立的工作之间建立联系.具体到本文是将各种测量数据和分析方法综合起来,通过寻找数据间差异来建立联系.首先,采用不同测量方法和数据源来收集拓扑快照与历史;然后,通过基于集合运算的分组比较来考察数据本身差异,通过观察历史上的生灭过程来验证增长机制;最后,运用复杂网络特征化方法分析统计特征及其显著性的差异与演化.2．测量2.1拓扑快照采用三种测量技术得到了19幅中国AS级拓扑快照,每幅图按“源-方法
7、”格式来命名,见表1.1)基于BGP方法从BGP路由表或更新消息的AS_path条目中提取数据.主要数据源是BGP路由采集器项目,包括:RouteViews,RIS和BGPView.BeyondBGP项目[3]收集上述项目数据,还收集IRR数据,但其中未包括APNIC,所以其中国部分是单纯基于BGP的.从三个采集器项目中各提取了一幅基于路由表的图和一幅基于更新消息的图.同时,收集BeyondBGP的一幅图,为与ZZZ-PTR比较,还提取了5个月后的.更新消息的采纳时间参照文献[2,3]为最近两个月.2)基于traceroute方法采用IP级测量发
8、现从监测点到目标的一组顺序相连路由器的接口IP地址,再通过BGP路由表中源AS—前缀对将IP地址映射到AS号.此方法主动发现数据包经过的
