基于分布式平均跟踪算法的多瓶颈网络主动队列优化方法

技术领域

本发明涉及控制与信息技术领域，尤其涉及一种基于分布式平均跟踪算法的多瓶颈网络主动队列优化方法。

背景技术

随着网络技术的不断发展，大量实时多媒体数据流的产生，单靠端节点实施拥塞控制已经不能满足现如今用户对上网速度、高清音视频的需求，网络中间节点(网关、路由器、交换机等)处的拥塞控制算法应运而生。网络中间节点主动队列拥塞控制的主要任务是提前预测节点的拥塞，一旦拥塞发生，节点自身采取拥塞控制的同时也会将拥塞信号传递给发送端，再与源端算法相结合进行协同拥塞控制，减少或者避免拥塞情况的发生，从而改善网络性能。

Floyd等人提出的RED算法是主动队列算法的开创性工作。它主要根据队列长度来判断网络的拥塞状况，在拥塞发生的早期,对数据包以一定的概率丢失或者标记，这样就可以及时地通知系统源端网络拥塞，降低数据包的发送速率,从而避免网络拥塞情况的加重。RED算法对参数设置敏感且只能根据特定的网络场景设置参数，不能适应网络中数据流量的变化，在单瓶颈网络中上述算法可以改善网络的性能，但应用到多瓶颈网络时上述算法没有考虑到瓶颈链路之间的相互影响，无法根据整个网络的拥塞情况采取控制策略，导致网络队列震荡严重甚至不稳定。本专利将分布式平均跟踪算法与RED算法相结合，动态调整RED算法的参数，根据整个网络的拥塞情况做出控制决策，改善多瓶颈网络的性能。

单瓶颈网络无法模拟瓶颈链路之间的相互影响，源端及交叉流量端对瓶颈资源的争夺，交叉流量对网络的影响，而这些是影响实际网络性能的重要因素。实际网络是一个不断变化、非线性的系统，相比于单瓶颈网络，多瓶颈网络更接近于实际的网络模型。通过对多瓶颈网络各种主动队列算法进行研究，有助于揭示现有算法在实际网络中的缺陷，并对推动主动队列算法的发展具有重要的意义。

发明内容

针对现有技术的不足，本发明提供一种基于分布式平均跟踪算法的多瓶颈网络主动队列优化方法，本发明动态调整RED算法的最大、最小阈值，并将分布式平均跟踪算法与RED算法相结合，根据整个网络的拥塞程度做出拥塞决策，改善多瓶颈网络的性能。

本发明所采取的技术方案是：

一种基于分布式平均跟踪算法的多瓶颈网络主动队列优化方法，包括以下步骤：

步骤1：构造路由器进行信息传递的网络结构拓扑图；

所述网络结构拓扑图是无向连通图，其中节点数量为N，边的数量为M，每个节点代表一个路由器；

步骤2：设置每个节点的的初始状态，以及初始队列长度；

步骤3：设置节点间的通信方式，使每个节点只能与邻居节点通信，运行分布式平均跟踪算法，根据与邻居节点通信获得的反馈信息来调整节点估计的队列长度达到一致性，并且跟踪网络中所有节点队列长度的平均值；

所述队列长度如下式所示：

x

q

其中，i，j为节点且i，j∈(0，N]，x

所述反馈信息为节点i与其邻居节点通信获得的差值信息e

e

其中，a

所述根据与邻居节点通信获得的反馈信息来调整节点估计的队列长度达到一致性，并且跟踪网络中所有节点队列长度的平均值，包括以下步骤：

步骤S1：计算下式表示的跟踪目标，实现跟踪所有节点实际队列长度的平均值：

其中，

步骤S2：跟踪队列长度平均值，如下式所示：

||x

其中，公式||x

步骤4：通过设置阈值参数得到路由器进行拥塞决策时的动态阈值；

所述设置阈值为，将阈值设置为整个网络平均队列长度的倍数，得到动态阈值如下式所示：

min

max

其中,min

步骤5：将得到的整个网络的平均队列长度q

步骤6：根据整个网络的平均队列长度，计算丢弃概率，进行拥塞控制；

如果min

所述数据包包含发送者和接收者的地址信息；

所述丢弃概率的具体公式如下：

P

其中，P

采用上述技术方案所产生的有益效果在于：

本发明提出一种基于分布式平均跟踪算法的多瓶颈网络主动队列优化方法，利用自适应动态调整RED算法的参数，以更好的适应网络中数据流量的变化。将分布式平均跟踪算法与RED算法相结合，利用分布式平均跟踪算法实现跟踪所有队列长度平均值的目的，实现所有节点估计的队列长度趋于一致且跟踪实际队列长度的平均值，路由器可以根据反映整个网络拥塞程度的队列长度做出拥塞决策，使拥塞控制更加准确，避免RED算法应用到多瓶颈网络出现的不稳定现象。

基于分布式平均跟踪算法的多瓶颈网络主动队列优化方法，应用于网络会提高网络的吞吐量，减少丢包率，提高用户的服务质量，改善网络的性能。

附图说明

图1为本发明的多瓶颈网络主动队列优化方法流程图；

图2为本发明实施例网络拓扑结构图；

图3为本发明实施例仿真实验结果图；

图中，图(a)-实际队列长度q1；图(b)-实际队列长度q2；图(c)-实际队列长度q3；图(d)-实际队列长度q4。

具体实施方式

下面结合附图对本发明具体实施方式加以详细的说明。

一种基于分布式平均跟踪算法的多瓶颈网络主动队列优化方法，如图1所示，包括以下步骤：

步骤1：构造路由器进行信息传递的网络结构拓扑图；

所述网络结构拓扑图是无向连通图，其中节点数量为N，边的数量为M，每个节点代表一个路由器，本实施例为一个具有4个拥塞路由器的通讯网络实例，网络结构拓扑图如图2所示；

步骤2：设置每个节点的初始状态和队列长度的初值，初始状态x

步骤3：设置节点间的通信方式，使每个节点只能与邻居节点通信，运行分布式平均跟踪算法，根据与邻居节点通信获得的反馈信息来调整节点估计的队列长度达到一致性，并且跟踪网络中所有节点队列长度的平均值；

所述队列长度如下式所示：

x

q

其中，i，j为节点且i，j∈(0，4]，x

所述反馈信息为节点i与其邻居节点通信获得的差值信息e

e

其中，a

所述根据与邻居节点通信获得的反馈信息来调整节点估计的队列长度达到一致性，并且跟踪网络中所有节点队列长度的平均值，包括以下步骤：

步骤S1：计算下式表示的跟踪目标，实现跟踪所有节点实际队列长度的平均值：

其中，

步骤S2：跟踪队列长度平均值，如下式所示：

||x

其中，公式||x

步骤4：通过设置阈值参数得到路由器进行拥塞决策时的动态阈值；

所述设置阈值为，原RED算法最大阈值和最小阈值是对特定的网络根据经验人为设定，将阈值设置为整个网络平均队列长度的倍数，让阈值参数可以适应网络数据流量的变化，动态调整，从而改善网络性能。得到动态阈值如下式所示：

min

max

其中,min

步骤5：将得到的整个网络的平均队列长度q

步骤6：根据整个网络的平均队列长度，计算丢弃概率，进行合理拥塞控制；

如果min

所述数据包包含发送者和接收者的地址信息；

所述丢弃概率的具体公式如下：

P

其中，P

图3对具有5组数据流和4个拥塞路由器的网络进行仿真，通过与RED算法对比，观察每个路由器的队列q1-q4的长度变化来验证新提出的优化方法的有效性，从图3的仿真结果可以看出新提出的方法，响应速度更快，可以让队列长度稳定在一个范围内，减少队列长度的震荡，有助于改善网络性能。

最后应说明的是：以上各实施例仅用以说明本发明的技术方案，而非对其限制；尽管参照前述各实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分或者全部技术特征进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本发明权利要求所限定的范围。