Internet AS层网络中的社团结构和地理特征

论文摘要

Internet是一个巨大、复杂、开放的网络集合,宏观上它由成千上万的自治系统（Autonomy System,简称AS）组成,这些自治系统通过专线或者公共网络接入点彼此互连,其间的路由通告和路由传递由域间路由协议边界网关协议（BGP）决定。BGP协议允许每个自治系统使用自己的策略宣告和接收路由,选择最佳路由。自治系统拓扑表现不同自治系统间的连接关系和输入输出策略,尤其是商业化以来,管理域之间商业合同关系己经成为决定路由策略的最重要因素。由此可见,AS之间的关系是Internet拓扑结构的重要方面,从中可以考察不同管理部门网络间的连接关系和运营情况,为优化网络结构和网络接入提供依据;同时AS的属性信息是重要的网络资源,掌握它对国家的网络管理与网络维护有深远的意义。本文首先介绍了Internet AS层的基本概念,以及研究自治系统之间关系的重要意义,我们采用美国Oregon大学caida项目利用skitter工具在互联网上发布的AS连接数据,在linux系统下进行预处理,然后利用复杂网络中的社区发现算法-基于Laplace矩阵的传统谱平分法对Internet AS层网络进行了社团划分;又通过搜集网上的AS属性信息设计了一个AS属性信息SQL数据库,并在此基础上利用PowerBuilder的OLE技术编程实现了AS属性信息查询处理系统,通过本系统对划分好的社团文件进行处理得到每个社区的AS的地理属性信息,最后通过origin画出经纬度坐标图对AS社团的地理特征进行了研究说明。

论文目录

• 摘要
• Abstract
• 1 绪论
• 1.1 课题背景
• 1.2 研究的目的和意义
• 1.3 本文的内容和结构
• 2 自治系统及其研究意义和方法
• 2.1 自治系统
• 2.2 AS号的申请、分配和使用情况
• 2.2.1 AS号的注册
• 2.2.2 AS号的分配和使用情况
• 2.3 自治系统关系研究的意义
• 2.4 自治系统关系研究的方法
• 2.4.1 whois数据库
• 2.4.2 主动探测方式
• 2.4.3 利用 BGP路由表数据
• 2.4.4 几种数据采集方式的比较
• 3 复杂网络中社区发现算法
• 3.1 算法概述
• 3.2 Kernighan-Lin算法
• 3.3 谱平分法
• 3.3.1 基于 Laplace矩阵的传统谱平分法
• 3.3.2 其它谱平分法
• 3.4 分裂方法
• 3.4.1 GN算法
• 3.4.2 在 GN算法上改进的一些分裂算法
• 3.5 凝聚算法
• 3.5.1 Newman快速算法
• 3.5.2 利用堆结构的模块性贪婪算法
• 3.5.3 结合谱分析的凝聚算法
• 3.6 派系过滤算法
• 3.6.1 k-派系社团的定义
• 3.6.2 寻找网络中的派系
• 3.6.3 利用派系寻找k-派系社团
• 3.6.4 网络中k-派系社团的统计特性
• 3.7 网络分解评价
• 4 Internet AS层网络社区发现
• 4.1 数据采集
• 4.2 数据预处理
• 4.2.1 数据预处理流程
• 4.2.2 数据预处理结果
• 4.3 基于 laplace矩阵之谱分析的社区发现算法实现
• 4.3.1 谱平分法的基本思想
• 4.3.2 谱平分法的算法流程
• 4.4 算法编程实现
• 4.4.1 Laplace矩阵初始化函数
• 4.4.2 Laplace矩阵处理函数
• 4.4.3 社区划分函数
• 4.5 算法实施
• 5 AS属性信息查询处理系统设计
• 5.1 数据采集
• 5.2 AS属性信息数据库设计
• 5.2.1 数据库设计过程
• 5.2.2 概念结构设计
• 5.2.3 逻辑结构设计
• 5.2.4 物理实现
• 5.3 AS属性信息查询处理系统的编程实现
• 5.3.1 数据库的连接
• 5.3.2 单个AS信息查询模块设计
• 5.3.3 AS属性信息批量查询模块设计
• 6 结果处理及结论
• 6.1 社区发现结果处理
• 6.2 社区的地理特征
• 6.3 展望
• 致谢
• 参考文献
• 附录