At each clock tick, each User creates packets. It sends them on to Resources, and tells them where to go once the Resource has finished with them. Typically, packets go through a sequence of Resources, before the User counts them to see how many got through and how many were marked.
At each clock tick, each Resource processes the packets that it has received. It may drop packets, and it may mark them. Once it has finished with them, it sends them on to wherever the User specified. A typical Resource queues up packets, dropping them if the number of packets in the queue exceeds the buffer size, possibly marking them, and serves them at a constant rate.
This is a very general description of the model, and it is usually easier to write your own Users and Resources using restricted interfaces. Two of these are given below.
Users represent people who want to send data. A FlowControlStrategy is the simplest sort of adaptive user. It is given a route, asked how many packets to send, and told how many were marked or dropped. It is defined like this.
public class SingleFlow.FlowControlStrategy
{
double updateRate(FlowControlStrategy.MarkInfo lastMarks);
}
public class SingleFlow.MarkInfo
{
int getMarks();
int getDropped();
double getCost();
}
The FlowControlStrategy.updateRate() function should
be overridden to return the number of packets to send in the next timestep.
The lastMarks.getMarks() function gives the number of
marked packets that have left the network on this User's route in the
last timestep. The lastMarks.getDropped() function
estimates how many packets were dropped, by looking at the serial numbers
of the received packets. And lastMarks.getCost() gives an
indication of the overall cost to the User, given by
getMarks()+k*getCost(), where k can be set
by the experimenter.
Here is an example. You can watch it running.
public class UserW extends SingleFlow.FlowControlStrategy
{
public UserW()
{ k=0.1; w=0.05; }
public double updateRate(SingleFlow.MarkInfo lastMarks)
{
X = (int)Math.max(Math.floor(z+x),0);
z = x+z-X;
x = x+k*(w-lastMarks.getCost()));
return X;
}
double k;
double w;
double x=0;
double z=0;
int X=0;
}
Resources represent network elements like switches, which receive packets from the Users and may drop them if too many arrive. They may additionally mark packets, to indicate to the User that there is congestion. The theory is that the resource should generate marks according to the shadow price of the work it receives. That is, if removing a unit of work w would result in the resource being able to carry an extra unit of work, then it should charge the User for packet w
An example of a Resource is a QueueResource. This can serve a fixed number of packets every time slot. If more packets arrive than can be served, they they are stored in a queue. If the queue exceeds a fixed buffer size, some packets will be dropped. To prevent overflow occuring too frequently, the queue can mark packets, with a class defined like this.
public class QueueResource.QueueMarkingStrategy
{
void mark(QueueResource.Queue queue);
}
public class QueueResource.Queue
{
int getBufferSize();
int getServiceRate();
int size(); // total number of packets, before any have been dropped or served
int getNumPacketsJustArrived(); // number of packets that arrived this timeslot
boolean isMarked(int index); // whether this packet has been marked
boolean isToBeDropped(int index); // whether drop() has been called for this packet
void mark(int index); // index=0 is head of the queue
void drop(int index); // packets are only dropped at the end of the timeslot
}
The QueueMarkingStrategy should indicate which packets are to
be marked or dropped. Once it has finished, the getServiceRate() packets at
the head of the queue are served. If the number remaining exceeds
getBufferSize(), they are dropped.
Here, for example, is the MarkAsSmallerQueue strategy. It
feeds arriving packets into a virtual queue with theta times
the original service rate and buffer size.
It marks any packets which arrive between
when the virtual queue overflows and the next time the virtual queue
idles.
public class MarkAsSmallerQueue extends QueueResource.QueueMarkingStrategy
{
double theta=0.9;
double q=0;
boolean amMarking=false;
public void mark(QueueResource.Queue queue)
{
int a=queue.getNumPacketsJustArrived();
double vC=theta*queue.getServiceRate();
double vB=theta*queue.getBufferSize();
int M=queue.size();
int m=M-a;
// Check if overflow and idling
q=q+a-vC;
if (q<0) amMarking=false;
if (q>vB && !amMarking)
{
amMarking=true;
for (int i=0; i<m; i++) queue.mark(i);
}
q=Math.min(vB,Math.max(q,0));
// Mark packets
if (amMarking)
for (int i=m; i<M; i++) queue.mark(i);
}
}