Tracing attack packets to their sources, known as IP traceback, is an
important step to counter distributed denial-of-service (DDoS) attacks.  
In this paper, we propose a novel packet logging based (i.e., hash-based) 
traceback scheme that requires an order of magnitude smaller processing 
and storage cost than the hash-based scheme proposed by Snoeren et al., 
thereby being able to scalable to much higher link speed (e.g., OC-768).  
The baseline idea of our approach is to sample and log a small percentage 
(e.g., 3.3\%) of packets. The challenge of this low sampling rate is that 
much more sophisticated techniques need to be used for traceback.  
Our solution is to construct the attack tree using the correlation between 
the attack packets sampled by neighboring routers.  The scheme using naive 
independent random sampling does not perform well due to the low correlation 
between the packets sampled by neighboring routers.  We invent a sampling 
scheme that improves this correlation and the overall efficiency significantly.
Another major contribution of this work is that we introduce a novel
information-theoretic framework for our traceback scheme to answer important 
questions on system parameter tuning and the fundamental trade-off between the
resource used for traceback and the traceback accuracy.  Simulation
results based on real-world network topologies (e.g. Skitter) match
very well with results from the information-theoretic analysis.  The
simulation results also demonstrate that our traceback scheme can
achieve high accuracy, and scale very well to a large number of
attackers (e.g., 5000+).