Subject: RE: [RRG] Path Hash proposal

From: Randall Atkinson <[email-masked]>
Date: Tue, 19 Feb 2008 11:24:16 -0800

Earlier, Dow Street wrote:
% I have also been thinking about this type of path hash
% - a (compressed) record of the router interfaces the packet
% has traversed.  If the receiver saw the hash value change
% over the course of a session, it would be a hint that the path changed:
%
% - restart congestion control / RTT measurements?
% - off-path attacker spoofing packets?
% - persistent oscillation of hash values -> load-balanced links
%   somewhere (watch for packet re-ordering)
%
% It may make sense to have the hash done per router *interface*.
% If we're making host changes, something like this is probably worth
% considering as a part of the information exchange between network
% and endpoint.

Maybe I'm confused, but the above seems to be suggesting that:

1) a hash computation needs to be done for each packet
   that  goes through each router interface along the path
   from origin to destination

2) the hash result is placed somewhere in the packet being
   forwarded, meaning that each packet would be modified
   in transit by each router

If I am not confused, each of those ideas would seem to
increase the per-packet cost of packet forwarding in a
very significant way.  Absent new custom hardware to
support that function, it isn't obvious how it could be done
at line-rate for interesting interface speeds (e.g. 1 Gbps
or higher speed).f

Did I miss something here ?

Yours,

Ran
[email-masked]

--
to unsubscribe send a message to [email-masked] 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

---

From: Dow Street <[email-masked]>
Date: Tue, 19 Feb 2008 11:47:29 -0800

> Did I miss something here ?

That's correct - this would be a new per-packet processing cost,  
probably implemented in hardware.  I'll leave it to the equipment  
designers to comment on the implementation cost / complexity.

R,
Dow

---

From: Randall Atkinson <[email-masked]>
Date: Tue, 19 Feb 2008 12:36:47 -0800

Earlier, Dow Street noted:
% That's correct - this would be a new per-packet processing cost,
% probably implemented in hardware.  I'll leave it to the equipment
% designers to comment on the implementation cost / complexity.

This would be a major increase in equipment costs to ISPs,
as near as I can tell, because changes to per-packet-processing
that require new hardware are not low cost.

The burden on smaller access routers, which often still use
CPU-based forwarding would also be an issue (software is
easier to update, but the increase in number of CPU cycles
per packet is an issue for deployed routers).

Ran

---

From: Dow Street <[email-masked]>
Date: Tue, 19 Feb 2008 13:21:01 -0800

> per packet is an issue for deployed routers).

Thanks, Ran.  I've mostly been thinking about fundamental / long-term  
changes to the architecture, so I'm expecting some cost.  I'm not  
necessarily convinced this specific mechanism would be worth the cost  
- just beginning to think through it.  Any thoughts on how this  
mechanism would compare to other changes to router hardware?  (MPLS,  
IPv6, LPM, ACLs, encryption, etc)

As Elwyn said, I think this could be incrementally deployable (since  
it is only used as a hint).

R,
Dow

---

From: Elwyn Davies <[email-masked]>
Date: Tue, 19 Feb 2008 23:05:23 +0000

Hi.

It might or might not require hardware upgrades but frankly a 
substitution from a precalculated 256 x 1 byte or 1024 byte x 10 bit 
table that is what this 'hash' amounts to is not going to break the CPU 
piggy bank, even on a software device.  We aren't (necessarily) talking 
on the fly HMAC calculations here.

/Elwyn

---

From: Dow Street <[email-masked]>
Date: Wed, 20 Feb 2008 08:48:00 -0800

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