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

覆盖网络是以底层的物理网络为基础，在此基础上建立的虚拟网络。覆盖网络中的节点间的虚拟连接是逻辑上的，与底层的物理网相比，覆盖网络具有更好的灵活性。覆盖网络中的节点与传统网络中的节点相比，具有处理功能，即存储一处理一转发功能。多路径路由是相对于单路径的路由来说的，现在的Intemet中的路由使用的是单路径路由，不支持多路径路由。文献中给出了覆盖网络上的负载均衡多播路由算法，文献中对多路径路由做了研究，文章指出了多路径对吞吐量的增大，可靠性的提高有着良好的作用。文献通过对网络拓扑的连通性和节点间距离建模，比较了覆盖路由相对普通的IP层路由的优势。文献提出弹性覆盖网络(Resilience Overlay Networks，RON)，是MIT的And-ersen等人对多路径覆盖路由系统的最早的实现方案，通过不断探测网络的状态，然后选择一个中间节点转发数据，实现系统对网络链路失效的快速检测和“绕行”。流量的均衡对于减少端到端时延，拥塞控制和充分利用网络有着重要的意义。但是，上述文献中并没有给出覆盖网络的多路径路由技术在网络流量均衡中的应用，因此本文提出在覆盖网络上用多路径路由技术对覆盖网络流量进行均衡的方法。
    本文在建立一种覆盖网络的多路径流量均衡的模型的基础上，引入一个网络流量预测算法，通过网络节点间的协作对网络流量进行均衡。

1 覆盖网络的多路径流量均衡模型
    相比现在研究较多的传统单路径网络的流量均衡，本文采用的是多路径方案对网络流量进行均衡。相比于单路径使网络流量过于汇集，多路径可以让网络流量分配到多条可行的路径上，提高网络的吞吐能力，降低网络的时延。
    本文的模型建立基于如下假设：
    (1)覆盖网络上的节点具有足够的数据处理能力和转发能力，即节点数据处理和数据转发与时延相比开销很小，网络的延迟主要产生在传输链路上。
    (2)覆盖网络上的节点的内部包括不同类型的流量成分，这些流量成分可以按照一定的标准划分，本文中按照目的节点来划分流量。
    (3)覆盖网络可以通过一定的检测机制检测网络的时延信息。
    本文中所用的路由是源路由，即所有的路由信息都是由源节点规划完成，路径上的节点只负责转发，不对路径作任何改变。源节点通过不断探测得到链路信息，这样节点就会拥有整个网络拓扑，进而根据网络的拓扑，链路的时延、带宽等信息规划出多条路径。这些路径构成路径集，本文中的路径集中的路径都是不相交的路径(disljoint paths)。
    进入节点S且目的节点为t的流量可以划分成两个部分：节点S始发到目的节点t的流量和经过节点S中转而发往目的节点t的流量。多路径的路由选择过程从网络流量角度来看分为两步：第一步是各链路流入节点S的过程，第二步是通过选路机制进行多路径的转发过程，将流量分配到不同的路径上去。为了说明此问题，下面给出图示。

    为了描述模型，定义如下符号，如表1所示。

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

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

    式(1)的含义是：输入的流量要小于输出的容量，以避免节点拥塞，因此将输出链路的总容量作为输入链路的总流量的约束；输入链路的总的流量要小于目的t的总流量。
    
    这里将其定义为平均链路利用率。
    式(1)条件下的最小值是存在的，但是问题的求解非常困难。因此，这里用一个近似算法来替代上式的求解。定义一个带宽分配周期，将平均链路利用率作为参考值，根据上一周期的输入链路利用率是否大于平均链路利用率而调整分配带宽。设置一个链路i调整带宽
    
    

3 多路径流量输出分配算法
    多路径流量分配算法是指通过多路径算法实现对节点的流量按照某些特定的要求分配到多条路径上，并实现网络性能的优化。
    在此，为了实现节点流量的多路径分配，定义一个分配概率矩阵。通过调节该矩阵实现流量的合理分配，使得流量的分配更加均衡。
    
    矩阵元素Piyj表示数据通过链路i到目的Vj的概率，在这里我们把其作为流量分配的比例。以t为目的节点，分配到链路i的流量为。

上述分配的流量需要满足以下约束：
    
    式(2)表示：分配到输出链路上的流量要小于输出链路的容量；输出的总的流量应小于流到目的节点的总流量。
    网络是动态的，通过分析多路径网络的实际运行过程可知，在很多情况下流量在一定时间段内具有相对稳定性，因此可以用预测算法对下一时段的流量进行预测。上式(2)求解计算开销较大，下面通过预测算法来决定概率分配矩阵。
    对流量进行周期性的预测。设tf为预测周期，tp为探测周期，每到一个探测周期对网络性能(时延、吞吐率、丢包率等)进行探测，预测周期是由若干个探测周期组成的。覆盖网络可以通过一定的检测机制对网络链路的时延状况进行评估。
    
    式中：为第j个预测周期，对链路i分配流量比率的预测；fi为当前链路i的流量；为节点当前的总流量；β为权重因子，调节β的大小可以调节预测部分和当前部分在决策中的权重；为第j-1个预测周期，链路i的预测流量；为第j-1个预测周期，节点的预测总流量用上述预测的概率来作为分配矩阵中的概率，即令。

4 仿真实验
    通过NS2的GT-ITM的Waxman模型模拟出如下图的网络拓扑，节点数为10，设节点链路的容量都是10Mb／s，输入链路的速率为50M／s。图2实验拓扑图。

    本文通过分析时延特性来说明对网络性能的改善。网络中的节点加上负载大小是随机的，以N2到N4为例来分析端到端时延特性，通过对比单路径和多路径的端到端的时延来实现。单路径表示N2-NO-N4，多路径包括路径1和路径2，其中路径1表示N2-N6-N4，路径2表示N2-N0-N4。可以看到通过多路径路径1和路径2相比于单路径可以有效地减少端到端的延迟。路径1和路径2的端到端延迟相差不大，说明负载在网络中是较为均衡的。

5 结语
    传统的网络只负责报文的尽力而为的转发服务，网络中流量按照单条路径转发，各节点之间缺少相互的协调工作。本文通过覆盖网络模型的建立，对网络流量进行预测并通过多路径传输，使得节点的端到端延迟大大减小，为解决流量均衡问题提供了一条新思路。