路由原理与设计之五--OSPF路由协议.doc

第1章 OSPF协议基本概念

    本课程由浅入深介绍了OSPF协议的基本概念，OSPF路由计算过程，以及如何合理规划设计OSPF网络。相信您学完本课程，定能迅速成为一个OSPF高手。
    假设您对计算机网络结构有一定了解，记住OSPF就是去寻找到某个终点计算机的最短路径的方法。

1.1 OSPF协议概述

现在Internet已广泛应用于军事，科技，教育，工农业等各个领域，发挥着越来越重要的作用，它标志着信息时代的兴起。
    Internet的重要基础是TCP/IP协议（Transmission Control Protocol / Internet Protocol即传输控制协议 / 国际互连网协议），该协议是计算机用于网络通信的标准，它是一个协议族，包含控制，传输，标识等各方面的子协议。
    TCP/IP协议中，寻找一台计算机到另一台计算机的路由是很重要的，一方面，要判断是否能找到路，一方面，找到路后找一条短的路（花费时间最小），再一方面，不能循环。最好还应该能动态处理路由变化，如：接口的UP或DOWN，时间花费的变化，网络结构的改变等。网络上的节点通常通过路由器与整个网络联系，它需要知道到达网络的另一个节点的路由。
    IETF(Internet Engineering Task Force)于1988年提出的OSPF是一个基于链路状态的动态路由协议。当前OSPF协议使用的是第二版，最新的RFC是2328。协议的基本思路如下：在自治系统中每一台运行OSPF的路由器收集各自的接口/邻接信息称为链路状态，通过Flooding算法在整个系统广播自己的链路状态，使得在整个系统内部维护一个同步的链路状态数据库，根据这一数据库，路由器计算出以自己为根，其它网络节点为叶的一根最短的路径树，从而计算出自己到达系统内部可达的最佳路由。OSPF是一类Interior Gateway Protocol(内部网关协议IGP)，它处理在一个自治系统中的路由表信息。
1.2 OSPF协议基本特征

    OSPF协议具有如下特点：
    适应范围 —— OSPF 支持各种规模的网络，最多可支持几百台路由器。
    快速收敛 —— 如果网络的拓扑结构发生变化，OSPF 立即发送更新报文，使这一变化在自治系统中同步。
    无自环 —— 由于 OSPF 通过收集到的链路状态用最短路径树算法计算路由，故从算法本身保证了不会生成自环路由。
    子网掩码 —— 由于 OSPF 在描述路由时携带网段的掩码信息，所以OSPF协议不受自然掩码的限制，对VLSM 提供很好的支持。
    区域划分 —— OSPF 协议允许自治系统的网络被划分成区域来管理，区域间传送的路由信息被进一步抽象，从而减少了占用网络的带宽。
    等值路由 —— OSPF 支持到同一目的地址的多条等值路由，即到达同一个目的地有多个下一跳，这些等值路由会被同时发现和使用。
    路由分级 —— OSPF 使用 4 类不同的路由，按优先顺序来说分别是：区域内路由、区域间路由、第一类外部路由、第二类外部路由。
    支持验证 —— 它支持基于接口的报文验证以保证路由计算的安全性。
    组播发送 —— OSPF在有组播发送能力的链路层上以组播地址发送协议报文，即达到了广播的作用，又最大程度的减少了对其他网络设备的干扰。
1.3 OSPF相关术语

    与OSPF协议相关的术语主要包括：
    (1)Router ID    OSPF域中路由器的唯一标识
    (2)Area         区域
    (3)Cost         花费值
    (4)ABR、ASBR    区域边界路由器、自治系统边界路由器
    (5)LSA          链路状态通告
    (6)Link Type    链路类型，包括广播，非广播，点到点，点到多点
    (7)DR和BDR      指定路由器和非指定路由器
    (8)区域类型     骨干区域，STUB区域，TRANSIT区域
    (9)Virtual-Link 虚连接
    接下来的课程我们将会对这些术语作详细介绍。
1.4 Router ID

    Router ID：
    OSPF协议使用一个被称为Router ID的32位无符号整数来唯一标识一台路由器。基于这个目的，每一台运行OSPF的路由器都需要一个Router ID。这个Router ID一般需要手工配置，一般将其配置为该路由器的某个接口的IP地址。由于IP地址是唯一的，所以这样就很容易保证Router ID的唯一性。在没有手工配置Router ID的情况下，一些厂家的路由器（包括Quidway系列）支持自动从当前所有接口的IP地址自动选举一个IP地址作为Router ID。
    Router ID选择注意点：
    (1)首先选取最大的loopback接口地址
    (2)如果没有配置loopback接口，那么就选取最大的物理接口地址
    (3)可以通过命令强制改变Router ID：VRP平台系统视图下，router id <ip address>
    (4)如果一台路由器的 Router ID 在运行中改变，则必须重启OSPF协议或重启路由器才能使新的 Router ID 生效
    协议号：
    OSPF 协议用IP 报文直接封装协议报文，协议号是89。
1.5 Area区域

    OSPF引入区域的概念是为了隔离和区分自治系统内的各部分，并由此减少路由器必须维护的整个自治系统的信息量，可以针对不同区域的拓扑特点采用不同的策略，也就意味着减少了路由器间传输和维护的OSPF路由表的额外信息。
    一个自治系统可以划分为多个区域。OSPF使用Area实现了分层----两层模式，即 transit area(backbone或area 0) 和regular areas(nonbackbone areas) 。transit area负责的主要功能是IP包快速和有效的传输，互联OSPF其他区域类型。一般的，这个区域里不会出现终端用户(end user)。 regular areas负责的主要功能就是连接用户和资源，这种区域一般是根据功能和地理位置来划分。一般情况下，一个regular area不允许其他区域的流量通过它到达另外一个区域，必须穿越transit area，比如area 0。regular areas还可以有很多子类型，比如stub area，和not-so-stubby area。
    区域号用一个32bit的整数来标识，可以定义为IP address格式，也可以用一个十进制整数表示(ie. Area 0.0.0.0, or Area 0)。其中，区域0.0.0.0保留为骨干区域，非骨干区域一定要连接到骨干区域。
    为何需要骨干区域：
    OSPF划分区域之后，并非所有的区域都是平等的关系。其中有一个区域是与众不同的，它的区域号（Area ID）是0，通常被称为骨干区域（Backbone Area）。由于划分区域之后，区域之间是通过ABR将一个区域内的已计算出的路由封装成Type3类的LSA发送到另一个区域之中来传递路由信息。需要注意的是：此时的LSA中包含的已不再是链路状态信息，而是纯粹的路由信息了。或者说，此时的OSPF是基于D-V算法，而不是基于链路状态算法的了。这就涉及到一个很重要的问题：路由自环。因为D-V算法无法保证消除路由自环。如果无法解决这个问题，则区域概念的提出就是失败的。
    通过分析D-V算法中路由环的产生的原因可知，自环的产生主要是因为生成该条路由信息的路由器没有加入生成者的信息，即每一条路由信息都无法知道最初是由谁所生成。OSPF协议在生成LSA时首先将自己的Router ID加入到LSA中，但是如果该路由信息传递超过两个区域后，就会丧失最初的生成者的信息。
    解决的方法是：所有ABR将本区域内的路由信息封装成LSA后，统一的发送给一个特定的区域，再由该区域将这些信息转发给其他区域。在这个特定区域内，每一条LSA都确切的知道生成者信息。在其他区域内所有的到区域外的路由都会发送到这个特定区域中，所以就不会产生路由自环。这个“特定区域”就是骨干区域。由上面的分析可知：所有的区域必须和骨干区域相连，也就是说，每一个ABR连接的区域中至少有一个是骨干区域。而且骨干区域自身也必须是连通的。

    注意：
    如果自治系统被划分成一个以上的区域，则必须有一个区域是骨干区域，并且保证其它区域与骨干区域直接相连或逻辑上相连，且骨干区域自身也必须是连通的。
1.6 COST值

    在OSPF路由协议中，最短路径树的树干长度，即OSPF路由器至每一个目的地路由器的距离，称为OSPF的Cost。Cost值应用于每一个启动了OSPF的链路，它是一个16 bit的正数，范围是1～65535。
    Cost值越小，说明路径越好。
    OSPF选择路径是依靠整个链路Cost值的总和。
    那么Cost值是如何计算的呢？
1.7 Cost（续）

    OSPF协议中，Cost值的计算方法是用108/链路带宽。在这里，链路带宽以bps来表示。也就是说，OSPF的Cost 与链路的带宽成反比，带宽越高，Cost越小，表示OSPF到目的地的距离越近。举例来说，56k的链路花费是1785，10M以太网链路花费是10，64k的链路花费是1562，T1的链路花费是64。
    缺省情况下，接口按照当前的波特率自动计算接口运行OSPF协议所需的开销。
1.8 ABR & ASBR

    ABR区域边界路由器（Area Border Router）：连接多个OSPF区域的路由器。
    ASBR自治系统边界路由器 (Autonomous System Border Router)：一个OSPF路由器，但它连接到另一个AS，或者在同一个AS的网络区域中，但运行不同于OSPF的IGP。
    上图通过不同标志的线条显示了AS内部和AS外部之间路由信息交换的情况。
1.9 思考题

    什么是Router ID ?有什么作用？
    为什么要划分区域？怎样合理规划区域？
    Cost值有什么作用？
第2章 OSPF网络类型

    本章我们将重点介绍OSPF通过LSA描述的几种网络类型。

2.1 OSPF通过LSA描述网络拓扑

OSPF以本路由器邻接网络的拓扑结构为基础计算路由。每台路由器将自己邻接的网络拓扑描述出来，传递给所有其它的路由器。
    根据链路层协议类型，OSPF将网络分为四种类型：
    (1)广播类型：链路层协议是Ethernet、FDDI、Token Ring，以组播的方式发送协议报文，选举DR BDR。
    (2)非广播多路访问Non Broadcast MultiAccess（NBMA）类型：链路层协议是帧中继、ATM、HDLC或X.25时。手工指定邻居，选举DR/BDR，DR/BDR要求和DROTHER完全互连。
    (3)点到多点Point-to-Multipoint（p2mp）类型：没有一种链路层协议会被缺省的认为是Point-to-Multipoint类型。点到多点必然是由其他网络类型强制更改的，常见的做法是将非全连通的NBMA改为点到多点的网络。多播hello包自动发现邻居，不要求DR/BDR的选举。
    (4)点到点Point-to-point（p2p）类型：链路层协议是PPP或LAPB。无需选举DR BDR，当只有两个路由器的接口要形成邻接关系的时候才使用。
    NBMA网络是指非广播、多点可达的网络，典型的有ATM。可通过配置轮询间隔来指定路由器在与相邻路由器构成邻接关系之前发送轮询Hello报文的时间周期。
    若在NBMA网络中并非所有路由器之间都直接可达时，可将接口配置成p2mp方式。
    若该路由器在NBMA网络中只有一个对端，则也可将接口类型改为p2p方式。
    NBMA与p2mp之间的区别：
    (1)在OSPF协议中NBMA是指那些全连通的、非广播、多点可达网络。而点到多点的网络，则并不需要一定是全连通的。
    (2)在NBMA上需要选举DR与BDR，而在点到多点网络中没有DR与BDR。
    (3)NBMA是一种缺省的网络类型，例如：如果链路层协议是ATM，OSPF会缺省的认为该接口的网络类型是NBMA（不论该网络是否全连通）。点到多点不是缺省的网络类型，没有哪种链路层协议会被认为是点到多点，点到多点必须是由其它的网络类型强制更改的。最常见的做法是将非全连通的NBMA改为点到多点的网络。
    (4)NBMA 用单播发送协议报文，需要手工配置邻居。点到多点是可选的，即可以用单播发送，又可以用多播发送报文。
    如上图所示，显示了四种类型的拓扑。其中，通过Hub连接的是广播型网络，两台路由器直接相连的是点到点类型网络，FR/X.25连接的NBMA类型网络，点到多点不是缺省的网络类型，需要手工设置。
2.2 邻居关系太多？

    对于广播和NBMA类型的网络，其内部网络路由器之间是全连接的。如果网络内有上百台路由器，那么将会形成很多的邻接关系，两两互相形成，即100*（100－1）。这些邻居关系要定期更新链路状态数据库LSDB，这样就会消耗大量的系统资源？应该怎么处理呢？
2.3 DR和BDR

    DR的概念：
    在广播和NBMA类型的网络上，任意两台路由器之间都需要传递路由信息（flood），如果网络中有 N 台路由器，则需要建立N *（N-1）/2 个邻接关系。任何一台路由器的路由变化，都需要在网段中进行N*（N-1）/2 次的传递。这是没有必要的，也浪费了宝贵的带宽资源。为了解决这个问题，OSPF协议指定一台路由器DR（Designated Router）来负责传递信息。所有的路由器都只将路由信息发送给DR，再由DR将路由信息发送给本网段内的其他路由器。两台不是DR的路由器（DROther）之间不再建立邻接关系，也不再交换任何路由信息。这样在同一网段内的路由器之间只需建立N个邻接关系，每次路由变化只需进行2N 次的传递即可。
    DR的产生过程：
    通过Hello报文的所带priority位，和DR、BDR信息，可以选出该网段的DR。所有路由器认可一个优先级最高的路由器作为DR，优先级次高的作为BDR，所有这个网段的路由器与DR，BDR构成邻接关系。
    哪台路由器会成为本网段内的DR并不是人为指定的，而是由本网段中所有的路由器共同选举出来的。DR的选举过程如下：
     登记选民

    本网段内的运行OSPF的路由器；

     登记候选人

    本网段内的Priority>0 的OSPF路由器；Priority 是接口上的参数，可以配置，缺省值是1；

     竞选演说

    一部分Priority>0 的OSPF路由器自己是DR；

     投票

    在所有自称是DR的路由器中选priority值最大的当选，若两台路由器的priority值相等，则选Router ID最大的当选。选票就是HELLO报文，每台路由器将自己选出的DR写入HELLO中，发给网段上的每台路由器；
    稳定压倒一切:
    由于网段中的每台路由器都只和DR建立邻接关系。如果DR频繁的更迭，则每次都要重新引起本网段内的所有路由器与新的DR建立邻接关系。 这样会导致在短时间内网段中有大量的OSPF协议报文在传输，降低网络的可用带宽。所以协议中规定应该尽量的减少DR的变化。具体的处理方法是，每一台新加入的路由器并不急于参加选举，而是先考察一下本网段中是否已有DR存在。如果目前网段中已经存在DR，即使本路由器的priority比现有的DR还高，也不会再声称自己是DR了。而是承认现有的DR。
    快速响应：
    如果DR由于某种故障而失效，这时必须重新选举DR，并与之同步。这需要较长的时间，在这段时间内，路由计算是不正确的。为了能够缩短这个过程，OSPF提出了BDR（Backup Designated Router）的概念。BDR实际上是对DR的一个备份，在选举DR的同时也选举出BDR，BDR也和本网段内的所有路由器建立邻接关系并交换路由信息。当DR失效后，BDR会立即成为DR，由于不需要重新选举，并且邻接关系事先已建立，所以这个过程是非常短暂的。当然这时还需要重新选举出一个新的BDR，虽然一样需要较长的时间，但并不会影响路由计算。
    注意：

     网段中的DR并不一定是priority最大的路由器；同理，BDR也并不一定就是priority第二大的路由器。

     DR是指某个网段中概念，是针对路由器的接口而言的。某台路由器在一个接口上可能是DR，在另一个接口上可能是BDR，或者是DROther。

     只有在广播和NBMA类型的接口上才会选举DR，在point-to-point和point-to-muiltipoint类型的接口上不需要选举。

     两台DROther路由器之间不进行路由信息的交换，但仍旧互相发送HELLO报文。他们之间的邻居状态机停留在2-Way状态。

    广播网络或NBMA类型的网络需要选举指定路由器DR（Designated Router）和备份指定路由器BDR（Backup Designated Router）。
    路由器接口的优先级Priority将影响接口在选举DR时所具有的资格。优先级为0的路由器不会被选举为DR或BDR。
    DR由本网段中所有路由器共同选举。Priority大于0的路由器都可作为“候选者”，选票就是Hello报文，OSPF路由器将自己选出的DR写入Hello报文中，发给网段上的其它路由器。当同一网段的两台路由器都宣布自己是DR时，选择Priority高的。如果Priority相等，选择Router ID大的。
    如果DR失效，则网络中的路由器必须重新选举DR，并与新的DR同步，为了缩短这个过程，OSPF提出了BDR（Backup Designated Router，备份指定路由器）的概念，与DR同时被选举出来。BDR也与本网段内的所有路由器建立邻接关系并交换路由信息。DR失效后，BDR立即成为DR，由于不需要重新选举，并且邻接关系已经建立，所以这个过程可以很快完成。这时，还需要选举出一个新的BDR，但已不会影响路由的计算。
    需要说明的是：
    DR并不一定是网段中Priority最大的路由器；同理，BDR也并不一定就是Priority第二大的路由器。若DR、BDR已经选择完毕，即使有一台Priority值更大的路由器加入，它也不会成为该网段中的DR。
    DR是网段中的概念，是针对路由器的接口而言的。某台路由器在一个接口上可能是DR，在另一个接口上可能是BDR，或者是DROther。
    只有在广播或NBMA类型的接口时才会选举DR，在点到点或点到多点类型的接口上不需要选举DR。
2.4 思考题

    (1) LSA描述的网络类型主要有哪些？
    (2) 为什么要选举DR和BDR？它们有什么作用？
第3章 OSPF路由计算过程

    在介绍了OSPF协议的各种术语之后，接下来我们详细介绍OSPF协议路由计算的过程。

3.1 OSPF报文头

Version # OSPF版本号，当前版本2。
    Type OSPF报文类型，包括Hello、DD、LSR、LSU和LSAck等五种报文。
    Router ID 报文起源的Router ID。
    Area ID 一个32位的数，标识报文属于哪个区域，所有OSPF报文只属于单个区域，且只有一跳。当报文在虚链接上承载时，会打上骨干区域0.0.0.0的标签。
    Checksum 包的整个内容的校验，从OSPF报文头部开始，但是除了64位的认证字段。
    AuType 认证类型包括四种：0（无需认证），1（明文认证），2（密文认证）和其他类型（IANA保留）。当不需要认证时，只是通过Checksun检验数据的完整性；当使用明文认证时，64位的认证字段被设置成64位的明文密码；当使用密文认证时，对于每一个OSPF报文，共享密钥都会产生一个“消息位”加在OSPF报文的后面，由于在网络上从来不以明文的方式发送密钥，所以提高了网络安全性。
3.2 OSPF五种协议报文

    OSPF的报文类型一共有五种：
    HELLO报文（Hello Packet）：
    最常用的一种报文，周期性的发送给本路由器的邻居，使用的组播地址224.0.0.5。DR和BDR发送和接收报文使用的组播地址是224.0.0.6。HELLO报文内容包括一些定时器的数值，DR，BDR，以及自己已知的邻居。根据RFC2328的规定，要保持网络邻居间的hello时间间隔一致。需要注意的是，hello时钟的值与路由收敛速度、网络负荷大小成反比。缺省情况下，p2p、broadcast类型接口发送Hello报文的时间间隔的值为10秒；p2mp、nbma类型接口发送Hello报文的时间间隔的值为30秒。
    DD报文（Database Description Packet）：
    路由信息(连接状态传送报文)只在形成邻接关系的路由器间传递。首先，它们之间互发DD（database description）报文，告之对方自己所拥有的路由信息，内容包括LSDB中每一条LSA的摘要（摘要是指LSA的HEAD，通过该HEAD可以唯一标识一条LSA）。这样做是为了减少路由器之间传递信息的量，因为LSA的HEAD只占一条LSA的整个数据量的一小部分，根据HEAD，对端路由器就可以判断出是否已经有了这条LSA。DD报文有两种，一种是空DD报文，用来确定Master/Slave关系（避免DD报文的无序发送），确定Master/Slave关系后，才发送有路由信息的DD报文，收到有路由信息的DD报文后，比较自己的数据库，发现对方的数据库中有自己需要的数据，则向对方发送LSR（Link State Request）报文，请求对方给自己发送数据。
    LSR报文（Link State Request Packet）：
    两台路由器互相交换过DD报文之后，知道对端的路由器有哪些LSA是本地的LSDB所缺少的或是对端更新的LSA，这时需要发送LSR报文向对方请求所需的LSA。内容包括所需要的LSA的摘要。
    LSU报文（Link State Update Packet）：
    用来向对端路由器发送所需要的LSA，内容是多条LSA（全部内容）的集合。
    LSAck 报文（Link State Acknowledgment Packet）
    由于没有使用可靠的TCP协议，但是OSPF包又要求可靠的传输，所以就有了LSAck包。它用来对接收到的LSU报文进行确认。内容是需要确认的LSA的HEAD（一个报文可对多个LSA进行确认）。
    DD报文、LSR报文、LSU报文发出后，在没有得到应有的对方相应的LSR、LSU、LSAck报文时，会重发。（例外：对DD报文若收到后发现没有必要产生连接状态请求报文，则不发连接状态请求报文。）同步后数据改变，则只向形成Adjacency关系的路由器发LSU报文。
3.3 邻接关系的形成与维持

    为了交换路由信息，邻居路由器之间首先要建立邻接关系，并不是每两个邻居路由器之间都能建立邻接关系。Hello报文主要负责建立和维护邻接关系，周期性的在路由器的接口上发送。当路由器发现自己被列在邻居路由器的hello报文中，双向通信就建立起来。在不同类型的链路上，hello报文工作的方式也不同。
    HELLO Interval：接口上发送报文的时间间隔，以秒为单位。如果两路由器不具有相同的呼叫周期，则不能成为邻接关系。
    DEAD Interval：如果在DEAD TIME指定的秒数内没有从已建立的邻居处收到报文，那么，邻居被宣布为故障状态。如果Hello报文中的Dead Interval与接收端口所设置的DeadInterval值不相同，则丢弃该报文。因此，要确保两邻居路由器具有相同的参数。
    邻接关系形成之后，接下来就是同步链路状态数据库。
3.4 OSPF邻居状态机

    Down：
    邻居状态机的初始状态，是指在过去的Dead-Interval时间内没有收到对方的Hello报文。
    Attempt：
    只适用于NBMA类型的接口，处于本状态时，定期向那些手工配置的邻居发送HELLO报文。
    Init：
    本状态表示已经收到了邻居的HELLO报文，但是该报文中列出的邻居中没有包含我的Router ID（对方并没有收到我发的HELLO报文）。
    2-Way：
    本状态表示双方互相收到了对端发送的HELLO报文，建立了邻居关系。在广播和NBMA类型的网络中，两个接口状态是DROther的路由器之间将停留在此状态。其他情况状态机将继续转入高级状态。
    ExStart：
    在此状态下，路由器和它的邻居之间通过互相交换DD报文（该报文并不包含实际的内容，只包含一些标志位）来决定发送时的主/从关系。建立主/从关系主要是为了保证在后续的DD报文交换中能够有序的发送。
    Exchange：
    路由器将本地的LSDB用DD报文来描述，并发给邻居。
    Loading：
    路由器发送LSR报文向邻居请求对方的LSA。
    Full：
    在此状态下，邻居路由器的LSDB中所有的LSA本路由器全都有了。即，本路由器和邻居建立了邻接（adjacency）状态。

    注：
     灰色的状态是指稳定的状态，其他状态则是在转换过程中瞬间（一般不会超过几分钟）存在的状态。

     本路由器和状态可能与对端路由器的状态不相同。例如本路由器的邻居状态是Full，对端的邻居状态可能是Loading。
3.5 邻接关系形成后开始相互交流

    数据库交换的过程主要包括：
    (1) 主从关系协商
    (2) DD报文交换
    (3) LSA请求
    (4) LSA更新
    (5) LSA应答
    下面的内容我们详细介绍OSPF数据库交换过程。、
3.6 OSPF协议数据库交换过程

    上图显示了两台路由器之间如何通过发送5种协议报文来建立邻接关系，以及邻居状态机的迁移。
    (1) RT1的一个连接到广播类型网络的接口上激活了OSPF协议，并发送了一个HELLO报文（使用组播地址224.0.0.5）。由于此时RT1在该网段中还未发现任何邻居，所以HELLO报文中的Neighbor字段为空。
    (2) RT2收到RT1发送的HELLO报文后，为RT1创建一个邻居的数据结构。RT2发送一个HELLO报文回应RT1，并且在报文中的Neighbor字段中填入RT1的Router id，表示已收到RT1的HELLO报文，并且将RT1的邻居状态机置为Init。
    (3) RT1收到RT2回应的HELLO报文后，为RT2创建一个邻居的数据结构，并将邻居状态机置为Exstart状态。下一步双方开始发送各自的链路状态数据库。

     为了提高发送的效率，双方需先了解一下对端数据库中那些LSA是自己所需要的（如果某一条LSA自己已经有了，就不再需要请求了）。方法是先发送DD报文，DD报文中包含了对本地数据库中LSA的摘要描述（每一条摘要可以惟一标识一条LSA，但所占的空间要少得多）。由于OSPF直接用IP报文来封装自己的协议报文，所以在传输的过程中必须考虑到报文传输的可靠性。为了做到这一点，在DD报文的发送过程中需要确定双方的主从关系。作为Master的一方定义一个序列号seq，每发送一个新的DD报文将seq 加一。作为Slave的一方，每次发送DD报文时使用接收到的上一个Master的DD报文中的seq。实际上这种序列号机制是一种隐含的确认方法。如果再加上每个报文都有超时重传，就可以保证这种传输是可靠的。

     RT1首先发送一个DD报文，宣称自己是Master（MS=1），并规定序列号为x。I=1表示这是第一个DD报文，报文中并不包含LSA的摘要，只是为了协商主从关系。M=1说明这不是最后一个报文。

    (4) RT2在收到RT1的DD报文后，将RT1的邻居状态机改为Exstart，并且回应了一个DD报文（该报文中同样不包含LSA的摘要信息）。由于RT2的Router ID较大，所以在报文中RT2认为自己是Master，并且重新规定了序列号为y。
    (5) RT1收到报文后，同意了RT2为Master，并将RT2的邻居状态机改为Exchange。RT1使用RT2的序列号y来发送新的DD报文，该报文开始正式地传送LSA的摘要。在报文中RT1将MS=0，说明自己是Slave。
    (6) RT2收到报文后，将RT1的邻居状态机改为Exchange，并发送新的DD报文来描述自己的LSA摘要，需要注意的是：此时RT2已将报文的序列号改为y+1了。
    (7) 上述过程持续进行，RT1通过重复RT2的序列号来确认已收到RT2的报文。RT2通过将序列号+1来确认已收到RT1的报文。当RT2发送最后一个DD报文时，将报文中的M=0，表示这是最后一个DD报文了。
    (8) RT1收到最后一个DD报文后，发现RT2的数据库中有许多LSA是自己没有的，将邻居状态机改为Loading状态。此时RT2也收到了RT1的最后一个DD报文，但RT1的LSA，RT2都已经有了，不需要再请求，所以直接将RT1的邻居状态机改为Full状态。
    (9) RT1发送LS Request报文向RT2请求所需要的LSA。RT2用LS Update报文来回应RT1的请求。RT1收到之后，需要发送LS Ack报文来确认。上述过程持续到RT1中的LSA与RT2的LSA完全同步为止。此时RT1将RT2的邻居状态机改为Full状态。
    注意：
    以上讨论是基于系统初始化达到同步过程的描述。但在系统达到同步后，某一台路由器的路由表发生变化（如：接口UP，DOWN，花费改变），OSPF的处理方法就有所不同：只对路由变化的部分，发送变化对应的LSU报文，对路由减少的项（接口或路由器DOWN掉），把Age位置位为MaxAge（3600秒），收到该LSU报文的路由器比较自己的路由表，如果跟自己的路由表不同，则把路由表更新，发送相应的LSU报文。如此类似链式反应的发送，我们称之为“泛洪”，把升级的路由表在系统内同步了。
    数据库同步的简要概括：
    路由信息（LSA）只在形成邻接关系的路由器之间传递，通过互发DD报文来实现。假设RTA、RTB为两台具有邻接关系的路由器，首先RTA发送一种空DD报文，用来确定Master/Slave关系（避免DD报文的无序发送）。然后RTA发送有路由信息DD报文给RTB，RTB将报文与自己的数据库比较。如果发现对方那里有自己需要的数据，则向对方发送连接状态请求报文，请求对方给自己发送相应数据。RTA收到连接状态请求报文后，按要求发送新的路由信息给对方，即发送连接状态升级报文。收到连接状态升级报文后，RTB会发送连接状态响应报文，以示收到。通过邻接间的连接状态传送报文的传递，路由信息在同一个网段内达到同步。可能会有路由器属于同一区域内的两个不同网段A、B（只需在两个接口上配置OSPF），那么，这个路由器会把Ａ、Ｂ网段的信息互相传播以使两网段的信息同步。依此类推：区域内不同网段的信息可以全部达到同步。
    作为边界路由器，由协议规定，它应该属于骨干，它会把它得到的路由信息摘要，发给骨干上其他点。骨干上的点会首先得到全自治系统的拓扑结构，然后把它传道所连的非骨干区域内部。这样，所有的路由器都得到了整个自治系统的拓扑结构。
    对于ASBR，发送自己接收到的其他AS传送来的LSA给本AS内部的路由器，同样也将本AS内部的信息组合成LSA发送到其他AS的ASBR。这样任何一个路由器都可以知道整个网络的LADB。即可以判断是否存在一条通往网络上其他节点的路由。
3.7 OSPF协议路由计算过程

    上图中描述了通过 OSPF 协议计算路由的过程。由四台路由器组成的网络，连线旁边的数字表示从一台路由器到另一台路由器所需要的花费。为简化问题，我们假定两台路由器相互之间发送报文所需花费是相同的。
首先，每台路由器都根据自己周围的网络拓扑结构生成一条 LSA（链路状态广播），并通过相互之间发送协议报文将这条 LSA 发送给网络中其它的所有路由器。这样每台路由器都收到了其它路由器的 LSA，所有的 LSA     放在一起称作 LSDB（链路状态数据库）。显然，4 台路由器的 LSDB 都是相同的。
    其次，由于一条 LSA 是对一台路由器周围网络拓扑结构的描述，那么 LSDB 则是对整个网络的拓扑结构的描述。路由器很容易将 LSDB 转换成一张带权的有向图，这张图便是对整个网络拓扑结构的真实反映。显然，4 台路由器得到的是一张完全相同的图。
    最后，接下来每台路由器在图中以自己为根节点，使用SPF算法计算出一棵最短路径树，由这棵树得到了到网络中各个节点的路由表。显然，4 台路由器各自得到的路由表是不同的。
    这样每台路由器都计算出了到其它路由器的路由。
    由上面的分析可知：OSPF协议计算出路由主要有以下三个主要步骤：

     描述本路由器周边的网络拓扑结构，并生成LSA。

     将自己生成的LSA在自治系统中传播。并同时收集所有的其他路由器生成的LSA。

    根据收集的所有的LSA计算路由。
    路由计算用的算法是Dijkstra算法，描述如下：
    Step1：把root加入最小树，设root可直达的顶点为候选人。
    Step2：若候选人列表空，则最小树生成完成，否则候选人列表中选取花费最小的，加入到最小树中。
    Step3：把新加入的顶点所能直达的顶点列为候选人。
    Step4：在候选人名单里除去最小树中已出现的，回Step2
    工作过程：通过LSDB可得各路由器的连接(link)状态(state)，利用Dijkstra算法，可由“内”向“外”，从区域内到区域间，从AS内到AS外，逐步生成最小树,进而生成路由表。
    在计算过程中，以路由器附属的每一个区域为出发点，计算每一个区域的最小树(相当与一个阶段性的最小树)，区域的最小树包括该区域内部路由器和子网，该区域所知道的其它区域的子网节点，该区域所知道的ASBR路由器，ASE节点，系统根据所得的区域的最小树，逐区域改进最小树，最后生成全局的最小树，改进路由表，并根据路由表的变化，调用生成和发送连接状态传送报文的函数，向外发送新的连接信息。
    下面详细介绍路由表计算过程：