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 oughtonly 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 rrg-request@psg.com 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