quick note on hash based tracebacks

Mon Jan 20 16:09:04 UTC 2003

The capabilities of hash-based tracebacks has come up a few times in the
past couple of days.  Most of the discussion has been quite accurate (always
nice to see one's work understood!) but there are two points that I thought
might benefit from clarification:

> The SPIE hash-based 
> traceback is a much cooler idea, but it has some practical limitations, 
> including the need to do the trace in more or less real-time (once the 
> hash table fills up, it becomes useless), and the need for very large 
> amounts of very fast memory on the tracing routers.

So that folks understand this point.  SPIE requires a fast memory that
equals a fraction of a second (fraction varies depending on configuration)
times about .2% of link bandwidth to store its hash information.  It then
expects each router to cache (on disk) all the hash tables recorded for
some period of time.

You can actually reduce the router's storage needs by simply sending old
hash tables off to an archive (say at your operations center).  [Remember,
the amount of data kept is a fraction of a percent of the link speed -- so
even if you've got ten lines into a box, the total bandwidth required to copy
their tables to an archive is, *at worst*, around 1%-2% of the bandwidth of the 
fastest link].

> There was an IETF 
> BoF on it, but the folks behind it haven't been pushing it much.  
> (Randy, do you know the status of it?)

Randy encouraged us to go off and write a spec on our own and just bring it
to IETF when done.  Since we've got a customer paying us to work on a
deployable system in his network, we figured we'd take advantage of the
experience (something about "running code" :-)).

Craig

PS: For more info, see the paper in the lastest issue of IEEE/ACM Trans. on
Networking, or read the (somewhat less detailed) paper from ACM SIGCOMM 2001.
The SIGCOMM paper is available on-line at no charge:

    http://doi.acm.org/10.1145/383059.383060