GreedyScheduling: 最小化成本的视频流量贪心调度策略

一、背景

在视频直播场景中，网络成本是影响服务成本的关键因素之一，不同的流量调度方案会产生不同的网络使用成本。

二、目标

本项目以云视频直播服务中的流量调度问题为基础，通过一定的抽象、调整和简化。设计一种高效网络流量的贪心调度策略，在满足客户需求的前提下，通过对流量的合理调度，最小化网络使用成本。

三、相关术语介绍

名称	解释
时刻	流量调度沿时间线进行，将时间线划分成若干个独立的调度单元，用单元的起始时间来指代这个单元，称为时刻。
带宽	在一个时刻，某个节点的流量大小称为带宽。
客户节点	一种抽象节点，在每个时刻，每个客户节点会产生新的带宽需求。
边缘节点	一种抽象节点，和客户节点直接交互的网络节点。客户节点通过边缘节点获取数据流量。在每个时刻，每个边缘节点可以为若干客户节点提供带宽，但它能提供的带宽之和有上限。在每个时刻，一个客户节点的带宽需求可以分配到一个或多个边缘节点。
QoS	客户节点和边缘节点之间的网络质量。不同客户节点和边缘节点之间的网络会因距离、网络连接状况有差别。本题中QoS简化成一个数值，表示时延大小（单位：ms）。
边缘节点带宽序列	对于某个边缘节点，统计它在每个时刻分配的带宽之和，这些值在整个时间线上形成一个带宽序列。
95百分位带宽	对一个边缘节点带宽序列进行升序排序，以其95%位置（向上取整）的带宽值作为该节点的95百分位带宽。
边缘节点成本	每个边缘节点的95百分位带宽值乘上带宽的单位成本。
带宽总成本	求和所有边缘节点成本得到带宽总成本。

四、核心流程

• 读取data文件夹中包含的各个数据
• 根据需要分配的时间总节点进行计算可作为免费使用的次数（>95%的位置有多少个）
• 优先选择存在95%位置（95百分位带宽）的边缘节点进行满载处理
• 用完免费使用次数后将所有剩余未分配的客户需求流量均分给每一个客户可使用的边缘节点
• 进行一轮检查，如还未分配完毕，则在进行一次平均分配

五、输入结果样例

A:<CZ,19261>
B:<AD,17223>
C:<CZ,8581>
D:<CZ,11671>
E:<Dr,6070>
F:<Dn,34940>
G:<CZ,9969>
H:<CF,3180>
I:<CZ,32248>
J:<CZ,39796>

六、运行方式

• 如果出现运行问题，则将main.cpp文件中的这部分代码，folder_path改为data文件夹所在的本地路径，如无问题，则忽略此步骤

string folder_path = "../data/";

• 打开终端，运行gcc main.cpp或者通过vscode的cmake工具配置为main.cpp文件运行
• 如想测试更复杂的数据，可以将数据文件目录切换为../pressure_data/