Subject: [PCN] Marking scheme better than random marking

From: "Lachlan Andrew" <[email-masked]>
Date: Wed, 25 Jul 2007 11:11:46 -0700

Greetings all,

I'm a newcomer to this WG, but noticed a heavy reliance on marking of
packets to signal continuous values.

It was good to discuss an alternative with some of you over lunch.
The proposal (ADPM) is described at
<http://netlab.caltech.edu/~lachlan/abstract/ADPM_CL.pdf> and in more
detail at <http://netlab.caltech.edu/~lachlan/dmtm.pdf>.

It is a way of sending a continuous-valued signal over an ECN-type
channel (a binary channel subject to to loss, reordering, duplication
etc).  The terminology is that of congestion control, but seems to be
applicable to PCN.

It overcomes the unfairness to long-haul flows traversing multiple
bottlenecks, giving max-min fairness (is that "too fair"?).

I think this can be used by several of the schemes (notably LC-PCN)
with no major change to the scheme.

Questions or comments are welcome.

Cheers,
Lachlan

-- 
Lachlan Andrew  Dept of Computer Science, Caltech
1200 E California Blvd, Mail Code 256-80, Pasadena CA 91125, USA
Phone: +1 (626) 395-8820    Fax: +1 (626) 568-3603

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

---

From: "Anna Charny \(acharny\)" <[email-masked]>
Date: Wed, 25 Jul 2007 14:46:58 -0400

Hi Lachlan,

I think I now understand the proposal after a very helful discussion
today.  But I do not quite understand how it overcomes unfairness for
flows traversing multiple bottlenecks in the context of admission
control?  It seems
the type of marking should not change the fact that the long flow finds
a link in the state of congestion more often than the short-haul flows,
it cannot admit more often than the short-haul flows. So at the same
demand level,  short-haul flows win.  

Maybe I am still missing something about the algorithm still...  Can you
explain?

Thanks,
Anna 

> -----Original Message-----
> From: Lachlan Andrew [mailto:[email-masked]] 
> Sent: Wednesday, July 25, 2007 2:12 PM
> To: PCN IETF list
> Cc: Stephen Hanly; Sammy Chan
> Subject: [PCN] Marking scheme better than random marking
> 
> Greetings all,
> 
> I'm a newcomer to this WG, but noticed a heavy reliance on 
> marking of packets to signal continuous values.
> 
> <http://netlab.caltech.edu/~lachlan/abstract/ADPM_CL.pdf> and 
> in more detail at <http://netlab.caltech.edu/~lachlan/dmtm.pdf>.
> 
> It is a way of sending a continuous-valued signal over an 
> ECN-type channel (a binary channel subject to to loss, 
> reordering, duplication etc).  The terminology is that of 
> congestion control, but seems to be applicable to PCN.
> 
> It overcomes the unfairness to long-haul flows traversing 
> multiple bottlenecks, giving max-min fairness (is that "too fair"?).
> 
> I think this can be used by several of the schemes (notably 
> LC-PCN) with no major change to the scheme.
> 
> Lachlan Andrew  Dept of Computer Science, Caltech 1200 E 
> California Blvd, Mail Code 256-80, Pasadena CA 91125, USA

---

From: "Lachlan Andrew" <[email-masked]>
Date: Wed, 25 Jul 2007 12:21:00 -0700

Greetings Anna,

Good point -- I was mainly extrapolating from what happens in
congestion control.  It only resolves a particular form of unfairness.

I assume that each link has a continuous-valued "congestion level"
(in the interval [0,1]) to be signalled.  Consider a network with two
links with congestion levels  A  and   B.  If both links independently
mark packets, with probabilities  A  and  B,  then a packet traversing
both links is more likely to be marked than a packet traversing only
the more congested link.  In ADPM, the marking probability is
max(A,B).

If the links "pre-quantise" the congestion level into "congested" or
"not congested" then you are quite right that longer flows are more
likely to observe one of the links being congested.  A leaky-bucket
scheme which defines a link as "congested" when the bucket is empty
has already quantised the continuous value.  Is that the scenario
you're thinking of?

I'm not sure if ADPM can be adapted to work in the leaky-bucket case.
I'll have to read your(?) draft first.

Cheers,
Lachlan

On 25/07/07, Anna Charny (acharny) <[email-masked]> wrote:
> I do not quite understand how it overcomes unfairness for

---

From: "Anna Charny \(acharny\)" <[email-masked]>
Date: Wed, 25 Jul 2007 15:44:17 -0400

Hi Lachlan,

I think there are two different causes of unfairness that are being
lumped together. The first is when a flow passes through multiple links
simultaneously congested.  In that case, if care is not taken,  the flow
traversing more congestion points gets more congestion marks and is more
affected, under some marking schemes.  Indeed, diferent marking
techniques have different  amount of exposure to this problem.  

The second one has to do with the amount of time the long-haul aggregate
sees congestion on at least one of the links.  The worst case here is
when at any given time only one of the links is congested, and at least
one is congested all (or most of) the time. Then, the short-haul
aggregates, which only see congestion ocasionally, will keep admitting
new flows, whereas the long-term ones will never (in the worst case) or
rarely (in practice) be allowed to admit.  This is the phenomenon
discussed today at the meeting. And I think your message below indicates
that you agree that there is nothing your proposal can do to deal with
this one?

I do agree that the marking method you propose seems compatible with the
draft-westberg approach (would it be correct to say that this would be a
clever implementation of excess-rate-proportional marking?)

Thanks,
Anna 

> Sent: Wednesday, July 25, 2007 3:21 PM
> To: Anna Charny (acharny)
> Cc: PCN IETF list; Stephen Hanly; Sammy Chan
> Subject: Re: [PCN] Marking scheme better than random marking
> 
> Greetings Anna,
> 
> mark packets, with probabilities  A  and  B,  then a packet 
> traversing both links is more likely to be marked than a 
> packet traversing only the more congested link.  In ADPM, the 
> marking probability is max(A,B).
> 
> If the links "pre-quantise" the congestion level into 
> "congested" or "not congested" then you are quite right that 
> longer flows are more likely to observe one of the links 
> being congested.  A leaky-bucket scheme which defines a link 
> as "congested" when the bucket is empty has already quantised 
> the continuous value.  Is that the scenario you're thinking of?
> 
> > I do not quite understand how it overcomes unfairness for flows 
> > traversing multiple bottlenecks in the context of admission 
> control?  
> > It seems the type of marking should not change the fact 
> that the long 
> > flow finds a link in the state of congestion more often than the 
> > short-haul flows, it cannot admit more often than the short-haul 
> > flows. So at the same demand level,  short-haul flows win.
> 
> 
> --

---

From: "Lachlan Andrew" <[email-masked]>
Date: Wed, 25 Jul 2007 13:16:13 -0700

Greetings Anna,

I still think that

On 25/07/07, Anna Charny (acharny) <[email-masked]> wrote:
> lumped together.

Exactly.  That's why I said last email that it only resolves a
particular form of unfairness.

> one is congested all (or most of) the time.

Agreed.  If "congestion" is a binary state then signalling can't help.
My (naive?) argument would be that in practice  congestion  isn't
binary.  If a link is operating very close to capacity, we should
admit a small fraction of flows,  if it is further from capacity we
admit more flows.  (When I think as a theoretician, I also think we
can admit a very few flows when the link is overloaded, assuming that
flows will depart continuously.)  Achieving fairness may need the
one-hop flows to average the congestion level over a time comparable
to the duration of a flow before allowing a new flow to start.

A scheme which admits either all or no flows probably won't benefit
from ADPM, but I would suggest that admitting a fraction of flows
based on more information would give better performance.

> And I think your message below indicates

I agree that it would require other changes to the admission control
in addition to ADPM.  I'm not sure if those changes would be easy.

> clever implementation of excess-rate-proportional marking?)

Yes, it is simply a way to do "X-proportional" marking.

Cheers,
Lachlan

---

From: "Anna Charny \(acharny\)" <[email-masked]>
Date: Wed, 25 Jul 2007 17:19:47 -0400

Hi Lachlan,

(cutting some text out where there seems to be agreement): 
> My (naive?) argument would be that in practice  congestion  
> isn't binary.  If a link is operating very close to capacity, 
> we should admit a small fraction of flows,  if it is further 
> from capacity we admit more flows.  (When I think as a 
> theoretician, I also think we can admit a very few flows when 
> the link is overloaded, assuming that flows will depart 
> continuously.)  Achieving fairness may need the one-hop flows 
> to average the congestion level over a time comparable to the 
> duration of a flow before allowing a new flow to start.
> 

Well, the issue here is that the one-hop flows are not really one-hop
flows - they are actually one "bottleneck" flow, but may in fact pass
more non-congested links.  And averaging over the duration of the flow
seems scary if the flow is long (e.g. video stream)...    It seems that
if a solution were to try to deal with this, it would have to be aware
of the number of bottlenecks traversed (this changes overtime, so
tricky)...  
In any case, I think we agree that machinery currently far from that
being envisioned in the PCN context might be required to deal with the
problem.

Anna

---

From: "Lachlan Andrew" <[email-masked]>
Date: Wed, 25 Jul 2007 14:45:59 -0700

Greetings Anna,

On 25/07/07, Anna Charny (acharny) <[email-masked]> wrote:
> more non-congested links.
> It seems that
> of the number of bottlenecks traversed...

I was assuming that the multi-bottleneck flows would also average the
congestion level.  Why would we need to consider the number of
bottlenecks?

> And averaging over the duration of the flow
> seems scary if the flow is long (e.g. video stream)...

Yes. It would certainly be bad to admit a flow when the load is
currently high just because the half-hour average was low.
Conversely, it seems scary to admit a half-hour flow because our rate
has just dipped below a threshold.  If our decision is to have an
effect on timescale  X,  we should try to predict the network
conditions over that timescale into the future.  It isn't clear to me
that the current conditions are a better estimate than the historical
conditions (but again, I'm a newbie in this area).

> being envisioned in the PCN context might be required to deal with the

I don't know the PCN charter, but if we provide the machinery for
signalling of the current congestion level, actual admission rule can
be left fairly flexible, can't it?  If "Generation 1" equipment admits
calls with a probability based on instantaneous rate, it will still
interwork with "Generation 2" equipment which bases its admission
probability on both instantaneous and long-term rate.  Perhaps I am
thinking like an IRTF person...

>From a quick look at your draft, it seems that using ADPM for it (for
the excess-rate signalling, as you said last email) preserves the
code-point benefit of being a "single marking", but forfeits the
benefit of using a token bucket.

Cheers,
Lachlan