Probabilistic Packet Marking algorithm, one promising solution to the IP traceback problem, uses one fixed marking space to store router information. Since this fixed space is not sufficient for storing all routers information, each router writes its information into packets chosen with probability p, so-called probabilistic marking. Probabilistic marking seems to be helpful in lowering router overhead, however, it also bring computation overhead for the victim to reconstruct the attack paths and large number of false positives. In this paper, we present a new approach for IP traceback, Deterministic Packet Marking Scheme with Link Signatures, which needs routers mark all packets during forwarding (so-called deterministic marking). We make a study of how much both the probabilistic and our deterministic packet marking schemes affect router overhead through simulations. The results confirm that our deterministic marking scheme will slightly lower router overhead, and besides, it has superior performance than another improved probabilistic packet marking method, Advanced Marking Schemes. Further performance analysis and simulation results are given to show that our technique is superior in precision to previous work—it has almost zero false positive rate. It also has lower computation overhead for victim and needs just a few packets to trace back attacks and to reconstruct the attack paths even under large scale distributed denial-of-service attacks. In addition, our scheme is simple to implement and support incremental deployment.