CN105933228B - 用于位索引显式复制的流量工程 - Google Patents

Abstract

本公开涉及用于位索引显式复制的流量工程。本文公开了用于通过一种新形式的位索引显式复制进行流量工程转发的方法和网络设备。在一个实施例中，方法包括在网络中的第一节点处接收包含消息位阵列的消息，以及将在消息位阵列中的一个或多个位位置处的位值与存储在第一节点处的转发表中的一个或多个条目进行对比。在该实施例中，一个或多个位位置与网络中的链路相对应。该方法实施例还包括：如果对比的结果指示在所述转发表中表示的链路被包含在消息要采用的路径中，那么在所述链路上转发消息。在方法的另一实施例中，消息是多播消息并且转发该消息包括转发多播消息的副本。

Description

用于位索引显式复制的流量工程

相关申请

本申请根据美国法典第35卷第119(e)章要求于2015年2月26日递交的题为“Traffic Engineering for Bit Indexed Explicit Replication”的美国临时专利申请No.62/121,291的权益，该申请的全部内容通过引用并针对所有目的被合并于此，如同其在本文中被完全且充分的给出。

技术领域

本发明涉及通信领域。

背景技术

网络节点转发数据。网络节点可以采用以下形式：一个或多个路由器、一个或多个网桥、一个或多个交换机、一个或多个服务器或任意其他适当的通信处理设备。数据通常被格式化为消息并使用转发表进行转发。消息是数据的格式化单元，其通常包含控制信息和有效载荷数据。控制信息可以包括标识源和目的地的信息，例如，地址、诸如校验和之类的错误检测码、序列信息等。控制信息通常在消息头和消息尾中找到。有效载荷数据通常位于消息头和消息尾之间。基于所使用的网络等级和网络协议之类的因素，消息可以被格式化为和/或称为诸如分组、数据报、片段或帧之类的各种具体类型之一。

转发消息涉及各种过程，这些过程尽管概念上简单但可能很复杂。转发所涉及的过程基于所使用的转发方法的类型而不同。整体转发配置包括单播、广播和多播转发。单播是点到点通信的方法，其最常用于特定节点(被称为源)希望向另一特定节点(被称为目的地)发送数据而不涉及向多个接收者发送数据的情况。广播是当源希望向某一域中的所有接收者发送数据时所使用的方法，并且多播允许源向某一域中的一组接收者发送数据而不向该域中的其他接收者发送数据。

对于诸如流媒体分发之类的很多流行应用而言，多播是数据转发的优选方法。一个原因是多播是一种带宽节约技术，其允许数据递送到多个接收者而避免相同消息的多个副本通过相同的网络链路进行传输。然而，在传统多播系统中使用了相对较大数量的控制平面信息。设置和维护控制信息在计算资源方面倾向于变得复杂和昂贵，并且可能成为整体网络性能的主要限制因素。

发明内容

根据本发明的一个方面，提供了一种方法，包括：在网络中的第一节点处接收包括消息位阵列的消息；将在消息位阵列中的一个或多个位位置处的位值与存储在第一节点处的转发表中的一个或多个条目进行对比，其中，一个或多个位位置与网络中的链路相对应；以及如果对比的结果指示所述转发表中表示的链路被包括在消息要采用的路径中，那么在所述链路上转发消息。

根据本发明的另一方面，提供了一种与网络中的节点相关联的网络设备，网络设备包括：一个或多个网络接口；存储器，存储器被配置为存储包括一个或多个条目的转发表；以及处理器，处理器被配置为：经由网络接口中的一个网络接口接收包括消息位阵列的消息；将在消息位阵列中的一个或多个位位置处的位值与转发表中的一个或多个条目进行对比，其中，一个或多个位位置与网络中的链路相对应；以及如果对比的结果指示所述转发表中表示的链路被包括在消息要采用的路径中，那么在所述链路上转发消息。

附图说明

通过参考附图，本公开可被更好地理解，并且其多个目的、特征和优势对本领域技术人员而言是明显的。

图1是示出示例网络的某些组件的简化图。

图2是示出示例网络的某些组件的简化图。

图3A是示出通过示例网络的转发消息的简化图。

图3B是示出通过示例网络的转发消息的简化图。

图4A是示出网络部分的示例的简化图。

图4B是示出网络部分的示例的简化图。

图5A是示出网络部分的示例的简化图。

图5B示出了转发表部分的示例。

图5C到5F是示出网络部分的示例的简化图。

图6A是示出网络部分的示例的简化图。

图6B示出了转发表部分的示例。

图6C是示出网络部分的示例的简化图。

图6D示出了转发表部分的示例。

图7是示出由这里所描述的网络的控制器或节点所执行的处理示例的流程图。

图8是示出由这里所描述的网络的控制器或节点所执行的处理示例的流程图。

图9A和9B是示出网络部分的示例的简化图。

图9C示出了转发表部分的示例。

图10A是示出由这里所描述的网络的控制器或节点所执行的处理示例的流程图。

图10B示出了转发表部分的示例。

图10C是示出由这里所描述的网络的节点所执行的处理示例的流程图。

图10D是示出由这里所描述的网络的控制器或节点所执行的处理示例的流程图。

图11A是示出由这里所描述的网络的节点所执行的处理示例的流程图。

图11B是示出由这里所描述的网络的节点所执行的处理示例的流程图。

图11C示出了转发表部分的示例。

图12A到12D是示出可用于这里所描述的网络的示例网络设备的某些组件的简化框图。

图13是示出可用于这里所描述的网络的示例网络设备的某些组件的简化框图。

图14是示出适于实现这里所描述的设备和系统的实施例的计算机系统的框图。

具体实施方式

概述

本文公开了通过一种新形式的位索引显式复制(BIER)进行流量工程转发的方法和网络设备。在一个实施例中，方法包括：在网络中的第一节点处接收包括消息位阵列的消息，以及将消息位阵列中的一个或多个位位置处的位值与存储于第一节点处的转发表中的一个或多个条目进行对比。在该实施例中，一个或多个位位置对应于网络中的链路。这一方法实施例还包括：如果对比结果显示转发表中所表示的链路被包括在消息要采用的路径中，则通过该链路转发消息。在另一方法实施例中，消息是多播消息并且转发消息包括转发多播消息的副本。

多播

多播传输将多播分组(通常包括标识多播组(例如多播组地址)的信息的分组)从源传递到多个接收者，而不会给源带来过重的负担。虽然本公开中的一些讨论关于分组，但是应该理解本公开还可被应用于其他类型的网络消息，例如数据报或数据帧。如这里所使用的，术语“接收者”表示已订阅到多播组的主机(例如，计算设备或应用)。不是由源复制多播分组并将多播分组的副本发送给每个接收者，而是由源发送多播分组的单个副本，而由多播使能的路由器(本文简称为节点)在到各个接收者的路径分叉的(一个或多个)点处复制该分组。多播路由协议通过在靠近多播分组的目的地处复制该多播分组来实现多播传输(即，一对多连接和多对多连接)，从而避免针对相同目的使用多个单播连接。这节省了网络带宽并提高了吞吐量。

典型多播路由协议要求每个节点的多播转发表都包括例如将每个多播流的源和组标识符映射到该节点必须经其转发该组的分组副本的接口以及该组的分组应经其正确到达的接口的信息。由每个多播使能节点维护的多播转发表可能在网络上变得非常大，其中具有很多多播源、很多多播组或二者。维护这样的多播转发表给网络可扩展性带来限制。

位索引显式复制(BIER)

在被称为位索引显式复制(Bit Indexexed Explicit Replication，BIER)的“无状态多播”技术中，多播网络内的状态信息量减少。在BIER转发中，接收者信息被编码于分组中，而不是在每个节点处基于多播源和组信息来在表中进行查找。具体地，接收者信息被编码于由分组承载的位阵列中。BIER转发在例如共同未决美国申请No.14/604,092中进行了更详细地说明，但一般而言，与多播接收者相关联的每个节点在位阵列中被分配位位置。被连接到接收者的节点在本文中也可被称为“接收者节点”或“目的地节点”。在给定位位置处的位值指示对应于该位位置的接收者节点是否是承载位阵列的多播分组的预期接收者或目的地。

在转发包含分组位阵列的BIER多播分组(或者更一般地，包含消息位阵列的BIER多播消息)中，BIER使能节点确定是否有任何该分组的预期目的地节点也是从该BIER使能节点可达的节点。这通过使用存储于BIER使能节点处的位索引转发表来实现，该转发表具有针对每个BIER使能节点的邻居(直接连接的下一跳)节点的条目。在一个实施例中，针对每个邻居节点的条目包括邻居位阵列，该邻居位阵列具有与分组位阵列相同的位位置到目的地节点的映射。然而，在邻居位阵列中，给定位位置处的位值指示相应的接收者节点是否从邻居节点可达，该邻居节点与包含邻居位阵列的转发表条目相关联。为了BIER转发的目的，节点是否从邻居节点“可达”取决于邻居节点是否被包括在到目的地节点的最短路径中，如通过在网络中所使用的内部网关协议(IGP)所确定的。消息位阵列在本文中还可被称为“位串”，并且邻居位阵列可被称为“位掩码”。

如果传入BIER分组的分组位阵列与转发表条目中的邻居位阵列的对比显示多播分组的至少一个预期目的地节点经由邻居节点可达，则通过使用来自转发节点的单播路由表的路由信息来将多播分组的副本转发到该邻居节点。该过程针对与任何其他邻居节点相关联的转发表条目进行重复，并且每个经转发的副本分组进而按照与在被各个BIER使能邻居节点接收时相似的方式而被处理。通过这种方式，多播分组根据需要被复制并转发以到达预期目的地。在一些实施例中，在转发过程中对分组位阵列进行修改，或是在节点处在分组位阵列与后续转发表条目中的邻居位阵列进行对比时，或是在承载分组位阵列的副本分组被转发到邻居节点之前，或在这两种情况下。这样的修改可以防止分组的循环和复制。

流量工程

上述BIER转发机制基于转发节点的单播路由信息的使用。BIER分组位阵列告知BIER使能节点分组必须到达哪些目的地而不告知使分组到达这些目的地所使用的路径。用于转发给定副本分组的路径是由转发节点的单播路由表确定的路径，该单播路由表通常使用最短路径优先算法建立。尚且没有如通常所实现的那样，使用BIER沿显式路径来路由分组(还被称为“流量工程”)的机制。

存在多播分组的显式路由不适合的情况。例如，显式路径通常用于被设计为监控或测量网络路径变量(例如，分组丢失或传输延时)的操作管理维护(OAM)活动中。显式路由可能有用的另一应用是将互联网协议(IP)用于视频广播的专业媒体网络的应用。视频广播网络通常包括在多个位置捕获内容、处理内容以及向一个或多个其他位置传输内容(被称为分发)。基于由控制器生成的控制信号，来自各个源的内容可被合并为连续的流，并且被提供给可能的多个接收者。在内容源之间进行切换以及对接收该流的接收者选择进行修改对时间要求非常严格。如果这些转换不是以非常明确的边界或时间间隔发生，则可能导致视频和音频失真或间断。视频传输也对在IP网络中可能发生的分组丢失所导致的错误非常敏感。因此，一些纠错方案包括通过替换路径来发送匹配分组流，从而接收者可以在流之间进行切换以重建无误信号。一般情况下视频广播所涉及的严格时间要求以及在某些情况下需要多个独立路径使得需要定义显式路径。

某些现有技术允许流量工程。例如，在采用多协议标签交换(MPLS)的网络中，显式路径可以使用被称为采用流量工程的资源预留协议(RSVP-TE)的协议来建立。当初始节点沿所请求的路径逐节点发送请求消息并且路径的最终节点通过沿该路径发回供该路径使用的MPLS标签来进行确认时，显式路径或“隧道”使用RSVP-TE被指定。这些标签随后必须被添加到沿着路径的节点的转发表。如果显式路径响应于网络拓扑或网络条件的改变而改变，则预留过程必须再次执行。RSVP-TE过程可被扩展到使用点到多点(P2MP)RSVP-TE的多播树。每个多播组将具有其自身的树预留过程及其自身的标签集，从而除了预留过程所需的时间和带宽之外，还需要每个节点处将标签与组和源信息相关的转发表的重要状态。

允许创建显式路径的另一转发机制是分段路由。分段路由在例如共同未决美国专利申请No.14/292,264中进行了详细说明。在分段路由中，路径信息以分段标识符集的形式承载在分组中，其中路径通过拓扑子路径来构造，其中每个子路径与分段标识符相关联。由分组承载的分段标识符集可以各种数据平面技术(例如，通过MPLS标签栈或通过嵌入互联网协议第六版(IPv6)扩展头中的标识符串)来实现。分段标识符可使用现有IGP来通告和交换，该现有IGP用于在IP网络中交换单播路由信息，从而不需要控制平面协议，例如，用于MPLS网络中的RSVP-TE协议或标签分发协议(LDP)。定义分组路径的分段标识符集例如由入口节点或网络控制器来确定，并被添加到分组的封装中。该封装将分段标识符沿所定义的路径顺序安置。然后转发通过在转发节点的分段路由转发表中查找第一分段标识符(例如，在使用标签栈的MPLS实现方式中是最上面的标识符)来进行。当对应于分段标识符的子路径已经被通过时，该标识符从分组所承载的分段标识符的活动集中移除。相应地，分组的路径通过顺序访问由分组承载的分段标识符来定义。虽然分段路由允许在每个转发节点处通过相当小的“状态”(标识符、标签等的存储)来定义显式路径，但是当前定义的分段路由不允许多播路径定义或转发。

采用流量工程的位索引显式复制(BIER-TE)

被称为采用流量工程的位索引显式复制(BIER-TE)的新的转发方法允许定义多播显式路径，同时展现出与上述现有BIER转发机制类似的多播状态信息的减少。现有BIER机制在本文中可被称为“BIER”、BIER最短路径优先(“BIER-SPF”)或“非TE BIER”。BIER和BIER-TE二者将路径相关信息编码于由分组承载的位阵列中。然而，对于这两个技术而言，所编码的信息类型是不同的。如上所述，BIER所使用的位阵列中的位位置对应于多播分组的接收者(例如连接到各接收者的出口节点或这些出口节点的入口节点)。而在BIER-TE中，位位置对应于路径中的链路，其中“链路”在本文中一般被用作网络节点与网络的另一节点或另一协议等级之间的数据连接。本文所描述的链路在本文中作为路径段或子路径，使得消息的路径由一系列相连的链路构成。由位位置表示的链路在本文中也被称为“跳”或“邻接”。

由BIER-TE位阵列中的位位置表示的链路可具有多种不同的类型。例如，链路可以连接一个网络节点和直接相连的相邻节点。这种类型的直接链路可被定义为单向或双向链路。位位置还可表示一个节点与非相邻节点之间的间接连接，使得该链路包括一个或多个中间节点。除了网络节点之间的这些直接和间接连接之外，位位置还可以表示网络的BIER-TE协议层和更高的协议层之间的连接。

准备通过BIER-TE来转发分组包括四个基本过程：确定分组(和同一多播组中的其他分组)路径(或形成多播树的路径集)；向连接在一起以创建路径或树的链路分配位位置；对分组进行封装以包括分组位阵列，该分组位阵列已在与沿路径的链路所对应的位位置中进行了位设置；以及对于沿路径的每个节点，表示连接到该节点的链路的位位置以及适当的转发指令被添加到该节点处的BIER-TE转发表中。这些过程在下文将详细讨论。

BIER-TE转发示例

图1示出了示例网络100。网络100包括节点118、120、122、124、126和128，这些节点被配置为使用BIER-TE来转发分组或其他消息。例如，这些BIER-TE使能节点被配置为基于BIER-TE位位置分配来存储和使用相应的位索引转发表，下文将进一步解释。在一些实施例中，这些BIER-TE使能节点中的一些或全部也能够使用反应不同位位置分配的不同转发表来转发非TE BIER分组。字母A到F表示BIER-TE使能节点的各个唯一标识符，例如，IP环回地址(在IP网络的情况下)。为了简洁起见，这些字母在本文被用于指代各个节点，并且用于描述网络100中的链路和路径。节点之间的实线表示节点之间的数据连接；在一个实施例中，这些连接是物理的点到点链路。

在图1的实施例中，BIER-TE使能节点118、120、122、124、126和128构成提供商网络或域。该提供商网络可由互联网服务提供商用于向消费者传输分组。该域包括核心节点120和122以及提供商边缘节点118、124、126和128。提供商边缘节点被耦合至消费者边缘节点110、112、114和116。主机102、104、106和108被耦合至消费者边缘节点。在图2的实施例中，主机102是多播源，而主机104、106和108被配置为多播接收者或订户。BIER-TE使能节点118被配置为多播数据分组的入口路由器。入口路由器经由消费者边缘节点110被耦合至源102。来自源102的多播数据分组经由入口路由器118进入BIER-TE网络。BIER-TE使能节点124、126和128中的每一个被配置为出口路由器。出口路由器可被连接(直接地或经由消费者边缘路由器)至主机(例如接收者)或其他网络。本文所使用的出口路由器是BIER-TE使能节点，该BIER-TE使能节点是源与接收者之间的路径上的最后一个BIER-TE使能节点。出口路由器可以是直接或间接(例如通过非BIER使能消费者边缘节点)耦合至接收者的提供商边缘节点。

网络100还包括中央控制器130。在实施例中，控制器130是BIER-TE网络的数据路径外部的控制器主机。在替换实施例中，入口节点118被配置为执行控制器130的一些或全部功能。在另一实施例中，控制器130的一些或全部功能可通过手动配置过程来执行。在实施例中，图1的控制器130通过与用于通过网络100转发多播分组不同的机制和/或协议来与BIER-TE使能节点中的每一个交互。该交互可被称为“带外”或“交叠”信令。控制器130与入口节点A之间的示例性交互由图1中的虚线132示出。虽然为了简洁起见，图1省略了额外的虚线，但是类似的通信也发生在控制器130与节点B到F中的每一个之间。控制器130与BIER-TE使能节点之间的通信可以通过一个或多个控制协议发生。作为示例，与控制器130的通信可以使用NETCONF和/或RESTCONF协议以及YANG数据建模语言来发生。这些协议例如在“Network Configuration Protocol(网络配置协，NETCONF)”(R.Enns，M.Bjorklund，J.Schoenwaelder，和A.Bierman，Eds.，RFC 6241，2011年6月，见https：//tools.ietf.org/html/rfc6241)、“RESTCONF Protocol(RESTCONF协议)”(A.Bierman，M.Bjorklund，和K.Watsen，2015年6月4日，见https：//tools.ietf.org/html/draft-ietf-netconf-restconf-05)、以及“YANG-A Data Modeling Language for the Network ConfigurationProtocol(针对网络配置协议NETCONF的数据建模语言)”(M.Bjorklund，Ed.，RFC 6020，2010年10月，见https：//tools.ietf.org/html/rfc6020)中进行了进一步描述，这些文档通过引用被合并于此，如同在本文被全部给出。作为另一示例，在BIER-TE使能节点运行BGP的实施例中，控制器130可以使用边界网关协议(BGP)与节点A到F通信。与控制器130的通信通过到控制器130的数据链路来承载，该数据链路在图1中未明确示出。在实施例中，节点A到F与控制器130之间的控制通信通过用于通过网络100来传输消息的相同物理链路中的一些或全部来承载，但是不同协议用于消息传输和控制传输。

在图1的实施例中，控制器130的功能包括：向网络100的BIER-TE使能部分内的链路分配位位置；将位位置分配传输至各BIER-TE使能节点中的转发表；确定特定多播组内的消息将遵循的显式路径(或树)；以及向组的BIER-TE入口节点传输组成路径的位位置以及多播组的标识。采用控制器(例如控制器130)的实施例可与软件定义网络(SDN)实现相关联。在分配位位置中，控制器使用网络的拓扑信息。在一个实施例中，网络节点运行内部网关协议(IGP)，并且控制器130通过IGP通告来获得网络100的拓扑。在替换实施例中，控制器130通过不同协议的操作或通过手动配置来获得拓扑信息。控制器130通常还在分配位位置中使用多播组成员信息。位位置分配仅对于消息在网络中要采取的路径中所包括的网络链路是需要的，而不是对于网络中的每条链路都是必需的。因此，多播组成员信息能够协助控制器130确定哪些网络链路应被分配位位置，并且被包括在显式路径中。在一个实施例中，提供商边缘节点(例如，网络100的节点A、D、E和F)与控制器130通信以将其各自的主机标识为特定多播传输的源或接收者(订户)，并通知控制器组成员状态的任何改变。在另一实施例中，通过提供商边缘节点与控制器130的通信是响应于从节点相关联的主机接收多播协议消息(例如，“加入”或“删除”消息)。

图1示出了对链路的示例性位位置分配。在图1使用的符号中，分配给链路的位位置用方括号中的数字来表示。符号的其他方面表示不同类型的链路，下文将进一步解释。例如，位位置分配134包括位于单向箭头上的方括号中的位位置号。箭头指向由位位置所表示的链路的方向。例如，位位置1被分配给节点A和节点B之间的直接链路，用于从A到B的消息传输。换言之，位位置1表示节点A和B之间的单向直接链路。这样的直接链路还可被称为例如“直接邻接”、“相连邻接”、“前向连接邻接”或“直接跳”链路或邻接。类似地，位位置2被分配给节点B和C之间的单向直接链路，并且位位置4被分配给节点B和E之间的单向直接链路。网络100中BIER-TE使能节点之间的其他单向直接链路包括节点C和D之间(分配位位置3)以及节点E和F之间(分配位位置5)的单向直接链路。

在本文所使用的惯例中，向链路分配位位置号意味着对包含该链路的路径进行编码的位阵列将在对应于该链路的位位置号的位位置中具有置位位(位值为“1”而不是“0”)，从右侧数起。例如，仅对图1的节点B和C之间的路径进行编码的12位位阵列(被分配位位置2)被表示为{0000 0000 0010}，出于可读性考虑，其中位阵列中的位被安排为四个一组。然而，其他惯例可被用于本文所描述的方法和系统的实施例中。例如，包括在路径中的链路的位置中使用位值“1”而其他使用“0”，这可以被反转，或者在一些实施例中，位位置可以从位阵列的最左位数起。作为另一示例，虽然位位置在本文以“1”开始编号，但在其他实施例中可以使用以“0”开始的编号系统。

返回到图1，另一类型的链路由位位置分配136表示。分配136将位位置6分配给节点C和E之间的双向直接链路，如位位置号下面的双向箭头所示。换言之，位位置6既表示节点C到节点E的直接链路，又表示相反方向节点E到节点C的链路。另一类型的链路由图1的位位置分配138表示。位位置138用于与出口节点(例如节点D和F)相关联的链路。在分配138的符号中所使用的斜向上的箭头表示到网络100中的更高协议层的链路。具体地，所分配的位位置与将BIER-TE信息从消息中解封装、以及将消息传递至下一更高协议层或在BIER-TE域外所使用的转发协议相关联。作为示例，消息被传递至的协议可以是MPLS多播或IP多播协议。任何所需的进一步的复制或转发随后使用更高层协议来执行。到更高协议的这种类型的链路可被称为例如“本地链路”、“本地邻接”、或“本地解封装”邻接或链路。在图1的实施例中，位位置9被分配有节点D处到网络100中的下一更高协议层的链路，位位置8被分配有节点F处到下一更高协议层的链路，并且位位置7与节点E处类似的链路相关联。

图1中的位位置分配140表示另一类型的网络链路。分配140将位位置10分配给节点A和节点E之间的链路，但是该链路不是直接链路，因为这两个节点在网络100中不是直接连接的。在图1的实施例中，消息可以在节点A和E之间通过穿过节点B到节点E或通过穿过节点B然后穿过节点C以到达节点E来传输。对于由节点A转发的一些消息，消息穿过节点E也许是重要的，而该消息采用哪条路径到达节点E可能是无所谓的。对于这样的消息，控制器130可以构造包括节点A到节点E的间接链路的显式路径。该间接链路在图1中通过虚线142示出，并且以表示目的地节点的E为上标的位位置分配140的符号来表示，而没有沿特定路由指向的箭头。这种类型的间接链路还可被称为例如“远程邻接”、“前向路由邻接”、或“松散跳“链路或邻接。在一个实施例中，节点A通过使用存储于节点A处的单播路由信息来实现与位位置10相关联的消息转发。与以上所讨论的位位置分配相关联的转发机制将在下文结合图2和图3进行进一步描述。

图1所示的位位置分配被用于描述由多播消息所采用的显式路径。例如，通过网络的路径ABEF由具有位位置1、4和5的链路构成。由消息承载的、被分配给路径ABEF的12位位阵列可以被表示为{0000 0001 1001}。路径ABCD由具有位位置1、2和3的链路构成，从而针对该路径的位位置被表示为{0000 0000 0111}。

图1的位位置分配符号意图协助使用被分配了位位置的链路或路径段进行显式路径形成的虚拟化。在BIER-TE转发中使用经分配的位位置是通过对应于与给定BIER-TE使能节点相关的那些位位置的转发表条目，并且通过消息封装以承载对显式路径进行编码的位阵列以由该消息传输来实现。示例性消息位阵列和转发表条目被示于图2中。图2示出了图1所示的网络100，但具有每个节点的示例性转发表部分中所反映的位位置分配。图2还包括BIER-TE使能节点的接口指定。例如，节点B具有三个接口，分别指定为1-3。图1、3A和3B中的网络100的表示中省略了这些接口指定，以使这些图中所示的其他特征更容易看到，但应该理解，相同的指定也被分配给这些图中所示的网络100的接口。以节点A开始，BIER-TE转发表(BTFT)部分202被存储于节点A。BIER-TE的转发表还可被称为位转发TE(BFTE)表。表部分202将链路位阵列(LBA)与节点A到BIER-TE使能节点的每条链路相关联。链路位阵列是在对应于被分配给相应链路的位位置具有单个置位位的位阵列。为了可读性，这里的表中所示的位阵列可以将这些位分组为4比特的子组。转发表中的链路位阵列此处还可被称为“位掩码”。在一个实施例中，以链路位阵列的形式来存储链路的位位置协助将链路位阵列与即将传入消息的消息位阵列进行对比。或者，在一些实施例中，被分配给链路的位位置可以简单地被存储为位位置号(例如，表202中的链路AB为“1”，AE为“10”)。这样的位位置号当然可以被存储为任意适当的编号系统中的号码，包括二进制或十六进制。

在图2的BTFT的“链路”列中，网络100中两个BIER-TE使能节点之间的链路由指定链路的发送节点的字母跟着指定接收节点的字母来表示。例如，链路AB指定节点A到B的直接单向链路，而AE指定节点A到节点E的间接(因为这些节点在网络100中不直接连接)单向链路。单个字母被用来表示节点处的“本地”链路(即，从BIER-TE协议层到下一更高协议层的链路)。该链路符号是为了方便和易于解释，并且可能不反映链路在实际转发表中被标识的方式。本领域普通技术人员鉴于该公开将认识到，链路可以各种方式存储于转发表中。例如，转发表可包括节点地址、可分开存储链路的发送端和接收端、和/或可包括关于链路的类型或属性的附加信息。一般地，BIER-TE使能节点的BTFT包括未示于图2的表部分中附加信息，例如，附加转发指令或入口和出口接口信息。在一个实施例中，一旦位位置已被分配给网络100内的链路，则BTFT部分202中的位位置和链路信息通过控制链路132从控制器130接收。在替换实施例中，表部分202的位位置和链路信息通过手动配置过程被提供给节点A。

节点A的BTFT的部分202将位位置1分配给节点A到B的直接链路，而将位位置10分配给节点A到E的间接链路。这些转发表条目反映涉及节点A的两个位位置分配，与图1采用不同的符号。因为只存在涉及节点A的两个位位置分配，因此在节点A的BTFT中只存在两个条目。每个BIER-TE节点处的转发表仅包括针对将该节点连接到其他BIER-TE节点的链路的条目，并且在到其他BIER-TE节点的那些链路中，仅包括具有经分配的位位置的链路。虽然在网络100的简化示例中，位位置被分配给BIER-TE使能节点之间的每个直接连接，但是在其他实施例中，位位置将不被分配给每条直接链路。在实施例中，位位置仅被分配给需要形成路径或树以供网络中的消息通过的链路。

节点B的BTFT的部分204也示于图2中。在图2的实施例中，BTFT B包括传入链路和外出链路。链路AB(已被分配位位置1并且也被包括在节点A的BTFT中)在BTFT B中被表示为到节点B的传入链路。链路BC和BE(已分别被分配位位置2和4)是包括在BTFT B中节点B的外出链路。节点处BIER-TE转发的基本机制(将在下文结合图3进一步描述)包括确定与该节点的外出链路相关联的位位置是否包括要转发的消息的消息位阵列中的置位位。然而，在一些情形中，在BTFT中包括传入链路也可能是有利的。例如，在一些实施例中，对应于传入链路的位位置中的位在被转发的消息的消息位阵列中被重置。这种重置过程可防止消息循环和复制；重置过程的实施例将在下文更详细地讨论。依赖于任何重置过程的时间，对应于传入链路的位位置在一些实施例中可被用于确定进入节点的消息应被该接受还是拒绝。因此，BTFT B以及图2所示的其他转发表中针对传入链路的条目可被用于包括这些重置和检查过程的处理中。在图2所使用的链路符号中，传入链路的名称将表示该节点的字母放在第二位(例如，链路AB是到节点B的传入链路)，而外出链路的名称将表示该节点的字母放在第一位(例如，链路BC是节点B的外出链路)。在实施例中，BTFT包括额外字段或列以指示表条目的链路是传入链路还是外出链路。在图2的替换实施例中，针对每个BIER-TE使能节点的BTFT仅包括针对各节点的外出链路的条目。

与图1所示的位位置分配相比，BTFT部分204反映了对于链路AB、BC和BE的相同分配。在一个实施例中，BTFT部分204中的位位置和链路信息通过类似于控制链路132的控制链路来从控制器130接收。在替换实施例中，表部分204的位位置和链路信息通过手动配置过程被提供给节点B。

被分配给将节点C连接到其他BIER-TE使能节点的链路的位位置被示于节点C的BTFT的部分206中。表部分206包括节点C的传入链路和外出链路，并且以上结合节点B所讨论的方面同样适用于节点C。因为节点C和E之间的链路是具有单个经分配的位位置的双向链路(如以上结合图1所讨论的)，因此BTFT C包括两个位位置6的条目：双向链路的每个方向对应一个。链路EC是节点C的传入链路，而链路CE是外出链路。在替换实施例中，BTFT C包括针对节点C和E之间的链路的单个条目，并且该条目包括指示该链路是单向链路还是双向链路的附加字段或列。与图1所示的位位置分配相比，BTFT部分206反映了针对链路BC、EC、CE和CD的相同分配。在实施例中，BTFT部分206中的位位置和链路信息通过类似于控制链路132的控制链路从控制器130接收。在替换实施例中，表部分206的位位置和链路信息通过手动配置过程被提供给节点C。

节点D的BTFT的部分208也被示于图2中。节点D是BIER-TE域的出口节点，并且其BTFT包括到更高协议层的链路。位位置2被分配给传入链路CD，位位置9被分配给节点D处到下一更高协议层的链路。BTFT部分208中的条目对应于图1中结合节点D所示的位位置分配。与网络100的其他BIER-TE使能节点类似，节点D可以通过手动配置过程从控制器130接收信息以存储于其BTFT中。节点F的BTFT部分212也被示于图2中，并且类似于节点D的BTFT部分。BTFT部分212中的位位置5被分配给传入链路EF，位位置8被分配给节点F处到下一更高协议层的链路。

图2中所示的最大BTFT部分是针对节点E，包括对于三条传入链路、两条外出链路及节点E处到下一更高协议层的链路的位位置分配。在网络100的实施例中，节点E是对于通过CE节点116发送至接收者108的消息的出口节点，并且是针对发送至BIER-TE使能节点F的消息的核心节点。与节点C的BTFT类似，节点E的BTFT部分210包括被分配位位置6的传入链路和外出链路二者，因为节点C和E之间的双向链路被分配该位位置。BTFT部分210中的条目对应于图1中结合节点E所示的位位置分配。与网络100的其他BIER-TE使能节点类似，节点E可从控制器130或通过手动配置过程来接收信息以存储于其BTFT中。

如上所述，图2中所示的BTFT一般包括未示出的额外信息，包括接口或端口信息，并且BTFT可以具有与图2所示的方式不同安排的信息和条目。例如，图2的BTFT将传入链路的条目与外出链路的条目分开分组。在其他实施例中，BTFT可以将条目用位位置号排序，而不管链路是进入还是外出。作为另一示例，图2的BTFT仅包括针对与该BTFT所存储的节点相连接的链路所分配的位位置的条目。在替换实施例中，每个BTFT包括针对该网络所使用的位阵列长度中的每个位位置的条目，但是对于未被分配给连接到该节点的链路的位位置的条目为空(不具有链路信息)。

除了为每个BIER-TE使能节点填充BIER-TE转发表，准备通过BIER-TE进行转发包括针对要使用BIER-TE进行转发的每个多播组，存储BIER-TE消息位阵列。BIER-TE组路径表(GPT)214的示例性部分被示于图2中。在实施例中，GPT部分214存储于入口节点A处，以供节点A用于封装传入多播分组以用于BIER-TE转发。在另一实施例中，分配给每个多播组的消息位阵列通过控制器130提供给节点A。或者，多播组的消息位阵列通过手动配置过程被提供给给节点A。网络100的GPT部分214包括组标识符或地址列以及要被分配给该组中的消息的消息位阵列的列。在实施例中，GPT中的组标识符或地址是由传入的多播消息承载的组标识符或地址。在另一实施例中，替代多播组信息或除多播组信息之外，GPT包括多播源信息。消息位阵列(MBA)是当消息被封装以供BIER-TE转发时，消息所承载的位阵列。在分组网络中，消息位阵列在这里可被称为分组位阵列(PBA)。消息位阵列或分组位阵列在这里还可被称为“位串”。如这里所使用的，术语“位阵列”、“位串”或“位掩码”指具有固定或可变长度的一组位。

特定BIER-TE网络中所使用的位阵列长度(即，阵列中的位数)可以静态配置或动态分配并在BIER-TE网络中分布。位阵列可能具有任何适当的长度。在一个实施例中，该长度根据网络的大小和容量来确定。在一个实施例中，位阵列的长度在8到4096比特之间。在另一实施例中，位阵列的长度在256到1024比特之间。在一个实施例中，最大位阵列长度值通过BIER-TE网络中BIER-TE使能节点的硬件或软件限制来确定。在一个实施例中，BIER-TE网络中的不同BIER-TE使能节点具有不同的最大位阵列长度。例如，一个BIER-TE使能节点可具有128比特最大位阵列长度，而另一BIER-TE使能节点可具有256比特最大位阵列长度。可由消息位阵列中的位位置表示的链路或路径段的数目取决于阵列的长度。用于减少定义网络中的路径或树所使用的位位置数的方法将在下文进一步讨论。

与BIER-TE转发表一起，在一些实施例中，GPT由从控制器130接收到的信息来填充。如上所述，控制器130使用拓扑信息和多播组信息来分配位位置和确定用于多播组的显式路径和树。在一个实施例中，网络100中的控制器130和节点运行IGP，并且控制器130通过IGP通告获得拓扑信息。在替换实施例中，BIER-TE使能节点通过使用控制协议的查询或报告过程向控制器130提供拓扑信息(例如邻居信息)。在一些或全部BIER-TE使能节点未运行IGP的实施例中，节点仍可以通过例如层2握手或宣告协议来获得邻居信息。在实施例中，BIER-TE使能节点使用地址解析协议(ARP)或邻居发现协议(NDP)来获取邻居信息。

如上所述，在一些实施例中，通过提供商边缘节点(例如，网络100中的节点A、D、E和F)向控制器130提供多播组信息。在另一实施例中，控制器130与消费者边缘节点(例如网络100的节点110、112、114和116)通信，并且从这些节点接收多播组信息。除了拓扑信息和多播组信息，与特定网络或应用相关的规则或要求可被控制器130用于确定多播组的显式路径和树。例如，视频传输网络中的纠错方案可能需要视频流通过两个分离的非重叠路径进行发送。在一些实施例中，控制器130考虑各种流量工程规则和要求。作为示例，在一些实施例中可以考虑共享风险组(SGR)信息。在一些实施例中，控制器130所使用的以上信息中的一些或全部通过手动配置过程提供给控制器130。在另一实施例中，显式路径或树信息通过手动配置过程提供给控制器130或入口节点A。

图2中GPT的部分214包括针对两个多播组的消息位阵列。组G1被分配MBA{00011111 0111}(为了可读性，这里示为以4比特为一组，之间间隔开)。组G1的MBE在位位置(BP)1、2、3、5、6、7、8和9处具有置位位。与BIER-TE使能节点的BTFT中的链路相比，针对组G1的树包括链路AB(BP 1)、BC(BP 2)、CD(BP 3)、EF(BP 5)、CE或EC(BP 6)、E(本地——BP 7)、F(本地——BP 8)和D(本地一-BP 9)。通过节点C和E之间的双向链路所采用的方向在基于网络100的拓扑考虑该组链路时变得清楚。在节点A进入，G1消息被转发至节点B，然后至节点C，在该点处消息被复制，一个副本被转发至节点D，一个副本被转发至节点E。因此，位位置6在组G1的树中对应于链路CE。副本消息然后从节点E发送至节点F，并且另一副本消息在E处根据节点E的“本地”链路进行解封装。G1分组的转发将在下文结合图3A进行更详细地描述。

GPT部分214中的组G2被分配MBA{0011 1011 0100}，在BP 3、5、6、8、9和10处具有置位位。根据BIER-TE转发表中的BP分配，针对组G2的树包括链路CD(BP 3)、EF(BP 5)、CE或EC(BP 6)、F(本地——BP 8)、D(本地——BP 9)和AE(BP 10)。基于网络100的拓扑考虑该组链路，并且假设G2消息在节点A处进入BIER-TE域，则消息首先被转发至节点E，在节点E处消息被复制，一个副本被转发至节点F，一个副本被转发至节点C。因此，位位置6在组G2的树中对应于链路EC。发送到节点C的消息然后被转发至节点D，在节点D处，该消息根据节点D的“本地”链路进行解封装。发送到节点F的消息同样根据节点F的“本地”链路进行解封装。G2分组的转发将在下文结合图3B进行更详细地描述。

图3A示出了通过网络100对多播组G1中的多播消息(例如，分组、帧或数据报)进行转发的过程。网络100如图1和2所示，针对节点A到F的GPT部分214和BTFT部分如图2所示。图1和2所示的控制链路132已从图3中移除，在某种程度上是为了附图清楚，而且还示出控制器130与BIER-TE使能节点之间的通信在实际消息转发期间一般是不需要的。通过控制器130的通信建立网络100以供BIER-TE转发，并且随后用于在网络或多播流发生任何改变的情况下对GPT和/或转发表进行更新。在图3A中，表示多播消息图标(例如，原始消息302和BIER-TE封装消息304)被叠加到网络100的图示上。该图标表示消息(或消息的副本)以箭头方向穿过网络时在连续的时间拍下的快照。例如，在一个时间点，消息310从节点B向节点C移动。在后续时间点，消息310已被复制并继续转发，使得消息副本312和314分别从节点C向节点D和E移动。在图3A的实施例中，消息302从源主机102通过消费者边缘节点110发送至BIER-TE入口节点A。入口节点A使用包括在多播消息中的多播组地址和/或源地址来访问其GPT并选择与多播组相关联的消息位阵列。在选择了对应于多播组的MBA之后，节点A将消息位阵列封装到多播消息中，从而产生BIER-TE消息304。

在入口节点A能够通过不同于BIER-TE的其他方法进行多播转发的实施例中，节点A将需要确定消息302将被封装为BIER-TE。在一个实施例中，节点A检查其已存储以供多播消息封装的每个表(例如，针对BIER-TE的GPT或针对非TE BIER的组成员表(GMT))。如果针对传入多播消息的源信息或多播组被包括在可用表之一中，则使用相应的封装。在另一实施例中，这些表以规定的顺序进行检查，并且使用与包括到来消息的组或源信息的第一表相对应的封装。在替换实施例中，对于传入多播消息的封装被扩展为包括对于BIER-TE转发应在可用的地方使用的指示。在该实施例中，节点A知道检查BIER-TE GPT以寻找要应用于到来消息的消息位阵列。

将消息位阵列封装到消息302上以形成BIER-TE消息304可以多种方式实现。在一个实施例中，现有封装适于或被扩展为承载BIER-TE信息。例如，在一个实施例中，消息位阵列被写到互联网协议第6版(IPv6)报头的目的地地址字段，对于该实施例，多播消息是IP分组。在另一实施例中，消息位阵列被写到一个或多个IPv6扩展头。作为另一示例，具有MPLS封装的IP分组使用在分组和IP报头和数据链路层报头之间插入的一个或多个32位标签来转发。在一个实施例中，包括消息位阵列的BIER-TE相关信息被包括在MPLS标签栈中。在替换实施例中，消息位阵列被编码于MPLS标签结构外、MPLS标签栈和分组的有效载荷之间。在另一实施例中，位阵列可被包括在标签栈和有效载荷之间的BIER-TE报头中，其中BIER-TE报头还可包括额外信息。作为以诸如上述方式来调整现有封装的替换选择，在一些实施例中可以使用专用BIER-TE封装，例如专用BIER-TE报头。在另一实施例中，控制器130将BIER-TE封装格式传输给网络100中的BIER-TE使能节点。

当到来消息已被封装从而形成BIER-TE消息时，节点A继续该消息的BIER-TE转发。基本BIER-TE转发机制是确定转发节点的BIER-TE转发表中表示外出路径的任何位位置是否包括消息位阵列中的置位位。如果MBA中置位位共享转发表中外出链路的位位置，则通过该链路转发分组的副本。在一个实施例中，确定MBA中是否有任何置位位与转发表中的链路具有相同的位位置包括将转发表中的链路表示为链路位阵列，其中LBA中的每个位(除了被分配给该链路的位位置中的位)被设置为零。在另一实施例中，然后在消息位阵列和链路位阵列之间执行逻辑“与”(AND)操作。如果“与”操作的结果为“真”(TRUE)，则消息位阵列在分配给该链路的位位置中具有置位位。在另一实施例中，使用不同的操作来检查对应于转发表中的链路的MBA中位位置的位值。在另一实施例中，对消息位阵列中的置位的位位置进行标识，然后检查BIER-TE转发表以确定该表中是否存在对应于任何经标识的位位置的链路。

将该机制应用到图3A的节点A处的消息304，消息304的消息位阵列与BTFT部分202的条目进行对比。节点A的BTFT只具有两个位位置对应于链路：BP 1对应于链路AB，BP 10对应于链路AE。其中之一BP 1对应于消息304的MBA中的置位位。因此，该消息通过链路AB转发至节点B。注意，消息304的MBA与节点A的BTFT的条目的对比可通过包括以上所述的那些的多种方式来执行。例如，消息304的MBA与BTFT A中的链路AB的LBA的逻辑“与”产生的结果为“真”(TRUE)，而与BTFT A中的链路AE的LBA的相同操作产生的结果为“假”(FALSE)。该方法的变体是首先对BTFT中的所有外出链路的链路位阵列执行逻辑“或”(OR)，然后将结果与MBA执行“与，并且标识”与“操作的结果中任何置位的位位置。然后将消息的副本通过对应于置位位的任何链路进行转发。作为另一示例，消息304的MBA中的置位的位位置可以逐一考虑，检查BTFT以查找与每个置位的位位置相关联的链路。该过程的结果也是将消息仅通过链路AB转发。

在实施例中，通过直接连接链路(例如，节点A和B之间的链路)的BIER-TE转发是通过层2(L2)转发而不是路由做出的。在仅使用直接连接链路的另一实施例中，BIER-TE使能节点不需要具有路由表或运行IGP。

在图3A的实施例中，在消息304通过链路AB转发之前，在节点A处执行重置操作。位位置306对应于该消息通过其进行转发的链路；该位置中的位被重置(在这里所使用的位值惯例中，设置为0)，从而产生消息308。将对应于消息通过其进行转发的链路的每个位位置中的位重置保证了在发生网络环路时，相同消息不能通过相同链路被重新发送。在一个实施例中，重置过程使用与每个BTF相关联的重置位掩码来执行。对于图3A所使用位值惯例，重置位掩码在对应于消息通过其进行转发的链路的每个位位置处具有位值0，并且在每个其他位置具有位值1。在另一实施例中，每个BTFT存储重置位掩码，该重置位掩码在对应于消息从该节点通过其进行转发的链路的每个位位置具有0。例如，BTFT中的每条外出链路的链路位阵列可被“或”在一起，并将结果反转，使得重置掩码在表中的每条外出链路的位位置中具有0，并且在每个其他位位置中具有1。通过这种方式，可使用相同的重置位掩码，而不管特定消息实际通过哪些链路进行转发；无论如何任何未使用的链路的位位置将在消息位阵列中被设置为0，使得重置掩码对于转发消息的MBA的这些位位置无影响。在另一实施例中，重置位掩码在对应于连接到该节点的传入链路或外出链路的每个位位置中具有0。这里所描述的重置过程不需要在无环的网络拓扑中，并且存在一些位位置分配情境要求位不被重置。重置过程变体将在下文进一步讨论。

返回图3A的转发示例，BIER-TE使能节点B从节点A接收消息308。在节点B通过除了BIER-TE之外的其他方法来转发消息的实施例中，节点B首先需要确定消息308是BIER-TE消息。将消息标识为BIER-TE消息可以各种方式被包括在消息的封装中。例如，在BIER-TE在MPLS网络中实现的实施例中，特定最上面的MPLS标签可被用于标识BIER-TE消息。或者，专用报头或报头字段可被用于将消息标识为BIER-TE消息。

当节点B将消息308识别为BIER-TE分组时，转发以与以上针对节点A所述类似的方式进行。消息308中的消息位阵列与关联于节点B的BTFT中外出链路的转发表条目进行对比。节点B的BTFT部分204包括两个位位置被分配给外出链路：BP 2对应于链路BC，BP 4对应于链路BE。消息308中的消息位阵列在BP 2处具有置位位，而在BP 4处不具有置位位。因此，该消息以上面针对节点A所讨论的方式，通过链路BC转发至节点C。在图3A的实施例中，节点B还采用以上针对节点A所讨论的重置过程，使得转发消息310将BP 2处的位重置。在节点C处，BIER-TE转发以与节点B类似的方式进行。节点C的BTFT部分206包括两条外出链路：CD(具有BP 3)和CE(具有BP 6)。传入消息310的消息位阵列在BP 3和BP 6处均具有置位位。因此，消息310被复制，其中一个副本(消息312)通过链路CD转发至节点D，而另一副本(消息314)通过链路CE转发至节点E。节点C还实现位重置过程，使得BP 3和BP 6处的位在每个转发消息中被重置。

在节点D处(在节点D处消息副本312被接收)，BTFT表中的唯一外出链路是节点D的本地链路(具有BP 9)。消息312的消息位阵列在BP 9处具有置位位，因此节点D从消息中移除BIER-TE封装，恢复原始多播消息302的格式。经解封装的消息变为消息316，其被传递至节点D处的下一更高协议层(例如，IP多播或m-LDP)，然后经由消费者边缘节点112转发至接收者104。

在节点E处(在节点E处消息副本314被接收)，BTFT表中具有三条外出链路：EC(具有BP 6)、EF(具有BP 5)和节点E的本地链路(具有BP 7)。消息314的消息位阵列在位位置5和7处具有置位位，而在BP 6处不具有置位位。节点E和C之间的双向链路示出了在某些情况下位重置过程的重要性。因为位位置6被分配给节点C和E之间的链路的两个方向，因此如果BP 6处的位在转发消息314之前未在节点C处重置，则消息将会从节点E发回节点C。如果消息位阵列中BP 6处的位未被任何节点重置，则消息将持续在这些节点之间来回发送。相反，消息314被复制，其中一个副本作为消息320被转发至节点F，另一副本被解封装以形成消息318，消息318具有在BIER-TE域之外使用的原始消息格式。消息320随后在节点F处根据消息320的消息位阵列中BP 8处的置位位进行解封装以形成消息322。消息318和322通过在BIER-TE域之外使用的协议被转发至其各自的接收者。

如图3A及以上描述所示，通过图3A的BIER-TE域进行多播消息的转发使得消息的副本通过特别预定的路径集被递送至接收者104、106和108。注意，因为在图3A的示例中BIER-TE节点所采用的重置过程，消息位阵列与每个节点处的转发表条目的对比可以包括针对传入链路和外出链路的转发表条目。图3A的重置过程保证了到达节点的消息的MBA中没有位在对应于该节点的传入链路的位位置处被置位。

图3B示出了另一BIER-TE消息转发示例，这次针对GPT 214的多播组G2中的消息。组G2中的多播消息332以与以上针对组G1中的消息302所描述的相同方式被转发至入口节点A。消息332还以以上针对消息302所描述的方式进行封装，以形成BIER-TE消息334。消息334中的消息位阵列与节点A的BTFT条目的对比显示表示BTFT A中的链路并且还在消息位阵列中具有置位的唯一位位置是被分配给链路AE的位位置10。因此，节点A需要向节点E转发多播消息。首先节点A执行重置过程，如以上结合图3A所述，使得所形成的的消息338将位位置10重置。因为节点E不直接连接到节点A，因此消息338被路由至节点E。在一个实施例中，被转发至远程或间接连接节点的BIER-TE消息通过使用沿间接路径的节点处的单播路由表来进行路由。消息338被封装用于单播路由，从而形成到节点E的单播“隧道”。作为示例，在被配置用于MPLS单播路由的网络中，应用于消息338路由封装340可采用最上面的MPLS标签的形式，其中MPLS标签是由节点A的路由信息库(RIB)提供的、用于向节点E路由的标签。经封装的消息被转发至节点B，节点B根据最上MPLS标签将消息作为单播消息进行路由。在图3B的实施例中，假设MPLS方案采用倒数第二跳弹出(PHP)，使得单播MPLS标签在将消息转发至其到节点E的最后一条之前被移除。(在该实施例中还假设路径ABE由路由算法选择为从节点A到节点E的最短路径。)在较大网络中，实现BIER-TE使能节点之间的间接链路的单播路由隧道当然可以比图3B的示例中的隧道长得多。在图3B的实施例中，节点E接收BIER-TE消息338，因为隧道封装已针对从节点A到节点E的路径的最后一跳而移除。然后节点E如上所述进行BIER-TE转发。消息338中的消息位阵列与节点E的BTFT条目的对比显示表示BTFT E中的链路并且在消息位阵列中具有置位的位位置是分别分配给链路EF和EC的位位置5和6。在重置位5和6的重置过程之后，消息338被复制，并且副本消息340和342分别被转发至节点F和C。如以上结合图3A所述，在消息342由节点C转发之前，重置至少位6是重要的，否则节点C将会将消息再次发送回节点E。消息342中的消息位阵列与节点C的BTFT条目的对比显示消息342应被转发至节点D。重置过程引起位3被重置的消息346，消息346被转发至节点D。因为消息346在BP 9中具有置位位，因此其在节点D处被解封装并通过BIER-TE域外所使用的协议转发至接收者104。同时，消息340被节点F接收并根据其消息位阵列的位位置8中的置位位进行解封装。经解封装的消息344被转发至接收者106。

如图3B及以上相关描述所示，通过网络100中的BIER-TE域来转发组G2中的多播消息使得消息的副本经由到节点E的“松散”路径和从节点E到每个接收者的显式路径的结合而被递送至接收者104和106。BIER-TE中的直接连接链路和“松散”间接链路在某种程度上类似于已被描述用于分段路由的直接连接段(或“邻接段”)和间接路由段(或“节点段”)。然而，在重要的方面，分段路由与BIER-TE不同。例如，在当前定义的分段路由中，消息承载要被穿越的路径的每个段的标识符，并且标识符必须按照与段沿路径出现的相同顺序被安排。沿分段路由路径的节点通常只读取对应于该节点沿路径的位置的一个标识符。相反，在BIER-TE中，不需要分组承载任何位位置的特定顺序，只要消息位阵列与每个节点处的BIER-TE转发表中使用相同的位位置分配。因为每个BIER-TE节点在其转发表中仅具有分配有位位置、连接到该节点的链路，因此该节点可被呈现有包含表示沿整条路径或树的每条链路的位的位阵列，并且只挑选与该节点处的链路相关的位位置。实际上，在每个节点的BIER-TE转发表中仅存储相关链路建立了一种针对该路径或树的自组装过程，因为消息承载着反映整个树的位开始其旅程，但是随着消息(或复制消息)逐节点前进，这些位逐渐被用于建造该路径。

因为每个BIER-TE节点可以访问消息位阵列，该消息位阵列包含表示消息的路径或树的剩余部分中的所有链路的位，并且每个BIER-TE节点可以复制消息和通过连接到该节点的任何链路发送消息，因此可以使用BIER-TE进行多播传输。这与当前定义的分段路由相反，分段路由被限制于单播路径，因为一次只有一个路径段是节点可访问的。然而，在多播中能够使用BIER-TE来执行显式路径转发不意味着BIER-TE被限制于多播。以上讨论的转发示例澄阐明了BIER-TE位阵列还可被用于定义消息的显式单播路径。在一些实施例中，BIER-TE消息位阵列可比对分段路由实现方式中的相同路径进行编码所需的分段标识符集合提供对给定显式路径更紧凑的编码。

通过BIER-TE转发在某种程度上类似于通过非TE BIER转发，主要在于两种方法都在被转发的消息所承载的位阵列中编码路径信息，并且将消息位阵列与每个节点处的转发表中的位位置信息进行对比。因此，这两种方法允许转发节点不具有多播状态，例如针对多播组所存储的树信息。然而在这两种方法之间存在重要不同。作为一个示例，BIER-TE提供了显式路径和树，因为BIER-TE消息位阵列包括对应于树中每条链路的位。另一方面，在非TE BIER中，消息位阵列中的位对应于接收节点，并且MBA不承载显式路径信息。BIER和BIER-TE方法还在转发节点处执行的操作中有所不同。在BIER转发中，每个节点维护路由表，该路由表用于基于SPF做出对于哪些接收节点从该节点的邻居节点中的每一个可达的确定。从每个邻居可达的接收节点在每个节点处创建的位索引转发表中反映。另一方面，在BIER-TE节点中，转发表由外部控制器或手动配置所提供的信息来填充。至少在路径仅使用直接连接链路构成的情形中，BIER-TE使能节点不需要路由表或超出知晓其直接邻居之外的任何拓扑信息。在一些实施例中，BIER-TE使能节点不运行IGP。

BIER-TE中的位位置分配

与非TE BIER中的接收节点不同，BIER-TE中对网络链路的位位置分配允许定义显式路径和树，但仍需要相对较高的位位置数。BIER-TE中用于定义显式多播树的位数可能比使用非TE BIER向相同的接收节点创建非显式树所需的数量要高得多。因此，BIER-TE中的位位置分配应在使得所使用的位位置的数量最小化的情况下做出。首先，位位置仅对那些包括在显式路径或树中的链路是需要的，而不是对网络中的每条链路都是必需的。在一些实施例中，显式路径仅在消息所采取的总路径的一个或多个部分是需要的。如果存在网络部分不需要多播复制或流量工程，则该部分可被“绕过”(从BIER-TE实现的角度)，这是通过定义被绕过的部分的两侧的BIER-TE使能节点之间的间接链路(类似于图1-4所述的链路AE)来实现的。通过这种方式，只需一个位位置来穿过网络的该部分。在实施例中，间接绕过链路通过封装转发消息来实现，该转发消息要使用被绕过部分中的节点的单播路由表进行路由。这种类型的单播路由间接链路还用于绕过网络具有非BIER-TE使能节点的部分。

在一些实施例中，可避免位位置分配的另一情况是被配置为仅通过一条链路转发或以其他方式仅采取一个动作的节点。作为示例，图1-4的网络100的出口节点D和E中的每一个在其BIER-TE转发表中仅具有一条外出链路，本地解封装链路用于将消息传出BIER-TE域。这种类型的出口节点可被称为“叶子”节点。在一个实施例中，不是将位位置分配给这些本地链路中的每一个，而是节点D和E被配置为对接收到的BIER-TE消息进行解封装，并将其传递至下一更高协议层。在其他实施例中，仅具有一条外出链路的BIER-TE域的入口节点或核心节点被配置为通过该链路转发所有BIER-TE消息，而不向该链路分配位位置。然而，在BIER-TE域内通过链路转发消息而不向该链路分配位位置将阻止接收转发消息的节点基于位位置执行消息的接受检查。接受检查考虑将在下文进一步讨论。注意，图1-4中的节点E作为发送至接收者108的消息的出口节点，但也作为发送至节点C或出口节点F的消息的核心节点。因此，在节点E的BTFT中存在多条外出链路，并且位位置应被分配至这些链路中的每一个。

在BIER-TE网络中维护位位置的另一途径是在链路之间共享位位置，即，向BIER-TE域内的不止一个链路分配单个位位置。这种情况的一个示例由以上讨论的网络100的节点D和E示出：位位置6被分配给节点之间的双向点到点链路的两个方向。在很多情形中，单个位位置可被用于这种类型的双向点到点链路的两个方向。针对两个方向使用单个位位置通常需要使用位重置过程，如以上结合图3A和3B中的位位置6所讨论的。单个位位置可被分配给多条链路的另一情形是诸如网络100的节点D和F之类的出口节点的本地解封装链路。例如，与图1-4所示分配位位置8以用于节点F处的解封装，分配位位置9以用于节点D处的解封装不同，单个位位置(例如，位位置8)被分配作为两个节点以及网络中任何其他类似的出口节点的解封装链路。这种方法是对上述方法的替换，在上述方法中，没有位位置被分配给诸如网络100的节点D和F之类的出口节点。与以上方法相比，以一个额外位位置的代价，分配单个位位置以用于仅出口节点或叶子节点处的解封装具有以下优势：允许出口节点至少验证解封装是想要的，而不是将其配置为对无论什么的所有接收到的流量进行解封装。

图4A和4B示出了位位置可被共享的情形的额外示例。例如在图4A中，链路402、404和406是节点A和B之间的等价多路径(ECMP)点到点链路，从而形成一捆链路。单个位位置(BP 5)被分配给该捆链路的两个方向，如图4A由分配408所示，并使用图1的链路分配符号来表示。由给定BIER-TE消息使用的链路由转发节点使用ECMP算法来确定，该ECMP算法例如考虑消息报头中的熵字段和/或存储于转发节点的BTFT中的种子参数。因为该捆链路中的多条链路彼此构成替换路径，因此任何一个消息将仅穿过其中一条链路，并且相同的位位置可被用于每条链路。

可共享位位置的链路的另一示例是在路径或树中将不会串联的链路。这种情况的一个示例是图4B所示的双平面网络。图4B的网络410具有上层412和下层414。接入节点A和F确定给定消息穿过哪一层。因为各层是独立的，因此位位置5可通过分配416被分配给上层412的节点B和C之间的链路以及下层414中的节点D和E之间的链路。在一个实施例中，每个网络层均具有其自身的BIER-TE控制器以分配位位置和确定显式路径和树。在替换实施例中，单个BIER-TE控制器管理网络410的两个层。在一些实施例中，单层网络可被分成多个部分，使得在一个部分中的链路不与网络的另一部分中的链路包括在相同的路径或树中。在这样的实施例中，相同的位位置集合可被用于网络的每个部分中的BIER-TE分配。

图5A到5D示出了对于消息可被复制到连接到节点的所有链路的情形中，将单个位位置分配到多条路径的额外示例。在图5A的网络部分500中，节点A被配置为星形布置中的中心，其中到节点B到F中的每一个具有单向链路。在替换实施例中，链路是双向链路，其中在每个节点处采用位重置过程以防止消息来回反弹。如果流量意图从节点A发送至每个相连的节点，则单个位位置可被分配给所有辐条链路，如图5A中的位位置分配502所示。在该示例中，使用单个位位置节省了四个位位置。即使由节点A发送至所有相连节点的消息不是所有节点需要的，但发送一些不想要的消息鉴于所获得的位位置的情况下是可容忍的。对于网络部分500以及这里所描述的其他网络和网络部分，如果消息不是接收节点需要的，则在该消息的消息位阵列中对应于针对接收节点的链路的位置处不具有置位位。在这种情况下，不需要的消息将被丢弃。

图5B示出了网络部分500的节点A的示例性BIER-TE转发表部分510。在图5B的实施例中，BTFT部分510中的条目通过位位置号进行排序，并且仅示出了针对位位置5的条目512。在替换实施例中，完整链路位阵列以类似于图2所示的BTFT的方式被包括在表部分510中。条目512包括位位置5被分配给的五条链路。节点A的转发指令(或编码在BTFT的其他位置或是节点A的转发引擎中)要求来自节点A、其消息位阵列中的位5被置位的BIER-TE消息被转发至节点B、C、D、E和F中的每一个。在这里所示的所有转发表部分的情形中，BTFT A一般包括未示出的额外信息，例如节点接口标识符或额外转发指令。

将一个位位置分配给多条链路的另一示例被示于图5C中。网络部分520包括局域网(LAN)522，LAN 522具有相连的节点A、B、C和D，使得相连节点的每一个均与任何其他相连节点具有双向连接。节点之间的这些链路使用图5C中的虚线示出。如果去往相连节点中的一个的BIER-TE流量被发送至所有其他相连节点是可接受的，则相同的位位置可被分配给每个连接。在网络520中，位位置5被分配给相连节点之间的每条链路，如分配524所示。在图5C的实施例中，在连接到LAN 522的每个节点处的BTFT包括位位置5到该节点与其他相连节点之间的所有三条链路的映射。因为图5C的位位置分配是针对双向链路的，因此在每个节点处需要位重置过程来防止消息在节点之间来回反弹。使用单个位位置用于连接到LAN522的节点之间的六条链路节省了五个位位置。

当将单个位位置用于网络结构中的多条链路时，如果该结构与同样将单一位位置分配给多条链路的另一网络结构具有共同的节点，则可能出现困难。图5D中使用与图5C类似的LAN结构示出了示例，但类似的情况可出现在使用其他网络结构时，例如，星形结构。图5D的网络部分530包括图5C所示的LAN 522，除了节点D还连接到另一LAN(LAN 532)。以相同的方式，位位置5被分配给LAN 522的相连节点之间的所有链路，位位置6被分配给LAN 532的所有相连节点，如分配534所示。节点D的BTFT将相应地包括将位位置5映射到去往节点A、B和C的链路的条目，以及将位位置6映射至去往节点E、F和G的链路的另一条目。网络部分530还包括分别连接到LAN 522和532的节点A和E的节点S。在图5D的实施例中，节点S向节点A和E中的每一个转发消息536的副本。消息536的消息位阵列在位位置5和6中包括置位位，以使被转发至节点A的消息536的副本将通过位位置5到达LAN 522上的节点，并且转发至节点E的副本将通过位位置6到达LAN 532上的节点。

如果LAN 522和532未经由节点D连接，则对到达节点A和LAN 522的消息的消息位阵列中位6的设置将没有影响，并且对到达节点E和LAN 532的消息的MBA中的位5的设置也没有影响。然而，通过节点D桥接两个LAN，不仅节点D得到消息的两个副本(通过节点A和E中的每一个一个副本)，而且节点D将通过LAN 532接收到消息转发给LAN 522的节点，反之亦然。因此，桥接两个LAN的节点D的存在能够产生显著的消息重复。避免该重复的替换位分配被示于图5E中。图5E示出了与图5D具有相同拓扑的网络部分530，但对于到来消息的位位置分配和消息位阵列有所改变。分配540将位位置5映射到节点A、B和C之间的链路，而没有节点D。类似地，分配542将位位置6映射到节点E、F和G之间的链路，而没有节点D。节点D与连接到LAN 522的节点之间的链路被映射到位位置7，如分配544所示，并且节点D与连接到LAN532的节点之间的链路被映射到位位置8。在图5E的实施例中，消息548的副本由节点S转发至节点A和E。消息548的消息位阵列在位位置5、6和8处包括置位位，以使用位位置8(经由节点E)到达节点D，使用位位置5(经由节点A)到达LAN 522上的其余节点，使用位位置6(经由节点E)到达LAN 532上的其余节点。因为节点D没有链路被分配给位位置5或6，因此其不作为到任一LAN的“后门”入口。在替换实施例中，消息位阵列在BP 7而不是BP 8中具有置位位，以通过节点A而不是节点E到达节点D。只要位位置7或8中仅有一个位被置位，则节点D将不会得到重复的消息。图5E中的位位置分配针对12条链路使用了4个位位置，节省了8个位位置。

从图5D的位位置分配产生的避免重复的另一方法被示于图5F中。在该实施例中，位位置5被分配给连接到也示于图5D中的LAN 522的节点之间的所有链路。然而，在LAN 532上没有位位置被分配给涉及节点D的链路。因此，消息536将经由节点A到达节点D，而不经由节点E到达节点D。实际上，该位位置分配移除了节点D与LAN 532之间的连接，以用于BIER-TE转发。然而，节点D可由使用其他方法转发的消息通过LAN 532进行访问。

在由多条链路共享一个位位置的以上示例中，共享位位置的链路是不沿路径串联的替换链路。然而，在一些实施例中，位位置可被沿同一路径串联的链路共享。例如，如果存在若任何一个路由器接收消息则所有路由器应接收该消息(或至少可以接收该消息)的网络部分，则单个位位置可被分配给该网络部分中的每条链路(或实际上被分配给整个网络部分)。对网络部分的该位位置分配可被称为“拓扑邻接”。如果网络部分包括串联的链路，则被分配给该网络部分的位位置在转发时不被重置是重要的(否则消息将在单跳之后被舍弃)。然而，如以上结合一些示例所述，在一些实施例中，在转发时重置位位置失败可能导致消息循环和/或重复。在一个实施例中，将单个位位置用于沿多跳路径的多条链路限于采用单向链路的无环网络。

具有单向链路的无环网络示例被示于图6A中。图6A的网络部分600被分配位位置4，因为到来消息(例如消息604)意图到达节点D和E(通过节点B)以及节点F和G(通过节点C)中的每个节点。位位置4被分配给单向链路，如分配602所示。然而，位位置仅被分配给创建无环路径的那些链路。节点B和C之间的链路将创建环路，所以没有位位置被分配给该链路。因此，该链路不会出现在节点B和C的BIER-TE转发表中，并且没有消息将通过它进行发送。节点B和C之间的链路被有效移除以用于BIER-TE转发。在实施例中，节点A到G的每一个的BTFT包括位位置4将不被重置的指令。节点B的BTFT部分的示例示于图6B中。在图6B的实施例中，BTFT部分610通过位位置排序，并且仅包括外出链路。条目612包括对应于位位置4的节点B的两条外出链路：链路BD和BE。对于这些链路中的每条链路，条目612还包括BTFT部分610的重置列中的“否”指令，使得位位置4在穿过链路BD或BE的消息中不被重置。消息604的副本通过图6A的网络600转发，因此消息位阵列的位位置4中的位保持置位。

将单个位位置用于串联的多条链路的网络部分的另一示例是图6C的环状布置。图6C的网络部分620包括连接成环的节点A、B、C和D。顺时针方向从A到D、D到C、C到B的链路被分配位位置2，如分配622所示。逆时针方向从A到B、B到C、C到D的链路被分配位位置3，如分配624所示。所有位位置分配包括不重置经分配的位位置中的MBA位的指令。因为在节点B和A之间没有分配顺时针位位置，因此在其MBA中位位置2处具有置位位的消息将从节点A到D到C到B行进，然后停止而不继续沿环进行循环。类似地，节点D和A之间的逆时针链路没有位位置分配在逆时针方向“打破循环”。在其MBA中的位位置3处的位是置位位的消息626相应地从节点A到B到C到D行进，在节点D停止。网络620的节点B的BTF部分的示例被示于图6D中。在图6D的实施例中，BTFT部分630包括传入和外出链路。在该实施例中，表部分630通过位位置排序，其中条目632对应于位位置2，条目634对应于位位置3。针对位位置2，只有节点B的传入链路CB被包括在条目632中，反映了顺时针方向上B的外出链路没有位位置分配。

用于向网络中的链路分配位位置的方法示例由图7的流程图示出。在一个实施例中，图7的方法700由网络控制器执行。该方法开始于接收消息流信息(步骤702)。这里所使用的“流”是在具有一组共同属性的特定源和特定目的地之间传输的一个或多个消息的流。在一个实施例中，消息流信息包括多播组和/或源信息。或者，消息流信息涉及多播消息流，并且例如包括该流的入口和出口节点信息。在一个实施例中，消息流信息从网络的入口或出口节点接收。在替换实施例中，消息流信息通过手动配置过程接收。

方法700接着针对该流中的消息确定路径(步骤704)。如结合以上转发示例所讨论的，网络拓扑信息与消息流信息一起用来确定路径。除了针对其来确定路径的特定消息流之外，所考虑的消息流信息可包括关于网络中的附加消息流的信息。在一个实施例中，关于特定网络或应用的附加规则或要求也被用于确定路径。例如，在某些实施例中，本领域普通技术人员鉴于本公开所理解的各种流量工程考虑被用于确定路径。在一些实施例中，确定路径涉及通过手动配置过程来接收路径的条目。在实施例中，步骤704的路径确定提供了初始路径定义，该初始路径定义可随着方法700的进行而变化和/或重新定义，并且位位置被分配。

在步骤706，本地解封装位位置被分配给针对消息流的路径或树上的一个或多个出口节点。这些是与图1的分配138类似的位位置分配。在一个实施例中，单独的位位置以图1的分配138的方式被分配给每个出口节点。在另一实施例中，单个位位置被分配给多个出口节点处的本地解封装链路，如以上对于共享位位置的讨论中所述。(一个或多个)经分配的位位置到其相应链路的映射被存储于控制器处，或存储于控制器可访问的位置处(步骤708)。在一个实施例中，位位置映射被存储于路由表中，该路由表被配置为存储用于填充沿路径或树的各节点处的转发表的信息。除了被存储以供控制器访问，位位置映射还被存储于连接到所涉及的链路的节点的转发表中。在步骤706的本地解封装位位置分配的情形中，位位置到本地解封装链路的映射被存储于执行该解封装的(一个或多个)出口节点的转发表中。在一个实施例中，对于在对应于本地解封装链路的位位置处具有MBA置位位的消息进行解封装的指令也被存储于出口节点处的转发表中。在替换实施例中，出口节点处的转发表将位位置映射至链路，该链路以某种方式被标识为本地解封装链路，并且针对如何处理这样的链路的具体指令被编码于别处(例如，出口节点的转发引擎中)。方法700的步骤706和708描述了向出口节点处的本地解封装链路分配位位置的子方法。该子方法是可选的，并且位位置分配方法中的一些实施例不包括该子方法。例如，在一些实施例中，出口节点被配置为对所有到达的消息进行解封装，使得本地解封装链路不被分配任何位位置。

在方法700的步骤710中，确定沿消息流的路径的一对节点是否由一捆ECMP链路连接。在一个实施例中，该确定是使用网络的拓扑信息做出的。这种类型的一捆链路的示例被示于图4A中。在方法700的实施例中，如果在一对节点之间存在一捆ECMP链路，则单个位位置被分配给该捆链路(步骤712)。以上文结合步骤708所述的方式，位位置到该捆链路的映射被存储以供控制器访问(步骤714)。位位置映射还被存储于连接到该捆链路的节点中的一个或两个的转发表中(步骤714)。在转发表通过位位置排序的实施例中，针对被分配给该捆链路的位位置的转发表条目将该捆链路中的所有ECMP链路标识为分配该位位置。如果ECMP链路是单向链路，则所分配的位位置到ECMP链路的映射被包括在这些链路的发送节点处的BIER-TE转发表中。如果ECMP链路是双向链路，则位位置到这些链路的映射被包括在每捆链路处的BTFT中。在一些实施例中，位位置到传入链路以及外出链路的映射被包括在(一个或多个)适当的转发表中。方法700的步骤710、712和714描述了在一对节点之间检查以及向一捆ECMP链路分配位位置的子方法。该子方法是可选的，并且位位置分配方法中的一些实施例不包括该子方法。例如，在替换实施例中，单独的位位置被分配给各ECMP链路。在另一实施例中，编码路径或树的替换消息位阵列被建立，每一个使用替换ECMP链路中的一个。在这样的实施例中，ECMP算法可被应用到入口节点处，以选择使用哪个替换消息位阵列来对到来消息进行BIER-TE封装。

方法700继续到步骤716，在步骤716确定是否存在路径或树穿过的网络部分，对于该网络部分，所有节点能够接收正在转发的消息的副本。在一个实施例中，所识别的网络部分是所有节点需要接收消息的网络部分。在其他实施例中，该网络部分是这样的网络部分：其中鉴于通过向多条链路分配一个位位置从而节省位位置的机会，节点中足够的节点需要接收消息(该消息的一些重复对于其他节点是可容忍的)。如果网络部分被识别，则在步骤718确定所识别的网络部分是否包括替换路径上的链路(即，不沿路径串联的链路)。这种类型的网络部分的示例包括图4B所示的双平面网络、图5A的星形配置以及图5C到5F的LAN配置。如果网络部分不包括替换路径上的链路，则单个位位置以类似于这里对以上列出的示例的讨论中所描述的方式被分配给替换链路中的一个或多个(步骤720)。与以上结合步骤708和714所描述的方式类似，经分配的位位置到相应链路的映射被存储以供控制器访问(步骤728)。位位置映射和任何适当的指令也被存储于每条链路的源节点的BIER-TE转发表中(步骤728)。在替换链路是双向链路的实施例中，链路每一端的节点是该链路一个方向上的源节点，因此在其转发表中包括针对经分配的位位置的链路。图7的流程图中由方法700的步骤716、718、720和728构成的循环表示检查和向替换路径上的链路分配位位置的子方法。该子方法是可选的，并且位位置分配方法的一些实施例不包括该子方法。例如，在步骤716、718、720和728的方法不执行的实施例中，单独的位位置被分配给网络部分内的各链路。

返回到方法700的步骤718，如果所有节点能够接收消息副本的网络部分不具有串联的链路(判断718的“否”分支)，则位位置仅被分配给沿非循环路径的单向链路(步骤722)。这种类型的位位置分配的一个示例被示于图6A中并在上文的相关讨论中进行了描述。如果网络部分在环状配置中(判断步骤724)或希望在两个方向上穿过链路来发送消息的任何其他配置中，则单独的位位置被分配至反向的单向链路(步骤726)。如上文结合图6A和6C所讨论的，任意方向的消息路径需要是非循环的，因为在消息被转发穿过具有相同位位置分配的串联路径时位位置未被重置。在一个实施例中，通过不向任何可能创建环路的链路分配位位置来避免循环。与以上结合步骤708、714和728所描述的方式类似，链路到经分配的位位置的映射被存储以供控制器访问(步骤728)。位位置映射和任何适当的指令也被存储于每条单向链路的源节点的BIER-TE转发表中(步骤728)。在一个实施例中，不重置经分配的位位置的指令也被包括在每条单向链路的源节点的BTFT中。图7的流程图中由方法700的步骤716、718、722、724、726和728构成的循环表示检查和向路径上串联的链路分配位位置的子方法。该子方法是可选的，并且位位置分配方法的一些实施例不包括该子方法。例如，在不执行该子方法的实施例中，单独的位位置被分配给网络部分内的各链路。

方法700继续到判断步骤730，其中确定是否存在穿过路径或树的消息可绕过的网络的一个或多个部分。在该上下文中，“被绕过的”网络部分是使用传统单播路由穿过的部分，使得通过该部分所采取的显式路径不是使用BIER-TE确定的。一般而言，从BIER-TE的角度可以绕过的网络部分是未发生消息复制的区域以及不以其他方式要求特定链路或节点穿过的区域。换言之，如果消息通过其来穿过网络部分的特定路径是不重要的，则该网络部分可被绕过。如果存在这样的网络部分，则在方法700的实施例中，通过向穿过该网络部分的间接链路分配位位置来绕过这样的网络部分(步骤732)。该间接链路的示例是图1到3B的网络100中的链路AE，但是间接链路当然可以包括比链路AE长得多的路由路径。与以上结合步骤708、714和728所描述的方式类似，经分配的位位置到间接链路(通常到单播路由路径的端节点)的映射被存储以供控制器访问(步骤734)。位位置映射和任何适当的指令也被存储于间接链路的每一端处的节点的BIER-TE转发表中。例如，在一个实施例中，用于封装消息以供单播路由的指令和/或信息被存储于间接链路的起始节点处的BTFT中。在替换实施例中，封装指令中的一些或全部被编码于起始节点的转发引擎中。类似地，在一些实施例中，用于移除单播路由封装的指令和/或信息被包括在间接链路的终止节点处的BTFT中。在单播封装在单播路由的最后一跳之前被移除(例如，以上结合图3B描述的具有PHP的MPLS)的实施例中，解封装指令在终止节点处可能是不需要的。方法700的步骤730、732和734描述了检查不需要显式路由的网络部分并向穿过该网络部分的绕过路径分配位位置的子方法。该子方法是可选的，并且位位置分配方法的一些实施例不包括该子方法。在不执行该子方法的实施例中，位位置被分配给消息路径的长度中直接相连的链路。

如果在上述分配之后，在针对消息流的路径或树中还存在尚未被分配位位置的链路，则这些链路中的每个被分配额外的位位置(步骤736)。这些位位置分配针对直接连接的链路，并且与图1的位位置分配134和136类似。这些剩余位位置分配可以是双向链路、单向链路或二者的组合。与以上结合步骤708、714、728和734所描述的方式类似，链路到其经分配的位位置的映射被存储以供控制器访问(步骤738)。位位置映射还被存储于连接到每条链路的一个或两个节点的转发表中。如果链路是单向链路，则经分配的位位置到每条链路的映射被包括在该链路的源节点处的BIER-TE转发表中。在位位置被分配给双向链路的实施例中，链路的每一端处的节点在该链路的一个方向上是源节点，因此在其转发表中包括经分配的位位置的链路。在一些实施例中，位位置到传入链路和外出链路的映射被包括在(一个或多个)适当的转发表中。

当位位置已被分配给相组合以形成针对消息流的整个路径或树的链路时，消息流的消息位阵列被生成和存储(步骤740)。根据这里所使用的位惯例，消息位阵列在对应于该路径或树中的链路的每个位位置中包括置位位。在一个实施例中，消息位阵列和消息流的地址或标识符之间的映射被存储于针对消息流的BIER-TE入口节点处的组路径表或流路径表中。位位置分配和消息位阵列生成过程(例如方法700的这一过程)针对由BIER-TE网络或域转发的每个消息流执行。

图7的方法700示出了用于BIER-TE位位置分配的各种考虑和过程。方法700示出了一个实施例，并且很多其他变化是可能和被预期的。例如，如上所述，方法700内的很多子方法是可选的并且在一些实施例中不执行。位位置分配方法的替换实施例可以不包括这些子方法，或其中之一，或任意两个子方法的组合，或任意三个子方法的组合或任意四个子方法的组合。此外，在其他实施例中，方法700的子方法被执行的顺序可以不同。此外，虽然在方法700中，在分配了每种类型的位位置之后，位位置分配被存储于BIER-TE节点处的适当的转发表中，但是在其他实施例中，每次在分配过程结束时向BIER-TE节点传输位位置分配，或在该过程中以不同间隔传输位位置分配。

虽然在方法700中被示为分离的步骤，但是注意，针对消息流的路径或树的确定和向路径内的链路分配位位置在一些实施例中可以是相关的过程。例如，诸如判断步骤730的对于网络部分是否可被绕过的询问可构成确定路径本身的过程的一部分。位位置分配方法(例如方法700)的一些或全部在一些实施例中可作为优化过程的一部分进行重复，以达成路径或树定义和相应的位位置分配集合。

位位置分配方法(例如图7的方法700)的一些或全部可被用于除了做出初始位位置分配之外，还生成改进的位位置分配。BIER-TE网络内的位位置分配可能需要被改变，原因包括网络改变或消息流路径改变。一般而言，BIER-TE网络的拓扑改变而位位置分配或消息位阵列不变可使得一些消息被舍弃。然而，这种情况不应引起消息循环或重复，因为任何在拓扑中导致循环的新链路尚未被分配位位置，因此BIER-TE消息不会通过新的链路转发。对位位置分配和消息位阵列中的路径的编码的改变应小心进行，以保证消息不创建循环或不能接受的重复。

用于更新位位置和消息位阵列的方法的实施例由图8的流程图示出。在实施例中，图8的方法800由网络控制器执行。方法800开始于分配新的位位置(步骤802)。新的位位置分配的示例由图9A和9B示出。图9A示出了具有类似于上文图5A的星形布置的网络部分900，除了新的节点G被添加到该布置。在网络添加节点G时，位位置5分别被分配给节点A和节点B到F之间的链路。如图9A所配置的BIER-TE网络的继续操作将不涉及节点A和节点G之间的链路，因为没有位位置被分配给它。分配新的位位置以合并节点G的示例由图9B示出。图9B示出了将位位置8分别分配给节点A和节点C到G之间的链路的新的位位置分配904。在图9B的实施例中，新的位位置8未被分配给链路A和B之间的链路。对于通过相同的位位置从连接到节点A的节点组中移除节点B的决定可例如由接收者从节点B是否可达的改变来引发(假设网络部分900中的节点具有到更广网络的额外连接(未示出))。对于预先存在的位位置5到一些链路的分配被维护，使得一些链路具有两个经分配的位位置。

返回到方法800，新的位位置分配被添加到受影响的节点的BIER-TE转发表中，而先前的位位置分配也被保留在表中(步骤804)。BIER-TE转发表反映新的位位置分配的示例在图9C中示出。图9C示出了网络部分900的节点A的BTFT部分910。在图9C的实施例中，BTFT通过位位置排序并且仅包括外出链路。条目912包括位位置5分别到从节点A到节点B到F的五条链路的映射。条目914包括新分配的位位置5分别到从节点A到节点C到G的链路的映射。在BTFT部分910包括条目912和9142者期间，通过节点A发送的消息穿过哪些链路取决于消息所承载的消息位阵列是否在位位置5或位位置8中具有置位位。

在方法800的实施例中，当步骤804执行时发送的任何消息承载消息位阵列，该消息位阵列反映先前存在的位分配。因为先前的位分配在步骤804后保留于转发表中，因此这些消息仍可通过任何仍作用的原始链路进行转发。然后，被新的位位置分配影响的任何消息流的消息位阵列被改变以反映新的分配。然后消息开始使用新的消息位阵列进行转发(步骤806)。被取代的位位置分配(例如图9A中位位置5的分配902)最后从受影响的节点的转发表中移除(步骤808)。此时，先前位位置已被“重新声明”，并且在下次需要新的位位置分配时可用于分配给一些其他(一个或多个)链路。

在一个实施例中，方法800包括认真检查以保证新的位位置分配不会产生循环或不能接受的重复量。方法800的顺序处理和两个位位置到某些链路的临时分配允许位位置分配之间的转换逐渐且小心进行。在一个实施例中，如果在反映新分配的消息流量开始流送之后足够快地发现新分配的问题，则转发消息的消息位阵列可变回原始形式，以反映先前的位位置分配。

重置和接收过程

如图3A和3B的转发示例所示出的，在一些实施例中采用位重置过程。当经由被分配至单个位位置的双向链路转发BIER-TE消息时，尤其需要重置过程。然而，在一些情况下，与路径内的链路相对应的位位置中的位应当被重置，例如如结合图6A和6C所讨论的。如以上关于图3A的讨论中所提到的，实现重置过程的一种方法是使用重置掩码。重置掩码可以被设计以针对其中位应当或不应当被重置的位位置负责。图10A的流程图示出了用于创建重置掩码的方法的示例。在一个实施例中，一旦转发节点处的BIER-TE转发表已经使用从BIER-TE控制器接收到的信息被填充，诸如图10A的方法1000之类的方法可以由每个转发节点处的转发引擎执行。在另一实施例中，方法1000由BIER-TE控制器执行，并且重置掩码连同BIER-TE转发表信息一起被提供给每个BIER-TE节点。图10A的方法1000可尤其适用于包含位位置号但不一定包含全链路位阵列来表示位位置的BTFT。

图10A的方法1000开始于创建位掩码(或位阵列)，该位掩码的长度与用于网络中的BIER-TE分组的消息位阵列的长度相同，其中位掩码最初使所有的位置位(步骤1002)。由于本公开中所用的编号规定，因此位掩码使得所有的位开始时被置为“1”。方法前进到访问节点的BTFT中的条目(步骤1004)，其中节点的BTFT将位位置映射到链路。如果条目包括不重置位位置中的位的指令(判断步骤1006)，该条目不被用于制作重置掩码。在这种情况下该方法将移向被映射到BTFT中表示的链路的另一位位置的条目(判断步骤1006和1010的“是”分支；步骤1012)。如果条目不包括不重置的指令，通过对位掩码中相应的位置处的位进行重置判断，该位位置被包括在重置掩码中(判断步骤1006的“否”分支；步骤1008)。然后针对被映射到BIER-TE转发表中的链路的任何剩余的位位置重复该过程。当所有的位位置已经被处理时，位掩码包括与BTFT中的链路相对应的位位置中的重置位，或者置位位。该位掩码作为重置掩码被存储在节点处(步骤1014)。重置掩码在重置过程期间通过在重置掩码和消息的消息位阵列之间执行逻辑与来被应用。这导致与BTFT中的链路相对应的位位置中的MBA位被重置(如果还未被重置)。

如图10A中所示出的方法1000不对传入链路和外出链路进行区分。重置掩码中包括与BTFT中的所有链路(除了那些具有“不进行重置””指令的链路)相对应的位位置导致针对紧在转发消息之前被执行重置过程的重置掩码，本文中被描述为“基于发送的重置(reset-on-send)”过程。BTFT将总是包括来自节点的外出链路的位重置映射，并且还可以包括传入链路。外出链路的位位置需要被包括在用于即发即重置过程的重置掩码中，并且针对传入链路的位位置也可以被包括在该重置掩码中而不影响操作。以上图3A和3B的转发示例包括即发即重置过程。在替代实施例中，仅外出链路在使用诸如方法1000之类的方法创建的重置掩码中被表示。这种实施例还产生也适用于“基于发送的重置”过程的重置掩码。

在另一实施例中，在使用诸如方法1000之类的方法创建的重置掩码中仅传入链路被表示。仅在与传入链路相对应的位位置处具有位重置的重置掩码适于在消息在节点处被接收之后并在所接收的消息的消息位阵列与节点的BTFT中的条目对比之前被执行以确定消息接下来去向哪里的重置过程。这种类型的重置过程在本文中被称为“基于接收的重置基于接收的重置(reset-on-receive)”过程。基于接收的重置过程的优点在于到达节点处的消息仍然在与消息通过其到达的链路相对应的位位置中置位了MBA位。这允许接收节点通过验证消息位阵列在与到节点的适当的传入链路相对应的位位置中的位被置位来执行消息的接收检查。参考图3A示出，所示出的基于发送的重置过程不允许节点处的输入消息的接收检查。考虑从节点A到节点B的链路，例如，该链路被分配位位置1，如BTFT部分202中所示出的。然而，从节点A发送到节点B的消息308在它的MBA的位置1中不具有置位位，因为该位在消息离开节点A之前被基于发送的重置过程重置。对于将被采用的基于接收的重置过程，节点处的BTFT需要包括到节点的传入链路和外出链路二者。

在图10B中示出供示例转发表使用的重置掩码的实施例。除BTFT部分1020还包括重置掩码实施例之外，转发表部分1020与图3A的节点E的BTFT部分210相同。在图10B的示出中，重置掩码被包括在BTFT部分1020之内并被放置在转发表的链路位阵列之下，以易于对比。在替代实施例中，一个或多个重置掩码可以被存储在BIER-TE转发表的与图10B中所示出区域不同的区域中，或重置掩码可以被存储在BTFT之外的位置处。重置掩码被包括在BTFT部分1020的三个条目中。条目1022具有供基于接收的重置过程中使用的重置掩码。条目1022的重置掩码与BTFT中的链路位阵列的对比显示重置位仅在被分配到传入链路BE、CE和AE的位位置中出现在重置掩码。条目1024和1026包括用于基于发送的重置过程的重置掩码。这些重置掩码与BTFT中的链路位阵列的对比显示条目1024中的重置掩码在外出链路EF、EC和E(本地)的位位置中具有重置位，而条目1026中的重置掩码在BTFT中的所有链路(输入和输出)的位位置中具有重置位。

因为BTFT部分1020是图1到3B的网络100中的节点E的BIER-TE转发表，并且因为图3A和3B的转发示例采用基于发送的重置过程，在转发示例中将图10B的条目1024和1026的重置掩码中的任一者应用到节点E处的传入消息都应当导致来自节点E的传出消息。在图3A的示例中，到节点E的传入消息具有消息位阵列{0001 1101 0000}。通过执行移位与操作将图10B的条目1024的重置掩码应用到该消息位阵列导致新的消息位阵列{0001 10000000}，因为消息位阵列的位位置5、6、和7中的任何置位位被与操作用重置掩码中的那些位置中的零重置。该产生的消息位阵列确实与图3A中的现有节点E中示出的消息320的MBA相匹配。将图10B的条目1026的重置掩码应用到传入消息314的MBA同样导致新的消息位阵列{0001 1000 0000}。条目1026的重置掩码在与条目1024的掩码中相同位位置处包括零，并且1026的掩码中额外的零(在BP 4和10中)没有影响，因为传入消息314的MBA的那些位置中的位由于在前节点(节点C)处的基于发送的重置过程已经被重置。类似的测试可使用图3B中的节点E的传入消息338和传出消息340来执行，以显示条目1024和1026的重置掩码中的任一者可以被应用于消息338的MBA以产生消息340的MBA。

图10C的流程图示出节点处的传入消息的接受检查的方法的示例，该方法与基于接收的重置过程相结合。在实施例中，图10C的方法1030由BIER-TE节点处的转发引擎执行。方法1030开始于在节点处接收BIER-TE消息(步骤1032)并访问所接收的消息的消息位阵列以检查与该节点处的BTFT中的传入链路相对应的位位置处的位值(步骤1034)。特别地，方法测试在传入消息的MBA中与BTFT中所表示的传入链路中的一者相对应的位位置处是否有置位位(判断步骤1036)。如果MBA中没有位在与该节点的传入链路相对应的位位置处被置位，消息被认为被不正确地接收并被丢弃(判断1036的“否”分支；步骤1038)。

如以上所表示的，如果基于发送的重置过程已经在传入消息所通过的在前节点处被执行，基于消息位阵列中与传入链路相对应的位位置处的置位位的接受检查将不进行。在图10C的实施例中，对于通过接受过程的消息，方法1030继续基于接收的重置过程(判断1036的“是”分支；步骤1040)的执行。在对其来说重置过程重要的实施例中(例如，具有单个分配的位位置的双向链路)，重置需要作为转发过程的一部分在传入消息位阵列被与BTFT条目对比之前被执行。这样，与不应当被再次穿过的链路相对应的置位位将在转发过程确定消息接下来应当穿过那些链路之前被重置。

步骤1040的基于接收的重置过程对所接收到的消息的MBA中的、在与节点处的BTFT中的传入链路相对应的位位置中的位进行重置。重要的是，在BIER-TE转发过程在该节点处被执行之前，在与外出链路相对应的位位置中的位此时不被重置。基于接收的重置过程可以使用仅反映传入链路的位位置的重置掩码来实现，类似于图10E的条目1022中的重置掩码。消息位阵列与这种重置掩码的逐位与运算将使适当的位重置。使用由诸如本文的图10A和10D中的那些方法之类的方法创建的重置掩码的优势在于，具有“不重置”指令的位位置已经负责创建重置掩码。在替代实施例中，在与传入链路相对应的位位置中的位通过不同的位运算过程被重置，如本领域技术人员基于本公开所理解的。然而，如果位被不同的过程重置，应当针对“不重置”指令检查BTFT条目，使得不应当被重置的位不被重置。在基于接收的重置过程之后，方法1030继续BIER-TE转发过程(步骤1042)，如联系例如上面的图3A和3B所讨论的并将在下面进一步讨论的。

图10D的流程图示出创建重置掩码的替代方法1000。如图10A的方法1000一样，在一些实施例中图10D的方法可以由BIER-TE节点处的转发引擎执行，在其它实施例中由BIER-TE控制器执行。图10D的方法1050可以尤其适于结合BTFT使用，该BTFT包括完整的链路位阵列，每个位位置分配给表中所表示的链路。然而，在仅包括位位置号的BTFT的情形中，链路位阵列可以被生成以用于方法1050的目的。在图10D的实施例中，方法1050开始于访问所希望的类型的链路的条目(步骤1052)，该条目被包括在节点处的BTFT中。条目被访问的链路的类型取决于为其创建掩码的重置过程的类型。如果重置掩码是用于基于接收的重置过程，步骤1052中所访问的条目是仅包括到节点的传入链路的条目。另一方面，如果重置掩码是用于基于发送的重置过程，步骤1052中所访问的条目包括来自节点的外出链路。

方法1050接着确定被访问的BTFT条目是否包括不重置位位置中与条目相关联位的指令(判断步骤1054)。如果条目包括不重置位位置中的位的指令，该条目不被用于制造重置掩码。在这种情形下方法将移向被映射到BTFT中所表示的链路的另一位位置的条目(判断步骤1054和1062的“是”分支；步骤1064)。如果条目不包括不重置的指令，方法接着确定用于重置掩码创建目的工作位掩码是否已经被建立(判断1054的“否”分支；判断步骤1056)。如果工作位掩码还未被建立，当前条目的LBA被指定为工作位掩码(判断1056的“否”分支；步骤1058)。方法然后接着看是否有更多的位位置被映射到转发表中表示的希望类型的链路(步骤1062)，并且如果是这样，移向下一链路的条目(步骤1064)，在该点处方法针对下一条目重新开始。

如果工作位掩码已经被建立，逐位逻辑或在工作位掩码和当前BTFT条目的链路位阵列之间被执行，并且结果被存储为新的工作位掩码(判断1056的“是”分支；步骤1060)。方法然后继续，以看是否有更多位位置被映射到转发表中所表示的所需类型的链路(步骤1062)，并且如果是，移向下一链路的条目(步骤1064)，在该点处方法针对下一条目重新开始。当映射到所需类型链路的所有位位置已经被处理时，工作位掩码的每一位被反转，并且结果被存储为重置掩码(判断1062的“否”分支；步骤1066)。该方法具有针对对被映射到BTFT中所需类型链路(传入、传出或二者)的每个位位置将链路位阵列“或”在一起并然后将结果进行反转的效果。这导致除了位位置中与所需类型的链路相对应的那些位(其被重置)之外所有的位被置位的位掩码。

图10A和10D中的方式仅是重置掩码生成方法的示例，多种替代和变化是可能的。在图10D的实施例中，例如，制造重置掩码中所包括的链路的每个链路位阵列可首先被逐位反转，并且所得到的位阵列可以通过逻辑与运算被合并。此外，位重置过程可以在根本不使用重置掩码的情况下被执行。

位重置过程的另外的应用是作为“打破”网络部分中的环路的替代方式，其中单个位位置被分配给串联连接的多个链路。考虑到例如上文所讨论的环形结构以及图6C，避免环路形成的一种方式是不向将闭合环路的链路分配位位置(如图6C中所示出的)。在替代实施例中，位位置被分配给每个链路，但是该位置中的位在消息通过将闭合环路的链路被转发之前被重置。在图6C的环路中，例如，位位置2可以被分配给链路BA(以顺时针方向)并且位位置3可以被分配给链路DA(逆时针方向)。然而，控制器将向适当的节点提供指令，使得沿环路顺时针行进的消息的位位置2中的位在消息被从B转发到A之前被重置，使得消息停在B处。类似地，逆时针行进的消息的位位置3中的位在消息被从D转发到A之前被重置，使得相同的位位置可以被用于沿路径的连续的链路，如上面关于图6A-6D的讨论中所提到的。如果基于接收的重置过程被使用，BP 2中的位将在节点B处被重置，BP 3中的位将在节点D处被重置。如果基于发送的重置过程被使用，则两种位置中的位将在通过路径的最后的链路发送消息之前在节点C处被重置。在一个实施例中，BIER-TE控制器向BIER-TE节点提供是否使用重置过程的指令，并且如果是，使用什么类型的重置过程(例如，基于发送的重置或基于接收的重置)。

BIER-TE转发方法

示出本公开中所描述的BIER-TE转发过程的示例的流程图在图11A和11B中被示出。图11A的流程图是针对在BIER-TE入口节点处实施的方法的。方法1100从接收诸如分组、帧、或数据报之类的消息开始(步骤1102)。消息当由入口节点接收时还不是BIER-TE消息。在方法1100的实施例中，检查将接收到的消息的消息流映射至BIER-TE消息位阵列的路径表(步骤1104)。在一个实施例中，接收到的消息是在它的封装中包括多播组和/或源信息的多播消息，并且路径表是类似于图2的表214的组路径表。在可替代的实施例中，消息是流量工程想要的单播消息流，并且BIER-TE消息位阵列信息被映射至存储在入口节点处的流路径表中的消息流。在另一实施例中，单播消息流被在流路径表中使用IP源和目的地地址信息识别。在另一实施例中，BIER-TE网络中的消息流的入口节点信息和出口节点信息被用来识别单播消息流。在另一实施例中，消息流(无论是单播还是多播)被在流路径表中使用网络流协议(例如，思科系统公司开发的NetFlow、或由互联网工程任务组(IETF)指定的互联网协议流信息导出(IPFIX)、或基于这样的协议的应用)识别。

处于方法1100的目的，它假定传入消息是在入口节点处的路径表中表示的消息流和/或多播组的一部分。因此消息位阵列(MBA)被获得，并且消息被封装为承载MBA的BIER-TE消息(步骤1106)。如前面结合例如图3A的消息304所讨论的，可以以各种方式(包括建立专用的BIER-TE报头或扩展诸如MPLS或IPv6之类的现有封装)完成BIER-TE封装。一旦接收到的消息针对BIER-TE被封装，入口节点执行类似于上面结合图3A和3B所描述的转发过程。在方法1100的实施例中，用于将BIER-TE消息中的消息位阵列与BIER-TE转发表(BTFT)中的条目进行对比的机制考虑消息的MBA中的每个置位位，并且检查将置位的位位置映射至由节点使用的链路的BTFT条目。如下面进一步讨论的，该对比还可以以其他方式被排序。如果接收到的消息的消息位阵列中不存在置位位，则图11A的方法1100结束(判断步骤1108的“否”分支)。

当接收到的消息的MBA中存在至少一个置位位时(作为典型的情况)，针对将MBA中的置位位的位位置(BP)映射至外出链路的条目检查转发节点(在方法1100的情况下，BIER-TE入口节点)处的BTFT(判断1108的“是”分支；步骤1110；决定步骤1112)。在一些BTFT实施例中，存在每个位位置的条目，但是不是每个条目都包括映射至该位位置的链路。在其他实施例中，BTFT仅具有针对映射至在节点处的链路的那些位位置的条目。在任一种情况下，针对将MBA中的当前考虑的置位的位位置映射至外出链路的条目检查BTFT。处于方法1100的目的，将“本地”或“解封装”链路视为外出链路。如果在BTFT中不存在被映射至置位的位位置的外出链路，则方法继续进行到MBA中的下一个置位位，如果存在一个外出链路，则重复查询(判断1112的“否”分支；判断步骤1140的“是”分支)。

如果在BTFT中存在被映射至置位的位位置的外出链路，则方法1100接着从BTFT条目读取链路的接收节点(判断1112的“是”分支；步骤1114)。参考图11C可以更好地理解方法1110的这个步骤和其他步骤，图11C示出了可以适于方法1110的实施例使用的格式中的BTFT部分的示例。类似于图10B的BTFT部分1020，图11C的BTFT部分1196是图2、3A、和3B中示出的网络100的节点E的BTFT的变型。在图11C的实施例中，BTFT部分1196具有用位位置排序的条目，并且仅包括将位位置映射至连接到节点的链路的这些条目。替代列用双字格式表示每个链路(如在图2的BTFT部分210中所包括的)，BTFT 1196针对在每个链路的两端处的“发送节点”和“接收节点”适当地使用单独列表示链路。在将位位置7映射至节点E的本地/解封装链路的条目的情况下，在表中所提供的针对该链路的“接收节点”是在节点E(解封装的消息被传递至该节点E)处的外部的(BIER域外部)或上层的协议。在一个实施例中，具体协议(例如，IPv4、IPv6、或以太网等等)的标识符被包括作为本地解封装链路的“接收节点”。外部的或上层的协议还可以被称为“下一个协议”。在图11C的实施例中，BTFT 1196包括到节点E的传入链路，每个传入链路将节点E作为接收节点。接收节点也可以被称为邻居节点或邻居(特别是在直接连接的单跳链路的情况下)。返回图11A的方法1100，映射至置位的位位置的外出链路的接收节点的读取(按步骤1114进行)在通过如图11C的BTFT 1196中示出的读取接收节点的实施例中被实现。

方法1100接着在步骤114中确定是否存在到读取的接收节点的多个ECMP链路(判断步骤1116)。这是确定消息的路径是否包括ECMP捆(例如上面结合图4A所讨论的)。在一个实施例中，这样的捆可以在BTFT(例如图11C的)中作为映射至具有相同的发送节点和接收节点(但是每个节点连接至BIER-TE节点的不同接口)的多个链路的单一位位置出现。在图11C的实施例中，BTFT部分1196包括节点E的每个BIER-TE链路被连接的接口的列。例如，从节点E到节点F的被映射至位位置5的链路被连接至节点E的接口3，其中图2中示出了网络100的BIER-TE域中的接口3和其他接口的指定。在BTFT部分1196的实施例中，供链路到直接连接的BIER-TE节点的接口被包括在BTFT中，而由不同协议使用的接口被存储在例如使用该协议的单播转发表中。在替代的实施例中，例如，在向接收器转发解封装的BIER-TE消息中或在经由路由间接链路通过隧道转发BIER-TE分组中由不同协议使用的一些或所有接口也被存储在节点的BTFT中。转向方法1100，如果存在ECMP捆，则ECMP算法被用来选择捆中的链路中的一个(判断1116的“是”分支；步骤1118)。

方法1100接着链路的接收节点复制消息(步骤1120)。如果链路是解封装链路，则BIER封装被移除并且消息被传递至下一个协议层(判断步骤1122的“是”分支；步骤1124)。这需要照顾该链路的转发，并且方法移动至查看是否存在更多被映射至相同位位置的链路(接收节点)(判断步骤1138)。另一方面，如果链路不是解封装链路，则确定是否将要使用基于发送的重置过程(判断1122的“是”分支)。在一个实施例中，重置过程是否将被使用以及使用何种类型的过程由BIER-TE控制器确定并且被通信至BIER-TE节点。此信息在这样的实施例中可以被存储在每个节点处的BTFT中或被存储在节点处的任意位置。因为方法1100在BIER-TE入口节点处进行从而接收到的消息还不是BIER-TE消息，所以方法1100中不考虑基于接收的重置过程。在图11C的实施例中，BTFT包括哪些位位置需要被重置(例如被分配至双向链路的BP 6)以及哪些位位置不要被重置(例如上面结合图6A和6D所讨论的那些)的信息。在一个实施例中，建立执行重置过程的默认，并且重置掩码被使用，以便不要被重置的位位置可以被从过程中排除。在另一实施例中，控制器建立针对特定定时执行重置过程(基于发送的重置过程或基于接收的重置过程)的默认。这样的默认重置过程可以针对每个节点分别被建立。在一个实施例中，一些节点被设置以执行重置过程，而其他节点不被设置。例如，边缘节点在一些实施例中可能不需要执行重置过程。转向方法1100，如果基于发送的重置过程被使用，则适当的重置掩码被应用于消息副本的MBA中(判断1126的“是”分支；步骤1128)。

方法1100继续确定接收节点是否直接连接至转发节点(判断步骤1130)。在一个实施例中，每个BIER-TE节点知道它的直接连接的邻居节点，无论是通过IGP的操作或通过诸如层2握手或宣告协议之类的另一协议。在方法1100的实施例中，如果链路的接收节点是直接连接的，则消息通过在链路的BTFT条目中识别的节点接口被转发(判断1130的“是”分支；步骤1136)。针对该链路的转发然后被完成，并且方法移动至查看是否存在更多被映射至相同位位置的链路(接收节点)(判断步骤1138)。如果接收节点不是直接连接的，则链路是非直接链路，例如图1到3B示出的网络100的链路AE。消息然后被封装以用于单播路由并且通过适当的单播转发表被转发(判断1130的“否”分支；步骤1132；步骤1134)。

在消息副本转发之后，无论是通过解封装并且传递至上层协议、转发至直接连接的BIER-TE节点、或封装用于路由至非直接连接的节点，方法1100继续确定其他接收节点是否被映射至位位置(判断步骤1138)。这个情况的示例是诸如图5A的星形配置之类的网络部分，其中从一个节点到多个邻居节点的链路被映射至相同位位置。如果存在另外的接收节点，则方法返回步骤1114并且针对下一个链路重做(判断1138的“是”分支)。如果不这样，则针对当前位位置转发完成，并且方法确定消息位阵列中是否存在另外的置位位(判断步骤1140)。如果存在另外的置位位，则方法返回步骤1110并且针对下一个位位置重做(判断1140的“是”分支)。当已经考虑了消息位阵列中的所有置位位时，方法结束。

在BIER-TE节点处实施的过程的另外示例由图11B的流程图示出。图11B的方法1150在BIER-TE节点处而不是在到BIER-TE域的入口节点处被实施。这样，方法1150从接收已经被用消息位阵列封装的BIER-TE消息开始(步骤1152)。方法开始确定是否使用基于接收的重置过程以及是否使用接受检查(判断步骤1154和1156)。在图11B的实施例中，接受检查是否将被执行的确定在使用基于接收的重置过程被确定之后被完成。在一个实施例中，接受检查由没有采用基于接收的重置过程的节点来执行。在一些实施例中，BIER-TE控制器确定接受检查是否将由节点执行。如果接受检查由节点执行，则它以类似于上面结合图10C所描述的方式进行。如果在消息的消息位阵列中在被映射至节点的传入链路的位位置处位被置位，则消息被接受(判断步骤1156和1158的“是”分支)。否则，消息被丢弃，结束方法(判断1158的“否”分支)。基于接收的重置过程然后通过将基于接收的重置掩码应用至消息位阵列而被实施，如上面的重置过程的讨论中所描述的(步骤1160)。接受过程和基于接收的重置过程两者都要求BIER-TE节点知道被映射至它的传入链路的任意BIER-TE位位置。在一个实施例中，此信息通过传入链路的BTFT中的条目被包括在节点处的BTFT中。

无论基于接收的重置过程是否被执行，方法1150的转发部分开始检查接收到的BIER-TE消息的消息位阵列中的处于被映射至节点的BTFT中的外出链路的位位置的位值(步骤1162)。方法1150采用不同于图11A的方法1100的机制的用于将BIER-TE消息的MBA与BTFT条目进行对比的机制。如上所述，方法1100的对比机制是考虑消息的MBA中的每个置位位，并且检查将置位的位位置映射至由节点使用的链路的BTFT条目。另一方面，方法1150首先考虑被映射至节点的BTFT中的外出链路的位位置，并且检查MBA中的这些位位置的位，从而查看任何位是否被置位。这两种机制的最终结果是相同的：如果MBA中的位被设置处于被映射至外出链路的位置，则BIER-TE消息通过该链路被转发。

如果步骤1162的位值检查的结果是位被置位，则方法继续从适当的BTFT条目读取对应于置位的位位置的链路的接收节点(判断步骤1164的“是”分支；步骤1166)。如果位值检查的结果是位没有被置位，则消息将不通过被映射至当前位位置的链路被转发，并且方法检查被映射至节点处的BTFT中的外出链路的任何其他位位置(判断1164的“否”分支；步骤1192)。注意，图11B的方法1150的步骤1166到1190与图11A中的方法1100的步骤1114到1138相同。这些步骤以上面针对方法1100所讨论的方式被实施。然而，关于步骤1178和1180的基于发送的重置过程，注意，如果基于接收的重置过程在步骤1154和1160中被执行，则通常没有基于发送的重置过程在节点处被执行。基于发送的重置过程的使用将使得由转发的消息遇到的下一个节点处的基于接收的重置过程是多余的(因为传入链路的位位置中的位已经被重置)，并且如果BIER-TE域中的BIER-TE使能的节点都采用重置过程，则它们通常采用相同重置过程定时。当已经考虑了被映射至BTFT中的外出链路的每个位位置，并且针对被映射至位位置的每个链路转发的消息副本在消息位阵列中具有置位位时，方法结束(判断步骤1190和1192的“否”分支)。

BIER-TE网络设备

图12A是示出可以与本文所述的网络中的一个网络中的节点相关联的示范性网络设备的某些组件的框图。例如，网络设备1200可以与图1至3B的网络100中的核心路由器或出口路由器相关联。在图12A的实施例中，网络设备1200包括转发引擎1204、转发信息1206和通信接口1202。在一个实施例中，通信接口1202包括多个接口并且被配置为在所述网络内在网络节点之间或者在网络设备和控制器之间既发送和接收消息又发送和接收控制信息。每个接口可以是物理接口或逻辑接口。

转发引擎1204被配置为利用存储的转发信息1206来转发消息。例如，转发引擎1204可以执行与图11B所示的转发过程类似的转发过程。转发信息1206被转发引擎1204利用。在图12A的实施例中，转发信息1206包括邻居信息1208和BIER-TE转发表1210。在一个实施例中，邻居信息1208是通过与IGP不同的协议(例如，层2握手或宣告协议)的操作被获得的。BTFT 1210包括BIER-TE位位置至与网络设备1200相关联的节点的链路的任意映射。在一个实施例中，网络设备1200不存储拓扑或路由信息，并且映射至BTFT 1210中的位位置的链路不包括间接链路或路由链路。在这样的实施例中，在BTFT 1210中表示的链路是如本公开所描述的直接连接的链路或解封装链路。邻居信息1208和BTFT 1210包括通过接口1202从其它节点处的网络设备上和/或从网络控制器接收的信息。在图12A的实施例中，接口1202上的通信经由转发引擎1204被处理。在其它实施例中，存储和更新转发信息1206可以通过至接口1202的独立连接来完成，例如，经由在图12A中未示出的通信模块。

网络设备的另一实施例的某些组件由图12B的框图示出。图12B的网络设备1220可以与图1至3B的网络100中的核心路由器或出口路由器相关联。除了上文针对网络设备1200所描述的接口1202和转发引擎1204之外，网络设备1220还包括路由模块1212和路由信息1214。在一个实施例中，在路由信息1214内的路由表是单播路由表。在图12B的实施例中，除上文针对网络设备1200所描述的邻居信息1208和BTFT 1210之外，转发信息1207还包括转发表1218。在一个实施例中，转发表1218是利用路由表1216建立的单播转发表。在这样的实施例中，包含路由模块1212、路由信息1214和转发表1218允许网络设备1220在间接的或转发路由的、链路上利用单播隧道执行BIER-TE转发。在图12B的实施例中，接口1202上的通信是经由转发引擎1204和路由模块1212被处理的。在其它实施例中，存储和更新转发信息1207和/或路由信息1214可以通过至接口1202的独立连接来完成，例如，经由在图12B中未示出的一个或多个通信模块。

图12C的框图还示出了网络设备的又一实施例。在一个实施例中，图12C的网络设备1230与域或BIER-TE网络的入口节点相关联。除了上文针对图12A的网络设备1200所描述的接口1202、转发引擎1204和转发信息1206之外，网络设备1230还包括封装模块1222和路径信息1224。封装模块1222被配置为利用包括消息位阵列的BIER-TE封装来封装传入消息。路径信息1224包括需要利用BIER-TE网络来封装一个或多个消息流的消息位阵列，其中，消息流可以包括例如多播组或流量工程单播流。在图12C的实施例中，路径信息1224包括一个或多个流路径表(FPT)1226，其中流路径表可以包括多播组路径表(GPT)1228。类似于图12A的网络设备1200，在图12C的实施例中，网络设备1230不存储拓扑或路由信息。在可替换的实施例中，网络设备1230可以包括如上文针对图12B的网络设备1220所述的路由模块、路由信息和转发表。在图12C的实施例中，接口1202上的通信是经由转发引擎1204和封装模块1222被处理的。在其它实施例中，存储和更新转发信息1206和/或路由信息1224可以通过至接口1202的独立连接来完成，例如，经由在图12C中未示出的一个或多个通信模块。

图12D示出针对本文所述的网络中的一个网络的附加网络设备的某些组件。网络设备1240还被配置成BIER-TE控制器。在一个实施例中，网络设备1240与在BIER-TE网络的数据路径之外的控制器主机相关联。在可替换的实施例中，网络设备1240的一些或全部功能与例如网络设备1230的功能相结合并且在域或BIER-TE网络的入口节点处被执行。在图12D的实施例中，网络设备1240包括被耦合至通信接口1264的位位置分配模块1242和路径生成模块1244。在一个实施例中，通信接口1264被配置为发送和接收网络设备1240和其它与BIER-TE中的节点相关联的网络设备之间的控制信息。通信接口1264可以包括多个接口，并且每个接口可以是逻辑或物理接口。

位位置分配模块1242被配置为向BIER-TE网络内被用来形成针对BIER-TE消息的明确路径或树的链路分配位位置。例如，BP分配模块1242可以执行与图7的方法700类似的分配过程。在一个实施例中，拓扑信息1246由BP分配模块1242使用。该拓扑信息反映了BIER-TE网络或域的节点是如何相互连接的。在一个实施例中，拓扑信息是通过与利用控制协议的每个BIER-TE节点的交互获得的。可替换地，在BIER-TE节点正运行IGP的实施例中，拓扑信息可以由网络设备1240通过IGP广告来获得。在图12D的实施例中，BP分配模块1242还被配置为利用从路径生成模块1244获得的路径相关信息来分配位位置。在图12D的实施例中，BP分配模块被配置为在BP信息库1254中存储位位置分配。在一个实施例中，BP信息库1254充当一种BIER-TE路由表，用于存储针对遍及BIER-TE网络或域的已经被分配了位位置的链路的位位置分配。然后信息库可以由例如路径生成模块1244访问以用于确定明确路径。除了在网络设备1240处存储位位置分配之外，BP分配模块1242还被配置为在每个BIER-TE节点处将与该节点相关的位位置分配传输至网络设备。例如，在图12A的网络设备1200与各自的BIER-TE节点相关联的实施例中，针对与每个节点相关的链路的位位置分配被传输至针对该节点的网络设备并且被存储在相应的BTFT中。

网络设备1240的路径生成模块1244被配置为确定针对通过BIER-TE网络或域被转发的每个消息流的明确路径或树、并且被配置为在将被流中的消息携带的消息位阵列中表示该路径和树。除了拓扑信息1246之外，路径生成模块1244被配置为使用被存储的消息流信息1248。在图12D的实施例中，消息流信息1248包括多播成员关系信息1250和单播流信息1252。在一个实施例中，网络设备1240适合于从BIER-TE网络中的一个或多个提供商边缘节点接收多播成员关系信息1250。多播成员关系信息可以包括由与此类提供商边缘节点相关联的主机接收或发送的针对传输的多播源和/或组信息。在一些实施例中，网络设备1240还适合于从提供商边缘节点接收单播流信息1248。在一些实施例中，网络设备1240适合于利用网络流协议从流分析设备接收单播流信息。在网络设备1240的实施例中，消息流信息1248被限制为是多播成员关系信息1250或单播流信息1252中的一个。在一些实施例中，多播成员关系信息1250和单播流信息1252还可以被组合成一个表或其它数据结构。路径生成模块1244还被配置为使用位位置信息库1254来创建对每个生成的路径或树进行编码的消息位阵列。

在图12D的实施例中，路径生成模块1244存储主路径信息1258，该主路径信息包括一个或多个主多播组路径表(GPT)1260和一个或多个主单播流路径表(FPT)1262。在一个实施例中，主GPT将消息位阵列映射至针对网络或域中的所有BIER-TE多播树的多播组信息。在主GPT中表示的多播组可以具有不同的BIER-TE入口节点。网络设备1240除了在其自己的主GPT中存储针对多播组的消息位阵列以外，还将消息位阵列和多播组信息发送至BIER-TE入口节点以便在包含消息位阵列的每个入口节点处为使用该入口节点的多播组填充GPT。在一个实施例中，存储在特定BIER-TE入口节点的GPT包含在主GPT 1260中的消息位阵列信息的子集一该子集与使用该入口节点的多播组相关。类似地，主FPT 1262将消息位阵列映射至在网络或域中的所有BIER-TE流量工程单播流的标识符，并且网络设备1240将消息位阵列和单播流信息发送至针对特定流的BIER-TE入口节点以便于在每个入口节点处为在该节点处开始的流填充FPT。在其它实施例中，主路径信息1258只包括主GPT(一个或多个)1260和主FPT(一个或多个)1262中一个或另一个。在一些实施例中，主GPT 1260和主FPT1262还可以被组合成单一主FPT。

在图12D的实施例中，路径生成模块1244和BP分配模块1242被配置为相互通信。如上文所讨论的，位位置的分配和路径的确定在一些实施例中是相互依赖的过程，并且可以以迭代的方式和/或作为优化进行。在一个实施例中，在模块之间传输的信息包括位位置信息、路径信息或消息流信息中的任意一个或任意组合。在图12D的实施例中，接口1264上的通信是经由BP分配模块1242和路径生成模块1244被处理的。在其它实施例中，存储和更新诸如拓扑信息1246和/或消息流信息1248之类的信息可以通过至接口1264的独立连接来完成，例如，经由图12D中未示出的一个或多个通信模块。

图13是示出可以在上文所述网络中被采用的节点的某些附加和/或替换组件的框图。在该描述中，节点1300包括经由数据总线1330和结果总线1340被通信地耦合至转发引擎或分组转发程序1310和处理器1320的多个线卡(线卡1302(1)-(N))。线卡1302(1)-(N)包括由端口处理器控制器1360(1)-(N)控制的多个端口处理器1350(1，1)-(N，N)。还应该注意的是转发引擎1310和处理器1320不只是经由数据总线1330和结果总线1340相互耦合，还通过通信链路1316被通信地相互耦合。

每个线卡1302的处理器1350和1360可以被安装在单个印刷电路板上。当分组或分组和头部被接收时，分组或分组和头部可以以以下方式被路由器1300识别和分析。当接收时，分组(或其控制信息的一些或全部)或分组和头部是从端口处理器1350(1，1)-(N，N)中的一个端口处理器被发送，在端口处理器处，分组或分组和头部被接收至被耦合至数据总线1330的那些设备中的一个或多个设备(例如，端口处理器1350(1，1)-(N，N)中的其它端口处理器、转发引擎1310和/或处理器1320)。分组或分组和头部的处理可以被例如转发引擎1310确定。例如，转发引擎1310可以确定分组或分组和头部应该被转发至端口处理器1350(1，1)-(N，N)中的一个或多个端口处理器。这可以通过向端口处理器控制器1360(1)-(N)中的相应的端口处理器控制器(一个或多个)指示在端口处理器1350(1，1)-(N，N)中的给定端口处理器中(一个或多个)保存的分组或分组和头部的副本应该被转发至端口处理器1350(1，1)-(N，N)中的适当端口处理器来完成。额外地或可替换地，一旦识别到用于处理的分组或分组和头部，那么转发引擎1310、处理器1320等可以被用于以一些方式处理该分组或分组和头部或添加分组安全信息，以便于保护分组。在发起这样的分组或分组和头部的节点上，该处理可以包括例如针对所有分组的或分组和头部的信息中的一些或全部信息的加密、数字签名或一些其它信息的添加、或有保护分组或分组和头部的能力的处理。在接收此类被处理的分组或分组和头部的节点上，相应的处理可以被执行以恢复或验证因此被保护的分组的或分组和头部的信息。

图14是示出例如如上文所述转发模块以软件实现方式的计算设备的框图。计算系统1410广泛地表示能够执行计算机可读指令的任意单一或多处理器计算设备或系统。计算系统1410的示例包括但不限于包括以下各项的各种设备中的一个或多个：工作站、个人计算机、膝上型电脑、客户端终端、服务器、分布式计算系统、手持设备(例如，个人数字助理或移动电话)、网络应用、交换机、路由器、存储控制器(例如，阵列控制器、磁带驱动控制器、或硬驱动控制器)等。在计算系统1410最基本的配置中，计算系统1410可以包括至少一个处理器1414和系统存储器1416。通过执行实施转发模块1417的软件，计算系统1410变成被配置为以上文所述的方式执行分组转发的专用计算设备。

处理器1414通常表示能够处理数据或翻译和执行指令的任意类型或形式的处理单元。在某些实施例中，处理器1414可以从软件应用或模块接收指令。这些指令可以使得处理器1414执行本文所述和/或所示的实施例中的一个或多个实施例的功能。例如，处理器1414可以执行本文所述的操作和/或可以是用于执行本文所述的操作的装置。处理器1414还可以执行本文所述和/或所示的任意其它操作、方法和处理和/或可以是用于执行本文所述和/或所示的任意其它操作、方法和处理的装置。

系统存储器1416通常表示能够存储数据和/或其它计算机可读指令的任意类型或形式的易失性或非易失性存储设备或介质。系统存储器1416的示例包括但不限于随机访问存储器(RAM)、只读存储器(ROM)、闪速存储器、或任意其它适合的存储器设备。虽然不是必需的，但是在某些实施例中，计算系统1410可以既包括易失性存储器(例如，系统存储器1416)又包括非易失性存储器(例如，如下文详细描述的主存储器设备1432)。在一个示例中，可执行来实施被配置为转发多播数据的转发模块的程序指令可以被加载至系统存储器1416。

在某些实施例中，计算系统1410还可以包括除处理器1414和系统存储器1416之外的一个或多个组件或元件。例如，如图14所示，计算系统1410可以包括存储器控制器1418、输入/输出(I/O)控制器1420、和通信接口1422，它们中的每一个可以经由通信基础设施1412互相连接。通信基础设施1412通常表示能够促进计算设备的一个或多个组件之间的通信的任意类型或形式的基础设施。通信基础设施1412的示例包括但不限于通信总线(例如，工业标准结构(ISA)、外部设备互联(PCI)、PCI标准(PCIe)、或类似的总线)和网络。

存储器控制器1418通常表示能够处理存储器或数据或控制计算系统1410的一个或多个组件之间的通信的任意类型或形式的设备。例如，在某些实施例中，存储器控制器1418可以控制处理器1414、系统存储器1416和I/O控制器1420之间经由通信基础实施1412的通信。在某些实施例中，存储器控制器1418可以单独或与其它元件组合来执行本文所述和/或所示的特征或操作中的一个或多个特征或操作、和/或可以是单独或与其它元件组合来执行本文所述和/或所示的特征或操作中的一个或多个特征或操作的装置。

I/O控制器1420通常表示能够协调和/或控制计算设备的输入和输出功能的任意类型或形式的模块。例如，在某些实施例中，I/O控制器1420可以控制或促进计算系统1410的一个或多个元件(例如，处理器1414、系统存储器1416、通信接口1422、显示适配器1426、输入接口1430、和存储接口1434)之间的数据的传递。

通信接口1422广泛地表示能够促进计算系统1410和一个或多个附加设备之间的通信的任意类型或形式的通信设备或适配器。例如，在某些实施例中，通信接口1422可以促进计算系统1410和个人或包括附加的计算系统的公共网络之间的通信。通信接口1422的示例包括但不限于有线网络接口(例如，网络接口卡)、无线网络接口(例如，无线网络接口卡)、调制解调器、和任意其它适合的接口。在至少一个实施例中，通信接口1422可以经由直接链路向网络(例如，互联网)提供至远程服务器的直接连接。通信接口1422还可以间接地通过例如局域网(例如，以太网)、个人局域网、电话或电缆网络、蜂窝电话连接、卫星数据连接或任意其它适合的连接来提供此类连接。

在某些实施例中，通信接口1422还可以表示被配置为促进计算系统1410和一个或多个附加网络或存储设备之间的经由外部总线或通信信道的通信的主机适配器。主机适配器的示例包括但不限于小型计算机系统接口(SCSI)主机适配器、通用串行总线(USB)主机适配器、电气与电子工程师协会(IEEE)11054主机适配器、串行高级技术附件(SATA)和外部SATA(eSATA)主机适配器、高级技术附件(ATA)、和平行ATA(PATA)主机适配器、光纤信道接口适配器、以太网适配器等。

通信接口1422还可以允许计算系统1410参与分布式或远程计算。例如，计算接口1422可以从远程设备接收指令或者向远程设备发送指令以用于执行。

如图14所示，计算系统1410还可以包括经由显示适配器1426被耦合至通信基础设施1412的显示设备1424。显示设备1424通常表示能够可视地显示由显示适配器1426转发的信息的任意类型或形式的设备。类似地，显示适配器1426通常表示被配置为转发来自通信基础设施1412的图形、文本、和其它数据以在显示设备1424上显示的任意类型或形式的设备。

如图14所示，计算系统1410还可以包括经由输入接口1430被耦合至通信基础设施1412的至少一个输入设备1428。输入设备1428通常表示能够向计算系统1410提供计算机或人工生成的输入的任意类型或形式的输入设备。输入设备1428的示例包括但不限于键盘、定点设备、语音识别设备或任意其它的输入设备。

如图14所示，计算系统1410还可以包括经由存储接口1434被耦合至通信基础设施1412的主存储设备1432和备份存储设备1433。存储设备1432和1433通常表示能够存储数据和/或其它计算机可读指令的任意类型或形式的存储设备或介质。例如，存储设备1432和1433可以是磁盘驱动(例如，所谓的硬驱动)、软盘驱动、磁带驱动、光盘驱动、闪盘驱动等。存储接口1434通常表示用于在存储设备1432和1433与计算系统1410的其它组件之间传输数据的任意类型或形式的接口或设备。类似于主存储设备1432的存储设备可以存储诸如路由表和转发表之类的信息。

在某些实施例中，存储设备1432和1433可以被配置为从被配置为存储计算机软件、数据或其它计算机可读信息的移动存储单元进行读取和/或写入至移动存储单元。合适的移动存储单元的示例包括但不限于软盘、磁带、光盘、闪速存储器设备等。存储设备1432和1433还可以包括用于允许计算机软件、数据、或其它计算机可读指令被加载至计算系统1410的其它类似的结构或设备。例如，存储设备1432和1433可以被配置为读和写软件、数据或其它计算机可读信息。存储设备1432和1433还可以是计算系统1410的一部分或者可以是通过其它接口系统接入的独立设备。

许多其它设备或子系统可以被连接至计算系统1410。相反地，不需要存在图14中示出的所有组件和设备来实践本文示出和/或描述的实施例。上文引用的设备和子系统还可以以与图14所示的方式不同的方式进行互连。

计算系统1410还可以采用任意数量的软件、固件和/或硬件配置。例如，本文公开的一个或多个实施例可以被编码成在计算机可读存储介质上的计算机程序(还被称为计算机软件、计算机应用、计算机可读指令或计算机控制逻辑)。计算机可读存储介质的示例包括磁存储介质(例如，硬盘驱动和软盘)、光存储介质(例如，CD-或DVD-ROM)、电存储介质(例如，固态驱动和闪存介质)等。这样的计算机程序还可以被传递至计算系统1410以经由诸如互联网之类的网络被存储在存储器上或被存储在载波介质上。

包含计算机程序的计算机可读介质可以被加载至计算系统1410。然后存储在计算机可读介质上的计算机程序的一部分或全部可以被存储在系统存储器1416和/或存储设备1432和1433的各种部分中。当由处理器1414执行时，被载入计算系统1410的计算机程序可以使得处理器1414执行本文所示和/或所述的实施例中的一个或多个实施例的功能、和/或使得处理器1414成为执行本文所示和/或所述的实施例中的一个或多个实施例的功能的装置。额外地或可替换地，本文所示或所述的实施例中的一个或多个实施例可以在固件和/或硬件中实施。例如，计算系统1410可以被配置成适合于实施本文公开的实施例中的一个或多个实施例的专用集成电路(ASIC)。

示例1是一种方法，包括：确定消息通过网络所采用的路径，其中该消息适于承载消息位阵列；在消息位阵列内分配与路径内的网络链路对应的位位置；以及将网络链路与其经分配的位位置之间的对应关系沿路径传输给网络节点，其中该网络节点被连接到该网络链路。

示例2包括示例1的方法，还包括在可由网络控制器访问的数据结构中存储网络链路与其经分配的位位置之间的对应关系。

示例3包括示例1的方法，还包括生成消息位阵列，其中消息位阵列中的位位置处的位值指示被分配给这些位位置的各网络链路是否包括在消息要采用的链路中。

示例4包括示例3的方法，还包括向网络的入口节点传输与包括该消息的消息流相关联的信息和消息位阵列。

示例5包括示例1的方法，其中：消息包括多播消息；并且确定路径包括确定多播树。

示例6包括示例1的方法，其中路径内的一个或多个网络链路直接将网络节点连接至相邻网络节点。

示例7包括示例6的方法，其中：被分配给一个或多个网络链路中的一个的双向位位置对应于跨相应网络链路的两个方向；以及传输对应关系包括将双向位位置与其经分配的网络链路之间的对应关系传输给该网络节点及由经分配的网络链路连接的相邻网络节点。

示例8包括示例7的方法，其中传输对应关系还包括传输指令以在通过经分配的网络链路转发接收到的消息的副本之前，在接收到的消息位阵列中重置双向位位置中的位。

示例9包括示例1的方法，其中确定路径包括接收对路径进行限定的输入。

示例10包括示例1的方法，还包括：标识网络的洪泛部分，在该洪泛部分中，所有节点能够接收多播消息；确定洪泛部分内的非环路径；以及向沿非环路径的所有网络链路分配第一位位置，其中经分配的位位置对应于跨每个相应网络链路的单个方向。

示例11包括示例1的方法，还包括：标识路径的绕过部分，其中多播消息的副本或多播消息的显式路由都无需通过该部分；以及向沿路径、在绕过部分的相对端处的第一节点和第二节点之间的绕过链路分配位位置。

示例12包括示例1的方法，还包括：向网络的出口节点分配位位置，其中出口节点被包括在该路径中；以及

将出口节点与位位置之间的对应关系传输给出口节点。

示例13包括示例12的方法，其中：分配位位置还包括向网络的多个出口节点中的每一个分配位位置，其中多个出口节点中的每一个被包括在该路径中；以及将出口节点与位位置之间的对应关系传输给出口节点包括将位位置与多个出口节点中的每一个之间的对应关系传输给相应出口节点。

示例14包括示例1的方法，还包括：标识由并列的多条链路连接的一对节点；以及向该多条链路中的每一条分配第一位位置。

示例15包括示例1的方法，其中将网络链路与其经分配的位位置之间的对应关系传输给网络节点包括传输该对应关系以存储于网络节点所使用的转发表中。

示例16是一种用于控制网络的设备，该设备包括：一个或多个通信接口；一个或多个计算机可读存储介质，被配置为存储网络的拓扑信息；处理器；以及所存储的程序指令，被配置为当被处理器执行时：使用拓扑信息来确定消息通过网络要采用的路径，其中该消息适于承载消息位阵列；与路径的至少一部分内的多条相应的网络链路相对应地，在消息位阵列内分配单独的位位置；以及对于每个经分配的位位置，将网络链路与其经分配的位位置之间的对应关系传输给连接到与该位位置相对应的网络链路的相应网络节点。

示例17包括示例16的设备，其中所存储的程序指令还被配置为当被处理器执行时，将沿该路径的网络链路与其各自经分配的位位置之间的对应关系存储在数据结构中。

示例18包括示例16的设备，其中所存储的程序指令还被配置为当被处理器执行时，生成消息位阵列，其中消息位阵列中的位位置处的位值指示被分配给这些位位置的各网络链路是否包括在消息要采用的链路中。

示例19包括示例18的设备，其中所存储的程序指令还被配置为当被处理器执行时，向网络的入口节点传输与包括该消息的消息流相关联的信息和消息位阵列。

示例20包括示例19的设备，其中该一个或多个计算机可读存储介质还被配置为存储将一个或多个消息位阵列与关联于各消息流的信息相关联的数据结构。

虽然本公开包括若干实施例，但是本公开不意欲被限制于本文提出的具体形式。相反，本公开意欲覆盖可以被合理地包含在由所附权利要求书定义的范围内的此类替换、修改和等同物。

Claims (41)

1.一种用于提供位索引显式复制的流量工程的方法，包括：

在配置用于流量工程位索引转发的网络中的第一节点处接收包括消息位阵列的消息；

将在所述消息位阵列中的一个或多个位位置处的位值与存储在所述第一节点处的转发表中的一个或多个条目进行对比，其中，所述一个或多个位位置被分配给所述网络中的单独路径段；以及

如果所述对比的结果指示在所述路径段被包括在所述消息要采用的路径中，那么在所述路径段上转发所述消息，其中所述转发表中表示的路径段被分配所述消息位阵列中的位位置中的一个位位置，并且，

所述消息位阵列中的位位置中的所述一个位位置并不表示配置用于流量工程位索引转发的所述网络的能经由所述路径段达到的出口节点。

2.根据权利要求1所述的方法，其中，

所述消息是多播消息；并且

转发所述消息包括转发所述多播消息的副本。

3.根据权利要求1所述的方法，其中，在所述消息位阵列中的至少一个位位置被分配给从所述第一节点至所述网络的核心节点的路径段。

4.根据权利要求1所述的方法，其中，所述对比包括：将所述消息位阵列的一部分与在所述转发表的条目中的链路位阵列的相应部分进行对比。

5.根据权利要求1所述的方法，其中，所述对比包括：检查在所述消息位阵列中的位位置的位值，其中，所述位位置被分配给所述转发表中表示的路径段。

6.根据权利要求1所述的方法，其中，所述对比包括：

识别所述消息位阵列中的一个或多个置位的位位置；以及

针对被分配有各个所识别的位位置的路径段检查所述转发表。

7.根据权利要求1所述的方法，其中，所述消息要采用的所述路径能够通过将被分配有所述消息位阵列中的具有置位值的位位置的多个路径段进行端到端连接来定义。

8.根据权利要求1所述的方法，其中，在所述转发表中表示的所述路径段直接将所述第一节点连接至所述网络中的相邻节点。

9.根据权利要求1所述的方法，其中，在所述转发表中表示的所述路径段包括：至所述网络中的第二节点的间接连接。

10.根据权利要求1所述的方法，其中，被分配有所述消息位阵列中的位位置的路径段包括：在被用于在所述第一节点处接收所述消息的网络协议层和所述网络的不同协议层之间的链路。

11.根据权利要求1所述的方法，所述方法还包括：在转发所述消息之前，重置所述消息位阵列中的被分配给所述转发表中表示的所述路径段的位位置的位值。

12.根据权利要求1所述的方法，其中，被存储在所述转发表中的信息的至少一部分是从网络控制器接收的。

13.根据权利要求12所述的方法，其中，所述网络的拓扑表示不被存储在所述第一节点中。

14.一种与网络中的节点相关联的配置用于进行流量工程位索引转达的网络设备，所述网络设备包括：

一个或多个网络接口；

存储器，所述存储器被配置为存储包括一个或多个条目的转发表；以及

处理器，所述处理器被配置为：

经由所述网络接口中的一个网络接口接收包括消息位阵列的消息；

将在所述消息位阵列中的一个或多个位位置处的位值与所述转发表中的一个或多个条目进行对比，其中，所述一个或多个位位置被指派给所述网络中的单独的路径段；以及

如果所述对比的结果指示所述路径段被包括在所述消息要采用的路径中，那么在所述路径段上转发所述消息，其中，在所述转发表中表示的所述路径段被分配有所述消息位阵列中的位位置中的一个位位置，并且

所述消息位阵列中的位位置中的所述一个位位置并不表示配置为用于流量功能位索引转发的所述网络的能够经由所述路径段达到的出口节点。

15.根据权利要求14所述的网络设备，其中，所述处理器还被配置为：

接收多播消息；以及

复制所述多播消息。

16.根据权利要求14所述的网络设备，其中，在所述转发表中表示的所述路径段是从所述节点至所述网络的另一节点的路径段。

17.根据权利要求16所述的网络设备，其中，所述网络的另一节点是所述网络的核心节点。

18.根据权利要求14所述的网络设备，其中，

所述存储器还被配置为存储针对所述网络的拓扑信息；并且

所述处理器还被配置为封装所述消息以便单播路由至所述网络的远程节点，其中，所述远程节点不被直接连接至与所述网络设备相关联的所述节点。

19.根据权利要求14所述的网络设备，其中，

所述存储器还被配置为存储包括为消息流编码路径或树的消息位阵列的路径表；并且

所述处理器还被配置为：

经由所述网络接口中的一个网络接口接收没有消息位阵列的消息，以及

利用从所述路径表取回的消息位阵列来封装所述消息。

20.根据权利要求19所述的网络设备，其中，

所述消息流的一个或多个源或接收者是多播组的成员；并且

所述路径表将多播组信息映射至所述消息位阵列。

21.根据权利要求14所述的网络设备，其中，

被分配有所述消息位阵列中的位位置的路径段是至所述网络中的更高协议层的链路；并且

所述处理器还被配置为从所述消息中移除所述消息位阵列并且在所述节点处将所述消息传递至所述更高协议层。

22.一种用于提供位索引显式复制的流量工程的方法，包括：

确定消息通过网络所采用的路径，其中该消息适于承载消息位阵列；

在消息位阵列内分配与路径内的网络链路对应的位位置；以及

将网络链路与其经分配的位位置之间的对应关系沿路径传输给网络节点，其中该网络节点被连接到该网络链路。

23.根据权利要求22所述的方法，还包括在可由网络控制器访问的数据结构中存储网络链路与其经分配的位位置之间的对应关系。

24.根据权利要求22所述的方法，还包括生成消息位阵列，其中消息位阵列中的位位置处的位值指示被分配给这些位位置的各网络链路是否包括在消息要采用的链路中。

25.根据权利要求24所述的方法，还包括向网络的入口节点传输与包括该消息的消息流相关联的信息和消息位阵列。

26.根据权利要求22所述的方法，其中：

消息包括多播消息；并且

确定路径包括确定多播树。

27.根据权利要求22所述的方法，其中路径内的一个或多个网络链路直接将网络节点连接至相邻网络节点。

28.根据权利要求27所述的方法，其中：

被分配给一个或多个网络链路中的一个的双向位位置对应于跨相应网络链路的两个方向；以及

传输对应关系包括将双向位位置与其经分配的网络链路之间的对应关系传输给该网络节点及由经分配的网络链路连接的相邻网络节点。

29.根据权利要求28所述的方法，其中传输对应关系还包括传输指令以在通过经分配的网络链路转发接收到的消息的副本之前，在接收到的消息位阵列中重置双向位位置中的位。

30.根据权利要求22所述的方法，其中确定路径包括接收对路径进行限定的输入。

31.根据权利要求22所述的方法，还包括：

标识网络的洪泛部分，在该洪泛部分中，所有节点能够接收多播消息；

确定洪泛部分内的非环路径；以及

以及向沿非环路径的所有网络链路分配第一位位置，其中经分配的位位置对应于跨每个相应网络链路的单个方向。

32.根据权利要求22所述的方法，还包括：

标识路径的绕过部分，其中多播消息的副本或多播消息的显式路由都无需通过该部分；以及

向沿路径、在绕过部分的相对端处的第一节点和第二节点之间的绕过链路分配位位置。

33.根据权利要求22所述的方法，还包括：

向网络的出口节点分配位位置，其中出口节点被包括在该路径中；以及

将出口节点与位位置之间的对应关系传输给出口节点。

34.根据权利要求33所述的方法，其中：

分配位位置还包括向网络的多个出口节点中的每一个分配位位置，其中多个出口节点中的每一个被包括在该路径中；以及

将出口节点与位位置之间的对应关系传输给出口节点包括将位位置与多个出口节点中的每一个之间的对应关系传输给相应出口节点。

35.根据权利要求22所述的方法，还包括：

标识由并列的多条链路连接的一对节点；以及

向该多条链路中的每一条分配第一位位置。

36.根据权利要求22所述的方法，其中将网络链路与其经分配的位位置之间的对应关系传输给网络节点包括传输该对应关系以存储于网络节点所使用的转发表中。

37.一种用于控制网络的设备，该设备包括：

一个或多个通信接口；

一个或多个计算机可读存储介质，被配置为存储网络的拓扑信息；

处理器；以及

所存储的程序指令，被配置为当被处理器执行时：

使用拓扑信息来确定消息通过网络要采用的路径，其中该消息适于承载消息位阵列；

与路径的至少一部分内的多条相应的网络链路相对应地，在消息位阵列内分配单独的位位置；以及

对于每个经分配的位位置，将网络链路与其经分配的位位置之间的对应关系传输给连接到与该位位置相对应的网络链路的相应网络节点。

38.根据权利要求37所述的设备，其中所存储的程序指令还被配置为当被处理器执行时，将沿该路径的网络链路与其各自经分配的位位置之间的对应关系存储在数据结构中。

39.根据权利要求37所述的设备，其中所存储的程序指令还被配置为当被处理器执行时，生成消息位阵列，其中消息位阵列中的位位置处的位值指示被分配给这些位位置的各网络链路是否包括在消息要采用的链路中。

40.根据权利要求39所述的设备，其中所存储的程序指令还被配置为当被处理器执行时，向网络的入口节点传输与包括该消息的消息流相关联的信息和消息位阵列。

41.根据权利要求40所述的设备，其中该一个或多个计算机可读存储介质还被配置为存储将一个或多个消息位阵列与关联于各消息流的信息相关联的数据结构。