（计算机系统结构专业论文）分布式并行多出口路由器的qos研究与实现.pdf

摘要 摘要 随着网络技术的发展和各种网络应用的涌现，使网络服务质量受到了前所未 有的关注，研究人员也发现单纯增加带宽并不能完全解决服务质量问题。鉴于此， 目前涌现出了多种服务质量的解决方案，包括区分服务模型、集成服务模型和 m p l s 多协议标签交换等。而路由器作为网络服务质量问题的关键器件，它的性能 将直接影响全网络的服务质量高低。 本教研室开发的基于l i n u x 软件平台和x 8 6 体系通用硬件平台的分布式并行 多出口路由器系统，它定位于网络接入路由器，具有高性能、高可靠性、低成本 和可扩展性好的特点。该路由器系统在服务质量上已经实现了基于区分服务模型 的优先级队列转发管理，而为了迸一步提高系统的服务质量和可靠性，也要求在 出口选择时充分考虑多个出口间的流量均衡；同时，在进行用户优先级管理时， 还要求在服务质量的可用性指标上得到保证。 本文首先简单分析了服务质量的技术指标和现在的研究发展状况，然后结合 当前网络的实际特点，在充分考虑了二级网络运营商所处的运营环境，和教研室 现有的分布式并行多出口路由器的基础上，进一步对出口选择方案进行了优化设 计，旨在改善该系统作为接入路由器产品的服务质量，提高它的性能。 随后本文也详细描述了本路由器服务质量系统中的高可用性的优先级用户管 理系统，包括它的关键技术及其解决方案。该方案对于其它使用优先级队列的q o s 系统也具有积极的启发意义。 关键词：路由器，分布式并行，多出口，服务质量 a b s t r a c t a b s t r a c t a st h ed e v e l o p i n go f i n t e r n e ta n dt h er u s ho f v a r i o u sa p p l i c a t i o n so v e rt h en e t ，t h e q u a l i t yo fs e r v i c e ( q o s ) h a sb e e nr e c e i v i n ga nu n p r e c e d e n t e dc o n c e r n r e s e a r c h e r s c o g n i z e dt h a ti tc o u l d n tr e s o l v et h ep r o b l e m sa b o u tq u a l i t yo fs e r v i c ec o m p l e t e l y m e r e l yb yw i d e n i n gt h eb a n d w i d t h o w i n gt ot h i ss i t u a t i o n ，m u l t i p l es o l u t i o n sa p p e a r c u r r e n t l y , w h i c hi n c l u d e sd i f f s e r v em o d e l ，i n t s e r vm o d e l ，m p l sm o d e la n d s oo n a sa p i v o t a lp a r to fn e t w o r k s ，r o u t e r s p e r f o r m a n c ew i l la f f e c tt h eq u a l i t yo fs e r v i c eo ft h e w h o l en e t w o r kd i r e c t l y t h ed i s t r i b u t e d p a r a l l e lm u l t i - p o r t r o u t e r s y s t e md e v e l o p e db y 8 0 1 0 r e s e a r c h - r o o mh a st h ec h a r a c t e r i s t i c so f1 1 i g hp e r f o r m a n c e ，h i 曲r e l i a b i l i t y , h i 曲 s c a l a b i l i t ya n dl o wp r i c e ，w h i c hi sb a s e do nl i n u xo p e r a t i o ns y s t e ms o f t w a r ep l a t f o r m a n dx 8 6g e n e r a l - u s i n gh a r d w a r ep l a t f o r m t oi m p r o v et h eq u a l i t yo fs e r v i c ea n dt h e r e l i a b i l i t yo ft h es y s t e m ，t h el o a db a l a n c eo fi t sm u l t i p l ep o r t ss h o u l db ec o n c e m e d c a r e f u l l y a tt h es a m et i m e ，i ti sr e q u e s t e dt oa s s u r et h eu s a b i l i t yo ft h er o u t e rs y s t e m w h e nt h em a n a g e m e n to f u s e r s p r i o r i t yi sp e r f o r m i n g t h et e c h n i c a li n d e xo f t h eq u a i 畸o f s e r v i c ea n dt h ea c t u a l i t yo f r e s e a r c ho i lr o u t e r s y s t e ma r ea n a l y z e df i r s t l yi nt h i st h e s i s ，a n dt h e ni to p t i m i z et h ea l g o r i t h mo ft h ep o r t s e l e c tt oi m p r o v et h eq u a l i t yo fs e r v i c ea n dt h ep e r f o r m a n c eo f t h es y s t e m t h i st h e s i sa l s od e t a i l st h em a n a g e m e n to f t h eu s e r s p r i o r i t yr u n n i n go nt h i sr o u t e r s y s t e m ，i n c l u d i n g i t s k e yt e c h n i q u ea n di t ss o l u t i o n s ，w h i c hm i g h t h a ss o m e i l l u m i n a t i o n st oo t h e rm a n a g e m e n to f q o sb a s e do np r i o r i t y q u e u e k e yw o r d s ：r o u t e r , d i s t r i b u t e dp a r a l l e l ，m u l t i - p o r t ，q o s i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名： 日期：d 6 年月厂日 i 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：二越砼导师签名：盔! 叫这一一 ，1 日期：d 6 年 月) 日 第一章引言 第一章引言 互联网络发展到今天早已超出了当初a p p a n e t 发起者们的最初构想，在互 联网上涌现出来的各种应用也远远超出了上个世纪任何组织或个人的最乐观估 计。自上个世纪八十年代以来，由于微电子技术的突破，使得芯片资源呈现出了 爆炸性的发展，以i n t e l 为代表的芯片厂商不断推陈出新，更新换代；在此基础上， 以m i c r o s o f t 为代表的软件厂商紧紧紧跟上，使计算机软件的处理能力越来越强大， 以前很多必须用专用硬件设备才能实现的功能，现在很多已经转为全由软件在通 用硬件平台上实现，而其中很有代表性的一种设备就是本文要讨论的路由器。另 一方面，由于光通信技术的突破，也使得过去的带宽瓶颈有了很大程度的改善， 很多以前必须在专用网络上才能享受到的昂贵服务，现在也进入了寻常百姓家。 然而，现实总是落后于理想的，越来越多的复杂应用对因特网带宽也提出了越来 越高的要求。人们终于发现，带宽并不是解决问题的全部，所有当前以及未来可 能的潜在应用实际上是对服务质量( q o s ：q u a l i t yo fs e r v i c e ) 有所要求，这是本 文要讨论的重点。下面先对路由器和服务质量作一些简单陈述。 1 1 路由器概述 路由器按照连接的网络级别可以分为骨干路由器、内部路由器、接入路由器 三个大类。其中骨干路由器通常用于连接长距离骨干网上的i s p ( i n t e m e ts e r v i c e p r o v i d e r ) 或企业网络的接入路由器，它要求有快速的物理网络接口和包交换能力， 路由器之间通过复杂的路由协议和算法进行信息交换来获取选路信息。内部路由 器通常位于企业局域网或者校园网内部，实现对局域网的划分和路由功能。而接 入路由器一般位于网络边缘，主要负责把端用户和小单位连接到网络服务商，通 常这种路由器有一个内网接口连接到企业内部网络，有一个或多个外网接口，连 接一个或多个接入服务商。它的主要流量就是来自内网接口而传向外部接入服务 商服务器或者由外网站点到内网接口并最终流向内部各个主机的，而它的外网接 口之间一般没有流量产生。这种路由器是本论文讨论的重点对象。 目前市面上大多数的接入路由器都采用硬件路由器。它们一般采用专用芯片 和专用硬件体系结构来实现，稳定性高，可靠性好，速度快，功能也很强大。但 电子科技大学硕士学位论文 同时它们的价格一般比较比较昂贵，开发周期一般较长，而且灵活性也较差，对 它们的操作一般需要专业培训人员来进行。 由于接入路由器连接的内部网络结构相对较为简单，因此接入路由器也常采 用软路由来实现。此时，它们由连接多个网络并运行相应的路由选择软件的计算 机组成，很多时候可以直接采用通用的计算机硬件平台和w i n d o w s 操作系统。这 种路由器开发周期短，配置简单，而且用户可以根据自己的实际需要灵活的增加 软件功能模块，对它们的操作也可以由普通技术人员来完成。但是，由于w i n d o w s 操作系统为了解决用户接口的友好性问题而同时运行了很多图形界面的进程；而 作为一个路由器，通常一旦设置好以后，并不需要很多的操作和修改，此时图形 子系统由于仍要占用大量资源反而成了性能的障碍，并且也导致了性能的不稳定。 另一方面，由于仅由单台p c 构成，也没有完善的故障检测和容错机制，一旦该节 点出项故障，将会导致整个网络连接瘫痪，可能造成重大损失。同时，由于w i n d o w s 仍然是作为商业软件来发行的，它的很多技术细节的实现也无从得知，要在此之 上作二次开发有很大的难度。故这种路由器一般速度较慢，可靠性和稳定性相对 较差，它一般只适用于对少数几台计算机进行组网的家庭用户。 l i n u x 操作系统的出现使得软路由的发展进入一个新的阶段。l i n u x 系统可以 认为是u n i x 的一个变种，它的很多设计思路都是直接参考了u n i x 的实现，而u n i x 系统的高可靠性和稳定性已经在它面世后的二十多年里得到了充分的考验和验 证；另一方面，路由转发以及相关的管理、配置功能是l i n u x 内核支持的功能之一。 同时，l i n u x 提供完整的源代码，便于研究它的具体实现过程，更进一步，可以直 接修改它的源代码以实现二次开发。因此，l i n u x 操作系统是目前很好的软路由软 件平台。 1 2 分布式并行多出口路由器原理 如果仅仅直接使用通用l i n u x 系统及其系统自带的路由模块，由于网络的接 入点仅由一台系统承担，此时无论从性能上还是可靠性上都还是远远低于专用硬 件系统的接入路由器，仍然不能越过单节点失效造成的低可靠性瓶颈。因此我们 采用了分布式体系结构来构造基于通用硬件p c 平台和l i n u x 软件平台的高速高可 靠性的接入路由器一分布式并行多出口路由器( d p m r ：d i s t r i b u t e dp a r a l l e l m u l t i p o r r o u t e 0 ，该系统的连接拓扑图见图1 1 所示。 2 第一章引言 图1 1 分布式并行多出口路由器连接拓扑图 从图中可以看出，一组并行工作的节点( 路由器l 到路由器3 ) 彼此协商进 行节点间的任务分配以实现负载的均衡；同时，节点间定时进行相互检测，以实 现单节点失效后的负载自动重新分配。i s p l 到i s p 3 是用户购买的多个i s p 服务商 的出口，并且由系统自动在这些出口上进行带宽分配，以达到合理利用出口带宽 资源，节省费用的目的；另一方面，当一个出口出现故障时，系统也可以自动进 行出口流量的调整，而且这种调整对内网使用者是完全透明的，通过这种方式也 提高了系统的可靠性。实践证明，此时的接入路由器系统无论从可靠性还是速度 等性能上都能满足二级i s p 接入商的需要，而由于采用了通用硬件系统以及软件 平台，因此在价格上更具有无可比拟的优势。 1 3i p q o s 产生背景 直到上世纪九十年代初期，i n t e r a c t 也只能提供网络层面上的点到点的尽力传 电子科技大学硕士学位论文 送的数据报服务，很大程度上这是由于当时i n t e m e t 上的主流应用局限于f t p 、 t e l n e t 以及h t t p 等简单业务。此时的网络无论是用户还是所能提供的应用都 非常稀少，而对传输有明确质量要求的应用往往都通过专用网络方式进行，因而， 尽力传送能够满足当时的绝大多数在i p 网络上应用要求。此时i n t e m e t 在控制层 面上的资源管理机制仅仅被用于建立动态路由。然而，当网络功能从单一发展到 多样，而且单机的处理能力也日益强大，口网络也随着通信技术的发展蒸蒸日上 的时候，此时的i p 网络完全有能力进行从简单的文件传递等简单服务到远程教学、 视频会议、网络游戏、网络语音传输等复杂业务。遗憾的是，i p 网络由于历史的 原因仍然采用了不加区分和限制以及完全“一视同仁”的尽力服务，此时就已经 远远不能满足用户以及应用所要求的在专用网络中所能得到的可靠性和稳定性等 服务质量要求了。 诚然，增加带宽是口网络可持续性发展的必要条件和提高网络服务质量最直 接的方法。然而，随着网络用户的几何级数增加以及网络应用的不可预见性，学 者们也逐渐认识到增加带宽并不是提高因特网服务质量的充分条件。从另一个方 面来看，以现今的网络基础建设技术来讲，提供给每一个潜在用户以足够的带宽 显然也是不经济和不现实的。正是在这种背景下，服务质量( q o s ：q u a l i t yo f s e r v i c e ) 问题受到了广泛的关注。 1 3 1 网络服务质量的相关参数 q o s 是指网络在传输数据流时要求满足的一系列服务请求及实现这些请求的 机制。这些服务请求可以用以下几个指标来衡量：带宽要求、传输延迟、延迟抖 动、可靠性、丢失率、吞吐量等，下面给以简单说明。 带宽要求，主要是指具体应用在平稳运行时所固定需要的带宽。不同的应用 往往有着不同的平稳带宽要求，而且这种要求也是和资源分配策略相关的。比如 对于文件传输而言，它没有最大值要求，此时，所分配的带宽和用户得到的服务 质量成正相关关系；但对于视频传输而言，当所分配带宽达到系统所要求的值后， 此时再继续增大带宽也不能提升服务质量。 传输延迟，是指数据包由主机发送出去，经过网络传输最后到达目的主机之 间的时间。很多时候在讨论q o s 问题时只讨论网络传输上的延迟，而不考虑数据 在从发送主机到提交给网络，以及在到达目的主机后由于主机系统负载等原因而 造成的交付到应用的延迟。产生时延的因素很多，包括分组时延、排队时延、交 4 电子科技大学磺士学位论文 送的数据报服务，很大程度上这是由于当时i n t e m e t 上的主流应用局限于f t p 、 t e l n e t 以及 r r r p 等简单业务。此时的网络无论是用户还是所能提供的应用都 非常稀少，而对传输有明确质量要求的应用往往都通过专用网络方式进行，因而， 尽力传送能够满足当时的绝大多数在i p 网络上应用要求。此时i n t e r n e t 在控制层 面上的资源管理机制仅仅被用于建立动态路由。然而，当网络动能从单一发展到 多样，而且单机的处理能力也日益强大，邛网络也随着通信技术的发展蒸蒸日上 的时候，此时的i p 网络完全有能力进行从简单的文件传递等简单服务到远程教学、 视频会议、网络游戏、网络语音传输等复杂业务。遗憾的是，i p 网络由于历史的 原因仍然采用了不加区分和限制以及完全“一视同仁”的尽力服务，此时就已经 远远不能满足用户以及应用所要求的在专用网络中所能得到韵可靠性和稳定性等 服务质量要求了。 诚然，增加带宽是d 网络可持续性发展的必要条件和提高网络服务质量最直 接的方法。然而，随着网络用户的几何级数增加以及网络应用的不可预见性，学 者们也逐渐认识到增加带宽并不是提高因特网服务质量的充分条件。从另一个方 面来看，以现今的网络基础建设技术来讲，提供给每一个潜在用户以足够的带宽 显然也是不经济和不现实的。正是在这种背景下，服务质量( q o s ：q u a l i t yo f s e r v i c e ) 问题受到了广泛的关注。 1 3 1 网络服务质量的相关参数 q o s 是指网络在传输数据流时要求满足的一系列服务请求及实现这些请求的 机制。这些服务请求可以用【三【下几个指标来衡量：带宽要求、传输延迟、延迟抖 动、可靠性、丢失率、吞吐量等，下面给以简单说明。 带宽要求，主要是指具体应用在平稳运行时所固定需要的带宽。不同的应用 往往有着不同的平稳带宽要求，而且这种要求也是和资源分配策略相关的。比如 对于文件传输而言，它没有最大值要求，此时，所分配的带宽和用户得到的服务 质量成正相关关系；但对于视频传输而言，当所分配带宽达到系统所要求的值后， 此时再继续增大带宽也不能提升服务质量。 传输延迟，是指数据包由主机发送出去，经过网络传输最后到达目的主机之 间的时问。很多时候在讨论q o s 问题时只讨论网络传输上的延迟，而不考虑数据 在从发送主机到提交给网络，以及在到达目的主机后由于主机系统负载等原因而 造成的交付到应用的延迟。产生时延的因素很多，包括分组时延、排队时延、交 造成的交付到应用的延迟。产生时延的因素很多，包括分组时延、排队时延、交 4 第一章引言 换时延和传播时延。 延时抖动，是指同一对端点之间传输的数据流，由于采用了不同的路径或者 即使采用了相同的路径，但由于网络负载的变化而造成的传输时延的变化。某些 业务类型，特别是语音和视频等实时业务，对时延参数有严格的要求，因为太大 的分组到达时间差异将会造成语音和视频的断续。所有传送系统都有抖动，只要 抖动落在应用许可的范围之内就不会影响服务质量。 可用性要求，有时也被称作可靠性要求，是指当用户需要时网络即能工作的 时间百分比，它主要依赖于设备的可靠性和网络的存活性。当然也还有一些其他 因素，包括软件稳定性以及网络硬件等系统升级时不中断服务的能力，以及建立 时间和保持时间等因素。 丢失率，是指数据传输时的发送方所发送的数据包经过网络传输后，达到目 的主机后所丢失的数据包的百分比。由于传统i p 网络在数据传输时只是尽力服务， 因此在此过程中可能会因为多种原因( 一般是因为拥塞或者主动流量控制引起的) 而使路由器或者交换机直接丢弃所接收到的数据包。在另一方面，网络传输过程 中仍然可能存在差错，此时将发生因为比特丢失最终引发包错误而丢弃数据包。 吞吐量，通常是指网络中数据包的传输速率，是在一定时间段内对网上的总 流量( 或带宽) 的度量。一般讲，吞吐量越大认为服务质量越好。 i p 网络q o s 研究的目标就是有效提供端到端( e n d - t o e n d ) 的服务质量控制和 保证。q o s 并不能增加带宽资源，也不能提高网络主机的运行速度，它只是根据 不同业务的具体需要和网络的管理来配置网络资源，使网络资源的利用最优化， 实现服务提供商的利益最大化。 1 3 2 不同的网络应用和客户对服务质量参数有不同的需求 网络的存在源于网络所支持的各种应用。没有纷繁复杂的各种网络应用，网 络的存在和繁荣就缺少持续长久的驱动，也就没有存在的价值。因此可以说，是 网络应用在刺激着网络新技术的产生，或者说是网络用户驱动着网络的发展。 不同的网络应用有着不同的运作模式，对网络服务的需求也不尽相同。网络 应用可以参照两种分类标准进行分类，其一是按照应用数据流的速率来分为流数 据和突发数据两类。对流数据，其传输速率可估计，且是相对连续的数据流，它 们的传输速率通常有上限，此时即使再增加给它们分配的带宽也不能明显提升它 们的服务质量。通常的语音和视频数据流就是此种类型。而对于突发数据，它们 电子科技大学硕士学位论文 的传输速率不可估计，也通常无上限要求，且它们的传输行为离散，一般无法预 测和估计。通常的文件传输就是此种应用，此时它们的传输速率和它们所能获得 的网络资源有关。 另一种分类方式可以按照应用对网络时延的承受能力来进行分类。可以分为 如表1 1 所示的五类： 表l l 以传输时延的敏感性对应用的分类表 时延承受能力传输类型描述典型应用 高 异步对时延基本无要求电子邮件 对传输时延敏感，但有 同步文件传输 很大的弹性。 交互 对传输时延敏感，但不 l 会影响到可用性。 在线聊天 要求传输时延必须限 制在一个可接受的范 等时i p 电话，视频会议 围内，否则会严重影响 可用性 传输时延大于一个临 低 临界界值时则认为系统不远程实时监控 可用 从表中我们也可以看出，不同的网络应用对于服务质量的时延指标都有着不 同的理解，因此我们不能简单的认为不断的提升带宽资源就一定能满足它们的需 求。从运营商和网络实际用户的角度出发，他们总是希望只购买最少的带宽，而 能够满足他们最主要的业务需求。因此提高网络效率，降低网络成本，按照不同 用户的实际应用对服务质量的不同要求，提供多种有区别的服务，才能提高用户 的满意度，同时提高网络运营商的收益和降低客户的网络使用成本，这才是网络 q o s 问题的现实可行的解决之道。 1 4q o s 不仅仅是网络转发的问题 通常我们讨论q o s 问题的时候，更多的是将焦点集中于网络传输环节里的各 6 第一章引言 个中转设备上，然而，q o s 最本质的目的还是为了使网络能够满足通过它传输数 据的应用程序各自的诸如传输时延、抖动等基本需求。因此，q o s 从本质上就是 一个从一台主机的应用程序端到另一台主机的应用程序端的问题，它还需要两端 的操作系统以及之上的应用程序也提供对应的q o s 支持。签于此，本节将初步讨 论一下端到端的q o s 所需要的操作系统和应用程序的支持。 我们现在所使用的操作系统，无论是像w i n d o w s 系列的个人桌面操作系统， 还是像u n i x 系列通常用于服务器的操作系统，一般都是多用户多任务的操作系统， 其上可能都同时运行着若干用户的应用程序以及若干系统支持进程，这些应用程 序和进程共享着同一个网络硬件和协议支持服务进程。很自然的，和在网络中的 数据转发一样，它们也存在对网络数据的优先级识别以及向上一层转发的问题。 另外，操作系统还必须在包括c p u 资源在内的其它本机系统资源分配层面上也全 面支持q o s 。因此，操作系统必须具有q o s 需求转换、接纳允许控制和q o s 需求 维护功能，对q o s 动态变化的应用还必须提供对应的q o s 实时更新功能。 q o s 的需求转换将应用程序的q o s 需求，转换为对各种系统资源的需求并进 行实际的参数化。接纳允许控制根据应用程序所提出的需求和当前系统资源的利 用情况，确定系统是否能够满足应用程序的需求，据此决定允许，或者拒绝应用 程序进入系统。资源预留是指为即将运行的应用程序保留资源，如c p u 、磁盘f o 、 网络带宽等，以保证该应用程序的q o s 需求。资源预留除了在本机上进行外，也 还包括由操作系统( 透明或不透明的) 向应用程序所提供的进行到另一端的沿途 所需资源进行预留协商的方法，通常它们是可由应用程序显示调用的a p i 。资源调 度和q o s 维护是为已投入运行的应用程序动态地分配资源。资源调度算法的设计 和进程的调度算法有点类似，其最终目的就是使资源的利用率最高，只是这里的 资源除了c p u 外，还包括网络带宽资源等。 因此，一个支持应用程序q o s 要求的操作系统的相关层次结构可以简单的如 图1 2 所示。 详细的讨论操作系统的q o s 支持已经远远超出了本论文的范围，通常我们只 讨论网络的q o s 问题，且把重点放在路由器的q o s 保证上。这是因为，对路由器 的q o s 控制可直接实现对各个业务流在网络传输中所占用的共享资源控制，而且 路由器的性能也直接关系到网络传输性能，所以路由器q o s 问题成为解决网络q o s 的关键。 下面简单陈述一下目前路由器q o s 的研究进展。 电子科技大学硕士学位论文 叵圈圈圈 困曰圈 图1 2 支持q o s 的操作系统层次图 1 5 路由器q o s 的研究现状 目前，路由器q o s 的研究成果主要是提出了三种体系结构，它们是i n t s e r v 集 成业务、d i f f s e r v 区分服务、m p l s 多协议标签交换。由于本课题是基于已经建立 了区分服务模型的路由器之上的，因此稍微详细的讨论一下区分服务模型，而对 其余两种则仅做系统介绍。 i n t s e r v 集成业务是由i e t f 在1 9 9 4 年提出的，它的基本思想就是在具体应用 启动之前，必须先向网络发送它的资源需求信息，在得到肯定的答复后应用再进 行数据传输。同时它要求网络传输过程中的各个中转单元一直保留这些资源，直 到应用主动撤销或者超时无响应后被动撤销。集成业务通过资源预留协议( r s v p ： r e s o u r c er e s e r v a t i o n p r o t o c 0 1 ) 来进行资源请求和保留的相关信令交换。 d i t p s e r v 区分服务采用边缘监管、分配以及业务优先级划分的方式，来满足 不同应用和用户对q o s 的需要。其基本思想是在网绍入口处，通常是在网关处或 者接入路由器上，根据用户和因特网服务提供商的服务等级协定s l a ( s e r v i c e l e v e la g r e e m e n t ) ，为该用户的应用所产生的分组分配一个区分服务码d s c p ( d i f f s e r vc o d ep o i n t ) ，同时它自己填写i p v 4 报头中未用的t o s ( t y p eo f s e r v i c e ) 域以及i p v 6 报头的t c 域，将此g 位定义为六位的d s c p 字段，余下两位不用。 这样每个数据包自身就携带了6 位的优先级信息，当它们在网络中被转发时，路 由器可以根据该优先级信息来进行排队和优先转发，具有相同d s c p 值的数据包 8 第一章引言 得到相同的处理。 区分服务实现了对应用的透明，不需要用户的参与，而且对数据包的分类和 流量调节由边缘路由器来完成；而对于核心路由器，只需要根据每个分组携带的 d s c p 信息来进行排队转发即可，因而不会加重核心路由器的负担。同时它不需要 每个路由器保留流的状态信息，因而具有很好的网络扩展性和伸缩性。然而，由 于d i f f s e r v 只是定义了服务优先级，而且现在也并无d s c p 的普遍标准，当网络 上存在大量的高优先级业务时，它并不能真正保证端到端的q o s 。同时也可以看 出，此种方式进行的区分服务，是以用户为粒度进行的，对于一个拥有高优先级 的用户来讲，无论他的任何应用所发出的数据包都将分配到高优先级的d s c p 区 分码，即使他进行的只是简单的电子邮件应用。因此这种方式也造成了一定的资 源浪费，需要和更细粒度的以实际应用来划分的区分服务相结合。 从对区分服务模型的流程分析中可以看出，它在正常工作之前必须由管理员 先建立起优先级用户数据，然后它才能据此判断数据包的所属的优先级，进而进 行相关的队列管理。更重要的还在于，对于一个商业化运作的路由器，为了不影 响它的可用性服务质量指标，还要求这些优先级用户数据能够随时在不中断服务 的前提下得到修改，比如增加用户、删除用户、更改用户优先级等等操作。 多协议标签交换m p l s ( m u l t i - - p r o t o c o ll a b e ls w i t c h ) 的基本思想是将二层 快速交换和三层相对慢速的路由有机结合来提高路由器的转发性能。在m p l s 中， 每一个分组在到达网络入口处的接入路由器的时候，路由器建立到目的网络的标 签映射，并将网络层的路由信息直接映射到数据链路层的交换路径上，进而建立 起网络层上的标记交换路径l s p ( l a b e ls w i t c h p a t h ) 。此后该分组在流经其它路由 器的时候，标记交换路由器只需根据它所携带的标签进行标签切换，用出标签替 换入标签，再将分组转换给下一跳路由器。此时，分组在转发之前就已经确定了 一条源端到目的端的路径l s p ，它由源主机到目的主机之间的中间节点序列组成。 从上面三种模型可以看出，它们主要都集中于解决核心路由器的服务质量问 题，且把重点放在解决传输时延。然而，正如前面所说的，q o s 还包括很多指标， 而对不同的路由器，由于它们的主要功能和它们在整个网络拓扑结构中所处的位 置不同，因而也对这些指标有不同的侧重点。 1 6 不同的路由器有不同的q o s 问题 对于核心以及内部路由器而言，其q o s 问题指的是为所传输的服务选择一个 9 电子科技大学硕士学位论文 满足其服务质量要求的路径，同时也要求使网络资源的利用率最大。在选择路径 的过程中，涉及到两个问题，一是选择哪些度量参数作为寻路标准；另一个是在 寻路标准确定后，如何找到满足业务需求的路径并保证数据按照所选定的路径传 输到目的节点。不同的寻路标准，也就决定了路由器间需要交换的信息。在传统 路由器中，如果简单的以跳数作为寻路标准，此时以r i p 协议进行简单路由信息 交换即可；如果加入路径延迟等参数，则应该以更复杂的o s p f 协议来交换更多的 网络信息。然而如果要支持q o s ，则路由器之间需要交换更多的信息，包括诸如 当前带宽使用状况等等。 而对于接入路由器而言，它的主要作用就是进行地址转换和内外网的数据转 发；它可能就只有两个网络接口，分别接在内网和外网上，此时它不需要进行出 口选择，而是按照默认直接转交就可以了。因此，接入路由器的服务质量问题主 要集中在数据包转发时的排队管理上。同时，由于接入路由器是内部网络获取外 部网络服务的必经之路，因此，高可靠性也成为了接入路由器服务质量的重要衡 量指标。另一方面，接入路由器在很多时候也充当了网关的角色，而区分服务体 系结构的服务质量解决方案中，对不同用户加以识别并赋以不同的d s c p 区分码 就是在网关上进行的，因此，接入路由器就在服务质量体系中还必须具有优先级 用户管理功能。 而对于本课题要讨论的多出口路由器系统，它还必须在多出口选择时考虑到 服务质量指标，使各个出口流量均衡，并能够自动检测出口故障和调整流量分配。 下面针对该具体课题作进一步的阐述。 1 7 课题背景、任务简介以及本人所作的工作 近年来i p 电话得到了迅猛的发展，众多的因特网服务提供商在提供网络接入 服务的同时，也纷纷提供i p 电话业务。然而，还是有很多具体技术问题使得i p 电 话业务的大规模推广受到一定的影响，其中最重要的两点就是语音通话质量和业 务的可靠性问题。和传统的p s t n 网络相比，p 电话首先要将语音模拟信息转换 成数字信息，再按一定的压缩算法压缩并打包后，然后才能在i p 网络上按特定的协 议进行传输。因此，语音通话质量既受压缩算法的影响，同时也受到网络传输质 量的影响。同时，业务的可靠性一方面是前面谈到的q o s 问题中的可用性问题， 另一方面，对于商业运营的i p 电话则涉及到用户管理、业务管理、实时数据更新 等问题。这些问题不只是存在于电话关守上，同时也存在于将语音i p 数据发送到 1 0 第一章引言 广域网上去的接入路由器上。 目前，随着技术的进步，压缩算法而引发的语音通话质量问题已经基本解决， 而就本教研室开发的接入路由器而言，也已经实现了基于区分服务模型的优先级 队列转发系统。进一步提高该路由器系统的可用性，使之真正达到可商用的可靠 程度，就成了迫在眉睫的一个任务。 这是因为，对于一个从二级接入商获得的实际用户而言，网络的可用性是q o s 的根本问题。对于一个进行商业i p 电话运营的接入商而言，如果他所提供的电 话的可用性很低，当用户急需使用电话的时候，却由于系统故障或者前端正在进 行数据库的更新而无法呼叫，很难想象还会有用户敢于真正使用他们的服务。 不只是p 电话业务需要高可用性的接入路由器。我们在家里上网的时候可能 都有这样的体验，急需要上网收取一封重要邮件的时候，网络就连接不上了；或 者正当资料下载到一半时，系统却提示网络不可用。一般说来，在核心网络上都 存在冗余路径或链路来保证网络的可靠性，而在接入到具体的用户小区后，由于 要实现高可用性以及在线更新管理等一般都需要专用的设备和软件，这自然使得 网络维护使用成本都水涨船高，它使得这种可用性通常不在接入商的首要考虑问 题之列。 因此，本课题的主要任务就是在以前开发的分布式并行多处口路由器系统基 础上，为合作方的因特网业务在接入广域网的接入路由器上实现部分q o s 控制功 能。具体讲就是在充分发挥多出口这一优势，使接入路由器在进行出口选择时充 分考虑q o s 指标，通过对出口流量的均衡来实现接入的高服务质量，同时要求进 行出口故障的自动检测和容错来达到高可靠性服务质量指标；而且要求配合此前 开发的基于d i f f s e r v 的q o s 模型，在q o s 的可用性指标上达到在线不间断数据更 新，以及向管理者提供不中断服务的用户优先级更改、用户管理等功能。 在此项目中，作者详细分析了l i n u x 的网络源代码，以及内核与用户通信的 相关资料，设计和实现了排队转发系统的底层节点出口转发任务均衡模块以及用 户，业务管理模块，用c 语言作为开发语言，开发平台是此前教研室开发的x 8 6 上 的分布式l i n u x 系统。 作者查阅了大量的分布式系统中的任务均衡方面的资料以及当前的发展方 向，并把它们应用到路由器的转发中来，同时熟悉了l i n u x 系统的网络部分以及内 核通信方面相关的功能模块和它们的实现方式。在实际开发过程中，密切配合课 题组的其它成员，积极参与了需求分析、系统分析以及最后的编码和测试，圆满 完成了开发任务并交付运营商使用，通过近期的反馈来看，取得了令人满意的效 电子科技大学硕士学位论文 果。 1 8 本论文的组织结构 本论文共有五章。 第一章：引言。介绍了本课题的背景和来源以及具体的要求，作者所作的工 作和论文结构。 第二章：优化出口选择提高分布式并行多出口路由器的q o s 。针对本教研室 开发的分布式并行多出口路由器系统的多出口特点，详细介绍出口选择对于服务 质量的改善，并给出具体实现。 第三章，分布式并行多出口路由器q o s 高可用性研究与实现。具体介绍了对 于优先级队列所必须的优先级用户管理系统，并给出了保证高可用性下的详细设 计。 第四章，系统测试与性能分析。给出了详细的测试方案、连接拓扑图和测试 数据。 第五章，结束语和展望。总结全文，并对未来的工作提出了初步的设想。 第二章优化出口选择提高分布式并行多出口路由器的q 0 s 第二章优化出口选择提高分布式并行多出口路由器的q o s 本教研室开发的分布式并行多出口路由器进行到现在，已经基本实现了作为 一个接入路由器所需要的很多功能。在q o s 性能上，也己经对于特定的v o i p 应用 以及v i p 用户和游戏服务器实现了d i f f s e r v 框架下的优先级排队转发。 然而和传统的单出口接入路由器不同，为了更进一步提高系统的可靠性，分 布式并行多出口接入路由器引入了多出口概念：网络运营商可以同时选择购买多 个i s p 服务商的流量。引入多个出口后的好处是显而易见的，简单讲有以下几个 理由值得考虑： ( 1 ) 增加出口带宽。以a d s l 为例，由于现在大部分地区的a d s l 开通一般 为1 - 2 m 带宽，那就是说无论局域网内部网络有多快，路由器处理能力有多强，设 备配置再好也发挥不出效用来。而如果使用多出口路由器，比如使用两条a d s l 或以太网宽带线路，再同时在这两个w a n 口间加上负载均衡，则相当于总出口带 宽拓宽到原来的两倍了。a d s l 或普通1 0 m 、1 0 0 m 的以太网宽带接入成本都不是 很高，多申请几条线路，就可以在节省成本的同时提高线路带宽。 ( 2 ) 提高系统可靠性，起到线路备援的作用。由于网络的不稳定因素很多，在 仅仅接入单条线路的情况下，如果线路出现故障，会造成整个局域网对外通信的 瘫痪。而如果选择使用多出口路由器，申请多条相同或不同运营商的线路( 如两 条a d s l ，或者是一条a d s l 和一条以太网外线等) ，使用多个m o d e m ，可以在某 个i s p 、某条电缆、某个m o d e m 出现故障时，把数据流量重新分配到没有故障的 出口上，从而对整个的网络系统进行了加固，避免了单个网络出口瘫痪造成的灾 难性后果。这种方案与单线接入方式要可靠得多，对于一些网吧或者一些信息化 程度较高的企业来说，线路故障所造成的后果可能会相当严重，缺乏备份的网络 系始终存在巨大的隐患，选择多出口路由器就可达防患于未然之效。 ( 3 ) 便于统一管理并进行全网内流量均衡，多出口路由器不是多个单出口路由 器接入到多个i s p 服务商的简单叠加。如果简单的选择多个单出口路由器接入到 多个i s p 服务商，就需要人为的把网络分成几组，一个路由器管一组，相当于变 成了几个局域网，还要分别设置对应的网关。更重要的还在于，管理者必须根据 各个用户的网络使用方式以及可能的数据流量大小来进行网络分割，才能勉强实 现网络出口带宽利用的最大化。然而网络使用状况在很大程度上并不是平均分布 电子科技大学硕士学位论文 的，因此就很难避免到某个接入商的流量严重超过购买值，而到另一些接入商的 流量却又有很大空闲的不均衡状况。使用多出口路由器则可以把多条线路接入到 一台设备，只需设置一个网关，避免了使用多条孤立出口线路的弊病。所有网段 的局域网之间实现了真正的互连和信息共享，并且将局域网集中起来统一管理， 为网络管理人员省去了不必要的麻烦。同时，如果选择了合适的出口均衡方式， 将使全网内进行流量的均衡成为可能。 ( 4 ) 提供更多的内容服务。不同的i s p 可以提供不同的游戏、聊天、视频点播 等服务，这些内容放在i s p 各自的服务器里，要享受这些服务就必须申请相应的 i s p 接入，这时候多出口路由器就发挥着不可替代的作用。 事物总是有它的两面性的，多出口路由器有上述那些优点和特长，然而要真 正充分发挥出来也不是件很容易的事情。其中最重要的一个问题就是多出口的选 择问题。 2 1 多出口路由器存在出口选择的问题 对于一个单出口的接入路由器而言，它的主要作用只是进行地址转换和内外 网的数据转发，它可能就只有两个网络接口，分别接在内网和外网上，此时它不 需要进行出口选择，也就不存在出口选择的问题，而是按照默认直接转交就可以 了。但当有多个出口可供选择的时候，情况就有所不同了。 一个网络运营者购买了多个接入服务商的出口，他按图1 1 所示的拓扑图来 搭建网络，路由器在收到内网用户的外出请求数据包时，通常，要对这些数据包 进行n a t 地址转换。此时路由器必须选择一个上级i s p 服务商的出口i p ，将之作 数据包的源i p 地址来进行n a t 转换后，再将用户数据包从这个出口上发送出去。 那么，此时多出口路由器应该如何从多个上级i s p 服务商的出口中选择一个来进 行n a t 转换并发送呢? 显然，出口选择不能是随意进行的，它必须遵循一些基本的准则。通常，对 于一个支持n a t 转换的接入路由器来讲，它必须记录n a t 的转换状态等一些连接 信息。n a t 的一个基本原则就是一旦建立了一对转换关系后，后续的n a t 转换就 必须一直使用该出口地址，否则连接的对方将会拒绝接受数据包( 对于非t c p 的 其他无连接协议，比如u d p ，可以认为它们在收发数据包时用来相互区分的五元 组关系源i p 地址、源端口、协议、目的i p 地址、目的端口是一个伪连接，下 面所说的“连接”的概念般都是指此种广义概念，它和t c p 的连接概念并不会 1 4 第二章优化出口选择提高分布式并行多出口路由器的q o s 发生混淆，因此不需加以单独区分。) 。所以连接一旦建立，该连接内上的所有数 据包都必须使用该源i p 地址。( 有关n a t 的详细过程可参阅文献