计算机网络路由选择

计算机网络路由选择（共9篇）

计算机网络路由选择 篇1

在我国经济和科技共同发展下, 不仅使计算机网络的技术水平得到了相应的提高, 还使它的应用范围得到了扩大。相应地, 路由选择的问题已日益突出。为使计算机网络的发展能够顺应当下社会发展的要求, 符合相应事物发展的规律, 需要对相应路由的选择放在重要的位置。需要对量子进化算法进行改进, 来解决相应路由优化选择的问题。进而使计算机网络得到优化, 更好地应用在人们生产和生活中。

1 计算机网络路由器的概述

众所周知, 在计算机网络中, 路由器占据着重要的位置, 是实现网络间相互联系的必须设备之一。路由器主要是指计算机网络中, 在相应的OSI或者RM的网络层上面进行相关工作。并在此基础上, 对不同网络之间的相关数据进行转发、分粗、存储, 同时对网络间传输数据时的路由器取向做出相应的决定。而网络路由不仅能够实现网络之间的连接, 还能够进行不同网络之间信息传递的设备。一般情况下, 路由器只能接收由其它路由传输过来的信息。同时, 它一般可以连接两个或两个以上的IP子网逻辑端口, 还需要有一个相应的物理端口。其主要包含了输入和输出端口、交换网络、路由处理器等, 不同部分发挥各自的作用, 使网络处于有序运行中。路由器会帮助每一个经过其中的相关数据帧找到一条最好的传输路径, 并在此基础上, 以该路径作为桥梁, 把相应数据信息传输到目的节点。如何选择一条最佳的路径, 这才是问题的关键。路由算法便是最重要的环节。路由算法是一种网络算法, 它主要是提升路由协议的功能, 以此降低路由消耗。路由算法需拥有能对故障进行处理的能力及迅速聚合的能力。在计算机网络的路径出现故障的时候, 路由算法不仅可以对网络信息进行更新, 还能够及时建立出新的相关数据传输途径。计算机网路中的路由器在整个网络运行中所发挥的作用是不可以轻视的。

2 量子进化算法概述

在计算机网路中, 路由的正确选择是保证它有序运行的关键, 而量子进化算法在路由选择中经常出现。所谓的量子进化算法主要是指进化算法和相应量子计算相结合的产物。具体的说, 它是在量子的太矢量表达的基础上的, 并用相应的量子比特编码来代表相应的染色体, 再用量子非门及量子旋转门来对相应的染色体进行更新。进而使相应的目标问题得到优化求解。在流程方面, 量子算法一般包括了以下步骤。首先, 需要对相应的种群进行初化。在此基础上, 对相关初始种群中的不同体进行测量, 得到一组相应的状态。在适应度方面, 对这组状态进行评估, 并把最佳个体状态和它的适应度值准确记录下来。最后, 在没有结束状态下, 进行之相关的其它操作。对于相应量子进化算法, 需要进行一系列复杂的过程。事物要用相应的符号来表示, 然后再进行计算, 比如, 染色体的长度可以用字母m表示。染色体也是相关对解多样性进行维持的最好呈现。通过这样的方式, 使它的表达更加简洁。同时, 对于它相应进化的方式需要采用量子旋转门进化。进而得出具体办法的描述, 可用下面的表达式表达。

在量子进化算法方面, 对于这种利用相应的量子旋转门来完成相应量子计划算法的办法, 它主要运用的是这种原理。利用搜索法把当下的解逼到最优解。结果可以以相应概率增加的形式来进行保留。相应地, 可以使用概率减少的办法删除没有用的结果, 使所得结果处于最佳状态。

3 量子进化算法的改进

在计算机网络中, 量子计算强大的计算能力已经成为火热的话题之一。在计算机网络路由选择中, 传统量子进化算法中存在的主要问题就是它们大都是对相应的表格进行查找, 寻找到适合的解法。这种方式, 使相应的旋转角之间的关联性不紧密。同时, 在问题搜索方面, 具有一定跳跃性, 不利于计算机网络的正常运行。为使相应的量子进化算法能更好地解决路由中的问题, 需要对它进行改进。一是, 对它的旋转角进行相应的调整和优化, 使最终数值更利于路由选择。改进后旋转角表达式如下:

根据这个改进后的相关表达式可以知道, 旋转角处于不同情况时, 会得出不一样的结果。换句话说, 旋转角的值不同, 所代表的含义也不同。如旋转角的值越小, 就表示最优个体和个体之间的距离越近, 搜索网络越小。这种状况下, 使用细搜索便可以找到最优解;当相关旋转角的值越大的时候, 就表明相应个体和最优个体之间的距离在不断拉大。所代表的搜索网络更大, 这种状况下, 就需要提高搜索速度, 才能使路由选择有利于计算机网络运行。二是, 对相应的函数进行优化调整。调整可采用组合优化办法, , 使函数处于最优状态, 为得出最优解提供相应条件。通过运用组合优化的方法可道, 个体基因之间没有很强的关联性。因此, 在计算网络路由的选择上, 可以对量子进化算法中的函数进行相应的调整, 并加以优化。它现在归一化条件对此满足的情况下, 来实现相应的实属对, 并把它们对应到一个量子位的概率幅上面。相应的量子位可以和二维空间进行对应, 分别用相关符号进行表示。在此基础上, 可以对相应的量子进化算法进行仿真测试, 看改进后的它是否比之前更具有优势。根据相应的仿真测试研究表明, 在计算机网络路由选择中的性能, 可以知道改进后的量子进化算法确实优于传统的量子进化算法, 根据相应的路由选择仿真表得出的结果, 见图1。

从图表中可得知, 在计算机网络路由选择方面, 改进后的量子进化算法不论是在收敛速度上, 还是在寻优能力上, 都比传统的量子进化算法好。相应的性能也优于传统量子进化算法。在仿真测试的基础上, 能够帮助改进后的量子进化算法在路由的最优选择中发挥应有的作用, 改进后的量子进化算法在相应路由选择中的应用更加完善。在这种状况下选择的路由能够对网络运行中出现的突发情况进行很好地应对, 及时发现和解决相应的问题。不仅能够提高相应工作人员的工作效率, 还能使计算机网络处于良好的运行状态。

4 结语

总之, 在计算机技术逐渐普及的状况下, 需要把路由的选择放在至关重要的位置。相应地, 量子进化算法的改进也是很重要的。通过对它进行改进, 使旋转角得到优化, 提高搜索速度。路由选择的优化不仅可以对计算机网路技术的发展起到巨大的推动作用, 也能成为我国经济发展的助推器之一。纵观计算机网络的发展之路, 相应改进后的量子进化算法在相应路由选择方面的应用具有很好的前景。最后, 笔者希望在丰富读者知识世界的同时, 也能引起他们的关注和新的思考。

参考文献

[1]雷华军, 秦开宇.基于改进量子进化算法的测试优化选择[J].仪器仪表学报, 2013 (4) :838-844.

[2]赵荣香.改进量子进化算法在计算机网络路由选择中的应用探究[J].科技传播, 2014 (24) :148-152.

[3]宋明红, 俞华锋, 陈海燕.改进量子进化算法在计算机网络路由选择中的应用研究[J].科技通报, 2014 (1) :170-173.

[4]刘宏艳, 王伟, 翟颖.计算机网络路由优化及优化算法的运用[J].赤子, 2014 (17) :241.

计算机网络路由选择 篇2

1、有类路由选择协议

在最初开发有类协议时，使用的网络与现在的网络有天壤之别。在那时候，modem的最高速度为300bit/s，WAN线路的最高速度为56bit/s，路由器的内存不超过640KB，而处理器的速度以KHz计，因此就要求路由选择更新必须足够小，且路由器也没有足够的资源来维护有关每个子网的最新信息，这就是有类路由协议出现的原因。

由于有类路由选择协议的更新中没有带子网掩码，因此分类路由器在发送或接收路由选择更新时，必须对更新中列出的网络使用的子网掩码作出假设，即假设各个子网所使用的子网掩码，这种假设是基于IP地址类的。

发送更新时，如果更新分组涉及的子网与发送接口的IP地址位于同一个分类网络中，路由器将发送完整的子网信息;如果更新分组涉及的子网与发送接口的IP地址不属于同一个分类网络中(即子网的更新通过属于另一个网络的接口发送出去)，该路由器就假设远程路由器将根据IP地址类来使用相应的默认子网掩码，因此路由器不发送完整的子网信息，而是该子网所属的分类网络地址信息(主网络地址)，这也被称为在网络边界自动进行汇总。

接收更新时，路由器也要对更新分组中的子网的子网掩码作出假设。如果更新分组中涉及的子网与接收接口的IP地址位于同一个分类网络中，路由器将使用接收接口的子网掩码作为该更新子网的子网掩码;如果不属于同一分类网络，那么路由器将对更新的网络应用默认的子网掩码。

在非连续网络中，有类路由选择协议在主网络边界自动进行了路由汇总，这就意味着，子网不会被通告给其他主网络，非连续子网之间相互不可见。非连续子网指的是被另一个主网络隔开的属于同一个主网络的子网。由于RIPv1不能跨越另一主网络通告其他的子网，当在跨越主网络通告其他子网时，路由器就自动进行汇总，因此，在非连续的网络中，可以使用RIPv2，OSPF，IS-IS或EIGRP路由选择协议，并禁用自动汇总功能来解决，因为这些路由选择协议属无类的路由选择协议，在发送更新时携带了子网掩码信息，

在使用了有类路由选择协议的存根网络中，最终网关路由器(如只有一个通往ISP网络的路由器)可能要使用默认路由或超网路由来转发未知子网的数据包，而与这些未知子网位于同一个主网络中的其他一些子网对路由器来说时已知的，则需要需用ip classless命令。

如果没有应用ip classless命令，路由选择表本身默认将以有类方式进行路由选择决策，即使没有使用路由选择协议也将如此。例如，路由器没有运行路由选择协议，而只是配置了静态路由，则使用默认路由仍将无法到达已知主网络的其他子网，除非配置了ip classless命令。

在12.0或更晚的cisco IOS版本中，默认将启用命令ip classless。

2、无类路由选择协议

无类路由选择协议应算时第2代的路由选择协议了，设计开发此类协议旨在克服早期分类路由选择协议的一些缺点，如：在分类路由网络环境中，在路由更新中不携带子网掩码信息，导致在同一个主网络中的所有子网必须相同的子网掩码，这就限制了VLSM的使用，导致IP地址的严重浪费。

由于无类路由网络环境中交换了子网掩码信息，则路由器的路由表中可能包含同一个主网络的多个子网路由信息，因此在转发数据包时使用了前缀最长的匹配原则来选择路由。

在有类路由网络环境中，需要在主网络边界自动进行汇总，这也限制了非连续子网的应用，而无类路由选择环境中，可手工控制路由汇总方式，通常可以在任何位置进行汇总。

默认情况下，RIPv2和EIGRP与分类路由选择协议一样，自动在分类网络边界进行汇总，这主要是让这些路由向后与它们的前任RIPv1和IGRP协议兼容。但RIPv2和EIGRP能允许路由器配置命令no auto-summary来手动关闭自动汇总功能，使得非连续子网能正常运行。但运行OSPF或IS-IS时，无需使用该命令，因为默认时它们不自动汇总网络。

计算机网络路由选择 篇3

传统的路由选择算法通常可分为两类:静态路由选择算法与动态路由选择算法。

1.1 静态路由选择算法

静态路由选择算法是指对网络信息既不进行利用也不进行测量, 按某种固定规律进行计算的路由选择的算法。

1.1.1 随机路径选择算法

随机路径选择算法是指在数据传输过程中, 当数据包到达某一节点后, 则在该节点上, 通过完全随机法和轮选法两种随机方法, 选择出一条输出路径进行转发。随机路径选择算法实现过程简单, 但由于计算过程中有可能将其收到的数据包通过原来的路径折回, 从而使数据包在网络中无限循环传达, 而最终无法到达目的节点, 因此具有一定的局限性。

1.1.2 扩散路径算法

扩散路径算法是指当某一个网络节点从某条线路收到一个分组后, 再向其除了该条线路以外的所有线路发送收到的分组, 最先到达的目的节点的一个或者若干组, 耗时最短, 必定为最短路径, 在此过程中所有可能的分组都被尝试过。但此种方法会产生很多的相同分组, 甚至可能产生无限多个分组。

1.1.3 最短路径选择法

最短路径选择算法是指用一个无向图来表示网络, 认定无向图的每条边即为一条链路, 在链路上用测度的数据进行标识, 例如节点之间的距离, 带宽, 平均吞吐量等。然后通过计算, 得出从本节点到其他节点的最优路径, 同时将计算结果进行记录。当某一节点收到一个数据包需要转发时, 可在数据包的计算结果中进行目的地址查找, 找出最优链路进行转发[2]。

1.2 动态路由选择算法

动态路由选择算法根据网络当前的状态信息来进行节点网络策略的选择, 又称自适应路由选择算法。

1.2.1 距离矢量算法

距离矢量算法中每个路由器都对应一张路由表, 它以每个路由器为索引, 在表中已详细列出了已知的路由器到每个目标路由器的最短距离及其所使用的线路, 在执行过程中, 相邻节点通过交换信息来更新表中的内容。距离矢量算法一般将距离用所通过的节点数或链路数表示, 在一定周期时间内, 每个节点将自己的距离矢量发送给相邻节点。若某个节点在给定的时间范围内, 没有接到邻接点的距离矢量表, 则可认定该邻接点的距离为∞, 表示不可达到。在收到邻接点对应的距离矢量表后, 节点根据优化原则, 同步更新自己的距离矢量表。

1.2.2 链路选择算法

链路选择算法通过发现邻居节点、测量邻接点延迟、创建链路状态分组、发布链路状态分组、计算新的路由这五步进行实现。链路选择算法应用广泛, 可应用于大型网络。

2 路由选择算法的改进

2.1 改进的路由选择算法的基本思想

由于源节点和目的节点并不相同, 可能出现多个数据包流量所选择的最佳路径为同一链路的现象, 这就使得某一链路被过分使用, 而其他链路被闲置。流量淘汰算法即是当出现情况时, 按照流量淘汰算法进行淘汰, 将不适宜的流量进行转移, 使其选择到其他闲置链路上, 从而降低同一链路的使用率, 最大程度的避免网络拥塞[3]。

2.2 改进的路由选择算法的模型

已知每段链路带宽为H, 每段链路最大数据流量为qi, 若流量G选择了该段链路则会得到效益fiai, 其中表示该流量被选择;ai=0表示该流量被淘汰。算法建立的数学描述如下:

2.3 算法的实现

此算法由于设置了过滤条件, 可以使得可行解通过过滤条件直接过滤, 而不用进行其他约束条件的判断, 这种计算过程减少了运算次数, 同时, 每次得到的过滤条件的判断值是可以动态改变的, 从而减少了计算量。

3 结论

与传统的路由选择算法相比, 改进后得到的应用于流量控制的路由选择算法经, 可较好的解决流量在选择数据传输时选择同一链路而产生的网络拥塞问题, 链路的使用率得到均衡, 大大提高了网络的吞吐量, 对于缓解流量在数据传输过程中的数据包丢失情况有显著效果。改进的路由选择算法对于提高网络的数据传输速率, 减少网络费用具有重要的意义。

参考文献

[1]方敏, 孙劲光, 杨勇.基于流量控制的路由选择算法[J].辽宁工程技术大学学报, 2002, 21 (6) :767-769.

[2]陶滔, 马淑萍, 罗江琴.网络路由信息安全应用研究-基于流量预测的路由选择新算法[J].中国安全科学学报, 2003, 13 (5) :62-64.

有关路由选择协议的学习笔记 篇4

开放式最短路径优先协议（OSPF）

OSPF克服了路由选择协议（RIP）中的缺陷，但是，这个协议并不是专有协议，但是，它仅支持IP路由选择协议。这个协议是以互联网工程任务组（IETF）为支持庞大的异构网络开发的Dijkstra算法为基础的一种链路状态的内部网关协议（IGP）。在至最后确定目前应用的OSPFv2期间，完成了很多有关这个问题的研究报告。链路状态通告(LSA)要发给所有的设备，从而引起路由器的大量通信。然后，OSPF就开始高效率地工作了，

这个路由选择协议使用了三个不同的数据库表记录邻居、链路状态和路由。下面是OSPF的特点：

1、开放式协议。

2、适用于小型至大型网络。

3、仅支持IP第三层路由选择协议栈。

4、链路状态路由选择协议（不像距离矢量仅发送给邻居）。

5、内部网关协议。

6、多播链路状态通告。

7、在多播地址224.0.0.5和224.0.0.6上升级。

8、IP协议号89。

9、管理距离是110。

10、衡量标准是累积成本（与带宽成反比）。

11、仅支持等价均分负载，但是，某些执行可利用服务类型请求的好处。

12、要求在那个每一个区域都有一个路由结构，每一个区域必须要接触到骨干区域（否则要使用虚拟链接等临时的补丁）。LSA、区域和状态等各种路由类型需要根据你的设计和第二层拓扑结构而定。

13、使用Dijkstra算法选择无路由自环路经，并且提供迅速的融合。这将使用LSA和SPF算法。

14、支持变长子网掩码（VLSM）和汇总（没有级别）。

15、仅支持手动汇总；这并不像增强型内部网关路由选择协议（EIGRP）那样是自动化的。只能在ABR（区域范围）或者ASBR（汇总地址）上执行。

试议路由器的选择 篇5

关键词：路由器,选择

路由器是互联网络的枢纽、“交通警察”。目前路由器已经广泛应用于各行各业，各种不同档次的产品已经成为实现各种骨干网内部连接、骨干网间互联和骨干网与互联网互联互通业务的主力军。面对众多的路由器品牌、型号和路由器专业的性能指标，该如何正确地选择路由器困扰着很多企业或个人。在此将根据不同的网络类型，对路由器的选择进行简单的探讨。

1 路由器功能

路由器是最重要的网络互连设备之一，它工作在网络层，用于互连不同类型的网络，使用路由器互连网络的最大特点是各互连子网仍保持各自独立，每个子网可以采用不同的拓扑结构、传输介质和网络协议，网络结构层次分明。

路由器的作用是在源节点和目的节点之间为数据交换选择路由，它提供了各种网络协议。路由器的功能主要有以下几种：

(1)网络互连，路由器支持各种局域网和广域网接口，主要用于互连局域网和广域网。

(2)数据处理，提供包括分组过滤、分组转发、优先级、复用、加密、压缩和防火墙等功能。

(3)网络管理，路由器提供包括配置管理、性能管理、容错管理和流量控制等功能。

2 常见路由器品牌

目前，全球生产路由器的厂家很多。在国内，这个市场过去通常是国外的品牌一统天下，如Cisco,3Com,Cabletron,Nortel Networks等公司。其中，思科系统公司(Cisco Systems)是路由器技术的领导者，在Internet上流动的数据大多都会通过Cisco的设备，其中绝大多数是Cisco的路由器。十多年以来，该公司一直掌握着网络互连系统全球市场的50%以上的市场份额。

现在随着互联网时代快速发展和自身技术的提高，国内厂商也纷纷推出自有品牌的网络产品，其中也包括了路由器。从技术含量较低的产品到具有高技术水平的产品，国内公司以不懈的努力证实了自己的实力，可以欣喜地看到市场上出现华为、联想、实达等品牌的路由器产品。其中，1988年成立的华为公司，自进入数据通信领域以来，已经推出了全系列的路由器产品。现在，华为技术有限公司以华为自主品牌的网络核心技术为龙头，不断成长壮大，造就了出色的全系列网络产品。

在这里，推荐一些生产路由器的大公司，Cisco公司和华为公司。这些公司的产品已经经历了市场的考验，在消费者中也有较好的口碑，消费者可以放心地选用它们的产品。

当然，在购买时要注意防伪标记，警防上当。比如，选购Cisco公司的路由器，应注意3点，第一，内部有黄色标贴，无法作假;第二，防伪贴触摸有凹凸感，为真的;第三，封箱带上的Cisco标志清晰，假货模糊。对于，华为公司的产品，可以电话咨询800-810-0504(免费热线)，查明真假序列号，同时看一下3COM产品外包装上都有的防伪蓝标。

3 路由器性能指标

在确定选用某个公司的路由器之后选购路由器时，还应该注意查看路由器的一些性能指标。可以参考以下性能指标，它们在很大程度上决定了路由器的工作性能，以及是否能适合自己将要构建的网络环境。

(1)全双工限速转发能力

所谓的全双工限速转发能力是指以最小包长(64bit)和最小包间隔，在路由器端口上双向传输时不致丢包。由于路由器最基本的且最重要的功能是数据包转发，因此，在同样端口速率下转发小包，就成为对路由器包转发能力最大的考验。所以，该参数是标志路由器性能的最重要指标。

(2)设备吞吐量

设备吞吐量是指设备整机包转发能力，是设备性能的重要指标。路由器的工作在于根据IP包头或者MPLS标记选路，所以，性能指标是转发包数量每秒。

(3)转发时延

转发时延是指需转发的数据包最后一个比特进入路由器端口，到该数据包第一比特出现在端口链路上的时间间隔。

(4)路由表能力

路由表能力是指路由表内所容纳路由表项数量的极限。由于Internet上执行BGP协议的路由器通常拥有数十万条路由表项，所以该项目也是路由器能力的重要体现。

(5)CPU

无论在中低端路由器还是高端路由器中，CPU都是其心脏。通常中低端路由器中，CPU负责交换路由信息、路由表查找以及转发数据包。CPU的能力直接影响路由器的吞吐量(路由表查找时间)和路由计算能力(影响网络路由收敛时间)。在高端路由器中，通常包转发和查表由ASIC芯片完成，CPU只实现路由协议、计算路由以及分发路由表。需要注意的是，CPU性能并不完全反映路由器性能。路由器性能主要由路由器吞吐量、时延等指标体现。

(6)内存

路由器中主要有4种内存，只读存储器(ROM)、闪存(FLASH)、随机存储器(RAM)、非易失性(NVRAM)，它们各自起到不同作用，在此不再详细描述。内存用作存储配置，路由器系统，路由器协议等。在中低端路由器中，路由表可能存储在内存中。一般来说，路由器的内存越大越好。当然，这样也会提高成本。

在这里，需要再次说明的是，并不是所有的性能指标都是越高越好，关键是要选择适合自己网络结构的路由器。

4 路由器选择

在选择路由器时，除了查看品牌，性能指标外，最重要的一点就是分清网络类型。不同网络类型对路由器的需求是不一样的。通常根据路由器的性能和所适应的环境，可将路由器的种类划分接入级路由器、企业级路由器和骨干级路由器。

(1)家庭网或ISP内的小型企业客户网

对于家庭或ISP内的小型企业客户，他们对路由器的要求不是很高，可以采用接入级路由器。接入级路由器要求可以提供SLIP或PPP连接，还支持诸如PPTP和IPSec等虚拟私有网络协议。这些协议要能在每个端口上运行。当然，随着如ADSL等技术的发展，将进一步增加接入级路由器的负担。接入级路由器将来会支持许多异构和高速端口，并在各个端口能够运行多种协议，同时还要避开电话交换网。

建议选择的产品档次应该相当于Cisco的2600系列以下的产品、Cisco的1700系列、Cisco的1600系列。至于具体选用哪个档次的路由器，应该根据自己的需求来决定。在购买之前，应该对所希望购买的路由器品牌及其质量状况、型号、路由器价格等有一定的了解，这样才能选购到适合自己网络的路由器。

(2)企业网或校园网

前几年发展起来的企业网络或校园网络大多规模较小，网络互连设备主要由Hub或网桥等连接起来。这些设备价格便宜、易于安装、无需配置。然而随着企业或学校的发展，希望网络能够提供等级服务的需求越来越迫切。如果有了路由器的参与，网络就能够分成多个域，并因此能够控制一个网络的大小。

企业级路由器要求能够连接许多终端系统，其主要目标是以尽量便宜的方法实现尽可能多的端点互连，并且进一步要求支持不同的服务质量。企业级路由器还支持一定的服务等级，至少允许分成多个优先级别。但是路由器的每端口造价要贵些，并且在能够使用之前要进行大量的配置工作。因此，企业级路由器的成败就在于是否提供大量端口且每端口的造价很低，是否容易配置等。

另外还要求企业级路由器有效地支持广播和组播。企业网络还要处理历史遗留的各种LAN技术，支持多种协议，包括IP、IPX和Vine。它们还要支持防火墙、包过滤以及大量的管理和安全策略以及VLAN。

可以选择的产品档次应该相当于Cisco的模块化3600系列，如图1所示以及Cisco 7200系列以下，选用的原则是考虑端口支持能力和包交换能力。

(3)企业级网络的互联

为了实现企业级网络的互联，需要采用骨干级路由器。一般来说，只有工作在电信等少数部门的技术人员，才能接触到骨干级路由器。互联网目前由几十个骨干网构成，每个骨干网服务几千个小网络，骨干级路由器实现企业级网络的互联。对于骨干路由器的要求主要在于速度和可靠性，而价格则处于次要地位。硬件可靠性可以采用电话交换网中使用的技术，如热备份、双电源、双数据通路等来获得，这些技术对所有骨干路由器来说是必须的。骨干IP路由器的主要性能瓶颈是在转发表中查找某个路由所耗的时间。当收到一个包时，输入端口在转发表中查找该包的目的地址以确定其目的端口，当包越短或者当包要发往许多目的端口时，势必增加路由查找的代价。因此，将一些常访问的目的端口放到缓存中能够提高路由查找的效率。不管是输入缓冲还是输出缓冲路由器，都存在路由查找的瓶颈问题。除了性能瓶颈问题，路由器的稳定性也是一个常被忽视的问题。

在这里，仅推荐两款骨干级路由器，它们是思科Cisco XR 12000系列路由器，如图2所示，爱立信AXI520-8(M40E)骨干路由器，如图3所示。在选择骨干级路由器时，选择一个具有良好的性能/价格比的产品，选择一个具有分散式架构的产品，选择一个符合国际标准、具备兼容性的产品，选择一个功能完整的产品，选择一个成熟的、有成功应用案例的产品对客户来说都是很重要的，而市场上具备这些完整特性的产品并不多，客户必须精挑细选才能保障自己的投资。

5 结语

简单介绍了路由器的功能作用、品牌和性能指标，让读者对路由器有了一定的了解。在此基础上，根据路由器的性能和所适应的环境，将路由器的种类划分接入级路由器、企业级路由器和骨干级路由器。通过在不同网络环境下对路由器不同需求的分析，介绍了几款路由器供读者参考。当然，在此观点还存在一定的局限性，因为从不同的角度出发，可以对路由器做出不同的选择。

参考文献

[1]刘哓辉,杨兴明.中小企业网络管理员实用教程[M].北京:科学出版社,2004.

计算机网络路由选择 篇6

随着互联网的发展以及人们对高质量网络需求的不断增长,为了提高网络效率,降低网络成本,提高用户的满意度和网络运营商的收益,必须提高网络的服务质量,寻求更快更好的路由交换方法,从而提高信息的传输效率。这就要求我们寻找一个最短路径的算法,来实现用户的需求。

IP路由选择,是指寻找一条将数据报从信源机传往信宿机的最佳传输路径的过程,而传输路径往往由一系列路由器组成,因此,IP路由选择实质是在不同的路由器之间做出选择,选择数据报传输过程中的下一个路由器,从而获得最佳传输路径。

最短路径算法使得网络中从源节点到接收节点的所选路径的链路权重之和最小。Dijkstra算法和Bellman-Ford算法是两个最著名的最短路径算法:Dijkstra算法是图论中寻找最短路径的算法。它实际上求出从源节点到系统中所有节点的最短路径。把它应用到网络路由,就嫌有点浪费,因为网络路由只要求从源节点到目的节点的最短路径,因此实践中研究了一些改进的Dijkstra算法。Bellman-Ford算法是寻找最短路径的分布式算法,允许边的权是负的,适合网络路由。但是,各节点的同步是一个问题。在不同步的情况下就可能得不到最优解,最短路径算法可用来解决路径约束问题。

2 常用路由选择算法

常用的路径选择算法有两种:Dijkstra算法和Bellman-Ford算法,下面分析这两个常用算法。

2.1 Dijkstra算法

也称为最短路径算法或正向搜索算法,是一种集中式的静态算法。按照路径长度增加的顺序寻找路径可以找到从给定的一个源顶点到所有其他顶点的最短路径。算法是逐步执行的,在第K步,到最靠近源顶点(到达源顶点耗费最小)的K个顶点的最短路径已经找到,这些顶点的集合记为M。在第(k+1)步,不在T中且离源顶点距离最短的顶点加入到M中时,从源顶点到该顶点的路径也就确定了。

该算法的形式化描述如下[7]:

N=网络中的顶点集合;

S=源顶点;

M=算法中用到的临时顶点集合;

W(i,j)=从顶点i到顶点j的链路耗费。若两个顶点之间不直接相连,则W(i,j)=∞;若两个顶点之间直接相连,则W(i,j)≥0,P(n)=从顶点S到顶点N的最小耗费路径的耗费,算法执行过程中是知道的;算法结束时,也就是S到N的最小耗费路径的耗费。

算法总共有3个步骤:步骤2和步骤3要重复执行,直至M=N。也就是说,步骤2和步骤3在重复到网络中所有顶点都已经找到最终路径为止:

1)初始化:M={S}即,临时顶点集合中只有源顶点P(n)=W(i,j),对所有n≠s即到相邻顶点的初始路径耗费就是链路耗费。

2)取下个顶点:找到不在M中且到顶点S有最小耗费路径的相邻顶点,把它加入到临时集合M中;把依附于该顶点和M中某顶点构成路径的边也加入到M中。

3)更新最小耗费路径:P(n)=min[P(n),P(x)+W(x,n)]对所有X￠M如果第二项小,则从S到N的路径从现在起就是从S到X再连上X与N之间的边。当所有的顶点都加入到M以后,算法结束。这样,算法要进行V次迭代。结束地,每个顶点X的值P(X)就是从S到X的最小耗费路径的耗费(长度),它的时间复杂度为O(v^2)。

2.2 Dijkstra算法的不足与优化分析

在实际的应用中,我们发现要计算最短路径的起点和终点往往不是网络中已知的顶点[3]。比如:我们从A、B两个城市之间的某个地方出发,要到C城市去,假设我们已经知道当前位置距离A城市的距离为100公里,距离B城市的距离为300公里,那么从当前位置如何走才能使到达目的地的路程最短?显然不能因为当前位置距离A城市近,就选择先到达A城市,然后再从A城市出发到达C城市;而是应该计算AC的距离加上100公里,然后与BC的距离加上300公里比较,然后选择总距离短的一个方案。由此,当选择的源点和终点均不是已知的顶点,而是已知两顶点所在线段上某一点时,按上面的计算方法则需要计算四次。这无形中增加的程序的运行时间,而且还要增加一定的变量来存储中间的计算结果。

以下我们在上述用自定义结构的数组表示邻接表的基础上,采用对邻接表进行动态修改的方法,对算法再次进行优化:对于有向图G=(V,E),图中有n个顶点,有e条弧,假设源点VS落在顶点A和顶点B所在的弧上,终点VT落在顶点C和顶点D所在的弧上。当建立邻接表的时候,把源点VS和终点VT纳入已有的网络中,则顶点的数量变为n+2,弧的数量变为e+2;由此,需要在邻接表末尾增加2个元素,并修改与源点VS及终点VT关联的4个顶点所对应的邻接表中的内容。

2.3 Bellman-Ford算法

也称为反向搜索算法或距离向量算法,它是从目的点出发反向计算的。它是找到一个给定的源顶点出发的最短路径,限制条件是径上最多只有一条链路;然后再找到一些最短路径,限制条件是路径上最多只有2条链路,其余类似。

这个算法也是分步骤执行的,其形式化描述如下:

S=源顶点

W(i,j)=从顶点i到顶点j的链路耗费,W(i,j)=0;如果两个顶点之间不直接相连,则W(i,j)=∞,如果2个顶点之间直接相连,则W(i,j)≥0

H=在算法和当前步骤中路径的最大链路数;

P(n)=从顶点S到顶点N的最小耗费路径的耗费,限制条件是路径的链路数不超过H。

算法的步骤如下:其中步骤2重复执行,直至路径的耗费不再变化为止:

1)初始化:P0(n)=∞,对所有n≠s,L[H](s)=0;

2)更新:对相继的每个H≥0对每个n≠s,计算P[H+1](n)=min[PH(j)+w(j,n)]找到符合最小条件的顶点j,将n与该前趋顶点相连,删除n与所有其它前趋顶点的连接,这些连接是在前面的迭代中产生的。从s到n的路径以j到n的链路结束,其算法时间复杂度为O(n^3)。

2.4 Bellman-Ford算法的缺陷及其优化方法分析

Bellman-Ford算法主要有以下不足:无法反映恶化情况,路由环引起的无穷计算,慢收敛。下面对这三种问题逐一介绍,并提出解决问题的思路。

2.4.1 无法反映恶化情况的问题

在距离向量路由算法中,我们总是用计算得到的最优路径取代已经存在的路由。但是如果线路的开销增大了,那将如何呢?考虑下图所示的网络,开始时B到E的最优路径是经过C开销为6。现在我们假设CE之间的开销增加到10,在下一轮交换的时候,B收到C的消息它声称自己到E的开销增加了,但是在上述的算法中B是不会更改自己的路由信息表的,因为它只在找到比现在路由信息表中更加优化的路径的时候才修改自己的路由信息表。

解决这个问题的一个简单办法是,路由器收到邻居节点的消息后,如果发现有更优化的路径,当然它采用具有最小开销的路径:反之如果它发现在这次的信息交换中计算得到的路径比自己原来记录的路径的开销还大。那么它就需要察看在原来记录的路由信息表中的那条最优路径上的第一个节点是否就是这个邻居节点,如果是,它就需要更改路由表中的开销值。虽然只是一个简单的优化办法,但是我们看到在开销增大后(以时延为度量值的网路中,因为拥塞的原因开销经常变化)经过几轮的交换后总可以正确的反映网络实际情况。而在原来的算法中,这个开销增大的坏消息永远不会被广播出去,路由信息永远不能正确的反映实际网络情况。

2.4.2 路由环引起的无穷计算问题

路由环路问题会引起无穷计算问题。当一个路由器宕机或下线后,这个消息可能需要经过无数次交换才能通知到每个节点。

一种办法就是设置一个最大值阀门。一旦开销增加到超过这个阀门值我们就认为网络不可到达,路由器收到的网络的数据包就把它丢弃,但是如何选择合适的最大值却是个问题。我们看到,交换次数取决于这个无穷大的值究竟取多大,而交换次数又决定了收敛时间和网络开销。对于以跳数为度量值的网络,通常取最长路径加1。对于以时间延迟为度量的网络,这个无穷大的阀值选取就是一个很麻烦的问题了。

2.4.3 慢收敛问题

收敛时间是指网络中所有路由器对当前网络拓扑结构达成一致所需要的时间。当网络节点故障或开销增大的时候,距离矢量路由算法的收敛时间长,收敛性是非常差的。用一句话概括距离矢量路由算法:好消息传播得快,坏消息传播得慢。为了解决慢收敛问题,我们可以采用触发更新和抑制计时法。

触发更新就是当路由器发现网络结构出现变化时,它不等待下一个信息交换周期的到来就主动发起路由信息广播。当它的邻居路由器收到触发更新的路由信息以后,也立即触发广播路由信息。如此一来它就可以引起全网的连锁反应,使消息能够迅速的广播出去。但是触发更新也存在问题。在许多路由器共享一个公共网络的结构中采用触发更新技术的情况下,一个广播就能改变这些路由器的选路表,引发一轮新的广播。如果第二轮广播改变了路由表,它又会引起更多的广播,这就产生了广播雪崩。

解决慢收敛问题的另一个技术使用了抑制计时法。抑制法迫使参与协议工作的路由器,在收到关于某网络不可达的信息后的一段固定时间内,忽略任何关于该网络的路由信息。这段抑制时间的典型长度是60秒。该技术的思路是等待足够的时间以便确信所有的机器都收到坏消息,并且不会错误地接受内容过时的报文。需要指出的是,所有参与的机器都要遵循抑制策略,否则仍然会发生选路回路现象。抑制技术的缺点是:如果出现了选路回路,那么在抑制期间内这些选路回路仍然会维持下去。更严重的是,在抑制期间所有不正确的路由也保留下来了,即使是有替代路由的存在。

3 结束语与展望

本文主要介绍最佳路由选择的两种常用算法Dijkstra算法和Bellman-Ford算法,通过对这两种算法的讨论,以及对它们不足之处与优化思路的分析,可以为以后的路由算法设计提供一个有效的参考,提高路由选择选择的效率,从而更好的为用户提供一个好的网络。

参考文献

[1]黄劲荣,李振,坤林穗.浅析两种分布式路由选择算法[D].广东工业大学计算机学院,2006.

[2]李峰,张建中.网络最短路径算法的改进及实现[J].厦门大学学报:自然科学版,2005(44):40.

[3]乐阳等.Dijkstra最短路径算法的一种高效率实现[J].武汉科技大学学报,1999,24(3):62.

[4]冀鑫泉,桂志波.Internet中路由算法研究现状及其实现[J]江苏通信技术,2003,19(1):13-16.

[5]闵应骅.计算机网络路由研究综述[J].计算机学报,2003,26(6):641-648.

[6]鲁士文.计算机网络原理与网络技术[M].北京:机械工业出版社,1996.

[7]谢希仁.计算机网络[M].4版.北京:电子工业出版社,2004.

[8]刘越,陈常嘉.基于信源路由的时延受限点到点路由算法[J].电子学报,2001,29(4):510-514.

供电公司综合业务网路由策略选择 篇7

电力通信综合业务数据网承载业务类型繁多, 随着企业发展综合业务数据网承载业务种类越来越多, 还包含有突发性的大型数据业务, 瞬时业务量巨大, 各站点路由设备压力较大。要求核心层和分布层主路由设备处理速度要快, 延迟要小。所以, 选择一种适合的路由策略组网至关重要。

1 综合业务数据网可选择的路由策略

路由策略为IP网络内各节点提供IP数据包的路由选择机制。

1) RIP/RIPv2 (路由信息协议)

RIP协议是一个国际标准, 所有的路由器厂商都支持它, 而且RIP在各种操作系统中都能很容易地进行配置和故障排除。该协议采用距离向量算法, 但是RIP协议需要相对较长的时间才能确认一个路由是否失效。这个时间对于大多数应用程序来说都会出现超时错误, 不能适应电力企业运营的发展需要。同时, 它在选择路由时不考虑链路的连接速度, 而仅仅用跳数来衡量路径的长短, 不能有效地利用备份冗余链路的资源。

2) OSPF (开放最短路径路由协议)

0SPF是一种基于链路状态的路由协议, 适用于IP网络。OSPF路由信息更新很快, 这个时间取决于实际网络的大小, 如果网络很大, 时间就不会特别快, 更重要的是这样的计算机制对路由器的CPU资源占用率很高, 网络中有节点故障或某节点运行不稳定时在广域网上频繁的广播也会造成网络性能的降低。

3) IS-IS (中间系统-中间系统路由协议)

IS-IS与OSPF相似, 也是基于链路状态计算的最短路径路由协议。IS-IS为ISO标准路由协议。IS-IS的骨干不是特定的一个域, 而是由连续的Level 2路由器组成。IS-IS的两层分级的网络拓扑结构不是必须的, 网络可以完全由Level 1路由器或完全由Level 2路由器构成。该协议扩展性较好, 支持网络规模大于OSPF, 在网络相当庞大时能体现出优势。同时, IS-IS占用网络资源较小;路由收敛和恢复时间快。IS-IS采用较小的协议数据包承载路由信息, 这使得路由信息繁衍速度更快。

4) 路由设备私有协议

由于私有路由协议所应用设备的局限性, 本文不予讨论。

5) 静态路由

由网络管理员手动配置的指定路由。

在上面的介绍中我们可以看出, 实际上可供供电企业综合业务数据网选择的内部路由协议有:RIP、OSPF和IS-IS、静态路由。RIP是较老的路由协议, 加上它收敛慢, 受hop跳数限制, 所以不建议选择;静态路由协议的优点是:配置简单, 效率高, 但不灵活;我们可以在局部情况下应用;OSPF和IS-IS各有特色, 都可以选用做内部IGP。下面针对具体网络模型分别进行讨论。

2 OSPF策略与IS-IS策略组网方案比较

2.1 协议比较

1) 两种协议都维护一个链路状态数据库;

2) 两种协议都使用SPF算法来计算路由。IS-IS在域内运行Level 1 SPF计算路由, 在域

间运行Level 2 SPF计算路由;OSPF在域内运行SPF计算路由, 在域间运行距离向量算法来计算路由;

3) 两种协议都使用域来建立两层分级的网络拓扑结构。IS-IS的骨干不是特定的一个域, 而

是由连续的Level 2路由器组成;OSPF的骨干必须有而且必须为area 0;IS-IS的域边界是在路由器之间的链路上;OSPF的域边界是在路由器上。

2.2 OSPF策略组网

OSPF在域内运行SPF计算路由, 在域间运行距离向量算法来计算路由, 如果数据流量大, 可能会造成以下两种情况:

1) 造成分布层路由设备压力大, 而核心层大容量路由交换设备并未充分利用;

2) 产生网络瓶颈, 降低网络的整体性能。

2.3 IS-IS策略组网

利用SPF算法针对整个网络进行计算, 同样的物理拓扑结构利用OSPF组网时区域边界路由选择方式可能会降低网络传输性能。

2.4 IS-IS策略的局限性

1) 早期的IS-IS协议在二层完成路由选择, 组网比较复杂, 实际应用的局限性很大。现在的IS-IS协议指扩展IS-IS协议, 补充了三层路由功能, 弥补了这点不足。

2) IS-IS只定义了两种网络拓扑类型:broadcast和general topology。OPSF定义了5种网络类型:point-to-point、point-tomultipoint、broadcast和NBMA, 以及virtual links。

对于要承载帧中继等传统数据业务的数据网来说, OSPF协议提出了NBMA以及virtual links网络类型提供了很好的解决办法, IS-IS协议没有提供任何办法, 并没有基于IP组网以外的传统通信业务, 所以这种局限性不会影响网络建设和发展。

3 建设可持续发展的电力通信综合业务数据网

OSPF策略组网网络中运行中设备IPV4升级IPV6较为困难, 必须重启机器或更换新设备。对于电力综合业务数据网来说:首先, 承载业务繁多而且较为重要, 实时性要求高, 设备运行中重启升级是不现实的;其次, 覆盖范围广、站点多, 更换新设备投资巨大。

ISIS策略组网可以直接对运行设备进行IPV6升级。考虑企业可持续发展的重要性, 采用ISIS路由策略较为合适。

4 结论

计算机网络路由选择 篇8

本文就如何利用迪杰斯特拉 (Dijkstra) 算法解决网络中路由选择的最短距离问题作了说明, 欲以此提高通信网的通信效率。

1 概述

Dijkstra算法是从一个顶点到其余各顶点的最短路径算法, 其基本原理是每次新扩展一个距离最短的点, 更新与其相邻的点的距离。当所有边权都为正式, 不会存在一个距离更短的没扩展过的点, 因此这个点的距离永远不会再被改变, 因此保证了算法的正确性。

2 算法在路由选择中的应用

在通信网中, 如何利用现有的通信网络, 通过最短的通信路径完成信息的传递, 在通信网研究中具有重要意义。最短路径算法在路由选择中运行的过程为:在一包含多个路由器的网络区域中, 以其中某一路由器A为例。

路由器A以自己为原点, 收集从其他本地区域广播来的更新后的链路状态信息, 得到本地自治系统区域内部的拓扑及链路状态信息, 之后构架自己的链路状态数据库。每个路由器根据此数据库信息, 在本地利用Dijkstra最短路径算法构造以自己为原点到本自治系统区域内的各个网络的最短路径树。若路由器欲发送数据到某一个网络, 即根据已构造好的最短路径树来优先选择最短路径, 然后发送数据到目的地。

可以这样说最短路径算法在路由选择中的应用, 具体到网络协议上就是开放最短路径优先协议OSPF。

OSPF是一种链路状态路由选择协议。对于大规模的自治系统的管理, 它引入了本地区域 (area) 的概念, 即组合若干网络和主机, 再把连接在这些网络中的路由器加上, 这些合起来称为一个区域。一个自治系统可划分多个区域, 每个区域都包含一组网络和路由器。一个区域内的路由器之间相互交换所有的信息, 而相对同一个自治系统内的其他区域内的路由器就隐藏了他的详细拓扑结构。这种分级结构减少了路由信息的流量, 并且简化了路由的计算。

在每个自治系统内有一个特殊的区域, 称为backbone area。OSPF规定, 所有区域间的通信必须经过此主干区域。整个自治系统就是一个以主干区域为中心的逻辑星形拓扑结构, 这要求主干区域必须是连续的, 即其中的任两台路由器都可以通信。

如图1所示, 路由器按其所处的位置分为4类:

(1) 内部路由器:该路由器所连接的网络都属于同一区域, 且运行同一种链路状态路由选择协议。

(2) 区域边界路由器 (ABR) :该路由器运行多种链路状态路由协议, 每个区域一个, 多个区域间被该路由器连接。该路由器连接区域的拓扑信息会由ABR传送至主干区域, 再由主干区域分发给其他区域。

(3) 主干路由器 (BR) :指连在主干区域的路由器, 除包含所有区域的边界路由器, 还可能包含别的路由器。

(4) 自治系统边界路由器 (ASBR) :交换其他自治系统中的路由信息。该路由器可能是内部区域边界路由器, 可能从属主干区域, 也可能不在主干区域。

3 OSPF协议的执行过程

OSPF把路由器之间要交换的网络拓扑机构信息称为链路状态公告 (LSA) 。在以太网等共享网络上, 如果让任何两台路由器之间都相互交换LSA信息, 那么会占用许多带宽, 并且很难保持路由器之间状态的一致性。OSPF规定, 在多访问网络中, 要选出一台指定路由器 (DR) 和一台备份指定路由器 (BDR) 。DR和网络上其他路由器交换LSA信息, 并代表它所在网络的LSA。BDR则在DR出现故障时快速转变为DR, 保证网络的正常运转。

如图1所示, 路由器按其所处的位置分为4类

当一个运行OSPF协议的路由器启动后, 它试图与相邻的路由器建立毗邻关系, 它会定期与其相连的所有链路 (各个网络接口) 上发送Hello消息。在Hello包中, 包含该路由器自己的ID (即某一接口的IP地址) , 优先权 (用于DR) , 已知的DR、BDR和相邻路由器表。接收到Hello包的路由器如果发现自己在对方相邻的路由表中, 则表明双方都收到了对方的Hello包。在多访问网络上, 根据优先权值, 各路由器选择自己网络上的DR。因为算法是固定的, 所以各台路由器选择的DR和BDR也是一致的。

OSPF协议中的毗邻是一种逻辑关系, 并且仅毗邻的路由器之间才直接交换LSA。直接相连的路由器并不一定就具有毗邻关系。OSPF规定, 尽在如下路由器之间建立毗邻关系:

(1) 点到点网络和虚拟链路两端的路由器之间;

(2) 指定路由器 (DR) 和同一网络上的所有其他路由器之间;

(3) 备份指定路由器 (BDR) 和同一网络上的所有其他路由器之间。

综上所述, 链路状态信息由路由器通过扩散报告给所在区域的其他路由器。这样, 每个路由器都可以构架一个它所在区域的链路状态数据库, 利用Dijkstra算法计算出最短路径。主干区域中的路由器也运行这样的过程, 获取区域边界路由器的信息, 计算出从主干到每个非主干区域的最短路径, 并且把这一信息再分发给区域边界路由器, 区域边界路由器再在它的区域内广播该信息。通过这个信息, 区域内部路由器转发至其他区域的分组就可以选择到主干区域的最合适的区域边界路由器。

实际生活中, 最短路径问题有广泛的应用, 运输调度问题、中国邮政员问题等都属于最短路径问题的范畴。因此, 有很多人提出了很多关于最短路径问题的算法, 其中最典型的算法就是Dijstra算法。

摘要：本文主要针对日益复杂的现代通信网络, 利用迪杰斯特拉 (Dijkstra) 算法求出指定的一个源节点到其他各节点的最佳通信路径, 解决了最短路由问题, 从而达到优化通信网络性能的目的。

关键词：最短路径,迪杰斯特拉 (Dijkstra) 算法,OSPF协议

参考文献

[1]严蔚敏, 吴伟民编著.数据结构.北京:清华大学出版社, 1999

[2]张先迪, 李正良.图论及其应用[M].北京:高等教育出版社2005第一版

[3]王朝瑞.图论.国防工业出版社

计算机网络路由选择 篇9

关键词：城域网,OSPF,BGP,RFC

目前城域网所广泛使用的内部网关路由选择协议为OSPF (Open Shortest Path First开放式最短路径优先) , 用来承载城域网内部的路由;使用外部网关路由选择协议为BGP (Border Gateway Protocol边界网关协议) , 用在与省网交互路由。正确部署OSPF与BGP至城域网后, 可保证城域网的正常运行。下面将分别介绍两种OSPF+BGP的部署方式。

1 全网运行OSPF、出口运行BGP路由选择协议的部署方式

1.1 路由发布方式及流量流程

建立城域网模型如图1所示, 下图为典型城域网模型。省网A、省网B隶属省网, 接入各地级城域网核心。

CR1、CR2为市城域网核心设备, 为市级城域网出口。BR1、BR2、BR3、BR4为市城域网汇聚设备, 汇聚业务控制层设备。SR1、Bras1、SR2、Bras2为市城域网业务控制设备。各设备之间链路以下简写为L (设备1设备2) , 如表示CR1至BR1的链路, 则写为L (CR1BR1) ;表示流量通道也简写为L (设备1设备2设备3) , 如表示SR1-BR1-CR1的路径, 则写为L (SR1BR1CR1) 。

省网A、省网B, 运行BGP协议, 二者之间通过静态路由在环回地址上建立IBGP邻居关系, 并通过静态路由在环回地址上分别与城域网核心CR1、CR2建立EBGP邻居关系。城域网核心CR1、CR2运行BGP、OSPF协议, CR1与CR2建立IBGP邻居关系、OSPF邻居关系, CR1分别与城域网汇聚BR1、BR2建立OSPF邻居关系, CR2分别与城域网汇聚BR3、BR4建立OSPF邻居关系。BR1、BR2、BR3、BR4运行OSPF协议, 相互之间两两建立OSPF邻居关系。业务控制SR1、Bras1、SR2、Bras2运行OSPF协议分别与上联城域网汇聚BR建立OSPF邻居关系。

路由宣告时, 省网A、省网B分别通过EBGP向CR1、CR2宣告省网内部路由及默认路由。CR1、CR2通过EBGP向省网A、省网B宣告所在城域网内路由。CR1、CR2分别通过OSPF向BR1、BR2、BR3、BR4强制下发默认路由。BR1、BR2、BR3、BR4分别通过OSPF向CR1、CR2宣告各自路由。BR1、BR2、BR3、BR4分别通过OSPF向所接SR、Bras下发城域网OSPF路由及默认路由。SR、Bras分别通过OSPF向BR宣告所带网段。

此时, 城域网已经可以正常工作。以用户由SR1接入为例, 说明流量出流向。流量出城域网方向, SR1的路由表内会有两条默认路由通往BR1、BR4, 此时流量流入BR1、BR4。通过OSPF的负载分担算法, L (SR1BR1) 和L (SR1BR4) 流量各占50%。BR1、BR4检查路由表, 其默认路由是由CR1、CR2强制下发, 流量会分别传递给CR1、CR2。CR1、CR2的默认路由是由省网A、省网B通过EB-GP下发, 流量最终会通过链路L (CR1省网A) 、L (CR2省网B) 至省网, 并各自分担50%流量。由于目的地址不确定性导致回程流量的不确定性, 可能从省网A回程、或从省网B回程, 或为负载分担省网A、省网B两个方向均有流量。现分开考虑, 如从省网A回程, 省网A将会将流量发送至CR1, CR1通过OSPF学习到路由将流量发送至BR1, 同理BR1发送流量至SR1;从省网B回程, 省网B将流量送至CR2, CR2将流量发送至BR4, BR4发送流量至SR1。

以上说明了全网运行OSPF、出口运行BGP路由选择协议的部署情况, 及正常情况下流量的出入城域网是如何进行的。正常情况下, 此部署方式无任何问题, 即可满足城域网流量需要, 又保证了链路冗余备份。但深入分析后, 会发现此种部署方式有一定弊端。

1.2 OSPF的30分钟刷新LSA的特性过多消耗网络资源

根据“OSPF Version 2”, RFC2328[1]的规定, 为确保数据库的准确性, OSPF每隔30分钟对路由器始发的每条LSA记录扩散 (刷新) 一次, 并将它的序号增加1, 老化时间设置为0。这种间隔被称为LSA的刷新时间 (LSA Refresh Time) 。其他的OSPF路由器一旦收到这个新的拷贝, 就会用这个新的拷贝替换该条LSA通告原来的拷贝, 并使这个新的拷贝的老化时间开始增加。根据这个原则, 无论网络拓扑是否改变, LSA的生存期30分钟必须被重新扩散一次, 此特性在保证域内OSPF数据库一致的情况下也消耗了过多的网络资源[2]。

1.3 单上行链路、出口互联链路故障时产生流量黑洞

1.3.1 当CR1、CR2配置为OSPF强制下发默认路由情况

当L (省网ACR1) 和L (CR1CR2) 同时出现故障时, 以用户在SR1上接入访问省外目的的出流量为例。此时, 由于配置CR1为强制下发默认路由, CR1上行中断后仍旧下发默认路由给BR1, CR2也下发默认路由给BR4。BR1、BR4将转发默认路由给SR1, SR1根据默认路由引导流量送入BR1、BR4。流量给BR4后可以正常通过CR2转发至省网B。但是流量由SR1送给BR1后将出现问题。BR1会根据收到的CR1强制下发的默认路由, 将流量送给CR1, 正常情况下流量应由CR1上送给省网A, 但由于链路中断CR1上没有省网A下发给其的BGP的默认路由。此时, CR1会检查路由表, CR1发现:由于CR1与CR2建立着IBGP邻居关系, 而IBGP邻居关系可通过OSPF协议保持建立状态, 所以CR2收到的EBGP默认路由会以IBGP默认路由的方式转发给CR1。CR1通过此条IBGP的默认路由, 将流量转发给CR2。但由于CR1、CR2之间链路也为故障状态, 流量不能送达。则CR1将根据IGP也就是OSPF的算法, 将流量送给BR1。流量到达BR1后还会以默认路由将流量送回给CR1, 此时产生了流量的黑洞, 当流量的TTL=1时, 流量将被丢弃。SR1始发的出流量将只有50%正常, 另50%将被丢弃。此过程如图2所示。

以上故障情况在OSPF默认路由配置为非强制下发模式下仍旧出现, 下面继续讨论上述故障发生在CR1、CR2配置为OSPF默认路由非强制下发模式。

1.3.2 当CR1、CR2配置为OSPF非强制下发默认路由情况

故障发生后, CR1上行中断, 将收不到省网A发送的EBGP默认路由, 此时按照配置预期, CR1应该不再下发OSPF的默认路由, 即可避免流量黑洞的产生。但是CR1虽然收不到EBGP邻居发送的默认路由, 而与CR2的IBGP邻居关系仍旧存在, CR1上仍旧收到由CR2转发过来的IBGP默认路由。CR1是否可以根据IBGP的默认路由来下发OSPF的默认路由成为关键, 然而RFC2328上并未规定OSPF下发默认路由的触发条件。可分两种情况考虑:

当只有EBGP默认路由为OSPF默认路由下发的条件而IBGP默认路由不能作为OSPF默认路由下发的条件时, CR1不会下发OSPF默认路由, 此时SR1上只收到一条默认路由, 由CR2产生并由BR4转发至SR1, 此时SR1流量将通过L (SR1BR4CR2省网B) , 没有流量黑洞的产生。此过程如图3所示。

当EBGP默认路由、IBGP默认路由都可作为OSPF默认路由下发条件时, CR1仍然会下发默认路由, 流量黑洞产生方式与强制下发情况一样。

由于RFC没有硬性规定, 此特性则和路由器生产厂家对于RFC2328的理解有必然关系。经过对全球最大路由器生产厂家Cisco公司此方面内容的查看, 发现Cisco公司研发的Cisco网络互联操作系统 (Internetwork Operating System, IOS) 中IBGP默认路由是可以触发配置为非强制下发的OSPF路由选择协议下发OSPF默认路由的。通过表1可看出两种OSPF默认路由下发规则在单上行链路、出口互联链路故障时均有出现流量黑洞的隐患。

1.4 回程流量不均衡出现瓶颈

城域网中由于访问目的地的不确定性导致了回程流量的不均衡性。出城域网流量由核心下发的默认路由引导, 所以出流量在双出口处为负载分担流出。但回程流量则没有这个属性, 鉴于此类问题, 在网络设计初期需要考虑到, 但由于不均衡性总是在发生着偏移[3], 所以省网也会针对不同时期, 对城域网的回程流量做一些调整。但省网的调整, 相对于城域网内设备来说, 颗粒度太大, 一般以GB为单位进行流量调整。而城域网并无有效的流量调整方式, 如下面一种情况:

城域网中针对SR1下接入用户的流量30%由L (省网ACR1) 流入, 70%由L (省网BCR2) 流入。CR1、CR2根据OSPF路由表, 将流量分别送给BR1、BR4。以至L (BR1SR1) 流量为30%, L (BR4SR1) 的流量为70%。假定SR1下接入用户峰值, 两省中继总流量为4Gbits/s, 为保证链路的资源合理利用, L (SR1BR1) 设计容量为2GB, L (SR1BR4) 设计容量为4GB。当流量按照30%、70%流入时, L (SR1BR1) 峰值流量为1.2Gbits/s, L (SR1BR4) 峰值流量为2.8Gbits/s, 均在每条链路的合理利用率之内。但如果此时流量方向发生偏移, 两出口入流量均分, 即50%由L (省网ACR1) 流入, 50%由L (省网BCR2) 流入时, L (SR1BR1) 、L (SR1BR4) 峰值流量将均为2Gbits/s, L (SR1BR1) 峰值流量将达到100%。此过程如图5所示。

上述三种问题:OSPF的30分钟刷新LSA的特性过多消耗网络资源、核心层故障后产生流量黑洞、回程流量不均衡出现瓶颈。在全网运行OSPF、出口运行BGP部署方案中, 并未有较好的解决方法。

2 全网部署OSPF+BGP路由选择协议

针对上述全网运行OSPF、出口运行BGP部署方式出现的问题, 使用全网部署OSPF+BGP路由选择协议可以很好的解决这三种问题。

2.1 路由发布方式及流量流程

在图一的典型城域网模型中, OSPF只用来承载城域网内设备的互联地址及环回地址, 保证各个城域网设备的连通性, 而不用其进行承载城域网内用户路由。所有城域网内设备启用BGP路由选择协议, BR3、BR4配置为RR, BR3、BR4建立IBGP邻居关系, CR1、CR2、BR1、BR4、SR1、SR2、Bras1、Bras2均通过环回地址分别与RR (BR3、BR4) 的环回地址建立IBGP邻居关系并作为路由器反射客户端, CR1、CR2通过环回地址建立IBGP邻居关系。IBGP用于承载用户路由。部署完毕后, 此模型可正常进行城域网流量的转发。

以SR1接入用户访问省外网络的出入流量为例, CR1、CR2分别通过EBGP收到省网A、省网B下发的默认路由, CR1、CR2以IB-GP转发默认路由给RR (BR2、BR3) , 由RR将默认路由反射给SR1。此时SR1收到两条IBGP的默认路由, 下一跳分别为CR1、CR2。SR1通过OSPF协议递归查找到两个CR1、CR2, 将数据负载分担分别送至BR1、BR4。BR1、BR4通过RR也会收到CR1、CR2的IBGP默认路由, 并通过OSPF迭代各自的下一跳, 将流量送至CR1、CR2, 后再由CR1、CR2分别送至省网A、省网B。SR1将自己承载的用户路由以IBGP方式通告给RR, 再由RR反射给CR1、CR2, CR1、CR2以EBGP方式通告给省网A、省网B。回程流量则分别使用L (省网ACR1BR1SR1) 、L (省网BCR2BR4SR1) 两条链路回程。

以上例子, 说明了全网部署BGP的路由通告过程及流量引导方式。下面则针对全网运行OSPF、出口运行BGP部署方式下不能解决的三个问题进行论述。

2.2 解决OSPF的30分钟刷新LSA的特性过多消耗网络资源的问题

全网部署OSPF+BGP路由选择协议, 使用IBGP来承载用户路由, 而OSPF只进行城域网中设备连通性的保证。则不会有大量的OSPF的LSA产生。根据RFC1771[4], BGP采用增量的路由更新, 即只有网络拓扑变更或通告属性发生变化时才会产生路由更新。所以, 使用全网部署OSPF+BGP路由选择协议时, OSPF只有少量的互联、设备环回地址的LSA, 不会因为30分钟的刷新LSA过多消耗网络资源。

2.3 解决单上行链路、出口互联链路故障时产生流量黑洞的问题

当L (省网ACR1) 和L (CR1CR2) 同时出现故障时, 以用户在SR1上接入访问省外目的的出流量为例。此时, CR1不能收到省网A通过EBGP下发的默认路由, CR2通过省网EBGP学到的默认路由会以IBGP的形式更新给CR1, CR1会学到CR2的IBGP默认路由, 根据IBGP的通告原则, CR1收到IBGP邻居学到的路由不会通告给其他的IBGP邻居即RR (BR2、BR3) , 则RR只会将CR2的IB-GP默认路由反射给SR1。SR1上只有一条IBGP默认路由, 下一跳为CR2, SR1通过OSPF路由表递归查询到下一跳为BR4, BR4通过OSPF迭代查找到下一条为CR2则流量通过L (SR1BR4CR2省网2) 。

根据上述路由发布及流量引导过程, 全网运行OSPF、出口运行BGP部署方式中产生的流量黑洞被完全避免了。

2.4 解决回程流量不均衡出现瓶颈的问题

继续讨论2.3章节出现的流量瓶颈, 出现流量瓶颈后, 可在根据SR1上所接入用户地址进行流量调整。根据A Border Gateway Protocol 4 (BGP-4) ”RFC1771关于LOCAL_PREF的选路定义[4], 通过向CR1、CR2分别通告SR1下接入用户路由的LOCAL_PREF不同, 可对回程流量进行调整。假设SR1下接入用户地址段为A的流量50%由省网A回程、50%由省网B回程, 目的减小L (BR4SR1) 链路的流量时, 在BR1上通告地址段A给RR (BR3、BR4) 的LOCAL_PREF设置为200。设置完成后, CR1、CR2的BGP路由表中网段A的路由条目各有两个:从SR1上学习到的LOCAL_PREF为100 (默认值) , 从BR1上学习到的LOCAL_PREF为200。通过RFC规定, CR1、CR2将优选BR1作为到达目的网段A的下一跳。CR1将流量送至BR1, BR1通过OSPF迭代查找到下一跳地址为SR1, 将流量送至SR1。CR2通过OSPF迭代查找下一跳BR1, 通过两条链路L (CR2CR1BR1) 和L (CR2BR4BR1) 进行负载均衡, 流量送至BR1后, BR1通过OSPF迭代查找, 将流量送至SR1。流量使用L (CR2CR1BR1SR1) 、L (CR2BR4BR1SR1) 、L (CR1BR1SR1) 两条链路, 使得网段A的回程流量不经过L (BR4SR1) , 将可以减轻某些压力过大链路上的流量压力。

上述流量调整实例可看出, 通过更改通告的LOCAL_PREF属性, 即可对城域网内回程路由不均衡进行调整。

3 展望

随着MPSL L3 VPN业务的日益发展, 大量的用户VPN路由将依靠MP-BGP进行更新, 因此部署BGP至城域网设备成为必然, 虽然部署MP-BGP对于IPv4协议簇并未有影响即对于现网业务没有影响, 但是随着IPv4路由迁移, 将全网运行OSPF、出口运行BGP路由协议改造为全网运行OSPF+BGP路由选择协议是一个对现网改造的过程, 这会影响现网业务。所以此工程涉及面广, 工作量大, 影响范围远, 需要进行详细的分析及考虑才可进行。

参考文献

[1]J.Moy, OSPF Version 2, RFC2328, April 1998.

[2]施文辉.IP城域网优化方案研究与实施案例[M].北京:北京邮电大学, 2008.35-37.

[3]Liang Ben-lai1, Yang Zhong-ming2, DENG Jia-bin1, Load Balance Algorithm of Multiple Links Based on Traffic Schedule, Computer En gineering[J], 2011 (9) :118-119.