Subject: [PCN] questions after a lot of reading

From: Lars Eggert <[email-masked]>
Date: Thu, 19 Jul 2007 06:37:59 -0500

Hi,

after reading over the set of PCN drafts, I was left with a number of  
questions. These aren't detailed comments on the individual documents  
but rather higher-level questions about the architecture. I'm posting  
them now in order to jumpstart the discussion during the PCN session  
next week.

I apologize that the questions go a bit all over the place. I'm  
trying to order them in a way that can be followed.

[1] Semantics of the stop-admission signals

Pre-congested routers piggyback admission markings onto the traffic  
flowing through them. The egress that analyzes the volume and  
dynamics of these markings and may make a stop-admission decision,  
which it then signals to the ingress. Agreement so far?

OK, then: What is the semantics of the stop-admission signal? A  
simple "stop admitting new flows" seems to require a complementary  
"start admitting new flows" signal. Or is it "stop admitting new  
flows for a time x", which would not need that second signal?

The latter seems conceptually simpler and may arguably be a bit more  
robust, because the system will un-wedge itself if the "start- 
admission signal" gets lost. But this approach might end up causing  
fluctuations during periods of pre-congestion that are significantly  
longer than x. (Do we expect to support cases where a domain is in a  
pre-congested state for prolonged periods of time?)

(For the "termination" signal going from the egress to the ingress, I  
guess the semantics are clear.)

[2] Implications of multi-marking schemes

I must admit that so far, I have mostly thought of PCN in terms of  
something similar to Anna's single-marking proposal. Meaning that the  
egress would come to a termination decision (rather than a stop- 
admission decision) when the volume or dynamics of the arriving  
markings becomes severe.

(Note: That's not to say that I necessarily believe that single- 
marking should be the technical solution the WG should pick; all I'm  
saying is that I had so far thought about PCN mostly in this way.)

Reading some of the proposals that use multiple kinds of markings  
made me realize that I had made some implicit assumptions about how  
the termination mechanism might operate that were a cause of thinking  
in terms of using a single marking. After reading the multi-marking  
proposals, I'm not sure if these assumptions are shared by all of the  
group. I'm also not sure if there is an agreement among the different  
multi-marking proposals, either.

With a multi-marking scheme, when a congested router marks packets  
with _termination_ marks, does it matter _which_ packets (and hence  
which flows) are marked? Is there an assumption that the system will  
terminate those and only those flows? Or is termination marking  
similar to admission marking, for which piggybacking them onto the  
current traffic stream is simply a convenient transport mechanism?  
Meaning that in the latter case, the egress is free to terminate  
flows whose packets didn't have congestion markings, and let flows  
remain whose packets did, as long as whatever decision it comes to  
alleviates the congestion?

Schemes where the termination decision is influenced by which flows  
have received termination marks seem to require per-flow state at the  
routers, because they need to be sure that they terminate a  
sufficient volume of traffic. That seems to conflict with the goal of  
the architecture to limit that such state to the domain boundary, right?

[3] Marking dynamics

I've seen two ways in the documents that describe how routers should  
mark packets: First, a scheme where the frequency at which a router  
marks packets is proportional to some level of pre-congestion or  
congestion. Second, a scheme where a router starts marking _all_  
packets when congestion exceeds a certain level.

The first scheme transmits much finer-grained information from the  
routers to the egress, which should benefit the decision algorithm  
there. The second scheme basically signals a binary condition. I  
can't come up with a reason why the second scheme should be the  
better one - can anyone explain?

Thanks and see you next week,
Lars
_______________________________________________
PCN mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/pcn

---

From: Michael Menth <[email-masked]>
Date: Fri, 20 Jul 2007 11:14:24 +0200

Hi,

Lars Eggert wrote:
> I apologize that the questions go a bit all over the place. I'm trying 
> to order them in a way that can be followed.
>
>
> flowing through them. The egress that analyzes the volume and dynamics 
> of these markings and may make a stop-admission decision, which it 
> then signals to the ingress. Agreement so far?

I agree.

>
> OK, then: What is the semantics of the stop-admission signal? A simple 
> "stop admitting new flows" seems to require a complementary "start 
> admitting new flows" signal. Or is it "stop admitting new flows for a 
> time x", which would not need that second signal?
>
> robust, because the system will un-wedge itself if the 
> "start-admission signal" gets lost. But this approach might end up 
> causing fluctuations during periods of pre-congestion that are 
> significantly longer than x. (Do we expect to support cases where a 
> domain is in a pre-congested state for prolonged periods of time?)

I cannot remember an explicit discussion and consensus about the exact 
method to signal admission-stop/admission-continue from PCN egress to 
ingress. I find it interesting to have a soft state at the PCN ingress 
node for a time during which it must not admit new traffic. This might 
be useful if an admission-continue signal is lost. As an alternative, 
TCP needs to be used for admission-stop/admission-continue signalling 
from PCN egress to ingress.

> guess the semantics are clear.)

Not really. We have at least two different options.

1) Measured rate termination (cl-draft and others)
ALL packets exceeding the "supportable/tolerable/termination rate" are 
"excess-traffic/termination" marked. The PCN egress node measures the 
rate of marked packets for each ingress-egress aggregate, it potentially 
applies an EWMA to the measured result, and signals it to the respective 
ingress which terminates a set of flows with that rate. Therefore, the 
PCN ingress node should know the rates of individual flows. In 
combination with multipath routing, the PCN ingress does not know which 
flows really go over the bottlenecked link and need to be terminated, 
unless the information about the marked flows is also signaled from PCN 
egress to ingress. Since all excess-traffic packets are marked, this can 
be a large amount. As an alternative, the PCN node may choose the flows 
for termination facing the same challenges. A minimum time between two 
consecutive termination signals for the same ingress-egress aggregate 
should be respected because it takes some time until the first 
termination signal has stopped its flows, the reduced rate is measured 
and visible in the averaged EWMA result. The required marking mechanism 
for this approach is covered as a special case in the 3sm draft 
(slowdown parameter s=0).

The single marking approach is slightly different (the excess traffic 
rate is determined differently), but it works similarly with regard to 
the signaling aspect once the excess traffic rate is found. However, 
there is a difference which is important for multipath routing. If a 
packet is marked, this may come from a path where only the admissible 
rate is exceeded or from a path where also the tolerable rate is 
exceeded such that flow termination is required. Thus, in the presence 
of multipath routing, single marking makes it harder to find out if a 
particular flow has been carried over a bottlenecked link whose 
tolerable rate is exceeded (termination of that flow helps to reduce the 
excess traffic) or just over another path whose admissible rate is 
exceeded (termination of that flow does not help to reduce the excess 
traffic).

2)  Marked flow termination (3sm draft aka explicit marking)
Only SOME packets exceeding the "supportable/tolerable/termination rate" 
are "excess-traffic/termination" marked. The PCN egress node signals the 
flow information of each marked packet to the corresponding PCN ingress 
node which terminates this flow (several flows may be signalled in one 
message). As this flow was marked, it used the bottlenecked link and is 
therefore a correct candidate to terminate also in case of multipath 
routing. No rate measurement is done. No EWMA smoothing is done. The PCN 
egress node does not need to wait a minimum amount of time between two 
termination signals. The PCN ingress node does not need to know the 
rates of the flows. The termination speed of this approach is fast and 
can be controlled by the slowdown-parameter of the packet marker.

> egress would come to a termination decision (rather than a 
> stop-admission decision) when the volume or dynamics of the arriving 
> markings becomes severe.
>
> (Note: That's not to say that I necessarily believe that 
> single-marking should be the technical solution the WG should pick; 
> all I'm saying is that I had so far thought about PCN mostly in this 
> way.)
>
> Reading some of the proposals that use multiple kinds of markings made 
> me realize that I had made some implicit assumptions about how the 
> termination mechanism might operate that were a cause of thinking in 
> terms of using a single marking. After reading the multi-marking 

As far as I know, exact marking behaviors using pseudo code are only 
described in the 3sm draft (it explicitly allows token bucket and 
virtual queue implementations, it does not exclude other similar 
implementations, only the behavior is described). I think that there is 
a rough consensus about the "multi-marking" schemes, at least I am not 
aware of any written proposal that significantly differs from 3sm. This 
is logical as 3sm focuses on this aspect while other drafts focus on 
encoding, signaling, or other aspects. However, I might be wrong and I 
might have missed something. If so, please correct me and point me to 
the section in the right document!

> Meaning that in the latter case, the egress is free to terminate flows 
> whose packets didn't have congestion markings, and let flows remain 
> whose packets did, as long as whatever decision it comes to alleviates 
> the congestion?

The individual marked packets are irrelevant for the flow termination 
result of the "measured rate termination" approach while they exactly 
determine the flows to be terminated for the "marked flow termination" 
approach. If the "measured rate termination" wants to cope with 
multipath routing, it should also terminate a subset of the marked flows.

> routers, because they need to be sure that they terminate a sufficient 
> volume of traffic. That seems to conflict with the goal of the 
> architecture to limit that such state to the domain boundary, right?

I don't see where extra per-flow states need to be kept when the 
termination decision is influenced by which flows have received the 
termination marks. Interior PCN nodes just mark packets for "marked flow 
termination" as for "measured rate termination". No flow states are 
required inside the PCN domain. In both cases the PCN egress nodes 
communicate the outcome of the marking (individual flows or excess 
traffic rate) to the respective flow termination entitiy (wich often is 
- unnecessarily - assumed to be collocated with the PCN ingress router). 
Do I miss something?

> there. The second scheme basically signals a binary condition. I can't 
> come up with a reason why the second scheme should be the better one - 
> can anyone explain?

"Termination/excess-traffic" marking: only those packets are marked that 
exceed the "supportable/tolerable/termination" rate.
1) Measured rate termination requires this to determine the rate to be 
terminated.
2) Marked flow termination uses an additional slowdown parameter to 
reduce the number of marked flows to avoid overtermination as all marked 
flows are going to be terminated.
Thus, both cases have a strong reason why not all packets should be marked.

Single marking and "Admission/admission-stop" marking in case of  
"multi-marking":
1) The single marking approach proposes to mark only a fraction of the 
traffic. Otherwise, there is no room to signal excess traffic which is 
done by just marking more traffic.
The exact rate of marked packets needs to be determined fast which is 
difficult in the presence of bursty or time-varying traffic. 5% error is 
already a significant difference that may impact the admission decision. 
Using EWMA with a LONG memory to improve the measurement accuracy delays 
the recognition of increased traffic rates. I guess that this problem is 
not visible for periodic traffic.

2) The approach presented in the 3sm draft marks all packets with 
admission-stop as soon as the admissible rate is exceeded.
Either 0% or 100% of the traffic is marked when the rate on the link is 
clearly below or above the admissible rate. Therefore, 5% error in the 
measurement process are negligible. The measurement can be done faster. 
The "all or nothing" approach can be seen as a "strong" signal which can 
be recognized more easily and therefore faster than an exact rate can be 
determined.

However, further simulations are required to underpin this speculation

Regards,

    Michael

> ------------------------------------------------------------------------
>

-- 
Dr. Michael Menth, Assistant Professor
University of Wuerzburg, Institute of Computer Science
Am Hubland, D-97074 Wuerzburg, Germany, room B206
phone: (+49)-931/888-6644, fax: (+49)-931/888-6632
mailto:[email-masked]
http://www3.informatik.uni-wuerzburg.de/research/ngn

---

From: "Anna Charny \(acharny\)" <[email-masked]>
Date: Fri, 20 Jul 2007 13:35:14 -0400

Hi Lars, Michael, 

Please see a bit more below:

> -----Original Message-----
> From: Michael Menth [mailto:[email-masked]] 
> Sent: Friday, July 20, 2007 5:14 AM
> To: Lars Eggert
> Cc: [email-masked]
> Subject: Re: [PCN] questions after a lot of reading
> 
> Hi,
> 
> Lars Eggert wrote:
> > Hi,
> >
> I cannot remember an explicit discussion and consensus about 
> the exact method to signal admission-stop/admission-continue 
> from PCN egress to ingress. I find it interesting to have a 
> soft state at the PCN ingress node for a time during which it 
> must not admit new traffic. This might be useful if an 
> admission-continue signal is lost. As an alternative, TCP 
> needs to be used for admission-stop/admission-continue 
> signalling from PCN egress to ingress.
> 

The current architecture work in the wg has not really addressed this
issue yet.  Different algs drafts however did take different approaches.
For example, the initial CL-phb work assumes that the CLE measurement is
continuously/peridically sent to the ingress, which admits as long as
the CLE is below a specified threshold, and does not admit when the
threshold is reached. Single marking does the same.  3sm draft marlking
stops admission on receipt of a single admisison market packet and
resumes after a timeout.  Not yet completely sure what draft-westberg
does about it (still to digest the draft in detail).

It seems that the architecture should allow both explicit periodic CLE
updates, and a timeout should the CLE feedback is lost.  I would argue
that timeout should probably be used as more of an exception measure
than the main mechanism, but the jury is still out.

> 1) Measured rate termination (cl-draft and others) ALL 
> packets exceeding the "supportable/tolerable/termination 
> rate" are "excess-traffic/termination" marked. The PCN egress 
> node measures the rate of marked packets for each 
> ingress-egress aggregate, it potentially applies an EWMA to 
> the measured result, and signals it to the respective ingress 
> which terminates a set of flows with that rate. Therefore, 
> the PCN ingress node should know the rates of individual 
> flows. 

Ideally it would be good if termintation mechanism is directly aware of
the rates of flows it terminates. However, in practice it may suffice
just use the number of flows as an indicator of how many flows to
remove.

>In combination with multipath routing, the PCN ingress 
> does not know which flows really go over the bottlenecked 
> link and need to be terminated, unless the information about 
> the marked flows is also signaled from PCN egress to ingress. 
> Since all excess-traffic packets are marked, this can be a 
> large amount. As an alternative, the PCN node may choose the 
> flows for termination facing the same challenges. A minimum 
> time between two consecutive termination signals for the same 
> ingress-egress aggregate should be respected because it takes 
> some time until the first termination signal has stopped its 
> flows, the reduced rate is measured and visible in the 
> averaged EWMA result. The required marking mechanism for this 
> approach is covered as a special case in the 3sm draft 
> The single marking approach is slightly different (the excess 
> traffic rate is determined differently), but it works 
> similarly with regard to the signaling aspect once the excess 
> traffic rate is found. However, there is a difference which 
> is important for multipath routing. If a packet is marked, 
> this may come from a path where only the admissible rate is 
> exceeded or from a path where also the tolerable rate is 
> exceeded such that flow termination is required. Thus, in the 
> presence of multipath routing, single marking makes it harder 
> to find out if a particular flow has been carried over a 
> bottlenecked link whose tolerable rate is exceeded 
> (termination of that flow helps to reduce the excess traffic) 
> or just over another path whose admissible rate is exceeded 
> (termination of that flow does not help to reduce the excess traffic).
> 

Indeed. This is the price for not using extra marking codepoint and
measurement in the core. Single marking will have to endure some error
in which flows are terminated in the mulipath case.  Of course the
moment you add back another measurement and another codepoint, the
ability to deal with multipath then comes back, and the many options of
doing so are described by Michael above.

> are "excess-traffic/termination" marked. The PCN egress node 
> signals the flow information of each marked packet to the 
> corresponding PCN ingress node which terminates this flow 
> (several flows may be signalled in one message). As this flow 
> was marked, it used the bottlenecked link and is therefore a 
> correct candidate to terminate also in case of multipath 
> routing. No rate measurement is done. No EWMA smoothing is 
> done. The PCN egress node does not need to wait a minimum 
> amount of time between two termination signals. The PCN 
> ingress node does not need to know the rates of the flows. 

It is correct that the ingress does not need to know the rates in this
case, but the other side of this coin is that removing a high-rate flow
may be an overkill if the amount of traffic that needs to be remoived is
samll.  So in either case lack of knowledge about the rates may lead to
inaccurate termination decisions with respect to rates.

> The termination speed of this approach is fast and can be 
> controlled by the slowdown-parameter of the packet marker.

It seems that how fast it really is still needs to be understood. The
speed of termination in the 3sm approach is controlled with the slowdown
parameter, while the EWMA parameters control the seed of reaction of the
other approaches.  I think quantification of these things still remains
to be done carefully.

> As far as I know, exact marking behaviors using pseudo code 
> are only described in the 3sm draft (it explicitly allows 
> token bucket and virtual queue implementations, it does not 
> exclude other similar implementations, only the behavior is 
> described). I think that there is a rough consensus about the 
> "multi-marking" schemes, at least I am not aware of any 
> written proposal that significantly differs from 3sm. 
> This is 
> logical as 3sm focuses on this aspect while other drafts 
> focus on encoding, signaling, or other aspects. However, I 
> might be wrong and I might have missed something. If so, 
> please correct me and point me to the section in the right document!
> 

Here I am a bit confused by Micael's statement - so perhaps I will try
to say it differently.

I believe that across all proposals, 5 separate marking approaches have
been described in both admission and termination contexts, and different
drafts use different approaches for different purposes (There may be
more described in draft-westberg - but again I am yet to fully
understand it)

1) "ramp" virtual-queue (two thresholds, mark all packets above the high
threshold, mark packets with specified probability between thresholds,
do not mark below the lower threshold
     - used for admission in cl-phb
     
2) "step" virtual queue (only one threshold, mark packets above it, do
not mark packets below it
    
     - used as an option for admission in cl-phb draft
     - is equivalent to token-bucket-based implementation of admission
marking in 3sm draft 
 
3) excess rate-based virtual marking 
     - all packets whose measured rate exceeds the configured
termination rate are marked
           -> can be implemented by standard token bucket
     - used for termination in cl-phb and single-marking
     - used for admission in single-marking

4) excess rate marking with slow-down
     - used in 3sm 
     - marks a subset of packets exceeding the rate 
     - can be implemented by adding the slow-down function to token
bucket, as done in CL

5) excess-rate-proportional marking
     - I believe this is the "encoded" marking in draft-westberg, used
for termination
     - marks a fraction of all packets, where the fraction encodes the
amount of overload  (but not equal to the amount of overload)
      (here I hope the authors of draft-westberg will jump in with
explanations or crrections of the details)

> The individual marked packets are irrelevant for the flow 
> termination result of the "measured rate termination" 
> approach while they exactly determine the flows to be 
> terminated for the "marked flow termination" 
> approach. If the "measured rate termination" wants to cope 
> with multipath routing, it should also terminate a subset of 
> the marked flows.

Yes. Said in other words, it matters for some proposals and does not
matter for others.

> sufficient 
> I don't see where extra per-flow states need to be kept when 
> the termination decision is influenced by which flows have 
> received the termination marks. Interior PCN nodes just mark 
> packets for "marked flow termination" as for "measured rate 
> termination". No flow states are required inside the PCN 
> domain. In both cases the PCN egress nodes communicate the 
> outcome of the marking (individual flows or excess traffic 
> rate) to the respective flow termination entitiy (wich often is

Also not sure why Lars thinks per-flow state is needed?

> "Termination/excess-traffic" marking: only those packets are 
> marked that exceed the "supportable/tolerable/termination" rate.
> 1) Measured rate termination requires this to determine the 
> rate to be terminated.

Actually, in cl-phb and single marking, it is the amount of
*termination- *un*marked packets that determines the desired rate, and
then the excess over this rate is terminated at the ingress.  This is
different than terminating the amount of marked packets if there is any
loss in the system. Also, makes some of the problems associated with
timing of removal somehat easier).

> 2) Marked flow termination uses an additional slowdown 
> parameter to reduce the number of marked flows to avoid 
> overtermination as all marked flows are going to be terminated.
> 1) The single marking approach proposes to mark only a 
> fraction of the traffic. Otherwise, there is no room to 
> signal excess traffic which is done by just marking more traffic.
> The exact rate of marked packets needs to be determined fast 
> which is difficult in the presence of bursty or time-varying 
> traffic. 5% error is already a significant difference that 
> may impact the admission decision. 
> Using EWMA with a LONG memory to improve the measurement 
> accuracy delays the recognition of increased traffic rates. I 
> guess that this problem is not visible for periodic traffic.
> 

Single-marking simulation draft actually provides some insight on the
issue of sensitivity to parameters. As it is not directly related to
Lars's question, will not discuss it here, though.

> 2) The approach presented in the 3sm draft marks all packets 
> with admission-stop as soon as the admissible rate is exceeded.
> Either 0% or 100% of the traffic is marked when the rate on 
> the link is clearly below or above the admissible rate. 
> Therefore, 5% error in the measurement process are 
> negligible. The measurement can be done faster. 
> The "all or nothing" approach can be seen as a "strong" 
> signal which can be recognized more easily and therefore 
> faster than an exact rate can be determined.
> 

Indeed. A sensitivity study to the timeout parameter value is needed.
The other side of the coin of "strong" signal is that for traffic that
is not very smooth reacting to a single mark to stop admission may
result in substantial underadmission.  Michael is quite right that
additional study is required to quantify that.  Also a subject of a
separate discussion, I think. 

Best,
Anna 

> University of Wuerzburg, Institute of Computer Science Am 
> Hubland, D-97074 Wuerzburg, Germany, room B206

---

From: Michael Menth <[email-masked]>
Date: Fri, 20 Jul 2007 21:00:55 +0200

Hi,

Anna Charny (acharny) wrote:
>>> after reading over the set of PCN drafts, I was left with a 
>>>       
>> number of 
>>     
>>> questions. These aren't detailed comments on the individual 
>>>       
>> documents 
>>     
>>> but rather higher-level questions about the architecture. 
>>>       
>> I'm posting 
>>     
>>> them now in order to jumpstart the discussion during the 
>>>       
>> PCN session 
>>     
>>> next week.
>>>
>>> I apologize that the questions go a bit all over the place. 
>>>       
>> I'm trying 
>>     
>>> flowing through them. The egress that analyzes the volume 
>>>       
>> and dynamics 
>>     
>>> OK, then: What is the semantics of the stop-admission 
>>>       
>> signal? A simple 
>>     
>>> admitting new flows" signal. Or is it "stop admitting new 
>>>       
>> flows for a 
>>     
>>> The latter seems conceptually simpler and may arguably be a 
>>>       
>> bit more 
>>     
> resumes after a timeout. 

We actually did not specify this so exactly in 3sm as this was not its 
major focus: "More specifically, if most of the packets are AS-marked, 
the PCN traffic rate of at least one of the links in the ingress-egress 
path has exceeded its admissible rate, i.e. it is AR-overloaded. 
Therefore, the PCN egress signals "admission-stop" to the admission 
control entity for the corresponding ingress-egress aggregate such that 
no further flows are admitted." But maybe this was in the previous 
explicit-marking draft.

>  Not yet completely sure what draft-westberg
>>> (For the "termination" signal going from the egress to the 
>>>       
>> ingress, I 
>>     

We are working on that issue.

>>> something similar to Anna's single-marking proposal. 
>>>       
>> Meaning that the 
>>     
>>> stop-admission decision) when the volume or dynamics of the 
>>>       
>> arriving 
>>     
>>> markings becomes severe.
>>>
>>> Reading some of the proposals that use multiple kinds of 
>>>       
>> markings made 
>>     
>>> termination mechanism might operate that were a cause of 
>>>       
>> thinking in 
>>     
>>> proposals, I'm not sure if these assumptions are shared by 
>>>       
>> all of the 
>>     
>>> group. I'm also not sure if there is an agreement among the 
>>>       
>> different 
>>     

Ooops, sorry, I appologize. Regarding multi-marking I subsumed the two 
different termination marking algs in 3sm as a single one for 
termination marking (the one is a special case of the other) and the two 
different admission marking algs (ramp marking and the pure threshold 
marking)  as another one for admission marking (also here mere threshold 
marking is a special case of the other, also simulation results showed 
no difference as far as I can remember). And I really forgot about 
"excess-rate-proportional marking".

Regards,

    Michael

>>> which flows) are marked? Is there an assumption that the 
>>>       
>> system will 
>>     
>>> Meaning that in the latter case, the egress is free to 
>>>       
>> terminate flows 
>>     
>>> whose packets did, as long as whatever decision it comes to 
>>>       
>> alleviates 
>>     
>>> the congestion?
>>>       
>>> have received termination marks seem to require per-flow 
>>>       
>> state at the 
>>     
>>> I've seen two ways in the documents that describe how 
>>>       
>> routers should 
>>     
>>> there. The second scheme basically signals a binary 
>>>       
>> condition. I can't 
>>     
>>> come up with a reason why the second scheme should be the 
>>>       
>> better one - 
>>     
>>> can anyone explain?
>>>       
>> ----------------------------------------------------------------------
>>     
>>> --
>>>