1. 到目前为止，在我们对路由算法的研究中，我们将网络简单地视为互连路由器的集合。一台路由器与另一台路由器没有什么区别，因为所有路由器都执行相同的路由算法来计算通过整个网络的路由路径。实际上，由于两个重要原因，该模型及其对一组执行相同路由算法的同质路由器的看法过于简单：
  • 规模（Scale）。随着路由器数量的增加，通信、计算和存储路由信息所涉及的开销变得令人望而却步。今天的互联网由数以亿计的路由器组成。在每台路由器上存储可能目的地的路由信息显然需要大量内存。在所有路由器之间广播连接和链路开销更新所需的开销将是巨大的！在如此多的路由器之间迭代的距离矢量算法肯定永远不会收敛。显然，必须采取一些措施来降低Internet这样大的网络中路由计算的复杂性。
  • 行政自治（Administrative autonomy）。如1.3节所述，Internet是由ISP组成的网络，每个ISP都由自己的路由器网络组成。ISP通常希望随心所欲地运行其网络(例如，在其网络内运行其选择的任何路由算法)，或者向外界隐藏其网络的内部组织的各个方面。理想情况下，组织应该能够随心所欲地运行和管理其网络，同时仍然能够将其网络连接到其他外部网络。

这两个问题都可以通过将路由器组织成自治系统(autonomous systems，AS)来解决，每个AS由一组处于相同管理控制下的路由器组成。通常，ISP中的路由器和互连它们的链路构成单个AS。然而，一些ISP将其网络划分为多个AS。特别是，一些一级ISP在他们的整个网络中使用一个巨大的AS，而另一些则将他们的ISP拆分成数十个相互连接的AS。自主系统由其全球唯一的自主系统号(autonomous system number，ASN)来标识[RFC 1930]。AS编号与IP地址一样，由ICANN区域注册机构分配[ICANN 2020]。
同一区域内的所有路由器都运行相同的路由算法，并且彼此之间都有相关信息。在自治系统内运行的路由算法称为自治系统内路由协议（intra-autonomous system routing protocol）。

开放最短路径优先(OSPF) Open Shortest Path First (OSPF)

OSPF路由及其密切相关的同类IS-IS被广泛用于Internet中的AS内路由。OSPF中的Open表示路由协议规范是公开可用的(例如，与思科的EIGRP协议相反，该协议在作为思科专有协议大约20年后，最近才开放[Savage 2015])。OSPF的最新版本(版本2)在公共文档[RFC 2328]中定义。
OSPF是一种链路状态协议（link-state protocol），它使用链路状态信息泛洪（flooding of link-state information）和Dijkstra的最小开销路径算法（Dijkstra’s least-cost path algorithm）。使用OSPF，每台路由器构建整个自治系统的完整拓扑图(complete topological map，即图)。然后，每台路由器在本地运行Dijkstra的最短路径算法，以其自身为根节点确定到所有子网的最短路径树。各个链路开销由网络管理员配置(请参阅侧栏原则和实践：设置OSPF权重)。管理员可以选择将所有链路开销设置为1，从而实现最小跳数路由，或者可以选择将链路权重设置为与链路容量成反比，以阻止流量使用低带宽链路。OSPF不强制规定如何设置链路权重的策略(这是网络管理员的工作)，而是提供为给定的链路权重集确定最低开销路径路由的机制(协议)。

PRINCIPLES IN PRACTICE 实践中的原则 SETTING OSPF LINK WEIGHTS 设置OSPF链路权重 我们对链路状态路由的讨论隐含地假设设置了链路权重，运行了OSPF之类的路由算法，并且流量根据LS算法计算出的路由表流动。在因果方面，在最小化总成本的路由路径中给出链路权重(即，它们优先)和结果(通过Dijkstra算法)。在这种观点下，链路权重反映了使用链路的成本(例如，如果链路权重与容量成反比，则使用大容量链路的权重较小，因此从路由的角度看更有吸引力)，Dijsktra的算法用于最小化总体成本。 实际上，链路权重和路由路径之间的因果关系可以颠倒，网络运营商配置链路权重以获得实现某些流量工程目标的路由路径(Fortz 2000，Fortz 2002)。例如，假设网络运营商对在每个入口点进入网络并去往每个出口点的业务流进行估计。然后，运营商可能想要设置入口到出口流量的特定路由，以最小化网络所有链路上的最大利用率。但是对于诸如OSPF之类的路由算法，运营商用于调整流经网络的路由的主要“旋钮”是链路权重。因此，为了实现最小化最大链路利用率的目标，操作员必须找到实现该目标的链路权重集合。这是因果关系的反转-流的所需路由是已知的，并且必须找到OSPF链路权重，以便OSPF路由算法产生所需的流路由。

  1. **使用OSPF，路由器会向自治系统中的所有其他路由器广播路由信息，而不仅仅是向其邻居路由器广播路由信息。每当链路状态发生变化(例如，开销变化或启用/关闭状态变化)时，路由器都会广播链路状态信息。它还会定期广播链路的状态(至少每30分钟广播一次)，即使链路的状态没有更改**。RFC 2328注意到“链路状态通告的这种周期性更新增加了链路状态算法的健壮性。”OSPF通告包含在由IP直接承载的OSPF报文中，OSPF的上层协议为89。因此，OSPF协议本身必须实现可靠报文传输和链路状态广播等功能。OSPF协议还检查链路是否运行正常(通过发送给连接的邻居的Hello消息)，并允许OSPF路由器获取邻居路由器的网络范围链路状态数据库（database of network-wide link state）。<br />OSPF中包含的一些改进包括：
  • 安全（Security）。可以对OSPF路由器之间的交换(例如链路状态更新)进行身份验证。通过身份验证，只有受信任的路由器才能参与AS内的OSPF协议，从而防止恶意入侵者(或网络学生带着新学到的知识出去兜风)将错误信息注入路由器表。默认情况下，路由器之间的OSPF数据包不会经过身份验证，因此可能会被伪造。可以配置两种类型的身份验证-简单身份验证和MD5身份验证(有关MD5和身份验证的一般讨论，请参阅第8章)。使用简单身份验证时，每台路由器上都会配置相同的口令。当路由器发送OSPF数据包时，它会以明文形式包含口令。显然，简单的身份验证不是很安全。MD5身份验证基于所有路由器中配置的共享密钥。对于它发送的每个OSPF数据包，路由器都会计算附加有密钥的OSPF数据包内容的MD5哈希。(请参阅第8章中关于消息验证码的讨论。)。然后，路由器将生成的哈希值包含在OSPF数据包中。接收路由器将使用预配置的密钥计算数据包的MD5哈希值，并将其与数据包携带的哈希值进行比较，从而验证数据包的真实性。序列号还与MD5身份验证一起使用，以防止重播攻击（replay attacks）。
  • 多条相同成本的路径（Multiple same-cost paths）。当到达目的地的多条路径的开销相同时，OSPF允许使用多条路径(即，当存在多条等价路径时，不需要选择一条路径来承载所有流量)。
  • 集成了对单播和组播路由的支持（Integrated support for unicast and multicast routing）。组播OSPF(MOSPF)[RFC 1584]提供了对OSPF的简单扩展，以提供组播路由。MOSPF使用现有的OSPF链路数据库，并向现有的OSPF链路状态广播机制添加一种新类型的链路状态通告。
  • 支持单个AS内的层次结构（Support for hierarchy within a single AS）。OSPF自治系统可以分层配置为区域。每个区域运行自己的OSPF链路状态路由算法，区域中的每台路由器向该区域中的所有其它路由器广播其链路状态。在每个区域内，一个或多个区域边界路由器负责将数据包路由到区域外。最后，AS中正好有一个OSPF区域配置为主干区域。主干区域的主要作用是在AS中的其他区域之间路由流量。主干始终包含AS中的所有区域边界路由器，也可能包含非边界路由器。AS内的区域间路由要求首先将数据包路由到区域边界路由器(区域内路由)，然后通过主干路由到目的地区域中的区域边界路由器，然后路由到最终目的地。

OSPF是一个相对复杂的协议，我们在这里的介绍必须简短；[Huitema 1998；Moy 1998；RFC 2328]提供了更多详细信息。