Subject: refocusing: what about the flow label?

From: "Christian Huitema" <[email-masked]>
Date: Thu, 6 Sep 2001 15:34:14 -0700

I hope that after three weeks of exchanges, everybody is convinced that
we will not get any consensus on whether the best handling of QoS is
diffserv, intserv, or maybe no QoS at all. Let's try to be practical. We
have a simple problem to solve, the definition of the flow label in the
IPv6 specification. I propose the following compromise:

The flow label is comprised of 20 bits, divided between a four bit label
type and a 16 bit label value. IPv6 sources may set the flow label type
and the flow label value to label sequences of packets for which they
request special handling by the IPv6 routers, such as non-default
quality of service or "real-time" service; the label type defines how
the label value shall be used in the production of these services.
Label types may be defined in IETF standards and registered with the
IANA. This specification (i.e. IPv6) defines only one label type, the
basic label, whose value in binary is 0000. Sources that do not require
any specific service should set the label type to the basic label and
the label value to a null value.

When the label type is the basic label and the label value to a non null
value, IPv6 routers are expected to treat identically all packets that
carry the same source address, destination address and flow label. For
example, when traffic is load balanced along several alternate paths,
these packets should all sent on a single path; when classification is
performed for the purpose of quality of service, these packets should
all be classified in the same class. If the label type is set to the
basic type, IPv6 routers SHOULD NOT rewrite or alter the flow label
value.

Processing of the flow label, and possibly rewriting of the label value,
is specified in the IETF standard defining the label type. When a router
encounters a packet with an unknown flow label type, it should treat the
packet as if the label type was the basic value and the label value was
the null value. Routers SHOULD NOT rewrite or alter the flow label value
if the flow label type is unknown.

I believe it captures most of our discussions: we get a basic label that
is roughly equivalent to the label currently assumed by RSVP/Intserv; we
get reserved bits for the future generations; and we get an extension
mechanism that can possibly used by Diffserv, charge to them to describe
exactly how they intend to use it.

-- Christian Huitema

--------------------------------------------------------------------
IETF IPng Working Group Mailing List
IPng Home Page:                      http://playground.sun.com/ipng
FTP archive:                      ftp://playground.sun.com/pub/ipng
Direct all administrative requests to [email-masked]
--------------------------------------------------------------------

---

From: "Tony Hain" <[email-masked]>
Date: Thu, 6 Sep 2001 16:44:10 -0700

I can live with this.

> -----Original Message-----
> From: [email-masked]
> [mailto:[email-masked]]On Behalf Of Christian Huitema
> Sent: Thursday, September 06, 2001 3:34 PM
> To: Brian E Carpenter; Michael Thomas
> Cc: ipng
> Subject: refocusing: what about the flow label?
> 
>

---

From: Robert Elz <[email-masked]>
Date: Fri, 07 Sep 2001 17:59:11 +0700

Date:        Thu, 6 Sep 2001 15:34:14 -0700
    From:        "Christian Huitema" <[email-masked]>
    Message-ID:  <[email-masked]>

  | Let's try to be practical. We
  | have a simple problem to solve, the definition of the flow label in the
  | IPv6 specification.

Yes, good.

  | I propose the following compromise:

Unfortunately ...

  | I believe it captures most of our discussions: we get a basic label that
  | is roughly equivalent to the label currently assumed by RSVP/Intserv;

Roughly yes, but very roughly.  The flow label used to be 28 bits (all
but the version in the first word).  It is already down to 20 bits.
Now 4 more bits are to be removed and used as a label type field for label
types that we have no idea will ever be required?

That seems wrong to me.   With a 20 bit field, and a PRNG value in the
field, then there's room for a million different flows, all passing through
a router, and all being uniquely matched by just the flow label (with
address verification later).  My guess is that a million is already too
small, but it is also most probably not so far away from what's needed
as to be unusable (to use the million we'd need rather more flows than
that, because we know we'll get collisions, which is what saves such a
small number).

Your proposal reduces that to 64K flows.   That I know is way too small.

If we revert the flow label field back to being strictly a flow identifier
set by the source host to identify its flows, then we get a nice clean
definition that can be used by anyone and everyone.

That's what I'd like to see happen.

kre

---

From: Michael Thomas <[email-masked]>
Date: Fri, 7 Sep 2001 04:20:27 -0700 (PDT)

> Your proposal reduces that to 64K flows.   That I know is way too small.

   Er, the flow key is src/dst/flowlabel, right? That means it's
   64k per host pair which seems like plenty.

       Mike

---

From: Robert Elz <[email-masked]>
Date: Fri, 07 Sep 2001 19:38:18 +0700

Date:        Fri, 7 Sep 2001 04:20:27 -0700 (PDT)
    From:        Michael Thomas <[email-masked]>
    Message-ID:  <[email-masked]>

  |    Er, the flow key is src/dst/flowlabel, right? That means it's
  |    64k per host pair which seems like plenty.

Sure, as far as identifying the flow is concerned.  I guess I was thinking
more of a usage model .. that is, src/dst/flowlabel is 272 bits (16 bit
label), that's a hell of a huge database lookup key - to actually be used,
(as a hash table lookup key for example) it needs to be reduced to some
reasonable size.

Doing that the "normal way" (value modulo some prime) seems like it would be
a much too expensive operation to contemplate.   Doing it by calculating some
kind of CRC of the 272 bits, then using however many bits of that would be
better, but still not blindingly cheap.

What's left is the "use N of the M bits, ignore the rest" (where "ignore"
doesn't mean we don't compare them with the result of the has lookup).

If we do that, then which N?   Clearly if the flow label is a PRNG, those
bits, or as many of them as are needed, would be a good choice.  If there
are insufficient of those bits (and I suspect 16 isn't enough) then more
bits are needed.   Some kind of guessing game could be done with picking
extra bits out of the addresses (xoring the two, ...) but those bits, while
often seemingly random, aren't - and they're clearly not going to be as good
as having more PRNG bits would be.

That's what I was getting at.

kre

---

From: Michael Thomas <[email-masked]>
Date: Fri, 7 Sep 2001 08:12:40 -0700 (PDT)

> (as a hash table lookup key for example) it needs to be reduced to some

   Considering that the normal 5 tuple is 288 bits,
   I think the size of the flow key is already factored
   in with the rest of the protocol. Admittedly this
   causes a lot of hardware designers waking apnea,
   but having another wide key to deal with isn't
   nearly as bad as having to deal with the first.

 > better, but still not blindingly cheap.

   Associative memory is your friend :-)

		      Mike

---

From: stanislav shalunov <[email-masked]>
Date: 07 Sep 2001 11:30:09 -0400

Robert Elz <[email-masked]> writes:

> With a 20 bit field, and a PRNG value in the field, then there's
> room for a million different flows, all passing through a router,
> and all being uniquely matched by just the flow label (with address
> verification later).

I'm not sure what do you mean by your parenthetical comment.
If you are to match on source and destination later, you could as well
include them in the key.  They are either part of the key or not,
"order" of matching bits in the key isn't the issue (you probably want
to hash the whole key anyway).

With 20 bits PRN as flow label, collisions will start occuring after
roughly 1000 flows.  That's obviously way too low a number.  If you
want to be able to identify flows by their labels you'd need many more
bits for the label.

What's the point, though?  Why is matching on some bits (flow label)
preferable to matching on other bits (addresses)?  Is your concern to
have a contiguous block of bits?  (That shouldn't matter in ASICs, I
suppose.)

-- 
Stanislav Shalunov		http://www.internet2.edu/~shalunov/

"Nuclear war can ruin your whole compile."          -- Karl Lehenbauer

---

From: Francis Dupont <[email-masked]>
Date: Fri, 07 Sep 2001 20:11:12 +0200

In your previous mail you wrote:

   If the label type is set to the basic type, IPv6 routers SHOULD NOT
   rewrite or alter the flow label value.
   
=> even if the source is the best place to put a non-zero/non-default
value I'd like to enable one of the first routers to set the flow label
on the behalf of a dumb source. (PS: to change to basic type and null
value is not enough because we need to catch the "on the behalf of the
source" too).

Regards

[email-masked]

---

From: Michael Thomas <[email-masked]>
Date: Fri, 7 Sep 2001 11:25:59 -0700 (PDT)

> value is not enough because we need to catch the "on the behalf of the

   Slippery slope! Slippery slope!

   Most of the lossage floating around here is due to
   the network trying to be intelligent for dumb hosts.
 
   Long live the dumb network!

	Mike

---

From: Brian E Carpenter <[email-masked]>
Date: Tue, 11 Sep 2001 14:40:36 -0500

>    Long live the dumb network!

I agree. We were actually *forced* into allowing the network to
rewrite the DSCP in the diffserv case, because of having to deal
with a non-TOS-aware IPv4 legacy. And as Francis has so eloquently
stated, having the network guess the correct value is not a clean
solution - it's just the only one we have.

If we can use the flow label at all, IMHO we should *not* cater for 
a non-flow-label-aware IPv6 legacy!

     Brian