Date Added: Apr 2010
Traceback schemes aim at identifying the source(s) of a sequence of packets and the nodes these packets traversed. This is useful for tracing the sources of high volume traffic, e.g., in Distributed Denial-of-Service (DDoS) attacks. In this paper, the authors are particularly interested in Probabilistic Packet Marking (PPM) schemes, where intermediate nodes probabilistically mark packets with information about their identity and the receiver uses information from several packets to reconstruct the paths they have traversed. Their paper is inspired by two observations. First, PPM is essentially a coupon collector's problem. Second, the coupon collector's problem significantly benefits from network coding ideas.