CN103856405A

CN103856405A - 每地址生成树网络

Info

Publication number: CN103856405A
Application number: CN201310628133.9A
Authority: CN
Inventors: J·B·卡特; W·M·费尔特; B·E·斯蒂芬斯
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 2012-11-30
Filing date: 2013-11-29
Publication date: 2014-06-11
Also published as: US20140153443A1

Abstract

本发明涉及每地址生成树网络。提供了一种用于实现每地址生成树（PAST）的机制，以指导数据包在交换机集合中的转发。为地址集合中每个识别出的地址计算每地址生成树，由此形成每地址生成树集合。生成与每地址生成树集合中每个每地址生成树关联的转发规则集合，并且将其安装在交换机集合中为其生成每地址生成树的所有适当的交换机中，使得所述交换机集合中的每个交换机都将基于所述交换机中所安装的转发规则集合转发数据包。

Description

每地址生成树网络

技术领域

本申请总体上涉及改进的数据处理装置与方法，而且更具体地说，涉及用于为数据中心以太网网络实现每地址生成树算法的机制。

背景技术

现代数据中心的网络需求与传统网络显著不同，因此传统的网络设计常常难以满足现代数据中心的网络需求。例如，层-2以太网网络提供了网络运营商想要的配置的灵活性与简便性，但是层-2以太网网络可扩展性差而且使用可用带宽很差。层-3互联网协议（IP）网络提供了更好的可扩展性和带宽，但是不太灵活而且更难配置和管理。网络运营商想同时得到这两种设计的好处，同时，为了降低成本，宁愿要商用硬件而不要昂贵的定制解决方案。

发明内容

在一种说明性实施例中，提供了一种用于在数据处理系统中在交换机集合中实现每地址生成树（per-address spanning tree,PAST）的方法。该说明性实施例为地址集合中每个识别出的地址计算每地址生成树，由此形成每地址生成树集合。该说明性实施例生成与每地址生成树集合中的每个每地址生成树关联的转发规则集合。然后，该说明性实施例在交换机集合中为其生成了每地址生成树的所有适当的交换机中安装与每地址生成树集合中的每个每地址生成树关联的转发规则集合，使得该交换机集合中的每个交换机都将基于所述交换机中所安装的转发规则集合转发数据包。

在其它说明性实施例中，提供了包括具有计算机可读程序的计算机可用或可读介质的计算机程序产品。当在计算设备上执行时，计算机可读程序使计算设备执行以上关于方法说明性实施例概述的各个操作及其组合。

在还有另一种说明性实施例中，提供了一种系统/装置。所述系统/装置可以包括一个或多个处理器及耦合到所述一个或多个处理器的存储器。存储器可以包括指令，当所述指令被所述一个或多个处理器执行时，使所述一个或多个处理器执行以上关于方法说明性实施例概述的各个操作及其组合。

本发明的这些及其它特征与优点将在以下本发明示例实施例的具体描述中描述，或者将从这些描述变得对本领域普通技术人员显而易见。

附图说明

当结合附图一起阅读时，参考以下说明性实施例的具体描述，本发明及其优选使用模式和进一步的目标与优点，将得到最好的理解，其中：

图1是其中可以实现说明性实施例的各方面的分布式数据处理系统的示例图；

图2是其中可以实现说明性实施例的各方面的计算设备的示例框图；

图3绘出了根据一种说明性实施例的示例性交换机的框图；

图4给出了根据一种说明性实施例的典型以太网交换机数据包处理流水线的相关部分的高级概述；

图5说明了根据一种说明性实施例的用于几种商用以太网交换机芯片的表的大致尺寸；

图6绘出了根据一种说明性实施例的每地址生成树（PAST）机制的功能性框图；

图7绘出了根据一种说明性实施例的在网络初始化过程中由每地址生成树（PAST）机制执行的操作的流程图；

图8绘出了根据一种说明性实施例的响应于地址添加或迁移而由每地址生成树（PAST）机制执行的操作的流程图；以及

图9绘出了根据一种说明性实施例的响应于链路添加或删除而由每地址生成树（PAST）机制执行的操作的流程图。

具体实施例

本文所述的说明性实施例涉及在网络交换机和/或路由器上实现有效的数据包转发。为了跨网络转发数据包，每个交换机和/或路由器必须用规定如何处理交换机和/或路由器可能接收到的任何数据包的匹配动作规则集合来编程。在接收到数据包时交换机或路由器执行的最常见动作是把该数据包从一个特定的输出端口或一组输出端口转发出去。层-2以太网网络中用于编程转发表的最常见的机制是运行分布式生成树协议（STP）机制，以便建立涵盖网络中所有交换机的单个逻辑生成树。所有数据包都是沿这单个生成树转发的。STP机制保证所有转发路径都没有循环，但是对其中在网络中的源与目的地之间存在多条路径的网络拓扑结构的可用带宽使用很差，例如HyperX、Jellyfish等。

因而，说明性实施例的机制提供了启用每地址生成树（PAST）的转发机制，该机制实现了扁平层-2数据中心网络体系结构，该体系结构支持非常大量的主机（一般超过100000个）、提供完整的主机移动、提供高端-端带宽并且在商用以太网交换机之上提供自治的路由构造。当一个主机加入网络或者该主机在网络中迁移时，安装新的生成树，以便携带前往那个主机的流量。这种生成树可以只利用商用交换机芯片中存在的大型以太网（精切匹配）转发表中的条目来实现，这允许PAST机制扩展到非常大量的主机。总的来说，树跨网络中的所有链路散布流量，因此PAST提供了与层-3等价多路径（ECMP）路由相同或更大的聚集带宽。PAST机制提供以太网语义并且在未修改的交换机与主机上运行，而不需要修改虚拟LAN（VLAN）或者其它首部字段。最后，PAST机制对任意网络拓扑结构起作用，包括HyperX、Jellyfish等，这些拓扑结构可以以其成本的一小部分和胖树拓扑结构一样或者更好地执行。

PAST机制可以按集中或分布方式实现。即，尽管优选实施例针对集中式的软件定义网络（SDN）体系结构，但是本领域技术人员将认识到，分布式网络也可以实现，其中所述PAST体系结构可以利用网络中的一个或多个交换机而不是集中式的PAST控制器来实现。所述优选实施例针对集中式的软件定义网络（SDN）体系结构，这种体系结构在高端服务器处理器上计算树，而不是利用商用以太网交换机中存在的控制平面处理器来协商每个树。描述了基于OpenFlow的PAST实现，以便考虑商用交换机硬件中所存在的匹配动作规则的种类、每个表的规则数量及规则可以安装的速度。通过把PAST机制约束到仅仅利用目的地介质访问控制（MAC）地址和VLAN标记来路由，说明性实施例可以利用典型L2以太网交换机中所存在的大型层-2转发表，而不是依赖更一般化但是小得多的三元内容寻址存储器（TCAM）表，就像在先前的OpenFlow体系结构中那样。

因此，说明性实施例提供了：

1.利用每地址生成树路由（PAST）机制满足上述所有需求的新颖网络体系结构。

2.使商用交换机硬件的能力得以有效使用的实现。

因而，说明性实施例可以在许多不同类型的数据处理环境中利用。为了提供用于描述说明性实施例的具体元素和功能性的背景，在下文中提供了图1和2，作为其中可以实现说明性实施例的各方面的示例环境。应当认识到，图1和2仅仅是例子而不是要断言或暗示关于其中可以实现本发明各方面或实施例的环境的任何限制。在不背离本发明主旨与范围的情况下，可以对所绘出的环境进行许多修改。

图1绘出了其中可以实现说明性实施例的各方面的示例分布式数据处理系统的图示。分布式数据处理系统100可以包括其中可以实现说明性实施例的各方面的计算机网络。分布式数据处理系统100包含至少一个网络102，该网络是用于在分布式数据处理系统100中连接到一起的各种设备与计算机之间提供通信链路的介质。网络102可以包括例如交换机、路由器等的连接设备以及例如有线通信链路、无线通信链路、光纤电缆等的连接。

在所绘出的例子中，服务器104和服务器106连同存储单元108和客户端110、112和114一起经连接设备（例如交换机116、118、120和122）耦合到网络102，其中交换机本身彼此耦合。这些客户端110、112和114可以是例如个人计算机、网络计算机等。在所绘出的例子中，服务器104向客户端110、112和114提供数据，例如启动文件、操作系统图像和应用。服务器104可以是物理机器或者是运行一个或多个虚拟机的机器。在所绘出的例子中，客户端110、112和114是服务器104的客户端。分布式数据处理系统100可以包括未示出的附加的服务器、客户端和其它设备。

在所绘出的例子中，分布式数据处理系统100是代表利用以太网协议彼此通信的交换机与服务器集合的数据中心网络（DCN）。当然，分布式数据处理系统100还可以实现为包括多种不同类型的网络，例如像内联网、局域网（LAN）、广域网（WAN）等。如上所述，图1是要作为例子，而不是作为对本发明不同实施例的体系结构限制，而且因此，图1中所示出的特定元素不应当认为是关于其中可以实现本发明说明性实施例的环境的限制。

图2是其中可以实现说明性实施例的各方面的示例数据处理系统的框图。数据处理系统200是计算机的一个例子，例如图1中的客户端110，其中实现用于本发明说明性实施例的过程的计算机可用代码或指令可以位于其中。

在所绘出的例子中，数据处理系统200采用集线器体系结构，包括北桥与存储器控制器集线器（NB/MCH）202和南桥与输入/输出（I/O）控制器集线器（SB/ICH）204。处理单元206、主存储器208和图形处理器210连接到NB/MCH202。图形处理器210可以通过加速图形端口（AGP）连接到NB/MCH202。

在所绘出的例子中，局域网（LAN）适配器212连接到SB/ICH204。音频适配器216、键盘与鼠标适配器220、调制解调器222、只读存储器（ROM）224、硬盘驱动器（HDD）226、CD-ROM驱动器230、通用串行总线（USB）端口和其它通信端口232、以及PCI/PCIe设备234通过总线238和总线240连接到SB/ICH204。PCI/PCIe设备可以包括例如以太网适配器、附件卡和用于笔记本电脑的PC卡。PCI使用卡总线控制器，而PCIe不使用。ROM224可以是例如闪存基本输入/输出系统（BIOS）。

HDD226和CD-ROM驱动器230通过总线240连接到SB/ICH204。HDD226和CD-ROM驱动器230可以使用例如集成式驱动器电子设备（IDE）或串行高级技术附件（SATA）接口。超级I/O（SIO）设备236可以连接到SB/ICH204。

操作系统在处理单元206上运行。操作系统协调并提供对图2数据处理系统200中各种组件的控制。作为客户端，操作系统可以是市场上可买到的操作系统，例如

面向对象的编程系统，例如Java^TM编程系统，可以结合操作系统运行并且从数据处理系统200上执行的Java^TM程序或应用提供对操作系统的调用。

作为服务器，数据处理系统200可以是例如运行高级交互执行

操作系统或者

操作系统的

eServer^TM

数据处理系统200可以是在处理单元206中包括多个处理器的对称多处理器（SMP）系统。作为替代，也可以采用单处理器系统。

用于操作系统、面向对象的编程系统和应用或程序的指令位于存储设备上，例如HDD226，而且可以被加载到主存储器208中，用于由处理单元206执行。用于本发明说明性实施例的过程可以由处理单元206利用计算机可用程序代码执行，其中，例如计算机可用程序代码可以位于例如像主存储器208、ROM224的存储器中，或者位于一个或多个外围设备226和230中。

总线系统，例如图2中所示的总线238或总线240，可以由一条或多条总线组成。当然，总线系统可以利用在附连到架构或体系结构的不同组件或设备之间提供数据传输的任何类型的通信架构或体系结构实现。通信单元，例如图2的调制解调器222或网络适配器212，可以包括用于发送和接收数据的一个或多个设备。存储器可以是例如主存储器208、ROM224或者像在图2中的NB/MCH202中找到的高速缓存。

本领域普通技术人员将认识到，图1和2中的硬件可以依赖实现而改变。其它的内部硬件或外围设备，例如闪存存储器、等价的非易失性存储器或者光盘驱动器等，可以除图1和2中所绘出的硬件之外附加地或者代替其使用。而且，在不背离本发明主旨与范围的情况下，除了前面提到的SMP系统，说明性实施例的过程还可以应用到多处理器数据处理系统。

而且，数据处理系统200可以采取多种不同数据处理系统中任意一种的形式，包括客户端计算设备、服务器计算设备、平板电脑、膝上型电脑、交换机、控制器、电话或其它通信设备、个人数字助理（PDA）等。在有些说明性例子中，数据处理系统200可以是配置成具有闪存存储器的便携式计算设备，其中，例如闪存存储器提供用于存储操作系统文件和/或用户生成的数据的非易失性存储器。从根本上讲，没有体系结构限制，数据处理系统200可以是任何已知或以后开发的数据处理系统。

尽管许多厂家都生产以太网转发硬件，但是部分地是由于在每种交换机的核心都使用来自例如Broadcom^TM和的厂家的“商用”交换机芯片，因此硬件趋于呈现许多相似性。以下描述集中在示例性交换机芯片与以太网交换机。

图3绘出了根据一种说明性实施例的示例性交换机的框图。交换机300包括经总线310耦合到一起的切换逻辑302、服务处理器304、存储器306和物理接口宏（PHY）308。当经一个PHY308接收到数据包时，切换逻辑302解析数据包的首部以识别该数据包的目的地地址，利用一个或多个转发表312来识别该数据包应当发送到哪个PHY308，如果必要的话就修改数据包的首部，以及在识别出的PHY308上把数据包发送出去。服务处理器304可以与其它交换机中的服务处理器交换消息，以便确定网络拓扑结构，例如，利用链路层发现协议（LLDP）消息。服务处理器304可以使用这种拓扑结构信息来确定数据包应当经其转发的转发拓扑结构以及对转发表312编程以反映这种转发拓扑结构。作为替代，服务处理器304可以把网络拓扑结构信息转发到网络控制器，或者根据说明性实施例，转发到每地址生成树（PAST）控制器，该控制器可以利用这种拓扑结构信息生成优选的转发拓扑结构。在这种实施例中，在下文图6中描述的每地址生成树（PAST）控制器将与每个交换机中的服务处理器304通信，以规定数据包应当如何转发，而且每个服务处理器304将更新其本地转发表312，以便反映这种规定。

图4给出了根据一种说明性实施例的典型以太网交换机数据包处理流水线的相关部分的高级概述。每个方框402、404、406和408代表把具有特定首部字段的数据包映射到一个或多个动作的表。每个表的区别在于哪些首部字段可以匹配、该表保留了多少条目以及该表允许什么类型的动作。典型的动作包括把数据包发送出具体的端口或者把数据包转发到另一个表。表可以被遍历的次序是受约束的；允许的交互用有向箭头示出。

图5说明了根据一种说明性实施例的用于典型以太网交换机芯片的表的大致尺寸。虽然绘出的许多商用以太网交换机芯片包括其它的表，例如互联网协议（IP）路由表、等价多路径（ECMP）路由表、数据中心桥接（DCB）、多协议标签切换（MPLS）表、多播表等，这些在本文不进行讨论，但是表500绘出了用于三元内容寻址存储器（TCAM）表502（图4的方框402和408）和层-2（L2）/以太网表504（图4的方框404）的估计尺寸。

L2/以太网表504对两个字段执行确切匹配查找：虚拟LAN（VLAN）标识符（ID）和目的地介质访问控制（MAC）地址。L2/以太网表504是迄今为止典型商用交换机芯片中最大的表。L2/以太网表504的输出或者是一个输出端口，或者是一个组，这个组可以被看作是用于支持多路径或多播的虚拟端口。

重写与转发TCAM表502对大部分数据包首部字段提供通配符匹配，包括每位通配符。TCAM表502的重写部分支持修改数据包首部的输出动作，而TCAM表502的转发部分用于更灵活地选择输出端口或组。TCAM表502的更大灵活性是有代价的；除了消耗显著的芯片面积，它们一般只包含几千个条目。

RackSwitch G8264柜顶交换机的OpenFlow1.0实现允许OpenFlow规则安装在L2/以太网表504中。具体而言，如果接收到精确匹配到（仅）目的地MAC地址与VLAN ID的规则，则交换机把该规则安装在L2/以太网表504中。否则，交换机就把该规则安装在适当的TCAM表502中，就像典型的OpenFlow实现那样。

交换机芯片不是通用处理器，因此交换机一般包含负责编程交换机芯片、提供交换机管理接口并参与控制平面协议的控制平面处理器，其中控制平面协议例如生成树协议（STP）或开放最短路径优先（OSPF）。在软件定义的网络中，控制处理器还把控制器命令翻译成交换机芯片状态。

在传统的以太网中，许多转发状态都是由交换机芯片基于观察到的数据包自动学习的。软件定义的方法把一些这种负担转移到控制处理器和外部控制器，这增加了等待时间和潜在的瓶颈。

一般来说，有两种扩展路由的方法。第一种方法需要使地址在拓扑结构上显著，因此路由可以在路由表中聚集。第二种方法是要在路由表中包括足够的空间，以便允许所有可路由的地址都具有至少一个条目。

如上所述，两个层-2转发表（精确匹配与TCAM）大小的区别大约是两个数量级。给定TCAM表502的小尺寸，需要TCAM匹配灵活性的任何路由机制都必须聚集路线，否则每个交换机几千个TCAM条目很快就会耗尽。但是，L2/以太网表504的较大尺寸意味着只匹配到目的地MAC与VLAN ID的任何转发机制具有足够的表空间来安装每个交换机每个可路由地址至少一个条目，即使对大的网络也是如此。应当指出，聚集可能不能在以太网转发表中使用，因为它只允许精确匹配。

说明性实施例的每地址生成树（PAST）机制提供了自配置与主机移动的传统以太网好处，同时在任意拓扑结构中使用所有可用的带宽、扩展到非常大量的主机并且在目前的商用硬件上运行。PAST通过在L2/以太网路由表中安装路由来这么做。

PAST的设计遵循商用交换机的以太网转发表的结构。把转发规则表示为从<目的地MAC地址，VLAN ID>对映射到一个输出端口或一个小端口集合的任何路由算法都可以利用大型以太网转发表来实现。通过设计，任意的生成树都可以利用这种形式的规则来表示。目前商用交换机的以太网表被设计成支持传统的生成树协议（STP），该协议实现了用于转发前往所有目的地主机的流量的单个生成树。但是，这些相同的以太网表也可以实现每个目的地主机单独的生成树，这导致每地址生成树（PAST）。有可能为任何连接的拓扑结构构造生成树，因此PAST是独立于拓扑结构的。

说明性实施例所考虑的网络拓扑结构具有高路径分集（pathdiversity），因此许多可能的生成树可以为每个地址建立。每个个别的树只使用网络中链路的一小部分，因此使不同的树尽可能脱节是有利的，以便提高聚集网络利用率。因而，与传统的L2/以太网网络不同，PAST会得益于具有高多路径程度的网络拓扑结构，例如HyperX、Jellyfish等。

PAST机制的一种变体建立以目的地为根的最短路径生成树。PAST机制背后建立这种树的直觉是最短路径生成树减小了等待时间并且最小化了网络上的负载。这种PAST机制采用广度优先搜索（BFS）逻辑为网络中的每个地址构造最短路径生成树。这种以目的地为根的生成树提供了从网络中任何点到那个目的地的最小跳计数路径。

一种备用的PAST机制通过选择网络中的一个随机交换机充当中介、建立把所有交换机连接到这个中介交换机的最小生成树、然后沿着从目的地到该中介的路径反转树边缘的方向来建立以目的地为根的非最小化生成树。这种机制实现了Valiant路由的形式。以增加网络中平均路径长度为代价，结果产生的非最小化生成树提高了PAST树集合中的路径分集。

任何给定的交换机只使用单个路径用于把流量转发到每个主机。这些路径被保证是没有循环的，因为它们形成了树。没有链路以任何方式被禁用。因为不同的生成树用于每个目的地，所以PAST网络中两个主机之间的转发与反转路径不必是对称的。

PAST机制不关心一个地址（MAC地址-VLAN对）是代表VM、主机还是交换机，它是作为一种选择向网络运营商提供的。由于PAST机制在商用硬件上支持非常大量的地址，因此，当存在比适合大型L2/以太网精确匹配表中的规则少的主机时，不需要共享、重写或者虚拟化网络中的地址。同样，如果主机希望以增加的转发状态为代价增加路径分集，则主机可以使用任何数量的地址。

在建立每个生成树时，对于下一跳链路常常有多个选项。本文描述的说明性实施例采用随机下一跳选择策略，但是本领域技术人员将认识到，可以使用许多不同的选择策略，例如随机的、有引导的、加权的，等等。PAST机制选择下一跳链路的方式可能影响路径分集、负载平衡和性能。

图6绘出了根据一种说明性实施例的每地址生成树（PAST）机制的功能性框图。数据处理系统600包括PAST控制器602、交换机集合604a、604b、604c、604d、…、604n和主机606a₁、606a₂、606a₃、606b₁、606b₂、606b₃、606c₁、606c₂、606c₃、606d₁、606d₂、…、606n₁。如所说明的，主机606a₁、606a₂、606a₃耦合到交换机604a，主机606b₁、606b₂、606b₃耦合到交换机604b，主机606c₁、606c₂、606c₃耦合到交换机604c，主机606d₁和606d₂耦合到交换机604d，而主机606n₁耦合到交换机604n。如进一步示出的，利用与数据网络610隔离的单独（带外）控制网络608，PAST控制器602耦合到交换机集合604a、604b、604c、604d、…、604n中的每一个，其中数据网络610把交换机集合604a、604b、604c、604d、…、604n耦合到一起。控制网络608与数据网络610的隔离允许PAST控制器602引导控制网络608并且从故障中快速恢复，这种恢复可以把数据网络610分区。但是，在控制网络610的所有或者一部分变得不稳定或者不可用的情况下，或者甚至是作为一种备选方案，本领域普通技术人员将认识到，PAST控制器602可以利用数据网络610发送和接收PAST控制消息。

PAST控制器602包括拓扑结构发现逻辑612、地址检测逻辑614、路由计算逻辑616、路由安装逻辑618以及地址解析逻辑620。拓扑结构发现逻辑612在网络中交换机集合604a、604b、604c、604d、…、604n中的每一个端口上发送和接收链路层发现协议（LLDP）消息等。这些LLDP消息发现一条链路是否连接到另一个交换机或主机，以及该端口是否耦合到另一个交换机，交换机的标识符ID。地址检测逻辑614配置交换机集合604a、604b、604c、604d、…、604n中的每一个监听所有地址解析协议（ARP）流量并且把所有ARP流量都转发到PAST控制器602。由主机606a₁、606a₂、606a₃、606b₁、606b₂、606b₃、606c₁、606c₂、606c₃、606d₁、606d₂、…、606n₁关于主机引导和迁移所生成的免费ARP提供新的或改变的位置的及时通知并且触发为每个识别出的地址的每地址生成树的（重新）计算。

一发现新的或迁移的地址，路由计算逻辑616就为每个识别出的目的地主机（MAC地址）（重新）计算每地址生成树并且生成与该每地址生成树关联的转发规则集合（每个主机一个），其中每地址生成树由交换机用于确定应当如何在每个主机实现数据包转发。另外，当交换机出现或消失时，路由计算逻辑616为交换机集合604a、604b、604c、604d、…、604n中的每一个重新计算所有每地址生成树并且生成与每个每地址生成树关联的转发规则集合。当一条链路在交换机之间或者在交换机与主机之间出现故障时，路由计算逻辑616只重新计算遍历那条链路的每地址生成树并且生成与每个每地址生成树关联的转发规则集合。尽管交换机之间或者从交换机到一个主机出现的新链路不影响现有的每地址生成树，但是路由计算逻辑616还是有规律地重新建立随机的每地址生成树并且生成与每个随机的每地址生成树关联的转发规则集合，以便逐步开拓新链路并且重新优化现有的每地址生成树。

无论什么时候在（重新）计算每地址生成树和生成与每个每地址生成树关联的转发规则集合时，路由安装逻辑618都并行地在所有关联的交换机中安装关联的转发规则集合。路由安装逻辑618直接在交换机的以太网表中安装关联的转发规则集合，使得TCAM条目可以用于其它目的，例如访问控制列表（ACL）和流量工程。为了确保关联的转发规则集合放在以太网表中，路由安装逻辑618确保关联的转发规则集合中的每个规则都规定关于目的地MAC地址与VLAN的精确匹配。为了防止产生暂时性路由循环，在安装与（重新）计算的每地址生成树关联的新转发规则集合之前，路由安装逻辑618可以除去先前安装的、与被替换的每地址生成树关联的转发规则的全部或一部分并且发布屏障（barrier），以确保它们被清除。

所属技术领域的技术人员知道，本发明的各个方面可以实现为系统、方法或计算机程序产品。因此，本发明的各个方面可以具体实现为以下形式，即：完全的硬件实施例、完全的软件实施例（包括固件、驻留软件、微代码等），或硬件和软件方面结合的实施例，这里可以统称为“电路”、“模块”或“系统”。此外，本发明的各个方面还可以实现为在任意一个或多个计算机可读介质中的计算机程序产品的形式，该计算机可读介质中包含计算机可用的程序代码。

可以采用一个或多个计算机可读介质的任意组合。计算机可读介质可以是计算机可读信号介质或者计算机可读存储介质。计算机可读存储介质例如可以是——但不限于——电、磁、光、电磁、红外线、或半导体的系统、装置或设备、或者任意以上的组合。计算机可读存储介质的更具体的例子（非穷举的列表）包括：具有一个或多个导线的电连接、便携式计算机盘、硬盘、随机存取存储器（RAM）、只读存储器(ROM)、可擦式可编程只读存储器(EPROM或闪存)、光纤、便携式紧凑盘只读存储器(CD-ROM)、光存储设备、磁存储设备、或者上述的任意合适的组合。在本文档的上下文中，计算机可读存储介质可以是任何包含或存储程序的有形介质，该程序可以被指令执行系统、装置或者设备使用或者与其结合使用。

计算机可读的信号介质可以包括在基带中或者作为载波一部分传播的数据信号，其中承载了计算机可读的程序代码。这种传播的信号可以采用多种形式，包括——但不限于——电磁信号、光信号或上述的任意合适的组合。计算机可读的信号介质还可以是计算机可读存储介质以外的任何计算机可读介质，该计算机可读介质可以发送、传播或者传输用于由指令执行系统、装置或者设备使用或者与其结合使用的程序。

计算机可读介质上包含的程序代码可以用任何适当的介质传输，包括——但不限于——无线、有线、光缆、RF等等，或者上述的任意合适的组合。

可以以一种或多种程序设计语言的任意组合来编写用于执行本发明操作的计算机程序代码，所述程序设计语言包括面向对象的程序设计语言—诸如Java、Smalltalk、C++等，还包括常规的过程式程序设计语言—诸如“C”语言或类似的程序设计语言。程序代码可以完全地在用户计算机上执行、部分地在用户计算机上执行、作为一个独立的软件包执行、部分在用户计算机上部分在远程计算机上执行、或者完全在远程计算机或服务器上执行。在涉及远程计算机的情形中，远程计算机可以通过任意种类的网络——包括局域网(LAN)或广域网(WAN)—连接到用户计算机，或者，可以连接到外部计算机（例如利用因特网服务提供商来通过因特网连接）。

下面将参照根据本发明说明性实施例的方法、装置（系统）和计算机程序产品的流程图和/或框图描述本发明。应当理解，流程图和/或框图的每个方框以及流程图和/或框图中各方框的组合，都可以由计算机程序指令实现。这些计算机程序指令可以提供给通用计算机、专用计算机或其它可编程数据处理装置的处理器，从而生产出一种机器，使得这些计算机程序指令在通过计算机或其它可编程数据处理装置的处理器执行时，产生了实现流程图和/或框图中的一个或多个方框中规定的功能/动作的装置。

也可以把这些计算机程序指令存储在计算机可读介质中，这些指令使得计算机、其它可编程数据处理装置、或其他设备以特定方式工作，从而，存储在计算机可读介质中的指令就产生出包括实现流程图和/或框图中的一个或多个方框中规定的功能/动作的指令的制造品（article of manufacture）。

计算机程序指令还可以加载到计算机、其它可编程数据处理装置或者其它设备上，使得一系列操作步骤在计算机、其它可编程装置或者其它设备上执行，产生一种计算机实现的过程，使得在所述计算机或者其它可编程装置上执行的指令提供用于实现在所述流程图和/或框图块中所指定的功能/动作的过程。

图7绘出了根据一种说明性实施例的在网络初始化过程中由每地址生成树（PAST）机制执行的操作的流程图。当操作开始时，由处理器执行的PAST机制使每个交换机在网络中交换机集合的每个端口上发送、接收并转发链路层发现协议（LLDP）消息，以便发现连接到该端口的链路是另一个交换机还是主机，以及该端口是否耦合到另一个交换机，交换机的标识符ID，由此发现包括网络的交换机集合的拓扑结构（步骤702）。然后，通过配置交换机集合中的全部都监听并把与地址解析协议（ARP）关联的所有流量转发到网络控制器，PAST机制检测网络中的所有MAC地址与IP地址（步骤704）。一旦发现了MAC地址与全部在用的端口的连通性，PAST机制就为每个识别出的MAC地址计算每地址生成树（步骤706）。然后，PAST机制生成与每个每地址生成树关联的转发规则集合（每个主机MAC地址一个）（步骤708）。然后，PAST机制并行地把关联的转发规则集合安装在所有关联的交换机中（步骤710），其后操作终止。PAST机制把关联的转发规则集合直接安装在交换机的以太网表中，使得TCAM条目可以用于其它目的，例如访问控制列表（ACL）和流量工程。

图8绘出了根据一种说明性实施例的响应于地址添加或迁移而由每地址生成树（PAST）机制执行的操作的流程图。当操作开始时，由处理器执行的PAST机制确定交换机集合中的交换机是否监听到与先前由那个交换机识别出的地址不匹配的地址（步骤802）。这个地址可以是由耦合到该交换机的主机添加的新地址，或者可以是从一个主机迁移到另一个的地址。如果在步骤802没有识别出新的或迁移的地址，则操作返回到步骤802。如果在步骤802识别出新的或迁移的地址，则在新地址的情况下PAST机制为每个MAC地址计算，或者在迁移地址的情况下重新计算，每地址生成树（步骤804）。然后，PAST机制生成与每地址生成树关联的转发规则集合（步骤806）。然后，在受该新的或迁移地址影响的关联交换机中安装转发规则集合之前，PAST机制确定是否有一个或多个之前的转发规则需要从关联的交换机除去（步骤808）。如果在步骤808有一个或多个之前的转发规则需要除去，则PAST机制除去这一个或多个转发规则（步骤810）。如果在步骤808没有转发规则需要除去或者在步骤810之后，PAST机制并行地在适当的交换机中安装关联的转发规则集合（步骤812），其后操作停止。同样，PAST机制把关联的转发规则集合直接安装在交换机的以太网表中，使得TCAM条目可以用于其它目的，例如访问控制列表（ACL）和流量工程。

图9绘出了根据一种说明性实施例的响应于链路添加或删除而由每地址生成树（PAST）机制执行的操作的流程图。当操作开始时，由处理器执行的PAST机制基于发送和接收的链路层发现协议（LLDP）消息确定把一个交换机耦合到另一个交换机或主机的链路是否被识别为添加的或删除的（步骤902）。应当指出，链路也可以基于交换机出现或消失而表现为是添加的或删除的。如果在步骤902没有识别出添加或删除的链路，则操作返回到步骤902。

如果在步骤902识别出添加或删除的链路，则PAST机制确定该链路具体是添加的链路还是删除的链路（步骤904）。如果在步骤904该链路是删除的链路，则PAST机制为耦合到那条链路的每个MAC地址重新计算每地址生成树（步骤906）。然后，PAST机制生成与这个新的每地址生成树关联的转发规则集合（步骤908）。如果在步骤904该链路是添加的链路，则PAST机制选择是否利用这条新链路（步骤910）。如果在步骤910PAST机制选择不利用这条新链路，则操作返回步骤902。如果在步骤910PAST机制选择利用这条新链路，则PAST机制为利用包括该添加链路的新网络拓扑结构的一个或多个目的地主机重新计算每地址生成树（步骤912）。要为其计算新的每地址生成树的目的地主机和被选择的具体主机的个数将影响重新计算和重新安装新的每地址生成树所需的时间量，以及利用该新链路的程度。

在步骤908之后或者步骤912之后并且在受任何新的每地址生成树影响的关联交换机中安装转发规则集合之前，PAST机制确定是否有一个或多个先前的转发规则需要从关联的交换机除去（步骤914）。如果在步骤914有一个或多个先前的转发规则需要除去，则PAST机制除去这一个或多个转发规则。如果在步骤914没有转发规则需要除去或者在步骤916之后，PAST机制并行地把关联的转发规则集合安装到适当的交换机中（步骤918），其后操作返回到步骤902。同样，PAST机制把关联的转发规则集合直接安装在交换机的以太网表中，使得TCAM条目可以用于其它目的，例如访问控制列表（ACL）和流量工程。

附图中的流程图和框图显示了根据本发明的多个实施例的系统、方法和计算机程序产品的可能实现的体系架构、功能和操作。在这点上，流程图或框图中的每个方框可以代表一个模块、程序段或代码的一部分，所述模块、程序段或代码的一部分包含一个或多个用于实现规定的逻辑功能的可执行指令。也应当注意，在有些作为替换的实现中，方框中所标注的功能也可以以不同于附图中所标注的顺序发生。例如，两个连续的方框实际上可以基本并行地执行，它们有时也可以按相反的顺序执行，这依所涉及的功能而定。也要注意的是，框图和/或流程图中的每个方框、以及框图和/或流程图中的方框的组合，可以用执行规定的功能或动作的专用的基于硬件的系统来实现，或者可以用专用硬件与计算机指令的组合来实现。

因而，通过提供每地址生成树（PAST）机制，说明性实施例提供了解决现有网络体系结构缺陷的机制，其中PAST机制提供了自配置与主机移动的传统以太网好处，同时利用任意拓扑结构中的所有可用带宽，扩展到非常大量的主机（对于某些商用交换机芯片超过100000个），并且运行在目前的商用硬件上。说明性实施例是通过不加约束地在以太网表中安装路由来这么做的，这是之前设计空间中一个未开发的点，而且因此，有效地使用商用交换机硬件的能力。

如以上所指出的，应当认识到，说明性实施例可以采取完全硬件实施例、完全软件实施例或者既包含硬件又包含软件元件的实施例的形式。在一种示例实施例中，说明性实施例的机制可以在软件或程序代码中实现，这可以包括但不限于固件、驻留软件、微代码等。

适于存储和/或执行程序代码的数据处理系统将包括至少一个直接地或者通过系统总线间接地耦合到存储器元件的处理器。存储器元件可以包括在程序代码实际执行过程中采用的本地存储器、大容量储存器和提供至少一些程序代码的临时存储以减少执行过程中必须从大容量储存器检索代码的时间量的高速缓存存储器。

输入/输出或I/O设备（包括但不限于键盘、显示器、定点设备等）可以直接地或者通过中间I/O控制器耦合到系统。网络适配器也可以耦合到系统，使数据处理系统变得通过中间的私有或公共网络耦合到其它数据处理系统或远端打印机或存储设备。调制解调器、电缆调制解调器和以太网卡仅仅是目前可以获得的一些网络适配器类型。

本发明的描述是为了说明和描述的目的而给出的，而不是详尽的或者要把本发明限定到所公开的形式。对本领域的普通技术人员来说，许多修改与变体都是显而易见的。实施例的选择与描述是为了最好地解释本发明的原理、实践应用，并且使本领域的其他普通技术人员能够理解本发明具有适于预期特定用途的各种修改的各种实施例。

Claims

1.一种用于在数据处理系统中实现每地址生成树的方法，以指导数据包在网络交换机集合中的转发，所述方法包括：

为地址集合中每个识别出的地址计算每地址生成树，由此形成每地址生成树集合；

生成与所述每地址生成树集合中的每个每地址生成树关联的转发规则集合；以及

在交换机集合中为其生成每地址生成树的所有适当的交换机中安装与每地址生成树集合中的每个每地址生成树关联的转发规则集合，使得交换机集合中的每个交换机都将基于所述交换机中所安装的转发规则集合转发数据包。

2.如权利要求1所述的方法，其中地址集合中的每个地址是介质访问控制（MAC）地址或者互联网协议（IP）地址。

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

发现包括网络的交换机集合的拓扑结构；以及

检测由所述交换机集合中的每个交换机处理的地址集合，其中所述地址集合中的每个地址是由主机集合中耦合到交换机集合中一个交换机的主机所使用的地址。

4.如权利要求3所述的方法，其中拓扑结构是交换机集合中两个交换机之间的链路连通性或者交换机与主机之间的链路连通性的聚集。

5.如权利要求4所述的方法，进一步包括：

响应拓扑结构是交换机集合中交换机之间的以及交换机与主机之间的链路连通性，发现包括网络的交换机与主机的标识符ID。

6.如权利要求1所述的方法，其中与每地址生成树集合中每个每地址生成树关联的规则集合并行地安装在交换机集合中所有适当的交换机中。

7.如权利要求1所述的方法，其中规则集合安装在交换机的以太网表中。

8.如权利要求1所述的方法，其中规则集合是利用独立的带外控制网络安装的，所述带外控制网络与把交换机集合中的交换机连接到其它交换机或主机的链路隔开。

9.一种装置，包括：

处理器；以及

耦合到所述处理器的存储器，其中所述存储器包括指令，当指令被处理器执行时，使处理器：

10.如权利要求9所述的装置，其中地址集合中的每个地址都是介质访问控制（MAC）地址或者互联网协议（IP）地址。

11.如权利要求9所述的装置，其中所述指令进一步使处理器：

发现包括网络的交换机集合的拓扑结构；以及

检测由所述交换机集合中每个交换机处理的地址集合，其中所述地址集合中的每个地址是由主机集合中耦合到交换机集合中一个交换机的主机所使用的地址。

12.如权利要求11所述的装置，其中拓扑结构是交换机集合中两个交换机之间的链路连通性或者交换机与主机之间的链路连通性的聚集。

13.如权利要求12所述的装置，其中所述指令进一步使处理器：

14.如权利要求9所述的装置，其中与每地址生成树集合中的每个每地址生成树关联的规则集合并行地安装在交换机集合中所有适当的交换机中。

15.如权利要求9所述的装置，其中规则集合安装在交换机的以太网表中。

16.如权利要求9所述的装置，其中规则集合是利用独立的带外控制网络安装的，所述带外控制网络与把交换机集合中的交换机连接到其它交换机或主机的链路隔开。