路由选择协议（routing protocol）作为路由器之间进行相互交流的语言，用于实现可达性信息和网络状态的共享。动态路由选择协议不仅执行路径决策和路由表更新功能，而且还要在最优路径不可用时决策下一条最优路径。动态路由选择相比静态路由选择而言，其最大的优势在于动态路由选择能够缓解拓扑变化带来的影响。
路由选择协议基础
显然，为了正确地通信，通信双方必须使用相同的语言。自从 IP 路由选择出现以来，共有 8 种主要的 IP 路由选择协议可供选择。所有路由选择协议都是围绕着一种算法而构建的。通常，一种算法是一个逐步解决问题的过程。一种路由算法至少应该指明以下内容：
- 向其他路由器传送网络可达性信息的过程
- 从其他路由器接收可达性信息的过程
- 基于现有可达性信息决策最优路由的过程以及在路由表中记录这些信息的过程
- 响应、修正和通告网络中拓扑变化的过程
对所有路由选择协议来说，几个共同的问题是：路径决策、度量、收敛和负载均衡。
路径决策
在网络内的所有子网都必须连接到一台路由器上，无论什么情况下，只要路由器有接口连接到一个网络上，那么该接口必须具有一个属于该网络的地址，这个地址就是可达性信息的起始点 。
如下给出了一个包含 3 台路由器的网络，路由器的每个接口都配置了相应的地址和掩码，同时每个接口都实现了所连网络的数据链路和物理层协议，因此路由器也知道网络的状态（工作正常为 up 或发生故障为 down）。
考虑路由器 A 的信息共享过程：
- 路由器 A 检查自己的 IP 地址和相关的掩码，然后推导出与自身所连接的网络是 192.168.1.0，192.168.2.0 和 192.168.3.0
- 路由器 A 将这些网络连同某些标记一起保存到路由表中，其中标记指明了网络是直连网络
- 路由器 A 向路由信息数据包中添加以下信息：路由器 A 的直连网络有：192.168.1.0，192.168.2.0 和 192.168.3.0
- 路由器 A 向路由器 B 和路由器 C 发送这些路由信息数据包的拷贝，或者称为路由选择更新
- 路由器 B 和路由器 C 将收到的信息连同发送路由器的源地址一起写入路由表，这样路由器 B 和路由器 C 就知道了路由器 A 所连接的网络
- 路由器 B 和路由器 C 也执行类似的步骤，这样所有的路由器就知道了所有的网络，而且还知道连接这些网络的路由器的地址。这个过程看似简单，但是仍然存在很多的问题。正是这些问题造成了协议的复杂性。每种路由选择协议都需要解决这些问题。
度量
当有多条路径到达相同目标网络时，路由器需要一种机制来计算最优路径。度量是指派给路由的一种变量，作为一种手段，度量可以对路由进行等级划分。
不同的路由选择协议使用不同的度量。例如，RIP 定义含有路由器跳数最少的路径是最优路径。EIGRP 基于路径沿路最小带宽和总时延定义最优路径。以下是一些常用度量的定义：
- 跳数：跳数（Hop Count）度量可以简单地记录路由器跳数
- 带宽：带宽（Bandwidth）度量将会选择高带宽路径，而不是低带宽链路
- 负载：负载（Load）度量反映了流量占用沿途链路带宽的数量。最优路径应该是负载最低的路径。不像跳数和带宽，路径上的负载会发生变化，因而度量也会发生变化。如果度量变化过于频繁，可能会产生路由波动（最优路径频繁变化）。路由波动对路由器的 CPU、数据链路的带宽和全网稳定性会产生负面影响
- 时延：时延（Delay）是度量数据包经过一条路径所花费的时间。使用时延度量的路由选择协议将会选择最低时延的路径作为最优路径。时延不仅要考虑链路时延，而且还要考虑路由器的处理时延和队列时延等因素。但是路由的时延可能无法测量，因此时延可能是沿路径各接口所定义的静态延时量总和，其中每个独立的时延量都是基于连接接口的链路类型估算得到
- 可靠性：可靠性（Reliability）度量是用来测量链路在某种情况下发生故障的可能性。可靠性可以是变化的或固定的。可靠性最高的路径将会被优先选择
- 代价：由管理员设置的代价（Cost）度量可以反应更优或更差路由。通过任何策略或链路特性都可以对代价进行定义，同时代价也可以反应出网络管理员对路径的随意判断。因此代价是一个描述无量纲度量的术语
收敛
动态路由选择协议必须包含一系列过程，这些过程用于路由器向其他路由器通告本地的直连网络，接收并处理来自其他路由器的同类信息，以及传递从其他路由器接收到的信息。此外，路由选择协议还需要定义用于确定最优路径的度量。
对路由选择协议来说，另一个标准是网络上所有路由器的路由表的可达性信息必须一致。使所有路由表都达到一致状态的过程叫做收敛，全网实现信息共享以及所有路由器计算最优路径所花费的时间总和就是收敛时间。
网络处于未收敛状态的这段时间内，可能发生路由选择错误。因此，在任何路由选择协议里收敛时间都是一个重要的因素，在拓扑发生变化后，一个网络的收敛速度越快越好。
负载均衡
为了有效地使用带宽，负载均衡作为一种手段，将流量分配到目标网络的多条路径上。负载均衡可以是等价或不等价，基于数据包或基于目标地址的。
距离矢量路由选择协议
大多数路由选择协议都属于如下两类的其中之一：
- 距离矢量（distance vector）
- 链路状态（link state）
距离矢量名称的由来是因为路由是以矢量（距离，方向）的方式被通告出去的，其中距离是根据度量定义的，方向是根据下一跳路由器定义的。因为每台路由器在信息上都依赖于邻接路由器，而邻接路由器又从它们的邻接路由器那里学习路由，依次类推，所以距离矢量路由选择有时又被称为是 依照传闻进行路由选择。
通用属性
典型的距离矢量路由选择协议通常会使用一个路由选择算法，算法中路由器通过广播整个路由表，定期地向所有邻居发送路由更新信息。
- 定期更新：定期更新意味着每经过特定时间周期就要发送更新信息。这里有争议的是，如果更新信息发送过于频繁可能会引起拥塞，但如果更新信息发送不频繁，收敛时间可能过长
- 邻居：在路由器上下文中，邻居通常意味着共享相同数据链路的路由器或某种更高层的逻辑邻居关系。距离矢量路由选择协议向邻接路由器发送更新信息，并依靠邻居再向它的邻居传递更新信息。因此，距离矢量路由选择被说成使用逐跳更新方式
- 广播更新：当路由器首次在网络上被激活时，路由器为了宣布自己的存在，最简单的方法是向广播地址发送（IP 广播地址为 255.255.255.255）更新信息。使用相同路由选择协议的邻居路由器将会收到广播数据包并采取相应的动作，不关心路由更新信息的主机和其他设备仅仅丢弃数据包
- 全路由选择表更新：大多数距离矢量路由选择协议使用非常简单的方式告诉邻居它所知道的一切，该方式就是广播它的整个路由表。但是邻居在收到这些更新信息之后，他们会收集自己需要的信息，而丢弃其它信息
依据传闻进行路由选择
距离矢量算法提供了指向网络的路标，该算法给出了方向和距离，但是没有给出沿着这条路径行走的细节。就像岔路口的路标一样，它很容易受到意外或故意的误导。下面是距离矢量算法所面临的的一些困难及算法的改进。
路由失效计时器
如果路由器的某个直连网络发生故障，在下一个更新周期中，路由器将这个网络标记为不可达并且发送该信息。但是如果路由器本身发生故障，此时路由器本身无法发出通知消息，这导致其他路由器可能继续向一个不可达的网络转发数据包。
处理这个问题的办法是为路由表中的每个表项设置路由失效计时器，每次收到其他路由器对该路由表项的更新信息后，都会重新复位该路由表项的计时器。如果路由器发生故障，则其邻接路由器无法接收到相应路由表项的更新信息，这时计时器将会超时，邻接路由器将相应的路由标记为不可达，并将在下一个更新周期中传递该信息。
路由超时的典型周期范围是 3-6 个更新周期。路由器在丢失单个更新信息之后将不会使路由无效，因为数据包的损坏、丢失或某种网络延迟都会造成这种事件的发生。但是如果路由失效周期太长，网络收敛速度将会过慢。
水平分割
路由的指向与数据包流动方向相反的路由被称为逆向路径（reverse route），水平分割是一种在两台路由器之间阻止逆向路由的技术。这样做除了不会浪费资源，还有一个很重要的原因是不会把从路由器学习到的可达性信息在返回给这台路由器。动态路由选择协议最重要的功能是检测和补偿拓扑变化，如果网络的最优路径不可用，协议必须寻找下一个最优路径。
执行水平分割可以阻止路由环路的发生，有两类水平分割方法：简单水平分割法和毒性逆转水平分割法。
- 简单水平分割的规则是：从某接口发送的更新消息不能包含从该接口收到的更新中所包含的网络
- 毒性逆转水平分割法的规则是：当更新信息被发送出某接口时，信息中将指定从该接口收到的更新信息中获取的网络是不可达的，通过设置度量为无穷大可以标记网络为不可达
简单水平分割采用抑制信息的工作方式，毒性逆转水平分割法是一种改进方法，它可以提供更积极的信息。毒性逆转水平分割发被认为比简单水平分割法更安全更健壮：一种 坏信息总比没消息好 的方法。正因如此，大部分现代距离矢量算法的实现都使用了毒性逆转水平分割法。缺点是使更新数据包更大了，可能会加剧链路的拥塞问题。
计数到无穷大
水平分割法切断了邻居路由器之间的环路，但是它不能隔断网络中的环路。这种情况下会出现计数到无穷大的情形，虽然所有路由器都执行了水平分割，但对此无能为力。
这里举个例子，在如下网络中，假设路由器 D 的链路 10.1.5.0 失效，它会向路由器 C 和路由器 B 发送相应的更新消息，于是路由器 B 和路由器 C 将相应的路由标记为不可达。假设此时正好路由器 A 向路由器 B 通告了一条到达 10.1.5.0 的路由，距离为 3 跳，路由器 B 将记录下这条路由并通告给路由器 D，此后，这条路由信息将不断在网络中传递，但是跳数会不断增加。如此循环下去，这种情况就叫计数到无穷大。
减轻计数到无穷大影响的方法是定义无穷大，大多数距离矢量协议定义无穷大为 16 跳。随着路由更新信息在网络环路中循环，最终某个不可达网络的跳数将会达到 16 跳，此时该网络就认为不可达。
这也是路由器如何通告网络不可达的一种方法，一个网络发生故障，不管它是毒性逆转路由，还是超过最大网络尺寸 15 跳的路由，路由器把所有跳数为 16 的路由看做不可达。
设置最大跳数有助于解决计数到无穷大的问题，但是收敛速度仍旧非常慢，假设更新周期为 30s，网络可能需要 7.5min 达到收敛，这期间容易受到路由错误的影响。触发更新可以有助于减少收敛时间。
触发更新
触发更新（Triggered Update）又叫做快速更新。如果一个度量变好或变换，那么路由器将立即发送更新消息，而不必等计时器超时。这样收敛的速度将会更快，而且可以大大减少计数到无穷大所引发的问题，虽然不能完全消除。
定期更新和触发更新可能一起发生，因而路由器可能会在收到来自触发更新的正确信息后又收到来自未收敛路由器的错误信息。这种情况表明，当网络正在进行重新收敛时，还会发生混乱和路由错误。但是触发更新将有助于更快地消除这些问题。
对触发更新的进一步改进是更新信息中仅包括实际触发该事件的网络，而不是包含整个路由表。触发更新技术减少了处理时间和对网络带宽的影响。
抑制计时器
触发更新为正在重新进行收敛的网络增加了应变能力。为了降低接受错误路由选择信息的可能性，抑制机制器（Holddown Timer）引入了某种程度的怀疑量。如果到一个目标的距离增加，那么路由器将为该路由设置抑制计时器，直到计时器超时，路由器才可以接受有关此路由的更新信息。
这是一种折中方法，错误路由选择信息进入路由表的可能性被减少了，但是重新收敛的时间也被消耗了。因此需要小心设置抑制计时器。
异步更新
当几台路由器共享一个广播网络时，路由器可能会同时发送广播更新信息，更新数据包因此会发生碰撞。因为在路由器中，更新处理所带来的系统时延将导致更新计时器趋于同步。当几台路由器的计时器同步后，碰撞随之发生，这又进一步影响系统时延，最终共享广播网络的所有路由器都可能变得同步起来。
可以使用下面两种方法维持异步更新：
- 每台路由器的更新计时器独立于路由选择进程，因而不会受到路由器处理负载的影响
- 在每个更新周期中加入一个小的随机时间或定时抖动作为偏移
链路状态路由选择协议
距离矢量路由器所使用的信息可以比拟为由路标提供的信息，而链路状态路由选择协议更像是一张公路线路图。链路状态路由器是不容易被欺骗而做出错误的路由决策的，因为它有一张完整的网络图。
链路状态不同于距离矢量依照传闻进行路由选择的工作方式，原因是链路状态路由器从对等路由器那里获取第一手信息。每台路由器会产生关于自己、本地直连链路、这些链路的状态和所有直接相连邻居的信息。这些信息从一台路由器传送到另一台路由器，每台路由器都做一份信息拷贝，但是绝不改动信息。最终目的是每台路由器都有一个相同的有关网络的信息，并且每台路由器可以独立地计算各自的最优路径。
链路状态协议，有时叫最短路径优先协议或分布式数据库协议，是围绕着图论中的一个著名算法：E.W.Dijkstra 的最短路径算法设计的。
虽然链路状态协议确实考虑的比距离矢量协议更复杂，但是基本功能却一点也不复杂：
- 每台路由器与它的邻居之间建立联系，这种联系叫做邻接关系
- 每台路由器向每个邻居发送被称为链路状态通告（LSA）的数据单元。对每条路由器链路都会生成一个 LSA，LSA 用于标识这条链路、链路状态、路由器接口到链路的代价度量值以及链路所连接的所有邻居。每个邻居在收到通告之后将依次向它的邻居泛洪这些通告
- 每台路由器都要在数据库中保存一份它所收到的 LSA 的备份。如果所有工作正常，所有路由器的数据库应该相同
- 完整的拓扑数据库，也叫链路状态库。Dijkstra 算法使用它对网络图进行计算得出每台路由器的最短路径。接着链路状态协议对链路状态数据库进行查询找到每台路由器所连接的子网，并把这些信息输入到路由表中
邻居
邻居发现是建立链路状态环境并运转的第一步，这里将使用 Hello 协议。Hello 协议定义了一个 Hello 数据包的格式和交换数据包并处理数据包信息的过程。
Hello 数据包至少应该包含一个路由器 ID 和发送数据包的网络地址。路由器 ID 可以将发送该 Hello 数据包的路由器和其他路由器唯一地区分开。
当两台路由器已经互相发现并将对方视为邻居时，它们要进行数据库同步过程，即交换和确认数据库信息直到数据库相同为止。为了执行数据库同步，邻居之间必须建立邻接关系，即他们必须就某些特定的协议参数，如计时器和对可选择能力的支持，达成一致意见。通过使用 Hello 数据包建立邻接关系，链路状态协议就可以在受控的方式下交换信息。与距离矢量相比，这种方式仅在配置了路由选择协议的接口上广播更新信息。
除了建立邻接关系之外，Hello 数据包还可作为监视邻接关系的握手信号。如果在特定的时间内没有从邻接路由器收到 Hello 数据包，那么认为邻居路由器不可达，随即邻接关系被解除。
链路状态泛洪扩散
在建立邻接关系之后，路由器开始泛洪扩展 LSA。通告被发送给每个邻居，路由器保存接收到的 LSA，并依次向每个邻居转发（除了发送该 LSA 的邻居之外）。LSA 几乎是立即被转发的，而距离矢量在发送路由更新之前必须运行算法并更新自身的路由表，甚至对触发更新也是如此。因此当网路拓扑发生改变时，链路状态协议收敛速度远远快于距离矢量协议。
泛洪扩散过程是链路状态协议中最复杂的一部分，有几种方式可以使泛洪扩散更高效和更可靠，如使用单播和组播地址、校验和以及主动确认。有两个过程对泛洪扩散是极其重要的：排序和老化。
序列号
泛洪扩散的一个难点是当所有路由器收到所有 LSA 时，泛洪扩散必须停止。尽管 TTL 值可以终止过期的数据包，但是在 TTL 减为 0 之前 LSA 仍然会在网络中漫游。
当路由器发送 LSA 时，同一个 LSA 的每一个拷贝中的序列号都是一样的，这个序列号和 LSA 的其他部分一起被保存在路由器的拓扑数据库中，当路由器收到数据库中已经存在的 LSA 且序号相同时，路由器将丢弃这些信息。如果信息相同但是序列号更大，那么接收的信息和新序列号被保存到数据库中，并且泛洪扩散该 LSA。按照这种方式，当所有路由器都收到 LSA 的最新拷贝时，泛洪扩展将停止。如果收到的 LSA 信息的序列号小于数据库中当前保存的 LSA 序列号，则认为该 LSA 是过时的信息而被丢弃。
因为序列号被携带在 LSA 中的一个固定字段内，所以序列号一定有上限：
- 线性序列号空间
一种办法是使用一个非常大的线性序列号空间以至于根本不可能达到上限。
但是假设一个链路状态路由选择进程用完了所有序列号，那么它在重新使用最低序列号之前必须停止，等待它所发出的 LSA 在所有的数据库中都不再被使用。而且假设路由器重启，它无法记得上次使用的序列号，必须重新使用 1，而其他邻居仍然保存了该路由器重启之前的 LSA 序列号，那么越小的序列号也就是越旧的序列号，因而会被忽略，因此路由选择进程必须一直等待网络上所有旧的 LSA 都消失。
更好的解决办法是在泛洪扩散行为中添加新的规则：如果一台重新启动的路由器向邻居发送 LSA 的序列号比邻居保存的序列号还要老，那么邻居会回发自己保存的 LSA 和序列号，这台路由器将知道启动前自己使用的序列号并作出相应调整。
但是需要小心，最近使用过的序列号不能接近上限，否则重新启动的路由器将不得不再次重新启动。必须设定规则限制路由器 跳跃 地使用序列号。
IS-IS 使用 32 位线性序列号空间。
- 循环序列号空间
另一种方法是使用循环序列号空间，数字是循环使用的，然而重新启动的路由器可能会遇到同线性序列号一样的问题。而且其需要明确的规则来确定什么时候一个序列号大于或小于另一个序列号。在运行状况不佳的网络上，由于数据差错可能导致 LSA 无限循环在网络上传递（现代网络的先驱 ARPANET 曾经出现过该故障）。
- 棒棒糖形序列号空间
棒棒糖形序列号空间是线性序列号空间和循环序列号空间的综合，其包含一个线性组件和一个圆形组件。圆形空间的缺点是不存在一个数小于其他所有的数，线性空间的缺点是不能循环使用序列号，即序列号是有限的。
当路由器 A 重新启动后，它将从小于其他所有数的 a 开始。邻居将会识别出这个数，这时如果邻居数据库还保留有上次序列号 b 的 LSA，那么它们会发送 b 给路由器 A，则路由器 A 将调至该序列号。在知道自己重启前使用的序列号之前，路由器 A 可能会发送不止一个 LSA。因此，在邻居通知路由器 A 上次使用的序列号或上次使用的序列号从所有数据库中消失之前，必须准备充足的启动数以便路由器 A 不会用光所有序列号。
这些线性重启序列号形成了棒棒糖的棒，在这些数用完或邻居提供了使路由器 A 跳转的序列号之后，路由器 A 进入了循环数空间，即棒棒糖的糖体部分。
在设计棒棒糖地址空间时使用了有符号数，即 -k < 0 < k，从 -k 到 1 的负数形成了棒棒，从 0 到 k 的正数形成循环空间。
OSPFv2 采用了线性和棒棒糖形序列号空间的最好的特性。OSPFv2 像棒棒糖形序列号数一样使用了 0x80000001 开始的有符号数空间，但是当序列号数变为正数时，序列号空间保持持续线性直至最大数 0x7FFFFFFF 为止。此刻，在重启之前 OSPF 进程必须从所有链路状态数据库中删除 LSA。
老化
LSA 格式中包含一个用于通告年龄的字段。当 LSA 被创建时，路由器将该字段设置为 0。随着数据包的扩散，每台路由器都会增加通告中的年龄（另一个选项时是从某个最大年龄开始，然后递减。OSPF 是递增，IS-IS 是递减）。
老化过程为泛洪扩散过程增加了另一层可靠性，该协议为网络定义了一个最大年龄差距（MaxAgeDiff）值。路由器可能收到一个 LSA 的多个拷贝，其中序列号相同，年龄不同。如果年龄的差距小于 MaxAgeDiff，那么认为是由于网络的正常时延造成了年龄的差异，因此数据库原有的 LSA 继续保存，新收到的 LSA（年龄更大）不被扩散。如果年龄差距超过 MaxAgeDiff，那么认为网络发生异常，因为新被发送的 LSA 的序列号值没有增加。这种情况下，较新的 LSA 被记录下来，并将数据包扩散出去。
若 LSA 驻留在数据库中，则 LSA 的年龄会不断增加。如果链路状态记录的年龄增加到某个最大年龄值（MaxAge），那么一个带有 MaxAge 值的 LSA 被泛洪扩散到所有邻居，邻居随机从数据库中删除相关记录。
当 LSA 的年龄到达 MaxAge 时，将从所有的数据库中删除。这需要有一种机制来定期地确认 LSA 并且在达到最大年龄之前将它的计时器复位。链路状态刷新定时器（LSRefeshTime）就是做此用途的：一旦计时器超时，路由器将向所有邻居泛洪扩散新的 LSA，收到的邻居会把有关路由器记录的年龄设置为新收到的年龄。
链路状态数据库
除了发现邻居和泛洪扩散 LSA 外，链路状态路由选择协议的第 3 个主要任务是建立链路状态数据库。链路状态数据库或拓扑数据库把 LSA 作为一连串记录保存下来。虽然 LSA 还包括序列号、年龄和其他信息，但这些变量主要用于管理泛洪扩散过程。对于最短路径的决策进程来说，通告路由器的 ID、连接的网络和邻居路由器以及与网络和邻居相关联的代价是非常重要的信息。
因此，LSA 还包括两类通用信息：
- 路由器链路信息：使用三元组（路由器 ID、邻居 ID、代价）通告路由器的邻居路由器，这里的代价是指链路到邻居的代价
- 末梢网络信息：使用三元组（路由器 ID、网络 ID、代价）通告路由器直接连接的末梢网络（没有邻居的网络）
- 最短路径优先（Shortest Path First，SPF）算法对路由器链路信息进行一次计算以建立到每台路由器的最短路径，然后使用末梢网络信息向路由器添加网络。链路状态数据库完整地描述了网络，通过运行 SPF 算法可以计算出一颗到达每台路由器的最短路径树。
SPF 算法
构造一颗树 [a]，使 n 个节点之间的总长最小（树是一个在每两个节点之间仅有一条路径的图）。构造过程中，分支被分成 3 个集合：
- 集合 1：被明确分配给构造中的树的分支（它们将在子树中）
- 集合 2：这个分支的隔壁分支被添加到集合 1
- 集合 3：剩余的分支（已拒绝或不考虑）
节点被分成 2 个集合：
- 集合 A：被集合 1 中的分支连接的节点
- 集合 B：剩余的节点
以下是构建树的过程。首先选择任意一个节点作为集合 A 中仅有的成员，并将所有拿这个节点做端点的分支放入集合 2 中，集合 1 开始是空的，然后重复执行以下两个步骤
- 步骤1：集合 2 中最短的分支被移出并加入结合 1 中，结果一个节点被从集合 B 传送到集合 A
- 步骤2：考虑从这个节点（刚才被传送到集合 A 中的节点）通向集合 B 中节点的分支。如果构建中的分支长于集合 2 中相应的分支，那么分支被丢弃，否则用它替代集合 2 中相应的分支，并且丢弃后者
回到步骤 1 并重复此过程，直到集合 2 和集合 B 为空。集合 1 中的分支形成所要求的树
配合路由器的算法，第一点注意的是，Dijkstra 描述了 3 个分支的集合，在路由器中，使用 3 个数据库表示 3 个集合：
- 树数据库：树数据库用来表示集合 1，通过向数据库中添加分支实现向最短路径树中添加链路（分支）。当算法完成时，这个数据库将可以描述最短路径树
- 候选对象数据库：候选对象数据库对应集合 2，按照规定的顺序从链路状态数据库向该列表中复制链路，作为向树中添加候选对象
- 链路状态数据库：按照前面的描述，这里保存所有链路，这个拓扑数据库对应集合 3
Dijkstra 算法还指定了两个节点集合：A 和 B。这里的节点是路由器，这些路由器被明确地用路由器链路三元组（路由器 ID、邻居 ID、代价）中的 ID 表示。集合 A 由数据库中的链路所连接的路由器组成，集合 B 是所有其他的路由器。由于最终结果是发现到每台路由器的最短路径，所以当算法结束时集合 B 应该为空。
下面是一台路由器中采用的 Dijkstra 算法版本：
- 步骤 1：路由器初始化树数据库，将自己作为树的根。这表明路由器作为它自己的邻居，代价为 0，根节点从集合 B 移动到集合 A 中，
- 步骤 2：在链路状态数据库中，所有描述从根路由器出发，到达其邻居的链路三元组信息被添加到到候选对象数据库中
- 步骤 3：计算从根到每条链路的代价，候选对象数据库中代价最小的链路被移到树数据库中。如果两个或更多的链路离根的最短代价相同，选择其中一条。所选择链路三元组中的 Neighbor ID 所表示的路由器从集合 B 移动到集合 A 中
- 步骤 4：检查刚刚添加到树数据库中的链路三元组信息中的邻居 ID（假设为 X）。除了那些 Neighbor ID 已经在树数据库中的三元组之外，链路状态数据库中所有以 X 为起点的链路三元组被添加到候选对象数据库中
- 步骤 5：如果集合 B 中还存在节点，回到步骤 3 ，如果集合 B 中为空，则终止算法。在树算法终止时，在数据库中，每一个单一的邻居 ID 表项将表示一台路由器，至此最短路径树构建完毕
- 在每台路由器完成自己的最短路径树的计算之后，它会检查其他路由器的网络链路信息，并且可以很容易地把末梢网络添加到树中。根据这些信息，表项可以制作为路由表。
区域
一个区域是构成一个网络的路由器的一个子集。将网络划分为区域是针对链路状态协议的 3 个不利影响所采取的措施：
- 必要的数据库导致所要求的的内存数量比距离矢量协议更多
- 复杂的算法要求 CPU 时间比距离矢量协议更多
- 链路状态泛洪扩散数据包对可用带宽带来了不利影响，特别是不稳定的网络
目前设计的链路状态协议和使用该协议的路由器都能够减少这些影响，但是却没有消除这些影响。通过划分区域可以减少这些影响，在一个区域内的路由器仅需要在本区域扩散 LSA，因而只需要维护本区域的链路状态数据库。数据库越小，意味着需要的内存越小，运行 SPF 算法所需要的 CPU 周期也越少。如果拓扑改变频繁发生，引起的扩散将被限制在不稳定的区域。
区域边界路由器是连接两个区域的路由器，它属于所连接的两个区域，而且必须为每个区域维护各自的拓扑数据库。在一个区域内想往其他区域发送数据包的路由器仅需要知道怎样找到本地区的区域边界路由器。
距离矢量协议，如 RIP 和 IGRP，不使用区域。假如这些协议除了把一个大型网络看成一个单一的实体外，没有任何依靠，那么它们就必须计算出到每个网络的路由，并且需要定期广播这个巨大的路由表。因此，利用区域的链路状态协议可以节省系统资源。
内部和外部网关协议
区域向网络体系结构中引入了一个层次，在此基础上，将一组区域组成一个更大的区域又向网络体系结构中引入了另一个层次。这些更高层的区域在 IP 领域内叫自治系统，在 ISO 模型中叫路由选择域。
一个自治系统被定义为在共同管理域下的一组运行相同路由选择协议的路由器。但是随着现代网络的发展，许多网络使用多种不精确的等级将多种路有选择协议结合在一起，并处于共同的管理之下。所以自主系统的当前定义应该是在共同管理下的网络。
一个自主系统内运行的路由选择协称为内部网关协议（Interior Gateway Protocols，IGP）。在自主系统之间或路由选择域之间的路由选择协议称为外部网关协议（Exterior Gateway Protocols，EGP）。IGP 发现网络之间的路径，而 EGP 发现自治系统之间的路径。
静态或动态路由选择
动态路由选择协议的主要任务是自动监测和适应网络拓扑的变化，但是为了实现 自动化，需要在带宽、队列空间、内存和处理时间上付出代价。
使用动态路由选择协议的另一个代价是减少了对路由选择的控制。对于一个指定的目标网络，路由选择协议可以替代我们确定最佳路径。如果需要进行精确的路由选择，特别是当你期望的路径和路由选择协议选择的不一致时，还是使用静态路由选择更好一些。
静态路由选择的最大缺陷是管理困难，这对于存在许多可选路由的中型和大型网络来说是真实的，但对于几乎没有可选路由的小型网络来说就不适用。
在设计网络时，最简单的解决方法常常是最好的办法。在确定静态路由选择协议不能满足设计要求之后，可以选择动态路由选择协议。