CN101268658B

CN101268658B - 产生对称生成树的系统和方法

Info

Publication number: CN101268658B
Application number: CN2006800311184A
Authority: CN
Inventors: 佛朗克斯·艾多乌尔德·塔列特; 诺曼·芬恩
Original assignee: Cisco Technology Inc
Current assignee: Cisco Technology Inc
Priority date: 2005-09-16
Filing date: 2006-09-11
Publication date: 2011-06-15
Anticipated expiration: 2026-09-11
Also published as: WO2007035307A3; US20070064628A1; WO2007035307A2; EP1925126A2; CN101268658A; EP1925126A4; EP1925126B1; US7646733B2; US8175009B2; US20100085899A1

Abstract

一种系统和方法建立了网络(200)中的多个对称的生成树。网络中的桥接器(302)生成、发送并处理生成树协议(STP)控制消息，当该STP控制消息穿过网络传播时更新该消息(100)来反应其遵循的路径。并且，桥接器使用接收到的STP控制消息的路径指示值来计算生成树。路径指示值优选地从对应于桥接器的桥接器标识(ID)之和导出，通过该桥接器STP控制消息从根桥接器(202)传递给当前的处理STP控制消息的桥接器。每一个桥接器还对新接收到的消息打上与以该桥接器为根的生成树相关的虚拟局域网(VLAN)标识符(VID)的标签，从而使得消息沿着更佳路径穿过网络。

Description

产生对称生成树的系统和方法

技术领域

本发明一般涉及计算机网络，更具体地涉及一种有效地穿过网络传输消息的方法和装置。

现有技术

包括商业、政府和教育机构在内的很多组织使用计算机网络，从而雇员和其他人可以共享并交换信息和/或资源。计算机网络典型地包括通过一个或多个通信媒介相互连接的多个实体。实体可以由在通信媒介上“供给”(即发送)或“吸收”(即接收)数据帧的任何设备组成，所述设备例如是计算机。一种常见形式的计算机网络是局域网(“LAN”)，“LAN”典型地是指在单个建筑或者校园中的私有网络。LAN典型地采用诸如以太网或者无线协议这样的、用于定义通信体系结构(即协议栈)的数据链路和物理层执行的功能的数据通信协议(LAN标准)。

一个或多个中间网络设备经常用来将LAN连接在一起，并且允许对应的实体来交换信息。例如，桥接器可以用来提供两个或多个LAN或者终端站之间的“交换”功能。典型地，桥接器是计算机，并且包括多个端口，所述多个端口通过LAN与其他桥接器连接，或者与诸如路由器或者主计算机这样的终端站连接。用来将桥接器相互连接的端口一般被称之为主干端口，而用来将桥接器连接到终端站的端口一般被称之为接入端口。桥接功能包括在源端口从发送实体接收数据，并且将这些数据发送该给至少一个目的地端口，来转发给一个或多个接收实体。

生成树(Spanning Tree)算法

大多数的计算机网络包括冗余通信路径，从而任何一个给定链路的故障不会隔离网络的任何部分。这种网络典型地被称之为网状网或者部分网状网。但是，冗余链路的出现可以引起网络中迂回路径或者“环路”的形成。由于数据帧可能无限地遍历环路，因此环路是非常不希望的。

而且，诸如桥接器或者交换机这样的一些设备复制目的地未知的帧，导致沿着环路数据帧的增殖。产生的信息量将淹没网络。诸如路由器这样的、工作在协议栈中的较高层(诸如传输控制协议/网际协议(“TCP/IP”)参考模型的网络层)的其他的中间设备与大多数桥接器或交换机不同地传递数据帧并得知网络上实体的地址，因此路由器一般不受持续环路问题的影响。

为了避免环路的形成，大多数桥接器和交换机执行允许其计算无环路的活动网络拓扑(即树)，并且还连接网络中的每一对LAN(即树是生成的)的生成树协议。IEEE公布了用于定义了802.1D兼容设备执行的生成树协议的标准(IEEE Std.802.1D-1998^TM)。一般，通过执行802.1D生成树协议，桥接器将桥接网络中的一个桥选择为“根桥接器”(RootBridge)。802.1D标准通过指定根桥接器是带有最低桥接器ID的桥接器，从而有利地利用每一个桥接器具有唯一的数字标识符(桥接器ID)这一事实。另外，对于连接到任何桥接器的每一个LAN，选择正好一个桥接器(“指定桥接器”)上的一个端口(“指定端口”)。指定桥接器典型地是根桥接器最接近的桥接器。在根桥接器上的所有端口是指定的端口，并且根桥接器是在其具有端口的所有LAN上的指定桥接器。

每一个非根桥接器还从其非指定端口中选择给出到根桥接器的最低成本路径的一个端口(其“根端口”)。选择根端口和指定端口以将其包括在活动拓扑中，并且根端口和指定端口被置于转发(forwarding)状态，从而数据帧可以转发给这些端口及从这些端口转发，并因此转发到将网络的桥接器终端站互连的LAN上。不包括在活动拓扑中的端口设置在阻止(blocking)状态。当端口处于阻止状态时，数据帧将不会转发给端口或者从端口接收。网络管理者还可通过将端口置于禁用(disabled)状态而从生成树排除端口。

为了获得运行生成树协议所必需的信息，桥接器交换专门的消息，该消息称为配置桥接器协议数据单元(BPDU)消息，或者简称BPDU。BPDU携带诸如假定的根和最低根路径成本这样的、用于计算活动拓扑的信息。更加具体地，在启动时，每一个桥接器初始假定其本身为根桥接器，并且相应地发送BPDU。在从邻近设备接收到BPDU后，检查其内容，并且与接收桥接器存储在存储器中的相似信息比较(如假定的根和最低根路径成本)。如果来自接收到的BPDU的信息比存储的信息“更好”，则桥接器采用该更好的信息并且将该信息用在该桥接器从其除了接收到该“更好”信息的端口之外的端口发送的BPDU中(给根路径成本加上与接收端口相关的成本)。尽管桥接器不转发BPDU，但是如上所述，根桥接器的标识符最终传播给所有的桥接器并且被所有的桥接器采用，从而允许它们选择其根端口和任何(一个或多个)指定端口。

为了使活动拓扑适应于改变和故障，根桥接器周期性地(如每个hellotime)发送BPDU。响应于在其根端口上接收到BPDU，桥接器从其指定端口(如果有的话)发送它们自己的BPDU。因此，BPDU周期性地通过桥接的网络传播，从而确认活动拓扑。当更新BPDU信息和/或BPDU信息超时，并且重新计算活动拓扑时，端口可以从阻止状态转换为转发状态，反之亦然。即，新的BPDU信息导致先前阻止的端口可以得知其应当处于转发状态(如，该端口现在是根端口或者指定端口)。

快速生成树协议

近来，IEEE发布了802.1D标准的新版本，称为IEEE Std.802.1D-2004，该标准描述了由在其他方面与802.1D兼容的设备执行的快速生成树协议(RSTP)。RSTP类似地选择桥接网络的一个桥接器为根桥接器，并且定义在切断任何环路的同时提供LAN之间的完整连接的活动拓扑。每一个桥接器的每一个单独的端口都根据端口是否是活动拓扑的一部分而分配端口角色。802.1D-2004标准定义的端口角色包括根(Root)、指定(Designated)、可替换(Alternate)和后备(Backup)。向提供对根的最好(例如最低)成本的路径的桥接器端口分配根端口角色。向提供对根的可替换的(例如较高)成本路径的每一个桥接器端口分配可替换端口角色。向从给定LAN提供最低成本路径的每一个桥接器端口分配指定端口角色，而向以回送(loop-back)方式连接到给定LAN的所有其他端口分配备用端口角色。

已经被分配了根端口和指定端口角色的那些端口被设置在转发状态，而分配为可替换和备用角色的端口设置在一种状态。如果分配为可替换端口角色的所有端口设置在阻止状态，则分配为根端口角色的端口能快速地转换为转发状态。同样地，如果在当前分配为根端口角色的端口上出现故障，假定之前的根端口已经转换为丢弃或者阻止状态，则分配为可替换的端口角色的端口能被重新分配为根端口角色，并且快速地被转换为转发状态。将被重新分配为指定端口角色的分配为指定端口或者后备端口角色的端口可以快速转换为转发状态，如果下游桥接器的端口的角色与被分配指定端口角色的该端口一致的话。RSTP提供邻近桥接器使用的显式的握手来确认新的指定端口能快速地转换为转发状态。

像在802.1D规范标准的1998版本中描述的STP一样，运行RSTP的桥接器还交换BPDU，以确定哪些角色分配给桥接器端口。BPDU还用在用来快速地将指定端口转换为转发状态的握手中。

虚拟局域网

计算机网络还可以分割成一系列的逻辑网络。例如，在1995年2月28日授权给Ross的美国专利号5,394,402(“’402专利”)公开了一种将交换机的任何一个端口与任何一个特定的网段相关的装置。具体地，根据’402专利，特定的交换机的任何数目个物理端口可以通过使用虚拟地将端口与特定VLAN名称相关联的虚拟局域网(VLAN)设置而与交换机中的任何数目个组相关。更加具体地，交换机或者集线器(hub)将VLAN名称与其端口相关联，并且还将那些VLAN名称与从VLAN名称已经分配到的任何一个端口发送的消息相关。

每一个端口的VLAN名称存储在交换机的存储器部分，从而每次在给定的接入端口上接收到消息时，该端口的VLAN名称与该消息相关联。基于接收到消息的具体接入端口，通过在存储器部分中查找VLAN名称的流处理元件完成所述关联。在很多情况中，可能希望将这些交换机中的多个交换机互连以扩展网络中的端口的VLAN关联。那些具有相同的VLAN名称的实体好像它们都是相同的LAN的部分一样地工作。VLAN配置的桥接器被特殊配置来防止具有不同的VLAN名称的网络的部件之间的消息交换，以保持每一个VLAN的边界。但是，工作在L2以上的中间网络设备(如路由器)能在不同的VLAN段之间中继消息。

除了’402专利以外，IEEE也公布了用于虚拟桥接局域网的802.1Q规范标准。为了保护跨越VLAN感知网络中的主干或者链路传输的消息的VLAN关联，Ross和IEEE Std.802.1Q-2003规范标准都公开了将VLAN标识(VID)域附加到相应的帧上。另外，与本申请属于同一所有者的授权给Edsall等人的美国专利号5,742,604(“’604专利”)公开了当维护帧的VLAN关联时，用于在交换机之间有效地传输分组或者帧(包括VLAN修改后的帧)的交换机间链路(ISL)封装机制。具体地，可以使用快速以太网标准的ISL链路连接在每一个交换机上设置的ISL接口电路。发送ISL电路封装在ISL头部和ISL误差检测信息中传输的帧，而ISL接收电路剥开该信息并恢复原始帧。

多生成树协议

在IEEE Std.802.1Q-2003中，IEEE还包括特定设计来与支持VLAN的网络一起使用的生成树协议的规范标准。在IEEE Std.802.1Q-2003的补充IEEE 802.1s中描述的多生成树协议(MSTP)将桥接网络组织成区域。在每一个区域中，MSTP建立用于提供对各个区域中的所有桥接器和对建立在其他区域中的内部生成树(IST)的连接的IST。在每一个MSTP区域中建立的IST还提供了与由运行STP或者RSTP的IEEE Std.802.1Q-1998兼容桥接器建立在MSTP区域外面的一个公共生成树(CST)的连接。给定的MST区域的IST接收并发送BPDU给CST。因此，桥接网络的所有桥接器通过单一的公共内部生成树(CIST)来连接。而且，从传统的或者IEEE Std.802.1Q-1998桥接器的角度来看，每一个MST区域作为CST上的单一的虚拟桥接器而出现。

在每一个MST区域中，MSTP兼容的桥接器建立了多个活动拓扑，其中的每一个活动拓扑被称为多生成树实例(MSTI)。MSTI桥接器还将每一个VLAN分配或者映射至MSTI的一个并且仅仅一个中。由于VLAN可以分配给不同的MSTI，因此与不同的VLAN相关的帧可以采用通过MSTP区域的不同路径。桥接器可以，但一般不可以，计算每一个单一的VLAN的分开的拓扑，从而保存处理器和存储器资源。每一个MSTI基本是仅仅存在于各自的区域中的简单的RSTP实例，并且MSTI与区域外部进行交互。

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

运行MSTP的每一个桥接器还具有由三个属性组成的单一MST配置标识符(ID)，所述三个属性是：混合符的(alphanumeric)配置名称、版本级别和将可能的4096VLAN中的每一个与相应的MSTI相关联的VLAN映射表。而且每一个桥接器将其MST配置ID加载进桥接器所发起的BPDU中。因为桥接器仅仅需要了解桥接器是否在相同的MST区域中，所以它们不在其BPDU中传播实际的VLAN对MSTI表。实际上，MST BPDU仅携带VLAN对MSTI表的摘要或者映射。摘要是通过将众所周知的MD-5算法应用于VLAN对MSTI表而产生的。当桥接器接收到MST BPDU时，其提取出包含在其中的MST配置ID，包括摘要，并且将其与自己的MST配置ID比较来确定是否同发送MST BPDU的桥接器一样在相同的MST区域中。如果两个MST配置ID是相同的，则两个桥接器是在相同的MST区域中。但是如果两个MST配置ID具有至少一个非匹配的属性，即不同的配置名称、不同的版本级别和/或不同的计算的摘要，则接收到BPDU的桥接器推断出其处于不同于发起BPDU的桥接器的不同的MST区域中。并且，如果指定的桥接器是在不同的MST区域中或者如果端口接收传统的BPDU，则MST桥接器的端口被认为是在MST区域的边界上。

图1是IEEE Std.802.1Q-2003的MST BPDU 100的高示意性框图。MST BPDU 100包括与各个LAN标准(如以太网)的媒体访问控制(MAC)层兼容的头部102。头部102包括目的地地址(DA)域、源地址(SA)域、目的地服务接入点(DSAP)域和源服务接入点(SSAP)域，等等。DA域携带分配给生成树协议的唯一的桥接器组播目的地地址，并DSAP和SSAP域携带分配给生成树协议的标准化标识符。附加在头部102上的是包括“外部”部分104和“内部”部分106的BPDU消息区域。外部部分104具有与RST BPDU消息相同的格式，并且被不实施MSTP的桥接器识别为有效的RSTP BPDU消息。“内部”部分106由执行MSTP的桥接器用来建立IST和MSTI。内部部分106具有用于IST的一组生成树参数，如生成树优先级向量，还具有发起MSTP BPDU 100的桥接器所支持的每一个MSTI的一组参数。

还被称之为CIST优先级向量的外部部分104具有多个域，包括协议标识符(ID)域108、协议版本ID域110、BPDU类型域112、CIST标志域114、CIST根ID域116、CIST外部路径成本域118、CIST区域根ID域120、CIST端口ID域122、消息年龄域124、最大(MAX)年龄域126、hello时间域128和转发延时域130。CIST根标识符域116包含假定为公共内部生成树的根的桥接器的标识符，该桥接器可能位于与发起BPDU消息100的桥接器相同的MSTP域中、在其他MSTP域中，或者在不运行MSTP的桥接网络的部分中。CIST外部路径成本域118包含表示从发起BPDU 100的桥接器至在域116中标识的CIST根的、不穿过与发起BPDU消息100的桥接器相同的域中的任何其他桥接器的最低成本的值。

还被称之为MSTI优先级向量的内部部分103相似地具有多个域，包括版本1长度域132(该域典型地设置为空)、版本3长度域136、MST配置ID域138、CIST内部根路径成本域140、CIST桥接器ID域144和CIST剩余跳域150。内部部分106还包括一个或多个可选的MSTI配置消息152，每一个MSTI配置消息构成另一MSTI优先级向量或者M-记录。

因为RSTP版本2没有指定除了那些已经由版本1指定的之外的任何额外的域，因此MST BPDU没有版本2长度域。

如上面提及的，MST配置ID域138是由三个子域构成的：配置名称子域154、版本级别子域156和MD-5校验和子域158。配置名称子域154携带用固定大小如32字节编码的可变长度文本串。版本级别子域156携带在两个字节的固定域中编码的整数。MD-5校验和子域158携带通过应用MD-5算法至桥接器的VLAN对MSTI表而建立的16字节签名，所述表包含4096个连续的两字节元素。

每一个MSTI配置消息152由包括MSTI标志域160、MSTI区域根ID域162、MSTI内部根路径成本域164、MSTI桥接器优先级域166、MSTI端口优先级域168和MSTI剩余跳域170的多个域组成。MST桥接器使用包含在内部部分106的域140-150中和每一个MSTI配置消息152中的STP参数，来计算配置在各自区域中的每一个MSTI的活动拓扑。

尽管STP防止了桥接网络中的环路的形成，但是它可能引起不理想的路径的建立。图2是桥接网络200的高示意性说明。网络200包括六个桥接器202a-f，每一个桥接器具有多个端口(未示出)。桥接器202a-f由网段204互连，所述网段例如是共享的介质或者点对点的链路。假定桥接器202a被选为网络200的根。STP的执行将会引起桥接器202b来阻止其端口中的一个，来防止网络200中的环路形成。假定桥接器202b确定其连接桥接器202f的端口被阻止，如在图2指示为“X”。因此STP的执行防止了网络200中的环路的形成。但是，从桥接器202b去向桥接器202f的数据消息使用的路径远远不是最佳的。具体地，在桥接器202b接收到的例如来自其所连接的局域网(LAN)(未示出)且发送给桥接器202f的数据消息通过桥接器202e、202d、202a和202c路由。由于桥接器202b和202f相邻，这种绕远的路径显然不是理想的。实际上，这种情形导致了延时和浪费带宽。

发明内容

简言之，本发明涉及用于在桥接网络中建立多个对称生成树的系统和方法。桥接器协作来通过网络建立多个生成树实例。在示例性实施例中，桥接器形成与存在的桥接器相同数目个生成树，从而每一个桥接器是一个生成树实例的根。桥接器还协作来确保每一个生成树实例定义的路径在网络中的每一对桥接器之间是对称的。当网络消息由网络中的第一桥接器接收到时，该桥接器在以其为根的生成树实例上转发该消息。具体地，桥接器可以用与该生成树示例相关的虚拟局域网(VLAN)标识符(VID)给消息加标签，并且将该消息转发进网络中。因此打标签的消息遵循从最初接收该消息的桥接器到其目的地的更好的路径。

为了建立对称生成树，桥接器生成、发送并处理新颖的生成树协议(STP)控制消息。根据本发明，STP控制消息包括新的域，当消息穿过网络传播时，更新该消息来反应消息所遵循的路径。并且，桥接器使用该新路径指示域中的值作为用来计算活动拓扑的生成树优先级向量的一部分。具体地，网桥接器注意路径记录的值以在两个或者更多个可能的根端口中选择，每一个可能的根端口具有到根的相同的成本。在示例性实施例中，路径记录携带从与STP控制消息从根桥接器传递至处理STP控制消息的当前桥接器所经过的桥接器相对应的桥接器标识符(ID)的和导出的值。因为沿着两个桥接器间的给定路径的桥接器ID之和在两个方向上相同，所以在选择根端口中的新路径记录的使用确保了每一对桥接器之间的生成树将会是对称的。

附图说明

本发明说明书将参见下面的附图，其中：

图1之前讨论过，它是多生成树协议的传统的配置桥接器协议数据单元的示意性框图；

图2之前讨论过，它是现有技术网桥接网络的高示意性说明；

图3是本发明优选实施例的桥接网络的高示意性说明；

图4和图5是本发明优选实施例的中间网络设备的部分框图；和

图6是本发明优选实施例的生成树协议控制消息的高示意性框图。

具体实施方式

图3是本发明计算机网络300的高示意性说明。网络300包括多个相互连接的中间网络设备302a-f。设备302a-f优选地是桥接器。网络实体(未示出)附接到桥接器302a-f，所述网络实体例如是局域网(LAN)和/或终端站。桥接器302a-f是由多个段304互连的，所述段可以是共享的介质或者点对点链路。

每一个桥接器302具有多个端口310来通过网络300接收并转发消息。并且，每一个桥接器302的端口可以例如通过端口号识别，如端口0(P0)、端口1(P1)、端口2(P2)等，从而各个桥接器能到达的实体可以与用来到达它们的特定端口相关联。直接与终端站或没有连接桥接器的LAN的桥接器端口被称之为“接入端口”。与其他中间网络设备，例如与相邻桥接器连接的桥接器端口310被称之为“主干端口”。

应当理解的是图3的网络300仅仅是用于示例性目的，并且本发明将会与具有可能更加复杂的拓扑的其他网络一起操作。

如图所示，网络300包括环路。对诸如在IEEE Std.802.1D-2003中定义的生成树协议之类的生成树协议的执行通过定义桥接网络300中的无环路拓扑(即活动拓扑)来防止环路。

而且，在IEEE Std.802.1Q-2003版本中定义的快速生成树协议(RSTP)或者多生成树协议(MSTP)的执行将允许作为活动拓扑一部分的交换机302的端口310快速地转换为转发状态，从而能以最小中断和/或时延来转发网络消息。但是，如上面所述，在一些情形中，RSTP和MSTP的当前实施方式会引起一些低效率。为了避免这些低效率，以及由于其他原因，网络300的桥接器302被配置来建立网络300中多个对称的生成树。

图4是桥接器302b的部分框图。如上面所指示的，该桥接器具有多个端口310a-c，其中每一个端口优选地由数字标识(如P0-P2)。一般地用402指示的一个或多个帧传输和接收对象与端口310a-c相关联，从而包括数据帧的在给定端口(如P1)上接收的网络消息可以被捕获，并且桥接器302b发送的帧可以传递到给定的端口如P2。帧接收和发送对象402优选地是消息存储结构，如优先级队列。

桥接器302b还包括至少一个协议实体404，该实体404与帧发送和接收对象404是通信关系，并且包括多个部件。具体地，协议实体404包括至少一个生成树协议(STP)引擎406，以及一个或多个转发引擎408。STP引擎406优选地包括多个子部件，包括端口角色选择状态机410、端口转换状态机412和STP控制消息发生器414。STP引擎406基本地遵守作为IEEE Std.802.1Q-2003的补充的IEEE 802.1S多生成树协议(MSTP)来操作，并通过本申请中描述的新颖的改进而扩展，在此通过引用将该补充完全地并入本文中。STP引擎406包括存储器418或者与存储器418是通信关系，该存储器418可以是易失性的和/或非易失性的随机存取存储器(RAM)或者一些其他的存储设备。存储器418优选地组织来包括多个记录或者单元(未示出)，来存储诸如桥接器的数字桥接器标识符(ID)、每一个端口310a-c的分配的路径成本、每一个端口P0-P2的当前或者“最好”生成树信息这样的生成树相关的信息或者参数。

一个或者多个转发引擎408优选地与用于存储对应于网络300(图3)的实体的地址信息的一个或多个过滤数据库420连接。每一个过滤数据库优选地具有多个记录(未示出)，每一个记录包含多个单元，所述多个单元包括目的地地址单元、目的地端口单元和对应的定时器单元。过滤数据库420中的每一个记录优选地对应于特定的网络实体。

转发引擎408被配置来根据包含在合适的转发数据库420中的信息，以及根据STP引擎406所管理的各端口310的生成树端口状态，来从源端口310向一个或多个目的地端口310交换或者桥接消息，所述消息例如是分组和/或帧。转发引擎408还与STP引擎406是通信关系，并且可以向STP引擎406中继在端口310上接收的STP控制消息，所述STP控制消息例如是MSTP桥接器协议数据单元(BPDU)消息。

在所示的实施例中，桥接器302b包括发送和接收电路，所述电路包括一个或多个建立用于交换网络消息的线路卡和/或网络接口卡(NIC)，具有用于执行计算及存储计算结果的中央处理单元(CPU)和/或微处理器和相关的存储器设备的一个或多个监督卡，以及一个或多个总线结构。图5是说明这些部件的桥接器302b的另一个高示意性的部分框图。如图5中所示，桥接器302b包括多个线路卡502和504，以及监督卡506。卡502、504和506通过通信总线508相互是通信关系。线路卡502和504的每一个包括微处理器(μP)510和至少一个存储器512。监督卡506还包括μP 514，以及非易失性(N-V)存储器516和易失性存储器518如RAM。

再次参见图4，本领域技术人员应当理解STP引擎406和转发引擎408每一个可包括配置并安排来产生序列逻辑电路的寄存器和组合逻辑。在所示实施例中，引擎406和408优选是包含与本申请中描述的方法相关的、且可由桥接器302b的一个或多个处理元件例如微处理器510和/或514(图5)执行的程序指令的软件模块或者库。其他计算机可读介质也可以用来存储并执行这些程序指令。但是，本领域普通技术人员将意识到软件和硬件(包括固件)的各种组合可以用来实施本发明。

与本发明一起使用的合适的中间网络设备平台包括但并不限于加利福尼亚圣何塞的思科系统公司的商业上可获得的系列交换机，例如Catalyst4000和6000。

如在此描述的，网络300的桥接器302配置来通过网络300建立多个生成树实例。在所示实施例中，它们针对每一个桥接器建立一个生成树实例，其中每一个桥接器是一个生成树实例的根。每一个桥接器302还配置来转发沿着以该桥接器为根的生成树实例在其接入端口中的一个上接收的消息。在这种方式中，遍历网络300的消息遵循更有效的路径。

由于桥接器典型地基于其接收到来自网络中另一设备的帧的桥接器端口而得知使用哪一个端口来到达该设备，因此每一对桥接器定义的活动拓扑需要是对称的。否则可能引起通信丢失。因此，桥接器302进一步地配置为使得与每一对桥接器相关联的两个生成树实例是对称的。当一对桥接器中的任何一个发起的消息遵循的路由相同，即两个消息穿过同一组中间桥接器，但是彼此是相反顺序的时候，这两个生成树实例被认为是对称的。

为了确保每一对生成树实例是对称的，配置网络300的桥接器302以使得：第一，给定段的路径成本对连接到该段的所有桥接器是相同的，第二，交换和处理新颖的STP控制消息。在一个实施例中，网络管理者手动配置网络300的桥接器302，从而与给定网段连接的所有桥接器具有分配给该段的相同的路径成本。本领域技术人员应该理解可以使用除了手工配置之外的其他技术。例如，信息分发协议可以用来传达路径成本。

传统的MSTP BPDU消息100(图1)包括多个MSTI配置消息152；对于MSTP BPDU 100携带的信息所关于的每一个生成树实例有一个MSTI配置消息152。根据本发明，新颖的STP控制消息是通过修改每一个MSTI配置消息来携带路径跟踪或者记录信息而形成的。当穿过网络300传播STP控制消息时，更新STP控制消息来反映传播该消息所通过的每一个桥接器。

图6是STP控制消息600的优选格式的高示意性说明。STP控制消息600包括头部602，头部602优选地与诸如以太网这样的各LAN标准的媒体访问控制(MAC)层兼容，并且对应于MSTP BPDU 100的头部102(图1)。附加在头部602上的是“外部”部分604，该部分604具有与MSTP BPDU的外部部分104(图1)相同的格式。即，外部部分604对应于RSTP BPDU消息，并且被不实施MSTP或者对MSTP的生成树路由扩展的桥接器认为是有效的RSTP BPDU消息。STP控制消息600进一步地包括由桥接器302用来建立IST和对称的MSTI的“内部”部分606。内部部分606优选地包括版本1长度域608、版本3长度域610、MST配置ID域612、CIST内部根路径成本域614、CIST桥接器ID域616、CIST剩余跳域618和多个MSTI配置消息620。

进一步如图6所示，每一个MSTI配置消息620优选地包括MSTI标志域622、MSTI区域根ID域624、MSTI内部根路径成本域626、路径跟踪域628、MSTI桥接器优先级域630、MSTI端口优先级域632和MSTI剩余跳域634。

参见图3，桥接器302生成STP控制消息600，用以从其端口发送。在STP控制消息600中，桥接器302a插入用于生成树实例的MSTI配置消息602，桥接器302a是该生成树实例的根。桥接器302a如IEEE 802.1Q中规定的加载该MSTI配置消息620的MSTI标志域622。由于该MSTI配置消息620对应于以桥接器302a为根的生成树实例，因此该MSTI配置消息620在MSTI区域根ID域624中输入其自己的桥接器ID值，并且设置MSTI内部根路径成本域626为空或者零。根据本发明，桥接器302a还设置路径跟踪域628为空或者零，这是因为该MSTI配置消息是由桥接器302a产生的，并且还未穿过任何一个桥接器302。优选地根据传统的MSTP加载域630-634。桥接器302a然后从其端口310发送STP控制消息600。

桥接器302a的一个或多个STP控制消息由桥接器302c和桥接器302d接收。桥接器302c用其与桥接器302a之间的路径的成本与包含在根路径成本域626中的当前值之和来替代该当前值。桥接器302c还更新路径跟踪域628的值，来指示该STP控制消息600已经通过桥接器302c传播。在一个实施例中，桥接器302c更新路径跟踪域628如下：第一，桥接器302c应用哈希函数至其桥接器ID值，以生成哈希桥接器ID值。桥接器ID典型地是64位长的。最前4位是可设置的优先级部分，接着12位指定生成树实例，最后48位是桥接器的全局唯一的MAC地址，如端口P0的MAC地址。哈希函数可应用于整个64位桥接器ID。可替换地，哈希函数可应用于桥接器ID的仅一部分，例如48位的MAC地址或者其他某个域或者域的组合。

在优选实施例中，哈希函数产生小于64位的值。但是，在可替换的实施例中，哈希函数可以产生大于64位的输出。

在产生哈希桥接器ID值后，桥接器302c用该哈希值和路径跟踪域628的当前值之和来替换路径跟踪域的当前值。桥接器302c优选地如IEEE Std.802.1Q-2003所指定的那样来修改域630-634的值。桥接器302c然后将修改的STP控制消息600从其端口310传播。

本领域的技术人员将会理解可以采用任何数目的众所周知的哈希函数，例如循环冗余校验(CRC)、安全哈希算法(SHA)、消息摘要算法4或5(MD4或MD5)、欧洲先进通信技术研发完整性基元评估消息摘要(RIPEMD)。

桥接器302d相似地修改从桥接器302a接收到的STP控制消息600，然后从其自己的端口310传播该消息。但是，桥接器302d通过对其桥接器ID进行哈希运算而更新路径跟踪域，并且将该哈希的桥接器ID值加至当前的路径跟踪值上，以建立域628的新的路径跟踪值。该过程由桥接器302e和302f重复，该桥接器302e和302f更新其接收的STP控制消息600的路径跟踪域628。具体地，桥接器302e通过对其桥接器ID进行哈希运算而更新路径跟踪域628，并将该哈希值加至当前路径跟踪值上。桥接器302f通过对其桥接器ID进行哈希运算和将该哈希值加至当前路径跟踪值上，相似地更新路径跟踪域628。

桥接器302b接收用于以桥接器302a为根的生成树实例的两个MST配置消息620。第一MST配置消息620从桥接器302e接收，并且在其路径跟踪域628中具有反映了该MST配置消息620通过桥接器302d和302e传播的值。第二MST配置消息620从桥接器302f接收。其在路径跟踪域628中携带反映了该MST配置消息620通过桥接器302c和302f传播的值。桥接器302b使用来自这两个MST配置消息的值来选择其用于以桥接器302a为根的生成树实例的根端口。首先，桥接器302b确定是否接收到的MST配置消息620之一指定了对根，即对桥接器302a的比另一MST配置消息620更低成本的路径。如果这样，则桥接器302b选择提供对根，即对桥接器302a的最低成本路径的端口为其根端口。假定MSTI配置消息620指定的路径成本是相同的。在传统的MSTP操作下，桥接器302b将随后注意域601中携带的发起这两个MSTI配置消息的桥接器的桥接器ID以选择其根端口，即桥接器302e和302f的桥接器ID。

但是，桥接器302b的STP引擎406不是注意源桥接器ID，而是配置来使用路径跟踪域628的值来选择其根端口。即，根据本发明，在两个或多个端口的根路径成本相同的情形下，STP引擎406选择接收到带有最低路径跟踪值的MSTI配置消息620的端口为其根端口。假定来自桥接器302e的MSTI配置消息具有比来自桥接器302f的MST配置消息620携带的路径跟踪值低的路径跟踪值。桥接器302b通过选择连接到桥接器302e的端口作为用于以桥接器302a为根的生成树实例的根端口，来做出响应。作为响应，端口角色选择状态机410将该端口分配为根端口角色，并且端口转换状态机将该端口转换为转发状态。连接到桥接器302f的端口被分配为可替换端口角色，并且转换为阻止状态，如“X”所示。

本领域技术人员应当理解，桥接器302a-f的STP引擎可以不使用最低路径跟踪值，而是配置来使用最高路径跟踪值选择根端口。相似地，本领域技术人员将理解除了求和以外的不同的功能可以用于更新路径跟踪记录域。

桥接器302a相似地接收最初由桥接器302b生成的用于以桥接器302b为根的生成树实例的两个MSTI配置消息620。第一个这种MSTI配置消息在其路径跟踪域628中携带指示消息是穿过桥接器302f和302c传播的值，而第二MSTI配置消息620在其路径跟踪域628中携带指示消息是穿过桥接器302e和302d来传播的值。与桥接器302b的情况一样，桥接器302a当选择其用于以桥接器302b为根的生成树实例的根端口时，也依赖于包含在这两个路径跟踪域中的值。桥接器302a注意路径跟踪域628携带的值，这是因为用于其去向桥接器302b的两个端口310的根路径成本是相同的。

重要的是，包含在接收自桥接器302d的MSTI配置消息620的路径跟踪域628中的值比接收自桥接器302c的MSTI配置消息620的路径跟踪域628低。这种情况是因为不管各STP控制消息采用的方向如何，路径跟踪值是相同的。即，(桥接器302d的桥接器ID的哈希)+(桥接器302e的桥接器ID的哈希)等于(桥接器302e的桥接器ID的哈希)+(桥接器302d的桥接器ID的哈希)。相似地，(桥接器302c的桥接器ID的哈希)+(桥接器302f的桥接器ID的哈希)等于(桥接器302f的桥接器ID的哈希)+(桥接器302c的桥接器ID的哈希)。因此，桥接器302a选择其连接到桥接器302d的端口作为其用于以桥接器302b为根的生成树实例的根端口。因此，该端口分配给根端口角色，并且转换为转发状态。连接桥接器302c的端口分配为可替换端口角色，并且转换为阻止状态，如“X”所示。

如图所示，使用本发明的路径跟踪特征可以确保以网络300的任何一对桥接器302为根的生成树将是对称的。

在优选实施例中，网络300还配置为使得每一个生成树实例被分配了对应的VLAN ID(VID)。当桥接器302在其接入端口中的一个上接收消息时，优选地桥接器用分配给以该桥接器为根的生成树实例的VID给所述消息加标签。在这种方式中，消息沿着以最初接收到该消息的桥接器为根的生成树实例进行路由。本领域技术人员应当理解可以由网络管理者手动执行VLAN配置。

应当理解的是桥接器302可替换地可以不应用哈希函数，而是应用诸如求和之类的某种函数至其整个桥接器ID值，以更新路径跟踪域628。还应当理解的是不同于桥接器ID的值可以被选择为路径记录的基础。而且可以采用除了哈希函数之外的其他方法。这些其他的方法优选地采用与每一个桥接器相关的值，该值可以为在此描述的其桥接器ID或者某个其他值，并且使用选中的值作为产生随机数的密钥。在优选的实施例中，选中的桥接器值和所应用的(一个或多个)函数被选中以使冲突的机会最小化(如果没有消除冲突的机会的话)，即，即使遍历两个不同的路径，也生成相同的路径跟踪记录值。

在优选实施例中，路径跟踪域配置来具有用于网络300的每一个桥接器的位。这种配置显示在图6的可替换的路径跟踪域628a中，其中该域628a包括6个位；针对每一个桥接器302有一个位。在该实施例中，在发送MSTI配置消息620之前，根桥接器即桥接器302a断言(assert)(例如设置为“1”)与根桥接器相关的域628a的位，并且移除(de-assert)(例如设置为零或者空)域628a的所有其他位。当每一个下游桥接器(如桥接器302d)接收携带有路径跟踪域628a的STP控制消息600时，其断言(例如设置为“1”)分配给其的域628a的位。因此，对于最初由桥接器302a发起并且穿过桥接器302d和302e传播的路径跟踪域，对应这三个桥接器的路径跟踪域628的位将会被断言，而其他的位位置将全部被移除。同样，当用于两个或者更多个端口的根路径成本相同的时候，桥接器302选择在其上接收到较低(或者可替换地为较高)的路径跟踪值的端口为其根端口。

每一个桥接器302的STP引擎406可以通过网络管理者动作来配置以具有用指示路径跟踪域628a的哪一个位被分配给该桥接器302的信息。可替换地，该信息可以通过执行信息分发协议而提供给桥接器302。

路径跟踪域628a的这种配置避免了两个不同组的桥接器ID的哈希运算后的和为相同值的情况，从而确保了确定性的行为。

本发明还可以与用于建立对称生成树的其他技术一起使用。例如，由与本申请人属于同一所有者的2005年7月14日递交的美国专利申请序列号11/182,564，名称为“用于改进多生成树协议的方法和设备”(Methods and Devices for Improving the Multiple Spanning TreeProtocol)，并且通过引用整体并入本文的专利申请公开了一种用于使用反映向量(Reflection Vector)建立对称生成树的技术。

反映向量包括在网络中定义的用于每个生成树实例的不同的位。并且，每一个MSTI配置消息配置来携带对应的反映向量。当根桥接器产生用于以其为根的生成树实例的MSTI配置消息时，其最初断言反映向量的所有位，例如其将所有位都设置为“1”。根桥接器然后校验来看将发送反映向量的给定的端口是否不是用于任何一个生成树实例的根端口。如果给定的端口不是用于生成树实例的根端口，则桥接器移除对应于该生成树实例的反映向量的位位置。下游桥接器相似地移除对应于发送反映向量的端口不是根端口的生成树实例的反映向量的位位置。对于发送反映向量的端口是根端口的生成树实例，反映向量的对应的位仍是“原样”，即如下游桥接器接收到的那样。

在优选实施例中，本发明的路径跟踪特征与并入的专利申请的反映向量组合在一起。即，MST配置消息被修改来传达路径跟踪域和反映向量这两者。在进一步的实施例中，反映向量被修改来仅包括与反映向量相关联的生成树实例下级的那些生成树实例的位。具体地，可以向每一个生成树实例赋予唯一的数。当给定的桥接器建立用于以该桥接器为根的生成树实例的反映向量时，其仅需要包括用于所述唯一数小于以该桥接器为根的生成树实例的那些生成树实例的位。

通过将反映向量并入本发明的路径跟踪特征，反映向量能够在穿过网络的单一传递中会聚(converge)。

上述的描述针对本发明的特定实施例。但是，很明显可以对描述的实施例进行其他的变化和修改，而保留实施例的所有优点或者部分优点。例如，不是形成用于网络中的每一个桥接器的分离的生成树实例，而是桥接器可以组织成群组和建立用于每一对群组的对称的生成树。因此，附加的权利要求书的目的在于覆盖如在本发明的实际精神和范围中的所有的这种变化和修改。

Claims

1.一种在中间网络设备中形成多个对称生成树实例的方法，所述中间网络设备具有用于在计算机网络中接收和转发消息的多个端口，该方法包括：

接收生成树(STP)控制消息，其中所述接收到的STP控制消息包括对应于给定的生成树实例的路径跟踪记录域，所述路径跟踪记录域具有指示哪些其他中间网络设备已经传播了所述STP控制消息的信息；和

使用所述路径跟踪记录域来计算用于所述给定的生成树实例的活动拓扑。

2.如权利要求1所述的方法，其中所述STP控制消息包括多个多生成树(MST)配置消息，每一个MST配置消息对应于不同的生成树实例并且具有各自的路径跟踪记录域。

3.如权利要求1所述的方法，还包括：

通过并入指示所述中间网络设备接收到STP控制消息的信息，更新所述接收到的STP控制消息的所述路径跟踪记录域；和

从所述中间网络设备的至少一个端口发送具有所述更新的路径跟踪记录域的所述STP控制消息。

4.如权利要求3所述的方法，其中所述中间网络设备具有标识符，并且所述更新包括：

从所述设备的所述标识符计算输出；

将函数应用于所述输出和所述路径跟踪记录域的当前值以生成新的值；和

将所述新的值输入到所述路径跟踪记录域中。

5.如权利要求4所述的方法，其中

所述标识符是桥接器标识符(ID)，和

所述输出是通过对所述桥接器ID进行哈希运算生成的。

6.如权利要求5所述的方法，其中所述函数是求和函数。

7.如权利要求1所述的方法，还包括：

在相应的端口上接收两个或更多个STP控制消息，每一个接收到的STP控制消息具有各自的路径跟踪记录域和用于给定的生成树实例的根路径成本，其中所述两个或更多个接收到的STP控制消息的所述根路径成本是相同的；和选择接收到最好路径跟踪记录域的端口作为用于所述给定生成树实例的根端口。

8.如权利要求7所述的方法，其中较低路径跟踪记录域好于较高路径跟踪记录域。

9.如权利要求7所述的方法，其中较高路径跟踪记录域好于较低路径跟踪记录域。

10.如权利要求1所述的方法，其中

所述网络包括多个中间网络设备，和

所述多个中间网络设备协作来建立多个生成树实例，以使得每一个中间网络设备是各自的生成树实例的根。

11.如权利要求10所述的方法，其中所述路径跟踪记录域包括分配给所述多个中间网络设备中的每一个设备的位，所述方法还包括：

通过断言分配给接收到所述STP控制消息的中间网络设备的位，更新所述接收到的STP控制消息的所述路径跟踪记录域；和

12.一种中间网络设备，配置来在计算机网络中接收并转发消息，所述设备具有用于将所述设备连接到一个或多个网络实体和其他设备的多个端口，所述中间网络设备包括：

生成树协议(STP)引擎，配置并安排来协助建立所述网络中的多个生成树实例，所述STP引擎具有控制消息发生器，其中

所述控制消息发生器被配置来建立用于所述多个生成树实例中每一个实例的多生成树实例(MSTI)配置消息，并且在每一个这种MSTI配置消息中插入对应的路径跟踪记录域，和

在建立对应的生成树实例时，所述STP引擎使用接收到的STP控制消息的所述路径跟踪记录域。

13.如权利要求12所述的中间网络设备，其中所述STP引擎响应于在相应端口上接收到对于给定的生成树实例具有各自的路径跟踪记录域并对该给定的生成树示例指定相同的根路径成本的两个或更多个STP控制消息，选择接收到最好路径跟踪记录域的端口作为用于所述给定的生成树实例的根端口。

14.如权利要求12所述的中间网络设备，还包括桥接器标识符(ID)值，其中所述STP引擎

计算所述桥接器ID值的哈希值；

将函数应用于所述计算出的哈希值和所述路径跟踪记录域的当前值，来生成新的值；和

将所述新的值输入到所述路径跟踪记录域中。

15.如权利要求14所述的中间网络设备，其中所述函数是求和函数。

16.如权利要求12所述的中间网络设备，其中

所述设备是给定的生成树实例的根；

虚拟局域网(VLAN)标识符(VID)被分配给以所述设备为根的所述生成树实例；和

所述设备在将所述消息转发到所述网络中之前，用所述VID给所述设备接收到的来自直接连接到所述设备的网络实体的消息加标签。