用于拆分式体系结构中快速故障转移的控制器安排

摘要

一种由网络拓扑设计系统(301)实现的方法，网络拓扑设计系统包括处理装置(303)。方法要确定在带有拆分式体系结构的网络内控制器(315)的安排，其中，拆分式体系结构网络的控制平面组件由控制器执行，并且控制平面组件与拆分式体系结构网络的数据平面组件分开。控制器的安排经选择以最小化由链路故障、交换器故障或在控制器与数据平面组件之间连接性丢失造成的拆分式体系结构网络的中断。

说明书

相关申请交叉引用

本申请涉及2011年9月19日提出的美国专利申请13/236296。

技术领域

本发明的实施例涉及网络的组织和设计。具体而言，本发明的实施例涉及用于为控制与转发分离的拆分式体系结构网络中的交换器确定控制器的安排的方法和系统。

背景技术

拆分式体系结构网络在网络的控制与转发组件之间引入了分隔。在此类体系结构的用例中有电信级网络的接入/聚合域、移动回程、云计算和多层（L3和L2和L1、OTN、WDM）支持、数据中心，所有这些均在网络体系结构的主要组成部分中。因此，这些网络的适当设计、管理和性能优化十分重要。

不同于在相同的盒（网络元件）中集成转发（数据）平面和控制平面的传统网络体系结构，拆式式体系结构网络将这两个平面分离，并且在可能与转发元件（交换器）在不同的物理位置中的服务器上执行控制平面。网络中拆分式体系结构的使用允许简化实现转发平面的交换器，并且将网络的智能移到监视交换器的多个控制器中。

在传统体系结构中转发和控制平面的紧密耦合通常导致过度复杂的控制平面和复杂的网络管理。众所周知的是，这对新协议和技术发展造成大的负担和高障碍。尽管线速、端口密度和性能快速改进，网络控制平面机制一直以比转发平面机制更慢得多的速度发展。

在拆分式体系结构网络中，控制器从交换器收集信息，并且计算和分布适当的转发决定到交换器。控制器和交换器使用协议传递和交换信息。此类协议的示例是OpenFlow（请访问www.openflow.org），它提供开放和标准的方法以便交换器与控制器进行通信，并且它在学界和业界都引起了相当大的关注。图1是示出在交换器与控制器之间OpenFlow接口的概观的图。OpenFlow交换器中的转发表填充有由以下项组成的条目：定义用于分组报头中字段的匹配项的规则、与流匹配项相关联的动作及有关流的统计的集合。

进入的分组匹配特定规则时，在分组上执行相关联的动作。规则包含来自协议栈中几个报头的关键字段，例如，以太网MAC地址、IP地址、IP协议、TCP/UDP端口号及进入端口号。为定义流，可使用所有可用匹配字段。但也可能通过将通配符用于不需要的字段，限制匹配规则到可用字段的子集。

拆分式体系结构的分离控制平台减轻了修改网络控制逻辑的任务，并且提供编程接口，开发人员能够在接口上构建广泛的多种新协议和管理应用。在此模型中，数据和控制平面能够独立演进和缩放，同时数据平面元件的成本得以降低。

发明内容

本发明的实施例包括一种由网络拓扑设计系统实现的方法，其中，网络拓扑设计系统包括处理装置。方法确定在带有拆分式体系结构的网络内控制器的安排，其中，拆分式体系结构网络的控制平面组件由控制器执行，并且控制平面组件与拆分式体系结构网络的数据平面组件分开。控制器的安排经选择以最小化由链路故障、交换器故障或在控制器与数据平面组件之间连接性丢失造成的拆分式体系结构网络的中断。方法包括以图表示拆分式体系结构网络的拓扑，拆分式体系结构网络中的链路表示为图中的边缘集，并且拆分式体系结构网络中的网络元件表示为节点集。方法也包括遍历图内的节点集以计算用于每个节点的保护度量，其中，保护度量将拆分式体系结构网络的弹性衡量为对于可能的控制器安排拆分式体系结构网络内节点故障保护的程度，节点故障保护的程度确定节点集中受保护节点的子集，其中，受保护节点的子集中的受保护节点能够通过隧道将控制业务重定向到图中不是受保护节点的下游的中间节点，以及其中，隧道遍历受保护节点的至少一个下游节点。此外，方法包括选择对应于将对网络产生最佳总体保护策略的节点的网络元件，以作为用于拆分式体系结构网络的控制器。

实施例包括带有拆分式体系结构的网络，其中，拆分式体系结构网络的控制平面组件由控制器执行，并且控制平面组件与拆分式体系结构网络的数据平面组件分开。控制器的安排经选择以最小化由链路故障、交换器故障或在控制器与数据平面组件之间连接性丢失造成的拆分式体系结构网络的中断。网络包括通过通信链路集互连的网络元件集，网络元件集中的每个网络元件执行由控制器控制并且与其进行通信的交换器。控制器由网络元件集的一个网络元件执行，其中，拆分式体系结构网络内网络元件集中网络元件的位置提供在控制器与网络元件集中每个网络元件之间优化数量的受保护节点。优化位置对应于用于网络元件集中所有网络元件的最佳保护策略。保护度量将拆分式体系结构网络的弹性衡量为拆分式体系结构网络内节点故障保护的程度，节点故障保护的程度确定网络元件集中受保护网络元件的子集，其中，受保护网络元件的子集中的受保护网络元件能够通过隧道将控制业务重定向到图中不是受保护网络元件的下游的中间节点，以及其中，隧道遍历受保护网络元件的至少一个下游网络元件。

实施例包括用于为拆分式体系结构网络确定控制器的安排的计算机系统，其中，拆分式体系结构网络的控制平面组件由控制器执行，并且控制平面组件与拆分式体系结构网络的数据平面组件分开。控制器的安排经选择以最小化由链路故障、交换器故障或在控制器与数据平面组件之间连接性丢失造成的拆分式体系结构网络的中断。计算系统包括配置成执行拓扑图表示模块和控制器安排模块的处理器，拓扑图表示模块配置成以图表示拆分式体系结构网络的拓扑，拆分式体系结构网络中的链路表示为图中的边缘集，并且拆分式体系结构网络中的网络元件表示为节点集。控制器安排模块配置成遍历图内的节点集以计算用于每个节点的保护度量。保护度量将拆分式体系结构网络的弹性衡量为对于可能的控制器安排拆分式体系结构网络内节点故障保护的程度，节点故障保护的程度确定节点集中受保护节点的子集，其中，受保护节点的子集中的受保护节点能够通过隧道将控制业务重定向到图中不是受保护节点的下游的中间节点，以及其中，隧道遍历受保护节点的至少一个下游节点。控制器安排模块还配置成将对应于带有最佳保护度量的节点的网络元件选择为用于拆分式体系结构网络的控制器。

附图说明

本发明通过示例方式而不是限制的方式在附图的图形中示出，图中相似的标号表示类似的元件。应注意的是，在此公开内容中对“一”或“一个”实施例的不同引用不一定为相同的实施例，并且此类引用至少表示一个。此外，结合实施例描述某个特定特征、结构或特性时，应认为结合无论是否明确描述的其它实施例来影响此类特征、结构或特性是在本领域技术人员的认知之内。

图1是用于OpenFlow网络的示例体系结构的一个实施例的图。

图2A和2B是包含受保护和未受保护交换器的拆分式体系结构网络的一个实施例的图，每个图示出单独的保护机制。

图3是耦合到带有优化控制器安排的网络的设计系统的一个实施例的图。

图4是控制器安排优化过程的一个实施例的流程图。

图5是最佳控制器安排过程的一个实施例的流程图。

图6是“贪婪”控制器安排过程的一个实施例的流程图。

具体实施方式

在下面的描述中，陈述了许多特定细节。然而，要理解的是，实践本发明的实施例可无需这些特定细节。在其它情况下，公知的电路、结构和技术未详细显示以免混淆对此描述的理解。然而，本领域的技术人员将领会到，可无需此类特定细节而实践本发明。通过包括的描述，本领域技术人员将能够在不进行不当实验的情况下实现适当的功能性。

流程图的操作将参照图的示范实施例进行描述。然而，应理解折是，流程图的操作能够通过与参照图所述的那些实施例不同的本发明的实施例执行，并且参照图所述的实施例能够执行与参照流程图所述的那些实施例不同的操作。

所述图中所示技术可使用一个或更多个电子装置（例如，终端站、网络元件、服务器或类似电子装置）上存储和执行的代码和/或数据来实现。此类电子装置使用非暂时性机器可读或计算机可读媒体存储和传递（在内部和/或通过网络与其它电子装置）代码和数据，如非暂时性机器可读或计算机可读存储媒体（例如，磁盘、光盘、随机存取存储器、只读存储器、闪存装置及相变存储器）。另外，此类电子装置一般情况下包括耦合到诸如一个或更多个存储装置、用户输入/输出装置（例如，键盘、触摸屏和/或显示器）和网络连接等一个或更多个其它组件的一个或更多个处理器的集合。处理器的集合与其它组件的耦合一般情况下是通过一个或更多个总线和桥接器（也称为总线控制器）。存储装置表示一个或多个非暂时性机器可读或计算机可读存储媒体和非暂时性机器可读或计算机可读通信媒体。因此，给定电子装置的存储装置一般情况下存储代码和/或数据以便在该电子装置的一个或更多个处理器的集合上执行。当然，本发明的实施例的一个或更多个部分可使用软件、固件和/或硬件的不同组合来实现。

在本文中使用时，网络元件（例如，路由器、交换器、桥接器或类似连网装置）是一件连网设备，包括硬件和软件，其在通信上与网络上的其它设备（例如，其它网络元件、计算机终端站或类似连网装置）互连。一些网络元件是“多服务网络元件”，其为多个连网功能（例如，路由选择、桥接、交换、第2层聚合、会话边界控制、多播和/或订户管理）提供支持和/或为多个应用服务（例如，数据集合）提供支持。本文中所述实施例使用交换器形式的网络元件的示例。然而，实施例不限于交换器，并且适用于其它类型的网络元件。

在本文中使用时，弹性是在面临故障和对正常操作的挑战时提供和保持可接受的服务级别的能力。在本文中使用时，故障概率是工程系统或组件发生故障的频率，表示为每小时的故障数量，或每个节点在长时间期内发生故障的概率。

评估网络设计时，网络弹性是重要因素，这是因为几毫秒的故障可容易在高速链路上造成兆兆字节数据丢失。在控制和数据分组均在相同链路上传送的传统网络中，在故障发生时，控制和数据信息同样受影响。有关网络弹性的现有工作因此一直采取带内控制模型，这意味着控制平面和数据平面具有相同弹性属性。然而，此模型不适用于拆分式体系结构网络。

链路故障指示遍历链路的业务不再能够通过链路传送。故障能够源于在两个交换器之间的链路或源于在一个控制器与它连接到的交换器之间的链路。大多数情况下，这些链路独立发生故障。

交换器故障指示对应网络元件不能发起，响应或转发任何分组。交换器故障能够由软件漏洞、软件故障、配置错误及类似问题造成。大多数情况下，这些交换器独立发生故障。

故障的特殊情况包括在交换器与控制器之间的连接性丢失。交换器能够由于沿在交换器与控制器之间的路径的中间链路或节点上的故障而失去到其控制器的连接性。在一个实施例中，无论何时交换器不能与其指派的控制器进行通信，即使转发平面上的路径仍有效，交换器也将丢弃在控制器管理的转发平面上的所有分组。在其它实施例中，业务的子集能够在转发平面上转发，或者类似有限功能性能够在有限时间内继续，直至与指派的控制器或另一控制器的连接得以重新建立。因此，这能够视为交换器故障的特殊情况。

拆分式体系结构网络中的控制分组能够在与数据分组不同的路径上（或甚至上单独的网络上）传送。因此，在这些网络中控制平面的可靠性不再与转发平面的可靠性直接有关。然而，拆分式体系结构中在控制器与转发平面之间的连接断开能够禁用转发平面；交换器与其控制器断开连接时，它不能接收有关如何转发新流的任何指示，并且变成实际上离线。

在拆分式体系结构网络的一个实施例中，每个交换器预编程有到达控制器的路径。在链路或节点故障发生时，交换器依赖控制器检测此类故障，并且重新计算用于交换器的新路径。然而，所有故障由控制器处理能够导致网络中出现大的延迟。在另一实施例中，到中间交换器的隧穿和/或备份路径的预配置用于与控制器重新建立通信，以便如果主输出链路不正常工作，则能够使用备份（辅助）输出链路或通过隧道到中间交换器的控制业务的封装。

交换器在其外出链路或其直接上游节点中检测到故障时，它立即更改其到控制器的路由，并且使用在交换器中预编程的备用路径（即，外出接口）重新连接到控制器。在备选中，交换器检测到故障，并且将控制业务封装以通过隧道传送到中间交换器，中间交换器将控制业务解封，并且将控制业务转发到控制器。此操作的进行无需涉及控制器，并且对网络中剩余的路由和下游节点到控制器的连接无任何影响。换而言之，在受影响交换器的外出接口中将只存在本地更改。网络中的所有其它连接将保持完好无损。在无此类备用路径或封装选择的情况下，控制器对交换器或链路中任何故障的检测必须基于一些隐式机制，如在控制器未从交换器收到问候(Hello)消息时。这在网络中引入了大的延迟，以便检测故障的确切位置和重新建立控制器-交换器连接。如果无备用路径或隧穿选择能够配置用于交换器，则在到控制器的主要路径中发生故障的情况下，交换器到控制器的连接将中断。

在本文中使用时，如果任何以下条件成立，则交换器被视为受到保护（在其到控制器的连接方面），以防止其直接上游交换器和其外出链路的故障：i)交换器能够为其朝向控制器的控制业务使用备用外出链路；或者ii)交换器能够将控制业务通过隧道发送到另一（中间）交换器并从那里到控制器。

在受保护交换器的外出链路或直接上游节点中发生故障时，交换器能够使用备用外出链路（如果条件i成立）以重新连接到控制器。备选（如果条件ii成立），交换器能够在数据消息中封装控制消息并将它发送到另一（中间）交换器。中间交换器接收此消息时，它将消息解封装，并且将消息象其自己的控制业务一样发送到控制器。

如果上述两个条件均未得到满足，则在外出链路或直接上游上交换器中发生故障的情况下，在交换器与控制器之间的连接将中断。目标是最小化此类中断的机会。最大弹性情形明显是在网络中的每个交换器受到保护时。但如果情况不是如此，则要求进行一些优化以最小化控制业务中断的风险。

通过在拆分式体系结构网络中使用此保护方案，重要是安排控制器，使得在控制平面与转发平面之间的连接更不可能中断。控制器位置的好选择必须产生从交换器到控制器的可靠路径，表现在大量的交换器必须具有到控制器的备用路径。

本发明的实施例提供用于避免现有技术的缺点的方法和系统。有关拆分式体系结构网络设计的现有提议为网络控制器采取固定位置。虽然一直存在有关在网络控制器与交换器之间路由选择机制的一些研究，但尚未形成用于为网络控制器选择优化位置的策略。因此，拆分式体系结构中的控制器安排未将在控制器与转发平面之间连接断开的可能性考虑在内以及寻求最小化此可能性。

此外，用于带有多个控制器的拆分式体系结构网络的方案集中将网络分区，并且指派一个控制器到每个分区，从而很好地连接每个分区内的交换器。这未解决在未分区的给定网络中查找用于控制器的最佳位置。用于在拆分式体系结构网络中安排单个控制器的方案可在最大化在控制器与交换器之间连接的弹性的节点安排控制器，然而，这些方案是基于保护的受限定义。在此类方案中，受保护交换器是带有备用外出链路的交换器，并且未考虑通过隧道将控制业务发送到另一交换器并且从那里发送到控制器的可能性。

本发明的实施例克服了现有技术的这些缺点。本发明的实施例在拆分式体系结构区域中在选择成优化在该区域中交换器与控制器之间连接弹性的位置中安排单个控制器。不进行有关如何将拆分式体系结构区域分区的假设。分区如果进行，则能够基于诸如地理约束等任何任意度量。本发明的实施例包含两个示例过程（即，最佳过程和贪婪过程），过程用于选择控制器位置以优化在控制器与交换器之间连接弹性，即，通过直接备用链路或者通过将控制业务隧穿到不在故障点下游的中间网络元件，最大化带有到控制器的预配置的备用路径的交换器的数量。

实施例支持用于受保护交换器的更普遍定义。如果没有用于交换器的备用外出接口，则如果它能够将其控制业务发送到另一（中间）交换器并从那里发送到控制器，仍认为交换器受保护。在此情况下，交换器在到中间交换器的数据消息内封装控制消息。中间交换器接收此消息时，它将消息解封装，并且将消息（象其自己的控制业务一样）发送到控制器。此备选保护机制在本文中称为基于隧穿的保护，并且术语隧穿是指在数据消息内封装业务消息，将它发送到中间交换器，并且最后在中间交换器将它解封装的过程。通过使用保护的此更普遍定义，实施例包括在网络中最佳安排控制器，使得弹性得以最大化的过程和系统。

网络控制器位置

在控制平面与转发平面之间连接的弹性在拆分式体系结构网络中十分重要。如果此连接中断，则转发平面将不知道如何转发新流（即，在交换器无现有规则的那些流），并且将失去其转发功能性。本发明的实施例提供了判定在何处安排拆分式体系结构控制器的过程，使得此连接（在控制平面与转发平面）之间不太可能中断。假定有某个网络拓扑，过程寻求在网络中选择正确的节点以在该节点定位控制器。网络控制器的位置的好选择必须产生从交换器到控制器的可靠路径，表现在每个交换器必须具有将不受相同故障影响的到控制器的备用（辅助）路径或基于隧穿的保护，如果其主要路径发生故障，则此备用路径能够是在检测到故障的交换器与网络中与控制器保持通信的另一交换器之间的直接链路，或者是通过隧道在检测到故障的交换器与中间交换器之间间接链路形式的基于隧穿的保护，其中，隧道遍历至少一个下游交换器。

保护度量

为评估网络中不同控制器安排策略（并且形成用于选择好位置的政策），利用了基于节点保护的保护度量。如上所定义和如本文中下面进一步解释的一样，此度量应用到拆分式体系结构以评定网络防止链路故障的弹性。

瞬态故障甚至在管理良好的因特网协议(IP)网络中较频繁发生。然而，随着输送重要服务的需求增大，网络服务预期始终是可用的。由于对网络可靠性的高要求，本发明的实施例寻求改进在拆分式体系结构网络中在控制器与交换器之间连接性的弹性。

网络环境

本发明的实施例提供在故障后尽快恢复数据分组的转发的过程。诸如开放式最短路径优先(OSPF)和中间系统到中间系统(IS-IS)等现有内部网关协议(IGP)一般要几秒时间收敛，这不满足预期实现网络可靠性的低于50 ms级别的故障恢复时间。控制器能够使用一些隐式机制检测交换器或链路中的故障，例如，在控制器未收到来自交换器的问候消息时。然而，此方法也将在网络中为故障检测和服务恢复带来大的延迟。

在一个实施例中，保护交换的判定由控制器（即，在检测到故障的网络元件）在本地做出和预确定。这不同于传统网络中的情形，这是因为该网络元件不具有网络的完整拓扑。该网络元件只是转发平面中的简单交换器，并且只接收来自控制器的转发规则。在失去到控制器的连接性时，交换器要独立做出故障转移的判定而无来自控制器的任何指示。换而言之，在受影响交换器的外出接口中将只存在本地更改。网络中的所有其它连接将保持完好无损。这样，过程使转发元件（即，交换器）保持尽可能简单。

在一个实施例中，控制器与交换器在相同物理网络中。也就是说，拆分式体系结构网络的现有基础设施（现有链路和交换器）用于将控制器连接到网络中的所有交换器，而不是使用单独的基础设施连接控制和转发平面。在其它实施例中，单独的网络基础设施用于通信或其任何组合。

在本文中使用时，交换器的网络由图G= (V, E)表示，其中，V是网络中的节点（交换器和控制器）集，并且E是节点之间的双向边缘（链路）集。成本与网络中的每个链路相关联。基于指派的链路成本，计算在网络中任何两个节点之间的最短路径路由。假设在每个链路上的成本适用于链路的两个方向。也假设在交换器与控制器之间发送的控制业务上无负载平衡。因此，每个节点只具有到达控制器的一个路径。换而言之，控制业务通过根在控制器的树从和向控制器发送，该树在本文中将称为控制器路由选择树。此路由选择树包括网络中的所有节点和边缘的子集。相同的路由选择树用于在控制器与交换器之间在两个方向上的通信。

通过给定的控制器位置，任何最短路径路由选择协议形成根在控制器节点的树T，该树包括所有节点和边缘的子集。如上所提及的一样，此树称为控制器路由选择树。图2A和2B示出网络及其控制路由选择树。在这些图中，虚线示出网络中的所有链路，并且实线示出在控制器路由选择树中使用的链路。每个节点能够通过沿控制器路由选择树中的路径发送其控制业务而到达控制器。在这些示例中，每个链路的两个方向具有相同成本，并且因此相同路由选择树将用于在控制器与交换器之间在两个方向上的通信。

在控制器路由选择树T中，如果在T中有从节点v到节点u朝向控制器的路径，则节点u是节点v的上游节点。如果在T中有从节点u到节点v朝向控制器的路径，则节点u是节点v的下游节点。在图2A和2B所示示例网络中，例如节点S4是节点S7和S8的上游节点，并且这两个节点是节点S4的下游节点。在控制器路由选择树中，节点的父项是其直接上游节点，并且节点的子项是其直接下游节点。由于假设的树结构原因，每个节点在T中只具有一个直接上游节点。在示例中及在控制器安排过程的实施例中，假设在从交换器发送到控制器的控制业务上无负载平衡。也就是说，我们假设网络中的每个节点在T中只具有一个直接上游节点。为清晰和准确起见，本文中引入的符号（例如，G、T、u和v）在本文中下面用于表示这些概念。

节点和链路故障

如本文中上面所述，如果交换器能够满足以下任一条件，则认为交换器（在其到控制器的连接中）受到保护，防止其直接上游交换器和其外出链路的故障：

i)      为其向控制器的控制业务使用备用外出链路；

          或者

ii)     通过隧道将其控制业务发送到另一（中间）交换器并从那里发送到控制器。

例如，如果条件(i)成立，则检测到其外出链路或其直接上游节点中故障的受保护交换器将在一检测到故障时便立即更改其到控制器的路由，并且使用备用外出链路重新连接到控制器。如果条件(ii)成立，则交换器能够在到中间交换器的数据消息内封装控制消息。中间交换器接收此消息时，它将消息解封装，并且将消息（象其自己的控制业务一样）发送到控制器。在两种情况下，进行控制业务的重新路由选择而对其它交换器到控制器的剩余连接无任何影响。换而言之，在受影响交换器的外出接口中将只存在本地更改。网络中的所有其它连接将保持完好无损。在一个实施例中，交换器能够自动执行这些故障转移过程（即，绑定到条件(i)或(ii)的那些过程）的任一过程而无需控制器的参与。

如果这两个条件均未得到满足，则在到控制器的主要路径中发生故障的情况下，在交换器与控制器之间的连接将中断。本文中所述控制器安排过程和系统设计成最小化此类中断的机会。网络的最具弹性配置明显是在网络中的每一个交换器受到保护时。但如果该配置不可能实现，则要求进行控制器安排的一些优化以最小化网络中在控制器与交换器之间控制业务中断的风险。

对于直接连接到控制器的那些交换器，由于直接上游节点是控制器，因此，未定义或量化上游节点保护。在部署传统故障管理工具的拆分式体系结构网络中，没有使节点向其下游节点通知故障的扩展信令机制。因此，如果交换器与控制器断开连接，则即使所有其下游节点本身受到保护，以防止其外出链路或直接上游节点故障，它们也将断开连接。这意味着在评估网络弹性中，应赋予更靠近控制器（它是控制器路由选择树的根）的节点更大的重要性。为表示影响网络弹性的网络的这些方面，为每个节点定义了基于其下游节点的数量的权重。

路由选择树的权重能够定义成所有其未受保护节点的权重之和。这些权重能够用于衡量对于相关联控制器位置网络的“不可保护性”或弹性。对于给定路由选择树T，此路由选择树权重能够描述或表示为“weight(T)”，该权重应最小化以便最大化网络的弹性。

图2A和2B示出示例网络和两个故障情形。这些图形中在交换器与控制器之间的实线示出在控制器与交换器之间的最短路径树。如果网络中无故障，则控制业务将在实线表示的此树上向/从控制器发送。

例如，此网络中的交换器S4通过其上游父项S1连接到控制器。在图2A和2B所示两种情形中，交换器S4受到保护。这是因为在直接上游交换器S1或连接S4和S1的链路中发生故障的情况下，还有用于交换器S1的控制业务到达控制器的备用路径。在图2A所示情况中，有由虚线表示的在S4与S5之间的链路。此链路不是路由选择树的一部分，因此，此链路能够在S4中配置为用于控制业务的备用外出链路。因此，如果S4检测到在交换器S4与S1之间的主要外出链路中或者在上游交换器S1的故障，则交换器S4能够使用在交换器S4与S5之间的备用外出链路。

在图2B所示情况中，没有连接S4到另一交换器的能够用作备用链路的链路。应注意的是，连接S4到其子项（交换器S6和S8）的链路均不能用作用于控制业务的备用外出链路，这是因为它们在路由选择树中没有不通过故障链路或故障交换器（即，在交换器S4与S1之间的链路或交换器S1）到控制器的路径。然而，在此情况下，有在交换器S8与S9之间的链路。此处，交换器S4能够形成从交换器S8到交换器S9的隧道（通过以交换器S9为目的地封装控制业务）。交换器S9接收并解封装此业务时，它能够在路径S9-S5-S2控制器上将业务发送到控制器（象其自己的控制业务一样）。应注意的是，此路径不通过S4和S1，由此避免了在此示例中的故障链路或交换器。换而言之，控制器已选择中间交换器，而该中间交换器到控制器的路径不受交换器S1或在交换器S4与S1之间链路的故障影响。

评估交换器的保护状态

在一个实施例中，拆分式体系结构网络中的每个交换器S能够评估其保护状态。在本文中使用时，“parent(S)”表示交换器S的直接上游交换器，并且“downstream(S)”表示交换器S的所有下游交换器（即，其子项和子项的子项并以此类推）。当且仅当网络中存在交换器A和B使得使用以下标准集理论符号时，根据上面我们的定义，给定网络中的每个交换器才得到保护：

1.   A是在{S} U downstream(S)中 - 即，A是S或交换器S的下游节点之一。

2.   B是在downstream(parent(S))中 

3.   在A与B之间有链路，该链路不是控制器路由选择树的一部分 

如果上述三个条件成立，则在发生故障的情况下，交换器S能够通过隧道将其控制业务发送到交换器B并且从那里发送到控制器。如果交换器A恰巧是S本身，则交换器S能够使用链路S-B作为用于控制业务的备用外出链路；因此，在此特殊情况下无需隧穿。上述条件基本上保证控制业务能够通过与根在节点S的父项的子树不同的子树发送。也就是说，业务能够绕过故障交换器/链路。

由于控制器路由选择树是最短路径树，因此，上述三个条件也保证从交换器B到控制器的路径不通过S及其直接上游节点（父项）。因此，在交换器S检测到故障（在其直接上游节点中或者在连接S到其直接上游节点的链路中）时，能够使用路径S-B-控制器。

回到图2A和2B的示例，图2A中的交换器A=S4和B=S5满足所有上述三个条件，并且在图2B中，交换器A=S8和B=S9满足这些条件。

使用OpenFlow的保护的实现

在一个实施例中，控制器安排过程能够应用到拆分式体系结构网络的任何实现。例如，OpenFlow交换器中的转发表填充有由定义用于分组报头中字段的匹配项的规则、与流匹配项相关联的动作集及有关流的统计的集合组成的条目。OpenFlow规范版本1.1介绍了用于允许在交换器的不止一个端口上的单流匹配触发转发的方法。快速故障转移是此类方法之一。通过使用此方法，交换器执行第一活跃动作集。每个动作集与控制其活跃性的特殊端口相关联。OpenFlow的快速故障转移方法允许交换器更改转发而不要求到控制器的往返行程。

控制器安排过程

网络中节点的保护取决于（对于给定控制器位置）主要路径的选择和控制器位置的选择。如下所设置的一样，定义通用路由选择策略，对于控制器位置的每个选择，该策略选择在网络中用于到达控制器的主要路径。此选择能够基于任何所需度量，例如，象延迟或负载等性能度量。还讨论的是详细搜索包括哪些内容以查找用于此任意选择的主要路径的最佳位置。

设计系统体系结构和带有优化控制器位置的示例网络

图3是耦合到带有优化控制器安排的网络的设计系统的一个实施例的图。该图提供了执行网络设计系统工具的示例网络设计系统301的图示。网络设计系统301能够是任何类型的计算装置，包括台式计算机、服务器、手持式计算装置、控制台装置、膝上型装置或类似计算装置。网络设计系统301包括运行网络设计系统工具的组件的处理器集303，网络设计系统工具包括拓扑图表示（graphing）模块305、控制器安排模块307和类似组件。在其它实施例中，任何或所有这些模块能够实现为硬件模块或装置集。处理器303也能够执行网络管理模块309以便与拆分式体系结构网络进行通信和/或管理该网络。

拓扑图表示模块305能够将网络拓扑转换成代表图，并且在代表图上执行图表示功能以支持控制器安排模块307。如本文中下面进一步所述，控制器安排模块307在拓扑图表示模块305生成的图上操作，并且引导图表示操作以实现最佳安排过程或“贪婪”安排过程，以确定用于控制器的位置。

网络管理模块309能够与控制器安排模块303和/或拓扑图表示模块305进行通信，以发现用于自动化过程的网络拓扑和/或实现在自动化过程中的控制器安排。在其它实施例中，控制器安排模块307生成报告或到用户的类似输出以便实现网络组织，并且网络管理模块309能够被忽略。

所示拆分式体系结构网络是带有与控制器安排优化一致的示例控制器安排的示例实现。在示例中，有控制由交换器317组成的域或拆分式体系结构区域的控制器315。交换器317由控制器315使用示为连接交换器317的虚线的控制器路由选择树319管理，其中，实线321是在交换器317之间的链路。用于确定控制器315位置的过程在本文中下面描述。

用于快速故障转移的优化的控制器位置

相对于图4描述通用控制器安排过程。控制器安排过程的输入是网络的拓扑图G=(V, E)，并且输出是controller_location，即，控制器将位于的网络节点。

通过以图表示拆分式体系结构网络的拓扑，启动通用控制器安排过程（框401）。节点和在节点之间的链路能够通过管理员输入、自动化发现过程或任何其组合确定。图将网络中的网络元件（例如，交换器）表示为图中的节点，在这些网络元件之间的通信链路表示图中的链路或边缘。

随后，过程遍历图中的节点以计算用于图中每个节点的保护度量（框403）。如本文中上面和本文中下面进一步所述的保护度量将拆分式体系结构网络的弹性衡量为对于网络内每个可能控制器位置（即，对于网络中每个可能节点或网络元件）节点故障保护的程度。保护度量将拆分式体系结构网络的弹性衡量为对于可能的控制器安排拆分式体系结构网络内节点故障保护的程度。节点故障保护的程度确定节点集（即，网络元件集）中受保护节点（即，受保护网络元件）的子集，其中，受保护节点的子集中的受保护节点能够通过隧道将控制业务重定向到图中不是受保护节点的下游的中间节点，以及其中，隧道遍历受保护节点的至少一个下游节点。

一旦为图中的每个节点确定了保护度量，便选择图中对应于带有最佳保护度量的节点的网络元件（框405）。随后，将选择的网络元件输出到网络管理员以进行手动实现，或者输出到网络管理模块以进行自动化实现，或者其任何组合。通过此过程的网络元件的选择在整体上为网络提供了优化的保护策略。

有遍历图并且为其中的节点确定保护度量的两个更具体的示例过程。在第一过程 - 最佳安排过程 - 中，搜索用于控制器的所有可能位置，并且选择最大化受保护交换器的数量的一个位置。在第二过程 - “贪婪”过程 - 中，通过更近似的评估进行节点的更快和更简单的遍历。

控制器安排 - 最佳安排过程

该过程的一个实施例在下面表1中示为伪码。

最佳安排过程 

1.   V = set of all nodes in the network; n=|V|（V=网络中所有节点的集；n=|V|）

2.   for each node v in V do（对于V中的每个节点，进行）

3.              T = Controller routing tree rooted at v（T=根在v的控制器路由选择树）

4.              weight(T) = 0

5.              for each node u≠v do（对于每个节点u≠v，进行）

6.                         weight(u) = 0

7.                         If (u is not protected) then（如果（u不受保护），则）

8.                                    weight(u) = 1 + number of downstream nodes of u in T（weight(u) = 1 + T中u的下游节点的数量）

9.                         end

10.                       weight(T) = weight(T) + weight(u);

11.                  end

12.      end

13.      controller_location = node v with minimum weight(T)（带有最小weigh(T)的节点v）

表I

如上一部分中简要描述的一样，用于以图表示的网络中每个节点的保护度量是基于根在该节点的树的权重。计算树的权重，其中，树中每个未受保护下游节点具有与设为0的树的权重的初始值（第4行）相加的权重。对于树中未受保护的每个节点，指派了基于其下游节点数量的权重（第7和8行）。随后，累加这些未受保护节点每个的权重以计算树的权重（第10行）。在所有树权重生成后，为控制器安排选择带有最小权重的树，这是因为由于具有邻近控制器的最少数量的未受保护节点原因，它将为配置提供最大弹性。

此过程相对于图5的流程图进行描述。响应接收来自拓扑图表示模块的拆分式体系结构网络的拓扑图，由控制器安排模块启动最佳安排过程（框501）。随后，过程开始通过图中的每个节点迭代进行（框503）。由于要检查每个节点并且为其生成保护度量，评估的顺序不重要，因此，能够串行或平行迭代节点。

对于图中的每个节点，生成以给定节点用作树的根部的控制器路由选择树（框505）。为此树的权重赋予0的初始值。随后，对于这些路由选择树的每个树，遍历这些树内的节点（框507）。路由选择树内节点的遍历的顺序不重要，并且能够平行或串行检查每个节点。对于每个路由选择树中的每个节点，赋予0的初始权重（框509）。随后，检查当前选择的节点是否如本文中上面所定义般受保护（框511）。如果当前选择的节点不受保护，则计算用于此节点的权重（框515）。通过统计当前选择的节点下游的节点的数量，能够计算权重。下游节点的此数量在总体路由选择树权重的计算中作为用于当前选择的节点的权重。如果路由选择树中当前选择的节点如本文中上面所定义般受保护，则它保持0的权重。

在计算每个节点权重时，将它与当前树的权重或“当前根节点权重”相加（框517）。此相加过程能够迭代进行，在此情况下，进行检查以确定是否需要检查树中的另外节点（框519）。相加过程也能够作为平行过程或类似过程进行。

类似地，进行检查以确定图中所有节点是否已检查以确定其相应控制器路由选择树的权重（框521）。控制器路由选择树的此权重能够是用于对应根节点的保护度量。一旦已计算用于图中所有节点的所有保护度量，便能够选择带有最佳保护度量（例如，最低或最小相关联树权重）的节点以指派为控制器（框523）。

控制器安排 - 贪婪安排过程

如果拆分式体系结构网络的大小很大，则在所有位置中的详尽搜索能够变得十分复杂。在此第二过程中，我们介绍了查找在其直接连接的交换器中带有丰富连接的位置的贪婪方式。在此过程中，节点v的程度（G中其邻居的数量）表示为D(v)。过程通过从以降序排序的网络节点的有序列表挑选第一节点，节点v(1)开始（第3行）。

贪婪安排过程 

1.   V = set of all nodes in the network; n=|V|;（V=网络中所有节点的集；n=|V|）

2.   Sort nodes in V such that D(v(l)) ≥D(v(2)) ≥...≥D(v(n))（将V中的节点排序，使得D(v(l)) ≥D(v(2))≥ ...≥D(v(n))）

3.   selected-node（选择的节点）←v(1)

4. 

5.   for i = 1 to n do（对于i=1到n，进行）

6.              A = neighbors of v(i) in V（A=V中v(i)的邻居）

7.              D '(v(i)) = number of members of A that are connected to at least one other member of A via a path that does not pass through v(i)（D'(v(i))=经不通过v(i)的路径连接到A的至少另一成员的A的成员的数量）

8.              if D '(v(i)) > D'(selected-node) then selected-node ← v(i)（如果D '(v(i)) > D'（选择的节点），则选择的节点←v(i)）

9.              if (D '(v(i)) == D(v(i)) then break（如果(D '(v(i)) == D(v(i))，则中断）

10. end

11. controller-location←selected-node（控制器位置←选择的节点）

表II

此过程中的目标是查找带有最大数量的受保护邻居的节点。此处，D'(v)表示节点v的受保护邻居的数量。在过程的第i次迭代中，计算节点v(i)的受保护邻居的数量（如本文中上面所定义的一样）（第6行），并且如果在受保护邻居的数量方面它好于以前搜索到的节点，则将控制器位置更新成节点v(i)（第7和8行）。在过程找到带有最大数量的受保护邻居的节点时，过程将停止，该节点将被选择为控制器将定位到的节点。

在此过程中使用的保护度量是受保护邻居的最大数量。如前面解释的一样，更靠近控制器的节点（比更远离控制器的那些节点）有更大的权重，这是因为如果其到网络的连接中断，所有其下游节点将受影响并且断开连接。因此，重要的是为控制器挑选位置，使得其邻居 - 即，直接连接到控制器的那些交换器 - 受到很好的保护。

图6是贪婪安排过程的一个实施例的流程图。通过由控制器安排模块接收拆分式体系结构网络的拓扑图，能够启动过程（框601）。随后，检查节点集以便为图中的每个节点确定到相邻节点的链路的数量。随后，基于邻居的数量的此评定，将节点排序（框603）。最初，将带有最多邻居链路的节点设为用于控制器的默认或当前位置。随后，从带有最大数量的邻居的节点开始，并且以降序通过排序列表逐渐进展，过程开始迭代通过每个排序节点（框605）。

随后，分析选择的节点以确定到受保护的邻居的链路的数量（框607）。随后进行检查以比较此节点的受保护链路的数量和设为或最初选择为当前位置的节点的受保护链路的数量（框609）。如果分析的节点超过当前位置节点，则更新当前位置节点（框611）。过程通过检查当前位置节点的受保护节点的数量是否小于要检查的下一节点的邻居的数量来继续（框613）。如果受保护节点的数量超过排序列表中的下一节点的邻居数量，则过程能够结束，并且输出要用作控制器安排位置的当前选择的节点（框615）。否则，过程继续到排序列表中的下一节点。

网络弹性是评估任何网络设计的最重要因素之一。几毫秒的故障可容易在高速传送速率的链路上造成兆兆字节数据丢失。从可行部署的角度而言，用于优化的控制器位置的这些过程最大化在拆分式体系结构中在控制器与交换器之间的弹性。通过最大化带有预配置的备用路径或基于隧道的保护，靠近控制器的受保护的交换器的数量，这些过程最大化了网络的弹性。在发生故障的情况下，受影响的转发元件能够立即交换到其备用路径或基于隧道的路由，并且恢复其与控制器的连接。

本发明的实施例能够为运营商提供以具成本效益方式部署其网络的指导。它们能够改进拆分式体系结构的弹性，这能够防止成千上万的流受瞬间故障影响。

拆分式体系结构网络的使用

拆分式体系结构网络能够部署用于蜂窝回程以支持基于MPLS的转发。在LTE中，它也能够在移动核心中部署以在MME、服务GW和PDN-GW之间路由用户业务。在此情况下，控制器能够在多个站点中或一个站点的多个位置中实现。本发明中的过程能够用于计算用于控制器安排的最佳位置。

例如GSM、3G、LTE等多个技术共存时，它们可共享相同的分组传输网络。在此示例中，控制器的公共集能够用于一起为所有网络控制分组交换功能。本发明能够用于确定控制器的位置以便控制多个技术网络。

在云计算中，特别是在数据中心网络中，为降低连网基础设施的成本，优选使用带有智能控制器和低成本交换器集的拆分式体系结构。在数据中心网络环境中，能够应用控制器安排过程以部署控制器。

要理解的是，上述描述旨在是说明性而不是限制性的。在阅读和理解上述描述后，本领域的技术人员将明白许多其它实施例。因此，本发明的范围应参照所附权利要求以及此类权利要求被授权的等同的完全范围来确定。