On Feb 20, 2008, at 6:31 AM, Randall Atkinson wrote:
Elwyn Davies wrote:
% This is still very much a work in progress, but as I said in the
% original message the 'hash' is based on a value chosen randomly
probably
% on a per router basis but then the substitution table is fixed
for all
% packets passing through the router being precalculated based on that
% value and a suitable hash function randomly chosen (think Bloom
% filters). Assuming an 8 or 10 bit value is enough to provide a
% signature sufficient to (probablistically) differentiate between the
% different flow paths once the packets reach the destination
(assumption
% yet to be tested), the per packet processing just consists of a
table
% lookup and fixed width field substitution hopefully in a part of the
% packet which is already accessible in the router fast path (like the
% flow label - the IPv4 case is more problematic).
To maintain router performance at wire speed, the hash function ought
only to use a small number of increments or decrements, with no
multiplies,
if one wants it to be computationally practical on a per-packet basis.
If the hash function is performed once per router, never per-flow
or per-packet,
then it could be more computationally intensive.
As Elwyn noted, per-packet processing is just a straight substitution
of fixed-length values (e.g. swap) from a pre-computed table. There
would be one of these tables per router, or perhaps one table per
router interface (depending on if you want to differentiate between
otherwise identical paths that transit different links between a pair
of adjacent routers). The table itself should be small - if we use 8
bits then it would have 256 entries.
The construction of the table would be more computationally
expensive, but would only happen once per-router or once per-
interface (possibly at boot-up).
% The actual random value and the hash function are pretty much
irrelevant
% as long as packets following different paths will see a different
random
% sequence of substitutions, but two packets following the same
path get
% the same sequence of substitutions resulting in the same pattern
at the
% destination, and thereby differentiating the flow path taken by
the packets.
The goal of the path hash is to give the receiver a hint that the
path from the sender has changed. There are existing header fields
that partly provide this functionality - for example, a path change
might cause the TTL observed by the receiver to change. Of course,
there are also many path changes where the number of router hops
stays the same. By adding the path hash, we would like to make most
(all?) path change events detectable by the receiver. Because we can
use existing header fields (TTL, SRC, DST) to assist in
distinguishing between paths, we may be able to keep the path hash
value itself to a fairly small number of bits. We would lose
fidelity if a great number of the individual router hops were hidden
due to tunneling (i.e. changes to paths between tunnel endpoints not
visible in the values of the packet header observed by the receiver).
Still thinking through this..
R,
Dow
--
to unsubscribe send a message to [EMAIL PROTECTED] with the
word 'unsubscribe' in a single line as the message text body.
archive: <http://psg.com/lists/rrg/> & ftp://psg.com/pub/lists/rrg
