基于覆盖网络的多路径流量均衡研究

设网络用G(V，E)表示，其中V表示顶点，E表示顶点间的边。
定义输入链路i的利用率：，这里表示流经i链路流量与i链路容量的比值。
根据前面的分析可知，节点S到t的总流量可以表示为：。
延迟对于发送数据来说是衡量链路好坏的一个重要参数，本文通过考虑节点的端到端的延迟来分析网络是否均衡。
输入排队延迟为输入链路的队列长度除以链路的速度，

上述定义的延迟在后面的仿真中将用到。

2 流量输入的带宽分配算法
输入的带宽分配方法主要是解决输入链路的不均衡利用问题。网络均衡在数学上的表示是各输入链路的带宽利用率的方差最小。即使得最小，因此该问题可以转化为以下问题：
目标函数：求解输入链路i上以t为目的节点的流量

式(1)的含义是：输入的流量要小于输出的容量，以避免节点拥塞，因此将输出链路的总容量作为输入链路的总流量的约束；输入链路的总的流量要小于目的t的总流量。

这里将其定义为平均链路利用率。
式(1)条件下的最小值是存在的，但是问题的求解非常困难。因此，这里用一个近似算法来替代上式的求解。定义一个带宽分配周期，将平均链路利用率作为参考值，根据上一周期的输入链路利用率是否大于平均链路利用率而调整分配带宽。设置一个链路i调整带宽



3 多路径流量输出分配算法
多路径流量分配算法是指通过多路径算法实现对节点的流量按照某些特定的要求分配到多条路径上，并实现网络性能的优化。
在此，为了实现节点流量的多路径分配，定义一个分配概率矩阵。通过调节该矩阵实现流量的合理分配，使得流量的分配更加均衡。

矩阵元素Piyj表示数据通过链路i到目的Vj的概率，在这里我们把其作为流量分配的比例。以t为目的节点，分配到链路i的流量为。