Proof of NP-Hardness, new mathematical formulation and constructive heuristic for In-band network monitoring optimization
dc.contributor.advisor | Ravelo, Santiago Valdes | pt_BR |
dc.contributor.author | Nahra, Leonardo Abreu | pt_BR |
dc.date.accessioned | 2020-08-19T03:39:18Z | pt_BR |
dc.date.issued | 2019 | pt_BR |
dc.identifier.uri | http://hdl.handle.net/10183/212981 | pt_BR |
dc.description.abstract | The increasing usage of distributed and cloud-driven network ecosystems have rendered legacy network monitoring obsolete, as they are unable to provide granular visibility to huge amounts of network traffic data exchanged each day. In-Band Network Telemetry (INT) is showing itself to be a promising alternative to these legacy solutions, by allowing active packets to report their metrics within the network system. This new approach can provide the much needed accurate real-time granular network monitoring solution, yet it may cause network performance degradation if applied aimlessly. Work has been done to formalize an optimization problem, namely the Network Monitoring Optimization problem (NEMO), in the search to find an optimum way for a network to report its current state using INT. We build on top of that work. We introduce a generalization of NEMO and proof that such problem is NP-Hard. Then, we propose a new mathematical formulation and a heuristic algorithm for the problem. In our experiments using real-world network configurations, we observed that the proposed heuristic was able to find high-quality solutions to all networks under 1:7 seconds. | en |
dc.format.mimetype | application/pdf | pt_BR |
dc.language.iso | por | pt_BR |
dc.rights | Open Access | en |
dc.subject | Heurística | pt_BR |
dc.subject | In-band network telemetry | en |
dc.subject | Otimizacao combinatoria | pt_BR |
dc.subject | Redes de computadores | pt_BR |
dc.title | Proof of NP-Hardness, new mathematical formulation and constructive heuristic for In-band network monitoring optimization | pt_BR |
dc.type | Trabalho de conclusão de graduação | pt_BR |
dc.contributor.advisor-co | Buriol, Luciana Salete | pt_BR |
dc.identifier.nrb | 001117152 | pt_BR |
dc.degree.grantor | Universidade Federal do Rio Grande do Sul | pt_BR |
dc.degree.department | Instituto de Informática | pt_BR |
dc.degree.local | Porto Alegre, BR-RS | pt_BR |
dc.degree.graduation | Ciência da Computação: Ênfase em Ciência da Computação: Bacharelado | pt_BR |
dc.degree.level | graduação | pt_BR |
Este item está licenciado na Creative Commons License
-
TCC Ciência da Computação (1021)