用于服务实例间周期性带宽分配的带宽利用率提升方法

1.本发明属于网络技术领域，具体为一种用于服务实例间周期性带宽分配的带宽利用率提升方法。


背景技术：

2.应用程序倾向于部署在云上，应用云原生架构以实现高可扩展性、可用性和可移植性。运营商或云提供商为租户提供计算和存储资源，租户为他们的用户部署应用程序。云上的应用通常被划分为多个微服务，微服务相互协作为用户服务。数以千计的服务实例在云原生平台上的容器中运行。
3.带宽是一项关键且受限的资源，同时影响用户体验质量和提供商的利润。现有的带宽分配算法在网络层或应用层运行，按时间周期为数据中心网络中的虚拟机分配带宽。云提供商为虚拟机分配带宽，以实现租户之间的性能隔离或高利用率。但是，租户将其应用程序以服务实例的形式部署在云上的容器中，希望充分利用购买的带宽。同一服务的服务实例共享带宽，每个实例都应该得到适当的、合理的带宽分配。
4.目前的实例间周期性带宽分配算法存在带宽利用率低的问题，在同一周期内的带宽分配值是固定值，这会导致存在实例浪费带宽或带宽不足。需要利用已有带宽分配算法的优势，提出一种能够提升实例间周期性带宽分配算法的带宽利用率的方法，以同时保证提供商的利润和用户体验质量。


技术实现要素：

5.为了克服现有实例间周期性带宽分配的带宽利用率低的问题，本发明的目的在于提供一种用于服务实例间周期性带宽分配的带宽利用率提升方法，包括相似带宽波动实例聚类算法和带宽波动方向相反实例对查找算法，能够帮助已有的周期性带宽分配算法提高带宽利用率。服务实例间周期性带宽分配的带宽利用率提升方法的基本思想是将实例周期内多余的带宽预支给其他周期内带宽不足的带宽；云服务提供商相似带宽波动实例聚类算法先将周期内带宽波动范围相似的实例聚为一类；然后用带宽波动方向相反实例对查找算法依次从每一类中寻找波动方向相反的实例对，为这样的实例对分配额外带宽，从而提高带宽利用率。
6.已有周期性带宽分配算法的基本工作方式是按周期运行，每周期开始时根据带宽分配策略(如最大最小公平)为每个服务实例分配基础带宽。本发明建立在已有周期性带宽分配算法的基础上，先由周期性带宽分配算法为每个周期内的服务实例分配基础带宽，用b
base
表示，实例i分得的基础带宽为
7.本发明的技术方案为：
8.一种用于服务实例间周期性带宽分配的带宽利用率提升方法，其步骤包括：
9.1)每周期开始时利用周期性带宽分配算法为每个服务实例分配基础带宽，为服务实例i对应的基础带宽；
10.2)将每个周期内带宽波动范围相似的服务实例聚为一类；
11.3)依次从每一类服务实例中寻找波动方向相反的服务实例对并为其分配额外带宽，作为对应服务实例下一周期的带宽。
12.进一步的，采用相似带宽波动实例聚类算法根据服务实例的波动距离对服务实例进行聚类，具体方法为：将所述周期划分为m个分段，计算每个分段内每一服务实例的带宽波动值；根据一个周期内每一服务实例在各分段的波动值生成该服务实例在该周期的实际状态，服务实例i的实际状态fi＝(f1,f2,
…
,fm)i，fu为服务实例i在分段m的波动值；然后根据一个周期内每一服务实例的实际状态f与理想状态o的欧氏距离dist(f,o)对服务实例进行聚类。
13.进一步的，所述欧氏距离服务实例的理想状态o为m个0。
14.进一步的，所述相似带宽波动实例聚类算法为mean shift聚类算法；所述mean shift聚类算法采用高斯函数作为平滑峰值函数。
15.进一步的，利用带宽波动方向相反实例对查找算法从每一类服务实例中寻找波动方向相反的服务实例对，如果两个服务实例u和v满足|fu+fv|≤v
dev
，则服务实例u和v为波动方向相反的服务实例对(u，v)；其中，fu为服务实例u的实际状态，fv为服务实例v的实际状态，v
dev
是预先设置好的偏差值，v
dev
≥0；然后将服务实例u绝对值最大的波动值max|fj|u作为服务实例u的额外带宽。
16.进一步的，为所述服务实例对中每一服务实例分配的额外带宽为该服务实例的基础带宽与该服务实例对应的额外带宽之和。
17.进一步的，所述服务实例对中服务实例i的下一周期的带宽为为服务实例i的额外带宽。
18.进一步的，所述周期性带宽分配算法根据最大最小公平带宽分配策略为每个服务实例分配基础带宽。
19.进一步的，服务实例i在分段j的波动值fj是服务实例i在该部分j实际平均到达负载速率和该服务实例i的基础带宽的差。
20.相似带宽波动实例聚类算法基于mean shift聚类算法(一种已公开的聚类算法)根据实例的波动距离对实例进行聚类。设每个周期被平均划分为m部分，每一服务实例在每个部分j的波动值是服务实例在该部分j实际平均到达负载速率和该服务实例的基础带宽b
base
的差，设fj表示第j部分(1≤j≤m)的波动值。设一个周期内每一服务实例在所有部分的波动值组成的元组为该实例在该周期的状态，用f表示，则实例i的状态fi可以表示为fi＝(f1,f2,
…
,fm)i。在实例带宽利用率为100％的情况下，分配的基础带宽迎合实际平均到达负载相等，此时每部分的波动都为0，设此情况为理想状态，用o表示，则理想状态可以表示为o＝(0,0,
…
,0)(m个0)。距离的值为状态f和理想状态o的欧氏距离，计算公式如下：
[0021][0022]
相似带宽波动实例聚类算法采用的mean shift聚类算法使用高斯函数作为平滑峰值函数，所有实例的距离作为mean shift聚类算法的输入，mean shift算法将距离相近
的实例聚到同一个类中，设最终得到的类数为k。
[0023]
带宽波动方向相反实例对查找算法在相似带宽波动实例聚类算法中得到的每个类中寻找波动方向相反的实例对。用如下条件判断两个实例u和v的波动方向相反：
[0024]
|fu+fv|≤v
dev
[0025]
其中v
dev
(v
dev
≥0)是预先设置好的偏差值。在理想状态下偏差值应为0，但实际上可能无法找到偏差值为0的实例对。带宽波动方向相反实例对查找算法依次遍历k个类，在每个类寻找满足上述判断条件的实例对，并分别记录实例对中每个实例状态中绝对值最大的波动值，实例u绝对值最大的波动值可用下式表示：
[0026]
max|fj|u[0027]
该波动值的绝对值称为额外带宽，用b
extra
(b
extra
≥0)表示，实例i的额外带宽为未结成实例对的实例的b
extra
值为0。额外带宽表示超过基础带宽额外分配的带宽，它间接地把同一服务实例对中的一个实例的带宽分配给另一个，因此不会对其他服务实例的带宽分配有影响。
[0028]
最终每个周期分配给实例i的带宽值bi是基础带宽和额外带宽的和，其计算公式如下：
[0029][0030]
本发明的优点如下：
[0031]
1.本发明可以为同一服务的不同服务实例按周期分配带宽。
[0032]
2.本发明能够提升已有周期性带宽分配方法的带宽利用率。
[0033]
3.本发明能够适应多种网络负载类型。
[0034]
4.本发明可以提升用户体验质量。
附图说明
[0035]
图1是本发明用于服务实例间周期性带宽分配的带宽利用率提升方法的结构框图。
[0036]
图2是本发明中的相似带宽波动实例聚类算法流程图。
[0037]
图3是本发明中的带宽波动方向相反实例对查找算法流程图。
具体实施方式
[0038]
下面结合附图对本发明进行进一步详细描述，所举实例只用于解释本发明，并非用于限定本发明的范围。
[0039]
本发明提供一种用于服务实例间周期性带宽分配的带宽利用率提升方法，如图1所示。服务由n个实例组成，每个服务实例在周期开始时将上周期的带宽使用情况发送给控制器，控制器先用已有的带宽分配算法为每个实例计算基础带宽，然后执行相似带宽波动实例聚类算法和带宽波动方向相反实例对查找算法计算额外带宽，最终计算额外带宽和基础带宽的加和为每个实例本周期的带宽分配结果，返回给n个实例。
[0040]
相似带宽波动实例聚类算法的流程图如图2，其主要目的在于先挑选出波动幅度相似的实例集合。算法首先根据上周期的带宽使用情况，计算每个实例的状态，然后根据实
例状态，计算每个实例的距离。根据实例的距离，用mean shift算法对所有实例进行聚类，在实施过程中，mean shift算法的核密度函数选择高斯函数，然后得到k个类，每个类中的实例距离相似。
[0041]
带宽波动方向相反实例对查找算法目的在于从波动幅度相似的实例类中找出实例波动方向相反的实例对，在周期内的任一时刻，实例对中的一个实例负载超过基础带宽，而另一个实例负载低于基础带宽，同时为这两个实例分配值为周期内最大工作负载的带宽，就能达到提升带宽利用率的效果。带宽波动方向相反实例对查找算法的流程图如图3，算法输入是相似带宽波动实例聚类算法得到的k个实例类、实例的状态和实例基础带宽，算法的输出是本周期各实例的带宽分配结果。实例对查找算法先将所有实例的额外带宽初始化为0，然后遍历k个类，在每个类中寻找状态和小于设置值v
dev
的实例对，状态分别为fu＝(f1,f2,
…
,fm)u和fv＝(f1,f2,
…
,fm)v的实例对(u,v)满足的条件可用如下公式表示：
[0042]
|fu+fv|≤v
dev
[0043]
满足公式条件的实例对的额外带宽值被设置为该实例状态元组中绝对值最大的值，上述实例对中实例u的额外带宽可以表示为
[0044]
max|fj|
[0045]
最终计算每个实例的基础带宽和额外带宽的和，作为实例本周期的带宽分配结果。
[0046]
尽管为说明目的公开了本发明的具体实施例，其目的在于帮助理解本发明的内容并据以实施，本领域的技术人员可以理解：在不脱离本发明及所附的权利要求的精神和范围内，各种替换、变化和修改都是可能的。因此，本发明不应局限于最佳实施例所公开的内容，本发明要求保护的范围以权利要求书界定的范围为准。

技术特征：
1.一种用于服务实例间周期性带宽分配的带宽利用率提升方法，其步骤包括：1)每周期开始时利用周期性带宽分配算法为每个服务实例分配基础带宽，为服务实例i对应的基础带宽；2)将每个周期内带宽波动范围相似的服务实例聚为一类；3)依次从每一类服务实例中寻找波动方向相反的服务实例对并为其分配额外带宽，作为对应服务实例下一周期的带宽。2.根据权利要求1所述的方法，其特征在于，采用相似带宽波动实例聚类算法根据服务实例的波动距离对服务实例进行聚类，具体方法为：将所述周期划分为m个分段，计算每个分段内每一服务实例的带宽波动值；根据一个周期内每一服务实例在各分段的波动值生成该服务实例在该周期的实际状态，服务实例i的实际状态f
i
＝(f1,f2,
…
,f
m
)
i
，f
m
为服务实例i在分段m的波动值；然后根据一个周期内每一服务实例的实际状态f与理想状态o的欧氏距离dist(f,o)对服务实例进行聚类。3.根据权利要求2所述的方法，其特征在于，所述欧氏距离服务实例的理想状态o为m个0。4.根据权利要求2所述的方法，其特征在于，所述相似带宽波动实例聚类算法为mean shift聚类算法；所述mean shift聚类算法采用高斯函数作为平滑峰值函数。5.根据权利要求2所述的方法，其特征在于，利用带宽波动方向相反实例对查找算法从每一类服务实例中寻找波动方向相反的服务实例对，如果两个服务实例u和v满足|f
u
+f
v
|≤v
dev
，则服务实例u和v为波动方向相反的服务实例对(u，v)；其中，f
u
为服务实例u的实际状态，f
v
为服务实例v的实际状态，v
dev
是预先设置好的偏差值，v
dev
≥0；然后将服务实例u绝对值最大的波动值max|f
j
|
u
作为服务实例u的额外带宽。6.根据权利要求5所述的方法，其特征在于，为所述服务实例对中每一服务实例分配的额外带宽为该服务实例的基础带宽与该服务实例对应的额外带宽之和。7.根据权利要求6所述的方法，其特征在于，所述服务实例对中服务实例i的下一周期的带宽为的带宽为为服务实例i的额外带宽。8.根据权利要求1所述的方法，其特征在于，所述周期性带宽分配算法根据最大最小公平带宽分配策略为每个服务实例分配基础带宽。9.根据权利要求1所述的方法，其特征在于，服务实例i在分段j的波动值f
j
是服务实例i在该部分j实际平均到达负载速率和该服务实例i的基础带宽的差。

技术总结
本发明公开了一种用于服务实例间周期性带宽分配的带宽利用率提升方法，其步骤包括：1)每周期开始时利用周期性带宽分配算法为每个服务实例分配基础带宽，为服务实例i对应的基础带宽；2)将每个周期内带宽波动范围相似的服务实例聚为一类；3)依次从每一类服务实例中寻找波动方向相反的服务实例对并为其分配额外带宽，作为对应服务实例下一周期的带宽。本发明大大提高了带宽利用率。本发明大大提高了带宽利用率。本发明大大提高了带宽利用率。


技术研发人员：杨威 李玉冰 刘庆云
受保护的技术使用者：中国科学院信息工程研究所
技术研发日：2023.03.03
技术公布日：2023/7/12