O Problema de Deteção e Localização de Eventos em Séries Temporais Aplicado a Redes de Computadores

• Diego Ximenes UFRJ
• Gabriel Mendonça UFRJ
• Gustavo H. A. Santos UFRJ
• Edmundo de Souza e Silva UFRJ
• Rosa M. M. Leão UFRJ
• Daniel S. Menasché UFRJ

DOI: https://doi.org/10.5753/wperformance.2018.3323

Resumo

Atualmente provedores de serviço de Internet (ISPs) fornecem infraestrutura para diversos serviços essenciais. Portanto, é fundamental detetar e localizar problemas na rede de forma automática. Apesar de esforços de monitoramento feito pelos ISPs, eles ainda não têm as ferramentas apropriadas para processar a enorme quantidade de dado gerado por medições de QoS realizadas dezenas de vezes por dia. Essa tarefa não é trivial. Propomos uma abordagem para detetar e localizar automaticamente problemas nas redes dos ISPs a partir de séries temporais resultantes de medições de QoS e traceroutes. Nosso framework é baseado no problema denominado de change point detection, em classificação não-supervisionada e inferência de topologia de rede. Aplicamos nosso framework em dados reais obtidos durante vários meses.

Referências

Adams, A., Lapukhov, P., and Zeng, J. H. (2016). NetNORAD: Troubleshooting networks via end-to-end probing. [link].

Adams, R. P. and MacKay, D. J. (2007). Bayesian online changepoint detection. arXiv preprint arXiv:0710.3742.

Aminikhanghahi, S. and Cook, D. J. (2017). A survey of methods for time series change point detection. Knowledge and information systems, 51(2):339–367.

Choffnes, D. R., Bustamante, F. E., and Ge, Z. (2010). Crowdsourcing service-level network event monitoring. SIGCOMM Comput. Commun. Rev., 40(4):387–398.

Fearnhead, P. (2006). Exact and efficient bayesian inference for multiple changepoint problems. Statistics and Computing, 16(2):203–213.

Kehagias, A. (2004). A hidden markov model segmentation procedure for hydrological and environmental time series. Stochastic Environmental Research and Risk Assessment, 18(2):117–130.

Kifer, D., Ben-David, S., and Gehrke, J. (2004). Detecting change in data streams. In Proceedings of the Thirtieth International Conference on Very Large Data Bases - Volume 30, VLDB ’04, pages 180–191. VLDB Endowment.

Luong, T. M., Rozenholc, Y., and Nuel, G. (2013). Fast estimation of posterior probabilities in change-point analysis through a constrained hidden markov model. Computational Statistics and Data Analysis, 68:129 – 140.

Maidstone, R., Hocking, T., Rigaill, G., and Fearnhead, P. (2017). On optimal multiple changepoint algorithms for large data. Statistics and Computing, 27(2):519–533.

Montañez, G. D., Amizadeh, S., and Laptev, N. (2015). Inertial hidden markov models: Modeling change in multivariate time series. In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, AAAI’15, pages 1819–1825. AAAI Press.

Parhami, B. (1994). Voting algorithms. IEEE transactions on reliability, 43(4):617–629.

Su, W.-x., Zhu, Y.-l., Liu, F., and Hu, K.-y. (2013). On-line outlier and change point detection for time series. Journal of Central South University, 20(1):114–122.

Truong, C., Oudre, L., and Vayatis, N. (2018). A review of change point detection methods. arXiv preprint arXiv:1801.00718.

Yan, H., Flavel, A., Ge, Z., Gerber, A., Massey, D., Papadopoulos, C., Shah, H., and Yates, J. (2012). Argus: End-to-end service anomaly detection and localization from an isp’s point of view. In 2012 Proceedings IEEE INFOCOM, pages 2756–2760.