Subject: [PCN] 5.5. Probing functions

From: Lars Eggert <[email-masked]>
Date: Thu, 1 Nov 2007 13:38:13 +0200

Hi,

I read through the section on probing in the architecture draft, and  
have some comments. Folks know that I'm not too thrilled with the  
idea of probing, so this should come as no surprise...

> 5.5.  Probing functions
>
>    Probing functions are optional, and can be used for admission
>    control.
>
>    PCN's admission control, as described so far, is essentially a
>    reactive mechanism where the PCN-egress-node monitors the pre-
>    congestion level for traffic from each PCN-ingress-node; if the  
> level
>    rises then it blocks new flows on that ingress-egress-aggregate.
>    However, it's possible that an ingress-egress-aggregate carries no
>    traffic, and so the PCN-egress-node can't make an admission  
> decision
>    using the usual method described earlier.
>
>    One approach is to be "optimistic" and simply admit the new flow.
>    However it's possible to envisage a scenario where the traffic  
> levels
>    on other ingress-egress-aggregates are already so high that they're
>    blocking new PCN-flows and admitting a new flow onto this 'empty'
>    ingress-egress-aggregate would add extra traffic onto the link  
> that's
>    already pre-congested - which may 'tip the balance' so that PCN's
>    flow termination mechanism is activated or some packets are  
> dropped.
>    This risk could be lessened by configuring on each link sufficient
>    'safety margin' above the PCN-lower-rate.
>
>    An alternative approach is to make PCN a more proactive mechanism.
>    The PCN-ingress-node explicitly determines, before admitting the
>    prospective new flow, whether the ingress-egress-aggregate can
>    support it.  This can be seen as a "pessimistic" approach, in
>    contrast to the "optimism" of the approach above.  It involves
>    probing: a PCN-ingress-node generates and sends probe packets in
>    order to test the pre-congestion level that the flow would
>    experience.

The above is a really good intro to the problem - nice job.

>    A probe packet is just a dummy data packet, generated by
>    the PCN-ingress-node and addressed to the PCN-egress-node.  A
>    downside of probing is that it adds delay to the admission control
>    process.  Also note that in the scenario described in the previous
>    paragraph (where traffic levels on other ingress-egress- 
> aggregates is
>    already very high), the probe packets may also 'tip the balance'.

This discussion on the downsides of probing is too short. Let me list  
some issues:

(1) The ingress needs to generate traffic in a pattern and at a rate  
that lets it draw conclusions about whether it is OK to admit the  
flow that is waiting for admission. How does it know what  
characteristics the probe traffic should have and how does it  
generate the probe traffic?

(2) How long do you need to probe for before you declare it safe to  
admit the new flow? What's the delay before a new flow can be  
admitted, and can apps actually deal with this delay?

(3) Since you're sending probe traffic at a rate that is likely not  
insignificant, how do you prevent the probe traffic itself from  
causing congestion and triggering stop-admission or flow-termination  
actions? If you're treating it differently (e.g., at a lower  
priority), how is what the probe traffic experiences still  
representative of what the real flow would experience? (How can you  
treat it differently and still make ECMP work?)

Without at least some good ideas about what the answers to these  
questions will be I believe it is premature to declare that probing  
is an optional component of PCN.

>    However, the risk should be reduced because it should be  
> possible to
>    send probe packets for a shorter time and at a lower rate than a
>    typical data flow.

This claim is related to (1) and (2) above. Is there any evidence  
that is it possible to "send probe packets for a shorter time and at  
a lower rate than a typical data flow"? I'm not aware of any research  
in this space.

>    The situation is more complicated if there is multipath routing
>    (ECMP) in the PCN-domain.  It is then possible for some paths to be
>    pre-congested whilst other paths within the same ingress-egress-
>    aggregate aren't pre-congested.
>
>    One approach essentially ignores ECMP: as usual, admit or block  
> a new
>    flow depending on the "measurements of PCN-traffic" on the ingress-
>    egress-aggregate.  This is rather similar to the "optimistic"
>    approach above.
>
>    An alternative ("pessimistic" or "proactive") approach is to probe
>    the ECMP path.  The PCN-ingress-node generates and sends probe
>    packets (dummy data) that follow the specific ECMP path that the  
> new
>    flow would do, in order to test the pre-congestion level along it.
>    An ECMP algorithm typically examines: the source and destination IP
>    addresses and port numbers, the protocol ID and the DSCP.  Hence
>    these fields must have the same values in the probe packets as the
>    future data packets would have.  On the other hand, the PCN-egress-
>    node needs to consume the probe packets to ensure that they don't
>    travel beyond the PCN-domain (eg they might confuse the destination
>    end node).  Hence somehow the PCN-egress-node has to be able to
>    disambiguate a probe packet from a data packet, via the
>    characteristic setting of particular bit(s) in the packet's  
> header or
>    body - but these bit(s) mustn't be used by any PCN-interior-node's
>    ECMP algorithm.  This should be possible with a typical ECMP
>    algorithm, but isn't in the general case.

Some things in this paragraph aren't specific to ECMP, such as that  
the egress needs to consume the probe packets.

>    The probing functions are:
>
>    o  Make decision that probing is needed.  As described above,  
> this is
>       when the ingress-egress-aggregate or the ECMP path carries no  
> PCN-
>       traffic.  An alternative is always to probe, ie probe before
>       admitting every PCN-flow.
>
>    o  (if required) Communicate the request that probing is needed  
> - the
>       PCN-egress-node signals to the PCN-ingress-node that probing is
>       needed
>
>    o  Generate probe traffic - the PCN-ingress-node generates the  
> probe
>       traffic.  The appropriate number (or rate) of probe packets will
>       depend on the PCN-marking algorithm; for example an excess-rate-
>       marking algorithm generates fewer PCN-marks than a threshold-
>       marking algorithm, and so will need more probe packets.
>
>    o  Forward probe packets - as far as PCN-interior-nodes are
>       concerned, probe packets must be handled the same as (ordinary
>       data) PCN-packets, in terms of routing, scheduling and PCN-
>       marking.
>
>    o  Consume probe packets - the PCN-egress-node consumes probe  
> packets
>       to ensure that they don't travel beyond the PCN-domain.

Nice summary of the required functions.

Lars

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

---

From: "Georgios Karagiannis" <[email-masked]>
Date: Thu, 1 Nov 2007 13:39:07 +0100

Hi Lars

Please receive some answers on the three questions!

> (1) The ingress needs to generate traffic in a pattern and at 
> a rate that lets it draw conclusions about whether it is OK 
> to admit the flow that is waiting for admission. How does it 
> know what characteristics the probe traffic should have and 
> how does it generate the probe traffic?

Georgios: The PCN_ingress_node generates one probe packet for each new 
incoming flow that requests access from the PCN_domain.

> 
> (2) How long do you need to probe for before you declare it 
> safe to admit the new flow? 
Georgios: One probe packet per new incoming and flow is enough 
if the PCN_domain takes care that the 
probe packet will be marked PCN_marked or using an other type of encoding,
if it is passing through a congested PCN_interior_node.

> What's the delay before a new 
> flow can be admitted, and can apps actually deal with this delay?

The delay = one RTT (within PCN_domain).

> 
> (3) Since you're sending probe traffic at a rate that is 
> likely not insignificant, how do you prevent the probe 
> traffic itself from causing congestion and triggering 
> stop-admission or flow-termination actions? If you're 
> treating it differently (e.g., at a lower priority), how is 
> what the probe traffic experiences still representative of 
> what the real flow would experience? (How can you treat it 
> differently and still make ECMP work?)

Georgios: By just sending one probe packet per new incoming flow that
requests access 
into the PCN_domain.

Best regards,
Georgios

> -----Original Message-----
> From: Lars Eggert [mailto:[email-masked]] 
> Sent: donderdag 1 november 2007 12:38
> To: pcn
> Subject: [PCN] 5.5. Probing functions 
> 
> Hi,
> 
> I read through the section on probing in the architecture 
> draft, and have some comments. Folks know that I'm not too 
> thrilled with the idea of probing, so this should come as no 
> surprise...
> 
> > 5.5.  Probing functions
> >
> aggregates 
> > is
> This discussion on the downsides of probing is too short. Let 
> me list some issues:
> 
> (1) The ingress needs to generate traffic in a pattern and at 
> a rate that lets it draw conclusions about whether it is OK 
> to admit the flow that is waiting for admission. How does it 
> know what characteristics the probe traffic should have and 
> how does it generate the probe traffic?
> 
> (2) How long do you need to probe for before you declare it 
> safe to admit the new flow? What's the delay before a new 
> flow can be admitted, and can apps actually deal with this delay?
> 
> (3) Since you're sending probe traffic at a rate that is 
> likely not insignificant, how do you prevent the probe 
> traffic itself from causing congestion and triggering 
> stop-admission or flow-termination actions? If you're 
> treating it differently (e.g., at a lower priority), how is 
> what the probe traffic experiences still representative of 
> what the real flow would experience? (How can you treat it 
> differently and still make ECMP work?)
> 
> Without at least some good ideas about what the answers to 
> these questions will be I believe it is premature to declare 
> that probing is an optional component of PCN.
> 
> possible 
> > to
> This claim is related to (1) and (2) above. Is there any 
> evidence that is it possible to "send probe packets for a 
> shorter time and at a lower rate than a typical data flow"? 
> I'm not aware of any research in this space.
> 
> >    One approach essentially ignores ECMP: as usual, admit 
> or block a 
> > new
> >    characteristic setting of particular bit(s) in the 
> packet's header 
> > or
> Some things in this paragraph aren't specific to ECMP, such 
> as that the egress needs to consume the probe packets.
> 
> >    o  Make decision that probing is needed.  As described 
> above, this 
> > is

---

From: Lars Eggert <[email-masked]>
Date: Thu, 1 Nov 2007 15:10:21 +0200

Hi,

> incoming flow that requests access from the PCN_domain.

how is a single packet probing the path? It's not obvious to me how  
one would derive bottleneck load based on a single packet, i.e.,  
based on one or zero markings.

> if the PCN_domain takes care that the probe packet will be marked  
> PCN_marked or using an other type of encoding, if it is passing  
> through a congested PCN_interior_node.

Ah - so this requires the marking scheme to mark all packets once the  
defined pre-congestion load level is reached, instead of marking  
proportionally with an increase in load, correct? This eliminates  
some of the marking options that have been discussed.

And you need to ensure that - after having gotten an indication of  
"not loaded" from the path - the single flow you're about to admit  
cannot by itself push the bottleneck straight into overload. This is,  
because the "not loaded" piece of information doesn't tell you how  
close to pre-congestion the bottleneck is, and if it can actually  
sustain the rate that the flow is going to send at.

You could do this through appropriate configuration, i.e., ensuring  
that the level at which you start marking is sufficiently below the  
overload state that you can sustain one new flow. Or two. Or three.  
How much is enough?

And if you did this through configuration, i.e., making sure that  
1,2,3,... flows can be admitted, what's the benefit of probing? Why  
not simply admit the flow?

> requests access into the PCN_domain.

Lars

---

From: "Georgios Karagiannis" <[email-masked]>
Date: Thu, 1 Nov 2007 16:12:51 +0100

Hi Lars

Please see in line!

Best regards,
Georgios

> Sent: donderdag 1 november 2007 14:10
> To: ext Georgios Karagiannis
> Cc: 'pcn'
> Subject: Re: [PCN] 5.5. Probing functions 
> 
> Hi,
> 
> how is a single packet probing the path? It's not obvious to 
> me how one would derive bottleneck load based on a single 
> packet, i.e., based on one or zero markings.

Georgios: The PCN_ingress_node sends a probe packet and it waits 
for a response from the PCN_egress_node. 
If a PCN_interior_node is congested (is in admission control state),
then the probe will be marked, either using the PCN_marking or an additional
encoding, say PCN_Affected_marking.
If the probe packet is dropped on the way, then the PCN_ingress_node has to
know this
such that the probe packet is retransmitted. This can be done by using
retransmission timers at the PCN_ingress_node.

> >> admit the new flow?
> > Georgios: One probe packet per new incoming and flow is 
> enough if the 
> > PCN_domain takes care that the probe packet will be marked 
> PCN_marked 
> > or using an other type of encoding, if it is passing through a 
> > congested PCN_interior_node.
> 
> Ah - so this requires the marking scheme to mark all packets 
> once the defined pre-congestion load level is reached, 
> instead of marking proportionally with an increase in load, 
> correct? 

Georgios: No! Marking proportionally is still needed, since it is also
needed
to encode the flow termination state of the PCN_interior nodes.
However, all packets that are passing through the congested node and are not
PCN_marked 
they will have to be remarked with this additional encoding, denoted as
PCN_Affected_marking.

> This eliminates some of the marking options that 
> have been discussed.

Georgios: No, please see above!

> 
> And you need to ensure that - after having gotten an 
> indication of "not loaded" from the path - the single flow 
> you're about to admit cannot by itself push the bottleneck 
> straight into overload. This is, because the "not loaded" 
> piece of information doesn't tell you how close to 
> pre-congestion the bottleneck is, and if it can actually 

Georgios: Yes, you are right, this is an issue that occurs in a similar way
on
all MBAC mechanisms. 

> 
> You could do this through appropriate configuration, i.e., 
> ensuring that the level at which you start marking is 
> sufficiently below the overload state that you can sustain 
> one new flow. Or two. Or three.  
> How much is enough?
> 
> And if you did this through configuration, i.e., making sure 
> that 1,2,3,... flows can be admitted, what's the benefit of 
> probing? Why not simply admit the flow?

Georgios: This preconfiguration might not be easy, but it is 
needed when any type of precongesion mechanism (that is not using probing) 
is used. 

When probing is used, then the PCN_egress_node is certain that when a
received probe is marked
that this probe (and thus all that packets that are associated with the flow
that generated the proobe packet) 
is/will be passing through the congested node. In this situation the
requesting 
flow is rejected. If the probe is not marked then 
the requesting flow is admitted. 
If probing is not used, then the PCN_egress_node cannot be certain about
such decissions.

Furthermore, when probing is used, the admission control mechanism also
works when the 
ingress/egress aggregate is not yet available/created at the
PCN_egress_node.
This cannot be done if probing is not used.

> likely not

---

From: Lars Eggert <[email-masked]>
Date: Mon, 5 Nov 2007 10:57:27 +0200

Hi,

> encoding, say PCN_Affected_marking.

ah - so this depends on the fact that a congested router uses a  
marking scheme that always tags the packet with _something_.

In other words, this wouldn't work with Anna's single-bit marking  
scheme, right? (Because that does not mark all packets passing a  
congested router.)

> know this such that the probe packet is retransmitted. This can be  
> done by using

That adds delay, obviously. You also need to defined some  
retransmission scheme that is safe without knowing the path RTT.

>>> Georgios: One probe packet per new incoming and flow is enough if  
>>> the
> needed to encode the flow termination state of the PCN_interior nodes.
> PCN_marked they will have to be remarked with this additional  
> encoding, denoted as
> PCN_Affected_marking.

Thanks - I think I've understood this now. See above for my comments  
about single-bit marking - this wouldn't work with single-bit  
marking, would it?

> Georgios: No, please see above!

I still believe this does eliminate single-bit marking.

>>> The delay = one RTT (within PCN_domain).

So what happens to the flow during the RTT needed for probing?  
Packets are dropped? That would seem to significantly affect various  
apps.

Lars

---

From: "Anna Charny (acharny)" <[email-masked]>
Date: Mon, 5 Nov 2007 07:26:30 -0500

Hi Lars,

Please see below: 

> Sent: Monday, November 05, 2007 3:57 AM
> > Georgios: The PCN_ingress_node sends a probe packet and it 
> waits for a 
> > response from the PCN_egress_node.
> > then the probe will be marked, either using the PCN_marking or an 
> > additional encoding, say PCN_Affected_marking.
> 
> ah - so this depends on the fact that a congested router uses 
> a marking scheme that always tags the packet with _something_.
> 
> In other words, this wouldn't work with Anna's single-bit 
> marking scheme, right? (Because that does not mark all 
> packets passing a congested router.)
> 

You are quite right - single marking would not necessarily mark a 
probe message - you would need to send several probes to notice 
that the path is congested with high enough probability - and that
introduces an additional delay.  This does not happen with schemes that
mark all packets with something when the  path is congested (for which
you need an additional codepoint).    

All of this assumes that RSVP message/probe goes through the same path
as the data - which happens for some ECMP hashes and not for others. 

Anna 

> > If the probe packet is dropped on the way, then the 
> PCN_ingress_node 
> > has to know this such that the probe packet is 
> retransmitted. This can 
> > be done by using retransmission timers at the PCN_ingress_node.
> 
> >>> the PCN_domain takes care that the probe packet will be marked 
> >> proportionally with an increase in load, correct?
> >
> > However, all packets that are passing through the congested 
> node and 
> > are not PCN_marked they will have to be remarked with this 
> additional 
> > encoding, denoted as PCN_Affected_marking.
> 
> Thanks - I think I've understood this now. See above for my 
> comments about single-bit marking - this wouldn't work with 
> single-bit marking, would it?
> 
> >> This eliminates some of the marking options that have been 
> discussed.
> >
> Packets are dropped? That would seem to significantly affect 
> various apps.
> 
> Lars
>

---

From: <[email-masked]>
Date: Mon, 5 Nov 2007 19:30:32 -0000

General conclusion is that next version of arch draft needs to include
more on the downsides of probing. Also seems to be a feeling that should
be out of initial scope [not sure if this needs saying in draft]

Follow-ups in-line
Phil

> Sent: 01 November 2007 11:38
> To: pcn
> Cc: Eardley,PL,Philip,CXR9 R
> Subject: 5.5. Probing functions
> 
[cut]
> is an optional component of PCN.

I think these are fair points.
My impression is that probing advocates have 2 reasons:
- the on-going ingress-egress-aggregate measurement of marked pkts
doesn't work. Because there's often no traffic on this
ingress-egress-aggregate, or no traffic on the ECMP path; AND simply
admitting the flow has a significant risk of leading to overload [pkts
dropped &/or flows terminated]
- there's no signalling state on the PCN-boundary-nodes for this
ingress-egress-aggregate (and no traffic already on it); AND the router
behaviour is such that every pkt is marked if the flow should be
blocked; AND just admitting the call is dangerous because there's a good
chance of overload in some parts of the nw (near the edge where the
capacity is low). Hence probing creates no extra delay (since you have
to send a signalling set-up msg anyway). Often this scenario is people
who envisage PCN going to end terminals or at least further out than
core nw [I think].

The first scenario will only happen in narrow conditions [flash crowds,
many ingress-egress-aggregates without any traffic]. An alternative way
of handling this is to limit the rate at which admit new flows [at least
this makes the conditions when the problem occurs even narrower].
The second scenario seems to break the (link) aggregation assumption?
presumably it could be solved by running different mechanism at the edge
compared with at the core. [joe, sorry if you've already explained, the
late hour => even poorer memory than usual.]

> the egress needs to consume the probe packets.

in the non-ecmp scenario the pcn-ingress-node is sending probes
addressed to the pcn-egress-node, so it's quite easy for the egress to
consume them!

---

From: Lars Eggert <[email-masked]>
Date: Tue, 6 Nov 2007 10:19:11 +0200

Hi,

> My impression is that probing advocates have 2 reasons:

thanks for summarizing this! I think this does capture the main  
points made.

> who envisage PCN going to end terminals or at least further out than

Although I agree that we can construct scenarios where "simply  
admitting the flow has a significant risk of leading to overload", I  
still remain unclear on how likely such cases are in whatever we  
envision the most likely deployment scenarios to be. Basically, I  
worry that we're making the architecture complex for what will  
provide little real benefit in the end.

Also, don't forget that using probing will mean dropping the packets  
of the flow waiting for admission for an RTT *every time* probing is  
used. Whereas "just admitting" may only cause overload sometimes.  
There is a tradeoff here - I believe it's possible to construct a  
case where probing hurts more than "just admitting."

And I'm still waiting for someone to convince me that dropping the  
initial packets of a flow at the ingress during the probing RTT will  
result in something that is acceptable for apps.

> this makes the conditions when the problem occurs even narrower].

And we should try to determine how narrow these conditions are. If  
they're very narrow, we may be able to avoid them through  
configuration suggestions (sufficient overprovisioning, sufficiently  
broad marking regions, etc.)

> late hour => even poorer memory than usual.]

Yes, we seem to be running into the "the number of flows across any  
potential aggregation bottleneck is sufficiently large for stateless,  
statistical mechanisms to be effective" restriction from the charter  
here. These scenarios seems to require a deterministic mechanism,  
while PCN is supposed to provide a probabilistic one.

Lars

---

From: Michael Menth <[email-masked]>
Date: Tue, 06 Nov 2007 09:29:00 +0100

Hi Lars and Phil,

I think that one major motivation for probing is to make PCN capable to 
deal with multipath routing like ECMP. Some path are empty, others are 
full. Some flows must be rejected, others can proceed although they all 
belong to the same ingress-egress-aggregate.

Regards,

    Michael

Lars Eggert wrote:
> thanks for summarizing this! I think this does capture the main points 
> made.
>
> worry that we're making the architecture complex for what will provide 
> little real benefit in the end.
>
> There is a tradeoff here - I believe it's possible to construct a case 
> where probing hurts more than "just admitting."
>
> ------------------------------------------------------------------------
>

-- 
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: <[email-masked]>
Date: Tue, 6 Nov 2007 09:13:08 -0000

Michael

Do you have an idea of how likely this is? will it be the case that for
a small increase in load all/most of the ECMP paths become full? Does it
depend strongly on topology? If each link is shared by mnay ecmp paths
from many different ingress-egress-aggregates is this less of a risk?

phil

> From: Michael Menth [mailto:[email-masked]]
> Sent: 06 November 2007 08:29
> To: Lars Eggert
> Cc: Eardley,PL,Philip,CXR9 R; [email-masked]
> Subject: Re: [PCN] Re: 5.5. Probing functions
> 
> Hi Lars and Phil,
> 
points
> > worry that we're making the architecture complex for what will
provide
> > There is a tradeoff here - I believe it's possible to construct a
case

---

From: Michael Menth <[email-masked]>
Date: Tue, 06 Nov 2007 11:25:33 +0100

Hi Phil and others,

I don't know how likely this is in operational networks, it certainly 
depends on topology, routing, and traffic dynamics.

We did a study on load balancing algorithms with a different focus. It 
turned out that with static load balancing significant imbalances occur 
due to statistical effects even if a 50:50 balance is envisaged.
http://www3.informatik.uni-wuerzburg.de/staff/menth/Publications/Menth06p.pdf

This is just one source of traffic imbalance. Another and more important 
issue is that links of a network can have substantially different 
utilization, no matter due to with reason (different bandwidth, 
different traffic load, different amount of backup capacity, ...). 
Therefore, some alternative paths of a single ingress-egress-aggregate 
have high utilization, others have low utilization. If the load 
increases, some flows of that aggregate must be blocked while others can 
safely be admitted.

If we do not consider this issue, we need to ask ourselves why we look 
at admission control at all for such networks instead of just doing 
reasonable overprovisioning (if it's possible and economically viable).

Regards,

    Michael

[email-masked] wrote:
>> I think that one major motivation for probing is to make PCN capable
>>     
> to
>   
>> full. Some flows must be rejected, others can proceed although they
>>     
> all
>   
>>>> ingress-egress-aggregate, or no traffic on the ECMP path; AND
>>>>         
> simply
>   
>>>> admitting the flow has a significant risk of leading to overload
>>>>         
> [pkts
>   
>>>> ingress-egress-aggregate (and no traffic already on it); AND the
>>>>         
> router
>   
>>>> blocked; AND just admitting the call is dangerous because there's a
>>>>         
>> good
>>     
>>>> capacity is low). Hence probing creates no extra delay (since you
>>>>         
> have
>   
>>>> to send a signalling set-up msg anyway). Often this scenario is
>>>>         
> people
>   
>>>> who envisage PCN going to end terminals or at least further out
>>>>         
> than
>   
>>>> core nw [I think].
>>>>         
>>>> The first scenario will only happen in narrow conditions [flash
>>>>         
> crowds,
>   
>>>> many ingress-egress-aggregates without any traffic]. An alternative
>>>>         
> way
>   
>>>> of handling this is to limit the rate at which admit new flows [at
>>>>         
>> least
>>     
>>>>  The second scenario seems to break the (link) aggregation
>>>>         
> assumption?
>   
>>>> presumably it could be solved by running different mechanism at the
>>>>         
>> edge
>>     
>>>> compared with at the core. [joe, sorry if you've already explained,
>>>>         
> the
>   
>>> potential aggregation bottleneck is sufficiently large for
>>>       
> stateless,
>

---

From: "Anna Charny (acharny)" <[email-masked]>
Date: Tue, 6 Nov 2007 09:31:42 -0500

Hi Phil, Michael,

Based on our own internal study here are a few highlights that can shed
light on the ECMP accuracy:

1) once the number of flows (at hash granularity) becomes large
(~100,000), most hashes perform very well at a single hop for a wide
range of hash inputs.
2) when the number of flows in a hash is smaller (not that small
actually - on the order of 1000!) practically all hashes display large
statistical variation for some distributions of the hash inputs (where
large is on the order 20-40% or more of relative error per bucket).
This appears to be true for a wide set of hashes, including those shown
very robust in many academic studies.

The above is for single hop only, and for heterogeneous traffic rates.
If flow rates distribution is skewed (i.e. there are a few large flows),
it can become much worse wrt actual bandwidth distribution. Some of the
known ways to fix this issue is to employ hashes that look deeper into
the packets so that large flows (e.g. based on (src, dst) hash) get
split into smaller flows (e.g. look not only at src,dst, but also at
layer 4 info) - but note that these same methods cause, for our PCN
purposes, a problem that rsvp messages may no longer follow the same
path as the data packets. 

So I think realistically, for truly large aggregation at the core, ECMP
imbalances are likely to be not much of an issue, but for relatively
lower levels of aggregation one might expect that fairly large ECMP
inaccuracies in some cases are quite possible.  Note that "relatively
low aggregation" may occur for tunneled traffic (i.e. lots of small
flows are aggregated into a relatively small number of large tunnels). 

Anna 

> From: [email-masked] [mailto:[email-masked]] 
> Sent: Tuesday, November 06, 2007 4:13 AM
> To: [email-masked]; [email-masked]
> Cc: [email-masked]
> Subject: RE: [PCN] Re: 5.5. Probing functions
> 
> Michael
> 
> Do you have an idea of how likely this is? will it be the 
> case that for a small increase in load all/most of the ECMP 
> paths become full? Does it depend strongly on topology? If 
> each link is shared by mnay ecmp paths from many different 
> ingress-egress-aggregates is this less of a risk?
> 
> phil
> 
> > Dr. Michael Menth, Assistant Professor University of Wuerzburg, 
> > Institute of Computer Science Am Hubland, D-97074 
> Wuerzburg, Germany, 
> > room B206

---

From: Michael Menth <[email-masked]>
Date: Tue, 06 Nov 2007 16:20:08 +0100

Hi Anna, Phil,

Anna, you addressed the impact of ECMP on possible imbalances of link 
utilization. I am with you in the sense that this is only a minor issue 
in networks with high traffic aggregation.

However, the point I wanted to make is that different links can have 
different utilizations in their normal operational mode (e.g. because 
some of them are provisioned with backup capacity for rerouted traffic, 
others aren't). This effect is not caused by ECMP or load balancing in 
general. But the consequence of that effect is that alternative paths 
can have substantially different utilization which possibly becomes 
problematic when ECMP is used in the presence of PCN-based admission 
control.

Regards,

    Michael

Anna Charny (acharny) wrote:
>>> deal with multipath routing like ECMP. Some path are empty, 
>>>       
>> others are 
>>     
>>>>> - the on-going ingress-egress-aggregate measurement of 
>>>>>           
>> marked pkts 
>>     
>>>>> blocked; AND just admitting the call is dangerous 
>>>>>           
>> because there's a
>>     
>>> good
>>>       
>>>>> chance of overload in some parts of the nw (near the 
>>>>>           
>> edge where the 
>>     
>>>> admitting the flow has a significant risk of leading to 
>>>>         
>> overload", I 
>>     
>>>> Also, don't forget that using probing will mean dropping 
>>>>         
>> the packets 
>>     
>>>> of the flow waiting for admission for an RTT *every time* 
>>>>         
>> probing is 
>>     
>>>> And I'm still waiting for someone to convince me that 
>>>>         
>> dropping the 
>>     
>>>> initial packets of a flow at the ingress during the 
>>>>         
>> probing RTT will 
>>     
>>>>> many ingress-egress-aggregates without any traffic]. An 
>>>>>           
>> alternative
>> way
>>     
>>>>> of handling this is to limit the rate at which admit new 
>>>>>           
>> flows [at
>>     
>>> least
>>>       
>>>> And we should try to determine how narrow these 
>>>>         
>> conditions are. If 
>>     
>>>> configuration suggestions (sufficient overprovisioning, 
>>>>         
>> sufficiently 
>>     
>>>>> presumably it could be solved by running different 
>>>>>           
>> mechanism at the
>>     
>>> edge
>>>       
>>>>> compared with at the core. [joe, sorry if you've already 
>>>>>           
>> explained,
>> the
>>     
>>>> Yes, we seem to be running into the "the number of flows 
>>>>         
>> across any 
>>     
>>>> statistical mechanisms to be effective" restriction from 
>>>>         
>> the charter 
>>

---

From: "Anna Charny (acharny)" <[email-masked]>
Date: Tue, 6 Nov 2007 10:38:55 -0500

Hi Michael, 

> Sent: Tuesday, November 06, 2007 10:20 AM
> To: Anna Charny (acharny)
> Cc: Philip Eardley; Lars Eggert; [email-masked]
> Anna, you addressed the impact of ECMP on possible imbalances 
> of link utilization. I am with you in the sense that this is 
> only a minor issue in networks with high traffic aggregation.
> 

Actually my point was not only that with sufficiently large aggregations
levels ECMP imbalance is not an practical issue - it was also that there
are realistic circumstances when ECMP imbalance may in fact be an issue
(specifically, deployments with large tunnels)

> However, the point I wanted to make is that different links 
> can have different utilizations in their normal operational 
> mode (e.g. because some of them are provisioned with backup 
> capacity for rerouted traffic, others aren't). This effect is 
> not caused by ECMP or load balancing in general. But the 
> consequence of that effect is that alternative paths can have 
> substantially different utilization which possibly becomes 
> problematic when ECMP is used in the presence of PCN-based 
> admission control.
> 

Would't we expect that in this case PCN thresholds will be chosen as
part of traffic engineering/network planning to reflect the expected
utilisation with and without "planned" failures - so setting these PCN
thresholds (as well as the rest of the network planning tasks) will be
chosen with the expected ECMP load-balancing in mind? So the issue of
imbalances will only/typically occur for "unplanned" multiple failures
or flash crowds for which this planning fails?  

Anna 

Anna 

> > Based on our own internal study here are a few highlights that can 
> > shed light on the ECMP accuracy:
> >
> > This appears to be true for a wide set of hashes, including those 
> > shown very robust in many academic studies.
> >
> > If flow rates distribution is skewed (i.e. there are a few large 
> > flows), it can become much worse wrt actual bandwidth distribution. 
> > Some of the known ways to fix this issue is to employ 
> hashes that look 
> > deeper into the packets so that large flows (e.g. based on 
> (src, dst) 
> > hash) get split into smaller flows (e.g. look not only at 
> src,dst, but 
> > also at layer 4 info) - but note that these same methods cause, for 
> > our PCN purposes, a problem that rsvp messages may no longer follow 
> > the same path as the data packets.
> >
> > So I think realistically, for truly large aggregation at the core, 
> > ECMP imbalances are likely to be not much of an issue, but for 
> > relatively lower levels of aggregation one might expect that fairly 
> > large ECMP inaccuracies in some cases are quite possible.  
> Note that 
> > "relatively low aggregation" may occur for tunneled traffic 
> (i.e. lots 
> > of small flows are aggregated into a relatively small 
> number of large tunnels).
> >
> > Anna
> >  
> >
> >   
> case that 
> >> for a small increase in load all/most of the ECMP paths 
> become full? 
> >> Does it depend strongly on topology? If each link is 
> shared by mnay 
> >> ecmp paths from many different ingress-egress-aggregates 
> is this less 
> >> of a risk?
> >>
> >> phil
> >>
> >>     
> University of Wuerzburg, Institute of Computer Science Am 
> Hubland, D-97074 Wuerzburg, Germany, room B206