基于BGP路由系统自组织特性的域间流量出口选择优化技术

摘要

当前Internet技术不断发展,其规模也变得日益庞大,随着多种应用的出现,对Internet流量的需求也变得越来越多,域间流量工程也随之出现,其主要目的在于优化各个AS之间的流量,以提高网络的服务质量,并且随着多宿主的出现,域间流量工程成为当前的一个研究热点。当前的域间流量工程主要包括基于出口和入口的流量优化问题,其各方面的研究也仅仅处于初始阶段,因此对域间流量工程的研究有很重要的意义。本文针对域间流量工程的基本问题以及关键技术主要进行了以下研究:1.提出了一种基于域间路由出口选择优化技术。通过使用随机递归搜索算法(RRS)查找使得AS出口链路上所有链路利用率之和最小。根据查找的结果,通过调节BGP报文中LOCAL_PREF属性,为流量选择适当的出口。仿真实验表明,使用本文提出的出口优化选择方法,能够使各条链路的利用率在同一水平上,由调整之前的最高链路利用率与最低利用率相差84％缩小到10%以内,有效地调节了域间流量的分布。2.域间路由系统自组织特性及HOT理论研究。通过对域间路由系统所表现出来的自组织特性进行研究,得到域间路由系统在AS级别拓扑结构所表现出来的度分布的幂率特性和小世界特性。并研究了幂率特性产生的根本原因:增长和择优。并且从系统优化的角度阐述了幂率特性产生的另一个原因—HOT(HighlyOptimizedTolerance/tradeoff)理论。HOT理论以系统设计的视角说明当系统朝最优化方向发展后,最终将会得到具有特性的输出。对于域间路由系统本身所表现出来的幂率特性具有很好的指导意义。3.根据网络中备用资源R,对当前网络中各个节点上设置相同的承载系数α的问题进行了改进,提出了两种优化方法:1)基于AHP(层次分析法)的α承载系数设置方案,根据通过节点的最短路径数,节点的度以及通过该节点邻居节点的所有最短路径条数计算各个节点的承载系数α,使得每个节点根据其重要程度获得备用资源的分配,从而保证资源的有效利用。2)基于HOT理论的α承载系数设置方案,根据HOT理论,系统朝最优目标演化后,最终将会得到具有幂率特性的输出。本文从逆向思考,以幂率特性的输入,研究系统的整体性能的变化情况。通过设置节点承载系数按照节点的重要程度成幂率分布,研究网络性能的变化情况。仿真分析表明,以上两种方法均能在一定程度上提高网络的效率,具有一定的实用性。

目录

摘要

ABSTRACT

第一章 绪论

1.1 研究意义

1.2 国内外研究现状

1.3 本论文研究内容和创新

1.4 本文的组织结构

第二章 BGP 协议概述

2.1 BGP 协议介绍

2.2 BGP 报文类型

2.3 BGP 的路由属性

2.4 BGP 路由机制

2.5 BGP 有限状态机

2.6 本章小结

第三章 基于出口选择优化的域间流量调节技术

3.1 流量工程定义

3.2 域间流量工程

3.3 基于BGP 出口优化选择的路由算法

3.3.1 问题描述及分析

3.3.2 优化的出口流量选择方法

3.3.3 流量出口选择优化仿真

3.4 本章小结

第四章 域间路由系统的自组织特性及HOT 理论研究

4.1 幂率特性

4.2 小世界特性

4.3 AS 之间的商业关系

4.4 HOT 理论

4.5 简单的森林防火模型

4.6 本章小结

第五章 基于HOT 理论的域间流量最大化方案及仿真分析

5.1 问题描述

5.2 简单的网络承载模型

5.3 原有的节点承载能力的分配方法

5.4 优化的分配方式一

5.4.1 AHP 法简介

5.4.2 AHP 分析法基本步骤

5.5 节点承载能力分配方法

5.5.1 资源分配方法

5.5.2 仿真分析

5.6 优化的分配方式二

5.6.1 资源分配方法

5.6.2 仿真分析

5.7 本章小结

第六章 总结

致谢

参考文献