多租用云计算网络中的网络带宽分配

摘要

计算装置基于多个VM的带宽要求的集合来确定用于多租户云网络中的多个虚拟机（VM）的多个通信链路上的网络带宽的最佳分配。计算装置生成多个生成树数据结构（TDS）。TDS中的边缘包含指示在由多个VM的那个边缘表示的通信链路上保留的带宽量的计算的带宽值。计算装置生成多个TDS中的每个TDS的加权距离值，并且选择多个TDS中的具有最小加权距离值的TDS作为具有表示网络带宽的最佳分配的计算的带宽值的TDS。

说明书

技术领域

本发明的实施例涉及计算机连网的领域；并且更具体地，涉及用于多租用云计算网络中的网络带宽分配的方法和系统。

背景技术

近年来的云计算的兴起已经改变创建和执行计算应用的方式。大多数云计算提供商采用基础设施即服务（IaaS）模型，其中消费者将它们的计算和软件能力外包到第三方基础设施并且按需支付服务使用，这允许消费者以分钟而不是天或月来建立并且快速扩展国际存在。通过供给实际上无限的资源而没有任何预先的资本投资和简单的现收现付收费模型，云计算向私有计算基础设施的构造、托管和维护提供引人注目的备选。

尽管有云计算的巨大势头，许多公司仍然不愿意将它们的服务或企业应用移动到云，由于可靠性、性能、安全和隐私顾虑。为最大化经济益处和资源利用，云网络通常同时启动多个虚拟机（VM）以在一个物理服务器计算装置上执行。另外，大多数云提供商只使用基于主机的虚拟化技术来实现终端主机层上的VM之间的分离和性能隔离。然后，在互连每个主机的网络中，部署物理路由器和链路的相同集合来无差别地携带所有租户的业务。另外，云提供商不向租户供给确保的网络资源，并且因此相同租户的VM之间的带宽可以随着时间显著地改变，取决于来自其它租户的网络负载和使用。

此外，虽然云计算数据中心提供许多机制来调度本地计算、存储器和磁盘资源，但是用于分配网络资源的现有机制不足。不幸地，当今的公用云平台——例如Amazon的Elastic计算云（EC2）、Google的Google应用引擎、微软的Azure服务平台、Rackspace的Mosso和GoGrid的云托管平台——不提供任何网络性能保证，它又影响应用可靠性和租户成本。特别地，当今的云中的资源保留模型只供应处理器（例如，中央处理单元（CPU））和存储器资源但完全地忽略连网。由于当今的数据中心网络的过度订阅特性，网络带宽是跨许多租户共享的稀有资源。当多个应用的网络密集阶段同时地发生并且竞争这些稀有网络资源，它们的运行时间变得不可预测。执行时间中的此不确定性另外翻译成不可预测的成本，因为租户需要对于它们的任务的整个持续时间为保留的VM进行支付。因此，存在对于提供多租户云网络中的网络带宽分配和保证的系统和机制的需要。

发明内容

根据本发明的实施例，计算装置执行方法以便确定用于连接多租户云网络中的租户的多个虚拟机（VM）的多个通信链路上的网络带宽的最佳分配。所述确定基于多个VM的带宽要求的集合。方法包含生成多个树数据结构（TDS）。多个TDS中的每个TDS包含表示多个VM和在多租户云网络中转发业务的多个网络装置的多个节点。多个TDS中的每个TDS还包含表示多个通信链路中的至少一些通信链路的多个边缘。多个边缘中的每个边缘包含指示在由租户的多个VM的边缘表示的通信链路上保留的带宽量的计算的带宽值。计算的带宽值基于带宽要求的集合。方法还包含生成多个TDS中的每个TDS的加权距离值。加权距离值的生成基于根节点与表示VM的每个其它节点之间的TDS中的距离，并且也基于根节点与表示VM的每个其它节点之间的TDS中的计算的带宽值。方法还包含选择多个TDS中的具有最小加权距离值的TDS作为具有表示网络带宽的最佳分配的计算的带宽值的TDS。

根据本发明的实施例，服务器终端站基于多个VM的带宽要求的集合来确定用于连接多租户云网络中的租户的多个虚拟机（VM）的多个通信链路上的网络带宽的最佳分配。服务器终端站包含一个或多个处理器的集合以及耦合到处理器的集合的树数据结构（TDS）生成模块。TDS生成模块配置为生成多个TDS。多个TDS中的每个TDS包含表示多个VM和在多租户云网络中转发业务的多个网络装置的多个节点。多个TDS中的每个TDS还包含表示多个通信链路中的至少一些通信链路的多个边缘。多个边缘中的每个边缘包含指示在由租户的多个VM的边缘表示的通信链路上保留的带宽量的计算的带宽值。计算的带宽值基于带宽要求的集合。TDS生成模块还配置为生成多个TDS中的每个TDS的加权距离值，基于根节点与表示VM的每个其它节点之间的TDS中的距离，也基于根节点与表示VM的每个其它节点之间的TDS中的计算的带宽值。服务器终端站也包含耦合到处理器的集合的TDS选择模块。TDS选择模块配置为选择多个TDS中的具有最小加权距离值的TDS作为具有表示网络带宽的最佳分配的计算的带宽值的TDS。

根据本发明的实施例，计算机可读存储介质提供指令，所述指令当由计算装置的一个或多个处理器的集合执行时，使计算装置确定用于连接多租户云网络中的租户的多个虚拟机（VM）的多个通信链路上的网络带宽的最佳分配。此确定基于多个VM的带宽要求的集合。计算装置生成多个树数据结构（TDS）。多个TDS中的每个TDS包含表示多个VM和在多租户云网络中转发业务的多个网络装置的多个节点。多个TDS中的每个TDS还包含表示多个通信链路中的至少一些通信链路的多个边缘。多个边缘中的每个边缘包含指示在由租户的多个VM的边缘表示的通信链路上保留的带宽量的计算的带宽值。计算的带宽值基于带宽要求的集合。计算装置也生成多个TDS中的每个TDS的加权距离值基于根节点与表示VM的每个其它节点之间的TDS中的距离，以及根节点与表示VM的每个其它节点之间的TDS中的计算的带宽值。计算装置也选择多个TDS中的具有最小加权距离值的TDS作为具有表示网络带宽的最佳分配的计算的带宽值的TDS。

本发明的实施例允许在多租户云网络内保留的网络带宽量的程序化确定而用最小量的要求的保留带宽向其租户最佳提供带宽保证。实施例允许使用简单的符号来规定带宽要求并且容易用现有的VM实时改变带宽要求。另外，本发明的实施例允许VM位于云网络中的任何位置，并且可以确定给定那个地形的最佳解决方案。

附图说明

可以通过参考下文的描述和用来说明本发明的实施例的附图来最佳地理解本发明。在图中：

图1图示根据本发明的一个实施例的包含虚拟机和规定的带宽要求的示例云计算网络拓扑；

图2图示根据本发明的一个实施例的使用图1的示例云计算网络拓扑的用于带宽分配的基于原生最短路径的方法；

图3图示根据本发明的一个实施例的用于确定在网络链路上保留的要求的带宽的表示生成树和等式的构造；

图4图示根据本发明的一个实施例的加权距离值公式和最佳网络带宽供应算法；

图5图示根据本发明的一个实施例的使用图1的第二虚拟机作为树中的根节点的宽度优先生成树的构造；

图6图示根据本发明的一个实施例的利用最佳网络带宽分配系统的多租户云网络的框图；

图7图示根据本发明的一个实施例的用于基于多个VM的带宽要求的集合来确定多租户云网络中的多个虚拟机的多个通信链路上的网络带宽的最佳分配的流程；以及

图8图示根据本发明的一个实施例的用于确定并且分配网络带宽要求的在云提供商的服务器终端站中执行的流程。

具体实施方式

在下文的描述中，阐述许多具体细节。然而，要理解，可在没有这些具体细节的情况下实践本发明的实施例。在其它实例中，没有详细示出已知的电路、结构和技术以便不模糊此描述的理解。利用包含的描述，本领域的普通技术人员将能够在没有过度的实验的情况下实现适当的功能性。

在说明书中对“一个实施例”、“实施例”、“示例实施例”等的参考指示描述的实施例可包含特定特征、结构或特性，但每个实施例可能不一定包含特定特征、结构或特性。此外，这样的短语不一定参考相同的实施例。另外，当结合实施例来描述特定特征、结构或特性时，认为结合无论是否明确描述的其它实施例来实现这样的特征、结构或特性在本领域的技术人员的知识内。

在下文的描述和权利要求中，可使用术语“耦合”和“连接”以及它们的派生词。应该理解这些术语不旨在作为彼此的同义词。“耦合”用于指示两个或者更多元件，它们可以或可以不彼此直接物理或电接触、彼此协作或交互。“连接”用于指示彼此耦合的两个或者更多元件之间的通信的建立。

本文使用具有虚线边界（例如，大虚线、小虚线、点虚线、点）的加括号文本和框来图示将附加的特征添加到本发明的实施例的可选操作。然而，这样的符号不应该用作意味着这些只是选项或可选的操作，和/或在本发明的某些实施例中具有实线边界的框不是可选的。

电子装置或计算装置（例如，终端站、网络装置）使用机器可读媒体来（内部和/或在网络上用其它电子装置）存储并且传送代码（由软件指令组成）和数据，例如非暂时性机器可读媒体（例如，机器可读存储媒体，例如磁盘；光盘；只读存储器；闪速存储器装置；相变存储器）和暂时性机器可读传送媒体（例如，电、光、声或其它形式的传播信号——例如，载波、红外信号）。此外，这样的电子装置包含硬件，例如耦合到一个或多个其它部件的一个或多个处理器的集合，例如一个或多个非暂时性机器可读媒体（来存储代码和/或数据）、用户输入/输出装置（例如，键盘、触摸屏和/或显示）以及网络连接（来使用传播信号传送代码和/或数据）。处理器的集合和其它部件的耦合通常是通过一个或多个总线和网桥（也被称为总线控制器）。因此，给定电子装置的非暂时性机器可读介质通常存储指令用于在那个电子装置的一个或多个处理器上的执行。可使用软件、固件和/或硬件的不同组合来实现本发明的实施例的一个或多个部分。

如本文所使用的，网络装置（例如，路由器、交换机、网桥）是一件连网设备，包含硬件和软件，它在通信上互连在网络上的其它设备（例如，其它网络装置、终端站）。一些网络装置是提供多个连网功能（例如，路由、网桥、交换机、层2聚合、会话边界控制、服务质量和/或订户管理）的支持和/或提供多个应用服务（例如，数据、语音和视频）的支持的“多个服务网络装置”。订户终端站（例如，服务器、工作站、膝上型计算机、上网本、平板计算机、掌上电脑、移动电话、智能电话、多媒体电话、语音网关（VOIP）电话、用户设备、终端、便携式媒体播放器、GPS单元、游戏系统、机顶盒）是计算装置，通常由用户操作，接入在因特网上提供的内容/服务和/或在覆盖（例如，贯穿）因特网的虚拟私有网（VPN）上提供的内容/服务。内容和/或服务通常是由属于参与对等服务的服务或内容提供商或终端站的一个或多个终端站（例如，服务器终端站）提供，并且例如，可包含公用网页（例如，免费内容、铺面、搜索服务）、私有网页（例如，提供电子邮件服务的用户名/密码接入的网页），和/或在VPN上的企业网络。通常，订户终端站耦合到边缘网络装置（例如，通过耦合到接入网络（有线或无线）的消费者终端设备），边缘网络装置（例如，通过一个或多个核心网络装置）耦合到其它边缘网络装置，其它边缘网络装置耦合到其它终端站（例如，服务器终端站）。

通常将云计算定义为提供计算资源与其潜在的物理架构（例如，服务器计算系统、存储装置和系统、网络）之间的抽象的计算能力，允许对可配置的计算资源的共享池的便捷、按需网络接入，该共享池可以用最小的管理努力或服务提供商交互来快速供应并且释放。由云计算提供商提供的资源可被说成“在云中”。云驻留的元件可包含但不限于存储装置、服务器、数据库、计算环境（包含虚拟机和台式机）网络和应用。在一些设置中，基于因特网的应用（有时是在“软件即服务”（SAAS）模型下提供）可被称作基于云的资源。

云计算运营商或云运营商通常向许多租户提供云服务。为了本公开的目的，将租户最佳地理解为从云运营商请求基于云的资源的人或组织。在一些实施例中，租户可使用订户终端站或计算装置而请求并且管理来自云提供商的基于云的资源。

对于云运营商关键的是部署有效率的网络资源分配和隔离技术，用于隔离租户之间的性能、最小化中断、并且防止恶意拒绝服务（DoS）攻击。网络资源分配的良好解决方案应该满足至少三个要求。第一，它应该允许租户以直觉方式规定它们的应用需求并且支持灵活的更新。更具体地，一方面，系统应该维持租户与提供商之间的接口的简单用于配置不同的服务，但是另一方面，应该允许租户规定各种类型的需求要求。第二，提供商应该仍然能够调节复用的优势来支持在它们的物理网络上的许多虚拟网络。共享的数量越多，云提供商可服务越多租户，并且因此潜在地云提供商将要求更多的收入。第三，分配系统应该与租户的大小成比例。利用每个新的租户，系统应该能够计算最佳带宽保留并且以快速和有效率的方式来设置对应的显式路由。

在最流行的云服务中，例如AmazonEC2，分配给多个租户的网络带宽取决于基于租户之间的竞争的传送控制协议（TCP）。然而，这将导致对DoS攻击的脆弱性。

本发明的实施例处理在云计算环境中缺乏连网服务等级协定（SLA）的问题。本发明的实施例提供最佳方法来供应云计算网络使得云网络可以满足由租户规定的新的网络抽象。使用新的网络抽象，租户可以规定它们的连网资源要求以及它们的CPU和存储器需要，因此它们的应用可以获得关于计算、存储器使用以及网络使用的可预测性能。在一实施例中，新的网络抽象建模使用虚拟群集（VC）模型的带宽抽象，其中所有虚拟机（VM）通过要求带宽B的链路连接到虚拟交换机。

在本发明的实施例中，系统不假设VM可只位于数据中心中的位置的有限集合中（即，执行在特定主机计算系统/装置上）。而是，本发明的实施例允许规定VM位于特别地位置——也许根据它们的CPU、存储器、磁盘或其它从属的要求——并且允许云网络的网络资源的最佳供应（给定规定的VM位置）以便满足这些租户的带宽要求。因此，本发明的实施例允许动态网络供应、使带宽分派能基于网络中的网络状况和VM集合而实时调整。另外，本发明的实施例允许租户的每个VM具有不同的带宽要求，并且在某些实施例中，一个或多个VM的带宽要求可包含不同的（或相同的）上行链路和下行链路带宽要求。

在本发明的一实施例中，利用网络资源抽象模型来表示云网络中的要求和参与者，其中云提供商向消费者提供虚拟网络服务用于相互连接分派给这些消费者的VM。消费者不需要意识到云网络的潜在物理基础设施，而是同意高级服务等级协定（SLA）（它规定它们将享有什么等级的服务）。为此目的，每个租户可以在拓扑连接性、安全策略、要求的带宽等方面来规定它们的网络服务的要求。

特别地，在此虚拟网络服务模型中，租户规定每个的对应带宽需求作为（0≤i<N，其中N是由租户请求的VM的总数量）。在本发明的一实施例中，虚拟网络服务模型利用带宽请求的“软管”模型，其中每个规定特定VM将在任何一个时刻发送到网络和/或在任何一个时刻接收自网络的最大总带宽量。然而，在其它实施例中，可利用其它带宽模块，例如通过定义VM的特定对或群组之间的带宽要求（例如，最大要求的带宽、最小要求的带宽）。

给定来自租户请求的带宽请求<>，在一实施例中的模型在租户正在请求非阻塞虚拟网络基础设施来提供网络服务的假设下操作，即，在分配给租户的虚拟网络中应该没有超额订购。虽然此假设要求来自云提供商的更多网络资源，此配置向租户提供更好的服务（因为它模拟其中所有VM连接到非阻塞虚拟交换机的场景）。然而，本领域技术人员公知的是此模型可以容易地扩展到允许超额订购的虚拟网络服务。

此抽象模型提供许多优势。第一，模型提供规格的便利性，因为每个VM只需要规定一个对内和对外速率（可能非对称）。第二，模型提供灵活性，因为至和自给定VM的数据可以任意地分布在其它端点上（假定聚合符合VM角色）。第三，模型允许复用增益，由于统计的复用增益，因为VM率可以小于VM对的集合所要求的聚合率。而且，模型允许特性化的便利性，因为“软管”要求更易于描绘特征，因为个别来源目的地业务中的统计差异由聚合而变得平滑。

给定网络服务抽象模型，本发明的实施例构造包含表示网络中的网络装置和VM位置的节点的多个生成树。表示通信链路的树的每个边缘与表示必须保留在链路上的最小带宽量的计算的带宽值的关联。计算的带宽值是通过分析可潜在流过通信链路的带宽量基于VM的输入和输出带宽要求来确定。多个生成树中的每个包含不同的节点作为根节点，并且构造每个树使得那个树的计算的带宽量总和最小化。每个树的加权距离值基于树中的每个VM之间的计算的带宽量和距离来计算。具有最小加权距离值的树被选择为具有最佳表示属于那个租户的VM的多租户云网络中的最小网络带宽分配（和转发路径）的计算的带宽量的树。

图1图示根据本发明的一个实施例的包含虚拟机和规定的带宽要求的示例云计算网络拓扑。图1包含多租户云网络100，云网络100包含在一个或多个主机计算装置的集合（未图示）上执行的三个虚拟机（102、103、104）。为了本公开的目的，VM可每个在不同的主机计算装置上执行，或一些或所有VM可在共享的主机计算装置上执行。图1的VM102、103、104使用多个通信链路130A-130K和网络装置‘A’-‘G’（111、112、113、114、115、115、116）来连接。在一些实施例中，每个网络装置111-117是单独的物理装置并且每个通信链路130A-130K是单独的物理通信链路（例如，网络线缆（例如，类别5（类5）线缆）、双绞线缆、同轴电缆、铜导线线缆、其它电线缆、光线缆、电源线等），但是在其它实施例中网络装置111-117和/或通信链路130A-130K中的一个或多个是虚拟的（例如，虚拟网络装置、虚拟通信链路）。

与每个VM关联的带宽请求（例如，120）图示为接近直接耦合到虚拟机102-104的每个通信链路（130A、130B、130K）。在本实施例中，每个带宽请求120包含表示第一VM101将在任何时间点处传送到多租户云网络100的最大业务量的要求的输出带宽量121，并且也包含表示第一VM101将在任何时间点处传送到多租户云网络100的最大业务量的要求的输入带宽量122。在这个描绘的实施例中，第一VM101的输出带宽量121和输入带宽量122相同（每秒1千兆位（Gbps））。在一些实施例中（以及图1的可能描绘的实施例），每个输出和输入带宽量121、122可不同，并且在一些实施例中，只有一个带宽量被用作输入和输出带宽量121、122。在此示例中，第一VM101被提供有1Gbps的带宽用于每个输入和输出业务（或下游/上游、下载/上载、传送/接收、进入/外出等）。类似地，第二VM102和第三VM103每个都提供有2Gbps的带宽用于每个输入和输出业务。在此描述中，除非以其它方式指示，系统确定关于不直接连接到VM的通信链路（即，通信链路130C-130J）的带宽分配。然而，在某些实施例中，这些通信链路130A、130B、130K也包含作为要求保留的带宽，当多个VM在每个主机计算装置上执行并且可共享一个通信链路（例如，130K）时这尤其有用。

图2图示根据本发明的一个实施例的使用图1的多租户云网络100的示例云计算网络拓扑的用于带宽分配的基于原生最短路径的方法。然而，虽然这样的基于原生最短路径的方法将确定提供VM的足够带宽的带宽量，但是此方法频繁地导致VM的带宽的过度供应。因此，此基于原生最短路径的方法将“浪费”可用的带宽，减少可服务的租户的数量。

用于确定在这些通信链路130C-130上保留的带宽的一个方法是应用已知的最短路径算法（例如，Dijkstra算法）来计算每个VM101-103之间的最短路径。例如，第一VM101与第二VM102之间的最短路径要求三“跳”并且流过网络装置A111、网络装置E115和网络装置F116。（通过多租户云网络100的其它路径要求多于三跳）。然后，此路径130F、130I上的每个通信链路将具有保留的带宽量，等于以下的最大值：

=min（第二VM的要求的输出带宽、第一VM的要求的输入带宽）

以及

=min（第一VM的要求的输出带宽、第二VM的要求的输入带宽）

在描绘的示例中，每个链路将具有保留的1Gbps，这是以下的最大值：

=min（2Gbps，1Gbps）=1Gbps

以及

=min（1Gbps，2Gbps）=1Gbps

因此，最大（）=最大（1Gbps，1Gbps）=1Gbps；并且1Gbps将保留在链路130B和链路130I上用于第一VM101与第二VM102之间的连接。

类似地，在第二VM102与第三VM103之间计算最短路径，它穿过网络装置A111、网络装置B112和网络装置C113，并且因此此路径类似地要求三跳。使用上述的相同带宽保留计算，链路130C和130D都将有2Gbps保留用于第二VM102与第三VM103之间的连接。最后，第三VM103与第一VM101之间的最短路径将计算为流过网络装置C113、网络装置G117和网络装置F116，也是三跳。因此，1Gbps的带宽将分配在链路130G和130J上用于第三VM103与第一VM101之间的连接。在此点上，云网络运营商将配置网络100来利用这三个VM101-103之间的这些路径，并且将在那些链路上保留这些相应带宽量来确保运营商满足租户与运营商之间的SLA。

从云网络运营商的观点，基于原生最短路径的此解决方案205要求将8Gbps的总带宽205分配/保留用于租户的这三个VM，因为来自通信链路130C-130J的带宽总和等于2+2+1+1+1+1=8Gbps。虽然此解决方案为租户的VM提供必要的网络带宽，但是它不是最佳的，因为其它配置将导致更小的整个带宽量保留在网络中。

替代地，存在多租户云网络100的最佳分配解决方案215，它要求云网络运营商只保留总共6Gbps的带宽来满足SLA并且根据每个VM的要求的带宽量来服务三个VM101-103。例如，最佳分配解决方案215替代地能够利用通信链路130E和130H，并且共享链路130C和130D的已经保留的带宽，而不是具有第一VM101与其它两个VM102-103中的每个之间的两个各别的保留路径。此优化变为可能的，因为要求第一VM101可以在任何时刻只接收总共1Gbps；因此，由于第一VM101无法同时地从第二VM102和第三VM103接收1Gbps，在网络的两个单独部分（例如，链路130F和130I；以及同样的链路130G和130J）上为第一VM101保留带宽是不必要的和低效的。类似地，因为第二VM102可以一次只接收2Gbps，所以第二VM102无法同时地从第三VM103接收2Gbps并且从第一VM101接收1Gbps。通过利用此事实，最佳分配解决方案215可以利用共享通信链路来满足SLA并且减少网络100中的保留的总带宽量。

因此，在最佳分配解决方案215中，第二VM102与第三VM103之间的路径维持相同，但是包括第一VM101的路径将全部经过通信链路130E和130H。虽然从第二VM102和第三VM103到第一VM101的这些路径利用比基于原生最短路径的方法105更大的跳数（例如，每个四跳而不是每个三跳），网络100中的保留的总带宽量从8Gbps减少到6Gbps，如在计算220中图示的。

图3图示根据本发明的一个实施例的用于确定在网络链路上保留的要求的带宽的表示生成树300和等式330的构造。根据本发明的实施例，系统配置为通过构造多个这样的生成树300并且为那些树中的每个中的每个链路计算要求的保留的带宽量来确定最佳带宽分配215。利用此信息，可标识“最佳”树，它映射到给定租户的带宽要求的最佳网络分配策略。在本发明的各实施例中，此系统可以计算所有可能的网络拓扑中的最佳分配策略，包含树、胖树、B-Cube、D-Cell等。另外，系统不要求在网络中“重新定位”VM的能力，并且因此与分派的VM位置一起工作来计算具有那些VM位置的系统的最佳策略。

在一实施例中，将网络建模为图G=（V，E），其中V是节点的集合并且E是节点之间的双向链路的集合。在本发明的一实施例中，节点是网络中的网络装置和网络中的VM中的一个或多个。为了此论述的目的，节点包含网络装置和VM。

每个链路（i，j）具有两个方向中的关联的带宽容量。从节点i到节点j的容量是由指代并且从节点j到节点i的容量（在相反的方向中）是由指代。租户规定VM的集合P?V以及它们的相应带宽要求和。

系统配置为搜索连接P中的所有VM的最佳树T。系统利用树结构，因为它是可扩展的以简化路由和恢复。而且，树结构允许由链路连接的VM的任何两个集合之间的业务共享在链路上保留的带宽。因此，在链路上保留的带宽等于由链路连接的VM的两个集合之间的最大可能的聚合业务。

为搜索最佳树，系统首先考虑，对于互连P中的所有VM的树T，从树T移除链路的影响。因此，如果在那个树T中移除特定链路（i，j），则树被划分成两个部分：和，前者包含在移除链路（i，j）之后仍然连接到节点i的VM的集合，并且后者包含在移除链路（i，j）之后仍然连接到节点j的VM的集合。在图3中在生成树300中描绘此分析，其中边缘314表示正在“移除”的节点i310与节点j312之间的链路（i，j）。在此场景中，表示在移除链路（i，j）之后仍然连接到节点i的VM的集合的包含节点301、302和303（由316图示）。类似地，表示在移除链路（i，j）之后仍然连接到节点j的VM的集合的包含节点304、305、306、307和308（由318图示）。

使用此过程，基于从节点i到节点j的业务流的需要在此“移除的”链路（i，j）上保留的带宽为：

，其在图3中表示为330。公式330是适当的，因为只有穿过从节点i到节点j的链路（i，j）的业务是来源于中的端点并且指向中的端点的业务。

因此，为树T保留的总带宽为：

。

从高级，此过程可更正式地如下定义：给定VM的集合P以及它们的进入和外出带宽，计算树T，它的叶子是P中的节点并且它的最小。

在图3的描绘的实施例中，假设节点301-308中的每一个包含2Gbps的输入带宽量320和4Gbps的输出带宽量322，则将计算332为节点301-303的输出带宽量（或4+4+4Gbps=12Gbps）和节点304-308的输入带宽量（或2+2+2+2+2Gbps=10Gbps）的最小值，即是10Gbps。因此，节点i310配置为能够在链路314上传送10Gbps的业务到节点j312用于这些VM。类似地，将计算334为节点304-308的输出带宽量（或4+4+4+4+4Gbps=20Gbps）和节点301-303的输入带宽量（或2+2+2Gbps=6Gbps）的最小值，即是6Gbps。因此，节点j312配置为能够在链路314上传送6Gbps的业务到节点i310用于这些VM。在一实施例中，和的最小值用于指示多少带宽必须保留在由边缘（i，j）表示的链路314上。

在本发明的一实施例中，除需要在每个树中保留的带宽量以外，在解决方案中系统还考虑路径长度。在这样的实施例中，对于树T和T中的节点v，T中的节点v的加权距离度量（见图4的402）定义为：

其中表示节点v与指代为节点k的VM之间的保留的带宽和，并且其中d（v，k）是树T中的从节点k到节点v的路径长度（例如，树中的跳数）。

图4图示根据本发明的一个实施例的加权距离值公式402和最佳网络带宽供应算法400，用于确定并且分配最佳网络带宽量来服务租户的VM。在本发明的一实施例中，算法400为图中的每个节点v（例如，网络装置和/或VM）计算树根在那个节点v处的宽度优先生成树，它在树根在节点v处的所有可能的树之间具有最小的可能值。在本实施例中，（所有这样的构造的树中的）具有最小值的构造的宽度优先生成树被选择为表示最佳带宽分配的树。

在图4中描绘的实施例中，算法包含在行140处的名为Connect_AllVMs（G，B）的过程，它利用来自图G（包含如上所述的节点和边缘）的信息和VM的带宽要求的集合B。

在行412处的“对于每个”循环的最外层指示为图G中的每个节点执行以下的指令（构造树根在节点v处的宽度优先生成树）。在414处，空树被设置为包含当前节点v作为根节点。在416处，宣布队列作为包含节点v的集合。

在416处，执行“while”循环而队列非空。首先，在420处，取回队列中的第一节点并且被认为是节点k。在422处，执行另一“对于每个”循环，遍历图中的连接到节点k的每个边缘。在424处，如果连接节点k到节点j的当前边缘不在树中，则发生三个动作。首先，在426处，将边缘（k，j）添加到树。接着，在428处，带宽值与边缘关联。在一实施例中，此带宽值是如上所述的和的最小值。接着，在430处，将在边缘（k，j）的另一端的节点j添加到队列的前列。在432处，三个动作已经完成，并且在434处的检查边缘（k，j）的过程已经完成，因此过程遍历步骤424-434用于连接到节点k的每个其它边缘。在436处，“while”循环完成，并且图G中的所有节点已经被处理并且现在存在于树中。在此点上，在本发明的一实施例中，在438处为此构造树计算加权距离度量值（见402和以上论述）。如果此加权距离度量值小于早先构造的树（即，来自在步骤412处的“对于每个”循环的早先迭代）的任何其它计算的加权距离度量值，则将到当前“最佳得分”树的指针维持为v’。最后在440处，过程完成，并且由v’标识的树是具有表示最佳带宽分配的网络带宽分配的树。

图5图示根据本发明的一个实施例的使用图1的第二虚拟机102作为树中的根节点以及图1的网络地形的宽度优先生成树的构造500。此图图示来自线路414-438的带宽供应算法400的一个执行；因此，给定选择的节点，构造宽度优先生成树并且计算加权距离值402。在此描绘中，表示VM的节点具有厚边界；表示网络装置的节点具有薄边界。另外，虽然在本实施例中计算为表示链路的每个边缘保留的带宽而将每个边缘添加到树（见图4的步骤424-432），但是为了简洁的目的，未图示这些保留的带宽。

树的宽度优先构造的工作原理是使用逐级方式添加节点到树。给定根节点（例如，在层0处），在“层1”中添加直接连接到根节点的所有节点。然后，添加直接连接到“层1”的节点的所有节点作为“层2”，等等。因此，在树中依次构造一层。宽度优先树遍历不同于深度优先树遍历，深度优先树遍历是在访问任何特定层中的其它“同级”节点之前通过越来越深移动到树（即，移动到更深层）来操作。

在502处，首先选择的节点（此处表示VM102）被添加到树（）。在504处，第一边缘和节点111被添加到树。如在图1中呈现的，VM102只直接连接到一个其它VM或网络装置（即，网络装置A111），并且在其处理期间，将网络装置B112和E115的节点添加到要接着处理的队列，因为这些网络装置112、115直接连接到网络装置A111。

在506和508处，将这些节点112和115添加到树。继续宽度优先方式，在步骤510、512和514中添加节点113、114和116。过程继续在516、518和520处，通过分别添加表示第三VM103、网络装置G117和第一VM101的节点。在此点上，图中的所有节点已经被添加到树中，并且每个链路包含如上所述的计算的带宽值。此构造树包含表示第二VM102的根节点534、多个节点（例如，见532）和多个边缘（例如，见530）。另外，可在节点之间计算距离538，它在一实施例中是树中的节点之间的跳数。

在522处，显示计算的带宽值，并且如上所述使用根节点作为节点v来计算加权距离值402。例如，在图5所描绘的实施例中，加权距离值402可等于：

因此，此构造树的加权距离值402是“52”。如果此加权距离值402小于每个其它这样的构造树（使用图的其它节点作为根节点）的加权距离值402，则此树将表示服务VM101-103的集合的最佳带宽分配数量和相应链路。

在此示例中，加权距离值402的计算包含使用直接连接表示VM的节点（例如，101、102、103的节点）和另一节点的链路的带宽值。在一些实施例中，从计算中排除这些带宽值。

图6图示根据本发明的一个实施例的利用最佳网络带宽分配系统的多租户云网络100的框图。在这个图示的实施例中，多租户云网络100包含图1的网络装置A-G111-117以及三个VM101-103。三个VM102、103、101每个执行在相应计算装置620、622、624上。也描绘服务器终端站604，它可存在于多租户云网络100的内部或外部。

在圆圈‘1’处，租户601的计算装置602传送用于计算和网络资源644的请求到服务器终端站604。在一实施例中，用于计算和网络资源644的请求包含指示由租户请求的虚拟机特性642的一个或多个消息以及指示那些虚拟机的带宽要求640的一个或多个消息。在不同的实施例中，VM特性642和带宽要求640是传送在一个消息内，但是在其它实施例中，此数据是传送在使用一个或多个消息的各种群组中。例如，VM的特性的集合以及那个VM的关联的带宽要求可包含在一个消息内。

计算和网络资源的请求644到达服务器终端站604的一个或多个网络接口616的集合。网络接口的集合（它们允许服务器终端站604传送并且接收网络业务）耦合到一个或多个处理器的集合606、带宽分配模块608、并且可选地耦合到虚拟存储器分配模块614。

在圆圈‘2’处，用于计算和网络资源644（或其部分）的请求提供到带宽分配模块608的树数据结构（TDS）生成模块610。（在一些实施例中，带宽分配模块608位于多租户云网络100的一个主机计算装置（例如，计算装置624）内。

使用计算和网络资源644的请求和多租户云网络100的地形和能力的表示中的一个或多个，TDS生成模块610构造表示不同的带宽分配方案（可能满足用于计算和网络资源644的请求的带宽要求）的多个树数据结构。在圆圈‘3’处，带宽分配模块608的树数据结构选择模块612选择多个构造的TDS中的一个TDS来允许用于计算和网络资源644的请求的带宽要求满足在多租户云网络100中使用最小的分配的带宽量。在一实施例中，TDS生成模块610和TDS选择模块612实现图4的带宽供应算法400。

在圆圈‘4’处，虚拟机分配模块614（位于服务器终端站604或多租户云网络100的主机计算装置620、622、624中的一个），使用选择的TDS（或基于来自选择的TDS的值的数据，例如但不限于通信链路标识符和/或网络装置标识符）可操作为配置多租户云网络100来利用VM的确定的分配的带宽量。在一实施例中，VM分配模块614可操作为在网络装置111-117中的一个或多个中安装转发信息来使VM101-103的业务传送在由选择的TDS标识的路由上，并且另外可操作为使网络装置111-117中的一个或多个在一个或多个通信链路（例如，在特定物理网络接口处）上“保留”或分配带宽用于VM101-103的业务。在一些实施例中，VM分配模块614另外可操作为使根据计算和网络资源644的请求在一个或多个计算装置620、622、624上初始化VM101-103。在这些实施例中的一些中，VM分配模块614包括VM管理程序。

图7图示根据本发明的一个实施例的用于基于多个VM的带宽要求的集合来确定多租户云网络中的多个虚拟机的多个通信链路上的网络带宽的最佳分配的流程700。

将参考其它图的示范性实施例来描述此操作和其它流程图。然而，应该理解：可以由不同于参考这些其它图讨论的那些的本发明的实施例来执行流程图的操作，并且参考这些其它图讨论的本发明的实施例可以执行不同于参考流程图讨论的那些的操作。

在710处，流程700包含由计算装置生成多个树数据结构。多个TDS中的每个TDS包含表示多个VM和在多租户云网络中转发业务的多个网络装置的多个节点。多个TDS中的每个TDS还包含表示多个通信链路中的至少一些通信链路的多个边缘。多个边缘中的每个边缘包含指示在由边缘表示的通信链路上保留的带宽量的计算的带宽值。计算的带宽值基于带宽要求的集合。在一实施例中，多个TDS中的每个使用宽度优先算法来生成的生成树。在一实施例中，带宽要求的集合包含：对于多个VM中的每个VM，提供给VM所要求的输出带宽指示VM必须能够传送的业务率。在一实施例中，带宽要求的集合包含：对于多个VM中的每个VM，提供给VM所要求的输入带宽指示VM必须能够接收的业务率。

在一实施例中，TDS中的特定边缘的计算的带宽值是两个值的最小值。第一值是多个VM中的具有一个或多个节点的第一划分中的代表节点的那些VM要求的带宽要求的集合的所有输出带宽的总和，其中节点的第一划分是当从生成树移除边缘时保持连接的生成树中的多个节点中的一个或多个节点的第一集合。第二值是多个VM中的具有一个或多个节点的第二划分中的代表节点的那些VM要求的带宽要求的集合的所有输入带宽的总和，其中节点的第二划分是当从生成树移除边缘时保持连接的生成树中的多个节点中的一个或多个节点的第二集合。

在720处，流程700包含由计算装置生成多个TDS中的每个TDS的加权距离值。此生成基于（1）根节点与表示VM的每个其它节点之间的TDS中的距离，以及（2）根节点与表示VM的每个其它节点之间的TDS中的计算的带宽值。在730处，流程700包含由计算装置选择多个TDS中的具有最小加权距离值的TDS作为具有表示网络带宽的最佳分配的计算的带宽值的TDS。

图8图示根据本发明的一个实施例的用于确定并且分配网络带宽要求的在云提供商的服务器终端站中执行的流程800。

在810处，流程800包含从租户的计算装置接收对于多租户云网络中的计算和网络资源的请求。请求包含标识要分配给租户的多个VM的特性（例如，其中VM应该执行的多租户云网络中的位置、VM的存储要求、VM的处理要求、VM的存储器要求等）并且还标识多个VM的带宽要求的集合的一个或多个消息的集合。

然后，在700处，流程800包含基于多个VM的带宽要求的集合来确定多租户云网络中的多个VM的多个通信链路上的网络带宽的最佳分配。在一实施例中，框700表示图7的步骤710、720和730。

在820处，流程800包含在多租户云网络中为多个VM分配多个其它计算装置上的资源。在一实施例中，多个VM中的每个执行在单独的计算装置上，但是在其它实施例中多个VM中的两个或者更多执行在单个计算装置上。在一些实施例中，有属于其它租户的一个或多个其它VM执行在其它计算装置中的一个或多个上。

在830处，流程800包含根据标识的TDS的计算的带宽值来分配多租户云网络中的带宽资源。在一实施例中，步骤820和830组合到一个步骤中并且可用一个动作来实现。

虽然图中的流程图示出由本发明的某些实施例执行的操作的特定次序，但是应该理解这样的次序是示范性的（例如，备选实施例可以用不同的次序来执行操作、组合某些操作、重叠某些操作等）。

虽然已经在若干实施例的方面描述本发明，但是本领域技术人员将认识到本发明不限于描述的实施例，可以用在所附的权利要求的精神和范围内的修改和变更来实践本发明。因此，描述被视为说明性的而不是限制性的。