-----------------------------------------------------------------------
                   B O S T O N   U N I V E R S I T Y
                      Computer Science Department
                          C O L L O Q U I U M
                      Wednesday, April 3, 3:00 PM 
                       (Coffee served at 2:45 PM)
                         Seminar Room / MCS 135


        Tradeoffs in Probabilistic Packet Marking for IP Traceback


                              Micah Adler
		  University of Massachusetts, Amherst

                              Abstract

There has been considerable recent interest in probabilistic packet
marking schemes for the problem of tracing a sequence of network packets
back to an anonymous source. An important consideration for such schemes
is b, the number of packet header bits that need to be allocated to the
marking protocol. However, all previous schemes belong to a class of
protocols for which b must be at least log(n), where n is the number of
bits used to represent the path of the packets. In this talk, we
introduce a new marking technique for tracing a sequence of packets sent
along the same path. This new technique is effective even when b=1. In
other words, the sequence of packets can be traced back to their source
using only a single bit in the packet header. With this scheme, the
number of packets required to reconstruct the path is O(2^(2n)), but we
also show that Omega(2^n) packets are required for any protocol where b=1.

We also study the tradeoff between b and the number of packets required. 
We provide a protocol and a lower bound that together demonstrate that 
for the optimal protocol, the number of packets required (roughly) 
increases exponentially with n, but decreases doubly exponentially with b.
The protocol we introduce is simple enough to be useful in practice. We 
also study the case where the packets are sent along k different paths. 
For this case, we demonstrate that any protocol must use at least log(2k-2)
header bits. We also provide a protocol that requires log(2k+1) header bits 
in some restricted scenarios (to which the lower bound applies). This 
protocol introduces a new coding technique that may be of independent 
interest.


Host: Azer Bestavros and John Byers
-------------------------------------------------------------------------
For colloquium info, including directions, see http://cs-www.bu.edu/colloquium
-------------------------------------------------------------------------