Subject: Re: [Fwd: I-D Action:draft-ietf-6man-flow-update-00.txt]

From: Brian E Carpenter <[email-masked]>
Date: Mon, 10 Jan 2011 09:33:08 +1300

When reviewing the text for the next update, I rediscovered that
we do in fact say

"The proposed generic use is to encourage pseudo-random flow labels that can be used to assist load balancing."

so (with draft-ietf-6man-flow-ecmp also in progress) I think Fred's
point is covered.

Regards
   Brian

On 2010-12-15 15:00, Brian E Carpenter wrote:
> We do have draft-ietf-6man-flow-ecmp, which is focussed on ECMP/LAG
> load sharing in tunnels. The reason we're proposing to recommend
> pseudo-random labels by default is so that load sharing becomes a
> natural use case.
> 
> When we did RFC 3697, there was strong pressure to keep the spec
> as "pure" as possible. I was sort of assuming the same approach
> this time around. Of course, the WG can decide otherwise, but
> embedding the use case(s) in the protocol spec does lengthen
> the discussion considerably.
> 
> Regards
>    Brian
> 
> On 2010-12-15 14:26, Fred Baker wrote:
>> So you're really really not interested in discussing the one use case that people have actually talked about wanting, which has to do with load sharing? What use case are you addressing?
>>
>> On Dec 14, 2010, at 5:14 PM, Brian E Carpenter wrote:
>>
>>> Hi,
>>>
>>> The authors have received one off-list comment on this version,
>>> requesting additional clarification of the text associated with
>>> this recommendation:
>>>
>>>>>       2.  A network domain MUST NOT forward packets outside the domain
>>>>>           whose flow label values are other than zero or pseudo-random.
>>>>>
>>> Does anyone else have comments, or are we getting somewhere near agreement?
>>>
>>> Regards
>>>   Brian Carpenter
>>>
>>>
>>> On 2010-12-03 12:40, Brian E Carpenter wrote:
>>>> Hi,
>>>>
>>>> This is intended to reflect the various comments made in Beijing,
>>>> notably strengthening the points about the flow label not being
>>>> changed en route. Please review - if the WG is generally OK
>>>> with this version, we'll start to think about RFC3697bis.
>>>>
>>>>  Brian + Sheng + Shane
>>>>
>>>> -------- Original Message --------
>>>> Subject: I-D Action:draft-ietf-6man-flow-update-00.txt
>>>> Date: Thu, 02 Dec 2010 15:00:02 -0800
>>>> From: [email-masked]
>>>> Reply-To: [email-masked]
>>>> To: [email-masked]
>>>> CC: [email-masked]
>>>>
>>>> A New Internet-Draft is available from the on-line Internet-Drafts directories.
>>>> This draft is a work item of the IPv6 Maintenance Working Group of the IETF.
>>>>
>>>>
>>>> 	Title           : Update to the IPv6 flow label specification
>>>> 	Author(s)       : S. Amante, et al.
>>>> 	Filename        : draft-ietf-6man-flow-update-00.txt
>>>> 	Pages           : 13
>>>> 	Date            : 2010-12-02
>>>>
>>>> Various published proposals for use of the IPv6 flow label are
>>>> incompatible with its existing specification in RFC 3697.
>>>> Furthermore, very little practical use is made of the flow label,
>>>> partly due to some uncertainties about the correct interpretation of
>>>> the specification.  This document proposes changes to the
>>>> specification in order to clarify it, making it clear what types of
>>>> usage are possible, and to introduce some additional flexibility.
>>>>
>>>> A URL for this Internet-Draft is:
>>>> http://www.ietf.org/internet-drafts/draft-ietf-6man-flow-update-00.txt
>>>>
>>>>
>>>>
>>>>
>>> --------------------------------------------------------------------
>>> IETF IPv6 working group mailing list
>>> [email-masked]
>>> Administrative Requests: https://www.ietf.org/mailman/listinfo/ipv6
>>> --------------------------------------------------------------------
>>
>

---

From: Fred Baker <[email-masked]>
Date: Sun, 9 Jan 2011 17:26:03 -0800

The issue is that randomness doesn't help, if you want a scalable approach. It means that for each flow passing through the load balancing system, I have to store its flow label and assign it a path. What are the arguments against NATs? One of the big ones is the expectation of per-flow state in the network, isn't it? If you're expecting the network to store per-flow state, you by definition have a scaling problem in the network.

To use the flow label in load sharing and have it be remotely scalable, the network needs to be in control of the label.

---

From: Brian E Carpenter <[email-masked]>
Date: Mon, 10 Jan 2011 14:45:05 +1300

Fred,

I'm confused. We've been talking for months about recommending
pseudo-random flow label values as inputs to hash functions,
precisely to allow scaleable and stateless load balancing and ECMP.

I completely agree that per-flow state doesn't scale.

Regards
   Brian Carpenter

---

From: "Joel M. Halpern" <[email-masked]>
Date: Sun, 09 Jan 2011 21:35:08 -0500

Let me phrase Brian's comment differently.
Presume we actually get wide use of the flow label in accordance with 
the load balancing draft.

What can go wrong?  Well, someone could send all their traffic with a 
single flow label, reducing the randomness.
So what goes wrong.  All of that subscribers traffic ends up on a single 
link.  Mostly, that means that if he does this, he increases the 
likelihood that his traffic will get damaged.  Seems unlikely he would 
choose to do that.

We coudl fo course view this as a deliberate attack.  But, in fact, it 
is an attack that could already be done.  The subscriber simply sends 
all his traffic with a single set of ports (source and dest).  That will 
have the exact same effect on the current system that a fixed flow-label 
would have under the proposed behavior.

So I do not see why the network needs to "control" the flow label, any 
more than it needs to "control" the ports the subscriber uses.

Yours,
Joel

---

From: Steven Blake <[email-masked]>
Date: Sun, 09 Jan 2011 23:05:25 -0400

On Mon, 10 Jan 2011 14:45:05 +1300, Brian E Carpenter 
 <[email-masked]> wrote:

>> The issue is that randomness doesn't help, if you want a scalable 
>> approach.
>> It means that for each flow passing through the load balancing 
>> system, I have
>> to store its flow label and assign it a path. What are the arguments 
>> against
>> NATs? One of the big ones is the expectation of per-flow state in 
>> the network,
>> isn't it? If you're expecting the network to store per-flow state, 
>> you by
>> definition have a scaling problem in the network.
>>
>> To use the flow label in load sharing and have it be remotely 
>> scalable,
>> the network needs to be in control of the label.

 Perhaps Fred has applications of "load balancing" beyond ECMP or LAG in 
 mind?

 The network doesn't control port numbers, so his argument obviously 
 doesn't
 apply to ECMP or LAG.

 Regards,

 // Steve

---

From: Fred Baker <[email-masked]>
Date: Sun, 9 Jan 2011 21:42:16 -0800

> I completely agree that per-flow state doesn't scale.

This isn't exactly the first time I have made the statement. I've been on record on this point regarding the flow label since it was designed to answer NIMROD's definition of a flow.

---

From: Fred Baker <[email-masked]>
Date: Sun, 9 Jan 2011 21:55:46 -0800

On Jan 9, 2011, at 7:05 PM, Steven Blake wrote:

> The network doesn't control port numbers, so his argument obviously doesn't apply to ECMP or LAG.

There are more than two common uses of load balancing. ECMP is a side effect of routing; we decide to multipath route when we know of two next hops that get us to a remote destination with the same routing metric. Link Aggregation (LAG) is what is done when I have multiple paths between myself and my next hop and want to distribute a data stream across them. Yes, those are important.

The most common use of load balancing is most likely the use in data centers, where I decide that (to pick but one example) a given HTTP GET is appropriate to one set of servers and a different one, perhaps within the same pipelined TCP session, is appropriate to a different one, and multiplex the session across these sets of servers as appropriate. If you look up the class of products referred to as "load balancers", you will find them in those and similar applications. There are a number of other uses, but they are typified by that use case.

If I want a random hash, I can - and do, and have since before the Internet was a commercial network - already generate that, by hashing the pseudoheader (actually just the source and destination address) of a stream of datagrams. That means that I don't have to remember which flow label I sent on one path and which I sent on another. If you want to tell me "oh, I take the modulus of the flow label with the number of servers I have to select which server", or any similar stateless algorithm, I can do it with that hash just as easily. And yes, that gives me a session predictably going to the same server. But it doesn't allow me to balance loads. To balance loads, I need to estimate the load on individual paths, and assign new data streams to paths as they change in their actual loading.

What having the network be in control of the flow label does is allow the network to balance loads. Which is what you were trying to do, wasn't it?

---

From: "Joel M. Halpern" <[email-masked]>
Date: Mon, 10 Jan 2011 08:33:02 -0500

A data center load balancer can afford, by its nature, to do as much 
work as it needs to in order to get the information it needs.
The same can not be said for the ECMP / LAG case which Brian, Shane, 
Steve, and I have been talking about.

Specifically, with the structure of extension headers, the possible use 
of crypto, and the use of tunnels (and probably other issues), it 
becomes more and more difficult for network devices along the path which 
need to perofrm ECMP or LAG (L3 or L2 sleection among equivalent paths) 
while keeping flows together, to do their job.
By getting the flow label used in a way that carries enough information, 
this problem can become MUCH simpler.

None of your concerns seem to relate to the this problem.
In particular, I see no issue of network side control for this.

Yours,
Joel

---

From: Thomas Narten <[email-masked]>
Date: Mon, 10 Jan 2011 09:10:25 -0500

> precisely to allow scaleable and stateless load balancing and ECMP.

I have a general issue with the above, but I'm not sure whether its a
real issue or just terminology.

The crux of the issue is the following:

>    1.  It is RECOMMENDED that source hosts support the flow label by
>        setting the flow label field for all packets of a flow to the
>        same pseudo-random value.

I do not see a reason to require this.

The goal of using the Flow Label with load balancing is to include it
as input to the hash in order to produce a more uniform spread of the
output of the hash, and specifically, so different flows from the same
machine can be sent across different links.

You do NOT need uniform spread on the input to the hash to get such an
output. A decent hash algorithm is what you need. You also don't need
Flow Labels selected in a psuedo random fashion.

RFC 3697 says specifically you can assign Flow Label values
sequentially. And that works just fine with the modulo(N) algorithm
specified in the ECMP document.

Note that I am in favor of suggesting that the Flow Label be included
in the hash when doing load balancing. Its a no brainer. At worst, its
a now op. But it certainly is never better to exclude it.

What I don't think is needed, is *any* requirement for
pseudo-randomness on the actual Flow Label values.

Thomas

---

From: Christian Huitema <[email-masked]>
Date: Mon, 10 Jan 2011 19:26:00 +0000

Fred wrote:

> Note that I am in favor of suggesting that the Flow Label be included in the hash when doing load balancing. It is a no brainer. At worst, it is a no op. But it certainly is never better to exclude it.

Have you looked at the security implications? Suppose that an attacker can predict the hash algorithm used by a router. This attacker could then pick "interesting" values of the flow ID, to get the flow of traffic directed to particular paths, or not. For example, they could systematically but a different flow label to each packet to ensure the traffic is spread over all available paths.

-- Christian Huitema

---

From: Thomas Narten <[email-masked]>
Date: Mon, 10 Jan 2011 14:51:44 -0500

> Have you looked at the security implications? Suppose that an
>  attacker can predict the hash algorithm used by a router. This
>  attacker could then pick "interesting" values of the flow ID, to
>  get the flow of traffic directed to particular paths, or not. For
>  example, they could systematically but a different flow label to
>  each packet to ensure the traffic is spread over all available
>  paths.

Yes, this is a potential problem.

That said, the router has no assurance that the Flow Label values are
not predictable, since it is others that set its value. Thus, no
router can *depend* on the properties of the Flow Label to be psuedo
random. Thus, nothing we require of the sender can obviate the need
for a router to assume worst-case behavior from a DOS perspective.

I.e., routers would do well (if they are concerned) to do something
not predicitable in terms of the hash it uses. Yes, that increases the
cost of the hash, but in today's world of Bad Guys doing Evil Things,
it may just be a cost of doing business. :-(

But IMO, it is not a requirement for the sender to choose
psuedo-random values for the Flow ID, and because there is no way to
enforce that in general there doesn't seem to me to be clear reason to
do so. Routers will not be able to rely on such properties in any
case, which is what the real issue is.

Thomas

---

From: Brian E Carpenter <[email-masked]>
Date: Tue, 11 Jan 2011 11:16:55 +1300

On 2011-01-10 18:42, Fred Baker wrote:
>> I'm confused. We've been talking for months about 
>> recommending pseudo-random flow label values as inputs to 
>> hash functions, precisely to allow scaleable and stateless 
>> load balancing and ECMP.
>> 
> This isn't exactly the first time I have made the statement. 
> I've been on record on this point regarding the flow label 
> since it was designed to answer NIMROD's definition of a 
> flow.

That is a long time ago, and actually the origin is even older
(as noted in draft-hu-flow-label-cases). But anyway, I don't
think we're disagreeing on this point.

On 2011-01-10 18:55, Fred Baker wrote:

> There are more than two common uses of load balancing. ECMP
> is a side effect of routing; we decide to multipath route
> when we know of two next hops that get us to a remote
> destination with the same routing metric. Link Aggregation
> (LAG) is what is done when I have multiple paths between
> myself and my next hop and want to distribute a data stream
> across them. Yes, those are important.
> 
> The most common use of load balancing is most likely the use
> in data centers, where I decide that (to pick but one
> example) a given HTTP GET is appropriate to one set of
> servers and a different one, perhaps within the same
> pipelined TCP session, is appropriate to a different one, and
> multiplex the session across these sets of servers as
> appropriate. If you look up the class of products referred to
> as "load balancers", you will find them in those and similar
> applications. There are a number of other uses, but they are
> typified by that use case.

Sure, and I think the approach in draft-ietf-6man-flow-ecmp
would work there too.

> 
> If I want a random hash, I can - and do, and have since
> before the Internet was a commercial network - already
> generate that, by hashing the pseudoheader (actually just the
> source and destination address) of a stream of datagrams.
> That means that I don't have to remember which flow label I
> sent on one path and which I sent on another. 

You don't need to remember anything in the stateless
draft-ietf-6man-flow-ecmp model.

If you want to
> tell me "oh, I take the modulus of the flow label with the
> number of servers I have to select which server", or any
> similar stateless algorithm, I can do it with that hash just
> as easily. And yes, that gives me a session predictably going
> to the same server. But it doesn't allow me to balance loads.
> To balance loads, I need to estimate the load on individual
> paths, and assign new data streams to paths as they change in
> their actual loading.

Why is that better than a statistical approach? I assume we're
talking about thousands of flows. In any case, in massive
server farms, the server load may be a more important parameter
than the network path load.

> 
> What having the network be in control of the flow label does
> is allow the network to balance loads. Which is what you were
> trying to do, wasn't it?

Well, have you read the fine detail of the current draft
(today's version will do fine)? The intent is to provide
a default mechanism but to recognize the reality that we cannot
prevent network domains doing otherwise. That's what we authors
understood to be the WG rough consensus after multiple drafts.

    Brian

---

From: Brian E Carpenter <[email-masked]>
Date: Tue, 11 Jan 2011 11:25:27 +1300

I'm not sure there's a problem here. The draft has the
pseudo-random label as a SHOULD and Fernando's crypto
algorithm as OPTIONAL. The problem with the RFC 3697
text is that it apparently encouraged lots of people
to design complex schemes for encoding semantics in the
flow label.

Given that we expect people to put flow labels into a
hash function of some kind, a 20-bit pseudo random number
seems like a better default than 1,2,3,... (depending on
the hash function, obviously).

Regards
   Brian

---

From: Thomas Narten <[email-masked]>
Date: Mon, 10 Jan 2011 17:31:26 -0500

> to design complex schemes for encoding semantics in the

I don't follow that last sentence. Can you expand?

> the hash function, obviously).

I want to challenge that up front.

For the example in your draft, MODULO(n), incrementing by one has
wonderful properties. Given that incrementing by 1 is about as simple
as it gets, that seems like a fine thing to do.

There may be security downsides by having such a predicable generator
at the source, but that is a different issue than making it hash well.

Thomas

---

From: Fred Baker <[email-masked]>
Date: Mon, 10 Jan 2011 14:50:02 -0800

> Have you looked at the security implications? Suppose that an attacker can predict the hash algorithm used by a router. This attacker could then pick "interesting" values of the flow ID, to get the…

Or he could hit a large number of flows, play with them to see which values achieve what he's trying to achieve, and simply use them - without knowledge of the game aforehand.

Unless, of course, the network is in control of the flow label. If the network is in control of the flow label, it is in a position to change that.

---

From: Brian E Carpenter <[email-masked]>
Date: Tue, 11 Jan 2011 11:51:36 +1300

Hi Thomas,

> I don't follow that last sentence. Can you expand?

See draft-hu-flow-label-cases, section 3, for several
examples.

> as it gets, that seems like a fine thing to do.

Yes, certainly, if the modulo is applied directly to the value. But
in practice it seems more likely that the value will be hashed up
with the traditional 5 tuple, and in that case having 20 variable bits
will do more to produce an even distribution of values than if the sources
only vary the low-order bits. (Assuming that most sources are
only generating a modest number of flows. If a source is generating
a few million flows an hour, this argument doesn't apply.)

> at the source, but that is a different issue than making it hash well.

Yes. Should we be using that argument more strongly in the draft?

---

From: Brian E Carpenter <[email-masked]>
Date: Tue, 11 Jan 2011 12:08:45 +1300

> Unless, of course, the network is in control of the flow label. If the network is in control of the flow label, it is in a position to change that.

I understood the WG to have reached a consensus that we still
want to declare the flow label immutable, except for allowing a
router to set it if the source host does not. The draft reflects
that consensus.

    Brian

---

From: Yong Lucy <[email-masked]>
Date: Mon, 10 Jan 2011 17:40:42 -0600

> than the network path load.

[LY] Statistical approach works well under the consumption that there are
thousands of flows and they have the similar rates. Today's Internet may
have the flows that only have few packets and the flows that have thousands
packets per second and last long. Hash does not work well under this
condition.

[LY] the server load balance and the network path load balance have
different criteria.

Lucy

 -------------------------------------------------------

---

From: Brian E Carpenter <[email-masked]>
Date: Tue, 11 Jan 2011 15:01:57 +1300

> packets per second and last long. Hash does not work well under this

In fact no solution works well for short flows and the problem isn't important
for long flows with few packets. So I think it's OK to discuss a solution
that works for long flows with many packets, since that covers most
of the load.

> [LY] the server load balance and the network path load balance have

Very true. It isn't clear to me that balancing the network load
without knowledge of the server load is a good idea.

     Brian

---

From: Shane Amante <[email-masked]>
Date: Mon, 10 Jan 2011 19:18:47 -0700

Thomas, All,

> as it gets, that seems like a fine thing to do.

Let's take a step back here for a moment and recognize a few things:
1)  Routers, (specifically, 1st-hop routers that would be replacing a zero flow-label with something non-zero), already implement a pseudorandom hash algorithm today (sometimes in HW), in order that they can determine an outgoing component-link for packets sent out/across LAG's and ECMP paths.  So, this draft is simply proposing to re-use an existing pseudorandom function already built-in to routers and simply encode that result into a flow-label.  
2)  For your proposal, above, of incrementing the flow-label by one to be successful, the device encoding the flow-label would have to track state of all flows in order to ensure that all packets belonging to the same flow got the same flow-label.  While this might be true, and easy, for hosts or stateful firewalls, this would absolutely not work for 1st-hop routers that are allowed to set a flow-label if they observe an incoming packet whose flow-label wasn't set by the host, (IOW, flow-label == 0).

So, I'm seeing a technical problem with your proposal (#2) and huge advantages for re-use of pseudorandom algorithms already implemented within devices in the network that are potentially responsible for writing a flow-label with as little state as possible, (#1).

-shane

---

From: Yong Lucy <[email-masked]>
Date: Tue, 11 Jan 2011 09:41:04 -0600

> that works for long flows with many packets, since that covers most

[LY] Hash works well for short flows. That was developed when Internet is
primarily used for data transport. As more and more video data on Internet,
traffic become mixed with long flows with many packets and short flow with
few packets. Hash no longer works well in this traffic pattern.

> without knowledge of the server load is a good idea.

[LY] Agree. However, today network performs load balance without considering
server load balance; server load performs load balance without considering
network load balance. Two operations are independent.

Lucy

---

From: Shane Amante <[email-masked]>
Date: Tue, 11 Jan 2011 10:10:49 -0700

Lucy, Brian,

> few packets. Hash no longer works well in this traffic pattern.

Let's be careful here and not cause a panic.  :-)

In reality, hash works quite well for the bulk of Video traffic currently being distributed over the public Internet, specifically in the form of streaming TV or movies such as Youtube, Hulu, Netflix, iTunes, etc. where individual streams/flows tend to be on the order of a few Mbps -- obviously because individual streams need to fit on "small" access circuits (relative to the size of Backbone links) to subscriber's homes that are primarily using either DSL or Cable (DOCSIS) -- at least from the PoV of here in North America.

It's probably better to say that a hash algorithm works well where individual, long-lived flows (regardless of traffic type) are a small-ish fraction of the physical BW of any individual component-link in a LAG or ECMP group.  It's when those long-lived flows are a substantial portion of component-link's physical BW that a hash algorithm is ineffective and you either need higher capacity component-links or more "creative" techniques.

>> without knowledge of the server load is a good idea.

Brian: It is from the perspective that it's stateless, which is a very desirable property when you're talking about Core/Edge devices with millions or billions of flows ...

-shane

---

From: Fred Baker <[email-masked]>
Date: Tue, 11 Jan 2011 09:29:00 -0800

> It's probably better to say that a hash algorithm works well where individual, long-lived flows (regardless of traffic type) are a small-ish fraction of the physical BW of any individual component-…

Statistics we're seeing suggest that long-lived video flows (video-on-demand, streaming media, netflix/youtube/etc) are becoming a fairly large subset of internet traffic. You may have seen Wired's article on it (http://www.wired.com/magazine/2010/08/ff_webrip/all/1) and the far-better-thought-through rebuttal (http://boingboing.net/2010/08/17/is-the-web-really-de.html).

---

From: Shane Amante <[email-masked]>
Date: Tue, 11 Jan 2011 11:14:23 -0700

Fred,

> Statistics we're seeing suggest that long-lived video flows (video-on-demand, streaming media, netflix/youtube/etc) are becoming a fairly large subset of internet traffic. You may have seen Wired's…

I have.  However, people need to put the [very poor] Wired article in context.  Specifically, there's a significant difference between the aggregate amount of all Video traffic **versus** the size (bandwidth) of individual Video streams that will appear in the core of the network.  IOW, as an operator, I don't have concerns transporting Terabits (and, more) of _aggregate_ Video traffic, so long as the _individual_ Video streams in that aggregate are "well distributed" amongst themselves and other traffic that would ultimately be output on a common set of component-links comprising a single LAG or ECMP group.  By that I mean: 
- each has a relatively unique 5-tuple (since that's the only thing I can use, today, from the IP header, today, as an input-key for a load-balancing hash algorithm), to ensure there is the low(est) probability that all Video flows will get put onto the same component-link in a LAG or ECMP path; and,
- the bandwidth of an individual Video stream is a small-ish fraction of the BW of a component-link comprising a LAG or ECMP path.  IOW, why should I care about a 5, 10 or 20 Mbps constant rate Internet [Video] flow on a 10 Gbps component-link, (you're talking about .2% [2-thousands] of the overall physical capacity of a component-link)?

What causes pain and/or worry to us operators is when someone launches a large *individual* "macro-flow"[1] at the network that start to represent a decent fraction of the overall capacity of a physical component-link underlying a LAG and/or ECMP path, (e.g.: and the following are only an *example*: 200 Mbps, 500 Mbps, 1 Gbps, etc. on a 10 Gbps link).  Unfortunately, due to the fact that load-hashing algorithms are stateless (and, thus, non-adaptive), that means that "well-behaved" microflows (think: casual Web surfing, e-mail, etc.) are still co-mingled with those large, fat-flows across all component-links in a common LAG/ECMP path *without* taking into account BW utilization of individual component-links.  So, there is a much higher probability (or, oftentimes, certainty) of congestion and packet loss causing pain to all users on the one (or, more) component-links with fat, macro-flows on them that I can't capacity plan for and I can't easily react to.

-shane

[1] Examples are: IPvX in IPvX tunneling, GRE, IPSec, "WAN acceleration" type products that are used for extremely fast large file xfers, etc.

---

From: Yong Lucy <[email-masked]>
Date: Tue, 11 Jan 2011 14:17:37 -0600

Shane and all,

> 
> What causes pain and/or worry to us operators is when someone launches a
> large *individual* "macro-flow"[1] at the network that start to represent
> a decent fraction of the overall capacity of a physical component-link
> underlying a LAG and/or ECMP path, (e.g.: and the following are only an
> *example*: 200 Mbps, 500 Mbps, 1 Gbps, etc. on a 10 Gbps link).
> Unfortunately, due to the fact that load-hashing algorithms are stateless
> (and, thus, non-adaptive), that means that "well-behaved" microflows
> (think: casual Web surfing, e-mail, etc.) are still co-mingled with those
> large, fat-flows across all component-links in a common LAG/ECMP path
> *without* taking into account BW utilization of individual
component-links.
> So, there is a much higher probability (or, oftentimes, certainty) of
> congestion and packet loss causing pain to all users on the one (or, more)
> component-links with fat, macro-flows on them that I can't capacity plan
> for and I can't easily react to.

[LY] Great analysis. As a result, it seems the necessary to differentiate
those large flows (decent fraction of the component link capacity) from
other "small" flows because there are few such large flows in the network
and hash can't do well on a small flow space nor on a large flow space that
mixed with huge number of small flows and a few large flows. 

Lucy

> 
> -shane
> 
> [1] Examples are: IPvX in IPvX tunneling, GRE, IPSec, "WAN acceleration"
> type products that are used for extremely fast large file xfers, etc.=

---

From: Brian E Carpenter <[email-masked]>
Date: Wed, 12 Jan 2011 10:04:38 +1300

On 2011-01-12 04:41, Yong Lucy wrote:
> [LY] Hash works well for short flows. 

Lucy, I wrote carelessly - really I was thinking about stateful solutions
involving a hash, that are simply not worth the overhead for short flows
("short" to me means maybe 5 or 10 packets at most. Yes, a stateless
solution can work for short flows, whether it's round-robin or hash
based.

For the rest, Fred and Shane have covered the discussion, and I don't
see that it affects the draft.

    Brian

---

From: Fred Baker <[email-masked]>
Date: Tue, 11 Jan 2011 18:05:54 -0800

> [1] Examples are: IPvX in IPvX tunneling, GRE, IPSec, "WAN acceleration" type products that are used for extremely fast large file xfers, etc.

Yes. And there are similar issues in data centers, where load balancing is also used but in a different way.

There is another way to make a video flow be a relatively large chunk of a link; go closer to the access. "why should I care about a 5/10/20 MBPS...on a 10 GBPS"? You shouldn't. But, how about a 20 MBPS data flow for each access customer when you have sized for an aggregate of 25 MBPS per customer? That can be quite a bit different. For the record, when we were developing our telepresence product, we had to look at the pacing of traffic coming out of the camera/codec, because we found that a 5 MBPS data flow with 10 MBPS peaks could momentarily swamp a 100 MBPS link. Obvious enough to me (hint: peak on a short timescale != average on a long timescale), but very counterintuitive to my colleagues.

There are ways to make stateless hashes change the way they hash. If you're using a CRC as a hash generator, for example, it starts with an initial value placed in a register. Change the initial value, and all the hashes change. If you find the distribution not to your liking, change the value, and see if you like that any better. The sad part is that there is no easy way to "calculate an initial value I will like"; you have to try them all, or at least occasionally try a different one.

Finding a predictable method tends to be about - as Ipsilon proposed a decade plus ago - identifying the important data flows and doing something intelligent with them, and running the rest statistically.

http://www.ietf.org/rfc/rfc2098.txt
2098 Toshiba's Router Architecture Extensions for ATM : Overview. Y.
     Katsube, K. Nagami, H. Esaki. February 1997. (Format: TXT=43622
     bytes) (Status: INFORMATIONAL)

http://www.ietf.org/rfc/rfc2129.txt
2129 Toshiba's Flow Attribute Notification Protocol (FANP)
     Specification. K. Nagami, Y. Katsube, Y. Shobatake, A. Mogi, S.
     Matsuzawa, T. Jinmei, H. Esaki. April 1997. (Format: TXT=41137 bytes)
     (Status: INFORMATIONAL)

---

From: Thomas Narten <[email-masked]>
Date: Mon, 17 Jan 2011 12:08:58 -0500

Christian Huitema <[email-masked]> writes:

> attacker could then pick "interesting" values of the flow ID, to get
> the flow of traffic directed to particular paths, or not. For

Thinking about this some more.

There are two cases to worry about. The first one concerns the
(currently mythical) case where a flow setup protocol has been used to
create state/reservations along a path for a particular Flow. An
attacker might want to target that precise flow in order to cause
problems for that one flow (e.g, exceed its flow spec). The attacker
would presumably need to determine the src/dst/flow label value of a
particular flow in order to exploit this. Since flow setup is
involved, presumably the Flow Label value can be choosen somewhat
carefully to make this harder for off-path attackers. This case is
presumably also not really a relevant to the current discussion.

The second case concerns a number of paths across which traffic is to
be split. An attacker might want to overload a particular path. One
way to do this is to guess the Flow Labels being used for ECMP. But it
seems like there is an even easier way. If there are N paths, whatever
hash is used will distribute over those N paths. So all an attacker
needs to do is generate src/dest/Flow IDs and probe the network to see
which paths are actually being used. And then generate lots of traffic
to target the particular path they are after. (Rereading the thread I
see now that Fred made this same point.)

The point being, an attacker doesn't have to guess the actual Flow
Labels that are being in use, but just come up with way to generate
traffic that ECMP maps onto the target path. That suggests that having
Flow Label values themselves be "pseudo random" doesn't buy a whole
lot.

Or am I missing something?

I'm a bit stuck on this point, because both of the current flow label
document continue to say flow labels should be generated SHOULD be
psuedo-random, and I'm not convinced this is necessary, required, or
buys us anything. What compelling argument am I missing?

Thomas

---

From: Christian Huitema <[email-masked]>
Date: Mon, 17 Jan 2011 19:27:14 +0000

Thomas Narten wrote:

> I'm a bit stuck on this point, because both of the current flow label document 
> continue to say flow labels should be generated SHOULD be pseudo-random, 
> and I'm not convinced this is necessary, required, or buys us anything. 
> What compelling argument am I missing?

I agree. The network routers should not trust that the flow label has any particular randomness properties, because misplaced trust would open a path for attacks. Having the randomness requirement in the spec would only encourage routers to make the wrong security assumptions.

-- Christian Huitema

---

From: Shane Amante <[email-masked]>
Date: Mon, 17 Jan 2011 12:55:53 -0700

Thomas,

On Jan 17, 2011, at 10:08 MST, Thomas Narten wrote:
[--snip--]
> see now that Fred made this same point.)

This type of attack is likely insignificant in the real-world, at least for links within the Backbone.  Let's keep in mind that a victim's traffic (assuming it's well-behaved) will already, automatically be spread across a large number of component-links in a ECMP/LAG group.  Thus, if an attacker were either patient enough or had the appropriate HW to generate the right traffic pattern congest a single link in that ECMP/LAG group, then it would only affect a, possibly small, percentage of the overall traffic toward a particular victim -- it depends on how many component-links are in the particular LAG/ECMP group.  Instead, it's much more straightforward for an attacker to [easily] acquire several hundred/thousand/etc. bots and congest the small-ish access circuit(s) that are closest to the victim/destination, (i.e.: from PE -> CE) ... or use application-level attacks on the servers, etc.  As you get closer to the victim/destination LAG/ECMP is less likely to be used, which is why it's an easier place to attack.

> buys us anything. What compelling argument am I missing?

Fernando Gont (and, Steve Blake) have been proposing using the flow-label as a security mechanisms for hosts to prevent off-path spoofing attacks.  However, to successfully implement/deploy this, you need the pseudo-random flow-labels:
   Therefore, the Flow Label should be obfuscated so that
   the chances of an off-path attacker of guessing the Flow Label of
   future flows are reduced.
http://tools.ietf.org/html/draft-gont-6man-flowlabel-security-01

So, why not take the opportunity to use the flow-label to reduce the attack surface of IPv6, (compared to v4)?

Does that help?

-shane

---

From: Steven Blake <[email-masked]>
Date: Mon, 17 Jan 2011 16:14:55 -0400

> Fernando Gont (and, Steve Blake) have been proposing using the
> flow-label as a security mechanisms for hosts to prevent off-path
> spoofing attacks.  However, to successfully implement/deploy this, 
> you
> need the pseudo-random flow-labels:
> So, why not take the opportunity to use the flow-label to reduce the
> attack surface of IPv6, (compared to v4)?

 I am not pushing the flow label nonce proposal anymore.

 I understand that there is a lot of deployed gear that uses CRC16 or 
 CRC32 to compute ECMP/LAG hashes.  To the extent that this gear can be 
 configured to use flow labels in the hash key (rather that 
 protocol/ports), I also understand that these CRC algorithms are not 
 great hash functions (i.e., they lack an avalanche effect), although I 
 haven't examined this myself.

 Setting the flow label using a non-repeating PRNG (*) makes it 
 (slightly?) more likely that one's traffic will experience a good load 
 split.  I can't think of a reason at the moment why this should be 
 mandatory, though.

 (*) This can be achieved using an array of maximum-sequence 20-bit 
 LFSRs, rather than an array of 20-bit counters as in Fernando's draft.

 Regards,

 // Steve

---

From: Brian E Carpenter <[email-masked]>
Date: Tue, 18 Jan 2011 10:02:50 +1300

> I agree. The network routers should not trust that the flow label has any particular randomness properties, because misplaced trust would open a path for attacks. Having the randomness requirement…

There are two, or possibly three, arguments for a "SHOULD" here:

1. The security argument, made in draft-gont-6man-flowlabel-security

Obviously downstream nodes must not rely on this, but that in itself
doesn't weaken the argument for pseudo-randomness. The draft says
"Forwarding nodes such as routers and load balancers MUST NOT
depend only on Flow Label values being randomly distributed."
I find Christian's counter-argument strange; there are many places
where foolish implementers can create security exposures.

2. The argument, that Thomas has disputed, that this provides better
input to a load balancing hash. I'll debate that on another thread
where Thomas has repeated his arguments.

3. The dubious argument that by recommending a *specific* method of
setting the flow label, we increase the chances that implementers will
actually do so. It's clear that the present recommendation is too
weak in that respect.

     Brian

---

From: Fernando Gont <[email-masked]>
Date: Fri, 21 Jan 2011 13:55:04 -0300

Hi, Thomas,

> I do not see a reason to require this.

Probably that could/should be rephrased as:

   1.  It is RECOMMENDED that source hosts support the flow label by
       setting the flow label field for all packets of a flow to the
       same value. Such value should not be easily predictable by an
       off-path attacker.

> Flow Labels selected in a psuedo random fashion.

Agreed. But predictable values have been found to have problems. See
e.g. the implications of the IPv4 identification field in
http://www.gont.com.ar/papers/InternetProtocol.pdf

> sequentially. 

Indeed, draft-gont-6man-flowlabel-security does select flow-labels
incrementally --- although with a scheme that makes it difficult for an
off-path attacker to guess te next flowlabel value.

Thanks!

Best regards,
-- 
Fernando Gont
e-mail: [email-masked] || [email-masked]
PGP Fingerprint: 7809 84F5 322E 45C7 F1C9 3945 96EE A9EF D076 FFF1

---

From: Bob Hinden <[email-masked]>
Date: Fri, 21 Jan 2011 09:20:33 -0800

Fernando,

>       same value. Such value should not be easily predictable by an

We could also add to this something like:  One way to achieve this is with a pseudo-random value.

Bob

---

From: Fernando Gont <[email-masked]>
Date: Fri, 21 Jan 2011 14:24:14 -0300

Hi, Bob,

On 21/01/2011 02:20 p.m., Bob Hinden wrote:

>>>> 1. It is RECOMMENDED that source hosts support the flow label
>>>> by setting the flow label field for all packets of a flow to
>>>> the same pseudo-random value.
>>> 

+1

-- Although if the flowlabels are expected to be unique for each flow
(as they currently are), then random numbers have a chance for
collisions, and the approach proposed in draft-gont-flowlabel-security
is better.

Thanks!

Best regards,

---

From: Brian E Carpenter <[email-masked]>
Date: Sat, 22 Jan 2011 08:25:46 +1300

> collisions, and the approach proposed in draft-gont-flowlabel-security

We seem to have agreed that the primary purpose of the flow label is
to facilitate load balancing, which is a statistical process. For that
to work, while minimising reordering, it's required that all packets
of the same flow have the same label (as is clear in 3697 and will be
clear in 3697bis). However, it is NOT required that flow labels
are strictly unique - a birthday-paradox rate of duplicate flow labels
really won't matter. I suggest (and this is a new suggestion that's
been in my mind for a few days) that the uniqueness requirement can and
should be relaxed to 'unique with high probability'.

     Brian

---

From: Thomas Narten <[email-masked]>
Date: Fri, 21 Jan 2011 14:49:08 -0500

> However, it is NOT required that flow labels are strictly unique - a
> birthday-paradox rate of duplicate flow labels really won't
> matter. I suggest (and this is a new suggestion that's been in my
> mind for a few days) that the uniqueness requirement can and should
> be relaxed to 'unique with high probability'.

Right. the way I've been thinking about that is that traditional
Flows, ala NSIS/RSVP where a flow setup protocol is in use, does still
require uniqueness.

But other uses of the Flow Label outside of that do not have that
requirement.

So, if you do traditional flows, you have to be sure to generate Flow
Labels carefully.  The default usage outside of signaling does not
have the same requirement.

Thomas

---

From: Fernando Gont <[email-masked]>
Date: Fri, 21 Jan 2011 19:05:43 -0300

> have the same requirement.

Having two different FlowLabel generation algorithms does not sound like
a good approach to me (not that you're proposing that, though) -- in
particular, when we'd have to work on an API for apps to select the
proper one.

IMHO, pick an algorithm that is suitable for all cases, and that's it.

Thanks,

---

From: Thomas Narten <[email-masked]>
Date: Fri, 21 Jan 2011 17:21:44 -0500

> particular, when we'd have to work on an API for apps to select the

You misunderstand me. For flows where the application wants special
service, you can afford to have a more sophisticated algorithm.

For the vast majority of applications, they won't set the flow label
and will leave it to the OS to use heuristics (like each socket gets a
different value). That is the case we are trying to make work with
load balancers. These can use a much simpler default algorithm. And we
need to allow for *very* simple devices, like sensor devices, etc.

> IMHO, pick an algorithm that is suitable for all cases, and that's

I think it's fine to have a simple default. What I'm arguing against
is making the default case more complicated than it really needs to
be.

We can have a more sophisticated algorithm in those cases where it
actually matters, since those will not be the common case (if indeed,
we ever develop standards in this area.)

Thomas

---

From: Fred Baker <[email-masked]>
Date: Fri, 21 Jan 2011 15:07:22 -0800

On Jan 21, 2011, at 11:25 AM, Brian E Carpenter wrote:

> to facilitate load balancing, which is a statistical process. 

except when it is not a statistical process.

---

From: Brian E Carpenter <[email-masked]>
Date: Sat, 22 Jan 2011 13:29:37 +1300

> except when it is not a statistical process. 

Yes, I should have written,

 We seem to have agreed that the primary purpose of the flow label is
 to facilitate load balancing, which is commonly implemented as a
 statistical process.

At least, I think that's where the conversation has taken us.

    Brian

---

From: Bob Hinden <[email-masked]>
Date: Fri, 21 Jan 2011 16:49:02 -0800

> At least, I think that's where the conversation has taken us.

That's my view as well.

Bob