一种基于负载均衡的多径路由分配方法

摘要

本发明为一种集中式的多径路由分配方法，利用基于线性规划的负载均衡技术，结合网络的链路状态，为业务需求提供路由分配方案，可以应用于网络层的带宽资源分配与路由建立过程。应用本发明可在各种复杂网络环境下，将业务流平均分配在网络各条链路之上，从而充分利用网络的拓扑结构，解决现有路由方法易拥塞、吞吐量低的缺点，扩展网络的吞吐量和连通性，改善网络的端到端延时等性能。在无线自组织网等负载严重不均衡的环境下，应用本发明可以显著提高网络的带宽利用效率，减少拥塞并降低端到端延时。

主权项

1.多径路由分配方法，其特征在于包括：根据总带宽资源矩阵C和已用带宽资源矩阵TM，计算从源节点矢量S到宿节点矢量R的业务的路由分配矩阵D，使得网络所有链路的负载占用率尽量小，其中当网络中有N个节点时，所述总带宽资源矩阵C是一个N×N矩阵，其中第i，j个矩阵元c_ij为从节点i到节点j的直达链路link_ij总带宽，所述已用带宽资源矩阵TM是一个N×N矩阵，其中第i，j个矩阵元tm_ij为链路link_ij的已用带宽，所述源节点矢量S是一个N维矢量，其第i个分量s_i表示节点i作为源节点的业务流出量，所述宿节点矢量R是一个N维矢量，其第i个分量r_i表示节点i作为宿节点的业务流入量，所述路由分配矩阵D是一个N×N矩阵，其中第i，j个矩阵元d_ij为链路link_ij上的分配带宽，在每次业务的分配前，分配中心获得：当前网络的总带宽资源矩阵C₀，所述总带宽资源矩阵C₀是一个N×N矩阵，其第i，j个矩阵元d_ij为从节点i到节点j的直达链路link_ij上的业务分配，其中矩阵元c_0ij表示链路link_ij的总带宽，已用带宽资源矩阵TM₀，所述已用带宽资源矩阵TM₀是一个N×N矩阵，其矩阵元tm_0ij为链路link_ij的已用带宽，源节点矢量S₀，所述源节点矢量S₀是一个N维矢量，其第i个分量s_0i表示节点i作为源节点的业务流出量，宿节点矢量R₀，所述宿节点矢量R₀是一个N维矢量，其第i个分量r_0i表示节点i作为宿节点的业务流入量，把所述总带宽资源矩阵C₀、已用带宽资源矩阵TM₀、源节点矢量S₀和宿节点矢量R₀分别作为网络总带宽资源、已用带宽资源、源节点、宿节点代入负载均衡算法，计算是否存在可行解，若不存在解，则返回“分配方案不存在”并结束分配流程，所述负载均衡算法输出路由分配矩阵D和最小化后的各链路负载占用率最大值r_min，将达到所述最小化后的各链路负载占用率最大值r_min的所有链路link定义为瓶颈链路集合A，以所述总带宽资源C、所述已用带宽资源TM、源节点矢量S、宿节点矢量R分别作为网络总带宽资源、已用带宽资源、源节点和宿节点，依次对所述瓶颈链路集合A中的每条链路分别用限制瓶颈链路流量的负载均衡算法进行处理，当存在可行解且各链路占用率最大值的最小值r_neck≤r_min时，将该链路从所述瓶颈链路集合A中删除，其中所述负载均衡算法包括：根据所述总带宽资源C和已用带宽资源TM，计算从源节点矢量S到宿节点矢量R的业务的路由分配矩阵D，其中路由分配矩阵D的矩阵元d_ij表示链路link_ij上的分配带宽，最小化所有链路的负载占用率的最大值，即r_min=minr其中r是所有链路的负载占用率的最大值，j，$0\le \frac{d_{\mathrm{ij}}+t{m}_{\mathrm{ij}}}{c_{\mathrm{ij}}}\le r$最小负载占用率约束，$\underset{j}{\Sigma }{d}_{\mathrm{ij}}-\underset{j}{\Sigma }{d}_{\mathrm{ji}}=s_i-r_i$节点流量守恒，j，0≤d_ij≤c_ij-tm_ij流量边界约束。