Subject: [PCN] Creating 3SM system behaviour with CL marking behaviour

From: <[email-masked]>
Date: Fri, 15 Feb 2008 17:40:22 -0000

At Vancouver, some of us agreed to make the working assumption of "CL
marking behaviour" & see if we could create (approximate) "3SM system
behaviour" by doing something different at the PCN-boundary-nodes. In
particular this concerns flow termination (for admission, the 3SM & CL
marking algorithms are essentially the same).

The good news is that I think this is very possible. Hoping so & I
haven't mucked up!

See
http://www.watersprings.org/pub/id/draft-charny-pcn-comparison-00.txt
for a description of CL & 3SM

The problem:
In 3SM, receipt of a termination marked pkt by a PCN-egress-node means
"terminate this flow". With the CL marking algo, PCN-interior-nodes
termination mark all pkts in excess of the PCN-upper-rate. So combining
CL marking with 3SM boundary node behaviour would lead to too many flows
being terminated - because there's a time delay between a pre-congested
router termination marking and the flow actually being terminated. 3SM
solves this problem by the PCN-interior-nodes "slowing down" their
marking.

The idea:
When the boundary node sees a termination marked pkt, then it terminates
the flow with some probability.
So this is doing "slow down" at the edge (instead of at the interior
router).

I studied the following scenario:
(intended to be identical to that
http://www.watersprings.org/pub/id/draft-babiarz-pcn-3sm-01.txt)

PCN-upper-rate = 800kb/s 
Initial excess rate = 800kb/s
1 flow = 80kb/s = pkt every 20msec
RTT = 50ms = delay between marking & flow termination

As an approximate model of what would really happen, I divide time into
50ms granularity (ie I assume the rate of marked pkts is constant for
50ms, then changes according to the number of terminated flows, then is
constant for another 50ms, then changes etc. So the rate of termination
slows down, in steps)

So in a 50ms period, we have a binomial distribution (n, p) = (number of
experiments, probability of success):
n = number of pkts marked by pre-congested node in 50ms period
p = probability of terminating a marked flow.

A smaller p means that it takes longer to get rid of all the excess
flows, but a lower risk of significant over-termination.

p = 0.19 (I think this is equivalent to draft-babiarz-pcn-3sm, which
uses a "slowdown" parameter of 1064/200 (= 1/0.19))

The mean number of terminated flows is np, in a 50ms period.
We also get a probability for marking too few or far too many flows. We
have to decide what is "far too many"; eg in the example above with
10flows in excess, we might decide that terminated 14flows is
unacceptable.
So we can look in the CDF of the binomial to find out what the chance is
of terminating 14 or more flows in this period.

For the next 50ms period, then re-do the binomial distribution, with a
mean of np less than before - and repeat.

Result:
Running this model (in Excel) gives:
After 5 iterations (=300msec, 50ms added because of RTT), there'll be
fewer than 1 flow in excess. 
Prob (terminating 14flows) = 0
Even Prob (terminating 12flows) is only about 1%

With p = 0.097, termination completes in about 550ms (cf draft-babiarz
slowdown of 2064/200)
With Prob (terminating 12flows) 0.001%

These results are the same as in the 3SM draft /slides of those
simulations.

Of course p can be set too big, eg doubling p to 0.38 gives 
Prob (terminating 12flows) 10%

(Incidentally, a few goes suggests the over-termination mainly occurs
near the end, ie in the last one or two 50ms periods that any
termination is done)

Approximations:
When deciding what n to use for the 2nd period of 50ms (n= number of
marked pkts), it's an approximation to subtract the mean (np) for the
previous period. Really should use a distribution for how much was
terminated in the previous 50ms. But it's intuitively a reasonable thing
to do - if fewer flows get terminated than expected in the first period,
then chances are more will get terminated in the 2nd period, so the
inaccuracy will tend to disappear.
We (Ben) have built a little matlab program, which doesn't do this
approx, because it uses fluid model equations. It (limited test) gives
similar answers - out of time today to type more.

The sources are basically CBR. I don't think this makes much odds -
think a fluid approx is quite good. eg if the VBR sources in one 50ms
period are quieter, there'll be fewer marked pkts, hence less
termination, but they'll probably be more active in the next 50ms
period. You'd expect a greater chance of over-termination (imagine
you've really terminated enough, but the VBR source happen to transmit
more than usual, then you'll still get excess traffic & the chance of
some termination). However, I don't think the issues are any different
for 3SM edge behaviour & the edge behaviour described here.

I've ignored 'double termination'. Ie you could get a marked pkt &
probabilistically decide the flow should be terminated (as per above),
but actually you've already terminated this flow. I'm not sure what
you'd do in reality, but effectively I've assumed you terminate another
flow. Could model this by reducing the granularity period from 50ms (say
to 10ms) but still keeping the RTT to 50ms (time to terminate after
router marks).

More work:
So basically I think this idea looks good. It would be nice to check it
in the 3SM simulations - Michael, I remember you said in Vancouver that
you'd be trying to simulate it, did you get a chance?
Eg test with different traffic sources.

Why might you want 3SM behaviour:
CL edge behaviour measures the rate of marked pkts in the
ingress-egress-aggregate (so as to help decide how much to terminate).
If the topology is such that the pkts through the pre-congested node
belong to many ingress-egress-aggregates, then it may take a long time
to measure the rate with any accuracy; and even then, if there are only
a few flows (eg 1) on the aggregate, then a probabilistic decision still
has to be made whether to terminate the flow. 

On the other hand, if the pre-congested node is traversed by not so many
ingress-egress-aggregates, then there are enough pkts for the egress to
measure rate in a short time period. Alternatively, the edge could run
the probabilistic behaviour above. Or just count until it has seen x
marked pkts. 

Note that the above behaviour is very dependent on the RTT (time to
terminate after router marks). Eg with RTT = 500ms, you have to make p
much smaller. making p factor of 10 less again gives all termination in
about 5 RTTs. The probability of termination too many flows is also
similar (eg Prob (terminating 12flows) = 1% or so)

phil

> -----Original Message-----
> From: Eardley,PL,Philip,CXR9 R
> Sent: 19 December 2007 15:33
> To: [email-masked]
> Cc: Eardley,PL,Philip,CXR9 R; 'Jozef Babiarz'; 'Anna Charny
(acharny)';
> 'Kwok-Ho Chan'; 'Michael Menth'; Briscoe,RJ,Bob,CXR9 R;
> Moncaster,T,Toby,CXR9 R; 'Tom Taylor'; 'Tina TSOU'
> Subject: RE: PCN dinner consensus
> 
> PCN-ers,
> Several of us [cc'd] met over a couple of "corridor" meetings. We've
> agreed a way forward until Philadelphia in terms of where we're going
to
> concentrate our particular efforts, in order to increase the chances
of
> success on the Milestone '(Pre-)Congestion Detection within a DiffServ
> Domain' due March 2008.
> 
> Over the next few months, we will make the working assumption of the
"CL
> marking behaviour" and explain/test this assumption (eg with further
> simulations):
> * "CL marking" means threshold-marking (step) for admission control &
> excess-rate-marking for flow termination.
> * Single Marking - this is potentially a migration step to CL. Explain
why
> SM is not enough (when is it enough?)
> * 3SM - we believe that the overall behaviour in the 3SM draft can be
> approximated with the CL marking + different edge behaviour. Explain
how
> (and what is lost). We had a good session to understand the pros/cons
of
> 3SM in more detail, and what simuls might help on this.
> * LC-PCN - we believe that Affected Marking could in principle be
added to
> CL (or indeed to SM). Assess whether the benefit is worth the cost
(are
> any simulations possible?)
> 
> Results etc of course on list and perhaps as a Part B to
> http://tools.ietf.org/wg/pcn/draft-charny-pcn-comparison-00.txt - in
order
> to help the decision what marking approach to standardise.
> 
> Note, this is just an unofficial understanding between some of us, in
an
> effort to increase the chances of the WG making a decision around the
next
> IETF (when the Milestone is due), and of course doesn't stop other
> proposals and work. Hopefully the above captures what we agree (cc'd
> people, please correct mistakes!).
> 
> Best wishes & have a nice Chistmas,
> Phil
> 

_______________________________________________
PCN mailing list
[email-masked]
http://www.ietf.org/mailman/listinfo/pcn