Subject: A taxonomy of state and tags in datagram networks

From: [email-masked] (Noel Chiappa)
Date: Tue, 29 Mar 94 09:13:40 -0500

As a result of discussions in the Int-Serv WG sessions yesterday, I'd
like to suggest a framework for thinking about, and set of terms for
describing, the state in datagram network systems. I think this framework will
both help us understand more clearly what's going on, and the common
terminology will allow us to have discussions without getting confused.
	I want to emphasize that I'm not pushing one design or another, just
trying to give us a common framework which we can use to understand, discuss,
and evaluate different designs in.

	I don't distinguish between "state" (which one normally thinks of as
data which records something transitory about a given process), and
information (which might be seen as a little more permanent), since it's
merely a matter of time-scale; there's very transient state (such as the
hop-count), intermediate lifetime (such as information about a flow), and
long-lived (such as routing table entries). However, it's all just state
in the end.
	I start by observing that even "classic" IPv4 has state in both the
routers, and the packets.

	In the packet, I distinguish between what I call "forwarding state",
which records something about the progress of this individual packet through
the network (such as the hop count, or the pointer into a source route), and
what I call "tags", which are fields which are used, in the routers through
which the packet passes, to look up various state stored in the routers.
An example of tags in the current IPv4 architecture is the "address", which is
used to look up routing table state; a "flow-id" might be a future tag.
	I further subdivide tags into two sub-classes; "keys" and "hints".  A
key is a field without which, or without the state in the router to which it
refers, one cannot forward the packet; the "address" is such a field in IPv4.
A hint is a field which is not necessary for the forwarding of the packet, but
which makes the forwarding more efficient if the hint is correct, and the
state in the router to which it refers is present.

	In the routers, there is a similar distinction between state which
must be present for the forwarding process to be sucessful, which we might
call "necessary" state (although I don't like this term, and welcome a better
one), such as routing table entries; and cached state which is not necessary
for the correct forwarding of packets. The term "soft state" is, I believe,
sometimes used to refer to the latter kind of state.
	Note that neither of these states is what we refer to as "critical"
state, i.e. state which is critical to a given end-end communication, and
which, once lost, means the loss of the connection. An example of this is
the state of a TCP connection, as stored co-located (i.e. sharing fate) with
the application.

	Having defined this way of looking at state, I'll put some thoughts
on how we ought to create and maintain this state in a separate message.

	Noel

---

From: braden (Bob Braden)
Date: Tue, 29 Mar 1994 10:35:03 -0800

*> one), such as routing table entries; and cached state which is not necessary
  *> for the correct forwarding of packets. The term "soft state" is, I believe,
  *> sometimes used to refer to the latter kind of state.

Noel,

I would say that cached state is simply an example of
soft state.  The essential feature of soft state is
that the router is allowed to delete it without an
explicit deletion request.  RSVP state is another example
of soft state; if it is deleted, packets cannot be
forwaarded "correctly" (although they may or may not
be forwarded as best-effort datagrams).  Yet a
router is allowed to time it out and delete the
RSVP state that is not refreshed.

  *> 	Note that neither of these states is what we refer to as "critical"
  *> state, i.e. state which is critical to a given end-end communication, and
  *> which, once lost, means the loss of the connection. An example of this is
  *> the state of a TCP connection, as stored co-located (i.e. sharing fate) with
  *> the application.

YOu have to get over this exclusively connectiontist view of
applications, Noel!  Most realtime applications don't have state in
that sense.

Bob Braden