Probabilistic packet marking (PPM) is a practical and effective method for IP traceback ofdenial-of-service (DOS) attack. In this paper, an adaptive PPM algorithm is presented: a router marks a passingpacket with a probability which is adaptive to the distance that the packet has traversed, so that a minimumconvergence time for an attacking path can be achieved in the victim. With a new IP header overloading scheme, thelabeled fragment encoding scheme, a real-time reconstruction is provided, so that thousands of paths can be tracedsimultaneously. Compared with previous PPM schemes, a 50% decrease in convergence time is achieved, while thecomputation overhead and false positives in re construction are greatly reduced.