网站建设吉金手指排名12,个人是否可以申请持有网站,我的网站要怎样做才能让人家搜到,网站使用说明书在本章中#xff0c;包含网络层的控制平面组件。控制平面作为一种网络范围的逻辑#xff0c;不仅控制沿着从源主机到目的主机的端到端路径间的路由器如何转发数据报#xff0c;而且控制网络层组件和服务如何配置和管理。5.2节#xff0c;传统的计算图中最低开销路径的路由选… 在本章中包含网络层的控制平面组件。控制平面作为一种网络范围的逻辑不仅控制沿着从源主机到目的主机的端到端路径间的路由器如何转发数据报而且控制网络层组件和服务如何配置和管理。5.2节传统的计算图中最低开销路径的路由选择算法。5.3和5.4节因特网路由选择协议 OSPF 和 BGP 的基础。OSPF 是一种运行在单一 ISP 的网络中的路由选择算法BGP 是一种在因特网中用于互联所有网络的路由选择算法常被称为因特网的“ 粘合剂 ”。 5.5 节SDN 控制器软件定义网络SDN在数据平面和控制平面之间做了明确分割在一台分离的“ 控制器 ”服务中实现了控制z平面功能该控制器服务于他所控制的路由器的转发组件完全分开并远离。 5.6 和 5.7节涉及管理 IP 网络的某些具体细节ICMP互联网控制报文协议和 SNMP简单网络管理协议。
5.1 概述 通过回顾图 4-2 和图 4-3 迅速建立起学习网络控制平面的环境。在这里转发表在基于目的地转发的场景中和流表在通用转发的场景中是链接网络层的数据平面和控制平面的首要元素。我们知道这些表定义了一台路由器的本地数据平面转发行为。看到在通用转发的场景下所采取的动作4.4.2 节不仅包括转发一个分组到达路由器的每个输出端口而且能够丢弃一个分组 、复制一个分组和/或重写第 2 ,3 或 4 层分组首部字段。 本章中学习这些转发表和流表是如何计算、维护和安装的。在 4.1 节的网络层概述中学习路完成这些工作有两种可能的方法。 ① 每路由器控制 。图 5-1 显示了在每台路由器中运行一种路由选择算法的情况每台路由器中都包含转发和路由选择功能。每台路由器有一个路由选择组件用于与其他路由器中的路由选择组件通信以计算其转发表的值。这种每路由器控制的方法在因特网中已经使用了几十年。将在 5.3 节和 5.4 节中学习的 OSPF 和 BGP 协议都是基于这种每路由器的方法进行控制的。 ② 逻辑集中式控制。图 5-2 显示了逻辑集中式控制器计算并分发转发表以供每台路由器使用的情况。如在 4.4 节中所见通用的 匹配加动作 抽象允许执行传统的 IP 转发以及其他功能负载共享、防火墙功能和 NAT的丰富集合而这些功能先前是在单独的中间盒中实现的。 该控制器经一种定义良好的协议与每台路由器中的一个控制代理CA进行交互以配置和管理该路由器的转发表。CA 一般具有最少的功能其任务是与控制器通信并且按控制器命令行事。与图 5-1 中的路由选择算法不同这些 CA 既不能直接相互交互也不能主动参与计算转发表。这是每路由器控制和逻辑集中式控制之间的关键差异。 逻辑集中式控制意味着就像路由选择控制服务位于单一的集中服务点那样获取它们即使该服务处于容错和性能扩展的原因可能经由多个服务器实现。正如 5.5 节所见SDN 采用了逻辑集中式控制器的概念而这种方法在生产部署中得到越来越多的应用。 5.2 路由选择算法 路由选择算法 (routing algorithm) 其目的是从发送方到接收方的过程中确定一条通过路由器网络的好的路径等价于路由。通常 一条好路径指具有最低开销的路径。然而我们将看到实践中现实世界还关心诸如策略之类的问题例如有一个规则是 属于组织Y 的路由器X 不应转发任何来源于组织 Z 所属网络的分组)。我们注意到无论网络控制平面采用每路由器控制方法还是采用逻辑集中式控制方法必定总是存在一条定义良好的一连串路由器使得分组从发送主机到接收主机跨越网络旅行 。 可以用图来形式化描述路由选择问题。图( graph ) G (N, E) 是一个 N 个节点和 E 条边的集合其中每条边是取自 N的 一对节点。在网络层路由选择的环境中图中的节点表示路由器这是做出分组转发决定的点连接这些节点的边表示这些路由器之间的物理链路。这样一个计算机网络的图抽象显示在图 5-3。 如图 5-3 所示一条边还有一个值表示它的开销。通常一条边的开销可反映出对应链路的物理长度例如一条越洋链路的开销可能比一条短途陆地链路的开销高 它的链路速度或与该链路相关的金钱上的开销。为了我们的目的只将这些链路开销看成是给定的而不必操心这些值是如何确定的。对于 E 中的任一条边xy用 c(xy) 表示节点 x 和 节点 y 间边的开销。如果节点对xy不属于 E则置 c(xy)∞。此外这里考虑的都是无向图图的边没有方向因此边xy与边yx是相同的并且 c(xy) c(yx)。然而学习的算法能够很容易扩展到在每个方向有不同开销的有向链路组合。同时如果xy属于 E节点 y 也被称为节点 x 的邻居。 在图抽象中为各条边指派了开销后路由选择算法的天然目标是找出从源到目的地间的最低开销路径。为了使问题更为精确回想在图 G (N, E) 中的一条路径 (path)是一个节点序列(x1x2…xp) 这样每一个对 (x1 x2 ), (x2x3) ,…, (xp-1,xp是 E中的边。路径x1,x2 …,xp的开销只是沿着路径所有边的开销的总和即c(x1x2) c( x2x3) … C(xp-1,xp。给定任何两个节点 x 和 y 通常在这两个节点之间有许多条路径每条路径都有一个开销。这些路径中的一条或多条是最低开销路径。最低开销路径问题是清楚的找出源和目的地之间具有最低开销的一条路。例如在图5-3中源节点 u 和目的节点 w 之间的最低开销路径是u,x,y,w具有的路径开销是3。注意到若在图中的所有边具有相同的开销则最低开销路径也就是最短路径即在源和目的地之间的具有最少链路数量的路径。 路由选择算法的一种分类方式是根据该算法是集中式还是分散式来划分。 ① 集中式路由选择算法用完整的、全局性的网络知识计算出从源到目的地之间的最低开销路径。也就是说该算法以所有节点之间的连通性及所有链路的开销为输入。这就要求该算法在真正开始计算以前要以某种方式获得这些信息。计算本身可在某个场点例如图 5-2 中所示的逻辑集中式控制器进行或在每台路由器的路由选择组件中重复进行(例如在图 5- 1 中) 然而这里的主要区别在于集中式算法具有关于连通性和链路开销方面的完整信息。具有全局状态信息的算法常被称作链路状态 (Link State , LS) 算法因为该算法必须知道网络中每条链路的开销。我们将在 5.2.1 节中学习 LS 算法。 ② 在分散式路由选择算法 (deeentralized routing algorithm) 中路由器以迭代、分布式的方式计算出最低开销路径。没有节点拥有关于所有网络链路开销的完整信息。相反每个节点仅有与其直接相连链路的开销知识即可开始工作。然后通过迭代计算过程以及与相邻节点的信息交换一个节点逐渐计算出到达某目的节点或一组目的节点的最低开销路径。我们将在后面的 5.2.2 节学习一个称为距离向量( Distance-Vector, DV) 算法的分散式路由选择算法。之所以叫作 DV 算法是因为每个节点维护到网络中所有其他节点的开销(距离)估计的向量。 这种分散式算法通过相邻路由器之间的交互式报文交换也许更为天然地适合那些路由器直接交互的控制平面就像在图 5-1 中那样。 路由选择算法的第二种广义分类方式是根据算法是静态的还是动态的进行分类。在静态路由选择算法static routing algorithm) 中路由随时间的变化非常缓慢通常是人工进行调整如人为手工编辑一条链路开销。动态路由选择算法 (dynamic routi algorithm)随着网络流量负载或拓扑发生变化而改变路由选择路径。一个动态算法可周期性地运行或直接响应拓扑或链路开销的变化而运行。虽然动态算法易于对网络的变化做出反应但也更容易受诸如路由选择循环、路由振荡之类问题的影响。 路由选择算法的第三种分类方式是根据它是负载敏感的还是负载迟钝的进行划分。在负载敏感算法load -sensitive algorithm) 中链路开销会动态地变化以反映出底层链路的当前拥塞水平。如果当前拥塞的一条链路与高开销相联系则路由选择算法趋向于绕开该拥塞链路来选择路由。当今的因特网路由选择算法(如 RIPOSPF BGP) 都是负载迟钝的( 10ad -insensitive) 因为某条链路的开销不明确地反映其当前(或最近)的拥塞水平。
5.2.1 链路状态路由选择算法 前面讲过 在链路状态算法中网络拓扑和所有的链路开销都是已知的也就是说可用作 LS 算法的输入。实践中这是通过让每个节点向网络中所有其他节点广播链路状态分组来完成的其中每个链路状态分组包含它所连接的链路的标识和开销。在实践中例如使用因特网的 OSPF 路由选择协议讨论见 5.3 节) 这经常由链路状态广播link state broadcast算法来完成。节点广播的结果是所有节点都具有该网络的统一、完整的视图。于是每个节点都能够像其他节点一样运行 LS 算法并计算出相同的最低开销路径集合。 下面给出的链路状态路由选择算法叫做 Dijkstra 算法。一个密切相关的算法是 prim 算法。Dijkstra 算法计算从某节点源节点 称之为 u到网络中所有其他节点的最低开销路径。Dijkstra 是迭代算法其性质是经算法的第 k 次迭代后可知道到 k 个目的节点的最低开销路径在到所有目的节点的最低开销路径中着 k 条路径具有 k 个最低开销。定义下列符号。 举一个例子考虑图 5-3 中的网络计算从 u 到所有可能目的地的最低开销路径算法的计算过程以表格方式总结于表5-1 中表中的每一行给出了迭代结束时该算法的变量的值。详细地考虑前几个步骤。 ① 在初始化步骤从 u 到与其直接相连的邻居v 、x、w 的当前已知最低开销路径分别初始化为 2,1,5。特别值得注意的是到 w 的开销被设为 5尽管我们很快就会看见确实存在一条开销更小的路径因为这是从 u 到 w 的直接一跳链路开销。到 y 与 z的开销被设为无穷大因为它们不直接与 u 连接。 ② 在第一次迭代中观察那些还未加到集合 N 中的节点并且找出在前一次迭代结束时具有最低开销的节点。那个节点便是 x 其开销是 1因此 x 被加到集合 N。于是 LS 算法中的第 12 行中的程序被执行以更新所有节点 v 的 D(v)产生表 5-1 中第 2 行( 步骤 )所示的结果。到 v 的路径开销未变。经过节点 x 到 w在初始化结束时其开销为 5的路径开销被发现为 4。因此这条具有更低开销的路径被选中且沿从 u 开始的最短路径上 w 的前一节点被设为 x。类似地到 y (经过 x的开销被计算为 2且该表也被相应地更新。 ③ 在第二次迭代时节点 v 与 y 被发现具有最低开销路径 (2) 并且我们任意改变次序将 y 加到集合 N 中使得 N 中含有 u,x 和 y。到仍不在 N 中的其余节点即节点 v w 和 z的开销通过 LS 算法中的第 12 行进行更新产生如表 5-1 中第 3 行所示的结果。 ④ 如此等等。 当 LS 算法终止时对于每个节点我们都得到从源节点沿着它的最低开销路径的前一节点。对于每个前一节点我们又有它的前一节点以此方式我们可以构建从源节点到所有目的节点的完整路径。通过对每个目的节点存放从 u 到目的地的最低开销路径上的下一跳节点在一个节点如节点 u中的转发表能够根据此信息而构建。图 5-4 显示了对于图 5-3 中的网络产生的最低开销路径和 u 中的转发表。 该算法的计算复杂性是什么即给定 n 个节点不算源节点在最坏情况下要经过多少次计算才能找到从源节点到所有目的节点的最低开销路径在第一次迭代中我们需要搜索所有的 n 个节点以确定出不在 N 中且具有最低开销的节点 w。 在第二次迭代时我们需要检查 n-1 个节点以确定最低开销。第三次对 n-2 个节点迭代依次类推。总之我们在所有迭代中需要搜寻的节点总数为 n(n1 )/2 因此我们说前面实现的链路状态算法在最差情况下复杂性 O(n^2)。(该算法的一种更复杂的实现是使用一种称为堆的数据结构能用对数时间而不是线性时间得到第 9 行的最小值因而减少其复杂性。 在完成 LS 算法的讨论之前考虑一下可能出现的问题。图 5-5 显示了一个简单的网络拓扑图中的链路开销等于链路上承载的负载例如反映要历经的时延。在该例中链路开销是非对称的即仅当在链路 (uv) 两个方向所承载的负载相同时 c(uv) 和 c(vu) 才相等。在该例中节点 z 产生发往 w 的一个单元的流量节点 x 也产生发往w 的一个单元的流量并且节点 y 也产生发往 w 的一个数量为 e 的流量。初始路由选择情况如图 5-5a 所示其链路开销对应于承载的流量。 当 LS 算法再次运行时节点 y 确定基于图 5-5a 所示的链路开销顺时针到 w 的路径开销为 1而逆时针到 w 的路径开销一直使用的是 1e。因此y 到 w 的最低开销路径现在是顺时针的。类似的x 确定其到 w 的新的最低开销路径也是顺时针的产生如图 5-5b 中所示的开销。当 LS 算法下次运行时节点 x、y 和 z 都检测到一条至 w 的逆时针方向零开销路径他们都将其流量引导到逆时针方向的路由上。下次 LS 算法运行时x、y和 z 都将其流量引导到顺时针方向的路由上。 如何才能防止这样的振荡它不只是出现在链路状态算法中而且也可能出现在任何使用拥塞或基于时延的链路测度的算法中。一种解决方案可能强制链路开销不依赖于所承载的流量但那是一种不可接受的解决方案因为路由选择的目标之一就是要避开高度拥塞如高时延的链路。另一种解决方案就是确保并非所有的路由器都同时运行 LS 算法。这似乎是一个更合理的方案因为我们希望即使路由器以相同周期运行 LS 算法在每个节点上算法执行的时机也将是不同的。有趣的是研究人员近来已注意到了因特网上的路由器能在它们之间进行自同步。 这就是说即使它们初始时以同一周期但在不同时刻执行算法算法执行时机最终会在路由器上变为同步并保持之 。避免这种自同步的一种方法是让每台路由器发送链路通告的时间随机化。
5.2.2 距离向量路由选择算法 距离向量Distance-Vector DV算法是一种迭代的、异步的和分布式的算法而 LS 算法是一种使用全局信息的算法。说它是分布式的是因为每个节点都要从一个或者多个直接相连邻居接收某些信息执行计算然后将其计算结果分发给邻居。说他是迭代的是因为此过程一直要持续到邻居之间无更多信息要交换为止。(有趣的是此算法是自我终止的即没有计算应该停止的信号它就停止了。说它是异步的是因为它不要求所有节点相互之间步伐一致地操作。我们将看到一个异步的、迭代的、自我终止的、分布式的算法。 给出 DV 算法之前讨论存在于最低开销路径的开销之间的一种重要关系。令 dx(y)是从节点 x 到 y 的最低开销路径的开销。则该最低开销于 Bellman-Ford 方程相关即 检查在图5-3 中的源节点 u 和目的节点 z。源节点有 3 个邻居v、x 和 w。通过遍历该图中的各条路径容易看出 dv(z)5 dx(z)3 dw(z)3。连通开销 c(uv)2、c(ux)1 c(uw)5 带入方程。得出 du(z)min{255313}4。显然是正确的。 在该 DV 算法中当节点 x 发现它的直接相连的链路开销变化或从某个邻居接收到一个距离向量的更新时它就更新其距离向量估计值。但是为了一个给定的目的地 y 而更新它的转发表节点 x 真正需要知道的不是到 y 的最短路径距离而是沿着最短路径到下一跳路由器邻居节点 v*(y) 。如你可能期望的那样下一跳路由器 v*(y) 是在 DV 算法第14 行中取得最小值的邻居 v 。(如果有多个取得最小值的邻居 v*(y) 能够是其中任何一个有最小值的邻居。)因此对于每个目的地 y在第 13 -14 行中节点 x 也决定v*(y) 并更新它对目的地 y 的转发表。 前面讲过 LS 算法是一种全局算法在于它要求每个节点在运行 Dìjkstra 算法之前首先获得该网络的完整信息。DV 算法是分布式的它不使用这样的全局信息。实际上节点具有的唯一信息是它到直接相连邻居的链路开销和它从这些邻居接收到的信息。每个节点等待来自任何邻居的更新(第 10 -11 行) 当接收到一个更新时计算它的新距离向量(第 14 行)并向它的邻居分布其新距离向量(第 16 -17 行)。在实践中许多类似 DV 的算法被用于多种路由选择协议中包括因特网的 RIP 和 BGP、ISO IDRP等。 图 5-6 举例说明了 DV 算法的运行应用场合是该图顶部有三个节点的简单网络。算法的运行以同步的方式显示出来其中所有节点同时从其邻居接收报文计算其新距离向量如果距离向量发生了变化则通知其邻居。学习完这个例子后你应当确信该算法以异步方式也能正确运行异步方式中可在任意时刻出现节点计算与更新的产生/接收。 该图最左边一列显示了这 3 个节点各自的初始路由选择表( routlng table)。例如位于左上角的表是节点 x 的初始路由选择表。在一张特定的路由选择表中每行是一个距离向量一一特别是每个节点的路由选择表包括了它的距离向量和它的每个邻居的距离向量。因此在节点 x 的初始路由选择表中的第一行 Dx[Dx(x)Dx(y)Dx(z)][0,2,7]。在该表的第二和第三行是分别从节点 y 和 z 收到的距离向量。因为在初始化时节点 x 还没有从节点 y 和z 收到任何东西所以第二行和第三行的表项被初始化为无穷大。 初始化后每个节点向它的两个邻居发送其距离向量。图 5-6 中用从表的第一列到表的第二列的箭头说明了情况。例如节点 x 向两个节点 y 和 z 发送了它的距离向量 Dx[027]。在接收到更新后每个节点重新计算它自己的距离向量。例如节点 x 计算 第二列因此为每个节点显示了节点的新距离向量连同刚从它的邻居接收到的距离向量。注意到例如节点 x 到节点 z 的最低开销估计 Dx(z) 已经从 7 变成 3 了。还应注意到对于节点 x节点 y 在该 DV 算法的第 14 行中取得了最小值因此在该算法的这个阶段在节点 x 得到了 v*(y)y 和 v*(z)y。 在节点重新计算它们的距离向量之后它们再次向其邻居发送它们的更新距离向量如果它们已经改变的话。图 5-6 中由从表第二列到表第三列的箭头说明了这一情况。注意到仅有节点 x 和节点 z 发送了更新节点 y 的距离向量没有发生变化因此节点 y 没有发送更新。在接收到这些更新后这些节点则重新计算它们的距离向量并更新它们的路由选择表这些显示在第三列中。 从邻居接收更新距离向量、重新计算路由选择表项和通知邻居到目的地的最低开销路径的开销已经变化的过程继续下去直到无更新报文发送为止。在这个时候因为无更新报文发送将不会出现进一步的路由选择表计算该算法将进入静止状态即所有的节点将执行 DV 算法的第 10 -11 行中的等待。该算法停留在静止状态直到一条链路开销发生改变如下面所讨论的那样。
1. 距离向量算法链路开销改变与链路故障 当一个运行 DV 算法的节点检测到从它自己到邻居的链路开销发生变化时(第 10 --11 行) 它就更新其距离向量第13-14 行) 并且如果最低开销路径的开销发生了变化向邻居通知其新的距离向量第16-17行。图 5-7a 图示了从 y 到 x 的链路开销从 4 变为 1 的情况。我们在此只关注 y 与 z 到目的地 x 的距离表中的有关表项。该 DV 算法导致下列事件序列的出现 ① 在 t0 时刻y 检测到链路开销变化(开销从 4 变为 1) 更新其距离向量并通知其邻居这个变化因为最低开销路径的开销已改变。 ② 在 t1 时刻收到来自 y 的更新报文并更新了其距离表。它计算出到 x 的新最低开销从开销 5 减为开销 2它向其邻居发送了它的新距离向量。 ③ 在 t2时刻y 收到来自 z 的更新并更新其距离表。y 的最低开销未变因此 y 不发送任何报文给 z。该算法进入静止状态。 因此对于该 DV 算法只需要两次迭代就到达了静止状态。在 x 与 y 之间开销减少的好消息通过网络得到了迅速传播。 现在考虑一下某链路开销增加的情况。假设 x 与 y 之间的链路开销从 4 增加到 60如图 5-7b 该过程将要继续多久呢你应认识到该循环将持续 44 次迭代(在 y 与 z 之间交换报文) 即直到 z 最终算出它经由 y 的路径开销大于 50 为止。此时 z 将(最终)确定它到的最低开销路径是经过它到 x 的直接连接。y 将经由 z 路由选择到 x 。关于链路开销增加的坏消息的确传播得很慢如果链路开销 c(y,x) 从 4 变为 10000 且开销 c(z x) 为 9999时将发生什么样的现象呢由于这种情况我们所见的问题有时被称为无穷计数( count-to-infinity)问题。
2. 距离向量算法增加毒性逆转 刚才描述的特定循环的场景可以通过使用一种称为毒性逆转 (poisoned reverse) 的技术而加以避免。其思想较为简单如果 z 通过 y 路由选择到目的地 x则 z 将通告 y它(即 z) 到 x 的距离是无穷大也就是 z 将向 y 通告 Dz(x)∞即使 z 实际上知道Dz (x) 5。只要 z 经 y 路由选择到 xz 就持续地向 y 讲述这个善意的小谎言。因为 y 相信 z 没有到 x 的路径故只要 z 继续经 y 路由选择到 x并这样去撒谎y 将永远不会试图经由 z 路由选择到 x。 现在看一下毒性逆转如何解决我们前面在图 5-7b 中遇到的特定环路问题。作为毒性逆转的结果y 的距离表指示了 Dz(x)∞。当(xy) 链路的开销在 t0 时刻从 4 变为60 更新其表虽然开销高达 60 仍继续直接路由选择到 x并将到 x 的新开销通知z即 Dy(x) 60。z在 t1 时刻收到更新后便立即将其到 x 的路由切换到经过开销为 50的直接 (z x) 链路 肉为这是一条新的到坏的最低开销路径且因为路径不再经过 yz 就在 t2 时刻通知 y 现在 Dz(x) 50。在收到来自 z 的更新后y 便用 Dy(x) 51 更新其距离表.另外因为 z 此时位于 y到 x 的最低开销路径上所以 y 通过在 t3 时刻通知 z 其 Dy(x)∞(即使 y 实际上知道 Dy(x) 51毒化从 z 到 x 坏的逆向路径。 毒性逆转解决了一般的无穷计数问题吗没有。你应认识到涉及 3 个或更多节点而不只是两个直接相连的邻居节点的环路将无法用毒性逆转技术检测到。
3. LS 与 DV 路由选择算法的比较 DV 和 LS 算法采用互补的方法来解决路由选择计算问题。在 DV 算法中每个节点仅与它的直接相连的邻居交谈但它为其邻居提供了从它自己到网络中它所知道的所有其他节点的最低开销估计。LS 算法需要全局信息。因此当在每台路由器中实现时例如像在图 4-2 和图 5-1 中那样每个节点经广播与所有其他节点通信但仅告诉它们与它直接相连链路的开销。通过快速比较它们各自的属性来总结所学的链路状态与距离向量算法。记住 N 是节点(路由器)的集合而 E 是边(链路)的集合。 ① 报文复杂性。LS 算法要求每个节点都知道网络中每条链路的开销。这就要求要发送 O|N||E|个报文。而且无论何时一条链路的开销改变时必须向所有节点发送新的链路开销。DV 算法要求在每次迭代时在两个直接相连邻居之间交换报文。我们已经看到算法收敛所需时间依赖于许多因素。当链路开销改变时 DV 算法仅当在新的链路开销导致与该链路相连节点的最低开销路径发生改变时才传播已改变的链路开销。 ② 收敛速度。LS 算法的实现是一个要求 O(|N||E|)个报文的 O(|N|^2)算法。DV 算法收敛较慢且在收敛时会遇到路由选择环路。DV 算法还会遭遇无穷计数问题。 ③ 健壮性。如果一台路由器发生故障、行为错乱或收到蓄意破坏时情况会怎样呢对于 LS 算法路由器能够向其连接的链路而不是其他链路广播不正确的开销。作为 LS 广播的一部分一个节点也可损坏或丢弃它收到的任何 LS 广播分组。但是一个 LS 节点仅计算自己的转发表其他节点也自行执行类似的计算。这就意味着LS 算法下路由计算在某种程度上是分离的提供了一定程度的健壮性。DV算法下一个节点可向任意或所有目的节点通告其不正确的最低开销路径。在1997 年 一个小 ISP 的一台有故障的路由器的确向美国的主干路由器提供了错误的路由选择信息。这引起了其他路由器将大量流量引向该故障路由器并导致因特网的大部分中断连接达数小时一般地我们会注意到每次迭代时在 DV 算法中一个节点的计算会传递给它的邻居然后在下次迭代时再间接地传递给邻居的邻居。在此情况下 DV 算法中一个不正确的节点计算值会扩散到整个网络。 总之两个算法没有一个是明显的赢家它们的确都在因特网中得到了应用。
5.3 因特网中自治系统内部的路由选择OSPF 在目前为止的算法研究中将网络只看作一个互联路由器的集合。从所有路由器执行相同的路由选择算法以计算穿越整个网络的路由选择路径的意义上说一台路由器很难同另一台路由器区别开来。 在实践中该模型和这种一组执行同样路径选择算法的同质路由器集合的观点有一点简单化。以下两个重要原因 ① 规模。随着路由器数目变得很大涉及路由选择信息的通信、计算和存储的开销将高得不可实现。当今的因特网由数亿台主机组成。在这些主机中存储的路由选择信息显然需要巨大容量的内存。在所有路由器之间广播连通性和链路开销更新所要求的负担将是巨大的在如此大量的路由器中迭代的距离向量算法将肯定永远无法收敛显然必须采取一些措施以减少像因特网这种大型网络中的路由计算的复杂性。 ② 管理自治。如在1.3 节描述的那样因特网是 ISP 的网络其中每个 ISP 都有它自己的路由器网络。 ISP 通常希望按自己的意愿运行路由器如在自己的网络中运行它所选择的某种路由选择算法或对外部隐藏其网络的内部组织面貌。在理想情况下一个组织应当能够按自己的愿望运行和管理其网络还要能将其网络与其他外部网络连接起来。 这两个问题都可以通过将路由器组织进自治系统 (Autonomous System, AS) 来解决其中每个 AS 由一组通常处在相同管理控制下的路由器组成通常在一个 ISP 中的路由器以及互联它们的链路构成一个 AS。然而某些 ISP 将它们的网络划分为多个 AS 。特别是某些一级 ISP 在其整个网络中使用一个庞大的 AS而其他 ISP 则将它们的 ISP 拆分为数十个互联的 AS。一个自治系统由其全局唯一 AS号 (ASN) 所标识。就像 IP地址那样 AS 号由 ICANN 区域注册机构所分配 在相同 AS 中的路由器都运行相同的路由选择算法并且有彼此的信息。在一个自治系统内运行的路由选择算法叫做自治系统内部路由选择协议。
开放最短路优先OSPF OSPF 路由选择及其关系密切的协议 IS-IS 都被广泛用于因特网的 AS 内部路由选择。 OSPF 是一种链路状态协议它使用洪泛链路状态信息和 Dijkstra 最低开销路径算法。使用 OSPF一台路由器构建了一幅关于整个自治系统的完整拓扑图(即一幅图)。于是每台路由器在本地运行 Dijkstra 的最短路径算法以确定一个以自身为根节点到所有子网的最短路径树。各条链路开销是由网络管理员配置的(参见实践原则设置 OSPF 链路权值。管理员也许会选择将所有链路开销设为 1因而实现了最少跳数路由选择或者可能会选择将链路权值按与链路容量成反比来设置从而不鼓励流量使用低带宽链路。OSPF 不强制使用设置链路权值的策略而是提供了一种机制(协议) 为给定链路权值集合确定最低开销路径的路由选择 。 使用 OSPF 时路由器向自治系统内所有其他路由器广播路由选择信息而不仅仅是向其相邻路由器广播。每当一条链路的状态发生变化时如开销的变化或连接/中断状态的变化) 路由器就会广播链路状态信息。即使链路状态未发生变化它也要周期性地(至少每隔 30 min 一次)广播链路状态。RFC 2328 中有这样的说明:链路状态通告的这种周期性更新增加了链路状态算法的健壮性。OSPF 通告包含在 OSPF 报文中该 OSPF报文直接由 IP 承载对 OSPF 其上层协议的值为 89。因此 OSPF 协议必须自己实现诸如可靠报文传输、链路状态广播等功能。OSPF 协议还要检查链路正在运行(通过向相连的邻居发送 HELLO 报文) 并允许 OSPF 路由器获得相邻路由器的网络范围链路状态的数据库。
