Subject: The use of a locally significant classifier "hint"

From: Curtis Villamizar <[email-masked]>
Date: Wed, 13 Apr 94 18:39:24 -0500

At the Seattle IETF, we discussed the use of a "hint" field in the
IPng header.  One suggestion was a unique field chosen at random from
a large range (ie: 32 bits or more) so that it was likely to be
unique.  A suggestion that I brought up was the use of a hint which
was locally significant.  This was discussed only briefly.  I promised
to get back to the list with some details on the idea.

The idea is that policy on how to do classification may be somewhat
localized.  For example, more localized provider A might grant a
subscriber up to X amount of link share credit (units?) of which some
percentage can be used toward reservation.  A more global provider
(one that primarily interconnects more local ones) might grant
provider A some link share regardless of how provider A allocates
among subscribers.  This is closer to the type of relationships
between providers today (only today it's more pipe size oriented).

Within a provider or some domain of consistent policy, there can be
some fairly granularity of packet treatment.  A classifier need only
classify sufficiently well to obtain the right packet treatment.  For
example, a packet classifier may be able to classify all packets as
the same if they leave the domain at the same point and share a common
queueing treatment.  If link sharing is on a fairly course basis,
there may be a small number of possible locally significant
classifications.

If a packet is classified at it's entry point it may be given a
classification hint number that is only locally significant
(significant only to the local router).  The first packet to arrive
that required a new classification can be assigned a new sequential
classification number.  When the packet is forwarded to the next hop,
if the classification number (the hint) has never been seen from the
immendiate source of that packet (the previous hop), the packet must
then be classified and a new locally significant hint assigned and the
packet can be forwarded further.  When a second packet with the same
hint, the hint can provide the next hop, packet treatment (which
queue), and the replacement value for the hint field.  The process
continues at each  internal hop, with only the first packet matching a
particular classification being classified.

If at an internal node a new hint may arrive from a previous hop, but
after classifying the packet, it is discovered that packets from a
another previous hop already match the classification.  In this case,
a new local classification number is not needed but a new mapping is
needed.  At the next hop, the classification number is already known
so the packet can take the fast path through the router without
running the classifier.

An example of where this would be useful is the case where a
institution funds a specific packet treatment within a service
provider for its traffic regardless of the source.  (Two concrete
examples: NSF funds X bandwidth over a NSP at any link regardless of
which regional or source injected the traffic; A corporation funds Y
amount of bandwidth regardless of which of its offices injects the
traffic).  At any bottleneck, the correct packet treatment can be
applied without ever having to classify the traffic.  Forwarding
lookup can actually be much faster since the hint need only point
toward the correct exit point and is by definition an integer lookup.
If the number of classifications is small, forwarding degenerates to
simple table lookup.

An advantage of this approach is that within a domain in which
classification policy or methodology was consistent, classification
generally need only be done at the borders (except for the first
packet of a given classification).  In current networks the borders
are often significantly less loaded than the interior.  It is also
easier and more cost effective to split the load at a border if the
load is due to the aggregation of a great deal of incoming traffic (by
splitting into more entry points) if processing power needed for
classification becomes an issue.

When exiting the claasification domain, the hint can be ignored by the
border router of the bordering domain and all packets reclassified if
the classification granularity is finer.  If the classification
granularity is similar (identical classification or more course), the
hint can be used in conjunction with the exit point from the new
domain, possibly to arrive at a classification more quickly than might
occur if the classifier itself were used.  If the classification of
more global providers (those which concentrate more local providers)
is the same or more course than some of the local providers, this
technique might become very useful (ie: in NRENspeak, classification
might occur at the entry to a regional network and be useable by the
NSP without requiring the NSP to rerun the classifier for the majorty
of packets).

For IPv4, the hint could be held in an IP option.  At certain borders
the IP option can be removed.  This will eliminate the overhead of
carrying the option over slow links where link speed is more an issue
than classifier speed.  For IPng, the question arises of whether it is
faster to keep a fixed header size or better to provide an optional
field for the reason just cited.  For IPv4 (or IPng), avoiding a radix
trie lookup of the next hop could easily outweigh the overhead of
processing the option field.  [aside: Some routers already cache a set
of host addresses.  This would allow a similar fast access but could
cover a much larger number of destinations with the same cache size.]

Routers would need configuration knobs to cause generation of an
outgoing hint on a particular interface and to cause the incoming hint
on a particular interface to be used.  Normally both would be set off.
For interior routers, both options would be turned on for all
interfaces.  For most border router both options would be turned on
for interior interfaces and off for exterior interfaces.  For border
routers where the classification was applicable to the adjacent domain
or the adjacent domain's classification was applicable, the
appropriate option (possibly both of them) could be enabled on
external interfaces.  Of course some means of determining exit point
(gee - BGP and IDRP do this nicely) and specifying how to drive the
classifier are needed and have to consistent within the domain.

I hope this made sense.  I'm afraid I didn't present the idea at all
clearly at the meeting.

Curtis