  Distributed Denial-of-Service (DDoS) attacks are a major problem in the
Internet today. In one form of a DDoS attack, a large number of compromised
hosts send unwanted traffic to the victim, thus exhausting the resources of the
victim and preventing it from serving its legitimate clients. One of the main
mechanisms that have been proposed to deal with DDoS is filtering, which allows
routers to selectively block unwanted traffic. Given the magnitude of DDoS
attacks and the high cost of filters in the routers today, the successful
mitigation of a DDoS attack using filtering crucially depends on the efficient
allocation of filtering resources. In this paper, we consider a single router,
typically the gateway of the victim, with a limited number of available
filters. We study how to optimally allocate filters to attack sources, or
entire domains of attack sources, so as to maximize the amount of good traffic
preserved, under a constraint on the number of filters. We formulate the
problem as an optimization problem and solve it optimally using dynamic
programming, study the properties of the optimal allocation, experiment with a
simple heuristic and evaluate our solutions for a range of realistic
attack-scenarios. First, we look at a single-tier where the collateral damage
is high due to the filtering at the granularity of domains. Second, we look at
the two-tier problem where we have an additional constraint on the number of
filters and the filtering is performed on the granularity of attackers and
domains.
