2.3 链路状态多播路由
我们知道，在单播使用的链路状态路由选择中，每个路由器监视跟它直接相连的链路的状态，当状态改变时，就给所有其他的路由器发送一个更新报文。由于每个路由器都收到了可以重构整个网络拓扑的足够信息，因此它们都能够使用Dijkstra算法计算以自己为根到达所有可能的目标的最短通路分发树。路由器使用这个树确定它转发的每个分组的下一跳段。
为了支持多播，我们对上述算法所做的扩展就是把在一个特别的链路（LAN）上具有成员的若干个组加到该链路的状态上。唯一的问题是每个路由器如何确定哪个组在哪个链路上有成员。答案是让每个主机定期地向LAN通告它所属于的组。路由器只需监视LAN以得到这样的通告。如果这样的通告停止到达了，那么在一段时间之后路由器就认为该主机已经脱离了这个组。
如果具备了哪个组在哪个链路上有成员的完全信息，那么每个路由器都能够使用Dijkstra算法计算任一源到任一组的最短通路多播树。不过，由于每个路由器必须潜在地为从每个路由器到每个组都保持一个单独的最短通路多播树，这显然是很昂贵的举措；因此取而代之的是，路由器只是计算和存储这些树的一个高速缓存，只为当前处于活动状态的每个（源，组）对缓存一个最小通路多播树。
在本书的这一节里，我们先讨论基本的链路状态多播路由算法，然后重点介绍使用该算法的MOSPF（Multicast Extensions to OSPF，对OSPF的多播扩展）协议。
2.3.1 链路状态多播路由算法
在链路状态路由算法中，每个路由器监视它的每个附接链路的状态（例如活动/关闭状态，流量负载）。每当一条链路的状态改变时，附接到那条链路的路由器都把这个新状态广播到在互联网络中的每个其他路由器。广播使用一种特定的高优先级的洪泛协议执行，以保证每个路由器都能很快地获悉新状态。因此每个路由器都接收关于所有链路和所有路由器的信息，由此它们每个都可以确定互联网络的完全拓扑。知道了完全拓扑，每个路由器使用Dijkstra算法独立地计算以它自己为根的最短通路树。使用这个树，路由器可以确定用于转发分组的从它自身到任何目的地的最短通路。
把链路状态路由算法扩展成支持最短通路多播路由的做法是直接的，这只需简单地让路由器包括在一条链路上有成员的组的列表作为链路状态的一部分。在一条链路上，每当一个新的组出现或一个老的组消失时，附接到那条链路的路由器就把新的状态洪泛到所有的其他路由器。获得了在哪条链路上哪个组有成员的完全信息，任何路由器都能够使用Dijkstra算法计算从任何源到任何组的最短通路多播树。如果做计算的路由器位于所计算的树内，那么它就能够确定它必须使用哪些链路转发从给定的源发往给定的组的多播分组的拷贝。
为了使得路由器能够监视在链路上的组成员关系，需要主机定期地发布成员关系报告。每个成员报告都作为一个本地多播发送给被报告的组，因而在同一链路上的同一组的任何其他成员都能够听到报告，并抑制它们自己的报告。当监视链路的路由器注意到关于一个组的成员报告停止到达时，就知道那个组已经退出了。这个技术在每条链路上对于存在的每个组在每个报告周期内产生一个分组。
比较可取的做法是只让附接到一条链路的一个路由器监视该链路的成员关系，从而减少可能洪泛关于该链路的成员信息的路由器的数目。在链路状态路由体系中，这个工作可以由LAN的指定路由器承担，它已经在执行监视链路上存在哪些主机的任务。
潜在地，从每个发送方都可能有一个到达每个组的最短通路多播树，因此让每个路由器都计算和存储所有可能的多播树，在空间和处理时间方面是非常昂贵的。可取的做法是只在需要时才建立多播树。每个路由器都保持一个下列形式的多播路由记录的缓区：
（源，子树，（组，链路-存活时间TTLs），（组，链路-存活时间TTLs），…）
源是一个多播源的地址。子树是这个路由器在以源为根的最短通路生成树中所有晚辈链路的列表。组是一个多播组地址。链路存活时间是一个存活时间（time-to-live，TTL）的向量，每条附接链路各有一个值，指定通过那条链路可以到达该组最近的晚辈成员所需要的最小存活时间；以无穷大表示的一个特别的TTL值标识从其不会到达任何晚辈成员的那些链路。
当一个路由器接收到一个多播分组时，它在自己的多播路由缓冲区中查找分组的源。如果它找到一个记录，就在（组，链路存活时间TTLs）段中查找目的组，如果找到了这个组，就在其链路存活时间小于或等于分组头中的TTL的所有链路上转发该分组。
如果找到源的记录，但在记录中找不到目的组，那么路由器必须计算输出链路和对应的TTLs。为此，它扫描在子树中的链路，查找有目的组成员的那些链路，并计算到达所找到的任何成员链路所需要的最小TTLs。新的组和链路存活时间TTLs被加进记录，并被用以做转发决定。
最后，如果找不到对应一个输入多播分组的源记录，那么必须计算关于那个源的完全的最短通路树。从这个树可以标识路由器的晚辈子树。然后把该源和子树作为一个新的记录安装在多播路由缓区中。对于目的地组的链路存活时间TTLs也作为计算完全树工作的一部分进行计算，并加到该记录，用以做转发决定。跟处理能力相比，存储器更为缺乏的路由器可能选择不在多播路由缓区中存储子树，当遇到一个特别的源的新树时，就再次计算完全树。
缓区记录不必采用超时机制。当缓区满时，可以根据最近最少使用的原则丢弃老的记录。每当拓扑改变时，都要丢弃所有的缓区记录。每当一个老的组在一条链路上消失时，标识那个组的所有（组，链路存活时间TTLs）域都从缓区中删除。
跟RPM算法一样，链路状态路由算法的代价非常依赖互联网络多播流量模式。假定在单个LAN存在的组的数目少于主机数，那么组链路状态分组所需要的带宽应该不会大于在IS-IS（Intermediate-System to Intermediate-System，中间系统到中间系统）路由协议中端点系统链路状态分组所需要的带宽。在路由器中存储链路成员关系信息所需要的存储器也是类似的情况。算法的主要代价在于存储多播路由缓区记录和计算多播树的处理需求。假定大多数多播分组需要跨越在互联网络中较小比例的路由器，那么这个算法需要的存储空间小于RPM算法，因为仅在那些必须经过的路由器中消耗存储。
该算法的一个可能的缺点是从一个给定的源发送第一个多播分组所引起的附加延迟，在每一跳段，路由器在它们可以转发分组之前必须计算完全的树。树计算的复杂度是在互联网络中链路数的数量级，将一个大的互联网络分解成多个路由子域是控制在任何域内链路数目的一个有效的方法。
2.3.2 MOSPF协议
OSPF是一个内部网关协议，在属于单个OSPF自治系统的路由器之间分发单播拓扑信息。它基于链路状态算法，允许使用最少的路由协议流量执行快速路由计算。除了有效的路由计算，OSPF还是一个开放的标准，支持等级式路由、负载平衡和外部路由信息的输入。
MOSPF（Multicast Extensions to Open Shortest Path First，开放最短通路优先的多播扩展）路由器通过OSPF链路状态路由协议维持网络当前的拓扑结构图。它建立在OSPF的顶部，因此可以递增地把多播路由功能引进OSPF路由域。在转发单播IP数据流量时，运行MOSPF的路由器跟非MOSPF路由器可以互操作。MOSPF不支持隧道。
1．MOSPF区内路由
区内路由描述MOSPF采用的基本的路由算法。这个基本算法在单个OSPF区内运行，当源和所有的目的地组成员都驻留在同一个OSPF区内或者整个OSPF自治系统是单个区时，支持多播转发。
类似于所有其他的多播路由协议，MOSPF路由器使用IGMP监视在直接附接的子网上的多播组成员。MOSPF路由器维护一个“本地组数据库”，列出直接附接的组，确定本地路由器投递多播数据报到这些组的责任。
在任何给定的子网上都是只有指定路由器（Designated Router，DR）发送IGMP主机成员查询。然而，监听IGMP主机成员报告的责任不仅由指定路由器承担，而且也让备份指定路由器（Backup Designated Router，BDR）承担。因此，在包含MOSPF路由器和OSPF路由器的混合LAN中，必须把一个MOSPF路由器选为指定路由器。这个可以通过在每个非MOSPF路由器中把OSPF路由器优先级（Router Priority）设置成0阻止它们成为DR或BDR来实现。
DR通过洪泛组成员关系LSA（Link-State Advertisement，链路状态通告）把组成员关系信息传达给在OSPF区中的所有其他的路由器。类似于路由器-LSA（描述收集的该路由器接口的状态）和网络-LSA（为每个网络产生一个这种LSA，描述当前连接到该网络的一组路由器），组成员关系LSA仅在单个区内洪泛。
数据报的最短通路树描述多播数据报在区内从源子网传输到每个组成员子网所遵循的通路。路由器在接收一个（源，组）对的第一个多播数据报时，它按需建立该（源，组）对的最短通路树。
当初始数据报到达时，源子网被放进MOSPF的源子网。MOSPF链路状态数据库就是标准的OSPF链路状态数据库附加组成员关系LSA。基于在OSPF链路状态数据库中的路由器-LSA和网络-LSA，使用Dijkstra算法构建基于源的最短通路树。在建立了树之后，使用组成员关系LSA剪枝树，让它仅保留指向含有这个组的成员的子网的枝。这些算法的输出是以数据报的源为根的经过剪枝的基于源的树（参见图2-5）。
图2-5 对于（S，G）对的最短通路树
为了把多播数据报转发到一个组的下游成员，每个路由器必须确定它在数据报的最短通路树中的位置。图2-5给出了一个给定的（源，组）对的最短通路树。路由器E的上游结点是路由器B，并且有两个下游接口：一个连接到子网6，另一个连接到子网7。
基本的MOSPF路由算法具有下列性质。
①对于一个给定的多播数据报，在一个区内的所有路由器都计算同样的基于源的最短通路投递树。在存在多条相同代价的通路的情况下，定义一种选择方法，让所有的路由器都就通过该区的单个通路问题达成一致。与单播OSPF不同，MOSPF不支持同时使用多个相同代价的路径的多通路路由的概念。
②同步链路状态数据库包含组成员关系LSA，它允许MOSPF路由器在存储器中建立一个基于源的最短通路树，支持从源到组成员的转发。与DVMRP不同，新传输的第一个数据报不必洪泛到在区中的所有路由器。
③基于源的投递树的按需建立具有散布计算时间的优点。当然，如果有许多个新的（源，组）对在差不多同样的时间出现，或者有大量的事件迫使MOSP进程负荷激增，重建它的转发缓区，可能过度使用CPU。在承载寿命长的多播会话的稳定拓扑中，这些效应应该是最小的。
每个MOSPF路由器基于它的转发缓区的内容做转发决定。与DVMRP不同，MOSPF的转发不是基于反向通路洪泛（RPF）。转发缓区从对于每个（源，组）对的基于源的最短通路树和该路由器的本地组数据库建立。路由器发现它在该最短通路树中的位置之后，建立一个转发缓区登记项，该登记项包含（源，组）对、期待的上游输入接口和需要的下游输出接口。此时，Dijkstra最短通路树被丢弃，释放了跟该树的建立相关联的所有资源。然后它就使用该转发缓区登记项快速地转发所有随后来自这个源发给这个组的数据报。如果一个新的源开始给一个新的组发送，那么MOSPF必须先计算分发树，以便它可以建立能够被用来转发该分组的缓区登记项。
图2-6给出了一个范例MOSPF路由器的转发缓区。显示的成分包括下列条目。
图2-6 MOSPF转发缓区
（1）目的地
转发的匹配数据报的目的组地址。
（2）源
数据报的源主机地址。每个（目的地，源）对都唯一地标识一个单独的转发缓区登记项。
（3）上游
匹配这一行的目的地和源的数据报必须在这个接口上接收。
（4）下游
如果匹配这行的目的地和源的数据报在正确的上游接口上收到，那么把它通过列出的下游接口转发。
（5）TTL
为了到达目的地组的成员，数据报必须通过最小跳段数。如果MOSPF路由器看到该数据报甚至没有到达最近的组成员所需要的足够的TTL，那么它可以丢弃该数据报。
在转发缓区中的信息不会超时作废，也不用定期刷新，只要系统资源（例如存储器）可用，它就一直被保持着，直到下一个拓扑改变为止。一般说来，仅在下列情况下，转发缓区的内容才会改变。
● OSPF互联网络拓扑改变，迫使重新计算所有的最短通路树。
● 发生了表示组成员分布改变的组成员关系LSA的改变。
2．混合MOSPF和OSPF路由器
MOSPF路由器可以跟非多播OSPF路由器结合使用。这就允许逐渐采用MOSPF，并允许以有限的规模做多播路由实验。
在建立基于源的最短通路投递树时需要排除所有的非多播OSPF路由器。根据在每个路由器的链路状态通告的选项域中设置的多播能力位（MC-bit），一个MOSPF路由器能够确定任何其他路由器的多播能力。忽略对非多播路由器的处理在转发多播流量时可能会产生若干潜在的问题。
①多路访问网络的指定路由器（Designated Router，DR）必须是一个MOSPF路由器。如果把一个非多播OSPF路由器选为DR，那么就不能选用该子网来转发多播数据报，因为非多播DR不能够为它的子网产生组成员关系LSA（它不运行IGMP，因此听不到IGMP主机成员关系报告）。
②即使有前往一个目的地的单播连接，也可能没有多播连接。例如，在两点之间仅有的通路可能需要通过一个不具备多播能力的OSPF路由器。
③在两点之间多播和单播的转发可能走不同的通路，这使得一些路由故障的解决更具挑战性。
3．MOSPF区际路由
区际路由适用于数据报的源和它的一些目的地组成员驻留在不同的OSPF区的情况。需要注意的是，多播数据报的转发仍然由从本地组数据库和基于数据报源的树建立的转发缓区的内容决定。主要的不同点在于组成员关系信息的传播方式和区际基于源的树的构建方式。
在MOSPF中，一个区的区边界路由器（Area Border Router，ABR）的子集起着区际多播转发器的作用。区际多播转发器负责在区之间转发组成员关系信息和多播数据报。配置参数确定一个特定的ABR是否也执行区际多播转发器的功能。
区际多播转发器归纳它们附接的区的组成员关系信息，并通过始发新的组成员关系LSA把该归纳信息传给主干。注意，在MOSPF中组成员关系的归纳是不对称的。这就意味着，虽然来自非主干区的组成员关系信息被洪泛进主干，但来自主干的（或来自其他非主干区的）组成员关系信息不会洪泛进任何非主干区。
为了允许在区之间转发多播流量，MOSPF引入“泛指多播接收方”。一个泛指多播接收方是一个路由器，它接收在一个区中产生的所有多播流量。在非主干区里，所有的区际多播转发器都作为泛指多播接收方运行。这就保证，源自任何非主干区的所有多播流量都被投递给它的区际多播转发器，然后如果需要，就将其转发进主干区。由于主干知道所有区的组成员关系，因此一个数据报只要被源区的多播ABR转发进主干，该数据报就可以被转发到在该OSPF自治系统中的适当位置。
在区际多播路由的情况下，通常不可能建立一个完全的最短通路投递树。树的不完全的缘由是因为没有把每个OSPF区的完全的拓扑和组成员关系信息在OSPF区之间分发。
通过使用泛指接收方和OSPF归纳-链路LSA进行拓扑估计。如果一个多播数据报的源跟执行计算的路由器驻留在同一个区中，剪枝过程必须谨慎，保证指向其他区的枝不被从树中剪去；仅那些没有组成员或没有泛指多播接收方的枝被剪除；包含泛指多播接收方的枝必须保留，因为本地路由器不知道在其他区中是否有组成员。
如果一个多播数据报的源与执行计算的路由器驻留在不同的区里，描述在源站周围的本地拓扑的细节不可得知。然而，这一信息可以用由源子网的归纳-链路LSA提供的信息进行估算。在这种情况下，树的基础始于把源子网直接连接到本区的每个区际多播转发器的枝。源自本区之外的数据报将通过它的一个区际多播转发器进入该区，因此它的所有区际多播转发器都必须是候选分发树的一部分。
由于每个区际多播转发器也都是一个区边界路由器（ABR），它必须为每个附接的区维持一个单独的链路状态数据库。因此，每个区际多播转发器都需要为它附接的每个区计算单独的转发树。
4．MOSPF树的建立和转发小结
MOSPF为每个（源，组）对结合建立一个单独的树。该树以源为根，包括作为叶的每个组成员。如果（M）OSPF域被划分成多个区，那么该树分几个部分建立，每次建立一个部分。然后，这些部分在连接多个区的区边界路由器处被粘在一起。
有的时候，某些区的组成员关系是未知的。MOSP通过把它们的区边界路由器作为“泛指多播接收方”加进树来，把树扩展到这些区。
在一个给定区内的树的建立取决于源的位置。如果源在区内，就使用“转发代价”，在区内的通路遵从“转发通路”，即单播分组从源往组成员传播将会采用的路径。如果源属于一个不同的区，就使用“反向代价”来构建以源为根的投递树。使用“反向代价”不是我们所希望的方式，但这是不得已而为之，因为OSPF的归纳LSA仅通告反向代价。
MOSPF树的建立过程是由数据驱动的。尽管在每个区的链路状态数据库中存在着组LSA，除非看到来自一个源到一个组的多播数据，否则相关的树不会建立。当然，如果链路状态数据库表明没有这个组的LSA，那么也不会建立对应的树，因为在这个区里一定没有组成员。因此，尽管MOSPF是“密集方式”路由协议，但它不是基于广播和剪枝，而是所谓的“显式加入”协议。
如果有一个没有见到过的（源，组）对的分组到达，那么路由器会对在链路状态数据库中的相关链路执行Dijkstra算法。Dijkstra算法输出这个（源，组）对的以源为根的最短通路树。路由器考察它在树中的位置，缓存期待的来自这个源的分组的输入接口，列出通往下游活动接收方的输出接口。对随后的流量针对这个缓存数据检查。来自这个源的流量必须在正确的接口上到达，才会对其做进一步的处理。