（计算机软件与理论专业论文）acr中央控制单元可靠工作机制的研究与实现.pdf

信息工程大学硕士学位论文摘要大规模接入汇聚路由器a c r 作为底层用户接入网与骨干网之间的桥梁，是一种不同于其它路由器的特殊网络设备。由于它兼顾骨干网核心路由器和底层用户交换机的双重功能，致使在发生故障时无法由其他路由器屏蔽其故障，所以保证其自身的可靠工作至关重要。本文结合国家8 6 3 计划专项重大课题“大规模接入汇聚路由器( a c r ) 系统性能和关键技术研究”，针对a c r 中央控制单元的单机架组网方式和多机架互联组网方式分别提出了对应的可靠工作机制。在此基础上选择对路由器性能影响最大的0 s p f 协议，提出了一种针对0 s p f 平滑重启协议应用局限性的改进方案，从而进一步完善了两种组网模式下的可靠工作机制。其中基于单机架组网模式的主备倒换工作机制和o s p f 平滑重启的改进方案已经予以实现，测试结果表明：该机制可以有效的保证发生故障时a c r 的可靠工作，满足a c r 中央控制单元可靠工作机制的需求。本文的主要工作如下： 在单机架组网模式下，提出了一种基于n s r 主备倒换的可靠工作机制。文章首先对主备倒换机制中的三个关键环节：故障探测，故障恢复以及状态信息备份进行了深入研究，利用马尔可夫模型对故障恢复机制与可靠性关系进行分析，这为a c r 单机架可靠工作机制的设计提供了理论依据。 在多机架互联组网模式下，提出基于t r p 思想的协同工作机制。针对a c r 存在大量直连路由的问题，提出了一种结合哈希函数的分布路由同步算法；并针对多控制单元可无冲突对接口设备进行管理问题，设计了保证接口管理视图一致性的方法。针对路由协议平滑重启机制无法独立完成的缺点，提出0 s p f g r a c e f i l l r e s t a n 协议的改进方法。使得本来需要邻接节点协助重启的工作模式，简化为由主备两个控制单元配合完成重启。 对基于n s r 主各倒换机制和改进的o s p fg r a c e 血lr e s t a n 协议在单机架模式下予以实现。通过对功能的划分，给出具体的模块化实现过程。通过测试表明，该机制可满足a c r 中央控制单元可靠工作的要求。关键词：可靠工作，主备倒换，协同工作，0 s p f 平滑重启，心跳探测，路由同步第v i 页信息工程大学硕士学位论文a b s t r a c ti 脚g c 一a l ea c c e s sc v e r g c er o u t e r ( a c r ) i sas p e c i a ln e t w o r kd e “c ew 量l i c ha c t s 硒ab r i d g eb e 咐e t l l eb a c k b o n en e 时o r k 锄d 饥dl l s e 瑙，锄di ti sd i 行- e 呦t 舶mo t l l c rr 0 1 n e r s w h e i lf 甑l u r ch a p p e ，a c rc 觚n o tb es u b s t i t u t o db yo t l l e rr o u t e r sf o ri tw o r k sn o to n l y 勰ac o r cr o u t e rf b rb a c k b o n en e t w o r kb u ta l s o 嬲龇c i l du s e 碍s w i t c h t h e r e f o r e ，i ti sv 7i m p o n a l l tt ok e 印托l i a b i l i t yo fa c r b 硒e do nm en a t i o n a l8 6 3s p e c i a l i z o dr e s r c hp 叫e c t ”r e s e a r c ho ns y s t 锄p c r f 撕n a n c e 觚d 王【e yt e c l l n o i o 百e so fi a r g e - s c a i ea c c e s sc o n v e f g c er o u t e r ( a c r ) ，t l l i sp 印e rm a i l l l yf o c u s e so i ll i s a b i l i t yo fa c r b 勰c d0 nt h et w ot y p e so fn e t w o r kb u i l d u p蛐m c t i l r c so fa c r ，t l l i st h e s i sp r c s e m st h em e c h a i l i s mf o rr e l i a b l eo p e 珀：t i o ni nc 锄【廿a lc o n 勘r o lu i l i to f a c r a c c o r d i n gt ot h em e c h 锄i s m ，t h em a i nw o r ko f t h i sd i s s c r 嘶0 ni s 勰f o l l o w s ：1 t h ed e s i g na 1 1 di n l p l e m e l l t a t i o no fm 咖一s t a l l d b ys w “c hm e c h a n i 锄b 鹤e do nn s ri sp r o p o du n d e rs i n 舀e s h e l fn e 咐o r kb u i l d l l ps 仇l c t i l r e s nc 觚b ec o m p l e t e du s i n gm a i n 锄ds t a l l d b ym a i n - b o a r d s t h r o u 曲b u i l d i n ga 曲o c h 嬲t i cp m c e s sm o d e ，t l l i sp 印e r 锄a l y z e sm et l l r e cw a y so f 筋l u r ed e t c c t i o nh o wt oa 舒酏tt l l ep c r f b n n a l l c eo fm a i l 】一s t a j 】d b ys w “c h ，a n dp “d l h e o r yr e f 的l c ef o rt h ed e s i 鲫o f r c l i a b l e 叩e r a t i o no nc e l l t r a lc o n 呐ll l l l i to f a c r 2 ac o 叩e r a t e dw o r k i n gm e c h a l l i m li sp r o p o s e dt op m t e c tc 吼h 丑lc o n 臼o l 砌t 蚰d e rm em u l t i s h e l fi n 咖一c o 曲e c t e dn e 时o f ks 咖c t i l 】r em o d e t h i sp a p e rf o c u s e so n 铆ok c yp 玎o b l e m si nt l l i sm o d e ：m ef i r s ti st h a tt l l e r ei sal o to fd i r c c t - c o 衄e c t i o nr o u t i n gi n s i d ea c t h es e c o n di sh o wt om a n a g et h ei m e r f k ee q u i p m 明tw i t h o u tc o l l i s i o n h a s ha l g o r i t l l i nt ok e e pt l l er o u t et a b l es y n c h r o i l i z e di sp r o v i d e d ，觚das c h e m ei sd e s i 弘c dt ok c c pt l l ec o m i s t 印c yo fi m 刚沁em a l l a g e m e i l t 3 a ni i n p r o 啊n go s p f 簪a c e f i l lr e s t a r tp f o t o c 0 1 i sd e s i 朗e d m l ei m p r o v i n gs c h e m e ，m eo g i l l a lr e s t a nm o d ew l l i c hn e e d sc o 叩e r a t i o n 锄o n gn e i g h b o 硌i si n l p r o v e da n ds i n l p l i f i e d ，a n di tc a i lw o r k m a i l l 锄ds t a i l d b ym a i n - b o a r dc o 耵叩l e t ei n d 印e 1 1 d e n t l y 4 a tt l l e 锄do ft l l i sp a p 豇；i ti st 1 1 er e a l i z a t i o no ft l i em a i n s t m “l b ys w i t c hb 邪e do nn s ra n di 埘p m v e do s p fe x t e n d e dp r o t o c o lo na c r t e s tr e s u l t si n d i c a t et l l a tt h em e c h a i l i s mo fm a i n - s t a l l d b ys w i t c hc 锄s a t i s 母t l l er c l i a b i l i t yr e q u i r e l n e l l to f t h ea c k e yw o r d s ：r e l i a b l eo p e r a t i o n ，m a i n s t a l l 曲ys w i t c h ，c o 叩e r a t i ，0 s p fg r a c e f i i lr e s t a n ，h e a n b e a td e t e c t i o i l ，r o u t cs y l l c h r o l l i z a t i o n第v 页信息工程大学硕士学位论文表目录表1 操作状态机状态转移表1 1表2 接口管理函数定义2 2表3n s r _ m s 模块与板间通信模块之间接口的数据结构3 6表4 n s r - m s 模块与系统数据维护模块之间接口的数据结构一3 7表5n s r m s 模块与系统数据维护模块之间接口的数据结构二3 7表6u d p 通信报文格式3 7表7u d p 通信报文各数据域说明3 8表8t c p 通信报文格式3 8表9t c p 通信报文各数据域说明3 8表1 0 文件备份测试统计4 2第1 i i 页信息工程大学硕士学位论文图目录图1a c r 单机架组网示意图2图2 可用性数值关系图4图3 状态同步机制示意图6图4 路由协议平滑重启触发示意图6图5 路由协议平滑重启恢复示意图7图6 数据复制机制示意图7图7 冗余结构马尔可夫模型8图8 路由协议平滑重启方式状态转移图8图9 状态同步机制状态转移图9图1 0 数据复制机制状态转移图9图1 l 故障恢复机制性能对比图1 0图1 2 操作状态转移图1 1图1 3 主用丢失心跳报文的处理过程1 3图1 4 主备倒换流程图1 4图1 5v 甜冲协议工作示意图1 5图1 6 a c r 路由器各处理单元拓扑结构1 6图1 7 多处理节点冗余备份拓扑图1 7图1 8a i 也f 算法本地添加路由过程1 8图1 9 a i u 弹算法本地删除路由过程1 8图2 0 a r e f 算法同步添加过程1 9图2 1a i 也f 算法同步撤消过程1 9图2 23 n e t 地址分配示例2 0图2 3 协同工作模式的系统结构2 1图2 4 接口管理状态转移图2 2图2 5 添加接口流程2 3图2 6 删除接口流程2 3图2 7o s p fg r 工作拓扑描述图2 4图2 8o s p fg r 工作过程2 5图2 9 修改后的o s p fg r 工作流程2 7图3 0 主备倒换模块在系统中的位置图2 9图3 ln s r m s 系统功能模块图3 0图3 2 主控状态信息数据结构3 0第页信息工程大学硕士学位论文图3 3 主备选举的3 种情况3 l图3 4 心跳周期测试结果3 2图3 5 死亡判断周期测试结果3 3图3 6 防振荡定时器工作过程3 4图3 7 二叉树及其树节点结构3 5图3 8n s r - m s 与b d c o m 接口3 5图3 9n s r m s 与s y s d 朋渔接口。3 6图4 0o s p fg r 模块位置图3 9图4 l0 s p fg r 初始化流程图4 0图4 2 备用帮助模式工作流程4 0图4 3 主备倒换测试环境示意图4 l图4 4 主备倒换后路由稳定测试4 2图4 5o s p fg r 测试环境示意图4 3图4 6o s p fg r 测试拓扑图4 3图4 70 s p fg r 改进前后性能对比图4 3第v 页原创性声明本人声明所提交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表和撰写过的研究成果，也不包含为获得信息工程大学或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。学位论文题目：学位论文作者签作者指导教师签名：嘲。e ；期：n ) 年华月，re名：1 扬让日期：年二月，产。垆ir。i学位论文版权使用授权书本人完全了解信息工程大学有关保留、使用学位论文的规定。本人授权信息工程大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。( 保密学位论文在解密后适用本授权书。)学位论文学位论文作者指导信息工程大学硕士学位论文第一章引言1 1 研究背景在现有的互联网体系中，各路由处理节点的连接方式可以保证：如果某台路由器可靠性不高，发生了故障，可由相邻路由器选取新路由屏蔽其故障。同时，各路由器厂商及标准化组织也相应提出或制定了提高可靠性的协议或规范，例如有代表性的c i s c o 公司的h s r p ( h o ts t a n d b yr o u t i n gp r o t o c 0 1 ) 协议【1 】和t f 提出的v r r p ( v i n i l a li b i n c rr c d 硼d a n c y p r o t o c 0 1 ) 【2 】协议等。但上述协议都不是从提高路由器自身可靠性出发而设计的。大规模汇聚路由器j 蛇r 作为一种不同于其他路由器的特殊设备f 3 1 ，除了可完成路由计算功能，还需要对用户接口及用户业务进行管理和控制。鉴于a c r 兼顾骨干网核心路由器和底层交换机功能的特殊性，在故障时无法由其他节点取代其工作，所以提高自身可用性十分重要。本课题依据国家8 6 3 计划专项重大课题“大规模接入汇聚路由器( a c r ，a c c e s sc o n v e r g e l l c er o u t e r ) 系统性能和关键技术研究”，主要针对a c r 中央控制单元的可靠工作机制进行研究。1 2 研究任务首先针对a c r 中央控制单元的两种组网形式：单机架组网和多机架互联组网，各提出一套保证可靠工作的方案，即基于n s r ( n o n s t 叩r d u t i i l g ) 的主备倒换机制和基于v 砌冲思想的协同工作模式；其次选取路由协议中对路由器性能影响最大的o s p f ( o p c i ls h o 懒tp a t hf i r s t ) 协议，对其扩展协议中完成重启功能的0 s p fg r ( o s p fg m c e f h lr e s t a r t ) 协议【4 】进行分析，针对其使用局限性的问题，提出改进方案。1 2 1a c r 两种组网形式的可靠工作机制a c r 大规模接入汇聚路由器作为新一代网络设备，它可以满足对6 万用户的接口及业务进行管理与控制，以及协同宽带运营支撑系统b o s s 支持宽带网络业务运营环境。就其中央控制单元a c r - s 而言，有两种组网形式，所以需要分别进行可靠工作机制的设计。单机架组网：如图l 所示，a c r s 作为集中控制单元，可采用两个主控板的硬件冗余设计，主用主控完成各种管理及路由计算任务，并将控制管理信息及转发信息备份到备用主控上，一旦主用故障，由备用迅速接替其工作，通过主备倒换来保证在单机架组网模式下a c r 的可靠工作。多机架互联：为实现对大规模用户的服务，采用多个主控机架共同组成a c r s 系统，各控制单元间处于平等地位，分别进行路由计算，再向下层e m d ( e m e r i l e tm u n i p l e x e rd 伽u l t i p l e 】【e r ) 单板下达转发及管理信息。同时各控制单元又可彼此具有冗余功能，即某个控制单元发生故障，可由系统中其它成员接替其工作。第1 页信息工程大学硕士学位论文图1 a c r 单机架组网示意图1 2 2 支持0 s p f 平滑重启的协议扩展功能路由器最关键的作用是进行路由协议的计算。其中，0 s p f 协议作为一种基于最短路径优先( s h o n e s tp 砒f i r s t ) 算法的域内路由协议，各节点通过m 层传输定时通告拓扑信息，再根据拓扑计算最短路径；而b g p 协议【5 】是一种距离矢量( d i s 伽1 c ev c c t o r ) 路由协议，以t c p 作为传输协议，在通信时，要先建立t c p 会话，使用增量的、触发性的路由更新。他们之间的区别是：运行b g p 的各节点保存的是网络的路由信息，在节点出现故障再重启时，与其相邻的节点仅通过重新通告删除或添加的路由，网络即可达到稳定状态；而o s p f 协议由于采用拓扑更新，虽然可以保证不产生路由环路及路由黑洞，但在路由器故障和恢复时，都会造成网络中大量的拓扑通告信息。0 s p f 重启后，需要通过重新学习拓扑，进行计算后才可恢复。由于o s p f 的拓扑更新机制，带来某节点在故障或重启时，不仅对网络造成很大抖动也极大增加了本节点的处理负担，成为路由器不稳定的隐患。针对这个问题，在设计a c r路由器可靠工作机制中，加入了对o s p f 扩展协议中重启功能的研究与实现，通过对0 s p fg r a c e f h lr e s t a r t 协议的改进，使a c r 中央控制单元的工作更为可靠。1 3 主要工作本文基于对大规模汇聚路由器a c r 的可靠性需求，结合“大规模接入汇聚路由器系统性能与关键技术研究”这一国家8 6 3 计划重大课题，通过对a c r 中央控制单元可靠工作的需求分析，提出一套中央控制单元可靠工作机制，其中着重围绕主备倒换的技术细节、协同工作的关键问题及对0 s p f 平滑重启的改进三方面，从理论、设计、实现或仿真等角度进行阐述。本文的主要研究内容如下：第2 页信息工程大学硕士学位论文对主备倒换中三个关键环节：故障探测、状态备份及故障恢复机制进行研究和分析，利用连续时间马尔可夫链对几种故障恢复方法进行可用性对比，得出采用路由协议平滑重启方式理论可靠性最好；而采用状态同步方式，若可提高倒换速度，也可保证很高的可靠性的结论。鉴于协议扩展中平滑重启功能具有使用的局限性，重点对如何提高倒换速度关键问题进行研究。在对三个关键环节研究分析的基础上，设计主备倒换自动机，作为模块化实现的基础。在对基于n s r 的主备倒换机制的设计中：首先通过设计操作控制自动机，对方案的功能进行逻辑划分；通过实验比较心跳探测周期与死亡判别周期的关系对探测性能的影响，加入故障判别机制，降低因心跳链路拥塞造成错误倒换的可能；根据理论分析中的结果，为了减小倒换的时延，采取状态同步作为故障恢复机制，在主备间实时备份设备的配置数据、接口状态数据以及各类路由转发表，并针对o s p f 协议进行对l s d b 数据库的备份。通过测试评估，采用主备倒换保证了中央控制单元的可靠工作要求。在对多机架互联组网下的协同工作模式的研究中：针对a c r 存在大量直连路由，以及分布式路由处理节点信息不同步的问题，提出了一种结合哈希函数的分布路由同步算法；又针对多机架协同工作时，各接口在逻辑上必须对应一个设备驱动以完成注册、接收、发送等工作，如何保证一个设备层次的一致性视图问题，本文提出了一种接口管理方案。针对实现路由协议中对路由器可靠工作影响最大o s p f 协议，通过对其协议扩展的o s p fg r a c e f i l lr e s t a n 的研究，针对其必须由邻接路由器协同完成的缺点，提出利用备用主控完成协同重启的方案，并予以实现，通过测试表明，改进前后的0 s p f 重启速度相差无几。1 4 本文的结构本文各章的内容安排如下：第一章：简要介绍了课题背景、研究问题以及论文的组织结构。第二章：对单机架组网的可靠工作机制基于n s r 的主备倒换机制进行设计。针对涉及的关键技术进行分析对比，并设计系统操作自动机，对n s r m s 的工作机制进行描述。第三章：对多机架互联组网模式下的协同工作机制进行设计。以v 心思想为基础，针对协同工作中的两个关键问题：存在大量直连路由的分布式节点路由信息同步问题和设备管理视图一致性问题，分别提出解决方案。第四章：分析0 s p fg m c e f h lr e s t a n 协议，并针对其使用局限性，不能完成路由器自愈功能，提出改进的设计方案。第五章：实现在单机架组网模式下的可靠工作机制基于n s r 的主备倒换机制和改进的o s p f 平滑重启机制，本章给出具体的模块化分，及实现细节描述。最后给出测试数据。第3 页信息工程大学硕士学位论文第二章基于n s r 的单机架主备倒换工作机制设计在冗余结构的单机架组网模式下，采用主备倒换机制保证可靠工作。本章首先对主备倒换过程中三个关键问题：故障探测、状态信息备份及故障恢复机制进行研究，利用马尔可夫模型，分析故障恢复机制实现的几种方法对系统可靠性的影响，以此作为主备倒换的设计基础。最后，利用有限状态机对基于n s r ( n o n - s 自叩r 0 u t i n g ) 的主备倒换机制进行描述。2 1 主各倒换实现机制分析完成可靠工作，即要保证系统的可靠性嘲，可靠性可以理解为实际的工作时间与要求的工作时间的比值。一般用m t b f ( m e 孤t i m eb e m e f a i l u r e ) 表示平均故障间隔时间，m 嗽( m e 狮t i m et 0r o v e r y ) 表示最长故障修复时间，m 兀 f ( m e 托t i m et of a i l u r c )表示平均无故障时间，且m t b f 吣仃1 r + m r r f ，那么可靠性公式为爿= 面元：；! ：善面，它们之间的关系如图2 ：失效点失效点平均故障间隔时问( m t b f )图2 可用性数值关系图由此可以看出必须使 肼尽量增长，而m t n t 尽量减短，即可保证系统的高可用性。那么m t t r 是：系统从出现软硬件故障到系统恢复故障继续正常工作之间的时间间隔。根据路由器的工作特点，这段时间分为以下三个阶段，即故障探测、主备倒换和恢复正常工作。研究的关键在于：首先，故障的探测时间要尽量短，以便及时发现故障；其次，备用主控从倒换后，各软件子模块从初始化到正常运行的收敛时间要尽量小，尽量接近无缝倒换。前者主要取决于系统的心跳探测及故障辨别能力，后者主要取决于故障恢复中涉及的诸多问题，例如状态信息的一致性，主控与单板的通信问题，以及各路由协议的重启能力。在主备倒换问题的研究上，比较关注三个问题：故障探测，状态信息备份，以及故障恢复，下面逐一进行介绍。2 1 1 故障探测机制分析第4 页信息工程大学硕士学位论文2 1 1 1h e a r t b e a t 的工作原理h e a r f b e a t 网络是双机冗余系统间故障探测的通道。简单跑说，系统通过心跳网络周期性进行问候信息交流。在系统正常工作情况下，备用处理器发送信息询问主用处理器的健康状况，主用处理器同样发送心跳探测包来确定备用处理器是否随时处于等待状态。当备用处理器在限定的周期内未收到主用处理器的探测包，则表明主用发生故障，它会自动接管主用处理器的p 地址和各种应用服务，成为新的主用处理器。当故障处理器恢复正常后，重新发状态信息给新的主用处理器，要求成为备用处理器。2 1 1 2h e a r m e a t 设计中的问题h e a r t b e a t 网络作为故障探测机制的基础，存在以下两点问题【7 j ：自身问题造成的误判主备双处理器的设计目的是为了避免s p o f ( s i n g l ep o i n to f f a i l u r c ，单点故障) 造成停机。而心跳线同样可以成为s p o f 。当处理器收不到对方的心跳信息时，故障原因分为两类，一种是主处理器软硬件的故障；另一种可能是心跳线路自身的故障。对于前一种情况确实应该触发主备倒换措施，而对于第二种情况会造成系统误判而进行主备倒换，主各处理器倒换必然要造成路由器短时间的异常工作。确定是哪种故障比较困难。 心跳周期难以设定作为判断故障的心跳模块自身必须可靠稳定，所以一般设计比较简单。对于心跳周期长度的设定一般采用人为设置，设置原则如下：在保证及时发现故障的前提下，探测的频率不应给系统造成多余负担。在实际应用中，如果周期过短，处理器要频繁处理心跳探测数据，影响了系统的效率。如果周期过长，在故障发生时，从处理器没有及时发现探测心跳未到达，而造成延误触发主备倒换。以上两个相互制约的因素都是设计故障探测机制要考虑的问题。2 1 2 状态信息备份机制分析主备用系统在工作中备份状态信息，可以大大提高对故障的恢复速度，备份机制【8 】分为批量备份、增量备份两种模式，下面逐一介绍他们的适用场合及性能：1 批量备份：这种备份方法一般使用在主用已经工作一段时间后，备用才启动。在这种情况下，由于主备之间的状态差异很大，需要在短时间内达到数据同步，必须将所有的状态信息进行备份。一般系统数据库中维护的各种物理设备的配置数据、接口状态数据以及各类路由转发表和内核中注册的虚拟驱动信息都应是批量备份的内容。由于数据量较大，所以采用批量备份的方法，由操作系统的调度机制来完成，所以不会影响主备倒换机制的性能。2 增量备份：在主备一起工作段时间后，主备用之间不存在大量状态不同步的现象，这时可以采用增量备份方式，即由主用的状态信息变化触发备份行为。根据备份的频率又可将增量备第5 页信息工程大学硕士学位论文份分为定时备份和实时备份两种方式： 实时备份：这种方式多用于状态信息变化不太频繁且通信量较小的情况下，主用实时地将状态变化通知备用。 定时备份：如果在主用状态信息变化相对频繁的时候采用实时备份，必定会给系统的通信模块带来负担，造成影响系统性能。所以在这种情况下多采用定时备份的方式。2 1 3 故障恢复机制分析2 1 2 1 故障恢复机制介绍( 1 ) 状态同步方式【9 】所谓状态同步，是指主备用主控间对路由状态信息的同步。如图3 所示，当主用主控路由状态发生改变时，就会利用内部报文通知备用，以达到主备用的信息一致。一般同步的信息包括系统的配置文件、路由数据库和接口状态信息等。但运行态的路由协议需要进行倒换时，需要重新与邻接建立连接，这会导致网络上流量的暂时中断。管理爰状杏信通知备用图3 状态同步机制示意图( 2 ) 路由协议平滑重启方式1 10 】如图4 所示，主用节点发生故障或升级需要重启时，通知邻居路由器进入h e l p e r 状态。如图5 所示，在主节点重启过程中，h e l p e r 状态下的邻居路由器会隐瞒重启事实，并在故障节点恢复后，通告更新消息，然后退出耻l p e r 状态，继续原先正常的工作。邻接点图4 路由协议平滑重启触发示意图第6 页信息工程大学硕士学位论文退邻接点图5 路由协议平滑重启恢复示意图平滑重启方式是为了解决如o s p f 、b g p 等路由协议设计时，把软件的错误当作链路故障处理的弊端，以保证在控制层故障的同时，数据层面保持不问断转发。但它应用的前提是邻接路由器均要支持相同路由协议平滑重启的功能，这也就造成了它使用的局限性。( 3 ) 数据复制方式f l l 】图6 数据复制机制示意图数据复制方案多应用于机群服务器系统，它要求主备主控同时运行相同的软件，由单板上报的数据会被复制，同时送往主备用系统中。对每个数据包，主备用均会做相同的处理，而备用会在底层发送端口丢弃回复报文。这样主备用就保持同样的运行状态，在倒换时也可达到无缝倒换，不中断任何工作。但最大的缺点是一旦主用故障，备用接替其工作后，主备系统间无法同步，主用难以恢复。2 1 2 2 故障恢复机制理论分析由于冗余结构主控系统的状态空间是有限的，属于连续时问状态离散随机过程【1 2 4 ”，根据文献【1 2 】中冗余系统故障转移图，本文将其中切入成功率的部分忽略，总结为图7 中连续时间的马尔可夫模型，用于分析上面三种故障恢复机制对可靠性的影响。状态定义如下：q o ( 无故摩状态) ：主备主控均正常工作；q l ( 单点故障状态) ：仅有一块正常工作的主控；q 2 ( 宕机状态) ：主备用均发生故障：q 3 ( 主备倒换状态) ：主用故障后，备用进入工作前的准备阶段。第7 页信息工程大学硕士学位论文2 u i c )图7 冗余结构马尔可夫模型其中九表示单块主控故障率，沁为主备倒换的时间分布率，表示单块主控恢复率，c 是故障覆盖因子，由于这里分析的是故障恢复模式对可用性的影响，所以忽略覆盖因子对可用性的影响，将其设为常量l 。只( f ) 表示系统q i 状态下的概率；a 表示系统处于q 2 状态以外的各稳定状态概率之和。下面具体进行计算：1 路由协议平滑重启：在这种方式下，由于有邻接路由器的保护，所以在主各倒换过程中，没有q 3 预备状态，状态转移如图8 ：2 pl i图8 路由协议平滑重启方式状态转移图根据图8 ，所得差分方程为：尸：o ) 2 2 织( f ) + 理0 )( 1 )只( f ) 2 2 织( f ) 一( 五+ ) 只( f ) + 胆( f )( 2 1尸- z ( f ) 2 鸩( f ) 一心( f )( 3 )根据( 1 ) ( 2 ) ( 3 ) 式，可知在路由协议平滑重启方式下，主控系统的可用性为：熙= 眦m ( f ) = 孝( 4 )2 状态同步：在状态同步方式下，由于备用系统中大部分进程必须在主备倒换时才能获得初始化的命令，所以必须经过q 3 状态的初始化准备后，备用才可取代主用进入正第8 页信息工程大学硕士学位论文常工作状态，如图9 ：图9 状态同步机制状态转移图根据图9 ，所得差分方程为：户t o o ) = - 2 五昂( f ) + ，以( f )p 。( f ) = 一( 五十力只o ) + ，以( f ) + 丸只( f )p ：( f ) = 鸩o ) 一芦f ：( f )p ，( f ) = 2 织( f ) 一 只( f )( 5 )( 6 )( 8 )根据( 5 ) ( 6 ) ( 7 ) ( 8 ) 式，可知在状态同步下，主控系统的可用性为：嬲= 删堋归历 筹兰知万c 3 数据复制：采用数据复制时，由于双主控状态始终保持一致，所以没用倒换状态q 3 ，但由于其对数据状态一致性的要求，一旦主用故障，则很难恢复到与备用相同的状态中，如果双主控均故障，是不可恢复的。如图1 0 ：p图1 0 数据复制机制状态转移图根据图l o ，所得差分方程为：p t 。( f ) = - 2 五矗( f )p ，( f ) = 2 允昂o ) 一犯( f ) + ，以o )根据( 1 0 ) ( 1 1 ) 式，可知在数据复制下，主控系统的可用性为：第9 页( 1 0 )( 1 1 )信息工程大学硕士学位论文舰4 ( f ) 2 只( ) + 只( f ) 2 焘( 1 2 )2 1 2 3 故障恢复机制的性能比较假设单块主控的平均无故障时问( m t b f ) 为1 0 0 0 h ，而平均故障修复时间( m t t r )为1 h ，那么系统的故障率五= 1 0 。，修复率= l ，单位均为| j i 。根据假设，单主控系统的可用性为4 = 面翕：；等面歹= o 9 9 9 0 0 ；通过路由协议平滑重启方式下的系统可用性为鸽：_ 二擘兰生：o 9 9 9 9 9 8 ；采用数据复制的冗余系统的可2 + 2 五“+ 口2靠性为以= = o 9 9 9 0 0 ，与单处理器系统可靠性一致；由于在状态同步环境中，系统“十倒换时间对可用性的影响至关重要，所以下面针对不同的平均倒换时间，比较几种故障 恢复方式对可用性的影响。、_ “弋、i ：啦、 一。o*i 埘枷枷枷- 埘倒基时同( 秒)图1 1 故障恢复机制性能对比图通过图1 1 可以看出，采用路由协议平滑重启的系统可靠性最高；状态同步方式下，如果系统倒换时间小于1 4 秒，依然可以保证5 个9 【6 】的可用性标准。以上结论为设计主备倒换模块中的故障恢复机制提供了理论依据，但路由协议平滑重启由于需要有邻居路由器的配合工作，不能像状态同步机制下的主备倒换这样具有良好的白愈功能。所以在设计时采用状态同步机制对路由表等信息进行备份，以提高倒换后路由的收敛速度。并结合设计灵敏的故障探测机制、实时文件备份机制完成最终的主备倒换设计。第1 0 页篙l l = l l = 一信息工程大学硕士学位论文2 2 主备倒换自动机设计在设计n f s m s ( m a i l l s t a l l d b y ) 主备倒换机制的过程中，由于其中具备诸多状态及复杂的转换关系，文章为了表述的严谨性，将冗余系统的工作过程抽象为自动机形式进行描述f 1 4 】。定义2 1 n s r m s 的任务自动机是一个五元组d 也t m ，= ( q ，万，吼，f ) ，其中：q = 吼，g l ，g ：，吼，g 。，吼，吼 ；= o ，l ；万为q 到q 的映射，具体如表l 所示；g 。为初始态状态；f = g 。) 。表1 操作状态机状态转移表操作( o 失败1 一成功)任务o1g og2叮lg l9 3g l哼2叮9 3g39 4叮lg49 69 59 5g l9 2，、图1 2 操作状态转移图q 操作任务集的含义及具体流程如下：吼：初始化状态；9 1 ：心跳探测；口：单主控工作；吼：失效判断；g 。：主备倒换；g ，：原主用重启；吼：系统故障。第“页信息工程大学硕士学位论文( 1 ) 在吼初始化过程中，创建三个线程： 线程1 ( 鹏一n e i g o _ t h r e a d ) ：建立两块主控板之间用于主备协商和心跳探测的u d p 连接，并进入主备协商阶段，确定主备关系；线程2 ( 眦_ i n t e r f a c e t h r e a d ) ：创建与其他模块之间通信的接口，用于维护传输数据所用的消息队列； 线程3 ( m s - b a c k u p _ t h r e a d ) ：建立两块主控板之间用于文件备份的t c p 连接。( 2 ) 吼心跳探测过程：路由器正常启动后，除了运行路由器正常工作时的各种应用程序以外，m a i n 与s t a n d b y之间定时互相发送k c e p a j i v e 报文以便通过软件诊测方式实时发现对方主控是否故障。然而由于备用的故障不会影响系统的正常运行，所以在主备心跳探测失败时，应区分处理：m a i n 在心跳探测失败时，启动死亡判断定时器，定时器到期启动失效判别机制，确定备用失效，则进入单主控工作模式。s t a l l d b y 在心跳及死亡判别定时器均到期后，如果未收到来自m a i l l 的报文，那么进行故障判断。若认为主用失效，则检查备用此时的状态，若为s t 柚d b y 则可进入主备倒换。( 3 ) 进入玑单主控工作有三种情况，即： 在初始化时主备协商或者用于文件传输的t c p 连接建立失败；主用工作中探测到备用故障； 主备倒换后，主用发生严重故障，无法重启。( 4 ) 失效判断：在备用心跳探测失败后，不能直接判断为主控失效，因为有可能出现心跳链路的拥塞造成心跳报文丢失的情况。针对这种干扰，设计失效判断机制：进行一次主用身份确认的过程，该过程与主备协商类似，仅在协商报文中指出自己的备用身份，等待主用的协商确认报文。如果由于心跳网络拥塞所致，而并非主控故障的情况，如图1 3 所示：第1 2 页信息工程大学硕士学位论文图1 3 主用丢失心跳报文的处理过程( 5 ) g 。主备倒换过程，是系统的处理关键，具体过程如图1 4 ：( 6 ) 在主备倒换后，故障处理器进入9 5 重启阶段，并在主备协商后进入备用状态。若重启失败，则进入玑单机工作状态。( 7 ) 在单机故障或者主备倒换失败发生时，进入系统故障终结态吼。2 3 本章小结本章在对路由器主备倒换关键技术中故障探测、故障恢复及状态备份机制进行介绍和理论分析。利用连续时间马尔可夫链分析几种故障恢复方法对可用性的影响，以比较结果作为对主备倒换设计的理论基础。最后，设计主备倒换操作自动机，并对各种具体操作过程进行功能描述。第1 3 页信息工程大学硕士学位论文图1 4 主备倒换流程图第1 4 页信息工程大学硕士学位论文第三章基于v i 沁思想的多机架协同工作机制设计在对多机架互联组网模式的可靠工作机制设计中，借用v i t r p 协议思想，通过多机架冗余工作，减小单个处理节点的负载，避免单点故障造成系统失效，保证a c r s 系统的可靠工作。基于这种设计，本章针对协同工作中的两个关键问题进行研究：1 如何解决由于分布式路由处理造成的各节点路由表不一致问题；2 启动的各单板接口必须映射到一个主控上，并通过相应的设备驱动完成注册、接收、发送等工作，如何保证设备层次视图的一致性。本章分别针对这两个问题，提出了一种结合哈希函数的路由表同步算法，并且设计了解决接口管理视图一致性的方法。3 1 基于u r p 协议的设计思想3 1 1 虚拟路由器冗余协议t r p 协议是t f 为实现局域网的可靠性而设计的标准解决方案【1 5 1 6 1 ，该协议利用一组冗余路由器( 由主用路由器和其他备份路由器组成) 实现对默认网关的保护。如果主用路由器失效，则由备份路由器中优先级最高的接替其工作。v 砌冲结构是为了在静态默认路由环境中排除单点故障而设计的。一个虚拟路由器有两个以上的运行、1 u 心的路由器组成。被用于唯一标识这组路由器，也就是虚拟路由器，他们对外表现为一个v p ( 虚拟口地址) 。主用路由器工作正常时，负责所有与外界网络的转发工作。一旦主用路由器失效，则备用路由器组中优先权最高的备用路由器将接替它工作。由于这种倒换非常迅速而且不用改变口地址和m a c 地址，在发生故障时虚拟路由器地址没有改变，主机仍然保持与其连接。因此更换网关对终端使用者是透明的，网络将不会受到单点故障的影响。图1 5 v r l 冲协议工作示意图如图1 5 所示结构1 + l 虚拟冗余路由器，所有的网络负载都由路由器r 1 来承担。如果r 1第1 5 页信息工程大学硕士学位论文有故障，那么虚拟路由器v r 中的备份路由器r 2 将接替主用路由器r l 的工作，开始转发原来由r l 转发的数据。u 啦协议保证r 2 使用虚拟路由器v r 的虚拟m a c 和m 地址。在下层的终端用户完全感觉不到倒换的改变。虚拟路由器中的节点数也可以扩展到n 个【1 7 】，并且独立进行工作且彼此互为冗余。这种模式与a c r 多机架组网后，主控与单板之间的通信模式很相似。下一小节将介绍a c r的内部通信网。3 1 2 基于v 褂冲设计思想的提出在a c r 路由器硬件结构中，中央控制平面与数据平面各单板呈现c s ( c l i 钮蜷e r v e r ，客户机服务器) 的模式，通过内部通信网进行连接。当单板收到协议报文需要上交主控进行处理时，采用u i ) ps o c k c t 传输方式。即在路由器初始化阶段，各单板与主控通过p 进行连接，并以不同端口号区分业务类型。图1 6 a c r 路由器各处理单元拓扑结构基于a c r 控制和转发平面的c s 通信模式与i r p 协议应用的默认网关用户结构具有相似性的特点，我们考虑在这种结构中利用v 雕冲协议的可靠性保护思想，使所有控制单元组成多个虚拟处理单元。为了使故障时，控制单元的倒换对单板是透明的，需要在内部通信网络中加入口接管( pa d d r e s st a k v e r ) 技术：既某个处理单元故障时，它的口由虚拟组中备用主控进行接管，由于内部通信网不使用m a c 进行通信，所以在接管后，不需要重新建立连接。3 2 分布式路由一致性算法随着路由器体系结构由集中控制向分布式结构发展，路由器内部处理节点也相应增加，这就会产生各内部节点间路由不一致性问题。3 2 1 现有路由一致性方法介绍具体来说，不一致一般出现在控制节点与转发节点之间或者控制节点与控制节点之间。针对这两种情况的解决方法也可总结为两类，对于前者一般采用广播更新方式，对于后者一般采取冗余备份方法。下面分别进行介绍：1 广播更新方法第1 6 页信息工程大学硕士学位论文传统集中式路由平台，它由一块主控板实现所有路由计算，网管配置管理，以及负责与邻接路由器进行更新或交换路由信息。各路由协议通过计算形成本地路由表，再通过一个权衡模块统一整合成全局转发表，最后通过广播更新的方式通知转发平面的各转发板。在这种模式下，主控板的处理能力将成为系统性能的瓶颈，并存在单点失效的不可靠隐患。但这种同步方法只有在全局转发表发生改变时，才会通告被动转发节点，所以在理论上是最优的一致性方法。2 冗余备份方法冗余备份方法【1 7 - 19 】是应用于多路由处理节点的环境下，例如图1 7 中：o s p f 协议分布在处理节点l 和3 上；r 口协议分布在处理节点l 和2 上，i g m p 协议分布在处理节点l和2 上；b g p 协议分布在处理节点1 和3 上；而处理节点4 没有参加路由计算、不会产生影响路由表变化的信息，它只承担报文的转发工作。图1 7 多处理节点冗余备份拓扑图在路由器工作过程中，各处理节点的路由协议在与邻接路由器通告、交换路由信息过程中，修改本地的转发表，由于不存在集中处理器