一种最大化最小公平多数据流传输调度方法

摘要

本发明提供了一种最大化最小公平多数据流传输调度方法，属于计算机网络中的网络数据流量优化领域。所述方法包括：输入数据中心网络拓扑信息和数据流传输请求信息，计算网络拓扑中每条边的中介性特征值；所述数据中心网络拓扑信息包括各个数据中心之间的链路连接关系和每条链路的带宽容量；所述数据流传输请求信息包括每个数据流传输请求的发送端、目的端和请求传输的数据量；基于所述中介性特征值，对两点间的不同路径进行评估，为每个数据流传输请求选出特定的K条不重叠传输路径的集合P_i；以及基于每个数据流传输请求的所述K条不重叠传输路径的集合P_i，迭代求出其对应最优的满足最大化最小公平规则的网络带宽资源分配方案。

主权项

一种最大化最小公平多数据流传输调度方法，其特征在于：所述方法包括：输入数据中心网络拓扑信息和数据流传输请求信息，计算网络拓扑中每条边的中介性特征值；所述数据中心网络拓扑信息包括各个数据中心之间的链路连接关系和每条链路的带宽容量；所述数据流传输请求信息包括每个数据流传输请求的发送端、目的端和请求传输的数据量；基于所述中介性特征值，对两点间的不同路径进行评估，为每个数据流传输请求选出特定的K条不重叠传输路径的集合P_i；以及基于每个数据流传输请求的所述K条不重叠传输路径的集合P_i，迭代求出其对应最优的满足最大化最小公平规则的网络带宽资源分配方案；所述基于所述中介性特征值，对两点间的不同路径进行评估，为每个数据流传输请求选出特定的K条不重叠传输路径的集合P_i包括：(A1)：给定网络G(V，E)，源点和目的点分别为v_s和v_t，以及需要求出的路径数目K；(A2)：在网络G上求解其最短路径p1，将p1加入集合Ps，并将p1所占据的带宽资源从G中减去，得到残余网络Gr；所述Ps为分配给每个数据流传输请求的路径集合；(A3)：在残余网络Gr上重复步骤(A2)直至路径数达到K或无法求出新的最短路径；若其中出现多条长度相等的路径的情况，选择中介性特征值和最小的路径；所述中介性特征值和是指每个路径中各条边的中介性特征值的和；(A4)：若求出K条路径，则转入步骤(A10)，否则设置变量k＝1，并转入步骤(A5)；(A5)：将Ps中的路径按照长度从小到大进行排序，然后从Ps中选出第k条路径，p_k＝(v₁，v₂，...，v_i，v_j，...，v_n)，其中，n为该路径上的节点数量，i，j均为初始值为0的整数；(A6)：对任意0＜j＜n，先将p_k的链路(v_i，v_j)长度设为无穷，之后在网络G上求出从v₁至v_n的最短路径p_d，并将其加入集合B，重复步骤(A6)直至j＝n‑1；(A7)：将i加1，恢复G中各链路长度为初始值，重复步骤(A6)直至i＝n‑2；(A8)：从集合B中选出中介特征值和最小的一条路径p’，并将其加入集合Ps；(A9)：若求出K条路径，则转入步骤(A10)，否则将k加1，并重复步骤(A5)至步骤(A9)，直至B中不存在任何路径，然后转入步骤(A10)；(A10)结束；所述基于每个数据流传输请求的所述K条不重叠传输路径的集合P_i，迭代求出其对应最优的满足最大化最小公平规则的网络带宽资源分配方案包括：(B1)：基于对数据中心网间带宽资源开销的预测信息，利用时间延展网络转换方法将具有动态空闲带宽资源的网络转换为静态流网络；(B2)：基于所述静态流网络，对所有数据流传输请求建立最大化最小公平多商品流线性规划模型；(B3)：迭代地求解所述最大化最小公平多商品流线性规划模型，得出各个数据流传输请求的最大传输流量以及对应的数据传输路径；所述(B1)的所述时间延展网络转换方法是这样实现的：将网络资源从时间维度进行延展，使具有动态空闲带宽资源的网络的动态带宽资源和节点的存储资源能力统一转化到一张静态流网络上；所述(B2)中的所述最大化最小公平多商品流线性规划模型为：maximize λ$\begin{array}{ccc}s.t.& \underset{r_i\in R}{\Sigma }\underset{p\in P_i}{\Sigma }{f}_p^{r_i}\le C_e,& \forall e\in E,e\in P_i\end{array}---\left(1\right)$$\begin{array}{cc}\underset{p\in P_i}{\Sigma }{f}_p^{r_i}\ge \lambda ·{\mathrm{dem}}_i,& \forall r_i\in R_{\mathrm{unsat}}\end{array}---\left(2\right)$$\begin{array}{cc}\underset{p\in P_i}{\Sigma }{f}_p^{r_i}\ge {\lambda }_{q_i}^{\mathrm{sat}}·{\mathrm{dem}}_i,& \forall r_i\in R_{\mathrm{sat}}\end{array}---\left(3\right)$$f_p^{r_i}\ge 0,\lambda \ge 0,\forall p\in P_{i=1...K}---\left(4\right)$其中，r_i是一个数据流传输请求，R是所有数据流传输请求的集合，表示在路径p上分配给r_i的带宽值，C_e代表链路e的带宽资源，E＝{e₁，e₂，...，e_m}，是网络中所有链路e的集合，λ为饱和的带宽分配比例值，dem_i是r_i传输的数据量，R_unsat为非饱和请求集合，为已经求得最大传输流量的那些请求所对应的λ值，R_sat为饱和请求集合；(1)、(2)、(3)和(4)这四个式子为约束条件。