用于在提供商网络中指配多实例服务的系统和方法

摘要

用于在服务提供商网络中放置具有多个实例的联机服务的系统和方法。在一个实现中，定义服务提供商网络的拓扑以及其中要放置的服务，其中网络节点可包括数据转发功能性和控制平面功能性。使用服务链策略要求、服务实例数量等作为输入，服务及其多个实例放置在网络内，使得对所有订户数据流来优化总网络度量。

说明书

相关申请的交叉引用

本申请是下列共同待审共同受让专利申请的部分继续申请：(i)2013年9月13日以YingZhang和Neda Beheshti-Zavareh的名义提交的申请号: 14/026,344 的“SERVICEPLACEMENT FOR INLINE SERVICES CHAINING WITH MULTIPLE INSTANCES”(Ericsson 参考号: P40960-US1)，并且公开与下列美国专利申请（一个或多个）的主题相关的主题：(i)2013年1月28日以Ying Zhang和Neda Beheshti-Zavareh的名义提交的申请号 13/751,826的 “METHOD AND APPARATUS FOR PLACING SERVICES IN A NETWORK”(Ericsson 参考号:P38903-US1)；以及(ii)2012年7月24日以Geoffrey Lefebvre、Erik Rubow和RaviManghirmalani的名义提交的申请号13/556,456的 “CHAINING OF INLINE SERVICESUSING SOFTWARE DEFINED NETWORKING”(Ericsson参考号: P37236-US2)；通过引用将其每个完整地结合到本文中。

技术领域

本公开一般涉及网络领域。更具体来说但不是作为任何限制，本公开针对网络中的具有多个实例的服务的放置（placement）。

背景技术

运营商使用不同中间盒服务或装备（appliance）(称作联机（inline）服务，例如深层分组检查(DPI)、记录/计量/计费/先进计费、防火墙、入侵检测和防护(IDP)、网络地址转换(NAT)等)来管理订户的业务。这些服务对吞吐量和分组检查能力具有高要求。它们能够对最终用户是透明或者不透明的。联机服务能够在专用物理硬件上或者虚拟机中托管。

如果业务需要经过一个以上联机服务，则可要求服务链。此外，如果一个以上服务链是可能的，则运营商需要配置连网基础设施来经过正确联机服务路径来引导正确业务。

发明内容

本专利公开广义地针对用于在服务提供商网络中放置具有多个实例(又称作“服务副本（replicas）”)的联机服务的方案。

在一个方面，公开一种用于在服务提供商网络中指配服务或服务实例的方法的实施例。要求保护的实施例除了别的以外还包括定义服务提供商网络的拓扑，其中网络节点可包括数据转发平面和控制平面功能性。然后定义或者以其他方式得到要在服务提供商网络中放置或指配的服务集合，其中至少一个服务可提供有多个实例(即，副本)。对于在一个或多个入口节点进入服务提供商网络的多个订户数据流来得到或者以其他方式确定服务要求集合，各要求是供各订户数据流在从一个或多个出口节点离开之前要遍历的服务的顺序。此后，服务及其多个实例(若有的话)可相对于服务提供商网络的一个或多个网络节点来指配，使得对所有订户数据流来优化与服务提供商网络关联的总网络度量。在示例实现中，要优化的网络度量包括订户流的基于性能的度量(例如带宽度量(例如，带宽利用))、总延迟和/或距离、跳计数（count）等中的至少一个。在另外的实现中，前述服务指配/放置方法还可包括：定义各服务的服务相关性并且对服务相关性评级（rank）；基于服务相关性的评级、各服务的实例的数量或者它们两者来确定各服务的权重；以及基于用于局部（locally）优化选择网络/性能度量的局部（local）优化机制(例如使用贪婪算法)相对于网络节点迭代地放置或指配各服务及其(一个或多个)实例，通过具有最大权重值的服务而开始。

在另一方面，公开网络管理节点的实施例，其包括：一个或多个处理器；以及持久存储器模块，具有配置成在由处理器运行时执行上文所描述方法的实施例的指令。在又一方面，公开一种非暂时计算机可读介质的实施例（包含存储在其上的用于执行上面阐述的方法的一个或多个实施例的指令）。将会了解到，虽然某些备选/附加实施例可涉及软件定义网络(SDN)架构内的服务放置，但是本发明不一定局限于此，以及其教导可在任何网络(包括例如涉及业务导引（steering）以及控制和数据平面耦合的变化程度的网络)中实施。

本发明的优点包括但不限于在具有一个或多个服务链策略的服务提供商网络内优化多实例服务的放置和/或指配。因为缺省指配能够动态改变，所以服务网络运营商能够使更多服务在线，而没有影响可缩放性。在从属权利要求中要求保护各种实施例的另外的特征。根据下列描述和附图，实施例的附加益处和优点将是显而易见的。

附图说明

在附图的图形中作为示例而不是作为限制来示出本公开的实施例，附图中，相通参考标号表指示相似元件。应当注意，本公开中对“一”、“一个”实施例的不同引用不一定表示同一实施例，并且这类引用可表示至少一个。此外，在结合实施例来描述具体特征、结构或特性时，无论是否明确描述，均认为结合其他实施例来实现这类特征、结构或特性在本领域的技术人员的知识之内。

附图结合到本说明书中并且形成其部分，以示出本公开的一个或多个示范实施例。通过结合所附权利要求并且参考附图进行的以下详细描述，将会理解本公开的各种优点和特征，在附图中：

图1A描绘示例网络，其中可实施本专利公开的一个或多个实施例；

图1B描绘附加示例网络，其中可实施本专利公开的一个或多个实施例；

图2和图3描绘与按照本专利公开的服务放置和/或指配机制的一个或多个实施例的变化的步骤、动作和/或框有关的流程图；

图4描绘按照本专利公开的实施例的可配置成实现服务放置和/或指配机制的网络控制器节点的框图；

图5描绘具有带有数据转发和控制平面功能性的节点的另一个示例服务提供商网络，其中可实施本专利公开的实施例；

图6描绘具有数据转发和控制平面功能性的示例网络节点的框图；以及

图7描绘按照本专利公开的另外的实施例的可配置成在图5的服务提供商网络中实现服务放置和/或指配机制的网络管理器节点的框图。

具体实施方式

在以下描述中，针对本专利公开的一个或多个实施例阐述许多具体细节。但是应当理解，在没有这类具体细节的情况下也可实施一个或多个实施例。在其他实例中，没有详细示出众所周知的电路、子系统、组件、结构和技术，以免模糊对示例实施例的理解。相应地，本领域的技术人员将意识到，在没有这类具体的基于组件的细节的情况下，也可实施本公开的一个或多个实施例。还应当认识到，本领域的技术人员借助于本文所阐述的详细描述并且对附图进行参考，将能够在没有过度实验的情况下进行和使用一个或多个实施例。

另外，在以下描述、权利要求或者两者中，可使用诸如“耦合”和“连接”的术语及其派生。应当理解，这些术语不一定意在作为彼此的同义词。“耦合”可用来指示彼此可以有或者可以没有处于直接物理或电接触的两个或更多元件相互协作或交互。“连接”可用来指示相互耦合的两个或更多元件之间的通信（即通信关系）的建立。此外，在本文所阐述的一个或多个示例实施例中，一般来说，元件、组件或模块可配置成执行功能（如果该元件能够执行或者以其他方式在结构上布置成执行该功能）。

如本文所使用的，“网络元件”或“节点”(例如路由器、交换机、桥接器等)是包括硬件和软件的一件连网设备，其在通信上互连网络上的其他设备(例如其他网络元件、端站等)。一些网络元件可包括“多服务网络元件”，其提供对多个连网功能(例如路由选择、桥接、交换、第2层聚合、会话边界控制、服务质量和/或订户管理等)的支持，和/或提供对多个应用服务(例如数据、语音和视频)的支持。订户端站(例如服务器、工作站、膝上型计算机、上网本、掌上型计算机、移动电话、智能电话、多媒体电话、因特网协议上的语音(VOIP)电话、用户设备、终端、便携媒体播放器、GPS单元、游戏系统、机顶盒)可经由适当服务提供商接入网来访问或消费通过分组交换广域公共网络（例如因特网）所提供的内容/服务。订户端站还可访问或消费覆盖在(例如隧穿)因特网上的虚拟专用网络(VPN)上提供的内容/服务。与具体实现无关，应当意识到，本专利公开的一个或多个实施例可涉及具有多个网络节点(例如按照拓扑布置所互连的交换机)的服务提供商网络，其中按照已知或者以其他方式预先配置的服务要求来放置具有多个实例(即，“服务副本”)的一个或多个服务用于由多个订户数据流(由任何类型的上述订户端站所生成或者涉及任何类型的上述订户端站)遍历。

本专利公开的一个或多个实施例可使用软件、固件和/或硬件的不同组合来实现。因此，附图(例如流程图)中所示技术的一个或多个可使用一个或多个电子装置(例如端站、网络元件等)上存储和运行的代码和数据来实现。这类电子装置可使用诸如非暂时计算机可读存储媒体(例如磁盘、光盘、随机存取存储器、只读存储器、闪速存储器装置、相变存储器等)、暂时计算机可读传输媒体(例如电、光、声或其他形式的传播信号—如载波、红外信号、数字信号)的计算机可读媒体来存储和传递(内部传递和/或通过网络与其他电子装置传递)代码和数据。另外，这类电子装置通常可包括一个或多个处理器集合（其耦合到诸如一个或多个存储装置(非暂时机器可读存储媒体)、用户输入/输出装置(例如键盘、触摸屏、定点装置和/或显示器)和网络连接的一个或多个其他组件。该处理器集合和其他组件的耦合通常可经过按照任何已知(例如对称/共享多处理)或迄今未知架构所布置的一个或多个总线和桥接器(又称作总线控制器)进行。因此，给定电子装置的存储装置或组件可配置成存储代码和/或数据以供用于实现本公开的一个或多个技术的目的而在该电子装置的一个或多个处理器上运行。

对图1A进行具体参考，其中所描绘的是示例服务提供商网络100，其具有一个或多个入口节点106-1至106-M以及一个或多个出口节点108-1至108-K，其中可为了在网络内放置多实例服务的目的而实施本专利公开的一个或多个实施例。参考标号110-1至110-L表示多个数据转发节点，其按照拓扑配置耦合在一起，以用于实行将在入口节点106-1至106-M从源域所接收的传入数据分组流102-1至102-N路由到出口节点108-1至108-K(其向外部域发射传出数据分组流104-1至104-N)。应当意识到，网络100内的数据分组的路由可在网络中的任何两个节点之间使用任何已知类的路由选择协议(例如诸如链路状态路由选择协议或者距离-向量路由选择协议)来实行。参考标号112-1至112-I表示要基于订户和/或运营商策略、服务链要求等放置在网络100内的一个或多个联机服务，可要求传入订户数据流102-1至102-N按照顺序次序来遍历所述联机服务。作为示例，这类服务可包括深层分组检查(DPI)、病毒扫描(VS)、入侵检测和防护(IDP)、防火墙(FW)过滤、网络地址转换(NAT)等。此外，这类联机服务的一个或多个可在多个实例或副本中提供，其可由网络运营商来部署以用于例如负荷平衡。

作为说明，在一个实施例中，示例服务提供商网络100可构建为基于已知协议(例如诸如OpenFlow(OF)协议、转发和控制元件分隔(ForCES)协议等)的软件定义网络(SDN)。但是应当意识到，本文所描述的备选/附加实施例也可结合其他网络架构来实施，如下面将阐述的。示例SDN架构通常涉及网络元件的控制和数据平面的分隔和去耦合，由此网络智能和状态控制可在逻辑上集中，并且基础网络基础设施从应用来抽象。因此，基于SDN的服务网络的一个实现可包括运行网络中的一个或多个服务器的全网络控制平台，其配置成监视和控制多个数据转发节点或交换机。相应地，标准化对接可在全网络控制平台(其为了本专利申请的一些实施例的目的而可称作“中央控制器”)与数据交换/转发节点之间提供，由此促进高可缩放性、基于流的服务链、多租户和安全基础设施共享、虚拟覆盖连网、有效负荷平衡等。相比之下，传统网络架构遵循集成设计，其中控制平面和数据转发平面在相同网络元件中密切耦合，这通常引起具有伴随缺点和缺陷的过度复杂的控制平面和复杂网络管理。

典型SDN交换节点包括：流表，其执行分组查找和转发；以及安全信道，其将交换机连接到中央控制器，从而允许命令和分组使用开放和标准协议在其之间发送。转发元件或交换机的主要任务是要按照控制器所编程的流表中的规则将分组从入口端口转发到出口端口。流表可包含流条目集合、活动计数器以及应用于匹配分组的一个或多个动作集合。例如，流条目可配置有动作集合，例如：将分组转发到给定端口、修改分组报头中的某些位、将分组封装到控制器或者简单地丢弃分组。对于新流中的第一分组，交换机通常将分组转发到控制器，以便触发被编程的新流条目。交换机还能够用来将所有慢路径分组（例如因特网控制消息协议(ICMP)分组）转发到控制器供处理。应当意识到，数据分组流的概念能够广义地定义，例如传输控制协议(TCP)连接，或者来自具体媒体访问控制(MAC)地址或因特网协议(IP)地址的所有业务，或者具有相同虚拟LAN(VLAN)标签的所有分组，或者来自相同交换机端口的所有分组，或者具有一个或多个用户定义控制标志的所有业务，以及包括前述条件性的任何组合。

针对图1A中所示的示例网络实现，参考标号115表示用于使用相对于其余网络组件（如通过接口116、118所例示的）的标准化对接架构来实现网络的控制平面操作的全网络控制器。网络控制器115可以操作以便从流表添加流条目和从流表移除流条目，例如作为定义该数据平面交换机集合之间的互连和路由选择的部分。网络控制器115还处置网络状态分发，例如从交换机收集信息并且向交换机分发路由选择指令。网络控制器115还能够编程为支持任何新的寻址、路由选择和复杂分组处理应用。相应地，网络控制器115可被认为是示例服务提供商网络100的“大脑”，其中可要求交换机连接到至少一个控制器功能性，以便正确操作。

应当意识到，图1A的示例网络100的入口和出口节点放置在网络100的周边，其中入口节点106-1至106-N可配置成分类传入业务流，并且使用控制器节点115所运行的业务导引机制基于服务链策略和其他服务要求(共同示为服务要求数据库114)将它导引朝向下一个服务。转向图1B，其中所示的是服务提供商网络布置150的稍微简化和/或更具体化解释，其中服务放置/指配机制可按照实施例来实施。如所示的，诸如VS 168、防火墙170、DPI182、内容高速缓存190的服务使用一个或多个周边节点或交换机162、164、166、180和一个或多个内部节点或交换机172、174、176、178经由网络来提供给订户。按照以上描述，按照OpenFlow(OF)协议所提供的逻辑上集中的控制器165用来管理交换机和中间盒，例如服务。在示例导引架构中，服务路径可基于订户、具体应用和所要求服务次序来配置，并且可作为方向特定或单向来提供。也就是说，可对上游和下游业务来指定不同的服务路径。图1B中，示出两个不同的服务路径。一个订户的服务路径156(例如涉及来自无线基础设施154的移动网络业务)示出在经过周边交换机180离开并且经由边界网关192进入因特网194之前经过VS 168、DPI 182和内容高速缓存190的上游业务。另一方面，另一个(或者相同)订户的服务路径158(例如涉及来自订户家庭驻地152的固定网络业务)旁路（bypass）所有服务。

由于OpenFlow节点在网络的周边提供，所以交换机162、164、166、180可配置成分类传入业务，并且在控制器165的控制下响应与相应流156、158有关的可应用服务链策略而对它进行导引，其中除了要求一个或多个服务被遍历的策略之外还可提供服务旁路策略。应当意识到，这类业务旁路策略对于节省网络中的资源会是有用的。此外，本领域的技术人员将认识到，在图1B的实施例中，周边交换机162、164、166、180是网络节点（服务和/或其他网关节点连接到其）。另一方面，内部交换机172、174、176、178可配置成简单地使用第2层(L2)交换来转发业务，并且因而可以仅连接到其他交换机。相应地，在一个实现中，内部交换机172、174、176、178可以是或者可以不是控制器165所控制的OF交换机。与内部交换机是否为符合OF的交换机无关，由中央控制器165所运行的导引机制可涉及二步过程。第一步骤分类传入分组，并且基于预定义订户、应用和排序策略为其指配服务路径。第二步骤涉及将分组转发到下一个服务（基于沿它的指配服务路径的其当前位置）。这类二步业务导引过程仅需要在任何两个边界路由器之间执行一次，而不管连接它们的交换机的数量。与SDN架构中的单实例服务的放置和示例业务导引实现有关的附加细节可在下列共同拥有共同待审的美国专利申请（一个或多个）的一个或多个中找到：(i) 2012年7月24日以GeoffreyLefebvre、Erik Rubow和Ravi Manghirmalani的名义提交的申请号: 13/556,456的“CHAINING OF INLINES SERVICES USING SOFTWARE DEFINED NETWORKING”(Ericsson 参考号: P37236-US2)；以及(ii) 2013年1月28日以Ying Zhang和Neda Beheshti-Zavareh的名义提交的申请号: 13/751,826的“METHOD AND APPARATUS FOR PLACING SERVICES IN ANETWORK”(Ericsson 参考号: P38903-US1)；并且由此通过引用将上述交叉引用结合到本文中。

在上面描述的示例网络架构的一个实现中，可按照本专利申请的多实例服务放置方案的实施例来考虑下列方面或因素的一个或多个。首先，可要求各订户指定订户的业务流需要遍历的服务的准确次序或顺序(即，特定订户的服务要求)。例如，订户可指定订户的业务应当首先经过防火墙服务并且然后经过DPI服务。其次，服务提供商/运营商可出于各种业务管理原因(例如负荷平衡、带宽优化、延迟最小化等)而部署服务的多个实例。说明性地，联机服务网络可具有防火墙服务的三个实例以及DPI的两个实例，其在一些实现中可作为虚拟化服务装备来提供。另外，一个订户的流能够被指配给服务的不同实例或副本以用于负荷平衡。另一方面，服务实例的分配的设定能够从缺省指配动态地改变。在一个配置中，缺省指配策略可以是将业务流路由到地理上最接近的服务实例/副本，以便使延迟为最小化。

因此，本领域的技术人员将认识到，在按照本文所阐述的理论的服务放置方案的实施例中，可用于各服务的实例的数量除了别的以外是重要因素或输入。此外，如下面将详细描述的，被估计或者以其他方式确定为最严格资源的服务(例如具有最少数量的实例但是具有大量服务路径和遍历它的大量数据业务)将首先被定位或放置在网络中，其中附加服务迭代地放置在其后。

为了本专利申请的目的，多实例服务放置机制可公式化为优化机制，其中适当的总网络度量相对于网络内的服务的放置为最小、最大或者以其他方式来优化。例如，可实现多实例服务放置机制的实施例，其中供所有订户的业务(即，数据流)要遍历的总延迟或距离最小化。取决于如何配置网络，可实现多实例服务放置机制的另一个实施例，其中要由网络中的订户数据流进行的总跳数(即，跳计数)最小化。在又一实施例中，可优化其他性能度量（例如总网络带宽消耗（consumption）/分配，以用于放置服务的多个实例。

为了公式化用于实现服务放置机制的各种过程、步骤、动作和框，示例服务提供商网络可使用来自图论的某些构造来抽象，其中预定目标函数，例如网络业务/性能度量被最小化或者以其他方式优化。为了此目的，使用下列符号。示例网络，例如具有上面描述的业务导引机制的OF网络表示为图G=(V, E)，其中取决于网络的给定连接性或配置，节点集合V表示网络中的交换机，以及边缘集合E表示交换机之间的逐对链路或边缘。在一个实现中，图G可以是具有加权边缘的无向对称图，即，如果(u, v) 0 E，则(v, u) 0 E。各边缘可与延迟值d_u,v关联。延迟值能够简单地为d_u,v>v,u>

联机服务集合表示为S>1,>2,…s_h}，其中各元素是要放置的一种类型的服务。各订户的数据流具有其自己对要遍历的联机服务的顺序的要求。例如，订户i的要求r_i= ing0,>1,>3,>5,>2,>1,>2,…r_k}，其中存在总共k个订户。另外，存在另一个{1xh}向量或副本阵列，其存储各服务的副本或实例的数量，N>1,>2,…n_h}，指示具体服务s_i具有n_i个数量的实例。

为了服务放置的目的，目标是开启所有候选VN = |V|之间的位置的子集M(|M| =|S| = h)，并且放置服务，使得所有用户的总延迟最小化。给定服务放置L，对于各服务顺序r_i，能够计算用于遍历r_i中的所有服务的总延迟。这个计算表示为：

在这里，d(r_i)^L表示在解L下的服务链r_i的延迟。元素a和b能够是任何入口点、出口点和任何服务实例。其是对所有连续入口/出口节点与r_i中的服务(a,>a,>b)的延迟计算为下列解下的a与b之间的路径中的所有边缘(u,>

这个解能够公式化为找到L以便：

按照本专利公开的教导，通过检查每个单独服务与其他服务之间的相关性以及所有入口和出口节点来创建虚拟图。此后，可每次使用局部优化试探(例如贪婪算法)迭代地放置服务，以便选择相对所有所放置的服务促成最小总性能恶化(在这种情况下为延迟)的位置。应当认识到，局部优化试探的目标函数也可涉及其他网络度量（单独地或者与延迟度量结合进行），以便实行服务放置。

为了本专利申请的目的，服务相关性可确定为在考虑下的当前服务的位置如何取决于或者应当取决于其他实体的位置的量化。可定义服务相关性图G₀>0,>0)，其中V₀包含S中的所有服务加上G中的所有边缘节点(即，入口和出口节点)。E₀中的边缘(u₀,v₀)表示存在从u₀到v₀的业务。此外，权重因数或参数可被定义或者以其他方式指配给边缘，w(u₀,v₀)，指示订户或数据流（其业务需要从u₀转到v₀）的总数(即，边缘权重)。应当认识到，图G₀能够是有向图，因为存在与数据业务流关联的方向性。又一个权重因数或参数可被定义或者以其他方式与图G0中的各节点关联，即w(v₀)，其可被确定或计算为到未放置服务的节点的出局（outbound）边缘的权重的和(即，节点权重)。

相应地，应当意识到，服务放置机制可看作是用于从虚拟服务图G₀到物理网络图G的映射的转换机制或图嵌入机制。如上面所阐述的，基于连续局部优化的贪婪算法为了便于大图中的计算效率而可用于实行这类机制，其中预期找到全局最佳。但是，本领域的技术人员将认识到，也可使用其他正式优化技术(例如线性编程或动态编程等)，尽管这类技术能够是极为计算密集的，并且可能花费过度时间量以得到收敛，特别是在涉及具有数百个节点和庞大数量订户流的网络的情况下。

在一个实施例中，服务放置机制可将虚拟服务图G₀中的所有入口和出口节点看作是已经放置的节点。各服务的新权重可计算为基于服务相关性的评级和服务实例的数量的评级的函数。最初，所有服务被看作是未放置集合的成员，因为它们相对于网络中的节点有待放置或指配。在各迭代中，选择具有最大新权重的未放置服务，并且逐个放置该服务的所有副本。在图G中的所有位置之间，每次选择具有放置的服务与考虑用于放置的具体服务的特定实例之间的最小总延迟的具体位置解。在其被放置之后，服务副本阵列采用各副本上的剩余负荷来更新。在放置具体服务的所有实例/副本之后，更新所有其他未放置服务的节点权重，直到未放置集合递减为零(即，没有更多服务要放置)。

可通过符合OF的中央控制器(例如上面描述的控制器165)或者按照适当网络架构所提供的某个其他管理节点可运行的计算机可读指令集合来例示和/或实行服务放置机制的前述实施例的实现。与这类实施例有关的示例过程流程在下表1中提供。

表1

本领域的技术人员在参考其时将认识到，按照一个实施例，前述服务放置过程流程利用四个多变元/多维组分(即G、S、R和N)作为输入，这可按照多种方式来实现，包括但不限于使用专用硬件组件、基于以任何已知或者迄今未知的编程语言等的编程指令的软件/固件引擎。如上面所描述的，服务相关性图G₀作为S和物理图G的入口/出口节点的联合来创建。而且，作为初始化的部分，所有服务，包括其实例(若有的话)放置在未放置集合中。在创建各连续服务对的有向边缘时，适当权重参数基于多少流遍历具体边缘以及多少流遍历具体服务来计算。前述操作可统称为初始化和权重计算框或循环。此后，对于各服务，新权重可计算为先前计算的权重参数的函数。在上面所示的示范过程流程中，新权重计算为两个权重(即，边缘权重和节点权重)的评级的平均值或平均数。这些操作可称作新权重计算框或循环。统称为放置操作框或循环的操作的第三集合涉及用于在各边缘执行迭代局部优化过程的未放置集合，提供选择具有最大新权重值的服务而开始。

在一个实施例中，前述服务放置过程流程的输出可实现为图G(表示服务网络的物理节点)与中间盒S(表示要放置的多实例服务)之间的映射指配集合。响应映射关系，服务网络的控制器/管理逻辑可配置成相对于网络节点来放置、部署、连接到和/或以其他方式指配服务。此外，映射关系输出还可提供给与服务网络关联的其他经营(administration)/管理节点。应当意识到，有可能使多个服务实例和多种类型的服务相对于相同网络节点来放置或指配。例如，DPI服务的至少一个实例和NAT服务的至少一个实例均可放置在相同网络节点。另外，在一些实现中可基于服务网络配置、服务链要求、各服务可具有的实例数量等向入口/出口节点和/或内部节点指配服务。

参考图2和图3，其中所示的是与按照在参考标号200、300一般所示的服务放置和/或指配机制的实施例的步骤、动作和/或框有关的流程图。在图2中所示的框202，定义或者以其他方式得到服务提供商网络以及其中其网络节点的拓扑布置。在一个实现中，服务提供商网络可构建为例如如图1A和图1B中所示的SDN。在另一个实现中，服务提供商网络可包括架构，其中在网络节点内可存在变化等级的数据平面和控制平面分隔/耦合。在框204，定义、确定、初始化和/或以其他方式得到包括相应多个实例(若有的话)的一个或多个服务。确定、定义和/或以其他方式得到相对于各种订户数据流的一个或多个服务要求、服务链策略、运营商/应用策略等，如在框206所阐述的。如先前所描述的，各订户数据流因此可与在服务提供商网络的入口节点与出口节点之间要遍历的服务集合(例如有序顺序)关联。此外，在不要求订户数据流遍历任何服务(即，“无服务”策略)的情况下，可实现要求的宽松集合。应当意识到，可从运营商管理节点（例如认证、授权和记帐(AAA)节点）来检索服务、链策略等。在框208，服务及其多个实例(若有的话)相对于一个或多个网络节点在网络中放置和/或指配，使得总网络度量对所有订户流最小化、最大化或者以其他方式优化。

转到图3，其中所示的是与在框208阐述的功能有关的附加步骤、功能、动作和/或框有关的流程图。在框302，创建或者以其他方式定义服务相关性图，其包括基于服务提供商网络的服务和网络入口/出口节点来定义节点或顶点。另外，可基于与流的数量、每流的服务需求度等相关的参数对服务相关性图的节点和边缘分别定义节点权重和边缘权重。对于各服务，可确定或者以其他方式得到基于相对评级、业务量、服务副本/实例的数量等的新权重(框304)。应当了解到，在某些示例实现中，不需要包括节点权重和边缘权重两者。同样地，在某些其他实现中，为了实行按照本文的教导的服务放置机制的目的，可定义或提供附加参数权重。在框306，贪婪算法(例如接着在迭代的各连续阶段进行局部最优选择的问题解决试探之后的算法)可被采用来向网络节点指配服务。虽然可能不一定每次在过程流程完成时找到全局最优放置解，但是试探放置机制可在合理时间和有限计算资源之内近似“足够良好”解。为了实现这类机制，下列组件可至少按照某种组合来提供。首先，定义候选集合，从其中可创建放置解。提供或者以其他方式定义选择函数，其选择最佳候选以便添加到放置解。可定义可行性函数，其可用来确定候选是否能够促成放置解。可提供解函数，以用于指示是否取得了完全放置解。应当了解到，本公开的贪婪算法放置机制可使用“贪婪”的不同特性（例如使用“纯贪婪”、“正交贪婪”或“宽松贪婪”以及使用不同度量以指导贪婪步骤）来实现。此外，在某些网络实现中，例如在涉及相对小数量的网络节点和/或订户流的情况下，更正式优化技术可用于服务放置，如先前所指出的。在得到和/或以其他方式确定放置解时，可向网络节点指配中间盒服务和相应实例，并且这类指配数据可提供给与网络关联的一个或多个管理节点(框308)。

图4描绘按照本专利公开的实施例的可配置成实行服务放置和/或指配机制的实现为示范计算机系统的网络控制器节点400的框图。本领域的技术人员将认识到，网络控制器节点400示出上文所描述的控制器115或165。一个或多个处理器404操作以控制多个子系统(通过硬件、软件、固件和/或通过它们的任何组合所实现的)，其可使用适当总线架构来互连。一个或多个Tx/Rx接口模块402操作以实行相对于控制器节点400的各种类型的网络连接性，包括但不限于服务提供商网络内部的连接性以及外部连接性。一个或多个协议引擎406操作以基于可如何构建服务提供商网络来实行适当通信协议。易失性存储装置418可包括各种类型的随机存取存储器(RAM)，以用于提供数据或信息的暂时存储。非易失性存储装置409示出持久存储装置(例如只读存储器(ROM)电路、可擦可编程只读存储器(EPROM)电路、闪速存储器电路)以及外部存储卡等，其中适当订户信息及相关服务链策略数据408可由运营商、第三方供应商和/或订户经由无线部件(例如空中)或者通过因特网来存储、下载、上载、更新和/或重新配置。另外，持久存储器409可配置成包括合并为一个或多个模块410的程序指令，其是一个或多个处理器404可运行的，以用于在服务提供商网络中实行多实例服务的放置和/或指配。流控制器414可相对在基于SDN的服务提供商网络的符合OF的转发元件中实行符合OF的流表的控制来提供。一个或多个应用416还可作为网络控制器节点400的部分来提供，以用于实行对服务提供商特定的网络级功能性。其他硬件412可包括一个或多个用户输入/输出装置(例如显示屏幕、定点装置等)、命令接口、总线控制器、存储器控制器、电源电路等。

应当意识到，前述服务放置/指配方法论可加以必要修正同样适用于具有展现控制与数据转发平面之间的耦合的变化程度的架构的服务提供商网络（这取决于如先前所指出的特定实现）。在一个实施例中，在图5中例示服务提供商网络500的一般化网络架构。本领域的技术人员将认识到，图5所描绘的示例服务提供商网络500可包括多个内部网络节点506-1至506-N，除了一个或多个入口节点504A和一个或多个出口节点504B之外各具有数据转发和控制平面功能性两者。与图1A中所描述的网络布置相似，一个或多个订户数据流502A在入口节点504A进入服务提供商网络500，并且在从出口节点504B作为离开流502B离开出口节点504B之前遍历各种节点。因为数据转发平面和控制平面功能性耦合在图5的架构中，所以各网络节点除了关于一个或多个适当网络管理节点的适当北向接口(NBI)功能性(例如NBI 514-1至514-N)之外还可包括局部配置/管理层(例如层516-1至516-N)、控制层(例如层516-1至518-N)和数据转发层(例如520-1至520-N)。在一些实例中，某些局部服务还可作为紧密耦合配置中的具体网络节点的部分来提供。除了这类局部服务之外，多个服务510还可配置用于在如先前所描述的服务指配方法论下运行的按照服务要求规则、链策略等预供应。作为说明，适当中央管理节点508可配置成相对服务提供商网络的外围和/或内部节点来运行服务指配/放置，其中一个或多个服务可托管在相应专用硬件机器上，和/或可实现为虚拟服务装备。此外，一个或多个服务还可作为多个实例来提供。可提供适当连接组构512，以用于实行服务提供商网络500内的适当连接性(例如节点间连接性、北向和南向对接、服务间连接等)。

图6描绘具有数据转发和控制平面功能性两者的示例网络节点600（例如内部网络节点）的框图。可为网络节点600的总体控制和管理来提供一个或多个处理器602。适当存储器，包括持久非易失性存储装置604可经由适当总线结构来耦合到处理器602。通常，控制平面功能性606和局部管理功能性608可作为非易失性存储器604中存储的、在需要时要由处理器602所运行的可运行代码部分或程序指令来提供。数据转发平面可实现为基于专用集成电路(ASIC)的硬件模块610，其耦合到具有多个端口的适当收发器电路612。一般来说，数据转发平面负责通过遵循规则(其可编程到硬件中)将数据分组从一个端口携带到另一个，其中控制平面包含节点用来对数据平面进行编程的逻辑。管理平面608允许网络管理员访问装置，使得可执行适当配置、测试、调试等操作(例如使用网络管理工具)。附加Tx/Rx电路614可作为网络节点600的部分来提供，以促进例如适当NBI功能性。

图7描绘按照本专利公开的另外的实施例的可配置为适合在图5的服务提供商网络中实现服务放置和/或指配机制(例如作为中央管理508的部分)的计算机系统的网络管理器节点或服务器700的框图。将认识到，管理节点700在某些方面与上文描述的网络控制器节点400有点相似。与控制器节点400相似，一个或多个处理器704操作以控制多个子系统(通过硬件、软件、固件和/或通过它们的任何组合所实现的)，其可使用适当总线架构来互连。一个或多个TX/Rx接口模块702操作以实行例如与服务提供商网络500关联的如上所描述的相对管理节点700的各种类型的网络连接性。一个或多个协议引擎706操作以基于可如何构建服务提供商网络来实行适当通信协议。易失性存储装置716可包括各种类型的随机存取存储器(RAM)，以用于提供数据或信息的暂时存储。非易失性存储装置708示出非暂时持久存储装置(例如ROM、FPROM、闪速存储器等)以及外部存储器卡等，其中合并为一个或多个模块710的适当程序指令是一个或多个处理器704可运行的，以用于按照上面阐述的方法在服务提供商网络中实行多实例服务的放置和/或指配。适当订户信息及相关服务链策略数据可本地存储(没有具体示出)或者由运营商、第三方供应商和/或订户经由无线部件(例如空中)或者通过因特网以其他方式来下载、上载、更新和/或重新配置。其他硬件712和一个或多个应用714还可作为网络管理节点700的部分来提供，以用于实行对如先前所描述的服务提供商特定的网络级功能性。

基于前述详细描述，应当意识到，本公开的实施例提供用于放置或者以其他方式指配服务提供商网络内的多实例服务的新颖的不明显方法论。由于虚拟化环境和/或基于云的平台中的服务部署变为更加普遍，将服务实例移动到网络内的更最优或者以其它方式更适当位置的灵活性呈现具体的重要性。因为缺省指配能够动态改变，所以服务网络运营商能够使更多服务在线，而没有影响可缩放性。本文所阐述的一个或多个实施例可在任何类型的服务网络架构中结合各种业务导引机制来实施，以便使大量网络性能度量(例如诸如总延迟、距离、跳计数和/或带宽消耗或分配(例如通过降低低效带宽使用))最小化、最大化或者以其他方式来优化。通过有选择地导引业务经过或离开(即，旁路)特定服务，能够有利地实现资本支出节省。此外，通过采用按照本公开的教导的迭代局部优化方案，甚至在具有大量节点、订户数据流或者它们两者的高度复杂网络环境中也可以可靠地得到收敛解。

在本公开的各种实施例的以上描述中，要理解，本文所使用的术语仅为了描述具体实施例的目的，并且不是意在限制本发明。除非以其它方式说明，否则本文所使用的所有术语(包括技术术语和科学术语)都具有与本发明所属领域的技术人员通常所理解的相同的含意。还将会理解，例如通常使用的词典中定义的那些术语等的术语应当被解释为具有与它们在本说明书和相关领域的上下文中的含意一致的含意，并且不会以理想化或过分正式意义来解释，除非本文中这样明确定义。

本文中参考计算机实现方法、设备(系统和/或装置)和/或计算机程序产品的框图和/或流程图图示描述了至少一些示例实施例。要理解，框图和/或流程图图示的框以及框图和/或流程图图示中的框的组合能够通过由一个或多个计算机电路所执行的计算机程序指令来实现。这类计算机程序指令可提供给通用计算机电路、专用计算机电路和/或其他可编程数据处理电路的处理器电路，以产生机器，使得经由计算机和/或其他可编程数据处理设备的处理器运行的指令变换和控制晶体管、存储器位置中存储的值以及这类电路内的其他硬件组件以实现框图和/或流程图框或多个框中指定的功能/动作，并且由此创建用于实现框图和/或一个或多个流程图框中指定的功能/动作的部件(功能性)和/或结构。另外，计算机程序指令还可存储在有形计算机可读介质中，其能够引导计算机或其他可编程数据处理设备以具体方式起作用，使得计算机可读介质中存储的指令产生制造产品，其包括实现框图和/或流程图的框或多个框中所指定的功能/动作的指令。

如先前所提到的，有形非暂时计算机可读介质可包括电子、磁、光、电磁或半导体数据存储系统、设备或装置。计算机可读介质的更具体示例可包括下列项：便携计算机磁盘、RAM电路、ROM电路、EPROM或闪速存储器电路、便携致密光盘只读存储器(CD-ROM)光盘和便携数字视频光盘只读存储器(DVD/蓝光)光盘。计算机程序指令还可加载到或者以其他方式下载到计算机和/或其他可编程数据处理设备，以使一系列操作步骤在计算机和/或其他可编程设备上执行，以产生计算机实现过程，使得在计算机或其他可编程设备上运行的指令提供用于实现框图和/或流程图的框或多个框中所指定功能/动作的步骤。相应地，本发明的实施例可通过硬件和/或通过在例如数字信号处理器等的统称为“电路”、“模块”或者其变体的处理器上运行的软件(包括固件、常驻软件、微代码等)来体现。

此外，在至少一些附加或备选实现中，框中所描述的功能/动作可不按照流程图中所示的次序发生。例如，取决于所涉及的功能性/动作，接连示出的两个框实际上可基本同时运行，或者框有时可按照相反次序运行。此外，流程图和/或框图的给定框的功能性可分为多个框，和/或流程图和/或框图的两个或更多框的功能性可至少部分集成。最后，其他框可被添加/插入所示的框之间，以及来自不同流程图的框可按照任何组合或者子组合来组合、重新排列和/或重新配置为附加流程图。此外，虽然一部分附图包括通信路径上的箭头以示出通信的主要方向，但是要理解，通信可在相对于所描绘箭头的相反方向发生。

虽然已经详细示出和描述了本发明的各种实施例，但是权利要求并不局限于任何具体实施例或示例。上面详细描述决不应当被解读为暗示任何具体组件、模块、元件、步骤、动作或功能是必需的而使得它必须包含在权利要求的范围中。除非明确那样陈述，否则以单数形式对元件的引用并不是意在表示“一个且仅一个”，而是表示“一个或多个”或“至少一个”。本领域的技术人员已知的上述实施例的元件的所有结构和功能等效方案通过引用明确地结合在本文中，并且意在由权利要求涵盖。相应地，本领域的技术人员将认识到，本文所描述的示范实施例能够采用以下所附权利要求的精神和范围之内的各种修改和变更来实施。