（计算机科学与技术专业论文）基于邻居会话划分的多线程并行bgp协议.pdf

国防科技大学研究生院硕士学位论文 摘要 b g p 协议作为i n t e m e t 域间路由协议的标准，伴随i n t e m e t 规模的扩展和连接 密度的增加，对b g p 协议性能的要求也越来越高。对b g p 协议性能的优化研究一 直是提高路由速度的主要研究方向之一。多核处理器的出现和并行程序设计的发 展为解决这一问题提供了新的途径。 现在，串行程序设计对程序运行的速度，尤其是对于b g p 协议这种经过长期 发展的软件来说，能够带来的提升空间越来越小。并行随着多线程程序设计的优 势越来越明显，加上处理器技术的不断发展，设计开发多线程并行b g p 协议将成 为b g p 协议未来发展的必然选择。 本文对b g p 协议和并行程序设计技术进行分析和研究，讨论了现有路由协议 并行处理技术的研究现状，结合q u a g g ab g p 协议实现，提出了基于功能划分和基 于邻居会话划分两种b g p 协议多线程并行模型。经过对比所提出的两种模型的实 现难度和预期性能，选择了其中基于邻居会话划分的多线程并行b g p 模型，结合 q u a g g a - 0 9 9 9 代码，设计并实现，取名为p b g p 协议。对实现过程中遇到的解耦 合问题、存储空间和互斥锁的处理等问题进行了分析，提出了解决方法并实现。 利用现有实验环境对原q u a g g ab g p 协议和p b g p 协议的一致性和性能进行了测 试。根据测试结果将p b g p 协议与原q u a g g ab g p 协议的功能和性能进行比较，并 对测试结果进行分析，找出与预期性能之间的差异等问题和原因，为进一步研究 和优化做了准备。 主题词：b g p 协议，多线程，并行 第i 页 国防科技大学研究生院硕士学位论文 a b s t r a c t a st h es t a n d a r do ft h er o u t i n gp r o t o c o lb e t w e e nt h e1 1 1 t e m e ta u t o n o m o u ss y s t e m s ， t h ep e r f o r m a n c er e q u i r e m e n to ft h eb g pp r o t o c o lb e c o m e si n c r e a s i n g l yh i g h ，w i t ht h e i n t e m e tc o n t i n u i n gi t se x p a n s i o ni nr a n g ea n di t si n c r e a s eo fl i n k i n gd e n s i t y t h e e m e r g e n c eo fm u l t i - c o r ep r o c e s s o r sa n dt h ed e v e l o p m e n to fp a r a l l e lp r o g r a m m i n g p r o v i d ean e ww a y t os o l v et h i sp r o b l e m n o w ，t h es p e e do ft h es e r i a lp r o g r a m m i n g ，e s p e c i a l l yt h es o f t w a r ea f t e ra l o n g t e r md e v e l o p m e n tl i k eb g pp r o t o c o l ，w i l lb es l o wg r o w i n g t h ea d v a n t a g eo f p a r a l l e l m u l t i t h r e a d e dp r o g r a m m i n gw i l lb em o r ea n dm o r eo b v i o u s ，w i t ht h e d e v e l o p m e n t o fp r o c e s s o r t e c h n o l o g y ， m u l t i t h r e a d e db g pp r o t o c o lw i l lb et h e p r o t o c o l sd e v e l o p m e n t d e s i g n i n g a n d d e v e l o p m e n t o f p a r a l l e l i n e v i t a b l ec h o i c ef o rt h ef u t u r eo fb g p a f t e ra n a l y z i n gt h eb g pp r o t o c o la n dp a r a l l e lp r o g r a m m i n gt e c h n o l o g y ，s t u d y i n g t h ee x i s t i n gp r o c e s s i n gt e c h n o l o g yt ot h ep a r a l l e lr o u t i n gp r o t o c o la n dr e s e a r c ht h eo f q u a g g ab g pp r o t o c o l si m p l e m e n t a t i o n ，w ed e f i n et w op a r a l l e lm u l t i - t h r e a d e db g p m o d e lb a s e do np e e r sa n dp e r f o r m a n c e w ed e s i g na n dr e a l i z et h ep b g pp r o t o c o lo n t h eb a s i co ft h ep a r a l l e lm u l t i t h r e a d e db g pm o d e lb a s e do np e e r s ，a f t e rc o m p a r i n gt h e t w om o d e l s d i f f i c u l t yf o ri m p l e m e n t a t i o na n dt h ee x p e c t e dp e r f o r m a n c e ，c o n s i d e r i n g t h eq u a g g a - 0 9 9 9c o d e a n a l y z i n gt h ek e yp r o b l e m sw ef a c e di nt h ep r o c e s so ft h e i m p l e m e n t a t i o na n dg i v i n gt h es o l u t i o n sf o rt h e m w ee x p e r i m e n tq u a g g ab g pa n dt h e p - b g pp r o t o c o l sc o n s i s t e n c ya n dp e r f o r m a n c e a c c o r d i n gt ot h er e s u l t so ft h et e s t s ，w e c o m p a r e dt h ep - b g pp r o t o c o l sf u n c t i o n sa n dp e r f o r m a n c e 、衍t ht h eo r i g i n a lq u a g g a b g pp r o t o c 0 1 a n da n a l y z i n gt h er e a s o n so fd i f f e r e n c ew i t ht h ep e r f o r m a n c ew e e x p e c t e d ，t op r e p a r ef o rt h ef u r t h e ri m p r o v e m e n tt h er e s e a r c h k e yw o r d s ：b g pp r o t o c o l ，m u l t it h r e a d s ，p a r a l l e l 第i i 页 国防科技大学研究生院硕士学位论文 表目录 表5 1p b g p 协议中的锁使用4 5 表6 1多核服务器主要配置4 6 表6 2 一致性测试结果4 8 表6 3协议内存占用和c p u 利用率4 9 第1 i i 页 国防科技大学研究生院硕士学位论文 图1 1 图2 1 图2 2 图2 3 图2 4 图2 5 图2 6 图 图 图 图 7 8 1 2 图目录 1 9 9 4 2 0 0 7 年b g p 路由表的增长形式2 b g p 消息头结构6 o p e n 消息格式6 u p d a t e 消息格式。7 n o t i f i c a t i o n 消息格式9 b g p 有限状态机1 1 m p is e n d 和m p ir e c v 语句的消息信封和消息数据1 3 c o r e r o u t e r 1 组成结构图1 9 并行x k e r n e l 体系结构21 q u a g g ab g p 协议的实现结构简图2 2 事件队列关系图2 5 图3 3 q u a g g ab g p 协议路由表结构简图2 5 图3 4q u a g g ab g p 协议实现工作流程图2 6 图4 1 单线程b g p 转变为多线程b g p 2 9 图4 2 基于功能的线程划分3 0 图4 3 基于功能划分的b g p 协议多线程模型3 1 图4 4b g p 多线程并行模型3 3 图4 5b g p 流程图比较一3 4 图4 6 主线程结构设计图3 8 图4 7 从线程结构设计图4 0 图5 1事件队列、工作队列和邻居队列的变化4 2 图6 1测试环境示意图：4 6 图6 2a x 4 0 0 0 测试仪一致性测试端口设置图4 7 图6 31 个邻居2 0 万路由的路由学习时间5 1 图6 45 个邻居2 0 万路由的路由学习时间5 1 图6 51 0 个邻居2 0 万路由的路由学习时间5 2 图6 65 个邻居4 0 万路由的路由学习时间5 2 图6 75 个邻居6 0 万路由的路由学习时间5 3 图6 8q u a g g a b g p 协议2 0 万路由邻居切换时间5 4 图6 9p - b g p 协议2 0 万路由邻居切换时间5 5 图6 1 0q u a g g a b g p 协议4 0 万路由邻居切换时间5 5 图6 1 1p - b g p 协议2 0 万路由邻居切换时间5 6 第1 v 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他入已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它 教育机构的学位或证书而使用过的材料与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名： 日期：多叩孑年j 土月鸪日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子 文档，允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文作者签名：整查 作者指导教师签名：二杈 日期：如口r 年f 2 月名日 日期：勿钉哞厂2 ，月岁日 国防科技大学研究生院硕士学位论文 第一章绪论 边界网关协议( b o r d e rg a t e w a yp r o t o c o l ，b g p ) 是一种自治系统( a u t o n o m o u s s y s t e m ，a s ) 之间的路径向量协议，目前是i n t e m e t 中域问路由协议的事实标准。 它主要实现在a s 间交换网络可达性信息，维护大型网络之间的互连互通，并通过 设置策略保证各自管理a s 的自主性。 随着i n t e m e t 规模的不断扩展和网络应用的飞速增加，b g p 路由表的迅猛增长、 b g p 路由猝发更新等问题已经变得不容忽视，它们都进一步对网络设备的计算能 力和存储容量提出了更高的要求。 通信协议并行体系结构的研究从上个世纪9 0 年代初开始兴起，研究的热点主 要集中在加速端系统t c p i p 协议栈执行，分析验证各种共享、互斥资源对并行系 统的影响，以及开发集群结构下多路由节点间并行性等【i j 。通过对b g p 协议的研 究，发现其自身潜在的并行特性【2 】，而通信协议并行技术的不断发展和应用，也为 我们提供了实现b g p 协议并行化的各种方法，从而有效地缓解上述问题造成的巨 大压力。 1 1 研究背景 b g p 协议作为域间路由的标准【3 】，为运营商之间的互连提供了稳定而安全的 路由协议，具有丰富的路由控制机制。为了更好地控制路由策略，当前大部分的 运营商均将b g p 部署到骨干路由器。随着网络的不断扩展、路由器数目的增多以 及路由信息条目的激增，加快b g p 协议的处理速度提高其性能变得越来越重要。 根据摩尔定律，c p u 速度每1 8 个月翻一倍，而i n t e r n e t 带宽则翻4 倍，高速 增长的网络带宽对作为网络核心设备的路由器性能提出了越来越高的要求，而作 为路由器软件基础的路由协议也同时面临性能提升速度受限于c p u 速度的问题。 近几年来，多核处理器成为处理器发展的主流方向，多核服务器正在逐步取代现 有大部分服务器。同时，多核处理器及多核服务器的出现与发展也大大刺激了多 线程并行运算与处理的发展【4 5 j 。因此，开展b g p 协议的多线程并行性研究为解决 b g p 协议性能瓶颈问题提供了一条新的途径。 b g p 协议出现并发展了十几年，但其处理性能及规模可扩展性等方面的问题 也随着i n t e m e t 的发展而越来越突出嘲。 首先，随着i n t e r n e t 中各种应用的增加，b g p 协议也随着越来越多的应用特征 而变得愈加复杂。而协议的复杂化造成了路由器计算资源的紧张，路由计算无法 快速完成导致了协议收敛速度变慢。严重时则会使报文收发延误，进而导致b g p 第1 页 国防科技大学研究生院硕十学位论文 邻居会话丢失，引起路由震荡等，使路由器的计算资源更加紧张，严重影响路由 器的工作。路由器的处理速度取决于硬件和软件两个方面，在硬件发展速度越来 越跟不上网络发展要求的今天，我们则需要更多的关注如何在软件方面加快路由 协议的处理速度。 d a t e 图1 11 9 9 4 2 0 0 7 年b g p 路由表的增长形式 其次，随着i n t e m e t 规模的扩大，b g p 协议路由存储空间日趋紧张，使其对邻 居数量的支持等方面也存在着严峻的问题。图1 1 给出了来自g e o f f h u s t o n 的b g p 路由表的增长形式【7 l ，可以看出其增长趋势接近指数增长，这势必对协议在路由表 存储、支持的邻居会话规模、路由更新处理能力等方面提出严峻的考验。对于这 些问题，除了加快硬件更新换代以外，提高b g p 协议的执行速度既可以加快路由 表的读写速度，又可以加快路由更新处理速度，处理速度提升也就意味着短时间 内处理更多使邻居报文和协议对邻居会话支持的规模增加。 总之，b g p 协议面临的问题主要表现为路由器处理能力跟不上网络应用和需 求发展，这给b g p 协议性能带来了更高的要求。为了应对这些问题，除了依靠硬 件性能提升，主要研究方向集中在从协议软件着手缓解b g p 协议的压力。而以往 b g p 协议软件均为串行处理程序。事实证明，在经过长期的研究和发展后，b g p 协议在串行实现上的性能提升已到了瓶颈，为了使b g p 协议的性能得到更大提高， 我们开始在并行实现技术上寻求突破。 第2 页 国防科技大学研究生院硕士学位论文 1 2b g p 协议并行性研究现状 对b g p 协议并行性的研究，已有的成果均基于多处理器和集群体系结构而应 用的，主要包括b g p 并行路由计算及协议功能卸载等方法【8 、9 】。文献【l o 根据b g p 协议本身固有的并行特性，提出一种基于树型b g p 路由处理分布式计算模型。 b g p 协议功能卸载是指将协议进程中频繁执行的模块或者计算密集型模块下 载到其他路由节点或者下层网络处理器中，从而减轻控制平面负载。在这方面的 研究，有h e n r i k s s o n t l l 】为t c p 报文处理设计了协议处理器，将某些处理独立出来， 并在上面运行实时操作系统。w e s t r e l i n t l 2 j 等人对协议功能卸载进行了仿真模拟， 分析比较了不同t c p 功能卸载场景下的性能差异，对研究端系统传输协议和路由 协议的功能卸载有很强的指导意义。 并行路由计算是指将路由协议传统的路由计算过程并行化，使路由计算任务 可以在多个节点或处理器同时并行的完成。x i a o z h ez h a n g 1 3 1 提出的基于a g e n t 的 b g p 协议分布式并行实现模型就采用了这种技术。该模型引入a g e n t 技术中的 t e a mw o r k 思想，扩展b g p 协议，将其作为b g p 实体独立运行于每个路由节点 上，每个b g p 实体除了支持规范定义的b g p 内部、外部邻居之间的交互行为外， 通过内部通讯协议进行路由的协同计算和状态信息同步等。这时b g p 协议不再作 为一个独立的进程运行在任何节点上，而是将其协议功能分解到各个b g p 实体上， 由b g p 实体集合共同完成。 分布式处理思想的提出对协议并行性研究起到了重要的作用，推动了路由协 议并行思想的发展，目前对路由协议的分布式实现已有许多研究。分布式处理虽 然提升了协议处理速度，但多个处理结点的使用也增加了计算资源，各处理实体 间的通信等问题也制约着整体性能的提升。 总之，以上的这些方法虽然都是对协议的并行性处理技术，但从根本上还只 是将计算资源进行简单的叠加，协议执行过程仍旧采用的是串行执行模式i l j 。 1 3 课题研究内容 本文对b g p 协议的工作原理及性能等方面进行了研究，结合多线程并行编程 技术设计实现了多线程并行b g p 协议，主要包括以下几个方面的工作： 1 对b g p - 4 协议进行了深入研究，对并行编程技术的使用进行了整理比较 通过对b g p 协议相关资料的研究掌握了b g p 协议的运行原理和路由处理过 程。对o p e m m p 、m p i 、p o s i x 线程编程三种并行程序设计方法进行了解和实验， 选取p o s i x 线程编程技术为设计多线程并行b g p 协议的实现方法。 2 对q u a g g ab g p 代码进行分析 第3 页 国防科技大学研究生院硕十学位论文 选耿歹l ：源代码q u a g g a 0 9 9 9 作为实现多线程并行b g p 协议设计的原型进行分 析，整理出q u a g g ab g p 协议从协议启动、连接建立到报文收发及报文处理等过程 的具体实现方法。 3 提出多线程并行b g p 协议模型并设计实现 通过对q u a g g ab g p 协议的研究，结合其潜在并行特点，提出分别基于功能划 分和邻居会话划分的两种多线程的并行b g p 协议的模型。选择其中基于邻居会话 划分的模型进行p b g p ( p a r a l l e l b g p ) 协议的详细设计，并具体完成的实现。 4 对原型b g p 协议和p b g p 协议的性能和一致性等功能测试及分析 使用联想4 核服务器、a x 4 0 0 0 测试仪及控制台组成的测试环境。测试q u a g g a b g p 协议和p b g p 协议的一致性和性能，并进行比较。根据结果对p b g p 协议的 功能正确性和性能优化性进行验证，并与理论分析数据进行对比分析。 1 4 论文结构 本文共分为七章 第一章：绪论，主要介绍课题背景，研究现状，本课题的研究内容以及本论 文组织结构等。 第二章：介绍b g p 协议主要内容、并行及多线程编程技术及路由协议的并行 处理技术研究现状。 第三章：分析了q u a g g ab g p 协议的结构及特点。 第四章：根据q u a g g ab g p 协议提出两种多线程并行b g p 协议模型。对模型特 点进行比较分析，选取其中一种设计并实现了一种多线程并行b g p 协议一一 p b g p 协议。 第五章：p b g p 协议设计与实现过程中的关键问题与分析。 第六章：对q u a g g ab g p 协议和p - b g p 协议的性能和一致性等功能进行测试和 分析。 第七章：全文的总结，以及下一步工作的展望。 第4 页 国防科技大学研究生院硕士学位论文 第二章相关技术与研究工作 2 1b g p 协议简介 b g p 是用于自治系统之间的路径向量协议，它的主要功能是在各个实现了 b g p 协议的系统之间交换网络可达信息，可达信息包括网络前缀及路由所穿越的 自治系统的列表。b g p 使用点到点的t c p 协议作为下层传输协议，通过与邻接的 支持b g p 协议的系统之间建立b g p 邻居会话，来交换信息。按照对端系统是否在 本a s 内部，可以将b g p 邻居会话分为外部b g p ( e b g p ) 和内部b g p ( i b g p ) 两种。a s 使用外部b g p 与邻接的a s 交换路由可达信息，使用内部b g p 将路由 可达信息传播到a s 内部。b g p 协议可以在原有缺省最短路径选择的基础上，通 过输入或者输出策略影响路由选择过程。路由器调用b g p 的路由决策过程，对每 个网络前缀，从来自于i g p ( 内部网关协议) 的内部网络拓扑信息生成将网络前缀 地址映射到输出链路的报文转发表。 如果一个特定a s 有多个b g p 发言者同时为别的a s 提供中转业务，应该注 意保证本a s 中对路由有一致的观点。a s 内部路由的一致看法由内部路由协议提 供。a s 外部对路由的一致看法由所有a s 内部的b g p 发言者通过全互联保证。在 b g p 发言者把中转业务通告到别的a s 之前所有的内部路由器需要更新中转信息。 不同a s 之间的b g p 发言者的连接被称为“外部 链路。同一个a s 内部的b g p 连接被称为“内部”链路。 2 1 1b g p 协议工作流程 运行b g p 时，b g p 发言者首先在t c p 端口1 7 9 等待连接，同时和其配置的 邻居主动建立连接，一旦传输层连接建立之后，双方就各自发送o p e n 报文协商连 接参数。参数确认之后，b g p 发言人之间才可以交换路由信息。初始的数据流是 全部的b g p 路由表，之后，只有在路由信息发生变化时，才发送更新信息。为确 保连接的存在，b g p 发言人周期性地发送k e e p a l i v e 报文。当有错误和特殊情况发 生时，便发送n o t i f i c a t i o n 报文，并关闭连接。 2 1 2b g p 协议报文格式 b g p 协议启动后将进入循环处理过程，当接收到指令或收到报文( 包括连接 建立、路由更新及错误处理等) 时做相应处理等。b g p 报文作为协议的一个重要 组成部分，主要分为o p e n 、u p d a t e 、k e e p a l i v e 和n o t i f i c a t i o n 等几种。 第5 页 国防科技大学研究生院硕士学位论文 报义格式包括消息头和消息体，大小在1 9 字节至4 0 9 6 字节之i 、日j 不等。1 9 字 节为消息头大小，消息头的结构如图2 1 所示。 0l2 3 0l2 34567 8 9 012 345 6 7 8 9 012 345 6 7 8 9 0l + 一+ 十+ 一+ 一+ 一+ 一+ + + 一+ 一+ 一+ 一+ 一+ 一+ _ + 一+ 一+ 一+ 一+ 一+ 卜+ 一+ 一+ 一+ 一+ 一+ 一+ 一+ 一+ 一+ ii + li + i l l a r k e r i + ii + 一+ 一+ 一+ 一+ 一+ 一+ 一+ 一+ 一+ 卜- + 一+ 一+ 一+ 一+ 一+ 一+ 一+ 一+ 一+ 一+ + 一+ + 卜+ 一+ 一+ 一+ 一+ + il e n g t hit y p ei 4 - - 1 _ - - - 4 - + - 4 - 4 - - 4 - 4 - - + - 4 - 4 - 4 - - 4 - - 4 - 4 - - 4 - 4 - 4 - + - + - + - + 图2 1b g p 消息头结构 消息头前1 6 字节为m a r k e r 标识部分包含消息接收者可以预测的值。如果消 息类型是o p e n ，或者o p e n 消息没有承载认证信息( 作为可选参数) ，标记必 须是全1 。否者，标记的值要使用认证机制来计算( 认证机制是通过认证信息的一 部分来指定的) 。标记可以用来探测b g p 对端的同步丢失，认证进入的b g p 消息。 2 字节的长度信息，定了消息的字节全长，包括头部的字节。1 字节的无符号整数 制定了消息类型编码，定义为：1 o p e n ；2 - u p d a t e ；3 - n o t i f i c a t i o n ； 4 ke e p a l i v e 。 1 o p e n 消息： 在传输协议连接建立之后，两边发送的第一个消息是o p e n 消息。如果o p e n 消息可以接受，需要发回一个k e e p a l i v e 消息来确认o p e n 消息。确认了o p e n 消息后，u p d a t e ，k e e k p a l i v e 和n o t i f i c a t i o n 消息可以交换。 o p e n 消息格式如图2 2 所示。 0l2 3 0l23456 78 90123456 了89o123456 789 o1 + 一+ + 一+ + 十+ 一+ 一4 - i v e r s i o n l + 一+ 卜+ 4 - + 一+ 一+ 一+ 一+ 一+ 一+ 一十一+ 一4 - 4 - + i弧ya u 七o n o m o u ss y s te m i + 一+ 卜十+ 一4 - + - 4 - - + 一+ 一+ 一+ 一+ 一+ + _ + i h o l dt i m e i 4 - + - + - + - 4 - - + _ + 一+ + + 一+ 一4 - 4 - + 一+ 一+ 一+ 卜叫+ + 卜- + 卜。+ 卜十+ 一+ 一+ + 4 - + i b g pi d e n t i f i e r i 4 - + - + - 4 - 4 - + 一+ + + 一4 - + 一+ 一+ + + 一4 - + _ + + + + 一忡+ 一4 - 4 - + + 一+ 一4 - - 4 - + io p tp a r ml e ni + 一+ 卜+ 一+ 一+ 一+ + - 4 - - + 一4 - - 4 - - + - 4 - - 4 - - + 一4 - + - + - - 4 - - + 一+ 卜+ 一+ 一+ 一+ 一+ _ 4 - - + 一+ - + ii io p ti o n a lp a r a m e te r sl ii + 一4 - - + 卜+ 卜十+ 一+ 一十一+ 一4 - + + + + 一+ 卜+ 卜+ + 一+ - + - 4 - + 一+ 一+ + + 一+ - + 图2 2o p e n 消息格式 第6 页 国防科技大学研究生院硕士学位论文 1 字节的无符号整数v e r s i o n ，版本号，目前为4 。 2 字节的无符号整数m ya u t o n o m o u ss y s t e m 自治域号。 2 字节的无符号整数h o l dt i m e ，记录消息发送方期望的h o l dt i m e 值。接收 方收到后，根据配置和对方期望的h o l dt i m e 值取其中较小者计算出h o l dt i m e 计 时器的值。且规定其必须为0 或者不少于3 秒。 4 字节的无符号整数b g pi d e n t i f i e r ，指示了b g p 发送者的标示符。给定的 b g p 发送者设置b g p 标示符为i p 地址。在启动的时候决定b g p 表示符，对每一 个本地端口和每一个对端是一样的。 l 字节的o p t i o n a lp a r a m e t e r sl e n g t h 无符号整数指示可选参数域的字节总长 度。如果这个域是o ，说明没有可选参数。 可选参数o p t i o n a lp a r a m e t e r s ，这个域包含了可选参数清单，每一个参数编码 为 三元组。参数类型是1 个字节明确指示了参数 的类型。参数长度1 子节包含参数值的字节长度。参数值是变长的，根据参数类 型有不同的解释。 o p e n 消息的最小长度是2 9 字节( 包括消息头) 。 2 u p d a t e 消息及路由处理： u p d a t e 消息用于在b g p 对端之间交换路由信息。u p d a t e 消息报内的信息 可以被用来构造a s 之间的拓扑关系描述。u p d a t e 消息用来广播一条可用路由 到对端，或者撤销多条不可用的路由。 u p d a t e 消息格式如图2 3 所示。 + 一一一一一一+ i u n f e a s i b l er o u te sl e n g t h ( 2o c te ts ) i + 一一一一一一一一+ f v i t h d r a w nr o u te s ( v a r i a b l e ) i 1 一一一一+ i t o t a lp a t ha t t r i b u t el e n g t h ( 2o c t e t s ) i + 一一一一一+ l p a t ha t tr i b u te s ( v a r i a b l e ) i + 一一一一一一一一+ in e t w o r kl a y e rr e a c h a b i l i t yi n f o r m a ti o n ( v a r i a b l e ) i “ 一一一一一+ 图2 3u p d a t e 消息格式 u n f e a s i b l er o u t e sl e n g t h2 字节，表示撤销路由的字节总长度，o 说明没有撤 消路由。 w i t h d r a w nr o u t e s 可变长，包括一系列的需要撤销的路由i p 前缀。每一个i p 前缀编码为( 长度，前缀) 二元组。 t o t a lp a t ha t t r i b u t el e n g t h 2 字节，表示路径属性域字节总长度。0 表示在 u p d a t e 消息中没有网络层可达信息域。 第7 页 国防科技大学研究生院硕士学位论文 p a t ha t t r i b u t e s 可变长，在每一个u p d a t e 消息中有变长的路径属性序列。每 一个路径属性是 变长三元组。 n e t w o r kl a y e r r e a c h a b i l i t yi n f o r m a t i o n ( 网络层可达信息) ，变长域包含了i p 地址前缀的列表。网络层可达信息的字节长度不是明确编码的。编码时作为一个 或者多个二元组格式为( 长度，前缀) 。其中： 长度，指示了i p 地址前缀的比特长度。0 地址指示了匹配所有i p 地址的前缀 ( 前缀本身o 字节) ； 前缀，包含了i p 地址前缀跟随足够的填充比特使结尾能够落在字节边界，填 充比特的值无关紧要。 u p d t a e 消息的最小长度是2 3 字节= 1 9 字节定长消息头+ 2 字节不可用路由长 度+ 2 字节总的路径属性长度( 不可用路由长度和总的路径属性长度都是o ) 。 一个u p d a t e 消息可以仅仅撤销路由，这样就不需要包括路径属性或者网络 层可达信息。相反，也可以仅仅广播可达路由，这样w i t h d r a w nr o u t e s 不 需要了。 b g p 协议运行过程中主要收发的报文为u p d a t e 报文，路由更新报文处理过 程主要是：首先，更新报文要记录到相应的r i b i n ( 输入路由信息库) 中。之后 按照用户配置，执行输入路由策略过滤。如果通过，将其加入到b g p 路由表中并 执行路由选优过程，按照b g p 路由选择规则将新增路由与已有的路由进行比较。 如果新增路由被选为最优路由，相应的更新转发表中对应的转发项。最后需要将 新增路由通告给其他b g p 邻接路由器，执行每个邻居会话( 除来源邻居会话以外) 的输出路由策略，根据过滤结果决定是否在该会话上发送路由更新并记录到 r i b o u t ( 输出路由信息库) 中。 3 k e e p a l i v e 消息 k e e p a l i v e 消息在对端之间交换以确定对端可达性，频率要满足h o l d t i m e 计时器不溢出的标准，所以合理的最大k e e p a l i v e 消息间隔是h o l dt i m e 计时器间隔的1 3 。k e e p a l i v e 消息频率不能超过每秒一次。可以使用h o l d t i m e 计时间隔的函数调整发送k e e p a l w e 消息的速率。如果商议h o l dt i m e 计时间隔是0 ，周期性的k e k p a l i v e 消息则不发送。k e e p a l i v e 消息只包含消 息头长度是1 9 字节。 4 n o t i f i c a t i o n 消息 n o t i f a c a t i o n 消息在探测到错误情况时发送。b g p 连接发送他之后要立即 关闭。n o t i f i c a t i o n 消息格式如图2 4 所示。 第8 页 国防科技大学研究生院硕十学位论文 0123 012 345 6 7 8 9 012 345 6 7 8 9 0l2 345 6 7 8 9 0l + 一+ 一+ 一+ 一+ 一+ 一+ 一+ - + 一+ 一+ 一+ 一+ 一+ 一+ 一+ 一+ 一+ 一+ 一+ + + 一+ 一+ 一+ + + 一+ 一+ 一+ 十+ 一+ ie r r o rc o d e l e r r o rs u b c o d e i d a t a l + 一+ 一+ 一+ 一+ - + 一+ 一+ + + 一+ 一+ + + 一+ 一+ 一+ ii - b - 4 - - 4 - 4 - - 6 - 4 - - 4 - 忡+ - 1 + 1 - 1 一q 一 一卜- 1 一_ 一_ 一1 一卜- 1 - 一1 1 一- 一卜1 卜+ 图2 4n o t i f i c a t i o n 消息格式 错误码和错误子码用来标识发送此n o t i f i c a t i o n 报文的原因，均为1 字节 整数。数据部分，用来诊断错误原因的，内容依赖于错误码和错误子码。 n o t i f i c a t i o n 消息最小的长度是2 1 字节( 包括消息头) 。 2 1 3b g p 协议有限状态机 b g p 协议与邻居建立起连接以后，为每个邻居保持一个独立的有限状态机以 维持对端之间的状态变换。b g p 协议有限状态机分为6 个状态和2 8 种事件，状态 之间的转换由时间驱动。 6 种状态是：i d l e 状态、c o n n e c t 状态、a c t i v e 状态、o p e n s e n t 状态、o p e n c o n f i r m 状态、e s t a b l i s h e d 状态。 2 8 种事件是：m a n u a l s t a r t ( 1 ) 、m a n u a l s t o p ( 2 ) 、a u t o m a t i c s t a r t ( 3 ) 、 m a n u a l s t a r t _ w i t h _ p a s s i v e t c p e s t a b l i s h m e n t ( 4 ) 、 a u t o m a t i c s t a r t _ w i t h _ p a s s i v e t c p e s t a b l i s h m e n t ( 5 ) 、 a u t o m a t i c s t a r t _ w i t h _ d a m p p e e r o s c i l l a t i o n s ( 6 ) 、 a u t o m a t i c s t a r t _ w i t h _ d a m p p e e r o s c i l l a t i o n s _ a n d _ p a s s i v e t c p e s t a b l i s h m e m ( 7 ) 、 a u t o m a t i c s t o p ( 8 ) 、c o n n e c t r e t r y t i m e r e x p i r e s ( 9 ) 、h o l d t i m e r e x p i r e s ( 10 ) 、 k e e p a l i v e t i m e r e x p i r e s ( 1 1 ) 、d e l a y o p e n t i m e r e x p i r e s ( 12 ) 、i d l e h o l d t i m e r _ e x p i r e s ( 1 3 ) 、t c p c o n n e c t i o n j a l i d ( 1 4 ) 、t c p _ c r _ i n v a l i d ( 1 5 ) 、t c p _ c r _ a c k e d ( 1 6 ) 、 t c p c o n n e c t i o n c o n f i r m e d ( 17 ) 、t c p c o n n e c t i o n f a i l s ( 18 ) 、b g p o p e n ( 19 ) 、b g p o p e n w i t hd e l a y o p e n t i m e rr u n n i n g ( 2 0 ) 、b g p h e a d e r e r r ( 21 ) 、b g p o p e n m s g e r r ( 2 2 ) 、 o p e n c o l l i s i o n d u m p ( 2 3 ) 、n o t i f m s g v e r e r r ( 2 4 ) 、n o t i f m s g ( 2 5 ) 、k e e p a l i v e m s g ( 2 6 ) 、u p d a t e m s g ( 2 7 ) 、u p d a t e m s g e r r ( 2 8 ) 。 开始b g p 在i d l e 状态。 i d l e 状态： 在这个状态，b g p 拒绝任何进入的b g p 连接。不为对端分配任何资源。响应 事件1 、3 至s t a r t 状态；响应事件4 、5 至a c t i v e 状态。在i d l e 状态下任何别的事 件被忽略。 c o n n e c t 状态： 第9 页 国防科技大学研究生院硕士学侥论文 在这个状态b g p 等待传输协议连接的完成。事件1 、3 7 在c o n n e c t 状态下 被忽略：响应事件2 、8 、1 0 、l l 、1 3 、1 9 、2 1 1 8 到i d l e 状态；响应事件9 、1 4 、 1 5 保持c o n n e c t 状态；响应事件1 2 到o p e