Removing Undesirable Flows by Edge Deletion
| Autor: | Polevoy, G., Trajanovski, S., Grosso, P., de Laat, C., Kim, D., Uma, R.N., Zelikovsky, A. |
|---|---|
| Přispěvatelé: | System and Network Engineering (IVI, FNWI) |
| Jazyk: | angličtina |
| Rok vydání: | 2018 |
| Předmět: |
Discrete mathematics
Denial-of-service attack 0102 computer and information sciences 01 natural sciences Dynamic programming Set (abstract data type) 03 medical and health sciences Tree (descriptive set theory) 0302 clinical medicine Flow (mathematics) 010201 computation theory & mathematics Greedy approximation 030220 oncology & carcinogenesis Path (graph theory) Enhanced Data Rates for GSM Evolution Mathematics |
| Zdroj: | Combinatorial Optimization and Applications: 12th International Conference, COCOA 2018, Atlanta, GA, USA, December 15-17, 2018 : proceedings, 217-232 STARTPAGE=217;ENDPAGE=232;TITLE=Combinatorial Optimization and Applications Combinatorial Optimization and Applications ISBN: 9783030046507 COCOA |
| ISSN: | 0302-9743 |
| Popis: | Consider mitigating the effects of denial of service or of malicious traffic in networks by deleting edges. Edge deletion reduces the DoS or the number of the malicious flows, but it also inadvertently removes some of the desired flows. To model this important problem, we formulate two problems: (1) remove all the undesirable flows while minimizing the damage to the desirable ones and (2) balance removing the undesirable flows and not removing too many of the desirable flows. We prove these problems are equivalent to important theoretical problems, thereby being important not only practically but also theoretically, and very hard to approximate in a general network. We employ reductions to nonetheless approximate the problem and also provide a greedy approximation. When the network is a tree, the problems are still MAX SNP-hard, but we provide a greedy-based 2l-approximation algorithm, where l is the longest desirable flow. We also provide an algorithm, approximating the first and the second problem within 2√2|E| and 2√2(|E|+|undesirable flows|), respectively, where E is the set of the edges of the network. We also provide a fixed-parameter tractable (FPT) algorithm. Finally, if the tree has a root such that every flow in the tree flows on the path from the root to a leaf, we solve the problem exactly using dynamic programming. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|