在虚拟网络中没有先验知识的情况下对数据流控制许可并分配资源的方法

摘要

一种用于在网络(1)中在没有任何先验知识的情况下控制许可并分配资源的方法，所述网络(1)被虚拟化以包括一个专用于具有最严格QoS约束级别的超级虚拟网络(2)和至少一个其他虚拟网络(3)，所述方法包括以下步骤：-当流(6)到达时，确定所述超级虚拟网络(2)上的第一路径(9)，-通过分析所述流(6)的前N个分组(11)而确定所述流(6)的QoS级别，-经所述第一路径(9)传输所述流(6)的所述前N个分组(11)，-确定专用于所述流(6)的所确定的QoS级的虚拟网络(3)上的第二路径(10)，-从第N+1个分组开始经所述第二路径(10)传输所述流(6)的分组(12)。

说明书

技术领域

本发明的技术领域是通信网络，具体地说是自主的自管理和虚拟化网 络。本发明涉及网络边缘或边界节点处的业务控制，并解决在流粒度级别 而不是在分组级别上定义的网络操作。流是通过服务质量QoS，即延迟约 束或带宽/吞吐量约束方面的相同特性相关的一系列分组。流的特征在于源 地址、目的地地址、源端口、目的地端口、协议以及时间相关性。在给定 时刻，共享所有这些参数的分组属于同一个流。基于这些参数，可以使各 流分离。

背景技术

电信网络向着自主的自管理和虚拟化基础设施发展。此类“下一代” 数据通信网络需要重新考虑某些网络功能，其中包括用户-网络接口处的业 务控制。值得注意的是，随着流取代分组并成为下一代网络的基本单位， 有利地在流粒度上定义诸如业务控制之类的网络操作。

在自主和自管理的数据通信系统内部，无法依赖于关于入站业务流的 先验知识。也就是说，此类系统在没有显式用户-网络信令的情况下工作。

在虚拟化网络环境内，链路和节点资源被虚拟化以便为通过特定QoS 约束表征的应用级别创建定制虚拟网络(VN)。

在此类上下文中，必须按照服务的级别或等价地按照虚拟网络执行业 务控制。

控制未知或未声明的业务流，即不知道其先验信息的流，对于许可控 制和资源分配而言极具挑战性，因为它们没有任何关于流的性质(例如， 应用的特性、类型)的先验信息。

“运行中(on the fly)”业务识别和分级过程是公知的并可被部署在 用户-网络接口处，即，部署在网络的边界节点处，以便表征入站流。快速 业务分级方法通常需要分析来自流的前N个分组，N约等于4至10个分 组。在分离流之后，业务识别的一个可能原则是例如测量流的最先分组的 大小。由于所述最先分组包含与流相关的协议信息，所以它们的大小指示 了流的应用，并且应用指示了级别。例如，参见ACM CoNext 2006的会 议录中L.Bernaille、R.Texeira、K.Salamatian的“Early application  identification”。

具有虚拟化资源的数据通信系统中的未声明业务流的流控制问题产生 了可被分为两个级别的问题。

在许可控制级别：许可控制负责决定是接受还是拒绝流。当流尚未被 识别和分级时，来自流的前N个分组的许可控制产生了第一个问题。当已 确定流的分级时，流的第N+1个分组和后续分组的许可控制产生了第二个 问题。

在资源分配级别：资源分配负责分配资源以便传输已接受的流。由于 必须在知道新的入站流的特性之前将资源分配给该流而产生了问题。

关于最佳流控制存在若干现有技术工作。例如，参见：

-P.Key，L.Massoulié的“Control of communication networks： welfare maximization and multipath transfers”，Philosophical  Transactions of the Royal Society，366(1872)，2008，

-P.Key，L.Massoulié，D.Towsley的“Path Selection and Multipath  Congestion Control”，INFOCOM 2007会议录，或

-M.Chiang，S.H.Low，A.R.Calderbank，J.C.Doyle的“Layering as optimization decomposition：A mathematical theory of network  architectures”，IEEE 会议录，卷95，第1期，第255-312页，2007年1 月。

某些现有技术工作甚至有益于网络虚拟化。例如，参见：

-M.Yu，Y.Yi，J.Rexford以及M.Chiang的“Rethinking virtual  network embedding：Substrate support for path splitting and migration”， ACM SIGCOMM Computer Communications Review会议录，2008年4 月，可从http://www.cs.princeton.edu/～jrex/papers/VNembed.pdf处获得，

-Y.Zhu，M.Ammar的“Algorithms for assigning substrate network  resources to virtual network components”，INFOCOM 2006会议录。

但是，所有这些研究都依赖于流的显式表征并因而依赖于流级别的先 验知识。因此，它们不适于未声明的流的在线分级。

一种在流的在线分级的情况下实现许可控制和资源分配的现有解决方 案主要包括存储来自流的前N个分组，直到分级过程结束，即，直到接收 到前N个分组。但是，尽管此解决方案代表一种“防止”网络的错误决策 的良好方法，但是其展现了若干使其不适合于实际实现的问题。某些最重 要的问题是：在将来自流的前N个分组释放到网络中之前，所述前N个分 组的存储：

-增加了附加延迟和延迟变化，对于恒定比特率和低比特率流尤为如 此。对于诸如VoIP之类的产生低比特率流的延迟敏感的应用而言，此问 题可以很严重，

-使得系统进行非工作保存并因此浪费了资源，

-更改了业务简档：此类方法增加了业务突发性，或者甚至在更坏的 情况下，使得业务具有突发性。这可导致网络核心的拥塞。其解释非常简 单而直观：设想经由一个核心路由器互连的数个边界路由器。边界路由器 处的两个许可控件可以变得“同步”，因为它们同时向核心路由器突然发 出N个分组。

在线分级是朝向自主网络发展的重要问题。因此，包含及适于在线分 级的流控制是自主网络中要解决的重要问题，其将自适应未声明的入站流。

在此要解决的技术问题是在具有虚拟化资源和多个服务级别的自管理 数据通信系统中设计一种流控制过程，其中用户-网络接口没有关于新的入 站业务流的特性的先验知识。

本发明解决了此问题。

发明内容

本发明的目标是一种用于在数据通信网络中在没有关于入站业务流的 先验知识的情况下控制对所述入站业务流的许可并将资源分配给所述入站 业务流的方法，所述数据通信网络被虚拟化以包括定制虚拟网络，所述定 制虚拟网络每个专用于至少一个特定QoS级别，所述定制虚拟网络包括一 个专用于具有最严格QoS约束级别的超级虚拟网络和至少一个其他虚拟网 络，所述方法包括以下步骤：

-当打算在入口节点与出口节点之间传送的流到达时，确定所述超级 虚拟网络上从所述入口节点到所述出口节点的第一路径，

-通过分析所述流的前N个分组而确定所述流的QoS级，

-在所述超级虚拟网络经所述第一路径传输所述流的所述前N个分 组，

-确定专用于所述流的所确定的QoS级别的虚拟网络，

-如果所确定的虚拟网络不同于所述超级虚拟网络，则确定所确定的 虚拟网络上从所述入口节点到所述出口节点的第二路径，或者

-如果所确定的虚拟网络等于所述超级虚拟网络，则确定等于所述第 一路径的第二路径，

-从第N+1个分组开始在所述第二路径上传输所述流的分组。

根据本发明的另一特征，确定第一路径的步骤包括检查所述第一路径 传输所述前N个分组的可用性的步骤。

根据本发明的另一特征，如果未检查可用性，则确定第一路径的步骤 之后的步骤被替换为拒绝所述流的步骤。

根据本发明的另一特征，确定第二路径的步骤包括检查所述第二路径 从第N+1个分组开始传输所述流的分组的可用性的步骤。

根据本发明的另一特征，如果未检查可用性，则确定第二路径的步骤 之后的步骤被替换为拒绝所述流的步骤。

根据本发明的另一特征，如果在确定第二路径的步骤中未检查可用性， 则将该步骤替换为在另一虚拟网络上确定第二路径的步骤。

根据本发明的另一特征，所述另一虚拟网络是专用于具有较宽松QoS 约束级别的虚拟网络。

根据本发明的另一特征，可用性的检查是确切性的或概率性的。

根据本发明的另一特征，当所述流结束时，停止或取消在所述第一路 径上传输的步骤之后的步骤。

附图说明

从以下根据附图给出的详细示例性说明，本发明的其他特征、细节和 优点将变得更加显而易见，其中：

图1是包括两个虚拟网络并传输未声明的流的虚拟化网络的示意图。

具体实施方式

根据图1，其中表示了物理网络1。所述网络1示例性地包括六个节点 A-F。部分地或全部地使用物理节点和链路在所述物理网络1上部署至少 两个虚拟网络2、3。例如，在此示出了两个虚拟网络2、3。第一虚拟网络 2(VN1)包括分别在物理节点A、C、D、E和F上实现的虚拟节点A”、 C”、D”、E”和F”。第二虚拟网络3(VN2)包括分别在物理节点A、B、 D和E上实现的虚拟节点A”、B”、D”和E”。在物理链路上实现虚拟链 路。有时，数个虚拟链路可共享一个物理链路。例如，在虚拟链路A”-E” (4)与虚拟链路A’-E’(5)之间共享物理链路A-E，如图底部的放大详 图所示。

每个虚拟网络2、3于是可专用于至少一个特定QoS级别。所述多个 虚拟网络包括一个专用于具有最严格QoS约束级别的超级虚拟网络2。除 了所述超级虚拟网络以外，可以找到若干其他虚拟网络3。

出于例示目的，考虑VN1(2)是超级虚拟网络，并且VN2(3)是专 用于另一QoS级别的一个其他虚拟网络3。例如，超级虚拟网络2可以针 对延迟敏感应用进行优化，而其他虚拟网络3可以针对吞吐量应用进行优 化。这种资源虚拟化方式简单地意味着，虚拟链路的拓扑和带宽分配是使 用VN1的延迟和VN2的带宽利用率，即吞吐量，作为效用函数对网络进 行多路径路由优化的结果。值得注意的是，延迟敏感和吞吐量敏感的应用 属于不同的QoS级别。此外，显然可以存在两个以上的虚拟网络。

根据本发明的方法关注控制对入站业务流6的许可和将资源分配给入 站业务流6的问题。多数现有技术许可控制器和/或资源分配器都基于关于 流6的先验知识。通常，由流6的用户/发送方提供关于流6的信息。这使 得必须将所述信息引入网络管理系统，尤其是必须在用户与负责许可控制/ 资源分配的节点，即流6通过其进入网络的边界节点7，之间发送信号。 本发明的一个重要特征在于，为了提供自主的自管理网络管理系统，避免 了发送信号并且通过在“运行中”分析到达边界节点7的流而自动获得关 于入站流6的信息。任何先验知识都被自动在线收集的信息所取代。

本发明的主要概念是在入站流6的分级之前临时接受入站流6。所述 分级需要分析入站流6的前N个分组11。在流6的级别未知期间，即，直 到第N个分组到达之前，流6必须缺省地被视为属于最高优先级别。因此 在开始时，流6被视为具有最高优先级并如此在专用于最高优先级级别的 虚拟网络，即超级虚拟网络2上传输。在确定了流6的级别之后，可以进 行重新路由以便按照流6的真实级别处理流6。

为了实现所述概念，所述方法包括以下步骤。

当打算在入口节点7与出口节点8之间传送的流6到达时，流6首先 被分配最高优先级。然后确定从入口节点7到出口节点8的第一路径9。 由于优先级处于最高级别，所以在专用于最高优先级的超级虚拟网络2上 确定所述第一路径9。

在流6的最先分组11到达时，分析所述最先分组11以便确定它们的 应用以及因此确定流6的对应QoS级别。需要给定数量(N)的分组以便 确定QoS级别。在最佳处理中，N通常在4与10之间。

同时，直到确定级别之前，即，直到第N个分组到达之前，优先级仍 被视为最高，对应于最严格的QoS约束。因此，跨所述超级虚拟网络2在 先前确定的第一路径9上传输流6的前N个分组。

在一个优选实施例中，为了不延迟分组的传输(这将修改流6的简档)， 两个先前的步骤将被交错。换言之，每个分组到达，被分析或出于分析目 的而被复制，并被连续传输。通过此操作，每个分组的处理时间将是相同 的。

但是，相对于整体处理而言，分析时间可被忽略。

基于流6的所确定的QoS级别，可以确定专用于流6的所确定的QoS 级别的虚拟网络3。

然后可以发生两种情况。第一，虚拟网络3不同于超级虚拟网络2。 然后可以确定所确定的虚拟网络3上从入口节点7到出口节点8的第二路 径10。可以然后应用重新路由以便减缓超级虚拟网络的压力。

第二，虚拟网络3被确定为与超级虚拟网络2相同。也就是说，流6 实际上属于与最严格的QoS约束对应的QoS级别。在此情况下，可以在 超级虚拟网络2上继续传输。然后可以得到与第一路径9相等的第二路径 10。

然后可以在第二路径10上从第N+1个分组开始传输流6的其余分组 12。

由于许可控制和资源分配在两个连续步骤中完成，因此也可以在分别 确定第一路径9和第二路径10时在两个步骤中应用可用性检查。

在确定第一路径9时，可以应用可用性检查，以便第一路径9拥有足 够的资源来传输至少前N个分组。

如果不能检查所述第一可用性，即不能在入口节点7与出口节点8之 间发现能够在超级虚拟网络2上传输流6的前N个分组11的路径，则所 述方法以拒绝入站流6的步骤结束。换言之，后来的步骤，即确定第一路 径9的步骤之后的步骤，被替换为拒绝步骤。

在确定第二路径10时，可以应用可用性检查，以便第二路径10拥有 足够的资源以在新确定的虚拟网络3上从第N+1个分组开始传输其余分组 12。

如果不能检查所述第二可用性，即不能在入口节点7与出口节点8之 间发现能够在新确定的虚拟网络3上从第N+1个分组开始传输流6的其余 分组12的路径，则所述方法以拒绝入站流6的步骤结束。换言之，后来的 步骤，即确定第二路径10的步骤之后的步骤，被替换为拒绝步骤。

备选地，如果在确定第二路径10的步骤中未检查可用性，则可以在另 一虚拟网络上执行新的尝试。换言之，所述方法在数个虚拟网络上重复， 以便确定提供可用性的第二路径10。

优选地，在专用于严格性较低的QoS约束级别的虚拟网络上应用新的 尝试。所述方法然后可以遍历按照降低的QoS约束严格性排序的虚拟网络 列表，直到一个虚拟网络可用为止。否则，如果没有虚拟网络可以提供可 用的路径，则最后可以拒绝流6。

可以确切地执行先前实施例中使用的若干可用性检查中的每个可用性 检查。也就是说，当且仅当适合流6的确切所需资源将在需要的时间和需 要的位置可用时才检查可用性。

还可以以概率性的方式执行先前实施例中使用的若干可用性检查中的 每个可用性检查。也就是说，在适合流6的所需资源显示需要时可用的概 率大于给定接受概率的情况下才检查可用性。

对本领域技术人员将显而易见的是，在流6结束时，将停止或取消在 第一路径上传输的步骤之后的步骤。

还显而易见的是，在处理前N个分组11之后，所述方法结束其对流 的操作。这是本发明的一个优点。

当流6包含的分组少于N个时，所述方法也会缩减。

对于较短的流，也称为小型流(mice)，要指出的是，可以发生两种 情况：

-流6属于最高业务级别：所述方法是正确的，因为流6被正确地视 为该级别的一部分并作为该级别的一部分被传输；

-流6不属于最高业务级别：在此情况下，所述方法将较短的流视为 “王”，即使情况并非如此。

但是，近来的业务调查显示，较小的业务流或小型流(例如，几十个 分组)代表了在诸如因特网的网络中传播的大多数业务流。然而，与因特 网业务的总量相比，它们消耗的带宽的百分比明显较小。这意味着较大的 流或大型流(elephant)消耗了总体带宽中的多数带宽，并且额外地代表 较少数量的业务流。

在此上下文中，将较短的流视为“王”对其他类型的业务流的QoS保 证具有微小影响。此外，本领域技术人员将理解，较小的流通常代表必须 以较低的延迟传输到其目的地的控制消息。

根据本发明的方法的另一优点是其可伸缩性。可以从以下事实推断出 所述可伸缩性：仅网络的边缘处的边界路由器具有许可控制机制，并且所 述机制仅对来自流6的前N个分组11执行操作。一旦流6被识别和分级， 许可控制就无需保留任何有关已接受的流的状态信息并专注于新到来的 流。

还显而易见的是，将流6从超级虚拟网络2重新路由到另一虚拟网络 3并不会干扰流6内的分组顺序。业务分离领域中的技术人员将理解，当 在多个路径间分离或路由/重新路由流6时，存在若干保证流的分组顺序的 业务分离方法。

对于此主题，可以例如参考以下文档：2008年3月，IEEE Network  Magazine，Jiayue He和Jennifer Rexford的“Towards Internet-wide  multipath routing”。