1. 引言
网络带宽是企业进行在线业务和数据传输的基础，但网络带宽的租赁和使用成本通常很高；随着企业的业务和客户需求的增长，对网络带宽的需求也在不断增加。现有加权公平队列算法保证了不同流之间的公平调度，却无法很好地实现压榨成本；最大剩余带宽算法在网络拓扑或流量分布发生变化时容易导致用户带宽之间得不到合理分配。费用流算法便能很好地通过优化路由和流量分配调度，根据实际需求实时预测和规划节点带宽需求，提高网络带宽的利用率和性能，降低网络带宽成本。
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系统录入计费数据进行整理，生成图表与数据集。
Figure1. Bandwidth usage of a certain IDC user for one month
图1. 某IDC用户的带宽一个月的使用情况
2) 分析计费数据，寻找合适的建模方式：挑选合适的数据，进行数学分析，离散分析，根据数据特点进行建模，拟合数据，采用多种建模方式进行对比，总结性质。
3) 设计图论算法，进行程序设计与编写：根据模型建图，通过图性质，设计算法查找增广路，开发程序对数据集进行计算对结果进行分析，检查结果的合理性。不合理要对程序进行调试，即通过上机发现和排除程序中的故障的过程。保存多种方案。
4) 对方案进行数据验证分析：根据方案，模拟带宽流量并计算产生费用，验证结果数据，对比多种方法的不同结果数据，并将局部最优解的方案进行迭代。使用贪心算法测试模拟筛选出最实际可行的方案。
4. 国内外现状和费用流的优势
4.1. 国内外现状
近些年国内外对于节省网络带宽，降低成本方面的研究也有着许多成果。一种利用微观经济学中的效用函数对带宽进行层次化分配，使网络效用尽可能的最大化。该算法主要是对业务因素和用户需求因素进行了一个综合考虑。为了最大限度的满足各种类型视频应用的带宽要求,提高不同类型视频用户的满意度，N. Metropolis等人于1953年提出了一个基于多描述编码的带宽分配模拟退火算法，实验表明该算法比其他带宽分配算法更能充分利用带宽资源且能有效提高网络视频用户的整体满意度。
此外，效用比例公平带宽分配：一种面向优化的方法，利用效用函数的概念，其中每个源使用效用函数来评估实现传输速率的益处，我们将资源分配问题解释为全局优化问题。另外还有4G异构无线接入网络中基于效用的多业务带宽分配，提出了一种带宽分配算法，不仅在无线接入网内部，而且在不同的无线接入网之间，根据效用公平性为CBR和VBR连接分配带宽。定点优化算法，将提出的算法应用于一个网络带宽分配问题，并显示了其有效性。除此之外还有P2P，CDN和H.265编码技术等多种技术能有效降低带宽成本的技术。
4.2. 费用流的优势
相较于上述P2P，编码技术等在源头降低带宽成本的技术，费用流的优势在于过程的分配，能和上述技术相互结合从源头到过程两个维度来进一步节省带宽成本 [1] 。同时相较于常见的最大剩余带宽算法，费用流算法可以通过动态调整路径，适应网络拓扑结构或流量分布的变化。费用流算法通过在网络中寻找最小费用路径，可以实现更全局的优化 [2] 。这有助于解决最大剩余带宽算法可能存在的局部最优解问题 [3] 。费用流算法能够综合考虑成本和流量需求，从而更好地实现公平的带宽分配。避免最大剩余带宽算法可能存在的某些用户或流受到不公平对待的问题。
5. 研究方案措施
费用流算法首先根据常规的dijkstra算法，亦或采用不同的寻找最短路方案比如bellman_ford，spfa，Floyd等进行尝试，以确定效率最高的搜索方案。dijkstra算法实现较为简单，但无法运用在存在负权边的图中，如果拓展需求，需要计算成本的最大值的话(或者说计算成本的区间)，那么可行流的残留网络里必然会出现负权流量，这时dijkstra算法无法完成全部任务。bellman_ford和spfa算法可以解决负权边的问题，但无法解决负权回路，当流网络图中出现负权回路，还需要另外使用消圈算法进行优化。Floyd算法适合解决多源问题，但算法时间复杂度偏高。那么可以尝试结合各算法性质并通过测试确定不同需求需要的最佳算法。
由于处理的问题是多源多汇且多时刻的，此时如果采用仅特殊情况进行贪心的分配方案，会对数据进行大量但冗余的枚举和排序运算，而这会导致运行时间很长，运算效率低。对于此问题，可以选择分治的方式，把最终问题转化成多个类似的子问题进行处理再合并。使用费用流算法优化每个时刻，使每个时刻的方案都达到最优，当解决子问题时，再进行全局贪心，在所有不同但最优的情况下选择最优方案，得到问题最终的最优解。
当客户端发出带宽请求，服务端响应并分配相应的带宽用于传输数据给客户端，在每个时刻，每个边缘节点可以为若干客户节点提供带宽，但它能提供的带宽之和有上限。在每个时刻，一个客户节点的带宽需求可以分配到一个或多个边缘节点。客户节点和边缘节点之间的网络质量为Qos，表示时延大小，当Qos小于一定程度，认为该边缘节点可以向客户节点分配带宽，且不影响客户的使用体验。最后将一段时间内的边缘节点所产生的带宽进行升序排序，以这段带宽的95%的位置作为该节点的95百分位带宽，用于计算成本。分配方案决定了每个节点的成本，所以想要节约成本就要先算出最佳分配方案。将该问题简单抽象，数学建模成客户节点与边缘节点之间的问题，就变成了一个多源最大流最小费用问题。
设置一个虚拟源点和一个虚拟汇点，分别与客户节点和边缘节点相连接，使它们成为流网络的一部分。便可再抽象为单元的费用流问题。我们通过bfs寻找增广路然后迭代更新残留网络完成分配方案的选定。此时能得到每个时刻的最大流最小费用方案，此时再进行全局贪心再加和处理即可得到最终的带宽总成本。算法流程如图2所示。
6. 结语
通过对费用流在网路带宽中的深入研究，本文从背景意义及研究思路、国内外现状和方案措施等全面阐述了费用流对于网络带宽成本优化中起了至关重要的作用。费用流模型通过对流量路由进行优化，有效地降低了网络带宽的使用成本，并提升了网络的性能和可靠性。未来的研究可以进一步探索并优化费用流算法，在更多场景下提升其应用效果。此外，随着5G、物联网等技术的发展，网络带宽成本优化仍然具有重要的研究价值和应用前景。我们相信，费用流模型在未来的研究中将会继续发挥重要作用，推动网络带宽成本优化向更高水平发展。
基金项目
2022年区级大学生创新创业计划立项项目——基于费用流的网络带宽成本优化算法设计(S202210595171)。