用于针对多个生成树选项高效管理带宽注册的技术

摘要

一种技术针对计算机网络中的多个生成树选项来高效管理带宽(BW)注册。根据该新颖技术，入口网桥确定去往网络的其他网桥的多条生成树路径(即，以网络的一个或多个网桥为根的一个或多个可用生成树)，并且确定这些路径中的每一条上已利用(注册)的BW。在例如从应用源端点接收到为去往目的地端点的数据流发起BW注册的请求后，入口网桥选择生成树路径之一来用于该数据流。从多条可用路径中对生成树路径的选择例如可以基于：(i)路径的可用带宽，(ii)最短路径，以及(iii)路径的网桥根的最低网桥标识符ID。入口网桥沿着所选择的生成树路径朝着目的地端点为数据流发送注册消息。如果成功，则数据流在所选择的路径上传输。否则，入口网桥尝试在下一最佳备用生成树上注册该数据流，直到注册成功为止或者确定不存在更多的备用生成树为止。

说明书

技术领域

本发明涉及计算机网络，更具体而言涉及在计算机网络中针对多个生成树选项高效管理带宽(BW)注册。

背景技术

包括企业、政府和教育机构在内的许多组织利用计算机网络，以便员工和他人可以共享和交换信息和/或资源。计算机网络一般包括利用一个或多个通信介质互连的多个实体。实体可以由通过通信介质“源发”(即，发送)或者“吸收”(即，接收)数据帧的任何设备(例如计算机)构成。常见类型的计算机网络是局域网(“LAN”)，LAN一般指的是单个建筑物或校园内的私有网络。LAN一般使用定义了由通信体系结构(即，协议栈)的数据链路和物理层执行的功能的数据通信协议(LAN标准)(例如以太网)或者无线协议。

一个或多个中间网络设备经常用于将LAN耦合到一起，并且允许相应的实体交换信息。例如，网桥可用于在两个或更多个LAN或末端站之间提供“切换”功能。一般来说，网桥是一个计算机，并且包括经由LAN耦合到其他网桥或者耦合到诸如路由器或主机计算机之类的末端站的多个端口。用于将网桥彼此耦合起来的端口一般被称为干线端口，而用于将网桥耦合到末端站的端口一般被称为接入端口。桥接功能包括在源端口处接收来自发送方实体的数据并将该数据传送到至少一个目的地端口以便转发到一个或多个接收方实体。

生成树算法

大多数计算机网络包括冗余通信路径，以便任何给定链路的故障不会使网络的任何部分孤立起来。这种网络一般被称为网状网络(meshednetwork)或部分网状网络。但是，冗余链路的存在可能导致在网络内形成迂回的路径或者“环路”。非常不希望出现环路，因为数据帧可能无限期地往返于环路。

另外，诸如网桥或交换机之类的一些设备对目的地未知的帧进行复制，从而导致环路上数据帧的激增。所造成的流量可能淹没网络。诸如路由器之类的在协议栈内的更高层(例如传输控制协议/因特网协议(“TCP/IP”)参考模型的互联网络层)工作的其他中间设备以与大多数网桥或交换机不同的方式递送数据帧并获知网络上的实体的地址，因而路由器一般不易受到持续的环路形成问题的影响。

为了避免环路的形成，大多数网桥和交换机执行生成树协议，这种协议允许它们计算无环路的活动网络拓扑(即，树)并仍连接网络内的每对LAN(即，该树是生成性的)。IEEE发布了一种标准(IEEE Std.802.1D-1998^TM)，这种标准定义了将由802.1D兼容设备执行的生成树协议。一般来说，通过执行802.1D生成树协议，网桥将桥接的网络内的单个网桥选择为“根网桥”。802.1D标准通过规定根网桥为具有最低网桥ID的网桥，从而利用了每个网桥具有唯一的数值标识符(网桥ID)这一事实。此外，对于耦合到任何网桥的每个LAN，选择一个网桥(“指定网桥”)上的恰好一个端口(“指定端口”)。指定网桥一般是最接近根网桥的网桥。根网桥上的所有端口都是指定端口，并且根网桥是所有下述LAN上的指定网桥：根网桥具有到所述LAN的端口。

每个非根网桥也从其非指定端口中选择一个端口(其“根端口”)，该端口给出去往根网桥的最低成本路径。根端口和指定端口被选择来包括在活动拓扑中，并且被置于转发(forwarding)状态中，从而数据帧可以被转发到和转发自这些端口，并因而转发到对网络的网桥和末端站进行互连的LAN上。未包括在活动拓扑内的端口被置于阻止(blocking)状态中。当端口处于阻止状态中时，不会向该端口转发数据帧，也不会从该端口接收数据帧。网络管理员还可以通过将端口置于禁用(disabled)状态中来将其排除在生成树之外。

为了获得运行生成树协议所必需的信息，网桥交换特殊的消息，这种特殊的消息被称为配置网桥协议数据单元(BPDU)消息或者简称为BPDU。BPDU携带着用于计算活动拓扑的信息，例如假定的根和最低根路径成本。更具体而言，在启动后，每个网桥最初假定其自身为根网桥，并相应地发送BPDU。在接收到来自相邻网桥的BPDU后，其内容被检查并被与接收方网桥存储在存储器中的类似信息(例如，假定的根和最低根路径成本)相比较。如果来自接收到的BPDU的信息比存储的信息“更好”，则网桥采用该更好的信息并且将该信息用在它从它的除了接收到该“更好”信息的端口之外的端口发送(在把与接收端口相关联的成本添加到根路径成本的情况下)的BPDU中。虽然BPDU不被网桥转发，但是根网桥的标识符如上所述最终被传播到所有网桥并被所有网桥所采用，从而使得它们可以选择其根端口和任何(一个或多个)指定端口。

为了使活动拓扑适应于变化和故障，根网桥周期性地(例如每hellotime)发送BPDU。响应于在其根端口上接收到BPDU，网桥从其指定端口(如果有的话)发送其自己的BPDU。这样，BPDU被周期性地在整个桥接的网络中传播，从而确认活动拓扑。随着BPDU信息被更新和/或淘汰并且活动拓扑被重新计算，端口可以从阻止状态转变到转发状态，反之亦然。也就是说，由于新的BPDU信息，先前被阻止的端口可能获知它应当处于转发状态中(例如，它现在是根端口或指定端口)。

虚拟局域网

计算机网络还可以被分割成一系列逻辑网络。例如，1995年2月28日授权给Ross的美国专利No.5,394,402(“’402专利”)公开了一种将交换机的任何端口与任何特定的网段关联起来的布置。具体而言，根据’402专利，通过利用将端口与特定的虚拟局域网(VLAN)指定(VLAN designation)虚拟地关联起来的VLAN布置，可以将特定交换机的任何数目的物理端口与该交换机内的任何数目的群组关联起来。更具体而言，交换机或集线器将VLAN指定与其端口关联起来，并且还将这些VLAN指定与从该VLAN指定所被指派的任何端口发送的消息关联起来。

每个端口的VLAN指定被存储在交换机的存储器部分中，从而每当在给定的接入端口上接收到消息时，该端口的VLAN指定就与该消息关联起来。关联是由一个流处理元件完成的，该流处理元件基于用来接收消息的特定接入端口在存储器部分中查找VLAN指定。在许多情况下，可能希望互连多个这样的交换机，以便扩展网络中的端口的VLAN关联。具有相同VLAN指定的那些实体就好像它们都是同一VLAN的一部分那样工作。VLAN配置的网桥被具体配置为防止网络的具有不同VLAN指定的部分之间的消息交换，以便保持每个VLAN的边界。然而，在L2上工作的中间网络设备(例如路由器)可以在不同VLAN段之间传递消息。

除了’402专利之外，IEEE发布了用于虚拟桥接局域网的802.1Q规范标准。为了保持在VLAN知晓网络中的干线或链路上传输的消息的VLAN关联，Ross和IEEE Std.802.1Q-2005规范标准都公开了将VLAN标识符(VID)字段附加到相应的帧。此外，与本申请属于同一申请人的Edsall等人的美国专利No.5,742,604(“’604专利”)公开了一种交换机间链路(ISL)封装机制，用于在交换机之间高效地传输分组或帧(包括经VLAN修改的帧)，同时维持帧的VLAN关联。具体地，可以利用快速以太网标准的ISL链路连接在每个交换机处部署的ISL接口电路。发送方ISL电路将所传输的帧封装在ISL头部和ISL差错检测信息中，而ISL接收方电路则剥除该信息并恢复原始帧。

多生成树协议

在IEEE Std.802.1Q-2005内，IEEE还包括了针对特别设计来结合支持VLAN的网络使用的生成树协议的规范标准。在IEEE Std.802.1Q-2005中描述的多生成树协议(MSTP)将桥接的网络组织成区域。在每个区域内，MSTP建立内部生成树(IST)，该内部生成树提供与各个区域内的所有网桥的连通性以及与其他区域内建立的IST的连通性。在每个MSTP区域内建立的IST还提供与由运行STP或RSTP的IEEE Std.802.1Q-2005兼容网桥在MSTP区域外建立的一个公共生成树(CST)的连通性。给定MST区域的IST接收并发送BPDU到CST。相应地，桥接网络的所有网桥被单个公共和内部生成树(CIST)所连接。另外，从遗留网桥或者IEEE Std.802.1Q-2005网桥的角度来看，每个MST区域看起来是CST上的单个虚拟网桥。

在每个MST区域内，MSTP兼容网桥建立多个活动拓扑，每个活动拓扑被称为多生成树实例(MSTI)。MSTP网桥还将每个VLAN指派或映射到一个(且仅一个)MSTI。因为VLAN可被指派给不同的MSTI，所以与不同VLAN相关联的帧可以采取不同的路径经过MSTP区域。网桥可以(但一般不)为每一个VLAN计算一个单独的拓扑，从而节约处理器和存储器资源。每个MSTI基本是一个仅存在于各个区域内的简单RSTP实例，并且MSTI不与区域外界交互。

与其他生成树协议一样，MSTP使用BPDU来建立IST和MSTI，以及定义不同MSTP区域的边界。网桥不为每个MSTI发送单独的BPDU。相反，每个MSTP BPDU携带为各个区域内定义的所有MSTI计算活动拓扑所需的信息。另外，每个MSTI具有相应的标识符(ID)，并且MSTIID被编码到网桥ID中。也就是说，每个网桥如上所述具有唯一的ID，并且该ID是由固定部分和可设置部分构成的。对于MSTP，网桥的ID的可设置部分被进一步组织为包括可设置优先级成分和系统ID扩展。系统ID扩展对应于MSTI ID之一或者CIST。给定区域内的MSTP兼容网桥从而将针对CIST和每个MSTI具有一个不同的网桥ID。对于给定的MSTI，针对该实例具有最低网桥ID的网桥被选择为根。因此，在给定的MSTP区域内，MSTP兼容网桥可以是一个MSTI的根，但不是另一个MSTI的根。

运行MSTP的每个网桥还具有由三个属性构成的单个MST配置标识符(ID)：文字数字配置名称、修订级别以及将可能的4096个VLAN中的每一个关联到相应的MSTI的VLAN映射表。另外，每个网桥将其MST配置ID加载到该网桥所源发的BPDU中。因为网桥只需要知道它们是否处于相同的MST区域中，因此它们在其BPDU中不传播实际的VLAN到MSTI表。作为替换，MST BPDU只携带VLAN到MSTI表或映射的摘要。该摘要是通过向VLAN到MSTI表应用公知的MD-5算法来生成的。当网桥接收到MST BPDU时，它提取其中包含的包括该摘要的MST配置ID，并将其与其自己的MST配置ID相比较，以判定它是否与发送MSTBPDU的网桥处于同一MST区域中。如果两个MST配置ID相同，则两个网桥处于同一MST区域中。但是，如果两个MST配置ID具有至少一个不匹配的属性，即，配置名称不同、修订级别不同和/或计算出的摘要不同，那么接收到BPDU的网桥断定它与源发BPDU的网桥处于不同的MST区域中。另外，如果指定网桥处于不同的MST区域中或者如果端口接收到遗留BPDU，则MST网桥的端口被认为处于MST区域的边界处。

注册协议

IEEE Std.802.1p(现在并入到了IEEE 802.1D-2004内)概述了通用属性注册协议(GARP)的实现方式和相关的GARP应用，其允许了末端站和网桥以通用方式交换成员资格信息。具体地，IEEE 802.1p所定义的GARP“提供了通用属性散布能力，该能力被GARP应用中的参与者(GARP参与者)用来向桥接的LAN内的其他GARP参与者注册和解除注册属性值”。IEEE 802.1p中定义的GARP的一个应用是GARP多播注册协议(GMRP)，该协议允许了GARP参与者加入和离开多播MAC(媒体访问控制)地址群组。希望加入特定群组的参与者(例如末端站)向接受注册的另一个GARP参与者(例如网桥)注册。该GARP参与者(网桥)随后代表原始参与者(末端站)申请成员资格，该成员资格被在整个网络中传播。GMRP所传播的信息一般包括多播MAC地址。IEEE802.1p中定义的另一个GARP应用是GARP VLAN注册协议(GVRP)。GVRP允许参与者以与GMRP相类似的方式加入和离开特定VLAN，但是涉及IEEE 802.1Q中定义的VLAN成员资格信息，例如VLAN ID(VID)。

一般来说，GARP参与者负责处理GARP状态机和BPDU分发。接收针对端口上的特定属性的注册的多端口设备(例如网桥/交换机)中的参与者通过申请者在参与GARP的所有其他端口上声明(通告)该属性。用于将该信息从一个GARP参与者传播到同一设备内的另一GARP参与者的机制被称为GARP信息传播(GIP)。GIP上下文指的是属于GIP的GARP参与者的群组。对于每个GIP上下文，对于在该端口上启用的每个GARP应用存在一个GARP参与者(例如，对于GMRP中该端口上的每个VLAN存在一个参与者，并且对于GVRP中的每个端口存在一个参与者)。每个GARP参与者可以既具有特定于应用的行为，又具有GARP信息声明(GID)组件，该组件可以包括一个或多个属性值，等等。属性是GARP所传播的特定于应用的信息，例如GMRP的群组MAC地址和服务要求、GVRP的VID，等等。

值得注意的是，除了GARP应用协议之外，IEEE 802.1p还说明了如何利用标记方案来允许帧被标记以优先级信息和可选的VID。优先级区分工作于流量的MAC层，并且将流量分类(分组)成不同的流量类。IEEE802.1p定义了八个类，这些类将由网络管理员手工配置(IEEE已进行了广泛的推荐)并且在整个网络中注册。作为示例，最高的优先级是7，该优先级例如可以被指派给网络关键流量，例如路由信息协议(RIP)和开放最短路径优先(OSPF)更新。值5和6可以用于对延迟敏感的应用，例如交互式视频和语音，而数据类4至1则归类于从受控负载应用(例如流式传输多媒体和业务关键流量)下至“可丢失”流量。0值用作尽力而为默认，在其他值没有被设置时该值可以被自动调用。

新的IEEE项目P802.1ak(草案5.1)确定了结合注册使用的多重注册协议(MRP)(正式名称为“Standard for Local and Metropolitan AreaNetworks Virtual Bridged Local Area Networks-Amendment 07：MultipleRegistration Protocol”)。作为对GARP的更新(或替换)，MRP允许了MRP应用中的参与者向桥接的LAN中的其他参与者注册属性。多重VLAN注册协议(MVRP)在IEEE P802.1ak中被定义为独立于支持VLAN的生成树为每个VLAN传输拓扑变化(例如，对GVRP的更新)。这使得多个VLAN可以使用单个生成树，并且在拓扑变化没有改变用于到达接收针对给定VLAN的帧的末端站的网桥端口时，无需网桥重新获知该VLAN的地址，本领域的技术人员也将明白这一点。还定义了以类似方式更新GMRP的多重多播注册协议(MMRP)。本领域的技术人员将会明白，MRP更新能够实现由于很大的网络中的一小部分的拓扑变化引起的该网络中的故障恢复时间(收敛时间)的减少和流量中断的减少。

服务带宽考虑

客户(用户)经常希望通过提供商网络(例如桥接网络)向其他客户发送流量。流量或数据“流”从源客户进入提供商网络，例如在“入口网桥”的用户-客户接口(UNI)处进入提供商网络，并且穿越提供商网络的节点(例如网桥)，以到达该流的目的地客户，例如到达远程UNI(以及“出口网桥”)。值得注意的是，如果一个提供商网络被附接到另一个提供商网络，则这些网络可以通过网络节点接口(NNI)来附接。这些客户到客户或者说“点到点”(P2P)传输(服务)可能要求使用一定量的带宽(BW)来传输数据。另一方面，“多点到多点”(MP2MP)服务是这样的服务：其中，任何数目的多个点(例如客户)可以通过网络向任何数目的其他多个点(即，多于两个UNI)发送数据流并从其接收数据流。

在一些情况下，希望例如根据特定的生成树来保证或预留沿着点之间的数据流(会话)的路径的传输所需的BW，以确保在点之间流动的流量具有足够的BW。否则，流量可能由于路径上的过多流量而被丢弃或暂停，例如由于其他流或会话而被丢弃或暂停。例如，“音频-视频桥接”(AVB)用于描述与将诸如机顶盒、收音机等等之类的视频和音频组件连接到桥接网络(例如以太网)相关联的技术。AVB中的数据流(或者“流(stream)”)可能要求一定的服务质量(QoS)以便有效地工作，例如要求一定量的BW用于该流(stream)，以及对等待时间、抖动等等的要求。运行AVB服务的应用可以请求在网络上(即，从源到目的地)为特定服务预留(注册)BW，以便保证传输正常进行(即具有足够的BW)。

如上所述以及如本领域的技术人员将会明白的，生成树的使用具有许多有用的应用。但是，许多客户设备(例如，执行AVB服务的客户设备)经常具有与网络的多个连接。例如，冗余连接可以将单个设备互连到网络，多个应用实例(例如，一个用于音频，一个用于视频，一个用于数据，等等)可以位于单个客户设备上，等等。通过利用单个生成树来将源客户连接到一个或多个目的地客户，在每个端点之间只存在一条路径。这样，来自源客户的所有数据流都利用单条生成树路径，这可能导致关键链路被流量所充满。这进而又可能增大满足服务的BW要求的难度，以及限制客户可以使用的应用服务的数目或质量。

可以通过除了IEEE Std.802.1D-2004或802.1Q-2005中描述的方法之外的方法来创建生成树。本领域的技术人员通常认可用于计算用来转发数据分组的路径的两种主要种类的算法：链路状态算法以及距离向量算法。示例性的链路状态算法例如包括在1998年4月的题为“OSPF Version 2”的请求注释(RFC)2328中描述的开放最短路径优先(OSPF)协议，以及在1990年12月的题为“Use of OSI JS-IS for routing in TCP/IP and DualEnvironments”的RFC 1195中描述的中间系统到中间系统(IS-IS)协议，这两个RFC都通过引用并入在此。另外，示例性的距离向量算法例如包括在1994年11月的题为“RIP Version 2”的RFC 1723中描述的路由信息协议(RIP)，以及MSTP(IEEE Std.802.1Q-2005)。如以上并入的属于同一申请人的共同未决的题为“METHODS AND DEVICES FORIMPROVING THE MULTIPLE SPANNING TREE PROTOCOL”的美国申请No.11/182,564以及题为“SYSTEM AND METHOD FORGENERATING SYMMETRICAL SPANNING TREES”的美国申请No.11/228,162中所述，也可以利用链路状态算法来计算通常利用MSTP计算的生成树。这里使用的这种技术被称为“最优桥接”。

在两类算法中，网桥利用更新分组(或BPDU)在彼此之间发送和接收信息，以便创建生成树。不同于距离向量算法，链路状态算法向每个网桥提供该网桥计算网络的当前拓扑的模型所需的信息，所述模型包括每一个网桥和每一个LAN。

在许多情况下，连接源端点和目的地端点的网络在其间可以具有多条路径，这多条路径可能连接到客户设备的多个连接。但是，即使在这多条路径中的一些具有可用资源(例如BW)的情况下，由于单生成树配置，它们一般也不可供客户使用。于是，这意味着如果入口网桥为客户设备使用的单个生成树不具有可用资源，则客户设备就无法满足其QoS要求(例如BW)，而不论是否存在通过网络去往(一个或多个)目的地的另一条路径。

因此，需要一种针对网络上的多条路径高效管理BW注册的技术。具体地，希望网络的网桥最优地利用网络的可用资源，而不论可用资源是否处于该网桥所使用的单个(主)生成树上。但是，同时应当维持传统的生成树技术，以便实现生成树的益处(例如，无环路环境，等等)。

发明内容

本发明涉及一种用于针对计算机网络中的多个生成树选项来高效管理带宽(BW)注册的技术。根据该新颖技术，入口网桥确定去往网络的其他网桥的多条生成树路径(即，以网络的一个或多个网桥为根的一个或多个可用生成树)，并且确定这些路径中的每一条上已利用(注册)的BW。在例如从应用源端点接收到为去往目的地端点的数据流发起BW注册的请求后，入口网桥选择生成树路径之一来用于该数据流。从多条可用路径中对生成树路径的选择例如可以按顺序基于：(i)路径的可用带宽，(ii)最短路径，以及(iii)路径的网桥根的最低网桥标识符ID。

入口网桥沿着所选择的生成树路径朝着目的地端点为数据流发送注册消息。如果注册成功，则数据流被通过所选择的路径传输。具体而言，入口网桥或者可以例如利用虚拟局域网(VLAN)标识符(VID)来告知源端点使用哪个生成树，或者可以检测数据流并自己通过所选择的生成树来引导流量。值得注意的是，如果所选择的生成树路径不是以入口网桥为根的，即不是在主生成树上而是在备用生成树上，则沿着该路径的网桥(例如，从入口网桥直到出口网桥)可以为该流量使用特殊转发(即，与传统转发相分离并且不同)，该特殊转发例如利用VID来指示主生成树或备用生成树。另一方面，如果注册失败，则入口网桥例如可以尝试在下一最佳备用生成树上注册该数据流，直到注册成功为止或者直到确定不存在更多的备用生成树为止。

有利地，该新颖技术针对计算机网络中的多个生成树选项高效地管理BW注册。通过监视多条生成树路径的BW利用(注册)，该新颖技术允许了入口网桥确定在发送数据流时要利用的最佳生成树。具体地，通过允许入口网桥基于BW利用情况选择可用的多个生成树中的任何一个，在以入口网桥为根的主生成树拥塞或由于其他原因不可用的情况下，本发明向入口网桥提供了更多的为数据流注册BW的机会。另外，该新颖技术的动态性质减轻了对繁重的手工配置的需要，并且不需要主网络BW分配设施。

附图说明

通过结合附图参考以下描述将更好地理解本发明的以上和其他优点，附图中相似的标号指示相同或功能上相似的元件，其中：

图1是根据本发明的计算机网络的概略示意图；

图2是根据本发明可以使用的示例性网桥的部分框图；

图3是根据本发明可以使用的网桥的另一个概略示意部分框图；

图4是根据本发明可以使用的传统注册PDU消息的示意框图；

图5是根据本发明可以使用的示例性数据流帧的示意框图；

图6A和6B是如图1所示的计算机网络的概略示意图示，其中示出了根据本发明的备用生成树路径；并且

图7是示出根据本发明用于针对多个生成树选项高效管理BW注册的过程的流程图。

具体实施方式

图1是根据本发明的计算机网络100的概略示意图。网络100包括具有多个互连的中间网络设备104的提供商网络120，所述中间网络设备104例如是网桥(例如，网桥A-F)。网桥通过多个局域网(LAN)106/108附接到彼此，并且附接到末端站102(例如102A和102F)。网桥104通过多个LAN 106/108互连，所述LAN 106/108可以包括共享介质或点到点链路/网段。

每个网桥104具有多个端口110(和111)，用于通过网络100接收和转发消息。另外，每个网桥104的端口可以通过端口号来标识，例如端口0(P0)、端口1(P1)、端口2(P2)等等，从而各个网桥能够到达的实体可以与用来到达它们的特定端口相关联。与仅连接到末端站而不连接到其他网桥的LAN相耦合的网桥端口111被称为“接入端口”或者用户网络接口(UNI)端口。具有UNI端口111的网桥在这里被称为为客户提供进入网络的入口或离开网络的出口的“入口网桥”或者“出口网桥”。经由LAN 106/108连接到另一中间网络设备(例如，连接到相邻网桥)的网桥端口110被称为“干线端口”。

应当明白，图1的网络100只是用于示例目的，本发明可以结合具有更简单或者可能复杂得多的拓扑的其他网络工作。

如图所示，网络100包括多个环路。对诸如IEEE Std.802.1D-2004中定义的生成树协议(STP)之类的生成树协议的执行通过在桥接网络100中定义无环路拓扑(即，活动拓扑)，从而防止了环路。例如，正如本领域的技术人员将会明白的，标识为粗线(106)的LAN(网段)是网桥A用来到达网桥F的示例性生成树路径(沿着活动拓扑)，而其他线条(108)是不在去往网桥F的路径上的LAN。传统上，网络100具有由网络的所有网桥104所共享的单个生成树。但是，在网络100中对多个生成树的使用，例如IEEE Std.802.1Q-2005中描述的多生成树协议(MSTP)描述了将多个生成树用于网络内。具体地，根据本发明的优化的MSTP(“最优桥接”)在下文中更详细描述。

图2是示例性网桥104的部分框图。如上所述，网桥具有多个端口110/111，每个端口优选地由一个号码(例如P0-P2)来标识。总地标注为202的一个或多个帧发送和接收对象与端口110/111相关联，从而在给定端口(例如P1)处接收的包括数据帧的网络消息可以被捕捉，并且网桥104要发送的帧可以被递送到给定的端口(例如P2)。帧接收和发送对象202优选是消息存储结构的，例如优先级队列。

网桥104还包括至少一个协议实体204，该至少一个协议实体204与帧发送和接收对象202处于通信关系，并且包括多个组件。具体地，协议实体204包括至少一个生成树协议(STP)引擎206以及一个或多个转发引擎208。STP引擎206优选地包括多个子组件，例如端口角色选择状态机210、端口转变状态机212和STP控制消息生成器214，等等。STP引擎206构造一组生成树实例，其中对于网络中的每个网桥有一个所述生成树实例。这些生成树实例是以与通过引用全部并入在此的IEEE Std.802.1Q-2005中相似的方式创建的，只不过使用了链路状态信息而不是距离向量信息，这在以上并入的属于同一申请人的共同未决的题为“METHODS AND DEVICES FOR IMPROVING THE MULTIPLESPANNING TREE PROTOCOL”的美国申请No.11/182,564以及题为“SYSTEM AND METHOD FOR GENERATING SYMMETRICALSPANNING TREES”的美国申请No.11/228,162中有所描述。STP引擎206包括存储器218或与存储器218处于通信关系，该存储器218可以是易失性和/或非易失性随机访问存储器(RAM)或某种其他存储器设备。存储器218优选地被组织为包括多个记录或单元(未示出)，用于存储与生成树相关的信息或参数，例如网桥的数值网桥标识符(ID)、每个端口P0-P2的注册值，等等。

一个或多个转发引擎208优选地耦合到一个或多个过滤数据库220，该一个或多个过滤数据库220存储与网络100(图1)的实体相对应的地址信息。每个过滤数据库优选地具有多个记录(未示出)，每个记录包含多个单元，其中包括目的地地址单元、目的地端口单元和相应的定时器单元。过滤数据库220中的每个记录优选地对应于一个特定的网络实体。

转发引擎208被配置为依据适当的过滤数据库220中包含的信息并且还依据由STP引擎206管理的各个端口110的生成树端口状态，来将来自源端口110的消息(例如分组和/或帧)切换或桥接到一个或多个目的地端口110。转发引擎208也与STP引擎206处于通信关系，并且可以向其转发在端口110处接收到的诸如注册(例如GARP)协议数据单元(PDU)消息之类的消息。

在图示实施例中，网桥104包括发送和接收电路，其中包括建立端口以便交换网络消息的一个或多个线路卡和/或网络接口卡(NIC)、具有中央处理单元(CPU)和/或微处理器和相关联的存储器设备以便执行计算以及存储计算结果的一个或多个监督卡，以及一个或多个总线结构。图3是网桥104的另一个概略示意部分框图，该图中示出了这种组件。如图3所示，网桥104包括多个线路卡302和304以及监督卡306。卡302、304和306通过通信总线308与彼此处于通信关系。线路卡302和304中的每一个包括微处理器(μP)310和至少一个存储器312。监督卡306也包括μP314，以及非易失性(N-V)存储器316和易失性存储器318，例如RAM。

再次参考图2，本领域的技术人员将会明白，STP引擎206和转发引擎208可以各自包括被配置和布置为产生顺序逻辑电路的寄存器和组合逻辑。在图示实施例中，引擎206和208优选是包含与这里描述的方法有关并且可由网桥104的一个或多个处理元件(例如微处理器310和/或314(图3))执行的程序指令的软件模块或者库。其他计算机可读介质也可用于存储和执行这些程序指令。然而，本领域的技术人员将会认识到可以使用软件和硬件的各种组合(包括固件)来实现本发明。

结合本发明使用的适当的中间网络设备平台包括但不限于可从SanJose，California的Cisco System，Inc.购得的一系列交换机，例如Catalyst6500、7600、3500和GRS。

如上所述，IEEE在IEEE Std.802.1D 1998版中开发了通用属性注册协议(GARP)。顾名思义，GARP提供了允许参与者作出和撤消对通用属性的声明的框架。响应于GARP声明，其他网络参与者在接收到声明的端口处注册规定属性的(一个或多个)参数值。GARP参与者还传播声明，以便网络中的其他参与者可以进行适当的注册。参与者还可以撤销其先前的声明。响应于撤消，其他参与者解除对(一个或多个)特定参数值的注册。

GARP参与者包括GARP应用组件和GARP信息声明(GID)组件。GID组件包括一组状态机，该组状态机定义了所有属性值的当前注册和声明状态。对于每个GARP应用，一般为每个端口建立一个GARP参与者。因而，对于经常具有多个端口的中间设备，建立了多个GARP参与者(230，图2)。为了作出或撤消声明，GARP参与者生成并发送被称为GARP协议数据单元(GARP PDU)消息的特殊消息。图4是传统的GARP PDU消息400的示意框图。本领域的技术人员将会明白，虽然示出了GARP PDU消息400，但是其他注册消息(例如多重注册协议、MRPPDU消息)也可用于本发明。示例性的注册消息400一般包括介质访问协议(MAC)头部402(其包括目的地和源地址字段，等等)，协议标识符(ID)字段404、多个消息字段(例如，消息字段406、408和410)以及结束标记字段412。另外，每个消息字段包括属性类型字段414和属性列表字段416。属性列表字段416进而包括一个或多个属性字段(例如，属性字段418、420和422)，以及结束标记字段424。每个属性字段(例如字段418)包括1字节的属性长度字段426、1字节的属性事件字段428以及可变长度的属性值字段430。

为了在布置于给定中间设备内的GARP参与者之间交换信息，使用一个单独的组件，该组件被称为GARP信息传播(GIP)组件(240，图2)。GIP组件工作在GIP上下文上，该GIP上下文是在中间设备处建立的并且定义了给定上下文中将要包括的端口。也就是说，虽然注册可能发生在任何端口处，但是该注册的传播只遵循相关联的GIP上下文。例如，GIP上下文可以包括属于活动拓扑的端口(即，处于转发生成树状态中的所有端口)。因为被阻止的端口不是GIP上下文的一部分，因此在被阻止的端口上接收到的声明不被传播到任何其他端口，虽然它仍在被阻止的端口处被注册。与之不同的是，在处于转发生成树状态中的端口处接收的声明既在该端口处被注册又在整个GIP上下文中被传播(即，被传播到所有处于转发状态中的其他端口)。

作为注册属性传播的一个示例，为了限制与给定VID相关联的广播、多播和单播洪泛的发送，IEEE规定基于GARP的应用在计算机网络上散布VLAN成员资格信息。被IEEE标准化的这个应用被称为GARP VLAN注册协议(GVRP)。参见IEEE Std.802.1Q-2005规范标准。根据GVRP，网桥从指派给其接入端口的VLAN的列表开始。与这些列出的VLAN相关联的所有广播、多播和洪泛的单播都需要在该网桥处被接收。GVRP为网桥提供了将其列表发送到其他网桥以便在其他网桥的干线端口处注册这些VLAN的机制。具体而言，网桥为网桥的VLAN列表中的每个VLAN生成GARP PDU消息400，该GARP PDU消息400具有属性结构，即，字段426、428和430。网桥从其每个干线端口发送GARP PDU消息400。GARP PDU消息400在相邻网桥的干线端口上被接收。假定GARP PDU消息400在处于转发生成树端口状态的端口上被接收，则接收方网桥在其所有其他也处于转发状态的端口处注册GARP PDU中包含的VLAN的列表，而不是只在接收到GARP PDU消息400的端口上注册GARP PDU中包含的VLAN的列表。相邻网桥随后生成和发送其自己的GARP PDU消息400，其自己的GARP PDU消息400不仅列出了与相邻网桥的接入端口相关联的VLAN，而且列出了由于接收到来自原网桥的GARP PDU消息而注册的VLAN。如果GARP PDU消息是在处于阻止生成树端口状态的端口处被接收到的，则GARP PDU消息中包含的VLAN在该被阻止的端口处被注册，但是它们不在任何其他网桥端口处被注册，也不被用于网桥发送的GARP PDU消息中。值得注意的是，正如本领域的技术人员将会明白并且被示例性地应用到这里描述的本发明的，可以通过与VLAN注册相似的方式在整个网络中分发其他注册的属性。

与一个或多个应用相关联的数据流或“流(stream)”(例如视频、音频、数据等等)从源端点(或者末端站)(例如，102A)穿越网络到达目的地端点(例如，102F)。图5是根据本发明可以使用的示例性数据流帧500的示意框图。作为示例，数据流帧500被实现为TCP/IP数据分组，但是本领域的技术人员将会明白，根据本发明也可使用其他适当的网络传输格式(例如，ATM帧等等)。帧500包括一个或多个头部510(例如，第2层、第3层、IP/ATM头部等等，这是本领域的技术人员将会明白的)以及数据字段520。头部510内的源地址514(例如，MAC地址)和目的地地址516(例如，一个或多个MAC地址)分别是发送方设备(102A)和(一个或多个)接收方设备(102F)的网络地址。根据这里描述的本发明，VID字段512(例如，Q标签中的VID字段，这是本领域的技术人员将会明白的)包含表示在转发帧500时将要使用的VLAN(生成树实例)的值。帧的数据字段520的数据内容一般是专有的事项，因为发送方设备将数据发送到被配置为根据一个或多个应用(例如，视频、音频等等)来解释特定数据的接收方设备。

本发明涉及一种用于在计算机网络中针对多个生成树选项来高效管理带宽(BW)注册的技术。根据该新颖技术，入口网桥确定去往网络的其他网桥的多条生成树路径(即，以网络的一个或多个网桥为根的一个或多个可用生成树)，并且确定这些路径中的每一条上已利用(注册)的BW。在例如从应用源端点接收到为去往目的地端点的数据流发起BW注册的请求后，入口网桥选择生成树路径之一来用于该数据流。从多条可用路径中对生成树路径的选择例如可以按顺序基于：(i)路径的可用带宽，(ii)最短路径，以及(iii)路径的网桥根的最低网桥标识符ID。

入口网桥沿着所选择的生成树路径朝着目的地端点为数据流发送注册消息。如果注册成功，则数据流被通过所选择的路径传输。具体而言，入口网桥或者可以例如利用VID来告知源端点使用哪个生成树，或者可以检测数据流并自己通过所选择的生成树来引导流量。值得注意的是，如果所选择的生成树路径不是以入口网桥为根的，即不是在主生成树上而是在备用生成树上，则沿着该路径的网桥(例如，从入口网桥直到出口网桥)可以为该流量使用特殊转发(即，与传统转发相分离并且不同)，该特殊转发例如利用VID来指示主生成树或备用生成树。另一方面，如果注册失败，则入口网桥例如可以尝试在下一最佳备用生成树上注册该数据流，直到注册成功为止或者直到确定不存在更多的备用生成树为止。

根据本发明，入口网桥(例如，网桥A)确定去往网络的其他网桥(例如，去往出口网桥F)的多条生成树路径。具体地，可以利用以上并入的属于同一申请人的共同未决的题为“METHODS AND DEVICES FORIMPROVING THE MULTIPLE SPANNING TREE PROTOCOL”的美国申请No.11/182,564以及题为“SYSTEM AND METHOD FORGENERATING SYMMETRICAL SPANNING TREES”的美国申请No.11/228,162中详细描述的技术来创建多条生成树路径。简言之，这里描述的技术(例如，“最优桥接”)定义了一种创建多个生成树的手段，其中网络的每个网桥是其自己的多生成树实例(MSTI)的根，并且每个网桥标识符(ID)被用作该生成树的VID。多个生成树中的每一个在网络的网桥之间是对称的，即，从第一网桥(网桥A)到第二网桥(例如，网桥F)的生成树路径与从第二网桥到第一网桥的生成树路径相同(方向相反)。

再次参考图1，假定每个网桥ID是网桥104内的字母(例如，A-F)，并且因而与每个生成树实例相对应的VID是A-F。正如本领域的技术人员将会明白的，位于网桥104的端口110附近的较小的圆圈对应于“被阻止”的生成树，或者该端口上的被阻止的VID。例如，从网桥A，在“A的生成树”(网桥A为根的生成树)上，可以看到A可以直接到达网桥B、C和D，即在网桥之间不存在阻止A的生成树的端口。另外，可以经由网桥B到达网桥F，并且可以经由网桥D到达网桥E。一旦任何数据被发送到超出网桥C和E，网桥F的端口(在圆圈中有“A”)就阻止对被标记以A的VID的数据的接收。另外，一旦数据到达网桥F(即，从网桥B)，数据不会返回任何其他网桥(B、C或E)，从而根据生成树协议防止了环路。值得注意的是，网桥A的生成树与网桥F的生成树是“对称”的，从而网桥A和F都通过网桥B到达彼此(实线，106)。其余的网桥104也具有其自己的最优生成树(即，以每个网桥作为其自己的生成树的根)，并且本领域的技术人员通过查看图1可以明白每个树是对称并且相应地是无环路的，如图所示。

根据本发明，入口网桥(网桥A)确定生成树的每个LAN(网段)上的已利用(已注册)BW。例如，各种链路状态协议可用于获知LAN(链路/网段)的能力，例如LAN的最大BW，等等。可结合本发明使用的示例性的链路状态协议包括开放最短路径优先(OSPF)协议、中间系统到中间系统(IS-IS)协议等等，这是本领域的技术人员将会明白的。作为示例，正如这里所使用的，链路状态协议可以通告“网桥到VID”指派，从而指定对于多个生成树VID值中的每一个要使用的网桥ID。由于网络100的网桥A-F中的每一个从每个其他网桥接收注册消息400，因此每个网桥可以知晓网络内的所有当前注册。例如，如这里所述，在某一网桥(例如入口网桥)处可以从网络中的其他网桥接收资源(例如BW)注册。在这些注册被接收到时，入口网桥可以确定它们的值和注册的位置并将其存储在例如存储器218中。由于具有关于链路状态信息(例如，LAN的最大BW)以及注册的信息(例如，LAN的已预留/已注册带宽)的知识，网络的每个网桥可以相应地确定网络内的每个位置处可用的(未预留的)资源的量。

在例如从应用源端点102A接收到为去往目的地端点的数据流发起BW注册的请求后，入口网桥(网桥A)选择一条生成树路径来用于该数据流。具体地，源端点102A可以生成资源预留协议(RSVP)消息来请求所预留的资源，这是本领域的技术人员将会明白的。入口网桥(A)可以通过检查在UNI端口111上接收到的消息来检测RSVP消息，并且作为响应，可以开始这里描述的注册过程。值得注意的是，应用源端点102A还可以被配置为明确地向入口网桥请求注册；但是，本发明的一个益处(正如本领域的技术人员将会明白的)在于“即插即用”能力，即无需将源端点配置为以与传统操作不同的方式操作。

值得注意的是，本发明利用了以每个网桥为根的MSTI以及基于特定VID(即，特定的生成树)的数据(例如，数据流帧500和注册消息400)的转发。本发明的一个方面因此在于下述附加能力：基于以网络中的另一网桥为根的生成树(即，不一定是以入口网桥为根的生成树)，在入口网桥处将来自源地址的帧转发到目的地地址。与“源路由”类似，本发明支持到达目的地端点(120F)的“备用生成树路径”(或“选项”)，而仍维持了生成树协议的优点。

为了进行说明，图6A和6B是如图1所示的计算机网络100的概略示意图示，其中示出了根据本发明的备用生成树路径。例如，传统上，网桥A(源120A的入口网桥)将只能利用A的生成树(“主生成树”)到达网桥F(目的地120F的出口网桥)。但是，如图6A所示，如果网桥A基于网桥C的生成树来转发帧，那么从网桥A到C再到F的“备用生成树”就可供网桥A使用。换言之，网桥F在互连到网桥C的端口上通常将会阻止来自网桥A的数据，即，基于数据消息中A的生成树的VID。但是，现在网桥A能够将网桥C的生成树VID插入到数据消息中(例如，插入到VID字段512中)，则网桥F不会再阻止该数据，因为网桥C在网桥F的端口上未被阻止。图6B示出了供网桥A到达网桥F的另一备用生成树，即通过利用网桥D(或者E)的生成树。

为了确定使用哪个生成树(例如，主生成树或备用生成树)，入口网桥(A)可以首先确定去往目的地(出口网桥)的具有可用于注册的资源的那组生成树路径。例如，假定来自源端点102A的RSVP消息请求10Mb/s。因此，入口网桥检查存储器218中由链路状态协议提供的信息的内容(例如，在链路状态数据库LSDB(未示出)中)，以确定网络的每个LAN(链路/网段)上原本可用的BW的量。然后，通过检查所存储的关于接收到的BW注册的信息(例如，如这里所述)，入口网桥可以确定在去往目的地的每条可能的生成树路径的每个LAN处的剩余可用BW。如果沿着某一路径的任何LAN(链路/网段)不符合资源要求(例如，包括RSVP消息中所请求的等待时间、丢失、延迟等等)，则该特定生成树路径不被选择。

在确定哪些生成树路径可供选择之后，入口网桥例如基于一个或多个度量来确定哪个可用生成树路径是最佳选项。注意，在基于资源要求只有单条生成树路径可用的情况下，该生成树被选择。否则，具有最低成本或距离(或者系统管理员所配置的任何其他度量)的生成树可以是关于哪条生成树路径是到达目的地(出口网桥)的最佳(例如，最短)生成树路径的决定因素。在多条生成树路径共享最佳度量(例如，“平局”)的情况下，入口网桥可以利用任何方法来选择生成树路径之一，例如，作为示例，选择以最低网桥ID(因此是最低VID)作为根的生成树路径。

在所选择的生成树路径不以入口网桥为根的情况下，即不是在主生成树上而是备用生成树上的情况下，沿着该路径的网桥可以利用特殊的转发，即与传统转发相分离并且不同。具体而言，本领域的技术人员将会明白，通过对消息(例如注册消息400或数据流帧500)进行转发，网络100的网桥104可能不正确地获知源和目的地MAC地址流量的转发(“MAC地址获知”)。例如，根据主生成树转发，网桥F已经获知了来自网桥A的流量将会从同一端口110到达并离开前往网桥B。但是，如果网桥F经由网桥C(例如，网桥C的生成树)接收到来自网桥A的流量(即，针对端点102A的源MAC地址)，那么网桥F可以为通过C的生成树以及A的生成树(或者取代A的生成树)转发的MAC地址创建两个分离的转发实例。于是，根据本发明为备用(对称)生成树利用单独的(“特殊”)的转发将会是有利的。

为了向网络100的网桥104指示出所选择的生成树VID是备用生成树而不是主生成树，可以使用各种技术。例如，可以为该流量使用一定的优先级，可以定义群组/个体比特的特殊使用，或者可以利用CEI/DEI比特用途(例如，新的以太类型)来将备用生成树流量与主生成树流量分离开来。但是，每个所述技术都可能需要对网络100进行配置改变。因此，本发明示例性地利用了VID本身。例如，本发明可以通过设置或消除VID的高位(例如，12位中的高位)来指示主生成树路径或备用生成树路径。低位(例如，剩余的11位)可用于具体标识作为特定生成树的根的网桥ID。网络的每个网桥104可以被指派两个VID，一个从值1至2047(例如，针对11个比特)，第二个是第一值加上2048(即，设置高位)。以这种方式，遇到较低的VID的网桥104可以被配置为利用传统的转发(例如，正如将会明白的，在公用FDB 220中查找和获知MAC地址)，而当遇到较高的VID时，网桥104可以被配置为利用这里描述的特殊转发。

这里使用的特殊转发基于在与流量的特定VID相对应的特定的(例如，单独的)FDB 220中的进行查找操作来转发流量(注册流量和/或数据流流量)。在本发明的一个实施例中，对于所有特殊转发VID上的数据流流量(如下所述)可以禁用MAC地址获知。此实施例中的MAC地址获知只在注册消息400的传输期间才发生。在注册被接收到时，特定FDB220被填充以与特定VID相对应的所获知的MAC地址(例如，对于每个VID有一个单独的FDB)。

在本发明的替换实施例中，并不禁用根据数据流流量的MAC地址获知，而是为这种获知定义特定的情况(例如，针对根据本发明非预留流量可以有利地利用备用生成树的情形)。例如，可以经由注册消息400提供多播MAC地址FDB条目(MAC地址获知)。(值得注意的是，本领域的技术人员将会明白，这也可以充当GMRP、MGRP、IGMP注册)。另外，单播MAC地址获知可以发生在注册期间(即，针对预留流量，例如AVB)，或者发生在数据流帧500流量期间(即，针对预留或非预留流量)。值得注意的是，在针对预留流量的单向单播流(没有返回流量)的情况下，为了避免持续地在整个所选择的生成树上洪泛流量，MAC地址获知应当发生在注册消息400分发期间(即，这至少需要临时的双向通信来选择“活动端口”，如下所述)。另外，出于同样的原因(洪泛)，以及因为不存在网桥可从中获知适当的转发的相关联的注册消息400，应当避免本发明中的利用备用生成树路径的单向非预留流量。

本领域的技术人员将会明白，防止预留流量沿着生成树的每一个LAN的持续洪泛(即，不是只沿着端点102之间的生成树路径)是尤其有利的。这种洪泛将会妨碍注册监视的高效操作，因为来自持续洪泛的过量BW可能危及对网络的不沿着该路径因而不为入口网桥所知的LAN(108)的实际利用，从而导致正在进行的注册流量的中断以及阻碍这里描述的路径选择技术的操作。因此，MAC地址获知应当可用于这里描述的备用路径流量。

值得注意的是，在本发明的示例性实施例中，所有注册流量(例如，所有AVB流量)都利用备用生成树路径VID，即，包括利用入口网桥的主生成树的流量。这样，任何将要利用主生成树路径(例如，从网桥A经由网桥B到网桥F)的注册流量都将会利用(网桥A的第二VID的)“备用生成树路径”，该“备用生成树路径”是同一物理路径(即，经由网桥B)。

一旦特定的生成树路径被选择，入口网桥就例如利用所选择的生成树的VID来沿着所选择的生成树路径朝着目的地端点为数据流发送注册消息400。作为示例，网络100的网桥104之间的带宽注册(预留)在以上并入的属于同一申请人的共同未决的美国专利申请No.11/431,429中有详细描述。根据这里描述的技术，给定服务所需的BW的量是以动态方式(例如“动态带宽控制”技术)针对提供商网络的每个端口确定的。某一服务的具有UNI端口111的每个网桥104(例如，入口网桥A)响应于从客户102A接收到注册请求(例如，利用RSVP，如上所述)而生成注册，该注册利用注册消息400(例如，GARP、MRP等等)携带该服务的最大BW值。例如，根据所请求的预留和/或服务级别协定(SLA)，该注册在以上图4的相应属性字段中携带每个端口方向的最大BW值。注册400被在整个网络中的相邻网桥之间向服务的其他UNI端口111通告(分发)(并且值得注意的是，它不被进一步通告(分发))。值得注意的是，从两个方向上接收注册的任何网桥端口110(即，已利用的生成树路径上的端口)是“活动端口”，因而相应地为特定的服务数据流分配(预留)BW(例如，与所请求的服务的RSVP“流规格”相同的流)。否则，正如本领域的技术人员将会明白的，端口只是在一个方向上接收或通告注册，而不是在任何端点(102A和102F)之间的直接路径(活动生成树LAN106)上接收或通告注册。

沿着注册消息400的路径检测到的任何故障都在转发方向上被通知。换言之，注册消息400在确定故障的网桥处被标记以“故障”指示(例如，一个比特或标志)，并且注册在网桥间继续。但是，本领域的技术人员将会明白，因为本发明示例性地基于对成功的指示(例如，根据链路状态协议和注册监视)通过生成树路径发送注册，因此拓扑变化或请求冲突(即，在两个入口网桥同时尝试注册可用BW的情况下)可能导致更多的故障。值得注意的是，“连通性优先级”(也在美国专利申请No.11/431,429中描述)可用于确定哪个发生冲突的请求应当被准予注册。例如，网桥(例如，AVG网桥)可以具有与网络的其他网桥时钟相同步的内部时钟。因此，将入口网桥处的注册生成时间用于连通性优先级可以帮助确定哪个网桥首先请求资源，并且因此应当被准予所请求的资源。正如本领域的技术人员将会明白的，根据本发明可以使用其他基于优先级的方案。另外，在所请求的资源不可用的情况下(例如，误通告的能力、对资源的其他未知利用，等等)，所尝试的注册也可能失败。当网桥接收到失败的注册时，它以与成功注册相同的方式传播该注册，但是该注册具有失败指示，并且它不为相应的数据流分配资源。当网桥接收到与该接收方网桥所发起的注册相对应(在另一方向上)的失败注册时，该网桥撤消其注册。

当入口网桥(网桥A)从相应的出口网桥(网桥F)中的每一个接收到返回的注册消息400时，注册成功。相反，如果任何其他出口网桥返回失败的注册消息400，则注册失败，并且该注册相应地被入口网桥撤消。

如果注册成功，则相应地在所选择的生成树路径上传输数据流(即，基于特定FDB 220中的VID实例，如上所述)。例如，入口网桥(网桥A)可以例如利用特定VID来告知/指示源端点102A使用哪个生成树。这样，源可以将VID包括在数据流帧500中的VID字段512中。或者，入口网桥可以不告知源端点利用哪个生成树，而是可以检测特定数据流并且自己将流量置于所选择的生成树上。也就是说，入口网桥(A)可以利用VLAN选择协议(例如，像现在并入了IEEE 802.1D-2004内的IEEE802.1v中那样)，来响应于目的地MAC地址等等向从源端点102A接收的数据流应用适当的VID(以及优先级，等等)，这是本领域的技术人员将会明白的。通过将VID插入到数据流帧500的VID字段512中，本发明在网络的边缘处保持了流标识，从而减轻了从网络内部进行此操作的要求(例如，因此，每个网桥不必基于流执行VID查找操作以确定利用哪个生成树)。

根据本发明，在完成应用服务数据流后，入口网桥可以撤消注册，并因而解除对资源(例如，BW)的预留，从而使得资源可用于未来的数据流。在注册失败的情况下，入口网桥(网桥A)以与上述相同的方式选择下一最佳生成树路径(只不过不能以失败的生成树路径作为选项)。例如，假设有充分的资源的话，入口网桥A可以不使用网桥C的生成树，而是使用网桥D(或者E)的生成树。入口网桥可以按这种方式继续尝试下一最佳备用生成树路径，直到为数据流进行了成功注册为止，或者直到不存在具有用于注册的充足资源的剩余备用生成树路径为止。在此情况下，入口网桥可被配置为向源端点(102A)返回指示出这一点的差错消息。

图7是示出根据本发明用于针对多个生成树选项来高效管理BW注册的过程的流程图。过程700开始于步骤705，并且继续到步骤710，在该步骤中入口网桥(例如，网桥A)根据上述技术确定去往网络的其他网桥(例如，网桥B-F)的多条生成树路径。例如，在计算机网络100内，每个网桥被配置为入口网桥(A)所知晓的一个生成树的根。在步骤715，入口网桥例如通过存储接收到的注册并使用链路状态协议来确定每条生成树路径的已利用(已注册)BW，如上所述。在步骤720中，入口网桥接收为从源端点(例如，源102A)到目的地端点(例如，目的地102F)的数据流发起BW注册的请求。如上所述，发起注册的请求可以是明确的请求，或者例如是对从源发送的RSVP预留请求消息的检测。作为响应，入口网桥在步骤725中选择为该数据流使用哪条生成树路径。具体地，入口网桥确定具有充足带宽用于该数据流的最佳生成树路径(例如，最短)，并且在相等度量生成树路径选项的情况下，可以选择具有最低网桥ID的生成树。

入口网桥朝着目的地102F(即，朝着出口网桥F)为数据流发送注册消息400。如上所述，沿着所选择的路径的每个网桥接收注册，并且例如可以响应于备用生成树路径的特定VID而获知要使用的MAC地址和特定端口。如果在步骤735中注册不成功(即，返回被设置的失败标志)，则在步骤740中注册被撤消，并且入口网桥在步骤745中判定是否有满足数据流的QoS(例如，BW)约束的备用生成树路径可用。如果没有，则过程700在步骤780中结束。但是，如果在步骤745中确实存在备用生成树路径，则入口网桥在步骤750中选择该备用路径，并且过程700返回到步骤730，以沿着新选择的路径发送注册消息400。

如果在步骤735中注册成功(即，未返回被设置的失败标志)(例如，由于所选择的第一个路径注册或备用路径的后续注册)，在步骤755中入口网桥则在所选择的生成树路径上为数据流发送所接收的数据。值得注意的是，沿着所选择的路径的每个其他网桥也相应地在所选择的路径上发送所接收的数据。如上所述，入口网桥可以被源端点102A明确告知所选择的路径(即，根据入口网桥最初的指示)，或者入口网桥可以扫描数据流量以确定数据流，并且将流量置于去往目的地(例如102F)的相应生成树路径上。如果在步骤760中所选择的生成树不以入口网桥为根(即，是备用生成树，而不是主生成树)，那么入口网桥(以及网络的后续网桥)在步骤750中为数据流使用特殊转发，以便与传统的转发保持分离，如上所述(例如，利用备用生成树的VID比特指示)。(值得注意的是，与上述替换示例中一样，所有预留数据流都可以利用特殊转发，即，只使用备用生成树)。不论是使用主生成树还是使用备用生成树，数据都可以继续相应地流动，直到在步骤770中服务完成，此时入口网桥可以在步骤775中撤消对服务的注册，并且过程在步骤780中结束。

有利地，该新颖技术针对计算机网络中的多个生成树选项高效地管理BW注册。通过监视多条生成树路径的BW利用(注册)，该新颖技术允许了入口网桥确定在发送数据流时要利用的最佳生成树。具体地，通过允许入口网桥基于BW利用情况选择可用的多个生成树中的任何一个，在以入口网桥为根的主生成树拥塞或由于其他原因不可用的情况下，本发明向入口网桥提供了更多的为数据流注册BW的机会。另外，该新颖技术的动态性质减轻了对繁重的手工配置的需要，并且不需要主网络BW分配设施。

虽然已经示出和描述了针对计算机网络中的多个生成树选项高效管理BW注册的示例性实施例，但是应当明白，在本发明的精神和范围内可以进行各种其他适应性改变和修改。例如，在这里利用例示IEEE网络的网桥或交换机来示出和描述了本发明，但是，本发明在其更广泛的意义上并不受此限制，而是实际上可以结合其他以太网或城域网(MAN)使用，这是本领域的技术人员将会明白的。另外，虽然该新颖技术已被示例性地描述为结合音频-视频桥接使用，但是利用预留的BW的任何数据流也可以利用这里阐述的创造性技术。另外，虽然以上描述记载了利用各种注册协议(GARP、MRP等等)来执行该技术，但是本发明同样可以利用任何适当的注册协议，这是本领域的技术人员将会明白的。

以上描述涉及本发明的特定实施例。但是，很明显，可以对所描述的实施例进行其他变化和修改，并获得其优点中的一些或全部。例如，明确设想本发明的教导可以实现为软件(包括具有在计算机上执行的指令的计算机可读介质)、硬件、固件，或者其组合。另外，可以生成电磁信号，以通过例如无线数据链路或数据网络(例如因特网)来传送实现本发明的技术方案的计算机可执行指令。因此，本说明书应当被理解为仅仅是示例性的，而不是在其他方面限制本发明的范围。因此，所附权利要求的目的是覆盖落在本发明的真实精神和范围内的所有变化和修改。