路由交换协定【路由交换协定】路由系统将整个网际网路划分为许多个自治系统的集合，每个自治系统由一个16bit的号码来表示 。自治系统在域边界之内运行局部路由协定或内部网关协定(IGP，Interior Gateway Protocol)，例如RIP、IGRP、EIGRP、OSPF等，以维持一个一致的网路拓扑结构视图；而在域边界之间则通过执行一种称为边界网路协定(BGP，Border Gateway Protocol)的外部网关协定(EGP，Exterior Gateway Protocol)来构成一个全局的连通域，如图1所示 。
图1网际网路路由结构
基本介绍中文名：路由交换协定
路由算法路由协定按路由算法一般划分为距离向量协定和链路状态协定两类 。距离向量协定，也称为Bellman-Ford算法，是指使用中继计数表示源节点到目的节点的距离，它基于下面的计算公式来计算两个节点间距离：D(i，i)=0D(i，j)=min[d(i，k)+D(k，j)]其中，D(i，j)表示从节点(节点为网路或路由器)i到节点j的最短路径，d(i，k)表示从节点i到k的直接路径，也就是说，节点i和k之间没有中介节点 。具体运算步骤如下：①所有的路由器都建有一个路由表，使系统中的所有目的地址都出现在表中，每一个表项内容均包括目的地址和下一站地址，记为元组(N，G) 。②路由器周期性地向邻居传送更新分组，更新分组的内容为路由表中的所有信息 。③邻居路由器接收处理更新分组 。设更新分组来自G'，根据更新分组计算到目的地址N的路由开销为D'，如果D'<D，则採用新的路由(N，G') 。如果当前路由表中存放的相应的下一站地址为G'，即G'=G，则採用新的路由，不管D'是大还是小 。距离向量协定的优点是内部保存状态少，网路负担轻；缺点是用中继计数表示距离不準确，不能反映链路的真实状态；收敛速度缓慢，如一条链路中断后，需要经过相当长时间才被发现 。链路状态协定，也称最短路径算法，其计算原理可以分为以下4个过程来描述：①发现该路由器的邻居，获取它们的网路地址，建立相邻关係，并测量到每个相邻路由器的开销或延迟 。建立相邻关係是通过传送Hello分组来实现的 。②将用于交换的信息收集起来，构造包含这些信息的链路状态讯息 。创建链路状态讯息的时机分两种，一种为定期创建，另一种就是当有事件发生时创建 。③通过flood(扩散)算法，向所有的其他路由器传送该讯息 。在链路状态路由选择算法中，如何可靠地发布链路状态讯息包是相当重要的 。链路状态算法实现的好坏在一定程度上取决于flood算法的优劣 。④根据收集到的链路状态信息，通过Dijkstra算法计算本路由器到全网其他路由器或网路的最短距离 。链路状态协定与距离向量协定相比，其优点是基于量度值(如链路频宽和时延)，而不是由中继计数来选择最佳化路由，因此可使网路负载平衡；通过链路状态更新，将链路和节点状态的变化情况扩散到整个网路，使所有路由器马上更新路由表，使网路具有更好的收敛特性 。内部网关协定RIPRIP(RoutingInformationProtocol)是一种距离向量协定，是当今套用最为广泛的内部网关协定 。在默认情况下，RIP使用一种非常简单的度量制度：距离就是通往目的站点所需经过的链路数，取值为1～15，数值16表示无穷大 。RIP进程使用UDP的520连线埠来传送和接收RIP分组 。RIP分组每隔30s以广播的形式传送一次，为了防止出现“广播风暴”，其后续的分组将做随机延迟后再传送 。在RIP中，如果一个路由在180s内未被刷新，则相应的距离就被设定成无穷大，并从路由表中删除该表项 。RIP分组分为两种：请求分组和回响分组 。由于RIP1存在一些缺陷，因此RIP2试图定义一套有效的RIP改进方案，例如子网路由选择、支持无类型域间路由(CIDR，ClasslessInter-DomainRouting)、验证机制和多点广播等，并且还定义了过渡策略 。但RIP2是一个兼容性的升级，也就继承了RIP1的大部分缺点 。OSPF为了解决RIP协定的缺陷，IETF于1998年4月在RFC2328中发布了OSPF协定的第二版(OSPFv2) 。OSPF(OpenShortest-PathFirst)全称为开放式最短路径优先协定，OSPF中的O意味着OSPF标準是对公共开放的，而不是封闭的专有路由方案 。OSPF採用链路状态协定算法，每个路由器维护一个相同的链路状态资料库，保存整个AS的拓扑结构(在自治系统不再划分的情况下) 。一旦每个路由器都有了完整的链路状态资料库之后，该路由器就可以自己为根构造最短路径树，然后再根据最短路径构造路由表 。对于大型的网路，为了进一步减少路由协定通信流量，利于管理和计算，OSPF将整个自治系统划分为若干个区域，区域内的路由器维护一个相同的链路状态资料库，保存该区域的拓扑结构 。OSPF路由器相互间交换信息，但它们交换的信息不是路由，而是链路状态 。OSPF定义了5种分组：Hello分组用于建立和维护连线；资料库描述分组用于初始化路由器的网路拓扑资料库，当发现资料库中的某部分信息已经过时时，路由器传送链路状态请求分组，请求相邻节点提供更新信息；路由器使用链路状态更新分组来主动扩散自己的链路状态资料库或对链路状态请求分组进行回响；由于OSPF直接运行在IP层，协定本身要提供确认机制，链路状态应答分组是对链路状态更新分组的确认 。与其他协定相比，OSPF有许多优点 。例如，OSPF支持各种不同鉴别机制(如简单口令验证、MD5加密验证等)，并且允许各个系统或区域採用互不相同的鉴别机制；提供负载均衡功能，如果计算到某个目的站有若干条费用相同的路由，OSPF路由器则会把通信流量均匀地分配给这几条路由，沿这几条路由把该分组传送出去；在一个自治系统内可划分出若干个区域，每个区域根据自己的拓扑结构计算最短路径，可以减少OSPF路由实现的工作量；OSPF属动态的自适应协定，对于网路的拓扑结构变化可以迅速地做出反应，并进行相应调整，提供短的收敛期，使路由表儘快稳定，并且与其他路由协定相比，OSPF在对网路拓扑变化的处理过程中仅需要最少的通信流量；OSPF提供点到多点的接口，支持CIDR地址 。OSPF的不足之处就是协定本身庞大複杂，实现起来较RIP困难 。IS-IS协定和OSPF一样，IS-IS也包含一些子协定 。其中，Hello协定用来发现邻机，在广播链路上选举指派路由器；扩散协定用来在区域或主干中传播链路状态记录 。IGRP由于RIP的局限性，Cisco公司在20世纪80年代中期开发了IGRP(InteriorGatewayRoutingProtocol)，它是一个距离向量家族的路由协定 。IGRP使用组合度量制式，其路由更新的每一项都包含了一组4种度量制式：延迟(D)、频宽(B)、可靠性(R)和负载(L) 。此外，它还包括2个不参与路径计算的变数：路由中的跳数(H)和路径MTU的计算结果 。IGRP的更新传送间隔更长(90s)，使用组合度量制式，可选择多路径路由、环路检测和处理默认路由的新手段 。IGRP最大的缺点是它为Cisco私有，故仅局限于Cisco产品，而RIP是任何平台上IP路由的一部分 。EIGRPIGRP存在的缺点是它的环路检测会持续较长时间，且路由更新的周期性传送也会造成同样效应 。因此Cisco公司还开发了EIGRP(EnhancedlnteriorGatewayRoutingProtocol) 。EIGRP仍是一个距离向量协定，使用了与IGRP相同的组合度量制式，除此之外就没什幺相似之处了 。EIGRP使用了扩散计算系统，保持快速收敛、避免环路产生 。EIGRP比传统的距离向量协定使用更少的频宽 。这使它适用于低频宽、高费用WAN链路 。最重要的是，EIGRP不仅可用于IP，而且还可用于IPX和AppleTalk 。外部网关协定早期的网际网路最初採用一种外部网关协定(EGP，ExteriorGatewayProtocol)的 。EGP是为一个简单的树形拓扑结构设计的 。随着网际网路的迅速扩大，EGP逐渐暴露出了很多的局限性，如不能处理环路和多个网路网状连线等情况 。为了克服EGP的局限性，IETF制定了实际上现已成为标準的边界网关协定(BGP，BorderGatewayProtocol) 。BGP经历了不同的阶段，从最早的版本BGP1发展到了当前的版本BGP4 。BGP4是第一个支持CIDR的版本 。BGP是一种用于在自治系统之间传递路由信息的路径向量协定 。路径向量的含义是指BGP路由讯息中带有一个自治域号码的序列，它说明了一条路由所通过的路径，这样可有效地检测并避免複杂拓扑结构中可能出现的环路问题 。BGP支持CIDR定址方式，减少了路由表长度，从而加快了选路速度 。另外，BGP使用TCP作为其传输协定(预设连线埠号为179)，这保证了传输的可靠性，由于差错控制功能全部由TCP协定完成，因此BGP自身的实现就变得非常简单 。BGP协定在TCP连线上传送4种讯息类型，包括：Open分组用来建立对等体连线；Update讯息用来在BGP对等体之间传输路由信息；Keepalive讯息用于周期性刷新对等体连线，以确保连线的有效性；Notification讯息用于通知其他BGP对等体检测到一个差错 。BGP协定的运行分为建立对等体连线和路由更新处理两个阶段 。BGP进程的对等体连线建立过程可用如图2所示的有限状态机模型来表示 。图2BGP对话的有限状态机模型①空闲状态：这是连线的第一阶段 。BGP进程等待一个通常由网路管理员发出的启动事件，然后BGP初始化资源，复位连线重试计数器，打开一个TCP连线连线埠，并开始监听可能由远程对等体启动的连线，若成功，就转换到连线状态，否则将回到空闲状态 。②连线状态：BGP进程等待TCP连线的建立 。如果TCP连线已建立，就转换到OPEN传送状态，同时传送OPEN讯息 。如果TCP连线没有建立，那幺将转换到行动(active)状态 。如果连线重试计时器溢出，状态就停留在连线阶段，计时器将被复位，一个TCP连线请求被启动 。③行动状态：BGP进程建立一个TCP连线，获得一个对等体 。若成功，则转换为Open传送状态，同时传送Open讯息 。如果TCP连线计时器溢出，那幺BGP进程将重新设定计时器，并回到连线状态 。一般地，如果BGP进程的状态在连线与行动之间来回变化，则表明存在故障，不能建立TCP连线 。这可能是因为对等体的IP位址不可达 。④Open传送状态：BGP进程等待接收来自对等体的Open讯息 。若收到Open讯息，就对Open讯息进行正确性检查：如果没有错误，就转换为Open确认状态，同时开始传送Keepalive讯息，并且复位Keepalive时钟；否则，传送Notification讯息，转换到空闲状态 。在这个阶段，BGP进程比较对等体的自治域号码，以确认对等体是内部对等体还是外部对等体 。⑤Open确认状态：BGP进程等待一个Keepalive或Notification报文 。如果收到Keepalive报文，就进入对等已建立状态，表示对等体连线已建立；如果收到Notification报文，则回到空闲状态 。⑥已建立状态：BGP进程与对等体交换Update或Keepalive数据包，假设Keepalive计时器的值不是零，那幺当收到Update或Keepalive数据包时，计时器将复位 。如果收到任何Notification报文，则说明系统出现错误，将就回到空闲状态 。路由更新处理是BGP协定的核心 。当BGP收到一个Update讯息时，首先验证Update数据包的有效性，若Update讯息内没有错误信息，那幺就调用图3所示的路由更新处理过程 。一个Update讯息或者通告一条可达路由，或者撤销多条不再可达路由 。对于不可达路由，BGP将从BGP路由表或路由信息库的输入路由表中删除这些不可达路由，然后再调用决策过程处理 。对于收到的可达路由信息，BGP将根据输入路由策略进行路由过滤及属性控制 。例如，BGP要过滤从一个对等体收到的一条路径的某个自治域号码，为了防止流量通过该对等体到达该自治网路，输出的路由将存储到BGP路由表或路由信息库的输入路由表中 。BGP决策过程基于路径属性值，在多条可达路由中选择一条到达某个目的地的最佳路由 。BGP协定使用的一些重要的路径属性包括：①起源(Origins)：表示一条路由的起源，如由外部BGP获取，或者由内部路由协定输入等 。图3BGP路由更新处理过程②自治系统路径(AS_Path)：一条路由到达一个目的地址所经过的一系列自治系统号码 。③下一段地址(Next-hop)：到达一个网路的下一跳地址 。④多出口判别(MULTI_EXIT_DISC)：用于提示进入一个多入口自治系统的入口优先权 。⑤本地优先(LOCAL_PREF)：用于自治系统内部到达某一地址出口点的优先权 。BGP决策过程分为以下几个步骤：①如果下一段地址是不可达的，这路由就要被忽略；②优先选择最大本地优先的路由；③如果本地优先相同，优先选择本地始发的路由；④如果本地始发相同，优先选择具有最短自治系统路径的路由；⑤如果自治系统路径相同，优先选择具有低起源属性的路由；⑥如果起源属性相同，优先选择具有最低多出口判别属性值的路由；⑦如果以上情况都相同，优先选择可通过最近对等体到达的路由 。由以上决策过程产生的最佳路由是路由器本身使用的，将被存储到BGP路由表的内部使用路由表中，同时输入到路由转发表 。BGP路由表中内部使用路由表的路由以及路由器在本地产生的路由需要通告给其他的对等体 。在送出更新讯息以前，要套用输出策略进行路由过滤及属性控制 。例如，自治系统记忆体在多个入口，给各个入口设定不同的多出口判别属性来调整各个入境流量的大小 。另外，还需区别内部和外部对等体，例如从内部对等体得知的路由不应传送到内部对等体 。总之，BGP协定是一种基于策略的路由协定，虽然协定本身相对简单，但配置相当複杂，若使用不当，则有可能影响其他网路 。更详细的BGP协定内容及套用指导参见IETFRFC1771、RFC1773等 。