CMPSCI Theory Seminar

There has been considerable interest in the past few years concerning probabilistic packet marking (PPM) techniques to solve the IP traceback problem. A formal study of the efficiency metrics of PPM techniques was initiated by Adler with a new approach for PPM that is much more efficient in terms of the number of header bits required. In this paper, we improve on and further study further existing PPM techniques in the following ways:

1. We advocate separating the design of a PPM technique into two components: path encoding and transmission technique.
2. We provide an in-depth empirical evaluation of our new technique and determine, for any path encoding, a precise estimate on the number of packets required to reconstruct that path encoding.
3. We figure out how to set parameters of our technique for better performance.
4. We provide a considerably simple description of our technique.
5. We demonstrate how to apply our transmission technique to a variety of path encodings including some new encodings.
6. Finally, we show an initial application of a novel technique that is able to decrease the length of path encoding hence the number of packets in an incremental way.

Last modified 2 December 2002