Subject: RE: refocusing: what about the flow label?

From: [email-masked]
Date: Fri, 7 Sep 2001 10:57:47 +0300

Christian,

While you intended to stay outside of the different QoS schemes, you still
wanted to cover the intserv/RSVP use of the flow label. Some clarifying
questions:

Assuming that you proposed intserv to use the label type basic: With the
label type basic and a non-null label value, are routers supposed to do what
you propose regardless of the presence of intserv state? I.e. to nail down
the path even if intserv is not used?

Could routers not interested in QoS classification based on the flow label
at all (e.g. diffserv interior routers) safely use just the 16 bit label
value for path distribution (ignoring the label type)?

With the current flow label semantics the routers can avoid doing intserv
state lookup if the flow label is null. If the flow label is used for path
distribution, the router will be searching for the intserv state for all the
packets (assuming the router does intserv at all). So from this
point-of-view it might be better to designate a separate label type for
intserv?

Or maybe intserv should be able to use whatever label type it wishes. Some
other type could allow for example rewrite at the intserv domain egress,
allowing the flow label to be mapped a value meaningful for some other
QoS/forwarding domain. (The value itself could be either carried in RSVP or
decided by the SLA between the intserv domain egress and the next domain).

What I'm aiming at is to see if a classifying router (intserv, diffserv, or
other) could be ignorant of the different flow label types when doing the
lookup based on the 3-tuple of the source address, destination address and
the 20 bit flow label. What state is then found based on the lookup would
tell the router what to do with the packet (which flow it belongs to, how to
police it, queue it, possibly remark DSCP and/or flow label, which interface
to use for output, etc.). In this scenario all the difference of the
different label types would be in the control plane (i.e. population of the
state found by the lookup engine). The silicon doing the classification
would remain the same regardless of the label type.

Or will the definition of the label type result in specialized silicon for
the different type values?

	Jarno

Christian Huitema wrote:
> 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]
> --------------------------------------------------------------------
> 
--------------------------------------------------------------------
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: "Hesham Soliman (ERA)" <[email-masked]>
Date: Fri, 7 Sep 2001 12:26:04 +0200

After observing the discussions for some time I'd like 
	to add my 2 cents on this.

	I appreciate Christian's efforts to achieve some concensus 
	on this issue, but I'd like to add to Jarno's comments below. 

	What are we doing by allowing multiple uses for the flow 
	label:

	- Perhaps resolving the "conflict" of opinions and getting some concencus
	- Creating some conflict in the network, between what the user wants / needs
	  and the way the network and business models are influencing flow 
	  treatment. How do we solve that ?  Negotiation between the host and 
	  network ? compromising one of the two (probably the host/user) ? 
	- We're opening the door for 15 possible uses of the flow label. 
	  who knows what will happen there !

	Are we happy with ending up in situations where the user has to choose 
	between 2 orthogonal issues like QoS and privacy (just an example) ??
	If we are then a split maybe possible, but personally I don't understand 
	why I should make a choice like that. 

	At the same time I also understand and appreciate the need for satisfying 
	the requirements of ISPs and router vendors. It's a matter of deciding 
	how much should be compromised. 

	Regards,
	Hesham

> > IPv6 specification. I propose the following compromise:> 
> >

---

From: "Christian Huitema" <[email-masked]>
Date: Fri, 7 Sep 2001 08:38:24 -0700

>  > 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.
> 
>    Associative memory is your friend :-)

In fact, one of the points that were made clear in the debate is that
the router manufacturers will never "just trust the host", i.e. just
trust that the "flow label" is sufficiently random and sufficiently
unique that they could use it without looking at the addresses. Then,
even if the flow was unique, we should note that even 20 bits would be
two small to be practical: the birthday paradox would kick in as soon as
the router processes 1,024 flows, which is not a very large number; you
would need some kind of tie-breaking logic, which means that you would
have at a minimum to process the source address. So, it is much safer to
assume that the primary classification will be based on the address
pair, and that the label is just a differentiator for packets that carry
the same address pair and require specific treatment; Mike points out
one possible solution; there are certainly others; hashing 256 bits of
source-destination should not require an inordinate number of gates in a
VLSI.

-- Christian Huitema

---

From: "Kastenholz, Frank" <[email-masked]>
Date: Mon, 10 Sep 2001 14:14:04 -0400

Christian,

It's not the gates to calculate the hash key that's the issue.
The problem is that hashing has a whole pile of memory
access issues surrounding the possibility of collisions.

First, it requires keeping a linked-list (or the like) of
"flow descriptors" in the memory. This list has to be
readable by the ASIC, but it also is written by the CPU
as new flows are added and old ones deleted. This leads to
the the classic multiple-accessor problems. Locking and
write-snooping and so on are all doable -- but they add
complexity that is very hard to verify and leads to
less-robust designs.

Second, since we can not know how many different flows
will map to a given hash bucket. This means that the
number of memory-accesses-per-packet is indeterminate.
This is bad -- the memory system can not be well designed,
so the packet rate can not be determined (which means that
buffer sizes can not be determined, system performance
can not be characterized, and so on)

Frank Kastenholz