Tradeoffs in Probabilistic Packet Marking for IP Traceback TITLE2
Micah Adler · 2001
Recently, a number of probabilistic packet marking schemes have been proposed for the problem of tracing a sequence of packets back to an anonymous source. This paper introduces a new technique for marking that applies when the packets are all sent along the same path. This new technique allows this path to be traced even when there is only a single bit in the header allocated to the marking scheme. If the path is encoded using $n$ bits, then with this scheme, for any constant $\epsilon < 0$, the number of packets required to reconstruct the path is $O((2+\epsilon)^{2n})$. We also demonstrate that $\Omega(2^n)$ packets are necessary if only one bit is used. To contrast our new technique with existing protocols, we demonstrate that all existing protocols belong to a class of algorithms for which at least $\log n$ bits are required. We also study the tradeoff between $b$, the number of header bits used, and the number of packets required. We provide a protocol such that $O(b n^2 2^b (2+\epsilon)^{4n/2^b})$ packets are sufficient, for any constant $\epsilon < 0$. This protocol is simple enough to be quite effective in practice. We also provide an information theoretic lower bound demonstrating that $\Omega(2^b 2^{n/2^b})$ packets are necessary. These are the first results concerning optimal tradeoffs in probabilistic packet marking.