Willingness-To-Pay (WTP) Congestion Avoidance
Virtual Queue and Load Based Packet Marking
This page contains our implementations of the Willingness-to-Pay (WTP) congestion avoidance algorithm,
and the Virtual Queue (VQ)and Load-Based Marking (LBM) algorithms, in the ns-2 simulator and in FreeBSD.
- Network Simulator 2 implementation
- FreeBSD implementation
Send comments/questions/problems to
Vasilios Siris (vsiris@ics.forth.gr)
and
George Margetis (gmarget@ics.forth.gr)
This is a congestion avoidance algorithm that increases the congestion window by approximately
kw in one round trip time. Unlike the TCP, which halves the congestion window when congestion is
detected, WTP decreases the congestion window by k*w/cwnd - k.
There is one more different between TCP/ECN and WTP: whereas TCP/ECN
decreases the congestion window once for every round trip time, WTP
decreases it for every ECN mark (actually ECN Echo) received;
hence, how the receivers
send ECN echo bits to the senders is also different.
The Virtual Queue marking algorithm maintains a virtual buffer, with capacity and buffer limit some percentage
theta of the link's capacity and buffer. The algorithm marks all packets that arrive at the link from the time a loss
occurs in the Virtual Queue, until the time the Virtual Queue empties.
According to this algorithm, the marking probability is a function of the average load,
measured over some time interval.
Network Simulator 2 implementation
Here there is a file with the instructions
for adding the modules to ns-2.
The table below contains all the modules needed for the installation.
WTP objects are a subclass of TCP objects that implement the willingness to pay
congestion avoidance algorithm [GK99,ACMSS00].
A WTP agent is created by using the command:
set tcp [new Agent/TCP/WTP]
w_ | Weight
(willingness-to-pay) factor of WTP |
k_ | Gain factor of WTP |
slowstart_on_ | If true then slowstart is used |
|
GKQ objects are a subclass of Queue objects that implement
Virtual Queue and Load Based Marking algorithms.
A link is configured to use gkq by using the commands:
$ns simplex-link node1 node2 bw delay GKQ
or
$ns duplex-link node1 node2 bw delay GKQ
NOTE Virtual Queue marking
is enabled by setting
mark_method_ to 1, and Load Based marking is enabled
by setting mark_method_ to 0.
queue_in_bytes_ | If true then
the size of queue is measured in bytes. |
interval_ | Interval (in msec)
over which the average load is calculated |
min_thresh_ | Minimum
threshold for the average load (marking occurs above this value) |
max_thresh_ | Maximum
threshold for the average load (slope of marking curve = 1/(max_thresh_-min_thresh_)) |
virtual_factor_ | Specifies that
the virtual queue's size and capacity will be virtual_factor_*100 % of the
real queue size and capacity respectively |
queue_in_bytes_ | For the virtual
queue strategy this parameter is always true |
|
WTP with LBM scenario
WTP with VQM scenario
NS 2 official page
NS 2 download and installation instructions
FreeBSD official site
FreeBSD implementations
Here there is a file with the instructions
for adding the above to FreeBSD kernel.
The table below contains everything that is needed for the installation.
In order to conduct experiments with TCP - WTP you need a test bed similar to that shown in Figure 1
The edges are FreeBSD 3.x with a kernel with the TCP-WTP patch. The router can be a router with ecn support,
or a FreeBSD workstation with altq v2.2, to which the patch (see link above) implementing the virtual queue
marking algorithm can be added.
The configuration of the TCP - WTP algorithm at the edges is achieved by using the
setsockopt system call.
The variables for the willingness to pay congestion control are the following:
wtp_w |
Weight (willingness-to-pay) factor of WTP |
wtp_invk |
Inverse value of gain factor of WTP |
ecn_counter |
Counter for CE bits that have been received |
TCP_SETWTP |
Setsockopt command used to enable or not WTP congestion control |
TCP_SETW |
Setsockopt command used to set the value of weight factor |
TCP_SETINVK |
Setsockopt command used to set the inverse value of gain factor |
|
In our implementation, the Virtual Queue is not a new class for altq, rather we used the existing red class
and indicate that the Virtual Queue algorithm is to be used when the min
threshold is equal to 0.
The variables for the virtual queue algorithm are the following:
bandwidth |
capacity of the virtual queue
|
virtual_buffer |
buffer limit of the virtual queue
|
virtual_bcount |
queue length of the virtual queue
|
last_time_vb |
time the previous packet was received
|
time_now |
time the current packet was received |
mark_flag |
true when packets are to be marked |
|
Virtual Queue example
WTP example
Pseudocode for Virtual Queue implementation
Alternate Queue software page
FreeBSD official site
[GK99] Resource pricing and the evolution of congestion
control , R.J. Gibbens and F.P. Kelly, Automatica 35 (1999), 1969-1985.
[ACMSS00] Efficient adaptation to dynamic
pricing communicated by ECN marks: Scenarios for experimental assessment , P. Antoniadis, C. Courcoubetis, G.
Margetis, V. A. Siris, and G. D. Stamoulis, SPIE International Symposium on Information Technologies 2000,
November 2000.
[SCM01] Service differentiation in ECN networks using weighted window-based congestion control for various packet marking
algorithms, Vasilios A. Siris, Costas Courcoubetis, and George Margetis, April 2001.