基于费用流的网络带宽成本优化算法研究

费用流算法是一种基于图论的优化算法，通常被用来解决网络流问题。在网络带宽成本优化方面，费用流算法能够最小化网络流的带宽成本，从而最大化网络资源利用率。本文旨在通过最小化网络流中的带宽成本，实现网络资源的最大化利用。该算法需要计算每个路径上的最大流量和最小费用，并通过贪心算法和增量优化迭代更新流量，直至找到最优解。与传统的线性规划方法相比，费用流算法不仅计算效率更高，而且在解决复杂网络带宽优化问题时能提供更精确的解决方案。

网络带宽是企业进行在线业务和数据传输的基础，但网络带宽的租赁和使用成本通常很高；随着企业的业务和客户需求的增长，对网络带宽的需求也在不断增加。现有加权公平队列算法保证了不同流之间的公平调度，却无法很好地实现压榨成本；最大剩余带宽算法在网络拓扑或流量分布发生变化时容易导致用户带宽之间得不到合理分配。费用流算法便能很好地通过优化路由和流量分配调度，根据实际需求实时预测和规划节点带宽需求，提高网络带宽的利用率和性能，降低网络带宽成本。

2. 研究背景及目的 网络带宽成本是指在单位时间内(一般指的是1 秒钟)内能传输的数据量。

随着网络规模不断扩大，互联网公司逐年增多，直播已成为一种常态，网络带宽成本是影响服务成本的关键因素之一，不同的流量调度方案会产生不同的网络使用成本，这也是各大直播公司所需要额外注意的问题。以虎牙直播、斗鱼直播两大直播巨头为例，2020 年第二季度，斗鱼带宽支出为1.684 亿人民币，平均每月5613 万，虎牙带宽支出为2.648 亿人民币，平均每月8826 万，带宽成本高得吓人。因此提升用户体验的同时降低运营成本是直播领域上竞争力的关键。

由于带宽往往是连续变动的，采用带宽计费时，根据取值方法的不同，可以分为两种方式：峰值计费和95 计费。

峰值计费采用一个时间段内的最高点作为计费依据，但是这种计费方式在遇到特殊的流量变化时，往往会造成费用激增。而目前从运营商采购带宽，大部分都是使用95 计费的方式。95 带宽峰值计费按自然月结算，在一个自然月内，按账户取每5 分钟有效带宽值进行降序排列，然后把带宽数值最高的5%的点去掉， 剩下的最高带宽就是95 带宽峰值计费值。

以一月30 天为例， 默认均为有效取值点：每5 分钟1 个带宽取值点，每小时12 个取值点，每月取值点数为12 × 24 × 30 = 8640 个；将所有的点按带宽数值降序排列，去掉前5%的点8640 × 5% = 432 个点，即第433 个点为计费点。

由图1 可以看出相较于峰值计费来说，95 计费能省下大量成本，节约开销。本项目研究内容是在95计费的基础上，结合国际先进的网络流技术，在满足客户要求的前提下，通过对流量的合理调度，最小化网络使用成本。从而进一步降低95 计费点的值，节约成本的同时，又不会影响用户的体验。

3. 研究内容及思路 1) 带宽流量计费进行分段数据采集，汇总。数据采集：使用cacti 多端口叠加流量开源软件监控测试机端口，对测试网络进行的实验数据收集，同步进行网络数据集收集；数据汇总：使用CRM 系统录入计费数据进行整理，生成图表与数据集。