Subject: Re: [OPSAWG] I-D Action: draft-krishnan-opsawg-large-flow-load-balancing-02.txt

From: Brian E Carpenter <[email-masked]>
Date: Sat, 12 Jan 2013 16:40:12 +0000

Hi,

My comments are on the discussion of flow IDs and hashing. I'm not
commenting at all on the overall proposal, because I can't judge
whether the problem is real or the solution is practical.

> A large space of the flow identifications, i.e. finer	
> granularity of the flows, conducts more random in spreading the flows	
> over a set of component links. 

That isn't accurate. The requirement is an ID space in which the IDs
belong to a uniform distribution. Technically speaking, if you have two
links, a one-bit flow ID is sufficient, as long as the values 0 and 1 are
equally likely to appear.

Therefore, the practical issue is not the size of the ID space but the
quality of the hash function used to generate the ID of each flow.
However, whatever the initial ID space, the final hash has to be down
to 0..N if you have N+1 alternative paths.

I think the reason that your model needs a larger ID space is to
reduce the probability of two flows colliding by chance in the ID space.
That would defeat your wish to separate out large flows.

> The advantages of hashing based load	
> distribution are the preservation of the packet sequence in a flow	
> and the real time distribution with the stateless of individual	
> flows. If the traffic flows randomly spread in the flow	
> identification space, the flow rates are much smaller compared to the	
> link capacity, 

That sounds like magic. I don't think you mean that at all.

> and the rate differences are not dramatic, 

Do you mean that the total traffic rate is more fairly distributed
across the links? In any case, "dramatic" isn't an engineering term.

> the hashing	
> algorithm works very well in general.

How can you say that without specifying a particular algorithm? Also,
"very well in general" isn't an engineering term either.

> There may be some false positives due to multiple other flows	
> masquerading as a large flow; the amount of false positives is	
> reduced by parallel hashing using different hash functions

To give you some data, with a 20 bit ID space, the FNV1a-32 hash
algorithm gives at most 5% collisions, based on IPv6 headers in real
packet traces.
[https://researchspace.auckland.ac.nz/handle/2292/13240]

I wonder whether the overhead of running several hashes in parallel
is justified by this collision rate?

Regards
   Brian Carpenter

---

From: ramki Krishnan <[email-masked]>
Date: Sat, 12 Jan 2013 21:14:55 -0800

Hi Brian,

Thanks a lot for your comments. Please find answers to some of your comments. We will respond to your other comments shortly.

> reduced by parallel hashing using different hash functions

Brian:

To give you some data, with a 20 bit ID space, the FNV1a-32 hash algorithm gives at most 5% collisions, based on IPv6 headers in real packet traces.  [https://researchspace.auckland.ac.nz/handle/2292/13240]. I wonder whether the overhead of running several hashes in parallel is justified by this collision rate?

Ram:

The need for multiple hashes is specific to the suggested algorithm on automatic hardware identification - this algorithm is similar to a bloom filter which uses multiple hash functions.

"On packet arrival, a new flow is looked up in parallel in all the hash tables and the corresponding counter is incremented. If the counter exceeds a programmed threshold in a given time interval in all the hash table entries, a candidate large flow is learnt and programmed in a hardware table resource like TCAM.

For a short-lived flow to masquerade as a long-lived lived flow, it needs to match all the hash table entries which is a joint probability event - thus, the amount of false positives due to short-lived flows is reduced.

Thanks,

ram

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Brian E Carpenter
Sent: Saturday, January 12, 2013 8:40 AM
To: [email-masked]
Cc: [email-masked]
Subject: Re: [OPSAWG] I-D Action: draft-krishnan-opsawg-large-flow-load-balancing-02.txt

Hi,

My comments are on the discussion of flow IDs and hashing. I'm not commenting at all on the overall proposal, because I can't judge whether the problem is real or the solution is practical.

> over a set of component links.

That isn't accurate. The requirement is an ID space in which the IDs belong to a uniform distribution. Technically speaking, if you have two links, a one-bit flow ID is sufficient, as long as the values 0 and 1 are equally likely to appear.

Therefore, the practical issue is not the size of the ID space but the quality of the hash function used to generate the ID of each flow.

However, whatever the initial ID space, the final hash has to be down to 0..N if you have N+1 alternative paths.

I think the reason that your model needs a larger ID space is to reduce the probability of two flows colliding by chance in the ID space.

> and the rate differences are not dramatic,

Do you mean that the total traffic rate is more fairly distributed across the links? In any case, "dramatic" isn't an engineering term.

> algorithm works very well in general.

How can you say that without specifying a particular algorithm? Also, "very well in general" isn't an engineering term either.

> reduced by parallel hashing using different hash functions

To give you some data, with a 20 bit ID space, the FNV1a-32 hash algorithm gives at most 5% collisions, based on IPv6 headers in real packet traces.

I wonder whether the overhead of running several hashes in parallel is justified by this collision rate?

Regards

   Brian Carpenter

_______________________________________________

OPSAWG mailing list

[email-masked]<mailto:[email-masked]>

https://www.ietf.org/mailman/listinfo/opsawg

---

From: Brian E Carpenter <[email-masked]>
Date: Sun, 13 Jan 2013 08:05:58 +0000

Ram,

> The need for multiple hashes is specific to the suggested algorithm on automatic hardware identification - this algorithm is similar to a bloom filter which uses multiple hash functions.

I think didn't explain my point sufficiently. I understand why you suggest using several
hashes. But this is statistical load balancing we are talking about. If a few % of the
time, you mistakenly treat several medium flows as one large flow, and therefore
rebalance them as a single unit, so what? You will still balance the traffic reasonably
well.

    Brian

---

From: ramki Krishnan <[email-masked]>
Date: Mon, 14 Jan 2013 09:48:40 -0800

Hi Brian,

>>I think didn't explain my point sufficiently. I understand why you suggest using several hashes. But this is statistical load balancing we are talking >>about. If a few % of the time, you mistakenly treat several medium flows as one large flow, and therefore rebalance them as a single unit, so what? >>You will still balance the traffic reasonably well.

Each of the flows is eventually learnt/programmed in a flow table (hardware table resource where the flow is finally committed); there is never a case of bundling multiple flows. More details below

1)    Scalable detection of long-lived large flows

a.    The goal is to keep the size of the flow table (hardware table resource where the long-lived large flow is finally committed) bounded and the processing requirements (CPU utilization) for flow learning bounded.

b.    For satisfying the above goal, several hashes helps.

2)    Scalable load-balancing of long-lived large flows

a.    The goal is to have a scalable load balancing solution which produces meaningful results while keeping the processing requirements (CPU utilization) for load-balancing bounded.

b.    For satisfying the above goal, it is not worthwhile to load-balance medium/small flows.

Thanks,

ram

-----Original Message-----
From: Brian E Carpenter [mailto:[email-masked]]
Sent: Sunday, January 13, 2013 12:06 AM
To: ramki Krishnan
Cc: [email-masked]; [email-masked]
Subject: Re: [OPSAWG] I-D Action: draft-krishnan-opsawg-large-flow-load-balancing-02.txt

Ram,

> The need for multiple hashes is specific to the suggested algorithm on automatic hardware identification - this algorithm is similar to a bloom filter which uses multiple hash functions.

I think didn't explain my point sufficiently. I understand why you suggest using several hashes. But this is statistical load balancing we are talking about. If a few % of the time, you mistakenly treat several medium flows as one large flow, and therefore rebalance them as a single unit, so what? You will still balance the traffic reasonably well.

    Brian

> From: [email-masked]<mailto:[email-masked]> [mailto:[email-masked]] On

> Behalf Of Brian E Carpenter

> To: [email-masked]<mailto:[email-masked]>

> Cc: [email-masked]<mailto:[email-masked]>

> Subject: Re: [OPSAWG] I-D Action:

> draft-krishnan-opsawg-large-flow-load-balancing-02.txt

> [email-masked]<mailto:[email-masked]<mailto:[email-masked]%3cmailto:[email-masked]>>

---

From: Lucy yong <[email-masked]>
Date: Mon, 14 Jan 2013 18:00:17 +0000

Hi Brian,

I think we are not discussing different things. Please see inline.

> Sent: Saturday, January 12, 2013 10:40 AM
> Subject: Re: I-D Action: draft-krishnan-opsawg-large-flow-load-
> balancing-02.txt
> 
> Hi,
> 
[Lucy] This is not requirement for the ID space. It is to say that using 5 tuple or 3 tuple to define a flow results a very large flow ID space. This flow definition is typically used in hashing based load balance today. This has nothing to do with how many links. We will refine the text to make it clear. 

> to 0..N if you have N+1 alternative paths.
[Lucy] The draft does not address using hashing to generate the flow ID at all. We are across each other here. You may refer some different applications.

Regards,
Lucy

---

From: Brian E Carpenter <[email-masked]>
Date: Tue, 15 Jan 2013 08:05:47 +0000

> I think we are not discussing different things. Please see inline.

I think the problem is that the draft doesn't explain the fundamental
model very well. I fully agree with your comments below (and these
aspects are discussed in RFC 6438).

   Brian

---

From: Brian E Carpenter <[email-masked]>
Date: Tue, 15 Jan 2013 08:12:42 +0000

Ram,

I understand everything you say below. But you aren't commenting on my
main point: why is it worth the *extra* cost of running several hashes
in parallel to exclude a *small* fraction of mis-identified large flows?
To me, that is not a useful engineering trade-off.

Regards
   Brian

---

From: Lucy yong <[email-masked]>
Date: Tue, 15 Jan 2013 17:46:52 +0000

Brian,

I mean to say that we are not discussing the same thing. It seems that you capture my error and response properly. We will make better explanation in next version. 

The fundamental model for the load balance is to hash on some fields in the packets. Hashing mechanism ensures the application or client flows traversing on the same path and a node does not need to track the mapping between flow and path, i.e. flow stateless. 

Thanks,
Lucy

> Sent: Tuesday, January 15, 2013 2:06 AM
> To: Lucy yong
> >> links, a one-bit flow ID is sufficient, as long as the values 0 and
> 1
> >> are
> > [Lucy] This is not requirement for the ID space. It is to say that
> using 5 tuple or 3 tuple to define a flow results a very large flow ID
> space. This flow definition is typically used in hashing based load
> balance today. This has nothing to do with how many links. We will
> refine the text to make it clear.
> >
> > [Lucy] The draft does not address using hashing to generate the flow
> ID at all. We are across each other here. You may refer some different
> applications.
> >
> > Regards,
> > Lucy

---

From: ramki Krishnan <[email-masked]>
Date: Tue, 15 Jan 2013 10:17:43 -0800

Hi Brian,

A potential long-lived large flow is declared if it exceeds a pre-programmed threshold in *all the matching hash table entries*.

Through the use of multiple hashes, the benefit of avoiding false positives is a much more than a small fraction, see an approximate sample probabilistic calculation below.

Let us assume the number of hash stages is m (4). Let us assume the probability of a short-lived flow matching a single hash table entry is .25. For a short-lived flow to be declared a long-lived large flow, it needs to match the same hash table entries as the long-lived large flow. The approximate probability of this event is (.25)^m = (.25)^4 = .003

Thanks,

ramki

-----Original Message-----
From: Brian E Carpenter [mailto:[email-masked]]
Sent: Tuesday, January 15, 2013 12:13 AM
To: ramki Krishnan
Cc: [email-masked]; [email-masked]
Subject: Re: [OPSAWG] I-D Action: draft-krishnan-opsawg-large-flow-load-balancing-02.txt

Ram,

I understand everything you say below. But you aren't commenting on my main point: why is it worth the *extra* cost of running several hashes in parallel to exclude a *small* fraction of mis-identified large flows?

Regards

   Brian

> Each of the flows is eventually learnt/programmed in a flow table

> (hardware table resource where the flow is finally committed); there

> is never a case of bundling multiple flows. More details below

> Cc: [email-masked]<mailto:[email-masked]>;

> [email-masked]<mailto:[email-masked]>

>> From: [email-masked]<mailto:[email-masked]<mailto:[email-masked]%3cmailto:[email-masked]>>

>> [mailto:[email-masked]] On

>> To:

>> [email-masked]<mailto<mailto:[email-masked]%3cmailto>

>> :[email-masked]>

>> Cc: [email-masked]<mailto:[email-masked]<mailto:[email-masked]%3cmailto:[email-masked]>>

>>> granularity of the flows, conducts more random in spreading the

>>> flows

>>> identification space, the flow rates are much smaller compared to

>>> the

>> [email-masked]<mailto:[email-masked]<mailto:[email-masked]%3cmailt<mailto:[email-masked]%3cmailto:[email-masked]%3cmailto:[email-masked]%3cmailt>

>> o:[email-masked]>>

---

From: Brian E Carpenter <[email-masked]>
Date: Wed, 16 Jan 2013 07:55:28 +0000

Again, I am not challenging your logic. I am challenging your statistics.

"Let us assume the probability of a short-lived flow matching a single hash table entry is .25"

That would be a very poor hash function. As I said, FNV gave me a worst-case
result close 0.02 (5%) with real data.

Regards
   Brian

---

From: Melinda Shore <[email-masked]>
Date: Tue, 15 Jan 2013 23:02:01 -0900

> That would be a very poor hash function. 

That would be a disturbingly bad hash function.  But let me ask this:
do you think the model would be workable with a better hash function?

Melinda

---

From: Brian E Carpenter <[email-masked]>
Date: Wed, 16 Jan 2013 08:17:57 +0000

> do you think the model would be workable with a better hash function?

The model works. I just don't see the point of running several inferior
hash functions instead of one good one.

   Brian

---

From: ramki Krishnan <[email-masked]>
Date: Wed, 16 Jan 2013 10:25:45 -0800

Hi Brian,

You are missing the spirit of the proposed multiple hashing scheme in terms of the hash table storage scalability it can offer - this is independent of the quality of the hash functions. Scalability is key - for e.g. there could be millions of flows out of which only a small percentage is long-lived large flows which you would like to learn.

With a single hash, your hash table size would be proportionate to the total number of flows to minimize false positives; with multiple hashes this could be reduced to a number proportional to the number of long-lived large flows - the exact number would depend on the use cases and traffic patterns.

As I mentioned before, this scheme is similar to a bloom filter (which uses multiple hash functions to substantially reduce the amount of storage) - please see below
http://en.wikipedia.org/wiki/Bloom_filter

I will also add some these details to an Appendix section in the draft. If needed, I would be glad to have a conference call to discuss further on this topic.

Thanks,
ramki

-----Original Message-----
From: Brian E Carpenter [mailto:[email-masked]] 
Sent: Wednesday, January 16, 2013 12:18 AM
To: Melinda Shore
Cc: ramki Krishnan; [email-masked]; [email-masked]
Subject: Re: [OPSAWG] I-D Action: draft-krishnan-opsawg-large-flow-load-balancing-02.txt

> do you think the model would be workable with a better hash function?

The model works. I just don't see the point of running several inferior hash functions instead of one good one.

   Brian

---

From: Brian E Carpenter <[email-masked]>
Date: Fri, 25 Jan 2013 14:16:27 +0000

> hash functions instead of one good one.

Ram has convinced me off line that the algorithm for large flow recognition
suggested in the draft does make sense. I hope the next version will make
this clearer.

    Brian