Estimação de Matrizes de Tráfego Origem-Destino Utilizando Algoritmo Genético
Resumo
A estimação precisa da matriz de tráfego origem-destino a partir do tráfego medido nos enlaces de uma rede IP é um problema complexo para o qual ainda não foi encontrada solução satisfatória. Este trabalho aplica algoritmos genéticos (AG) a este problema de estimação e compara os resultados com aqueles obtidos através de três outras técnicas aplicadas anteriormente: Programação Linear, Estimação Bayesiana e aproximação pelo algoritmo Esperança-Maximização (EM). Além da utilização de AG, uma outra contribuição deste trabalho é um algoritmo de inicialização de parâmetros que diminui o esforço computacional e auxilia a convergência para o resultado esperado. Os experimentos apontam para um melhor desempenho do algoritmo genético do ponto de vista do erro de estimação.
Referências
Cao J., Davis D., Weil S. V., and B. Yu. (2000). Time-Varying Network Tomography. J. of the American Statistical Association.
Goldberg, D.E. (1989). Genetic Algorithms in Search, Optimization and Machine Learning. Editora: Addison-Wesley. New York.
Goldschmidt, O. (2000). ISP Backbone Traffic Inference Methods to Support Traffic Engineering. Em Internet Statistic and Metrics Analisys (ISMA) Workshop, San Diego, CA.
Holland, J.H. (1975). Adaptation in Natural and Artificial Systems. The University of Michigan Press, Ann Arbor, 2nd edition.
Lutton, E.; Martinez, P. (1994). A Genetic Algorithm for the Detection of 2D Geometric Primitives in Images; 1051-4651/94 IEEE. INRIA - Rocquencourt, B.P. 105, 78153 LE CHESNAY Cedex, France.
MATLAB for Windows User’s Guide, The Math Works Inc., 1991.
Medina, A., Taft, N. Salamatain, K. Bhattacharyya, S., Diot, C. (2002). Traffic Matrix Estimation: Existing Techniques and New Directions. SIGCOMM.
Michalewicz, Z. (1996). Genetic Algorithms + Data Structures = Evolution Programs, 3th edition, Springer - Verlag, New York.
Mitchell M. (1996). An Introduction to Genetic Algorithms. MIT Press.
Rschendorf L. (1995). Convergence of the iterative proportional fitting procedure. Annals of Statistics, pages 1160–1174.
Russell , Norvig. (2003). Artificial Intelligence: A Modern Approach. Prentice Hall.
Silva, A. N., Lima, H. O., Pereira, S.S.L., Nobre, D. N., Silva, J. L. C., Maia, J. E. B., Cunha, P. R. F. (2007). Estimação de Matrizes de Tráfego de Backbones utilizando Restrições de Proporcionalidade em Modelo de Programação Linear. SBRC.
Soule, A., Lakhina, A., Taft, N., Papagiannaki, K., Salamatian, K., Nucci, A., Crovella, M., e Diot, C. (2005). Traffic matrices: Balancing measurements, inference and modeling. In Proc. of the ACM SIGMETRICS’05, Banff, Canada.
Soule, A., Nucci, A., Cruz, R., Leonardi, E., e Taft, N. (2004). How to identify and estimate the largest traffic matrix elements in a dynamic environment. In Proc. of the ACM SIGMETRICS’04, Nova Iorque, NY, EUA.
Strang G. (1993). Introduction to Linear Algebra. Wellesley-Cambridge Press.
Tan, K. C., Li, Y., Murray-Smith, D .J. and Sharman, K. C. (1995). Nonlinear Parameter Estimation via the Genetic Algorithm, Proc. IEE/IEEE Int. Conf. On GA in Eng. Syst.: Innovations and Applications, Sheffield, U.K., pp. 164-169.
Tebaldi, C e West, M. (1998). Bayeysian Inference of Network Traffic Using Link Count Data. Journal of the American Statistical Association, pag. 557-573.
Teixeira, R., Duffield, N., Rexford, J., e Roughan, M. (2005). Traffic matrix reloaded: Impact of routing changes. In Proc. of the Passive and Active Measurement Workshop-PAM’2005, Boston, MA, EUA.
Uhlig, S. and Quoitin, B. and Balon, S. and Lepropre, J. (2006). Providing Public Intradomain Traffic Matrices to the Research Community. SIGCOMM Comput. Commun. Rev. ACM Press.
Vardi, Y. (1996). Network tomography: Estimating source-destination traffic intensities from link data, Journal of the American Statistical Association, 91, 365-377.
Whitley D. (1993). A Genetic Algorithm Tutorial. Computer Science Department, Colorado State University.
Ying-ping Chen. (2004). Extending the Scalability of Linkage Learning Genetic Algorithms: Theory and Practice. Dissertation, University of Illinois at Urbana-Champaign.
Zhang, Y., Roughan, M., Duffield, N., e Greenberg, A. (2003a). Fast accurate computation of large-scale IP traffic matrices from link loads. In Proc. of the ACM SIGMETRICS’03, San Diego, CA, EUA.
Zhang, Y., Roughan, M., Lund, C., e Donoho, D. (2003b). An information-theoretic approach to traffic matrix estimation. In Proc. of the ACM SIGCOMM’2003, Karlsruhe, Germany.
Goldberg, D.E. (1989). Genetic Algorithms in Search, Optimization and Machine Learning. Editora: Addison-Wesley. New York.
Goldschmidt, O. (2000). ISP Backbone Traffic Inference Methods to Support Traffic Engineering. Em Internet Statistic and Metrics Analisys (ISMA) Workshop, San Diego, CA.
Holland, J.H. (1975). Adaptation in Natural and Artificial Systems. The University of Michigan Press, Ann Arbor, 2nd edition.
Lutton, E.; Martinez, P. (1994). A Genetic Algorithm for the Detection of 2D Geometric Primitives in Images; 1051-4651/94 IEEE. INRIA - Rocquencourt, B.P. 105, 78153 LE CHESNAY Cedex, France.
MATLAB for Windows User’s Guide, The Math Works Inc., 1991.
Medina, A., Taft, N. Salamatain, K. Bhattacharyya, S., Diot, C. (2002). Traffic Matrix Estimation: Existing Techniques and New Directions. SIGCOMM.
Michalewicz, Z. (1996). Genetic Algorithms + Data Structures = Evolution Programs, 3th edition, Springer - Verlag, New York.
Mitchell M. (1996). An Introduction to Genetic Algorithms. MIT Press.
Rschendorf L. (1995). Convergence of the iterative proportional fitting procedure. Annals of Statistics, pages 1160–1174.
Russell , Norvig. (2003). Artificial Intelligence: A Modern Approach. Prentice Hall.
Silva, A. N., Lima, H. O., Pereira, S.S.L., Nobre, D. N., Silva, J. L. C., Maia, J. E. B., Cunha, P. R. F. (2007). Estimação de Matrizes de Tráfego de Backbones utilizando Restrições de Proporcionalidade em Modelo de Programação Linear. SBRC.
Soule, A., Lakhina, A., Taft, N., Papagiannaki, K., Salamatian, K., Nucci, A., Crovella, M., e Diot, C. (2005). Traffic matrices: Balancing measurements, inference and modeling. In Proc. of the ACM SIGMETRICS’05, Banff, Canada.
Soule, A., Nucci, A., Cruz, R., Leonardi, E., e Taft, N. (2004). How to identify and estimate the largest traffic matrix elements in a dynamic environment. In Proc. of the ACM SIGMETRICS’04, Nova Iorque, NY, EUA.
Strang G. (1993). Introduction to Linear Algebra. Wellesley-Cambridge Press.
Tan, K. C., Li, Y., Murray-Smith, D .J. and Sharman, K. C. (1995). Nonlinear Parameter Estimation via the Genetic Algorithm, Proc. IEE/IEEE Int. Conf. On GA in Eng. Syst.: Innovations and Applications, Sheffield, U.K., pp. 164-169.
Tebaldi, C e West, M. (1998). Bayeysian Inference of Network Traffic Using Link Count Data. Journal of the American Statistical Association, pag. 557-573.
Teixeira, R., Duffield, N., Rexford, J., e Roughan, M. (2005). Traffic matrix reloaded: Impact of routing changes. In Proc. of the Passive and Active Measurement Workshop-PAM’2005, Boston, MA, EUA.
Uhlig, S. and Quoitin, B. and Balon, S. and Lepropre, J. (2006). Providing Public Intradomain Traffic Matrices to the Research Community. SIGCOMM Comput. Commun. Rev. ACM Press.
Vardi, Y. (1996). Network tomography: Estimating source-destination traffic intensities from link data, Journal of the American Statistical Association, 91, 365-377.
Whitley D. (1993). A Genetic Algorithm Tutorial. Computer Science Department, Colorado State University.
Ying-ping Chen. (2004). Extending the Scalability of Linkage Learning Genetic Algorithms: Theory and Practice. Dissertation, University of Illinois at Urbana-Champaign.
Zhang, Y., Roughan, M., Duffield, N., e Greenberg, A. (2003a). Fast accurate computation of large-scale IP traffic matrices from link loads. In Proc. of the ACM SIGMETRICS’03, San Diego, CA, EUA.
Zhang, Y., Roughan, M., Lund, C., e Donoho, D. (2003b). An information-theoretic approach to traffic matrix estimation. In Proc. of the ACM SIGCOMM’2003, Karlsruhe, Germany.
Publicado
12/07/2008
Como Citar
RIBEIRO, Fabiano C.; SILVA, Arnoldo N. da; MAIA, J. E. Bessa; SILVA, Jorge L. C.; CUNHA, Paulo R. F..
Estimação de Matrizes de Tráfego Origem-Destino Utilizando Algoritmo Genético. In: WORKSHOP EM DESEMPENHO DE SISTEMAS COMPUTACIONAIS E DE COMUNICAÇÃO (WPERFORMANCE), 7. , 2008, Belém/PA.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2008
.
p. 127-140.
ISSN 2595-6167.
