RED算法C++实现

随机早起检测（RED，Random Early Detection）算法将队列的平均队长作为决定拥塞避免机制是否应被处罚的随机函数的参数，增加了在队列长度变得太大之前平滑瞬时拥塞的可能性，减少了同时使多个流受分组丢弃影响的可能性。

基本思想：

通过监控路由器输出端口队列的平均长度来探测拥塞，一旦发现拥塞逼近，就随机地选择连接来通知拥塞，使他们在队列溢出导致丢包之前减小拥塞窗口，降低发送数据速度，从而缓解网络拥塞。

随机早期检测的设计目标：

　　1)最小化数据包丢失率和排队延迟；
　　2)避免全局同步现象；
　　3)避免对突发业务的偏见：网络中含有大量的突发数据，而传统的“去尾”算法对突发业务有很大的偏见。偏见就是在采用“去尾”算法的路由器中，如果某个流的突发性越高，则当该流的数据包进入队列时越容易造成队列溢出，从而导致连续地丢弃大量的该流的包；
　　4)即使在缺乏传输层协议有效配合的情况下，算法也能控制平均队列长度，从而避免拥塞。为了达成以上目标，RED采用了基于时间的平均队列长度，并且随机地选择正进入路由器地分组进行丢弃。这种方法能被有效地实施而无需在路由器中维持每个流(per-flow)的状态信息。

算法实现

RED算法主要分为两个部分。首先是计算平均队列长度，另一个就是计算丢弃包的概率。
计算平均队长的目的就是为了反映拥塞状况，根据拥塞的程度来计算丢弃包的概率，从而有效地控制平均队列长度。
 1）计算平均队列长度

avgQ = (1-w)×avgQ+q×w

w 为权值，q 为采样测量时实际队列长度

2）计算丢弃包的概率

RED 有两个和队列长度相关的阈值：minth 和maxth。当有包达到路由器时，RED 计算出平均队长 avgQ。若 avgQ 小于 minth，则没有包需要丢弃；当 minth≤avgQ≤maxth 时，计算出概率 P，并以此概率丢弃包；当 avgQ>maxth时，所有的包都被丢弃。

Pb = maxp×(avgQ-minth) / (maxth-minth)
P = Pb / (1-count×Pb)

RED 算法优点：

RED 算法是一种主动拥塞控制机制，通过监测平均队列长度来确定网络拥塞的程度，采用按一定比例随机地标记丢弃分组的方法，有效地克服了全局同步及存在振荡的缺陷，利用低通滤波器计算平均队列长度，有效解决了网络流量的突发性对网络稳定性的影响。

RED 算法局限性

1. RED 对参数的设置敏感，参数变化对性能影响大。
1) avgQ 为平均队列长度，作为动态计算分组丢弃标记概率的依据，计算公式如下：

avgQ = (1-w)×avgQ+q×w

w 的大小决定了 q 对 avgQ 的影响严重程度， w 越小，表明 avgQ 随 q 的变化不明显， w 越大，说明 avgQ 紧随 q 的变化而变化，选择合适的 w 确保 avgQ 适度的灵敏性使网络缓解突发流量的影响，又能对网络的拥塞作出适度反应，避免多个数据流的同步。
2) minth 、 maxth 两个门限值，中间节点的平均队列长度一般局限于这两个门限之间变化，如何充分利用缓存资源又减少分组通过中间节点的延迟，同时保证网络的高吞吐量，这本身就存在矛盾，要充分利用缓存资源，就要增加队列长度，而队列长度增加，又会增加网络的延迟。
3) maxp 为分组丢弃概率跳转到 1 之前的最大丢弃概率，RED 算法中分组丢弃概率随 avgQ 从 minth 到 maxth 由 0 线性增长到 maxp 。 maxp 决定了拥塞指示程度，取值偏大会导致拥塞指示过重，分组丢弃过多，网络吞吐量降低，缓存区占用也随之下降，取值偏小会导致拥塞指示过轻，缓存区容易溢出，形成DropTail 方式，使系统增加了计算量却不能发挥应有的控制作用，其性能甚至比 DropTail 更差。

2. RED 算法中的平均队列长度随着加入网络的连接数的增加而增加。这使得分组通过中间节点的延迟会因此而增加，将对许多对延迟敏感的网络业务产生影响。

RED 代码模拟实现 C++

[collapse title=”点击展开 查看更多”]

// RED算法.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
// Red.cpp : 定义控制台应用程序的入口点。

//
#include "stdafx.h"
#include"queue"
#include"cstdlib"
#include"iostream"
#include"windows.h"
#include"string"
#include"ctime"
#include"vector"

using namespace std;
int lose = 0;

/计算丢弃报文概率
float getp(float pmax, float la, int thmax, int thmin, int count)/
{
	float ptemp = pmax*(la - thmin) / (thmax - thmin);
	return (ptemp / (1 - count*ptemp));
}

//计算平均队列长度
float getla(float oldla, float newla)
{
	return ((1 - 0.125)*oldla + 0.125*newla);
}

//初始化发送端
void initq(priority_queue &q, string s)
{
	while (q.size()<25)
	{
		q.push(s);
	}
}

void trans(priority_queue &a, priority_queue &q, float la, int thmax, int  thmin, float p, int &count, string s)
{
	if (la0)
	{
		q.push(a.top());
		cout << "接收" << s << "发来的数据" << endl;
		a.pop();
	}
	else if (la >= thmax&&a.size()>0)
	{
		cout << "丢弃" << s << "发来的数据" << endl;
		a.pop();
		lose++;
	}
	else if (la >= thmin&&la0)
		{
			cout << "丢弃" << s << "发来的数据" << endl;
			a.pop();
			lose++;
		}
		else if (a.size()>0)
		{
			q.push(a.top());
			count++;
			cout << "接收" << s << "发来的数据" << endl;
			a.pop();
		}
	}
}

void transport(priority_queue &a, priority_queue &b, priority_queue &c, priority_queue &q, vector &v)
{
	int count, thmax, thmin, i, j, ja, jb, jc;
	float pmax, la, p; la = 0;
	double time;
	clock_t start, finish;
	cout << "输入thmax thmin pmax" << endl;
	cin >> thmax >> thmin >> pmax;
	if (thmax>40)
	{
		cout << "thmax已超过最大路由缓存长度40！当缓存的数据长度等于40时，以后到达的数据将被丢弃";
		thmax = 40;
	}
	start = clock();
	cout << "a b c 向路由器发送数据" << endl;
	while (a.size() != 0 || b.size() != 0 || c.size() != 0)
	{
		count = 0;
		p = getp(pmax, la, thmax, thmin, count);
		j = rand() % 10;
		ja = j;
		j = rand() % 10;
		jb = j;
		j = rand() % 10;
		jc = j;
		if (a.size()>0 && ja % 2 == 0) { cout << "a 向路由器发送数据" << endl; }
		if (b.size()>0 && jb % 2 == 0) { cout << "b 向路由器发送数据" << endl; }
		if (c.size()>0 && jc % 2 == 0) { cout << "c 向路由器发送数据" << endl; }
		if (ja % 2 == 0)
		{
			trans(a, q, la, thmax, thmin, p, count, "a");
		}
		la = getla(la, q.size());
		p = getp(pmax, la, thmax, thmin, count);
		if (jb % 2 == 0)
		{
			trans(b, q, la, thmax, thmin, p, count, "b");
		}
		la = getla(la, q.size());
		p = getp(pmax, la, thmax, thmin, count);
		if (jc % 2 == 0)
		{
			trans(c, q, la, thmax, thmin, p, count, "c");
		}
		la = getla(la, q.size());
		p = getp(pmax, la, thmax, thmin, count);
		if (q.size()>0)
		{
			v.push_back(q.top());
			q.pop();
		}
		//Sleep(100);
	}
	finish = clock();
	time = (double)(finish - start) / CLOCKS_PER_SEC;
	cout << "所有站点数据传送完毕,共用时 " << time << " s" << endl << "丢弃的数据共" << lose << "组" << endl;
	while (q.size()>0)
	{
		v.push_back(q.top());
		q.pop();
	}
	for (i = 0; i a, b, c, d;
	vector v;
	initq(a, "aa");
	initq(b, "bb");
	initq(c, "cc");
	transport(a, b, c, d, v);
	return 0;
}

[/collapse]