Filtering Undesirable Flows in Networks

We study the problem of fully mitigating the effects of denial of service by filtering the minimum necessary set of the undesirable flows. First, we model this problem and then we concentrate on a subproblem where every good flow has a bottleneck. We prove that unless \(\text {P}= \text {NP}\), this subproblem is inapproximable within factor \(2^{\log ^{1 - 1/\log \log ^c (n)}(n)}\), for \(n = \left| E \right| + \left| GF \right| \) and any \(c < 0.5\). We provide a \(b (k + 1)\)-factor polynomial approximation, where k bounds the number of the desirable flows that a desirable flow intersects, and b bounds the number of the undesirable flows that can intersect a desirable one at a given edge. Our algorithm uses the local ratio technique.