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

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

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
    installation, and use a key in the packets to find it, makes little sense.
    We should do one or the other...

It has been pointed out to me that there are three ways in which to interpret
this statement, and it makes sense to take note of the different way, because
the utility of doing this makes different degrees of sense in the different
ways.

First, there is the meaning I had in mind, where one single flow uses
different mechanisms for different subsystems.

Second, one flow might use a given technique for all its subsystems, and
another flow might use a different technique of its; there is potentially some
use to this, although I'm not sure the cost in complexity of supporting both
mechanisms is worth the benefits.

Third, one flow might use on mechanism with one router along its path, and
another for a different router. A number of different reasons exist as to
why one might do this, including the fact that not all routers may support
the same mechanisms simultaneously.

	Noel

---

From: Jon Crowcroft <[email-masked]>
Date: Wed, 30 Mar 94 21:52:07 +0100

this is the state of my view created by the ietf sessions on int-serv,
rsvp and so forth so far.

a source sends a packet with 1 or 2 things in
1: a tuple, eg. source + ddst, IP addrs and src + dst ports + proto
2: a flow field for routers to do something

a router gets 1 or 2 things
1: a rule for the tuple to map it to a class of traffic
2: a rule for the field to a class of traffic

the rule for the tuple is defined in some useful langauge for flows,
thaty allows you to describe combinations of 
various packet fields that correspond to flowspeecs (e.g. effective
bandwidth, or class queues to put such packetrs into)
, and to define ways of merging various such combinations if their
flow specs are subsets of aggregatable flows in the queueing
system....

the router maintains state that can be indexed by some function on the
flow field if it exists. if the indexing fails to find the state (i.e.
pointer to ther right class queue and associated flow monitoring
statistics), the router may be able to apply the rule for the tuple to
find the state. if this succeeds, it then caches the flow field as a
shortcut to this infomration. if it fails, it may be because an
element of the rule from the  flow to the class is not present in the
packet, but is provided out of band via some reservation protoolc
(wehich has a suitable robust refresh period) - then, when the next
(e.g. RSVP) message arrives at the router, it recreates the map from
whats i nthe pascvket, what is in the RSVP message, to what is in the
flow field, to get the shortcut back to get to the state for classes.

what is in practice being defined:

0. a spec for what goes in RSVP to identify the tuples, the flow field
and the class requirements.
1. a syntax for describing the tuples
2. requirements on the flow field's size from numbers of flows,
efficiencies of indexing, and from some level of security provided by
sparseness (really for prevention of replay or denial of service
attacks)
3. a spec for how to deterimine if a router is doing what the flows
that are traversing it asked for, even in the presewncve of
non-conforming flows.

what is left for router vendors to compete on?
i) the actual queueing algorith used.
ii)the compilers and runtime system for the classification code

what 'free good' can we then measure of a router?
i) the excess bandwidth avaialble under underload conditions to
ii) flexible flows, above their minium requirements.

in the world of us unix hackers, what this means is, that between
route lookup, and output queueing, we need a module that implements
the queueing. It has an API, to hand it class (tuple) definitions
(ioctls), and a classifier compiler, eval engine. we have an rsvpd
that accepts requires, and maps them into classifier updates.

i guess apart fro mthe queues, we have the monitoring police
function, which has to tell whether a flow or aggregate is within 
limits, and the overlimit action function (police state:-)

The test spec can include bradner style things (e.g. classifications
per second per flow per number of flows; discards per second per flow
per number of non-conforming flows, etc etc; these fall out of simply
profiling the functions above, almost gprof style), plus the new measures of
a) how close to 100% class and link utilisation can our queueing algorithm go
and still  police flows correctly (i.e. interaction between how good
the flow spec guess is, the queue alg match to that guess is)
b) how much borrowing is available between underlimit flows and
flexible flows in what time frame (i.e. do we want to permit a lot of
packets to go ionto a queue, only to have an underlimit flow suddenyl
catch up and dump a huge burst of packets into /dev/null from a best
effort ftp?)

anyhow, i can't think of other tests for how Takoma Routers Inc can
make their high end expesnive rouiters distinguisable from Arachnid
Cheapo routers, and explain why (e.g. memory and CPU requirement to
implement more flexible and accurate match of flow requirement to
requested resource)

cheers

jon