5.3 互联网中的域内路由:OSPF#
5.3 Intra-AS Routing in the Internet: OSPF
在我们目前对路由算法的研究中,我们将网络简单地视为一组互联的路由器。从某种意义上说,一个路由器与另一个没有区别,因为所有路由器都执行相同的路由算法来计算整个网络中的路由路径。实际上,这种模型和其对所有路由器都执行相同路由算法的同质性看法是过于简单的,主要有两个重要原因:
规模。随着路由器数量的增多,用于通信、计算和存储路由信息的开销变得难以承受。如今的互联网由数亿个路由器组成。在每个路由器上存储所有可能目的地的路由信息显然需要大量内存。广播所有路由器之间的连通性和链路代价更新的开销也将是巨大的!在如此多路由器之间迭代的距离向量算法几乎不可能收敛。显然,必须采取一些措施来降低像互联网这样大规模网络中的路由计算复杂性。
管理自治性。如 第 1.3 节 所述,互联网是一个由 ISP 构成的网络,每个 ISP 由其自身的路由器网络组成。一个 ISP 通常希望按自己的意愿运营其网络(例如,在其网络中运行任意选择的路由算法),或向外部隐藏其网络内部组织的某些方面。理想情况下,一个组织应当能够按照自己的意愿运营和管理其网络,同时仍能将其网络连接到其他外部网络。
这两个问题都可以通过将路由器组织成 自治系统(AS) 来解决,每个 AS 包含一组在相同管理控制下的路由器。通常,ISP 中的路由器和连接它们的链路构成一个单独的 AS。然而,一些 ISP 将其网络划分为多个 AS。特别是,一些一级 ISP 为整个网络使用一个庞大的 AS,而其他 ISP 将其 ISP 网络划分为数十个互联的 AS。自治系统通过其全球唯一的自治系统编号(ASN)进行标识 [RFC 1930]。类似于 IP 地址,AS 编号由 ICANN 区域注册机构分配 [ICANN 2016]。
同一 AS 中的所有路由器都运行相同的路由算法,并拥有彼此的信息。在一个自治系统内运行的路由算法称为 域内(intra-autonomous system)路由协议。
原文
In our study of routing algorithms so far, we’ve viewed the network simply as a collection of interconnected routers. One router was indistinguishable from another in the sense that all routers executed the same routing algorithm to compute routing paths through the entire network. In practice, this model and its view of a homogenous set of routers all executing the same routing algorithm is simplistic for two important reasons:
Scale. As the number of routers becomes large, the overhead involved in communicating, computing, and storing routing information becomes prohibitive. Today’s Internet consists of hundreds of millions of routers. Storing routing information for possible destinations at each of these routers would clearly require enormous amounts of memory. The overhead required to broadcast connectivity and link cost updates among all of the routers would be huge! A distance-vector algorithm that iterated among such a large number of routers would surely never converge. Clearly, something must be done to reduce the complexity of route computation in a network as large as the Internet.
Administrative autonomy. As described in Section 1.3, the Internet is a network of ISPs, with each ISP consisting of its own network of routers. An ISP generally desires to operate its network as it pleases (for example, to run whatever routing algorithm it chooses within its network) or to hide aspects of its network’s internal organization from the outside. Ideally, an organization should be able to operate and administer its network as it wishes, while still being able to connect its network to other outside networks.
Both of these problems can be solved by organizing routers into autonomous systems (ASs), with each AS consisting of a group of routers that are under the same administrative control. Often the routers in an ISP, and the links that interconnect them, constitute a single AS. Some ISPs, however, partition their network into multiple ASs. In particular, some tier-1 ISPs use one gigantic AS for their entire network, whereas others break up their ISP into tens of interconnected ASs. An autonomous system is identified by its globally unique autonomous system number (ASN) [RFC 1930]. AS numbers, like IP addresses, are assigned by ICANN regional registries [ICANN 2016].
Routers within the same AS all run the same routing algorithm and have information about each other. The routing algorithm running within an autonomous system is called an intra-autonomous system routing protocol.
开放最短路径优先(OSPF)#
Open Shortest Path First (OSPF)
OSPF 路由协议及其密切相关的变体 IS-IS 被广泛用于互联网中的域内路由。OSPF 中的 Open 表示该路由协议规范是公开可用的(例如,相对于 Cisco 的 EIGRP 协议,它直到最近才公开 [Savage 2015],在此之前已是 Cisco 的专有协议近二十年)。OSPF 的最新版本为第 2 版,定义于 RFC 2328,该文档是公开发布的。
OSPF 是一种链路状态协议,使用链路状态信息的泛洪机制和 Dijkstra 最小代价路径算法。在 OSPF 中,每个路由器构建整个自治系统的完整拓扑图(即图)。然后,每个路由器在本地运行 Dijkstra 最短路径算法,从自身出发,构建指向所有子网的最短路径树。各链路的代价由网络管理员配置(见边栏 原则与实践:设置 OSPF 权重)。管理员可以选择将所有链路代价设置为 1,以实现最小跳数路由;也可以选择将链路权重设置为链路容量的倒数,以避免流量通过低带宽链路。OSPF 不强制规定链路权重的设置策略(这是网络管理员的职责),而是提供了根据给定链路权重确定最小代价路径的机制(协议)。
原则与实践
设置 OSPF 链路权重
我们对链路状态路由的讨论隐含地假设链路权重已经设置,运行如 OSPF 之类的路由算法,然后流量依据链路状态算法计算出的路由表进行转发。从因果关系的角度来看,链路权重是给定的(即先有链路权重),然后通过 Dijkstra 算法得出最小总代价的路由路径。在这种观点下,链路权重反映使用链路的代价(例如,若链路权重与容量成反比,则使用高容量链路具有更小权重,因此在路由选择上更具吸引力),而 Dijkstra 算法的作用是最小化总代价。
实际上,链路权重与路由路径之间的因果关系可能被颠倒,网络运营商可以通过配置链路权重来获得实现特定流量工程目标的路由路径 [Fortz 2000,Fortz 2002]。例如,假设网络运营商估算了每个入口点进入网络并指向每个出口点的流量流。运营商可能希望实现一种特定的入口到出口的路由方式,以最小化网络所有链路的最大利用率。但在 OSPF 这类路由算法中,运营商调节流量路由的主要“旋钮”就是链路权重。因此,为了实现最小化最大链路利用率的目标,运营商必须找到一组能实现此目标的链路权重。这实际上颠倒了因果关系 —— 期望的流量路由已知,而需要设置 OSPF 的链路权重,使得 OSPF 路由算法得出期望的流量路由。
使用 OSPF 时,一个路由器会将路由信息广播给整个自治系统中的所有其他路由器,而不仅仅是其邻居。每当链路状态发生变化时(例如,代价变化或链路状态从启用变为失效),路由器就会广播链路状态信息。即使链路状态未发生变化,路由器也会周期性地广播链路状态(至少每 30 分钟一次)。RFC 2328 指出:“这种链路状态通告的周期性更新增强了链路状态算法的鲁棒性。” OSPF 通告被封装在由 IP 直接承载的 OSPF 消息中,其上层协议号为 89。因此,OSPF 协议自身必须实现诸如可靠消息传输和链路状态广播等功能。OSPF 协议还会通过发送 HELLO 消息到连接的邻居来检查链路是否可用,并允许 OSPF 路由器获取邻居的网络链路状态数据库。
OSPF 的一些重要特性包括:
安全性。OSPF 路由器之间的交换(例如,链路状态更新)可以进行认证。通过认证,只有可信的路由器才能在 AS 内参与 OSPF 协议,从而防止恶意入侵者(或滥用新知识的网络学生)向路由表注入错误信息。默认情况下,OSPF 路由器之间的包不经过认证,可能会被伪造。可以配置两种认证方式 —— 简单认证和 MD5 认证(详见 第 8 章 中对 MD5 和认证的一般讨论)。简单认证要求在每个路由器上配置相同密码,发送 OSPF 包时以明文形式包含密码。显然,这种方式不够安全。MD5 认证基于在所有路由器中配置的共享密钥。每当路由器发送 OSPF 包时,它会对该包内容加上密钥后计算 MD5 哈希值(参见 第 8 章 中的消息认证码讨论)。然后将结果哈希值包含在 OSPF 包中。接收路由器利用预配置的密钥对收到的数据包进行 MD5 哈希计算,并与数据包中携带的哈希值比较,从而验证数据包的真实性。MD5 认证还使用序列号来防止重放攻击。
支持多条等价路径。当通往某个目的地存在多条等代价路径时,OSPF 允许使用多条路径(即,在存在多条等价路径时,不强制选择单一路径承载所有流量)。
集成对单播和多播路由的支持。多播 OSPF(MOSPF)[RFC 1584] 对 OSPF 进行了简单扩展以支持多播路由。MOSPF 使用现有的 OSPF 链路数据库,并向现有的 OSPF 链路状态广播机制添加了一种新的链路状态通告类型。
支持单一 AS 内的层次结构。OSPF 的自治系统可以被配置为具有层次结构的多个区域(area)。每个区域运行其自己的 OSPF 链路状态路由算法,区域内的每个路由器向该区域内的所有其他路由器广播其链路状态。在每个区域内,一个或多个区域边界路由器负责将数据包转发到区域外部。最后,在 AS 中必须有且只有一个区域被配置为骨干区域(backbone area)。骨干区域的主要职责是负责在 AS 中各区域之间转发流量。骨干区域始终包含 AS 中的所有区域边界路由器,也可能包含一些非边界路由器。AS 内的区域间路由要求数据包首先被路由到一个区域边界路由器(域内路由),然后通过骨干路由到达目的区域的区域边界路由器,最终再转发到目的地。
OSPF 是一个相对复杂的协议,本文对此的介绍不可避免地比较简略;更多细节可参考 [Huitema 1998;Moy 1998;RFC 2328]。
原文
OSPF routing and its closely related cousin, IS-IS, are widely used for intra-AS routing in the Internet. The Open in OSPF indicates that the routing protocol specification is publicly available (for example, as opposed to Cisco’s EIGRP protocol, which was only recently became open [Savage 2015], after roughly 20 years as a Cisco-proprietary protocol). The most recent version of OSPF, version 2, is defined in [RFC 2328], a public document.
OSPF is a link-state protocol that uses flooding of link-state information and a Dijkstra’s least-cost path algorithm. With OSPF, each router constructs a complete topological map (that is, a graph) of the entire autonomous system. Each router then locally runs Dijkstra’s shortest-path algorithm to determine a shortest-path tree to all subnets, with itself as the root node. Individual link costs are configured by the network administrator (see sidebar, Principles and Practice: Setting OSPF Weights). The administrator might choose to set all link costs to 1, thus achieving minimum-hop routing, or might choose to set the link weights to be inversely proportional to link capacity in order to discourage traffic from using low-bandwidth links. OSPF does not mandate a policy for how link weights are set (that is the job of the network administrator), but instead provides the mechanisms (protocol) for determining least-cost path routing for the given set of link weights.
PRINCIPLES IN PRACTICE
SETTING OSPF LINK WEIGHTS
Our discussion of link-state routing has implicitly assumed that link weights are set, a routing algorithm such as OSPF is run, and traffic flows according to the routing tables computed by the LS algorithm. In terms of cause and effect, the link weights are given (i.e., they come first) and result (via Dijkstra’s algorithm) in routing paths that minimize overall cost. In this viewpoint, link weights reflect the cost of using a link (e.g., if link weights are inversely proportional to capacity, then the use of high-capacity links would have smaller weight and thus be more attractive from a routing standpoint) and Dijsktra’s algorithm serves to minimize overall cost.
In practice, the cause and effect relationship between link weights and routing paths may be reversed, with network operators configuring link weights in order to obtain routing paths that achieve certain traffic engineering goals [Fortz 2000, Fortz 2002]. For example, suppose a network operator has an estimate of traffic flow entering the network at each ingress point and destined for each egress point. The operator may then want to put in place a specific routing of ingress-to-egress flows that minimizes the maximum utilization over all of the network’s links. But with a routing algorithm such as OSPF, the operator’s main “knobs” for tuning the routing of flows through the network are the link weights. Thus, in order to achieve the goal of minimizing the maximum link utilization, the operator must find the set of link weights that achieves this goal. This is a reversal of the cause and effect relationship—the desired routing of flows is known, and the OSPF link weights must be found such that the OSPF routing algorithm results in this desired routing of flows.
With OSPF, a router broadcasts routing information to all other routers in the autonomous system, not just to its neighboring routers. A router broadcasts link-state information whenever there is a change in a link’s state (for example, a change in cost or a change in up/down status). It also broadcasts a link’s state periodically (at least once every 30 minutes), even if the link’s state has not changed. RFC 2328 notes that “this periodic updating of link state advertisements adds robustness to the link state algorithm.” OSPF advertisements are contained in OSPF messages that are carried directly by IP, with an upper-layer protocol of 89 for OSPF. Thus, the OSPF protocol must itself implement functionality such as reliable message transfer and link-state broadcast. The OSPF protocol also checks that links are operational (via a HELLO message that is sent to an attached neighbor) and allows an OSPF router to obtain a neighboring router’s database of network-wide link state.
Some of the advances embodied in OSPF include the following:
Security. Exchanges between OSPF routers (for example, link-state updates) can be authenticated. With authentication, only trusted routers can participate in the OSPF protocol within an AS, thus preventing malicious intruders (or networking students taking their newfound knowledge out for a joyride) from injecting incorrect information into router tables. By default, OSPF packets between routers are not authenticated and could be forged. Two types of authentication can be configured—simple and MD5 (see Chapter 8 for a discussion on MD5 and authentication in general). With simple authentication, the same password is configured on each router. When a router sends an OSPF packet, it includes the password in plaintext. Clearly, simple authentication is not very secure. MD5 authentication is based on shared secret keys that are configured in all the routers. For each OSPF packet that it sends, the router computes the MD5 hash of the content of the OSPF packet appended with the secret key. (See the discussion of message authentication codes in Chapter 8.) Then the router includes the resulting hash value in the OSPF packet. The receiving router, using the preconfigured secret key, will compute an MD5 hash of the packet and compare it with the hash value that the packet carries, thus verifying the packet’s authenticity. Sequence numbers are also used with MD5 authentication to protect against replay attacks.
Multiple same-cost paths. When multiple paths to a destination have the same cost, OSPF allows multiple paths to be used (that is, a single path need not be chosen for carrying all traffic when multiple equal-cost paths exist).
Integrated support for unicast and multicast routing. Multicast OSPF (MOSPF) [RFC 1584] provides simple extensions to OSPF to provide for multicast routing. MOSPF uses the existing OSPF link database and adds a new type of link-state advertisement to the existing OSPF link-state broadcast mechanism.
Support for hierarchy within a single AS. An OSPF autonomous system can be configured hierarchically into areas. Each area runs its own OSPF link-state routing algorithm, with each router in an area broadcasting its link state to all other routers in that area. Within each area, one or more area border routers are responsible for routing packets outside the area. Lastly, exactly one OSPF area in the AS is configured to be the backbone area. The primary role of the backbone area is to route traffic between the other areas in the AS. The backbone always contains all area border routers in the AS and may contain non-border routers as well. Inter-area routing within the AS requires that the packet be first routed to an area border router (intra-area routing), then routed through the backbone to the area border router that is in the destination area, and then routed to the final destination.
OSPF is a relatively complex protocol, and our coverage here has been necessarily brief; [Huitema 1998; Moy 1998; RFC 2328] provide additional details.