QSS Boundary Conditions

The question is: how to implement boundary conditions in QSS without using the sample&hold model (which can bring big headaches to set the samplingPeriod)

Example and problem

If we want to implement the following equation (modeling a buffer):


 \begin{displaymath}  \frac{d Q(t)}{dt} = A(t) - C \  \end{displaymath}(1)

boundary condition: $ 0 <= Q(t) <= Q_{max} $

Where C and Q_max are constant parameters. A(t) is the input rate and can be modeled with any function.

Without the boundary conditions it would be implemented as follows:

For the following input would not respect the boundary conditions:

There are 2 problems to solve:

  1. Respecting the boundary conditions
  2. Detecting the boundary crossing point. These can be done in an exact way, or with a contraied error.

Keeping boundaries

Option: as in TCP-AQM (too many oscilations)

This is the model implemented in the TCP-AQM model (only that without the sample&hold)


 \begin{displaymath}  \frac{d Q(t)}{dt} = A(t) - C if 0 <= Q(t) \ \end{displaymath}(2)

 \begin{displaymath}  \frac{d Q(t)}{dt} = A(t) if NOT \ \end{displaymath}(3)



Which can be implemented as follows. The switch model condition would be: q(t)>0 then C else 0

This solution works well in some conditions, but in this example the simulation reaches T=6' and can not advance further:

Parameters:

linkCapacity = 100; // (bits/s)
stepTimeChanges = [0, 1, 2, 3, 4, 8];
stepValueChanges = [0, linkCapacity*3, 0, linkCapacity, linkCapacity/2, linkCapacity*2 ];

problem:

This implementation makes the simulation to execute SUPER LONG TIMES (almost hangs) frown

As it can be seen the model osciles around the boundary conditions almost indefinetly when the inputRate>0 && inputRate<linkCapacity.
In the QSS execution what happens is:

  1. When the q(t)>0, the switch model outputs C and the sum model outputs A-C that is <0. So the input to the integrator is <0 and the function decreases.
  2. At one point the integrator reaches 0
  3. The switch model detects the crossing condition (q(t) < 0), so it outputs 0
  4. The Sum model outputs A (which is positive)
  5. This makes the integrator to have a positive derivate so starts growing
  6. The switch model detects q(t) >0, so it outputs C
  7. We go back to 1 and loop

Option : changing dqrel (not a solution for all scenarios)

One possible option to the previous approach is to set the dqrel=1 in the integrator. This makes the ocilations to be more distant in time: the integrator updates its status only when there is a difference >1, which for a queue can make sense (see plot on the left).

But still the ocilations exist, so the model becomes a bit slow in those intervals.

Also the dqrel value to use is a "magic number" without a real justification.If we change the inputRate=100Gb/s (instead of just 100b/s) and the integrator is not that accuarate (it goes to negative values, see plot on the right).

linkCapacity = 100 *G; // (bits/s)
stepTimeChanges = [0, 1, 2, 3, 4, 8];
stepValueChanges = [0, linkCapacity*3, 0, linkCapacity, linkCapacity/2, linkCapacity*2 ];

Interesting is that if we add an extra output value in the generator but with same value, I would expect nothing to change, but it does: simulation finished, there are no oscilations, but the queueSize goes negative!!

linkCapacity = 100 G; // (bits/s)
stepTimeChanges = [0, 1, 2, 3, 4, 6, 8];
stepValueChanges = [0, linkCapacity*3, 0, linkCapacity, linkCapacity/2, *linkCapacity/2
, linkCapacity*2 ];

Option 4: switch model (not working)

Option : Switch model attempt 2 ( seems to work, but misses the crossing point )

To implement the boundary conditions we could change the equation as follows: setting a derivate 0 when the boundaries are reached, and add an extra condition for staying with q'(t)=0

if ( Q(t) > 0 OR A(t) - C > 0 ) :


 \begin{displaymath}  \frac{d Q(t)}{dt} = A(t) - C \  \end{displaymath}(4)

If not

(which means condition) --> Q(t) <= 0 AND A-C<=0

 \begin{displaymath}  \frac{d Q(t)}{dt} = 0 \end{displaymath}(5)

Implemented in PowerDEVS blocks:

Result:

The value of Q(t) stays always "aproximately" >=0 and without oscilations!

Still to check:

The queueSize it is not always EXACTLY >=0. There are times when it goes slightly below 0

queueSize
queueSize =

value: [0,1,2.000D+11,1.000D+11,9.990D+10,-0.0000305,0.9999695]
t: [0,1,2,3.002,4.002,6.001998,8]

Boundary crossing detection

Option: bounded integrator

To fix the problem of option (detecting exactly the moment the function crosses 0), the integrator need to output the calculation of x(t) (instead of just q(t)).

For this, new atomic models need to be developed: new Bounded QSS Integrator

Option: restricting values using the rest port

There are two possible options: 1) using a reset integrator so as to set the value to 0 when it goes below, or 2) use a saturation model to prevent other models to see the negative values.

Just the integrator:

The queueSize value goes below cero. Also the crossing time (queueSize.t) is a bit shifter by ~2ms:

QueueSize.value = [ 0, 0.99999999999999989, 99999999999.666656, 99999999999.999985 , 99899999999.9999847, - 0.000030517578125 , 0.99996948242187489]
QueueSize.t .......= [0, 1.000000000005 , 2.00000000000333333, 3.00199999999999667, 4.00199999999999978, 6.00199800000000039, 28.0000000000100009]

With Reset:

The queueSize value goes exactly to cero. Also the crossing time (queueSize.t) is exact (6s). It works for QSS2/4

QueueSize.value = [0, 0.99999999999999989, 199999999999.666656, 99999999999.999985 , 99899999999.9999847, 0, 0.99999999999999989]
QueueSize.t .......= [0, 1.000000000005 , 2.00000000000333333, 3.00199999999999667, 4.00199999999999978, 6, 28.0000000000100009]

For QSS1 the value is actually reset to exactly 0. But the crossing time is not exact (numerical error?) :

QueueSize.value = [....., 0.02223399732821360, 0.02221176333088538, 0 , 0.17775571612105948, 0.17793347183718053, .......]
QueueSize.t .......= [....., 5.99999999999991385, 5.99999999999991473, 5.99999999999991562, 28 , 28.0000000000000036, .......]

It also works for BQSS, CQSS (but produces negative values) and . For LIQSS1, LIQSS2, LIQSS3 it does not work. Probably because all the model say they only support (QSS1 to 4)

Both boundaries together

We need to implement the following equations with conditionals:

(online here)

Higher boudary

The higher boundary is very similar:

- It requires the queueSize to change signd (the "-1" model) so as to respect the < (if not it works as a <=)
- The reseter model is condigured to check for highBoundary detection (sends events when the input is higher than the value)
- In the image we are using a saturation model in comparison with the previous screenshot. It has the same effect, but it is simpler.

Bounds controller

The idea would be to program a new atomic model: similar to the saturator (on the input of q(t)), but which should output the values from the incomming ports1:3, depending on the saturation status.

(online here: https://www.draw.io/#G0B0Spz4YE9z7_N1R0TTA1RUxtZW8)

Depending on the value of q(t) there can be 3 states:

  1. q(t)>MAX HighStaturation, so the model outputs the values from port1,
  2. q(t) <=0 LowSaturation, so the model outputs the values from port3
  3. 0<= q(t) <= MAX NoSaturation, so the model outputs the values from port2.
If the 4 input ports are connected as in the first image, it would effectively bound the integrator values.

TODO: the rest port should be used and is not in this design... but should be simple to set?

Final solution: Mimic logical operators (AND & OR)

The idea is to use the comparator, sum, and multiplication atomic models to mimic logical operators and use them to implement the conditios. The input value of the integrator (q'(t)) is either 0 or A-C. But the conditions where each should be used is not that simple to implement in blocks.

To implement logical operations new models could be developed. But it would be time-consuming, we implemented them sub-optimally using aritmethic operations as follows:

AND(a,b) = a * B
OR(a,b) = a+b - (a*b)
NOT(a) = -a + 1

Also we implemented de >, >=, < and <= using the comparator QSS model (which already detects crossings). These operators were added to a new library.

(online here)

We implemented the logical condition of the equation above, the "IF NOT" part because it seems easier. So, if the conditions are met, the models output q'(t)=0. If conditions are not met. the model output q'(t) = A-C.

We gathered this big model that check all conditions and outputs the q'(t) necesary to keep q(t) bounded in a coupled model, so that it can be reused for any other model. Then the inputs for this coupled model are: 1) The output of the integrator q(t) (in our case the queueSize); 2) the acceleration q'(t) (in our case A-C) ; 3) the MAX; 4) the MIN values for q(t).

Tests for this boundedQueue can be found in https://twiki.cern.ch/twiki/bin/view/Main/TDAQSimulations_hybrid_continousQueueModel

Adding reset

With the logical operators the integrator value stays bounded. But still we observed that it goes above or below the boundaries by a small error. We use the same technique as before using the reset input port of the integrator.

Using the logical operators it is now easy to detect when the integrator should be reset: when either q(t)>=MAX or q(t)<=0.
We developed a new atomic model that mimics the cross_detection model. The cross_detect model can only output a constant fixed value (received by parameter). The new model outputs the value received by the input port (in this queue model either MAX or MIN).

New Generic features added to PowerDEVS

As a result of this new generic features were added to PowerDEVS:

  1. A new (coupled) model was implemented which, in conyection with the QSSIntegrator, implements a bounded integrator.
  2. A new library of models that implement logic and comparison operators: >, >=, <, <=, AND, OR, NOT
-- MatiasAlejandroBonaventura - 2017-03-28
Edit | Attach | Watch | Print version | History: r11 < r10 < r9 < r8 < r7 | Backlinks | Raw View | WYSIWYG | More topic actions
Topic revision: r11 - 2017-05-09 - MatiasAlejandroBonaventura
 
    • Cern Search Icon Cern Search
    • TWiki Search Icon TWiki Search
    • Google Search Icon Google Search

    Main All webs login

This site is powered by the TWiki collaboration platform Powered by PerlCopyright & 2008-2019 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback