Subject: Re: [PCN] Please modify the marking behaviour draft

From: SATOH Daisuke <[email-masked]>
Date: Fri, 06 Mar 2009 13:15:18 +0900

Hi Phil,

> Hi Daisuke
> 
> I've thought a bit more about your proposal, and read your
> draft-satoh-pcn-ST-marking (thanks for sending me a version that will
> soon be the 01 doc. I think most of my comments are relevant to the
> earlier version, but there are one or two that need the update to make
> sense, sorry to rest of WG where this is the case but I wanted to send
> my comments before I forgot them!)
> 
> First, I'd like to understand a bit more your reasoning behind the
> proposal. OK, you want a marking behaviour that can give reasonable
> admission control and flow termination even when only 2 PCN encoding
> states are available (PCN-marked & not marked). There is already a
> proposal that achieves this - ie "single marking"
> http://www.watersprings.org/pub/id/draft-charny-pcn-single-marking-03.tx
> t (just expired, but i believe will be renewed very soon). Your
> simulations (roughly speaking) show that the behaviour of your marking
> behaviour is similar to that of SM. Please could you explain in what
> situations /scenarios it has a significant advantage. The SM proposal
> works with the existing marking behaviour in the WG doc
> http://tools.ietf.org/wg/pcn/draft-ietf-pcn-marking-behaviour/ which has
> been extensively simulated etc, so we need to understand where it has
> clear benefit (ie beyond being a plausible alternative). I think this is
> the most important comment.

Our simulation shows that the behaviour of our marking behaviour is similar to that of CL, not SM. Furthermore, STM is little affected by synchronization. I explain it later. STM has two advantages to CL in termination. One is accuracy of termination when the load is large. The other is fairness of termination in multi-bottleneck case. Accumulation of the number of marking packets in CL brings heavier over termination at upstreamer links. However, STM is not at all affected by the accumulation. Therefore, STM makes over termination percentage to be almost the same at every link. Our simulation shows it.

> 
> I wonder about the relative complexity of your marking behaviour
> (compared with draft-ietf-pcn-marking-behaviour). It seems somewhat more
> complex (because of the linking of two token buckets; and the second
> threshold at just below the 'full' level of the token bucket). 
> 
> A similar complexity concern I have is about migration. The
> draft-ietf-pcn-marking-behaviour has both threshold and excess-rate
> meters as musts to implement. One reason is that it makes it easy to
> migrate, when an extra PCN encoding state becomes available, from SM to
> the more accurate admission & termination of (eg) CL. With your approach
> this requires a 3rd meter (& possibly a 4th, depending whether the MkTB
> token bucket is good enough).

I do not understand why migration is necessary. I understand that PCN WG determined two codepoints encoding was standard and three codepoints encoding was experimental at Philadelphia. Do I misunderstand? Could you explain why migration is necessary?

> 
> [I think this issue is relevant to the -01 version, not the -00]. I
> didn't follow the termination method if the link is very heavily
> overloaded, ie above the link capacity. You seem to imply that something
> beyond the normal mechanism is done, but I didn't get it.
> 
> The termination mechanism is to terminate y% of flows every 'measuring
> interval', if the sending rate is > receiving rate (I assume these are
> measured for a particular ingress-egress-aggregate). First, this method
> seems to need careful balancing of the parameters (y & measuring
> interval) in order to ensure that termination is fast enough but not too
> much is over-terminated. Maybe the over-termination is limited to y%, ie
> known amount, so this aspect not too bad (still need to set measurement
> interval).

Only an ingress node has measuring interval. An egress node measures receiving rate packet by packet.

You mean balancing of the parameters: y and measuring interval is necessary to terminate necessary flows in a certain interval. The number of termination intervals is limited by the measuring interval. If y is too small, STM cannot terminate enough flows within the the certain interval. I describe it as tradeoff between accuracy and time of termination.

> Second, the approach to date has to been to try to allow a range of
> possible termination approaches - not sure whether this is possible with
> your draft (don't know).
> 

When the load is a little bit higher than PCN-supportable-rate, y % over termination is not avoidable.

> Distinguishing admission and termination: it is (I think) inevitable
> that any scheme with just one PCN-marked encoding will have scenarios
> where it mistakenly terminates when it should just be doing admission
> control, at least in theory. For example, in your draft if the pattern
> of traffic means that L pkts in a row are marked (ie pkts arriving at an
> egress from a particular ingress), even though PCN-nodes are doing
> admission marked (ie marking 1/N pkts). Immediate reaction is that this
> "mistaken termination" seems more likely to happen than with SM.

No.
SM terminates flows when an ingress node observes a non-zero CLE and sending rate > U*SAR. The mistaken termination occurs some packets are excess-traffic-marked at the admissible rate and traffic rate fluctuates. If the rate is stable, this termination works. Otherwise, the mistaken termination occurs. The rate depends traffic type (VBR, SVD) and measuring interval. Therefore to avoid mistaken termination is difficult in SM.

In STM, if one IE pair gets L pkts marking in a row in the 1/N marking state, the mistaken termination occurs. This is just synchro. STM is little affected by synchro. I would like to see an attached file. These figures in the file helps you to understand how to avoid synchro in STM.

More packets in our marking are marked than ones in excess-traffic marking. If N = 1, synchro also occurs in our marking because packets in the interval between sequential two packets in a CBR flow are marked cyclically. This cyclic marking occurs in excess-traffic-marking, too. Synchro is caused by this cyclic marking. However, if anothre number is chosen as N in modified threshold marking, the
packets in the interval are not marked cyclically. This avoids Synchro.

> However, this needs more thought (would you argue it is less likely?)
> Also, the choice of the 1/N parameter seems to depend on the odds of L
> pkts in a row being marked - which seems to depend on the traffic
> pattern, type of traffic (CBR, VBR etc), factors which may be uncertain
> when management configuration is done?
> 

Our marking little depend on the traffic pattern. If traffic pattern is described by a renewal process and the number of multiplexed flows is enough large, our marking gives traffic intensity when the service rate is the PCN-supportable-tate. You understand it by reading ex., "D. Gross and C.M. Harris, Fundamentals of queueing theory, John Wiley & Sons, " and "D.R. Cox, Renewal Theory, John Wiley & Sons."Gross and Harris book describes Little's formula and PASTA. Cox's book describes infinite multiplexed renewal processes is Poisson process. If the arrival process is not described by a renewal process, the error between the marking ratio and the traffic intensity can be evaluated by the paper" E.A. Pekoz, S.M. Ross and S. Seshadri, How nearly do arriving customers see time-average behavior, J. Appl. Prob. 45, pp. 963--971 (2008)."

> Also i worry that this problem could be critical with synchronised
> traffic, eg CBR flows or smoothed by nw. then every pkt for a particular
> flow (or ingress-egress-aggregate) might be marked by a router doing
> admission marking. Your simulations seem to show no problem with
> synchronisation with CBR traffic, but I didn't understand conceptually
> if this is because the problem I describe is impossible to happen, or
> didn't because of some simulation assumption, or something else. 

See the attached file.

> 
> I don't understand why the MkTB has the "shallow.threshold" just below
> the "full" level of the token bucket (it's below by the size of the
> metered-packet). [There's a reference "see Appendix" but wasn't sure
> which bit of appendix to read.] why is this needed at all? (sorry, am
> sure you explained this to me at the last ietf but I've forgotten.)

If shallow.threshold is set, each packet sees if the server whose service rate is the PCN-supportable-rate is busy or not. However, each packet generally does not see time average except arrival process  of each packet is Poisson process. The Gross and Harris book explain them that is Little's formula and PASTA.

> 
> Thanks
> phil
> 
> { -----Original Message-----
> { From: [email-masked] [mailto:[email-masked]] On Behalf Of
> { SATOH Daisuke
> { Sent: 21 January 2009 07:46
> { To: [email-masked]
> { Subject: [PCN] Please modify the marking behaviour draft
> { 
> { 
> { 
> { Hi Phil,
> { 
> { 
> { If you received this e-mail again, I'm sorry.
> { 
> { 
> { I would like you to modify draft-ietf-pcn-marking-behaviour-01. I made
> { an example of modification as follows.
> { I understand I have to show you the performance of our algorithm. So I
> { have to update draft-satoh-pcn-st-marking-00. We have simulated our
> { algorithm
> { in extreme cases for both admission and termination. Now we are
> { simulating it. Please wait for performance evaluation awhile.
> { 
> { 
> { 
> { ---
> { 2.3. Threshold meter function
> { 
> { 2.3.1 Threshold meter function with One threshold
> { A PCN-node MUST implement a Threshold Meter that has behaviour
> { functionally
> { equivalent to the following. The meter acts like a token bucket, which
> { is sized in bits and has a configured bit rate, termed
> { PCN-threshold-rate. The amount of tokens in the token bucket is termed
> { TBthreshold.fill. Tokens are added at the PCN-threshold-rate, to a
> { maximum value TBthreshold.max. Tokens are removed equal to the size in
> { bits of the metered-packet, to a minimum TBthreshold.fill=0. The token
> { bucket has a configured intermediate depth, termed
> TBthreshold.threshold.
> { If TBthreshold.fill < TBthreshold.threshold, then the meter indicates
> to
> { the Marking function that the packet is to be threshold-marked;
> { otherwise it does not.
> { 
> { 
> { 2.3.2 Threshold meter function with two threshold
> { A PCN-node MUST implement a Threshold Meter that has behaviour
> { functionally
> { equivalent to the following.
> { 
> { The meter acts like a token bucket, which is sized in bits and has a
> { configured
> { bit rate, termed PCN-threshold-rate. The amount of tokens in the token
> { bucket is termed TBthreshold.fill. Tokens are added at the
> { PCN-threshold-rate, to a maximum value TBthreshold.max. Tokens are
> { removed equal to the size in bits of the metered-packet, to a minimum
> { TBthreshold.fill=0. The token bucket has two configured intermediate
> { depths, termed TBthreshold.shallow.threshold and
> TBthreshold.threshold,
> { where TBthreshold.shallow.threshold is greater than
> { TBthreshold.threshold. If (TBthreshold.fill <
> { TBthreshold.shallow.threshold) and (TBthreshold.fill >=
> { TBthreshold.threshold), then the meter indicates to the Marking
> function
> { that one-N-th packets are threshold-marked. If TBthreshold.fill <
> { TBthreshold.threshold, then the meter indicates to the Marking
> function
> { that the packet is to be threshold-marked; otherwise it does not.
> { 
> { 
> { 
> { 2.5 Combination of the meter functions
> { A PCN-node MAY implement combination of Threshold and Excess traffic
> { meters. The
> { meter is composed of two tandem meters of Threshold and Excess traffic
> { meters or two Threshold meters or two Excess traffic meters. The
> former
> { meter is used for marking switch and the latter meter is used for
> { marking.
> { 
> { The combined meter has behaviour functionally equivalent to the
> following.
> { 
> { 
> { If TBthreshold.fill >= TBthreshold.threshold (when the former meter is
> the
> { Threshold
> { meter) or if the token bucket is not empty (the former meter is the
> { Excess traffic meter), the combined meter indicates to the Marking
> { function that the packet is not to be marked even if the latter meter
> { indicates to the Marking function that the packet is to be marked.
> { Otherwise, the combined meter indicates the same result as the latter
> { meter's indication to the Marking function.
> { 
> { 
> { 
> { A.3 Combined metering and marking
> { The combined meter by using two Threshold meters is introduced. The
> two
> { combined
> { token buckets with the following parameters:
> { 
> { o TBthreshold.PCN-threshold-rate.former: token rate of the former
> token
> { bucket (bits/second)
> { 
> { o TBthreshold.PCN-threshold-rate.latter: token rate of the latter
> token
> { bucket (bits/second)
> { 
> { o TBthreshold.max.former: depth of the former token bucket (bits)
> { 
> { o TBthreshold.max.latter: depth of the latter token bucket (bits)
> { 
> { o TBthreshold.threshold.former: marking threshold of the former token
> { bucket (bits)
> { 
> { o TBthreshold.shallow.threshold.latter: One-Nth marking threshold of
> the
> { latter token bucket (bits)
> { 
> { o TBthreshold.threshold.latter: marking threshold of the latter token
> { bucket (bits)
> { 
> { o TBthreshold.lastUpdate: time both token buckets were last updated
> { (seconds)
> { 
> { o TBthreshold.fill.former: amount of tokens in the former token bucket
> { (bits)
> { 
> { o TBthreshold.fill.latter: amount of tokens in the latter token bucket
> { (bits)
> { 
> { 
> { A PCN-packet has the following parameters:
> { 
> { o packet.size: the size of the PCN-packet (bits)
> { 
> { o packet.mark: the PCN encoding state of the packet
> { 
> { In addition there is the parameter:
> { 
> { o now: the current time (seconds)
> { 
> { 
> { The following steps are performed when a PCN-packet arrives on a link:
> { 
> { o TBthreshold.fill.former = min(TBthreshold.max.former,
> { TBthreshold.fill.former +
> { TBthreshold.PCN-threshold-rate.former*(now - TBthreshold.lastUpdate));
> { // add tokens to the former token bucket
> { 
> { o TBthreshold.fill.latter = min(TBthreshold.max.latter,
> { TBthreshold.fill.latter +
> { TBthreshold.PCN-threshold-rate.latter*(now -
> TBthreshold.lastUpdate));//
> { add tokens to the latter token bucket
> { 
> { 
> { o TBthreshold.fill.former = max(0, TBthreshold.fill.former -
> packet.size);
> { //remove
> { tokens from the former token bucket
> { 
> { 
> { o TBthreshold.fill.latter = max(0, TBthreshold.fill.latter -
> packet.size);
> { //remove
> { tokens from the latter token bucket
> { 
> { 
> { o if (TBthreshold.fill.former < TBthreshold.threshold.former) then
> {      if  (TBthreshold.fill.latter <
> TBthreshold.shallow.threshold.latter)
> { then
> {         if (TBthreshold.fill.latter >= TBthreshold.threshold.latter)
> then
> { 	       one-Nth packets are threshold-marked
> {         else
> { 		packet.mark = threshold-marked;
> { //do threshold marking with two thresholds only when
> { TBthreshold.fill.former <= TBthreshold.threshold.former
> { 
> { o TBthreshold.lastUpdate = now
> { ---
> { Best regards,
> { 
> { Daisuke
> { 
> { _______________________________________________
> { PCN mailing list
> { [email-masked]
> { https://www.ietf.org/mailman/listinfo/pcn
-- 
NTTアドバンステクノロジ（株）　ネットワークテクノロジセンタ
佐藤　大輔　(Daisuke SATOH, Ph.D.)
tel:0422-36-7502  fax:0422-36-7591
mailto: [email-masked]
※2008.7.7より電話番号、Fax番号が変更になりました。

---

From: <[email-masked]>
Date: Fri, 6 Mar 2009 18:11:43 -0000

Mostly I need to think about this more than I can at the moment. 

Couple of quicker follow ups
{ 
{ I do not understand why migration is necessary. I understand that PCN
WG
{ determined two codepoints encoding was standard and three codepoints
{ encoding was experimental at Philadelphia. Do I misunderstand? Could
you
{ explain why migration is necessary?

That' what we're aiming for from an ietf point of view. As one example
of migration,. imagine an operator that starts with the 2 codepoints and
migrates to using a 3rd/ 

{ 
{ In STM, if one IE pair gets L pkts marking in a row in the 1/N marking
{ state, the mistaken termination occurs. This is just synchro. STM is
{ little affected by synchro. I would like to see an attached file.
These
{ figures in the file helps you to understand how to avoid synchro in
STM.
{ 

I'm unsure whether what you mean by syncro is what I had in mind by
syncronisation. Please could you define your syncro. 

{ 
{ If shallow.threshold is set, each packet sees if the server whose
service
{ rate is the PCN-supportable-rate is busy or not. However, each packet
{ generally does not see time average except arrival process  of each
packet
{ is Poisson process. The Gross and Harris book explain them that is
{ Little's formula and PASTA.

I need a gentler explanation, sorry.

---

From: SATOH Daisuke <[email-masked]>
Date: Wed, 11 Mar 2009 18:38:35 +0900

Hi Phil,

Although I upload my new draft, it has not uploaded yet because of 

> of migration,. imagine an operator that starts with the 2 codepoints and

I understand what your migration is. However, does it have reality?

> syncronisation. Please could you define your syncro. 

My difinition is the same as that in
draft-zhang-pcn-performance-evaluation. 

When packets are partially marked, packets in some flow can be all
marked and packets in other flow can be no marked. If traffic type is
CBR and PCN-excess-traffic-marking is used, this phenomenon happens.

Please look at pdf file I sent before. Due to 1/N, there is no flow whose packets are all marked.

> I need a gentler explanation, sorry. 

I describe this explanation in Appendix D. 

Best regards,
Daisuke