利用事务使分布式网络控制系统中的波动降至最小

摘要

特定控制器接收来自第一控制器的第一组输入，和来自第二控制器的第二组输入。所述特定控制器随后开始利用第一组输入，计算一组输出。在第一控制器失效之后，所述特定控制器接收来自第二控制器的第三组输入。所述第三组输入和第一组或第二组输入构成一群输入，以便与另一群输入一起地以及分开地被处理。所述特定控制器随后接收来自第二控制器的指示符，所述指示符指示所述一组输入中的所有输入都已到达所述特定控制器。在收到所述指示符之后，并且在完全计算所述一组输出之后，所述特定控制器把所述一组输出发送给第四控制器，或者发送给托管转发元件。

说明书

背景技术

许多现代企业具有支持各种连接、应用和系统的包含交换机、集线 器、路由器、服务器、工作站和其它连网设备的大型复杂网络。计算机 联网的增大的复杂性，包括虚拟机迁移、动态工作负载、多租户、和特 定于客户的服务质量和安全配置，需要能够处理这种复杂性的网络控制 系统。提供了分布式网络控制系统，以便分布地处理这些大型的复杂网 络。然而，常见的情况是由分布式网络控制系统中的一个组件产生的网 络状态的变化来回地波及系统的其余部分，从而在分布式网络控制系统 中引起波动。

发明内容

本发明的一些实施例提供一种特定的网络控制器，所述网络控制器 接收来自由几个网络控制器形成的分层结构的上层中的第一控制器和第 二控制器的输入。所述特定控制器处理来自第一和第二控制器的输入， 以按照这样的方式产生输出，以致所述输出不会与通过处理仅仅来自第 一控制器的输入而会产生的输出不同。

特别地，一些实施例的所述特定控制器接收来自第一控制器的第一 组输入，和来自第二控制器的第二组输入。所述特定控制器随后开始利 用第一组输入，计算一组输出。在第一控制器失效之后，所述特定控制 器接收来自第二控制器的第三组输入。所述第三组输入和第一组或第二 组输入构成一群输入，以便与另一群输入一起地以及分开地被处理。

所述特定控制器随后接收来自第二控制器的指示符，所述指示符指 示所述一群输入中的所有输入都已到达所述特定控制器。在收到所述指 示符之后，并且在完全计算所述一组输出之后，所述特定控制器把所述 一组输出发送给第四控制器，或者发送给托管转发元件(managed  forwarding element)。第四控制器随后处理来自所述特定控制器的该组输 出，并把处理后的输出发送给托管转发元件。

本发明的一些实施例还在所述分层结构的中间层中，设置接收分别 来自分层结构中的上面一层中的几个不同控制器的输入的网络控制器。 来自上层控制器的输入以几个不同事务的形式到来。在一些实施例中， 下层控制器根据从不同的控制器接收的输入，产生输出，并把产生的输 出以单一事务的形式，发送给在分层结构中的下面一层中的一组控制器。

具体地，中间层网络控制器接收来自一组上层网络控制器的几群输 入。与另一群输入一起地和分开地处理每群输入。当各群输入满足某些 条件时，中间层网络控制器一起地处理各群输入中的两群或更多群输入， 以产生一组输出。当各群输入不满足某些条件时，网络控制器通过每次 一起处理一群输入地处理各群输入，从而生成一组输出。网络控制器随 后把生成的一组输出发送给下面一层中的一组控制器。

上面的发明内容用来简要介绍本发明的一些实施例。并不意图介绍 或概述在本文中公开的所有发明主题。下面的具体实施方式和在具体实 施方式中参照的附图将进一步说明在发明内容中说明的各个实施例，以 及其它实施例。因而，为了理解本文描述的所有实施例，需要完整地回 顾发明内容、具体实施方式和附图。此外，要求保护的主题不受发明内 容、具体实施方式和附图中的例证细节限定制，而是由附加的权利要求 限定，因为要求保护的主题可用其它具体形式体现，而不脱离所述主题 的范围。

附图说明

附加权利要求中记载了本发明的新颖特征。然而，为了便于说明， 在以下附图中例示了本发明的几个实施例。

图1描述网络控制器的例证分层结构。

图2图解说明一些实施例的网络控制器的体系结构。

图3概念地图解说明从逻辑控制器接收输入的物理控制器。

图4概念地图解说明一些实施例进行的处理在网络控制器的分层结 构中的上面一层中的源控制器的失效备援的过程。

图5概念地图解说明从逻辑控制器接收输入的物理控制器。

图6概念地图解说明从几个逻辑控制器接收输入变化的物理控制器。

图7概念地图解说明一些实施例进行的根据构成几个事务的输入变 化，产生一组事务输出变化的过程。

图8图解说明其中网络控制器把来自用户的请求分发给托管转发元 件，并把对所述请求的响应返回给用户的网络控制系统。

图9图解说明一些实施例的聚合从一组物理控制器接收的通用响应 的逻辑控制器。

图10概念地图解说明一些实施例进行的聚合来自在控制器的分层结 构中的下面一层中的下层控制器的一组响应，从而生成单一响应，以向 上传送给在分层结构中的上面一层中的上层控制器的过程。

图11概述地图解说明实现本发明的一些实施例的电子系统。

具体实施方式

在本发明的以下详细说明中，记载和说明了本发明的众多细节、例 子和实施例。然而，对本领域的技术人员来说，本发明显然并不局限于 记载的实施例，在没有所讨论的一些具体细节和例子的情况下，也可以 实践本发明。

一些实施例提供其中网络控制器计算转发状态信息，以推送给一组 托管转发元件，以便定义所述一组托管转发元件的转发行为的网络控制 系统。在一些实施例中，网络控制器构成具有几层控制器的分层结构。 一组逻辑控制器位于分层结构的顶层中，根据输入的逻辑控制平面数据， 产生通用物理控制平面数据。在所述一组逻辑控制器下面的一层是一组 物理控制器，在一些实施例中，所述一组物理控制器把通用控制平面数 据定制成特定于托管转发元件的物理控制平面数据。

在一些实施例中，物理控制器把通用物理控制平面数据中继给为托 管转发元件实际进行所述定制的一组机架控制器。在这些实施例中，机 架控制器在由控制器形成的分层结构的底层。物理控制器或机架控制器 与托管转发元件面接，把定制的物理控制平面数据馈送给托管转发元件。 托管转发元件利用从控制器接收的数据，在网络中转发数据。

在分层结构中的上层中的特定控制器把控制器的输出数据馈送给在 分层结构中的下面一层中的另一个控制器。在一些实施例中，所述特定 控制器具有在同层中的备用控制器，所述备用控制器起所述特定控制器 的热备份或冗余控制器的作用(例如，通过把相同的输出数据馈送给在分 层结构中的下面一层中的控制器)。在一些实施例中，下层中的控制器根 据从所述特定控制器接收的输出数据，产生它自己的输出。

当所述特定控制器失效时，下层中的控制器以通过处理来自备用控 制器的相同输出数据，从而输出数据不受影响的方式，根据(1)迄今从所 述特定控制器收到的输出数据，和(2)来自备用控制器的输出数据，产生 它自己的输出数据。即，在特定控制器失效之后，下层中的控制器接收 并处理来自备用控制器的输出数据，所述来自备用控制器的输出数据包 括与在所述失效之前，从所述特定控制器接收的数据相同的数据。然而， 下层中的控制器以下层中的控制器的输出数据不同于通过仅仅处理来自 所述特定控制器的输出数据而会产生的输出数据的方式，处理来自备用 控制器的输出数据。

在分层结构的下层中的控制器接收分别来自上面一层中的几个不同 控制器中每个的输出数据。来自上层控制器的输出数据以几个不同事务 的形式到来。在一些实施例中，下层控制器根据从不同的控制器接收的 输出数据，产生它自己的输出数据，并把它自己的输出数据作为单一事 务，发送给在所述下层下面的一层中的一组控制器。

在以下各节中，说明了各详细的实施例。具体地，节I首先说明用 于控制逻辑网络和物理网络的一些实施例的网络控制系统。之后，节II 说明使更新率降至最小。节III随后说明实现本发明的一些实施例的电子 系统。

I.网络控制系统

图1图解说明其中网络控制器计算转发状态信息，以推送给一组托 管转发元件，以便定义所述一组托管转发元件的转发行为的网络控制系 统100。网络控制系统100包括逻辑控制器110，2个物理控制器115和 120，和3个托管转发元件125-135。网络控制系统100表示具有向下向3 个托管转发元件推送状态的2个物理控制器115和120的简化例子。在 许多情况下，一些实施例的网络控制系统会包括众多的控制器，和成百 上千个托管转发元件。

在一些实施例中，网络控制器110-120进行转发状态的计算，并以流 表项的形式，把所述状态向下推送给托管转发元件。一些实施例的网络 控制器接收定义逻辑网络的逻辑控制平面(LCP)数据，并把该LCP数据 转换成物理控制平面(PCP)数据，以发送给托管转发元件125-135。在一 些实施例中，逻辑网络的逻辑控制平面定义连接逻辑地址空间中的终端 机器(例如，虚拟机)的一个或多个逻辑转发元件(例如，逻辑交换机、逻 辑路由器)。逻辑转发元件定义来自源机器的分组在逻辑空间中，应被如 何转发给目的地机器(例如，相对于逻辑端口的虚拟机MAC地址的绑定)。 另外，在一些实施例中，LCP定义由逻辑转发元件实现的逻辑策略(例如， 访问控制列表)。LCP及其结构对通过其实现的物理网络来说是不可知 的。

一些实施例的网络控制器进行LCP数据的几种不同变换，以获得被 向下推送到托管转发元件的PCP数据。在一些实施例中，控制器把LCP 数据转换成逻辑转发平面(LFP)数据，随后把LFP数据转换成PCO数据。 LFP数据定义在逻辑空间中，转发分组的转发表项。即，除简单地把地 址绑定到逻辑端口以外，LFP数据还包括规定如果地址匹配，那么把分 组转发给逻辑端口的表项。

LFP数据到PCP数据的变换把逻辑转发表项结合到物理网络中。 PCP表项包含在物理网络内的逻辑地址空间中进行转发的信息(例如，把 逻辑端口映射到物理端口等)。

在一些实施例中，推送到托管转发元件的PCP的计算分布在由控制 器构成的分层结构中的不同层的控制器之间。例如，在一些实施例中， 逻辑控制器110管理至少一个逻辑转发元件。逻辑控制器110进行 LCP-LFP变换和随后的LFP-通用PCP(UPCP)变换，如该图的右半部分 所示。UPCP数据包括未被定制成包括特定于任何托管转发元件的数据， 而是只包括特定于特定物理实现的这种数据的抽象(例如，端口号、隧道 标识符等)的流表项。

在一些实施例中，管理特定逻辑转发元件的逻辑控制器把UPCP数 据发送给任意数目的物理控制器。例如，逻辑控制器110把UPCP数据 发送给所述2个物理控制器115和120。每个托管转发元件由主物理控制 器管理。从而，用于跨几个托管转发元件实现的逻辑转发元件的UPCP 数据可被发送给管理这些转发元件的几个不同的主物理控制器。如图所 示，物理控制器115是管理2个托管转发元件125和130的主控制器。 物理控制器120是管理托管转发元件135的主控制器。

在物理控制器或者与托管转发元件在相同物理机中的机架控制器(本 图中未示出)，UPCP数据被转换成定制的PCP(CPCP)数据。CPCP数据 是填充有为特定的托管转发元件特有的定制数据的物理控制平面数据。 如上所述，在一些实施例中，物理控制器利用从托管转发元件接收的信 息，进行这种变换。在其它实施例中，物理控制器起通道(pass-through) 作用，以把UPCP数据发送给托管转发元件所驻留于的主机，在所述主 机，控制器逻辑(机架控制器)进行UPCP-CPCP变换。

托管转发元件125-135是由网络控制器管理(例如，接收来自网络控 制器的转发状态信息)的软件或硬件转发元件。在一些实施例中，托管转 发元件是在主机上(例如，在主机的用户空间和/或内核内)工作的软件转 发元件。这些托管转发元件接收来自终端机器140-160的分组，对分组进 行逻辑处理，和跨过物理网络把分组发送给其目的地(例如，在也连接到 不同的托管转发元件的另一个终端机器)。

终端机器140-160可以是物理机或虚拟机。在一些实施例中，作为虚 拟机的终端机器在具有为所述终端机器转发分组的托管转发元件的相同 主机中工作。由于属于多个物理网络的虚拟机可能位于单个主机中(例如， 终端机器140和145可以位于托管转发元件125所位于的相同主机内)， 因此每个托管转发元件可以实现多个不同的逻辑转发元件。另外，如上 所述，通常跨众多的托管转发元件，实现单个逻辑转发元件。

除了位于网络边缘的托管转发元件以外，在具有虚拟机的主机上， 一些实施例另外包括第二级的非边缘托管转发元件(在一些情况下，称为 池节点或服务节点)。当边缘托管转发元件不能进行关于分组的所有处理 时(例如，由于它不具有把目的地MAC地址绑定到逻辑端口的流表项)， 边缘托管转发元件把分组发送给池节点，以便使池节点可以处理该分组， 并把分组发送给其目的地。

图2概念地图解说明一些实施例的网络控制器200的例证体系结构。 取决于网络控制器200处理的数据的种类，网络控制器200能够起逻辑 控制器、物理控制器或机架控制器的作用。

作为逻辑控制器，网络控制器200把LCP数据作为输入。在一些实 施例中，网络控制器200把LCP数据转换成LFP数据，随后转换成UPCP 数据。网络控制器200把UPCP数据推送给一组物理控制器，所述一组 物理控制器是实现作为逻辑控制器的网络控制器200所管理的逻辑转发 元件的托管转发元件的控制者(master)。

作为一些实施例的物理控制器，网络控制器200把UPCP数据作为 输入，把UPCP数据转换成CPCP数据。网络控制器随后把CPCP数据 推送给网络控制器200为其控制者的一组托管转发元件。在其它实施例 中，作为物理控制器的网络控制器200把UPCP中继给一组机架控制器， 所述一组机架控制器在一组托管转发元件在其中工作的主机中工作。在 这些实施例中，网络控制器200是该组托管转发元件的控制者。

作为机架控制器，网络控制器200把来自一组物理控制器的UPCP 数据作为输入。网络控制器200为机架控制器管理的托管转发元件，把 UPCP数据转换成CPCP数据，随后把CPCP数据发送给所述托管转发 元件。

如图2中所示，网络控制器200包括一组规则引擎输入表210，一组 函数和常数表215，导入器220，规则引擎225，一组规则引擎输出表245， 转换器250，导出器255，持久性事务数据库(PTD)260，和编译器235。 编译器235是控制器的与控制器的其它组件在不同的时刻工作的组件。 当开发人员需要为特定的网络控制器和/或虚拟化环境指定规则引擎时， 编译器工作，而当控制器面接(interface)其它控制器或托管转发元件时， 控制器的其余模块在运行时工作。

在一些实施例中，编译器235获得用声明性语言指定的较小一组(例 如，几百行)声明性指令240，并把这些指令转换成规定规则引擎225的 操作的较大一组(例如，数千行)代码(即，目标代码)，规则引擎225进行 控制器的表映射。因而，编译器大大简化网络控制器开发人员的定义和 更新网络控制器的过程。这是因为编译器允许开发人员利用允许简明地 定义网络控制器的复杂映射操作的高级编程语言，随后响应于任意数目 的变化(即，由网络控制器支持的逻辑连网功能的变化，对网络控制器的 期望行为的变化等等)，更新该映射操作。此外，当开发人员定义映射操 作时，编译器可以使开发人员免于考虑事件到达网络控制器的顺序。另 外，开发人员用不同的规则集编程网络控制器200，以使网络控制器200 起逻辑控制器、物理控制器或机架控制器的作用。

在一些实施例中，规则引擎(RE)输入表210包括根据网络控制器200 用作的网络控制器的类型，而具有不同种类的数据的表格。输入表210 包括需要映射到LFP数据的LCP数据，并且当网络控制器200起逻辑 控制器作用时，包括需要映射到UPCP数据的LFP数据。当网络控制器 200起物理控制器或机架控制器作用时，输入表210包括需要被映射到 CPCP数据的UPCP数据。

除了RE输入表210以外，网络控制器200还包括规则引擎225用 于为其表映射操作收集输入的其它各种表215。这些表215包括保存规则 引擎225为进行其表映射操作而需要的常数的规定值的常数表。例如， 常数表215可包括被定义为值0的常数“0”，被定义为值4000的常数 “dispatch_port_no”，和被定义为值0xFF:FF:FF:FF:FF:FF的常数 “broadcast_MAC_addr”。

当规则引擎225引用常数时，实际上取回并使用关于所述常数定义 的对应值。另外，可以修改和/或更新常数表215中关于各个常数定义的 值。这样，常数表215提供修改关于规则引擎225引用的常数定义的值， 而不需要重写或重新编译指定规则引擎225的操作的代码的能力。表215 还包括函数表，函数表保存规则引擎225为了计算用于填充输出表245 的值而需要使用的函数。

规则引擎225进行表映射操作，表映射操作指定把输入数据转换成 输出数据的一种方式。每当规则引擎(RE)输入表之一被修改时，规则引 擎进行一组表映射操作，所述一组表映射操作可导致一个或多个RE输 出表中的一个或多个数据元组的更改。在一些实施例中，网络控制系统 利用称为nLog的datalog数据库语言的变形来创建规则引擎225。类似 于datalog，nLog提供允许开发人员指定当发生不同事件时，要进行的 不同操作的少许声明规则和算符。在一些实施例中，nLog提供由datalog 提供的算符的有限子集，以便提高nLog的运算速度。例如，在一些实施 例中，在任意声明规则中，nLog只允许使用AND算符。

如图2中所示，规则引擎225包括事件处理器222、几个查询计划 227，和表处理器230。每个查询计划是规定当发生对RE输入表之一的 更改时，要进行的一组连接操作的一组规则。下面把这样的更改称为输 入表事件。每个查询计划由编译器235根据一组声明240中的一个声明 规则产生。在一些实施例中，根据一个声明规则，产生不止一个查询计 划。例如，为由一个声明规则连接的各个表创建查询计划。即，当声明 规则指定连接4个表时，根据所述一个声明，将创建4个不同的查询计 划。在一些实施例中，通过利用nLog声明式语言，定义查询计划。

规则引擎225的事件处理器222检测每个输入表事件的发生。不同 实施例的事件处理器不同地检测输入表事件的发生。在一些实施例中， 事件处理器向RE输入表登记回叫，以便通知对RE输入表的记录的改变。 在这样的实施例中，当从RE输入表收到其记录之一已改变的通知时， 事件处理器222检测输入表事件。

响应于检测的输入表事件，事件处理器222(1)为检测的表事件，选 择适当的查询计划，和(2)指令表处理器230执行该查询计划。在一些实 施例中，为了执行查询计划，表处理器230进行由查询计划指定的连接 操作，以根据一个或多个输入以及各种表210和215，产生表示一组或多 组数据值的一个或多个记录。一些实施例的表处理器230随后(1)进行选 择操作，以从利用连接操作产生的记录中选择数据值的子集，和(2)把选 择的数据值的子集写入一个或多个RE输出表245中。

在一些实施例中，RE输出表245保存逻辑和物理网络元件数据属性。 表245被称为RE输出表，因为它们保存规则引擎225的表映射操作的 输出。在一些实施例中，RE输出表可被分为几种不同的类别。例如，在 一些实施例中，这些表可以是RE输入表和/或控制器输出表。当表中的 变化致使规则引擎检测到要求查询计划的执行的输入事件时，表是RE 输入表。RE输出表245也可是产生使规则引擎进行另一个查询计划的事 件的RE输入表210。这种事件被称为内部输入事件，与外部输入事件形 成对照，外部输入事件是由导入器220产生的RE输入表更改引起的事 件。

当表中的变化致使导出器255把变化导出到另外的控制器或者托管 转发元件时，表是控制器输出表。RE输出表245中的表可以是RE输入 表、控制器输出表，或者RE输入表和控制器输出表这两者。在一些实 施例中，RE输入表和RE输出表是关系数据库管理系统(RDBMS)的表。 这些表被保存为关系数据库数据结构，所述关系数据库数据结构是网络 控制器的主要数据存储结构。

导出器255检测RE输出表245的控制器输出表的变化。不同实施 例的导出器不同地检测控制器输出表事件的发生。在一些实施例中，导 出器向控制器输出表登记回叫，以便通知控制器输出表的记录的变化。 在这样的实施例中，当它从控制器输出表收到其记录之一已变化的通知 时，导出器255检测输出表事件。

响应于检测的输出表事件，导出器255获得更改的控制器输出表中 的一些或者全部的更改数据元组，并把更改的数据元组传送给其它控制 器或托管转发元件。具体地，当网络控制器200起逻辑控制器作用时， 导出器255通过与物理控制器建立的一组通信通道(例如，远程过程调用 (RPC)通道)，把UPCP数据传送给一组物理控制器。当网络控制器200 起物理控制器作用时，一些实施例的导出器255通过与机架控制器建立 的一组通信通道，把UPCP数据传送给一组机架控制器。其它实施例的 导出器255通过与各个托管转发元件建立的一对通信通道(例如， OpenFlow通道和配置通道)，把CPCP数据传送给一组托管转发元件。 当网络控制器200起机架控制器作用时，一些实施例的导出器255通过 与各个托管转发元件建立的一对通信通道(例如，OpenFlow通道和配置 通道)，把CPCP数据传送给一组托管转发元件。

在一些实施例中，网络控制器不在输出表245中保持该网络控制器 不负责管理的数据。然而，这样的数据将由转换器250转换成可被保存 在PTD中的格式，并被保存在PTD260中。PTD是网络控制器的次要 存储结构。网络控制器200的PTD把该数据传送给一个或多个其它的网 络控制器，以致负责管理该数据的其它网络控制器中的一些网络控制器 能够处理该数据。

在一些实施例中，考虑到数据的弹性，网络控制器还把保存在输出 表245中的数据(即，网络控制器负责管理的数据)带到PTD。这样的数 据也由转换器250转换，保存在PTD中，并被传送给其它控制器实例的 其它PTD。于是，在这些实施例中，控制器实例的PTD具有由网络控制 系统管理的所有数据的所有配置数据。即，在一些实施例中，每个PTD 包含逻辑和物理网络的结构的全局视图。

导入器220面接输入数据的许多不同来源，并利用输入数据更改或 创建输入表210。当网络控制器200起逻辑控制器作用时，一些实施例的 导入器220通过输入转换控制器(未示出)，接收来自用户(租户)的输入数 据，所述输入转换控制器把用户输入(例如，呈应用编程接口(API)调用的 形式)转换成LCP数据。在一些实施例中，导入器220通过通信通道，接 收LCP数据。导入器220还与PTD 260面接，以致通过PTD从其它控 制器实例接收的数据可被用作更改或创建输入表210的输入数据。此外， 导入器220还检测RE输入表和RE输出表245的控制器输出表中的变化。 产生并保存在输出表245中的LFP数据由用于规则引擎225的导入器 220，反馈给规则引擎225，以便产生UPCP数据。

当网络控制器200起物理控制器作用时，导入器220通过与一组逻 辑控制器建立的一组通信通道，从所述一组逻辑控制器获得UPCP数据。 当网络控制器200起机架控制器作用时，导入器通过与一组物理控制器 建立的一组通信通道，从所述一组物理控制器获得UPCP数据。

至此在图中，说明了输入表210包括来自控制器分层结构的上层中 的控制器的输入，输出表245包括给控制器分层结构的下层中的控制器 或者给一组托管转发元件的输出。在一些情况下，输入和输出沿相反的 方向来回。即，在这些情况下，网络控制器从下层中的控制器，或者从 托管转发元件获得输入，并把输出发送给上层中的控制器。例如，网络 控制器200可能收到起源于用户的请求，并把该请求分发给下层中的一 组控制器，或者分发给一组托管转发元件。这些分发的请求到达托管转 发元件，托管转发元件准备响应。所述响应通过导入器，以输入的形式 回到网络控制器200。规则引擎255进行表映射操作，以把响应组合成一 个响应，从而向上发送给向网络控制器200发送了请求的控制器。处理 请求和响应的更多细节将在下面参考图9和10进一步说明。

在说明了其中网络控制器形成分层结构的网络控制系统之后，下面 的节II说明通过组合事务，使网络控制系统中的波动(churn)降至最小。

II.使更新率降至最小

A.重排外部输入

在网络控制系统中，网络控制器管理网络状态，以便在物理网络之 上实现逻辑网络。网络状态不是常数，当所述状态变化时，所述状态的 更新必须被分发给整个网络内的托管转发元件。至少由于3个原因，会 出现网络状态的这些更新。首先，当逻辑策略因为由逻辑管线强制实施 的网络策略被重新配置(例如，逻辑网络的管理员进行的访问控制列表的 更新)而变化时，网络状态变化。其次，工作负载操作变化导致网络状态 的变化。例如，当虚拟机从第一节点迁移到第二节点时，逻辑视图保持 不变。然而，归因于所述迁移，网络状态需要更新，因为VM附接到的 逻辑端口现在位于不同的物理位置。第三，物理重构事件，比如设备增 加、去除、升级和重新配置，会导致网络状态的变化。

尽管策略配置的典型的用户驱动变化引起微小的递增量，并且转发 状态的这种递增变化可被有效地计算，不过失效备援(failover)状况会 引起nLog计算引擎的较大输入变化。考虑在源控制器崩溃并且新的控制 器接管源控制器的任务之后的接收控制器，所述接收控制器被配置成从 源控制器接收输入。尽管新的控制器是备用控制器，于是具有预先计算 的状态，不过接收控制器仍然必须进行从旧的源控制器到新的源控制器 的失效备援。

在一些实施例中，接收控制器简单地清除从崩溃的控制器接收的所 有输入(复原输入的效果)，随后把来自新控制器的新输入馈送给nLog计 算引擎，即使可以预测新旧输入很可能几乎相同(即使不是完全相同)。尽 管在新的源控制器启动并且计算达到其定点(例如，对给定的输入数据进 行计算的点)之前，计算的事务性会使转发状态的任何变化不致被暴露， 不过计算开销会极大：整个转发状态会被计算两次，首先要除去所述状 态，随后要重新确立所述状态。

在一些实施例中，接收控制器识别来自新旧源控制器的输入的差异， 并且仅仅关于变化的输入，计算转发状态变化。这会完全消除所述开销。 然而，借助事务计算和借助达到定点的能力，一些实施例的接收控制器 可在不识别所述差异的情况下，获得相同的结果。为了在不识别所述差 异的情况下实现从一个输入源到另一个输入源的渐进、有效的迁移，网 络控制系统就是不通过清除来自旧的源控制器的输入而启动，而是改为 在仍然利用来自旧的源控制器的输入的时候，把来自新的源控制器的输 入馈送给计算引擎。网络控制系统随后等待新的源控制器对于来自新的 源控制器的输入达到定点，只有在这之后，才删除来自旧的源控制器的 输入。

通过按照这种方式重排外部输入/事件，一些实施例的nLog计算引 擎能够检测重叠，从而避免完全清除旧状态的开销。在不需要清除来自 旧的源控制器的状态的情况下，接收控制器不提交事务，直到新的源控 制器达到定点为止。一旦新的源控制器达到定点，接收控制器就把由变 化的输入引起的转发状态(即，输出状态)的任何变化推送给使用的 (consuming)转发元件。如果变化相当大，那么这种方法的代价是瞬时内 存使用增大。在一些实施例中，当源控制器达到定点时，源控制器发送 分界线(barrier)。当在接收控制器收到所述分界线时，接收控制器认识到 源控制器已达到定点。

图3概念地图解说明从逻辑控制器310接收输入的物理控制器305。 特别地，图3按4个不同阶段301-304，图解说明当逻辑控制器310失效， 从而逻辑控制器335接管计算更新并把更新发送给物理控制器305的任 务时，物理控制器305的输入处理。逻辑控制器335是逻辑控制器310 的热备份逻辑控制器。

物理控制器305类似于上面参考图2说明的网络控制器200，因为物 理控制器305包括与控制器200的对应组件类似的导入器315、规则引擎 320、输入表325和输出表330。为了讨论的简明起见，图3中未表示物 理控制器305的所有组件。

在第一阶段301，逻辑控制器310正把描述成白色的平行四边形的输 入变化1和2发送给物理控制器305。输入变化是控制器的输入表的一个 或多个记录的变化。在一些实施例中，输入变化采取数据元组的形式。 逻辑控制器335也向物理控制器305发送相同的变化1和2。来自备用逻 辑控制器335的变化1和2被描述成灰色的平行四边形，以直观地把它 们与来自逻辑控制器310的变化1和2区分开。

在第二阶段302，物理控制器305已收到来自逻辑控制器310的变化 1和2，以及来自逻辑控制器335的变化1和2。然而，导入器315已仅 仅用来自逻辑控制器310的变化1和2更新了输入表325，并把来自备份 逻辑控制器335的变化1和2保存在存储结构(未示出)中。

在一些实施例中，物理控制器305不认为逻辑控制器335是逻辑控 制器310的备用控制器。即，从物理控制器305的观点看，逻辑控制器 310和335是馈送相同的输入变化的两个控制器。物理控制器305本地决 定利用来自控制器之一的变化，并且如果已使用的变化来自于的控制器 失效，那么切换到另一个控制器。在阶段302，物理控制器305利用来自 逻辑控制器310的变化。

阶段302还表示逻辑控制器310已失效，并且在逻辑控制器310失 效之后，逻辑控制器335在发送变化3和4。变化4被描述成具有粗体边 线，以指示变化4是来自逻辑控制器335的事务的最后变化。换句话说， 变化3和4构成事务，并且变化4(或者变化4之后的单独数据)具有指示 一个事务的一组输入的结束的分界线。由于例如规则引擎320还未完成 其它变化(未示出)的处理，因此规则引擎320还未处理变化1和2。

第三阶段303表示规则引擎320已进行表映射操作，从而根据变化1 和2产生一组输出变化。输出变化是作为对被输入变化改变的输入表进 行表映射操作的结果，对控制器的输出表的一个或多个记录产生的变化。 在一些实施例中，输出变化采取数据元组的形式。输出变化被描述成包 括变化1和2的虚线框，以指示这些输出变化是处理来自逻辑控制器310 的变化1和2的结果。另外在第三阶段303，导入器315已用保持在存储 结构中的来自逻辑控制器335的变化1和2更新了输入表325。导入器 315还除去来自逻辑控制器310的变化1和2，因为逻辑控制器310已失 效，逻辑控制器335已切换到逻辑控制器335，以便从逻辑控制器335 接收变化。此外，物理控制器305已收到来自逻辑控制器335的变化3 和4。导入器315用变化3和4，更新输入表325。

第四阶段304表示规则引擎320进行了表映射操作，从而根据通过 备用逻辑控制器335接收的变化1-4，生成输出变化。描述成包含变化1-4 的虚线框的输出变化指示输出变化与如果导入器未两次用变化1和2(一 次用来自逻辑控制器310的变化1和2，另一次用来自逻辑控制器335 的变化1和2)更新输入表而会产生的输出变化相同。这是因为一些实施 例的规则引擎不通过对重复的输入变化进行表映射操作，产生重复的输 出变化。

由于物理控制器处理了来自上层控制器的构成事务的所有输入变 化，因此物理控制器335已达到它自己的定点。物理控制器335随后把 该组输出变化发送给一组托管转发元件，或者一组机架控制器。图3图 解说明物理控制器进行的逻辑控制器失效备援的处理。然而，本领域的 普通技术人员会认识到，机架控制器可类似地处理物理控制器失效备援。

图4概念地图解说明一些实施例进行的处理在网络控制器的分层结 构中的上面一层中的源控制器的失效备援的过程400。过程400由从产生 输入变化的两个或更多的源控制器接收输入变化的接收控制器进行。在 一些实施例中，接收控制器是从产生输入变化(包括UPCP数据)的一 组逻辑控制器接收输入变化的物理控制器。另外，接收控制器可以是从 中继UPCP数据的一组物理控制器接收输入变化的机架控制器。一些实 施例的接收控制器类似于上面参考图3说明的物理控制器305。

通过(在405)从主源控制器和备用源控制器接收输入变化，开始过程 400。备用控制器是向接收控制器发送与主控制器发送的输入变化相同的 输入变化的备份或冗余控制器。在一些实施例中，接收控制器不识别这 两个源控制器中的哪一个是主控制器。接收控制器选择它们之一，并利 用来自所选源控制器的输入变化来产生接收控制器自己的输出变化。为 了便于讨论，主源控制器是接收控制器最初选择的控制器。

之后，过程400(在410)仅仅利用来自主控制器的输入，计算输出变 化。一些实施例的过程400把来自备用控制器的冗余输入变化放在一边 地保存在存储结构中，直到从主源控制器完整地收到事务(例如，分界线 之间的一组输入变化)为止。一些实施例的过程400不利用放在一边地保 存在存储结构中的输入变化。一些实施例的过程400不从输入表中除去 从主控制器接收的输入变化。

过程400(在415)判定主源控制器是否已失效。在一些实施例中，源 控制器定期地传送其状态或心跳，接收控制器利用所述状态判定源控制 器是否有效。在一些实施例中，接收控制器轮询源控制器，以判定源控 制器是否有效。当过程400(在415)判定主源控制器失效时，过程400进 入将在下面进一步说明的430。

当过程400(在415)判定主源控制器未失效时，过程400(在420)判定 过程是否从主控制器收到分界线。即，过程判定该过程收到的输入变化 是否构成完整的事务。当过程400(在420)判定该过程还未从主源控制器 收到完整的事务时，过程400返回405，以继续从主源控制器和备用源控 制器接收输入变化。

当过程400(在420)判定过程已从主源控制器收到分界线时，过程 400(在425)判定过程400是否达到它自己的定点。一些实施例的过程400 在过程400完成来自主源控制器的事务的所有接收的输入变化的处理， 从而产生输出变化时，确定它已达到它自己的定点。过程400随后进入 将在下面进一步说明的450。

当过程400(在415)判定主源控制器已失效时，过程切换到备用源控 制器，以(在430)接收来自备用控制器的输入变化。过程400随后(在435) 根据从备用控制器接收的输入，计算输出变化。在一些实施例中，过程 400还利用(在410)放在一边的变化来计算输出变化。放在一边的变化是 已用于产生输出变化的来自主源控制器的输入变化的副本变化。然而， 过程400不清除通过处理从主源控制器接收的相同输入变化而产生的输 出变化。过程400仍然处理放在一边的重复的输入变化，但是进行过程 400的接收控制器的规则引擎不通过处理重复的输入变化而产生重复的 输出变化。当过程切换到备用源控制器时，一些实施例的过程400从输 入表中，除去从失效的控制器接收的变化。

之后，过程400(在440)判定过程是否从备用源控制器收到分界线。 即，该过程判定该过程收到的输入变化是否构成完整的事务。构成完整 事务的输入变化应包括被放在一边的重复输入变化，和在主控制器失效 之后，该过程从备用控制器接收的任何输入变化。

当过程400(在440)判定该过程未收到分界线时，过程400返回430， 以继续从备用源控制器接收输入变化。当过程400(在440)确定该过程收 到了分界线时，过程400(在425)判定过程400是否达到它自己的定点。

之后，过程400(在450)把计算的输出变化发送给在控制器的分层结 构中的下面一层中的一组控制器，或者发送给一组托管转发元件，所述 一组托管转发元件根据所述输出变化转发数据。一些实施例的过程400 在输出变化的结尾插入分界线，或者向输出变化的最后一个变化加入指 示完整事务的信息。过程随后结束。

B.分层转发状态计算中的事务

在一些实施例中，网络控制器形成具有两层或更多层的网络控制器 的分层结构，所述两层或更多层的网络控制器向转发元件馈送更新，所 述转发元件从多个控制器接收事务更新。在这些实施例中，最上面的控 制器以事务方式，计算它们的更新，不过在它们下面的控制器可从多个 最上面的控制器接收更新；类似地，转发元件可从多个第二层的控制器 接收更新。

事务可在它们的边界中无任何变化地向下流动；即，在第二层控制 器处理的顶层事务产生向下馈送给转发元件的事务，该事务只包含来自 最顶层控制器的输入事务的作为结果的变化。然而，即使事务在其向下 到转发元件的途中被聚合，策略的一致性也能够被维持。在一些实施例 中，第二层控制器把多个输入事务(可能来自不同的最顶层控制器)聚合成 单个事务，所述单个事务被向下馈送给转发元件。判定哪个层级是聚合(如 果有的话)的适当层级是一项本地决策。例如，系统可实现其中默认根本 不聚合事务，但是在队列中的事务的数目增大的过载状况下，怀着(来自 相同来源的)事务具有能够相互抵消的重叠变化的希望，聚合事务的方法。 在更宽广的网络环境中，可把这种方法看作一种路由翻动惩罚(route flap  dampening)。

图5概念地图解说明从逻辑控制器150接收输入的物理控制器505。 特别地，图5分4个不同的阶段501-504，图解说明物理控制器505聚合 来自向物理控制器505馈送输入变化的逻辑控制器510的构成几个完整 事务的输入变化。物理控制器505类似于上面参考图2说明的网络控制 器200，因为物理控制器505包括与控制器200的对应组件类似的导入器 515、规则引擎520、输入表525和输出表530。为了讨论的简明起见， 图5中未表示物理控制器505的所有组件。

在第一阶段501，逻辑控制器510正把输入变化1-3发送给物理控制 器505。变化3被描述成具有粗体边线，以指示变化1-3构成完整事务。 即，变化3包括分界线或者伴随有分界线。在阶段501，输入表525和输 出表530是空表，因为物理控制器505先前计算和发送了一组事务输出 变化。

在第二阶段502，物理控制器505已收到来自逻辑控制器510的变化 1-3。导入器515已用变化1-3更新输入表525。第二阶段502还表示逻 辑控制器正在发送构成事务的下一组输入变化4和5。

在第三阶段503，物理控制器505已从逻辑控制器530收到构成事务 的下一组输入变化4和5。导入器515用变化4和5更新输入表525。第 三阶段503还表示规则引擎520进行了表映射操作，以根据在前一阶段 502放入输入表525中的变化1-3，产生一组输出变化。输出变化被描述 成包括变化1-3的虚线框，以指示这些输出变化是处理变化1-3的结果。

另外在阶段503，物理控制器505判定是否(1)发送当前在输出表530 中的输出变化，因为控制器通过处理构成完整事务的一组输入变化，产 生了所述输出变化，或者(2)等待更多的输入变化到来。在一些实施例中， 物理控制器根据某些标准，作出所述判定。例如，如果自发送最后一组 输出变化以来，或者自收到最后的事务以来，未过去一段时间，那么物 理控制器等待更多的输入变化到来。在这些实施例中的一些实施例中， 当所述一段时间过去时，物理控制器505聚合构成完整事务的所有输入 变化，从而产生单组事务输出变化。

另一方面或者结合地，一些实施例的物理控制器505考虑输入表525 中具有的数据的数量。在这些实施例中的一些实施例中，当输入表525 具有大于阈值量的数据时，物理控制器505聚合构成完整事务的所有输 入变化，从而产生单组事务输出变化。代替或者结合考虑数据的数量， 一些实施例的物理控制器525考虑输入表525具有的完整事务的数目。 在一些这样的实施例中，当输入表525具有大于阈值数目的完整事务时， 物理控制器聚合构成完整事务的输入变化，从而产生单组事务输出变化。

在第四阶段504，物理控制器505已确定物理器505应利用更多的事 务来产生单组事务输出变化。从而，物理控制器505未发送根据变化1-3 计算的输出变化。规则引擎520对变化4和5进行了表映射操作，从而 产生输出变化。如图所示，根据变化4和5产生的输出变化随后和根据 变化1-3产生的输出变化被集中在一起。物理控制器535随后把该组输出 变化发送给一组托管转发元件或者一组机架控制器。

单组事务输出变化构成发送给另一个控制器或托管转发元件的事 务。事务包括将应用于进行接收的托管转发元件的转发状态的一组变化。 于是，通过在输入侧聚合几个事务，生成发送给输出侧的单一事务，一 些实施例的控制器组合各组变化，以致所有这些变化被一起应用于托管 转发元件。

图6概念地图解说明接收来自几个逻辑控制器635-645的输入变化的 物理控制器610。特别地，图6分5个阶段601-605，图解说明物理控制 器610把来自几个不同逻辑控制器的构成几个事务的输入变化聚合成单 组事务输出变化。物理控制器610类似于上面参考图2说明的网络控制 器200，因为物理控制器610包括与控制器200的对应组件类似的导入器 615、规则引擎620、输入表625和输出表630。为了讨论的简明起见， 图6中未表示物理控制器610的所有组件。

在第一阶段601，逻辑控制器635正向物理控制器610发送输入变化 1。逻辑控制器640正在发送构成完整事务的输入变化2-4。在阶段601， 输入表625和输出表630是空表，因为物理控制器610先前计算并发送 了一组事务输出变化。

在第二阶段602，物理控制器610已从逻辑控制器635和640收到变 化1-4。导入器615已用变化1-4更新输入表625。第二阶段602还表示 逻辑控制器正发送构成完整事务的变化5和6。

在第三阶段603，物理控制器610已从逻辑控制器645收到构成事务 的输入变化5和6。导入器615用变化5和6更新输入表625。输入表625 现在具有变化1-6。第三阶段603还表示规则引擎620进行了表映射操作， 以根据在前一阶段602，放入输入表625中的变化1-4，产生输出变化。 产生了两组输出变化。如图所示，第一组包括通过处理变化1而产生的 输出变化。第二组包括通过处理变化2-4而产生的输出变化。

另外在阶段603，物理控制器610判定是否(1)发送通过处理变化2-4 而产生的输出变化，因为物理控制器通过处理构成完整事务的所有输入 变化，产生了这些输出变化，或者(2)等待更多的输入变化到来。在一些 实施例中，物理控制器根据某些标准作出所述判定-即，自发送一组事务 输出变化或者接收完整事务以来，过去的一段时间，输入表625中的数 据的数量，和/或输入表625中的完整事务的数目，如上参考图5所述。

在第四阶段604，物理控制器610已确定物理器610应利用更多的事 务来产生单组事务输出变化。从而，物理控制器610未发出根据输入变 化2-4计算的输出变化。规则引擎620对变化5和6进行了表映射操作， 产生了对应的输出变化。然而，如图所示，根据输入变化5和6计算的 输出变化现在和根据输入变化2-4计算的输出变化被集中在一起。从而， 物理控制器610通过聚合处理构成两个事务的两组输入变化2-4和5-6而 获得的输出，产生了所述单组输出变化。

在第五阶段605，物理控制器610已把根据变化2-6计算的输出变化 发送给一组机架控制器或一组托管转发元件。物理控制器已从输出表630 中除去已被发送的输出变化。物理控制器还从输入表625中除去了输入 变化2-6。阶段605表示输入变化1和根据输入变化1计算的输出变化仍 然分别在输入表625和输出表630中。这是因为输入变化1不构成完整 事务-物理控制器未收到指示在物理控制器610，已收到包括变化1的完 整事务的分界线。

图7概念地图解说明一些实施例进行的根据构成几个事务的输入变 化，产生一组事务输出变化的过程700。过程700由从产生输入变化的两 个或更多的源控制器接收输入变化的接收控制器进行。在一些实施例中， 接收控制器是从产生输入变化(包括UPCP数据)的一组逻辑控制器接 收输入变化的物理控制器。另外，接收控制器可以是从中继UPCP数据 的一组物理控制器接收输入变化的机架控制器。接收控制器类似于图5 和6的物理控制器505和605。

通过(在705)接收来自源控制器的输入变化，开始过程700。在一些 实施例中，来自不同源控制器的输入变化与不同组的逻辑转发元件相关。 过程700随后利用该过程迄今收到的输入变化，(在710)计算输出变化。

之后，过程700(在715)判定过程700是否从源控制器收到至少一个 完整的事务。如上所述，完整事务包括在从一个源控制器收到分界线之 后，并在收到另一个分界线之前，从该源控制器接收的输入变化。当过 程700(在715)判定该过程未收到至少一个完整事务时，过程700返回705， 以从源控制器接收更多的输出变化。

当过程700(在715)确定过程收到至少一个完整的事务时，过程700 进入720，以判定特定聚合标准是否被满足。不同的实施例具有不同的聚 合标准。例如，在一些实施例中，所述特定标准包括自发送最后一组输 出变化以来，或者自接收最后的完整事务以来过去的一段时间。当已过 去所述一段时间时，所述特定标准被满足。另一方面或者结合地，在一 些实施例中，所述特定聚合标准包括(进行过程700的接收控制器的)输入 表中具有的数据的数量。在这些实施例中，当输入表具有大于阈值量的 数据时，所述特定标准被满足。在这些实施例中的一些实施例中，代替 或者结合数据的数量，所述特定标准可包括输入表具有的完整事务的数 目。在这些实施例中，当输入表具有大于阈值数的完整事务时，所述特 定标准被满足。

之后，过程700(在725)聚合根据构成所有完整事务的输入变化计算 的输出变化。在一些实施例中，过程700不考虑根据不构成完整事务的 输入变化计算的那些输出变化。换句话说，这些未被考虑的输出变化是 根据对于其未收到分界线的输入变化计算的。

过程700随后(在730)把聚合的输出变化发送给在控制器的分层结构 中的下面一层中的一组控制器，或者发送给一组托管转发元件，所述一 组托管转发元件根据输出变化转发数据。一些实施例的过程700在输出 变化的结尾插入分界线，或者向输出变化的最后一个变化加入指示完整 事务的信息。另外，过程从接收控制器的输出表中除去发送的输出变化， 并从接收控制器的输入表中，除去构成完整事务的根据其计算了发送的 输出变化的输入变化。过程随后结束。

C.例证的使用情况

1.API

呈应用编码接口(API)调用形式的定义逻辑转发元件的输入被发送 给支持API的输入转换控制器。一些实施例的网络控制系统原子级地实 施API更新。即，配置变化以原子方式，把系统从旧状态迁移到新状态。 具体地，在收到API调用之后，系统中的API接收代码更新nLog引擎 的状态，并在馈送所有更新之后，系统中的API接收代码等待定点(以使 计算收敛)，并通过提交关于nLog的变化，用信号通知待结束的事务。 之后，转发状态更新将被向下发送给聚类分层结构中下面的控制器，或 者发送给转发元件-都在单一事务更新中。所述更新将由接收元件以事务 的方式应用。

在一些实施例中，可跨越分布式存储系统(例如，控制器中的PTD) 地传送API更新，只要更新作为单一事务更新地到达接收器。即，只要 更新作为单一事务更新被写入存储器中，并且nLog处理控制器以单一事 务的形式，接收所述更新，就可如上所述，在推送状态更新的过程继续 的情况下，把更新作为单一事务更新写入nLog计算过程中。

2.控制器失效备援

设想管理一组逻辑转发元件的主逻辑控制器。在一些实施例中，该 控制器具有计算相同的状态，并按照和主控制器相同的方式向下推送所 述状态的热备份。主控制器和热备份控制器之间的一个差别在于在开始 失效备援之前，来自备份控制器的流被忽略。当主控制器失效时，通过 如下逐渐从旧状态迁移到新状态，接收控制器/转发元件可切换到备份控 制器。

代替除去/关闭来自旧的主控制器的状态更新流，并使计算朝着现在 存在来自上方控制器的活动的更新流的状态收敛，可以仅仅开启新的主 控制器，使计算收敛，并有效地合并旧的更新流和新的更新流。即，这 是建立在两个来源产生相同或几乎相同的流的前提之上的。在此之后， 控制器等待计算收敛，通过等待定点，并且只有在控制器达到定点之后， 控制器才完全除去旧的流。同样，通过等待定点，控制器使计算收敛到 仅仅利用新的来源。之后，通过提交事务，控制器能够完成从旧来源到 新来源的迁移。这用信号通知nLog运行时，以便以状态更新应被处理的 信号的形式，有效地传递来自下面的控制器/转发元件的分界线。

D.按需请求处理

在一些情况下，API请求处理可以利用nLog引擎来实现。在这种情 况下，通过把请求转换成一组元组，把请求馈送入nLog引擎中，所述一 组元组将触发同样表示成元组的API响应的nLog计算。当元组请求和 响应与请求和响应元组具有一对一映射时，等待响应是容易的：API请 求处理仅仅等待与请求匹配的响应到达。一旦与请求匹配的响应到达， 关于响应的计算就准备就绪。

然而，当请求/响应不具有一对一映射时，更难以知道请求处理何时 完成。在这种情况下，在馈送入请求之后，API请求处理可能需要计算 的定点；一旦达到定点，该请求就使所有的响应都被产生。一旦请求和 响应元组具有某个公共的标识符，就易于识别响应元组，而与响应元组 的数目无关。从而，这种使用情况不需要利用如上所述的提交，不过实 现基础是定点等待。

图8图解说明其中网络控制器把来自用户的请求分发给托管转发元 件，并把对所述请求的响应返回给用户的网络控制系统800。网络控制系 统800类似于图1的网络控制系统100，因为网络控制系统800中的控制 器也计算转发状态信息，从而推送给托管转发元件，以便定义托管转发 元件的转发行为。网络控制系统800包括输入转换控制器805、逻辑控制 器810、2个物理控制器815和820，和3个托管转发元件825-835。网络 控制系统800代表2个物理控制器815和820向3个托管转发元件分发 请求的简化例子。在许多情况下，一些实施例的网络控制系统会包括众 多的控制器，以及成百上千个托管转发元件。

一些实施例的输入转换控制器805从用户获得输入。这些输入包括 逻辑网络的规范，输入转换控制器把所述规范转换成LCP数据，逻辑控 制器随后将处理所述LCP数据。此外，输入还包括对逻辑网络的有关信 息的请求。例如，来自用户的请求可能询问统计信息(例如，某一段时间， 逻辑转发元件的逻辑端口的流量)。输入转换控制器805把请求转换成呈 数据元组形式的逻辑请求，逻辑控制器随后将处理所述数据元组。

在一些实施例中，输入转换控制器805接收呈API调用形式，来自 用户的输入。输入转换控制器805支持API，在API之上，可以建立网 络管理应用(例如，web应用或命令行接口(CLI)应用)。用户利用网络应 用获得给输入转换控制器的输入。

在一些实施例中，网络控制器810-820进行请求的变换，并以数据元 组的形式，把请求向下分发给托管转发元件。在把请求分发给托管转发 元件之前，一些实施例的网络控制器进行所述请求的几种不同变换。具 体地，逻辑控制器810接收来自输入转换控制器805的逻辑请求。在一 些实施例中，利用逻辑网络的逻辑属性指定逻辑请求。例证的逻辑请求 是对与特定逻辑转发元件的特定逻辑端口的有关信息的请求。该请求可 利用逻辑端口名称或地址和逻辑转发元件的名称或地址来编写。

逻辑控制器810把该逻辑请求转换成通用请求。在一些实施例中， 利用实现逻辑网络的托管转发元件的属性，指定通用请求。然而，这些 属性是用并不特定于特定物理实现的抽象术语(例如，端口号、隧道标识 符等)表述的。例如，可以利用任意托管转发元件的物理端口的名称，而 不是利用物理端口的实际端口号编写通用请求。

在一些实施例中，逻辑控制器810把该通用请求发送给任意数目的 物理控制器。例如，逻辑控制器810把通用请求发送给2个物理控制器 815和820。在一些实施例中，通用请求带有用于识别该请求的标识符。 该标识符将用于匹配所述请求和对应的响应。所述响应将在下面进一步 说明。

各个托管转发元件由主物理控制器管理。从而，对于跨几个托管转 发元件实现的逻辑转发元件的逻辑请求可被发送给管理这些转发元件的 几个不同的主物理控制器。如图所示，物理控制器815是管理2个托管 转发元件825和830的主控制器。物理控制器820是管理托管转发元件 835的主控制器。

在物理控制器或者与托管转发元件在相同物理机中的机架控制器(图 中未示出)，通用请求被转换成定制请求。在一些实施例中，利用托管转 发元件的为其特有的属性，指定定制请求。例如，对于托管转发元件的 定制请求可以用托管转发元件的物理端口的实际的本地使用的端口号编 写。在其中物理控制器是把UPCP数据发送给机架控制器的通道 (pass-through)的那些实施例中，物理控制器是把通用请求发送给机架控 制器的通道。

托管转发元件825-835类似于图1的托管转发元件125-135。终端机 器840-860类似于图1的终端机器140-160。托管转发元件825-835收集 定制请求所查询的信息。托管转发元件825-835都响应于收到定制请求， 而产生包括收集的信息的定制请求。

托管转发元件把定制响应向上传递给托管转发元件从其收到定制请 求的物理控制器(或者机架控制器)。在物理控制器或者机架控制器，如果 需要，定制响应被聚合，随后被转换成通用响应。通用响应随后被向上 传递给物理控制器从其收到通用请求的逻辑控制器。

例如，物理控制器815接收来自托管转发元件825和830的定制请 求，聚合所述定制请求，并将其转换成通用响应。在一些实施例中，物 理控制器820不必聚合定制的响应。物理控制器820仅仅转换从托管转 发元件825接收的定制的响应，并把通用响应向上传递给逻辑控制器 810。

逻辑控制器810接收来自逻辑控制器810向其发送通用请求的物理 控制器的通用响应。逻辑控制器810聚合通用响应，把聚合的通用响应 转换成逻辑响应，随后把逻辑响应向上传递给输入转换控制器805。在一 些实施例中，输入转换控制器805随后把逻辑响应转换成供用户通过管 理应用查看的输出。

在一些实施例中，用分别用于指定定制请求、通用请求和逻辑请求 的相同属性指定定制响应、通用响应和逻辑响应。在一些实施例中，这 些请求和响应呈数据元组的形式。

注意，在一些情况下，控制器的分层结构中的控制器不接收来自分 层结构中的下面控制器的多个响应。例如，当请求用于获得被映射到特 定托管转发元件的特定物理端口的特定逻辑端口的信息时，逻辑控制器 不必向不止一个物理控制器分发通用请求，于是，逻辑控制器会从该物 理控制器获得一个通用响应。

当控制器向控制器的分层结构中、向该控制器发送请求的上方的另 一个控制器传递响应时，该控制器以事务的方式发送响应。图9图解说 明聚合从一组物理控制器935、940和945接收的通用响应的一些实施例 的逻辑控制器910。特别地，图9分5个阶段901-905，图解说明逻辑控 制器910把通过处理来自几个不同物理控制器的构成几个事务的输入变 化而获得的输出变化聚合成单组事务输出变化。逻辑控制器910随后把 聚合的输出变化向上传递给输入转换控制器(未示出)。聚合的输出信号包 括逻辑响应，所述逻辑响应包含由逻辑控制器905从输入转换控制器接 收的逻辑请求所询问的信息。

逻辑控制器910类似于上面参考图2说明的网络控制器200，因为逻 辑控制器910包括与控制器200的对应组件类似的导入器915、规则引擎 920、输入表924和输出表930。为了讨论的简明起见，图9中未表示逻 辑控制器910的所有组件。

在第一阶段901，物理控制器935正把输入变化1-3发送给逻辑控制 器910。输入变化1-3包括响应于收到来自逻辑控制器910的通用请求， 由物理控制器935准备的通用响应。在一些实施例中，输入变化1-3包括 通用请求的标识符。逻辑控制器910利用标识符来匹配对请求的响应。

在一些实施例中，物理控制器935通过(1)聚合物理控制器935从一 组托管转发元件接收的一组定制响应，和(2)把聚合的定制响应转换成通 用响应，准备通用响应。在其它实施例中，物理控制器935通过聚合物 理控制器935从一组机架控制器(未示出)接收的一组通用响应，准备通用 响应。机架控制器通过聚合来自一组托管转发元件实例的一组定制响应， 准备向上传递给物理控制器935的通用响应，所述一组托管转发元件实 例在机架控制器工作于的相同主机中工作。

在阶段901，输入表925和输出表930可包含关于转发状态、请求和 /或响应的记录。为了讨论的简明起见，在图中未描述这些其它记录。

在第二阶段902，逻辑控制器910已从物理控制器935收到变化1-3。 导入器915已用变化1-3更新输入表925。第二阶段902还表示物理控制 器940在发送构成完整事务的变化4-6。控制器945在发送构成完整事务 的变化7和8。变化4-6和变化7-8包括物理控制器935和940分别响应 于从逻辑控制器910收到通用请求而准备的通用响应。在一些实施例中， 变化4-8还包括通用请求的标识符。

在第三阶段903，逻辑控制器910已收到来自物理控制器940的一组 事务输入变化4-6，和来自物理控制器945的构成事务的输入变化7和8。 导入器915用变化4-8更新输入表925。输入表925现在具有变化1-8。 第三阶段903还表示规则引擎920已进行表映射操作，从而根据在前一 阶段902放入输入表925中的变化1-3，产生输出变化。

另外在阶段903，逻辑控制器910判定是否(1)发送通过处理变化1-3 而产生的输出变化，因为逻辑控制器910已通过处理构成完整事务的输 入变化，产生了这些输出变化，或者(2)等待包含通用响应的更多输入变 化到来。物理控制器根据特定标准，进行该判定。例如，在一些实施例 中，逻辑控制器910等待从逻辑控制器910接收通用请求的所有物理控 制器向上传递通用响应。在这些实施例中，逻辑控制器910聚合通过处 理所有的通用响应而产生的输出变化，以产生逻辑响应。另一方面或者 结合地，物理控制器505聚合通过处理在通用请求被向下发送给物理控 制器之后，在预定一段时间内接收的通用响应而产生的输出变化。物理 控制器根据在所述预定一段时间内聚合的输出变化，产生逻辑响应。

在第四阶段904，逻辑控制器910确定逻辑控制器910应利用更多的 包含通用响应的事务来产生包含逻辑响应的单组事务输出变化。从而， 逻辑控制器910未发送在前一阶段903，根据输入变化1-3计算的输出变 化。规则引擎920已对变化4-8进行了表映射操作，并产生了对应的输出 变化。不过，如图所示，根据输入变化4-8计算的输出变化现在和根据输 入变化1-3计算的输出变化被集中在一起。从而，逻辑控制器910产生了 所述单组输出变化，所述单组输出变化包含通过聚合构成3个完整事务 的输入变化1-3、4-6和7-8而产生的逻辑响应。

在第五阶段905，逻辑控制器901已把根据变化1-8计算的输出变化 发送给输入转换控制器(未示出)。物理控制器已从输入表925中除去了输 入变化1-8，并从输出表930中除去了输出变化。

图9图解说明逻辑控制器的通用响应的聚合。本领域的普通技术人 员会认识到图9中图解说明的逻辑控制器和物理控制器可分别用物理控 制器和机架控制器代替，以便图解说明物理控制器的定制响应的聚合。

图10概念地图解说明一些实施例进行的聚合来自在控制器的分层结 构中的下面一层中的一组下层控制器的一组响应，从而生成单一响应， 以向上传送给在分层结构中的上面一层中的上层控制器的过程1000。在 一些实施例中，过程1000由与图8和9的逻辑控制器810和910类似的 中间控制器进行。即，中间控制器(1)接收来自上层控制器的请求，(2)把 所述请求分发给一组下层控制器，和(3)聚合来自下层控制器的对所述请 求的响应，从而产生单一响应，并向上传递给上层控制器。在一些实施 例中，中间控制器接收或产生的请求和响应呈构成完整事务的变化(例如， 数据元组)的形式。

在一些实施例中，接收控制器是从输入转换控制器接收逻辑请求； 向一组物理控制器发送通用请求；从物理控制器接收通用响应；和向输 入转换控制器发送逻辑响应的逻辑控制器。下面，过程1000被描述成由 逻辑控制器进行。不过，一些实施例的接收控制器可以是从逻辑控制器 接收通用请求；向一组托管转发元件发送定制请求，或者向一组机架控 制器中继通用请求；从托管转发元件接收定制响应，或者从机架控制器 接收通用响应；并向逻辑控制器发送通用响应的物理控制器。

通过(在1005)接收来自输入转换控制器的逻辑请求，开始过程1000。 输入转换控制器根据由一些实施例的网络控制系统的用户提供的输入数 据，产生逻辑请求。逻辑请求询问用户通过输入转换控制器管理的逻辑 转发元件的一些信息。过程1000随后通过把逻辑请求转换成通用请求， (在1010)计算通用请求。

之后，过程1000(在1015)识别向其发送通用请求的一组物理控制器。 为了识别所述一组物理控制器，过程1000首先识别实现逻辑转发元件的 一组托管转发元件，随后识别这组托管转发元件的主物理控制器。在一 些实施例中，这些主物理控制器应接收所述通用请求。过程1000(在1015) 把通用请求发送给每个识别的物理控制器。在一些实施例中，过程1000 保持逻辑请求的标识符，并把所述标识符加入通用请求中。过程1000利 用标识符来匹配对通用请求以及对逻辑请求的通用响应。

在把通用请求发送给识别的一组物理控制器之后，过程1000(在1020) 接收来自物理控制器的通用响应。另外在1020，过程1000处理包含通用 响应的输入变化(例如，对输入变化进行表映射操作)，从而产生输出变化。

之后，过程1000(在1025)判定过程1000是否从物理控制器收到至少 一个完整的事务。完整的事务包括在从物理控制器收到分界线之后，并 在收到另一个分界线之前，从所述物理控制器接收的输入变化。来自物 理控制器的完整事务包括通用响应。

当过程1000(在1025)确定过程还未从物理控制器收到至少一个完整 的事务(例如，至少一个完整的通用响应)时，过程1000返回1020，以便 从物理控制器接收更多的输入变化。

当过程1000(在1025)确定过程收到至少一个完整的事务时，过程 1000进入1030，以判定特定聚合标准是否被满足。不同的实施例具有不 同的聚合标准。例如，在一些实施例中，所述特定标准包括自从(在1015) 发出通用请求以来，或者自从(在1005)收到逻辑请求以来过去的一段时 间。当所述一段时间过去时，所述特定标准被满足。另一方面或者结合 地，在一些实施例中，所述特定标准包括是否从接收通用请求的所有物 理控制器都收到了通用响应。在这些实施例中，当从接收通用请求的所 有物理控制器收到通用响应时，所述特定标准被满足。

当过程1000确定(在1030)特定标准未被满足时，过程返回1020， 继续接收通用响应，并处理所述通用响应。当过程1000判定(在1030)所 述特定标准被满足时，过程1000聚合(在1035)根据接收的通用响应计算 的输出变化(即，包含通用响应的完整事务的输入变化)。另外在1035， 过程1000根据聚合的输出变化，产生单一的逻辑响应。

过程1000随后(在1040)把逻辑响应发送给已向逻辑控制器发送逻辑 请求的输入转换控制器。一些实施例的过程1000在输出变化的结尾插入 分界线，或者向输出变化中的最后一个变化添加指示完整事务的信息。 另外，所述过程从逻辑控制器的输出表中除去发送出的输出变化，并从 逻辑控制器的输入表中，除去构成根据其计算逻辑响应的完整事务的输 入变化。所述过程随后结束。

III.电子系统

许多上述特征和应用被实现成软件过程，所述软件过程被指定成记 录在计算机可读存储介质(也称为计算机可读介质)上的指令集。当这些指 令由一个或多个处理单元(例如，一个或多个处理器、处理器的核心、或 者其它处理单元)执行时，它们使所述处理单元进行在指令中指示的动作。 计算机可读介质的例子包括(但不限于)CD-ROM、闪速驱动器、RAM芯 片、硬盘驱动器、EPROM等。计算机可读介质不包括载波和无线地或 者通过有线连接传送的电子信号。

在本说明书中，术语“软件”意味包括可被读入内存中，以便由处理 器处理的驻留在只读存储器中的固件，或者保存在磁存储器中的应用。 另外，在一些实施例中，在仍然是不同的软件发明的情况下，多个软件 发明可被实现成更大的程序的子部分。在一些实施例中，多个软件发明 也可被实现成独立的程序。最后，一起地实现这里说明的软件发明的独 立程序的任意组合在本发明的范围之内。在一些实施例中，当被安装以 在一个或多个电子系统上工作时，软件程序定义执行和实现软件程序的 操作的一种或多种具体的机器实现。

图11概念地图解说明可实现本发明的一些实施例的电子系统1100。 电子系统1100可用于执行上面说明的控制、虚拟化或操作系统应用程序 任意之一。电子系统1100可以是计算机(例如，桌上型计算机、个人计算 机、平板计算机、服务器计算机、大型机、刀片计算机等)、电话机、PDA 或任意其它种类的电子设备。这样的电子系统包括各种计算机可读介质， 和用于各种其它种类的计算机可读介质的接口。电子系统1100包括总线 1105、处理器1110、系统内存1125、只读存储器1130、永久性存储设备 1135、输入设备1140和输出设备1145。

总线1105总体代表通信地连接电子系统1100的众多内部设备的所 有系统总线、外围总线和芯片集总线。例如，总线1105通信地连接处理 器1110和只读存储器1130、系统内存1125和永久性存储设备1135。

从这些各个存储单元，处理器1110取回待执行的指令和待处理的数 据，以便执行本发明的过程。在不同的实施例中，处理器可以是单一处 理器或者多核处理器。

只读存储器(ROM)1130保存处理器1110和电子系统的其它模块需 要的静态数据和指令。另一方面，永久性存储设备1135是读-写存储设备。 该设备是即使光电子系统1100关闭时，也保存指令和数据的非易失性存 储器。本发明的一些实施例利用大容量存储设备(比如磁盘或光盘及其对 应的盘驱动器)，作为永久性存储设备1135。

其它实施例利用可拆卸的存储设备(比如软盘、闪速驱动器等)，作为 永久性存储设备。类似于永久性存储设备1135，系统内存1125是读-写 存储设备。然而，不同于存储设备1135，系统存储器是易失性读-写存储 器，比如随机存取存储器。系统内存保存在运行时，处理器需要的一些 指令和数据。在一些实施例中，本发明的过程被保存在系统内存1125、 永久性存储设备1135和/或只读存储器1130中。从这些各个存储单元， 处理器1110取回待执行的指令和待处理的数据，以便执行一些实施例的 过程。

总线1105还连接到输入和输出设备1140和1145。输入设备使用户 能够向电子系统传达信息和选择命令。输入设备1140包括字母数字键盘 和指示设备(也称为“光标控制设备”)。输出设备1145显示由电子系统生 成的图像。输出设备包括打印机和显示设备，比如阴极射线管(CRT)或液 晶显示器(LCD)。一些实施例包括同时起输入设备和输出设备作用的设 备，比如触摸屏。

最后，如图11中所示，总线1105还通过网络适配器(未示出)，把电 子系统1100耦接到网络1165。按照这种方式，计算机可以是计算机网络 (比如局域网(“LAN”)、广域网(“WAN”)或企业内部网)，或者网络之网(比 如因特网)的一部分。电子系统1100的任意或全部组件可以和本发明一起 使用。

一些实施例包括电子组件，比如微处理器，把计算机程序指令保存 在机器可读或计算机中读介质(另一方面，称为计算机可读存储介质、机 器可读介质或机器可读存储介质)中的存储器和内存。所述计算机可读介 质的一些例子包括RAM、ROM、只读光盘(CD-ROM)、可记录光盘 (CD-R)、可重写光盘(CD-RW)、只读数字通用光盘(例如，DVD-ROM、 双层DVD-ROM)、各种可记录/可重写DVD(例如，DVD-RAM、 DVD-RW、DVD+RW等)、闪存(例如，SD卡、小型SD卡、微型SD卡 等)、磁性和/或固态硬盘驱动器、只读和可记录蓝光光盘、超高密度 光盘、任何其它光或磁介质、以及软盘。计算机可读介质可保存可由至 少一个处理单元执行，并且包含用于实现各种操作的多个指令集的计算 机程序。计算机程序或计算机代码的例子包括比如由编译器产生的机器 代码，和包括通过利用解释器，由计算机、电子组件或微处理器执行的 高级代码的文件。

尽管上面的讨论主要涉及执行软件的微处理器或多核处理器，不过 一些实施例由一个或多个集成电路，比如专用集成电路(ASIC)或现场可 编程门阵列(FPGA)实现。在一些实施例中，所述集成电路执行保存在电 路本身上的指令。

本说明书中使用的术语“计算机”、“服务器”、“处理器”和“存储器” 都指的是电子或其它技术设备。这些术语把人或人群排除在外。对本说 明书来说，术语“显示”意味电子设备上的显示。本说明书中使用的术语 “计算机可读介质”和“机器可读介质”完全局限于以计算机可读的形式， 保存信息的有形物理物体。这些术语排除任何无线信号、有线下载信号 和任何其它短暂的信号。

尽管关于众多的具体细节，说明了本发明，不过，本领域的普通技 术人员会认识到，可以用其它具体形式体现本发明，而不脱离本发明的 精神。另外，许多附图(包括图4、7和10)概念地图解说明了各种过程。 这些过程的具体操作可以不按照表示和说明的严格顺序进行。可以不用 连续的一系列操作进行所述具体操作，并且在不同的实施例中，可以进 行不同的具体操作。此外，过程可以利用几个子过程来实现，或者被实 现成更大的宏过程的一部分。