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