EEPW论坛

国家数字交换系统工程技术研究中心 周文辉 丁利剑 唐健 摘 要:首先对路由技术的发展和要求进行了介绍，接着讨论了两种主要的路由算法，最后主要对ＲＩＰ、ＯＳＰＦ和ＢＧＰ路由协议进行了介绍。 关键词:Ｉｎｔｅｒｎｅｔ 路由 ＲＩＰ ＯＳＰＦ ＢＧＰ 所谓路由技术，简单而言就是采用一种或多种策略，为数据分组从源地址到目的地址的转发选择一条或几条理想的路径。路由技术是通过在路由设备（如路由器等）上运行路由协议来实现的。通过路由器相互间的通信，每个路由器都建立一个路由表，存放网络的路由转发信息。当路由器转发数据分组时，首先根据数据分组的目的地址查找路由表表项，然后按表项中提供的相应下一站的地址对该数据分组进行转发。 路由技术是计算机和通信技术相结合的产物，它随着网络的迅速发展而发展。在各种网络中，Ｉｎｔｅｒｎｅｔ的发展对路由技术的革新起到了关键的作用。在Ｉｎｔｅｒｎｅｔ发展的初期，它是以ＡＲＰＡＮＥＴ为核心的核心系统结构，其他网络通过核心路由器与ＡＲＰＡＮＥＴ主干网相连。当时的路由协议比较单一，功能也比较简单，比较典型的路由协议有ＲＩＰ-1和ＥＧＰ。但随着网络数量的增长，仍然要求其他网络与核心系统相连，这既不现实也不可能。于是非核心系统体系结构应运而生，并引入了ＡＳ（自治系统，Ａｕｔｏｎｏｍｏｕｓ ｓｙｓｔｅｍ）概念。这种非核心系统体系结构将整个Ｉｎｔｅｒｎｅｔ划分为许多ＡＳ，每个ＡＳ由不同的机构运营管理，在其内部使用自己的路由协议，并且可以独立于其他ＡＳ所选用的路由协议，随之产生了ＲＩＰ-2，ＯＳＰＦ和ＢＧＰ4为代表的一批路由协议。 路由技术发展到现在，很好地实现了异种网络之间互连的目的。以ＴＣＰ/ＩＰ协议簇为基础，几乎可以进行任何异种网络间的互连。相对于ＲＩＰ-1，ＥＧＰ等早期路由协议，以ＲＩＰ-2，ＯＳＰＦ和ＢＧＰ4为代表的路由协议在安全性、灵活性、稳定性和可扩展性等方面有了极大的改善。 1 现代路由技术的要求 随着Ｉｎｔｅｒｎｅｔ的发展，新业务不断出现，网络数量和规模不断增长，给路由技术提出了新的要求。 1.1 路由技术和交换技术相互结合 在过去的20多年中，路由技术和交换技术都得到了充分的发展。但随着网络流量的高速增长，路由器的处理速度低下以及交换机无法适应众多新业务等问题也日益暴露出来。在这种情况下，多种多层交换技术被提出。但无论是Ｃｉｓｃｏ的标签交换，还是ＮＯＫＩＡ/Ｉｐｓｉｌｏｎ的ＩＰ ｓｗｉｔｃｈ技术，其基本实现方法均是将ＩＰ层的智能路由能力与第二层的快速交换能力融合在一起。无论采用哪一种交换技术，都离不开路由技术，离不开现有的路由协议，只是与第二层交换功能结合得更为紧密。 1.2 支持ＣＩＤＲ（无类域间路由） 目前的ＩＰ地址总长度为32ｂｉｔ，总共能提供210万个网络号，37亿个主机地址。但随着Ｉｎｔｅｒｎｅｔ的迅猛发展，局域网数量和主机数量急剧增长，地址耗尽问题迫在眉睫。同时随着网络数量的增长，路由表表项增长过快。因为从路由器的观点来看，ＩＰ地址空间是一个由网络号和主机号组成的两级结构，路由表中不必包含所有主机的地址信息，但必须知道所有的网络。如果有50万个Ｃ类网络地址，则Ｉｎｔｅｒｎｅｔ上的每个主干路由器都要保存一个有50万个表项的路由列表，这将导致与路由表管理相关的算法复杂度会超线性地增长。而ＣＩＤＲ以可变长分块的方式分配所剩的Ｃ类网络地址，将几个连续的Ｃ类网络地址压缩为一个表项，这可以缓解一下地址耗尽和路由表表项增长过快问题的解决，也就要求路由协议支持ＣＩＤＲ方案。 1.3 支持组播传送 通过Ｉｎｔｅｒｎｅｔ向小组内的每个成员发送消息的事件时有发生，尤其在多媒体应用方面。如果组的规模较小，它可以通过点到点的方式向其他成员发送消息；如果组太大，这种策略会造成带宽的极大浪费。组播（点到多点）方式仅在必要的时候才复制数据分组，这使网络负载大大减少。另一方面，采用支持组播的路由协议还需允许进行资源发现。为了支持组播传送能力，需要开发相应的路由算法和路由协议。 1.4 网络攻击给路由安全提出了要求 最初的计算机网络应用范围狭小，主要是针对科研人员和公司职员而言，所以在安全性问题上并未给予足够的重视。随着越来越多的用户开始通过网络办理各项业务，路由信息被攻击和篡改事件屡见不鲜，路由的安全性已成为一个不容忽视的大问题。这就要求路由协议支持一定的安全机制，如数字签名和ＭＤ5等。 2 路由算法 路由算法形式多样，得到广泛应用的有两种：距离向量算法和链路状态算法。目前大多数路由协议都是基于这两种路由算法之一。 2.1 距离向量算法（ｄｉｓｔａｎｃｅ ｖｅｃｔｏｒ ａｌｇｏｒｉｔｈｍ） 距离向量算法是基于下面的计算公式： Ｄ（ｉ，ｉ） ＝ 0 Ｄ（ｉ，ｊ） ＝ ｍｉｎ ［ｄ（ｉ，ｋ）＋Ｄ（ｋ，ｊ）］ 其中，Ｄ（ｉ，ｊ）表示从节点（节点为网络或路由器）ｉ到节点ｊ的最短路径，ｄ（ｉ，ｋ）表示从节点ｉ到ｋ的直接路径，也就是说节点ｉ和ｋ之间没有中介节点。具体运算步骤如下： （1） 所有的路由器建有一个路由表，使系统中的所有目的地址都出现在表中。每一表项内容包括目的地址和下一站地址，记为元组（Ｎ，Ｇ）。 （2） 路由器周期性地向邻居发送更新分组，更新分组的内容为路由表中的所有信息。 （3） 邻居路由器接收处理更新分组。 设更新分组来自Ｇ’，根据更新分组计算到目的地址Ｎ的路由开销为Ｄ’，如果Ｄ’＜Ｄ，采用新的路由（Ｎ，Ｇ’）。如果当前路由表中所存放的相应下一站地址为Ｇ’，也就是Ｇ’ ＝Ｇ，采用新的路由，不管Ｄ’是大或小。 2.2 链路状态算法（ｌｉｎｋ ｓｔａｔｅ ａｌｇｏｒｉｔｈｍ） 链路状态算法，或者称为ＳＰＦ（Ｓｈｏｒｔｅｓｔ-Ｐａｔｈ Ｆｉｒｓｔ）算法，其思路可以分为以下4个部分来描述： （1） 发现该路由器的邻居，获取它们的网络地址，建立相邻关系，并测量到每个相邻路由器的开销或延迟。建立相邻关系是通过发送Ｈｅｌｌｏ分组来实现的。 （2） 将用于交换的信息收集起来，构造包含这些信息的链路状态分组。创建链路状态分组的时机分两种，一种为定期创建，另一种就是当有事件发生时创建。 （3） 通过ｆｌｏｏｄ（扩散）算法，向所有的其他路由器发送该分组。如何可靠地发布链路状态分组在链路状态路由选择算法中占相当大的比重，链路状态算法实现的好坏在一定程度上取决于ｆｌｏｏｄ算法的优劣。 （4） 根据收集到的链路状态信息，通过Ｄｉｊｋｓｔｒａ算法，计算本路由器到全网其他路由器或网络的最短距离。 3 路由协议 路由协议作为ＴＣＰ/ＩＰ协议簇中重要成员之一，其选路过程实现的好坏会影响整个Ｉｎｔｅｒｎｅｔ网络的效率。按应用范围的不同，路由协议可分为两类：在一个ＡＳ内的路由协议称为内部网关协议（ｉｎｔｅｒｉｏｒ ｇａｔｅ-ｗａｙ ｐｒｏｔｏｃｏｌ），ＡＳ之间的路由协议称为外部网关协议（ｅｘｔｅｒｉｏｒ ｇａｔｅｗａｙ ｐｒｏｔ ｏｃｏｌ）。这里网关是路由器的旧称。 现在正在使用的内部网关路由协议有以下几种：ＲＩＰ-1，ＲＩＰ-2，ＩＧＲＰ，ＥＩＧＲＰ，ＩＳ-ＩＳ和ＯＳＰＦ。其中前4种路由协议采用的是距离向量算法，ＩＳ-ＩＳ和ＯＳＰＦ采用的是链路状态算法。对于小型网络，采用基于距离向量算法的路由协议易于配置和管理，且应用较为广泛。但在面对大型网络时，不但其固有的环路问题变得更难解决，所占用的带宽也迅速增长，以至于网络无法承受。对于大型网络，采用链路状态算法的ＩＳ-ＩＳ和ＯＳＰＦ较为有效，并且得到了广泛的应用。ＩＳ-ＩＳ与ＯＳＰＦ在质量和性能上的差别并不大，但ＯＳＰＦ更适用于ＩＰ，较ＩＳ-ＩＳ更具有活力。ＩＥＴＦ始终在致力于ＯＳＰＦ的改进工作，其修改节奏要比ＩＳ-ＩＳ快得多。这使得ＯＳＰＦ正在成为应用广泛的一种路由协议。现在不论是传统的路由器设计，还是即将成为标准的ＭＰＬＳ（多协议标记交换），均将ＯＳＰＦ视为必不可少的路由协议。 外部网关协议最初采用的是ＥＧＰ。ＥＧＰ是为一个简单的树形拓扑结构设计的。随着越来越多的用户和网络加入Ｉｎｔｅｒｎｅｔ，给ＥＧＰ带来了很多的局限性。为了摆脱ＥＧＰ的局限性，ＩＥＴＦ边界网关协议工作组制定了标准的边界网关协议——ＢＧＰ。 下面对使用广泛且很有活力的ＲＩＰ，ＯＳＰＦ和ＢＧＰ进行介绍。 3.1 ＲＩＰ协议 ＲＩＰ是路由信息协议（Ｒｏｕｔｉｎｇ Ｉｎｆｏｒｍａｔｉｏｎ Ｐｒｏｔｏｃｏｌ）的缩写，采用距离向量算法，是当今应用最为广泛的内部网关协议。在默认情况下，ＲＩＰ使用一种非常简单的度量制度：距离就是通往目的站点所需经过的链路数，取值为1～15，数值16表示无穷大。ＲＩＰ进程使用ＵＤＰ的520端口来发送和接收ＲＩＰ分组。ＲＩＰ分组每隔30ｓ以广播的形式发送一次，为了防止出现“广播风暴”，其后续的的分组将做随机延时后发送。在ＲＩＰ中，如果一个路由在180ｓ内未被刷新，则相应的距离就被设定成无穷大，并从路由表中删除该表项。ＲＩＰ分组分为两种：请求分组和相应分组。 ＲＩＰ-1被提出较早，其中有许多缺陷。为了改善ＲＩＰ-1的不足，在ＲＦＣ1388中提出了改进的ＲＩＰ-2，并在ＲＦＣ 1723和ＲＦＣ 2453中进行了修订。ＲＩＰ-2定义了一套有效的改进方案，新的ＲＩＰ2支持子网路由选择，支持ＣＩＤＲ，支持组播，并提供了验证机制。 随着ＯＳＰＦ和ＩＳ-ＩＳ的出现，许多人认为ＲＩＰ已经过时了。但事实上ＲＩＰ也有它自己的优点。对于小型网络，ＲＩＰ就所占带宽而言开销小，易于配置、管理和实现，并且ＲＩＰ还在大量使用中。但ＲＩＰ也有明显的不足，即当有多个网络时会出现环路问题。为了解决环路问题，ＩＥＴＦ提出了分割范围方法，即路由器不可以通过它得知路由的接口去宣告路由。分割范围解决了两个路由器之间的路由环路问题，但不能防止3个或多个路由器形成路由环路。触发更新是解决环路问题的另一方法，它要求路由器在链路发生变化时立即传输它的路由表。这加速了网络的聚合，但容易产生广播泛滥。总之，环路问题的解决需要消耗一定的时间和带宽。若采用ＲＩＰ协议，其网络内部所经过的链路数路径不能超过15，这使得ＲＩＰ协议不适于大型网络。 3.2 ＯＳＰＦ协议 为了解决ＲＩＰ协议的缺陷，1988年ＲＦＣ成立了ＯＳＰＦ工作组，开始着手于ＯＳＰＦ的研究与制定，并于1998年4月在ＲＦＣ 2328中ＯＳＰＦ协议第二版（ＯＳＰＦｖ2）以标准形式出现。ＯＳＰＦ全称为开放式最短路径优先协议（Ｏｐｅｎ Ｓｈｏｒｔｅｓｔ-Ｐａｔｈ Ｆｉｒｓｔ），ＯＳＰＦ中的Ｏ意味着ＯＳＰＦ标准是对公共开放的，而不是封闭的专有路由方案。 ＯＳＰＦ采用链路状态协议算法，每个路由器维护一个相同的链路状态数据库，保存整个ＡＳ的拓扑结构（ＡＳ不划分情况下）。一旦每个路由器有了完整的链路状态数据库，该路由器就可以自己为根，构造最短路径树，然后再根据最短路径构造路由表。对于大型的网络，为了进一步减少路由协议通信流量，利于管理和计算，ＯＳＰＦ将整个ＡＳ划分为若干个区域，区域内的路由器维护一个相同的链路状态数据库，保存该区域的拓扑结构。ＯＳＰＦ路由器相互间交换信息，但交换的信息不是路由，而是链路状态。ＯＳＰＦ定义了5种分组：Ｈｅｌｌｏ分组用于建立和维护连接；数据库描述分组初始化路由器的网络拓扑数据库。当发现数据库中的某部分信息已经过时后，路由器发送链路状态请求分组，请求邻站提供更新信息；路由器使用链路状态更新分组来主动扩散自己的链路状态数据库或对链路状态请求分组进行响应；由于ＯＳＰＦ直接运行在ＩＰ层，协议本身要提供确认机制，链路状态应答分组是对链路状态更新分组进行确认。 相对于其他协议，ＯＳＰＦ有许多优点。ＯＳＰＦ支持各种不同鉴别机制（如简单口令验证，ＭＤ5加密验证等），并且允许各个系统或区域采用互不相同的鉴别机制；提供负载均衡功能，如果计算出到某个目的站有若干条费用相同的路由，ＯＳＰＦ路由器会把通信流量均匀地分配给这几条路由，沿这几条路由把该分组发送出去；在一个自治系统内可划分出若干个区域，每个区域根据自己的拓扑结构计算最短路径，这减少了ＯＳＰＦ路由实现的工作量；ＯＳＰＦ属动态的自适应协议，对于网络的拓扑结构变化可以迅速地做出反应，进行相应调整，提供短的收敛期，使路由表尽快稳定化，并且与其他路由协议相比，ＯＳＰＦ在对网络拓扑变化的处理过程中仅需要最少的通信流量；ＯＳＰＦ提供点到多点接口，支持ＣＩＤＲ（无类型域间路由）地址。 ＯＳＰＦ的不足之处就是协议本身庞大复杂，实现起来较ＲＩＰ困难。 3.3 ＢＧＰ协议 ＲＦＣ1771对ＢＧＰ的最新版本ＢＧＰ-4进行了详尽的介绍。ＢＧＰ用来在ＡＳ之间实现网络可达信息的交换，整个交换过程要求建立在可靠的传输连接基础上来实现。这样做有许多优点，ＢＧＰ可以将所有的差错控制功能交给传输协议来处理，而其本身就变得简单多了。ＢＧＰ使用ＴＣＰ作为其传输协议，缺省端口号为179。 与ＥＧＰ相比，ＢＧＰ有许多不同之处，其最重要的革新就是其采用路径向量的概念和对ＣＩＤＲ技术的支持。路径向量中记录了路由所经路径上所有ＡＳ的列表，这样可以有效地检测并避免复杂拓扑结构中可能出现的环路问题；对ＣＩＤＲ的支持，减少了路由表项，从而加快了选路速度，也减少了路由器间所要交换的路由信息。另外，ＢＧＰ一旦与其他ＢＧＰ路由器建立对等关系，其仅在最初的初始化过程中交换整个路由表，此后只有当自身路由表发生改变时，ＢＧＰ才会产生更新报文发送给其他路由器，且该报文中仅包含那些发生改变的路由，这样不但减少了路由器的计算量，而且节省了ＢＧＰ所占带宽。 ＢＧＰ有4种分组类型：打开分组用来建立连接；更新分组用来通告可达路由和撤销无效路由；周期性地发送存活分组，以确保连接的有效性；当检测到一个差错时，发送通告分组。 4 未来发展 （1）ＩＰｖ6 尽管采用ＣＩＤＲ技术缓解了ＩＰｖ4所面临的问题，但ＩＰｖ4的诸多弊端是它自身所不能解决的。为了摆脱ＩＰｖ4所固有的症结，需要采用新版本的网络协议——ＩＰｖ6。下个世纪初ＩＰｖ6将逐步地取代ＩＰｖ4，而这将带来一系列问题。当前的路由协议均是面向ＩＰｖ4，这就需要开发新的路由协议。ＲＦＣ2080中描述了面向ＩＰｖ6的ＲＩＰ——ＲＩＰｎｇ，该协议在ＲＩＰ-1和ＲＩＰ-2基础上做了较小的改动，使之适用于ＩＰｖ6的环境。对于面向ＩＰｖ6的ＯＳＰＦ，只是以草稿（ｄｒａｆｔ）的形式出现在ＲＦＣ中，还未列入ＲＦＣ标准。 （2）增强组播路由 支持组播的算法主要有扩散式（ｆｌｏｏｄ）、生成树（ｓｐａｎｎｉｎｇ ｔｒｅｅ）、反向路径转发（ｒｅｖｅｒｓｅ-ｐａｔｈ ｆｏｒ-ｗａｒｄｉｎｇ）、ｓｔｅｉｎｅｒ树、修剪反向路径广播（Ｔｒｕｎｃａｔｅｄ Ｒｅｖｅｒｓｅ Ｐａｔｈ Ｂｒｏａｄｃａｓｔｉｎｇ）和有核树（ｃｏｒｅ-ｂａｓｅｄ ｔｒｅｅｓ）。支持组播的路由协议主要有ＤＶＭＲＰ，ＭＯＳＰＦ和ＰＩＭ。ＤＶＭＲＰ是距离向量组播路由协议的缩写，它源于ＲＩＰ，在ＲＦＣ1057中有详尽的描述；ＲＦＣ1584中描述了支持组播路由的ＭＯＳＰＦ，它在ＯＳＰＦ链路状态数据库的帮助下建立自己的组播传送树；ＰＩＭ（协议无关组播）是由ＩＤＭＲ（域间组播路由）工作组提出，ＲＦＣ2117中提出了ＰＩＭ的稀疏形式。支持组播的ＭＢＯＮＥ（组播主干网）实验网于1992年开通，并在随后的几年得到了迅速发展。 （3）可移动ＩＰ 随着可移动计算机和可移动网络的出现，移动用户在不断地增长。同时这也带来了一个有挑战性的课题：考虑可移动ＩＰ。为此，ＩＥＴＦ专门成立了移动ＩＰ小组，处理可移动ＩＰ的相关问题。可移动ＩＰ路由需考虑以下问题：一个移动的主机必须能持续通信，并使用同一ＩＰ地址；一个移动的主机应该能与现有的其它主机和路由器相互协作；考虑移动主机的安全性问题；支持移动主机的组播处理能力。到现在，有关移动ＩＰ的解决方案多以草稿的形式出现在ＲＦＣ中。随着移动用户的增加，有关移动ＩＰ方面的研究将会越广泛。