编址方法、编址装置、架构管理器、交换机和数据路由方法

摘要

本发明提出了一种用于数据中心网络的编址方法、编址装置、架构管理器、交换机和数据路由方法。根据本发明的编址装置，包括：树创建单元，用于依次以每个交换机为根，通过网络拓扑发现功能，创建包含所有主机的树，由此，得到多棵树；树选择单元，用于从所述树创建单元所创建的多棵树中选择具有最小高度的树；以及地址分配单元，用于针对由所述树选择单元所选择的每一棵具有最小高度的树，为网络中每个交换机和每个主机分配地址。本发明适用于数据中心所采用的多种网络拓扑，可实现位置地址的聚合，以减小转发表，而且能够容易地实现网络负载均衡。

说明书

技术领域

本发明涉及数据中心网络，更具体地，涉及一种用于数据中心网络 的编址方法、编址装置、架构管理器、交换机和数据路由方法，适用于 数据中心所采用的多种网络拓扑，可实现位置地址的聚合，以减小转发 表，而且能够容易地实现网络负载均衡。

背景技术

随着互联网和云计算服务等应用的发展，数据中心的规模日益增大， 当前的数据中心包含着成千上万台的服务器和交换机。另外，数据中心 通常同时支持多种不同的应用，其中一些应用要求数据中心内部不同服 务器之间的大量的数据通信。数据中心的规模的增大和应用的发展对其 网络架构带来了新的挑战。

数据中心网络的目标是将大量的数据中心服务器进行互连，并为上 层的应用提供高效和容错的路由转发服务。数据中心网络架构主要有两 类选择：二层网络(Layer 2 Network)和三层网络(Layer 3 Network)。

在二层网络架构中，整个数据中心成为一个大的以太网。以太 网给网络管理带来了很大的方便，“即插即用”，无缝的虚拟机 迁移等。但是，以太网不能扩展到成千上万台服务器的规模。

三层网络架构具有很好的可扩展性，但是它不再具有以太网简 单方便的优点，给网络管理带来了负担。

针对这个问题，研究人员提出了新的系统和方法来解决以太网的扩 展性问题，支持“即插即用”的大规模的数据中心网络。

以太网是当今最常用的局域网技术，它使用MAC地址来标识网络中 的节点。不同于IP地址的层次化结构，MAC地址是一种平面(flat)结 构，并且是全球唯一的。交换机中的转发表记录了目的MAC地址到发送 端口的映射。

图1是用于说明交换机通过自学习的方式构建转发表的示意图。当 一个数据帧到达交换机的时候，交换机查看该数据帧的源MAC地址，并 且将此源MAC地址和此数据帧进入的端口的映射存储到转发表。由于这 种自学习机制以及MAC地址的使用，使得网络管理非常方便，交换机可 以“即插即用”。

但是以太网不能扩展到成千上万台服务器的规模，主要有以下几点 原因。首先，MAC地址是非层次化的，不能将多个MAC地址聚合在一起。 交换机的转发表存储的是目的MAC地址和发送端口的映射，因此每个交 换机的转发表里面就需要存储整个网络的所有主机的MAC地址。交换机 的缓存大小的限制使得网络中主机的个数不能无限制的增长。其次，如 图2所示，对于具有未知目的MAC地址的数据帧(转发表中没有存储此 目的MAC地址)，交换机将其发送(广播)至除了数据帧到达的端口以外 的所有其他端口。另外，一些基本网络服务(包括地址解析协议ARP、 动态主机配置协议DHCP等)都是通过广播的方式进行的。这种全网性的 广播机制也使得以太网不能扩展到太大规模。最后，以太网使用生成树 协议(Spanning Tree Protocol-STP)来避免环路，但是沿着单一的生 成树来转发数据包会导致低效的路由选择和链路负载的不均衡。

这些原因使得数据中心网络不能被直接构建成一个大的局域网。一 个解决方法是使用二层三层混合的结构，数据中心被构建成多个局域网， 这些局域网之间是由IP路由连接。每个局域网由几十或者几百台机器组 成，形成一个IP子网。这种二层三层混合的结构解决了可扩展性问题， 但是不再具有以太网简单方便的优点，给网络管理带来了负担。本发明 的目的在于解决以太网的扩展性问题，以支持“即插即用”的大规模数 据中心网络。

参考文献[1]提出了PortLand协议——一种用于数据中心网络的二 层寻址、路由和转发协议。根据该协议，给网络中的主机分配一个假的 MAC(PMAC)地址，用来编码这些主机在网络拓扑中的位置。PMAC地址 可以用非常小的交换机的状态来实现有效的路由转发功能。以下，对 PortLand系统进行更为详细的描述。

图3是示出了PortLand系统的系统结构的示意图。

在PortLand系统中，终端主机被分配假的MAC地址(PMAC)(例如， 如图3所示，PMAC地址“00.00.01.02.00.01”被分配给MAC地址为 “00.19.B9.FA.88.E2”、IP地址为“10.5.1.2”的终端主机)，用来编 码这些终端主机在网络拓扑中的位置。PMAC代替实际的MAC地址存储在 转发表中，用于数据包的转发。不同于MAC地址的平面结构，PMAC是层 次化的，可以聚合，因此交换机只需要保存很小的转发表。另外，PortLand 引入了一个中心化的架构管理器(Fabric Manager-FM)300。FM 300 维护网络配置信息和状态(比如，拓扑结构等)。不同于传统以太网中的 纯广播机制，FM 300可以帮助进行ARP解析和提高容错性能。

Portland协议是基于Fat Tree网络拓扑(参考文献[3])的寻址、 路由和转发协议。在Fat Tree网络拓扑中，交换机分成三层：边缘层、 汇聚层和核心层。不同层中所有的交换机都是相同的，每个交换机包含 k个端口。图3示出了k＝4的Fat Tree网络拓扑结构。Fat Tree分为k 个独立的分块(pod)，如图3中边缘层和汇聚层的虚线框所示，每个框 里面的k个交换机组成一个分块。Fat Tree网络拓扑结构可以支持k³/4 台主机，使用5k²/4个k口交换机。

边缘交换机给其所有直接相连的主机分配一个48比特的PMAC地址。 PMAC地址是层次化的，编码了主机在网络拓扑中的位置。PMAC地址的格 式是：

pod.position.port.vmid，

其中

pod：16比特，表示此边缘交换机所处的pod的序号，

position：8比特，表示此边缘交换机在此pod中所处的位置，

port：8比特，表示此主机连接的边缘交换机的端口号，

vmid：16比特，表示此物理机上虚拟机的序号(因为一个物理机上 可能运行多个虚拟机)。

在图3所示的例子中，左侧第三个主机的PMAC地址是：

00.00.01.02.00.01。

其中，

pod：00.00，表示pod 0，

position：01，表示pod 0中位置1，

port：02，表示此主机连接在边缘交换机的2号端口，

vmid：00.01，表示此主机上的虚拟机序号为1。

如图3所示，PMAC地址代替实际的MAC地址存储在转发表(如图3 中最右侧的表格所示)中，用于数据包的转发。不同于MAC地址的平面 结构，PMAC是层次化的，可以聚合，因此交换机只需要保存很小的转发 表。各层交换机的转发表如下：

核心层交换机：

例如，图3中最右端的核心交换机，它的端口0和pod 0相连， 端口1和pod 1相连，等等。因此，所有目的MAC地址为00.00.* 送往端口0，表示所有去往pod 0的数据包都送往端口0；同理， 所有去往pod 1的数据包都送往端口1，等等。

汇聚层交换机：例如，图3中最右端的汇聚交换机，它属于pod 3，即00.11。 所有目的MAC地址为00.11.*的数据包都是发往本pod，其中 00.11.00.*的数据包发往位置为0的边缘交换机，所以发送往 端口0，所有00.11.01.*的数据包发往位置为1的边缘交换机， 所以发送往端口1。其他的目的MAC地址的数据包是发往其他 pod的上行数据包，由端口2或者端口3发送。

边缘交换机：

例如，图3中最右端的边缘交换机，它属于pod 3，位置1，即 00.11.01。它有两个直接相连的主机，所有目的MAC为 00.11.01.00.*的数据包都发送往端口0，所有目的MAC为 00.11.01.01.*的数据包都发送往端口1。其他的目的MAC地址 的数据包是发往其他主机的上行数据包，由端口2或者端口3 发送。

PortLand协议是一种用于数据中心网络的二层寻址、路由和转发协 议。但是，PortLand协议局限于Fat Tree这一网络拓扑，不能方便地 应用到其他拓扑。例如，PortLand协议所使用的PMAC的形式： pod.position.port.vmid不能直接应用于参考文献[2]所提出的Clos网 络拓扑。

图4是示出了Clos网络拓扑的示意图。Clos网络拓扑也是分为三 层，其中ToR(Top of Rack)交换机类似于Fat Tree网络拓扑中的边 缘交换机，与终端主机直接相连。Fat Tree网络拓扑中所有的交换机都 是一样的。但是，在Clos网络拓扑中，核心交换机和汇聚交换机是10G 口的大交换机，而ToR交换机通过10G的上行口连接汇聚交换机，通过 1G的下行口连接主机。

在Clos网络拓扑中不再有pod的概念，所以PMAC格式 (pod.position.port.vmid)无法直接使用。如果将一个汇聚交换机对 应于一个pod，例如，汇聚交换机S3为pod0，汇聚交换机S4为pod1， 则无法编址ToR交换机。因为每个ToR交换机都与两个汇聚交换机相连， 例如，ToR交换机S7既与汇聚交换机S3相连，也与汇聚交换机S4相连， 这样，ToR交换机S7的pod序号可以为0，也可以为1。因此，参考文 献[1]提出的PortLand协议不能直接应用于参考文献[2]提出的这种 Clos网络拓扑。

参考文献：

[1]“PortLand：A Scalable Fault Tolerant Layer 2 Data Center Network Fabric”，Radhika Niranjan Mysore etc.，in Sigcomm 2009

[2]“VL2：A Scalable and Flexible Data Center Network”，Albert Greenberg etc.，in Sigcomm 2009

[3]“A Scalable，Commodity Data Center Network Architecture”，M. Al-Fares etc.，in Sigcomm 2008

发明内容

考虑到现有技术的上述缺陷，本发明提出了一种用于数据中心网络 的编址方法、编址装置、架构管理器、交换机和数据路由方法，适用于 数据中心所采用的多种网络拓扑，可实现位置地址的聚合，以减小转发 表，而且能够容易地实现网络负载均衡。

本发明提出了一种用于数据中心网络的编址方法、编址装置、架构 管理器、交换机和数据路由方法。网络中的主机和交换机被分配一个或 者多个位置地址(locator)，位置地址是层次化的，编码了主机和交换 机在网络拓扑中的位置。当网络拓扑提供了冗余的路径时，给主机和交 换机分配多个位置地址。位置地址代替MAC地址存储在交换机的转发表 里，用于数据包的转发。多个位置地址描述了多条路径，在多条路径中 选择合适的路径可实现负载均衡。

根据本发明的第一方案，提出了一种编址装置，包括：树创建单元， 用于依次以每个交换机为根，通过网络拓扑发现功能，创建包含所有主 机的树，由此，得到多棵树；树选择单元，用于从所述树创建单元所创 建的多棵树中选择具有最小高度的树；以及地址分配单元，用于针对由 所述树选择单元所选择的每一棵具有最小高度的树，为网络中每个交换 机和每个主机分配地址。

优选地，当以一个交换机为根，能够创建出多棵包含所有主机的树 时，所述树创建单元选择以此交换机为根、高度最小的任意一棵树，作 为所创建的树。

优选地，当以一个交换机为根，能够创建出多棵包含所有主机的树 时，所述树创建单元记录所有这多棵树，作为所创建的树。

优选地，当存在多棵高度相同的最小高度的树时，所述树选择单元 选择所有这多棵最小高度的树。

优选地，所述地址分配单元针对由所述树选择单元所选择的每一棵 具有最小高度H的树，为位于所述树的根节点的根交换机，也称为第0 层交换机，分配根交换机位置地址；从与所述根交换机直接相连的第1 层交换机开始，针对与第i-1层交换机直接相连的每一个第i层交换机， 找出从所述根交换机到达此第i层交换机的所有路径，针对每条路径， 为此第i层交换机分配一个第i层交换机位置地址，其格式为：“根交换 机位置地址.第1层交换机地址.….第i层交换机地址”，其中1≤i≤H-2； 为每个主机分配主机位置地址，其格式为：“边缘交换机位置地址.主机 地址”，其中边缘交换机是与主机直接相连的第k层交换机，0≤k≤H-2。

优选地，第i层交换机地址是第i-1层交换机与每一个第i层交换 机相连的端口的端口号。

优选地，主机地址是边缘交换机与每一个主机相连的端口的端口号。

根据本发明的第二方案，提出了一种编址方法，包括：依次以每个 交换机为根，通过网络拓扑发现功能，创建包含所有主机的树，由此， 得到多棵树；从所创建的多棵树中选择具有最小高度的树；以及针对所 选择的每一棵具有最小高度的树，为网络中每个交换机和每个主机分配 地址。

优选地，当以一个交换机为根，能够创建出多棵包含所有主机的树 时，选择以此交换机为根、高度最小的任意一棵树，作为所创建的树。

优选地，当以一个交换机为根，能够创建出多棵包含所有主机的树 时，记录所有这多棵树，作为所创建的树。

优选地，当存在多棵高度相同的最小高度的树时，选择所有这多棵 最小高度的树。

优选地，针对所选择的每一棵具有最小高度H的树，为位于所述树 的根节点的根交换机，也称为第0层交换机，分配根交换机位置地址； 从与所述根交换机直接相连的第1层交换机开始，针对与第i-1层交换 机直接相连的每一个第i层交换机，找出从所述根交换机到达此第i层 交换机的所有路径，针对每条路径，为此第i层交换机分配一个第i层 交换机位置地址，其格式为：“根交换机位置地址.第1层交换机地址.…. 第i层交换机地址”，其中1≤i≤H-2；为每个主机分配主机位置地址， 其格式为：“边缘交换机位置地址.主机地址”，其中边缘交换机是与主机 直接相连的第k层交换机，0≤k≤H-2。

优选地，第i层交换机地址是第i-1层交换机与每一个第i层交换 机相连的端口的端口号。

优选地，主机地址是边缘交换机与每一个主机相连的端口的端口号。

根据本发明的第三方案，提出了一种架构管理器，包括：根据本发 明第一方案所述的编址装置；以及存储器，用于存储全局位置地址表， 所述全局位置地址表包括了每一个主机的因特网协议地址与所述主机的 所有主机位置地址之间的映射。

优选地，所述架构管理器还包括：调度单元，用于在收到地址解析 协议请求时，以目的主机的因特网协议地址为索引查找所述全局位置地 址表，并根据调度算法，从所找到的与目的主机的因特网协议地址对应 的一个或者多个主机位置地址中选择一个主机位置地址返回给源主机， 完成地址解析协议地址解析。

更优选地，当未能从所述全局位置地址表找到与目的主机的因特网 协议地址对应的主机位置地址时，所述调度单元进行全网络的广播，获 得目的主机的一个或者多个主机位置地址，再根据调度算法，从所获得 的与目的主机的因特网协议地址对应的一个或者多个主机位置地址中选 择一个主机位置地址返回给源主机，完成地址解析协议地址解析。

更优选地，所述架构管理器还包括：故障处理单元，用于在交换机 检测到相邻交换机或链路发生故障时，将全局位置地址表中相应的主机 位置地址设为失效，其中所述调度单元在选择与目的主机的因特网协议 地址对应的主机位置地址时，不选择被设为失效的主机位置地址。

根据本发明的第四方案，提出了一种交换机，包括根据本发明第一 方案所述的编址装置。

根据本发明的第五方案，提出了一种数据路由方法，采用了根据本 发明第二方案所述的编址方法编址的交换机位置地址和主机位置地址， 所述数据路由方法包括：根交换机/第0层交换机将包含了“根交换机位 置地址.第1层交换机地址/主机地址.*”作为目的主机的主机位置地址 的数据包转发至端口号为“第1层交换机地址/主机地址”的端口；第i 层交换机将包含了“第i层交换机位置地址.第i+1层交换机地址/主机 地址.*”作为目的主机的主机位置地址的数据包转发至端口号为“第i+1 层交换机地址/主机地址”的端口，其中1≤i≤H-2；以及第i层交换 机将包含了“根交换机位置地址.*”作为目的主机的主机位置地址的数 据包转发至与以具有“根交换机位置地址”作为根交换机位置地址的根 交换机为根节点的第i-1层交换机相连的端口，其中1≤i≤H-2。

本发明提出的新的编址/寻址方案适用于数据中心使用的多种网络 拓扑，例如，Fat Tree网络拓扑、Clos网络拓扑等。位置地址代替MAC 地址存在交换机的转发表里，用于数据包的转发。因为位置地址是层次 化的，可以聚合，因此交换机只需要保存很小的转发表。当网络拓扑提 供了冗余的路径时，主机和交换机具有多个位置地址，这多个位置地址 分别描述了多条路径，在多条路径中选择合适的路径可以方便地实现负 载均衡。

附图说明

通过下面结合附图说明本发明的优选实施例，将使本发明的上述及 其它目的、特征和优点更加清楚，其中：

图1是用于说明交换机通过自学习的方式构建转发表的示意图。

图2是用于说明交换机转发(广播)具有未知目的MAC的数据帧的 示意图。

图3是示出了PortLand系统的系统结构的示意图。

图4是示出了Clos网络拓扑的示意图。

图5是示出了根据本发明的编址装置500的结构方框图。

图6是示出了根据本发明的编址方法600的流程图。

图7是再次示出了参考文献[3]所提出的Fat Tree网络拓扑的示意 图。

图8示出了基于Fat Tree网络拓扑、通过网络拓扑发现功能创建 的一棵树的示例。

图9示出了基于Fat Tree网络拓扑、通过网络拓扑发现功能创建 的另一棵树的示例。

图10示出了基于Fat Tree网络拓扑、通过网络拓扑发现功能创建 的另一棵树的示例。

图11示出了基于Fat Tree网络拓扑的部分编址结果。

图12示出了基于Clos网络拓扑的部分编址结果。

图13是示出了Fat Tree网络拓扑下数据包转发的示例示意图。

图14是示出了包含了根据本发明的编址装置500的示例架构管理 器1400的结构方框图。

图15示出了多个位置地址分别对应多条路径的示意图。

在本发明的所有附图中，相同或相似的结构和步骤均以相同或相似 的附图标记标识。

具体实施方式

下面参照附图对本发明的优选实施例进行详细说明，在描述过程中 省略了对于本发明来说是不必要的细节和功能，以防止对本发明的理解 造成混淆。

图5是示出了根据本发明的编址装置500的结构方框图。根据本发 明的编址装置500可以位于图3所示的架构管理器300中、也可以位于 任何一个交换机中。如图5所示，根据本发明的编址装置500包括：树 创建单元510、树选择单元520和地址分配单元530。

树创建单元510用于依次以每个交换机为根，通过网络拓扑发现功 能，创建一棵包含所有主机的树，由此，得到多棵树。因为网络拓扑可 能会提供冗余的路径，不一定每棵树都包含所有的交换机。另外，以一 个交换机为根，可能会创建出多棵包含所有主机的树，在这种情况下， 可以先于树选择单元520的操作，由树创建单元510先选择以此交换机 为根、高度最小的任意一棵树，作为所创建的树。也可以创建并记录所 有这些树，由树选择单元520统一进行选择。

树选择单元520用于从树创建单元510所创建的多棵树中选择具有 最小高度的树，如果存在多棵高度相同的最小高度的树，则选出所有这 多棵最小高度的树。根据树选择单元520的操作，当存在多棵高度相同 的最小高度的树时，网络拓扑将被构建成一个多根树。

地址分配单元530用于完成网络中每个交换机和每个主机的编址操 作。

为了描述方便，先对网络中的交换机的分层结构进行描述。

将位于每棵树的根节点的交换机称为根交换机(也称为第0层交换 机)，将与第i-1层交换机直接相连的交换机称为第i层交换机(1≤i ≤H-2，H是树的高度)，将与主机直接相连的交换机称为边缘交换机(边 缘交换机可以是第k层交换机，0≤k≤H-2)。

首先，对于所选择的每一棵具有最小高度的树，为该树的根交换机 (也可以称为第0层交换机)分配根交换机位置地址。

然后，从与所述根交换机(第0层交换机)直接相连的第1层交换 机开始，针对每一个第i层交换机，找出从根交换机到达此第i层交换 机的所有路径，针对每条路径，为此第i层交换机分配一个第i层交换 机位置地址，其格式为：“根交换机位置地址.第1层交换机地址.….第 i层交换机地址”，其中第i层交换机地址可以是第i-1层交换机与第i 层交换机相连的端口的端口号。

最后，为每个主机分配主机位置地址，其格式为：“边缘交换机位 置地址.主机地址”，其中主机地址可以是边缘交换机与每一个主机相连 的端口的端口号。

图6是示出了根据本发明的编址方法600的流程图。

在步骤S610，树创建单元510依次以每个交换机为根，通过网络拓 扑发现功能，创建一棵包含所有主机的树，由此，得到多棵树。因为网 络拓扑可能会提供冗余的路径，不一定每棵树都包含所有的交换机。另 外，以一个交换机为根，可能会创建出多棵包含所有主机的树，在这种 情况下，可以先于树选择单元520的操作，由树创建单元510先选择以 此交换机为根、高度最小的任意一棵树，作为所创建的树。也可以创建 并记录所有这些树，由树选择单元520统一进行选择。

在步骤S620，树选择单元520从树创建单元510所创建的多棵树中 选择具有最小高度的树，如果存在多棵高度相同的最小高度的树，则选 出所有这多棵最小高度的树。根据树选择单元520的操作，当存在多棵 (R棵)高度相同的最小高度的树时，网络拓扑将被构建成一个多根树。 所述多根树的高度为H。位于每棵树的根节点的交换机称为根交换机(也 称为第0层交换机)，与第i-1层交换机直接相连的交换机称为第i层交 换机(1≤i≤H-2)，与主机直接相连的交换机称为边缘交换机(边缘 交换机可以是第k层交换机，0≤k≤H-2)。

在步骤S630，地址分配单元530对于所选择的每一棵具有最小高度 H的树，将该树的根节点作为根交换机(也可以称为第0层交换机)，分 配根交换机位置地址。例如，可以依次为每棵树的根节点分配根交换机 位置地址“0”、“1”、…、“R-1”。

在步骤S640，地址分配单元530从与每个根交换机直接相连的第1 层交换机开始，针对每一个第i层交换机，找出从根交换机到达此第i 层交换机的所有路径，针对每条路径，为此第i层交换机分配一个第i 层交换机位置地址，其格式为：“根交换机位置地址.第1层交换机地 址.….第i层交换机地址”，其中第i层交换机地址可以是第i-1层交换 机与第i层交换机相连的端口的端口号。

在步骤S640，地址分配单元530为每个主机分配主机位置地址，其 格式为：“边缘交换机位置地址.主机地址”，其中主机地址可以是边缘交 换机与主机相连的端口的端口号。

对于位置地址“根交换机位置地址.第1层交换机地址.第2层交换 机地址.….第i层交换机地址.….边缘交换机地址.主机地址”，每层 地址可以用8比特表示。这样当通过拓扑发现功能得到的多根树的高度 H小于等于6时，位置地址的长度不会超过MAC地址的48比特的空间。

当位置地址未用满6层(48比特)时，用全1填充表示无效地址(可 以由地址分配单元530完成)。例如，“0.1.2.3.255.255”表示这个主机 的位置地址格式为“根交换机位置地址.第一层地址.第二层地址.主机地 址”，具体值为“0.1.2.3”。在本说明书的描述中，为了行文方便，无效 地址通常被省略，即“0.1.2.3”就表示“0.1.2.3.255.255”。

“根交换机位置地址”的地址空间大小是由根交换机的个数决定的， 8比特最多可以表示255个根交换机。核心层的交换机一般是10G口的 大交换机，假设核心层交换机是128口，共255个，那么可以支持 255*128*10＝326，400个主机的1G线速通信，这个数目完全可以满足一 个数据中心的最大规模。

除“根交换机位置地址”以外，其他“第1层交换机地址”、“第2 层交换机地址”、…、“第i层交换机地址”和“主机地址”的地址空间 大小是由交换机的端口数决定的，8比特最多可以表示255个端口，也 可以满足现有交换机的需求。

另一方面，当通过拓扑发现功能得到的多根树的高度H大于6时， 需要对位置地址“根位置地址.第1层交换机地址.第2层交换机地址.…. 第i层交换机地址.….边缘交换机地址.主机地址”进行压缩。假定某层 地址的最大地址空间≤2^N-1，就把这层的比特数压缩到N比特(可以由 地址分配单元530完成)。因为每层不再由固定长度8比特表示，在这种 情况下，在完成拓扑发现之后，架构管理器300(图3)需要将每层的比 特长度通知给所有交换机。

本发明提出的新的编址方案可适用于数据中心使用的多种网络拓 扑，下面给出几种常用网络拓扑下编址的例子。

图7示出了参考文献[3]所提出的Fat Tree网络拓扑。具体描述可 参考对图3的具体内容，为了行文简洁，此处不再赘述。

图8示出了基于Fat Tree网络拓扑、通过网络拓扑发现功能创建 的一棵树的示例。

如图8所示，树创建单元510以交换机S1为根，通过网络拓扑发 现功能，创建了一棵包含所有主机的树，树的高度H＝4(步骤S610)。

图9示出了基于Fat Tree网络拓扑、通过网络拓扑发现功能创建 的另一棵树的示例。

如图9所示，树创建单元510以交换机S5为根，通过网络拓扑发 现功能，创建了另一棵包含所有主机的树，树的高度H＝5(步骤S610)。

图10示出了基于Fat Tree网络拓扑、通过网络拓扑发现功能创建 的另一棵树的示例。

如图10所示，树创建单元510以交换机S13为根，通过网络拓扑 发现功能，创建了另一棵包含所有主机的树，树的高度H＝6(步骤S610)。

按照以上操作，树创建单元510针对图7所示的Fat Tree网络拓 扑一共可以创建至少20棵树。

图11示出了基于Fat Tree网络拓扑的部分编址结果。

树选择单元520从树创建单元510所创建的至少20棵树中选择具 有最小高度的树(H＝4)。一共有4棵高度H＝4的树，分别以4个核心交 换机S1、S2、S3和S4为根(步骤S620)。

因此，地址分配单元530分别将这4个核心交换机S1、S2、S3和 S4作为根交换机，分配根交换机位置地址分别“0”、“1”、“2”、“3”(步 骤S630)。

交换机S5～S12直接和根交换机相连，是第1层交换机。对于每个 第1层交换机，从根交换机出发到达这些交换机有两条路径，所以这些 交换机被分配两个位置地址。例如，交换机S5，一条路径是S1→S5，假 设交换机S5连接到根交换机S1的第0号端口，那么对应这条路径，交 换机S5得到的交换机位置地址是“0.0”。另外一条从根交换机到交换 机S5的路径是S2→S5，假设交换机S5和根交换机S2的第0号端口相 连，那么对应这条路径，交换机S5得到的交换机位置地址是“1.0”。交 换机S13～S20和第1层交换机相连，是第2层交换机。对于每个第2 层交换机，从根交换机出发到这些交换机有4条路径，所以这些交换机 被分配4个位置地址。例如，交换机S13，4条路径分别为：S1→S5→S13、 S2→S5→S13、S3→S6→S13、S4→S6→S13，对应的4个交换机位置地址 分别为：“0.0.0”、“1.0.0”、“2.0.0”和“3.0.0”(步骤S630)。

主机与边缘交换机(第2层交换机)直接相连，对应边缘交换机的 每个交换机位置地址，主机被分配一个主机位置地址，因此，图11中的 每个主机有4个主机位置地址。例如，主机H1与交换机S13的第0号端 口相连，因此对应交换机S13的4个交换机位置地址“0.0.0”、“1.0.0”、 “2.0.0”和“3.0.0”，此主机H1的主机位置地址分别为“0.0.0.0”、 “1.0.0.0”、“2.0.0.0”和“3.0.0.0”(步骤S640)。

图12示出了基于Clos网络拓扑的部分编址结果。

树创建单元510针对图12所示的Fat Tree网络拓扑一共可以创建 至少10棵树。

树选择单元520从树创建单元510所创建的至少10棵树中选择具 有最小高度的树(H＝4)。一共有2棵高度H＝4的树，分别以2个核心交 换机S1和S2为根(步骤S620)。

因此，地址分配单元530分别将这2个核心交换机S1和S2作为根 交换机，分配根交换机位置地址分别“0”和“1”(步骤S630)。

交换机S3～S6直接和根交换机相连，是第1层交换机。对于每个 第1层交换机，从根交换机出发到达这些交换机有两条路径，所以这些 交换机被分配两个位置地址。例如，交换机S3，一条路径是S1→S3，假 设交换机S3连接到根交换机S1的第0号端口，那么对应这条路径，交 换机S3得到的交换机位置地址是“0.0”。另外一条从根交换机到交换 机S3的路径是S2→S3，假设交换机S3和根交换机S2的第0号端口相 连，那么对应这条路径，交换机S3得到的交换机位置地址是“1.0”。交 换机S7～S10和第1层交换机相连，是第2层交换机。对于每个第2层 交换机，从根交换机出发到这些交换机有4条路径，所以这些交换机被 分配4个位置地址。例如，交换机S7，4条路径分别为：S1→S3→S7、 S2→S3→S7、S1→S4→S7、S2→S4→S7，对应的4个交换机位置地址分 别为：“0.0.0”、“1.0.0”、“0.1.0”和“1.1.0”(步骤S630)。

主机与边缘交换机(第2层交换机)直接相连，对应边缘交换机的 每个交换机位置地址，主机被分配一个主机位置地址，因此，图12中的 每个主机有4个主机位置地址。例如，主机H1与交换机S7的第0号端 口相连，因此对应交换机S7的4个交换机位置地址“0.0.0”、“1.0.0”、 “0.1.0”和“1.1.0”，此主机H1的主机位置地址分别为“0.0.0.0”、 “1.0.0.0”、“0.1.0.0”和“1.1.0.0”(步骤S640)。

位置地址代替MAC地址存在交换机的转发表里，用于数据包的转发。 图13是示出了Fat Tree网络拓扑下数据包转发的示例示意图。各层交 换机的转发表如下：

根交换机：

其中“selflocator”表示根交换机自身的根交换机位置地址， 以及“port”表示位于根交换机位置地址后的下一地址字段。

例如，根交换机S1，selflocator是“0”。它的端口0和 S5相连，分配给S5的第一层地址也是“0”，因此目的位置地址 为“0.0.*”的数据包都送往端口0；同理，所有目的位置地址 为“0.1.*”的数据包都送往端口1等。

第i层交换机：

其中“selflocator”表示第i层交换机自身的第i层交换机位 置地址，“port”表示位于第i层交换机位置地址后的下一地址 字段，“parent’s root”表示与第i层交换机相连的第i-1层交 换机的根交换机的根交换机位置地址。

例如，交换机S5，selflocator是“0.0”和“1.0”，端口 0和交换机S13相连，分配给交换机S13的第2层地址也是“0”， 因此，所有目的位置地址为“selflocator.0.*”的数据包都送 往端口0，也就是同理，所有目的位置地址为“selflocator.1.*”的数据包都送 往端口1，也就是交换机S5的端口2和3为上行端口，连到第i-1层交换机， 与其相连的第i-1层交换机称为其父交换机(parent)，交换机 S5有两个父交换机——交换机S1和交换机S2，假设交换机S2 和交换机S5的端口2相连，交换机S2的根节点为其自身(根 交换机位置地址“1”(parent’s root))，因此对应的转发表项 为同理，交换机S1和交换机S5的端口3 相连，交换机S1的根节点为其自身(根交换机位置地址“0” (parent’s root))，因此对应的转发表项为

再例如，交换机S13，selflocator是“0.0.0”、“1.0.0”、 “2.0.0”和“3.0.0”，端口0和主机H1相连，分配给H1的主 机位置地址也是0，因此所有目的位置地址为“selflocator.O.*” 的数据包都送往端口0，也就是同理，所有目的位置地址为“selflocator.1.*”的 数据包都送往端口1，也就是父 换机S13的端口2和3为上行端口，连到第i-1层交换机，与 其相连的第i-1层交换机称为其父交换机(parent)，交换机S13 有两个父交换机——交换机S5和交换机S6，假设交换机S6和 交换机S13的端口2相连，交换机S6的根节点为根交换机S3 (根交换机位置地址“2”(parent’s root))或根交换机S4(根 交换机位置地址“3”(parent’s root))，因此对应的转发表项 为同理，交换机S5和 交换机S13的端口3相连，交换机S5的根节点为根交换机S1 (根交换机位置地址“0”(parent’s root))或根交换机S2(根 交换机位置地址“1”(parent’s root))，因此对应的转发表项 为

当网络拓扑提供了冗余的路径时，主机和交换机分配多个位置地址。 多个位置地址描述了多条路径，在多条路径中选择合适的路径可以实现 负载均衡。

图14是示出了包含了根据本发明的编址装置500的示例架构管理 器1400的结构方框图，以及图15示出了多个位置地址分别对应多条路 径的示意图。

如图14所示，包含了根据本发明的编址装置500的示例架构管理 器1400还包括：存储器1410、调度单元1420和故障处理单元1430。

存储器1410存储了全局位置地址表。全局位置地址表包括了每一 个主机的IP地址与由编址装置500生成的所述主机的所有主机位置地址 之间的映射。

调度单元1420在收到地址解析协议(ARP)请求时，以目的主机的 IP地址为索引查找所述全局位置地址表，并根据调度算法，从所找到的 与目的主机的IP地址对应的一个或者多个主机位置地址中选择一个主 机位置地址返回给源主机，完成ARP地址解析。当未能从所述全局位置 地址表找到与目的主机的IP地址对应的主机位置地址时，调度单元1420 进行全网络的广播，获得目的主机的一个或者多个主机位置地址(可以 将这样得到的一个或者多个主机位置地址与目的主机的IP地址之间的 映射存储到全局位置表中)，再根据调度算法，从所获得的与目的主机的 IP地址对应的一个或者多个主机位置地址中选择一个主机位置地址返 回给源主机，完成ARP地址解析。

故障处理单元1430在交换机检测到相邻交换机或链路发生故障时， 将全局位置地址表中相应的主机位置地址设为失效。此时，调度单元 1420在选择与目的主机的IP地址对应的主机位置地址时，不再选择被 设为失效的主机位置地址。

如图15所示，主机H1是源主机，主机H5是目的主机，主机H5具 有4个位置地址，相对应地，主机H1到主机H5之间有4条不同的路径， 如图14中所示。全局位置地址表(存储于存储器1410中)中存储了所 有主机的所有主机位置地址。当架构管理器收到地址解析协议(ARP)请 求的时候，调度单元1420可以从多个主机位置地址中选择一个主机位置 地址进行应答。对主机位置地址的选择相当于从多个路径中选择一个路 径，选择合适的路径可以实现负载均衡。选择方法可以是随机选择、Round Robin、或者其他调度算法。针对ARP地址解析，架构管理器存储有全局 位置地址表。在收到ARP请求时，架构管理器在全局位置地址表中查找 与目的主机的IP地址相对应的主机位置地址。如果找到了与目的主机的 IP地址对应的一个或者多个主机位置地址，可以根据调度算法，从所找 出的一个或者多个主机位置地址中选择一个主机位置地址，并返回所选 择的目的主机的主机位置地址给源主机，完成ARP地址解析。如果在全 局位置地址表没有找到与目的主机的IP地址对应的主机位置地址，架构 管理器可以进行全网络的广播，获得目的主机的一个或者多个主机位置 地址，并采用调度算法从所获得的一个或者多个主机位置地址中选择一 个主机位置地址，并返回所选择的目的主机的主机位置地址给源主机， 完成ARP地址解析。由于架构管理器的参与，大部分情况下不需要进行 全网广播。

另外，因为数据中心中包含了成千上万台服务器和交换机，并且经 常支撑着数据密集型应用，因此对数据中心网络的容错性要求比较高。 本发明由于采用了与一个交换机对应的一个或多个交换机位置地址，可 以方便地提供容错性。交换机之间通过定期交换Keep Alive消息来检测 邻居交换机的运行状态(可以由交换机中的故障检测单元完成)。当交换 机或者链路出现故障时，相邻交换机的故障检测单元可以检测到此故障 并报告给架构管理器，故障处理单元1430将全局位置地址表中相应的主 机位置地址设为失效。这样，在处理稍后的ARP请求时，调度单元1420 就不再选择被设为失效的主机位置地址，而是选择其他有效的主机位置 地址，来完成ARP地址解析。

这里所公开的本发明实施例的其他设置包括执行在先概述并随后 详述的方法实施例的步骤和操作的软件程序。更具体地，计算机程序产 品是如下的一种实施例：具有计算机可读介质，计算机可读介质上编码 有计算机程序逻辑，当在计算设备上执行时，计算机程序逻辑提供相关 的操作，从而提供上述编址方案。当在计算系统的至少一个处理器上执 行时，计算机程序逻辑使得处理器执行本发明实施例所述的操作(方法)。 本发明的这种设置典型地提供为设置或编码在例如光介质(例如 CD-ROM)、软盘或硬盘等的计算机可读介质上的软件、代码和/或其他数 据结构、或者诸如一个或多个ROM或RAM或PROM芯片上的固件或微代码 的其他介质、或专用集成电路(ASIC)、或一个或多个模块中的可下载的 软件图像、共享数据库等。软件或固件或这种配置可安装在计算设备上， 以使得计算设备中的一个或多个处理器执行本发明实施例所述的技术。 结合诸如一组数据通信设备或其他实体中的计算设备进行操作的软件过 程也可以提供根据本发明的编址装置。根据本发明的编址装置也可以分 布在多个数据通信设备上的多个软件过程、或者在一组小型专用计算机 上运行的所有软件过程、或者单个计算机上运行的所有软件过程之间。

应该理解，严格地讲，本发明的实施例可以实现为数据处理设备上 的软件程序、软件和硬件、或者单独的软件和/或单独的电路。

至此已经结合优选实施例对本发明进行了描述。应该理解，本领域 技术人员在不脱离本发明的精神和范围的情况下，可以进行各种其它的 改变、替换和添加。因此，本发明的范围不局限于上述特定实施例，而 应由所附权利要求所限定。