TCP/IP基本原理 第五章 路由原理与协议

本章学习要求： 掌握：路由器的原理 掌握：路由表的建立 掌握：Internet结构，及其基本概念 掌握：RIP、BGP协议 了解：OSPF协议 了解：组播路由

5.1 概述 所谓路由是将数据从一个地方转发到另一个地方的一个中继过程。 5.1.1 路由的任务 任务 5.1 概述 所谓路由是将数据从一个地方转发到另一个地方的一个中继过程。 5.1.1 路由的任务 任务 寻路：寻径即判定到达目的地的最佳路径，由路由算法来实现。为了判定最佳路径，路由选择算法必须启动并维护包含路由信息的路由表，其中路由信息依赖于所用的路由选择算法而不尽相同。 转发：沿寻径好的最佳路径传送信息分组。路由器首先在路由表中查找，判明是否知道如何将分组发送到下一个站点（路由器或主机），如果路由器不知道如何发送分组，通常将该分组丢弃；否则就根据路由表的相应表项将分组发送到下一个站点，如果目的网络直接与路由器相连，路由器就把分组直接送到相应的端口上。这就是路由转发协议（routed protocol）。 感知并维持网络拓扑结构：路由选择算法将收集到的不同信息填入路由表中，根据路由表可将目的网络与下一站（nexthop）的关系告诉路由器。路由器间互通信息进行路由更新，更新维护路由表使之正确反映网络的拓扑变化，并由路由器根据量度来决定最佳路径。这就是路由选择协议（routing protocol），例如路由信息协议（RIP）、开放式最短路径优先协议（OSPF）和边界网关协议（BGP）等。

路由转发协议(routed protocol)和路由选择协议(routing protocol)是相互配合又相互独立的概念，前者使用后者维护的路由表，同时后者要利用前者提供的功能来发布路由协议数据分组。我们说的路由协议，除非特别说明，都是指路由选择协议。 路由协议分类：根据路由表的更新方式，分为： 静态路由：即在路由器中设置的固定的路由表。除非网络管理员干预，否则静态路由不会发生变化。由于静态路由不能对网络的改变作出反映，一般用于网络规模不大、拓扑结构固定的网络中。静态路由的优点是简单、高效、可靠。在所有的路由中，静态路由优先级最高。当动态路由与静态路由发生冲突时，以静态路由为准。 动态路由：根据网络中路由器之间相互通信，传递路由信息，利用收到的路由信息更新路由器表的过程。它能实时地适应网络结构的变化。如果路由更新信息表明发生了网络变化，路由选择软件就会重新计算路由，并发出新的路由更新信息。这些信息通过各个网络，引起各路由器重新启动其路由算法，并更新各自的路由表以动态地反映网络拓扑变化。动态路由适用于网络规模大、网络拓扑复杂的网络。当然，各种动态路由协议会不同程度地占用网络带宽和CPU资源。

根据是否在一个自治域 (指一个具有统一管理机构、统一路由策略的网络) 内部使用，动态路由协议分为： 内部网关协议(IGP)：自治域内部采用的路由选择协议称为内部网关协议，常用的有RIP、OSPF； 外部网关协议(EGP)：主要用于多个自治域之间的路由选择，常用的是BGP和BGP-4。 此外，还可以分为单路和多路、平等和分级、源路由和透明路由、链路状态和距离向量。 路由表项的优先级 在一个路由器中，可同时配置静态路由和一种或多种动态路由。它们各自维护的路由表都提供给转发程序，但这些路由表的表项间可能会发生冲突。这种冲突可通过配置各路由表的优先级来解决。通常静态路由具有默认的最高优先级，当其它路由表表项与它矛盾时，均按静态路由转发。

交换路由信息的最终目的在于通过路由表找到一条数据交换的“最佳”路径。每一种路由算法都有其衡量“最佳”的一套原则。大多数算法使用一个量化的参数来衡量路径的优劣，一般说来，参数值越小，路径越好。该参数可以通过路径的某一特性进行计算，也可以在综合多个特性的基础上进行计算，几个比较常用的特征是： 路径所包含的路由器结点数（hop count） 网络传输费用（cost） 带宽（bandwidth） 延迟（delay） 负载（load） 可靠性（reliability） 最大传输单元MTU（maximum transmission unit）

路由协议通过度量值来决定到达目的地的最佳路径。小度量值代表优选的路径；如果两条或更多路径都有一个相同的小度量值，那么所有这些路径将被平等地分享。通过多条路径分流数据流量被称为到目的地的负载均衡。 执行路由操作所需要的信息被包含在路由器的路由表中，它们由一个或多个路由选择协议进程生成。路由表由多个路由条目组成，每个条目指明了以下内容： 学习该路由所用的机制（动态或手动） 逻辑目的地 管理距离 度量值（它是度量一条路径的总"总开销"的一个尺度） 去往目的地下一跳的中继设备(路由器)的地址； 路由信息的新旧程度 与要去往目的地网络相关联的接口

5.1.2路由算法的设计目标 正确性(correctness)：指路由算法选择最佳路径的能力。 简单性(simplicity)：算法设计简洁，利用最少的软件和开销，提供最有效的功能。 健壮性(robustness)：路由算法处于非正常或不可预料的环境时，如硬件故障、负载过高或操作失误时，都能正确运行。最好的路由器算法通常能经受时间的考验，并在各种网络环境下被证实是可靠的。 快速收敛：收敛是在最佳路径的判断上所有路由器达到一致的过程。当某个网络事件引起路由可用或不可用时，路由器就发出更新信息。路由更新信息遍及整个网络，引发重新计算最佳路径，最终达到所有路由器一致公认的最佳路径。收敛慢的路由算法会造成路径循环或网络中断。 稳定性(stability)：路由算法对网络状态的变化不能过于敏感或者过于迟缓，使得路由算法不管运行了多长时间，都一直不能趋于稳定。对网络变化的反应应该做到恰倒好处。

5.2 路由原理 当IP子网中的一台主机发送IP分组给同一IP子网的另一台主机时，它将直接把IP分组送到网络上，对方就能收到。而要送给不同IP于网上的主机时，它要选择一个能到达目的子网上的路由器，把IP分组送给该路由器，由路由器负责把IP分组送到目的地。如果没有找到这样的路由器，主机就把IP分组送给一个称为“缺省网关（default gateway）”的路由器上。“缺省网关”是每台主机上的一个配置参数，它是接在同一个网络上的某个路由器端口的IP地址。 路由器转发IP分组时，只根据IP分组目的IP地址的网络号部分，选择合适的端口，把IP分组送出去。同主机一样，路由器也要判定端口所接的是否是目的子网，如果是，就直接把分组通过端口送到网络上，否则，也要选择下一个路由器来传送分组。路由器也有它的缺省网关，用来传送不知道往哪儿送的IP分组。这样，通过路由器把知道如何传送的IP分组正确转发出去，不知道的IP分组送给“缺省网关”路由器，这样一级级地传送，IP分组最终将送到目的地，送不到目的地的IP分组则被网络丢弃了。 Internet就是成千上万个IP子网通过路由器互连起来的国际性网络。这种网络称为以路由器为基础的网络（router based network），形成了以路由器为节点的“网间网”。在“网间网”中，路由器不仅负责对IP分组的转发，还要负责与别的路由器进行联络，共同确定“网间网”的路由选择和维护路由表。

5.2.1 路由表的建立 建立路由涉及初始化和更新两个方面。每个路由器在启动时都必须建立初始的一系列路由，还要在路由改变时更新路由表（如网络接口出故障时）。初始化的情况与操作系统有关：在某些系统中，路由器启动时从辅存储器中（如硬盘）读取初始路由表并将其驻留在主存中；在另一些系统中，操作系统把路由表初始化为空表，然后使用显式命令来赋初值；还有的系统在启动时根据本机直接相连的网络的地址推导出初始的一系列路由，并和相邻主机联络请求得到其他路由。 初始路由表建立起来之后．路由器还要适应路由的变化情况来更改路由表。在小型的、变化缓慢的互联网中．管理员可以用手工方式来建立和更改路由。但是，在大型的、迅速变化的环境下，人工更新的办法慢得无法接受并且容易造成人为的错误，这就需要自动更新路由的协议和方法。

5.2.2 Internet的结构 最初的Internet结构与核心路由器 Internet是由早期的ARPANET演变而来的。其路由器可以大致分为两类：有一小类是核心路由器 (core router) ；另一大类是非核心路由器 (non-core router)，由各个独立的群组控制。核心系统将整个Internet中的所有网点连接在一起，并提供到所有可能的目的站的可靠的、一致的、权威的路由。每个网点经过许可，获得一个Internet网络地址，再把这个地址通告给核心系统。核心系统在内部让所有核心路由器交换路由信息，使得每个路由器都具有关于到所有目的站的最短路由的全部信息，从而消除了默认路由，避免了可能低效率的路由。 非核心路出器中只包含本网 络的部分路由信息。与本网络以外 的通信都采用默认路由的方式交由 核心路由器去处理，典型结构如右 图所示。

从核心结构到对等结构 随着美国国家科学基金网 NSFNET(National Science Foundation Network) 引人Internet并成为 Internet的主要组成部分，原有的核心路由结构就无法满足要求了，这时，ARPANET与NSFNET之间建立有多个连接，如右图所示。称这两个网络为对等主干网络 (peer backbone network) 或简称为对等网络(peers)。 对等网的IP路由变得非常复杂。随着骨干网的进一步增多和Internet规模的扩展，核心路由器越来越难以保证路由信息的一致。曾经有一些尝试，将骨干网分割成几大块并在核心路由器中引入默认路由，但是这将导致出现潜在的环路。为了解决这些问题，Internet引人了自治系统的概念。

自治系统 从路由的目的来看，将处于同一个管理机构控制之下的网络和路由器群组称为一个自治系统(autonomous system)，简称为AS。在一个AS内的路由器可以自由选择一种协议来发现路由、传播路由以及检测路由的一致性。 在Internet的最上层保留核心路由的结构，各AS通过核心路由器接入Internet。核心路由器群组本身 也构成一个AS，由专门的机构INOC (Internet Network Operation Center) 统一管理，可以保证极高的可靠性， 并且互相交换信息，以保证Internet 路由的一致性。其拓扑结构如右图 所示。

为了能通过Internet到达隐藏在各个AS中的网络，每个AS在内部通过RIP、OSPF等内部网关协议来控制路由表的变化，并收集路由数据．AS内部中所有路由器必须把隐藏网络的信息通告给AS中的主路由器。 用以BGP、EGP等外部网关协议将收集的网络可达信息传播给其他AS。 为了能区分各个AS，每一个AS都被赋予一个AS编号，该编号由负责分配Internet地址的中央管理机构分发。当两个AS中的路由器交换路由信息时，报文中都携带有该路由器所代表的AS的系统编号。AS号分为私有AS号和公有AS号。在一个管理机构管理的大型网络中，为了便于管理也会划分不同的AS，这些AS使用私有AS号。 为了减少对核心系统的依赖关系，使Internet的管理和控制尽可能分散化进而提高可靠性，在各自治系统之间可以建立信任关系，信任度高的自治系统之间可以通过EGP协议直接交换路由信息，而不需要通过核心系统。

←───────────── IP数据报 ─────────────→ 5.3 内部网关路由协议 5.3.1 路由信息协议(RIP) 路由信息协议 (RIP，Routing Information Protocol) 是内部网关协议IGP中使用得最广泛的一个。RIP是一个基于距离向量的分布式路由选择协议，它的最大优点就是简单。 RIP报文格式 RIP报文包含在UDP数据报中，如下图所示。 ←─────────────　IP数据报　─────────────→ ←──────── UDP数据报───────→ IP首部 UDP首部 RIP报文 封装在UDP数据报中的RIP报文

(最多可以有24个另外的路由，与前20字节具有相同的格式) RIP报文格式见下图所示 RIP报文中命令字段的含义： 1：请求部分或全部路由信息 2：响应，包含发送方路由表内的网络距离序偶 3：启动跟踪模式 4：关闭跟踪模式 5：保留，由Sun Microsystem公司内部使用 0 8 16 31 命令(1~5) 版本号(1) (必须为0) 网络1的协议族 ↑ 20 字 节 ↓ 网络1的IP地址 到网络1的距离(<=16) (最多可以有24个另外的路由，与前20字节具有相同的格式) RIP报文格式

5.3.2 RIP操作 初始化：在启动一个路由守护程序时，它先判断启动了哪些接口，并将这些接口所在的网络信息填入路由表，然后在每个接口上发送一个请求报文，要求其他路由器发送完整路由表。在点对点链路中，该请求是发送给其他终点的。如果网络支持广播的话，这种请求是以广播形式发送的。目的UDP端口号是520(这是其他路由器的路由守护程序端口号)。 这种请求报文的命令字段设为1，但网络协议族字段设置为0，而到网络的距离字段设置为16。这是一种要求另一端发送完整路由表的请求报文。 接收到请求报文：如果报文是请求完整路由表，那么路由器就将内部的完整的路由表发送给请求者。如果该报文是请求部分路由，就处理请求报文中的每一个表项。如果路由表中有连接到该指明网络地址的路由，则将到该网络的距离设置成相应的值，否则将其置为16(在RIP中，距离为16是一种称为“无穷大”的特殊值．它意味着没有到达目的的路由），然后给请求方发回响应。

接收到响应报文：收到响应报文以后，可能会更新路由表。当路由器K收到相邻路由器X的“我到目的网络Y的距离为N”的信息，就按如下规则进行更新： 若K的路由表中没有到网络Y的表项，则增加到网络Y的表项，并将距离值设为 N+1．下一站设置为X； 若K的路由表中已有到网络Y的表项：“到目的网络Y经过路由器Z距离为M”，则当 M≤N+1时，不进行更新，当M＞N+1，将该表项更新为“到目的网络Y经过路由器X距离为N+1”； 若K的路由表中已有到网络Y的表项：“到目的网络Y经过路由器X距离为M”，则当M≠N+1时，将其距离值更新为N+1。

定期进行路由更新：每过30秒，所有或部分路由器会将其完整路由表发送给相邻路由器。发送路由表可以是广播形式的（如在以太网上），也可以是发送给点对点链路的其他终点的。收到报文的路由器按前面的规则进行更新。经过一段时间后，更新过程就会收敛，并使所有的路由器都建立起自己的路由表。每条路由都有与之相关的定时器。如果运行RIP的系统发现一条路由在3分钟内未更新，就将该路由的度量设置成无穷大(16)，并标注为删除。这意味着已经在6个30秒更新时间里没收到通告该路由的路由器的更新了。再过60秒，将从本地路由表中删除该路由，以保证该路由的失效信息被传播开。 触发更新：每当一条路由的距离值发生变化时，就对它进行更新。不需要发送完整路由表，而只需要发送那些发生变化的表项。

考察右下图所示的网络拓扑图，各路由器从初始化直到路由信息收敛。其路由表的一系列变化情况如下表所示。

5.3.3 慢收敛和计数到无穷大问题 假设路由器A与网络 10.0.0.0 的连接 断开了，如右图所示。路由器A应该立即 更新它的路由表，将路由表中到网络 10.0.0.0 的距离设置为16，并在下一次RIP 广播时，将这个消息通知路由器B和C。 但是，假若B正好在A与网络10.0.0.0 的 连接失效后通告其路由，这样，A就会先收到B的报文，并且按照前面的规则进行路由更新：A将路由表中到网络10.0.0.0 的表项更新为“经40.0.0.2 到网络10.0.0.0 距离为2 跳”。此时，如果A和B中的任意一个收到发往网络10.0.0.0 的数据报，就会在A和B之间来回传递该数据报，直到其寿命计数器到期。 随后的RIP广播并不能迅速解决这两个路由器的问题。从下页的图中A和B的路由表变化情况可以看出，直至A和B的路由表中关于网络 10.0.0.0 的距离都达到16时，更新过程才会收敛，此时的路由表才是正确的。

解决的办法之一：水平分割 水平分割更新 (split horizon update) 技术是指，在使用水平分割更新技术时，路由器不会把从某路由器学来的信息再回传到该路由器的接口去。在上面的例子中，路由器B和C不会把它到网络10.0.0.0的距离为1的路由信息再通告给 A(因为 B和C是从A得到该路由信息的)。因此，如果A与网络10.0.0.0 的连接失效，A将不会收到B和C提供给它的错误路由信息，而A会将网络10.0.0.0 的不可达信息传播给B和C，这样，经过一轮路由更新之后，所有的路由器都知道网络10.0.0.0是不可达的。但是，分割范围更新技术并不能解决所有拓扑结构中的路由环路和慢收敛问题。 解决的办法之二：抑制法 抑制法(holddown) 要求所有的RIP路由器在收到某网络不可达信息后的一段固定时间内，忽略任何该网络的可达信息。这段抑制时间的典型长度是60秒。该技术的思路是，等待足够的时间以确保所有机器都收到网络不可达的坏消息，并且不会错误地接受内容过时的报文。抑制技术的缺点是：如果出现了选路环路，那么在抑制期内这些选路环路仍然会维持下去。更严重的是，即便存在替代路由，抑制期间所有不正确的路由也保留下来了。

解决的办法之三：毒性反转 毒性反转(poison reverse)是指，当路由器与某个网络断开后，该路由器在若干个更新周期内都保留该路由，但是在广播路由信息时将到该路由的距离置为无限大。为提高毒性逆转法的效率，它应该与触发更新(triggered update)技术相结合，使得路由器在接收到坏消息后立即进行广播。通过立即发送更新信息，路由器减少了因为相信好消息而容易出错的时间。 虽然触发更新技术、毒性反转技术、抑制技术和水平分割技术能够解决一些问题，但它们又带来了一些新问题。例如，当许多路由器共享一个公共网络时，如果不用触发更新技术，一个广播就能改变这些路由器的路由表，引发一轮新的广播。如果第二轮广播改变了路由表，又会引起更多的广播。这就产生了广播风暴。 使用广播（这有可能产生选路环路）和抑制技术防止慢收敛，都会使RIP的工作效率极低。所有机器周期性地进行广播意味着通信量随着路由器数目的增加而增加，而在线路容量有限的情况下，选路环路可能就是致命的问题。当形成环路的分组造成线路容量饱和后，路由器需要交换一些选路报文来打破这种环路。此刻就不可能做到。同样，在广域网中，抑制期可能太长，使得高层协议使用的定时器超时而中断连接。

5.3.4 RIP跳数的缺点 RIP作为内部网关协议在两个方面限制了选路： RIP把路径距离限制为一个跳数值而忽略了其他的距离度量标准。 跳数值只是对网络响应能力和容量的粗略估计，并不能得出具有最小时延或最高容量的路由。更为严重的是，它使路由固定不变，因为路由无法对网络负载的变化做出反应。因此在OSPF等协议中就支持其他几种距离度量标准。

Hello报文允许机器计算新的路由。路由的算法与RIP 很相似，只是要将RIP中的距离换成时延。 Hello协议也是IGP中的一种，但它是基于路由的网络时延，而不是基于路由的距离，因此它对网络响应时间敏感的用户比较有用。虽然目前Hello协议已经陈旧，但它在Internt的发展历史中仍占有重要地位。最初NSFNET中的路由器就是使用Hello协议。 Hello协议提供两种功能。一种功能是使各机器(指路由器和目的主机) 的时钟得到同步。另一种功能是每个机器都能计算出到目的主机的最小时延路由。因此，Hello报文既包括路由信息，也还带有时间戳信息。 Hello协议的原理：参加交换Hallo报文的每一个机器都有一个相邻机器时钟的最佳估算值表。一个机器在发送分组时，要加上一个时间戳，写入当前的时钟值。当从相邻路由器发来的分组到达时，机器计算分组在链路上的时延：从对相邻机器时钟的估算值减去分组中时间戳上的时钟值。所有的机器要周期性地向相邻机器发出轮询，以重新建立时钟的估算值。 Hello报文允许机器计算新的路由。路由的算法与RIP 很相似，只是要将RIP中的距离换成时延。

Hello协议也不能使路由表更新得太快，否则会出现路由的不稳定，即路由表中的表项在两条路由之间来回改变

5.5 OSPF协议 5.5.1 OSPF的网络拓扑结构 OSPF：Open Shortest Path First，开放式最短路径优先协议。 Internet中AS范围仍然很大，不便于管理。OSPF对网络进行了进一步的划分： 它把一个网络或一系列相邻的网络分为编号区域(area)。一个区域的拓扑结构对于AS的其余部分是不可见的 (信息隐藏技术是为了让路由器信息量显著降低)。 域内的路由只由区域本身拓扑结构决定，而不受域外信息的影响。OSPF还定义了一个特殊的域：主干(Backbone)，其编号为0。所有的区域都与主干相连。主干负责向所有的非主干区域发送路由信息。在主干之外，其拓扑结构也是不可见的。 OSPF区域不能随意划分，应该合理地选择区域边界，使不同区域之间的通信量最小。但在实际应用中区域的划分往往并不是根据通信模式而是根据地理或政治因素来完成的。

路由器的分类：由于区域的引入，OSPF路由器可以划分成以下4种类型： 域内路由器(internal router) ：与该路由器相连的所有通信对端(网络或路由器)均属于同一域。该路由器只运行一套基本路由算法。 域间路由器(area border router) ：与多个域相连的路由器。它运行多套基本的路由算法。每套算法对应它相连的一个区域。域间路由器将与它们相连域的拓扑结构加以提炼并发送给主干，然后主干将这些信息分发到各个域中。 主干路由器(backbone router) ：与主干有接口的路由器。括所有的域间路由器都是主干路由器，但并非所有的主干路由器都是域间路由器。下图中的R2、R3、R4、R5和R6都是主干路由器。 自治系统边界路由器(AS boundary router)：与其它AS交换路由信息的路由器。这些路由器向整个AS广播系统外的路由信息。AS内的所有路由器都知道通往AS系统边界路由器的路径。 注意：这4种路由器的分类是有重叠的。例如，域间路由器都是主干路由器，有些域间路由器也是AS边界路由器。

域内路由器：R1、R4、R7 域间路由器： R2、R3、R5、R6 主干路由器： R2、R3、R4、R5、R6 AS边界路由器：R2

5.5.2 OSPF分组报头结构 OSPF属于网络层，其功能实现建立在IP能够接受并向邻节点发送分组的基础之上。所有的OSPF分组都从一个公共报头开始，其格式见右图： 版本号：当前OSPF的版本号为2 类型：OSPF分组类型 分组长度：分组的字节数 路由器ID：路由器的标识符 域ID：区域标识符 校验和：对此字段以前的字段 (8字节)的校验，方法与IP校验 相同 认证类型：0_ 不认证，1_ 认证 8 31 版本号 类型 分组长度 路由器ID 域ID 校验和 认证类型 认证 OSPF的分组报头格式

5.5.3 OSPF网络类型 根据路由器所连接的物理网络不同，OSPF将网络划分为四种类型： 广播多路访问型(Broadcast multiAccess)：Ethernet、Token Ring、FDDI。 非广播多路访问型(None Broadcast MultiAccess，NBMA)： Frame Relay、X.25、SMDS。 点到点型 (Point-to-Point)： PPP、HDLC。 点到多点型（Point-to-MultiPoint）。

5.5.4 指派路由器(DR)和备份指派路由器(BDR) 在多路访问网络上可能存在多个路由器，为了避免路由器之间建立完全相邻关系而引起的大量开销，OSPF要求在区域中选举一个DR。每个路由器都与之建立完全相邻关系。DR负责收集所有的链路状态信息，并发布给其他路由器。选举DR的同时也选举出一个BDR，在DR失效的时候，BDR担负起DR的职责。 点对点型网络不需要DR，因为只存在两个节点，彼此间完全相邻。 协议组成OSPF协议由Hello协议、交换协议、扩散协议组成。 当路由器开启一个端口的OSPF路由时，会从这个端口发出一个Hello报文，以后它也将以一定的间隔周期性地发送Hello报文。OSPF路由器用Hello报文来初始化新的相邻关系以及确认相邻的路由器邻居之间的通信状态。 对广播型网络和非广播型多路访问网络，路由器使用Hello协议选举出一个DR。在广播型网络里，Hello报文使用多播地址224.0.0.5周期性广播，并通过这个过程自动发现路由器邻居。在NBMA网络中，DR负责向其他路由器逐一发送Hello报文。

下图是选举指派路由器前后网络中的邻接关系对比。

5.5.5 协议过程 第一步：建立路由器的邻接关系 所谓“邻接关系”（Adjacency）是指OSPF路由器以交换路由信息为目的，在所选择的相邻路由器之间建立的一种关系。 路由器首先发送拥有自身ID信息（Loopback端口或最大的IP地址）的Hello报文。与之相邻的路由器如果收到这个Hello报文，就将这个报文内的ID信息加入到自己的Hello报文内。 如果路由器的某端口收到从其他路由器发送的含有自身ID信息的Hello报文，则它根据该端口所在网络类型确定是否可以建立邻接关系。 在点对点网络中，路由器将直接和对端路由器建立起邻接关系，并且该路由器将直接进入到第三步操作：发现其他路由器。若为MultiAccess 网络, 该路由器将进入选举步骤。

第二步：选举DR/BDR 不同类型的网络选举DR和BDR的方式不同。Multi Access网络支持多个路由器，在这种状况下，OSPF需要建立起作为链路状态和LSA更新的中心节点。选举利用Hello报文内的ID和优先权(Priority)字段值来确定。优先权字段值大小从0到255，优先权值最高的路由器成为DR。如果优先权值大小一样，则ID值最高的路由器选举为DR，优先权值次高的路由器选举为BDR。优先权值和ID值都可以直接设置。 第三步：发现路由器 路由器与路由器之间首先利用Hello报文的ID信息确认主从关系，然后主从路由器相互交换部分链路状态信息。每个路由器对信息进行分析比较，如果收到的信息有新的内容，路由器将要求对方发送完整的链路状态信息。这个状态完成后，路由器之间建立完全相邻（Full Adjacency）关系，同时邻接路由器拥有自己独立的、完整的链路状态数据库。 在Multi Access网络内，DR与BDR互换信息，并同时与本子网内其他路由器交换链路状态信息。

第四步: 选择适当的路由器 当一个路由器拥有完整独立的链路状态数据库后，它将采用SPF算法计算并创建路由表。OSPF路由器依据链路状态数据库的内容，独立地用SPF算法计算出到每一个目的网络的路径，并将路径存入路由表中。 OSPF利用量度（Cost）计算目的路径，Cost最小者即为最短路径。在配置OSPF路由器时可根据实际情况，如链路带宽、时延或经济上的费用设置链路Cost大小。Cost越小，则该链路被选为路由的可能性越大。 第五步：维护路由信息 当链路状态发生变化时，OSPF通过Flooding 过程通告网络上其他路由器。OSPF路由器接收到包含有新信息的链路状态更新报文，将更新自己的链路状态数据库，然后用SPF算法重新计算路由表。在重新计算过程中，路由器继续使用旧路由表，直到SPF完成新的路由表计算。新的链路状态信息将发送给其他路由器。值得注意的是，即使链路状态没有发生改变，OSPF路由信息也会自动更新，默认时间为30分钟。

OSPF路由器之间使用链路状态通告(LSA)来交换各自的链路状态信息，并把获得的信息存储在链路状态数据库中。各OSPF路由器独立使用SPF算法计算到各个目的地址的路由。 OSPF协议支持分层路由方式，这使得它的扩展能力远远超过RIP协议。当OSPF网络扩展到100、500甚至上千个路由器时，路由器的链路状态数据库将记录成千上万条链路信息。为了使路由器的运行更快速、更经济、占用的资源更少，人们通常按功能、结构和需要把OSPF网络分割成若干个区域，并将这些区域和主干区域根据功能和需要相互连接从而达到分层的目的。

5.6 外部网关路由协议 术语EGP (Exterior Gateway Protocol)，外部网关路由协议) 原来是指用于和ARPANET核心通信的一个具体的已经淘汰的协议，现在EGP用来表示两个自治系统之间传送路由信息的所有协议。 大多数TCP/IP互联网都使用BGP-4协议作为EGP (Border Gateway Protocol，边界网关路由协议) 协议。 当两个自治系统同意交换路由信息时，每个系统必须指定一个边界路由器，它们要运行BGP协议。这两个路由器分别被称为另一个BGP的对等路由器。每个边界路由器收集自己所在的AS内部的路由信息后，使用BGP通告给其它AS的对等路由器(peer)。 BGP是一种自治系统间的动态路由发现协议，它的基本功能是在自治系统间自动交换无环路的路由信息。

BGP协议的层次位置 BGP SOCKET TCP IP，IPX PPP，X.25等 操作系统 硬件接口及驱动 BGP使用Socket 服务建立连接，端口号为179。BGP运行时，分别与本自治区域外和区域内的BGP伙伴建立连接(使用Socket)。与区域内伙伴的连接称为IBGP(Internal BGP)连接，与自治区域外的BGP伙伴的连接称为EBGP(External BGP)连接。本地的BGP协议对IBGP和EBGP伙伴使用不同的机制处理。

5.6.1 BGP协议工作过程 BGP执行三类路由：AS间路由、AS内部路由和贯穿AS路由。 AS间路由发生在不同AS的两个或多个BGP路由器之间，这些系统的对等路由器使用BGP来维护一致的网络拓扑视图，AS间通信的BGP邻居必须处于相同的物理网络。因特网就是使用这种路由的实例，因为它由多个AS构成，BGP经常用于为因特网内提供最佳路径而做路由选择。 AS内路由发生在同一AS内的多个BGP路由器间，同一AS内的对等路由器用BGP来维护一致的系统拓扑视图。BGP也用于决定哪个路由器作为与外部AS的连接点。因特网利用BGP在其自己的管理域（或称AS）内提供最佳路由。BGP协议既可以提供AS间也可以提供AS内部路由。 贯穿(pass-through) AS路由发生在通过不运行BGP的AS交换数据的两个或多个BGP对等路由器间。在贯穿AS环境中，BGP通信既不源自AS内，目的也不在该AS内的节点，BGP必须与AS内使用的路由协议交互以成功地通过该AS传输BGP通信。

下图所示为贯穿AS环境：

5.6.2 BGP的主要功能 与其它路由协议一样，BGP维护路由表、发送路由更新信息且基于路由metric决定路由。BGP系统的主要功能是交换其它BGP系统的网络可达信息，包括AS路径的列表信息，此信息可用于建立AS系统连接图，以消除路由环，及执行AS级策略确定。 每个BGP路由器维护到特定网络的所有可用路径构成的路由表，但是它并不清除路由表，它维持从对等路由器收到的路由信息直到收到增值(incremental)更新。 BGP设备在初始数据交换和增值更新后交换路由信息。当路由器第一次连接到网络时，BGP路由器交换它们的整个BGP路由表，类似的，当路由表改变时，路由器发送路由表中改变的部分。BGP路由器并不周期性发送路由更新，且BGP路由更新只包含到某网络的最佳路径。 BGP用单一的路由metric决定到给定网络的最佳路径。这一metric含有指定链路优先级的任意单元值，BGP的metric通常由网管赋给每条链路。赋给一条链路的值可以基于任意数目的尺度，包括途经的AS数目、稳定性、速率、延迟或代价等。

5.6.3 BGP消息类型 RFC1771中规定了四种BGP消息类型：初始消息，更新消息、通知消息和keep-alive消息： 初始消息(open)：在对等路由器间打开一个BGP通信会话，是建立传输协议后发送的第一个消息。初始消息由对等设备发送的keep-alive消息确认，得到确认后再交换更新、通知和keep-alive消息。 更新消息(update)：用于提供到其它BGP系统的路由更新，使路由器可以建立一致的网络拓扑视图。更新用TCP发送以保证传输的可靠性。更新消息可以从路由表中清除多条失效路由，同时发布若干路由。 通知消息(notify)：在检查到有错误时发送。通知消息用于关闭一条活动的会话，并通知其它路由器为何关闭该会话。 keep-alive消息：通知对等BGP路由器该设备仍然alive。keep-alive消息发布足够频繁以防止会话过期。

5.6.4 BGP的消息结构 BGP有4种类型的消息。分别为OPEN，UPDATE，KEEPALIVE和NOTIFICATION 。它们有相同的消息头： 标记 : (16字节) 鉴权信息 长度 : (2字节) 消息的长度 类型 : (1字节) 消息的类型: 0 ：OPEN 1 ：UPDATE 2 ：NOTIFICATION 3 ：KEEPALIVE 16 bytes 2 bytes 1 byte variable 标记 长度 类型 数据

open消息结构 在信头的类型域中标识为BGP初始消息的BGP分组包含下列各域，这些域为两个BGP路由器建立对等关系提供了交换方案： BGP初始(open)消息由BGP信头和附加域构成，下图为BGP初始消息的附加域： 在信头的类型域中标识为BGP初始消息的BGP分组包含下列各域，这些域为两个BGP路由器建立对等关系提供了交换方案： 版本号：使接收者可以确认它是否与发送者运行同一版本协议。 自治系统：提供发送者的AS号。 保持时间(Hold-time)：在发送者被认为失效前最长的不接收消息的秒数。 BGP标识：提供发送者的标识 (IP地址)，在启动时决定，对所有本地接口和所有对等BGP路由器而言都是相同的。 可选参数长度：标识可选参数域的长度 (如果存在的话)。 可选参数：包含一组可选参数。目前只定义了一个可选参数类型：认证信息。认证信息含有下列两个域： 认证码：标识使用的认证类型。 认证数据：包含由认证机制使用的数据。 1 byte 2 byte 4 byte 4byte 版本 自治系统 保持时间 BGP标识 可选参数长度 可选参数

更新消息格式 BGP更新消息由BGP信头和附加域构成，下图为BGP更新消息的附加域： 收到更新消息后，路由器就可以从路由表中增加或删除指定的表项以保证路由的准确性。更新消息包含下列域： 失效路由长度 ：标识失效路由域的总长度或该域不存在。 失效路由：包含一组失效路由的IP地址前缀。 总路径属性长度：标识路径属性域的总长度或该域不存在。 路径属性：描述发布路径的属性，可能的值如下： 源：必选属性，定义路径信息的来源。 AS路径：必选属性，由一系列AS路径段组成。 下一跳：必选属性，定义了在网络层可达信息域中列出的应用作到目的地下一跳的边缘路由器的IP地址。 多重出口区分：可选属性，用于在到相邻AS的多个出口间进行区分。 本地优先权：可选属性，用以指定发布路由的优先权等级。 原子聚合：可选属性，用于发布路由选择信息。 聚合：可选属性，包含聚合路由信息。 网络层可达信息：包含一组发布路由的IP地址前缀。 2 byte vatiable 可变长 失效路由长度 失效路由 总路径属性长度 路径属性 网络层可达信息

通知消息格式 通知消息分组用于给对等路由器通知某种错误情况。 下图为BGP通知消息使用的附加域： 通知消息分组用于给对等路由器通知某种错误情况。 错误码 - 标识发生的错误类型。下面为定义的错误类型：   -- 消息头错：指出消息头出了问题，如不可接受的消息长度、标记值或消息类型。   -- 初始消息错：指出初始消息出了问题，如不支持的版本号，不可接受的AS号或IP地址或不支持的认证码。   -- 更新消息错：指出更新消息出了问题，如属性列表残缺、属性列表错误或无效的下一跳属性。   -- 保持时间过期：指出保持时间已过期，这之后BGP节点就被认为已失效。   -- 有限状态机错：指示期望之外的事件。   -- 终止：发生严重错误时根据BGP设备的请求关闭BGP连接。 错误子码 - 提供关于报告的错误的更具体的信息。 错误数据 - 包含基于错误码和错误子码域的数据，用于检测通知消息发送的原因。 1 byte 可变长 错误码 错误子码 错误数据

5.6.5 BGP协议中消息的应用 BGP使用TCP建立连接，本地监听端口为179。 TCP通过握手协商通告其端口等参数，BGP的握手协商的参数有：BGP版本，BGP连接保持时间，本地的路由器标识(Router ID)，授权信息等。这些信息都在OPEN消息中体现。 BGP连接建立后，如果有路由需要发送则发送UPDATE消息，以通告对端路由信息。UPDATE消息发布路由时，还要指定此路由的属性，以帮助对端BGP协议选择最佳的路由。由UPDATE消息的格式可以看出每个UPDATE消息只可以发布一种路由属性，本地BGP如果有路由属性完全相同的路由(只有信宿地址不同)，则可以由一条UPDATE消息发布，否则只能使用不同的UPDATE消息发布。 在本地BGP路由变化时，也使用UPDATE消息修正对端BGP的路由表。 经过一段时间的路由信息交换后，本地BGP和对端BGP都无新路由通告，趋于稳定了。随后定时发送KEEPALIVE消息以保持BGP连接的有效性。对于本地BGP，如果在超过保持时间的时间内，还未收到任何对端BGP消息，就认为此BGP连接已经无效，将此BGP连接断开。 当本地BGP运行中出错时，发送NOTIFY消息通告BGP对端。比如，对端BGP版本本地不支持，本地BGP收到了结构非法的UPDATE消息等。本地BGP退出BGP连接时也要发送NOTIFY消息。

5.7 组播路由 组播：是一种允许一个或多个发送者（组播源）发送单一的数据包到多个接收者（一次的，同时的）的网络技术。组播源把数据包发送到特定组播组，而只有属于该组播组的地址才能接收到数据包。组播可以大大的节省网络带宽，因为无论有多少个目标地址，在整个网络的任何一条链路上只传送单一的数据包。 IP组播：在IP网络中，源IP主机只发送一份数据，多个接收者可接收相同数据的拷贝。可以接收组播数据分组的一组主机，称之为组播组。 IPv4中用D类IP地址(224.0.0.0~239.255.255.255)来表示组播地址。 局部链接地址：224.0.0.0～224.0.0.255，用于局域网，路由器不转发此地址范围的IP包； 预留组播地址：224.0.1.0～238.255.255.255，用于全球范围或网络协议； 管理权限地址：239.0.0.0～239.255.255.255，组织内部使用，用于限制组播范围； IPv6的高8位地址为FF（11111111）值时，标识为组播地址。随后四位的“标识字段”中高三位始终设置为0并保留。第四位T标识设置为0时表示一个永久分配的组播地址。T标识设置为1时，表示非永久分配的组播地址，这种地址作为一个临时的组播地址。范围值限制了组播的范围。

IP组播地址范围是224.0.0.0~239.255.255.255，下面列出部分知名或已用的IP组播地址： 224.0.0.0　基础地址，保留，不能被任何群组使用　 224.0.0.1　全主机群组（all　hosts　group），指参加本IP组播的所有主机、路由器、网关（不是指整个互连网）　 224.0.0.2　本子网上的路由器（all routers on a LAN） 224.0.0.4　DVMRP*路由器 ( DVMRP Routers ) 224.0.0.5　本子网上的OSPF*路由器(all OSPF routers on a LAN) 224.0.0.6　本子网上被指定的OSPF路由器(all designated OSPF routers　on a LAN )　 224.0.1.1　网络时间协议 ( Network Time Protocol，NTP ) 224.0.5.000-224.0.5.127　蜂窝式数字信息包数据发送主机组 ( CDPD　Groups ) 224.1.0.0-224.1.255.255　基于流的协议组播主机组 ( Stream Protocol　Multicast Groups )　 224.2.0.0-224.2.255.255　多媒体会议呼叫 ( Multimedia Conference 　Calls )　 *注：DVMRP是Distance　vector　multicast　routing　protocol的缩写，意为距离矢量组播选路协议，是用来生成组播路由；

以太网组播MAC地址映射 组播传输可在数据链路层（第二层）和网络层（第三层）实现，支持的媒体类型包括以太网、FDDI和ATM。大多数路由器支持IP组播，不支持IP组播的网络通过组播隧道技术传输组播信息包。 IP组播帧都使用以0X0100.5EXX.XXXX的24位前缀开始的MAC层地址，但只有其中的一半MAC地址可以被IP组播使用，剩下的MAC地址空间的23位作为第三层IP组播地址进入第二层MAC地址的映射使用。由于第三层IP组播的28位地址不能映射到只有23位的可用MAC地址空间，造成有32:1的地址不明确，所以主机CPU必须对收到的每一个组播数据包做出判断。这增加了主机CPU的开销。

5.7.1 组管理协议IGMP 主机使用IGMP通知子网组播路由器，希望加入组播组；路由器使用IGMP查询本地子网中是否有属于某个组播组的主机 加入组播组 当主机加入一个组播组时，它通过“成员资格报告”消息通知它所在的IP子网的组播路由器，同时将自己的IP模块做相应的准备，以便开始接收来自该组播组传来的数据。如果这台主机是它所在的IP子网中第一台加入该组播组的主机，通过路由信息的交换，组播路由器加入组播分布树。 退出组播组 在IGMP v1中，当主机离开某一个组播组时，它将自行退出。组播路由器定时(如120秒) 使用“成员资格查询” 消息向IP子网中的所有主机的组地址（224.0.0.1）查询，如果某一组播组在IP子网中已经没有任何成员，那么组播路由器在确认这一事件后，将不再在子网中转发该组播组的数据。与此同时，通过路由信息交换，从特定的组播组分布树中删除相应的组播路由器。这种不通知任何人而悄悄离开的方法，使得组播路由器知道IP子网中已经没有任何成员的事件延时了一段时间，所以在IGMP v2.0中，当每一个主机离开某一个组播组时，需要通知子网组播路由器，组播路由器立即向IP子网中的所有组播组询问，从而减少了系统处理停止组播的延时。

5.7.3组播转发 由于组播源是向组播组发送数据包而非单播模型中的具体目标主机，所以组播路由器不能依靠IP包中的目标地址来决定如何转发数据包，而必须将组播数据包转发到多个外部接口上，以便同一组播组的成员都能接收到数据包。这使组播转发比单播转发更加复杂。大多数现有组播路由协议使用逆向路径转发（RPF）机制作为组播转发的基础。 逆向路径转发(Reverse Path Forward: RPF) 当组播数据包到达路由器时，路由器作RPF检查，以决定是否转发或抛弃该数据包，若成功则转发，否则抛弃。RPF检查过程如下： 检查数据包的源地址，以确定该数据包经过的接口，是否在从源到此的路径上； 若数据包是从可返回源主机的接口上到达，则RPF检查成功，转发该数据包到输出接口表上的所有接口，否则RPF检查失败，抛弃该数据包。

组播转发缓存 ：对每一个输入组播数据包进行RPF检查会导致较大的路由器性能损失。因此，建立组播转发缓存时，通常由组播路由确定RPF接口。然后将RPF接口变成组播转发缓存项的输入接口。一旦RPF检查程序使用的路由表发生变化，必须重新计算RPF接口；并更新组播转发缓存项。 TTL阈值：每当路由器转发组播数据包，IP包中的TTL（Time To Live）值减1。若数据包的TTL减少到0，路由器将抛弃该数据包。TTL阈值可用于组播路由器的各个接口，以防止在该接口上转发低于TTL阈值的组播数据包。这样可对组播的范围加以控制。下表给出典型的初始TTL值和作为不同TTL边界的路由器接口TTL阈值。 管理权限边界：除TTL阈值外，组播提供另一种称为管理权限的地址机制作为边界，以限制组播信息转发到域外。管理权限的组播地址是从239.0.0.0到239.255.255.255，这段地址被认为是本地分配(类似于单播中的192.168.xx.xx)，不能用于Internet。这种机制使得在Intranet内部可重复使用组播地址，提高组播地址空间的利用率。 范　围 本地网 区域 地区 全球 初始TTL值 1 15 63 127 TTL阈值 N/A 16 64 128

本章习题 参见教师网页：http://staff.ustc.edu.cn/~leeyi