bgp的路由算法

Ⅰ BGP协议最佳路径的选择算法有哪些

每个BGP路由器通过邻居声名与周边的一个或多个路由器连接。一旦建立了邻居关系，这些BGP路由器之间就会相互交换路由信息。据我最近一次统计，整个互联网上有大约12.5万个路由信息，因此要配备一个强大的路由器才能将所有BGP路由信息接收下来。
由于整个互联网的BGP路由表有超过20万个路由，同时一个BGP路由器可能从多个来源收到多份的路由表，因此肯定会有一种方法可以比较不同的BGP路由表，并从中选择最佳的路由方案。这种方法就是BGP最佳路径选择算法。
可能你会注意到，CiscoBGP路由器会将应用权重（weight）作为路由表的第一标准，而其它品牌的路由器则不是这样。Cisco的官方BGP最佳路径选择算法文档中详细列明了所参考的各项标准。接下来我会列出每种标准并给出解释和范例。
默认情况下，BGP最佳路径都是基于最短自治系统（AS）的原理得出的。不过很多时候，诸如weight，localpreference以及MED这样的标准都是网络管理员自行设定的。
接下来我们就按照BGP选择最佳路径的参考顺序将这几项标准介绍一下：
#1 Weight —权重是Cisco为本地路由器设定的自定义参数，并不随路由器更新而变化。如果指向某一IP地址的路径有多条（这很常见），那么BGP会寻找权重最高的路径。设定权重的参考因素很多，包括邻居命令，as-path访问列表，或者路由镜像等。
#2 Local Preference — 本地出口优先级参数会告知AS哪条路径具有本地优先，数值越高优先级越高。默认为100。比如：
bgp default local-preference 150
#3 Network or Aggregate—这个参数会选择本地发起的网络或聚合作为路径。将特定的路径加入路由中，会让路由更有效率，同时也节省了网络空间。更多有关聚合的信息，可以参考Cisco的文章“UnderstandingRouteAggregation in BGP.”
#4 Shortest AS_PATH — BGP 只有在weight， localpreference和locallyoriginated相当接近的时候才使用这个参数。
#5 Lowest origin type — 这个参数处理Interior Gateway Protocol（IGP）协议的优先级低于 Exterior Gateway Protocol （EGP）协议。
#6 Lowest multi-exit discriminator （MED） — 较低的MED值要优于较高的MED值。
#7 eBGP over iBGP — 类似于#5， BGP AS Path 更倾向 eBGP 而不是 iBGP。
#8 Lowest IGP metric — 这个参数倾向于采用最低IGP作为BGP下一跳。
#9 Multiple paths — 这个参数决定是否要在路由表中装入多个路径。可以参考 BGPMultipath获取更多信息。
#10 External paths — 当所有路径都为外部路径时，选择首先接收到的路径（较老的路径）。
#11 Lowest router ID — 选择来自具有最低路由器ID的BGP路由器的路径。
#12 Minimum cluster list — 如果多个路径的originator或路由器ID相同，选择cluster列表长度最短的路径。

Ⅱ 什么是路由啊 路由的组成 以及路由的算法

路由：路由（routing）是指分组从源到目的地时，决定端到端路径的网络范围的进程。路由工作在OSI参考模型第三层——网络层的数据包转发设备。路由器通过转发数据包来实现网络互连。虽然路由器可以支持多种协议（如TCP/IP、IPX/SPX、AppleTalk等协议），但是在我国绝大多数路由器运行TCP/IP协议。路由器通常连接两个或多个由IP子网或点到点协议标识的逻辑端口，至少拥有1个物理端口。路由器根据收到数据包中的网络层地址以及路由器内部维护的路由表决定输出端口以及下一跳地址，并且重写链路层数据包头实现转发数据包。路由器通过动态维护路由表来反映当前的网络拓扑，并通过网络上其他路由器交换路由和链路信息来维护路由表。

路由器的组成：

1. RAM（随机存储器）

   功能：存放路由表；存放ARP告诉缓存；存放快速交换缓存；存放分组交换缓冲；存放解压后的IOS；路由器加电后，存放running配置文件；

   特点：重启或者断电后，RAM中的内容丢失。

2. NVRAM（非易失性RAM）

   功能：存储路由器的startup配置文件；存储路由器的备份。

   特点：重启或者断电后内容不丢失。

3. FLASH（快速闪存）

   功能：存放IOS和微代码。

   特点：重启或者断电后内容不丢失；可存放多个IOS版本（在容量许可的前提下）；允许软件升级不需替换CPU中的芯片。

4. ROM(只读存储器)

   功能：存放POST诊断所需的指令；存放mini-ios；存放ROM监控模式的代码。

   特点：ROM中的软件升级需要更换CPU的芯片（还好这种情况比较少遇到)

5. CPU（中央处理器）

   衡量路由器性能的重要指标，负责路由计算，路由选择等。

6. 背板：

   背板能力是一个重要参数，尤其在交换机中。

路由算法：又名选路算法，可以根据多个特性来加以区分。算法的目的是找到一条从源路由器到目的路由器的“好”路径（即具有最低费用的路径[1]）。算法设计者的特定目标影响了该路由协议的操作；具体来说存在着多种路由算法，每种算法对网络和路由器资源的影响都不同；由于路由算法使用多种度量标准（metric），从而影响到最佳路径的计算。

算法分类：主要有RIP、IGRP（IGRP为 Cisco公司的私有协议）；链路状态路由协议基于图论中非常着名的Dijkstra算法，即最短优先路径（Shortest Path First， SPF）算法，如OSPF。在距离向量路由协议中，路由器将部分或全部的路由表传递给与其相邻的路由器；而在链路状态路由协议中，路由器将链路状态信息传 递给在同一区域内的所有路由器。 根据路由器在自治系统（AS）中的位置，可将路由协议分为内部网关协议 （Interior Gateway Protocol，IGP）和外部网关协议（External Gateway Protocol，EGP，也叫域 间路由协议）。域间路由协议有两种：外部网关协议（EGP）和边界网关协议（BGP）。EGP是为一个简单的树型拓扑结构而设计的，在处理选路循环和设置 选路策略时，具有明显的缺点，已被BGP代替。