原文地址 ：http://selab.whust.com/Display_Diary.aspx?DiaryID=47
实验目的
学习DropTail 和 RED 队列管理机制，以了解主动式和被动式队列管理的优缺点。
【DropTail 和被动式队列管理机制】
在Internet中最简单也最普遍的队列管理机制就是DropTail。当一个数据报到达队列时，就把数据报放到队列中等待被传送，但由于队列长度是有限的，因此如果数据流太大，而队列没有空间去暂存这些新到的数据报，就会把队列最尾端的数据报丢弃，这样的管理机制就叫做DropTail。很多时候，DropTail队列管理机制会与FIFO（First In First Out）相结合，整个运作方式为：数据报传送的顺序与封包进入队列的顺序相同，先进入队列的封包先传送出去，后进入队列的封包较晚传送出去。如果队列长度超过暂存空间的大小，就会把队列最尾端的数据报丢弃。DropTail在丢弃数据报时，并不会去考虑要丢弃的数据报属于哪个数据流，只是单纯的把超过暂存空间大小的数据流丢弃，因此DropTail队列管理机制的最大优点就是实际操作简单。但是，有利有弊，正是由于这个特性，使得队列在相当长的时间内处于充满或几乎充满的状态。而队列管理机制最重要的目标之一是降低稳定状态下队列的长度，因为端点到端点的延迟主要由队列中排队等待造成的。
此外，DropTail容易造成TCP全局同步（TCP Global Synchronization）问题。由于Internet 上的数据流都具有突发性，到达路由器的封包也往往是突发的。如果此时队列处于充满或几乎充满状态，就会导致在短时间内连续大量的丢包。而TCP数据流具有自适应特性（Adaptive），来源端发现封包丢失就会急速降低传送速度，于是网络拥塞情况得到缓解。但来源端在发现网络不再拥塞后又开始增加发送速度，最终又造成网络拥塞。这种现象就像一个循环，周而复始的进行下去，致使网络长期处于链路利用率很低的状态，降低了整体的吞吐量，这正是传说中的“TCP全局同步”现象，这个现象，我们会在后面的实验中通过网络仿真产生的数据和图形进行验证。
除了DropTail外，另外两种在队列满时用得比较多的队列管理机制是Random Drop 和 Drop Front。当队列满时，前者从队列中随机找到一个数据报丢弃，让新来的数据报进入队列；后者从队列前端把数据报丢弃，以便新来的数据报进入队列。但这两种队列管理机制仍然存在“满队列”问题。由于这几种方法都是在队列满时被迫丢包，因此被称为被动式队列管理。
【RED和主动式队列管理机制】
与被动式队列管理机制在队列满时被动丢包相比，主动式队列管理机制在队列未满时就开始按一定概率丢弃数据报。这样未雨绸缪，对具有拥塞控制的传送端做流量速度管制，以避免满队列被迫丢包的两种负面影响：端点到端点的延迟时间过长，链路利用率过低。而RED（Random Early Detection）就是一种典型的主动式队列管理机制。
RED队列管理机制使用平均队列长度来预测即将发生的网络拥塞，并采用随机选择的方式对数据报进行丢弃，使得拥塞发生前就会有拥塞控制的传送端提示要进行流量速度管制，以避免拥塞发生。与此同时，由于RED是采用随机的方式来丢弃封包，因此不同的TCP数据流对拥塞情况的反应不同步，因而解决了“TCP全局同步”现象。
简言之，RED路由器由两个独立的算法组成：1.计算平均队列长度（avg）的算法决定了路由器队列容纳突发性数据的程度；2.计算丢包概率（Pb）的算法决定了在当前拥塞程度下，路由器丢弃分组的概率。
RED计算平均队列长度是采用加权平均方式，计算公式如下：
avg = (1- Wq)* avg + Wq * q
其中，avg是平均队列长度，q是目前实际的队列长度，Wq 为目前实际的队列长度加权系数，其值在0与1之间。一般而言，设置得比较小，以便计算出来的平均队列长度变化得比较慢，不会因为突发流量的到来而使平均队列长度增加得过快，造成大量封包丢失。
决定要丢弃封包依据两个阈值minth 和maxth ，当平均队列长度avg 小于minth 时，所有的封包都允许进入队列，但当avg超过maxth 时，所有的封包被直接丢弃，当avg介于minth 和maxth 时，则根据下面的概率公式来丢弃封包。
Pb = maxp * （avg - minth）/（maxth- minth）
其中的maxp为网管预先设置的丢弃概率值，Pb 为目前封包丢弃的计算值，其值变化如下图所示：
而RED再真正决定是否要丢弃数据报，并不是采用Pb ，而是对Pb 进行如下修改，以作为实际封包丢弃概率：
Pa = Pb / （1- count* Pb）
其中，count记录了上一个封包丢弃后有多少数据报进入队列。采用 Pa 是希望能让数据报丢弃概率的分布更均匀。
可见，若想有效的使用RED，适当选择Wq ，minth ， maxth ，maxp 等参数很关键。1993年 Floy S，Jacobson 发表了一篇题为“Random early detection gateways for congestion avoidance”的论文，将RED的算法，参数的设置，实验的结果详细的进行了分析和论证，大家可以在网上下载，进行参考。
说了这么久，我们终于可以开始做实验了！
1. 仿真的网络结构图
可能大家对这个结构图已经不陌生了，r1和r2是路由器，其中的链路采用DropTail和RED队列管理机制以作为效率分析的比较，频率为56kbps，传输延迟为10ms。其中的数据流数目可由用户在模拟时决定，下面的例子为10条TCP数据流。我们要比较的效率是这10条数据流的平均吞吐量、第一条数据流的端点到端点平均延迟时间和队列长度变化。
2. TCL程序代码 （假设我们将程序代码保存于/home/ns下的queue.tcl中）
if {$argc !=2} {
puts "Usage: ns queue.tcl queuetype_ noflows_"
puts "Example: ns queue.tcl DropTail 10"
puts "queuetype_: DropTail or RED"
exit
}
set par1 [lindex $argv 0]
set par2 [lindex $argv 1]
#产生一个仿真的对象
set ns [new Simulator]
#打开一个trace文件，用来记录数据报传送的过程
set nd [open out-$par1-$par2.tr w]
$ns trace-all $nd
#结束一个结束的程序
proc finish {} {
global ns nd par2 tcp startT
$ns flush-trace
close $nd
set time [$ns now]
set sum_thgpt 0
# throughput = 收到ACK数 * Packet Size(Bit) / 传送时间
# 收到Ack数 = 传送出Packet 数
for {set i 0} {$i < $par2} {incr i 1} {
set ackno_($i) [$tcp($i) set ack_ ]
set thgpt($i) [expr $ackno_($i) *1000.0*8.0/($time-$startT($i))]
#puts $thgpt($i)
set sum_thgpt [expr $sum_thgpt+$thgpt($i)]
}
set avgthgpt [expr $sum_thgpt/$par2]
puts "average throughput: $avgthgpt (bps)"
exit 0
}
#定义节点
for {set i 0} {$i<$par2} {incr i 1} {
set src($i) [$ns node]
set dst($i) [$ns node]
}
#产生两个路由器
set r1 [$ns node]
set r2 [$ns node]
#把结点和路由器连接起来
for {set i 0} {$i<$par2} {incr i 1} {
$ns duplex-link $src($i) $r1 100Mb [expr ($i*10)]ms DropTail
$ns duplex-link $r2 $dst($i) 100Mb [expr ($i*10)]ms DropTail
}
$ns duplex-link $r1 $r2 56k 10ms $par1
#设置r1和r2之间的Queue Size 为50个数据报大小
$ns queue-limit $r1 $r2 50
#记录队列长度
#Recording the length of queue
set q_ [[$ns link $r1 $r2] queue]
# set queuechan [open q-$par1-$par2.tr w]
# $q_ trace curq_
if {$par1=="RED"} {
#Using packet mode
$q_ set bytes_ false
$q_ set queue_in_bytes false
}
# $q_ attach $queuechan
for {set i 0} {$i<$par2} {incr i 1} {
set tcp($i) [$ns create-connection TCP/Reno $src($i) TCPSink $dst($i) 0]
$tcp($i) set fid_ $i
}
#随机在0与1之间决定数据流开始传送的时间
set rng [new RNG]
$rng seed 1
set RVstart [new RandomVariable/Uniform]
$RVstart set min_ 0
$RVstart set max_ 1
$RVstart use-rng $rng
for {set i 0} {$i<$par2} {incr i 1} {
set startT($i) [expr [$RVstart value]]
#puts "startT($i) $startt($i)sec"
}
#在指定时间，开始传送数据
for {set i 0} {$i<$par2} {incr i 1} {
set ftp($i) [$tcp($i) attach-app FTP]
$ns at $startT($i) "$ftp($i) start"
}
#在第50s时区调用finish来结束模拟
$ns at 50.0 "finish"
$ns run
3. 执行方法和执行结果
（1）10条TCP数据流，采用DropTail 队列管理机制：
[root@localhost ns]# ns queue.tcl DropTail 10
average throughput: 4353.6337788880564 (bps)
（2）10条TCP数据流，采用RED队列管理机制：
[root@localhost ns]# ns queue.tcl RED 10
average throughput: 4789.3897693204663 (bps)
结果分析：从上面的数据可知，在只有10条TCP数据流的情况下，RED队列管理机制得到的吞吐量高于DropTail队列管理机制。
知识拓展：上面是10条TCP数据流，我们还可以将数据流的数目改为15,20,25,30等，然后观察平均吞吐量（average throughput）
4. 端点到端点平均延迟的awk程序 （假设我们将此awk程序保存于/home/ns下的measure-delay1.awk中）
#这是测量第一条TCP数据流数据报端点到端点间平均延迟时间的awk程序
#我们可以根据这个程序，举一反三，写出测量第2条以至第n条TCP/UDP
#数据流的awk程序
BEGIN {
#程序初始化，设置一变量以记录目前最高处理数据报的ID
highest_packet_id = 0;
}
{
#与trace文件结构对应
action = $1;
time = $2;
from = $3;
to = $4;
type = $5;
pktsize = $6;
flow_id = $8;
src = $9;
dst = $10;
seq_no = $11;
packet_id = $12;
#记录目前最高的packet ID
if( packet_id > highest_packet_id )
highest_packet_id = packet_id;
#记录第一条TCP（flow-id=0）的接收时间
if ( start_time[packet_id] == 0 )
start_time[packet_id] = time;
#记录第一条TCP（flow-id=0）的接收时间
if( flow_id==0 && action!="d" && type=="tcp" ) {
if ( action == "r" ) {
end_time[packet_id] = time;
}
} else {
#把不是flow-id=0 的封包或则flow-id=0 ，但此封包被drop的时间设置为-1
end_time[packet_id] = -1;
}
}
END {
sum_delay=0;
no_sum=0;
#把数据全部读取完后，开始计算有效数据报的端点到端点延迟时间
for( packet_id = 0; packet_id <= highest_packet_id; packet_id++ ) {
start = start_time[packet_id];
end = end_time[packet_id];
packet_duration = end-start;
#只把接收时间大于传送时间的记录列出来
if( start < end ) {
#print ("%f %f/n",start,packet_duration);
sum_delay+=packet_duration;
no_sum+=1;
}
}
#求出数据报端点到端点的平均延迟时间
printf( "average delay: %f sec/n",sum_delay/no_sum );
}
5. 执行方法和执行结果：
（1）10条TCP数据流，采用DropTail队列管理机制
[root@localhost ns]# awk -f measure-delay1.awk out-DropTail-10.tr
average delay: 4.379053 sec
（2）10条TCP数据流，采用RED队列管理机制
[root@localhost ns]# awk -f measure-delay1.awk out-RED-10.tr
average delay: 1.237935 sec
结果分析：从上面的数据可知，在只有10条TCP数据流的情况下，RED队列管理机制得到的端点到端点的平均延迟时间低于DropTail队列管理机制。
6. 使用gnuplot 观察DropTail 和RED 队列长度变化（假设我们要分析的q-DropTail-10.tr 和q-RED-10.tr文件都保存在/home/ns中）
[root@localhost root]# cd /home/ns
[root@localhost ns]# gnuplot
G N U P L O T
Version 3.7 patchlevel 3
last modified Thu Dec 12 13:00:00 GMT 2002
System: Linux 2.4.20-8
Copyright(C) 1986 - 1993, 1998 - 2002
Thomas Williams, Colin Kelley and many others
Type `help` to access the on-line reference manual
The gnuplot FAQ is available from
http://www.gnuplot.info/gnuplot-faq.html
Send comments and requests for help to
Send bugs, suggestions and mods to
Terminal type set to 'x11'
gnuplot> plot "q-RED-10.tr" using 2:3 with linespoints 1
显示图形如下：
按照同样的方法进入gnuplot，然后输入：
gnuplot> plot "q-DropTail-10.tr" using 2:3 with linespoints 2
^
得到的结果为： x range is invalid
为什么呢？
我们从/home/ns中打开文件q-DropTail-10.tr，查看，发现此文件是空的。
原因何在呢？
我们来看queue.tcl中的这段代码：
#记录队列长度
#Recording the length of queue
set q_ [[$ns link $r1 $r2] queue]
# set queuechan [open q-$par1-$par2.tr w]
# $q_ trace curq_
if {$par1=="RED"} {
#Using packet mode
$q_ set bytes_ false
$q_ set queue_in_bytes false
}
# $q_ attach $queuechan
我们把记录队列长度的核心代码set queuechan [open q-$par1-$par2.tr w] 、$q_ trace curq_ 、$q_ attach $queuechan 给注释了！之所以这样做，是因为NS2中并没有提供追踪DropTail队列长度的功能。因此，现在的关键在于，如何在NS2中添加追踪DropTail队列长度的新协议。
这个问题还待研究。。。。。。
