Cyclical deterministic packet marking

Packet marking is a popular technique used in IP traceback. The existing packet marking techniques are categorized into probabilistic packet marking (PPM) and deterministic packet marking (DPM). Each has their respective strengths and weaknesses. In this paper, we propose a novel protocol, called cyclical deterministic packet marking (CDPM), to address the issues challenging the existing approaches. CDPM demands routers along the attack path to deterministically mark the packets in a sequential and cyclical fashion. This new method exhibits some unique advantages. When compared with probabilistic marking techniques, our approach requires much less marked packets to reconstruct the attack path. It is also more resilient to packet spoofing and, in particular, packet loss. Furthermore, the marking and decoding computation is of reasonable complexity. It can also reveal more complete path than the existing DPM based mechanisms. To the best of our knowledge, this paper is the first of its kind considering the impact of the packet loss in designing packet marking scheme.