Search

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 P=NP, this subproblem is inapproximable within factor 2 log 1−1/loglog c (n) (n) , for n=|E|+|GF| and any ck 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.

Spatially-close network fibers have a significant chance of failing simultaneously in the event of man-made or natural disasters within their geographic area. Network operators are interested in the proper detection and grouping of any existing spatially-close fiber segments, to avoid service disruptions due to simultaneous fiber failures. Moreover, spatially-close fibers can further be differentiated by computing the intervals over which they are spatially close. In this paper, we propose (1) polynomial-time algorithms for detecting all the spatially-close fiber segments of different fibers, (2) a polynomial-time algorithm for finding the spatially-close intervals of a fiber to a set of other fibers, and (3) a fast exact algorithm for grouping spatially-close fibers using the minimum number of distinct risk groups. All of our algorithms have a fast running time when simulated on three real-world network topologies.

It is important that our vital networks (e.g., infrastructures) are robust to more than single-link failures. Failures might for instance affect a part of the network that resides in a certain geographical region. In this paper, considering networks embedded in a two-dimensional plane, we study the problem of finding a critical region - that is, a part of the network that can be enclosed by a given elementary figure (a circle, ellipse, rectangle, square, or equilateral triangle) with a predetermined size - whose removal would lead to the highest network disruption. We determine that there is a polynomial number of non-trivial positions for such a figure that need to be considered and, subsequently, we propose a polynomial-time algorithm for the problem. Simulations on realistic networks illustrate that different figures with equal area result in different critical regions in a network.