Subject: mechanisms for managing the flow ID field in IPv6

From: Craig Partridge <[email-masked]>
Date: Tue, 29 Nov 94 09:12:15 -0800

Hi folks:

    Attached is a draft of an RFC that I propose to send to the RFC editor
in two weeks.  It summarizes recent discussions in the End-to-End Research
Group about how to manage the Flow ID field and has some suggestions for
refining the language in the IPv6 specificiation.  I'm still waiting for
a few comments to filter back, but I've gotten several comments already
and think this is ready for wider circulation.  Comments are welcomed.

    I apologize to those of you who get this message three or four times -
I'm trying to hit the more important interested lists, namely the E2E list,
the IPNG list (since this involves the IPNG spec), the Flows list (since
this is a flows issue) and the INT SERV WG (since I propose to discuss
this document at the INT SERV WG meeting next week).

Craig

***************************************************************************

End-To-End Research Group                                   C. Partridge
Request for Comments: DRAFT                 BBN Systems and Technologies
                                                           December 1994

                    Using the Flow ID Field in IPv6

Status of this Memo

   At its most recent meeting, the End-to-End Research Group had a
   discussion about how the Flow ID field in IPv6 should be used.  This
   memo attempts to distill that discussion into a set of suggestions
   and still unresolved issues that can be used as an input into the
   IPv6 process.  Distribution of this memo is unlimited.

Brief Description of the Flow ID

   The current draft of the IPv6 specification states that every IPv6
   header contains a 28-bit Flow Label, which is composed of a 4-bit
   traffic class field followed by a 24-bit Flow ID field.

   The traffic class is a priority field and can be redefined by the
   flow.

   The Flow ID is a pseudo-random number between 1 and FFFFFF (hex) that
   is unique when combined with the source address.  The zero Flow ID is
   reserved to say that no Flow ID is being used.  The specification
   requires that a source must not reuse a Flow ID value until all state
   information for the previous use of the Flow ID has been flushed from
   all routers in the internet.

   The specification further requires that all datagrams with the same
   (non-zero) Flow ID must have the same Destination Address, Hop
   Options header, and Routing Header contents.  The notion is that by
   simply looking up the Flow ID in a table, the router can decide how
   to route and forward the datagram without examining the rest of the
   header.

Flow ID Issues

   The current specification leaves open a number of questions, which
   the End-to-End group discussed:

        1.   What should a router do if a datagram with a (non-zero)
             Flow ID arrives and the router has no state for that Flow
             ID?

Partridge                                                       [Page 1]

RFC DRAFT                                                  December 1994

        2.   How does an internet flush old Flow IDs?

        3.   Which datagrams should carry (non-zero) Flow IDs?

   This memo summarizes the group's attempts to answer these questions.

What Does a Router Do With Flow IDs for Which It Has No State?

   If a datagram with a non-zero Flow ID arrives at a router and the
   router discovers it has no state information for that Flow ID, what
   is the correct thing for the router to do?

   There is an initial instinct to assume that this scenario only occurs
   in the case of an error, but this may not be the case.  For instance,
   a router that crashes will lose its state, but may be able to recover
   that state after a brief period of operation.  During the recovery
   period, the router will receive datagrams with Flow IDs it does not
   know, but this is arguably not an error, but rather a part of the
   recovery period.

   In any case, it is clear that usual IPv4 error handling, namely to
   drop the datagram and send an ICMP message, is inappropriate.  We
   expect a large number of flows to be multicast, and it is easy to
   envision scenarios in which the flow's sender could be inundated with
   ICMP error messages if some portion of an internet unexpectedly
   starts receiving the flow's datagrams.  Furthermore, it seems likely
   that in most cases, simply forwarding the datagram as one would a
   datagram with a zero Flow ID would give better service to the flow
   than dropping the datagram.  (Note that because the flow may have
   redefined the meaning of the traffic class field, the datagram must
   be forwarded as if the traffic class field was also 0, even if the
   traffic class is non-zero).

   Of course, there will be situations in which routing the datagram as
   if its Flow ID were zero will cause the wrong result.  An example is
   a router which has two paths to the datagram's destination, one via a
   high-bandwidth satellite link and the other via a low-bandwidth ter-
   restrial link.  A high bandwidth flow obviously should be routed via
   the high-bandwidth link, but if the router loses the flow state, the
   router may route the traffic via the low-bandwidth link, with the
   potential for the flow's traffic to swamp the low-bandwidth link.  It
   seems likely, however, these situations will be exceptions rather
   than the rule.   So it seems reasonable to handle these situations
   using options that indicate that if the flow state is absent, the
   datagram needs special handling.  (The options may be Hop-by-Hop or
   only handled at some routers, depending on the flow's needs).

   In summary, the group's view is that the default rule should be that

Partridge                                                       [Page 2]

RFC DRAFT                                                  December 1994

   if a router receives a datagram with an unknown Flow ID, it treats
   the datagram as if the Flow ID and traffic class fields are zero.  As
   part of forwarding, the router will examine any options and learn if
   the the datagram requires special handling.  The options could
   include simply the information that the datagram is to be dropped if
   the Flow ID is unknown or could contain a brief summary of the flow
   state the router should have.  There is clearly room here for experi-
   mentation with option design.

Flushing Old Flow IDs

   The flow mechanism assumes that state associated with a given Flow ID
   is somehow deposited in routers, so they know how to handle datagrams
   that carry the Flow ID.  A serious problem is how to flush Flow IDs
   that are no longer being used (stale Flow IDs) from the routers.

   Stale Flow IDs can happen a number of ways, even if we assume that
   the source always sends a message deleting a Flow ID when the source
   finishes using a Flow.  An internet may have partioned since the flow
   was created.  Or the deletion message may be discarded before reach-
   ing all routers.  Furthermore, the source may crash before it can
   send out a Flow ID deletion message.  The point here is that we can-
   not expect the source (or, for the same reasons, a third party) to
   clear out stale Flow IDs.  Rather routers will have to find some
   mechanism to flush Flow IDs themselves.

   The obvious mechanism is to use a timer.  Routers should discard Flow
   IDs whose state has not been refreshed within some period of time
   (say 2 minutes).  At the same time, a source that crashes must
   observe a quiet time, during which it creates no flows, until it
   knows that all Flow IDs from its previous life must have expired.
   (Sources can avoid quiet time restrictions by keeping information
   about active Flow IDs in stable storage that survives crashes).  This
   is precisely how TCP initial sequence numbers are managed and it
   seems the same mechanism should work well for Flow IDs.

   Exactly how the Flow ID and its state should be refreshed needs some
   study.  There are two obvious options.  The source could periodically
   send out a special refresh message (such as an RSVP Path message) to
   explicitly refresh the Flow ID and its state.  Or, the router could
   treat every datagram that carries the Flow ID as an implicit refresh.
   The choice is between periodically handling a special update message
   and doing an extra computation on each datagram (namely noting in the
   Flow ID's entry that the Flow ID has been refreshed).

Which Datagrams Should Carry (Non-Zero) Flow IDs?

   Interestingly, this is the problem on which the research group made

Partridge                                                       [Page 3]

RFC DRAFT                                                  December 1994

   the least progress.

   There were some points of basic agreement.  Small exchanges of data
   should have a zero Flow ID, because it is not worth creating a flow
   for a few datagrams.  And real-time flows must obviously always have
   a Flow ID, since flows are the main reason Flow IDs were created.
   The issue is what to do with peers sending large amounts of best
   effort traffic (e.g., TCP connections).  Some people want TCP connec-
   tions to use Flow IDs, others do not.

   The argument in favor of using Flow IDs on individual TCP connections
   is that even if the source does not request special service, a net-
   work provider's routers may be able to recognize a large amount of
   traffic and use the Flow ID field to establish a special route that
   gives the TCP connection better service (e.g., lower delay or bigger
   bandwidth).

   The argument against using Flow IDs in individual TCP connections is
   that it changes how we handling route caches in routers.  Currently
   one can cache a route for a destination host, regardless of how many
   different sources are sending to that destination host.  I.e., if
   five sources each have two TCP connections sending data to a server,
   one cache entry containing the route to the server handles all ten
   TCPs' traffic.  Putting Flow IDs in each datagram changes the cache
   into a Flow ID cache, in which there is a cache entry for every TCP
   connection.  So there's a potential for cache explosion.  (One can
   alleviate this slightly by having the multiple Flow ID cache entries
   for the same destination point to the same routing entry, but there's
   still some cost).

   Observe that there is no easy compromise between these positions.
   One cannot, for instance, let the application decide whether to use a
   Flow ID.  Those who want different Flow IDs for every TCP connection
   assume that they may optimize a route without the application's
   knowledge.  And forcing all applications to use Flow IDs will force
   routing vendors to deal with the cache explosion issue, even if we
   later discover that we don't want to optimize individual TCP connec-
   tions.

Recommendations

   Based on its discussion, the End-to-End Group suggests the following
   requirements on Flow IDs be added to the IPv6 specification.

     1.   When a router receives a datagram with an unknown Flow ID, the
          router forwards the datagram as if the Flow Label field was
          set to zero (i.e., both traffic class and Flow ID), unless the
          datagram options indicate different handling is required.

Partridge                                                       [Page 4]

RFC DRAFT                                                  December 1994

          Note that the router is not expected to examine any options it
          would not examine on a datagram with a zero Flow Label.

     2.   Flow IDs should expire if not refreshed within some number of
          minutes (the exact number needs some more consideration) and
          flow sources should observe a quiet time equal to this inter-
          val after rebooting to avoid confusing Flow IDs (unless the
          source keeps track of Flow IDs across reboots).  The exact
          refresh mechanism (periodic messages vs.  implicit refreshes
          on each datagram) is still to be determined.

   The issue of which datagrams should have non-zero Flow IDs is still
   not decided.

Acknowledgements

   I would like to acknowledge the assistance of the members of the
   End-To-End Research Group, chaired by Bob Braden, whose discussions
   produced this memo.  I would also like to particularly thank Deborah
   Estrin for her help in putting this memo together.

Partridge                                                       [Page 5]

---

From: Tony Li <[email-masked]>
Date: Wed, 30 Nov 1994 09:41:51 -0800

Craig,

I take issue with this because it seems to preclude (or at least
ignore) the obvious implementation.  The flow ID cache may be a
fixed-sized LRU cache in front of the existing destination cache.

I don't believe there's even an issue here... just a clearly solvable
implementation problem.

Tony

---

From: Craig Partridge <[email-masked]>
Date: Wed, 30 Nov 94 17:01:18 -0800

Hi Tony:
    
    I think this note misunderstands the problem (or are using a different
architecture base).

    The idea behind this is the following.  Take Van J's fast IP forwarding
code and write it up in assembler for your favorite current processor.
What you'll discover is that, in almost all cases, you are memory bound
not instruction bound.  I.e. the instruction count is small and you're
usually running in-cache instructions, and so the key performance issue
is how likely is your routing table entry to be in the primary cache in
the processor? Provided your cache hit rate is high, you run pretty
quickly.

    OK, now the problem.  Flows force one to split the first level cache
into two caches -- one of flow IDs and one of routing entries (note if one is
tricky, the flow ID table simply points to routing entries in the routing
cache, which improves cache memory usage).  But we're still smashing up our
first level cache differently.  What's more, the flow space is bigger,
so rather than using the, say, 100 or 200 most recent routes (ala Feldmeier's
and Mogul's studies), we may have to cache the most recent 200-500 flow IDs.
This may overflow primary cache, and voila, performance goes down sharply.

    I believe there's an analog of this problem that crops up in other
solutions (like the Cisco 7000).

Craig

---

From: Tony Li <[email-masked]>
Date: Wed, 30 Nov 1994 18:44:43 -0800

Hi Craig,

Thanks for the explanation, yes, it's the latter.  From your
explanation, you're assuming a zero-sum game, which is not necessarily
the case.  I concur that it would be a problem in a zero-sum
architecture.

Not directly, because in the 7000 all caches occupy independent
memories.

Tony

---

From: Masataka Ohta <[email-masked]>
Date: Thu, 1 Dec 94 17:53:22 JST

> the processor? Provided your cache hit rate is high, you run pretty

Aren't you trying to support tommorrow's network with yesterday's LSIs?

If you are using a newtwork of 1500B packets over 1GBps line, you have
12 micro seconds for the forwarding, which is more than enough for tens
of NON-CACHED DRAM accesses.

You may even use multiple processors per an interface. When the memory
latency is the bottleneck, having muptiple processors really helps.

If you are using shorter transfer unit of ATM, MAC layer flow label:
VPI/VCI, which is somehow supposed be recognized by hardware for
the necessary translation, will do the job (provided that RSVP
indirectly affects the link layer setup).

							Masataka Ohta

---

From: Curtis Villamizar <[email-masked]>
Date: Thu, 01 Dec 1994 12:27:18 -0500

> of NON-CACHED DRAM accesses.

It's those pesky TCP ACKs.  Now if we could just stop people from
sending ACKs and using DNS, etc ....  :-)

TCP data packets are more often 552 byte packets and 40 byte acks.

Data point:  average packet size according to Merit data on the NSFNET
varies from 180-260 bytes depending on which month you look at.  

I agree that even a radix tree lookup can be done easily within this
time.  If that was the only thing a processor on a router interface
had to do, then we'd be in good shape.

Curtis

---

From: Masataka Ohta <[email-masked]>
Date: Fri, 2 Dec 94 12:24:33 JST

> TCP data packets are more often 552 byte packets and 40 byte acks.

ACK and DNS? What is it?

It's flow. It's INT-SERV. It's QoS assured. It's MTU discovered.

Well, there may be a small amount of users who use flows with time
consuming setup procedure for DNS look up. So?

						Masataka Ohta

---

From: "Jamshid Mahdavi" <[email-masked]>
Date: Fri, 02 Dec 1994 09:06:54 -0500

> TCP data packets are more often 552 byte packets and 40 byte acks.

One would hope that the IPng and TCPng designers and implementors
won't leave us in this particular bind again.  MTU discovery is out
there and works well when people bother...

--J