一种基于奇异值分解的可用带宽预测方法

摘要

一种基于奇异值分解的可用带宽预测方法，本发明是针对如何准确地预测任意两个结点的可用带宽问题，提出的基于奇异值分解的可用带宽预测方法AVBP-SVD。首先，在网络中随机选择部分结点作为基准结点，基准结点互测彼此间的可用带宽来确定嵌入的向量空间。然后，非基准结点通过测量与基准结点间的可用带宽来计算自己在整个向量空间的坐标，从而估计出节点间的可用带宽。相对于以往的可用带宽模型和预测方法更加准确。通过选择适当数目的测量点和嵌入维数，有效降低了不同网络路径瓶颈分布差异带来的误差。

主权项

1.一种基于奇异值分解的可用带宽预测方法，其特征在于，包括下列步骤：A.在一个具有N个节点的网络中选择m个结点作为基准结点集L={l₁,l₂,…,l_m}，各基准节点分别测量到其余基准节点间的可用带宽并发送给服务器S，在服务器S上形成可用带宽矩阵B；B.使用奇异值分解方法对可用带宽矩阵B进行分解得到左右两个变化矩阵X和Y，即:B=U∧V＝UΣ²V＝(UΣ)(ΣV)                    (1)然后，取(UΣ)和(ΣV)的前n维作为变换矩阵，分别记作X＝(UΣ)_n，Y＝(UΣ)_n，其中Σ为特征值矩阵，U和V为左右两个奇异矩阵，n表示嵌入维数，基准节点的坐标即为X和Y中对应的行向量和列向量；C.从N个节点中选择取非基准节点的任一个结点H_i，从服务器S查询获得基准结点集的列表L，并向所有基准结点发起测量请求，在各基准结点的配合下分别测得出向和入向可用带宽向量Lⁱ_in=(b_i1，b_i2，…,b_im),Lⁱ_out＝(b_1i，b_2i，…，b_mi)；D.计算结点H_i在嵌入空间中的坐标(),计算公式如下:$C_{\mathrm{in}}^i=\left(L_{\mathrm{in}}^{i}Y\right){\left(Y^{T}Y\right)}^{-1}---\left(2\right)$$C_{\mathrm{out}}^i=\left(L_{\mathrm{out}}^{i}X\right){\left(X^{T}X\right)}^{-1}---\left(3\right)$E.估计网络中任意两结点间的可用带宽大小，计算公式如下：$\mathrm{avb}(H_i,H_j)=\overline{C_{\mathrm{in}}^i}·\overline{C_{\mathrm{out}}^j}---\left(4\right)$$\mathrm{avb}(H_j,H_i)=\overline{C_{\mathrm{in}}^j}·\overline{C_{\mathrm{out}}^i}---\left(5\right).$