Subject: How to create and maintain state in a packet network

From: [email-masked] (Noel Chiappa)
Date: Tue, 29 Mar 94 10:54:59 -0500

It seems to be an item of rough consensus that in the future
internetwork, the routers will need to contain more state about the traffic
flowing through them if we want to provide fair sharing of resources etc.  A
smaller, but influential, group feels that in order to provide certain
services we will need to be able to provide service guarantees, and do so in a
way which requires explicit reservation of resources. All of this means more
state in the routers.
	The interesting question is how this state gets into the routers; is
it inferred from watching the datagrams which flow through the router, or is
in installed in some more explicit way?

	In all of this discussion, I'm passing over the need to retain support
for real datagrams, i.e. transactions which require only a single packet. (In
fact, I'm going to use the term "datagram" from here on out to refer to such
applications, and use the term "packet" to describe the unit of transmission
through the network.) There's clearly no point in storing any state about that
datagram in the routers; it's come and gone in the same packet, and this
discussion is all about state retention, so that's why I don't talk about
them.  However, don't assume from this discussion of how to handle the packets
generated by non-datagram applications that I'm advocating system which
support *only* such packet sequences (which we call "flows").
	As another aside, I still think that the unreliable packet ought to be
the fundamental building block of the internetwork layer. I really like the
design principle that says that we can take any packet and throw it away with
no warning or other action, or take any router and turn it off with no
warning, and have the system still work. The component design simplicity
(since routers don't have to stand on their heads to retain a packet which
they have the only copy of), and overall system robustness, resulting from
these two assumptions is absolutely unloseable.
	Anyway, back to the  question is how the state gets into the routers.

	There is an interesting potential synergy here, because there is
thought being given to routing architectures which, for reasons of engineering
efficiency, store more state in the routers for long-lived flows. (There may
be similar thoughts in the security and billing areas, but I'm not aware of
them.)
	It's important to realize that there is no *fundamental* reason why
this state has to be stored in the routers, and looked up via a key in the
packets. It could easily be repeated in every packet (as a source route), but
we don't plan on doing so for reasons of efficiency in header size (both in
terms of bandwidth, and in processing to create and forward the packets).
	This observation is of some use when thinking about the router state
which is used for doing resource allocation. Some of that state might be
information about the user's service needs; information which could be sent in
each packet, or which can be saved in the router, depending on which makes the
most engineering sense. I call such state, which reflects the desires of the
user, "user state", even when a copy is cached in the routers.
	However, other state is needed for this cannot be stored in each
packet; it's state about the longer-term (i.e. spanning multiple packets)
situation. I call this state "server state".

	There are two schools of thought as to how to proceed. The first says
that for reasons of robustness and simplicity, all "user state" (resource
class info, source route, etc) ought to be repeated in each packet. For
efficiency reasons, the routers may cache such "user state", probably along
with precomputed data derived from the user state. (It makes sense to store
such cached user state along with any applicable server state, of course.)
	This school may be subdivided into two subschools, depending on what
hint they use in the packet to find this cached state. (It's a hint, not a key,
since the state in the router can be discarded at any time without making it
impossible to forward the packet.) In one school, there's a field (the flow-id)
whose sole purpose in life is to be a hint. In the other school, a number of
other fields (source as source and destination address, port, etc) combine to
be the hint.
	The second school says that it's simply going to be too inefficient
to carry all the user state around all the time, and we should just bite
the bullet, install it in the routers directly, and include in the packets
a key (also called a flow-id, just to be confusing) to find that state.
I call this this "installation" school.

	I'm not sure how much use there is to any intermediate position. It
seems to me that to have one internetwork layer subsystem (e.g. resource
allocation) carry user state in all the packets, and use a hint in the packets
to find it, and have a second (e.g. routing) use a direct installaion, and use
a key in the packets to find it, makes little sense. We should do one or the
other, based on a consideration of the efficiency/robustness tradeoff.

	It's a little difficult to make this choice without more information
of exactly how much user state the network is likely to have in the
future (i.e. we might wind up with 500 byte headers if we include the
full source route, resource reservation, etc, etc in every header).
	It's also difficult without consideration of the actual mechanisms
involved. As a general principle, we wish to make recovery from a loss of
state as local as possible, to limit the number of entities which have to
become involved. For instance, when a router crashes, traffic is rerouted
around it without needing to open a new TCP connection.
	In a similar way, the option of the "installation" looks a lot more
attractive if it's plausible, and relatively cheap, to reinstall the user
state when a router crashed, without otherwise causing a lot of hassle.

	My intuition tells me that in the long run we're better off with
just biting the bullet on user state, and going to an installation paradigm
with keys, not replicated user state in each packet with hints, but until
we see more details it may prove difficult to know for sure which way is
the best way.

	Noel

---

From: John Hascall <[email-masked]>
Date: Tue, 29 Mar 94 12:44:39 CST

[...]
> 	Anyway, back to the  question is how the state gets into the routers.
[...]
> 	There are two schools of thought as to how to proceed.
    [...school  1)  all state in every packet...]
    [....subschool  1a)  dedicated field in packet as hint to state cache...]
    [....subschool  1b)  combine existing fields as hint...]
    [...school  2)  install state in routers, key in packet to find state...]

> 	I'm not sure how much use there is to any intermediate position.

    It seems to me that there is an intermediate position worth exploring.

    Have a hint in the packet (preferably a dedicated one in my eyes),
    and have the initial packet contain the state as an option (a la
    TCP MSS).  Since it is a hint the router could discard it based on
    whatever criteria (LRU, timeout, lack of space, crash, etc.).

    It seems to me you would want a way for a router to request the
    hint again (if it was discarded or if the routing changed and new
    router wanted the hint).  ICMP or its successor would seem the
    most obvious methodology to request it occur in the next convenient
    packet.

John
-----------------------------------------------------------------------------
John Hascall                      An ill-chosen word is the fool's messenger.
Systems Software Engineer
Project Vincent
Iowa State University Computation Center  +  Ames, IA  50011  +  515/294-9551