### Trade-offs in probabilistic packet marking for IP tracebackTrade-offs in probabilistic packet marking for IP traceback

Access Restriction
Subscribed

 Author Adler, Micah Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2005 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Denial of Service Abstract There has been considerable recent interest in probabilistic packet marking schemes for the problem of tracing a sequence of network packets back to an anonymous source. An important consideration for such schemes is the number of packet header bits that need to be allocated to the marking protocol. Let $\textit{b}$ denote this value. All previous schemes belong to a class of protocols for which $\textit{b}$ must be at least log $\textit{n},$ where $\textit{n}$ is the number of bits used to represent the path of the packets. In this article, we introduce a new marking technique for tracing a sequence of packets sent along the same path. This new technique is effective even when $\textit{b}$ = 1. In other words, the sequence of packets can be traced back to their source using only a single bit in the packet header. With this scheme, the number of packets required to reconstruct the path is $O(2^{2n}),$ but we also show that $Ω(2^{n})$ packets are required for any protocol where $\textit{b}$ = 1. We also study the trade-off between $\textit{b}$ and the number of packets required. We provide a protocol and a lower bound that together demonstrate that for the optimal protocol, the number of packets required (roughly) increases exponentially with $\textit{n},$ but decreases doubly exponentially with $\textit{b}.$ The protocol we introduce is simple enough to be useful in practice. We also study the case where the packets are sent along $\textit{k}$ different paths. For this case, we demonstrate that any protocol must use at least $log(2\textit{k}$ ™ 1) header bits. We also provide a protocol that requires $⌈log(2\textit{k}$ + 1)⌉ header bits in some restricted scenarios. This protocol introduces a new coding technique that may be of independent interest. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2005-03-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 52 Issue Number 2 Page Count 28 Starting Page 217 Ending Page 244

#### Open content in new tab

Source: ACM Digital Library