１ 引言
光传输技术飞速发展和核心路由表快速增长对路由器性能提出了更高的需求，互联网快速发展要求路由器随着网络规模和流量增长不断扩展自身性能，虽然通过硬件升级在短期内能够提高路由器的性能，但受硬件性能限制，仅依靠硬件升级无法满足互联网快速发展的需要，为了克服硬件的性能束缚，一些路由器在数据平面采用多机柜分布式互连的集群体系结构提高转发性能，但目前路由器控制平面只有一个控制单元处理控制任务，数据平面规模扩展将增加控制平面的负载，容易造成控制单元过载。
目前对路由器的研究大部分集中在数据平面，对于逐渐成为路由器性能瓶颈的控制平面缺乏成体系的研究，为了解决现有路由器控制平面基于单一控制单元的集中式控制所面临的问题，研究人员提出了路由器分布式控制方案。
为了更好地了解路由器集中控制与分布式控制的特点，我们从可靠性、可扩展性和部署代价等方面对它们进行了比较，如表１所示。
路由器控制平面分布式互连和多实例并行可有效地避免单一硬件或软件失效导致的网络振荡，提高网络稳定性和路由器容错能力，分布式控制能够支持性能和功能的灵活扩展，提高路由器的可扩展性，控制单元之间和控制单元与转发单元之间分担负载，可克服单一硬件的性能瓶颈，减少控制单元过载，提高路由器的可靠性，硬件分布式互连和软件功能分布式、模块化设计和实现可实现不中断服务升级，提高路由器的可用性，但与集中式控制相比，分布式控制存在内部通信开销大和能耗高、管理和维护复杂等不足。
表１ 路由器集中式控制与分布式控制比较
文献［５］虽然按照分层模型综述了可扩展路由器目前的研究进展，但它重点分析和比较了数据平面的扩展方案，而对控制平面—这个制约路由器可扩展的瓶颈和关键问题缺少系统和针对性分析。
本文深入剖析了路由器集中控制存在的局限性，总结出路由器控制平面从集中式向分布式发展需要解决三个关键问题：（１）分布式控制平面，由多个控制单元分布式互连而成的分布式控制平面可有效克服单一控制单元的性能瓶颈和可扩展性差等不足，为控制平面的性能和功能灵活扩展提供支持；（２）分布式控制平面内部通信，物理上分布的控制单元和软件功能模块要形成一个整体，需要分布式控制平面内部通信协议实现硬件和软件的透明通信；（３）分布式路由协议，为适应分布式控制平面体系结构，路由协议和算法应分布式实现，充分利用系统的计算和存储资源，提高路由器的性能，本文重点围绕这三个关键问题综述了这一领域的最新研究进展，并对各种方案进行了分析和比较。
２ 路由器集中控制面临的主要问题
２.１ 性能瓶颈
目前路由器控制平面只有一个控制单元处理协议分组，Ｉａｎｎａｃｃｏｎｅ，Ｇ等人通过网络测量得出，５０％的网络故障可能因路由器控制平面过载丢失“心跳”消息引起，根据目前互联网的发展速度和硬件技术发展速度，基于单一控制单元的集中式控制平面很难满足互联网快速增长的需求。
２.２ 单点失效
现有路由协议大部分集中在主控制单元上运行，很容易因硬件或软件局部功能失效或代码错误导致整个协议失效，例如：邻居建立与维护功能失效将导致整个协议失效，虽然现有路由器控制平面采用主、从备份方式，但是主、从备份的失效恢复速度相对较慢，影响了网络的可用性，为提高网络可用性，目前通过向网络中增加路由器和运行虚拟路由器冗余协议（ＶｉｒｔｕａｌＲｏｕｔｅｒＲｅｄｕｎｄａｎｃｙＰｒｏｔｏｃｏｌ，简称ＶＲＲＰ）实现冗余备份，这提高了网络的运营成本，增加了网络连接的复杂度和网络管理的难度。
２.３ 可扩展性差
各路由器厂商都采用私有技术，分别设计各自专用的部件、接口和通信协议，不同生产厂商的路由器部件之间不能互换和通信，因此，在网络中，这些路由器只能作为独立的网络设备互连，而不能通过互连扩展为一台更高性能和更多功能的路由器，技术封闭私有和集中控制严重影响了路由器的可扩展性。
基于路由器集中控制所面临的问题，研究人员提出了路由器分布式控制方案，通过分布式互连、并行处理和冗余备份等技术提高路由器的性能、可靠性和可扩展性。
虽然路由器分布控制是一种发展趋势，但是随着硬件处理能力的不断提高，集中式还将长期存在，Ｂａｌｌａｎｉ，Ｈｉｔｅｓｈ等人研究表明两种控制方式相结合将有效延长现有路由器的生存周期，改进网络性能。
３ 分布式控制平面
路由器分布式控制平面主要分为集群路由器（ＣｌｕｓｔｅｒＲｏｕｔｅｒ，简称ＣＲ）和转发与控制分离（ＦｏｒｗａｒｄｉｎｇａｎｄＣｏｎｔｒｏｌＥｌｅｍｅｎｔｓＳｅｐａｒａｔｉｏｎ，简称ＦｏｒＣＥＳ）两种结构。
３.１ ＣＲ
ＣＲ是多个可独立运行的、具有路由功能的节点通过某种互连结构（例如：高速以太网）连接成性能、功能可扩展的单映像路由器，集群路由器根据内部节点的类型可分为软件集群路由器和集群路由器。
软件集群路由器由一台路由器与多台具有路由处理能力的ＰＣ机相连而成，软件集群路由器通过向集群中增加路由处理节点扩展路由器的性能和功能，目前比较典型的软件集群路由器有ＣＬＡＲＡ、Ｓｕｅｚ和ＶＥＲＡ，软件集群路由器借助多个路由处理节点并行，实现分布式控制单元间的负载分担，提高路由处理性能，多台ＰＣ机和一台路由器组成的分布式控制平面可实现功能和性能灵活扩展，部署代价比较低，但软件集群路由器不支持数据平面的扩展，无法提高数据平面性能，在软件集群路由器中，路由器节点失效会导致整个系统不可用，降低了系统的可靠性。
与软件集群路由器相比，集群路由器ＨＣＲ的内部节点都是具有路由和转发功能的路由器，在集群路由器内部，节点之间分担负载，并行处理不同协议的分组，分布式控制单元之间功能可相互冗余备份，能够支持数据平面的灵活扩展。
由于集群路由器的最小组成单元是路由器，控制单元与转发单元之间采用私有协议和专用接口通信，因此，内部节点的互连需要对路由器进行相应的修改，增加了部署代价。
３.２ ＦｏｒＣＥＳ
ＦｏｒＣＥＳ体系结构如图１所示，ＦｏｒＣＥＳ体系结构允许一台路由器的控制平面有多个控制单元，它们之间通过内部高速网络互连，控制单元（ＣＥ）与转发单元（ＦＥ）可采取预先配置或动态联合的方式实现路由器相应的功能，ＣＥ和ＦＥ间的自由联合可灵活扩展路由器的性能和功能，控制单元之间可彼此分担负载、冗余备份和实现分布式控制，ＦｏｒＣＥＳ体系结构为一台路由器内部多个控制单元分布式互连和规模扩展提供了一种灵活的机制，ＦＥ／ＣＥ、ＦＥ／ＦＥ、ＣＥ／ＣＥ间的标准接口和ＦＥ／ＣＥ间的ＦｏｒＣＥＳ通信协议为控制平面的性能和功能灵活扩展提供了支持，通过标准化的机制，ＣＥ和ＦＥ变成相互分离的标准组件，克服了集群路由器控制单元和转发单元不能分离的不足，可对ＣＥ和ＦＥ数量灵活扩展，有效克服单个部件性能的束缚，延长路由器生存周期，保护投资，
图1 ForCES体系结构
ＦｏｒＣＥＳ方案虽然为路由器实现控制单元、数据单元的规模扩展和扩展路由器的功能提供了一种灵活机制，但是，它只提出了分布式控制平面体系结构和ＣＥ与ＦＥ之间的ＦｏｒＣＥＳ通信协议，没有对路由软件进行分布式、模块化设计。
ＤＭＲ（ＤｅｃｅｎｔｒａｌｉｚｅｄＭｏｄｕｌａｒＲｏｕｔｅｒ，简称ＤＭＲ）是基于ＦｏｒＣＥＳ框架实现的分布式模块化路由器，在ＤＭＲ中，ＣＥ和ＦＥ是独立的标准组件，设计有标准的ＦｏｒＣＥＳ接口，相互通过内部高速以太网互连，ＤＭＲ路由器支持控制单元数量和控制平面功能的灵活扩展，通过内部通信协议Ｆｏｒｚ（ＦｏｒＣＥＳｏｎｚｅｂｒａ，简称Ｆｏｒｚ），多个分布式互连的控制单元聚合为一个整体，彼此分担负载和冗余备份，ＤＭＲ对路由协议进行了功能分解和模块化设计，将路由协议的邻居建立与维护功能迁移到转发单元上实现，利用转发单元的处理资源分担控制平面的负载，实现了路由协议分组的并行处理，提高了路由器对网络变化的感知能力和路由协议的可用性，多个控制单元分布式互连和路由协议的功能分布可提高路由器的可靠性。
由于ＣＥ与ＦＥ的标准化需要一段较长的时间，在短时期内，这种方案还很难体现它的优势，但是，ＤＭＲ实现了基于ＦＥ与ＣＥ分离的多个控制单元间的分布式互连的原型系统，为路由器分布式控制平面的设计提供了很好的参考和借鉴作用。
４ 分布式控制平面内部通信
随着路由器控制平面由集中式向分布式发展，为了使物理上分布式互连的控制单元和转发单元组合成一台完整的路由器，需要设计和实现分布式控制平面内部通信协议，目前分布式控制平面内部通信方案主要有集群路由器内部通信协议（ＲｏｕｔｅｒＣｌｕｓｔERPｒｏｔｏｃｏｌ，简称ＲＣＰ）和Ｆｏｒｚ两种。
４.１ ＲＣＰ
Ｊ.Ｂ-Ｇｕａｎ等人设计了集群路由器内部通信协议ＲＣＰ，其内部接口和协议框架模型如图２所示。
图2 RCP协议内部接口和协议框架模型
通过ＲＣＰ协议，集群路由器内部各节点都可获得组成该集群路由器的节点数量、编号、邻居节点的性能和类型、内部端口号和外部端口号等信息，集群路由器内部各节点形成对整个集群路由器一致的内部拓扑视图，在转发平面上，多个路由器节点通过标准互连卡互连。
集群路由器内部互连接口的物理层采用高速光互连技术（ＶｅｒｙＳｈｏｒｔＲｅａｃｈ，简称ＶＳＲ）；链路层使用常用的高级数据链路控制（ＨｉｇｈＬｅｖｅｌＤａｔａＬｉｎｋＣｏｎｔｒｏｌ，简称ＨＤＬＣ）帧封装格式，通过制定多种速率等级备选，满足了集群路由器内部不同速率互连的需要，提高了互连的灵活性，传输的数据帧中包含符合ＮＰＳＩ规范的数据信元和流控信元两种格式，数据信元交换数据报文，流控信元交换集群路由器内部各个交换网络的流量控制信息，数据信元头部附加一个包含信元全局目的端口信息的标签，在它所经过的每一个交换网络节点的内部互连卡上，互连卡根据全局端口设备视图与本地交换网络端口的映射关系确定本地交换网络的目的端口，将信元送往本地交换网络进行交换。
在控制平面，多个控制单元通过ＲＣＰ协议交换拓扑信息，形成统一的集群路由器管理视图和设备视图，相互间协同路由计算和协议处理，同步转发表等功能，由于ＲＣＰ方案只设计了集群路由器内部通信协议的框架，没有可参考的协议的具体工作机制，而且它只适用于集群路由器内部节点间的通信和数据交换，具有一定的局限性。
４.２ Ｆｏｒｚ
Ｏ，Ｈａｇｓａｎｄ等人基于开源路由软件Ｚｅｂｒａ和ＦｏｒＣＥＳ体系结构设计了路由器分布式控制平面内部的通信协议Ｆｏｒｚ，Ｆｏｒｚ协议在ＦｏｒＣＥＳ协议框架的基础上，对其内部通信机制进行了扩展，可实现ＣＥ／ＦＥ，ＣＥ／ＣＥ，ＦＥ／ＦＥ间的通信，其消息格式如图３所示，Ｆｏｒｚ协议的通信机制分为：联合、配置和数据传输三个阶段。
图3 Forz协议消息格式
在联合阶段，每个ＣＥ或ＦＥ通过ＩＰ可靠组播的方式向同组内的其它成员发送Ｈｅｌｌｏ消息，报告自身的信息，Ｈｅｌｌｏ机制管理成员的加入和离开，通告内部控制和数据流的组播地址、成员的信息和心跳检测。
当一个成员刚加入时，它的初始Ｆｏｒｚ数据库为空，首先，它向内部控制流的组播地址发送一个Ｈｅｌｌｏ消息，Ｈｅｌｌｏ消息中包括自身的性能、端口数量、类型等信息，收到Ｈｅｌｌｏ消息后，组内的其它成员将新成员的信息加入到自己的数据库，同时，组内现有成员向新加入的成员发送Ｈｅｌｌｏ消息通告自己的功能、资源和端口地址等信息，收到消息后，新加入的成员向自己本地的Ｆｏｒｚ数据库中添加相应成员的信息，当一个成员离开时，它发送Ｂｙｅ消息，组内其它成员收到这个消息后，将它的信息从数据库中删除，当一个成员失效时，由于缺少心跳消息，其它的成员将其从数据库中删除。
在配置阶段，Ｆｏｒｚ协议用于创建、删除和获取网络接口、ＩＰ地址、路由信息和邻居的信息等，Ｆｏｒｚ协议通过可靠组播对配置信息进行分发，建立本地端口与全局端口的映射关系，形成内部一致的路由表。
在数据传输阶段，Ｆｏｒｚ协议对本地数据进行封装，然后通过内部网络交换到相应的输出端口，在输出端口解封装后发送到外部网络。
Ｆｏｒｚ实现了分布式控制平面内部通信的工作机制和协议消息格式；对分布式控制平面内部路由和通信机制的设计具有很好的参考和借鉴作用。
４.３ 小结
现有的分布式控制平面方案及其内部通信协议如表２所示。
集中式控制平面路由器内部通信采用私有协议，技术成熟，部署代价相对较低，但性能和功能相对固定，可扩展性差，集群路由器分布式控制单元间采用ＲＣＰ协议通信，但它需要对部分路由器进行修改，增加了部署代价，ＦｏｒＣＥＳ和ＤＭＲ内部采用标准的接口和协议进行通信，基于标准化组件容易实现对控制单元的功能定制，支持性能和功能的灵活扩展，但标准化设计是一个长期的过程，因此部署代价目前相对较高。
表２ 路由器控制平面体系结构与内部通信
５ 分布式路由协议和算法
现有路由协议的功能大都集中在控制平面，为充分利用分布式控制单元和转发单元的资源，需要对路由协进行功能分解和分布式设计，将不同的功能分布在相应的控制单元或转发单元上实现，设计分布式路由算法，充分利用多个控制单元的计算资源，提高路由计算性能。
５.１ 分布式路由协议
５.１.１ ＤＣＰ
Ｍ，Ｄｅｖａｌ等人提出了分布式控制方案（ＤｉｓｔｒｉｂｕｔｅｄＣｏｎｔｒｏｌＰｌａｎｅ，简称ＤＣＰ），将路由协议的功能分为三类：
（１）链路相关功能，主要包括分组转发和邻居状态维护，这些功能可分布在转发单元上实现，利用转发单元的处理资源分担控制单元的负载，
（２）协议处理功能，例如：路由计算，协议状态机的维护，这些功能需要在多个控制单元间实现分布，
（３）更新控制信息功能，例如，更新路由表，这些功能很难进行分布式设计，应在控制单元实现，ＤＣＰ方案将ＯＳＰＦ的Ｈｅｌｌｏ机制迁移在转发单元实现，有效地利用了转发单元的处理资源处理协议的信令分组，分担了控制单元的负载，减少了Ｈｅｌｌｏ分组到控制平面的传输时间，缩短了等待控制单元处理的排队时间，加快了路由器对网络故障的感知和响应，信令功能分布在转发单元实现可避免转发单元规模扩展而导致的内部通信开销，缓解了数据平面扩展对控制平面处理能力的需求，协议信令功能的分布和并行，提高了协议的可靠性和容错性。
ＤＣＰ虽然提出了路由协议功能分布的原则，但缺乏对路由协议功能分布和模块化设计的细节。
５.１.２ ＭＣＰＢ
模块化ＢＧＰ（ＭｏｄｕｌａｒＣｏｎｔｒｏｌＰｌａｎｅｆｏｒＢＧＰ，简称ＭＣＰＢ）按照功能将ＢＧＰ协议划分为信令模块（ＢＧＰＳｅｓｓｉｏｎＭａｎａｇｅｒ）和路由处理模块（ＢＧＰＰｒｏｃｅｓｓｉｎｇ），信令模块分布在转发单元，用于维护邻居关系、接收邻居路由通告和处理“心跳”消息、分配路由计算任务，路由处理模块分布在控制单元，进行路由计算，通过对ＢＧＰ协议功能分解和模块化设计，ＭＣＰＢ方案可实现对ＢＧＰ协议分组并行处理，能够利用转发单元的处理资源分担控制单元的负载，ＢＧＰ相应的功能模块分布在不同的控制单元或转发单元上并行运行提高了可靠性和可扩展性。
５.１.３ ＤＣＰＡ
Ｋ-Ｋ，Ｎｇｕｙｅｎ等人设计了路由软件的分布式控制平面体系结构（ＤｉｓｔｒｉｂｕｔｅｄＣｏｎｔｒｏｌＰｌａｎｅＡｒｃｈｉｔｅｃｔｕｒｅ，简称ＤＣＰＡ），分别对ＯＳＰＦ／ＩＳＩＳ和ＢＧＰ等路由协议进行了功能分解和模块化设计，例如：将ＯＳＰＦ协议分解为ＯＣＣ（ＯＳＰＦＣｏｎｔｒｏｌＣｏｍｐｏｎｅｎｔ）模块和ＯＳＣ（ＯＳＰＦＳｉｇｎａｌｉｎｇＣｏｍｐｏｎｅｎｔ）模块，ＯＳＣ模块分布在转发单元，ＯＣＣ模块分布在控制单元，每个控制单元上运行的路由协议模块在其它控制单元上都相应地备份，提高了可靠性，ＤＣＰＡ将ＢＧＰ协议分解为ＢＧＰ邻居建立与维护模块、本地路由管理（Ｌ-ＲＴＭ）模块和全局路由管理（Ｇ-ＲＴＭ）模块，邻居建立与维护模块分布在转发单元，Ｌ-ＲＴＭ和ＧＲＴＭ分布在不同的控制单元，每个控制单元的ＢＧＰ邻居建立与维护模块接收来自邻居的路由信息，Ｌ-ＲＴＭ先决策出本地最优路由，然后发送给Ｇ-ＲＴＭ模块，Ｇ-ＲＴＭ模块从各个Ｌ-ＲＴＭ发送的本地最优路由中计算出全局最优路由，ＢＧＰ路由协议功能的分布和模块化设计提高了控制平面的可扩展性。
ＤＣＰＡ方案为路由协议的功能分布和模块化设计提供了很好的参考，由于ＤＣＰＡ方案只是从功能上考虑了路由协议的功能分布，没有考虑路由协议模块相互之间的耦合度和通信开销，因此，在实际的路由协议功能分布和模块化设计中需要考虑这些因素。
５.１.４ ＤＲＴＭ
Ｋ，Ｋｈｏａ等人对路由表管理进行了分布式、模块化设计（ＤｉｓｔｒｉｂｕｔｅｄＲＴＭ，简称ＤＲＴＭ），ＤＲＴＭ方案将路由表管理分解为线卡路由表管理模块（ＬＣ-ＲＴＭ）和全局路由表管理模块（Ｇ-ＲＴＭ），ＬＣ-ＲＴＭ分布在线卡，线卡维护它所在区域的链路状态数据库，当多个线卡具有相同的拓扑信息时，这些线卡组成一个集群，在集群中选举超级节点负责计算重叠区域的路由表，Ｇ-ＲＴＭ分布在控制单元，Ｇ-ＲＴＭ模块接收各ＬＣ-ＲＴＭ模块发送的路由信息最终计算出全局路由表。
ＤＲＴＭ方案充分利用数据平面的计算和存储资源来提高路由表的计算效率，但目前路由器的线卡不具备路由计算能力，因此，该方案不适合于常规路由器，实现代价比较高，另外，它在一台集中式控制路由器的控制单元与转发单元之间实现路由表计算的分布式，无法避免控制单元或Ｇ-ＲＴＭ模块导致的单点失效，降低了可靠性。
５.１.５ 小结
路由协议的分布式和模块化设计方案如表３所示。
表３ 路由协议功能分布式设计
目前路由协议大都集中在主控制单元，影响了可靠性，不能实现负载分担和并行处理，ＤＣＰ将路由协议信令功能迁移到转发单元，与集中式控制相比，在一定程度上提高了系统的可靠性和并行处理能力，ＭＣＰＢ和ＤＣＰＡ对现有协议功能进行分布式模块化设计，提高了并行性、可靠性和可扩展性，ＤＲＴＭ基于高端路由器的线卡具备计算能力设计了路由表分布式管理方案，对线卡的性能要求较高，由于它在同一路由器的控制单元与线卡之间实现分布式路由表管理，影响了系统的可靠性，但是，利用转发单元计算路由较好地分担了控制单元的负载，提高了路由器的并行处理性能。
５.２ 分布式路由算法
为了提高路由计算性能，应设计分布式路由算法，充分利用分布式控制平面多个控制单元的资源，提高路由计算性能，目前的分布式路由算法主要分为：（１）分布式并行ＯＳＰＦ路由算法，包括ＰＤＳＰＴ、ＢＰＡ和ＰＲＴＣ；（２）分布式并行ＢＧＰ路由算法，主要有ＦＤＨＰ和ＩＴＢＧＰ。
５.２.１ 分布式并行ＯＳＰＦ路由算法
（１）ＰＤＳＰＴ
Ｚｈｕ-Ｙ.Ｂ等人根据最短路径树（ＳｈｏｒｔｅｓｔＰａｔｈＴｒｅｅ，简称ＳＰＴ）增量更新的特点，利用原有的ＳＰＴ树设计了并行动态ＳＰＴ算法（ＰａｒａｌｌｅｌＤｙｎａｍｉｃＳＰＴ，简称ＰＤＳＰＴ），每次网络拓扑发生变化，将原ＳＰＴ树上受链路变化影响的节点加入队列，并分配给相应的控制单元，每个控制单元每次从本地选出距离增量最小的节点，控制单元之间利用广播方式选出全局距离增量最小的节点，每次选出全局距离增量最小的节点后，根据原ＳＰＴ树上的父子关系，相应更新全局最小节点原ＳＰＴ树上子孙的距离，并将它们从受影响节点的队列中删除，然后将新受影响的节点加入队列，反复迭代，直到受影响节点的队列为空。
ＰＤＳＰＴ算法利用分布式控制平面多个处理器资源分担计算负载，实现了ＯＳＰＦ路由表的并行计算，由于利用了ＳＰＴ增量更新，减少了整个算法的迭代次数，当网络拓扑规模比较大，并且链路故障对原ＳＰＴ树上的节点影响比较多时，这个算法的并行性能较好，当网络拓扑中每个受影响节点的入度和出度比较接近时，控制单元的负载比较均衡，由于每次迭代控制单元间需要相互通信，因此，路由器内部通信开销比较大，受网络拓扑结构和迭代算法的影响，系统的负载均衡性差，影响了并行性能。
（２）ＰＳＰＴ
Ｚｈａｎｇ-Ｘ.Ｐ等人针对ＯＳＰＦ协议设计了并行ＳＰＴ算法（ＰａｒａｌｌｅｌＳＰＴＡｌｇｏｒｉｔｈｍ，简称ＰＳＰＴ），ＰＳＰＴ根据路由器中控制单元的数量ｐ利用图分割理论将网络拓扑分割成几个区域，每个控制单元负责相应区域的路由计算，首先，每个控制单元并行计算出各自区域内所有边界程度上提高了系统的可靠性和并行处理能力，ＭＣＰＢ和ＤＣＰＡ对现有协议功能进行分布式模块化设计，提高了并行性、可靠性和可扩展性，ＤＲＴＭ基于高端路由器的线卡具备计算能力设计了路由表分布式管理方案，对线卡的性能要求较高，由于它在同一路由器的控制单元与线卡之间实现分布式路由表管理，影响了系统的可靠性，但是，利用转发单元计算路由较好地分担了控制单元的负载，提高了路由器的并行处理性能。
５.２ 分布式路由算法
为了提高路由计算性能，应设计分布式路由算法，充分利用分布式控制平面多个控制单元的资源，提高路由计算性能，目前的分布式路由算法主要分为：（１）分布式并行ＯＳＰＦ路由算法，包括ＰＤＳＰＴ、ＢＰＡ和ＰＲＴＣ；（２）分布式并行ＢＧＰ路由算法，主要有ＦＤＨＰ和ＩＴＢＧＰ。
５.２.１ 分布式并行ＯＳＰＦ路由算法
（１）ＰＤＳＰＴ
Ｚｈｕ-Ｙ，Ｂ等人根据最短路径树（ＳｈｏｒｔｅｓｔＰａｔｈＴｒｅｅ，简称ＳＰＴ）增量更新的特点，利用原有的ＳＰＴ树设计了并行动态ＳＰＴ算法（ＰａｒａｌｌｅｌＤｙｎａｍｉｃＳＰＴ，简称ＰＤＳＰＴ），每次网络拓扑发生变化，将原ＳＰＴ树上受链路变化影响的节点加入队列，并分配给相应的控制单元，每个控制单元每次从本地选出距离增量最小的节点，控制单元之间利用广播方式选出全局距离增量最小的节点，每次选出全局距离增量最小的节点后，根据原ＳＰＴ树上的父子关系，相应更新全局最小节点原ＳＰＴ树上子孙的距离，并将它们从受影响节点的队列中删除，然后将新受影响的节点加入队列，反复迭代，直到受影响节点的队列为空。
ＰＤＳＰＴ算法利用分布式控制平面多个处理器资源分担计算负载，实现了ＯＳＰＦ路由表的并行计算，由于利用了ＳＰＴ增量更新，减少了整个算法的迭代次数，当网络拓扑规模比较大，并且链路故障对原ＳＰＴ树上的节点影响比较多时，这个算法的并行性能较好，当网络拓扑中每个受影响节点的入度和出度比较接近时，控制单元的负载比较均衡，由于每次迭代控制单元间需要相互通信，因此，路由器内部通信开销比较大，受网络拓扑结构和迭代算法的影响，系统的负载均衡性差，影响了并行性能。
（２）ＰＳＰＴ
Ｚｈａｎｇ-Ｘ，Ｐ等人针对ＯＳＰＦ协议设计了并行ＳＰＴ算法（ＰａｒａｌｌｅｌＳＰＴＡｌｇｏｒｉｔｈｍ，简称ＰＳＰＴ），ＰＳＰＴ根据路由器中控制单元的数量ｐ利用图分割理论将网络拓扑分割成几个区域，每个控制单元负责相应区域的路由计算，首先，每个控制单元并行计算出各自区域内所有边界节点到这些区域每个节点的最短路径，对于包含根节点的区域，计算根节点到这些区域中每个节点的最短路径，然后，将每个区域的边界节点和根节点组成新的拓扑图，再计算根节点到这个区域边界节点的最短路径；最后并行地将根节点到每个区域边界节点的路径和区域边界节点到区域内每个节点的最短路径合并，生成最终的ＳＰＴ树。
每次拓扑变化，ＰＳＰＴ算法需要重新分割网络拓扑，算法复杂度高，因此，ＰＳＰＴ算法不适用于网络拓扑频繁变化时的ＳＰＴ计算，基于图分割能够较好地实现负载均衡，并行性能较好，ＰＳＰＴ算法在网络拓扑规模比较大时能够获得较好的性能。
（３）ＰＲＴＣ
Ｘｉａｏ-Ｘ，Ｐ等人根据集群路由器的分布式控制平面提出了并行ＯＳＰＦ路由算法（ＰａｒａｌｌｅｌＲｏｕｔｉｎｇＴａｂｌｅＣｏｍｐｕｔａｔｉｏｎ，简称ＰＲＴＣ），利用集群路由器多个路由节点将ＯＳＰＦ区域按照收集的拓扑信息进行分割，每个节点负责维护自己所在区域的拓扑，各自计算这个区域的路由表，当多个路由节点的路由区域重叠时，选举指派节点计算重叠区域的路由表，每个区域的指派节点向所有节点通告自己的路由表，每个节点选择性地将接收的路由合并生成最终的路由表，当自己所在区域的路由变化，每个指派路由节点向其它路由节点广播变化的路由。
ＰＲＴＣ算法可实现ＯＳＰＦ路由表的并行计算，但它对网络拓扑依赖比较大，由于每个节点在网络中所处的位置不同，它们各自的计算负载不同，不能很好地实现节点间的负载均衡，并行性较低，每个节点不维护全局的链路状态数据库，一定程度上降低了可靠性。
５.２.２ 分布式并行ＢＧＰ路由算法
（１）ＦＤＨＰ
Ｚｈａｎｇ-Ｘ，Ｚｈ等人设计了ＢＧＰ并行路由算法（ＦｕｌｌＤｉｓｔｒｉｂｕｔｅｄＨｉｇｈＰａｒａｌｌｅｌｉｚｅｄＢＧＰ，简称ＦＤＨＰ），集群路由器的每个路由节点分别充当与它相连的ＢＧＰ邻居的代理，负责与其相连的ＢＧＰ邻居交换路由信息，每个节点根据本地路由信息计算本地最优路由，每个节点将本地最优路由广播给集群中其它节点，从而保证每个路由节点都维护一致的全局路由表，当集群中某个节点失效时，将它代理的ＢＧＰ邻居会话和路由计算任务重新分配给其它节点。
ＦＤＨＰ方案有效地利用了集群内部各个路由节点的计算资源和存储资源，每个路由节点只计算和存储一部分ＢＧＰ候选路由，多个路由节点分担负载提高了路由计算性能，但节点间以广播的方式同步路由信息增加了内部的通信开销。
（２）ＩＴＢＧＰ
Ｗｕ-Ｋｕｎ等人设计了“迭代树”ＢＧＰ并行路由算法（ＩｔｅｒａｔｉｖｅＴｒｅｅＢＧＰ，ＩＴＢＧＰ），ＩＴＢＧＰ方案根据ＢＧＰ邻居的数量ｎ和每个控制单元的ＢＧＰ邻居数量，采用广度优先算法构建一棵ｋ阶迭代树，每当路由发生变化，树中相应的叶子节点首先计算出本地最优路由，然后发送给自己的父节点，这样沿着叶子向根的方向反复迭代，最后在根节点计算出全局最优路由。
当负载分布比较均衡时，ＩＴＢＧＰ算法的性能最优，当负载分布不均衡时，例如，到某一目的地的路由只存储在一个内部节点时，基于树形结构需要从叶子到根的方向多次迭代计算，降低了路由计算效率。
５.２.３ 小结
ＰＤＳＰＴ将计算ＳＰＴ树步骤中计算邻居节点的距离和搜索全局距离最小节点实现了并行处理，但算法复杂度较高，不能实现较好的负载均衡，ＰＳＰＴ将拓扑进行分割，能够较好实现路由计算的并行和负载均衡，但算法复杂度较高，ＰＲＴＣ对网络拓扑进行分割，算法性能受网络拓扑结构影响比较大，负载均衡性能差，但算法复杂度低。
ＦＤＨＰ按邻居会话将ＢＧＰ路由计算任务进行划分，能够较好地实现ＢＧＰ路由计算并行，算法复杂度低，采用广播的方式进行路由信息同步，减少了路由计算的迭代次数，多个节点并行计算，提高了系统的并行性能，但是，在互联网中，由于多个邻居会通告同一故障，基于广播的方式进行路由信息同步将导致内部大量的通信开销，ＩＴＢＧＰ虽然按邻居会话划分负载并行计算ＢＧＰ路由，但需要经过多次迭代才能计算出全局最优路由，随着树高度增加，内部通信开销和延时不断增大，影响了系统的并行性能。
６ 结论和研究展望
路由器控制平面的分布式实现是一种发展趋势，也是路由器体系结构及软件设计必须解决的一个关键性技术问题，通过以上分析和比较，本文认为实现分布式控制平面应该从以下几个方面入手：
（１）分布式控制平面体系结构是实现路由器分布式控制的基础，它为标准化接口和内部通信设计提供依据，为控制平面性能和功能的灵活扩展提供支持。
（２）标准化接口和通信机制是实现与互连技术无关的关键技术，是控制单元与转发单元数量和功能灵活扩展的基本保证。
（３）软件分布式、模块化设计是提高路由器性能，支持路由器功能和性能动态扩展的主要途径，合理设计将有利于提高路由器的可用性和可扩展性。
虽然目前提出了一些路由器分布式控制方案，但是路由器实现分布式控制仍然面临一些关键问题亟待解决，需要进一步深入研究：（１）任务分配，如何将原来并行运行在一个控制单元上的多个路由协议任务合理地分布到多个分布式的控制单元，这需要研究分布式控制平面的任务分配方案，即要考虑每个任务对ＣＰＵ的占用时间，又要考虑不同路由协议模块之间的通信开销，实现负载均衡，使内部通信开销最小，从而优化整个系统的性能，（２）分布式路由算法，应设计高效的分布式路由算法，充分利用各个节点的计算和存储资源，提高系统的性能。
转载请注明出处：拓步ERP资讯网http://www.toberp.com/
本文标题：路由器分布式控制研究综述
相关文章
